Implementing Memory Block Pools for Fixed-Size Allocation

In this lesson, you will learn how to design a memory pool to achieve deterministic O(1) allocation performance while completely eliminating external fragmentation.

The Problem with Dynamic Allocation

Standard memory allocators (like malloc) search a heap for a contiguous block of sufficient size. Over time, as you allocate and free different-sized chunks, the memory space becomes a "Swiss cheese" of small, scattered gaps. This is external fragmentation. Furthermore, the time to find a suitable gap varies depending on the heap state, making malloc non-deterministic—a dangerous trait for real-time systems.

The Memory Pool Solution

A memory pool side-steps these issues by partitioning a pre-allocated block of memory into a fixed number of identical, uniform-sized slots. Because every slot is the same size, we don’t care which slot we take; any free slot will always fit the request.

To manage these slots, we maintain a Free List (typically a linked list). When the system initializes, we link every block together.

typedef struct Block {
    struct Block* next;
} Block_t;

typedef struct {
    Block_t* free_list;
    void* pool_start;
} MemoryPool_t;

O(1) Operations

1. Allocation: Simply pop the head off the free_list. It takes a constant number of instructions regardless of how many blocks are currently in use.
2. Deallocation: Simply push the returned memory address back onto the head of the free_list. Again, this is a constant-time pointer operation.

Because every block is identical, there is no need to "search" or "coalesce" adjacent free blocks. You trade flexibility—you can only store objects of one specific size—for total predictability. This is ideal for fixed-size message structures used in the inter-task communication patterns we discussed in previous lessons, such as those passed through message buffers or queues. By aligning these blocks to the processor's word boundary, you also ensure efficient hardware access.

Key Takeaway: Memory pools provide deterministic, O(1) performance by replacing complex heap searching with simple linked-list pointer operations, effectively eliminating external fragmentation in real-time applications.