C compiler undefined behavior: calls never-called function
gcc.godbolt.org
gcc.godbolt.org
Is this what is happening?
While this is certainly unexpected, I can't fault the compiler here. The example emphasizes the need for tools to check for undefined behavior.
You can see that if you "fix" the program by checking Do before calling it, it still inlines the call in the True branch:
if (NULL != s) { s->a = 1; }
s->b = 1;
then GCC may optimize away the NULL check because referring to s->b after the block protected by the NULL check indicates that the NULL check is superfluous. I this case, this is actually true, but in cases that involve aliasing that is not detected by dataflow analysis, there might be circumstances where the NULL check is required. Discussion of something related is here[0]; my example might not be very good.
An even more insidious case is [1](strong language), where manual overflow checks are optimized out because the overflow technically invokes UB.
Compiler optimization gone wild.
[0] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71892 [1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475
At some point safety matters, and the more likely human mistakes matter.
NeverCalled is a "public" function since it isn't marked static, so the author of this code intended for it to be called externally to initialize Do.
The compiler's optimization produces a correct program along the only valid execution path: Compile this as an object file, and link it with some other code that calls NeverCalled and then main.
If you mark NeverCalled as static, the compiler outputs an explicit "Undefined Instruction", because there are then no execution paths that don't invoke undefined behavior.
Compilers are not in the business of creatively guessing what "the author of this code intended".
It's not theoretical at all: Before I saw this thread, I was in the middle of writing some Haskell that loads some non-main symbols from an object file derived from an executable's source code, and invokes them. People carefully mark which functions are or are not static to ensure their executables don't get bloated. I'd be very annoyed if my C compiler didn't take symbol visibility into account when optimizing, because I depend on it all the time.
Real life analogy: declaring a static function is like locking your car because you don't want it stolen: only hackers can access it through forbidden means. If instead you leave your nonstatic car parked in the street, open and with keys in the ignition, you are making it easy to steal (probably you want it to be stolen, there might be an UB corpse in the trunk you want to get rid of), but you cannot be sure that a thief will actually come along and take it away; you are just advertising that they should.
Since the program unconditionally calls an uninitialized (actually zero-initialized) function pointer, that is undefined behavior. It therefore has no valid executions. The compiler is legally allowed to generate whatever code it wants, and that is considered valid according to the standard. It just so happens in this case that it probably generated no code at all for main, falling through to code that it did generate. (and my guess as to why it did generate code for NeverCalled() is because it's non-static and could be called by functions outside this compilation unit; NeverCalled keeps EraseAll() alive.)
edit: the above is only true if the compiler knows main is the entrypoint to the program.
With -O1 you can see that this part already happens. With optimization cranked further up it just inlines EraseAll, and EraseAll ceases to exist as a separate symbol. This is possible since Do is static and not aliased. Meanwhile NeverCalled continues to exist as a retq, since it is not static.
It's not a bug in what? The compiler or the input program? [The answer is, the compiler is fine, the input program has undefined behavior.]
> without optimization it doesn't happen
That's fine. As the input program has undefined behavior, the compiler is free to compile it differently at different optimization levels.
Some of them will insist on not using the optimizer because it can introduce bugs. I take the opposite attitude - let's go with -o3 from day one because we'll eventually run out of CPU time and have to turn it on anyway. If that uncovers bugs in the code or compiler it's better to find them early.
I don't think compilers know that main() is really the entrypoint, since there is some code in the C runtime that runs before main. If compilers treated main like the program entrypoint, then my original comment would stand.
Yes they do.
> since there is some code in the C runtime that runs before main
So? From the point of view of the C standard, main is the entrypoint to the C code in the program the compiler is asked to compile.
(Edited to add: This particular example program is in C++, but whatever.)
Why don't we call that what the compiler emits when it encounters undefined behavior not "correct" but "invalid" or "wrong"? It's a matter of changing the terms to not overload "correct". The compiler is free to output "invalid" code on "invalid" input - garbage in, garbage out. But to use the term "correct" is silly.
Going a bit further, I believe a compiler has the right to do sensible things with undefined behavior. I greatly prefer it to do the obvious thing, when it can't do the correct thing.
In this case, try to execute the function at the address given by Do; since Do is uninitialized just use the number already in memory at Do's location as an address. I would also not be surprised if it initializes it with 0, and places EraseAll at 0x00, and thus calls EraseAll (although I know that address spaces on modern computers do not work like that).
In reality, I would expect the program to crash most of the time with an access violation, rarely with an invalid opcode, and extremely rarely call one of the functions (when Do contains that address by chance).
But the compiler has full control over that memory, and it's faster when the number is the same as what might eventually be written into it, but then you no longer need to write anything, since that value is already in memory, and now it's a constant and why keep a constant in memory when you can just inline it ...
All of the steps are completely intuitive and a compiler capable of executing them is much better than one that just indiscriminately zeros all memory and never dares to optimize anything to avoid exposing someone's mistakes.
The best a compiler can do in the face of guaranteed undefined behavior is to warn the programmer and tell them to fix their code. Unfortunately, C makes it quite difficult to distinguish between defensively-written code that avoids UB, and code that treats C like a portable assembler, that will do the "obvious" (but slow) thing.
Noting that your parent only used the word "correct" in the phrase "correct compilation"...
> The compiler is free to output "invalid" code on "invalid" input
... you are actually agreeing with your parent. Maybe they should have said "legal compilation" instead of "correct compilation".
You seem to be saying that your parent said "the resulting assembly program is a correct program", which is silly. We cannot talk about its correctness, as there is no specification to judge correctness against (or the source program already doesn't satisfy the specification, in which case the compiler cannot help and should never even be called before fixing the bug).
What I'm arguing is that we shouldn't call that a correct compilation. It is a wrong compilation - is wrong with prior notice, and there is in fact no way to do it right, because the source is wrong (UB).
I think I don't disagree about behavior, but about semantics. We shouldn't say, e.g. in a compiler's manual, that the compiler is free to (has the right to, is correct to) do anything when it encounters UB. Rather, I'd warn that the compilation might fail silenty on UB.
The difference is not factual, it is in tone. Stating matter-of-factly that nasal demons is the correct result of compiling UB code is aggravating. It is the equivalent of the compiler singing nana-nana-na-na (or ätsch bätsch for the Germans).
What do you mean by "fail"? Terminate compilation without producing output code? That's not possible, the compiler cannot detect all (or even most) UB at compilation time. Or do you mean it would produce "wrong" code (as it does now)? That's not what is commonly called "failure", and I think putting it that way is obscuring the issue, not making it clearer.
I suspect UB is going to seriously damage or largely kill off statically compiled languages in the long run. Speculating JIT compilers can compile code in such a way that all executions are defined yet which does not experience the speed penalty C programs suffer, because the optimiser is free to make risky assumptions that are checked on the fly and de-optimise if they fail. It's heavy to have a full blown compiler running at the same time as your app, but desktop/laptop machines tend to have spare cores doing nothing anyway, and on servers the compiler is only running for a short period during warmup anyway and then is hardly used again.
As for a "reasonable" C compiler, there is always -O0.
http://webcache.googleusercontent.com/search?q=cache%3Assw.j...
If the compiler concludes that the program has no valid executions, then why not just generate an error message at compile time?
I wonder in what other engineering disciplines this kind of attitude (i.e. silently punishing users for mistakes by generating arbitrarily misbehaving code) is considered acceptable. It seems unethical to me. Perhaps compiler writers should think more about what constitutes sound engineering, rather than what happens to be permitted by The Standard.
I agree that that would be nice to see in this case, and it seems like this particular case would be low-hanging fruit, but it's not that simple. In particular, the compiler in this example most likely does not reason globally; it never actually decides that "the program has no valid executions". It does a series of local transformations, presumably based on facts of the form "if we can reach this point, then certain values are invalid".
Another thing about such error messages would be that they would push compilers more in the direction of verification tools, which they aren't, and cannot be.
Consider:
int f() {
return 1 / 0;
}
int g() {
int a = 0;
return 1 / a;
}
If compilers had more such warnings, programmers would be tempted to say "look, there is no warning, the code must be fine". That's the whole "if it compiles, it's correct" approach that gives some gullible people a false sense of security in other languages.
Clang and gcc will warn you about some of these issues if you give them the right flags (so much so that -Wall no longer means literally all warnings, IIRC), but then you run into static analysis' problem of burying you in false positives for conditional / data-dependent undefined behavior.
I have found it instructive to play with Dafny, one of the languages where the compiler does require you to prove that a variety of bugs will not occur, but 'play' is the operative word here. It is not a feasible option for C.
C has always been a language for (among other things) creating optimized code, but the implication of that has changed. Originally, it meant / required being 'close to the metal', but since then, effective automated optimization has come along, and the metal itself has become considerably more complicated (partly as a consequence of more capable optimization). As C programmers, we should understand that these changes have occurred, and what they mean for programming in C - or not use the optimizer.
No, the Haskell slogan is "If it compiles it works". "It works" is something quite different to "it is correct".
"please don't do this, you're not producing value": http://blog.metaobject.com/2014/04/cc-osmartass.html
"No sane compiler writer would ever assume it allowed the compiler to 'do anything' with your code": http://article.gmane.org/gmane.os.plan9.general/76989
"Everyone is fired": http://web.archive.org/web/20160309163927/http://robertoconc...
The really strange this is: there's probably tons of places that the compiler takes advantage of undefined behaviour, and nobody notices, and in fact is grateful of the magic speed improvement that comes for free simply from adding -O3 or whatever. And these are then used to justify the undefined behaviour that people find slightly mystifying, or that cause actual problems in practice (interestingly these always seem to be related, as in this case, to things that can be statically proven to have NULL-related undefined behaviour). But why not treat these two cases differently?
The customer is always right!
From this optimization pass's perspective, it has proved that in a legal program `Do` can only have one possible value, and simplified the code appropriately. Most of the time this sort of optimization is correct and the programmer wants it; how is it supposed to figure out that this time the programmer had some different semantics in mind?
E.g. one justification given for signed integer overflow being undefined behavior is so that compilers are legally permitted to optimize "(a + k) < (b + k)" to "a < b", which is not correct in the case of overflow.
However, to me it looks as if the assembly contains code for main (label main: is present) and EraseAll got inlined into main. This seems reasonable once you believe that the compiler can, due to undefined behavior, assume DO to be EraseAll.
I wonder how many static analysis tools will pick up that the function will be run.
And then I start wondering if the static analysis tool "scene" realizes how important their work is for security...
You can't be sure, that's just what one compiler does today. Static analysis tools tend to refer to the standard.
$ tis-analyzer foo.c -val
/tmp/foo.c:16:[kernel] warning: Function pointer and pointed function have incompatible types.
Pointer type: int ()
Non-function: {0}
assert \valid_function(Do);
....
/tmp/foo.c:16:[value] Assertion 'Value,function_pointer' got final status invalid.
Which means that if I have a method that wipes my entire production database but never ever call it, it might still get called because of mistake like this one where someone forgot to initialize a function pointer.
Do you actually have a method like that? Somehow I doubt it. Also, the example is completely contrived. If you have an uninitialized function pointer it's going to be pretty uncommon that there's only one possible function for the compiler to conclude is the right one. Also, you should not be testing on a production system.
On a note related to your example, many automotive ECUs have the ability to re-flash over the vehicle network. In many cases the OEM requires that they do not contain any code to erase or program their own flash memory. This is for the reason you cite - if somehow (for whatever reason) that code were to execute it may brick that device. This then requires that the bootloader download a couple functions to RAM prior to updating its own code - those functions are the ones that erase and write flash. This is also convenient for some micro controllers that can't modify flash while code is being executed from it.
There are optimizations that can bite you when you thought you were doing everything right, but misunderstood undefined behavior. This is not such a case. If you write that kind of code, wiping your database is letting you off easy.
This is not the "expected" behavior; undefined behavior doesn't have an expected behavior. This is what the compiler at godbolt.com happens to generate for this particular code.
At best, an analysis tool can warn that the code has undefined behavior.
The least obvious things, like undefined behavior, are exactly the sort of thing a static analysis tool should be expected to warn about.
The case in point is Rust: Its type system is basically an elaborate static analysis.
Rusts advantage over tools like UBsan is that the programmer expects to interact with the type system. Many static analysis tools get rejected by programmers, because the expectation is that they "just work", when really one needs to interact with such a tool. This means bidirectional communication: The programmer tells the tool what invariant he wants to get, and the tool tells the programmer which invariants it is missing.
Most optimization passes don't know what the original code looks like, they only see it after it's been passed through a bunch of other optimization passes and preprocessing, so they can't reason about whether a particular optimization would seem "completely natural" or "abuse of UB" to the original programmer.
Here it's clear that "NeverCalled" is never called so it's clear that Do is never assigned, so the Call can't produce anything useful.
EDIT: Ugh missed the lack of "static" on the NeverCalled. Never mind.
Is this too hard to decide with certainty in C because of how you could do some pointer gymnastics and just fiddle with the field without the compiler realizing, so in order not to spit out false positives, compilers just have to assume the author knows what he's doing and allow the suspected UB without warning?
I'm just used to higher level "safe" languages (Rust, C#, etc), where lack of assignment is usually determined with certainty.
I don't think that is clear. If the given file is linked with another file that initializes a static variable with a function that calls NeverCalled, the initialization will be done before main is called, and so NeverCalled will be called. The compiler can't tell from just analysing the one file shown here whether or not NeverCalled is called.
Right. I missed that the uncalled function was public. So the issue is not clear until you link I suppose, so only detected "globally" whether the function is called. is it fair to say that that kind of global analysis is rare in the compiler+linker toolchain world for C, and usually left to static analyzers instead?
> The compiler can't tell from just analysing the one file shown here whether or not NeverCalled is called.
Right, and making it static you get the -Wunused-function. Great. This warning is about the NeverCalled function being unused though, and not about Do being unassigned before it's called. Curious, is there any way to get a warning for this? This is UB, correct? And the assignment is now known not to happen?
typedef int (*Function)();
static Function Do;
void main() { Do(); }How would that work in actual code? Static initialization must be done with constant expressions. C++ has constexpr functions, but they cannot call NeverCalled unless it is also marked constexpr, can they?
I tried to build the example (and changing the system to an echo) using "clang a.cpp -o a -Os -std=c++11 -lstdc++ -fsanitize=undefined", but the sanitizer didn't detect the UB.
[0] https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html
> clang -Os -std=c++11 -Wall -o boom -fsanitize=undefined boom.cpp
/tmp/boom-428713.o:(.rodata._ZTIFvvE[_ZTIFvvE]+0x0): undefined reference to `vtable for __cxxabiv1::__function_type_info'
/tmp/boom-428713.o:(.rodata._ZTIFivE[_ZTIFivE]+0x0): undefined reference to `vtable for __cxxabiv1::__function_type_info'
clang: error: linker command failed with exit code 1 (use -v to see invocation)Isn't this because the sanitizer works with the instrumented "optimized" code, which does no longer invoke UB? Or is the clang toolchain intelligent enough to not perform UB dependent optimizations when the sanitizer is specified?
UB is mostly a C concept, not a lower-level one. The semantics of assembly language programs are well-defined much more often (the only counterexample I can think of is stuff involving using threading, memory barriers, etc. incorrect)
11 : <source>:11:6: warning: no previous prototype for function 'NeverCalled' [-Wmissing-prototypes] void NeverCalled() { ^ 1 warning generated.
Or you could write correct C and use (void) instead of () as argument list.
edit: I was wrong, see below.
If an object that has automatic storage duration is not initialized explicitly, its value is indeterminate. If an object that has static or thread storage duration is not initialized explicitly, then:
— if it has pointer type, it is initialized to a null pointer;
From 3.6.2:
>Variables with static storage duration (3.7.1) or thread storage duration (3.7.2) shall be zero-initialized (8.5) before any other initialization takes place
and from 8.5:
>To zero-initialize an object or reference of type T means
>--if T is a scalar type (3.9), the object is initialized to the value obtained by converting the integer literal 0 (zero) to T
and from 3.9:
>Arithmetic types (3.9.1), enumeration types, pointer types, pointer to member types (3.9.2), std::nullptr_- t, and cv-qualified versions of these types (3.9.3) are collectively called scalar types
I remember reading an old book about implementing a compiler. The book actually recommended that compilers should make an effort to fix simple mistakes; e.g., compilers should add semicolons if needed, check whether an undefined variable or function was actually a misspelled variable or function, etc. I wasn't sure whether I should laugh at the naivety or shudder about what kind of code that would have led to. Especially given that each compiler would be lenient in different ways from competing compilers.
If the programmer intended to write a correct program, and the programmer wrote an undefined program instead, you should blame the programmer, not the compiler.
I mean, do you actually know which one you'd turn off and what the pros and cons are. Not just answer like "of course, whichever one caused this behavior!"
I'm asking because I noticed nobody who rants about compiler behavior on UB code actually seems to have a detailed understanding of what they're talking about. They always seem to just be shooting from the hip.