Stacked Borrows: raw pointer usable only for `T` too strict?

RalfJung commented 5 years ago

Currently, the following is illegal according to Stacked Borrows:

let val = [1u8, 2];
let ptr = &val[0] as *const u8;
let _val = unsafe { *ptr.add(1) };

The problem is that the cast to *const u8 creates a raw pointer that may only be used for the u8 it points to, not anything else. The most common case is to do &slice[0] as *const _ instead of slice.as_ptr().

This has lead to problems:

Maybe this is too restrictive and raw pointers should be allowed to access their "surroundings"? I am not sure what exactly that would look like though. It would probably require having the raw pointer fully inherit all permissions from the reference it is created from.

I'll use this issue to collect such cases.

RalfJung commented 5 years ago

This is also a problem in Rc::into_raw/Rc::from_raw:

    pub fn into_raw(this: Self) -> *const T {
        let ptr: *const T = &*this;
        mem::forget(this);
        ptr
    }

ptr may only be used to access the T part of the RcBox<T>, but if later used with from_raw it is used for the entire Rc. Fixing this is not even possible without https://github.com/rust-lang/rfcs/pull/2582.

RalfJung commented 5 years ago

This also came up in https://github.com/Gilnaa/memoffset/pull/21, where @Amanieu proposed an container_of! macro that computes the address of a struct given the address of one of its fields.

RalfJung commented 5 years ago

@Amanieu the problem with code like this

struct Pair { f1: u16, f2: u16 };

let p = Pair { f1: 2, f2: 3 };
let c = container_of!(&p.f1, Pair, f1);
let _val = c.f2;

arises when you imagine splitting it across several functions:

struct Pair { f1: u16, f2: u16 };

let p = Pair { f1: 2, f2: 3 };
foo(&p.f1);
p.f2 = 4;

We want the compiler to be able to move the assignment to f2 up across the call to foo. But if foo is allowed to use container_of! and then read f2, that is no longer possible.

So, I think there is a real conflict here between being able to bound the effects of a call like foo(&p.f1), and allowing container_of!.

Lokathor commented 5 years ago

How does this work with [T]::as_ptr? Does that pointer let you use "the whole slice" when offsetting?

RalfJung commented 5 years ago

@Lokathor yes. Those methods do the right thing. They cast the wide reference to a wide raw pointer, and only then go to thin -- so the ref-to-raw cast has the right "span" in memory.

ecstatic-morse commented 5 years ago

rust-lang/rust#64980 gives a minor reason to maintain the status quo here. It includes a test-case for a dataflow analysis that computes whether a given Local is mutable through a reference. This test would show the analysis to be unsound if it were legal to offset a reference to one field into a pointer to another, disjoint field.

