DynLinkedList

[conradludgate]

I wanted to have a linked list of Arc<dyn DynTask> for a toy async runtime I am working on. It took a bit of effort but I did eventually manage to define an adaptor that works. I thought I would share it here for lack of any other suitable discussion place.

The basis of this impl is the FatLink, which is a linked list link + a type-erased get_value function that the Adapter impl uses.

pub(crate) struct FatLink<D: ?Sized> {
    link: XorLinkedListAtomicLink,
    get_value: unsafe fn(link: NonNull<FatLink<D>>) -> *const D,
}

Unfortunately, I needed to add this get_link method to the DynTask trait, which requires feature(arbitrary_self_types). I could not figure out a way to avoid the nightly dep here.

    unsafe fn get_link(self: *const Self) -> NonNull<FatLink<dyn DynTask>> {
        <Self as FatLinked<dyn DynTask>>::get_link(self)
    }

https://github.com/conradludgate/arc-discharge/blob/dbd9b0aeb0d1389262a203eeff3bc2e9b0c91a37/src/linked_list.rs

[amari]

Hi @conradludgate,

AFAIK, you need to convert a Arc<dyn DynTask> into a custom fat link via a PointerOps implementation. Links, barring very exotic cases, should always be either plain pointers or value types (e.g. u8 within an arena) and should lack unsized generics.

What's interesting is that typeinfo of the DynTask implementation(s) (ptr, vtable) must be preserved somewhere during insertion, and recovered when removing from a collection. From what I remember, a custom PointerOps can do this, provided your "link" type includes a vtable in addition to an address.

Also, your FatLink should not have an unsized type parameter. It looks like you're "throwing out" the vtable.

I wrote a task library a while back, ran into this same problem, and had to convert dyn types into "fat pointers", then restore them at api boundaries.

Also, all the Link types use regular "thin" pointers: NonNull<Link>, AtomicUsize, etc. So the vtable is getting dropped, which is the real reason the compiler is complaining.