2426. Issue about compare_exchange

Section: 32.5.8.2 [atomics.types.operations] Status: C++17 Submitter: Hans Boehm Opened: 2014-08-25 Last modified: 2017-07-30

Priority: 1

View other active issues in [atomics.types.operations].

View all other issues in [atomics.types.operations].

View all issues with C++17 status.

Discussion:

The standard is either ambiguous or misleading about the nature of accesses through the expected argument to the compare_exchange_* functions in 99 [atomics.types.operations.req]p21.

It is unclear whether the access to expected is itself atomic (intent clearly no) and exactly when the implementation is allowed to read or write it. These affect the correctness of reasonable code.

Herb Sutter, summarizing a complaint from Duncan Forster wrote:

Thanks Duncan,

I think we have a bug in the standardese wording and the implementations are legal, but let's check with the designers of the feature.

Let me try to summarize the issue as I understand it:

1. What I think was intended: Lawrence, I believe you championed having compare_exchange_* take the expected value by reference, and update expected on failure to expose the old value, but this was only for convenience to simplify the calling loops which would otherwise always have to write an extra "reload" line of code. Lawrence, did I summarize your intent correctly?

2. What I think Duncan is trying to do: However, it turns out that, now that expected is an lvalue, it has misled(?) Duncan into 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. Duncan, did I summarize your usage correctly? Is that the only use that is broken?

3. What the standard says: I can see why Duncan thinks the standard supports his use, but I don't think this was intended (I don't remember this being discussed but I may have been away for that part) and unless you tell me this was intended I think it's a defect in the standard. From 99 [atomics.types.operations.req]/21:

   -21- Effects: Atomically, compares the contents of the memory pointed to by object or by this for equality with that in expected, and if true, replaces the contents of the memory pointed to by object or by this with that in desired, and if false, updates the contents of the memory in expected with the contents of the memory pointed to by object or by this. […]

   I think we have a wording defect here in any case, because the "atomically" should not apply to the entire sentence — I'm pretty sure we never intended the atomicity to cover the write to expected.

   As a case in point, borrowing from Duncan's mail below, I think the following implementation is intended to be legal:

   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) //!!!!! Note the unconditional read from *_Exp here
       _Res = 1;
     else
     { /* copy old value */
       _Res = 0;
       *_Exp = _Prev;
     }
     return (_Res);
   }
   

   I think this implementation is intended to be valid — I think the only code that could be broken with the "!!!!!" read of *_Exp is Duncan's use of treating a.compare_exchange_*(expected, desired) == true as implying expected got handed off, because then another thread could validly be using *_Exp — but we never intended this use, right?

In a different thread Richard Smith wrote about the same problem:

The atomic_compare_exchange functions are described as follows:

"Atomically, compares the contents of the memory pointed to by object or by this for equality with that in expected, and if true, replaces the contents of the memory pointed to by object or by this with that in desired, and if false, updates the contents of the memory in expected with the contents of the memory pointed to by object or by this. Further, if the comparison is true, memory is affected according to the value of success, and if the comparison is false, memory is affected according to the value of failure."

I think this is less clear than it could be about the effects of these operations on *expected in the failure case:

1. We have "Atomically, compares […] and updates the contents of the memory in expected […]". The update to the memory in expected is clearly not atomic, and yet this wording parallels the success case, in which the memory update is atomic.

2. The wording suggests that memory (including *expected) is affected according to the value of failure. In particular, the failure order could be memory_order_seq_cst, which might lead someone to incorrectly think they'd published the value of *expected.

I think this can be clarified with no change in meaning by reordering the wording a little:

"Atomically, compares the contents of the memory pointed to by object or by this for equality with that in expected, and if true, replaces the contents of the memory pointed to by object or by this with that in desired, and if. If the comparison is true, memory is affected according to the value of success, and if the comparison is false, memory is affected according to the value of failure. Further, if the comparison is false, updatesreplaces the contents of the memory in expected with the contents ofvalue that was atomically read from the memory pointed to by object or by this. Further, if the comparison is true, memory is affected according to the value of success, and if the comparison is false, memory is affected according to the value of failure."

Jens Maurer add:

I believe this is an improvement.

I like to see the following additional improvements:

• "contents of the memory" is strange phrasing, which doesn't say how large the memory block is. Do we compare the values or the value representation of the lvalue *object (or *this)?

• 32.5.4 [atomics.order] defines memory order based on the "affected memory location". It would be better to say something like "If the comparison is true, the memory synchronization order for the affected memory location *object is […]"

There was also a discussion thread involving Herb Sutter, Hans Boehm, and Lawrence Crowl, resulting in proposed wording along the lines of:

-21- Effects: Atomically with respect to expected and the memory pointed to by object or by this, compares the contents of the memory pointed to by object or by this for equality with that in expected, and if and only if true, replaces the contents of the memory pointed to by object or by this with that in desired, and if and only if false, updates the contents of the memory in expected with the contents of the memory pointed to by object or by this.

At the end of paragraph 23, perhaps add

[Example: Because the expected value is updated only on failure, code releasing the memory containing the expected value on success will work. E.g. list head insertion will act atomically and not have a data race in the following code.

do {
  p->next = head; // make new list node point to the current head
} while(!head.compare_exchange_weak(p->next, p)); // try to insert

— end example]

Hans objected that this still gives the misimpression that the update to expected is atomic.

[2014-11 Urbana]

Proposed resolution was added after Redmond.

Recommendations from SG1:

1. Change wording to if trueif and only if true, and change if falseif and only if false.
2. If they want to add "respect to" clause, say "respect to object or this".
3. In example, load from head should be "head.load(memory_order_relaxed)", because people are going to use example as example of good code.

(wording edits not yet applied)

[2015-02 Cologne]

Handed over to SG1.

[2015-05 Lenexa, SG1 response]

We believed we were done with it, but it was kicked back to us, with the wording we suggested not yet applied. It may have been that our suggestions were unclear. Was that the concern?

[2016-02 Jacksonville]

Applied the other half of the "if and only if" response from SG1, and moved to Ready.

Proposed resolution:

1. Edit 99 [atomics.types.operations.req] p21 as indicated:

   -21- Effects: Retrieves the value in expected. It then aAtomically, compares the contents of the memory pointed to by object or by this for equality with that inpreviously retrieved from expected, and if true, replaces the contents of the memory pointed to by object or by this with that in desired, and if false, updates the contents of the memory in expected with the contents of the memory pointed to by object or by this. Further, if. If and only if the comparison is true, memory is affected according to the value of success, and if the comparison is false, memory is affected according to the value of failure. When only one memory_order argument is supplied, the value of success is order, and the value of failure is order except that a value of memory_order_acq_rel shall be replaced by the value memory_order_acquire and a value of memory_order_release shall be replaced by the value memory_order_relaxed. If and only if the comparison is false then, after the atomic operation, the contents of the memory in expected are replaced by the value read from object or by this during the atomic comparison. If the operation returns true, these operations are atomic read-modify-write operations (1.10) on the memory pointed to by this or object. Otherwise, these operations are atomic load operations on that memory.

2. Add the following example to the end of 99 [atomics.types.operations.req] p23:

   -23- [Note: […] — end note] [Example: […] — end example]

   [Example: Because the expected value is updated only on failure, code releasing the memory containing the expected value on success will work. E.g. list head insertion will act atomically and would not introduce a data race in the following code:

   
   do {
     p->next = head; // make new list node point to the current head
   } while(!head.compare_exchange_weak(p->next, p)); // try to insert
   

   — end example]