cadalloc 0.1.0

A minimal, configurable, embeddable allocator with segregated free lists for multithreaded environments
Documentation
  • Coverage
  • 100%
    93 out of 93 items documented7 out of 70 items with examples
  • Size
  • Source code size: 154.0 kB This is the summed size of all the files inside the crates.io package for this release.
  • Documentation size: 685.6 kB This is the summed size of all files generated by rustdoc for all configured targets
  • Ø build duration
  • this release: 2s Average build duration of successful builds.
  • all releases: 2s Average build duration of successful builds in releases after 2024-10-23.
  • Links
  • williamwutq/cadalloc
    0 0 0
  • crates.io
  • Dependencies
  • Versions
  • Owners
  • williamwutq

cadalloc

A minimal, configurable, embeddable allocator with segregated free lists — built for managing a fixed region of memory from many threads.

cadalloc is #![no_std], assumes a 64-bit target, and hands out Slices ({ ptr: u64, len: u64 }) rather than raw pointers. It coordinates its size-class free lists with atomics inside the managed heap, so it needs no global allocator, no thread-local state, and no dependencies.

License: MIT Crates.io Docs.rs

Status: experimental (0.1). The API is not yet stable. Read the tradeoffs below before depending on it.

Is this the allocator you want?

cadalloc is deliberately narrow. It is a good fit when all of these hold:

  • You own a single, fixed region of memory to sub-allocate — a static buffer, an mmap, a device/shared-memory window, a VM/interpreter heap — and its size is known up front.
  • You address that memory by (base, len) as plain u64s — a length beside every address, independent of the host pointer type. This is the natural way to hand out real addresses into a fixed embedded/bare-metal RAM or MMIO region, and it works just as well when the region is not in the allocating CPU's own address space at all — a GPU/device buffer, a shared-memory arena between processes, or a WASM-style linear memory.
  • The workload's allocation sizes are reasonably homogeneous / bounded, or churn is high enough that freed blocks get reused at the same sizes.
  • You need it to be no_std, small, or dependency-free.

It is not a general-purpose malloc replacement:

  • It never coalesces free blocks. Blocks are class-exact and are returned to their size-class free list on free; adjacent free blocks are never merged. This keeps the hot path short and predictable, but means fragmentation is permanent: memory freed at one size class cannot later satisfy a larger class. Under a long-lived, heterogeneous workload it will strand memory. Under a fixed-heap workload with bounded sizes — the target — it is fast and stable.
  • Growing a block via realloc always relocates (allocate + copy + free), precisely because there is no coalescing.
  • The optional #[global_allocator] support is limited. There is a GlobalAlloc impl behind the alloc feature (see As the global allocator), but it inherits the two points above and can only satisfy alignments up to MIN_ALIGN — so it fits a fixed-heap program, not arbitrary malloc traffic. The unstable core::alloc::Allocator trait is not implemented.

If you want a general heap allocator with coalescing, reach for talc, linked_list_allocator, buddy_system_allocator, or rlsf instead. cadalloc trades generality for a tiny, offset-addressed core.

Design at a glance

  • Segregated free lists. Size classes are computed at compile time from four power-of-two constants: a linear region (step MIN_ALIGN), an exponential region (each octave split in two), and one oversized bin above EXP_CEIL.
  • Lock-free bins + one refill lock. Each fixed size class is a lock-free Treiber stack (with a low-bit ABA tag); the bump pointer, the oversized list, and block splitting run under a single spinlock. There are no thread-local caches — one shared set of bins, kept simple.
  • One-word headers, no footer. Every block starts with a single u64 packing its size and a free bit (the low alignment bits are always zero, so no shifting). No footers, no coalescing metadata.
  • Configuration fingerprint. An initialized heap is stamped with a "CADALLOC" marker and a 64-bit fingerprint of the layout constants; verify rejects a heap laid out by a different configuration before it can corrupt anything — useful for persistent or shared-memory regions.

Installation

[dependencies]
cadalloc = "0.1"

# Or, to also use it as the program's `#[global_allocator]`:
# cadalloc = { version = "0.1", features = ["alloc"] }

Configuring an allocator

The whole configuration surface is one trait, Config: name an atomics backend and the four size-class constants (heap region optional at compile time).

use cadalloc::{Config, CoreAtomics};

struct MyConfig;

impl Config for MyConfig {
    type Atomics = CoreAtomics;

    const MIN_ALIGN: u64 = 16;    // min alignment & linear class step
    const LNR_FLOOR: u64 = 32;    // smallest class (>= 2 * MIN_ALIGN)
    const EXP_FLOOR: u64 = 256;   // linear -> exponential boundary
    const EXP_CEIL: u64 = 65536;  // largest class; above spills oversized

    const HEAP_BASE: u64 = 0x2000_0000; // a real, mapped region
    const HEAP_SIZE: u64 = 1 << 20;     // 1 MiB
}

// Optional but recommended: validate the constants at compile time.
const _: () = cadalloc::assert_config_valid::<MyConfig>();

When the region is only known at runtime, leave HEAP_BASE/HEAP_SIZE at their defaults and override the heap_base() / heap_size() methods instead.

Usage

use cadalloc::{CadAlloc, Config, CoreAtomics};

