Reducing undefined behavior in the C language
6 points by fanf
6 points by fanf
Undefined behavior exists for a number of reasons. It allows implementations to support extensions, manage interactions with hardware-based safety mechanisms
No.
No. No. No.
UB has nothing to do with supporting different hardware behaviour. At all.
Let's take signed integer overflow. That is UB. This does not mean that you can write a + b < a as an overflow check if that's the behaviour on your hardware. Being UB means that if you code does this, you code is wrong. It does not check for overflow, it either:
This is ostensibly useful for vectorizing loop induction variables, but I'm not super convinced.
There are
(1) is obvious. (2) and (3) are what support different implementations and hardware, etc. The behavior is still defined, the code that triggers them is correct (per the AM, you're still free to have logic bugs), the compiler is constrained, it cannot assume it doesn't exist.
And UB is behavior that is invalid on the AM, and anything invalid on the AM can be assumed to not happen.
(C++ also has Erroneous behavior, but that basically just exists because the standard wants to be able to say a common error is an error, but recognize the failure mode is so catastrophic that it requires the compiler to have safe-ish behavior)
Another misconception is that the compiler is detecting and optimizing UB it finds. What actually happens is the compiler encounters some code, and assumes that UB does not happen. e.g lets look a different case of ub: null dereferences.
void do_thing(int a) {
precondition(a > 0);
userid = a;
}
Can a call to this function set userid to 0? let's look at that precondition call. It turns out to be a macro:
#define precondition(x) if (!(x)) *(char*)0=0;
From the compiler's point of view, that macro means that if a < 0 a null dereference occurs. That is UB, so it can't happen, and the branch disappears, and the precondition does nothing. This is not hypothetical: there was a period where dereferencing a nullptr was considered a valid way to force a trap. Then one day gcc started optimizing on the basis of it being UB, and a whole bunch of security bugs went from theoretical to real.
And to be even more explicit about what UB permits:
void do_thing(int a) {
a = -1;
precondition(a > 0);
userid = a;
}
can call an arbitrary function.
I used to think that, but I no longer do. What changed my mind is that C23 redefined realloc(ptr, 0) to be UB, with the explicit purpose of allowing downstream standards to refine the contract:
https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2464.pdf
Classifying a call to realloc with a size of 0 as undefined behavior would allow POSIX to define the otherwise undefined behavior however they please.
So, I think, after all UB means what it says on the tin: just a mere lack of any requirements whatsoever. This absence of guarantees can be used for different purposes: for optimization, to make compilation possible at all (it is a fallacy to think that non optimizing compiler somehow dodges UB), or, as in the realloc case, to define the behavior elsewhere.
I wish that everyone adopted "Checked Illegal Behavior" and "Unchecked Illegal Behavior" terminology instead. It just more precisely expresses the phenomenon we care about with respect to memory safety and all that stuff. Certain runtime behavior of the program are "bad" simply because they are deemed to be so by fiat. It's just the letter of the law, without obligatory connection to hardware.
This legalistic view makes it easy to see the role of compiler as a translator between the high-level language contract and the low-level language contract.
Classifying a call to realloc with a size of 0 as undefined behavior would allow POSIX to define the otherwise undefined behavior however they please.
At least at first blush this sounds like a perfect match for implementation-defined behavior, so I'm rather puzzled why the committee sprung for UB instead. I'd assume that that was discussed in meetings and/or on the mailing list but unfortunately the paper does not elaborate further :(
In C89, calling realloc(ptr,0) (assuming ptr had been allocated previously) would actually free the memory. This changed in C99, so realloc(ptr,0) would return a pointer to 0 bytes [1]. I think so many programs assumed the C89 behavior that the C99 behavior probably caught most programmers by surprise.
[1] What does allocating 0 bytes even mean? A valid pointer that can't be used?
I would hesitate to say that U(ndefined)B exists for the purpose of compiler optimization. You can have a Turing-decidable language and still optimize within it, and that requires the decider to be total, so the semantics of every behavior have to be well-defined by definition. All you need is a notion of what behavior is and is not observable. My personal crackpot theory as to why the term "undefined behavior" has stuck around is aversion to the idea of "nonstandard behavior." Crashing when pointers to different types alias is often way better than introducing memory corruption via ordering, or worse, coherence mismatches. If this was deemed "checked illegal behavior," and this program blew up the planet:
volatile int q;
void foo(int *a, float *b) {
*a = 5;
*b = 6;
}
int main() {
foo(&q, (float*)&q);
blow_up_the_planet();
}
That may end up being a nightmare for someone. However, if the behavior is undefined, then it is perfectly legal for the compiler to decide to blow up the planet.
(to clarify, my claim is "can be used for", not "exists for", I am agnostic about UB's original intended purpose)
All you need is a notion of what behavior is and is not observable.
That's the issue for C though, everything is observable, and why I think any discussion about optimization in the context of C UB is ultimately a red herring. Consider:
int a = 1;
int b = 2;
int* a_ptr = &a;
int* feeling_lucky_ptr = a_ptr + 1;
*feeling_lucky_ptr += 1;
printf("%d", b);
You just can't explain what a non optimizing compiler would do to this program, without some notion of (Unchecked) Illegal Behavior.
Are you proposing the standard itself imposes what is and is not checked? Or just what is illegal? If the former, you still run into the problem I proposed if you ever deem any behavior to be "checked illegal." In the latter case, why is "maybe checked illegal behavior" practically any better than "undefined," if the answer as to what happens is still "I dunno?"
That's the issue for C though, everything is observable
And as far as I understand it, please correct me if I am mistaken, this is not true. Just because you gave a a memory address does not mean that its value is necessarily observable.
If what you mean by "unoptimizing compiler" is a naive compiler that translates the code to the letter like a macro assembler, then you could very easily explain what that code does, just not through the lens of the abstract machine. It writes happens to be at a_ptr + 1, which is a perfectly reasonable statement given that the abstract machine is not in question here.
To loop back, is the behavior I just described "non-standard" (not explained by the standard), "undefined" (also not explained by the standard), or "unchecked and illegal" (I don't know exactly what this means)? Practically, what is the difference?
Classifying a call to realloc with a size of 0 as undefined behavior would allow POSIX to define the otherwise undefined behavior however they please.
What posix says is irrelevant though. realloc is specified as part of the language, compilers are aware of the semantics, and the platform providing defined behavior is irrelevant. If the intent is to permit a platform to specified the contract for realloc, the solution is implementation defined or unspecified behavior, not to label it UB.
Labeling it UB means that
void *foo(void* ptr, int newsize) {
if (!newsize) report("zero sized realloc")
return realloc(ptr, newsize);
}
can be optimized to
void *foo(void* ptr, int newsize) {
return realloc(ptr, newsize);
}
If the compiler discovers that newsize is zero, this can be compiled to
_foo:
_some_other_function:
...
That's literally the definition of what UB allows. The underlying implementation is completely irrelevant, by saying realloc(ptr, 0) is UB they are not saying "the implementation can change the contract for a zero sized realloc", they are saying that the behavior of an implementation in response to a zero sized realloc is irrelevant.
More realistically a compiler might choose to lower realloc(.., 0) or equivalently malloc(0) to a trap: it's UB, so it is permitted to do so, and malloc(0) and realloc(..., 0) are generally considered bad things to do for a variety of reasons. So trapping when that happens means that the mistake is identified early (it is definitionally incorrect code), helping the developer fix it, and it helps the implementation by removing the need to support it. This applies even if the implementation intentionally supports it.
You cannot have a definition of UB in which there are no constraints on how a compiler treats signed integer overflow, while also saying that their are constraints on how realloc(ptr, 0) is interpreted. If a standard wants to say "the implementation can define the behavior in this case", the solution is to say it is implementation defined.
UB has nothing to do with supporting different hardware behaviour.
I thought some of UB was to deal with different CPU behavior. Some CPUs trap on signed overflow; others wrap. Some can do both, either by setting a flag (VAX) or instruction selection (MIPS). Some CPUs, when executing 1 << 100 do 100 rotates; other mask to the bit width of the type (8086 would do all rotates, 80286 started masking).
the compiler encounters some code, and assumes that UB does not happen
I hate that compilers assume that. I know that programmers don't intentionally want to invoke UB in C, but there are so damn many footguns in C that I seriously doubt any non-trivial C program is completely UB free. And if a compiler can delete NULL checks in certain circumstance (<cough> <cough> GCC <cough>) that it at least should warn about it deleting a NULL check written by a programmer, but I've been told that such checks are beyond the ken of compiler writers for some obscure reason.
I thought some of UB was to deal with different CPU behavior.
That's what implementation defined behavior means.
Let's say you're on a machine where integer overflow is defined as trapping. Because it is UB, the fact that it has defined behavior is irrelevant, their are no constraints on the compiler. For example, say you have code that does this:
int foo(int a, int b) {
return a + b;
}
...
int x = INT_MAX;
int y = cond ? 0 : 1;
foo(x, y);
If cond is true, then a + b is INT_MAX + 1 which is UB, so cond must always be false.
It's really important to understand that the compiler is not detecting this directly, a lot of optimizations are constraint based, and the result of applying those constraints is that UB paths get dropped.
I hate that compilers assume that. I know that programmers don't intentionally want to invoke UB in C, but there are so damn many footguns in C that I seriously doubt any non-trivial C program is completely UB free.
Yes, but for the majority of cases where this happens, the problem is not that the compiler is assuming UB operations can't happen. The problem is that operations with well defined behavior are being labeled as UB. Most of the foot guns around "the compiler removed this code" boil down to "the developer wrote code around well defined behavior on the platform, but the spec says it is undefined". The moment that implementation defined behavior stops being labeled as UB, many of those foot guns go away.
UB has nothing to do with supporting different hardware behaviour. At all.
Consider your example of signed integer overflow. If this were implementation defined behavior conforming, correct C programs that relied on the implementation specific behavior (wraparound, saturation, trapping, whatever) would not be portable to different hardware that had different behavior.
Since it is undefined behavior, conforming correct C programs are correct with respect to all hardware.
The ANS Forth standard states that programs written to it must document what the program expects of "implementation specific behavior," so I think it would be prudent for C programs to follow suit. And there are "implementation specific behavior" in C (character set used for source code, size of int, whether char is signed or unsigned, limitations on environment variables names, etc.).
So we agree that UB has nothing to do with cross platform compatibility.
But your justification for the use of UB in cases like this is an argument against any implementation defined behavior, and it brings an immediate rebuttal
Any conforming and correct C program that avoids implementation defined behavior will behave identically across all platforms.
There is absolutely no difference in the degree of difficulty in avoiding all UB and avoiding all IDB: the logic required to avoid invoking UB for any given operation is that same logic required to avoid IDB. The result of making an error is the same in the overwhelming majority of cases, except by labeling something UB the compiler can disregard the behavior that it applies in other places.
There is not difference in cross platform compatibility: the same incompatible code exists in both cases, the only difference is that by claiming something to be UB, code that is correct with respect to the target will behave in accordance with that hardware, except for unpredictable occasions where it will not, and it is not possible for a developer to ever reason about whether or not that happens, because UB is a global, not local, property of the program.
So I have some questions, and I'm curious about what you feel that answers are - obviously you're under no obligation to respond, but I am curious. I'm just saying IDB here, but IDB and unspecified are in the same general bucket for the purpose of this thread.