Meg's Mirrors

zig

1	//! An allocator that is intended to be used in Debug mode.
2	//!
3	//! ## Features
4	//!
5	//! * Captures stack traces on allocation, free, and optionally resize.
6	//! * Double free detection, which prints all three traces (first alloc, first
7	//! free, second free).
8	//! * Leak detection, with stack traces.
9	//! * Never reuses memory addresses, making it easier for Zig to detect branch
10	//! on undefined values in case of dangling pointers. This relies on
11	//! the backing allocator to also not reuse addresses.
12	//! * Uses a minimum backing allocation size to avoid operating system errors
13	//! from having too many active memory mappings.
14	//! * When a page of memory is no longer needed, give it back to resident
15	//! memory as soon as possible, so that it causes page faults when used.
16	//! * Cross platform. Operates based on a backing allocator which makes it work
17	//! everywhere, even freestanding.
18	//! * Compile-time configuration.
19	//!
20	//! These features require the allocator to be quite slow and wasteful. For
21	//! example, when allocating a single byte, the efficiency is less than 1%;
22	//! it requires more than 100 bytes of overhead to manage the allocation for
23	//! one byte. The efficiency gets better with larger allocations.
24	//!
25	//! ## Basic Design
26	//!
27	//! Allocations are divided into two categories, small and large.
28	//!
29	//! Small allocations are divided into buckets based on `page_size`:
30	//!
31	//! ```
32	//! index obj_size
33	//! 0 1
34	//! 1 2
35	//! 2 4
36	//! 3 8
37	//! 4 16
38	//! 5 32
39	//! 6 64
40	//! 7 128
41	//! 8 256
42	//! 9 512
43	//! 10 1024
44	//! 11 2048
45	//! ...
46	//! ```
47	//!
48	//! This goes on for `small_bucket_count` indexes.
49	//!
50	//! Allocations are grouped into an object size based on max(len, alignment),
51	//! rounded up to the next power of two.
52	//!
53	//! The main allocator state has an array of all the "current" buckets for each
54	//! size class. Each slot in the array can be null, meaning the bucket for that
55	//! size class is not allocated. When the first object is allocated for a given
56	//! size class, it makes one `page_size` allocation from the backing allocator.
57	//! This allocation is divided into "slots" - one per allocated object, leaving
58	//! room for the allocation metadata (starting with `BucketHeader`), which is
59	//! located at the very end of the "page".
60	//!
61	//! The allocation metadata includes "used bits" - 1 bit per slot representing
62	//! whether the slot is used. Allocations always take the next available slot
63	//! from the current bucket, setting the corresponding used bit, as well as
64	//! incrementing `allocated_count`.
65	//!
66	//! Frees recover the allocation metadata based on the address, length, and
67	//! alignment, relying on the backing allocation's large alignment, combined
68	//! with the fact that allocations are never moved from small to large, or vice
69	//! versa.
70	//!
71	//! When a bucket is full, a new one is allocated, containing a pointer to the
72	//! previous one. This doubly-linked list is iterated during leak detection.
73	//!
74	//! Resizing and remapping work the same on small allocations: if the size
75	//! class would not change, then the operation succeeds, and the address is
76	//! unchanged. Otherwise, the request is rejected.
77	//!
78	//! Large objects are allocated directly using the backing allocator. Metadata
79	//! is stored separately in a `std.HashMap` using the backing allocator.
80	//!
81	//! Resizing and remapping are forwarded directly to the backing allocator,
82	//! except where such operations would change the category from large to small.
83	const builtin = @import("builtin");
84	const StackTrace = std.debug.StackTrace;
85
86	const std = @import("std");
87	const log = std.log.scoped(.DebugAllocator);
88	const math = std.math;
89	const assert = std.debug.assert;
90	const mem = std.mem;
91	const Allocator = std.mem.Allocator;
92
93	const default_page_size: usize = switch (builtin.os.tag) {
94	// Makes `std.heap.PageAllocator` take the happy path.
95	.windows => 64 * 1024,
96	else => switch (builtin.cpu.arch) {
97	// Max alignment supported by `std.heap.WasmAllocator`.
98	.wasm32, .wasm64 => 64 * 1024,
99	// Avoids too many active mappings when `page_size_max` is low.
100	else => @max(std.heap.page_size_max, 128 * 1024),
101	},
102	};
103
104	const Log2USize = std.math.Log2Int(usize);
105
106	const default_sys_stack_trace_frames: usize = if (std.debug.sys_can_stack_trace) 6 else 0;
107	const default_stack_trace_frames: usize = switch (builtin.mode) {
108	.debug => default_sys_stack_trace_frames,
109	else => 0,
110	};
111
112	pub const Config = struct {
113	/// Number of stack frames to capture.
114	stack_trace_frames: usize = default_stack_trace_frames,
115
116	/// If true, the allocator will have two fields:
117	/// * `total_requested_bytes` which tracks the total allocated bytes of memory requested.
118	/// * `requested_memory_limit` which causes allocations to return `error.OutOfMemory`
119	/// when the `total_requested_bytes` exceeds this limit.
120	/// If false, these fields will be `void`.
121	enable_memory_limit: bool = false,
122
123	/// Whether to enable safety checks.
124	safety: bool = std.debug.runtime_safety,
125
126	/// Whether the allocator may be used simultaneously from multiple threads.
127	thread_safe: bool = !builtin.single_threaded,
128
129	/// This is a temporary debugging trick you can use to turn segfaults into more helpful
130	/// logged error messages with stack trace details. The downside is that every allocation
131	/// will be leaked, unless used with retain_metadata!
132	never_unmap: bool = false,
133
134	/// This is a temporary debugging aid that retains metadata about allocations indefinitely.
135	/// This allows a greater range of double frees to be reported. All metadata is freed when
136	/// deinit is called. When used with never_unmap, deliberately leaked memory is also freed
137	/// during deinit. Currently should be used with never_unmap to avoid segfaults.
138	/// TODO https://github.com/ziglang/zig/issues/4298 will allow use without never_unmap
139	retain_metadata: bool = false,
140
141	/// Enables emitting info messages with the size and address of every allocation.
142	verbose_log: bool = false,
143
144	/// Tell whether the backing allocator returns already-zeroed memory.
145	backing_allocator_zeroes: bool = true,
146
147	/// When resizing an allocation, refresh the stack trace with the resize
148	/// callsite. Comes with a performance penalty.
149	resize_stack_traces: bool = false,
150
151	/// Magic value that distinguishes allocations owned by this allocator from
152	/// other regions of memory.
153	canary: usize = @truncate(0x9232a6ff85dff10f),
154
155	/// The size of allocations requested from the backing allocator for
156	/// subdividing into slots for small allocations.
157	///
158	/// Must be a power of two.
159	page_size: usize = default_page_size,
160	};
161
162	/// Default initialization of this struct is deprecated; use `.init` instead.
163	pub fn DebugAllocator(comptime config: Config) type {
164	return struct {
165	backing_allocator: Allocator = std.heap.page_allocator,
166	/// Tracks the active bucket, which is the one that has free slots in it.
167	buckets: [small_bucket_count]?*BucketHeader = @splat(null),
168	large_allocations: LargeAllocTable = .empty,
169	total_requested_bytes: @TypeOf(total_requested_bytes_init) = total_requested_bytes_init,
170	requested_memory_limit: @TypeOf(requested_memory_limit_init) = requested_memory_limit_init,
171	mutex: @TypeOf(mutex_init) = mutex_init,
172
173	const Self = @This();
174
175	pub const init: Self = .{};
176
177	/// These can be derived from size_class_index but the calculation is nontrivial.
178	const slot_counts: [small_bucket_count]SlotIndex = init: {
179	@setEvalBranchQuota(10000);
180	var result: [small_bucket_count]SlotIndex = undefined;
181	for (&result, 0..) |*elem, i| elem.* = calculateSlotCount(i);
182	break :init result;
183	};
184
185	comptime {
186	assert(math.isPowerOfTwo(page_size));
187	}
188
189	const page_size = config.page_size;
190	const page_align: mem.Alignment = .fromByteUnits(page_size);
191	/// Integer type for pointing to slots in a small allocation
192	const SlotIndex = @Int(.unsigned, math.log2(page_size) + 1);
193
194	const total_requested_bytes_init = if (config.enable_memory_limit) @as(usize, 0) else {};
195	const requested_memory_limit_init = if (config.enable_memory_limit) @as(usize, math.maxInt(usize)) else {};
196
197	const have_mutex = config.thread_safe;
198	const mutex_init = if (have_mutex) std.Io.Mutex.init else {};
199
200	const stack_n = config.stack_trace_frames;
201	const one_trace_size = @sizeOf(usize) * stack_n;
202	const traces_per_slot = 2;
203
204	pub const Error = mem.Allocator.Error;
205
206	/// Avoids creating buckets that would only be able to store a small
207	/// number of slots. Value of 1 means 2 is the minimum slot count.
208	const minimum_slots_per_bucket_log2 = 1;
209	const small_bucket_count = math.log2(page_size) - minimum_slots_per_bucket_log2;
210	const largest_bucket_object_size = 1 << (small_bucket_count - 1);
211	const LargestSizeClassInt = std.math.IntFittingRange(0, largest_bucket_object_size);
212
213	const bucketCompare = struct {
214	fn compare(a: *BucketHeader, b: *BucketHeader) std.math.Order {
215	return std.math.order(@intFromPtr(a.page), @intFromPtr(b.page));
216	}
217	}.compare;
218
219	const LargeAlloc = struct {
220	bytes: []u8,
221	requested_size: if (config.enable_memory_limit) usize else void,
222	stack_addresses: [trace_n][stack_n]usize,
223	freed: if (config.retain_metadata) bool else void,
224	alignment: if (config.never_unmap and config.retain_metadata) mem.Alignment else void,
225
226	const trace_n = if (config.retain_metadata) traces_per_slot else 1;
227
228	fn dumpStackTrace(self: *LargeAlloc, trace_kind: TraceKind) void {
229	std.debug.dumpStackTrace(self.getStackTrace(trace_kind));
230	}
231
232	fn getStackTrace(self: *LargeAlloc, trace_kind: TraceKind) std.debug.StackTrace {
233	assert(@backingInt(trace_kind) < trace_n);
234	const stack_addresses = &self.stack_addresses[@backingInt(trace_kind)];
235	var len: usize = 0;
236	while (len < stack_n and stack_addresses[len] != 0) {
237	len += 1;
238	}
239	return .{
240	.return_addresses = stack_addresses[0..len],
241	.skipped = if (len < stack_addresses.len) .none else .unknown,
242	};
243	}
244
245	fn captureStackTrace(self: *LargeAlloc, ret_addr: usize, trace_kind: TraceKind) void {
246	assert(@backingInt(trace_kind) < trace_n);
247	const stack_addresses = &self.stack_addresses[@backingInt(trace_kind)];
248	collectStackTrace(ret_addr, stack_addresses);
249	}
250	};
251	const LargeAllocTable = std.AutoHashMapUnmanaged(usize, LargeAlloc);
252
253	/// Bucket: In memory, in order:
254	/// * BucketHeader
255	/// * bucket_used_bits: [N]usize, // 1 bit for every slot
256	/// -- below only exists when config.safety is true --
257	/// * requested_sizes: [N]LargestSizeClassInt // 1 int for every slot
258	/// * log2_ptr_aligns: [N]u8 // 1 byte for every slot
259	/// -- above only exists when config.safety is true --
260	/// * stack_trace_addresses: [N]usize, // traces_per_slot for every allocation
261	const BucketHeader = struct {
262	allocated_count: SlotIndex,
263	freed_count: SlotIndex,
264	prev: ?*BucketHeader,
265	next: ?*BucketHeader,
266	canary: usize = config.canary,
267
268	fn fromPage(page_addr: usize, slot_count: usize) *BucketHeader {
269	const unaligned = page_addr +% page_size -% bucketSize(slot_count);
270	return @ptrFromInt(unaligned & ~(@as(usize, @alignOf(BucketHeader)) - 1));
271	}
272
273	fn usedBits(bucket: *BucketHeader, index: usize) *usize {
274	const ptr: [*]u8 = @ptrCast(bucket);
275	const bits: [*]usize = @ptrCast(@alignCast(ptr + @sizeOf(BucketHeader)));
276	return &bits[index];
277	}
278
279	fn requestedSizes(bucket: *BucketHeader, slot_count: usize) []LargestSizeClassInt {
280	if (!config.safety) @compileError("requested size is only stored when safety is enabled");
281	const start_ptr = @as([*]u8, @ptrCast(bucket)) + bucketRequestedSizesStart(slot_count);
282	const sizes = @as([*]LargestSizeClassInt, @ptrCast(@alignCast(start_ptr)));
283	return sizes[0..slot_count];
284	}
285
286	fn log2PtrAligns(bucket: *BucketHeader, slot_count: usize) []mem.Alignment {
287	if (!config.safety) @compileError("requested size is only stored when safety is enabled");
288	const aligns_ptr = @as([*]u8, @ptrCast(bucket)) + bucketAlignsStart(slot_count);
289	return @ptrCast(aligns_ptr[0..slot_count]);
290	}
291
292	fn stackTracePtr(
293	bucket: *BucketHeader,
294	slot_count: usize,
295	slot_index: SlotIndex,
296	trace_kind: TraceKind,
297	) *[stack_n]usize {
298	const start_ptr = @as([*]u8, @ptrCast(bucket)) + bucketStackFramesStart(slot_count);
299	const addr = start_ptr + one_trace_size * traces_per_slot * slot_index +
300	@backingInt(trace_kind) * @as(usize, one_trace_size);
301	return @ptrCast(@alignCast(addr));
302	}
303
304	fn captureStackTrace(
305	bucket: *BucketHeader,
306	ret_addr: usize,
307	slot_count: usize,
308	slot_index: SlotIndex,
309	trace_kind: TraceKind,
310	) void {
311	// Initialize them to 0. When determining the count we must look
312	// for non zero addresses.
313	const stack_addresses = bucket.stackTracePtr(slot_count, slot_index, trace_kind);
314	collectStackTrace(ret_addr, stack_addresses);
315	}
316	};
317
318	pub fn allocator(self: *Self) Allocator {
319	return .{
320	.ptr = self,
321	.vtable = &.{
322	.alloc = alloc,
323	.resize = resize,
324	.remap = remap,
325	.free = free,
326	},
327	};
328	}
329
330	fn bucketStackTrace(
331	bucket: *BucketHeader,
332	slot_count: usize,
333	slot_index: SlotIndex,
334	trace_kind: TraceKind,
335	) StackTrace {
336	const stack_addresses = bucket.stackTracePtr(slot_count, slot_index, trace_kind);
337	var len: usize = 0;
338	while (len < stack_n and stack_addresses[len] != 0) {
339	len += 1;
340	}
341	return .{
342	.return_addresses = stack_addresses[0..len],
343	.skipped = if (len < stack_addresses.len) .none else .unknown,
344	};
345	}
346
347	fn bucketRequestedSizesStart(slot_count: usize) usize {
348	if (!config.safety) @compileError("requested sizes are not stored unless safety is enabled");
349	return mem.alignForward(
350	usize,
351	@sizeOf(BucketHeader) + usedBitsSize(slot_count),
352	@alignOf(LargestSizeClassInt),
353	);
354	}
355
356	fn bucketAlignsStart(slot_count: usize) usize {
357	if (!config.safety) @compileError("requested sizes are not stored unless safety is enabled");
358	return bucketRequestedSizesStart(slot_count) + (@sizeOf(LargestSizeClassInt) * slot_count);
359	}
360
361	fn bucketStackFramesStart(slot_count: usize) usize {
362	const unaligned_start = if (config.safety)
363	bucketAlignsStart(slot_count) + slot_count
364	else
365	@sizeOf(BucketHeader) + usedBitsSize(slot_count);
366	return mem.alignForward(usize, unaligned_start, @alignOf(usize));
367	}
368
369	fn bucketSize(slot_count: usize) usize {
370	return bucketStackFramesStart(slot_count) + one_trace_size * traces_per_slot * slot_count;
371	}
372
373	/// This is executed only at compile-time to prepopulate a lookup table.
374	fn calculateSlotCount(size_class_index: usize) SlotIndex {
375	const size_class = @as(usize, 1) << @as(Log2USize, @intCast(size_class_index));
376	var lower: usize = 1 << minimum_slots_per_bucket_log2;
377	var upper: usize = (page_size - bucketSize(lower)) / size_class;
378	while (upper > lower) {
379	const proposed: usize = lower + (upper - lower) / 2;
380	if (proposed == lower) return lower;
381	const slots_end = proposed * size_class;
382	const header_begin = mem.alignForward(usize, slots_end, @alignOf(BucketHeader));
383	const end = header_begin + bucketSize(proposed);
384	if (end > page_size) {
385	upper = proposed - 1;
386	} else {
387	lower = proposed;
388	}
389	}
390	const slots_end = lower * size_class;
391	const header_begin = mem.alignForward(usize, slots_end, @alignOf(BucketHeader));
392	const end = header_begin + bucketSize(lower);
393	assert(end <= page_size);
394	return lower;
395	}
396
397	fn usedBitsCount(slot_count: usize) usize {
398	return (slot_count + (@bitSizeOf(usize) - 1)) / @bitSizeOf(usize);
399	}
400
401	fn usedBitsSize(slot_count: usize) usize {
402	return usedBitsCount(slot_count) * @sizeOf(usize);
403	}
404
405	fn detectLeaksInBucket(
406	bucket: *BucketHeader,
407	size_class_index: usize,
408	used_bits_count: usize,
409	) usize {
410	const size_class = @as(usize, 1) << @as(Log2USize, @intCast(size_class_index));
411	const slot_count = slot_counts[size_class_index];
412	var leaks: usize = 0;
413	for (0..used_bits_count) |used_bits_byte| {
414	const used_int = bucket.usedBits(used_bits_byte).*;
415	if (used_int != 0) {
416	for (0..@bitSizeOf(usize)) |bit_index_usize| {
417	const bit_index: Log2USize = @intCast(bit_index_usize);
418	const is_used = @as(u1, @truncate(used_int >> bit_index)) != 0;
419	if (is_used) {
420	const slot_index: SlotIndex = @intCast(used_bits_byte * @bitSizeOf(usize) + bit_index);
421	const stack_trace = bucketStackTrace(bucket, slot_count, slot_index, .alloc);
422	const page_addr = @intFromPtr(bucket) & ~(page_size - 1);
423	const addr = page_addr + slot_index * size_class;
424	log.err("memory address 0x{x} leaked: {f}", .{
425	addr,
426	std.debug.FormatStackTrace{
427	.stack_trace = stack_trace,
428	.terminal_mode = std.log.terminalMode(),
429	},
430	});
431	leaks += 1;
432	}
433	}
434	}
435	}
436	return leaks;
437	}
438
439	/// Emits log messages for leaks and then returns the number of detected leaks (0 if no leaks were detected).
440	pub fn detectLeaks(self: *Self) usize {
441	var leaks: usize = 0;
442
443	for (self.buckets, 0..) |init_optional_bucket, size_class_index| {
444	var optional_bucket = init_optional_bucket;
445	const slot_count = slot_counts[size_class_index];
446	const used_bits_count = usedBitsCount(slot_count);
447	while (optional_bucket) |bucket| {
448	leaks += detectLeaksInBucket(bucket, size_class_index, used_bits_count);
449	optional_bucket = bucket.prev;
450	}
451	}
452
453	var it = self.large_allocations.valueIterator();
454	while (it.next()) |large_alloc| {
455	if (config.retain_metadata and large_alloc.freed) continue;
456	const stack_trace = large_alloc.getStackTrace(.alloc);
457	log.err("memory address 0x{x} leaked: {f}", .{
458	@intFromPtr(large_alloc.bytes.ptr),
459	std.debug.FormatStackTrace{
460	.stack_trace = stack_trace,
461	.terminal_mode = std.log.terminalMode(),
462	},
463	});
464	leaks += 1;
465	}
466	return leaks;
467	}
468
469	fn freeRetainedMetadata(self: *Self) void {
470	comptime assert(config.retain_metadata);
471	if (config.never_unmap) {
472	// free large allocations that were intentionally leaked by never_unmap
473	var it = self.large_allocations.iterator();
474	while (it.next()) |large| {
475	if (large.value_ptr.freed) {
476	self.backing_allocator.rawFree(large.value_ptr.bytes, large.value_ptr.alignment, @returnAddress());
477	}
478	}
479	}
480	}
481
482	pub fn flushRetainedMetadata(self: *Self) void {
483	comptime assert(config.retain_metadata);
484	self.freeRetainedMetadata();
485	// also remove entries from large_allocations
486	var it = self.large_allocations.iterator();
487	while (it.next()) |large| {
488	if (large.value_ptr.freed) {
489	_ = self.large_allocations.remove(@intFromPtr(large.value_ptr.bytes.ptr));
490	}
491	}
492	}
493
494	/// Returns `std.heap.Check.leak` if there were leaks; `std.heap.Check.ok` otherwise.
495	pub fn deinit(self: *Self) std.heap.Check {
496	const leaks: usize = if (config.safety) self.detectLeaks() else 0;
497	self.deinitWithoutLeakChecks();
498	return if (leaks == 0) .ok else .leak;
499	}
500
501	/// Like `deinit`, but does not check for memory leaks. This is useful if leaks have already
502	/// been detected manually with `detectLeaks` to avoid reporting them for a second time.
503	pub fn deinitWithoutLeakChecks(self: *Self) void {
504	if (config.retain_metadata) self.freeRetainedMetadata();
505	self.large_allocations.deinit(self.backing_allocator);
506	self.* = undefined;
507	}
508
509	fn collectStackTrace(first_trace_addr: usize, addr_buf: *[stack_n]usize) void {
510	const st = std.debug.captureCurrentStackTrace(.{ .first_address = first_trace_addr }, addr_buf);
511	@memset(addr_buf[@min(st.return_addresses.len, addr_buf.len)..], 0);
512	}
513
514	fn reportDoubleFree(ret_addr: usize, alloc_stack_trace: StackTrace, free_stack_trace: StackTrace) void {
515	@branchHint(.cold);
516	var addr_buf: [stack_n]usize = undefined;
517	const second_free_stack_trace = std.debug.captureCurrentStackTrace(.{ .first_address = ret_addr }, &addr_buf);
518	log.err("Double free detected. Allocation: {f} First free: {f} Second free: {f}", .{
519	std.debug.FormatStackTrace{
520	.stack_trace = alloc_stack_trace,
521	.terminal_mode = std.log.terminalMode(),
522	},
523	std.debug.FormatStackTrace{
524	.stack_trace = free_stack_trace,
525	.terminal_mode = std.log.terminalMode(),
526	},
527	std.debug.FormatStackTrace{
528	.stack_trace = second_free_stack_trace,
529	.terminal_mode = std.log.terminalMode(),
530	},
531	});
532	}
533
534	/// This function assumes the object is in the large object storage regardless
535	/// of the parameters.
536	fn resizeLarge(
537	self: *Self,
538	old_mem: []u8,
539	alignment: mem.Alignment,
540	new_size: usize,
541	ret_addr: usize,
542	may_move: bool,
543	) ?[*]u8 {
544	if (config.retain_metadata and may_move) {
545	// Before looking up the entry (since this could invalidate
546	// it), we must reserve space for the new entry in case the
547	// allocation is relocated.
548	self.large_allocations.ensureUnusedCapacity(self.backing_allocator, 1) catch return null;
549	}
550
551	const entry = self.large_allocations.getEntry(@intFromPtr(old_mem.ptr)) orelse {
552	if (config.safety) {
553	@panic("Invalid free");
554	} else {
555	unreachable;
556	}
557	};
558
559	if (config.retain_metadata and entry.value_ptr.freed) {
560	if (config.safety) {
561	reportDoubleFree(ret_addr, entry.value_ptr.getStackTrace(.alloc), entry.value_ptr.getStackTrace(.free));
562	@panic("Unrecoverable double free");
563	} else {
564	unreachable;
565	}
566	}
567
568	if (config.safety and old_mem.len != entry.value_ptr.bytes.len) {
569	@branchHint(.cold);
570	var addr_buf: [stack_n]usize = undefined;
571	const free_stack_trace = std.debug.captureCurrentStackTrace(.{ .first_address = ret_addr }, &addr_buf);
572	log.err("Allocation size {d} bytes does not match free size {d}. Allocation: {f} Free: {f}", .{
573	entry.value_ptr.bytes.len,
574	old_mem.len,
575	std.debug.FormatStackTrace{
576	.stack_trace = entry.value_ptr.getStackTrace(.alloc),
577	.terminal_mode = std.log.terminalMode(),
578	},
579	std.debug.FormatStackTrace{
580	.stack_trace = free_stack_trace,
581	.terminal_mode = std.log.terminalMode(),
582	},
583	});
584	}
585
586	// If this would move the allocation into a small size class,
587	// refuse the request, because it would require creating small
588	// allocation metadata.
589	const new_size_class_index: usize = @max(@bitSizeOf(usize) - @clz(new_size - 1), @backingInt(alignment));
590	if (new_size_class_index < self.buckets.len) return null;
591
592	// Do memory limit accounting with requested sizes rather than what
593	// backing_allocator returns because if we want to return
594	// error.OutOfMemory, we have to leave allocation untouched, and
595	// that is impossible to guarantee after calling
596	// backing_allocator.rawResize.
597	const prev_req_bytes = self.total_requested_bytes;
598	if (config.enable_memory_limit) {
599	const new_req_bytes = prev_req_bytes + new_size - entry.value_ptr.requested_size;
600	if (new_req_bytes > prev_req_bytes and new_req_bytes > self.requested_memory_limit) {
601	return null;
602	}
603	self.total_requested_bytes = new_req_bytes;
604	}
605
606	const opt_resized_ptr = if (may_move)
607	self.backing_allocator.rawRemap(old_mem, alignment, new_size, ret_addr)
608	else if (self.backing_allocator.rawResize(old_mem, alignment, new_size, ret_addr))
609	old_mem.ptr
610	else
611	null;
612
613	const resized_ptr = opt_resized_ptr orelse {
614	if (config.enable_memory_limit) {
615	self.total_requested_bytes = prev_req_bytes;
616	}
617	return null;
618	};
619
620	if (config.enable_memory_limit) {
621	entry.value_ptr.requested_size = new_size;
622	}
623
624	if (config.verbose_log) {
625	log.info("large resize {d} bytes at {*} to {d} at {*}", .{
626	old_mem.len, old_mem.ptr, new_size, resized_ptr,
627	});
628	}
629	entry.value_ptr.bytes = resized_ptr[0..new_size];
630	if (config.resize_stack_traces)
631	entry.value_ptr.captureStackTrace(ret_addr, .alloc);
632
633	// Update the key of the hash map if the memory was relocated.
634	if (resized_ptr != old_mem.ptr) {
635	const large_alloc = entry.value_ptr.*;
636	if (config.retain_metadata) {
637	entry.value_ptr.freed = true;
638	entry.value_ptr.captureStackTrace(ret_addr, .free);
639	} else {
640	self.large_allocations.removeByPtr(entry.key_ptr);
641	}
642
643	const gop = self.large_allocations.getOrPutAssumeCapacity(@intFromPtr(resized_ptr));
644	if (config.retain_metadata and !config.never_unmap) {
645	// Backing allocator may be reusing memory that we're retaining metadata for
646	assert(!gop.found_existing or gop.value_ptr.freed);
647	} else {
648	assert(!gop.found_existing); // This would mean the kernel double-mapped pages.
649	}
650	gop.value_ptr.* = large_alloc;
651	}
652
653	return resized_ptr;
654	}
655
656	/// This function assumes the object is in the large object storage regardless
657	/// of the parameters.
658	fn freeLarge(
659	self: *Self,
660	old_mem: []u8,
661	alignment: mem.Alignment,
662	ret_addr: usize,
663	) void {
664	const entry = self.large_allocations.getEntry(@intFromPtr(old_mem.ptr)) orelse {
665	if (config.safety) {
666	@panic("Invalid free");
667	} else {
668	unreachable;
669	}
670	};
671
672	if (config.retain_metadata and entry.value_ptr.freed) {
673	if (config.safety) {
674	reportDoubleFree(ret_addr, entry.value_ptr.getStackTrace(.alloc), entry.value_ptr.getStackTrace(.free));
675	return;
676	} else {
677	unreachable;
678	}
679	}
680
681	if (config.safety and old_mem.len != entry.value_ptr.bytes.len) {
682	@branchHint(.cold);
683	var addr_buf: [stack_n]usize = undefined;
684	const free_stack_trace = std.debug.captureCurrentStackTrace(.{ .first_address = ret_addr }, &addr_buf);
685	log.err("Allocation size {d} bytes does not match free size {d}. Allocation: {f} Free: {f}", .{
686	entry.value_ptr.bytes.len,
687	old_mem.len,
688	std.debug.FormatStackTrace{
689	.stack_trace = entry.value_ptr.getStackTrace(.alloc),
690	.terminal_mode = std.log.terminalMode(),
691	},
692	std.debug.FormatStackTrace{
693	.stack_trace = free_stack_trace,
694	.terminal_mode = std.log.terminalMode(),
695	},
696	});
697	}
698
699	if (!config.never_unmap) {
700	self.backing_allocator.rawFree(old_mem, alignment, ret_addr);
701	}
702
703	if (config.enable_memory_limit) {
704	self.total_requested_bytes -= entry.value_ptr.requested_size;
705	}
706
707	if (config.verbose_log) {
708	log.info("large free {d} bytes at {*}", .{ old_mem.len, old_mem.ptr });
709	}
710
711	if (!config.retain_metadata) {
712	assert(self.large_allocations.remove(@intFromPtr(old_mem.ptr)));
713	} else {
714	entry.value_ptr.freed = true;
715	entry.value_ptr.captureStackTrace(ret_addr, .free);
716	}
717	}
718
719	fn alloc(context: *anyopaque, len: usize, alignment: mem.Alignment, ret_addr: usize) ?[*]u8 {
720	const self: *Self = @ptrCast(@alignCast(context));
721	if (have_mutex) std.Io.Threaded.mutexLock(&self.mutex);
722	defer if (have_mutex) std.Io.Threaded.mutexUnlock(&self.mutex);
723
724	if (config.enable_memory_limit) {
725	const new_req_bytes = self.total_requested_bytes + len;
726	if (new_req_bytes > self.requested_memory_limit) return null;
727	self.total_requested_bytes = new_req_bytes;
728	}
729
730	const size_class_index: usize = @max(@bitSizeOf(usize) - @clz(len - 1), @backingInt(alignment));
731	if (size_class_index >= self.buckets.len) {
732	@branchHint(.unlikely);
733	self.large_allocations.ensureUnusedCapacity(self.backing_allocator, 1) catch return null;
734	const ptr = self.backing_allocator.rawAlloc(len, alignment, ret_addr) orelse return null;
735	const slice = ptr[0..len];
736
737	const gop = self.large_allocations.getOrPutAssumeCapacity(@intFromPtr(slice.ptr));
738	if (config.retain_metadata and !config.never_unmap) {
739	// Backing allocator may be reusing memory that we're retaining metadata for
740	assert(!gop.found_existing or gop.value_ptr.freed);
741	} else {
742	assert(!gop.found_existing); // This would mean the kernel double-mapped pages.
743	}
744	gop.value_ptr.bytes = slice;
745	if (config.enable_memory_limit)
746	gop.value_ptr.requested_size = len;
747	gop.value_ptr.captureStackTrace(ret_addr, .alloc);
748	if (config.retain_metadata) {
749	gop.value_ptr.freed = false;
750	if (config.never_unmap) {
751	gop.value_ptr.alignment = alignment;
752	}
753	}
754
755	if (config.verbose_log) {
756	log.info("large alloc {d} bytes at {*}", .{ slice.len, slice.ptr });
757	}
758	return slice.ptr;
759	}
760
761	const slot_count = slot_counts[size_class_index];
762
763	if (self.buckets[size_class_index]) |bucket| {
764	@branchHint(.likely);
765	const slot_index = bucket.allocated_count;
766	if (slot_index < slot_count) {
767	@branchHint(.likely);
768	bucket.allocated_count = slot_index + 1;
769	const used_bits_byte = bucket.usedBits(slot_index / @bitSizeOf(usize));
770	const used_bit_index: Log2USize = @intCast(slot_index % @bitSizeOf(usize));
771	used_bits_byte.* |= (@as(usize, 1) << used_bit_index);
772	const size_class = @as(usize, 1) << @as(Log2USize, @intCast(size_class_index));
773	if (config.stack_trace_frames > 0) {
774	bucket.captureStackTrace(ret_addr, slot_count, slot_index, .alloc);
775	}
776	if (config.safety) {
777	bucket.requestedSizes(slot_count)[slot_index] = @intCast(len);
778	bucket.log2PtrAligns(slot_count)[slot_index] = alignment;
779	}
780	const page_addr = @intFromPtr(bucket) & ~(page_size - 1);
781	const addr = page_addr + slot_index * size_class;
782	if (config.verbose_log) {
783	log.info("small alloc {d} bytes at 0x{x}", .{ len, addr });
784	}
785	return @ptrFromInt(addr);
786	}
787	}
788
789	const page = self.backing_allocator.rawAlloc(page_size, page_align, @returnAddress()) orelse
790	return null;
791	const bucket: *BucketHeader = .fromPage(@intFromPtr(page), slot_count);
792	bucket.* = .{
793	.allocated_count = 1,
794	.freed_count = 0,
795	.prev = self.buckets[size_class_index],
796	.next = null,
797	};
798	if (self.buckets[size_class_index]) |old_head| {
799	old_head.next = bucket;
800	}
801	self.buckets[size_class_index] = bucket;
802
803	if (!config.backing_allocator_zeroes) {
804	@memset(@as([*]usize, @as(*[1]usize, bucket.usedBits(0)))[0..usedBitsCount(slot_count)], 0);
805	if (config.safety) @memset(bucket.requestedSizes(slot_count), 0);
806	}
807
808	bucket.usedBits(0).* = 0b1;
809
810	if (config.stack_trace_frames > 0) {
811	bucket.captureStackTrace(ret_addr, slot_count, 0, .alloc);
812	}
813
814	if (config.safety) {
815	bucket.requestedSizes(slot_count)[0] = @intCast(len);
816	bucket.log2PtrAligns(slot_count)[0] = alignment;
817	}
818
819	if (config.verbose_log) {
820	log.info("small alloc {d} bytes at 0x{x}", .{ len, @intFromPtr(page) });
821	}
822
823	return page;
824	}
825
826	fn resize(
827	context: *anyopaque,
828	memory: []u8,
829	alignment: mem.Alignment,
830	new_len: usize,
831	return_address: usize,
832	) bool {
833	const self: *Self = @ptrCast(@alignCast(context));
834	if (have_mutex) std.Io.Threaded.mutexLock(&self.mutex);
835	defer if (have_mutex) std.Io.Threaded.mutexUnlock(&self.mutex);
836
837	const size_class_index: usize = @max(@bitSizeOf(usize) - @clz(memory.len - 1), @backingInt(alignment));
838	if (size_class_index >= self.buckets.len) {
839	return self.resizeLarge(memory, alignment, new_len, return_address, false) != null;
840	} else {
841	return resizeSmall(self, memory, alignment, new_len, return_address, size_class_index);
842	}
843	}
844
845	fn remap(
846	context: *anyopaque,
847	memory: []u8,
848	alignment: mem.Alignment,
849	new_len: usize,
850	return_address: usize,
851	) ?[*]u8 {
852	const self: *Self = @ptrCast(@alignCast(context));
853	if (have_mutex) std.Io.Threaded.mutexLock(&self.mutex);
854	defer if (have_mutex) std.Io.Threaded.mutexUnlock(&self.mutex);
855
856	const size_class_index: usize = @max(@bitSizeOf(usize) - @clz(memory.len - 1), @backingInt(alignment));
857	if (size_class_index >= self.buckets.len) {
858	return self.resizeLarge(memory, alignment, new_len, return_address, true);
859	} else {
860	return if (resizeSmall(self, memory, alignment, new_len, return_address, size_class_index)) memory.ptr else null;
861	}
862	}
863
864	fn free(
865	context: *anyopaque,
866	old_memory: []u8,
867	alignment: mem.Alignment,
868	return_address: usize,
869	) void {
870	const self: *Self = @ptrCast(@alignCast(context));
871	if (have_mutex) std.Io.Threaded.mutexLock(&self.mutex);
872	defer if (have_mutex) std.Io.Threaded.mutexUnlock(&self.mutex);
873
874	const size_class_index: usize = @max(@bitSizeOf(usize) - @clz(old_memory.len - 1), @backingInt(alignment));
875	if (size_class_index >= self.buckets.len) {
876	@branchHint(.unlikely);
877	self.freeLarge(old_memory, alignment, return_address);
878	return;
879	}
880
881	const slot_count = slot_counts[size_class_index];
882	const freed_addr = @intFromPtr(old_memory.ptr);
883	const page_addr = freed_addr & ~(page_size - 1);
884	const bucket: *BucketHeader = .fromPage(page_addr, slot_count);
885	if (bucket.canary != config.canary) @panic("Invalid free");
886	const page_offset = freed_addr - page_addr;
887	const size_class = @as(usize, 1) << @as(Log2USize, @intCast(size_class_index));
888	const slot_index: SlotIndex = @intCast(page_offset / size_class);
889	const used_byte_index = slot_index / @bitSizeOf(usize);
890	const used_bit_index: Log2USize = @intCast(slot_index % @bitSizeOf(usize));
891	const used_byte = bucket.usedBits(used_byte_index);
892	const is_used = @as(u1, @truncate(used_byte.* >> used_bit_index)) != 0;
893	if (!is_used) {
894	if (config.safety) {
895	reportDoubleFree(
896	return_address,
897	bucketStackTrace(bucket, slot_count, slot_index, .alloc),
898	bucketStackTrace(bucket, slot_count, slot_index, .free),
899	);
900	// Recoverable since this is a free.
901	return;
902	} else {
903	unreachable;
904	}
905	}
906
907	// Definitely an in-use small alloc now.
908	if (config.safety) {
909	const requested_size = bucket.requestedSizes(slot_count)[slot_index];
910	if (requested_size == 0) @panic("Invalid free");
911	const slot_alignment = bucket.log2PtrAligns(slot_count)[slot_index];
912	if (old_memory.len != requested_size or alignment != slot_alignment) {
913	var addr_buf: [stack_n]usize = undefined;
914	const free_stack_trace = std.debug.captureCurrentStackTrace(.{ .first_address = return_address }, &addr_buf);
915	if (old_memory.len != requested_size) {
916	@branchHint(.cold);
917	log.err("Allocation size {d} bytes does not match free size {d}. Allocation: {f} Free: {f}", .{
918	requested_size,
919	old_memory.len,
920	std.debug.FormatStackTrace{
921	.stack_trace = bucketStackTrace(bucket, slot_count, slot_index, .alloc),
922	.terminal_mode = std.log.terminalMode(),
923	},
924	std.debug.FormatStackTrace{
925	.stack_trace = free_stack_trace,
926	.terminal_mode = std.log.terminalMode(),
927	},
928	});
929	}
930	if (alignment != slot_alignment) {
931	@branchHint(.cold);
932	log.err("Allocation alignment {d} does not match free alignment {d}. Allocation: {f} Free: {f}", .{
933	slot_alignment.toByteUnits(),
934	alignment.toByteUnits(),
935	std.debug.FormatStackTrace{
936	.stack_trace = bucketStackTrace(bucket, slot_count, slot_index, .alloc),
937	.terminal_mode = std.log.terminalMode(),
938	},
939	std.debug.FormatStackTrace{
940	.stack_trace = free_stack_trace,
941	.terminal_mode = std.log.terminalMode(),
942	},
943	});
944	}
945	}
946	}
947
948	if (config.enable_memory_limit) {
949	self.total_requested_bytes -= old_memory.len;
950	}
951
952	if (config.stack_trace_frames > 0) {
953	// Capture stack trace to be the "first free", in case a double free happens.
954	bucket.captureStackTrace(return_address, slot_count, slot_index, .free);
955	}
956
957	used_byte.* &= ~(@as(usize, 1) << used_bit_index);
958	if (config.safety) {
959	bucket.requestedSizes(slot_count)[slot_index] = 0;
960	}
961	bucket.freed_count += 1;
962	if (bucket.freed_count == bucket.allocated_count) {
963	if (bucket.prev) |prev| {
964	prev.next = bucket.next;
965	}
966
967	if (bucket.next) |next| {
968	assert(self.buckets[size_class_index] != bucket);
969	next.prev = bucket.prev;
970	} else {
971	assert(self.buckets[size_class_index] == bucket);
972	self.buckets[size_class_index] = bucket.prev;
973	}
974
975	if (!config.never_unmap) {
976	const page: [*]align(page_size) u8 = @ptrFromInt(page_addr);
977	self.backing_allocator.rawFree(page[0..page_size], page_align, @returnAddress());
978	}
979	}
980	if (config.verbose_log) {
981	log.info("small free {d} bytes at {*}", .{ old_memory.len, old_memory.ptr });
982	}
983	}
984
985	fn resizeSmall(
986	self: *Self,
987	memory: []u8,
988	alignment: mem.Alignment,
989	new_len: usize,
990	return_address: usize,
991	size_class_index: usize,
992	) bool {
993	const new_size_class_index: usize = @max(@bitSizeOf(usize) - @clz(new_len - 1), @backingInt(alignment));
994	if (!config.safety) {
995	if (new_size_class_index != size_class_index) return false;
996	// Still account for total even if safety is off
997	if (config.enable_memory_limit)
998	self.total_requested_bytes = self.total_requested_bytes - memory.len + new_len;
999	return true;
1000	}
1001
1002	const slot_count = slot_counts[size_class_index];
1003	const memory_addr = @intFromPtr(memory.ptr);
1004	const page_addr = memory_addr & ~(page_size - 1);
1005	const bucket: *BucketHeader = .fromPage(page_addr, slot_count);
1006	if (bucket.canary != config.canary) @panic("Invalid free");
1007	const page_offset = memory_addr - page_addr;
1008	const size_class = @as(usize, 1) << @as(Log2USize, @intCast(size_class_index));
1009	const slot_index: SlotIndex = @intCast(page_offset / size_class);
1010	const used_byte_index = slot_index / @bitSizeOf(usize);
1011	const used_bit_index: Log2USize = @intCast(slot_index % @bitSizeOf(usize));
1012	const used_byte = bucket.usedBits(used_byte_index);
1013	const is_used = @as(u1, @truncate(used_byte.* >> used_bit_index)) != 0;
1014	if (!is_used) {
1015	reportDoubleFree(
1016	return_address,
1017	bucketStackTrace(bucket, slot_count, slot_index, .alloc),
1018	bucketStackTrace(bucket, slot_count, slot_index, .free),
1019	);
1020	// Recoverable since this is a free.
1021	return false;
1022	}
1023
1024	// Definitely an in-use small alloc now.
1025	const requested_size = bucket.requestedSizes(slot_count)[slot_index];
1026	if (requested_size == 0) @panic("Invalid free");
1027	const slot_alignment = bucket.log2PtrAligns(slot_count)[slot_index];
1028	if (memory.len != requested_size or alignment != slot_alignment) {
1029	var addr_buf: [stack_n]usize = undefined;
1030	const free_stack_trace = std.debug.captureCurrentStackTrace(.{ .first_address = return_address }, &addr_buf);
1031	if (memory.len != requested_size) {
1032	@branchHint(.cold);
1033	log.err("Allocation size {d} bytes does not match free size {d}. Allocation: {f} Free: {f}", .{
1034	requested_size,
1035	memory.len,
1036	std.debug.FormatStackTrace{
1037	.stack_trace = bucketStackTrace(bucket, slot_count, slot_index, .alloc),
1038	.terminal_mode = std.log.terminalMode(),
1039	},
1040	std.debug.FormatStackTrace{
1041	.stack_trace = free_stack_trace,
1042	.terminal_mode = std.log.terminalMode(),
1043	},
1044	});
1045	}
1046	if (alignment != slot_alignment) {
1047	@branchHint(.cold);
1048	log.err("Allocation alignment {d} does not match free alignment {d}. Allocation: {f} Free: {f}", .{
1049	slot_alignment.toByteUnits(),
1050	alignment.toByteUnits(),
1051	std.debug.FormatStackTrace{
1052	.stack_trace = bucketStackTrace(bucket, slot_count, slot_index, .alloc),
1053	.terminal_mode = std.log.terminalMode(),
1054	},
1055	std.debug.FormatStackTrace{
1056	.stack_trace = free_stack_trace,
1057	.terminal_mode = std.log.terminalMode(),
1058	},
1059	});
1060	}
1061	}
1062
1063	if (new_size_class_index != size_class_index) return false;
1064
1065	const prev_req_bytes = self.total_requested_bytes;
1066	if (config.enable_memory_limit) {
1067	const new_req_bytes = prev_req_bytes - memory.len + new_len;
1068	if (new_req_bytes > prev_req_bytes and new_req_bytes > self.requested_memory_limit) {
1069	return false;
1070	}
1071	self.total_requested_bytes = new_req_bytes;
1072	}
1073
1074	if (memory.len > new_len) @memset(memory[new_len..], undefined);
1075	if (config.verbose_log)
1076	log.info("small resize {d} bytes at {*} to {d}", .{ memory.len, memory.ptr, new_len });
1077
1078	if (config.safety)
1079	bucket.requestedSizes(slot_count)[slot_index] = @intCast(new_len);
1080
1081	if (config.resize_stack_traces)
1082	bucket.captureStackTrace(return_address, slot_count, slot_index, .alloc);
1083
1084	return true;
1085	}
1086	};
1087	}
1088
1089	const TraceKind = enum {
1090	alloc,
1091	free,
1092	};
1093
1094	const test_config: Config = .{};
1095
1096	test "small allocations - free in same order" {
1097	var gpa = DebugAllocator(test_config){};
1098	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1099	const allocator = gpa.allocator();
1100
1101	var list = std.array_list.Managed(*u64).init(std.testing.allocator);
1102	defer list.deinit();
1103
1104	var i: usize = 0;
1105	while (i < 513) : (i += 1) {
1106	const ptr = try allocator.create(u64);
1107	try list.append(ptr);
1108	}
1109
1110	for (list.items) |ptr| {
1111	allocator.destroy(ptr);
1112	}
1113	}
1114
1115	test "small allocations - free in reverse order" {
1116	var gpa = DebugAllocator(test_config){};
1117	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1118	const allocator = gpa.allocator();
1119
1120	var list = std.array_list.Managed(*u64).init(std.testing.allocator);
1121	defer list.deinit();
1122
1123	var i: usize = 0;
1124	while (i < 513) : (i += 1) {
1125	const ptr = try allocator.create(u64);
1126	try list.append(ptr);
1127	}
1128
1129	while (list.pop()) |ptr| {
1130	allocator.destroy(ptr);
1131	}
1132	}
1133
1134	test "large allocations" {
1135	var gpa = DebugAllocator(test_config){};
1136	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1137	const allocator = gpa.allocator();
1138
1139	const ptr1 = try allocator.alloc(u64, 42768);
1140	const ptr2 = try allocator.alloc(u64, 52768);
1141	allocator.free(ptr1);
1142	const ptr3 = try allocator.alloc(u64, 62768);
1143	allocator.free(ptr3);
1144	allocator.free(ptr2);
1145	}
1146
1147	test "very large allocation" {
1148	var gpa = DebugAllocator(test_config){};
1149	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1150	const allocator = gpa.allocator();
1151
1152	try std.testing.expectError(error.OutOfMemory, allocator.alloc(u8, math.maxInt(usize)));
1153	}
1154
1155	test "realloc" {
1156	var gpa = DebugAllocator(test_config){};
1157	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1158	const allocator = gpa.allocator();
1159
1160	var slice = try allocator.alignedAlloc(u8, .of(u32), 1);
1161	defer allocator.free(slice);
1162	slice[0] = 0x12;
1163
1164	// This reallocation should keep its pointer address.
1165	const old_slice = slice;
1166	slice = try allocator.realloc(slice, 2);
1167	try std.testing.expect(old_slice.ptr == slice.ptr);
1168	try std.testing.expect(slice[0] == 0x12);
1169	slice[1] = 0x34;
1170
1171	// This requires upgrading to a larger size class
1172	slice = try allocator.realloc(slice, 17);
1173	try std.testing.expect(slice[0] == 0x12);
1174	try std.testing.expect(slice[1] == 0x34);
1175	}
1176
1177	test "shrink" {
1178	var gpa: DebugAllocator(test_config) = .{};
1179	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1180	const allocator = gpa.allocator();
1181
1182	var slice = try allocator.alloc(u8, 20);
1183	defer allocator.free(slice);
1184
1185	@memset(slice, 0x11);
1186
1187	try std.testing.expect(allocator.resize(slice, 17));
1188	slice = slice[0..17];
1189
1190	for (slice) |b| {
1191	try std.testing.expect(b == 0x11);
1192	}
1193
1194	// Does not cross size class boundaries when shrinking.
1195	try std.testing.expect(!allocator.resize(slice, 16));
1196	}
1197
1198	test "large object - grow" {
1199	if (builtin.target.cpu.arch.isWasm()) {
1200	// Not expected to pass on targets that do not have memory mapping.
1201	return error.SkipZigTest;
1202	}
1203	var gpa: DebugAllocator(test_config) = .{};
1204	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1205	const allocator = gpa.allocator();
1206
1207	var slice1 = try allocator.alloc(u8, default_page_size * 2 - 20);
1208	defer allocator.free(slice1);
1209
1210	const old = slice1;
1211	slice1 = try allocator.realloc(slice1, default_page_size * 2 - 10);
1212	try std.testing.expect(slice1.ptr == old.ptr);
1213
1214	slice1 = try allocator.realloc(slice1, default_page_size * 2);
1215	try std.testing.expect(slice1.ptr == old.ptr);
1216
1217	slice1 = try allocator.realloc(slice1, default_page_size * 2 + 1);
1218	}
1219
1220	test "realloc small object to large object" {
1221	var gpa = DebugAllocator(test_config){};
1222	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1223	const allocator = gpa.allocator();
1224
1225	var slice = try allocator.alloc(u8, 70);
1226	defer allocator.free(slice);
1227	slice[0] = 0x12;
1228	slice[60] = 0x34;
1229
1230	// This requires upgrading to a large object
1231	const large_object_size = default_page_size * 2 + 50;
1232	slice = try allocator.realloc(slice, large_object_size);
1233	try std.testing.expect(slice[0] == 0x12);
1234	try std.testing.expect(slice[60] == 0x34);
1235	}
1236
1237	test "shrink large object to large object" {
1238	var gpa: DebugAllocator(test_config) = .{};
1239	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1240	const allocator = gpa.allocator();
1241
1242	var slice = try allocator.alloc(u8, default_page_size * 2 + 50);
1243	defer allocator.free(slice);
1244	slice[0] = 0x12;
1245	slice[60] = 0x34;
1246
1247	if (!allocator.resize(slice, default_page_size * 2 + 1)) return;
1248	slice = slice.ptr[0 .. default_page_size * 2 + 1];
1249	try std.testing.expect(slice[0] == 0x12);
1250	try std.testing.expect(slice[60] == 0x34);
1251
1252	try std.testing.expect(allocator.resize(slice, default_page_size * 2 + 1));
1253	slice = slice[0 .. default_page_size * 2 + 1];
1254	try std.testing.expect(slice[0] == 0x12);
1255	try std.testing.expect(slice[60] == 0x34);
1256
1257	slice = try allocator.realloc(slice, default_page_size * 2);
1258	try std.testing.expect(slice[0] == 0x12);
1259	try std.testing.expect(slice[60] == 0x34);
1260	}
1261
1262	test "shrink large object to large object with larger alignment" {
1263	if (builtin.os.tag == .wasi) {
1264	// https://github.com/ziglang/zig/issues/22731
1265	return error.SkipZigTest;
1266	}
1267
1268	var gpa: DebugAllocator(test_config) = .{};
1269	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1270	const allocator = gpa.allocator();
1271
1272	var debug_buffer: [1000]u8 = undefined;
1273	var fba = std.heap.FixedBufferAllocator.init(&debug_buffer);
1274	const debug_allocator = fba.allocator();
1275
1276	const alloc_size = default_page_size * 2 + 50;
1277	var slice = try allocator.alignedAlloc(u8, .@"16", alloc_size);
1278	defer allocator.free(slice);
1279
1280	const big_alignment: usize = default_page_size * 2;
1281	// This loop allocates until we find a page that is not aligned to the big
1282	// alignment. Then we shrink the allocation after the loop, but increase the
1283	// alignment to the higher one, that we know will force it to realloc.
1284	var stuff_to_free = std.array_list.Managed([]align(16) u8).init(debug_allocator);
1285	while (mem.isAligned(@intFromPtr(slice.ptr), big_alignment)) {
1286	try stuff_to_free.append(slice);
1287	slice = try allocator.alignedAlloc(u8, .@"16", alloc_size);
1288	}
1289	while (stuff_to_free.pop()) |item| {
1290	allocator.free(item);
1291	}
1292	slice[0] = 0x12;
1293	slice[60] = 0x34;
1294
1295	slice = try allocator.reallocAdvanced(slice, big_alignment, alloc_size / 2);
1296	try std.testing.expect(slice[0] == 0x12);
1297	try std.testing.expect(slice[60] == 0x34);
1298	}
1299
1300	test "realloc large object to small object" {
1301	var gpa = DebugAllocator(test_config){};
1302	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1303	const allocator = gpa.allocator();
1304
1305	var slice = try allocator.alloc(u8, default_page_size * 2 + 50);
1306	defer allocator.free(slice);
1307	slice[0] = 0x12;
1308	slice[16] = 0x34;
1309
1310	slice = try allocator.realloc(slice, 19);
1311	try std.testing.expect(slice[0] == 0x12);
1312	try std.testing.expect(slice[16] == 0x34);
1313	}
1314
1315	test "non-page-allocator backing allocator" {
1316	var gpa: DebugAllocator(.{
1317	.backing_allocator_zeroes = false,
1318	}) = .{
1319	.backing_allocator = std.testing.allocator,
1320	};
1321	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1322	const allocator = gpa.allocator();
1323
1324	const ptr = try allocator.create(i32);
1325	defer allocator.destroy(ptr);
1326	}
1327
1328	test "realloc large object to larger alignment" {
1329	if (builtin.os.tag == .wasi) {
1330	// https://github.com/ziglang/zig/issues/22731
1331	return error.SkipZigTest;
1332	}
1333
1334	var gpa = DebugAllocator(test_config){};
1335	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1336	const allocator = gpa.allocator();
1337
1338	var debug_buffer: [1000]u8 = undefined;
1339	var fba = std.heap.FixedBufferAllocator.init(&debug_buffer);
1340	const debug_allocator = fba.allocator();
1341
1342	var slice = try allocator.alignedAlloc(u8, .@"16", default_page_size * 2 + 50);
1343	defer allocator.free(slice);
1344
1345	const big_alignment: usize = default_page_size * 2;
1346	// This loop allocates until we find a page that is not aligned to the big alignment.
1347	var stuff_to_free = std.array_list.Managed([]align(16) u8).init(debug_allocator);
1348	while (mem.isAligned(@intFromPtr(slice.ptr), big_alignment)) {
1349	try stuff_to_free.append(slice);
1350	slice = try allocator.alignedAlloc(u8, .@"16", default_page_size * 2 + 50);
1351	}
1352	while (stuff_to_free.pop()) |item| {
1353	allocator.free(item);
1354	}
1355	slice[0] = 0x12;
1356	slice[16] = 0x34;
1357
1358	slice = try allocator.reallocAdvanced(slice, 32, default_page_size * 2 + 100);
1359	try std.testing.expect(slice[0] == 0x12);
1360	try std.testing.expect(slice[16] == 0x34);
1361
1362	slice = try allocator.reallocAdvanced(slice, 32, default_page_size * 2 + 25);
1363	try std.testing.expect(slice[0] == 0x12);
1364	try std.testing.expect(slice[16] == 0x34);
1365
1366	slice = try allocator.reallocAdvanced(slice, big_alignment, default_page_size * 2 + 100);
1367	try std.testing.expect(slice[0] == 0x12);
1368	try std.testing.expect(slice[16] == 0x34);
1369	}
1370
1371	test "large object rejects shrinking to small" {
1372	if (builtin.target.cpu.arch.isWasm()) {
1373	// Not expected to pass on targets that do not have memory mapping.
1374	return error.SkipZigTest;
1375	}
1376
1377	var failing_allocator = std.testing.FailingAllocator.init(std.heap.page_allocator, .{ .fail_index = 3 });
1378	var gpa: DebugAllocator(.{}) = .{
1379	.backing_allocator = failing_allocator.allocator(),
1380	};
1381	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1382	const allocator = gpa.allocator();
1383
1384	var slice = try allocator.alloc(u8, default_page_size * 2 + 50);
1385	defer allocator.free(slice);
1386	slice[0] = 0x12;
1387	slice[3] = 0x34;
1388
1389	try std.testing.expect(!allocator.resize(slice, 4));
1390	try std.testing.expect(slice[0] == 0x12);
1391	try std.testing.expect(slice[3] == 0x34);
1392	}
1393
1394	test "objects of size 1024 and 2048" {
1395	var gpa = DebugAllocator(test_config){};
1396	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1397	const allocator = gpa.allocator();
1398
1399	const slice = try allocator.alloc(u8, 1025);
1400	const slice2 = try allocator.alloc(u8, 3000);
1401
1402	allocator.free(slice);
1403	allocator.free(slice2);
1404	}
1405
1406	test "setting a memory cap" {
1407	var gpa = DebugAllocator(.{ .enable_memory_limit = true }){};
1408	defer std.testing.expect(gpa.deinit() == .ok) catch @panic("leak");
1409	const allocator = gpa.allocator();
1410
1411	gpa.requested_memory_limit = 1010;
1412
1413	const small = try allocator.create(i32);
1414	try std.testing.expect(gpa.total_requested_bytes == 4);
1415
1416	const big = try allocator.alloc(u8, 1000);
1417	try std.testing.expect(gpa.total_requested_bytes == 1004);
1418
1419	try std.testing.expectError(error.OutOfMemory, allocator.create(u64));
1420
1421	allocator.destroy(small);
1422	try std.testing.expect(gpa.total_requested_bytes == 1000);
1423
1424	allocator.free(big);
1425	try std.testing.expect(gpa.total_requested_bytes == 0);
1426
1427	const exact = try allocator.alloc(u8, 1010);
1428	try std.testing.expect(gpa.total_requested_bytes == 1010);
1429	allocator.free(exact);
1430	}
1431
1432	test "large allocations count requested size not backing size" {
1433	var gpa: DebugAllocator(.{ .enable_memory_limit = true }) = .{};
1434	const allocator = gpa.allocator();
1435
1436	var buf = try allocator.alignedAlloc(u8, .@"1", default_page_size + 1);
1437	try std.testing.expectEqual(default_page_size + 1, gpa.total_requested_bytes);
1438	buf = try allocator.realloc(buf, 1);
1439	try std.testing.expectEqual(1, gpa.total_requested_bytes);
1440	buf = try allocator.realloc(buf, 2);
1441	try std.testing.expectEqual(2, gpa.total_requested_bytes);
1442	}
1443
1444	test "retain metadata and never unmap" {
1445	var gpa = std.heap.DebugAllocator(.{
1446	.safety = true,
1447	.never_unmap = true,
1448	.retain_metadata = true,
1449	}){};
1450	defer std.debug.assert(gpa.deinit() == .ok);
1451	const allocator = gpa.allocator();
1452
1453	const alloc = try allocator.alloc(u8, 8);
1454	allocator.free(alloc);
1455
1456	const alloc2 = try allocator.alloc(u8, 8);
1457	allocator.free(alloc2);
1458	}