Is custom allocators the right abstraction?

Since none of the RFC (such as 2984) have been implemented yet, I created a simple set of traits to just get the meta data out and back: Rust Playground.

For experimentation it should be good enough, since it doesn't require any modification to the compiler.

I'll take the opportunity to explain the -- perhaps odd -- choice of working entirely in terms of pointers, and therefore implementing the conversion between *const T and (meta, *const u8).

In Rust, &T and &mut T have specific guarantees with regard to (1) aliasing and (2) liveness of the pointee. By not materializing a reference, we circumvent the 2 issues: in the absence of reference, reference rules do not apply!

As a bonus we are allowing pointer manipulations to be safe, as usual, with the caveat that it may not be safe to dereference the pointer later, as usual.

The code, which will not win any beauty contest:

#![feature(raw)]
#![feature(specialization)]

#![allow(incomplete_features)]

pub mod meta {

use std::{marker::PhantomData, mem, raw::TraitObject};

//
//  SizedMeta
//
pub struct SizedMeta<T>(PhantomData<fn(T) -> T>);

impl<T> Clone for SizedMeta<T> {
    fn clone(&self) -> Self { *self }
}

impl<T> Copy for SizedMeta<T> {}

//
//  UnsizedMeta
//
//  Ideally we'd want a separate item for slices vs traits. Fortunately at the
//  moment they both only require one usize worth of data...
//
pub struct UnsizedMeta<T: ?Sized>(usize, PhantomData<fn(T) -> T>);

impl<T: ?Sized> Clone for UnsizedMeta<T> {
    fn clone(&self) -> Self { *self }
}

impl<T: ?Sized> Copy for UnsizedMeta<T> {}

//
//  MetaData
//
pub trait MetaData<T: ?Sized>: Sized {
    fn assemble(&self, data: *const u8) -> *const T;
    fn disassemble(ptr: *const T) -> (Self, *const u8);
}

//  The trait specialization -- because a slice specialization exists and people
//  really shouldn't use that for sized T.
impl<T: ?Sized> MetaData<T> for UnsizedMeta<T> {
    default fn assemble(&self, data: *const u8) -> *const T {
        assert!(mem::size_of::<*const T>() == mem::size_of::<TraitObject>());

        let object = TraitObject { data: data as *mut (), vtable: self.0 as *mut () };

        unsafe { mem::transmute_copy(&object) }
    }

    default fn disassemble(ptr: *const T) -> (Self, *const u8) {
        assert!(mem::size_of::<*const T>() == mem::size_of::<(usize, usize)>());

        let object: TraitObject = unsafe { mem::transmute_copy(&ptr) };

        (UnsizedMeta(object.vtable as usize, PhantomData), object.data as *const u8)
    }
}

//  The slice specialization. It is dodgy, avoiding the use of from_raw_parts to
//  avoid materializing a reference in case the pointer is dangling.
impl<T> MetaData<[T]> for UnsizedMeta<[T]> {
    fn assemble(&self, data: *const u8) -> *const [T] {
        debug_assert!(mem::size_of::<*const [T]>() == mem::size_of::<(usize, usize)>());

        unsafe { mem::transmute_copy(&(data, self.0)) }
    }

    fn disassemble(ptr: *const [T]) -> (Self, *const u8) {
        debug_assert!(mem::size_of::<*const [T]>() == mem::size_of::<(usize, usize)>());

        let (data, len): (usize, usize) = unsafe { mem::transmute_copy(&ptr) };

        (UnsizedMeta(len, PhantomData), data as *const u8)
    }
}

impl<T> MetaData<T> for SizedMeta<T> {
    fn assemble(&self, data: *const u8) -> *const T {
        data as *const T
    }

    fn disassemble(ptr: *const T) -> (Self, *const u8) {
        (SizedMeta(PhantomData), ptr as *const u8)
    }
}

//
//  MetaPointee
//
pub trait MetaPointee {
    type Meta: MetaData<Self> + Clone + Copy;

