Knowing the implementation, are all undefined behaviours become implementation-defined behaviours?

[Richard Tobin]

while (ptr != 0) {
/* blah blah blah */
ptr = get_ptr();
x = *ptr;
}

gcc might turn the while into an if followed by an infinite loop, because
it *knows* that ptr can't become null during the loop, because if it did,
that would have invoked undefined behavior.

As I've said before, the fact that the compiler can do this sort of
optimisation is often an indication of an error in the code. Why
would the programmer repeatedly test the pointer if it couldn't be
null? I would much rather that the compiler warned about this, instead
of just treating it as an opportunity to remove some code.

-- Richard

 

[Seebs]

As I've said before, the fact that the compiler can do this sort of
optimisation is often an indication of an error in the code. Why
would the programmer repeatedly test the pointer if it couldn't be
null? I would much rather that the compiler warned about this, instead
of just treating it as an opportunity to remove some code.

That's an interesting point, and I think I'd agree. Maybe. Do we
want a warning for while(1), which we know definitely loops forever?

It could be that the loop was written because the programmer wasn't *sure*
it couldn't be null, but the compiler has proven it and thus feels safe
optimizing.

-s

 

[Richard Tobin]

That's an interesting point, and I think I'd agree. Maybe. Do we
want a warning for while(1), which we know definitely loops forever?

No, but only because it's a common idiom.

It could be that the loop was written because the programmer wasn't *sure*
it couldn't be null, but the compiler has proven it and thus feels safe
optimizing.

All the more reason for a warning. Then the programmer can sleep
soundly, and perhaps modify the code accordingly. (And modify the
comment about it that he no doubt wrote.)

-- Richard

 

[Seebs]

All the more reason for a warning. Then the programmer can sleep
soundly, and perhaps modify the code accordingly. (And modify the
comment about it that he no doubt wrote.)

Hmm.

The problem is, this becomes a halting problem case, effectively. It's like
the warnings for possible use of uninitialized variables. We *know* that
those warnings are going to sometimes be wrong, or sometimes be omitted when
they were appropriate, so the compiler has to accept some risk of error. I
think this optimization is in the same category -- there's too many boundary
cases to make it a behavior that people rely on or expect.

-s

 

[ThosRTanner]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Deferencing a NULL pointer is undefined behaviour, but, on Linux, the
program crashes with SIGSEGV. So, the behaviour of derefencing a NULL
pointer is defined to "crash the program with SIGSEGV".

Signed integer overflow is undefined behaviour, but, on x86 CPUs, the number
simply wrap around so we can say that the behaviour is defined to round on
x86 CPUs.

The results of accessing uninitialised memory however are wildly
unpredictable, as well as going over the end of an array. It may
always crash, but its far more likely to occasionally do something
strange.

void func()
{
int i;
std::cout << i << "\n";
}

is going to depend, among other things, on what has been called before
func.

Arguably it's predictable but so is the weather. It just takes 3 days
of work on a massive supercomputer to get a 24 hours forecast...

 

[Phil Carmody]

It's not.

But if you dereference a pointer at some point, a check against it can
be omitted. If, that is, that dereference can happen without the check.

So imagine something like:

ptr = get_ptr();

while (ptr != 0) {
/* blah blah blah */
ptr = get_ptr();
x = *ptr;
}

gcc might turn the while into an if followed by an infinite loop, because
it *knows* that ptr can't become null during the loop, because if it did,
that would have invoked undefined behavior.

And there are contexts where you can actually dereference a null and not
get a crash, which means that some hunks of kernel code can become infinite
loops unexpectedly with modern gcc. Until the kernel is fixed, which I
believe it has been.

One high profile instance was fixed. I think I fixed another one or two
recently. Independent eyes, and all that, imply that there are probably
hundreds left.

I wonder if sparse can be tweaked to detect it. I'm a tad rusty at
sparse internals, but might be able to add it if I have some spare
time.

Phil

 

[Phil Carmody]

That's an interesting point, and I think I'd agree. Maybe. Do we
want a warning for while(1), which we know definitely loops forever?

It could be that the loop was written because the programmer wasn't *sure*
it couldn't be null, but the compiler has proven it and thus feels safe
optimizing.

There's a difference between deducing that an expression has or
doesn't have a particular value based on code elsewhere, and
detecting a purely constant value. So the two can be treated as
separate cases and {en,dis}abled independently.

However, in a C context, this would be a mid-way case between those two:

static const int debugging = MAYBE_A_HASHDEFINE;

foo() {
//...
if(debugging) { frob_stuff(); }
//...
}

