Slab Allocator Visualization | Linux SLUB and kmalloc

The idea: one cache per object size, slabs cut from pages

The buddy allocator hands out whole pages of 4 KiB. Most kernel objects are much smaller: an inode, a socket buffer head, a 300-byte request. Giving each of them a page would waste most of it. The slab allocator sits on top: it takes pages from the buddy allocator and cuts each one into equal objects. Since Linux 2.6.23 the default slab allocator is SLUB (mm/slub.c), and since 6.8 it is the only one.

Objects of one size and type live in one cache, a struct kmem_cache. A slab is one or more contiguous pages that belong to one cache. kmalloc(size) uses a set of general caches, one per size class: kmalloc-8, kmalloc-16, … kmalloc-8k. Subsystems also create their own caches with kmem_cache_create (dentry, inode_cache, task_struct).

kmalloc(300) is rounded up to the kmalloc-512 cache. The cache has a kmem_cache_cpu per CPU with its current slab and freelist, and a kmem_cache_node with a partial list. Full slabs are on no list. New slabs come from the buddy allocator as pages, and empty slabs go back to it. — A cache gives each CPU its own slab to allocate from; slabs with free objects wait on the node's partial list, and pages come from and go back to the buddy allocator.

Reading the canvas

Size classes (top): the caller's kmalloc(size) flies to the class it is rounded up to. The three modelled caches show how many objects are in use.
kmem_cache (left): one cache at a time. The two CPU rows are each CPU's current slab. Below them the node's partial list and the full slabs. Each cell is one object: orange with the owner's name when allocated; when free it shows the index of the next free object (→3, →∅ at the end).
/proc/slabinfo (right): the same columns the kernel prints, plus the bytes lost by rounding up.
Buddy allocator (right): page frames 16–31. Six are free; a slab page shows the object size of its cache.

Inside a slab: the freelist lives in the free objects

A new slab is a page cut into objperslab objects: a 4096-byte page holds 8 objects of 512 bytes. SLUB needs no separate table of free objects. Each free object stores a pointer to the next free object at a fixed offset inside itself, so the free list costs no memory at all. Allocating means "take the head, the head becomes its next pointer". Freeing means "write the old head into the object, make it the head". Both are O(1), and the list is LIFO: the object freed last is handed out first, while it is still warm in the CPU cache.

A 4096-byte page cut into 8 objects of 512 bytes. Before: all free, linked 0 to 1 to 2 up to 7, head 0. After kmalloc A, B, C and kfree B: objects 0 and 2 hold A and C, the freelist head is 1, which points to 3, then 4 to 7. — Free objects hold the next pointer themselves; after kfree(B) the freelist head is B's old slot, so the next kmalloc gets the same address.

The fast path: a per-CPU freelist, no lock

Each cache has a struct kmem_cache_cpu per CPU with two fields that matter here: c->slab, the CPU's current slab, and c->freelist, its free objects. slab_alloc_node() pops the head with one this_cpu_cmpxchg (together with a transaction id, so a preemption in between is detected). There is no lock and no shared cache line, which is why most kmalloc calls take a few nanoseconds. A kfree on the same CPU into its own slab pushes onto the same list (Demo: fast path, kmalloc and kfree: D gets B's slot and B's address).

The slow path: get_freelist, partial list, new slab

When c->freelist is empty, ___slab_alloc() tries, in order:

get_freelist: other CPUs may have freed objects into this slab. They could not touch c->freelist, so those objects sit on the slab's own slab->freelist. One cmpxchg takes them all (Demo: remote free from another CPU).
If there are none, the slab is full. The CPU lets go of it and it goes on no list: SLUB does not track full slabs, a later kfree finds the slab through the object's page.
get_partial: take the node's list_lock and the first slab on its partial list; its free objects become c->freelist.
new_slab: no partial slab, so alloc_pages() gets a page from the buddy allocator and cuts it up. If that fails too, kmalloc returns NULL.

Decision chain of kmalloc: if c->freelist has an object, pop it (fast path, no lock). Else if slab->freelist has objects, take them (get_freelist). Else the full slab goes on no list; if the node partial list has a slab, take it under list_lock; else allocate a new page from the buddy allocator; else return NULL. — Each step of the slow path is more expensive than the one before; most allocations never leave the first box.

