Part 3 of 7 · 2 min read
Free lists
In plain words: An allocator must remember two things: which pieces are in use, and where the holes are. A hotel manager does the same with rooms. Each room has a size, and a list shows which rooms are free. The common design keeps a free list, a linked list of the free pieces. Each piece has a small header just before it that records its size. The program sees only the address after the header.
To serve malloc(n):
- Search the free list for a piece of at least n bytes. The rules of Level 6 apply: first fit takes the first piece that is big enough, best fit takes the smallest that is big enough.
- If the piece is much larger than n, split it: the first part goes to the program, and the remainder stays on the list.
- If no piece is big enough, ask the kernel for more (section 1).
To serve free(p), the allocator reads the header before p to learn the size, and puts the piece back on the list. If the piece sits next to another free piece, the two are joined, which is called coalescing. Without it, the heap would turn into many small holes (external fragmentation, page 2 of Level 6).
A trace on a heap of 100 bytes, with first fit and headers ignored (made up to show the idea):
| Step | Free list after the step | Note |
|---|---|---|
| Start | [0–100) | one hole |
| A = malloc(30) | [30–100) | A takes 0–30 |
| B = malloc(20) | [50–100) | B takes 30–50 |
| free(A) | [0–30), [50–100) | two holes, B in between |
| C = malloc(40) | [0–30), [90–100) | first hole is too small, so C takes 50–90 |
| free(B) | [0–50), [90–100) | B joins the hole at 0–30: coalescing |
Real glibc keeps more than one list (small sizes in bins, a cache for each thread), and every block has an 8-byte header, with blocks rounded to 16 bytes. The measurement on this machine shows the effect: consecutive requests of 24 bytes are 32 bytes apart, and the usable sizes are as follows.
| Request | Usable bytes |
|---|---|
| 1 | 24 |
| 24 | 24 |
| 25 | 40 |
| 40 | 40 |
| 41 | 56 |
A request of 25 bytes uses a 48-byte block, with 8 bytes for the header and 40 usable. The waste inside a block is internal fragmentation. So a program that makes 10 million 24-byte nodes uses about 320 MB (32 bytes each), and not 240 MB.
Free list
A free list is the allocator's list of the unused pieces of the heap, from which malloc takes a piece, and to which free returns it, joining it to its free neighbours if there are any.
Example: after the heap of 100 bytes served 30 and 20 bytes and freed the first, the free list has two holes, 0–30 and 50–100.
Check yourself:
1. What does the header before a block hold?
2. Why must free coalesce neighbours?
3. How many bytes of heap does a request of 25 bytes use on this machine?