DHO is Mostly Confused

Rants from Devon H. O'Dell

Discovering Undefined Behavior

The C language is infamous for undefined behavior. Fantastic, multi-part articles by Chris Lattner and John Regehr have made their rounds over the years, describing several instances of undefined behavior. In particular, they describe how compilers are allowed to assume it does not occur in correct C programs, and therefore make optimizations that seem to remove correctness from programs. The intent of these posts seems to be to educate people that they should be aware of what consitutes undefined behavior.

But this isn’t always so easy.

When does undefined behavior occur? The C11 draft formalizes this in §4p2:

If a ‘‘shall’’ or ‘‘shall not’’ requirement that appears outside of a constraint or runtime-constraint is violated, the behavior is undefined. Undefined behavior is otherwise indicated in this International Standard by the words ‘‘undefined behavior’’ or by the omission of any explicit definition of behavior. There is no difference in emphasis among these three; they all describe ‘‘behavior that is undefined’’.

Of note should be the text stating that undefined behavior occurs when “any explicit definition of behavior” is omitted. What happens if you try to run a C compiler on cheese? This is undefined by omission, and therefore this implicit undefined behavior becomes explicit.

Maybe that doesn’t sound so bad, but it results in tons of confusion amongst programmers and compiler implementors. For example, did you know that printf("%p", (void *)NULL); yields undefined behavior? This is because §7.1.4p1 states, “If an argument to a function has … a null pointer, … the behavior is undefined.” Later on, in the specification of the printf family, no such exception appears.

This might seem innocuous, but it’s maybe more obviously problematic if you consider a case like printf("%s", s);, where s is NULL. Printf functions have relatively high overhead: they’re variadic functions, which tend to be more expensive to call. They also contain format strings, which must be parsed at runtime. Some compilers therefore optimize calls like printf("%s", s); to puts(s);, which are functionally equivalent. This is allowed because of the statement in §7.1.4p1, but pisses folks off because most printf implementations will output something like (nil) if s is NULL. Puts, on the other hand, probably crashes trying to dereference a null pointer.

You might think all cases of undefined behavior have been discovered. I’d be surprised if this was true. The “undefined by omission” case allows for all sorts of things that are so circuitous to understand, it makes you wonder how the language works at all. For example, after a somewhat long discussion in ##C on Freenode, we came to the conclusion that there’s undefined behavior hidden in bit-fields. To get here, you have to jump through several hoops:

First of all, §6.7.2p5 states that an implementation may choose whether a bit-field of type int is represented as signed int or unsigned int. Given the following code,

struct ex {
    int bf : 1;
};

we might expect to be able to represent the values -1 and 0. Or maybe 0 and 1. Or maybe -0 and 0. But none of these are actually possible, because §6.2.6.2p2 defines signed integers as “containing exactly one sign bit,” the purpose of which is to modify the value of the variable with either sign and magnitude, two’s complement, or ones’ complement semantics. However, in the above example, ex.bf clearly has no value bits to modify if it is represented as a signed integer: there is only enough space to represent the sign bit.

The spec could clear this up by specifying in §6.7.2.1 that bit-fields of signed type must include enough space for at least one value bit. Or specifying something similar at or around §6.2.6.2, where the representation of signed integers is discussed. As it stands, this is the kind of thing you end up running into on accident.

I don’t think it’s great that programmers should be left to “discover” undefined behavior. To that end, I think it’d be great if things like this were spelled out more completely in the standard, or if Annex J.2 was considered normative. However, it seems the standard committee is fine leaving such behavior undefined by omission.

What undefined behavior have you discovered? I’d love to hear about it!

More Posts