Deterministic (but undefined) layout

[nikomatsakis]

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.

[nikomatsakis]

Key comments from #11:

@asajeffrey writes:

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.

@RalfJung writes:

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.

@gankro writes:

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 that f32 has an alignment of 4 in the platform being targeted - the maximum alignment of a field of F is then 4. Would it be ok for the compiler to increase the alignment of F to 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 to 16 to facilitate SIMD operations.

[nikomatsakis]

Sorry if I missed any.

[the8472]

• 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?

[ChrisJefferson]

I 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).

[rodrimati1992]

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 phantomtype attribute would allow these transmutes to be safe (always keeping the same T) :

• WithMetadata<u32,()>> to WithMetadata<u32,Initialized>
• WithMetadata<Rectangle<u64>,Uninitialized>> to WithMetadata<Rectangle<u64>,Initialized>
• Arc<WithMetadata<String,NoneMetadata>> to Arc<WithMetadata<String,SomeMetadata>>
• Box<WithMetadata<Arc<LargeStruct>,U10>> to Box<WithMetadata<Arc<LargeStruct>,U20>>

The phantomtype attribute would not guarantee these having the same memory layout:

• WithMetadata<u32,()>> compared to WithMetadata<i32,()
• WithMetadata<(),()>> compared to WithMetadata<PhantomData<fn()->Vec<u32>>,()>
• WithMetadata<Vec<usize>,()>> compared to WithMetadata<Vec<isize>,()>

[the8472]

That's quite a special case that does not generalize well to the myriad of heterogeneous structs with multiple non-ZST fields. It would fall under #34 already.

[rodrimati1992]

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

[the8472]

Well, it would still be determined by some of its generic parameters, T in that case, obviously each concrete T can result in different layouts even though it's always the same generic fields being present.

[Gankra]

I stand by my exact request; I'm fine with field re-ordering being the exact thing allowed.

[the8472]

@gankro couldn't that prevent some optimizations, e.g. reducing alignment (and thus size) when there are no references are taken on a private member?

[strega-nil]

@the8472 that's legal under as-if

[RalfJung]

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

[the8472]

@RalfJung even with the same input couldn't slight changes to the program plus optimization fuel change which structs get optimized and which don't?

[alercah]

I'm a big fan of randomized layout personally. I'd much more happily assert that layouts can be randomized rather than try to offer any guarantees about determinism besides those that we view are required for interoperability.

…

On Sat, 13 Oct 2018 at 08:04 the8472 ***@***.***> wrote: @RalfJung <https://github.com/RalfJung> even with the same input couldn't slight changes to the program plus optimization fuel change which structs get optimized and which don't? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#35 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AT4HVShyH7idIV5u8KaR7A2yKuVTT1rfks5ukdbHgaJpZM4XYCOx> .

[gnzlbg]

@rkruppe

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

We might not want to think of the source code "written by the user" as part of the input to this deterministic function, but only think about the Rust that's left after macro expansion for this. If build scripts, proc macros, etc. have non-determinism, then that just produces a different "program".

@alercah

I'm a big fan of randomized layout personally. I'd much more happily assert
that layouts can be randomized rather than try to offer any guarantees
about determinism besides those that we view are required for
interoperability.

It doesn't have to be either or. I sometimes, during debugging, want fully deterministic builds to reliably reproduce an issue, and other times, also during debugging, want fully randomized layouts to see if one bug is caused by some layout assumption. This screams "implementation-defined", but that does not mean that the spec cannot say anything more about it. The spec could say that: "layout is implementation defined but must be defined in one of the following ways: ..." leaving it to the implementation to pick one (e.g. depending on build flags), but not allowing implementations to invent new ones.

In any case, it might be interesting to come up with "definitions" for the relevant cases that we might want to have, and then reconsider what to do here. If we decide to make it defined to one of these, or implementation defined, then we just pick one or some of the definitions, and if we leave it as unspecified, then we drop them.

[the8472]

I guess @RalfJung is aiming for reproducible builds, correct? Maybe the solution is to make struct layout conditionally deterministic.

Preconditions: no optimization fuel limit, no randomization, ???
Inputs: unordered sizes and alignments of struct members, layout-relevant attributes, PGO profile, compiler version, target specification, optimization flags, source (whole program? compilation unit?)

Some Inputs can also be shifted to preconditions. I.e. we can simply say it's only deterministic if certain optimization flags are disabled.

[RalfJung]

