Allocators that "shrink" allocations to fit the request cause Stacked Borrows errors when used with Box

[RalfJung]

When a Box allocator creates an allocation and returns only a part of that to Box, there will be Stacked Borrows errors when the Box is deallocated. This is because the pointer lost the provenance for the other parts of memory outside the Box, and hence does not have the right to deallocate them.

This affects, in particular, the System allocator on Windows:

#![feature(allocator_api)]

#[repr(align(32))]
struct VeryAligned(u8);

fn main() {
    let _ = Box::new_in(VeryAligned(0), std::alloc::System);
}

Also see the discussion on Zulip.

[Nemo157]

It's not just shrinking, allocators that overallocate (as allowed by the Allocator::allocate docs) also fail under miri:

#![feature(allocator_api)]

use core::ptr::NonNull;
use std::alloc::{Allocator, Layout, AllocError, System};

struct OverAllocate;

unsafe impl Allocator for OverAllocate {
    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        let (layout, _) = layout.extend(layout).unwrap();
        let layout = layout.pad_to_align();
        System.allocate(layout)
    }
    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
        let (layout, _) = layout.extend(layout).unwrap();
        let layout = layout.pad_to_align();
        System.deallocate(ptr, layout);
    }
}

fn main() {
    let _ = Box::new_in(0, OverAllocate);
}

error: Undefined Behavior: no item granting write access for deallocation to tag <3690> at alloc1837 found in borrow stack
  --> /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/unix/alloc.rs:42:9
   |
42 |         libc::free(ptr as *mut libc::c_void)
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no item granting write access for deallocation to tag <3690> at alloc1837 found in borrow stack
   |
   = 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: <3690> was created by a retag at offsets [0x0..0x4]
  --> src/main.rs:22:13
   |
22 |     let _ = Box::new_in(0, OverAllocate);
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: backtrace:
   = note: inside `std::sys::unix::alloc::<impl std::alloc::GlobalAlloc for std::alloc::System>::dealloc` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/unix/alloc.rs:42:9
   = note: inside `<std::alloc::System as std::alloc::Allocator>::deallocate` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/alloc.rs:216:22
note: inside `<OverAllocate as std::alloc::Allocator>::deallocate` at src/main.rs:17:9
  --> src/main.rs:17:9
   |
17 |         System.deallocate(ptr, layout);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: inside `alloc::alloc::box_free::<i32, OverAllocate>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/alloc.rs:348:9
   = note: inside `std::ptr::drop_in_place::<std::boxed::Box<i32, OverAllocate>> -

(If you assume this check in miri is correct, then fixing Box is not enough; if you combine this with Box::from_raw(Box::leak(...)) it seems to me that the Allocator::allocate and Box::leak docs are in direct contradiction under the SB rules).

[jtroo]

I had a confusing time trying to get some code to pass MIRI and ended up needing to use strict provenance functions to make MIRI happy. Is the "Fails MIRI" code failing due to this issue, or is it expected to fail?

Fails MIRI:
https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=498931662a59e8cbb2f3f6610e9bfd5b

fn main() {
    // Declare a buffer to pass to FFI
    let mut buf: Buf = Buf(std::array::from_fn(|_| 0));

    // FFI will use an unknown amount of space in the buffer
    unsafe { emulated_c_ffi(buf.0.as_mut_ptr() as *mut u8) };

    // Read what's in the buffer, (shrinks valid memory region?), but parent is buf
    let token_groups = buf.0.as_ptr() as *const TOKEN_GROUPS;
    println!("group count: {}", unsafe { (*token_groups).GroupCount });

    // Get a slice from Groups, fails MIRI
    let groups: &[u32] = unsafe {
        std::slice::from_raw_parts(
            (*token_groups).Groups.as_ptr(),
            (*token_groups).GroupCount as usize,
        )
    };

    for (i, group) in groups.iter().enumerate() {
        println!("group {i}: {group}");
    }
}

Passes MIRI by using strict provenance:
https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=f96fb47253eb92aa46ae0d8d36cfe678

Changes from before:

    // The providence ptr's address isn't important; the useful information is
    // that it's coming from `buf`.
    let providence_ptr = buf.0.as_ptr() as *const u32;

    // Get a slice from Groups
    let groups: &[u32] = unsafe {
        std::slice::from_raw_parts(
            providence_ptr.with_addr((*token_groups).Groups.as_ptr().addr()),
            (*token_groups).GroupCount as usize,
        )
    };

[saethlin]

The problem you're having here is not related to this issue.

In the invalid code you are creating an intermediate reference which only refers to the GroupCount member, which is a length-1 array (the reference is the receiver of the .as_ptr() slice method). Then .as_ptr() turns that reference into a pointer, then you try to use that to create a slice with length 3.

The root cause of the problem is that length-1 array. If C really has that length-1 array and you really need the type to be compatible that's a real shame (I thought all pointers in C were ABI-compatible, but I'm no C expert). It looks like you are trying to imitate flexible array members, and Rust supports them too, the last member in your struct could be type [u32] (I would personally not attempt this, but that is much more my own inexperience with the feature than anything else).

The other way out of this is to do the address calculation you want using offset_of!. You can use the memoffset crate: https://crates.io/crates/memoffset or refer to the RFC: rust-lang/rfcs#3308.

Happy to discuss more on the miri stream in the Rust Zulip: https://rust-lang.zulipchat.com/, your comment is strictly-speaking off topic for this issue. And while GitHub is a great place for some things it is a very poor support forum :)

[RalfJung]

It's not just shrinking, allocators that overallocate (as allowed by the Allocator::allocate docs) also fail under miri:

That is what I mean by shrinking: allocating more, and then only returning a part of that from the allocation request (hence "shrinking" the underlying allocation to fit the request).

---

We now have the very experimental Tree Borrows mode in Miri, which should be able to handle code like this. You can enable it via -Zmiri-tree-borrows.

[Nemo157]

By "overallocating" I mean allocating something larger than the requested layout and returning the entire larger allocation, not returning a subset.

[RalfJung]

I think that just means Box is doing the shrinking. It ignores the length of the returned slice.