面向 Debug 模式的分配器。
特性
- 在分配、释放时捕获栈回溯,也可选择在调整大小时捕获。
- 检测重复释放,并输出三次操作的全部回溯(首次分配、首次 释放、再次释放)。
- 检测内存泄漏,并附带栈回溯。
- 从不复用内存地址,使 Zig 更容易检测悬空指针导致的 基于未定义值的分支。这也要求 底层分配器不复用地址。
- 为底层分配设置最小大小,避免活跃内存映射过多 导致操作系统错误。
- 内存页不再需要时,尽快归还其驻留 内存,以便后续访问触发缺页异常。
- 跨平台。通过底层分配器工作,因此可在 任何环境中使用,包括独立式环境。
- 支持编译期配置。
这些特性使该分配器速度较慢,且空间开销较大。例如, 分配单个字节时,空间利用率不到 1%; 管理这一字节的分配需要超过 100 字节的 额外开销。分配大小越大,利用率越高。
基本设计
分配分为小型和大型两类。
小型分配根据 page_size 划分到不同的桶中:
index obj_size
0 1
1 2
2 4
3 8
4 16
5 32
6 64
7 128
8 256
9 512
10 1024
11 2048
...
索引按此规律延续,共有 small_bucket_count 个。
按 max(len, alignment) 将分配归入对象大小类别, 并向上取整到下一个二的幂。
分配器的主要状态包含一个数组,保存每种
大小类别的全部“当前”桶。数组中每个槽位可以为 null,表示该
类别尚未分配桶。首次为某一类别
分配对象时,从底层分配器分配一块大小为 page_size 的内存。
此分配划分为多个“槽位”,每个槽位对应一个已分配对象,同时预留
分配元数据的空间(以 BucketHeader 开头),元数据
位于该“页”的最末尾。
分配元数据包含“使用位”:每个槽位用一位表示
是否已使用。分配始终使用当前桶的下一个空闲
槽位,设置相应的使用位,
并递增 allocated_count。
释放时,根据地址、长度和 对齐恢复分配元数据;这依赖底层分配具有较大的对齐, 同时依赖分配不会从小型转为大型, 也不会从大型转为小型。
桶满后会分配新桶,其中保存指向 前一个桶的指针。泄漏检测会遍历此双向链表。
对小型分配而言,调整大小和重新映射的处理方式相同:若大小 类别不变,则操作成功且地址 不变;否则拒绝请求。
大型对象直接使用底层分配器分配。元数据
单独保存在同样使用底层分配器的 std.HashMap 中。
调整大小和重新映射直接转发给底层分配器, 但会使分配从大型变为小型的操作除外。
std.heap.debug_allocator.Allocator
别名
别名目标 std.mem.Allocator
std.heap.debug_allocator.assert
别名
别名目标 std.debug.assert
std.heap.debug_allocator.builtin
常量
std.heap.debug_allocator.Config
容器
字段
stack_trace_frames: usize = default_stack_trace_frames要捕获的栈帧数量。
enable_memory_limit: bool = false若为 true,分配器将包含两个字段:
total_requested_bytes:跟踪所请求分配的总内存字节数。requested_memory_limit:当total_requested_bytes超过此限制时, 使分配返回error.OutOfMemory。 若为 false,这些字段的类型为void。
safety: bool = std.debug.runtime_safety是否启用安全检查。
thread_safe: bool = !builtin.single_threaded是否允许多个线程同时使用该分配器。
never_unmap: bool = false这是一种临时调试技巧,可将段错误变为更有帮助的 日志错误消息,并附带详细栈跟踪。缺点是每次分配 都会泄漏,除非配合 retain_metadata 使用!
retain_metadata: bool = false临时调试辅助功能,无限期保留分配元数据, 以报告更多种类的重复释放。调用 deinit 时释放全部元数据。 与 never_unmap 一起使用时,有意泄漏的内存也会 在 deinit 时释放。目前应搭配 never_unmap,避免段错误。 TODO: https://github.com/ziglang/zig/issues/4298 将允许不搭配 never_unmap 使用。
verbose_log: bool = false启用信息消息输出,报告每次分配的大小和地址。
backing_allocator_zeroes: bool = true说明后备分配器是否返回已经清零的内存。
resize_stack_traces: bool = false调整已分配内存大小时,使用 resize 调用位置 刷新栈跟踪。这会带来性能开销。
canary: usize = @truncate(0x9232a6ff85dff10f)用于区分此分配器拥有的分配与 其他内存区域的魔数。
page_size: usize = default_page_size从底层分配器请求的分配大小,用于进一步细分为 小型分配的槽位。
必须为 2 的幂。
std.heap.debug_allocator.DebugAllocator
类型函数
此结构体的默认初始化方式已弃用;请改用 .init。
pub fn DebugAllocator(comptime config: Config) type
参数
config: Config
字段
backing_allocator: Allocator = std.heap.page_allocator
buckets: [small_bucket_count]?*BucketHeader = @splat(null)跟踪活动桶,即包含空闲槽位的桶。
large_allocations: LargeAllocTable = .empty
total_requested_bytes: @TypeOf(total_requested_bytes_init) = total_requested_bytes_init
requested_memory_limit: @TypeOf(requested_memory_limit_init) = requested_memory_limit_init
mutex: @TypeOf(mutex_init) = mutex_init
Selfinitslot_countspage_sizepage_alignSlotIndextotal_requested_bytes_initrequested_memory_limit_inithave_mutexmutex_initstack_none_trace_sizetraces_per_slotErrorminimum_slots_per_bucket_log2small_bucket_countlargest_bucket_object_sizeLargestSizeClassIntbucketCompareLargeAllocLargeAllocTableBucketHeaderallocatorbucketStackTracebucketRequestedSizesStartbucketAlignsStartbucketStackFramesStartbucketSizecalculateSlotCountusedBitsCountusedBitsSizedetectLeaksInBucketdetectLeaksfreeRetainedMetadataflushRetainedMetadatadeinitdeinitWithoutLeakCheckscollectStackTracereportDoubleFreeresizeLargefreeLargeallocresizeremapfreeresizeSmall
std.heap.debug_allocator.DebugAllocator.alloc
函数
fn alloc(context: *anyopaque, len: usize, alignment: mem.Alignment, ret_addr: usize) ?[*]u8
参数
std.heap.debug_allocator.DebugAllocator.allocator
函数
pub fn allocator(self: *Self) Allocator
参数
self: *Self
std.heap.debug_allocator.DebugAllocator.bucketAlignsStart
函数
fn bucketAlignsStart(slot_count: usize) usize
参数
slot_count: usize
std.heap.debug_allocator.DebugAllocator.bucketCompare
常量
std.heap.debug_allocator.DebugAllocator.bucketCompare.compare
函数
fn compare(a: *BucketHeader, b: *BucketHeader) std.math.Order
参数
a: *BucketHeader
b: *BucketHeader
std.heap.debug_allocator.DebugAllocator.BucketHeader
容器
桶在内存中的顺序如下:
- BucketHeader
- bucket_used_bits: [N]usize, // 每个槽位一位 -- 以下仅在 config.safety 为 true 时存在 --
- requested_sizes: [N]LargestSizeClassInt // 每个槽位一个整数
- log2_ptr_aligns: [N]u8 // 每个槽位一个字节 -- 以上仅在 config.safety 为 true 时存在 --
- stack_trace_addresses: [N]usize, // 每次分配保存 traces_per_slot 个地址
字段
allocated_count: SlotIndex
freed_count: SlotIndex
prev: ?*BucketHeader
next: ?*BucketHeader
canary: usize = config.canary
std.heap.debug_allocator.DebugAllocator.BucketHeader.captureStackTrace
函数
fn captureStackTrace( bucket: *BucketHeader, ret_addr: usize, slot_count: usize, slot_index: SlotIndex, trace_kind: TraceKind, ) void
参数
std.heap.debug_allocator.DebugAllocator.BucketHeader.fromPage
函数
fn fromPage(page_addr: usize, slot_count: usize) *BucketHeader
参数
page_addr: usize
slot_count: usize
std.heap.debug_allocator.DebugAllocator.BucketHeader.log2PtrAligns
函数
fn log2PtrAligns(bucket: *BucketHeader, slot_count: usize) []mem.Alignment
参数
bucket: *BucketHeader
slot_count: usize
std.heap.debug_allocator.DebugAllocator.BucketHeader.requestedSizes
函数
fn requestedSizes(bucket: *BucketHeader, slot_count: usize) []LargestSizeClassInt
参数
bucket: *BucketHeader
slot_count: usize
std.heap.debug_allocator.DebugAllocator.BucketHeader.stackTracePtr
函数
fn stackTracePtr( bucket: *BucketHeader, slot_count: usize, slot_index: SlotIndex, trace_kind: TraceKind, ) *[stack_n]usize
参数
std.heap.debug_allocator.DebugAllocator.BucketHeader.usedBits
函数
fn usedBits(bucket: *BucketHeader, index: usize) *usize
参数
bucket: *BucketHeader
index: usize
std.heap.debug_allocator.DebugAllocator.bucketRequestedSizesStart
函数
fn bucketRequestedSizesStart(slot_count: usize) usize
参数
slot_count: usize
std.heap.debug_allocator.DebugAllocator.bucketSize
函数
fn bucketSize(slot_count: usize) usize
参数
slot_count: usize
std.heap.debug_allocator.DebugAllocator.bucketStackFramesStart
函数
fn bucketStackFramesStart(slot_count: usize) usize
参数
slot_count: usize
std.heap.debug_allocator.DebugAllocator.bucketStackTrace
函数
fn bucketStackTrace( bucket: *BucketHeader, slot_count: usize, slot_index: SlotIndex, trace_kind: TraceKind, ) StackTrace
参数
std.heap.debug_allocator.DebugAllocator.calculateSlotCount
函数
仅在编译期执行,用于预先填充查找表。
fn calculateSlotCount(size_class_index: usize) SlotIndex
参数
size_class_index: usize
std.heap.debug_allocator.DebugAllocator.collectStackTrace
函数
fn collectStackTrace(first_trace_addr: usize, addr_buf: *[stack_n]usize) void
参数
first_trace_addr: usize
addr_buf: *[stack_n]usize
std.heap.debug_allocator.DebugAllocator.deinit
函数
若存在泄漏,则返回 std.heap.Check.leak;否则返回 std.heap.Check.ok。
pub fn deinit(self: *Self) std.heap.Check
参数
self: *Self
std.heap.debug_allocator.DebugAllocator.deinitWithoutLeakChecks
函数
类似 deinit,但不检查内存泄漏。若已通过 detectLeaks
手动检测泄漏,可用此函数避免重复报告。
pub fn deinitWithoutLeakChecks(self: *Self) void
参数
self: *Self
std.heap.debug_allocator.DebugAllocator.detectLeaks
函数
为泄漏输出日志消息,然后返回检测到的泄漏数;未检测到泄漏则返回 0。
pub fn detectLeaks(self: *Self) usize
参数
self: *Self
std.heap.debug_allocator.DebugAllocator.detectLeaksInBucket
函数
fn detectLeaksInBucket( bucket: *BucketHeader, size_class_index: usize, used_bits_count: usize, ) usize
参数
std.heap.debug_allocator.DebugAllocator.Error
别名
std.heap.debug_allocator.DebugAllocator.flushRetainedMetadata
函数
pub fn flushRetainedMetadata(self: *Self) void
参数
self: *Self
std.heap.debug_allocator.DebugAllocator.free
函数
fn free( context: *anyopaque, old_memory: []u8, alignment: mem.Alignment, return_address: usize, ) void
参数
std.heap.debug_allocator.DebugAllocator.freeLarge
函数
无论参数如何,此函数均假定对象位于 大对象存储区中。
fn freeLarge( self: *Self, old_mem: []u8, alignment: mem.Alignment, ret_addr: usize, ) void
参数
std.heap.debug_allocator.DebugAllocator.freeRetainedMetadata
函数
fn freeRetainedMetadata(self: *Self) void
参数
self: *Self
std.heap.debug_allocator.DebugAllocator.have_mutex
常量
std.heap.debug_allocator.DebugAllocator.init
常量
Self
std.heap.debug_allocator.DebugAllocator.LargeAlloc
容器
字段
std.heap.debug_allocator.DebugAllocator.LargeAlloc.captureStackTrace
函数
fn captureStackTrace(self: *LargeAlloc, ret_addr: usize, trace_kind: TraceKind) void
参数
std.heap.debug_allocator.DebugAllocator.LargeAlloc.dumpStackTrace
函数
fn dumpStackTrace(self: *LargeAlloc, trace_kind: TraceKind) void
参数
self: *LargeAlloc
trace_kind: TraceKind
std.heap.debug_allocator.DebugAllocator.LargeAlloc.getStackTrace
函数
fn getStackTrace(self: *LargeAlloc, trace_kind: TraceKind) std.debug.StackTrace
参数
self: *LargeAlloc
trace_kind: TraceKind
std.heap.debug_allocator.DebugAllocator.LargeAlloc.trace_n
常量
std.heap.debug_allocator.DebugAllocator.LargeAllocTable
类型
std.heap.debug_allocator.DebugAllocator.largest_bucket_object_size
常量
std.heap.debug_allocator.DebugAllocator.LargestSizeClassInt
类型
std.heap.debug_allocator.DebugAllocator.minimum_slots_per_bucket_log2
常量
避免创建只能存储少量槽的桶。值为 1 表示最小槽数为 2。
std.heap.debug_allocator.DebugAllocator.mutex_init
常量
std.heap.debug_allocator.DebugAllocator.one_trace_size
常量
std.heap.debug_allocator.DebugAllocator.page_align
常量
mem.Alignment
std.heap.debug_allocator.DebugAllocator.page_size
常量
std.heap.debug_allocator.DebugAllocator.remap
函数
fn remap( context: *anyopaque, memory: []u8, alignment: mem.Alignment, new_len: usize, return_address: usize, ) ?[*]u8
参数
std.heap.debug_allocator.DebugAllocator.reportDoubleFree
函数
fn reportDoubleFree(ret_addr: usize, alloc_stack_trace: StackTrace, free_stack_trace: StackTrace) void
参数
std.heap.debug_allocator.DebugAllocator.requested_memory_limit_init
常量
std.heap.debug_allocator.DebugAllocator.resize
函数
fn resize( context: *anyopaque, memory: []u8, alignment: mem.Alignment, new_len: usize, return_address: usize, ) bool
参数
std.heap.debug_allocator.DebugAllocator.resizeLarge
函数
无论参数如何,此函数均假定对象位于 大对象存储区中。
fn resizeLarge( self: *Self, old_mem: []u8, alignment: mem.Alignment, new_size: usize, ret_addr: usize, may_move: bool, ) ?[*]u8
参数
std.heap.debug_allocator.DebugAllocator.resizeSmall
函数
fn resizeSmall( self: *Self, memory: []u8, alignment: mem.Alignment, new_len: usize, return_address: usize, size_class_index: usize, ) bool
参数
std.heap.debug_allocator.DebugAllocator.Self
别名
std.heap.debug_allocator.DebugAllocator.slot_counts
常量
这些值可根据 size_class_index 推导,但计算较复杂。
[small_bucket_count]SlotIndex
std.heap.debug_allocator.DebugAllocator.SlotIndex
常量
用于指向小型分配中槽位的整数类型
std.heap.debug_allocator.DebugAllocator.small_bucket_count
常量
std.heap.debug_allocator.DebugAllocator.stack_n
常量
std.heap.debug_allocator.DebugAllocator.total_requested_bytes_init
常量
std.heap.debug_allocator.DebugAllocator.traces_per_slot
常量
std.heap.debug_allocator.DebugAllocator.usedBitsCount
函数
fn usedBitsCount(slot_count: usize) usize
参数
slot_count: usize
std.heap.debug_allocator.DebugAllocator.usedBitsSize
函数
fn usedBitsSize(slot_count: usize) usize
参数
slot_count: usize
std.heap.debug_allocator.default_page_size
常量
usize
std.heap.debug_allocator.default_stack_trace_frames
常量
usize
std.heap.debug_allocator.default_sys_stack_trace_frames
常量
usize
std.heap.debug_allocator.log
类型
std.heap.debug_allocator.Log2USize
类型
std.heap.debug_allocator.math
别名
别名目标 std.math
std.heap.debug_allocator.mem
别名
别名目标 std.mem
std.heap.debug_allocator.StackTrace
别名
别名目标 std.debug.StackTrace
std.heap.debug_allocator.std
别名
别名目标 std
std.heap.debug_allocator.test_config
常量
Config
std.heap.debug_allocator.TraceKind
容器
字段
alloc
free
源码
std/heap/debug_allocator.zig
//! 面向 Debug 模式的分配器。
//!
//! ## 特性
//!
//! * 在分配、释放时捕获栈回溯,也可选择在调整大小时捕获。
//! * 检测重复释放,并输出三次操作的全部回溯(首次分配、首次
//! 释放、再次释放)。
//! * 检测内存泄漏,并附带栈回溯。
//! * 从不复用内存地址,使 Zig 更容易检测悬空指针导致的
//! 基于未定义值的分支。这也要求
//! 底层分配器不复用地址。
//! * 为底层分配设置最小大小,避免活跃内存映射过多
//! 导致操作系统错误。
//! * 内存页不再需要时,尽快归还其驻留
//! 内存,以便后续访问触发缺页异常。
//! * 跨平台。通过底层分配器工作,因此可在
//! 任何环境中使用,包括独立式环境。
//! * 支持编译期配置。
//!
//! 这些特性使该分配器速度较慢,且空间开销较大。例如,
//! 分配单个字节时,空间利用率不到 1%;
//! 管理这一字节的分配需要超过 100 字节的
//! 额外开销。分配大小越大,利用率越高。
//!
//! ## 基本设计
//!
//! 分配分为小型和大型两类。
//!
//! 小型分配根据 `page_size` 划分到不同的桶中:
//!
//! ```
//! index obj_size
//! 0 1
//! 1 2
//! 2 4
//! 3 8
//! 4 16
//! 5 32
//! 6 64
//! 7 128
//! 8 256
//! 9 512
//! 10 1024
//! 11 2048
//! ...
//! ```
//!
//! 索引按此规律延续,共有 `small_bucket_count` 个。
//!
//! 按 max(len, alignment) 将分配归入对象大小类别,
//! 并向上取整到下一个二的幂。
//!
//! 分配器的主要状态包含一个数组,保存每种
//! 大小类别的全部“当前”桶。数组中每个槽位可以为 null,表示该
//! 类别尚未分配桶。首次为某一类别
//! 分配对象时,从底层分配器分配一块大小为 `page_size` 的内存。
//! 此分配划分为多个“槽位”,每个槽位对应一个已分配对象,同时预留
//! 分配元数据的空间(以 `BucketHeader` 开头),元数据
//! 位于该“页”的最末尾。
//!
//! 分配元数据包含“使用位”:每个槽位用一位表示
//! 是否已使用。分配始终使用当前桶的下一个空闲
//! 槽位,设置相应的使用位,
//! 并递增 `allocated_count`。
//!
//! 释放时,根据地址、长度和
//! 对齐恢复分配元数据;这依赖底层分配具有较大的对齐,
//! 同时依赖分配不会从小型转为大型,
//! 也不会从大型转为小型。
//!
//! 桶满后会分配新桶,其中保存指向
//! 前一个桶的指针。泄漏检测会遍历此双向链表。
//!
//! 对小型分配而言,调整大小和重新映射的处理方式相同:若大小
//! 类别不变,则操作成功且地址
//! 不变;否则拒绝请求。
//!
//! 大型对象直接使用底层分配器分配。元数据
//! 单独保存在同样使用底层分配器的 `std.HashMap` 中。
//!
//! 调整大小和重新映射直接转发给底层分配器,
//! 但会使分配从大型变为小型的操作除外。
const builtin = @import("builtin");
const StackTrace = std.debug.StackTrace;
const std = @import("std");
const log = std.log.scoped(.DebugAllocator);
const math = std.math;
const assert = std.debug.assert;
const mem = std.mem;
const Allocator = std.mem.Allocator;
const default_page_size: usize = switch (builtin.os.tag) {
// 使 `std.heap.PageAllocator` 走正常成功路径。
.windows => 64 * 1024,
else => switch (builtin.cpu.arch) {
// `std.heap.WasmAllocator` 支持的最大对齐值。
.wasm32, .wasm64 => 64 * 1024,
// `page_size_max` 较小时,避免活动映射过多。
else => @max(std.heap.page_size_max, 128 * 1024),
},
};
const Log2USize = std.math.Log2Int(usize);
const default_sys_stack_trace_frames: usize = if (std.debug.sys_can_stack_trace) 6 else 0;
const default_stack_trace_frames: usize = switch (builtin.mode) {
.debug => default_sys_stack_trace_frames,
else => 0,
};
pub const Config = struct {
/// 要捕获的栈帧数量。
stack_trace_frames: usize = default_stack_trace_frames,
/// 若为 true,分配器将包含两个字段:
/// * `total_requested_bytes`:跟踪所请求分配的总内存字节数。
/// * `requested_memory_limit`:当 `total_requested_bytes` 超过此限制时,
/// 使分配返回 `error.OutOfMemory`。
/// 若为 false,这些字段的类型为 `void`。
enable_memory_limit: bool = false,
/// 是否启用安全检查。
safety: bool = std.debug.runtime_safety,
/// 是否允许多个线程同时使用该分配器。
thread_safe: bool = !builtin.single_threaded,
/// 这是一种临时调试技巧,可将段错误变为更有帮助的
/// 日志错误消息,并附带详细栈跟踪。缺点是每次分配
/// 都会泄漏,除非配合 retain_metadata 使用!
never_unmap: bool = false,
/// 临时调试辅助功能,无限期保留分配元数据,
/// 以报告更多种类的重复释放。调用 deinit 时释放全部元数据。
/// 与 never_unmap 一起使用时,有意泄漏的内存也会
/// 在 deinit 时释放。目前应搭配 never_unmap,避免段错误。
/// TODO: https://github.com/ziglang/zig/issues/4298 将允许不搭配 never_unmap 使用。
retain_metadata: bool = false,
/// 启用信息消息输出,报告每次分配的大小和地址。
verbose_log: bool = false,
/// 说明后备分配器是否返回已经清零的内存。
backing_allocator_zeroes: bool = true,
/// 调整已分配内存大小时,使用 resize 调用位置
/// 刷新栈跟踪。这会带来性能开销。
resize_stack_traces: bool = false,
/// 用于区分此分配器拥有的分配与
/// 其他内存区域的魔数。
canary: usize = @truncate(0x9232a6ff85dff10f),
/// 从底层分配器请求的分配大小,用于进一步细分为
/// 小型分配的槽位。
///
/// 必须为 2 的幂。
page_size: usize = default_page_size,
};
/// 此结构体的默认初始化方式已弃用;请改用 `.init`。
pub fn DebugAllocator(comptime config: Config) type {
return struct {
backing_allocator: Allocator = std.heap.page_allocator,
/// 跟踪活动桶,即包含空闲槽位的桶。
buckets: [small_bucket_count]?*BucketHeader = @splat(null),
large_allocations: LargeAllocTable = .empty,
total_requested_bytes: @TypeOf(total_requested_bytes_init) = total_requested_bytes_init,
requested_memory_limit: @TypeOf(requested_memory_limit_init) = requested_memory_limit_init,
mutex: @TypeOf(mutex_init) = mutex_init,
const Self = @This();
pub const init: Self = .{};
/// 这些值可根据 size_class_index 推导,但计算较复杂。
const slot_counts: [small_bucket_count]SlotIndex = init: {
@setEvalBranchQuota(10000);
var result: [small_bucket_count]SlotIndex = undefined;
for (&result, 0..) |*elem, i| elem.* = calculateSlotCount(i);
break :init result;
};
comptime {
assert(math.isPowerOfTwo(page_size));
}
const page_size = config.page_size;
const page_align: mem.Alignment = .fromByteUnits(page_size);
/// 用于指向小型分配中槽位的整数类型
const SlotIndex = @Int(.unsigned, math.log2(page_size) + 1);
const total_requested_bytes_init = if (config.enable_memory_limit) @as(usize, 0) else {};
const requested_memory_limit_init = if (config.enable_memory_limit) @as(usize, math.maxInt(usize)) else {};
const have_mutex = config.thread_safe;
const mutex_init = if (have_mutex) std.Io.Mutex.init else {};
const stack_n = config.stack_trace_frames;
const one_trace_size = @sizeOf(usize) * stack_n;
const traces_per_slot = 2;
pub const Error = mem.Allocator.Error;
/// 避免创建只能存储少量槽的桶。值为 1 表示最小槽数为 2。
///
const minimum_slots_per_bucket_log2 = 1;
const small_bucket_count = math.log2(page_size) - minimum_slots_per_bucket_log2;
const largest_bucket_object_size = 1 << (small_bucket_count - 1);
const LargestSizeClassInt = std.math.IntFittingRange(0, largest_bucket_object_size);
const bucketCompare = struct {
fn compare(a: *BucketHeader, b: *BucketHeader) std.math.Order {
return std.math.order(@intFromPtr(a.page), @intFromPtr(b.page));
}
}.compare;
const LargeAlloc = struct {
bytes: []u8,
requested_size: if (config.enable_memory_limit) usize else void,
stack_addresses: [trace_n][stack_n]usize,
freed: if (config.retain_metadata) bool else void,
alignment: if (config.never_unmap and config.retain_metadata) mem.Alignment else void,
const trace_n = if (config.retain_metadata) traces_per_slot else 1;
fn dumpStackTrace(self: *LargeAlloc, trace_kind: TraceKind) void {
std.debug.dumpStackTrace(self.getStackTrace(trace_kind));
}
fn getStackTrace(self: *LargeAlloc, trace_kind: TraceKind) std.debug.StackTrace {
assert(@backingInt(trace_kind) < trace_n);
const stack_addresses = &self.stack_addresses[@backingInt(trace_kind)];
var len: usize = 0;
while (len < stack_n and stack_addresses[len] != 0) {
len += 1;
}
return .{
.return_addresses = stack_addresses[0..len],
.skipped = if (len < stack_addresses.len) .none else .unknown,
};
}
fn captureStackTrace(self: *LargeAlloc, ret_addr: usize, trace_kind: TraceKind) void {
assert(@backingInt(trace_kind) < trace_n);
const stack_addresses = &self.stack_addresses[@backingInt(trace_kind)];
collectStackTrace(ret_addr, stack_addresses);
}
};
const LargeAllocTable = std.AutoHashMapUnmanaged(usize, LargeAlloc);
/// 桶在内存中的顺序如下:
/// * BucketHeader
/// * bucket_used_bits: [N]usize, // 每个槽位一位
/// -- 以下仅在 config.safety 为 true 时存在 --
/// * requested_sizes: [N]LargestSizeClassInt // 每个槽位一个整数
/// * log2_ptr_aligns: [N]u8 // 每个槽位一个字节
/// -- 以上仅在 config.safety 为 true 时存在 --
/// * stack_trace_addresses: [N]usize, // 每次分配保存 traces_per_slot 个地址
const BucketHeader = struct {
allocated_count: SlotIndex,
freed_count: SlotIndex,
prev: ?*BucketHeader,
next: ?*BucketHeader,
canary: usize = config.canary,
fn fromPage(page_addr: usize, slot_count: usize) *BucketHeader {
const unaligned = page_addr +% page_size -% bucketSize(slot_count);
return @ptrFromInt(unaligned & ~(@as(usize, @alignOf(BucketHeader)) - 1));
}
fn usedBits(bucket: *BucketHeader, index: usize) *usize {
const ptr: [*]u8 = @ptrCast(bucket);
const bits: [*]usize = @ptrCast(@alignCast(ptr + @sizeOf(BucketHeader)));
return &bits[index];
}
fn requestedSizes(bucket: *BucketHeader, slot_count: usize) []LargestSizeClassInt {
if (!config.safety) @compileError("requested size is only stored when safety is enabled");
const start_ptr = @as([*]u8, @ptrCast(bucket)) + bucketRequestedSizesStart(slot_count);
const sizes = @as([*]LargestSizeClassInt, @ptrCast(@alignCast(start_ptr)));
return sizes[0..slot_count];
}
fn log2PtrAligns(bucket: *BucketHeader, slot_count: usize) []mem.Alignment {
if (!config.safety) @compileError("requested size is only stored when safety is enabled");
const aligns_ptr = @as([*]u8, @ptrCast(bucket)) + bucketAlignsStart(slot_count);
return @ptrCast(aligns_ptr[0..slot_count]);
}
fn stackTracePtr(
bucket: *BucketHeader,
slot_count: usize,
slot_index: SlotIndex,
trace_kind: TraceKind,
) *[stack_n]usize {
const start_ptr = @as([*]u8, @ptrCast(bucket)) + bucketStackFramesStart(slot_count);
const addr = start_ptr + one_trace_size * traces_per_slot * slot_index +
@backingInt(trace_kind) * @as(usize, one_trace_size);
return @ptrCast(@alignCast(addr));
}
fn captureStackTrace(
bucket: *BucketHeader,
ret_addr: usize,
slot_count: usize,
slot_index: SlotIndex,
trace_kind: TraceKind,
) void {
// 将它们初始化为 0。确定计数时,必须查找非零地址。
//
const stack_addresses = bucket.stackTracePtr(slot_count, slot_index, trace_kind);
collectStackTrace(ret_addr, stack_addresses);
}
};
pub fn allocator(self: *Self) Allocator {
return .{
.ptr = self,
.vtable = &.{
.alloc = alloc,
.resize = resize,
.remap = remap,
.free = free,
},
};
}
fn bucketStackTrace(
bucket: *BucketHeader,
slot_count: usize,
slot_index: SlotIndex,
trace_kind: TraceKind,
) StackTrace {
const stack_addresses = bucket.stackTracePtr(slot_count, slot_index, trace_kind);
var len: usize = 0;
while (len < stack_n and stack_addresses[len] != 0) {
len += 1;
}
return .{
.return_addresses = stack_addresses[0..len],
.skipped = if (len < stack_addresses.len) .none else .unknown,
};
}
fn bucketRequestedSizesStart(slot_count: usize) usize {
if (!config.safety) @compileError("requested sizes are not stored unless safety is enabled");
return mem.alignForward(
usize,
@sizeOf(BucketHeader) + usedBitsSize(slot_count),
@alignOf(LargestSizeClassInt),
);
}
fn bucketAlignsStart(slot_count: usize) usize {
if (!config.safety) @compileError("requested sizes are not stored unless safety is enabled");
return bucketRequestedSizesStart(slot_count) + (@sizeOf(LargestSizeClassInt) * slot_count);
}
fn bucketStackFramesStart(slot_count: usize) usize {
const unaligned_start = if (config.safety)
bucketAlignsStart(slot_count) + slot_count
else
@sizeOf(BucketHeader) + usedBitsSize(slot_count);
return mem.alignForward(usize, unaligned_start, @alignOf(usize));
}
fn bucketSize(slot_count: usize) usize {
return bucketStackFramesStart(slot_count) + one_trace_size * traces_per_slot * slot_count;
}
/// 仅在编译期执行,用于预先填充查找表。
fn calculateSlotCount(size_class_index: usize) SlotIndex {
const size_class = @as(usize, 1) << @as(Log2USize, @intCast(size_class_index));
var lower: usize = 1 << minimum_slots_per_bucket_log2;
var upper: usize = (page_size - bucketSize(lower)) / size_class;
while (upper > lower) {
const proposed: usize = lower + (upper - lower) / 2;
if (proposed == lower) return lower;
const slots_end = proposed * size_class;
const header_begin = mem.alignForward(usize, slots_end, @alignOf(BucketHeader));
const end = header_begin + bucketSize(proposed);
if (end > page_size) {
upper = proposed - 1;
} else {
lower = proposed;
}
}
const slots_end = lower * size_class;
const header_begin = mem.alignForward(usize, slots_end, @alignOf(BucketHeader));
const end = header_begin + bucketSize(lower);
assert(end <= page_size);
return lower;
}
fn usedBitsCount(slot_count: usize) usize {
return (slot_count + (@bitSizeOf(usize) - 1)) / @bitSizeOf(usize);
}
fn usedBitsSize(slot_count: usize) usize {
return usedBitsCount(slot_count) * @sizeOf(usize);
}
fn detectLeaksInBucket(
bucket: *BucketHeader,
size_class_index: usize,
used_bits_count: usize,
) usize {
const size_class = @as(usize, 1) << @as(Log2USize, @intCast(size_class_index));
const slot_count = slot_counts[size_class_index];
var leaks: usize = 0;
for (0..used_bits_count) |used_bits_byte| {
const used_int = bucket.usedBits(used_bits_byte).*;
if (used_int != 0) {
for (0..@bitSizeOf(usize)) |bit_index_usize| {
const bit_index: Log2USize = @intCast(bit_index_usize);
const is_used = @as(u1, @truncate(used_int >> bit_index)) != 0;
if (is_used) {
const slot_index: SlotIndex = @intCast(used_bits_byte * @bitSizeOf(usize) + bit_index);
const stack_trace = bucketStackTrace(bucket, slot_count, slot_index, .alloc);
const page_addr = @intFromPtr(bucket) & ~(page_size - 1);
const addr = page_addr + slot_index * size_class;
log.err("memory address 0x{x} leaked: {f}", .{
addr,
std.debug.FormatStackTrace{
.stack_trace = stack_trace,
.terminal_mode = std.log.terminalMode(),
},
});
leaks += 1;
}
}
}
}
return leaks;
}
/// 为泄漏输出日志消息,然后返回检测到的泄漏数;未检测到泄漏则返回 0。
pub fn detectLeaks(self: *Self) usize {
var leaks: usize = 0;
for (self.buckets, 0..) |init_optional_bucket, size_class_index| {
var optional_bucket = init_optional_bucket;
const slot_count = slot_counts[size_class_index];
const used_bits_count = usedBitsCount(slot_count);
while (optional_bucket) |bucket| {
leaks += detectLeaksInBucket(bucket, size_class_index, used_bits_count);
optional_bucket = bucket.prev;
}
}
var it = self.large_allocations.valueIterator();
while (it.next()) |large_alloc| {
if (config.retain_metadata and large_alloc.freed) continue;
const stack_trace = large_alloc.getStackTrace(.alloc);
log.err("memory address 0x{x} leaked: {f}", .{
@intFromPtr(large_alloc.bytes.ptr),
std.debug.FormatStackTrace{
.stack_trace = stack_trace,
.terminal_mode = std.log.terminalMode(),
},
});
leaks += 1;
}
return leaks;
}
fn freeRetainedMetadata(self: *Self) void {
comptime assert(config.retain_metadata);
if (config.never_unmap) {
// 释放 never_unmap 有意泄漏的大型分配。
var it = self.large_allocations.iterator();
while (it.next()) |large| {
if (large.value_ptr.freed) {
self.backing_allocator.rawFree(large.value_ptr.bytes, large.value_ptr.alignment, @returnAddress());
}
}
}
}
pub fn flushRetainedMetadata(self: *Self) void {
comptime assert(config.retain_metadata);
self.freeRetainedMetadata();
// 同时从 large_allocations 移除条目
var it = self.large_allocations.iterator();
while (it.next()) |large| {
if (large.value_ptr.freed) {
_ = self.large_allocations.remove(@intFromPtr(large.value_ptr.bytes.ptr));
}
}
}
/// 若存在泄漏,则返回 `std.heap.Check.leak`;否则返回 `std.heap.Check.ok`。
pub fn deinit(self: *Self) std.heap.Check {
const leaks: usize = if (config.safety) self.detectLeaks() else 0;
self.deinitWithoutLeakChecks();
return if (leaks == 0) .ok else .leak;
}
/// 类似 `deinit`,但不检查内存泄漏。若已通过 `detectLeaks`
/// 手动检测泄漏,可用此函数避免重复报告。
pub fn deinitWithoutLeakChecks(self: *Self) void {
if (config.retain_metadata) self.freeRetainedMetadata();
self.large_allocations.deinit(self.backing_allocator);
self.* = undefined;
}
fn collectStackTrace(first_trace_addr: usize, addr_buf: *[stack_n]usize) void {
const st = std.debug.captureCurrentStackTrace(.{ .first_address = first_trace_addr }, addr_buf);
@memset(addr_buf[@min(st.return_addresses.len, addr_buf.len)..], 0);
}
fn reportDoubleFree(ret_addr: usize, alloc_stack_trace: StackTrace, free_stack_trace: StackTrace) void {
@branchHint(.cold);
var addr_buf: [stack_n]usize = undefined;
const second_free_stack_trace = std.debug.captureCurrentStackTrace(.{ .first_address = ret_addr }, &addr_buf);
log.err("Double free detected. Allocation: {f} First free: {f} Second free: {f}", .{
std.debug.FormatStackTrace{
.stack_trace = alloc_stack_trace,
.terminal_mode = std.log.terminalMode(),
},
std.debug.FormatStackTrace{
.stack_trace = free_stack_trace,
.terminal_mode = std.log.terminalMode(),
},
std.debug.FormatStackTrace{
.stack_trace = second_free_stack_trace,
.terminal_mode = std.log.terminalMode(),
},
});
}
/// 无论参数如何,此函数均假定对象位于
/// 大对象存储区中。
fn resizeLarge(
self: *Self,
old_mem: []u8,
alignment: mem.Alignment,
new_size: usize,
ret_addr: usize,
may_move: bool,
) ?[*]u8 {
if (config.retain_metadata and may_move) {
// 必须在查找条目之前为新条目预留空间
// (因为预留操作可能使条目失效),
// 以防分配的内存被迁移。
self.large_allocations.ensureUnusedCapacity(self.backing_allocator, 1) catch return null;
}
const entry = self.large_allocations.getEntry(@intFromPtr(old_mem.ptr)) orelse {
if (config.safety) {
@panic("Invalid free");
} else {
unreachable;
}
};
if (config.retain_metadata and entry.value_ptr.freed) {
if (config.safety) {
reportDoubleFree(ret_addr, entry.value_ptr.getStackTrace(.alloc), entry.value_ptr.getStackTrace(.free));
@panic("Unrecoverable double free");
} else {
unreachable;
}
}
if (config.safety and old_mem.len != entry.value_ptr.bytes.len) {
@branchHint(.cold);
var addr_buf: [stack_n]usize = undefined;
const free_stack_trace = std.debug.captureCurrentStackTrace(.{ .first_address = ret_addr }, &addr_buf);
log.err("Allocation size {d} bytes does not match free size {d}. Allocation: {f} Free: {f}", .{
entry.value_ptr.bytes.len,
old_mem.len,
std.debug.FormatStackTrace{
.stack_trace = entry.value_ptr.getStackTrace(.alloc),
.terminal_mode = std.log.terminalMode(),
},
std.debug.FormatStackTrace{
.stack_trace = free_stack_trace,
.terminal_mode = std.log.terminalMode(),
},
});
}
// 若此操作会将分配移入小型大小类别,则拒绝请求,因为这将需要创建小型分配元数据。
//
//
const new_size_class_index: usize = @max(@bitSizeOf(usize) - @clz(new_size - 1), @backingInt(alignment));
if (new_size_class_index < self.buckets.len) return null;
// 按请求大小而非 backing_allocator 返回的大小核算内存限制,
// 因为若要返回 error.OutOfMemory,就必须保证分配未被修改,
// 而调用 backing_allocator.rawResize 之后无法保证这一点。
//
//
const prev_req_bytes = self.total_requested_bytes;
if (config.enable_memory_limit) {
const new_req_bytes = prev_req_bytes + new_size - entry.value_ptr.requested_size;
if (new_req_bytes > prev_req_bytes and new_req_bytes > self.requested_memory_limit) {
return null;
}
self.total_requested_bytes = new_req_bytes;
}
const opt_resized_ptr = if (may_move)
self.backing_allocator.rawRemap(old_mem, alignment, new_size, ret_addr)
else if (self.backing_allocator.rawResize(old_mem, alignment, new_size, ret_addr))
old_mem.ptr
else
null;
const resized_ptr = opt_resized_ptr orelse {
if (config.enable_memory_limit) {
self.total_requested_bytes = prev_req_bytes;
}
return null;
};
if (config.enable_memory_limit) {
entry.value_ptr.requested_size = new_size;
}
if (config.verbose_log) {
log.info("large resize {d} bytes at {*} to {d} at {*}", .{
old_mem.len, old_mem.ptr, new_size, resized_ptr,
});
}
entry.value_ptr.bytes = resized_ptr[0..new_size];
if (config.resize_stack_traces)
entry.value_ptr.captureStackTrace(ret_addr, .alloc);
// 若内存发生重定位,则更新哈希映射中的键。
if (resized_ptr != old_mem.ptr) {
const large_alloc = entry.value_ptr.*;
if (config.retain_metadata) {
entry.value_ptr.freed = true;
entry.value_ptr.captureStackTrace(ret_addr, .free);
} else {
self.large_allocations.removeByPtr(entry.key_ptr);
}
const gop = self.large_allocations.getOrPutAssumeCapacity(@intFromPtr(resized_ptr));
if (config.retain_metadata and !config.never_unmap) {
// 底层分配器可能复用仍保留有元数据的内存
assert(!gop.found_existing or gop.value_ptr.freed);
} else {
assert(!gop.found_existing); // 这意味着内核对页面进行了双重映射。
}
gop.value_ptr.* = large_alloc;
}
return resized_ptr;
}
/// 无论参数如何,此函数均假定对象位于
/// 大对象存储区中。
fn freeLarge(
self: *Self,
old_mem: []u8,
alignment: mem.Alignment,
ret_addr: usize,
) void {
const entry = self.large_allocations.getEntry(@intFromPtr(old_mem.ptr)) orelse {
if (config.safety) {
@panic("Invalid free");
} else {
unreachable;
}
};
if (config.retain_metadata and entry.value_ptr.freed) {
if (config.safety) {
reportDoubleFree(ret_addr, entry.value_ptr.getStackTrace(.alloc), entry.value_ptr.getStackTrace(.free));
return;
} else {
unreachable;
}
}
if (config.safety and old_mem.len != entry.value_ptr.bytes.len) {
@branchHint(.cold);
var addr_buf: [stack_n]usize = undefined;
const free_stack_trace = std.debug.captureCurrentStackTrace(.{ .first_address = ret_addr }, &addr_buf);
log.err("Allocation size {d} bytes does not match free size {d}. Allocation: {f} Free: {f}", .{
entry.value_ptr.bytes.len,
old_mem.len,
std.debug.FormatStackTrace{
.stack_trace = entry.value_ptr.getStackTrace(.alloc),
.terminal_mode = std.log.terminalMode(),
},
std.debug.FormatStackTrace{
.stack_trace = free_stack_trace,
.terminal_mode = std.log.terminalMode(),
},
});
}
if (!config.never_unmap) {
self.backing_allocator.rawFree(old_mem, alignment, ret_addr);
}
if (config.enable_memory_limit) {
self.total_requested_bytes -= entry.value_ptr.requested_size;
}
if (config.verbose_log) {
log.info("large free {d} bytes at {*}", .{ old_mem.len, old_mem.ptr });
}
if (!config.retain_metadata) {
assert(self.large_allocations.remove(@intFromPtr(old_mem.ptr)));
} else {
entry.value_ptr.freed = true;
entry.value_ptr.captureStackTrace(ret_addr, .free);
}
}
fn alloc(context: *anyopaque, len: usize, alignment: mem.Alignment, ret_addr: usize) ?[*]u8 {
const self: *Self = @ptrCast(@alignCast(context));
if (have_mutex) std.Io.Threaded.mutexLockUncancelable(&self.mutex);
defer if (have_mutex) std.Io.Threaded.mutexUnlock(&self.mutex);
if (config.enable_memory_limit) {
const new_req_bytes = self.total_requested_bytes + len;
if (new_req_bytes > self.requested_memory_limit) return null;
self.total_requested_bytes = new_req_bytes;
}
const size_class_index: usize = @max(@bitSizeOf(usize) - @clz(len - 1), @backingInt(alignment));
if (size_class_index >= self.buckets.len) {
@branchHint(.unlikely);
self.large_allocations.ensureUnusedCapacity(self.backing_allocator, 1) catch return null;
const ptr = self.backing_allocator.rawAlloc(len, alignment, ret_addr) orelse return null;
const slice = ptr[0..len];
const gop = self.large_allocations.getOrPutAssumeCapacity(@intFromPtr(slice.ptr));
if (config.retain_metadata and !config.never_unmap) {
// 底层分配器可能复用仍保留有元数据的内存
assert(!gop.found_existing or gop.value_ptr.freed);
} else {
assert(!gop.found_existing); // 这意味着内核对页面进行了双重映射。
}
gop.value_ptr.bytes = slice;
if (config.enable_memory_limit)
gop.value_ptr.requested_size = len;
gop.value_ptr.captureStackTrace(ret_addr, .alloc);
if (config.retain_metadata) {
gop.value_ptr.freed = false;
if (config.never_unmap) {
gop.value_ptr.alignment = alignment;
}
}
if (config.verbose_log) {
log.info("large alloc {d} bytes at {*}", .{ slice.len, slice.ptr });
}
return slice.ptr;
}
const slot_count = slot_counts[size_class_index];
if (self.buckets[size_class_index]) |bucket| {
@branchHint(.likely);
const slot_index = bucket.allocated_count;
if (slot_index < slot_count) {
@branchHint(.likely);
bucket.allocated_count = slot_index + 1;
const used_bits_byte = bucket.usedBits(slot_index / @bitSizeOf(usize));
const used_bit_index: Log2USize = @intCast(slot_index % @bitSizeOf(usize));
used_bits_byte.* |= (@as(usize, 1) << used_bit_index);
const size_class = @as(usize, 1) << @as(Log2USize, @intCast(size_class_index));
if (config.stack_trace_frames > 0) {
bucket.captureStackTrace(ret_addr, slot_count, slot_index, .alloc);
}
if (config.safety) {
bucket.requestedSizes(slot_count)[slot_index] = @intCast(len);
bucket.log2PtrAligns(slot_count)[slot_index] = alignment;
}
const page_addr = @intFromPtr(bucket) & ~(page_size - 1);
const addr = page_addr + slot_index * size_class;
if (config.verbose_log) {
log.info("small alloc {d} bytes at 0x{x}", .{ len, addr });
}
return @ptrFromInt(addr);
}
}
const page = self.backing_allocator.rawAlloc(page_size, page_align, @returnAddress()) orelse
return null;
const bucket: *BucketHeader = .fromPage(@intFromPtr(page), slot_count);
bucket.* = .{
.allocated_count = 1,
.freed_count = 0,
.prev = self.buckets[size_class_index],
.next = null,
};
if (self.buckets[size_class_index]) |old_head| {
old_head.next = bucket;
}
self.buckets[size_class_index] = bucket;
if (!config.backing_allocator_zeroes) {
@memset(@as([*]usize, @as(*[1]usize, bucket.usedBits(0)))[0..usedBitsCount(slot_count)], 0);
if (config.safety) @memset(bucket.requestedSizes(slot_count), 0);
}
bucket.usedBits(0).* = 0b1;
if (config.stack_trace_frames > 0) {
bucket.captureStackTrace(ret_addr, slot_count, 0, .alloc);
}
if (config.safety) {
bucket.requestedSizes(slot_count)[0] = @intCast(len);
bucket.log2PtrAligns(slot_count)[0] = alignment;
}
if (config.verbose_log) {
log.info("small alloc {d} bytes at 0x{x}", .{ len, @intFromPtr(page) });
}
return page;
}
fn resize(
context: *anyopaque,
memory: []u8,
alignment: mem.Alignment,
new_len: usize,
return_address: usize,
) bool {
const self: *Self = @ptrCast(@alignCast(context));
if (have_mutex) std.Io.Threaded.mutexLockUncancelable(&self.mutex);
defer if (have_mutex) std.Io.Threaded.mutexUnlock(&self.mutex);
const size_class_index: usize = @max(@bitSizeOf(usize) - @clz(memory.len - 1), @backingInt(alignment));
if (size_class_index >= self.buckets.len) {
return self.resizeLarge(memory, alignment, new_len, return_address, false) != null;
} else {
return resizeSmall(self, memory, alignment, new_len, return_address, size_class_index);
}
}
fn remap(
context: *anyopaque,
memory: []u8,
alignment: mem.Alignment,
new_len: usize,
return_address: usize,
) ?[*]u8 {
const self: *Self = @ptrCast(@alignCast(context));
if (have_mutex) std.Io.Threaded.mutexLockUncancelable(&self.mutex);
defer if (have_mutex) std.Io.Threaded.mutexUnlock(&self.mutex);
const size_class_index: usize = @max(@bitSizeOf(usize) - @clz(memory.len - 1), @backingInt(alignment));
if (size_class_index >= self.buckets.len) {
return self.resizeLarge(memory, alignment, new_len, return_address, true);
} else {
return if (resizeSmall(self, memory, alignment, new_len, return_address, size_class_index)) memory.ptr else null;
}
}
fn free(
context: *anyopaque,
old_memory: []u8,
alignment: mem.Alignment,
return_address: usize,
) void {
const self: *Self = @ptrCast(@alignCast(context));
if (have_mutex) std.Io.Threaded.mutexLockUncancelable(&self.mutex);
defer if (have_mutex) std.Io.Threaded.mutexUnlock(&self.mutex);
const size_class_index: usize = @max(@bitSizeOf(usize) - @clz(old_memory.len - 1), @backingInt(alignment));
if (size_class_index >= self.buckets.len) {
@branchHint(.unlikely);
self.freeLarge(old_memory, alignment, return_address);
return;
}
const slot_count = slot_counts[size_class_index];
const freed_addr = @intFromPtr(old_memory.ptr);
const page_addr = freed_addr & ~(page_size - 1);
const bucket: *BucketHeader = .fromPage(page_addr, slot_count);
if (bucket.canary != config.canary) @panic("Invalid free");
const page_offset = freed_addr - page_addr;
const size_class = @as(usize, 1) << @as(Log2USize, @intCast(size_class_index));
const slot_index: SlotIndex = @intCast(page_offset / size_class);
const used_byte_index = slot_index / @bitSizeOf(usize);
const used_bit_index: Log2USize = @intCast(slot_index % @bitSizeOf(usize));
const used_byte = bucket.usedBits(used_byte_index);
const is_used = @as(u1, @truncate(used_byte.* >> used_bit_index)) != 0;
if (!is_used) {
if (config.safety) {
reportDoubleFree(
return_address,
bucketStackTrace(bucket, slot_count, slot_index, .alloc),
bucketStackTrace(bucket, slot_count, slot_index, .free),
);
// 可以恢复,因为这是释放操作。
return;
} else {
unreachable;
}
}
// 现在确定是正在使用的小块分配。
if (config.safety) {
const requested_size = bucket.requestedSizes(slot_count)[slot_index];
if (requested_size == 0) @panic("Invalid free");
const slot_alignment = bucket.log2PtrAligns(slot_count)[slot_index];
if (old_memory.len != requested_size or alignment != slot_alignment) {
var addr_buf: [stack_n]usize = undefined;
const free_stack_trace = std.debug.captureCurrentStackTrace(.{ .first_address = return_address }, &addr_buf);
if (old_memory.len != requested_size) {
@branchHint(.cold);
log.err("Allocation size {d} bytes does not match free size {d}. Allocation: {f} Free: {f}", .{
requested_size,
old_memory.len,
std.debug.FormatStackTrace{
.stack_trace = bucketStackTrace(bucket, slot_count, slot_index, .alloc),
.terminal_mode = std.log.terminalMode(),
},
std.debug.FormatStackTrace{
.stack_trace = free_stack_trace,
.terminal_mode = std.log.terminalMode(),
},
});
}
if (alignment != slot_alignment) {
@branchHint(.cold);
log.err("Allocation alignment {d} does not match free alignment {d}. Allocation: {f} Free: {f}", .{
slot_alignment.toByteUnits(),
alignment.toByteUnits(),
std.debug.FormatStackTrace{
.stack_trace = bucketStackTrace(bucket, slot_count, slot_index, .alloc),
.terminal_mode = std.log.terminalMode(),
},
std.debug.FormatStackTrace{
.stack_trace = free_stack_trace,
.terminal_mode = std.log.terminalMode(),
},
});
}
}
}
if (config.enable_memory_limit) {
self.total_requested_bytes -= old_memory.len;
}
if (config.stack_trace_frames > 0) {
// 捕获栈追踪作为“首次释放”的记录,以备发生重复释放时使用。
bucket.captureStackTrace(return_address, slot_count, slot_index, .free);
}
used_byte.* &= ~(@as(usize, 1) << used_bit_index);
if (config.safety) {
bucket.requestedSizes(slot_count)[slot_index] = 0;
}
bucket.freed_count += 1;
if (bucket.freed_count == bucket.allocated_count) {
if (bucket.prev) |prev| {
prev.next = bucket.next;
}
if (bucket.next) |next| {
assert(self.buckets[size_class_index] != bucket);
next.prev = bucket.prev;
} else {
assert(self.buckets[size_class_index] == bucket);
self.buckets[size_class_index] = bucket.prev;
}
if (!config.never_unmap) {
const page: [*]align(page_size) u8 = @ptrFromInt(page_addr);
self.backing_allocator.rawFree(page[0..page_size], page_align, @returnAddress());
}
}
if (config.verbose_log) {
log.info("small free {d} bytes at {*}", .{ old_memory.len, old_memory.ptr });
}
}
fn resizeSmall(
self: *Self,
memory: []u8,
alignment: mem.Alignment,
new_len: usize,
return_address: usize,
size_class_index: usize,
) bool {
const new_size_class_index: usize = @max(@bitSizeOf(usize) - @clz(new_len - 1), @backingInt(alignment));
if (!config.safety) {
if (new_size_class_index != size_class_index) return false;
// 即使禁用安全检查,也要计入总数
if (config.enable_memory_limit)
self.total_requested_bytes = self.total_requested_bytes - memory.len + new_len;
return true;
}
const slot_count = slot_counts[size_class_index];
const memory_addr = @intFromPtr(memory.ptr);
const page_addr = memory_addr & ~(page_size - 1);
const bucket: *BucketHeader = .fromPage(page_addr, slot_count);
if (bucket.canary != config.canary) @panic("Invalid free");
const page_offset = memory_addr - page_addr;
const size_class = @as(usize, 1) << @as(Log2USize, @intCast(size_class_index));
const slot_index: SlotIndex = @intCast(page_offset / size_class);
const used_byte_index = slot_index / @bitSizeOf(usize);
const used_bit_index: Log2USize = @intCast(slot_index % @bitSizeOf(usize));
const used_byte = bucket.usedBits(used_byte_index);
const is_used = @as(u1, @truncate(used_byte.* >> used_bit_index)) != 0;
if (!is_used) {
reportDoubleFree(
return_address,
bucketStackTrace(bucket, slot_count, slot_index, .alloc),
bucketStackTrace(bucket, slot_count, slot_index, .free),
);
// 可以恢复,因为这是释放操作。
return false;
}
// 现在确定是正在使用的小块分配。
const requested_size = bucket.requestedSizes(slot_count)[slot_index];
if (requested_size == 0) @panic("Invalid free");
const slot_alignment = bucket.log2PtrAligns(slot_count)[slot_index];
if (memory.len != requested_size or alignment != slot_alignment) {
var addr_buf: [stack_n]usize = undefined;
const free_stack_trace = std.debug.captureCurrentStackTrace(.{ .first_address = return_address }, &addr_buf);
if (memory.len != requested_size) {
@branchHint(.cold);
log.err("Allocation size {d} bytes does not match free size {d}. Allocation: {f} Free: {f}", .{
requested_size,
memory.len,
std.debug.FormatStackTrace{
.stack_trace = bucketStackTrace(bucket, slot_count, slot_index, .alloc),
.terminal_mode = std.log.terminalMode(),
},
std.debug.FormatStackTrace{
.stack_trace = free_stack_trace,
.terminal_mode = std.log.terminalMode(),
},
});
}
if (alignment != slot_alignment) {
@branchHint(.cold);
log.err("Allocation alignment {d} does not match free alignment {d}. Allocation: {f} Free: {f}", .{
slot_alignment.toByteUnits(),
alignment.toByteUnits(),
std.debug.FormatStackTrace{
.stack_trace = bucketStackTrace(bucket, slot_count, slot_index, .alloc),
.terminal_mode = std.log.terminalMode(),
},
std.debug.FormatStackTrace{
.stack_trace = free_stack_trace,
.terminal_mode = std.log.terminalMode(),
},
});
}
}
if (new_size_class_index != size_class_index) return false;
const prev_req_bytes = self.total_requested_bytes;
if (config.enable_memory_limit) {
const new_req_bytes = prev_req_bytes - memory.len + new_len;
if (new_req_bytes > prev_req_bytes and new_req_bytes > self.requested_memory_limit) {
return false;
}
self.total_requested_bytes = new_req_bytes;
}
if (memory.len > new_len) @memset(memory[new_len..], undefined);
if (config.verbose_log)
log.info("small resize {d} bytes at {*} to {d}", .{ memory.len, memory.ptr, new_len });
if (config.safety)
bucket.requestedSizes(slot_count)[slot_index] = @intCast(new_len);
if (config.resize_stack_traces)
bucket.captureStackTrace(return_address, slot_count, slot_index, .alloc);
return true;
}
};
}
const TraceKind = enum {
alloc,
free,
};
const test_config: Config = .{};
test "small allocations - free in same order" {
var gpa = DebugAllocator(test_config){};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
var list = std.array_list.Managed(*u64).init(std.testing.allocator);
defer list.deinit();
var i: usize = 0;
while (i < 513) : (i += 1) {
const ptr = try allocator.create(u64);
try list.append(ptr);
}
for (list.items) |ptr| {
allocator.destroy(ptr);
}
}
test "small allocations - free in reverse order" {
var gpa = DebugAllocator(test_config){};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
var list = std.array_list.Managed(*u64).init(std.testing.allocator);
defer list.deinit();
var i: usize = 0;
while (i < 513) : (i += 1) {
const ptr = try allocator.create(u64);
try list.append(ptr);
}
while (list.pop()) |ptr| {
allocator.destroy(ptr);
}
}
test "large allocations" {
var gpa = DebugAllocator(test_config){};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
const ptr1 = try allocator.alloc(u64, 42768);
const ptr2 = try allocator.alloc(u64, 52768);
allocator.free(ptr1);
const ptr3 = try allocator.alloc(u64, 62768);
allocator.free(ptr3);
allocator.free(ptr2);
}
test "very large allocation" {
var gpa = DebugAllocator(test_config){};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
try std.testing.expectError(error.OutOfMemory, allocator.alloc(u8, math.maxInt(usize)));
}
test "realloc" {
var gpa = DebugAllocator(test_config){};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
var slice = try allocator.alignedAlloc(u8, .of(u32), 1);
defer allocator.free(slice);
slice[0] = 0x12;
// 此次重新分配应保持指针地址不变。
const old_slice = slice;
slice = try allocator.realloc(slice, 2);
try std.testing.expect(old_slice.ptr == slice.ptr);
try std.testing.expect(slice[0] == 0x12);
slice[1] = 0x34;
// 这需要升级到更大的尺寸类别
slice = try allocator.realloc(slice, 17);
try std.testing.expect(slice[0] == 0x12);
try std.testing.expect(slice[1] == 0x34);
}
test "shrink" {
var gpa: DebugAllocator(test_config) = .{};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
var slice = try allocator.alloc(u8, 20);
defer allocator.free(slice);
@memset(slice, 0x11);
try std.testing.expect(allocator.resize(slice, 17));
slice = slice[0..17];
for (slice) |b| {
try std.testing.expect(b == 0x11);
}
// 缩减时不跨越大小类别边界。
try std.testing.expect(!allocator.resize(slice, 16));
}
test "large object - grow" {
if (builtin.target.cpu.arch.isWasm()) {
// 预期在没有内存映射的目标上无法通过。
return error.SkipZigTest;
}
var gpa: DebugAllocator(test_config) = .{};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
var slice1 = try allocator.alloc(u8, default_page_size * 2 - 20);
defer allocator.free(slice1);
const old = slice1;
slice1 = try allocator.realloc(slice1, default_page_size * 2 - 10);
try std.testing.expect(slice1.ptr == old.ptr);
slice1 = try allocator.realloc(slice1, default_page_size * 2);
try std.testing.expect(slice1.ptr == old.ptr);
slice1 = try allocator.realloc(slice1, default_page_size * 2 + 1);
}
test "realloc small object to large object" {
var gpa = DebugAllocator(test_config){};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
var slice = try allocator.alloc(u8, 70);
defer allocator.free(slice);
slice[0] = 0x12;
slice[60] = 0x34;
// 这需要升级为大对象
const large_object_size = default_page_size * 2 + 50;
slice = try allocator.realloc(slice, large_object_size);
try std.testing.expect(slice[0] == 0x12);
try std.testing.expect(slice[60] == 0x34);
}
test "shrink large object to large object" {
var gpa: DebugAllocator(test_config) = .{};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
var slice = try allocator.alloc(u8, default_page_size * 2 + 50);
defer allocator.free(slice);
slice[0] = 0x12;
slice[60] = 0x34;
if (!allocator.resize(slice, default_page_size * 2 + 1)) return;
slice = slice.ptr[0 .. default_page_size * 2 + 1];
try std.testing.expect(slice[0] == 0x12);
try std.testing.expect(slice[60] == 0x34);
try std.testing.expect(allocator.resize(slice, default_page_size * 2 + 1));
slice = slice[0 .. default_page_size * 2 + 1];
try std.testing.expect(slice[0] == 0x12);
try std.testing.expect(slice[60] == 0x34);
slice = try allocator.realloc(slice, default_page_size * 2);
try std.testing.expect(slice[0] == 0x12);
try std.testing.expect(slice[60] == 0x34);
}
test "shrink large object to large object with larger alignment" {
if (builtin.os.tag == .wasi) {
// https://github.com/ziglang/zig/issues/22731
return error.SkipZigTest;
}
var gpa: DebugAllocator(test_config) = .{};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
var debug_buffer: [1000]u8 = undefined;
var fba = std.heap.FixedBufferAllocator.init(&debug_buffer);
const debug_allocator = fba.allocator();
const alloc_size = default_page_size * 2 + 50;
var slice = try allocator.alignedAlloc(u8, .@"16", alloc_size);
defer allocator.free(slice);
const big_alignment: usize = default_page_size * 2;
// 此循环不断分配,直到找到一个未按较大对齐值对齐的页面。
// 循环后缩减分配,同时将对齐要求提高到较大值;
// 已知这会强制触发重新分配。
var stuff_to_free = std.array_list.Managed([]align(16) u8).init(debug_allocator);
while (mem.isAligned(@intFromPtr(slice.ptr), big_alignment)) {
try stuff_to_free.append(slice);
slice = try allocator.alignedAlloc(u8, .@"16", alloc_size);
}
while (stuff_to_free.pop()) |item| {
allocator.free(item);
}
slice[0] = 0x12;
slice[60] = 0x34;
slice = try allocator.reallocAdvanced(slice, big_alignment, alloc_size / 2);
try std.testing.expect(slice[0] == 0x12);
try std.testing.expect(slice[60] == 0x34);
}
test "realloc large object to small object" {
var gpa = DebugAllocator(test_config){};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
var slice = try allocator.alloc(u8, default_page_size * 2 + 50);
defer allocator.free(slice);
slice[0] = 0x12;
slice[16] = 0x34;
slice = try allocator.realloc(slice, 19);
try std.testing.expect(slice[0] == 0x12);
try std.testing.expect(slice[16] == 0x34);
}
test "non-page-allocator backing allocator" {
var gpa: DebugAllocator(.{
.backing_allocator_zeroes = false,
}) = .{
.backing_allocator = std.testing.allocator,
};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
const ptr = try allocator.create(i32);
defer allocator.destroy(ptr);
}
test "realloc large object to larger alignment" {
if (builtin.os.tag == .wasi) {
// https://github.com/ziglang/zig/issues/22731
return error.SkipZigTest;
}
var gpa = DebugAllocator(test_config){};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
var debug_buffer: [1000]u8 = undefined;
var fba = std.heap.FixedBufferAllocator.init(&debug_buffer);
const debug_allocator = fba.allocator();
var slice = try allocator.alignedAlloc(u8, .@"16", default_page_size * 2 + 50);
defer allocator.free(slice);
const big_alignment: usize = default_page_size * 2;
// 此循环持续分配,直到找到不满足大对齐要求的页。
var stuff_to_free = std.array_list.Managed([]align(16) u8).init(debug_allocator);
while (mem.isAligned(@intFromPtr(slice.ptr), big_alignment)) {
try stuff_to_free.append(slice);
slice = try allocator.alignedAlloc(u8, .@"16", default_page_size * 2 + 50);
}
while (stuff_to_free.pop()) |item| {
allocator.free(item);
}
slice[0] = 0x12;
slice[16] = 0x34;
slice = try allocator.reallocAdvanced(slice, 32, default_page_size * 2 + 100);
try std.testing.expect(slice[0] == 0x12);
try std.testing.expect(slice[16] == 0x34);
slice = try allocator.reallocAdvanced(slice, 32, default_page_size * 2 + 25);
try std.testing.expect(slice[0] == 0x12);
try std.testing.expect(slice[16] == 0x34);
slice = try allocator.reallocAdvanced(slice, big_alignment, default_page_size * 2 + 100);
try std.testing.expect(slice[0] == 0x12);
try std.testing.expect(slice[16] == 0x34);
}
test "large object rejects shrinking to small" {
if (builtin.target.cpu.arch.isWasm()) {
// 预期在没有内存映射的目标上无法通过。
return error.SkipZigTest;
}
var failing_allocator = std.testing.FailingAllocator.init(std.heap.page_allocator, .{ .fail_index = 3 });
var gpa: DebugAllocator(.{}) = .{
.backing_allocator = failing_allocator.allocator(),
};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
var slice = try allocator.alloc(u8, default_page_size * 2 + 50);
defer allocator.free(slice);
slice[0] = 0x12;
slice[3] = 0x34;
try std.testing.expect(!allocator.resize(slice, 4));
try std.testing.expect(slice[0] == 0x12);
try std.testing.expect(slice[3] == 0x34);
}
test "objects of size 1024 and 2048" {
var gpa = DebugAllocator(test_config){};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
const slice = try allocator.alloc(u8, 1025);
const slice2 = try allocator.alloc(u8, 3000);
allocator.free(slice);
allocator.free(slice2);
}
test "setting a memory cap" {
var gpa = DebugAllocator(.{ .enable_memory_limit = true }){};
defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
const allocator = gpa.allocator();
gpa.requested_memory_limit = 1010;
const small = try allocator.create(i32);
try std.testing.expect(gpa.total_requested_bytes == 4);
const big = try allocator.alloc(u8, 1000);
try std.testing.expect(gpa.total_requested_bytes == 1004);
try std.testing.expectError(error.OutOfMemory, allocator.create(u64));
allocator.destroy(small);
try std.testing.expect(gpa.total_requested_bytes == 1000);
allocator.free(big);
try std.testing.expect(gpa.total_requested_bytes == 0);
const exact = try allocator.alloc(u8, 1010);
try std.testing.expect(gpa.total_requested_bytes == 1010);
allocator.free(exact);
}
test "large allocations count requested size not backing size" {
var gpa: DebugAllocator(.{ .enable_memory_limit = true }) = .{};
const allocator = gpa.allocator();
var buf = try allocator.alignedAlloc(u8, .@"1", default_page_size + 1);
try std.testing.expectEqual(default_page_size + 1, gpa.total_requested_bytes);
buf = try allocator.realloc(buf, 1);
try std.testing.expectEqual(1, gpa.total_requested_bytes);
buf = try allocator.realloc(buf, 2);
try std.testing.expectEqual(2, gpa.total_requested_bytes);
}
test "retain metadata and never unmap" {
var gpa = std.heap.DebugAllocator(.{
.safety = true,
.never_unmap = true,
.retain_metadata = true,
}){};
defer std.debug.assert(gpa.deinit() == .ok);
const allocator = gpa.allocator();
const alloc = try allocator.alloc(u8, 8);
allocator.free(alloc);
const alloc2 = try allocator.alloc(u8, 8);
allocator.free(alloc2);
}