Undefined behavior when storing `Box` values

[tyilo]

Miri says that the following code has undefined behavior:

use once_map::OnceMap;

fn main() {
    let map = OnceMap::new();
    map.insert(0, |_| Box::new(0));
}

$ cargo +nightly miri run
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.02s
     Running `/home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/cargo-miri runner target/miri/x86_64-unknown-linux-gnu/debug/test_once_map`
error: Undefined Behavior: trying to retag from <84399> for SharedReadOnly permission at alloc26540[0x0], but that tag does not exist in the borrow stack for this location
   --> /home/tyilo/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/once_map-0.4.23/src/sync.rs:577:24
    |
577 |                 Ok((v, ret))
    |                        ^^^ this error occurs as part of retag at alloc26540[0x0..0x4]
    |
    = 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: <84399> was created by a SharedReadOnly retag at offsets [0x0..0x4]
   --> src/main.rs:5:5
    |
  5 |     map.insert(0, |_| Box::new(0));
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: <84399> was later invalidated at offsets [0x0..0x4] by a Unique retag
   --> src/main.rs:5:5
    |
  5 |     map.insert(0, |_| Box::new(0));
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = note: BACKTRACE (of the first span):
    = note: inside closure at /home/tyilo/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/once_map-0.4.23/src/sync.rs:577:24: 577:27
    = note: inside `once_map::sync::Shard::<i32, std::boxed::Box<i32>>::get_or_try_insert::<std::convert::Infallible, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}, &i32, once_map::RandomState, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::map_try_insert<&i32, std::convert::Infallible, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::map_insert<&i32, {closure@src/main.rs:5:19: 5:22}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}>::{closure#0}}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}>::{closure#0}}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::map_try_insert<&i32, std::convert::Infallible, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::map_insert<&i32, {closure@src/main.rs:5:19: 5:22}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}>::{closure#0}}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}>::{closure#1}}>` at /home/tyilo/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/once_map-0.4.23/src/sync.rs:285:28: 285:49
    = note: inside `once_map::OnceMap::<i32, std::boxed::Box<i32>>::get_or_try_insert::<{closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}, &i32, std::convert::Infallible, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::map_try_insert<&i32, std::convert::Infallible, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::map_insert<&i32, {closure@src/main.rs:5:19: 5:22}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}>::{closure#0}}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}>::{closure#0}}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::map_try_insert<&i32, std::convert::Infallible, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::map_insert<&i32, {closure@src/main.rs:5:19: 5:22}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}>::{closure#0}}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}>::{closure#1}}>` at /home/tyilo/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/once_map-0.4.23/src/sync.rs:619:17: 619:101
    = note: inside `once_map::OnceMap::<i32, std::boxed::Box<i32>>::map_try_insert::<&i32, std::convert::Infallible, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::map_insert<&i32, {closure@src/main.rs:5:19: 5:22}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}>::{closure#0}}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}>` at /home/tyilo/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/once_map-0.4.23/src/sync.rs:571:9: 580:10
    = note: inside `once_map::OnceMap::<i32, std::boxed::Box<i32>>::map_insert::<&i32, {closure@src/main.rs:5:19: 5:22}, {closure@once_map::OnceMap<i32, std::boxed::Box<i32>>::insert<{closure@src/main.rs:5:19: 5:22}>::{closure#0}}>` at /home/tyilo/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/once_map-0.4.23/src/sync.rs:547:9: 547:67
    = note: inside `once_map::OnceMap::<i32, std::boxed::Box<i32>>::insert::<{closure@src/main.rs:5:19: 5:22}>` at /home/tyilo/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/once_map-0.4.23/src/sync.rs:486:9: 486:77
note: inside `main`
   --> src/main.rs:5:5
    |
  5 |     map.insert(0, |_| Box::new(0));
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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

error: aborting due to 1 previous error

---

This is probably caused by Storyyeller/stable_deref_trait#15, but that still means that this crate is also unsound :/

Maybe this crate could use its own definition of StableDeref which excludes Box.

[a1phyr]

Thanks for reporting this! I usually run the tests with MIRI, but these almost always use String, so I didn't notice the issue!

Fortunately this seems to be a Stack Borrows issue, as running with MIRIFLAGS=-Zmiri-tree-borrows does not report this as an error. So the code is fine under the new model, and there is not much to do to be compatible with the old one. Given that, I'll close as "Won't fix".

