personal/_posts/2017-07-14-undefined-behavior.md

   1 ---
   2 title: Undefined Behavior and Unsafe Code Guidelines
   3 categories: internship rust
   4 ---
   5
   6 Last year, the [Rust unsafe code guidelines strike team](https://internals.rust-lang.org/t/next-steps-for-unsafe-code-guidelines/3864) was founded, and I am on it. :-)
   7 So, finally, just one year later, this post is my take at what the purpose of that team is.
   8 <!-- MORE -->
   9 Warning:  This post may contain opinions.  You have been warned.
  10
  11 ## When are optimizations legal?
  12
  13 Currently, we have a pretty good understanding of what the intended behavior of *safe* Rust is.
  14 That is, there is general agreement (modulo some [bugs](https://github.com/rust-lang/rust/issues/27868)) about the order in which operations are to be performed, and about what each individual operation does.
  15
  16 For unsafe Rust, this is very different.
  17 There are multiple reasons for this.
  18 One particularly nasty one is related to compiler optimizations that rustc/LLVM either already perform today, or want to perform some day in the future.
  19 Consider the following simple function:
  20 {% highlight rust %}
  21 fn simple(x: &mut i32, y: &mut f32) -> i32 {
  22     *x = 3;
  23     *y = 4.0;
  24     *x
  25 }
  26 {% endhighlight %}
  27 We would like the compiler to be able to *reorder* these two stores without changing program behavior.
  28 After all, `x` and `y` are both mutable references, which the type system ensures are unique pointers, so they cannot possibly alias (i.e., the memory ranges they point to cannot overlap).
  29 After this transformation, the code contains `*x = 3; *x`, which can be further optimized to `*x = 3; 3`, saving a memory access.
  30 Compilers are able to get a lot of performance out of code by figuring out which operations are independent of each other, and then moving code around to either eliminate certain operations entirely (like the load of `x`), or making code faster to execute with clever scheduling that exploits the [parallelism](https://en.wikipedia.org/wiki/Instruction-level_parallelism) in modern CPU cores (this is per-core parallelism we are talking about, not the parallelism arising from having multiple cores).
  31
  32 Optimizations like reordering stores are based on the compiler making *assumptions* about the code, and then using these assumptions to justify a program transformation.
  33 In this case, the assumption is that the two stores never affect the same address.
  34 Usually, if a compiler wants to make such an assumption, it has to do some static analysis to *prove* that this assumption actually holds in any possible program execution.
  35 After all, if there is any execution for which the assumption does *not* hold, the optimization may be incorrect -- it could change what the program does!
  36
  37 Now, it turns out that it is often really hard to obtain precise aliasing information.
  38 This could be the end of the game:  No alias information, no way to verify our assumptions, no optimizations.
  39
  40 ## But we want to optimize anyway!
  41
  42 However, it turns out that compilers writers want these optimizations *so badly* that they came up with an alternative solution:
  43 Instead of putting the burden for verifying such assumptions on the compiler, they put it on the programmer.
  44
  45 To this end, the C standard says that memory accesses have to happen with the right "effective type":  If data was stored with a `float` pointer, it must not be read with an `int` pointer.
  46 If you violate this rule, your program has *undefined behavior* (UB) -- which is to say, the program may do *anything* when executed.
  47 Now, if the compiler wants to make a transformation like reordering the two stores in our example, it can argue as follows:
  48 In any particular execution of the given function, either `x` and `y` alias or they do not.
  49 If they do not, reordering the two writes is just fine.
  50 However, if they *do* alias, that would violate the effective type restriction, which would make the code UB -- so the compiler is permitted to do anything.
  51 *In particular*, it is permitted to reorder the two writes.
  52 As we have seen, in both of the possible cases, the reordering is correct; the compiler is thus free to perform the transformation.
  53
  54 Undefined behavior moves the burden of proving the correctness of this optimization from the compiler to the programmer.
  55 Unfortunately, it is often not easy to say whether a program has undefined behavior or not -- after all, such an analysis being difficult is the entire reason compilers rather rely on UB to perform their optimizations.
  56 Furthermore, while C compilers are happy to exploit the fact that a particular program *has* UB, they do not provide a way to test that executing a program *does not* trigger UB.
  57 In fact, it is pretty hard to perform such a test; the standard has not been written with such considerations in mind.
  58 This has given UB a very bad reputation, and mostly rightly so, I would say.
  59 [A lengthy blog post](https://blog.regehr.org/archives/1520) summarizes the situation quite well:
  60 There is progress being made with various sanitizers, but e.g. for the effective type restriction we discussed above, the mitigation (i.e., the way to check or otherwise make sure your programs are not affected) is "turn off optimizations that rely on this".
  61 That's not very satisfying.
  62
  63 ## Undefined Behavior in Rust
  64
  65 Coming back to Rust, where are we at?
  66 Safe Rust is [free from UB]({{ site.baseurl }}{% post_url 2017-07-08-rustbelt %}), but we still have to worry about unsafe Rust.
  67 For example, what if unsafe code crafts two aliasing mutable references (something that is prevented in safe Rust) and passes them to our `simple` function?
  68 This violates the assumptions we made when we reordered the two writes.
  69 If we want to permit this optimization (which we do!), we have to argue why it cannot change program behavior.
  70 It should be forbidden for unsafe Rust code to pass aliasing pointers to `simple`; doing so should result in UB.
  71 So we have to come up with rules for when Rust code is UB.
  72 This is what the unsafe code guidelines strike team set out to do.
  73
  74 We could of course just copy what C does, but I hope I convinced you that this is not a great solution.
  75 When defining UB for Rust, I hope we can do better than C.
  76 I think we should strive for programmers' intuition agreeing with the standard and the compiler on what the rules are.
  77 It turns out that is [not the case for C](https://www.cl.cam.ac.uk/~pes20/cerberus/notes50-survey-discussion.html), which leads to miscompilations and sometimes to security [vulerabilities](https://lwn.net/Articles/342330/).
  78
  79 I also think that tooling to *detect* UB is of paramount importance, and that the specification should be written in a way that such tooling is feasible.
  80 In fact, specifying a dynamic UB checker is a very good way to specify UB!
  81 Such a specification would describe the additional state that is needed at run-time to then *check* at every operation whether we are running into UB.
  82 It is with such considerations in my mind that I have previously written about [miri as an executable specification]({{ site.baseurl }}{% post_url 2017-06-06-MIR-semantics %}).
  83
  84 Coming up next on this channel:  During my [internship]({{ site.baseurl }}{% post_url 2017-05-23-internship-starting %}), I am working on such a specification.
  85 I have a draft ready now, and I want to share it with the world to see what the world thinks about it.