What is a memory pool, and how do you implement a fixed-size block allocator?
Short answer: A memory pool pre-allocates a block of memory divided into equal-sized chunks and keeps the free chunks in a linked list (the "free list"), with the link stored inside each free chunk. Allocation takes the first chunk from the list and freeing pushes it back, both in O(1) with no fragmentation, which makes pools ideal for real-time and embedded systems.
#include <stddef.h>
#include <stdint.h>
#define BLOCK_SIZE 32u
#define BLOCK_COUNT 16u
typedef union block {
union block *next; /* used while the block is free */
uint8_t data[BLOCK_SIZE]; /* used while it is allocated */
} block_t;
static block_t pool[BLOCK_COUNT];
static block_t *free_list;
void pool_init(void)
{
for (size_t i = 0; i < BLOCK_COUNT - 1; i++)
pool[i].next = &pool[i + 1];
pool[BLOCK_COUNT - 1].next = NULL;
free_list = &pool[0];
}
void *pool_alloc(void)
{
block_t *b = free_list; /* in an RTOS/ISR context: protect with a critical section */
if (b) free_list = b->next;
return b; /* NULL when the pool is exhausted */
}
void pool_free(void *p)
{
if (p == NULL) return;
block_t *b = p;
b->next = free_list;
free_list = b;
}
Why a union: a free block does not need its data, so its first bytes can hold the next pointer, costing no extra memory. The union also makes every block aligned for a pointer.
Properties
| Memory pool | General malloc |
|
|---|---|---|
| Time | O(1), constant | varies with heap state |
| External fragmentation | none | possible |
| Internal fragmentation | yes, if objects are smaller than the block | small (headers, alignment) |
| Sizes | one per pool (use several pools for several sizes) | any |
Production details
- Thread/ISR safety: wrap alloc/free in a critical section, or use a lock-free stack (watch out for the ABA problem).
- Debug checks: fill freed blocks with a pattern, check that a freed pointer is inside the pool and on a block boundary, detect double free with a bitmap.
- Statistics: track the minimum number of free blocks ever (high-water mark) to size the pool.
- Alignment: if blocks hold types with stricter alignment (e.g.
double, DMA buffers needing 32-byte alignment), align the pool array and round the block size up.
Where you see pools: RTOS memory pools (Zephyr k_mem_slab, ThreadX block pools, CMSIS-RTOS osMemoryPool), network stacks (lwIP pbuf pools, Linux's kmem_cache slab allocator), and USB/CAN message buffers.