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

[mvtec-bergdolll]

Honest question, why build and maintain Yoke, when solutions like Ouroboros and self_cell already exist? For example self_cell passes it's tests with -Zmiri-retag-fields.

[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

[mvtec-bergdolll]

@Manishearth well I'd argue a question why a project is using a hand rolled Vec instead of the std one is a valid question on an issue with said custom Vec causing problems. Can you provide an example how they wouldn't work for you use case, because I can't come up with one based on your explanation. Without HKTs I don't see how you could be generic over them, which is the only limitation I can think of.