FeedaMail: Comments for Sutter’s Mill

	Comments for Sutter's Mill
	(Sponsor this newsletter) Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by nosenseetal He was free to raise his concerns during development of C11 and C++11. so I suggest skipping his rants. Read More »
	(Sponsor this newsletter)
	Delievered to you by Feedamail. Unsubscribe

FeedaMail: Comments for Sutter’s Mill

	Comments for Sutter's Mill
	(Sponsor this newsletter) Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Jan Ringoš You might also want to check the thread on GCC mailing list where Linus is raising hell about atomics wording in C11 (and all the things around). Read More »
	(Sponsor this newsletter)
	Delievered to you by Feedamail. Unsubscribe

FeedaMail: Comments for Sutter’s Mill

	Comments for Sutter's Mill
	(Sponsor this newsletter) Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by bames Herb, Has a defect report been filed on this (or do you know of one in the works)? The actual language of the spec does seem to imply much stronger guarantees than you are suggesting here. (In fact the actual language of the spec appears to guarantee behavior even stronger than Anthony’s library provides.) Read More »
	(Sponsor this newsletter)
	Delievered to you by Feedamail. Unsubscribe

FeedaMail: Comments for Sutter’s Mill

	Comments for Sutter's Mill
	(Sponsor this newsletter) Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by nosenseetal @Anthony Williams is it a implementation or ISO bug? Read More » Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by nosenseeta; btw my apology, I thought it was just an another example of somebody not understanding some brainf**k atomic code, but it turns out to be about a serious bug. :D But since Herb said it is not I was like meh, boring… Read More » Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Anthony Williams @nosenseetal It’s an implementation bug Read More » Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Matthew Elvey Price Or rather… you guarantee it will NOT unexpectedly modified/invalidated. Whoops. Read More » Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Matthew Elvey Price My reading of the standard is: part of 29.6.5/2: In the following operation definitions: — an A refers to one of the atomic types. — a C refers to its corresponding non-atomic type. (…) An example function definition from just before 29.6.5/20: bool atomic_compare_exchange_weak(A* object,C* expected,C desired) noexcept Expected is type C so is NOT atomic. If we assume what I’ve said above, the specific issue in your code is that by passing in a non-atomic variable (expected), you guarantee it will unexpectedly modified or invalidated during that call. Then you break that guarantee by deleting or modifying it in another thread. Ben’s code appears to account for this correctly. The compiler bugs listed only cover storing to expected in the success case where it would store the same value anyway. Read More » Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Noob Learner In fact, I think Ducan is stretching the guarantee of atomicity to its function parameter which I don’t think was intended. Read More » Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Noob Learner After reading both the SO as well as the above post. My initial reaction was that indeed Duncan and Anthony are both correct. However on second thoughts, I think Herb is also right. In this case for compare_exchange, I would rather say the atomicity was for the head node not for the node-next. Think of it this way suppose we have the following code which store the new value into the atomic_var and put the original value in the old_value. template void SuperStore(std::atomic& atmoic_var, const Ty1* new_value, Ty1* old_value); Obviously from the function signature, we safely say the the store to the atomic_var would be atomically safe, but to assume the write to old_value is safe would be a big no no. If it was atomic, old_value should have been std::atomic* old_value. I think to make the whole issue of compare_exchange better, ‘expected’ should have been an atomic variable. Or maybe the standard committee was referring to the atomicity of the calling object of compare_exchange_weak, rather than the atomicity of the compare_exchange_weak function parameters. It is just a guess and maybe I am wrong. Read More » Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by bames I don’t think the issue is that implementations are failing to make the assignment to expected atomic with the compare/exchange. The problem is that the spec guarantees that, if the exchange occurs, then expected is _not_ written to. Thus if the exchange occurs then another thread which was waiting on the exchange can go ahead and access expected, knowing that the compare_exchange will not write to it and there will therefore be no race. But since actual implementations write to expected unconditionally real implementations introduce a race. Read More » Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Noob Learner My opinion on the issue is that the problem is not about race/unconditional write but more of sharing the ‘expected’ variable across thread. I would say there was never a guarantee in atomic write to ‘expected’. Thus I think trying to assume atomicity for ‘expected’ isn’t an appropriate thing. If there was never a guarantee to atomic write for ‘expected’ then we should not attempt to pass a variable to ‘expected’ which spans multiple thread. Think of it as a simple function: void foo(int* arg); In the above case, passing a variable to the function ‘arg’ which is shared across multiple thread is just asking for trouble. Whether function foo write arg unconditionally or does anything to it is beside the point. It doesn’t change the problem that passing in a variable used by multiple thread into arg is creating a problem of attempting atomicity/synchronisation on a variable/type not meant to do that. Read More » Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Anthony Williams The write to expected does not need to be atomic. It should only be written to on failure, so if the compare-exchange succeeds, then other threads can touch the value passed as the “expected” parameter, because the compare-exchange will not do so (in a correct implementation). This is important when doing things like lock-free data structures, where the “expected” value may often be part of a node being added to the data structure by the compare-exchange. If the compare-exchange fails then the node is still not part of the data structure, so modifying expected is not a problem. If the compare-exchange succeeds then the node is now part of the data structure and may be accessed by other threads. Read More » Comment on Reader Q&A: Is std::atomic_compare_exchange_* implementable? by Herb Sutter BTW, I’ve started an email thread with the designers of the feature and Duncan and Anthony. I understood that the design of having compare_exchange_* take the “expected” value by reference, and update “expected” on failure to expose the old value, was only intended for convenience to simplify the calling loops which would otherwise always have to write an extra “reload” line of code. Now that “expected” is an lvalue, folks like Duncan are trying to use the success of compare_exchange_* to hand off ownership **of “expected” itself** to another thread. For that to be safe, if the compare_exchange_* succeeds then the thread that performed it must no longer read or write from “expected” else his technique contains a race. I don’t think this usage was ever intended to be supported, but I could be wrong (waiting to hear back from the feature’s designer), even if it wasn’t we may want to extend and add support for it now, and in any event I think we need to improve the standardese wording which is apparently unclear today. Read More »
	(Sponsor this newsletter)
	Delievered to you by Feedamail. Unsubscribe

