Allocator: split deallocation into its own trait

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
• https://github.com/rust-lang/wg-allocators/issues/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.

Start with the core::alloc trait proposal in the issue, then read the linked Zulip thread and wg-allocators issue #112 for the API discussion. Progress would require resolving the Deallocator and Allocator design and getting libs-api review; the issue does not identify a bounded implementation task.