Arena Allocation

In class, we discussed an alternative memory management discipline, arena allocation. With this scheme, we maintain one or more arenas, large chunks of memory from which we create allocations. We do not worry about manually freeing individual allocations. Instead, we release an arena once when we are done using it!

Ownership-based memory allocation is the correct tool for most programs. However, in the few cases where arena allocation is applicable, it is both more efficient and easier to get right compared to our standard approaches!

In this optional lab, you will implement an arena allocator as introduced in class. Here is the header that you will implement:

// arena.h
#pragma once

#include <stdlib.h>

typedef struct {
    void *base;  // A pointer to the base of the arena's chunk
    void *bound; // A pointer to the end (bound) of the arena's chunk
    void *cur;   // A pointer into the chunk indicating where we allocate next
} arena;

/** Returns a newly initialized area with the given (initial) size. */
arena arena_init (size_t initial_size); 

/** Deallocates the memory within the given arena */
void arena_release (arena ar);

/** Clears the arena, allowing for the arena to be reused from scratch. */
void arena_clear (arena *ar);

/**
  * Allocates a `sz` byte chunk from the given arena, or returns `NULL`
  * if the allocation is not possible, e.g., because the arena has been
  * exhausted and it cannot resize.
  */
void* arena_alloc (arena *ar, size_t sz);

Implement this header in an implementation file called arena.c. In memory, an arena simply keeps track of several pointers into a heap-allocated chunk from which we carve allocations.

  ---------------------------
  |///////|                 |
  ---------------------------
  ∧       ∧                 ∧
  |       |                 |
 base    cur              bound

In the diagram above, the region of memory between the base and cur pointer has already been used for allocations, and the region between cur and bound is free.

To allocate a chunk of memory from this arena, we bump cur by the size of the requested chunk, returning a pointer to the previous cur's location:

  ---------------------------
  |///////|***|             |
  ---------------------------
  ∧       ^   ∧             ∧
  |       |   |             |
 base    ret cur          bound

In the diagram above, the region marked with *s is newly allocated. cur now points past the end of this chunk and arena_alloc would return ret, i.e., where cur was previously pointing.

If an allocation request would move cur past bound, then we cannot service the request with the current chunk. At this point, we can either return NULL, indicating that we failed to allocate memory. Or we can dynamically grow the underlying chunk with realloc, taking care to reestablish all three pointers in our arena in this new chunk.

After you are done implementing arena.c, take one of your previous programs that uses dynamic memory management and retrofit your code to use your arena allocator as a test.