Yoke vs noalias

[CAD97]

Even with C: StableDeref, moving the cart can potentially invalidate the yoke.

However, miri does not by default report any errors when using yoke. This is due to the fact that miri's aliasing analysis/retagging does not by-default recurse into private fields, so the box's uniqueness is never asserted, along with never giving mutable access to the carted data meaning uniqueness never needs to be asserted. -Zmiri-retag-fields exists to opt into the retagging of fields, which will surface this potential UB.

This is mostly to note that this potential issue is known; feel free to close if this is considered a non-issue.

Related:

• OwningRef is in conflict with noalias Kimundi/owning-ref-rs#49
• Soundness problems? Storyyeller/stable_deref_trait#15
• Stacked Borrows: Retag (private) fields of ADTs? rust-lang/unsafe-code-guidelines#125
• Stacked Borrows vs inner pointers into "stable-deref" types rust-lang/unsafe-code-guidelines#194
• What are the uniqueness guarantees of Box and Vec? rust-lang/unsafe-code-guidelines#326
• MaybeDangling rust-lang/rfcs#3336

[Manishearth]

Hmm, so Yokeable enforces covariance, which ought to protect us from issues like this involving interior mutability? That said, we have no such constraints on Carts.

In general Yoke should probably just disallow carts with interior mutability, we can perhaps do that by enforcing that the cart does not deref to a type containing interior mutability? We might need our own trait for that, Sync kinda does that but not fully because mutexes are allowed.

That does bring up the question: does this UB still exist with Mutex instead of Cell? I imagine so.

In our case most carts will be some pointer type wrapping some kind of simple data buffer ([u8], str, etc). We could even just have our own trait for this.

Do you think that would be sufficient to protect us from this bug?

[CAD97]

Apologies for the below footnote essay, this is a complicated topic involving open questions about how to write sound unsafe Rust. The footnotes should just be optional context.

The 100% surefire way is to store an into_rawed form of the cart and only from_raw it when its been deyoked. This isn't possible with the current API, since yoke allows fn backing_cart(&self) -> &C¹². replace_cart is I think the only other signature problem with this approach, but it could be done by making it take impl FnOnce(Cart<C>) -> C2 instead, where Cart<C> wraps the raw version of C to from_raw it on drop.

I've been meaning to write a crate to do this to suggest people replace stable_deref_trait for a while, actually...³

While that approach is 100% bulletproof w.r.t. aliasing⁵, it's not necessarily necessary. Instead, yoke could use a refined version of StableDeref which doesn't include Box or other types which are potentially noalias. This use of StableDeref is indeed sound in a vacuum, as the trait does promise that

the result of calling deref() is valid for the lifetime of the object, not just the lifetime of the borrow, and that the deref is valid even if the object is moved,

it's just that none of the std types ever actually guaranteed⁶ this. However, if you're willing to assume a reasonable quality of implementation from your standard library, we could define our own StableDeref trait for types we trust to not invalidate dereffed pointers when moved; I'm personally confident saying that &T is obviously safe, as well as Arc<T> and Rc<T>⁷.

A third status quo option is to bet on yoke's usage just never breaking. There is a lot more code out there doing yoke-like things (c.f. owning_ref, rental) and in a lot more questionably sound ways. Make a Miri job so that we'll know if/when it breaks; it's imho very unlikely that the situation will be made worse without a way to get the behavior we want from uniquely owning std pointers⁸.

Note that the problem is not shared mutability in the pointee (that's absolutely fine) and not even shared mutability before indirection (that's disallowed by StableDeref). The problem is specifically that the current aliasing semantics of Box as specified by Miri mean that moving a Box invalidates any pointers to its pointee, like a deref_mut [example].⁹

