Hacker News new | comments | ask | show | jobs | submit login
What you get is what you C: Controlling side effects in mainstream C compilers [pdf] (cam.ac.uk)
95 points by gbrown_ 9 months ago | hide | past | web | favorite | 66 comments



> For example, divisions by zero are considered UB [undefined behavior], so a compiler can assume the divisor is always non-zero (Chapter 6.5.5). This means code that checks the value of the divisor prior to a division can be removed by a compiler

C's "undefined behavior" rules are insanity of the highest order, bordering on professional malpractice. They are the result of the pursuit of speed at the expense of all else. This might have been acceptable in 1973. It should not even be contemplated in 2018.


I don't disagree, but I feel "code that checks the value of the divisor prior to a division can be removed by a compiler" needs clarification: it's not as insane as it sounds.

The example given in the referenced paper[1] for this is:

    if (arg2 == 0)
        ereport(/* ... */);
    PG_RETURN_INT32((int32) arg1 / arg2);
The compiler re-ordered the instructions and performed the division before the check, but only because it didn't know "ereport()" couldn't return (so the compiler thought the division would happen either way). If the code had been:

    if (arg2 != 0)
        PG_RETURN_INT32((int32) arg1 / arg2);
    ereport(/* ... */);
or something like it, it would have been fine.

[1] https://people.csail.mit.edu/nickolai/papers/wang-undef-2012...


I think that's just a compiler bug.


Nah, it's a valid optimization as long as ereport() returns.

The compiler doesn't need to follow the order of operations as long as the observed behavior is the same as if the operations were performed in the order in the code. Since the compiler doesn't have any responsibility if division by zero happens, it's fine to do the division before.

This is an interesting read: https://blogs.msdn.microsoft.com/oldnewthing/20140627-00/?p=...


It is a compiler bug. The compiler can't reason what the effect of dividing by zero will be, because it's undefined. Therefore, hoisting the division before the if can change the observed behaviour, because the ereport function won't be executed. Ereport may not return, or it may print a debug message, or any other manner of things that are absolutely observable program behaviour. The function should be compiled with whatever division opcode or subroutine the compiler likes, including ones that crash the program, make it loop forever, make your cpu explode, or launch nukes at North Korea, however - it cannot reorder the function call after the division, because if it crashes, the program behaviour changes.


> The compiler can't reason what the effect of dividing by zero will be, because it's undefined.

It can reason: because it's undefined, it won't happen, that is, the code will never divide by zero. Therefore, the divisor is non-zero, and so the division instruction will not trap. Which means it can be moved above the call.

If you mentally replace "undefined" with "impossible", the compiler behavior becomes more clear. And yeah, even in the absence of undefined behavior, optimizing compilers reason about impossible behavior all the time; for instance, after an "if (x == 2)", the compiler knows it's impossible for x to be 2 at the start of the else branch.


The correct reasoning would be: “Because it’s undefined, it won’t happen, that is, the code will never divide by zero. Therefore, the divisor is non-zero or the division is never executed.”

Undefined behavior can ‘go back in time’, but only to a point where the compiler can prove it will necessarily occur in the future. And there’s no language in the standard allowing compilers to assume that an arbitrary function will ever return, as opposed to terminating the program or entering an infinite loop.

There are some cases where the compiler is allowed to assume a loop will eventually terminate (one of the less widely known forms of undefined behavior), but only if the loop has no input/output or other observable effects besides spinning:

https://stackoverflow.com/questions/16436237/is-while1-undef...

Edit: And according to the linked Debian bug report thread, the problematic optimization could no longer be reproduced on newer versions of GCC.


> Undefined behavior can ‘go back in time’, but only to a point where the compiler can prove it will necessarily occur in the future.

I don't quite get what you mean here. If the compiler can prove that you perform undefined behavior, isn't it legal for it to move it to the start of the program and literally produce no output?


> If the compiler can prove that you perform undefined behavior, isn't it legal for it to move it to the start of the program and literally produce no output?

Yes, it can! (Or worse, like making it erase all your files.) But that's only if it can prove that the program will always reach the undefined behavior. The path a program takes can depend on its input, command line parameters, contents of the filesystem, or even the phase of the moon (literally: the program can ask the operating system for the current date and time, and branch on a value derived from them). If a program will only reach undefined behavior once in a blue moon, the compiler is not allowed to output an executable which will fail when ran on dates which are not considered a blue moon.


