3 ms·
The algorithm is sound given a proper min() implementation. The reader just needs to read at most however much data is available at the moment or however much d
by mikeash 10y ago
The algorithm is sound given a proper min() implementation. The reader just needs to read at most however much data is available at the moment or however much data the passed-in buffer can hold. If the available data increases during this operation, it's no problem, because the reader is allowed to read less than all of the data available.
For some concrete numbers, if the ring holds 4 bytes, the caller passes in a 6-byte buffer, and a concurrent writer adds 4 more bytes, it's OK if the reader only returns 4 bytes. It would also be OK if the reader sees the new data and returns 6 bytes. It is not OK if the reader returns 8 bytes, which the incorrect min macro could cause.
In this scenario, the incorrect min macro could return 4, 6, or 8, despite the fact that one of the parameters was a constant 6 and the result should never exceed 6. The correct min macro always returns 4 or 6.
- jjnoakes 10y agoI see. So you are relying on single-reads of your shared variables. They must be suitably defined to be atomic on your architecture (so no word-tearing, out-of-order visibility), etc. I would think that if you had all the proper barriers in place to do the reads and writes atomically, though, that you would never have been able to use the min() macro in the first place. You would have had to do your barrier reads into local variables first, and then the min() macro on those local variables would have produced the right result. Unless I'm missing something. Like I said, it all depends on your implementation, but in general, this sure sounds like the min() macro wasn't at fault. Perhaps your specific scenario is much more constrained (single architecture, no barriers required, non-portable, etc).
- mikeash 10y agoMost lock-free code I've seen is pretty architecture dependent and often non-portable, and this was no exception. I should also note that it was only intended to be correct for a single reader and a single writer. Given those constraints, it's not all that difficult. The amount of data in the ring buffer gets stored in a properly aligned word-sized field which the architecture guarantees will have atomic reads and writes. You just need a write barrier after writing new data and before updating the amount of data available, and a read barrier after reading the amount of data available and before actually reading the data. The read code would look something like: amountToRead = min(outBufferSize, availableData) barrier() memcpy(outBuffer, ringBuffer, amountToRead) (Ignoring the tricks you have to play to deal with wraparound, just to keep things simple.) This works fine as long as min() actually evaluates to the smaller of the two numbers passed in. The moment it evaluates to a number larger than outBufferSize, you have a buffer overrun.
- nhaehnle 10y agoThe code is still incorrect, because the compiler is free to speculate and transform the code in a way that leads to availableData being loaded twice (as in the macro). That probably doesn't happen in practice, but it is an allowed transform. You really do need to explicitly tell the compiler that it should load availableData only once (e.g. with a volatile load or an atomic load built-in).
- mikeash 10y agoIt was marked as volatile, so the compiler wouldn't be allowed to load it twice. I do actually know what I'm doing here....
- jjnoakes 10y agoYou probably know, but for others reading these threads: volatile is not the optimal way (and usually it isn't even a correct way, outside of very specific code) to synchronize variables across threads.
- mikeash 10y agoYeah, don't use what I've said as a guide for writing your own stuff. I'm pretty sure I did it right, but you need a lot more understanding of what's going on than what I've explained.... These days, with atomics showing up in the C and C++ standard libraries, there are better ways to do it altogether.
- jjnoakes 10y agoThanks for the details. If you are reading from a shared variable like that you most definitely need to be careful about using macros. I would be concerned if I wasn't using some sort of read_once routine or macro (like a sister comment also mentioned), since I have no idea what games a compiler or architecture is allowed to play without such an explicit restriction. And once I was using such a read_once to fetch that shared variable, I think it would be obvious that writing it in function argument position is a red flag to signal "be careful, if this is a macro".
- nhaehnle 10y agoThe original code may have had something like min(read_once(available), buffer_size), with a suitably and correctly defined atomic read_once function. In that case, it would be fair to blame a bad min macro on problems.