Fixed-Block Memory Pool Allocator

1. Why Not malloc in Real-Time Systems?

While malloc is incredibly flexible, its very flexibility is its weakness in a real-time context. An interviewer might ask you to justify the need for a custom allocator. Here's the core argument:

• Non-Deterministic Execution Time: The time it takes for malloc to return can vary significantly. It might find a suitable block immediately in the thread-local cache (tcache), or it might have to search long lists of free blocks, coalesce them, and even request more memory from the OS. This unpredictability is unacceptable in a system where deadlines must be met.
• External Fragmentation: As we discussed, over time the heap can become a patchwork of small, free blocks that are unusable for larger allocation requests, even if the total free memory is sufficient. This can lead to allocation failures at critical moments.

A memory pool allocator solves these problems by trading flexibility for predictability.

2. The Memory Pool Concept

A fixed-block memory pool is fundamentally simple:

1. A large, contiguous block of memory is allocated once, typically at system startup.
2. This block is divided into a fixed number of smaller, equal-sized chunks.
3. The allocator's job is simply to hand out these chunks on request and collect them back when they are freed.

This design provides two crucial guarantees for real-time systems.

As the video highlights, the key advantages are:

• Minimal Bookkeeping Overhead: The metadata required for each chunk can be extremely small.
• Elimination of External Fragmentation: Because all chunks are the same size, any free chunk can satisfy any allocation request. The problem of having unusable gaps between allocations disappears.

The most important benefit, however, is O(1) performance for allocation and deallocation, which we will achieve using a familiar data structure: the free list.

3. Designing a Fast Pool Allocator with a Free List

In the last lesson, we saw how malloc uses an explicit free list to speed up its search for free blocks. For our memory pool, the free list is even simpler and more powerful. Since every chunk is the same size, we don't need to search for a "best fit"; any free chunk will do. This means we can always just take the first one on our list.

The core idea is to repurpose the memory of a free chunk to hold a pointer to the next free chunk. This creates a linked list of free blocks without requiring any extra memory for pointers.

4. Implementation Deep Dive

Now, let's translate this design into a practical C implementation. We will build a complete, self-contained fixed-block allocator.

Building on the concepts from that article, here is a complete, commented implementation you can study and experiment with. This is exactly the kind of code you might be asked to write or analyze in an interview.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>

// --- Configuration ---



#define CHUNK_SIZE   64  // Size of the data payload for each chunk
#define POOL_SIZE    10  // Number of chunks in the pool

// --- Data Structures ---

/**
 * @brief A memory chunk. Can be part of the free list or hold user data.
 *
 * Using a union is a memory-efficient technique. When the chunk is free,
 * we use the 'next' pointer to link it into the free list. When it's
 * allocated, the user uses the 'data' array. They occupy the same memory.
 */
typedef union Chunk {
    // Points to the next free chunk when this chunk is in the free list
    union Chunk* next;
    // User data area. The size includes space for the 'next' pointer
    // to ensure alignment and that our CHUNK_SIZE is the minimum size.
    char data[CHUNK_SIZE];
} Chunk;

/**
 * @brief The memory pool controller structure.
 */
typedef struct Pool {
    // Pointer to the first chunk in the free list
    Chunk* free_list_head;
    // Pointer to the start of the entire allocated pool memory
    // Needed so we can free the whole pool later.
    Chunk* pool_start;
} Pool;

// --- API Functions ---

/**
 * @brief Creates and initializes a memory pool.
 *
 * @return A pointer to the initialized Pool structure, or NULL on failure.
 */
Pool* pool_create() {
    // 1. Allocate the main controller structure
    Pool* pool = (Pool*)malloc(sizeof(Pool));
    if (!pool) {
        return NULL;
    }

    // 2. Allocate the large, contiguous memory block for all chunks
    pool->pool_start = (Chunk*)malloc(sizeof(Chunk) * POOL_SIZE);
    if (!pool->pool_start) {
        free(pool);
        return NULL;
    }

    // 3. Initialize the free list by linking all chunks together
    pool->free_list_head = pool->pool_start;
    Chunk* current_chunk = pool->free_list_head;
    for (int i = 0; i < POOL_SIZE - 1; ++i) {
        current_chunk->next = current_chunk + 1; // Point to the next adjacent chunk
        current_chunk = current_chunk->next;
    }
    // The last chunk's 'next' pointer is NULL to mark the end of the list
    current_chunk->next = NULL;

    printf("Pool created with %d chunks of %zu bytes each.\n", POOL_SIZE, sizeof(Chunk));
    return pool;
}

