Tree Borrows explained

The recent merge of Tree Borrows into Miri was unfortunately not immediately accompanied by an example-driven explanation.

This new blog post remedies that issue. It is by no means short, but it is structured so that reading only a prefix provides an incomplete-but-not-wrong model.

I look forward to any

  • examples of code that would be expected to be UB but are not according to TB
  • examples of code that TB declares UB but should not be
  • suggestions of codebases that TB should be tested on (already tested: stdlib, regex, tokio, rand, hashbrown)

Note: this is mostly unrelated to the other model sharing the same name, in that it addresses the same issue but in a completely different way.

29 Likes

Nice! From a quick lookover it looks quite informative and I look forward to reading it in full.

Example: copy_nonoverlapping

Am I correct that this fixes the most practically annoying issue in SB where it’s too easy to accidentally borrow something, and then get punished, even if you don’t actually use that?

That is, that TB would fix Vec::push invalidates interior references even when it does not reallocate Β· Issue #60847 Β· rust-lang/rust Β· GitHub by making analysis smarter, without requiring changes to the unsafe code?

Yes, even if you create a mutable reference you pay the cost of a write access only on locations you explicitly write through. Reborrowed locations that are not written to only pay the cost of a read access.

In the example you linked (since there is no reallocation) v.push(1) never writes to v[0] and thus does not disable v0. The most closely related piece of code that would not be accepted by TB needs two more write accesses:

fn main() {
    let mut v = Vec::with_capacity(10);
    v.push(0);
    let v0 = unsafe { &mut *(&mut v[0] as *mut _) };
    *v0 += 1; // v0: Reserved -> Active
    v.push(1); // v0: Active -> Frozen
    *v0 += 1; // Write through Frozen is UB
}
1 Like

Oh, this is absolutely brilliant then! Looks like mere mortals can now write sound unsafe code again :heavy_heart_exclamation:

1 Like

Yes, that was the hope. :slight_smile:

Now, mind you, this is not free: we may the price of being able to do fewer optimizations for write accesses, since mutable references are only considered writable if they have ever written to. So discussions will have to be had about the trade-offs here. The idea is that we now have two points in the design space (Stacked Borrows and Tree Borrows): the former prioritizing optimizations, the latter prioritizing supporting the main code patterns that turned out to be problematic with Stacked Borrows. The final model might well sit somewhere between the two, but that discussion is much easier to have with concrete proposals at hand.

That is with the old Vec implementation, right? Current Vec should accept this code since v.push does not create a reference to the entire vector content any more.

So, the bugfix for #60847 is still important.

8 Likes

I quite like this! I agree that this model more closely matches my model of the average developer's understanding of the borrow rules than SB, though I have a hard time putting into words exactly how or deriving implications more interesting than those spelled out by the OP.

I have a few clarifying questions for my own benefit.

Clarification: if you pass a reference to a function, the protector includes a reborrow and does a phantom read, throwing UB if the tag is disabled, correct?

Question: when you pass a mut reference to a function, do the protector semantics function in such a way that the tag already being Frozen is UB? I know they're leaving Reserved as-is until an actual write happens.

Clarification: shared mutability is handled via the unexplained ty_is_freeze query: is this currently using the UnsafeCell tracking which is field granular (for structs only, infectious for enum/union) or is it always a single yes/no answer for the entire reborrowed range?

Clarification: Unpin isn't mentioned in the state automaton; is it correct then that Unpin only impacts when a new borrow is derived, and not when read/writes are done?

Clarification: what interaction of rules make it so &mut impl !Unpin doesn't get noalias on function boundaries with protectors but &mut impl Unpin does? This wasn't super clear to me on the first read through at least.

Question: how are Unpin/Freeze handled for the range of the allocation outside of the known range of the reborrowed type? (For extern type, you at least have the extern type to do type queries on, but for other cases you just don't know. Personally, I'm fine with strict borrow subranges even though it breaks *addr_of!(v[0]), requiring the use of extern type to get delayed retagging semantics. But will admit this can still cause some issues, e.g. with allocators storing meta before the returned pointer.)

Question: if a function takes a shared reference derived from a writable reference and writes to it, and that's the last access that ever happens, when/is that UB? For some reason I'm having trouble mentally tracking that at the moment, for TB or for SB. (Context derived from the previous: deallocating from a child provenance, would that be able to jump up to the root provenance or would it be UB because it's working at a derived provenance without write/dealloc permission? Potentially relevant for Box<T> -> &'static T -> Box<T>.)

Interesting observation: because &mut borrows start as the two-phase reserved stated, &mut borrow splitting just falls out of the model without any special handling, even if it were to keep fully eager instead of delayed tag reborrowing. This is evident from the walkthrough of the disjoint fields example.

