Skip to main content
Be Bitwise

Memory Allocator Internals

Advanced Memory Management · Memory & Systems track

8 min read

Part ofSystems Programming Companion, week 11

In this module

How malloc Actually Works

Call malloc(64) and you walk away with a pointer to 64 usable bytes. Where did those bytes come from, though? The memory allocator sits between your program and the OS kernel, managing a pool obtained via system calls (brk/sbrk or mmap) and slicing it into chunks of whatever sizes your program asks for. Knowing how allocators tick matters for performance tuning, debugging memory bugs, and understanding heap exploitation.

Key Concept

malloc is not a kernel call. It's a userspace allocator that asks the kernel for big slabs of memory once, then hands out smaller chunks from those slabs to your program — pooling, splitting, and recycling free memory in size-sorted bins.

ptmalloc2 / glibc malloc

The default allocator on most Linux systems is ptmalloc2, derived from Doug Lea's dlmalloc with threading bolted on. It sorts free memory into bins — linked lists of free chunks grouped by size.

Chunk structure: every chunk starts with two 8-byte fields, prev_size and size. The last 3 bits of size carry flags (sizes are always 16-byte aligned, so those bits would otherwise sit at zero), and the lowest, P, says whether the previous chunk is in use. That flag makes a neat space saving possible. prev_size only means anything when the previous chunk is free, so while it's in use, those 8 bytes belong to the previous chunk as part of its user data. The header is 16 bytes on paper and costs 8 per allocation in practice, which is why malloc(24) gets a 32-byte chunk. The minimum chunk is 32 bytes, enough room for the fd and bk pointers once it's freed.

Tcache (since glibc 2.26): a per-thread cache that both malloc and free check before anything else. It has 64 bins, one per chunk size from 32 to 1,040 bytes, each holding up to 7 chunks by default in a singly linked LIFO list. Because it belongs to one thread it needs no lock, which makes it the fast path for almost every small allocation. Only when the matching tcache bin is full (on free) or empty (on malloc) does glibc fall through to the bins below. Since glibc 2.29 each freed tcache entry also carries a key that lets free spot a chunk already sitting in the cache, which turns a naive double free into an abort. From glibc 2.32, safe-linking mangles the next pointers in tcache and fastbin lists with bits of their own address, so a heap overflow can no longer write a usable pointer there without first leaking a heap address.

Fastbins: singly-linked LIFO lists for sizes up to 128 bytes by default (configurable up to 160). No coalescing — adjacent free chunks don't merge. Allocation and deallocation are fast as anything: linked-list push/pop. Fastbins matter most because small allocations dominate.

Small bins: 62 bins covering 32 to ~1008 bytes, each holding chunks of one exact size. Doubly-linked FIFO lists. Small-bin chunks coalesce with adjacent free chunks where possible.

Large bins: cover sizes above ~1008 bytes, each spanning a range of sizes (sorted by size within the bin). Large allocations comb these for a best-fit chunk.

Unsorted bin: one bin acting as a cache. Freed chunks that don't fit in the tcache or a fastbin land here first. On the next allocation, the allocator sweeps the unsorted bin, parks each chunk in the appropriate small or large bin, and may grab a chunk directly if it fits.

Arenas and Thread Safety

ptmalloc2 uses arenas to reduce lock contention. Each arena is an independent heap with its own set of bins and a mutex. The main arena uses brk/sbrk; secondary arenas use mmap. When a thread calls malloc and its current arena is locked, ptmalloc2 may assign it a different arena or create a new one (up to a limit of 8 * number of CPUs). This reduces but does not eliminate contention.

jemalloc

jemalloc (used by FreeBSD, Firefox, optionally in Rust) tunes for multi-threaded workloads. Its trademark trick is aggressive thread-local caching.

Thread caches: each thread has a cache of recently freed objects per size class. Allocations hit the thread cache first, lockless. Only when the thread cache empties does the thread reach for a lock on its assigned arena.

Size classes: jemalloc bins allocations into size classes: 8, 16, 32, 48, 64, 80, 96, 112, 128, then 160, 192, 224, 256, with four classes for every doubling from there on. A request never wastes more than about a fifth of its block to rounding, and every object in a run has the same size, so no per-object header is needed at all.

Arenas: usually one per CPU core. Each manages its own set of runs (contiguous regions of same-sized chunks). Threads are assigned to arenas in round-robin fashion.

Extent-based management: large allocations live in extents — contiguous regions of virtual memory. jemalloc splits and coalesces them efficiently.

tcmalloc

Google's tcmalloc (Thread-Caching Malloc) shares jemalloc's thread-local-cache philosophy but takes a different architectural path.

Front-end: per-thread caches (per-CPU caches in newer versions) hold free objects by size class. Fast-path allocations and frees take no locks at all.

Middle-end: a transfer cache that batches objects between front-end and back-end. When a thread cache overflows, it ships a batch to the transfer cache. When it underflows, it pulls a batch back.

Back-end: the page heap, managing large contiguous regions. It serves the transfer cache by slicing spans (contiguous runs of pages) into objects of the requested size class.

Windows Heap

The Windows heap manager has its own architecture:

Front-end (Low Fragmentation Heap): since Windows Vista the default front-end is the LFH, grouping allocations into buckets (similar to size classes). Each bucket runs subsegments of 128 same-sized blocks. The LFH randomises allocation order within each subsegment as a hardening measure against heap exploitation.

Back-end: handles larger allocations and feeds the front-end. Uses a free list of variable-sized blocks and coalesces adjacent free blocks.

Windows heap also bakes in NT-specific features: heap segments (large virtual memory reservations committed on demand), guard pages for debugging, and tight integration with the NT memory manager.

Choosing and Tuning Allocators

Most applications should keep the default allocator. Switching only earns its keep when profiling fingers allocation as the bottleneck. Tells: heavy lock contention in malloc/free (visible in perf profiles), runaway memory use from fragmentation, or allocation-heavy workloads spread over many threads.

Common knobs: set MALLOC_ARENA_MAX for ptmalloc2 to cap arena count, drop in jemalloc for multi-threaded servers, reach for tcmalloc when you've got many small allocations across many threads, and use pool allocators for fixed-size objects you alloc/free hot.

Here's what that last suggestion buys. The program makes a million 32-byte allocations three ways: malloc and free back to back, malloc a thousand then free them all, and the same batches from a tiny pool allocator that keeps fixed-size slots on a free list:

Try itChange BATCH to 7 and see whether the batched malloc row catches up.
C (GCC 9.2.0)

Ignore the exact milliseconds, since the runner builds without optimisation and shares its machine. The pool should win clearly: no size lookup, no header, no checks, just a pointer popped and pushed. Of the two malloc rows, back-to-back pairs are glibc's cheapest case, because each free drops the chunk into the tcache and the next malloc takes it straight back. Batches of a thousand overflow the 7-entry tcache bin, so most chunks go through the fastbins instead. The pool's speed has a price, of course: it only ever hands out one size.