/**
 * @brief Allocates a single chunk from the pool. O(1) complexity.
 *
 * @param pool The pool to allocate from.
 * @return A pointer to the allocated chunk's data area, or NULL if pool is full.
 */
void* pool_alloc(Pool* pool) {
    if (!pool || !pool->free_list_head) {
        // Pool is full or invalid
        return NULL;
    }

    // Get the first chunk from the free list
    Chunk* allocated_chunk = pool->free_list_head;

    // Advance the free list head to the next available chunk
    pool->free_list_head = allocated_chunk->next;

    // Return a pointer to the user data area
    return allocated_chunk->data;
}

/**
 * @brief Frees a chunk, returning it to the pool. O(1) complexity.
 *
 * @param pool The pool the chunk belongs to.
 * @param ptr Pointer to the chunk's data area that was returned by pool_alloc.
 */
void pool_free(Pool* pool, void* ptr) {
    if (!pool || !ptr) {
        return;
    }

    // Cast the user pointer back to a Chunk pointer.
    // This relies on the user giving us a valid pointer from this pool.
    Chunk* freed_chunk = (Chunk*)((char*)ptr - offsetof(Chunk, data));

    // Add the freed chunk to the front of the free list
    freed_chunk->next = pool->free_list_head;
    pool->free_list_head = freed_chunk;
}

/**
 * @brief Destroys the memory pool, freeing all associated memory.
 *
 * @param pool The pool to destroy.
 */
void pool_destroy(Pool* pool) {
    if (!pool) {
        return;
    }
    free(pool->pool_start); // Free the large chunk block
    free(pool);             // Free the controller struct
    printf("Pool destroyed.\n");
}


// --- Example Usage ---
int main() {
    Pool* my_pool = pool_create();
    if (!my_pool) {
        fprintf(stderr, "Failed to create pool.\n");
        return 1;
    }

    // Allocate all available chunks
    void* allocations[POOL_SIZE];
    printf("\n--- Allocating all %d chunks ---\n", POOL_SIZE);
    for (int i = 0; i < POOL_SIZE; ++i) {
        allocations[i] = pool_alloc(my_pool);
        if (allocations[i]) {
            printf("Allocated chunk %d at address %p\n", i, allocations[i]);
            // You can now use this memory, e.g., sprintf((char*)allocations[i], "Chunk %d", i);
        } else {
            printf("Allocation %d failed. Pool is full.\n", i);
        }
    }
    
    // Try to allocate one more - should fail
    printf("\n--- Trying to allocate one more chunk ---\n");
    void* extra_alloc = pool_alloc(my_pool);
    if (!extra_alloc) {
        printf("Correctly failed to allocate from a full pool.\n");
    }

    // Free half of the chunks in a non-sequential order
    printf("\n--- Freeing half of the chunks ---\n");
    pool_free(my_pool, allocations[5]); printf("Freed chunk 5\n");
    pool_free(my_pool, allocations[2]); printf("Freed chunk 2\n");
    pool_free(my_pool, allocations[8]); printf("Freed chunk 8\n");

    // Allocate again - should succeed and reuse the freed chunks
    printf("\n--- Allocating again to reuse freed chunks ---\n");
    void* re_alloc1 = pool_alloc(my_pool);
    printf("Re-allocated chunk at %p (should match a recently freed one)\n", re_alloc1);
    void* re_alloc2 = pool_alloc(my_pool);
    printf("Re-allocated chunk at %p\n", re_alloc2);

    pool_destroy(my_pool);

    return 0;
}

Conclusion

You have now designed and implemented a fixed-block memory pool allocator, a cornerstone of deterministic memory management in embedded and real-time systems. This demonstrates a deep understanding of memory layout, pointer manipulation, and performance trade-offs that interviewers at top semiconductor companies look for.

Key Takeaways:

• Memory pools provide deterministic O(1) allocation and free operations, which is critical for real-time performance guarantees.
• They eliminate external fragmentation by using fixed-size chunks. The trade-off is potential internal fragmentation if requests are smaller than the chunk size.
• A singly-linked free list is the most efficient way to manage free chunks. The memory of the free chunks themselves is repurposed to build the list, resulting in zero memory overhead for the list structure.
• Using a union is an elegant and efficient C idiom for implementing the dual-purpose nature of a memory chunk (metadata pointer vs. user data).

In our next lesson, we will shift our focus to memory safety. Now that you know how to build custom allocators, we will look at the common pitfalls associated with them and with manual memory management in general. We will learn to identify and fix dangling pointer, wild pointer, double-free, and memory leak bugs in C code samples.