Question About Sequence Points and Interrupt/Thread Safety

Tim Rentsch <txr@alumnus.caltech.edu> wrote in
news:kfntz6gg3vu.fsf@alumnus.caltech.edu: 

> 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.

I disagree with this analysis.  I think you're ascribing too pandemic a 
meaning to the phrase 'any expression referring to such an object...'.  

As you say, the language syntax requires that the interpretation of the 
expression is "(((a + b) + c) + v)".  However, decomposing that further 
shows that in the outermost expression, 'v' is being added to the result 
of another expression '((a + b) + c)'.  This latter (sub-)expression 
references no volatile object and hence could be commuted as "(a + (b + 
c))" or could use an already computed sub-expression like (a + b).  Once 
the '((a + b) + c)' is evaluated, the outermost expression (which *does* 
reference a volatile object) can then be evaluated 'strictly according 
to the rules of the abstract machine'.  

In your explanation, you reference the term 'full expression'.  But the 
term 'full expression' is explicitly defined in the standard (6.8p4): "A 
full expression is an expression that is not part of another expression 
or declarator. [...]"  And it seems to have exactly the meaning you are 
arguing for here.  But if 'full expression' was indeed what was intended 
in 6.7.3p6 as you argue, then wouldn't the well-defined term have been 
used there?

GH

On Feb 26, 3:55=A0pm, Tim Rentsch <t...@alumnus.caltech.edu> wrote:
> This part of the paper is wrong. =A0The 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.

No-- accesses to global variables are not side effecting operations.

The definition of side effect in the C standard differs from the
colloquial computer science definition:

"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."

John Regehr

> "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."

Hmm, nevermind... probably I am not reading "object" correctly!

Even so, as people have pointed out, compilers move these accesses
around pretty freely. For example:

volatile int Ready;
int Message[100];
void foo (int i)
{
  Message[i / 10] = 42;
  Ready = 1;
}

regehr@john-home:~$ gcc -O3 -S -o - ready.c -fomit-frame-pointer
.globl foo
	.type	foo, @function
foo:
	movl	4(%esp), %ecx
	movl	$1717986919, %edx
	movl	$1, Ready
	movl	%ecx, %eax
	imull	%edx
	sarl	$31, %ecx
	sarl	$2, %edx
	subl	%ecx, %edx
	movl	$42, Message(,%edx,4)
	ret

Here the store into the non-volatile array has been moved below the
volatile store by gcc-4.2 for x86. The latest (pre-4.4.0) version of
gcc does the same thing, as does the current Intel CC.  The current
version of llvm-gcc does not, it stores to the flag last.  This code
example is from Arch Robison's blog.

John Regehr

On Feb 24, 11:51=A0pm, "Jujitsu Lizard" <jujitsu.liz...@gmail.com>
wrote:
> That is the single most depressing paper I've read recently.

Perhaps amusingly, when I talk to compiler developers about volatile
bugs they are not at all surprised.  Of course optimizers, like any
other large and complex programs, contain bugs.  Embedded developers
tend to be more surprised and depressed (my gut reaction as well).

To make things worse we have also found regular old wrong-code errors
in every compiler that we've tested, including a number of embedded
compilers.  This is for integer C programs: no pointers, no FP, not
even any structs or unions.

One example: the gcc that shipped with Ubuntu Hardy for x86
miscompiled this function so that it returned 1 instead of 0:

int foo (void) {
  signed char l_11 =3D 1;
  unsigned char l_12 =3D -1;
  return (l_11 > l_12);
}

The base version of gcc, 4.2.3, did not mess this up, but the Ubuntu
people applied about 5 MB of patches in the released compiler and one
of these broke it badly.  They have since pushed out an update that
fixes this.  Did this bug put any security vulnerabilities into
Ubuntu?  Wish I knew how to answer that :).

Broadly speaking, embedded compilers seem to be worse than, for
example, gcc for x86, in the sense that they produce wrong code for
broader classes of inputs.  It is hard to say what is going on, but I
suspect that the cross-product of compiler vendors * target platforms
results in a situation where each individual compiler cannot be tested
nearly as thoroughly as a typical gcc for x86 release.

