Are seq-cst fences exactly the same as acq-rel fences in absence of seq-cst loads?

Question

I'm trying to understand the purpose of std::atomic_thread_fence(std::memory_order_seq_cst); fences, and how they're different from acq_rel fences.

So far my understanding is that the only difference is that seq-cst fences affect the global order of seq-cst operations ([atomics.order]/4). And said order can only be observed if you actually perform seq-cst loads.

So I'm thinking that if I have no seq-cst loads, then I can replace all my seq-cst fences with acq-rel fences without changing the behavior. Is that correct?

And if that's correct, why am I seeing code like this "implementation Dekker's algorithm with Fences", that uses seq-cst fences, while keeping all atomic reads/writes relaxed? Here's the code from that blog post:

std::atomic<bool> flag0(false),flag1(false);
std::atomic<int> turn(0);

void p0()
{
    flag0.store(true,std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_seq_cst);

    while (flag1.load(std::memory_order_relaxed))
    {
        if (turn.load(std::memory_order_relaxed) != 0)
        {
            flag0.store(false,std::memory_order_relaxed);
            while (turn.load(std::memory_order_relaxed) != 0)
            {
            }
            flag0.store(true,std::memory_order_relaxed);
            std::atomic_thread_fence(std::memory_order_seq_cst);
        }
    }
    std::atomic_thread_fence(std::memory_order_acquire);
 
    // critical section


    turn.store(1,std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_release);
    flag0.store(false,std::memory_order_relaxed);
}

void p1()
{
    flag1.store(true,std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_seq_cst);

    while (flag0.load(std::memory_order_relaxed))
    {
        if (turn.load(std::memory_order_relaxed) != 1)
        {
            flag1.store(false,std::memory_order_relaxed);
            while (turn.load(std::memory_order_relaxed) != 1)
            {
            }
            flag1.store(true,std::memory_order_relaxed);
            std::atomic_thread_fence(std::memory_order_seq_cst);
        }
    }
    std::atomic_thread_fence(std::memory_order_acquire);
 
    // critical section


    turn.store(0,std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_release);
    flag1.store(false,std::memory_order_relaxed);
}

Answer 1

Before C++20, the C++ standard contained the following paragraphs to define visibility in terms of the single total order S (see [atomics.order]):

For an atomic operation B that reads the value of an atomic object M, if there is a memory_order_seq_cst fence X sequenced before B, then B observes either the last memory_order_seq_cst modification of M preceding X in the total order S or a later modification of M in its modification order.

For atomic operations A and B on an atomic object M, where A modifies M and B takes its value, if there is a memory_order_seq_cst fence X such that A is sequenced before X and B follows X in S, then B observes either the effects of A or a later modification of M in its modification order.

For atomic operations A and B on an atomic object M, where A modifies M and B takes its value, if there are memory_order_seq_cst fences X and Y such that A is sequenced before X, Y is sequenced before B, and X precedes Y in S, then B observes either the effects of A or a later modification of M in its modification order.

However, WG21/P0668R5 proposed two changes that were accepted for C++20: first, it weakens some guarantees of the single total order (it no longer needs to be consistent with "happens-before"), and second (and more importantly for this question), it strengthens the guarantees provided by seq-cst fences. For that they replaced Section 32.4 [atomics.order] paragraphs 3-7 (the definition of SC ordering) with the wording referenced in your question. P0668R5 states:

This new wording takes a significantly different approach with respect to the sequential consistency ordering S: Instead of defining visibility in terms of S and the other orders in the standard, this essentially defines constraints on S in terms of visibility in a particular execution, as expressed by the coherence order. If these constraints are not satisfiable by any total order S, then the candidate execution which gave rise to the coherence order is not valid.

To be honest I find this new definition to be less clear, but I suppose I just need to read through it a few more times and try to wrap my head around it. :) However, since this is supposed to strengthen the guarantees, the visibility guarantees described in previous standards should still hold.

