Improve upon Stacked Borrows by introducing a tree

I have been thinking about how to improve upon Stacked Borrows the past few weeks. Now my first draft of my idea is finished and i would appreciate any feedback greatly.

I have read

So point me to anything I might have missed!

Replacing the stack with a tree is not an original idea, Ralf mentioned it in this blog:

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).

What the tree should improve:

  • better interior mutability tracking
  • define allowed mutable aliasing
  • retain existing behavior
  • catch use-after-move errors
  • improve handling two-phase borrows

It of course also has some drawbacks (especially the way I defined some of the interactions), but I hope that these are actually advantages (allowing more optimizations/simplifying other areas) or they are worth, because of what they enable us to do.

Any feedback is welcome! Hints to improve the formatting/wording and of course problems with the design itself.

Why is this even needed?

I am in no way sure that the proposed idea fixes any of these problems, but I hope that this is a step in the right direction.


Just a couple first pass notes from me:

TB does not include untagged pointers, so ptr-int-ptr round trips will always produce pointers with invalid tags. This should not really be a problem, because iirc (y86-dev) non provenance respecting code is going to be UB at some point. This of course poses some problems for code abusing provenance (e.g. XOR linked lists), so maybe we need to add the Untagged pointer-id like SB has today

IIUC the current plan for "next gen" SB is to drop Untagged and the complexity it introduces (-Zmiri-strict-provenance), now that the Strict Provenance Experiment has shown that most code actually can maintain provenance and doesn't need to use expose_addr and from_exposed_addr. [from_]expose[d]_addr would then be modeled as extern functions, with angelic nondeterminism (in implementation: maximally conservative treatment) to choose a non-UB execution (all of which have the same observable behavior).

I summarized that poorly, but the general plan is outlined by RalfJ in Zulip.

TB needs type information at allocation time. I (y86-dev) gave a quick glance at the source code and did find easy access to the type at allocation time. Maybe it is possible to postpone such a type lookup until the first use of the location.

Type lookup will likely need to be done at access time, not at allocation time. box $expr currently does a "typed" allocation, but trait Allocator (and trait Storage) do allocations based purely off of Layout. The current goal is to eventually make Box less special an have its de/allocation and deref paths (c.f. DerefMove) go through library code using the Allocator parameter rather than being an intrinsic part of MIR.

However, if the transmute problem is solved, we could theoretically keep the typed allocation and just say that all heap memory is allocated as [MaybeUninit<u8>]... but if that's supported, why is the stack doing special typed things and not just using the same mechanism.

Creating a T, transmuting it to UnsafeCell will not allow UnsafeCell-like access to T (because the original tag of the location will be Unique ).

This is a blocker. Cell::from_mut(&mut T) -> &Cell<T> is stable.


In lccc, xlang's model seems fairly similar to this, though with key differences:

  1. xlang's model divides permissions from tags into two parts - aliasing attributes and valid-range attributes. The two are partially orthogonal, but this allows more granular selection than stacked borrows tags.
  2. There is no two-phase borrow - I do not believe them to be necessary based on how XIR's model does invalidation, and how various types interact with the many pointer attributes. In the one case for two-phase borrows, it could be performed with "creative" uses of derive operation (which would incidentally be less creative in an SSA IR than xlang's stack based IR, which involves a pivot to bring the offending pointer to the head, a derive to change attributes, then a pivot to place it back in the correct location pending the function call).
  3. the xlang model relies on a structural object model for memory - it uses this to determine things like what regions of memory are covered by an UnsafeCell by asking "Is this a mutable subobject" or "Is this part of the object-representation of a mutable subobject". This is not a fundamental flaw for a rust model - it could be changed to ask about bytes rather than objects. UnsafeCell would just be fun again.
  4. On page 8, §3.1.1 notes that TB, unlike SB, does not permanently invalidate raw pointers. The xlang model preserves the Stacked Borrows Behaviour

The xlang model does allow this by "creates transparent objects".

Another note, about the model I mentioned above, though I didn't see it addressed by TB, xlang's model permits the direct cast of &mut T to *const T to have write access with triggering a reborrow as Unique, which poses a problem in SB as it invalidates the following safe code:

