An implementation of Allocator can allocate, grow, shrink, and deallocate arbitrary blocks of data described via [Layout][].

Allocator is mostly designed to be implemented on ZSTs, references, or smart pointers, but can also be implemented directly on the underlying memory-owning type so long as it upholds the necessary guarantees. In general, an allocator of the type MyAlloc([u8; N]) cannot be soundly created without being pinned or otherwise immovable in order to be correct.

In contrast to [GlobalAlloc][], Allocator allows zero-sized allocations. If an underlying allocator does not support this (like jemalloc) or responds by returning a null pointer (such as libc::malloc), this must be caught by the implementation.

In order to be usable in a flexible manner while still being sound, implementors of the trait must uphold very detailed semantics as explained below; the following terms are thus provided as vocabulary for allocator safety and implementation requirements:

Equivalent allocators

Multiple allocator values can sometimes be interchangeable with each other. When this is the case, we refer to those allocators as being equivalent to each other.

Users of allocators may assume the following are true of equivalent allocators, and implementors must ensure these rules are upheld:

• An allocator is equivalent to itself. (Equivalence is reflexive.)
• If an allocator is equivalent to a second allocator, then the second allocator is also equivalent to the first. (Equivalence is symmetric.)
• If an allocator is equivalent to a second allocator, and the second allocator is equivalent to a third allocator, then the first allocator is also equivalent to the third allocator. (Equivalence is transitive.)
• Moving, subtyping, unsize-coercing, or trait-upcasting an allocator does not change what the allocator is equivalent to.
• Copying or cloning an allocator creates an equivalent one, should the AllocatorClone trait be implemented.

Additionally, implementors of Allocator may specify additional equivalences between allocators. It is the responsibility of such implementors to make sure that equivalent allocators have "compatible" Allocator implementations. In particular, the standard library specifies the following equivalences:

• A reference to an allocator (either & or &mut) is equivalent to the allocator being referenced.
• A Box, Rc, or Arc containing an allocator is equivalent to the allocator inside.
• All Global allocator instances are equivalent with each other.
• All System allocator instances are equivalent with each other.

Currently allocated memory

Some of the methods require that a memory block is currently allocated by some specific allocator. This means that:

• the starting address for that memory block was previously returned by the allocate, allocate_zeroed, grow, grow_zeroed, or shrink methods, called on an allocator that's equivalent to this specific allocator; and
• the memory block has not subsequently been invalidated.

Invalidating memory blocks

A memory block that is currently allocated becomes invalidated when one of the following happens:

• The memory block is deallocated. This occurs when the memory block is passed as an argument to a deallocate call, or when it is passed as an argument to a grow, grow_zeroed or shrink call that returns Ok.
• For all (equivalent) allocators that this memory block is currently allocated by, at least one of the following has occurred:
  • The allocator's destructor runs.
  • The allocator is mutated through a public or otherwise untrusted API taking &mut access.
  • One of the borrow-checker lifetimes in the allocator's type expires.

Note that these conditions imply that a collection may ensure that any specific currently allocated memory block won't be invalidated by:

• not deallocating that memory block,
• owning an allocator that memory block is allocated with, and
• not publicly exposing &mut access to that allocator.

Also note that safe public API of an allocator with & access is not allowed to invalidate its memory blocks. Furthermore, unsafe public API of an allocator with & access must document that they invalidate memory blocks (e.g., by calling deallocate) if they do. Therefore, a collection may safely expose & access to its allocator.

Also note that, even in cases where there are other "alive" allocators known to be equivalent to a given collection's allocator, most collections still should not publicly expose &mut access to their allocators. The fact that there are other "alive" allocators would prevent this &mut access from invalidating the collection's memory block, but public &mut access is still likely to be unsound, since a user could replace the collection's allocator with a non-equivalent allocator, causing the collection to deallocate its memory with the wrong allocator.

Memory fitting

Some of the methods require that a layout fits a memory block or vice versa. This means that the following conditions must hold:

• the memory block must be currently allocated with alignment of layout.align(), and
• layout.size() must fall in the range min ..= max, where:
  • min is the size of the layout used to allocate the block, and
  • max is the actual size returned from allocate, allocate_zeroed, grow, grow_zeroed, or shrink.

Safety

Implementors of Allocator must ensure that a memory block that is currently allocated by the allocator points to valid memory until that memory block is invalidated. The implementor must also not violate this invariant of Allocator via allocator equivalences that are in the implementor's control.

Additionally, any memory block returned by the allocator must satisfy the allocation invariants described in core::ptr. In particular, if a block has base address p and size n, then p as usize + n <= usize::MAX must hold. These blocks must also be wholly disjoint.

This ensures that pointer arithmetic within the allocation (for example, ptr.add(len)) cannot overflow the address space, and that it is possible to perform nonoverlapping copies between allocations.

None of the allocating or deallocating methods may unwind. This restriction may be lifted in the future by ensuring unwinding out of an allocating function always aborts. If an implementor of Allocator also has drop glue or directly implements Drop, dropping the allocator must not result in an unwind.

It is undefined behavior for the allocator to read, write, or deallocate any memory that is currently allocated. This memory is owned by the user; the allocator must not touch it.

Lastly, the methods on this trait must be correct; in particular, the layout requested must be respected, calls must zero out memory if the documentation so requires, returning an AllocError from a reallocating method must indeed ensure that the old pointer was not invalidated, and de/reallocating calls must accept layouts in the ranges defined by their documentation.