Statically allocated memory pool in C for embedded systems

Question

I made a statically allocated memory pool for embedded systems. I think it needs a little work but it works fine so far.

How it works: An array of size MEMORY_POOL_SIZE is first reserved in memory and that's actually the space and the whole program uses to get memory from.
The number of allocations that can happen at the same time are limited and defined from MEMORY_POOLS_NUM. The current implementation below uses 16384 bytes of memory space and 64 concurrent memory allocations. The numbers don't have to be power of 2.

When the program wants to allocate some memory, it access the memory allocator which passes a pointer back to the program.

It is thread safe, which means the program is not interrupted during the allocation or de-allocation of the memory pool.

When the size an allocated space needs to change (realloc) everything in memory has to move. When the pointers of the mem_allocator point to a different address, the program will break and for this reason the pointers that are passed back to the program point to the address of the start_p.

-- mem_pool.h --

#ifndef MEM_POOL_H
#define MEM_POOL_H

#include <inttypes.h>

/**
 * \brief      Allocates a chunk from the memory pool
 * \param buf  Must be a double NULL pointer.
 * \param size Must be greater than zero.
*/
void mem_pool_alloc(uint8_t ** buf, uint16_t size);

/**
 * \brief      Re-allocates a chunk from the memory pool.
 *             The new chunk is always bigger.
 * \param buf  Must be a double NULL pointer.
 * \param size Must be greater than zero.
*/
void mem_pool_realloc(uint8_t ** buf, uint16_t new_size);

/**
 * \brief     Release a chunk from the memory pool.
 * \param buf Must be a double pointer.
*/
void mem_pool_free(uint8_t ** buf);


#endif

-- mem_pool.c --

#include "mem_pool.h"
#include <stddef.h>
#include <stdbool.h>


#define MEMORY_POOL_SIZE    (16384) /** The size in bytes of the statically allocated memory */
#define MEMORY_POOLS_NUM    (64)    /** The number of elements of the memory allocator */

typedef struct
{
    bool     locked;  /** Shows whether the element of the memory allocator is reserved or not */
    uint8_t* start_p; /** The pointer to the first element in the statically allocated memory */
    uint16_t size;    /** The total size of the chunk that is allocated from the memory */

}MemPoolAllocator;

/**
 * The statically allocated array in memory.
*/
static volatile uint8_t memory_pool[MEMORY_POOL_SIZE];

/**
 * Memory allocator struct. It is used to allocate memory in the pool.
*/
static volatile MemPoolAllocator mem_allocator[MEMORY_POOLS_NUM];



void mem_pool_alloc(uint8_t ** buf, uint16_t size)
{
    ASSERT(buf != NULL);
    ASSERT(*buf == NULL);
    ASSERT(size > 0);

    __disable_irq();

    for (uint8_t i = 0; i < MEMORY_POOLS_NUM; i++) {
        if (mem_allocator[i].locked == false) {
            mem_allocator[i].locked = true;
            // Find the first unlocked element.
            if (i > 0) {
                mem_allocator[i].start_p = mem_allocator[i - 1].start_p + mem_allocator[i - 1].size;
            }
            else {
                // If the element is the first one the pointer of the chunk points to the first byte of
                // the statically allocated memory.
                mem_allocator[i].start_p = memory_pool;
            }
            mem_allocator[i].size = size;
            // The double pointer points to the address of the pointer.
            // This allows the pointers that the program use to be updated in case
            // a re-allocation is needed.
            *buf = &mem_allocator[i].start_p;

            __enable_irq();
            return;
        }
    }

    *buf = NULL;
    __enable_irq();
}

void mem_pool_realloc(uint8_t ** buf, uint16_t new_size)
{
    ASSERT(buf != NULL);
    ASSERT(new_size > 0);

    __disable_irq();

    if (*buf == NULL) {
        mem_pool_alloc(buf, new_size);
    }
    else {
        for (uint8_t id = 0; id < MEMORY_POOLS_NUM; id++) {
            if (*buf == &mem_allocator[id].start_p) {
                // The current element must be locked.
                ASSERT(mem_allocator[id].locked == true);
                // Starting from the end, all elements of the memory pool and
                // the memory allocator must move as many as the new_size variable.
                for (uint8_t x = MEMORY_POOLS_NUM - 1; x > id; x--) {
                    if (mem_allocator[x].locked == true) {

                        uint16_t temp_size = mem_allocator[x].size;
                        uint16_t offset_size = new_size - mem_allocator[x].size;

                        for (uint16_t a = mem_allocator[x].size; a > 0; a--) {
                            *(mem_allocator[x].start_p + a + offset_size - 1) = *(mem_allocator[x].start_p + a - 1);
                            *(mem_allocator[x].start_p + a - 1) = 0; // Initialize the new space to 0.
                        }
                        mem_allocator[x].start_p += offset_size;
                        mem_allocator[x].size = new_size;
                    }
                }

                break;
            }
        }
    }

    __enable_irq();
}

