Linux Kernel Memory Management: From Buddy System to SLUB Allocator

1. Introduction: Why Memory Management Matters

Memory management is arguably the most critical subsystem in the Linux kernel. Unlike user-space applications that rely on libc's malloc/free abstraction, the kernel must manage physical memory directly—balancing the competing demands of latency, fragmentation, throughput, and fairness across thousands of concurrent consumers. From page tables to per-CPU caches, every layer in the memory stack has been refined over three decades of production deployment.

This article provides an engineering-depth analysis of the Linux memory management subsystem: the Buddy System for physical page allocation, the SLAB/SLUB/SLOB allocators for kernel-object allocation, vmalloc for virtually-contiguous mappings, and the interaction between them. We will trace code paths, analyze algorithmic complexity, examine real-world tuning parameters, and benchmark allocator behavior under stress.

2. The Buddy System: Physical Page Allocation

The Buddy System is the foundational physical-memory allocator in Linux. It manages all physical pages organized by node (NUMA) and zone, fulfilling allocation requests in power-of-two page counts.

2.1 Data Structure and Invariants

Each NUMA node (struct pglist_data) contains multiple memory zones (struct zone), each maintaining an array of free area lists:

// include/linux/mmzone.h
struct zone {
    struct free_area    free_area[MAX_ORDER];
    ...
};

struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];
    unsigned long       nr_free;
};

MAX_ORDER is typically 11, giving allocation blocks from 4 KB (order 0) up to 4 MB (order 10). The key invariant: two blocks of size 2^N are "buddies" if their physical addresses differ by exactly 2^N pages—meaning they can be coalesced into a 2^(N+1) block.

2.2 Allocation Path

When alloc_pages(gfp_mask, order) is called:

1. The Buddy allocator searches free_area[order] for a free block of the exact order.
2. If none is found, it escalates to higher orders, splitting each in half recursively (creating buddy pairs) until the target size is reached.
3. The block is removed from the free list and returned to the caller.
4. If no block of any sufficient size exists, the page reclaim and compaction subsystems are invoked.

// mm/page_alloc.c (simplified)
struct page *alloc_pages(gfp_t gfp, unsigned int order)
{
    struct page *page = __alloc_pages(gfp, order);
    if (!page) {
        // Trigger direct reclaim
        page = __alloc_pages_direct_reclaim(gfp, order);
    }
    return page;
}

2.3 Coalescing on Free

When __free_pages(page, order) is called, the allocator checks whether the released block's buddy is also free. If so, they are coalesced into a block of order+1, and the check repeats for the next higher order. This recursive coalescing is what keeps long-running systems from fragmenting to death.

2.4 Page Migration and Fragmentation Control

Linux classifies pages into migrate types within each free area:

• MIGRATE_UNMOVABLE: Kernel data structures, page tables
• MIGRATE_MOVABLE: User-space pages, cache pages
• MIGRATE_RECLAIMABLE: Kernel caches that can be recomputed
• MIGRATE_ISOLATE: Temporarily isolated for hotplug

This typification enables memory compaction (kswapd compaction / /proc/sys/vm/compact_memory), which migrates movable pages to defragment unmovable allocations—critical for huge-page (THU/hugetlb) availability.

3. The SLAB Allocator: Kernel Object Caching

The Buddy System allocates in power-of-two page granularity. But many kernel objects—task_struct (about 7 KB), inode (about 600 B), dentry (about 200 B)—are far smaller than a page, and allocating an entire page for each would waste catastrophic amounts of memory. The SLAB allocator solves this by subdividing pages into same-size object caches.

3.1 Architecture Overview

SLAB uses a three-level hierarchy:

Cache (kmem_cache)     -- one per object type (e.g., "task_struct", "dentry")
  - Slab               -- one or more physical pages
       Object           -- individual allocated instance (free or in-use)

Each slab has a fixed number of objects. A slab can be full (all allocated), empty (all free), or partial (some allocated). The allocator maintains three lists per cache.

3.2 Slab Layout and Free Tracking

