skiplist: Miri reports SB violation

[taiki-e]

Run MIRIFLAGS="-Zmiri-disable-isolation -Zmiri-ignore-leaks" cargo miri test -p crossbeam-skiplist on #871, than miri reports an SB violation.

git clone https://github.com/crossbeam-rs/crossbeam.git
cd crossbeam
git checkout epoch-fix-sb-violations
cargo update
MIRIFLAGS="-Zmiri-disable-isolation -Zmiri-ignore-leaks" \
  cargo miri test -p crossbeam-skiplist

output

test clear ... error: Undefined Behavior: trying to reborrow from <233450> for SharedReadWrite permission at alloc95738[0x80], but that tag does not exist in the borrow stack for this location
    --> /Users/taiki/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/slice/mod.rs:405:18
     |
405  |         unsafe { &*index.get_unchecked(self) }
     |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^
     |                  |
     |                  trying to reborrow from <233450> for SharedReadWrite permission at alloc95738[0x80], but that tag does not exist in the borrow stack for this location
     |                  this error occurs as part of a reborrow at alloc95738[0x80..0x88]
     |
     = 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: <233450> was created by a retag at offsets [0x80..0x80]
    --> /Users/taiki/projects/sources/crossbeam-rs/crossbeam/crossbeam-skiplist/src/base.rs:39:18
     |
39   |         unsafe { self.pointers.get_unchecked(index) }
     |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     = note: backtrace:
     = note: inside `core::slice::<impl [crossbeam_epoch::Atomic<crossbeam_skiplist::base::Node<i32, i32>>]>::get_unchecked::<usize>` at /Users/taiki/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/slice/mod.rs:405:18
note: inside `crossbeam_skiplist::SkipList::<i32, i32>::search_position::<i32>` at /Users/taiki/projects/sources/crossbeam-rs/crossbeam/crossbeam-skiplist/src/base.rs:781:24
    --> /Users/taiki/projects/sources/crossbeam-rs/crossbeam/crossbeam-skiplist/src/base.rs:781:24
     |
781  |                     && self.head[level - 1]
     |                        ^^^^^^^^^^^^^^^^^^^^
note: inside `crossbeam_skiplist::SkipList::<i32, i32>::insert_internal::<[closure@crossbeam_skiplist::SkipList<i32, i32>::insert::{closure#0}]>` at /Users/taiki/projects/sources/crossbeam-rs/crossbeam/crossbeam-skiplist/src/base.rs:871:26
    --> /Users/taiki/projects/sources/crossbeam-rs/crossbeam/crossbeam-skiplist/src/base.rs:871:26
     |
871  |                 search = self.search_position(&key, guard);
     |                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `crossbeam_skiplist::SkipList::<i32, i32>::insert` at /Users/taiki/projects/sources/crossbeam-rs/crossbeam/crossbeam-skiplist/src/base.rs:1085:9
    --> /Users/taiki/projects/sources/crossbeam-rs/crossbeam/crossbeam-skiplist/src/base.rs:1085:9
     |
1085 |         self.insert_internal(key, || value, true, guard)
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `clear` at crossbeam-skiplist/tests/base.rs:829:9
    --> crossbeam-skiplist/tests/base.rs:829:9
     |
829  |         s.insert(x, x * 10, guard);
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure at crossbeam-skiplist/tests/base.rs:825:1
    --> crossbeam-skiplist/tests/base.rs:825:1
     |
824  |   #[test]
     |   ------- in this procedural macro expansion
825  | / fn clear() {
826  | |     let guard = &mut epoch::pin();
827  | |     let s = SkipList::new(epoch::default_collector().clone());
828  | |     for &x in &[4, 2, 12, 8, 7, 11, 5] {
...    |
836  | |     assert_eq!(s.len(), 0);
837  | | }
     | |_^
     = 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 previous error

[Imberflur]

I think this is also an instance of rust-lang/unsafe-code-guidelines#256

With Tower<K, V> being a ZST, under SB a &Tower<K, V> will only have permission to access 0 bytes.

/// The tower of atomic pointers.
///
/// The actual size of the tower will vary depending on the height that a node
/// was allocated with.
#[repr(C)]
struct Tower<K, V> {
    pointers: [Atomic<Node<K, V>>; 0],
}

[Imberflur]

I experimented with some changes fixing this SB violation on top of the epoch-fix-sb-violations branch: Imberflur@9156396

This commit passes:

MIRIFLAGS="-Zmiri-disable-isolation -Zmiri-ignore-leaks" \
  cargo miri test -p crossbeam-skiplist