Skip to content

std.heap.SmpAllocator

Standard libraryZig 0.17.1Official documentation
Sourcestd/heap/SmpAllocator.zig

Source line 1

An allocator that is designed for ReleaseFast optimization mode, with multi-threading enabled.

This allocator is a singleton; it uses global state and only one should be instantiated for the entire process.

Basic Design

Each thread gets a separate freelist, however, the data must be recoverable when the thread exits. We do not directly learn when a thread exits, so occasionally, one thread must attempt to reclaim another thread's resources.

Above a certain size, those allocations are memory mapped directly, with no storage of allocation metadata. This works because the implementation refuses resizes that would move an allocation from small category to large category or vice versa.

Each allocator operation checks the thread identifier from a threadlocal variable to find out which metadata in the global state to access, and attempts to grab its lock. This will usually succeed without contention, unless another thread has been assigned the same id. In the case of such contention, the thread moves on to the next thread metadata slot and repeats the process of attempting to obtain the lock.

By limiting the thread-local metadata array to the same number as the CPU count, ensures that as threads are created and destroyed, they cycle through the full set of freelists.

Fields

cpu_count: u32
threads: [max_thread_count]Thread

std.heap.SmpAllocator.Alignment

alias

Source line 38

Alias of std.mem.Alignment

std.heap.SmpAllocator.alloc

function

Source line 118

fn alloc(context: *anyopaque, len: usize, alignment: Alignment, ra: usize) ?[*]u8

Parameters

context: *anyopaque
len: usize
alignment: Alignment
ra: usize

std.heap.SmpAllocator.Allocator

alias

Source line 37

Alias of std.mem.Allocator

std.heap.SmpAllocator.assert

alias

Source line 34

Alias of std.debug.assert

std.heap.SmpAllocator.builtin

constant

Source line 31

std.heap.SmpAllocator.free

function

Source line 200

fn free(context: *anyopaque, memory: []u8, alignment: Alignment, ra: usize) void

Parameters

context: *anyopaque
memory: []u8
alignment: Alignment
ra: usize

std.heap.SmpAllocator.getCpuCount

function

Source line 100

fn getCpuCount() u32

std.heap.SmpAllocator.global

variable

Source line 44

SmpAllocator

std.heap.SmpAllocator.math

alias

Source line 36

Alias of std.math

std.heap.SmpAllocator.max_alloc_search

constant

Source line 56

Before mapping a fresh page, alloc will rotate this many times.

std.heap.SmpAllocator.max_thread_count

constant

Source line 50

std.heap.SmpAllocator.mem

alias

Source line 35

Alias of std.mem

std.heap.SmpAllocator.min_class

constant

Source line 53

Because of storing free list pointers, the minimum size class is 3.

std.heap.SmpAllocator.PageAllocator

alias

Source line 39

Alias of std.heap.PageAllocator

std.heap.SmpAllocator.remap

function

Source line 188

fn remap(context: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) ?[*]u8

Parameters

context: *anyopaque
memory: []u8
alignment: Alignment
new_len: usize
ra: usize

std.heap.SmpAllocator.resize

function

Source line 176

fn resize(context: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) bool

Parameters

context: *anyopaque
memory: []u8
alignment: Alignment
new_len: usize
ra: usize

std.heap.SmpAllocator.size_class_count

constant

Source line 54

std.heap.SmpAllocator.sizeClassIndex

function

Source line 218

fn sizeClassIndex(len: usize, alignment: Alignment) usize

Parameters

len: usize
alignment: Alignment

std.heap.SmpAllocator.slab_len

constant

Source line 51

usize

std.heap.SmpAllocator.slotSize

function

Source line 222

fn slotSize(class: usize) usize

Parameters

class: usize

std.heap.SmpAllocator.SmpAllocator

alias

Source line 29

Alias of std.heap.SmpAllocator

std.heap.SmpAllocator.std

alias

Source line 33

Alias of std

std.heap.SmpAllocator.Thread

container

Source line 58

Fields

_: void align(std.atomic.cache_line) = {}

