orderly-allocator

crates.io | docs.rs | github

A super-simple soft-realtime allocator for managing an external pool of memory.

Since the allocator stores its metadata separately from the memory pool it manages, it could be useful as a suballocator for e.g. a GPU buffer.

Has worst-case O(log(n)) performance* for alloc & free. Provides a best-fit search strategy and coalesces immediately on free, resulting in low fragmentation.

orderly-allocator uses BTrees internally, so while it has O(log(n)) complexity expect excellent real-world performance; Rust's BTree implementation uses a branching factor of 11. This means even if the allocator were in a state where it had ~100,000 separate free-regions, a worst-case lookup will traverse only 5 tree nodes.

Usage

This crate provides two types Allocator and Allocation which can be used to manage any kind of buffer as demonstrated.

use {
  ::core::mem::{align_of, size_of},
  ::orderly_allocator::{Allocation, Allocator},
};

#[repr(transparent)]
struct Object([u8; 16]);

// get a pool of memory and create an allocator to manage it
const POOL_SIZE: u32 = 2u32.pow(16);
let mut memory: Vec<u8> = vec![0; POOL_SIZE as usize];
let mut allocator = Allocator::new(POOL_SIZE);

assert_eq!(allocator.total_available(), POOL_SIZE);

// allocate some memory
let allocation = allocator.alloc_with_align(
  size_of::<Object>() as u32,
  align_of::<Object>() as u32
);

// fill the corresponding memory region with some data
if let Some(allocation) = allocation {
  let object = Object([
    0x68, 0x65, 0x6C, 0x6C, 0x6F, 0x2C, 0x20, 0x6F, 0x72, 0x64, 0x65, 0x72,
    0x6C, 0x79, 0x21, 0x0,
  ]);
  &memory[allocation.range()].copy_from_slice(&object.0[..]);
}

assert_eq!(
  allocator.total_available(),
  POOL_SIZE - size_of::<Object>() as u32
);

// free the memory region when it is no longer needed
allocator.free(allocation.unwrap());

assert_eq!(allocator.total_available(), POOL_SIZE);

#![no_std]

This crate works in a no_std context, however it currently requires the alloc crate for the BTree implementation.

Future Work

*Currently the BTree implementation at the heart of orderly-allocator will ask the global-allocator for memory, for newly-created nodes, every now and then.

It would be possible to turn this into a firm- or hard-realtime allocator by using a different BTree implementation, one which preallocated memory for its nodes ahead of time.

Other Libraries

Other libraries in the ecosystem that might serve a similar purpose:

• offset-allocator, A Rust port of Sebastian Aaltonen's C++ package of the same name.

License

This crate is licensed under any of the Apache license 2.0, or the MIT license, or the Zlib license at your option.

Contribution

Unless explicitly stated otherwise, any contributions you intentionally submit for inclusion in this work shall be licensed as above, without any additional terms or conditions.