Question About Sequence Points and Interrupt/Thread Safety

Stephen Sprunk wrote:
> Hans-Bernhard Bröker wrote:
>> Stephen Sprunk wrote:
>>> The former quote says that compilers can't move volatile accesses 
>>> _across_ a sequence point;
>> [...]
>>> bar(), or move code before foo() to after bar() or vice versa, if it 
>>> could prove that doing so wouldn't violate the as-if rule.
>>
>> Ehm, no.  You're overlooking that by moving code down from before 
>> foo() to after bar(), you're also moving your volatile accesses up, 
>> across the sequence point(s) in that code, which would violate the 
>> first statement above.
>>
>> It cuts both ways --- whenever you talking about "moving" code, what 
>> actually happens is that operations are swapped, and that means you 
>> move each across the other.
> 
> Hmm.  I think that you're right in theory, but is it possible that a 
> conforming program could tell the difference?  Doesn't the as-if rule 
> still apply to the non-volatile parts of the code?  Or does a single 
> volatile access break the as-if rule even for non-volatile operations?
> 
> I've seen compilers do what I described (from studying the asm output), 
> and nobody seems to complain about it.  Mixing volatile and non-volatile 
> operations is pretty unpredictable in practice, so I have always avoided 
> that entirely rather than try to figure out exactly what the Standard 
> guarantees (which doesn't appear to be much when it comes to volatile 
> variables).
> 

You are correct - the "as-if" rule lets the compiler re-order 
non-volatile accesses as it wants.  It is only volatile accesses that 
must remain strictly in order.  However, if the compiler does not know 
the details of a function, then any function call must be ordered as 
though it were a volatile access, since the compiler does not know that 
it does not contain volatile accesses.  So in your example, it could not 
normally move the foo() or bar() calls above or below the volatile sum.

If the definitions of foo() and bar() are known to the compiler (or it 
knows other details, such as if they are declared with the gcc "const" 
attribute), so that the compiler knows it is safe, it can move them around.

Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:

> Jack Klein <jackklein@spamcop.net> writes:
> > The real crime is the fact there's a paper showing a number of
> > compilers that actually have errors in their implementation of
> > volatile that can be detected by a strictly conforming program.  See:
> >
> > http://www.cs.utah.edu/~regehr/papers/emsoft08-preprint.pdf
> 
> I'm feeling a bit dense currently. I'm having issues with the 
> following:
>[snip]
> """
> For example, the
> following code illustrates a common mistake in which a volatile
> variable is used to signal a condition about a non-volatile data struc-
> ture, perhaps to another thread:
> 
>    volatile int buffer_ready;
>    char buffer[BUF_SIZE];
>    void buffer_init() {
>       int i;
>       for (i=0; i<BUF_SIZE; i++)
>         buffer[i] = 0;
>       buffer_ready = 1;
>    }
> 
>    The for-loop does not access any volatile locations, nor does it
> perform any side-effecting operations. Therefore, the compiler is
> free to move the loop below the store to buffer_ready, defeating
> the developer's intent.
> """

This part of the paper is wrong.  The loop does perform
side-effecting operations, both the increments of i and the
stores into buffer[i], and these must be done before the
(volatile) assignment into buffer_ready.

Whether the consequences of using (volatile) in this way
qualify as a mistake depends on other factors, notably the
implementation-defined rule for what constitutes an access
to a volatile-qualified variable.  Perhaps what the paper
means to say is that assuming this code will always work
is a mistake, and that is in fact correct;  but whether
it must work is implementation dependent, so on some
implementations it could be just fine.

More about volatile shortly...

Stephen Sprunk <stephen@sprunk.org> writes:

> Hans-Bernhard Br&ouml;ker wrote:
> > Stephen Sprunk wrote:
> >> The former quote says that compilers can't move volatile accesses 
> >> _across_ a sequence point;
> > [...]
> >> bar(), or move code before foo() to after bar() or vice versa, if it 
> >> could prove that doing so wouldn't violate the as-if rule.
> > 
> > Ehm, no.  You're overlooking that by moving code down from before foo() 
> > to after bar(), you're also moving your volatile accesses up, across the 
> > sequence point(s) in that code, which would violate the first statement 
> > above.
> > 
> > It cuts both ways --- whenever you talking about "moving" code, what 
> > actually happens is that operations are swapped, and that means you move 
> > each across the other.
> 
> Hmm.  I think that you're right in theory, but is it possible that a 
> conforming program could tell the difference?  Doesn't the as-if rule 
> still apply to the non-volatile parts of the code?  Or does a single 
> volatile access break the as-if rule even for non-volatile operations?
> 
> I've seen compilers do what I described (from studying the asm output), 
> and nobody seems to complain about it.  Mixing volatile and non-volatile 
> operations is pretty unpredictable in practice, so I have always avoided 
> that entirely rather than try to figure out exactly what the Standard 
> guarantees (which doesn't appear to be much when it comes to volatile 
> variables).

