89 Allocation is a parameter

89.1 An allocator is a value

proven_allocator_t is one struct — a context pointer and three function pointers (allocate, reallocate, free). There is no special global and no registration procedure. Being simply a value, it can be passed as an argument, held in a struct, and returned from a function. The virtual function table seen in chapter 59 is here as it stands.

typedef struct {
    void *ctx;                        /* this allocator's state (for an arena, the arena) */
    proven_alloc_fn_t   alloc_fn;
    proven_realloc_fn_t realloc_fn;
    proven_free_fn_t    free_fn;
} proven_allocator_t;

The three functions’ signatures write the contract down as they stand.

proven_result_mem_mut_t (*alloc_fn)(void *ctx, proven_size_t size,
                                    proven_size_t align);
proven_result_mem_mut_t (*realloc_fn)(void *ctx, void *old_ptr,
                                      proven_size_t old_size,
                                      proven_size_t new_size,
                                      proven_size_t align);
void                    (*free_fn)(void *ctx, void *ptr);

Why pass old_size and align too. The standard realloc does not ask the old size — because the allocator wrote it into the block’s header (chapter 84). But an arena has no header. Not making a place to write the size is why an arena is fast, so the choice was for the caller to tell it instead. This decision is what lets a “headerless allocator” fit the same interface.

Four things from the contract must be remembered.

1. align must be a power of two. And a block must be reallocated and freed with the same alignment it was allocated with. Because the heap allocator handles requests at or below the default alignment differently from stricter ones (chapter 88) — handing a block back in a different alignment class is outside the contract.
2. size == 0 is INVALID_ARG. A zero-byte allocation is treated as a caller’s bug. Before this rule the heap said NOMEM (a lie — nothing was out of memory) and the arena returned a valid pointer, so the answer differed per allocator. Generic code cannot be written on a rule like that.
3. A reallocation with new_size == 0 is a free — it gives a null pointer and PROVEN_OK.
4. Reallocation is failure-atomic. On failure old_ptr is still valid and its contents untouched — chapter 66′s realloc leak counterexample blocked at the level of the interface.

And every function that allocates has this shape.

proven_result_u8str_t proven_u8str_create(proven_allocator_t alloc,
                                          proven_size_t limit);
void                  proven_u8str_destroy(proven_allocator_t alloc,
                                           proven_u8str_t *str);

Destroy with the allocator given at creation — that is the whole of the ownership rule.

89.2 Swapping the three sources

/* The same code, three sources of memory — the heap, an arena, a pool.
   What it makes possible that an allocator is simply a value. */
#include <proven.h>

/* This function does not know where the memory it uses comes from.
   Taking an allocator as a parameter is itself "it may allocate", written in
   the signature. */
static proven_err_t make_list(proven_allocator_t alloc, int n, proven_u8str_t *out)
{
    proven_result_u8str_t made = proven_u8str_create(alloc, 128);
    if (!proven_is_ok(made.err)) return made.err;

    proven_u8str_t s = made.value;
    for (int i = 1; i <= n; i++) {
        proven_fmt_result_t r =
            proven_u8str_append_fmt(&s, i == 1 ? "{}" : ", {}", PROVEN_ARG(i));
        if (!proven_is_ok(r.err)) {
            proven_u8str_destroy(alloc, &s);
            return r.err;
        }
    }
    *out = s;
    return PROVEN_OK;
}

static void run(const char *where, proven_allocator_t alloc)
{
    proven_u8str_t s;
    proven_err_t e = make_list(alloc, 6, &s);
    if (!proven_is_ok(e)) {
        proven_println("{:<8} failed (code {})", PROVEN_ARG(where), PROVEN_ARG((int)e));
        return;
    }
    proven_println("{:<8} {}", PROVEN_ARG(where), PROVEN_ARG(proven_u8str_as_view(&s)));
    proven_u8str_destroy(alloc, &s);      /* through the very allocator it was made with */
}

