NonZeroLayout for Allocator

[pitaj]

Proposal

Problem statement

The current allocator trait takes arguments of type Layout, which can be zero-sized. However, many allocators do not support zero-sized allocations, and must manually implement a ZST check when implementing the trait.

A nonzero check it can't be elided when allocating via &dyn, and having an allocator on the other side of a crate boundary might mean it isn't. There is already special handling for ZSTs in the implementation of Vec and other containers, so sometimes these checks are redundant.

Motivating examples or use cases

Moving the ZST check to the caller side means it can pretty much always be elided even if the allocator is opaque.

Solution sketch

pub struct NonZeroLayout {
    size: NonZeroUsize,
    align: Alignment,
}

// existing Layout type acts as the "builder" for the NonZeroLayout type
impl Layout {
    pub fn non_zero(self) -> Option<NonZeroLayout> {
        ...
    }
}

pub unsafe trait Allocator {
    fn allocate(&self, layout: NonZeroLayout) -> Result<NonNull<[u8]>, AllocError>;
    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: NonZeroLayout);
}

Alternatives

We could also provide "convenience" functions which can handle ZSTs:

pub unsafe trait Allocator {
    fn allocate_maybe_zst(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        if let Some(layout) = layout.non_zero() {
            self.allocate(layout)
        } else {
            Ok(NonNull::slice_from_raw_parts(NonNull::dangling_mut(), 0))
        }
    }

    // likewise for deallocate
}

and allocators which handle ZSTs without issue can override the implementations.

Links and related work

• zulip

Prior wg discussions decided against this, but more recent discussions support it

• Ban zero-sized allocations wg-allocators#16
• Add default implementation for allocating zero-sized types (or ZSTs) wg-allocators#38

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]

Two other possible alternatives that come to mind, without actually taking a position whether they're better:

• Also add a requirement that size be a multiple of alignment, rather than just not overflowing if rounded up. (Layout doesn't have that because it's more a LayoutBuilder than a RustLayout. I don't know what real allocators actually do with such not-a-multiple requests today, though.)
• Split the NonZeroLayout into just being two values, a mem::NonZeroSize and a mem::Alignment. That does mean allocators would have to handle the possibility of round-up-to-alignment overflowing isize::MAX, but since size+align couldn't overflow usize, I don't know how impactful that would be -- and we can offer methods that do the right thing regardless. (This one would have the nice property that we could actually do it by adding mem::Size and use num::NonZero<mem::Size>, since Size would just be usize is (0..=isize::MAX.cast_unsigned()).)

[CAD97]

I still like the idea in theory that std could provide an Allocator wrapper which performs the zero-size check and guarantees a no-op allocation, and collections can use that wrapper around the user-provided A instead of needing to remember to special-case the ZST case every time they touch the allocator. So if we go this direction, I'd prefer the ZST handler to be final so consumers don't have to worry about ZST allocation being realized with metadata. The reason collections are handling ZSTs directly is to avoid the need to have ZST "allocation" be real and require calling alloc/dealloc.

[nia-e]

This was discussed in today's @rust-lang/libs-api meeting; some concerns were raised over increasing API complexity too much for Allocator & the need to special-case ZST allocations (e.g. for an empty Vec), but that's not a hard no. Are there any performance or code size numbers to suggest this would be a significant improvement?

[Amanieu]

I don't think the potential performance gains here justify the additional API complexity. Specifically:

• Most allocators can handle zero-sized allocations just fine without any special casing. For example, a bump allocator just bumps by 0.
• The allocator API make no promises that zero-sized allocations actually consume zero memory. If you need this guarantee (e.g. Vec::new which needs to be const) then you have to do this check outside of the allocator. But we shouldn't impose this on users which don't need it: the API should "just work" for most users.
• If the allocator can't natively handle sizes of 0, it's trivial to either round the size up to 1 or to return a dangling pointer. Either way, this is very cheap in practice and I feel doesn't justify making the API more complex.