Avoid false sharing.

mutex: std.atomic.Mutex = .unlocked

Protects the state in this struct (per-thread state).

Threads lock this before accessing their own state in order to support freelist reclamation.

next_addrs: [size_class_count]usize = @splat(0)

For each size class, tracks the next address to be returned from alloc when the freelist is empty.

frees: [size_class_count]usize = @splat(0)

For each size class, points to the freed pointer.

std.heap.SmpAllocator.thread_index

variable

Source line 48

u32

std.heap.SmpAllocator.Thread.lock

function

Source line 74

fn lock() *Thread

std.heap.SmpAllocator.Thread.unlock

function

Source line 95

fn unlock(t: *Thread) void

Parameters

t: *Thread

std.heap.SmpAllocator.vtable

constant

Source line 107

Allocator.VTable
Source code

std/heap/SmpAllocator.zig

//! An allocator that is designed for ReleaseFast optimization mode, with
//! multi-threading enabled.
//!
//! This allocator is a singleton; it uses global state and only one should be
//! instantiated for the entire process.
//!
//! ## Basic Design
//!
//! Each thread gets a separate freelist, however, the data must be recoverable
//! when the thread exits. We do not directly learn when a thread exits, so
//! occasionally, one thread must attempt to reclaim another thread's
//! resources.
//!
//! Above a certain size, those allocations are memory mapped directly, with no
//! storage of allocation metadata. This works because the implementation
//! refuses resizes that would move an allocation from small category to large
//! category or vice versa.
//!
//! Each allocator operation checks the thread identifier from a threadlocal
//! variable to find out which metadata in the global state to access, and
//! attempts to grab its lock. This will usually succeed without contention,
//! unless another thread has been assigned the same id. In the case of such
//! contention, the thread moves on to the next thread metadata slot and
//! repeats the process of attempting to obtain the lock.
//!
//! By limiting the thread-local metadata array to the same number as the CPU
//! count, ensures that as threads are created and destroyed, they cycle
//! through the full set of freelists.
const SmpAllocator = @This();

const builtin = @import("builtin");

const std = @import("../std.zig");
const assert = std.debug.assert;
const mem = std.mem;
const math = std.math;
const Allocator = std.mem.Allocator;
const Alignment = std.mem.Alignment;
const PageAllocator = std.heap.PageAllocator;

cpu_count: u32,
threads: [max_thread_count]Thread,

var global: SmpAllocator = .{
    .threads = @splat(.{}),
    .cpu_count = 0,
};
threadlocal var thread_index: u32 = 0;

const max_thread_count = 128;
const slab_len: usize = @max(std.heap.page_size_max, 64 * 1024);
/// Because of storing free list pointers, the minimum size class is 3.
const min_class = math.log2(@sizeOf(usize));
const size_class_count = math.log2(slab_len) - min_class;
/// Before mapping a fresh page, `alloc` will rotate this many times.
const max_alloc_search = 1;

const Thread = struct {
    /// Avoid false sharing.
    _: void align(std.atomic.cache_line) = {},

    /// Protects the state in this struct (per-thread state).
    ///
    /// Threads lock this before accessing their own state in order
    /// to support freelist reclamation.
    mutex: std.atomic.Mutex = .unlocked,

    /// For each size class, tracks the next address to be returned from
    /// `alloc` when the freelist is empty.
    next_addrs: [size_class_count]usize = @splat(0),
    /// For each size class, points to the freed pointer.
    frees: [size_class_count]usize = @splat(0),

    fn lock() *Thread {
        var index = thread_index;
        {
            const t = &global.threads[index];
            if (t.mutex.tryLock()) {
                @branchHint(.likely);
                return t;
            }
        }
        const cpu_count = getCpuCount();
        assert(cpu_count != 0);
        while (true) {
            index = (index + 1) % cpu_count;
            const t = &global.threads[index];
            if (t.mutex.tryLock()) {
                thread_index = index;
                return t;
            }
        }
    }

    fn unlock(t: *Thread) void {
        t.mutex.unlock();
    }
};

