Slab Caches and Per-CPU Magazines for Fixed-Size Objects

A general-purpose heap serves arbitrary sizes and pays for the flexibility with per-allocation metadata and a search on every request. Kernel and runtime code usually knows more than that: it allocates the same small structure thousands of times, an inode, a socket, a task control block or a parsed node, and it knows the size, the alignment, and often the constructor that initialises the fields. An object cache exploits that knowledge. It pre-slices pages into same-size objects, keeps the free objects on a list, and can run an initialiser once per object instead of once per allocation.

From pages to objects

The unit of backing storage in a slab cache is a page or a group of contiguous pages, called a slab, carved into an integral number of objects of one size. If an object occupies 256 bytes and a slab is one 4 KiB page, the slab holds 16 objects. The remaining bytes, if the size does not divide the page, become unused slack at the end of the slab, a cost that grows with the object size and is one reason caches prefer object sizes that divide the page evenly.

Two metadata layouts are possible. Objects can be linked through their own payload, which requires that a free object be at least as large as a pointer and that the object not be in use while free, which is true by definition, but means the free list pointers are overwritten when the object is handed out, and the constructor must not rely on those bytes. Alternatively a separate array of indices or pointers describes the free objects, which costs bytes outside the slab but leaves the payload untouched.

The slab header holds a count of in-use objects, a pointer to the free list, and links that place the slab on the cache’s partial, full, or free lists. A cache maintains three such lists:

• full: every object allocated; no work can come from here until a free arrives.
• partial: some objects free; the source for allocations.
• free: every object free; candidates for return to the page allocator.

Allocation takes the first object from the partial list’s free list, decrementing the in-use count, and moves the slab to the full list when the count reaches capacity. Freeing does the reverse: the object goes back onto its slab’s free list and the slab moves from full to partial, or from partial to free when it empties. The in-use counter is the piece that a plain free list lacks. It is what makes it possible to know that a page holds no live objects and can be released.

Because every object in a slab is the same size, allocation never splits and never searches for a fit. The whole class-selection problem of size-class heaps collapses to a pointer load.

What the constructor buys

A cache can hold a constructor, invoked when an object is first placed on the free list rather than on every allocation. The distinction matters for structures whose initial state is expensive or whose invariant must hold even while free. A mutex, a reference count at zero, a list head pointing at itself: all can be established once and preserved across reuse, provided the code that frees the object restores that state.

The saving is real when initialisation is a handful of stores, and negligible when it is a syscall or a large zeroing operation. Kernel caches usually expose both paths: a plain allocation returns an object whose constructor has run, while a zeroed allocation must clear the payload itself, because reuse means the previous user’s data is still there. That reuse is also an information leak if the object crosses a privilege boundary, which is why zeroing is mandatory for anything reachable from another protection domain.

Construction at slab creation rather than at allocation has a second effect: objects are laid out in address order on the free list, so consecutive allocations walk forward through the slab. That sequential access pattern is friendly to the hardware prefetcher, and it is why freshly created slabs often perform better than recycled ones whose free order has been scrambled by frees.

The per-CPU magazine layer

A single lock around a cache’s partial list serialises every allocation on every processor. On a machine with many cores, that lock becomes the bottleneck even when the critical section is a few instructions, because the cache line holding the lock and the list head bounces between cores. The magazine layer removes the lock from the common path by giving each processor a small private stack of free objects.

The scheme has two levels. Each CPU holds a magazine: a fixed-size array with a count, typically holding a few dozen to a few hundred objects. Allocation pops from the current magazine. When it is empty, the CPU swaps in a full magazine from a shared depot, which requires the lock but happens once per magazine-worth of allocations. Freeing pushes onto the current magazine; when it is full, the CPU exchanges it for an empty one at the depot.

The parameter that governs the trade is the magazine size. A large magazine amortises the locked exchange over many operations but holds more memory idle per CPU, and delays the point at which objects return to the cache. With 64 objects of 128 bytes per magazine, a hundred CPUs hold 800 KiB of free objects that are not available to any other CPU. A small magazine returns memory sooner and loses the amortisation. The trade is between footprint and contention, and the right magazine size depends on the number of CPUs and the allocation rate.

The depot is itself a stack of magazines, with a depth that bounds how many full magazines a cache can hold. When the depot is full and a CPU returns a magazine, the objects are released to the cache’s slab layer, potentially freeing slabs. This cascade, from CPU magazine through the depot and the cache to the page allocator, is what makes the design able to give memory back at all, and each level introduces a delay proportional to its capacity.

Returning a slab is not automatic

A slab becomes releasable when its in-use count reaches zero and it sits on the free list. Whether it is actually released depends on policy, and the policy has to balance two costs.

Keeping a free slab costs memory. Releasing it costs a page-allocator call now and a page-allocator call later, plus the loss of the slab’s warmed cache lines and its object layout. A cache that oscillates between needing one slab and needing none will thrash if every transition releases and reacquires. Real caches therefore keep a reserve of free slabs per cache and release beyond it. The reserve is often scaled to the number of CPUs, on the theory that a machine with more cores has more concurrent demand.

Release is also where the cache interacts with the kernel’s reclaim machinery. Free slabs are a reclaimable resource: under memory pressure, the kernel can drain them, because their contents are by definition unused. That is why slab memory appears in reclaim accounting rather than being unreclaimable, and why the amount of memory held in free slabs is a quantity worth monitoring on a memory-constrained system.

The degenerate cases are worth naming. A cache whose objects are larger than a page cannot use a single-page slab, so slabs span multiple pages and the slack calculation changes. A cache whose object size exceeds the slab size entirely degenerates to a page allocator with extra steps. And a cache that is never drained holds its high-water mark forever: the peak population of objects determines the number of slabs, and slabs are only released when fully empty, so a workload that peaks once and then settles keeps the peak footprint.

Cache colouring and its limits

A slab’s objects are laid out at a fixed stride, so the mapping from object index to cache set is fixed. If the stride is a multiple of the cache set count times the line size, objects at the same index across slabs collide in the same sets. Cache colouring offsets the first object in each slab by a different amount, so consecutive slabs start at different positions in the cache and the collisions spread out.

The technique requires slack in the slab: the unused bytes at the end that arise when the object size does not divide the page. Colour is chosen from the number of distinct offsets the slack permits, and the offset is applied when carving objects. Colouring helps when the access pattern is index-based and regular; it does nothing for random access, and it cannot help when the object size leaves no slack at all.

Colouring also interacts with alignment. Shifting objects by an arbitrary number of bytes breaks the alignment guarantee for objects that require more than the base alignment, so an object needing 64-byte alignment cannot be coloured on a 4 KiB page whose slack is not itself a multiple of 64. In practice, alignment requirements cap the useful colour count.

The layered design of magazines for concurrency, slabs for locality and a page allocator for backing is what thread-local caches generalise into user space, with one important difference: a user-space allocator cannot assume that objects are freed by the thread that allocated them, so it must handle the case where a foreign thread’s free has to cross into the owner’s structures. The slab cache handles it by falling back to the shared depot under a lock, which is correct but costs the property that made the fast path fast.