Stacked Borrows: asserting uniqueness too early? Should we allow the optimizer to add spurious stores?

[RalfJung]

We have seen a few cases in libstd where the rule that just creating a mutable reference already asserts uniqueness is a problem:

• VecDeque creating overlapping mutable references.
• BTreeMap creating mutable references that overlap with shared references.
• LinkedList creating overlapping mutable references.
• Vec::push invalidating existing references into the vector. The typed-arena crate ran into the same problem.
• shepmaster asking on Zulip why some code doesn't work.
• We have a huge problem with self-referential generators, see Stacked Borrows: asserting uniqueness too early? Should we allow the optimizer to add spurious stores? #133.
• Illegal aliasing of mutable references bodil/sized-chunks#8 would likely also not be an issue if we could delay uniqueness for long enough.
• Some uses of ptr::replace are forbidden even though they should probably be allowed.

In some cases, even just creating a shared ref is an issue, as it conflicts with a recently created mutable ref:

• miri:error printing the return value of align_to_mut rust#68549
• Miri failure in btree::map::test_iter_min_max test rust#73915

So maybe we assert uniqueness to aggressively here? Maybe mutable references should only become unique on first write, or so? I am not sure what that would look like though. (In principle this could also happen with shared references but I have not seen that.)

I'll use this issue to collect such cases.

However, there are also cases where people want the extra UB to get more optimizations:

• Missed Optimization: Inefficient Handling of Mutable Reference in Simple Conditional Assignment rust#124346
• Unnecessary copy when constructing arrays from returned arrays? rust#62446

[RalfJung]

Another related case: rust-lang/rust#62553; calling mem::forget asserts uniqueness and invalidates the pointer that we actually care about.

[retep998]

This is my opinion based on experience with unsafe code and FFI:

While mutable references should assert that the data is otherwise immutable, I believe that the assertion of uniqueness should only apply to references. It is far too common of an assumption that raw pointers are not invalidated by a mutable reference existing, and that it is sufficient to merely hold off on reading or writing through raw pointers until the mutable reference ceases to exist. At the moment you dereference a raw pointer immutably no other mutable references should exist, and at the moment you dereference a raw pointer mutably no other references should exist at all, but a raw pointer should not be invalidated by mutable references.

[RalfJung]

the assertion of uniqueness should only apply to references

It does only apply to references.

if you have a reference and a raw pointer working on the same thing, the reference is not unique. It's not the raw pointer that is causing issues here, it is the reference.

a raw pointer should not be invalidated by mutable references.

It would help if you could give a concrete self-contained example of something that is UB according to current Stacked Borrows, but which you think should be allowed.

Is it something like this:

fn main() {
    let mut local = 0;
    let raw = &mut local as *mut i32;
    
    let mut_ref = &mut local;
    *mut_ref = 13;
    
    let _val = unsafe { *raw }; // UB (as of Stacked Borrows 2.1).
}

[retep998]

fn main() {
    let mut x = 0;
    let y = &mut x as *mut _;
    { let _z = &mut x; }
    unsafe { *y = 10; }
}

When run through miri:

error[E0080]: Miri evaluation error: no item granting write access to tag <untagged> found in borrow stack
 --> src/main.rs:5:14
  |
