Larry Osterman's WebLog

Confessions of an Old Fogey
Blog - Title

The C abstract machine

The C abstract machine

  • Comments 21

I mentioned yesterday that the C/C++ language was defined to operate on an abstract machine.  At the time I didn't know of an online reference to the C or C++ language standard, but a little birdie pointed me to this, which is a draft of the C language specification.

In section 5.1.2.3, you find:

  1. The semantic descriptions in this International Standard describe the behavior of an
    abstract machine in which issues of optimization are irrelevant.
  2. Accessing a volatile object, modifying an object, modifying a file, or calling a function
    that does any of those operations are all side effects, which are changes in the state of
    the execution environment. Evaluation of an expression may produce side effects. At
    certain specified points in the execution sequence called sequence points, all side effects
    of previous evaluations shall be complete and no side effects of subsequent evaluations
    shall have taken place. (A summary of the sequence points is given in annex C.)
  3. In the abstract machine, all expressions are evaluated as specified by the semantics. An
    actual implementation need not evaluate part of an expression if it can deduce that its
    value is not used and that no needed side effects are produced (including any caused by
    calling a function or accessing a volatile object).
  4. When the processing of the abstract machine is interrupted by receipt of a signal, only the
    values of objects as of the previous sequence point may be relied on. Objects that may be
    modified between the previous sequence point and the next sequence point need not have
    received their correct values yet.
  5. The least requirements on a conforming implementation are:
    * At sequence points, volatile objects are stable in the sense that previous accesses are
    complete and subsequent accesses have not yet occurred.
    * 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.19.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.
  6. What constitutes an interactive device is implementation-defined.
  7. More stringent correspondences between abstract and actual semantics may be defined by
    each implementation.

    <The standard goes on and gives examples and clarifications associated with those examples>

 

There are more details scattered throughout the document, but this is the section that defines the machine.  A couple of things that I find quite cool in it:

Section 2 which states that side effects of previous evaluations must be complete at sequence points (for example at the ; at the end of a statement)  What that means is that a compiler is free to reorder operations in any way it chooses but it can't reorder them across sequence points IF the operations have side effects.

So if you have:

*p++ = p[i++];
printf("p is: %p", p++);

the compiler could generate about 4 different versions (depending on what order in which the post increments occur), but the first statement can't affect the printf statement.

Section 3 states that a compiler can reorder code if there are no side-effects.  It also says that the compiler can discard code if it figures it's not used.

 

What's also fascinating is that the standard says nothing about concurrency or multiple execution units - the C language definition defines what happens within ONE execution unit.  It is also explicitly mute about other execution units.  Why is this important?

Consider the following code:

static int myFirstSharedValue, mySecondSharedValue;

myFirstSharedValue = 5;

mySecondSharedValue = 42;

if (mySharedValue == 5)
{
    <do stuff>
}

