Level 5 · Research· Lesson 3 of 9 · 50 min
Aliasing models: Stacked Borrows, Tree Borrows and provenance
What unsafe code is actually allowed to do — operational semantics for references, pointer provenance, and the optimisations these models exist to justify.
Safe Rust’s rules are enforced by a type checker. Unsafe Rust’s rules are a specification of undefined behaviour — and for aliasing, that specification is still being settled. This lesson covers the two leading proposals and the concept underneath both.
Why a model is needed
Consider what the compiler wants to do with references:
fn example(x: &mut i32, y: &i32) -> i32 {
*x = 10;
unknown(); // some function the compiler cannot see into
let a = *y;
*x = 20;
a + *x // the compiler would like to return `a + 20` without re-reading *x,
// and to assume `*y` was not changed by `*x = 10` or by `unknown()`
}
fn unknown() {}
Those optimisations are valid only if x and y do not alias, and if unknown cannot write to *x or *y through some stashed raw pointer. The type system guarantees this for safe code. For unsafe code, nothing in the type system stops you from fabricating an aliasing &mut. So the language must declare such programs to have undefined behaviour, and it must say precisely which ones — otherwise neither compiler authors nor unsafe-code authors know where the line is.
An aliasing model is therefore a contract with two sides: it lists what unsafe code must not do, and thereby what the optimiser may assume.
The models are defined operationally: the abstract machine carries extra “ghost” state, and each memory access checks and updates it. If a check fails, the program has UB. Miri implements exactly this machine, which is why it can detect violations.
Provenance
Before aliasing, a more basic question: what is a pointer?
fn main() {
let a = [1u8, 2];
let b = [3u8, 4];
let end_of_a = a.as_ptr().wrapping_add(2);
let start_of_b = b.as_ptr();
// The two addresses may well be equal — the arrays can be adjacent on the stack.
println!("same address: {}", end_of_a as usize == start_of_b as usize);
// Yet reading through `end_of_a` is undefined behaviour even if they are equal:
// it was derived from `a`, and its provenance does not cover `b`.
println!("{}", unsafe { *start_of_b });
}
A pointer in the abstract machine is an address plus provenance: the allocation it was derived from and the permissions it carries. Provenance is not stored in the bits; it exists so that the compiler can reason that pointers derived from different allocations never alias. All mainstream compilers already reason this way — LLVM and GCC miscompile programs that assume pointers are “just integers”.
Consequences:
- A pointer may only access memory within the allocation it was derived from, even if arithmetic lands it on a valid address elsewhere.
- Pointer-to-integer casts lose provenance; integer-to-pointer casts must conjure it. This is the hard part. Rust offers two regimes:
- Strict provenance (stable since 1.84):
ptr.addr()returns the address without exposing provenance;ptr.with_addr(a)andptr.map_addr(f)produce a new pointer with a different address and the same provenance. Pointer tagging and similar tricks can be written with no int-to-pointer cast at all, and Miri can check them precisely. - Exposed provenance:
ptr.expose_provenance()andptr::with_exposed_provenance(addr)(andascasts) allow real round trips. The model marks the provenance as exposed, and a later cast may pick up any exposed provenance — sound for the programmer, but it blocks optimisations and is inherently fuzzy to check.
- Strict provenance (stable since 1.84):
- Bytes carry provenance too: copying a pointer byte-by-byte must preserve it, which is why memory is modelled as abstract bytes (initialised-with-optional-provenance, or uninitialised), not as
u8.
Stacked Borrows
Jung, Dang, Kang and Dreyer, POPL 2020.
Every pointer value carries a tag. Every memory location has a borrow stack of items, each a tag with a permission:
| Permission | Granted by | Allows |
|---|---|---|
Unique |
&mut T |
read and write |
SharedReadOnly |
&T (outside UnsafeCell) |
read |
SharedReadWrite |
raw pointers, &T inside UnsafeCell |
read and write |
The rules, in essence:
- Retag. Creating a reference, or passing one to a function, pushes a new item with a fresh tag on top of the stack, above the item it was derived from.
- Use. To access memory through a pointer, its tag must be in the stack. A write pops everything above the item used. A read pops (or disables) the
Uniqueitems above it. - If the tag is no longer in the stack, the access is undefined behaviour.
- Protectors. A reference passed as a function argument is protected for the duration of the call: popping its item is UB. This is what lets the compiler assume a reference argument stays valid throughout the function.
The stack discipline mirrors the nesting of reborrows that the borrow checker enforces statically: a child borrow must be finished before its parent is used again.
fn main() {
let mut x = 10;
let a = &mut x as *mut i32; // stack for x: [Unique(x), SharedRW(a)]
let b = &mut x as *mut i32; // a new &mut x is a write-like use of the base: pops `a`
// stack for x: [Unique(x), SharedRW(b)]
unsafe {
*b += 1; // fine: b's tag is on the stack
// *a += 1; // would be UB: a's tag was popped
}
println!("{x}");
}
Uncomment the write through a and run it under Miri on the Playground — the “Undefined behaviour” example there is this program. A normal run prints 12 and gives no hint of a problem.
The correct way to obtain two raw pointers to the same data is to derive both from one: let a = &raw mut x; let b = a;.
Where Stacked Borrows is too strict
Stacked Borrows validated an important set of optimisations, with machine-checked proofs. But experience with Miri on real crates exposed patterns it rejects that programmers consider reasonable and that LLVM does not actually exploit:
- A reference is retagged for exactly the bytes of its type. Code that takes
&mut headerand then offsets the pointer to reach trailing data in the same allocation (the C “container_of” idiom) is UB. - Creating a
&mutis treated as a write, so merely creating a mutable reference invalidates sibling pointers even if it is never used. - Shared references permit no reordering with certain raw-pointer reads that seem harmless.
Tree Borrows
Villani, Hostert, Dreyer and Jung, PLDI 2025.
Tree Borrows replaces the stack with a tree per allocation: each node is a pointer tag; a reborrow adds a child. Each node holds, per memory location, a state from a small state machine:
An access is a child access for a node if it is made through that node or one of its descendants, and a foreign access otherwise. Each access updates every node in the tree according to this transition table (simplified; protectors and interior mutability add cases):
| State | Child read | Child write | Foreign read | Foreign write |
|---|---|---|---|---|
Reserved (fresh &mut) |
stays | → Active |
stays | → Disabled |
Active (written-to &mut) |
stays | stays | → Frozen |
→ Disabled |
Frozen (&T, or demoted &mut) |
stays | UB | stays | → Disabled |
Disabled |
UB | UB | stays | stays |
What this buys:
Reservedmodels two-phase borrows directly. A fresh&mutis not yetActive; it tolerates foreign reads until its first write. Creating a mutable reference is no longer a write.- Lazy, access-driven violations. A conflicting pointer becomes
Disabledonly when a conflicting access actually happens, and UB occurs only when a disabled pointer is used. - No fixed extent. Permissions outside the reference’s initial range are initialised lazily on first access, so the
container_ofpattern and offsetting within one allocation are permitted. - Protectors remain, strengthened: a protected node must not become
Disabled, and function-argument references behave as active for the duration of the call.
The price: a few optimisations valid under Stacked Borrows are lost, notably some that move writes earlier, since a Reserved reference has not yet claimed exclusivity. The paper’s evaluation found Tree Borrows rejects markedly fewer real-world crates’ test suites than Stacked Borrows while retaining the read-reordering optimisations that matter. The authors also provide mechanised proofs (in Rocq) that the key optimisations are sound under the model.
In Miri, Stacked Borrows is the default; -Zmiri-tree-borrows selects Tree Borrows. Neither is normative yet. The official position is conservative: code that is UB under both models should be considered wrong; code accepted by Tree Borrows but rejected by Stacked Borrows is in a grey area that will most likely end up allowed.
The wider specification effort
- The Rust Reference lists behaviour considered undefined, with an explicit caveat that the list is not final.
- The Unsafe Code Guidelines working group (now the opsem team) maintains a glossary and an issue tracker of open questions — validity of references to uninitialised memory, the exact
UnsafeCellrules, when padding may be read, and more. - MiniRust (Jung) is a precise specification of a core Rust-like language written as an interpreter in a Rust-like pseudo-language: the intended normative definition of the abstract machine, with Stacked/Tree Borrows as a pluggable component.
- Miri (Jung et al., POPL 2026) is the reference implementation of all of this and is what makes the models falsifiable: they are evaluated against the test suites of thousands of crates.
Rules to work by today
- Never have a live
&mut Tand any other usable pointer to the same memory that was not derived from that&mut. - Do not write through a pointer derived from
&Tunless the data is inside anUnsafeCell. - When you need several raw pointers to one object, create one raw pointer and copy it; do not create references in between.
- Prefer
&raw mut/&raw constto&mut x as *mut _— they create no intermediate reference. - Keep pointers as pointers. Use the strict-provenance API; avoid integer round trips.
- Run your tests under Miri with both models.
Reading list
- Jung et al., “Stacked Borrows: An Aliasing Model for Rust” (POPL 2020).
- Villani et al., “Tree Borrows” (PLDI 2025), and Villani’s earlier blog series.
- Jung, “Pointers Are Complicated” I–III (blog) — the best introduction to provenance.
- Memarian et al., “Exploring C Semantics and Pointer Provenance” (POPL 2019) — PNVI and the C side of the story.
- Lee et al., “Reconciling High-Level Optimizations and Low-Level Code in LLVM” (OOPSLA 2018).
- The
std::ptrmodule documentation, sections on provenance. - The MiniRust repository and the Unsafe Code Guidelines reference.
Exercises
- For the
a/bprogram, write the borrow stack after each line under Stacked Borrows. Then draw the tree and node states under Tree Borrows. Does Tree Borrows accept the write througha? Check with Miri. - Write a program that Stacked Borrows rejects and Tree Borrows accepts, using a pointer to the first field of a
repr(C)struct to reach the second field. - Implement a tagged pointer (low two bits used as flags) with
map_addr, never casting an integer to a pointer. - Explain, with reference to protectors, why it is UB for a function taking
x: &mut i32to cause*xto be deallocated before it returns, even ifxis never used again. - Give one optimisation that is sound under Stacked Borrows and not under Tree Borrows, and argue why from the
Reservedstate.
Check your understanding
Pick an answer to see the explanation.
1.Why does Rust need an aliasing model defined for unsafe code, when the borrow checker already enforces aliasing rules?
2.What is pointer provenance?
3.How does Tree Borrows chiefly differ from Stacked Borrows?