//! Two allocators, because ESP-Hosted needs two different things and `std` supplies neither.
//!
//! **`Heap`** is a general-purpose allocator over a caller-supplied static buffer, exposed through
//! the ordinary `std.mem.Allocator` vtable. Writing one was not the first choice. `std.heap` was
//! read first, and nothing in it fits this workload:
//!
//!   * `FixedBufferAllocator` can only free the *most recent* allocation. ESP-Hosted frees
//!     per-packet buffers in whatever order the radio finishes with them.
//!   * `ArenaAllocator` cannot reclaim at all until the whole arena dies, and this arena never dies.
//!   * `BrkAllocator` (`std/heap/BrkAllocator.zig:38`) rounds its backing store to
//!     `@max(64 * 1024, page_size_max)` per *size class*. One 64 KiB page per class does not fit in
//!     a 128 KiB L2MEM, let alone the ~48 KiB this heap is meant to occupy.
//!   * `DebugAllocator` is page-granular and carries per-page metadata for a debugging feature set
//!     nothing here wants.
//!   * `SmpAllocator`, `PageAllocator`, `c_allocator` all need an OS.
//!
//! So `Heap` is a K&R-style allocator: one address-sorted free list, coalescing on free, first fit.
//! The workload it is sized for is the one the parent measured - `mempool.c` recycling fixed-size
//! buffers - which is exactly the pattern that keeps a coalescing free list short and its first fit
//! O(1) in practice: freed blocks of one size are handed straight back out.
//!
//! **`CHeap`** is the part that has nothing to do with which allocator is underneath. C's `free`
//! takes a bare pointer and no length, and `std.mem.Allocator.rawFree` requires both the exact
//! length and the original alignment. `CHeap` recovers them from an eight-byte header stored
//! immediately below every pointer it hands out. That header is the price of the C ABI and it is
//! paid per allocation:
//!
//!     _h_malloc(n)             -> 8 bytes overhead
//!     _h_malloc_align(n, 64)   -> 64 bytes overhead (the header plus the alignment slack)
//!
//! `CHeap` is written against `std.mem.Allocator`, not against `Heap`, so `install()` can be handed
//! any allocator at all and the C side does not change.

const std = @import("std");
const assert = std.debug.assert;
const Allocator = std.mem.Allocator;
const Alignment = std.mem.Alignment;

// ---------------------------------------------------------------------------------------- Heap

