Box in custom allocator fails even with -Zmiri-tree-borrows

[js2xxx]

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

[RalfJung]

This is odd, the problem is with accessing the allocator state itself, not the memory that stores the data. The backtraces are not very helpful since the actual action is in the standard library. Something Box/Vec do with the allocator itself makes Miri unhappy.

Note that there is an unrelated UB issue here

        let delta = unsafe { next.byte_offset_from(self.memory.get()) };

This is UB if next is out-of-bounds.

[RalfJung]

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.

I can't reproduce this locally: when I run your file with -Zmiri-tree-borrows, it seems to work fine.

$ ./miri run alloc.rs -Zmiri-tree-borrows
8
8
8

EDIT: oh your code is the non-failing one. That's confusing...

[RalfJung]

This line is the culprit:

let their_alloc = ptr.as_ptr().map_addr(|addr| addr & !127).cast::<Self>();

Even with Tree Borrows, you can't just "get out" of the Box and access the surrounding memory again. ptr here is a unique pointer to a Box<i32> -- emphasis on "unique pointer". Tree Borrows is fine with using this pointer for more than just that i32, but it is still unique in everything it touches. And yet here you are using it in a way that aliases with the original my_alloc pointer or with the other Box.

This seems pretty fundamental; if we want to assume that Box is unique then we can't just use a Box pointer (or things derived from it) in aliasing ways like that.

[RalfJung]

What I don't understand is why you use ptr here to get to top. You have self available which should be a perfectly good way to access that same memory.

[js2xxx]

Thanks for your reply!

What I don't understand is why you use ptr here to get to top. You have self available which should be a perfectly good way to access that same memory.

Here is a more realistic example with some explanatory comments: Rust playground. In short, finding the corresponding bin is somewhat expensive in my real implementation, so I chose to use pointer arithmetics.

This seems pretty fundamental; if we want to assume that Box is unique then we can't just use a Box pointer (or things derived from it) in aliasing ways like that.

I think the uniqueness of Box pointers is too strong currently, which should just cover the actual storage place of its data (such as the 4 bytes of a u32) in space, and just cover the lifetime between the allocation and deallocation of its memory in time. Could it still be sound being modified this way? Or could it be actually implemented in pratice?

Note that there is an unrelated UB issue here

Oops XD. The newer example has fixed it.

[RalfJung]

I think the uniqueness of Box pointers is too strong currently, which should just cover the actual storage place of its data (such as the 4 bytes of a u32) in space, and just cover the lifetime between the allocation and deallocation of its memory in time. Could it still be sound being modified this way? Or could it be actually implemented in pratice?

There's no way to have a pointer that's only unique for some of memory, that would defeat the entire purpose of noalias (being able to reorder accesses without knowing much about them).

Making uniqueness temporary in scope is possible, but here this doesn't really help. Consider a function like:

fn foo(a: Box<i32, MyAlloc>, b: Box<i32, MyAlloc>) {
  drop(a); drop(b),
}

LLVM does limit the scope of the noalias here (more so than Stacked/Tree Borrows), and it's the entire function. And yet the custom allocator destructor will do aliasing accesses while the function runs. LLVM doesn't even know that there is a "deallocation" here, calling MyAlloc::deallocate is just a regular fn call. There's no way to say that this magically ends the scope of some aliasing requirements (which ones would that even be, and how would we know the parent scope).

I think the only way to allow such accesses is to not have noalias to begin with.

[js2xxx]

LLVM doesn't even know that there is a "deallocation" here, calling MyAlloc::deallocate is just a regular fn call.

Things being it here, why not give Allocate::deallocate some special treatment just like foreign functions? If my memory is correct, the noalias rule for Box pointers will end at a foreign function call, such as libc::free.

[RalfJung]

No there is no such special treatment. Foreign functions are usually "unknown" to the compiler so it has to be very conservative, but then Rust supports cross-language LTO so e.g. inlining C functions into Rust may actually happen.

malloc and free are special magic functions that likely do need extra compiler treatment (different from your average foreign function); the exact shape and rules for that are unknown at this time. rust-lang/unsafe-code-guidelines#442 discusses some of that. But that's all specifically for the global allocator. What Box<T, A> does is just call some functions on A; so far there's no magic going on here whatsoever. Maybe there should, I don't know -- I worry it might cause more problems. What causes issues for you is making the Box type magic (with noalias) without also making the allocator functions magic.

[js2xxx]

Okay I get it now. Seems like this issue cannot be resolved for a few days. I'll leave this open for now.

[RalfJung]

