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 (https://github.com/rust-lang/miri/pull/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 https://github.com/rust-lang/unsafe-code-guidelines/issues/204.

Some posts with useful datapoints (not exhaustive):

• https://github.com/rust-lang/unsafe-code-guidelines/issues/236#issuecomment-1166540628
• https://github.com/rust-lang/unsafe-code-guidelines/issues/236#issuecomment-1175403140

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 https://github.com/rust-lang/rust/issues/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 https://github.com/rust-lang/rust/pull/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[^1] can make about generic code, but giving that up this seems justified[^2] by the operational specification simplifications gained.

[^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.

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.

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

[chorman0773]

On Tue, Jun 28, 2022 at 09:52 Ralf Jung @.***> wrote:

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.

In XIR, pointer types consistent of a number of validity attributes and some definition attributes (pointer kind and syntax declaration kinds), and pointee type. Different attributes forms different pointer types that are incompatible with each other. An explicit conversion (called the derive operation) is necessary. This is because an implicit conversion is otherwise needed (else you can get a T that is the same pointer as a unique T, and which allows both to be passed to the same function) and I don't like doing non-trivial operations implicitly.

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.

Fair, though it encompasses the previous proposal. Since searching for Freeze itself is structural on a type, though, couldn't it just use the implicit Pad fields?

— Reply to this email directly, view it on GitHub https://github.com/rust-lang/unsafe-code-guidelines/issues/236#issuecomment-1168756172, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABGLD26CJRDU24DNQR672N3VRL7RTANCNFSM4N4GIRZQ . You are receiving this because you commented.Message ID: @.***>

[RalfJung]

In XIR,

Can you explain this without going into the specifics of XIR? As in, is there actually something fundamental here, or just a design quirk of XIR?

Fair, though it encompasses the previous proposal. Since searching for Freeze itself is structural on a type, though, couldn't it just use the implicit Pad fields?

There are no implicit Pad fields. Padding is the absence of a field at a given offset into a struct. (And something more complicated for enums.) At least that's how I prefer to think of it.

[chorman0773]

Can you explain this without going into the specifics of XIR? As in, is there actually something fundamental here, or just a design quirk of XIR?

It's fundamental, part of the type system. Especially for non-trivial validity, it changes how the pointers interact with certain operations, like being moved (particularily into a function, local, or a static, the same way that &mut T and &T do. And there are no implicit conversions in XIR, only weak ones with the convert instruction, especially when the conversion is as non-trivial as an implicit derive operation (which can best be described as being equivalent to a generalization of the reborrow operation - although as an instruction, derive is "Change pointer attributes and produce new pointer value").

There are no implicit Pad fields. Padding is the absence of a field at a given offset into a struct

Yeah, that's how I'd think of it as well. Parts of the object-representation that don't participate in determining the value.

[RalfJung]

I don't mean fundamental to XIR. I mean fundamental in a way that does not depend on the details of the language this is formalized in.

[RalfJung]

Context: I am mostly interested in XIR insofar as it teaches us general lessons that we might miss by taking a MIR/LLVM view, due to the quirks of those languages. I am much less interested in XIR itself. So if there is a lesson here that transcends XIR, I would like to learn it.

[chorman0773]

I don't mean fundamental to XIR. I mean fundamental in a way that does not depend on the details of the language this is formalized in.

Fair, it's not really fundmental in that way, It comes arround from the design of XIR and just not wanting to do highly complicated operations implicitly. I think you could argue that any time you've got a generic IR that doesn't have high-level source language queries, you'd have a similar problem though. Having it be part of the type system isn't but is that not what the type system is for, encoding information about the constraints on values?

[CAD97]

not wanting to do highly complicated operations implicitly.

What I don't get is why you aren't willing to / think you can't handle making the operations explicit as part of lowering to XIR. This kind of elaboration is an intrinsic part of lowering to any IR.

I think you could argue that any time you've got a generic IR that doesn't have high-level source language queries, you'd have a similar problem though.

This is in fact a pessimisation of what optimizations can be done on a generic IR (e.g. MIR, XIR), but it's not like this is a choice we're making without knowing its the case; we'd love to have more MIR opts in rustc as well.

What I think you/XIR needs and doesn't have at the moment is to be able to apply the pointer (restricting) attributes to the types, with the semantics that this makes any pointer access to that type act as if it had the attribute.

And if you're throwing away the required type information before the point where it would be required to provide/take advantage of pointer attributes on the pointee, then I think you'll just need to accept that you won't be able to optimize Rust code as well as otherwise.

(An option to preserve doing the optimizations in generic paths relying on the lost attributes would be to assume a monomorphization adding the "usual" attributes and preprovide a partial morphization as such.)

[RalfJung]

Having it be part of the type system isn't but is that not what the type system is for, encoding information about the constraints on values?

Yes, but then the question is what is the type system that actually encodes this properly. :)

My proposal is to view interior mutability as a property of the reference, i.e., we have two kinds of shared references: interior mutable ones and regular frozen ones. The only purpose of UnsafeCell is to automatically infer which kind of shared reference to use. Once that inference is done, you can entirely forget about UnsafeCell.

Of course actually erasing it can only be done after monomorphization, so a compiler working on polymorphic IR has to consider that each &T is actually a &{frozen: bool} T, where frozen == true iff T: Freeze.

[RalfJung]

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

OTOH, already the current status of UnsafeCell "infecting" surrounding enums is a problem for some possible approaches to ensuring that match in a UB-free program always behaves the way one might think it would.

[chorman0773]

On Wed, 29 Jun 2022 at 19:12, Christopher Durham @.***> wrote:

not wanting to do highly complicated operations implicitly.

What I don't get is why you aren't willing to / think you can't handle making the operations explicit as part of lowering to XIR. This kind of elaboration is an intrinsic part of lowering to any IR.

The issue here is something like function pointers. fn<T>(&T) instantiated with i32 has to be compatible with fn(&i32). fn(&i32) currently becomes function(*readonly dereferenceable(4) aligned(4) int(32)), which requires being called with a single parameter of type *readonly dereferencable(4) aligned(4) int(32). A conversion does exist (the derive instruction does pointer attribute conversion w/o directly changing types), but the problem is that fn foo<T>(&T) under these rules doesn't get readonly, but if I instantiate foo<T> with i32 and take an fn-ptr to it, then the resulting pointer must be the same type as fn(&i32). Extending mutable similarily to UnsafeCell is a possibility but I run into problems with optimizing C and C++ (specifically, non-mutable subobjects of a const complete object with a mutable subobject can't assume immutability), and if I'm allowed to get a unique interior pointer that moving around the exterior pointer doesn't invalidate, then I'm fairly certain I can get a *unique pointer using offsetting, due to lack of reachability restrictions (which is basically banned by C and restrained by C++) and a no-attribute pointer to have the same pointer value (which means that both can be passed into a function, and still alias).

