Allocator: split deallocation into its own trait

[pitaj]

Proposal

Problem statement

One of the common use-cases for the allocator_api feature is using arena allocators to reduce overhead. These arena allocators often have no-op dealloc, instead freeing all memory when the allocator itself is dropped. In these cases, we would like an API design that allows for the programmer to avoid the overhead of storing a largely useless reference to the allocator in every container.

Motivating examples or use cases

// dyn safe
trait Foo { ... }

{
    // `deallocate` is a no-op, freeing is done when the allocator instance is dropped
    let mut bump = Bump::new();
    let mut lists: Vec<Box<dyn Foo, &Bump>> = Vec::new();
    
    // Many of these
    list.push(Box::new_in(foo, &bump) as Box<dyn Foo, &Bump>);
    
    // Despite the fact that the boxes don't need the allocator for anything,
    // they still must pay the memory overhead of storing the allocator ref.
}

Solution sketch

// in core::alloc

// move `deallocate` to it's own trait
pub unsafe trait Deallocator {
    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout);
}

// every `Allocator` is also a `Deallocator` for convenience
pub unsafe trait Allocator: Deallocator {
    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError>;
    
    // ... etc
}

// Change `Box`, etc to only require `Allocator` when absolutely necessary
// and require `Deallocator` everywhere else.

Usage example:

/// `Bar` is a bump allocator
pub struct Bar { ... }
pub struct BarDealloc<'a>(PhantomData<&'a Bar>);
unsafe impl Deallocator for &Bar { ... }
unsafe impl Allocator for &Bar { ... }
unsafe impl Deallocator for BarDealloc {
    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
        // no-op
    }
}
impl Bar {
    pub fn make_box<T>(&self, value: T) -> Box<T, BarDealloc<'_>> {
        let (ptr, _) = Box::into_raw_with_allocator(Box::new_in(value, self));
        unsafe { Box::from_raw_in(ptr, BarDealloc(PhantomData)) }
    }
}

Alternatives

Leave as-is, the same can technically be accomplished with panics at the cost of prolific footguns.

Links and related work

• zulip thread
• Split Allocator trait wg-allocators#112

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[scottmcm]

For exposition, probably worth penciling in that this would use the "you can implement Deallocator::deallocate in your impl Allocator block" mechanism, though I forget what the current proposal is for how to spell that.

[programmerjake]

For exposition, probably worth penciling in that this would use the "you can implement Deallocator::deallocate in your impl Allocator block" mechanism, though I forget what the current proposal is for how to spell that.

that's https://github.com/rust-lang/rfcs/pull/3851/files

[nia-e]

I sketched something out in Zulip, but I think this can be achieved without changing the current implementation of Allocator. If we flip this on its head somewhat:

trait Allocator: Deallocator {
    fn allocate(&self, layout: Layout) -> NonNull<u8>;

    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout);
}

trait Deallocator {
    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout);
}

impl<T: Allocator> Deallocator for T {
    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
        unsafe { <T as Deallocator>::deallocate(self, ptr, layout) }
    }
}

Then, types like Box can simply have another generic parameter for the deallocator and different methods for instantiating one with a custom allocator and different custom deallocator. The downside here is that it's admittedly really annoying that for T: Allocator, deallocation will need the annoying syntax of <T as {Allocator, Deallocator}>::deallocate() with both of these being identical; however, rust-lang/rust#148605 should fix this (and/or adding the bound Allocator: Deallocator later and doing some coinductivity magic in the trait solver to have this resolve, which would be sound in this case and there is precedent for this in the stdlib). If we go for something like my suggestion, Allocator could stabilise soon as-is while still leaving open the possibility for custom deallocators in the near future.

edit: this seems to work on stable as-is with the circular dependency between Allocator and Deallocator; see this playground link

[m-mueller678]

I would like to note that no-op deallocation is not the only motivator for this. Many allocators can derive all information necessary for deallocation from the deallocated pointer and layout.

[nia-e]

