Skip to content

Support slice DST transmutes (including those requiring metadata fix-up) in transmute_{ref,mut}! #1817

New issue
New issue
Closed
Closed
Support slice DST transmutes (including those requiring metadata fix-up) in transmute_{ref,mut}!#1817
@joshlf

Description

@joshlf
joshlf
opened on Oct 4, 2024

This design is prototyped in #1924. An older, more limited design is prototyped in transmute-slice-experiment.

Currently, transmute_ref! and transmute_mut! only support sized referents, and ensure that the source and destination types are the same size. This enforcement relies on core::mem::transmute, which is special-cased in the compiler (no other language or standard library API provides a compile-time size equality check, except via post-monomorphization error (PME)).

Users often request the ability to transmute dynamically-sized referents – specifically slices and slice DSTs. "Size equality" for slices and slice DSTs is a far more nuanced concept than for sized types. In particular, there are four things we might mean when we say that two slice DSTs "have the same size":

  1. When performing a fat pointer cast, the destination encodes the same referent size as the source; e.g.: 
    let src: &[u8] = &[1, 2, 3, 4];
assert_eq!(src.len(), 4);
assert_eq!(size_of_val(src), 4);

let dst: &[i8] = transmute_ref!(src);
assert_eq!(dst.len(), 4);
assert_eq!(size_of_val(dst), 4);
  2. When performing a fat pointer cast, the destination encodes a referent size no larger than that of the source; e.g.: 
    let src: &[u8] = &[1, 2, 3, 4];
assert_eq!(src.len(), 4);
assert_eq!(size_of_val(src), 4);

