Slab Allocators and the Buddy System

Where the last two guides left a sore spot

Guide 1 gave you a general-purpose allocator: a free list threaded through the holes, first fit or best fit to choose a block, and splitting and coalescing with boundary tags to keep memory dense. It works for any size in any order — but it pays for that generality. Every free() may scan a long list, and every coalesce has to chase neighbours and rewrite headers and footers. Guide 2 then showed the other extreme: an arena or pool that gives up generality for raw speed, handing back fixed-size slots in a couple of instructions but unable to free one object at a time, or unable to serve mixed sizes at all.

This guide is about two designs that sit cleverly between those poles. The buddy system keeps a general allocator's ability to serve a range of sizes, yet makes splitting and merging almost free by allowing only sizes that are powers of two. The slab allocator keeps a pool's blazing speed for one object type, yet adds the ability to free individual objects and to reuse their already-initialized shape. They were not invented as toys: the buddy system manages the Linux kernel's physical page frames, and the slab allocator (and its descendants) sit right on top of it serving the kernel's millions of small objects. By the end you should see why each one is shaped the way it is.

The buddy system: powers of two, and the XOR trick

Recall the pain of coalescing in guide 1: to merge two free blocks you must find a neighbour, confirm it is free, and confirm the two are physically adjacent and the same logical unit. The buddy system makes all three checks trivial by imposing one rule: every block has a size that is a power of two, and a block of size 2^k can only ever come from splitting a block of size 2^(k+1) exactly in half. The two halves born from one split are called buddies. A block may only ever coalesce with its own buddy — never with some arbitrary neighbour — which is exactly what makes merging cheap and predictable.

Here is the trick that makes it sing. If a block of size 2^k starts at address a (measured from the start of the pool), its buddy's address is simply a XOR 2^k — flipping the single bit at position k. That one bitwise operation, with no list to walk and no footer to read, tells you exactly where your buddy lives. To free a block: compute the buddy address, check whether the buddy is also free and the same size, and if so flip that bit to step up to the merged parent of size 2^(k+1), then repeat the check one level up. Allocation runs the same machinery backwards: keep a free list per size class (one list of 16 KiB blocks, one of 32 KiB, and so on); if the right-sized list is empty, take a block from the next size up and split it, putting one buddy on the smaller list and using the other.

Pool of 64 KiB. Ask for a 6 KiB block -> round up to 8 KiB (2^13).

  [-------------------- 64 --------------------]   need 8
  [------- 32 -------][------- 32 -------]          split 64
  [-- 16 --][-- 16 --]                              split left 32
  [ 8 ][ 8 ]                                         split left 16  <- return this 8

The returned 8 KiB block sits at offset 0x0000.
Its buddy is at 0x0000 XOR 0x2000 = 0x2000 (the other 8).
Free both 8s -> merge to the 16 -> its buddy is the right 16 ->
merge to 32 -> buddy is the right 32 -> merge back to the full 64.

The slab allocator: keep objects pre-shaped

Now flip to the other problem. A kernel allocates and frees the same kind of small object constantly — a task structure here, an inode there, thousands per second, all identical in size. A general allocator treats each one as an anonymous blob: round up the size, search a list, write a header, and on free, coalesce. That is wasteful when every object is the same shape. The slab allocator, invented by Jeff Bonwick for SunOS in 1994, builds on the pool idea from guide 2 with one organizing insight: dedicate a cache to one object type, carve large slabs of contiguous pages into an exact grid of object-sized slots, and serve from that grid.

Because every slot in a cache is the same size, there is no searching and no rounding: a free list of identical slots means malloc-equivalent is "pop the head" and free-equivalent is "push the head", both O(1). A slab is just a run of pages plus a small free list of its empty slots; the allocator keeps slabs sorted into three states — full (every slot used), partial (some free), and empty (all free) — and always serves from a partial slab so memory stays packed. When a whole slab goes empty it can be handed back to the page allocator under memory pressure. Notice the layered design: the buddy system below hands out page-sized chunks, and the slab allocator above chops those into fine-grained objects. That is exactly how Linux is built, with kmalloc() sitting on slab caches sitting on the buddy allocator.

Tracking objects: where does the bookkeeping go?

A slab allocator faces the same metadata question guide 1 raised — given a pointer to free, how do you find its slab and its free list? — but answers it differently, and the difference matters for cache behaviour. The original design stored each slab's control structure and its array of free slot indices inside the slab itself, typically at the end of the page run. This keeps a slab self-contained, but for small objects the in-slab metadata steals slots, and worse, touching the management data drags an extra cache line into the CPU on every allocation.

There is a slicker route that avoids per-object headers entirely. Because every object in a slab is the same size and the slab starts on a page boundary, you can recover an object's slab from its address by simple arithmetic — mask the pointer down to the page (something like p & ~0xFFF on 4 KiB pages) and look up that page in a global table that records which cache it belongs to. The object itself carries no header at all; the slab metadata lives off to the side. This is the modern approach, and it is why a slab object often costs zero per-object overhead, unlike the header-bearing blocks of guide 1. Honesty check: the per-object bookkeeping did not vanish, it moved into a compact per-slab structure and a page lookup, which is cheaper precisely because it is shared across thousands of identical objects.

Putting buddy and slab together, and what comes next

Step back and see the whole machine, because the two ideas are partners, not rivals. The buddy system is a coarse-grained, general allocator: it serves big power-of-two chunks (pages and runs of pages) with cheap split and merge and almost no external fragmentation, and it tolerates internal waste because page-sized requests rarely round up much. The slab allocator is a fine-grained, specialized allocator: it takes those big chunks and dices each one into exact slots for a single object type, with O(1) alloc/free and zero per-object header. Coarse-and-general underneath, fine-and-specialized on top — that two-layer split is one of the most reused patterns in all of systems memory management.

1. A kernel subsystem needs a new inode object and calls its allocator. The slab cache for inodes is asked for one slot.
2. If a partial slab has a free slot, pop the head of its free list — one or two instructions, done. The object may already be in constructed state, so no re-initialization is needed.
3. If every slab is full, the cache asks the buddy system for a fresh run of pages, carves it into a grid of inode-sized slots, and that becomes a new empty-then-partial slab.
4. On free, mask the pointer to its page, find the owning slab and cache, push the slot back on the free list. When a whole slab empties and memory is tight, its pages return to the buddy allocator, which may merge them back up with their buddies.

Two threads still pulling at this design point straight at the next guides. First, an allocator built around one fixed object size is wonderful for a kernel but useless for a malloc() that must serve arbitrary sizes — the resolution is to keep many slab-like pools at carefully chosen sizes, the size classes of guide 4. Second, a single shared slab cache becomes a lock-contention bottleneck when many CPUs allocate at once, which is why real kernel and user allocators bolt a per-CPU or per-thread cache on the front — the structure that guide 5 shows powering jemalloc, tcmalloc, and mimalloc. You have now seen the two cleanest specialized allocators; the rest of the rung is about making one general allocator borrow their tricks.