Quick answer: Yes.
I see there was also a thread about this on StackOverflow, so I’ll echo this Q&A publicly for others’ benefit and hopefully to dispel confusion.
Duncan Forster asked:
I’m quite alarmed the C++ committee chose such a bad interface for std::atomic compare_exchange, i.e.:
bool compare_exchange_???(T& expected, T desired, …);
I notice you have mentioned (here reader-qa-how-to-write-a-cas-loop-using-stdatomics) that the committee had doubts whether it was a good idea.
Your quote below:
- Usage note: In the code at top we save an explicit reload from ‘a’ in the loop because compare_exchange helpfully (or “helpfully” – this took me a while to discover and remember) stores the actual value in the ‘expected’ value slot on failure. This actually makes loops simpler, though some of us are still have different feelings on different days about whether this subtlety was a good idea… anyway, it’s in the standard.
The reason I think it’s not only bad but also dangerous is that we now have a race condition baked into the standard. Race condition you say? All hardware CAS implementations that I know of only return 1 value (the old value). Yet the C++ version has 2 returns (success/failure as a boolean return and the old value by reference). So how can an atomic class which is suppose to implement atomic methods do this? Answer is it can’t, the boolean result is calculated after the atomic exchange has occurred. That leaves us with a method which is only partially atomic and with the bonus of a built-in race condition!
Perhaps I haven’t convinced you, so here’s some code to help. I have simulated the hardware CAS with simple C++ code to help demonstrate the problem. The crux of the problem is this statement: while(!atomic_bool_compare_and_swap(&head, new_node->next, new_node))
By creating a 1-line while loop and passing new_node->next as the expected value, if someone is also consuming data the new_node will temporarily be visible by 2 threads. The other thread may process and delete the node before atomic_bool_compare_and_swap has calculated success/failure. This would result in a spurious failure and the new_node actually being pushed twice onto the queue. As you can image this should lead to double delete and possibly the process aborting.
bool atomic_bool_compare_and_swap(_T *value, _T& expected, _T new_value)
// Here be atomic
old_value = *value;
if(old_value == expected)
*value = new_value;
// Here be race conditions
return (old_value == expected);
[... more code that exercises this function ...]
I don’t believe there is an implementability bug in the standard. Rather, your code is incorrect.
In the above code, presumably only *value is intended to be atomic (and presumably it assumes *value is of a type with a size and alignment that will naturally be written to atomically by the hardware or this code will see torn reads).
General technique: A useful “quick and dirty” analysis of any lock-free code is simply to look at all uses of *value (the atomic thing) as a sanity check. Each use (read, write, or read-modify-write) of the variable is itself atomics, but if there is more than one use you have to view it as a timing window and “mind the gap.”
Based on that quick look here, it seems the comments in the code are backwards:
- The part labeled “atomic” is not atomic – it accesses *value twice, leaving a timing window where you can lose updates.
- The part labeled “race conditions” is fine (or would be if the block before it really were atomic) – it is only accessing local variables.
Let’s say you have a CAS that returns only the old value, but doesn’t set “expected,” as you describe below. Then you should just be able to implement the standard one in terms of that – quick sketch (untested code):
bool atomic_compare_exchange(_T *value, _T& expected, _T new_value)
// If all you have is a CAS that returns the old value, use that:
old_value = CAS(value, expected, new_value);
bool result = old_value == expected;
expected = old_value;
Notice that there’s only one use of “value” and so no timing window.
If I’m misunderstanding the question, or have a bug in my thinking, please let me know in the comments.