Specifying a set of transmutes from Struct<T> to Struct<U> which are not UB

21

MaybeUninit is also currently marked #[repr(transparent)] so it has similar issues in the opposite direction. Caring about niches just doesn't matter to the primary reason #[repr(transparent)] exists and in fact probable goes against it.

2 Likes
22

Right. I implicitly ignored unions and then just forgot to consider MaybeUninit there :sweat_smile: So yes, I agree that transparency is independent of niches.

In any case, validity of transmutes when niches are present is that the value being transmuted isn't in the niche of the target type. It's a little sad that this can't just be a safety requirement rather than a validity requirement, but these transmutes are too useful (and too used) to rule out.

Compatibility for transmuting in a container type is much more problematic, though. Because of niches, the requirement even for opt-in containers can't just be that it's sound to transmute the wrapped value, but that both types have identical niches as well.

I definitely think that transmute::<Vec<T>, Vec<Wrapper<T>>> should be sound, I'm just less and less sure how best to get there.

23

I'm not still convinced that transmuting Vec<T> to Vec<U> is really needed.

An easier transmutation &Vec<T> to &Vec<U> which is conceptually similar to pointer casts. When Vec is not owned, &Vec<u32> to &Vec<[u8; 4]> should be okay because layout equality is only issue when a buffer is dropped.

24

And why is that?

The one obstacle (that's specific to repr(C), i.e., isn't an objection to enabling any transmutes no matter how) I'm aware of is that it would silence the improper_ctypes lint when using HashMap in FFI, which is probably not great. That's why I suggested an attribute for deterministic layout without FFI baggage (not that libstd types would really need it, FWIW).

But that's about it. The other major thing repr(C) means is "no field reordering", but I don't see how that's going to be an issue for HashTables. They're composed of just a few pointers and usizes (which all have the same size and alignment) plus the S: BuildHasher. This isn't really dependent on implementation details (and indeed this fact was unaffected by the move to hashbrown). So the only field that's possibly beneficial to reorder is the BuildHasher, but in practice it's likely always optimal to just put it at the start. This requires no extra padding if the BuildHasher:

  • is a ZST (e.g., BuildHasherDefault<H>), or
  • has alignment is greater or equal to the usize / pointers (e.g., RandomState contains two u64s),
  • has a size that is a multiple of usize's size

