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.
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 plainu64s — 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
reallocalways relocates (allocate + copy + free), precisely because there is no coalescing. - The optional
#[global_allocator]support is limited. There is aGlobalAllocimpl behind theallocfeature (see As the global allocator), but it inherits the two points above and can only satisfy alignments up toMIN_ALIGN— so it fits a fixed-heap program, not arbitrarymalloctraffic. The unstablecore::alloc::Allocatortrait 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 aboveEXP_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
u64packing 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;verifyrejects a heap laid out by a different configuration before it can corrupt anything — useful for persistent or shared-memory regions.
Installation
[]
= "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 ;
;
// Optional but recommended: validate the constants at compile time.
const _: = ;
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 ;
# ;
#
let a = new;
a.init.expect; // once, before any allocation
assert!; // marker + config fingerprint
let s = a.alloc; // Slice { ptr, len }; len may exceed 100
if !s.is_null
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 ;
# ;
#
export_c_api!
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:
static GLOBAL: CadAlloc = new;
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 byallocand consumed byfree/realloc. It is move-only (notCopy/Clone), so the compiler rules out double frees and use-after-free through the handle: once you pass aSlicetofree, you cannot name it again.SliceView<'a>— a cheap,Copynon-owning view, borrowed for'a. It carries the inspection and sub-region operations (subslice,split_at,contains,as_bytes, …). Borrow an owner as one withslice.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::newassert 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 fromallocand views fromslice.view()need nounsafe. - Double-free detection is best-effort and debug-only. The move-only
Slicemakes an honest double free a compile error; the runtime guard exists for the FFI path, where a caller can fabricate a second handle.freerefuses 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
loommodel 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"loomis a dev-dependency only under--cfg loom; a normalcargo testnever compiles or downloads it. Loom cannot model the whole allocator (a real heap is far too many atomic locations, and it addresses memory by rawu64), so it targets the one genuinely subtle lock-free component while the stress test exercises the whole thing.
Development
RUSTFLAGS="--cfg loom"
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.