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_structs, 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.