When a process starts, the system allocates space for the text segment and statically allocated data, space for the stack, and space for the heap, which contains dynamically allocated data.
Not all programs allocate data dynamically, so the initial size of the heap might be small or zero. Initially the heap contains only one free chunk.
malloc is called, it checks whether it can find a free chunk that’s big enough. If not, it has to request more memory from the system. The function that does that is
sbrk, which sets the “program break”, which you can think of as a pointer to the end of the heap.
sbrk is called, the OS allocates new pages of physical memory, updates the process’s page table, and sets the program break.
In theory, a program could call
sbrk directly (without using
malloc) and manage the heap itself. But
malloc is easier to use and, for most memory-use patterns, it runs fast and uses memory efficiently.
To implement the memory management API (that is, the functions
realloc), most Linux systems use
ptmalloc, which is based on
dlmalloc, written by Doug Lea. A short paper that describes key elements of the implementation is available at http://gee.cs.oswego.edu/dl/html/malloc.html.
For programmers, the most important elements to be aware of are:
- The run time of
mallocdoes not usually depend on the size of the chunk, but might depend on how many free chunks there are.
freeis usually fast, regardless of the number of free chunks. Because
callocclears every byte in the chunk, the run time depends on chunk size (as well as the number of free chunks).
reallocis sometimes fast, if the new size is smaller than the current size, or if space is available to expand the existing chunk. If not, it has to copy data from the old chunk to the new; in that case, the run time depends on the size of the old chunk.
- Boundary tags: When
mallocallocates a chunk, it adds space at the beginning and end to store information about the chunk, including its size and the state (allocated or free). These bits of data are called “boundary tags”. Using these tags,
malloccan get from any chunk to the previous chunk and the next chunk in memory. In addition, free chunks are chained into a doubly-linked list; each free chunk contains pointers to the next and previous chunks in the “free list”.
The boundary tags and free list pointers make up
malloc’s internal data structures. These data structures are interspersed with program data, so it is easy for a program error to damage them.
- Space overhead: Boundary tags and free list pointers take up space. The minimum chunk size on most systems is 16 bytes. So for very small chunks,
mallocis not space efficient. If your program requires large numbers of small structures, it might be more efficient to allocate them in arrays.
- Fragmentation: If you allocate and free chunks with varied sizes, the heap will tend to become fragmented. That is, the free space might be broken into many small pieces. Fragmentation wastes space; it also slows the program down by making memory caches less effective.
- Binning and caching: The free list is sorted by size into bins, so when
mallocsearches for a chunk with a particular size, it knows what bin to search in. If you free a chunk and then immediately allocate a chunk with the same size,
mallocwill usually be fast.