The semantics of volatile are confusing, or at least expressed in
a confusing way.  What many people think are the rules for how
volatiles are accessed and what the Standard says about how
volatile-qualified objects must be treated are quite a bit
different from each other.

In the examples below, the variables v, v1, v2, ..., are
volatile, and other variables aren't.  To keep things simple all
the arithmetic types are (unsigned int).

First simple example:

   x = a + b + c + v;

The first rule for volatile is captured in a single sentence
in 6.7.3p6:

    Therefore any expression referring to such an object [i.e.,
    with volatile-qualified type] shall be evaluated strictly
    according to the rules of the abstract machine, as described
    in 5.1.2.3.

The full expression assigning to x is an expression referring to an
object with volatile-qualified type.  Therefore that expression,
the /entire/ expression, must be evaluated strictly according to
the rules of the abstract machine.  The sums must be formed in the
right order;  even though addition for (unsigned int) commutes,
the additions must be done as (((a + b) + c) + v), and not, for
example, as ((a + (b + c)) + v).  Furthermore, the sum (a+b)
must be performed, even if that value happens to be lying around
conveniently in a register somewhere.  These consequences follow
because of the requirement than any volatile-referring expression
be evaluated /strictly/ according to the rules of the abstract
machine.

Now let's consider a multi-statement (and so multi-sequence-point)
example:

    foo();
    x = a + b + c + v;
    bas();

To lend some concreteness, foo() increments a global variable
foo_count, and bas increments a global varible bas_count.
Neither foo_count nor bas_count is volatile.  The functions
foo() and bas() don't either read or write x, a, b, c, or v.

Question:  can any part of the assignment expression (statement)
be done before calling foo() or after calling bas()?

Answer:  No.

Reason:  The expression in question must be evaluated strictly
according to the rules of the abstract machine, as described in
5.1.2.3.  In particular, there is 5.1.2.3 p 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,(11) 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.

The assignment expression must be evaluated strictly according to
this rule.  As it follows a sequence point, all side effects of
evalutions before that sequence point (namely, the call to foo())
must be complete.  It has a sequence point at its end;  all side
effects of evaluations after that sequence point (namely, the call
to bas()) must not have taken place.  The act of calling foo()
(or bas()) is itself a side effect, since an object is modified
in its function body.

These kinds of consequences may seem counter-intuitive.  Certainly
they are not what many people expect.  But the stated semantics for
volatile, coupled with the abstract machine description in 5.1.2.3p2,
impose very strict requirements for how much latitude is available
for optimizing around expressions that access volatile objects.

Note also:  apparently some of the people who are confused about
volatile are compiler writers;  hence, we have the results shown in

  http://www.cs.utah.edu/~regehr/papers/emsoft08-preprint.pdf

David Brown <david.brown@hesbynett.removethisbit.no> writes:

> Stephen Sprunk wrote:
> > Hans-Bernhard Br&ouml;ker wrote:
> >> Stephen Sprunk wrote:
> >>> The former quote says that compilers can't move volatile accesses 
> >>> _across_ a sequence point;
> >> [...]
> >>> bar(), or move code before foo() to after bar() or vice versa, if it 
> >>> could prove that doing so wouldn't violate the as-if rule.
> >>
> >> Ehm, no.  You're overlooking that by moving code down from before 
> >> foo() to after bar(), you're also moving your volatile accesses up, 
> >> across the sequence point(s) in that code, which would violate the 
> >> first statement above.
> >>
> >> It cuts both ways --- whenever you talking about "moving" code, what 
> >> actually happens is that operations are swapped, and that means you 
> >> move each across the other.
> > 
> > Hmm.  I think that you're right in theory, but is it possible that a 
> > conforming program could tell the difference?  Doesn't the as-if rule 
> > still apply to the non-volatile parts of the code?  Or does a single 
> > volatile access break the as-if rule even for non-volatile operations?
> > 
> > I've seen compilers do what I described (from studying the asm output), 
> > and nobody seems to complain about it.  Mixing volatile and non-volatile 
> > operations is pretty unpredictable in practice, so I have always avoided 
> > that entirely rather than try to figure out exactly what the Standard 
> > guarantees (which doesn't appear to be much when it comes to volatile 
> > variables).
> > 
> 
> You are correct - the "as-if" rule lets the compiler re-order 
> non-volatile accesses as it wants.  It is only volatile accesses that 
> must remain strictly in order.  However, if the compiler does not know 
> the details of a function, then any function call must be ordered as 
> though it were a volatile access, since the compiler does not know that 
> it does not contain volatile accesses.  So in your example, it could not 
> normally move the foo() or bar() calls above or below the volatile sum.
> 
> If the definitions of foo() and bar() are known to the compiler (or it 
> knows other details, such as if they are declared with the gcc "const" 
> attribute), so that the compiler knows it is safe, it can move them around.

