Custom malloc in C: split, fusion, and heap extension

I wrote a small allocator in C to understand how malloc works under the hood.

My implementation keeps a doubly linked list of heap blocks and uses sbrk/brk for heap growth and release.

Block layout

Each block stores metadata plus payload pointer.

typedef struct s_block *t_block;
struct s_block {
  size_t size;
  t_block next;
  t_block prev;
  int free;
  void *ptr;   // ptr = b->data
  char data[1];
};
#define BLOCK_SIZE (sizeof(struct s_block) - sizeof(char))

I also align allocation sizes to 4 bytes:

#define align4(x) (((((x) - 1) >> 2) << 2) + 4)

Allocation path

1. Align requested size.
2. Search free list (find_block) for first fit.
3. Split block if large enough (split_block).
4. If no fit, extend heap (extend_heap) using sbrk.

void *malloc(size_t size) {
  t_block b, last;
  size_t s = align4(size);

  if (base) {
    last = base;
    b = find_block(&last, s);
    if (b) {
      if ((b->size - s) >= (BLOCK_SIZE + 4)) {
        split_block(b, s);
        b->free = 0;
      }
    } else {
      b = extend_heap(last, s);
      if (!b) return NULL;
    }
  } else {
    b = extend_heap(NULL, s);
    if (!b) return NULL;
    base = b;
  }
  return b->data;
}

Free path and coalescing

On free(p):

• Validate pointer (valid_addr)
• Mark block as free
• Merge with adjacent free blocks (fusion)
• If tail block is free, shrink heap with brk

void free(void *p) {
  t_block b;
  if (valid_addr(p)) {
    b = get_block(p);
    b->free = 1;
    if (b->prev && b->prev->free) b = fusion(b->prev);
    if (b->next) fusion(b);
    else {
      if (b->prev) b->prev->next = NULL;
      else base = NULL;
      brk(b);
    }
  }
}

Takeaway

This allocator is intentionally small, but it gave me hands-on understanding of fragmentation, metadata design, pointer safety checks, and why allocator edge-cases get tricky fast.