6

I was reading about memory orders in C++. I could understand relaxed and acquire-release models a well. But I'm struggling with sequential-consistency.

If I am not wrong, from cppreference, std::memory_order_seq_cst 'operation' is equivalent to:

  • an acquire operation plus a single total order when the operation is 'load'.
  • a release operation plus a single total order when the operation is 'store'.
  • an acq-rel operation plus a single total order when the operation is 'read-modify-write'.

But what is the case with std::memory_order_seq_cst 'fence'? Is it equivalent to which of these?

  • an acquire fence plus a single total order.
  • a release fence plus a single total order.
  • an acq-rel fence plus a single total order.

If it is equivalent to one of above, what about the other two?

As far as I know, if it is case 1 (acquire fence), compilers would be free to move any write operation from above the fence to below it. Similarly, if it is case 2 (release fence), compilers would be free to move any read operation from below the fence to above it. Finally, if it is case 3 (acq-rel fence), compilers would be disallowed to move any instructions across the fence. Is this correct?

I'm still in a lot of confusion. Above statements may be incorrect. Please correct me where I'm wrong.

20
  • 1
    The standard calls it "a sequentially consistent acquire and release fence" (§7.17.4.1)
    – Homer512
    Feb 27 at 20:54
  • 1
    std::atomic_thread_fence( std::memory_order ) has to use one of the standard memory_order values; there aren't different flavours of seq_cst, there's only std::memory_order_seq_cst. I don't think there'd be much use for a fence that was for example part of the SC total order but which allowed non-SC loads to reorder with it, only ordering stores. Also not cheaper on many machines; an SC fence has to include a StoreLoad barrier, the most expensive type, might as well do them all: preshing.com/20120913/acquire-and-release-semantics Feb 28 at 8:40
  • 2
    As @curiousguy says, the C++ formalism is defined in terms of syncs-with and happens-before. The way CPUs and compilers implement those semantics is coherent shared cache, with local reordering allowed for accesses to it. preshing.com/20120710/… (And on e.g. PowerPC, store-forwarding between logical cores sharing a physical core before commit to L1d cache, creating IRIW reordering.) Feb 28 at 20:38
  • 2
    To implement fence(seq_cst) in the normal mapping from C++ to asm (cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html), you need to block all reordering, it's a full barrier. Unlike any other fence strength, it needs to keep an earlier relaxed store from reordering with a later relaxed load. (i.e. block StoreLoad reordering, like I said.) It also does all the things, LoadStore, LoadLoad and StoreStore. Feb 28 at 20:42
  • 2
    The no-StoreLoad reordering requirement comes from the fact that the "single total order" of all SC operations has to be consistent with program order (sequenced-before). I forget the formal details of how SC fences interact with that. But the key thing you left out of your question is that the total order has to be some interleaving across threads of program order. Feb 28 at 20:51

2 Answers 2

2

In short, it's case 3.

A seq_cst fence includes all the functionality of an acq_rel fence. See [atomics.fences p5.5]:

is a sequentially consistent acquire and release fence, if order == memory_order::seq_cst.

So in particular it is an acquire and release fence. And it is also a sequentially consistent fence, meaning that it is included in the total order S defined in [atomics.order p4], in a manner consistent with the rules stated there.

The formal C++ memory model does not have a concept of "reordering". However, you are right that a typical implementation of a seq_cst fence would be one which prevents loads and stores from being reordered across it in either direction. Note that this is strictly stronger than an acq_rel fence, which would permit a store before the fence to be reordered with a load after the fence (StoreLoad reordering).

1

This is what I think the authors of the standard intended for C_17 and C++20. My version of the abstract machine (see below). The proof of logical equivalence of the old and a new abstract machine is not included though, sorry.

Regarding your question please read rule 13 below. You will notice the (very simple) difference. It is obvious when rules are simplified like that. That difference comes from this idiomatic example, which shows that acq_rel combo-fence is not enough to avoid x == 0 && y == 0, so a seq_cst fence with special properties (namely a full memory barrier, forget about the "single order") is needed:

