Hacker News Reader

Comment by pcwalton | Hacker News Reader

Lock-free programming is really tough. There are really only a few patterns that work (e.g. Treiber stack). Trying to invent a new lock-free algorithm, as this vulnerable code demonstrates, almost always ends in tears.

View on HN

IMO lock-free MP or MC algorithms are harder to get right than SPSC structures (atomics for shared memory, queues for messaging, triple buffers for tear-free shared memory). But even SPSC algorithms can be tricky; I've found the same (theoretical) ordering error in three separate Rust implementations of triple buffering (one of them mine), written by people who've already learned the ordering rules (which I caught with Loom). And initially learning to reason about memory ordering is a major upfront challenge too.

I'd be interested in knowing the details of the error!

https://github.com/HadrienG2/triple-buffer/issues/14

I particularly like lock-free (wait-free?) SPSC queues because they're (relatively) easy to get right, and are extremely useful for buffering in embedded systems. I end up with something like this on almost every project:

One side of the queue is a peripheral like a serial port that needs to be fed/drained like clockwork to avoid losing data or glitching (e.g. via interrupts or DMA), and the other side is usually software running on the main thread, that wants to be able to work at its own pace and also go to sleep sometimes.

An SPSC queue fits this use-case nicely. James Munns has a fancy one written in Rust [1], and I have a ~100 line C template [2].

[1] https://github.com/jamesmunns/bbqueue

[2] https://gist.github.com/ohazi/40746a16c7fea4593bd0b664638d70...

There's no new invention in here. Just an (intentional) misuse of "volatile".

There are tons of lock-free algorithms, both node based and array backed up. Lock-free is notoriously easier on garbage collector set-ups, of course.

This isn't a new lock-free algorithm. Single-reader, single-write FIFOs are one of the oldest approaches around.

They have to be tweaked when execution isn't guaranteed (by using memory barriers). TFA is about an exploit based on code that hasn't added the required memory barriers.

Reply on news.ycombinator.com