Implement a slab-like allocator for fixed-size objects.
#include <stddef.h>
#include <stdint.h>
typedef struct slab_cache {
size_t obj_size; /* rounded up to hold a pointer and keep alignment */
void *free_list; /* singly linked through the free objects */
size_t in_use, total;
} slab_cache_t;
void slab_init(slab_cache_t *c, void *mem, size_t mem_size, size_t obj_size)
{
obj_size = (obj_size < sizeof(void *)) ? sizeof(void *) : obj_size;
obj_size = (obj_size + 7u) & ~(size_t)7u; /* 8-byte alignment */
c->obj_size = obj_size;
c->free_list = NULL;
c->in_use = 0;
c->total = mem_size / obj_size;
uint8_t *p = mem;
for (size_t i = 0; i < c->total; i++) { /* thread objects onto the list */
*(void **)(p + i * obj_size) = c->free_list;
c->free_list = p + i * obj_size;
}
}
void *slab_alloc(slab_cache_t *c)
{
void *o = c->free_list;
if (o) { c->free_list = *(void **)o; c->in_use++; }
return o;
}
void slab_free(slab_cache_t *c, void *o)
{
*(void **)o = c->free_list;
c->free_list = o;
c->in_use--;
}
Points: one cache per object type (struct packet, struct timer), O(1) allocate/free, no fragmentation, objects packed tightly. The Linux kernel's slab/SLUB allocator (kmem_cache_create, kmem_cache_alloc) works on this idea, with per-CPU caches to avoid locking and constructors to pre-initialise objects. Add a lock or per-core caches for concurrency.