跳转到内容

std.heap.SafeAllocator

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

第 1 行

提供以下保证:

  • 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

std.heap.SafeAllocator.acquireThread

函数

第 753 行

fn acquireThread(s: *SafeAllocator) *Thread

参数

std.heap.SafeAllocator.addOrOom

函数

第 779 行

fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize

参数

a: usize
b: usize

错误

OutOfMemory

std.heap.SafeAllocator.advanceBucketAlloc

函数

第 995 行

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

函数

第 774 行

fn alignForwardOrOom(a: Alignment, addr: usize) error{OutOfMemory}!usize

参数

a: Alignment
addr: usize

错误

OutOfMemory

std.heap.SafeAllocator.Alignment

别名

第 34 行

别名目标 std.mem.Alignment

std.heap.SafeAllocator.alloc

函数

第 1053 行

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

参数

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

std.heap.SafeAllocator.allocator

函数

第 749 行

返回的分配器是线程安全的

pub fn allocator(s: *SafeAllocator) mem.Allocator

参数

std.heap.SafeAllocator.allocBucket

函数

第 904 行

若此操作失败,后续向该桶分配内存均不合法

fn allocBucket( s: *SafeAllocator, t: *Thread, b: *Bucket, len: usize, alignment: Alignment, ra: usize, ) ?[*]u8

参数

s: *SafeAllocator
t: *Thread
b: *Bucket
len: usize
alignment: Alignment
ra: usize

std.heap.SafeAllocator.AllocFooter

容器

第 268 行

放在分配块尾部,有以下优点:

  • 对于桶,最后一个分配块的尾部结构始终位于当前填充位置。
  • 更容易对齐分配块,浪费的空间更少。
  • 越界写更可能破坏尾部结构,从而被检测出来。 对于桶内分配,其后跟随 [2][stack_trace_size]usize。 对于大块分配,其后跟随 [1][stack_trace_size]usize。

字段

checksum: u32

使用数据地址的哈希作为种子,计算 data 的哈希,从而检测分配 元数据被 memcpy;若不能即时检测,至少能在不同运行期间发现。

将此存储值与 canary 值异或,以便检测 canary 不匹配。

modify: Modify

以 .monotonic 内存顺序原子访问,以捕获操作竞态。

存储值与其地址的哈希异或,以检测分配元数据的内存复制, 或至少在不同运行之间捕获这种复制。

data: Data
_: void align(@max(8, @alignOf(usize))) = {}

8:Bucket 分配的最小对齐值 @alignOf(usize):使尾随数据的偏移位于 @sizeOf(@This())

std.heap.SafeAllocator.AllocFooter.actualChecksum

函数

第 413 行

fn actualChecksum(f: *AllocFooter, s: *SafeAllocator) u32

参数

std.heap.SafeAllocator.AllocFooter.allocAlign

函数

第 435 行

fn allocAlign(a: Alignment) Alignment

参数

std.heap.SafeAllocator.AllocFooter.allocLenBucket

函数

第 455 行

fn allocLenBucket(s: *SafeAllocator, len: usize, is_extended: bool) usize

参数

s: *SafeAllocator
len: usize
is_extended: bool

std.heap.SafeAllocator.AllocFooter.allocLenBucketOrOom

函数

第 467 行

fn allocLenBucketOrOom( s: *SafeAllocator, len: usize, is_extended: bool, ) error{OutOfMemory}!usize

参数

s: *SafeAllocator
len: usize
is_extended: bool

错误

OutOfMemory

std.heap.SafeAllocator.AllocFooter.allocLenLarge

函数

第 459 行

fn allocLenLarge(s: *SafeAllocator, len: usize) usize

参数

s: *SafeAllocator
len: usize

std.heap.SafeAllocator.AllocFooter.allocOffset

函数

第 431 行

fn allocOffset(len: usize) usize

参数

len: usize

std.heap.SafeAllocator.AllocFooter.allocOffsetOrOom

