Slab Allocation for Systems Kernels

In this lesson, you will learn how to implement a slab allocator to achieve deterministic memory performance and eliminate fragmentation for high-frequency, fixed-size object allocation in kernel environments.

The Problem: Fragmentation

When a systems kernel constantly allocates and deallocates objects of the same size (like TaskControlBlock or BufferDescriptor), the general-purpose heap inevitably suffers from external fragmentation. Over time, free memory becomes a collection of non-contiguous holes, leading to allocation failures even when sufficient total memory is available.

The Slab Strategy

A Slab Allocator solves this by pre-allocating a large, contiguous chunk of memory—a "slab"—and subdividing it into equal-sized slots. Because every slot is identical, the kernel can allocate and free these objects in $O(1)$ time without searching for fit.

In Rust, we manage this by maintaining a linked list of free slots within the slab itself. When a slab is initialized, we treat the unallocated memory as a chain of pointers.

struct SlabNode {
    next: Option<*mut SlabNode>,
}

pub struct Slab<T> {
    memory: *mut T,
    free_list: Option<*mut SlabNode>,
    // Metadata for tracking slab capacity
}

impl<T> Slab<T> {
    pub fn allocate(&mut self) -> *mut T {
        if let Some(node) = self.free_list {
            // Pop from free list
            self.free_list = unsafe { (*node).next };
            node as *mut T
        } else {
            panic!("Slab exhausted!");
        }
    }

    pub fn deallocate(&mut self, ptr: *mut T) {
        // Push back onto free list
        let node = ptr as *mut SlabNode;
        unsafe {
            (*node).next = self.free_list;
            self.free_list = Some(node);
        }
    }
}

Architectural Benefits

By partitioning memory by object type, we gain three distinct advantages:

1. Cache Locality: Related objects reside in a contiguous memory block, improving CPU cache hit rates.
2. Deterministic Latency: We replace complex heap search algorithms (like First-Fit or Best-Fit) with a simple pointer swap.
3. Internal Fragmentation Control: Since every slot perfectly fits the object type, the internal waste is virtually eliminated, keeping the kernel’s memory footprint stable over weeks of uptime.

Key Takeaway: Slab allocation prevents long-term heap fragmentation by segregating memory usage into uniform slots, ensuring that the kernel can perform constant-time allocations without relying on unpredictable heap state.