Crate simple_chunk_allocator
source · [−]Expand description
Simple Chunk Allocator
A simple no_std
allocator written in Rust that manages memory in fixed-size chunks/blocks. Useful for basic no_std
binaries where you want to manage a heap of a few megabytes without complex features such as paging/page table
management. Instead, this allocator gets a fixed/static memory region and allocates memory from there. This memory
region can be contained inside the executable file that uses this allocator. See examples down below.
⚠ Other allocators with different properties (for example better memory utilization but less performance) do exist. The README of the repository contains a section that discusses how this allocator relates to other existing allocators on <crates.io>. ⚠
TL;DR
- ✅
no_std
allocator with test coverage - ✅ uses static memory as backing storage (no paging/page table manipulations)
- ✅ allocation strategy is a combination of next-fit and best-fit
- ✅ reasonable fast with low code complexity
- ✅ const compatibility (no runtime
init()
required) - ✅ efficient in scenarios where heap is a few dozens megabytes in size
- ✅ user-friendly API
The inner and low-level ChunkAllocator
can be used as #[global_allocator]
with the synchronized wrapper type
GlobalChunkAllocator
. Both can be used with the allocator_api
feature. The latter enables the usage in several
types of the Rust standard library, such as Vec::new_in
or BTreeMap::new_in
. This is primarily interesting for
testing but may also enable other interesting use-cases.
The focus is on const
compatibility. The allocator and the backing memory can get initialized during compile time
and need no runtime init()
call or similar. This means that if the compiler accepts it then the allocation will
also work during runtime. However, you can also create allocator objects during runtime.
The inner and low-level ChunkAllocator
is a chunk allocator or also called fixed-size block allocator. It uses a
mixture of the strategies next-fit and a best-fit. It tries to use the smallest gap for an allocation request to
prevent fragmentation but this is no guarantee. Each allocation is a trade-off between a low allocation time and
preventing fragmentation. The default chunk size is 256 bytes
but this can be changed as compile time const generic.
Having a fixed-size block allocator enables an easy bookkeeping algorithm through a bitmap but has as consequence that
small allocations, such as 64 byte
will take at least one chunk/block of the chosen block size.
This project originates from my Diplom thesis project. Since I originally had lots of struggles to create this (my first ever allocator), I outsourced it for better testability and to share my knowledge and findings with others in the hope that someone can learn from it in any way.
Minimal Code Example
#![feature(const_mut_refs)]
#![feature(allocator_api)]
use simple_chunk_allocator::{heap, heap_bitmap, GlobalChunkAllocator, PageAligned};
// The macros help to get a correctly sized arrays types.
// I page-align them for better caching and to improve the availability of
// page-aligned addresses.
/// Backing storage for heap (1Mib). (read+write) static memory in final executable.
///
/// heap!: first argument is chunk amount, second argument is size of each chunk.
/// If no arguments are provided it falls back to defaults.
/// Example: `heap!(chunks=16, chunksize=256)`.
static mut HEAP: PageAligned<[u8; 1048576]> = heap!();
/// Backing storage for heap bookkeeping bitmap. (read+write) static memory in final executable.
///
/// heap_bitmap!: first argument is amount of chunks.
/// If no argument is provided it falls back to a default.
/// Example: `heap_bitmap!(chunks=16)`.
static mut HEAP_BITMAP: PageAligned<[u8; 512]> = heap_bitmap!();
// please make sure that the backing memory is at least CHUNK_SIZE aligned; better page-aligned
#[global_allocator]
static ALLOCATOR: GlobalChunkAllocator =
unsafe { GlobalChunkAllocator::new(HEAP.deref_mut_const(), HEAP_BITMAP.deref_mut_const()) };
fn main() {
// at this point, the allocator already got used a bit by the Rust runtime that executes
// before main() gets called. This is not the case if a `no_std` binary gets produced.
let old_usage = ALLOCATOR.usage();
let mut vec = Vec::new();
vec.push(1);
vec.push(2);
vec.push(3);
assert!(ALLOCATOR.usage() > old_usage);
// use "allocator_api"-feature. You can use this if "ALLOCATOR" is not registered as
// the global allocator. Otherwise, it is already the default.
let _boxed = Box::new_in([1, 2, 3], ALLOCATOR.allocator_api_glue());
}
Macros
Helper macro that initializes a page-aligned static memory area with a correct size to
get used as heap in crate::GlobalChunkAllocator
.
Helper macro that initializes a page-aligned static memory area with a correct size to
get used as heap bookkeeping bitmap in crate::GlobalChunkAllocator
.
Structs
Helper struct generated by GlobalChunkAllocator
that can be used in structs that accept
a custom instance of a specific allocator implementation.
Low-level chunk allocator that operates on the provided backing memory. Allocates memory with a variant of the strategies next-fit and best-fit.
Synchronized high-level wrapper around ChunkAllocator
that implements the Rust traits
GlobalAlloc
which enables the usage as global allocator. The method
GlobalChunkAllocator::allocator_api_glue
returns an object of type AllocatorApiGlue
which can be used with the allocator_api
feature.
Wrapper around a T
that gets page-aligned.
All important methods allow the usage in const contexts.
Enums
Possible errors of ChunkAllocator
.
Constants
The default number of chunks. If the default chunk size of DEFAULT_CHUNK_SIZE
gets
used then this equals to 1MiB of memory.
Default chunk size used by ChunkAllocator
. 256 Bytes is a trade-off between fast
allocations and efficient memory usage. However, small allocations will take up at least
this amount if bytes.