bomalloc 0.3.1

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

Date: 2026-08-15

Release target: bomalloc 0.3.1

Status: implemented and runtime-tested on x86-64 Windows and Linux; experimental

This document describes the current allocator. Historical optimization
checkpoints and superseded designs are intentionally excluded from the release
documentation.

## Public integration surfaces

Bomalloc exposes three supported entry points:

- `BoAllocator`, an explicit allocator with `allocate`, unsafe `deallocate`,
  `trim`, `stats`, and `validate` operations;
- `BoGlobalAllocator`, a stable `GlobalAlloc` adapter suitable for
  `#[global_allocator]`;
- a versioned C ABI whose exported names use the `bo_` prefix.

The unstable standard-library `Allocator` trait is not implemented. The crate
does not transparently interpose the C runtime allocator.

## Address-space model

The allocator reserves memory in 16 MiB chunks. Every chunk is represented by a
complete, non-overlapping partition of page-granular spans. A span descriptor has
one of these logical kinds:

- `Free`: unallocated extent;
- `ReservedSmall`: owner-ranked, uncommitted small-object territory;
- `Small`: activated 64 KiB size-class span;
- `ReservedRun`: lazily activated page-run territory;
- `Run`: active medium allocation territory;
- `Dedicated`: standalone large or over-aligned reservation;
- `Retired`: logically removed metadata awaiting safe reclamation.

The fixed size classes are:

```text
8, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512,
768, 1024, 1536, 2048, 3072, 4096, 6144, 8192,
12288, 16384, 24576, 32768
```

Small allocations are at most 32 KiB with alignment at most 4 KiB. Allocations
at or above 1 MiB use dedicated reservations; other objects use page runs.
Live object addresses never move during span transfer, tree split, merge, trim,
or metadata reclamation.

## Ownership and colors

Colors describe an allocation candidate relative to the requesting thread; they
are not stored as an independent safety state:

- **White**: completely free public territory.
- **Green**: unallocated territory ranked for the current owner.
- **Red**: another owner's cold, still-unallocated territory that may transfer.
- **Black**: activated storage. A small span containing a live object or an
  owner lease cannot transfer.

Owner identity is a placement and reuse hint, not an object-access boundary.
Objects may be released by threads other than their allocator. Red transfer only
changes ownership of future allocation capacity; it never cuts or moves live
objects.

The optional conflict-driven random traversal and Young Ring mechanisms remain
implemented and observable, but both default to disabled because current
cross-platform measurements do not justify charging the general path.

## Small-object path

Each active size class has bounded TLS state:

- a current span and recent-span ring;
- an adaptive inline magazine;
- an owner-only intrusive overflow chain;
- bounded hints for recycled bitmap words and low-capacity classes.

The magazine learns a target of `1 -> 2 -> 4 -> 8` under the default
configuration. `Config::runtime_gc()` changes only the upper bound to sixteen.
Magazine blocks are removed from the shared bitmap and protected by a persistent
span lease.

An exact same-thread magazine or overflow hit performs no shared atomic metadata
operation. Allocation from the leased span continues through its bump frontier
or recycled bitmap without re-entering the packed control word. Local live-byte
changes accumulate in TLS and synchronize at refill, statistics, validation, or
lease release boundaries.

Cross-thread release does not require ownership transfer. It publishes the block
to an out-of-band atomic bitmap and updates a disjoint remote accounting channel.
The bitmap avoids storing a concurrently readable Treiber-stack link inside a
block that may already have returned to user code.

An activated small span is frozen before trim, retirement, or ownership change.
Freeze excludes new operations, waits for already admitted operations and leases,
and revalidates the live count before decommit or structural reuse.

## Medium and large allocations

Medium allocations use fixed-stride page runs inside stable run territories.
Windows can batch virgin run slots in an owner-local TLS window to amortize page
commit; Linux leaves that window disabled by default because its demand-paged
mapping makes logical commit syscall-free.

Large and over-aligned allocations use dedicated reservations. Their allocation
header records the original reservation so an aligned interior address can be
returned safely. Empty reservations use smallest-compatible reuse and a bounded
committed-content budget before older pages are discarded.

## Address tree and metadata

Spans are indexed by a fanout-64 B-Link tree. Nodes have high keys, right links,
parent hints, versions, and immutable payloads. A search that encounters a stale
parent separator follows the right chain until the key is in range.

Structural operations publish helpable operation descriptors. The supported
transactions include leaf/internal split, parent insertion, logical removal,
redirect, internal merge or redistribution, root replacement, and root collapse.
Once a sibling link or redirect is visible, helpers complete the forward-only
operation rather than rolling it back.

Tree nodes, span descriptors, bitmap storage, and persistent immutable arrays use
allocator-owned virtual-memory slabs. Concurrent readers pin the allocator's
private epoch collector before dereferencing reclaimable tree state. Detached
metadata is reused only after its epoch grace period and generation change.

## Maintenance and operating-system backing

Windows reserves address space and commits pages with `VirtualAlloc`; trim can
discard or decommit eligible pages, and only a completely empty chunk is released
with `VirtualFree`. Linux uses anonymous `MAP_NORESERVE` mappings. First touch
supplies physical pages, while `MADV_DONTNEED` discards contents and preserves
zero-filled reuse.

Ordinary cached small allocation/release, cross-thread release, exact tree
lookup, reserved activation, and most span/run growth do not acquire a global
topology lock. A maintenance lock and packed admission gate deliberately
serialize operations that change OS resource ownership:

- new chunk insertion;
- coalescing and structural cleanup associated with trim;
- page discard/decommit;
- complete chunk release;
- full debug validation.

The allocator therefore makes a narrow lock-free claim for normal small-object
operations and helpable tree progress, not a whole-allocator or OS-level
lock-free claim.

## Reclamation and trimming

Normal release updates span-local state and leaves structural cleanup to a later
slow path or explicit trim. Maintenance is cooperative; no allocator background
thread is created.

- `TrimMode::Excess` retains bounded thread working sets.
- `TrimMode::Aggressive` advances a global trim epoch so TLS caches invalidate
  at their next allocator boundary and attempts to reclaim every safely free
  span.
- Adjacent White extents may coalesce.
- A live Black span is never cut for coalescing.
- A chunk is released only after every span is empty, active operations and
  leases have drained, and retired metadata has passed its epoch grace period.

## Correctness evidence

The current test gates cover:

- every size-class boundary, alignment, zero-size, page-run, dedicated, and
  over-aligned path;
- deterministic mixed allocation traces with overlap and partition checks;
- cross-thread producer/consumer release and high-contention ownership traffic;
- thread exit, cache flushing, aggressive trim, descriptor reuse, and chunk
  reclamation;
- C ABI and process-global allocator integration;
- Loom models for bitmap publication, accounting, freeze, leases, owner transfer,
  run claims, tree descriptors, redirects, root changes, and epoch reuse;
- native Windows and Linux execution, Clippy, strict rustdoc, and tests executed
  from the packaged crate archive.

This is substantial regression evidence, not a formal proof or an independent
security audit.

## Current limitations

- Only x86-64 Windows and Linux are supported.
- The caller must use the original allocator and layout and release each non-zero
  allocation exactly once.
- The final allocator handle must outlive all of its allocations.
- No NUMA policy, huge-page policy, object movement, stable `Allocator` trait,
  or transparent libc interposition is provided.
- OS allocation calls and maintenance are outside the user-space lock-free
  progress guarantee.
- Performance is workload-dependent; the allocator is not uniformly faster than
  jemalloc, mimalloc, or the platform allocator.
- Bomalloc remains experimental and is not production-certified.