malloc(256) looks like one function call, but it's a decision tree with six layers, each one slower than the last — and the last layer isn't the allocator at all, it's the hardware. Here's the literal path glibc takes.
The thread-local tcache (thread cache) is checked first: a per-thread array of singly-linked free lists, one per size class. For a 256-byte request, the allocator rounds up to the 256-byte size class, checks the tcache bin, and if there's a freed chunk there, pops it. This is ~10 instructions, no lock, ~20–50 ns. The vast majority of mallocs in a typical program end here — chunks are recycled thread-locally.
Tcache miss. glibc checks the arena's fastbins (for chunks ≤ 80 bytes — not our case) and then the small bins (up to 512 bytes on 64-bit). These are doubly-linked lists with a bin lock; popping from them costs a lock acquisition plus list surgery, ~100–200 ns. If a suitable chunk exists anywhere in the arena's free lists, this is where it's found.
No bin has a chunk of the right size. The allocator cuts from the arena's top chunk — the contiguous free region at the end of the heap. It splits off 256 bytes (plus headers) and advances the top pointer. Still no syscall: this is bookkeeping inside an already-mapped region, ~100–300 ns. The top chunk is why malloc is amortized O(1) for sequential allocations — each one is just a pointer bump.
If the top chunk is exhausted, the allocator grows the heap with the brk syscall — "extend my data segment by N bytes." The kernel adjusts the process's heap boundary and returns the new end address. This costs ~500 ns–1 µs (syscall entry/exit, no I/O). The mapping is virtual-only: no physical memory is touched yet. glibc keeps a heap-consolidation threshold (~128 KB) so small growths reuse the existing region rather than calling brk every time.
Large allocations — above MMAP_THRESHOLD (~128 KB, tunable via mallopt) — skip the heap entirely: the allocator calls mmap to get an anonymous, zero-filled region, and munmap on free. Each mmap is a full page-table walk plus TLB shootdown on other cores, ~1–5 µs, which is why large allocations are deliberately not cached the way small chunks are. The free of an mmap'd region returns memory to the OS immediately; a freed heap chunk returns it only to the allocator.
The final twist: nothing above has touched the memory. The first store to the returned pointer hits a virtual page with no physical backing, and the CPU's MMU raises a page fault. The kernel maps a zeroed physical page and returns — ~1 µs for a fresh page, doubled the first time (zeroing + fault). This is why malloc is fast but first-touch is slow, and why benchmarks that allocate without writing measure nothing real.
strace -e trace=brk,mmap ./your_program 2>&1 | tail
# and the faults, after the fact:
/usr/bin/time -v ./your_program 2>&1 | grep -E "minor|major"What the machine actually does is a graded descent: thread-local lists, arena bins, one pointer bump, one syscall, one mmap, and finally one page fault that only the first write discovers. malloc(256) is cheap precisely because it defers every expensive thing — locking, syscalls, physical memory — to the moment they're unavoidable.