search

moka-rs / moka

A high performance concurrent caching library for Rust
Apache License 2.0
1.63k stars 73 forks source link

Miri errors on the `timer_wheel` module. (Miri v0.1.0 8b2459c1 2024-04-09) #414

Closed tatsuya6502 closed 7 months ago

tatsuya6502 commented 7 months ago

Miri started to report errors on the test for the moka::common::timer_wheel module.

https://github.com/moka-rs/moka/actions/runs/8629705772/job/23654526179

$ cargo +nightly miri -V
miri 0.1.0 (8b2459c1 2024-04-09)

The errors change when Stacked Borrows is used, or [Tree Borrows]() is used.

Miri's Stacked Borrow

$ cargo +nightly miri test timer_wheel --features 'sync, future'
```console running 2 tests test common::timer_wheel::tests::test_advance ... error: Undefined Behavior: trying to retag from <704136> for SharedReadOnly permission at alloc237477[0x0], but that tag does not exist in the borrow stack for this location --> /Users/tatsuya/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:402:18 | 402 | unsafe { &*self.as_ptr().cast_const() } | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | | | trying to retag from <704136> for SharedReadOnly permission at alloc237477[0x0], but that tag does not exist in the borrow stack for this location | this error occurs as part of retag at alloc237477[0x0..0x28] | = 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: <704136> was created by a Unique retag at offsets [0x0..0x28] --> src/common/deque.rs:172:37 | 172 | let node = NonNull::new(Box::into_raw(node)).expect("Got a null ptr"); | ^^^^^^^^^^^^^^^^^^^ help: <704136> was later invalidated at offsets [0x0..0x28] by a SharedReadOnly retag --> src/common/timer_wheel.rs:517:55 | 517 | ... let entry_info = unsafe { node_p.as_ref() }.element.entry_info(); | ^^^^^^^^^^^^^^^ = note: BACKTRACE (of the first span) on thread `common::timer_wheel::tests::test_advance`: = note: inside `std::ptr::NonNull::>>::as_ref::<'_>` at /Users/tatsuya/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:402:18: 402:46 note: inside closure --> src/common/deque.rs:162:48 | 162 | self.tail.as_ref().map(|node| unsafe { node.as_ref() }) | ^^^^^^^^^^^^^ = note: inside `std::option::Option::<&std::ptr::NonNull>>>::map::<&common::deque::DeqNode>, {closure@src/common/deque.rs:162:32: 162:38}>` at /Users/tatsuya/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/option.rs:1072:29: 1072:33 note: inside `common::deque::Deque::>::peek_back` --> src/common/deque.rs:162:9 | 162 | self.tail.as_ref().map(|node| unsafe { node.as_ref() }) | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ note: inside `common::timer_wheel::TimerWheel::::reset_timer_node_positions` --> src/common/timer_wheel.rs:335:16 | 335 | while !deque.peek_back().unwrap().element.is_sentinel() { | ^^^^^^^^^^^^^^^^^ note: inside ` as std::iter::Iterator>::next` --> src/common/timer_wheel.rs:492:17 | 492 | / self.timer_wheel 493 | | .reset_timer_node_positions(self.level, i as usize); | |_______________________________________________________________________^ note: inside `common::timer_wheel::tests::test_advance` --> src/common/timer_wheel.rs:751:32 | 751 | assert_eq!(expired_key(expired_entries.next()), 1); | ^^^^^^^^^^^^^^^^^^^^^^ note: inside closure --> src/common/timer_wheel.rs:647:22 | 646 | #[test] | ------- in this procedural macro expansion 647 | fn test_advance() { | ^ = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info) note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace error: aborting due to 1 previous error error: test failed, to rerun pass `--lib` Caused by: process didn't exit successfully: `/Users/tatsuya/.rustup/toolchains/nightly-aarch64-apple-darwin/bin/cargo-miri runner /Users/tatsuya/Documents/git-repos-ssd/moka-rs/worktrees/fix-ci/moka-012-2/target/miri/aarch64-apple-darwin/debug/deps/moka-445381416204669a timer_wheel` (exit status: 1) note: test exited abnormally; to see the full output pass --nocapture to the harness. ```

Miri's Tree Borrow

$ MIRIFLAGS="-Zmiri-tree-borrows" cargo +nightly miri test timer_wheel --features 'sync, future'
```console running 2 tests test common::timer_wheel::tests::test_advance ... error: Undefined Behavior: write access through <679865> at alloc237007[0x20] is forbidden --> src/common/deque.rs:208:13 | 208 | (*next.as_ptr()).prev = node.prev; | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ write access through <679865> at alloc237007[0x20] is forbidden | = help: this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental = help: the accessed tag <679865> is a child of the conflicting tag <679827> = help: the conflicting tag <679827> has state Frozen which forbids this child write access help: the accessed tag <679865> was created here --> src/common/deque.rs:172:37 | 172 | let node = NonNull::new(Box::into_raw(node)).expect("Got a null ptr"); | ^^^^^^^^^^^^^^^^^^^ help: the conflicting tag <679827> was created here, in the initial state Reserved --> src/common/timer_wheel.rs:245:37 | 245 | let node = unsafe { Box::from_raw(node.as_ptr()) }; | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: the conflicting tag <679827> later transitioned to Active due to a child write access at offsets [0x20..0x28] --> src/common/deque.rs:171:13 | 171 | node.prev = self.tail; | ^^^^^^^^^^^^^^^^^^^^^ = help: this transition corresponds to the first write to a 2-phase borrowed mutable reference help: the conflicting tag <679827> later transitioned to Frozen due to a reborrow (acting as a foreign read access) at offsets [0x0..0x28] --> src/common/timer_wheel.rs:517:55 | 517 | ... let entry_info = unsafe { node_p.as_ref() }.element.entry_info(); | ^^^^^^^^^^^^^^^ = help: this transition corresponds to a loss of write permissions = note: BACKTRACE (of the first span) on thread `common::timer_wheel::tests::test_advance`: = note: inside `common::deque::Deque::>::move_to_back` at src/common/deque.rs:208:13: 208:46 note: inside `common::deque::Deque::>::move_front_to_back` --> src/common/deque.rs:225:22 | 225 | unsafe { self.move_to_back(node) }; | ^^^^^^^^^^^^^^^^^^^^^^^ note: inside `common::timer_wheel::TimerWheel::::reset_timer_node_positions` --> src/common/timer_wheel.rs:336:13 | 336 | deque.move_front_to_back(); | ^^^^^^^^^^^^^^^^^^^^^^^^^^ note: inside ` as std::iter::Iterator>::next` --> src/common/timer_wheel.rs:492:17 | 492 | / self.timer_wheel 493 | | .reset_timer_node_positions(self.level, i as usize); | |_______________________________________________________________________^ note: inside `common::timer_wheel::tests::test_advance` --> src/common/timer_wheel.rs:751:32 | 751 | assert_eq!(expired_key(expired_entries.next()), 1); | ^^^^^^^^^^^^^^^^^^^^^^ note: inside closure --> src/common/timer_wheel.rs:647:22 | 646 | #[test] | ------- in this procedural macro expansion 647 | fn test_advance() { | ^ = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info) note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace error: aborting due to 1 previous error error: test failed, to rerun pass `--lib` Caused by: process didn't exit successfully: `/Users/tatsuya/.rustup/toolchains/nightly-aarch64-apple-darwin/bin/cargo-miri runner /Users/tatsuya/Documents/git-repos-ssd/moka-rs/worktrees/fix-ci/moka-012-2/target/miri/aarch64-apple-darwin/debug/deps/moka-445381416204669a timer_wheel` (exit status: 1) note: test exited abnormally; to see the full output pass --nocapture to the harness. ```
tatsuya6502 commented 7 months ago

The error should be fixed by #416.

The code that was causing the error (Stacked Borrows/Tree Borrows violation) was enabled only when testing (#[cfg(test)]), so the release and debug builds had no issue.