frame-alloc

A no_std, dependency-free, const-constructible physical frame allocator library for kernels, written in Rust. Four interchangeable core allocators and three generic composition layers sit behind one public contract, so a kernel can swap the mechanism without changing its call site.

This is the research artifact for the bachelor's thesis "Engineering a Reusable Physical Memory Free List" (Paul Sandner, Technical University of Munich (TUM); supervisor: Marcus Müller). The thesis text is not part of this repository - see Relation to the thesis.

Scope. This is a research artifact, not a production allocator. It is designed for reuse and demonstrated in one integration (a single-core x86-64 QEMU kernel). ARM/RISC-V hosts, a UEFI memory-map path, SMP bring-up, and re-entrancy through a live ISR are untested.

This branch carries the full research artifact: all four core allocators, the controlled alternatives they are compared against, the benchmark harness, and the committed measurement data. The reduced release - the components the evaluation actually recommends keeping (SummaryBuddyAllocator, DepotAllocator, RegionedAllocator) with no benchmark scaffolding - lives on the release branch, which is what any published crate is built from. Start there if you want to use the allocator.

Quick Start

cargo run --example basic          # API tour: const static, holey boot map, alloc/free
cargo test --features stats        # functional correctness (unit + conformance + property)
cd kernel-demo && cargo run        # boot the allocator on bare metal under QEMU

The library itself is no_std and needs no features; stats adds optional diagnostic counters, and --cfg audit compiles in per-operation structural-invariant assertions.

Design

Reading order is from the kernel call site downwards: one public interface, an optional wrapper level, and the core allocators that own the physical span. Every component implements PhysicalAllocator and AllocatorStats. RegionedAllocator is the sole exception to RegionInit, which it replaces with per-region initialization and placement methods. The strategy traits on the right name the architecture- and kernel-specific operations the host supplies.

The public contract

Three roles form the boundary:

Trait	Responsibility
PhysicalAllocator	Transfers ownership. Safe allocate_physical, unsafe exact-match deallocate_physical.
RegionInit	One-time boot-map initialization over a span with holes, plus late in-span donation.
AllocatorStats	Optional, non-linearizable diagnostics (feature stats).

static PHYS: SummaryBuddyAllocator<ORDERS, KernelProv> = SummaryBuddyAllocator::new(BASE);

let usable = [
    PhysRange { base: ram_a, len: len_a },
    PhysRange { base: ram_b, len: len_b },
];

// SAFETY: ranges are owned, mapped by KernelProv, sorted and disjoint;
// initialization is single-threaded and PHYS is published after success.
unsafe { PHYS.try_init(span_base, span_len, &usable)? };

let block = PHYS.allocate_physical(BASE, NonZeroUsize::new(4).unwrap())?;
// SAFETY: exact address, PageSize, and count from the live allocation above.
unsafe { PHYS.deallocate_physical(BASE, NonZeroUsize::new(4).unwrap(), block) };

Reserved gaps between the usable ranges are never handed out. A failed try_init leaves the allocator untouched and retryable; at most one initialization succeeds. See examples/basic.rs for a runnable version of the above.

Core allocators

Four controlled alternatives, kept in one artifact so that later results are attributable to representation and synchronization.

Axis	FreeListAllocator	ListBuddyAllocator	BitmapBuddyAllocator	SummaryBuddyAllocator
Request sizing	Exact	Power-of-two rounded	Power-of-two rounded	Power-of-two rounded
Authoritative state	Ordered runs	Per-order lists	Per-order L1 bits	Per-order L1 bits
Metadata	Headers in free runs	Headers in free blocks	In-pool bitmap	In-pool L1 + summary bits
Synchronization	One lock	Per-order locks	CAS loops	CAS loops
Search / merge	O(r) search and insertion	Head removal; merge list scan	L1 word scan	Count + summary, L1 fallback
Main structural cost	Long fragmented lists	Rounding and merge scan	Span-width bitmap and scan	Extra shared hints/counts

The CAS backends are lock-free at the data-structure level but neither contention-free nor wait-free: a bounded operation may still return a spurious OutOfMemory after the documented retry policy, which the contract explicitly permits.

Composition wrappers

Wrappers implement PhysicalAllocator themselves and require only the same trait from their backend, so stacks compose statically over any core - including foreign allocators placed behind the trait by an adapter.

• MagazineAllocator - per-CPU LIFO magazines (SLOTS cache-line-padded slots of CAP frames, selected by CpuId). Caches single base frames only; refills in batches from the backend and steals from siblings on local exhaustion.
• DepotAllocator - magazine plus a shared depot tier that absorbs overflow, so frames freed on one CPU can be reused on another without a backend round-trip.
• RegionedAllocator - routes among several independent backends. Allocation starts at the calling CPU's home region and falls back; deallocation and donation route by physical address. alloc_in_region / alloc_in_chain expose explicit placement. Each region is its own contiguity domain, so aggregate free capacity does not imply a matching largest request.

Convenience aliases RegionedMagazine and RegionedDepot are exported for stacking of wrapper tiers.

Host strategies