let mut x = 0i32;
let y = &mut x;
let z = &*y;
let p = y as *const i32;

This seems to be the same thing that I proposed here, so that seems good.

IIUC this is only needed by legacy code (so code that was not updated to conform to strict provenance) and provenance nightmares like XOR Linked Lists. But I think that we could add new pointer functions allowing xoring with usize/another pointer (thus also conforming to strict provenance). I do not know if there are other situations where new API is not an option.

I tried to find it on zulip, but was not able to, could you point me to the right thread/tell me the right way to search?

I have only looked at the MIR generation code very sparsely, so this might not be feasible, but when computing the layout, some form of type information needs to be present, so in my mind it could be possible to extend the layout information (only in miri executions/compilations) with the location tags at each byte. Or just pass the type with the allocation call (also only when using miri).

What transmute problem are you refering to (point 3 of "Current Issues"?)? When all heap allocations have type [MaybeUninit<u8>] then using Box<UnsafeCell<u8>> does not tag the location with SharedReadOnly, but with Unique, triggering undefined behavior when the cell is used normally.

Good catch! This is a bummer, realistically this seems to just be a violation of the rules I proposed. I looked at the rfc that introduced the function and would like to see if this code is actually used in some crates (I know there exist some tools for this, notably crater [but that is for also running tests] and I remember some blog post about downloading all of, but i would like to know if there is a simpler "search through popular crates" tool).

On second thought, theoretically I think that we could provide the exact same function in UnsafeCell (my intuition says that when we own a unique &mut T, we are already allowed by TB to create as many derived *mut T as we want and then write/read in an aliased way. The UnsafeCell would only live for the same lifetime, preventing any misuse.), this way we could specially handle that function (because I would like to avoid making Cell a special type) and in Cell::from_mut call UnsafeCell::from_mut and then do another pointer cast to Cell.

I am not familiar with lccc, so I might have misunderstood this:

Both SB/TB augment locations (each byte induvidually) in memory with a stack/tree holding the items (pointer id + permission tag) of pointers allowed to access the location. Range attributes are not present on pointers themselves. But this way access is also very granular.

I am not yet accustomed to two-phase borrows, I do not know the rationale behind allowing the pattern (i only glanced over the PR, could have missed something). I think it is only to allow more ergonomic usage of mutable methods that can take a parameter created by the same (but immutable) receiver (e.g. vec.push(vec.len())).

This would actually be very similar to the location-tag tracking that I have in mind for TB, UnsafeCell would just be mapped to SharedReadOnly and only UnsafeCell::get is allowed to cast that pointer to SharedReadWrite.

Theoretically nothing prevents TB from also following the SB behavior, but I thought that this way would make more sense. Can you/anyone else explain to me why it is necessary/good to invalidate the derived *mut T (that explicitly allows aliased mutation) when the parent &mut T is written to?

I tried to find it in the documentation, but was not successful, could you point me to it?

This is covered in section 1.4.4 on page 4:

When casting a reference to a raw pointer (Unique / SharedImmutRead 7→ SharedReadWrite / SharedReadOnly , or Unique Two-Phase-Unique ) or reborrowing a reference, treat it the same as a write/read access of that pointer.

So yes there exists a direct cast to *const T (i think this is also present in SB).

That's part of the object model (rather than the pointer model), which is incompletely documented. I'm working on it, though, but I'm also working on several other parts of the xlang documentation, and the actual backend stuff, as well as the XIR frontend, so it is slow going.

Yeah, the XIR model places pointer values themselves, rather than individual tags, in the graph. That is, given let x = #[repr(C)] (0u8, 0u16); taking &x in SB gives 4 tags over each of the 4 bytes of x, xlang's model gives one pointer that has dereferenceable(4) and needs 4 bytes to be "reachable" from the start of &x. The range attributes dictate desired permissions, whereas the aliasing attributes (unique, readonly, readshallow, and invalid) together dictate the permissions for other pointers (none for regions covered by a unique pointer wrt. other pointers, read only for regions covered by a readonly pointer or readshallow wrt. the same pointer) as well as the invalidation behaviour of derive operations. The granularity here is in the combination of attributes (this would notably allow a unique, read only pointer, by combinining unique and readonly)

