---
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.
## 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
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`.
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.
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.
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);
}
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))
+ }
}
}
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`.
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