Suspicious undefined hehaviour report about stacked borrows

chuigda · July 22, 2021, 9:13am

I'm implementing an object pool like structure and testing it, with miri. Miri reported an undefined behavior about stacked-borrows (will post error message in replies).

After carrying out several experiments, I think this piece of code could act as a minimal reproducible example. Seems that the following steps would tick miri off:

Creating a Box
Getting a pointer ptr to the content of the created Box via
- &*boxed
- boxed.as_ref() as *const _
Move the created Box somewhere
Getting an immutable reference to the content of that Box via ptr
Drop the created Box

According to my test, without either step 3 or step 4, miri won't complain about stacked borrows any more.

I have read the stacked borrow paper for several times, and also have checked related chapaters in Rust reference and Rust nomicon. Personally I guess this is potentially a problem of miri, but I'm still not sure about that.

chuigda · July 22, 2021, 9:14am

Miri error message of my original project

running 6 tests
test data::test::test_dyn_base_assoc ... error: Undefined Behavior: trying to reborrow for SharedReadWrite at alloc86848, but parent tag <217678> does not have an appropriate item in the borrow stack
   --> /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:192:1
    |
192 | pub unsafe fn drop_in_place<T: ?Sized>(to_drop: *mut T) {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ trying to reborrow for SharedReadWrite at alloc86848, but parent tag <217678> does not have an appropriate item in the borrow stack
    |
    = 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::ptr::drop_in_place::<data::tyck::TyckInfo> - shim(Some(data::tyck::TyckInfo))` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:192:1
    = note: inside `std::ptr::drop_in_place::<std::boxed::Box<data::tyck::TyckInfo>> - shim(Some(std::boxed::Box<data::tyck::TyckInfo>))` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:192:1
    = note: inside `std::ptr::drop_in_place::<(std::boxed::Box<data::tyck::TyckInfo>, ())> - shim(Some((std::boxed::Box<data::tyck::TyckInfo>, ())))` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:192:1
    = note: inside `std::ptr::mut_ptr::<impl *mut (std::boxed::Box<data::tyck::TyckInfo>, ())>::drop_in_place` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mut_ptr.rs:995:18
    = note: inside `hashbrown::raw::Bucket::<(std::boxed::Box<data::tyck::TyckInfo>, ())>::drop` at /home/debian/.cargo/registry/src/mirrors.tuna.tsinghua.edu.cn-d3a35666c793c312/hashbrown-0.11.0/src/raw/mod.rs:344:9
    = note: inside `hashbrown::raw::RawTable::<(std::boxed::Box<data::tyck::TyckInfo>, ())>::drop_elements` at /home/debian/.cargo/registry/src/mirrors.tuna.tsinghua.edu.cn-d3a35666c793c312/hashbrown-0.11.0/src/raw/mod.rs:598:17
    = note: inside `<hashbrown::raw::RawTable<(std::boxed::Box<data::tyck::TyckInfo>, ())> as std::ops::Drop>::drop` at /home/debian/.cargo/registry/src/mirrors.tuna.tsinghua.edu.cn-d3a35666c793c312/hashbrown-0.11.0/src/raw/mod.rs:1665:17
    = note: inside `std::ptr::drop_in_place::<hashbrown::raw::RawTable<(std::boxed::Box<data::tyck::TyckInfo>, ())>> - shim(Some(hashbrown::raw::RawTable<(std::boxed::Box<data::tyck::TyckInfo>, ())>))` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:192:1
    = note: inside `std::ptr::drop_in_place::<hashbrown::map::HashMap<std::boxed::Box<data::tyck::TyckInfo>, (), std::collections::hash_map::RandomState>> - shim(Some(hashbrown::map::HashMap<std::boxed::Box<data::tyck::TyckInfo>, (), std::collections::hash_map::RandomState>))` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:192:1
    = note: inside `std::ptr::drop_in_place::<hashbrown::set::HashSet<std::boxed::Box<data::tyck::TyckInfo>, std::collections::hash_map::RandomState>> - shim(Some(hashbrown::set::HashSet<std::boxed::Box<data::tyck::TyckInfo>, std::collections::hash_map::RandomState>))` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:192:1
    = note: inside `std::ptr::drop_in_place::<std::collections::HashSet<std::boxed::Box<data::tyck::TyckInfo>>> - shim(Some(std::collections::HashSet<std::boxed::Box<data::tyck::TyckInfo>>))` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:192:1
    = note: inside `std::ptr::drop_in_place::<data::tyck::TyckInfoPool> - shim(Some(data::tyck::TyckInfoPool))` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:192:1
note: inside `data::test::test_dyn_base_assoc` at pr47-core/src/data/test.rs:117:1
   --> pr47-core/src/data/test.rs:117:1
    |
117 | }
    | ^
note: inside closure at pr47-core/src/data/test.rs:90:9
   --> pr47-core/src/data/test.rs:90:9
    |
90  |   #[test] fn test_dyn_base_assoc() {
    |  _-------_^
    | | |
    | | in this procedural macro expansion
91  | |     let mut tyck_info_pool: TyckInfoPool = TyckInfoPool::new();
92  | |
93  | |     let w: Wrapper<TestStruct> = Wrapper::new_owned(TestStruct {
...   |
116 | |     assert_eq!(out.field3, "1919810");
117 | | }
    | |_^
    = note: inside `<[closure@pr47-core/src/data/test.rs:90:9: 117:2] as std::ops::FnOnce<()>>::call_once - shim` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `test::test::__rust_begin_short_backtrace::<fn()>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:578:5
    = note: inside closure at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:569:30
    = note: inside `<[closure@test::test::run_test::{closure#2}] as std::ops::FnOnce<()>>::call_once - shim(vtable)` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send> as std::ops::FnOnce<()>>::call_once` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:1572:9
    = note: inside `<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>> as std::ops::FnOnce<()>>::call_once` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:347:9
    = note: inside `std::panicking::r#try::do_call::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:401:40
    = note: inside `std::panicking::r#try::<(), std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:365:19
    = note: inside `std::panic::catch_unwind::<std::panic::AssertUnwindSafe<std::boxed::Box<dyn std::ops::FnOnce() + std::marker::Send>>, ()>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:434:14
    = note: inside `test::test::run_test_in_process` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:601:18
    = note: inside closure at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:493:39
    = note: inside `test::test::run_test::run_test_inner` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:531:13
    = note: inside `test::test::run_test` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:565:28
    = note: inside `test::test::run_tests::<[closure@test::test::run_tests_console::{closure#2}]>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:306:17
    = note: inside `test::test::run_tests_console` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/console.rs:290:5
    = note: inside `test::test::test_main` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:123:15
    = note: inside `test::test::test_main_static` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:142:5
    = note: inside `main`
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:125:18
    = note: inside closure at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:63:18
    = note: inside `std::ops::function::impls::<impl std::ops::FnOnce<()> for &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>::call_once` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:259:13
    = note: inside `std::panicking::r#try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:401:40
    = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:365:19
    = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:434:14
    = note: inside closure at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:45:48
    = note: inside `std::panicking::r#try::do_call::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:401:40
    = note: inside `std::panicking::r#try::<isize, [closure@std::rt::lang_start_internal::{closure#2}]>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:365:19
    = note: inside `std::panic::catch_unwind::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:434:14
    = note: inside `std::rt::lang_start_internal` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:45:20
    = note: inside `std::rt::lang_start::<()>` at /home/debian/.rustup/toolchains/nightly-i686-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:62:5
    = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to previous error

Hyeonu · July 22, 2021, 9:22am

After the step 2, the borrow stack would be something like this.

*const T
&T
&Box<T>
Box<T> - the owned value

And moving out the Box<T> invalidates the whole borrow stack including the raw ptr at the top.

chuigda · July 22, 2021, 9:25am

So would this lead to true undefined behavior or cause some damage?

What's more, using a custom "box" type seems to be okay (though I'm not sure if it is correctly implemented):

use std::alloc::{alloc, Layout, dealloc};
use std::marker::PhantomData;
use std::ptr::drop_in_place;

pub struct MyBox<T>(*mut T, PhantomData<T>);

impl<T> MyBox<T> {
    #[inline(never)] pub fn new(t: T) -> Self {
        unsafe {
            let ptr: *mut T = alloc(Layout::new::<T>()) as *mut _;
            std::ptr::write(ptr, t);
            Self(ptr, PhantomData::default())
        }
    }

    #[inline(never)] pub fn as_ref(&self) -> &T {
        unsafe { self.0.as_ref().unwrap() }
    }
}

impl<T> Drop for MyBox<T> {
    #[inline(never)] fn drop(&mut self) {
        unsafe {
            drop_in_place(self.0);
            dealloc(self.0 as *mut u8, Layout::new::<T>())
        }
    }
}

alice · July 22, 2021, 9:32am

Yes, it is true undefined behavior. A box like the one you suggested is indeed necessary, though I usually recommend using Box as the allocator and into_raw/from_raw to get the pointer, as you otherwise need to handle zero sized types specially. Also, your destructor leaks memory if the destructor panics.

jhpratt · July 22, 2021, 9:34am

While MIRI has false negatives (it doesn't catch everything), to my knowledge it has no false positives. If it reports there's UB, there is.

chuigda · July 22, 2021, 9:37am

I still have two more confusions:

Since moving (out?) the Box<T> invalidates the whole borrow stack including the raw ptr at the top as Hyeonu stated, why the error was reported on the moved Box destruction, instead of raw ptr dereferencing?
What's making the Box<T> and MyBox<T> different?

bjorn3 · July 22, 2021, 9:41am

Box is special cased inside the compiler. For example the pointer it wraps is marked as noalias when codegening to LLVM ir. There are a couple of other things like being able to move out of a box using *boxed_value. See

chuigda · July 23, 2021, 2:03am

I think it's done. Any one have some spare time to take a code review? Thanks ahead.

system · October 21, 2021, 2:03am

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.