twinsem paper: directly link to current location

[web.git] / 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
index 702ac47454cbc7d626d74e7f09a151fd1d5fad56..bbb1468535f65b94a406fcf6b2d2205485484842 100644 (file)
--- a/personal/_posts/2019-07-14-uninit.md
+++ b/personal/_posts/2019-07-14-uninit.md
@@ -1,6 +1,6 @@
 ---
 title: '"What The Hardware Does" is not What Your Program Does: Uninitialized Memory'
 ---
 title: '"What The Hardware Does" is not What Your Program Does: Uninitialized Memory'

-categories: rust
+categories: rust research programming

 forum: https://internals.rust-lang.org/t/what-the-hardware-does-is-not-what-your-program-does-uninitialized-memory/10561
 ---
 
 forum: https://internals.rust-lang.org/t/what-the-hardware-does-is-not-what-your-program-does-uninitialized-memory/10561
 ---
 


@@ -36,48 +36,53 @@ Here is an example to demonstrate why "random bit pattern" cannot describe unini
 use std::mem;
 
 fn always_returns_true(x: u8) -> bool {
 use std::mem;
 
 fn always_returns_true(x: u8) -> bool {

-    x < 150 || x > 120
+    x < 120 || x == 120 || x > 120

 }
 
 fn main() {
 }
 
 fn main() {

-    let x: u8 = unsafe { mem::uninitialized() };
+    let x: u8 = unsafe { mem::MaybeUninit::uninit().assume_init() };

     assert!(always_returns_true(x));
 }
 {% endhighlight %}
     assert!(always_returns_true(x));
 }
 {% endhighlight %}

+**Update (2022-11-17):** Switched to `MaybeUninit` to keep the example working in newer versions of Rust.
+

 `always_returns_true` is a function that, clearly, will return `true` for any possible 8-bit unsigned integer.
 `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]
+After all, *every* possible value for `x` will be either less than 120, equal to 120, or bigger than 120.
+A quick loop [confirms this](https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=65b690fa3c1691e11d4d45955358cdbe).
+However, if you [run the example](https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=c17d299cacd626c572def0c4262aed69), 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`.
+[^godbolt]: In case this changes with future Rust versions, [here is the same example on godbolt](https://godbolt.org/z/9G67hP); the `xor eax, eax` indicates that the function returns 0, aka `false`. And [here is a version for C++](https://godbolt.org/z/TWrvcq).

 
 ## What *is* uninitialized memory?
 
 How is this possible?
 
 ## 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".
+The answer is that, in the "abstract machine" that is used to specify the behavior of our program, every byte in memory cannot just have a value in `0..256` (this is Rust syntax for a left-inclusive right-exclusive range), 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.
 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.
+Performing operations such as comparison on uninitialized bytes is [undefined behavior]({% post_url 2017-07-14-undefined-behavior %}).

 As a consequence, our program has undefined behavior, so we should not be surprised that it acts "weirdly".
 
 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.
+Of course, there is a reason for this undefined behavior; there is a reason the "abstract machine" is defined the way it is.

 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!
 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.
+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.

 That explains why our compiled example program behaves the way it does.
 That explains why our compiled example program behaves the way it does.

+[This LLVM document](http://nondot.org/sabre/LLVMNotes/UndefinedValue.txt) gives some more motivation for "unstable" uninitialized memory.

 
 

-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*.
+When thinking about Rust (or C, or C++), you have to think in terms of an "abstract machine", not the real hardware you are using.
+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<u8>` 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).)
 
 You can think of memory as storing an `Option<u8>` 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.
+When writing safe Rust, you do not have to worry about this, but this is the model that is good to 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.
 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.)
+(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, at least in Rust which does not have C-style bitfields.)

 
 [^pointers]: In fact, [bytes are even more complicated than that]({% post_url 2018-07-24-pointers-and-bytes %}), but that is another topic.
 
 
 [^pointers]: In fact, [bytes are even more complicated than that]({% post_url 2018-07-24-pointers-and-bytes %}), but that is another topic.
 


@@ -91,20 +96,38 @@ 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.
 
 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.
 

+Ruling out any operation on uninitialized values also makes it impossible to implement [this cute data structure](https://research.swtch.com/sparse).
+The `is-member` function there relies on the assumption that "observing" an uninitialized value (`sparse[i]`) twice gives the same result, which as we have seen above is not the case.
+This could be fixed by providing a "freeze" operation that, given any data, replaces the uninitialized bytes by *some* non-deterministically chosen *initialized* bytes.
+It is called "freeze" because its effect is that the value "stops changing each time you observe it".
+`is-member` would freeze `sparse[i]` once and then know for sure that "looking at it" twice will give consistent results.
+Unfortunately, since C/C++ do not acknowledge that their memory model is what it is, we do not have crucial operations such as "freeze" officially supported in compilers.
+At least for LLVM, that [might change though](http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf).
+

 ## "What the hardware does" considered harmful
 
 ## "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.
+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*.

 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).
 
 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).
 

+*Only* 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.[^sanitizer]
+
+[^sanitizer]: This does imply that tools like valgrind, that work on the final assembly, can never reliably detect *all* UB.
+

 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.
 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.
+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 if your program has UB.

 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.
 
 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.
 

+Of course, to explain *why* the abstract machine is defined the way it is, we have to look at optimizations and hardware-level concerns.
+But without an abstract machine, it is very hard to ensure that all the optimizations a compiler performs are consistent---in fact, both [LLVM](https://bugs.llvm.org/show_bug.cgi?id=35229) and [GCC](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65752) suffer from miscompilations caused by combining optimizations that all seem [fine in isolation, but together cause incorrect code generation]({% post_url 2020-12-14-provenance %}).
+The abstract machine is needed as an ultimate arbiter that determines which optimizations can be safely combined with each other.
+I also think that when writing unsafe code, it is much easier to keep in your head a fixed abstract machine as opposed to a set of optimizations that might change any time, and might or might not be applied in any order.
+

 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<u8>` instead of the `u8` one might naively expect.
 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<u8>` instead of the `u8` one might naively expect.


@@ -112,7 +135,7 @@ In Rust, I am very happy that we have [Miri](https://github.com/rust-lang/miri/)
 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 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.
+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 around and undefined behavior is involved, 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.

 
 As usual, if you have any comments, suggestions or questions, [let me know in the forums](https://internals.rust-lang.org/t/what-the-hardware-does-is-not-what-your-program-does-uninitialized-memory/10561).
 
 
 As usual, if you have any comments, suggestions or questions, [let me know in the forums](https://internals.rust-lang.org/t/what-the-hardware-does-is-not-what-your-program-does-uninitialized-memory/10561).