[tyilo]

I can also trigger it with tree borrows with the following code:

use std::sync::Mutex;

use once_map::OnceMap;

fn make_val(k: &i32) -> Box<Mutex<String>> {
    Box::new(Mutex::new(format!("{k}")))
}

fn main() {
    let map = OnceMap::new();
    let v1 = map.insert(0, make_val);
    let s1 = &mut *v1.lock().unwrap();

    // Trigger resize
    for i in 1..100 {
        map.insert(i, make_val);
    }

    s1.push('a');
}

Output:

MIRIFLAGS='-Zmiri-tree-borrows' cargo +nightly miri run
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.02s
     Running `/home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/cargo-miri runner target/miri/x86_64-unknown-linux-gnu/debug/test_once_map`
error: Undefined Behavior: reborrow through <86228> at alloc26908[0x0] is forbidden
   --> /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1
    |
804 | pub unsafe fn drop_in_place<T: PointeeSized>(to_drop: *mut T) {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Undefined Behavior occurred here
    |
    = 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: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/tree-borrows.md for further information
    = help: the accessed tag <86228> is a child of the conflicting tag <86226>
    = help: the conflicting tag <86226> has state Disabled which forbids this reborrow (acting as a child read access)
help: the accessed tag <86228> was created here
   --> src/main.rs:11:14
    |
 11 |     let v1 = map.insert(0, make_val);
    |              ^^^^^^^^^^^^^^^^^^^^^^^
help: the conflicting tag <86226> was created here, in the initial state Reserved
   --> src/main.rs:11:14
    |
 11 |     let v1 = map.insert(0, make_val);
    |              ^^^^^^^^^^^^^^^^^^^^^^^
help: the conflicting tag <86226> later transitioned to Disabled due to a foreign write access at offsets [0x0..0x4]
   --> src/main.rs:12:20
    |
 12 |     let s1 = &mut *v1.lock().unwrap();
    |                    ^^^^^^^^^
    = help: this transition corresponds to a loss of read and write permissions
    = note: BACKTRACE (of the first span):
    = note: inside `std::ptr::drop_in_place::<std::sync::Mutex<std::string::String>> - shim(Some(std::sync::Mutex<std::string::String>))` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1: 804:62
    = note: inside `std::ptr::drop_in_place::<std::boxed::Box<std::sync::Mutex<std::string::String>>> - shim(Some(std::boxed::Box<std::sync::Mutex<std::string::String>>))` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1: 804:62
    = note: inside `std::ptr::drop_in_place::<(i32, std::boxed::Box<std::sync::Mutex<std::string::String>>)> - shim(Some((i32, std::boxed::Box<std::sync::Mutex<std::string::String>>)))` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1: 804:62
    = note: inside `std::ptr::mut_ptr::<impl *mut (i32, std::boxed::Box<std::sync::Mutex<std::string::String>>)>::drop_in_place` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mut_ptr.rs:1396:18: 1396:37
    = note: inside `hashbrown::raw::Bucket::<(i32, std::boxed::Box<std::sync::Mutex<std::string::String>>)>::drop` at /home/tyilo/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/hashbrown-0.16.0/src/raw/mod.rs:505:9: 505:38
    = note: inside `hashbrown::raw::RawTableInner::drop_elements::<(i32, std::boxed::Box<std::sync::Mutex<std::string::String>>)>` at /home/tyilo/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/hashbrown-0.16.0/src/raw/mod.rs:2106:17: 2106:28
    = note: inside `hashbrown::raw::RawTableInner::drop_inner_table::<(i32, std::boxed::Box<std::sync::Mutex<std::string::String>>), hashbrown::raw::alloc::inner::Global>` at /home/tyilo/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/hashbrown-0.16.0/src/raw/mod.rs:2161:17: 2161:42
    = note: inside `<hashbrown::raw::RawTable<(i32, std::boxed::Box<std::sync::Mutex<std::string::String>>)> as std::ops::Drop>::drop` at /home/tyilo/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/hashbrown-0.16.0/src/raw/mod.rs:3365:13: 3366:75
    = note: inside `std::ptr::drop_in_place::<hashbrown::raw::RawTable<(i32, std::boxed::Box<std::sync::Mutex<std::string::String>>)>> - shim(Some(hashbrown::raw::RawTable<(i32, std::boxed::Box<std::sync::Mutex<std::string::String>>)>))` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1: 804:62
    = note: inside `std::ptr::drop_in_place::<hashbrown::table::HashTable<(i32, std::boxed::Box<std::sync::Mutex<std::string::String>>)>> - shim(Some(hashbrown::table::HashTable<(i32, std::boxed::Box<std::sync::Mutex<std::string::String>>)>))` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1: 804:62
    = note: inside `std::ptr::drop_in_place::<once_map::map::HashMap<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>> - shim(Some(once_map::map::HashMap<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>))` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1: 804:62
    = note: inside `std::ptr::drop_in_place::<std::cell::UnsafeCell<once_map::map::HashMap<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>>> - shim(Some(std::cell::UnsafeCell<once_map::map::HashMap<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>>))` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1: 804:62
    = note: inside `std::ptr::drop_in_place::<lock_api::rwlock::RwLock<parking_lot::raw_rwlock::RawRwLock, once_map::map::HashMap<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>>> - shim(Some(lock_api::rwlock::RwLock<parking_lot::raw_rwlock::RawRwLock, once_map::map::HashMap<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>>))` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1: 804:62
    = note: inside `std::ptr::drop_in_place::<once_map::sync::Shard<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>> - shim(Some(once_map::sync::Shard<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>))` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1: 804:62
    = note: inside `std::ptr::drop_in_place::<[once_map::sync::Shard<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>]> - shim(Some([once_map::sync::Shard<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>]))` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1: 804:62
    = note: inside `std::ptr::drop_in_place::<std::boxed::Box<[once_map::sync::Shard<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>]>> - shim(Some(std::boxed::Box<[once_map::sync::Shard<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>]>))` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1: 804:62
    = note: inside `std::ptr::drop_in_place::<once_map::OnceMap<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>> - shim(Some(once_map::OnceMap<i32, std::boxed::Box<std::sync::Mutex<std::string::String>>>))` at /home/tyilo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:804:1: 804:62
note: inside `main`
   --> src/main.rs:20:1
    |
 20 | }
    | ^

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