/// A coalescing free-list allocator over one contiguous buffer.
///
/// Not thread-safe, and deliberately so: this runs under a cooperative single-core scheduler where
/// no task can be preempted between two instructions, and every entry point here runs to completion
/// without yielding. An interrupt handler must never allocate - see `port.zig`, which never does.
pub const Heap = struct {
    base: [*]align(granule) u8,
    /// Arena length in bytes, always a multiple of `granule`.
    len: u32,
    /// Offset of the first free block's header, or `null_off`.
    free_head: u32,

    /// Every block header and every payload is 8-byte aligned. Eight is `_Alignof(max_align_t)` on
    /// rv32 (`long long` and `double` are 8-byte aligned), which is the weakest guarantee C's
    /// `malloc` is allowed to make, so it is also the strongest one a caller may assume.
    pub const granule = 8;

    /// Free blocks store their list link in the payload, so a block must hold a header plus one
    /// link. Any split that would leave less than this is absorbed into the neighbour instead.
    const min_block = @sizeOf(Block) + granule;
    const null_off: u32 = std.math.maxInt(u32);

    /// Header of every block, allocated or free.
    ///
    /// `next` is only meaningful while the block is on the free list; in an allocated block it
    /// holds `alloc_magic`, which turns a double free or a wild pointer into an assertion instead
    /// of a corrupted list.
    const Block = extern struct {
        /// Total bytes of this block *including* the header. Always a multiple of `granule`.
        size: u32,
        next: u32,

        const alloc_magic: u32 = 0xA110_C8ED;
    };

    comptime {
        assert(@sizeOf(Block) == granule);
        assert(@alignOf(Block) <= granule);
    }

    /// Take ownership of `buffer`. The whole buffer becomes one free block; nothing else is stored
    /// outside it, so the heap's own footprint is `@sizeOf(Heap)` (12 bytes) plus the buffer.
    pub fn init(buffer: []align(granule) u8) Heap {
        const usable: u32 = @intCast(buffer.len & ~@as(usize, granule - 1));
        assert(usable >= min_block);
        var h: Heap = .{ .base = buffer.ptr, .len = usable, .free_head = 0 };
        const first = h.blockAt(0);
        first.* = .{ .size = usable, .next = null_off };
        return h;
    }

    pub fn allocator(h: *Heap) Allocator {
        return .{ .ptr = h, .vtable = &.{
            .alloc = alloc,
            .resize = resize,
            .remap = remap,
            .free = freeFn,
        } };
    }

    inline fn blockAt(h: *Heap, off: u32) *Block {
        assert(off + @sizeOf(Block) <= h.len);
        return @ptrCast(@alignCast(h.base + off));
    }

    inline fn payloadOf(h: *Heap, off: u32) [*]u8 {
        return h.base + off + @sizeOf(Block);
    }

    fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {
        _ = ret_addr;
        const h: *Heap = @ptrCast(@alignCast(ctx));

        // A zero-length allocation still needs a distinct address with a valid header, because it
        // will be handed back to `free` with its length and must be findable.
        const want: u32 = std.math.cast(u32, std.mem.alignForward(usize, @max(len, granule), granule)) orelse return null;
        const a: u32 = @intCast(@max(granule, alignment.toByteUnits()));

        var prev: u32 = null_off;
        var cur: u32 = h.free_head;
        while (cur != null_off) {
            const blk = h.blockAt(cur);

            // Where the payload would land if the block were used as-is, and how far it has to
            // move to satisfy `a`. A gap smaller than `min_block` cannot become its own free
            // block, so step one whole alignment further - the block was sized for that case.
            const natural = @intFromPtr(h.payloadOf(cur));
            var gap: u32 = @intCast(std.mem.alignForward(usize, natural, a) - natural);
            if (gap != 0 and gap < min_block) gap += a;

            const need = gap + @sizeOf(Block) + want;
            if (blk.size < need) {
                prev = cur;
                cur = blk.next;
                continue;
            }

            // The block that will be handed out starts `gap` bytes into the free block. When
            // `gap` is zero that is the free block itself, which then leaves the list.
            const alloc_off = cur + gap;
            var alloc_size = blk.size - gap;
            const tail_off = alloc_off + @sizeOf(Block) + want;
            const tail_size = alloc_size - @sizeOf(Block) - want;

            if (gap == 0) {
                h.unlink(prev, cur);
            } else {
                // The leading gap stays a free block at the same address, so the list order is
                // unchanged and no relinking is needed.
                blk.size = gap;
            }

            if (tail_size >= min_block) {
                alloc_size -= tail_size;
                const tail = h.blockAt(tail_off);
                tail.* = .{ .size = tail_size, .next = undefined };
                h.insert(tail_off);
            }

            const out = h.blockAt(alloc_off);
            out.* = .{ .size = alloc_size, .next = Block.alloc_magic };
            const payload = h.payloadOf(alloc_off);
            assert(@intFromPtr(payload) % a == 0);
            return payload;
        }
        return null;
    }

    fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) bool {
        _ = alignment;
        _ = ret_addr;
        const h: *Heap = @ptrCast(@alignCast(ctx));
        const off = h.offsetOfPayload(memory.ptr);
        const blk = h.blockAt(off);
        assert(blk.next == Block.alloc_magic);

        const want: u32 = std.math.cast(u32, std.mem.alignForward(usize, @max(new_len, granule), granule)) orelse return false;
        const have = blk.size - @sizeOf(Block);
        if (want <= have) {
            // Shrink: give the tail back if it is big enough to be a block of its own.
            const tail_size = have - want;
            if (tail_size >= min_block) {
                blk.size -= tail_size;
                const tail_off = off + @sizeOf(Block) + want;
                h.blockAt(tail_off).* = .{ .size = tail_size, .next = undefined };
                h.insert(tail_off);
            }
            return true;
        }

        // Grow in place only by swallowing the physically adjacent free block, which is the case
        // that matters: `serial_ll_if.c:282` reassembles a fragmented RPC response by repeatedly
        // reallocating the same buffer upward with nothing allocated after it.
        const next_off = off + blk.size;
        if (next_off >= h.len) return false;
        const prev_link = h.findFreePredecessor(next_off) orelse return false;
        const next = h.blockAt(next_off);
        if (blk.size + next.size < @sizeOf(Block) + want) return false;

        h.unlink(prev_link, next_off);
        blk.size += next.size;
        const tail_size = blk.size - @sizeOf(Block) - want;
        if (tail_size >= min_block) {
            blk.size -= tail_size;
            const tail_off = off + @sizeOf(Block) + want;
            h.blockAt(tail_off).* = .{ .size = tail_size, .next = undefined };
            h.insert(tail_off);
        }
        return true;
    }

    fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
        // Relocation is never cheaper here than the caller's own alloc/copy/free, because this
        // allocator cannot move a block without copying it either.
        return if (resize(ctx, memory, alignment, new_len, ret_addr)) memory.ptr else null;
    }

    fn freeFn(ctx: *anyopaque, memory: []u8, alignment: Alignment, ret_addr: usize) void {
        _ = alignment;
        _ = ret_addr;
        const h: *Heap = @ptrCast(@alignCast(ctx));
        const off = h.offsetOfPayload(memory.ptr);
        // A double free lands here with `next` already holding a list offset rather than the
        // magic, and would otherwise splice the block into the free list twice.
        assert(h.blockAt(off).next == Block.alloc_magic);
        h.insert(off);
    }

    fn offsetOfPayload(h: *Heap, p: [*]u8) u32 {
        const delta = @intFromPtr(p) - @intFromPtr(h.base);
        assert(delta >= @sizeOf(Block) and delta < h.len);
        return @intCast(delta - @sizeOf(Block));
    }

    /// Splice `off` out of the free list. `prev` is its predecessor, or `null_off` if it is head.
    fn unlink(h: *Heap, prev: u32, off: u32) void {
        const nxt = h.blockAt(off).next;
        if (prev == null_off) h.free_head = nxt else h.blockAt(prev).next = nxt;
    }

    /// The free-list predecessor of `off`, or null if `off` is not on the free list at all.
    /// `null_off` is returned when `off` is the head, mirroring `unlink`'s convention.
    fn findFreePredecessor(h: *Heap, off: u32) ?u32 {
        var prev: u32 = null_off;
        var cur = h.free_head;
        while (cur != null_off) : ({
            prev = cur;
            cur = h.blockAt(cur).next;
        }) {
            if (cur == off) return prev;
            if (cur > off) return null;
        }
        return null;
    }

    /// Insert a block into the address-sorted free list, coalescing with either neighbour it
    /// physically touches. Address order is what makes coalescing a pointer comparison rather than
    /// a search, and it is why the list is sorted at all.
    fn insert(h: *Heap, off: u32) void {
        var prev: u32 = null_off;
        var cur = h.free_head;
        while (cur != null_off and cur < off) : ({
            prev = cur;
            cur = h.blockAt(cur).next;
        }) {}

        const blk = h.blockAt(off);
        blk.next = cur;
        if (prev == null_off) h.free_head = off else h.blockAt(prev).next = off;

        if (cur != null_off and off + blk.size == cur) {
            const nxt = h.blockAt(cur);
            blk.size += nxt.size;
            blk.next = nxt.next;
        }
        if (prev != null_off) {
            const p = h.blockAt(prev);
            if (prev + p.size == off) {
                p.size += blk.size;
                p.next = blk.next;
            }
        }
    }

    pub const Stats = struct {
        /// Bytes in the arena, header overhead included.
        total: u32,
        /// Bytes on the free list, header overhead included.
        free: u32,
        /// Largest single free block, which is the largest allocation that can still succeed
        /// (less one header, less alignment slack).
        largest_free: u32,
        free_blocks: u32,
    };

    pub fn stats(h: *Heap) Stats {
        var s: Stats = .{ .total = h.len, .free = 0, .largest_free = 0, .free_blocks = 0 };
        var cur = h.free_head;
        while (cur != null_off) : (cur = h.blockAt(cur).next) {
            const size = h.blockAt(cur).size;
            s.free += size;
            s.free_blocks += 1;
            if (size > s.largest_free) s.largest_free = size;
        }
        return s;
    }

    /// Walk the free list and assert every invariant. Used by the tests; also usable from a
    /// hardware self-test, where a corrupted list is otherwise invisible until it is fatal.
    pub fn check(h: *Heap) void {
        var cur = h.free_head;
        var prev: u32 = null_off;
        while (cur != null_off) {
            const blk = h.blockAt(cur);
            assert(blk.size >= min_block);
            assert(blk.size % granule == 0);
            assert(cur % granule == 0);
            assert(cur + blk.size <= h.len);
            if (prev != null_off) {
                // Sorted, and never two free blocks that touch: `insert` would have merged them.
                assert(prev < cur);
                assert(prev + h.blockAt(prev).size < cur);
            }
            prev = cur;
            cur = blk.next;
        }
    }
};

// --------------------------------------------------------------------------------------- CHeap

/// C `malloc`/`free`/`realloc` semantics on top of any `std.mem.Allocator`.
///
/// The whole reason this type exists is that `free(p)` carries no size and `rawFree` demands one.
/// Every pointer handed to C therefore has a `Header` in the eight bytes below it, holding what
/// `rawFree` needs: the exact length that was allocated, and the distance back to the base pointer.
///
/// The alignment passed to the backing allocator is always `granule` (8). Stronger alignments are
/// satisfied *inside* the allocation by over-allocating and moving the payload up, rather than by
/// asking the backing allocator for them - which keeps the header immediately below the payload in
/// every case, and means `Heap` only ever sees one alignment.
pub const CHeap = struct {
    gpa: Allocator,

    /// Live bytes as seen by C, i.e. what was asked for, not what was consumed. `bytes_reserved`
    /// is the honest number.
    bytes_live: usize = 0,
    bytes_reserved: usize = 0,
    peak_reserved: usize = 0,
    blocks_live: usize = 0,
    /// Allocations that returned NULL. Nonzero means the heap is too small; ESP-Hosted logs and
    /// limps on rather than failing loudly, so this counter is the only durable evidence.
    failures: usize = 0,

    pub const granule = Heap.granule;

    const Header = extern struct {
        /// Bytes passed to `rawAlloc`, and therefore the length `rawFree` must be given.
        total: u32,
        /// `payload - base`. Between `granule` and the requested alignment, inclusive.
        offset: u16,
        /// `log2` of the alignment C asked for. Kept for `realloc`, which must preserve it.
        log2_align: u8,
        magic: u8,

        const value: u8 = 0x48; // 'H'
    };

    comptime {
        assert(@sizeOf(Header) == granule);
        assert(@alignOf(Header) <= granule);
    }

    /// The strongest alignment expressible in `Header.offset`. ESP-Hosted asks for at most 64
    /// (`HOSTED_MEM_ALIGNMENT_64`, port_esp_hosted_host_os.h:95).
    pub const max_alignment = 1 << 15;

    pub fn malloc(c: *CHeap, size: usize) ?[*]u8 {
        return c.mallocAligned(size, granule);
    }

    /// `size` is rounded up to a multiple of `alignment` before allocating, which is what
    /// `heap_caps_aligned_alloc` does and therefore what `_h_malloc_align`'s callers get today.
    /// It matters for DMA: a buffer whose *end* is not aligned shares its last cache line with
    /// whatever follows it.
    pub fn mallocAligned(c: *CHeap, size: usize, alignment: usize) ?[*]u8 {
        assert(std.math.isPowerOfTwo(alignment));
        assert(alignment <= max_alignment);
        const a = @max(granule, alignment);

        const payload = std.mem.alignForward(usize, @max(size, 1), a);
        // `a` bytes of slack is always enough: the base is `granule`-aligned, the header needs
        // `granule` of that slack, and moving up to the next `a` boundary costs at most `a -
        // granule` more.
        const total = std.math.add(usize, payload, a) catch {
            c.failures += 1;
            return null;
        };

        const base = c.gpa.rawAlloc(total, .fromByteUnits(granule), @returnAddress()) orelse {
            c.failures += 1;
            return null;
        };
        const user_addr = std.mem.alignForward(usize, @intFromPtr(base) + @sizeOf(Header), a);
        const offset = user_addr - @intFromPtr(base);
        assert(offset >= @sizeOf(Header) and offset <= a);
        assert(offset + payload <= total);

        const user: [*]u8 = @ptrFromInt(user_addr);
        headerOf(user).* = .{
            .total = @intCast(total),
            .offset = @intCast(offset),
            .log2_align = @intCast(std.math.log2_int(usize, a)),
            .magic = Header.value,
        };

        c.bytes_live += size;
        c.bytes_reserved += total;
        c.blocks_live += 1;
        if (c.bytes_reserved > c.peak_reserved) c.peak_reserved = c.bytes_reserved;
        return user;
    }

    pub fn calloc(c: *CHeap, count: usize, size: usize) ?[*]u8 {
        const n = std.math.mul(usize, count, size) catch {
            c.failures += 1;
            return null;
        };
        const p = c.malloc(n) orelse return null;
        @memset(p[0..n], 0);
        return p;
    }

    pub fn free(c: *CHeap, ptr: ?[*]u8) void {
        const user = ptr orelse return;
        const h = headerOf(user).*;
        assert(h.magic == Header.value);
        const base: [*]u8 = @ptrFromInt(@intFromPtr(user) - h.offset);
        // Poison the magic so a second free asserts here rather than corrupting the backing
        // allocator's own bookkeeping several calls later.
        headerOf(user).magic = 0;

        c.bytes_live -|= usableLen(h);
        c.bytes_reserved -= h.total;
        c.blocks_live -= 1;
        c.gpa.rawFree(base[0..h.total], .fromByteUnits(granule), @returnAddress());
    }

    /// C `realloc`: null pointer means allocate, zero size means free, and the old contents are
    /// preserved up to the smaller of the two sizes.
    ///
    /// Growth in place is attempted first. `serial_ll_if.c:282` reassembles a fragmented RPC
    /// response by calling this in a loop on the same buffer, so a `realloc` that always copies
    /// turns an n-fragment response into O(n^2) bytes moved.
    pub fn realloc(c: *CHeap, ptr: ?[*]u8, new_size: usize) ?[*]u8 {
        const user = ptr orelse return c.malloc(new_size);
        if (new_size == 0) {
            c.free(user);
            return null;
        }

        const h = headerOf(user).*;
        assert(h.magic == Header.value);
        const a = @as(usize, 1) << @intCast(h.log2_align);
        const old_usable = usableLen(h);
        if (new_size <= old_usable) return user;

        const base: [*]u8 = @ptrFromInt(@intFromPtr(user) - h.offset);
        const new_total = std.math.add(usize, std.mem.alignForward(usize, new_size, a), a) catch {
            c.failures += 1;
            return null;
        };
        if (c.gpa.rawResize(base[0..h.total], .fromByteUnits(granule), new_total, @returnAddress())) {
            c.bytes_live += new_size - old_usable;
            c.bytes_reserved += new_total - h.total;
            if (c.bytes_reserved > c.peak_reserved) c.peak_reserved = c.bytes_reserved;
            headerOf(user).total = @intCast(new_total);
            return user;
        }

        const fresh = c.mallocAligned(new_size, a) orelse return null;
        @memcpy(fresh[0..old_usable], user[0..old_usable]);
        c.free(user);
        return fresh;
    }

    /// Bytes the caller may legitimately touch. Larger than what was asked for whenever the
    /// request was rounded up to the alignment.
    fn usableLen(h: Header) usize {
        return h.total - h.offset;
    }

    inline fn headerOf(user: [*]u8) *Header {
        return @ptrFromInt(@intFromPtr(user) - @sizeOf(Header));
    }
};

// ---------------------------------------------------------------------------------------- tests

const testing = std.testing;

fn testHeap(comptime bytes: usize) struct { buf: []align(Heap.granule) u8, heap: Heap } {
    const buf = testing.allocator.alignedAlloc(u8, .fromByteUnits(Heap.granule), bytes) catch unreachable;
    return .{ .buf = buf, .heap = Heap.init(buf) };
}

test "Heap: alloc, free, and reuse of a hole in the middle" {
    var t = testHeap(4096);
    defer testing.allocator.free(t.buf);
    const a = t.heap.allocator();

    const p0 = try a.alloc(u8, 64);
    const p1 = try a.alloc(u8, 64);
    const p2 = try a.alloc(u8, 64);
    t.heap.check();

    // Free the middle one. An arena or a FixedBufferAllocator cannot give this back; the whole
    // point of this allocator is that the next 64-byte request lands right here.
    a.free(p1);
    t.heap.check();
    const p3 = try a.alloc(u8, 64);
    try testing.expectEqual(p1.ptr, p3.ptr);

    a.free(p0);
    a.free(p2);
    a.free(p3);
    t.heap.check();
    // Everything coalesced back into one block.
    const s = t.heap.stats();
    try testing.expectEqual(@as(u32, 1), s.free_blocks);
    try testing.expectEqual(s.total, s.free);
}

test "Heap: the malloc/free/realloc churn that defeats an arena" {
    var t = testHeap(16 * 1024);
    defer testing.allocator.free(t.buf);
    const a = t.heap.allocator();

    // mempool.c's pattern: allocate a batch of same-size buffers, release them in a scrambled
    // order, allocate the same batch again. An arena's high-water mark would double each round;
    // this must not grow at all.
    var live: [16][]u8 = undefined;
    const order = [_]usize{ 7, 0, 15, 3, 11, 1, 9, 4, 13, 2, 8, 6, 14, 5, 12, 10 };

    for (&live) |*slot| slot.* = try a.alloc(u8, 200);
    const after_first_round = t.heap.stats().free;

    for (0..8) |_| {
        for (order) |i| a.free(live[i]);
        t.heap.check();
        for (&live) |*slot| slot.* = try a.alloc(u8, 200);
        t.heap.check();
        try testing.expectEqual(after_first_round, t.heap.stats().free);
    }
    for (live) |slot| a.free(slot);

    // Interleave reallocs that grow past their block, which is the serial reassembly path.
    var grow = try a.alloc(u8, 32);
    @memset(grow, 0xAB);
    var n: usize = 64;
    while (n <= 2048) : (n *= 2) {
        const old_len = grow.len;
        grow = try a.realloc(grow, n);
        try testing.expect(std.mem.allEqual(u8, grow[0..old_len], 0xAB));
        @memset(grow[old_len..], 0xAB);
        t.heap.check();
    }
    a.free(grow);
    t.heap.check();
    try testing.expectEqual(t.heap.stats().total, t.heap.stats().free);
}

test "Heap: strong alignment splits the leading gap back into the free list" {
    var t = testHeap(8192);
    defer testing.allocator.free(t.buf);
    const a = t.heap.allocator();

    // 64-byte alignment is what _h_malloc_align asks for on the SDIO data path.
    var blocks: [8][]align(64) u8 = undefined;
    for (&blocks, 0..) |*b, i| {
        b.* = try a.alignedAlloc(u8, .@"64", 100 + i);
        try testing.expectEqual(@as(usize, 0), @intFromPtr(b.ptr) % 64);
    }
    t.heap.check();
    for (blocks) |b| a.free(b);
    t.heap.check();
    try testing.expectEqual(t.heap.stats().total, t.heap.stats().free);
}

test "Heap: exhaustion returns null rather than trampling the arena" {
    var t = testHeap(1024);
    defer testing.allocator.free(t.buf);
    const a = t.heap.allocator();

    var held: [64][]u8 = undefined;
    var n: usize = 0;
    while (n < held.len) : (n += 1) {
        held[n] = a.alloc(u8, 64) catch break;
    }
    try testing.expect(n > 0 and n < held.len);
    try testing.expectError(error.OutOfMemory, a.alloc(u8, 64));
    t.heap.check();
    for (held[0..n]) |b| a.free(b);
    t.heap.check();
    try testing.expectEqual(t.heap.stats().total, t.heap.stats().free);
}

