• atomic_compare_exchange atomicity of write to *expected

    From Philipp Klaus Krause@pkk@spth.de to comp.std.c on Tue Oct 5 12:46:13 2021
    From Newsgroup: comp.std.c

    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)?
    --- Synchronet 3.19a-Linux NewsLink 1.113
  • From =?UTF-8?B?VMSzbA==?= Coosemans@tijl@coosemans.org to comp.std.c on Fri Oct 8 13:20:58 2021
    From Newsgroup: comp.std.c

    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.

    --- Synchronet 3.19a-Linux NewsLink 1.113
  • From Tim Rentsch@tr.17687@z991.linuxsc.com to comp.std.c on Sat Oct 9 03:04:29 2021
    From Newsgroup: comp.std.c

    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.
    --- Synchronet 3.19a-Linux NewsLink 1.113
  • From Florian Weimer@fw@deneb.enyo.de to comp.std.c on Mon Oct 11 07:51:28 2021
    From Newsgroup: comp.std.c

    * 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.
    --- Synchronet 3.19a-Linux NewsLink 1.113
  • From Tim Rentsch@tr.17687@z991.linuxsc.com to comp.std.c on Sat Dec 18 05:50:05 2021
    From Newsgroup: comp.std.c

    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.
    --- Synchronet 3.19a-Linux NewsLink 1.113