c++language-lawyerc++20atomic

Is the load part of a read-modify-write operation of atomic object guaranteed to read the last value in modification order compared to load operation?

Consider this example:

std::atomic<int> v = {0};

// thread 1:
for(int i = 0; i<999999;i++)
   v.load(memory_order::seq_cst);  // #1

v.exchange(2,memory_order::seq_cst);  // #2

//thread 2:
  v.store(1,memory_order::seq_cst);  // #3

Assuming the modification order of v is {0, 1} where 0 is written by the initialization of v and 1 is stored by #3 in thread 2 and both #1 and #2 does not happen before #3. According to [intro.races] p14 ~ p18:

The value of an atomic object M, as determined by evaluation B, is the value stored by some unspecified side effect A that modifies M, where B does not happen before A.

If an operation A that modifies an atomic object M happens before an operation B that modifies M, then A is earlier than B in the modification order of M.

If a value computation A of an atomic object M happens before a value computation B of M, and A takes its value from a side effect X on M, then the value computed by B is either the value stored by X or the value stored by a side effect Y on M, where Y follows X in the modification order of M.

If a value computation A of an atomic object M happens before an operation B that modifies M, then A takes its value from a side effect X on M, where X precedes B in the modification order of M.

If a side effect X on an atomic object M happens before a value computation B of M, then the evaluation B takes its value from X or from a side effect Y that follows X in the modification order of M.

the load operation at #1 is permitted to always read 0 until the end of the loop, it also can be 1. However, the load part of #2 must read 1 that is written by #3 as per [atomics.order] p10

Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.

In this case, if #1 always reads 0 in its loop, it also does not violate the single total: #1 is sequenced before #2, which also means #1 strongly happens before #2, so, in the single total order, #1 precedes #2, since #1 reads 0 and 0 precedes 1(produced by #3) in the modification order of v, according to [atomics.order] p3

An atomic operation A on some atomic object M is coherence-ordered before another atomic operation B on M if

  • A is a modification, and B reads the value stored by A, or
  • [...]
  • A and B are not the same atomic read-modify-write operation, and there exists an atomic modification X of M such that A reads the value stored by X and X precedes B in the modification order of M, or

#1 is coherence-ordered before #3, hence, #1 precedes #3 in the single total order. Finally, since #2 reads the value written by #3, #3 is coherence-ordered before #2, hence #3 precedes #2 in the single total order. which all three requirements

  1. #1 precedes #2
  2. #1 precedes #3
  3. #3 precedes #2

can form a valid single total {#1, #3, #2}

Hence, with the pre-conditions, #1 can always load 0, and #2 must read the value 1. Is this a possible output?

Solution

  • I think you're overthinking it.

    Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.

    This just says that RMWs are invidivisable, i.e. no writes can be inserted between the read part and the write part. (In other words, they say that the "write" part of RMW appears in the modification order right after the value that was read by the "read" part, that's all).

    This doesn't say that RMWs are any less prone to reading stale values than non-RMW reads. (Maybe that's what happens in practice on some platforms, but that's above my paygrade and isn't the point.)

    This presumed difference doesn't affect how you analyze the programs anyway. If all #1s returned 0, and #2 suddenly returned 1, is it because, #1 was reading a "stale" value, or because #3 happened to happen exactly between the last #1 and #2? You can't tell, and it doesn't matter.

    Also operations on v have to be consistent with the global seq-cst order, but that doesn't tell you much. (If all #1s returned 0 and #2 returned 1, then #3 lands between the latest #1 and #2. If some #1 returns 1, then #3 is right before that, etc.)

    [assume that] both #1 and #2 does not happen before #3

    They can't happen-before #3 in the first place, I believe (for A to happen-before B in a different thread, there has to be a synchronizes-with relationship, so either B must be a read, or must have a preceding read in the same thread). At best you can say they're coherence-ordered-before, or that #2 precedes #3 in the modification order of v.

    In general, I'd start my assumptions with what value each load returns, and deduce the various "...-before" orderings from there, not the other way around.