Seq-cst fences are also part of the single total order S, so any two seq-cst fences are always totally ordered. Suppose we have a write operation A that is sequenced before a seq-cst fence X, and a read operation B that is sequenced after a seq-cst fence Y. If X is ordered before Y in S, then B is guaranteed to observe the value written by A, or some later value (this is based on the last paragraph from the first quote). An acq-rel fence does not provide any such guarantees.

Acq-rel fences basically convert surrounding relaxed load/stores into acquire/release operations, but acq-rel only provides visibility guarantees for surrounding operations once an acquire-load synchronizes with a release-store. That is, only once the load has already observed the value stored. But it does not provide any guarantee when the store becomes visible.

Answer 2

As I understand it, they're not the same, and a counterexample is below. I believe the error in your logic is here:

And said order can only be observed if you actually perform seq-cst loads.

I don't think that's true. In atomics.order p4 which defines the axioms of the sequential consistency total order S, items 2-4 all may involve operations which are not seq_cst. You can observe the coherence ordering between such operations, and this can let you infer how the seq_cst operations have been ordered.

As an example, consider the following version of the StoreLoad litmus test, akin to Peterson's algorithm:

std::atomic<bool> a,b;  // initialized to false

void thr1() {
    a.store(true, std::memory_order_seq_cst);
    std::atomic_thread_fence(std::memory_order_seq_cst);
    if (b.load(std::memory_order_relaxed) == false)
        std::cout << "thr1 wins";
}

void thr2() {
    b.store(true, std::memory_order_seq_cst);
    std::atomic_thread_fence(std::memory_order_seq_cst);
    if (a.load(std::memory_order_relaxed) == false)
        std::cout << "thr2 wins";
}

Note all the loads are relaxed.

I claim that if thr1 prints "thr1 wins", then we deduce that a.store(true) preceded b.store(true) in the sequential consistency order S.

To see this, let A be b.load() and B be b.store(true). If b.load() == false then we have that A is coherence-ordered before B. (Apply atomics.order p3.3 with A,B as above, and X the initialization of b to false.)

Now let X be the fence in thr1. Then X happens before A by sequencing, so X precedes B in S by atomics.order p4.3. That is, the thr1 fence precedes b.store(true). And a.store(true), which is also seq_cst, precedes the thr1 fence, because the store strongly happens before the fence by sequencing. So by transitivity, a.store(true) precedes b.store(true), as claimed.

Similarly, if thr2 prints, then b.store(true) precedes a.store(true). They can't both precede each other, so we have therefore proved that the program cannot print both messages.

If you downgrade the fences to acq_rel, the proof breaks down. In that case, as far as I can see, nothing prevents the program from printing thr1 wins even if b.store(true) precedes a.store(true) in the order S. As such, with acq_rel fences, I believe it is allowed for both threads to print. Though I'm not sure whether there is any real implementation where it could actually happen.

---

We can get an even simpler example if we make all the loads and stores relaxed, so that the only seq_cst operations are the fences. Then we can use (4.4) instead to show that if b.load(relaxed) returns false, the thr1 fence precedes the thr2 fence, and vice versa if a.load() returns false. We therefore conclude, as before, that the program cannot print both messages.

However, if we keep the loads and stores relaxed and weaken the fences to acq_rel, it is then more clear that we have lost this guarantee. Indeed, with a little prodding, a similar example actually fails on x86, where the acq_rel fence is a no-op because the loads/stores are already acquire/release. So that's a clearer case where a seq_cst fence really achieves something that acq_rel does not.

Answer 3

To summarize the argument made by Nate Eldredge in their answer:

---

The global seq-cst order by itself doesn't seem to affect anything other than seq-cst loads, but the order must exist even if there are no loads.

Certain operation reorderings (like, in Nate's example, both threads entering the critical section) would impose contradicting constraints on the seq-cst order, and are therefore not allowed.

I'm not entirely sure if this effect can be observed without seq-cst fences (i.e. only with seq-cst stores), I think no.