Updated 8/26: Duncan’s question is actually correct and compare_exchange should have the semantics he asks for. However, the answer to ‘is it implementable’ is I think still Yes.
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.
template<typename _T>
bool atomic_bool_compare_and_swap(_T *value, _T& expected, _T new_value)
{
_T old_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.
[Update: …off-point stuff omitted…]
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):
template<typename _T>
bool atomic_compare_exchange(_T *value, _T& expected, _T new_value)
{
_T old_value;
_T old_expected = expected;
// 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 == old_expected;
expected = old_value;
return result;
}
Now that there’s no use of “expected” after the CAS 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. [Update: Thanks to Duncan in particular for pointing out my original answer did have a bug in my thinking.]
Sutter’s Mill 