Memory pools or best practice in dynamic allocation in embedded systems

Before going into any presentation it is worthwhile to remember one important thing which I missed right from the beginning: only pointers (here I’m including arrays also) can be used in conjunction with dynamic memory allocation.

In C you cannot have something like this:

int n = (*int) malloc (sizeof (int));
// because malloc is returning a (void *) it has to be
// assigned as an r-value to a pointer

I read in many places that the cast to (*int) is not so safe and is better to be avoided but this is more subject of a footer note.

Malloc implementation presented in my previous post had many drawbacks. Just to name few of them:

- there is no memory overflow handling, only the presumption of a success is considered
- it cannot be used in multitasking environments because it has no locking mechanism implemented (mutex or semaphore)
- is_available flag occupies an integer even if should be only one bit
- it does not handle free space in order to avoid, or at least to limit fragmentation
- it is non-deterministic, the algorithm has to iterate through each heap location in order to find the right one

Let’s just reacap a little bit how things are passing in the standard way when allocating dynamically memory. At the beginning the operating system granted a chunk of 32 KB memory to the current process (this is the thing that brk and sbrk handled), from which I would like to use (to allocate with malloc) 2 Kbytes:

Dynamic memory allocation under the hood

I owed you some explanations regarding dynamic memory management implementation so here they are.

Before going into any specific implementation I would like to refer to Ritchie and Kernighan’s “The C programming language” bible. I had in hands the second edition published at Prentice Hall in 2008.

Chapter 8.7 provides a storage allocator example. Few important things are outlined out there:

calls to malloc and free may occur in any order
malloc requests storage from the operating system as needed
the storage used by a program can be requested by malloc, but also by other sources, so its memory blocks are basically of three types: not owned by malloc, owned by malloc which are free and which are in use, only last two categories make the subject of our discussion (let’s name those two as free and in use)
every free block is split into three fields as shown in the picture below: a pointer to the next free block, the size (usually in bytes) of the current free block and the actual stored data

What happens when mallocfunction is called?