5 ms·

Your bug doesn't seem to be related to the 'min' macro, but to the fact that your lock-free algorithm is not actually lock-free: if one thread can update an 'av

Your bug doesn't seem to be related to the 'min' macro, but to the fact that your lock-free algorithm is not actually lock-free: if one thread can update an 'availableData' variable while another thread can read it, make a choice based on it, and then act on that choice, then that's not lock-free; that requires a lock to keep the read, decision, and action "atomic". I'm skeptical that using some other 'min' implementation is a real fix to the root of your problem, but without knowing more, I can only speculate.

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

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