Add headers to the bump allocator:
fn alloc(size: i64) i64 {
var total: i64 = (size + 7) / 8 * 8 + 8;
var block: i64 = heap_ptr;
heap_ptr += total;
if (heap_ptr > heap_limit) { return 0; }
store64(block, total);
return block + 8;
}
alloc(100) allocates 112 bytes (100 rounded to 104, plus 8 for the header). It writes 112 at the block address and returns block + 8.
Given a pointer ptr, the block size is load64(ptr - 8).
Test:
check(
\\var heap_ptr: i64 = 500000;
\\var heap_limit: i64 = 900000;
\\fn alloc(size: i64) i64 {
\\ var total: i64 = (size + 7) / 8 * 8 + 8;
\\ var block: i64 = heap_ptr;
\\ heap_ptr += total;
\\ if (heap_ptr > heap_limit) { return 0; }
\\ store64(block, total);
\\ return block + 8;
\\}
\\var p: i64 = alloc(100);
\\load64(p - 8)
, 112); // 100 -> 104 aligned + 8 header = 112
### The free list
When we free a block, we add it to a free list -- a linked list of available blocks. Each free block stores a pointer to the next free block in its payload area (which isn't being used):
Free block:
┌────────────────┬────────────────┬─────────────────┐
│ block_size │ next_free │ (unused) │
└────────────────┴────────────────┴─────────────────┘
free_list is a global that points to the first free block (or 0 if the list is empty).