提供以下保证:
deinit报告所有泄漏并释放全部底层内存。- 所有分配不匹配都会导致 panic 或段错误。
- 来自其他
SafeAllocator实例的分配会导致 panic,前提是Options.canary不同。 - 重复释放及操作竞态(resize、remap 和 free)会导致 panic 或段错误。
如果底层分配器不复用内存,则此分配器也不复用内存,且
- 释放后的大多数写入会发生段错误,或最终被检测到并触发 panic。
线程安全。
字段
backing: mem.Allocator
threads: [128]Thread
bucket_size_log2: u5
block_size_log2: u5
stack_trace_size: usize以 usize 为单位
allocs_entry_count: usize以 usize 为单位
large_alloc_threshold: usize
canary: u32
check_write_after_free: bool
stdmathmemAlignmentassertpanicSafeAllocatorscoped_logOptionsn_threadsthread_indexbucketSizebucketMaskThreadAllocsBucketAllocFooterinitdeinitdeinitLogdeinitLeakedBucketdeinitLargeAllocallocatoracquireThreadalignForwardOrOomaddOrOomisLargeisLargeOrOomnewAllocEntryfreeAllocEntryoverwriteFreedcheckFreedFormatMemorycaptureStackTraceformatStackTraceallocBucketgrowingResizeBucketadvanceBucketAllocvtableallocfreeresizeremapSmithfuzz_probsFuzzSingleThreadedContextFuzzSingleThreadedAllocatorfuzzSingleThreadedFuzzMultiThreadedContextFuzzMultiThreadedAllocatorfuzzMultiThreadedfuzzMultiThreadedWorker
std.heap.SafeAllocator.acquireThread
函数
fn acquireThread(s: *SafeAllocator) *Thread
参数
s: *SafeAllocator
std.heap.SafeAllocator.addOrOom
函数
fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize
参数
a: usize
b: usize
错误
- OutOfMemory
std.heap.SafeAllocator.advanceBucketAlloc
函数
fn advanceBucketAlloc( s: *SafeAllocator, old: *AllocFooter, new_start: u32, start_moved: bool, alignment: Alignment, new_len: usize, ra: usize, ) bool
参数
s: *SafeAllocator
old: *AllocFooter
new_start: u32
start_moved: bool
alignment: Alignment
new_len: usize
ra: usize
std.heap.SafeAllocator.alignForwardOrOom
函数
fn alignForwardOrOom(a: Alignment, addr: usize) error{OutOfMemory}!usize
参数
a: Alignment
addr: usize
错误
- OutOfMemory
std.heap.SafeAllocator.Alignment
别名
别名目标 std.mem.Alignment
std.heap.SafeAllocator.alloc
函数
fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, ra: usize) ?[*]u8
参数
std.heap.SafeAllocator.allocator
函数
返回的分配器是线程安全的
pub fn allocator(s: *SafeAllocator) mem.Allocator
参数
s: *SafeAllocator
std.heap.SafeAllocator.allocBucket
函数
若此操作失败,后续向该桶分配内存均不合法
fn allocBucket( s: *SafeAllocator, t: *Thread, b: *Bucket, len: usize, alignment: Alignment, ra: usize, ) ?[*]u8
参数
std.heap.SafeAllocator.Allocs
容器
后面跟随 [allocs_entry_count]Entry
字段
next: ?*Allocs
std.heap.SafeAllocator.Allocs.entries
函数
fn entries(a: *Allocs, s: *SafeAllocator) []Entry
参数
a: *Allocs
s: *SafeAllocator
std.heap.SafeAllocator.Allocs.Entry
容器
字段
kind: Kind
ptr_high: @Int(.unsigned, @bitSizeOf(usize) - 2)
std.heap.SafeAllocator.Allocs.Entry.fromBucket
函数
fn fromBucket(ptr: *Bucket) Entry
参数
ptr: *Bucket
std.heap.SafeAllocator.Allocs.Entry.fromFree
函数
fn fromFree(ptr: ?*Entry) Entry
参数
ptr: ?*Entry
std.heap.SafeAllocator.Allocs.Entry.fromLargeAlloc
函数
fn fromLargeAlloc(ptr: *AllocFooter) Entry
参数
ptr: *AllocFooter
std.heap.SafeAllocator.Allocs.Entry.Kind
容器
字段
std.heap.SafeAllocator.Allocs.Entry.toBucket
函数
fn toBucket(ent: Entry) *Bucket
参数
ent: Entry
std.heap.SafeAllocator.Allocs.Entry.toFree
函数
fn toFree(ent: Entry) ?*Entry
参数
ent: Entry
std.heap.SafeAllocator.Allocs.Entry.toLargeAlloc
函数
fn toLargeAlloc(ent: Entry) *AllocFooter
参数
ent: Entry
std.heap.SafeAllocator.Allocs.usizes
函数
fn usizes(a: *Allocs, s: *SafeAllocator) []usize
参数
a: *Allocs
s: *SafeAllocator
std.heap.SafeAllocator.assert
别名
别名目标 std.debug.assert
std.heap.SafeAllocator.Bucket
容器
此结构体包含桶头,始终属于一个更大的分配,
该分配的长度与对齐均为 bucketSize()。
桶内全部分配至少按 8 字节对齐,包括长度, 因此对齐要求不超过 8 字节的分配无需保存 前一个尾部的位置,因为该尾部就在其正前方。非扩展 尾部利用此性质省略前一个尾部的偏移量。
字段
entry: *Allocs.Entry
alloc_count: AllocCount以 .acquire / .release 顺序原子访问,
为分配尾部元数据提供内存顺序,但 modify 字段
除外。每次更新尾部数据时,都需要执行 .acquire
栅栏(AllocCount.fenceAcqRel)。
fill: Fill以 .monotonic 顺序进行原子访问。也可以
通过 alloc_count 同步。
_: void align(8) = {}使对齐要求不超过 8 字节时,@sizeOf(Bucket) 即为第一次分配的起始位置。
std.heap.SafeAllocator.Bucket.AllocCount
容器
字段
n: u31
filling: bool若为 true,此桶暂时不能释放。
std.heap.SafeAllocator.Bucket.AllocCount.fenceAcqRel
函数
fn fenceAcqRel(a: *AllocCount) void
参数
a: *AllocCount
std.heap.SafeAllocator.Bucket.bytes
函数
fn bytes(b: *Bucket, s: *SafeAllocator) []u8
参数
b: *Bucket
s: *SafeAllocator
std.heap.SafeAllocator.Bucket.check
函数
检查是否存在释放后写入。
假定已使用 .acquire 顺序加载 b.alloc_count。
fn check(b: *Bucket, s: *SafeAllocator) void
参数
b: *Bucket
s: *SafeAllocator
std.heap.SafeAllocator.Bucket.Fill
容器
字段
at: u31
last_is_extended: bool
std.heap.SafeAllocator.Bucket.fillAt
函数
fn fillAt(s: *SafeAllocator, ptr: [*]const u8) u32
参数
s: *SafeAllocator
ptr: [*]const u8
std.heap.SafeAllocator.Bucket.lastAlloc
函数
fn lastAlloc(b: *Bucket, s: *SafeAllocator, fill: Fill) ?*AllocFooter
参数
std.heap.SafeAllocator.Bucket.of
函数
fn of(s: *SafeAllocator, ptr: [*]u8) *Bucket
参数
s: *SafeAllocator
ptr: [*]u8
std.heap.SafeAllocator.bucketMask
函数
fn bucketMask(s: *SafeAllocator) u32
参数
s: *SafeAllocator
std.heap.SafeAllocator.bucketSize
函数
fn bucketSize(s: *SafeAllocator) u32
参数
s: *SafeAllocator
std.heap.SafeAllocator.captureStackTrace
函数
首个元素存储包括已跳过栈帧在内的栈轨迹长度。 其余元素存储返回地址。
fn captureStackTrace(trace_buf: []usize, ra: usize) void
参数
trace_buf: []usize
ra: usize
std.heap.SafeAllocator.checkFreed
函数
返回首次释放后写入的地址
fn checkFreed(s: *SafeAllocator, footer: *AllocFooter) void
参数
s: *SafeAllocator
footer: *AllocFooter
std.heap.SafeAllocator.deinit
函数
返回泄漏数量
pub fn deinit(s: *SafeAllocator) usize
参数
s: *SafeAllocator
std.heap.SafeAllocator.deinitLargeAlloc
函数
fn deinitLargeAlloc(s: *SafeAllocator, footer: *AllocFooter, log: bool) void
参数
std.heap.SafeAllocator.deinitLeakedBucket
函数
返回实际的泄漏数量
fn deinitLeakedBucket(s: *SafeAllocator, b: *Bucket, log: bool) usize
参数
std.heap.SafeAllocator.deinitLog
函数
与 deinit 相同,但若 log 为 false,则不会记录内存泄漏。
pub fn deinitLog(s: *SafeAllocator, log: bool) usize
参数
s: *SafeAllocator
log: bool
std.heap.SafeAllocator.FormatMemory
容器
字段
memory: []const u8
alignment: Alignment
std.heap.SafeAllocator.FormatMemory.format
函数
pub fn format(m: FormatMemory, w: *std.Io.Writer) std.Io.Writer.Error!void
参数
m: FormatMemory
w: *std.Io.Writer
错误
- WriteFailed
详细诊断信息见
Writer实现。
std.heap.SafeAllocator.formatStackTrace
函数
fn formatStackTrace(trace_buf: []usize) std.debug.FormatStackTrace
参数
trace_buf: []usize
std.heap.SafeAllocator.free
函数
fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, ra: usize) void
参数
std.heap.SafeAllocator.freeAllocEntry
函数
fn freeAllocEntry(t: *Thread, ent: *Allocs.Entry) void
参数
std.heap.SafeAllocator.fuzz_probs
命名空间
由单线程和多线程模糊测试共享。
std.heap.SafeAllocator.fuzz_probs.alignment
常量
[]const Smith.Weight
std.heap.SafeAllocator.fuzz_probs.checkSplat
函数
fn checkSplat(splat: ?u8, bytes: []const u8) void
参数
splat: ?u8
bytes: []const u8
std.heap.SafeAllocator.fuzz_probs.eos
常量
[]const Smith.Weight
std.heap.SafeAllocator.fuzz_probs.generateLen
函数
fn generateLen(smith: *Smith, will_memset: bool) usize
参数
smith: *Smith
will_memset: bool
std.heap.SafeAllocator.fuzz_probs.generateOp
函数
fn generateOp(smith: *Smith, any_allocs: bool) Op
参数
smith: *Smith
any_allocs: bool
std.heap.SafeAllocator.fuzz_probs.generateOptions
函数
fn generateOptions(smith: *Smith) Options
参数
smith: *Smith
std.heap.SafeAllocator.fuzz_probs.generateSplat
函数
fn generateSplat(smith: *Smith) ?u8
参数
smith: *Smith
std.heap.SafeAllocator.fuzz_probs.Op
容器
字段
std.heap.SafeAllocator.fuzzMultiThreaded
函数
fn fuzzMultiThreaded(ctx: FuzzMultiThreadedContext, smith: *Smith) !void
参数
ctx: FuzzMultiThreadedContext
smith: *Smith
std.heap.SafeAllocator.FuzzMultiThreadedAllocator
容器
保证内存不会被重用。
字段
std.heap.SafeAllocator.FuzzMultiThreadedAllocator.alloc
函数
fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, _: usize) ?[*]u8
参数
std.heap.SafeAllocator.FuzzMultiThreadedAllocator.allocator
函数
fn allocator(f: *FuzzMultiThreadedAllocator) mem.Allocator
参数
std.heap.SafeAllocator.FuzzMultiThreadedAllocator.allocInner
函数
fn allocInner(f: *FuzzMultiThreadedAllocator, len: usize, alignment: Alignment) ?[*]u8
参数
std.heap.SafeAllocator.FuzzMultiThreadedAllocator.free
函数
fn free(ctx: *anyopaque, _: []u8, _: Alignment, _: usize) void
参数
std.heap.SafeAllocator.FuzzMultiThreadedAllocator.maybeFail
函数
fn maybeFail(f: *FuzzMultiThreadedAllocator) bool
参数
std.heap.SafeAllocator.FuzzMultiThreadedAllocator.maybeFixedRemap
函数
fn maybeFixedRemap(f: *FuzzMultiThreadedAllocator) bool
参数
std.heap.SafeAllocator.FuzzMultiThreadedAllocator.remap
函数
fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, _: usize) ?[*]u8
参数
std.heap.SafeAllocator.FuzzMultiThreadedAllocator.resize
函数
fn resize(ctx: *anyopaque, memory: []u8, _: Alignment, new_len: usize, _: usize) bool
参数
std.heap.SafeAllocator.FuzzMultiThreadedContext
容器
字段
std.heap.SafeAllocator.FuzzMultiThreadedContext.n_threads
常量
std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps
容器
字段
run: Run每次运行开始时在两个值之间切换。
running: u32虽然可计算为 n_threads - (i -| ops.items.len),
但此操作也为每个线程提供 .release 同步。
instance: SafeAllocator
i: usize
items: []Op
std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Op
容器
字段
alloc: struct {
len: usize,
alignment: Alignment,
splat: ?u8,
/// 为绕过 tsan 问题,不直接嵌入结构体;
/// 因为直接对 `Op` 执行 switch 会非原子地加载整个值。
result: *MemoryDependency,
}
free: struct {
memory: *MemoryDependency,
alignment: Alignment,
splat: ?u8,
}
resize: Realloc
remap: Realloc
std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Op.MemoryDependency
容器
字段
std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Op.MemoryDependency.get
函数
fn get(dep: *MemoryDependency, io: std.Io) ?[]u8
参数
dep: *MemoryDependency
io: std.Io
std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Op.MemoryDependency.init
常量
MemoryDependency
std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Op.Realloc
容器
字段
memory: *MemoryDependency
alignment: Alignment
new_len: usize
splat: ?u8
result: *MemoryDependency为绕过 tsan 问题,不直接嵌入结构体;
因为直接对 Op 执行 switch 会非原子地加载整个值。
std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Run
容器
字段
n: bool
pad: u31 = 0
std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Run.next
函数
fn next(r: Run) Run
参数
r: Run
std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Run.wait
函数
fn wait(ptr: *Run, val: Run, io: std.Io) error{Canceled}!void
参数
错误
- Canceled
std.heap.SafeAllocator.fuzzMultiThreadedWorker
函数
fn fuzzMultiThreadedWorker( io: std.Io, ops: *FuzzMultiThreadedContext.ThreadOps, ) error{Canceled}!void
参数
io: std.Io
ops: *FuzzMultiThreadedContext.ThreadOps
错误
- Canceled
std.heap.SafeAllocator.fuzzSingleThreaded
函数
fn fuzzSingleThreaded(ctx: FuzzSingleThreadedContext, smith: *Smith) !void
参数
ctx: FuzzSingleThreadedContext
smith: *Smith
std.heap.SafeAllocator.FuzzSingleThreadedAllocator
容器
保证内存不会被重用。
字段
std.heap.SafeAllocator.FuzzSingleThreadedAllocator.alloc
函数
fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, _: usize) ?[*]u8
参数
std.heap.SafeAllocator.FuzzSingleThreadedAllocator.allocator
函数
fn allocator(f: *FuzzSingleThreadedAllocator) mem.Allocator
参数
std.heap.SafeAllocator.FuzzSingleThreadedAllocator.allocIndex
函数
fn allocIndex(f: *FuzzSingleThreadedAllocator, memory: []u8, alignment: Alignment) usize
参数
std.heap.SafeAllocator.FuzzSingleThreadedAllocator.AllocInfo
容器
字段
std.heap.SafeAllocator.FuzzSingleThreadedAllocator.allocInner
函数
fn allocInner(f: *FuzzSingleThreadedAllocator, len: usize, alignment: Alignment) ?[*]u8
参数
std.heap.SafeAllocator.FuzzSingleThreadedAllocator.free
函数
fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, _: usize) void
参数
std.heap.SafeAllocator.FuzzSingleThreadedAllocator.remap
函数
fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, _: usize) ?[*]u8
参数
std.heap.SafeAllocator.FuzzSingleThreadedAllocator.resize
函数
fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, _: usize) bool
参数
std.heap.SafeAllocator.FuzzSingleThreadedContext
容器
字段
testing_buf: []u8
backing_buf: []u8
std.heap.SafeAllocator.growingResizeBucket
函数
fn growingResizeBucket( s: *SafeAllocator, f: *AllocFooter, memory: []const u8, alignment: Alignment, new_len: usize, ra: usize, ) bool
参数
std.heap.SafeAllocator.init
函数
pub fn init( backing: mem.Allocator, options: Options, ) SafeAllocator
参数
std.heap.SafeAllocator.isLarge
函数
fn isLarge(s: *SafeAllocator, len: usize, alignment: Alignment) bool
参数
std.heap.SafeAllocator.isLargeOrOom
函数
fn isLargeOrOom(s: *SafeAllocator, len: usize, alignment: Alignment) error{OutOfMemory}!bool
参数
错误
- OutOfMemory
std.heap.SafeAllocator.math
别名
别名目标 std.math
std.heap.SafeAllocator.mem
别名
别名目标 std.mem
std.heap.SafeAllocator.n_threads
变量
usize
std.heap.SafeAllocator.newAllocEntry
函数
fn newAllocEntry(s: *SafeAllocator, t: *Thread, ra: usize) error{OutOfMemory}!*Allocs.Entry
参数
错误
- OutOfMemory
std.heap.SafeAllocator.Options
容器
字段
stack_trace_frames: usize = if (is_debug and std.debug.sys_can_stack_trace) 7 else 0
check_write_after_free: bool = is_debug
canary: u32 = 0x85dff10f用于检查其他 SafeAllocator 实例创建的分配是否被传入当前实例的唯一值。
bucket_size_log2: u5 = @max(page_size_log2, 13)控制分配桶的块大小和对齐方式。
如果后备分配器提供更细的粒度,或限制活动分配数量, 修改此值可节省内存,但减小此值 可能降低性能。
断言其 >= 8。
block_size_log2: u5 = page_size_log2控制内部元数据的块大小。
如果底层分配器提供更细的分配粒度,或限制活动分配 数量,可更改此值以节省内存;但减小它 可能损害性能。
断言其 >= 8。
std.heap.SafeAllocator.Options.is_debug
常量
std.heap.SafeAllocator.Options.page_size_log2
常量
std.heap.SafeAllocator.overwriteFreed
函数
fn overwriteFreed(s: *SafeAllocator, bytes: []u8) void
参数
s: *SafeAllocator
bytes: []u8
std.heap.SafeAllocator.panic
别名
别名目标 std.debug.panic
std.heap.SafeAllocator.remap
函数
fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) ?[*]u8
参数
std.heap.SafeAllocator.resize
函数
fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) bool
参数
std.heap.SafeAllocator.SafeAllocator
别名
std.heap.SafeAllocator.scoped_log
类型
std.heap.SafeAllocator.Smith
别名
别名目标 std.testing.Smith
std.heap.SafeAllocator.std
别名
别名目标 std
std.heap.SafeAllocator.Thread
容器
字段
std.heap.SafeAllocator.thread_index
变量
usize
std.heap.SafeAllocator.vtable
常量
mem.Allocator.VTable
源码
std/heap/SafeAllocator.zig
//! 提供以下保证:
//! * `deinit` 报告所有泄漏并释放全部底层内存。
//! * 所有分配不匹配都会导致 panic 或段错误。
//! * 来自其他 `SafeAllocator` 实例的分配会导致 panic,前提是 `Options.canary` 不同。
//! * 重复释放及操作竞态(resize、remap 和 free)会导致 panic 或段错误。
//!
//! 如果底层分配器不复用内存,则此分配器也不复用内存,且
//! * 释放后的大多数写入会发生段错误,或最终被检测到并触发 panic。
//!
//! 线程安全。
// 总体设计:
//
// 每次分配的内存后都跟随一个 `AllocFooter`,其中包含该次分配的元数据和栈跟踪。它由校验和保护,以检测越界写导致的损坏并报告金丝雀值不匹配。分配内存的最小对齐要求为 `AllocFooter` 的对齐要求,因此可根据分配大小确定尾部结构的固定偏移量。分配内存存放在以下两处之一:
// * 对于小块分配,放在线性填充的桶中。
// * 放在直接从后备分配器取得的分配块中。
//
// 为跟踪分配,每个线程维护一张后备分配表。在生产者—消费者操作中,其他线程可能修改该表,因此它采用链表形式,仅通过创建新段扩展。每个线程还维护空闲条目的链表,其中可能包含其他线程分配表中的条目。
//
// 对于生产者—消费者操作,假定外部已提供获取/释放内存序。所有会复用内存的其他线程安全分配器也有相同假定,否则复用已分配内存时会发生数据竞争。
//
//
//
//
//
//
//
//
//
const std = @import("../std.zig");
const math = std.math;
const mem = std.mem;
const Alignment = mem.Alignment;
const assert = std.debug.assert;
const panic = std.debug.panic;
const SafeAllocator = @This();
const scoped_log = std.log.scoped(.SafeAllocator);
pub const Options = struct {
const is_debug = @import("builtin").mode == .debug;
const page_size_log2 = @max(math.log2_int(usize, std.heap.page_size_max), 8);
stack_trace_frames: usize = if (is_debug and std.debug.sys_can_stack_trace) 7 else 0,
check_write_after_free: bool = is_debug,
/// 用于检查其他 `SafeAllocator` 实例创建的分配是否被传入当前实例的唯一值。
///
canary: u32 = 0x85dff10f,
/// 控制分配桶的块大小和对齐方式。
///
/// 如果后备分配器提供更细的粒度,或限制活动分配数量,
/// 修改此值可节省内存,但减小此值
/// 可能降低性能。
///
/// 断言其 >= 8。
bucket_size_log2: u5 = @max(page_size_log2, 13),
/// 控制内部元数据的块大小。
///
/// 如果底层分配器提供更细的分配粒度,或限制活动分配
/// 数量,可更改此值以节省内存;但减小它
/// 可能损害性能。
///
/// 断言其 >= 8。
block_size_log2: u5 = page_size_log2,
};
var n_threads: usize = 0;
threadlocal var thread_index: usize = 0;
backing: mem.Allocator,
// 必须采用固定大小,以便所有实例对最大 `n_threads` 值达成一致。
threads: [128]Thread,
bucket_size_log2: u5,
block_size_log2: u5,
/// 以 `usize` 为单位
stack_trace_size: usize,
/// 以 `usize` 为单位
allocs_entry_count: usize,
large_alloc_threshold: usize,
canary: u32,
check_write_after_free: bool,
fn bucketSize(s: *SafeAllocator) u32 {
return @as(u32, 1) << s.bucket_size_log2;
}
fn bucketMask(s: *SafeAllocator) u32 {
return s.bucketSize() - 1;
}
const Thread = struct {
/// 避免伪共享。
_: void align(std.atomic.cache_line) = {},
mutex: std.atomic.Mutex,
fill_bucket: ?*Bucket,
free_entry: ?*Allocs.Entry,
allocs_next: usize,
allocs_first: ?*Allocs,
};
/// 后面跟随 `[allocs_entry_count]Entry`
const Allocs = extern struct {
next: ?*Allocs,
comptime {
assert(@alignOf(@This()) == @alignOf(usize));
assert(@sizeOf(@This()) == @sizeOf(usize));
}
fn usizes(a: *Allocs, s: *SafeAllocator) []usize {
return @as([*]usize, @ptrCast(a))[0 .. 1 + s.allocs_entry_count];
}
fn entries(a: *Allocs, s: *SafeAllocator) []Entry {
return @as([*]Entry, @ptrCast(a))[1..][0..s.allocs_entry_count];
}
const Entry = packed struct(usize) {
kind: Kind,
ptr_high: @Int(.unsigned, @bitSizeOf(usize) - 2),
const Kind = enum(u2) { free, bucket, large_alloc };
comptime {
assert(@alignOf(Entry) >= 4);
assert(@alignOf(Bucket) >= 4);
assert(@alignOf(AllocFooter) >= 4);
}
fn fromFree(ptr: ?*Entry) Entry {
return .{
.ptr_high = @intCast(@intFromPtr(ptr) >> 2),
.kind = .free,
};
}
fn fromBucket(ptr: *Bucket) Entry {
return .{
.ptr_high = @intCast(@intFromPtr(ptr) >> 2),
.kind = .bucket,
};
}
fn fromLargeAlloc(ptr: *AllocFooter) Entry {
return .{
.ptr_high = @intCast(@intFromPtr(ptr) >> 2),
.kind = .large_alloc,
};
}
fn toFree(ent: Entry) ?*Entry {
assert(ent.kind == .free);
return @ptrFromInt(@as(usize, ent.ptr_high) << 2);
}
fn toBucket(ent: Entry) *Bucket {
assert(ent.kind == .bucket);
return @ptrFromInt(@as(usize, ent.ptr_high) << 2);
}
fn toLargeAlloc(ent: Entry) *AllocFooter {
assert(ent.kind == .large_alloc);
return @ptrFromInt(@as(usize, ent.ptr_high) << 2);
}
};
};
/// 此结构体包含桶头,始终属于一个更大的分配,
/// 该分配的长度与对齐均为 `bucketSize()`。
///
/// 桶内全部分配至少按 8 字节对齐,包括长度,
/// 因此对齐要求不超过 8 字节的分配无需保存
/// 前一个尾部的位置,因为该尾部就在其正前方。非扩展
/// 尾部利用此性质省略前一个尾部的偏移量。
const Bucket = struct {
entry: *Allocs.Entry,
/// 以 `.acquire` / `.release` 顺序原子访问,
/// 为分配尾部元数据提供内存顺序,但 **`modify` 字段
/// 除外**。每次更新尾部数据时,都需要执行 `.acquire`
/// 栅栏(`AllocCount.fenceAcqRel`)。
alloc_count: AllocCount,
/// 以 `.monotonic` 顺序进行原子访问。也可以
/// 通过 `alloc_count` 同步。
fill: Fill,
/// 使对齐要求不超过 8 字节时,`@sizeOf(Bucket)` 即为第一次分配的起始位置。
_: void align(8) = {},
comptime {
assert(@alignOf(@This()) >= 8);
}
const AllocCount = packed struct(u32) {
n: u31,
/// 若为 `true`,此桶暂时不能释放。
filling: bool,
fn fenceAcqRel(a: *AllocCount) void {
_ = @atomicRmw(AllocCount, a, .Or, .{ .n = 0, .filling = false }, .acq_rel);
}
};
const Fill = packed struct(u32) {
at: u31,
last_is_extended: bool,
};
fn of(s: *SafeAllocator, ptr: [*]u8) *Bucket {
const size_log2 = s.bucket_size_log2;
return @ptrFromInt(@intFromPtr(ptr) >> @intCast(size_log2) << @intCast(size_log2));
}
fn fillAt(s: *SafeAllocator, ptr: [*]const u8) u32 {
return @intCast(@intFromPtr(ptr) & s.bucketMask());
}
fn bytes(b: *Bucket, s: *SafeAllocator) []u8 {
assert(@intFromPtr(b) & s.bucketMask() == 0);
return @as([*]u8, @ptrCast(b))[0..s.bucketSize()];
}
fn lastAlloc(b: *Bucket, s: *SafeAllocator, fill: Fill) ?*AllocFooter {
return b.allocFooterBefore(s, fill.at, fill.last_is_extended);
}
fn allocFooterBefore(b: *Bucket, s: *SafeAllocator, at: u32, is_extended: bool) ?*AllocFooter {
if (at - @sizeOf(Bucket) == 0) return null;
const off = at - AllocFooter.lenBucket(s, is_extended);
assert(off >= @sizeOf(Bucket));
return @ptrCast(@alignCast(b.bytes(s)[off..]));
}
/// 检查是否存在释放后写入。
///
/// 假定已使用 `.acquire` 顺序加载 `b.alloc_count`。
fn check(b: *Bucket, s: *SafeAllocator) void {
var footer = b.lastAlloc(s, b.fill).?;
while (true) {
const modify = @atomicLoad(
AllocFooter.Modify,
&footer.modify,
// 唯一可能的值应为 `.freed`,因为 `b.alloc_count`
// 已用 `.acquire` 加载。不过,另一线程可能试图在
// 分配释放后修改它,因此即使此线程仍看到 `.freed`,
// 另一线程也会 panic。
.unordered,
).storedXor(&footer.modify);
if (modify != .freed or footer.actualChecksum(s) != footer.checksum ^ s.canary) {
panic("corrupted footer metadata in bucket at *{x}", .{@intFromPtr(&footer)});
}
s.checkFreed(footer);
footer = footer.bucketPrev(b, s) orelse break;
}
}
};
/// 放在分配块尾部,有以下优点:
/// * 对于桶,最后一个分配块的尾部结构始终位于当前填充位置。
/// * 更容易对齐分配块,浪费的空间更少。
/// * 越界写更可能破坏尾部结构,从而被检测出来。
/// 对于桶内分配,其后跟随 `[2][stack_trace_size]usize`。
/// 对于大块分配,其后跟随 `[1][stack_trace_size]usize`。
const AllocFooter = struct {
/// 使用数据地址的哈希作为种子,计算 `data` 的哈希,从而检测分配
/// 元数据被 memcpy;若不能即时检测,至少能在不同运行期间发现。
///
/// 将此存储值与 canary 值异或,以便检测 canary 不匹配。
checksum: u32,
/// 以 `.monotonic` 内存顺序原子访问,以捕获操作竞态。
///
/// 存储值与其地址的哈希异或,以检测分配元数据的内存复制,
/// 或至少在不同运行之间捕获这种复制。
modify: Modify,
data: Data,
/// `8`:`Bucket` 分配的最小对齐值
/// `@alignOf(usize)`:使尾随数据的偏移位于 `@sizeOf(@This())`
_: void align(@max(8, @alignOf(usize))) = {},
comptime {
assert(@alignOf(@This()) >= @max(8, @alignOf(usize)));
}
const Data = packed struct(u16) {
len: Len,
/// 对齐量的低位。
///
/// 对于非扩展标头,这就是完整对齐量。由于 `Bucket` 中的页脚保证
/// 至少按 8 字节对齐,前一个标头的位置就在此次分配之前。
///
alignment: u2,
/// 仅用于桶式分配。
prev_extended: bool,
const Len = enum(u13) {
_,
/// 此尾部后面、跟踪信息之前,跟随 `Extended`。
/// 对齐值的高位编码为相对于 `extended_start` 的偏移量。
///
/// 即使严格来说不需要 `Extended`,也可能因
/// 调整大小和重新映射而设置此标志。
const extended_start: u13 = math.maxInt(u13) - ((@bitSizeOf(usize) - 1) >> 2);
};
};
const Extended = struct {
len: usize,
container: Container,
const Container = union {
bucket_prev: ?*AllocFooter,
large_entry: *Allocs.Entry,
};
comptime {
// 恰好为 `usize`,使其紧接常规尾部,
// 并使跟踪信息紧接 `@sizeOf(@This())`。
assert(@alignOf(@This()) == @alignOf(usize));
}
};
const Modify = enum(u16) {
// 采用随机、非线性的枚举值,以降低数据损坏未被检测到的概率。
none = 0x2962,
resized = 0x0030,
remaped = 0x9068,
freeing = 0x7f3d,
freed = 0xb98b,
_,
fn setNone(m: *Modify) void {
_ = @atomicRmw(Modify, m, .Xchg, .storedXor(.none, m), .monotonic);
}
fn opName(m: Modify) []const u8 {
return switch (m) {
.resized => "resize",
.remaped => "remap",
.freeing => "free",
_, .none, .freed => unreachable,
};
}
fn stateName(m: Modify) []const u8 {
return switch (m) {
.resized => "after resize",
.remaped => "after remap",
.freeing => "during free",
.freed => "after free",
_, .none => unreachable,
};
}
fn storedXor(m: Modify, ptr: *Modify) Modify {
const addr_hash: u16 = @truncate(std.hash.int(@intFromPtr(ptr)));
return @fromBackingInt(@intCast(@backingInt(m) ^ addr_hash));
}
};
fn isExtended(f: *AllocFooter) bool {
return @backingInt(f.data.len) >= Data.Len.extended_start;
}
fn extended(f: *AllocFooter) *Extended {
assert(f.isExtended());
return @ptrFromInt(@intFromPtr(f) + @sizeOf(AllocFooter));
}
fn userMemory(f: *AllocFooter) []u8 {
const memory_addr = @intFromPtr(f) - allocOffset(f.userLen());
assert(f.userAlign().check(memory_addr));
const memory_ptr: [*]u8 = @ptrFromInt(memory_addr);
return memory_ptr[0..f.userLen()];
}
fn userLen(f: *AllocFooter) usize {
const len_int = @backingInt(f.data.len);
return if (len_int < Data.Len.extended_start) len_int else f.extended().len;
}
fn userAlign(f: *AllocFooter) Alignment {
const high = (@backingInt(f.data.len) -| Data.Len.extended_start) << 2;
return @fromBackingInt(@intCast(high | f.data.alignment));
}
fn bucketPrev(f: *AllocFooter, b: *Bucket, s: *SafeAllocator) ?*AllocFooter {
if (f.isExtended()) return f.extended().container.bucket_prev;
return b.allocFooterBefore(s, Bucket.fillAt(s, f.userMemory().ptr), f.data.prev_extended);
}
fn tracesPtr(f: *AllocFooter) [*]usize {
const off_footer = @divExact(@sizeOf(AllocFooter), @sizeOf(usize));
const off_extended = @as(usize, @divExact(@sizeOf(Extended), @sizeOf(usize))) *
@intFromBool(f.isExtended());
return @as([*]usize, @ptrCast(f))[off_footer + off_extended ..];
}
fn allocTrace(f: *AllocFooter, s: *SafeAllocator) []usize {
return f.tracesPtr()[0..s.stack_trace_size];
}
fn freeTrace(f: *AllocFooter, s: *SafeAllocator) []usize {
const trace_size = s.stack_trace_size;
return f.tracesPtr()[trace_size..][0..trace_size];
}
fn actualChecksum(f: *AllocFooter, s: *SafeAllocator) u32 {
if (f.isExtended()) {
const len = f.extended().len;
const addr: usize = if (s.isLarge(len, f.userAlign()))
@intFromPtr(f.extended().container.large_entry)
else
@intFromPtr(f.extended().container.bucket_prev);
const len_bytes: [@sizeOf(usize)]u8 = @bitCast(len);
const container: [@sizeOf(usize)]u8 = @bitCast(addr);
const regular_bytes: [2]u8 = @bitCast(f.data);
const data_bytes = len_bytes ++ container ++ regular_bytes;
return @truncate(std.hash.Wyhash.hash(@truncate(@intFromPtr(f)), &data_bytes));
}
return @truncate(std.hash.int(@as(u16, @bitCast(f.data)) ^ @intFromPtr(f)));
}
fn allocOffset(len: usize) usize {
return Alignment.of(AllocFooter).forward(len);
}
fn allocAlign(a: Alignment) Alignment {
return a.max(.of(AllocFooter));
}
/// 假定尾部位于桶分配中;所有
/// 大块分配都需要扩展头部。
fn requiresExtended(len: usize, alignment: Alignment) bool {
return len >= Data.Len.extended_start or @backingInt(alignment) > math.maxInt(u2);
}
fn lenBucket(s: *SafeAllocator, is_extended: bool) usize {
return Alignment.forward(.@"8", @sizeOf(AllocFooter) +
@as(usize, @sizeOf(Extended)) * @intFromBool(is_extended) +
s.stack_trace_size * @sizeOf(usize) * 2);
}
fn lenLarge(s: *SafeAllocator) usize {
return @sizeOf(AllocFooter) + @sizeOf(Extended) + s.stack_trace_size * @sizeOf(usize);
}
fn allocLenBucket(s: *SafeAllocator, len: usize, is_extended: bool) usize {
return allocOffset(len) + lenBucket(s, is_extended);
}
fn allocLenLarge(s: *SafeAllocator, len: usize) usize {
return allocOffset(len) + lenLarge(s);
}
fn allocOffsetOrOom(len: usize) error{OutOfMemory}!usize {
return alignForwardOrOom(.of(AllocFooter), len);
}
fn allocLenBucketOrOom(
s: *SafeAllocator,
len: usize,
is_extended: bool,
) error{OutOfMemory}!usize {
return addOrOom(try allocOffsetOrOom(len), lenBucket(s, is_extended));
}
fn of(user_memory: []u8) *AllocFooter {
// 若 `memory.ptr` 未正确对齐,此时先不要触发 panic,因为稍后
// 会通过不匹配或无效的尾部信息给出更有用的 panic。
const aligned_start = Alignment.backward(.of(AllocFooter), @intFromPtr(user_memory.ptr));
return @ptrFromInt(aligned_start + allocOffset(user_memory.len));
}
fn startModify(f: *AllocFooter, m: Modify, s: *SafeAllocator, mem_fmt: FormatMemory) void {
const prev = @atomicRmw(
Modify,
&f.modify,
.Xchg,
.storedXor(m, &f.modify),
.monotonic,
).storedXor(&f.modify);
if (prev != .none) {
@branchHint(.cold);
const op_name = m.opName();
switch (prev) {
.none => unreachable,
.resized, .remaped => panic(
\\{s} {s} of {f}
\\alloc: {f}
\\{s}:
// (panic 栈跟踪)
, .{
op_name,
prev.stateName(),
mem_fmt,
// 栈回溯可能已被覆盖,但至少尝试一下。
formatStackTrace(f.allocTrace(s)),
op_name,
}),
.freeing, .freed => {
if (prev == .freeing) {
// 等待跟踪信息可用
const complete: Modify = .storedXor(.freed, &f.modify);
while (@atomicLoad(Modify, &f.modify, .monotonic) != complete) {}
const b: *Bucket = .of(s, @ptrCast(f));
b.alloc_count.fenceAcqRel();
}
if (m == .freeing) {
panic(
\\double free of {f}
\\alloc: {f}
\\first free: {f}
\\second free:
// (panic 栈跟踪)
, .{
mem_fmt,
formatStackTrace(f.allocTrace(s)),
formatStackTrace(f.freeTrace(s)),
});
} else {
panic(
\\{s} {s} of {f}
\\alloc: {f}
\\free: {f}
\\{s}:
// (panic 栈跟踪)
, .{
op_name,
prev.stateName(),
mem_fmt,
formatStackTrace(f.allocTrace(s)),
formatStackTrace(f.freeTrace(s)),
op_name,
});
}
},
_ => panic(
"{s} of invalid memory {f} or corrupted metadata",
.{ m.opName(), mem_fmt },
),
}
comptime unreachable;
}
const expected_checksum = f.actualChecksum(s);
if (f.checksum ^ s.canary != expected_checksum) {
@branchHint(.cold);
const other_canary = f.checksum ^ expected_checksum;
panic(
"{s} of invalid memory {f}, corrupted metadata, or foreign allocation from canary 0x{x}",
.{ m.opName(), mem_fmt, other_canary },
);
}
if (f.userLen() != mem_fmt.memory.len or f.userAlign() != mem_fmt.alignment) {
const op_name = m.opName();
panic(
\\{s} of {f} mismatches allocation of {f}
\\alloc: {f}
\\{s}:
// (panic 栈跟踪)
, .{ op_name, mem_fmt, FormatMemory{
.memory = f.userMemory(),
.alignment = f.userAlign(),
}, formatStackTrace(f.allocTrace(s)), op_name });
}
}
/// 调用方负责对相应的 `Bucket.alloc_count` 执行 `.acquire` 栅栏。
fn populate(
memory: []align(@alignOf(AllocFooter)) u8,
len: usize,
alignment: Alignment,
ra: usize,
/// 大型分配时为 `true`
is_extended: bool,
/// 大块分配时为 `false`
prev_extended: bool,
container: Extended.Container,
s: *SafeAllocator,
) *AllocFooter {
const footer: *AllocFooter = @ptrCast(@alignCast(memory[allocOffset(len)..].ptr));
if (!is_extended) {
footer.data = .{
.len = @fromBackingInt(@intCast(len)),
.alignment = @intCast(@backingInt(alignment)),
.prev_extended = prev_extended,
};
assert(!footer.isExtended());
} else {
footer.data = .{
.len = @fromBackingInt(@intCast(Data.Len.extended_start + (@backingInt(alignment) >> 2))),
.alignment = @truncate(@backingInt(alignment)),
.prev_extended = prev_extended,
};
assert(footer.isExtended());
footer.extended().* = .{
.len = len,
.container = container,
};
}
captureStackTrace(footer.allocTrace(s), ra);
footer.checksum = footer.actualChecksum(s) ^ s.canary;
footer.modify.setNone();
return footer;
}
};
pub fn init(
/// 此项必须线程安全,分配器才可能线程安全。
backing: mem.Allocator,
options: Options,
) SafeAllocator {
assert(options.block_size_log2 >= 8);
assert(options.bucket_size_log2 >= 8);
const allocs_entry_count = (@as(usize, 1) << options.block_size_log2) / @sizeOf(usize);
return .{
.backing = backing,
.threads = @splat(.{
.mutex = .unlocked,
.fill_bucket = null,
.free_entry = null,
.allocs_next = allocs_entry_count,
.allocs_first = null,
}),
.bucket_size_log2 = options.bucket_size_log2,
.block_size_log2 = options.block_size_log2,
.stack_trace_size = options.stack_trace_frames +
@intFromBool(options.stack_trace_frames != 0),
.allocs_entry_count = allocs_entry_count,
.large_alloc_threshold = (@as(usize, 1) << options.bucket_size_log2) * 3 / 4,
.canary = options.canary,
.check_write_after_free = options.check_write_after_free,
};
}
/// 返回泄漏数量
pub fn deinit(s: *SafeAllocator) usize {
return s.deinitLog(true);
}
/// 与 `deinit` 相同,但若 `log` 为 `false`,则不会记录内存泄漏。
pub fn deinitLog(s: *SafeAllocator, log: bool) usize {
var leaks: usize = 0;
const thread_count = @atomicRmw(usize, &n_threads, .Or, 0, .monotonic);
for (s.threads[0..@max(1, thread_count)]) |*t| {
assert(t.mutex == .unlocked); // 在 `deinit` 期间使用分配器
var maybe_allocs = t.allocs_first;
var n_entries = t.allocs_next;
while (maybe_allocs) |allocs| {
for (allocs.entries(s)[0..n_entries]) |*ent| {
switch (ent.kind) {
.free => {
@branchHint(.likely);
},
.bucket => leaks += s.deinitLeakedBucket(ent.toBucket(), log),
.large_alloc => {
leaks += 1;
s.deinitLargeAlloc(ent.toLargeAlloc(), log);
},
}
}
maybe_allocs = allocs.next;
n_entries = s.allocs_entry_count;
s.backing.rawFree(@ptrCast(allocs.usizes(s)), .of(usize), 0);
}
}
return leaks;
}
/// 返回实际的泄漏数量
fn deinitLeakedBucket(s: *SafeAllocator, b: *Bucket, log: bool) usize {
var leaks: usize = 0;
const expected = @atomicLoad(Bucket.AllocCount, &b.alloc_count, .acquire);
if (expected.n == 0) assert(expected.filling);
var footer = b.lastAlloc(s, b.fill).?;
while (true) {
const modify = @atomicRmw(
AllocFooter.Modify,
&footer.modify,
.Xchg,
undefined,
.monotonic,
).storedXor(&footer.modify);
const bad_modify = modify != .none and modify != .freed;
if (bad_modify or footer.actualChecksum(s) != footer.checksum ^ s.canary) {
panic("corrupted footer metadata in bucket at *{x}", .{@intFromPtr(&footer)});
}
switch (modify) {
.none => {
leaks += 1;
if (log) scoped_log.err("leaked {f} allocated at: {f}", .{ FormatMemory{
.memory = footer.userMemory(),
.alignment = footer.userAlign(),
}, formatStackTrace(footer.allocTrace(s)) });
},
.freed => s.checkFreed(footer),
else => unreachable,
}
footer = footer.bucketPrev(b, s) orelse break;
}
s.backing.rawFree(b.bytes(s), @fromBackingInt(@intCast(s.bucket_size_log2)), 0);
assert(leaks == expected.n);
return leaks;
}
fn deinitLargeAlloc(s: *SafeAllocator, footer: *AllocFooter, log: bool) void {
const modify = footer.modify.storedXor(&footer.modify);
if (modify != .none or footer.checksum ^ s.canary != footer.actualChecksum(s)) {
panic("corrupted footer metadata at *{x}", .{@intFromPtr(&footer)});
}
const memory = footer.userMemory();
if (log) scoped_log.err("leaked {f} allocated at {f}", .{ FormatMemory{
.memory = memory,
.alignment = footer.userAlign(),
}, formatStackTrace(footer.allocTrace(s)) });
s.backing.rawFree(
memory.ptr[0..AllocFooter.allocLenLarge(s, memory.len)],
AllocFooter.allocAlign(footer.userAlign()),
0,
);
}
/// 返回的分配器是线程安全的
pub fn allocator(s: *SafeAllocator) mem.Allocator {
return .{ .ptr = s, .vtable = &vtable };
}
fn acquireThread(s: *SafeAllocator) *Thread {
while (true) {
const t = &s.threads[thread_index];
if (t.mutex.tryLock()) {
@branchHint(.likely);
return t;
}
var max = @atomicLoad(usize, &n_threads, .unordered);
if (max == 0) {
@branchHint(.unlikely);
max = @min(std.Thread.getCpuCount() catch s.threads.len, s.threads.len);
max = @cmpxchgStrong(usize, &n_threads, 0, max, .monotonic, .monotonic) orelse max;
}
thread_index += 1;
// 如果 getCpuCount 返回零,thread_index 可能大于 max。
thread_index *= @intFromBool(thread_index < max);
}
}
fn alignForwardOrOom(a: Alignment, addr: usize) error{OutOfMemory}!usize {
const x = a.toByteUnits() - 1;
return try addOrOom(addr, x) & ~x;
}
fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize {
return math.add(usize, a, b) catch error.OutOfMemory;
}
fn isLarge(s: *SafeAllocator, len: usize, alignment: Alignment) bool {
const max_align_waste = alignment.toByteUnits() - 1;
const max_use = max_align_waste + AllocFooter.allocLenBucket(s, len, true);
return max_use >= s.large_alloc_threshold;
}
fn isLargeOrOom(s: *SafeAllocator, len: usize, alignment: Alignment) error{OutOfMemory}!bool {
const max_align_waste = alignment.toByteUnits() - 1;
const max_use = try addOrOom(max_align_waste, try AllocFooter.allocLenBucketOrOom(s, len, true));
return max_use >= s.large_alloc_threshold;
}
fn newAllocEntry(s: *SafeAllocator, t: *Thread, ra: usize) error{OutOfMemory}!*Allocs.Entry {
if (t.free_entry) |ent| {
@branchHint(.likely);
t.free_entry = ent.toFree();
return ent;
}
if (s.allocs_entry_count - t.allocs_next != 0) {
@branchHint(.likely);
const ent = &t.allocs_first.?.entries(s)[t.allocs_next];
t.allocs_next += 1;
return ent;
}
const new_segment: *Allocs = @ptrCast(@alignCast(s.backing.rawAlloc(
(1 + s.allocs_entry_count) * @sizeOf(usize),
.of(usize),
ra,
) orelse return error.OutOfMemory));
new_segment.next = t.allocs_first;
t.allocs_first = new_segment;
t.allocs_next = 1;
return &new_segment.entries(s)[0];
}
fn freeAllocEntry(t: *Thread, ent: *Allocs.Entry) void {
ent.* = .fromFree(t.free_entry);
t.free_entry = ent;
}
fn overwriteFreed(s: *SafeAllocator, bytes: []u8) void {
if (!s.check_write_after_free) return;
// 使用 0x55,使写入未定义值 0xaa 的行为仍能被检测到。
// 另一种方式是使用以地址作为种子的随机字节流,但这会使调试释放后读取更困难,且产生性能损失,因此不值得仅为额外捕获少量释放后写入而这样做。
//
//
@memset(bytes, 0x55);
}
/// 返回首次释放后写入的地址
fn checkFreed(s: *SafeAllocator, footer: *AllocFooter) void {
if (!s.check_write_after_free) return;
const memory = footer.userMemory();
for (memory) |*b| if (b.* != 0x55) {
panic(
\\write after free at *{x}
\\original alloc of {f}: {f}
\\free: {f}
\\stack trace:
// (panic 栈跟踪)
, .{
@intFromPtr(b),
FormatMemory{ .memory = memory, .alignment = footer.userAlign() },
formatStackTrace(footer.allocTrace(s)),
formatStackTrace(footer.freeTrace(s)),
});
};
}
const FormatMemory = struct {
memory: []const u8,
alignment: Alignment,
pub fn format(m: FormatMemory, w: *std.Io.Writer) std.Io.Writer.Error!void {
return w.print(
"[addr: {x}, len: {} (0x{x}) align: {}]",
.{ @intFromPtr(m.memory.ptr), m.memory.len, m.memory.len, m.alignment.toByteUnits() },
);
}
};
/// 首个元素存储包括已跳过栈帧在内的栈轨迹长度。
/// 其余元素存储返回地址。
fn captureStackTrace(trace_buf: []usize, ra: usize) void {
if (trace_buf.len == 0) return;
if (ra == 0) { // 未提供返回地址
@branchHint(.unlikely);
trace_buf[0] = 0;
return;
}
const t = std.debug.captureCurrentStackTrace(.{ .first_address = ra }, trace_buf[1..]);
const skipped = @backingInt(t.skipped) *
@intFromBool(t.return_addresses.len == trace_buf[1..].len);
trace_buf[0] = t.return_addresses.len +| skipped;
}
fn formatStackTrace(trace_buf: []usize) std.debug.FormatStackTrace {
return .{
.stack_trace = if (trace_buf.len != 0) trace: {
const frames = trace_buf[0];
const addrs = trace_buf[1..];
break :trace .{
.return_addresses = addrs[0..@min(frames, addrs.len)],
.skipped = switch (frames) {
else => @fromBackingInt(@intCast(frames -| addrs.len)),
0, math.maxInt(usize) => .unknown,
},
};
} else .{
.return_addresses = &.{},
.skipped = .unknown,
},
.terminal_mode = std.log.terminalMode(),
};
}
/// 若此操作失败,后续向该桶分配内存均不合法
fn allocBucket(
s: *SafeAllocator,
t: *Thread,
b: *Bucket,
len: usize,
alignment: Alignment,
ra: usize,
) ?[*]u8 {
const fill = &b.fill;
const is_extended = AllocFooter.requiresExtended(len, alignment);
const alloc_len: u32 = @intCast(AllocFooter.allocLenBucket(s, len, is_extended));
const alloc_align = AllocFooter.allocAlign(alignment);
var prev_fill = @atomicLoad(Bucket.Fill, fill, .monotonic);
var start: u32 = undefined;
var end: u32 = undefined;
while (true) {
start = @intCast(alloc_align.forward(prev_fill.at));
end = start + alloc_len;
if (end > s.bucketSize()) {
@branchHint(.unlikely);
const prev_count = @atomicRmw(
Bucket.AllocCount,
&b.alloc_count,
.Sub,
.{ .filling = true, .n = 0 },
.acq_rel,
);
assert(prev_count.filling);
if (prev_count.n == 0) {
@branchHint(.unlikely);
freeAllocEntry(t, b.entry);
b.check(s);
s.backing.rawFree(b.bytes(s), @fromBackingInt(@intCast(s.bucket_size_log2)), ra);
}
return null;
}
prev_fill = @cmpxchgWeak(
Bucket.Fill,
fill,
prev_fill,
.{ .at = @intCast(end), .last_is_extended = is_extended },
.monotonic,
.monotonic,
) orelse {
@branchHint(.likely);
break;
};
// b.fill 在调整大小期间发生变化(或 cmpxchgWeak 偶发失败)
}
const memory = b.bytes(s)[start..end];
_ = AllocFooter.populate(
@alignCast(memory),
len,
alignment,
ra,
is_extended,
prev_fill.last_is_extended,
.{ .bucket_prev = b.lastAlloc(s, prev_fill) },
s,
);
assert(@atomicRmw(
Bucket.AllocCount,
&b.alloc_count,
.Add,
.{ .filling = false, .n = 1 },
.acq_rel,
).filling);
return memory.ptr;
}
fn growingResizeBucket(
s: *SafeAllocator,
f: *AllocFooter,
memory: []const u8,
alignment: Alignment,
new_len: usize,
ra: usize,
) bool {
assert(new_len >= memory.len);
return s.advanceBucketAlloc(f, Bucket.fillAt(s, memory.ptr), false, alignment, new_len, ra);
}
fn advanceBucketAlloc(
s: *SafeAllocator,
old: *AllocFooter,
new_start: u32,
start_moved: bool,
alignment: Alignment,
new_len: usize,
ra: usize,
) bool {
assert(AllocFooter.allocAlign(alignment).check(new_start));
const b: *Bucket = .of(s, @ptrCast(old));
const old_is_extended = old.isExtended();
const old_footer_len = AllocFooter.lenBucket(s, old_is_extended);
const old_fill: u32 = @intCast(Bucket.fillAt(s, @ptrCast(old)) + old_footer_len);
const new_is_extended = old_is_extended or start_moved or
AllocFooter.requiresExtended(new_len, alignment);
const new_footer_len = AllocFooter.lenBucket(s, new_is_extended);
const new_fill: u32 = @intCast(new_start + AllocFooter.allocOffset(new_len) + new_footer_len);
assert(old_fill <= new_fill);
if (new_fill > s.bucketSize()) {
return false;
}
if (old_fill == new_fill or @cmpxchgStrong(
Bucket.Fill,
&b.fill,
.{ .last_is_extended = old_is_extended, .at = @intCast(old_fill) },
.{ .last_is_extended = new_is_extended, .at = @intCast(new_fill) },
.monotonic,
.monotonic,
) != null) {
return false;
}
_ = AllocFooter.populate(
@alignCast(b.bytes(s)[new_start..new_fill]),
new_len,
alignment,
ra,
new_is_extended,
old.data.prev_extended,
.{ .bucket_prev = old.bucketPrev(b, s) },
s,
);
b.alloc_count.fenceAcqRel();
return true;
}
const vtable: mem.Allocator.VTable = .{
.alloc = alloc,
.free = free,
.resize = resize,
.remap = remap,
};
fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, ra: usize) ?[*]u8 {
assert(len != 0);
const s: *SafeAllocator = @ptrCast(@alignCast(ctx));
const t = s.acquireThread();
defer t.mutex.unlock();
if (s.isLargeOrOom(len, alignment) catch return null) {
@branchHint(.unlikely);
const entry = s.newAllocEntry(t, ra) catch return null;
const alloc_len = AllocFooter.allocLenLarge(s, len);
const alloc_align = AllocFooter.allocAlign(alignment);
const alloc_ptr = s.backing.rawAlloc(alloc_len, alloc_align, ra) orelse {
freeAllocEntry(t, entry);
return null;
};
const footer = AllocFooter.populate(
@alignCast(alloc_ptr[0..alloc_len]),
len,
alignment,
ra,
true,
false,
.{ .large_entry = entry },
s,
);
entry.* = .fromLargeAlloc(footer);
return alloc_ptr;
}
if (t.fill_bucket) |bucket| {
@branchHint(.likely);
if (s.allocBucket(t, bucket, len, alignment, ra)) |ptr| {
@branchHint(.likely);
return ptr;
}
}
t.fill_bucket = null; // 若下面发生内存不足,此桶仍无法用于后续
// 分配。
const entry = s.newAllocEntry(t, ra) catch return null;
const bucket: *Bucket = @ptrCast(@alignCast(s.backing.rawAlloc(
s.bucketSize(),
@fromBackingInt(@intCast(s.bucket_size_log2)),
ra,
) orelse {
freeAllocEntry(t, entry);
return null;
}));
bucket.* = .{
.entry = entry,
// 无需原子存储,因为此线程会在下面的 allocBucket 中
// 首先以原子方式更新这些值。
.alloc_count = .{ .filling = true, .n = 0 },
.fill = .{ .at = @sizeOf(Bucket), .last_is_extended = false },
};
entry.* = .fromBucket(bucket);
t.fill_bucket = bucket;
return s.allocBucket(t, bucket, len, alignment, ra);
}
fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, ra: usize) void {
const s: *SafeAllocator = @ptrCast(@alignCast(ctx));
const f: *AllocFooter = .of(memory);
f.startModify(.freeing, s, .{ .memory = memory, .alignment = alignment });
if (s.isLarge(memory.len, alignment)) {
@branchHint(.unlikely);
const t = s.acquireThread();
freeAllocEntry(t, f.extended().container.large_entry);
t.mutex.unlock();
s.backing.rawFree(
memory.ptr[0..AllocFooter.allocLenLarge(s, memory.len)],
AllocFooter.allocAlign(alignment),
ra,
);
return;
}
const b: *Bucket = .of(s, memory.ptr);
s.overwriteFreed(memory);
captureStackTrace(f.freeTrace(s), ra);
// 在将 `f.modify` 设为 `.freed` 之前,为分配计数建立内存屏障。
// 这样,如果另一线程正在等待跟踪信息
// 可用,它就不会与当前线程竞相观察此 `.release`。
//
// 下方的分配计数更新不能移到此处替代屏障,
// 否则另一线程就可能观察到 `.freeing` 状态。
b.alloc_count.fenceAcqRel();
// 若结果不同于 .freeing,则说明其他线程
// 正在触发 panic。因此直接忽略。
// (其他几个位置也采用此理由。)
_ = @atomicRmw(
AllocFooter.Modify,
&f.modify,
.Xchg,
.storedXor(.freed, &f.modify),
.monotonic,
);
const prev_count = @atomicRmw(
Bucket.AllocCount,
&b.alloc_count,
.Sub,
.{ .filling = false, .n = 1 },
.acq_rel,
);
if (prev_count.n - 1 == 0 and !prev_count.filling) {
@branchHint(.unlikely);
const t = s.acquireThread();
freeAllocEntry(t, b.entry);
t.mutex.unlock();
b.check(s);
s.backing.rawFree(b.bytes(s), @fromBackingInt(@intCast(s.bucket_size_log2)), ra);
}
}
fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) bool {
assert(new_len != 0);
const s: *SafeAllocator = @ptrCast(@alignCast(ctx));
const f: *AllocFooter = .of(memory);
f.startModify(.resized, s, .{ .memory = memory, .alignment = alignment });
// 检查分配没有在桶分配与大块分配之间移动。
// 在前述操作之后检查,以确保仍检查传入内存有效,
// 且不存在重复修改。
const from_large_alloc = s.isLarge(memory.len, alignment);
const to_large_alloc = s.isLargeOrOom(new_len, alignment) catch {
f.modify.setNone();
return false;
};
if (from_large_alloc != to_large_alloc) {
@branchHint(.unlikely);
f.modify.setNone();
return false;
}
if (from_large_alloc) {
@branchHint(.unlikely);
const entry = f.extended().container.large_entry;
const new_alloc_len = AllocFooter.allocLenLarge(s, new_len);
if (!s.backing.rawResize(
memory.ptr[0..AllocFooter.allocLenLarge(s, memory.len)],
AllocFooter.allocAlign(alignment),
new_alloc_len,
ra,
)) {
f.modify.setNone();
return false;
}
const new_footer = AllocFooter.populate(
@alignCast(memory.ptr[0..new_alloc_len]),
new_len,
alignment,
ra,
true,
false,
.{ .large_entry = entry },
s,
);
assert(entry.kind == .large_alloc);
entry.* = .fromLargeAlloc(new_footer);
return true;
}
if (new_len < memory.len) {
// 任何情况下均不允许通过 resize 缩小分配,因为这会破坏链表。
// 即使此页脚是最后一个,也必须减小 fill 值,
// 而这会允许内存被重用。
f.modify.setNone();
return false;
}
if (s.growingResizeBucket(f, memory, alignment, new_len, ra)) {
@branchHint(.likely);
return true;
} else {
f.modify.setNone();
return false;
}
}
fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ra: usize) ?[*]u8 {
assert(new_len != 0);
const s: *SafeAllocator = @ptrCast(@alignCast(ctx));
const f: *AllocFooter = .of(memory);
f.startModify(.remaped, s, .{ .memory = memory, .alignment = alignment });
// 检查分配没有在桶分配与大块分配之间移动。
// 在前述操作之后检查,以确保仍检查传入内存有效,
// 且不存在重复修改。
const from_large_alloc = s.isLarge(memory.len, alignment);
const to_large_alloc = s.isLargeOrOom(new_len, alignment) catch {
f.modify.setNone();
return null;
};
if (from_large_alloc != to_large_alloc) {
@branchHint(.unlikely);
f.modify.setNone();
return null;
}
if (from_large_alloc) {
@branchHint(.unlikely);
const entry = f.extended().container.large_entry;
const new_alloc_len = AllocFooter.allocLenLarge(s, new_len);
const new_memory = s.backing.rawRemap(
memory.ptr[0..AllocFooter.allocLenLarge(s, memory.len)],
AllocFooter.allocAlign(alignment),
new_alloc_len,
ra,
) orelse {
f.modify.setNone();
return null;
};
const new_footer = AllocFooter.populate(
@alignCast(new_memory[0..new_alloc_len]),
new_len,
alignment,
ra,
true,
false,
.{ .large_entry = entry },
s,
);
assert(entry.kind == .large_alloc);
entry.* = .fromLargeAlloc(new_footer);
return new_memory;
}
if (new_len < memory.len) {
// 将分配位置前移,以避免复用桶。
const fixed_start = Bucket.fillAt(s, @ptrCast(f)) - AllocFooter.allocOffset(new_len);
const moved_start = alignment.forward(fixed_start);
if (moved_start != fixed_start or !f.isExtended()) {
@branchHint(.unlikely);
// 对于 `moved_start != fixed_start`:尾部也需要向前移动,
// 以维持正确的 allocOffset。
//
// 对于 `!f.isExtended()`:因为此内存不再紧随
// 前一个尾部之后,需要将尾部升级为扩展尾部,
// 以编码前一个尾部的位置。
if (!s.advanceBucketAlloc(f, @intCast(moved_start), true, alignment, new_len, ra)) {
@branchHint(.unlikely);
f.modify.setNone();
return null;
}
const new_memory = Bucket.bytes(.of(s, @ptrCast(f)), s)[moved_start..][0..new_len];
@memmove(new_memory, memory[0..new_memory.len]);
return new_memory.ptr;
}
// 尾部可原地修改
const b: *Bucket = .of(s, @ptrCast(f));
f.extended().len = new_len;
f.checksum = f.actualChecksum(s) ^ s.canary;
captureStackTrace(f.allocTrace(s), ra);
f.modify.setNone();
b.alloc_count.fenceAcqRel();
const new_memory = f.userMemory();
@memmove(new_memory, memory[0..new_memory.len]);
return new_memory.ptr;
}
if (s.growingResizeBucket(f, memory, alignment, new_len, ra)) {
@branchHint(.likely);
return memory.ptr;
} else {
f.modify.setNone();
return null;
}
}
const Smith = std.testing.Smith;
/// 由单线程和多线程模糊测试共享。
const fuzz_probs = struct {
const alignment: []const Smith.Weight = &.{
.rangeAtMost(Alignment, .@"1", .@"16", 32), // ~75%
.rangeAtMost(Alignment, .@"16", @fromBackingInt(@intCast(@bitSizeOf(usize) - 1)), 1),
.value(Alignment, @fromBackingInt(@intCast(@bitSizeOf(usize) - 1)), 32), // 更可能发生溢出的情况
};
const eos: []const Smith.Weight = &.{
// 极高的 false 权重,使分配表扩展、内存不足情况及多线程生产者/消费者情况得到充分测试。
//
.value(bool, false, 255),
.value(bool, true, 1),
};
fn generateOptions(smith: *Smith) Options {
@disableInstrumentation();
const size_log2_weights: []const Smith.Weight = &.{
.value(u5, 8, 1024), // 概率是下方情况的 8 倍
.rangeAtMost(u5, 8, 16, 16),
.rangeAtMost(u5, 17, 31, 1), // 概率为上面的 1/32,因为使用固定缓冲区时这些情况只会内存不足
};
return .{
.stack_trace_frames = smith.valueWeighted(u16, &.{
.value(u16, 0, 1 << 18), // 4x——除 I.B. 外,栈跟踪没有经过测试的性质。
.rangeAtMost(u16, 0, math.maxInt(u16), 1),
}),
// 若设置此项,则力求显著减少分配的字节数,因为释放会变为 O(n)。
// 不设置时为 O(1),因为会绕过 mem.Allocator,
// 从而无需对数据执行 memset。
.check_write_after_free = smith.valueWeighted(bool, &.{
.value(bool, false, 31),
.value(bool, false, 1),
}),
.canary = smith.value(u32),
.block_size_log2 = smith.valueWeighted(u5, size_log2_weights),
.bucket_size_log2 = smith.valueWeighted(u5, size_log2_weights),
};
}
const Op = enum(u8) { alloc, free, resize, remap };
fn generateOp(smith: *Smith, any_allocs: bool) Op {
@disableInstrumentation();
return if (any_allocs) smith.valueWeighted(Op, &.{
.rangeAtMost(Op, .alloc, .free, 4),
.rangeAtMost(Op, .resize, .remap, 1),
}) else .alloc;
}
fn generateSplat(smith: *Smith) ?u8 {
@disableInstrumentation();
// `check_write_after_free` 的理由相同
const n = smith.valueWeighted(u16, &.{
.value(u16, 256, 256 * 31),
.rangeAtMost(u16, 0, 255, 1),
});
return if (n == 256) null else @intCast(n);
}
fn generateLen(smith: *Smith, will_memset: bool) usize {
@disableInstrumentation();
// 1 << 24 表示生成不加权的 usize。
// 1 << 25 表示提供相对于 usize 最大值的数值。
const len = smith.valueWeightedWithHash(
u32,
if (!will_memset) comptime &.{
// zig fmt: off
.rangeLessThan(u32, 1 , 1 << 6 , 1 << 15), // 下方使用 2^21 - 2^4,因此几率高出 16 倍
.rangeLessThan(u32, 1 << 6, 1 << 17, 1 ), // 比下方多 2^17 - 2^4 次,因此概率为 16 倍
.value (u32, 1 << 24, 1 << 12), // 2^12
.value (u32, 1 << 25, 1 << 12), // 2^12
// zig fmt: on
} else comptime &.{
// zig fmt: off
.rangeLessThan(u32, 1 , 1 << 6, 1 << 17), // 下方有 2^23 - 2^6 次,因此概率为 64 倍
.rangeLessThan(u32, 1 << 6, 1 << 17, 1 ), // 下方使用 2^17 - 2^6,因此几率高出 64 倍
.value (u32, 1 << 24, 1 << 10), // 2^10
.value (u32, 1 << 25, 1 << 10), // 2^10
// zig fmt: on
},
// 使用不同权重时,为模糊测试器提供不同的哈希,
// 防止它重复使用其他概率配置的值。
if (!will_memset) 0x38a74424 else 0xec581ff0,
);
if (len == 1 << 24) return @max(1, smith.value(usize));
if (len == 1 << 25) return @as(usize, math.maxInt(usize)) - smith.value(u16);
return len;
}
fn checkSplat(splat: ?u8, bytes: []const u8) void {
@disableInstrumentation();
const byte = splat orelse return;
for (bytes) |*b| if (b.* != byte) {
panic("SafeAllocator corrupted allocation data at *{x}", .{@intFromPtr(b)});
};
}
};
test "fuzz single threaded" {
// 此单线程模糊测试具有以下优势:
// * 吞吐量更高且行为确定,有利于模糊测试器。
// * 更易调试可重现的单线程错误。
const testing_buf = try std.testing.allocator.alloc(u8, 65536);
defer std.testing.allocator.free(testing_buf);
const backing_buf = try std.testing.allocator.alloc(u8, 1 << 17);
defer std.testing.allocator.free(backing_buf);
try std.testing.fuzz(FuzzSingleThreadedContext{
.testing_buf = testing_buf,
.backing_buf = backing_buf,
}, fuzzSingleThreaded, .{});
}
const FuzzSingleThreadedContext = struct {
testing_buf: []u8,
backing_buf: []u8,
};
/// 保证内存不会被重用。
const FuzzSingleThreadedAllocator = struct {
gpa: mem.Allocator,
smith: *std.testing.Smith,
buf: []u8,
fill: usize,
allocs: std.MultiArrayList(AllocInfo),
const AllocInfo = struct {
ptr: [*]u8,
len: usize,
alignment: Alignment,
};
fn allocator(f: *FuzzSingleThreadedAllocator) mem.Allocator {
@disableInstrumentation();
return .{ .ptr = f, .vtable = &.{
.alloc = FuzzSingleThreadedAllocator.alloc,
.free = FuzzSingleThreadedAllocator.free,
.resize = FuzzSingleThreadedAllocator.resize,
.remap = FuzzSingleThreadedAllocator.remap,
} };
}
fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, _: usize) ?[*]u8 {
@disableInstrumentation();
const f: *FuzzSingleThreadedAllocator = @ptrCast(@alignCast(ctx));
f.allocs.ensureUnusedCapacity(f.gpa, 1) catch return null;
const ptr = f.allocInner(len, alignment) orelse return null;
f.allocs.appendAssumeCapacity(.{
.ptr = ptr,
.len = len,
.alignment = alignment,
});
return ptr;
}
fn allocInner(f: *FuzzSingleThreadedAllocator, len: usize, alignment: Alignment) ?[*]u8 {
@disableInstrumentation();
const start_addr = alignment.forward(@intFromPtr(f.buf[f.fill..].ptr));
const start = @as([*]u8, @ptrFromInt(start_addr)) - f.buf.ptr;
if (start +| len > f.buf.len or f.smith.boolWeighted(31, 1)) return null;
f.fill = start + len;
return f.buf[start..][0..len].ptr;
}
fn allocIndex(f: *FuzzSingleThreadedAllocator, memory: []u8, alignment: Alignment) usize {
@disableInstrumentation();
const allocs_slice = f.allocs.slice();
const i = mem.findScalar([*]u8, allocs_slice.items(.ptr), memory.ptr) orelse panic(
"invalid SafeAllocator free of {f}",
.{FormatMemory{ .memory = memory, .alignment = alignment }},
);
const expected_len = allocs_slice.items(.len)[i];
const expected_align = allocs_slice.items(.alignment)[i];
if (memory.len != expected_len or allocs_slice.items(.alignment)[i] != expected_align) {
panic("SafeAllocator free {f} mismatches alloc {f}", .{
FormatMemory{ .memory = memory, .alignment = alignment },
FormatMemory{ .memory = memory.ptr[0..expected_len], .alignment = expected_align },
});
}
return i;
}
fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, _: usize) void {
@disableInstrumentation();
const f: *FuzzSingleThreadedAllocator = @ptrCast(@alignCast(ctx));
f.allocs.swapRemove(f.allocIndex(memory, alignment));
}
fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, _: usize) bool {
@disableInstrumentation();
const f: *FuzzSingleThreadedAllocator = @ptrCast(@alignCast(ctx));
const i = f.allocIndex(memory, alignment);
const start = memory.ptr - f.buf.ptr;
const old_end = start + memory.len;
const new_end = start +| new_len;
if (new_end > f.buf.len or f.smith.value(bool)) {
return false;
}
if (new_len <= memory.len) {
// fill 未减小,因此内存不会被复用。
} else if (f.fill == old_end) {
f.fill = new_end;
} else {
return false;
}
f.allocs.items(.len)[i] = new_len;
return true;
}
fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, _: usize) ?[*]u8 {
@disableInstrumentation();
const f: *FuzzSingleThreadedAllocator = @ptrCast(@alignCast(ctx));
if (f.smith.value(bool)) {
const resized = FuzzSingleThreadedAllocator.resize(
ctx,
memory,
alignment,
new_len,
undefined,
);
return if (resized) memory.ptr else null;
}
const i = f.allocIndex(memory, alignment);
if (f.smith.value(bool)) return null;
const new_ptr = f.allocInner(new_len, alignment) orelse return null;
const copy_len = @min(memory.len, new_len);
@memcpy(new_ptr[0..copy_len], memory[0..copy_len]);
f.allocs.set(i, .{
.ptr = new_ptr,
.len = new_len,
.alignment = alignment,
});
return new_ptr;
}
};
fn fuzzSingleThreaded(ctx: FuzzSingleThreadedContext, smith: *Smith) !void {
@disableInstrumentation();
var gpa_instance: std.heap.FixedBufferAllocator = .init(ctx.testing_buf);
const gpa = gpa_instance.allocator();
var backing_gpa_instance: FuzzSingleThreadedAllocator = .{
.gpa = gpa,
.smith = smith,
.buf = ctx.backing_buf,
.fill = 0,
.allocs = .empty,
};
const backing_gpa = backing_gpa_instance.allocator();
const options = fuzz_probs.generateOptions(smith);
var s: SafeAllocator = .init(backing_gpa, options);
const no_ra: usize = 0;
var allocs: std.MultiArrayList(struct {
memory: []u8,
alignment: Alignment,
splat: ?u8,
}) = .empty;
var used_memory: std.ArrayList(struct {
start: usize,
end: usize,
}) = .empty;
while (!smith.eosWeighted(fuzz_probs.eos)) {
const op = fuzz_probs.generateOp(smith, allocs.len != 0);
const new_mem: []const u8, const old_mem: ?[]const u8 = new_alloc: switch (op) {
.alloc => {
used_memory.ensureUnusedCapacity(gpa, 1) catch break;
allocs.ensureUnusedCapacity(gpa, 1) catch break;
const splat = fuzz_probs.generateSplat(smith);
const will_memset = options.check_write_after_free or splat != null;
const len = fuzz_probs.generateLen(smith, will_memset);
const alignment = smith.valueWeighted(Alignment, fuzz_probs.alignment);
const ptr = alloc(&s, len, alignment, no_ra) orelse continue;
if (!alignment.check(@intFromPtr(ptr))) @panic("bad returned alignment");
const memory = ptr[0..len];
if (splat) |b| @memset(memory, b);
allocs.appendAssumeCapacity(.{
.memory = memory,
.alignment = alignment,
.splat = splat,
});
break :new_alloc .{ memory, null };
},
.free => {
const i = smith.valueRangeLessThan(u32, 0, @intCast(allocs.len));
const alloc_info = allocs.get(i);
allocs.swapRemove(i);
fuzz_probs.checkSplat(alloc_info.splat, alloc_info.memory);
free(&s, alloc_info.memory, alloc_info.alignment, no_ra);
continue;
},
.resize => {
used_memory.ensureUnusedCapacity(gpa, 1) catch break;
const i = smith.valueRangeLessThan(u32, 0, @intCast(allocs.len));
const allocs_slice = allocs.slice();
const prev_alloc = allocs_slice.get(i);
const old_len = prev_alloc.memory.len;
const alloc_memory = &allocs_slice.items(.memory)[i];
const splat = prev_alloc.splat;
const will_memset = options.check_write_after_free or splat != null;
const new_len = fuzz_probs.generateLen(smith, will_memset);
if (!resize(&s, prev_alloc.memory, prev_alloc.alignment, new_len, no_ra)) {
fuzz_probs.checkSplat(prev_alloc.splat, prev_alloc.memory);
continue;
}
alloc_memory.len = new_len;
fuzz_probs.checkSplat(prev_alloc.splat, alloc_memory.*[0..@min(old_len, new_len)]);
if (splat) |b| @memset(alloc_memory.*[@min(old_len, new_len)..], b);
break :new_alloc .{ alloc_memory.*, prev_alloc.memory };
},
.remap => {
used_memory.ensureUnusedCapacity(gpa, 1) catch break;
const i = smith.valueRangeLessThan(u32, 0, @intCast(allocs.len));
const allocs_slice = allocs.slice();
const prev_alloc = allocs_slice.get(i);
const old_len = prev_alloc.memory.len;
const alloc_memory = &allocs_slice.items(.memory)[i];
const alignment = prev_alloc.alignment;
const splat = prev_alloc.splat;
const will_memset = options.check_write_after_free or splat != null;
const new_len = fuzz_probs.generateLen(smith, will_memset);
const new_ptr = remap(
&s,
prev_alloc.memory,
prev_alloc.alignment,
new_len,
no_ra,
) orelse {
fuzz_probs.checkSplat(prev_alloc.splat, prev_alloc.memory);
continue;
};
alloc_memory.* = new_ptr[0..new_len];
if (!alignment.check(@intFromPtr(new_ptr))) @panic("bad returned alignment");
fuzz_probs.checkSplat(prev_alloc.splat, alloc_memory.*[0..@min(old_len, new_len)]);
if (splat) |b| @memset(alloc_memory.*[@min(old_len, new_len)..], b);
break :new_alloc .{ alloc_memory.*, prev_alloc.memory };
},
};
const new_start = @intFromPtr(new_mem.ptr);
const new_end = new_start + new_mem.len;
const old_start = if (old_mem) |old| @intFromPtr(old.ptr) else 0;
const old_end = new_start + if (old_mem) |old| old.len else 0;
for (used_memory.items) |used| {
if (old_start <= used.end and used.start <= old_end) {
continue;
}
if (new_start <= used.end and used.start <= new_end) {
panic(
"memory reuse between [addr: {x}, len: {}] and new [addr: {x}, len: {}]",
.{ used.start, used.end, new_start, new_end },
);
}
}
used_memory.appendAssumeCapacity(.{ .start = new_start, .end = new_end });
}
try std.testing.expectEqual(allocs.len, s.deinitLog(false));
const leaks_slice = backing_gpa_instance.allocs.slice();
for (0..leaks_slice.len) |i| {
const leak = leaks_slice.get(i);
std.log.err("SafeAllocator leaked {f}", .{FormatMemory{
.memory = leak.ptr[0..leak.len],
.alignment = leak.alignment,
}});
}
try std.testing.expectEqual(0, leaks_slice.len); // 无泄漏
}
test "fuzz multi threaded" {
if (@import("builtin").single_threaded) return error.SkipZigTest;
const testing_buf = try std.testing.allocator.alloc(u8, 65536);
defer std.testing.allocator.free(testing_buf);
const backing_buf = try std.testing.allocator.alloc(u8, 1 << 17);
defer std.testing.allocator.free(backing_buf);
// `std.testing` 实例会在 `std.testing.fuzz` 期间被覆盖,因此必须使用自己的 io 和 gpa 实例。
//
var threaded_io: std.Io.Threaded = .init(std.heap.smp_allocator, .{});
defer threaded_io.deinit();
const io = threaded_io.io();
var ops: FuzzMultiThreadedContext.ThreadOps = undefined;
ops.run = .{ .n = false };
var group: std.Io.Group = .init;
defer group.cancel(io);
for (0..FuzzMultiThreadedContext.n_threads) |_| {
try group.concurrent(io, fuzzMultiThreadedWorker, .{ io, &ops });
}
try std.testing.fuzz(FuzzMultiThreadedContext{
.testing_buf = testing_buf,
.backing_buf = backing_buf,
.io = io,
.ops = &ops,
}, fuzzMultiThreaded, .{});
}
const FuzzMultiThreadedContext = struct {
testing_buf: []u8,
backing_buf: []u8,
io: std.Io,
ops: *ThreadOps,
const n_threads = 4;
const ThreadOps = struct {
/// 每次运行开始时在两个值之间切换。
run: Run,
/// 虽然可计算为 `n_threads - (i -| ops.items.len)`,
/// 但此操作也为每个线程提供 `.release` 同步。
running: u32,
instance: SafeAllocator,
i: usize,
items: []Op,
const Run = packed struct(u32) {
n: bool,
pad: u31 = 0,
fn wait(ptr: *Run, val: Run, io: std.Io) error{Canceled}!void {
assert(val.pad == 0);
while (true) {
// 不可能加载更旧的值,因为此线程此前已加载
// 最新值。
const prev = @atomicLoad(Run, ptr, .acquire);
assert(prev.pad == 0);
if (prev == val) break;
try io.futexWait(Run, ptr, prev);
}
}
fn next(r: Run) Run {
assert(r.pad == 0);
return .{ .n = !r.n };
}
};
const Op = union(fuzz_probs.Op) {
alloc: struct {
len: usize,
alignment: Alignment,
splat: ?u8,
/// 为绕过 tsan 问题,不直接嵌入结构体;
/// 因为直接对 `Op` 执行 switch 会非原子地加载整个值。
result: *MemoryDependency,
},
free: struct {
memory: *MemoryDependency,
alignment: Alignment,
splat: ?u8,
},
resize: Realloc,
remap: Realloc,
const Realloc = struct {
memory: *MemoryDependency,
alignment: Alignment,
new_len: usize,
splat: ?u8,
/// 为绕过 tsan 问题,不直接嵌入结构体;
/// 因为直接对 `Op` 执行 switch 会非原子地加载整个值。
result: *MemoryDependency,
};
const MemoryDependency = struct {
ready: std.Io.Event,
/// 内存分配失败时为 Null
memory: ?[]u8,
const init: MemoryDependency = .{
.ready = .unset,
.memory = undefined,
};
fn get(dep: *MemoryDependency, io: std.Io) ?[]u8 {
dep.ready.waitUncancelable(io);
return dep.memory;
}
};
};
};
};
/// 保证内存不会被重用。
const FuzzMultiThreadedAllocator = struct {
gpa: mem.Allocator,
fill: usize,
active_allocs: usize,
fail_i: usize,
fixed_remap_i: usize,
// 假定以下内容由外部同步
// 即每个线程首次使用分配器之前,都具有获取屏障
buf: []u8,
fails: []const bool,
fixed_remaps: []const bool,
fn allocator(f: *FuzzMultiThreadedAllocator) mem.Allocator {
@disableInstrumentation();
return .{ .ptr = f, .vtable = &.{
.alloc = FuzzMultiThreadedAllocator.alloc,
.free = FuzzMultiThreadedAllocator.free,
.resize = FuzzMultiThreadedAllocator.resize,
.remap = FuzzMultiThreadedAllocator.remap,
} };
}
fn maybeFail(f: *FuzzMultiThreadedAllocator) bool {
@disableInstrumentation();
const i = @atomicRmw(usize, &f.fail_i, .Add, 1, .monotonic);
return i < f.fails.len and f.fails[i];
}
fn maybeFixedRemap(f: *FuzzMultiThreadedAllocator) bool {
@disableInstrumentation();
const i = @atomicRmw(usize, &f.fixed_remap_i, .Add, 1, .monotonic);
return i < f.fixed_remaps.len and f.fixed_remaps[i];
}
fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, _: usize) ?[*]u8 {
@disableInstrumentation();
const f: *FuzzMultiThreadedAllocator = @ptrCast(@alignCast(ctx));
const memory = f.allocInner(len, alignment) orelse return null;
_ = @atomicRmw(usize, &f.active_allocs, .Add, 1, .monotonic);
return memory;
}
fn allocInner(f: *FuzzMultiThreadedAllocator, len: usize, alignment: Alignment) ?[*]u8 {
var prev_fill = @atomicLoad(usize, &f.fill, .monotonic);
var start: usize = undefined;
while (true) {
const start_addr = alignment.forward(@intFromPtr(f.buf[prev_fill..].ptr));
start = @as([*]u8, @ptrFromInt(start_addr)) - f.buf.ptr;
if (start +| len > f.buf.len or f.maybeFail()) return null;
prev_fill = @cmpxchgStrong(
usize,
&f.fill,
prev_fill,
start + len,
.monotonic,
.monotonic,
) orelse {
@branchHint(.likely);
break;
};
}
return f.buf[start..][0..len].ptr;
}
fn free(ctx: *anyopaque, _: []u8, _: Alignment, _: usize) void {
@disableInstrumentation();
const f: *FuzzMultiThreadedAllocator = @ptrCast(@alignCast(ctx));
assert(@atomicRmw(usize, &f.active_allocs, .Sub, 1, .monotonic) != 0);
}
fn resize(ctx: *anyopaque, memory: []u8, _: Alignment, new_len: usize, _: usize) bool {
@disableInstrumentation();
const f: *FuzzMultiThreadedAllocator = @ptrCast(@alignCast(ctx));
const start = memory.ptr - f.buf.ptr;
const old_end = start + memory.len;
const new_end = start +| new_len;
if (new_end > f.buf.len or f.maybeFail()) {
return false;
}
if (new_len <= memory.len) {
// fill 未减小,因此内存不会被复用。
return true;
}
return @cmpxchgStrong(usize, &f.fill, old_end, new_end, .monotonic, .monotonic) == null;
}
fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, _: usize) ?[*]u8 {
@disableInstrumentation();
if (maybeFixedRemap(@ptrCast(@alignCast(ctx)))) {
const resized = FuzzMultiThreadedAllocator.resize(
ctx,
memory,
alignment,
new_len,
undefined,
);
return if (resized) memory.ptr else null;
}
const f: *FuzzMultiThreadedAllocator = @ptrCast(@alignCast(ctx));
const new_ptr = f.allocInner(new_len, alignment) orelse return null;
const copy_len = @min(memory.len, new_len);
@memcpy(new_ptr[0..copy_len], memory[0..copy_len]);
return new_ptr;
}
};
fn fuzzMultiThreaded(ctx: FuzzMultiThreadedContext, smith: *Smith) !void {
@disableInstrumentation();
var gpa_instance: std.heap.FixedBufferAllocator = .init(ctx.testing_buf);
const gpa = gpa_instance.allocator();
var op_count: u32 = 0;
while (!smith.eosWeighted(fuzz_probs.eos)) op_count += 1;
const Op = FuzzMultiThreadedContext.ThreadOps.Op;
const ops = gpa.alloc(Op, op_count) catch return error.SkipZigTest;
const op_results = gpa.alloc(Op.MemoryDependency, op_count) catch return error.SkipZigTest;
@memset(op_results, .init);
const allocs = gpa.alloc(struct {
memory: *FuzzMultiThreadedContext.ThreadOps.Op.MemoryDependency,
alignment: Alignment,
splat: ?u8,
}, op_count) catch return error.SkipZigTest;
var allocs_n: u32 = 0;
var expected_remaps: usize = 0;
const options = fuzz_probs.generateOptions(smith);
for (ops, op_results) |*op, *result| switch (fuzz_probs.generateOp(smith, allocs_n != 0)) {
.alloc => {
const splat = fuzz_probs.generateSplat(smith);
const will_memset = options.check_write_after_free or splat != null;
op.* = .{ .alloc = .{
.len = fuzz_probs.generateLen(smith, will_memset),
.alignment = smith.valueWeighted(Alignment, fuzz_probs.alignment),
.splat = splat,
.result = result,
} };
allocs[allocs_n] = .{
.memory = result,
.alignment = op.alloc.alignment,
.splat = splat,
};
allocs_n += 1;
},
.free => {
const i = smith.valueRangeLessThan(u32, 0, allocs_n);
op.* = .{ .free = .{
.memory = allocs[i].memory,
.alignment = allocs[i].alignment,
.splat = allocs[i].splat,
} };
allocs_n -= 1;
allocs[i] = allocs[allocs_n];
},
.resize, .remap => |kind| {
op.* = switch (kind) {
.remap => .{ .remap = undefined },
.resize => .{ .resize = undefined },
else => unreachable,
};
const realloc = switch (kind) {
.remap => &op.remap,
.resize => &op.resize,
else => unreachable,
};
expected_remaps += @intFromBool(kind == .remap);
const i = smith.valueRangeLessThan(u32, 0, allocs_n);
realloc.* = .{
.memory = allocs[i].memory,
.alignment = allocs[i].alignment,
.new_len = fuzz_probs.generateLen(smith, options.check_write_after_free),
.splat = allocs[i].splat,
.result = result,
};
allocs[i].memory = result;
},
};
const fails: []bool = gpa.alloc(bool, ops.len * 2 + smith.value(u8)) catch &.{};
const fixed_remaps: []bool = gpa.alloc(bool, expected_remaps + smith.value(u8)) catch &.{};
for (fails) |*f| f.* = smith.boolWeighted(31, 1);
for (fixed_remaps) |*f| f.* = smith.value(bool);
var backing_gpa_instance: FuzzMultiThreadedAllocator = .{
.gpa = gpa,
.fill = 0,
.active_allocs = 0,
.fail_i = 0,
.fixed_remap_i = 0,
.buf = ctx.backing_buf,
.fails = fails,
.fixed_remaps = fixed_remaps,
};
const backing_gpa = backing_gpa_instance.allocator();
ctx.ops.instance = .init(backing_gpa, options);
ctx.ops.i = 0;
ctx.ops.items = ops;
ctx.ops.running = FuzzMultiThreadedContext.n_threads;
// 可以非原子地加载 `ctx.ops.run`,因为只有此线程会写入它。
@atomicStore(FuzzMultiThreadedContext.ThreadOps.Run, &ctx.ops.run, ctx.ops.run.next(), .release);
ctx.io.futexWake(FuzzMultiThreadedContext.ThreadOps.Run, &ctx.ops.run, math.maxInt(u32));
while (true) {
const prev_running = @atomicLoad(u32, &ctx.ops.running, .acquire);
if (prev_running == 0) break;
ctx.io.futexWaitUncancelable(u32, &ctx.ops.running, prev_running);
}
var expected_allocs = allocs_n;
for (allocs[0..allocs_n]) |a| {
expected_allocs -= @intFromBool(a.memory.memory == null);
}
try std.testing.expectEqual(expected_allocs, ctx.ops.instance.deinitLog(false));
try std.testing.expectEqual(0, backing_gpa_instance.active_allocs); // 无泄漏
}
fn fuzzMultiThreadedWorker(
io: std.Io,
ops: *FuzzMultiThreadedContext.ThreadOps,
) error{Canceled}!void {
const no_ra: usize = 0;
var next_run: FuzzMultiThreadedContext.ThreadOps.Run = .{ .n = true };
while (true) {
try ops.run.wait(next_run, io);
next_run = .next(next_run);
while (true) {
const i = @atomicRmw(usize, &ops.i, .Add, 1, .monotonic);
if (i >= ops.items.len) {
// 必须使用 `.acq_rel`,因为获取加载只与写入所读取值的线程同步,并不与所有先前的写入线程同步。
//
const prev_rem = @atomicRmw(u32, &ops.running, .Sub, 1, .acq_rel);
if (prev_rem - 1 == 0) {
io.futexWake(u32, &ops.running, 1);
}
break;
}
switch (ops.items[i]) {
.alloc => |call| {
const alloc_ptr = alloc(&ops.instance, call.len, call.alignment, no_ra);
if (alloc_ptr) |memory_ptr| {
const memory = memory_ptr[0..call.len];
if (call.splat) |b| @memset(memory, b);
call.result.memory = memory;
} else {
call.result.memory = null;
}
call.result.ready.set(io);
},
.free => |call| {
const memory = call.memory.get(io) orelse continue;
fuzz_probs.checkSplat(call.splat, memory);
free(&ops.instance, memory, call.alignment, no_ra);
},
.resize, .remap => |call, kind| {
const memory = call.memory.get(io) orelse {
call.result.memory = null;
call.result.ready.set(io);
continue;
};
const new_memory: []u8 = switch (kind) {
.remap => if (remap(
&ops.instance,
memory,
call.alignment,
call.new_len,
no_ra,
)) |new_ptr| new_ptr[0..call.new_len] else memory,
.resize => if (resize(
&ops.instance,
memory,
call.alignment,
call.new_len,
no_ra,
)) memory.ptr[0..call.new_len] else memory,
else => unreachable,
};
const old_len = memory.len;
const new_len = new_memory.len;
fuzz_probs.checkSplat(call.splat, new_memory[0..@min(old_len, new_len)]);
if (call.splat) |b| @memset(new_memory[@min(old_len, new_len)..], b);
call.result.memory = new_memory;
call.result.ready.set(io);
},
}
}
}
}