| ||||
 Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by nosenseetal
this is all cool and interesting, but I wish people would pay attention a bit to the boring stuff also, like serialization(preferably to make class serializable automatically in a sense that it can be serialized automatically if all its members can be serialized automatically… and if you have serialization for all built in ntypes then you have default serialization for any type :D ), for each for enums, to_string for enums… atomics are for small perchentage of the people, other just need to know here be danger except in simple cases like counter, bool flag… Read More »Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Norbert Lange
I believe the issue is the while loop: First its been noted that 2 threads could try to add the “new_node”, so I expect this to be an existing node and a reachable next pointer, The problem then is that you should never update the existing pointer unless the cmpexchange suceeded. Instead you would need something like this: MyPointer temp = new_node->next; while(!atomic_bool_compare_and_swap(&head, temp, new_node)) ; new_node->next = temp; (might use the compare_exchange_*_strong variant instead of a loop). In short, the expected variable must not be reachable from anywhere except the calling thread. The rest about CAs and compare_echange is covered already, I will just add that the boolean return value is bloody necessary when you implement the compare_exchange with loadlinked/storelinked. Look at a implementation with only the old value returned: template<typename _T> _T atomic_compare_exchange(_T *value, _T expected, _T new_value) { _T old_value = loadlnked(value); if (old_value == expected && storelinked(value, new_value)) return new_value; else { return atomic_load(value); } } Lets assume _T=int and the value in question is 5, and wants to change it to 42. Thread A: The caller of atomic_compare_exchange gets the expected value as return value, and thus would assume he changed the value, when in thruth the value got set from somewhere else. This might not be a problem for some uses, but for example reference-counting would mean the counter got incremented once instead of twice. So a usefull atomic_compare_exchange needs an indication of the operation failed, the write-back of expected is the only thing that could have been left out. Read More »Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Ben Hutchings
Herb, I think Duncan’s ‘Here be atomic’ comment means that the following block is pseudo-code for the hardware CAS instruction. And I think he’s concerned that the use of the the ‘expected’ variable is not atomic. (Actually, it could be on some architectures.) But you’re right that that isn’t normally required. Norbert, your code is backwards. You have to set the ‘next’ pointer of the new node before swapping the list head. So you would do something like: MyPointer temp = head; do new_node->next = temp; while(!atomic_compare_exchange(&head, temp, new_node));Read More » Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Duncan Forster
I think you have misunderstood my example. The example function atomic_bool_compare_and_swap is not real code but used to illustrate how CAS works in hardware. So the block with comment ‘Here be atomic’ above for this example should be considered atomic. This serves the discussion well, except I made a mistake. In fact CMPXCHG does return success/failure in the ZF flag (on x86, thanks Anthony for correcting me). I overlooked this because every time I have used CMPXCHG (or seen it used) the result has always been calculated by another compare. This seems innocuous but is racy. I’m not talking about an issue in theory, this has caused serious production issues. So to recap the C++ interface (it turns) out is implementable with CMPXCHG (on x86) and in some cases is rather nice. Wait a second the interface is correct, CAS is correct, this doesn’t compute in regards to my real-world issue. I have a test case, I can prove this doesn’t work. Ah, the penny drops, this is actually a bug in the implementation (in my case GCC 4.8). Take this simple example: #include This is completely correct C++ and should work always in any situation (with the assumption nodes are unique and never re-used). I like to think of this example as the Push thread creating a private object. The compare_exchange_weak operation is an attempt by the Push thread to relinquish ownership and pass it to another thread. If the operation succeeds the object is no longer owned by the Push thread and it shouldn’t touch the object ever (otherwise you have a race and all bets are off). If the operation fails As I have discussed with Anthony Williams and also mentioned on SO, no current compiler implements this correctly. The only know correct implementation is the Just::Thread library. I won’t go thru the assembly for all the compilers but I will mention VC++: inline int _Compare_exchange_seq_cst_4(volatile _Uint4_t *_Tgt, _Uint4_t *_Exp, _Uint4_t _Value) This is not correct, it has a race condition which means it’s reading a value it shouldn’t after the CAS. Since it’s a race it may calculate the wrong return code. If that happens it will also invent a write when in fact the CAS succeeded. This is very bad when you consider object ownership (from above). Read More »Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Anthony Williams
Duncan is unfortunately correct: there are bugs in at least gcc 4.8, clang 3.4 and Visual Studio 2013, all of which do an unconditional store to the “expected” parameter, even on successful exchanges, which can cause a race. The bugs have now been reported: GCC: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60272 Clang: http://llvm.org/bugs/show_bug.cgi?id=18899 Read More » | ||||
| | ||||
| ||||
Thursday, February 20, 2014
FeedaMail: Comments for Sutter’s Mill
Subscribe to:
Comments (Atom)