I think I wouldn't want a compiler warning for that, were debugging
to be zero.

Phil

 

[Nobody]

Sorry to interrupt, but since when is checking a pointer value
for 0 the same as deferencing it? Checking a pointer treats the
pointer itself as a value, and comparison against 0 is one of
the few things that are _guaranteed_ to work with a pointer
value. So if GCC really would remove a check of the form

if(!pointer)
do_something(*pointer);

or even

if(pointer == 0)
throw NullPointerException;

It won't remove those checks, but the first one may well be converted to:

if(!pointer)
do_something_completely_different();

And that's entirely legal, as the the original code invokes UB when the
test succeeds. [Or did you get the test the wrong way around?]

Also, if you do e.g.:

int x = *p;

if (p)
do_something_to(x);

it may simply omit the test. As you have already dereferenced p by that
point, if p happens to be null, you invoke UB and the compiler can do
whatever it wants, including executing the code which should be executed
when p is non-null.

This isn't a theoretical situation; some versions of gcc *will* perform
the above optimisation. This particular case resulted in an exploitable
bug in a Linux kernel module (the bug was compounded by the fact that you
*can* have memory mapped to page zero; this is permitted for the benefit
of emulators such as DOSbox).

 

[Alan Curry]

|-----BEGIN PGP SIGNED MESSAGE-----
|Hash: SHA1
|
|Deferencing a NULL pointer is undefined behaviour, but, on Linux, the
|program crashes with SIGSEGV. So, the behaviour of derefencing a NULL
|pointer is defined to "crash the program with SIGSEGV".

Are you sure?

Compile this with and without -DUSE_STDIO and explain the results.

Both branches ask the system to do the exact same thing: fetch a byte from
the address indicated by NULL, and write it to the standard output.

#include <stdio.h>
#include <unistd.h>

int main(void)
{
#ifdef USE_STDIO
if(fwrite(NULL, 1, 1, stdout)==0 || fflush(stdout))
perror("fwrite from null pointer");
#else
if(write(STDOUT_FILENO, NULL, 1)<0)
perror("write from null pointer");
#endif
return 0;
}

 

[James Kanze]

Then I would say that it is not an example of what James was
talking about. In his C++ example, no null pointer is
dereferenced.

It's also a case of the implementation (compiler) guaranteeing
the implementation (library) that in this particular case, it
will work. That's an in-house guarantee, that they might not
have made public. (And of course, not all compilers do this.)

Obviously there is a terminology issue here in that you might
want to say that sizeof *(int *)0 is a dereference of a null
pointer because, structurally, it applies * to such a pointer;
but I would rather reserve the word dereference for an
/evaluated/ application of * (or [] or ->). I'd go so far as
to say that any other use is wrong.

It's not a question of what one would "rather". The standard is
very clear that dereferencing a null pointer is something that
happens at execution, not at compile time. And that a sizeof
expression is fully evaluated at compile time.

 

[Ersek, Laszlo]

It's not a question of what one would "rather". The standard is
very clear that dereferencing a null pointer is something that
happens at execution, not at compile time. And that a sizeof
expression is fully evaluated at compile time.

There might be a shorter path leading there:

C90 6.3.3.4 "The sizeof operator", p2: "The size is determined from the
type of the operand. which is not itself evaluated."

C99 6.5.3.4 "The sizeof operator", p2: "If the type of the operand is a
variable length array type, the operand is evaluated; otherwise, the
operand is not evaluated and the result is an integer constant."

C++98/C++03 5.3.3 "Sizeof", p1: "The operand is either an expression,
which is not evaluated, or a parenthesized type-id."

Cheers,
lacos

 

[Ben Bacarisse]

Then I would say that it is not an example of what James was
talking about. In his C++ example, no null pointer is
dereferenced.

It's also a case of the implementation (compiler) guaranteeing
the implementation (library) that in this particular case, it
will work. That's an in-house guarantee, that they might not
have made public. (And of course, not all compilers do this.)

Obviously there is a terminology issue here in that you might
want to say that sizeof *(int *)0 is a dereference of a null
pointer because, structurally, it applies * to such a pointer;
but I would rather reserve the word dereference for an
/evaluated/ application of * (or [] or ->). I'd go so far as
to say that any other use is wrong.

It's not a question of what one would "rather". The standard is
very clear that dereferencing a null pointer is something that
happens at execution, not at compile time. And that a sizeof
expression is fully evaluated at compile time.

