Building a lock free continuous ring buffer in Rust

https://ferrous-systems.com/blog/lock-free-ring-buffer/

by Argorak • 7 years ago

200 109 7 years ago

kazinator• 7 years ago

I implemented such a buffer in 2006. It was used for fast message passing from user space to the kernel. When a message was too large to fit at the end of the circular buffer, a zero-length message was placed into the remaining space; that indicated "wrap to the beginning". It's so obvious, it must have been implemented numerous times by others before me.

If I were to implement the same thing again, I would just split the messages and use scattered writes (struct iovec) to process them. I cannot remember exactly, but I think the only reason the messages were linear was just for the kernel thread to be able to write them out in a single call.

Oh wait, now I remember; I think the buffers were linear due to the production side: sprintf being used to produce some of the message payloads, and that requiring a linear buffer. But of course it's possible to support both wrapped messages and the "tail space not used" indicator.

kmill• 7 years ago

I was wondering about having a special message to indicate the end of the buffer while reading the article, so thanks for pre-emptively answering my question!

Another thing I was wondering about is using a simple buddy allocator with the ring buffer being just a list of pointers. There would be a second ring buffer to send memory back to the producer to be freed, and you would statically allocate enough memory so fragmentation doesn't affect the particular application---you know each message has a limited lifetime, for instance. (The allocator would not be shared between different ring buffers.)

Then again, I don't see any benefits to doing this.

banachtarski2• 7 years ago

Also important, not using a power of two sized ring is leaving lots of optimization on the table.

monocasa• 7 years ago

Eh, maybe/maybe not. This implementation requires a family big boy CPU with a really MMU; I'd be willing to bet that most of the extra latency of the divides are hidden in the memory access latencies.

banachtarski2• 7 years ago

CPUs are pipelined though so you can easily imagine many slots being operated on at once. Perhaps a better metric is the relative cost of the slot assignment against the the cost of the read/write operation. Not to mention the fact that elements may be in L1, in which case the penalty of additional cycles may actually be felt.

opencl• 7 years ago

There are two implementations described in this blog post and one of them is specifically designed to run on microcontrollers.

CUViper• 7 years ago

You can make wrapping writes look contiguous by mapping the same memory twice, one after the other. This is done in slice-deque such that the entire buffer can be viewed as a contiguous slice, regardless of the start/end positions.

https://crates.io/crates/slice-deque

pslam• 7 years ago

This trick may break ordering and cache aliasing rules on many architectures. If you're dipping into this kind of thing, it needs per-architecture whitelisting.

BeeOnRope5• 7 years ago

I'm not sure about the ordering part, but about "cache aliasing rules" - can you give some details? This situation can be trivially set up via mmap, so if that breaks it would seem to be a problem?

I understand that aliasing is an issue when it comes to hardware design, but the practical need to support systems that allow this to occur means that all major architectures I'm aware of support transparent V->P aliasing, either by having their caches physically indexed, effectively physically indexed like VIPT or some strategy where V is used to look up the way in L1 but misses due to aliasing will be resolved in the L2 (i.e., aliasing "works" but is slow), or some other similar strategy.

I would be curious what systems don't work this way.

Note that I'm talking only about data - systems definitely have all sorts of rules about modification of instruction-containing pages.

gpderetta9• 7 years ago

I have also seen this trick called the magic ring buffer.

dragontamer22• 7 years ago

Looking at this blog-post more carefully... I'm not convinced that this ring buffer is actually correct unfortunately.

buffer.write.store(buffer.write.load() + write_len)

This is... an atomic load, followed by an add, followed atomic store.

A TRUE lock-free queue would be buffer.write.AtomicAdd(write_len), (which is a singular, atomic add).

There are many other issues here, but this is the most egregious issue I was able to find. The whole thing doesn't work, its completely non-safe and incorrect from a concurrency point of view. Once this particular race condition is solved, there's at least 3 or 4 others that I was able to find that also need to be solved.

EDIT: Here's my counter-example

    write = 100 (at the start)
    write_len = 10 for both threads.

    |-----------------------------------|
    |   Thread 1      |   Thread 2      |
    |-----------------------------------|
    | write.load (100)| write.load (100)|
    | 100+write_len   |                 |
    | write.store(110)| 100+write_len   |
    |                 | write.store(110)|
    |-----------------------------------|

    write = 110 after the two threads "added" 10 bytes each

Two items of size 10 were written to the queue, but only +10 bytes happened to the queue. The implementation is completely busted and broken. Just because you're using atomics doesn't mean that you've created an atomic transaction.

It takes great effort and study to actually build atomic transactions out of atomic parts. I would argue that this thread should be a lesson in how easy it is to get multithreaded programming dead wrong.

---------

For a talk that actually gets these details right... I have made a recent submission: https://news.ycombinator.com/item?id=20096907 . Mr. Pikus breaks down how atomics and lock-free programming needs to be done. It takes him roughly 3.5 hours to describe a lock-free concurrent queue. He's not messing around either: its a dense talk on a difficult subject.

