Unupdated crossbeam dependency makes MIRI angry

[levs57]

I am testing my code in MIRI, and apparently a version of crossbeam used by rayon (0.8.0) uses integer-pointer casts, which are discouraged.

I'm observing the following error:

error: Undefined Behavior: trying to retag from <3916922> for SharedReadWrite permission at alloc1723074[0x8], but that tag does not exist in the borrow stack for this location
   --> /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-epoch-0.9.18/src/internal.rs:549:9
    |
549 |         &*local_ptr
    |         ^^^^^^^^^^^
    |         |
    |         trying to retag from <3916922> for SharedReadWrite permission at alloc1723074[0x8], but that tag does not exist in the borrow stack for this location
    |         this error occurs as part of retag at alloc1723074[0x0..0x180]
    |
    = 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: <3916922> was created by a SharedReadWrite retag at offsets [0x0..0x8]
   --> /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-epoch-0.9.18/src/internal.rs:548:26
    |
548 |         let local_ptr = (entry as *const Entry).cast::<Self>();
    |                          ^^^^^
    = note: BACKTRACE (of the first span) on thread `unnamed-2`:
    = note: inside `<crossbeam_epoch::internal::Local as crossbeam_epoch::sync::list::IsElement<crossbeam_epoch::internal::Local>>::element_of` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-epoch-0.9.18/src/internal.rs:549:9: 549:20
    = note: inside `<crossbeam_epoch::sync::list::Iter<'_, crossbeam_epoch::internal::Local, crossbeam_epoch::internal::Local> as std::iter::Iterator>::next` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-epoch-0.9.18/src/sync/list.rs:290:37: 290:53
    = note: inside `crossbeam_epoch::internal::Global::try_advance` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-epoch-0.9.18/src/internal.rs:235:22: 235:45
    = note: inside `crossbeam_epoch::internal::Global::collect` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-epoch-0.9.18/src/internal.rs:200:28: 200:51
    = note: inside `crossbeam_epoch::internal::Local::pin` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-epoch-0.9.18/src/internal.rs:435:17: 435:46
    = note: inside `crossbeam_epoch::collector::LocalHandle::pin` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-epoch-0.9.18/src/collector.rs:81:18: 81:37
    = note: inside closure at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-epoch-0.9.18/src/default.rs:40:26: 40:38
    = note: inside closure at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-epoch-0.9.18/src/default.rs:60:23: 60:27
    = note: inside `std::thread::LocalKey::<crossbeam_epoch::collector::LocalHandle>::try_with::<{closure@crossbeam_epoch::default::with_handle<{closure@crossbeam_epoch::default::pin::{closure#0}}, crossbeam_epoch::guard::Guard>::{closure#0}}, crossbeam_epoch::guard::Guard>` at /home/khaaru/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/thread/local.rs:283:12: 283:27
    = note: inside `crossbeam_epoch::default::with_handle::<{closure@crossbeam_epoch::default::pin::{closure#0}}, crossbeam_epoch::guard::Guard>` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-epoch-0.9.18/src/default.rs:59:5: 60:28
    = note: inside `crossbeam_epoch::default::pin` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-epoch-0.9.18/src/default.rs:40:5: 40:39
    = note: inside `crossbeam_deque::deque::Stealer::<rayon_core::job::JobRef>::steal` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crossbeam-deque-0.8.5/src/deque.rs:645:22: 645:34
    = note: inside `rayon_core::registry::WorkerThread::take_local_job` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.12.1/src/registry.rs:751:19: 751:39
    = note: inside `rayon_core::registry::WorkerThread::wait_until_cold` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.12.1/src/registry.rs:785:32: 785:53
    = note: inside `rayon_core::registry::WorkerThread::wait_until::<rayon_core::latch::OnceLatch>` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.12.1/src/registry.rs:769:13: 769:40
    = note: inside `rayon_core::registry::WorkerThread::wait_until_out_of_work` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.12.1/src/registry.rs:818:9: 818:65
    = note: inside `rayon_core::registry::main_loop` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.12.1/src/registry.rs:923:5: 923:43
    = note: inside `rayon::ThreadBuilder::run` at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.12.1/src/registry.rs:53:18: 53:33
    = note: inside closure at /home/khaaru/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.12.1/src/registry.rs:98:20: 98:32
    = note: inside `std::sys::backtrace::__rust_begin_short_backtrace::<{closure@<rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{closure#0}}, ()>` at /home/khaaru/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/backtrace.rs:155:18: 155:21
    = note: inside closure at /home/khaaru/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/thread/mod.rs:542:17: 542:71
    = note: inside `<std::panic::AssertUnwindSafe<{closure@std::thread::Builder::spawn_unchecked_<'_, '_, {closure@<rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{closure#0}}, ()>::{closure#2}::{closure#0}}> as std::ops::FnOnce<()>>::call_once` at /home/khaaru/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/panic/unwind_safe.rs:272:9: 272:19
    = note: inside `std::panicking::r#try::do_call::<std::panic::AssertUnwindSafe<{closure@std::thread::Builder::spawn_unchecked_<'_, '_, {closure@<rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{closure#0}}, ()>::{closure#2}::{closure#0}}>, ()>` at /home/khaaru/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:553:40: 553:43
    = note: inside `std::panicking::r#try::<(), std::panic::AssertUnwindSafe<{closure@std::thread::Builder::spawn_unchecked_<'_, '_, {closure@<rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{closure#0}}, ()>::{closure#2}::{closure#0}}>>` at /home/khaaru/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:517:19: 517:88
    = note: inside `std::panic::catch_unwind::<std::panic::AssertUnwindSafe<{closure@std::thread::Builder::spawn_unchecked_<'_, '_, {closure@<rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{closure#0}}, ()>::{closure#2}::{closure#0}}>, ()>` at /home/khaaru/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:350:14: 350:33
    = note: inside closure at /home/khaaru/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/thread/mod.rs:541:30: 543:16
    = note: inside `<{closure@std::thread::Builder::spawn_unchecked_<'_, '_, {closure@<rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{closure#0}}, ()>::{closure#2}} as std::ops::FnOnce<()>>::call_once - shim(vtable)` at /home/khaaru/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:250:5: 250:71
    = note: inside `<std::boxed::Box<dyn std::ops::FnOnce()> as std::ops::FnOnce<()>>::call_once` at /home/khaaru/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:2062:9: 2062:52
    = note: inside `<std::boxed::Box<std::boxed::Box<dyn std::ops::FnOnce()>> as std::ops::FnOnce<()>>::call_once` at /home/khaaru/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:2062:9: 2062:52
    = note: inside `std::sys::pal::unix::thread::Thread::new::thread_start` at /home/khaaru/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys/pal/unix/thread.rs:108:17: 108:64