函数

第 463 行

fn allocOffsetOrOom(len: usize) error{OutOfMemory}!usize

参数

len: usize

错误

OutOfMemory

std.heap.SafeAllocator.AllocFooter.allocTrace

函数

第 404 行

fn allocTrace(f: *AllocFooter, s: *SafeAllocator) []usize

参数

std.heap.SafeAllocator.AllocFooter.bucketPrev

函数

第 392 行

fn bucketPrev(f: *AllocFooter, b: *Bucket, s: *SafeAllocator) ?*AllocFooter

参数

std.heap.SafeAllocator.AllocFooter.Data

容器

第 289 行

字段

len: Len
alignment: u2

对齐量的低位。

对于非扩展标头,这就是完整对齐量。由于 Bucket 中的页脚保证 至少按 8 字节对齐,前一个标头的位置就在此次分配之前。

prev_extended: bool

仅用于桶式分配。

std.heap.SafeAllocator.AllocFooter.Data.Len

容器

第 300 行

字段

_

std.heap.SafeAllocator.AllocFooter.Data.Len.extended_start

常量

第 308 行

此尾部后面、跟踪信息之前,跟随 Extended。 对齐值的高位编码为相对于 extended_start 的偏移量。

即使严格来说不需要 Extended,也可能因 调整大小和重新映射而设置此标志。

u13

std.heap.SafeAllocator.AllocFooter.extended

函数

第 370 行

fn extended(f: *AllocFooter) *Extended

参数

std.heap.SafeAllocator.AllocFooter.Extended

容器

第 312 行

字段

len: usize
container: Container

std.heap.SafeAllocator.AllocFooter.Extended.Container

容器

第 316 行

字段

bucket_prev: ?*AllocFooter
large_entry: *Allocs.Entry

std.heap.SafeAllocator.AllocFooter.freeTrace

函数

第 408 行

fn freeTrace(f: *AllocFooter, s: *SafeAllocator) []usize

参数

std.heap.SafeAllocator.AllocFooter.isExtended

函数

第 366 行

fn isExtended(f: *AllocFooter) bool

参数

std.heap.SafeAllocator.AllocFooter.lenBucket

函数

第 445 行

fn lenBucket(s: *SafeAllocator, is_extended: bool) usize

参数

s: *SafeAllocator
is_extended: bool

std.heap.SafeAllocator.AllocFooter.lenLarge

函数

第 451 行

fn lenLarge(s: *SafeAllocator) usize

参数

std.heap.SafeAllocator.AllocFooter.Modify

容器

第 328 行

字段

none = 0x2962
resized = 0x0030
remaped = 0x9068
freeing = 0x7f3d
freed = 0xb98b
_

std.heap.SafeAllocator.AllocFooter.Modify.opName

函数

第 341 行

fn opName(m: Modify) []const u8

参数

m: Modify

std.heap.SafeAllocator.AllocFooter.Modify.setNone

函数

第 337 行

fn setNone(m: *Modify) void

参数

m: *Modify

std.heap.SafeAllocator.AllocFooter.Modify.stateName

函数

第 350 行

fn stateName(m: Modify) []const u8

参数

m: Modify

std.heap.SafeAllocator.AllocFooter.Modify.storedXor

函数

第 360 行

fn storedXor(m: Modify, ptr: *Modify) Modify

参数

m: Modify
ptr: *Modify

std.heap.SafeAllocator.AllocFooter.of

函数

第 475 行

fn of(user_memory: []u8) *AllocFooter

参数

user_memory: []u8

std.heap.SafeAllocator.AllocFooter.populate

函数

第 579 行

调用方负责对相应的 Bucket.alloc_count 执行 .acquire 栅栏。

fn populate( memory: []align(@alignOf(AllocFooter)) u8, len: usize, alignment: Alignment, ra: usize, is_extended: bool, prev_extended: bool, container: Extended.Container, s: *SafeAllocator, ) *AllocFooter