# struct MyConfig;
# impl Config for MyConfig {
#     type Atomics = CoreAtomics;
#     const MIN_ALIGN: u64 = 16;
#     const LNR_FLOOR: u64 = 32;
#     const EXP_FLOOR: u64 = 256;
#     const EXP_CEIL: u64 = 65536;
#     const HEAP_BASE: u64 = 0x2000_0000;
#     const HEAP_SIZE: u64 = 1 << 20;
# }
let a = CadAlloc::<MyConfig>::new();
a.init().expect("prepare the heap");   // once, before any allocation
assert!(a.verify().is_ok());           // marker + config fingerprint

let s = a.alloc(100);                  // Slice { ptr, len }; len may exceed 100
if !s.is_null() {
    // ... use the region [s.ptr, s.ptr + s.len) ...
    let s = a.realloc(s, 4000);        // grow (relocates) or shrink in place
    a.free(s);
}

The CadAlloc handle is zero-sized — all state lives in the heap — so it can be reconstructed anywhere (e.g. a static) and shared across threads once init has run.

Exporting to C

export_c_api! emits unmangled extern "C" shims bound to one configuration:

# use cadalloc::{Config, CoreAtomics};
# struct MyConfig;
# impl Config for MyConfig {
#     type Atomics = CoreAtomics;
#     const MIN_ALIGN: u64 = 16;
#     const LNR_FLOOR: u64 = 32;
#     const EXP_FLOOR: u64 = 256;
#     const EXP_CEIL: u64 = 65536;
#     const HEAP_BASE: u64 = 0x2000_0000;
#     const HEAP_SIZE: u64 = 1 << 20;
# }
cadalloc::export_c_api! {
    config: MyConfig,
    init: cad_init,
    alloc: cad_alloc,
    realloc: cad_realloc,
    free: cad_free,
    verify: cad_verify,
}

Slice is #[repr(C)] (struct { uint64_t ptr, len; }), passed and returned by value. See the ffi module docs for the ABI and status codes.

As the global allocator

With the alloc feature, a configuration can back the alloc crate:

#[global_allocator]
static GLOBAL: cadalloc::CadAlloc<MyConfig> = cadalloc::CadAlloc::new();

fn main() {
    GLOBAL.init().expect("prepare the heap"); // before the first allocation
    // `Box`, `Vec`, ... now allocate from the fixed heap.
}

Two caveats (see the global module docs): init() must run before anything allocates — there is no lazy initialization — and only alignments up to MIN_ALIGN can be satisfied; a stronger request returns null, which the alloc crate turns into an allocation-error abort.

Two region types

Following C++'s string / string_view, memory is described by two types:

  • Slice — an owning handle to an allocation, returned by alloc and consumed by free/realloc. It is move-only (not Copy/Clone), so the compiler rules out double frees and use-after-free through the handle: once you pass a Slice to free, you cannot name it again.
  • SliceView<'a> — a cheap, Copy non-owning view, borrowed for 'a. It carries the inspection and sub-region operations (subslice, split_at, contains, as_bytes, …). Borrow an owner as one with slice.view(); the view — and any &'a [u8] taken from it — is tied to that borrow, so the owner cannot be freed while a view of it is alive.

Safety

  • Constructing either type from a raw address is unsafe. Slice::new / SliceView::new assert that the address really names owned memory (and, for a view, that it lives for the chosen 'a) — you only reach for them to reconstruct an address you already own, e.g. across FFI. Handles from alloc and views from slice.view() need no unsafe.
  • Double-free detection is best-effort and debug-only. The move-only Slice makes an honest double free a compile error; the runtime guard exists for the FFI path, where a caller can fabricate a second handle. free refuses a block already marked free (and asserts in debug builds), but release builds do not defend against every misuse.

Concurrency testing

Because the bins are lock-free, serial tests can't establish correctness. Two layers guard it:

  • A multithreaded stress test (cargo test) hammers one heap from many threads doing alloc/free/realloc churn, fingerprinting every live block so any overlap or lost/duplicated free is caught as corruption.

  • A loom model check exhaustively explores thread interleavings and memory orderings for the isolated Treiber-stack push/pop protocol (including its ABA tag). Run it with:

    RUSTFLAGS="--cfg loom" cargo test --lib treiber
    

    loom is a dev-dependency only under --cfg loom; a normal cargo test never compiles or downloads it. Loom cannot model the whole allocator (a real heap is far too many atomic locations, and it addresses memory by raw u64), so it targets the one genuinely subtle lock-free component while the stress test exercises the whole thing.

Development

cargo test                                            # unit + stress + doctests
cargo test --features alloc                           # + the GlobalAlloc adapter
cargo clippy --all-targets --all-features -- -D warnings   # what CI gates on
cargo fmt --check
cargo doc --no-deps --all-features --open
cargo build --target thumbv7em-none-eabihf            # bare-metal smoke build
RUSTFLAGS="--cfg loom" cargo test --lib treiber       # loom model check

CI runs on master and main: ci.yml tests the stable/beta/nightly × Linux/macOS/Windows matrix, and check.yml gates clippy, formatting, and docs.

See PLANNED.md for the design surface and CHANGELOG.md for changes.

License

MIT — see LICENSE.