Miri detects a violation of stacked borrows in slice::sort_unstable with -Zmiri-track-raw-pointers

[saethlin]

Similar to #78749?

I tried this code:

fn main() {
    let mut data = [1, 0];
    data.sort_unstable();
}

MIRIFLAGS="-Zmiri-track-raw-pointers" cargo +nightly miri run

I expected to see this happen: Miri does not detect UB

Instead, this happened: Miri detects UB (experimentally)

error: Undefined Behavior: no item granting read access to tag <2552> at alloc1081 found in borrow stack.
    --> /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/intrinsics.rs:2079:14
     |
2079 |     unsafe { copy_nonoverlapping(src, dst, count) }
     |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no item granting read access to tag <2552> at alloc1081 found in 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

Meta

rustc --version --verbose:

rustc 1.58.0-nightly (6d246f0c8 2021-11-26)
binary: rustc
commit-hash: 6d246f0c8d3063fea86abbb65a824362709541ba
commit-date: 2021-11-26
host: x86_64-unknown-linux-gnu
release: 1.58.0-nightly
LLVM version: 13.0.0

Backtrace

error: Undefined Behavior: no item granting read access to tag <2552> at alloc1081 found in borrow stack.
    --> /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/intrinsics.rs:2079:14
     |
2079 |     unsafe { copy_nonoverlapping(src, dst, count) }
     |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no item granting read access to tag <2552> at alloc1081 found in 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::intrinsics::copy_nonoverlapping::<i32>` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/intrinsics.rs:2079:14
     = note: inside `core::slice::sort::shift_tail::<i32, [closure@core::slice::<impl [i32]>::sort_unstable::{closure#0}]>` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/sort.rs:104:13
     = note: inside `core::slice::sort::insertion_sort::<i32, [closure@core::slice::<impl [i32]>::sort_unstable::{closure#0}]>` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/sort.rs:175:9
     = note: inside `core::slice::sort::recurse::<i32, [closure@core::slice::<impl [i32]>::sort_unstable::{closure#0}]>` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/sort.rs:734:13
     = note: inside `core::slice::sort::quicksort::<i32, [closure@core::slice::<impl [i32]>::sort_unstable::{closure#0}]>` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/sort.rs:815:5
     = note: inside `core::slice::<impl [i32]>::sort_unstable` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/mod.rs:2356:9
note: inside `main` at src/main.rs:3:5
    --> src/main.rs:3:5
     |
3    |     data.sort_unstable();
     |     ^^^^^^^^^^^^^^^^^^^^
     = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/ben/.rustup/toolchains/nightly-x86_64-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/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:123:18
     = note: inside closure at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:145: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/ben/.rustup/toolchains/nightly-x86_64-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/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:406:40
     = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:370:19
     = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:133:14
     = note: inside closure at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:128:48
     = note: inside `std::panicking::r#try::do_call::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:406:40
     = note: inside `std::panicking::r#try::<isize, [closure@std::rt::lang_start_internal::{closure#2}]>` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:370:19
     = note: inside `std::panic::catch_unwind::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:133:14
     = note: inside `std::rt::lang_start_internal` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:128:20
     = note: inside `std::rt::lang_start::<()>` at /home/ben/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:144:17

error: aborting due to previous error

[oli-obk]

cc @rust-lang/miri

[saethlin]

FWIW, I have now detected this bug through the tests in hashbrown and rand.

[RalfJung]

Looks like the problem is in this line:

rust/library/core/src/slice/sort.rs

Line 112 in 18fb97e

ptr::copy_nonoverlapping(v.get_unchecked(i), v.get_unchecked_mut(i + 1), 1);

v.get_unchecked_mut re-borrows an &mut on the entire slice, thus invalidation previously created pointers. So this is yet another instance of rust-lang/unsafe-code-guidelines#133.

[saethlin]

Actually, just to be sure, @RalfJung are we interested in patching out all such instances of this in std/alloc/core? I know I personally would like the standard library to be clean against Miri with -Ztag-raw-pointers so that I can check libraries for stacked borrows issues. I just did a quick skim now that I understand the rules and I think I can spot a few other issues, so I'm not sure if these were deliberately left in, or if I'm just the first person to be looking this carefully.

[RalfJung]

So far we fixed various issues of this sort that people noticed, but there was never a concerted effort to find all of them. So they were not deliberately left in, just not found yet.

Whether we want to fix them all is up to @rust-lang/libs who ultimately decide about the std library implementation.

[scottmcm]

@saethlin So far the fixes have been localized enough that it's been easy to take them (eg #81160). If anything comes up that requires drastic changes to fix then there might be a conversation about it, but for simple ones that don't increase maintenance burden I think they'll be happily accepted.