How the malloc Function Manages Memory via User-Space Bookkeeping

A single system call to request memory from the kernel can take roughly 610 nanoseconds, a cost that would become prohibitive if a program had to perform one for every small allocation. To solve this, the malloc function acts as a sophisticated user-space manager that requests large blocks of memory and maintains its own internal bookkeeping to serve smaller requests efficiently.

This table provides the empirical data supporting the claim that malloc is significantly faster than direct system calls.

The Cost of Kernel Interaction

When a program requests memory, it resides in an address space divided into regions like text, data, bss, heap, and stack. While the kernel ultimately owns the physical memory, calling the kernel for every tiny allocation is inefficient due to the overhead of switching from userspace to kernel space.

This visual helps illustrate the different regions of a process's address space, such as the heap and stack, mentioned in the text.

By requesting a large block of memory at once—such as a 132 KiB jump in a single operation—malloc allows a program to perform hundreds of subsequent allocations without further kernel intervention. This strategy ensures that the majority of memory requests are handled by the library's internal logic rather than a slow system call.

Chart drawn by HN Digest from figures reported by benmandrew.com; values are shown as written in the source.

“malloc requests large blocks from the kernel and cuts them up itself.”

— What is malloc doing, anyway?

Internal Bookkeeping and Free Lists

To manage these large blocks, malloc uses 'chunks' that include a size header. This header allows the allocator to know how much memory is occupied and where the next chunk begins without the user needing to provide a size during the free operation.

This diagram explains the internal bookkeeping mechanism where a header precedes the actual memory allocated to the user.

When memory is freed, it is placed into a free list. The allocator then performs 'splitting' to break large free chunks into smaller pieces that fit specific requests, and 'coalescing' to merge adjacent free chunks back into larger blocks to prevent the memory from becoming unusable.

The allocator ensures that all returned pointers are 16-byte aligned, which is the standard for x86-64 architectures, ensuring the memory is compatible with any C data type.

Fragmentation and Resident Memory

A significant limitation of heap management is fragmentation. Because the kernel can only reclaim memory from the very top of the heap (the 'program break'), any live memory block located above a free gap prevents that gap from being returned to the system.

This means that in long-running programs, fragmentation can cause the resident set size (RSS) to grow over time. Even if the application 'frees' a large amount of memory, the physical RAM remains occupied if even a single small, live allocation sits at a higher address than the free space.

Handling Large Allocations with mmap

For very large memory requests, such as those exceeding 128 KiB, malloc may switch strategies and use the mmap syscall. This creates a completely independent mapping in the process's address space that is not part of the standard heap.

Unlike heap memory, these mmap'ed blocks can be returned to the kernel immediately upon being freed via the munmap syscall. This allows the allocator to handle massive allocations without contributing to the heap's fragmentation or preventing the program break from shrinking.