Repository navigation
Deterministic (but undefined) layout #35
Description
Activity
Key comments from #11:
Can we say something like we guarantee that the layout for a struct is only dependent on certain properties of its fields? Off the top of my head those are size, alignment and non-zero-ness, but there may be others. This would avoid having to propose an RFC with a language extension.
So, after all this talk about layout guarantees for structs... could we do a little practical exercise and see if rust-lang/rust#54922 if within bounds of the guarantees, or exceeding them? This does some manual layout computation that is supposed to recompute the layout of a
repr(Rust)struct with an unsized tail.Quickly chiming in with a +1 for restricting
repr(rust)to only reordering and still mandating natural/greedy c-style padding. This would make (align=1,size=0) types not affect layout, newtypes not affect layout, alignment predictable, and the size of heterogeneous types predictable. At the same time it would still allow us to do the only really relevant optimization of ordering the fields optimally. The fact that a theoretical field fuzzer wouldn't be allowed to be as powerful as it could be is not especially concerning to me.@gnzlbg writes (in response to @asajeffrey):
Can we say something like we guarantee that the layout for a struct is only dependent on certain properties of its fields? Off the top of my head those are size, alignment and non-zero-ness,
I don't know. For example, consider the
repr(Rust)struct F { x: f32, y: f32, z: f32, w: f32 }, under the assumption thatf32has an alignment of4in the platform being targeted - the maximum alignment of a field ofFis then4. Would it be ok for the compiler to increase the alignment ofFto say,16, to facilitate SIMD operations?We have been talking about guaranteeing the layout of homogenous tuples / structs, but I also imagine that this could happen somewhere else, e.g.,
struct G { a: u64, x: f32, y: f32, z: f32, w: f32, b: u64 }where{xyzw}get re-ordered at the front and the alignment increased to16to facilitate SIMD operations.Sorry if I missed any.
- deterministic layout would disallow intentional randomization for fuzzing or defense purposes
- as written it would have to remain stable between compiler versions, e.g. to allow serialization or punning between libs compiled with different versions, which would prevent future changes. In essence the current implementation would become the implicit but ostensibly undefined standard
- this could have spooky action at a distance where upgrading a dependency which is a member of a struct suddenly causes the struct itself to change layout
So I would like to pose the counter-question: Why should this be guaranteed?
Reacted by MinusGixI am +1 with @the8472 . My experience of C is that these kinds of limitations get annoying as time goes by, because newer ideas and compilers are limited by the old restrictions.
I'd actually be in favour of the compiler gaining randomisation, because (in my experience) even if something is technically allowed to vary, if it doesn't tend to change then people start to expect it being fixed.
Also randomisation seems (to me) a possibly cheap and effective anti-hacking technique -- if I can compile a program with a randomised order for every struct, it will be much harder for someone to make a repeatable hack, even if they find a suitable bug, as they won't know the layout of anything. Of course it isn't perfect by any means, but it's another layer of defense and I would want to see a good reason to throw it away.
If someone wants a well-defined fixed ABI, they can always use repr(C).
Deterministic layout seems appealing,especially if it is determined by the fields,not the generic parameters,
Even if layout is not deterministic,there should be ways to recover back some determinism through attributes.
One example attribute would be '#[phantomtype(C)]' which would guarantee that the generic parameters it lists cannot affect the layout of the type,only allowing PhantomData/types with the same attribute to mention those generic parameters.
#[phantomtype(C)] struct WithMetadata<T,C>{ value0:T, value1:Vec<u8>, _metadata:PhantomWrapper<C>, } #[phantomtype(C)] struct PhantomWrapper<C>(PhantomData<fn()->C>)The
phantomtypeattribute would allow these transmutes to be safe (always keeping the sameT) :WithMetadata<u32,()>>toWithMetadata<u32,Initialized>WithMetadata<Rectangle<u64>,Uninitialized>>toWithMetadata<Rectangle<u64>,Initialized>Arc<WithMetadata<String,NoneMetadata>>toArc<WithMetadata<String,SomeMetadata>>Box<WithMetadata<Arc<LargeStruct>,U10>>toBox<WithMetadata<Arc<LargeStruct>,U20>>
The
phantomtypeattribute would not guarantee these having the same memory layout:WithMetadata<u32,()>>compared toWithMetadata<i32,()WithMetadata<(),()>>compared toWithMetadata<PhantomData<fn()->Vec<u32>>,()>WithMetadata<Vec<usize>,()>>compared toWithMetadata<Vec<isize>,()>
One example where it doesn't apply?
This is the very specific problem of wanting to guarantee stable layout for types with phantom generic parameters(when the phantom type parameter changes).Well, it would still be determined by some of its generic parameters,
Tin that case, obviously each concrete T can result in different layouts even though it's always the same generic fields being present.I stand by my exact request; I'm fine with field re-ordering being the exact thing allowed.
@the8472 that's legal under as-if
@gankro We are discussing here whether we can say that layout is deterministic (with some list of inputs that may affect layout, and nothing else may). You are talking about constraining what layout may do, irrespective of its inputs. That's an entirely orthogonal discussion.
@ubsan "as-if"?
@rkruppe also writes in the PR:
I am not sure this wording reserves the freedoms it want to reserve, and even if someone argued it does I would like it to be clarified. Since we did not get consensus to rule out profile-guided layout, the program source code is not all that informs layout. Not even if that includes build scripts, input data files, etc. that are used during the profiling run, since the program may not be deterministic w.r.t. these (e.g. it might have race conditions or depend on the system time or ...). So I don't think we can guarantee anything involving the words "deterministic function" and have to stick to something like "every time you invoke the compiler you may get a completely different layout".
Even with PGO, we should be able to guarantee that given the same PGO profile data, we compute the same layout. I do not know how PGO works, but I assume there's a "collection" phase spitting out some data into a file and then that file is used by the next compilation? So that file would be part of the input to the deterministic function.
59 remaining items
Prior art related to the current discussion: Haskell's type roles and the Data.Coerce library (referenced in the safe transmute RFC).
I was hoping there might be a way to construct the inner types in such a way that the layout of the wrapper type is guaranteed to stay the same
So, you are asking for some amount of "parametricity" on the type level. That sounds like a very reasonable request. To make this work, we need to at least ensure that the two types also behave identically for every trait resolution query, to avoid associated type shenanigans. More precisely speaking, for any trait resolution query, replacing one of the types by the other anywhere in the query (including in nested positions, where clauses, whatever) must not affect the outcome of the query.
Your approach of using private types that implement no traits seems to be a nice step in that direction. Unfortunately I don't have enough intuition for specialization to really say if that is enough.
Outside of the trait system, I think our current layout algorithm is indeed parametric in that sense -- it cares about a few extensional properties of the type (size, alignment, niches), but as long as those remain the same, changing the type will have no effect. The main question here is if we want to make this a guarantee that will be maintained in the future. (That's what this issue was originally about.)
Reacted by Jon GjengsetPrior art related to the current discussion: Haskell's type roles and the Data.Coerce library (referenced in the safe transmute RFC).
So, my haskell is weak, but if I understand type roles document correctly then it is primarily about representing the difference between exact type equality vs. layout equality based on generic parameters in the type system and then goes on to suggest that exact (norminal) type equality should be the default for all types and layout equivalence should require explicit annotations. In other words they suggest that by default there should be no promises about layout equality.
The main question here is if we want to make this a guarantee that will be maintained in the future.
Technically the initial comment only asks whether it is a deterministic function of a fixed set of inputs. Those inputs could contain the exact type (nominal equality in the type roles document) or a random input.
It would also have to include something to preclude ossification of the ostensibly unspecified layout (e.g. the compiler hash), otherwise people would just dump memory representation to disk and expect it to be loadable in a later build.Questions that I think need to be answered
- Is there any value in the context of the UCG to guarantee deterministic layout where one of the inputs of the deterministic function is external lookup (PGO, layout randomization seed) and/or the full type name? It basically sounds like a non-guarantee to me.
- Do we want to keep the possibility of PGO-based layout or punning-hostile randomization open?
- Do we want to enable transmutation of inner types in arbitrary containers? If so should this require annotations on the container and/or the inner type? Which other conditions would apply? In other words, under which conditions whould the function be guaranteed to be surjective?
- How do we prevent ossification if we make such guarantees?
Reacted by Jon Gjengset- added 2 commits that reference this issue
on Dec 6, 2020 Does
-Zrandomize-layoutsatisfy any of the proposals made in this thread regarding determinism / parametricity of layout? AFAIK not, which probably means we should just close this issue as there's not really anything we'd like to guarantee here?Reacted by scottmcmAgreed, if this is a thing it should be an opt-in
reprbecause otherwise we're closing off unknown unknowns.If we'd done this in 2017 we would have said "well same size and align of a field means same layout", and that would have been a mistake because we now use more things than just that in the layout calculations.
Okay, let's close this for now. If this discussion is to be reopened it should be with a somewhat more concrete proposal.
Does -Zrandomize-layout satisfy any of the proposals made in this thread regarding determinism / parametricity of layout?
See tests/ui/layout/randomize.rs for its current behavior.
Currently it ignores any generic, maybe-unsized tail fields, which includes single-field wrappers, even if a particular instance of T might not be unsizable.
Additionally it does not inject padding at offset 0, but that might get added at some point rust-lang/rust#97861.
Combining these properties means that currently
SingleField(T) == SingleField(U)have the same layout even withoutrepr(transparent)¹ if T and U do.
That does extend toFoo<SingleField<T>>andFoo<SingleField<U>>, because we stop propagating the inner type information (if ?Sized).
It does not extend toFoo<SingleFieldA<T>>andFoo<SingleFieldB<T>>, becauseFoocan distinguish the wrappers themselves.These are current implementation details that could get tightened in the future.
Overall the rules are fairly complicated and subject to change that relying on
repr(Rust)transmutability is on very thin ice.¹ and as the test explains:
repr(transparent)on a non-generic wrapper does nothing, which meansFoo<Transparent(Concrete)>andFoo<Concrete>can get different layouts, due to potential associated-type-specialization ofFooin the future.
From #31: Can we say that layout is some deterministic function of a certain, fixed set of inputs? This would allow you to be sure that if you do not alter those inputs, your struct layout would not change, even if it meant that you can't predict precisely what it will be. For example, we might say that struct layout is a function of the struct's generic types and its substitutions, full stop -- this would imply that any two structs with the same definition are laid out the same. This might interfere with our ability to do profile-guided layout or to analyze how a struct is used and optimize based on that. (Some would call that a feature.)
Also, this presumably applies to enums as well as other types.