No, this is a misreading of the semantics of volatile as
required by the description in 5.1.2.3 of how the abstract
machine operates.  Please see my last response in this
thread.

Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:

> Stephen Sprunk <stephen@sprunk.org> writes:
> > Phil Carmody wrote:
> >> I'm feeling a bit dense currently. I'm having issues with the
> >> following:
> >> """
> >> 2. WHAT DOES VOLATILE MEAN?
> >> ...
> >>   A compiler may not move accesses to volatile variables across
> >> sequence points.[1] ...
> >> No guarantees are made about the atomicity of any given volatile
> >> access, about the ordering of multiple volatile
> >> accesses between two consecutive sequence points, or about the
> >> ordering of volatile and non-volatile accesses. """
> >>
> >> That final clause seems to contradict the initial footnoted clause,
> >> on the presumption that the non-volatile accesses begin with, end
> >> with, or contain, a sequence point.
> >
> > The former quote says that compilers can't move volatile accesses
> > _across_ a sequence point; the latter quote says that the order of
> > volatile accesses _between_ two sequence points is undefined.  The two
> > do not contradict each other.
> >
> > For instance, consider the following:
> >
> > volatile int a, b, c;
> > /* other code */
> > foo();
> > a += b + c;
> > bar();
> >
> > The compiler cannot move the volatile accesses before foo() or after
> > bar(), 
> 
> I'm happy with that. A nice clear absolute. No wondering about 'as if's.
> 
> > but it _can_ choose in what order to read a, b, and c.
> 
> Perfectly happy with that too, wouldn't want it any other way.
> 
> > However, it can also choose to move other (non-volatile) code between
> > foo() and bar(), or move code before foo() to after bar() or vice versa
> 
> What's so special about function calls? Why wouldn't a for loop,
> or even simple assignments, contain sequence points that the 
> volatile accesses couldn't be moved past? What property do foo()
> and bar() have that those other things with sequence points don't 
> have?

Sequence points are just a kind of convenient reference
point.  Sequence points can be identified at the level
of source code, and perhaps they "exist" in some sense
in the abstract machine, but they don't have any meaning
during an actual execution.  The key thing is side effects;
when starting to evaluate

   a += b + c;

all the side effects of previous evaluations must be complete
(and not just as-if!), and presumably the call to foo()
qualifies because its body has a side effect of its own.
The rule about side effects also includes assignment,
and for() loops, assuming of course that there is incrementing
or something else going on in the for() loop that qualifies
as a side effect.

Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:

> Stephen Sprunk <stephen@sprunk.org> writes:
> > Phil Carmody wrote:
> >> What's so special about function calls? Why wouldn't a for loop,
> >> or even simple assignments, contain sequence points that the
> >> volatile accesses couldn't be moved past? What property do foo()
> >> and bar() have that those other things with sequence points don't
> >> have?
> >
> > Any sequence point suffices; the only magical property of function
> > calls in my example is that they're easy to refer to by name.  It's
> > hard to refer to particular semicolons because they all look the
> > same...

Minor correction:  any side effect before a previous sequence
point suffices.  Presuming the definitions of foo() and bas()
have side effects in their bodies, then calls to foo() or
bas() also count as side effects.

> 
> So you think the document's wrong?

Yes.  On a broad scale it's right, but on the specific
explanation for this case it's wrong.

Tim Rentsch <txr@alumnus.caltech.edu> writes:
> Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:
>> Jack Klein <jackklein@spamcop.net> writes:
>> > http://www.cs.utah.edu/~regehr/papers/emsoft08-preprint.pdf
>> 
>> I'm feeling a bit dense currently. I'm having issues with the ...
>
> This part of the paper is wrong.  

Thank you thank you thank you Tim. So I'm not going senile.
Or if I am, I'm not alone.

> More about volatile shortly...

Looking forward to it. I'll probably have to wait until Sunday 
though...

Cheers,
Phil
-- 
I tried the Vista speech recognition by running the tutorial. I was 
amazed, it was awesome, recognised every word I said. Then I said the 
wrong word ... and it typed the right one. It was actually just 
detecting a sound and printing the expected word! -- pbhj on /.

