Memory Allocator

malloc and free over one address range

Design malloc and free over one contiguous range of addresses: find room, split what is too big, and merge freed neighbors so the range does not crumble into slivers.

Overview

An allocator owns one range of addresses, say 0 to 64, and hands out pieces of it on request. malloc(size) returns the start of a piece at least size bytes long that nobody else holds; free(address) gives the piece back. Under C's malloc and free, and under every language runtime, something like this is running.

The problem is hard for a reason that is easy to state: pieces come back in a different order than they went out. After a while the range is a patchwork of used and free pieces, and a request can fail even when the free bytes add up to more than it needs. Every design choice, the fit rule, splitting, merging, alignment, is about keeping that patchwork usable.

A strong answer keeps the blocks in one list in address order, splits a free block on malloc, merges a freed block with free neighbors on free, and names the two kinds of fragmentation with an example of each. Interviewers then push on the fit rule, on making free O(1), and on threads.

Scoping the problem

Is this a model of the algorithm, or real memory? — A model can keep block records in Python objects; a real allocator stores them inside the range — A model; addresses are integers
What is the alignment? — Requests are rounded up, which is one source of waste — 8 bytes, configurable
What happens when nothing fits? — Return a sentinel or raise — malloc returns None; free of a bad address raises
Which fit rule? — Changes which hole a request takes — First fit and best fit, as swappable policies
Do we merge freed neighbors at once? — Decides whether free bytes stay usable — Yes, on every free
Many threads? — Every change to the block list must be atomic — One lock

Core entities

The list is doubly linked and sorted by address, so a block's prev and next are exactly its physical neighbors. That is what makes merging on free a matter of looking at two pointers.

malloc: round up, pick, split

This trace runs the demo in the implementation on a range of 64 bytes with first fit and 8-byte alignment. Each row shows the block list after the call.

1 — malloc(10) returns 0 — 0..16 used, 16..64 free — 10 rounds up to 16; the free block is split
2 — malloc(16) returns 16 — 0..16 used, 16..32 used, 32..64 free
3 — malloc(8) returns 32 — 0..16, 16..32, 32..40 used, 40..64 free
4 — free(16) — 0..16 used, 16..32 free, 32..40 used, 40..64 free — Neighbors are used, so no merge
5 — malloc(40) returns None — unchanged — 40 bytes are free, but the largest hole is 24
6 — free(32) — 0..16 used, 16..64 free — Merges with both neighbors: 16 + 8 + 24 = 48
7 — malloc(40) returns 16 — 0..16 used, 16..56 used, 56..64 free — Now it fits

free: give back and merge

There are four cases, and the code handles them with two if statements in a fixed order: merge with next first, then with prev. Doing next first means the block that survives is always the one with the lower address, which keeps the list sorted with no extra work.

Neither — 1 new free block — None; only the flag flips
Next only — The two become one — Skip over next
Prev only — The two become one — Prev grows; skip over this block
Both — The three become one — Both of the above, in that order

Two kinds of fragmentation

Internal — Bytes inside a handed-out block that the caller did not ask for — Step 1: 10 requested, 16 given, 6 wasted — Smaller alignment; size classes that match common requests
External — Free bytes that are split into holes too small to use — Step 5: 40 free, largest hole 24, request for 40 fails — Merge on free; a fit rule that leaves fewer slivers

Choosing the hole

First fit takes the first hole that is big enough. Best fit takes the tightest one. Worst fit takes the biggest. The demo shows first and best fit disagreeing on the same list: holes of 24 at address 0 and 16 at address 48, then a request for 16.

First fit — The 24-byte hole at 0 — An 8-byte sliver at 16 and the 16-byte hole — Fails
Best fit — The 16-byte hole at 48 — The 24-byte hole whole — Succeeds
Worst fit — The 24-byte hole at 0 — The same sliver as first fit — Fails

Doug Lea's description of his allocator, the base of glibc's, reports that best-fit schemes of various kinds tend to produce the least fragmentation on real workloads. His allocator finds a best fit quickly by keeping free chunks in bins by size instead of scanning one list. The lesson for the interview: best fit is the better rule, and a real allocator makes it cheap with a size index rather than settling for first fit.

What real allocators add

The model keeps block records in Python objects and a dict. A real allocator has no dict; its records live inside the memory it manages.

Finding the block on free(p) — A dict from address to block — A header just before p holds the size and a used flag (a boundary tag)
Finding the previous neighbor — block.prev — A copy of the size at the end of each free block, so a free previous neighbor's header is one subtraction away
Alignment — Configurable, 8 by default — glibc returns addresses that are a multiple of 16 on 64-bit systems
Very large requests — Same list — glibc serves requests above a threshold (128 KiB by default, then adjusted at run time) straight from the operating system with mmap
Threads — One lock — glibc keeps several arenas so threads do not all wait on one lock; a tunable caps their number, and the default cap follows the number of cores

What you will be able to do

Draw the block list and walk through a split and a merge on a concrete trace.
Define internal and external fragmentation with the numbers from that trace.
Compare first, best and worst fit on one free list and say which real allocators use.
Explain how a real allocator finds a block on free without a dictionary.
Say what one lock protects and how production allocators reduce contention.

Functional requirements

malloc(size) returns the start address of a free run of at least size bytes, rounded up to the alignment, or None when no hole is big enough
free(address) returns a block; a freed block merges with any free neighbor on either side at once
A hole bigger than the request is split; the leftover stays free
free of an address that is not the start of a live block, including a second free of the same block, raises
The fit rule is a policy object; first fit and best fit are provided
layout(), free_bytes() and largest_free() expose the state for tests and for explaining fragmentation

Non-functional requirements

malloc is O(number of blocks) for the scan; free is O(1) thanks to the address dict and the doubly linked list
Every change to the block list happens under one lock
Memory overhead is one Block record per live or free run; the list is always sorted by address
The model never has two adjacent free blocks after a free, so the largest hole is as large as it can be

Interview questions

Is first fit or best fit better? The scan for best fit is longer.
Many objects have the same size. Can you do better than a general allocator for them?
Why merge on every free? You could wait until a malloc fails.
Your free() uses a dict. A real allocator has no dict. How does free(p) find the block?
Two threads call malloc at the same time. What breaks, and what do production allocators do about it?