c++synchronizationmemory-barriers

"Synchronizes with" relation


From the cppreference article on std::memory_order:

Synchronizes with: If an atomic store in thread A is a release operation, an atomic load in thread B from the same variable is an acquire operation, and the load in thread B reads a value written by the store in thread A, then the store in thread A synchronizes-with the load in thread B.

Does "…reads a value written by…" have a precise meaning that I'm missing?


Solution

  • Each atomic object has (individually) a total order of its modifications, the so-called modification order, which all threads must globally agree on.

    Every side effect (i.e. store) on the atomic object makes up an entry in this modification order.

    Each value computation (i.e. load) on the atomic object takes its value from one of the side effects in this modification order, which aside from some consistency rules, is an unspecified one.

    These consistency rules are given on the cppreference page you linked:

    The following four requirements are guaranteed for all atomic operations:

    1. Write-write coherence: If evaluation A that modifies some atomic M (a write) happens-before evaluation B that modifies M, then A appears earlier than B in the modification order of M.

    2. Read-read coherence: if a value computation A of some atomic M (a read) happens-before a value computation B on M, and if the value of A comes from a write X on M, then the value of B is either the value stored by X, or the value stored by a side effect Y on M that appears later than X in the modification order of M.

    3. Read-write coherence: if a value computation A of some atomic M (a read) happens-before an operation B on M (a write), then the value of A comes from a side-effect (a write) X that appears earlier than B in the modification order of M.

    4. Write-read coherence: if a side effect (a write) X on an atomic object M happens-before a value computation (a read) B of M, then the evaluation B shall take its value from X or from a side effect Y that follows X in the modification order of M.

    Note that the above uses informal language like "the value of A comes from", which formally should be "the value computation on A takes its value from". The formal specification can be found in [intro.races]/14 and following paragraphs.

    "and the load in thread B reads a value written by the store in thread A" is also a less formal way to say "and the value computation in thread B takes its value from the side effect in thread A in the modification order of the atomic object".

    Your quote is saying that the synchronizes-with relation occurs only with the particular evaluation that caused the side effect to the atomic object from which the value computation takes its value.

    What this means in particular is that if there are two side effects in the modification order that both store the same value to the atomic, then, taking into account the consistency rules above, it may be possible that a value computation on the atomic will take its value from either one of the two. While you can't distinguish the two cases by looking at the value produced by the load, it will still affect the synchronizes-with relation and what memory synchronization guarantees you will get.


    As @PeterCordes points out in a comment under this answer, the rule for when a release/acquire implies synchronizes-with quoted from cppreference is also incomplete. In fact the synchronizes-with relation is not only established with the evaluation which caused the side effect from which the value computation takes its value.

    Instead the relation exists also if the value computation takes its value from any side effect in the so-called release sequence headed by the release operation under consideration, which is a contiguous subsequence of the modification order made up of release operations starting from the release operation under consideration.

    This means that if the value is taken from some release operation in the modification order and there is another release operation before it, then generally the acquire operation also synchronizes-with the previous release operation.

    But due to some uncommon CPU memory models out there this does not apply to all previous release operations. The current definition for release sequence can be found in [intro.races]/5 and there are (ongoing?) discussions about it. Specifically the current definition contains only release operations that are also read-modify-write operations.

    Naively one would probably expect the synchronizes-with relation to apply with all previous release-stores in the modification order, so this can cause some surprising results.

    For example, consider this scenario:

    Then thread 3 can safely retrieve data B, but because the non-RMW modification isn't part of the release sequence, there won't be any synchronization with thread 1 and accessing data A will be a data race.