Kernel Heap Allocators

Your kernel needs malloc, and nobody is going to give it one. There's no libc in ring 0 — you are the layer libc calls. Every kernel object born at runtime (process structs, page-table pages, file buffers) comes from an allocator you must build from raw memory ranges.

Two layers, two granularities

Kernel memory management splits cleanly in two, and confusing them is the classic beginner tangle:

• The physical frame allocator hands out whole 4 KiB frames — the currency of the paging system. "Give me a page for this page table."
• The heap allocator hands out arbitrary byte-sized objects within pages it got from the frame allocator. "Give me 48 bytes for a task struct."

This lesson is the second one. It's where allocation strategy actually gets interesting, because requests are variably sized and arrive in any order.

The bump allocator: brutally simple, genuinely used

The simplest possible allocator is a pointer:

next  = heap_start
end   = heap_start + heap_size

alloc(size, align):
    p = align_up(next, align)
    if p + size > end:  fail          # out of memory
    next = p + size
    return p

free(ptr):
    # nothing.

Allocation is two additions and a compare. free does nothing — memory comes back only by resetting the whole heap. That sounds like a toy, but it's exactly what Linux does during early boot (memblock) before the real allocator exists, and what arena allocators do in high-performance servers: when everything dies together, never tracking individual lifetimes is a feature.

Alignment: the part everyone fumbles

Hardware cares where objects start. Atomics and wide loads require (or heavily prefer) naturally-aligned addresses; page tables must start on 4 KiB boundaries; a misaligned SSE load can fault outright. So alloc takes an alignment — always a power of two — and rounds up:

align_up(p, a) = (p + a - 1) & ~(a - 1)

Why it works: adding a-1 pushes p past the next boundary unless it's already on one, and masking with ~(a-1) clears the low bits back down to the boundary. Walk one example in hex until it's obvious:

p = 0x1003, a = 0x10:
  0x1003 + 0xF = 0x1012
  0x1012 & ~0xF = 0x1010   ✓ next 16-byte boundary
p = 0x1010, a = 0x10:
  0x1010 + 0xF = 0x101F
  0x101F & ~0xF = 0x1010   ✓ already aligned, unchanged

The bytes between p and the aligned address are simply lost — internal fragmentation, the price of alignment. Your exercise is precisely this machine: a bump allocator over a fixed heap that honors alignment, reports each allocation's address, fails cleanly when full, and resets. Every rule above becomes a test case.

Free lists: when objects die individually

Real general-purpose heaps must reclaim. The workhorse design is the free list: every freed block is threaded onto a linked list (the list nodes live inside the free memory — it's free, after all). alloc walks the list for a block that fits (first-fit takes the first one; best-fit hunts the tightest), splits off the remainder, returns the front. free inserts the block back and coalesces — merges with physically adjacent free neighbors so the heap doesn't decay into confetti.

That decay has a name: external fragmentation — plenty of free bytes, none of them contiguous enough. A megabyte of free memory in 4-byte crumbs can't satisfy a 64-byte request. Coalescing fights it; allocation-size policy fights it; nothing fully cures it.

What grown-up kernels do

Two refinements dominate real systems:

• Slab / slub allocators (Linux's kmalloc backend): kernels allocate the same types constantly — task structs, inodes, socket buffers. A slab dedicates whole pages to one object size, so allocation is "pop from this size's list": near-zero search, near-zero fragmentation, and freed objects can even keep their initialized state.
• Buddy allocator (the frame layer underneath): manage physical memory in power-of-two blocks; split a block in half ("buddies") to satisfy small requests, and merge buddies back on free with one XOR to find your partner. It's the standard answer to contiguous multi-frame allocation.

Bump → free list → slab is not just a difficulty ramp; it's the actual archaeology of your running kernel. Build the first one now, and you'll recognize the others when you meet them in /proc/slabinfo.