Indeed - though XIR just allows you to do any operation that reaches the mutable subobject - an as cast would suffice (that is - UnsafeCell is magic, not UnsafeCell::get).

Consider the following code:

extern "C" { fn expose_addr(x: *mut u32); fn foo();}
let mut x = 0u32;
unsafe{expose_addr(&mut x as *mut i32);} // through some means, leak the address of `x`
x = 1i32; // Assignment to named place contains reborrow as Unique
x = 2i32; // Ditto here, but it's a new `&mut`

The SB behaviour (that xlang replicates) allows the first assignment to x to be delayed passed f and combined with the assignment of x to 2 (or dropped entirely, if nothing later uses x). The current TB behaviour does not, since f could reactivate the raw pointer to x that was exposed by expose_addr. I find this a very useful optimization as most FFI calls(perhaps a read(2) or write(2) call) won't actually keep a pointer arround for long enough that it would be broken by the reordering, but the optimizer can't know that.

In current rustc, the cast of &mut T to *const T does a reborrow as &raw const, which reduces to SRO. This is required because of the aformentioned code and a limitation in stacked borrows.

Nice, keep up the good work! Would be interesting to know more about those transparent objects though, how are they used and how do they work?

Yeah this is not in SB, because there you only have the stack structure indicating the relationship between the pointers. TB also could just move to this model (adding a range on the pointer). This also seems reasonable, but I am not sure about the implementation details.

In TB UnsafeCell would also still be magic (all locations containing an UnsafeCell are marked with SharedReadOnly), but it additionally requires UnsafeCell::get to be magic as well, because it breaks normal behavior of SharedReadOnly (no reborrow as a writable pointer allowed, except when the a parent is Unique/SharedReadWrite). I thought about creating another tag for that, but I thought that SharedReadOnly captures the other qualities good enough.

Right that is a good argument, I will change TB to allow for this.

But why does xlang allow &mut T -> *const T to have write access? I think it is sufficient to allow &mut T -> *const T -> *mut T to have write access (although tracking this might be difficult).

The more specific thing is that &mut T -> *const T does not deny write access - permissions in xlang are subtractive, not addative. Specifically, there's no XIR *readonly pointer anywhere, or *readshallow pointer between the &mut T and *const T. The const in *const T is just for show in XIR, rust, and C++.

A transparent object is an object of an implicit-lifetime (irrelevant to rust) type that is transparent (so #[repr(transparent)] in rust). Certain kinds of pointer operations are allowed to implicitly-create objects in overlapping storage that new pointers point to. Technically, &T->&UnsafeCell<T> is permitted by those rules, though the &T would preclude getting a writable pointer to the interior, since the outer pointer points to the mutable subobject that acts as the barrier for readonly in xlang.

But what prevents someone to write C code that places the pointer in some global and then reads it in f()? Is this not allowed/UB for extern "C" functions (that would be strange)? Is this not allowed/UB in C (this also would be strange)? When concerned with extern code is this optimization really allowed?

Plugging the code into the playground reveals in the llvm-ir (it could be erroneous, because there are still unlinked symbols, but i think the optimization passes should not be affected) no reordering of the assignments:

; playground::main
; Function Attrs: nonlazybind uwtable
define internal void @_ZN10playground4main17h0f70b70433043d01E() unnamed_addr #2 {
  %x = alloca i32, align 4
  %0 = bitcast i32* %x to i8*
  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %0)
  store i32 0, i32* %x, align 4
  call void @expose_addr(i32* nonnull %x)
  store i32 1, i32* %x, align 4
  call void @foo()
  store i32 2, i32* %x, align 4
  call void @print(i32 2)
  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %0)
  ret void

So I am not so sure if this really is a sound optimization.

In my mental model *const T means readonly but !immutable so subsequent reads cannot be reordered (&T on the other hand has this guarantee, so reads can be reordered).

