🎓 A1Learner
🔍
0 of 46 lessons completed

Zig Allocator Composition

Allocator composition is the practice of combining two allocators into one. A small fast allocator handles the common case and a general allocator handles the rest.

Spilling to the secondary

The 8-byte block fits the fixed buffer. The 32-byte block does not fit, so it spills to the general allocator.

const std = @import("std");
const FallbackAllocator = struct {
    primary: std.mem.Allocator,
    primary_start: usize,
    primary_len: usize,
    secondary: std.mem.Allocator,
    fn owns(self: *FallbackAllocator, memory: []u8) bool {
        const p = @intFromPtr(memory.ptr);
        return p >= self.primary_start and p < self.primary_start + self.primary_len;
    }
    fn allocFn(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ret_addr: usize) ?[*]u8 {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.primary.rawAlloc(len, alignment, ret_addr)) |ptr| return ptr;
        return self.secondary.rawAlloc(len, alignment, ret_addr);
    }
    fn resizeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) bool {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.owns(memory)) return self.primary.rawResize(memory, alignment, new_len, ret_addr);
        return self.secondary.rawResize(memory, alignment, new_len, ret_addr);
    }
    fn remapFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.owns(memory)) return self.primary.rawRemap(memory, alignment, new_len, ret_addr);
        return self.secondary.rawRemap(memory, alignment, new_len, ret_addr);
    }
    fn freeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, ret_addr: usize) void {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.owns(memory)) {
            self.primary.rawFree(memory, alignment, ret_addr);
        } else {
            self.secondary.rawFree(memory, alignment, ret_addr);
        }
    }
    fn allocator(self: *FallbackAllocator) 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 small: [16]u8 = undefined;
    var fixed = std.heap.FixedBufferAllocator.init(&small);
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    var fallback = FallbackAllocator{ .primary = fixed.allocator(), .primary_start = @intFromPtr(&small[0]), .primary_len = 16, .secondary = gpa.allocator() };
    const alloc = fallback.allocator();
    const a = try alloc.alloc(u8, 8);
    const b = try alloc.alloc(u8, 32);
    a[0] = 5;
    b[0] = 6;
    try out.print("{d} {d} {d} {d}\n", .{ a.len, b.len, a[0], b[0] });
    alloc.free(b);
    alloc.free(a);
}

Freeing routes correctly

Both blocks are freed to their own allocators. The fixed buffer is empty again, so a 16-byte block fits it.

const std = @import("std");
const FallbackAllocator = struct {
    primary: std.mem.Allocator,
    primary_start: usize,
    primary_len: usize,
    secondary: std.mem.Allocator,
    fn owns(self: *FallbackAllocator, memory: []u8) bool {
        const p = @intFromPtr(memory.ptr);
        return p >= self.primary_start and p < self.primary_start + self.primary_len;
    }
    fn allocFn(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ret_addr: usize) ?[*]u8 {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.primary.rawAlloc(len, alignment, ret_addr)) |ptr| return ptr;
        return self.secondary.rawAlloc(len, alignment, ret_addr);
    }
    fn resizeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) bool {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.owns(memory)) return self.primary.rawResize(memory, alignment, new_len, ret_addr);
        return self.secondary.rawResize(memory, alignment, new_len, ret_addr);
    }
    fn remapFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.owns(memory)) return self.primary.rawRemap(memory, alignment, new_len, ret_addr);
        return self.secondary.rawRemap(memory, alignment, new_len, ret_addr);
    }
    fn freeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, ret_addr: usize) void {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.owns(memory)) {
            self.primary.rawFree(memory, alignment, ret_addr);
        } else {
            self.secondary.rawFree(memory, alignment, ret_addr);
        }
    }
    fn allocator(self: *FallbackAllocator) 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 small: [16]u8 = undefined;
    var fixed = std.heap.FixedBufferAllocator.init(&small);
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    var fallback = FallbackAllocator{ .primary = fixed.allocator(), .primary_start = @intFromPtr(&small[0]), .primary_len = 16, .secondary = gpa.allocator() };
    const alloc = fallback.allocator();
    const a = try alloc.alloc(u8, 8);
    const b = try alloc.alloc(u8, 32);
    alloc.free(b);
    alloc.free(a);
    const c = try alloc.alloc(u8, 16);
    try out.print("{d}\n", .{c.len});
    alloc.free(c);
}

Resizing through the wrapper

The 8-byte block is the newest block in the fixed buffer. Growing it to 12 bytes succeeds in place.

