LWG4174 [atomics.order] p3.3 The initialization to an atomic object is not a atomic operation

[xmh0511]

Full name of submitter (unless configured in github; will be published with the issue): Jim X

Consider this example:

std::atomic<int> v = 0;
// thread 1:
v.load(std::memory_order::seq_cst);
//thread 2:
v.store(1,std::memory_order::seq_cst);

If the load operation reads the value 0, how are they ordered in the single total order? 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 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

The initialization to v is not an atomic modification as per [atomics.types.operations] p3

Effects: Initializes the object with the value desired. Initialization is not an atomic operation ([intro.multithread]).

The initialization(i.e. X) precedes the store(i.e. B) in the modification order of v, however, X is not atomic modification, so, how does p3.3 apply to this case to determine the order of the load and store in the single total order?

[t3nsor]

I deleted my previous comment because I misread the example.

It's possible that there's a defect here, but I'm not sure yet. In this example, there is no observable consequence of the total order; in fact, because no other variables are present, even if both operations were relaxed, the program would have the same behavior as this one that uses sequentially consistent operations.

Do you have an example where the observable behavior of the program could actually be affected by the inability to determine which operation is earlier in the total order?

[languagelawyer]

Related: #38, #96 (comment)

[xmh0511]

I deleted my previous comment because I misread the example.

It's possible that there's a defect here, but I'm not sure yet. In this example, there is no observable consequence of the total order; in fact, because no other variables are present, even if both operations were relaxed, the program would have the same behavior as this one that uses sequentially consistent operations.

Do you have an example where the observable behavior of the program could actually be affected by the inability to determine which operation is earlier in the total order?

This issue just gave a minimum example to expose the defect wording. A concrete example could be Peterson's algorithm, when we want to prove the correctness of the algorithm, we should first assume the case where both flags read the initialization value, and in that case the result forms the invalid single total order to prove the assumption is not possible.

In this proof, [atomics.order] p3 is necessary, to determine the orders of the seq_cst load and store operations in the single total order where A is the load operation, B is the store operation, and the initialization modification is that X. However, X must be an atomic modification, so how to order A and B where the initialization modification is not that X?

A relevant discussion can be found https://stackoverflow.com/questions/79183275/can-the-combination-of-pure-load-and-a-store-model-the-rmw-operation?noredirect=1#comment139629372_79183275

[t3nsor]

Can you be a bit more concrete about your concern about the total order in Peterson's algorithm? Your original example was formulated in terms of "even if the load operation reads the value stored by the store operation, I cannot prove that the store operation was earlier in the total order". What is the analogous concern in the case of Peterson's algorithm?

[xmh0511]

Can you be a bit more concrete about your concern about the total order in Peterson's algorithm? Your original example was formulated in terms of "even if the load operation reads the value stored by the store operation, I cannot prove that the store operation was earlier in the total order". What is the analogous concern in the case of Peterson's algorithm?

Given this simplified example:

std::atomic<bool> a = false;
std::atomic<bool> b = false;
int v = 0;
// thread 1:
a.store(true, seq_cst);
if(b.load(seq_cst)== false){
   v = 1;  // #1
}
//thread 2:
b.store(true, seq_cst);
if(a.load(seq_cst)== false){
   v = 2; // #2
}

To prove whether #1 and #2 can have data race, we should prove whether it's possible that a and b simultaneously read false. This proof equals whether there can be a valid single total order in this case. To determine the order of b.load and b.store when b.load reads the initialization value false, [atomics.order] p3.3 should apply here. However, the initialization is not an atomic modification such that X cannot be that value.

[jensmaurer]

LWG4174