Crate context_allocator

context-allocator

This provides allocators suitable for a number of use cases.

All of these allocators implement the traits ::std::alloc::GlobalAlloc and ::std::alloc::Alloc, as we as a common base trait, Allocator.

The most useful is a global allocator which allows switching between thread, coroutine and global (and thuse lockable) memory allocators, using the macro global_thread_and_coroutine_switchable_allocator().

Allocators provided include:-

• BumpAllocator, a never-freeing bump allocator with slight optimization for reallocating the last allocation.
• BitSetAllocator, an allocator that uses a bit set of free blocks; uses 64-bit chunks to optimize searches.
• MultipleBinarySearchTreeAllocator, an efficient allocator which minimizes fragmentation by using multiple red-black trees of free blocks which are aggresively defragmented.
• ContextAllocator, a choice of either BumpAllocator, BitSetAllocator or MultipleBinarySearchTreeAllocator.
• MemoryMapAllocator, a mmap allocator with support for NUMA policies.
• GlobalThreadAndCoroutineSwitchableAllocator, suitable for replacing the global allocator and provides switchable allocators for global, thread local and context (coroutine) local needs.

Allocators use a MemorySource to obtain and release memory. Memory sources provided include:-

• MemoryMapAllocator, useful for thread-local allocators as it can obtain memory from NUMA-local memory.
• ArenaMemorySource, an arena of fixed blocks which is itself backed by a memory source; this is useful as a source for the BumpAllocator and BitSetAllocator when used for contexts.

Additionally a number of adaptors are provided:-

• AllocatorAdaptor, an adaptor of Allocator to GlobalAlloc and Alloc; use it by calling Allocator.adapt()
• GlobalAllocToAllocatorAdaptor, an adaptor of GlobalAlloc to Allocator, useful for assigning a global allocator to GlobalThreadAndCoroutineSwitchableAllocator.
• AllocToAllocatorAdaptor, an adaptor of Alloc to Allocator.

When using GlobalThreadAndCoroutineSwitchableAllocator, it is possible to save and restore the allocator state for the currently running context (coroutine). It is also possible to create a lockless, fast thread-local allocator which make use of NUMA memory, unlike a conventional malloc.

Future

• Investigate wrapping Rampant Pixel's Memory Allocator.
• Investigate using DPDK's allocator.
• Investigate a B-tree backed allocator.
• Investigate a design that uses multiple doubly-linked 'free' lists of blocks; blocks can be variable in size but the free list is sorted
  • Iteration over a particular free-list range may encountered blocks too small, or blocks so large they can be split up.
  • This design is similar to that used by DPDK.
  • To make the allocator multi-threaded, DPDK takes a spin lock on a particular 'heap', which is a set of free lists.
• Investigate an arena allocator for fixed-size blocks (suitable for holding ready-to-rumble context allocators, say).
• Investigate a fall-back over-size allocator for a thread-local allocator, which could use the NumaMemoryMapAllocator underneath.
• Investigate supporting over-size allocations in MultipleBinarySearchTreeAllocator by scanning the largest binary search tree for contiguous blocks.
• Investigate a persistent-memory backed allocator.
• Properly support excess allocations and Alloc's grow_in_place functions, but only if these are used by downstream collections.
• Investigate the use of the BMI1 intrinsics _blsi_u64 (extract lowest set bit), _blsmsk_u64 and _blsr_u64.

Modules

arena_memory_source	A memory source which uses an arena.
bit_set	A bit set based allocator; allows reallocations, but requires a linear scan to find free blocks.
global	Global, switchable allocator.
mmap	A memory map (mmap) based allocator with support for NUMA.

Macros

global_thread_and_coroutine_switchable_allocator

Creates a new global, switchable allocator inside a module $mod_name.

Structs

AllocToAllocatorAdaptor	Adapts implementations of Alloc to Allocator.
AllocatorAdaptor	Adapts an Allocator to the GlobalAlloc and Alloc traits.
BumpAllocator	This is a very simple bump allocator of minimal utility.
GlobalAllocToAllocatorAdaptor	Adapts implementations of GlobalAlloc to Allocator.
MultipleBinarySearchTreeAllocator	An allocator which uses sorted lists (red-black binary search trees) of different block sizes (sizes are powers of 2); in that sense, it is similar to an efficient buddy allocator.

Enums

ContextAllocator

An allocator designed for contexts with different lifetimes.

Traits

Allocator	A helper trait that brings together the core, common functionality required to implement the traits GlobalAlloc and Alloc.
MemorySource	A memory source is a sort-of crude allocator that can obtain and release memory, from, say, the operating system, an arena or some fixed range.