lib/deadalloc/src/allocator.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const sys_thread = @import("sys").thread;
3 const size_class = @import("class.zig");
4 const report_mod = @import("report.zig");
5 const exterminator = @import("exterminator.zig");
6
7 const Allocator = std.mem.Allocator;
8 const Alignment = std.mem.Alignment;
9
10 pub const Mode = enum {
11 diehard,
12 dieharder,
13 exterminator,
14 };
15
16 pub const DiagnosticConfig = struct {
17 enabled: bool = false,
18 red_zone_bytes: usize = 16,
19 quarantine_epochs: u64 = 16,
20 };
21
22 pub const Config = struct {
23 mode: Mode = .diehard,
24 numerator: usize = 8,
25 denominator: usize = 7,
26 seed: u64 = 0xd1e4_a110_cafe_f00d,
27 thread_safe: bool = true,
28 min_chunk_blocks: usize = 64,
29 diagnostics: DiagnosticConfig = .{},
30 repairs: exterminator.RepairTable = .{},
31
32 pub fn diagnostic(mode: Mode) Config {
33 return .{
34 .mode = mode,
35 .diagnostics = .{ .enabled = true },
36 };
37 }
38
39 pub fn repaired(current: Config, report: report_mod.Report) Config {
40 var next = current;
41 const policy = exterminator.RepairPolicy.fromReport(report, .{
42 .red_zone_bytes = current.diagnosticRedZoneBytes(),
43 .quarantine_epochs = current.quarantineEpochs(),
44 .repairs = current.repairs,
45 });
46 next.mode = .exterminator;
47 next.diagnostics.enabled = true;
48 next.diagnostics.red_zone_bytes = policy.red_zone_bytes;
49 next.diagnostics.quarantine_epochs = policy.quarantine_epochs;
50 next.repairs = policy.repairs;
51 return next;
52 }
53
54 fn diagnosticRedZoneBytes(self: Config) usize {
55 if (self.diagnostics.enabled or self.mode == .exterminator) return self.diagnostics.red_zone_bytes;
56 return 0;
57 }
58
59 fn quarantineEpochs(self: Config) u64 {
60 return switch (self.mode) {
61 .diehard => 0,
62 .dieharder => @max(self.diagnostics.quarantine_epochs, 8),
63 .exterminator => @max(self.diagnostics.quarantine_epochs, 1),
64 };
65 }
66
67 fn repairPadding(self: Config, allocation_return_address: usize) usize {
68 if (self.mode != .exterminator) return 0;
69 return self.repairs.overflowPadding(allocation_return_address);
70 }
71
72 fn repairQuarantineEpochs(self: Config, allocation_return_address: usize, free_return_address: usize) u64 {
73 const base = self.quarantineEpochs();
74 if (self.mode != .exterminator) return base;
75 return @max(base, self.repairs.lifeExtension(allocation_return_address, free_return_address));
76 }
77 };
78
79 pub const Report = report_mod.Report;
80 pub const Issue = report_mod.Issue;
81 pub const IssueKind = report_mod.IssueKind;
82 pub const RepairTable = exterminator.RepairTable;
83
84 pub const min_alignment = size_class.min_alignment;
85 pub const page_size = size_class.page_size;
86 pub const max_small_size = size_class.max_small_size;
87 pub const class_sizes = size_class.sizes;
88
89 const canary_byte: u8 = 0xa9;
90 const freed_byte: u8 = 0xdf;
91 const allocated_byte: u8 = 0xcd;
92
93 const BlockState = enum(u8) {
94 fresh,
95 live,
96 free,
97 };
98
99 const BlockRef = struct {
100 chunk: *Chunk,
101 index: usize,
102 };
103
104 const AllocationKind = enum {
105 small,
106 large,
107 };
108
109 const AllocationRecord = struct {
110 kind: AllocationKind,
111 address: usize,
112 requested_len: usize,
113 repair_padding: usize = 0,
114 block_size: usize,
115 backing_len: usize,
116 alignment: Alignment,
117 allocation_id: u64,
118 allocation_return_address: usize,
119 free_return_address: usize = 0,
120 small_block: ?BlockRef = null,
121 free_epoch: u64 = 0,
122 free_quarantine_epochs: u64 = 0,
123 free_pattern: u64 = 0,
124 free_issue_reported: bool = false,
125 canary_issue_reported: bool = false,
126 };
127
128 const Chunk = struct {
129 class_index: usize,
130 block_size: usize,
131 block_stride: usize,
132 capacity: usize,
133 live_count: usize,
134 base: [*]u8,
135 area_len: usize,
136 states: []BlockState,
137 requested_lens: []usize,
138 repair_paddings: []usize,
139 allocation_ids: []u64,
140 allocation_return_addresses: []usize,
141 free_return_addresses: []usize,
142 free_epochs: []u64,
143 free_quarantine_epochs: []u64,
144 free_patterns: []u64,
145 free_issue_reported: []bool,
146
147 fn blockPtr(chunk: *Chunk, index: usize) [*]u8 {
148 return chunk.base + index * chunk.block_stride;
149 }
150
151 fn isAvailable(chunk: *Chunk, index: usize, epoch: u64) bool {
152 return switch (chunk.states[index]) {
153 .fresh => true,
154 .live => false,
155 .free => epoch -% chunk.free_epochs[index] >= chunk.free_quarantine_epochs[index],
156 };
157 }
158 };
159
160 const ClassState = struct {
161 chunks: std.ArrayList(*Chunk) = .empty,
162 capacity: usize = 0,
163 live_count: usize = 0,
164 next_chunk_blocks: usize = 0,
165
166 fn deinit(class_state: *ClassState, allocator: Allocator, owner: *DeadAllocator) void {
167 for (class_state.chunks.items) |chunk| owner.destroyChunk(chunk);
168 class_state.chunks.deinit(allocator);
169 class_state.* = .{};
170 }
171 };
172
173 pub const DeadAllocator = struct {
174 backing_allocator: Allocator,
175 config: Config,
176 classes: [size_class.count]ClassState = @as([size_class.count]ClassState, @splat(.{})),
177 live: std.AutoHashMap(usize, AllocationRecord),
178 known: std.AutoHashMap(usize, AllocationRecord),
179 page_owners: std.AutoHashMap(usize, usize),
180 large_quarantine: std.ArrayList(AllocationRecord) = .empty,
181 prng: std.Random.DefaultPrng,
182 mutex: std.atomic.Mutex = .unlocked,
183 epoch: u64 = 1,
184 next_allocation_id: u64 = 1,
185 counters: report_mod.Counters = .{},
186 last_issue: ?Issue = null,
187 issues: report_mod.IssueLog = .{},
188
189 const Self = @This();
190
191 pub fn init(backing_allocator: Allocator, config: Config) Self {
192 std.debug.assert(config.numerator >= config.denominator);
193 std.debug.assert(config.denominator > 0);
194 return .{
195 .backing_allocator = backing_allocator,
196 .config = config,
197 .live = std.AutoHashMap(usize, AllocationRecord).init(backing_allocator),
198 .known = std.AutoHashMap(usize, AllocationRecord).init(backing_allocator),
199 .page_owners = std.AutoHashMap(usize, usize).init(backing_allocator),
200 .prng = std.Random.DefaultPrng.init(config.seed),
201 };
202 }
203
204 pub fn deinit(self: *Self) void {
205 if (self.diagnosticsActive()) {
206 self.counters.invalid_free += 0;
207 }
208 self.releaseLiveLargeAllocations(@returnAddress());
209 for (self.large_quarantine.items) |record| self.releaseLarge(record, @returnAddress());
210 self.large_quarantine.deinit(self.backing_allocator);
211 for (&self.classes) |*class_state| class_state.deinit(self.backing_allocator, self);
212 self.live.deinit();
213 self.known.deinit();
214 self.page_owners.deinit();
215 self.* = undefined;
216 }
217
218 pub fn allocator(self: *Self) Allocator {
219 return .{
220 .ptr = self,
221 .vtable = &vtable,
222 };
223 }
224
225 pub fn report(self: *Self) Report {
226 self.lock();
227 defer self.unlock();
228 const ret_addr = @returnAddress();
229 self.scanLiveCanaries(ret_addr);
230 self.scanFreedMemory(ret_addr);
231 self.drainLargeQuarantine(ret_addr);
232 return self.reportUnlocked(ret_addr);
233 }
234
235 fn reportUnlocked(self: *Self, ret_addr: usize) Report {
236 var live_bytes: usize = 0;
237 var leak_issue: ?Issue = null;
238 var issues = self.issues;
239 var iterator = self.live.valueIterator();
240 while (iterator.next()) |record| {
241 live_bytes += record.requested_len;
242 const issue: Issue = .{
243 .kind = .leak,
244 .address = record.address,
245 .requested_len = record.requested_len,
246 .block_size = record.block_size,
247 .allocation_id = record.allocation_id,
248 .allocation_return_address = record.allocation_return_address,
249 .return_address = ret_addr,
250 };
251 if (leak_issue == null) leak_issue = issue;
252 issues.append(issue);
253 }
254 return .{
255 .counters = self.counters,
256 .live_allocations = self.live.count(),
257 .live_bytes = live_bytes,
258 .leak_count = self.live.count(),
259 .leak_issue = leak_issue,
260 .last_issue = self.last_issue,
261 .issues = issues,
262 };
263 }
264
265 pub fn rawAlloc(self: *Self, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {
266 self.lock();
267 defer self.unlock();
268 self.drainLargeQuarantine(ret_addr);
269
270 const repair_padding = self.config.repairPadding(ret_addr);
271 const total_len = self.totalAllocationLen(len, repair_padding) orelse return null;
272 const class_index = size_class.indexFor(total_len, alignment) orelse return self.allocateLarge(len, repair_padding, total_len, alignment, ret_addr);
273 return self.allocateSmall(class_index, len, repair_padding, total_len, alignment, ret_addr) catch null;
274 }
275
276 pub fn rawResize(self: *Self, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) bool {
277 self.lock();
278 defer self.unlock();
279 self.drainLargeQuarantine(ret_addr);
280
281 const address = @intFromPtr(memory.ptr);
282 const record_ptr = self.live.getPtr(address) orelse {
283 self.recordUnknownFree(address, memory.len, alignment, ret_addr);
284 return false;
285 };
286 if (memory.len != record_ptr.requested_len) {
287 self.recordIssue(.{
288 .kind = .size_mismatch,
289 .address = address,
290 .requested_len = memory.len,
291 .block_size = record_ptr.block_size,
292 .allocation_id = record_ptr.allocation_id,
293 .allocation_return_address = record_ptr.allocation_return_address,
294 .free_return_address = record_ptr.free_return_address,
295 .free_epoch = record_ptr.free_epoch,
296 .return_address = ret_addr,
297 });
298 }
299
300 _ = self.checkCanary(record_ptr, ret_addr);
301
302 const total_len = self.totalAllocationLen(new_len, record_ptr.repair_padding) orelse return false;
303 if (total_len > record_ptr.block_size) return false;
304
305 if (record_ptr.kind == .small) {
306 const block = record_ptr.small_block.?;
307 block.chunk.requested_lens[block.index] = new_len;
308 }
309 record_ptr.requested_len = new_len;
310 record_ptr.canary_issue_reported = false;
311 if (self.known.getPtr(address)) |known| known.requested_len = new_len;
312 self.installCanary(@ptrFromInt(address), new_len, record_ptr.repair_padding, record_ptr.block_size);
313 return true;
314 }
315
316 pub fn rawRemap(self: *Self, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
317 if (self.rawResize(memory, alignment, new_len, ret_addr)) return memory.ptr;
318
319 const address = @intFromPtr(memory.ptr);
320 const old_len = old_len: {
321 self.lock();
322 defer self.unlock();
323 const record = self.live.get(address) orelse return null;
324 break :old_len record.requested_len;
325 };
326
327 const new_ptr = self.rawAlloc(new_len, alignment, ret_addr) orelse return null;
328 const copy_len = @min(old_len, new_len);
329 const old_ptr: [*]u8 = @ptrFromInt(address);
330 @memcpy(new_ptr[0..copy_len], old_ptr[0..copy_len]);
331 self.rawFree(old_ptr[0..old_len], alignment, ret_addr);
332 return new_ptr;
333 }
334
335 pub fn rawFree(self: *Self, memory: []u8, alignment: Alignment, ret_addr: usize) void {
336 self.lock();
337 defer self.unlock();
338
339 const address = @intFromPtr(memory.ptr);
340 var record = self.live.fetchRemove(address) orelse {
341 self.recordUnknownFree(address, memory.len, alignment, ret_addr);
342 return;
343 };
344
345 if (memory.len != record.value.requested_len) {
346 self.recordIssue(.{
347 .kind = .size_mismatch,
348 .address = address,
349 .requested_len = memory.len,
350 .block_size = record.value.block_size,
351 .allocation_id = record.value.allocation_id,
352 .allocation_return_address = record.value.allocation_return_address,
353 .free_return_address = record.value.free_return_address,
354 .free_epoch = record.value.free_epoch,
355 .return_address = ret_addr,
356 });
357 }
358
359 _ = self.checkCanary(&record.value, ret_addr);
360
361 switch (record.value.kind) {
362 .small => self.freeSmall(&record.value, ret_addr),
363 .large => self.freeLarge(&record.value, ret_addr),
364 }
365
366 if (self.known.getPtr(address)) |known| known.* = record.value;
367 }
368
369 fn allocateSmall(
370 self: *Self,
371 class_index: usize,
372 requested_len: usize,
373 repair_padding: usize,
374 total_len: usize,
375 alignment: Alignment,
376 ret_addr: usize,
377 ) ![*]u8 {
378 const class_state = &self.classes[class_index];
379 if (self.shouldGrow(class_state)) try self.addChunk(class_index, ret_addr);
380
381 const total_capacity = class_state.capacity;
382 if (total_capacity == 0) return error.OutOfMemory;
383
384 var attempts: usize = 0;
385 while (attempts < total_capacity) : (attempts += 1) {
386 const ordinal = self.prng.random().int(usize) % total_capacity;
387 if (try self.tryAllocateSmallBlock(
388 class_state,
389 ordinal,
390 requested_len,
391 repair_padding,
392 total_len,
393 alignment,
394 ret_addr,
395 )) |ptr| return ptr;
396 }
397
398 var ordinal = self.prng.random().int(usize) % total_capacity;
399 var probes: usize = 0;
400 while (probes < total_capacity) : (probes += 1) {
401 if (try self.tryAllocateSmallBlock(
402 class_state,
403 ordinal,
404 requested_len,
405 repair_padding,
406 total_len,
407 alignment,
408 ret_addr,
409 )) |ptr| return ptr;
410 ordinal = (ordinal + 1) % total_capacity;
411 }
412
413 try self.addChunk(class_index, ret_addr);
414 return self.allocateSmall(class_index, requested_len, repair_padding, total_len, alignment, ret_addr);
415 }
416
417 fn tryAllocateSmallBlock(
418 self: *Self,
419 class_state: *ClassState,
420 ordinal: usize,
421 requested_len: usize,
422 repair_padding: usize,
423 total_len: usize,
424 alignment: Alignment,
425 ret_addr: usize,
426 ) !?[*]u8 {
427 const selected = self.blockByOrdinal(class_state, ordinal);
428 const chunk = selected.chunk;
429 const index = selected.index;
430 if (!chunk.isAvailable(index, self.epoch)) return null;
431
432 const ptr = chunk.blockPtr(index);
433 if (!std.mem.isAligned(@intFromPtr(ptr), alignment.toByteUnits())) return null;
434
435 if (self.diagnosticsActive() and chunk.states[index] == .free and !chunk.free_issue_reported[index]) {
436 chunk.free_issue_reported[index] = self.checkFreedPattern(
437 ptr,
438 chunk.block_size,
439 chunk.requested_lens[index],
440 chunk.allocation_ids[index],
441 chunk.allocation_return_addresses[index],
442 chunk.free_return_addresses[index],
443 chunk.free_epochs[index],
444 chunk.free_patterns[index],
445 ret_addr,
446 );
447 }
448
449 try self.ensurePageOwnerCapacityFor(@intFromPtr(ptr), chunk.block_size);
450
451 const allocation_id = self.nextAllocationId();
452 chunk.states[index] = .live;
453 chunk.free_issue_reported[index] = false;
454 chunk.requested_lens[index] = requested_len;
455 chunk.repair_paddings[index] = repair_padding;
456 chunk.allocation_ids[index] = allocation_id;
457 chunk.allocation_return_addresses[index] = ret_addr;
458 chunk.free_return_addresses[index] = 0;
459 chunk.live_count += 1;
460 class_state.live_count += 1;
461 self.epoch +%= 1;
462
463 @memset(ptr[0..@min(requested_len, chunk.block_size)], allocated_byte);
464 self.installCanary(ptr, requested_len, repair_padding, chunk.block_size);
465
466 const record: AllocationRecord = .{
467 .kind = .small,
468 .address = @intFromPtr(ptr),
469 .requested_len = requested_len,
470 .repair_padding = repair_padding,
471 .block_size = chunk.block_size,
472 .backing_len = total_len,
473 .alignment = alignment,
474 .allocation_id = allocation_id,
475 .allocation_return_address = ret_addr,
476 .small_block = .{ .chunk = chunk, .index = index },
477 };
478 self.live.put(record.address, record) catch {
479 var cleanup = record;
480 self.freeSmall(&cleanup, ret_addr);
481 return error.OutOfMemory;
482 };
483 self.known.put(record.address, record) catch {
484 _ = self.live.remove(record.address);
485 var cleanup = record;
486 self.freeSmall(&cleanup, ret_addr);
487 return error.OutOfMemory;
488 };
489 self.putPageOwnerAssumeCapacity(record);
490 return ptr;
491 }
492
493 fn allocateLarge(self: *Self, requested_len: usize, repair_padding: usize, backing_len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {
494 const effective_backing_len = self.largeBackingLen(backing_len) orelse return null;
495 const effective_alignment = self.largeAlignment(alignment);
496 const ptr = self.backing_allocator.rawAlloc(effective_backing_len, effective_alignment, ret_addr) orelse return null;
497 @memset(ptr[0..@min(requested_len, effective_backing_len)], allocated_byte);
498 self.installCanary(ptr, requested_len, repair_padding, effective_backing_len);
499
500 const allocation_id = self.nextAllocationId();
501 const record: AllocationRecord = .{
502 .kind = .large,
503 .address = @intFromPtr(ptr),
504 .requested_len = requested_len,
505 .repair_padding = repair_padding,
506 .block_size = effective_backing_len,
507 .backing_len = effective_backing_len,
508 .alignment = effective_alignment,
509 .allocation_id = allocation_id,
510 .allocation_return_address = ret_addr,
511 };
512 self.ensurePageOwnerCapacity(record) catch {
513 self.backing_allocator.rawFree(ptr[0..effective_backing_len], effective_alignment, ret_addr);
514 return null;
515 };
516 self.live.put(record.address, record) catch {
517 self.backing_allocator.rawFree(ptr[0..effective_backing_len], effective_alignment, ret_addr);
518 return null;
519 };
520 self.known.put(record.address, record) catch {
521 _ = self.live.remove(record.address);
522 self.backing_allocator.rawFree(ptr[0..effective_backing_len], effective_alignment, ret_addr);
523 return null;
524 };
525 self.putPageOwnerAssumeCapacity(record);
526 return ptr;
527 }
528
529 fn largeBackingLen(self: *const Self, backing_len: usize) ?usize {
530 return switch (self.config.mode) {
531 .dieharder => alignForwardChecked(backing_len, page_size),
532 .diehard, .exterminator => backing_len,
533 };
534 }
535
536 fn largeAlignment(self: *const Self, alignment: Alignment) Alignment {
537 return switch (self.config.mode) {
538 .dieharder => .fromByteUnits(@max(alignment.toByteUnits(), page_size)),
539 .diehard, .exterminator => alignment,
540 };
541 }
542
543 fn freeSmall(self: *Self, record: *AllocationRecord, ret_addr: usize) void {
544 const block = record.small_block.?;
545 const chunk = block.chunk;
546 const ptr = chunk.blockPtr(block.index);
547 record.free_pattern = self.nextFreedPattern();
548 if (self.writeFreedPattern()) self.fillFreedPattern(ptr, chunk.block_size, record.free_pattern);
549 record.free_return_address = ret_addr;
550 record.free_epoch = self.epoch;
551 record.free_quarantine_epochs = self.config.repairQuarantineEpochs(record.allocation_return_address, ret_addr);
552 chunk.states[block.index] = .free;
553 chunk.free_return_addresses[block.index] = ret_addr;
554 chunk.free_epochs[block.index] = self.epoch;
555 chunk.free_quarantine_epochs[block.index] = record.free_quarantine_epochs;
556 chunk.free_patterns[block.index] = record.free_pattern;
557 chunk.free_issue_reported[block.index] = false;
558 chunk.live_count -= 1;
559 self.classes[chunk.class_index].live_count -= 1;
560 self.epoch +%= 1;
561 }
562
563 fn freeLarge(self: *Self, record: *AllocationRecord, ret_addr: usize) void {
564 const ptr: [*]u8 = @ptrFromInt(record.address);
565 record.free_pattern = self.nextFreedPattern();
566 if (self.writeFreedPattern()) self.fillFreedPattern(ptr, record.backing_len, record.free_pattern);
567 record.free_return_address = ret_addr;
568 record.free_epoch = self.epoch;
569 record.free_quarantine_epochs = self.config.repairQuarantineEpochs(record.allocation_return_address, ret_addr);
570 if (record.free_quarantine_epochs > 0) {
571 var quarantined = record.*;
572 quarantined.free_issue_reported = false;
573 self.large_quarantine.append(self.backing_allocator, quarantined) catch {
574 self.releaseLarge(record.*, ret_addr);
575 return;
576 };
577 self.epoch +%= 1;
578 return;
579 }
580 self.releaseLarge(record.*, ret_addr);
581 }
582
583 fn releaseLarge(self: *Self, record: AllocationRecord, ret_addr: usize) void {
584 const ptr: [*]u8 = @ptrFromInt(record.address);
585 self.removePageOwner(record);
586 self.backing_allocator.rawFree(ptr[0..record.backing_len], record.alignment, ret_addr);
587 }
588
589 fn releaseLiveLargeAllocations(self: *Self, ret_addr: usize) void {
590 var iterator = self.live.valueIterator();
591 while (iterator.next()) |record| {
592 if (record.kind == .large) self.releaseLarge(record.*, ret_addr);
593 }
594 }
595
596 fn addChunk(self: *Self, class_index: usize, ret_addr: usize) !void {
597 const class_state = &self.classes[class_index];
598 const block_size = size_class.size(class_index);
599 const block_stride = self.blockStride(block_size);
600 if (class_state.next_chunk_blocks == 0) {
601 class_state.next_chunk_blocks = self.initialChunkBlocks(block_stride);
602 }
603 const capacity = class_state.next_chunk_blocks;
604 const area_len = std.math.mul(usize, capacity, block_stride) catch return error.OutOfMemory;
605 const alignment = Alignment.fromByteUnits(@max(block_stride, min_alignment));
606 const base = self.backing_allocator.rawAlloc(area_len, alignment, ret_addr) orelse return error.OutOfMemory;
607 errdefer self.backing_allocator.rawFree(base[0..area_len], alignment, ret_addr);
608
609 const chunk = try self.backing_allocator.create(Chunk);
610 errdefer self.backing_allocator.destroy(chunk);
611
612 const states = try self.backing_allocator.alloc(BlockState, capacity);
613 errdefer self.backing_allocator.free(states);
614 const requested_lens = try self.backing_allocator.alloc(usize, capacity);
615 errdefer self.backing_allocator.free(requested_lens);
616 const allocation_ids = try self.backing_allocator.alloc(u64, capacity);
617 errdefer self.backing_allocator.free(allocation_ids);
618 const allocation_return_addresses = try self.backing_allocator.alloc(usize, capacity);
619 errdefer self.backing_allocator.free(allocation_return_addresses);
620 const free_return_addresses = try self.backing_allocator.alloc(usize, capacity);
621 errdefer self.backing_allocator.free(free_return_addresses);
622 const repair_paddings = try self.backing_allocator.alloc(usize, capacity);
623 errdefer self.backing_allocator.free(repair_paddings);
624 const free_epochs = try self.backing_allocator.alloc(u64, capacity);
625 errdefer self.backing_allocator.free(free_epochs);
626 const free_quarantine_epochs = try self.backing_allocator.alloc(u64, capacity);
627 errdefer self.backing_allocator.free(free_quarantine_epochs);
628 const free_patterns = try self.backing_allocator.alloc(u64, capacity);
629 errdefer self.backing_allocator.free(free_patterns);
630 const free_issue_reported = try self.backing_allocator.alloc(bool, capacity);
631 errdefer self.backing_allocator.free(free_issue_reported);
632
633 @memset(states, .fresh);
634 @memset(requested_lens, 0);
635 @memset(repair_paddings, 0);
636 @memset(allocation_ids, 0);
637 @memset(allocation_return_addresses, 0);
638 @memset(free_return_addresses, 0);
639 @memset(free_epochs, 0);
640 @memset(free_quarantine_epochs, 0);
641 @memset(free_patterns, 0);
642 @memset(free_issue_reported, false);
643 self.fillFreedPattern(base, area_len, self.freshFreedPattern());
644
645 chunk.* = .{
646 .class_index = class_index,
647 .block_size = block_size,
648 .block_stride = block_stride,
649 .capacity = capacity,
650 .live_count = 0,
651 .base = base,
652 .area_len = area_len,
653 .states = states,
654 .requested_lens = requested_lens,
655 .repair_paddings = repair_paddings,
656 .allocation_ids = allocation_ids,
657 .allocation_return_addresses = allocation_return_addresses,
658 .free_return_addresses = free_return_addresses,
659 .free_epochs = free_epochs,
660 .free_quarantine_epochs = free_quarantine_epochs,
661 .free_patterns = free_patterns,
662 .free_issue_reported = free_issue_reported,
663 };
664
665 try class_state.chunks.append(self.backing_allocator, chunk);
666 class_state.capacity += capacity;
667 class_state.next_chunk_blocks = std.math.mul(usize, capacity, 2) catch capacity;
668 }
669
670 fn destroyChunk(self: *Self, chunk: *Chunk) void {
671 self.backing_allocator.rawFree(
672 chunk.base[0..chunk.area_len],
673 .fromByteUnits(@max(chunk.block_stride, min_alignment)),
674 @returnAddress(),
675 );
676 self.backing_allocator.free(chunk.states);
677 self.backing_allocator.free(chunk.requested_lens);
678 self.backing_allocator.free(chunk.repair_paddings);
679 self.backing_allocator.free(chunk.allocation_ids);
680 self.backing_allocator.free(chunk.allocation_return_addresses);
681 self.backing_allocator.free(chunk.free_return_addresses);
682 self.backing_allocator.free(chunk.free_epochs);
683 self.backing_allocator.free(chunk.free_quarantine_epochs);
684 self.backing_allocator.free(chunk.free_patterns);
685 self.backing_allocator.free(chunk.free_issue_reported);
686 self.backing_allocator.destroy(chunk);
687 }
688
689 fn blockStride(self: *Self, block_size: usize) usize {
690 return switch (self.config.mode) {
691 .diehard, .exterminator => block_size,
692 .dieharder => if (block_size < page_size) page_size else block_size,
693 };
694 }
695
696 fn initialChunkBlocks(self: *Self, block_stride: usize) usize {
697 const base = @max(self.config.min_chunk_blocks, 1);
698 if (self.config.mode == .dieharder and block_stride >= page_size) return @max(@min(base, 16), 2);
699 return base;
700 }
701
702 fn shouldGrow(self: *Self, class_state: *const ClassState) bool {
703 if (class_state.capacity == 0) return true;
704 return self.config.numerator * (class_state.live_count + 1) >= class_state.capacity * self.config.denominator;
705 }
706
707 fn blockByOrdinal(self: *Self, class_state: *ClassState, ordinal: usize) BlockRef {
708 _ = self;
709 var remaining = ordinal;
710 for (class_state.chunks.items) |chunk| {
711 if (remaining < chunk.capacity) return .{ .chunk = chunk, .index = remaining };
712 remaining -= chunk.capacity;
713 }
714 unreachable;
715 }
716
717 fn totalAllocationLen(self: *Self, requested_len: usize, repair_padding: usize) ?usize {
718 const occupied_len = std.math.add(usize, @max(requested_len, 1), repair_padding) catch return null;
719 return std.math.add(usize, occupied_len, self.config.diagnosticRedZoneBytes()) catch null;
720 }
721
722 fn installCanary(self: *Self, ptr: [*]u8, requested_len: usize, repair_padding: usize, block_size: usize) void {
723 const red_zone = self.config.diagnosticRedZoneBytes();
724 const start = std.math.add(usize, @max(requested_len, 1), repair_padding) catch return;
725 if (red_zone == 0 or start >= block_size) return;
726 const canary_len = @min(red_zone, block_size - start);
727 @memset(ptr[start .. start + canary_len], canary_byte);
728 }
729
730 fn checkCanary(self: *Self, record: *AllocationRecord, ret_addr: usize) bool {
731 const red_zone = self.config.diagnosticRedZoneBytes();
732 const start = std.math.add(usize, @max(record.requested_len, 1), record.repair_padding) catch return false;
733 if (red_zone == 0 or start >= record.block_size) return false;
734 const canary_len = @min(red_zone, record.block_size - start);
735 const ptr: [*]u8 = @ptrFromInt(record.address);
736 var offset = start;
737 while (offset < start + canary_len) : (offset += 1) {
738 if (ptr[offset] != canary_byte) {
739 if (!record.canary_issue_reported) {
740 self.recordIssue(.{
741 .kind = .buffer_overflow,
742 .address = record.address,
743 .offset = offset,
744 .requested_len = record.requested_len,
745 .block_size = record.block_size,
746 .allocation_id = record.allocation_id,
747 .allocation_return_address = record.allocation_return_address,
748 .free_return_address = record.free_return_address,
749 .free_epoch = record.free_epoch,
750 .return_address = ret_addr,
751 });
752 record.canary_issue_reported = true;
753 }
754 return true;
755 }
756 }
757 record.canary_issue_reported = false;
758 return false;
759 }
760
761 fn scanLiveCanaries(self: *Self, ret_addr: usize) void {
762 if (!self.diagnosticsActive()) return;
763 var iterator = self.live.valueIterator();
764 while (iterator.next()) |record| _ = self.checkCanary(record, ret_addr);
765 }
766
767 fn scanFreedMemory(self: *Self, ret_addr: usize) void {
768 if (!self.diagnosticsActive()) return;
769 for (&self.classes) |*class_state| {
770 for (class_state.chunks.items) |chunk| {
771 for (chunk.states, 0..) |state, index| {
772 if (state != .free or chunk.free_issue_reported[index]) continue;
773 chunk.free_issue_reported[index] = self.checkFreedPattern(
774 chunk.blockPtr(index),
775 chunk.block_size,
776 chunk.requested_lens[index],
777 chunk.allocation_ids[index],
778 chunk.allocation_return_addresses[index],
779 chunk.free_return_addresses[index],
780 chunk.free_epochs[index],
781 chunk.free_patterns[index],
782 ret_addr,
783 );
784 }
785 }
786 }
787 for (self.large_quarantine.items) |*record| {
788 if (record.free_issue_reported) continue;
789 const ptr: [*]u8 = @ptrFromInt(record.address);
790 record.free_issue_reported = self.checkFreedPattern(
791 ptr,
792 record.block_size,
793 record.requested_len,
794 record.allocation_id,
795 record.allocation_return_address,
796 record.free_return_address,
797 record.free_epoch,
798 record.free_pattern,
799 ret_addr,
800 );
801 }
802 }
803
804 fn drainLargeQuarantine(self: *Self, ret_addr: usize) void {
805 var index: usize = 0;
806 while (index < self.large_quarantine.items.len) {
807 var record = &self.large_quarantine.items[index];
808 if (!record.free_issue_reported) {
809 const ptr: [*]u8 = @ptrFromInt(record.address);
810 record.free_issue_reported = self.checkFreedPattern(
811 ptr,
812 record.block_size,
813 record.requested_len,
814 record.allocation_id,
815 record.allocation_return_address,
816 record.free_return_address,
817 record.free_epoch,
818 record.free_pattern,
819 ret_addr,
820 );
821 }
822 if (self.epoch -% record.free_epoch < record.free_quarantine_epochs) {
823 index += 1;
824 continue;
825 }
826 const removed = self.large_quarantine.swapRemove(index);
827 self.releaseLarge(removed, ret_addr);
828 }
829 }
830
831 fn checkFreedPattern(
832 self: *Self,
833 ptr: [*]u8,
834 block_size: usize,
835 requested_len: usize,
836 allocation_id: u64,
837 allocation_return_address: usize,
838 free_return_address: usize,
839 free_epoch: u64,
840 pattern: u64,
841 ret_addr: usize,
842 ) bool {
843 var index: usize = 0;
844 while (index < block_size) : (index += 1) {
845 if (ptr[index] != patternByte(pattern, index)) {
846 self.recordIssue(.{
847 .kind = .use_after_free,
848 .address = @intFromPtr(ptr),
849 .offset = index,
850 .requested_len = requested_len,
851 .block_size = block_size,
852 .allocation_id = allocation_id,
853 .allocation_return_address = allocation_return_address,
854 .free_return_address = free_return_address,
855 .free_epoch = free_epoch,
856 .return_address = ret_addr,
857 });
858 return true;
859 }
860 }
861 return false;
862 }
863
864 fn freshFreedPattern(self: *Self) u64 {
865 return switch (self.config.mode) {
866 .dieharder => 0,
867 .diehard, .exterminator => repeatedPattern(freed_byte),
868 };
869 }
870
871 fn nextFreedPattern(self: *Self) u64 {
872 return switch (self.config.mode) {
873 .dieharder => 0,
874 .diehard, .exterminator => sanitizedFreedPattern(self.prng.random().int(u64)),
875 };
876 }
877
878 fn nextAllocationId(self: *Self) u64 {
879 const id = self.next_allocation_id;
880 self.next_allocation_id +%= 1;
881 if (self.next_allocation_id == 0) self.next_allocation_id = 1;
882 return id;
883 }
884
885 fn writeFreedPattern(self: *Self) bool {
886 return switch (self.config.mode) {
887 .diehard => self.diagnosticsActive(),
888 .dieharder, .exterminator => true,
889 };
890 }
891
892 fn fillFreedPattern(self: *Self, ptr: [*]u8, len: usize, pattern: u64) void {
893 _ = self;
894 var index: usize = 0;
895 while (index < len) : (index += 1) ptr[index] = patternByte(pattern, index);
896 }
897
898 fn recordUnknownFree(self: *Self, address: usize, len: usize, alignment: Alignment, ret_addr: usize) void {
899 _ = alignment;
900 if (self.known.get(address)) |record| {
901 self.recordIssue(.{
902 .kind = .double_free,
903 .address = address,
904 .requested_len = len,
905 .block_size = record.block_size,
906 .allocation_id = record.allocation_id,
907 .allocation_return_address = record.allocation_return_address,
908 .free_return_address = record.free_return_address,
909 .free_epoch = record.free_epoch,
910 .return_address = ret_addr,
911 });
912 return;
913 }
914 if (self.pageOwnedRecord(address)) |record| {
915 self.recordIssue(.{
916 .kind = .invalid_free,
917 .address = address,
918 .offset = address - record.address,
919 .requested_len = len,
920 .block_size = record.block_size,
921 .allocation_id = record.allocation_id,
922 .allocation_return_address = record.allocation_return_address,
923 .free_return_address = record.free_return_address,
924 .free_epoch = record.free_epoch,
925 .return_address = ret_addr,
926 });
927 return;
928 }
929 if (self.containingKnownRecord(address)) |record| {
930 self.recordIssue(.{
931 .kind = .invalid_free,
932 .address = address,
933 .offset = address - record.address,
934 .requested_len = len,
935 .block_size = record.block_size,
936 .allocation_id = record.allocation_id,
937 .allocation_return_address = record.allocation_return_address,
938 .free_return_address = record.free_return_address,
939 .free_epoch = record.free_epoch,
940 .return_address = ret_addr,
941 });
942 return;
943 }
944 self.recordIssue(.{
945 .kind = .invalid_free,
946 .address = address,
947 .requested_len = len,
948 .return_address = ret_addr,
949 });
950 }
951
952 fn pageOwnedRecord(self: *Self, address: usize) ?AllocationRecord {
953 if (!self.usesPageOwners()) return null;
954 const owner_address = self.page_owners.get(pageNumber(address)) orelse return null;
955 const record = self.known.get(owner_address) orelse return null;
956 if (address <= record.address) return null;
957 const end = std.math.add(usize, record.address, record.block_size) catch std.math.maxInt(usize);
958 if (address >= end) return null;
959 return record;
960 }
961
962 fn containingKnownRecord(self: *Self, address: usize) ?AllocationRecord {
963 var iterator = self.known.valueIterator();
964 while (iterator.next()) |record| {
965 if (address <= record.address) continue;
966 const end = std.math.add(usize, record.address, record.block_size) catch std.math.maxInt(usize);
967 if (address < end) return record.*;
968 }
969 return null;
970 }
971
972 fn ensurePageOwnerCapacity(self: *Self, record: AllocationRecord) !void {
973 return self.ensurePageOwnerCapacityFor(record.address, record.block_size);
974 }
975
976 fn ensurePageOwnerCapacityFor(self: *Self, address: usize, block_size: usize) !void {
977 if (!self.usesPageOwners()) return;
978 const pages = std.math.cast(u32, pageSpan(address, block_size)) orelse return error.OutOfMemory;
979 try self.page_owners.ensureUnusedCapacity(pages);
980 }
981
982 fn putPageOwnerAssumeCapacity(self: *Self, record: AllocationRecord) void {
983 if (!self.usesPageOwners()) return;
984 const first_page = pageNumber(record.address);
985 const pages = pageSpan(record.address, record.block_size);
986 var index: usize = 0;
987 while (index < pages) : (index += 1) {
988 self.page_owners.putAssumeCapacity(first_page + index, record.address);
989 }
990 }
991
992 fn removePageOwner(self: *Self, record: AllocationRecord) void {
993 if (!self.usesPageOwners()) return;
994 const first_page = pageNumber(record.address);
995 const pages = pageSpan(record.address, record.block_size);
996 var index: usize = 0;
997 while (index < pages) : (index += 1) {
998 _ = self.page_owners.remove(first_page + index);
999 }
1000 }
1001
1002 fn usesPageOwners(self: *const Self) bool {
1003 return self.config.mode == .dieharder;
1004 }
1005
1006 fn recordIssue(self: *Self, issue: Issue) void {
1007 if (!self.diagnosticsActive()) return;
1008 self.counters.increment(issue.kind);
1009 self.last_issue = issue;
1010 self.issues.append(issue);
1011 }
1012
1013 fn diagnosticsActive(self: *const Self) bool {
1014 return self.config.diagnostics.enabled or self.config.mode == .exterminator;
1015 }
1016
1017 fn lock(self: *Self) void {
1018 if (!self.config.thread_safe) return;
1019 while (!self.mutex.tryLock()) std.atomic.spinLoopHint();
1020 }
1021
1022 fn unlock(self: *Self) void {
1023 if (self.config.thread_safe) self.mutex.unlock();
1024 }
1025 };
1026
1027 const vtable: Allocator.VTable = .{
1028 .alloc = rawAlloc,
1029 .resize = rawResize,
1030 .remap = rawRemap,
1031 .free = rawFree,
1032 };
1033
1034 fn repeatedPattern(byte: u8) u64 {
1035 var pattern: u64 = 0;
1036 var index: u6 = 0;
1037 while (index < 8) : (index += 1) {
1038 pattern |= @as(u64, byte) << (index * 8);
1039 }
1040 return pattern;
1041 }
1042
1043 fn sanitizedFreedPattern(raw: u64) u64 {
1044 var pattern = if (raw == 0) @as(u64, 0x9e37_79b9_7f4a_7c15) else raw;
1045 var index: u6 = 0;
1046 while (index < 8) : (index += 1) {
1047 const shift = index * 8;
1048 const mask = @as(u64, 0xff) << shift;
1049 const byte: u8 = @truncate(pattern >> shift);
1050 if (byte == 0 or byte == freed_byte or byte == allocated_byte or byte == canary_byte) {
1051 pattern = (pattern & ~mask) | (@as(u64, sanitizedPatternByte(byte)) << shift);
1052 }
1053 }
1054 return pattern;
1055 }
1056
1057 fn sanitizedPatternByte(byte: u8) u8 {
1058 const first = byte ^ 0x5a;
1059 if (first != 0 and first != freed_byte and first != allocated_byte and first != canary_byte) return first;
1060 return 0x7b;
1061 }
1062
1063 fn patternByte(pattern: u64, offset: usize) u8 {
1064 const shift: u6 = @intCast((offset & 7) * 8);
1065 return @truncate(pattern >> shift);
1066 }
1067
1068 fn alignForwardChecked(value: usize, alignment: usize) ?usize {
1069 std.debug.assert(std.math.isPowerOfTwo(alignment));
1070 const adjusted = std.math.add(usize, value, alignment - 1) catch return null;
1071 return std.mem.alignBackward(usize, adjusted, alignment);
1072 }
1073
1074 fn pageNumber(address: usize) usize {
1075 return address / page_size;
1076 }
1077
1078 fn pageSpan(address: usize, len: usize) usize {
1079 const first_page = pageNumber(address);
1080 const last_byte = std.math.add(usize, address, @max(len, 1) - 1) catch std.math.maxInt(usize);
1081 return pageNumber(last_byte) - first_page + 1;
1082 }
1083
1084 fn rawAlloc(ctx: *anyopaque, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {
1085 const self: *DeadAllocator = @ptrCast(@alignCast(ctx));
1086 return self.rawAlloc(len, alignment, ret_addr);
1087 }
1088
1089 fn rawResize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) bool {
1090 const self: *DeadAllocator = @ptrCast(@alignCast(ctx));
1091 return self.rawResize(memory, alignment, new_len, ret_addr);
1092 }
1093
1094 fn rawRemap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
1095 const self: *DeadAllocator = @ptrCast(@alignCast(ctx));
1096 return self.rawRemap(memory, alignment, new_len, ret_addr);
1097 }
1098
1099 fn rawFree(ctx: *anyopaque, memory: []u8, alignment: Alignment, ret_addr: usize) void {
1100 const self: *DeadAllocator = @ptrCast(@alignCast(ctx));
1101 self.rawFree(memory, alignment, ret_addr);
1102 }
1103
1104 test "diehard mode returns aligned disjoint allocations" {
1105 var heap = DeadAllocator.init(std.testing.allocator, .{ .seed = 1 });
1106 defer heap.deinit();
1107 const allocator = heap.allocator();
1108
1109 const left = try allocator.alignedAlloc(u8, .fromByteUnits(64), 33);
1110 defer allocator.free(left);
1111 const right = try allocator.alloc(u8, 33);
1112 defer allocator.free(right);
1113
1114 try std.testing.expect(std.mem.isAligned(@intFromPtr(left.ptr), 64));
1115 try std.testing.expect(@intFromPtr(left.ptr) + left.len <= @intFromPtr(right.ptr) or @intFromPtr(right.ptr) + right.len <= @intFromPtr(left.ptr));
1116 }
1117
1118 test "random small block probes tolerate occupied collisions" {
1119 var heap = DeadAllocator.init(std.testing.allocator, .{ .seed = 3, .min_chunk_blocks = 2, .thread_safe = false });
1120 defer heap.deinit();
1121
1122 const class_index = size_class.indexFor(8, .@"1").?;
1123 try heap.addChunk(class_index, @returnAddress());
1124 const class_state = &heap.classes[class_index];
1125
1126 const first = (try heap.tryAllocateSmallBlock(class_state, 0, 8, 0, 8, .@"1", @returnAddress())).?;
1127 const collision = try heap.tryAllocateSmallBlock(class_state, 0, 8, 0, 8, .@"1", @returnAddress());
1128 try std.testing.expect(collision == null);
1129 try std.testing.expectEqual(@as(usize, 1), class_state.live_count);
1130 try std.testing.expectEqual(@as(usize, 1), class_state.chunks.items[0].live_count);
1131
1132 const second = (try heap.tryAllocateSmallBlock(class_state, 1, 8, 0, 8, .@"1", @returnAddress())).?;
1133 try std.testing.expect(@intFromPtr(first) + 8 <= @intFromPtr(second) or @intFromPtr(second) + 8 <= @intFromPtr(first));
1134 try std.testing.expectEqual(@as(usize, 2), class_state.live_count);
1135 try std.testing.expectEqual(@as(usize, 2), class_state.chunks.items[0].live_count);
1136 }
1137
1138 test "dieharder large allocations are page granular" {
1139 var heap = DeadAllocator.init(std.testing.allocator, .{ .mode = .dieharder, .thread_safe = false });
1140 defer heap.deinit();
1141 const allocator = heap.allocator();
1142
1143 const len = max_small_size + 1;
1144 const rounded_len = alignForwardChecked(len, page_size).?;
1145 const ptr = allocator.rawAlloc(len, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1146 try std.testing.expect(std.mem.isAligned(@intFromPtr(ptr), page_size));
1147
1148 const record = heap.live.get(@intFromPtr(ptr)).?;
1149 try std.testing.expectEqual(.large, record.kind);
1150 try std.testing.expectEqual(rounded_len, record.backing_len);
1151 try std.testing.expectEqual(rounded_len, record.block_size);
1152 try std.testing.expectEqual(page_size, record.alignment.toByteUnits());
1153
1154 try std.testing.expect(allocator.rawResize(ptr[0..len], .@"1", rounded_len, @returnAddress()));
1155 allocator.rawFree(ptr[0..rounded_len], .@"1", @returnAddress());
1156 }
1157
1158 test "dieharder page owners resolve interior small frees" {
1159 var heap = DeadAllocator.init(std.testing.allocator, .{
1160 .mode = .dieharder,
1161 .thread_safe = false,
1162 .diagnostics = .{ .enabled = true },
1163 });
1164 defer heap.deinit();
1165
1166 const ptr = heap.rawAlloc(64, .@"1", 0x1000) orelse return error.OutOfMemory;
1167 const address = @intFromPtr(ptr);
1168 try std.testing.expectEqual(address, heap.page_owners.get(pageNumber(address + 16)).?);
1169
1170 heap.rawFree(ptr[16..32], .@"1", 0x2000);
1171
1172 const report = heap.report();
1173 const issue = report.last_issue.?;
1174 try std.testing.expectEqual(@as(usize, 1), report.counters.invalid_free);
1175 try std.testing.expectEqual(@as(usize, 1), report.live_allocations);
1176 try std.testing.expectEqual(.invalid_free, issue.kind);
1177 try std.testing.expectEqual(address + 16, issue.address);
1178 try std.testing.expectEqual(@as(usize, 16), issue.offset);
1179 try std.testing.expectEqual(@as(usize, 16), issue.requested_len);
1180 try std.testing.expectEqual(address, heap.page_owners.get(pageNumber(address + page_size - 1)).?);
1181
1182 heap.rawFree(ptr[0..64], .@"1", 0x3000);
1183 }
1184
1185 test "dieharder page owners cover large quarantined pages" {
1186 var heap = DeadAllocator.init(std.testing.allocator, .{
1187 .mode = .dieharder,
1188 .thread_safe = false,
1189 .diagnostics = .{ .enabled = true, .quarantine_epochs = 8 },
1190 });
1191 defer heap.deinit();
1192
1193 const len = max_small_size + page_size + 17;
1194 const ptr = heap.rawAlloc(len, .@"1", 0x1000) orelse return error.OutOfMemory;
1195 const address = @intFromPtr(ptr);
1196 const interior = address + page_size + 8;
1197 try std.testing.expectEqual(address, heap.page_owners.get(pageNumber(interior)).?);
1198
1199 heap.rawFree((ptr + page_size + 8)[0..16], .@"1", 0x2000);
1200
1201 const report = heap.report();
1202 const issue = report.last_issue.?;
1203 try std.testing.expectEqual(@as(usize, 1), report.counters.invalid_free);
1204 try std.testing.expectEqual(.invalid_free, issue.kind);
1205 try std.testing.expectEqual(interior, issue.address);
1206 try std.testing.expectEqual(page_size + 8, issue.offset);
1207
1208 heap.rawFree(ptr[0..len], .@"1", 0x3000);
1209 try std.testing.expect(heap.page_owners.get(pageNumber(address)) != null);
1210
1211 var index: usize = 0;
1212 while (index < 9) : (index += 1) {
1213 const scratch = heap.rawAlloc(64, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1214 heap.rawFree(scratch[0..64], .@"1", @returnAddress());
1215 }
1216 _ = heap.report();
1217 try std.testing.expect(heap.page_owners.get(pageNumber(address)) == null);
1218 }
1219
1220 const SwitchFailAllocator = struct {
1221 inner: Allocator,
1222 fail_allocations: bool = false,
1223
1224 fn allocator(self: *SwitchFailAllocator) Allocator {
1225 return .{
1226 .ptr = self,
1227 .vtable = &.{
1228 .alloc = alloc,
1229 .resize = resize,
1230 .remap = remap,
1231 .free = free,
1232 },
1233 };
1234 }
1235
1236 fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {
1237 const self: *SwitchFailAllocator = @ptrCast(@alignCast(ctx));
1238 if (self.fail_allocations) return null;
1239 return self.inner.rawAlloc(len, alignment, ret_addr);
1240 }
1241
1242 fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) bool {
1243 const self: *SwitchFailAllocator = @ptrCast(@alignCast(ctx));
1244 if (self.fail_allocations) return false;
1245 return self.inner.rawResize(memory, alignment, new_len, ret_addr);
1246 }
1247
1248 fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
1249 const self: *SwitchFailAllocator = @ptrCast(@alignCast(ctx));
1250 if (self.fail_allocations) return null;
1251 return self.inner.rawRemap(memory, alignment, new_len, ret_addr);
1252 }
1253
1254 fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, ret_addr: usize) void {
1255 const self: *SwitchFailAllocator = @ptrCast(@alignCast(ctx));
1256 self.inner.rawFree(memory, alignment, ret_addr);
1257 }
1258 };
1259
1260 test "dieharder releases large page owners when quarantine append fails" {
1261 var backing = SwitchFailAllocator{ .inner = std.testing.allocator };
1262 var heap = DeadAllocator.init(backing.allocator(), .{
1263 .mode = .dieharder,
1264 .thread_safe = false,
1265 .diagnostics = .{ .enabled = true, .quarantine_epochs = 8 },
1266 });
1267 defer heap.deinit();
1268
1269 const len = max_small_size + page_size + 17;
1270 const ptr = heap.rawAlloc(len, .@"1", 0x1000) orelse return error.OutOfMemory;
1271 const address = @intFromPtr(ptr);
1272 const middle_page = pageNumber(address + page_size);
1273 try std.testing.expect(heap.page_owners.get(pageNumber(address)) != null);
1274 try std.testing.expect(heap.page_owners.get(middle_page) != null);
1275
1276 backing.fail_allocations = true;
1277 heap.rawFree(ptr[0..len], .@"1", 0x2000);
1278 backing.fail_allocations = false;
1279
1280 try std.testing.expectEqual(@as(usize, 0), heap.live.count());
1281 try std.testing.expectEqual(@as(usize, 0), heap.large_quarantine.items.len);
1282 try std.testing.expect(heap.page_owners.get(pageNumber(address)) == null);
1283 try std.testing.expect(heap.page_owners.get(middle_page) == null);
1284 }
1285
1286 test "small quarantine availability survives epoch wraparound" {
1287 var heap = DeadAllocator.init(std.testing.allocator, .{
1288 .mode = .exterminator,
1289 .thread_safe = false,
1290 .min_chunk_blocks = 2,
1291 .diagnostics = .{ .enabled = true, .quarantine_epochs = 4 },
1292 });
1293 defer heap.deinit();
1294
1295 heap.epoch = std.math.maxInt(u64) - 1;
1296 const ptr = heap.rawAlloc(16, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1297 const address = @intFromPtr(ptr);
1298 heap.rawFree(ptr[0..16], .@"1", @returnAddress());
1299
1300 const block = heap.known.get(address).?.small_block.?;
1301 try std.testing.expectEqual(std.math.maxInt(u64), block.chunk.free_epochs[block.index]);
1302 try std.testing.expectEqual(@as(u64, 0), heap.epoch);
1303 try std.testing.expect(!block.chunk.isAvailable(block.index, heap.epoch));
1304
1305 heap.epoch = 2;
1306 try std.testing.expect(!block.chunk.isAvailable(block.index, heap.epoch));
1307
1308 heap.epoch = 3;
1309 try std.testing.expect(block.chunk.isAvailable(block.index, heap.epoch));
1310 }
1311
1312 test "repair config adds overflow padding from nondiagnostic mode" {
1313 const report: report_mod.Report = .{
1314 .counters = .{
1315 .buffer_overflow = 1,
1316 },
1317 };
1318 const repaired = Config.repaired(.{ .mode = .diehard, .diagnostics = .{ .enabled = false, .red_zone_bytes = 0 } }, report);
1319 try std.testing.expectEqual(.exterminator, repaired.mode);
1320 try std.testing.expect(repaired.diagnostics.enabled);
1321 try std.testing.expectEqual(@as(usize, 16), repaired.diagnostics.red_zone_bytes);
1322 }
1323
1324 test "repair config applies overflow padding by allocation site" {
1325 const alloc_site: usize = 0x1000;
1326 const report: report_mod.Report = .{
1327 .counters = .{ .buffer_overflow = 1 },
1328 .issues = .{
1329 .count = 1,
1330 .items = [_]report_mod.Issue{.{
1331 .kind = .buffer_overflow,
1332 .offset = 10,
1333 .requested_len = 8,
1334 .allocation_return_address = alloc_site,
1335 }} ++ @as([(report_mod.max_issues - 1)]report_mod.Issue, @splat(.{})),
1336 },
1337 };
1338 const repaired = Config.repaired(Config.diagnostic(.exterminator), report);
1339 try std.testing.expectEqual(@as(usize, 3), repaired.repairs.overflowPadding(alloc_site));
1340
1341 var heap = DeadAllocator.init(std.testing.allocator, repaired);
1342 defer heap.deinit();
1343 const ptr = heap.rawAlloc(8, .@"1", alloc_site) orelse return error.OutOfMemory;
1344 const record = heap.live.get(@intFromPtr(ptr)).?;
1345 try std.testing.expectEqual(@as(usize, 3), record.repair_padding);
1346
1347 ptr[10] = 0xee;
1348 try std.testing.expectEqual(@as(usize, 0), heap.report().counters.buffer_overflow);
1349
1350 ptr[11] = 0xee;
1351 try std.testing.expectEqual(@as(usize, 1), heap.report().counters.buffer_overflow);
1352 heap.rawFree(ptr[0..8], .@"1", @returnAddress());
1353 }
1354
1355 test "repair config applies dangle extension by allocation and free site" {
1356 const alloc_site: usize = 0x1111;
1357 const free_site: usize = 0x2222;
1358 const report: report_mod.Report = .{
1359 .counters = .{ .use_after_free = 1 },
1360 .issues = .{
1361 .count = 1,
1362 .items = [_]report_mod.Issue{.{
1363 .kind = .use_after_free,
1364 .allocation_return_address = alloc_site,
1365 .free_return_address = free_site,
1366 }} ++ @as([(report_mod.max_issues - 1)]report_mod.Issue, @splat(.{})),
1367 },
1368 };
1369 var table = exterminator.RepairTable.fromReport(report, .{});
1370 table = exterminator.RepairTable.fromReport(report, table);
1371 table = exterminator.RepairTable.fromReport(report, table);
1372
1373 const repaired = Config.repaired(.{
1374 .mode = .exterminator,
1375 .diagnostics = .{ .enabled = true, .quarantine_epochs = 1 },
1376 .repairs = table,
1377 }, report);
1378 try std.testing.expectEqual(@as(u64, 8), repaired.repairs.lifeExtension(alloc_site, free_site));
1379 try std.testing.expectEqual(@as(u64, 2), repaired.diagnostics.quarantine_epochs);
1380
1381 var heap = DeadAllocator.init(std.testing.allocator, repaired);
1382 defer heap.deinit();
1383 const ptr = heap.rawAlloc(8, .@"1", alloc_site) orelse return error.OutOfMemory;
1384 heap.rawFree(ptr[0..8], .@"1", free_site);
1385 const known = heap.known.get(@intFromPtr(ptr)).?;
1386 try std.testing.expectEqual(@as(u64, 8), known.free_quarantine_epochs);
1387 }
1388
1389 test "exterminator mode reports invalid free double free overflow and leaks" {
1390 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1391 defer heap.deinit();
1392 const allocator = heap.allocator();
1393
1394 var stack_byte: u8 = 0;
1395 allocator.rawFree((&stack_byte)[0..1], .@"1", @returnAddress());
1396
1397 const ptr = allocator.rawAlloc(8, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1398 ptr[8] = 1;
1399 allocator.rawFree(ptr[0..8], .@"1", @returnAddress());
1400 allocator.rawFree(ptr[0..8], .@"1", @returnAddress());
1401
1402 _ = try allocator.alloc(u8, 24);
1403
1404 const got = heap.report();
1405 try std.testing.expectEqual(@as(usize, 1), got.counters.invalid_free);
1406 try std.testing.expectEqual(@as(usize, 1), got.counters.double_free);
1407 try std.testing.expectEqual(@as(usize, 1), got.counters.buffer_overflow);
1408 try std.testing.expectEqual(@as(usize, 1), got.leak_count);
1409 try std.testing.expectEqual(.leak, got.leak_issue.?.kind);
1410 try std.testing.expectEqual(@as(usize, 24), got.leak_issue.?.requested_len);
1411 }
1412
1413 test "diagnostic invalid free reports interior allocation context" {
1414 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1415 defer heap.deinit();
1416 const allocator = heap.allocator();
1417
1418 const ptr = allocator.rawAlloc(32, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1419 allocator.rawFree(ptr[1..2], .@"1", @returnAddress());
1420
1421 const got = heap.report();
1422 const issue = got.last_issue.?;
1423 try std.testing.expectEqual(@as(usize, 1), got.counters.invalid_free);
1424 try std.testing.expectEqual(@as(usize, 1), got.live_allocations);
1425 try std.testing.expectEqual(.invalid_free, issue.kind);
1426 try std.testing.expectEqual(@intFromPtr(ptr) + 1, issue.address);
1427 try std.testing.expectEqual(@as(usize, 1), issue.offset);
1428 try std.testing.expectEqual(@as(usize, 1), issue.requested_len);
1429 try std.testing.expect(issue.block_size >= 32);
1430 try std.testing.expect(issue.allocation_id != 0);
1431 try std.testing.expect(issue.allocation_return_address != 0);
1432
1433 allocator.rawFree(ptr[0..32], .@"1", @returnAddress());
1434 }
1435
1436 test "diagnostic raw remap rejects unknown allocation" {
1437 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1438 defer heap.deinit();
1439 const allocator = heap.allocator();
1440
1441 var stack_byte: u8 = 0x5a;
1442 const remapped = allocator.rawRemap((&stack_byte)[0..1], .@"1", 16, @returnAddress());
1443
1444 const got = heap.report();
1445 try std.testing.expect(remapped == null);
1446 try std.testing.expectEqual(@as(usize, 1), got.counters.invalid_free);
1447 try std.testing.expectEqual(@as(usize, 0), got.live_allocations);
1448 }
1449
1450 test "diagnostic raw remap rejects freed allocation" {
1451 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1452 defer heap.deinit();
1453 const allocator = heap.allocator();
1454
1455 const ptr = allocator.rawAlloc(16, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1456 allocator.rawFree(ptr[0..16], .@"1", @returnAddress());
1457 const remapped = allocator.rawRemap(ptr[0..16], .@"1", 32, @returnAddress());
1458
1459 const got = heap.report();
1460 try std.testing.expect(remapped == null);
1461 try std.testing.expectEqual(@as(usize, 1), got.counters.double_free);
1462 try std.testing.expectEqual(@as(usize, 0), got.live_allocations);
1463 }
1464
1465 test "diagnostic report retains structured issue history" {
1466 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1467 defer heap.deinit();
1468 const allocator = heap.allocator();
1469
1470 var stack_byte: u8 = 0;
1471 allocator.rawFree((&stack_byte)[0..1], .@"1", @returnAddress());
1472
1473 const overflow = allocator.rawAlloc(8, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1474 overflow[10] = 0xee;
1475 allocator.rawFree(overflow[0..8], .@"1", @returnAddress());
1476
1477 const doubled = allocator.rawAlloc(16, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1478 allocator.rawFree(doubled[0..16], .@"1", @returnAddress());
1479 allocator.rawFree(doubled[0..16], .@"1", @returnAddress());
1480
1481 const got = heap.report();
1482 const issues = got.issueSlice();
1483 try std.testing.expectEqual(@as(usize, 3), issues.len);
1484 try std.testing.expectEqual(.invalid_free, issues[0].kind);
1485 try std.testing.expectEqual(.buffer_overflow, issues[1].kind);
1486 try std.testing.expectEqual(.double_free, issues[2].kind);
1487 try std.testing.expectEqual(@as(usize, 10), issues[1].offset);
1488 try std.testing.expect(issues[1].allocation_id != 0);
1489 try std.testing.expect(issues[2].free_return_address != 0);
1490 try std.testing.expect(issues[2].free_epoch != 0);
1491 }
1492
1493 test "diagnostic report includes bounded leak issues" {
1494 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1495 defer heap.deinit();
1496 const allocator = heap.allocator();
1497
1498 const first = try allocator.alloc(u8, 8);
1499 defer allocator.free(first);
1500 const second = try allocator.alloc(u8, 16);
1501 defer allocator.free(second);
1502 const third = try allocator.alloc(u8, 24);
1503 defer allocator.free(third);
1504
1505 const got = heap.report();
1506 const issues = got.issueSlice();
1507 try std.testing.expectEqual(@as(usize, 3), got.leak_count);
1508 try std.testing.expectEqual(@as(usize, 3), issues.len);
1509 for (issues) |issue| {
1510 try std.testing.expectEqual(.leak, issue.kind);
1511 try std.testing.expect(issue.allocation_id != 0);
1512 try std.testing.expect(issue.allocation_return_address != 0);
1513 }
1514 }
1515
1516 test "diagnostic report detects stale small writes before reuse" {
1517 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1518 defer heap.deinit();
1519 const allocator = heap.allocator();
1520
1521 const allocation = try allocator.alloc(u8, 16);
1522 const address = @intFromPtr(allocation.ptr);
1523 allocator.free(allocation);
1524
1525 const stale: [*]u8 = @ptrFromInt(address);
1526 stale[0] = freed_byte;
1527
1528 const first = heap.report();
1529 const second = heap.report();
1530 try std.testing.expectEqual(@as(usize, 1), first.counters.use_after_free);
1531 try std.testing.expectEqual(@as(usize, 1), second.counters.use_after_free);
1532 }
1533
1534 test "diagnostic report scans entire freed small block" {
1535 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1536 defer heap.deinit();
1537 const allocator = heap.allocator();
1538
1539 const allocation = try allocator.alloc(u8, 17);
1540 const address = @intFromPtr(allocation.ptr);
1541 allocator.free(allocation);
1542
1543 const stale: [*]u8 = @ptrFromInt(address);
1544 stale[40] = freed_byte;
1545
1546 const got = heap.report();
1547 try std.testing.expectEqual(@as(usize, 1), got.counters.use_after_free);
1548 const issue = got.last_issue.?;
1549 try std.testing.expectEqual(.use_after_free, issue.kind);
1550 try std.testing.expectEqual(@as(usize, 40), issue.offset);
1551 try std.testing.expect(issue.allocation_id != 0);
1552 try std.testing.expect(issue.free_return_address != 0);
1553 try std.testing.expect(issue.free_epoch != 0);
1554 }
1555
1556 test "diagnostic freed patterns detect fixed fill byte writes" {
1557 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1558 defer heap.deinit();
1559 const allocator = heap.allocator();
1560
1561 const allocation = try allocator.alloc(u8, 16);
1562 const address = @intFromPtr(allocation.ptr);
1563 allocator.free(allocation);
1564
1565 const stale: [*]u8 = @ptrFromInt(address);
1566 stale[0] = freed_byte;
1567
1568 const got = heap.report();
1569 try std.testing.expectEqual(@as(usize, 1), got.counters.use_after_free);
1570 }
1571
1572 test "diagnostic resize checks existing red zone before updating size" {
1573 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1574 defer heap.deinit();
1575 const allocator = heap.allocator();
1576
1577 const ptr = allocator.rawAlloc(8, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1578 ptr[8] = 0xee;
1579
1580 try std.testing.expect(allocator.rawResize(ptr[0..8], .@"1", 12, @returnAddress()));
1581 const got = heap.report();
1582 try std.testing.expectEqual(@as(usize, 1), got.counters.buffer_overflow);
1583 }
1584
1585 test "diagnostic report detects live red zone overflow once" {
1586 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1587 defer heap.deinit();
1588 const allocator = heap.allocator();
1589
1590 const ptr = allocator.rawAlloc(8, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1591 ptr[8] = 0xee;
1592
1593 const first = heap.report();
1594 const second = heap.report();
1595 try std.testing.expectEqual(@as(usize, 1), first.counters.buffer_overflow);
1596 try std.testing.expectEqual(@as(usize, 1), second.counters.buffer_overflow);
1597
1598 allocator.rawFree(ptr[0..8], .@"1", @returnAddress());
1599 const after_free = heap.report();
1600 try std.testing.expectEqual(@as(usize, 1), after_free.counters.buffer_overflow);
1601 }
1602
1603 test "diagnostic report detects stale large writes while quarantined" {
1604 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1605 defer heap.deinit();
1606 const allocator = heap.allocator();
1607
1608 const len = max_small_size + 64;
1609 const ptr = allocator.rawAlloc(len, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1610 const address = @intFromPtr(ptr);
1611 allocator.rawFree(ptr[0..len], .@"1", @returnAddress());
1612
1613 const stale: [*]u8 = @ptrFromInt(address);
1614 stale[0] = freed_byte;
1615
1616 const first = heap.report();
1617 const second = heap.report();
1618 try std.testing.expectEqual(@as(usize, 1), first.counters.use_after_free);
1619 try std.testing.expectEqual(@as(usize, 1), second.counters.use_after_free);
1620 }
1621
1622 test "diehard mode preserves freed small contents until reuse" {
1623 var heap = DeadAllocator.init(std.testing.allocator, .{
1624 .mode = .diehard,
1625 .seed = 4,
1626 .min_chunk_blocks = 8,
1627 .thread_safe = false,
1628 });
1629 defer heap.deinit();
1630
1631 const ptr = heap.rawAlloc(64, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1632 @memset(ptr[0..64], 0xab);
1633 const address = @intFromPtr(ptr);
1634 heap.rawFree(ptr[0..64], .@"1", @returnAddress());
1635
1636 const stale: [*]u8 = @ptrFromInt(address);
1637 for (stale[0..64]) |byte| try std.testing.expectEqual(@as(u8, 0xab), byte);
1638 try std.testing.expect(heap.report().isClean());
1639 }
1640
1641 test "dieharder mode zeroes freed small contents" {
1642 var heap = DeadAllocator.init(std.testing.allocator, .{
1643 .mode = .dieharder,
1644 .seed = 5,
1645 .min_chunk_blocks = 8,
1646 .thread_safe = false,
1647 });
1648 defer heap.deinit();
1649
1650 const ptr = heap.rawAlloc(64, .@"1", @returnAddress()) orelse return error.OutOfMemory;
1651 @memset(ptr[0..64], 0xab);
1652 const address = @intFromPtr(ptr);
1653 heap.rawFree(ptr[0..64], .@"1", @returnAddress());
1654
1655 const stale: [*]u8 = @ptrFromInt(address);
1656 for (stale[0..64]) |byte| try std.testing.expectEqual(@as(u8, 0), byte);
1657 try std.testing.expect(heap.report().isClean());
1658 }
1659
1660 test "deinit releases reported large leaks" {
1661 var heap = DeadAllocator.init(std.testing.allocator, Config.diagnostic(.exterminator));
1662 const allocator = heap.allocator();
1663
1664 _ = try allocator.alloc(u8, max_small_size + 4096);
1665
1666 const got = heap.report();
1667 try std.testing.expectEqual(@as(usize, 1), got.leak_count);
1668 try std.testing.expectEqual(.leak, got.leak_issue.?.kind);
1669 try std.testing.expectEqual(@as(usize, max_small_size + 4096), got.leak_issue.?.requested_len);
1670 heap.deinit();
1671 }
1672
1673 test "dieharder mode delays reuse and detects stale writes when diagnostics are enabled" {
1674 var heap = DeadAllocator.init(std.testing.allocator, .{
1675 .mode = .dieharder,
1676 .seed = 2,
1677 .min_chunk_blocks = 2,
1678 .diagnostics = .{ .enabled = true, .quarantine_epochs = 2 },
1679 });
1680 defer heap.deinit();
1681 const allocator = heap.allocator();
1682
1683 const first = try allocator.alloc(u8, 16);
1684 const first_addr = @intFromPtr(first.ptr);
1685 allocator.free(first);
1686 const stale: [*]u8 = @ptrFromInt(first_addr);
1687 stale[0] = 0x44;
1688
1689 var scratch: ?[]u8 = null;
1690 var index: usize = 0;
1691 while (index < 32 and heap.report().counters.use_after_free == 0) : (index += 1) {
1692 scratch = try allocator.alloc(u8, 16);
1693 allocator.free(scratch.?);
1694 scratch = null;
1695 }
1696
1697 const got = heap.report();
1698 try std.testing.expect(got.counters.use_after_free >= 1);
1699 }
1700
1701 const ConcurrentWork = struct {
1702 allocator: Allocator,
1703 handoff: []?[]u8,
1704 failed: *std.atomic.Value(bool),
1705 };
1706
1707 fn concurrentAllocatorWorker(work: *ConcurrentWork, worker_index: usize) void {
1708 const handoff_per_thread = 16;
1709 const start = worker_index * handoff_per_thread;
1710 const end = start + handoff_per_thread;
1711 var handoff_index = start;
1712 while (handoff_index < end) : (handoff_index += 1) {
1713 const allocation = work.handoff[handoff_index] orelse {
1714 work.failed.store(true, .release);
1715 return;
1716 };
1717 const expected: u8 = @truncate(handoff_index *% 17 +% 3);
1718 for (allocation) |byte| {
1719 if (byte != expected) {
1720 work.failed.store(true, .release);
1721 return;
1722 }
1723 }
1724 work.allocator.free(allocation);
1725 work.handoff[handoff_index] = null;
1726 }
1727
1728 var iteration: usize = 0;
1729 while (iteration < 128) : (iteration += 1) {
1730 const len = 1 + ((worker_index * 257 + iteration * 37) % 2048);
1731 const fill: u8 = @truncate(worker_index *% 31 +% iteration);
1732 const allocation = work.allocator.alloc(u8, len) catch {
1733 work.failed.store(true, .release);
1734 return;
1735 };
1736 @memset(allocation, fill);
1737
1738 const new_len = 1 + ((worker_index * 131 + iteration * 53) % 4096);
1739 const resized = work.allocator.realloc(allocation, new_len) catch {
1740 work.allocator.free(allocation);
1741 work.failed.store(true, .release);
1742 return;
1743 };
1744 const prefix_len = @min(len, new_len);
1745 for (resized[0..prefix_len]) |byte| {
1746 if (byte != fill) {
1747 work.allocator.free(resized);
1748 work.failed.store(true, .release);
1749 return;
1750 }
1751 }
1752 @memset(resized, fill);
1753 work.allocator.free(resized);
1754 }
1755 }
1756
1757 test "thread-safe allocator supports concurrent allocation and cross-thread free" {
1758 const thread_count = 4;
1759 const handoff_per_thread = 16;
1760
1761 var heap = DeadAllocator.init(std.testing.allocator, .{
1762 .mode = .dieharder,
1763 .seed = 0x7c0c_5afe,
1764 .diagnostics = .{ .enabled = true, .quarantine_epochs = 8 },
1765 });
1766 defer heap.deinit();
1767 const allocator = heap.allocator();
1768
1769 var handoff: [thread_count * handoff_per_thread]?[]u8 = @as([(thread_count * handoff_per_thread)]?[]u8, @splat(null));
1770 defer {
1771 for (handoff) |allocation| {
1772 if (allocation) |live| allocator.free(live);
1773 }
1774 }
1775
1776 for (&handoff, 0..) |*slot, index| {
1777 const len = 1 + (index * 23) % 1024;
1778 const fill: u8 = @truncate(index *% 17 +% 3);
1779 const allocation = try allocator.alloc(u8, len);
1780 @memset(allocation, fill);
1781 slot.* = allocation;
1782 }
1783
1784 var failed = std.atomic.Value(bool).init(false);
1785 var work = ConcurrentWork{
1786 .allocator = allocator,
1787 .handoff = &handoff,
1788 .failed = &failed,
1789 };
1790 var threads: [thread_count]sys_thread.JoinHandle = undefined;
1791 var spawned: usize = 0;
1792 while (spawned < thread_count) : (spawned += 1) {
1793 threads[spawned] = try sys_thread.spawn(concurrentAllocatorWorker, .{ &work, spawned });
1794 }
1795 for (threads) |thread| thread.join();
1796
1797 try std.testing.expect(!failed.load(.acquire));
1798 try std.testing.expect(heap.report().isClean());
1799 }