Step 1 of 14 · commit 1: Add kalloctest, a stress test for the page allocator

The test: three harts allocating at once

The first commit adds the test, and it passes on the unmodified kernel: this lab changes speed, not behaviour.

churn is the workload. Each of three children (one per hart, though the scheduler decides where each actually runs) grows by 64 pages with sbrk, writes a value into every page, checks them all, and shrinks again, 2,000 times. Each round costs the kernel 64 kalloc calls in uvmalloc and 64 kfree calls in uvmunmap: 768,000 allocator calls in all, from three harts at once, for pages no two processes ever share.

sbrk here is the eager kind (sbrk passes SBRK_EAGER), so the pages are allocated inside the system call, with interrupts on before the allocator’s own locks turn them off. The writes check that each page really belongs to this process: a page handed out twice would show another process’s value.

churntest prints the tick count as information. It is not a check: on QEMU it says more about the emulator than about the allocator (see the measure section).

Step 2 of 14 · commit 1: Add kalloctest, a stress test for the page allocator

What a single process must still be able to do

The other three checks are about properties that per-CPU lists could break.

• gather (line 135): after churn, the freed pages are wherever the three children freed them. countfree allocates page after page in one process until sbrk fails; it must get exactly as many pages as at the start. An allocator that looks only at its own CPU’s list would stop early.
• exhaust (lines 84-123): three children allocate one page at a time until sbrk fails, at the same time, and hold on to their pages (they block in read on the go pipe) until all three have failed. Between them they must get nearly all of memory: each child’s own page tables, about one page per 512 heap pages, come out of the same pool, which is why the check allows 256 pages of slack. In practice they got 32,378 of 32,472. This phase is where all three harts’ lists run dry together, and where clinic 2’s deadlock appeared.
• no leaks: free pages at the end equal free pages at the start.

Everything the test checks is visible from user space. Which list a page is on, and how often a lock was contended, are not; for those you use Ctrl-P (commit 5) and a contention counter.

Step 3 of 14 · commit 2: Make kmem an array of free lists with named locks

One list and one named lock per CPU

The data structure first, with no change in behaviour: kmem becomes an array of NCPU (8) structures, each a lock and a list head. In this commit kalloc and kfree still use kmem[0] only (lines 67-71 and 82-86), so the system behaves exactly as before.

Each lock gets its own name, and the name is stored in the struct (name[8]). initlock keeps only a pointer to the name (kernel/spinlock.c:14); a name built in a local array would be gone when kinit returns. "kmem0" is copied and its digit bumped by i, giving kmem0 to kmem7. Nothing in the lock code reads the name; it exists for people and tools, here the contention counter that tells kmem0 from kmem1. (Clinic 4 forgets this loop.)

kinit runs on hart 0 only (kernel/main.c:19), with interrupts off and paging off, before harts 1 and 2 leave their wait on started: the locks are initialized before anyone can use them, and no lock is needed to do it.

Step 4 of 14 · commit 3: Give each CPU its own free list

kfree puts the page on this CPU's list

Now the lists become per-CPU. kfree reads the CPU number and pushes the page on that CPU’s list, under that list’s lock.

The recorded moment (gdb on the finished branch, whose kfree is this one plus a counter): the shell, pid 2, has just finished exec("sh") on hart 2 and kexec is freeing the old image’s pages. Each goes on kmem2. noff is 2: kfree's own push_off and the list lock. intena is 1: this is a system call, interrupts were on when the outer push_off ran, and the final pop_off will turn them back on.

The push_off on line 73 comes before cpuid() and the pop_off on line 79 after the release. Between them no timer interrupt can be taken on this hart, so the thread cannot be moved, and id names the hart it is running on for as long as it is used. The acquire on line 75 would turn interrupts off as well, but too late: id was read, and the lock chosen, before it.

Step 5 of 14 · commit 3: Give each CPU its own free list

Why cpuid() needs interrupts off

cpuid does one real thing, mv a0, tp: read tp. start put the hart’s mhartid there (kernel/start.c:47-kernel/start.c:48), uservec reloads it from the trapframe on every entry from user space (kernel/trampoline.S:79), and the kernel never changes it. So tp is always the number of the hart executing the read.

The comment on lines 61-63 is the rule this lab lives by. A thread can move to another hart only by giving up the CPU: sleep, or a timer interrupt that makes kerneltrap call yield (kernel/trap.c:157). swtch does not save tp; it belongs to the hart, which is why kernelvec deliberately does not restore it (kernel/kernelvec.S:44: “in case we moved CPUs”). A thread resumed on hart 1 reads tp = 1 from then on, but any id it read on hart 2 still says 2.

The allocator never sleeps, so turning interrupts off is enough. mycpu has the same requirement (line 72) and myproc shows the pattern in miniature: push_off, read, pop_off (lines 85-88).

Step 6 of 14 · commit 3: Give each CPU its own free list

kfree inside kwait, at noff 4

The same kfree, called from a much deeper place. The shell (pid 2) has waited for echo hi (pid 3) and found it a ZOMBIE. kwait holds wait_lock and the child’s p->lock (kernel/proc.c:376, kernel/proc.c:384) and calls freeproc (kernel/proc.c:398), which frees the trapframe and every page of the child’s address space through kfree.

gdb recorded noff 4 here, on hart 2: wait_lock (1), echo’s p->lock (2), kfree's push_off (3), kmem2 (4). intena is 1, recorded by the outermost level, the acquire(&wait_lock) in a system call; the inner levels leave it alone. When kfree returns, its pop_off brings noff back to 2, and interrupts stay off because noff is not 0.

In the original kernel this path is the deepest one measured, at noff 3 (Locks and interrupt state). The new push_off adds a level to every path through the allocator. That is harmless (noff is an int, and sched only cares that it is exactly 1 at a switch), but it is the kind of change to a kernel-wide property that is worth noticing: here it is also why pop_off and not intr_on is the only correct way out.

Step 7 of 14 · commit 3: Give each CPU its own free list

kalloc tries its own list, then the others, one lock at a time

kalloc scans the lists starting with its own (i = 0) and takes one page from the first list that has one. Each list is locked, examined and unlocked before the next is locked: no hart ever holds two kmem locks, so two harts scanning each other’s lists cannot deadlock (question 5).

The first allocation on hart 1 in a recorded boot shows why the scan is needed at all. The first process (pid 1) was picked by hart 1’s scheduler and in forkret calls kexec for /init, which needs a page table. kmem1 is empty: every free page is on kmem0, where kinit put them. Hart 1 scans kmem2 to kmem7 (all empty) and takes its page from kmem0 at i = 7. (Recorded on the finished branch, where the same scan happens in steal; gdb showed kmem0 held, noff 2, intena 0.)

intena is 0 because forkret runs with interrupts off: it releases the p->lock the scheduler acquired with interrupts off (kernel/proc.c:520), and nothing has turned them on since. So this kalloc's pop_off will leave them off.

This commit is complete and correct, and it passes usertests -q. It is also slow in a way the next commit fixes: a CPU with an empty list stays empty, and pays a scan of several locks for every page (clinic 3 measures it).

Step 8 of 14 · commit 3: Give each CPU its own free list

A page fault versus a system call

The same lines, entered from a page fault. In usertests lazy_alloc (pid 5 in the recorded run, on hart 2) the process touches memory it reserved with sbrklazy; usertrap sends the store fault to vmfault (kernel/trap.c:71), which calls kalloc (kernel/vm.c:469).

gdb recorded noff 2 and intena 0 with kmem2 held. Compare the system call in the fourth step (intena 1). The difference is usertrap: it turns interrupts on only for a system call (kernel/trap.c:66); for a fault, SIE is still 0 from the trap entry. So in a fault, kalloc's push_off is the outermost level and records 0, and its pop_off at line 103 leaves interrupts off, as the rest of the fault handling expects. In a system call the same pop_off turns them back on.

This is the reason the allocator must use the counting pair: it cannot know whether its caller had interrupts on, and it must leave them exactly as it found them.

Step 9 of 14 · commit 4: Steal pages from other CPUs in batches

steal: cut a batch off the victim's list

Commit 4 moves the scan of other lists into steal and makes it take up to STEAL (64) pages. Under the victim’s lock only: walk at most 63 next pointers to find the last page of the batch, and make the page after it the victim’s new head. That is one lock round trip and a walk of at most 64 nodes, whatever the length of the victim’s list.