5 |     unsafe { *y = 10; }
  |              ^^^^^^^ Miri evaluation error: no item granting write access to tag <untagged> found in borrow stack
  |
  = note: inside call to `main` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:64:34
  = note: inside call to closure at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:53
  = note: inside call to closure at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:296:40
  = note: inside call to `std::panicking::try::do_call::<[closure@DefId(1:5891 ~ std[82ff]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:292:5
  = note: inside call to `std::panicking::try::<i32, [closure@DefId(1:5891 ~ std[82ff]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe]>` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panic.rs:394:9
  = note: inside call to `std::panic::catch_unwind::<[closure@DefId(1:5891 ~ std[82ff]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:25
  = note: inside call to `std::rt::lang_start_internal` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:64:5
  = note: inside call to `std::rt::lang_start::<()>`

error: aborting due to previous error

I was led to believe that this error is by design due to stacked borrows. If it is just an issue with miri that will get fixed and this code example is actually fine then I would be so happy.

[RalfJung]

@retep998 Right, so that is an example involving an unused mutable references. This is definitely forbidden by the current Stacked Borrows (it is not "just" a Miri implementation issue), but I could imagine something like "Tree-shaped borrows" that would open a design space to allow more things here. However, it is unclear how much that would cost in terms of lost optimizations. This issue is about collecting cases where unused mutable references caused UB. ("used"/"unused" is a fuzzy term here, but if the variable is dead immediately after it got created, like in your last example, that's definitely "unused".)

What I am wondering about is how you feel about used mutable references interacting with raw pointers, like in my example above.

[retep998]

In your example above the used mutable reference still exists when the raw pointer is accessed, which is shaky ground. If we were to modify my example to actually use the mutable reference...

fn main() {
    let mut x = 0;
    let y = &mut x as *mut _;
    {
        let z = &mut x;
        *z = 20;
    }
    unsafe { *y = 10; }
}

then I would still want it to be okay and not UB. Raw pointers should not care if something else mutated the value in the time between accesses.

[taralx]

So if I understand correctly, miri invalidates other children of x when &mut x is created. Is it possible to simply hold the raw children in abeyance, like one does with x itself? It is a bit surprising that creating z from y is ok, but creating z from x (which we know is the same as y) is not.

[comex]

@retep998 By itself your example is pretty harmless, but it's also useless in that nothing uses the stored value of 10. On the other hand, if we add a use of x...

fn main() {
    let mut x = 0;
    let y = &mut x as *mut _;
    {
        let z = &mut x;
        *z = 20;
    }
    unsafe { *y = 10; }
    println!("{}", x);
}

Then we have a problem, because what if the raw pointer stuff is hidden behind function calls?

fn foo(x: &mut i32){
    some_global = x as *mut _;
}

fn bar() {
    unsafe { *some_global = 10; }
}

fn main() {
    let mut x = 0;
    foo(&mut x);
    {
        let z = &mut x;
        *z = 20;
    }
    bar();
    println!("{}", x);
}

(Note that in reality foo and bar might be trait object methods or from external crates, so the compiler might not be able to inspect their contents.)

Under Stacked Borrows, the compiler can optimize main by changing println!("{}", x); to println!("{}", 20}. If this example is non-UB, it cannot.

In other words, from an implementation perspective, the issue is not how the compiler treats raw pointers, but what assumptions the compiler can make about unknown code.

That said, I agree that this is a footgun. I really wish we had something with miri's level of undefined behavior detection that also worked with FFI, at least to some extent.

[gnzlbg]

I really wish we had something with miri's level of undefined behavior detection that also worked with FFI, at least to some extent.

I don't think we should design things under the assumption that something like this can exist.

[Lokathor]

i think that means that the foo/bar example has to be blindly assumed to always be the sort of case if you pass an address to unknown code, because some code does work that way.

[gnzlbg]

In other words, from an implementation perspective, the issue is not how the compiler treats raw pointers, but what assumptions the compiler can make about unknown code.

While the aliasing model determines which optimizations Rust is allowed to do locally (without whole program analysis), it also determines what assumptions users can make about the behavior of unknown code. Can users reason about the code locally? E.g. if I modify this piece of code, I know I can do this and that, because these unknown functions are not allowed to do x and y without introducing UB. Or do users need to keep the whole program in their head to be able to reason about UB and about how to modify code without introducing UB ?

[RalfJung]

@retep998

In your example above the used mutable reference still exists when the raw pointer is accessed, which is shaky ground.

Now that is interesting. Stacked Borrows was specifically designed to not care about such cases of "existence" because I was sure that would result in a lot of backlash. ;) So I didn't expect some far on the "max freedom for unsafe code" end of the spectrum to consider this a reasonable restriction.
However, there's also the fact that even the borrow checker considers a locally created reference dead when it is definitely not used/copied/reborrowed any more. I don't think the dynamic model should be even more conservative that the borrow checker.

OTOH, references passed as function argument do have special treatment that keeps them "live" throughout the call (and the borrow checker does assume they live for the entire function).

(Btw let me say that I enjoy this exchange a lot, this is the kind of discussion I was hoping to have when I put out my proposals.)

If we were to modify my example to actually use the mutable reference... [...]
then I would still want it to be okay and not UB.

This is where it gets interesting. I consider this equivalent to my example as the only difference is in the scoping of some variables without drop glue.

Thankfully @comex already came up with a great example for why Stacked Borrows makes this example UB -- an example for what kind of optimizations this UB enables. In my view, the entire point of Stacked Borrows is to enable intraprocedural optimization based on alias information, so losing some of those is a big deal.

For the current version of Stacked Borrows, we have formal machine-checked proofs that some optimizations are possible (I'll share this in a blog post eventually). It does not seem obvious that even those optimizations are still possible in a model that permits as many programs as you are asking. But it might be possible. I will have to think about this more.

Raw pointers should not care if something else mutated the value in the time between accesses.

As stated above, the raw pointer does not care. It's the mutable reference that cares enough to make other pointers invalid, in order to enforce its own discipline.

@retep998 while I have your attention, can I probe your intuition another way? What if we change your example to use x directly instead of creating a new mutable reference and writing to that?

fn main() {
    let x = &mut 0; // changed x to also be a reference
    let y = &mut *x as *mut _;
    *x = 20; // instead of `{ let z = &mut *x; *z = 20; }`
    unsafe { *y = 10; }
    println!("{}", *x); // Does removing this change anything?
}

This program I feel very strongly should have UB, because between two uses of x (the write and the read) there is a conflicting access. If we do not make this UB, I think there is very little to nothing that we can optimize based on reference types.

But OTOH, my intuition also says it makes sense to consider *x = 20 and { let z = &mut *x; *z = 20; } as equivalent. At that point we are very close to your example, the only difference being the println! at the end.

So, I am wondering what your thoughts on this are.

@taralx

Is it possible to simply hold the raw children in abeyance, like one does with x itself?

Maybe. Stacked Borrows is but one point in a gigantic design space. But "simply" doesn't exactly describe the situation. ;)

It is a bit surprising that creating z from y is ok, but creating z from x (which we know is the same as y) is not.

However, here I think your intuition needs some refinement. x and y are not the same. The entire point of an aliasing model is to define which of multiple aliasing pointers you are actually allowed to use to do what in which order. That is, even if two pointers point to the same thing, they are not "the same".

This is somewhat unintuitive, but even C does this. Here is some literature: [1], [2], [3].

I don't think we should design things under the assumption that something like this can exist.

I think it could exist. It's just hard.
Stacked Borrows supports untagged pointers specifically for this case: all accesses done by FFI code would be considered as happening with an untagged pointer.

@gnzlbg

E.g. if I modify this piece of code, I know I can do this and that, because these unknown functions are not allowed to do x and y without introducing UB.

I am afraid I don't understand your question. Do you have an example for "this and that"?
Certainly the same local reasoning principles that the compiler uses, can also be used by the programmer.