I think you could argue that any time you've got a generic IR that doesn't have high-level source language queries, you'd have a similar problem though.

This is in fact a pessimisation of what optimizations can be done on a generic IR (e.g. MIR, XIR), but it's not like this is a choice we're making without knowing its the case; we'd love to have more MIR opts in rustc as well.

What I think you/XIR needs and doesn't have at the moment is to be able to apply the pointer (restricting) attributes to the types, with the semantics that this makes any pointer access to that type act as if it had the attribute.

And if you're throwing away the required type information before the point where it would be required to provide/take advantage of pointer attributes on the pointee, then I think you'll just need to accept that you won't be able to optimize Rust code as well as otherwise.

I had originally considered this, but I opted against it in favour of doing the same for pointer types (__lccc::xlang_pointer_attributes adds pointer attributes to a pointer type used in a field, there's also xlang_scalar_attributes which is the same but for scalar types, and is used by NonZero* types). One consideration is that the user could just have plugins stop being run at any point in compilation (incl. before generics are instantiated), which means any and all information has to be encoded in the IR directly. Additionally, adding pointer attributes implicitly is bad for two reasons:

• One, how would you distinguish between a pointer that can have it validly added vs. one that can't (IE. *const i32 vs. &i32). Both use the XIR pointer type internally
• Two, Adding pointer attributes changes the behaviour of operations, hence making it part of the pointer type. Further, the entire core of the pointer model in XIR is based on this special behaviour - implicit derive operations. Adding pointer attributes to pointees means that you come back to the "operations implicitly changing behaviour" The ability to remove pointer attributes, which would be better for the first, was even more problematic, due to backwards and forwards compatibility of the IR - adding an attribute to a type in the future strictly increases the defined behaviour of a program.

— Reply to this email directly, view it on GitHub https://github.com/rust-lang/unsafe-code-guidelines/issues/236#issuecomment-1170580929, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABGLD2YTRDGN7MAFTBVY56LVRTJ7BANCNFSM4N4GIRZQ . You are receiving this because you commented.Message ID: @.***>

[RalfJung]

This came up in Zulip again because Tree Borrows, unlike Stacked Borrows, considers UnsafeCell to be "fully infectious" to its neighbors. Noteworthy examples:

• code that was rejected by SB but is now allowed under TB
• a variant that was already allowed with SB since it uses an enum (except that very early variants of SB did reject this, too)

[Jules-Bertholet]

I'd like to note the compromise alternative of saying that, if a byte is UnsafeCell in one enum variant, it is in all of them, but if it is not UnsafeCell in any variant, then it isn't. It makes the analysis not require reading from memory, but you still avoid most of the infectious behavior.

[RalfJung]

Yes that is pretty much the limit we can reach if we want to make "which bytes can be mutated" an entirely static property that does not depend on run-time memory contents.

It makes 'infection' depend on enum layout details which is very fragile. Not sure I buy that this is truly an advantage over infecting the entire enum.

[chorman0773]

Well, in the limit, UnsafeCell<()> IMO shouldn't affect mutability at all.'

It makes 'infection' depend on enum layout details which is very fragile. Not sure I buy that this is truly an advantage over infecting the entire enum.

Quite a bit of undefined behaviour can depend on layout. I'm not sure why this particular UB would make a difference.

[CAD97]

Well, in the limit, UnsafeCell<()> IMO shouldn't affect mutability at all.

While I don't necessarily disagree, I'm not completely convinced either.

For LLVM at least, IIUC noalias is a coarse annotation; it either applies to all accesses through a pointer or none of them. There's not currently a way to say that a pointer is noalias for some bytes but not for others. (You can mark derived pointers/accesses as noalias, but aliased writes can still occur between those ranges.)

In the current implementation, the Unpin hack to disable noalias behavior for &mut T is infectious. Freeze having the same infectious behavior for disabling noalias behavior for &T provides a very predictable consistency.

Plus, the language already does care about Freeze (contains shared mutability) in a visible way via const. consts currently cannot create references to any type that (potentially) has shared mutability. This can be lifted in the future, but it's still necessary that types with shared mutability don't exist as const items and only transiently during const evaluation.

Making (nonindirect) shared mutability semantics rely solely on the unsafe autotrait Freeze means the trait has a meaningful interpretation, and could potentially be exposed publicly to the surface language. Manually implementing Freeze would be frighteningly unsafe, but have a consistent and predictable semantic.

I don't have a strong opinion or intuition on whether making UnsafeCell/Freeze coarse/type-directed or making "UnsafeMut/FreezeMut" precise/byte-directed is a "better" end state, but both have practical benefits.

[chorman0773]

On Sun, 14 May 2023 at 12:59, Christopher Durham @.***> wrote:

Well, in the limit, UnsafeCell<()> IMO shouldn't affect mutability at all.

While I don't necessarily disagree, I'm not completely convinced either.

For LLVM at least, IIUC noalias is a coarse annotation; it either applies to all accesses through a pointer or none of them. There's not currently a way to say that a pointer is noalias for some bytes but not for others. (You can mark derived pointers/accesses as noalias, but aliased writes can still occur between those ranges.)

This is a limitation on llvm specifically (and perhaps gcc as well, I do not know it well enough to say either way). lccc's xlang has a much more granular system, and can benefit from bytewise Freeze. The currently implemented magic in lccc's stdlib is using the mutable xlang field attribute inside UnsafeCell, which has the same behaviour as C++'s mutable keyword. These semantics were actually deliberately chosen because llvm is coarse-grained on UnsafeCell - something along the lines of "I can do better than that", I had the same thought about the then-disable mutable-noalias. Future implementations should not be enjoined from reasonable optimizations because current implementations are deficient, otherwise there is room for neither competition nor innovation. Even for llvm as well, rustc could be modified to emitreadonly + noalias for &T when T only contains ZST UnsafeCells. That's one of the reasons I use UnsafeCell<()> as the example. Current implementations can already take advantage of bytewise UnsafeCell granularity with it. Depending on the implementation of Mutex, this would avoid infecting a structure that might be using Mutex<()> as an external lock for some non-memory resource.

In the current implementation, the Unpin hack to disable noalias behavior for &mut T is infectious. Freeze having the same infectious behavior for disabling noalias behavior for &T provides a very predictable consistency.

I would like to see this tossed out as well, eventually, and replaced with an appropriate alternative for &mut T, such as with UnsafeCellMut. TBH, I'd like to avoid having to call the trait solver during irgen in general - I cannot think of another case that it's required (determining whether to put the static const in .data, .rodata, or .bss happens in the xlang backend, which looks for mutable), and frankly, trait evaluation is slow.

Plus, the language already does care about Freeze (contains shared mutability) in a visible way via const. consts currently cannot create references to any type that (potentially) has shared mutability. This can be lifted in the future, but it's still necessary that types with shared mutability don't exist as const items and only transiently during const evaluation.

Making (nonindirect) shared mutability semantics rely solely on the unsafe autotrait Freeze means the trait has a meaningful interpretation, and could potentially be exposed publicly to the surface language. Manually implementing Freeze would be frighteningly unsafe, but have a consistent and predictable semantic.

I would not like this for the same reason as above.

I don't have a strong opinion or intuition on whether making UnsafeCell/ Freeze coarse/type-directed or making "UnsafeMut/FreezeMut" precise/byte-directed is a "better" end state, but both have practical benefits.

— Reply to this email directly, view it on GitHub https://github.com/rust-lang/unsafe-code-guidelines/issues/236#issuecomment-1546946729, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABGLD25L6GFGMT2EZWRLHY3XGEFN3ANCNFSM4N4GIRZQ . You are receiving this because you commented.Message ID: @.***>

[CAD97]

(just so you're aware, the email response formatting isn't translating well onto GitHub and it's not super clear the division between quote and response)

a structure that might be using Mutex<()> as an external lock for some non-memory resource

I hadn't thought specifically about this case, actually. While I personally think std exposing some sort of RawMutex (and perhaps more of std::sys, even) — i.e. just the OS mutex handle with unsafe lock/unlock — could probably[^1] be a good idea (even if std's Mutex isn't generic over the raw mutex provider), it would still be desirable that Mutex<()> doesn't result in interior mutability if the raw mutex doesn't use it. But if the semantics rely on Freeze, it could theoretically[^2] be a library fix to implement Freeze where size_of::<T>() is 0.

[^1]: Depending on how confident we can be that we won't want to change the interface to make it more restrictive for performance, like with the semirecent change to put the os primitive mutexes inline instead of allocated.

[^2]: Would require new language features and/or magic.

I'd like to avoid having to call the trait solver during irgen in general [...] frankly, trait evaluation is slow. [...] I would not like this for the same reason as above.

I'm assuming the point there is primarily about allowing manual Freeze impls (as opposed to it being exclusively derived information); requiring const items to not have interior mutability is a necessity.

If it's also about the effects being infectious, then I don't quite understand the objection, because then recording whether a type is "logically Freeze" or not is just checking to see if the type transitively contains UnsafeCell.

Properties like constness being determined from annotations on the field/place is how C++ does it, but it's typically type-directed in Rust. And traits are how to talk about properties of types.

I cannot think of another case that [traits influence semantics]

A subtle but meaningful one is that Copy does influence semantics. People say that a move is always a memcpy and that Copy doesn't change that, and that's mostly true. But moves/copies are a typed operation, and that changes the borrowing implications, in that a copy is a shared access (invalidates derived unique-write pointer provenance) but a move is considered a unique access (invalidates all derived provenance).

And this is the case independent of whether moves are considered to deinitialize the moved-from place or not.

I suppose you could just ignore the difference to claim the purity of traits not impacting how you lower fully-resolved Rust, but that's leaving some obvious optimization potential behind[^3] for no particular reason.

[^3]: In particular, the ability to use pass by rvalue reference when a pointer to the place has escaped. It's a known performance pitfall that rustc/LLVM optimizes large Copy values poorly (unnecessary defensive copies) at least in part because of this.

[chorman0773]

I'm assuming the point there is primarily about allowing manual Freeze impls (as opposed to it being exclusively derived information); requiring const items to not have interior mutability is a necessity.

Yes, explicitly as it relates to changing defined behaviour of programs. It also relates to Unpin and the Unpin Hack.

Properties like constness being determined from annotations on the field/place is how C++ does it, but it's typically type-directed in Rust. And traits are how to talk about properties of types.

And I do like borrowing stuff from C++ given that I'm implementing it as well. And it works well, because my goal for rust's semantics, and what I'd want to implement, is that it's the property of given offsets of a type whether or not

A subtle but meaningful one is that Copy does influence semantics. People say that a move is always a memcpy and that Copy doesn't change that, and that's mostly true. But moves/copies are a typed operation, and that changes the borrowing implications, in that a copy is a shared access (invalidates derived unique-write pointer provenance) but a move is considered a unique access (invalidates all derived provenance).

Fair, though I'd expect this differentiation to occur at a higher level than irgen (either during borrowck or tycheck). when Copy would need to be solved anyways to determine whether the operation would be well-formed in the first place.

[RalfJung]

And I do like borrowing stuff from C++ given that I'm implementing it as well.

I think that's a bad argument. You decided to solve a crazy hard problem by having tight integration of Rust and C++ in your compiler, but I feel strongly that this should not impact Rust design decisions. We should of course look at C++ and see if there is anything there for us to learn from, but if we think we can do better or there is a more "Rust-y" approach then implementation concerns of a 3rd-party compiler are IMO not a relevant point. That's why I keep asking you to phrase your concerns in terms of arguments that apply to Rust in general, and are independent of the particular implementation choices you made. (And most of the arguments you are bringing in this thread are indeed general, I just felt I had to call out this particular one since it is new.)

I'd like to avoid having to call the trait solver during irgen in general

There's tons of trait resolution happening during monomorphization. Checking Freeze is just one of them. So conceptually Freeze doesn't introduce any kind of trait solver dependency that we don't already have.

Are you suggesting we get rid of Freeze entirely (except as a rustc implementation detail)?

---

In the end we are weighing some amount of optimization potential against the simpler model of "the aliasing guarantees of &T are determined by a trait query on T". I can see good arguments both ways and find it hard to make an objective call here. I personally have strong feelings regarding making the model simpler, hence by bias is towards the 2nd option, but I also see why a compiler dev would equally strongly bias to the 1st option.

[chorman0773]

I think that's a bad argument. You decided to solve a crazy hard problem by having tight integration of Rust and C++ in your compiler, but I feel strongly that this should not impact Rust design decisions

To be clear here, the thing that got borrowed is the granularity - I could fairly easily just remove the top-level readonly on the pointer, like rustc does. Using mutable here simply means I'm capable of exploiting the granularity of UnsafeCell beyond the trivial case of UnsafeCell<()>. The thing I'm "borrowing" from C++ is the optimization, not necessarily the implementation-level constraint. lccc is likely going to keep clang's restrict extension and further extend it with `const T& restrict`, which will have similar behaviour to &T in rust. It also wants granularity of mutable, though imo to a lesser extent, because mutable is rarely used (mutex is one of the most common cases, so you can lock it in a const member function). By representing them the same way, in which the C++-style makes sense for, both can benefit from the same optimization here.

Are you suggesting we get rid of Freeze entirely (except as a rustc implementation detail)?

In my opinion, if Freeze is exposed, which is a separate question, it should be sealed by the standard library (impl(priv)) and usable by user-code as a way to determine if a type contains interior mutability, and shouldn't be user-implementable as a way to cause a type to have interior-mutability.

[CAD97]

if Freeze is exposed, which is a separate question, it should be sealed by the standard library (impl(priv)) and usable by user-code as a way to determine if a type contains interior mutability, and shouldn't be user-implementable as a way to cause a type to have interior-mutability.

For clarity, that's the wrong direction. IF Freeze is implementable, implementing it would say that a type doesn't use shared mutability. To unimplement the trait and add shared mutability, you'd need to contain some PhantomUnfrozen (e.g. UnsafeCell<()>) marker ZST (assuming shared mutability is entirely top-level rather than byte-granular).

So technically speaking, user implementable Freeze and granular shared mutability are separate axes. It's just that it's a more directly meaningful property to Rust programmers (as opposed to compiler developers) if it's "is/isn't shared mutable" instead of "may/doesn't have shared mutability" (before indirection).

Making it byte granular is certainly optimization potential, and we've deliberately left open room to make pinning's uniqueness relaxation granular rather than infectious. It's a tradeoff between model simplicity and optimization potential. The fact that it's (almost certainly) necessarily leaky across enum variants biases me towards making it the simple infectious version, because it's no longer a tradeoff between loose or exact tracking, but between loose or "usually exact except for when it commonly isn't" tracking.

If enums didn't put that caveat on exact tracking, I'd be for it near unambiguously; code already should be working under a strict tracking interpretation most of the time because reborrowing to an "infected" field will reintroduce the noalias-quality.

---

Interesting (but probably bad) concept I haven't seen mentioned: retagging could be precise on enums without imposing indirected validity requirements if when reading the discriminant it treats an invalid discriminant as any/unknown and retags the worst case, but precisely for valid discriminants.

[RalfJung]

Interesting (but probably bad) concept I haven't seen mentioned: retagging could be precise on enums without imposing indirected validity requirements if when reading the discriminant it treats an invalid discriminant as any/unknown and retags the worst case, but precisely for valid discriminants.

It's not just enforcing validity requirements that I object to, it is having any memory accesses at all as part of figuring out "which bytes gets which aliasing rules". Those accesses should themselves be subject to aliasing rules, leading to some challenging reentrancy in the aliasing model. We better don't do any reads that would invalidate other pointers elsewhere (except if the retag would anyway have invalidated those pointers).

At the very least we would want to prove a theorem showing that it doesn't make a difference whether those accesses are subject to the aliasing rules or not. So we can only read things that are anyway already considered to be read by the retag.

[chorman0773]

If enums didn't put that caveat on exact tracking, I'd be for it near unambiguously; code already should be working under a strict tracking interpretation most of the time because reborrowing to an "infected" field will reintroduce the noalias-quality.

FWIW, I don't see enums (and unions) as special under the vertical proposal: structs are also subject to "If a byte is covered by an UnsafeCell in any variant, it's tagged SRW/Reserved", it just so happens that a struct only has the one variant to care about.

In this way, the behaviour is not unique to enums (or unions).

[chorman0773]

As a further note on being more precise than vertical accross the variants: unions must necessarily be at most as precise as the vertical proposal AFAIK, only enums could be variant-precise. I don't know if there's much benefit to being more precise just for enums, and IMO it's definitely not worth the design work of getting an acceptable model for that - I don't think there are many optimizations that can benefit, and I certainly cannot see any of the implementations we have in various stages of progress being able to benefit (that being said, it is entirely possible that a novel compiler could come up with such an optimization, but TBH I can't see what such an optimization would be).

[danielhenrymantilla]

By the way, in the context of wanting to DIY a Covariant{Unsafe,}Cell<T> type, I thought of the following design:

#[repr(C)]
union CovariantCell<T> {
    value: ManuallyDrop<T>,
    _mutable: ManuallyDrop<Cell<u8>>,
}

I have talked about it over here, where you can find context about the motivation for it (I have also asked over Discord, where I have been told that this question may still be in the air, hence my posting this): I am not sure about how this model (or TB) may evolve w.r.t. this, so if the vertical proposal is a real possibility I should amend my comment accordingly. I do think it would be valuable to be able to write a CovariantCell<T> one way or another.

• Bonus question: what about a _mutable: UnsafeCell<Zst>, e.g., UnsafeCell<()>? (to try and keep the T : Zst => CovariantCell<T> : Zst property). It wouldn't affect the Freezeness of the type, so it could work, but then again how much is it guaranteed for UnsafeCell<()> : !Freeze to remain true?
  • (if Freeze were to be exposed, based on with_negative_coherence, having UnsafeCell<()> become Freeze would then be breaking)

[chorman0773]

One reason I think that limitations on UnsafeCell tracking should apply to unions as well, is that enums should (at least logically) be definable in terms of unions, and if the behaviour differs between an enum and a union, that would be surprising. This shouldn't be regarded as a massive concern on my side, and I'd forgo that equivalence if necessary.

On Sat, May 27, 2023 at 08:01 Daniel Henry-Mantilla < @.***> wrote:

By the way, in the context of wanting to DIY a Covariant{Unsafe,}Cell type, I thought of the following design:

[repr(C)]union CovariantCell {

value: ManuallyDrop<T>,
_mutable: ManuallyDrop<Cell<u8>>,}

I have talked about it over here, where you can find context about the motivation for it https://github.com/matklad/once_cell/issues/167#issuecomment-1564262379 (I have also asked over Discord, where I have been told that this question may still be in the air, hence my posting this): I am not sure about how this model (or TB) may evolve w.r.t. this, so if the vertical proposal is a real possibility I should amend my comment accordingly. I do think it would be valuable to be able to write a CovariantCell one way or another.

• Bonus question: what about a _mutable: UnsafeCell, e.g., UnsafeCell<()>? (to try and keep the T : Zst => CovariantCell : Zst property). It wouldn't affect the Freezeness of the type, so it could work, but then again how much is it guaranteed for UnsafeCell<()> : !Freeze to remain true?
  • (if Freeze were to be exposed, based on with_negative_coherence, having UnsafeCell<()> become Freeze would then be breaking https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=68cf54a59a88325a7fef15d3afad47ed )

— Reply to this email directly, view it on GitHub https://github.com/rust-lang/unsafe-code-guidelines/issues/236#issuecomment-1565372080, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABGLD25UM63A4XDANOZQEBLXIHULLANCNFSM4N4GIRZQ . You are receiving this because you commented.Message ID: @.***>

[Jules-Bertholet]

I do think it would be valuable to be able to write a CovariantCell<T> one way or another.

FWIW, I think that this should ideally be supported via a proper language feature—something like unsafe impl<T> covariant_in<T> for MyStruct<T>;. The memory model shouldn't be permanently pessimized just to work around (hopefully temporary) deficiencies in the Rust language.

[CAD97]

One thing I realized is that match guards are more complicated than I originally realized; it's not sufficient for the guard to receive a shared retag; it needs a (partially) precise retag.

Specifically, given something like

type T = Result<(u8, Cell<u8>), Cell<u16>>;
fn f(_: &T) -> bool { false }

let x: T = Ok((1, default()));
match x {
    Ok((0, _)) => ..,
    a if f(&a) => ..,
    Ok((1.., _)) => ..,
    Err(_) => ..,
}

the passed reference's pointee's tags needs to be shared-immutable on the first payload byte and shared-mutable on the second payload byte.

(Though actually it'd be acceptable w.r.t. the match for the guard to mutate the first byte if it returns true.)

I think the exact rule might amount to that for the purpose of match guards, the scrutinee is retagged individually for each subplace which has been scrutinized rather than with the reborrowed place type.

This tangentially relates to deref patterns. Specifically, in that (mutable) derefs share the same problem of being able to mutate the derefed-to place despite pattern matching expecting it to be immutable. I think the solution can be similar; specifically, when structurally matching a (projected) place, take and hold a single shared reborrow of the place through the final pattern structurally matching on that place, using that borrow for each comparison. This naturally makes any shared mutation relying on infectious relaxation cause UB when hitting the next pattern which assumes the place remains unmutated.

[RalfJung]

I wasn't thinking the guard would receive a shared retag. The shared (forced-immutable) retag is only used for the reads of the match itself; the guard will receive the parent reference.

(This is a question for https://github.com/rust-lang/unsafe-code-guidelines/issues/399 though, not this thread.)

[RalfJung]

When talking about more precise UnsafeCell tracking for Tree Borrows, an interesting question arises: what about all the bytes outside the type's memory range? (assuming no strict subobject provenance)

If the type is Freeze, we pretty much have to make all those bytes read-only as well, otherwise we violate noalias. But if otherwise we could do something like attempt more precise tracking inside T, but allow interior mutation outside of T -- or we could say the range outside is all read-only.

This is relevant for examples like this.

[RalfJung]

Another related question: does UnsafeCell inside PhantomData do anything? Currently it does not. But maybe we want to change that?

[chorman0773]

I'd say no - PhantomData is just that, non-existant data. I wouldn't expect to become !Freeze if I'm trying to opt-out of Sync and/or RefUnwindSafe. Even if it was somehow meaningful, I'd expect it to be the same as UnsafeCell<PhantomData>, no bytes exist inside the UnsafeCell.

On Sun, Jul 16, 2023 at 08:32 Ralf Jung @.***> wrote:

Another related question: does UnsafeCell inside PhantomData do anything? Currently it does not. But maybe we want to change that?

— Reply to this email directly, view it on GitHub https://github.com/rust-lang/unsafe-code-guidelines/issues/236#issuecomment-1637072799, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABGLD2YYZAM6LNMMRXGXTGLXQPNPLANCNFSM4N4GIRZQ . You are receiving this because you commented.Message ID: @.***>

[RalfJung]

See here for the (pretty reasonable) motivation.

[chorman0773]

BTW, I have used PhantomData<UnsafeCell<()>> to opt out of Sync in some cases involving FFI (without opting out of readonly noalias). I'd be rather suprised if that opts-out of the optimization I'm trying to avoid opting out of.

There's no other good way to opt out of Sync but not Send without adding extra unsafe impls (I've also used PhantomData<&'static UnsafeCell<()>> for both, I prefer it over raw pointers).

[RalfJung]

I have used PhantomData<UnsafeCell<()>> to opt out of Sync in some cases

IMO that's clearly a hack, so I don't see that as a good argument for "you must keep noalias optimizations in that case".

[chorman0773]

IMO that's clearly a hack, so I don't see that as a good argument for "you must keep noalias optimizations in that case".

Is it though? Using PhantomData arround appropriate types is the way you are supposed to opt-out of auto traits.

[RalfJung]

Yes but UnsafeCell lacks several auto traits -- Sync and Freeze. You cannot reasonably expect its Phantom version to only affect one of them. Nor do the docs say "use a phantom UnsafeCell to opt-out of Sync".

[chorman0773]

Isn't there impl<T: ?Sized> Freeze for PhantomData?

On Sun, Aug 6, 2023 at 10:11 Ralf Jung @.***> wrote:

Yes but UnsafeCell lacks several auto traits -- Sync and Freeze. You cannot reasonably expect its Phantom version to only affect one of them.

— Reply to this email directly, view it on GitHub https://github.com/rust-lang/unsafe-code-guidelines/issues/236#issuecomment-1666873660, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABGLD2Y6ZTYUGULTQISFAXDXT6Q2TANCNFSM4N4GIRZQ . You are receiving this because you commented.Message ID: @.***>

[RalfJung]

Not that I know of.

[chorman0773]

https://stdrs.dev/nightly/x86_64-unknown-linux-gnu/core/marker/trait.Freeze.html lists it.

[CAD97]

In any case, Freeze is currently an internal implementation detail and those details are permitted to change. It currently attempts to answer the question "is any byte shared mutable" roughly as accurately as possible, and thus we have that PhantomData<_>: Freeze unconditionally, but if Freeze were to be exposed and semantic, I would personally expect PhantomData to be transparent to it like it is to all other exposed auto traits.

There's no other good way to opt out of Sync but not Send

You can use PhantomData<&'static mut Cell<()>> for Send + !Sync just like you can use PhantomData<&'static Cell<()>> for !Send + !Sync. But for this reason I've often wanted some kind of PhantomSingleThread: Send + !Sync, PhantomThreadStuck: !Send + Sync, and PhantomThreadLocal: !Send + !Sync, but naming is hard, and "by example" is usually sufficient and also opt out of [Ref]UnwindSafe roughly correctly.

oibit impl rambling

When possible, I do think it's generally preferable to avoid exposing any types with explicit impls for autotraits, because the rustdoc render is preferable for the automatic trait impl than explicit ones, especially since I prefer to bound the impl "by example" but the `where` obligations should preferably be collapsed in the docs like the auto impl obligations are, e.g. I'd bound a custom `Rc`'s obit impls with `where std::Rc: Oibit` but still prefer the docs to say `where T: Oibit`.

[chorman0773]

You can use PhantomData<&'static mut Cell<()>> for Send + !Sync just like you can use PhantomData<&'static Cell<()>> for !Send + !Sync.

I'd note that this also opts-out of UnwindSafe, but I mostly treat {Ref,}UnwindSafe as if it doesn't exist. I don't like adding more decorators than necessary though (Although, says the person who does use PhantomData<&'static UnsafeCell<()>> instead of PhantomData<*const ()>).

And yes, please give actual auto-trait opt-outs. I work with a lot of code that is on older versions of rust, though, for various reasons.

And in general, I think it's reasonable to expect PhantomData to have no runtime implications on a type given that is how it's documented. Another example is a user implementation of Box<T> or other Collections. I would not expect to be able to replace the pointer behind a &Box<AtomicI32>, implemented as:

pub struct Box<T>{
    ptr: NonNull<T>,
    phantom: PhantomData<T>
}