    fn assemble(meta: Self::Meta, data: *const u8) -> *const Self;
    fn disassemble(ptr: *const Self) -> (Self::Meta, *const u8);
}

impl<T: ?Sized> MetaPointee for T {
    default type Meta = UnsizedMeta<T>;

    default fn assemble(meta: Self::Meta, data: *const u8) -> *const Self {
        meta.assemble(data)
    }

    default fn disassemble(ptr: *const Self) -> (Self::Meta, *const u8) {
        <Self::Meta as MetaData<Self>>::disassemble(ptr)
    }
}

impl<T> MetaPointee for T {
    type Meta = SizedMeta<T>;
}

} // mod meta

use std::fmt::Debug;
use meta::MetaPointee;

fn main() {
    let array = [1; 7];
    let slice: &[i32] = &array[..];
    let slice_pointer: *const [i32] = slice as *const _;
    let trait_pointer: *const dyn Debug = &array as &dyn Debug as *const _;

    let (slice_meta, slice_data) = MetaPointee::disassemble(slice_pointer);
    println!("{:?} / {:?}", slice_data, slice.as_ptr() as *const u8);

    let (trait_meta, trait_data) = MetaPointee::disassemble(trait_pointer);
    println!("{:?} / {:?}", trait_data, slice.as_ptr() as *const u8);

    let reassembled_slice_pointer: *const [i32] =
        MetaPointee::assemble(slice_meta, slice_data);
    println!("{:?}", unsafe { &*reassembled_slice_pointer });

    let reassembled_trait_pointer: *const dyn Debug =
        MetaPointee::assemble(trait_meta, trait_data);
    println!("{:?}", unsafe { &*reassembled_trait_pointer });
}

This prints:

0x7ffcf955ee04 / 0x7ffcf955ee04
0x7ffcf955ee04 / 0x7ffcf955ee04
[1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1]
2 Likes

@TimDiekmann I published a crate roughly following (and extending) the freshly accepted RFC 2580: https://crates.io/crates/rfc2580 .

It's not so different from my earlier playground link, but I refined and documented the API, stuck closer to the names from RFC 2580, and most importantly a crate makes it easy to reuse and collaborate.

I'm still thinking about the best API for storage traits. I'm a bit stuck with the lack of GAT for expressing a StorageBuilder trait that could be passed to LinkedList<T> or BTreeMap<K, V> so they wouldn't have to publicly expose their internal node types.

1 Like

Out of curiosity, how would it look like?

So the problem that I face with LinkedList<T> and other node-based containers, is that the allocation requests are not going to be for T, they're going to be for Node<T>: an internal type which adorns the element(s) with some extra information, such as pointers.

This internal type is, well, internal. And for a good reason (encapsulation) should not be exposed.

So essentially we'd like something like:

struct LinkedList<T, S: StorageBuilder> {
     head: Option<NonNull<Node<T>>>,
     tail: Option<NonNull<Node<T>>>,
     storage: S::Storage<Node<T>>,
}

And the StorageBuilder builder would have a type Storage<U>: <requirements>, eg. GAT.

In the absence of GAT, I am not sure how to express the type of storage.

(The same problem plagues BTreeMap/BTreeSet, which are also node-based)


The allocators don't care, they only use raw-memory. The thing, though, is that there is an advantage to a typed storage: what is available at compile-time need not be present at run-time. In this case, for example, the storage is homogeneous: all allocation/deallocation requests are always for the same size.

Homogeneity is a nice property, it means a simple implementation of the above is essentially:

struct ListStorage<T, const N: usize> {
    next: u32,
    storage: [ListStorageBlock<T>; N],
}

union ListStorageBlock<T> {
    index: u32,
    element: MaybeUninit<T>,
}

Heterogeneous requests, on the other hand, are more onerous to implement.

Isn't this a "type constructor"?
ADT not GADT?

This is a Generic Associated Type, or GAT for short.

It's a type constructor (hence Generic Type) nested (hence Associated) inside a trait definition.

1 Like

