Slab Allocator Algorithm: Memory Management Deep Dive

1. Introduction and Core Concepts

The slab allocator algorithm is a specialized memory management technique designed to efficiently allocate and deallocate fixed-size objects that are frequently created and destroyed. Originally introduced by Jeff Bonwick in 1994 for the SunOS 5.4 kernel, the slab allocator was created to solve the performance bottlenecks and fragmentation problems associated with general-purpose allocators when handling kernel objects such as inodes, file descriptors, and network buffers. Unlike traditional heap allocators that must handle arbitrary allocation sizes, the slab allocator exploits the predictability of kernel object sizes to achieve near-constant time allocation with minimal fragmentation.

At its core, the slab allocator algorithm pre-allocates contiguous regions of memory called slabs, each dedicated to a single type or size of object. A slab is divided into equal-sized slots, each capable of holding exactly one object. By caching these initialized objects, the allocator avoids the expensive operations of repeatedly constructing and destructing objects, zeroing memory, and searching for suitable free blocks. This approach is particularly valuable in operating system kernels and high-performance user-space applications where allocation latency directly impacts throughput.

The importance of the slab allocator algorithm extends far beyond its original kernel context. It addresses three fundamental problems in memory management: internal fragmentation, external fragmentation, and allocation overhead. Internal fragmentation is minimized because objects perfectly fit their slots without wasted padding beyond alignment requirements. External fragmentation is reduced because slabs contain only identical objects, preventing the checkerboard pattern of free and allocated blocks of varying sizes. Allocation overhead is dramatically lowered through object caching and free-list management, turning expensive memory operations into simple pointer manipulations. Understanding this algorithm is essential for anyone working on systems programming, high-performance caching layers, or custom memory allocators.

Why Fixed-Size Allocation Matters

Most programs allocate many objects of the same size repeatedly. Web servers allocate request contexts, database engines allocate page frames, and network stacks allocate packet buffers. A general-purpose allocator like malloc must handle any size, which requires complex data structures such as free lists, buddy trees, or segregated fits. The slab allocator algorithm sidesteps this complexity by creating a separate cache for each object size or type, often called a kmem_cache in Linux terminology. Each cache maintains its own set of slabs, allowing allocation to become a simple pop from a free list.

This specialization also enables powerful optimizations such as constructor and destructor caching. When an object is freed, instead of returning its memory to the operating system and destroying its state, the slab allocator keeps it in a partially initialized state. The next allocation can reuse the object without re-running expensive initialization logic. This is especially beneficial for objects that require zeroing, locking primitives, or complex setup, saving hundreds of CPU cycles per allocation.

2. How It Works

The slab allocator algorithm operates on a three-tier hierarchy: caches, slabs, and objects. At the top level, a cache represents a pool for a specific object type or size. For example, a system might have a 32-byte cache, a 64-byte cache, and a dedicated inode cache. Each cache is responsible for managing all memory for that particular class of objects. The cache tracks its slabs and provides the public alloc and free interface to clients.

The middle tier is the slab itself. A slab is a contiguous block of memory, typically one or more physical pages, that is carved into equal-sized slots. Each slab has metadata that tracks which slots are free and which are allocated, along with linkage to the parent cache. Slabs within a cache are typically organized into three lists: empty, partial, and full. Empty slabs contain no allocated objects and can be reclaimed under memory pressure. Partial slabs have some allocated and some free objects and are the preferred source for new allocations. Full slabs are completely allocated and require no further bookkeeping until an object is freed.

At the bottom tier are the objects themselves. Each object slot contains the actual data plus optional per-object metadata such as a free-list pointer when the slot is unused. Allocation from a slab is performed by removing an entry from the slab's free list, marking it as allocated, and returning its address. Deallocation reverses this process by returning the slot to the free list. Because all objects in a slab are the same size, there is no need to search for a best-fit or first-fit block, and no splitting or coalescing is required.

Cache Coloring and Alignment