// Without reordering
// thread A
    std::atomic<int> a {0}, x {0};
    extern std::atomic<int> b;
    a.store(1, memory_order_relaxed);
    std::atomic_thread_fence(memory_order_acq_rel);
    if (b.load(memory_order_relaxed) == 1) {
        x.store(1, memory_order_relaxed);
    }
    /* ... */
// thread B
    std::atomic<int> b {0}, y {0};
    extern std::atomic<int> a;
    b.store(1, memory_order_relaxed);
    std::atomic_thread_fence(memory_order_acq_rel);
    if (a.load(memory_order_relaxed) == 1) {
        y.store(1, memory_order_relaxed);
    }
    /* ... */

// With the reordering
// thread A
    std::atomic<int> a {0}, x {0}, c;
    extern std::atomic<int> b;
    std::atomic_thread_fence(memory_order_acquire);
    c = b.load(memory_order_relaxed);
    a.store(1, memory_order_relaxed);
    std::atomic_thread_fence(memory_order_release);
    if (c == 1) {
        x.store(1, memory_order_relaxed);
    }
    /* ... */
// thread B
    std::atomic<int> b {0}, y {0}, d;
    extern std::atomic<int> a;
    std::atomic_thread_fence(memory_order_acquire);
    d = a.load(memory_order_relaxed);
    b.store(1, memory_order_relaxed);
    std::atomic_thread_fence(memory_order_release);
    if (d == 1) {
        y.store(1, memory_order_relaxed);
    }
    /* ... */

Mathematicians are welcomed. Jokers too. Due respect to Jeff Preshing and his series of the articles about lock-free programming!

Multi-threaded executions and data races (new version to n2346 C_17)

  1. Under a hosted implementation, a program can have more than one thread of execution (or thread) running concurrently. The execution of each thread proceeds as defined by the remainder of this document. The execution of the entire program consists of an execution of all of its threads. Under a freestanding implementation, it is implementation-defined whether a program can have more than one thread of execution.

  2. If there are two accesses to the same memory location, one of which is a writing and both are not ordered by the "happens before" relation defined below, the behavior is undefined.

  3. Note: an access is an action that happens in the execution environment, see rules n2346 (3.1, 5.1).

  4. For any possible execution of the entire program, for any atomic object, any pair A, B of accesses to it, "A happens before B" xor "B happens before A". If there is also an access C to the atomic object, such that "A happens before C" and "C happens before B", then "A happens before B".

  5. Note: the proof of the rule consists of: a) proving the absence of any consequences to the introduction of the converse rules of the cache coherence rules of the old abstract machine to the new one, thus extending the meaning (definition) of "happens before" relation; b) consolidating those converse rules into a single rule.

  6. X, T, U are some accesses in the following rules. In the following rules all accesses may happen on different memory locations and may be evaluated in different threads, unless otherwise specified.

  7. A simply inter-thread happens before B, if an access A to an atomic object happens before an access B to the same object, but which is evaluated in another thread.

  8. A subexpression A carries a dependency to a subexpression B if:

  • the value of A is used as an operand of B, unless: • B is an invocation of the kill_dependency macro, or • A is the left operand of a && or || operator, or • A is the left operand of a ?: operator, or • A is the left operand of a , operator; or

  • A writes to a memory location, B reads from it, and A is sequenced before B.

  1. Note: the "unless"-exceptions, which breaks "carries a dependency to" chain through operands of subexpressions, are chosen by the authors of the standard for the convenience of a programmer, no hardware limitations were implied here. Looks like.

  2. A is consume-ordered before B if:

  • a release writing A simply inter-thread happens before a consume reading B; or

  • an access A is sequenced before X and X is consume-ordered before B; or

  • A is consume-ordered before X and X carries a dependency to an access B.

  1. Note: an access X carries dependency to B, iff the subexpressions, which X, B are evaluated because of, do the same.

  2. A simply synchronizes with B, if a writing A simply inter-thread happens before a reading B.

  3. A relacq-synchronizes with B if:

  • a release writing A simply synchronizes with an acquire reading B; or

  • a release fence A is sequenced before T and T simply synchronizes with an acquire reading B; or

  • a release writing A simply synchronizes with U and U is sequenced before an acquire fence B; or

  • a release fence A is sequenced before T, T simply synchronizes with U and U is sequenced before an acquire fence B; or

  • a seqcst fence A is sequenced before T and T simply inter-thread happens before an acquire reading B; or

  • a release writing A simply inter-thread happens before U and U is sequenced before a seqcst fence B; or

  • a seqcst fence A is sequenced before T, T simply inter-thread happens before U and U is sequenced before a seqcst fence B.

  1. A is sync-ordered before B if:
  • A relacq-synchronizes with B; or

  • an access A is sequenced before X and X relacq-synchronizes with B; or

  • A relacq-synchronizes with X and X is sequenced before an access B; or

  • a seqcst access A is sequenced before a seqcst access C and C variously inter-thread happens before a seqcst access B; or

  • a seqcst access A variously inter-thread happens before a seqcst access C and C is sequenced before a seqcst access B.

  1. Note: rules n2346 (7.17.3\3, 9-11; 7.17.4\3, 4) of the old abstract machine do not prohibit reordering of a reading (writing) before (after) a "fence" with a seqcst writing (reading) in another thread, the new abstract machine proudly does that and even more as it may have been intended by the authors of the standard. I may be wrong of course, so let mathematicians correct me.

  2. A variously inter-thread happens before B if:

  • A simply inter-thread happens before B; or

  • A is consume-ordered before B; or

  • A is sync-ordered before B; or

  • A variously inter-thread happens before X and X variously inter-thread happens before B.

  1. A happens before B, if A is sequenced before B or A variously inter-thread happens before B.

  2. A is a visible writing to a memory location M with respect to a reading B from M, iff:

  • A happens before B, and

  • there is no other writing X to M such that A happens before X and X happens before B.

  1. B reads the value written by A, if A is a visible writing to a reading B.

  2. A reading from an atomic object reads the value from only one writing to that object.

  3. Note: that and also rule 4 implicate that writing to be a visible writing.

  4. Note: the declaration of an object (even without initializer) specifies an initialization writing to that object.

  5. The implementation should not introduce a writing, which is not specified by any statement in a program, to any object declared in the program.

