Storage allocator (slab + free list)

The idea

Asking the operating system for memory is slow, so an allocator does it rarely. Instead of one syscall per request, it grabs a big slab once and carves it into equal, fixed-size blocks.

A free list remembers which blocks are available. alloc() pops the block at the head of the list; free() pushes a block back onto the head. Both are O(1) — no scanning, no searching, just a pointer move.

How it works

At init the allocator carves the slab into N blocks and threads them into a singly-linked free list: each free block stores the index of the next free one, and a free_head points at the first. The list lives inside the free blocks themselves, so it costs no extra memory.

BLOCK_SIZE = 64
N         = 14

def init(slab):
    # Link every block into the free list: 0 -> 1 -> 2 -> ... -> N-1 -> NONE
    for i in range(N - 1):
        slab.next[i] = i + 1
    slab.next[N - 1] = NONE
    slab.free_head   = 0          # first free block

def alloc(slab):
    i = slab.free_head            # head of the free list
    if i == NONE:
        return NONE               # slab exhausted — no free blocks
    slab.free_head = slab.next[i] # advance head to the next free block  (O(1) pop)
    return i                      # caller now owns block i

def free(slab, i):
    slab.next[i]   = slab.free_head  # block i now points at the old head
    slab.free_head = i               # block i becomes the new head        (O(1) push)

Both operations are pure pointer moves — a LIFO stack of free blocks. alloc pops the head; free pushes onto the head. That is why a freed block is the very next one handed back out.

Cost / trade-offs

The classic move: run many slabs, one per size class (32 B, 64 B, 128 B, …), and route each request to the slab whose block size is the smallest fit. This is the core of the Linux kernel slab allocator and of object pools generally.

Watch out for

• Double-free corrupts the free list. Freeing the same block twice links it to itself or creates a cycle, so alloc can hand the same block to two owners. Mark blocks as in-use and reject a free on an already-free block.
• Use-after-free. A freed block can be re-allocated immediately, so a stale pointer silently reads or writes another owner’s data. The slab makes this more likely because freed blocks are reused right away (LIFO).
• Slab exhaustion. When every block is out, free_head == NONE and alloc must fail or grow a new slab. Callers must handle a null return, not assume alloc always succeeds.
• Internal fragmentation from a too-large block. Sizing blocks at 256 B to “be safe” wastes most of every block holding 40-byte objects. Pick the block size from the real object size, or use multiple size classes.
• Thread safety. Two threads popping the head concurrently can both grab the same block. Guard the head with a lock, a lock-free CAS, or give each CPU its own per-CPU slab to avoid contention entirely.

Worked example

A server keeps a pool of connection objects on a slab so it never mallocs on the hot path. Block size matches one Connection struct; free_head starts at block 0.

conn_a = alloc()   # pops head 0 -> free_head now 1   (conn_a = block 0)
conn_b = alloc()   # pops head 1 -> free_head now 2   (conn_b = block 1)
conn_c = alloc()   # pops head 2 -> free_head now 3   (conn_c = block 2)
conn_d = alloc()   # pops head 3 -> free_head now 4   (conn_d = block 3)

free(conn_b)       # block 1 pushed -> next[1]=4, free_head now 1
free(conn_d)       # block 3 pushed -> next[3]=1, free_head now 3
                   # free list head is now:  3 -> 1 -> 4 -> 5 -> ...

conn_e = alloc()   # pops head 3 -> free_head now 1   (conn_e REUSES block 3)

Notice conn_e reuses block 3 — the most recently freed slot — because the free list is a LIFO stack. No OS call happened after the first slab grab; the four allocs, two frees, and the reuse were all pointer moves.

Check yourself