A critical optimization in the slab allocator algorithm is cache coloring, which addresses CPU cache conflicts. If all slabs start at the same offset relative to a page boundary, objects at the same offset within different slabs will map to the same set in a direct-mapped or set-associative CPU cache, causing conflict misses. To avoid this, the allocator adds a different offset, or color, to each slab. The color is a small amount of unused padding at the beginning of the slab, calculated as (slab_index * color_increment) % max_color. This spreads objects across different cache lines and can improve performance by 10-20% in cache-sensitive workloads.

Another key mechanism is the per-CPU or per-thread magazine layer, often called the slab's local cache. Instead of requiring a global lock for every allocation, each CPU maintains a small array of free objects. Allocations are first satisfied from the local magazine without locking. Only when the magazine is empty does the CPU refill it from the global partial list, and only when it overflows does it return objects to the global pool. This drastically reduces lock contention on multiprocessor systems and is a major reason for the slab allocator's scalability.

The Lifecycle of a Slab

When a cache is created, it starts with no slabs. On the first allocation, the allocator requests pages from the underlying page allocator, formats them as a new slab, initializes the free list, and allocates one object. As more allocations occur, the slab transitions from empty to partial to full. When objects are freed, the slab moves back from full to partial, and if all objects are freed, it becomes empty. Empty slabs are not immediately destroyed; they are kept for a short period to handle bursty allocation patterns, but a background reaper can reclaim them when the system is low on memory. This lifecycle ensures that memory usage adapts dynamically to workload demands while keeping hot objects cached.

3. Implementation

Implementing the slab allocator algorithm in user space requires careful management of free lists, slab states, and cache lookup. The following Python examples simulate the core logic without relying on low-level page management, making the concepts accessible while remaining faithful to the kernel implementation. Note that a production implementation in C would use intrusive linked lists and manual pointer arithmetic for maximum efficiency.

The first example implements a single slab that manages a fixed number of equal-sized objects. It demonstrates the fundamental alloc and free operations using an explicit free list and allocation bitmap.

# Single slab managing fixed-size objects
class Slab:
    def __init__(self, object_size, num_objects, color_offset=0):
        self.object_size = object_size
        self.num_objects = num_objects
        self.color_offset = color_offset
        # Simulate contiguous memory as bytearray
        self.memory = bytearray((object_size * num_objects) + color_offset)
        # Free list stores indices of available slots
        self.free_list = list(range(num_objects))
        self.allocated = [False] * num_objects
        self.free_count = num_objects
        self.state = "empty"  # empty, partial, full

    def _update_state(self):
        if self.free_count == self.num_objects:
            self.state = "empty"
        elif self.free_count == 0:
            self.state = "full"
        else:
            self.state = "partial"

    def alloc(self):
        """Allocate one object - O(1) time"""
        if self.free_count == 0:
            return None  # Slab is full, need new slab
        idx = self.free_list.pop()
        self.allocated[idx] = True
        self.free_count -= 1
        self._update_state()
        # Return index as handle; real allocator returns memory address
        offset = self.color_offset + (idx * self.object_size)
        return {"index": idx, "offset": offset}

    def free(self, idx):
        """Free one object - O(1) time"""
        if idx < 0 or idx >= self.num_objects:
            raise ValueError("Invalid index: out of bounds")
        if not self.allocated[idx]:
            raise ValueError("Double free detected at index " + str(idx))
        self.allocated[idx] = False
        self.free_list.append(idx)
        self.free_count += 1
        self._update_state()
        return True

    def is_empty(self):
        return self.free_count == self.num_objects

    def is_full(self):
        return self.free_count == 0

The next example builds a cache that manages multiple slabs and implements the classic empty, partial, and full lists. It also includes a simple cache coloring strategy and a per-cache free object count.

