How do you make miri understand joined allocations?

leddoo · July 24, 2023, 4:20pm

i'm implementing a "path" data structure. path in the vector graphics sense, an array of verbs and an array of points.

the memory layout looks as follows:

struct PathMemory {
    header: PathHeader,
    verbs:  [Verb;  header.num_verbs],
    points: [Point; header.num_points],
}

now, since we obviously can't define such a struct in rust (though it would be nice if we could), this layout is implemented manually using unsafe.

the user primarily interacts with &'a PathHeader (which is exposed under the alias Path).

now to the issue:
i have a method verbs(&self) -> &[Verb] implemented on PathHeader, which, according to miri, triggers undefined behavior. (it just works by offsetting the pointer derived from &self and aligning it. the returned slice contains the correct values.)

the issue seems to be that &self only borrows the bytes of the header, but the verbs are after the header, of course. - if i'm reading this log correctly:

error: Undefined Behavior: trying to retag from <3947> for SharedReadOnly permission at alloc1950
[0x20], but that tag does not exist in the borrow stack for this location
   --> /Users/leddoo/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library
/core/src/slice/raw.rs:100:9
    |
100 |         &*ptr::slice_from_raw_parts(data, len)
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |         |
    |         trying to retag from <3947> for SharedReadOnly permission at alloc1950[0x20], but t
hat tag does not exist in the borrow stack for this location
    |         this error occurs as part of retag at alloc1950[0x20..0x24]
    |
    = 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-borro
ws.md for further information
help: <3947> was created by a SharedReadOnly retag at offsets [0x14..0x44]
   --> /Users/leddoo/dev/rug/rug/src/path.rs:267:41
    |
267 |         let ptr: *const Verb = cat_next(self, size_of::<Self>());
    |                                         ^^^^
    = note: BACKTRACE (of the first span):
    = note: inside `std::slice::from_raw_parts::<'_, rug::path::Verb>` at /Users/leddoo/.rustup/t
oolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/slice/raw.rs:100:9: 
100:47
note: inside `rug::path::PathData::verbs`
   --> /Users/leddoo/dev/rug/rug/src/path.rs:268:9
    |
268 |         core::slice::from_raw_parts(ptr, self.num_verbs as usize)
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `main`
   --> examples/api/src/main.rs:13:22
    |
13  |     println!("{:?}", path.verbs());
    |                      ^^^^^^^^^^^^

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

here's the implementation of cat_next:

#[inline(always)]
pub unsafe fn cat_next<T, U>(base: *const T, base_size: usize) -> *const U {
    unsafe { cat_next_ex(base, base_size, core::mem::align_of::<U>()) }
}

#[inline(always)]
pub unsafe fn cat_next_ex<T, U>(base: *const T, base_size: usize, next_align: usize) -> *const U {
    let result = ceil_to_multiple_pow2(base as usize + base_size, next_align);
    #[cfg(miri)] {
        // miri doesn't like int->ptr casts.
        let delta = result - base as usize;
        return (base as *const u8).add(delta) as *const U;
    }
    #[cfg(not(miri))] {
        return result as *const U;
    }
}

#[inline(always)]
pub fn ceil_to_multiple_pow2(x: usize, n: usize) -> usize {
    debug_assert!(is_pow2(n));
    (x + (n-1)) & !(n-1)
}

i've considered modeling the path memory like so:

struct PathData {
    header: PathHeader,
    blob: [u8],
}

this doesn't really work for me however, as it would make Path (a &PathData in this case) a fat pointer. - though i suppose i could do that in cfg(miri) builds only

any ideas for how i could make miri understand what's going on?

leddoo · July 24, 2023, 4:23pm

actually, maybe this is a bug in my code

the &self of a Vec doesn't include the bytes of the vec's values either, but somehow miri understands Vec, and not just the stdlib implementation.

(though again, the resulting slice is correct.)

just for completeness, here's the verbs function:

impl PathHeader {
    #[inline(always)]
    pub fn verbs(&self) -> &[Verb] { unsafe {
        let ptr: *const Verb = cat_next(self, size_of::<Self>());
        core::slice::from_raw_parts(ptr, self.num_verbs as usize)
    }}
}

scottmcm · July 24, 2023, 4:31pm

Note that Vec very carefully stays in pointer-land most of the time, to avoid shrinking what it can address. See Vec: avoid creating slices to the elements by RalfJung · Pull Request #61114 · rust-lang/rust · GitHub

