The Slab Allocator

Slab Allocator

Unit of allocation

One cache per object type/size

Slab source

One or more contiguous physical pages

Allocation cost

O(1): pop a free slot

Typical use

Fixed-size kernel structs (task, inode, ...)

Slab allocation is the allocator design production kernels use for a case a general-purpose free list handles poorly: allocating and freeing large numbers of same-sized, fixed-type structures (a task struct, an inode, a network buffer) at high frequency. Heap Allocators covers the general-purpose free-list model in depth but only touches on alternative designs, without going into any of them.

Why a general-purpose allocator struggles here

A free-list allocator has no notion of the objects it’s handing out; every request, regardless of what the caller intends to store in it, competes for space in the same pool of variously-sized free blocks, which produces two costs a workload dominated by one fixed-size, frequently-churned type pays repeatedly. First, satisfying a request means walking the free list looking for a block that fits, work proportional to how fragmented the heap currently is rather than a fixed cost; second, allocating and freeing same-sized objects in an unpredictable order leaves behind a scattered pattern of free and used blocks of that exact size, fragmentation that a generic allocator has no way to prevent since it has no way to know in advance that the same size will keep recurring.

The core idea

A slab allocator sidesteps both costs by giving each distinct object type its own dedicated cache, backed by one or more slabs, contiguous regions of memory (commonly one or a small number of physical pages) pre-divided into fixed-size slots, each exactly large enough for one instance of that cache’s object type and nothing else.

struct kmem_cache {
    size_t   obj_size;
    void    *free_list;   // singly-linked list threaded through free slots
    void    *slab_base;
};

void *kmem_cache_alloc(struct kmem_cache *cache) {
    void *obj = cache->free_list;
    if (obj) cache->free_list = *(void **)obj;  // next free slot's address
    return obj;
}

void kmem_cache_free(struct kmem_cache *cache, void *obj) {
    *(void **)obj = cache->free_list;
    cache->free_list = obj;
}

Because every slot in a slab is identical in size, a free slot can hold nothing but a pointer to the next free slot, threading every unused slot in the slab into a simple singly-linked list with no search involved: allocation is popping the list head, and freeing is pushing back onto it, both O(1) regardless of how many objects the cache currently holds or how fragmented the rest of the system’s memory is. This is what eliminates the free-list-walking cost entirely, and since every slot is pre-sized to exactly one object, there’s no varying-size gap left behind by a freed object for a differently-sized request to partially fill or fail to fit, which is what eliminates the fragmentation a generic allocator suffers for this same workload.

Growing and shrinking a cache

A cache with no free slots left allocates a new slab from the underlying page allocator, formats it into slots the same size as every other slab in that cache, and threads them onto the free list the same way the cache’s very first slab was; a cache is therefore a variable number of slabs, growing as demand for that specific object type increases. Some implementations go further and keep freed objects pre-constructed: a slab’s slots are initialized once when the slab is first created, and freeing an object that has a non-trivial constructor (setting up embedded locks or list heads, for instance) leaves that internal state intact rather than tearing it down, so the next allocation from that same slot skips reconstruction entirely and only needs to reset whatever fields the specific new use actually requires, avoiding repeated constructor cost for objects that cycle through allocation and freeing rapidly.

Implementation notes

A slab allocator is a complement to a general-purpose heap allocator, not a replacement for it: it only makes sense for object types allocated frequently enough, and at a fixed enough size, to justify a dedicated cache, while variably-sized or infrequent allocations continue to go through the general-purpose allocator the way they always did. A real kernel typically runs both side by side, dedicated caches for its own frequently-churned fixed-size structs, the general free-list allocator for everything else, rather than trying to force every allocation through either mechanism exclusively.

References

1. ^ J. Bonwick, “The Slab Allocator: An Object-Caching Kernel Memory Allocator,” USENIX Summer Technical Conference, 1994: the original slab allocator paper, describing its design and use in Solaris.

See also

• Heap Allocators: the general-purpose model this design complements for fixed-size, high-frequency allocations rather than replaces.