</>EmbeddedInterview

Implement a slab-like allocator for fixed-size objects.

Hard"Coding: Memory & String Functions"
#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.