17 ms·

“What the Hardware Does” Is Not What Your Program Does: Uninitialized Memory

124 points by pornel 7y ago

saagarjha 7y ago
> So each time an uninitialized variable gets used, we can just use any machine register—and for different uses, those can be different registers! 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. 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).
- cperciva 7y ago
  It could do that, but it doesn't have to. A common example is "a variable is set inside a loop and used outside it"; if the loop runs zero times, the variable will be used uninitialized, but the fastest compilation will assume that the loop runs at least once and read the value from whatever register/memory location the loop writes into.
an_d_rew 7y ago
> the Rust program you wrote does not run on your hardware. It runs on the Rust abstract machine 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.
- twic 7y ago
  I don't like this formulation much. I would rather say that the program does indeed run on your hardware, but the program that runs is not the program you wrote. It's the program into which program you wrote has transformed by the compiler - better yet, it could be any one of the programs into which the compiler is allowed to transform the program you wrote. 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!
  - anp 7y ago
    > 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?
    - twic 7y ago
      The kind of reasoning we do is "if thread A writes to this location, then next time thread B writes to this location, it will have to take ownership of the cache line, which will take N cycles, so let's not do that". I don't think that kind of performance reasoning maps on to anything in Rust.
  - twic 7y ago
    I missed out so many words in this comment. I need to hire a proofreader.
  - ralfjung 7y ago
    I think thinking about real hardware (most of the time) just distracts from thinking about what your program "actually does", which is specified by the abstract machine. By thinking in terms of the abstract machine, you can forget about compilers and optimizations when writing your program, and focus on your code and what it does. 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.
rini17 7y ago
Is there an example of actually helpful and practical enabled-by-undefined-behavior optimization in C/C++? All I can remember are discussions of its pitfalls, like this.
- steveklabnik 7y ago
  One classic helpful example that gets brought up is integer overflow and loops. Because overflow is undefined in C and C++, the loop doesn’t need to check for it on each iteration.
  - mhh__ 7y ago
    https://d.godbolt.org/z/_r6C9N https://d.godbolt.org/z/_r6C9N Example of an Integer overflow based optimization
    - rini17 7y ago
      This is considered a practical example? Regardless, checking a register or hot value already in cache against a constant is free on modern CPUs.
      - mhh__ 7y ago
        It's not a practical example but it's relatively non trivial e.g. some otherwise good compilers can't figure that one out.
    - andreareina 7y ago
      Wait, how does that work? Without overflow, how does the compiler prove that eventually x == 7?
      - cryptonector 7y ago
        If x <= 7 then the answer will be 420, but if x > 7 then behavior is undefined because x will overflow, and x is signed, and signed integer overflow is UB in C, so the compiler is free to, for example, conclude that blazeit() is never called with x > 7, thus it can prove that blazeit() always returns 420. Besides, if the compiler chooses to implement signed integer overflow much like unsigned integer overflow, then x will eventually come around to 7 anyways, so the answer must be 420.
tomp 7y ago
This is just terrible. I'm really sad that it's 2019, and not only are we still talking about undefined behaviour, but there are also blog posts arguing for undefined behaviour! I expect a good (programmer-friendly) compiler to at least warn the programmer in any case of provable, or potential, undefined behaviour, or ideally, refuse to compile/use implementation-defined behaviour (i.e. exactly "what the hardware does"). Anything else is basically just inviting security bugs in your code. 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)?
- ummonk 7y ago
  You mentioned it briefly with "implementation-defined behavior" but tons of C/C++ relies on technically undefined behavior that has normal behavior on standard compiler / platform combinations.
- JoshTriplett 7y ago
  > 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.
- nemetroid 7y ago
  > 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)? Any code that handles signed integers is going to assume that overflow/underflow does not happen.
  - steveklabnik 7y ago
    Note that this isn’t UB in Rust.
