tiny.deadalloc.DeadAllocator

1pub const DeadAllocator = struct {2    backing_allocator: Allocator,3    config: Config,4    classes: [size_class.count]ClassState = @as([size_class.count]ClassState, @splat(.{})),5    live: std.AutoHashMap(usize, AllocationRecord),6    known: std.AutoHashMap(usize, AllocationRecord),7    page_owners: std.AutoHashMap(usize, usize),8    large_quarantine: std.ArrayList(AllocationRecord) = .empty,9    prng: std.Random.DefaultPrng,10    mutex: std.atomic.Mutex = .unlocked,11    epoch: u64 = 1,12    next_allocation_id: u64 = 1,13    counters: report_mod.Counters = .{},14    last_issue: ?Issue = null,15    issues: report_mod.IssueLog = .{},1617    const Self = @This();1819    pub fn init(backing_allocator: Allocator, config: Config) Self {20        std.debug.assert(config.numerator >= config.denominator);21        std.debug.assert(config.denominator > 0);22        return .{23            .backing_allocator = backing_allocator,24            .config = config,25            .live = std.AutoHashMap(usize, AllocationRecord).init(backing_allocator),26            .known = std.AutoHashMap(usize, AllocationRecord).init(backing_allocator),27            .page_owners = std.AutoHashMap(usize, usize).init(backing_allocator),28            .prng = std.Random.DefaultPrng.init(config.seed),29        };30    }3132    pub fn deinit(self: *Self) void {33        if (self.diagnosticsActive()) {34            self.counters.invalid_free += 0;35        }36        self.releaseLiveLargeAllocations(@returnAddress());37        for (self.large_quarantine.items) |record| self.releaseLarge(record, @returnAddress());38        self.large_quarantine.deinit(self.backing_allocator);39        for (&self.classes) |*class_state| class_state.deinit(self.backing_allocator, self);40        self.live.deinit();41        self.known.deinit();42        self.page_owners.deinit();43        self.* = undefined;44    }4546    pub fn allocator(self: *Self) Allocator {47        return .{48            .ptr = self,49            .vtable = &vtable,50        };51    }5253    pub fn report(self: *Self) Report {54        self.lock();55        defer self.unlock();56        const ret_addr = @returnAddress();57        self.scanLiveCanaries(ret_addr);58        self.scanFreedMemory(ret_addr);59        self.drainLargeQuarantine(ret_addr);60        return self.reportUnlocked(ret_addr);61    }6263    fn reportUnlocked(self: *Self, ret_addr: usize) Report {64        var live_bytes: usize = 0;65        var leak_issue: ?Issue = null;66        var issues = self.issues;67        var iterator = self.live.valueIterator();68        while (iterator.next()) |record| {69            live_bytes += record.requested_len;70            const issue: Issue = .{71                .kind = .leak,72                .address = record.address,73                .requested_len = record.requested_len,74                .block_size = record.block_size,75                .allocation_id = record.allocation_id,76                .allocation_return_address = record.allocation_return_address,77                .return_address = ret_addr,78            };79            if (leak_issue == null) leak_issue = issue;80            issues.append(issue);81        }82        return .{83            .counters = self.counters,84            .live_allocations = self.live.count(),85            .live_bytes = live_bytes,86            .leak_count = self.live.count(),87            .leak_issue = leak_issue,88            .last_issue = self.last_issue,89            .issues = issues,90        };91    }9293    pub fn rawAlloc(self: *Self, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {94        self.lock();95        defer self.unlock();96        self.drainLargeQuarantine(ret_addr);9798        const repair_padding = self.config.repairPadding(ret_addr);99        const total_len = self.totalAllocationLen(len, repair_padding) orelse return null;100        const class_index = size_class.indexFor(total_len, alignment) orelse return self.allocateLarge(len, repair_padding, total_len, alignment, ret_addr);101        return self.allocateSmall(class_index, len, repair_padding, total_len, alignment, ret_addr) catch null;102    }103104    pub fn rawResize(self: *Self, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) bool {105        self.lock();106        defer self.unlock();107        self.drainLargeQuarantine(ret_addr);108109        const address = @intFromPtr(memory.ptr);110        const record_ptr = self.live.getPtr(address) orelse {111            self.recordUnknownFree(address, memory.len, alignment, ret_addr);112            return false;113        };114        if (memory.len != record_ptr.requested_len) {115            self.recordIssue(.{116                .kind = .size_mismatch,117                .address = address,118                .requested_len = memory.len,119                .block_size = record_ptr.block_size,120                .allocation_id = record_ptr.allocation_id,121                .allocation_return_address = record_ptr.allocation_return_address,122                .free_return_address = record_ptr.free_return_address,123                .free_epoch = record_ptr.free_epoch,124                .return_address = ret_addr,125            });126        }127128        _ = self.checkCanary(record_ptr, ret_addr);129130        const total_len = self.totalAllocationLen(new_len, record_ptr.repair_padding) orelse return false;131        if (total_len > record_ptr.block_size) return false;132133        if (record_ptr.kind == .small) {134            const block = record_ptr.small_block.?;135            block.chunk.requested_lens[block.index] = new_len;136        }137        record_ptr.requested_len = new_len;138        record_ptr.canary_issue_reported = false;139        if (self.known.getPtr(address)) |known| known.requested_len = new_len;140        self.installCanary(@ptrFromInt(address), new_len, record_ptr.repair_padding, record_ptr.block_size);141        return true;142    }143144    pub fn rawRemap(self: *Self, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {145        if (self.rawResize(memory, alignment, new_len, ret_addr)) return memory.ptr;146147        const address = @intFromPtr(memory.ptr);148        const old_len = old_len: {149            self.lock();150            defer self.unlock();151            const record = self.live.get(address) orelse return null;152            break :old_len record.requested_len;153        };154155        const new_ptr = self.rawAlloc(new_len, alignment, ret_addr) orelse return null;156        const copy_len = @min(old_len, new_len);157        const old_ptr: [*]u8 = @ptrFromInt(address);158        @memcpy(new_ptr[0..copy_len], old_ptr[0..copy_len]);159        self.rawFree(old_ptr[0..old_len], alignment, ret_addr);160        return new_ptr;161    }162163    pub fn rawFree(self: *Self, memory: []u8, alignment: Alignment, ret_addr: usize) void {164        self.lock();165        defer self.unlock();166167        const address = @intFromPtr(memory.ptr);168        var record = self.live.fetchRemove(address) orelse {169            self.recordUnknownFree(address, memory.len, alignment, ret_addr);170            return;171        };172173        if (memory.len != record.value.requested_len) {174            self.recordIssue(.{175                .kind = .size_mismatch,176                .address = address,177                .requested_len = memory.len,178                .block_size = record.value.block_size,179                .allocation_id = record.value.allocation_id,180                .allocation_return_address = record.value.allocation_return_address,181                .free_return_address = record.value.free_return_address,182                .free_epoch = record.value.free_epoch,183                .return_address = ret_addr,184            });185        }186187        _ = self.checkCanary(&record.value, ret_addr);188189        switch (record.value.kind) {190            .small => self.freeSmall(&record.value, ret_addr),191            .large => self.freeLarge(&record.value, ret_addr),192        }193194        if (self.known.getPtr(address)) |known| known.* = record.value;195    }196197    fn allocateSmall(198        self: *Self,199        class_index: usize,200        requested_len: usize,201        repair_padding: usize,202        total_len: usize,203        alignment: Alignment,204        ret_addr: usize,205    ) ![*]u8 {206        const class_state = &self.classes[class_index];207        if (self.shouldGrow(class_state)) try self.addChunk(class_index, ret_addr);208209        const total_capacity = class_state.capacity;210        if (total_capacity == 0) return error.OutOfMemory;211212        var attempts: usize = 0;213        while (attempts < total_capacity) : (attempts += 1) {214            const ordinal = self.prng.random().int(usize) % total_capacity;215            if (try self.tryAllocateSmallBlock(216                class_state,217                ordinal,218                requested_len,219                repair_padding,220                total_len,221                alignment,222                ret_addr,223            )) |ptr| return ptr;224        }225226        var ordinal = self.prng.random().int(usize) % total_capacity;227        var probes: usize = 0;228        while (probes < total_capacity) : (probes += 1) {229            if (try self.tryAllocateSmallBlock(230                class_state,231                ordinal,232                requested_len,233                repair_padding,234                total_len,235                alignment,236                ret_addr,237            )) |ptr| return ptr;238            ordinal = (ordinal + 1) % total_capacity;239        }240241        try self.addChunk(class_index, ret_addr);242        return self.allocateSmall(class_index, requested_len, repair_padding, total_len, alignment, ret_addr);243    }244245    fn tryAllocateSmallBlock(246        self: *Self,247        class_state: *ClassState,248        ordinal: usize,249        requested_len: usize,250        repair_padding: usize,251        total_len: usize,252        alignment: Alignment,253        ret_addr: usize,254    ) !?[*]u8 {255        const selected = self.blockByOrdinal(class_state, ordinal);256        const chunk = selected.chunk;257        const index = selected.index;258        if (!chunk.isAvailable(index, self.epoch)) return null;259260        const ptr = chunk.blockPtr(index);261        if (!std.mem.isAligned(@intFromPtr(ptr), alignment.toByteUnits())) return null;262263        if (self.diagnosticsActive() and chunk.states[index] == .free and !chunk.free_issue_reported[index]) {264            chunk.free_issue_reported[index] = self.checkFreedPattern(265                ptr,266                chunk.block_size,267                chunk.requested_lens[index],268                chunk.allocation_ids[index],269                chunk.allocation_return_addresses[index],270                chunk.free_return_addresses[index],271                chunk.free_epochs[index],272                chunk.free_patterns[index],273                ret_addr,274            );275        }276277        try self.ensurePageOwnerCapacityFor(@intFromPtr(ptr), chunk.block_size);278279        const allocation_id = self.nextAllocationId();280        chunk.states[index] = .live;281        chunk.free_issue_reported[index] = false;282        chunk.requested_lens[index] = requested_len;283        chunk.repair_paddings[index] = repair_padding;284        chunk.allocation_ids[index] = allocation_id;285        chunk.allocation_return_addresses[index] = ret_addr;286        chunk.free_return_addresses[index] = 0;287        chunk.live_count += 1;288        class_state.live_count += 1;289        self.epoch +%= 1;290291        @memset(ptr[0..@min(requested_len, chunk.block_size)], allocated_byte);292        self.installCanary(ptr, requested_len, repair_padding, chunk.block_size);293294        const record: AllocationRecord = .{295            .kind = .small,296            .address = @intFromPtr(ptr),297            .requested_len = requested_len,298            .repair_padding = repair_padding,299            .block_size = chunk.block_size,300            .backing_len = total_len,301            .alignment = alignment,302            .allocation_id = allocation_id,303            .allocation_return_address = ret_addr,304            .small_block = .{ .chunk = chunk, .index = index },305        };306        self.live.put(record.address, record) catch {307            var cleanup = record;308            self.freeSmall(&cleanup, ret_addr);309            return error.OutOfMemory;310        };311        self.known.put(record.address, record) catch {312            _ = self.live.remove(record.address);313            var cleanup = record;314            self.freeSmall(&cleanup, ret_addr);315            return error.OutOfMemory;316        };317        self.putPageOwnerAssumeCapacity(record);318        return ptr;319    }320321    fn allocateLarge(self: *Self, requested_len: usize, repair_padding: usize, backing_len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {322        const effective_backing_len = self.largeBackingLen(backing_len) orelse return null;323        const effective_alignment = self.largeAlignment(alignment);324        const ptr = self.backing_allocator.rawAlloc(effective_backing_len, effective_alignment, ret_addr) orelse return null;325        @memset(ptr[0..@min(requested_len, effective_backing_len)], allocated_byte);326        self.installCanary(ptr, requested_len, repair_padding, effective_backing_len);327328        const allocation_id = self.nextAllocationId();329        const record: AllocationRecord = .{330            .kind = .large,331            .address = @intFromPtr(ptr),332            .requested_len = requested_len,333            .repair_padding = repair_padding,334            .block_size = effective_backing_len,335            .backing_len = effective_backing_len,336            .alignment = effective_alignment,337            .allocation_id = allocation_id,338            .allocation_return_address = ret_addr,339        };340        self.ensurePageOwnerCapacity(record) catch {341            self.backing_allocator.rawFree(ptr[0..effective_backing_len], effective_alignment, ret_addr);342            return null;343        };344        self.live.put(record.address, record) catch {345            self.backing_allocator.rawFree(ptr[0..effective_backing_len], effective_alignment, ret_addr);346            return null;347        };348        self.known.put(record.address, record) catch {349            _ = self.live.remove(record.address);350            self.backing_allocator.rawFree(ptr[0..effective_backing_len], effective_alignment, ret_addr);351            return null;352        };353        self.putPageOwnerAssumeCapacity(record);354        return ptr;355    }356357    fn largeBackingLen(self: *const Self, backing_len: usize) ?usize {358        return switch (self.config.mode) {359            .dieharder => alignForwardChecked(backing_len, page_size),360            .diehard, .exterminator => backing_len,361        };362    }363364    fn largeAlignment(self: *const Self, alignment: Alignment) Alignment {365        return switch (self.config.mode) {366            .dieharder => .fromByteUnits(@max(alignment.toByteUnits(), page_size)),367            .diehard, .exterminator => alignment,368        };369    }370371    fn freeSmall(self: *Self, record: *AllocationRecord, ret_addr: usize) void {372        const block = record.small_block.?;373        const chunk = block.chunk;374        const ptr = chunk.blockPtr(block.index);375        record.free_pattern = self.nextFreedPattern();376        if (self.writeFreedPattern()) self.fillFreedPattern(ptr, chunk.block_size, record.free_pattern);377        record.free_return_address = ret_addr;378        record.free_epoch = self.epoch;379        record.free_quarantine_epochs = self.config.repairQuarantineEpochs(record.allocation_return_address, ret_addr);380        chunk.states[block.index] = .free;381        chunk.free_return_addresses[block.index] = ret_addr;382        chunk.free_epochs[block.index] = self.epoch;383        chunk.free_quarantine_epochs[block.index] = record.free_quarantine_epochs;384        chunk.free_patterns[block.index] = record.free_pattern;385        chunk.free_issue_reported[block.index] = false;386        chunk.live_count -= 1;387        self.classes[chunk.class_index].live_count -= 1;388        self.epoch +%= 1;389    }390391    fn freeLarge(self: *Self, record: *AllocationRecord, ret_addr: usize) void {392        const ptr: [*]u8 = @ptrFromInt(record.address);393        record.free_pattern = self.nextFreedPattern();394        if (self.writeFreedPattern()) self.fillFreedPattern(ptr, record.backing_len, record.free_pattern);395        record.free_return_address = ret_addr;396        record.free_epoch = self.epoch;397        record.free_quarantine_epochs = self.config.repairQuarantineEpochs(record.allocation_return_address, ret_addr);398        if (record.free_quarantine_epochs > 0) {399            var quarantined = record.*;400            quarantined.free_issue_reported = false;401            self.large_quarantine.append(self.backing_allocator, quarantined) catch {402                self.releaseLarge(record.*, ret_addr);403                return;404            };405            self.epoch +%= 1;406            return;407        }408        self.releaseLarge(record.*, ret_addr);409    }410411    fn releaseLarge(self: *Self, record: AllocationRecord, ret_addr: usize) void {412        const ptr: [*]u8 = @ptrFromInt(record.address);413        self.removePageOwner(record);414        self.backing_allocator.rawFree(ptr[0..record.backing_len], record.alignment, ret_addr);415    }416417    fn releaseLiveLargeAllocations(self: *Self, ret_addr: usize) void {418        var iterator = self.live.valueIterator();419        while (iterator.next()) |record| {420            if (record.kind == .large) self.releaseLarge(record.*, ret_addr);421        }422    }423424    fn addChunk(self: *Self, class_index: usize, ret_addr: usize) !void {425        const class_state = &self.classes[class_index];426        const block_size = size_class.size(class_index);427        const block_stride = self.blockStride(block_size);428        if (class_state.next_chunk_blocks == 0) {429            class_state.next_chunk_blocks = self.initialChunkBlocks(block_stride);430        }431        const capacity = class_state.next_chunk_blocks;432        const area_len = std.math.mul(usize, capacity, block_stride) catch return error.OutOfMemory;433        const alignment = Alignment.fromByteUnits(@max(block_stride, min_alignment));434        const base = self.backing_allocator.rawAlloc(area_len, alignment, ret_addr) orelse return error.OutOfMemory;435        errdefer self.backing_allocator.rawFree(base[0..area_len], alignment, ret_addr);436437        const chunk = try self.backing_allocator.create(Chunk);438        errdefer self.backing_allocator.destroy(chunk);439440        const states = try self.backing_allocator.alloc(BlockState, capacity);441        errdefer self.backing_allocator.free(states);442        const requested_lens = try self.backing_allocator.alloc(usize, capacity);443        errdefer self.backing_allocator.free(requested_lens);444        const allocation_ids = try self.backing_allocator.alloc(u64, capacity);445        errdefer self.backing_allocator.free(allocation_ids);446        const allocation_return_addresses = try self.backing_allocator.alloc(usize, capacity);447        errdefer self.backing_allocator.free(allocation_return_addresses);448        const free_return_addresses = try self.backing_allocator.alloc(usize, capacity);449        errdefer self.backing_allocator.free(free_return_addresses);450        const repair_paddings = try self.backing_allocator.alloc(usize, capacity);451        errdefer self.backing_allocator.free(repair_paddings);452        const free_epochs = try self.backing_allocator.alloc(u64, capacity);453        errdefer self.backing_allocator.free(free_epochs);454        const free_quarantine_epochs = try self.backing_allocator.alloc(u64, capacity);455        errdefer self.backing_allocator.free(free_quarantine_epochs);456        const free_patterns = try self.backing_allocator.alloc(u64, capacity);457        errdefer self.backing_allocator.free(free_patterns);458        const free_issue_reported = try self.backing_allocator.alloc(bool, capacity);459        errdefer self.backing_allocator.free(free_issue_reported);460461        @memset(states, .fresh);462        @memset(requested_lens, 0);463        @memset(repair_paddings, 0);464        @memset(allocation_ids, 0);465        @memset(allocation_return_addresses, 0);466        @memset(free_return_addresses, 0);467        @memset(free_epochs, 0);468        @memset(free_quarantine_epochs, 0);469        @memset(free_patterns, 0);470        @memset(free_issue_reported, false);471        self.fillFreedPattern(base, area_len, self.freshFreedPattern());472473        chunk.* = .{474            .class_index = class_index,475            .block_size = block_size,476            .block_stride = block_stride,477            .capacity = capacity,478            .live_count = 0,479            .base = base,480            .area_len = area_len,481            .states = states,482            .requested_lens = requested_lens,483            .repair_paddings = repair_paddings,484            .allocation_ids = allocation_ids,485            .allocation_return_addresses = allocation_return_addresses,486            .free_return_addresses = free_return_addresses,487            .free_epochs = free_epochs,488            .free_quarantine_epochs = free_quarantine_epochs,489            .free_patterns = free_patterns,490            .free_issue_reported = free_issue_reported,491        };492493        try class_state.chunks.append(self.backing_allocator, chunk);494        class_state.capacity += capacity;495        class_state.next_chunk_blocks = std.math.mul(usize, capacity, 2) catch capacity;496    }497498    fn destroyChunk(self: *Self, chunk: *Chunk) void {499        self.backing_allocator.rawFree(500            chunk.base[0..chunk.area_len],501            .fromByteUnits(@max(chunk.block_stride, min_alignment)),502            @returnAddress(),503        );504        self.backing_allocator.free(chunk.states);505        self.backing_allocator.free(chunk.requested_lens);506        self.backing_allocator.free(chunk.repair_paddings);507        self.backing_allocator.free(chunk.allocation_ids);508        self.backing_allocator.free(chunk.allocation_return_addresses);509        self.backing_allocator.free(chunk.free_return_addresses);510        self.backing_allocator.free(chunk.free_epochs);511        self.backing_allocator.free(chunk.free_quarantine_epochs);512        self.backing_allocator.free(chunk.free_patterns);513        self.backing_allocator.free(chunk.free_issue_reported);514        self.backing_allocator.destroy(chunk);515    }516517    fn blockStride(self: *Self, block_size: usize) usize {518        return switch (self.config.mode) {519            .diehard, .exterminator => block_size,520            .dieharder => if (block_size < page_size) page_size else block_size,521        };522    }523524    fn initialChunkBlocks(self: *Self, block_stride: usize) usize {525        const base = @max(self.config.min_chunk_blocks, 1);526        if (self.config.mode == .dieharder and block_stride >= page_size) return @max(@min(base, 16), 2);527        return base;528    }529530    fn shouldGrow(self: *Self, class_state: *const ClassState) bool {531        if (class_state.capacity == 0) return true;532        return self.config.numerator * (class_state.live_count + 1) >= class_state.capacity * self.config.denominator;533    }534535    fn blockByOrdinal(self: *Self, class_state: *ClassState, ordinal: usize) BlockRef {536        _ = self;537        var remaining = ordinal;538        for (class_state.chunks.items) |chunk| {539            if (remaining < chunk.capacity) return .{ .chunk = chunk, .index = remaining };540            remaining -= chunk.capacity;541        }542        unreachable;543    }544545    fn totalAllocationLen(self: *Self, requested_len: usize, repair_padding: usize) ?usize {546        const occupied_len = std.math.add(usize, @max(requested_len, 1), repair_padding) catch return null;547        return std.math.add(usize, occupied_len, self.config.diagnosticRedZoneBytes()) catch null;548    }549550    fn installCanary(self: *Self, ptr: [*]u8, requested_len: usize, repair_padding: usize, block_size: usize) void {551        const red_zone = self.config.diagnosticRedZoneBytes();552        const start = std.math.add(usize, @max(requested_len, 1), repair_padding) catch return;553        if (red_zone == 0 or start >= block_size) return;554        const canary_len = @min(red_zone, block_size - start);555        @memset(ptr[start .. start + canary_len], canary_byte);556    }557558    fn checkCanary(self: *Self, record: *AllocationRecord, ret_addr: usize) bool {559        const red_zone = self.config.diagnosticRedZoneBytes();560        const start = std.math.add(usize, @max(record.requested_len, 1), record.repair_padding) catch return false;561        if (red_zone == 0 or start >= record.block_size) return false;562        const canary_len = @min(red_zone, record.block_size - start);563        const ptr: [*]u8 = @ptrFromInt(record.address);564        var offset = start;565        while (offset < start + canary_len) : (offset += 1) {566            if (ptr[offset] != canary_byte) {567                if (!record.canary_issue_reported) {568                    self.recordIssue(.{569                        .kind = .buffer_overflow,570                        .address = record.address,571                        .offset = offset,572                        .requested_len = record.requested_len,573                        .block_size = record.block_size,574                        .allocation_id = record.allocation_id,575                        .allocation_return_address = record.allocation_return_address,576                        .free_return_address = record.free_return_address,577                        .free_epoch = record.free_epoch,578                        .return_address = ret_addr,579                    });580                    record.canary_issue_reported = true;581                }582                return true;583            }584        }585        record.canary_issue_reported = false;586        return false;587    }588589    fn scanLiveCanaries(self: *Self, ret_addr: usize) void {590        if (!self.diagnosticsActive()) return;591        var iterator = self.live.valueIterator();592        while (iterator.next()) |record| _ = self.checkCanary(record, ret_addr);593    }594595    fn scanFreedMemory(self: *Self, ret_addr: usize) void {596        if (!self.diagnosticsActive()) return;597        for (&self.classes) |*class_state| {598            for (class_state.chunks.items) |chunk| {599                for (chunk.states, 0..) |state, index| {600                    if (state != .free or chunk.free_issue_reported[index]) continue;601                    chunk.free_issue_reported[index] = self.checkFreedPattern(602                        chunk.blockPtr(index),603                        chunk.block_size,604                        chunk.requested_lens[index],605                        chunk.allocation_ids[index],606                        chunk.allocation_return_addresses[index],607                        chunk.free_return_addresses[index],608                        chunk.free_epochs[index],609                        chunk.free_patterns[index],610                        ret_addr,611                    );612                }613            }614        }615        for (self.large_quarantine.items) |*record| {616            if (record.free_issue_reported) continue;617            const ptr: [*]u8 = @ptrFromInt(record.address);618            record.free_issue_reported = self.checkFreedPattern(619                ptr,620                record.block_size,621                record.requested_len,622                record.allocation_id,623                record.allocation_return_address,624                record.free_return_address,625                record.free_epoch,626                record.free_pattern,627                ret_addr,628            );629        }630    }631632    fn drainLargeQuarantine(self: *Self, ret_addr: usize) void {633        var index: usize = 0;634        while (index < self.large_quarantine.items.len) {635            var record = &self.large_quarantine.items[index];636            if (!record.free_issue_reported) {637                const ptr: [*]u8 = @ptrFromInt(record.address);638                record.free_issue_reported = self.checkFreedPattern(639                    ptr,640                    record.block_size,641                    record.requested_len,642                    record.allocation_id,643                    record.allocation_return_address,644                    record.free_return_address,645                    record.free_epoch,646                    record.free_pattern,647                    ret_addr,648                );649            }650            if (self.epoch -% record.free_epoch < record.free_quarantine_epochs) {651                index += 1;652                continue;653            }654            const removed = self.large_quarantine.swapRemove(index);655            self.releaseLarge(removed, ret_addr);656        }657    }658659    fn checkFreedPattern(660        self: *Self,661        ptr: [*]u8,662        block_size: usize,663        requested_len: usize,664        allocation_id: u64,665        allocation_return_address: usize,666        free_return_address: usize,667        free_epoch: u64,668        pattern: u64,669        ret_addr: usize,670    ) bool {671        var index: usize = 0;672        while (index < block_size) : (index += 1) {673            if (ptr[index] != patternByte(pattern, index)) {674                self.recordIssue(.{675                    .kind = .use_after_free,676                    .address = @intFromPtr(ptr),677                    .offset = index,678                    .requested_len = requested_len,679                    .block_size = block_size,680                    .allocation_id = allocation_id,681                    .allocation_return_address = allocation_return_address,682                    .free_return_address = free_return_address,683                    .free_epoch = free_epoch,684                    .return_address = ret_addr,685                });686                return true;687            }688        }689        return false;690    }691692    fn freshFreedPattern(self: *Self) u64 {693        return switch (self.config.mode) {694            .dieharder => 0,695            .diehard, .exterminator => repeatedPattern(freed_byte),696        };697    }698699    fn nextFreedPattern(self: *Self) u64 {700        return switch (self.config.mode) {701            .dieharder => 0,702            .diehard, .exterminator => sanitizedFreedPattern(self.prng.random().int(u64)),703        };704    }705706    fn nextAllocationId(self: *Self) u64 {707        const id = self.next_allocation_id;708        self.next_allocation_id +%= 1;709        if (self.next_allocation_id == 0) self.next_allocation_id = 1;710        return id;711    }712713    fn writeFreedPattern(self: *Self) bool {714        return switch (self.config.mode) {715            .diehard => self.diagnosticsActive(),716            .dieharder, .exterminator => true,717        };718    }719720    fn fillFreedPattern(self: *Self, ptr: [*]u8, len: usize, pattern: u64) void {721        _ = self;722        var index: usize = 0;723        while (index < len) : (index += 1) ptr[index] = patternByte(pattern, index);724    }725726    fn recordUnknownFree(self: *Self, address: usize, len: usize, alignment: Alignment, ret_addr: usize) void {727        _ = alignment;728        if (self.known.get(address)) |record| {729            self.recordIssue(.{730                .kind = .double_free,731                .address = address,732                .requested_len = len,733                .block_size = record.block_size,734                .allocation_id = record.allocation_id,735                .allocation_return_address = record.allocation_return_address,736                .free_return_address = record.free_return_address,737                .free_epoch = record.free_epoch,738                .return_address = ret_addr,739            });740            return;741        }742        if (self.pageOwnedRecord(address)) |record| {743            self.recordIssue(.{744                .kind = .invalid_free,745                .address = address,746                .offset = address - record.address,747                .requested_len = len,748                .block_size = record.block_size,749                .allocation_id = record.allocation_id,750                .allocation_return_address = record.allocation_return_address,751                .free_return_address = record.free_return_address,752                .free_epoch = record.free_epoch,753                .return_address = ret_addr,754            });755            return;756        }757        if (self.containingKnownRecord(address)) |record| {758            self.recordIssue(.{759                .kind = .invalid_free,760                .address = address,761                .offset = address - record.address,762                .requested_len = len,763                .block_size = record.block_size,764                .allocation_id = record.allocation_id,765                .allocation_return_address = record.allocation_return_address,766                .free_return_address = record.free_return_address,767                .free_epoch = record.free_epoch,768                .return_address = ret_addr,769            });770            return;771        }772        self.recordIssue(.{773            .kind = .invalid_free,774            .address = address,775            .requested_len = len,776            .return_address = ret_addr,777        });778    }779780    fn pageOwnedRecord(self: *Self, address: usize) ?AllocationRecord {781        if (!self.usesPageOwners()) return null;782        const owner_address = self.page_owners.get(pageNumber(address)) orelse return null;783        const record = self.known.get(owner_address) orelse return null;784        if (address <= record.address) return null;785        const end = std.math.add(usize, record.address, record.block_size) catch std.math.maxInt(usize);786        if (address >= end) return null;787        return record;788    }789790    fn containingKnownRecord(self: *Self, address: usize) ?AllocationRecord {791        var iterator = self.known.valueIterator();792        while (iterator.next()) |record| {793            if (address <= record.address) continue;794            const end = std.math.add(usize, record.address, record.block_size) catch std.math.maxInt(usize);795            if (address < end) return record.*;796        }797        return null;798    }799800    fn ensurePageOwnerCapacity(self: *Self, record: AllocationRecord) !void {801        return self.ensurePageOwnerCapacityFor(record.address, record.block_size);802    }803804    fn ensurePageOwnerCapacityFor(self: *Self, address: usize, block_size: usize) !void {805        if (!self.usesPageOwners()) return;806        const pages = std.math.cast(u32, pageSpan(address, block_size)) orelse return error.OutOfMemory;807        try self.page_owners.ensureUnusedCapacity(pages);808    }809810    fn putPageOwnerAssumeCapacity(self: *Self, record: AllocationRecord) void {811        if (!self.usesPageOwners()) return;812        const first_page = pageNumber(record.address);813        const pages = pageSpan(record.address, record.block_size);814        var index: usize = 0;815        while (index < pages) : (index += 1) {816            self.page_owners.putAssumeCapacity(first_page + index, record.address);817        }818    }819820    fn removePageOwner(self: *Self, record: AllocationRecord) void {821        if (!self.usesPageOwners()) return;822        const first_page = pageNumber(record.address);823        const pages = pageSpan(record.address, record.block_size);824        var index: usize = 0;825        while (index < pages) : (index += 1) {826            _ = self.page_owners.remove(first_page + index);827        }828    }829830    fn usesPageOwners(self: *const Self) bool {831        return self.config.mode == .dieharder;832    }833834    fn recordIssue(self: *Self, issue: Issue) void {835        if (!self.diagnosticsActive()) return;836        self.counters.increment(issue.kind);837        self.last_issue = issue;838        self.issues.append(issue);839    }840841    fn diagnosticsActive(self: *const Self) bool {842        return self.config.diagnostics.enabled or self.config.mode == .exterminator;843    }844845    fn lock(self: *Self) void {846        if (!self.config.thread_safe) return;847        while (!self.mutex.tryLock()) std.atomic.spinLoopHint();848    }849850    fn unlock(self: *Self) void {851        if (self.config.thread_safe) self.mutex.unlock();852    }853};

1pub const DeadAllocator = allocator_mod.DeadAllocator;