Appendix A: A Simple Allocator
block-headers

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).