martinhath 7y ago
Why aren't undefined bytes like these treated in the same way as I/O data? That is, arbitrary but fixed data? This seems to align fairly well with how I think about uninitialized data.
- YawningAngel 7y ago
  Because it's faster not to do that and these compilers don't attempt to behave in safe or predictable ways when UB is invoked.
  - martinhath 7y ago
    Of course it's faster - any program can be compiled into something "faster" by making the entire thing do nothing. What I mean is, why isn't uninitialized memory properly defined to be an arbitrary fixed string of bytes? In the example of the post, the compiler would look into `always_returns_true`, and either say "okay, is `x < 150`: well, I have no idea what `x` is, so I can't tell for sure", OR "Ah, for any value of `x` this expression is true, so let's replace it with `true`". There would be no 257th value of "uninitialized"; the value of `x` would definitely be a single value in the allowed range of that type, but it's indeterminable.
    - cesarb 7y ago
      It's like you suggested in your parent comment: uninitialized memory is similar to I/O data, which can change at any moment without warning. That is, it can be 200 at the "x < 150" and moments later 100 at the "x > 120". > 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.
      - martinhath 7y ago
        Ah, I knew my analogy would bite me :) I didn't mean IO as in "can change at any moment", but as in "read from a file but you have no idea what it is". 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.
rkagerer 7y ago
Would have liked to see the machine code generated by the example function, and a deeper dive mapping compiler choices to the unintuitive results. 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.
- deleted 7y ago
  [deleted]
- Arnavion 7y ago
  The dropdown next to the "Run" button in the playground link shows you the ASM. But here's the relevant part: playground::main: push rax call std::panicking::begin_panic ud2 That is, it's an unconditional panic.