Yep. In the ereport() example, though, it’s even simpler: the program couldn’t execute undefined behavior given any input, because ereport() calls abort() if the error level is ERROR (as is the case here). There’s a statement syntactically following the ereport() which would be UB if it were executed, and since ereport isn’t marked noreturn, the compiler can’t prove that it won’t be executed. But that’s not the right standard: the optimization is only justified if the compiler can prove that it will be executed (under the assumption that control flow has reached the code whose observable behavior is being altered).

Edit: that is, with any input that causes it to be altered. The most famous cases of UB involve compilers removing code entirely or optimizing an expression to a constant, but it’s just as valid (and more useful) to replace one computation with another computation (e.g. an unsigned division with a signed division) that produces the same result for “legal” inputs, but potentially a different result for “illegal” inputs – where “illegal” means “given that input at that point in the program, the program necessarily has executed or will execute UB”. From the standard’s perspective, the question is not which instructions are generated or what computations are actually performed, but whether the observable behavior is the same “as if” the computations in the source code were performed, for all execution traces not containing UB. (Just to reword myself in increasingly verbose fashion.)


In my experience, there is no such thing as "this cannot happen" in any program with more than 100 SLOC. UB is fine as long as it's treated as "anything may happen", but definitely not as "cannot happen". There's other ways compilers can wring out more performance from current CPUs, than by pretending certain bit patterns will never occur as input to certain operations, and with ever-increasing SIMD widths, optimising code that definitely will happen, will become even more important.


> it cannot reorder the function call after the division

Actually, it can because one of the things undefined behavior can do is go backwards in time.

Undefined behavior anywhere in the program can legally make any part of the program do anything at any time.

On top of that, there is no reliable way to tell if your program contains undefined behavior.

This is madness.


> Undefined behavior anywhere in the program can legally make any part of the program do anything at any time.

This is only true if the undefined behavior is guaranteed to be reachable.

This is not true in general.

Putting "if (0) 1/0;" in a program does not cause undefined behavior.


Consider a program that reads two numbers input by the user, divides them, and prints the result. Can it really be that because it's POSSIBLE for the user to enter zero for the second number, that the compiler is allowed to replace this program by one that removes all your files (even when the user DIDN'T enter zero)?

The C standard writers may have been unwise to specify undefined behaviour the way they did, but they weren't THAT crazy!


> This is only true if the undefined behavior is guaranteed to be reachable.

Nope. It's true if the UB is possibly reachable.

See: https://blogs.msdn.microsoft.com/oldnewthing/20140627-00/?p=...


That article agrees with me, not you. Even in the time travel examples, the code paths unrelated to the ub can't be touched.

In other words, it can travel backward, but not sideways (which is what you originally claimed).


> Even in the time travel examples, the code paths unrelated to the ub can't be touched.

Of course they can. UB licenses the program to do anything including re-write any part of itself.


UB only licenses the program to do anything if it is reachable. Unreachable, unexecuted, cant-be-executed UB simply can't change a program's behavior. I'm not sure why you think it can.

Do you think this program can "do anything" or "re-write any part of itself"?

    unsigned int x = <input from user>;
    unsigned int y = <input from user>;
    printf("%u\n", x / y);
The compiler must output valid code for that program, and execution (not compilation) can only "do anything" if the user enters values that invoke UB (like "y == 0" for example). For all valid inputs this program must execute correctly and can not "do anything", even at runtime, do you agree?

What about this one?

    unsigned int x = <input from user>;
    unsigned int y = <input from user>;
    if (y == 0) {
      printf("%u\n", x / y);
    } else {
      printf("%u\n", x * y);
    }
Same idea: this program can only "do anything" if the user enters "y == 0". The compiler can see that "x / y" would invoke UB, and remove the entire "if (y == 0) { ... }" branch (because the compiler can assume it is never reached, otherwise it would invoke UB), but the compiler can not do anything to change the behavior of the "else" branch - entering any non-zero "y" value must produce correct output, so the program can't just be compiled to "do anything".

Only the paths related to the UB can be optimized/modified/rewritten by the compiler based on that UB, and if those optimizations or modifications affect the proper execution of paths unrelated to the UB (i.e. paths where the UB can not be reached from), then the optimization or modification in question is a compiler bug.


> UB only licenses the program to do anything if it is reachable.

That's true, but it doesn't help much.

> Do you think this program can "do anything" or "re-write any part of itself"?

Yes. Not for all inputs, but yes.

> this program can only "do anything" if the user enters "y == 0".

Nope. There is at least one other input value that produces UB.

And this is exactly the problem: even on a trivial example that you contrived, you cannot fully enumerate all the circumstances that produce UB. For real programs, the situation is hopeless.


> Not for all inputs

