TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Building a lock free continuous ring buffer in Rust

200 点作者 Argorak将近 6 年前

9 条评论

dragontamer将近 6 年前
Looking at this blog-post more carefully... I&#x27;m not convinced that this ring buffer is actually correct unfortunately.<p>&gt; buffer.write.store(buffer.write.load() + write_len)<p>This is... an atomic load, followed by an add, followed atomic store.<p>A TRUE lock-free queue would be buffer.write.AtomicAdd(write_len), (which is a singular, atomic add).<p>There are many other issues here, but this is the most egregious issue I was able to find. The whole thing doesn&#x27;t work, its completely non-safe and incorrect from a concurrency point of view. Once this particular race condition is solved, there&#x27;s at least 3 or 4 others that I was able to find that also need to be solved.<p>EDIT: Here&#x27;s my counter-example<p><pre><code> 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 &quot;added&quot; 10 bytes each </code></pre> 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&#x27;re using atomics doesn&#x27;t mean that you&#x27;ve created an atomic transaction.<p>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.<p>---------<p>For a talk that actually gets these details right... I have made a recent submission: <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=20096907" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=20096907</a> . 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&#x27;s not messing around either: its a dense talk on a difficult subject.<p>Yeah, its not easy. But this is NOT an easy subject by any stretch of the imagination.
评论 #20098405 未加载
评论 #20098519 未加载
评论 #20098446 未加载
评论 #20101325 未加载
ohazi将近 6 年前
Although dragontamer&#x27;s complaints are mostly correct, I think he&#x27;s being a little uncharitable and is largely missing the point.<p>Yes, writing lock-free code that&#x27;s generic, that supports many-to-many reads&#x2F;writes, and that&#x27;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.<p>Are there issues with this one? Maybe. As dragontamer stated multiple times, this stuff is pretty hard to reason about.<p>HOWEVER, this ring buffer was designed to run on embedded systems. As usual, the constraints are often a little bit different when you&#x27;re writing software for a microcontroller.<p>As an example, let&#x27;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&#x27;t know, sending an endmill through the wall.<p>You can absolutely make this work, and you can even formally verify that you&#x27;ll always meet timing, but you&#x27;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&#x27;t even think about resetting the queue from either thread, and... (etc).<p>But if you&#x27;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.<p>Would it automatically run correctly and at full performance on a Xeon running Linux? Fuck no. But that&#x27;s not the point.<p>The desirable quality of lock-free queues for embedded systems is correctness, not performance.
评论 #20102355 未加载
0xffff2将近 6 年前
&gt;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. <i>If any of those words look scary to you, don&#x27;t fret, we&#x27;ll explain everything from the basics.</i><p>This is not the message I want to see introducing such a complex topic. Writing correct lock-free code is <i>incredibly</i> hard, and you&#x27;re <i>not</i> going to get it right or even understand it from a single post. I&#x27;ve done a bit of reading on this subject, and I&#x27;m not even sure that it&#x27;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.
评论 #20098499 未加载
评论 #20099240 未加载
评论 #20102181 未加载
评论 #20098486 未加载
评论 #20098541 未加载
kazinator将近 6 年前
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 &quot;wrap to the beginning&quot;. It&#x27;s so obvious, it must have been implemented numerous times by others before me.<p>If I were to implement the same thing again, I would just split the messages and use scattered writes (<i>struct iovec</i>) 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.<p>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&#x27;s possible to support both wrapped messages and the &quot;tail space not used&quot; indicator.
评论 #20098701 未加载
评论 #20098706 未加载
评论 #20098114 未加载
CUViper将近 6 年前
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&#x2F;end positions.<p><a href="https:&#x2F;&#x2F;crates.io&#x2F;crates&#x2F;slice-deque" rel="nofollow">https:&#x2F;&#x2F;crates.io&#x2F;crates&#x2F;slice-deque</a>
评论 #20098235 未加载
评论 #20102309 未加载
banachtarski将近 6 年前
Also important, not using a power of two sized ring is leaving lots of optimization on the table.
评论 #20098091 未加载
_Codemonkeyism将近 6 年前
Reminds me of the LMAX architecture.<p>Slides of a talk I gave about LMAX<p><a href="https:&#x2F;&#x2F;www.slideshare.net&#x2F;Stephan.Schmidt&#x2F;lmax-architecture-jax-conference" rel="nofollow">https:&#x2F;&#x2F;www.slideshare.net&#x2F;Stephan.Schmidt&#x2F;lmax-architecture...</a>
person_of_color将近 6 年前
What is considered the bible on lock free programming?
评论 #20101570 未加载
评论 #20103976 未加载
amelius将近 6 年前
I&#x27;m guessing this still uses locks, but at the CPU&#x2F;cache level instead of inside the algorithm.
评论 #20101163 未加载