Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
RalfJung opened this issue May 28, 2019 · 38 comments
Open

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

RalfJung opened this issue May 28, 2019 · 38 comments
Labels
A-aliasing-model Topic: Related to the aliasing model (e.g. Stacked/Tree Borrows) A-SB-vs-TB Topic: Design questions where SB and TB are opposite sides of the design axis C-open-question Category: An open question that we should revisit S-pending-design Status: Resolving this issue requires addressing some open design questions

Comments

@RalfJung
Copy link
Member

RalfJung commented May 28, 2019

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 RalfJung added the A-aliasing-model Topic: Related to the aliasing model (e.g. Stacked/Tree Borrows) label May 28, 2019
@RalfJung
Copy link
Member Author

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 rust-lang/rfcs#2582.

bors added a commit to rust-lang/hashbrown that referenced this issue May 28, 2019
cast the entire slice to a raw pointer, not just the first element

A strict reading of pointer provenance implies that when a `&T` gets cast to `*const T`, you may only use the raw pointer to access that `T`, not its neighbors.  That's what Miri currently implements, though it is less strict around statics (which is why this one does not currently cause a Miri failure -- I'd like to make Miri more strict though).

Cc rust-lang/unsafe-code-guidelines#134
@RalfJung RalfJung added the C-open-question Category: An open question that we should revisit label Aug 14, 2019
@RalfJung
Copy link
Member Author

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

@RalfJung
Copy link
Member Author

@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
Copy link
Contributor

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

@RalfJung
Copy link
Member Author

@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
Copy link

ecstatic-morse commented Oct 5, 2019

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
Copy link
Member Author

See this discussion for a related example.

@comex
Copy link

comex commented Dec 23, 2019

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);

Dylan-DPC-zz pushed a commit to Dylan-DPC-zz/rust that referenced this issue Mar 30, 2020
avoid creating unnecessary reference in Windows Env iterator

Discovered in rust-lang/miri#1225: the Windows `Env` iterator violates Stacked Borrows by creating an `&u16`, turning it into a raw pointer, and then accessing memory outside the range of that type.

There is no need to create a reference here in the first place, so the fix is trivial.
Cc @JOE1994
Cc rust-lang/unsafe-code-guidelines#134
@retep998
Copy link
Member

retep998 commented May 12, 2020

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!

A few examples after a quick search:
https://github.com/kavorite/imgclip/blob/f3889e9da99fde01bd688e5ee2a18d89c823dee6/src/dib.rs#L53
https://github.com/rust-lang/backtrace-rs/blob/16682c76eb25df517e2cc220e56baf4f8a616f72/src/symbolize/dbghelp.rs#L165
https://github.com/klenin/spawner2/blob/0d461fd59e09fbcf9e863acf9a5db441da58b7a2/spawner/sys/windows/helpers.rs#L450
https://github.com/benfred/remoteprocess/blob/cdbf4aa23f48b48f949da3dadfc5878ab6e94f53/src/windows/symbolication.rs#L76
https://github.com/notify-rs/notify/blob/eed64ac9088ec1aab5c4710ef7232f0fbee49e0a/src/windows.rs#L328
https://github.com/CasualX/pelite/blob/29c4cac31c2ff4a7fd3d7953e9af8ea97c55423b/src/pe64/exception.rs#L180
https://github.com/snuk182/nuklear-rust/blob/1fb270a527ff048bb7e38dd88553c98987af233c/src/lib.rs#L5678
https://github.com/diwic/reffers-rs/blob/e6bdacafb96dae5dfa95a0830dda18fd64928691/src/rc.rs#L320
https://github.com/szymonwieloch/rust-dlopen/blob/26b70292744db1052403378d4a01075b6171e3d1/src/raw/windows.rs#L213
https://github.com/PyO3/pyo3/blob/956ed524122d27597888c28199053e6ba3f5289d/src/types/tuple.rs#L85
https://github.com/gluon-lang/gluon/blob/7b4cb090037d5ddf62dc35fde0b316689e5e4de3/vm/src/array.rs#L103
https://github.com/redsift/redbpf/blob/bea9eff8d2eedf0a57e90c8b7191a465cffdc56f/redbpf/src/load/map_io.rs#L70
https://github.com/servo/html5ever/blob/304c155bce19f956f0641cce3a1e19bc3b7bdaa1/zbuf/heap_data.rs#L178
https://github.com/arcnmx/ddcutil-rs/blob/3a631cdc92fcffcfc6e97fa29b4ed607fafc52d8/sys/src/lib.rs#L226

@RalfJung
Copy link
Member Author

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...

@workingjubilee
Copy link
Member

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 rust-lang/rust#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
Copy link
Member

thomcc commented Mar 25, 2022

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
Copy link
Member

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

@RalfJung
Copy link
Member Author

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
Copy link

Just wanted to follow up on @saethlin's example with a minimal reproduction (from rkyv/rkyv#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
Copy link
Member

saethlin commented Apr 4, 2022

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
Copy link

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 rust-lang/miri#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
Copy link
Member Author

RalfJung commented Apr 4, 2022

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
Copy link
Member

saethlin commented Apr 9, 2022

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
Copy link

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: rust-lang/libc#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
Copy link
Member Author

RalfJung commented Jun 4, 2023

Yeah, dirent is basically the same problem as extern type (#276).

jmchacon added a commit to jmchacon/rusty6502 that referenced this issue Jun 5, 2023
* We hae binaries. So dependabot everything.

Also remote nostd

* Remove our old CI

* Add miri flag, disable loom

* Update config.toml to take linking options out.

Those should remain local, not checked in.

* Disable isolation in miri as we need to read in test input files

* Bump msrv to 1.65

* suppress leak suppressions file for now

* Bump msrv comment explaining why

* Change test to see if miri gets happier

* Fixup tests trying to get miri to work.

Turns out it won't due to:

rust-lang/unsafe-code-guidelines#134

so disable that check

* take 2 for multiple miri flags

* Try adding a leak suppresions file

* try putting lsan at top level

* Rework a few things:

sanitizer - specify path relative in github actions

miri - use sampling of tests from cpu. Otheriwse it OOMs

* Specify tests better

* Break miri up for c64basic vs cpu

For CPU only do a subset and run in separate runs to avoid OOMs.

Try again to get leak detector happy

* Change to a test miri can run.

Try a different way to pass lsan suppressions file
@JakobDegen JakobDegen added S-pending-design Status: Resolving this issue requires addressing some open design questions A-SB-vs-TB Topic: Design questions where SB and TB are opposite sides of the design axis labels Aug 1, 2023
@RalfJung
Copy link
Member Author

RalfJung commented Apr 1, 2024

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
Copy link

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
Copy link
Contributor

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
Copy link
Member Author

RalfJung commented May 24, 2024

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-aliasing-model Topic: Related to the aliasing model (e.g. Stacked/Tree Borrows) A-SB-vs-TB Topic: Design questions where SB and TB are opposite sides of the design axis C-open-question Category: An open question that we should revisit S-pending-design Status: Resolving this issue requires addressing some open design questions
Projects
None yet
Development

No branches or pull requests