When casting &mut T to *const T we have a pointer that we can only use for read access, but in TB you are allowed to cast it to *mut T (I think i should add in TB that this counts as a write access at the first mutable ancestor) and then use that to write. So at any point a SRO that is derived from a pointer with write access may be cast to a pointer with write access (this requires reasserting the write capability of the writable ancestor), there is no need to invalidate other write-capable pointers when a SRO is created.

It is because it's UB from the rust side of FFI to use the pointer: Rust requires that FFI obey both the Rust Rules and the target-lang rules.

XIR doesn't have a concept of a restriction that can be lifted - readonly means "this and other pointers cannot be used write to that object (excluding mutable shenanigans)" and readshallow means "this pointer and derivatives cannot be used to write to that object". There's no version that denies a permission to that pointer, but allows it to derivatives - there isn't really a functional point.

Once you have a pointer, *const T versus *mut T is just a lint to control variance. Initial as *const T creates a read-only pointer, and as *mut T creates a read-write pointer, and casting between pointers makes no change.

This is a decided factor for Rust surface level semantics. (mut_ref: &mut T) as *const T is (&*mut_ref) as *const T, as you can see by how the borrow checker behaves in the following example:

fn okay(mut_ref: &mut u8) {
    let derived = &mut_ref;
    mut_ref as *const u8;

fn also_okay(mut_ref: &mut u8) {
    let derived = &mut_ref;
    (&*mut_ref) as *const u8;

fn not_okay(mut_ref: &mut u8) {
    let derived = &mut_ref;
    mut_ref as *mut u8; //~ error

If I've understood your model correctly, either (ptr: *const T) as *mut T has a side effect (bad! what about transmute?) or this safe code would be made UB.

Just let reference as *const _ be &*reference as *const _. It's simpler for everyone.

This is generally considered undesired behaviour. I've seen quite a few people (including on the Rust Community Server in the #dark-arts channel) suprised by this. To add insult to injury, (mut_array_ref: &mut [T]) as *const T does not contain an intermediate reborrow as &[T] and produces a pointer with write provenance over the array.

1 Like

Why is SharedImmutRead called as such when it doesn't allow aliasing? Why not UniqueImmut or something like that?

That sounds like a bug in miri to me, as the motivating safe example I provided behaves the same way for &mut [u8] as it does &mut u8 (that is, it allows (mut_ref: &mut [u8]) as *const [u8] when mut_ref is immutably borrowed.

Though (mut_ref: &mut [u8]) as *const u8 (casting &mut [u8] as *const u8), which is what you wrote, is just invalid; I've assumed you meant (mut_ref: &mut [u8]) as *const [u8] (casting &mut [u8] as *const [u8]).

However, I'm getting a miri error when writing through such a pointer. Can you provide an example of the slice code which you believe is inconsistent with mut_ref as *const _ being (&*mut_ref) as *const _?

Nope. Or it might be arrays rather than slices. But there is an array to pointer cast: Rust Playground

Well, if anything it's a bug in rustc's MIR generation because it contains a &raw mut rather than &raw const. MIRI just does what it's told.

So what I think is going on is that there's a multiple step coersion going on here, and that's making things wonky.

First, note that while &mut [u8; N] as *const u8 is treated as a mutable borrow, as *const [u8; N] and as *const [u8] are both immutable borrows.

So what I think is happening is that a cast from &mut [u8; N] to *const u8 isn't actually valid, and what we're getting is instead &mut [u8; N] being relaxed to *mut [u8; N] and then cast. Or something along those lines, I'm failing to explain what the compiler in my head is saying about this example.

I definitely think that this is a bug, and as *const should consistently be an immutable use of the lhs reference.

This behavior was introduced rustc 1.52; 1.51 and prior say that casting &mut [u8; N] to *const u8 is invalid. 1.51 was the introduction of stable const generics, but I don't see anything that would be relevant to this cast.

In any case, both can be fixed in either tree/graph model - we can have our cake an eat it too as it were, both treat it as an immutable borrow, but allow it to have dynamic write provenance. XIR's model makes it valid for free - in lccc, raw pointers get no non-trivial validity attributes, so the only invalidations happening at the derive are the normal *-unique invalidations.