# 05: Memory Management – User Mode: From brk to malloc — Deep Dive into User-Space Memory Allocators
“When a user program calls malloc, how do the kernel and libc work together? This article delves into the brk/mmap system calls, the dlmalloc algorithm, and compares glibc’s implementation details, building an efficient, low-fragmentation user-space memory allocator.”
Introduction: Challenges of User-Space Memory Management
When a user program calls malloc(100), the seemingly simple operation involves complex collaboration between user mode and kernel mode:
Small memory (<128KB): Through brk to extend the heap, libc manages the free list
Large memory (≥128KB): Through mmap anonymous mapping, directly allocates virtual memory
Memory reclamation: free needs to merge adjacent free blocks to avoid fragmentation
Security boundaries: The kernel must verify user pointers to prevent out-of-bounds access
User-space memory allocators (such as glibc’s ptmalloc) are key to performance and memory efficiency, and their design directly impacts application performance.
This article systematically analyzes user-space memory management, from system calls to libc implementation, and deeply compares glibc’s dlmalloc algorithm, ultimately providing a runnable industrial-grade framework.
Chapter 1: brk and mmap System Calls
1.1 brk System Call: Heap Management Basics
Core role of brk: manages the Program Break pointer, extends/shrinks the process data segment, returns the new heap top address
System call interface:
User-mode wrapper:
1.2 mmap System Call: Flexible Memory Mapping
Core capabilities of mmap: anonymous mapping (allocates large virtual memory with MAP_ANONYMOUS), file mapping (maps files to memory with MAP_SHARED/MAP_PRIVATE), shared memory (inter-process shared memory region)
System call interface:
User-mode wrapper:
1.3 brk vs mmap Comparison
| Feature | brk | mmap |
|---|---|---|
| Use case | Small memory (heap) | Large memory, file mapping |
| Memory contiguity | Contiguous | Can be non-contiguous |
| Allocation granularity | Page-aligned | Page-aligned |
| Reclamation method | sbrk(negative) | munmap |
| Fragmentation risk | High (middle cannot be freed) | Low (any region can be freed) |
| Performance | Fast (single system call) | Slow (requires VMA operations) |
💡 glibc default threshold 128KB: small memory uses brk, large memory uses mmap
Chapter 2: User-Space malloc Implementation Framework
2.1 malloc Design Goals
Core requirements:
-
High performance: O(1) time allocation/free
-
Low memory overhead: metadata < 8 bytes per block
-
Low fragmentation: merge adjacent free blocks
-
Thread safety: support multi-threading (this article simplifies to single-thread)
Design decisions:
Small memory (<128KB): use heap extended by brk + free list
Large memory (≥128KB): use mmap anonymous mapping
Free block management: Boundary Tag method
2.2 Memory Block Structure Design
Chunk Header:
Key design:
Low 3 bits store flags: saves memory
prev_size field: enables bidirectional merging
fd/bk pointers: used as linked list pointers when free
2.3 Free List Management
Boundary Tag principle:
Each block stores its own size and the previous block’s size at both the header and footer
Allows O(1) merging of adjacent free blocks when freeing
Free blocks maintain a doubly-linked list for fast allocation and deallocation
Chapter 3: glibc malloc (ptmalloc) Implementation
3.1 Arena and Heap Extension
Per-thread arena:
– Main thread uses brk to extend the heap
– Child threads use mmap to allocate separate heaps
– Reduces lock contention between threads
3.2 Fast bins and Small bins
Fast bins (LIFO):
– Blocks ≤ 64 bytes (default)
– Fast allocation/free, no merging
– 10 bins, step size of 8 bytes
Small bins (FIFO):
– Blocks ≤ 512 bytes (32-bit) / ≤ 1024 bytes (64-bit)
– Regular doubly-linked list management
– 62 bins, step size of 16 bytes (64-bit) / 8 bytes (32-bit)
3.3 Unsorted bin and Large bins
Unsorted bin:
– Temporary storage for recently freed blocks
– Avoids expensive exact bin insertion
– Serves as a “buffer” between fast/small/large bins
Large bins (63 bins):
– Blocks > 512 bytes (32-bit)
– Sorted by size, each bin holds a range
– Requires search within the bin
3.4 Top Chunk and mmap
Top chunk (wilderness):
– The last chunk in the heap, adjacent to the program break
– When no free blocks match, split from top chunk
– When top chunk is insufficient, extend brk
Direct mmap:
– Requests > 128KB (default threshold)
– Allocated via mmap anonymous mapping
– Has its own header (mmap_chunk), can be independently unmapped
Summary Comparison Table
| Bin Type | Size Range | Count | Characteristics |
|---|---|---|---|
| Fast bins | ≤ 64B | 10 | LIFO, no merging, fast |
| Small bins | 64-512B (32-bit) | 62 | FIFO, fixed size |
| Unsorted bin | Any | 1 | Recently freed, buffer zone |
| Large bins | > 512B | 63 | Range-based, needs search |
| Top chunk | End of heap | 1 | Last resort, extendable via brk |
| mmap chunk | ≥ 128KB | Many | Directly mapped, independent unmapping |
💡 Understanding malloc internals is crucial for performance tuning and memory leak debugging!
#MemoryManagement #malloc #glibc #ptmalloc #brk #mmap #OSKernel #WritingFromScratch
Comments