Slab Allocator

Jeff Bonwick introduced the slab allocator in 1994 for SunOS 5.4 (Solaris), in the paper "The Slab Allocator: An Object-Caching Kernel Memory Allocator". It lives on in Linux's kmem_cache (and its SLUB variant), FreeBSD's UMA, illumos, and userspace caches such as memcached's. After this lesson your program will manage named caches that hand out fixed-size objects from slabs, grow when they run out, and give empty slabs back.

The key insight

Most kernel allocations are for the SAME TYPE of object: struct dentry, struct inode, struct task_struct. Each has a known, fixed size. Paying for a general-purpose allocator on every one of them, with a header, a size lookup and a search, is waste.

A cache is a named pool for one type. A slab is a contiguous run of memory pre-divided into a fixed number of equal slots, each big enough for one object:

cache "inode" (object size 256 bytes, 4 slots per slab)

slab 0: [ used ][ used ][ used ][ used ]     full
slab 1: [ used ][ free ][ free ][ used ]     partial
slab 2: [ free ][ free ][ free ][ free ]     empty

Why it wins

1. No per-object header. The size is implied by the cache, and the address of a slot is plain arithmetic: slab base plus slot index times object size.
2. Locality. Same-type objects sit together, so scanning all inodes touches few cache lines.
3. Constructed objects. Bonwick's original design keeps freed objects in their initialised state, so the next allocation skips the constructor.
4. Per-CPU magazines later added the same lock-free fast path you saw in the Thread-Local Caches lesson.

For general userspace allocations, the size-class allocators (jemalloc, tcmalloc) are effectively slab caches per size class: same idea, generalised.

The rules of this lesson's cache

• CACHE_CREATE name obj_size per_slab registers a cache whose slabs each hold per_slab slots of obj_size bytes.

• Slabs get ids 0, 1, 2, ... in creation order, per cache. An id is never reused, even after the slab is released.

• ALLOC name chooses where to take a slot, in this order of preference:

  1. a partial slab (some slots used, some free), lowest id first;
  2. otherwise an empty slab (nothing used), lowest id first;
  3. otherwise grow: create a new slab with the next id.

  Inside the chosen slab it takes the lowest-numbered free slot and prints <slab>:<slot>.

• FREE name slab slot returns that slot: OK, or BAD if the slab does not exist, the slot is out of range, or the slot is not currently allocated.

• STATS name prints objs_alloc=<n> slabs=<n> empty=<n> partial=<n> full=<n>.

• REAP name releases every empty slab back to the system and prints reaped=<n>. Kernels do this under memory pressure.

• ADDR name slab slot prints the byte offset of a slot, slab * per_slab * obj_size + slot * obj_size (slabs are laid out one after another), or BAD for a slab that does not exist or a slot out of range. It shows what "no header" means: the slot's address needs no lookup.

The preference order matters: filling PARTIAL slabs first lets a nearly empty slab drain completely and become reapable, which is why real implementations do it. A policy of "lowest id with any free slot" would refill an empty slab 0 while slab 1 sits half full, keeping both alive.

Common mistakes

• Taking the lowest-id slab with a free slot, rather than preferring a partial one.
• Creating a new slab while an empty one exists.
• Reusing a reaped slab's id for the next new slab. Ids only grow.
• Accepting FREE on a slot that is not allocated, which would let a double free push a slab's count below zero.

Your exercise

The starter holds the cache table and prints the replies; implement the slot choice and the free and reap logic. A sequence that frees slots in several slabs and then allocates again is the whole test of the preference order.