Multi-threaded executions and data races (new version to n4860 C++20)

Rules 1-13 are the same as the new rules 1-13 for C_17 above. Rules 17-23 are the same as the new rules 17-23 for C_17 above.

  1. A is sync-ordered before B if:
  • an access A is sequenced before X and X relacq-synchronizes with B; or

  • A relacq-synchronizes with X and X is sequenced before an access B; or

  • a seqcst access A is sequenced before a seqcst access C and C strongly inter-thread happens before a seqcst access B; or

  • a seqcst access A strongly inter-thread happens before a seqcst access C and C is sequenced before a seqcst access B.

  1. A strongly inter-thread happens before B if:
  • A simply inter-thread happens before B; or

  • A is sync-ordered before B; or

  • A strongly inter-thread happens before X and X strongly inter-thread happens before B.

  1. A variously inter-thread happens before B if:
  • A strongly inter-thread happens before B; or

  • A relacq-synchronizes with B; or

  • A is consume-ordered before B; or

  • A variously inter-thread happens before X and X variously inter-thread happens before B.

4
  • 2
    This is all very interesting but I do not see how it answers the question in any way. Apr 20 at 1:21
  • @NateEldredge I have looked more attentively and indeed not only the answer is not clear, but I have found the mistake of not specifying the ability of seq_cst fences to couple with ordinary release and acquire accesses. Now I have rewritten everything... Thank you for your interest! Apr 21 at 16:57
  • Well, I have more questions, but I still don't think this is a good answer to the question at hand, and so I really do not think this answer's comments are the right place to discuss further. Have you written this up and posted it anywhere else? Apr 23 at 3:22
  • @NateEldredge That is not the shortest answer, yeah... If you want to, you may write to my mdzar5___gmail. Apr 23 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.