Along these lines, I want to bring up a really cool (ab)use of the allocator API someone came up with: [RFC] Add allocators for zero-copy conversion from Box<T> into Rc<T> by mahkoh · Pull Request #80273 · rust-lang/rust · GitHub

Basically, it's an allocator wrapper that when requested an allocation for T, actually returns an allocation for RcInner<T>, offset to the position of the T. This then allows zero-copy turning a Box<T, ThisAllocator<A>> into Rc<T, A>.

This is sort of the other direction, and I think still works fine with the Storage design, but is worth mentioning as related.

And yes, it looks like typed Storage basically requires GAT in order to be able to ask for a Storage capable of allocating an undisclosed internal type.

1 Like

@TimDiekmann

I have been experimenting about storages in storage-poc.

On the bright side:

  • I have managed to condense the API to 3 traits:
    • SingleElementStorage: for Box.
    • MultiElementStorage: for LinkedList, BTreeSet/Map, ...
    • SingleRangeStorage: for Vec, VecDeque, ...
  • By restricting the usecases, the traits are all strongly typed, and much more high-level than the Allocator API.
  • Bridging to the Allocator API remains easy.

I'm notably very happy that SingleRangeStorage means that I can implement a InlineVec<u8, 31>, that is a Vec with 31 u8 elements stored inline in only 32 bytes -- the one more byte coming from the necessity to maintain the current length, of course.

On the slightly less bright side:

  • This relies on Generic Associated Types.
    • Though the good news is that the code does compile, and pass its tests, on nightly -- with the notable exception of S::Handle<T> : CoerceUnsized<S::Handle<U>>, which crashes the compiler.
  • RFC 2580 is not quite sufficient for Box<T, inline::SingleElement<T>> to be CoerceUnsized:
    • It needs to strongly type all <T as Pointee>::Metadata.
    • And then the compiler needs to make them CoerceUnsized.
    • I've left a comment on the RFC about it; though since it's accepted I'm not sure if that's the appropriate way to communicate the issue.

I don't see RFC 2580 as being a blocker -- it prevents implementing inline storages efficiently, but since there's no such thing in core/std, it can always be added later.

So the only big issue is the GAT crash with CoerceUnsized; there's 2 FIXME in the tests of raw_box.rs around that.


I'm not sure if a MultiRangeStorage is necessary; at least in std. Maybe HashMap for future-proofing?

13 Likes

MultiRangeStorage I thought this might be nice for BTreeSet/BTreeMap, but I might be misunderstanding how that datastructure works.

On the bright side:

This looks very promising! I like the kind of traits as they abstract very well and, as far as I can see, cover the needed operations. However, names like acquire and release might be confusing because of atomic ordering, but we can bikeshed about the naming later.

This relies on Generic Associated Types.

it is just a matter of time until GATs can be used on stable, this shouldn't be a blocker in any case. I prefer designing better APIs with not-yet-stable features than relying on the current stable with a worse API.

I had problems with CoerceUnsized occured before, but I never had an ICE. I'm sure this can be fixed ... somehow. This is that kind of compiler magic I don't understand.

Instead of calling it SingleRangeStorage I suggest ContiguousStorage. Instead of calling MultiElementStorage, maybe DiscontiguousStorage.

4 Likes

I'm not even interested in discussing naming right now; that's bikeshed for the RFC phase.

1 Like

Element vs Range is essentially whether the storage allocates a T (single element) or a [MaybeUninit<T>] (contiguous range of elements).

In BTreeSet and BTreeMap, the storage just needs to allocate one Node at a time, and that doesn't require ranges -- even if said nodes contains 4 or 6 pointers.

One the other hand, a JaggedVec could be something like:

struct JaggedVec<T> {
    length: usize,
    capacity: usize,
    elements: [NonNull< [ MaybeUninit<T> ] >; 32],
                        ^                ^
}

In which case it asks the storage for a range of values each time.

And bluss' CompactHashMap is implemented as:

struct CompactHashMap<K, V> {
    lookup: HashMap<K, usize>,
    values: Vec<(K, V)>,
}

