7 ms·

Notes on Concurrency Bugs (2016)

67 points by zdw 4y ago

hollerith 4y ago
Published in 2016.
- BlackFingolfin 4y ago
  I greatly enjoy reading his articles, but I wonder why he seemingly refuses to put a date on them?
  - hollerith 4y ago
    The table of contents has the date or more precisely the month of publication: https://danluu.com/ https://danluu.com/
  - zasdffaa 4y ago
    maybe contact him and suggest it.
    - fanf2 4y ago
      He explained why recently on Twitter https://twitter.com/danluu/status/1521583578856902656 https://twitter.com/danluu/status/1521583578856902656
      - pvg 4y ago
        Obviously Dan Luu should format his own stuff exactly the way he wants but I can't say I follow this explanation at all. It seems to be something about people jumping to iffy conclusions based on the dates and commenting about it online? Some people jump to iffy conclusions in general and comment about it online. The solution of annoying everyone because of a minority of annoying people feels like a net increase in annoyance.
bombcar 4y ago
One thing I take away from this is that it is worth it to add a data-verification layer to your files, even if you think/know the filesystem will be handling that for you. It becomes especially more important if corruption would go unnoticed otherwise.
- SpicyLemonZest 4y ago
  Absolutely agreed. I’ve been through a couple debates about whether it’s worth adding a checksum, and every time we’ve either been glad we did or regretted that we didn’t.