参数

memory: []align(@alignOf(AllocFooter)) u8
len: usize
alignment: Alignment
ra: usize
is_extended: bool

大型分配时为 true

prev_extended: bool

大块分配时为 false

container: Extended.Container
s: *SafeAllocator

std.heap.SafeAllocator.AllocFooter.requiresExtended

函数

第 441 行

假定尾部位于桶分配中;所有 大块分配都需要扩展头部。

fn requiresExtended(len: usize, alignment: Alignment) bool

参数

len: usize
alignment: Alignment

std.heap.SafeAllocator.AllocFooter.startModify

函数

第 482 行

fn startModify(f: *AllocFooter, m: Modify, s: *SafeAllocator, mem_fmt: FormatMemory) void

参数

std.heap.SafeAllocator.AllocFooter.tracesPtr

函数

第 397 行

fn tracesPtr(f: *AllocFooter) [*]usize

参数

std.heap.SafeAllocator.AllocFooter.userAlign

函数

第 387 行

fn userAlign(f: *AllocFooter) Alignment

参数

std.heap.SafeAllocator.AllocFooter.userLen

函数

第 382 行

fn userLen(f: *AllocFooter) usize

参数

std.heap.SafeAllocator.AllocFooter.userMemory

函数

第 375 行

fn userMemory(f: *AllocFooter) []u8

参数

std.heap.SafeAllocator.Allocs

容器

第 107 行

后面跟随 [allocs_entry_count]Entry

字段

next: ?*Allocs

std.heap.SafeAllocator.Allocs.entries

函数

第 119 行

fn entries(a: *Allocs, s: *SafeAllocator) []Entry

参数

std.heap.SafeAllocator.Allocs.Entry

容器

第 123 行

字段

kind: Kind
ptr_high: @Int(.unsigned, @bitSizeOf(usize) - 2)

std.heap.SafeAllocator.Allocs.Entry.fromBucket

函数

第 142 行

fn fromBucket(ptr: *Bucket) Entry

参数

ptr: *Bucket

std.heap.SafeAllocator.Allocs.Entry.fromFree

函数

第 135 行

fn fromFree(ptr: ?*Entry) Entry

参数

ptr: ?*Entry

std.heap.SafeAllocator.Allocs.Entry.fromLargeAlloc

函数

第 149 行

fn fromLargeAlloc(ptr: *AllocFooter) Entry

参数

ptr: *AllocFooter

std.heap.SafeAllocator.Allocs.Entry.Kind

容器

第 127 行

字段

free
bucket
large_alloc

std.heap.SafeAllocator.Allocs.Entry.toBucket

函数

第 161 行

fn toBucket(ent: Entry) *Bucket

参数

ent: Entry

std.heap.SafeAllocator.Allocs.Entry.toFree

函数

第 156 行

fn toFree(ent: Entry) ?*Entry

参数

ent: Entry

std.heap.SafeAllocator.Allocs.Entry.toLargeAlloc

函数

第 166 行

fn toLargeAlloc(ent: Entry) *AllocFooter

参数

ent: Entry

std.heap.SafeAllocator.Allocs.usizes

函数

第 115 行

fn usizes(a: *Allocs, s: *SafeAllocator) []usize

参数

std.heap.SafeAllocator.assert

别名

第 35 行

别名目标 std.debug.assert

std.heap.SafeAllocator.Bucket

容器

第 180 行

此结构体包含桶头,始终属于一个更大的分配, 该分配的长度与对齐均为 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

容器

第 197 行

字段

n: u31
filling: bool

若为 true,此桶暂时不能释放。

std.heap.SafeAllocator.Bucket.AllocCount.fenceAcqRel

函数

第 202 行

fn fenceAcqRel(a: *AllocCount) void

参数

std.heap.SafeAllocator.Bucket.allocFooterBefore

函数

第 230 行

fn allocFooterBefore(b: *Bucket, s: *SafeAllocator, at: u32, is_extended: bool) ?*AllocFooter

