Notes on Concurrency Bugs (2016) | Hacker News Reader

Notes on Concurrency Bugs (2016)

danluu.com

67 pointszdw25 comments

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."

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.

'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.

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.)

> forgetting to synchronize at all, inconsistent locking

At least for these two classes of categories, mutex usage at Google is broadly paired with compiler-enforced annotations to enforce that _all_ accesses to mutex-guarded member variables are done while holding the appropriate mutex.

https://abseil.io/docs/cpp/guides/synchronization#thread-ann...

(While yes, it can also help with deadlock avoidance as well, that tends to be trickier to enforce across the board, especially if the mutexes in question belong to different objects. There's separate deadlock detection baked into Abseil that's used primarily in non-production builds.)

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

solution for this is atomic block / compare-and-swap ?

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.

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.

Discussed at the time:

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

Published in 2016.

I greatly enjoy reading his articles, but I wonder why he seemingly refuses to put a date on them?

The table of contents has the date or more precisely the month of publication: https://danluu.com/

maybe contact him and suggest it.

He explained why recently on Twitter https://twitter.com/danluu/status/1521583578856902656

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.

The general problem is that threads are the worst concurrency model ever...

https://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-...

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

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/).

My favorite simple concurrent data structure is 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).

I suppose &/&mut is also a safeguard against event-loop and reentrancy bugs (like 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). File saving is also difficult (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/ is doing now.

This triple buffer is a new one on me, super clever thanks for sharing this.

& versus &mut (and the associated borrow checker rules) also stop certain types of bugs in non-concurrent code. For example, if you try to get a reference to an element in a vector, then try to clear the vector, the compiler will not allow it since you need a mutable reference to call the `clear` method, which can't be taken while a reference to an element exists (unless the reference isn't used again after the clear, in which case the compiler will recognize the lifetimes of the references don't overlap). In a GC language, the referenced object could still be kept around without needing to remain in the vector, but in a language like C/C++, you'd end up with a dangling pointer: https://play.rust-lang.org/?version=stable&mode=debug&editio...

(edited to replace poorly formatted inline code with link to playground)

Naive question, why is the triple buffer called like that?

So I literally just learned about this, and it's because it is 3 buffers. I found this website to be a good high level overview: https://wiki.c2.com/?TripleBuffer

If that's not short enough the tl;dr is: "with Triple Buffering, there will always be a buffer to write to while a transition is in progress between the other two." The other two buffer's being producer, and consumer buffers.

Hah, I was thinking about how to share state from an background collector thread to the frontend thread and TripleBuffer is exactly the data structure I needed just now. Thanks!

(My C++-infested instinct was to just go "naw, just slap a mutex on the data, it'll be fiiiinee", but I already knew that Rust Probably Has A Better Way For That).

A triple buffer (which isn't even Rust-specific IMO) is a good choice if all you want is polling the latest data at any given time, and you want to avoid mutexes altogether. If you want each piece of data to be delivered exactly once, you can use a queue (bounded or "unlimited" though the latter doesn't supply backpressure which I hear causes problems). SPSC lock-free bounded queues are dead simple to write, and can be better-tuned for higher throughput even with contention. For example, https://github.com/rigtorp/SPSCQueue is C++, claims to be highly optimized, and I haven't had issues working with it (aside from forgetting to peek and pop separately the first time I used it). However it's not a misuse-proof API since it doesn't use the "handles" idea I talked about, so you can push/read/pop from the wrong thread. If you want the reader to poll/WaitForMultipleObjects until the queue has items, that has to be done separately from the SPSC or triple buffer.

And mutexes make a lot of things easier... and introduces "oops wrong mutex!" (Rust solves it) and deadlock (Rust doesn't solve it).

Reply on news.ycombinator.com