Bucket

const Bucket = struct {
    entry: *Allocs.Entry,
    /// Accesed atomically with `.acquire` / `.release` ordering to
    /// provide memory ordering for allocation footers, **expect for
    /// the `modify` field**. This needs `.acquire` fenced every time
    /// footer data is updated (`AllocCount.fenceAcqRel`).
    alloc_count: AllocCount,
    /// Accesed atomically with `.monotonic` ordering. Alternatively,
    /// this is also synchronized by `alloc_count`.
    fill: Fill,

    /// So that `@sizeOf(Bucket)` is the start of first allocation if it is 8-byte aligned or less.
    _: void align(8) = {},
    comptime {
        assert(@alignOf(@This()) >= 8);
    }

    const AllocCount = packed struct(u32) {
        n: u31,
        /// If `true`, this bucket cannot be freed yet.
        filling: bool,

        fn fenceAcqRel(a: *AllocCount) void {
            _ = @atomicRmw(AllocCount, a, .Or, .{ .n = 0, .filling = false }, .acq_rel);
        }
    };

    const Fill = packed struct(u32) {
        at: u31,
        last_is_extended: bool,
    };

    fn of(s: *SafeAllocator, ptr: [*]u8) *Bucket {
        const size_log2 = s.bucket_size_log2;
        return @ptrFromInt(@intFromPtr(ptr) >> @intCast(size_log2) << @intCast(size_log2));
    }

    fn fillAt(s: *SafeAllocator, ptr: [*]const u8) u32 {
        return @intCast(@intFromPtr(ptr) & s.bucketMask());
    }

    fn bytes(b: *Bucket, s: *SafeAllocator) []u8 {
        assert(@intFromPtr(b) & s.bucketMask() == 0);
        return @as([*]u8, @ptrCast(b))[0..s.bucketSize()];
    }

    fn lastAlloc(b: *Bucket, s: *SafeAllocator, fill: Fill) ?*AllocFooter {
        return b.allocFooterBefore(s, fill.at, fill.last_is_extended);
    }

    fn allocFooterBefore(b: *Bucket, s: *SafeAllocator, at: u32, is_extended: bool) ?*AllocFooter {
        if (at - @sizeOf(Bucket) == 0) return null;
        const off = at - AllocFooter.lenBucket(s, is_extended);
        assert(off >= @sizeOf(Bucket));
        return @ptrCast(@alignCast(b.bytes(s)[off..]));
    }

    /// Checks that no writes after frees were performed.
    ///
    /// Assumes `b.alloc_count` has been loaded with `.acquire` ordering.
    fn check(b: *Bucket, s: *SafeAllocator) void {
        var footer = b.lastAlloc(s, b.fill).?;
        while (true) {
            const modify = @atomicLoad(
                AllocFooter.Modify,
                &footer.modify,
                // The only possible value should be `.freed` since `b.alloc_count`
                // has been loaded with `.acquire`. However, another thread may be trying to
                // modify the allocation after it is freed and so the other thread is going
                // to panic even if this thread still sees `.freed`.
                .unordered,
            ).storedXor(&footer.modify);
            if (modify != .freed or footer.actualChecksum(s) != footer.checksum ^ s.canary) {
                panic("corrupted footer metadata in bucket at *{x}", .{@intFromPtr(&footer)});
            }

            s.checkFreed(footer);
            footer = footer.bucketPrev(b, s) orelse break;
        }
    }
}