bomalloc 0.3.1

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

[![Crates.io](https://img.shields.io/crates/v/bomalloc.svg)](https://crates.io/crates/bomalloc)
[![Documentation](https://docs.rs/bomalloc/badge.svg)](https://docs.rs/bomalloc)
[![MSRV](https://img.shields.io/badge/MSRV-1.86-blue.svg)](https://www.rust-lang.org)
[![License](https://img.shields.io/crates/l/bomalloc.svg)](LICENSE-MIT)

> 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](docs/mature-benchmark-results.md) and
[runtime-shaped workloads](docs/runtime-workload-results.md) 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](docs/design-status.md). 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:

```text
cargo add bomalloc@0.3
```

or declare it directly:

```toml
[dependencies]
bomalloc = "0.3"
```

## Use as Rust's global allocator

```rust
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](docs/global-allocator-api.md) for initialization,
bootstrap, shutdown, and safety details.

## Explicit allocation API

```rust
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:

```rust
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).

```c
#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](docs/c-abi.md) 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

```text
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](docs/README.md),
[Contributing](CONTRIBUTING.md), and [Release checklist](RELEASING.md).

## License

Licensed under either of

- Apache License, Version 2.0 ([LICENSE-APACHE]LICENSE-APACHE); or
- MIT license ([LICENSE-MIT]LICENSE-MIT)

at your option.