miri: `Box` in custom allocator fails even with `-Zmiri-tree-borrows`

I’m writing an arena-like memory allocator that uses pointer arithmetic to calculate the associated bin address of the allocated pointer. Some of the structures look like this:

Example on the playground

When I tested my allocator with miri, it told me some undefined behavior occurred.

At first, I thought it was just a duplicate of #2104 and rust-lang/unsafe-code-guidelines#402 when I ran the example above with -Zmiri-stack-borrows, so I followed the suggestions in the comments there and switched to -Zmiri-tree-borrows.

However, when switched to -Zmiri-tree-borrows, the error stops happening if I use Vec::with_capacity_in(1, alloc), but occurs again for a different reason if I use (Box::new_in([1], alloc) as Box<[u32], A>).into_vec() (commented out in the example above), which indicates something wrong with Box once again.

The output of miri says:

error: Undefined Behavior: read access through <1659> is forbidden
   --> ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/cell.rs:517:18
    |
517 |         unsafe { *self.value.get() }
    |                  ^^^^^^^^^^^^^^^^^ read access through <1659> is forbidden
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental
    = help: the accessed tag <1659> is a child of the conflicting tag <1526>
    = help: the conflicting tag <1526> has state Disabled which forbids this child read access
help: the accessed tag <1659> was created here
   --> main.rs:58:5
    |
58  |     (Box::new_in([t], a) as Box<[T], A>).into_vec()
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: the conflicting tag <1526> was created here, in the initial state Reserved
   --> main.rs:58:6
    |
58  |     (Box::new_in([t], a) as Box<[T], A>).into_vec()
    |      ^^^^^^^^^^^^^^^^^^^
help: the conflicting tag <1526> later transitioned to Disabled due to a foreign write access at offsets [0x0..0x8]
   --> main.rs:37:9
    |
37  |         self.top.set(delta as usize);
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = help: this transition corresponds to a loss of read and write permissions
    = note: BACKTRACE (of the first span):
    = note: inside `std::cell::Cell::<usize>::get` at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/cell.rs:517:18: 517:35
note: inside `<MyAllocator as std::alloc::Allocator>::deallocate`
   --> main.rs:50:28
    |
50  |             println!("{}", this.top.get());
    |                            ^^^^^^^^^^^^^^
    = note: inside `<&MyAllocator as std::alloc::Allocator>::deallocate` at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/alloc/mod.rs:392:18: 392:50
    = note: inside `<alloc::raw_vec::RawVec<i32, &MyAllocator> as std::ops::Drop>::drop` at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/raw_vec.rs:532:22: 532:56
    = note: inside `std::ptr::drop_in_place::<alloc::raw_vec::RawVec<i32, &MyAllocator>> - shim(Some(alloc::raw_vec::RawVec<i32, &MyAllocator>))` at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:515:1: 515:56
    = note: inside `std::ptr::drop_in_place::<std::vec::Vec<i32, &MyAllocator>> - shim(Some(std::vec::Vec<i32, &MyAllocator>))` at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:515:1: 515:56
    = note: inside `std::ptr::drop_in_place::<(std::vec::Vec<i32, &MyAllocator>, std::vec::Vec<i32, &MyAllocator>)> - shim(Some((std::vec::Vec<i32, &MyAllocator>, std::vec::Vec<i32, &MyAllocator>)))` at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:515:1: 515:56
    = note: inside `std::mem::drop::<(std::vec::Vec<i32, &MyAllocator>, std::vec::Vec<i32, &MyAllocator>)>` at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/mem/mod.rs:992:24: 992:25
note: inside `main`
   --> main.rs:66:5
    |
66  |     drop((a, b));
    |     ^^^^^^^^^^^^

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

error: aborting due to 1 previous error

It seems a Reserved region is affected by foreign writing access and thus becomes Disabled. I wonder what “magic” Box puts in here, and whether there is some way to solve it (or get rid of it).

About this issue

  • Original URL
  • State: closed
  • Created 4 months ago
  • Comments: 23 (14 by maintainers)

Commits related to this issue

Most upvoted comments

Oh, sorry, you are right.

The issue is here:

        unsafe {
            let slice = slice::from_raw_parts_mut(me.ptr() as *mut MaybeUninit<T>, len);
            Box::from_raw_in(slice, ptr::read(&me.alloc))
        }

That creates a reference, which generates noalias assumptions and restricts the provenance to just that memory region the reference points to. That should probably use ptr::slice_from_raw_parts_mut instead.

EDIT: Should be fixed by https://github.com/rust-lang/rust/pull/122298.

By the way, my allocator is nearly complete. Check it out here if you are interested.

Your original testcase should now pass in Miri (with tomorrow’s nightly) both with Stacked Borrows and Tree Borrows. I am curious what happens when you run the full allocator!

Little status update: with https://github.com/rust-lang/rust/pull/122018, code like yours is no longer causing UB in the generated LLVM IR. Miri still needs to be updated to support such code though.

Note that this is not a stable guarantee that the code you are writing is sound. You are using nightly features so their requirements are subject to change. Whether that pattern you are using is permitted is tracked at https://github.com/rust-lang/wg-allocators/issues/122.