fn getCpuCount() u32 {
    const cpu_count = @atomicLoad(u32, &global.cpu_count, .unordered);
    if (cpu_count != 0) return cpu_count;
    const n: u32 = @min(std.Thread.getCpuCount() catch max_thread_count, max_thread_count);
    return if (@cmpxchgStrong(u32, &global.cpu_count, 0, n, .monotonic, .monotonic)) |other| other else n;
}

pub const vtable: Allocator.VTable = .{
    .alloc = alloc,
    .resize = resize,
    .remap = remap,
    .free = free,
};

comptime {
    assert(!builtin.single_threaded); // you're holding it wrong
}

fn alloc(context: *anyopaque, len: usize, alignment: Alignment, ra: usize) ?[*]u8 {
    _ = context;
    _ = ra;
    const class = sizeClassIndex(len, alignment);
    if (class >= size_class_count) {
        @branchHint(.unlikely);
        return PageAllocator.map(len, alignment);
    }

    const slot_size = slotSize(class);
    assert(slab_len % slot_size == 0);
    var search_count: u8 = 0;

    var t = Thread.lock();

    outer: while (true) {
        const top_free_ptr = t.frees[class];
        if (top_free_ptr != 0) {
            @branchHint(.likely);
            defer t.unlock();
            const node: *usize = @ptrFromInt(top_free_ptr);
            t.frees[class] = node.*;
            return @ptrFromInt(top_free_ptr);
        }

        const next_addr = t.next_addrs[class];
        if ((next_addr % slab_len) != 0) {
            @branchHint(.likely);
            defer t.unlock();
            t.next_addrs[class] = next_addr + slot_size;
            return @ptrFromInt(next_addr);
        }

        if (search_count >= max_alloc_search) {
            @branchHint(.likely);
            defer t.unlock();
            // slab alignment here ensures the % slab len earlier catches the end of slots.
            const slab = PageAllocator.map(slab_len, .fromByteUnits(slab_len)) orelse return null;
            t.next_addrs[class] = @intFromPtr(slab) + slot_size;
            return slab;
        }

        t.unlock();
        const cpu_count = getCpuCount();
        assert(cpu_count != 0);
        var index = thread_index;
        while (true) {
            index = (index + 1) % cpu_count;
            t = &global.threads[index];
            if (t.mutex.tryLock()) {
                thread_index = index;
                search_count += 1;
                continue :outer;
            }
        }
    }
}

fn resize(context: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) bool {
    _ = context;
    _ = ra;
    const class = sizeClassIndex(memory.len, alignment);
    const new_class = sizeClassIndex(new_len, alignment);
    if (class >= size_class_count) {
        if (new_class < size_class_count) return false;
        return PageAllocator.realloc(memory, alignment, new_len, false) != null;
    }
    return new_class == class;
}

fn remap(context: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) ?[*]u8 {
    _ = context;
    _ = ra;
    const class = sizeClassIndex(memory.len, alignment);
    const new_class = sizeClassIndex(new_len, alignment);
    if (class >= size_class_count) {
        if (new_class < size_class_count) return null;
        return PageAllocator.realloc(memory, alignment, new_len, true);
    }
    return if (new_class == class) memory.ptr else null;
}

fn free(context: *anyopaque, memory: []u8, alignment: Alignment, ra: usize) void {
    _ = context;
    _ = ra;
    const class = sizeClassIndex(memory.len, alignment);
    if (class >= size_class_count) {
        @branchHint(.unlikely);
        return PageAllocator.unmap(@alignCast(memory));
    }

    const node: *usize = @ptrCast(@alignCast(memory.ptr));

    const t = Thread.lock();
    defer t.unlock();

    node.* = t.frees[class];
    t.frees[class] = @intFromPtr(node);
}

fn sizeClassIndex(len: usize, alignment: Alignment) usize {
    return @max(@bitSizeOf(usize) - @clz(len - 1), @backingInt(alignment), min_class) - min_class;
}

fn slotSize(class: usize) usize {
    return @as(usize, 1) << @intCast(class + min_class);
}