ralf/_posts/2018-12-26-stacked-borrows-barriers.md

   1 ---
   2 title: "Barriers and Two-phase Borrows in Stacked Borrows"
   3 categories: internship rust
   4 forum: https://internals.rust-lang.org/t/barriers-and-two-phase-borrows-in-stacked-borrows/9100
   5 ---
   6
   7 My internship ("research assistantship") with Mozilla has ended several weeks ago, and this post is a report of the most recent tweaks I made to Miri and Stacked Borrows.
   8 Neither project is by any means "done", of course.
   9 However, both have reached a fairly reasonable state, so I felt some kind of closing report made sense.
  10 Also, if I ever want to finish my PhD, I'll have to seriously scale down the amount of time I work on Rust -- so at least from my side, things will move more slowly from now on.
  11
  12 In particular, installing Miri and running your test suite in it is now just a single command away!
  13 Scroll all the way down if you are not interested in the rest.
  14
  15 <!-- MORE -->
  16
  17 ## Stacked Borrows Tweaks
  18
  19 I made some small tweaks to Stacked Borrows which mostly serve to make things overall more consistent.
  20 All of these have been incorporated into my [previous post on Stacked Borrows]({% post_url 2018-11-16-stacked-borrows-implementation %}).
  21
  22 The only noticeable functional change affects creating a shared reference: previously, that would push a `Shr` item to the stack before freezing the location.
  23 That would, however, permit mutation like in the following example:
  24
  25 {% highlight rust %}
  26 fn demo_shared_mutation(ptr: &mut u8) {
  27     let shared = &*ptr; // pushes a `Shr` item
  28     let raw = shared as *const u8 as *mut u8;
  29     unsafe { *raw = 5; } // allowed: unfreezing, then matching the `Shr` item
  30 }
  31 {% endhighlight %}
  32
  33 Since "no mutation through (pointers derived from) shared references" has been a rule in Rust pretty much from the beginning, I changed creating a shared reference to no longer unconditionally push a `Shr` item.
  34 That now only happens when the pointee is mutable because of an `UnsafeCell`.
  35 As a consequence, the code above is now forbidden.
  36
  37 ## Barriers
  38
  39 Beyond these small tweaks, I implemented the *barriers* that I already described in my [original proposal]({% post_url 2018-08-07-stacked-borrows %}).
  40 The purpose of barriers is to handle code like the following:
  41
  42 {% highlight rust %}
  43 fn aliasing(ptr: &mut u8, raw: *mut u8) -> u8 {
  44     let val = *ptr;
  45     unsafe { *raw = 4; }
  46     val // we would like to move the `ptr` load down here
  47 }
  48
  49 fn demo_barrier() -> u8 {
  50     let x = &mut 8u8;
  51     let raw = x as *mut u8;
  52     aliasing(unsafe { &mut *raw }, raw)
  53 }
  54 {% endhighlight %}
  55
  56 `aliasing` here gets two aliasing pointers as argument.
  57 This means writing to `raw` changes the value in `ptr`, so the desired optimization would change the behavior of `demo_barrier` (currently it returns 8, after moving the load of `ptr` down it returns 4).
  58 Stacked Borrows without barriers would allow this code because `ptr` does not get used again after `raw`.
  59
  60 To disallow this code and enable the desired optimization, we introduce a new kind of item that can be pushed to the per-location stack: a *function barrier* referring to a particular function call.
  61 While the function is running, the barrier may not be popped.
  62 The type of items on the borrow stack therefore now looks as follows:
  63
  64 {% highlight rust %}
  65 pub enum BorStackItem {
  66     Uniq(Timestamp),
  67     Shr,
  68     FnBarrier(CallId),
  69 }
  70 {% endhighlight %}
  71
  72 These barriers get pushed when doing the initial retagging of a function (remember that we insert `Retag` statements for all arguments at the beginning of each function).
  73 We do this only for references (not for `Box`), and we do *not* push a barrier to locations inside a shared `UnsafeCell`.
  74 Concretely, between steps 4 and 5 of retagging (after we performed the action of an access and before we push the new item), we push a `FnBarrier` referring to the current function call.
  75 Moreover, when retagging with barriers, we do not perform the usual redundancy check -- even if the reborrow is redundant, pushing the barrier might be necessary.
  76
  77 Barriers have no effect when a pointer gets dereferenced: looking for the item in the stack just skips over barriers.
  78 However, when performing a memory access and popping items from the stack, we stop when we encounter an active barrier, i.e., a barrier for a function call that is still ongoing.
  79 If that ever happens, we have undefined behavior.
  80
  81 Together, these rules make the above example invalid code, and hence enable our optimization: when doing the memory access in `*raw = 4`, we pop until we find a `Shr` item.
  82 That will hit the barrier that was added when `aliasing` did the initial retagging of `val`, triggering UB.
  83
  84 An interesting (and positive!) consequence of barriers is that they make the following code UB:
  85
  86 {% highlight rust %}
  87 fn aliasing(ptr1: &mut u8, ptr2: &mut u8) {}
  88
  89 fn demo_barrier() -> u8 {
  90     let x = &mut 8u8;
  91     let raw = x as *mut u8;
  92     aliasing(unsafe { &mut *raw }, x)
  93 }
  94 {% endhighlight %}
  95
  96 Without barriers, there is no problem with this code because `aliasing` does not actually *use* the two aliasing pointers in conflicting ways.
  97 With barriers, the initial retag of `ptr2` goes wrong because it tries to pop off the barrier that just got pushed for `ptr1`.
  98 That's great, because we don't actually want to allow passing two aliasing pointers to `aliasing`.
  99
 100 Barriers have one more effect: when memory gets deallocated, it must not have any active barriers left in its stacks.
 101 Barriers so far ensure that a reference passed to a function does not get *invalidated* during that function call; this extra check ensures that it also does not get *deallocated*.
 102 This is important, because we tell LLVM via the `dereferencable` attribute that the reference is, well, dereferencable for the duration of the function call.
 103 To justify this attribute, we have to argue that the program really cannot deallocate this memory
 104
 105
 106 ### Intuition and Design Decisions
 107
 108 One high-level intuition for barriers is that they encode the rule that a reference passed to a function outlives the function call.
 109 The item matching that reference can never get popped while the function is still being executed: if it would get popped, we would hit the barrier and trigger UB.
 110 This is also why we don't have barriers for `Box`: they don't have any such relationship to function calls.
 111
 112 The other exception, about not having barriers for shared `UnsafeCell`, is more subtle.
 113 In my [previous post]({% post_url 2018-11-16-stacked-borrows-implementation %}), I had an example of a function where a shared and a mutable reference alias (the shared reference being `&RefCell` and the mutable reference pointing into it).
 114 This example crucially relies on the redundancy check during retagging, where the shared reference does *not* get reborrowed (which would invalidate the mutable reference).
 115 If we wanted to add a barrier for that shared reference, we could not push it in top of the stack; we would have to add it somewhere in the middle next to the `Shr` item matching this reference.
 116 For now, I am trying to avoid adding items to the middle of the stack.
 117
 118 Another problem with shared `UnsafeCell` and barriers is summarized in [this issue](https://github.com/rust-lang/rust/issues/55005): in `Arc`, it can actually be the case that the memory referenced by a shared reference (but inside an `UnsafeCell`) gets deallocated while the function (that got this shared reference as argument) is still running.
 119 This violated LLVM's expectations for `dereferencable` pointers, and it would also violate the rule that memory with active barriers cannot be deallocated.
 120 We will have to either declare the current implementation of `Arc` incorrect or change the attributes that we use with LLVM.
 121 The model currently takes the position that `Arc` is correct, deallocating data behind a shared `UnsafeCell` is allowed, and the attribute is emitted incorrectly.
 122
 123 ## Two-phase Borrows
 124
 125 During the RustFest Rome, I was reminded that Stacked Borrows does not currently support [two-phase borrows](http://smallcultfollowing.com/babysteps/blog/2017/03/01/nested-method-calls-via-two-phase-borrowing/).
 126 This means that the following code (which is safe code in the 2018 edition) would get rejected by Miri:
 127 {% highlight rust %}
 128 fn two_phase() {
 129     let mut v = vec![];
 130     v.push(v.len());
 131 }
 132 {% endhighlight %}
 133
 134 To fix that, I just had to make a very tiny change.
 135 Retagging now has a special mode for two-phase borrows (it would be used in the above example when retagging the temporary containing the first argument of `push`), and in that mode, after completing all the usual steps, we create a shared reborrow of the newly created mutable borrow, with all the usual effects (freezing or pushing a `Shr` onto the stack.
 136 Thanks to the rule that reading through a mutable reference does not unfreeze or pop a `Shr` off the stack, this means that the original `v` can be used for reading until the time that the newly created (two-phase) borrow is written to for the first time.
 137 Writing will unfreeze and pop the `Shr` off the stack, disallowing any further reads through other references.
 138 This corresponds to the "activation" of a two-phase borrow.
 139
 140 Unfortunately, this model is not quite enough to handle all the code that rustc currently accepts.
 141 See [this issue](https://github.com/rust-lang/rust/issues/56254) for further discussion on this subject.
 142
 143 ## Stacked Borrows Specification
 144
 145 Between the various changes described here, there is now a noticeable discrepancy between the only self-contained description of Stacked Borrows in my previous blog post(s) and what is actually implemented.
 146 I will try to find a good spot to put a "living description" of whatever version of Stacked Borrows is currently implemented in Miri, so that there is more than just the code to look at.
 147 I'll let you know when I found one!
 148
 149 ## Making Miri Easier to Use
 150
 151 Finally, I decided to spend some time making Miri easier to install and use and fixing the problems with running test suites.
 152 Now all you have to do is run
 153
 154 ```
 155 cargo +nightly install --force --git https://github.com/solson/miri miri
 156 ```
 157
 158 and then go to your project directory and run `cargo +nightly miri test` (you may have to `cargo clean` first to make sure all your dependencies are built the right way for Miri).
 159 On first launch, Miri will (with your consent) install xargo and prepare a libstd suited for executing Rust programs in the interpreter, and then it will run your test suite.
 160 @oli-obk is currently working on making this even easier by making Miri a component that you can install via `rustup`.
 161 Give it a try and let us know what you think!