This was discussed in today's @rust-lang/libs-api meeting, and we had a few questions. For one we'd like some clarification on the possible usecases - is this just relevant for bump/arena allocation, or is there more not mentioned in this thread? We're also curious if this needs to be explicitly done by splitting the trait, since that would mean Allocator being stabilised would be blocked on Deallocator instead of e.g. the supertrait item shadowing idea I had proposed to allow Deallocator to be implemented and stabilised at a later time. Lastly, it would be useful to get an idea of the API we'd want for working with this in stdlib collections (e.g. do we just relax the Box<T, A: Allocator> bound to Box<T, A: Deallocator>? Which methods do we implement on the case where A: Allocator vs A: Deallocator etc.)

[m-mueller678]

Use cases

This is relevant to any allocators that need less information to perform a deallocation than they need to perform an allocation. The most prominent examples of this are allocators with no-op deallocation. However, it is not exclusive to no-op deallocators. For instance, one might implement an Allocator that allocates to a specific jemalloc arena. This allocation can be freed without specifying which arena it was allocated from, as jemalloc can derive this information. C-style allocators (which implement free without taking a size) often recover the allocation size from the passed pointer. Similar tricks can be used by many potential implementors of Allocator to recover all necessary information for deallocation.

This is most useful for Box, Rc, and Arc, both because they inherently cannot allocate after construction and because they tend to be smaller than proper collections, increasing the relative overhead of non-ZST deallocators. It can also be applied to other collections. Often, collections are constructed and then never modified. These, too, need only a Deallocator after construction. Strings in particular come to mind, though alloc::String is not actually generic over its allocator.

API changes

All types that are currently generic over Allocator become generic over Deallocator. So do their Drop impls, non-mutating methods, from_raw, AsMut, BorrowMut, and DerefMut. To keep the discussion short, other trait impls and mutating methods keep the Allocator requirement for now. They can be relaxed to only require Deallocator at a later time, where appropriate. This makes from_raw the only way to construct a collection whose allocator is only Deallocator. Some alternative ways of constructing such collections were discussed on Zulip, but they all have some drawbacks. Some collections do not have a from_raw (e.g., BTreeMap). These should probably keep the Allocator bound for now, to avoid confusion.

Alternatives

• One options is to just implement the changes as proposed above right away, without waiting for super trait auto impl. Allocators are still unstable, so users can just deal with the breakage. If there are other changes to Allocator before stabilization, then it would make sense to just throw this one in with the rest of them.

• Another alternative is to perform the above changes once super trait auto impl is here. This would make it easier for current users of the unstable api to migrate. This is a bet on the features actually being stabilized soon. I think splitting the trait would then still be a breaking change, as users might explicitly refer to Allocator::deallocate, so we could only stabilize Allocator after we have super trait auto impl. If I am wrong on that and it would not be a breaking change, then I see no downsides with this approach.

• Yet another is to use super trait item shadowing. This allows stabilizing allocator before super trait auto impl, but has a few minor downsides:

  • Having two deallocate functions might be confusing.
  • It makes error messages slightly misleading by referring to the blanket impl first, rather than suggesting the user implement Deallocator. Prompting the user to implement Allocator probably gives them a good enough hint about where the problem is though.
  • It slightly grows the size of vtables for dyn Allocator. This is probably negligible for practically all applications and it is still undecided if dyn Allocator is even a good idea.
  • super trait item shadowing is not yet stable. It seems prudent to wait at least until it stabilizes (PR). In the unlikely case that it fails to become stable, we would be stuck with ugly syntax otherwise.

[Keith-Cancel]

Lastly, it would be useful to get an idea of the API we'd want for working with this in stdlib collections (e.g. do we just relax the Box<T, A: Allocator> bound to Box<T, A: Deallocator>? Which methods do we implement on the case where A: Allocator vs A: Deallocator etc.)

With Deallocator as a super trait std collection types like box can just be Box<T, A: Deallocator>.

Any methods that need allocation can be:

impl <T, A: Allocator> Box<T, A> {
    // ... methods
}

Things like drop obviously only need just the Deallocate.

Even for types like Vec this works fine. While this little example I posted #t-libs/wg-allocators > State of Allocators @ 💬 mainly was talking taking about context. You can get idea of how idea of using the split.

However, yes we probably want to outline what methods on the std::collections need the Allocator bound vs the Deallocator bound or neither.