So that even if HashMap and Vec only allocate a single (contiguous) range each, the CompactHashMap itself needs to allocate 2 different ranges -- although is also poses additional difficulties wrt. sharing the storage between 2 collections, but self-referential is a rabbit hole I'd rather not go down into here.

1 Like

After a week-end of work storage-poc now contains generic implementations of:

  • alternative storage, which uses either the first or the second storage, one at a time.
  • fallback storage, which uses either the first or the second storage, both at the same time.

I took the opportunity the clean-up the implementation of the small storage, it's now defined as an alternative of inline and allocator storage, or in the code:

type Inner<S, A> =
    alternative::SingleElement<
        inline::SingleElement<S>,
        allocator::SingleElement<A>,
        DefaultBuilder,
        AllocatorBuilder<A>
    >;

I think the crate is in a pretty good shape, and therefore that it's a good time to summarize where it stands, which I am going to do here:

Usecases unlocked

This crates demonstrates that a number of usecases are unlocked by the usage of Storages, rather than the currently proposed Allocator API.

There are essentially 2 features of the crate that unlock usecases:

  1. Inline storage.
  2. Custom handles.

Inline Storage unlocks:

  • Inline collections:
    • InlineString<63> (InlineVec<u8, 63>): a String of up to 63 bytes, entirely stored inlined in 64 bytes. Guaranteed never to allocate, good cache locality.
    • InlineBox<T, [usize; 4]>: a Sized type for !Sized types. Allows passing dyn Fn(...), or dyn Future<...> around without allocation, without waiting for unsized_locals.
  • Small collections, such as SmallString<N>.
  • const collections: since InlineVec is non-allocating, it should be feasible to store it in a const item, and extending, there's no reason an InlineHashMap couldn't be stored in a const item either.

Allocators cannot allow inline storage, as then when the collection moves the pointer its stores to its elements is now dangling. Storages can, as demonstrated, by relying on custom handles.

Custom Handles, themselves, unlock at least one usecase:

  • Using Box, Vec, ... in shared memory. Storing pointers in shared memory is only possible if the shared memory is mapped at the same address in every process, which is a big constraint. Using a SharedMemoryStorage which resolves the custom handle to a pointer relative to its own address, however, this problem is solved.

Remaining Work

Unstable Features

The crate requires a few unstable language features:

  • specialization is inherited: as it uses rfc2580 for meta-data.
  • coerce_unsized and unsize: to manipulate unsized elements.
  • untagged_unions: for alternative's handles, maybe?
  • And the biggest: generic_associated_types which is critical to the whole type Handle<T> = ...; allowing collections not to expose their internal nodes.

It is intended to be part of standard library, however some features will be necessary for any user to implement the traits themselves:

  • generic_associated_types is always necessary.
  • coerce_unsized and unsize are necessary for the ElementStorage family of traits -- see below.

CoerceUnsized for Box

The RawBox implementation of the crate does not manage to implement CoerceUnsized. As a work-around, the ElementStorage requires implementing a coerce function to coerce a Handle<T> into a Handle<U>.

If the Handle<T> = NonNull<T>, then this is not a problem. The problem occurs when attempting to define a custom handle embedding the pointer meta-data instead of the pointer itself.

I've left a comment on the tracking issue of RFC2580; I believe the best solution would be for <T as Pointee>::Metadata to be coercible to <U as Pointee>::Metadata if T: Unsize<U>. Since the intent is for the Metadata types to be strongly tied to the compiler, I would expect it is technically feasible.

To move forward or not to move forward?

storage-poc was always intended as Proof Of Concept to:

  1. Demonstrate the technical feasibility.
  2. Showcase collections for each usecase.
  3. Sketch out a potential API.

It has met its goals. It's pretty clearly demonstrated the feasibility, the collections are there for anyone to see, and the resulting API is pretty lean1 yet enabling all of that -- though I hold no illusion that it's perfect.

1 The first drafts were much more crowded, I even wondered if each collection would end-up requiring a specialized trait. By contrast, the current API has essentially 4 traits, in a matrix: [Multi|Single][Element|Range]Storage, and each trait has only a handful of functions, with no duplication in sight.