Little status update: with rust-lang/rust#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 rust-lang/wg-allocators#122.

[RalfJung]

@js2xxx you write

        // By the way, switching provenance from `ptr` to `self` seems not feasible
        // either, because there might be pointers from another thread although this
        // structure is not Send or Sync, for what I expect is storing `MyAlloc`
        // in a thread-local variable and wrap it with a Send & Sync unit struct.

I don't understand this. Why is the thread relevant? If all dealloc of all threads go through self they all use the same provenance, right? Specifically it is self.bins that has to store the right provenance.

Currently you are storing this entire pointer, &MyAlloc, with each Box, and you don't even use it in dealloc -- seems like a waste.

[js2xxx]

Oops, I was not very clear about that. Sorry for the confusion.

The "switching provenance trick" is doing something like this:

let their_bin = (&*self.bins as *const [MyBin; 1])
    .with_addr(ptr.as_ptr().addr() & !127)
    .cast::<MyBin>();

This trick tries to match the address range and the provenance of some bin. While the collection of bins is simple (a 1-element array) in this example, it can be a large & finely crafted collection that is logically complex but contiguous in memory.

But in the example above:

• I want a Send & Sync global allocator in the end.
• MyAllocator is thread-local, but storing it in the TLS and wrapping it into a unit struct can make the final allocator Send & Sync, iff a MyAllocator in one thread can deallocate pointers from MyAllocators in another thread. The implementation of this function is off-topic and not going to be discussed here.
• Hence, the pointer argument in the deallocate function can have a different provenance from the current MyAllocator, which prevents the trick.

Edit: The trick actually passes the miri test using Tree Borrows, but is not what I want in the end.

[RalfJung]

Hence, the pointer argument in the deallocate function can have a different provenance from the current MyAllocator, which prevents the trick.

There's a ptr indirection here, so it's no longer the pointer in deallocate that's relevant, it's the pointer to MyBin. So as long as all the many MyAllocator have the same provenance for the same bin (I assume in fact each bin is in only one allocator?), everything is fine.

[RalfJung]

Btw I think there is still a bug in this code

        if top == 32 {
            return None;
        }
        let ptr = unsafe { NonNull::new_unchecked(self.memory.get().add(top)) };
        self.top.set(top + 1);
        Some(ptr.cast())

There is only space for 8 usize in self.memory, but this allows allocating up to 32.

[js2xxx]

Oh, yes, indeed. That example is just for demonstration though, and that mistake doesn't relate to the issue we are concerned about.

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

[RalfJung]

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!

[js2xxx]

Unfortunately, there is another problem with Box & Vec where both Stacked Borrows and Tree Borrows fail in one way of allocation but pass in another: Playground

Code diff on the test box-custom-alloc-aliasing.rs with my modifications:

@@ -48,6 +48,7 @@
         let end = start + BIN_SIZE * mem::size_of::<usize>();
         let addr = ptr.addr().get();
         assert!((start..end).contains(&addr));
+        println!("{}", self.top.get());
     }
 }

