Help with miri error?

help
1

I'm getting a new error running miri on tinyset, which used to pass on an older nightly. Sadly, the error explanation is incomprehensible to me, so I can't see how to fix it.

error: Undefined Behavior: trying to retag from <908696> for Unique permission at alloc335826[0x10], but that tag does not exist in the borrow stack for this location
    --> /home/droundy/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/raw.rs:141:9
     |
141  |         &mut *ptr::slice_from_raw_parts_mut(data, len)
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     |         |
     |         trying to retag from <908696> for Unique permission at alloc335826[0x10], but that tag does not exist in the borrow stack for this location
     |         this error occurs as part of retag at alloc335826[0xc..0x48]
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows 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
help: <908696> was created by a SharedReadWrite retag at offsets [0xc..0x10]
    --> src/setu32.rs:1546:57
     |
1546 |                 unsafe { std::slice::from_raw_parts_mut(&mut s.array as *mut u32, b.cap as usize) };

Here is the error on CI, and if you want to reproduce it yourself, you can just run

cargo +nightly miri test check_sets

The relevant code is:

    fn internal_mut<'a>(&'a mut self) -> InternalMut<'a> {
        if self.0 as usize == 0 {
            InternalMut::Empty
        } else if self.0 as usize & 3 != 0 {
            InternalMut::Stack(Tiny::from_usize(self.0 as usize))
        } else {
            let s = unsafe { &mut *self.0 };
            let b = &mut s.b;
            let a =
                unsafe { std::slice::from_raw_parts_mut(&mut s.array as *mut u32, b.cap as usize) };
            if b.bits == 0 || b.bits > 32 {
                InternalMut::Big { s: b, a }
            } else if b.bits == 32 {
                InternalMut::Dense { sz: &mut b.sz, a }
            } else {
                InternalMut::Heap { s: b, a }
            }
        }
    }

Can anyone help by explaining what this error might mean, or how one might fix it?

2

Edit: Err, I just noticed it fails an assertion now, so this is quite likely irrelevant; sorry.

Anyway...

If I replace 0 as *mut _ with core::ptr::null_mut() and comment out this line:

    pub fn insert(&mut self, e: u32) -> bool {
        match self.internal_mut() {
            InternalMut::Empty => {
                if let Some(t) = Tiny::from_singleton(e) {
//                    *self = SetU32(t.to_usize() as *mut S);

Then miri stops complaining. (Various other changes were made to make it playground friendly, perhaps relevantly the removal of rand32() calls.)

That's where I stopped digging though.

3

I am very much out of my depth here but I think the problem is in the trick you're using to avoid needing a usize pointer for your allocated storage inside S

You allocate a chunk of memory, and then cast the pointer to S where S is

#[repr(C)]
#[derive(Debug)]
struct S {
    b: Sbeginning,
    array: u32,
}

array is effectively an unsized type[1]. You take a reference to array and then reinterpret it as the first element of a slice. But the reference you take to array only has "permission" to access that first element under Stacked Borrows[2], so miri complains.

I did some wacky pointer math to jump the original pointer to the right place in the allocation instead of converting &mut s.array to a slice, and that seems to have worked? It certainly isn't pretty though.

fn internal_mut<'a>(&'a mut self) -> InternalMut<'a> {
    if self.0 as usize == 0 {
        InternalMut::Empty
    } else if self.0 as usize & 3 != 0 {
        InternalMut::Stack(Tiny::from_usize(self.0 as usize))
    } else {
        let s = unsafe { &mut *self.0 };
        let b = &mut s.b;
        let array = unsafe {
            // Use the calculated offset to jump the pointer to where the array starts directly, keeping the permissions for the whole allocation intact.
            // Note: This doesn't cast the final pointer to `u32`, that still happens below.
            self.0.cast::<u8>().offset(
                // get a raw pointer to the array field
                (&mut s.array as *mut u32)
                    // cast it to bytes so we can do math on the two pointers
                    .cast::<u8>()
                    // calculate the offset from `*mut S` to the array field
                    .offset_from(self.0.cast()),
            )
        };
        let a = unsafe { std::slice::from_raw_parts_mut(array as *mut u32, b.cap as usize) };
        if b.bits == 0 || b.bits > 32 {
            InternalMut::Big { s: b, a }
        } else if b.bits == 32 {
            InternalMut::Dense { sz: &mut b.sz, a }
        } else {
            InternalMut::Heap { s: b, a }
        }
    }
}

I made basically the same change on the non-mut version of that method too.

It would definitely be nice if that error message was nicer though.

  1. When using the "big" variant, which appears to be where the failures start ↩︎

  2. I think??? ↩︎

4 Likes
4

Thanks for figuring that out. But is it actually safer or sounder? Wacky pointer arithmetic is one of the things that I'd rather avoid, if possible. On the other hand, it is only in two functions (per set type), which reasonably well encapsulate the unsafe...

Actually, your pointer arithmetic isn't that wacky. It's just the conversions to u8 that make it look bad, and those conversions aren't needed.

1 Like
5

Oh yeah to be clear I am absolutely sure there are better ways to do that pointer math, I don't do that kind of thing very often in Rust.

Is it more safe this way? Ehhh. Stacked borrows is an experiment at the moment, it isn't an official memory model for Rust. If stacked borrows are adopted as-is then your code would technically be unsound. That being said, I don't really think what you were doing is violating the primary principles stacked borrows are intended to enforce. [1]

I would probably open an issue asking whether this should be allowed, or if there's a better way to do this pattern that doesn't violate the current rules.

  1. but like I said I am not an expert on stacked borrows ↩︎

6

The arithmetic can be simplified using the std::mem::addr_of! macro.

7

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.