class SlabCache:
    def __init__(self, name, object_size, objects_per_slab=8, max_colors=4):
        self.name = name
        self.object_size = object_size
        self.objects_per_slab = objects_per_slab
        self.max_colors = max_colors
        self.next_color = 0
        self.empty_slabs = []
        self.partial_slabs = []
        self.full_slabs = []
        self.total_allocated = 0
        self.total_slabs = 0

    def _create_slab(self):
        # Cache coloring: rotate offset to avoid CPU cache conflicts
        color = (self.next_color * 8) % (self.max_colors * 8)
        self.next_color = (self.next_color + 1) % self.max_colors
        slab = Slab(self.object_size, self.objects_per_slab, color_offset=color)
        self.empty_slabs.append(slab)
        self.total_slabs += 1
        return slab

    def _move_slab(self, slab, from_list, to_list):
        if slab in from_list:
            from_list.remove(slab)
            to_list.append(slab)

    def alloc(self):
        """Allocate from partial slab, or empty slab, or create new slab"""
        # Prefer partial slabs to improve locality
        target_slab = None
        if len(self.partial_slabs) > 0:
            target_slab = self.partial_slabs[0]
        elif len(self.empty_slabs) > 0:
            target_slab = self.empty_slabs[0]
        else:
            target_slab = self._create_slab()

        prev_state = target_slab.state
        result = target_slab.alloc()
        new_state = target_slab.state

        # Update cache-level lists based on state transition
        if prev_state == "empty" and new_state == "partial":
            self._move_slab(target_slab, self.empty_slabs, self.partial_slabs)
        elif prev_state == "partial" and new_state == "full":
            self._move_slab(target_slab, self.partial_slabs, self.full_slabs)

        if result is not None:
            self.total_allocated += 1
        return result

    def free(self, slab, idx):
        prev_state = slab.state
        slab.free(idx)
        new_state = slab.state
        self.total_allocated -= 1

        # Move slab between lists on state change
        if prev_state == "full" and new_state == "partial":
            self._move_slab(slab, self.full_slabs, self.partial_slabs)
        elif prev_state == "partial" and new_state == "empty":
            self._move_slab(slab, self.partial_slabs, self.empty_slabs)

    def reclaim_empty_slabs(self):
        """Reaper: return empty slabs to page allocator"""
        reclaimed = len(self.empty_slabs)
        self.empty_slabs = []
        self.total_slabs -= reclaimed
        return reclaimed

For multiprocessor scalability, modern slab allocators add a per-CPU magazine layer. The following code simulates this optimization, showing how local caches reduce global lock contention.

class MagazinedSlabCache(SlabCache):
    def __init__(self, name, object_size, objects_per_slab=8, magazine_size=4):
        super().__init__(name, object_size, objects_per_slab)
        self.magazine_size = magazine_size
        # Simulate per-CPU magazines with a dict keyed by cpu_id
        self.magazines = {}  # cpu_id -> list of free objects
        self.cpu_alloc_count = {}

    def _get_magazine(self, cpu_id):
        if cpu_id not in self.magazines:
            self.magazines[cpu_id] = []
            self.cpu_alloc_count[cpu_id] = 0
        return self.magazines[cpu_id]

    def alloc_fast(self, cpu_id=0):
        """Fast path: try per-CPU magazine first"""
        mag = self._get_magazine(cpu_id)
        if len(mag) > 0:
            self.cpu_alloc_count[cpu_id] += 1
            return mag.pop()

        # Slow path: refill magazine from global partial slabs
        refill_count = self.magazine_size // 2
        for _ in range(refill_count):
            obj = super().alloc()
            if obj is not None:
                mag.append(obj)
        if len(mag) > 0:
            self.cpu_alloc_count[cpu_id] += 1
            return mag.pop()
        return None

    def free_fast(self, obj, cpu_id=0):
        """Fast path: return to per-CPU magazine"""
        mag = self._get_magazine(cpu_id)
        mag.append(obj)
        # If magazine overflows, flush half back to global cache
        if len(mag) > self.magazine_size:
            flush_count = self.magazine_size // 2
            for _ in range(flush_count):
                flushed = mag.pop()
                # In real implementation, return to slab's free list
                # Here we simulate by tracking
                pass

The final example demonstrates a higher-level allocator that manages multiple caches for different object sizes, similar to how the Linux SLAB/SLUB allocator provides kmalloc for generic allocations.

