Miri detects MPSC as having UB according to stacked borrows

[Michael-F-Bryan]

While using -Zmiri-track-raw-pointers to test provenance on some unsafe code I was writing, cargo miri test detected possible undefined behaviour according to the stacked borrows model. This makes it impossible to use miri-track-raw-pointers flag on an entire test suite.

Steps to reproduce:

$ cd /tmp
$ cargo new --lib temp
     Created library `temp` package
$ MIRIFLAGS="-Zmiri-track-raw-pointers" cargo miri test --verbose
...
error: Undefined Behavior: trying to reborrow for SharedReadWrite at alloc65629, but parent tag <untagged> does not have an appropriate item in the borrow stack
  --> /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sync/mpsc/mpsc_queue.rs:73:13
   |
73 |             (*prev).next.store(n, Ordering::Release);
   |             ^^^^^^^^^^^^

   |
   = 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.50.0-nightly (1f5bc176b 2020-12-19)
binary: rustc
commit-hash: 1f5bc176b0e54a8e464704adcd7e571700207fe9
commit-date: 2020-12-19
host: x86_64-unknown-linux-gnu
release: 1.50.0-nightly

$ cargo --version --verbose
cargo 1.50.0-nightly (a3c2627fb 2020-12-14)
release: 1.50.0
commit-hash: a3c2627fbc2f5391c65ba45ab53b81bf71fa323c
commit-date: 2020-12-14

$ cargo miri --version
miri 0.1.0 (2065b52 2020-12-11)

(Full Backtrace)

$ RUST_BACKTRACE=full MIRIFLAGS="-Zmiri-track-raw-pointers" cargo miri test --verbose
   Compiling temp v0.1.0 (/tmp/temp)
     Running `/home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/cargo-miri rustc --crate-name temp --edition=2018 src/lib.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type lib --emit=dep-info,metadata,link -C embed-bitcode=no -C debuginfo=2 -C metadata=397d4e79e9476f01 -C extra-filename=-397d4e79e9476f01 --out-dir /tmp/temp/target/x86_64-unknown-linux-gnu/debug/deps --target x86_64-unknown-linux-gnu -C linker=/usr/bin/clang -C incremental=/tmp/temp/target/x86_64-unknown-linux-gnu/debug/incremental -L dependency=/tmp/temp/target/x86_64-unknown-linux-gnu/debug/deps -L dependency=/tmp/temp/target/debug/deps -C link-arg=-fuse-ld=lld`
     Running `/home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/cargo-miri rustc --crate-name temp --edition=2018 src/lib.rs --error-format=json --json=diagnostic-rendered-ansi --emit=dep-info,link -C embed-bitcode=no -C debuginfo=2 --test -C metadata=095a78e43e82b177 -C extra-filename=-095a78e43e82b177 --out-dir /tmp/temp/target/x86_64-unknown-linux-gnu/debug/deps --target x86_64-unknown-linux-gnu -C linker=/usr/bin/clang -C incremental=/tmp/temp/target/x86_64-unknown-linux-gnu/debug/incremental -L dependency=/tmp/temp/target/x86_64-unknown-linux-gnu/debug/deps -L dependency=/tmp/temp/target/debug/deps -C link-arg=-fuse-ld=lld`
    Finished test [unoptimized + debuginfo] target(s) in 0.12s
     Running `/home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/cargo-miri /tmp/temp/target/x86_64-unknown-linux-gnu/debug/deps/temp-095a78e43e82b177`

running 1 test
test tests::it_works ... error: Undefined Behavior: trying to reborrow for SharedReadWrite at alloc65629, but parent tag <untagged> does not have an appropriate item in the borrow stack
  --> /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sync/mpsc/mpsc_queue.rs:73:13
   |
73 |             (*prev).next.store(n, Ordering::Release);
   |             ^^^^^^^^^^^^

   |
   = 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::sync::mpsc::mpsc_queue::Queue::<tests::test::event::CompletedTest>::push` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sync/mpsc/mpsc_queue.rs:73:13
   = note: inside `std::sync::mpsc::shared::Packet::<tests::test::event::CompletedTest>::send` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sync/mpsc/shared.rs:166:9
   = note: inside `std::sync::mpsc::Sender::<tests::test::event::CompletedTest>::send` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sync/mpsc/mod.rs:794:45
   = note: inside `tests::test::run_test_in_process` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:552:5
   = note: inside closure at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:449:39
   = note: inside `tests::test::run_test::run_test_inner` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:474:13
   = note: inside `tests::test::run_test` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:504:28
   = note: inside `tests::test::run_tests::<[closure@tests::test::run_tests_console::{closure#2}]>` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:283:13
   = note: inside `tests::test::run_tests_console` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/console.rs:289:5
   = note: inside `tests::test::test_main` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:121:15
   = note: inside `tests::test::test_main_static` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/test/src/lib.rs:140:5
   = note: inside `main`
   = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/michael/.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/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:125:18
   = note: inside closure at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/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/michael/.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/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:379:40
   = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:343:19
   = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:396:14
   = note: inside `std::rt::lang_start_internal` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:51:25
   = note: inside `std::rt::lang_start::<()>` at /home/michael/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:65:5

error: aborting due to previous error

error: test failed, to rerun pass '--lib'

[RalfJung]

Note than an error with -Zmiri-track-raw-pointers is not necessarily a bug -- that flag has false positives; that's why it is not enabled by default. In particular, it basically breaks casting integers to pointers and using those pointers for anything.

The error message talks about <untagged>, so this looks to me like there is indeed a ptr-int cast going on. Without having checked the code yet, I think this is not necessarily a bug in MPSC. (The exact rules around Stacked Borrows and ptr-int casts are not clear yet, so there might be a bug, but we currently do not have a precise enough definition to say one way or the other. Casting integers to pointers is complicated.)

[RalfJung]

You didn't even show any code... are you saying that the error comes up even for an empty test suite? Hm yeah I can see how that would be annoying.^^

The issue is probably caused by AtomicPtr::swap, which performs int-ptr casts. @oli-obk do you think your approach from #77611 would also work for this operation?

[Michael-F-Bryan]

You didn't even show any code... are you saying that the error comes up even for an empty test suite? Hm yeah I can see how that would be annoying.^^

Correct. I was able to narrow it down to the default it_works test.

The error message talks about , so this looks to me like there is indeed a ptr-int cast going on. Without having checked the code yet, I think this is not necessarily a bug in MPSC. (The exact rules around Stacked Borrows and ptr-int casts are not clear yet, so there might be a bug, but we currently do not have a precise enough definition to say one way or the other. Casting integers to pointers is complicated.)

I had a feeling something like that was going on after your comments on Zulip but thought it might be useful to create an issue regardless.

That way you've got some examples of false positives, and if the issue is recorded elsewhere it's easy enough to close as a duplicate.