Alloc: Clarify supported Layouts

[joshlf]

TLDR

The Alloc trait doesn't currently document what Layouts are guaranteed to be supported, which leaves consumers unsure whether their allocations will fail with AllocErr::Unsupported. This issue proposes addressing this by introducing a distinction between "general" and "specialized" allocators, and documenting a set of required Layouts that the former must be able to handle.

Problem Statement

One of the errors that the Alloc trait's allocation methods can return is AllocErr::Unsupported, which indicates that the allocator doesn't support the requested Layout. Currently, the Alloc trait places no restrictions - either using the type system or in documentation - on what Layouts must be supported. Thus, consumers of a generic Alloc (as opposed to a particular type that implements Alloc) must assume that any given allocation request might be unsupported.

This creates a problem: in order for a consumer of an Alloc to be able to guarantee to their users that they will not crash at runtime (after all, having gotten AllocErr::Unsupported, there's really no other recourse other than to abort or bubble up the error), they need to document the set of Layouts that they might request from an allocator provided by the user. This, in turn, requires that all implementations of Alloc document precisely which Layouts they can handle so that users can ensure that they're upholding the requirements of the consumers. Even if all of this documentation was written and maintained, it'd impose a very large burden on the users. Imagine every time you wanted to use Vec<T, A: Alloc> for a particular, custom A, you had to carefully read the Vec documentation and the documentation for the desired allocator to ensure they were compatible.

Worse still, the current mechanism for configuring the global allocator involves providing an instance of Alloc. In this case, there's no way for code to communicate to the person configuring the global allocator what their requirements are, since that code might be buried behind an arbitrary number of dependencies (e.g., I use crate foo which depends on crate bar which depends on crate baz which is incompatible with the global allocator I've configured).

This came up in practice for me while working on my slab-alloc crate (which is basically just an object cache). I allow users to provide a custom Alloc to back a SlabAlloc instance, but I currently have no way other than in documentation to ensure that the provided Allocs will be compatible with the allocations I perform. If, for example, a user were to provide an allocator incapable of providing page-aligned allocations, or if somebody upstream of my crate configured a global allocator with this limitation, my code would crash at runtime.

Proposal

In order to address this issue, I propose introducing (in the Alloc trait's documentation) the notion of a "general allocator," which is an implementation of the Alloc trait which guarantees the ability to handle a certain class of standard allocation requests.

All implementations of Alloc are assumed to be general allocators unless documented to the contrary. All consumers of an Alloc type parameter are assumed to be compatible with a general allocator (that is, they do not perform any allocations which are outside of the set of guaranteed-to-be-supported allocations) unless documented to the contrary.

An allocation is guaranteed to be supported so long as it meets the following criteria:

• The size is non-zero
• The alignment is a non-zero power of two (this is already enforced by Layout)
• The size is a multiple of the alignment (this is already enforced by Layout)
• The alignment is not larger than the system's page size
• The size is not larger than 2^31 bytes on 32-bit platforms or 2^47 on 64-bit platforms

This system does not hamstring special-case uses. Alloc implementations which do not provide all of these guarantees merely need to document this. Alloc consumers which require more than what a general allocator guarantees merely need to document this, placing the onus on their users to provide an appropriate Alloc.

Open questions

• A 2^31 byte limit on 32-bit platforms might be limiting, so it might be worth making it 2^32 - 1 bytes (and 2^48 - 1 on 64-bit) instead. My concern is how this will play with signed integers, but that might be the sort of thing that it's reasonable to expect an allocator implementor to just be careful about.

[Mark-Simulacrum]

cc @alexcrichton

[alexcrichton]

AFAIK "unsupported" is meant for "niche allocators" where a general purpose allocate probably will never be returned from a general purpose allocator.

[joshlf]

Was that the idea? RFC 1398 doesn't give any explanation of when an allocator may return AllocErr::Unsupported, and neither do the current docs. @nikomatsakis , did you have thoughts on this when you wrote that RFC?

If we decide that that's the right answer, then we should at least document that. Documenting that requires introducing a notion of a "general purpose allocator," so I suspect that in documenting it, we'll end up with something pretty similar to what I proposed anyway, if perhaps a little less formal.

[pnkfelix]

@joshlf The intention of AllocErr::Unsupported, as I recall, was to allow an allocator to indicate "this request is not satisfiable by me, and never will be, regardless of what memory you deallocate or what allocation patterns you use in the future."

See also the comment above Unsupported here: https://github.com/nox/rust-rfcs/blob/master/text/1398-kinds-of-allocators.md#allocerr-api

I'm inclined to agree with @alexcrichton that a general purpose global allocator should not be returning Unsupported ... the only exception I could imagine would be for a zero-sized allocation request...

[joshlf]

Some clarifying questions to follow up:

• What happens if the user requests a Layout whose size is not a multiple of its alignment? I don't think that Layout lets you do that without using from_size_align_unchecked, but the documentation in Alloc doesn't actually specify that the size is required to be a multiple of the alignment. Is a general-purpose allocator allowed to make that UB? Should it instead explicitly check and return Unsupported? Is it required to support it (e.g., rounding up the size to the next multiple of the alignment)?
• Is there a maximum size that can be requested? If not, that implies that the only error possible even for very large allocations is OOM, which in turn implies that running that code on some system with the right resources would allow such a request to succeed. If there is a maximum, then should that be signaled using Unsupported?
• If the allocator doesn't support 0-sized allocations, is it acceptable for such a request to invoke UB rather than to result in Unsupported being returned?

[SimonSapin]

@joshlf’s first point is relevant to https://github.com/rust-lang/rust/issues/45955, though Layout::from_size_align currently does not check whether the size is a multiple of the alignment.

[SimonSapin]

Update: GlobalAlloc and Layout were stabilized in Rust 1.28 with:

• Requesting a zero-size alloc is UB as far as the trait is concerned. Specific impls may provide more guarantees about their behavior in that case. They may also choose to return a null pointer (indicating an allocation error or failure) in any case, including unsupported layout regardless of resource availability

• The requirements for a Layout to exist (checked by from_size_align, assumed by from_size_align_unchecked) are:

  • The alignment is power of two (and so non-zero)
  • The size does not overflow usize when rounded the size up to the next multiple of the alignment.

  That’s it. A zero-size Layout value is valid, and can be useful for example as an intermediate value passed to Layout::extend.

The Alloc trait is still unstable.