Modern SLAB uses an embedded free-list approach: free object slots store pointers to the next free object within the same slab, forming a linked list. This eliminates external metadata overhead entirely.

// mm/slab.h
struct slab {
    struct list_head list;       // full/partial/empty list
    unsigned long s_mem;         // pointer to first object
    unsigned int inuse;          // number of active objects
    unsigned int free;           // index of next free object
};

3.3 Allocation and Free Path

Allocation: kmem_cache_alloc(cache, flags)

1. Checks the per-CPU cache (a hot-path optimization with no locking).
2. On miss, finds a partial slab in the cache's partial list.
3. If no partial slab exists, allocates a new slab from the Buddy System (cache_grow_begin()).
4. Returns the first free object from the slab's free list.

Free: kmem_cache_free(cache, obj)

1. Places the object back on the per-CPU cache (fast path).
2. If the per-CPU cache is full, returns objects to the slab's free list.
3. If the slab becomes fully empty, it is returned to the Buddy System or kept on the empty list for rapid reuse.

3.4 Coloring and Cache Alignment

SLAB implements cache coloring: each slab is given a different offset within the page (colour_off) so that objects starting at different slab offsets land in different L1/L2 cache lines. This reduces aliasing conflicts and improves cache utilization significantly for tight loops over kernel structures.

4. SLUB: The Default Allocator

SLUB (the "unqueued" slab allocator) replaced SLAB as Linux's default in kernel 2.6.23. It addresses SLAB's fundamental complexity: SLAB's per-CPU and per-node queues created significant memory overhead and lock contention on large systems.

4.1 Key Design Decisions

• No per-CPU queues: Objects are freelist-linked directly through the slab. CPUs use a simple redirection through page->freelist and page->inuse counters.
• Embraces the Buddy System: SLUB does not manage its own page pools tightly; it relies on the page allocator and benefits from compaction directly.
• Deferred boot-time initialization: SLUB supports slab_nomerge for security isolation and slab_debug for corruption detection.

4.2 Locking Model

Each kmem_cache has a single struct kmem_cache_node per NUMA node with a spinlock protecting its partial list. In the common case (allocation from a per-CPU slab), no lock is taken. This is achieved through a CPU-local pointer race pattern:

// mm/slub.c (simplified CPU-quasi-local allocation)
static __always_inline void *slab_alloc(struct kmem_cache *s, gfp_t gfp)
{
    void *object = this_cpu_ptr(s->cpu_slab)->freelist;
    struct page *page = this_cpu_ptr(s)->page;
    
    if (unlikely(!object || !page || !node_match(page, node))) {
        return slab_alloc_node(s, gfp, node, addr);  // slow path
    }
    this_cpu_ptr(s)->freelist = get_freepointer(s, object);
    page->inuse++;
    return object;
}

4.3 Kmemcheck and KASAN Integration

SLUB natively supports KASAN (Kernel Address SANitizer): on allocation, KASAN poisons the object's memory; on free, it verifies no use-after-free. SLUB's freelist poisoning patterns (0x6b/0xa5 sentinels) combined with red-zone padding around objects make use-after-free and out-of-bounds bugs detectable at near-zero cost in production.

5. vmalloc: Virtually-Contiguous Memory

While kmalloc() returns physically-contiguous memory (required for DMA), vmalloc() provides virtually-contiguous mappings over physically dispersed pages. This is essential when large contiguous physical blocks are unavailable.

5.1 vmalloc Address Space

On x86-64, the vmalloc region occupies a large window in the kernel virtual address space:

# cat /proc/vmallocinfo | head
0xffffc90000000000-0xffffc90000020000   131072 alloc_large_pages+0x...
0xffffc90000020000-0xffffc90000021000    4096 vmalloc

5.2 Mapping Mechanism

vmalloc() updates the kernel page tables to map physical pages into a contiguous virtual range. This means every access might trigger a TLB miss (non-linear mapping), and page-table walks become 4–5 levels deep for unmapped regions. For this reason, vmalloc() is used only when physical contiguity is not required—e.g., module loading, large I/O buffers, video framebuffers that do not need DMA.

6. Performance Analysis and Benchmarks

