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

[tatsuya6502]

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'

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::<common::deque::DeqNode<common::timer_wheel::TimerNode<u32>>>::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<common::deque::DeqNode<common::timer_wheel::TimerNode<u32>>>>::map::<&common::deque::DeqNode<common::timer_wheel::TimerNode<u32>>, {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::<common::timer_wheel::TimerNode<u32>>::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::<u32>::reset_timer_node_positions`
   --> src/common/timer_wheel.rs:335:16
    |
335 |         while !deque.peek_back().unwrap().element.is_sentinel() {
    |                ^^^^^^^^^^^^^^^^^
note: inside `<common::timer_wheel::TimerEventsIter<'_, u32> 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'

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::<common::timer_wheel::TimerNode<u32>>::move_to_back` at src/common/deque.rs:208:13: 208:46
note: inside `common::deque::Deque::<common::timer_wheel::TimerNode<u32>>::move_front_to_back`
   --> src/common/deque.rs:225:22
    |
225 |             unsafe { self.move_to_back(node) };
    |                      ^^^^^^^^^^^^^^^^^^^^^^^
note: inside `common::timer_wheel::TimerWheel::<u32>::reset_timer_node_positions`
   --> src/common/timer_wheel.rs:336:13
    |
336 |             deque.move_front_to_back();
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `<common::timer_wheel::TimerEventsIter<'_, u32> 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]

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.