</>EmbeddedInterview
← All problems · Data Structures

Fixed-Block Memory Pool

Medium

Many firmware projects forbid malloc. Implement a pool of POOL_BLOCKS blocks of BLOCK_SIZE bytes from a static array:

  • pool_init() prepares the pool.
  • pool_alloc() returns a free block in O(1), or NULL if none remain.
  • pool_free(p) returns a block in O(1).

Use no memory beyond the static array itself (no separate bitmap).

Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.

A free block is not in use, so you can store a "next free block" pointer inside it. Chain all free blocks into a singly linked free list.

#include <stdio.h>
#include <stddef.h>
#include <stdint.h>

#define BLOCK_SIZE  32u
#define POOL_BLOCKS 4u

typedef union block {
    union block *next;                 /* valid while free */
    unsigned char data[BLOCK_SIZE];    /* valid while allocated */
} block_t;

static block_t  pool[POOL_BLOCKS];
static block_t *free_list;

void pool_init(void)
{
    for (unsigned i = 0; i < POOL_BLOCKS - 1u; i++)
        pool[i].next = &pool[i + 1];
    pool[POOL_BLOCKS - 1u].next = NULL;
    free_list = &pool[0];
}

void *pool_alloc(void)
{
    block_t *b = free_list;
    if (b) free_list = b->next;
    return b;
}

void pool_free(void *p)
{
    if (!p) return;
    block_t *b = p;
    b->next = free_list;
    free_list = b;
}

The union guarantees each block is large enough and aligned for a pointer. Allocation pops the head of the free list and freeing pushes onto it, both O(1) and deterministic, with no fragmentation because every block is the same size. This is the idea behind RTOS memory pools (ThreadX block pools, Zephyr k_mem_slab).

For use from both tasks and ISRs, wrap alloc and free in a critical section. Debug builds often add a magic value or a range check in pool_free to catch double frees and foreign pointers.

solution.c
OutputPress Run to compile and test your code.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
    pool_init();
    void *b[POOL_BLOCKS];
    for (unsigned i = 0; i < POOL_BLOCKS; i++) { b[i] = pool_alloc(); CHECK(b[i] != NULL); }
    CHECK(pool_alloc() == NULL);
    for (unsigned i = 0; i < POOL_BLOCKS; i++)
        for (unsigned j = i + 1; j < POOL_BLOCKS; j++) CHECK(b[i] != b[j]);
    CHECK(((uintptr_t)b[0] % sizeof(void *)) == 0);
    pool_free(b[2]);
    CHECK(pool_alloc() == b[2]);
    pool_free(b[0]); pool_free(b[1]);
    CHECK(pool_alloc() != NULL && pool_alloc() != NULL && pool_alloc() == NULL);
    puts(fails ? "Some tests failed" : "All tests passed");
    return fails != 0;
}