John Regehr

On Feb 26, 3:55=A0pm, Tim Rentsch <t...@alumnus.caltech.edu> wrote:

> This part of the paper is wrong. =A0The 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.

Hi!  I am one of the authors of the paper in question.

I think that the cited portion of the paper is not wrong.

As described in other posts in this thread, Section 5.1.2.3 paragraph
2 describes a semantics in which "modifying an object" --- any object
--- is a side-effect.  Side-effects are complete at sequence points.

But it is important to remember that this is a description of the
abstract semantics, and the specification distinguishes between the
abstract semantics and the semantics that are allowed by conforming
implementations.

Paragraph 5 in the same section describes the minimum requirements for
a conforming implementation, which are essentially that only volatile
objects must be stable at sequence points.  Paragraphs 8 and 9 provide
further discussion, which help to clarify that the abstract semantics
and the semantics of a conforming implementation may be different.

If I have missed some detail here, please let me know!

Thanks ---

Eric.

PS --- Please direct any email replies to eeide@cs.utah.edu, not the
addess from which this message was posted.

John Regehr wrote:
> On Feb 24, 11:51 pm, "Jujitsu Lizard" <jujitsu.liz...@gmail.com>
> wrote:
>> That is the single most depressing paper I've read recently.
> 
> Perhaps amusingly, when I talk to compiler developers about volatile
> bugs they are not at all surprised.  Of course optimizers, like any
> other large and complex programs, contain bugs.  Embedded developers
> tend to be more surprised and depressed (my gut reaction as well).
> 
> To make things worse we have also found regular old wrong-code errors
> in every compiler that we've tested, including a number of embedded
> compilers.  This is for integer C programs: no pointers, no FP, not
> even any structs or unions.
> 
> One example: the gcc that shipped with Ubuntu Hardy for x86
> miscompiled this function so that it returned 1 instead of 0:
> 
> int foo (void) {
>   signed char l_11 = 1;
>   unsigned char l_12 = -1;
>   return (l_11 > l_12);
> }
> 
> The base version of gcc, 4.2.3, did not mess this up, but the Ubuntu
> people applied about 5 MB of patches in the released compiler and one
> of these broke it badly.  They have since pushed out an update that
> fixes this.  Did this bug put any security vulnerabilities into
> Ubuntu?  Wish I knew how to answer that :).
> 

There should not be any security vulnerabilities due to such a bug - the 
C code is clearly incorrect code, even though it is legal C, and 
security-critical code is often better checked than application-level 
code.  Of course, *should not be* does not mean the same as *are not* ! 
  Real bugs in heavily used features of heavily used compilers are rare, 
but not unknown - that's one reason you need to test software well 
(especially if it is critical to security or reliability).

> Broadly speaking, embedded compilers seem to be worse than, for
> example, gcc for x86, in the sense that they produce wrong code for
> broader classes of inputs.  It is hard to say what is going on, but I
> suspect that the cross-product of compiler vendors * target platforms
> results in a situation where each individual compiler cannot be tested
> nearly as thoroughly as a typical gcc for x86 release.
> 

I think that is a perfectly good explanation.  Tools that are heavily 
used are going to have fewer bugs (at least, fewer bugs that are easily 
triggered) since there are more people using them.  They also tend to 
have more resources in development.  This is somewhat countered by the 
complexity of the software, which is often higher than for smaller 
tools.  Certainly if you look at embedded compilers, the bugs are 
generally in the target-specific backends rather than the more generic 
front-ends.

Gil Hamilton <gil_hamilton@hotmail.com> writes:
> Tim Rentsch <txr@alumnus.caltech.edu> wrote in
> news:kfntz6gg3vu.fsf@alumnus.caltech.edu: 
>
>> 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.
[...]
>
> I disagree with this analysis.  I think you're ascribing too pandemic a 
> meaning to the phrase 'any expression referring to such an object...'.  

I don't.

