From ae9f5d237c9ee2fc21a33e741849f5845669f5d5 Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Sun, 14 Jul 2019 18:29:49 +0200 Subject: [PATCH] new post on uninitialized memory --- personal/_posts/2019-07-14-uninit.md | 116 +++++++++++++++++++++++++++ 1 file changed, 116 insertions(+) create mode 100644 personal/_posts/2019-07-14-uninit.md diff --git a/personal/_posts/2019-07-14-uninit.md b/personal/_posts/2019-07-14-uninit.md new file mode 100644 index 0000000..f454bfd --- /dev/null +++ b/personal/_posts/2019-07-14-uninit.md @@ -0,0 +1,116 @@ +--- +title: '"What The Hardware Does" is not What Your Program Does: Uninitialized Memory' +categories: rust +--- + +This post is about uninitialized memory, but also about the semantics of highly optimized "low-level" languages in general. +I will try to convince you that reasoning by "what the hardware does" is inherently flawed when talking about languages such as Rust, C or C++. +These [are not low-level languages](https://queue.acm.org/detail.cfm?id=3212479). +I have made this point before [in the context of pointers]({% post_url 2018-07-24-pointers-and-bytes %}); this time it is going to be about uninitialized memory. + +The trigger for this post is the [deprecation of `mem::uninitialized()`](https://blog.rust-lang.org/2019/07/04/Rust-1.36.0.html#maybeuninitt%3E-instead-of-mem::uninitialized) with Rust 1.36, but the post is just as relevant for C/C++ as it is for Rust.[^deprecate] + +[^deprecate]: This deprecation has been in the works for [more than two years](https://github.com/rust-lang/rfcs/pull/1892), and it has been almost a year since [I took over pushing for this](https://github.com/rust-lang/rfcs/pull/1892#issuecomment-410430449). I am very happy that we are finally there! + + + +## The pitfalls of uninitialized memory + +When you allocate some memory (whether it be on the stack or heap), and you do not initialize it, what are its contents? +We call this "uninitialized memory", but what exactly does this mean and what happens when it gets read? +For many languages, this question is inconsequential: in Java, Haskell, OCaml and generally in all safe languages, uninitialized memory cannot be read, this is prevented by the type system. +The same is true in safe Rust, actually. +However, in unsafe Rust as well as in inherently unsafe languages such as C and C++, not having to initialize memory can be an important optimization, so this is a very relevant question. + +The C and C++ specifications (without going into all the detail here) say that uninitialized memory is "indeterminate", but the details of what exactly that means [are unclear](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1793.pdf). +Many people will tell you that "uninitialized memory contains a random bit pattern". +This is wrong. +They might also talk about the system allocator or how the OS kernel allocates pages for the program to use. +That is just irrelevant information.[^blame] + +[^blame]: To be clear, I am not blaming anyone for getting this wrong. There is tons of misinformation out there, and the standard is awfully ambiguous. That is why I am writing this post. + +Here is an example to demonstrate why "random bit pattern" cannot describe uninitialized memory: +{% highlight rust %} +use std::mem; + +fn always_returns_true(x: u8) -> bool { + x < 150 || x > 120 +} + +fn main() { + let x: u8 = unsafe { mem::uninitialized() }; + assert!(always_returns_true(x)); +} +{% endhighlight %} +`always_returns_true` is a function that, clearly, will return `true` for any possible 8-bit unsigned integer. +After all, *every* possible value for `x` will be less than 150 or bigger than 120. +A quick loop [confirms this](https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=58168009e601a2f01b08981f907a473c). +However, if you [run the example](https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=da278adb50142d14909df74ea1e43069), you can see the assertion fail.[^godbolt] + +[^godbolt]: In case this changes with future Rust versions, [here is the same example on godbolt](https://godbolt.org/z/JX4B4N); the `xor eax, eax` indicates that the function returns 0, aka `false`. And [here is a version for C++](https://godbolt.org/z/PvZGQB); imagine calling `make_true(true)` which *should* always return `true` but as the assembly shows will return `false`. + +## What *is* uninitialized memory? + +How is this possible? +The answer is that every byte in memory cannot just have a value in `0..256`, it can also be "uninitialized". +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. +Performing operations such as comparison on uninitialized bytes is undefined behavior. +As a consequence, our program has undefined behavior, so we should not be surprised that it acts "weirdly". + +Of course, there is a reason for this undefined behavior. +Compilers don't just want to annoy programmers. +Ruling out operations such as comparison on uninitialized data is useful, because it means the compiler does not have to "remember" which exact bit pattern an uninitialized variable has! +A well-behaved (UB-free) program cannot observe that bit pattern anyway. +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. +That explains why our compiled example program behaves the way it does. + +When thinking about Rust (or C, or C++), you have to imagine that every byte in memory is either initialized to some value in `0..256`, or *uninitialized*. +You can think of memory as storing an `Option` at every location.[^pointers] +When new memory gets allocated for a local variable (on the stack) or on the heap, there is actually nothing random happening, everything is completely deterministic: every single byte of this memory is marked as *uninitialized*. +Every location stores a `None`. +(In LLVM, this `None` corresponds to `poison`, which [has the potential to replace `undef` entirely](http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf).) + +When writing safe Rust, you do not have to worry about this, but this is the model you should have in your head when dealing with uninitialized memory in unsafe code. +Alexis wrote a [great post](https://gankro.github.io/blah/initialize-me-maybe/) on which APIs to use for that in Rust; there is no need for me to repeat all that here. +(In that post, Alexis says that every *bit* can be either 0, 1 or uninitialized, as opposed to every *byte* being initialized or not. Given that memory accesses happen at byte granularity, these two models are actually equivalent.) + +[^pointers]: In fact, [bytes are even more complicated than that]({% post_url 2018-07-24-pointers-and-bytes %}), but that is another topic. + +## What can you do with uninitialized memory? + +Now that we have a concrete way to talk about uninitialized memory, we can talk about which operations are allowed on values involving uninitialized bytes. +My interpretation of the rules in C/C++, and my proposal for the rules in Rust, is that *any* operation working on the "value" of an integer (arithmetic and logical operations, comparisons, conditional jumps) is undefined behavior if any input is uninitialized. +In particular, `x + 0` is UB if `x` is not initialized. +However, this still leaves many questions open, such as whether even just *creating* an uninitialized `u8` is undefined behavior in Rust (which is the subject of [active discussion](https://github.com/rust-lang/unsafe-code-guidelines/issues/71)), or what happens when some but not all bytes of the input are uninitialized. +Over time, we will come to some kind of compromise here. +The important part (for both Rust and C/C++) however is that we have this discussion with a clear mental model in our minds for *what uninitialized memory is*. +I see Rust on a good path here; I hope the C/C++ committees will eventually follow suit. + +## "What the hardware does" considered harmful + +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. +Sure, hardware (well, [most hardware](https://devblogs.microsoft.com/oldnewthing/20040119-00/?p=41003)) does not have a notion of "uninitialized memory". +But *the Rust program you wrote does not run on your hardware*. +It runs on the Rust abstract machine, and that machine (which only exists in our minds) *does* have a notion of "uninitialized memory". +The real, physical hardware that we end up running the compiled program on is a very efficient *but imprecise* implementation of this abstract machine, and all the rules that Rust has for undefined behavior work together to make sure that this imprecision is not visible for *well-behaved* (UB-free) programs. +But for programs that do have UB, this "illusion" breaks down, and [anything is possible](https://raphlinus.github.io/programming/rust/2018/08/17/undefined-behavior.html). + +This does not just apply to uninitialized memory: for example, in x86 assembly, there is no difference between "relaxed" and "release"/"acquire"-style atomic memory accesses. +But when writing Rust programs, even when writing Rust programs that you only intend to compile to x86, "what the hardware does" just does not matter. +The Rust abstract machine *does* make a distinction between "relaxed" and "release"/"acquire", and your program will go wrong if you ignore that fact. +After all, x86 does not have "uninitialized bytes" either, and still our example program above went wrong. + +Unfortunately, in my opinion not enough of the discussion around undefined behavior in Rust/C/C++ is focused on what concretely the "abstract machine" of these languages looks like. +Instead, people often talk about hardware behavior and how that can be altered by a set of allowed optimizations---but the optimizations performed by compilers change as new tricks are discovered, and it's the abstract machines that define if these tricks are allowed. +C/C++ have extensive standards that describe many cases of undefined behavior in great detail, but nowhere does it say that memory of the C/C++ abstract machine stores `Option` instead of the `u8` one might naively expect. +In Rust, I am very happy that we have [Miri](https://github.com/rust-lang/miri/), which is meant to be (very close to) a direct implementation of the Rust abstract machine, and I am strongly advocating for us to write the Rust specification (once that gets going) in a style that makes this machine very explicit. +I hope C/C++ will come around to do the same, and there is some [great work in that direction](https://www.cl.cam.ac.uk/~pes20/cerberus/), but only time will tell to what extend that can affect the standard itself. + +If you want to do me a favor, please spread the word! +I am trying hard to combat the myth of "what the hardware does" in Rust discussions whenever I see it, but I obviously don't see all the discussions---so the next time you see such an argument, no matter whether it is about uninitialized memory or [concurrency](http://hboehm.info/boehm-hotpar11.pdf) or [out-of-bounds memory accesses](https://github.com/rust-lang/rust/issues/32976#issuecomment-446775360) or anything else, please help by steering the discussion towards "what the Rust abstract machine does", and how we can design and adjust the Rust abstract machine in a way that it is most useful for programmers and optimizing compilers alike. + +#### Footnotes -- 2.30.2