provenance-matters: explain what went wrong
[web.git] / ralf / _posts / 2019-04-30-stacked-borrows-2.md
1 ---
2 title: "Stacked Borrows 2"
3 categories: rust research
4 forum: https://internals.rust-lang.org/t/stacked-borrows-2/9951
5 ---
6
7 Recently, I have [significantly updated](https://github.com/rust-lang/miri/pull/695) Stacked Borrows in order to fix some issues with the handling of shared references that were uncovered in the previous version.
8 In this post, I will describe what the new version looks like and how it differs from [Stacked Borrows 1]({% post_url 2018-11-16-stacked-borrows-implementation %}).
9 I assume some familiarity with the prior version and will not explain everything from scratch.
10
11 <!-- MORE -->
12
13 ## Stacked Borrows: Table of Contents
14
15 Before we start, let me give a brief overview over the posts on Stacked Borrows that I have written so far.
16 I didn't plan this out in advance, so things are a bit more messy than I would like.
17
18 * [Stacked Borrows: An Aliasing Model For Rust]({% post_url 2018-08-07-stacked-borrows %}) is the first post of the series and describes my initial ideas of what Stacked Borrows would look like before I started implementing them. It might be interesting for some of the context it gives, but is largely superseded by the next post.
19 * [Stacked Borrows Implemented]({% post_url 2018-11-16-stacked-borrows-implementation %}) describes Stacked Borrows 1 and my experience implementing it. It is self-contained; I was not happy with some of my explanations in the original post so I decided to give it another shot. **This is the post to read if you are catching up.**
20 * [Barriers and Two-phase Borrows in Stacked Borrows]({% post_url 2018-12-26-stacked-borrows-barriers %}) describes how I extended Stacked Borrows 1 with partial support for two-phase borrows and explains the idea of "barriers". You do not have to have read that post to understand Stacked Borrows 2, except for the parts that specifically refer to barriers and two-phase borrows.
21
22 ## The problem
23
24 The problem I wanted to solve with Stacked Borrows 2 was that the first version of Stacked Borrows only performed very little tracking of shared references.
25 My thinking was, if the location is read-only anyway, then it is not harmful to grant anyone read access.
26 However, [as @arielby noted](https://github.com/rust-lang/unsafe-code-guidelines/issues/87), this leads to loss of optimization potential in cases where a function receives a mutable reference (which is supposed to have no aliases) and then creates a shared reference from it:
27 {% highlight rust %}
28 fn main() {
29     let x = &mut 0u32;
30     let p = x as *mut u32;
31     foo(x, p);
32 }
33
34 fn foo(a: &mut u32, y: *mut u32) -> u32 {
35     *a = 1;
36     let _b = &*a; // This freezes `*a`. Frozen locations can be read by any raw pointer.
37     let _val = unsafe { *y; }; // Hence, this legal in Stacked Borrows.
38     *a = 2; // But we might want to drop the earlier `*a = 1` because it gets overwritten!
39     _val
40 }
41 {% endhighlight %}
42 Stacked Borrows 1 allowed any raw pointer to read a frozen location.
43 Basically, once a location is frozen we do not keep track of which pointer is allowed to read; we just allow all pointers to read.
44 However, that means that `&*a` above (reborrowing a mutable reference as a shared reference) has the unintended side-effect of permitting raw pointers to read `*a`!
45 This violates the idea that `a` is a unique pointer: we'd like to remove the first write (`*a = 1`) because it gets overwritten later and there is no read *through `a`* in the mean time.
46 The issue is, there *is* an aliasing read through `y`, so removing the seemingly redundant write would change the return value of `foo` from `1` to `0`.
47 Hence calling `foo` like we do here with `a` and `y` pointing to the same thing must be undefined behavior---and yet, Stacked Borrows 1 considered the example above to be legal.
48
49 ## The solution
50
51 To fix this, I had to replace the mechanism of "freezing" by something else.
52 Remember that in Stacked Borrows 1, when a shared reference was created, we stored the timestamp at which that happened and also recorded in memory that the location this reference points to is frozen since now.
53 Whenever a shared reference gets used, we check that the location is frozen *at least* since our reference got created.
54 This is in contrast to mutable references, where we require the exact unique ID of that reference to be present in the borrow stack.
55
56 To rule out cases like the example above, instead of freezing a location and allowing *all* shared reference created henceforth to access this location, we keep track precisely of *which* shared references are allowed access.
57 The per-location borrow stack now consists of items that grant a particular *permission* to a pointer identified by a particular *tag*:
58 {% highlight rust %}
59 pub struct Item {
60     /// The pointers the permission is granted to.
61     tag: Tag,
62     /// The permission this item grants.
63     perm: Permission,
64 }
65
66 pub enum Permission {
67     /// Grants unique mutable access.
68     Unique,
69     /// Grants shared mutable access.
70     SharedReadWrite,
71     /// Greants shared read-only access.
72     SharedReadOnly,
73 }
74 {% endhighlight %}
75 There is no longer a separate "frozen" state; keeping shared references read-only is now handled by the borrow stack itself:
76 {% highlight rust %}
77 pub struct Stack {
78     borrows: Vec<Item>
79 }
80 {% endhighlight %}
81 The *tag* is also simpler than it was before: there are no longer separate tags for mutable and shared references.
82 {% highlight rust %}
83 pub type PtrId = u64;
84 pub enum Tag {
85     Tagged(PtrId),
86     Untagged,
87 }
88 {% endhighlight %}
89 Just like before, a new `Tag` gets picked on every retagging; in particular whenever a reference gets created with `&mut <expr>`/`& <expr>` and when a reference gets cast to a raw pointer.
90 Other than that (like on pointer arithmetic), the tag just gets propagated to keep track of where this pointer comes from.
91 However, unlike before, the only difference between mutable and shared references is the permissions that are associated with that tag.
92
93 ### Memory accesses
94
95 But before we go into creation of new references, let us look at how permissions in the borrow stack affect what happens at a memory access is legal.
96 So assume that some pointer tagged `tag` is used to either read from or write to memory.
97 For each affected location, we go through two steps: first we try to find the *granting item*, then we remove *incompatible items*.
98
99 **Finding the granting item.**
100 To find the granting item, we traverse the borrow stack top-to-bottom and search for an item that has the same tag.
101 If this is a write access, we go on looking until we find an item with the right tag whose permission is `SharedReadWrite` or `Unique`---we do not consider items with `SharedReadOnly` permission to grant a write access.
102 This is the item that grants pointers tagged `tag` the permission to perform the given access, hence the name (the same concept used to be called "matching item" in Stacked Borrows 1).
103 Once we found the granting item, we remember its position in the stack; that will be important for the second step.
104 If no granting item can be found, the access causes undefined behavior.
105
106 For example, if the stack is
107 ```
108 [ Item { tag: Tagged(0), perm: Unique },
109   Item { tag: Tagged(1), perm: SharedReadOnly} ]
110 ```
111 then a read access with tag `Tagged(1)` is granted by the item at index 1; a read/write access with tag `Tagged(0)` is granted by the item at index 0, but a write access with tag `Tagged(1)` is not granted by any item (and thus not allowed).
112 Just to keep things shorter and easier to read, in the following I will use a short-hand syntax for writing down items, so the above stack would look as follows:
113 ```
114 [ (0: Unique), (1: SharedReadOnly) ]
115 ```
116
117 To consider a second example, if the stack is
118 ```
119 [ (0: Unique), (Untagged: SharedReadWrite), (Untagged: SharedReadOnly) ]
120 ```
121 then a read access with an `Untagged` pointer is granted by the item at index 2, but a write access with an `Untagged` pointer is only granted by the item at index 1.
122
123 **Removing incompatible items.**
124 In the second step, we traverse all the items *above* the granting item in the stack, and see if they are compatible with this access.
125 This realizes the idea (already present in the original Stacked Borrows) that using one pointer disallows future uses of another pointer.
126 For example, if the current stack is
127 ```
128 [ (0: Unique), (1: Unique) ]
129 ```
130 then doing any kind of access with a `Tagged(0)` pointer should remove the `1: Unique` item from the stack.
131 This matches the part of Stacked Borrows 1 where items got popped off the stack until the granting item is at the top.
132 We say that the granting `Unique` permission is *incompatible* with the `Unique` permission of the item higher up the stack, and hence the latter must be removed.
133
134 However, in the new model, we don't always remove *all* items that are above the granting item:
135 ```
136 [ (0: Unique), (1: SharedReadOnly), (2: SharedReadOnly) ]
137 ```
138 In a situation like this, there are two pointers that may be used for reading, `Tagged(1)` and `Tagged(2)`.
139 Using either of them should not have an impact on the other one, and the fact that their items are in a particular order on the stack has no impact.
140 In other words, a granting `SharedReadOnly` permission is *compatible* with other `SharedReadOnly` permissions, and hence when using a `SharedReadOnly` permission to grant an access, other `SharedReadOnly` permissions above it are maintained.
141
142 Sometimes, being compatible depends on the kind of access that was performed:
143 in our last example stack, if we *write* with a `Tagged(0)` pointer, that should remove the `SharedReadOnly` tags because writing to a unique pointer should make sure that that pointer is at the top of the stack.
144 In other words, on a write, a `Unique` permission is incompatible with everything.
145 However, if we just *read* with a `Tagged(0)` pointer, that's fine!
146 This is to allow [safe code like this](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d9aa504b1be72a0f55fb5a744cba69ff) that interleaves reads from aliasing mutable and shared references.
147 To enable this, on a read, a `Unique` permission is only incompatible with other `Unique` permissions.
148
149 The following table fully documents which permissions are compatible with which other permissions on a read or write access, respectively:
150
151 |↓ **Granting item** \ **Compatible with** → | `Unique`  | `SharedReadWrite`   | `SharedReadOnly`  |
152 |---:|---|---|---|
153 |`Unique`                                    | no | only reads | only reads  |
154 |`SharedReadWrite`                           | no | yes  | only reads |
155 |`SharedReadOnly`                            | no | no  | only reads |
156
157 So, for example, if the granting item has `SharedReadWrite` permissions, then all `Unique` above it in the stack will be removed, and moreover on a write, all `SharedReadOnly` above it will be removed.
158 This makes sure that the pointers for which those `SharedReadOnly` permission grants read access cannot be used any more: those pointers assumed the location was read-only, so we must make sure that after a write, they become invalid.
159
160 The name "stack" is a bit of a misnomer at this point, because we do *not* follow a stack discipline when removing items: just because some item got removed due to incompatibility, does not mean all items above it will also get removed.
161 I will discuss [later][no-stack] why a strict stack discipline does not work.
162 But I felt it would be even more confusing to rename the entire thing at this point, and the order of elements in the "stack" still *does* matter, so I kept the name.
163
164 In Stacked Borrows 2, there is no more action occurring when a pointer gets dereferenced: the tags only matter for the actual access.
165 This simplification is possible because the rules for accesses are now more complicated than before, so there is no need for extra checks on the dereference operation.
166 (In particular, previously the dereference checks relied on knowing the Rust type at which the access happens for proper handling of interior mutability; but now all that information is encoded using `SharedReadWrite`/`SharedReadOnly` tags as we will see. Not relying on types any more here also [fixed an annoying issue around `UnsafeCell`](https://github.com/rust-lang/miri/issues/615).)
167
168 ### Retagging: when permissions get added
169
170 The framework of permissions in a stack with a notion of (in)compatibility that we have seen so far allows us to express some ideas like:
171
172 * "A `Unique` pointer will get invalid when any of its parent pointers get used."<br> That is realized by having "no" in the entire first column of our table: every access removes all `Unique` permissions above the granting item.
173 * "A `SharedReadOnly` pointer will get invalid when the location gets written to."<br> This gets realized by having "only reads" in the entire last column of the table and not granting write accesses with a `SharedReadOnly` permission. In addition to that, however, we *also* need to ensure that in the stack we never have a `Unique` or `SharedReadWrite` *on top* of a `SharedReadOnly`! In a nonsense stack like `[ (0: SharedReadOnly), (1: SharedReadWrite) ]` we could write with a `Tagged(1)` pointer without invalidating the `Tagged(0)` pointers.
174
175 Now the question is, how to we *use* this "language"?
176 We have to define which items and permissions get added to the borrow stack.
177 Just like before, this happens during retagging.
178 Before we discuss retagging in general, let us look at our motivating example and see how retagging works there in Stacked Borrows 2, and how this program is defined to cause UB:
179 {% highlight rust %}
180 fn main() {
181     let x = &mut 0u32;
182     Retag(x); // Tagged(0)
183     // Stack: [ (0: Unique) ]
184
185     let p = x as *mut u32;
186     Retag([raw] p); // Untagged
187     // Stack: [ (0: Unique), (Untagged: SharedReadWrite) ]
188
189     foo(x, p);
190 }
191
192 fn foo(a: &mut u32, y: *mut u32) -> u32 {
193     Retag(a); // Tagged(1)
194     // Stack: [ (0: Unique), (1: Unique) ]
195
196     *a = 1;
197
198     let _b = &*a;
199     Retag(_b); // Tagged(2)
200     // Stack: [ (0: Unique), (1: Unique), (2: SharedReadOnly) ]
201
202     // UB: y is Untagged, and there is no granting item in the stack!
203     let _val = unsafe { *y };
204
205     *a = 2;
206
207     _val
208 }
209 {% endhighlight %}
210 Initially, `x` with tag `Tagged(0)` is the only reference, and the stack says that this is the only pointer with any kind of permission.
211 Next, we cast `x` to a raw pointer.
212 The raw retagging of `p` turns `p` into an `Untagged` pointer, and adds a new item granting `Untagged` pointers `SharedReadWrite` permission.
213 (Really, in the MIR it will say `&mut *x as *mut u32`, so there will be an additional `Unique` permission for the temporary mutable reference, but that makes no difference and I hope [we will change that eventually](https://github.com/rust-lang/rfcs/pull/2582).)
214
215 Then `foo` gets called, which starts with the usual retagging of all reference arguments.
216 `a` is originally `Tagged(0)`, and retagging a mutable reference acts like an access (just like in Stacked Borrows 1), so the first thing that happens is that all items above the granting item that are incompatible with a write access for a `Unique` permission get removed from the stack.
217 In our case, this means that the `Untagged: SharedReadWrite` gets removed.
218 Then, `a` gets the new tag `Tagged(1)` and `1: Unique` gets pushed on top of the stack.
219 Nothing interesting happens when writing to `a`.
220 When `_b` gets created, it gets assigned the new tag `Tagged(2)`, and a new item `2: SharedReadOnly` is pushed to the stack.
221 As we can see, shared and mutable references no longer differ in the tag they carry; the only difference is what kind of permission they get granted.
222 (I think this is a nice improvement from Stacked Borrows 1, where shared references had a different kind of tag. In particular, transmutes between mutable references and shared pointers no longer need any kind of special treatment.)
223 Finally, we come to the interesting point: the program reads from `y`.
224 That pointer is `Untagged`, and there is no item granting any access to such pointers, and thus the access is UB!
225 This is in contrast to Stacked Borrows 1, where instead of `2: SharedReadOnly` we set a special "frozen" marker on this location that would, as a side-effect, also grant untagged pointers like `y` read-only access.
226
227 In general, during retagging, we start with some original tag used by our "parent" pointer, and we have a fresh tag `N` that will be used for the new pointer.
228 We have to decide which permission to grant so this tag, and where in the "stack" to insert it.
229 (We will not always insert new items at the top---again, as we will see following a strict stack discipline does not work.)
230 All of this happens for every location that the reference covers (as determined by its type).
231
232 **Retagging a mutable reference.**
233 The simplest case of retagging is handling mutable references:
234 just like in Stacked Borrows 1, this starts by performing the actions of a write access with the parent tag.
235 `Unique` permissions are incompatible with anything on a write, so all items above the granting item get removed.
236 Then we add `N: Unique` on top of the stack to grant the new tag unique access to this location.
237
238 This encodes the idea that mutable references must be used in a well-nested way---if you just consider mutable references, Stacked Borrows 2 still follows a stack discipline.
239
240 **Retagging a shared reference.**
241 When retagging a shared reference, we have to be mindful of `UnsafeCell`.
242
243 Outside of `UnsafeCell`, we start by performing the actions of a read access with the parent tag.
244 Then we push `N: SharedReadOnly` on top of the borrow stack.
245 This way, we grant the new pointer read-only access but make sure that it gets invalidated on the next write through any aliasing pointer (because all write-granting items are below us, and thus we test for compatibility when they get used).
246 There might be items left between the granting item and the one we just added, but that's okay: if any of them gets used for reading, that will be compatible with the `SharedReadOnly` according to our table above; and if any of them gets used for writing then it is important that our `SharedReadOnly` gets removed.
247
248 When we are inside an `UnsafeCell`, we will *not* perform the actions of a memory access!
249 Interior mutability allows all sorts of crazy aliasing, and in particular, one can call a function with signature
250 {% highlight rust %}
251 fn aliasing(refcell: &RefCell<i32>, inner: &mut i32)
252 {% endhighlight %}
253 such that `inner` points *into* `refcell`, i.e., the two pointers overlap!
254 Retagging `refcell` must not remove the `Unique` item associated with `inner`.
255
256 So, when retagging inside an `UnsafeCell`, we *find* the write-granting item for the parent's tag, and then we add `N: SharedReadWrite` just above it.
257 This grants write access, as is clearly needed for interior mutability.
258 We cannot add the new item at the top of the stack because that would add it *on top of* the item granting `inner`.
259 Any write to `inner` would remove our item from the stack!
260 Instead, we make our item sit just on top of its parent, reflecting the way one pointer got derived from the other.
261
262 **Retagging a raw pointer.**
263 Retagging for raw pointers happens only immediately after a reference-to-raw-pointer cast.
264 Unlike in Stacked Borrows 1, retagging depends on whether this is a `*const T` or `*mut T` pointer---this is a departure from the principle that these two types are basically the same (except for variance).
265 I have recently learned that the borrow checker actually handles `*mut` and `*const*` casts differently; also see [this long comment](https://github.com/rust-lang/rust/issues/56604#issuecomment-477954315).
266 Given that the idea of Stacked Borrows is to start with what the borrow checker does and extrapolate to a dynamic model that also encompasses raw pointers, I felt that it makes sense for now to mirror this behavior in Stacked Borrows.
267 This is certainly not a final decision though, and I feel we should eventually have a discussion whether we should make the borrow checker and Stacked Borrows both treat `*const T` and `*mut T` the same.
268
269 When casting to a `*mut T`, we basically behave like in the above case for inside an `UnsafeCell` behind a shared reference: we find the write-granting item for our parent's tag, and we add `Untagged: SharedReadWrite` just on top of it.
270 The way compatibility is defined for `SharedReadWrite`, there can be many such items next to each other on the stack, and using any one of them will not affect the others.
271 However, writing with a `Unique` permission further up the stack *will* invalidate all of them, reflecting the idea that when writing to a mutable reference, all raw pointers previously created from this reference become invalid.
272
273 When casting to a `*const T`, we behave just like retagging for a shared reference `&T` (including being mindful of `UnsafeCell`).
274 There isn't really anything that a `*const T` can do that a shared reference cannot (both in terms of aliasing and mutation), so modeling them the same way makes sense.
275
276 ### Two-phase borrows
277
278 Stacked Borrows 1 [had some support for two-phase borrows]({% post_url 2018-12-26-stacked-borrows-barriers %}), but some advanced forms of two-phase borrows that used to be allowed by the borrow checker [could not be handled](https://github.com/rust-lang/rust/issues/56254).
279 With the additional flexibility of Stacked Borrows 2 and its departure from a strict stack discipline, it is possible to accept at least the known examples of this pattern that were previously rejected:
280 {% highlight rust %}
281 fn two_phase_overlapping1() {
282     let mut x = vec![];
283     let p = &x;
284     x.push(p.len());
285 }
286 {% endhighlight %}
287 Previously, when the implicit reborrow of `x` in `x.push` got executed, that would remove the item for `p` from the stack.
288 This happens as part of the implicit write access that occurs when a mutable reference gets retagged.
289 With Stacked Borrows 2, we can do something else:
290 when retagging a two-phase mutable borrow, we do *not* perform the actions of a write access.
291 Instead, we just find the write-granting item for our parent's tag, and then add `N: Unique` just above it.
292 This has the consequence that on the first write access to this new pointer, everything on top of it will be removed, but until then the existing item for `p` remains on the stack and can be used just as before.
293
294 Just like with Stacked Borrows 1, we then proceed by doing a *shared* reborrow of the parent's tag from `N`.
295 This way, the parent pointer can be used in the ways a shared reference can (including writes, if there is interior mutability) without invalidating `N`.
296 This is somewhat strange because we then have "parent tag - new tag - parent tag" on the stack in that order, so we no longer properly reflect the way pointers got derived from each other.
297 More analysis will be needed to figure out the consequences of this.
298
299 We should also try to fully understand the effect this "weak" form of a mutable reborrow (without a virtual write access) has on the optimizations that can be performed.
300 Most of the cases of Stacked Borrows violations I found in the standard library are caused by the fact that even just *creating* a mutable reference asserts that it is unique and invalidates aliasing pointers, so if we could weaken that we would remove one of the most common causes of UB caused by Stacked Borrows.
301 On the other hand, this means that the compiler will have a harder time reordering uses of mutable references with function calls, because there are fewer cases where a mutable reference is actually assumed to be unique.
302
303 ### Barriers are dead, long live protectors
304
305 With the departure from a strict stack discipline, I also had to re-think the concept of [barriers]({% post_url 2018-12-26-stacked-borrows-barriers %}).
306 The name was anyway terrible, so I replaced barriers by *protectors*: an `Item` actually consists not only of a `Tag` and a `Permission`, but also optionally of a "protector" represented as a `CallId` referencing some function call (i.e., some stack frame).
307 As long as that function call is running, the item with the protector may not be removed from the stack (or else we have UB).
308 This has pretty much the same effects as barriers did in Stacked Borrows 1.
309
310 ## Why not a strict stack discipline?
311 [no-stack]: #why-not-a-strict-stack-discipline
312
313 The biggest surprise for me in designing Stacked Borrows 2 was that I was not able to enforce a strict stack discipline any more.
314 For retagging, that is only partially surprising; really in Stacked Borrows 1 we already added barriers below the "frozen" marker sitting next to a stack, and the `aliasing` example with the `RefCell` mentioned above only worked due to a hack that relied on reusing existing items in the middle of the stack instead of pushing a new one.
315 However, I had initially hoped that the rules for memory accesses would be slightly different:
316 my plan was that after finding the granting item, we would seek upwards through the stack and find the first incompatible item, and then remove everything starting there.
317 That would be a stack discipline; we would basically pop items until all items above the granting item are compatible.
318
319 Unfortunately, that would reject many reasonable programs, such as:
320 {% highlight rust %}
321 fn test(x: &mut [i32]) -> i32 { unsafe {
322   let raw = x.as_mut_ptr(); // implicitly: as_mut_ptr(&mut *x)
323   let _val = x[1];
324   return *raw;
325 } }
326 {% endhighlight %}
327 The issue with this example is that when calling `as_mut_ptr`, we reborrow `x`.
328 So after the first line the stack would look something like (using `x` as notation for `x`'s tag)
329 ```
330 [ ..., (x: Unique), (_: Unique), (Untagged: SharedReadWrite) ]
331 ```
332 In other words, there would be some `Unique` item *between* the items for `x` and `raw`.
333 When reading from `x` in the second line, we determine that this `Unique` tag is not compatible.
334 This is important; we have to ensure that any access from a parent pointer invalidates `Unique` pointers---that's what makes them unique!
335 However, if we follow a stack discipline, that means we have to pop the `Untagged: SharedReadWrite` *and* the `_: Unique` off the stack, making the third line UB because the raw pointer got invalidated.
336
337 `test` seems like a perfectly reasonable function, and in fact this pattern is used in the standard library.
338 So in order to allow such code, accesses in Stacked Borrows 2 do *not* follow a stack discipline:
339 we remove all incompatible items above the granting item and ignore any interleaved compatible items.
340 As a consequence, line 2 in the above program removes `_: Unique` but keeps `Untagged: SharedReadWrite`, so line 3 is okay.
341
342 However, this means we also accept the following, even if we eventually do fully precise tracking of raw pointers:
343 {% highlight rust %}
344 fn main() { unsafe {
345   let x = &mut 0;
346   let raw1 = x as *mut _;
347   // Stack: [ (x: Unique), (raw1: SharedReadWrite) ]
348
349   let tmp = &mut *raw1;
350   let raw2 = tmp as *mut _;
351   // Stack: [ (x: Unique), (raw1: SharedReadWrite), (tmp: Unique), (raw2: SharedReadWrite) ]
352
353   *raw1 = 1; // This will invalidate tmp, but not raw2.
354   // Stack: [ (x: Unique), (raw1: SharedReadWrite), (raw2: SharedReadWrite) ]
355
356   let _val = *raw2;
357 } }
358 {% endhighlight %}
359 Naively I would assume that if we tell LLVM that `tmp` is a unique pointer, it will conclude that `raw2` cannot alias with `raw1` as that was not derived from `tmp`, and hence LLVM might conclude that `_val` must be 0.
360 This means the program above would have to have UB.
361 However, in the current framework I do not see a way to make it UB without also making the reasonable example from the beginning of this section UB.
362 So maybe we can find a way to express to LLVM precisely what we mean, or maybe we can only exploit some of these properties in home-grown optimizations, or maybe we find a way to have UB in the second example but not in the first.
363 (Like, maybe we do the stack-like behavior on writes but keep the more lenient current behavior on reads? That seems annoying to implement though. Maybe a stack is just the wrong data structure, and we should use something more tree-like.)
364
365 ## Conclusion
366
367 Stacked Borrows 2 shares with Stacked Borrows 1 just the general structure: pointers are tagged, and there is a per-location stack indicating which tags are allowed to perform which kinds of operations on this location.
368 In the new version, shared references are tagged the same way as mutable references (just with an ID to distinguish multiple references pointing to the same location); the stack keeps track of which IDs are read-only (shared) pointers and which are unique (mutable) pointers.
369 The only operations affected by Stacked Borrows 2 are memory accesses and the `Retag` instructions explicitly represented in the MIR; there is no longer any action on a pointer dereference.
370 This balances the extra complexity of the new access rules (the new implementation is actually a dozen lines shorter than the old, despite long comments).
371 The "stack" is unfortunately not used in a completely stack-like fashion though.
372
373 I leave it as an exercise to the reader to convince yourself that the [key properties of Stacked Borrows 1]({% post_url 2018-11-16-stacked-borrows-implementation %}#5-key-properties) still hold, and that uniqueness of mutable references is maintained even if we do a shared reborrow, as long as we keep that shared reference to ourselves.
374
375 The new model gives some wiggle-room in both the notion of which permissions are compatible with others and where exactly which permissions are added in the "stack" in a reborrow.
376 We could use that wiggle-room to experiment with a bunch of closely related models to see how they affect which code gets accepted and analyze their impact on optimizations.
377
378 I am quite excited by this new model!
379 It puts us into a good position to do more precise tracking for raw pointers, similar to what already happens for shared references (and something I was worried about in the original model).
380 That will be needed for compatibility with LLVM.
381 However, [there are still some known issues](https://github.com/rust-lang/unsafe-code-guidelines/issues?q=is%3Aissue+is%3Aopen+label%3Atopic-stacked-borrows), and also the fact that we do not actually use the "stack" as a stack indicates that maybe we should use a different structure there (potentially something more like a tree).
382 This is definitely not the final word, but I think it is a step in the right direction, and I am curious to see how it works out.
383 As usual, if you have any questions or comments, please join the [discussion in the forums](https://internals.rust-lang.org/t/stacked-borrows-2/9951)!