Tim Rentsch wrote:
> 

<snip to save space>

> In the examples below, the variables v, v1, v2, ..., are
> volatile, and other variables aren't.  To keep things simple all
> the arithmetic types are (unsigned int).
> 
> First simple example:
> 
>    x = a + b + c + v;
> 
> The first rule for volatile is captured in a single sentence
> in 6.7.3p6:
> 
>     Therefore any expression referring to such an object [i.e.,
>     with volatile-qualified type] shall be evaluated strictly
>     according to the rules of the abstract machine, as described
>     in 5.1.2.3.
> 
> The full expression assigning to x is an expression referring to an
> object with volatile-qualified type.  Therefore that expression,
> the /entire/ expression, must be evaluated strictly according to
> the rules of the abstract machine.  The sums must be formed in the
> right order;  even though addition for (unsigned int) commutes,
> the additions must be done as (((a + b) + c) + v), and not, for
> example, as ((a + (b + c)) + v).  Furthermore, the sum (a+b)
> must be performed, even if that value happens to be lying around
> conveniently in a register somewhere.  These consequences follow
> because of the requirement than any volatile-referring expression
> be evaluated /strictly/ according to the rules of the abstract
> machine.
> 
> Now let's consider a multi-statement (and so multi-sequence-point)
> example:
> 
>     foo();
>     x = a + b + c + v;
>     bas();
> 
> To lend some concreteness, foo() increments a global variable
> foo_count, and bas increments a global varible bas_count.
> Neither foo_count nor bas_count is volatile.  The functions
> foo() and bas() don't either read or write x, a, b, c, or v.
> 
> Question:  can any part of the assignment expression (statement)
> be done before calling foo() or after calling bas()?
> 
> Answer:  No.
> 
<snip to save space>
> 
> These kinds of consequences may seem counter-intuitive.  Certainly
> they are not what many people expect.  But the stated semantics for
> volatile, coupled with the abstract machine description in 5.1.2.3p2,
> impose very strict requirements for how much latitude is available
> for optimizing around expressions that access volatile objects.
> 
> Note also:  apparently some of the people who are confused about
> volatile are compiler writers;  hence, we have the results shown in
> 
>   http://www.cs.utah.edu/~regehr/papers/emsoft08-preprint.pdf
> 

That is very interesting - I haven't read through the standards quite 
like that.  Your interpretation may well be the correct one according to 
the standards (I don't know the priority of these rules and the "as-if" 
rule), but I think it is slightly different from what users and compiler 
writers expect, and slightly different from what they *want*.  In 
particular, no one wants or expects the compiler to treat the "a + b + 
c" part of your expression in any special way just because there is a "+ 
v" added.  They want and expect "v" to be read as a volatile access, but 
"a + b + c" should be subject to common expression and other optimisations.

