Memory Allocation Walkthrough
Trace kmalloc() and __alloc_pages() from the slab/SLUB allocator through the buddy system, zone watermarks, memory compaction, and the OOM killer.
Walkthrough
// annotated source at every step
kmalloc() selects a SLUB cache by size
Most kernel subsystems allocate small objects with kmalloc(size, flags). kmalloc() does not call the buddy allocator directly — it routes through the SLUB allocator. SLUB maintains a set of size-class caches (kmalloc-8, kmalloc-16, kmalloc-32, … kmalloc-8192). kmalloc() rounds the requested size up to the nearest power-of-two size class and calls kmem_cache_alloc() on the matching cache. For allocations larger than KMALLOC_MAX_CACHE_SIZE (typically 8 KB), kmalloc() falls through to __get_free_pages() directly.
// include/linux/slab.h
static __always_inline void *kmalloc(size_t size, gfp_t flags)
{
if (__builtin_constant_p(size)) {
// compile-time: select exact size-class cache
if (size <= KMALLOC_MAX_CACHE_SIZE)
return kmalloc_fixed_size(size, flags);
}
return __kmalloc(size, flags);
}SLUB fast path: per-CPU freelist
kmem_cache_alloc() enters the SLUB fast path. Each CPU has a per-CPU slab (struct kmem_cache_cpu) with a freelist — a linked list of free objects within the current slab page. If the freelist is non-empty, SLUB pops the head object with a single cmpxchg (compare-and-swap) instruction — no lock, no cache-line contention. This is the common case and is extremely fast (< 10 ns on modern hardware). The object is returned to the caller immediately.
// mm/slub.c
static __always_inline void *slab_alloc_node(struct kmem_cache *s,
gfp_t gfpflags, int node, unsigned long addr)
{
void *object;
struct kmem_cache_cpu *c = raw_cpu_ptr(s->cpu_slab);
// fast path: pop from per-CPU freelist
object = c->freelist;
if (likely(object)) {
c->freelist = get_freepointer(s, object);
return object;
}
// slow path: refill
return __slab_alloc(s, gfpflags, node, addr, c);
}SLUB slow path: refill from partial list or allocate a new slab
If the per-CPU freelist is empty, __slab_alloc() is called. It first checks the node's partial slab list — slabs that have some free objects but are not completely empty. If a partial slab is found, it becomes the new per-CPU slab and its freelist is used. If no partial slabs exist, SLUB must allocate a brand-new slab page from the buddy allocator via allocate_slab() → alloc_slab_page() → __alloc_pages(). The new page is divided into fixed-size objects and the freelist is initialised.
// mm/slub.c
static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags,
int node, unsigned long addr,
struct kmem_cache_cpu *c)
{
// try node partial list
slab = get_partial(s, gfpflags, node, &object);
if (slab)
goto check_new_slab;
// allocate new slab from buddy
slab = new_slab(s, gfpflags, node);
// ...
}__alloc_pages() enters the buddy allocator
__alloc_pages() is the core page allocator entry point. It takes a GFP (Get Free Pages) flags mask and an order (2^order contiguous pages). It calls get_page_from_freelist() which iterates over memory zones (ZONE_DMA32, ZONE_NORMAL, ZONE_HIGHMEM) in the node's zonelist. For each zone it checks whether the free page count is above the zone's low watermark — if so, it calls rmqueue() to remove a block of the requested order from the buddy free lists.
// mm/page_alloc.c
struct page *__alloc_pages(gfp_t gfp, unsigned int order, int preferred_nid,
nodemask_t *nodemask)
{
// fast path: try preferred zone above low watermark
page = get_page_from_freelist(gfp, order, alloc_flags, &ac);
if (likely(page))
return page;
// slow path: reclaim, compact, OOM
return __alloc_pages_slowpath(gfp, order, &ac);
}Buddy allocator splits a free block
rmqueue() looks up the free list for the requested order. If a block of exactly the right order is available, it is removed and returned. If not, rmqueue() walks up the order levels until it finds a larger free block, then repeatedly splits it in half — each split produces a 'buddy' pair. One half satisfies the allocation; the other half is inserted into the free list at the next lower order. This splitting continues until the requested order is reached. The buddy system guarantees that any two adjacent same-size blocks can be coalesced back on free.
// mm/page_alloc.c
static struct page *rmqueue(struct zone *preferred_zone, struct zone *zone,
unsigned int order, gfp_t gfp_flags, ...)
{
// try exact order first
page = __rmqueue_smallest(zone, order, migratetype);
if (!page)
// steal from higher order or different migratetype
page = __rmqueue(zone, order, migratetype, alloc_flags);
return page;
}Slow path: kswapd wakes and reclaims pages
If get_page_from_freelist() fails (all zones below low watermark), __alloc_pages_slowpath() is entered. It first wakes kswapd — the kernel swap daemon — by calling wakeup_kswapd(). kswapd runs as a kernel thread and reclaims pages by writing dirty pages to disk (via the writeback subsystem) and swapping out anonymous pages to the swap device. The allocating process may also perform direct reclaim itself if the allocation is urgent (GFP_DIRECT_RECLAIM flag). After reclaim, the allocation is retried.
// mm/vmscan.c
static unsigned long shrink_zone(struct zone *zone,
struct scan_control *sc)
{
// reclaim file-backed pages (writeback)
shrink_active_list(nr_to_scan, lruvec, sc, LRU_ACTIVE_FILE);
// reclaim anonymous pages (swap)
shrink_active_list(nr_to_scan, lruvec, sc, LRU_ACTIVE_ANON);
return nr_reclaimed;
}Memory compaction coalesces fragmented free pages
Even after reclaim, the buddy allocator may fail for high-order allocations (order ≥ 3) due to fragmentation — enough total free pages exist but not as a contiguous block. The kernel runs memory compaction: compact_zone() migrates movable pages toward the top of the zone (using migrate_pages()) and free pages toward the bottom, creating large contiguous free regions. Compaction is triggered automatically in the slow path and can also be triggered manually via /proc/sys/vm/compact_memory.
// mm/compaction.c
static enum compact_result compact_zone(struct compact_control *cc)
{
// scan from bottom: find movable pages
// scan from top: find free pages
// migrate movable pages into free space at top
ret = migrate_pages(&cc->migratepages, compaction_alloc,
compaction_free, 0, MIGRATE_SYNC_LIGHT, ...);
return COMPACT_SUCCESS;
}OOM killer selects and kills a process as last resort
If reclaim and compaction both fail and the allocation cannot be satisfied, the kernel invokes the OOM (Out-Of-Memory) killer. out_of_memory() calls select_bad_process() which scores every process using oom_badness(). The score is proportional to the process's RSS (resident set size) and adjusted by its oom_score_adj value (settable via /proc/PID/oom_score_adj, range -1000 to +1000). The highest-scoring process is sent SIGKILL. After the victim exits and releases its pages, the allocation is retried.
// mm/oom_kill.c
static void select_bad_process(struct oom_control *oc)
{
for_each_process_thread(g, p) {
points = oom_badness(p, oc->totalpages);
if (points > oc->chosen_points) {
oc->chosen = p;
oc->chosen_points = points;
}
}
}
// oom_badness score = RSS + page_table_pages
// adjusted by /proc/PID/oom_score_adjKnowledge Check
// click each question to reveal the answer
Source References
// annotated entry points · Linux 7.2