It is possible to relax the analysis so that it remains sound if this behavior became defined (see rust-lang/rust#65030).

RalfJung commented 4 years ago

See this discussion for a related example.

comex commented 4 years ago

Another example caught by miri. The offending code:

// self.storage: Box<[MaybeUninit<u8>]>
self.storage[self.cursor]
     .as_mut_ptr()
     .cast::<T>()
     .write_unaligned(component);

retep998 commented 4 years ago

A common violation of this rule is FFI structs that end with a flexible array. For example:

#[repr(C)]
struct Foo {
    // other fields
    length: u32,
    data: [u8; 0],
}
// later in code
let foo: *mut Foo = /* obtained somehow */;
let data = slice::from_raw_parts((*foo).data.as_ptr(), (*foo).length);

This pattern is used in quite a few crates that deal with windows api, and some others that don't!

RalfJung commented 4 years ago

That is an interesting special case. It is actually less problematic than the other cases because there is no Rust reference pointing to that "extra" memory (unlike the example in the OP where val still "owns" that extra memory). I am not sure however how to incorporate that into Stacked Borrows...

retep998 commented 4 years ago

I have created a VariableSizedBox smart pointer in wio that as far as I can tell is sound. I would appreciate some thorough review to ensure it is correct and a valid solution to the problem of FFI structs with variable sized arrays.

https://github.com/retep998/wio-rs/blob/master/src/vsb.rs

RalfJung commented 4 years ago

@retep998 this looks like the sensitization approach that we had already discussed before, right? Looks good to me overall.

Do you think such an abstraction will still be needed once https://github.com/rust-lang/rust/issues/73394 stabilizes?

thomcc commented 4 years ago

Oh, this might be the same as #256. If so I mention a bunch of other cases.

They also are sort of different, as that's more about accessing past the end of the struct, and not into different fields of the same struct.

danielhenrymantilla commented 4 years ago

(I don't know where to ask this: I think here is the best place, rather than a new issue)

For "wrapping newtypes" or whatever they are called struct Wrapper(Wrappee, ZSTs); (i.e., for all the newtypes that could have a #[repr(transparent)] on them), is "container_of!", i.e., ::ref_cast guaranteed to be sound, if…:

#[repr(transparent)]?
- I expect it to be the case (even when no instance of the wrapper ever existed)
#[repr(C)]?
- I also expect it to be the case (even when no instance of the wrapper ever existed), since the fact it could have a #[repr(transparent)] on it means there is exactly one non-ZST type and that the other ZSTs are 1-aligned, meaning that memory-wise, there are no other bytes for the container_of! to have access to, and there are no alignment issues whatsoever;
- Potential "extension": Quid of non-1-aligned ZSTs? (Assuming the inner reference has the correct alignment, e.g., because it originated from a reference to the wrapper).
#[repr(Rust)]?
- I conservatively assume it not to be the case, although I struggle to find any hypothetical use case for that lack of guarantee 🤔

The answer may be obvious, but I'd like to have a confirmation from more knowledgeable people 🙂

RalfJung commented 4 years ago

I am very confused by the question, in particular by the mention of container_of!, since there seems to be no pointer arithmetic in your example. Aren't you just asking if you can transmute Wrapper and Wrappee? But that has nothing to do with Stacked Borrows...

danielhenrymantilla commented 4 years ago

Isn't going from Wrappee to Wrapper through a transmutation the same as "trivial pointer arithmetic"?

But that has nothing to do with Stacked Borrows...

I apologize if I have misplaced my question (in "my view", a transmute with the semantics of a trivial container_of! still belonged to an issue that was discussing about it).

(I can (re)move my comments to another issue that would be more apt)

The TL,DR of my question is:

if the container contains no other bytes than those of the wrappee, is it sound to transmute from a reference to the wrappee to a reference to the wrapper? (Basically a generalization of &T -> &[T; 1])
And are there requirements on the repr-ness of the wrapper?

with the extension regarding non-1-aligned ZSTs and padding bytes (theoretical problem, not one that I may have stumbled on):

type Wrappee = u8;

#[repr(C)]
struct Wrapper(Wrappee, [u32; 0]); /* 3 trailing padding bytes */

let at_wrapper = &Wrapper(42, []);
let at_wrappee: &Wrappee = &at_wrapper.0;
let at_wrapper2 = unsafe { ::core::mem::transmute::<_, &Wrapper>(at_wrappee) }; // is this UB?
// is at_wrapper2 usable?

RalfJung commented 4 years ago

Isn't going from Wrappee to Wrapper through a transmutation the same as "trivial pointer arithmetic"?

Maybe, with an emphasis on "trivial", which means I think it has little to do with this issue. This issue is about the case where there actually is some extra data "outside" the T that one wants to access, but the aliasing model has something to say about whether that access is allowed.

(in "my view", a transmute with the semantics of a trivial container_of! still belonged to an issue that was discussing about it).

This issue is specifically about Stacked Borrows, as the title says. Which does not come up in your question at all, hence my confusion.^^ Also I hope the thread here makes it clear that the issue is nit about container_of; container_of is just one user of a particular kind of behavior that Stacked Borrows disallows that we discuss here.

Your question is all about layout guarantees, so yes, a new issue would be better. However for repr(transparent) I am confused why you are even asking, since the docs should be quite clear that repr(transparent) is all about being able to transmute between the wrapper and the wrappee. But maybe better safe than sorry. :) I am just worried, if even such basic questions are not clearly answered in the existing docs, clearly we entirely failed at writing those docs. I thought this was clear. Feedback would be welcome for what could be done so that the docs would have given you the answers you were looking for without having to ask for confirmation.

danielhenrymantilla commented 4 years ago

if even such basic questions are not clearly answered in the existing docs

Nah, I think it's mostly my bad, I get too paranoid sometimes 😅 Now that you mention it, I think that

repr(transparent)

This can only be used on structs with a single non-zero-sized field (there may be additional zero-sized fields). The effect is that the layout and ABI of the whole struct is guaranteed to be the same as that one field.

The goal is to make it possible to transmute between the single field and the struct. An example of that is UnsafeCell, which can be transmuted into the type it wraps.

source: https://doc.rust-lang.org/nomicon/other-reprs.html#reprtransparent

as well as:

The C Representation

The C representation is designed for dual purposes. One purpose is for creating types that are interoperable with the C Language. The second purpose is to create types that you can soundly perform operations on that rely on data layout such as reinterpreting values as a different type.

source: https://doc.rust-lang.org/reference/type-layout.html#the-c-representation

are pretty clear 🙇

RalfJung commented 4 years ago

Okay. :) Don't hesitate to open a new issue if new questions come up in the future or if you are not entirely sure. Issues are more easily merged than split. :)

RalfJung commented 3 years ago

This issue plagues not only raw pointers but also references whose size cannot be determined, see https://github.com/rust-lang/unsafe-code-guidelines/issues/276. The ideas that were mentioned above to fix this for raw pointers should hopefully also let us fix this forextern type.

saethlin commented 2 years ago

I recently found another interesting example of this pattern: https://github.com/rkyv/rkyv/blob/f552fabc204ebc27f812166e636a75d45d97cba1/rkyv/src/string/repr.rs#L40-L62

    /// Returns the offset of the representation.
    ///
    /// # Safety
    ///
    /// The internal representation must be out-of-line.
    #[inline]
    pub unsafe fn out_of_line_offset(&self) -> isize {
        FixedIsize::from_le_bytes(self.out_of_line.offset) as isize
    }

    /// Returns a pointer to the bytes of the string.
    #[inline]
    pub fn as_ptr(&self) -> *const u8 {
        unsafe {
            if self.is_inline() {
                self.inline.bytes.as_ptr()
            } else {
                (self as *const Self)
                    .cast::<u8>()
                    .offset(self.out_of_line_offset())
            }
        }
    }

RalfJung commented 2 years ago

How is that an instance of this pattern? The one cast I see (self as *const Self) seems to be at the maximal possible type?

saethlin commented 2 years ago

The offset that rkyv is applying here offsets the pointer outside of Self. This is an implementation of relative pointers, and relies on the caller being pinned.

I thought this issue was a duplicate of #256 but if there's some narrow difference between them, this is more like #256.

workingjubilee commented 2 years ago

soooo I don't think miri can handle AVX code or anything but I imagine this might give Miri even more of a fit (from https://github.com/rust-lang/rust/issues/71025):

use std::arch::x86_64::*;

#[inline(always)]
pub unsafe fn mutate_chunk(rows: [__m256d; 4]) -> [__m256d; 4] {
    [
        _mm256_permute2f128_pd(rows[0], rows[1], 0x20),
        _mm256_permute2f128_pd(rows[2], rows[3], 0x20),
        _mm256_permute2f128_pd(rows[0], rows[1], 0x31),
        _mm256_permute2f128_pd(rows[2], rows[3], 0x31),
    ]
}

#[target_feature(enable = "avx")]
pub unsafe fn mutate_array(input: *const f64, output: *mut f64) {
    let mut input_data = [_mm256_setzero_pd(); 4];

    for i in 0..4 {
        input_data[i] = _mm256_loadu_pd(input.add(4*i));
    }

    let output_data = mutate_chunk(input_data);

    for i in 0..4 {
        _mm256_storeu_pd(output.add(4*i), output_data[i]);
    }
}

thomcc commented 2 years ago

That doesn't seem to have any UB on its own, it just requires that input and output have provenance over at [f64; 16] or similar.

workingjubilee commented 2 years ago

I didn't post it because I think it's UB, but because I suspect it might be an Exciting Case Study.

RalfJung commented 2 years ago

Hm, but I don't think I quite understand the case study here, other than being a real-world example of using the C idiom of passing an array (of known length) via a raw pointer to its first element?

djkoloski commented 2 years ago

Just wanted to follow up on @saethlin's example with a minimal reproduction (from https://github.com/rkyv/rkyv/issues/259):

#[repr(C)]
pub struct RelSlice {
    offset: [u8; 4],
    len: [u8; 4],
}

impl RelSlice {
    pub fn as_slice(&self) -> &[u8] {
        let offset = i32::from_le_bytes(self.offset) as isize;
        let len = u32::from_le_bytes(self.len) as usize;

        let base = self as *const Self as *const u8;
        unsafe {
            ::core::slice::from_raw_parts(base.offset(offset), len)
        }
    }
}

unsafe fn get_root<T>(bytes: &[u8]) -> &T {
    let root_pos = bytes.len() - ::core::mem::size_of::<T>();
    &*bytes.as_ptr().offset(root_pos as isize).cast::<T>()
}

fn main() {
    let bytes: &[u8] = &[
        0, 1, 2, 3,
        0xfc, 0xff, 0xff, 0xff,
        4, 0, 0, 0,
    ];

    let root = unsafe { get_root::<RelSlice>(bytes) };
    println!("{:?}", root.as_slice());
}

Under MIRIFLAGS=-Zmiri-tag-raw-pointers, this does not pass with the following error:

error: Undefined Behavior: trying to reborrow <1728> for SharedReadOnly permission at alloc769[0x0], but that tag does not exist in the borrow stack for this location
  --> C:\Users\David\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\slice\raw.rs:93:14
   |
93 |     unsafe { &*ptr::slice_from_raw_parts(data, len) }
   |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |              |
   |              trying to reborrow <1728> for SharedReadOnly permission at alloc769[0x0], but that tag does not exist in the borrow stack for this location
   |              this error occurs as part of a reborrow at alloc769[0x0..0x4]
   |
   = 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::slice::from_raw_parts::<u8>` at C:\Users\David\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\slice\raw.rs:93:14
note: inside `RelSlice::as_slice` at src\main.rs:14:13
  --> src\main.rs:14:13
   |
14 |             ::core::slice::from_raw_parts(base.offset(offset), len)
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `main` at src\main.rs:32:22
  --> src\main.rs:32:22
   |
32 |     println!("{:?}", root.as_slice());
   |                      ^^^^^^^^^^^^^^^

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

It appears that the issue here is that the base pointer is created by self as *const Self as *const u8. If I understand correctly, this prevents it from accessing data outside the bounds of the RelSlice because it stores the location as a relative pointer instead of a raw pointer. To my mind, it seems like get_root should allow the returned reference to access any memory in bytes since the borrow encompasses the whole slice. This might interact poorly with mutably borrowing the bytes though, as splitting that mutable borrow (e.g. using slice::split_at_mut) would have to rely on dynamic constraints to prevent both resulting borrows from overlapping.

That said, rkyv currently enforces a strict ownership model with relative pointers, so I don't think a situation like the one described above using container_of! is possible. These constraints can also be verified dynamically with bytecheck, so this restriction is really the core of the issue. It also supports a mutable API with the disjoint borrowing described above. All of this currently passes MIRI as well, just not with -Zmiri-tag-raw-pointers. Is there any way to reconcile relative pointers with MIRI's tagged raw pointer semantics?

saethlin commented 2 years ago

I cannot comment on changes to the model which may accommodate this code, I think Ralf will take care of that.

To my mind, it seems like get_root should allow the returned reference to access any memory in bytes since the borrow encompasses the whole slice.

I think this points to a common misunderstanding that I've already seen at least twice. I think you're confusing the borrow checker and lifetimes with the (prototype) aliasing rules. The lifetime connection between these two references is irrelevant and not even accessed by Miri. You could make them both 'static, or transmute the lifetimes to anything else, the aliasing model doesn't care.

Is there any way to reconcile relative pointers with MIRI's tagged raw pointer semantics?

Relative pointers work perfectly fine in Stacked Borrows. What doesn't work is putting a reference anywhere in the chain of custody between the outer object and the access back out from the inner object to the outer object. I'm not saying that this is a good thing, or that you should write code like what I'm including below. I've just noticed that people often say things like "X is impossible under SB/SB with raw pointer tagging" and that is very rarely true. Almost always the thing is possible, but it's unergonomic or inconvenient to do the thing in question while avoiding references. So I don't know if people are just being terse or they don't understand. Anyway, this code does relative pointers and passes Miri with raw pointer tagging:

#[repr(C)]
pub struct RelSlice<'a> {
    offset: [u8; 4],
    len: [u8; 4],
    _marker: std::marker::PhantomData<&'a u8>,
}

impl<'a> RelSlice<'a> {
    pub fn as_slice(slf: *const RelSlice<'a>) -> &'a [u8] {
        unsafe {
            let offset = i32::from_le_bytes((*slf).offset) as isize;
            let len = u32::from_le_bytes((*slf).len) as usize;

            let base = slf as *const u8;
            ::core::slice::from_raw_parts(base.offset(offset), len)
        }
    }
}

unsafe fn get_root<'a, T>(bytes: &'a [u8]) -> *const T {
    let root_pos = bytes.len() - ::core::mem::size_of::<T>();
    bytes.as_ptr().offset(root_pos as isize).cast::<T>()
}

fn main() {
    let bytes: &[u8] = &[
        0, 1, 2, 3,
        0xfc, 0xff, 0xff, 0xff,
        4, 0, 0, 0,
    ];

    let root: *const RelSlice = unsafe { get_root::<RelSlice>(bytes) };
    println!("{:?}", RelSlice::as_slice(root));
}

djkoloski commented 2 years ago

Thanks for the detailed explanation, that cleared up my confusion a lot. I see now that producing a reference causes the issue. I guess this is an instance where the aliasing information generated by relative pointers is correct, but not compatible with stricter stacked borrows semantics.

I am somewhat confused why -Zmiri-strict-provenance implies -Zmiri-tag-raw-pointers though (per https://github.com/rust-lang/miri/pull/2045). As I understand it, the relative pointer example I provided should not violate strict provenance since there is an unbroken chain of custody from the byte buffer. I am very supportive of strict provenance but I'm not sure why raw pointer tagging is a prerequisite for it. I might just have to read up on stacked borrows some more though, so apologies if my questions are using a lot of your time.

RalfJung commented 2 years ago

As I understand it, the relative pointer example I provided should not violate strict provenance since there is an unbroken chain of custody from the byte buffer.

Yeah, and you can run -Zmiri-strict-provenance -Zmiri-disable-stacked-borrows to check that.

But strict provenance plus aliasing rules means we should also track provenance on raw pointers. Or, put differently, default Stacked Borrows treats raw pointers basically like integers -- as not having provenance. That is in direct opposition to the goal of strict provenance, where provenance ought to be tracked properly everywhere.

saethlin commented 2 years ago

eyre also runs across this, because it wants to create a concrete type which contains a generic: https://github.com/yaahc/eyre/blob/master/src/error.rs#L194-L207

        let inner = Box::new(ErrorImpl {
            vtable,
            handler,
            _object: error,
        });
        // Erase the concrete type of E from the compile-time type system. This
        // is equivalent to the safe unsize coersion from Box<ErrorImpl<E>> to
        // Box<ErrorImpl<dyn StdError + Send + Sync + 'static>> except that the
        // result is a thin pointer. The necessary behavior for manipulating the
        // underlying ErrorImpl<E> is preserved in the vtable provided by the
        // caller rather than a builtin fat pointer vtable.
        let erased = mem::transmute::<Box<ErrorImpl<E>>, Box<ErrorImpl<()>>>(inner);
        let inner = ManuallyDrop::new(erased);
        Report { inner }

This transmute on its own is fine, but in a few places it then tries to un-erase: https://github.com/yaahc/eyre/blob/b8f3892754b83505c61e83db477a02f294dbd04e/src/error.rs#L517-L523

// Safety: requires layout of *e to match ErrorImpl<E>.
unsafe fn object_drop<E>(e: Box<ErrorImpl<()>>) {
    // Cast back to ErrorImpl<E> so that the allocator receives the correct
    // Layout to deallocate the Box's memory.
    let unerased = mem::transmute::<Box<ErrorImpl<()>>, Box<ErrorImpl<E>>>(e);
    drop(unerased);
}

and due to the retag in the transmute which decreases the provenance of the type-erased Box, we end up with this:

test test_iter ... error: Undefined Behavior: trying to reborrow <164086> for SharedReadOnly permission at alloc62436[0x18], but that tag does not exist in the borrow stack for this location
   --> /tmp/eyre-0.6.8/src/error.rs:541:5
    |
541 |     &(*(e as *const ErrorImpl<()> as *const ErrorImpl<E>))._object
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |     |
    |     trying to reborrow <164086> for SharedReadOnly permission at alloc62436[0x18], but that tag does not exist in the borrow stack for this location
    |     this error occurs as part of a reborrow at alloc62436[0x18..0x28]
    |
    = 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
help: <164086> was created due to a retag at offsets [0x0..0x18]
   --> /tmp/eyre-0.6.8/src/error.rs:541:9
    |
541 |     &(*(e as *const ErrorImpl<()> as *const ErrorImpl<E>))._object
    |         ^
    = note: inside `eyre::error::object_ref::<eyre::error::ContextError<i32, eyre::Report>>` at /tmp/eyre-0.6.8/src/error.rs:541:5

safinaskar commented 1 year ago

Here is another example possibly worth adding to this issue. On x86_64-linux-gnu struct libc::dirent has last field with type [c_char; 256], but such type is lie, because Linux allows one to create a file with more than 256 bytes in file name. See my bug report here: https://github.com/rust-lang/libc/issues/2669 . So I'm not sure whether using such struct conforms to Rust rules. If not, this will be great argument for convincing libc authors to change dirent definition

RalfJung commented 1 year ago

Yeah, dirent is basically the same problem as extern type (https://github.com/rust-lang/unsafe-code-guidelines/issues/276).

RalfJung commented 8 months ago

Tree Borrows solves this issue by not doing any retagging on raw pointers, and just giving them the same permission as the reference they are created from. However doing that without two-phase borrows is tricky; here's some discussion.

briansmith commented 6 months ago

let val = [1u8, 2];
let ptr = &val[0] as *const u8;
let _val = unsafe { *ptr.add(1) };
The problem is that the cast to *const u8 [...]

The problem is not restricted to casts, but also affects coercions, right? Consider the equivalent (AFAICT):

.let val = [1u8, 2];
 let ptr: *const u8 = &val[0];
 let _val = unsafe { *ptr.add(1) };

A lot of the discussion regarding this has been about "casts" but even if one avoids casts, one could still be affected by this.

danielhenrymantilla commented 6 months ago

Yes, it applies to "ref-to-ptr coërcions" as well. I think the "cast" terminology is used here kind of indiscriminately to cover both explicit as ... casts, and implicit casts, such as the ones stemming from "coërcions" like with let ptr: *const u8 = &val[0]; or identity::<*const u8>(&val[0]). The terminology in the book about casts vs. coërcions is a bit muddy, to be honest.

RalfJung commented 6 months ago

Yes indeed, we often view coercions as just automatically inserted casts. Opsem discussions generally are happening on a level where all these implicit operations are made explicit. I can see how that can make the terminology confusing though.

rust-lang / unsafe-code-guidelines

Stacked Borrows: raw pointer usable only for `T` too strict? #134

`repr(transparent)`

The C Representation