TL;DR (I don't blame you):

Three main options:

• 😀 Store into_rawed versions of the cart.
• 🙂 Use Pin and wrap the pointee as !Unpin
• 😐 Monitor for future developments

Any change for soundness I think also needs to replace access to &C with &<C as Deref>::Target to avoid reintroducing it.

Footnotes

1. In fact, doing so would necessitate handling the cart by-value to temporarily from_raw it, and likely turn this into a real unsoundness/miscompilation. ↩

2. A sound version is -> <C as Deref>::Target⁴. ↩

3. Aww, sashimi would've been a great name and it was taken last week. tartare is available, though... 👀 ↩

4. Well if you're using into_raw it'd have to actually be something more like <<C as IntoRaw>::Raw as RawPtr>::Pointee. There's a reason StableDeref is so much nicer to use than this 🙂 ↩

5. Of course you still need to make sure the trait enforces that into_rawd pointers can be dereferenced freely. ↩

6. Another giant caveat: safe Pin constructors now mean that they kinda do? The Pin documentation does guarantee (for a !Unpin pointee) that Deref[Mut] returns a reference to a stable location, but stops short of actually saying that pointers derived from a deref are not invalidated when the deref lifetime ends¹⁰, let alone anything about aliasing. Making our situation more complicated is that any guarantees a safe Pin constructor provides only apply if the pointee is !Unpin, and since we don't have guaranteed parametricity (broken by e.g. impl specialization and just normal TypeId shenanigans) ?Unpin isn't enough¹¹. ↩

7. Namely, I'm comfortable trusting Rc<T> because other strong pointers can be dereferenced while the cart moves around, and operationally there's no difference between a shared pointer derived from one or the other. I'm fairly confident Rust won't have a model of invalidating pointers derived from a reference when a reference's lifetime ends, because the “end of a lifetime” is already a poorly defined point. ↩

8. The comment that convinced me personally that the current situation (just Box is special) is distinctly problematic is that we currently tell people e.g. that they can/should use Box<str>/Box<[T]> instead of String/Vec<T> if they don't need to change the length. It would be a source of potential subtle issues if these have subtly different aliasing properties. Along with this, the current documentation for Vec talking about how it won't reallocate if it has sufficient capacity can be read to say that this doesn't invalidate existing pointers¹³ and ↩

9. As I understand it, this is not hit by yoke specifically because Miri/SB do not recurse into struct fields for the purpose of doing alias retagging. However, this isn't a specific choice in the system for some benefit, but rather an implementation limitation to make checking more tractable, and Ralf has mentioned a couple times the potential of changing this, making ptr::Unique have the magical aliasing semantics instead of Box. ↩

10. However, this is an actively malicious (yet probably “compliant”) reading of the docs. That previously derived pointers are still valid after moving or again dereferencing Pin<Box<T>> is required for the self referential struct example to be sound, and any reasonable reading would assume that the example is sound and the reasoning making it sound extends to any other std smart pointer with a safe way to construct a Pin version of it. Plus, well, we expect async/Future to be sound... though back to being malicious, since std doesn't provide any root Future implementations, someone¹² could potentially extend this argument to say that resuming a suspended ↩ ↩²

11. This could potentially be worked around by storing a cart P<T> as Pin<P<UnpinWrapper<T>> (where such a transmute is soundly available). Don't quote me on that, though; I don't know the exact details of pin projection to a field which is Unpin, and this reading is malicious¹⁰, giving us the worst possible scenario. ↩

12. Not me, not now, I've exhausted my malicious compliance legalese battery for today. ↩

13. Similarly to how Pin's discussion of location stability implies it doesn't invalidate references to deref, but doesn't say so explicitly. In fact, Pin's docs say about a Pin<Vec<T>> “Nor could it allow push, which might reallocate and thus also move the contents [emphasis mine].” This can be read as Vec<T> providing everything needed for pinning except the actual safe APIs... ↩

[Manishearth]

Thanks for this in-depth analysis! I read it a while ago but didn't have an opportunity to reply, sorry.

This isn't possible with the current API, since yoke allows fn backing_cart(&self) -> &C

Note: This API exists so that it's possible to e.g. clone the underlying Rc.

In general I would like to be able to use Box in a Yoke. I don't like having restrictions there, in fact, we do have Box<dyn Any> carts when we use the erased cart stuff.

The problem is specifically that the current aliasing semantics of Box as specified by Miri mean that moving a Box invalidates any pointers to its pointee, like a deref_mut

So I think here's where I feel like it's upon the UCG to come up with ways to disable this. Namely, having some kind of InlineShared<T> that you can wrap around any type and have the same effect as if it were found behind, say, and Rc<T>. Hell, maybe UnsafeCell<T> is that type, and it works perfectly fine for our use case since we only ever need immutable access to the cart.

In general my attitude towards this is:

• If I have to do things differently, that's all right
• If I can no longer do something, there's something missing in the model.

It feels like we're strongly in the second case here: All the "fixes" for this reduce the flexibility of Yoke, and it's not at all clear to me that the UCG's model so far really has to mandate that: they just haven't figured out escape hatches.

Thoughts?

[sffc]

@Manishearth is "Utilities 1.0" the correct milestone for this issue?

[Manishearth]

Yes, though to some extent whether or not this is fixable by then depends on upstream

[CAD97]

So I think here's where I feel like it's upon the UCG to come up with ways to disable this. Namely, having some kind of InlineShared<T> that you can wrap around any type and have the same effect as if it were found behind, say, and Rc<T>. Hell, maybe UnsafeCell<T> is that type, and it works perfectly fine for our use case since we only ever need immutable access to the cart.

In general my attitude towards this is:

• If I have to do things differently, that's all right
• If I can no longer do something, there's something missing in the model.

I agree inasmuch as I also think Box being unique (rather, invalidating pointers when moved) is thoroughly unexpected in practice, and making -Zbox-noalias=no the normal behavior is what we should end up with.

Even in a future where Box is unique and retagging is recursive through fields, there will be some way to have a box without this behavior. There's been some discussion of "UnsafeAliasCell;" fundamentally, the guarantee opt-out that yoke wants to apply is the same as that of futures and other self-referencing types, even though it is simpler due to not needing to actually have mutable access. At the extreme, you can use a wrapper around ptr::NonNull<T> instead of Box<T>, and this needn't change how any of the other carts function.

If you want to test the strict version, we now have -Zmiri-retag-fields to retag fields, which makes yoking a cart UB.

Nobody wants to break the ability to do Yoke-like things. As such, I think it's fair to defer any changes here until either -Zmiri-retag-fields is the default or the Box uniqueness question is furthered. If you want to help with data for this and have projects which use a lot of boxes (ideally passed around by-value), you can try running them under -Zbox-noalias=no and reporting if it has any perf impact. rustc isn't impacted, but it also doesn't use that many Boxes.

I would consider a miri CI job for yoke sufficient to mark the issue as closed, unless you want to leave it open for further tracking. (Probably also with a if: failure(), run: echo "this indicates miri's default rules changed; see #2095" step.) It'll unfortunately probably be a while until any real progress is made upstream on clarifying the situation here.

[Manishearth]

I'm happy to leave this open for tracking but a CI job is probably a good idea anyway

[Manishearth]

@mvtec-bergdolll The issue tracker is not the relevant place to ask questions about why a crate exists (ask on the currently active reddit thread instead?), but the answer basically is: those crates are internal to a type and do not support the use cases here. The miri issues are largely due to an area of UB that is still being pinned down so I'm generally happy with waiting a bit until we have more concrete rules and writing mitigations then. I may introduce a stopgap trait till then

[CAD97]

Reply to minimized

@mvtec-bergdolll self_cell allocates its cart on the heap as part of self_cell!, so you can have e.g. self_cell!(u64, &'self u64). yoke's primary purpose is for zero-copy deserialization, thus introducing an allocation here isn't permissable.

Any crate which does what zero-copy (actually: zero-alloc) yoking requires boils down to (impl StableDeref, Ref) and will run into this exact issue unless it finds a novel mitigation.

....but, I found a potential implementation change that shouldn't require changing the API¹ any. It's not pretty, but... if we wrap the cart in MaybeUninit, it no longer gets retagged and everything passes under -Zmiri-retag-fields. This works for any cart type.

(I tried ManuallyDrop first, but that just changes &mut to require -Zmiri-retag-fields to throw UB, and doesn't remove the field retag UB.)

By my thermometer, it looks like we're currently very slightly biased towards Box not retagging, and this specific version of the issue would be moot under that. IIUC RalfJ is also biased towards not doing field retagging, so that would also make this specific manifestation of the issue moot.

There remains the case of &mut which is currently problematic even without -Zmiri-retag-fields². This I think yoke will need to address; this will likely be by forbidding using &mut.

Footnotes

1. modulo that Yoke becomes no longer #[may_dangle]y, since it now requires a Drop implementation. ↩

2. I need more time to experiment with the implementation, but I'm thinking any fix to make this work is much worse than forbidding &mut since that's not a deliberate use case of yoke to store a &mut cart. ↩

[Manishearth]

@mvtec-bergdolll Firstly, that's a false equivalence; there is no "std" self-referential thing, self_cell didn't even exist when we designed this crate. Secondly, the issues in this thread are issues faced by the general space of self-referential types in Rust, and even if those crates are UB-free today (which I'm skeptical of) that does not necessarily mean they will be UB free once the exact semantics of Rust around this stuff is pinned down. So no, this issue is not about the custom crate causing problems, it's about the kind of operation we need being generally problematic, switching to a different crate will have the same problems.

Before designing this I did a survey of the existing self-referential stuff and found it lacking for our use cases. I do not feel particularly obliged to spend effort explaining the details in response to someone who has at this point violated an explicit boundary set about where such questions should go (though I appreciate @CAD97 trying!).

This issue is likely going to be a complicated one, I do not wish for it to get polluted with irrelevant chatter.

[mvtec-bergdolll]

@Manishearth sorry for the perceived derailing of the discussion. I've personally seen too many projects and blog posts talk about their own version of self-referentiell structs in Rust, and more often than not their reason for going with something custom did not hold up to closer scrutiny, nor was their code sound. Maybe it's my reading comprehension and I missed some obvious part, I didn't understand the difference to other heap allocated self-referential structs from the Documentation. A section about that might help avoid future confusion.

[CAD97]

Tracking context: there's a new RFC that proposes a proper way out:

• MaybeDangling rust-lang/rfcs#3336

If this RFC is accepted as currently written, it will be sufficient to wrap the cart in ManuallyDrop or the newly described MaybeDangling.

I believe it very likely that at a minimum ManuallyDrop will get the changes described in that RFC (namely, that references/boxes/etc within ManuallyDrop will not be SB-retagged or marked LLVM-dereferencable/noalias).

If we would like to preemptively adopt the likely solution, we can wrap the cart in ManuallyDrop today¹. We could also use MaybeUninit instead if we'd like to have the fix apply today.

Note that this isn't an exclusively theoretical concern; -Zmiri-retag-fields semantics are required to fully justify the LLVM attributes rustc already emits, which includes dereferencable/noalias on field references.

(At this point I'm not 100% certain how allowing access to &C impacts noalias/uniqueness, which is what yoke cares about. I think it's fine — obviously you can use &Box<T> and &T concurrently — but at this exact point in time I've gone and confused myself into being unsure.)

Footnotes

1. Although note that adding the necessary Drop implementation to Yoke will be a technically breaking change due to preventing NLL early termination of captured lifetimes. The hypothetical MaybeDangling should have no such issues. ↩

[CAD97]

Small update: Miri's default is currently to do field retagging for "small" structs only; the ones where rustc currently emits noalias for the fields. IIUC, this is any struct with "scalar" or "scalar pair" ABI; these are the ones where they're actually passed to functions as their component fields; LLVM-noalias only can be applied to function arguments (and returns).

This means consumers will be flagged for miri UB if 1) they use the default -Zmiri-retag-fields=scalar and yoke &impl Sized to Box<impl Sized>, or 2) they use -Zmiri-retag-fields=all and a Box cart. -Zmiri-retag-fields=none is available to disable this, but is documented as unsound (not catching UB which is present).

---

However, I made an interesting observation today when discussing this unsoundness elsewhere:

I believe that due to the fact yoke only allows shared access to the yoked data, it does not expose any LLVM-level unsoundness resulting from noalias. This is because AIUI LLVM-noalias only cares about write aliasing; this is why &_ gets LLVM-noalias.

This doesn't change the fact that Rust-level UB still exists under the Stacked Borrows model as implemented by Miri, but it does provide a buffer against this turning into an actual potential miscompilation.

[coolreader18]

Note: This API exists so that it's possible to e.g. clone the underlying Rc.

Finding this late, but if the IntoRaw-trait-based approach was going to be taken, there could be a trait CloneFromRaw that could be implemented for Rc as:

trait CloneFromRaw: Deref {
    fn clone_from_raw(ptr: *const Self::Target) -> Self;
}
impl<T: ?Sized> CloneFromRaw for Rc<T> {
    fn clone_from_raw(ptr: *const T) -> Self {
        unsafe {
            Rc::increment_strong_count(ptr);
            Rc::from_raw(ptr)
        }
    }
}

and even for Box like:

impl<T> CloneFromRaw for Box<T> {
    fn clone_from_raw(ptr: *const T) -> Self {
        unsafe { Box::new((&*ptr).clone()) }
    }
}

It seems like this is probably gonna go in the MaybeUninit/MaybeDangling/MaybeAliased direction though, which is much easier.

[RalfJung]

Since I haven't seen it above, here's an example triggering a Miri error:

#[test]
fn box_noalias() {
    let x: Yoke<&'static u8, Box<u8>> = Yoke::attach_to_cart(Box::new(0), |data| data);
    // The move into `x` reborrows the Box (cart), thus invalidating the yoke.
    assert_eq!(**x.get(), 0);
}

Interestingly this works fine with Tree Borrows, because nothing here is getting mutated. I am not sure if it is possible to mutate the yoke while the Yoke lives? If not, this looks like it would actually be compatible with Tree Borrows. (I found with_mut but Yokeable doesn't seem implemented for mutable references so this does not seem to help.)

[Manishearth]

I am not sure if it is possible to mutate the yoke while the Yoke lives?

It's possible to mutate the Yokeable value, but only the parts that aren't a reference (which I imagine is not an actual problem!). And you can change references into other references (derived from the same source, or 'static)

---

(continued from #3735 (comment))

(context: is it sufficinet to wrap the cart in MaybeDangling? Must the backing_cart() method be tweaked?

We could make backing_cart() take an &mut self; seems suboptimal.

The primary purpose of that method is doing things like cloning Rcs, which could just be exposed directly, and we could make this method unsafe (and say "please do not call .get() while holding on to this reference). ICU4X doesn't use it anyway though I am of the opinion something like this should exist.

I've been holding off on resolving that until other things are settled (it's a bit hard to write safety docs for an external unsafe API when the unsafety it exhibits is not completely well documented). However if you think there's a clear path forward there, I can try and resolve it.

Given that MaybeDangling is basically going to be the path forward anyway we probably should figure out what the right thing is to do here and resolve this issue soon instead of leaving it open.

[Manishearth]

(Since I wrote the last comment @RalfJung already responded on the other thread and said)

I think it's fine; &Box<T> only has an outer noalias for the shared ref and there is no way to get to the inner box.

@RalfJung note that backing_cart() is available for all carts, even non-StableDeref ones. However it seems fine to restrict this to just StableDeref types for now.

(non-StableDeref carts are not always safe to construct; but they are usable; the primary use case is stuff like Option<Cart> and ()))

[RalfJung]

IIUC, this issue is about the cart having noalias requirements which are violated since the yoke does alias. Those requirements only come up when the cart shows up by-value (unless we decide to apply noalias recursively, but I doubt we will do that). So I don't see how backing_cart can be a problem. I don't know what is possible without StableDeref so I can't really comment on that.

Mutation could be an issue but if it's never allowed to mutate the cart or the "part of the yoke that borrows from the cart" then that circumvents those problems.

please do not call .get() while holding on to this reference

Why would that be a useful restriction?

I can obviously create aliasing &Box<u8> and &u8 in safe code so this on its own can never be the problem.

[Manishearth]

Aha, I see. If by-value is the problem then we should be fine! Great, I've been hopign to resolve this issue without impacting functionality for a while!

I can obviously create aliasing &Box<u8> and &u8 in safe code so this on its own can never be the problem.

Ah, I misunderstood your comment.

[Manishearth]

Ah, annoying; we do want the cart to be allowed to have lifetimes so we can't use KindaSortaDangling and I don't want to use nightly eyepatch stuff yet. I guess it's fine for Yoke to be annoying about manual self-references coming out of the cart, though. Either way, probably a followup where I relax the 'static requirement on KindaSortaDangling.

[RalfJung]

relax the 'static requirement on KindaSortaDangling

Yeah I don't think I see the necessity for that bound.

[CAD97]

Mostly a note for myself: while the cart is the bigger retag hazard, the yoke is also necessarily KindaSortaDangling, because if you pass a yoked reference into a function, the reference retag will protect the allocation and make it UB to deallocate. That's dereferencable instead of noalias.

(The MaybeDangling name fits reasonably well for its application there. It fits less well for its application to the owning cart.)

If/when you wrap the cart as well, that will indeed resolve this issue. The one caveat will be around replace_cart APIs since that does the problematic by-value manipulation of the cart. Thankfully since it's unsafe you can just put a "don't cause aliasing issues thanks" warning on it (implied by the requirement for the yoked references to remain valid) and tweak the wrap_cart_in_* and erase_box_cart function implementations to avoid retagging the cart. (erase_box_cart and wrap_cart_in_alloc should be simple enough, but wrap_cart_in_enum might pose a problem, since there's no guarantee that Enum<Transparent<T>> and Transparent<Enum<T>> have the same layout.)

[RalfJung]

Mostly a note for myself: while the cart is the bigger retag hazard, the yoke is also necessarily KindaSortaDangling, because if you pass a yoked reference into a function, the reference retag will protect the allocation and make it UB to deallocate. That's dereferencable instead of noalias.

That's #3696.