- rrobukef 7y ago
  The provided example ([rust playground](https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=da278adb50142d14909df74ea1e43069) https://play.rust-lang.org/?version=stable&mode=release&edit...) can generate assembly ('...' next to 'Run'). `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?
  - ralfjung 7y ago
    > 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.
userbinator 7y ago
When K&R invented C, and when ISO/ANSI standardised C, I don't think this is at all what they had in mind for UB. 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 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.)
- nothrabannosir 7y ago
  This is driven by programmers' insatiable thirst for performance. Compiler writers are constantly judged on benchmarks, and the only way to squeeze that last flop out of a piece of code is to take the specification to its extreme. 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.
  - naniwaduni 7y ago
    > This is driven by programmers' insatiable thirst for performance. Compiler writers are constantly judged on benchmarks, and the only way to squeeze that last flop out of a piece of code is to take the specification to its extreme. 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.
deleted 7y ago
[deleted]
quotemstr 7y ago
I disagree that bit and byte level uninitialized models are equivalent. Consider a program that uses one bit of a bitfield in a stack allocated strict. The compiler is free to preserve the value of that bit however it pleases --- e.g., in the carry flag --- and randomize the rest of the bits if you ever read the whole byte.
- ralfjung 7y ago
  Hm, good point about the bitfields. The paper I cite [1] actually talks specifically about bitfields as their precise semantics in the presence of "poison"-style uninitialized memory is not entirely clear yet. [1]: http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf
verisimilitudes 7y ago
The real issue is the C and C++ languages are horrible languages. They're too high-level to correspond to any real machine, yet so low-level so as to make such an abstract machine useful. The C language leaves the precise lengths of types up for grabs, as merely one example. As for Rust, I'd figure it's poor as well, considering it follows in the footsteps of C++. 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: https://annexi-strayline.com/blog https://annexi-strayline.com/blog
- kyllo 7y ago
pizlonator 7y ago
Sounds like a lot of excuses for what is really a compiler bug that found its way into the spec.
- saagarjha 7y ago
  Undefined behavior is not a compiler bug: it's a necessity that is required to have language constructs that give you a way of doing things for which there is no good way to define the behavior of. Your compiler optimizes your code every day by concluding that you're not doing anything illegal: it would have a rather miserable time if it couldn't make these assumptions.
scoutt 7y ago
I appreciate the attempt to explain low-level stuff, but I think this is a high-level language programmer trying to understand herself/himself an issue without a clear idea of what he/she is talking about >> 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.
- dancek 7y ago
  > 0..256?? Is this still 8-bits bytes?? In Rust a..b means the range a <= x < b, so yes, that is an 8-bit byte.
  - scoutt 7y ago
    An 8-bit byte can hold 256 values, from 0 to 255, and cannot hold a value = 256, whatever the philosophy is.
    - ChrisSD 7y ago
      Read what dancek said again. In Rust `a..b` means a <= x < b So 0..256 is 0 <= x < 256 That is "less than" 256. There's no equals (that would be `0..=256` in Rust).
      - scoutt 7y ago
        Oh my.... Well, I guess the author realized about the confusion in every other non-Rust programmer it generates (https://git.ralfj.de/web.git/commitdiff/13622f8642fc071bedf32dba3efbd50a5906032c https://git.ralfj.de/web.git/commitdiff/13622f8642fc071bedf3...).
- noobermin 7y ago
  The problem here (and I caught it too and sort of recoiled at it) was they were using their logic and worse language/word choice regarding the "abstract machine" being the actual thing we should think about when reasoning about a programming language before they actually went out and were explicit that's what they were doing. They saved the explicit thesis until the end of the piece. They should have traded the writer's desire to be witty and hide the lede and just lead with it upfront. 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.
rthrowayay 7y ago
This poison thing is interesting because it seems like one poison value could have the capability of poisoning all the data in your program. You could imagine a faithful implementation of the rust abstract machine after hitting one code path would cause your program to start generating complete nonsense.
IshKebab 7y ago
I don't think this is really right. He claims that uninitialised memory is not just random bytes, but it is! 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.
- ralfjung 7y ago
  > I don't think this is really right. He claims that uninitialised memory is not just random bytes, but it is! 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).
  - IshKebab 7y ago
    You missed my point. Rust and C may treat uninitialised memory in a special way, but that doesn't change what uninitialised memory actually is. Think about assembly. What is uninitialised memory there? It's just memory with an unknown value.

124 points by pornel 7y ago

> So each time an uninitialized variable gets used, we can just use any machine register—and for different uses, those can be different registers! 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. 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).

cperciva 7y ago
It could do that, but it doesn't have to. A common example is "a variable is set inside a loop and used outside it"; if the loop runs zero times, the variable will be used uninitialized, but the fastest compilation will assume that the loop runs at least once and read the value from whatever register/memory location the loop writes into.

an_d_rew 7y ago

> the Rust program you wrote does not run on your hardware. It runs on the Rust abstract machine 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.

twic 7y ago
I don't like this formulation much. I would rather say that the program does indeed run on your hardware, but the program that runs is not the program you wrote. It's the program into which program you wrote has transformed by the compiler - better yet, it could be any one of the programs into which the compiler is allowed to transform the program you wrote. 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!
- anp 7y ago
  > 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?
  - twic 7y ago
    The kind of reasoning we do is "if thread A writes to this location, then next time thread B writes to this location, it will have to take ownership of the cache line, which will take N cycles, so let's not do that". I don't think that kind of performance reasoning maps on to anything in Rust.
- twic 7y ago
  I missed out so many words in this comment. I need to hire a proofreader.
- ralfjung 7y ago
  I think thinking about real hardware (most of the time) just distracts from thinking about what your program "actually does", which is specified by the abstract machine. By thinking in terms of the abstract machine, you can forget about compilers and optimizations when writing your program, and focus on your code and what it does. 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.

rini17 7y ago

Is there an example of actually helpful and practical enabled-by-undefined-behavior optimization in C/C++? All I can remember are discussions of its pitfalls, like this.

steveklabnik 7y ago
One classic helpful example that gets brought up is integer overflow and loops. Because overflow is undefined in C and C++, the loop doesn’t need to check for it on each iteration.
- mhh__ 7y ago
  https://d.godbolt.org/z/_r6C9N https://d.godbolt.org/z/_r6C9N Example of an Integer overflow based optimization
  - rini17 7y ago
    This is considered a practical example? Regardless, checking a register or hot value already in cache against a constant is free on modern CPUs.
    - mhh__ 7y ago
      It's not a practical example but it's relatively non trivial e.g. some otherwise good compilers can't figure that one out.
  - andreareina 7y ago
    Wait, how does that work? Without overflow, how does the compiler prove that eventually x == 7?
    - cryptonector 7y ago
      If x <= 7 then the answer will be 420, but if x > 7 then behavior is undefined because x will overflow, and x is signed, and signed integer overflow is UB in C, so the compiler is free to, for example, conclude that blazeit() is never called with x > 7, thus it can prove that blazeit() always returns 420. Besides, if the compiler chooses to implement signed integer overflow much like unsigned integer overflow, then x will eventually come around to 7 anyways, so the answer must be 420.

tomp 7y ago

This is just terrible. I'm really sad that it's 2019, and not only are we still talking about undefined behaviour, but there are also blog posts arguing for undefined behaviour! I expect a good (programmer-friendly) compiler to at least warn the programmer in any case of provable, or potential, undefined behaviour, or ideally, refuse to compile/use implementation-defined behaviour (i.e. exactly "what the hardware does"). Anything else is basically just inviting security bugs in your code. 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)?

