path: root/examples/heapcheck.zig

//! Does `src/net/heap.zig` survive an editor's allocation pattern in 512 KiB?
//!
//! `Heap` was written for ESP-Hosted and sized by it: its own header says 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".
//! An editor is not that workload. pardes allocates panes, text buffers, cell grids and per-frame
//! scratch in a dozen different sizes and frees them in an order nobody chose. Two properties that
//! were free under fixed-size recycling stop being free:
//!
//!   * **First fit fragments.** Varied sizes leave gaps too small for the next request, and the
//!     symptom is not a clean failure - it is `largest_free` collapsing while `free` stays healthy,
//!     so the heap reports plenty of room and cannot satisfy a grid reallocation.
//!   * **First fit is O(n) in the free list.** One long-lived allocation in the middle of the arena
//!     splits it permanently, and every subsequent walk pays for it.
//!
//! So this measures both, on the die, before the editor depends on it. Each phase prints a line
//! whether it passed or not: a number is the deliverable, not a verdict.
//!
//! The interesting column is `largest/free`. At 1.00 the free space is one block and the heap is
//! pristine; as it falls, that fraction is the largest single allocation still possible. An editor
//! that cannot get one contiguous cell grid is dead regardless of how many bytes are notionally
//! free.

const std = @import("std");
const soc = @import("soc");
const hal = @import("hal");
const heapmod = @import("heap");

/// The upper RAM chunk, from the linker script - the same span the firmware gets.
///
/// Reached with `@extern`, NOT with `extern const __heap_start: anyopaque` plus
/// `@intFromPtr`/`@ptrFromInt`. That spelling cost real debugging on this board. Declaring a linker
/// symbol as an `anyopaque` OBJECT gives the optimiser a zero-sized object to reason about, so a
/// pointer derived from its address carries provenance for zero bytes - and the ordinary
/// (non-volatile) store `Heap.init` makes through it was simply dropped. The symptom was the block
/// header reading back as `size=2988759312 next=0x14284684` instead of `{393216, 0xFFFFFFFF}`, after
/// which the first free-list walk followed garbage and never terminated. With asserts compiled out
/// in ReleaseSmall that is a silent hang, and `examples/memprobe.zig` could not see it because it
/// writes through a `volatile` pointer, which the optimiser must not touch.
///
/// `@extern` with a `[*]u8` result has no size to lose.
const heap_start = @extern([*]align(heapmod.Heap.granule) u8, .{ .name = "__heap_start" });
const heap_end = @extern([*]align(heapmod.Heap.granule) u8, .{ .name = "__heap_end" });

var gpa_heap: heapmod.Heap = undefined;

fn span() []align(heapmod.Heap.granule) u8 {
    return heap_start[0 .. @intFromPtr(heap_end) - @intFromPtr(heap_start)];
}

fn report(tag: [*:0]const u8) void {
    const s = gpa_heap.stats();
    // Split across two calls, and no `%%`: the mask ROM's printf is size-optimised and this file's
    // first version passed it six varargs plus a literal `%%`, which hung. Four is known to work
    // (examples/memprobe.zig's range lines), so this stays inside what has been demonstrated.
    soc.rom.print("MARK HEAP %s total=%u free=%u blocks=%u\r\n", .{
        tag, s.total, s.free, s.free_blocks,
    });
    // `largest` is the number that matters under fragmentation: it is the largest single allocation
    // still possible, whatever `free` claims.
    soc.rom.print("MARK HEAP %s largest=%u\r\n", .{ tag, s.largest_free });
}

/// A deterministic LCG, so a bad run is reproducible. Numerical Recipes' constants.
var rng_state: u32 = 0x1234_5678;
fn rand() u32 {
    rng_state = rng_state *% 1664525 +% 1013904223;
    return rng_state;
}

/// How many live pointers the phases below track. 512 slots at an average of ~512 B is ~256 KiB,
/// half the arena, which is enough to fragment it without trivially exhausting it.
const slots = 512;
var live: [slots][]u8 = undefined;
var live_len: usize = 0;

export fn zig_main() noreturn {
    const s = span();
    // The bootloader leaves the RTC watchdog running and expects the application to take it over.
    // A bare image never did, so every demo in this repo has been resetting on a ten-second cycle
    // (README.md:289-293) - invisible until a run lasted longer than eight seconds. The churn phase
    // below does 20,000 allocations, so this is the first example here that would have hit it: the
    // symptom was HEAP_BOOT printed twice and nothing after.
    const was_armed = hal.rwdt.disable();
    soc.rom.print("MARK HEAP_RWDT was_armed=%u now_armed=%u\r\n", .{
        @as(u32, @intFromBool(was_armed)), @as(u32, @intFromBool(hal.rwdt.armed())),
    });
    soc.rom.print("\r\nMARK HEAP_BOOT 0x%08x..0x%08x %u KiB\r\n", .{
        @as(u32, @intFromPtr(s.ptr)),
        @as(u32, @intFromPtr(s.ptr)) + @as(u32, @intCast(s.len)),
        @as(u32, @intCast(s.len / 1024)),
    });
    gpa_heap = heapmod.Heap.init(s);
    soc.rom.print("MARK HEAP_INIT done\r\n", .{});
    // Read the block header straight back through a volatile pointer. `stats()` walks the free list
    // starting here, so if these two words are not {len, 0xFFFFFFFF} the walk follows garbage and
    // never terminates - and with asserts compiled out in ReleaseSmall that is a silent hang.
    {
        const hdr: *volatile [2]u32 = @ptrFromInt(0x4FF4_0000);
        soc.rom.print("MARK HEAP_HDR size=%u next=0x%08x\r\n", .{ hdr[0], hdr[1] });
    }
    const a = gpa_heap.allocator();
    soc.rom.print("MARK HEAP_VTABLE done\r\n", .{});
    const probe_stats = gpa_heap.stats();
    soc.rom.print("MARK HEAP_STATS total=%u\r\n", .{probe_stats.total});
    report("fresh");

    // ---- phase 1: how much of the arena is actually reachable, and what does the header cost?
    // Allocate one block at a time until refusal, to separate "512 KiB of RAM" from "512 KiB of
    // usable allocations". Each block costs an 8-byte header, so the answer is strictly less.
    {
        var n: u32 = 0;
        var total: usize = 0;
        while (n < slots) {
            const blk = a.alloc(u8, 512) catch break;
            live[n] = blk;
            total += blk.len;
            n += 1;
        }
        live_len = n;
        soc.rom.print("MARK HEAP_FILL %u blocks of 512 B = %u B payload\r\n", .{ n, @as(u32, @intCast(total)) });
        report("filled");
        for (live[0..live_len]) |blk| a.free(blk);
        live_len = 0;
        // Coalescing is the whole design: after freeing everything the arena must be ONE block
        // again. If it is not, `insert`'s merge is wrong and every later number is meaningless.
        report("emptied");
    }

    // ---- phase 2: the fragmentation case. Fill with alternating sizes, free every other block.
    // This is the adversarial pattern for first fit: the holes are all the smaller size, and the
    // next larger request has to walk past every one of them.
    {
        var n: usize = 0;
        while (n < slots) : (n += 1) {
            const size: usize = if (n % 2 == 0) 192 else 320;
            live[n] = a.alloc(u8, size) catch break;
        }
        live_len = n;
        var i: usize = 0;
        while (i < live_len) : (i += 2) a.free(live[i]);
        report("holed");

        // Now ask for something that fits in no single hole and see what the heap does.
        if (a.alloc(u8, 4096)) |big| {
            soc.rom.print("MARK HEAP_BIG 4096 B satisfied after holing\r\n", .{});
            a.free(big);
        } else |_| {
            soc.rom.print("MARK HEAP_BIG 4096 B REFUSED after holing\r\n", .{});
        }
        i = 1;
        while (i < live_len) : (i += 2) a.free(live[i]);
        live_len = 0;
        report("unholed");
    }

    // ---- phase 3: the O(n) first-fit walk, measured rather than argued.
    // Build a long free list, then time one allocation that has to traverse it. `soc.cycles()` is
    // the cycle counter, so this is in real CPU cycles.
    {
        var n: usize = 0;
        while (n < slots) : (n += 1) live[n] = a.alloc(u8, 256) catch break;
        live_len = n;
        // Free every other block to make `free_blocks` large, then measure a request that no hole
        // can satisfy, which is the worst case: the full walk.
        var i: usize = 0;
        while (i < live_len) : (i += 2) a.free(live[i]);
        const before = gpa_heap.stats().free_blocks;

        const t0 = soc.cycles();
        const probe = a.alloc(u8, 1024) catch null;
        const cycles = soc.cycles() - t0;
        soc.rom.print("MARK HEAP_WALK %u free blocks, alloc took %u cycles\r\n", .{ before, @as(u32, @intCast(cycles)) });
        if (probe) |p| a.free(p);

        i = 1;
        while (i < live_len) : (i += 2) a.free(live[i]);
        live_len = 0;
        report("after-walk");
    }

    // ---- phase 4: a long random churn, which is the closest thing here to a real session.
    // Random sizes, random free order, and a running count of refusals. A heap that fragments
    // itself to death shows up as refusals climbing while `free` stays large.
    {
        var refusals: u32 = 0;
        var ops: u32 = 0;
        live_len = 0;
        while (ops < 20000) : (ops += 1) {
            const keep = live_len < slots and (live_len < 64 or rand() % 100 < 55);
            if (keep) {
                // 24 B to ~6 KiB: the spread pardes actually shows, from a small string to a
                // reallocated row buffer.
                const size = 24 + (rand() % 6000);
                if (a.alloc(u8, size)) |blk| {
                    live[live_len] = blk;
                    live_len += 1;
                } else |_| refusals += 1;
            } else if (live_len > 0) {
                const victim = rand() % @as(u32, @intCast(live_len));
                a.free(live[victim]);
                live[victim] = live[live_len - 1];
                live_len -= 1;
            }
        }
        soc.rom.print("MARK HEAP_CHURN %u ops, %u live, %u refusals\r\n", .{ ops, @as(u32, @intCast(live_len)), refusals });
        report("churned");
        for (live[0..live_len]) |blk| a.free(blk);
        live_len = 0;
        report("drained");
    }

    soc.rom.print("MARK HEAP_DONE\r\n", .{});
    while (true) {}
}

export fn _start() linksection(".text.entry") callconv(.naked) noreturn {
    asm volatile (
        \\ li t0, 1 << 13
        \\ csrs mstatus, t0
        \\ la sp, __stack_top
        \\ mv fp, sp
        \\ la t0, __bss_start
        \\ la t1, __bss_end
        \\ bgeu t0, t1, 2f
        \\1:
        \\ sw zero, 0(t0)
        \\ addi t0, t0, 4
        \\ bltu t0, t1, 1b
        \\2:
        \\ j zig_main
    );
}

pub const panic = std.debug.FullPanic(struct {
    fn call(msg: []const u8, _: ?usize) noreturn {
        soc.rom.print("MARK HEAP_PANIC %s\r\n", .{msg.ptr});
        while (true) {}
    }
}.call);