Module elfmalloc::slag [−] [src]

A fast concurrent memory allocator.

This module implements a novel memory allocator. The high-level design is inspired by the scalloc allocator, but most of the details are different. We leverage scalable BagPipe data-structures to hold available pages, and we use a novel design for individual "spans" of memory (called Slags) that allow for extremely fast remote frees while still facilitating competitive speeds for local allocation and free operations.

`Slag` Lifecycle

Slags start as unhewn blocks of memory in a large memory-mapped region called a Creek. They are then stored in a Bagpipe data-structure (a scalable queue-like object with weak ordering guarantees) in a PageAlloc before they are finally initialized by a thread that is able to claim it after removing it from the BagPipe. Slags that are claimed in this way are said to be in the owned state.

Owned `Slag`s

Owned Slags are used to service per-thread allocations for a particuar size class. They are equipped with fast stack and iterator data-structures to allow for fast allocation and deallocation operations that are local to that particular Slag. Of course, some free operations may correspond to Slags that were not allocated from the Slag local to the current thread. These "remote" frees are serviced by an efficient fetch_or instruction applied to the remote slag's bit-set. Remote frees also increment a Slag-specific reference count.

N.B: The reference count and the bit-set cannot be updated atomically, which leads to some subtle code.

If a thread is unable to service allocations from its local Slag, it attempts to uncalim it and get a new Slag with more available objects. The unclaim protocol is a bit tricky, but if it is successful, the Slag is transitioned to the floating state.

Floating, Available and Full `Slag`s

A Slag is floating if it has fewer available objects than some size-class-specific cutoff value. In this state, frees are performed in the same manner as they were in the owned state. The difference here is that modifications to a Slag's reference count matter: If a free operation increments the reference count above the cutoff, that thread pushes it to a BagPipe containing Slags that can be re-used.

Slags in this BagPipe are called available. From there, they can transition back to the owned state. However, what if we have a large number of Slags that are completely full? If they go unused, it makes sense to hand them back to the Operating System.

An available Slag can be transitioned to a full Slag if it is present in the available BagPipe when it becomes completely full (i.e. all objects from this Slag have been freed). If it is present, then it can be revoked (i.e. removed in-place) from the BagPipe and placed in a global cache of dirty pages (mentioned above). From there it can be uncommitted or cached for use by other object sizes.

Structs

AllocBuilder	A builder-pattern-style builder for `MagazineAllocator`s and `LocalAllocator`s.
Creek	A large, contiguous, memory-mapped region of memory.
LocalAllocator
LocalCache	A `LocalCache` provides thread-local data on top of a `SlagAllocator`.
MagazineAllocator
MagazineCache	A different approach to caching to `LocalCache` inspired by Bonwick-style magazines.
Metadata	Metadata about a particular size-class of objects allocated to a particular page size.
PageAlloc	An allocator for large, fixed-sized objects.
Slag	A collection of objects allocated on the heap.
SlagAllocator	Allocator state wrapping a `Slag`.

Traits

CoarseAllocator	An allocator that allocates objects at the granularity of the page size of the underlying `MemoryBlock`.
DirtyFn	A `DirtyFn` is a callback that is called upon allocating a clean page from a `PageAlloc`. It generally does nothing, but its presence in `PageAlloc` allows us to inject other callbacks for debugging or performance analysis.
MemoryBlock	A generator of chunks of memory providing an `sbrk`-like interface.

Functions

compute_metadata

Compute an optimal layout for objects of size obj_size for Slags of size page_size with cutoff a cutoff_factor fraction of total objects, and a local index local_index.

Type Definitions

RevocablePipe