Vec::sort violates pointer provenance rules according to Miri

[ssomers]

I tried miri with -Zmiri-track-raw-pointers on this code:

fn main() {
    let mut v = vec![1; 20];
    v.push(0);
    v.sort();
}

I hoped to see everybody happy.

Instead, this happened (including -Zmiri-track-alloc-id=2016):

note: tracking was triggered
   --> /home/stein/rust/library/alloc/src/alloc.rs:120:14
    |
120 |     unsafe { __rust_realloc(ptr, layout.size(), layout.align(), new_size) }
    |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ created allocation with id 2016
    |
    = note: inside `std::alloc::realloc` at /home/stein/rust/library/alloc/src/alloc.rs:120:14
    = note: inside `std::alloc::Global::grow_impl` at /home/stein/rust/library/alloc/src/alloc.rs:196:31
    = note: inside `<std::alloc::Global as std::alloc::AllocRef>::grow` at /home/stein/rust/library/alloc/src/alloc.rs:249:18
    = note: inside `alloc::raw_vec::finish_grow::<std::alloc::Global>` at /home/stein/rust/library/alloc/src/raw_vec.rs:492:13
    = note: inside `alloc::raw_vec::RawVec::<i32>::grow_amortized` at /home/stein/rust/library/alloc/src/raw_vec.rs:428:19
    = note: inside `alloc::raw_vec::RawVec::<i32>::try_reserve` at /home/stein/rust/library/alloc/src/raw_vec.rs:317:13
    = note: inside `alloc::raw_vec::RawVec::<i32>::reserve` at /home/stein/rust/library/alloc/src/raw_vec.rs:311:24
    = note: inside `std::vec::Vec::<i32>::reserve` at /home/stein/rust/library/alloc/src/vec.rs:505:9
    = note: inside `std::vec::Vec::<i32>::push` at /home/stein/rust/library/alloc/src/vec.rs:1210:13
note: inside `main` at src/main.rs:3:5
   --> src/main.rs:3:5
    |
3   |     v.push(0);
    |     ^^^^^^^^^
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/stein/rust/library/core/src/ops/function.rs:227:5
    = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /home/stein/rust/library/std/src/sys_common/backtrace.rs:125:18
    = note: inside closure at /home/stein/rust/library/std/src/rt.rs:66: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/stein/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/stein/rust/library/std/src/panicking.rs:381:40
    = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/stein/rust/library/std/src/panicking.rs:345:19
    = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/stein/rust/library/std/src/panic.rs:396:14
    = note: inside `std::rt::lang_start_internal` at /home/stein/rust/library/std/src/rt.rs:51:25
    = note: inside `std::rt::lang_start::<()>` at /home/stein/rust/library/std/src/rt.rs:65:5

error: Undefined Behavior: no item granting read access to tag <5348> at alloc2016+0x4c found in borrow stack.
    --> /home/stein/rust/library/core/src/intrinsics.rs:1860:14
     |
1860 |     unsafe { copy_nonoverlapping(src, dst, count) }
     |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no item granting read access to tag <5348> at alloc2016+0x4c 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/stein/rust/library/core/src/intrinsics.rs:1860:14
     = note: inside `std::ptr::swap::<i32>` at /home/stein/rust/library/core/src/ptr/mod.rs:382:9
     = note: inside `core::slice::<impl [i32]>::reverse` at /home/stein/rust/library/core/src/slice/mod.rs:659:17
     = note: inside `std::slice::merge_sort::<i32, [closure@std::slice::<impl [i32]>::sort::{closure#0}]>` at /home/stein/rust/library/alloc/src/slice.rs:996:21
     = note: inside `std::slice::<impl [i32]>::sort` at /home/stein/rust/library/alloc/src/slice.rs:200:9
note: inside `main` at src/main.rs:4:5
    --> src/main.rs:4:5
     |
4    |     v.sort();
     |     ^^^^^^^^
     = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/stein/rust/library/core/src/ops/function.rs:227:5
     = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /home/stein/rust/library/std/src/sys_common/backtrace.rs:125:18
     = note: inside closure at /home/stein/rust/library/std/src/rt.rs:66: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/stein/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/stein/rust/library/std/src/panicking.rs:381:40
     = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/stein/rust/library/std/src/panicking.rs:345:19
     = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/stein/rust/library/std/src/panic.rs:396:14
     = note: inside `std::rt::lang_start_internal` at /home/stein/rust/library/std/src/rt.rs:51:25
     = note: inside `std::rt::lang_start::<()>` at /home/stein/rust/library/std/src/rt.rs:65:5

error: aborting due to previous error

Meta

• miri is from rustup's nightly 2020-11-02.
• lib is today's rust master 5629309 (and earlier)

[RalfJung]

FWIW, the interesting thing to track here would be ptr ID 5348, not the alloc ID.