32. Coda: the allocator you never needed
Tchaikovsky's Pathétique ends with a movement that goes down rather than up, and its last bars are the double basses alone, underneath everything: the piece does not conclude, it reaches the floor.
This is the floor. Every program in this book has stood on an allocator and not one of them has mentioned it.
The C Programming Language ends at §8.7 with a storage allocator, and it
ends there for a reason that has nothing to do with wanting a grand finale.
In C, allocation is a library written in C. A reader who does not understand
malloc cannot read the standard library, cannot read a heap dump, and
cannot be handed a char * with any confidence about what happens next.
Kernighan and Ritchie put it last because it was the hardest thing they had
to say, and because they had to say it.
Wolf does not have to. So this chapter builds one anyway.
32.1 Why C ends here
Chapter 8 answered the allocation question with a granule instead of a
function. A region is the allocator: you allocate into it freely, nothing in
it outlives anything else in it, and the closing brace is the free. Chapter
28 is what that looks like at the bottom of a data structure — a binary tree
whose nodes, strings, and list buffers all go at once, in one motion, with no
treefree to write and therefore none to get wrong.
That is the whole reason this chapter is a coda and not a requirement. Nothing later in the book depends on it. Skip it and you lose nothing you will need.
What you get for reading it is the floor itself, and the floor is worth
seeing once from below, for the reason chapter 9 gave: the raw tier is not
the dangerous end of the language, it is the simple end. Inside an unsafe
block a pointer is an address, arithmetic on it is arithmetic, two pointers
may name the same byte, and no rule about aliasing is in force. The rules
are C’s rules. An allocator is the program those rules were designed for,
which is why it is the one worth writing in them.
Two honesties before the program, because this is a page and not a chapter.
Our allocator is first-fit with splitting, and it does not coalesce. A freed block goes back on the list whole; two adjacent free blocks stay two blocks. K&R’s version does coalesce, and the difference matters to any program that runs long enough to fragment its heap. Ours is the version that fits on a page.
Our allocator does not think about alignment. It hands out cell indices into an array of eight-byte cells, so everything it returns is eight-byte-aligned and nothing finer is available from it. A real allocator takes a size in bytes and an alignment, and the arithmetic gets longer.
32.2 A free-list allocator in a page
The arena is one malloc from C. Inside it, everything is a cell index —
which is the trick that makes this short, so read the layout comment twice:
import c "stdlib.h"
// A block is two header cells and then its payload:
// [size][next][payload…]. `size` counts payload cells; `next` is the cell
// index of the next free block, and 0 ends the list, because cell 0 is
// never a header and so 0 can mean nothing.
struct Heap { cells: *i64, head: int }
fn arena(cells: int) -> Heap {
// # Safety: the allocation owns `cells` eight-byte cells and lives
// until the free at the end of `main`; every index below is inside it.
unsafe {
let base = c.malloc((cells * 8) as uint) as *i64
base[1] = (cells - 3) as i64
base[2] = 0
Heap { cells: base, head: 1 }
}
}
Heap holds a raw pointer in a field, and that is the shape chapter 9’s
E1302 note asks for. There are no unsafe fns in wolf and no *T crosses a
function signature, so an allocator’s state cannot be “the pointer, passed
around”; it is a value with the pointer inside it, and the module is the
audit granule.
The zero is the other thing to read. next == 0 means “no next block”
because cell 0 is never a header — cell 0 is the arena’s own first cell and
the first block’s header starts at 1. That is a sentinel, exactly like the
ones chapters 26 and 27 spent their pages arguing against, and here it is
correct: this is the tier where an integer is allowed to mean two things,
because there is no second channel to put the other meaning in and no
compiler asking for one.
Now the allocation itself. Walk the free list, take the first block big enough, split it if the remainder can hold a header and at least one payload cell:
#[trusted("every `next` is a header cell inside the arena, and no block sits on the free list twice")]
fn carve(mut h: Heap, want: int) -> int {
var prev = 0
var b = h.head
while b != 0 {
var size = 0
var next = 0
// # Safety: `b` is a header the free list put there, so cells `b`
// and `b + 1` are inside the arena.
unsafe {
size = h.cells[b] as int
next = h.cells[b + 1] as int
}
if size >= want {
var link = next
if size >= want + 3 {
let rest = b + 2 + want
// # Safety: both halves of the split lie inside the block
// at `b`, which had `size` payload cells.
unsafe {
h.cells[rest] = (size - want - 2) as i64
h.cells[rest + 1] = next as i64
h.cells[b] = want as i64
}
link = rest
}
if prev == 0 {
h.head = link
} else {
// # Safety: `prev` is the header before `b` on the list.
unsafe { h.cells[prev + 1] = link as i64 }
}
return b + 2
}
prev = b
b = next
}
0
}
#[trusted] is chapter 9 §9.7 arriving at the program it was written for.
Look at the obligation in the attribute and then look at the function: every
next is a header cell inside the arena, and no block sits on the list
twice. Nothing in the type system says either of those things. Nothing can:
they are properties of a graph the program maintains by being written
correctly. The attribute is where a person takes the proof over, the string
is the sentence a reviewer checks the body against, and §32.3 shows what the
tooling does with it.
Freeing is one store, and the rest of the program is a demonstration:
fn recycle(mut h: Heap, p: int) {
let b = p - 2
// # Safety: `p` came from `carve`, so `b` is its header cell.
unsafe { h.cells[b + 1] = h.head as i64 }
h.head = b
}
fn main() -> !int {
var h = arena(64)
let a = carve(mut h, 4)
let b = carve(mut h, 4)
print("a={a} b={b} free={h.head}")
// # Safety: both payloads own four cells each.
unsafe {
h.cells[a] = 40
h.cells[b] = 2
print("{h.cells[a] + h.cells[b]}")
}
recycle(mut h, a)
let d = carve(mut h, 2)
print("d={d} free={h.head}")
// # Safety: the arena is freed exactly once, and nothing reads it after.
unsafe { c.free(h.cells as *u8) }
0
}
$ lupin allocator.lu
a=3 b=9 free=13
42
d=3 free=13
Three lines, and each of them is the allocator answering a question.
a=3 b=9 is the split working: the first request takes cells 1 and 2 as its
header and hands back cell 3, the remainder becomes a new free block, the
second request repeats it four cells further along. free=13 is where the
free list points after both: past the two blocks it handed out.
42 is the payload being used as payload — two stores and two loads through
a raw pointer, which is the entire reason the arena exists.
d=3 is the interesting one. recycle put block a back on the front of
the list, so the next request finds it first and reuses the same cells. It
asked for two and got a block that holds four, because 4 is not big enough
to split — a header costs two cells and a payload at least one, so a
four-cell block cannot become a two-cell block plus anything legal. Those
two wasted cells are internal fragmentation, they are visible in this
program’s arithmetic, and there is no version of a hand-rolled allocator in
which you do not have to think about them.
32.3 The brace you already had
Now the two measurements, which are the coda’s whole argument.
The first is the one this part has been making since chapter 26:
$ wc -l samples/projects/allocator/allocator.lu samples/projects/wordtree/wordtree.lu
84 samples/projects/allocator/allocator.lu
45 samples/projects/wordtree/wordtree.lu
Comments and blank lines removed, the allocator is 65 lines. Chapter 28’s
whole word-frequency program — node, insert, in-order walk, tokenizer, and
main — is 41. The allocator is not a program that does anything a reader
wanted; it is the machinery underneath one, and it is half again as long as
the thing it would have been underneath.
Of chapter 28’s 41 lines, the ones doing this chapter’s job are two: region words { near the top of main, and the } ten lines later. That is the
comparison, and it is not close, and the reason it is not close is that the
two programs are not solving the same problem. carve and recycle maintain
a free list because the program asks for and returns individual objects at
unpredictable times. Chapter 28’s tree never returns anything: it allocates
until it is finished and then everything goes at once. Wolf did not write a
better allocator. It changed the question to one that has a two-line answer.
The second measurement is the one only wolf can print. Ask the compiler what it would take to review this file:
$ wolf audit-surface ./allocator.lu
unsafety surface (D11 rings)
module root:
trusted fn carve — "every `next` is a header cell inside the arena, and no block sits on the free list twice"
unsafe blocks: 7 · assume sites: 0 · re-entry doors: 0 · import c: 1 · inline c/asm: 0
error[E1303]: module `root` holds `#[trusted]` code, but the package manifest does not declare it
--> ./allocator.lu:21:4
|
21 | fn carve(mut h: Heap, want: int) -> int {
| ^^^^^ the first trusted function is here
|
= note: add `trusted = root` to `wolf.pkg` — the trusted roster is the supply-chain surface
`wolf audit` diffs (D11 ring 2), so every trusted module is declared, visibly.
= note: this package has no `wolf.pkg` yet; create one next to the entry file.
wolf audit-surface: undeclared `#[trusted]` module(s) — the manifest is the deal
Seven blocks, one C import, one obligation stated in English — and the deal chapter 9 §9.7 described, arriving as a refusal, because the manifest line that would declare this module is not written. The count is the reviewer’s budget: seven places where the compiler stopped proving things, and one sentence a person has to believe.
Ask the same question of chapter 28’s program:
$ wolf audit-surface ./wordtree.lu
unsafety surface (D11 rings)
(clean — no unsafety rings in this package)
Nothing to count, nothing to declare, nothing to believe.
So the book ends where it began, with a question about granules. Chapter 7 asked who owns a value. Chapter 8 asked how big the thing that dies together is. This page is what the answer bought: the program that would have been at the bottom of every wolf program ever written — the one C had to teach in its last chapter, because in C you cannot ship without it — turns out to be an exercise. Seven unsafe blocks and one obligation, against a brace you already had.