Repository navigation
Validity of unions #73
Description
Discussing the validity invariant of unions.
One possible choice here is "none, any bit pattern is allowed no matter which types the fields have, and including uninitialized bits".
We could also decide that e.g. a
union Foo { a: bool, b: (bool, u8) }must start with the first byte being either the bit-pattern of false or the bit-pattern of true, because all fields agree on that invariant.
Notice that we cannot require the union to be valid for some field: for a union like
union Mix {
f1: (bool, u8),
f2: (u8, bool),
}we want to allow a bit pattern like 0x3 0x3, which can occur from code like
let m = Mix { f1: (false, 3) };
m.f2.0 = 3;There is no demonstrated benefit from disallowing such code, and this kind of code seems perfectly reasonable around unions.
Given that, any validity invariant that wants to restrict the set of allowed bit patterns will be rather complicated. However, such an invariant would enable us to e.g. layout-optimize Option<Foo>, whereas the "anything goes"-invariant would prohibit any kind of layout optimization around unions.
Activity
RalfJung commentedon Jan 10, 2019
My personal preference is to allow any bit pattern, mostly to keep things simple. Unions are already complex enough, and they only occur in unsafe code, we should make this as simple to use for the programmer as we can.
If we ever desparately need to layout-optimize
Option<Foo>, I propose we add attributes that let us control this -- something like a stable version ofrustc_layout_scalar_valid_range_start.nikomatsakis commentedon Jan 31, 2019
I feel like @joshtriplett and @cramertj have both, in the past, expressed strong opinions about this.
I think I agree regarding allowing any bit pattern. That said, I can definitely imagine wanting to be able to create a
unionthat is "as optimized" as the equivalentenum, but that it has no discriminant (because you know you can figure that out from other means).nikomatsakis commentedon Jan 31, 2019
@RalfJung
It seems like this would be true only if the Rust compiler decided to lay the fields out at offset zero, right? Personally, I sort of think we should just guarantee that the Rust compiler will do so. Particularly if we decide that unions are an opaque "bag of bits" from the perspective of the compiler, what is the motivation for the compiler to add extra padding into that bag?
(The same applies to your second example.)
RalfJung commentedon Jan 31, 2019
Yes, I've been assuming that to be the base.
Yeah I remember that as well. Also @petrochenkov expressed the opposite opinion, namely that unions should have a non-trivial invariant.
I can imagine wanting to do many things. :) But I feel such needs are better served by an opt-in attribute, than enabled per default.
cramertj commentedon Feb 1, 2019
Yep, I would prefer this for non-
repr(C)unions. IMO the common case (the FFI stuff) should always userepr(C), so this should be a non-issue for most folks. We could even lint on non-repr(C)unions just as a "be sure you know what you're doing, and that this is uncommon" hint.RalfJung commentedon Feb 1, 2019
Could you spell out what you mean by "this"?
gnzlbg commentedon Feb 4, 2019
I also think that we should guarantee this, but @joshtriplett mentioned some reasons about why we might not want to do that in the discussion about the layout of unions (#13 (comment)). It's unclear to me whether that interchange achieved some consensus, but maybe we should open a different issue to discuss whether we might want to guarantee this particular thing ? That would need amending the layout of unions in the repo.
EDIT: for
repr(C)unions, the fields always start at offset 0 AFAIK.hanna-kruppe commentedon Feb 4, 2019
That question can't really be separated from what we're discussing here: these kinds of layout optimizations are only possible if unions have a non-trivial validity invariant relating to the validity invariants of the fields. If we achieve consensus here that unions are just bags of bits, then it should be uncontroversial that there's no reason to place union fields at nonzero offsets. Conversely, the desire for layout optimizations of unions is a reason to want some non-trivial validity invariant for unions. I believe that's why nothing was settled during the previous discussion of union layout.
cramertj commentedon Feb 5, 2019
@RalfJung
Yeah-- I'd like the opportunity to optimize based on known-invalid bitpatterns for
repr(Rust)unions.RalfJung commentedon Feb 5, 2019
@cramertj So what do you think about code like this, which violates the principle that at any time, some variant of the union is valid?
From what I recall, this is something we explicitly want to support. It is also rather hard to argue that this is UB because it never actually performs an operation that "sees" a bad value.
Given that unions are basically sugar for transmutes, I am really worried about automatically assuming that any of their bit patterns are invalid.
cramertj commentedon Feb 5, 2019
oh wow what a mess, good point! I'd still argue that the niches left over from overlapping all variants (e.g.
union Mix { f1: NonZeroU32, f2: NonZeroU8 }) could be supported, but that is more complicated than what I originally imagined.RalfJung commentedon Jun 20, 2019
I thought I had written down what the validity invariant could be to justify layout optimizations such as what @cramertj is asking for, but it seems not here... it would be something like:
Bit/byte i of the union is allowed to have value v iff there is a variant of the union such that bit/byte i of the variant is allowed to have value v. We assume all variants to be "filled up" to the same size with padding, which may have any value.
Whether it should be bits or bytes is unclear, as are a few other things. For example, this kind of implicitly assumes that validity talks only about the bits, but it might also talk about contents of the memory and then things become even more messy. Also this is very hard to check for in an implementation of our dynamic semantics.
One thing that everyone seems to agree on though (including the above definition) is that if the union has a field of size 0 (such as is the case for
MaybeUninit), then it may contain any value and thus there can be no layout optimizations.HadrienG2 commentedon Jun 20, 2019
This property certainly is necessary for the current implementation of
MaybeUninitto be sound:57 remaining items
RalfJung commentedon Jul 6, 2023
Sure, we can write such an algorithm as part of the Rust-to-MiniRust lowering. As I said, that's what we already do for constructing the "chunks".
But in MiniRust, actually checking whether the type representation for a given type satisfies this property is not possible. I thought that's what you were asking.
digama0 commentedon Jul 6, 2023
Let me put it this way: rustc picks some implementation-defined strategy, maybe including randomness or the phase of the moon, to determine for each type what its layout is. This layout is described by a grammar, which is already written down in minirust - this is
Type, as far as I can tell. You can then evaluate given an element ofTypewhether it satisfies all the local validity requirements.We already have
Type::inhabitedwhich determines whether a Type "has any elements" without having to do anything like an exhaustive enumeration of values. This would be just like that, but for determining whether a type structurally cannot hold uninit at a given byte, because it's not padding and it is part of an integer value, something like that. (It would then be a theorem that ifty.valid_for(i, UnionByte::Init)is true thenty.decode(bytes).is_some()impliesbytes[i]is initialized.)Is there something about
Typethat makes it unsuitable to do this? Everything I can see in the definition would imply that you can write avalid_for()which is basically linear time computable.RalfJung commentedon Jul 7, 2023
We have
inhabitedsince it affectsdecodefor references. It is completely okay to always setinhabitedto true.Sure, we could add some more syntactic structure for this. I don't see a good reason to do that though since MiniRust doesn't care. This is entirely on the frontend. The Rust-to-MiniRust translation will specify the set of possible layouts to choose for any given union, and that is where we will need such an analysis -- but not inside MiniRust itself.
chorman0773 commentedon Jul 10, 2023
Yes, the bytes are valid. Or, the validity predicate for a union type is
valid(b)=true.I can't see any rule that could assign a validity invariant that doesn't involve a massive Decision tree. And even then, only something trivial like:
would actually get assigned any invalid bit patterns.
At the most, we could limit
uninitbytes to where any variant allows anuninitbyte, or a padding byte introduced by the union itself (either tail padding, or, for the repr(Rust) union fans, leading padding). I can't see this reasonbly being exploitable, though, especially since if we do read out a scalar (or something that contains scalars), we know it's notuninit.RalfJung commentedon Jul 10, 2023
@scottmcm why did you say it was important here that this type be
noundef?scottmcm commentedon Jul 13, 2023
@RalfJung I don't have any concrete issue. It's just that it's a scalar pair, so today it's passed as
ptr noundef nonnull+ptr noundefin LLVM function arguments (https://rust.godbolt.org/z/Wr93ExKod) and I worry that losing thatnoundefon the second pointer would inhibit optimizations.scottmcm commentedon Jul 13, 2023
Oh, wait, it's worse than I thought -- if I used a
unionthen it's no longer eligible to be a scalar pair at all, and gets passed by pointer instead https://rust.godbolt.org/z/bWhEGeYs1.CAD97 commentedon Jul 15, 2023
That led to me doing some more experimentation and discovering more ways
#[repr(transparent)]has fun implications, in thatMaybeUninit<(usize, usize)>gets passed as twoi64LLVM parameters at the LLVM level, meaning it'd lose any provenance. This is compared toMaybeUninit<(*mut (), *mut ())>which gets passed as twoptrLLVM.For the specific case of
#[repr(transparent)], presuming we want to preserve ABI transparency, I think the validity effectively has to be exactly the transparently wrapped type's, except that bytes may also storeuninit, and with copies only preserving the same bytes as for the wrapped type. (Importantly, this doesn't impact whether provenance is valid.)(Apologies if this was asserted upthread; I don't recall it being directly stated, at least not so plainly.)
RalfJung commentedon Jul 16, 2023
My hope was always that we'd eventually get the ability to annotate types to add the attributes we want, instead of somehow having to preserve them through a union. (E.g. you'd probably also have situations where you would want to preserve the nonnull.)
A
repr(transparent)union should help.Well, maybe it would, it's not like LLVM specifies this. Doesn't LLVM itself even sometimes turn ptr loads into i64 loads?
The much-discussed "byte" type in LLVM would fix this. So we could also document this as a known issue (unlikely to cause trouble in practice) with the LLVM backend caused by an LLVM limitation, and hope LLVM can one day give us a clear answer for how to express "a type of a given fixed size that gets passed in registers and can carry provenance". I think currently they would say i64 is the type to use for that.
scottmcm commentedon Jul 20, 2023
I must have misunderstood your point here, because I can't make a two-field transparent union:
https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=28e02ef2968d6500948188e22b976db8
RalfJung commentedon Jul 20, 2023
Ah, interesting.
MaybeUninit<(NonNull, usize)>will be a scalar pair. So probably you need arepr(transparent)union with one field that is a pair.scottmcm commentedon Jul 20, 2023
I don't think that would really help me in #113344, though.
The union would be convenient -- and way less MIR -- if instead of
I could just write
But sticking a pair into a transparent union doesn't make things any easier than just having the
*const Tfield -- it probably makes it overall way harder since accessing the begin pointer becomes messy too.I guess what this boils down to is that I want an "unsafe enum", not really a union. (Not that I know what to do with that observation.)
RalfJung commentedon Jul 21, 2023
Ah sorry, what I said makes no sense.
I guess this is a layout computation thing... a union where all fields are scalar of the same size, could be passed around as a scalar.
RalfJung commentedon Aug 2, 2023
This issue got too long and just asking about the validity invariant skips some key aspects (such as which bytes are preserved when a union gets copied). Closing in favor of #438, which I think summarizes the remaining open questions here and merges this with #156.