🎓 A1Learner
🔍
0 of 46 lessons completed

Zig Slab Allocators

A slab allocator is an allocator that serves fixed-size blocks from a pool. Every block has the same size, so freeing and reuse stay simple.

One fixed-size slot

The slot holds 32 bytes. Storing 5 in the first byte prints the value and the slot size.

const std = @import("std");
const SlabAllocator = struct {
    backing: [256]u8 = [_]u8{0} ** 256,
    next: usize = 0,
    free_stack: [8]usize = undefined,
    free_len: usize = 0,
    reused: usize = 0,
    fn allocFn(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ret_addr: usize) ?[*]u8 {
        _ = ret_addr;
        const self: *SlabAllocator = @ptrCast(@alignCast(ctx));
        if (len > 32) return null;
        if (alignment.toByteUnits() > 32) return null;
        var index: usize = undefined;
        if (self.free_len > 0) {
            self.free_len -= 1;
            index = self.free_stack[self.free_len];
            self.reused += 1;
        } else if (self.next < 8) {
            index = self.next;
            self.next += 1;
        } else {
            return null;
        }
        const slice = self.backing[index * 32 .. index * 32 + 32];
        return slice.ptr;
    }
    fn resizeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) bool {
        _ = ctx;
        _ = memory;
        _ = alignment;
        _ = ret_addr;
        return new_len <= 32;
    }
    fn remapFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
        _ = ctx;
        _ = memory;
        _ = alignment;
        _ = new_len;
        _ = ret_addr;
        return null;
    }
    fn freeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, ret_addr: usize) void {
        _ = alignment;
        _ = ret_addr;
        const self: *SlabAllocator = @ptrCast(@alignCast(ctx));
        const off = @intFromPtr(memory.ptr) - @intFromPtr(&self.backing[0]);
        if (off % 32 != 0) return;
        const index = off / 32;
        if (index >= 8) return;
        if (self.free_len >= self.free_stack.len) return;
        self.free_stack[self.free_len] = index;
        self.free_len += 1;
    }
    fn allocator(self: *SlabAllocator) std.mem.Allocator {
        return .{ .ptr = self, .vtable = &.{ .alloc = allocFn, .resize = resizeFn, .remap = remapFn, .free = freeFn } };
    }
};
pub fn main() !void {
    const out = std.io.getStdOut().writer();
    var slab = SlabAllocator{};
    const alloc = slab.allocator();
    const a = try alloc.alloc(u8, 32);
    a[0] = 5;
    try out.print("{d} {d}\n", .{ a[0], a.len });
    alloc.free(a);
}

Reuse through the free list

Freeing a slot returns it to the free list. The next allocation reuses a freed slot.

const std = @import("std");
const SlabAllocator = struct {
    backing: [256]u8 = [_]u8{0} ** 256,
    next: usize = 0,
    free_stack: [8]usize = undefined,
    free_len: usize = 0,
    reused: usize = 0,
    fn allocFn(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ret_addr: usize) ?[*]u8 {
        _ = ret_addr;
        const self: *SlabAllocator = @ptrCast(@alignCast(ctx));
        if (len > 32) return null;
        if (alignment.toByteUnits() > 32) return null;
        var index: usize = undefined;
        if (self.free_len > 0) {
            self.free_len -= 1;
            index = self.free_stack[self.free_len];
            self.reused += 1;
        } else if (self.next < 8) {
            index = self.next;
            self.next += 1;
        } else {
            return null;
        }
        const slice = self.backing[index * 32 .. index * 32 + 32];
        return slice.ptr;
    }
    fn resizeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) bool {
        _ = ctx;
        _ = memory;
        _ = alignment;
        _ = ret_addr;
        return new_len <= 32;
    }
    fn remapFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
        _ = ctx;
        _ = memory;
        _ = alignment;
        _ = new_len;
        _ = ret_addr;
        return null;
    }
    fn freeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, ret_addr: usize) void {
        _ = alignment;
        _ = ret_addr;
        const self: *SlabAllocator = @ptrCast(@alignCast(ctx));
        const off = @intFromPtr(memory.ptr) - @intFromPtr(&self.backing[0]);
        if (off % 32 != 0) return;
        const index = off / 32;
        if (index >= 8) return;
        if (self.free_len >= self.free_stack.len) return;
        self.free_stack[self.free_len] = index;
        self.free_len += 1;
    }
    fn allocator(self: *SlabAllocator) std.mem.Allocator {
        return .{ .ptr = self, .vtable = &.{ .alloc = allocFn, .resize = resizeFn, .remap = remapFn, .free = freeFn } };
    }
};
pub fn main() !void {
    const out = std.io.getStdOut().writer();
    var slab = SlabAllocator{};
    const alloc = slab.allocator();
    const a = try alloc.alloc(u8, 32);
    a[0] = 11;
    try out.print("{d}\n", .{a[0]});
    alloc.free(a);
    const b = try alloc.alloc(u8, 32);
    try out.print("{d} {d}\n", .{ slab.reused, b.len });
    alloc.free(b);
}

Too big for a slot

A 64-byte request is larger than the 32-byte slot. The allocator rejects it.

