subroute.
Advanced12 min readlive prototype

Slab Allocation

Pre-size caches of fixed slots per object type. O(1) allocation, zero external fragmentation — the kernel's workhorse.

Overview

What this concept solves

The slab allocator answers a different question from the fit strategies. They ask 'where do I put an arbitrary-sized request?' Slab allocation asks 'I allocate millions of objects of the same few types — how do I make that nearly free?' Its answer: give every object type its own cache of memory carved into slots exactly the right size, so allocation never searches and never wastes space on rounding.

Each cache owns one or more slabs — a slab is a chunk of contiguous memory (typically a page or a few pages from the underlying page allocator) sliced into a fixed number of equal slots. To allocate an object, you grab any free slot in the cache; to free it, you mark the slot free. There's no size matching, no splitting, no coalescing — just a free slot to claim. That's why allocation and free are O(1).

Because every slot in a cache is the exact size of the object, there is essentially no external fragmentation within a cache, and internal fragmentation is limited to the small, fixed slack the object type itself defines. Bonwick designed the slab allocator for Solaris precisely to serve the kernel's torrent of same-typed objects — inodes, file structures, task structs — and the design (and its descendants SLAB/SLUB/SLOB) is now standard in Linux and the BSDs.

Mechanics

How it works

Caches, slabs, and slots

  • Cache — one per object type (e.g. inode_cache). It knows the object size and how many slots fit in a slab, and it tracks its slabs by state.
  • Slab — a contiguous run of memory from the page allocator, divided into N fixed-size slots. A slab is empty (all slots free), partial (some used), or full (all used).
  • Slot — space for exactly one object. Allocation claims a free slot; free releases one.

Allocate: prefer a partial slab

  1. Look for a partial slab first. It already has both live objects and free slots, so using it keeps memory dense and avoids touching empty slabs.
  2. Else use an empty slab if one is on hand (kept around for fast reuse).
  3. Else grow. Ask the page allocator for a fresh slab (one or more pages), slice it into slots — it starts empty — and use it.
  4. Claim a free slot in O(1) and update the slab's state (empty→partial, or partial→full).

Free: release and maybe reclaim

  1. Find the object's slot and mark it free; the slab transitions full→partial or partial→empty.
  2. Reclaim empty slabs. When a slab becomes fully empty, its memory can be returned to the page allocator. (Real allocators often keep a few empties cached for fast reuse instead of reclaiming immediately.)

Object caching: the other half of Bonwick's idea

The original slab design also caches constructed objects: when an object is freed, it can be kept in an initialized state so the next allocation skips re-initialization. For complex kernel structures with expensive constructors, reusing a warm, already-initialized object is a real speedup — allocation becomes 'hand back a ready-made object,' not 'find memory and build one.'

Layered on the page/buddy allocator

Slab allocation doesn't get memory from thin air — it requests whole pages from the underlying page allocator (a buddy system in Linux) and subdivides them into slots. Buddy handles coarse, power-of-two page allocation with fast coalescing; slab handles fine-grained, same-sized objects with O(1) speed. They're complementary layers, not competitors.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

About this simulation

A slab allocator gives each object type its own cache. A cache is a set of slabs — contiguous memory pre-divided into fixed-size slots sized exactly for that object. Allocation is just 'find a free slot,' an O(1) operation with no size search and no external fragmentation. Slabs move between empty → partial → full as slots fill, and empty slabs are reclaimed. Scenario 1 · Two object types runs two caches side by side; scenario 2 · Grow & reclaim shows a slab created, filled, and returned to the OS.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Allocate from two caches at once

On scenario 1 · Two object types, step through. file_cache (64B, 6 slots/slab) and task_cache (128B, 4 slots/slab) fill independently — each object goes into a slot of its own cache. Watch a new slab get created the first time each cache is touched, and note the 'External frag = 0B' stat holding steady: every slot is exactly object-sized.

try 02

Watch slab states and reclamation