test "CHeap: malloc/free/realloc against the C ABI, over the Heap" {
    var t = testHeap(16 * 1024);
    defer testing.allocator.free(t.buf);
    var c: CHeap = .{ .gpa = t.heap.allocator() };

    const p = c.malloc(100).?;
    @memset(p[0..100], 0x5A);
    try testing.expectEqual(@as(usize, 0), @intFromPtr(p) % CHeap.granule);
    try testing.expectEqual(@as(usize, 1), c.blocks_live);

    // realloc must preserve contents across a move.
    const q = c.realloc(p, 4000).?;
    try testing.expect(std.mem.allEqual(u8, q[0..100], 0x5A));
    // Shrinking inside the same block returns the same pointer, as C permits.
    try testing.expectEqual(q, c.realloc(q, 8).?);
    c.free(q);
    try testing.expectEqual(@as(usize, 0), c.blocks_live);
    try testing.expectEqual(@as(usize, 0), c.bytes_reserved);

    // calloc zeroes.
    const z = c.calloc(10, 16).?;
    try testing.expect(std.mem.allEqual(u8, z[0..160], 0));
    c.free(z);

    // free(NULL) is a no-op, and realloc(NULL, n) is malloc.
    c.free(null);
    const r = c.realloc(null, 32).?;
    // realloc(p, 0) frees and yields NULL.
    try testing.expectEqual(@as(?[*]u8, null), c.realloc(r, 0));
    try testing.expectEqual(@as(usize, 0), c.blocks_live);

    t.heap.check();
    try testing.expectEqual(t.heap.stats().total, t.heap.stats().free);
}

test "CHeap: _h_malloc_align(n, 64) is 64-aligned at both ends and frees exactly" {
    // 12 x (1536 rounded to 64, plus 64 of header and slack) = 19,200 bytes, plus block headers.
    var t = testHeap(24 * 1024);
    defer testing.allocator.free(t.buf);
    var c: CHeap = .{ .gpa = t.heap.allocator() };

    var held: [12][*]u8 = undefined;
    for (&held, 0..) |*slot, i| {
        slot.* = c.mallocAligned(1536 - i, 64).?;
        try testing.expectEqual(@as(usize, 0), @intFromPtr(slot.*) % 64);
    }
    // 64-byte alignment costs exactly 64 bytes of overhead per buffer: the eight-byte header plus
    // the slack that moves the payload onto the boundary.
    try testing.expectEqual(@as(usize, 12), c.blocks_live);
    for (held) |slot| c.free(slot);
    try testing.expectEqual(@as(usize, 0), c.bytes_reserved);
    t.heap.check();
    try testing.expectEqual(t.heap.stats().total, t.heap.stats().free);
}

test "CHeap: allocation failure is reported, not fatal" {
    var t = testHeap(1024);
    defer testing.allocator.free(t.buf);
    var c: CHeap = .{ .gpa = t.heap.allocator() };

    try testing.expectEqual(@as(?[*]u8, null), c.malloc(100_000));
    try testing.expectEqual(@as(usize, 1), c.failures);
    // The heap is untouched by the failure.
    t.heap.check();
    try testing.expectEqual(t.heap.stats().total, t.heap.stats().free);
}