Miri reports Undefined Behavior in tests

[parasyte]

Hi! Evaluating some crates and decided to check out thunderdome. It looked pretty good until I tried running the test suite under miri, which reports Undefined Behavior:

$ cargo miri test --lib -- get2_mut
Preparing a sysroot for Miri (target: x86_64-unknown-linux-gnu)... done
    Finished test [unoptimized + debuginfo] target(s) in 0.01s
     Running unittests src/lib.rs (target/miri/x86_64-unknown-linux-gnu/debug/deps/thunderdome-1f5b4f350601acba)

running 5 tests
test arena::test::get2_mut ... error: Undefined Behavior: trying to retag from <233349> for Unique permission at alloc93875[0x4], but that tag does not exist in the borrow stack for this location
   --> src/arena.rs:409:48
    |
409 |         let item1 = unsafe { item1_ptr.map(|x| &mut *x) };
    |                                                ^^^^^^^
    |                                                |
    |                                                trying to retag from <233349> for Unique permission at alloc93875[0x4], but that tag does not exist in the borrow stack for this location
    |                                                this error occurs as part of retag at alloc93875[0x4..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: <233349> was created by a SharedReadWrite retag at offsets [0x4..0x8]
   --> src/arena.rs:406:54
    |
406 |         let item1_ptr = self.get_mut(index1).map(|x| x as *mut T);
    |                                                      ^
help: <233349> was later invalidated at offsets [0x0..0x18] by a Unique retag
   --> src/arena.rs:372:15
    |
372 |         match self.storage.get_mut(index.slot as usize) {
    |               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = note: BACKTRACE (of the first span):
    = note: inside closure at src/arena.rs:409:48: 409:55
    = note: inside `std::option::Option::<*mut i32>::map::<&mut i32, [closure@src/arena.rs:409:44: 409:47]>` at /home/jay/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/option.rs:972:29: 972:33
note: inside `arena::Arena::<i32>::get2_mut`
   --> src/arena.rs:409:30
    |
409 |         let item1 = unsafe { item1_ptr.map(|x| &mut *x) };
    |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `arena::test::get2_mut`
   --> src/arena.rs:810:40
    |
810 |         let (foo_handle, bar_handle) = arena.get2_mut(foo, bar);
    |                                        ^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure
   --> src/arena.rs:805:19
    |
804 |     #[test]
    |     ------- in this procedural macro expansion
805 |     fn get2_mut() {
    |                   ^
    = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

FWIW, asan does not report any issues when running the test suite.

[LPGhatguy]

Hey, thanks for checking this out! MIRI is serious business, we should fix these issues and add it to our CI pipeline.

[parasyte]

Similar to orlp/slotmap#92 (comment), using MIRIFLAGS='-Zmiri-tree-borrows' does not report any issues!

[CosmicHorrorDev]

Noticed this because of the linked issue

It looks like this crate is very similar to slab which implements .get2_mut() by using .split_at_mut() on the underlying Vec to get two mutable slices that each contain one of the desired elements. Then you can call .get_mut() on each of the slices to get a mutable reference

https://docs.rs/slab/latest/src/slab/lib.rs.html#751-773

Do you think the same technique would work here? It allows you to avoid using unsafe

[CosmicHorrorDev]

Looks like you can. I opened #42

[LPGhatguy]

Thanks for the investigation and PR!

In general, I'm happy to reduce unsafety in crates when there's an easy replacement. In this case though, I'm a little concerned — this safe alternative has a lot more code! It's hard to make sure that all of these branches are tested and work correctly when compared with the original code.

Based on orlp/slotmap#92 (comment), I'm not sure we should change the implementation of this method. It seems like there might be a compelling argument that MIRI is raising a false alarm here. I am not familiar enough with the current status of UB in Rust to know for sure.

[CosmicHorrorDev]

The main part that has a lot of explicit branches is when the two indices occupy the same slot. I was mostly trying to avoid duplicate checks, but they could probably just use .get_mut() and the compiler should be smart enough to remove the duplicate checks. That should reduce a lot of the near-duplicate logic

I was mostly just making this change to reduce unsafe usage, not because I'm worried about aliasing issues here (which the compiler doesn't have a firm stance on yet). slab seems to be largely the same as this library aside from the generational indices and manages to avoid any unsafe aside from a couple of unsafe methods they expose for comparison

[CosmicHorrorDev]

Went ahead and pushed changes to consolidate a lot of the branches