epoch: Miri reports SB violation

[YoshikiTakashima]

UPDATE(taiki-e): The error originally reported here no longer exists. See #545 (comment) for the remaining SB violations currently reported. The fix for SB violations in epoch exists in #871, and using that branch or using TB (-Zmiri-tree-borrows) instead of SB should fix problems.

---

Hello.

Another MIRI unbounded behavior for destructors, this time in Collector.

 let x1_0: crossbeam::epoch::Collector = crossbeam::epoch::Collector::new();//LAYER:0
 let x2_0: & crossbeam::epoch::Collector = & x1_0;//LAYER:1
 let x3_0: crossbeam::epoch::LocalHandle = x2_0.register();//LAYER:2

Running this gives the MIRI error at deallocation:

error: Undefined Behavior: deallocating while item is protected: [SharedReadWrite for <235744> (call 76130)]
<trace>

I am not super familiar with your internal memory structure, but this may be related to a similar issue seen in another garbage collection implementation. Maybe it will help with the patch.

A code file with a full trace attached. It looks a little weird because the test case was automatically generated.

As for the impact of this issue, it doesn't seem to be too big of an issue as it is mostly contained. Use-after-free should not be possible unless something else happens during dealloc. I can't be 100% sure because Miri stops at that point, but looking at the code in list.rs, it looks okay. It may become more problematic if people start adding more unsafe functions that expose internal memory in some way.

Thanks
~Yoshi

[RalfJung]

The full error message says that this is a Stacked Borrows violation. So, there's an aliasing problem, nothing like use-after-free.

@YoshikiTakashima you could run this with -Zmiri-disable-stacked-borrows to see if other problems show up.

[ghost]

@RalfJung Since the concept of stacked borrows is still in development and shaping up (at least that's my understanding), what's your suggestion on how to treat miri reports like these? Do you think we should strive to eliminate all warnings one by one? Or should we take note of them and wait for stacked borrows to be finalized and accepted into the Rust standard?

[RalfJung]

It would be good to understand what happens, to determine if this is code that should be fixed (and if there is a good way to do that) or a case of Stacked Borrows being too restrictive.

"Deallocated while item is protected" is not a common error, so this seems rather suspicious.

[YoshikiTakashima]

@stjepang and @RalfJung, I reran with -Zmiri-disable-stacked-borrows and it passes fine, no use-after-free, or any other UB except the one we already know. I forgot about this when I rushed some of the evals. Thanks for pointing it out.

[RalfJung]

@stjepang the problem is somewhere in this function:

crossbeam/crossbeam-epoch/src/internal.rs

Lines 615 to 617 in ce53365

	unsafe fn finalize(entry: &Entry, guard: &Guard) {
	guard.defer_destroy(Shared::from(Self::element_of(entry) as *const _));
	}

It looks like one of the two arguments that is passed by reference to this function is actually deallocated while that function is ongoing. That is UB; Rust declares function arguments dereferencable to LLVM which means LLVM may assume that the reference is live throughout the entire execution of the function.

The backtrace goes through this line, so it looks like indeed the entry is being deallocated:

crossbeam/crossbeam-epoch/src/guard.rs

Line 197 in ce53365

local.defer(Deferred::new(move || drop(f())), self);

Miri is actually currently extremely conservative about this kind of error; for good optimizations we likely want to make such liveness assumptions more than we currently do. Some related discussion: rust-lang/unsafe-code-guidelines#88, rust-lang/unsafe-code-guidelines#125.

[jeehoonkang]

It seems entry is immediately destroyed at line 616 without deferred. Actually, I liked Crossbeam's trick of deallocating an object in its own method, but apparently it's "too clever" :) @RalfJung do you have any workaround suggestions for this?

[RalfJung]

@jeehoonkang yeah, use raw pointers for things you want to deallocate. ;)

