为启用多线程的 ReleaseFast 优化模式设计的分配器。
此分配器是单例,使用全局状态;整个进程只应实例化一个。
基本设计
每个线程拥有独立空闲链表,但线程退出后必须能够回收数据。我们不能直接获知线程何时退出,因此某个线程需要偶尔尝试回收另一个线程的资源。
超过一定大小的分配会直接进行内存映射,不存储分配元数据。这之所以可行,是因为实现会拒绝使分配在小型和大型类别之间移动的调整大小操作。
每个分配器操作都会从线程局部变量检查线程标识,确定访问哪一份全局元数据,并尝试获取其锁。除非另一个线程被分配了相同标识,通常不会发生竞争。如果存在竞争,线程就移动到下一个线程元数据槽位,重复尝试获取锁。
将线程局部元数据数组限制为与 CPU 数量相同的长度,可以确保线程不断创建与销毁时,会循环利用全部空闲链表。
字段
cpu_count: u32
threads: [max_thread_count]Thread
std.heap.SmpAllocator.Alignment
别名
别名目标 std.mem.Alignment
std.heap.SmpAllocator.alloc
函数
fn alloc(context: *anyopaque, len: usize, alignment: Alignment, ra: usize) ?[*]u8
参数
std.heap.SmpAllocator.Allocator
别名
别名目标 std.mem.Allocator
std.heap.SmpAllocator.assert
别名
别名目标 std.debug.assert
std.heap.SmpAllocator.builtin
常量
std.heap.SmpAllocator.free
函数
fn free(context: *anyopaque, memory: []u8, alignment: Alignment, ra: usize) void
参数
std.heap.SmpAllocator.getCpuCount
函数
fn getCpuCount() u32
std.heap.SmpAllocator.global
变量
SmpAllocator
std.heap.SmpAllocator.math
别名
别名目标 std.math
std.heap.SmpAllocator.max_alloc_search
常量
映射新页前,alloc 会轮转这么多次。
std.heap.SmpAllocator.max_thread_count
常量
std.heap.SmpAllocator.mem
别名
别名目标 std.mem
std.heap.SmpAllocator.min_class
常量
由于需要存储空闲链表指针,最小大小类别为 3。
std.heap.SmpAllocator.PageAllocator
别名
std.heap.SmpAllocator.remap
函数
fn remap(context: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) ?[*]u8
参数
std.heap.SmpAllocator.resize
函数
fn resize(context: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) bool
参数
std.heap.SmpAllocator.size_class_count
常量
std.heap.SmpAllocator.sizeClassIndex
函数
fn sizeClassIndex(len: usize, alignment: Alignment) usize
参数
len: usize
alignment: Alignment
std.heap.SmpAllocator.slab_len
常量
usize
std.heap.SmpAllocator.slotSize
函数
fn slotSize(class: usize) usize
参数
class: usize
std.heap.SmpAllocator.SmpAllocator
别名
std.heap.SmpAllocator.std
别名
别名目标 std
std.heap.SmpAllocator.Thread
容器
字段
_: 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
变量
u32
std.heap.SmpAllocator.Thread.lock
函数
fn lock() *Thread
std.heap.SmpAllocator.Thread.unlock
函数
fn unlock(t: *Thread) void
参数
t: *Thread
std.heap.SmpAllocator.vtable
常量
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);
}