The recorded moment: you typed kalloctest at the shell; the shell’s child (pid 4, still running sh’s code before its exec) grows its heap with sbrk on hart 1. kmem1 is empty, so kalloc calls steal(1), which finds kmem2 to kmem7 empty and cuts 64 pages off kmem0 (i = 7). gdb: kmem0 held, noff 2 (kalloc's push_off and kmem0), intena 1 (a system call).

The scan order (id + i) % NCPU gives each hart a different first victim: hart 0 looks at kmem1 first, hart 1 at kmem2, hart 2 at kmem3. With 3 harts and NCPU 8, harts 1 and 2 pass several lists that are always empty before they reach kmem0; that costs a few lock round trips per steal, once per 64 pages.

Step 10 of 14 · commit 4: Steal pages from other CPUs in batches

steal: keep one page, give the rest to your own list

The victim’s lock is released on line 105 before this CPU’s own lock is taken on line 110. That ordering is the whole deadlock argument: no hart ever waits for a kmem lock while holding another, so no cycle of waiting harts can form. (Clinic 2 takes the own lock first and deadlocks on the second kalloctest.)

Then the batch is spliced in front of the own list: last->next points at the old head, and the head becomes first->next. The first page is kept for the caller; the other 63 are now on kmem1, and the next 63 allocations on hart 1 are local.

Between line 105 and line 110 the batch is on no list: it is reachable only from first and last. Interrupts are off, so the window is a few instructions; but another hart that scans all lists in that window will not see these 63 pages (question 8). With the opposite rule (take two locks in CPU order) the batch would never be in transit, at the price of more complicated code.

Step 11 of 14 · commit 4: Steal pages from other CPUs in batches

kalloc, final shape

kalloc now does the common case in five lines: push_off, cpuid(), pop a page from the own list under the own lock, release. Only if that list was empty does it call steal, and by then it holds no kmem lock. pop_off comes last, so id is valid for steal too.

The recorded moment is the shell’s child on hart 1 again, a few allocations after the steal: its own list now has pages, and this allocation is purely local. gdb: kmem1 held, noff 2, intena 1.

Compare with the original kalloc (kernel/kalloc.c:69): one lock, always the same one. Here, in the common case, also one lock, but each hart’s own, which no other hart touches unless it is stealing. In the measured kchurn workload that brings the contended acquisitions from 43,429-49,770 to 2-5 (measure section).

Step 12 of 14 · commit 5: Show each CPU's free-page count on Ctrl-P

A count per list, kept under the list's lock

The last commit makes the distribution of memory visible. Each list gets nfree, kept exact by updating it in the same critical sections that change the list: ++ in kfree, -- in kalloc, -= n on the victim and += n - 1 on the stealer in steal.

kmemdump prints the eight counts and takes no lock, following procdump's rule (kernel/proc.c:675): Ctrl-P must work on a machine that is stuck, and a machine stuck on a kmem lock (clinic 2) is exactly the one you want to look at. The price is that a count may be a moment old; an int read is a single lw, so it is never torn.

The recorded moment: Ctrl-P after echo hi. The UART interrupt was taken on hart 1 while it was idle in its scheduler, so kernelvec pushed its frame on the scheduler stack; consoleintr holds cons.lock (noff 1, intena 0: an interrupt handler) and calls procdump, which calls kmemdump. Output: free pages: kmem0 32435 kmem1 73 kmem2 37 kmem3 0 kmem4 0 kmem5 0 kmem6 0 kmem7 0. Harts 1 and 2 have stolen a little from hart 0 and are living on it.

Step 13 of 14 · commit 5: Show each CPU's free-page count on Ctrl-P

procdump prints the counts

One line in procdump, after the process list. It is the only change outside kalloc.c (apart from the prototype in defs.h), and it changes nothing for the rest of the kernel.

This is the tool for the last think question. Type Ctrl-P after kalloctest, after usertests -q, after a big program exits: the free pages are on whichever list the last big free went to (kmem0 0 kmem1 0 kmem2 32545 after one kalloctest in a recorded run; kmem0 32545 kmem1 0 kmem2 0 after the next). Nothing moves them back; stealing in batches of 64 is what keeps that imbalance cheap.

Step 14 of 14 · commit 5: Show each CPU's free-page count on Ctrl-P

What changed, and what it cost

The whole change is about 90 changed lines in kalloc.c, plus one line in procdump. The rest of the kernel did not notice: every caller of kalloc and kfree is unchanged, and usertests -q passes at every commit.

What it bought, measured with a counter of failed amoswap attempts per lock (measure section): during three processes churning memory on three harts, contended acquisitions of the allocator’s locks fell from 43,429-49,770 to 2-5 out of about 768,000, and the spins from 617,603-683,545 to 2,211-15,351. What it cost: a push_off level on every allocator call (noff 4 in kwait), a scan of eight locks for every failed allocation, a short window in which a stolen batch is on no list, and memory that piles up on the hart that freed it.

And the lesson of the clinics: the one rule that matters for correctness is the lock order (never hold two kmem locks), and breaking it passed one full kalloctest before it deadlocked. The rule that the CPU number must not go stale cost nothing visible when broken, thanks to the per-list locks; it is kept because without those locks it would be a race rare enough that no test would catch it.