Heap Allocator Internals

1. The Allocator's Interface with the OS: brk and mmap

The first thing to understand is that malloc is a library function, not a system call. It acts as a middleman, requesting large blocks of memory from the operating system (OS) and then carving out smaller pieces for your application. This avoids the overhead of making a system call for every single small allocation.

The two primary system calls malloc uses on Linux-like systems to get memory are brk (or its wrapper sbrk) and mmap.

To summarize the key points from the video:

• The Heap and the Program Break: The heap is a region of a process's virtual memory that grows "upwards" from the end of the data/BSS segments. The program break is a pointer maintained by the kernel that marks the top of the heap. Any memory address below the break is valid; anything above it is not.
• brk() and sbrk(): These system calls manipulate the program break.
  • brk(addr) sets the break to a specific addr.
  • sbrk(increment) moves the break by increment bytes. Critically, it returns the previous location of the break, giving you a pointer to the start of the newly allocated memory block.
• mmap(): This system call creates a new, independent memory mapping in the process's virtual address space. Unlike sbrk, it is not tied to the contiguous heap region.

Most modern malloc implementations use a hybrid strategy:

1. For small-to-medium allocations: They use sbrk to grow a single, contiguous heap. This is efficient for frequent, small requests.
2. For large allocations: They switch to mmap. This is advantageous because a large mmap-ed region can be returned to the OS immediately with munmap when freed, preventing the heap from staying permanently bloated (a problem with sbrk). It also avoids fragmenting the main heap with a single huge allocation.

This hybrid approach is visualized well in the following diagram:

2. Managing the Heap: Metadata, Free Lists, and Fragmentation

Now that the allocator has a large region of memory, its main job begins: managing this space. It must keep track of which parts are allocated and which are free, so it can reuse the free parts for future requests.

This is done by dividing the heap into chunks. Each chunk contains the user's requested memory plus some metadata that the allocator uses for bookkeeping.

Let's consolidate those concepts, as they are central to any discussion about allocators.

The Chunk and its Metadata

The most basic allocator design embeds a header at the beginning of every memory chunk. This header typically stores:

• Size of the chunk: Needed so free() knows how much memory to release.
• Allocated/Free status: A flag (often packed into the low-order bits of the size field) indicating if the chunk is in use.

The user gets a pointer to the memory after this header. When free() is called with this pointer, the allocator simply subtracts the header size to get back to the metadata.

Free Lists: Tracking Available Memory

A free list is the data structure the allocator uses to keep track of all the free chunks.

• Implicit Free List: As shown in the video, this is the simplest form. The "list" is simply implied by the contiguous layout of chunks on the heap. To find a free block, the allocator must iterate through every chunk from the beginning of the heap, checking its status bit. This is simple but slow, with a search time of O(N) where N is the total number of chunks.

• Explicit Free List: A much more efficient approach. Here, the payload area of a free chunk is repurposed to store pointers to the next and previous free chunks, forming a doubly-linked list.

With an explicit free list, the search time is proportional to the number of free blocks, which is typically much smaller than the total number of blocks.

Fragmentation and Coalescing

• Internal Fragmentation: Wasted space inside an allocated chunk. This happens when the allocator gives you a block larger than you requested (e.g., due to alignment requirements or to meet a minimum block size).
• External Fragmentation: Wasted space between allocated chunks. This is the more serious problem, where you have many small free blocks, but none are large enough to satisfy a new request.
• Coalescing: The solution to external fragmentation. When a block is freed, the allocator inspects its adjacent neighbors (using the metadata headers/footers). If a neighbor is also free, they are merged into one larger free block. Performing this check on every free operation is called immediate coalescing and prevents the heap from becoming riddled with tiny, unusable free chunks.

3. A Look at a Real-World Allocator: glibc's ptmalloc2

The concepts of free lists and coalescing are the foundation. However, production-grade allocators like ptmalloc2 (used in glibc on Linux) are far more complex to deliver high performance, especially in multi-threaded applications.

Instead of a single free list, ptmalloc2 uses a sophisticated system of bins. A bin is a free list for chunks of a specific size or size range.

The binning strategy of ptmalloc2 is a masterclass in performance engineering:

• Tcache (Thread Cache): The fastest layer. Each thread gets its own cache of recently freed small chunks. Since it's thread-local, no locking is required, which is a massive performance win for multi-threaded applications.
• Fast Bins: For small chunks that miss the tcache. They are singly-linked and don't coalesce, trading a bit of fragmentation for the speed of not having to merge blocks. The assumption is that small blocks of the same size will be requested again soon.
• Unsorted Bin: A single "purgatory" bin where larger freed chunks land first. When the next malloc runs, it scans this bin, giving these recently freed chunks a chance to be re-used immediately (great for temporal locality) before incurring the cost of sorting them into the correct bin.
• Small/Large Bins: The main, sorted, coalesced free lists. Small bins are for exact sizes, while large bins are for size ranges. These are the general-purpose workhorses of the allocator.
• Top Chunk: The final frontier. If all bins fail, malloc carves memory from the chunk at the very top of the heap, extending the heap with sbrk if necessary.

Conclusion

You now have a multi-layered understanding of heap allocation, from the OS interface to the internal data structures and real-world optimizations. This knowledge is not just academic; it's essential for debugging complex memory corruption, tuning performance, and demonstrating system-level expertise in an interview.

Key Takeaways:

• malloc is a library function that gets memory from the OS via sbrk (for the main heap) and mmap (for large allocations or thread heaps).
• The allocator manages memory by dividing it into chunks, each with a metadata header storing its size and status.
• Free lists (implicit or explicit) are used to track available chunks for reuse. Explicit lists are much faster for finding free blocks.
• Fragmentation (internal and external) is the primary challenge. Coalescing—merging adjacent free blocks—is the key technique to combat external fragmentation.
• Production allocators like glibc's ptmalloc2 use a sophisticated hierarchy of bins (tcache, fast, unsorted, small, large) to optimize for speed, multi-threading, and memory usage.

In our next lesson, we will put this theory into practice. You will implement a fixed-block memory pool allocator, a common technique in embedded systems to achieve deterministic, real-time memory management by pre-allocating a fixed number of fixed-size blocks.