How Linux’s Buddy System and SLUB Allocator Power Efficient Memory Management

Linux Memory Management Overview

The Linux kernel uses a two‑layer memory manager: the buddy system for allocating large contiguous physical pages and the SLUB allocator for fast allocation of small kernel objects.

Buddy System

Concept

Physical memory is divided into blocks whose sizes are powers of two (orders). Each order has its own free list, enabling O(1) allocation of a block of size 2^k pages.

Key Data Structures

struct free_area { struct list_head free_list; unsigned long nr_free; };
#define MAX_ORDER 11
struct zone { struct free_area free_area[MAX_ORDER]; unsigned long zone_start_pfn; unsigned long zone_end_pfn; const char *name; };
struct pglist_data { struct zone node_zones[MAX_NR_ZONES]; };

Allocation Flow

#include <linux/mm.h>
#include <linux/gfp.h>
static int __init buddy_alloc_init(void)
{
    int order = 2;               // request 4 contiguous pages
    gfp_t gfp_mask = GFP_KERNEL;
    unsigned long addr = __get_free_pages(gfp_mask, order);
    if (!addr) {
        pr_err("Buddy: allocation failed
");
        return -ENOMEM;
    }
    pr_info("Buddy: allocated order=%d at 0x%lx
", order, addr);
    free_pages(addr, order);
    pr_info("Buddy: memory released
");
    return 0;
}
module_init(buddy_alloc_init);
MODULE_LICENSE("GPL");

Freeing and Merging

When a block is freed the kernel computes its buddy with buddy = page_num ^ (1UL << order). If the buddy is also free, the two blocks are merged into the next higher order, recursively.

#include <stdio.h>
unsigned long get_buddy_page(unsigned long page_num, int order)
{
    return page_num ^ (1UL << order);
}
void buddy_free_and_merge(unsigned long page_num, int order)
{
    while (order < 10) {
        unsigned long buddy = get_buddy_page(page_num, order);
        printf("Merging order %d block %lu with buddy %lu
", order, page_num, buddy);
        page_num = (page_num < buddy) ? page_num : buddy;
        order++;
    }
}

SLUB Allocator

Concept

SLUB replaces the older slab allocator to provide low‑latency allocation of frequently used small objects (e.g., task_struct, inode). It reduces internal fragmentation and lock contention on SMP systems.

Architecture

Cache : per‑type container (e.g., task_struct_cache).

Slab : one or more contiguous pages split into equal‑size objects.

Object : the actual memory chunk handed to the kernel.

Key Structures

struct kmem_cache_cpu { void **freeobj; struct page *page; struct page *partial; unsigned long nr_slabs; };
struct kmem_cache {
    struct kmem_cache_cpu __percpu *cpu_slab;
    struct list_head partial;
    unsigned int object_size;
    unsigned int order;
};

Allocation Path

Try the per‑CPU cache.

If empty, replenish from the global partial list.

If still empty, request a new page from the buddy system and create a fresh slab.

#include <linux/slab.h>
static int __init slub_alloc_init(void)
{
    struct file *f = kmalloc(sizeof(*f), GFP_KERNEL);
    if (!f) {
        pr_err("SLUB: allocation failed
");
        return -ENOMEM;
    }
    pr_info("SLUB: allocated object of size %zu
", sizeof(*f));
    return 0;
}
module_init(slub_alloc_init);
MODULE_LICENSE("GPL");

Freeing Path

Objects are returned to the per‑CPU cache; when the cache exceeds a threshold, excess objects are moved to the global partial list. Completely free slabs are handed back to the buddy system.

#include <linux/slab.h>
static int __init slub_free_init(void)
{
    void *obj = kmalloc(64, GFP_KERNEL);
    if (!obj) return -ENOMEM;
    kfree(obj);
    return 0;
}
module_init(slub_free_init);
MODULE_LICENSE("GPL");

Comparison

Performance

Buddy excels at large allocations (multiple pages) but may require several splits.

SLUB provides ~30 % faster allocation and ~25 % faster reclamation for sub‑page objects under high‑frequency workloads.

Fragmentation

Buddy’s fixed‑order scheme can cause internal fragmentation (e.g., a 12 KB request may allocate a 16 KB block).

SLUB’s per‑type slabs keep internal fragmentation low, reducing it by ~15 % in micro‑benchmarks.

Typical Use‑Cases

Buddy: page‑cache buffers, video/audio buffers, large I/O.

SLUB: process descriptors, inode structures, network connection objects.

Practical Scenarios

Server Example

#define SMALL_OBJ_SIZE 256
#define LARGE_ORDER 3   // 2^3 = 8 pages
static int __init server_mem_init(void)
{
    void *small = kmalloc(SMALL_OBJ_SIZE, GFP_KERNEL);
    unsigned long large = __get_free_pages(GFP_KERNEL, LARGE_ORDER);
    /* ... use memory ... */
    kfree(small);
    free_pages(large, LARGE_ORDER);
    return 0;
}
module_init(server_mem_init);
MODULE_LICENSE("GPL");

Embedded Example

#define EMBED_SMALL_OBJ 128
#define EMBED_LARGE_ORDER 2   // 2^2 = 4 pages
static int __init embed_mem_init(void)
{
    void *drv = kzalloc(EMBED_SMALL_OBJ, GFP_KERNEL);
    unsigned long buf = __get_free_pages(GFP_KERNEL|GFP_DMA32, EMBED_LARGE_ORDER);
    /* ... */
    kfree(drv);
    free_pages(buf, EMBED_LARGE_ORDER);
    return 0;
}
module_init(embed_mem_init);
MODULE_LICENSE("GPL");

Conclusion

The buddy system provides robust management of large contiguous blocks and mitigates external fragmentation, while SLUB delivers high‑speed allocation for the kernel’s myriad small objects. Understanding their algorithms, data structures, and interaction allows kernel developers to tune memory performance for servers, desktops, and embedded platforms.