frame-alloc

A physical frame allocator for kernels: no_std, no runtime dependencies, and const-constructible so it lives in a static with no heap and no runtime initializer.

You give it a boot memory map. It hands out physically contiguous, naturally aligned runs of frames and takes them back.

[dependencies]
frame-alloc = "0.1"

Quick Start

use core::num::NonZeroUsize;
use frame_alloc::{PageSize, PhysRange, PhysicalAllocator, RegionInit, SummaryBuddyAllocator};

const BASE: PageSize = PageSize::from_log2(12); // 4 KiB base frame
const ORDERS: usize = 11;                       // orders 0..10, i.e. up to 4 MiB blocks

// No heap, no lazy_static, no runtime initializer.
static PHYS: SummaryBuddyAllocator<ORDERS, KernelProv> = SummaryBuddyAllocator::new(BASE);

fn boot(span_base: usize, span_len: usize, usable: &[PhysRange]) {
    // SAFETY: the usable ranges are owned by us and mapped by KernelProv; they are
    // sorted, disjoint, base-frame aligned, and inside the span. This runs once,
    // single-threaded, and PHYS is published to other CPUs only after it succeeds.
    unsafe { PHYS.init(span_base, span_len, usable) };
}

fn use_frames() -> Result<(), frame_alloc::AllocError> {
    let four = NonZeroUsize::new(4).unwrap();
    let block = PHYS.allocate_physical(BASE, four)?; // 4 contiguous frames, 16 KiB-aligned

    // SAFETY: exact address, page size, and count from the allocation above,
    // and the block is not used after this point.
    unsafe { PHYS.deallocate_physical(BASE, four, block) };
    Ok(())
}

Gaps between the usable ranges are reserved forever — the allocator never hands out a frame you did not give it. Allocation is safe; deallocation is unsafe because the allocator cannot verify that the address, page size, and count match a live allocation.

A runnable version of the above, with a holey boot map and heap memory standing in for physical RAM, is in examples/basic.rs:

cargo run --example basic
cargo run --example basic --features stats   # …with utilisation readouts

What You Have To Provide

The crate is architecture-neutral, not architecture-independent. Three traits inject the things a library cannot define portably:

NoCpuId and NoInterruptControl are supplied for uniprocessor or interrupt-free hosts.

Provenance is the one to get right. SummaryBuddyAllocator stores its bitmap inside the managed pool, so it must reach that memory through a pointer. Producing one with a bare addr as *mut u8 is unsound. Your create should establish provenance the way your kernel actually maps the frame — the demo kernel does it with an inline-asm block that is a runtime no-op but opaque to the compiler. destroy ends that allocation before a frame is handed to a caller, so the recipient's own pointer cannot alias the allocator's.

Components

Everything below implements PhysicalAllocator, so the wrappers compose over the core — or over your own allocator, if you implement the trait yourself.

SummaryBuddyAllocator<ORDERS, P, G = DefaultGates> — the core. A buddy allocator whose authoritative state is a per-order bitmap kept in the pool, with a summary layer above it so a scan skips empty regions instead of walking every word. Synchronization is CAS loops, not a lock. Requests round up to a power of two; a request is bounded by ORDERS and by max_page.

It is lock-free at the data-structure level, but not contention-free and not wait-free: under concurrent load allocate_physical may return AllocError::OutOfMemory spuriously, after the bounded internal retries, while memory is in fact available. Callers that must not fail early should retry.

DepotAllocator<A, S, SLOTS, CAP = 128, DEPOT_CAP = 512, I = NoInterruptControl> — a two-level per-CPU cache over any backend A. Each of the SLOTS magazines is a cache-line padded LIFO of up to CAP single frames; overflow spills into a shared depot of DEPOT_CAP, so a frame freed on one CPU can be reused on another without touching the backend. Only single-frame requests are cached — multi-frame requests pass straight through. Set SLOTS to the number of CPUs that may ever be online, not the current count; it is a const generic.

RegionedAllocator<REGIONS, A, S = NoCpuId> — routes among several independent backends, each owning a disjoint span. Allocation starts at the calling CPU's home region and falls back across the others; deallocation and donation route by physical address, not by calling CPU. alloc_in_region and alloc_in_chain give you explicit placement for zone- or NUMA-style policies. It replaces RegionInit with init_at for per-region setup.

Note that each region is its own contiguity domain: no allocation can span two regions, so total free capacity does not imply a request that large will succeed.

Composing them is ordinary type nesting:

// Per-CPU cached, IRQ-safe, over the summary buddy.
static PHYS: DepotAllocator<SummaryBuddyAllocator<ORDERS, KernelProv>, KernelCpu, 64, 128, 512, X86Irq> =
    DepotAllocator::new(BASE, SummaryBuddyAllocator::new(BASE));

Features

• stats — adds the AllocatorStats accessors (total_bytes, free_bytes, largest_free_bytes). Diagnostic only: the values are not linearizable under concurrency.
• --cfg audit — a build-time flag, not a feature. Compiles in structural-invariant assertions that run after every allocation and free. Far too slow for production; useful when porting or when you suspect the allocator.

Running On Real Hardware

kernel-demo/ is a minimal x86-64 kernel that boots this allocator under QEMU: a real BIOS memory map, a higher-half direct map, a static SummaryBuddyAllocator with a DepotAllocator over it, and a pushfq; cli interrupt strategy. It allocates, writes through a frame, frees, and prints utilisation over the serial port.

Its README walks through the glue code — it is the shortest path to seeing what integration actually requires. The demo is not part of the published crate; clone the repository to run it.

Correctness

The crate reinterprets pool bytes as AtomicUsize and crosses the integer-to-pointer boundary through Provenance, so the type system does not establish its soundness. It is checked by layers with different blind spots, driven by scripts/verify.sh:

./scripts/verify.sh                  # all layers
./scripts/verify.sh miri-concurrent  # one: tests | tsan | miri | miri-concurrent | audit
./scripts/verify.sh --log            # archive each layer to validation/<layer>.log

Unit and black-box conformance tests, a randomized occupancy oracle, threaded stress tests, ThreadSanitizer, Miri for UB and provenance, Miri again over 16 scheduler seeds with weak-memory emulation, and audit mode. The nightly layers need rust-src and miri. CI runs all of them.

This is validation, not proof: every layer observes executed states. Symbolic verification and exhaustive model checking were not done.

Status

Version 0.1. The API is not yet stable.

Known limits, stated plainly: the allocator is concurrency-safe and has been exercised under TSan and Miri, but it has been integrated into exactly one kernel — single-core, x86-64, BIOS boot. SMP bring-up, re-entrancy through a live interrupt handler, ARM and RISC-V hosts, and a UEFI memory-map path are untested. RegionedAllocator does no distance modelling, migration, or balancing, and its address-to-region lookup is linear — it is a placement mechanism, not a NUMA policy.

Background

This crate is the release artifact of a bachelor's thesis, Engineering a Reusable Physical Memory Free List (Paul Sandner, Technical University of Munich; supervisor: Marcus Müller). The components here are the ones its evaluation recommends keeping.

The master branch carries the full research artifact: four interchangeable core allocators instead of one, the external allocators they were measured against, the benchmark harness, and the committed measurement data. Go there if you want the comparison, the methodology, or the numbers.

License

MIT — see LICENSE.