6.1 Allocation Latency Comparison

Allocator	Request Size	Latency (cycles)	Contiguity
kmalloc (SLUB)	64 B – 8 KB	~50–120	Physical
kmalloc (SLUB)	8 KB – 4 MB	~200–800	Physical
vmalloc	4 KB – 64 MB	~5000–50000	Virtual
alloc_pages (Buddy)	4 KB+ (page-granular)	~500–2000	Physical
alloc_pages (huge, 2 MB)	2 MB	~5000+	Physical

6.2 Fragmentation Behavior

Long-running systems face the "slow fragmentation death" problem. After days of mixed allocations:

• Buddy System: External fragmentation prevents huge-page allocations (check /proc/pagetypeinfo).
• SLUB: Internal fragmentation is bounded at about 8–16 bytes per object. External fragmentation is mitigated because SLUB directly consumes from the Buddy allocator.
• Fragmentation Index: /proc/buddyinfo shows available blocks per order. A healthy system shows nonzero orders at order 10+.

6.3 NUMA Considerations

In multi-socket systems, SLUB defaults to local node allocation (objects come from the same NUMA node as the requesting CPU). This avoids cross-socket memory traffic, which can be 2–3× slower. The vm.zone_reclaim_mode sysctl controls whether the kernel reclaims local pages before falling back to remote nodes.

7. Tuning and Debugging

7.1 Critical Sysctl Parameters

# vm.min_free_kbytes -- minimum KB that must remain free (default: adaptive)
# vm.swappiness -- tendency to swap (0=dont swap, 100=aggressive, default: 60)
# vm.dirty_ratio -- percentage of memory at which writes block on dirty flush
# vm.vfs_cache_pressure -- tendency to reclaim dentry/inode caches (default: 100)
# vm.zone_reclaim_mode -- NUMA reclaim (0=disable, 1=enable)
# kernel.slab_max_order -- SLAB max order (controls slab size)
# vm.admin_reserve_kbytes -- memory reserved for root (default: 8192)

7.2 Diagnosing Memory Pressure

# /proc/meminfo -- high-level memory usage breakdown
# /proc/slabinfo -- per-cache object count, active, memory
# /proc/buddyinfo -- fragmentation per zone per order
# /proc/pagetypeinfo -- page-type aware fragmentation
# /proc/vmallocinfo -- vmalloc regions and callers
# /sys/kernel/slab/<cachename>/ -- per-cache active tuning parameters

7.3 Slub Debug Features

# Enable full SLUB debugging (boot parameter):
slub_debug=FZP     # F=trace, Z=repopulate redzones, P=poison
# Trace a specific cache:
slub_debug=-kmalloc-128   # Disable debug for 128-byte cache
# Check for slab corruption:
echo 1 > /sys/kernel/slab/dentry/validate

8. Future Evolution

The Linux memory management subsystem continues to evolve toward better performance at scale and stronger security guarantees:

• MGLRU (Multi-Gen LRU): Replaces the legacy active/inactive list model with generation-based eviction, reducing reclaim CPU overhead by ~40% (merged in 6.1).
• Damon (Data Access Monitor): Provides hardware-level page-access tracing for intelligent reclaim policies.
• Memory Folios: Introduces struct folio as a compound-page abstraction, reducing overhead for transparent-hugepage workloads.
• Cgroup-aware memory pressure: Future per-cgroup PSI (Pressure Stall Information) integration enables fine-grained QoS.
• HugeVM: Research into scalable hugetlbfs and 1 GB page support for ML/AI workloads.

9. Conclusion

The Linux memory management stack—Buddy System for physical pages, SLUB for kernel objects, vmalloc for virtual mappings, MGLRU for page reclaim—is a masterpiece of systems engineering. Understanding its internals is not academic: kernel engineers, driver developers, and performance tuners who grasp these layers can design subsystems that scale to millions of objects per second without fragmentation, tune NUMA latency to microseconds, and debug the most elusive memory corruption bugs. The code paths traced here (simplified) power every Linux server, mobile device, and supercomputer on Earth—and they are still improving.