I think it should be fixed (see this issue: crossbeam-rs/crossbeam#957 , resolved by this pull crossbeam-rs/crossbeam#796 ); but I think that rayon uses earlier version of crossbeam.

[adamreichold]

rayon-core depends on crossbeam-deque = "0.8.1", i.e. at least version 0.8.1 or semver-compatible newer versions. As indicated by your backtrace, version 0.8.5 was used which is indeed the latest release for crossbeam-deque and transitively pulls in crossbeam-epoch version 0.9.18, also the latest release for that crate.

So the error you see is not due to an outdated dependency and possibly also unrelated to pointer-to-integer casts. (Miri complains about the stacked borrows model being violated, not provenance issues.)

Could you provide some minimal example so others can reproduce the issue including the flags passed to Miri?

[zinkkkk]

I came across this same bug when using miri.

Using a simple parallel iterator loop example i just grabbed from a google search causes it, both in windows and linux (wsl).

running with $env:MIRIFLAGS="-Zmiri-permissive-provenance"; cargo miri run

fn main() {
    let vec1 = vec![1, 2, 3, 4, 5];
    let vec2 = vec![6, 7, 8, 9, 10];

    let dot_product: i32 = vec1.par_iter()
                            .zip(vec2.par_iter())
                            .map(|(&x, &y)| x * y)
                            .sum();

    println!("{}", dot_product);
}

    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.01s
     Running `C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\bin\cargo-miri.exe runner target\miri\x86_64-pc-windows-msvc\debug\rayonbug.exe`
error: Undefined Behavior: trying to retag from <48199> for SharedReadWrite permission at alloc19391[0x8], but that tag does not exist in the borrow stack for this location
   --> C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-epoch-0.9.18\src\internal.rs:549:9
    |
549 |         &*local_ptr
    |         ^^^^^^^^^^^
    |         |
    |         trying to retag from <48199> for SharedReadWrite permission at alloc19391[0x8], but that tag does not exist in the borrow stack for 
this location
    |         this error occurs as part of retag at alloc19391[0x0..0x180]
    |
    = 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: <48199> was created by a SharedReadWrite retag at offsets [0x0..0x8]
   --> C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-epoch-0.9.18\src\internal.rs:548:26
    |
548 |         let local_ptr = (entry as *const Entry).cast::<Self>();
    |                          ^^^^^
    = note: BACKTRACE (of the first span) on thread `unnamed-1`:
    = note: inside `<crossbeam_epoch::internal::Local as crossbeam_epoch::sync::list::IsElement<crossbeam_epoch::internal::Local>>::element_of` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-epoch-0.9.18\src\internal.rs:549:9: 549:20
    = note: inside `<crossbeam_epoch::sync::list::Iter<'_, crossbeam_epoch::internal::Local, crossbeam_epoch::internal::Local> as std::iter::Iterator>::next` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-epoch-0.9.18\src\sync\list.rs:290:37: 290:53
    = note: inside `crossbeam_epoch::internal::Global::try_advance` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-epoch-0.9.18\src\internal.rs:235:22: 235:45
    = note: inside `crossbeam_epoch::internal::Global::collect` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-epoch-0.9.18\src\internal.rs:200:28: 200:51
    = note: inside `crossbeam_epoch::internal::Local::pin` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-epoch-0.9.18\src\internal.rs:435:17: 435:46
    = note: inside `crossbeam_epoch::collector::LocalHandle::pin` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-epoch-0.9.18\src\collector.rs:81:18: 81:37
    = note: inside closure at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-epoch-0.9.18\src\default.rs:40:26: 40:38
    = note: inside closure at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-epoch-0.9.18\src\default.rs:60:23: 60:27
    = note: inside `std::thread::LocalKey::<crossbeam_epoch::collector::LocalHandle>::try_with::<{closure@crossbeam_epoch::default::with_handle<{closure@crossbeam_epoch::default::pin::{closure#0}}, crossbeam_epoch::guard::Guard>::{closure#0}}, crossbeam_epoch::guard::Guard>` at C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\thread\local.rs:283:12: 283:27
    = note: inside `crossbeam_epoch::default::with_handle::<{closure@crossbeam_epoch::default::pin::{closure#0}}, crossbeam_epoch::guard::Guard>` 
at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-epoch-0.9.18\src\default.rs:59:5: 60:28
    = note: inside `crossbeam_epoch::default::pin` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-epoch-0.9.18\src\default.rs:40:5: 40:39
    = note: inside `crossbeam_deque::deque::Stealer::<rayon_core::job::JobRef>::steal` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\crossbeam-deque-0.8.5\src\deque.rs:645:22: 645:34
    = note: inside `rayon_core::registry::WorkerThread::take_local_job` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\rayon-core-1.12.1\src\registry.rs:751:19: 751:39
    = note: inside `rayon_core::registry::WorkerThread::wait_until_cold` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\rayon-core-1.12.1\src\registry.rs:785:32: 785:53
    = note: inside `rayon_core::registry::WorkerThread::wait_until::<rayon_core::latch::OnceLatch>` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\rayon-core-1.12.1\src\registry.rs:769:13: 769:40
    = note: inside `rayon_core::registry::WorkerThread::wait_until_out_of_work` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\rayon-core-1.12.1\src\registry.rs:818:9: 818:65
    = note: inside `rayon_core::registry::main_loop` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\rayon-core-1.12.1\src\registry.rs:923:5: 923:43
    = note: inside `rayon::ThreadBuilder::run` at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\rayon-core-1.12.1\src\registry.rs:53:18: 53:33
    = note: inside closure at C:\Users\levia\.cargo\registry\src\index.crates.io-6f17d22bba15001f\rayon-core-1.12.1\src\registry.rs:98:20: 98:32  
    = note: inside `std::sys::backtrace::__rust_begin_short_backtrace::<{closure@<rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{closure#0}}, ()>` at C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\sys\backtrace.rs:154:18: 154:21
    = note: inside closure at C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\thread\mod.rs:522:17: 522:71
    = note: inside `<std::panic::AssertUnwindSafe<{closure@std::thread::Builder::spawn_unchecked_<'_, {closure@<rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{closure#0}}, ()>::{closure#1}::{closure#0}}> as std::ops::FnOnce<()>>::call_once` at C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\panic\unwind_safe.rs:272:9: 272:19
    = note: inside `std::panicking::r#try::do_call::<std::panic::AssertUnwindSafe<{closure@std::thread::Builder::spawn_unchecked_<'_, {closure@<rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{closure#0}}, ()>::{closure#1}::{closure#0}}>, ()>` at C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panicking.rs:557:40: 557:43
    = note: inside `std::panicking::r#try::<(), std::panic::AssertUnwindSafe<{closure@std::thread::Builder::spawn_unchecked_<'_, {closure@<rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{closure#0}}, ()>::{closure#1}::{closure#0}}>>` at C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panicking.rs:520:19: 520:88
    = note: inside `std::panic::catch_unwind::<std::panic::AssertUnwindSafe<{closure@std::thread::Builder::spawn_unchecked_<'_, {closure@<rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{closure#0}}, ()>::{closure#1}::{closure#0}}>, ()>` at C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panic.rs:348:14: 348:33
    = note: inside closure at C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\thread\mod.rs:521:30: 523:16
    = note: inside `<{closure@std::thread::Builder::spawn_unchecked_<'_, {closure@<rayon_core::registry::DefaultSpawn as rayon_core::registry::ThreadSpawn>::spawn::{closure#0}}, ()>::{closure#1}} as std::ops::FnOnce<()>>::call_once - shim(vtable)` at C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\ops\function.rs:250:5: 250:71
    = note: inside `<std::boxed::Box<dyn std::ops::FnOnce()> as std::ops::FnOnce<()>>::call_once` at C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\alloc\src\boxed.rs:2453:9: 2453:52
    = note: inside `<std::boxed::Box<std::boxed::Box<dyn std::ops::FnOnce()>> as std::ops::FnOnce<()>>::call_once` at C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\alloc\src\boxed.rs:2453:9: 2453:52
    = note: inside `std::sys::pal::windows::thread::Thread::new::thread_start` at C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\sys\pal\windows\thread.rs:55:22: 55:69

error: aborting due to 1 previous error

error: process didn't exit successfully: `C:\Users\levia\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\bin\cargo-miri.exe runner target\miri\x86_64-pc-windows-msvc\debug\rayonbug.exe` (exit code: 1)
PS C:\Users\levia\Documents\Code\rayonbug>```

[cuviper]

Miri is happier with -Zmiri-tree-borrows, although you can't mix that with -Zmiri-permissive-provenance so that give a warning instead. Either way, this happens even with the latest versions of the crossbeam dependencies, and there's nothing rayon can do to fix that, apart from choosing an entirely different deque implementation.

cc crossbeam-rs/crossbeam#545