Now is a good time, then, to take a step back and evaluate whether to move forward or not.

I love this quote, from Antoine the Saint Exupéry:

Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away

I believe that the usecases unlocked by the use of Storages over Allocators are compelling enough, but then since they solve problems that I have, I am more than a little biased.

On the one hand, there are strong benefits:

  1. Obsoletes many crates, among which coca, by allowing Box, BTreeMap, Vec, etc... in non-allocating contexts.
  2. Offers an alternative solution to unsized_locals and co: you could pass RawBox<dyn Future, [usize; 4]> as function parameter, or return it; you could implement a non-allocating task-queue as containing RawBox<FnOnce(), [usize; 4]>.
  3. Potentially offers a way to store BTreeMap, or HashMap as const items.

On the other hand, there are clear costs:

  1. Impact on RFC2580: I expect that it requires Metadata to be coercible, which first requires them to be strongly typed.
  2. Impact on Collections: the collections code can be made core, but in exchange it has to be fully overhauled to use handles rather than pointers, and to convert handles to pointers any time it actually needs the pointer.
  3. Impact on Compile-Times: mostly likely, the additional layer of generics will lead to a degradation of compile-times.

Also, it is important to remember that as long as RFC2580 implements coercible metadata, a userspace crate could fork all the std collections to rebase them on storages, and only the people who care would pay the cost. I find it distasteful (duplication), but pragmatically it could work rather well.

So, do we think that a sufficient number of users, and usecases, would benefit from the usage of storages to justify going forward, or not?

@TimDiekmann @RustyYato @CAD97

20 Likes

It's another nightly feature to wait on, but -Zshare-generics (or similar) should be able to mitigate some of the cost of more complicated Storage traits, by effectively providing MIR for e.g. Vec<T, AllocatorStorage<Global>>.

I'd also like to see a comparison between the compilation cost of Allocator versus Storage; I'm not completely convinced that they'd be significantly different.

Given that custom allocators are nightly only, have been for a good while, and there's been no real "coming soon" pressure on custom allocators (global alloc is "good enough" to unlock initial use cases), I think the benefit of getting it "right" with Storage outweighs the cost of waiting.

This is something we can do better than everyone else, so we should do our best to try to do so. We already have mandatory size on dealloc; we can push further for Storage.

There's also a thin tightrope we could potentially walk to stabilize Allocator without Storage. Basically, stabilize AllocatorStorage, but the only stable use is to pass it along to Vec or another collection that requires the unstable Storage trait. If it's later decided to yeet Storage, AllocatorStorage becomes a deprecated item that's just a noöp Allocator wrapper.

10 Likes

This is a great summary of your findings so far. All applicable portions are more or less in line (pun not intended) with what I found when implementing generic-vec. I think RawBox is sufficient motivation for Storage over Allocator, because there is no way to get non-allocating trait objects without it. The fact that smallbox uses a similar approach seems to back this up (specialized for Box).

I think @CAD97 already pointed this out. This is no different from adding an allocator type parameter. So there isn't any difference over the alternative.

I think it would be best to separate SingleRangeStorage and MultiRangeStorage because with SingleRangeStorage, the Storage could deallocate the memory when it drops, making RangeStorage::release unnecessary. It would also simplify the Drop code for data structures like storage_poc's RawVec<_> and make them panic-safe for free. This might also be applicable to *Storage in general, but I'm unsure about that (If it is generally applicable, then RangeStorage could stay).

This is... surprisingly reasonable, though a little roundabout. This applies equivalently to SingleElementStorage, and is easier to explain, so I'm going to walk through with that.

Originally I though this would be unreasonable to support, as SingleElementAllocatorStorage<Alloc> obviously would have a Handle of ptr::NonNull<T>, so that Box<T, SEAS<A>> would decay back to just being { ptr: NonNull<T>, alloc: SEAS(A) }, which is basically just the current allocator-generic box. However, the storage itself could store the pointer, and provide a Handle of (), so Box<T, SEAS<S>> would be { handle: (), storage: NonNull<T> }.

