# 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.
```toml
[dependencies]
frame-alloc = "0.1"
```
## Quick Start
```rust
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`](https://github.com/PaulSandner/frame_alloc/blob/release/examples/basic.rs):
```bash
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:
| `Provenance` | Turn a physical address into a `NonNull<u8>` your kernel can dereference — typically a direct-map offset | Always: the allocator keeps its metadata in the pool |
| `CpuId` | `current_cpu() -> usize` | Per-CPU caching and region selection |
| `InterruptControl` | Local interrupt save/restore | Making the cache tier's lock IRQ-safe |
`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:
```rust
// 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/`](https://github.com/PaulSandner/frame_alloc/tree/release/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](https://github.com/PaulSandner/frame_alloc/blob/release/kernel-demo/README.md)
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`:
```bash
./scripts/verify.sh # all layers
```
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`](https://github.com/PaulSandner/frame_alloc) 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](https://github.com/PaulSandner/frame_alloc/blob/release/LICENSE).