[−][src]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:
- 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 lastsize
bytes of the block is returned as free memory, and the block's header is adjusted as needed. - If no suitable block is found in the list, the appropriate
HeapGrower
instance is called to "grow the heap". For theUnixHeapGrower
, this means that one or more pages of virtual memory are requested from the OS. The firstsize
bytes are returned, and the remainder of the page is added to theBlockList
.
Deallocation
When RawAlloc
is
called to deallocate size
bytes at
a pointer ptr
:
- The
BlockList
is iterated through to find where in the listptr
should be to remain sorted. 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 |
FreeBlock | A |
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 |