class SlabAllocator:
    def __init__(self):
        # Create caches for common power-of-two sizes
        self.caches = {}
        sizes = [32, 64, 128, 256, 512, 1024]
        for sz in sizes:
            self.caches[sz] = SlabCache(f"cache-{sz}", sz, objects_per_slab=16)

    def _find_cache(self, size):
        # Find smallest cache that fits requested size
        for cache_size in sorted(self.caches.keys()):
            if size <= cache_size:
                return self.caches[cache_size]
        return None

    def kmalloc(self, size):
        """Generic allocation like Linux kmalloc"""
        cache = self._find_cache(size)
        if cache is None:
            raise MemoryError("Requested size too large: " + str(size))
        return cache.alloc()

    def kfree(self, cache_size, slab_ref, idx):
        cache = self.caches.get(cache_size)
        if cache is None:
            raise ValueError("Invalid cache size")
        cache.free(slab_ref, idx)

    def stats(self):
        result = []
        for sz, cache in sorted(self.caches.items()):
            result.append({
                "size": sz,
                "slabs": cache.total_slabs,
                "allocated": cache.total_allocated,
                "empty": len(cache.empty_slabs),
                "partial": len(cache.partial_slabs),
                "full": len(cache.full_slabs)
            })
        return result

# Example usage
allocator = SlabAllocator()
obj1 = allocator.kmalloc(40)   # Uses 64-byte cache
obj2 = allocator.kmalloc(100)  # Uses 128-byte cache
print(allocator.stats())

4. Step-by-Step Example

Consider a concrete scenario where a web server needs to manage 32-byte request context objects. We configure a slab cache with 4 objects per slab and walk through a sequence of allocations and deallocations to see how the slab allocator algorithm manages state transitions and memory reuse.

Initially, the cache is empty with no slabs. The first request arrives and calls alloc. The cache finds no partial or empty slabs, so it creates Slab A with color offset 0. Slab A contains slots [0,1,2,3], all free. The allocator pops index 3, marks it allocated, and returns it. Slab A now has 3 free slots, so it moves from the empty list to the partial list. The cache state is: partial=[A], empty=[], full=[], total_allocated=1.

Three more requests arrive in quick succession. Each alloc is satisfied from Slab A: index 2, then 1, then 0. After the fourth allocation, Slab A has 0 free slots and transitions to full. The cache now has partial=[], full=[A]. A fifth request arrives; since no partial slabs exist, the cache creates Slab B with color offset 8, allocates index 3 from it, and places Slab B in the partial list. At this point, we have full=[A], partial=[B] with 3 free slots remaining in B, and total_allocated=5.

Now two requests complete and their contexts are freed. Suppose we free index 1 from Slab A and index 3 from Slab B. Slab A moves from full to partial because it now has 1 free slot. Slab B remains partial but its free count increases from 3 to 4. The cache now has partial=[A,B], full=[]. This state is ideal because future allocations can be satisfied from either partial slab without creating new slabs. If we then free all remaining objects in Slab B, it becomes empty and could be reclaimed by the reaper if memory pressure occurs, while Slab A remains partial to handle the steady-state load.

Visualizing State Transitions

This example highlights the key invariant: the allocator always prefers partial slabs over empty slabs, and empty slabs over creating new slabs. This policy maximizes memory utilization and keeps the number of slabs proportional to the peak concurrent allocations, not the total number of allocations over time. The free list within each slab ensures that deallocated slots are immediately reusable without any global search, and cache coloring ensures that Slab A and Slab B do not thrash the same CPU cache lines even though they hold identical object types.

In a multithreaded environment with magazines, the sequence would be even faster. Each CPU core would maintain a local magazine of 2-4 pre-allocated objects. The first few allocations on a core would refill the magazine from the global partial list in bulk, then subsequent allocations would be satisfied with a simple array pop without acquiring any global lock. This batching amortizes the cost of global synchronization and is crucial for high-throughput servers handling tens of thousands of requests per second.

5. Complexity Analysis

The slab allocator algorithm is prized for its predictable, constant-time performance. Unlike general allocators that may need to traverse free lists or coalesce blocks, slab allocation is essentially a stack operation on a free list. This section analyzes the time and space complexity in detail, including the impact of the magazine layer and reclamation.

Allocation in the fast path, where a partial slab or per-CPU magazine has a free object, is O(1) with very low constants. It involves popping an index from a list, updating a state flag, and returning a pointer. No loops or searches are required. The slow path, which creates a new slab by requesting pages from the operating system, is O(n) where n is the number of objects per slab, because the free list must be initialized. However, this cost is amortized over many allocations, so the average remains O(1). Deallocation is always O(1) as it simply pushes the index back onto the free list and updates the slab state.

