Slab / Pool Allocator (C)
Topics: allocators, free lists, fixed-size objects
Problem
Implement a pool (slab) allocator over a fixed caller-provided buffer (no
malloc): hand out and reclaim same-sized objects in O(1).
typedef struct { /* ... */ } Pool;
void pool_init(Pool *p, void *storage, size_t total_size, size_t obj_size);
void *pool_alloc(Pool *p); // a free block, or NULL if exhausted
void pool_free(Pool *p, void *ptr); // return a block to the pool
size_t pool_available(const Pool *p); // free blocks remaining
The pool holds total_size / obj_size blocks. obj_size is at least
sizeof(void*).
Key concepts
- The free list lives in the free blocks. This is the elegant part: a block that
is not in use has nothing to store, so use it to store a pointer to the next free
block.
init walks the buffer and links every block into a singly linked list;
alloc pops the head; free pushes the block back on. No side table, no per-block
header, O(1) both ways.
- Why fixed size makes it fast. A general allocator (like your free-list
allocator) searches for a block that fits and splits or coalesces. A pool knows
every block is identical, so there is nothing to search or split. Allocation is a
pointer pop.
- Alignment. Because blocks are reused for
void* links and then for the
caller's objects, the backing storage must be suitably aligned (the tests align
it for you).
Pools back object caches in kernels (the Linux slab allocator), fixed-size node
pools for trees and lists, and any hot path that churns through many objects of one
type.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/pool && /tmp/pool
Sign in to submit your solution.