bomalloc 0.3.1

A fragmentation-aware experimental allocator built around address-span ownership
Documentation

bomalloc

Crates.io Documentation MSRV License

An ownership-aware, fragmentation-conscious allocator built for concurrent runtimes.

bomalloc treats free address space as lazily transferable thread territory. Once a small-object span is activated, its owning thread allocates and recycles objects through thread-local state; other threads can still release those objects safely. Address-ordered metadata keeps free-space discovery and coalescing independent from the object hot path, and live objects never move.

The result is an allocator aimed at workloads with strong allocation locality, cross-thread handoff, or runtime/GC-shaped allocation bursts—not just a wrapper around a conventional per-thread arena.

Why bomalloc?

  • Thread-exclusive small-object hot path. Steady same-thread magazine and overflow hits do not touch shared atomic metadata. Activated Black spans are leased to their owner instead of being contested allocation pools.
  • Cheap cross-thread release. Foreign frees publish into a span-local atomic bitmap and can be consumed in batches by the owner; the freeing thread does not need to acquire ownership.
  • Locality without permanent arena pinning. Green and Red territories are lazy placement hints. Cold, still-unallocated territory can transfer between threads, while live Black spans remain stable.
  • Fragmentation-aware address index. A concurrent fanout-64 B-Link tree indexes page-granular spans by address. Empty neighboring extents can coalesce without scanning unrelated object lists.
  • Runtime-friendly retention. Recent-span reuse, adaptive magazines, and bounded empty working sets favor short-lived local allocation bursts. Config::runtime_gc() provides a measured opt-in profile; bomalloc itself is not a garbage collector and never moves objects.
  • Native virtual-memory backends. Windows uses VirtualAlloc/VirtualFree; Linux uses mmap/madvise/munmap. Reservation, commitment, discard, and release are tracked separately.
  • Multiple integration surfaces. Use the explicit Rust API, install BoGlobalAllocator with #[global_allocator], or link through the versioned C ABI.
  • Observable internals. Statistics expose live/usable bytes, span colors, contention, topology, and reclamation. Debug validation and Loom models cover the critical ownership and publication protocols.

At a glance

Allocation Current strategy
Small (<= 32 KiB) 24 size classes in aligned 64 KiB spans
Medium Page-granular runs in reusable territories
Large (>= 1 MiB) Dedicated, reusable virtual-memory reservations
Platforms x86-64 Windows and Linux
Rust Edition 2024; stable Rust 1.86 or newer
Integration Explicit API, GlobalAlloc, and prefixed C ABI

Measured performance

The current external benchmark checkpoint shows that the design already has useful specialties, while remaining workload-dependent:

Workload Result
Windows alloc-test 101.88 M operations/s, 2.03x the platform allocator
Windows malloc-large 2.084 s, 2.83x faster than the platform allocator
Linux xmalloc-test 186.49 M frees/s, 1.77x glibc and 4.32x jemalloc, but 46% of mimalloc
Windows Larson 95.78 M operations/s, within 3.8% of the platform allocator
Linux Larson 85.20 M operations/s, within 1.3% of glibc and 14.2% behind jemalloc

These figures are medians from the documented i7-12700K Windows/WSL2 setup, not universal performance claims. Bomalloc still trails leading allocators on some tiny-object paths and often retains more resident memory. See the complete allocator results and runtime-shaped workloads for methodology, memory usage, and limitations.

Project status

Bomalloc 0.3 is experimental software intended for allocator research, benchmarks, runtime prototypes, and non-critical applications. It is heavily tested on its supported platforms but has not received an independent security audit and is not recommended for security-sensitive or high-availability production systems.

The current implementation and remaining boundaries are described in Current design. There is currently no stable standard-library Allocator integration, NUMA or huge-page policy, transparent libc interposition, or production-safety guarantee.

Installation

After publication, add the crate with Cargo:

cargo add bomalloc@0.3

or declare it directly:

[dependencies]
bomalloc = "0.3"

Use as Rust's global allocator

use bomalloc::BoGlobalAllocator;

#[global_allocator]
static GLOBAL: BoGlobalAllocator = BoGlobalAllocator::new();

fn main() {
    let values = (0_u64..100_000).collect::<Vec<_>>();
    println!("{}", values.iter().sum::<u64>());
}