参数

b: *Bucket
s: *SafeAllocator
at: u32
is_extended: bool

std.heap.SafeAllocator.Bucket.bytes

函数

第 221 行

fn bytes(b: *Bucket, s: *SafeAllocator) []u8

参数

std.heap.SafeAllocator.Bucket.check

函数

第 240 行

检查是否存在释放后写入。

假定已使用 .acquire 顺序加载 b.alloc_count。

fn check(b: *Bucket, s: *SafeAllocator) void

参数

std.heap.SafeAllocator.Bucket.Fill

容器

第 207 行

字段

at: u31
last_is_extended: bool

std.heap.SafeAllocator.Bucket.fillAt

函数

第 217 行

fn fillAt(s: *SafeAllocator, ptr: [*]const u8) u32

参数

s: *SafeAllocator
ptr: [*]const u8

std.heap.SafeAllocator.Bucket.lastAlloc

函数

第 226 行

fn lastAlloc(b: *Bucket, s: *SafeAllocator, fill: Fill) ?*AllocFooter

参数

b: *Bucket
s: *SafeAllocator
fill: Fill

std.heap.SafeAllocator.Bucket.of

函数

第 212 行

fn of(s: *SafeAllocator, ptr: [*]u8) *Bucket

参数

s: *SafeAllocator
ptr: [*]u8

std.heap.SafeAllocator.bucketMask

函数

第 91 行

fn bucketMask(s: *SafeAllocator) u32

参数

std.heap.SafeAllocator.bucketSize

函数

第 87 行

fn bucketSize(s: *SafeAllocator) u32

参数

std.heap.SafeAllocator.captureStackTrace

函数

第 868 行

首个元素存储包括已跳过栈帧在内的栈轨迹长度。 其余元素存储返回地址。

fn captureStackTrace(trace_buf: []usize, ra: usize) void

参数

trace_buf: []usize
ra: usize

std.heap.SafeAllocator.checkFreed

函数

第 835 行

返回首次释放后写入的地址

fn checkFreed(s: *SafeAllocator, footer: *AllocFooter) void

参数

s: *SafeAllocator
footer: *AllocFooter

std.heap.SafeAllocator.deinit

函数

第 653 行

返回泄漏数量

pub fn deinit(s: *SafeAllocator) usize

参数

std.heap.SafeAllocator.deinitLargeAlloc

函数

第 729 行

fn deinitLargeAlloc(s: *SafeAllocator, footer: *AllocFooter, log: bool) void

参数

s: *SafeAllocator
footer: *AllocFooter
log: bool

std.heap.SafeAllocator.deinitLeakedBucket

函数

第 688 行

返回实际的泄漏数量

fn deinitLeakedBucket(s: *SafeAllocator, b: *Bucket, log: bool) usize

参数

s: *SafeAllocator
b: *Bucket
log: bool

std.heap.SafeAllocator.deinitLog

函数

第 658 行

与 deinit 相同,但若 log 为 false,则不会记录内存泄漏。

pub fn deinitLog(s: *SafeAllocator, log: bool) usize

参数

s: *SafeAllocator
log: bool

std.heap.SafeAllocator.FormatMemory

容器

第 854 行

字段

memory: []const u8
alignment: Alignment

std.heap.SafeAllocator.FormatMemory.format

函数

第 858 行

pub fn format(m: FormatMemory, w: *std.Io.Writer) std.Io.Writer.Error!void

参数

错误

WriteFailed

详细诊断信息见 Writer 实现。

std.heap.SafeAllocator.formatStackTrace

函数

第 883 行

fn formatStackTrace(trace_buf: []usize) std.debug.FormatStackTrace

参数

trace_buf: []usize

std.heap.SafeAllocator.free

函数

第 1118 行

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

参数

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

std.heap.SafeAllocator.freeAllocEntry

函数

第 820 行

