OS: Slab Allocator for Kernel Memory

Efficient memory management inside an operating system kernel is a critical performance challenge. The kernel constantly allocates and frees small, frequently used data structures like task descriptors, network buffers, and file system inodes. A general-purpose allocator working with raw pages from the buddy system—an allocator that manages physical memory in power-of-two-sized chunks—would be too slow and wasteful for this task. The slab allocator solves this by acting as a specialized object cache, dramatically reducing allocation time, fragmentation, and initialization overhead for common kernel objects.

The Basic Slab Cache Model

At its heart, the slab allocator is built on the concept of object caching. Instead of asking the page-level buddy allocator for memory each time, the slab pre-allocates one or more complete pages of physical memory. It then divides this contiguous block, called a slab, into an array of equal-sized chunks, each large enough to hold one instance of a specific kernel data structure, such as a task_struct. This slab is then placed into a slab cache—a dedicated manager for objects of a single type.

This model provides several key advantages. First, it eliminates external fragmentation for these objects because all spaces within a slab are perfectly sized for the target data type. Second, by allocating objects from a pre-divided slab, the allocator performs a simple pointer increment or free list pop, which is far faster than searching a complex heap structure. Finally, and crucially, it allows for constructor and destructor functions. When a slab is first created, a constructor function can be called for each object in the slab to initialize it to a predefined state. This means when the kernel requests a new task_struct, it receives an already-initialized object, saving valuable CPU cycles.

Object Construction, Destruction, and State

The slab allocator tracks objects within a slab using a simple state machine. When a slab is first created from raw pages, all its objects are in a constructed, free state. Upon an allocation request, the allocator marks an object as allocated and returns its pointer; no construction is needed. When the kernel frees the object back to the slab cache, it transitions to a destructed, free state if a destructor function was invoked. This decouples memory management from object lifecycle.

Consider the workflow: A slab for inode objects is created. The constructor sets default locks and list heads. When the virtual file system needs a new inode, the slab provides a pre-initialized object instantly. When the file is deleted, the kernel calls kfree(). The slab's destructor might release ancillary resources, but the memory itself remains in the slab's free list, ready for the next allocation. This recycling of initialized objects is the core of the performance gain. A slab becomes empty when all its objects are free, and it can be returned to the buddy system, or it becomes full when all objects are allocated.

Cache Coloring and Cache Line Utilization

A subtle but important optimization in slab allocators is cache coloring. The fundamental problem is this: if every slab for a given cache starts its first object at the same offset within a page, consecutive allocations will map to identical set locations in the processor's data cache. This leads to cache line contention, where these objects evict each other, causing costly cache misses.

Cache coloring solves this by adding a color offset—a calculated amount of wasted space—to the front of each slab. The allocator calculates how many objects fit in a page, then determines how much leftover "slack" space remains. It divides this slack space by the size of a CPU cache line to get a number of possible colors. Each new slab created is assigned a different color, shifting the starting address of its object array by that color multiplied by the cache line size. This distributes objects across different cache sets, dramatically improving cache hit rates and overall system performance. The small internal fragmentation cost of the colored space is a worthy trade-off for the speed improvement.

Per-CPU Caching: The Magazine Layer

Even with slab caching, a global free list for objects requires locking to prevent race conditions between CPUs, which becomes a scalability bottleneck. Modern slab allocators like those in Linux (SLUB) and Solaris introduce a magazine layer for per-CPU caching, analogous to a person keeping a magazine of bullets in their gun rather than fetching each one from a central armory.

Each CPU is given its own small, lock-free cache of free objects, called a per-CPU slab cache or magazine. When a CPU needs to allocate an object, it first checks its own magazine. If full, it can refill its magazine from a global pool (the slab proper). When freeing, the object goes back into the CPU's local magazine. Only when the local magazine overflows does it flush a batch back to the global slab. This ensures that the frequent allocate/free operations on a single processor happen without any inter-CPU locking. The magazine layer sits logically atop the core slab allocator, which still handles the replenishment of the per-CPU caches and the management of full and empty slabs.

Common Pitfalls

1. Ignoring Slab Metadata Overhead: When designing or tuning a slab cache, forgetting to account for the allocator's own metadata (tracking free objects, slab management structures) can lead to incorrect object counts per slab. This reduces efficiency and can cause unexpected memory consumption.
2. Misusing Constructors and Destructors: Performing heavy, non-idempotent work in a constructor is dangerous, as objects are constructed in bulk when a slab is created. Destructors should only handle cleanup tied to the memory lifetime, not logical object state. Placing logic that belongs to the kernel subsystem (e.g., flushing file data) in the slab destructor creates tight, problematic coupling.
3. Neglecting Color Accounting in Size Calculations: When manually calculating object alignment or sizing, failing to consider that the slab allocator itself will add a color offset can break alignment assumptions for hardware that requires strictly aligned data accesses (e.g., DMA buffers).
4. Assuming Per-CPU Caches are Infinite: The magazine layer is a performance optimization, not infinite storage. Code that performs mass freeing in a loop can still trigger expensive flushes to the global pool. Understanding the batch size of your allocator is key for performance-sensitive paths.

Summary

• The slab allocator is a kernel-specific object cache that dramatically improves performance by pre-allocating and initializing pools (slabs) of identical-sized objects.
• It eliminates fragmentation for common kernel data structures and reduces allocation time to a simple pointer operation by maintaining objects in a constructed, ready state.
• Cache coloring introduces small, deliberate offsets to the start of object arrays within slabs to distribute memory accesses across CPU cache sets and prevent performance-degrading cache line contention.
• A magazine layer of per-CPU caches provides lock-free allocation and freeing on the fast path, allowing the slab allocator to scale efficiently on multi-processor systems.
• While the slab allocator handles small, frequent allocations, it works in concert with the page-level buddy system, which supplies it with the raw physical memory pages to be organized into slabs.