const std = @import("std");
const SlabAllocator = struct {
    backing: [256]u8 = [_]u8{0} ** 256,
    next: usize = 0,
    free_stack: [8]usize = undefined,
    free_len: usize = 0,
    reused: usize = 0,
    fn allocFn(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ret_addr: usize) ?[*]u8 {
        _ = ret_addr;
        const self: *SlabAllocator = @ptrCast(@alignCast(ctx));
        if (len > 32) return null;
        if (alignment.toByteUnits() > 32) return null;
        var index: usize = undefined;
        if (self.free_len > 0) {
            self.free_len -= 1;
            index = self.free_stack[self.free_len];
            self.reused += 1;
        } else if (self.next < 8) {
            index = self.next;
            self.next += 1;
        } else {
            return null;
        }
        const slice = self.backing[index * 32 .. index * 32 + 32];
        return slice.ptr;
    }
    fn resizeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) bool {
        _ = ctx;
        _ = memory;
        _ = alignment;
        _ = ret_addr;
        return new_len <= 32;
    }
    fn remapFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
        _ = ctx;
        _ = memory;
        _ = alignment;
        _ = new_len;
        _ = ret_addr;
        return null;
    }
    fn freeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, ret_addr: usize) void {
        _ = alignment;
        _ = ret_addr;
        const self: *SlabAllocator = @ptrCast(@alignCast(ctx));
        const off = @intFromPtr(memory.ptr) - @intFromPtr(&self.backing[0]);
        if (off % 32 != 0) return;
        const index = off / 32;
        if (index >= 8) return;
        if (self.free_len >= self.free_stack.len) return;
        self.free_stack[self.free_len] = index;
        self.free_len += 1;
    }
    fn allocator(self: *SlabAllocator) std.mem.Allocator {
        return .{ .ptr = self, .vtable = &.{ .alloc = allocFn, .resize = resizeFn, .remap = remapFn, .free = freeFn } };
    }
};
pub fn main() !void {
    const out = std.io.getStdOut().writer();
    var slab = SlabAllocator{};
    const alloc = slab.allocator();
    if (alloc.alloc(u8, 64)) |big| {
        alloc.free(big);
        try out.print("accepted\n", .{});
    } else |_| {
        try out.print("rejected\n", .{});
    }
}

Example

const std = @import("std");
const SlabAllocator = struct {
    backing: [256]u8 = [_]u8{0} ** 256,
    next: usize = 0,
    free_stack: [8]usize = undefined,
    free_len: usize = 0,
    reused: usize = 0,
    fn allocFn(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ret_addr: usize) ?[*]u8 {
        _ = ret_addr;
        const self: *SlabAllocator = @ptrCast(@alignCast(ctx));
        if (len > 32) return null;
        if (alignment.toByteUnits() > 32) return null;
        var index: usize = undefined;
        if (self.free_len > 0) {
            self.free_len -= 1;
            index = self.free_stack[self.free_len];
            self.reused += 1;
        } else if (self.next < 8) {
            index = self.next;
            self.next += 1;
        } else {
            return null;
        }
        const slice = self.backing[index * 32 .. index * 32 + 32];
        return slice.ptr;
    }
    fn resizeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) bool {
        _ = ctx;
        _ = memory;
        _ = alignment;
        _ = ret_addr;
        return new_len <= 32;
    }
    fn remapFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
        _ = ctx;
        _ = memory;
        _ = alignment;
        _ = new_len;
        _ = ret_addr;
        return null;
    }
    fn freeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, ret_addr: usize) void {
        _ = alignment;
        _ = ret_addr;
        const self: *SlabAllocator = @ptrCast(@alignCast(ctx));
        const off = @intFromPtr(memory.ptr) - @intFromPtr(&self.backing[0]);
        if (off % 32 != 0) return;
        const index = off / 32;
        if (index >= 8) return;
        if (self.free_len >= self.free_stack.len) return;
        self.free_stack[self.free_len] = index;
        self.free_len += 1;
    }
    fn allocator(self: *SlabAllocator) std.mem.Allocator {
        return .{ .ptr = self, .vtable = &.{ .alloc = allocFn, .resize = resizeFn, .remap = remapFn, .free = freeFn } };
    }
};
pub fn main() !void {
    const out = std.io.getStdOut().writer();
    var slab = SlabAllocator{};
    const alloc = slab.allocator();
    var slots: [8][]u8 = undefined;
    var sum: usize = 0;
    for (0..8) |i| {
        slots[i] = try alloc.alloc(u8, 32);
        slots[i][0] = @intCast(i);
        sum += i;
    }
    alloc.free(slots[3]);
    const extra = try alloc.alloc(u8, 32);
    try out.print("{d} {d}\n", .{ sum, slab.reused });
    alloc.free(extra);
    for (slots, 0..) |s, i| {
        if (i != 3) alloc.free(s);
    }
}

Key points

  • Slab allocator: a slab allocator is an allocator that divides a pool into equal-size slots.
  • Each slot is the same size, so any free slot can serve any request that fits.
  • Freed slots return to a free list for the next allocation.
  • A request larger than the slot size is rejected with OutOfMemory.
  • Resizing a slot succeeds only when the new size still fits the slot.
  • A slab allocator suits programs that create many objects of one size.

Eight slots hold the values 0 through 7, which add up to 28. Freeing one slot and allocating again reuses a freed slot. The reuse count is 1.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

A slab allocator has 32-byte slots. What happens to a 64-byte request?