error: aborting due to 1 previous error

The problem is that when a Box is moved, the references to it are invalidated even when the address is still the same.

[tyilo]

If you replace Box with a custom Box implementation such as this, the UB goes away:

struct MyBox<T> {
    ptr: NonNull<T>,
}

impl<T> MyBox<T> {
    fn new(v: T) -> Self {
        let ptr = Box::into_raw(Box::new(v));
        // SAFETY: `Box::into_raw` always returns a non-null pointer
        let ptr = unsafe { NonNull::new_unchecked(ptr) };
        Self { ptr }
    }
}

impl<T> Drop for MyBox<T> {
    fn drop(&mut self) {
        let ptr = self.ptr.as_ptr();
        // SAFETY: `ptr` is guaranteed to come from `Box::into_raw`
        let v = unsafe { Box::from_raw(ptr) };
        drop(v);
    }
}

impl<T> Deref for MyBox<T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        // SAFETY: `ptr` is valid
        unsafe { self.ptr.as_ref() }
    }
}

unsafe impl<T> StableDeref for MyBox<T> {}

[tyilo]

Actually the body of the main function can just be reduced to the following and still trigger UB:

fn main() {
    let map = OnceMap::new();
    let v1 = map.insert(0, make_val);
    let s1 = &mut *v1.lock().unwrap();
}

[tyilo]

Hi @a1phyr, could you re-open this?

[tyilo]

You could consider depending on aliasable and use its AliasableDeref trait instead.

[purplesyringa]

So the code is fine under the new model, and there is not much to do to be compatible with the old one.

I'd like to push back on this a bit: TB is not "the new model", TB is merely a different model, and the aliasing model Rust will eventually converge on will be neither SB, nor TB, but most likely something in-between. Just because something works in TB doesn't mean it's guaranteed to work when the aliasing model is stabilized.

This issue in particular is related to rust-lang/rfcs#3712, which is an open, unresolved RFC. There seems to be some consensus in favor of making boxes non-magical, but no actual work to do so, and Box is still noalias AFAIK, so for me it doesn't seem right to just ignore the problem.

[tyilo]

You could consider depending on aliasable and use its AliasableDeref trait instead.

Maybe not, seems unmaintained and the latest version on crates.io has some unsoundness problems: rustsec/advisory-db#1437