Search code examples
cmultithreadingassemblyx86stdatomic

Are 2 consecutive statements sequenced-before each other?


I'm reading a part of the C Standard related to multi-threaded execution and highly confused by the definition of Sequenced-before which is used to define inter-thread happens before:

5.1.2.4/16:

A is inter-thread happens before B if for some action X

A is sequenced before X and X inter-thread happens before B


Initially I was thinking that if action A precedes action B in the program order then A sequenced before B, but consider the following simple example:

int read_write(int *a, int *b) {
    *a = 10;
    return *b;
}

which compiles to

read_write:
        mov     DWORD PTR [rdi], 10
        mov     eax, DWORD PTR [rsi]
        ret

Godbolt

It's clear that if *a, and *b are unrelated memory locations then according to Intel Manual Vol.3:

  • store can be reordered with later load to unrelated memory location

It's clear that such reordering happens on the hardware level due to store-buffer forwarding, but the Standard makes it clear that Sequenced-before is about how exactly evaluations are done:

5.1.2.3/3:

Sequenced before is an asymmetric, transitive, pair-wise relation between evaluations executed by a single thread, which induces a partial order among those evaluations. Given any two evaluations A and B, if A is sequenced before B, then the execution of A shall precede the execution of B. (Conversely, if A is sequenced before B, then B is sequenced after A.) If A is not sequenced before or after B, then A and B are unsequenced.

Which in the example is unspecified. So this means that the store *a = 10; is unsequenced to the load *b. The Standard notes at 5.1.2.3/6 that

Volatile accesses to objects are evaluated strictly according to the rules of the abstract machine.


QUESTION: Is it sufficient to make at least one pointer to point to a volatile variable, or both int *a and int *b must be volatile to ensure sequenced-before realtion?

Here is what I mean:

int read_write(volatile int *a, int *b) {
    *a = 10; 
    //sequenced before since a points to volatile int
    return *b;
}

and

int read_write(int *a, volatile int *b) {
    *a = 10; 
    //sequenced before since b points to volatile int
    return *b;
}

But adding volatile does not change the compiled code which is relatively confusing.


Solution

  • Which in the example is unspecified.

    No, sequencing is not unspecified in your example. C 2018 6.8 4 says:

    A full expression is an expression that is not part of another expression, nor part of a declarator or abstract declarator… There is a sequence point between the evaluation of a full expression and the evaluation of the next full expression to be evaluated.

    In the example code:

        *a = 10;
        return *b;
    

    *a = 10 is an expression that is not part of another expression, so it is a full expression. And *b is also an expression that is not part of another expression, so it is a full expression. So there is a sequence point between these two expressions.

    5.1.2.3 3 says:

    … The presence of a sequence point between the evaluation of expressions A and B implies that every value computation and side effect associated with A is sequenced before every value computation and side effect associated with B

    So the value computations and the side effect of *a = 10 are sequenced before the value computation of *b.

    … according to Intel Manual Vol.3:

    • store can be reordered with later load to unrelated memory location

    This is irrelevant to C semantics. The hardware may execute the operations one way or another, but its end results will conform to the required C semantics (because the compiler was written to generate instructions that do that, even if the hardware reorders the operations).

    The C semantics do not define what the hardware must do except for the observable behavior of the program. 5.1.2.3 6 says the observable behavior is:

    — Accesses to volatile objects are evaluated strictly according to the rules of the abstract machine.

    — At program termination, all data written into files shall be identical to the result that execution of the program according to the abstract semantics would have produced.

    — The input and output dynamics of interactive devices shall take place as specified in 7.21.3. The intent of these requirements is that unbuffered or line-buffered output appear as soon as possible, to ensure that prompting messages actually appear prior to a program waiting for input.

    So as long as the hardware ultimately produces the desired input and output and other behavior described above, it does not matter what order it performs operations in.

    QUESTION: Is it sufficient to make at least one pointer to point to a volatile variable, or both int *a and int *b must be volatile to ensure sequenced-before realtion?

    Making *a or *b or both volatile will not change the sequencing in the C semantics, which already exists. Making both volatile will require the accesses to them to occur, as viewed outside the program, in the same order as the C semantics. Making one volatile and not the other will not require the accesses to them, as viewed outside the program, to occur in the same order as the C semantics.

    What constitutes an access to a volatile object is implementation-defined. So a C implementation might define it as executing an instruction that accesses it or it might define it as the access request appearing on the memory bus or it might define it in some other way.