12 ms·
Building a lock free continuous ring buffer in Rust
- kazinator 7y agoI 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.
- deleted 7y ago[deleted]
- kmill 7y agoI 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.
- deleted 7y ago[deleted]
- banachtarski 7y agoAlso important, not using a power of two sized ring is leaving lots of optimization on the table.
- monocasa 7y agoEh, 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.
- opencl 7y agoThere are two implementations described in this blog post and one of them is specifically designed to run on microcontrollers.
- banachtarski 7y agoCPUs 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.
- CUViper 7y agoYou 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 https://crates.io/crates/slice-deque
- pslam 7y agoThis 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.
- BeeOnRope 7y agoI'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.
- gpderetta 7y agoI have also seen this trick called the magic ring buffer.
- dragontamer 7y agoLooking 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 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 7y agoThe 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.
- 0xffff2 7y 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_city 7y 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.
- 0xffff2 7y agoYeah, 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.
- lalaland1125 7y agoWell, then your mind should be blown as the lock free queue provided in this article works without either locks or garbage collection. The trick here is that this queue has a fixed capacity so it can allocate everything upfront. You are right that infinite capacity queues can be a bit tricky to implement without violating your conditions. (In many cases you don't actually need an infinite capacity queue though ...)
- amelius 7y agoI'm guessing this still uses locks, but at the CPU/cache level instead of inside the algorithm.
- taneq 7y agoI'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 7y agoWhat is considered the bible on lock free programming?
- queensnake 7y agoI don't think there is one, yet. 'Multiprocessor Programming': https://www.amazon.com/Art-Multiprocessor-Programming-Revised-Reprint/dp/0123973376/ https://www.amazon.com/Art-Multiprocessor-Programming-Revise... has some algorithms, though.
- gpderetta 7y agoThe Art of Multiprocessor Programming. by Maurice Herlihy and Nir Shavit is an excellent start.
- ohazi 7y agoAlthough 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 7y agoCan you give the 20 lines of example code? Would really love to see some modern atomics code.
- ohazi 7y agoOkay, not quite 20 lines, but something like this: https://gist.github.com/ohazi/40746a16c7fea4593bd0b664638d7017 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 7y agoReminds me of the LMAX architecture. Slides of a talk I gave about LMAX https://www.slideshare.net/Stephan.Schmidt/lmax-architecture-jax-conference https://www.slideshare.net/Stephan.Schmidt/lmax-architecture...