photochemsyn 4y ago
Reading down: > "Note that all of the programs studied were written in C or C++, and that this study predates C++11. Moving to C++11 and using atomics and scoped locks would probably change the numbers substantially, not to mention moving to an entirely different concurrency model."
- Matthias247 4y ago
  Even pre C++11 scoped locks where commonly used - eg via boost::lock_guard. But RAII locks just solve one problem from a huge bag of potential problems: Forgetting to unlock in all path. They won’t fix deadlocks, forgetting to synchronize at all, inconsistent locking, race conditions and other pain points.
  - hinkley 4y ago
    'Security primitives' aren't an accident of naming. Concurrency mechanisms we've had from the 70's are still contentious precisely because they don't compose. Everything is great when you have one or two concerns trying to do things in parallel, but when your whole app is doing it... it is a rare person who can figure out why things are breaking in magical ways. Most people are overwhelmed by the prospect or the number of things they have to consider. If SOLID principals apply in spades to regular code, then there's a power law for concurrent code. When Simon Peyton Jones was working at Microsoft Research on Software Transactional Memory, he prefaced practically every video/interview with this uncomfortable fact. Given the lack of traction, I can only assume that some of the corner cases of STM proved to be intractable, and my read on the domain is that borrow semantics are trying to arrive at a similar place by different avenues. I'm very interested to see 1) how far borrow semantics get, in the same way that type inference simplifies generics, and 2) what someone tries next, particularly if it involves synthesizing elements from different schools.
    - jerf 4y ago
      The problem with STM is A: You can not retrofit it on to an existing language and B: The language you build to support it looks an awful lot like Haskell, particularly the careful separation between pure and IO code. And as of 2022, most programmers are not willing to program that way. I do a lot of concurrency stuff, and my go-to is one form or another of message passing. It isn't a miracle cure, but it turns the exponentially complicated issues with lock-based systems into polynomial ones, and that's at least something you have a prayer of managing. They compose better. I'm not sure I'd say they compose well, and someone may yet find an even better model, but they compose better. (STM doesn't seem to be that model. As the transactions inevitably get larger over time they start getting complicated.)
slurpmaker 4y ago
I'll leave this here: https://doc.rust-lang.org/book/ch16-00-concurrency.html https://doc.rust-lang.org/book/ch16-00-concurrency.html
- deleted 4y ago
  [deleted]
- nyanpasu64 4y ago
  In terms of shared-memory threading concurrency, Send and Sync, and the distinction between &T and &Mutex<T> and &mut T, were a revelation when I first learned them. It was a principled approach to shared-memory threading, with Send/Sync banning nearly all of the confusing and buggy entangled-state codebases I've seen and continue to see in C++ (much to my frustration and exasperation), and &Mutex<T> providing a cleaner alternative design (there's an excellent article on its design at http://cliffle.com/blog/rust-mutexes/ http://cliffle.com/blog/rust-mutexes/). My favorite simple concurrent data structure is https://docs.rs/triple_buffer/latest/triple_buffer/struct.TripleBuffer.html https://docs.rs/triple_buffer/latest/triple_buffer/struct.Tr.... It beautifully demonstrates how you can achieve principled shared mutability, by defining two "handle" types (living on different threads), each carrying thread-local state (not TLS) and a pointer to shared memory, and only allowing each handle to access shared memory in a particular way. This statically prevents one thread from calling a method intended to run on another thread, or accessing fields local to another thread (since the methods and fields now live on the other handle). It also demonstrates the complexity of reasoning about lock-free algorithms (https://github.com/HadrienG2/triple-buffer/issues/14 https://github.com/HadrienG2/triple-buffer/issues/14). I suppose &/&mut is also a safeguard against event-loop and reentrancy bugs (like https://github.com/quotient-im/Quaternion/issues/702 https://github.com/quotient-im/Quaternion/issues/702). I don't think Rust solves the general problem of preventing deadlocks within and between processes (which often cross organizational boundaries between projects and distinct codebases, with no clear contract on allowed behavior and which party in a deadlock is at fault), and non-atomicity between processes on a single machine (see my PipeWire criticism at https://news.ycombinator.com/item?id=31519951 https://news.ycombinator.com/item?id=31519951). File saving is also difficult (https://danluu.com/file-consistency/ https://danluu.com/file-consistency/), though I find that fsync-then-rename works well enough if you don't need to preserve metadata or write through file (not folder) symlinks. I wonder how https://lwn.net/Articles/789600/ https://lwn.net/Articles/789600/ is doing now.
deleted 4y ago
[deleted]
legulere 4y ago
The type of bug described for MySQL has a special name: time-of-check to time-of-use https://en.wikipedia.org/wiki/Time-of-check_to_time-of-use https://en.wikipedia.org/wiki/Time-of-check_to_time-of-use
- agumonkey 4y ago
  solution for this is atomic block / compare-and-swap ?
jeffreygoesto 4y ago
The general problem is that threads are the worst concurrency model ever... https://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf https://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-...
- deleted 4y ago
  [deleted]
dang 4y ago
Discussed at the time: Notes on concurrency bugs - https://news.ycombinator.com/item?id=12234922 https://news.ycombinator.com/item?id=12234922 - Aug 2016 (26 comments)

67 points by zdw 4y ago

hollerith 4y ago

Published in 2016.

BlackFingolfin 4y ago
I greatly enjoy reading his articles, but I wonder why he seemingly refuses to put a date on them?
- hollerith 4y ago
  The table of contents has the date or more precisely the month of publication: https://danluu.com/ https://danluu.com/
- zasdffaa 4y ago
  maybe contact him and suggest it.
  - fanf2 4y ago
    He explained why recently on Twitter https://twitter.com/danluu/status/1521583578856902656 https://twitter.com/danluu/status/1521583578856902656
    - pvg 4y ago
      Obviously Dan Luu should format his own stuff exactly the way he wants but I can't say I follow this explanation at all. It seems to be something about people jumping to iffy conclusions based on the dates and commenting about it online? Some people jump to iffy conclusions in general and comment about it online. The solution of annoying everyone because of a minority of annoying people feels like a net increase in annoyance.

bombcar 4y ago

One thing I take away from this is that it is worth it to add a data-verification layer to your files, even if you think/know the filesystem will be handling that for you. It becomes especially more important if corruption would go unnoticed otherwise.

SpicyLemonZest 4y ago
Absolutely agreed. I’ve been through a couple debates about whether it’s worth adding a checksum, and every time we’ve either been glad we did or regretted that we didn’t.

photochemsyn 4y ago

Reading down: > "Note that all of the programs studied were written in C or C++, and that this study predates C++11. Moving to C++11 and using atomics and scoped locks would probably change the numbers substantially, not to mention moving to an entirely different concurrency model."

Matthias247 4y ago
Even pre C++11 scoped locks where commonly used - eg via boost::lock_guard. But RAII locks just solve one problem from a huge bag of potential problems: Forgetting to unlock in all path. They won’t fix deadlocks, forgetting to synchronize at all, inconsistent locking, race conditions and other pain points.
- hinkley 4y ago
  'Security primitives' aren't an accident of naming. Concurrency mechanisms we've had from the 70's are still contentious precisely because they don't compose. Everything is great when you have one or two concerns trying to do things in parallel, but when your whole app is doing it... it is a rare person who can figure out why things are breaking in magical ways. Most people are overwhelmed by the prospect or the number of things they have to consider. If SOLID principals apply in spades to regular code, then there's a power law for concurrent code. When Simon Peyton Jones was working at Microsoft Research on Software Transactional Memory, he prefaced practically every video/interview with this uncomfortable fact. Given the lack of traction, I can only assume that some of the corner cases of STM proved to be intractable, and my read on the domain is that borrow semantics are trying to arrive at a similar place by different avenues. I'm very interested to see 1) how far borrow semantics get, in the same way that type inference simplifies generics, and 2) what someone tries next, particularly if it involves synthesizing elements from different schools.
  - jerf 4y ago
    The problem with STM is A: You can not retrofit it on to an existing language and B: The language you build to support it looks an awful lot like Haskell, particularly the careful separation between pure and IO code. And as of 2022, most programmers are not willing to program that way. I do a lot of concurrency stuff, and my go-to is one form or another of message passing. It isn't a miracle cure, but it turns the exponentially complicated issues with lock-based systems into polynomial ones, and that's at least something you have a prayer of managing. They compose better. I'm not sure I'd say they compose well, and someone may yet find an even better model, but they compose better. (STM doesn't seem to be that model. As the transactions inevitably get larger over time they start getting complicated.)

slurpmaker 4y ago

I'll leave this here: https://doc.rust-lang.org/book/ch16-00-concurrency.html https://doc.rust-lang.org/book/ch16-00-concurrency.html

deleted 4y ago
[deleted]
nyanpasu64 4y ago
In terms of shared-memory threading concurrency, Send and Sync, and the distinction between &T and &Mutex<T> and &mut T, were a revelation when I first learned them. It was a principled approach to shared-memory threading, with Send/Sync banning nearly all of the confusing and buggy entangled-state codebases I've seen and continue to see in C++ (much to my frustration and exasperation), and &Mutex<T> providing a cleaner alternative design (there's an excellent article on its design at http://cliffle.com/blog/rust-mutexes/ http://cliffle.com/blog/rust-mutexes/). My favorite simple concurrent data structure is https://docs.rs/triple_buffer/latest/triple_buffer/struct.TripleBuffer.html https://docs.rs/triple_buffer/latest/triple_buffer/struct.Tr.... It beautifully demonstrates how you can achieve principled shared mutability, by defining two "handle" types (living on different threads), each carrying thread-local state (not TLS) and a pointer to shared memory, and only allowing each handle to access shared memory in a particular way. This statically prevents one thread from calling a method intended to run on another thread, or accessing fields local to another thread (since the methods and fields now live on the other handle). It also demonstrates the complexity of reasoning about lock-free algorithms (https://github.com/HadrienG2/triple-buffer/issues/14 https://github.com/HadrienG2/triple-buffer/issues/14). I suppose &/&mut is also a safeguard against event-loop and reentrancy bugs (like https://github.com/quotient-im/Quaternion/issues/702 https://github.com/quotient-im/Quaternion/issues/702). I don't think Rust solves the general problem of preventing deadlocks within and between processes (which often cross organizational boundaries between projects and distinct codebases, with no clear contract on allowed behavior and which party in a deadlock is at fault), and non-atomicity between processes on a single machine (see my PipeWire criticism at https://news.ycombinator.com/item?id=31519951 https://news.ycombinator.com/item?id=31519951). File saving is also difficult (https://danluu.com/file-consistency/ https://danluu.com/file-consistency/), though I find that fsync-then-rename works well enough if you don't need to preserve metadata or write through file (not folder) symlinks. I wonder how https://lwn.net/Articles/789600/ https://lwn.net/Articles/789600/ is doing now.

deleted 4y ago

[deleted]

legulere 4y ago

The type of bug described for MySQL has a special name: time-of-check to time-of-use https://en.wikipedia.org/wiki/Time-of-check_to_time-of-use https://en.wikipedia.org/wiki/Time-of-check_to_time-of-use

agumonkey 4y ago
solution for this is atomic block / compare-and-swap ?

jeffreygoesto 4y ago

The general problem is that threads are the worst concurrency model ever... https://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf https://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-...

deleted 4y ago
[deleted]

dang 4y ago

Discussed at the time: Notes on concurrency bugs - https://news.ycombinator.com/item?id=12234922 https://news.ycombinator.com/item?id=12234922 - Aug 2016 (26 comments)