Interesting observation: this isn't what TB is doing. But if all retagging is delayed (i.e. the phantom read on reborrow doesn't undelay the retag), this alone makes the spurious speculative write an incorrect optimization (and also would for reads, which is bad). This suggests an interesting potential middle ground between full two-phase and no two-phase: non static two-phase mut borrows could do the phantom read (putting them in the Reserved state) and then make a delayed phantom write transition to Active. This would I believe allow moving writes before reads again but I think still retain some of the benefit of being two-phase (not actually requiring uniqueness unless written through). On the other hand doing so makes the state more complicated (it's basically another state between Reserved and Active; let's say Speculated) for speculative and likely quite minimal benefit. A more realistic middle ground would be to make function protectors activate

2 Likes

Protector semantics described here allow a protected mutable reference to be Frozen, as long as it never became Active, i.e. it went directly from Reserved to Frozen because of a foreign read.

The case you're describing is slightly different: if the parent is Frozen and is reborrowed mutably, then this creates a Reserved child of Frozen. As long as you only read, everything is fine. If you ever try to write then UB will be triggered by the Frozen parent, not by the Reserved child.

Another way of saying this: Unpin &muts start out Reserved. No exceptions. However they can have ancestors that are Frozen and these will block writing.

Freeze is not granular:

// computed exactly once per reborrow
// src/borrow_tracker/tree_borrows/mod.rs
// in `fn from_ref_ty` at L114
let ty_is_freeze = pointee.is_freeze(*cx.tcx, cx.param_env());

Unpin does indeed only matter at reborrow time, where Unpins get their own tag and !Unpins don't. As for the why, see UCG #381: &mut impl !Unpin are not dereferenceable

Since the Freeze and Unpin properties are not checked granularly, they are applied identically to out-of-range locations. That's a very debatable aspect of the model, but for now it's in line with TB being "maximally permissive" and can totally be changed if deemed problematic.

Only as long as you don't write between the two reborrows though...

A shared derived from a mutable is a Frozen child of Active. Trying to write through that is an attempted write through Frozen, so UB.

Deallocation will first perform a fake write. If the pointer you try to deallocate through is or has a parent that is Frozen, then this is UB.

Is this the reason for why this is not UB under TB:

use core::{cell::Cell, ptr::addr_of};

struct WithCell {
    _cell: Cell<()>,
    value: u64,
}

impl WithCell {
    fn evil(&self) {
        unsafe { *addr_of!(self.value).cast_mut() = 0 };
    }
}

fn main() {
    let with_cell = WithCell {
        value: 42,
        _cell: Cell::new(()),
    };
    println!("{}", with_cell.value);
    with_cell.evil();
    println!("{}", with_cell.value);
}
1 Like

It seems like things that take pinned references like Future::poll implicitly get a safety requirement along these lines:

Every Pin<&mut T> passed to a pinned method must have the same tag and must remain valid until the destructor runs.

Since otherwise the self-referential object might be keeping around pointers with old invalidated tags.


Now, since mutable references only create new tags when the type is Unpin, the above is normally fine. However, if we create a struct that is unconditionally Unpin and store a future inside it (like happened with poll_fn), then it is very easy to end up violating the above safety requirement for pinning.

I suggest that the condition for when mutable references create new tags should be expanded so that it ignores impl Unpin and just looks whether any field is !Unpin recursively.

4 Likes