let dst: &[()] = transmute_ref!(#![allow(shrink)] src);
assert_eq!(src.len(), 4);
assert_eq!(size_of_val(src), 0);
  3. When performing a fat pointer cast, it is possible to do a "metadata fix-up" operation at runtime such that the destination encodes the same referent size as the source; e.g.: 
    let src: &[u16] = &[1, 2, 3, 4];
assert_eq!(src.len(), 4);
assert_eq!(size_of_val(src), 8);

let dst: &[u8] = transmute_ref!(src);
assert_eq!(dst.len(), 8);
assert_eq!(size_of_val(dst), 8);
  4. When performing a fat pointer cast, it is possible to do a "metadata fix-up" operation at runtime such that the destination encodes a referent size no larger than that of the source; e.g.: 
    let src: &[u8] = &[1, 2, 3, 4, 5];
assert_eq!(src.len(), 5);
assert_eq!(size_of_val(src), 5);

let dst: &[[u8; 2]] = transmute_ref!(#![allow(shrink)] src);
assert_eq!(dst.len(), 2);
assert_eq!(size_of_val(dst), 4);

The "no larger than" cases are referred to as "shrinking" casts, and they are tracked separately in #2701. The designed outlined in this issue only supports size-preserving casts, and is the default behavior. Shrinking casts will require a user opt-in to avoid the footgun of inadvertent data loss.

We can of course view casts which do not require a metadata fix-up as a special case of casts which do require a metadata fix-up, with the caveat that the former will be marginally cheaper at runtime compared to the latter. That said, as we explore below, the fix-up operation itself is very cheap, and so we do not believe that the cognitive complexity of requiring our users to reason about the distinction between these casts is justified by the marginal performance gain. Users who care enough about performance to think about it are of course free to take other measures to ensure that they don't accidentally perform casts which require metadata fix-up.

Progress

Upstream Rust language semantics changes

Externally-tracked designs

PRs

High-level design

In the rest of this issue, we will refer to transmute_ref! for brevity. Everything we say of transmute_ref! applies to transmute_mut! as well.

Currently, transmute_ref! validates:

  • Src: Sized and Dst: Sized have the same size
  • Src has alignment at least as large as Dst

We can view this condition as a special case of a more general condition, which is that Src and Dst have the same size as defined by KnownLayout::LAYOUT.size_info. That condition means, precisely, that either of the following hold:

  • Src: Sized, Dst: Sized, and size_of::<Src>() == size_of::<Dst>() (what we currently support)
  • Src and Dst are slice DSTs with the same TrailingSliceLayout – the same trailing slice offset and the same trailing slice element size

(Note a subtlety here: It would be tempting to say that, in order to avoid a difference in trailing padding, alignment must be equal. However, as we describe below, this is not the case.)

So long as either of these conditions hold, then a &Src to &Dst conversion will preserve referent size (with the exception of trailing padding in the slice DST case – again, see below).

Metadata fix-up

We can, in turn, view this slice DST case as a special case of a more general notion of size equality. In particular, it is sometimes possible to modify the metadata of a fat reference such that the size is preserved even if KnownLayout::LAYOUT.size_info is not the same. Consider, for example, transmuting &[u16] -> &[u8]: if we double the slice length, then the referent size is preserved exactly.

We can even support cases in which the trailing slice offset differs between types. Consider, for example:

#[repr(C)]
struct Src(u32, [u32]);

#[repr(C)]
struct Dst(u16, [u16]);

A &Src with 2 trailing slice elements has size 4 + 2 * 4 = 12. Thus, we can convert a &Src with 2 trailing slice elements to a &Dst with 5 trailing slice elements.

In the general case, the &Src to &Dst transformation is an affine function. The difference between the slice offsets (in this case, the difference between the 4-byte offset of the trailing [u32] in Src and the 2-byte offset of the trailing [u16] in Dst) must be a multiple of the element size of Dst's trailing slice. Regardless of the metadata of Src, there will always be this fixed component (in this case, the 0th element of the trailing [u16] corresponds to bytes 2 and 3 in Src, and this is true even when Src has a trailing slice of length 0). The remainder is a linear transformation from the trailing slice in Src to the trailing slice in Dst. In this particular example, dst_meta = 1 + (src_meta * 2) – the fixed part is 1, and the linear part is * 2.

Detailed design

Bit validity and transmutation

The most straightforward approach to implementing this feature would be to require the appropriate trait bounds on the Src and Dst types and then to write the relevant unsafe code by hand internally. However, as we've seen in e.g. #2226, that's risky and error-prone. It also requires duplicating the same safety reasoning in multiple places (e.g. in transmute_mut! and in various TryFromBytes and FromBytes methods), which increases long-term maintenance burden and increases the likelihood of soundness holes like #2226 slipping through.

Instead, we're going to use this as an opportunity to unify our transmutability analysis around a generic transmutability framework on Ptr (#1359). This issue is blocked on that unification work, and thus concerns itself only with the pointer metadata aspects of slice DST support, but not with the bit validity aspects.

SizeEq trait

Building on generic transmutability means that the pointer metadata fix-up operation has to live in a location which is reachable from the Ptr transmute machinery. Currently, Dst: SizeEq<Src> is a marker trait that denotes that a *Src to *Dst pointer cast will preserve referent size. In order to support metadata fix-up, SizeEq needs to gain the ability to perform that metadata fix-up. Dst: SizeEq<Src> will no longer denote that some other operation has a particular behavior – instead, it will provide a method that provides the metadata fix-up functionality.

PME bound on trait implementation

Here we run into a seeming contradiction between three unavoidable aspects of this design:

  • The code which executes at compile time to compute the size equality predicate (ie, to determine whether a particular &Src to &Dst transmutation is valid from a size perspective) must be written as const code, and failure must be expressed as a const panic, otherwise known as a post-monormphization error (PME).*
  • This code must operate on generic types. The alternative would be for all of the code to be generated by macro_rules! macro, and thus to operate on concrete types, but since the code in question is quite complex, that would make for extremely difficult debugging and horrendous error messages for users.
  • Building atop the generic transmutability machinery requires that SizeEq be implemented for the Src and Dst types.

* Technically, since Rust's type system is turing complete, it would be possible to encode this predicate in the trait system itself. For myriad, hopefully self-evident reasons, we're not taking that approach.

Thus, we need to support code that looks something like:

fn transmute_ref<Src, Dst>(src: &Src) -> &Dst
where
    Src: IntoBytes + Immutable,
    Dst: FromBytes + Immutable,
{ ... }

Note that transmute_ref appears infallible, but it is not: errors are surfaced at compile time via PME. In order to support transmutability, we need Dst: SizeEq<Src>, but we can't actually implement that! We don't actually know that Dst: SizeEq<Src> until we have computed the relevant predicate. But there's no way in Rust – in a generic context – to say "emit this trait impl only if this const code executes without panicking."

In order to work around this limitation, we introduce the following macro:

/// Invokes `$blk` in a context in which `$src<$t>` and `$dst<$u>` implement
/// `SizeEq`.
///
/// This macro emits code which implements `SizeEq`, and ensures that the impl
/// is sound via PME.
///
/// # Safety
///
/// Inside of `$blk`, the caller must only use `$src` and `$dst` as `$src<$t>`
/// and `$dst<$u>`. The caller must not use `$src` or `$dst` to wrap any other
/// types.
macro_rules! unsafe_with_size_eq {
    (<$src:ident<$t:ident>, $dst:ident<$u:ident>> $blk:expr) => { ... };
}

The idea is that $t and $u are the generic Src and Dst types which are parameters on transmute_ref. The PME logic is called inside the macro body, which ensures that it is sound to emit $dst<$u>: SizeEq<$src<$t>>. However, this is done by emitting a generic impl: impl<T, U> SizeEq<$src<T>> for $dst<U>>. Note that this impl is unsound!! It's only guaranteed to be sound for the particular T and U types $t and $u. That's why unsafe_with_size_eq! has a safety precondition requiring the caller to promise to only use $src and $dst with $t and $u.

Backwards-compatibility with const execution

Today, transmute_ref! works in a const context. However, the machinery we're proposing here relies on trait methods, and those can't be called in a const context.

In order to maintain backwards-compatibility, we will use autoref specialization to delegate to one of two implementations. When Src: Sized and Dst: Sized, we will delegate to a const-friendly implementation. When Src: ?Sized or Dst: ?Sized, we will delegate to the new implementation, which does not work in a const context. Since transmute_ref! only currently supports Sized types, this ensures backwards-compatibility.

The PME delayed compilation footgun

Using fallible, const-time machinery presents a tradeoff between expressivity and debugability. Monomorphization — the stage at which const code is actually executed — is part of the codegen phase of the Rust compiler, not its type-checking phase. Consequently, this snippet is accepted by cargo check, but rejected by cargo build with a post-monomorphization error (PME):

    let src: &[u8] = &[1];
    let dst: &[u16] = transmute_ref!(src);

Generic code that produces PMEs is particularly tricky to debug. For example, given:

fn a_generic_function<T, U>(t: &[T]) -> &[U]
where
    T: KnownLayout + Immutable + IntoBytes + FromBytes,
    U: KnownLayout + Immutable + IntoBytes + FromBytes,
{
    transmute_ref!(t)
}

fn main() {
    // a harmless instantiation
    a_generic_function::<u8, i8>(&[0]);

    // a problematic instantiation
    a_generic_function::<u8, u32>(&[0]);
}

...cargo build correctly produces a PME, but the error does not include a backtrace that would help the programmer localize the failure to the problematic instantiation of a_generic_function. While this is a relatively trivial example with only one layer of abstraction, zerocopy's largest customers use it amidst many layers of abstraction.

We limit the consequences of this footgun by limited transmute_ref's use in generic contexts. The macro may only be used in contexts where the types of the source and destination are concrete, which ensures that the customer need only apply local reasoning in that concrete context to diagnose the cause of the PME.

Core algorithm: Metadata fix-up

At runtime, we will be given a src: &Src with a particular metadata (for brevity, we'll denote this s_meta). At compile time, we need to compute two things:

  • Whether, given any src, it's possible to construct a dst: &Dst which addresses the same number of bytes (ie, whether, for any Src pointer metadata, there exists Dst pointer metadata that addresses the same number of bytes)
  • If this is possible, any information necessary to perform the metadata conversion at runtime

Given Src,Dst: KnownLayout<PointerMetadata = usize>, let's define the following short-hands:

  • S_OFF = Src::LAYOUT.size_info.offset
  • S_ELEM = Src::LAYOUT.size_info.elem_size
  • D_OFF = Dst::LAYOUT.size_info.offset
  • D_ELEM = Dst::LAYOUT.size_info.elem_size

We are trying to solve the following equation:

D_OFF + d_meta * D_ELEM = S_OFF + s_meta * S_ELEM

At runtime, we will be attempting to compute d_meta, given s_meta (a runtime value) and all other parameters (which are compile-time values). We can solve:

D_OFF + d_meta * D_ELEM = S_OFF + s_meta * S_ELEM

d_meta * D_ELEM = S_OFF - D_OFF + s_meta * S_ELEM

d_meta = (S_OFF - D_OFF + s_meta * S_ELEM)/D_ELEM

Since d_meta will be a usize, we need the right-hand side to be an integer, and this needs to hold for any value of s_meta (in order for our conversion to be infallible - ie, to not have to reject certain values of s_meta at runtime). This means that:

  • s_meta * S_ELEM must be a multiple of D_ELEM
  • Since this must hold for any value of s_meta, S_ELEM must be a multiple of D_ELEM
  • S_OFF - D_OFF must be a multiple of D_ELEM

Thus, let OFFSET_DELTA_ELEMS = (S_OFF - D_OFF)/D_ELEM and ELEM_MULTIPLE = S_ELEM/D_ELEM. We can rewrite the above expression as:

d_meta = (S_OFF - D_OFF + s_meta * S_ELEM)/D_ELEM

d_meta = OFFSET_DELTA_ELEMS + s_meta * ELEM_MULTIPLE

Thus, we just need to compute OFFSET_DELTA_ELEMS and ELEM_MULTIPLE and confirm that they have integer solutions in order to both a) determine whether infallible Src -> Dst casts are possible and, b) pre-compute the parameters necessary to perform those casts at runtime. Given a particular value for s_meta at runtime, we simply calculate d_meta as shown here.

Alignment mismatch

Slice DSTs can have dynamic padding which appears after the trailing slice field. It is "dynamic" in the sense that its size is a function of the trailing slice length. For example, here's a type which can have zero or two bytes of trailing padding depending on the trailing slice's length:

#[repr(C)]
struct Src(u32, [u16]);

This padding is necessary to ensure that Foo's size is a multiple of its alignment (4, thanks to the u32 field). By contrast, despite having the same field sizes at the same byte offsets, this type never has any trailing padding:

#[repr(C)]
struct Dst([u16; 2], [u16]);

Thus, we might expect that performing a &Src -> &Dst transmute would require that Src have an alignment no larger than that of Dst in order to ensure that the source and destination references agree about how many bytes they refer to.

Luckily, this mismatch is actually not problematic. The worst that can happen is that Src refers to more bytes than Dst, but nonetheless every byte of Src which is contained in a field which correspond to a byte of Dst which is contained in a field (and vice-versa). Importantly, since Src must not have smaller alignment than Dst (this is already a requirement for references regardless of sizedness), the source referent cannot be smaller than the destination referent. This would be problematic, were it possible, since (assuming Rust supports unsized locals in the future) it would allow writing past the end of an allocation (namely, past the end of *src).

Old design

Here is an old design that only supported slices, not arbitrary slice DSTs

For slices, when transmuting [Src] into [Dst], the conditions are identical:

  • The fat pointer cast from [Src] to [Dst] preserves length if Src and Dst have the same size
  • [T] has the same alignment as T

If we could figure out a way to get transmute_ref! to infer Src and Dst when those are the transmuted types and Src and Dst when the transmuted types are [Src] and [Dst], then we could get it to support both sized and slice transmutations.

As a bonus, we could also support size_of::<Src>() being a multiple of size_of::<Dst>(), although this would require runtime code to update the slice metadata.

Design

We could do this by introducing a trait like the following:

trait TransmuteRefHelper {
    type Elem;
}

impl<T: Sized> TransmuteRefHelper for T {
    type Elem = T;
}

impl<T: Sized> TransmuteRefHelper for [T] {
    type Elem = T;
}

We'd need to figure out some way of coaxing the correct inference. Currently we do the following:

zerocopy/src/macros.rs

Lines 214 to 217 in d204727

// `t` is inferred to have type `T` because it's assigned to `e` (of
// type `&T`) as `&t`.
let mut t = loop {};
e = &t;

Instead we need to make this more generic. Naively, we could do:

fn from_elem<T: TransmuteRefHelper>(e: T::Elem) -> &'static T

Then we could modify the code in transmute_ref! something like:

// Infers `t` as either equal to the sized source value or
// the element type of the source slice.
let mut t = loop {}; 
e = from_elem(t);

This works, but it means we can't support const fn on our MSRV, which doesn't permit trait bounds in const fn. If we can figure out another way to accomplish the same inference, then we could avoid breaking const support.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions