Lock-Free Bugs
research.swtch.com
research.swtch.com
As a result, the mutex implementation might spray futex-wake calls into arbitrary addresses not owned by the implementation. This means that other libraries in the same process can't rely on accurate wakeups, even if it would otherwise be algorithmically correct to do so (unless it has some way of guaranteeing that its synchronization locations never share an address with other libraries).
If you've ever wondered why pthreads-style condition variables allow spurious wakeups, this is one reasonable situation in which they can occur.
“By June 1949, people had begun to realize that it was
not so easy to get a program right as had at one time
appeared. … It was on one of my journeys between the
EDSAC room and the punching equipment that the
realization came over me with full force that a good
part of the remainder of my life was going to be spent
in finding errors in my own programs.” - Wilkes
My favorite lock-free bug involved a concurrent ring buffer. At one point the code had to figure out how much data to read, which was either the size of the buffer passed in, or the amount of data available in the ring buffer, whichever was smaller. So the code did something like:
toRead = min(requestSize, availableData)
#define min(a, b) ((a) < (b) ? (a) : (b))
I deleted the custom min macro and used the (properly implemented) system-provided one, and all was well.
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.
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.
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).
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)
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.
I do actually know what I'm doing here....
These days, with atomics showing up in the C and C++ standard libraries, there are better ways to do it altogether.
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".
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.
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.)