ummonk 7y ago
You mentioned it briefly with "implementation-defined behavior" but tons of C/C++ relies on technically undefined behavior that has normal behavior on standard compiler / platform combinations.
JoshTriplett 7y ago
> 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.
nemetroid 7y ago
> 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)? Any code that handles signed integers is going to assume that overflow/underflow does not happen.
- steveklabnik 7y ago
  Note that this isn’t UB in Rust.

martinhath 7y ago

Why aren't undefined bytes like these treated in the same way as I/O data? That is, arbitrary but fixed data? This seems to align fairly well with how I think about uninitialized data.

YawningAngel 7y ago
Because it's faster not to do that and these compilers don't attempt to behave in safe or predictable ways when UB is invoked.
- martinhath 7y ago
  Of course it's faster - any program can be compiled into something "faster" by making the entire thing do nothing. What I mean is, why isn't uninitialized memory properly defined to be an arbitrary fixed string of bytes? In the example of the post, the compiler would look into `always_returns_true`, and either say "okay, is `x < 150`: well, I have no idea what `x` is, so I can't tell for sure", OR "Ah, for any value of `x` this expression is true, so let's replace it with `true`". There would be no 257th value of "uninitialized"; the value of `x` would definitely be a single value in the allowed range of that type, but it's indeterminable.
  - cesarb 7y ago
    It's like you suggested in your parent comment: uninitialized memory is similar to I/O data, which can change at any moment without warning. That is, it can be 200 at the "x < 150" and moments later 100 at the "x > 120". > 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.
    - martinhath 7y ago
      Ah, I knew my analogy would bite me :) I didn't mean IO as in "can change at any moment", but as in "read from a file but you have no idea what it is". 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.

rkagerer 7y ago

Would have liked to see the machine code generated by the example function, and a deeper dive mapping compiler choices to the unintuitive results. 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.

