99 Inside the allocator — the heap, alternative allocators, alternative standard libraries

99.1 Ledger ① — the header attached to each block#

free(p) does not take a size. And yet it must know how many bytes are being returned. The answer is simple — the size is written just before the address that was returned.

        ┌────────────┬──────────────────────────┐
        │ header     │ the place given to you   │
        │ size·flags │ ← the address malloc gave│
        └────────────┴──────────────────────────┘

This header explains two facts seen in chapter 46. Even a request for 1 byte consumes far more (the header plus alignment padding), and making countless small pieces makes the management information as large as the data.

The classic design (the dlmalloc family) lays one more layer on top of this. It writes the size at the end of the block too — a boundary tag. Then from any block the size of “the block just before” can be known at once, so coalescing with a neighbouring free piece on release finishes in constant time. It is the most basic device for preventing pieces from scattering finely.

99.2 Ledger ② — lists by size and caches per strand#

Keep the free pieces in one long list and every request must scan the whole list. So the lists are divided by size — these are bins. Taking glibc’s allocator as an example, there are roughly these layers.

The heart of it is the cache per strand (tcache). If several strands touch the same ledger, locking slows them down (chapter 95), so each strand keeps a small drawer of its own and takes from there first. Only when the drawer is empty does it go to the shared ledger. It is the common design of today’s fast allocators, differing only in name (tcache, thread cache, mimalloc’s local heap) while the idea is the same.

Two things seen in chapter 98 attach here. When the heap is short it is enlarged with brk (for small requests), and large requests are received separately through mmap. And releasing a large block may return it to the operating system, while small ones are mostly only marked in the ledger.

99.3 Fragmentation — memory grows though there is no leak#

Fragmentation is memory the allocator holds but cannot put to use. It comes in two kinds.

Internal fragmentation — the waste arising from giving a piece larger than the request. Request 24 bytes, be given a 32-byte slot, and 8 bytes are wasted. It is the fate of allocators that round requests up to a few fixed sizes (size classes), and speed is gained in exchange.

External fragmentation — the state in which the total free space is ample but there is no contiguous large lump, so a large request fails. If small live blocks are lodged between free pieces, those free pieces cannot be joined into a large lump.

This is what lies behind the phenomenon “there is no leak and yet memory keeps growing”. It appears especially in long-running servers, and the cause is usually allocating things of different lifetimes mixed together — one long-lived small object lodged in the middle of a large empty region ties up that whole region.

99.4 Swapping out the standard malloc — alternative allocators#

The allocator alone can be changed without mending the program. malloc and free are, after all, names, so linking another implementation (statically) or inserting it at run time (Linux’s LD_PRELOAD) puts that one in use.

How much difference does changing make — it depends on the workload is the honest answer. On a server with many strands and a flood of small allocations, performance can shift by tens of per cent, while in a single-strand computational program there is almost no difference. So there is one rule: measure, then change. And before changing, trying chapter 46′s first prescription — not allocating at all in the hot loop — is usually the greater gain.

99.5 Freeing with the size — C23′s free_sized#

Now that we have seen the allocator’s ledger, the point of two functions C23 added comes into view.

void free_sized(void *ptr, size_t size);
void free_aligned_sized(void *ptr, size_t alignment, size_t size);

free(p) takes no size. So the allocator has to remember “how big was this block” by itself, and that record is the header from this chapter’s first section. The caller usually knew the size already, and had no way to say it.

C23 gives the caller a way to say it. Hand over the size you know and the allocator need not read the header — which opens designs that drop the header altogether.

The contract is exacting. The size must be the one that was requested (not the possibly larger size the allocator handed back), and getting it wrong is undefined behaviour. Memory from aligned_alloc may not go to free_sized; use free_aligned_sized.

★ And the standard notes that an implementation may ignore the size and just call free. So this is not “the fast free” but a function that gives the allocator an opportunity — whether it pays is decided by the allocator you swapped in.

99.6 Alternative standard libraries#

There is also the choice of swapping out one layer larger than the allocator — the standard library implementation itself. It is the concrete form of chapter 76′s “the standard is a list and the implementations are several”.

The criteria for choosing are mostly three — size (embedded, containers), the convenience of static linking (musl’s strength), and the breadth of features (glibc’s strength). And what one runs into when moving is mostly not standard C but extensions: functions only glibc has, locale handling, subtle differences in threads and signals. Chapter 76′s conclusion — “use only what is in the standard and it ports” — pays off here.

99.7 Alternatives that change the shape — arenas, pools, and the allocator as an argument#

Until now the story has been making the same malloc better. There is another road. It is changing the very shape of allocation.

Arena (region, bump allocator). Take a large lump once, and when a request comes merely push a pointer forward. Allocation is one addition and so nearly free, and release is not done individually — when the work is done the pointer is returned to the beginning and the whole is thrown away. There is no fragmentation, the time is constant, and release cannot be forgotten. In exchange, individual release is given up.

This approach fits “things of the same lifetime” perfectly. One request of a web server, one function of a compiler, one frame of a game — for each unit of work with a clear beginning and end, keep one arena and reset it when it ends. It really is widely used (Apache’s memory pools and PostgreSQL’s memory contexts are the same idea).

Pool (slab). An allocator that handles only pieces of the same size. Slots cut in advance are managed as a list, so allocation and release are one list operation each, and there is no internal fragmentation either. It fits data structures with tens of thousands of nodes, or the fixed-object management of embedded work seen in chapter 98.

Taking the allocator as an argument. For the two above to have force, a library must ask the caller “where shall I get memory from”. So modern C libraries make a bundle of allocation functions into one value and take it as an argument. The table of function pointers learned in chapter 68 does exactly this work here.

We have walked the terrain of the standard library and opened even the warehouse beneath it. The next part is the attempt to handle all these traps and costs by design — proven, the library this book has leaned on.