Help me understand this UB with stacked borrows detected by `miri`

I am posting this here, but here might actually be a better place, if i should post it there, please let me know.

I am trying to solve a bigger problem in a library, but i managed to reduce it to this:

use core::{
    cell::UnsafeCell,
    mem::ManuallyDrop,
    pin::Pin,
    ptr::{addr_of, null},
};

/// self referential struct, but because buf is never accessed through a `&` or `&mut`, only
/// `*mut`, this aliasing should be allowed, right?
struct PtrBuf<T, const N: usize> {
    ptr: *const T,
    // need to only drop elements if they are not read (not implemented)
    buf: UnsafeCell<[ManuallyDrop<T>; N]>,
}

impl<T, const N: usize> PtrBuf<T, N> {
    /// only call once
    unsafe fn init(self: Pin<&mut Self>) {
        let this = Pin::into_inner_unchecked(self);
        this.ptr = this.buf.get() as *const _ as *const T;
    }

    /// only call after init
    unsafe fn next(self: Pin<&mut Self>) -> Option<T> {
        // we only structually pin the location of buf, but each element of buf is not pinned
        let this = Pin::into_inner_unchecked(self);
        // check if we are still inside of the buf
        if this.ptr <= addr_of!((*this.buf.get())[N - 1]) as *const T {
            let val = this.ptr.read();
            // ptr is valid and the offset is going at most one byte further than buf.
            this.ptr = this.ptr.offset(1);
            Some(val)
        } else {
            None
        }
    }
}

fn main() {
    let buf = PtrBuf {
        ptr: null(),
        buf: UnsafeCell::new([ManuallyDrop::new(0), ManuallyDrop::new(42)]),
    };
    let mut buf = Box::pin(buf);
    unsafe {
        buf.as_mut().init();
        assert_eq!(buf.as_mut().next(), Some(0));
        assert_eq!(buf.as_mut().next(), Some(42));
        assert_eq!(buf.as_mut().next(), None);
    }
}

When running this program under miri the following error shows up:

error: Undefined Behavior: attempting a read access using <2605> at alloc1319[0x8], but that tag does not exist in the borrow stack for this location
    --> ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:1096:9
     |
1096 |         copy_nonoverlapping(src, tmp.as_mut_ptr(), 1);
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     |         |
     |         attempting a read access using <2605> at alloc1319[0x8], but that tag does not exist in the borrow stack for this location
     |         this error occurs as part of an access at alloc1319[0x8..0xc]
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
     = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
             
     = note: inside `std::ptr::read::<i32>` at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:1096:9
     = note: inside `std::ptr::const_ptr::<impl *const i32>::read` at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/const_ptr.rs:941:18
note: inside `PtrBuf::<i32, 2_usize>::next` at src/main.rs:29:23
    --> src/main.rs:29:23
     |
29   |             let val = this.ptr.read();
     |                       ^^^^^^^^^^^^^^^
note: inside `main` at src/main.rs:47:20
    --> src/main.rs:47:20
     |
47   |         assert_eq!(buf.as_mut().next(), Some(0));
     |                    ^^^^^^^^^^^^^^^^^^^

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

error: aborting due to previous error

The -Zmiri-track-pointer-tag=2605 reveals that <2605> is popped due to writing to <2576>:

note: tracking was triggered
    --> ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/cell.rs:1911:9
     |
1911 |         self as *const UnsafeCell<T> as *const T as *mut T
     |         ^^^^ created tag 2605
     |
     = note: inside `std::cell::UnsafeCell::<[std::mem::ManuallyDrop<i32>; 2]>::get` at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/cell.rs:1911:9
note: inside `PtrBuf::<i32, 2_usize>::init` at src/main.rs:20:20
    --> src/main.rs:20:20
     |
20   |         this.ptr = this.buf.get() as *const _ as *const T;
     |                    ^^^^^^^^^^^^^^
note: inside `main` at src/main.rs:46:9
    --> src/main.rs:46:9
     |
46   |         buf.as_mut().init();
     |         ^^^^^^^^^^^^^^^^^^^

note: tracking was triggered
    --> ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:1789:9
     |
1789 |         &mut **self
     |         ^^^^^^^^^^^ popped tracked tag for item [SharedReadWrite for <2605>] due to Write access for <2576>
     |
     = note: inside `<std::boxed::Box<PtrBuf<i32, 2_usize>> as std::ops::DerefMut>::deref_mut` at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:1789:9
     = note: inside `std::pin::Pin::<std::boxed::Box<PtrBuf<i32, 2_usize>>>::as_mut` at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/pin.rs:650:42
note: inside `main` at src/main.rs:47:20
    --> src/main.rs:47:20
     |
47   |         assert_eq!(buf.as_mut().next(), Some(0));
     |                    ^^^^^^^^^^^^

And this contradicts my understanding of UnsafeCell: "i have a &mut PtrBuf" does not entail, that the data in buf is not aliased.

cc @RalfJung I can't quickly figure out what is wrong with the code.

In this case, I think you misunderstood what UnsafeCell is for. The documentation explicitly states this:

So reading from ptr while you are holding a &mut PtrBuf is indeed disallowed.

That said, the error message doesn't seem to be about mutable aliasing, so something else is also wrong.

2 Likes

I think you need something like the Aliasable<T> type that the pinned-aliasable crate provides. That crate has a good explanation for why the type is needed but I don't think it would make the code pass miri since such a type really needs support by the compiler and language to guarantee that the code will be sound in the future.

The reddit announcement of that crate has a comment that links to a Rust issue discussing the problem, which among other things has a link to intrusive.md that explains how this issue affects tokio.

1 Like

Thank you for getting me to re-read the UnsafeCell documentation, it also states:

Note that whilst mutating the contents of an &UnsafeCell (even while other &UnsafeCell references alias the cell) is ok (provided you enforce the above invariants some other way), it is still undefined behavior to have multiple &mut UnsafeCell aliases. That is, UnsafeCell is a wrapper designed to have a special interaction with shared accesses (i.e., through an &UnsafeCell<_> reference); there is no magic whatsoever when dealing with exclusive accesses (e.g., through an &mut UnsafeCell<_>): neither the cell nor the wrapped value may be aliased for the duration of that &mut borrow. This is showcased by the .get_mut() accessor, which is a safe getter that yields a &mut T.

The important bit: neither the cell nor the wrapped value may be aliased for the duration of that &mut borrow. So the above code does not use UnsafeCell<T> soundly.

buf.ptr is derived from the reference created in buf.as_mut().init(). When you call buf.as_mut() again, the new Pin<&mut Self> reference invalidates the previous reference, and by extension invalidates buf.ptr.

1 Like

Author of intrusive.md here. Basically all self-referential structs are unsound under stacked borrows if you give the user ownership of the struct. You're seeing an example of that.

You can make your structs !Unpin to make miri shut up, but it's only a temporary measure.

6 Likes

Interesting crate, i looked briefly at the source code for the Aliasable struct and found, that it just is !Unpin through the PhantomPinned marker, then i added that to PtrBuf and miri stops complaining. I find this behavior very strange, why does !Unpin inhibit noalias? Is this still UB (because of the UnsafeCell doc) or just not yet finalized compiler behaviour?

I saw the tracking issue, but only glanced over it, and intrusive.md is a nice resource!

was writing my previous answer befor reading your comment.

Interesting, what is the reason for miri to not care about aliasing !Unpin?
I maybe did not read enough of the tracking issue, but what are the blockers for adding Aliasable/UnsafeAliasCell/UnsafeAlias to the stdlib?

It's not actually clear how they would work internally in the compiler. You would probably have to find a memory model that supports them to do that, and I don't think there are even any proposals for that.

Note that stacked borrows is not Rust's memory model. It's a proposal for what the memory model could be, but the issue with async/await being unsound probably means it wont be the one they choose in the end.

As for why miri does not care about aliasing !Unpin, it's to make it possible to test code that uses it with miri. Before that change, lots of things would trigger miri errors with Tokio, whereas now I'm not aware of any ways to trigger it.

2 Likes

Ah ok makes sense. Does rust at the moment even have a memory model? I found this still open issue which at the end links to the UCG repo, while the UCG are a helpful tool to write unsafe code, i do not view it as a memory model spec.

iirc *mut T and *const T are allowed to alias and miri already has a hack to allow T: !Unpin to alias, so adding an unstable type that provides the same for T should be very similar to this hack. Why is this not as simple as i make it out to be?
UnsafeAlias<T> would only allow one to get a *mut T and the caller would be responsible to never cast it to &mut T while it is aliased.

No, Rust does not have a full memory model, though there have been lots of discussion on the area lately with the strict provenance stuff.

As for why it's non-trivial, for example, consider if you have a !Unpin struct with a field of type String. Maybe you want to call push_str on the string. But that involves creating a &mut String to the field, but that reference is to an Unpin field. How does that interact with mutable references to the entire struct?

2 Likes

Oh right, that makes it more difficult... But still manageable, if you only use raw pointers:

If the String is aliased (or equivalently the surrounding struct), then it would be unsound to create a &mut String in the first place. Handling mutable aliased memory is only possible using *mut, so when we have this struct:

struct Data {
    msg: UnsafeAliasCell<String>,
    ptr: *const String,
}

then it is unsound to turn the *mut String returned from UnsafeAliasCell::get(&msg) into &mut String, becaues it is aliased by ptr. The aliased type would need explicit support for operations on aliased data, so for the String example:

impl String {
    // only hypothetical, i do not know if String could do this without refs
    /// # Safety
    /// - this is a valid pointer to a valid `String`
    /// - this is not mutated at the same time
    pub unsafe fn push_str_aliased(this: *mut Self, string: &str) {
        // append the given str using only raw pointers
    }
}

You also wouldnt be able to call push_str_aliased(msg.get(), msg), because you cannot get a reference to the data behind the UnsafeAliasCell<T>. This would allow these functions to still assume, that the data they are receiving is unique.

I am probably missing something here, but was not able to find an example that would work now (using !Unpin to allow aliasing in miri) and not work when using UnsafeAliasCell<T>.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.