Part 2 of 7 · 2 min read
Why an allocator exists
In plain words: A wholesaler sells goods only in pallets, and a shop buys a pallet and sells single items from it. The kernel is the wholesaler: it hands out whole pages (4 KiB or more) and every request costs a system call and, later, page faults. The allocator is the shop. It asks the kernel for a large block, cuts it into small pieces, and hands out a piece for each malloc call without involving the kernel. The analogy stops in one place: a shop buys from a wholesaler it chooses, while a process has only the kernel to ask.
On Linux, the C library (glibc) asks the kernel in two ways:
brkmoves the program break, the end of the heap region that starts just above the program's data. Moving it up gives the process more contiguous heap, and moving it down gives some back.mmapcreates a new, separate region of anonymous memory (page 7 of Level 6 explained that these regions start with zero pages).
A measurement shows the cost saved. The program below makes 100,000 requests of 1,000 bytes each, about 100 MB in all. Running it under strace -c -e trace=brk counts the calls to the kernel:
| What the program did | Calls to the kernel |
|---|---|
100,000 calls to malloc(1000) |
749 calls to brk |
Each brk call extended the heap by about 135,000 bytes (132 KiB). So one call to the kernel served about 133 calls to malloc. The other 99.3% of the requests were served by the library from memory it already owned.
Program break
The program break is the address of the end of a process's heap region, and the system call brk moves it up to enlarge the heap or down to shrink it.
Example: when the first malloc runs, glibc moves the break up by about 132 KiB, and later requests are carved out of that region.
Read it as
malloc is not a system call. It is a function in the C library, and only some calls to it lead on to brk or mmap. You can see the real system calls with strace ./prog.
Check yourself:
1. Why does malloc not call the kernel for every request?
2. What does the program break mark?
3. In the measurement, how many malloc calls were served for each brk call, about?