ptr & ~(SLAB_SIZE - 1) lands you on its header for free);[]align(N) slice type, @ptrFromInt, and @ptrCast/@alignCast let you express the raw pointer surgery a slab needs while still telling the compiler exactly what alignment you are promising;malloc in every modern libc and under the slab layer in the Linux kernel;slab, slotmap), and Go (size-classed spans in the runtime), and why the memory-safety story still differs across the four.MemoryPool(T): one slab of same-sized cells, a free list threaded through the free cells themselves, create/destroy collapsed to a pointer pop and push. Today's slab allocator is that pool, multiplied and managed;malloc";Learn Zig Series):Last week I ended episode 114 with a promise and a picture. We built a MemoryPool(T) -- one big slab of same-sized cells, a free list threaded through the free cells themselves, create and destroy collapsed to a single pointer pop and a single pointer push. And then I pointed at the load-bearing assumption sitting under all of it: one size. The pool is fast precisely because every cell is interchangeable. But a kernel does not allocate only task_structs, and a libc does not serve only 64-byte requests -- real programs churn through dozens of distinct sizes at once. So I said the next step was a system that manages a family of pools, routes each request to the right one, carves them out of page-sized runs, and hands whole pages back when they go cold.
That system has a name, and it is one of the prettiest pieces of design in systems programming: the slab allocator. Jeff Bonwick invented it for the Solaris kernel in 1994, and the same shape now sits under the Linux kernel's kmalloc, under jemalloc and tcmalloc, and under the size-classed heart of the Go runtime. The wonderful part is that you already understand the hard bit -- the free-list-through-storage trick is exactly what we built last week. Today is mostly about bookkeeping: sorting slabs into buckets, routing by size, and one genuinely new pointer trick that lets us find a slab from a bare object pointer without spending a single byte per object. But first -- the memory-pool debt from last week, three exercises, all with real code ;-)
Exercise 1 -- a double-free guard. The bare pool does not track which cells are live, so calling destroy twice on the same pointer silently corrupts the free list into a cycle. The cheap-to-write version is an O(n) walk of the free list in Debug builds: before pushing a cell back, check it is not already there. Here it is, bolted onto the pool from last week:
const std = @import("std");
const builtin = @import("builtin");
fn MemoryPool(comptime T: type) type {
return struct {
const Self = @This();
const Cell = union { item: T, next: ?*Cell };
const Block = struct { cells: []Cell, prev: ?*Block };
backing: std.mem.Allocator,
free_list: ?*Cell = null,
blocks: ?*Block = null,
per_block: usize,
fn init(backing: std.mem.Allocator, per_block: usize) Self {
return .{ .backing = backing, .per_block = per_block };
}
fn grow(self: *Self) !void {
const cells = try self.backing.alloc(Cell, self.per_block);
const block = try self.backing.create(Block);
block.* = .{ .cells = cells, .prev = self.blocks };
self.blocks = block;
var i: usize = cells.len;
while (i > 0) {
i -= 1;
cells[i] = .{ .next = self.free_list };
self.free_list = &cells[i];
}
}
fn create(self: *Self) !*T {
if (self.free_list == null) try self.grow();
const cell = self.free_list.?;
self.free_list = cell.next;
cell.* = .{ .item = undefined };
return &cell.item;
}
// In Debug builds, refuse a double free by scanning the free list first.
fn destroy(self: *Self, ptr: *T) void {
const cell: *Cell = @fieldParentPtr("item", ptr);
if (builtin.mode == .Debug) {
var n = self.free_list;
while (n) |c| : (n = c.next)
if (c == cell) @panic("MemoryPool double free");
}
cell.* = .{ .next = self.free_list };
self.free_list = cell;
}
};
}
That O(n) walk is brutal on a big pool -- every free becomes linear in the number of currently-free cells, so a full pool freeing in a loop is quadratic. The cheaper scheme I would actually ship keeps detection O(1) by spending a debug-only side channel: a parallel is_free slice indexed by each cell's position. It leaves the compact union layout completely untouched in Release (the slice is literally void there) and turns a double-free into a single boolean read:
fn FlaggedPool(comptime T: type) type {
return struct {
const Self = @This();
const debug = builtin.mode == .Debug;
const Cell = union { item: T, next: ?*Cell };
backing: std.mem.Allocator,
storage: []Cell,
is_free: if (debug) []bool else void,
free_list: ?*Cell = null,
fn init(backing: std.mem.Allocator, n: usize) !Self {
const storage = try backing.alloc(Cell, n);
var self = Self{
.backing = backing,
.storage = storage,
.is_free = if (debug) try backing.alloc(bool, n) else {},
};
var i: usize = n;
while (i > 0) {
i -= 1;
storage[i] = .{ .next = self.free_list };
if (debug) self.is_free[i] = true;
self.free_list = &storage[i];
}
return self;
}
fn indexOf(self: *Self, cell: *Cell) usize {
return (@intFromPtr(cell) - @intFromPtr(self.storage.ptr)) / @sizeOf(Cell);
}
fn destroy(self: *Self, ptr: *T) void {
const cell: *Cell = @fieldParentPtr("item", ptr);
if (debug) {
if (self.is_free[self.indexOf(cell)]) @panic("MemoryPool double free"); // O(1)
self.is_free[self.indexOf(cell)] = true;
}
cell.* = .{ .next = self.free_list };
self.free_list = cell;
}
};
}
I would ship the flag, not the walk. The O(1) check costs one byte per object in Debug and nothing in Release, where the if (debug) branch and the is_free field both compile away entirely -- you get the safety net during testing and pay zero for it in production. A generation counter per cell would catch use-after-free on top, at the price of a whole word; for a plain double-free the one-byte flag is the honest minimum.
Exercise 2 -- a pool that reclaims empty blocks. The pool from last week only ever grows: a burst of a million objects leaves a million cells allocated forever, even after every one is freed. The fix hinges on the question the exercise asks -- how do you know a whole block is free without an O(n) scan? Give each block its own free list and a live counter. Then "is this block entirely free?" is just live == 0, an O(1) test on every destroy:
fn ReclaimPool(comptime T: type) type {
return struct {
const Self = @This();
const Cell = union { item: T, next: ?*Cell };
const Block = struct {
cells: []Cell,
free_list: ?*Cell, // this block's OWN free objects
live: usize, // how many of this block's cells are handed out
prev: ?*Block,
next: ?*Block,
};
backing: std.mem.Allocator,
blocks: ?*Block = null,
per_block: usize,
fn init(backing: std.mem.Allocator, per_block: usize) Self {
return .{ .backing = backing, .per_block = per_block };
}
fn grow(self: *Self) !*Block {
const cells = try self.backing.alloc(Cell, self.per_block);
const block = try self.backing.create(Block);
block.* = .{ .cells = cells, .free_list = null, .live = 0, .prev = null, .next = self.blocks };
if (self.blocks) |h| h.prev = block;
self.blocks = block;
var i: usize = cells.len;
while (i > 0) {
i -= 1;
cells[i] = .{ .next = block.free_list };
block.free_list = &cells[i];
}
return block;
}
fn create(self: *Self) !*T {
var b = self.blocks;
const block = while (b) |blk| : (b = blk.next) {
if (blk.free_list != null) break blk; // first block with a spare cell
} else try self.grow();
const cell = block.free_list.?;
block.free_list = cell.next;
block.live += 1;
cell.* = .{ .item = undefined };
return &cell.item;
}
fn destroy(self: *Self, ptr: *T) void {
const cell: *Cell = @fieldParentPtr("item", ptr);
const addr = @intFromPtr(cell);
var b = self.blocks;
const block = while (b) |blk| : (b = blk.next) {
const base = @intFromPtr(blk.cells.ptr);
if (addr >= base and addr < base + blk.cells.len * @sizeOf(Cell)) break blk;
} else unreachable; // the pointer must have come from this pool
cell.* = .{ .next = block.free_list };
block.free_list = cell;
block.live -= 1;
if (block.live == 0) self.reclaim(block);
}
fn reclaim(self: *Self, block: *Block) void {
if (block.prev) |p| p.next = block.next else self.blocks = block.next;
if (block.next) |n| n.prev = block.prev;
self.backing.free(block.cells);
self.backing.destroy(block);
}
};
}
The honest trade: destroy now does an O(blocks) range-scan to find the owning block, because a bare object pointer carries no clue which block it lives in. That is the exact problem today's slab allocator solves elegantly -- hold that thought, because in about three sections we make that lookup O(1) with a single mask. Whether the reclaim is worth it depends on your workload: if memory sits at a high-water mark and never comes down, reclaiming is a real win; if the pool churns near its peak forever, you are paying the scan for a reclaim that never fires. Measure before you commit.
Exercise 3 -- benchmark pool-of-nodes versus general-allocator-of-nodes. Take the singly-linked list from episode 106, build it a million nodes two ways, and time the three phases separately. Because the timing API keeps moving between Zig versions (same disclaimer as last week), I hand you the measured work as functions and leave the stopwatch to you -- wrap each labelled loop in your platform's monotonic clock:
const Node = struct { value: u64, next: ?*Node };
fn SimplePool(comptime T: type) type {
return struct {
const Self = @This();
const Cell = union { item: T, next: ?*Cell };
backing: std.mem.Allocator,
free_list: ?*Cell = null,
blocks: std.ArrayListUnmanaged([]Cell) = .empty,
per_block: usize,
fn init(a: std.mem.Allocator, per_block: usize) Self {
return .{ .backing = a, .per_block = per_block };
}
fn deinit(self: *Self) void {
for (self.blocks.items) |cells| self.backing.free(cells);
self.blocks.deinit(self.backing);
}
fn create(self: *Self) !*T {
if (self.free_list == null) {
const cells = try self.backing.alloc(Cell, self.per_block);
try self.blocks.append(self.backing, cells);
var i: usize = cells.len;
while (i > 0) {
i -= 1;
cells[i] = .{ .next = self.free_list };
self.free_list = &cells[i];
}
}
const cell = self.free_list.?;
self.free_list = cell.next;
cell.* = .{ .item = undefined };
return &cell.item;
}
};
}
fn buildWithGeneral(a: std.mem.Allocator, n: usize) !void {
var head: ?*Node = null;
for (0..n) |i| { // PHASE 1: build -- one allocator round-trip each
const node = try a.create(Node);
node.* = .{ .value = i, .next = head };
head = node;
}
var sum: u64 = 0;
var walk = head;
while (walk) |node| : (walk = node.next) sum += node.value; // PHASE 2: iterate scattered nodes
walk = head;
while (walk) |node| { // PHASE 3: free -- one round-trip each again
const nx = node.next;
a.destroy(node);
walk = nx;
}
std.mem.doNotOptimizeAway(sum);
}
fn buildWithPool(a: std.mem.Allocator, n: usize) !void {
var pool = SimplePool(Node).init(a, 4096);
defer pool.deinit(); // PHASE 3 (free) is one bulk teardown
var head: ?*Node = null;
for (0..n) |i| { // PHASE 1: build -- bare pointer pop on the hot path
const node = try pool.create();
node.* = .{ .value = i, .next = head };
head = node;
}
var sum: u64 = 0;
var walk = head;
while (walk) |node| : (walk = node.next) sum += node.value; // PHASE 2: iterate near-contiguous cells
std.mem.doNotOptimizeAway(sum);
}
Which phase does the pool help most, and why does iteration differ even though neither version allocates while iterating? The build phase is the obvious win -- a pointer pop versus a full allocator search. But the sneaky one is iteration: the general allocator scatters a million nodes across the heap wherever it found holes, so walking the list is a cache-miss carnival, one cold line per node. The pool's nodes come from a handful of contiguous 4096-cell blocks, so consecutive create calls sit next to each other in memory and the walk streams through cache. Same algorithm, wildly different memory shape -- and shape is what the hardware actually charges you for. Right, debt paid. On to the slab ;-)
Strip a slab allocator down and it is three ideas stacked on last week's pool.
One: size classes. You cannot run a separate pool per exact byte-size -- there are billions of them. So you pick a fixed ladder of sizes (say 16, 32, 48, 64, ... 1024) and round every request up to the nearest rung. A 20-byte request and a 30-byte request both land in the 32-byte class and come from the same pool. You waste a little memory to internal fragmentation (that 20-byte object sitting in a 32-byte cell), and in exchange every object in a class is identical, which is the whole reason the pool trick works.
Two: the slab. Each size class owns a set of slabs. A slab is exactly last week's pool-block: one contiguous run of memory, carved into equal-sized objects, with a free list threaded through the free ones. The twist is that we make each slab a fixed, power-of-two size (I will use 64 KiB) and align it to that size -- which buys us the pointer trick coming up.
Three: the three-state sort. Within a size class, we do not keep slabs in one undifferentiated pile. We sort them into three lists by how full they are: full (every object handed out), partial (some used, some free), and empty (nothing handed out). Allocation always prefers a partial slab -- it is already warm and has room -- falls back to reviving an empty one, and only carves a brand-new slab when both are exhausted. Freeing runs the sort in reverse: an object coming back to a full slab makes it partial; the last object leaving a partial slab makes it empty, and an empty slab is a candidate to hand back to the OS.
That is the entire architecture. A slab allocator is a size-indexed array of these three-list "caches", each cache a herd of same-size slabs, each slab last week's pool. Everything below is spelling it in Zig.
Let me lay the foundations -- the constants, the free-list node, and the slab header. The header lives at offset zero of the slab's own backing memory, and the objects follow it. That placement is deliberate and it is the key to the whole thing: if the slab starts at a 64 KiB-aligned address, then every object inside it shares the top bits of that address, so masking any object pointer down to the 64 KiB boundary lands you exactly on the header:
const std = @import("std");
const SLAB_SIZE: usize = 64 * 1024; // power of two: also the alignment we mask against
const OBJ_ALIGN: usize = 16; // malloc-style alignment; every size class is a multiple of 16
// While an object is free, its first bytes hold the "next free" pointer -- the episode 114 trick,
// but the size is now a runtime value, so we overlay a node onto the object's bytes by hand.
const FreeNode = struct { next: ?*FreeNode };
const Slab = struct {
backing: []align(SLAB_SIZE) u8, // the whole page-run; the header lives at backing[0]
free_list: ?*FreeNode, // objects still free in THIS slab
used: usize, // objects currently handed out from THIS slab
capacity: usize, // how many objects this slab holds
cache: *SlabCache, // the size class we belong to
prev: ?*Slab = null, // linkage within one of the cache's three lists
next: ?*Slab = null,
};
Two Zig details worth pausing on. The backing field is typed []align(SLAB_SIZE) u8, not a plain []u8 -- the alignment is baked into the slice type, so the compiler knows every element is 64 KiB-aligned and will let us both allocate it with the right alignment and free it back correctly. And the FreeNode overlay is the runtime-sized cousin of last week's union: because a size class is a runtime number, we cannot spell a union { item: T, next } with a comptime T, so we treat a free object's raw bytes as a FreeNode via a pointer cast. The minimum size class is 16 bytes, comfortably larger than the 8-byte ?*FreeNode, so a free object always has room to store its own next-pointer -- same guarantee, established by hand.
The three-list membership needs the usual doubly-linked-list plumbing so we can yank a slab out of the middle of one list and push it onto another in O(1):
fn listPush(head: *?*Slab, slab: *Slab) void {
slab.prev = null;
slab.next = head.*;
if (head.*) |h| h.prev = slab;
head.* = slab;
}
fn listRemove(head: *?*Slab, slab: *Slab) void {
if (slab.prev) |p| p.next = slab.next else head.* = slab.next;
if (slab.next) |n| n.prev = slab.prev;
slab.prev = null;
slab.next = null;
}
Nothing exotic -- listRemove handles the four cases (interior, head, tail, sole element) with two ifs, exactly as we did for the doubly-linked list in episode 106. The head: *?*Slab parameter is a pointer to the list head so we can update the caller's partial/full/empty field when we remove the front element.
Now the size class itself. A SlabCache is one object size, a backing allocator to get slabs from, and the three lists. Growing a cache means allocating one aligned 64 KiB run, planting the Slab header at its front, computing how many objects fit after the header, and threading every one of them onto the new slab's free list:
const SlabCache = struct {
backing: std.mem.Allocator,
obj_size: usize,
partial: ?*Slab = null, // some used, some free
full: ?*Slab = null, // every object handed out
empty: ?*Slab = null, // nothing handed out (reclaim candidate)
fn grow(self: *SlabCache) !*Slab {
const mem = try self.backing.alignedAlloc(u8, .fromByteUnits(SLAB_SIZE), SLAB_SIZE);
errdefer self.backing.free(mem);
const slab: *Slab = @ptrCast(@alignCast(mem.ptr)); // header at offset 0
const header_end = std.mem.alignForward(usize, @sizeOf(Slab), OBJ_ALIGN);
const capacity = (mem.len - header_end) / self.obj_size;
slab.* = .{
.backing = mem,
.free_list = null,
.used = 0,
.capacity = capacity,
.cache = self,
};
// Thread every object slot onto this slab's free list.
var off = header_end;
var i: usize = 0;
while (i < capacity) : (i += 1) {
const node: *FreeNode = @ptrCast(@alignCast(mem.ptr + off));
node.next = slab.free_list;
slab.free_list = node;
off += self.obj_size;
}
listPush(&self.empty, slab);
return slab;
}
A fresh slab is born onto the empty list, which keeps alloc simple: it can treat "no partial slab" uniformly whether an empty one already existed or had to be grown. Here is alloc -- prefer partial, else empty-or-grow, pop one object, and re-sort the slab if its fullness changed:
fn alloc(self: *SlabCache) !*anyopaque {
const slab = self.partial orelse (self.empty orelse try self.grow());
const from_empty = (slab.used == 0);
const node = slab.free_list.?; // this slab always has a free object here
slab.free_list = node.next;
slab.used += 1;
if (from_empty) {
listRemove(&self.empty, slab); // it was empty; it is not any more
if (slab.free_list == null) listPush(&self.full, slab) else listPush(&self.partial, slab);
} else if (slab.free_list == null) {
listRemove(&self.partial, slab); // it was partial and just filled up
listPush(&self.full, slab);
}
return @ptrCast(node);
}
Freeing is the mirror image, and this is where the cache back-pointer in the slab header pays off: given a slab and an object pointer, push the object back onto the slab's own free list and re-sort by the new fullness. Note we read was_full before pushing, because the push itself changes free_list:
fn freeObject(self: *SlabCache, slab: *Slab, ptr: *anyopaque) void {
const node: *FreeNode = @ptrCast(@alignCast(ptr));
const was_full = (slab.free_list == null);
node.next = slab.free_list;
slab.free_list = node;
slab.used -= 1;
if (was_full) {
listRemove(&self.full, slab); // it was full; now it has a hole -> partial (or empty)
if (slab.used == 0) listPush(&self.empty, slab) else listPush(&self.partial, slab);
} else if (slab.used == 0) {
listRemove(&self.partial, slab); // last object left -> fully empty
listPush(&self.empty, slab);
}
}
fn deinit(self: *SlabCache) void {
for ([_]?*Slab{ self.partial, self.full, self.empty }) |head| {
var s = head;
while (s) |slab| {
const nx = slab.next; // save next BEFORE we free the memory the node lives in
self.backing.free(slab.backing); // frees the header too -- it lives inside `backing`
s = nx;
}
}
}
};
Watch the subtlety in deinit: the Slab header lives inside the backing allocation, so freeing slab.backing frees the header along with it. We have to read slab.next into nx before the free, or we would be chasing a pointer into freed memory -- the same discipline as freeing a linked list, from episode 106.
Here is the one genuinely new idea, and the thing that made the reclaim exercise painful up above. When a caller hands back a *anyopaque to free, how do we find which slab it belongs to without storing a back-pointer in every object (wasting a word each) and without scanning every slab (the O(blocks) walk from exercise 2)?
Because we aligned each slab to SLAB_SIZE and put the header at offset 0, the answer is a single bitwise AND. Every object in a slab has an address of the form slab_base + something_less_than_64KiB, so clearing the low 16 bits of any object pointer gives you slab_base -- which is the Slab header:
const CLASSES = [_]usize{ 16, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024 };
const SlabAllocator = struct {
backing: std.mem.Allocator,
caches: [CLASSES.len]SlabCache,
fn init(backing: std.mem.Allocator) SlabAllocator {
var self: SlabAllocator = .{ .backing = backing, .caches = undefined };
for (&self.caches, CLASSES) |*c, size| c.* = .{ .backing = backing, .obj_size = size };
return self;
}
fn deinit(self: *SlabAllocator) void {
for (&self.caches) |*c| c.deinit();
}
fn classFor(size: usize) ?usize {
for (CLASSES, 0..) |cs, i| if (size <= cs) return i;
return null; // too big for the slab layer -- a real allocator would go straight to mmap
}
fn alloc(self: *SlabAllocator, size: usize) !*anyopaque {
const idx = classFor(size) orelse return error.TooBig;
return self.caches[idx].alloc();
}
fn free(self: *SlabAllocator, ptr: *anyopaque) void {
_ = self;
// The magic line: mask any object pointer down to its 64 KiB-aligned slab header.
const slab: *Slab = @ptrFromInt(@intFromPtr(ptr) & ~(SLAB_SIZE - 1));
slab.cache.freeObject(slab, ptr); // the header knows its own size class
}
};
Read free twice, because it is the payoff for every design decision so far. @intFromPtr(ptr) turns the object address into an integer (episode 8). & ~(SLAB_SIZE - 1) clears the low 16 bits -- SLAB_SIZE - 1 is 0xFFFF, its complement masks those bits off -- landing us on the slab base. @ptrFromInt turns that back into a *Slab. And because the header stored a *SlabCache when it was born, slab.cache tells us the size class with zero searching. No per-object metadata, no scan, O(1) free of any pointer we ever handed out. That is why real slab allocators align their slabs (or, in the Linux kernel, look up the owning struct page, which is the same trick wearing a different hat). This is the elegant O(1) answer to exercise 2's painful O(blocks) scan, and it fell out of one alignment choice.
Notice free does not even use self -- the pointer alone carries enough structure to route itself home. I keep the parameter for API symmetry (and to sit behind a std.mem.Allocator vtable later), and _ = self; tells Zig I meant to ignore it.
A slab allocator is exactly the kind of raw pointer surgery where a weaker language leaves you no way to say what you mean, and Zig makes you say it precisely. Three places:
First, alignment as a type. alignedAlloc(u8, .fromByteUnits(SLAB_SIZE), SLAB_SIZE) returns a []align(SLAB_SIZE) u8, and that alignment rides along in the slice type. When we later @ptrCast(@alignCast(mem.ptr)) to a *Slab, the @alignCast is where we promise the compiler the pointer meets Slab's alignment; if we lied, a safety build traps at that exact spot instead of corrupting something three functions away. In C the cast is silent and the mistake is a segfault next Tuesday.
Second, error handling on the growth path. alloc is !*anyopaque, so "the OS refused another 64 KiB slab" surfaces as an ordinary error.OutOfMemory the caller must try or catch. And classFor returns ?usize, so "this request is bigger than any size class" is a null we turn into error.TooBig -- explicit, unignorable, right there in the type. A real production allocator would not error on big requests; it would route them straight to mmap/the page allocator and remember to free them the same way. Making that a one-line change is left for the exercises.
Third, @ptrFromInt and @intFromPtr as named operations. Turning pointers into integers and back is the beating heart of the mask trick, and Zig refuses to let it happen implicitly -- you write the builtin, the reader sees exactly where the type system is being deliberately stepped around, and grep finds every such place in your codebase. That visibility is not bureaucracy; when a pointer trick goes wrong, the first thing you want is a list of every spot you did pointer arithmetic.
The properties that matter are the mask trick (any pointer routes back to the right cache), address reuse (a freed object comes back), distinctness across slab growth (no aliasing), and the state-machine transitions (full to partial to empty). All of it is single-threaded and cheap to check:
test "mask trick recovers the slab header from any object pointer" {
var sa = SlabAllocator.init(std.testing.allocator);
defer sa.deinit();
const p = try sa.alloc(24); // 24 rounds up to the 32-byte class
const slab: *Slab = @ptrFromInt(@intFromPtr(p) & ~(SLAB_SIZE - 1));
try std.testing.expectEqual(@as(usize, 32), slab.cache.obj_size);
sa.free(p);
}
test "many objects across slab growth stay distinct" {
var sa = SlabAllocator.init(std.testing.allocator);
defer sa.deinit();
const Thing = struct { id: u64, pad: [24]u8 };
var ptrs: [5000]*Thing = undefined;
for (&ptrs, 0..) |*slot, i| {
const raw = try sa.alloc(@sizeOf(Thing));
const t: *Thing = @ptrCast(@alignCast(raw));
t.id = @intCast(i); // stamp each object with a unique id
slot.* = t;
}
for (ptrs, 0..) |t, i| try std.testing.expectEqual(@as(u64, @intCast(i)), t.id);
for (ptrs) |t| sa.free(@ptrCast(t));
}
The second test is the load-bearing one. Five thousand Things (32 bytes each) overflow a single 64 KiB slab several times, forcing grow to fire and the cache to juggle its three lists, and stamping every object with a distinct id then reading it back proves no two alloc calls ever returned the same cell. Because it runs on std.testing.allocator, a leaked slab -- a missing free in deinit -- fails the test outright. And the state machine deserves a test that names the transitions explicitly:
test "slab moves full -> partial -> empty as objects come and go" {
var sa = SlabAllocator.init(std.testing.allocator);
defer sa.deinit();
var cache = &sa.caches[SlabAllocator.classFor(16).?];
const cap = blk: {
const first = try cache.alloc();
const slab: *Slab = @ptrFromInt(@intFromPtr(first) & ~(SLAB_SIZE - 1));
const c = slab.capacity;
cache.freeObject(slab, first);
break :blk c;
};
var ptrs = try std.testing.allocator.alloc(*anyopaque, cap);
defer std.testing.allocator.free(ptrs);
for (ptrs) |*slot| slot.* = try cache.alloc(); // drain exactly one slab dry
try std.testing.expect(cache.full != null and cache.partial == null);
sa.free(ptrs[0]); // one hole -> partial
try std.testing.expect(cache.full == null and cache.partial != null);
for (ptrs[1..]) |p| sa.free(p); // last one out -> empty
try std.testing.expect(cache.partial == null and cache.empty != null);
}
This is the kind of test that would have caught the off-by-one I nearly shipped while writing this -- reading was_full/from_empty at the wrong moment relative to the free-list mutation quietly leaves a slab on two lists at once, and the assertion on which list is populated is what pins it down. Nota bene the slab does not zero objects on reuse: a recycled cell holds whatever the last object left there, so your code must fully initialise every object after alloc, exactly as after malloc.
The slab allocator inherits the memory pool's whole performance story and adds one wrinkle. The wins: alloc on a warm partial slab is a list-head read plus a pointer pop -- no size search, no coalescing, no fragmentation within a class, because every cell is interchangeable. Cache locality is excellent for the same reason as last week: objects of a class cluster in a few 64 KiB runs, so iterating live objects streams through memory. And free is now O(1) for any pointer thanks to the mask, where last week's reclaiming pool paid an O(blocks) scan.
The wrinkle, and the first real cost, is internal fragmentation from rounding. A 17-byte request lands in the 32-byte class and wastes 15 bytes; the coarser your size ladder, the more you waste. Real allocators tune this carefully -- jemalloc and tcmalloc use dozens of finely-spaced classes precisely to keep the average waste low. My 12-class ladder is a teaching compromise; a production ladder is geometric with extra rungs down low where allocations cluster.
The second cost is the same safety footgun as the bare pool, now slightly worse. The slab does not track liveness, so a double-free corrupts a slab's free list and a use-after-free reads a cell already handed to someone else -- and because the mask trick will happily route a wild pointer to some slab header, freeing a pointer the allocator never gave out can scribble on an unrelated slab's bookkeeping. The debug is_free flag from exercise 1 generalises to slabs and is worth every debug-mode byte. You trade a slice of safety for the speed, and -- I will keep saying this -- you have to know you made that trade.
When should you not reach for one? If your sizes vary wildly and unpredictably, if your allocation volume is low enough that a plain allocator.create is clearer, or if you need the debug allocator's use-after-free detection more than you need the throughput. Reach for a slab when a profiler (episode 34) actually points at malloc as your bottleneck, not because it is clever.
In C, this is the canonical systems-programming allocator. Bonwick's 1994 "The Slab Allocator" paper introduced it for the Solaris kernel, Linux adopted it for kmalloc (the SLAB, then SLUB, then SLOB variants are all this idea with different bookkeeping), and userspace allocators jemalloc and tcmalloc are size-classed slab allocators with per-thread caches bolted on for concurrency. The mechanism is identical to ours -- aligned slabs, free-list-through-storage, three-state sort -- but every cast is unchecked, the object-to-slab lookup is a raw pointer mask the compiler cannot verify, and a size-class mismatch is a silent corruption. The pattern is too valuable to skip and the language gives you no guardrails while you build it.
In Rust, the borrow checker makes the raw-pointer version fight you exactly as the pool did, so the ecosystem reaches for crates that change the API to make lifetimes provable: slab hands out integer keys in stead of pointers (a Vec-backed pool where a key, not a &mut, names your object), and slotmap adds generational keys so a stale key is detected rather than dangling. You get memory safety, but you give up the bare *T ergonomics -- the object is behind a key and a bounds-checked lookup. Rust makes the safety a type; you pay for it at the interface, as always.
In Go, the runtime's own heap is a slab allocator -- mcache/mcentral/mheap carve size-classed "spans" (Go's word for slabs) out of arena memory, with ~70 size classes and per-P caches for lock-free fast paths. But you never see it: it is wired to the garbage collector and there is no public API to run your own. The closest userspace tool is sync.Pool, which we met last week -- a GC-aware cache of temporaries, not a deterministic slab. Go's whole philosophy is that you should not think about this layer, which is a perfectly defensible choice and the exact opposite of Zig's.
Our Zig version sits where it always does: the slab alignment and object layout explicit, the free list threaded through storage at zero metadata cost, the mask trick spelled with named @intFromPtr/@ptrFromInt builtins, and the !/? return types letting you choose whether "too big" or "out of memory" is an error or an ordinary value. Same design across four languages -- but only here is it a couple hundred lines you can read start to finish, with no GC, no borrow-checker ceremony, and every dangerous cast marked in the source ;-)
Route oversized requests to the backing allocator. Right now alloc returns error.TooBig for anything over 1024 bytes. Change it so a request larger than the biggest size class goes straight to self.backing (a plain alloc/free), and make free recognise those pointers so it does not try to mask them to a slab header. The hard part is the recognition: a masked wild pointer is dangerous, so you need a reliable way to tell "this came from a slab" from "this came from the backing allocator" -- think about what you could check at the slab-header location, or what side table you could keep, and argue why your check can never false-positive.
Add the debug liveness flag to slabs. Generalise exercise 1's is_free idea from the flat pool to the slab: give each slab a debug-only bitset (one bit per object), set and clear it in alloc/freeObject, and @panic on a double-free or a free of a pointer whose slab-relative index is out of range. Measure the Debug-versus-Release size difference of a slab and confirm the bitset compiles to nothing in release.
Wrap it in the std.mem.Allocator interface. Give SlabAllocator an allocator(self) method returning a std.mem.Allocator with a vtable (the type-erasure pattern from episodes 13 and 26), so it can be handed to any stdlib container. You will have to handle the alloc/resize/remap/free vtable functions and decide what resize means for a slab (hint: a resize that stays within the same size class is free; one that crosses a class boundary is not). Then swap it under an std.ArrayList and prove it works.
Step back and notice what every allocator in this two-episode arc has assumed: a single machine, single thread. Our alloc and free walk shared lists and mutate shared free-list heads with no synchronisation at all -- hand this slab allocator to two threads and they will race on the exact partial/full/empty pointers, corrupting the lists in ways that make last week's double-free look gentle. That is not an oversight; it is the next problem. Every production allocator that matters -- jemalloc, tcmalloc, Go's runtime, the Linux slab layer -- solves it the same way, and it is a beautiful solution: give each thread its own cache of slabs so the fast path touches no shared state and needs no lock, and only reach for a shared, synchronised layer when a thread's local cache runs dry.
We have spent two episodes learning to manage memory when we are the only one asking for it. The tools we built to make that concurrent -- atomics and the memory model from episode 30, the lock-free discipline from episode 113 -- are about to come back and combine with today's size-classed slabs into something that looks a lot like a real, grown-up malloc. The free-list-through-storage trick you have now used three times becomes one gear; the mask trick becomes another; and the thing we bolt around them is what lets a hundred threads allocate at once without ever waiting on each other ;-)
Thanks for reading -- de groeten, en tot de volgende keer!
@scipio