add CACM article to blog
[web.git] / personal / _posts / 2019-07-14-uninit.md
index e2089cb9ca09f42d97db73203f6ca40bc78e24f5..7af373fbf7b905276902a246cc1a024e3c82b286 100644 (file)
@@ -1,6 +1,6 @@
 ---
 title: '"What The Hardware Does" is not What Your Program Does: Uninitialized Memory'
-categories: rust
+categories: rust research
 forum: https://internals.rust-lang.org/t/what-the-hardware-does-is-not-what-your-program-does-uninitialized-memory/10561
 ---
 
@@ -36,7 +36,7 @@ Here is an example to demonstrate why "random bit pattern" cannot describe unini
 use std::mem;
 
 fn always_returns_true(x: u8) -> bool {
-    x < 150 || x > 120
+    x < 120 || x == 120 || x > 120
 }
 
 fn main() {
@@ -45,22 +45,22 @@ fn main() {
 }
 {% 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]
+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=812fe3c8655bfedcea37bb18bb70a945), 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?
-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/Ruby syntax for a left-inclusive right-exclusive range), 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.
-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".
 
-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.
@@ -78,7 +78,7 @@ When new memory gets allocated for a local variable (on the stack) or on the hea
 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.
 (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.)
 
@@ -122,8 +122,8 @@ The Rust abstract machine *does* make a distinction between "relaxed" and "relea
 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.
-The abstract machine is needed as an ultimate arbiter that shows if all of the optimizations are correct, or if some of them are in conflict with each other.
+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.
@@ -133,7 +133,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 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).