fn freeAllocEntry(t: *Thread, ent: *Allocs.Entry) void

参数

t: *Thread
ent: *Allocs.Entry

std.heap.SafeAllocator.fuzz_probs

命名空间

第 1346 行

由单线程和多线程模糊测试共享。

std.heap.SafeAllocator.fuzz_probs.alignment

常量

第 1347 行

[]const Smith.Weight

std.heap.SafeAllocator.fuzz_probs.checkSplat

函数

第 1439 行

fn checkSplat(splat: ?u8, bytes: []const u8) void

参数

splat: ?u8
bytes: []const u8

std.heap.SafeAllocator.fuzz_probs.eos

常量

第 1353 行

[]const Smith.Weight

std.heap.SafeAllocator.fuzz_probs.generateLen

函数

第 1407 行

fn generateLen(smith: *Smith, will_memset: bool) usize

参数

smith: *Smith
will_memset: bool

std.heap.SafeAllocator.fuzz_probs.generateOp

函数

第 1388 行

fn generateOp(smith: *Smith, any_allocs: bool) Op

参数

smith: *Smith
any_allocs: bool

std.heap.SafeAllocator.fuzz_probs.generateOptions

函数

第 1360 行

fn generateOptions(smith: *Smith) Options

参数

smith: *Smith

std.heap.SafeAllocator.fuzz_probs.generateSplat

函数

第 1396 行

fn generateSplat(smith: *Smith) ?u8

参数

smith: *Smith

std.heap.SafeAllocator.fuzz_probs.Op

容器

第 1387 行

字段

std.heap.SafeAllocator.fuzzMultiThreaded

函数

第 1988 行

fn fuzzMultiThreaded(ctx: FuzzMultiThreadedContext, smith: *Smith) !void

参数

std.heap.SafeAllocator.FuzzMultiThreadedAllocator

容器

第 1873 行

保证内存不会被重用。

字段

gpa: mem.Allocator
fill: usize
active_allocs: usize
fail_i: usize
fixed_remap_i: usize
buf: []u8
fails: []const bool
fixed_remaps: []const bool

std.heap.SafeAllocator.FuzzMultiThreadedAllocator.alloc

函数

第 1909 行

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

参数

ctx: *anyopaque
len: usize
alignment: Alignment
_: usize

std.heap.SafeAllocator.FuzzMultiThreadedAllocator.allocator

函数

第 1887 行

fn allocator(f: *FuzzMultiThreadedAllocator) mem.Allocator

参数

std.heap.SafeAllocator.FuzzMultiThreadedAllocator.allocInner

函数

第 1918 行

fn allocInner(f: *FuzzMultiThreadedAllocator, len: usize, alignment: Alignment) ?[*]u8

参数

f: *FuzzMultiThreadedAllocator
len: usize
alignment: Alignment

std.heap.SafeAllocator.FuzzMultiThreadedAllocator.free

函数

第 1940 行

fn free(ctx: *anyopaque, _: []u8, _: Alignment, _: usize) void

参数

ctx: *anyopaque
_: []u8
_: Alignment
_: usize

std.heap.SafeAllocator.FuzzMultiThreadedAllocator.maybeFail

函数

第 1897 行

fn maybeFail(f: *FuzzMultiThreadedAllocator) bool

参数

std.heap.SafeAllocator.FuzzMultiThreadedAllocator.maybeFixedRemap

函数

第 1903 行

fn maybeFixedRemap(f: *FuzzMultiThreadedAllocator) bool

参数

std.heap.SafeAllocator.FuzzMultiThreadedAllocator.remap

函数

第 1966 行

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

参数

ctx: *anyopaque
memory: []u8
alignment: Alignment
new_len: usize
_: usize

std.heap.SafeAllocator.FuzzMultiThreadedAllocator.resize

函数

第 1947 行

fn resize(ctx: *anyopaque, memory: []u8, _: Alignment, new_len: usize, _: usize) bool

参数