int main(void)
{
    /* ── (1) the heap — standard malloc wrapped in the interface ──── */
    run("heap", proven_heap_allocator());

    /* ── (2) an arena — on a static array. malloc is never called ─── */
    static proven_byte_t backing[512];
    proven_arena_t arena = proven_arena_create(
        (proven_mem_mut_t){ .ptr = backing, .size = sizeof backing });
    run("arena", proven_arena_as_allocator(&arena));

    proven_println("  arena in use: {} / {} bytes",
                   PROVEN_ARG(arena.offset), PROVEN_ARG(arena.backing.size));

    /* an arena is released not piece by piece but whole */
    proven_arena_reset(&arena);
    proven_println("  in use after the reset: {} (individual frees did nothing)",
                   PROVEN_ARG(arena.offset));

    /* ── (3) a pool — pieces of one size, handed round ───────────── */
    proven_pool_t pool;
    proven_err_t pe = proven_pool_init(&pool, proven_heap_allocator(),
                                       /* item_size  */ 129,
                                       /* item_align */ PROVEN_MAX_ALIGN,
                                       /* bin_cap    */ 8);
    if (proven_is_ok(pe)) {
        proven_allocator_t pa = proven_pool_as_allocator(&pool);
        run("pool", pa);
        run("pool", pa);          /* the second reuses the piece given back a moment ago */
        proven_pool_destroy(&pool);
    }

    /* ── (4) when an arena runs dry — the failure arrives as a value ─ */
    proven_arena_t tiny = proven_arena_create(
        (proven_mem_mut_t){ .ptr = backing, .size = 64 });
    proven_u8str_t s;
    proven_err_t e = make_list(proven_arena_as_allocator(&tiny), 6, &s);
    proven_println("a 64-byte arena -> code {} (a refusal, not a collapse)",
                   PROVEN_ARG((int)e));
    return 0;
}

heap     1, 2, 3, 4, 5, 6
arena    1, 2, 3, 4, 5, 6
  arena in use: 129 / 512 bytes
  in use after the reset: 0 (individual frees did nothing)
pool     1, 2, 3, 4, 5, 6
pool     1, 2, 3, 4, 5, 6
a 64-byte arena -> code 1 (a refusal, not a collapse)

Look at the make_list function. This function does not know whether the memory it uses comes from malloc, from a static array, or from a recycling bin. The caller settles it, and the same code runs identically over all three.

Three things can be read in the output.

① An arena’s usage is visible. That arena.offset is 129 means exactly 129 bytes (128 of content + 1 NUL) went out for one string. A number that cannot be known on the heap can be counted in an arena — in embedded work this transparency pays when setting a memory budget.

② Reset makes individual release meaningless. The usage did not fall although destroy was called (an arena’s free does nothing), and one reset took it to 0. “Instead of giving back individually, give the whole back” is this picture.

③ When it runs dry it refuses as a value. Requesting 128 bytes from a 64-byte arena gave back NOMEM (1). It neither collapses nor quietly falls back to the heap.

89.3 The arena — things of the same lifetime, all at once

Chapter 45 taught the heap’s three dangers (leak, double free, use after free). All three come from individual release. Then what if individual release were removed — that is the arena’s idea.

An arena takes one large lump of memory and, whenever a request comes, cuts from the front. There is a release function but it does nothing. Instead there is reset — it returns everything at once.

That the struct has only two slots shows this simplicity as it stands.

typedef struct {
    proven_mem_mut_t backing;   /* the memory that backs it (borrowed) */
    proven_size_t    offset;    /* how far it has been handed out */
} proven_arena_t;

An arena does not own its memory. That backing is a writing window (mem_mut_t) is that declaration — a static array, a stack array, or a lump received once from the heap is prepared by the caller, and the arena only cuts on top of it. So proven_arena_destroy does nothing (there is nothing borrowed to give back). If the lump came from the heap, returning it is still the caller’s part.

The life cycle is four steps.

The allocation function has four editions. Choose the one that fits.