> As you say, the language syntax requires that the interpretation of the 
> expression is "(((a + b) + c) + v)".  However, decomposing that further 
> shows that in the outermost expression, 'v' is being added to the result 
> of another expression '((a + b) + c)'.  This latter (sub-)expression 
> references no volatile object and hence could be commuted as "(a + (b + 
> c))" or could use an already computed sub-expression like (a + b).  Once 
> the '((a + b) + c)' is evaluated, the outermost expression (which *does* 
> reference a volatile object) can then be evaluated 'strictly according 
> to the rules of the abstract machine'.  

The standard says that "*any expression referring to such an
object shall be evaluated strictly according to the rules of the
abstract machine".  v is such an object.  ``x = a + b + c + v''
is an "expression referring to such an object".  Therefore
``x = a + b + c + v'' must be evaluated strictly according to the
rules of the abstract machine.  The statement in the standard, if
taken literally (and I don't know how else one could reasonably take
it) applies to the expressions ``v'', ``a + b + c + v'', and
``x = a + b + c + v''.

It's entirely possible that this wasn't the intent of the authors of
the standard.  In some cases, where the literal wording of the
standard doesn't express the obvious intent, it can be reasonable to
use a loose interpretation, but I don't see how to construct such an
interpretation in this case, at least not in a way that everyone would
agree on.

> In your explanation, you reference the term 'full expression'.  But the 
> term 'full expression' is explicitly defined in the standard (6.8p4): "A 
> full expression is an expression that is not part of another expression 
> or declarator. [...]"  And it seems to have exactly the meaning you are 
> arguing for here.  But if 'full expression' was indeed what was intended 
> in 6.7.3p6 as you argue, then wouldn't the well-defined term have been 
> used there?

It doesn't need to be.  A full expression is an expression.  If the
standard refers to "any expression", it must be referring to full
expressions as well as to subexpressions.

-- 
Keith Thompson (The_Other_Keith) kst@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

David Brown wrote:
> John Regehr wrote:

>> int foo (void) {
>>   signed char l_11 = 1;
>>   unsigned char l_12 = -1;
>>   return (l_11 > l_12);
>> }

> There should not be any security vulnerabilities due to such a bug - the 
> C code is clearly incorrect code, 

No, it's not.  It's questionable, but way short of "clearly incorrect". 
  As far as minimal examples checking for a possible compiler bug go, I 
find it to be just about perfect.

Hans-Bernhard Br�ker wrote:
> David Brown wrote:
>> John Regehr wrote:
> 
>>> int foo (void) {
>>>   signed char l_11 = 1;
>>>   unsigned char l_12 = -1;
>>>   return (l_11 > l_12);
>>> }
> 
>> There should not be any security vulnerabilities due to such a bug - 
>> the C code is clearly incorrect code, 
> 
> No, it's not.  It's questionable, but way short of "clearly incorrect". 
>  As far as minimal examples checking for a possible compiler bug go, I 
> find it to be just about perfect.

Setting an "unsigned" value to a negative value is more than a little 
questionable, IMHO.  It's still a compiler bug, of course.

David Brown said:

> Hans-Bernhard Br�ker wrote:
>> David Brown wrote:
>>> John Regehr wrote:
>> 
>>>> int foo (void) {
>>>>   signed char l_11 = 1;
>>>>   unsigned char l_12 = -1;
>>>>   return (l_11 > l_12);
>>>> }
>> 
>>> There should not be any security vulnerabilities due to such a
>>> bug - the C code is clearly incorrect code,
>> 
>> No, it's not.  It's questionable, but way short of "clearly
>> incorrect".
>>  As far as minimal examples checking for a possible compiler bug
>>  go, I
>> find it to be just about perfect.
> 
> Setting an "unsigned" value to a negative value is more than a
> little questionable, IMHO.

I don't see why. Note 3.1.2.5 Types: "A computation involving 
unsigned operands can never overflow, because a result that cannot 
be represented by the resulting unsigned integer type is reduced 
modulo the number that is one greater than the largest value that 
can be represented by the resulting unsigned integer type."

So: unsigned char l_12 = -1; is guaranteed to set l_12 to UCHAR_MAX. 
No question.

<snip>

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999