Three traits inject what the library cannot define portably:

• Provenance - turns a physical address into a pointer usable for metadata access. The in-pool-metadata backends need this; a kernel supplies a direct-map translation that creates a real allocation rather than casting a bare integer.
• InterruptControl - local interrupt save/restore, making the magazine's lock IRQ-safe.
• CpuId - a locality hint for magazine slot and home-region selection.

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

Kernel Integration

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

See kernel-demo/README.md for the glue code walkthrough, build requirements, and captured boot output.

Validation

The crate uses interior mutability over raw pool bytes - bitmap words are pool memory reinterpreted as AtomicUsize, list backends write into free frames and cross the integer-to-pointer boundary. Rust's type system does not prove that sound, and the x86-64 development host hides ordering bugs a weaker memory model would expose. No single tool covers both gaps, so the artifact is exercised by a stack of layers with different blind spots:

Layer	What it checks	Main blind spot
White-box unit tests	Algorithm edge cases, invalid input, summary consistency, wrapper mechanics	Limited tested states
Black-box conformance	One public contract over four backends and five compositions	Small concrete pools
Occupancy oracle	No aliasing, in-range, alignment, conservation over randomized traces	Finite seeds; power-of-two requests; sequential
Threaded stress	Duplicate/loss freedom, lock and LIFO behaviour under contention	Schedule sampling only
ThreadSanitizer	Data races in executed real-code paths	Cannot flag synchronized-but-wrong protocols
Miri	UB, bounds, alignment, provenance; weak-memory executions over seeded schedules	Curated subset; finite executions; harness provenance
Audit mode	Structural invariants after every sequential operation	Concurrent transient states excluded

All of it is driven by scripts/verify.sh:

./scripts/verify.sh                  # every layer
./scripts/verify.sh miri-concurrent  # one layer: tests | tsan | miri | miri-concurrent | audit

The TSan, Miri, and Miri-concurrent layers need a nightly toolchain (rust-src, miri components). miri-concurrent replays the threaded tests across 16 scheduler seeds under weak-memory emulation and takes several minutes - it is the only layer that can surface a wrong atomic ordering. .github/workflows/ci.yml runs the same layers plus fmt/clippy and a default-feature build.

The term used throughout is validation, not verification: every layer observes executed or sampled states. Symbolic proof and exhaustive model checking are out of scope.

Benchmarks

Twelve benchmark binaries drive the allocators through controlled microbenchmarks, phased multi-tenant workloads, fragmentation scenarios, and a deterministic footprint report. External baselines (buddy_system_allocator, rlsf TLSF, and LLFree) are placed behind the same trait so mechanism comparisons are like-for-like.

Committed results live in benches/data/ as {machine}.csv alongside a .log and a .meta.json provenance sidecar that records the commit, toolchain, full CPU topology, and every environment knob of that run, so any figure in the thesis can be traced to a re-runnable configuration.

See benches/README.md for what each benchmark measures, how to run it, the data layout, and the host methodology.

Repository Layout

src/                    the library
  allocator.rs            PhysicalAllocator / RegionInit / AllocatorStats contracts
  implementations/        four core allocators
  implementations/wrappers/  magazine, depot, regioned
  strategies/             Provenance, InterruptControl, CpuId
  util/                   LIFO, IRQ-saving lock, cache padding
  tests/                  white-box unit tests (in-crate)
tests/                  black-box suites (link the crate as a downstream dependency)
examples/basic.rs       runnable API tour
benches/                benchmark binaries, shared harness, and committed data
kernel-demo/            bare-metal QEMU kernel (separate crate)
scripts/                verify.sh (validation layers), capture_meta.py (run provenance)
docs/                   figures used by this README

Reproducibility

Raw measurements are reproducible from this repository, the plots are not. Figures in the thesis are generated out of tree from the committed CSVs, those plotting scripts are not part of this artifact. What is here is the complete input side: the benchmark sources, the harness, the committed CSV/log/meta triples, and scripts/capture_meta.py, which regenerates a provenance sidecar for any new run.

Relation to the Thesis

The thesis is not distributed in this repository. Where its claims are grounded here:

Research question	Evidence in this repository
RQ1 - how the public interface should divide safe/unsafe responsibility, express initialization and ownership contracts, and isolate host-specific behaviour	src/allocator.rs, src/strategies/, examples/basic.rs, tests/conformance.rs, kernel-demo/
RQ2 - how the mechanisms trade off throughput, latency, metadata cost, capacity, and contiguity, and which configuration is a defensible release choice	benches/ and the committed data in benches/data/
RQ3 - what evidence supports confidence in the unsafe concurrent implementation, and what risks remain	scripts/verify.sh, src/tests/, tests/, .github/workflows/ci.yml

The reduced release recommendation is SummaryBuddyAllocator as the core, DepotAllocator as an optional cache tier, and RegionedAllocator as a situational sharding or placement layer - available components with conditional guidance, not one stack that should always be enabled.

License

MIT - see LICENSE. The benchmark dev-dependencies (buddy_system_allocator, rlsf, llfree) are separately licensed by their authors and are not part of the library.