FeedaMail: Comments for Sutter’s Mill

	Comments for Sutter's Mill
	(Sponsor this newsletter) 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: while(!atomic_bool_compare_and_swap(&head, new_node->next, new_node)). 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: 1) _T old_value = loadlnked(value); 2) another Thread interrupts and changes the value (or atleast causes the linked sequence to fail) 3) storelinked fails 4) another thread interrupts and changes the value to 42 5) atomic_load(value) returns 5 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 struct Node { Node* next; }; void Push(std::atomic head, Node* node) { node->next = head.load(); while(!head.compare_exchange_weak(node->next, node)) ; } 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 the Push thread still owns the object (still private), thus it may be modified race free. 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) { /* compare and exchange values atomically with sequentially consistent memory order */ int _Res; _Uint4_t _Prev = _InterlockedCompareExchange((volatile long *)_Tgt, _Value, *_Exp); if (_Prev == *_Exp) !!!!!!!!!!!!!!!!!!!!!!! _Res = 1; else { /* copy old value */ _Res = 0; *_Exp = _Prev; } return (_Res); } 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: MSVC: https://connect.microsoft.com/VisualStudio/feedback/details/819819/std-atomic-compare-exchange-weak-has-spurious-write-which-can-cause-race-conditions GCC: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60272 Clang: http://llvm.org/bugs/show_bug.cgi?id=18899 Read More »
	(Sponsor this newsletter)
	Delievered to you by Feedamail. Unsubscribe

FeedaMail: Comments for Sutter’s Mill

	Comments for Sutter's Mill
	(Sponsor this newsletter) Comment on Reader Q&A: How to write a CAS loop using std::atomics by Reader Q&A: Is std::atomic_compare_exchange_* implementable? | Sutter's Mill […] 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 […] Read More »
	(Sponsor this newsletter)
	Delievered to you by Feedamail. Unsubscribe