Continue scenario 1 into the free operations. Freeing F3 turns its slab partial; freeing T1 then T2 empties the task slab entirely — watch it transition to EMPTY and get reclaimed back to the OS, dropping the 'Slabs in use' and 'Memory committed' stats. Then the final file allocation reuses the freed F3 slot rather than growing.

try 03

Grow past one slab, then reclaim a whole slab

Switch to scenario 2 · Grow & reclaim. Allocate seven file objects: the first six fill slab 1 (empty→partial→full), and the seventh forces a second slab to be created. Then free F1–F6 to empty slab 1 completely and watch it get reclaimed while slab 2 keeps F7. Use Auto to watch the empty→partial→full→reclaim lifecycle play out.

In practice

When to use it — and what you give up

When slab allocation is the right tool

  • You allocate huge numbers of identically-sized objects — kernel objects, network buffers, tree/list nodes, connection structs. This is the workload slab was built for.
  • Allocation must be O(1) and predictable — no scan, no fit search, no fragmentation-driven latency spikes; ideal for kernels and real-time-ish paths.
  • Object initialization is expensive — caching constructed objects amortizes the setup cost across allocations.
  • Not for arbitrary-sized requests — slab needs to know object sizes up front. General malloc workloads with wildly varying sizes are served by sized caches plus a fallback, not by a single slab cache.

Real-world example

The Linux kernel uses slab-style allocation (the SLUB allocator by default, with SLAB and SLOB as alternatives) for nearly all internal objects. kmalloc is backed by a set of caches for common sizes; dedicated caches like dentry, inode_cache, and task_struct serve specific object types. You can watch them live in /proc/slabinfo. FreeBSD uses a slab allocator (uma, the zone allocator) descended from the same Solaris design.

Pros

  • O(1) allocate and free — just claim or release a slot; no search, no splitting.
  • Almost no fragmentation — slots are exactly object-sized, so no external fragmentation within a cache.
  • Object caching — freed objects can stay initialized, skipping re-construction on reuse.
  • Great cache/TLB behavior — same-typed objects packed densely in slabs improve locality.

Cons

  • One cache per object type — you must know sizes up front; not for arbitrary-sized allocation.
  • Per-cache overhead — many object types means many caches and some bookkeeping.
  • Partially-full slabs hold memory — a slab with one live object still occupies its whole page until that object frees.
  • Complexity — slab states, reclamation policy, and per-CPU caches (in SLUB) add machinery.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

slab.ts
interface Slab { slots: (string | null)[]; }      // null = free slot

class Cache {
  slabs: Slab[] = [];
  constructor(public objectSize: number, public slotsPerSlab: number) {}

  private state(s: Slab) {
    const used = s.slots.filter(Boolean).length;
    return used === 0 ? "empty" : used === s.slots.length ? "full" : "partial";
  }

  /** O(1): claim a free slot, preferring a partial slab; grow only if needed. */
  alloc(objId: string): void {
    let slab = this.slabs.find((s) => this.state(s) === "partial")
            ?? this.slabs.find((s) => this.state(s) === "empty");
    if (!slab) {                                   // grow: new slab from page allocator
      slab = { slots: Array(this.slotsPerSlab).fill(null) };
      this.slabs.push(slab);
    }
    slab.slots[slab.slots.indexOf(null)] = objId;  // take the first free slot
  }

  /** O(1): release the slot; reclaim the slab if it becomes empty. */
  free(objId: string): void {
    for (const slab of this.slabs) {
      const i = slab.slots.indexOf(objId);
      if (i !== -1) {
        slab.slots[i] = null;
        if (this.state(slab) === "empty") {        // return memory to the OS
          this.slabs = this.slabs.filter((s) => s !== slab);
        }
        return;
      }
    }
  }
}

References & further reading

5 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

Why is slab allocation O(1) with essentially no external fragmentation?

question 02 / 03

When allocating, which slab does the allocator prefer to use?

question 03 / 03

What is a key limitation of slab allocation?

0/3 answered

Was this concept helpful?

Tell us what worked, or what to improve. We read every note.

Back to Memory Allocation