Basically, SingleElementStorage acts like Box<T>, and MultiElementStorage acts like Box<[T]> (except maybe uninit (maybe), so RawBox).


HOWEVER, I don't think this is the correct way to handle (no pun intended) it. The Storage traits should solely care about acquiring/releasing memory when asked. Let (Raw)Box<T, S>/Box<[T], S> be those types that do the dealloc on drop. This simplifies the Storages' job immensely, and reduces the cost of providing/implementing Storage. Additionally, if SingleStorage isn't in charge of releasing handles and assumes the user does, this allows MultiStorage to be a simple marker trait extension of SingleStorage that lifts the "only one live handle" restriction.

Specifically, (assuming there are no further impl restrictions, and I think this is just a slight reorganization of the existing POC traits), I think the right API is something along the lines of (modulo naming bikeshed)

// NB: Blank lines removed for compactness, also I just use usize for simplicity

/// A storage capable of storing single elements.
unsafe trait Storage {
    /// The handle used to access stored elements.
    type Handle<T: ?Sized + Pointee>: Copy;
    /// Acquire a handle managed by this storage.
    /// # Safety
    /// Only one handle may be live unless this type is `MultiStorage`.
    unsafe fn acquire<T: ?Sized + Pointee>(&mut self, meta: T::Metadata) -> Result<Self::Handle<T>, Error>;
    /// Release a handle managed by this storage.
    /// # Safety
    /// This is an unreleased handle acquired from this storage.
    /// Invalidates the handle.
    unsafe fn release<T: ?Sized + Pointee>(&mut self, handle: Self::Handle<T>);
    /// Resolve a handle managed by this storage.
    /// # Safety
    /// This is an unreleased handle acquired from this storage. The pointer is only valid
    /// until the storage is moved or `acquire`/`release` is called (for any handle).
    unsafe fn resolve<T: ?Sized + Pointee>(&self, handle: Self::Handle<T>) -> ptr::NonNull<T>;
    // helpers and coerce things
}

/// This storage supports multiple live handles.
unsafe trait MultiStorage: Storage {}

/// A storage capable of storing contiguous ranges of elements.
unsafe trait RangeStorage {
    /// The handle used to access stored elements.
    /// Knows the provided capacity.
    type Handle<T>: Copy;
    /// Acquire a handle managed by this storage, capable of holding at least `capacity` elements.
    /// # Safety
    /// Only one handle may be live unless this type is `MultiRangeStorage`.
    unsafe fn acquire<T>(&mut self, capacity: usize) -> Result<Self::Handle<T>, Error>;
    /// Release a handle managed by this storage.
    /// # Safety
    /// This is an unreleased handle acquired from this storage.
    /// Invalidates the handle.
    unsafe fn release<T>(&mut self, handle: Self::Handle<T>);
    /// Resolve a handle managed by this storage.
    /// # Safety
    /// This is an unreleased handle acquired from this storage. The pointer is only valid
    /// until the storage is moved or `acquire`/`release` is called (for any handle).
    unsafe fn resolve<T>(&self, handle: Self::Handle) -> ptr::NonNull<[T]>;
    /// helpers, try_grow, try_shrink, max capacity
}

/// This storage supports multiple live handles.
unsafe trait MultiRangeStorage: MultiStorage {}

(Traits need to be unsafe. Otherwise a valid impl is no-op acquire/release and ptr::null for resolve.)

I'm unsure about providing the Ts upfront to be honest, and could go either way. (The current POC requires the T upfront, my sketch just requires the pointer metadata.) Not requiring the T is probably better, as you maintain the ability to emplace dynamically sized types (for arbitrary storage). [std::alloc example]