Space overhead comes from three sources: per-slab metadata, per-object free-list pointers, and internal fragmentation due to rounding up to the nearest cache size. Per-slab metadata is typically a few dozen bytes for the free count, color, and list pointers, which is negligible when amortized over 32-64 objects per slab. Per-object overhead is one pointer when the object is free, stored directly in the unused slot itself, so no extra memory is needed. Internal fragmentation is the dominant overhead and depends on the cache size granularity; with power-of-two caches, worst-case waste is just under 50% for sizes just over a power of two, but average waste is around 20-25% in practice.

In the table, k denotes objects per slab, s denotes number of empty slabs, and C denotes number of caches. The logarithmic lookup for kmalloc assumes caches are stored in a sorted array or balanced tree; a direct-mapped size-to-cache table can achieve O(1). The reclamation operation is linear in the number of empty slabs but is performed infrequently by a background thread, so it does not affect foreground allocation latency. Overall, the slab allocator provides excellent temporal locality and cache behavior, which often matters more than asymptotic complexity in real systems.

6. Variations and Optimizations

The original slab allocator has evolved into several variants, each optimizing for different trade-offs between complexity, scalability, and memory efficiency. The three most prominent are SLAB, SLUB, and SLOB in the Linux kernel, along with user-space adaptations like jemalloc and tcmalloc that incorporate slab-like principles.

The classic SLAB allocator maintains the three-list structure with full queueing, per-CPU magazines, and extensive debugging features such as red-zoning and poisoning. It excels at caching constructed objects and provides detailed statistics, but its metadata overhead and queue management can be heavy for small systems. SLUB, introduced in Linux 2.6.23, simplifies the design by eliminating the per-CPU magazines and the three lists in favor of a simpler per-CPU partial list and direct page allocation. SLUB reduces metadata overhead, improves NUMA locality by keeping slabs node-local, and performs better for the common case of allocating from the local CPU. It is now the default in most Linux distributions.

SLOB, the Simple List Of Blocks, is designed for embedded systems with tiny memory footprints. It abandons the slab concept altogether and uses a simple first-fit list with minimal metadata, trading performance for code size and memory savings. For user-space allocators, jemalloc uses slab-like runs for small allocations, grouping them into size classes and using per-thread caches similar to magazines. tcmalloc from Google uses a central page heap with per-thread slab caches for small objects, achieving excellent scalability for multithreaded workloads. Another optimization is slab merging, where caches with similar sizes are merged to reduce the number of caches and improve utilization, at the cost of slightly higher internal fragmentation.

Advanced Techniques

Beyond the major variants, several advanced optimizations are widely deployed. NUMA-aware allocation places slabs on the memory node closest to the CPU that will use them, reducing remote memory access latency. Huge page backing uses 2MB or 1GB pages for slabs to reduce TLB misses for large caches. Delayed reclamation keeps empty slabs for a configurable time to handle bursty workloads without repeatedly allocating and freeing pages. Debugging features include slab poisoning, where freed memory is filled with a pattern to detect use-after-free, and red zones, where guard bytes are placed around objects to detect buffer overflows.

Object-specific optimizations include constructor caching, where the allocator calls a constructor on allocation and a destructor on free, allowing objects to remain in a hot, initialized state. This is particularly effective for objects containing locks or reference counts that are expensive to initialize. Some allocators also implement slab prefetching, where the next free object is prefetched into the CPU cache during allocation, hiding memory latency for sequential allocation patterns.

7. Real-World Applications

The slab allocator algorithm is ubiquitous in systems where predictable latency and high throughput are critical. Its most famous deployment is in operating system kernels, but it has also been adapted for user-space infrastructure such as web servers, databases, and network appliances. The following table summarizes key use cases and the specific benefits the slab allocator provides in each domain.

