How malloc Works in C: Dynamic Heap Allocation

The malloc function in C provides dynamic memory allocation by requesting, organizing, and serving chunks of memory from the heap during program execution. This article examines the internal mechanics of malloc, explaining how it communicates with the operating system via system calls, how standard C library allocators track and structure memory blocks, and how techniques like splitting, coalescing, and free lists prevent fragmentation and maintain optimal runtime performance.

The Heap and Virtual Address Space

Every C program runs within its own virtual address space, typically divided into segments: text (code), data, BSS, stack, and heap. While the stack automatically grows and shrinks with function calls, the heap is designed for variable-sized, manually managed memory whose lifetime exceeds the scope of the function that created it.

The heap begins directly above the BSS segment and historically grows upward toward higher memory addresses. malloc serves as an intermediary between user code and the operating system kernel, avoiding the heavy performance penalty of invoking a system call for every memory request.

System Calls: Interfacing with the Operating System

When a program requests memory that exceeds the current heap boundary, malloc asks the kernel to expand the process's address space. It primarily utilizes two system calls:

  1. brk and sbrk: Used for relatively small allocations. The brk call sets the address of the program break, which marks the end of the heap segment. When malloc exhausts its current pool of heap memory, it calls brk or sbrk to increment the break pointer, reserving more contiguous virtual pages.
  2. mmap: Used for large allocations (often exceeding a threshold like 128 KB in implementations such as glibc's ptmalloc). Instead of extending the continuous heap, mmap maps an anonymous page directly into the process's address space. When free() is called on an mmap-allocated region, the memory is immediately unmapped and returned to the OS via munmap.

Chunk Structure and Metadata

When malloc(size_t size) is called, it allocates more than just the requested number of bytes. The allocator embeds metadata immediately preceding the memory address returned to the pointer.

A typical memory chunk consists of:

  • Header: Contains control information, primarily the total size of the chunk (including the header) and status bits indicating whether the chunk is allocated or free, and whether it was allocated via mmap.
  • Payload: The usable memory region returned to the programmer. The pointer returned by malloc points directly to the start of this payload, not the start of the chunk.
  • Padding/Alignment: Memory systems require specific alignment (usually 8-byte or 16-byte boundaries) for hardware performance and safety. malloc pads requests to satisfy these architecture-specific constraints.

Managing Free Memory: Free Lists

To avoid repeatedly requesting memory from the OS, freed chunks are retained in user-space data structures known as free lists. Modern allocators employ several types of bins to track available blocks:

  • Fastbins / Small Bins: Single-linked lists or fixed-size pools that hold small chunks for rapid retrieval, using a LIFO (last-in, first-out) order to maximize CPU cache locality.
  • Unsorted Bins: Chunks recently freed are placed here temporarily, allowing them to be quickly reallocated if a similar size is requested shortly afterward.
  • Large Bins: Sorted doubly-linked lists used for larger allocations where searching by size is required.

Search Strategies

When allocating from existing free lists, malloc uses search heuristics to locate a suitable block:

  • First-Fit: Selects the first free block that is large enough. It is fast but can lead to fragmentation near the beginning of the heap.
  • Best-Fit: Scans all free blocks to find the smallest block that accommodates the request. This minimizes wasted space within the selected block but can be slower and produces tiny, unusable fragments.
  • Segregated-Fit: Routes the request to a specific size bin containing chunks within a narrow size range, combining the speed of first-fit with the space efficiency of best-fit.

Splitting and Coalescing

If the selected free chunk is significantly larger than the requested size, malloc splits the chunk. The first part is sized to the request, marked as allocated, and returned to the caller. The remainder becomes a new, smaller free chunk and is returned to the appropriate free list.

Conversely, when memory is released using free(), the allocator inspects adjacent chunks. If neighboring chunks are also marked as free, they are merged—a process known as coalescing. Coalescing recombines adjacent fragments into a single larger block, preventing external fragmentation and ensuring future large allocations can be satisfied without expanding the heap.