fn resolve_mut(&mut self, handle: Self::Handle<T>) is probably required (under current stacked borrows rules), to give mutable provenance to the returned pointer even for inline storages. Either that, or any inline storage that wants to be mutable must use UnsafeCell on its internals. Everywhere I marked to invalidate pointers is being conservative around SB; I'm not sure if conservative enough tbh. Ultimately, I'm not super confident how inline storages, pointer provenance, and stacked borrows interact, and would need to do further study to gain confidence. RustBelt proved our allocation primitives sound (with std::alloc); we definitely don't want to accidentally lose that without a very clear way to gain it back.

One thing I'd be curious to know is if it's possible to collapse RangeStorage of T into just being a Storage of [T]. I'm not sure; this would require more design experimentation to see if it puts undue restrictions on storages to support both single and range allocation simultaneously (rather than, say, providing an impl of RangeStorage based on {Storage of [T]}). IIUC, RangeStorage handles are currently required to remember the capacity they provide (acquire returns ptr::NonNull<[T]>; I took this directly from the POC), rather than passing that responsibility on to the user (which would be a clear reason to split the traits; acquire would just return ptr::NonNull<T>).

Maybe it would look as simple as something like...

/// A storage that can more efficiently manage contiguous ranges of elements.
unsafe trait RangeStorage: Storage {
    /// Attempt to grow the handle to cover at least `capacity` elements.
    /// # Safety
    /// Requested capacity is >= current capacity.
    /// Invalidates resolved handle pointers.
    /// Invalidates the input handle only on success.
    unsafe fn try_grow<T>(&mut self, handle: Self::Handle<[T]>, capacity: usize) -> Result<Self::Handle<[T]>, Error>;
    /// Shrink the handle to cover at least `capacity` elements.
    /// # Safety
    /// Requested capacity is <= current capacity.
    /// Invalidates resolved handle pointers and the input handle.
    /// Output handle may have any capacity between requested and prior capacity.
    unsafe fn shrink<T>(&mut self, handle: Self::Handle<[T]>, capacity: usize) -> Self::Handle<[T]>;
}

This extension-style RangeStorage sketch makes me think that an independent RangeStorage that resolves to ptr::NonNull<T> and requires (lets) the user remember the capacity of each handle separately is probably better. (E.g. [MaybeUninit<T>; N] would just use Handle = () and resolve() => self.arr.as_mut_ptr().

Now I should probably stop discussing this in depth, since IP ownership of stuff I do is murky at best right now. (I will go to SMU legal and get an exception for OSS if I need to but... confrontation,, and the Guildhall people seem to think the agreement doesn't apply to non-coursework anyway,,)

Ok, I haven't got time today to read that in depth, but I should have mentioned why I said this. Currently this is how Vec is implemented. Vec has a "Storage" RawVec that represents the allocation. Vec is a minimal wrapper that keeps track of how many elements are initialized. Dropping RawVec deallocates the allocation.

The Storage already hands out the Handle and provides a release mechanism, why should it matter (for the Single* variants) it the release is done in drop or elsewhere? (There doesn't need to be a handle at all for Single* Storage)

TL;DR of the last post: doing so is basically making the single storage into a trait version of RawBox (for SingleElementStorage) / RawVec (for SingleRangeStorage). While this is a possible design path, I think it more would useful to have the Storage traits be manually managed, make the Multi versions just an extra capability for the Storages (having multiple concurrently live handles), and let RawBox/RawVec be the RAII-ifiers wrapping the raw Storage.

In other words, I think keeping the difference between Single/Multi versions small (to the point of it being the same acquire implementation) is more useful for the abstraction layer than the automatic of memory without another wrapping type that adds that on top.

Plus, this way the RAII is implemented once[1] for all Storages, whereas if you bake it into the storage trait contract, then all Storages have to implement the cleanup-in-Drop logic. Minor, but meaningful.

(There might be extra caveats around Box, though, due to its current use of Unique rather than NonNull and extra magic properties...)

2 Likes

@CAD97 After reading through this new proposal, I think it does outline a better way to model these traits. Especially once the new RangeStorage is factored in.

Ok, I can see that. Maybe along side these traits it would be possible to provide a RAII guard that cleans up on Drop for ease of use (Maybe limited to Handle<()> = () or something similar).

@matthieum what do you think about the revised proposal.