此分配器封装已有分配器,提供先分配、 再统一释放的接口。单独释放某个项目时, 只有该项目是最近一次分配才真正释放,否则 不执行任何操作。
提供的 Allocator 实现具备线程安全性,前提是 child_allocator
也具备线程安全性。
字段
std.heap.ArenaAllocator.alignedIndex
函数
fn alignedIndex(buf_ptr: [*]u8, end_index: usize, alignment: Alignment) usize
参数
std.heap.ArenaAllocator.Alignment
别名
别名目标 std.mem.Alignment
std.heap.ArenaAllocator.alloc
函数
fn alloc(ctx: *anyopaque, n: usize, alignment: Alignment, ret_addr: usize) ?[*]u8
参数
std.heap.ArenaAllocator.allocator
函数
pub fn allocator(arena: *ArenaAllocator) Allocator
参数
arena: *ArenaAllocator
std.heap.ArenaAllocator.Allocator
别名
别名目标 std.mem.Allocator
std.heap.ArenaAllocator.ArenaAllocator
别名
std.heap.ArenaAllocator.assert
别名
别名目标 std.debug.assert
std.heap.ArenaAllocator.countListCapacity
函数
fn countListCapacity(first_node: ?*Node) usize
参数
first_node: ?*Node
std.heap.ArenaAllocator.deinit
函数
非线程安全。
pub fn deinit(arena: ArenaAllocator) void
参数
arena: ArenaAllocator
std.heap.ArenaAllocator.free
函数
fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, ret_addr: usize) void
参数
std.heap.ArenaAllocator.FuzzAllocator
容器
字段
std.heap.ArenaAllocator.FuzzAllocator.alloc
函数
fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8
参数
std.heap.ArenaAllocator.FuzzAllocator.allocator
函数
fn allocator(fa: *FuzzAllocator) Allocator
参数
fa: *FuzzAllocator
std.heap.ArenaAllocator.FuzzAllocator.free
函数
fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, ret_addr: usize) void
参数
std.heap.ArenaAllocator.FuzzAllocator.init
函数
fn init(buffer: []u8) FuzzAllocator
参数
buffer: []u8
std.heap.ArenaAllocator.FuzzAllocator.prepareFailures
函数
fn prepareFailures(fa: *FuzzAllocator, smith: *std.testing.Smith) void
参数
fa: *FuzzAllocator
smith: *std.testing.Smith
std.heap.ArenaAllocator.FuzzAllocator.remap
函数
fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8
参数
std.heap.ArenaAllocator.FuzzAllocator.reset
函数
fn reset(fa: *FuzzAllocator) void
参数
fa: *FuzzAllocator
std.heap.ArenaAllocator.FuzzAllocator.resize
函数
fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) bool
参数
std.heap.ArenaAllocator.FuzzContext
容器
字段
std.heap.ArenaAllocator.FuzzContext.Action
容器
字段
std.heap.ArenaAllocator.FuzzContext.Alloc
容器
字段
control_ptr: [*]u8
sample_ptr: [*]u8
common: packed struct(usize) {
len: Len,
alignment: Alignment,
_: @Int(.unsigned, padding_bits) = 0,
}
std.heap.ArenaAllocator.FuzzContext.Alloc.Index
容器
字段
std.heap.ArenaAllocator.FuzzContext.Alloc.Len
容器
字段
std.heap.ArenaAllocator.FuzzContext.Alloc.len_bits
常量
std.heap.ArenaAllocator.FuzzContext.Alloc.padding_bits
常量
std.heap.ArenaAllocator.FuzzContext.check
函数
fn check(ctx: *const FuzzContext, n_allocs: usize) !void
参数
ctx: *const FuzzContext
n_allocs: usize
std.heap.ArenaAllocator.FuzzContext.deinit
函数
fn deinit(ctx: *FuzzContext) void
参数
ctx: *FuzzContext
std.heap.ArenaAllocator.FuzzContext.doOneAlloc
函数
fn doOneAlloc(ctx: *FuzzContext, len: usize, alignment: Alignment, index: Alloc.Index) void
参数
std.heap.ArenaAllocator.FuzzContext.doOneFree
函数
fn doOneFree(ctx: *FuzzContext) void
参数
ctx: *FuzzContext
std.heap.ArenaAllocator.FuzzContext.doOneRemap
函数
fn doOneRemap(ctx: *FuzzContext, new_len: usize) void
参数
ctx: *FuzzContext
new_len: usize
std.heap.ArenaAllocator.FuzzContext.doOneResize
函数
fn doOneResize(ctx: *FuzzContext, new_len: usize) void
参数
ctx: *FuzzContext
new_len: usize
std.heap.ArenaAllocator.FuzzContext.init
函数
fn init( control_allocator: Allocator, sample_allocator: Allocator, ) FuzzContext
参数
std.heap.ArenaAllocator.FuzzContext.Init
容器
字段
threaded_instance: *std.Io.Threaded
arena_state: *ArenaAllocator.State
control_instance: *std.heap.FixedBufferAllocator
sample_instance: *FuzzAllocator
std.heap.ArenaAllocator.FuzzContext.max_action_count
常量
std.heap.ArenaAllocator.FuzzContext.max_alloc_count
常量
std.heap.ArenaAllocator.FuzzContext.max_alloc_size
常量
std.heap.ArenaAllocator.fuzzMultiThreaded
函数
fn fuzzMultiThreaded(fuzz_init: FuzzContext.Init, smith: *std.testing.Smith) anyerror!void
参数
fuzz_init: FuzzContext.Init
smith: *std.testing.Smith
std.heap.ArenaAllocator.init
函数
pub fn init(child_allocator: Allocator) ArenaAllocator
参数
child_allocator: Allocator
std.heap.ArenaAllocator.loadFirstNode
函数
fn loadFirstNode(arena: *ArenaAllocator) ?*Node
参数
arena: *ArenaAllocator
std.heap.ArenaAllocator.mem
别名
别名目标 std.mem
std.heap.ArenaAllocator.nextLen
函数
fn nextLen(smith: *std.testing.Smith) @typeInfo(FuzzContext.Alloc.Len).@"enum".tag_type
参数
std.heap.ArenaAllocator.Node
容器
对节点指针的并发访问通常必须具有 acquire/release 语义,以保证新分配节点在插入列表时 处于有效状态。也可能存在例外,例如某个 cmpxchg 循环 从不访问失败时返回的节点,则失败时可以使用 monotonic 语义,但成功时仍须使用 release 语义,以保护 正在尝试压入的节点。
字段
std.heap.ArenaAllocator.Node.allocatedSliceUnsafe
函数
非线程安全。
fn allocatedSliceUnsafe(node: *Node) []u8
参数
node: *Node
std.heap.ArenaAllocator.Node.beginResize
函数
返回已分配的切片;若节点已在调整大小,则返回 null。
fn beginResize(node: *Node) ?[]u8
参数
node: *Node
std.heap.ArenaAllocator.Node.endResize
函数
fn endResize(node: *Node, size: usize, prev_size: usize) void
参数
std.heap.ArenaAllocator.Node.loadBuf
函数
fn loadBuf(node: *Node) []u8
参数
node: *Node
std.heap.ArenaAllocator.Node.Size
容器
字段
resizing: bool
_: @Int(.unsigned, @bitSizeOf(usize) - 1) = 0
std.heap.ArenaAllocator.Node.Size.fromInt
函数
fn fromInt(int: usize) Size
参数
int: usize
std.heap.ArenaAllocator.Node.Size.toInt
函数
fn toInt(size: Size) usize
参数
size: Size
std.heap.ArenaAllocator.pushFreeList
函数
fn pushFreeList(arena: *ArenaAllocator, first: *Node, last: *Node) void
参数
std.heap.ArenaAllocator.PushResult
容器
字段
success
failure: ?*Node
std.heap.ArenaAllocator.queryCapacity
函数
查询此区域分配器当前的内存使用量。 不包含内部管理所需的存储空间。
非线程安全。
pub fn queryCapacity(arena: ArenaAllocator) usize
参数
arena: ArenaAllocator
std.heap.ArenaAllocator.remap
函数
fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8
参数
std.heap.ArenaAllocator.reset
函数
重置区域分配器并释放全部已分配内存。
mode 定义如何处理当前已分配的内存。
各模式的效果参见 ResetMode 的变体文档。
返回重置操作是否成功。
若重新分配失败,则返回 false。此时区域仍
完全可用,全部内存均已释放;只是后续
分配可能变慢。
不保证线程安全。
注意:若 mode 为 free_all,此函数始终返回 true。
pub fn reset(arena: *ArenaAllocator, mode: ResetMode) bool
参数
arena: *ArenaAllocator
mode: ResetMode
std.heap.ArenaAllocator.ResetMode
容器
字段
free_all释放该区域分配器中的所有已分配内存。
retain_capacity通过分配足以容纳此前全部分配的大缓冲区,
为后续分配预热区域。
预热减少调用底层分配器的次数,
从而加速分配。若在循环中使用 reset(),则在
执行过最大操作之后,不再进行内存分配。
retain_with_limit: usize与 retain_capacity 相同,但如果内存超过此上限,
则将其缩减至此值。
std.heap.ArenaAllocator.resize
函数
fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) bool
参数
std.heap.ArenaAllocator.State
容器
ArenaAllocator 的内部状态。可只存储此状态而非整个 ArenaAllocator, 以优化内存使用。
此结构体的默认初始化已弃用;请改用 init。
字段
std.heap.ArenaAllocator.State.init
常量
State
std.heap.ArenaAllocator.State.promote
函数
pub fn promote(state: State, child_allocator: Allocator) ArenaAllocator
参数
std.heap.ArenaAllocator.std
别名
别名目标 std
std.heap.ArenaAllocator.stealFreeList
函数
fn stealFreeList(arena: *ArenaAllocator) ?*Node
参数
arena: *ArenaAllocator
std.heap.ArenaAllocator.tryPushNode
函数
fn tryPushNode(arena: *ArenaAllocator, node: *Node) PushResult
参数
arena: *ArenaAllocator
node: *Node
源码
std/heap/ArenaAllocator.zig
//! 此分配器封装已有分配器,提供先分配、
//! 再统一释放的接口。单独释放某个项目时,
//! 只有该项目是最近一次分配才真正释放,否则
//! 不执行任何操作。
//!
//! 提供的 `Allocator` 实现具备线程安全性,前提是 `child_allocator`
//! 也具备线程安全性。
const ArenaAllocator = @This();
child_allocator: Allocator,
state: State,
/// ArenaAllocator 的内部状态。可只存储此状态而非整个 ArenaAllocator,
/// 以优化内存使用。
///
/// 此结构体的默认初始化已弃用;请改用 `init`。
pub const State = struct {
used_list: ?*Node = null,
free_list: ?*Node = null,
pub const init: State = .{
.used_list = null,
.free_list = null,
};
pub fn promote(state: State, child_allocator: Allocator) ArenaAllocator {
return .{
.child_allocator = child_allocator,
.state = state,
};
}
};
pub fn allocator(arena: *ArenaAllocator) Allocator {
return .{
.ptr = arena,
.vtable = &.{
.alloc = alloc,
.resize = resize,
.remap = remap,
.free = free,
},
};
}
pub fn init(child_allocator: Allocator) ArenaAllocator {
return State.init.promote(child_allocator);
}
/// 非线程安全。
pub fn deinit(arena: ArenaAllocator) void {
// 注意:修改此项时,确保相应调整 `reset()`!
for ([_]?*Node{ arena.state.used_list, arena.state.free_list }) |first_node| {
var it = first_node;
while (it) |node| {
// 必须在释放之前执行此操作,因为释放操作会释放 node
it = node.next;
arena.child_allocator.rawFree(node.allocatedSliceUnsafe(), .of(Node), @returnAddress());
}
}
}
/// 查询此区域分配器当前的内存使用量。
/// **不**包含内部管理所需的存储空间。
///
/// 非线程安全。
pub fn queryCapacity(arena: ArenaAllocator) usize {
var capacity: usize = 0;
for ([_]?*Node{ arena.state.used_list, arena.state.free_list }) |first_node| {
capacity += countListCapacity(first_node);
}
return capacity;
}
fn countListCapacity(first_node: ?*Node) usize {
var capacity: usize = 0;
var it = first_node;
while (it) |node| : (it = node.next) {
// 计算实际分配的大小,不包含
// 链表节点。
capacity += node.size.toInt() - @sizeOf(Node);
}
return capacity;
}
pub const ResetMode = union(enum) {
/// 释放该区域分配器中的所有已分配内存。
free_all,
/// 通过分配足以容纳此前全部分配的大缓冲区,
/// 为后续分配预热区域。
/// 预热减少调用底层分配器的次数,
/// 从而加速分配。若在循环中使用 `reset()`,则在
/// 执行过最大操作之后,不再进行内存分配。
retain_capacity,
/// 与 `retain_capacity` 相同,但如果内存超过此上限,
/// 则将其缩减至此值。
retain_with_limit: usize,
};
/// 重置区域分配器并释放全部已分配内存。
///
/// `mode` 定义如何处理当前已分配的内存。
/// 各模式的效果参见 `ResetMode` 的变体文档。
///
/// 返回重置操作是否成功。
/// 若重新分配失败,则返回 `false`。此时区域仍
/// 完全可用,全部内存均已释放;只是后续
/// 分配可能变慢。
///
/// 不保证线程安全。
///
/// 注意:若 `mode` 为 `free_all`,此函数始终返回 `true`。
pub fn reset(arena: *ArenaAllocator, mode: ResetMode) bool {
// 关于实现的说明:
// reset 函数有两种基本实现方式:
// - 统计自上次重置以来分配的字节数,并将该
// 信息保存在 State 中。这使 reset 很快,而 alloc 只会略微
// 变慢。
// - 遍历块链表来统计分配字节数。这会
// 使 reset 变慢,但启用 reset() 后,alloc() 的速度
// 与没有 reset() 时相同。
//
// 实现选择了第二种方案,因为随着 reset() 调用次数增加,
// 该函数会越来越快。最终,函数的复杂度
// 将降至均摊 O(1),因为此时只剩一个不会重新
// 分配的块,甚至不再访问底层分配器。
//
// 因此,实际上只有最初几次 reset() 调用需要遍历
// 链表;后续调用只取第一个节点,并重置 `end_index`
// 的值。
const limit: ?usize = switch (mode) {
.retain_capacity => null,
.retain_with_limit => |limit| limit,
.free_all => 0,
};
if (limit == 0) {
// 没有需要重新分配的内容时,直接重置
arena.deinit();
arena.state = .init;
return true;
}
const used_capacity = countListCapacity(arena.state.used_list);
const free_capacity = countListCapacity(arena.state.free_list);
const new_used_capacity = if (limit) |lim| @min(lim, used_capacity) else used_capacity;
const new_free_capacity = if (limit) |lim| @min(lim - new_used_capacity, free_capacity) else free_capacity;
var ok = true;
for (
[_]*?*Node{ &arena.state.used_list, &arena.state.free_list },
[_]usize{ new_used_capacity, new_free_capacity },
) |first_node_ptr, new_capacity| {
// 释放除最后一个以外的所有节点
var it = first_node_ptr.*;
const node: *Node = while (it) |node| {
// 必须在释放之前执行此操作,因为释放操作会释放 node
it = node.next;
if (it == null) break node;
arena.child_allocator.rawFree(node.allocatedSliceUnsafe(), .of(Node), @returnAddress());
} else {
continue;
};
const allocated_slice = node.allocatedSliceUnsafe();
// 向下对齐,以始终保持在上限以下。
const new_size = mem.alignBackward(usize, @sizeOf(Node) + new_capacity, 2);
if (new_size == @sizeOf(Node)) {
arena.child_allocator.rawFree(allocated_slice, .of(Node), @returnAddress());
first_node_ptr.* = null;
continue;
}
node.end_index = 0;
first_node_ptr.* = node;
if (allocated_slice.len == new_size) {
// 正好符合预期,无需调用 child_allocator
continue;
}
if (arena.child_allocator.rawResize(allocated_slice, .of(Node), new_size, @returnAddress())) {
// 调整大小成功
node.size = .fromInt(new_size);
} else {
// 手动重新分配
const new_ptr = arena.child_allocator.rawAlloc(new_size, .of(Node), @returnAddress()) orelse {
// 未能正确预热区域分配器,将此情况告知用户。
ok = false;
continue;
};
arena.child_allocator.rawFree(allocated_slice, .of(Node), @returnAddress());
const new_first_node: *Node = @ptrCast(@alignCast(new_ptr));
new_first_node.* = .{
.size = .fromInt(new_size),
.end_index = 0,
.next = null,
};
first_node_ptr.* = new_first_node;
}
}
return ok;
}
/// 对节点指针的并发访问通常必须具有 acquire/release
/// 语义,以保证新分配节点在插入列表时
/// 处于有效状态。也可能存在例外,例如某个 cmpxchg 循环
/// 从不访问失败时返回的节点,则失败时可以使用 monotonic
/// 语义,但成功时仍须使用 release 语义,以保护
/// 正在尝试压入的节点。
const Node = struct {
/// 除非节点由访问它的线程拥有,否则只能通过此类型提供的
/// 方法间接访问。
/// 必须始终为偶数,以容纳 `resize` 位。
size: Size,
/// 任何增大 `end_index` 的操作均须使用获取语义;
/// 任何减小 `end_index`、使先前活跃的分配失效的操作,
/// 均须使用释放语义。
/// 这保证对即将释放内存的全部访问
/// 先行发生于释放操作的发布。
/// 由于 `size` 只增不减,依赖任意
/// `end_index` <= 任意 `size` 的内存访问绝不会越界。
end_index: usize,
/// 仅当节点归访问它的线程所有时,
/// 才应访问此字段。
next: ?*Node,
const Size = packed struct(usize) {
resizing: bool,
_: @Int(.unsigned, @bitSizeOf(usize) - 1) = 0,
fn fromInt(int: usize) Size {
assert(int >= @sizeOf(Node));
const size: Size = @bitCast(int);
assert(!size.resizing);
return size;
}
fn toInt(size: Size) usize {
var int = size;
int.resizing = false;
return @bitCast(int);
}
comptime {
assert(Size{ .resizing = true } == @as(Size, @bitCast(@as(usize, 1))));
}
};
fn loadBuf(node: *Node) []u8 {
// `size` 只会增长,因此此函数返回的缓冲区始终是有效内存。
//
const size = @atomicLoad(Size, &node.size, .monotonic);
return @as([*]u8, @ptrCast(node))[0..size.toInt()][@sizeOf(Node)..];
}
/// 返回已分配的切片;若节点已在调整大小,则返回 `null`。
fn beginResize(node: *Node) ?[]u8 {
const size = @atomicRmw(Size, &node.size, .Or, .{ .resizing = true }, .acquire); // 与 `endResize` 中的释放操作同步
if (size.resizing) return null;
return @as([*]u8, @ptrCast(node))[0..size.toInt()];
}
fn endResize(node: *Node, size: usize, prev_size: usize) void {
assert(size >= prev_size); // 节点不得缩小
assert(@atomicLoad(Size, &node.size, .unordered).toInt() == prev_size);
return @atomicStore(Size, &node.size, .fromInt(size), .release); // 与 `beginResize` 中的获取操作同步
}
/// 非线程安全。
fn allocatedSliceUnsafe(node: *Node) []u8 {
return @as([*]u8, @ptrCast(node))[0..node.size.toInt()];
}
};
fn loadFirstNode(arena: *ArenaAllocator) ?*Node {
return @atomicLoad(?*Node, &arena.state.used_list, .acquire); // 与成功的 `tryPushNode` 中的 release 操作同步。
}
const PushResult = union(enum) {
success,
failure: ?*Node,
};
fn tryPushNode(arena: *ArenaAllocator, node: *Node) PushResult {
assert(node != node.next);
if (@cmpxchgStrong( // 使用强操作,因为重试意味着丢弃适配节点,开销较大
?*Node,
&arena.state.used_list,
node.next,
node,
.release, // 与失败路径或 `loadFirstNode` 中的 acquire 操作同步。
.acquire, // 与成功路径中的 release 同步
)) |old_node| {
return .{ .failure = old_node };
} else {
return .success;
}
}
fn stealFreeList(arena: *ArenaAllocator) ?*Node {
// 此处无需 acq_rel,因为始终交换写入 `null`,
// 不存在需要释放的节点。
return @atomicRmw(?*Node, &arena.state.free_list, .Xchg, null, .acquire); // 与 `pushFreeList` 中的 release 同步
}
fn pushFreeList(arena: *ArenaAllocator, first: *Node, last: *Node) void {
assert(first != last.next);
assert(first != first.next);
assert(last != last.next);
while (@cmpxchgWeak(
?*Node,
&arena.state.free_list,
last.next,
first,
.release, // 与 `stealFreeList` 中的获取操作同步
.monotonic, // 从不访问 `old_free_list` 的任何字段,仅关注其指针。
)) |old_free_list| {
last.next = old_free_list;
}
}
fn alignedIndex(buf_ptr: [*]u8, end_index: usize, alignment: Alignment) usize {
// 由于 `end_index` 不受 `size` 限制,使用回绕算术以避免溢出。
// 这始终可行,因为按字节计的最大对齐值也是 `usize` 最大值,
// 因此回绕后的值仍保持正确对齐。
return alignment.forward(@intFromPtr(buf_ptr) +% end_index) -% @intFromPtr(buf_ptr);
}
fn alloc(ctx: *anyopaque, n: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {
const arena: *ArenaAllocator = @ptrCast(@alignCast(ctx));
_ = ret_addr;
assert(n > 0);
var cur_first_node = arena.loadFirstNode();
var cur_new_node: ?*Node = null;
defer if (cur_new_node) |node| {
node.next = null; // 针对空闲链表为空的情况优化
arena.pushFreeList(node, node);
};
retry: while (true) {
const first_node: ?*Node, const prev_size: usize = first_node: {
const node = cur_first_node orelse break :first_node .{ null, 0 };
const buf = node.loadBuf();
// 为避免在热点路径使用 CAS 循环,以原子方式将 `end_index` 增加足够大的量,确保预留内存始终能满足所需对齐。
// 为回收潜在浪费的空间,随后尝试通过一次 cmpxchg 减去“超额预留”部分,但该操作可能失败。
//
//
//
const alignable = n + alignment.toByteUnits() - 1;
const end_index = @atomicRmw(usize, &node.end_index, .Add, alignable, .acquire); // 获取可能已释放的任意内存
const aligned_index = alignedIndex(buf.ptr, end_index, alignment);
assert(end_index + alignable >= aligned_index + n);
if (end_index + alignable != aligned_index + n) {
_ = @cmpxchgStrong(
usize,
&node.end_index,
end_index + alignable,
aligned_index + n,
.monotonic, // 无需释放对齐填充,因为没有任何代码访问它!
.monotonic,
);
}
if (aligned_index + n > buf.len) break :first_node .{ node, buf.len };
return buf[aligned_index..][0..n].ptr;
};
resize: {
// 获取新节点之前,先尝试调整
// 当前持有节点的大小。此操作是独占操作;
// 若另一线程已处于此区域,就绝不能调整大小。
const node = first_node orelse break :resize;
const allocated_slice = node.beginResize() orelse break :resize;
var size = allocated_slice.len;
defer node.endResize(size, allocated_slice.len);
const buf = allocated_slice[@sizeOf(Node)..];
const end_index = @atomicLoad(usize, &node.end_index, .monotonic);
const aligned_index = alignedIndex(buf.ptr, end_index, alignment);
const new_size = mem.alignForward(usize, @sizeOf(Node) + aligned_index + n, 2);
if (new_size <= allocated_slice.len) {
// 有 `resize` 或 `free` 调用穿插进来,需要
// 保证 `size` 只增不减;重试!
continue :retry;
}
if (arena.child_allocator.rawResize(allocated_slice, .of(Node), new_size, @returnAddress())) {
size = new_size;
// 使用强操作,因为虚假失败可能导致
// 此节点的使用方式不够理想。
if (null == @cmpxchgStrong(
usize,
&node.end_index,
end_index,
aligned_index + n,
.acquire, // 获取可能已释放的任意内存
.monotonic,
)) {
const new_buf = allocated_slice.ptr[0..new_size][@sizeOf(Node)..];
return new_buf[aligned_index..][0..n].ptr;
}
}
}
// 需要新节点!先在 `free_list` 中搜索足够大的节点;
// 若未找到,则回退为使用 `child_allocator` 分配新节点
// (如果尚未这样做)。
from_free_list: {
// 通过原子操作“夺取”整个空闲链表,独占处理,避免其他线程干扰。
// 这是一种务实方案,但由于空闲链表使用频率不高,即使有负载时性能也可接受。
// 这还避免了 ABA 问题:通过原子交换取走链表,不会引入可能过期的 `next` 指针。
//
//
//
const free_list = arena.stealFreeList() orelse break :from_free_list;
const first_free: *Node, const last_free: *Node, const node: *Node, const prev: ?*Node = find: {
var best_fit_prev: ?*Node = null;
var best_fit: ?*Node = null;
var best_fit_diff: usize = std.math.maxInt(usize);
var it_prev: ?*Node = null;
var it: ?*Node = free_list;
while (it) |node| : ({
it_prev = node;
it = node.next;
}) {
assert(!node.size.resizing);
const buf = node.allocatedSliceUnsafe()[@sizeOf(Node)..];
const aligned_index = alignedIndex(buf.ptr, 0, alignment);
const diff = aligned_index + n -| buf.len;
if (diff < best_fit_diff) {
best_fit_prev = it_prev;
best_fit = node;
best_fit_diff = diff;
}
}
break :find .{ free_list, it_prev.?, best_fit.?, best_fit_prev };
};
const aligned_index, const need_resize = aligned_index: {
const buf = node.allocatedSliceUnsafe()[@sizeOf(Node)..];
const aligned_index = alignedIndex(buf.ptr, 0, alignment);
break :aligned_index .{ aligned_index, aligned_index + n > buf.len };
};
if (need_resize) {
// 理想情况下,最终应使用 `free_list` 中的所有节点,
// 因此即使没有节点合适,也会尝试调整
// 最接近所需大小的节点。
const new_size = mem.alignForward(usize, @sizeOf(Node) + aligned_index + n, 2);
if (arena.child_allocator.rawResize(node.allocatedSliceUnsafe(), .of(Node), new_size, @returnAddress())) {
node.size = .fromInt(new_size);
} else {
arena.pushFreeList(first_free, last_free);
break :from_free_list; // 未找到大小合适的空闲节点
}
}
const buf = node.allocatedSliceUnsafe()[@sizeOf(Node)..];
const old_next = node.next;
node.end_index = aligned_index + n;
node.next = first_node;
switch (arena.tryPushNode(node)) {
.success => {
// 完成从空闲链表中移除节点。
if (prev) |p| p.next = old_next;
// 将窃取的空闲链表剩余部分压回 `arena.state.free_list`。
const new_first_free = if (node == first_free) old_next else first_free;
const new_last_free = if (node == last_free) prev else last_free;
if (new_first_free) |first| {
const last = new_last_free.?;
arena.pushFreeList(first, last);
}
return buf[aligned_index..][0..n].ptr;
},
.failure => |old_first_node| {
// 将空闲链表恢复原状
node.next = old_next;
arena.pushFreeList(first_free, last_free);
cur_first_node = old_first_node;
continue :retry; // 出现了新的首节点;重试!
},
}
}
const new_node: *Node = new_node: {
if (cur_new_node) |new_node| {
break :new_node new_node;
} else {
@branchHint(.cold);
}
const size: Node.Size = size: {
const min_size = @sizeOf(Node) + alignment.toByteUnits() + n;
const big_enough_size = prev_size + min_size + 16;
const size = mem.alignForward(usize, big_enough_size + big_enough_size / 2, 2);
break :size .fromInt(size);
};
const ptr = arena.child_allocator.rawAlloc(size.toInt(), .of(Node), @returnAddress()) orelse
return null;
const new_node: *Node = @ptrCast(@alignCast(ptr));
new_node.* = .{
.size = size,
.end_index = undefined, // 在下方设置
.next = undefined, // 在下方设置
};
cur_new_node = new_node;
break :new_node new_node;
};
const buf = new_node.allocatedSliceUnsafe()[@sizeOf(Node)..];
const aligned_index = alignedIndex(buf.ptr, 0, alignment);
assert(new_node.size.toInt() >= @sizeOf(Node) + aligned_index + n);
new_node.end_index = aligned_index + n;
new_node.next = first_node;
switch (arena.tryPushNode(new_node)) {
.success => {
cur_new_node = null;
return buf[aligned_index..][0..n].ptr;
},
.failure => |old_first_node| {
cur_first_node = old_first_node;
},
}
}
}
fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) bool {
const arena: *ArenaAllocator = @ptrCast(@alignCast(ctx));
_ = alignment;
_ = ret_addr;
assert(memory.len > 0);
assert(new_len > 0);
const node = arena.loadFirstNode().?;
const buf_ptr = @as([*]u8, @ptrCast(node)) + @sizeOf(Node);
const cur_end_index = @atomicLoad(usize, &node.end_index, .monotonic);
if (buf_ptr + cur_end_index != memory.ptr + memory.len) {
// 这不是最近一次分配,因此不能扩展,
// 但允许调用方缩小它。
return new_len <= memory.len;
}
if (new_len <= memory.len) {
const new_end_index = cur_end_index - (memory.len - new_len);
assert(buf_ptr + new_end_index == memory.ptr + new_len);
_ = @cmpxchgStrong(
usize,
&node.end_index,
cur_end_index,
new_end_index,
.release, // 释放已归还的内存
.monotonic,
);
return true; // 缩小内存分配应当始终成功。
}
// 使用饱和算术,因为不保证 `end_index` 满足 `<= size`。
// 尝试调整大小的分配可能属于另一节点!
if (node.loadBuf().len -| cur_end_index >= new_len - memory.len) {
const new_end_index = cur_end_index + (new_len - memory.len);
assert(buf_ptr + new_end_index == memory.ptr + new_len);
return null == @cmpxchgStrong(
usize,
&node.end_index,
cur_end_index,
new_end_index,
.acquire, // 获取可能已释放的任意内存
.monotonic,
);
}
return false;
}
fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
return if (resize(ctx, memory, alignment, new_len, ret_addr)) memory.ptr else null;
}
fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, ret_addr: usize) void {
const arena: *ArenaAllocator = @ptrCast(@alignCast(ctx));
_ = alignment;
_ = ret_addr;
assert(memory.len > 0);
const node = arena.loadFirstNode().?;
const buf_ptr = @as([*]u8, @ptrCast(node)) + @sizeOf(Node);
const cur_end_index = @atomicLoad(usize, &node.end_index, .monotonic);
if (buf_ptr + cur_end_index != memory.ptr + memory.len) {
// 不是最近一次分配,无法释放它。
return;
}
const new_end_index = cur_end_index - memory.len;
assert(buf_ptr + new_end_index == memory.ptr);
_ = @cmpxchgStrong(
usize,
&node.end_index,
cur_end_index,
new_end_index,
.release, // 释放已归还的内存
.monotonic,
);
}
const std = @import("std");
const assert = std.debug.assert;
const mem = std.mem;
const Allocator = std.mem.Allocator;
const Alignment = std.mem.Alignment;
test "reset with preheating" {
var arena_allocator = ArenaAllocator.init(std.testing.allocator);
defer arena_allocator.deinit();
// 使分配的数据具有一定差异
var rng_src = std.Random.DefaultPrng.init(std.testing.random_seed);
const random = rng_src.random();
var rounds: usize = 25;
while (rounds > 0) {
rounds -= 1;
_ = arena_allocator.reset(.retain_capacity);
var alloced_bytes: usize = 0;
const total_size: usize = random.intRangeAtMost(usize, 256, 16384);
while (alloced_bytes < total_size) {
const size = random.intRangeAtMost(usize, 16, 256);
const alignment: Alignment = .@"32";
const slice = try arena_allocator.allocator().alignedAlloc(u8, alignment, size);
try std.testing.expect(alignment.check(@intFromPtr(slice.ptr)));
try std.testing.expectEqual(size, slice.len);
alloced_bytes += slice.len;
}
}
}
test "reset while retaining a buffer" {
var arena_allocator = ArenaAllocator.init(std.testing.allocator);
defer arena_allocator.deinit();
const a = arena_allocator.allocator();
// 创建两个内部缓冲区
_ = try a.alloc(u8, 1);
try std.testing.expect(arena_allocator.state.used_list != null);
while (arena_allocator.state.used_list.?.next == null) {
_ = try a.alloc(u8, 1000);
}
// 保留首个分配的缓冲区
try std.testing.expect(arena_allocator.reset(.{ .retain_with_limit = 2 }));
try std.testing.expect(arena_allocator.state.used_list.?.next == null);
try std.testing.expectEqual(2, arena_allocator.queryCapacity());
}
test "fuzz multi threaded" {
@disableInstrumentation();
if (@import("builtin").single_threaded) return error.SkipZigTest;
const gpa = std.heap.smp_allocator;
var io_instance: std.Io.Threaded = .init(gpa, .{});
defer io_instance.deinit();
var arena_state: ArenaAllocator.State = .init;
// 无需 deinit arena_state,所有分配都位于 `sample_buffer` 中!
const buffer_size = FuzzContext.max_alloc_count * FuzzContext.max_alloc_size;
const control_buffer = try gpa.alloc(u8, buffer_size);
defer gpa.free(control_buffer);
var control_instance: std.heap.FixedBufferAllocator = .init(control_buffer);
const sample_buffer = try gpa.alloc(u8, buffer_size);
defer gpa.free(sample_buffer);
var sample_instance: FuzzAllocator = .init(sample_buffer);
try std.testing.fuzz(FuzzContext.Init{
.threaded_instance = &io_instance,
.arena_state = &arena_state,
.control_instance = &control_instance,
.sample_instance = &sample_instance,
}, fuzzMultiThreaded, .{});
}
fn fuzzMultiThreaded(fuzz_init: FuzzContext.Init, smith: *std.testing.Smith) anyerror!void {
@disableInstrumentation();
const testing = std.testing;
const io = fuzz_init.threaded_instance.io();
fuzz_init.sample_instance.prepareFailures(smith);
const control_allocator = fuzz_init.control_instance.threadSafeAllocator();
const sample_child_allocator = fuzz_init.sample_instance.allocator();
var arena_instance = fuzz_init.arena_state.*.promote(sample_child_allocator);
defer fuzz_init.arena_state.* = arena_instance.state;
var ctx: FuzzContext = .init(
control_allocator,
arena_instance.allocator(),
);
defer ctx.deinit();
var group: std.Io.Group = .init;
defer group.cancel(io);
var n_allocs: usize = 0;
var n_actions: usize = 0;
while (!smith.eosWeightedSimple(99, 1) and n_actions < FuzzContext.max_action_count) {
errdefer comptime unreachable;
const weights: []const testing.Smith.Weight = if (n_allocs == FuzzContext.max_alloc_count)
&.{
.value(FuzzContext.Action, .resize, 1),
.value(FuzzContext.Action, .remap, 1),
.value(FuzzContext.Action, .free, 1),
}
else
&.{
.value(FuzzContext.Action, .resize, 1),
.value(FuzzContext.Action, .remap, 1),
.value(FuzzContext.Action, .free, 1),
.value(FuzzContext.Action, .alloc, 3),
};
switch (smith.valueWeighted(FuzzContext.Action, weights)) {
.alloc => {
const alloc_index = n_allocs;
n_allocs += 1;
ctx.allocs[alloc_index].common.len = .free;
group.concurrent(io, FuzzContext.doOneAlloc, .{
&ctx,
nextLen(smith),
smith.valueRangeAtMost(
Alignment,
.@"1",
.fromByteUnits(2 * std.heap.page_size_max),
),
@fromBackingInt(@intCast(alloc_index)),
}) catch unreachable;
},
.resize => group.concurrent(io, FuzzContext.doOneResize, .{ &ctx, nextLen(smith) }) catch unreachable,
.remap => group.concurrent(io, FuzzContext.doOneRemap, .{ &ctx, nextLen(smith) }) catch unreachable,
.free => group.concurrent(io, FuzzContext.doOneFree, .{&ctx}) catch unreachable,
}
n_actions += 1;
}
try group.await(io);
try ctx.check(n_allocs);
// 这也覆盖 `deinit` 逻辑,因为 `free_all` 在内部使用它。
const old_capacity = arena_instance.queryCapacity();
const reset_mode: ResetMode = switch (smith.value(@typeInfo(ResetMode).@"union".tag_type.?)) {
.free_all => .free_all,
.retain_capacity => .retain_capacity,
.retain_with_limit => .{ .retain_with_limit = smith.value(usize) },
};
const ok = arena_instance.reset(reset_mode);
const new_capacity = arena_instance.queryCapacity();
switch (reset_mode) {
.free_all => {
try testing.expect(ok);
try testing.expectEqual(0, new_capacity);
fuzz_init.sample_instance.reset();
},
.retain_with_limit => |limit| if (ok) try testing.expect(new_capacity <= limit),
.retain_capacity => if (ok) try testing.expectEqual(old_capacity, new_capacity),
}
fuzz_init.control_instance.reset();
}
fn nextLen(smith: *std.testing.Smith) @typeInfo(FuzzContext.Alloc.Len).@"enum".tag_type {
@disableInstrumentation();
const BackingInt = @typeInfo(FuzzContext.Alloc.Len).@"enum".tag_type;
return smith.valueRangeAtMost(BackingInt, 1, FuzzContext.max_alloc_size);
}
const FuzzContext = struct {
control_allocator: Allocator,
sample_allocator: Allocator,
last_alloc_index: Alloc.Index,
allocs: [max_alloc_count]Alloc,
const max_alloc_count = 64;
const max_action_count = 2 * max_alloc_count;
const max_alloc_size = 16 << 10;
const Alloc = struct {
control_ptr: [*]u8,
sample_ptr: [*]u8,
common: packed struct(usize) {
len: Len,
alignment: Alignment,
_: @Int(.unsigned, padding_bits) = 0,
},
const Len = enum(@Int(.unsigned, len_bits)) {
free = (1 << len_bits) - 1,
_,
};
const len_bits = @min(64, @bitSizeOf(usize)) - @bitSizeOf(Alignment);
const padding_bits = @bitSizeOf(usize) - (len_bits + @bitSizeOf(Alignment));
const Index = enum(usize) {
none = std.math.maxInt(usize),
_,
};
};
const Action = enum {
alloc,
resize,
remap,
free,
};
const Init = struct {
threaded_instance: *std.Io.Threaded,
arena_state: *ArenaAllocator.State,
control_instance: *std.heap.FixedBufferAllocator,
sample_instance: *FuzzAllocator,
};
fn init(
control_allocator: Allocator,
sample_allocator: Allocator,
) FuzzContext {
@disableInstrumentation();
return .{
.control_allocator = control_allocator,
.sample_allocator = sample_allocator,
.last_alloc_index = .none,
.allocs = undefined,
};
}
fn deinit(ctx: *FuzzContext) void {
@disableInstrumentation();
ctx.* = undefined;
}
fn check(ctx: *const FuzzContext, n_allocs: usize) !void {
@disableInstrumentation();
for (ctx.allocs[0..n_allocs]) |allocation| {
const len: usize = switch (allocation.common.len) {
.free => continue,
_ => |len| @backingInt(len),
};
const control = allocation.control_ptr[0..len];
const sample = allocation.sample_ptr[0..len];
try std.testing.expectEqualSlices(u8, control, sample);
}
}
fn doOneAlloc(ctx: *FuzzContext, len: usize, alignment: Alignment, index: Alloc.Index) void {
@disableInstrumentation();
assert(ctx.allocs[@backingInt(index)].common.len == .free);
const control_ptr = ctx.control_allocator.rawAlloc(len, alignment, @returnAddress()) orelse
return;
const sample_ptr = ctx.sample_allocator.rawAlloc(len, alignment, @returnAddress()) orelse {
ctx.control_allocator.rawFree(control_ptr[0..len], alignment, @returnAddress());
return;
};
ctx.allocs[@backingInt(index)] = .{
.control_ptr = control_ptr,
.sample_ptr = sample_ptr,
.common = .{
.len = @fromBackingInt(@intCast(len)),
.alignment = alignment,
},
};
for (control_ptr[0..len], sample_ptr[0..len], 0..) |*control, *sample, i| {
control.* = @truncate(i);
sample.* = @truncate(i);
}
@atomicStore(Alloc.Index, &ctx.last_alloc_index, index, .release);
}
fn doOneResize(ctx: *FuzzContext, new_len: usize) void {
@disableInstrumentation();
const index = @atomicRmw(Alloc.Index, &ctx.last_alloc_index, .Xchg, .none, .acquire);
if (index == .none) return;
const allocation = &ctx.allocs[@backingInt(index)];
assert(allocation.common.len != .free);
const memory = allocation.sample_ptr[0..@backingInt(allocation.common.len)];
const alignment = allocation.common.alignment;
assert(alignment.check(@intFromPtr(allocation.control_ptr)));
assert(alignment.check(@intFromPtr(allocation.sample_ptr)));
// 由于 `resize` 可能失败,必须提前预留所需内存,
// 以确保 `control_allocator` 始终成功。
const new_control_ptr = ctx.control_allocator.rawAlloc(new_len, alignment, @returnAddress()) orelse
return;
if (ctx.sample_allocator.rawResize(memory, alignment, new_len, @returnAddress())) {
const old_control = allocation.control_ptr[0..memory.len];
const overlap = @min(memory.len, new_len);
@memcpy(new_control_ptr[0..overlap], old_control[0..overlap]);
ctx.control_allocator.rawFree(old_control, alignment, @returnAddress());
} else {
ctx.control_allocator.rawFree(new_control_ptr[0..new_len], alignment, @returnAddress());
return;
}
ctx.allocs[@backingInt(index)] = .{
.control_ptr = new_control_ptr,
.sample_ptr = memory.ptr,
.common = .{
.len = @fromBackingInt(@intCast(new_len)),
.alignment = alignment,
},
};
if (new_len > memory.len) {
for (
allocation.control_ptr[memory.len..new_len],
allocation.sample_ptr[memory.len..new_len],
0..,
) |*control, *sample, i| {
control.* = @truncate(i);
sample.* = @truncate(i);
}
}
@atomicStore(Alloc.Index, &ctx.last_alloc_index, index, .release);
}
fn doOneRemap(ctx: *FuzzContext, new_len: usize) void {
@disableInstrumentation();
return doOneResize(ctx, new_len);
}
fn doOneFree(ctx: *FuzzContext) void {
@disableInstrumentation();
const index = @atomicRmw(Alloc.Index, &ctx.last_alloc_index, .Xchg, .none, .acquire);
if (index == .none) return;
const allocation = &ctx.allocs[@backingInt(index)];
assert(allocation.common.len != .free);
const len: usize = @backingInt(allocation.common.len);
const alignment = allocation.common.alignment;
assert(alignment.check(@intFromPtr(allocation.control_ptr)));
assert(alignment.check(@intFromPtr(allocation.sample_ptr)));
ctx.control_allocator.rawFree(allocation.control_ptr[0..len], alignment, @returnAddress());
ctx.sample_allocator.rawFree(allocation.sample_ptr[0..len], alignment, @returnAddress());
ctx.allocs[@backingInt(index)] = .{
.control_ptr = undefined,
.sample_ptr = undefined,
.common = .{
.len = .free,
.alignment = .@"1",
},
};
}
};
const FuzzAllocator = struct {
fba: std.heap.FixedBufferAllocator,
spurious_failures: [256]u8,
index: u8,
fn init(buffer: []u8) FuzzAllocator {
@disableInstrumentation();
return .{
.fba = .init(buffer),
.spurious_failures = undefined, // 通过 `preprepareFailures` 设置
.index = 0,
};
}
fn prepareFailures(fa: *FuzzAllocator, smith: *std.testing.Smith) void {
@disableInstrumentation();
const bool_weights: []const std.testing.Smith.Weight = &.{
.value(u8, 0, 10),
.value(u8, 1, 1),
};
smith.bytesWeighted(&fa.spurious_failures, bool_weights);
fa.index = 0;
}
fn reset(fa: *FuzzAllocator) void {
@disableInstrumentation();
fa.fba.reset();
}
fn allocator(fa: *FuzzAllocator) Allocator {
@disableInstrumentation();
return .{
.ptr = fa,
.vtable = &.{
.alloc = FuzzAllocator.alloc,
.resize = FuzzAllocator.resize,
.remap = FuzzAllocator.remap,
.free = FuzzAllocator.free,
},
};
}
fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {
@disableInstrumentation();
const fa: *FuzzAllocator = @ptrCast(@alignCast(ctx));
_ = ret_addr;
const index = @atomicRmw(u8, &fa.index, .Add, 1, .monotonic);
if (fa.spurious_failures[index] != 0) return null;
return fa.fba.threadSafeAllocator().rawAlloc(len, alignment, @returnAddress());
}
fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) bool {
@disableInstrumentation();
const fa: *FuzzAllocator = @ptrCast(@alignCast(ctx));
_ = ret_addr;
const index = @atomicRmw(u8, &fa.index, .Add, 1, .monotonic);
if (fa.spurious_failures[index] != 0) return false;
return fa.fba.threadSafeAllocator().rawResize(memory, alignment, new_len, @returnAddress());
}
fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
@disableInstrumentation();
const fa: *FuzzAllocator = @ptrCast(@alignCast(ctx));
_ = ret_addr;
const index = @atomicRmw(u8, &fa.index, .Add, 1, .monotonic);
if (fa.spurious_failures[index] != 0) return null;
return fa.fba.threadSafeAllocator().rawRemap(memory, alignment, new_len, @returnAddress());
}
fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, ret_addr: usize) void {
@disableInstrumentation();
const fa: *FuzzAllocator = @ptrCast(@alignCast(ctx));
_ = ret_addr;
return fa.fba.threadSafeAllocator().rawFree(memory, alignment, @returnAddress());
}
};