diff options
Diffstat (limited to 'examples/heapcheck.zig')
| -rw-r--r-- | examples/heapcheck.zig | 240 |
1 files changed, 240 insertions, 0 deletions
diff --git a/examples/heapcheck.zig b/examples/heapcheck.zig new file mode 100644 index 0000000..9d61f71 --- /dev/null +++ b/examples/heapcheck.zig @@ -0,0 +1,240 @@ +//! 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); |