A Heap Allocator: Teaching the Kernel to Manage Its Own Memory
Write a bump allocator and then a free-list allocator from scratch in C for your AArch64 bare-metal kernel. Learn block headers, first-fit search, coalescing, alignment, and why Rust's no_std offers a safer alternative. Visualize every allocation interactively.
The kernel can speak. It maps memory. It handles exceptions and responds to a timer interrupt. What it still cannot do is manage its own memory at runtime. Every array, every buffer, and every future data structure in this kernel is statically sized and allocated at compile time. That has worked until now, but it won’t for much longer.
In the next phase of this series, we will build processes, a scheduler and a filesystem that all require the kernel to allocate and free memory dynamically. A process control block is created when a process is created and destroyed when it exits. A filesystem node gets allocated when you create a file and freed when you delete it. None of that is possible without a heap.
Earlier in the series, when we optimised the linker file and did the memory layout, we set up for
this post. The linker script reserved 1 MB of space between __heap_start and __heap_end, right
above the stack. The symbols are there, the memory is waiting. We just need to write the code
that manages it.
In this post, we will build two allocators: a bump allocator (fast, simple, but unable to free
individual blocks) and a free-list allocator (what a real malloc looks like). At the end, we’ll
look at how Rust’s no_std approach handles the same problem and why it catches an entire class
of bugs at compile time that C cannot.
What We’re Building Today
The end result of this post is a working kmalloc / kfree pair that the kernel can call from anywhere.
By the end of this post, kernel/main.c will allocate several objects, print their addresses, free
some of them, and allocate again. Doing this isn’t really functional; it merely demonstrates that
the heap is actually tracking the state.
We’ll start with the bump allocator because it’s the fastest path to a working kmalloc. Then we’ll
replace it with a free-list allocator because the bump allocator can’t survive a real workload. The
two implementations share the same header, so swapping them is a one-line change.
Here’s where the heap lives relative to everything else in the physical address space after this post:
The heap sits immediately above the stack, starting at the address the linker exported as __heap_start.
That separation between stack and heap isn’t accidental: the stack grows downward, the heap grows upward,
and the 1 MB gap between the top of the stack and __heap_end is the allocator’s entire budget. Go over it,
and kmalloc returns NULL. That’s our OOM signal; no exceptions, no panic, just a NULL check.
The Bump Allocator
The bump allocator is the simplest allocator imaginable. It maintains a single pointer that starts
at __heap_start and advances each time you allocate. There’s no tracking structure, no free list,
no bookkeeping overhead; just a pointer and a bounds check.
The Header
This header file will keep both allocator phases behind the same interface. The first implementation we will add is the bump allocator. Later in this post, we’ll swap in the free-list version without changing a single call site.
/* include/kernel/heap.h
*
* Kernel heap allocator — dual-phase implementation.
*
* Phase 1: Bump allocator (fast, no-free)
* Phase 2: Free-list allocator (malloc/free semantics)
*
* From Silicon to Shell — Post 8: A Heap Allocator
*/
#ifndef KERNEL_HEAP_H
#define KERNEL_HEAP_H
#include <stddef.h>
#include <stdint.h>
/* Align a size up to the nearest multiple of `align`.
* `align` must be a power of two. */
#define ALIGN_UP(n, align) (((size_t)(n) + (align) - 1) & ~((size_t)(align) - 1))
/* Minimum allocation alignment. AArch64 requires 8 bytes for 64-bit stores.
* Bump allocator and free-list both honour this. */
#define HEAP_ALIGN 8
/*
* heap_init — must be called once, before any kmalloc, from kernel_main.
* Initialises internal allocator state using __heap_start and __heap_end
* from the linker script.
*/
void heap_init(void);
/*
* kmalloc — allocate `size` bytes from the kernel heap.
* Returns a pointer to at least `size` bytes of usable memory, aligned
* to HEAP_ALIGN (8 bytes). Returns NULL on out-of-memory.
*
* The returned pointer must be freed with kfree when no longer needed
* (free-list phase). In the bump-allocator phase, kfree is a no-op.
*/
void *kmalloc(size_t size);
/*
* kfree — release memory previously returned by kmalloc.
* Passing a NULL pointer is safe (no-op). Passing a pointer that
* was not returned by kmalloc is undefined behaviour.
*/
void kfree(void *ptr);
/*
* heap_dump — print allocator state to UART for debugging.
* Shows total/used/free bytes and the free-list chain in Phase 2.
*/
void heap_dump(void);
#endif /* KERNEL_HEAP_H */The Bump Allocator Implementation
/* kernel/heap.c — Phase 1: Bump Allocator
*
* How it works in one sentence: maintain a pointer that only ever moves
* forward. Each kmalloc advances the pointer by the requested size.
* kfree is a no-op.
*
* Pros: O(1) allocation, zero metadata overhead, zero fragmentation.
* Cons: Memory is never recovered. Suitable for kernel startup and for
* allocations that live for the entire kernel lifetime.
*/
#include "kernel/heap.h"
#include "drivers/uart.h"
#include <stdint.h>
/* Linker-script symbols — their ADDRESS is the value, not their contents.
* Declared as arrays to force the compiler to treat them as addresses,
* not as variables whose contents we'd try to dereference. */
extern char __heap_start[];
extern char __heap_end[];
/* ── Internal state ───────────────────────────────────────────────────────── */
static char *bump_ptr; /* next free byte */
/* ── Public API ───────────────────────────────────────────────────────────── */
void heap_init(void) {
bump_ptr = __heap_start;
kprint("[heap] init: bump allocator\n");
kprint("[heap] start: 0x");
/* We don't have printf, so kprint_hex is a small helper we'll add */
kprint("\n");
}
void *kmalloc(size_t size) {
if (size == 0) return NULL;
/* Round up to 8-byte alignment to satisfy AArch64 data alignment
* requirements. Misaligned 64-bit stores trigger Data Abort (EC 0x25)
* on real hardware, even though QEMU forgives them. */
size = ALIGN_UP(size, HEAP_ALIGN);
/* Bounds check: will the allocation fit? */
if (bump_ptr + size > __heap_end) {
kprint("[heap] OOM: kmalloc returning NULL\n");
return NULL;
}
void *ptr = bump_ptr;
bump_ptr += size;
return ptr;
}
void kfree(void *ptr) {
/* Bump allocator cannot free individual blocks.
* Accepting the pointer silently is intentional — callers don't need
* to know which allocator is active. */
(void)ptr;
}
void heap_dump(void) {
kprint("[heap] bump allocator: free from bump_ptr to __heap_end\n");
}Update the Makefile
We need to add heap.c to our Makefile and ensure a rebuild such
that the header changes are picked up:
# Makefile — add the heap object
OBJS := build/arch/arm64/boot.o \
build/arch/arm64/vectors.o \
build/drivers/uart/uart.o \
build/kernel/exceptions.o \
build/kernel/gic.o \
build/kernel/main.o \
build/kernel/mmu.o \
build/kernel/timer.o \
build/kernel/heap.o # ← new
build/kernel/heap.o: kernel/heap.c include/kernel/heap.h
$(CC) $(CFLAGS) -c -o $@ $<A Quick Test
Before we go further, let’s prove the bump allocator works. Add this to
kernel_main right after heap_init:
/* kernel/main.c — temporary heap smoke test */
#include "kernel/heap.h"
void kernel_main(void) {
mmu_init();
uart_init();
kprint("PurgatoryOS booting...\n");
heap_init();
/* Allocate three blocks */
void *a = kmalloc(128);
void *b = kmalloc(64);
void *c = kmalloc(512);
kprint("a="); kprint_ptr(a);
kprint(" b="); kprint_ptr(b);
kprint(" c="); kprint_ptr(c);
kprint("\n");
/* Free b — no-op with bump allocator */
kfree(b);
/* Reallocate — will NOT reuse b's slot */
void *d = kmalloc(64);
kprint("d="); kprint_ptr(d);
kprint(" (b slot not reused)\n");
/* ... rest of init ... */
}Before you run the test, we also need to create a new helper function. The kprint_ptr
helper converts a pointer to a hex string and prints it. We need it because we have
no printf. Add it to drivers/uart.c:
/* drivers/uart.c — add this helper */
void kprint_ptr(void *ptr) {
uintptr_t val = (uintptr_t)ptr;
char buf[19]; /* "0x" + 16 hex digits + '\0' */
buf[0] = '0'; buf[1] = 'x';
for (int i = 15; i >= 0; i--) {
int nibble = val & 0xF;
buf[2 + i] = nibble < 10 ? '0' + nibble : 'a' + nibble - 10;
val >>= 4;
}
buf[18] = '\0';
kprint(buf);
}Now build and run it:
a starts at __heap_start (0x4002c000). b is 128 bytes (0x80) later. c is 64 bytes
after b. After freeing b and allocating d, you can see d is at 0x4002c2c0, which
is c + 512 bytes, not at b’s old address. The bump allocator moved past b and never
looked back.
Why the Bump Allocator Fails a Real Kernel
The bump allocator is correct for exactly one use case: allocations that live forever. Kernel
initialisation data, page tables, and static buffers are all allocated once and never freed. Once
the kernel starts creating and destroying objects at runtime, the bump allocator leaks every single
kfree into a growing void. Eventually, it runs out of space and returns NULL for everything.
Step through the interactive visualizer below to see both allocators in action. Pay attention to
what happens when you call kfree in bump mode:
bump_ptr = __heap_start. The entire heap is uncharted territory — no tracking structure, just a pointer.
The free-list mode shows what we’re building next. You should notice and understand these two things before you start the implementation:
- First, every allocation costs more than just the bytes you asked for. Each block has a small header that the allocator writes before your data. That header is why
kmalloc(128)consumes 128 +sizeof(block_header_t)bytes from the heap. This is unavoidable because the allocator needs somewhere to store its bookkeeping. The ratio of header overhead to payload is why allocating many small objects is expensive in memory allocators. An 8-byte allocation with a 24-byte header is 75% overhead. - Second, after several allocations and frees, the heap can end up with many small free fragments that together have enough space for a new allocation, but no single fragment is large enough. This is external fragmentation. The free-list allocator addresses it by coalescing adjacent free blocks. It’s a fundamental property of dynamic allocation. No allocator eliminates it entirely.
The Free-List Allocator
The free-list allocator solves the “I need to free individual blocks” problem by keeping a linked
list of both free and allocated blocks, embedded directly in the heap itself. When you call kfree,
the allocator marks that block as free, and the next kmalloc can reuse it.
The Block Header
Every allocation, whether currently in use or free, starts with a block_header_t that describes it.
This struct lives in the bytes before the pointer that your caller gets back.
/* The per-block metadata header — lives just before the returned payload.
*
* The `size` field stores the payload size, NOT including the header.
* `next` points to the next block header in the heap (not the next
* free block — every block is linked, free or allocated).
*/
typedef struct block_header {
size_t size; /* payload bytes (excludes header) */
int is_free; /* 1 = available for reuse */
struct block_header *next; /* next block in the linked chain */
} block_header_t;
/* HEADER_SIZE: round up to HEAP_ALIGN so that the payload following
* the header is always 8-byte aligned. sizeof(block_header_t) on
* AArch64 with -O2 is 20 bytes; ALIGN_UP gives us 24. */
#define HEADER_SIZE ALIGN_UP(sizeof(block_header_t), HEAP_ALIGN)This is the critical insight. The header lives in the heap itself, with no separate metadata array
or global table. The heap is a chain of headers, each pointing to the next, with payloads sandwiched
between them. To kfree(ptr), you subtract HEADER_SIZE from ptr, and you have the header.
The allocator doesn’t need to look anything up.
The Free-List Implementation
We now need to change the bump allocator to the free list implementation by changing the
body of kernel/heap.c with this:
/* kernel/heap.c — Phase 2: Free-List Allocator
*
* Strategy: first-fit with immediate coalescing.
*
* Allocation: walk the block chain from the start, find the first free
* block with enough space. If it's larger than needed, split it.
*
* Deallocation: mark block free, then scan forward and backward to
* coalesce adjacent free blocks into a single larger block.
*
* Time complexity: O(n) for both alloc and free (n = number of blocks).
* Suitable for a kernel with hundreds to low thousands of live allocations.
*/
#include "kernel/heap.h"
#include "drivers/uart.h"
#include <stdint.h>
extern char __heap_start[];
extern char __heap_end[];
/* ── Internal state ───────────────────────────────────────────────────────── */
static block_header_t *heap_head; /* first block in the chain */
/* ── Private helpers ──────────────────────────────────────────────────────── */
/* Write a block header at address `addr` with the given payload size,
* free flag, and next pointer. Returns the header pointer. */
static block_header_t *write_header(char *addr, size_t size, int is_free,
block_header_t *next)
{
block_header_t *hdr = (block_header_t *)addr;
hdr->size = size;
hdr->is_free = is_free;
hdr->next = next;
return hdr;
}
/* Payload pointer from header: the bytes just after the header struct. */
static inline void *payload(block_header_t *hdr) {
return (char *)hdr + HEADER_SIZE;
}
/* Header from payload pointer: the bytes just before the payload. */
static inline block_header_t *header(void *ptr) {
return (block_header_t *)((char *)ptr - HEADER_SIZE);
}
/* ── Public API ───────────────────────────────────────────────────────────── */
void heap_init(void) {
/* The entire heap is one large free block. */
size_t total = (size_t)(__heap_end - __heap_start);
size_t payload_size = total - HEADER_SIZE;
heap_head = write_header(__heap_start, payload_size, /*is_free=*/1, NULL);
kprint("[heap] init: free-list allocator\n");
}
void *kmalloc(size_t size) {
if (size == 0) return NULL;
/* All payloads are 8-byte aligned. Callers shouldn't have to think
* about this — the allocator absorbs the rounding. */
size = ALIGN_UP(size, HEAP_ALIGN);
/* ── First-fit search ── */
block_header_t *cur = heap_head;
while (cur != NULL) {
if (cur->is_free && cur->size >= size) {
/* Found a free block large enough. Can we split it?
* We split only if the remainder is large enough to hold
* a header plus at least HEAP_ALIGN bytes of payload.
* Otherwise we hand the entire block to the caller. */
size_t remainder = cur->size - size;
if (remainder > HEADER_SIZE + HEAP_ALIGN) {
/* Split: create a new free block for the remainder. */
char *split_addr = (char *)payload(cur) + size;
block_header_t *new_block = write_header(
split_addr,
remainder - HEADER_SIZE,
/*is_free=*/1,
cur->next
);
cur->size = size;
cur->next = new_block;
}
cur->is_free = 0;
return payload(cur);
}
cur = cur->next;
}
/* No block large enough — heap is exhausted or too fragmented. */
kprint("[heap] OOM: kmalloc returning NULL\n");
return NULL;
}
void kfree(void *ptr) {
if (ptr == NULL) return;
/* Recover the header from the payload pointer. */
block_header_t *hdr = header(ptr);
hdr->is_free = 1;
/* ── Immediate forward coalescing ──
* If the block immediately after this one is also free, merge them.
* We only coalesce forward here (backward coalescing requires a
* footer tag or a doubly-linked list — a good next exercise). */
if (hdr->next != NULL && hdr->next->is_free) {
hdr->size += HEADER_SIZE + hdr->next->size;
hdr->next = hdr->next->next;
}
}
void heap_dump(void) {
kprint("[heap] --- free-list dump ---\n");
block_header_t *cur = heap_head;
int idx = 0;
while (cur != NULL) {
kprint("[heap] block ");
/* A minimal integer printer since we have no printf */
char ibuf[8];
int n = idx, pos = 7;
ibuf[pos] = '\0';
if (n == 0) { ibuf[--pos] = '0'; }
while (n > 0) { ibuf[--pos] = '0' + (n % 10); n /= 10; }
kprint(&ibuf[pos]);
kprint(": size=");
/* print size similarly — left as exercise */
kprint(cur->is_free ? " FREE\n" : " USED\n");
cur = cur->next;
idx++;
}
kprint("[heap] --------------------\n");
}Updating kernel_main
Update kernel/main.c to initialise the heap and run a proper smoke test:
/* kernel/main.c */
#include "drivers/uart.h"
#include "kernel/mmu.h"
#include "kernel/exceptions.h"
#include "kernel/gic.h"
#include "kernel/timer.h"
#include "kernel/heap.h"
void kernel_main(void) {
mmu_init();
uart_init();
kprint("PurgatoryOS booting...\n");
exceptions_init();
kprint("Exceptions: ready\n");
gic_init();
kprint("GIC: ready\n");
timer_init(500);
kprint("Timer: armed\n");
/* Heap must be up before any dynamic allocation */
heap_init();
kprint("Heap: ready\n");
/* Smoke test: allocate, free, re-allocate */
void *a = kmalloc(128);
void *b = kmalloc(64);
void *c = kmalloc(256);
kprint("[test] allocated a, b, c\n");
heap_dump();
kfree(b);
kprint("[test] freed b\n");
heap_dump();
void *d = kmalloc(48);
kprint("[test] allocated d (should reuse b slot)\n");
heap_dump();
kfree(a); kfree(c); kfree(d);
kprint("[test] freed all — heap should be mostly coalesced\n");
heap_dump();
asm volatile("msr daifclr, #2");
kprint("Interrupts enabled. Waiting for timer...\n");
while (1) {
asm volatile("wfi");
}
}Now build and run:
The reuse of b’s slot for d shows that the free list works. The 8-byte fragment left after splitting
b’s 64-byte block for d’s 48-byte request shows the allocator correctly splitting and leaving a small
remainder. The final coalescing pass on kfree(a) + kfree(c) + kfree(d) collapses everything back into
a single large free block.
Understanding the Block Layout in Memory
The RegisterViewer below shows the heap at the byte level immediately after kmalloc(128) returns for the first
time. The addresses are based on __heap_start = 0x4002c000.
›payload_ptr_a = block_0_header + HEADER_SIZE (24 bytes). When you call kfree(a), the allocator subtracts 24 from the pointer to recover block_0_header and sets is_free = 1. This is the core trick: the header is physically adjacent to the payload, just behind it.
The gap between block_0_header (0x4002c000) and payload_ptr_a (0x4002c018) is exactly 24 bytes, which is the
HEADER_SIZE. That’s what ALIGN_UP(sizeof(block_header_t), 8) gives you on AArch64: 20 bytes for the struct,
padded to 24. The 4 bytes of padding ensure the payload starts on an 8-byte boundary, satisfying AArch64’s
alignment requirement for 64-bit loads and stores.
The Alignment Bug (And Why It’s Subtle)
There’s one mistake I haven’t mentioned yet, but it’s the one most likely to bite you if you write this yourself.
Look at HEADER_SIZE:
#define HEADER_SIZE ALIGN_UP(sizeof(block_header_t), HEAP_ALIGN)If you forget the ALIGN_UP and just use sizeof(block_header_t) directly, the header is 20 bytes on AArch64. The first payload starts
at heap_start + 20. Is heap_start + 20 8-byte aligned? Only if heap_start is 4-byte-aligned but not 8-byte-aligned in the low 3 bits…
which is hard to guarantee without carefully working through the linker script. Our linker script has ALIGN(8) before the heap symbols,
so __heap_start is 8-byte aligned. heap_start + 20 is then 4-byte-aligned but not 8-byte-aligned.
On QEMU, misaligned loads and stores work. On real Cortex-A53 silicon, they trigger a Data Abort with EC = 0x25 in ESR_EL1. We have been
booted on QEMU for a couple of months now, and everything is fine. If we move to a Pi 4, the kernel locks up immediately with no
diagnostics. ALIGN_UP(sizeof(block_header_t), HEAP_ALIGN) is not optional.
It’s also worth noting that the second allocation’s payload is at heap_start + 24 + 128 + 24 = heap_start + 176. 176 mod 8 = 0. Good. And
the third is at heap_start + 24 + 128 + 24 + 64 + 24 = heap_start + 264. . The alignment propagates correctly through the
chain as long as all sizes and header sizes are multiples of HEAP_ALIGN.
First-Fit vs. Best-Fit
Our allocator uses first-fit: it takes the first free block large enough. This is fast because we stop as soon as we find a match. However, this can leave many small fragments near the start of the heap over time as the early part of the heap is repeatedly split.
Best-fit searches the entire free list for the smallest block that satisfies the request. It wastes less space per allocation but is slower (always ) and creates many small, unusable fragments at the end.
Next-fit (a variant of first-fit) picks up the search where it left off last time, distributing fragmentation more evenly across the heap. Linux’s slob allocator uses this strategy for the kernel’s small-object heap. For our kernel, first-fit is the right choice because the heap will have at most hundreds of objects, and simplicity matters more than theoretical fragmentation analysis.
The Rust Alternative: no_std and #[global_allocator]
We won’t implement a full Rust heap allocator here. But the no_std Rust perspective on heap allocation is worth understanding, because it
illustrates exactly where our C implementation is fragile.
In C, nothing stops you from doing this:
void *p = kmalloc(128);
kfree(p);
kfree(p); /* double-free: undefined behaviour — heap corruption */
char *q = kmalloc(64);
kfree(q + 8); /* wrong pointer: header() gives garbage, heap corrupts */Both of these are silent in C. The first makes the freed block appear free twice, so two future allocations might return the same address. The second writes garbage into the block chain. Neither crashes immediately, but the corruption surfaces later, in completely unrelated code, with a symptom that has nothing to do with the original bug. These are among the hardest bugs to debug in a C kernel.
In no_std Rust, the type system prevents both at compile time. You implement the GlobalAlloc trait:
// kernel/heap.rs (no_std Rust equivalent)
use core::alloc::{GlobalAlloc, Layout};
struct KernelAllocator;
unsafe impl GlobalAlloc for KernelAllocator {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 { /* ... */ }
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) { /* ... */ }
}
#[global_allocator]
static ALLOCATOR: KernelAllocator = KernelAllocator;Register it with #[global_allocator] and Box, Vec, and all heap-using types just work, with the entire borrow checker protecting every access.
You literally cannot write a double-free in safe Rust: the compiler rejects it as a use-after-move. You cannot pass the wrong pointer:
Box<T> carries its own Drop impl and calls dealloc automatically, with the right pointer, when it goes out of scope.
The implementation complexity is identical. The allocator algorithm is the same. The difference is that Rust makes every caller’s contract with the allocator part of the type system rather than a convention you hope every contributor remembers.
What Broke (And Why)
The bug I got and spent most of my time on wasn’t due to alignment but rather to the split threshold. My first version of kmalloc
split any block that was even one byte larger than the request:
/* BROKEN: splits even when the remainder is too small to be useful */
if (cur->size > size) {
char *split_addr = (char *)payload(cur) + size;
block_header_t *new_block = write_header(
split_addr,
cur->size - size - HEADER_SIZE,
1,
cur->next
);
cur->size = size;
cur->next = new_block;
}The problem: if cur->size - size is less than HEADER_SIZE + HEAP_ALIGN (32 bytes), you write a header for a block whose payload is
smaller than one minimum allocation. That block will never be used because it’s too small for anything. Worse, when you try to split
it in a future allocation, cur->size - size - HEADER_SIZE underflows (it’s unsigned). The new “block” header gets written at a
nonsense address, overwriting valid heap data.
The resulting heap corruption showed up as a lockup on the third or fourth allocation after a specific free sequence.
GDB’s $ heap_start showed a chain pointer pointing into the middle of an allocated block. It took a while to
trace the split code back. The fix is the minimum remainder check:
if (remainder > HEADER_SIZE + HEAP_ALIGN) {
/* split */
}That > matters. Not >=. If remainder == HEADER_SIZE + HEAP_ALIGN, the remainder block has exactly HEAP_ALIGN (8) bytes of payload.
That’s technically a valid allocation, but it’s 24 bytes of header for 8 bytes of data. The > adds a small tolerance and prevents
the creation of nearly-useless slivers.
What’s Next
The heap is alive, and every future system in this kernel will use kmalloc to exist at runtime. That’s the main thing we achieved in this
post: we just gave the kernel the ability to create things.
The next post starts using that immediately. We’ll define a process control block (a pcb_t struct), allocate one with kmalloc, fill it in,
and write the assembly that saves and restores the CPU’s full register state to switch between two processes. The scheduler in the next
post is the moment when the kernel stops being a single-threaded boot sequence and becomes an actual operating system.
The heap allocator we just wrote is good enough to get through the rest of the series. It’s O(n), which isn’t production-quality, but it only coalesces forward and doesn’t handle heap expansion. But it’s real: it correctly tracks state, it actually reuses freed memory, and it doesn’t corrupt itself when you use it correctly. That’s what matters for now.
Sources
- Allocator Designs — Writing an OS in Rust (Philipp Oppermann) — the definitive walk-through of bump, linked-list, and fixed-size block allocators in a bare-metal context. Our implementation is independent but the conceptual framing here is excellent.
- Writing a Memory Allocator — Dmitry Soshnikov — step-by-step C implementation of a free-list allocator with boundary tags and coalescing, well-commented and precise.
- Memory Allocation — OSDev Wiki — the OSDev reference for kernel heap strategies, covering physical memory managers, slab allocators, and the relationship to virtual memory.
- Dynamic Memory Allocation: Free Lists — Brown University CS208 — clean academic treatment of implicit and explicit free lists, first-fit vs. best-fit, and fragmentation analysis. Good companion to the implementation.
- A Deep Dive into Building a Memory Allocator — Sriman, Medium — practical C walk-through covering block headers, coalescing, and splitting, with diagrams.
- CMU 15-213: Dynamic Memory Allocation Lecture — the canonical slide deck on dynamic memory allocation from Carnegie Mellon’s systems course. Covers fragmentation, throughput, and allocator design trade-offs in depth.
- no_std — The Embedded Rust Book — the authoritative guide to
no_stdRust, explaining what’s available without the standard library and how to provide a global allocator. - embedded-alloc: A heap allocator for embedded systems — rust-embedded — the reference
no_stdallocator crate for Rust embedded/bare-metal work, implementingGlobalAllocwith a linked-list strategy. - Dynamic Memory Allocation — Practical Guide to Bare Metal C++ — explains what
-ffreestandingand-nostdlibremove from the standard allocator, and what bare-metal code must provide itself. - Power-of-Two Free Lists Allocators — GeeksforGeeks — explains the slab/power-of-two variant of free-list allocation used in production kernels, a natural evolution from our first-fit approach.
- The Slab Allocator in the Linux Kernel — hammertux.github.io — deep-dive into Linux’s slab allocator, showing how a production kernel builds on the same free-list fundamentals with per-type caches and NUMA awareness.
- AArch64 Data Alignment Faults — ARM Architecture Reference Manual DDI 0487 — the authoritative reference for
EC = 0x25alignment fault behaviour andSCTLR_EL1.A. Required reading if you want to understand why QEMU forgives what real silicon doesn’t.