# How malloc Works: Arenas, Bins, and Fragmentation

> malloc looks like one function, but underneath it's a memory allocator juggling free lists, size classes, and the kernel. Knowing how it works explains fragmentation, allocator contention, and why your RSS never goes down.

URL: https://harshith.in/blog/how-malloc-works/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: memory, systems, performance

You call `malloc(32)` and get a pointer. That simplicity hides an allocator
making a series of decisions: where the memory comes from, how free space is
tracked, how it avoids locking on every call, and whether freeing it gives
anything back to the operating system. Usually it doesn't, and that surprises
people.

## The Allocator Sits Between You and the Kernel

The kernel deals in pages (4 KB) via `brk` (grow the heap) and `mmap` (map a
fresh region). Asking it for every small object would be absurdly slow. So
`malloc` grabs memory in big chunks and hands out small pieces itself:

```text
   your code  ──malloc(32)──▶  allocator  ──brk/mmap──▶  kernel
                               (manages chunks, free lists)
```

The allocator's whole job is to satisfy small requests from big slabs and reuse
freed space without a syscall.

## Bins: Free Lists by Size

When you `free()` a chunk, it isn't returned to the OS — it goes onto a **free
list** so the next `malloc` of a similar size can reuse it instantly. glibc
groups these by size class into **bins**:

```text
   fastbins:  [16][16]        small, recently freed, LIFO, no coalescing
   smallbins: [32][48][64]    exact size classes
   largebins: sorted ranges   for big allocations
```

A `malloc(32)` checks the matching bin first. Hit → O(1), no kernel involvement.
This caching is why allocation is fast on average, and why a freed pointer used
again (use-after-free) often still "works" — the memory's still there, just
re-handed-out.

## Fragmentation: The Space You Can't Use

Free memory that's the wrong shape is useless. **External fragmentation** is
scattered free chunks too small to satisfy a larger request even though the total
is plenty:

```text
   [used][free 16][used][free 16][used]   ← 32 bytes free total,
                                            but no contiguous 32-byte slot
```

Allocators fight this by **coalescing** adjacent free chunks back together and by
carving from size classes that minimize waste, but it can't be eliminated.

## Why RSS Doesn't Drop After free()

Memory freed back to the allocator generally stays in the process. Returning it
to the OS requires the *top* of the heap to be free (to shrink `brk`), or the
chunk to have come from `mmap`. A free list full of holes in the middle can't be
returned. So your resident set stays high even after freeing — it's reserved for
reuse, not leaked.

## Arenas: Why Threads Don't Serialize

If every thread shared one heap, every `malloc` would contend on one lock. glibc
gives each thread its own **arena** (a separate heap with its own bins and lock),
so concurrent allocations mostly don't collide:

```text
   thread 1 ─▶ arena A (lock A)
   thread 2 ─▶ arena B (lock B)     parallel, no contention
```

This is why allocator-heavy multithreaded code can still scale — and why
replacing the allocator (jemalloc, tcmalloc, mimalloc) is a common performance
win when the default's arena strategy doesn't fit your workload.

## Takeaways

- `malloc` buys memory from the kernel in big chunks and hands out small pieces
  from its own free lists.
- Freed chunks go into size-classed bins for fast reuse — they're not returned to
  the OS, which is why RSS stays high after `free()`.
- External fragmentation wastes space the wrong shape; coalescing helps but can't
  fix it entirely.
- Per-thread arenas avoid lock contention; swapping allocators is a real tuning
  lever.