Arenas and pools
When many small objects are created and thrown away together, calling malloc and free for each one is slow and easy to leak. An arena reserves one block and hands out pieces of it, and a reset returns them all at once. A pool does the same with fixed-size slots and reuses them individually.
A bump allocator
The simplest arena keeps a byte buffer and an offset. An allocation returns the address at the offset and moves it forward by the requested size; there is no way to free one block, only to reset the whole arena. The check used + size > sizeof arena is the only failure mode.
#include <stdio.h>
static unsigned char arena[64];
static size_t used = 0;
static void *arena_alloc(size_t size)
{
if (used + size > sizeof arena) {
return NULL;
}
void *block = arena + used;
used += size;
return block;
}
int main(void)
{
int *a = arena_alloc(sizeof *a);
int *b = arena_alloc(sizeof *b);
if (a == NULL || b == NULL) {
return 1;
}
*a = 11;
*b = 22;
printf("%d %d used %zu\n", *a, *b, used);
return 0;
}
gcc -Wall -Wextra bump.c -o bump
./bump
11 22 used 8
Two ints used eight of the sixty-four bytes. The addresses were never stored anywhere and the frees never happen; the whole arena disappears when the program ends or when the owner resets it. That is exactly why an arena is fast: no allocator metadata per block.
Alignment
A pointer to an int must be aligned like an int, usually to four bytes. After a one-byte allocation the offset is odd, so the next allocation rounds it up to a multiple of the alignment before returning the address. The mask (alignment - 1) works because the alignment is a power of two.
#include <stdio.h>
static unsigned char arena[64];
static size_t used = 0;
static void *arena_alloc(size_t size, size_t alignment)
{
size_t start = (used + alignment - 1) & ~(alignment - 1);
if (start + size > sizeof arena) {
return NULL;
}
used = start + size;
return arena + start;
}
int main(void)
{
char *letter = arena_alloc(1, 1);
int *number = arena_alloc(sizeof *number, _Alignof(int));
if (letter == NULL || number == NULL) {
return 1;
}
*letter = 'A';
*number = 42;
size_t offset = (size_t) ((unsigned char *) number - arena);
printf("%c %d\n", *letter, *number);
printf("offset %zu, aligned %d\n", offset, offset % _Alignof(int) == 0);
return 0;
}
gcc -Wall -Wextra align.c -o align
./align
A 42
offset 4, aligned 1
The char took byte zero, so the int starts at four. The subtraction of the two byte pointers gives the offset without any pointer arithmetic on int *, and _Alignof(int) supplies the requirement instead of a hard-coded four.
A fixed-size pool
When every object has the same size, a pool can reuse slots individually. The free slots form a linked list by index, stored in a parallel array, so no pointers are needed and the pool works before any object exists. An allocation pops a slot from the list and a release pushes it back.
#include <stdio.h>
#define SLOTS 4
static int values[SLOTS];
static int next_free[SLOTS];
static int free_head;
static void pool_init(void)
{
for (int i = 0; i < SLOTS - 1; i++) {
next_free[i] = i + 1;
}
next_free[SLOTS - 1] = -1;
free_head = 0;
}
static int pool_alloc(void)
{
if (free_head < 0) {
return -1;
}
int slot = free_head;
free_head = next_free[slot];
return slot;
}
static void pool_release(int slot)
{
next_free[slot] = free_head;
free_head = slot;
}
int main(void)
{
pool_init();
int a = pool_alloc();
int b = pool_alloc();
values[a] = 10;
values[b] = 20;
pool_release(a);
int c = pool_alloc();
values[c] = 30;
printf("slots: %d %d %d\n", a, b, c);
printf("values: %d %d\n", values[a], values[b]);
return 0;
}
gcc -Wall -Wextra pool.c -o pool
./pool
slots: 0 1 0
values: 30 20
Slot 0 was released and handed out again for the third allocation, which overwrote the old ten with thirty. The pool never grows and never asks the system for memory; when it is empty, the next allocation returns -1 and the caller decides whether that is an error or a reason to wait.
Reset all at once
The arena has no free per block, but it has a reset: set the offset back to zero and every block becomes available at once. That suits a request handler that builds a tree, sends the answer and throws the tree away. The memory is reused, not returned, and the next allocation starts at the same address.
#include <stdio.h>
static unsigned char arena[32];
static size_t used = 0;
static void *arena_alloc(size_t size)
{
if (used + size > sizeof arena) {
return NULL;
}
void *block = arena + used;
used += size;
return block;
}
int main(void)
{
int *first = arena_alloc(sizeof *first);
int *second = arena_alloc(sizeof *second);
*first = 1;
*second = 2;
printf("used before reset: %zu\n", used);
used = 0;
int *again = arena_alloc(sizeof *again);
*again = 3;
printf("used after reset: %zu\n", used);
printf("same block reused: %d\n", again == first);
return 0;
}
gcc -Wall -Wextra reset.c -o reset
./reset
used before reset: 8
used after reset: 4
same block reused: 1
The second allocation returned the first address again, which is the promise of the arena and also its danger: any pointer kept across the reset now points at reused memory. The reset belongs at a point where no old pointer can still be used.
Unaligned casts
Casting a byte pointer to an int pointer increases the required alignment, and the compiler can warn about it. The call is not part of -Wall; ask for it with -Wcast-align. Here the cast starts at offset one of a byte array, so the int would be misaligned.
#include <stdio.h>
int main(void)
{
unsigned char buffer[8];
int *number = (int *) (buffer + 1);
*number = 5;
printf("%d\n", *number);
return 0;
}
gcc -Wall -Wextra -Wcast-align=strict castalign.c -o castalign
castalign.c: In function 'main':
castalign.c:6:19: warning: cast increases required alignment of target type [-Wcast-align]
6 | int *number = (int *) (buffer + 1);
| ^
The program is not run here: on x86_64 a misaligned int store usually works, and on other processors it traps, so the result would depend on the machine. The fix is the alignment step from the arena section: round the offset up before casting, and the warning disappears because the compiler can see that the address is a multiple of the requirement.
Exercises
- Extend the arena with a duplicate_string function that copies a string into the arena and returns the copy.
- Add a pool_free_count function to the pool and stop allocating when fewer than two slots remain.
- Allocate ten ints from the arena, reset, allocate ten again, and print both sets of addresses to show the reuse.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
How does a bump allocator return memory to the program?
Answer
By moving an offset back to zero for the whole arena
There is no per-block free: the arena resets its offset and makes every block available at once.
-
What is the danger of keeping a pointer across an arena reset?
Answer
The next allocation reuses it
The reset makes the old addresses available again, so a kept pointer can silently alias a new object.
-
Why does the aligned allocator round the offset up?
Answer
So the returned address meets the type alignment
An
intmust start at an address that is a multiple of its alignment, and the mask rounds the offset up to that boundary. -
How does a fixed-size pool reuse a released slot?
Answer
By returning it to a free list
A release pushes the slot onto a free list, and the next allocation pops it and reuses the same storage.
-
What does this program print?
#include <stdio.h> static unsigned char arena[64]; static size_t used = 0; static void *arena_alloc(size_t size) { if (used + size > sizeof arena) return NULL; void *block = arena + used; used += size; return block; } int main(void) { int *a = arena_alloc(sizeof *a); int *b = arena_alloc(sizeof *b); if (a == NULL || b == NULL) return 1; *a = 11; *b = 22; printf("%d %d used %zu\n", *a, *b, used); return 0; }Answer
11 22 used 8
Each
inttakes four bytes, so two allocations advance the offset by eight. -
What does this program print?
#include <stdio.h> #include <stddef.h> static unsigned char arena[64]; static size_t used = 0; static void *arena_alloc(size_t size, size_t alignment) { size_t start = (used + alignment - 1) & ~(alignment - 1); if (start + size > sizeof arena) return NULL; used = start + size; return arena + start; } int main(void) { char *letter = arena_alloc(1, 1); int *number = arena_alloc(sizeof *number, _Alignof(int)); if (letter == NULL || number == NULL) return 1; *letter = 'A'; *number = 42; size_t offset = (size_t) ((unsigned char *) number - arena); printf("%c %d\noffset %zu, aligned %d\n", *letter, *number, offset, offset % _Alignof(int) == 0); return 0; }Answer
A 42 / offset 4, aligned 1
The one-byte char takes offset zero, and the int starts at the next multiple of four.
-
What does this program print?
#include <stdio.h> #define SLOTS 4 static int values[SLOTS]; static int next_free[SLOTS]; static int free_head; static void pool_init(void) { for (int i = 0; i < SLOTS - 1; i++) next_free[i] = i + 1; next_free[SLOTS - 1] = -1; free_head = 0; } static int pool_alloc(void) { if (free_head < 0) return -1; int slot = free_head; free_head = next_free[slot]; return slot; } static void pool_release(int slot) { next_free[slot] = free_head; free_head = slot; } int main(void) { pool_init(); int a = pool_alloc(); int b = pool_alloc(); values[a] = 10; values[b] = 20; pool_release(a); int c = pool_alloc(); values[c] = 30; printf("slots: %d %d %d\n", a, b, c); printf("values: %d %d\n", values[a], values[b]); return 0; }Answer
slots: 0 1 0 / values: 30 20
Slot 0 is released and reused for the third allocation, which overwrites its old value with 30.
-
What does this program print?
#include <stdio.h> static unsigned char arena[32]; static size_t used = 0; static void *arena_alloc(size_t size) { if (used + size > sizeof arena) return NULL; void *block = arena + used; used += size; return block; } int main(void) { int *first = arena_alloc(sizeof *first); int *second = arena_alloc(sizeof *second); *first = 1; *second = 2; used = 0; int *again = arena_alloc(sizeof *again); *again = 3; printf("used after reset: %zu\n", used); printf("same block reused: %d\n", again == first); return 0; }Answer
used after reset: 4 / same block reused: 1
The reset sets the offset to zero, and one int allocation advances it by four again at the first address.
-
This program is built with
gcc -std=c17 -Wall -Wextra -Wcast-align=strict castalign.c -o castalign. What does GCC warn about?#include <stdio.h> int main(void) { unsigned char buffer[8]; int *number = (int *) (buffer + 1); *number = 5; printf("%d\n", *number); return 0; }Answer
cast increases required alignment of target type [-Wcast-align]
Casting a byte pointer at offset one to
int *produces an address that may not meet the alignment ofint. -
Why is an arena fast for many small objects?
Answer
It uses no per-block allocator metadata
A single offset serves every allocation, and the whole region is released or reset together without per-block bookkeeping.
The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev