This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++17 status.

### 2426. Issue about `compare_exchange`

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

Priority: 1

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, updates replaces the contents of the memory in `expected` with the contents of value 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`)?

> - 33.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 true if and only if true, and change if false if 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 a Atomically, compares the contents of the memory pointed to by `object` or by `this` for equality with that in previously 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]