Crate basic_allocator

A simple memory allocator, written for educational purposes.

This module was written primarily for the code to be read. The allocator enclosed can be used as a memory allocator in a rust program.

Usage

use basic_allocator::UnixAllocator;

#[global_allocator]
static ALLOCATOR: UnixAllocator = UnixAllocator::new();
fn main() {
    println!("It works!")
}

See also core::alloc::GlobalAlloc.

Major Components

This module has several parts.

BlockList

A BlockList is a linked list of freed memory not returned to the OS, which can be reused by the allocator.

The free block starts with a header, and then has unused memory after that. The header is 16 bytes, and consists of a pointer to the next block and the size of the block as a whole.

RawAlloc

A RawAlloc is a single-threaded, non-thread-safe heap and freed memory manager, implementing core::alloc::GlobalAlloc. However, because it is not thread-safe, it canot be used as a global allocator.BlockList

UnixAllocator

A UnixAllocator wraps RawAlloc with a spin lock to make it thread-safe, allowing it to be used as the global allocator. It also combines RawAlloc with a unix-specific UnixHeapGrower to use virtual memory pages as its underlying basis for making those calls.

HeapGrower

HeapGrower is a simple trait interface meant to abstract over the calls to the OS to expand the heap.

Implementation

Free memory is maintained in a linked list. The allocator has a pointer to the first block, and each block starts with a header with a pointer to the next block and the size of the current block. Blocks are in-order, so that merges are easily implemented.

Allocation

When RawAlloc is called to allocate size bytes:

1. The BlockList is iterated through, and if any free block is found there large enough for the request, it is used. If the found block is just the right size, "popped" out of the linked list, and returned as a block of free memory; otherwise, the last size bytes of the block is returned as free memory, and the block's header is adjusted as needed.
2. If no suitable block is found in the list, the appropriate HeapGrower instance is called to "grow the heap". For the UnixHeapGrower, this means that one or more pages of virtual memory are requested from the OS. The first size bytes are returned, and the remainder of the page is added to the BlockList.

Deallocation

When RawAlloc is called to deallocate size bytes at a pointer ptr:

1. The BlockList is iterated through to find where in the list ptr should be to remain sorted.
2. ptr is inserted, and an attempt is made to merge with both the preceding and following blocks. Each attempt is successful only if the two blocks involved are adjacent.

Structs

BlockIter
BlockList	A BlockList is a linked list of "free" blocks in memory.
FreeBlock	A FreeBlock is a wrapper around a pointer to a freed block to be maintained in a BlockList.
FreeHeader	The header for our free blocks.
GenericAllocator	A thread-safe allocator, using a spin lock around a RawAlloc.
RawAlloc	A raw allocator, capable of growing the heap, returning pointers to new allocations, and tracking and reusing freed memory.
Stats
ToyHeap
UnixAllocator
UnixHeapGrower	UnixHeapGrower uses virtual memory to grow the heap upon request.
Validity	Validity contains a representation of all invalid states found in a BlockList.

Enums

ApplyState	State after a single "apply".
Relation	An enum for easy comparison of blocks and their order

Traits

HeapGrower