kfree and the partial list

The object's slab is	What `kfree` does
this CPU's slab	fast path: push on `c->freelist`
another CPU's slab	push on `slab->freelist` with cmpxchg; the owner picks it up later
full (on no list)	push; the slab is now partial: take `list_lock`, add it to the partial list
partial	push; if the slab is now empty and the node has at least `min_partial` partial slabs, give the page back to the buddy allocator

Demo: full slab, partial list, new slab uses 700-byte objects from kmalloc-1k (4 per slab): the fifth kmalloc needs a new page, freeing B makes the first slab partial, and when the second slab is full the CPU takes the first one back and the next object lands in B's old slot. min_partial keeps a few empty slabs around so that alloc/free cycles don't bounce pages to and from the buddy allocator (Demo: empty slab back to the buddy allocator; the page uses 2, Linux 5–10).

kmalloc size classes and wasted bytes

kmalloc rounds the size up to the next class: powers of two from 8 bytes to 8 KiB, plus 96 and 192. Larger requests go straight to the page allocator. The rest of the object is lost (internal fragmentation): Demo: size classes and wasted bytes asks for 200, 300, 700 and 1000 bytes and gets 256, 512, 1024 and 1024, losing 616 bytes. A subsystem with many objects of one odd size creates its own cache with that exact size instead. ksize(ptr) tells the real size of a kmalloc object.

kmalloc(size)	cache	wasted
200	kmalloc-256	56 B
300	kmalloc-512	212 B
700	kmalloc-1k	324 B
1000	kmalloc-1k	24 B

How to see it: /proc/slabinfo and slabtop

$ sudo head -3 /proc/slabinfo; sudo grep -E '^(kmalloc-(256|512|1k)|dentry) ' /proc/slabinfo
slabinfo - version: 2.1
# name            <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables ... : slabdata <active_slabs> <num_slabs> ...
kmalloc-1k          4832   4864   1024   32    8 : tunables    0    0    0 : slabdata    152    152      0
kmalloc-512         6377   6528    512   32    4 : tunables    0    0    0 : slabdata    204    204      0
kmalloc-256         3918   4096    256   32    2 : tunables    0    0    0 : slabdata    128    128      0
dentry            196413 197106    192   21    1 : tunables    0    0    0 : slabdata   9386   9386      0

active_objs is the objects in use, num_objs the room in all slabs; the difference is free objects held in slabs. Real kernels use bigger slabs than the page does (pagesperslab 8 for kmalloc-1k: 32 objects per slab) so that less of each slab is left over. slabtop shows the same numbers sorted live, and /sys/kernel/slab/<cache>/ has one file per statistic. Caches with the same size and flags are often merged into one, so several names point at the same slabs.

SLAB, SLUB and SLOB

	SLAB (1996–2023)	SLUB (default since 2.6.23)	SLOB (removed in 6.4)
Per-CPU	arrays of object pointers	one current slab + its freelist	none
Lists	full, partial, free per node	partial only	one list of free blocks
Metadata	separate per-slab management area	in `struct slab` (the page's struct) and in the free objects	headers in the blocks
For	general use	general use, less memory, simpler	tiny embedded systems

User space has the same problem and similar answers: glibc malloc keeps per-thread caches (tcache) and bins of free chunks per size, see Stack vs Heap in C. The pages the kernel maps for a process come one at a time from the buddy allocator, see Linux Virtual Memory.

What the page leaves out

Per-CPU partial lists (CONFIG_SLUB_CPU_PARTIAL: a freed-into full slab first goes on the freeing CPU's own partial list, and a CPU refills from there before taking the node lock); NUMA nodes, each with its own partial list; slabs of more than one page (oo order); the transaction id and preemption checks of the fast path; freelist pointer hardening and random freelist order; debugging (red zones, poisoning, slub_debug); cache merging; RCU-freed caches (SLAB_TYPESAFE_BY_RCU); kmalloc of more than 8 KiB, which goes to the page allocator; memory cgroup accounting; and reclaimable caches that the shrinkers empty under memory pressure.