BoGlobalAllocator implements alloc, alloc_zeroed, dealloc, and realloc. Management operations are also available through GLOBAL.stats(), GLOBAL.trim(mode), and GLOBAL.validate().

See Rust global allocator API for initialization, bootstrap, shutdown, and safety details.

Explicit allocation API

use std::alloc::Layout;
use std::ptr::NonNull;

use bomalloc::{BoAllocator, Config, TrimMode};

let allocator = BoAllocator::new(Config::default())?;
let layout = Layout::from_size_align(96, 32)?;
let allocation = allocator.allocate(layout)?;
let pointer = NonNull::new(allocation.as_ptr() as *mut u8).unwrap();

unsafe {
    pointer.as_ptr().write_bytes(0, layout.size());
    allocator.deallocate(pointer, layout);
}

let _ = allocator.trim(TrimMode::Excess);
# Ok::<(), Box<dyn std::error::Error>>(())

For non-zero allocations, the pointer must be released exactly once through the same allocator using its original Layout. The allocator's final handle must not be dropped while its allocations remain live. Zero-sized allocations return an aligned, non-null dangling pointer and deallocation is a no-op.

Thread-local generational runtimes can opt into the measured magazine setting:

use bomalloc::{BoAllocator, Config};

let allocator = BoAllocator::new(Config::runtime_gc())?;
# Ok::<(), bomalloc::BoAllocError>(())

The general default keeps a magazine ceiling of eight. runtime_gc() raises it to sixteen without changing the hot-path instruction layout; it remains opt-in because some burst and remote-release workloads prefer the smaller default.

C and C++ ABI

Release builds produce Rust, dynamic-library, and static-library artifacts. The public header is include/bomalloc.h.

#include "bomalloc.h"

void *buffer = bo_calloc(1024, sizeof(unsigned));
void *grown = bo_realloc(buffer, 8192);
if (grown != NULL) {
    buffer = grown;
}
bo_free(buffer);

The ABI exports prefixed allocation, aligned allocation, reallocation, usable-size, statistics, trimming, and validation functions. It does not interpose libc or the Windows CRT. See C ABI for linking and compatibility contracts.

Design overview

Bomalloc divides reserved address space into page-granular spans indexed by a fanout-64 B-Link tree. Live object addresses never move when ownership or tree topology changes.

The color terminology is relative to a requesting thread:

  • White: completely free public span or extent.
  • Green: unallocated address territory reserved for the current owner.
  • Red: another owner's cold, still-unallocated territory that may transfer.
  • Black: activated storage; a live or leased small span cannot be stolen.

Small allocations use 64 KiB spans and fixed size classes. Their steady same-thread allocation/release path uses a TLS magazine and owner-only overflow without shared atomic metadata access. Foreign releases publish directly to the span's atomic recycled bitmap. Medium objects use page runs; large and over-aligned objects use dedicated virtual-memory reservations.

Tree nodes, span descriptors, bitmaps, and immutable topology payloads are allocator-owned metadata. Concurrent readers use epochs; tree structure changes use helpable descriptors and immutable payload publication. OS resource maintenance—new chunks, decommit, coalescing, and release—remains deliberately serialized.

Memory management and diagnostics

  • TrimMode::Excess performs cooperative normal reclamation.
  • TrimMode::Aggressive invalidates eligible TLS caches and attempts to discard or release every safely free span.
  • StatsSnapshot reports reservation, commitment, live bytes, metadata, span colors, contention, topology, and reclamation counters.
  • validate() checks address partitions, descriptor generations, tree order, live accounting, and free-slot uniqueness in debug/test configurations.

The allocator intentionally retains bounded empty working sets. Reserved virtual address space is not equivalent to committed or resident memory; use the reported counters together with operating-system RSS/commit measurements.

Development checks

cargo fmt --all -- --check
cargo test
cargo clippy --all-targets --all-features -- -D warnings
cargo doc --no-deps --all-features
cargo package

The test suite includes deterministic allocation traces, cross-thread stress, OS backing-store tests, C ABI and global allocator integration, and Loom models for critical atomic protocols. See Documentation index, Contributing, and Release checklist.

License

Licensed under either of

at your option.