Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.std.c > #6332 > unrolled thread

atomic_compare_exchange atomicity of write to *expected

Back to article view | Back to comp.std.c

Contents

  atomic_compare_exchange atomicity of write to *expected Philipp Klaus Krause <pkk@spth.de> - 2021-10-05 12:46 +0200
    Re: atomic_compare_exchange atomicity of write to *expected Tijl Coosemans <tijl@coosemans.org> - 2021-10-08 13:20 +0200
      Re: atomic_compare_exchange atomicity of write to *expected Florian Weimer <fw@deneb.enyo.de> - 2021-10-11 07:51 +0200
        Re: atomic_compare_exchange atomicity of write to *expected Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-12-18 05:50 -0800
    Re: atomic_compare_exchange atomicity of write to *expected Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-10-09 03:04 -0700

#6332 — atomic_compare_exchange atomicity of write to *expected

For the atomic_compare-exchange family, e.g.

_Bool atomic_compare_exchange_strong(volatile A *object, C *expected, C
desired);

the description states "Atomically, compares the contents of the memory
pointed to by object for equality with that pointed to by expected, and
if true, replaces the contents of the memory pointed to by object with
desired, and if false, updates the contents of the memory pointed to by
expected with that pointed to by object."

This reads to me as if the write to *expected is also part of the atomic
operation. This doesn't map well to compare-and-swap hardware
instructions, where the content of *object would be written to a
register, and later stored into *expected by a separate instruction.

Of course, this difference only matters if it is observable. I think it
is observable if just after the compare-and swap, a second thread writes
*object, while the first thread has already done the comparison, but not
yet updated *expected.
Then e.g. a thread thread could read the new value from *object, but the
old one from *expected, which is not possible if
atomic_compare_exchange_strong is fully atomic (i.e. also wrt. *expected).