Yeah, its not easy. But this is NOT an easy subject by any stretch of the imagination.

ekimekim• 7 years ago

The article is discussing an exclusive-writer, exclusive-reader ring buffer. Interleaved writers is intentionally not considered.

A common strategy to reduce the amount of coordination that needs to happen between the two threads (writer, reader) is to associate each coordination variable (pointer) with a single thread that has exclusive write access to it.

dragontamer22• 7 years ago

reduce the amount of coordination

Interesting premise, but it doesn't hold up to scrutiny.

1. They have three shared variables.

2. Those three shared variables are being falsly shared in that data-structure.

    struct ContiguousAsyncBuffer {
      buf: *mut u8,
      len: usize,
      read: AtomicUsize,
      write: AtomicUsize,
      watermark: AtomicUsize,
    }

Look at that struct, all of the atomics are inside the same 64-byte cache line!! That's the worst sharing possibility imaginable!

3. Therefore: the dumb-and-simple "Mutex / Spinlock" would actually have less sharing (share only a ONE variable: the mutex), without any false-sharing of various atomic variables.

---------

I kid you not: a "lock/unlock" queue probably performs better than the atomic thing they did here (and the atomic-thing they're doing doesn't even work correctly).

BubRoss2• 7 years ago

If there is exclusive writing and exclusive reading, then it either isn't lock free or it isn't correct.

forrestthewoods3• 7 years ago

The article stipulates there is a single reader and a single writer. The actual API enforces this constraint.

https://docs.rs/spsc-bip-buffer/0.1.1/spsc_bip_buffer/fn.bip...

cesarb3• 7 years ago

That's only an issue if there are multiple producers. That code works fine when there's a single producer, since nothing else will modify the "write" value between the load and the store. Given that this is in Rust, it's easy to encapsulate this data structure in a way that makes the compiler enforce this invariant.

userbinator• 7 years ago

Just because you're using atomics doesn't mean that you've created an atomic transaction.

Raymond Chen of Microsoft has a much simpler example of that:

https://devblogs.microsoft.com/oldnewthing/20040915-00/?p=37...

Yeah, its not easy. But this is NOT an easy subject by any stretch of the imagination.

Having had to debug many difficult race conditions before, I can say that anything related to concurrency is extremely difficult to reason about, and needs to be done with a lot of careful thought.

0xffff25• 7 years ago

This is the story of how Andrea Lattuada (PhD student at ETH Zurich) and James Munns (from Ferrous Systems) designed and implemented (two versions!) of an high-perf lock-free ring-buffer for cross-thread communication. If any of those words look scary to you, don't fret, we'll explain everything from the basics.

This is not the message I want to see introducing such a complex topic. Writing correct lock-free code is incredibly hard, and you're not going to get it right or even understand it from a single post. I've done a bit of reading on this subject, and I'm not even sure that it's possible to write a correct lock-free queue (of which this is a variant) in a non-garbage collected language without some pretty substantial trade-offs regarding memory management.

holy_city2• 7 years ago

I'm not even sure that it's possible to write a correct lock-free queue (of which this is a variant) in a non-garbage collected language.

I'm guessing because of the "magical free that doesn't lock" assumption in several papers?

There are some ideas in the Rust community (mostly centered around audio), most of them use garbage collection schemes that prevent either the producer or consumer thread from locking. It's tricky and easy to break.

0xffff25• 7 years ago

Yeah, that's pretty much exactly it. Every "lock-free queue without garbage collection" I've seen is either broken, relying on hidden locks (most commonly in free), or implementing garbage collection while calling it something else.

dragontamer22• 7 years ago

Pikus does it. I made a post about it. https://news.ycombinator.com/item?id=20096907

The talk is 3.5 hours, about as long as you'd expect one to be for "writing a concurrent lockfree queue". Its an incredibly difficult topic, but I'm convinced that Pikus's implementation is actually correct.

Although, maybe there's a subtle bug somewhere. And Pikus is REALLLY stretching the definition of a queue to make his implementation work. (This queue may sometimes function like a stack, but that's okay because there's no way for the end programmer to figure it out without a global lock)

---------

EDIT: Oh, I guess you wouldn't consider it "truly lock free", because he has a global lock in the case of the rare situation of a full queue. He uses double-checked lock pattern for that case (and causes an expensive, but temporary, global lock on the data-structure) and basically says "This situation only happens once per hour, so its probably not bad".

So Pikus's implementation is "lock free mostly", but still falls back to a global spinlock in exceptionally rare corner cases.

0xffff25• 7 years ago

Oh, that's actually a different lock-free talk from Pikus than I expected. I haven't it watched yet. Thanks!

I probably wrote my original comment a little too quickly. Yes, it's possible to write useful mostly lock-free data structures, but it's hard enough that I consider anyone claiming to have done so in a way that beats the equivalent locked structure (as you pointed out above) to be making an extraordinary claim that requires extraordinary evidence and serious consideration of the difficulty involved.

adwn• 7 years ago