const std = @import("std");
const FallbackAllocator = struct {
    primary: std.mem.Allocator,
    primary_start: usize,
    primary_len: usize,
    secondary: std.mem.Allocator,
    fn owns(self: *FallbackAllocator, memory: []u8) bool {
        const p = @intFromPtr(memory.ptr);
        return p >= self.primary_start and p < self.primary_start + self.primary_len;
    }
    fn allocFn(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ret_addr: usize) ?[*]u8 {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.primary.rawAlloc(len, alignment, ret_addr)) |ptr| return ptr;
        return self.secondary.rawAlloc(len, alignment, ret_addr);
    }
    fn resizeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) bool {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.owns(memory)) return self.primary.rawResize(memory, alignment, new_len, ret_addr);
        return self.secondary.rawResize(memory, alignment, new_len, ret_addr);
    }
    fn remapFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.owns(memory)) return self.primary.rawRemap(memory, alignment, new_len, ret_addr);
        return self.secondary.rawRemap(memory, alignment, new_len, ret_addr);
    }
    fn freeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, ret_addr: usize) void {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.owns(memory)) {
            self.primary.rawFree(memory, alignment, ret_addr);
        } else {
            self.secondary.rawFree(memory, alignment, ret_addr);
        }
    }
    fn allocator(self: *FallbackAllocator) 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 small: [16]u8 = undefined;
    var fixed = std.heap.FixedBufferAllocator.init(&small);
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    var fallback = FallbackAllocator{ .primary = fixed.allocator(), .primary_start = @intFromPtr(&small[0]), .primary_len = 16, .secondary = gpa.allocator() };
    const alloc = fallback.allocator();
    const a = try alloc.alloc(u8, 8);
    a[0] = 7;
    const b = try alloc.realloc(a, 12);
    try out.print("{d} {d}\n", .{ b.len, b[0] });
    alloc.free(b);
}

Example

const std = @import("std");
const FallbackAllocator = struct {
    primary: std.mem.Allocator,
    primary_start: usize,
    primary_len: usize,
    secondary: std.mem.Allocator,
    fn owns(self: *FallbackAllocator, memory: []u8) bool {
        const p = @intFromPtr(memory.ptr);
        return p >= self.primary_start and p < self.primary_start + self.primary_len;
    }
    fn allocFn(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ret_addr: usize) ?[*]u8 {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.primary.rawAlloc(len, alignment, ret_addr)) |ptr| return ptr;
        return self.secondary.rawAlloc(len, alignment, ret_addr);
    }
    fn resizeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) bool {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.owns(memory)) return self.primary.rawResize(memory, alignment, new_len, ret_addr);
        return self.secondary.rawResize(memory, alignment, new_len, ret_addr);
    }
    fn remapFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.owns(memory)) return self.primary.rawRemap(memory, alignment, new_len, ret_addr);
        return self.secondary.rawRemap(memory, alignment, new_len, ret_addr);
    }
    fn freeFn(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, ret_addr: usize) void {
        const self: *FallbackAllocator = @ptrCast(@alignCast(ctx));
        if (self.owns(memory)) {
            self.primary.rawFree(memory, alignment, ret_addr);
        } else {
            self.secondary.rawFree(memory, alignment, ret_addr);
        }
    }
    fn allocator(self: *FallbackAllocator) 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 small: [16]u8 = undefined;
    var fixed = std.heap.FixedBufferAllocator.init(&small);
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    var fallback = FallbackAllocator{ .primary = fixed.allocator(), .primary_start = @intFromPtr(&small[0]), .primary_len = 16, .secondary = gpa.allocator() };
    const alloc = fallback.allocator();
    const tag = try alloc.alloc(u8, 4);
    const data = try alloc.alloc(u8, 100);
    tag[0] = 3;
    data[0] = 4;
    try out.print("{d} {d} {d}\n", .{ tag.len, data.len, tag[0] + data[0] });
    alloc.free(data);
    alloc.free(tag);
}

Key points

  • Fallback allocator: a fallback allocator is an allocator that tries a primary allocator first and a secondary allocator when the primary is full.
  • The primary allocator is usually small and fast, like a fixed buffer.
  • The secondary allocator is usually general, like the general purpose allocator.
  • Freeing must route each block to the allocator that created it.
  • A pointer range check can tell which allocator owns a block.
  • Resizing must route the same way as freeing.

The 4-byte tag fits the fixed buffer. The 100-byte payload does not fit, so it goes to the general allocator. The printed sum is the two first bytes added together.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

A fallback allocator's primary buffer is full. What happens to the next allocation?