Miri violation in std/src/sys/sgx/waitqueue/unsafe_list.rs

[Hoblovski]

As of Aug 7, 2023, the unsafe list implementation in sgx waitqueue has a violation against Stacked Borrows.
Here is the playground link; executing it with miri produces an error.

......

error: Undefined Behavior: trying to retag from <1601> for SharedReadOnly permission at alloc960[0x0], but that tag does not exist in the borrow stack for this location
   --> /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:377:18
    |
377 |         unsafe { &*self.as_ptr().cast_const() }
    |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |                  |
    |                  trying to retag from <1601> for SharedReadOnly permission at alloc960[0x0], but that tag does not exist in the borrow stack for this location
    |                  this error occurs as part of retag at alloc960[0x0..0x18]
    |
    = 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

......

I basically copy-pasted library/std/src/sys/sgx/waitqueue/unsafe_list{.rs,/tests.rs} into the playground link. I made a few minor modifications that should not affect the result:

• Changed use crate::ptr::NonNull to use std::ptr::NonNull and rtassert!(...) to assert!(...)
• Manually invokes the push_pop() test in main() (other test cases exhibit the same error)

It looks like an actual violation to me. Because

• self.head_tail is a mutable reborrow from self.head_tail_entry constructed in init()
• Later in pop(), the compiler retags (which is a Stacked Borrows rule) fields of self, invalidating any old references to its fields including self.head_tail.
• In the is_empty() called by pop(), we try to use the invalidated pointer.

The last change to unsafe_list.rs was two years ago and it's a private module only used in sys/sgx/waitqueue, so the problem might not be that severe.
Still, I wonder whether this is a false positive of miri, or can we confirm it's a Stacked Borrows/memory-safety violation.

[Noratrieb]

@raoulstrackx i see you have a PR touching the waitqueue

[raoulstrackx]

Hi @Nilstrieb I'm not familiar with Stacked Borrows but I took another look at the waitqueue code. If I read your comment correctly, the retagging upon a pop() will cause all references in UnsafeList to be invalidated. But UnsafeList relies on UnsafeList::head_tail_entry to be either:

• None
• Or Some and then (and only then) UnsafeList::head_tail must point to its UnsafeList::head_tail_entry entry.
  The latter does not holds in the Stacked Borrows logic. I don't see a way for this to go wrong in waitqueue's case. So I think the Stacked Borrows logic is overly aggressive in this case. Does that make sense?

[Hoblovski]

Also, I'm not sure why the code uses head_tail: NonNull::new_unchecked(1 as _) (miri complains about it too). I think we can replace it with the idiomatic NonNull::dangling()?

[Hoblovski]

I think the comment of @raoulstrackx makes sense. In this case I suppose miri is a bit pedantic (not sure though I am quite new to Stacked Borrows myself).

I have experimented with pieces of simplified code.
For function-entry retags, miri is a bit over concerned with fields that has the type of Pointer<Self>.
I'll take a deeper look at miri and try to figure out their implementation, and maybe submit an issue there.

[Noratrieb]

About stacked borrows, check out https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md

I don't think Miri is wrong here. Miri faithfully implements stacked borrows. Stacked borrows are known to be more strict than ideal, and the new tree borrows is less strict (probably too lax) so it's also worth trying out that using the Miri flag, but in general for now it's a good idea to have all code in std conform with stacked borrows.

[RalfJung]

For function-entry retags, miri is a bit over concerned with fields that has the type of Pointer.

It's not just Miri, we also tell LLVM that these fields are noalias dereferenceable. Miri isn't doing this just for fun. :)

It sounds like this code mixes references and raw pointers in a subtle way -- maybe we'll end up declaring this correct, maybe not, it's certainly in a gray area. Ideally when there is aliasing like that, you just use raw pointers everywhere and avoid using references entirely, then the code is "obviously" correct. Mixing references and raw pointers to the same data should only be done with the utmost care and when absolutely necessary.

Is there a reason this code cannot use raw pointers throughout?

[RalfJung]

Looking at the code, this looks like an intrusive collection. Those are well-known to not be compatible with Rust references (unless you use shared references and UnsafeCell). There's an active RFC intended to fix that: rust-lang/rfcs#3467. Until that is accepted, the advice is to use pinning. Adding a PhantomPinned to your UnsafeListEntry will fix the Miri error, but note that this is a temporary hack introduced for the async fn ecosystem and not something that is guaranteed to keep working indefinitely.

[Hoblovski]

Thank you, Ralf!
Stacked/Tree Borrows are great tools and I definitely love to use them.

For function-entry retags, miri is a bit over concerned with fields that has the type of Pointer.

It's not just Miri, we also tell LLVM that these fields are noalias dereferenceable. Miri isn't doing this just for fun. :)

I mentioned "over concerned" because when I tried to simplify the unsafe list, I found stacked borrows handles this piece of code in a strange way. The existence of a null field somehow affects miri execution (the field does not involve any aliases).
I read the paper but did not get why, so I'll try checking stacked borrows code to find out what's going on.

[RalfJung]

The existence of a null field somehow affects miri execution (the field does not involve any aliases).

If you remove the field, Entry has size 0, so two &mut Entry never alias -- zero-sized types cannot overlap each other.

[Hoblovski]

The existence of a null field somehow affects miri execution (the field does not involve any aliases).

If you remove the field, Entry has size 0, so two &mut Entry never alias -- zero-sized types cannot overlap each other.

That made sense! Never occurred to me it was the ZSTs.

Thank you very much!