跳转到内容

std.heap.SmpAllocator

标准库Zig 0.17.1官方原文
源码std/heap/SmpAllocator.zig

第 1 行

为启用多线程的 ReleaseFast 优化模式设计的分配器。

此分配器是单例,使用全局状态;整个进程只应实例化一个。

基本设计

每个线程拥有独立空闲链表,但线程退出后必须能够回收数据。我们不能直接获知线程何时退出,因此某个线程需要偶尔尝试回收另一个线程的资源。

超过一定大小的分配会直接进行内存映射,不存储分配元数据。这之所以可行,是因为实现会拒绝使分配在小型和大型类别之间移动的调整大小操作。

每个分配器操作都会从线程局部变量检查线程标识,确定访问哪一份全局元数据,并尝试获取其锁。除非另一个线程被分配了相同标识,通常不会发生竞争。如果存在竞争,线程就移动到下一个线程元数据槽位,重复尝试获取锁。

将线程局部元数据数组限制为与 CPU 数量相同的长度,可以确保线程不断创建与销毁时,会循环利用全部空闲链表。

字段

cpu_count: u32
threads: [max_thread_count]Thread

std.heap.SmpAllocator.Alignment

别名

第 38 行

别名目标 std.mem.Alignment

std.heap.SmpAllocator.alloc

函数

第 118 行

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

参数

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

std.heap.SmpAllocator.Allocator

别名

第 37 行

别名目标 std.mem.Allocator

std.heap.SmpAllocator.assert

别名

第 34 行

别名目标 std.debug.assert

std.heap.SmpAllocator.builtin

常量

第 31 行

std.heap.SmpAllocator.free

函数

第 200 行

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

参数

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

std.heap.SmpAllocator.getCpuCount

函数

第 100 行

fn getCpuCount() u32

std.heap.SmpAllocator.global

变量

第 44 行

SmpAllocator

std.heap.SmpAllocator.math

别名

第 36 行

别名目标 std.math

std.heap.SmpAllocator.max_alloc_search

常量

第 56 行

映射新页前,alloc 会轮转这么多次。

std.heap.SmpAllocator.max_thread_count

常量

第 50 行

std.heap.SmpAllocator.mem

别名

第 35 行

别名目标 std.mem

std.heap.SmpAllocator.min_class

常量

第 53 行

由于需要存储空闲链表指针,最小大小类别为 3。

std.heap.SmpAllocator.PageAllocator

别名

第 39 行

别名目标 std.heap.PageAllocator

std.heap.SmpAllocator.remap

函数

第 188 行

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

参数

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

std.heap.SmpAllocator.resize

函数

第 176 行

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

参数

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

std.heap.SmpAllocator.size_class_count

常量

第 54 行

std.heap.SmpAllocator.sizeClassIndex

函数

第 218 行

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

参数

len: usize
alignment: Alignment

std.heap.SmpAllocator.slab_len

常量

第 51 行

usize

std.heap.SmpAllocator.slotSize

函数

第 222 行

fn slotSize(class: usize) usize

参数

class: usize

std.heap.SmpAllocator.SmpAllocator

别名

第 29 行

别名目标 std.heap.SmpAllocator

std.heap.SmpAllocator.std

别名

第 33 行

别名目标 std

std.heap.SmpAllocator.Thread

容器

第 58 行

字段

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

避免伪共享。

mutex: std.atomic.Mutex = .unlocked

保护此结构体中的状态,即每线程状态。

线程访问自身状态前先加锁, 以支持空闲链表回收。

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

为每个大小类别记录空闲列表为空时, alloc 下一次将返回的地址。

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

对每个尺寸类别,指向已释放的指针。

std.heap.SmpAllocator.thread_index

变量

第 48 行

u32

std.heap.SmpAllocator.Thread.lock

函数

第 74 行

fn lock() *Thread

std.heap.SmpAllocator.Thread.unlock

函数

第 95 行

fn unlock(t: *Thread) void

参数

t: *Thread

std.heap.SmpAllocator.vtable

常量

第 107 行

Allocator.VTable
源码

std/heap/SmpAllocator.zig

//! 为启用多线程的 ReleaseFast 优化模式设计的分配器。
//!
//! 此分配器是单例,使用全局状态;整个进程只应实例化一个。
//!
//! ## 基本设计
//!
//! 每个线程拥有独立空闲链表,但线程退出后必须能够回收数据。我们不能直接获知线程何时退出,因此某个线程需要偶尔尝试回收另一个线程的资源。
//!
//! 超过一定大小的分配会直接进行内存映射,不存储分配元数据。这之所以可行,是因为实现会拒绝使分配在小型和大型类别之间移动的调整大小操作。
//!
//! 每个分配器操作都会从线程局部变量检查线程标识,确定访问哪一份全局元数据,并尝试获取其锁。除非另一个线程被分配了相同标识,通常不会发生竞争。如果存在竞争,线程就移动到下一个线程元数据槽位,重复尝试获取锁。
//!
//! 将线程局部元数据数组限制为与 CPU 数量相同的长度,可以确保线程不断创建与销毁时,会循环利用全部空闲链表。
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
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);
/// 由于需要存储空闲链表指针,最小大小类别为 3。
const min_class = math.log2(@sizeOf(usize));
const size_class_count = math.log2(slab_len) - min_class;
/// 映射新页前,`alloc` 会轮转这么多次。
const max_alloc_search = 1;

const Thread = struct {
    /// 避免伪共享。
    _: void align(std.atomic.cache_line) = {},

    /// 保护此结构体中的状态,即每线程状态。
    ///
    /// 线程访问自身状态前先加锁,
    /// 以支持空闲链表回收。
    mutex: std.atomic.Mutex = .unlocked,

    /// 为每个大小类别记录空闲列表为空时,
    /// `alloc` 下一次将返回的地址。
    next_addrs: [size_class_count]usize = @splat(0),
    /// 对每个尺寸类别,指向已释放的指针。
    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); // 使用方式不正确
}

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 对齐确保先前的 % slab len 能检测到槽位末尾。
            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);
}