</>EmbeddedInterview

How would you implement a simple malloc() and free()?

HardPointers & Memory

Short answer: Manage a fixed memory region as a list of blocks, each starting with a small header (size and a free flag, or a link to the next free block). malloc searches the free list for a block that is big enough (first fit or best fit), splits off the remainder if it is large, marks the block used and returns the address just after the header. free marks the block free and coalesces it with adjacent free neighbours to fight fragmentation.

#include <stddef.h>
#include <stdint.h>

#define HEAP_SIZE 4096u
#define ALIGN8(x) (((x) + 7u) & ~(size_t)7u)

typedef struct hdr {
    size_t size;              /* payload size in bytes */
    struct hdr *next;         /* next block in address order */
    int free;
} hdr_t;

static _Alignas(8) uint8_t heap[HEAP_SIZE];
static hdr_t *head;

static void heap_init(void)
{
    head = (hdr_t *)heap;
    head->size = HEAP_SIZE - sizeof(hdr_t);
    head->next = NULL;
    head->free = 1;
}

void *my_malloc(size_t n)
{
    if (head == NULL) heap_init();
    if (n == 0) return NULL;
    n = ALIGN8(n);
    for (hdr_t *b = head; b; b = b->next) {
        if (b->free && b->size >= n) {
            if (b->size >= n + sizeof(hdr_t) + 8) {           /* split */
                hdr_t *rest = (hdr_t *)((uint8_t *)(b + 1) + n);
                rest->size = b->size - n - sizeof(hdr_t);
                rest->next = b->next;
                rest->free = 1;
                b->size = n;
                b->next = rest;
            }
            b->free = 0;
            return b + 1;                                      /* memory after the header */
        }
    }
    return NULL;                                               /* out of memory */
}

void my_free(void *p)
{
    if (p == NULL) return;
    hdr_t *b = (hdr_t *)p - 1;
    b->free = 1;
    for (hdr_t *c = head; c; c = c->next) {                   /* coalesce neighbours */
        while (c->free && c->next && c->next->free) {
            c->size += sizeof(hdr_t) + c->next->size;
            c->next = c->next->next;
        }
    }
}

Design points to discuss

  • Alignment: every returned pointer must be suitably aligned for any type (8 bytes on Cortex-M with double/uint64_t; 16 on ARM64/x86-64). The header size must keep payloads aligned (it is 12 bytes on 32-bit here, so add padding or use _Alignas on the header in a real allocator).
  • Placement policy: first fit (fast, fragments the start of the heap), best fit (less wasted space, slower search), next fit, or segregated free lists by size class (what real allocators do).
  • Coalescing: this version scans the whole list; real allocators use boundary tags (a footer with the size) or doubly linked lists to merge in O(1).
  • Thread safety: a lock around both functions (newlib's __malloc_lock, FreeRTOS suspends the scheduler).
  • Safety checks: detect double free and invalid pointers, add canaries to catch overruns.
  • Determinism: for real-time code, use TLSF or pools instead, because search time here grows with the number of blocks.

Where real implementations come from: newlib/newlib-nano malloc (dlmalloc-based), FreeRTOS heap_2/4/5, Zephyr sys_heap, TLSF, and the Linux kernel's buddy allocator plus slab caches.