Stacked Borrows: How precise should UnsafeCell be tracked?

[RalfJung]

Currently, when looking for UnsafeCell behind shared references, Miri descends through arrays, structs and the like, but does not descend through enums. Instead, when it sees an enum, it checks if T: Freeze, and if not, treats the entire enum as an UnsafeCell.

The benefit of this is that finding UnsafeCell does not require reading from memory (rust-lang/miri#931), which makes formal reasoning about Stacked Borrows a lot simpler. Accessing memory during UnsafeCell search opens all sorts of nasty questions, such as whether those accesses are themselves subject to Stacked Borrows rules or not (and if yes, which tag they use). Not reading enum discriminants also avoids potential confusion from Stacked Borrows partially checking the validity invariant of the referenced data.

On the other hand, being more precise with UnsafeCell search could help optimizations. When a function works on &Result<Cell<i32>, i32>, and the compiler somehow can know that the Err variant is active, we would be able to rely on this shared reference being read-only -- currently, that is not an assumption that the compiler can make. (But note that once a shared reference gets created to the i32 in the Err variant, that is already guaranteed to be read-only.)

This is somewhat related to #204.

Some posts with useful datapoints (not exhaustive):

• Stacked Borrows: How precise should UnsafeCell be tracked? #236 (comment)
• Stacked Borrows: How precise should UnsafeCell be tracked? #236 (comment)

Other parts of this question:

• If we don't have strict subobject provenance, then what is the mutability of bytes outside the range of T?
• Does UnsafeCell inside PhantomData have any effect?

[RalfJung]

To be precise, here is currently how we compute the permissions associated with a shared reference &T: we do recursive descend over T.

• If we hit an UnsafeCell, the memory it covers is writable.
• If we hit a field of type U such that U: Freeze, we stop searching for UnsafeCell here. This is purely an optimization, we could equivalently continue our descend, but we know that U: Freeze guarantees the absence of UnsafeCell.
• If we hit a union or a type where variants is Variants::Multiple, and since we already checked Freeze, we treat memory this type covers as writable.
• For other types (Variants::Single), we descend recursively through its fields.

Every location not marked as writable in the above procedure is marked as read-only.

[chorman0773]

For reasons similar to those brought up in #77, #84, and #253, I think the multiple variants case should consider the active variant, when determining runtime writability.
Consider the type Result<Cell<i32>,i32>, brought up in the original example. Under the model presented by lccc, in an object of that type, reguardless of the variant, there is a subobject of type i32. However, that subobject has the mutable characteristic (used to implement UnsafeCell) only when the result is Ok. Behind a shared reference, it should be reasonable to conclude that the value of this subobject does not change if you have the Err variant. This allows the movement/removal of reads behind a shared reference of this type when the variant is known to be Err (without loss of generality).

I cannot think of a particular example where this distinction would have an effect (one would probably use an external UnsafeCell, which does fun things anyways, and I've pretty much given up trying to optimize things inside an UnsafeCell, and focus my efforts on things outside of one).

[RalfJung]

FWIW, making UnsafeCell "maximally imprecise" would also help with issues like rust-lang/rust#98498, where currently the obvious fix is not sound because one of the fields of Scope is not an UnsafeCell.

[RalfJung]

In fact, even just making each field be in an UnsafeCell is not always sufficient to allow deallocating that reference, since the padding between the fields is not in an UnsafeCell.

So making use of the exception that is being added in rust-lang/rust#98017 is rather fragile currently, but would fairly very well if we don't attempt to track where inside a type the UnsafeCell are.

[CAD97]

There is still a possible axiomatic alternative: treat padding even more weakly. All fields being UnsafeCell can be sufficient to say the whole struct is in UnsafeCell if you explicitly don't care about padding. Treating the answer to “is this padding byte in an UnsafeCell” as undefined isn't strong enough; that could resolve to always say no and be the same as today; I think you'd need to somehow say the answer is always yes but still somehow justify Freeze from lack of non-padding UnsafeCell.

I don't know exactly what this would look like, and it would probably break some important properties of Stacked Borrows — the simplest interpretation is probably to have a “padding” permission tag on the borrow stack for a byte reborrowed as padding, and then reading through a padding permission both returns an uninitialized byte and stores uninit. (Making a read perform a write is the certainly broken bit.)

Ultimately I'm also in favor of the weakening applied by UnsafeCell (and by analogy, PhantomPinned) applying to the entire pointee if the pointee type contains any UnsafeCell. As chorman has pointed out, this greatly limits the reasoning the compiler¹ can make about generic code, but giving that up this seems justified² by the operational specification simplifications gained.

What might be beneficial under such a model is splitting the UnsafeCell weakening into parts, so that you can remove the dereferencable_always(n) and noalias qualities individually.

Footnotes

1. But I want to point out that code authors can still make these assumptions in a generic environment due to privacy, encapsulation, and generally the concept of soundness of an API not considering outside uses of unsafe that break such. ↩

2. Especially since for better or for worse Rust already relies heavily on monomorphizations for performance. ↩

[RalfJung]

There is still a possible axiomatic alternative: treat padding even more weakly. All fields being UnsafeCell can be sufficient to say the whole struct is in UnsafeCell if you explicitly don't care about padding.

We could do something operational where if all fields of a struct are entirely UnsafeCell, then its padding is considered UnsafeCell, too.

What might be beneficial under such a model is splitting the UnsafeCell weakening into parts, so that you can remove the dereferencable_always(n) and noalias qualities individually.

Basically, separating its effect on protectors and permissions? Sure, that would be easy to represent.

[chorman0773]

As chorman has pointed out, this greatly limits the reasoning the compiler can make about generic code, but giving that up this seems justified

I actually think there might be a more insidious problem, if this includes the fact that you can get a &mut T to those fields (while the exterior can still be freely moved as a shared reference). If it's just mutability, then the loss in generic contexts actually affects non-generic contexts as well, since non-trivial validity attributes are salient parts of pointer types in XIR (if they weren't the same problem I mentioned before is trivial to recreate, since it basically involves smuggling a unique pointer into a function as a trivially-valid pointer type, which doesn't cause implicit derives, and thus allows you to alias it to another unique pointer passed into the same function, since the raw pointer in the second parameter is its direct parent).

We could do something operational where if all fields of a struct are entirely UnsafeCell, then its padding is considered UnsafeCell, too.

I'd be even fine with a more expansive restriction: Any contiguous extent of padding bytes that preceeds or follows an UnsafeCell gets SRW as well. Unlike actual fields, XIRs model doesn't let you just point to padding bytes the same way as a subobject (I mean, you can have a pointer to it, but not a pointer to it), which is where the problem would arrise.

[RalfJung]

If it's just mutability, then the loss in generic contexts actually affects non-generic contexts as well,

I don't see why that has to be the case, or why it would be the case in MIR+LLVM.

I'd be even fine with a more expansive restriction: Any contiguous extent of padding bytes that preceeds or follows an UnsafeCell gets SRW as well. Unlike actual fields, XIRs model doesn't let you just point to padding bytes the same way as a subobject (I mean, you can have a pointer to it, but not a pointer to it), which is where the problem would arrise.

Even precisely defining the notion of "padding byte" is super hard (and subtle), on top of the already subtle rules for how far we traverse looking for UnsafeCell, on top of the already super subtle aliasing rules... I think this is way overspending our complexity budget.