Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

epoch: Miri reports SB violation #545

Open
YoshikiTakashima opened this issue Aug 19, 2020 · 12 comments · May be fixed by #871
Open

epoch: Miri reports SB violation #545

YoshikiTakashima opened this issue Aug 19, 2020 · 12 comments · May be fixed by #871

Comments

@YoshikiTakashima
Copy link

YoshikiTakashima commented Aug 19, 2020

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
Copy link
Contributor

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
Copy link

ghost commented Aug 31, 2020

@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
Copy link
Contributor

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
Copy link
Author

@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
Copy link
Contributor

RalfJung commented Sep 2, 2020

@stjepang the problem is somewhere in this function:

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:

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
Copy link
Contributor

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
Copy link
Contributor

RalfJung commented Sep 2, 2020

@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
Copy link

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

@RalfJung
Copy link
Contributor

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

@taiki-e taiki-e linked a pull request Jul 20, 2022 that will close this issue
@RalfJung
Copy link
Contributor

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
Copy link
Member

taiki-e commented Jul 22, 2022

@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

bors bot added a commit that referenced this issue Jul 23, 2022
796: epoch: Remove ptr-to-int casts r=taiki-e a=taiki-e

Use [this hack](rust-lang/miri#1866 (comment)) to fix compatibility issues with Miri (see #490 (comment) for details). 

Due to the #545, still not compatible with stacked borrows. This will be fixed by the subsequent PR (#871).

Note: this is a breaking change because changes API of Pointable and Pointer traits

Fixes #579

881: Remove deprecated items r=taiki-e a=taiki-e

This removes the following deprecated items:

- crossbeam-epoch:
  - `CompareAndSetError`
  - `CompareAndSetOrdering`
  - `Atomic::compare_and_set`
  - `Atomic::compare_and_set_weak`
- crossbeam-utils:
  - `AtomicCell::compare_and_swap`

Co-authored-by: Taiki Endo <[email protected]>
bors bot added a commit that referenced this issue Jul 23, 2022
796: epoch: Remove ptr-to-int casts r=taiki-e a=taiki-e

Use [this hack](rust-lang/miri#1866 (comment)) to fix compatibility issues with Miri (see #490 (comment) for details). 

Due to the #545, still not compatible with stacked borrows. This will be fixed by the subsequent PR (#871).

Note: this is a breaking change because changes API of Pointable and Pointer traits

Fixes #579

Co-authored-by: Taiki Endo <[email protected]>
@taiki-e taiki-e changed the title MIRI reports UB in crossbeam::epoch::Collector's deallocation epoch: Miri reports SB violation Jun 17, 2023
@taiki-e taiki-e removed the bug label Jun 18, 2023
@Imberflur
Copy link

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).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Development

Successfully merging a pull request may close this issue.

6 participants