@@ -109,7 +109,9 @@
 // Make sure to involve `Box` in allocating these,
 // as that's where `noalias` may come from.
 fn v<T, A: Allocator>(t: T, a: A) -> Vec<T, A> {
-    (Box::new_in([t], a) as Box<[T], A>).into_vec()
+    let vec = (Box::new_in([t], a) as Box<[T], A>).into_vec();
+    vec.into_boxed_slice().into_vec() // <------------------------ This one fails
+    // vec                            // <------------------------ This one works
 }
 
 fn main() {

However, if the implementation of v is changed like the code below, everything passes:

// Box creation and then converting to another Box.
fn v<T, A: Allocator>(t: T, a: A) -> Box<[T], A> {
    Box::new_in([t], a) as Box<[T], A>
}

In summary, it seems that Box::new_in, Box::into_vec, and Vec::with_capacity_in + Vec::push are all fine, except for Vec::into_boxed_slice. Maybe something is amiss in the implementation of that function?

More precisely, Miri with Tree Borrows only fails for access to top on deallocation (println!("{}", self.top.get());), which I think necessary for updating information such as used counts, linked list heads and so on. Miri with Stacked Borrows fails even when the line with println does not exist.

The output of miri using Stacked Borrows

error: Undefined Behavior: attempting a read access using <4003> at alloc1552[0x0], but that tag does not exist in the borrow stack for this location
   --> src/main.rs:100:25
    |
100 |         let thread_id = ptr::read(ptr::addr_of!((*their_bin).thread_id));
    |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |                         |
    |                         attempting a read access using <4003> at alloc1552[0x0], but that tag does not exist in the borrow stack for this location
    |                         this error occurs as part of an access at alloc1552[0x0..0x8]
    |
    = 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: <4003> was created by a SharedReadWrite retag at offsets [0x10..0x18]
   --> src/main.rs:113:5
    |
113 |     vec.into_boxed_slice().into_vec() // <------------------------ This one fails
    |     ^^^^^^^^^^^^^^^^^^^^^^
    = note: BACKTRACE (of the first span):
    = note: inside `<MyAllocator as std::alloc::Allocator>::deallocate` at src/main.rs:100:25: 100:73
    = 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<usize, &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:556:22: 556:56
    = note: inside `std::ptr::drop_in_place::<alloc::raw_vec::RawVec<usize, &MyAllocator>> - shim(Some(alloc::raw_vec::RawVec<usize, &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<usize, &MyAllocator>> - shim(Some(std::vec::Vec<usize, &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<usize, &MyAllocator>, std::vec::Vec<usize, &MyAllocator>)> - shim(Some((std::vec::Vec<usize, &MyAllocator>, std::vec::Vec<usize, &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<usize, &MyAllocator>, std::vec::Vec<usize, &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`
   --> src/main.rs:124:5
    |
124 |     drop((a, b));
    |     ^^^^^^^^^^^^

The output of miri using Tree Borrows

error: Undefined Behavior: read access through <3557> at alloc1542[0x8] 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 <3557> at alloc1542[0x8] 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 <3557> is a child of the conflicting tag <3553>
    = help: the conflicting tag <3553> has state Disabled which forbids this child read access
help: the accessed tag <3557> was created here
   --> src/main.rs:114:5
    |
114 |     vec.into_boxed_slice().into_vec() // <------------------------ This one fails
    |     ^^^^^^^^^^^^^^^^^^^^^^
help: the conflicting tag <3553> was created here, in the initial state Reserved
   --> src/main.rs:114:5
    |
114 |     vec.into_boxed_slice().into_vec() // <------------------------ This one fails
    |     ^^^^^^^^^^^^^^^^^^^^^^
help: the conflicting tag <3553> later transitioned to Disabled due to a foreign write access at offsets [0x8..0x10]
   --> src/main.rs:38:9
    |
38  |         self.top.set(top + 1);
    |         ^^^^^^^^^^^^^^^^^^^^^
    = 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 `MyBin::push`
   --> src/main.rs:51:24
    |
51  |         println!("{}", self.top.get());
    |                        ^^^^^^^^^^^^^^
note: inside `<MyAllocator as std::alloc::Allocator>::deallocate`
   --> src/main.rs:103:22
    |
103 |             unsafe { (*their_bin).push(ptr) };
    |                      ^^^^^^^^^^^^^^^^^^^^^^
    = 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<usize, &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:556:22: 556:56
    = note: inside `std::ptr::drop_in_place::<alloc::raw_vec::RawVec<usize, &MyAllocator>> - shim(Some(alloc::raw_vec::RawVec<usize, &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<usize, &MyAllocator>> - shim(Some(std::vec::Vec<usize, &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<usize, &MyAllocator>, std::vec::Vec<usize, &MyAllocator>)> - shim(Some((std::vec::Vec<usize, &MyAllocator>, std::vec::Vec<usize, &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<usize, &MyAllocator>, std::vec::Vec<usize, &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`
   --> src/main.rs:125:5
    |
125 |     drop((a, b));
    |     ^^^^^^^^

[RalfJung]

vec.into_boxed_slice().into_vec()

That code is buggy. into_boxed_slice creates a Box with the Global allocator; if you want to use a custom allocator you have to use it throughout.

[js2xxx]

into_boxed_slice creates a Box with the Global allocator

That's not the source code of the standard library shows:

    pub fn into_boxed_slice(mut self) -> Box<[T], A> {
        unsafe {
            self.shrink_to_fit();
            let me = ManuallyDrop::new(self);
            let buf = ptr::read(&me.buf);
            let len = me.len();
            buf.into_box(len).assume_init()
        }
    }

It clearly returns with the same allocator from the original Vec.

[RalfJung]

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

[js2xxx]

Thanks! I think all the problems will be fixed by that PR.

[js2xxx]

Just FYI, except Vec::into_boxed_slice and types using the global allocator, my custom allocator has passed all the miri tests with both borrow rules! You can check out the CI builds here.

[RalfJung]

Great, thanks for trying that. :)