Kernel Memory Allocators
The kernel cannot call \texttt{malloc} — it is the thing that
\texttt{malloc} is built on. When a device driver needs a buffer, when the
scheduler needs a new task structure, when the network stack needs a socket, some code inside the kernel
must hand out memory from the raw supply of physical
page
frames — quickly, without fragmenting itself to death, and without ever blocking in a context
where blocking would deadlock the machine. This lesson is about how kernels solve that, at two very
different scales, and how the same ideas resurface in the fast user-space allocators your own programs
rely on.
The problem splits cleanly by granularity. Sometimes the kernel wants whole pages, or
runs of contiguous pages — that is the buddy allocator's job. Far more often it wants a
tiny, fixed-shape object — a 256-byte \texttt{struct}
— thousands of times a second; carving those out of whole pages would waste enormous space, so a second
layer, the slab allocator, sits on top. Two allocators, two fragmentation problems, one
stack.
The buddy allocator: power-of-two blocks
The buddy system manages physical memory in blocks whose sizes are powers of two pages:
1, 2, 4, 8, \dots, 2^{\text{order}} pages. A free list is kept for each order.
To satisfy a request you round up to the next power of two, then:
- if a free block of exactly that order exists, hand it out;
- otherwise take a larger free block and split it in half repeatedly — each half is the
other's buddy — until you reach the right size, parking the unused halves on their free
lists.
When a block is freed, the allocator checks whether its buddy is also free; if so it
coalesces them back into the block of the next order up, and repeats. Because a block and
its buddy differ by exactly one bit (buddy of block b at order
o is b \oplus 2^{o}), finding the buddy and merging
is a single XOR — fast, and it keeps large contiguous regions available. Watch a request for 3 pages split
a 16-page block down:
That last step exposes the buddy system's built-in tax. A request for 3 pages had to be served by a
4-page block — one whole page is handed over but unused. This is internal fragmentation:
waste inside an allocated block, caused by rounding up to a power of two. In the worst case (a
request one page over a power of two) the buddy allocator wastes almost 50\%.
// A buddy allocator over 2^4 = 16 pages. Requests round up to a power of two;
// larger free blocks split into buddies; frees coalesce buddies back together.
const MAX_ORDER = 4; // total memory = 16 pages
const free: number[][] = Array.from({ length: MAX_ORDER + 1 }, () => []);
free[MAX_ORDER].push(0); // one free block @0 covering all 16 pages
const orderFor = (pages: number): number => {
let o = 0; while (2 ** o < pages) o++; return o; // smallest order that fits `pages`
};
function alloc(pages: number): number {
const need = orderFor(pages);
let o = need;
while (o <= MAX_ORDER && free[o].length === 0) o++; // find the smallest available block >= need
if (o > MAX_ORDER) { console.log(`alloc(${pages}) FAILED (out of memory)`); return -1; }
let base = free[o].shift() as number;
while (o > need) { // split down to the needed order
o--;
const buddy = base + 2 ** o;
free[o].push(buddy);
console.log(` split -> buddies @${base} and @${buddy} (order ${o})`);
}
const got = 2 ** need;
console.log(`alloc(${pages}) -> block @${base}, ${got} pages, internal frag = ${got - pages} page(s)`);
return base;
}
function release(base: number, pages: number): void {
let o = orderFor(pages);
while (o < MAX_ORDER) { // try to coalesce with the buddy, repeatedly
const buddy = base ^ (2 ** o);
const i = free[o].indexOf(buddy);
if (i === -1) break; // buddy not free -> stop
free[o].splice(i, 1);
base = Math.min(base, buddy);
console.log(` coalesce @${base} + @${buddy} -> order ${o + 1}`);
o++;
}
free[o].push(base);
console.log(`free(@${base}, ${pages}) done`);
}
const a = alloc(3); // rounds up to a 4-page block: 1 page wasted
const b = alloc(2);
release(a, 3);
release(b, 2); // frees ripple up, coalescing back toward the whole 16-page block
The slab allocator: object caches
The buddy system deals in pages, but the kernel mostly wants objects far smaller than a page —
a \texttt{task\_struct}, an inode, a directory entry, allocated and freed
constantly. Cutting a fresh page from the buddy allocator for each tiny object would waste most of the
page and thrash the buddy lists. The slab allocator (Bonwick, 1994) fixes this: it asks
the buddy allocator for a slab (one or a few contiguous pages) and carves it into an
array of same-sized objects, kept in a per-type cache. Allocating an
object is then just popping one off a free list — no splitting, no page walk.
Slabs earn their keep three ways. They pack many objects per page, so per-object overhead is tiny. They
keep cache-warm objects: a freed object is not scrubbed but kept partly initialised, so
the next allocation of that type reuses a structure whose fields (and CPU-cache lines) are already hot —
a real speed win for churny types. And each object type gets its own cache, so a burst of one type does
not fragment the memory used by another. The cost is a form of internal fragmentation: an
object cache sized for 320-byte objects rounds a
300-byte request up, wasting the slack in every slot.
- the buddy allocator hands out contiguous runs of pages as power-of-two blocks,
splitting on demand and coalescing buddies (an XOR apart) on free — its waste is
internal fragmentation from rounding up, and it fights external
fragmentation by coalescing;
- the slab/slub allocator sits on top, carving buddy-supplied pages into caches of
fixed-size objects for fast, low-overhead, cache-warm allocation of small kernel structures;
- user-space allocators (jemalloc, tcmalloc) apply the same playbook: size classes
plus per-thread caches to make \texttt{malloc} fast and
scalable.
Internal vs external fragmentation — the two enemies
Every allocator is judged by how much memory it wastes, and there are exactly two ways to waste
it. Keep them straight, because the fixes are opposite:
| Type | Where the waste is | Cause | Fought by |
|---|
| Internal | inside an allocated block (unused slack) | rounding a request up to a fixed size | finer size classes |
| External | between allocated blocks (free but unusable gaps) | free memory scattered in pieces too small to use | coalescing / compaction |
The buddy allocator trades them off deliberately: rounding to powers of two causes internal
fragmentation, but the resulting regularity makes coalescing trivial, which crushes external
fragmentation. Slabs almost eliminate external fragmentation for small objects (a slab is fully used or
fully returned) at the price of a little internal slack per slot. There is no free lunch — you choose
which fragmentation to pay.
Up in user space: jemalloc and tcmalloc
Your program's \texttt{malloc} faces the same pressures — plus one the kernel
allocators mostly dodge: dozens of threads calling it at once. A single global lock around the heap would
serialise them all. The modern answer, in tcmalloc (Google) and
jemalloc (FreeBSD, Facebook), is two ideas you have now met:
- Size classes: round every request up to one of a fixed menu of sizes (8, 16, 32, 48,
64, …), and keep a free list per class — the slab idea, in user space. Bounds internal fragmentation and
makes allocation a list pop.
- Per-thread caches: each thread keeps a small private cache of free objects per size
class, so the common case — allocate and free on the same thread — touches no shared lock at
all. Only when a thread's cache runs dry or overflows does it talk to the central heap.
That is why swapping in tcmalloc or jemalloc can dramatically speed up a heavily-threaded server: the
allocator stops being a contention bottleneck. The lesson is universal — from the buddy allocator in the
kernel to \texttt{malloc} in your process, fast allocation means
size classes to bound waste and per-CPU / per-thread caches to bound contention.
If every slab lays its objects out starting at the same offset within a page, then object number 0 of
every slab maps to the same
CPU-cache set.
Hammer many such objects and they all collide in that one set, evicting each other while the rest of the
cache sits idle — a self-inflicted hot spot. Slab colouring nudges each new slab's
starting offset by a different small amount ("colour"), so equivalent objects across slabs land in
different cache sets and spread the load. It costs a few wasted bytes per slab and buys measurably
fewer conflict misses. It is a lovely example of an allocator reaching down two layers — past virtual
memory, into the cache's set-index bits — to tune performance.
The classic mix-up: seeing a buddy allocator "waste" memory on a 3-page request and calling it external
fragmentation. It is internal — the waste is the unused fourth page inside the
block you were given. External fragmentation is the opposite failure: you have, say, 6 pages free in
total, but scattered as three separate 2-page gaps, so a request for a contiguous 4-page block
fails even though enough memory exists. The tell is where the free space is: unusable
slack inside a block you hold is internal; usable-in-total but too-scattered-to-use free space
between blocks is external. They demand opposite cures — finer sizing shrinks internal
fragmentation but tends to worsen external, and coalescing/compaction cures external at the cost of some
internal. Diagnose which one is biting before you "fix" it.