Fixed-size block pool allocator with freelist

Challenge

Fixed-size block pool allocators partition a contiguous memory buffer into identical chunks. Free chunks store a pointer to the next free chunk directly inside themselves, providing $O(1)$ allocation and deallocation without heap fragmentation.

Your Task

Implement:

struct pool_block {
    struct pool_block *next;
};

struct pool {
    void *buffer;
    size_t buf_size;
    size_t block_size;
    struct pool_block *free_head;
};

void pool_init(struct pool *p, void *buffer, size_t buf_size, size_t block_size);
void *pool_alloc(struct pool *p);
void pool_free(struct pool *p, void *ptr);

Rules

1. In pool_init:
   • If p == NULL, buffer == NULL, or block_size < sizeof(struct pool_block), do nothing.
   • Slices buffer into buf_size / block_size consecutive blocks.
   • Links each block's next pointer to the subsequent block. The last block's next is NULL.
   • Sets p->free_head to point to the first block.
2. In pool_alloc:
   • If p == NULL or p->free_head == NULL (pool exhausted), return NULL.
   • Pop and return the block at p->free_head, advancing free_head to free_head->next.
3. In pool_free:
   • If p == NULL or ptr == NULL, do nothing.
   • Push ptr back onto the front of p->free_head as the new head.

Input format

p: pool struct pointer; buffer: memory slab; buf_size: slab byte size; block_size: size per chunk.

Output format

pool_alloc returns allocated block pointer or NULL. pool_free returns void.

Constraints

Freestanding C11. No malloc/free. Embed freelist inside chunks.

Starter code

#include <stddef.h>

/* The harness provides:
struct pool_block {
    struct pool_block *next;
};
struct pool {
    void *buffer;
    size_t buf_size;
    size_t block_size;
    struct pool_block *free_head;
};
*/

void pool_init(struct pool *p, void *buffer, size_t buf_size, size_t block_size) {
    (void)p; (void)buffer; (void)buf_size; (void)block_size;
}

void *pool_alloc(struct pool *p) {
    (void)p;
    return NULL;
}

void pool_free(struct pool *p, void *ptr) {
    (void)p; (void)ptr;
}

Common mistakes

Calculating next block address without casting to char* or uint8_t*; forgetting that block_size must be >= sizeof(struct pool_block).

Edge cases to handle

buf_size < block_size results in empty pool; pool exhaustion returns NULL; freeing and re-allocating reuses blocks.

Background lessons

• malloc and the heap
• free and ownership