This is a C/C++ distinction. I'd already forgotten the cross post by
the end of my post. The C standard does not use the term so, for C
alone, a case could be made to use the term in a purely syntactic way
and I was arguing against that.

 

[Nobody]

|Deferencing a NULL pointer is undefined behaviour, but, on Linux, the
|program crashes with SIGSEGV. So, the behaviour of derefencing a NULL
|pointer is defined to "crash the program with SIGSEGV".

Are you sure?

Compile this with and without -DUSE_STDIO and explain the results.

Both branches ask the system to do the exact same thing: fetch a byte from
the address indicated by NULL, and write it to the standard output.

Neither branch *dereferences* a null pointer; they just pass it to a
function. It's unknown whether either function ultimately dereferences the
pointer; they may test it for validity first.

In any case, the argument about dereferencing null pointers being
"defined" to crash the program with SIGSEGV is bogus.

First, SIGSEGV isn't defined to "crash" the program; you can install a
handler for SIGSEGV, and even if you don't, not everyone would consider
terminating on a signal to be a "crash" (does abort() "crash" the program?).

Second, SIGSEGV typically arises from accessing an address to which
nothing is mapped (or which is mapped but without the desired access). But
you can have memory mapped to page zero; 8086 (DOS) emulators frequently
do this.

Finally, reading a null pointer (as that term is defined by C) doesn't
necessarily result in reading address zero, as the compiler can optimise
the access away. In particular, in a context where a pointer has already
been dereferenced, recent versions of gcc will assume that the pointer is
non-null (if it's null, you've invoked UB by dereferencing it, so the
compiler can do whatever it wants, including doing whatever it's supposed
to do when the pointer is non-null).

 

[tonydee]

The way that term is used in the standard,
is to describe programs outside of any context.

The question is,
"Does the standard place any limitions
on the behavior of this program?"
If the answer is "No", then you have undefined behavior.

I think it is simplest to consider
the behavior of an otherwise correct
program which executes this statement
     return (1 / (CHAR_BIT - 7));
as being implementation defined

The way you're contrasting this with "/ (CHAR_BIT - 9)" suggests you
believe CHAR_BIT >= 8. I've heard rumours of systems where it was 7,
but let's ignore that.

I don't believe that your example is implementation defined vis-à-vis
the Standard.

"1.4 Definitions
[intro.defs]

--implementation-defined behavior: Behavior, for a well-formed
program
construct and correct data, that depends on the implementation
and
that each implementation shall document."

If your code divides 1 by some positive value, that has a well-defined
meaning and flow of control that is common to all C++ compilers/
environments, though the exact divisor and result may vary. Nothing
here needs to be documented per implementation.

and the the behavior of an otherwise correct
program which executes this statement
     return (1 / (CHAR_BIT - 9));
as being undefined.

Only on a system where CHAR_BIT was equal to 9 would this result in
undefined behaviour. From the Standard:

5.6 Multiplicative operators [expr.mul]

4 ...
If the second operand of / or % is zero the behavior is unde-
fined; otherwise (a/b)*b + a%b is equal to a. If both operands
are
nonnegative then the remainder is nonnegative; if not, the sign of
the
remainder is implementation-defined

This applies at run-time. A program doesn't have some static property
of "undefined behaviour" just because some unsupported inputs could
cause undefined behaviour at run-time. That said, given CHAR_BIT may
be constant for a particular version of a compiler on a particular
system, it may be that compiling and running the program in that
environment will always generate undefined behaviour. Taking the code
in isolation from the compilation environment, it's more likely to
provide a negative divisor, triggering the mixed-signs clause above
and hence implementation-defined behaviour. So, there are three
possible run-time outcomes based on static analysis of the source
code: undefined behaviour, implementation defined behaviour, and well-
defined behaviour.

Cheers,
Tony

 

[Nick Keighley]

[this] suggests you
believe CHAR_BIT >= 8.  I've heard rumours of systems where it was 7 [...]

CHAR_BIT cannot be less than 8 on a standard conforming C (or C++)
implementation

 

[tonydee]

[I note the cross-post to clc++. My answer is given in a C context,
which may or may not also apply to C++.]

I don't believe that your example is implementation defined vis-à-vis
the Standard.

The CHAR_BIT - 7 one is implementation-defined. The implementation
defines it by defining CHAR_BIT (as it is required to do), which is at
least 8 but which can be greater. So the result of the expression 1 /
(CHAR_BIT - 7) will be 1 unless CHAR_BIT exceeds 8, in which case it
will be 0.

The _value_ of CHAR_BIT is implementation defined. Programs that
incorporate the value into the division above always receive a result
that's entirely specified - as a function of the inputs - by the
Standard. The division process and behaviour are well defined. I
don't think it's correct or useful to imagine that all behaviour
consequent to something implementation defined is itself
implementation defined.

If we look at what was being said:

Surely it is implied that it's the use of CHAR_BIT in the division,
and not CHAR_BIT itself, which might make the expression
implementation defined? I'm saying that in that exact but limited
sense, it's moved past the implementation defined aspect and division
behaviour is well defined.

When we shift to CHAR_BIT - 9, however, the result can be -1 (for
CHAR_BIT of 8), or 1 (for CHAR_BIT of 10), or 0 (for CHAR_BIT of 11+),
or undefined (for CHAR_BIT of 9). So, if all we can observe is the
source (i.e. we don't know the implementation), the safest observation
we can make is that the code exhibits undefined behaviour and should be
changed.

Again, this misses the subtlety I was trying to communicate. "The
code exhibits undefined behaviour" is misleading. It's only exhibited
when it happens. It certainly _can_ exhibit undefined behaviour, but
there are many environments where it will run with well-defined
behaviour. There may even be a compile time assertion that CHAR_BIT !
= 9 somewhere above. While any good program would handle this issue
is a robust fashion, but it's not a precondition for avoiding
undefined behaviour when the implementation has CHAR_BIT != 9. It
boils down to a defensive programming consideration.

CHAR_BIT does. Since the result of the expression depends on that value,
the behaviour is effectively implementation-defined.

(Discussed again above.)

Cheers,
Tony

 

[Richard Bos]

As I've said before, the fact that the compiler can do this sort of
optimisation is often an indication of an error in the code. Why
would the programmer repeatedly test the pointer if it couldn't be
null? I would much rather that the compiler warned about this, instead
of just treating it as an opportunity to remove some code.

I'd much rather that it did both. I can see why you'd want a warning,
but I still want my compiler to optimise away a test which I'd not
realised was superfluous (or perhaps more likely, which is superfluous
on one architecture but not on another).

Richard

 

[Tim Rentsch]

Hmm.

The problem is, this becomes a halting problem case, effectively. It's like
the warnings for possible use of uninitialized variables.

There is one very important difference -- in one case the
compilers says the code /might/ not work they way you /think/ it
does, and in the other case the compiler says the code /won't/
work they way you said it /should/ work. Any optimizations
predicated on previous undefined behavior fall into the second
category, and warnings for these are "fool proof", because they
happen only when the compiler is doing something it's /sure/ is
dangerous, not when you're doing something that only /might/ be dangerous.

We *know* that
those warnings are going to sometimes be wrong, or sometimes be omitted when
they were appropriate, so the compiler has to accept some risk
of error.

Good compilers do only one of these for uninitialized variables,
namely, they sometimes warn that variables might be used without
initialization even though they aren't. No decent compiler that
purports to give warnings on uninitialized variable use ever
misses a case when this might happen.

I
think this optimization is in the same category -- there's too many boundary
cases to make it a behavior that people rely on or expect.

I expect if you think about it a little longer you'll reach
a different conclusion.

 

[Tim Rentsch]

I'd much rather that it did both. I can see why you'd want a warning,
but I still want my compiler to optimise away a test which I'd not
realised was superfluous (or perhaps more likely, which is superfluous
on one architecture but not on another).

Definitely - as long as the compiler provides an option to give
the warning, I also want the option to do the optimization.

 

[Seebs]

Good compilers do only one of these for uninitialized variables,
namely, they sometimes warn that variables might be used without
initialization even though they aren't. No decent compiler that
purports to give warnings on uninitialized variable use ever
misses a case when this might happen.

I do not believe this to be the case.

I expect if you think about it a little longer you'll reach
a different conclusion.

Well, actually. The reason I hold my current belief is that I have had
opportunities to discuss "may be used uninitialized" warnings with gcc
developers. And it turns out that, in fact, spurious warnings are
consistently reported as bugs, and that at any given time, gcc is usually
known both to give spurious warnings and to miss some possible uninitialized
uses. In each case, the goal of the developers seems to be to maximize
the chances that gcc is correct.

Now, maybe that makes gcc "not a good compiler", but it certainly makes gcc
the sort of compiler that customers appear to want, which is one which does
its best to minimize errors rather than accepting a larger number of errors
in order to ensure that they're all of the same sort.

Keep in mind that, stupid though it may be, many projects have a standing
policy of building with warnings-as-errors, so a spurious warning can cause
a fair bit of hassle.

-s