Heap Growth and Release: brk, mmap, and Trim

An allocator above the system call boundary manages virtual address space; the kernel manages physical pages. The two are decoupled by demand paging, and the decoupling is what makes a heap possible: an allocator can reserve a large contiguous range of addresses cheaply, hand out pieces of it, and let the kernel populate pages only as they are touched. The interface it uses to obtain that range determines how the memory can later be released, and the two available interfaces on Unix-like systems have different shapes.

The program break

brk sets the end of the process’s data segment, known as the program break, to an address. sbrk adjusts it by a signed increment and returns the previous break. Both operate on a single contiguous region that begins after the program’s static data and grows upward. The allocator treats the region between the old break and the new one as fresh heap.

The interface is old and its shape explains a great deal of allocator behaviour. Because the heap is one contiguous range, a brk-based allocator can extend its top chunk in place when the topmost block is too small for a request: raise the break, enlarge the block, return a piece of it. No new chunk is created, no free list changes, and the address space stays contiguous, which keeps boundary-tag arithmetic valid across the whole heap.

Contiguity is also the interface’s weakness. To release memory, the allocator must lower the break, and it can only lower it past blocks that are entirely free: the top chunk must be free, and the amount released is limited by where the highest live block sits. A single long-lived allocation near the top of the heap pins every free byte below it. This is why a brk-based heap’s footprint tends to track its high-water mark rather than its live set, and why allocators that care about release tend to move large and long-lived allocations out of the main arena.

There is a second, sharper constraint. The break is a property of the process, not of a thread. Two threads calling sbrk concurrently race on a single global value, so any allocator that supports concurrent growth must serialise the growth path even if the rest of its design is lock-free. Growth is rare enough that this is tolerable, but it makes the growth path a place where latency spikes appear under heavy multithreaded allocation.

brk also interacts with the address space layout. On Linux, the data segment and the mmap region grow toward each other from opposite ends of the address space, with the stack at the top. A heap that grows without bound eventually collides with a mapping placed by mmap, at which point brk fails. Modern kernels place mmap regions in a gap chosen to leave room, but the failure mode exists and appears as an allocation failure in a process with plenty of free physical memory.

Anonymous mappings

mmap with MAP_PRIVATE | MAP_ANONYMOUS and a file descriptor of -1 obtains a fresh range of addresses backed by zero-filled pages, independent of the data segment. The allocator uses it for two purposes: to obtain additional chunks when the main arena needs more room, and to serve large individual allocations directly.

The direct path is the important one for behaviour. A request above a threshold, commonly in the region of a hundred kilobytes, is served by a dedicated mapping rather than by carving a piece out of the heap. The advantages are immediate:

• Release is exact. munmap on the range returns the pages and the address space together, with no dependence on neighbouring blocks.
• No fragmentation. A large allocation cannot be pinned by small blocks around it.
• The mapping is page-aligned by construction, which satisfies large alignment requests without the header-and-padding gymnastics described in alignment handling.

The cost is a system call per large allocation and per free. On a context-switch-free path a system call still costs on the order of hundreds of cycles to a few microseconds depending on mitigations, and a workload that allocates and frees multi-megabyte buffers in a loop will spend measurable time in the kernel. Allocators mitigate by caching freed mappings instead of returning them immediately, keeping a small pool of recently unmapped regions, or leaving the mapping in place but marking it reusable, which avoids the mmap on the next request at the cost of retained address space.

MAP_NORESERVE and overcommit policy enter here. On Linux, mmap of anonymous memory normally succeeds without physical pages being allocated, because pages are assigned on first touch. A process can therefore reserve address space far exceeding physical memory, and the failure appears later as an out-of-memory kill rather than as an allocation failure. Allocators that assume a successful mmap means usable memory are relying on this behaviour; those that must fail gracefully need to touch pages or account for them.

What returning a page actually costs

Releasing memory to the kernel is not free, and the cost is not the same as the cost of freeing a block.

When a page is unmapped, the kernel must remove the mapping from the process’s page tables. For a 4 KiB page that is one page-table entry; for a range it is many, and the kernel may need to invalidate TLB entries on every CPU that might have cached the translation. That invalidation is a cross-processor operation, and its cost scales with the number of CPUs. On a large machine, a munmap of a small range can cost far more than the arithmetic the allocator did to decide to call it.

There is also the page-table memory itself. A process with a large sparse address space has page-table pages that exist only to describe mappings. Unmapping releases the mapped pages but not necessarily the page-table pages that described them, unless the whole range is removed. A heap that grows and shrinks repeatedly in different places can leave page tables sized for the high-water mark.

The practical consequence is that allocators release memory in batches and on a delay, not immediately. A typical policy keeps freed spans for reuse and releases only when the amount of retained free memory exceeds a threshold, or when the kernel signals pressure. This is the mechanism behind the familiar observation that a process’s resident size does not drop after a large deallocation: the bytes are free at the allocator level, and the allocator has decided the release is not yet worth its cost.

Trim, madvise, and the middle path

Between “keep the page” and “unmap the page” there is a third option: keep the mapping and tell the kernel that the contents are no longer needed. madvise with MADV_DONTNEED on Linux discards the pages, so subsequent access faults and gets a zero-filled page, while the address range remains mapped. MADV_FREE is a lazier variant: the pages are marked as candidates for reclaim, and the kernel may reclaim them under pressure, but if the process writes to them first the contents are retained.

The distinction matters for two reasons. First, MADV_DONTNEED costs a fault on next use, which is a trap-and-emulate sequence costing on the order of a microsecond, while retaining the page costs nothing until pressure arrives. Second, MADV_FREE preserves the contents if they are touched before reclaim, which lets an allocator return pages optimistically and still have the data if the allocation is reused immediately. That behaviour makes MADV_FREE attractive for freeing large buffers whose reuse is likely.

Both calls operate on page-granular ranges, so an allocator can only apply them to whole pages it holds free, which is why allocators that want to release memory keep their spans page-aligned and track which pages within a span are entirely free. A span that is 60% free but has a live object on every page cannot be released at all; the allocator must either keep it or move the live objects, which a non-moving allocator cannot do.

The threshold for using the large-allocation path at all is a policy choice with visible consequences. Set it too low and every medium allocation pays a system call; set it too high and large allocations come from the main arena, where they fragment it and pin the break. The familiar choice of a threshold in the region of a hundred kilobytes to a few hundred kilobytes reflects a compromise: below it, system call overhead dominates; above it, the fragmentation and release problems dominate.

Interaction with the rest of the allocator

The kernel interface constrains designs upstream of it. A slab cache that returns empty spans promptly pays page-allocator traffic; one that retains them holds the high-water mark. A thread-cached allocator multiplies the retention by the thread count, because each cache’s slack is invisible to the central policy. And a segregated heap whose classes each hold a partially used span has, in aggregate, a footprint determined by the sum of per-class slack plus per-class retention.

The one design that sidesteps most of this is the arena, which obtains large chunks and never returns individual bytes. Its release granularity is the chunk, so a chunk that is entirely unused can be unmapped cheaply, and a chunk that is partly used cannot be released at all. That is a coarse policy, and it is why arenas are paired with a scope that ends: at the end of the scope, everything in the chunk is dead, and the whole chunk goes back in one operation rather than in a sequence of per-page decisions.

A final edge case is the fork. After fork, the child has a copy-on-write view of the parent’s address space, including the heap. Any write by either process faults and copies a page, so a process that forks and then allocates heavily duplicates its heap page by page. Allocators cannot prevent this, but they can make it cheaper by keeping large regions untouched after fork, and by avoiding writes to free-list metadata that would dirty pages shared with a child.