[...] I'm not even sure that it's possible to write a correct lock-free queue (of which this is a variant) in a non-garbage collected language without some pretty substantial trade-offs regarding memory management.

There's no dynamic memory allocation going on in this particular lock-free queue, so I don't see how your concern is relevant here?

0xffff25• 7 years ago

After reading the full article, they solve a vastly more restricted (although perhaps still useful) problem than the title implies. Their design assumes a single producer and single consumer and is trivially broken if that's not the case. I don't have time to write a convincing set of benchmarks to prove it, but I very much doubt that this is faster than a locking implementation of the same structure.

scott_s2• 7 years ago

This is not the message I want to see introducing such a complex topic.

I don't see the need for such gatekeeping. I think telling people over-and-over how "incredibly hard" something is will tend to discourage people from learning about that thing. I think that's bad.

zbentley• 7 years ago

Warning about complexity and gatekeeping are not the same thing.

First-year programmer says "I can't wrap my head around Python, I'll write my own language!"

A response of "You're an idiot, don't bother, people smarter than you have tried and failed" is gatekeeping, and shitty.

A response of "There is a lot about this area you do not understand, be aware that it is a lot harder than you seem to think it is" is cautionary, but not gatekeeping.

gpderetta9• 7 years ago

There are plenty of hard lock free algorithms, but an SPSC ring buffer is not exactly rocket science and it is a good introduction on the topic.

Why do you think that a GC is required for a queue? It is certainly very helpful to implement complex node-based intrusive concurrent data structures, but for queues, even node based and even MPMC, as long as each message is produced by one thread and consumed by another one (i.e. the typical use case), single ownership works just fine.

edit: I see you are talking about hidden locks in the allocator. That's fair, but even GC at some point might need to hit the kernel to increase the heap size.

amelius• 7 years ago

I'm guessing this still uses locks, but at the CPU/cache level instead of inside the algorithm.

taneq• 7 years ago

I've always thought "lock free" was a misnomer for this kind of thing because they use multi-stage atomic instructions which obviously require some kind of implied locking. I'd probably call them "non-blocking".

person_of_color• 7 years ago

What is considered the bible on lock free programming?

queensnake• 7 years ago

I don't think there is one, yet. 'Multiprocessor Programming': https://www.amazon.com/Art-Multiprocessor-Programming-Revise... has some algorithms, though.

gpderetta9• 7 years ago

The Art of Multiprocessor Programming. by Maurice Herlihy and Nir Shavit is an excellent start.

ohazi4• 7 years ago

Although dragontamer's complaints are mostly correct, I think he's being a little uncharitable and is largely missing the point.

Yes, writing lock-free code that's generic, that supports many-to-many reads/writes, and that's correct on all architectures is hilariously hard, and most people should not try to implement these from scratch at work. Other approaches can be more performant, and can have acceptable trade-offs for most use cases.

Are there issues with this one? Maybe. As dragontamer stated multiple times, this stuff is pretty hard to reason about.

HOWEVER, this ring buffer was designed to run on embedded systems. As usual, the constraints are often a little bit different when you're writing software for a microcontroller.

As an example, let's imagine you have periodic bursts of data coming in on a serial port at 2 Mbps, and your microcontroller is running at 32 MHz. Also, your serial port only has a 4 byte hardware buffer, and the cost of missing a byte is... I don't know, sending an endmill through the wall.

You can absolutely make this work, and you can even formally verify that you'll always meet timing, but you're going to have a really hard time doing this if you also have to analyze every other piece of code that will ever try to acquire that lock. A single-producer, single-consumer, lock-free queue with fixed message sizes can be implemented correctly in about 20 lines of C. It has a lot of annoying constraints, and you still have to use atomics correctly, and you still need a memory barrier, and don't even think about resetting the queue from either thread, and... (etc).

But if you're careful, a queue like this can make an otherwise impossible task relatively manageable. I can no longer count the number of times a construct like this has saved a project I was involved with.

Would it automatically run correctly and at full performance on a Xeon running Linux? Fuck no. But that's not the point.

The desirable quality of lock-free queues for embedded systems is correctness, not performance.

sansnomme• 7 years ago

Can you give the 20 lines of example code? Would really love to see some modern atomics code.

ohazi4• 7 years ago

Okay, not quite 20 lines, but something like this:

https://gist.github.com/ohazi/40746a16c7fea4593bd0b664638d70...

I've dressed it up to look like C11, but vendor specific macros from your microcontroller support library are more common. I think you can relax some of the memory ordering too, but I don't remember the details off-hand.

Also, sometimes you can have a modified version of queue_push / queue_pop where a DMA handles the memcpy and then you only have to update the pointers in the cleanup interrupt (along with configuring the next or next-next DMA if the queue isn't full / empty).

_Codemonkeyism• 7 years ago

Reminds me of the LMAX architecture.

Slides of a talk I gave about LMAX

https://www.slideshare.net/Stephan.Schmidt/lmax-architecture...

Building a lock free continuous ring buffer in Rust

Related Stories