leddoo · July 24, 2023, 4:39pm

what i mean is, in Vec::index, for example, a &Vec<T> is turned into a &T.
but the &Vec<T> doesn't actually cover the bytes of the T - that's behind a NonNull<T>.

similarly in this case, the &PathHeader doesn't cover the bytes of the verbs.
the only difference seems to be that, in case of the path, there's just one allocation, and in case of the vec, there are two.

unless i'm doing something wrong here, ThinVec should, by that logic, have the same issues with miri.

edit1: but ThinVec doesn't have the issue. okay, let's see how they do it.
edit2: hmm, they do exactly the same thing. only difference appears to be that i use a &Header, while they have a struct with a NonNull<Header>.

leddoo · July 24, 2023, 5:01pm

okay, so that was the issue.

making Path a struct with a NonNull<PathHeader> fixes the issue.

that's kinda annoying though, cause that means PathBuf, which owns the actual data, can't Deref to Path, cause Path no longer is a reference.

leddoo · July 24, 2023, 5:09pm

okay, i'm going to close this.

having a custom struct as the "reference version" is the correct/clean thing to do. (also don't have to leak the header in the public interface)

and that's going to be annoying until this issue is resolved: https://github.com/rust-lang/rfcs/issues/997
(actually, ownership transfer is not what i'm after, but someone commented about the Foo and "borrowed Foo" idea)

CAD97 · July 24, 2023, 5:19pm

Disclaimer: I am a member of T-opsem but speak here as myself and am not representing the team.

This is exactly

github.com/rust-lang/unsafe-code-guidelines

Storing an object as &Header, but reading the data past the end of the header

opened 04:26AM - 11 Nov 20 UTC

thomcc

C-open-question A-provenance

This is related to https://github.com/rust-lang/unsafe-code-guidelines/issues/2 …but the read is not out of bounds of the allocation, not being written to by other threads, not the bytes of a `&mut Blah`, etc. That is to say, really the code is trying to model a dynamically sized type, that for one reason or another does not support (Note that ther are a number of custom DST proposals). So, I heard that it was UB for you to have a &T and read outside the bounds of that T, even if conceptually it's a totally in-bounds read. E.g. `T` here may be a ZST, or it may be a header after which a trailing array is expected, or standing that sits at the head of a trailing array, or it may be a struct that's the common shared fields of some set of other struct... These are pretty common in unsafe code as it's a pattern which is both legal and useful in C and C++. It's pretty common in Rust too: - It's not unheard of in C apis to use a `#[repr(C)] struct Foo { _priv: [u8; 0] }`, as this is what bindgen uses. Some of these APIs then go on use `&Foo` in the Rust code. (This is essentially a workaround for a lack of a stable `extern Type`). This code doesn't read the data, so the only issue would be if we told LLVM it could assume things about the pointer that turn out to be untrue in a situation like cross-lang LTO, probably. - Similarly, I've seen other FFI code that used a `struct CStr([u8; 0])` for a similar purpose — as a version of `std::ffi::CStr` that you can actually pass to C directly. (I even almost did this for [ffi_support::FfiStr](https://docs.rs/ffi-support/0.4.2/ffi_support/struct.FfiStr.html), but went with a pointer inside so I could easily check for code passing in null). - `bitvec` has a `BitSlice` type which acts a lot like a slice that magically has bit-level indexing. Internally it's something like `struct BitSlice { _mem: [()] }` which lets it behave like an unsized type, The "pointer" and length are both specially encoded values that contain both the actual pointer/length as well as bit-level offsets for tracking where withing byte things are. There are a lot of reasons this might be illegal, but I had not thought `mem::size_of_val` returning the wrong value was the actual one. - `anyhow::Error` internally wraps a `Box<ErrorImpl<()>>`, where `ErrorImpl<T>` contains a vtable, a backtrace, and then the `T`. `ErrorImpl<()>` is used as it behaves as the "common header" for real ErrorImpl values. On construction, `Box<ErrorImpl<T>>` is converted to `Box<ErrorImpl<()>>`, when stored in the Error. Whenever a method is called that needs to delegate to the vtable, the `Box<ErrorImpl<()>>` is converted into the right pointer type for the vtable function (one of `&ErrorImpl<()>`, `&mut ErrorImpl<()>`, `Box<ErrorImpl<()>>`) which is called with that pointer. The first thing the vtable function generally does is convert the reference to e.g. `&ErrorImpl<T>`, example: https://github.com/dtolnay/anyhow/blob/99c982128458fecb8d1d7aff9478dd77dac0ee3b/src/error.rs#L538-L545. (I had always kind of thought it wasn't okay to use `Box<T>` here, but I'm surprised that stuff like `&ErrorImpl<()>` to `&ErrorImpl<RealType>` isn't okay either). - `wio-rs` contains `VariableSizedBox` which provides this pattern in a library form, and IIUC is mostly intended for the flexible-array-member case. The API attempts to launder pointers to the object, which is... very non-obvious. It seems like it plausibly avoids the issue here, though, but it's insanely subtle, and if this is the recommended pattern, I suspect it will need a very good nomicon entry. https://github.com/retep998/wio-rs/blob/9bf021178b2d02485f1bd35e6cff41bf52d4a9a2/src/vsb.rs#L98-L113 - I do [something similar](https://github.com/thomcc/arcstr/blob/main/src/arc_str.rs#L725-L728) in `arcstr`, where there's a header and a variable length segment that trails it. I avoided issues here by luck, as I took great care to avoid ever putting the inner type behind a reference. This was lucky since I wasn't aware of this at all, and did it for other reasons. This was painful as it required field hard-coding offsets. - This isn't to say anything of the numerous C or C++ apis which expose polymorphism in this way — In c++ this is how single non-virtual inheritance is represented, so it's especially common, although it was common in C too. Additionally, C code with a flexible array member is in tons of places, and not just windows APIs. This is just a few off the top — there's a lot of unsafe code that does this. Personally, I had thought it was allowed so long as you don't go past the actual bounds of the allocation, it makes *some* sense that it's not though, unfortunately. (Somehow, I don't think I've ever had miri trouble me about it, but it's seeming like it's just because of luck && coincidence more than anything else). Anyway, I think if this is UB we should start being way more vocal about it, because it's a totally legal pattern in C and C++, and common.

and you can read that issue's surrounding discussion for more information. In short, this pattern with references cannot be accepted under Miri's default Stacked Borrows model — reborrowing as &PathHeader restricts the pointer provenance to only being usable for the bytes of PathHeader — and you need to either use raw pointers (i.e. make your Path<'a> type (NonNull<PathHeader>, PhantomData<&'a PathHeader>) instead) or opt in to the newer, more experimental Tree Borrows model^[1].

There are two standard SB-compatible workarounds for this:

Have PathRef<'a> be the thin pointer, but it also dereferences to a Path fat type which holds a [u8] slice. &Path is expected to be transient. (This is essentially the pattern my crates erasable and slice-dst exist to support, spelling PathRef as Thin<&Path>.)
Have Path be an opaque/extern type, and any actual functionality is done by "laundering" the pointer through exposed provenance via ptr2int2ptr casts (type_ascribe!(self, &Path) as *const Path as usize as *const PathHeader). Exposed provenance is angelic nondeterminism to use whichever previously exposed provenance works, and is mostly supported by Miri (though with a warning and not perfect support). This is essentially how bitvec gets away with its &BitSlice APIs.

As an overly simplified summary of the situation, SB is a reasonably good bet for the strictest dynamic borrow model Rust might formally adopt, and TB is much closer to the most permissive model that justifies the optimization properties Rust wants to maintain for references. (E.g. LLVM noalias, roughly C restrict; that active &mut don't alias other active pointers and that active & don't alias active writable pointers.) ↩︎

leddoo · July 25, 2023, 2:28pm

i just saw you added some more stuff, thanks!

though i'm not quite sure how it would apply to my case.

here's my setup:

// this owns the actual path data.
// (paths are immutable, this also implements `Arc` logic)
pub struct PathBuf<A: Alloc> {
    data: NonNull<PathHeader>,
    alloc: A,
}

// this is used by all the apis that take paths,
// so they don't have to be allocator generic, which would be annoying.
// this also implements all the path logic (like iteration), so it would be
// nice, if an owned `PathBuf` could deref to `Path`.
pub struct Path<'a> {
    data: NonNull<PathHeader>,
    phantom: PhantomData<&'a ()>,
}

i guess, i could use repr(C), so the pointers overlap, and then use that second type_ascribe magic thing to implement deref?