ctx: *anyopaque
memory: []u8
_: Alignment
new_len: usize
_: usize

std.heap.SafeAllocator.FuzzMultiThreadedContext

容器

第 1780 行

字段

testing_buf: []u8
backing_buf: []u8
io: std.Io
ops: *ThreadOps

std.heap.SafeAllocator.FuzzMultiThreadedContext.n_threads

常量

第 1787 行

std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps

容器

第 1789 行

字段

run: Run

每次运行开始时在两个值之间切换。

running: u32

虽然可计算为 n_threads - (i -| ops.items.len), 但此操作也为每个线程提供 .release 同步。

instance: SafeAllocator
i: usize
items: []Op

std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Op

容器

第 1823 行

字段

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

容器

第 1853 行

字段

ready: std.Io.Event
memory: ?[]u8

内存分配失败时为 Null

std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Op.MemoryDependency.get

函数

第 1863 行

fn get(dep: *MemoryDependency, io: std.Io) ?[]u8

参数

dep: *MemoryDependency
io: std.Io

std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Op.MemoryDependency.init

常量

第 1858 行

MemoryDependency

std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Op.Realloc

容器

第 1842 行

字段

memory: *MemoryDependency
alignment: Alignment
new_len: usize
splat: ?u8
result: *MemoryDependency

为绕过 tsan 问题,不直接嵌入结构体; 因为直接对 Op 执行 switch 会非原子地加载整个值。

std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Run

容器

第 1800 行

字段

n: bool
pad: u31 = 0

std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Run.next

函数

第 1817 行

fn next(r: Run) Run

参数

r: Run

std.heap.SafeAllocator.FuzzMultiThreadedContext.ThreadOps.Run.wait

函数

第 1804 行

fn wait(ptr: *Run, val: Run, io: std.Io) error{Canceled}!void

参数

ptr: *Run
val: Run
io: std.Io

错误

Canceled

std.heap.SafeAllocator.fuzzMultiThreadedWorker

函数

第 2106 行

fn fuzzMultiThreadedWorker( io: std.Io, ops: *FuzzMultiThreadedContext.ThreadOps, ) error{Canceled}!void

参数

错误

Canceled

std.heap.SafeAllocator.fuzzSingleThreaded

函数

第 1599 行

fn fuzzSingleThreaded(ctx: FuzzSingleThreadedContext, smith: *Smith) !void

参数

std.heap.SafeAllocator.FuzzSingleThreadedAllocator

容器

第 1469 行

保证内存不会被重用。

字段

gpa: mem.Allocator
smith: *std.testing.Smith
buf: []u8
fill: usize
allocs: std.MultiArrayList(AllocInfo)

std.heap.SafeAllocator.FuzzSingleThreadedAllocator.alloc

函数

第 1493 行

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

参数

ctx: *anyopaque
len: usize
alignment: Alignment
_: usize

std.heap.SafeAllocator.FuzzSingleThreadedAllocator.allocator

函数

第 1483 行

fn allocator(f: *FuzzSingleThreadedAllocator) mem.Allocator

参数

std.heap.SafeAllocator.FuzzSingleThreadedAllocator.allocIndex

函数

第 1518 行

fn allocIndex(f: *FuzzSingleThreadedAllocator, memory: []u8, alignment: Alignment) usize

参数

f: *FuzzSingleThreadedAllocator
memory: []u8
alignment: Alignment

std.heap.SafeAllocator.FuzzSingleThreadedAllocator.AllocInfo

容器

第 1477 行

字段

ptr: [*]u8
len: usize
alignment: Alignment

std.heap.SafeAllocator.FuzzSingleThreadedAllocator.allocInner

函数

第 1508 行

fn allocInner(f: *FuzzSingleThreadedAllocator, len: usize, alignment: Alignment) ?[*]u8

参数

f: *FuzzSingleThreadedAllocator
len: usize
alignment: Alignment

std.heap.SafeAllocator.FuzzSingleThreadedAllocator.free