(I've been planning to bring a write-up/proposal with a suggestion to introduce a separate FreezeMut unsafe autotrait for the aliasing semantics currently attached to Unpin, like is currently the case with Freeze for UnsafeCell. But finding the time to finish the write-up has been difficult.)

4 Likes

Here is some examples showing closures are very different. I have no idea how compiler treat them so that tb's behavior becomes very confusing.

use std::ptr::addr_of;

fn pass() {
    let a = 0;
    unsafe {
        *addr_of!(a).cast_mut() = 5;
    }
}

fn rejected() {
    let a = 0;
    let f = move || unsafe {
        *addr_of!(a).cast_mut() = 5; // UB!
    };
    f();
}

fn main() {
    pass();
    rejected();
}

But if the closure is boxed and returned immediately tb would calm on some occasions:

use std::ptr::addr_of;
// Works for Box<dyn FnOnce()->()> too
// However impl Fn/FnMut/FnOnce and Box<dyn FnMut> will make it rejected
fn pass() -> Box<dyn FnMut() -> ()> {
    let a = 0;
    Box::new(move || unsafe {
        *addr_of!(a).cast_mut() = 5;
    })
}

fn rejected() -> Box<dyn FnMut() -> ()> {
    let a = 0;
    // An intermediate variable annoys TB
    let f = Box::new(move || unsafe {
        *addr_of!(a).cast_mut() = 5;  // UB!
    });
    f
}

fn main() {
    pass()();
    rejected()();
}

1 Like

Yes. FWIW this is also basically the case in Stacked Borrows, except it doesn't have to be literally the same tag, it can just be a tag in the "same SharedReadWrite group" -- TB just collapses that entire group into a single tag.

Wouldn't that just slightly move the issue? The issue you are describing is basically what happened with poll_fn, which did show that impl Unpin is quite dangerous indeed.

Related discussion: UnsafeCellMut.

Confusing behavior indeed. To understand what happens I modified your code a bit to

use std::ptr::addr_of;

#[path = "../../../tests/utils/mod.rs"]
mod utils;
use utils::macros::*;

unsafe fn pass() {
    let a = 0;
    name!(addr_of!(a));
    print_state!(alloc_id!(addr_of!(a))); // (1)
    let raw = addr_of!(a).cast_mut();
    print_state!(alloc_id!(raw)); // (2)
    name!(raw);
    let f = || {
        print_state!(alloc_id!(raw)); // (3)
        *raw = 5;
    };
    f();
}

unsafe fn rejected() {
    let a = 0;
    name!(addr_of!(a));
    print_state!(alloc_id!(addr_of!(a))); // (1)
    let f = move || {
        let raw = addr_of!(a).cast_mut();
        print_state!(alloc_id!(raw)); // (2)
        name!(raw);
        print_state!(alloc_id!(raw)); // (3)
        *raw = 5; // UB!
    };
    f();
}

fn main() {
    unsafe {
        pass();
        rejected();
    }
}

Which prints the following trees

// Trees for `pass`
// (1)
────────────────────────────────────────────────────────────────
0..  4
| Act|    └────<2793=root of the allocation, addr_of!(a)>
────────────────────────────────────────────────────────────────
// (2)
────────────────────────────────────────────────────────────────
0..  4
| Act|    └────<2793=root of the allocation, addr_of!(a)>
────────────────────────────────────────────────────────────────
// (3)
────────────────────────────────────────────────────────────────
0..  4
| Act|    └────<2793=root of the allocation, addr_of!(a), raw>
────────────────────────────────────────────────────────────────


// Trees for `rejected`
// (1)
────────────────────────────────────────────────────────────────
0..  4
| Act|    └────<2826=root of the allocation, addr_of!(a)>
────────────────────────────────────────────────────────────────
// (2)
────────────────────────────────────────────────────────────────
0..  4
| Act|    └────<2830=root of the allocation>
────────────────────────────────────────────────────────────────
// (3)
────────────────────────────────────────────────────────────────
0..  4
| Act|    └─┬──<2830=root of the allocation>
| Frz|      └────<2832=raw> Strongly protected
────────────────────────────────────────────────────────────────

The relevant diff between these two is that

  • in rejected, a gets reallocated (it changes tag from 2926 to 2830 between (1) and (2)
  • the above explains the disappearance of addr_of!(a) from the allocation
  • having been reallocated, a is no longer a local variable

This is a very debatable choice, but it happens that TB always gives the Active permission to the root of the allocation, so it makes no fundamental difference between let x = 0 and let mut x = 0.

I agree that it just moves the issue, but I think it moves it more than slightly.

Let's define self-referential type recursively by saying that a type is self-referential if it is !Unpin, or if it has a self-referential field. Then, my proposed rule is that creating a mutable reference only creates a new tag if the type is not self-referential.

I claim that it makes triggering the issue a lot more difficult. For example, the poll_fn situation would not have happened because PollFn has a field that is !Unpin, so the PollFn struct itself would also be considered self-referential.

To see why, consider operations that take a &mut T and create a &mut U into the same part of the same allocation. In safe code, this mainly encompasses reborrows and creating references to fields of T, but also a few others like coercing from a sized type to an unsized one. As far as I can tell, all of these have the property that if U is self-referential, then so is T.

However, creating two mutable references to the same thing (they don't necessarily have to exist simultaneously) with different tags can only be done given a mutable reference to something that isn't self-referential. Hence, to create two mutable references to the same self-referential value with different tags, you must at some point convert from &mut T to &mut U with T non-self-referential and U self-referential. That can only be done unsafely, and I think it's a quite rare unsafe operation especially in the context of futures.

So in some sense, my suggestion changes the dangerous thing from impl Unpin to "convert non-self-referential reference to self-referential reference".

I think basically you are trying to reconstruct what we have with UnsafeCell (where impl Freeze is not possible since the trait is unstable). If we think that is desirable, I'd much rather have a type that plays the same role for mutable reference aliasing, as in what I proposed here.

1 Like

Sure, an UnsafeCellMut would work for me too.