I wrote a pool allocator (Arena) for a compiler I'm writing.
My use case for this allocator is for storing the parse tree because it allows me to free all the memory at once, so I don't need to keep a reference to each node (which makes the code and logic a big mess).
The implementation uses a singly linked list of blocks. For each block more memory than needed is allocated, and then the "tail" memory is used for allocating.
To align the allocated memory I used union align (a union with types that have the strictest alignment requirements according to the book), a trick I learned from the book C Interfaces and Implementations.
The union header is for calculating the aligned size of the Arena struct.
The error if malloc() fails was reported using my compiler's error reporting code, so I replaced it with an fprintf(stderr, ...) call to report the error, and an exit(1) call to stop the execution of the program.
I'm aware that using an existing library would most likely be better, but as I'm writing the compiler for learning purposes, I want to implement all the data structures I use as an exercise.
Interface:
#ifndef ARENA_H
#define ARENA_H
#include <stddef.h> // size_t
// The default block size is 10K
#define ARENA_DEFAULT_BLOCK_SIZE 10 * 1024
typedef struct block Block;
typedef struct arena {
Block *blocks;
} Arena;
void arenaInit(Arena *a);
void arenaFree(Arena *a);
void *arenaAlloc(Arena *a, size_t size);
void *arenaCalloc(Arena *a, size_t nmemb, size_t size);
#endif // ARENA_H
Implementation:
#include <stdlib.h> // malloc(), free()
#include <string.h> // memset()
#include "Arena.h"
typedef struct block {
struct block *prev;
size_t size, used;
char data[];
} Block;
union align {
int i;
long l;
long *lp;
void *p;
void (*fp)(void);
float f;
double d;
long double ld;
};
union header {
Arena arena;
union align a;
};
static inline Block *new_block(size_t size, Block *prev) {
Block *b = malloc(sizeof(union header) + size);
// In my compiler, the following check uses the internal error
// reporting system. I replaced it with fprintf() and exit() calls.
if(b == NULL) {
fprintf(stderr, "Error: Arena: new_block(): failed to allocate %zu bytes.\n", size);
exit(1);
}
b->size = size;
b->used = 0;
b->prev = prev;
return b;
}
static inline void free_blocks(Block *b) {
while(b) {
Block *prev = b->prev;
free(b);
b = prev;
}
}
void arenaInit(Arena *a) {
a->blocks = new_block(ARENA_DEFAULT_BLOCK_SIZE, NULL);
}
void arenaFree(Arena *a) {
free_blocks(a->blocks);
a->blocks = NULL;
}
void *arenaAlloc(Arena *a, size_t size) {
size = (size + sizeof(union align) - 1) / sizeof(union align) * sizeof(union align);
if(a->blocks->used + size > a->blocks->size) {
// All blocks have at least 10K of memory space.
a->blocks = new_block(size + ARENA_DEFAULT_BLOCK_SIZE, a->blocks);
}
a->blocks->used += size;
return (void *)(a->blocks->data + a->blocks->used - size);
}
void *arenaCalloc(Arena *a, size_t nmemb, size_t size) {
void *p = arenaAlloc(a, nmemb * size);
memset(p, 0, nmemb * size);
return p;
}