Which proves my point: a program can't "do anything" just because some part of it may contain UB. Only the UB paths are allowed to "do anything".

> There is at least one other input value that produces UB.

Not in my example there isn't (assuming proper context for the example code, i.e. you aren't doing "#define printf (something evil)", you include the right headers, you define main properly, etc, etc).

> And this is exactly the problem: even on a trivial example that you contrived, you cannot fully enumerate all the circumstances that produce UB

The problem is that you don't really understand UB fully and are making incorrect claims about it repeatedly.

I'm not claiming UB can't cause problems, but it doesn't cause problems in some of the ways you've been quite vocal about.


> Not in my example there isn't.

Want to bet? How much are you willing to wager? (And yes, I accept all the conditions you listed.)

> The problem is that you don't really understand UB fully

Then this is a chance for you to make some easy money.


No wager necessary, feel free to point out my mistake, if I made one. It won't prove that you know what you are talking about in general (since, as we've seen, programs really can't "do anything" if they have UB anywhere in them), but I do like to know when I make mistakes, and I'll fully own up to it if I did.


> programs really can't "do anything" if they have UB anywhere in them

I never said they could.

> I do like to know when I make mistakes

I doubt that very much, but let's do the experiment:

Here is one of your many mistakes:

"Even in the time travel examples, the code paths unrelated to the ub can't be touched."

That's simply not true. UB licenses a program to do anything, including overwriting itself. Which means that the compiler can anticipate this and emit arbitrary code.

Now, you might, if you are very very careful, be able to construct a program that contains UB that is guaranteed to behave as intended for some non-zero time interval. You might even be able to construct a program that contains no UB at all, though this is even more challenging. Writing a non-trivial C program that contain no UB is practically impossible. I doubt there is even a single such program in existence in the world today. Your trivial examples both contain UB. And no, I'm not going to tell you what it is because that would be missing the point. The point is not that I know some detail of the C standard that you have overlooked (though that is in fact true). The point is that you think you can write correct C code, and you can't. No one can.

> I'll fully own up to it if I did.

I doubt that very much too, but I'm ready to be surprised.


> UB licenses a program to do anything

Only if it is reachable under the given inputs. We've gone over this, and you were on the right track a few comments up. Why revert now?

> Writing a non-trivial C program that contain no UB is practically impossible > The point is that you think you can write correct C code

We happen to agree on both of these points, but I'm not sure how you got on this topic? Let's stay focused...

> And no, I'm not going to tell you what it is because that would be missing the point.

That's about what I expected, since there's no UB in my example.

Good day!


> Only if it is reachable under the given inputs

Yes, I already conceded that.

> there's no UB in my example

Then here is an opportunity for you to show me up and make some easy money. How much are you willing to bet?


I would wager quite a bit (I wager my career on things like this daily), but based on the ability for you to communicate effectively and based on facts thus far, I'm not entirely convinced that when you end up being wrong, you'd accept it, understand it, and pay up.

The ball's in your court man. Posturing around a wager is just you flailing around, empty handed.


Well, you would have won. I was thinking of this:

https://spin.atomicobject.com/2014/05/19/c-undefined-behavio...

but I just noticed that you actually specified your ints to be unsigned. So I would have lost. (And I would have paid.)


Thanks for coming clean.


> I never said they could.

I almost missed this one! Here's some choice quotes for you:

From https://news.ycombinator.com/item?id=16917162

> "Undefined behavior anywhere in the program can legally make any part of the program do anything at any time."

and from https://news.ycombinator.com/item?id=16917551

> "It's true if the UB is possibly reachable."


Yeah, yeah, there is a special case that if the UB is not reachable then it's a no-op. That doesn't change the fact that writing correct non-trivial C code is practically impossible.


No argument here, I'm just trying to keep the facts straight; I have no opinion on right/wrong/good/bad/easy/hard (at least, not in this forum).


See my response to a sibling comment of yours making a similar point. It can only go back in time to a point where execution of undefined behavior is inevitable; it doesn’t count if the program aborts first:

https://news.ycombinator.com/item?id=16917302


On that last point, check out Rosu et al's KCC: an executable, formal semantics of C that addresses undefined behavior.

https://github.com/kframework/c-semantics/blob/master/README...


Undefined behaviour can be tricky, but I don't think it is THAT tricky. If a check for a divisor of zero done before a division could be eliminated, programming would become completely impossible.

On the other hand, code that does the division first, and AFTER that checks whether the divisor was zero, could fall prey to the dreaded undefined behaviour optimization...



OK, what lesson exactly am I supposed to take away from this? Because the last sentence in that post is exactly my point:

