“What the Hardware Does” Is Not What Your Program Does: Uninitialized Memory
ralfj.de
ralfj.de
"NOTE: Possible undefined behavior ranges from [...] to behaving during translation or program execution in a documented manner characteristic of the environment"
The whole point of C as K&R and ISO is to let you do "what the hardware does". They left parts of the standard purposefully undefined, so it could remain applicable to a wide variety of implementations. The intention was definitely NOT "screw the programmer" as a lot of the compiler writers seem to have interpreted it, but to allow them to do something that makes sense for the environment.
Now we have, mostly academics from what I've noticed, that are taking the language farther and farther away from reality; focusing only on something uselessly abstract, completely ignoring the practical consequences of what they're doing. Compilers are becoming increasingly hostile to programmers. A programming language that had humble and very practical uses, with straightforward and easily understood behaviour, has been perverted into theoretical quagmire of uselessness.
Something very very odd is going on, and I don't like it one bit. It's very WTF-inducing.
(I don't know much about Rust, hence why I didn't say anything about it. But I've been using C since the late 80s.)
UB is always about optimisations and performance. Incidentally, this is why I don't think talking about "nasal demons" is productive. The compiler mostly just uses UB to assume: ah, this can't happen, so I can optimise it away. Often that means valid programs go faster. We wanted it: we got it.
From my limited experience (and it's been a while), -O0 (no optimisations) is really quite reliable, even if you do all kinds of UB shenanigans.
Really? I've seen people switch between competing compilers for licensing reasons, platform support, features---but benchmark performance? Maybe blog posts suggesting that a new compiler wasn't ready.
Compiler writers judge themselves on benchmarks.
No idea whether ICC is still worth paying for
From my experience, ICC is far more reluctant to exploit UB, yet still generates very good code.
So basically ICC has -ffast-math (or -funsafe-math-optimizations) on by default, and you can turn it off with an explicit flag?
I see this as more of a philosophical difference than a material one since you can just add or remove the flag on either one...
Ironically, strict aliasing rule (which is one of the most common causes of UB) makes writing fast programs much harder, because it forbids type punning (except via memcpy or unions).
BTW, according to WG14 mailings and minutes, the C committee is considering either relaxing it or creating a standard way to suppress it in C2X. I can't wait for it.
Safe Rust does have some implementation-specific behavior - for instance, panics can either unwind or abort.
In Unsafe Rust, all bets are off, and the programmer may trigger Undefined Behavior if they're not careful. The upshot is that it's easier to maintain the compiler's invariants because you only need to be careful in a single place about making sure everything is in order. By clearly marking places where the programmer is in charge of maintaining the invariants instead of the compiler, the hope is that mistakes will be minimized (thanks to careful code review and making the programmer think a lot about what they're writing).
Further helping with that, the goal is to have tools to help catch UB at runtime. For instance, miri is an interpreter for MIR (an intermediate language between rust and the LLVM IR) that checks for UB.
I agree that in C, UB has probably be stretched way beyond its intended purpose. But in Rust, this new definition of UB is taken advantage of in much less WTF-inducing ways, allowing us to enjoy those performance guarantees without losing our minds.
I don't think it's the academics, it's the compiler implementers - driven by wanting to win at benchmarks. Our industry is absurdly focused on "performance" over all else (even correctness). But then again, those who care about other things moved on to non-C languages years or decades ago.
However, the performance impact of optimizations that take advantage of UB is not known, and is potentially very large. It would be a very interesting experiment to modify a C/C++ compiler so that every C/C++ program has defined semantics in terms of a simple array-of-bytes abstract machine, and see how much slower the generated code is compared to the regular compiler.
Alternatively, look at compilers like Intel's ICC --- it has historically been one of the best at code generation, yet it's not known for having anywhere near the same level of UB-craziness as Clang (or GCC, to a lesser extent). The same has been my experience with MSVC, at least the earlier versions.
[1]: https://hal.archives-ouvertes.fr/hal-00128124v5/document
So in some respects ICC is very aggressive.
Us academics do have a lot of "fun" figuring out a way to put what the compiler developers do on solid footing [1]. But this is a game of whack-a-mole that will never end: each time we find a way to formally approach some new crazy optimization they came up with, and help them weed out all the bugs that were caused by not carefully thinking through all the implications [2], the next crazy optimization comes up [3].
[1]: https://people.mpi-sws.org/~jung/twinsem/twinsem.pdf
[2]: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65752, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82282, https://bugs.llvm.org/show_bug.cgi?id=35229, https://bugs.llvm.org/show_bug.cgi?id=34548
[3]: https://bugs.llvm.org/show_bug.cgi?id=21725, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57359
What current compilers do is about as far away from “ignoring the situation completely” as it is possible to get.
(b) What compilers are doing does not match "ignore at execution", because they also use it to remove completely separate code.
It isn't.
And when they're talking about doing something hardware-specific I would take that to be about the MMU on certain platforms. Platforms with an MMU and where the processor is executing code in a virtual address space can generate an access violation if the program code reads data at a virtual address that is not mapped to a specific segment of physical memory.
Even when a program runs in a physical address space, the processor may be configured with an address space that is significantly larger than the actual block of memory and registers on the memory bus. And this matters because if you have a 32-bit processor but the upper 3 gigabytes of the address space don't map to a register file or RAM then it's hardware-dependent what happens when you read from those addresses.
Some hardware will roll the map over and read from somewhere in the available section of the address space based on the offset, and some hardware will treat that as an error which triggers an access violation. Some hardware will bug out and do something completely unexpected. It's undefined behavior what happens in this case. It has everything to do with how your specific chip, mainframe, or minicomputer is wired. And that's what they're referring to.
Undefined behavior does not mean "do whatever you want," it means "do what the hardware would probably do in this situation, or do whatever can be reasonably expected." And that's important here because that means that UB is not carte blanche to violate the programmer's expectations here.
But let's ignore the standard... who cares what it says...
The thing is, what you're asking for inhibits optimizations that many people would very much like to see from their compilers. Like for example if you have an uninitialized function pointer that you only assign to in 1 or 2 locations -- the compiler should be able to just replace the indirect function calls with direct function calls. You're demanding that it doesn't do that, and that it simply call whatever function or non-function that pointer happened to point to. I mean -- you're welcome to ask for that, and maybe your compiler should have a flag to make it behave that way (or maybe it does already? do you use it if so?), but to me and many other people, the compiler should obviously be permitted to see right through that.
Rather than telling someone what they are demanding, it's often better to ask them --- especially if you are sure that what they are demanding is stupid. Personally, I'd guess that 'jschwartzi' might be fine with a compiler that makes the optimization you refer to, and is instead objecting to a compiler that deletes essential safety checks in other parts of the program on the assumption that all bets are off once "undefined behavior" can be proven to occur. If he's like me, he'd probably also prefer that the compiler issue a warning about the undefined behavior rather than silently making changes to the program. But better to ask him than to guess.
In the case of your safety check example, it'd be nice if you could mention something concrete so we know exactly what situation you're talking about. But I mean, I can't rule out that maybe you'll find a couple situations here and there where the standard shouldn't leave things undefined. But the argument I'm rebutting here is that all instances of UB must behave "like the hardware", not that this particular instance is good but another one is bad, so I'm not sure you two would agree. I agree warnings would be nice too (some of which already exist), and I think despite their current efforts compiler still have some ways to go (e.g. a macro expanding to 0 should probably not behave the same as the literal 0 when you multiply, say, by a constant), but again, that's already assuming you're fine with UB...
There are some well-publicised cases of compilers removing NULL-checks[0] on the assumption that the NULL value can't occur as it would be UB.
As another example, the Linux kernel assumes in several places that signed integer overflow wraps, so it is compiling with -f-no-strict-overflow/-fwrapv ever since GCC started optimizing based on this piece of UB (they noticed the compiler behavior change and added the flags before releasing any faulty kernels though, apparently).
People want these optimizations individually. They don't want to keep dead code taking up cycles and they also don't want dead variables taking up registers. So you can't really find much support arguing that those optimizations should be removed entirely. The only real possibilities you can propose here are that the compiler should have magically re-inserted the pruned check during the second optimization, or that it should have performed them in the opposite order. But are you sure these are actually possible and if so, practical? I mean, maybe they are, but they are far from obvious to me. I can easily see the compiler thrashing and failing to reach a fixed point if it re-inserts code that a previous optimization pass pruned. Similarly, I don't see how the compiler can just magically detect an optimization order that ensures "surprising" situations like this don't occur. My guesstimation is that it would carry severe downsides people wouldn't want. Now maybe I'm just not smart enough to see a good solution to this that doesn't carry significant downsides, and there's already one out there. If there is, I'm curious to hear about it, and I hope someone implements it under some flag, but I have yet to hear of one.
For signed integer overflow -- that might be one place where I think it would make sense to just define it to either wrap with 2's complement just like unsigned integers do, or to be unspecified behavior that falls back to the implementation's representation. Though in the latter case... you already have an implementation-specific solution: your compiler flags. But again, we might agree on a couple optimizations here and there, but that's a far cry from saying UB should just fall back to hardware behavior. And honestly, I'm not even here supporting C; I hate it. If you want wrapping, I would suggest it's a sign you might want to use C++ already. Then you can define an integer type that will play Beethoven when you overflow, and people who want their UB on overflow can have that too.
[1] I'm ignoring the validity of address 0 in kernel-mode here; there's also some subtleties on what's a null pointer and what's address zero that are rather beside my point.
That's the sort of thing I would suggest - don't work back from UB (and I agree, I wouldn't expect the optimizer to backtrack optimizations as new facts come up), work forward from actually known facts.
NULL checks are probably a pretty bad example, since the NULL access would surely SEGFAULT if allowed to execute (though the particular case of address 0 vs NULL, and of code catching segfaults like on Windows, throw a wrench in this assumption eve here), but other types of UB are much worse.
If you accidentally issue a read from a point after the end of an array, but only later check that the index was within bounds (e.g. `int x = a[i]; if i < len(a) return x; else return NULL`), the compiler eliding the bounds check by the same logic will take a program that might have been safe in practice to a program that is certainly not safe. Note that I don't know if compilers perform this type of optimization, so this may be a hypothetical.
In general though, I think that the tension here comes from C being used in 2 very different use cases: 1 is C used as portable assembly, where you expect the compiler to keep a pretty 1:1 mapping with your code; and the second one is C used as the ultimate performance language, where you drop to C when you can't optimize further in anything else. I think most of the complaints about "exploiting UB" come from the first camp, whereas the second camp is pretty happy with the current status quo.
Usually these are not reachable in practice so warnings that these exist would cause a tidal wave of pointless warnings. Instead, the compiler simply prunes those paths which can lead to better code generation for the paths that are taken.
Side note, Kernighan (of K&R) did not have any part in the invention of C, it was all Dennis Ritchie. Kernighan famously wrote the book on it with Ritchie but that was it.
In his own words[1]:
> remember, C is entirely the work of Dennis Ritchie, I am but a popularizer
Rather than rehashing the same arguments I've made over and over, I'll just link to parts of a Twitter thread where Daniel Micay argues eloquently that keeping the sources of UB that we have today as they are is important:
You could always write “WrapAroundSan”.
This is effectively what Rust does (replace "SIGILL" by "panic").
That also means it's possible to write overflow checks easily, and ones that the compiler won't optimise out. Before compilers became UB-crazy, you could write such checks in the most straightforward way, and get exactly what you expected. I'd consider that a far bigger advantage for security than arguing for the existence of a tool whose sole reason for existence seems to be due to the presence of UB in the first place.
no, because unsigned overflow is valid and yet ubsan is able to check for it with -funsigned-integer-overflow (and I caught so many bugs like this)
Brian Kernighan didn't invent C, he co-authored a book about it.
> Whenever discussions like this come up, I like to quote the C standard itself on its definition: "NOTE: Possible undefined behavior ranges from [...] to behaving during translation or program execution in a documented manner characteristic of the environment"
The actual quote is: "NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message)." - but you snipped out the part that contradicted your point.
> The whole point of C as K&R and ISO is to let you do "what the hardware does". They left parts of the standard purposefully undefined, so it could remain applicable to a wide variety of implementations. The intention was definitely NOT "screw the programmer" as a lot of the compiler writers seem to have interpreted it, but to allow them to do something that makes sense for the environment.
This seems to be contradicted by the full quote above: "ignoring the situation completely with unpredictable results" does sound like it's going to "make sense for the environment". It's also pretty inflammatory to say that the intention of a compiler author is to "screw the programmer".
> Now we have, mostly academics from what I've noticed, that are taking the language farther and farther away from reality; focusing only on something uselessly abstract, completely ignoring the practical consequences of what they're doing. Compilers are becoming increasingly hostile to programmers. A programming language that had humble and very practical uses, with straightforward and easily understood behaviour, has been perverted into theoretical quagmire of uselessness.
So, the "academics" are making compilers "hostile to programmers" and perverting the language into a "theoretical quagmire of uselessness"? That's nonsensical anti-academic garbage unsubstantiated by fact.
> "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied, including, without limitation, ... FITNESS FOR A PARTICULAR PURPOSE.
which would permit the GCC steering committee to decide tomorrow that every other statement must be "HAIL SATAN;" or your code won't compile.
Of course, "can" doesn't mean "should," and if they actually did it, it wouldn't say anything particularly deep about the GPL being a bad license, it would merely indicate that the GCC steering committee had become untrustworthy, and that the community should act accordingly.
Undefined behavior is exactly analogous. It was a degree of freedom designed to allow compiler writers to smooth over CPU architecture friction back in a time when the CPU architecture scene was far less settled than it is now. Trust and responsibility were always understood to be necessary components to make it work. The fact that trust can be broken isn't deep, isn't surprising, and isn't a failure of C.
If C compiler writers want to use UB as an excuse to abuse the trust they have been given, that's on them. I am moving away from C, for many reasons, but the UB-related reason has very little to do with UB being inherently evil and very much to do with the fact that it seems to be placed in increasingly irresponsible hands.
I agree though, the moment abstract machines distract from actually creating something is the moment one has gone too far.
[1]: https://raphlinus.github.io/programming/rust/2018/08/17/unde...
[2]: https://www.ralfj.de/blog/2017/07/14/undefined-behavior.html
Excellent point, and very well made… Thank you for writing this!
There is a constant back-and-forth here on Hacker News about whether or not “undefined behavior“ is the root of all evil or the root of all real-worls optimizations… And your article does a great job of explaining, in real-world terms, what UB really (in-part) is.
I prefer this because it is more open about the fact that all the weird and counterintuitive behaviour happens because the language specifiers and compiler implementers decided to make it that way (usually, with good reason!). It's not some unavoidable property of the universe, or the machine.
The idea of an abstract machine is still really useful, because it lets you reason directly about the code you are writing, rather than having to express and reason about what the compiler might do with it. But i think we should be clear that it's a tool for thinking, not a truth.
The idea that you can ignore the real hardware is particularly unhelpful in Rust, because it's a great fit to low-level problems where the real hardware is a big deal. For example, at work, we have a Rust program where we routinely need to think about NUMA placement and cache coherency protocols. Those don't exist in the Rust abstract machine at all!
If I understand Ralf's overall model here, I think they'd argue that this sort of reasoning must be done within the context of the abstract machine's behavior for std::ptr::{read,write}_volatile, no?
Of course, when you ask why the abstract machine is the way it is, optimizations and hardware come up again. But I think these concerns are better separated. This also mirrors how languages like C/C++ are actually designed, at least in theory: optimizations are justified against the abstract machine, not the other way around. Isn't it much easier to have one, albeit weird, machine in your head, than a (only marginally simpler) "real" machine plus a list of optimizations that also contribute to the behavior of the compiled program? And that list can even change any time!
> The idea of an abstract machine is still really useful, because it lets you reason directly about the code you are writing, rather than having to express and reason about what the compiler might do with it. But i think we should be clear that it's a tool for thinking, not a truth.
If you read the C/C++ standard, you can see that the abstract machine is the truth. Same if you read the really well-written WebAssembly standard (which comes with a mathematically precise formal definition).
So IMO you got it backwards. The abstract machine is the truth, the optimizations are just the way that machine gets exploited right now and can change with any compiler update. Of course the abstract machine is not "God-given", but neither are the optimizations. And the abstract machine can only change when switching to a new version of the language standard, the optimizations can change on any minor compiler update. The machine is much more stable than the list of optimizations.
> The idea that you can ignore the real hardware is particularly unhelpful in Rust, because it's a great fit to low-level problems where the real hardware is a big deal. For example, at work, we have a Rust program where we routinely need to think about NUMA placement and cache coherency protocols. Those don't exist in the Rust abstract machine at all!
I admit that once you think about performance, the details of what your compiler and hardware happen to do become very relevant. But when talking about correctness, I think that is an unsuited level of (lack of) abstraction.
EDIT: Based on this feedback and others, I have amended the blog post a bit. It now says
> Maybe the most important lesson to take away from this post is that “what the hardware does” is most of the time irrelevant when discussing what a Rust/C/C++ program does, unless you already established that there is no undefined behavior. [...]
> UB-free programs can be made sense of by looking at their assembly, but whether a program has UB is impossible to tell on that level. For that, you need to think in terms of the abstract machine.
GCC: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65752
LLVM: https://bugs.llvm.org/show_bug.cgi?id=35229, https://bugs.llvm.org/show_bug.cgi?id=34548
The article (indeed the point of it) abstracts that all away behind "undefined behavior" and a mental model sitting between your code and its resulting executable. Which is fine, but it leaves a loose end which fails to sate my curiosity.
playground::main:
push rax
call std::panicking::begin_panic
ud2
`main` just calls `panic` immediately. The functions returns undef. The reason: `x > 150` is undefined, `undef || ...` is undefined thus the first if-statement with side-effects may be interpret undefined as true.
I wonder why the optimiser didn't choose false and let the assert pass?
I don't know exactly, but it's kind of a moot point. I would have negated the statements until I found a way to make it return what I want it to.
The point is that the compiler picks some result, and it does so "locally", so when it picks results for multiple comparisons it makes no attempt to check that these results are all "consistent" and can even arise for a single value. The result that we can observe is that the value is "unstable".
To "fix" this (assuming we wanted to specify that unstable values are not allowed in C/C++/Rust), the compiler would have to keep track of which constant foldings it already did for some uninitialized value, and make sure it remains consistent with that. That's a hard problem and likely undecidable in general. Allowing unstable values frees the optimizer from this burden, letting it optimize more code better.
I think though (as your question indicates); that the author misses the point of why people care about "What the hardware does". At the end of the day, assembly code is going to execute, and that assembly code is going to (despite the authors protestations to the contrary) have well defined memory of one value or another. The moment you start saying "Rust has a third value of uninitialized" the question comes up "How is that abstraction enforced by the hardware?" This is valuable information for understanding how the language works.
From the authors discussion, I was expecting some sort of sentinel value being checked; however, instead, the uninitialized memory access is detected by the compiler and it panics uniformly regardless of the actual memory state.
The idea that one should only worry about the abstract virtual machine of rust seems like an encouragement of magical thinking. "Don't worry about how any of this works, the compiler will just make it happen". This will not go over well with many people who are curious about learning Rust.
However, if the author is arguing "Don't let the behavior of a naive enforcement of a Rust safety construct dictate how the optimized version should work" this seems like a more interesting position; but it's not clear that is the argument being made here.
The point is that you may not get the assembly you assume you’re going to get. Like the example shows, it may never even generate something that accesses the value at all.
I really need to finish my own blog post series on this topic...
The compiler does not enforce it though. It only implements the abstract machine, and the implementation is only correct for UB-free programs.
The actual hardware behavior is useful for other purposes, like understanding why the abstract machine is the way it is, or understanding and improving the performance of well-defined programs, but it is not useful at all once you have UB.
This is exactly the point the author is arguing. The focus of all their work on UB is to make sure safe Rust can do all the optimizations we would like, by careful design of the abstract machine.
The immediately visible outcome of this work is a set of rules for what you can do in unsafe Rust, which taken together amount to this weird-looking abstract machine with its extra "uninitialized" values- something that can be implemented efficiently on real hardware assuming no UB.
The point here is that this abstract machine is a better, simpler, easier way to convince yourself whether or not an unsafe Rust program is well-defined, and that "what the hardware does" is too many layers removed to be a good tool here. You can think about "what the hardware does" another time, for other purposes, but trying to do so in this context is actively unhelpful.
I mean, the latter seems quite a bit more extreme, and is what the author explicitly is calling for.
Yes, but this only really means anything in the absence of undefined behavior. The compiler's job is generate assembly that produces the results that running the code in the abstract machine would, but the issue is that undefined behavior allows the abstract machine to do arbitrary things, so the compiler is free to generate whatever it likes in this case.
I don't get this hostility to understanding the tools you're using.
Pretty much, yes.
> I don't get this hostility to understanding the tools you're using.
Don't take me the wrong way: I'm interested in how compilers work, but I accept the concession that I can only really understand their output when my program is free of undefined behavior. It would be nice to have the compiler try its best in the cases where I am violating the rules of the programming language, and often it will do so, but in general I cannot expect this and trying to do so will require making some sort of tradeoff with regards to performance or language power.
The assembly has to implement the abstract machine only if your program has no UB. The assembly never has to check if memory is "initialized" or not even though that distinction is real on the abstract machine, because if the difference would matter, your program would have UB.
To determine if your program has UB, looking at the assembly is useless. The only way is to consider the abstract machine.
Trying to interpret the assembly of a UB program is like trying to interpret the noise of a radio when there is no station on the given frequency. It has more to do with fortune telling than anything else. There is no signal in there, or at least not enough of it to be useful.
It's literally just
xor eax, eax
retI am sceptical the author really knows much as some of their statements seem blatantly wrong or just nonsense:
"So, one time we 'look' at x it can be at least 150, and then when we look at it again it is less than 120, even though x did not change."
Is talking about "x < 150 || x > 120", but gets it the wrong way around, ouch!
"Memory remembers if you initialized it. The x that is passed to always_return_true is not the 8-bit representation of some number, it is an uninitialized byte."
Benefit of doubt could be extremely poor metaphors, or referencing the wrong code?
Also stating C is not low-level is a conceited attempt to redefine the word.
I expect a low level language to run the code I typed, or something that has the same effect.
They're not redefining the term. C itself has been redefined away from its origins.
That is exactly the point of my post! If you think I disagree with that statement, we seriously miscommunicated somewhere.
The parts you seem to be concerned about are those where I try to explain why the abstract machine is the way it is. Hardware and compiler concerns do come in at that point, and my feeling is just dogmatically giving an abstract machine won't help convince people of its usefulness.
> Is talking about "x < 150 || x > 120", but gets it the wrong way around, ouch!
It's not the wrong way around. The assertion failure being discussed happens when the function returns false, which happens when both sides of the || are false. Technically he should have said "less than or equal to 120" rather than just "less than", but otherwise it's accurate.
xor eax, eax
ret
Only UB-free programs can be made sense of by looking at their assembly. Whether a program has UB is impossible to tell on that level. For that, you need to think in terms of the abstract machine.
I mean, look at the code I wrote! It literally compares `x` with 150 and 120. That's the program I wrote. This program has a "meaning"/"behavior" that is entirely irrelevant of compilers and optimizations, and determined by the langauge specification. How can you argue that it does compare `x`?
Responding to whether C is "low-level" I like this comment: http://lambda-the-ultimate.org/node/5534#comment-95721 And processors have undefined behaviour so should we say assembly is not "low-level"? e.g. "Grep through the ARM architecture reference manual for 'UNPREDICTABLE' (helpfully typeset in all caps), for example…" - pcwalton
Thanks heaps for your article which was a good read, and it led me to the funnier side of undefined behaviour: https://raphlinus.github.io/programming/rust/2018/08/17/unde... and https://lkml.org/lkml/2018/6/5/769
I suspect it may be because the author is German. In French at least «inférieur» means “less or equal than” and you need to say «strictement inférieur» to say “less than”, and I wouldn't be surprised if it were the same in German.
But thanks for pointing out this mistake, I will fix it immediately.
Example of an Integer overflow based optimization
Regardless, checking a register or hot value already in cache against a constant is free on modern CPUs.
How can anyone put up with that?
This is one of those optimizations that a very clever compiler might be able to do interprocedurally give a certain input for example.
> In the case of our example, the program actually compares such an “unobservable” bit pattern with a constant, so the compiler constant-folds the result to whatever it pleases. Because the value is allowed to be “unstable”, the compiler does not have to make a “consistent choice” for the two comparisons, which would make such optimizations much less applicable. So, one time we “look” at x the compiler can pretend it is at least 150, and then when we look at it again it is at most 120, even though x did not change.
Also see http://nondot.org/sabre/LLVMNotes/UndefinedValue.txt.
> In the example of the post, the compiler would look into `always_returns_true`
You can't look at each function in isolation. One important optimization all modern compilers use is inlining: short functions (like this `always_returns_true`) or functions that are only used once (like this `always_returns_true`) have their body inserted directly into the caller function, which allows further optimizations like constant propagation.
You definitely _can_ look at each function in isolation (in this example it's even sufficient to get the "best" possible version of that function"), but I do know that you'd usually do an inline pass, and further optimization passes afterwards. I don't see how that changes anything, though. If the function was inlined you'd get the same expression, and still you'd be unable to tell anything about `x`, except that it would have a definite value that you cannot observe. Again, you could argue that no matter the value, the expression would be `true`, so you could replace it.
But `always_returns_true` is not an example of how this particular undefined behavior can be useful as an optimization, merely an example of how it can be dangerous. For some examples of how it can be useful:
- Document describing the origins of `undef` in LLVM: http://nondot.org/sabre/LLVMNotes/UndefinedValue.txt
Basically, it helps to be able to replace "cond ? some_value : undef" with "some_value", especially when the code has been transformed to SSA form.
- Some architectures literally have a 257th possible value, like Itanium [1] [2]. On Itanium, every register can be set to "Not a Thing", i.e. uninitialized, and the CPU will trap if you try to store such a value to memory. Ironically, NaT was created in order to make the CPU's behavior more defined in a certain case, or at least more predictable... argh, I'm too tired to explain it properly; look at section 2.3.1 of [2] for a somewhat confusing explanation.
[1] https://devblogs.microsoft.com/oldnewthing/20040119-00/?p=41...
[2] https://www.cse.unsw.edu.au/~cs9244/06/seminars/07-gaol.pdf
> LLVM propagates the `undef` outward through the expression until the whole condition is `undef`, and then it arbitrarily picks that the condition should be false.
I think this illustrates what I find counter-intuitive about this whole mess; any function of `undef` shouldn't itself be `undef`. `undef < undef` is false in my head. `undef < 150` is just unknown, not undefined, since we don't know what `undef` is.
> Basically, it helps to be able to replace "cond ? some_value : undef" with "some_value"
This feels really contrived; in what setting would this actually be useful?
The text file I linked to explains it in more detail, so I'll defer to that.
> I think this illustrates what I find counter-intuitive about this whole mess; any function of `undef` shouldn't itself be `undef`. `undef < undef` is false in my head. `undef < 150` is just unknown, not undefined, since we don't know what `undef` is.
Except that for `undef < undef`, what if they're two different undefs? You would have to track each potentially uninitialized value separately. And then the optimizer would want to strategically choose values for the different undefs – e.g. "we want to merge 'cond ? some_value : undef123' with 'some_value', so let's set undef123 equal to some_value... except that could negatively impact this other section of code that uses it". It's certainly possible, but it would make the optimizer's job somewhat harder.
See also:
I suppose it could be enlightening to understand why it wasn't a good decision for C or C++ at the time either.
> some architectures might use a trap/invalid representation
Traps on what? Access of an invalid representation? What if such representations doesn't exist?
Yeah - certain bit-patterns are just "invalid" rather than representing any given value. It's much nicer to debug, because you get an immediate failure (at the point where your code tries to access the uninitialized variable) rather than having a corrupt value propagate through your program.
> What if such representations doesn't exist?
Then you can't implement that strategy (other than by emulating it with considerable overhead, e.g. by having an extra marker byte for each variable in your program and checking it on every access). Hence why the C standard doesn't require you to do this.
As originally intended, C left the behaviour undefined so that users on platforms that did have trap representations would be able to take advantage of them. (It's very hard to rigorously specify what accessing a trap representation should do without impeding the compiler's ability to reorder memory accesses). Unfortunately it's ended up being used to do the opposite by modern compilers - not only do they not trap on access to uninitialized values, they abuse the undefined behaviour rules to propagate unexpected behaviour even further from the code that caused it.
We use types to restrain complexity. It was a mistake in C# to allow every object to be null. A better type system would allow devs to make a contract to easily disallow this and they try to fix this. Now here we have a blog post that seems to be fine with a function parameter of type u8 not actually being of 0-255. That's a huge change I always understood the type. Do I now have to do implement a null-check equivalent?
Undefined behavior for unsafe code is fine. But there has to be a transition were we go back to classical behavior. And in the blog posts example, this should be somewhere in main. Certainly not the seemingly safe always_returns_true.
So if the programmer doesn't in fact know what they're doing then they can cause bad things to happen outside the `unsafe` block, as this post shows.
It's not a valid value of that type - it's not a value you'll ever see if you're using the language in accordance with the spec (and, in the case of Rust, not a value you can ever see in safe Rust). It's an uninitialised value.
> We use types to restrain complexity. It was a mistake in C# to allow every object to be null. A better type system would allow devs to make a contract to easily disallow this and they try to fix this. Now here we have a blog post that seems to be fine with a function parameter of type u8 not actually being of 0-255. That's a huge change I always understood the type. Do I now have to do implement a null-check equivalent?
The point is for the language to do the null-check equivalent for you. A trap representation is null done better. Silently defaulting to a valid value is even worse than silently defaulting to null, because the value propagates even further from the point where it's wrong - imagine e.g. a Map implementation that, rather than returning null for a key that isn't present, returned an arbitrary value.
(Of course in the case of a Map, returning Maybe is better. But there's no way to do an equivalent thing for uninitialized variables, unless we made every single field of every single struct be Optional, and that's actually just equivalent to reintroducing null - the advantage of using Optional is the ability to have values that aren't Optional, at least in safe code).
> Undefined behavior for unsafe code is fine. But there has to be a transition were we go back to classical behavior.
Unfortunately no, that's not and has never been how undefined behaviour works. Undefined behaviour anywhere in your program invalidates the whole program and can lead to arbitrary behaviour anywhere else in your program (this has always been true with or without trap representations).
Pragmatically, what you want in the blog post's example is to get an error that tells you that the bug is that x was uninitialized, as soon and as close as possible to the point where x is actually used uninitialized. Ideally that would be on the "let x = ..." line (and if you didn't use "unsafe", that line would already be an error), but given that you've made the mistake, you're better off having an error as soon as you touch x (which happens in always_returns_true). Then you can see what the problem is and what's caused it. If always_returns_true runs "successfully", returning false, then you don't actually find out there's a bug until later (potentially much later) in your program, and have to do a lot of detective work to find out what went wrong.
I even have a post about this. :D https://www.ralfj.de/blog/2016/01/09/the-scope-of-unsafe.htm...
Is this actually true? I thought these would just be poisoned and then the optimizer would just do whatever it liked in the presence of undefined behavior (like optimize the function to return true).
>> The answer is that every byte in memory cannot just have a value in 0..256,
0..256?? Is this still 8-bits bytes??
>> it can also be “uninitialized”. Memory remembers if you initialized it.
This is plainly wrong.
>> So, one time we “look” at x it can be at least 150, and then when we look at it again it is less than 120, even though x did not change. x was just uninitialized all the time.
You might be dealing with a bug on a non-volatile variable. It has nothing to do with allocated but uninitialized memory.
In Rust a..b means the range a <= x < b, so yes, that is an 8-bit byte.
a <= x < b
0 <= x < 256
Well, I guess the author realized about the confusion in every other non-Rust programmer it generates (https://git.ralfj.de/web.git/commitdiff/13622f8642fc071bedf3...).
Of course you're right in part that their idea of "memory" is an abstraction, but it isn't too wrong. A "variable" in C or any compiled language on a modern machine is an abstraction that could refer to a register one moment, be a place in the cache in another, be a place in memory in the next, and be on a swapfile after. The "variables" are abstractions which lie in "memory" which is another abstraction because it need not be in one place.
FYI The author is a PhD student working on optimizing compiler.
It's just that there is a compile time optimisation that allows the compiler to assume you will never read from uninitialised memory.
It would be perfectly possible to make a language (or even a C++ compiler) that didn't perform that optimisation.
No it's not. To describe the behavior of a program involving uninitialized memory (like the example in my post), at no point in time to you need to talk about arbitrarily chosen bytes. The "abstract machine" on which a Rust programs runs (of which your hardware is a fast implementation, but only accurate for UB-free programs) does not "pick random bytes" when you allocate new memory, it just fills it all with `None`.
You should not think in terms of optimizations when thinking about what your program does. The optimizations the compiler performs can change from version to version and are affected by seemingly random changes at the other end of your program.
> It would be perfectly possible to make a language (or even a C++ compiler) that didn't perform that optimisation.
Sure. That would be a different language though, with a different abstract machine. C/C++/Rust behave the way I described (and that behavior is not defined by what any particular compiler does).
Think about assembly. What is uninitialised memory there? It's just memory with an unknown value.
I can compile an Ada program that has an uninitialized variable and use it, but I get a warning; there's also a Valid attribute that acts as a predicate for whether a scalar value has an acceptable value or not.
To @userbinator , you're mistaken to believe the C has much design behind it. There are many things where one requires a certain range of values and C forces the programmer to use a type that's much larger than necessary and cope with unwanted values. The C language leaves details to the underlying machine, so long as that machine is determined to pretend it's a PDP-11. Most languages that have a standard expect the programmer to follow it; since most C programmers don't know what the standard says, having been lied to about it being a simple and base language, they're offended when they do something they never should've done; they shouldn't be using C anyway, however.
Abstract language details are necessary for a high-level language and can work quite well if the language is designed well; this then leaves high-level features to be implemented in whichever way is best for the machine; the C language doesn't do this well at all, however, and precisely specifies the nature of irrelevant details and so hinders the machine and implementation possibilities.
The C language doesn't even have true boolean values or arrays thereof. You're expected to use an entire integer that's zero or not and you're left to your own devices if you want an array of these values that isn't grotesque in its wastefulness. Meanwhile, most proper languages have the concept of types that only have two values and can easily use an underlying machine representation for efficiently representing these, without involving the programmer.
In closing, you may argue that C is necessary because it permits specifying these low-level details, albeit required in every case instead of only where necessary. To that, I direct you to look at Ada, which permits the programmer to ignore such details wherever unneeded, and so leave them to the compiler’s discretion, but allows size, address, representation, bit-level organization, and more to be specified in those cases where it's truly necessary.
Here's a link others may like for learning more about Ada and the deficiencies of C:
Don't other languages still use an entire byte to represent a bool though, since memory access is at the byte level? Having a bool type in the type system is really a language usability concern, I don't think it's at all a performance optimization. And stdbool.h exists now, so that concern has been addressed. When you want a bitmap, you can just use an int of the appropriate length and do bitwise operations on it, instead of wasting space with an array of ints.
While at the discretion of the implementation, Common Lisp is a language that can easily and transparently perform this optimization. Common Lisp even has a specialized array type, BIT-VECTOR, which can only hold values of zero or one, which is more likely to be optimized for size than other types. Ada allows the programmer to specify data structures be optimized for size, which is nice.
Now, representing a lone true or false value is a different matter and I'd expect it to consume an entire register or whatnot under most anything, since you probably wouldn't be able to store anything else with the remaining space.
>Having a bool type in the type system is really a language usability concern, I don't think it's at all a performance optimization.
Ada has a boolean type because there are clearly boolean situations, such as predicates, and having a dedicated type reduces use errors. Programmers are encouraged to define their own boolean types, though, such as (On, Off), say.
>And when you want a bitmap, you can just use an int of the appropriate length and do bitwise operations on it.
That's what I was describing. Why should a high-level language have you making your own arrays? Don't you agree that programs would benefit from a specialized type for this that can more easily be optimized and specialized for the particular machine and whatnot?
- Safe code cannot access uninitialized memory under any circumstances (unless unsafe code accidentally vends it to safe code).
- The simple case you mentioned, of using a variable without initializing it, is always a hard error. This applies in both safe and unsafe code.
- ...However, unsafe code can explicitly ask for uninitialized memory, like the code in the blog post does. It's not really useful to ask for an uninitialized integer, but you may want to allocate a large struct on the stack and not initialize it.
- Unsafe code can also obtain uninitialized memory in other ways, such as by calling malloc, which allocates memory that starts in an uninitialized state. (The alternative is to zero the memory after allocating it, but that's slower.)
That said, Ada certainly got many things right. it was an important milestone. But even Ada has "unchecked" operations (such as deallocation), which is exactly what unsafe Rust is, and then you have all the same problems about undefined behavior and having to describe an abstract machine to specify what exactly is (not) undefined behavior and so on.
But, for a counter-point: what is an example of a code/algorithm that not only uses undefined behaviour (i.e. relies on it in order to compile to fast, optimized code), but also couldn't possibly be rewritten to eliminate undefined behaviour (while keeping the same speed)?
"couldn't possibly be rewritten" isn't always the issue; sometimes you need to improve the toolchain and language to provide a supported non-undefined solution, for instance.
Any code that handles signed integers is going to assume that overflow/underflow does not happen.
2. The poster’s job is to work on defining unsafe Rust, where UB is still a thing. It has to be, to some degree, as that’s the entire point.
3. Miri, references in the post, is an interpreter for the Rust abstract machine (or will be, once we’re done defining it) and gives warnings for many kinds of UB already. The hope is that it will be able to do so for all of it in the future. Doing so means defining what “all of it” means, and that’s still in progress.
"This program relies on user input, which is undefined behavior."
Should the following code have a warning? It has undefined behavior if argc == 0.
int main(int argc, char **argv) {
return **argv;
}
> refuse to compile/use implementation-defined behaviour (i.e. exactly "what the hardware does")
malloc is guaranteed to be 16-byte aligned on macOS. Should the following code not compile?
void *memalign(size_t size, size_t alignment) {
#if TARGET_OS_MAC
if (alignment < 16) {
return malloc(size);
}
#endif
// General case
}Undefined behavior is, for the most part, meant to enable compiler optimizations. If you're willing to do all your optimizations by hand rather than relying on the compiler to do them – in other words, use C as the "portable assembler" it was originally conceived as – then you don't really need it. (At least, not to the extent it exists in C.) And for small, tight loops, that's a perfectly reasonable proposition. For large programs, on the other hand, especially if you want to pile on a lot of abstraction and rely on the compiler to turn it into nice code (see C++)... not so much.