Linked lists and memory pools

A linked list is a structure in which each node holds the address of the next. Inserting and removing in the middle is easy, so it is used for timer lists and lists of pending work.

Why malloc is avoided

• Repeated allocation and freeing splits the free space into pieces, causing fragmentation: the total free space is enough but no large block can be had.
• The time an allocation takes is not constant.
• There is almost nothing you can do when it fails.

So many embedded coding rules forbid dynamic allocation after initialisation.

Memory pool

Blocks of the same size are reserved in advance as an array, and the free blocks are threaded together as a linked list (the free list).

typedef struct node { struct node *next; uint8_t data[32]; } node_t;
static node_t pool[16];
static node_t *free_list;

void pool_init(void) {
    for (int i = 0; i < 15; i++) pool[i].next = &pool[i + 1];
    pool[15].next = NULL; free_list = pool;
}
node_t *pool_alloc(void) { node_t *n = free_list; if (n) free_list = n->next; return n; }
void pool_free(node_t *n) { n->next = free_list; free_list = n; }

Allocation and freeing are always O(1) and there is no fragmentation. You only have to decide what happens when all the blocks are in use.