In web servers, the slab allocator pattern is often implemented as memory pools. Nginx, for example, allocates a large slab for each connection and then sub-allocates request data from it, freeing the entire slab when the connection closes. This avoids per-request malloc overhead and improves cache locality. Memcached famously uses slab classes to store cached items: each slab class holds items of a specific size range, and the allocator assigns items to the smallest fitting class. This prevents fragmentation when items of varying sizes are cached and evicted, a problem that would cripple a general-purpose allocator under long-running cache workloads.

In high-speed networking, the Data Plane Development Kit (DPDK) uses slab-like mempools for packet buffers. Each CPU core has a local cache of mbufs, and packets are allocated and freed at line rate, often exceeding 10 million packets per second. The slab's O(1) guarantee and cache coloring are essential to meet these rates without dropping packets. Similarly, database engines like PostgreSQL and MySQL use slab caches for buffer pool pages and lock table entries, where allocation latency directly affects transaction throughput. By keeping hot database pages in slab caches backed by huge pages, these systems reduce TLB misses and improve query performance by measurable margins.

8. Comparison with Alternatives

Choosing a memory allocator involves trade-offs between fragmentation, allocation speed, scalability, and implementation complexity. The slab allocator algorithm is not a universal replacement for all allocators but excels in specific scenarios. The table below compares it against the most common alternatives: the buddy system, segregated free lists, and simple sequential fits.

The buddy system, used for page allocation in kernels, splits and merges power-of-two blocks. It is simple and handles arbitrary sizes but suffers from high internal fragmentation and logarithmic allocation time due to splitting. The slab allocator is typically layered on top of the buddy system: the buddy system provides pages, and the slab allocator carves those pages into fine-grained objects. This two-level design combines the strengths of both.

Segregated free lists, as used in many malloc implementations, maintain separate free lists for different size classes, similar to slabs but without the slab abstraction. They handle variable sizes better than slabs but lack object caching and cache coloring, and they can still suffer from fragmentation when size classes are not carefully tuned. First-fit and best-fit allocators scan a single free list for a suitable block, leading to O(n) allocation time and severe external fragmentation over time, making them unsuitable for long-running servers. The slab allocator's key advantage is its specialization: by restricting each cache to one size, it eliminates search and coalescing, achieving both speed and fragmentation resistance that general allocators cannot match for fixed-size workloads.

9. Common Mistakes and Best Practices

Implementing or using the slab allocator algorithm incorrectly can lead to subtle bugs, memory leaks, and performance regressions. One of the most common mistakes is using the slab allocator for variable-sized or rarely allocated objects. If object sizes vary widely or allocations are infrequent, the overhead of maintaining a dedicated cache outweighs the benefits, and internal fragmentation can waste significant memory. In such cases, a general-purpose allocator or a simple pool is more appropriate. A good rule of thumb is to use slabs only for objects that are allocated at least hundreds of times per second or that have expensive construction costs.

Another frequent pitfall is ignoring alignment and false sharing. Objects that are accessed by different CPU cores should not share the same cache line, otherwise performance will suffer due to cache coherence traffic. The slab allocator should pad objects to cache line boundaries when necessary and use cache coloring to distribute slabs across cache sets. Failing to do so can cause a 2-3x slowdown in multithreaded benchmarks even though allocation appears fast in isolation. Similarly, not considering NUMA topology when placing slabs can lead to remote memory accesses that dominate latency.

Double frees and use-after-free errors are particularly dangerous with slab allocators because freed objects remain in the cache and may be quickly reallocated. Without debugging features, these bugs can corrupt the free list and cause silent data corruption. Best practices include enabling poisoning and red-zoning in debug builds, using guard pages, and integrating with sanitizers like AddressSanitizer. In production, the allocator should validate free operations by checking that the pointer belongs to the correct cache and slab, and that the slot is currently allocated.

Best Practices for Production Use