As for whether code (in particular, non-volatile loads and stores) 
should be moveable around the volatile accesses, there are two camps - 
those who think it should not be possible (if your interpretation is 
correct, this is the standard's viewpoint), and those who think it is 
possible (and arguably desirable).  The fact is, real compilers *do* 
move code around like that - if you want your code to run correctly, you 
have to assume that such re-ordering is possible.

Just for fun, I compiled this code with a couple of versions of gcc and 
different optimisation flags:

typedef unsigned char uint8_t;

extern volatile uint8_t v, v1, v2, v3;
extern uint8_t x, a, b, c;
extern uint8_t foo_count, bas_count;

void foo(void) {
	foo_count++;
}

void bas(void) {
	foo_count--;
}

void test1(void) {
	v1 = a + b;
	foo();
	x = a + b + c + v;
	bas();
	v2 = a + b + c;
	x += 1;
}


With avr-gcc 4.2 and 4.3, -Os optimisation, test1 is implemented as 
though it were:

void test1(void) {
	uint8_t r24, r25;		// 8-bit registers
	r24 = b;
	r25 = a;
	r24 += r25;		// a + b
	v1 = r24;		// volatile store v1 = a + b
	r25 = c;
	r25 += r24;		// a + b + c
	r24 = v;		// volatile load v
	v2 = r25;		// volatile store v2 = a + b + c
	r24 += 1;		// v + 1
	r24 += r25		// v + 1 + a + b + c
	x = r24;		// Store x = a + b + c + v + 1
}

As you can see, calls to foo() and bas() have been eliminated, and there 
is a lot of re-use of the partial calculations.  This is, in my opinion, 
correct code - the volatile accesses are correct, and in the correct 
order, and the rest of the code runs *as if* it were a direct 
translation.  The generated code is also as small and fast as it 
possibly could be on the AVR.


The biggest problem with "volatile" in C is that the standards are 
vague, difficult to understand, and probably inconsistent.  This will 
always lead to misunderstandings and disagreements about "volatile". 
comp.lang.c frequenters will often be interested in exactly what the 
standards say, while comp.arch.embedded frequenters will be more 
interested in what real-life compilers actually *do* (we are used not 
not-quite-standard compilers).

	

David Brown <david@westcontrol.removethisbit.com> writes:

> Tim Rentsch wrote:
> > [SNIP]
> [SNIP]

Sometime soon I'd like to post a more complete response
that doesn't ignore this snipped portion, talking about
the semantics of volatile.  Right now the response will
be just to the paragraph below.

 
> The biggest problem with "volatile" in C is that the standards are 
> vague, difficult to understand, and probably inconsistent.  This will 
> always lead to misunderstandings and disagreements about "volatile". 
> comp.lang.c frequenters will often be interested in exactly what the 
> standards say, while comp.arch.embedded frequenters will be more 
> interested in what real-life compilers actually *do* (we are used not 
> not-quite-standard compilers).

This makes perfect sense, given both the problems of how
volatile is described in the Standard, and what the priorities
are of the two groups.  Folks in comp.arch.embedded aren't
going to care very much what compilers are supposed to do,
if most compilers don't actually do what they're supposed to
do -- and moreso if what they're supposed to do isn't clear.

However, it is in the interests of both groups -- in fact
maybe even more in the interests of comp.arch.embedded than it
is of comp.lang.c -- that what 'volatile' is supposed to do be
well-understood, and that such understanding be shared by a
broad community, in particular including lots of compiler
people who produce the different implementations, and also
including people like those in comp.arch.embedded who actually
use 'volatile' in their C code.  I'm much more of a
comp.lang.c person than a comp.arch.embedded person, but the
cross-pollination that's happened in this thread has been (at
least IMO) a real boon, and I would like to see that continue
during a further discussion of the semantics of volatile.

Also, on a personal note, a "thank you" to David Brown for
taking the time to write/compile the example code that uses
volatile to see what the compilers actually do with it.

Hoped-for followup discussing the semantics of volatile:  as
soon as I can get to it, but realistically that won't be
before next week.

Tim Rentsch wrote:
> David Brown <david@westcontrol.removethisbit.com> writes:
> 
>> Tim Rentsch wrote:
>>> [SNIP]
>> [SNIP]
> 
> Sometime soon I'd like to post a more complete response
> that doesn't ignore this snipped portion, talking about
> the semantics of volatile.  Right now the response will
> be just to the paragraph below.
> 
>  
>> The biggest problem with "volatile" in C is that the standards are 
>> vague, difficult to understand, and probably inconsistent.  This will 
>> always lead to misunderstandings and disagreements about "volatile". 
>> comp.lang.c frequenters will often be interested in exactly what the 
>> standards say, while comp.arch.embedded frequenters will be more 
>> interested in what real-life compilers actually *do* (we are used not 
>> not-quite-standard compilers).
> 
> This makes perfect sense, given both the problems of how
> volatile is described in the Standard, and what the priorities
> are of the two groups.  Folks in comp.arch.embedded aren't
> going to care very much what compilers are supposed to do,
> if most compilers don't actually do what they're supposed to
> do -- and moreso if what they're supposed to do isn't clear.
> 
> However, it is in the interests of both groups -- in fact
> maybe even more in the interests of comp.arch.embedded than it
> is of comp.lang.c -- that what 'volatile' is supposed to do be
> well-understood, and that such understanding be shared by a
> broad community, in particular including lots of compiler
> people who produce the different implementations, and also
> including people like those in comp.arch.embedded who actually
> use 'volatile' in their C code.  I'm much more of a
> comp.lang.c person than a comp.arch.embedded person, but the
> cross-pollination that's happened in this thread has been (at
> least IMO) a real boon, and I would like to see that continue
> during a further discussion of the semantics of volatile.
> 
> Also, on a personal note, a "thank you" to David Brown for
> taking the time to write/compile the example code that uses
> volatile to see what the compilers actually do with it.
> 
> Hoped-for followup discussing the semantics of volatile:  as
> soon as I can get to it, but realistically that won't be
> before next week.

I'll look forward to that.  I too enjoy a bit of cross-posting between 
these two groups - comp.lang.c is mostly a bit too theoretical for my 
tastes, but areas such as "volatile" are definitely in an overlap area, 
and it's good to get input from a different viewpoint.