---
title: "Stacked Borrows: An Aliasing Model For Rust"
categories: internship rust
+forum: https://internals.rust-lang.org/t/stacked-borrows-an-aliasing-model-for-rust/8153
---
In this post, I am proposing "Stacked Borrows": A set of rules defining which kinds of aliasing are allowed in Rust.
<!-- MORE -->
But before I delve into my latest proposal, I want to briefly discuss a key difference between my previous model and this one:
-"Types as Contracts" was a fully "validity"-based model, while "Stacked Borrows" is (to some extend) "access"-based.
+"Types as Contracts" was a fully "validity"-based model, while "Stacked Borrows" is (to some extent) "access"-based.
+
+**Update:**
+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).
+That other post is self-contained, so if you are just interested in the current state of Stacked Borrows, I suggest you go there.
+Only go on reading here if you want some additional historic context.
+**/Update**
## 1 Validity-based vs. Access-based
However, in Rust, we cannot talk about references and whether the are valid at their given type without talking about lifetimes.
With "Types as Contracts", the exact place where a lifetime ended turned out to be really important.
-Not only did this make the specification complex and hard to understand; the implementation in [Miri]({% post_url 2017-06-06-MIR-semantics %}) also had to actively work against the compiler's general intention to forget about lifetimes as early as possible.
+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.
With non-lexical lifetimes, the "end" of a lifetime is not even so clearly defined any more.
## 2 Stacking Borrows
let y = &mut *x; // Now `Uniq(y)` is pushed onto the stack, as new active reference.
// The stack now contains: Uniq(y), Uniq(x), ...
*y = 5; // Okay because `y` is active.
- *x = 3; // This "activates" `x` by popping the stack.
+ *x = 3; // This "reactivates" `x` by popping the stack.
// The stack now contains: Uniq(x), ...
*y // This is UB! `Uniq(y)` is not on the stack of borrows, so `y` must not be used.
}
let y = unsafe { &mut *raw }; // Now `y` is pushed onto the stack, as new active reference.
// The stack now contains: Uniq(y), Raw, Uniq(x), ...
*y = 5; // Okay because `y` is active.
- *x = 3; // This "activates" `x` by popping the stack twice.
+ *x = 3; // This "reactivates" `x` by popping the stack twice.
*y // This is UB! `Uniq(y)` is not on the stack of borrows, so `y` must not be used.
}
{% endhighlight %}
let y = unsafe { &mut *raw }; // Now `y` is pushed onto the stack, as new active reference.
// The stack now contains: Uniq(y), Raw, Uniq(x), ...
*y = 5; // Okay because `y` is active.
- unsafe { *raw = 5 }; // Using a raw pointer, so `Raw` gets activated by popping the stack!
+ unsafe { *raw = 5 }; // Using a raw pointer, so `Raw` gets reactivated by popping the stack!
// The stack now contains: Raw, Uniq(x), ...
*y // This is UB! `Uniq(y)` is not on the stack of borrows, so `y` must not be used.
}
// The stack now contains: Raw, Uniq(x), ...
let y = unsafe { & *raw }; // Now memory gets frozen (recording the timestamp)
let _val = *y; // Okay because memory was frozen since `y` was created
- *x = 3; // This "activates" `x` by unfreezing and popping the stack.
- let z = unsafe { & *raw }; // Now memory gets frozen *again*
+ *x = 3; // This "reactivates" `x` by unfreezing and popping the stack.
+ let z = &*x; // Now memory gets frozen *again*
*y // This is UB! Memory has been frozen strictly after `y` got created.
}
{% endhighlight %}
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.
A frozen location is never written to, and no `Uniq` is pushed.
-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 `mem::size_of::<T>` many bytes).
+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).
Whenever a shared reference is created, if there is no interior mutability, we freeze the locations if they are not already frozen.
If there is interior mutability, we just push a `Raw`.
Whenever a raw pointer is created from a mutable reference, we push a `Raw`.
A shared reference without interior mutability is active if the location is frozen at least since the location was created.
A shared reference with interior mutability is active is `Raw` is on top of the stack.
-Whenever a reference is used to do something (anything), we make sure that it is active for all locations that it covers; this can involve unfreezing and popping the stack.
-If it is not possible to activate the reference this way, we have UB.
+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.
+If it is not possible to reactivate the reference this way, we have UB.
+
+**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**
## 3 Tracking Borrows
If we compared them as raw pointers, they would turn out equal.
And yet, it makes a huge difference if we use `x` or `y`!
-If you read my previous post on [why pointers are complicated](2018-07-24-pointers-and-bytes), this should not come as too much of a surprise.
+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.
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.
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.
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.
The full model is not quite as simple, but it is not much more complicated either.
-We need two add just two more concepts: Retagging and barriers.
+We need to add just two more concepts: Retagging and barriers.
### 4.1 Retagging
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:
After using `x`, we know it is active.
-Next we use and activate `y`, which has to pop `Uniq(x)` as they have distinct tags.
+Next we use and reactivate `y`, which has to pop `Uniq(x)` as they have distinct tags.
Finally, we use `x` again even though it is no longer in the stack, triggering UB.
-(A `Uniq` is only veer pushed when it is created, so it is never in the stack more than once.)
+(A `Uniq` is only ever pushed when it is created, so it is never in the stack more than once.)
### 4.2 Barriers
Consider the following code:
{% highlight rust %}
-fn demo5(x: &mut i32, y: usize) -> i32 {
+fn demo5(x: &mut i32, y: usize) {
*x = 42;
foo(y);
}
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).
This could happen if the stack contained, somewhere, a `Raw`.
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.
-This is sometimes crucial, but in this case, `demo5` should be able to prevent those old historic borrows involved in creating `x` from being activated.
+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.
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.
-This way, all the borrows further down in the stack (below `Uniq(x)`) are temporarily disabled and cannot be activated while `demo5` runs.
-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 activated.
+This way, all the borrows further down in the stack (below `Uniq(x)`) are temporarily disabled and cannot be reactivated while `demo5` runs.
+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.
Another way to think about barriers is as follows:
The model generally ignores lifetimes and does not know how long they last.
-All we know is that when a reference is used, its lifetime must be ongoing, so we say that is when we activate the borrow.
+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.
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.
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.
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:
-When renumbering `x`, we are pushing a barrier. Renumbering `y` would attempt to activate `Uniq(y)`, but that can only be behind the barrier, so it cannot be activated.
+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.
## 5 The Model in Code
self.frz_since.map_or(false, |loc_t| loc_t <= acc_t),
Mut(acc_m) =>
// Raw pointers are fine with frozen locations. This is important because &Cell is raw!
- (acc_m.is_raw() && self.frozen_since.is_some()) ||
- self.borrows.last().map_or(false, |loc_itm| loc_itm == Mut(acc_m)),
+ if self.frozen_since.is_some() {
+ acc_m.is_raw()
+ } else {
+ self.borrows.last().map_or(false, |loc_itm| loc_itm == Mut(acc_m))
+ }
}
}
- /// Activate the given existing borrow for this location, fail if that is not possible.
- fn activate(&mut self, bor: Borrow) {
+ /// Reactivate the given existing borrow for this location, fail if that is not possible.
+ fn reactivate(&mut self, bor: Borrow) {
// Do NOT change anything if `bor` is already active -- in particular, if
// it is a `Mut(Raw)` and we are frozen.
if self.check(bor) { return; }
while let Some(itm) = self.borrows.last() {
match itm {
FnBarrier(_) => {
- bail!("Trying to activate a borrow that lives behind a barrier");
+ bail!("Trying to reactivate a borrow that lives behind a barrier");
}
Mut(loc_m) => {
if loc_m == acc_m { return; }
}
}
}
- bail!("Borrow-to-activate does not exist on the stack");
+ bail!("Borrow-to-reactivate does not exist on the stack");
}
/// Initiate the given (new) borrow for the location.
For each of these operation, we iterate over all affected locations; let us call the loop variable `loc` of type `MemoryByte`.
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, ...).
-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/beta/std/cell/struct.UnsafeCell.html).
+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).
(This realizes the conditions checking whether we have interior mutability or not.)
For example, in `&Cell<i32>`, all 4 locations are inside an `UnsafeCell`.
However, in `&(i32, Cell<i32>)`, only the last 4 of the 8 covered locations are inside an `UnsafeCell`.
Now we can look at what happens for each operation.
* 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.
-* 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 activate.
- - `loc.activate(borrow)`.
+* 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.
+ - `loc.reactivate(borrow)`.
* Any time a *new* reference is created (any time we run an expression `&mut foo` or `&foo`), we (re)borrow.
- Bump up the clock, and remember the old time as `new_tag`.
- Compute `new_bor` from `new_tag` and the type of the reference being created.
- `if loc.check(new_bor) {`
* The new borrow is already active! This can happen because a mutable reference can be shared multiple times. We do not do anything else.
- As a special exception, we do *not* activate `bor` even though it is "used", because that would unfreeze the location!
+ As a special exception, we do *not* reactivate `bor` even though it is "used", because that would unfreeze the location!
`} else {`
- * We might be creating a reference to a local variable. In that case, `loc.reset()`. Otherwise, `activate(bor)`.
+ * We might be creating a reference to a local variable. In that case, `loc.reset()`. Otherwise, `reactivate(bor)`.
* `initiate(new_bor)`
`}`
* 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.
- Bump up the clock, and remember the old time as `new_tag`.
- Compute `new_bor` from `new_tag` and the type of the reference being created.
- - `activate(bor)`.
+ - `reactivate(bor)`.
- If this is a function argument coming in: `loc.borrows.push(FnBarrier(stack_height))`.
- - `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 we do not want to push that might unfreeze the location when being activated.
+ - `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.
- Change reference tag to `new_tag`.
* Any time a raw pointer is created from a reference, we might have to do a raw reborrow.
- - `activate(bor)`.
+ - `reactivate(bor)`.
- `initiate(Mut(Raw))`. This is a NOP when coming from a shared reference.
* Any time a function returns, we have to clean up the barriers.
- 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>
This could be optimized by adding an indirection, so we just have to record somewhere that this function call has ended.
+* 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.
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.
It is just easier to answer these questions when you do not have to *manually* reevaluate all examples after every tiny change.
However, I can always use more examples, so if you think you found some interesting or surprising corner case, please let me know!
-<!-- As always, if you have any questions or comments, feel free to [ask in the forums](). -->
+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).
projects / web.git / blobdiff