A Deep Dive into C++ malloc: How ptmalloc2 Actually Works

Ref

glibc wiki

CSAPP

Intro

Memory allocation sits at the heart of every running program. Everyone knows C's malloc() — at the application level it's a one-line abstraction, but behind it lies a whole memory-management stack. Here's a basic layered overview: from top to bottom we have the application layer, the language runtime, user-space memory allocation, the OS kernel's memory management, and finally the hardware. The subject of this post, malloc, sits between the language runtime and the kernel, acting as a middleman that keeps the memory "supply chain" running.

Why malloc Exists

Imagine there were no malloc and programs asked the kernel for memory directly. You'd run into at least these problems:

First, a granularity mismatch. Recall how virtual memory and paging work: the smallest unit the kernel manages is a page, typically 4KB, and there are only two interfaces, brk and mmap — the former can only move the end of the heap, the latter maps a whole-page region. But real allocations don't come in 4KB-aligned sizes. If I ask for a 4-byte integer and you hand me 4KB, that's a thousandfold blowup.

Second, the cost is too high. Every request would mean trapping into the kernel for a system call — one kernel entry plus a privilege-level switch typically costs hundreds of nanoseconds to sub-microsecond. Doing that on a hot path is a non-starter, and the latency is unpredictable.

Third, a lifetime mismatch. brk only controls the end of the heap, so it's effectively a stack: a pointer that can only move straight up and down. But in real programs objects are born and die out of order — what was allocated first may be freed last. An interface like brk simply cannot express "I'm giving back a chunk from the middle."

So you can quite intuitively design your way to this: the architecture needs a middleman to manage the program's memory. This middleman buys memory wholesale from the kernel in big batches, but retails to the program only the small slice it needs, while keeping allocation in user space as much as possible — reuse first, go back to the kernel wholesaler only when necessary. In other words, the middleman needs its own allocation strategy and its own recycling/reuse strategy — and that's malloc. void* malloc(size_t size) is, at its core, a bookkeeping system running inside your own process, managing memory bought in bulk.

Where malloc Gets Its Inventory

As the logistics provider between the program and the kernel, let's first understand how the kernel's wholesale mechanism works. The kernel's promise to each process is: you get your own flat, contiguous virtual address space, invisible to other processes. This space is managed in units of pages, and the kernel decides which page maps to which piece of physical memory. A side note on why pages rather than bytes: if every byte carried its own mapping metadata, the metadata overhead would be several times the data itself. Computing is full of designs like this.

The key property of virtual memory is that its mapping is lazy. When you go wholesale 1GB from the kernel, the kernel really just makes a note — it doesn't actually hand it over. Only when you actually try to write and trigger a page fault does the kernel allocate. That's why malloc itself returns quickly, and only the first real access is slow. It's also why "memory warm-up" exists: walk the region up front to make sure all the page faults have fired.

Within a process's address space, the kernel lays out regions like this — malloc can only touch two of them: mmap and brk.

brk moves the pointer at the top of the heap. That boundary is called the program break, and brk can slide this line up and down to grow or shrink the heap. Its limitation was mentioned earlier: as long as a single byte at the top of the heap is still in use, the program break can't come down, and that memory stays held and never gets returned.

mmap can allocate anywhere, but the size must be a whole number of pages, every call is a system call, and for security reasons the kernel must zero the pages. That makes it more expensive and less suited to frequent, small purchases.

From this, glibc arrived at its malloc strategy:

• For small, frequent requests: first use brk or mmap to obtain more heap space (why "or" — see the multithreading section later), buying a large batch at once, then do the carving inside it (details below), with reuse — even after the program calls free, the memory isn't necessarily returned to the kernel; in practice the resources most likely stay in malloc's hands.
• For large requests (above the threshold M_MMAP_THRESHOLD, 128KB by default and dynamically adjusted): use mmap to hand you one whole block directly. malloc does no carving — it's essentially proxying a system mmap call — and munmap returns the whole thing to the kernel in one go.

Let the Carving Begin!

The carving-and-allocating logic is the core of malloc's design. What comes wholesale from the kernel is one big stretch of memory; to retail it out, an allocator like malloc must be able to answer these queries at any time: How big is this block (the user won't tell you at free time)? Are the blocks before and after it free — can they be merged and sold together? What free blocks exist right now, where do I find one of a suitable size, and where's the fastest available one?

The intuitive approach is to keep a separate table off to the side. But then every allocation pays an extra memory access to consult an external table — more memory, and unfriendly to the cache. glibc's choice is ruthless: embed the metadata directly into each block of memory itself. Every carved block — a chunk — carries its metadata glued right next to its data in its header:

Chunks get strung together into linked lists, and that list structure is called a bin. By structure, ptmalloc has 4 kinds of bins (all size figures below are 64-bit platform defaults):