The compiler could optimize the assignment of mySecondSharedValue to occur AFTER the if test (assuming that nothing in <do stuff> depends on the value of mySecondSharedValue.  The compiler also might reorder the assignment to put the second assignment first!

What's worse, the processor might chose to reorder how the data was saved in memory.  As long as the read of mySecondSharedValue for that execution unit returns the value of 42, it doesn't actually matter when the value of 42 is saved in memory.  It might easily be before the first value is written.  As long as you've only got one thread running, it doesn't matter.

On the other hand, if you have multiple threads that read those values, it would be easy to depend on the write to myFirstSharedValue happening before the write to mySecondSharedValue - after all, that's what the code says, and that's what the language defines.

But the language is defined for the abstract execution unit above, and that might not match the real system.

 

This is why people who try to write correct lock-free programming end up tearing their hair out, and why it's so hard to write lock free code. 

 

Btw, Herb Sutter's been chairing a working group that's chartered to define the abstract machine definition for Windows programs, some of his work can be found here.

  • > So if you have:

    >   *p++ = p[i++];

    >   printf("p is: %p", p++);

    > the compiler could generate about 4 different versions

    No.  If you had a program which obeyed the rules of the standard[*] then the compiler could generate about 4 different versions.  When you have a program which violates the standard, the standard says that results are undefined.  The standard imposes no limits on what kind of generated code can result from your program.

    Look more closely at

    *p++ = p[i++]

    There is a sequence point before that expression starts executing and another sequence point after that expression finishes.  In between, your program modifies p once, which by itself would be allowable.  But also in between, your program accesses the old[**] value of p for a purpose other than computing the new value of p, so you are violating the standard.  Results are undefined.

    [* Some people proposed the phrase "strongly conforming" but it never caught on.  Anyway this condition is more stringent than simply conforming to one implementation, but far less stringent than strictly conforming and producing identical results on all implementations.]

    [** If you wish you can propose an ordering of operations in which your expression accesses the new value there instead of the old value.  However, the compiler doesn't have to choose the same ordering.  Your expression allows code to be generated to access the old value and wipe your hard disk.]

  • Norman, for c# the rules are explicit about ordering of operation, c/c++ are ambiguous.  I probably messed up and picked an unambiguous version, my bad.

  • Two paragraphs from section 6.5 (Expressions):

    ===

    2 Between the previous and next sequence point an object shall have its stored value modified at most once by the evaluation of an expression. Furthermore, the prior value shall be read only to determine the value to be stored.

    3 The grouping of operators and operands is indicated by the syntax. Except as specified later (for the function-call (), &&, ||, ?:, and comma operators), the order of evaluation of subexpressions and the order in which side effects take place are both unspecified.

    ===

    The footnote on paragraph 2 clarifies:

    ===

    This paragraph renders undefined statement expressions such as

    i = ++i + 1;

    a[i++] = i;

    while allowing

    i = i + 1;

    a[i] = i;

    ===

    So there are *allowed differences in the order of expression evaluation* in C, giving you unspecified behaviour (i.e. it's non-deterministic, but you know one of the orders will be used). This is in sharp contrast to the *non-allowed expressions* which violate the C standard and give you undefined behaviour. Undefined behaviour means the execution environment is at liberty to do whatever it likes, including wiping your hard drive, as Norman suggests. If we want to be clear on the difference between unspecified and undefined, we look in the specification:

    ===

    3.4.3

    undefined behavior: behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements

    3.4.4

    unspecified behavior: use of an unspecified value, or other behavior where this International Standard provides two or more possibilities and imposes no further requirements on which is chosen in any instance

    ===

    Here's an example of an expression that's unspecified but not undefined:

    q = 0;

    p = (++q) + (2 * (++q));

    if we treat this as p = x + 2*y, both x and y may be either 1 or 2, as long as q = 2 at the last sequence point.

  • BTW: But do you think that using code like *p++  = p[i++] is good way of writing code? :-) IMHO robust quality code means avoiding unreadable or ambiguous statements; I do prefer splitting that statements into smaller and more readable ones...

  • Two paragraphs from section 6.5 (Expressions):

    ===

    2 Between the previous and next sequence point an object shall have its stored value modified at most once by the evaluation of an expression. Furthermore, the prior value shall be read only to determine the value to be stored.

    3 The grouping of operators and operands is indicated by the syntax. Except as specified later (for the function-call (), &&, ||, ?:, and comma operators), the order of evaluation of subexpressions and the order in which side effects take place are both unspecified.

    ===

    The footnote on paragraph 2 clarifies:

    ===

    This paragraph renders undefined statement expressions such as

    i = ++i + 1;

    a[i++] = i;

    while allowing

    i = i + 1;

    a[i] = i;

    ===

    So there are *allowed differences in the order of expression evaluation* in C, giving you unspecified behaviour (i.e. it's non-deterministic, but you know one of the orders will be used). This is in sharp contrast to the *non-allowed expressions* which violate the C standard and give you undefined behaviour. Undefined behaviour means the execution environment is at liberty to do whatever it likes, including wiping your hard drive, as Norman suggests. If we want to be clear on the difference between unspecified and undefined, we look in the specification:

    ===

    3.4.3

    undefined behavior: behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements

    3.4.4

    unspecified behavior: use of an unspecified value, or other behavior where this International Standard provides two or more possibilities and imposes no further requirements on which is chosen in any instance

    ===

    Here's an example of an expression that's unspecified but not undefined:

    q = 0;

    p = (++q) + (2 * q);

    if we treat this as p = x + 2*y, x is always 1, but y may be either 0 or 1, as long as q = 1 at the last sequence point! Therefore, p may non-deterministically be either 1 or 3, but the compiler is not at liberty to assign p another value at the last sequence point, nor indeed to wipe your hard drive (which is a relief!).

  • My memory is fuzzy, but I thought assignment was also a sequence point and, since it was right associative, it would always evaluate the right side first.  Thus, despite being cryptic, Larry's example would be well-defined.

    *p++ = p[i++];

    The rhs (p[i++]) would be fully evaluated (including the side effect), THEN the lhs (*p++), THEN the assignment.

    Perhaps I'm suffering from false memories and wishful thinking.

    Aside from that, isn't that volatile storage class supposed to be the Band-Aid that keeps all this working in a multi-threaded environment?  If you tag myFirstSharedValue and mySecondSharedValue with volatile, doesn't that solve the threading problems that an aggressive optimizer might have introduced?

  • If that were true, then a[i++] = i (one of the examples of an undefined expression from the spec which I quoted above) would be well-defined, and it's not!

    To go back to the specification once more:

    ===

    Section 6.5.16 (Assignment operators):

    Semantics

    3 An assignment operator stores a value in the object designated by the left operand. An assignment expression has the value of the left operand after the assignment, but is not an

    lvalue. The type of an assignment expression is the type of the left operand unless the left operand has qualified type, in which case it is the unqualified version of the type of the left operand. The side effect of updating the stored value of the left operand shall occur between the previous and the next sequence point.

    4 The order of evaluation of the operands is unspecified. If an attempt is made to modify the result of an assignment operator or to access it after the next sequence point, the behavior is undefined.

    ===

    So all you know from paragraph 3 is that the value of the lhs of the assignment will occur between two sequence points. There is no implicit sequence point in the assignment operator.

    On the second point, volatile only specifies semantics of a variable relative to the current execution unit, i.e. that reads and writes to the variable must occur in a certain order relative to other observable behaviour for the current execution unit. It makes no specification on how this is seen by other execution units (if any). Therefore, other execution units may legally see the updates to volatile variables in a different order than the order your execution unit sees them (which you are explicitly controlling using volatile).

    This is part of the reason that VS2005 was updated to give volatile acquire/release semantics, as volatile then gives you the "expected" behaviour w.r.t. other threads:

    http://msdn2.microsoft.com/en-us/library/12a04hfd(VS.80).aspx

    It's also the reason that Herb Sutter is chairing a group to standardise the memory model for Windows platforms, so that developers can have a consistent playing field when trying to implement corrent multi-threaded code on Windows, because the memory model you get for native code on Windows at the moment is basically dependent on the underlying architecture, making it difficult to write consistently correct code.

  • Sys64738: I don't think anyone reading (or writing, for that matter) this blog would consider writing such code.

  • So does this type of problem go away when you use a functional programming style?

    I know very little about FP, but have heard that it makes concurrency "easy" to deal with.  Can somebody in the know make some comments on this?  I'd be interested in what you have to say.

  • Jonathan, I'm suspect that the problems are orthagonal.  In many procedural languages (C# for example), the concept of specified but not defined or unspecified but defined don't happen, for functional languages, I suspect there are languages that have defined but not specified behaviors.

  • Thursday, May 17, 2007 9:59 AM by Andrew Rogers

    > Furthermore, the prior value shall be read only to determine

    > the value to be stored.

    Your quotation is correct.

    > Here's an example of an expression that's unspecified but not undefined:

    > p = (++q) + (2 * q);

    No.  The compiler is free to read the prior value of q for the purpose of computing 2*q and computing the new value of p, before the compiler writes the new value of q as a side effect of computing ++q.  You correctly quoted why this results in undefined behaviour.

  • Norman,

    You're right; I should have been more careful. To demonstrate the unspecified nature of subexpression evaulation giving rise to non-deterministic behaviour, I believe we can use a function call and so not run foul of the rule in 6.5 p2, as functions have a sequence point before the call:

    ===

    Section 6.5.2.2 (Function calls):

    Semantics

    10 The order of evaluation of the function designator, the actual arguments, and subexpressions within the actual arguments is unspecified, but there is a sequence point before the actual call.

    ===

    static int q = 0;

    int inc_q() {

       return ++q;

    }

    int p = (inc_q()) + (2 * q);

    Is my toy example right now? :-)

  • Friday, May 18, 2007 2:21 AM by Andrew Rogers

    > Is my toy example right now? :-)

    That's about the point where I stopped trying to interpret the standard and returned to practical programming  ^_^

  • > Is my toy example right now? :-)

    OK, yes I think it's right.  But my previous answer to this question was better  ^_^

  • *sigh* So many hairs to split, so little time...

    Seriously: I consider this knowledge important when reading/debugging existing code, not writing new code. Code whose function depends on this, even if correct, is not code that I want to maintain or debug.

Page 1 of 2 (21 items) 12