void mem_pool_free(uint8_t ** buf)
{
    if ((*buf == NULL) || (buf == NULL)) {
        return;
    }

    __disable_irq();

    uint8_t id = 0;
    for (id = 0; id < MEMORY_POOLS_NUM; id++) {
        if (*buf == &mem_allocator[id].start_p) {
            ASSERT(mem_allocator[id].locked == true);

            mem_allocator[id].locked = false;
            *buf = NULL;

            for (uint16_t i = 0; i < mem_allocator[id].size; i++) {
                mem_allocator[id].start_p[i] = 0;
            }
            mem_allocator[id].start_p = NULL;
            mem_allocator[id].size = 0;

            break;
        }
    }

    __enable_irq();
}

Answer 1

Consider using void pointers

Prefer using void pointers in your memory pool API, as this allows the caller to pass in any type of pointer without having to explicitly cast them. So for example:

void mem_pool_alloc(void **buf, uint16_t size);

Naming things

There are several ways the names of constants, variables and functions can be improved. First: avoid repeating mem and memory in private variables and functions inside mem_pool.c. It is already clear from the context that everything has to do with memory pools. So for example:

#define POOL_SIZE (16384)
...
static uint8_t pool[POOL_SIZE];

Futhermore, MemPoolAllocator is a misnomer, this struct just represents a single allocation from the memory pool. Also, there is only one pool, so NUM_POOLS is wrong as well. I would instead write:

#define NUM_ALLOCATIONS (64)

typedef struct {
    ...
} Allocation;

static Allocation allocations[NUM_ALLOCATIONS];

Avoid unnecessary use of volatile

You should not make things volatile unnecessarily. The volatile keyword doesn't make access atomic, and while it prevents the compiler from reordering access to volatile variables with respect to other volatile variables, it doesn't prevent the CPU itself from reordering access.

I would check if __disable_irq() and __enable_irq() themselves act as memory barriers. If so, that will be enough to guarantee that everything stays consistent. Then the compiler is free to reorder access to the variables between those two statements as it sees fit, resulting in better optimized code.

Unnecessary member variable locked

I see that you do not allow allocations of zero length. This means you can use the member variable size to check whether an allocation is in use or not, and you don't need locked anymore:

void *mem_pool_alloc(uint16_t size)
{
    ...
    for (uint8_t i = 0; i < NUM_ALLOCATIONS; i++) {
        if (allocations[i].size == 0) {
            // This allocation is free
            ...

Check if there is enough space in the pool

Your allocator does not properly check if there is enough space for an allocation. First, it allows allocations larger than the size of the whole pool. But second, even if there is enough free space in the pool as a whole, it doesn't check whether there is enough space at the location it has chosen. Consider this order of events:

void *p1, *p2, *p3;
mem_pool_alloc(&p1, 10);
mem_pool_alloc(&p2, 10);
mem_pool_alloc(&p3, 10);
mem_pool_free(&p2);
mem_pool_alloc(&p2, 20); // will overwrite p3

What you should do is find a free spot that is large enough to hold the new allocation. And due to fragmentation there might not be, unless you move allocations here as well.

Your reallocation algorithm doesn't move anything before the allocation that is resized

When moving existing allocations to make space for the new size of an allocation during mem_pool_realloc(), you only consider moving allocations after the one being resized. But what if it's already the last one? You should handle moving allocations both before and after: move allocations before towards the start of the pool, and allocations after towards the end of the pool, to make enough space in the middle of the pool.

Answer 2

Design:

• Consider making an API that enforces the caller to allocate aligned chunks. This will make the code much more robust on 32 bit systems. You can still let them state the desired size in bytes, but do the actual allocation on aligned chunks (32 bits etc). It's strange that your code does not address alignment at all(?) as far as I can see.

• Avoid asserts inside library code. They don't add much but slow everything down. Besides that, the proper way to deal with "dumb" errors such as null pointers or other nonsense parameters is to enforce the error checking on the caller through documentation. It's not the job of your function to chase down application layer bugs in the calling application.

  If you need actual error handling rather than "halt and catch fire like a PC", then return an enum error code from the functions and let the caller deal with the errors.

• Hitting the global interrupt mask is questionable practice in general. This must be documented too. Besides, your library has no use case that requires the library itself to prevent race conditions with interrupts. So in the normal use-case, all this achieves is to screw up the real-time performance of any program using your library, for no reason what so ever. Not sexy at all. In this case "thread safety" is not a feature, but a burden. The user could as well have shut down the relevant interrupts in the caller code.

• volatile achieves nothing in this case, unless you somehow expect the user to DMA data straight into the memory pool. In which case you should design a special version of the memory pool for that specific purpose.

Style:

• Place all library includes in the header. This documents to the user who reads your header which library dependencies it got.
• I'd use stdint.h over inttypes.h because the former is mandatory for all C systems, including embedded ("freestanding") systems. inttypes.h is not necessarily supported by embedded compilers and apart from including stdint.h, it only contains misc printf formatting goo that you don't need anyway.
• Parenthesis around integer constants in macros (16384) is superfluous and only adds clutter. You only need to use parenthesis when dealing with function-like macros.