The _or_panic family exists for the reason given in chapter 87 — where the memory budget has been calculated in advance (embedded work is representative), “the arena is short” is not a failure to recover from but a design error, so demanding a check every time is rather noise.

The realloc has one interesting property. An arena having no header, ordinary reallocation is “cut anew and copy”, but if the block being grown happens to be the last one handed out it can grow in place simply by pushing offset. It is why code that appends to a string a little at a time is fast on an arena, and why calling chapter 90′s proven_u8str_reserve in advance pays especially on an arena (an intervening allocation breaks the property).

#include <proven.h>
#include <stdio.h>

int main(void)
{
    /* An arena: the backing memory is given whole, and pieces are carved out of it */
    static unsigned char backing[1024];
    proven_arena_t arena = proven_arena_create(
        (proven_mem_mut_t){ .ptr = backing, .size = sizeof backing });

    proven_result_mem_mut_t a = proven_arena_alloc(&arena, 100);
    proven_result_mem_mut_t b = proven_arena_alloc(&arena, 200);

    if (!proven_is_ok(a.err) || !proven_is_ok(b.err)) {
        printf("arena allocation failed\n");
        return 1;
    }
    printf("carved two blocks: %zu, %zu bytes\n", a.value.size, b.value.size);

    /* there is no individual free — things of the same lifetime are given back at once */
    proven_arena_reset(&arena);
    printf("one reset reclaimed everything\n");

    /* a request larger than the vessel comes back as a failure value (it does not collapse) */
    proven_result_mem_mut_t too_big = proven_arena_alloc(&arena, 100000);
    printf("oversized request: %s\n", proven_is_ok(too_big.err) ? "granted" : "refused");
    return 0;
}

carved two blocks: 100, 200 bytes
one reset reclaimed everything
oversized request: refused

There really are many places this model fits. The temporary data made while handling one request, a game’s calculation results used for one frame, the syntax tree made while parsing one file — all data born at different moments but dying at the same one. For such data, individual release is only cost and risk.

The pool (proven_pool_t) is the third branch. It is used where objects of the same size are repeatedly made and unmade — a game’s bullets, a server’s connection objects, a parser’s nodes. The slot size being fixed there is no fragmentation, and a returned slot is reused at once. A pool too becomes an allocator through proven_pool_as_allocator, so the previous example’s build function runs on it as it is.

proven_result_u8str_t r = proven_u8str_create(proven_heap_allocator(), 64);
...
proven_u8str_destroy(proven_arena_as_allocator(&arena), &r.value);  /* wrong */

proven_u8str_t name;
for (int i = 0; i < n; i++) {
    proven_arena_reset(&per_request);        /* taken back per request */
    handle(proven_arena_as_allocator(&per_request), &name);
}
use(&name);        /* ← dangerous. what name pointed at has already gone back */

89.4 Which to choose

In practice these four are layered. The program as a whole uses the heap, while handling one request uses a request arena, and a data structure making thousands of nodes inside it lays a pool on top. That all three share the same interface, so that layering needs no special device, is the value of this design.

89.5 Owning and borrowing, and state that points at itself

Now we return to chapter 85′s fourth bug. The problem of char * meaning four things is solved by dividing the type in two.

• Owned — things such as proven_u8str_t and proven_array_t. Obtained with _create and let go with _destroy.
• Borrowed — proven_u8str_view_t, proven_mem_view_t. Never destroyed. When the owner vanishes they become invalid with it.

That “must I release this?” can be answered from the signature alone is the whole of this distinction and its purpose.

There is one more rule attached. State that points at itself is not copied. Chapter 46 taught that struct assignment is a shallow copy. Copy an object that holds inside a pointer to its own buffer that way, and the copy’s pointer still points at the original, so two objects share the same memory and destroying both is a double free. So such objects are not copied by value but passed by pointer.

We have set up the rules for obtaining and letting go of memory. From the next chapter come the real components that rise on top of it — first, the strings this book warned about all through chapter 42.