Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Block sizes (20 minutes)
Using the table of section 2, say how many usable bytes malloc(1), malloc(41) and malloc(25) give on this allocator, and why malloc(1) is not wasteful in a list of 24-byte nodes.
Done when: 24, 56 and 40 bytes, and a note that a 24-byte node fits the smallest block exactly.
Hint
A 24-byte request fills a smallest block with no waste.
Easy 2: Which call (20 minutes)
For a fresh process, say whether malloc(50) and malloc(300000) are likely to call brk or mmap.
Done when: brk (the heap is enlarged, or has room) for the first, and mmap for the second, since 300,000 is above the threshold and the first heap block is only about 132 KiB.
Hint
The first heap block has about 132 KiB (135,168 bytes) of space.
Easy 3: Round up (20 minutes)
An arena rounds each request up to a multiple of 16. Find the bytes used after requests of 3, 17 and 32 bytes.
Done when: 16 + 32 + 32 = 80 bytes.
Hint
3 becomes 16, 17 becomes 32, 32 stays 32.
Medium
Medium 1: A free-list trace (45 minutes)
A heap has 100 bytes, first fit, no headers. Trace: A = malloc(25), B = malloc(25), C = malloc(25), free(B), D = malloc(20), free(A), free(C). Write the free list after each step.
Done when: D sits at 25–45, the free list after free(A) is [0–25), [45–50), [75–100), and after free(C) it is [0–25), [45–100), where free(C) joined both neighbours.
Hint
After free(B), the first hole that fits D is the one at 25–50, and it leaves 5 bytes.
Medium 2: Count the brk calls (60 minutes)
Write the program of section 4 without the frees. Run it under strace -c -e trace=brk. Report the calls and compute the average bytes per call.
Done when: a call count of the order of 750 and an average near 135,000 bytes, with the arithmetic shown.
Hint
Use strace -c, divide the heap growth by the number of calls.
Medium 3: Free does not shrink (60 minutes)
Reproduce the table of section 4. Then change the program so that the last block is freed first and the other 99,999 after it. Report the RSS after each step.
Done when: both tables, and a sentence on which block pinned the heap in the first run.
Hint
Print /proc/self/statm after each stage.
Hard
Hard 1: Write the arena (90 minutes)
Use the arena code, and add a function arena_mark that returns the current offset, and arena_release(mark) that sets the offset back to it. Use it in a program that allocates and releases 1,000 groups of 100 small blocks. Compare the time with malloc and free of the same blocks.
Done when: two timings, a correctness check that the arena never exceeds its size, and a note on when marks are safe.
Hint
Use clock_gettime and a fixed number of rounds.
Hard 2: A first-fit allocator (90 minutes)
Write a simulator for a heap of 1,000 bytes with a free list, first fit, splitting and coalescing, driven by a list of alloc and free commands. Test it on the trace of section 2.
Done when: the simulator prints the free list after each command and reproduces the table of section 2.
Hint
Keep the free list sorted by address, so that coalescing looks at the neighbours only.
Hard 3: Find the dynamic threshold (90 minutes)
Write a program that allocates and frees blocks of 200 KiB, 300 KiB, 600 KiB and 1 MiB in turn, many times. Use strace -e trace=mmap,munmap,brk to see which sizes use mmap the first time and which later. Repeat with MALLOC_MMAP_THRESHOLD_=131072.
Done when: a table of the calls in both runs, and a sentence on how the dynamic threshold changed the number of calls.
Hint
Compare the run with the container's environment variables removed, using env -u.