dyn* doesn't need to be special
Tags: rust, programming, design
Published: 2022-04-07 16:05:39


 
 or: more storage API propaganda

A response to [@nikomatsakis](https://twitter.com/nikomatsakis)'s [dyn*: can we make dyn sized?](https://smallcultfollowing.com/babysteps//blog/2022/03/29/dyn-can-we-make-dyn-sized/)

`dyn* Trait` is a way to own a value of `dyn Trait` without knowing how the pointee is stored. In short, `dyn* Trait` acts as "`&move dyn Trait`", owning the pointee and dropping it, while also containing a clever feature I'm calling "owning vtables" allowing it to also transparently own the memory the pointee is stored in.

When you have a normal `Box<dyn Trait>`, the pointer itself looks something like

```rust
struct Box<dyn Trait> {
    data: ptr::NonNull<{unknown}>,
    vtable: &'static TraitVtable<{unknown}>,
}
```

and the vtable something like

```rust
struct TraitVtable<T: Trait> {
    layout: Layout = Layout::new::<T>();
    drop_in_place: unsafe fn(*mut T)
        = ptr::drop_in_place::<T>;
    // ... the contents of Trait
}
```

so that `dyn Trait` can recover the type information needed to interact with the pointee. The trick of `dyn*` is in using an owning vtable, best explained with a simple example:

- `Box<T as dyn Trait>`'s vtable's `drop_in_place` is `ptr::drop_in_place::<T>`
- `Box<T as dyn Trait> as dyn* Trait`'s vtable's `drop_in_place` is `Box::drop`

In this manner, any smart pointer with an `into_raw(self) -> *mut T` can be owned transparently as `dyn* Trait` by generating a new vtable which replaces `drop_in_place` with a shim that `from_raw`s the smart pointer and then drops it[^dyn*-drop].

[^dyn*-drop]: You can do clever things to avoid the `from_raw` shim, like with `Box`, where you can just call `Box::drop` directly, by patching up the other vtable members to take into account the container the smart pointer puts it in. However, since you use the `dyn*` many times and only drop it once, it seems better to just shim `drop_in_place`.

With more complicated vtable shims, you can even shove any pointer-sized value into a `dyn*`, by dealing it a data "pointer" of `ptr::invalid(value)` and the vtable shimming back to the original trait implementation on `value` directly.

-----

And now, we need to talk about the [storages API proposal](https://github.com/matthieu-m/storage-poc) for a bit.

> ![Cool Bear Says](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u6izja91mzp1qo6krqwz.png) But what does this have to with `dyn*`?

We'll get there! ... Hey, does [Amos](https://fasterthanli.me/) know you're here?

> ![Cool Bear Says](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u6izja91mzp1qo6krqwz.png) Actually, [yes](https://twitter.com/fasterthanlime/status/1512075785196081161?s=20&t=ZQ_QUBFQ6GlPv10Vu6WVyw).

... Anyway, on the current nightly, `Box` and other allocating types are generic over [`trait Allocator`](https://doc.rust-lang.org/nightly/std/alloc/trait.Allocator.html). `Allocator` is a fairly standard abstraction over heap allocation, providing methods `fn allocate(&self, Layout) -> Result<ptr::NonNull<[u8]>, AllocError>` and `fn deallocate(&self, ptr::NonNull<u8>, Layout)`.

The storages API adds another layer on top of this, dealing in a generic `Self::Handle<T>` type instead of `ptr::NonNull<T>` directly. In short[^safety]:

[^safety]: For brevity, I omit a lot of details included in the full proposal. Notably, I omit a lot of safety concerns that are put on the user, and the full proposal has static controls for whether a storage can only create a single handle at a time or manages multiple handles, whether a handle is to a single element or to a slice of elements, as well as whether you need exclusive access to the storage to get mutable access to the pointee.

```rust
trait Storage {
    type Handle<T: ?Sized>: Copy;
    type Error;
    fn create(&mut self, meta: <T as Pointee>::Metadata) -> Result<Self::Handle<T>, Self::Error>;
    fn destroy(&mut self, Self::Handle<T>);
    // 👇
    fn resolve(&self, Self::Handle<T>) -> ptr::NonNull<T>;
}
```

To illustrate the benefit, consider a potential implementation:

```rust
struct InlineStorage<const LAYOUT: Layout> {
    data: UnsafeCell<MaybeUninit<[u8; LAYOUT.size()]>>,
    align: PhantomAlignTo<LAYOUT.align()>,
}

impl<const LAYOUT: Layout> Storage for InlineStorage<LAYOUT> {
    type Handle<T: ?Sized> = <T as Pointee>::Metadata;
    type Error = !;
    fn create(&mut self, meta: Self::Handle<T>) -> Result<Self::Handle<T>, !> { meta }
    fn destroy(&mut self, _: Self::Handle<T>) {}
    // 👇
    fn resolve(&self, meta: Self::Handle<T>) -> ptr::NonNull<T> {
        ptr::NonNull::from_raw_parts((self as *const _).cast(), meta)
    }
}
```

Now, you can have `Box<T, InlineStorage<Layout::new::<T>()>>` be layout-equivalent to storing `T` directly on the stack.

> ![Cool Bear Says](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u6izja91mzp1qo6krqwz.png) Amazing.

More importantly, though, is that you can have `Box<dyn Trait, InlineStorage<Layout::new::<T>()>>` *also* be layout-equivalent to storing `T` directly on the stack (plus a vtable pointer), but type-erased so you don't actually know about `T` anymore.

> ![Cool Bear Says](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u6izja91mzp1qo6krqwz.png) Oh, I think I see where you're going with this!

So, if we add a fallback to heap allocation ...

```rust
struct SmallStorage<const LAYOUT: Layout, A: Allocator = Global> {
    inline: InlineStorage<LAYOUT>,
    outline: AllocStorage<A>,
}

impl<const LAYOUT: Layout, A: Allocator> for SmallStorage<LAYOUT, A> {
    type Handle<T: ?Sized> = ptr::NonNull<T>;
    type Error = AllocError;

    fn create(&mut self, meta: <T as Pointee>::Metadata) -> Result<Self::Handle<T>, AllocError> {
        let layout = Layout::for_metadata(meta)?;
        if layout.fits_in(LAYOUT) {
            self.inline.create(meta)
        } else {
            let meta = self.outline.create(meta)?;
            Ok(NonNull::from_raw_parts(layout.dangling(), meta))
        }
    }

    fn destroy(&mut self, handle: Self::Handle<T>) {
        let meta = handle.metadata();
        let layout = Layout::for_metadata(meta)?;
        if layout.fits_in(LAYOUT) {
            self.inline.destroy(meta)
        } else {
            self.outline.destroy(handle)
        }
    }

    fn resolve(&self, handle: Self::Handle<T>) -> ptr::NonNull<T> {
        let meta = handle.metadata();
        let layout = Layout::for_metadata(meta)?;
        if layout.fits_in(LAYOUT) {
            self.inline.resolve(meta)
        } else {
            self.outline.resolve(handle)
        }
    }
}
```

... and maybe a type alias for convenience ...

```rust
type Dyn<T: ?Sized> = Box<T, SmallStorage<Layout::new::<usize>()>>;
```

We have the functionality of `dyn*` as a library type! Instead of `dyn* Trait`, we have `Dyn<dyn Trait>` (the stutter is unfortunate[^dyn-stutter]). This is our type that is

[^dyn-stutter]: In the olden days (before Rust 2018), we didn't have `dyn Trait`, it was just `&Trait`. `dyn Trait` is better, because you can immediately know that you're dealing with a `dyn` type rather than a fixed type. However, in this *one* specific case, omitting the `dyn` *would* allow us to write `Dyn<Trait>` instead, so it's impossible to say if it's good or not,,

- The size of `Box<dyn Trait>`,
- Stores small values of `dyn Trait` inline, and
- Owns the storage of `dyn Trait`, dellocating it on drop.

> ![Cool Bear Says](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u6izja91mzp1qo6krqwz.png) But wait, you're still missing something.

What, Cool Bear?

> ![Cool Bear Says](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u6izja91mzp1qo6krqwz.png) `dyn*` can hold *any* smart pointer, not just `Box`. You said so yourself!

Well, but there's a catch: `dyn*` needs to be `DerefMut` if it wants to fulfil its life goal of facilitating `Pin<dyn* Future>` usage. This means that it's restricted to single-ownership smart pointers wait hey that sounds like `Box`.

It's my belief that there aren't really any `Pin<P<dyn Future>>` types out there for a `P` that's not `&mut` or `Box`. I don't have any proof, just a feeling.

But the storages `Dyn` can be extended to support other `DerefMut` smart pointers, though it *might* require a second vtable pointer without the language support for easily wrapping the vtable into an owning vtable[^&mut].

[^&mut]: Then remaining concern is actually unowning references like `&mut dyn Trait`. The important thing to note here is that `Box<Type, Storage>` gives us two axis of customization: I've talked here about `Storage` for customization of the owning memory, but `Type` still gives us customization over how its used. For `fn(&mut dyn Trait) -> Dyn<dyn Trait>`, you can wrap the vtable to remove any drop glue with e.g. `ManuallyDrop<dyn Trait>`. This is where language support would be useful.

So, storages get us the benefit of `dyn*` without any of the main problems with `dyn*`. I think that more than justifies bringing the storages API to std so we can properly spin the wheels on this design and find where it falls short. There's definitely flaws in the storages proposal I haven't spotted yet[^storage-flaws], but we need to use it to find the rest of them.

Oh, and `&move` also falls out of storages as `Box<T, &mut MaybeUninit<T>>`, so that's even more proposed language features handled by the library feature. The storage API is good.

[^storage-flaws]: In fact, I [spotted one while drafting this post](https://github.com/matthieu-m/storage-poc/issues/3); as currently prototyped, storages are unsound, because the only handle resolution option is by-shared-ref and inline storages aren't using `UnsafeCell`, thus ultimately violating the aliasing guarantees 💣💥😱