summaryrefslogtreecommitdiff
path: root/src/net/heap.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/net/heap.zig')
-rw-r--r--src/net/heap.zig673
1 files changed, 673 insertions, 0 deletions
diff --git a/src/net/heap.zig b/src/net/heap.zig
new file mode 100644
index 0000000..73ebcf2
--- /dev/null
+++ b/src/net/heap.zig
@@ -0,0 +1,673 @@
+//! 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);
+}
generated by cgit v1.3 (git 2.53.0) at 2026-10-02 23:53:40 +0000