Builds should be reproducible, yes (not sure if that is a sufficient condition though). I got nothing against a flag to randomize stuff for debugging, but we shouldn't do that in normal release builds.

even with the same input couldn't slight changes to the program plus optimization fuel change which structs get optimized and which don't?

So make fuel part of the input.

Fuel changes the game in annoying ways anyway, similar to PGO actually, in taht adding new structs can change the layout of the existing ones. So if our definition is ready for PGO then fuel shouldn't cause extra problems, and if we decide we don't want to support PGO then our rule should say it only holds when fuel is not used. Both seem like reasonable options to me.

[the8472]

Another option for determinism is hashing the fully qualified name of the struct and using that as input for layout. That way a struct could retain a its layout between builds but two different structs with the same members would end up with different layouts, thus discouraging punning between repr(Rust) type without additional annotations.

[Gankra]

@RalfJung no I'm saying I am fine with it being non-deterministic as long as the non-determinism is constrained to field-reordering, with an otherwise simple and deterministic (same as repr(C)) alignment/padding algorithm.

[ChrisJefferson]

Something which is worth separating is the behaviour of the compiler under default / "sensible" settings vs what is EVER allowed.

I can understand someone not wanting field randomisation in their build, so they can tune ordering and achieve greater performance.

However, do we want to ban field randomisation from ever being valid in a Rust implementation? Banning it from ever being valid feels like it would need an extremely good reason.

[gnzlbg]

Something which is worth separating is the behaviour of the compiler under default / "sensible" settings vs what is EVER allowed.

The goal is establishing what guarantees can unsafe code rely on - these guarantees must always hold; compiler settings cannot break these guarantee.