Is my understanding here correct (I'm not an expert on atomics)?

[toc] | [next] | [standalone]

#6338

On Tue, 5 Oct 2021 12:46:13 +0200 Philipp Klaus Krause <pkk@spth.de>
wrote:
> For the atomic_compare-exchange family, e.g.
> 
> _Bool atomic_compare_exchange_strong(volatile A *object, C *expected, C
> desired);
> 
> the description states "Atomically, compares the contents of the memory
> pointed to by object for equality with that pointed to by expected, and
> if true, replaces the contents of the memory pointed to by object with
> desired, and if false, updates the contents of the memory pointed to by
> expected with that pointed to by object."
> 
> This reads to me as if the write to *expected is also part of the atomic
> operation. This doesn't map well to compare-and-swap hardware
> instructions, where the content of *object would be written to a
> register, and later stored into *expected by a separate instruction.
> 
> Of course, this difference only matters if it is observable. I think it
> is observable if just after the compare-and swap, a second thread writes
> *object, while the first thread has already done the comparison, but not
> yet updated *expected.
> Then e.g. a thread thread could read the new value from *object, but the
> old one from *expected, which is not possible if
> atomic_compare_exchange_strong is fully atomic (i.e. also wrt. *expected).
> 
> Is my understanding here correct (I'm not an expert on atomics)?

*expected has type C, so it's not atomic, but even if it was, the
compare-and-swap, reading of *object, and reading of *expected are three
different operations and anything can happen in between them.

[toc] | [prev] | [next] | [standalone]

#6348

* Tijl Coosemans:

> On Tue, 5 Oct 2021 12:46:13 +0200 Philipp Klaus Krause <pkk@spth.de>
> wrote:
>> For the atomic_compare-exchange family, e.g.
>> 
>> _Bool atomic_compare_exchange_strong(volatile A *object, C *expected, C
>> desired);
>> 
>> the description states "Atomically, compares the contents of the memory
>> pointed to by object for equality with that pointed to by expected, and
>> if true, replaces the contents of the memory pointed to by object with
>> desired, and if false, updates the contents of the memory pointed to by
>> expected with that pointed to by object."
>> 
>> This reads to me as if the write to *expected is also part of the atomic
>> operation. This doesn't map well to compare-and-swap hardware
>> instructions, where the content of *object would be written to a
>> register, and later stored into *expected by a separate instruction.
>> 
>> Of course, this difference only matters if it is observable. I think it
>> is observable if just after the compare-and swap, a second thread writes
>> *object, while the first thread has already done the comparison, but not
>> yet updated *expected.
>> Then e.g. a thread thread could read the new value from *object, but the
>> old one from *expected, which is not possible if
>> atomic_compare_exchange_strong is fully atomic (i.e. also wrt. *expected).
>> 
>> Is my understanding here correct (I'm not an expert on atomics)?
>
> *expected has type C, so it's not atomic, but even if it was, the
> compare-and-swap, reading of *object, and reading of *expected are three
> different operations and anything can happen in between them.

And there are very few CPUs which can actually implement an atomic
updated of *expected as well.  Since the intent is that
atomic_compare_exchange maps to a typical CAS instruction, it's
apparent hat an atomic update of *expected can't be the intended
meaning.

I do think that the wording in the standard is ambiguous, though.

[toc] | [prev] | [next] | [standalone]

#6400

Florian Weimer <fw@deneb.enyo.de> writes:

> * Coosemans:
>
>> On Tue, 5 Oct 2021 12:46:13 +0200 Philipp Klaus Krause <pkk@spth.de>
>> wrote:
>>
>>> For the atomic_compare-exchange family, e.g.
>>>
>>> _Bool atomic_compare_exchange_strong(volatile A *object, C *expected, C
>>> desired);
>>>
>>> the description states "Atomically, compares the contents of the
>>> memory pointed to by object for equality with that pointed to by
>>> expected, and if true, replaces the contents of the memory pointed
>>> to by object with desired, and if false, updates the contents of
>>> the memory pointed to by expected with that pointed to by object."
>>>
>>> This reads to me as if the write to *expected is also part of the
>>> atomic operation.  This doesn't map well to compare-and-swap
>>> hardware instructions, where the content of *object would be
>>> written to a register, and later stored into *expected by a
>>> separate instruction.
>>>
>>> Of course, this difference only matters if it is observable.  I
>>> think it is observable if just after the compare-and swap, a
>>> second thread writes *object, while the first thread has already
>>> done the comparison, but not yet updated *expected.
>>>
>>> Then e.g. a thread thread could read the new value from *object,
>>> but the old one from *expected, which is not possible if
>>> atomic_compare_exchange_strong is fully atomic (i.e. also
>>> wrt. *expected).
>>>
>>> Is my understanding here correct (I'm not an expert on atomics)?
>>
>> *expected has type C, so it's not atomic, but even if it was, the
>> compare-and-swap, reading of *object, and reading of *expected are
>> three different operations and anything can happen in between them.
>
> And there are very few CPUs which can actually implement an
> atomic updated of *expected as well.  Since the intent is that
> atomic_compare_exchange maps to a typical CAS instruction,

I don't see anything in the C standard that supports this
premise.

> it's apparent hat an atomic update of *expected can't be the
> intended meaning.

I finally had a chance to look at this question more closely,
after which I think there is a stronger case for the opposite
conclusion.  The description of the atomic_compare_exchange
generic functions (given in section 7.17.7.4), along with the
introductory comments on atomic functions (given in 7.17.1, and
in particular 7.17.1 p5.4) and the definitions for the various
choices of memory_order (given in 7.17.3, and in particular
7.17.3 p6, for memory_order_seq_cst), taken together imply that
any update of *expected is covered by the atomic umbrella that
surrounds the atomic_compare_exchange_strong operation.

Note that this protection does not extend to arbitrary accesses
of *expected (at least I don't think it does), but it does
include all other accesses that are conducted under the auspices
of a memory_order_seq_cst operation.

Short summary:  any update of *expected is part of the overall
atomic operation.

[toc] | [prev] | [next] | [standalone]

#6342

Philipp Klaus Krause <pkk@spth.de> writes:

> For the atomic_compare-exchange family, e.g.
>
> _Bool atomic_compare_exchange_strong(volatile A *object,
> C *expected, C desired);
>
> the description states "Atomically, compares the contents of the
> memory pointed to by object for equality with that pointed to by
> expected, and if true, replaces the contents of the memory pointed
> to by object with desired, and if false, updates the contents of the
> memory pointed to by expected with that pointed to by object."
>
> This reads to me as if the write to *expected is also part of the
> atomic operation.

For what it's worth my reading agrees on this point:  any update
of *expected is included in the indivisible atomic operation of
comparing and either replacing of *object or updating of *expected.

> This doesn't map well to compare-and-swap hardware instructions,
> where the content of *object would be written to a register, and
> later stored into *expected by a separate instruction.

What I think you mean is that it /might/ not map nicely onto an
unprotected compare-and-swap operation, depending on context.
More on that point given below.

> Of course, this difference only matters if it is observable.  I
> think it is observable if just after the compare-and swap, a second
> thread writes *object, while the first thread has already done the
> comparison, but not yet updated *expected.

Yes, in the worst case the combination of compare-and-swap and
(possible) subsequent update of *expected needs to be wrapped in
a protective shell covered by an inter-thread mutex, to prevent
other threads from breaking the atomicity requirements.  But
please note: in the worst case.  See below.

> Then e.g. a thread thread could read the new value from
> *object, but the old one from *expected, which is not possible
> if atomic_compare_exchange_strong is fully atomic (i.e. also
> wrt. *expected).

Consider the following function (disclaimer: not compiled):

  void
  update_atomic( volatile A* it, C new_from_old( C ) ){
    C old = { 0 }, new;
    do {
      new = new_from_old( old );
    } while(  ! atomic_compare_exchange_strong( it, &old, new )  );
  }

An implementation may compile this function using an inline
compare-and-swap, with no surrounding protection of using an
inter-thread mutex.  A surrounding mutex call is not needed,
because the variable 'old' cannot be affected by what other
threads are doing (at least not in a way that has defined
behavior), and implementations can know that based on the
code in the function definition.


> Is my understanding here correct (I'm not an expert on atomics)?

My comments above are made primarily based on what I believe the
C standard requires, and not so much on trying to discern what I
think your understanding may be.  If what I've said helps your
understanding then that's great but my emphasis has been on
explicating the consequences of what is in the C standard.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.std.c

csiph-web