• Size your slabs appropriately: Choose objects_per_slab to balance between page utilization and reclamation granularity. Too few objects per slab wastes pages, too many increases the cost of slab creation and reclamation. A common choice is to fill one or two pages per slab.
• Implement a reaper with hysteresis: Do not immediately reclaim empty slabs; keep them for a few seconds to handle bursts. Reclaim only when memory pressure is high or when the number of empty slabs exceeds a threshold, such as 25% of total slabs.
• Use per-CPU magazines for scalability: Even a small magazine of 4-8 objects per CPU can reduce global lock contention by over 90%. Batch refill and flush operations to amortize synchronization costs.
• Monitor fragmentation and utilization: Export metrics for total slabs, empty/partial/full counts, and allocation rates per cache. Alert when internal fragmentation exceeds 30% or when empty slabs accumulate, indicating a possible memory leak.
• Prefer SLUB over SLAB for modern kernels: Unless you need extensive debugging or object caching, SLUB's simpler design and lower overhead make it the better default choice for most workloads.
• Test with realistic allocation patterns: Benchmark with production-like size distributions and lifetimes. Synthetic benchmarks that allocate and free in a tight loop may hide fragmentation or magazine overflow issues that appear under real traffic.

10. Interview Questions

Interviewers often use the slab allocator algorithm to assess understanding of systems programming, memory management, and performance optimization. The following questions are commonly asked, along with guidance on what constitutes a strong answer.

Q1: Why is the slab allocator faster than malloc for fixed-size objects?

A strong answer should explain that malloc must handle arbitrary sizes, requiring a search for a suitable free block, potential splitting, and coalescing on free, all of which are O(n) or O(log n). The slab allocator, by contrast, knows all objects are the same size, so allocation is a simple pop from a free list, O(1) with no search. It also caches constructed objects, avoiding repeated initialization, and uses per-CPU magazines to avoid locking. Mention cache coloring and reduced fragmentation as additional performance benefits, and note that the slab is layered on top of the page allocator, so it benefits from bulk page allocation.

Q2: How does the slab allocator handle fragmentation, and what are its limitations?

Explain that internal fragmentation is minimized because objects exactly fit slots, with only alignment padding wasted. External fragmentation is virtually eliminated because slabs contain only identical objects, so there are no interleaved free blocks of different sizes. However, the slab allocator can still suffer from internal fragmentation when used for generic kmalloc with power-of-two size classes, where a 65-byte request wastes 63 bytes in a 128-byte cache. Also, if a cache has many partial slabs with low occupancy, memory is underutilized. Discuss slab merging and careful size class selection as mitigations, and note that the slab allocator is not suitable for large, variable-sized allocations where a buddy system or vmalloc is better.

Q3: Explain cache coloring and per-CPU magazines. Why are they important?

Cache coloring addresses CPU cache conflicts: without it, objects at the same offset in different slabs map to the same cache set and evict each other, causing misses. By adding a small offset to each slab, the allocator spreads objects across cache lines. Per-CPU magazines address scalability: without them, every allocation would contend on a global lock. Magazines allow each CPU to allocate from a local array without locking, refilling in batches from the global pool. Together, these optimizations can improve throughput by 20-50% on multicore systems. A good answer will quantify the impact and explain the trade-off of slightly higher memory usage for magazines.

Q4: Design a slab allocator for a user-space cache like Memcached. How would you handle varying item sizes?

This is a system design question. A strong answer proposes creating multiple slab classes for size ranges, such as 64, 128, 256 bytes, and assigning each item to the smallest fitting class. Discuss the trade-off between number of classes and internal fragmentation, and how to handle items larger than the largest class by falling back to malloc or direct page allocation. Mention rebalancing: if one class is full while another has empty slabs, consider slab reassignment or slab automove. Also cover expiration and eviction: when items expire, their slots are returned to the free list, and empty slabs can be reclaimed. Include monitoring, thread safety with per-thread caches, and how to avoid slab calcification where memory is stuck in the wrong class.

Q5: What happens when a slab becomes empty, and when should it be reclaimed?

Explain the slab lifecycle: empty to partial to full and back. When a slab becomes empty, it is moved to the empty list but not immediately freed, to handle bursty patterns where the same objects are quickly reallocated. Reclamation is typically performed by a background reaper thread that runs periodically or when memory pressure is high, freeing empty slabs back to the page allocator. Discuss hysteresis: reclaim only if the number of empty slabs exceeds a threshold or if the system is low on memory, to avoid thrashing. Mention that holding empty slabs improves allocation latency for the next burst but wastes memory, so tuning the reaper interval is a key operational parameter.