函数

第 1537 行

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

参数

ctx: *anyopaque
memory: []u8
alignment: Alignment
_: usize

std.heap.SafeAllocator.FuzzSingleThreadedAllocator.remap

函数

第 1568 行

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

参数

ctx: *anyopaque
memory: []u8
alignment: Alignment
new_len: usize
_: usize

std.heap.SafeAllocator.FuzzSingleThreadedAllocator.resize

函数

第 1544 行

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

参数

ctx: *anyopaque
memory: []u8
alignment: Alignment
new_len: usize
_: usize

std.heap.SafeAllocator.FuzzSingleThreadedContext

容器

第 1463 行

字段

testing_buf: []u8
backing_buf: []u8

std.heap.SafeAllocator.growingResizeBucket

函数

第 983 行

fn growingResizeBucket( s: *SafeAllocator, f: *AllocFooter, memory: []const u8, alignment: Alignment, new_len: usize, ra: usize, ) bool

参数

s: *SafeAllocator
f: *AllocFooter
memory: []const u8
alignment: Alignment
new_len: usize
ra: usize

std.heap.SafeAllocator.init

函数

第 621 行

pub fn init( backing: mem.Allocator, options: Options, ) SafeAllocator

参数

backing: mem.Allocator

此项必须线程安全,分配器才可能线程安全。

options: Options

std.heap.SafeAllocator.isLarge

函数

第 783 行

fn isLarge(s: *SafeAllocator, len: usize, alignment: Alignment) bool

参数

s: *SafeAllocator
len: usize
alignment: Alignment

std.heap.SafeAllocator.isLargeOrOom

函数

第 789 行

fn isLargeOrOom(s: *SafeAllocator, len: usize, alignment: Alignment) error{OutOfMemory}!bool

参数

s: *SafeAllocator
len: usize
alignment: Alignment

错误

OutOfMemory

std.heap.SafeAllocator.math

别名

第 32 行

别名目标 std.math

std.heap.SafeAllocator.mem

别名

第 33 行

别名目标 std.mem

std.heap.SafeAllocator.n_threads

变量

第 69 行

usize

std.heap.SafeAllocator.newAllocEntry

函数

第 795 行

fn newAllocEntry(s: *SafeAllocator, t: *Thread, ra: usize) error{OutOfMemory}!*Allocs.Entry

参数

s: *SafeAllocator
t: *Thread
ra: usize

错误

OutOfMemory

std.heap.SafeAllocator.Options

容器

第 41 行

字段

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

常量

第 42 行

std.heap.SafeAllocator.Options.page_size_log2

常量

第 43 行

std.heap.SafeAllocator.overwriteFreed

函数

第 825 行

fn overwriteFreed(s: *SafeAllocator, bytes: []u8) void

参数

s: *SafeAllocator
bytes: []u8

std.heap.SafeAllocator.panic

别名

第 36 行

别名目标 std.debug.panic

std.heap.SafeAllocator.remap

函数

第 1246 行

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

参数

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

std.heap.SafeAllocator.resize

函数

第 1178 行

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

参数

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

std.heap.SafeAllocator.SafeAllocator

别名

第 38 行

别名目标 std.heap.SafeAllocator

std.heap.SafeAllocator.scoped_log

类型

第 39 行

std.heap.SafeAllocator.Smith

别名

第 1343 行

别名目标 std.testing.Smith

std.heap.SafeAllocator.std

别名

第 31 行

别名目标 std

std.heap.SafeAllocator.Thread

容器

第 95 行

字段

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

避免伪共享。

mutex: std.atomic.Mutex
fill_bucket: ?*Bucket
free_entry: ?*Allocs.Entry
allocs_next: usize
allocs_first: ?*Allocs

std.heap.SafeAllocator.thread_index

变量

第 70 行

usize

std.heap.SafeAllocator.vtable

常量

第 1046 行

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);
                },
            }
        }
    }
}