0f36e05d5f9fe6a537ebebac4078204236fc1fd9
[web.git] / personal / _posts / 2018-08-07-stacked-borrows.md
1 ---
2 title: "Stacked Borrows: An Aliasing Model For Rust"
3 categories: internship rust
4 forum: https://internals.rust-lang.org/t/stacked-borrows-an-aliasing-model-for-rust/8153
5 ---
6
7 In this post, I am proposing "Stacked Borrows": A set of rules defining which kinds of aliasing are allowed in Rust.
8 This is intended to answer the question which pointer may be used when to perform which kinds of memory accesses.
9
10 This is a long-standing open question of many unsafe code authors, and also by compiler authors who want to add more optimizations.
11 The model I am proposing here is by far not the first attempt at giving a definition: The model is heavily based on ideas by [@arielb1](https://github.com/nikomatsakis/rust-memory-model/issues/26) and [@ubsan](https://github.com/nikomatsakis/rust-memory-model/issues/28), and of course taking into account the lessons I [learned last year]({% post_url 2017-08-11-types-as-contracts-evaluation %}) when I took my first stab at defining such a model, dubbed ["Types as Contracts"]({% post_url 2017-07-17-types-as-contracts %}).
12
13 <!-- MORE -->
14
15 But before I delve into my latest proposal, I want to briefly discuss a key difference between my previous model and this one:
16 "Types as Contracts" was a fully "validity"-based model, while "Stacked Borrows" is (to some extent) "access"-based.
17
18 **Update:**
19 Since publishing this post, I have written [another]({% post_url 2018-11-16-stacked-borrows-implementation %}) blog post about a slightly adjusted version of Stacked Borrows (the first version that actually got implemented).
20 That other post is self-contained, so if you are just interested in the current state of Stacked Borrows, I suggest you go there.
21 **/Update**
22
23 ## 1 Validity-based vs. Access-based
24
25 An "access"-based model is one where certain properties -- in this case, mutable references being unique and shared references pointing to read-only memory -- are only enforced when the reference is actually used to *access* memory.
26 In contrast, a "validity"-based model requires these properties to always hold for all references that *could* be used.
27 In both cases, violating a property that the model requires to hold is undefined behavior..
28
29 Essentially, with a validity-based model like "Types as Contracts", the basic idea is that all data is always valid according to the type it is given.
30 Enforcing the restrictions of such a model (e.g., when checking whether a program has undefined behavior) amounts to eagerly checking all reachable data for validity.
31 An access-based model, on the other hand, only requires data to be valid when used.
32 Enforcing it amounts to lazily checking the bare minimum at each operation.
33
34 Validity-based models have several advantages: Eager checking means we can typically identify which code is actually responsible for producing the "bad" value.
35 "All data must always be valid" is also easier to explain than a long list of operations and the kind of restrictions they place upon the data.
36
37 However, in Rust, we cannot talk about references and whether the are valid at their given type without talking about lifetimes.
38 With "Types as Contracts", the exact place where a lifetime ended turned out to be really important.
39 Not only did this make the specification complex and hard to understand; the implementation in Miri also had to actively work against the compiler's general intention to forget about lifetimes as early as possible.
40 With non-lexical lifetimes, the "end" of a lifetime is not even so clearly defined any more.
41
42 ## 2 Stacking Borrows
43
44 For these reasons, my second proposal makes lifetimes in general and the result of lifetime inference in particular completely irrelevant for whether a program has undefined behavior (UB).
45 This is one of the core design goals.
46
47 If you need some more context on undefined behavior and how it relates to compiler optimizations, I suggest you read [my blog post on this topic]({% post_url 2017-07-14-undefined-behavior %}) first.
48 It's not a long post, and I cannot repeat everything again here. :)
49
50 The central idea of this model (and its precursors by @arielb1 and @ubsan) is that, for every location, we keep track of the references that are allowed to access this location.
51 (I will discuss later just how we keep track of this; for now, let's just assume it can be done.)
52 This forms a stack: When we have an `&mut i32`, we can *reborrow* it to obtain a new reference.
53 That new reference is now the one that must be used for this location, but the old reference it was created from cannot be forgotten: At some point, the reborrow will expire and the old reference will be "active" again.
54 We will have other items on that stack as well, so we will write `Uniq(x)` to indicate that `x` is the unique reference permitted to access this location.
55
56 Let us look at an example:
57 {% highlight rust %}
58 fn demo0(x: &mut i32) -> i32 {
59   // At the beginning of the function, `x` must be the "active" reference
60   // for the 4 locations it points to, meaning `Uniq(x)` is at the top of the stack.
61   // (It's 4 locations because `i32` has size 4.)
62   let y = &mut *x; // Now `Uniq(y)` is pushed onto the stack, as new active reference.
63   // The stack now contains: Uniq(y), Uniq(x), ...
64   *y = 5; // Okay because `y` is active.
65   *x = 3; // This "reactivates" `x` by popping the stack.
66   // The stack now contains: Uniq(x), ...
67   *y // This is UB! `Uniq(y)` is not on the stack of borrows, so `y` must not be used.
68 }
69 {% endhighlight %}
70 Of course, this example would not compile because the borrow checker would complain.
71 However, in my interpretation, the *reason* it complains is that if it accepted the program, we would have UB in safe code!
72
73 This is worth pondering a bit: The model defines program semantics without taking lifetimes into account, so we can run programs and ask whether they have UB without
74 ever doing lifetime inference or borrow checking (very much unlike "Types as Contracts").
75 One important property, then, is that *if* the program has UB and does not use any unsafe code, the borrow checker must detect this.
76 In some sense, my model defines a dynamic version of the borrow checker *that works without lifetimes*.
77 It turns out that even with non-lexical lifetimes, the borrow structure for a given location is still well-nested, which is why we can arrange borrows in a stack.
78
79 ### 2.1 Raw Pointers
80
81 Let us bypass the borrow checker by adding some unsafe code to our program:
82 {% highlight rust %}
83 fn demo1(x: &mut i32) -> i32 {
84   // At the beginning of the function, `x` must be the "active" reference.
85   let raw = x as *mut _; // Create raw pointer
86   // The stack now contains: Raw, Uniq(x), ...
87   let y = unsafe { &mut *raw }; // Now `y` is pushed onto the stack, as new active reference.
88   // The stack now contains: Uniq(y), Raw, Uniq(x), ...
89   *y = 5; // Okay because `y` is active.
90   *x = 3; // This "reactivates" `x` by popping the stack twice.
91   *y // This is UB! `Uniq(y)` is not on the stack of borrows, so `y` must not be used.
92 }
93 {% endhighlight %}
94
95 What happens here is that we are casting `x` to a raw pointer.
96 For raw pointers, we cannot really keep track of where and how they have been created -- raw pointers can be safely cast to and from integers, and data could flow arbitrarily.
97 So, when a `&mut` is cast to `*mut` like above, we instead push `Raw` onto the stack, indicating that *any* raw pointer may be used to access this location.
98 (The usual restrictions about address arithmetic across allocations still apply, I am just talking about the borrow checking here.)
99
100 In the next line, we use a raw pointer to create `y`.
101 That is okay because `Raw` is active.
102 As usual when a reference is created, we push it onto the stack.
103 This makes `y` the active reference, so we can use it in the next line.
104 And again, using `x` pops the stack until `x` is active -- in this case, this removes both the `Uniq(y)` and the `Raw`, making `y` unusable and causing UB in the last line.
105
106 Let us look at another example involving raw pointers:
107 {% highlight rust %}
108 fn demo2(x: &mut i32) -> i32 {
109   // At the beginning of the function, `x` must be the "active" reference.
110   let raw = x as *mut _; // Create raw pointer
111   // The stack now contains: Raw, Uniq(x), ...
112   let y = unsafe { &mut *raw }; // Now `y` is pushed onto the stack, as new active reference.
113   // The stack now contains: Uniq(y), Raw, Uniq(x), ...
114   *y = 5; // Okay because `y` is active.
115   unsafe { *raw = 5 }; // Using a raw pointer, so `Raw` gets reactivated by popping the stack!
116   // The stack now contains: Raw, Uniq(x), ...
117   *y // This is UB! `Uniq(y)` is not on the stack of borrows, so `y` must not be used.
118 }
119 {% endhighlight %}
120 Because raw pointers are tracked on the stack, they have to follow the well-nested structure.
121 `y` was "created from" `raw`, so using `raw` again invalidates `y`!
122 This is exactly in symmetry with the first example where `y` was "created from" `x`, so using `x` again invalidated `y`.
123
124 ### 2.2 Shared References
125
126 For shared references, of course, we do not have a single reference which is the only one with permission to access.
127 The key property we have to model is that shared references point to memory that does not change (assuming no interior mutability is involved).
128 The memory is, so to speak, *frozen*.
129
130 For this purpose, we tag shared references with some kind of "timestamp" indicating *when* it was created.
131 We also have an extra flag for each location storing *since when* the location is frozen.
132 Using a shared reference to access memory is okay if memory has been frozen continuously since the reference was created.
133
134 We can see this in action in the following example:
135 {% highlight rust %}
136 fn demo3(x: &mut i32) -> i32 {
137   // At the beginning of the function, `x` must be the "active" reference.
138   let raw = x as *mut _; // Create raw pointer
139   // The stack now contains: Raw, Uniq(x), ...
140   let y = unsafe { & *raw }; // Now memory gets frozen (recording the timestamp)
141   let _val = *y; // Okay because memory was frozen since `y` was created
142   *x = 3; // This "reactivates" `x` by unfreezing and popping the stack.
143   let z = &*x; // Now memory gets frozen *again*
144   *y // This is UB! Memory has been frozen strictly after `y` got created.
145 }
146 {% endhighlight %}
147
148 Shared references with interior mutability do not really have any restrictions in terms of what can happen to memory, so we treat them basically like raw pointers.
149
150 ### 2.3 Recap
151
152 For every location in memory, we keep track of a stack of borrows (`Uniq(_)` or `Raw`), and potentially "top off" this stack by freezing the location.
153 A frozen location is never written to, and no `Uniq` is pushed.
154
155 Whenever a mutable reference is created, a matching `Uniq` is pushed onto the stack for every location "covered by" the reference -- i.e., the locations that would be accessed when the reference is used (starting at where it points to, and going on for `size_of_val` many bytes).
156 Whenever a shared reference is created, if there is no interior mutability, we freeze the locations if they are not already frozen.
157 If there is interior mutability, we just push a `Raw`.
158 Whenever a raw pointer is created from a mutable reference, we push a `Raw`.
159 (Nothing happens when a raw pointer is created from a shared reference.)
160
161 A mutable reference `x` is "active" for a location if that location is not frozen and `Uniq(x)` is on top of the stack.
162 A shared reference without interior mutability is active if the location is frozen at least since the location was created.
163 A shared reference with interior mutability is active is `Raw` is on top of the stack.
164
165 Whenever a reference is used to do something (anything), we make sure that it is active again for all locations that it covers; this can involve unfreezing and popping the stack.
166 If it is not possible to reactivate the reference this way, we have UB.
167
168 **Update:** I previously talked about "activating" the reference instead of "reactivating it"; I decided to change terminology to make it clearer that this is an old reference being used again, so it must be on the stack already (but might not be at the top). **/Update**
169
170 ## 3 Tracking Borrows
171
172 So far, I have just been assuming that we can somehow keep a connection between a reference like `x` in the code above, and an item `Uniq(x)` on the stack.
173 I also said we are keeping track of when a shared reference was created.
174 To realize this, we need to somehow have information "tagged" to the reference.
175 In particular, notice that `x` and `y` in the first example have the same address.
176 If we compared them as raw pointers, they would turn out equal.
177 And yet, it makes a huge difference if we use `x` or `y`!
178
179 If you read my previous post on [why pointers are complicated]({% post_url 2018-07-24-pointers-and-bytes %}), this should not come as too much of a surprise.
180 There is more to a pointer, or a reference (I am using these terms mostly interchangeably), than the address in memory that it points to.
181
182 For the purpose of this model, we assume that a value of reference type consists of two parts: An address in memory, and a tag used to store the time when the reference was created.
183 "Time" here is a rather abstract notion, we really just need some counter that we bump up every time a new reference is created.
184 This gives us a unique ID for each mutable reference -- and, as we have seen, for shared references we actually exploit the fact that IDs are handed out in increasing order
185 (so that we can test if a reference was created before or after a location was frozen).
186 So, we can actually treat mutable and shard references uniformly in that both just record, in their tag, the time at which they were created.
187
188 Whenever I said above that we have `Uniq(x)` on the stack, what I really meant is that we have `Uniq(t_x)` on the stack, where `t_x` is some clock value, and that the "tag" of `x` is `t_x`.
189 For the sake of readability, I will continue to use the `Uniq(x)` notation below.
190
191 Since raw pointers are not tracked, we can erase the tag when casting a reference to a raw pointer.
192 This means our tag does not interfere with pointer-integer casts, which means there are a whole bunch of complicated questions we do not have to worry about. :)
193
194 Of course, these tags do not exist on real hardware.
195 But that is besides the point.
196 When *specifying* program behavior, we can work with an ["instrumented machine"]({% post_url 2017-06-06-MIR-semantics %}) that has extra state which is not present on the real machine, as long as we only use that extra state to define whether a program is UB or not:
197 On real hardware, we can ignore programs that are UB (they may just do whatever), so the extra state does not matter.
198
199 Tags are something I wanted to avoid in "Types as Contracts" -- that was one of the initial design constraints I had put upon myself, in the hope of avoiding the trouble coming with "complicated pointers".
200 However, I now came to the conclusion that tagging pointers is a price worth paying if it means we can make lifetimes irrelevant.
201
202 ## 4 Retagging and Barriers
203
204 I hope you now have a clear idea of the basic structure of the model I am proposing: The stack of borrows, the freeze flag, and references tagged with the time at which they got created.
205 The full model is not quite as simple, but it is not much more complicated either.
206 We need to add just two more concepts: Retagging and barriers.
207
208 ### 4.1 Retagging
209
210 Remember that every time we create a mutable borrow, we assign it the current
211 clock values as its tag.  Since the tag can never be changed, this means two
212 different variables can never have the same tag -- right?  Well, unfortunately,
213 things are not so simple: Using
214 e.g. [`transmute_copy`](https://doc.rust-lang.org/stable/std/mem/fn.transmute_copy.html)
215 or a `union`, one can make a copy of a reference in a way that Rust does not
216 even notice.
217
218 Still, we would like to make statements about code like this:
219 {% highlight rust %}
220 fn demo4(x: &mut i32, y: &mut i32) -> i32 {
221   *x = 42;
222   *y = 7;
223   *x // Will load 42! We can optimize away the load.
224 }
225 {% endhighlight %}
226 The trouble is, we cannot prevent the outside world from passing bogus `&mut` that have the same tag.
227 Does this mean we are back to square one in terms of making aliased mutable references UB?
228 Lucky enough, we are not! We have a lot of machinery at our disposal, we just have to tweak it a little.
229
230 What we will do is, every time a reference comes "into" our function (this can be a function argument, but also loading it from memory or getting it as the return value of some other function), we perform "retagging":
231 We change the tags of the mutable references to the current clock value, bumping up the clock after every tag we assign, and then we push those new tags on top of the borrow stack.
232 This way, we can know -- without making any assumptions about foreign code -- that all references have distinct IDs.
233 In particular, two different references can never be both "active" for the same location at the same time.
234
235 With this additional step, it is now easy to argue that `demo4` above is UB when `x` and `y` alias, no matter their initial tag:
236 After using `x`, we know it is active.
237 Next we use and reactivate `y`, which has to pop `Uniq(x)` as they have distinct tags.
238 Finally, we use `x` again even though it is no longer in the stack, triggering UB.
239 (A `Uniq` is only ever pushed when it is created, so it is never in the stack more than once.)
240
241 ### 4.2 Barriers
242
243 There is one more concept I would like to add: Barriers.
244 The model would make a lot of sense even without barriers -- but adding barriers rules out some more behavior that I do not think we want to allow.
245 It is also needed to explain why we can put the [`noalias` parameter attribute](https://llvm.org/docs/LangRef.html#parameter-attributes) on our functions when generating LLVM IR.
246
247 Consider the following code:
248 {% highlight rust %}
249 fn demo5(x: &mut i32, y: usize) {
250   *x = 42;
251   foo(y);
252 }
253
254 fn foo(y: usize) {
255   let y = unsafe { &mut *(y as *mut i32) };
256   *y = 7;
257 }
258 {% endhighlight %}
259 The question is: Can we reorder the `*x = 42;` down to the end of `demo5`?
260 Notice that we are *not* using `x` again, so we cannot assume that `x` is active at the end of `demo5`!
261 This is the usual trouble with access-based models.
262
263 However, someone might conceivably call `demo5` with `y` being `x as *mut _ as usize`, which means reordering could change program behavior.
264 To fix this, we have to make sure that if someone actually calls `demo5` this way, we have UB *even though* `x` is not used again.
265
266 To this end, I propose to turn the dial a little more towards a validity-based model by imposing some extra constraints.
267 We want to ensure that turning the integer `y` into a reference does not pop `x` from the stack and continue executing the program (we want UB instead).
268 This could happen if the stack contained, somewhere, a `Raw`.
269 Remember that we do not tag raw pointers, so when a raw pointer was involved in creating `x`, that `Raw` item will still be on the stack, enabling any raw pointer to be used to access this location.
270 This is sometimes crucial, but in this case, `demo5` should be able to prevent those old historic borrows involved in creating `x` from being reactivated.
271
272 The idea is to put a "barrier" into the stack of all function arguments when `demo5` gets called, and to make it UB to pop that barrier from the stack before `demo5` returns.
273 This way, all the borrows further down in the stack (below `Uniq(x)`) are temporarily disabled and cannot be reactivated while `demo5` runs.
274 This means that even if `y` happens to be the memory address `x` points to, it is UB to cast `y` to a reference because the `Raw` item cannot be reactivated.
275
276 Another way to think about barriers is as follows:
277 The model generally ignores lifetimes and does not know how long they last.
278 All we know is that when a reference is used, its lifetime must be ongoing, so we say that is when we reactivate the borrow.
279 On top of this, barriers encode the fact that, when a reference is passed as an argument to a function, then its lifetime (whatever it is) extends beyond the current function call.
280 In our example, this means that no borrow further up the stack (these are the borrows with even longer lifetimes) can be used while `demo5` is running.
281
282 A nice side-effect of barriers in combination with renumbering is that even if `demo4` from the previous subsection would not use its arguments at all, it would *still* be UB to call it with two aliasing references:
283 When renumbering `x`, we are pushing a barrier. Renumbering `y` would attempt to reactivate `Uniq(y)`, but that can only be behind the barrier, so it cannot be reactivated.
284
285 ## 5 The Model in Code
286
287 Now we have everything together.
288 Instead of giving another recap, I will try to give an alternative, more precise description of the model in the form of pseudo Rust code.
289 This is essentially a draft of the code that will hopefully be in Miri soon, to actually dynamically track the borrow stack and enforce the rules.
290 This is also how I go about developing such models -- I use some form of pseudo-Rust, which I find it easier to be precise in than pure English.
291 Some details have been omitted in the high-level description so far, they should all be in this code.
292
293 If you are only interested in the high-level picture, feel free to skip to the end.
294 The rest of this is more like a specification than an explanatory blog post.
295 The nice thing is that even with the spec, this post is still shorter than the one introducing "Types as Contracts". :)
296
297 ### 5.1 Per-Location Operations
298
299 Imagine we have a type `MemoryByte` storing the per-location information in memory.
300 This is where we put the borrow stack and the information about freezing:
301
302 {% highlight rust %}
303 /// Information about a potentially mutable borrow
304 enum Mut {
305   /// A unique, mutable reference
306   Uniq(Timestamp),
307   /// Any raw pointer, or a shared borrow with interior mutability
308   Raw,
309 }
310 /// Information about any kind of borrow
311 enum Borrow {
312   /// A mutable borrow, a raw pointer, or a shared borrow with interior mutability
313   Mut(Mut),
314   /// A shared borrow without interior mutability
315   Frz(Timestamp)
316 }
317 /// An item in the borrow stack
318 enum BorStackItem {
319   /// Defines which references are permitted to mutate *if* the location is not frozen
320   Mut(Mut),
321   /// A barrier, tracking the function it belongs to by its index on the call stack
322   FnBarrier(usize)
323 }
324
325 struct MemoryByte {
326   borrows: Vec<BorStackItem>, // used as a stack
327   frz_since: Option<Timestamp>,
328   /* More fields, to store the actual value and what else might be needed */
329 }
330 {% endhighlight %}
331
332 Next, we define some per-location operations that we will use later to define what happens when working with references.
333 Below, `assert!` is used for things that should always be true because of interpreter invariants (i.e., Miri will ICE if they fail to hold), and `bail!` is used to indicate that the program has UB.
334
335 {% highlight rust %}
336 impl MemoryByte {
337
338   /// Check if the given borrow may be used on this location.
339   fn check(&self, bor: Borrow) → bool {
340     match bor {
341       Frz(acc_t) =>
342         // Must be frozen at least as long as the `acc_t` says.
343         self.frz_since.map_or(false, |loc_t| loc_t <= acc_t),
344       Mut(acc_m) =>
345         // Raw pointers are fine with frozen locations. This is important because &Cell is raw!
346         if self.frozen_since.is_some() {
347           acc_m.is_raw()
348         } else {
349           self.borrows.last().map_or(false, |loc_itm| loc_itm == Mut(acc_m))
350         }
351     }
352   }
353
354   /// Reactivate the given existing borrow for this location, fail if that is not possible.
355   fn reactivate(&mut self, bor: Borrow) {
356     // Do NOT change anything if `bor` is already active -- in particular, if
357     // it is a `Mut(Raw)` and we are frozen.
358     if self.check(bor) { return; }
359     let acc_m = match bor {
360       Frz(acc_t) => bail!("Location should be frozen but it is not"),
361       Mut(acc_m) => acc_m,
362     };
363     // We definitely have to unfreeze this, even if we use the topmost item.
364     self.frozen_since = None;
365     // Pop until we see the one we are looking for.
366     while let Some(itm) = self.borrows.last() {
367       match itm {
368         FnBarrier(_) => {
369           bail!("Trying to reactivate a borrow that lives behind a barrier");
370         }
371         Mut(loc_m) => {
372           if loc_m == acc_m { return; }
373           self.borrows.pop();
374         }
375       }
376     }
377     bail!("Borrow-to-reactivate does not exist on the stack");
378   }
379
380   /// Initiate the given (new) borrow for the location.
381   /// This is "pushing to the stack", except that it also handles initiating a `Frz`.
382   fn initiate(&mut self, bor: Borrow) {
383     match bor {
384       Frz(t) => {
385         if self.frozen_since.is_none() {
386           self.frozen_since = Some(t);
387         }
388       }
389       Mut(m) => {
390         if m.is_uniq() && self.frozen_since.is_some() {
391           bail!("Must not initiate Uniq when frozen!");
392         }
393         self.borrows.push(Mut(m));
394       }
395     }
396   }
397
398   /// Reset the borrow tracking for this location.
399   fn reset(&mut self) {
400     if self.borrows.iter().any(|itm| if let FnBarrier(_) = item { true } else { false }) {
401       assert!("Cannot reset while there are barriers");
402     }
403     self.frozen_since = None;
404     self.borrows.clear();
405   }
406   
407 }
408 {% endhighlight %}
409
410 ### 5.2 MIR operations
411
412 Finally, we enhance some MIR operations with bookkeeping, following the model I described above.
413 This is where the code gets more "pseudo" and less Rust. ;)
414
415 For each of these operation, we iterate over all affected locations; let us call the loop variable `loc` of type `MemoryByte`.
416 We also have a variable `tag` with the tag of the pointer we are operating on (loading, or storing, or casting to a raw pointer, ...).
417
418 Moreover, we have a boolean variable `in_unsafe_cell` indicating whether, according to the type of the pointer, the location we are currently working on is covered by an [`UnsafeCell`](https://doc.rust-lang.org/stable/std/cell/struct.UnsafeCell.html).
419 (This realizes the conditions checking whether we have interior mutability or not.)
420 For example, in `&Cell<i32>`, all 4 locations are inside an `UnsafeCell`.
421 However, in `&(i32, Cell<i32>)`, only the last 4 of the 8 covered locations are inside an `UnsafeCell`.
422
423 Finally, given a reference type, a tag, and whether we are inside an `UnsafeCell`, we can compute the matching `Borrow`:
424 Mutable references use `Mut(Uniq(tag))`, shared references in an `UnsafeCell` use `Mut(Raw)` and other shared references use `Frz(tag)`.
425 We use `bor` to refer to the `Borrow` of the pointer we are working on.
426
427 Now we can look at what happens for each operation.
428
429 * Using a raw pointer directly is desugared to creating a shared reference (when reading) or a mutable reference (when writing), and using that. The appropriate steps below apply.
430 * Any time we use a (mutable or shared) reference to access memory, and any time we pass a reference to "the outside world" (passing it to a function, storing it in memory, returning it to our caller; also below structs or enums but not below unions or pointer indirectons), we reactivate.
431   - `loc.reactivate(borrow)`.
432 * Any time a *new* reference is created (any time we run an expression `&mut foo` or `&foo`), we (re)borrow.
433   - Bump up the clock, and remember the old time as `new_tag`.
434   - Compute `new_bor` from `new_tag` and the type of the reference being created.
435   - `if loc.check(new_bor) {`
436     * The new borrow is already active! This can happen because a mutable reference can be shared multiple times. We do not do anything else.
437       As a special exception, we do *not* reactivate `bor` even though it is "used", because that would unfreeze the location!
438
439     `} else {`
440     * We might be creating a reference to a local variable. In that case, `loc.reset()`. Otherwise, `reactivate(bor)`.
441     * `initiate(new_bor)`
442
443     `}`
444   - Use `new_tag` for the new reference.
445 * Any time a reference is passed to us from "the outside world" (as function argument, loaded from memory, or returned from a callee; also below structs or enums but not below unions or pointer indirectons), we retag.
446   - Bump up the clock, and remember the old time as `new_tag`.
447   - Compute `new_bor` from `new_tag` and the type of the reference being created.
448   - `reactivate(bor)`.
449   - If this is a function argument coming in: `loc.borrows.push(FnBarrier(stack_height))`.
450   - `initiate(new_bor)`. Note that this is a NOP if `new_bor` is already active -- in particular, if the location is frozen and this is a shared reference with interior mutability, we do *not* push anything on top of the barrier. This is important, because any reactivation that unfreezes this location must lead to UB while the barrier is still present.
451   - Change reference tag to `new_tag`.
452 * Any time a raw pointer is created from a reference, we might have to do a raw reborrow.
453   - `reactivate(bor)`.
454   - `initiate(Mut(Raw))`. This is a NOP when coming from a shared reference.
455 * Any time a function returns, we have to clean up the barriers.
456   - Iterate over all of memory and remove the matching `FnBarrier`. This is where the "stack" becomes a bit of a lie, because we also remove barriers from the middle of a stack.<br>
457     This could be optimized by adding an indirection, so we just have to record somewhere that this function call has ended.
458 * Any time memory is deallocated, this counts as mutation, so the usual rules for that apply. After that, the stacks of the deallocated bytes must not contain any barriers.
459
460
461 If you want to test your own understanding of "Stacked Borrows", I invite you to go back to [Section 2.2 of "Types as Contracts"]({% post_url 2017-07-17-types-as-contracts %}#22-examples) and look at the three examples here.
462 Ignore the `Validate` calls, that part is no longer relevant.
463 These are examples of optimizations we would like to be valid, and in fact all three of them are still valid with "Stacked Borrows".
464 Can you argue why that is the case?
465
466 ## Summary
467
468 I have described (yet) another Rust memory model that defines when a reference may be used to perform which memory operations.
469 The main design constraint of this model is that lifetimes should not matter for program execution.
470 To my own surprise, the model actually ended up being fairly simple, all things considered.
471
472 I think I covered most of the relevant features, though I will have to take a closer look at two-phase borrows and see if they need some further changes to the model.
473
474 Of course, now the big question is whether this model actually "works" -- does it permit all the code we want to permit (does it even permit all safe code), and does it rule out enough code such that we can get useful optimizations?
475 I hope to explore this question further in the following weeks by implementing a dynamic checker to test the model on real code.
476 It is just easier to answer these questions when you do not have to *manually* reevaluate all examples after every tiny change.
477 However, I can always use more examples, so if you think you found some interesting or surprising corner case, please let me know!
478
479 As always, if you have any questions or comments, feel free to [ask in the forums](https://internals.rust-lang.org/t/stacked-borrows-an-aliasing-model-for-rust/8153).