Absolutist statements such as this may give you a glowing sense of superiority and cleverness, but they contribute nothing and are not as clever as you think.
Yes but his examples are about churn in code that makes assumptions that neither the language nor the compiler guarantees. It's not at all surprising that if your code depends on coincidental properties of your compiler that compiler upgrades might break it. You can't build your code on assumptions and then blame others when those assumptions turn out to be false. But then again, it's perhaps not too surprising that cryptographers would do this since their entire field depends on unproven assumptions.
A general policy change here makes no sense because most language users do not care about constant runtime and would rather have their programs always run as fast as possible.
Personally I'm grateful the cryptographers do what they do, computers would be a lot less useful without their work.
So the only possible way to ensure things like string comparison don't have data-dependent timing is often to implement it in assembly, which is not great.
What we really need is intrinsics that are guaranteed to have the desired timing properties , and/or a way to disable optimization, or at least certain kinds of optimization for an area of code.
I'm sure you know who DJB is.
But yeah, seeing how virtually everyone on every road is constantly speeding, that doesn't give me a lot of faith in my fellow programmers' ability to avoid UB...
(I'm one of those speeders, too; I drive with a mentality of safety > following the strict letter of the law; I'll prefer speed of traffic if that's safer than strict adherence to the limit. That said, I know not all of my peers have the same priorities on the road, too.)
The tone of my answer is a reflection of what most surveys state, related to the actual use of such tooling.
The problem with this is that no general purpose compiler wants to tie its own hands behind its back in this way, for the benefit of one narrow use case. It's not just that it would cost performance for everyone else, but also that it requires a totally different approach to specification and backwards compatibility, not to mention deep changes to compiler architecture.
You almost may as well just design a new language, at that point.
Forget “almost”.
Go compile this C code:
void foo(int *ptr)
{
free(ptr);
*ptr = 42;
}
This is UB. And it has nothing whatsoever to do with optimizations — any sensible translation to machine code is a use-after-free, and an attacker can probably find a way to exploit that machine code to run arbitrary code and format your disk.If you don’t like this, use a language without UB.
But djb wants something different, I think: a way to tell the compiler not to introduce timing dependencies on certain values. This is a nice idea, but it needs hardware support! Your CPU may well implement ALU instructions with data-dependent timing. Intel, for example, reserves the right to do this unless you set an MSR to tell it not to. And you cannot set that MSR from user code, so what exactly is a compiler supposed to do?
https://www.intel.com/content/www/us/en/developer/articles/t...
void foo(int *ptr)
{
assert(ptr != NULL);
free(ptr);
assert(ptr != NULL);
}
Why is that? Well, I think because the C standard authors wanted to support the language being used on platforms with "fat pointers", in which a pointer is not just a memory address, but some kind of complex structure incorporating flags and capabilities (e.g. IBM System/38 and AS/400; Burroughs Large Systems; Intel iAPX 432, BiiN and i960 extended architecture; CHERI and ARM Morello). And, on such a system, they wanted to permit implementors to make `free()` a "pass-by-reference" function, so it would actually modify the value of its argument. (C natively doesn't have pass-by-reference, unlike C++, but there is nothing stopping a compiler adding it as an extension, then using it to implement `free()`.)See this discussion of the topic from 8 years back: https://news.ycombinator.com/item?id=11235385
> And you cannot set that MSR from user code, so what exactly is a compiler supposed to do?
Set a flag in the executable which requires that MSR to be enabled. Then the OS will set the MSR when it loads the executable, or refuse to load it if it won't.
Another option would be for the OS to expose a user space API to read that MSR. And then the compiler emits a check at the start of security-sensitive code to call that API and abort if the MSR doesn't have the required value. Or maybe even, the OS could let you turn the MSR on/off on a per-thread basis, and just set it during security-sensitive processing.
Obviously, all these approaches require cooperation with the OS vendor, but often the OS vendor and compiler vendor is the same vendor (e.g. Microsoft)–and even when that isn't true, compiler and kernel teams often work closely together.
gcc did approximately this for decades with -ffast-math. It was an unmitigated disaster. No thanks. (For flavor, consider what -lssl would do. Or dlopen.)
> Another option would be for the OS to expose a user space API to read that MSR. And then the compiler emits a check at the start of security-sensitive code to call that API and abort if the MSR doesn't have the required value.
How does the compiler know where the sensitive code starts and ends? Maybe it knows that certain basic blocks are sensitive, but it’s a whole extra control flow analysis to find beginning and ends.
And making this OS dependent means that compilers need to be more OS dependent for a feature that’s part of the ISA, not the OS. Ick.
Or maybe even, the OS could let you turn the MSR on/off on a per-thread basis, and just set it during security-sensitive processing.
Put an attribute on the function. In C23, something like `[[no_data_dependent_timing]]` (or `__attribute__((no_data_dependent_timing))` using pre-C23 GNU extension)
> And making this OS dependent means that compilers need to be more OS dependent for a feature that’s part of the ISA, not the OS. Ick.
There are lots of unused bits in RFLAGS, I don't know why Intel didn't use one of those, instead of an MSR. (The whole upper 32 bits of RFLAGS is unused – if Intel and AMD split it evenly between them, that would be 16 bits each.) Assuming the OS saves/restores the whole of RFLAGS on context switch, it wouldn't even need any change to the OS. CPUID could tell you whether this additional RFLAGS bit was supported or not. Maybe have an MSR which controls whether the feature is enabled or not, so the OS can turn it off if necessary. Maybe even default to having it off, so it isn't visible in CPUID until it is enabled by the OS via MSR – to cover the risk that maybe the OS context switching code can't handle a previously undefined bit in RFLAGS being non-zero.
One of the advantages of rust is it confines any potential UB to unsafe blocks. But even in rust, which has defined behavior in a lot of places that are UB in c, if you venture into unsafe code, it is remarkable easy to accidentally run into subtle UB issues.
Because, me despite knowing both since the 1990's, I rather leave that to static analysis tools.
You also have languages using immutable or persistent data structures in their std lib to side-step the problem.
They are in the process of rewording such cases as erroneous instead of UB, but it will take time.
If it's simply erroneous, then it behaves like in every other language outside C and C++: it leaves memory in a bad state if it happens at runtime, but it doesn't have any effect at compile time.
For example, if you do an out of bounds write in C, you can set some part of an object to a value it never should have according to the text of the program, simply because that object happened to be placed in memory next to the array that you wrote past the end of.
According to the semantics of the C abstract machine, the value of a non-volatile object can only change when it is written to. But in a real program, writes to arbitrary memory (which are not valid programs in C's formal semantics) can also modify C objects, which would be called a "bad state".
For example, take this program, and assume it is compiled exactly as written, with no optimizations at all:
void foo() {
int x = 10;
char y[3];
y[4] = 1;
printf("x = %d", x);
}
In principle, this program should print "10". But, the OOB write to y[4] might overwrite one byte of x with the value 1, leading to the program possibly printing 1, or printing 266 (0x010A), or 16777226 (0x0100000A), depending on how many bytes an int has and how they are laid out in memory. Even worse, the OOB write may replace a byte from the return address instead, causing the program to jump to a random address in memory when hitting the end of the function. Either way, your program's memory is in a bad state after that instruction runs.If you want an example of something that is not UB leaving memory in a bad state, here is some Go code:
global := 7;
func main () {
go func() {
global = 1000000;
}()
go func() {
global = 10
}()
fmt.Printf("gloabl is now %d")
}
The two concurrent writes may partially overlap, and global may have a value that is neither 7 nor 10 nor 1000000. The program's memory is in a bad state, but none of this is UB in the C or C++ sense. In particular, the Go compiler is not free to compile this program into something entirely different.Edit: I should also note that a similar C program using pthreads or win32 threading for concurrent access is also an example of a program which will go into a bad state, but that is not UB per the C standard (since the C standard has no notion of multithreading).
It would help if there was better tooling for finding places that could result in UB.
[1]: although some of them can be a little surprising, like the fact that overflow is defined for unsigned types but not signed types
Even today you may find issues with signed integers. The ESP32 vector extensions seem to saturate signed integer overflow [1].
[1]: https://bitbanksoftware.blogspot.com/2024/01/surprise-esp32-...
As I said, Google does not prioritize for technical expertise, primarily because that's quite individual-centric. They're a large organization and their goal is to make sure people are formatted and replaceable.
They hire generally smart people and mold them to solve problems with the frameworks that they've previously built, with guidelines that are set such that anyone can come and pick it up and contribute to it, in order to facilitate maintenance in case of turnover or changing teams.
They also hire a lot of people straight out of university, with many people spending large portions of their career there without seeing much of the outside world.
As a result, their workforce is not particularly adept about using third-party tools in a variety of situations; they're optimized to know how things work at Google, which is its own sub- (or arguably mono-)culture.
Being an expert requires using a tool in many diverse codebases for widely different applications and domains. A large organization like this is not a particularly good data point to assess whether people can become good experts knowledgeable about the gotchas of a programming language.
Why else would corporations be the exclusive authors of "middle-level" languages like Java, C#, and Go? ;p JS and Python are too slow, but we can't find enough C, C++, or Rust developers! Let's invent these abominations instead with which we can churn out more good-enough mediocrity per quarter than ever before!
Are about C++. There's an order of magnitude difference in the cognitive level to visually spot UB in C code and in C++ code.
For every C operation you type, ask yourself what is its "contract", that is, what are the preconditions that the language or the library function expects the programmer to ensure in order for their behavior to be well-defined, and do you ensure them at the particular usage point? Also, what are the failure modes within the defined behavior (which result in values or states that may lead to precondition violations in subsequent operations)? This contractual thinking is key to correctness in programs in general, not just in C. The consequences of incorrect code are just less predictable in C.
Maybe you can argue that C doesn't have a “ridiculous amount” of UB (even though the number is large), but C++ is so much worse I don't think saying it's “ridiculous” is off the mark.
And not only the amount is already ridiculous but every new feature introduced in modern versions of C++ adds its own brand new UB!
IIRC the overflow in SHA3's reference implementation was hard to catch also for ststic analisys tools, and had the practical impact of making it easy to generate collisions.
You're basically saying that every project in the wild has bad “coding strategy”…
> I expect that we will have full bounds safety options in compilers soon
Which will be disabled in most places because of the overhead it incurs.
> But having a good ownership model and good abstractions also avoids most problems here in my experience. I rarely have actual problems in my projects related to this.
It's easier said than done when you have no way of enforcing the ownership, and practically intractable when not working alone on a codebase.
It's not about crash at all, but “all software has security vulnerabilities because of UB” is unfortunately true.
> It is not intractable, in my experience you just have to document some rules and occasionally make sure they are followed.
If even DJB couldn't get that part perfectly I'm pretty certain you cannot either.
2. Sandbox escapes are commonplace, and not everything can even be sandboxed at all.
You're right, only software that has actual users cares about security.
> I run a lot of large simulations. I do not care at all if that software would crash on specially prepared inputs.
But it's not the 50s anymore and digital simulation is a tiny fraction of the code ever written nowadays so it's not a very good argument.
> I do care that it's as fast as possible.
You don't realize it but it ruins your entire argument. If speed is all that matters for your use-case then:
- there's no way you can use runtime bound-checks, and you unconditionally need the compiler to optimize as much as possible around UB, even if it breaks your program every once in a while.
- you likely can't afford dynamic memory allocation, which makes the UAF/double free kind of bugs irrelevant. Not out of “good coding strategy” but because you never free in the first place…
These are hypothesis that don't apply to software industry at large.
But the amount of actual problems I have with UB in typical projects is very low by just some common sense and good use of tools: continuous integration with sanitizers, using pointers to arrays instead of raw pointers (where a sanitizer then does bounds checks), avoiding open coded string and buffer operations, also abstracting away other complicated data structures behind safe interfaces, and following a clear policy about memory ownership.
Making sure you have no UB certainly slows you down considerably, and I strongly prefer languages that can catch all non-defined behavior statically for sure, but I don’t find C to be unmanageable.
Memory alignment issues only happen when you cast pointers from the middle of raw memory to/from other types, which, yes, is dangerous territory, and you have to know what you are doing there.
Is it annoying if you want to make sure your code compiles the same in different compiler sets? Sure, but that's part of the the issue with the standards body and the compiler developers existing independent of each other. Especially considering plenty of times C/C++ have tried to enforce certain niche behaviors and GCC/ICC/Clang/etc have decided to go their own ways.
All modern C and C++ compilers use the potential of UB as a signal in their optimization options. It is 100% unpredictable how a given piece of code where UB happens will actually be compiled, unless you are intimately familiar with every detail of the optimizer and the signals it uses. And even if you are, seemingly unrelated changes can change the logic of the optimizer just enough to entirely change the compilation of your UB segment (e.g. because a function is now too long to be inlined, so a certain piece of code can no longer be guaranteed to have some property, so [...]).
Your example of signed integer overflow is particularly glaring, as this has actually triggered real bugs in the Linux kernel (before they started using a compilation flag to force signed integer overflow to be considered defined behavior). Sure, the compiler compiles all signed integer operations to processor instructions that result in two's complement operations, and thus overflow on addition. But, since signed integer overflow is UB, the compiler also assumes it never happens, and optimizes your program accordingly.
For example, the following program will never print "overflow" regardless of what value x has:
int foo(int num) {
int x = num + 100;
if (x < num) {
printf("overflow occured");
}
return x;
}
In fact, you won't even find the string "overflow" in the compiled binary, as the whole `if` is optimized away [0], since per the standard signed integer overflow can't occur, so x + 100 is always greater than x for any (valid) value of x.This is shifting though, e.g. GCC now has -fanalyzer. I does not detect this specific coding error though, but for example issues such as dereferencing a pointer before checking for null.
if(DEBUG) {
log("xyz")
}
Should the compiler emit a warning for such code? Compilers don't behave like a human brain, maybe a specific diagnostic could be added by pattern matching the AST but it will never catch every case.A dead code report would be a useful thing, though, especially if it could give the reason for removal. (Something like the list of removed registers in the Quartus analysis report when building for FPGAs.)
#define DEBUG i<num+100
The example is silly, but you should get the point. DEBUG can be anything.(And if DEBUG is a static define then it still won't result in dead code since the preprocessor will remove it, and the compiler will never actually see it.)
EDIT: and now I realise I misread the first example all along - I read "#if (DEBUG)" rather than "if (DEBUG)".
Not really, that’s the problem. After many passes of transforming the code through optimization it is hard for the compiler to tell why a given piece of code is dead. Compiler writers aren’t just malicious as a lot of people seem to think when discussions like this come up.
It's "dead wrong" that compilers independently choose to define undefined behavior?
Oh, ok; I guess I must just be a stellar programmer to never have received the dreaded "this is undefined" error (or it's equivalent) that would inevitably be emitted in these cases then.
They don't throw errors when UB happens, they compile your program under the assumption that any path that would definitely lead to UB can't happen at runtime.
I believe you think that because signed integer addition gets compiled to the `add` instruction that overflows gracefully at runtime, this means that compilers have "defined signed int overflow". I showed you exactly why this is not true. You can't write a C or C++ program that relies on this behavior, it will have optimizer-induced bugs sooner or later.
You seem to think I'm saying "undefined behavior means nothing, ignore it"; when what I'm actually saying is "undefined behavior doesn't mean the compiler hasn't defined a behavior and doesn't necessarily = 'bad'". There's dozens of "UB" that C (and C++) developers rely on frequently, because the compilers have defined some behavior they follow; to the point critical portions of the Linux Kernel rely on it (particularly in the form of pointer manipulations).
TL;DR - Is UB unsafe to rely on generally? Yes. Should you ignore UB warnings? Definitely not. Does UB mean that the compiler has no idea what to do or is lacking some consistent behavior? Also, no.
Know your compiler, and only write code that you know what it does; especially if it's in a murky area like "UB".
> The excuse for not taking responsibility is that there are "language standards" saying that these bugs should be blamed on millions of programmers writing code that bumps into "undefined behavior", rather than being blamed on the much smaller group of compiler writers subsequently changing how this code behaves. These "language standards" are written by the compiler writers.
> Evidently the compiler writers find it more important to continue developing "optimizations" than to have computer systems functioning as expected. Developing "optimizations" seems to be a very large part of what compiler writers are paid to do.
The argument is that the compiler writers are themselves the ones deciding what is and isn't undefined, and they are defining those standards in such a way as to allow themselves latitude for further optimizations. Those optimizations then break previously working code.
The compiler writers could instead choose to prioritize backwards compatibility, but they don't. Further, these optimizations don't meaningfully improve the performance of real world code, so the trade-off of breaking code isn't even worth it.
That's the argument you need to rebut.
Here's a nine-year-old comment from the author asking for exactly that:
https://groups.google.com/g/boring-crypto/c/48qa1kWignU/m/o8...
>The only thing stopping gcc from becoming the desired boringcc is to find the people willing to do the work.
And frankly, nine years is enough time to build a C compiler from scratch.
The examples they give are all perfectly valid code. The specific bugs they're talking about seem to be compiler optimizations that replace bit twiddling arithmetic into branches, which isn't a safe optimization if the bit twiddling happens in a cryptographic context because it opens the door for timing attacks.
I don't think it's correct to call either the source code or compiler buggy, it's the C standard that is under specified to the author's liking and it creates security bugs on some targets.
Ultimately though I can agree with the C standard authors that they cannot define the behavior of hardware, they can only define the semantics for the language itself. Crypto guys will have to suffer because the blame is on the hardware for these bugs, not the software.
You don't need to rely on C to guarantee some behaviour forever.
But we have generally the problem that there are far more people complaining that actually contributing usefully to the ecosystem. For example, I have not seen anybody propose or work on such an extension for GCC.
You need a language where you can express what you actually meant, which in this case is "Perform this constant time operation". Having expressed what you meant, now everybody between you and the hardware can co-operate to potentially deliver that.
So long as you write C (or C++) you're ruined, you cannot express what you meant, you are second guessing the compiler authors instead.
Yeah, even with assembly, your timing guarantees are limited on modern architectures. But if you REALLY need something specific from the machine, that's where you go.
Even most managed languages provide a way to get down into Assembly dumps from their AOT and JIT compiler toolchains.
Maybe we need some TikTok videos showing how to do such workflows.
If you are doing really low level stuff, sometimes it’s worth rolling out your own little RTOS with just the bits and pieces you need.
Not that long ago, I realised most 8-bit (and MS-DOS) computer games had their own RTOS woven into the game code, with multi-tasking, hardware management, IO, and so on.
CPUs are actually much better at making those guarantees than compilers are.
https://lore.kernel.org/all/851920c5-31c9-ddd9-3e2d-57d379aa...
In other words, they have announced the possibility of breaking that guarantee years before touching it, which is something the clang developers would never do.
This notion is not expressible in most (or almost all) high-level programming languages. Or, to put it another way: If you wrote C or C++ you never mean to say "perform this guaranteed-constant-time CPU operation" (ignoring asm instructions and hardware-aware builtins).
Isn't this unreasonable? Here we are, 52, years down the road with C et al. and suddenly it's expected that compiler developers must consider any change in the light of timing attacks? At what point do such new expectations grind compiler development to a halt? What standard would a compiler developer refer to to stay between the lines? My instincts tell me that this would be a forever narrowing and forever moving target.
Does timing sensitivity ever end? Asked differently: is there any code that deals in sensitive information that can't, somehow, be compromised by timing analysis? Never mind cryptographic algorithms. Just measuring the time needed to compute the length of strings will leak something of use, given enough stimuli and data collection.
Is there some reason a cryptographic algorithm developer must track the latest release of a compiler? Separate compilation and linking is still a thing, as far as I know. Such work could be isolated to "validated" compilers, leaving the insensitive code (if that concept is even real...) to whatever compiler prevails.
Also, it's not just compilers that can "optimize" code. Processing elements do this as well. Logically, therefore, must we not also expect CPU designers to also forego changes that could alter timing behavior? Forever?
I've written a lot of question marks above. That's because this isn't my field. However, invoking my instincts again: what, short of regressing to in-order, non-speculative cores and freezing all compiler development, could possibly satisfy the expectation that no changes are permitted to reveal timing differences where it previously hadn't?
This all looks like an engineering purity spiral.
We already went through a similar case to this: when the C++11 multithreaded memory model was introduced, compiler authors were henceforth forced to consider all future optimizations in light of multithreading. Which actually forced them to go back and suppress some optimizations that otherwise appeared reasonable.
This isn't to say the idea is good (or bad), but just that "compiler development will grind to a halt" is not a convincing against it.
It would be reasonable to implement (and later standardize) a pragma or something that specifies timings constraint for a subset of the language. But somebody would need to do the work.
I'm sort of reminded of the software people vs. hardware people stuff in embedded work, where ideally you'd have people around who'd crossed over from one to another but (comparing to crypto authors and compiler authors) there's enough of a cultural disconnect between the two groups that it doesn't happen as often as one might prefer.
I do wonder though how often cpu instructions have data-dependent execution times....
Tracking the latest release is important because:
1. Distributions build (most? all?) libraries from source, using compilers and flags the algorithm authors can't control
2. Today's latest release is the base of tomorrow's LTS.
If the people who know most about these algorithms aren't tracking the latest compiler releases, then who else would be qualified to detect these issues before a compiler version bearing a problematic optimization is used for the next release of Debian or RHEL?
> Logically, therefore, must we not also expect CPU designers to also forego changes that could alter timing behavior?
Maybe? [1]
> freezing all compiler development
There are many, many interesting areas of compiler development beyond incremental application of increasingly niche optimizations.
For instance, greater ability to demarcate code that is intended to be constant time. Or test suites that can detect when optimizations pose a threat to certain algorithms or implementations. Or optimizing the performance of the compiler itself.
Overall I agree with you somewhat. All engineers must constantly rail against entropy, and we are doomed to fail. But DJB is probably correct that a well-reasoned rant aimed at the community that both most desires and most produces the problematic optimizations has a better chance at changing the tide of opinion and shifting the rate at which all must diminish than yelling at chipmakers or the laws of thermodynamics.
[1]https://en.m.wikipedia.org/wiki/Spectre_(security_vulnerabil...
I guess you are referring to a GPU cores here.
It is a joke but can hint that in-order non-speculative cores are powerful computers nonetheless.
This seems a lot more sane than trying to retrofit these concerns onto the entire stack of general purpose hardware and software.
EDIT: just to make my point clear: the problem with UB isn't just that it exists, it is also that compiler optimizations make it hard to check for it.
Undefined behaviour isn't exactly what most people think it is.
Nicely put, but at the end perfectionism is a flaw.
For example, you might suspect that the NSA has a better sieve than the public, and conclude that your RSA key needs to be a full terabyte*. We know that this isn't perfect, of course, but going much beyond that key length will prevent your recipient from decrypting the message in their lifetime.
* runtime estimates were not performed to arrive at this large and largely irrelevant number
To get philosophical for a second, all of engineering is analyzing problems and synthesizing solutions. When faced with impossible problems or infinite solution space, we must constrain the problem domain and search space to find solutions that are physically and economically realizable.
That's why the answer to every one of your questions is, "it depends."
But at the top, yes, it's unreasonable. The C standard specifies the observable behavior of software in C. It does not (and cannot) specify the observable behavior of the hardware that evaluates that software. Since these behavior are architecture and application specific, it falls to other tools for the engineer to find solutions.
Simply put, it isn't the job of the C standard to solve these problems. C is not a specification of how a digital circuit evaluates object code. It is a specification of how a higher level language translates into that object code.
1) This is a bad idea and refuse to compile.
2) Do something sensible and stable.
Silently fail and generate impossible to predict code is a third model that is only of use to compiler writers. Hiding behind the spec benefits no actual user.
some_array[i]
What should the compiler emit here? Should it emit a bounds check? In the event the bounds check fails, what should it do? It is only through the practice of undefined behavior that the compiler can consistently generate code that avoids the bounds check. (We don't need it, because if `i` is out-of-bounds then it's undefined behavior and illegal).If you think this is bad, then you're arguing against memory unsafe languages in general. A sane position is the one the Rust takes, which is by default, yes indeed you should always generate the bounds check (unless you can prove it always succeeds). But there will likely always be hot inner loops where we need to discharge the bounds checks statically. Ideally that would be done with some kind of formal reasoning support, but the industry is far that atm.
For a more in depth read: https://blog.regehr.org/archives/213
It should emit an instruction to access memory location some_array + i.
That's all most people that complain about optimizations on undefined behavior want. Sometimes there are questions that are hard to answer, but in a situation like this, the answer is "Try it and hope it doesn't corrupt memory." The behavior that's not wanted is for the compiler to wildly change behavior on purpose when something is undefined. For example, the compiler could optimize
if(foo) {
misbehaving_code();
return puppies;
} else {
delete_data();
}
into delete_data();That's definitely what compilers emit. The UB comes from the fact that the compiler cannot guarantee how the actual memory will respond to that. Will the OS kill you? Will your bare metal MCU silently return garbage? Will you corrupt your program state and jump into branches that should never be reached? Who knows. You're advocating for wild behavior but you don't even realize it.
As for your example. No, the compiler couldn't optimize like that. You seem to have some misconceptions about UB. If foo is false in your code, then the behavior is completely defined.
That's the point. If foo is false, both versions do the same thing. If foo is true, then it's undefined and it doesn't matter. Therefore, assume foo is false. Remove the branch.
you get it, but a lot of other people don't understand just how undefined, undefined code is.
But let me put it this way. If you only had the misbehaving_code(); line by itself, the compiler would rightly be called crazy and malicious if it compiled that to delete_data();
So maybe it's not reasonable to treat both branches as having the same behavior, even if you can.
If this was true most of them could just adopt Rust where of course this isn't a problem.
But in fact they're often vehemently against Rust. They like C and C++ where they can write total nonsense which has no meaning but it compiles and then they can blame the compiler for not reading their mind and doing whatever it is they thought it "obviously" should do.
Signed overflow is the classic example - making that undefined rather than implementation-defined is a decision that makes less to those of us living in today's exclusively two's-complement world than it would have done when it was taken.
It's become more of an issue in recent years as compilers started doing more advanced optimisations, which some people perceived as the compiler being "lawful evil".
What it reminds me of is that episode of Red Dwarf with Kryten (with his behavioural chip disabled) explaining why he thought it was OK to serve roast human to the crew: "If you eat chicken then obviously you'd eat your own species too, otherwise you'd just be picking on the chickens"!
Yes, go ahead and assume it won't alias outside the rules of C and hope it works out.
> That's taking advantage of undefined behavior to optimize a program.
I don't know if I really agree with that, but even taking that as true, that's fine. The objection isn't to doing any optimizations. Assuming memory didn't get stomped is fine. Optimizations that significantly change program flow in the face of misbehavior and greatly amplify it are painful. And lots of things are in the middle.
int stupid (int a) {
return (a+1) > a;
}
What should the compiler emit for this? Should it check for overflow, or should it emit the asm equivalent of `return 1`? If your answer is check for overflow: then should the compiler be forced to check for overflow every time it increments an integer in a for loop? If your answer is don't check: then how do you explain this function behaving completely weird in the overflow case? The point I'm trying to get at is that "do the obvious thing" is completely dependent on context.The for loop example is silly. There is no reason whatsoever to add an overflow check in a for loop. The code of a standard for loop, `for (int i = 0; i < n; i++)` doesn't say to do any overflow check, so why would the compiler insert one? Not inserting overflow checks is completely different than omitting overflow checks explicitly added in the code. Not to mention, for this type of loop, the compiler doesn't need any UB-based logic to prove that the loop terminates - for any possible value of n, including INT_MAX, this loop will terminate, assuming `i` is not modified elsewhere.
I'd also note that the "most correct" type to use for the iteration variable in a loop used to access an array, per the standard, would be `size_t`, which is an unsigned type, which does allow overflow to happen. The standard for loop should be `for (size_t i = 0; i < n; ++i)`, which doesn't allow the compiler to omit any overflow checks, even if any were present.
A compiler will just avoid inlining any code here, since it's not valid, and thus by definition that branch cannot be taken, removing cruft that would impact the instruction cache.
Note that also `return 1 < 0` is also perfectly valid code.
The problem related to UB appears if the function is inlined in a situation where a is INT_MAX. That causes the whole branch of code to be UB, and the compiler is allowed to compile the whole context with the assumption that this didn't happen.
For example, the following function can well be compiled to print "not zero":
int foo(int x) {
if (x == 0) {
return stupid(INT_MAX);
} else {
printf("not zero");
return -1;
}
}
foo(0); //prints "not zero"
This is a valid compilation, because stupid(INT_MAX) would be UB, so it can't happen in a valid program. The only way for the program to be valid is for x to never be 0, so the `if` is superfluous and `foo` can be compiled to only have the code where UB can't happen.Eidt: Now, neither clang nor gcc seem to do this optimization. But if we replace stupid(INT_MAX) with a "worse" kind of UB, say `*(int*)NULL = 1`, then they do indeed compile the function to simply call printf [0].
Functions have parameters. In the case of the previous function, it is not defined if its parameter is INT_MAX, but is defined for all other values of int.
Having functions that are only valid on a subset of the domain defined by the types of their parameters is a commonplace thing, even outside of C.
Yes, a compiler can deduce that a particular code path can be completely elided because the resulting behaviour wasn't defined. There is nothing surprising about this.
And no, this doesn't happen in any other commonly-used language. No other commonly-used language has this notion of UB, and certainly not this type of optimization based on deductions made from UB. A Java function that is not well defined over its entire input set will trigger an exception, not cause code calling it with the parameters it doesn't accept to be elided from the executable.
Finally, I should mention that the compiler is not even consistent in its application of this. The signed int overflow UB is not actually used to ellide this code path. But other types of UB, such as null pointer dereference, are.
Your statement that such a function would throw an exception is false.
Ensuring a function is only called for the domain it is defined on is entirely at the programmer's discretion regardless of language. Some choose to ensure all functions are defined for all possible values, but that's obviously impractical due to combinatorial explosions. Types that encapsulate invariants are typically seen as the solution for this.
And yes, it's the programmer's job to make sure functions are called in their domain of apllication. But it doesn't help at all when the compiler prunes your code-as-written to remove flows that would have reached an error situation, making debugging much harder when you accidentally do call them with illegal values.
Optimizing compilers on the other hand are all about outputting something that is equivalent to your code UNDER THE RULES OF THE LANGUAGE while hopefully being faster. This condition isn't there to fuck you over its there because it is required for the compiler to do more than very very basic optimizations.
The problem here is how far you stretch this "equivalent under the rules of the language" concept. I think many agree that C and C++ compilers have chosen to play language lawyer games to little performance in real world code, but introducing very real bugs.
As it stands today, C and C++ are the only mainstream languages that have non-timing-related bugs in optimized builds that aren't there in debug builds - putting a massive burden on programmers to find and fix these bugs. The performance gain from this is extremely debatable. But what is clear is that you can create very performant code without relying on this type of UB logic.
And undefined behaviour is still undefined behaviour without all the optimisation passes turned on.
A significant issue is that compiler "optimizations" aren't gaining a lot of general benefit anymore, and yet they are imposing a very significant cost on many people.
Lots of people still are working on C/C++ compiler optimizations, but nobody is asking if that is worthwhile to end users anymore.
Data suggests that it is not.
Compiler writers measure an "optimization" as successful if they can find any example where the "optimization" saves time. Does this matter for the overall user experience? The typical debate runs as follows:
In 2000, Todd A. Proebsting introduced "Proebsting's Law: Compiler Advances Double Computing Power Every 18 Years" (emphasis in original) and concluded that "compiler optimization work makes only marginal contributions". Proebsting commented later that "The law probably would have gone unnoticed had it not been for the protests by those receiving funds to do compiler optimization research."
Arseny Kapoulkine ran various benchmarks in 2022 and concluded that the gains were even smaller: "LLVM 11 tends to take 2x longer to compile code with optimizations, and as a result produces code that runs 10-20% faster (with occasional outliers in either direction), compared to LLVM 2.7 which is more than 10 years old."
Compiler writers typically respond with arguments like this: "10-20% is gazillions of dollars of computer time saved! What a triumph from a decade of work!"
We are spinning the compilers much harder and imposing changes on end programmers for roughly 10-20% over a decade. That's not a lot of gain in return for the pain being caused.I suspect most programmers would happily give up 10% performance on their final program if they could halve their compile times.
> I suspect most programmers would happily give up 10% performance on their final program if they could halve their compile times.
10% at FAANG scale is around a billion dollars per year. There's a reason why FAANG continues to be the largest contributor by far to LLVM and GCC, and it's not because they're full of compiler engineers implementing optimizations for the fun of it.
And, yet, Google uses Go which is glop for performance (Google even withdrew a bunch of people from the C/C++ working groups). Apple funded Clang so they could get around the GPL with GCC and mostly care about LLVM rather than Clang. Amazon doesn't care much as their customers pay for CPU.
So, yeah, Facebook cares about performance and ... that's about it. Dunno about Netflix who are probably more concerned about bandwidth.
-O0 gives you what you are after.
How do you expect the compiler to statically guarantee that this property holds in all the cases you want to do a binary search?
No, it's like calling dd buggy for deliberately zeroing all your drives when you call it with no arguments.
How did we let pedantic brainless "but muh holy standards!!!1" religious brigading triumph over common sense?
The standards left things undefined in the hopes that the language would be more widely applicable and implementers would give those areas thought themselves and decide the right thing. Not so that compiler writers can become adversarial smartasses. It even suggests that "behaving in a manner characteristic of the environment" is a possible outcome of UB, which is what "the spirit of C" is all about.
In my observations this gross exploitation of UB started with the FOSS compilers, GCC and Clang being the notable examples. MSVC or ICC didn't need to be so crazy, and yet they were very competitive, so I don't believe claims that UB is necessary for optimisation.
The good thing about FOSS is that those in power can easily be changed. Perhaps it's time to fork, fix, and fight back.
That sounds like implementation-defined behavior, not undefined behavior.
Huzzah! Lead on, then.
But maybe not come in with an "I need to take back the compiler from evil compiler writers" attitude.
They're the ones who started this hostility in the first place.
If even someone like Linus Torvalds can't get them to change their ways, what chances are there for anyone else?
P.S. "All they do is worship The Holy Standard. They follow the rules blindly without ever thinking whether it makes sense" — well, no. Who do you think writes The Holy Standard? Those compiler folks actually comprise quite a number of the members of JTC1/SC22/WG14, and they are also the ones who actually get to implement that standard. So to quote JeanHeyd Meneide of thephd.dev, "As much as I would not like this to be the case, users – me, you and every other person not hashing out the bits ‘n’ bytes of your Frequently Used Compiler — get exactly one label in this situation: bottom bitch".
"How dare these free software developers not do exactly what I want."
Talk about being entitled. If you can't manage to communicate you ideas in a way that will convince others to do the work you want to see done then you need to either pay (and find someone willing to do the work for payment) or do the work yourself.
This attitude turns bugs into security vulnerabilities. There's a reason the Linux kernel is compiled with -fwrapv -fno-strict-aliasing -fno-delete-null-pointer-checks and probably many more sanity restoring flags. Those flags should actually be the default for every C project.
So, well, yes, if the bug is due to triggering UD, some blame should fall on the developer, too.
But that's not an excuse for having a bug; it's the exact evidence that it's not a bug at all. Calling the compiler buggy for not doing what you want when you commit Undefined Behavior is like calling dd buggy for destroying your data when you call it with the wrong arguments.