Tree Borrows: Two-phase borrows + interior mutability have surprising interactions

[RalfJung]

Consider this function:

pub fn f(xr : &mut Cell<i32>) -> i32 {
    *xr = Cell::new(-1);
    shouldnt_escape(&mut *xr);
    *xr = Cell::new(1337); // the write should invalidate all children
    do_something();
    xr.get() // ...so the compiler should be able to optimize
             // this to return 1337
}

If this was an &mut i32 reference, then the *xr = ... assignment would invalidate all child references and hence we could rely on do_something not being able to use anything derived from the reference passed to shouldnt_escape.

But it turns out under current Tree Borrows rules, that optimization would be wrong, as demonstrated by this example (due to @JoJoDeveloping).

The reason this works is that two-phase mutable references to !Freeze types in their reservation stage accept foreign write accesses. This is necessary to make code like this (entirely safe code!) not UB.

This is probably undesirable. But I am not sure what the best way is to make the safe code example allowed but make the counterexample for the optimization above have UB.

[RalfJung]

Cc @comex, this is inspired by your example here

[RalfJung]

Another way to put this is to say that actually, UnsafeCell does make a difference below mutable references -- specifically during the reservation phase of a two-phase borrows, UnsafeCell determines whether mutation through other pointers is allowed.

[chorman0773]

Could we say that creating a protected tag via a &mut T simultaneously activates it? That should make *cr = Cell::new(1337); invalidate the &mut *cr passed into the function, because it would be active and not reserved.

Although this won't help if we make shouldnt_escape take a raw pointer.

[RalfJung]

IIRC a bunch of things break in TB if we have tags that are activated without an associated write event. @Vanille-N might remember the details of that as I forgot...

We could make function calls implicit writes for &mut, but not doing that was one of the key innovations of Tree Borrows -- these writes would bring back a bunch of UB we want to avoid.

[RalfJung]

Although this won't help if we make shouldnt_escape take a raw pointer.

That's okay. If you hand out a raw pointer, you don't get any free aliasing model optimizations -- that's how it should be.

[Vanille-N]

If we allow activated tags without write events it breaks a lot of things indeed.

In particular if we make that possible then

• when you have an Active you can no longer assume that you're allowed to write through it (because you didn't kill cousin Frozens that might still be there -- possibly protected -- and won't appreciate a spurious write)
• when you have a Frozen you can no longer assume that you're allowed to read through it (because there might have been an Active created in the meantime -- also possibly protected -- that didn't invalidate your pointer upon creation)

It should come to no surprise that these two assumptions are quite important.

Compared to SB, Tree Borrows stops requiring implicit write on creation of &mut precisely because &mut doesn't start Active. If it did then we would have to.

[JoJoDeveloping]

The difference between this examples and the safe code "motivating example" for the weird behavior of interior mutable &mut references is that:

• in the example above, the conflicting use of the reference happens after the call to shouldnt_escape, but
• normally (and in safe code), the conflicting use of the reference happens before the call to shouldnt_escape (or do_the_thing) in the motivating example.

So maybe we should somehow have it that when a protector on an item ends (i.e. the function into which it was passed as an argument returns), it also sets all Reserved InteriorMut permissions in this item to Reserved TyFreeze, to forbid further conflicting writes?

But since there are two reborrows at play here (one inside the function, and one outside it in the parent function), you might also want to have a MIR EndTwoPhaseBorrow instruction that does the same operation as above on the reborrow "outside" (in the parent function where the two-phased borrow is created). That would also be sufficient, and easier to reason about. But it would also mean that the semantics now depends on where the borrow checker places those instructions during its inference, but this should be pretty predictable (always right after the function returns).

[RalfJung]

Usually in SB and TB, we use conflicting memory accesses rather than static instructions to determine when borrows end. Intuitively, the two-phase ends when there is a write to the mutable reference. So ideally what would happen is that the Reserved mutable reference accepts foreign writes to interior mutable shared references, but not foreign writes to mutable references. Not sure if that's possible though? It would be a bit like saying we actually have two kinds of writes (statically annotated in the source, presumably), exclusive writes and non-exclusive writes, and writing to an &mut generates an exclusive write. Then the "reserved interior mutable" would have a self-loop transition for non-exclusive foreign writes but would transition to Disabled for exclusive foreign writes.

[chorman0773]

If we allow activated tags without write events it breaks a lot of things indeed.

FTR, by "activating new protecting tags" I was indeed suggesting an implicit write event. I'm hoping that by limiting it to protected tags, it wouldn't create too much extra UB. It seems like it would allow the aforementioned optimization (I also would like it for additional reasons, as it will make the relaxed version of the model saner to define)

[RalfJung]

FTR, by "activating new protecting tags" I was indeed suggesting an implicit write event. I'm hoping that by limiting it to protected tags, it wouldn't create too much extra UB.

It would break code like this, which is code that we explicitly wanted to allow with TB:

fn foo(x: &mut [i32]) {
  let ptr1 = x.as_ptr();
  let ptr2 = x.as_mut_ptr(); // implicit write invalidates `ptr1`
  ptr2.copy_from(ptr1.add(16), 16);
}

[chorman0773]

TBH, <[T]>::as_mut_ptr() seems to cause a lot of UB anyways that should be fixed by taking a *mut Self reciever instead of &mut Self. Likewise <[T]>::as_ptr(). The implicit read of the &self receiver presumably poses similar issues.

[RalfJung]

Tree Borrows makes implicit reads very harmless. That's one of the key advantages it has over SB.

[JoJoDeveloping]

Turns out that this example is affected rust-lang/miri#3742. Now, the "leaking" of the Reserved InteriorMut can no longer happen in another function (here: shouldnt_escape) because there it becomes Reserved TyFrz. Instead, the "leaking" has to happen within that function, where it could be tracked locally.

[RalfJung]

if I write shouldnt_escape with custom MIR to manually control where Retags occur, the example still works, doesn't it? IOW the defense you are proposing relies on the assumption that the callee will make an FnEntry retag? Or did I misunderstand something?

[JoJoDeveloping]

Yes, it relies on the other functions doing the proper retag.