• fast bins: A bet that "small objects just freed will be wanted again immediately." They manage small blocks up to roughly 128 bytes, one singly-linked list per size class, LIFO — push and pop at the head. The aggressive part: they don't clear the chunk's flag bit (the P bit) and never coalesce, so to its neighbors a fast-bin chunk looks no different from an allocated one. As a result, malloc/free of a small object is nothing more than a few pointer operations. The price when the bet fails is fragmentation.

• small bins: Built for determinism. Below 1KB, one size class every 16 bytes; every chunk within a class is the same size. The list is maintained FIFO (insert at the head, take from the tail) — grab one in O(1) and you're done.

• large bins: Big blocks aren't worth exact size classes (the class count would explode), so they're binned by size range, kept sorted by size within each list, and lookup takes the smallest block that's big enough.

• unsorted bin: Think of it as a cache in front of the other bins. When a chunk is freed, it isn't classified immediately — that costs something. ptmalloc first drops the chunk into the unsorted bin; only on the next malloc miss does it come here to shop, and whatever isn't picked gets filed into its proper bin.

The top chunk is one large free region. When none of the bins have anything available, allocations come here to carve off a piece — and if even that isn't enough, it's back to brk for another wholesale run!

This way, sir

So when an allocation request arrives, in what order should malloc consult these bins? Setting multithreading aside for now, ptmalloc follows this simplified model (multithreading comes later): try from cheapest to most expensive — roughly a greedy strategy.

Going the other way, free needs a matching mechanism for coalescing chunks. As the diagram shows, if the block between two free blocks is being freed, we'd like all three to merge afterward and then land in the unsorted bin awaiting reclassification. Recall the metadata in the chunk layout diagram — it exists precisely for this moment. The prev_size field in the header records the size of the previous chunk, giving O(1) access to the previous chunk's boundary; this field is also known as the boundary tag. Note that prev_size is only valid when the previous chunk is free — when the previous chunk is in use, that space gets reused by it to store data, and whether the previous chunk is free is exactly what the P bit (PREV_INUSE) tells you.

If the merged chunk reaches the top chunk, merging continues; and if the top chunk grows past a threshold (M_TRIM_THRESHOLD, 128KB by default), malloc hands that memory back to the kernel — release in the physical sense.

The sources of fragmentation are visible in this same picture. The normalization step rounds every request up to a fixed alignment — 20 bytes becomes 32 bytes, and the difference is wasted forever. This is internal fragmentation.

Meanwhile, the positions of carved-out chunks are unpredictable, and each chunk's lifetime is defined and managed by the program itself. If one object lands between two free regions and turns out to be extremely long-lived, those two regions can hardly ever merge; the program break can't come down, and the memory never goes back to the kernel. This is external fragmentation.

Scaling to Multiple Threads

When allocation requests come from more than one thread, the most naive fix is a single global lock over the whole allocator. Correctness is fine, but every malloc/free from every thread serializes, and the cache line holding the lock ping-pongs between cores — performance gets ugly.

The improvement is almost inevitable: make several copies of the whole allocation apparatus. In ptmalloc each copy is called an arena — a complete, independent "heap + bins + one lock." Threads bind to an arena, and threads on different arenas don't interfere with each other. But the arena count is capped (8× the core count by default on 64-bit), so with enough threads you're back to fighting over locks. To ease this, glibc added another layer: tcache, a per-thread cache of small blocks. Access to it is entirely thread-local — no locks, no atomics. On a miss, you fall through to the arena and walk the path from the previous section. One more note: the main arena's heap comes from brk, while the other arenas' heaps come from mmap (recall the earlier "brk or mmap").

The tcache itself is a simple structure: 64 singly-linked lists binned by size, covering small blocks up to about 1KB. All threads try here first and only go to an arena when it comes up empty. This is, once again, a classic move in computing: use a cache to amortize the expensive layer below, just as malloc amortizes the kernel. The memory hierarchy of a computer is, at its essence, caches all the way down (CSAPP).

Look back at the first diagram and you'll see the whole system telling the same story over and over: every layer buys the expensive resource of the layer below wholesale and retails it to the layer above — the kernel wholesales physical pages from the hardware, malloc wholesales address space from the kernel, tcache wholesales chunks from the arena, and your object pool wholesales slabs from malloc. And every design fork comes down to: where the resource lives, how many copies to make (lock vs. arena vs. per-thread), and how much memory you're willing to hoard for speed. malloc is no longer a black-box function, but the middleman right in the middle of this map, connecting the layers above and below.

Here we go again...

Back to C++. From the program's point of view, objects are more than bytes — malloc's job ends at handing raw memory over to C++. C++ objects have lifetimes, constructors, and destructors, so new in C++ is not malloc: it adds an extra step of managing the object.

On construction, new decomposes into operator new plus new (ptr) T(args) — allocate memory first, then construct the object. On destruction it goes in reverse (which is exactly what intuition says): delete first calls ~T() to destroy the object, then calls operator delete to release the memory.

In practice, even though we can swap in modern malloc implementations like tcmalloc and friends, squeezing out peak performance still relies on tricks like object pools and inter-thread caches — recall our previous post.