# How the Kernel Allocates Memory: Buddy and Slab

> malloc has a supplier: the kernel's own allocators. The buddy system deals in power-of-two page blocks and fights fragmentation with math; the slab layer turns pages into typed object caches. Between them, every allocation on your machine.

URL: https://harshith.in/blog/buddy-and-slab-allocators/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: kernel, memory, linux

Userspace gets to be cavalier about memory: `malloc` fails, you exit. The
kernel doesn't get that luxury — it *is* the allocator of last resort, it can't
swap out its own working memory, and some of its callers (interrupt handlers)
can't even wait. Under every `malloc`, every page fault, every `sk_buff`, sit
two kernel allocators solving different problems: the **buddy allocator** for
raw pages, and the **slab layer** for objects. Both are visible from `/proc`,
and both are worth understanding the day `page allocation failure` shows up in
dmesg on a machine with gigabytes "free."

## The Buddy Allocator: Power-of-Two Discipline

Physical memory is carved into 4 KB page frames, and the buddy system manages
them in blocks of 2^order pages — order 0 = 4 KB up to order 10 = 4 MB — one
free list per order:

```text
$ cat /proc/buddyinfo
Node 0, zone   Normal   312   180   96   41   17   6   3   1   1   0   0
                        ord0  ord1 ord2 ord3 ...                    ord10
```

Need an order-2 block (16 KB) and the order-2 list is empty? Take an order-3
block and split it into two order-2 "buddies"; hand one out, list the other.
The trick is freeing: a block's buddy is computable — `block_addr XOR
(1 << order)` — so on free, check the buddy; if it's also free, **coalesce**
into an order+1 block, and cascade upward. That XOR is the whole reason for
power-of-two sizing: merge candidates are found in O(1) with no searching,
which keeps external fragmentation perpetually being repaired.

Being repaired, not solved. A long-running box's memory becomes confetti of
order-0/1 blocks, and an order-4 request (64 KB contiguous — jumbo-frame
buffers, some drivers) can fail with plenty of total memory free. That's the
dmesg error above, and it's why the numbers on the right side of buddyinfo
draining to zero is an early-warning sign, why `vm.min_free_kbytes` and
kcompactd (physical defragmentation by *moving movable pages*) exist, and one
more reason huge pages are best reserved at boot.

## The Slab Layer: Objects, Not Pages

The kernel allocates the same structs relentlessly — inodes, dentries,
`task_struct`s, network buffers — mostly far smaller than a page. The slab
layer sits on top of buddy: grab an order-n block, slice it into equal
object-sized slots, and serve those from per-type caches:

```text
$ sudo slabtop
  OBJS   ACTIVE   USE  OBJ SIZE  SLABS  NAME
 210k     198k    94%    1.06K   7000   ext4_inode_cache
 890k     870k    97%    0.19K   21000  dentry
  45k      44k    98%    3.5K    5600   task_struct
```

The wins stack up: no per-allocation size math (every slot fits exactly, zero
internal fragmentation for that type); freed objects return to their slab and
are reallocated *as the same type* — warm in cache, and historically even
kept pre-initialized (Bonwick's original constructor idea from Solaris 1994).
Modern Linux uses **SLUB**, which streamlined this design: per-CPU active
slabs make the common alloc/free path lock-free — allocation is "pop a
pointer off this CPU's freelist," a handful of instructions.

`kmalloc` is this same machinery behind a malloc-shaped API: generic caches at
power-of-two-ish sizes (kmalloc-8 … kmalloc-8k, visible in slabtop). Beyond a
few pages, `vmalloc` changes strategy entirely — gather *scattered* physical
pages and stitch them virtually-contiguous via page tables, trading buddy
pressure for TLB pressure.

Two operational notes that pay rent: slab memory is why "free" memory lies —
dentry/inode caches happily grow into gigabytes (they're reclaimable; check
`SReclaimable` in /proc/meminfo before panicking) — and per-type accounting
makes slabtop a leak detector: a cache that only ever grows names the
subsystem with the bug. Debug builds go further: SLUB poisoning (0x6b fill on
free) and redzones catch kernel use-after-free the same way glibc's heap
checks catch yours.

## The Full Supply Chain

Your `malloc(32)` at the bottom of the stack: glibc serves it from an arena;
when the arena's empty, `brk`/`mmap` asks the kernel; the fault handler asks
the buddy allocator for a page; and kernel-side, the VMA structs *describing*
that mapping came from a slab cache. Allocators all the way down — each layer
batching the one below, each solving the fragmentation shape the layer above
creates.

## Takeaways

- Buddy allocator: power-of-two blocks, O(1) buddy-XOR coalescing, free lists
  per order — read them in /proc/buddyinfo.
- High-order allocation failure with free memory = external fragmentation;
  compaction and boot-time reservation are the levers.
- Slab/SLUB: per-type object caches on buddy pages — zero internal
  fragmentation, cache-warm reuse, lock-free per-CPU fast paths.
- slabtop is both a "where did my memory go" answer (reclaimable caches) and a
  kernel leak detector.
- kmalloc = generic slabs; vmalloc = virtually-stitched scattered pages; your
  malloc sits on all of it.