deleted 7y ago
[deleted]
Arnavion 7y ago
The dropdown next to the "Run" button in the playground link shows you the ASM. But here's the relevant part: playground::main: push rax call std::panicking::begin_panic ud2 That is, it's an unconditional panic.
rrobukef 7y ago
The provided example ([rust playground](https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=da278adb50142d14909df74ea1e43069) https://play.rust-lang.org/?version=stable&mode=release&edit...) can generate assembly ('...' next to 'Run'). `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?
- ralfjung 7y ago
  > 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.

userbinator 7y ago

When K&R invented C, and when ISO/ANSI standardised C, I don't think this is at all what they had in mind for UB. 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 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.)

nothrabannosir 7y ago
This is driven by programmers' insatiable thirst for performance. Compiler writers are constantly judged on benchmarks, and the only way to squeeze that last flop out of a piece of code is to take the specification to its extreme. 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.
- naniwaduni 7y ago
  > This is driven by programmers' insatiable thirst for performance. Compiler writers are constantly judged on benchmarks, and the only way to squeeze that last flop out of a piece of code is to take the specification to its extreme. 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.

deleted 7y ago

[deleted]

quotemstr 7y ago

I disagree that bit and byte level uninitialized models are equivalent. Consider a program that uses one bit of a bitfield in a stack allocated strict. The compiler is free to preserve the value of that bit however it pleases --- e.g., in the carry flag --- and randomize the rest of the bits if you ever read the whole byte.

ralfjung 7y ago
Hm, good point about the bitfields. The paper I cite [1] actually talks specifically about bitfields as their precise semantics in the presence of "poison"-style uninitialized memory is not entirely clear yet. [1]: http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf

verisimilitudes 7y ago

The real issue is the C and C++ languages are horrible languages. They're too high-level to correspond to any real machine, yet so low-level so as to make such an abstract machine useful. The C language leaves the precise lengths of types up for grabs, as merely one example. As for Rust, I'd figure it's poor as well, considering it follows in the footsteps of C++. 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: https://annexi-strayline.com/blog https://annexi-strayline.com/blog

kyllo 7y ago

pizlonator 7y ago

Sounds like a lot of excuses for what is really a compiler bug that found its way into the spec.

saagarjha 7y ago
Undefined behavior is not a compiler bug: it's a necessity that is required to have language constructs that give you a way of doing things for which there is no good way to define the behavior of. Your compiler optimizes your code every day by concluding that you're not doing anything illegal: it would have a rather miserable time if it couldn't make these assumptions.

scoutt 7y ago

I appreciate the attempt to explain low-level stuff, but I think this is a high-level language programmer trying to understand herself/himself an issue without a clear idea of what he/she is talking about >> 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.

dancek 7y ago
> 0..256?? Is this still 8-bits bytes?? In Rust a..b means the range a <= x < b, so yes, that is an 8-bit byte.
- scoutt 7y ago
  An 8-bit byte can hold 256 values, from 0 to 255, and cannot hold a value = 256, whatever the philosophy is.
  - ChrisSD 7y ago
    Read what dancek said again. In Rust `a..b` means a <= x < b So 0..256 is 0 <= x < 256 That is "less than" 256. There's no equals (that would be `0..=256` in Rust).
    - scoutt 7y ago
      Oh my.... Well, I guess the author realized about the confusion in every other non-Rust programmer it generates (https://git.ralfj.de/web.git/commitdiff/13622f8642fc071bedf32dba3efbd50a5906032c https://git.ralfj.de/web.git/commitdiff/13622f8642fc071bedf3...).
noobermin 7y ago
The problem here (and I caught it too and sort of recoiled at it) was they were using their logic and worse language/word choice regarding the "abstract machine" being the actual thing we should think about when reasoning about a programming language before they actually went out and were explicit that's what they were doing. They saved the explicit thesis until the end of the piece. They should have traded the writer's desire to be witty and hide the lede and just lead with it upfront. 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.

rthrowayay 7y ago

This poison thing is interesting because it seems like one poison value could have the capability of poisoning all the data in your program. You could imagine a faithful implementation of the rust abstract machine after hitting one code path would cause your program to start generating complete nonsense.

IshKebab 7y ago

I don't think this is really right. He claims that uninitialised memory is not just random bytes, but it is! 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.

ralfjung 7y ago
> I don't think this is really right. He claims that uninitialised memory is not just random bytes, but it is! 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).
- IshKebab 7y ago
  You missed my point. Rust and C may treat uninitialised memory in a special way, but that doesn't change what uninitialised memory actually is. Think about assembly. What is uninitialised memory there? It's just memory with an unknown value.