This covers all existing BuildHasher impls and then some (I don't actually know of any real example of the last one) and should also cover practically every other conceivable state you might want to store to build hashers.

There might of course also be objections to allowing type punning of HashTables in the first place. It's been pointed out before that this requires the hashes of the elements to not change, people may have doubts about the usefulness of the operation, etc. but none of those are problems of repr(C).

1 Like
25

It's ok in this direction, with lesser alignment, but not in reverse.

26

Given that &Vec is pretty useless, and that we can already safely convert slices , I don't think that this is necessary.

1 Like
27

The validity for &_ transmutes is the same as for &mut _, so while we talk about transmuting &_ the &mut _ transmute is included and definitely more important for Vec.

That's why I talk about transmuting the owned value; transmuting the reference or casting a pointer follows the same rules for when it's valid (to interpret one value as another type).

It is theoretically simple to guarantee that distinct generic instantiations of the same type parameterized with transmute-compatible types (and value(s) of that type) are also transmute-compatible (when no associated types are involved) while retaining the theoretical permission to reorder fields between compiler invocations and between instantiations that aren't parameterized by transmute-compatible types.

Practically, though, this is more difficult, as you have to say when the guarantee applies and actually fully define what types are transmute-compatible and what uses of the type break the guarantee. Plus, you need the layout algorithm to respect this, while still applying reorderings as desired, just guaranteeing the reorderings are equivalent for compositions of transmute-compatible types.

28

Here is my attempt at a complete enumeration of all the transmutes that we want to consider "well-defined" or "not UB" (I believe the UWG people like the word "valid" here?); in other words, the sort of thing you can put in unsafe block in a safe function. I think a few of these have been discussed but I think we need to be explicit.

  • T <=> U for T, U numeric primitives of equal size (though not necessarily alignment). Unconditional[1].
  • T <=> [U; size_of<T> / size_of<U>] for T a numeric primitive and U an integer of equal or smaller size. Unconditional.
  • uN <=> NonZeroUN for N an integer with the obvious precondition when going from uN to NonZero.
  • uN <=> Option<NonZeroUN>. Unconditional.
  • &?mut T <=> &?mut U for T, U are any of the above pairs, and the conversion would not go & => &mut or violate produce a misaligned reference.
  • T <=> W, where W is a transparent[1] wrapper around T and the T => W conversion does not violate any constraints W has.
  • *?mut T <=> *?mut U. Unconditional.
  • *?mut T <=> &?mut T, such that creating a reference does not violate any of the obvious rules.
  • *?mut T <=> Option<&?mut T>, same rules as e.g. (*const T)::as_ref.
  • Vec<T> <=> Vec<U>, same rules as for references.
  • Cell<T> <=> Cell<U>, (maybe?) same rules as for references.
  • HMap<K, T> <=> HMap<K, U>, same rules as for references.
  • HMap<T, V> <=> HMap<U, V>, same rules as for references, and some nonsense about hash compatibility (unless T: !Hash or whatever).
  • PhantomData<T> <=> PhantomData<U>. Unconditional.
  • MaybeUninit<T> <=> MaybeUninit<U>. Conditional on size, maybe alignment?
  • The obvious C-struct conversions, maybe have alignment requirements.
  • T <=> U where U is a union with an active t: T variant; T -> U direction probably requires T to be as big as U in a bunch of unclear cases, at the very least when behind a reference???

A couple of questionable ones not mentioned yet:

  • [T] <=> T for single-element slices. Seems sketchy, and mostly not useful?
  • dyn T <=> dyn U, if we can figure out some "equivalence of traits" that guarantees identical vtable layout. Usefulness is deeply unclear, beyond transmuting dyn Derived => dyn Base.
  • We already commit to a layout for &[T]; we definitely want &[T] to be transmutable into that layout struct (and, probably &[T] <=> (usize, *const T), since tuples are laid out exactly like repr(Rust) types). I feel like there is a deeper connection with the type [T] = [T; dyn]; proposal.

I think the only really open question is parametricity. I'm in favor of some kind of single #[repr(transmutable)] that captures the above cases we don't have a good way to pronounce:

  • The transparent wrapper case.
  • The parametric case (namely, layout is deterministic and entirely determined by the transmutable equivalence class of its type parameters; probably also forbids associated types for good measure?). I think that any type that wants to be "parametric" should be declared as such by the author.

And, obviously, we probably want the compiler to lint (error by default, as is when transmuting & to &mut) any transmutations that are not in the list above (modulo preconditions).

[1] - I don't think we should be fussing about alignment in most cases, since anything small that isn't a reference is going to be in registers most of the time. Being worried about paying for spills is kind of something you can't worry about, and if you care, there's a perfectly good assembler right there. Certainly, I see no reason we can't go from [u8; 8] to u64 if a reference is never taken, and, if it is, we can do some re-spill nonsense that you were going to have to do anyway.

The above discussion doesn't really mention lifetimes, since those don't really exist at codegen time. 99% of my uses of transmute are to extend lifetimes for pinning purposes; I keep wanting some kind of transmute variant that accepts any type of kind lifetime -> lifetime -> ... -> type and makes all the lifetimes unbound (or, binds them all to a single specified lifetime 'a). I think such a thing would need to be a macro-like construct, though, since we have no way of expressing such a type signature.

29

Vec<T> and anything else that allocates must also ensure that the alignments are equal. This is different from references. Cell<T> should have the same requirements as T, not references, same with MaybeUninit<T> because they are both supposed to behave similarly to T.

[T] <=> T is slice::from_ref or slice::from_mut

I don't think we would ever want dyn T to be transmutable to anything other than itself.

30

What about dyn Trait<Assoc=T> to dyn Trait<Assoc=Wrapper<T>>?

31

Nope, never in general because of traits like this one,

trait Foo {
    type Bar: Control;
    
    fn do_something_with(&self, bar: &Self::Bar) {
        bar.do_something();
    }
}

trait Control {
    fn do_something(&self);
}

Even adding simple wrapper could have very different vtables.

dyn T<Assoc = Foo> is a different type from dyn T<Assoc = Wrapper>

32

Is this actually true? I see no reason you can't reinterpret a Vec<u64> as a Vec<[u8; 8]>; the Unique inside is still well-aligned, and on most systems most allocations are word-aligned, anyway.

Why? I certainly don't see any optimization opportunity that's to be lost by forcing a particular vtable order, if a trait derives exactly one other non-empty, non-Drop trait. You could also imagine transmuting to dyn Drop to completely erase the vtable.

33

Yes, quoting the Alloc docs

This function is unsafe because undefined behavior can result if the caller does not ensure all of the following:

  • ptr must denote a block of memory currently allocated via this allocator,
  • layout must fit that block of memory,
  • In addition to fitting the block of memory layout , the alignment of the layout must match the alignment used to allocate that block of memory.

and vec docs

This is highly unsafe, due to the number of invariants that aren't checked:

  • ptr needs to have been previously allocated via String / Vec<T> (at least, it's highly likely to be incorrect if it wasn't).
  • ptr 's T needs to have the same size and alignment as it was allocated with.
  • length needs to be less than or equal to capacity .
  • capacity needs to be the capacity that the pointer was allocated with.

emphasis mine

I remember seeing concerns that if you use a lower alignment, some allocators will allocate a bit more space and so when it comes to deallocating they will try and reclaim that space and that would fail because you lowered the alignment and that space wasn't actually allocated.

Ok, that is an interesting idea, I need to think this over a bit more. But my gut reaction is that trait objects are too unspecified for transmutes to be safe.

34

I remember seeing concerns that if you use a lower alignment, some allocators will allocate a bit more space

I'm kind of shocked that we support allocators that don't have the malloc/free interface. Is this actually used in practice? This seems like an extremely strong restriction. (Huh, Alloc::dealloc takes a Layout parameter. Not sure how I feel about that...)

But my gut reaction is that trait objects are too unspecified for transmutes to be safe.

Yes, we would be forced to specify Rust vtables as

#[repr(C)]
struct Vtable {
  size: usize,
  align: usize,
  dtor: fn(*mut ()),
  fns: [*mut ()],
}

where, if a Derived derives Base, fns must contain the functions of Base as a prefix. AIUI this is how rustc implements vtables (except perhaps the last requirement...), and, quite frankly, I doubt there is a better way to do it, seeing as this needs to be consistent across dlopen() calls (ruling out randomization at a minimum). This, basically, how C++ does it, I think (though C++ has deleteing dtors blah blah).

35

Even if we do force layouts like that, how do we guarantee the order of the function pointers? Also, what if a trait has multiple base traits?

36

That's the codengen's problem; we need to generate the trait method function pointers in some deterministic order (declaration order is probably safe??[2])

The transmute is always UB, I guess. For multiple inheritance, C++ (well, given Itanium ABI) just concatenates a bunch of vtables, and upcasting is just a static offset (and the vtable contains negative offsets to the "top" of the "real" vtable, which is what (along with the RTTI pointers) allows for downcasting).[1]

I think this is part of a larger issue of "I want to use dyn objects for crazy runtime polymorphism" that requires significantly more infrastructure. This paradigm is so out of the way for Rust that, honestly, I don't see what there is to gain from it, and we should probably table this particular variety of transmute.

[1] fwiw, this is not the only way to implement multiple inheritance: casting between interfaces in Go will actually synthetize vtables at runtime to avoid combinatorial explosion, which I think is a little too involved for Rust.

[2] Edit: declaration order isn't safe in the presence of dynamic linking, but seeing as we have dynamic linking, the compiler almost certainly already has to pick a deterministic way to lay out function pointers, so my point stands.

FWIW, this is what rustc currently emits as a vtable for a very simple trait inhertiance:

	.quad	core::ptr::real_drop_in_place
	.quad	8
	.quad	8
	.quad	playground::Derived::bar
	.quad	playground::Derived::bar1
	.quad	playground::Derived::bar2
	.quad	playground::Base::foo1
	.quad	playground::Base::foo
	.quad	playground::Base::foo2
37

Given that &Vec is pretty useless

I was thinking about when Vec<T> is in another struct.

Because Vec<u32> to Vec<[u8; 4]> is only UB when the buffer is reallocated or freed, we should take mutability into account when defining parameterized transmutation compatibility.


#[repr(C)]
struct S1<T>(Vec<T>, OtherType);

#[repr(C)]
struct S2(Cell<Vec<T>>, OtherType);

transmuting &S1<u32> to &S1<[u8; 4]> should be okay but transmuting &S2<u32> to &S2<[u8; 4]> is not.

It seems like this is related to variance. Which is not surprising because this is a kind of subtyping relation.

I wonder if existing subtyping/variance infomation can be extended to transmutation compatibility somehow? My feeling is this is the right way.

2 Likes
38

To be honest, I can't see why we would even want to devote so much energy into trying to make any form of Type<u32> -> Type<[u8; 4]> well-defined. What is the actual use case for this? What kind of API are you trying to bridge into that expects a container of fixed-size arrays of native-endian order bytes?

and some nonsense about hash compatibility (unless T: !Hash or whatever).

There should be no way you can invoke UB solely as a consequence of the fact that you transmuted to a type with a different Hash impl; if you could, then you should also be able to invoke UB in safe code with a rogue Hash impl.

1 Like
39

In graphics libraries I want to be able to take arbitrary struct RGBA, and then safely access its bytes. Vec<[u8; 4]> would do, but ideally I'd like Vec<u8>.

40

If the struct has 4 u8s, that doesn't change alignment and most of the recent discussion doesn't apply. If the struct has a u32, doesn't endianness cause issues?