Stacked Borrows: Incompatibilities with LLVM noalias

[RalfJung]

There are programs that are accepted by Stacked Borrows and conflict with LLVM noalias. @arielb1 had the following example in this long discussion on Zulip:

let x: &mut u32 = a;
let raw_ptr: *const u32 = x;
foo(x, raw_ptr);

fn foo(x: &mut u32, raw_ptr: *const u32) -> u32 {
    let x = &mut *x; // stack is now [..., Uniq(N)]
    *x = 5;
    let y = &*x; // stack is now [..., Uniq(N), Shr]

    // this is OK according to stacked borrows because of the Shr tag, but is UB
    // according to LLVM noalias and would be hard to make non-UB.
    unsafe { *raw_ptr }
}

On a high level, the problem is that create a raw reference is like a "broadcast" that lets every raw pointer now access this location, whereas LLVM only lets newly created raw pointers be used for that.

[arielb1]

That example is straight #87 - we do want to do be able to delay the write to x in real life. The real problem with noalias is that it brings along with it LLVM provenance tracking:

unsafe fn foo(x: &mut u32, raw_ptr: *const u32) -> u32 {
    let x: *mut u32 = &mut *x; // stack is now [..., Uniq(N), Shr]

    *x = 5; // access a raw pointer, OK because of the Shr.

    // this is OK according to stacked borrows because of the Shr tag, but is UB
    // according to LLVM noalias and would be hard to make non-UB.
    unsafe { *raw_ptr }
}

LLVM provenance tracking is unsound around int->ptr casts and the like and not well-defined in any case, so bringing it along is harmful.

[RalfJung]

@arielb1 the example in my first post here is basically a duplicate of #87. That issue is resolved by rust-lang/miri#695: the following is now UB.

fn main() { unsafe {
    let x = &mut 0;
    let raw = x as *mut _;
    let x = &mut *x; // kill `raw`
    let _y = &*x; // this should not activate `raw` again
    let _val = *raw; //~ ERROR
} }

However, I assume other incompatibilities with LLVM remain, so I'll keep this open. There'll be a blog post on this new Stacked Borrows soon; it'd be great if you could then try to help find new incompatibilities with LLVM @arielb1.

[RalfJung]

@comex came up with an example of UB that Miri does not catch, based on Stacked Borrows not tracking raw pointers currently.

See here for why we currently cannot do this more precise tracking: We'd have to fix Rc, but the fix is not expressible without something like &raw.

[RalfJung]

Since rust-lang/miri#872, retagging is "shallow" in the sense that only "bare" references are retagged and can be used for reasoning. So, things like Pin<&mut T> would actually not be treated like a reference.

This is in contrast to how we compile (with -Zmutable-noalias), where we do add noalias for newtypes around references.

[comex]

Hmm... that might be a good idea for now, but it doesn't seem like a good long-term approach to me, as it implies that single-field structs would no longer be zero-overhead abstractions.

[RalfJung]

Yeah. We probably want this for some but not all newtypes.

[eddyb]

Pin is a lang item and definitely subject to special-casing.
In a sense, Box<T> is currently just a *mut T newtype special-cased to noalias.
It would be trivial to do something similar for Pin, but in the opposite direction.

[RalfJung]

We also need the "opt-out of noalias" for Ref, RefMut and vec_deque::Drain though -- and maybe more.

[gnzlbg]

We also need the "opt-out of noalias" for Ref, RefMut and vec_deque::Drain though -- and maybe more.

These types aren't really special, and fixing these is a PR from libstd away. I'd be more comfortable with such PRs if miri were actually able to detect these issues if we were to commit test cases that trigger them. Is this possible?

[RalfJung]

Miri used to be able to detect them and I removed that for several reasons -- the main one being that I thought surely Stacked Borrows is too strict here, and we should fix the model instead of complaining about legitimate code. I could certainly bring that back (would require reverting a rustc PR and a Miri PR).

Would be interesting to get a lang team opinion on that -- rust-lang/rust#63787 is probably the better place for that discussion, though.

[RalfJung]

Miri now tags raw references by default, and the new -Zmiri-retag-fields flag re-enables recursive retagging. I think this means that with that flag Stacked Borrows is actually sound wrt our LLVM attributes, finally! (The main caveat is around int2ptr casts, where Miri has to start approximating things, and LLVM doesn't give us a sufficiently precise spec.)

[JakobDegen]

Closing as having been fixed by more recent versions of SB and by TB