There's more to this discussion though, Arc has a similar bug: rust-lang/rust#55005. In particular see the lang-team meeting about this and the follow-up discussion that ensued. So another option that we considered besides "use raw pointers" is "do not add dereferencable to types with UnsafeCell". Entry contains an AtomicUsize, so if we applied that work-around on the language level, no changes in crossbeam would be needed.

[divergentdave]

FWIW, Counter in crossbeam-channel exhibits the same behavior, as discussed in rust-lang/miri#1535.

[RalfJung]

It is possible that rust-lang/miri#2248 might help here -- that change is enough to work around rust-lang/rust#55005.

[RalfJung]

Does this still occur now that rust-lang/miri#2248 has landed?
Also some of our error messages got better, so it'd be good to see what the error looks like today, if it still occurs.

[taiki-e]

@RalfJung: I believe the original SB violation reported in this issue (rust-lang/rust#55005) no longer exists, but there are several other SB violations.

One is the use of pointers that went through methods of InElement trait. Methods of InElement trait take and return references, so this requires converting the pointer to a reference, which drops the raw/mut provenance (IIUC), so SB violations are being reported during deallocation.

Reported error

test collector::tests::buffering ... error: Undefined Behavior: trying to reborrow from <301152> for SharedReadWrite permission at alloc123336[0x8], but that tag does not exist in the borrow stack for this location
   --> crossbeam-epoch/src/internal.rs:550:9
    |
550 |         &*local_ptr
    |         ^^^^^^^^^^^
    |         |
    |         trying to reborrow from <301152> for SharedReadWrite permission at alloc123336[0x8], but that tag does not exist in the borrow stack for this location
    |         this error occurs as part of a reborrow at alloc123336[0x8..0x10]
    |
    = 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: <301152> was created by a retag at offsets [0x0..0x8]
   --> crossbeam-epoch/src/internal.rs:547:26
    |
547 |         let local_ptr = (entry as *const Entry as *const u8)
    |                          ^^^^^
    = note: backtrace:
    = note: inside `<internal::Local as sync::list::IsElement<internal::Local>>::element_of` at crossbeam-epoch/src/internal.rs:550:9
note: inside `<sync::list::Iter<internal::Local, internal::Local> as std::iter::Iterator>::next` at crossbeam-epoch/src/sync/list.rs:290:37
   --> crossbeam-epoch/src/sync/list.rs:290:37
    |
290 |             return Some(Ok(unsafe { C::element_of(c) }));
    |                                     ^^^^^^^^^^^^^^^^
note: inside `internal::Global::try_advance` at crossbeam-epoch/src/internal.rs:236:22
   --> crossbeam-epoch/src/internal.rs:236:22
    |
236 |         for local in self.locals.iter(guard) {
    |                      ^^^^^^^^^^^^^^^^^^^^^^^
note: inside `internal::Global::collect` at crossbeam-epoch/src/internal.rs:201:28
   --> crossbeam-epoch/src/internal.rs:201:28
    |
201 |         let global_epoch = self.try_advance(guard);
    |                            ^^^^^^^^^^^^^^^^^^^^^^^
note: inside `internal::Local::pin` at crossbeam-epoch/src/internal.rs:434:17
   --> crossbeam-epoch/src/internal.rs:434:17
    |
434 |                 self.global().collect(&guard);
    |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `collector::LocalHandle::pin` at crossbeam-epoch/src/collector.rs:81:18
   --> crossbeam-epoch/src/collector.rs:81:18
    |
81  |         unsafe { (*self.local).pin() }
    |                  ^^^^^^^^^^^^^^^^^^^
note: inside `collector::tests::buffering` at crossbeam-epoch/src/collector.rs:257:26
   --> crossbeam-epoch/src/collector.rs:257:26
    |
257 |             let guard = &handle.pin();
    |                          ^^^^^^^^^^^^
note: inside closure at crossbeam-epoch/src/collector.rs:245:5
   --> crossbeam-epoch/src/collector.rs:245:5
    |
244 |       #[test]
    |       ------- in this procedural macro expansion
245 | /     fn buffering() {
246 | |         const COUNT: usize = 10;
247 | |         #[cfg(miri)]
248 | |         const N: usize = 500;
...   |
278 | |         assert_eq!(DESTROYS.load(Ordering::Relaxed), COUNT);
279 | |     }
    | |_____^
    = 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; 2 warnings emitted

The fix in #871 was to change IsElement's arguments/return types to pointers: a81e099#diff-13205636f82aa8e8cd7cc50eb810f3d9de2c0a9636e8e542b59ec1c606ffb348

And, a similar problem existed in the deref method of the Pointable trait, which returns a reference, which was used to create the pointer passed to methods of IsElement trait.
The fix in #871 was to change Pointable's deref and deref_mut methods to as_ptr/as_mut_ptr which returns a pointer: a81e099#diff-df0731defb6841d17a007b010d4e079c5eca21650262ce588ea5f5b17169a086

The last SB violation in epoch was impl<T> Pointable for [MaybeUninit<T>] creating a pointer of a slice via reference.

Reported error

test atomic::tests::array_init ... error: Undefined Behavior: trying to reborrow from <254406> for SharedReadOnly permission at alloc104909[0x8], 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/raw.rs:97:9
     |
97   |         &*ptr::slice_from_raw_parts(data, len)
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     |         |
     |         trying to reborrow from <254406> for SharedReadOnly permission at alloc104909[0x8], but that tag does not exist in the borrow stack for this location
     |         this error occurs as part of a reborrow at alloc104909[0x8..0x58]
     |
     = 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: <254406> was created by a retag at offsets [0x8..0x8]
    --> crossbeam-epoch/src/atomic.rs:284:19
     |
284  |         let ptr = (*array).elements.as_ptr();
     |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^
     = note: backtrace:
     = note: inside `std::slice::from_raw_parts::<std::mem::MaybeUninit<usize>>` at /Users/taiki/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/slice/raw.rs:97:9
note: inside `<[std::mem::MaybeUninit<usize>] as atomic::Pointable>::as_ptr` at crossbeam-epoch/src/atomic.rs:285:9
    --> crossbeam-epoch/src/atomic.rs:285:9
     |
285  |         slice::from_raw_parts(ptr, (*array).len)
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `<atomic::Owned<[std::mem::MaybeUninit<usize>]> as std::ops::Deref>::deref` at crossbeam-epoch/src/atomic.rs:1306:20
    --> crossbeam-epoch/src/atomic.rs:1306:20
     |
1306 |         unsafe { &*T::as_ptr(raw) }
     |                    ^^^^^^^^^^^^^^
note: inside `atomic::tests::array_init` at crossbeam-epoch/src/atomic.rs:1792:42
    --> crossbeam-epoch/src/atomic.rs:1792:42
     |
1792 |         let arr: &[MaybeUninit<usize>] = &owned;
     |                                          ^^^^^^
note: inside closure at crossbeam-epoch/src/atomic.rs:1790:5
    --> crossbeam-epoch/src/atomic.rs:1790:5
     |
1789 |       #[test]
     |       ------- in this procedural macro expansion
1790 | /     fn array_init() {
1791 | |         let owned = Owned::<[MaybeUninit<usize>]>::init(10);
1792 | |         let arr: &[MaybeUninit<usize>] = &owned;
1793 | |         assert_eq!(arr.len(), 10);
1794 | |     }
     | |_____^
     = 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

The fix in #871 was to use addr_of!.

There is also a SB violation in skiplist, but I'm not sure how to fix it.

Reported error

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

EDIT: filed issue #878 for SB violation in skiplist

[Imberflur]

The SB error with IsElement looks like a case of rust-lang/unsafe-code-guidelines#256

With SB the provenance of references is restricted to the range of the type that the reference points to. Whereas, with TB this aspect is relaxed, which seems to align with this error not showing up under TB.

I think this is complicated by the container type being !Freeze but luckily the field is also !Freeze (IIUC). If Entry was Freeze I suspect there would be issues even with TB: rust-lang/unsafe-code-guidelines#256 (comment).