There does not seem to be a consensus about whether we want to allow Rust implementations to randomize the field order of repr(Rust) structs or not. If we want to support this use case, then do we want the compiler to be able to fully randomize things? (e.g. increasing struct size, alignment, etc?) Or do we want to add some constraints to the amount of randomization that we want to allow (e.g. a variation of @gankro 's comment could be that "alignment and size shall not be larger than if the struct were repr(C)").

[ChrisJefferson]

With regards alignment, when using SSE instructions I often use the macro _MM_ALIGN16, which forces a struct to be 16-byte aligned, so it's contents can be efficiently loaded for use with SSE instructions. It would be nice if the compiler decided it wanted to use SSE on a struct it could add this by itself.

Restricting the size to be no bigger than repr(C) seems like a really tight restriction, as if a struct is already efficiently packed that strongly limits the options for re-ordering the members.

[the8472]

@gnzlbg we have said a lot about why the compiler might want to change layout and why a dev might want stable layout for debuggability. But very little has been said why unsafe code would need some specific guarantee.

@rodrimati1992 brought one example, punning between the same generic type with different phantom generic arguments. Without an annotation signalling that intent this would be ok. Without such an annotation it would prevent the compiler from making different optimization choices for different uses of monomorphized types.

What other uses do we have? @gankro never stated how unsafe code would benefit from his requests for example.

[nikomatsakis]

An observation. If we did the following:

For example, we might say that struct layout is a function of the struct's generic types and its substitutions, full stop

but also included compiler settings in that equation, then we could still randomize layout, but we would be restricted that two structs with the same definition must still wind up with the same layout (which might be in any order etc).

In any case, I am getting more attracted to the idea of pulling out certain special cases (e.g., single-field structs in #34) and leaving the broader question for later.

[digama0]

Rather than a .bikeshed() method, couldn't that be an implementation of the very same TransmuteFrom trait? That way you can also O(1) transmute Vec<Vec<i32>> -> Vec<Vec<u32>> and so on.

[RalfJung]

Mmm, good point. It would be really nice to have some rules around whether this is ever safe though, as it is a very handy cast to be able to do in particularly "weird" unsafe code. In my case, I use it because I know that I'm operating on aliased values, and I essentially want to "turn" any drop of those values into a forget in some code that I do not control (e.g., HashMap::clear).

Do you know SomeType or is it somehow user-defined? Rust doesn't have Generic Associated Types / Associated Type Constructors, but once it does one could write code that is fully generic in SomeType. In such code it is certainly not okay to perform these transmutes -- we'd have to have some trait bound which ensures that there are no "associated type shenanigans". However, Rust doesn't GAT/ATC, so I wonder how much you concretely know about that SomeType.

[digama0]

I saw the stream, and in @jonhoo 's situation SomeType is a known (but complicated) nesting of types, a few struct wrappers around a HashMap or IndexMap. So some external types are used (you have to know the implementation of HashMap) but it's not completely generic. (The question is basically whether MyWrapper<HashMap<K, V>> and MyWrapper<HashMap<K, ManuallyDrop<V>>> are layout compatible.) He contemplated having a map interface to generalize over the map type, and in that case it would look a bit more dire, given the discussion here. Most likely the trait would have to directly support a ManuallyDrop-like operation, because you can't quantify over type constructors anyway.

[scottmcm]

couldn't that be an implementation of the very same TransmuteFrom trait?

That depends whether the standard library wants to make that promise. I don't know if it's willing to commit to never tweaking how it's stored.

Perhaps it will, and the only things that will need the method are things like O(1) Vec<[f32; 4]> -> Vec<f32> that cannot possibly be a transmute (without changing len to do a division or something).

[RustyYato]

For example, once we have the safe transmute traits to use as a bound, I hope to get vec.bikeshed() to allow O(1) Vec -> Vec and Vec -> Vec<MaybeUninit>, etc.

@scottmcm my vec-utils crate can do that VecExt::drop_and_reuse. It falls back to a map+collect if layouts are incompatible.

[jonhoo]

Another example of a potentially useful transmute is between SomeWrapper<T> and SomeWrapper<UnsafeCell<T>> with the same intended use-case as the ManuallyDrop transmute (see also #258 (comment)).

[the8472]

This was already discussed in previous comments. That transmute is incorrect in general (for arbitrary T) due to UnsafeCell being #[repr(no_niche)], i.e. size_of::<Wrapper<T>>() != size_of::<Wrapper<UnsafeCell<T>>>() for some combinations of T and Wrapper.

[jonhoo]

Continuing down this path, what about a transmute from

SomeWrapper<MyType<T, MyPrivateTypeA>>

to

SomeWrapper<MyType<T, MyPrivateTypeB>>

where MyPrivateTypeA and MyPrivateTypeB are both unit structs that implement no traits, and MyType holds only the T (and the private type in PhantomData) and is repr(transparent)?

I could be mistaken, but I think there is now no way to have an impl outside the current crate that distinguishes between the two types, and therefore the transmute should be safe?

[the8472]

While MyType's layout would be covered by the rule proposed in #34 (single field structs) it doesn't tell us what properties SomeWrapper would have. So in the general case for arbitrary wrapper types you'd have to assume the compiler could make different decisions for each different U in SomeWrapper<U>.

[jonhoo]

Hmm, that's unfortunate indeed. And it doesn't sound like you think there's any chance of that being the case subject to the discussion on this issue either without placing restrictions on the wrapper type? Essentially, I'm trying to find a way to use the type system to change the drop behavior of a type that is nested inside another data structure, but without being able to safely transmute the type "inside" the data structure, I cannot find a way to do so. Which leads me down the path of horrible hacks like https://github.com/jonhoo/rust-evmap/blob/4e83da000cfee94810eb790f25c1dc159def1b12/evmap/src/aliasing.rs#L79-L94. 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 (making the transmute safe), but it sounds like that's not the case.. hmm hmm hmm what to do.

EDIT: I tried to summarize my understanding of the discussion here over in jonhoo/left-right#83 (comment) in case it helps anyone who's trying to understand this issue.

EDIT2: A sketch of what I want to do in my implementation is jonhoo/left-right@sound-aliasing...drop-by-generic-type (the commit message has more details).

[the8472]

Essentially, I'm trying to find a way to use the type system to change the drop behavior of a type that is nested inside another data structure, but without being able to safely transmute the type "inside" the data structure,

Can you reach into the data structure to touch the values? If so you could try exploiting the niche optimization instead of using the type system. It would come at a runtime cost but at least you wouldn't be suffering size overhead to carry that state as long as types have niches.

E.g.

enum DropToggle<T> {
  On(T),
  Off(ManuallyDrop<T>)
}

[jonhoo]

In this case the wrapper type is a collection type (worse yet, a collection of collections), so while I could walk every value to toggle the value, that operation is quite expensive as it is proportional to the size of the collection, even if only one item actually ends up being dropped. Think of something like calling HashMap::retain with a user-provided closure — you would need to walk all the values in the map, flip all of them, run the retain, then walk all of them again to flip them off again.

[gThorondorsen]

Prior art related to the current discussion: Haskell's type roles and the Data.Coerce library (referenced in the safe transmute RFC).

[RalfJung]

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

[the8472]

Prior 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?