4 ms·

I 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-

I 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 ago
Most 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 ago
  The 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 ago
    It 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 ago
      You 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 ago
        Yeah, 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 ago
  Thanks 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".
- alfalfasprout 10y ago
  Eh, the portability is actually getting a lot better nowadays. Most consumer and server processors being released in the last few years support double-world compare and swap. Atomic increment, load, store, etc. are also pretty widespread now. The key is like someone said above that you cannot make your code ambiguous. In C++ especially, the atomic primitives can compile to different instructions depending on how you use them so it's important to be very explicit. One thing that can be a pain is memory fences. The guarantees can be different on different CPUs so you can run into weird bugs. In my case, generally I compile to target particular CPUs on servers we own so it's not a big deal. But I can imagine for consumer software this can be a huge pain.
  - mikeash 10y ago
    I haven't seen too much recent stuff. I made this fix probably around 2004, and the code was at least a couple of years old at that point. We initially targeted PPC Mac, then it eventually expanded to x86 Mac and ARM iOS. All fairly similar when it comes to simple stuff like this, the barriers are straightforward when needed, and no need for DCAS or similar fanciness. (Indeed, no need for any CAS at all.)
nhaehnle 10y ago
The 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.

mikeash 10y ago

Most 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 ago
The 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 ago
  It 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 ago
    You 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 ago
      Yeah, 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 ago
Thanks 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".
alfalfasprout 10y ago
Eh, the portability is actually getting a lot better nowadays. Most consumer and server processors being released in the last few years support double-world compare and swap. Atomic increment, load, store, etc. are also pretty widespread now. The key is like someone said above that you cannot make your code ambiguous. In C++ especially, the atomic primitives can compile to different instructions depending on how you use them so it's important to be very explicit. One thing that can be a pain is memory fences. The guarantees can be different on different CPUs so you can run into weird bugs. In my case, generally I compile to target particular CPUs on servers we own so it's not a big deal. But I can imagine for consumer software this can be a huge pain.
- mikeash 10y ago
  I haven't seen too much recent stuff. I made this fix probably around 2004, and the code was at least a couple of years old at that point. We initially targeted PPC Mac, then it eventually expanded to x86 Mac and ARM iOS. All fairly similar when it comes to simple stuff like this, the barriers are straightforward when needed, and no need for DCAS or similar fanciness. (Indeed, no need for any CAS at all.)

nhaehnle 10y ago

The 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.