"... undefined behavior in C is a pretty scary thing if performance is not your only goal."


You mentioned this:

> C's "undefined behavior" rules are insanity of the highest order, bordering on professional malpractice. They are the result of the pursuit of speed at the expense of all else.

C's goal is performance (though not necessarily at the expense of all else). It's the compiler's job to make code that is as fast as possible. The article I linked was an attempt to show that it is very difficult to both have this goal as well as one in which you don't have "insane" undefined behavior. It's not that the C compiler authors are out to get you: "ha ha, lipser used undefined behavior! Let's break his code in the weirdest way"; rather, this seemingly poor behavior is borne out of a desire to have reasonable rules. Allowing the compiler to assume that a run runs ten times or that a pointer doesn't randomly change between statements is important.


> It's the compiler's job to make code that is as fast as possible.

This doesn't used to be the case, or we would have had something more like FORTRAN, with less pointers that alias all over the place. C was build so the programmer could optimise the program. The design of C was pretty hostile to compiler optimisations, to the point that some PL researchers say its wide adoption set us back decades.

It's only later that compilers started to really optimise stuff themselves. And they used undefined behaviour to do so. Signed integer overflow UB for instance was used to optimised `for` loops, thus compensating the verbose, hard to optimise original design.

> It's not that the C compiler authors are out to get you

The end result is the same. "Oh, this code leads to undefined behaviour. Let's pretend it's dead, it will be faster that way".

Apply that to reasonable looking, yet incorrect, safety checks (like checking for integer overflow after the fact), and just like that you have a buffer overflow and an arbitrary code execution exploit.


And the biggest issue is that the code producing UB might not even be visible to the programmer.

It might only visible to the optimizer after applying a few inlining and code transformations before reaching the UB analysis.


> It's the compiler's job to make code that is as fast as possible.

This is simply wrong, but it absolutely is the misunderstanding that is driving this.

It is not the compiler's job to make code that is as fast as possible.

If anything, that is the developer's job.

The compiler's job is to make the developer's job easier, not to second-guess her.


not just speed but "portable assembly" if architectures get to decide what to do on ÷0 then by golly so does a C compiler (never mind that those differences make C less portable).


> insanity of the highest order, bordering on professional malpractice.

Hear, hear!

> might have been acceptable in 1973

The irony being that compilers in, well, 1983-ish did not pull these kinds of stunts.


Well, C compilers required some ways to catch up with optimizers in other programming languages with better type information, as Fran Allen complained a few times.


Surely there are still applications in 2018 that require speed at the expense of all else. Perhaps not as many, but there are bound to be some.


Like what?

Seriously... what do you want to run for which you would be willing to risk data corruption, or a hacker pwning your machine, in exchange for it running faster? Because that's what we're really talking about here.


I agree with you. But this quote is badly written by the author -- they should have clarified further. In fact, compilers don't remove check of divisors that prevents div-by-0 precisely for this reason. What the authors mean is someting like this:

>if (!msize) msize = 1 / msize; // provoke a signal


This is great stuff; if I were ever to write a language this sort of side-effect control is something I would like to include.

That being said, I'm bit surprised how much effort developers put into "tricking" C compilers; one would think that writing pieces of (inline) assembly would provide the desired effect while being both easier and more robust. At least it feels like in many cases the developers have some idea on what the desired code is. Maybe there are some subtleties that I am missing?


Assembly is presumably harder to write, audit, and port to other platforms.


Assembly is not portable.


Are the tricks portable?


"portable" in the sense that the compiler will produce the proper assembly for the platform - choice of x86, ARM, MIPS, 32/64 bit, etc. Whether the "tricks" behave identically across all platforms depends on the trick, I think.


Usually those tricks are not even portable across compilers on the same platform.

It suffices a change on compiler version with optimizer improvements, or using another vendor's compiler for the tricks to fall apart.

In a gigantic code base, with rotating developers, it becomes a very "fun" thing to debug.


>Usually those tricks are not even portable across compilers on the same platform.

That's much less of an issue. If it can work on GCC for example or Clang across platforms, you're OK for tons of platforms, even if you can't change compilers intra-platform.


Would be interesting to see this applied to Rust. Obviously physical side-effect attacks (timing, EM) are still a concern and LLVM optimisations need to be considered as with the Clang toolchain, but massive swathes of UB are eliminated when compared to C.


On x86 CPUs, working with latest compilers in -O3 optimization level is becoming like working with old RISC CPUs without hardware for unaligned load/store: except if you write your code using memcpy/memmove for unaligned load/store, you'll get caught by some crash. E.g. in x86-64 in -O3 GCC emits SIMD instructions that can crash your code if not properly aligned. E.g. the typical cast to 32 or 64 bit that worked in C on x86 processors, is no longer guaranteed to work:

uint8_t * p = some_address_not_aligned;

uint32_t i = * (uint32_t *)p;

In order to be safe previous code should be replaced by:

memcpy(&i, p, sizeof(uint32_t));

(the compiler is smart enough for inlining the above memcpy call, so is as fast as the previous case)


uint32_t is aligned on a 4-byte boundary, so the compiler optimisation is actually valid in this case. Reading from a misaligned pointer is not guaranteed to work.


E.g. the typical cast to 32 or 64 bit that worked in C on x86 processors, is no longer guaranteed to work:

Sorry to disappoint you, but this fragment of code was never guaranteed to work by the C standard, and x86 is a special case where it might work (but is not guaranteed to!). I hope you didn't make such type punning mistakes in the code you've written so far. A memcpy is always necessary to transform 4 bytes in an (unaligned) char array into a 32-bit integer. And yes, it all gets optimised away. At the end of the day, if you do it with memcpy, you end up with literally the same assembly as when you use a type cast, at least on GCC last time I tried. Still, it's good to not cause undefined behaviour.


I don't know why this comment was killed: it's correct. The code above violates the C standard, so you're luckily that it even crashes at all rather than doing something even worse like masking to a 4-byte boundary.


"was never guaranteed to work by the C standard"

It was, on x86, before of compilers emitting opcodes not supporting unaligned memory accesses, because x86 CPUs guaranteed safe operation on unaligned memory accesses.

Don't get me wrong, of course it is a good practice writing code not relying on CPU-specific characteristics. The problem is that there is a ton of software for x86 that becomes not reliable when recompiled with -O3 on x86-64 (with hard to catch situations, e.g. passing tests, but with random crashes depending on the data being handled, etc.).


What do you mean by "guaranteed"? Was there some specification (e.g. compiler manual or so) that said it?

Or did you rely on not-specified behavior?

If it's the latter, I wouldn't call that "guaranteed".


Intel CPUs guaranteed correct operation on unaligned accesses. In fact, back in the day, transparent unaligned memory access support, and a strong memory model for SMP, were very strong selling points for Intel vs most RISC vendors.

The "problem" on Intel CPUs started when SIMD instructions not supporting unaligned memory were being used for optimizing generic code. Which is a very good thing, of course. The only problem is that there is many bad quality code around that was written with the assumption of x86 CPUs being "safe" in that regard.


That's fine if you're writing assembly.

Compilers are free to use UB from the standard to optimize and absolutely do not guarantee you to emit machine loads and store naively as specified in the C source.

At least for clang I'm pretty sure they decided _not_ to give knowledge of, e.g., the zero low bits of an int pointer to the optimizer since many people are relying on it. That might not be the case in the future or another compiler.

Here is a thread discussing that http://lists.llvm.org/pipermail/llvm-dev/2016-January/094012...


Sure. And I love compilers generating very fast code. My point was that there is a ton of code written for x86 on assumptions that are no longer true when compiled with -O3 flags. Fortunately, open source code is less affected because usually target the generic case. However, for private code is a huge problem and risk. In my opinion, code intended to operate on x86 processors should be compiled with -O3 only in the case of high quality software, and if the quality can not be assured, it should be compiled with -O2 (at least when compiled with GCC and CLang).


The problem is the same as it's always been. C made no guarantees about a specific behavior in some cases, but people learned that a specific compiler and platform combination exhibited specific behavior in those cases, so took advantage of that to write code that used that exhibited behavior. Then the chickens came home to roost as the platforms added new capabilities and the compilers changed, in completely spec compliant ways, mind you, to take advantage of those capabilities.

There seems to be a lot of C code written not to spec, but to empirically observed behavior in the wild. People writing "incorrect" programs that function by happenstance isn't new, and the assumptions made when they were written were never true, they just happened to conform to (wrong) expectations for a while.


You still see this a lot nowadays, specially those that only use gcc and clang, without experience writing actual portable C code.


I think you're agreeing with what everyone else is saying now - there never was any "guarantee", there was just "bad quality code around that was written with the assumption." This wasn't guaranteed to work from C either, since compilers were still free to do things like assume that the bottom two bits of a uint32_t * were zero.

However, probably -mno-sse or something will solve your problem (where "your problem" is defined as "Intel used to guarantee something in one of its ways of handling data, and in a newer architecture revision, they introduced a faster mechanism for the same calculations that no longer guarantees it.")




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: