Step 1 of 18 · commit 1: Make walk stop at a leaf PTE at any level

A leaf, at any level

The story of this tour comes from one gdb-recorded run of supertest on the reference branch, 3 harts: pid 3 is supertest, pid 4 counts free pages, pid 5 runs the tests, and pids 6 and later are its children. Steps quote the harts and values gdb printed.

Commit 1 teaches the kernel’s software walk the hardware’s rule. SUPERPGSIZE is 1 << 21: the 21 virtual-address bits that a walk stopping at level 1 has not used. PTE_LEAF is the test from step 4 of the specification’s translation algorithm: a valid PTE with any of R, W, X set is a leaf. With all three clear it points to the next page-table page. The specification allows a leaf “at any level”; until now the kernel only ever wrote leaves at level 0, and only freewalk used the rule.

The rounding macros mirror PGROUNDUP and PGROUNDDOWN for 2 megabytes; the allocator and uvmalloc will need them.

Step 2 of 18 · commit 1: Make walk stop at a leaf PTE at any level

walklevel stops where the hardware stops

The loop is the old walk with two changes. It walks down only to the level the caller asks for (*level on entry: 0 for a page, 1 to find a superpage’s slot), and it stops at a valid leaf, returning that PTE and leaving its level in *level.

Without the stop, line 115 would take a superpage’s physical address for a page-table page and return a pointer into the user’s data: clinic 2 shows the kernel then treating bytes the user wrote as PTEs, until freewalk panics.

walk keeps its interface, so its many callers compile unchanged; but they now get a level-1 PTE back for a superpage address, and each one must be checked. mappages is already safe: a valid leaf where it wants to map a page makes it panic remap.

State: the moment shown is a later one in the recorded run, supertest’s pipe test. pipewrite holds pi->lock (noff 1, intena 1, since the system call had turned interrupts on) and copies the user’s bytes one at a time with copyin, which calls walkaddr, which calls this function.

Step 3 of 18 · commit 1: Make walk stop at a leaf PTE at any level

walkaddr adds the offset inside the superpage

walkaddr's callers (copyin, copyout, copyinstr, loadseg) treat its result as the physical address of the 4096-byte page holding va. For a superpage, PTE2PA(*pte) is the start of 2 megabytes, so the offset of va’s page inside them is added: PGROUNDDOWN(va) - SUPERPGROUNDDOWN(va).

gdb stopped here with va = 0x402000 (the pipe test’s source bytes, which start at 0x402f38), level 1, and pa = 0x87c00000 before the addition: the second superpage’s chunk. After the addition the copy reads from 0x87c02000. Forget the addition and every address in a superpage reads its first page: system calls would send the wrong 400 bytes.

Nothing else in copyin or copyout changes. They still copy at most 4096 bytes per step, even inside a superpage; correct and simple.

Step 4 of 18 · commit 2: Keep free memory in 2-megabyte chunks

Sixty-four chunks of RAM

RAM from KERNBASE to PHYSTOP is 64 aligned chunks of 2 megabytes, and the allocator now tracks each: FREE (whole and free), SUPER (whole, in use as a superpage) or SPLIT (512 pages, each free or in use). A split chunk has its own free list and count.

kinit marks the chunk that holds the kernel SPLIT (in this build end is 0x80021f88, so only chunk 0) and frees its pages above end as before: 478 pages. Chunks 1 to 63 need no work: a static array starts at 0, which is FREE. That also means boot no longer writes junk over 126 megabytes; pages are junk-filled when they are allocated or freed.

No lock is needed: hart 0 runs alone, harts 1 and 2 wait in main for started.

Step 5 of 18 · commit 2: Keep free memory in 2-megabyte chunks

kfree puts a page back on its own chunk's list

A freed page goes onto the list of the chunk it belongs to, CHUNK(pa), and the chunk’s count goes up. The count will matter in commit 3: a split chunk whose 512 pages are all free is as good as a free chunk.

The state check is new and cheap: a page can only be freed one at a time if its chunk is split. Freeing a page of a superpage (or of a free chunk) is always a bug, and the panic kfree: whole chunk catches it at the call that makes the mistake (clinic 4). The original allocator would have accepted it and leaked or double-allocated memory.

The second check narrows a hole that chunks open. Freeing a page twice already corrupts the original free list; here it can also make a chunk’s count reach 512 while one of its pages is still in use, and commit 3 would then hand that chunk out as a superpage over a live page. A count that would exceed 512 can only mean a page was freed twice, so kfree panics kfree: double free. It does not catch every double free: one in a chunk that still has a page in use can leave the count at exactly 512. Catching all of them would take a “free” bit per page.

The state shown is the reasoned one for a page freed by sbrk(-n) in a system call: kmem.lock held, noff 1, intena 1.

Step 6 of 18 · commit 2: Keep free memory in 2-megabyte chunks

kalloc takes a page from the lowest chunk it can

kalloc scans the 64 chunks for the lowest split chunk with a free page. Only if there is none does it split the lowest free chunk: split pushes the chunk’s 512 pages onto its list (top first, so the list starts at the chunk’s lowest page) and marks it SPLIT.

gdb caught the first splits of the run: pid 4, the child that counts free memory by calling sbrk(4096) until it fails, on hart 2, split chunk 1 when its heap reached 0x10f000: chunk 0’s free pages above the kernel were used up. Then chunk 2 at 0x30e000, chunk 3 at 0x50d000, and so on: about 2 megabytes of heap per chunk, because the low chunks fill up first.

This order is the allocator’s whole policy against fragmentation: small allocations pile up at the bottom of RAM, and the chunks at the top stay whole. Think question 3 tells what happens with an allocator that reuses the most recently freed page first: after a full usertests -q, only 52 of the 63 chunks were still available as superpages.

The scan costs up to 64 comparisons per kalloc, under kmem.lock with interrupts off: noff 1, intena 1, SIE 0, as gdb printed.

Step 7 of 18 · commit 2: Keep free memory in 2-megabyte chunks

Superpages come from the top

superalloc hands out the highest FREE chunk, the opposite end from kalloc, and superfree takes one back. Both fill the 2 megabytes with junk (5 on allocation, 1 on free), as kalloc and kfree do with a page; clinic 5 shows the 0x05 bytes catching a copy that was too short.

Their checks mirror kfree's: superfree panics on an unaligned address or one below end (clinic 1 hits it with 0x43f000), and on a chunk that is not SUPER.

After this commit the kernel boots and passes usertests -q: small allocations split chunks as needed, and nothing asks for a superpage yet.

Step 8 of 18 · commit 3: Let a split chunk become a superpage again

A split chunk can be whole again

Without this commit, every chunk that kalloc ever split would be lost to superpages for good. whole(c) also accepts a SPLIT chunk whose count is 512, and superalloc takes it by forgetting its list: no page of it is in use, so nothing else can be holding a pointer into that list.

This is the path the recorded run took every time. pid 4 had split chunks 1 to 63 while counting free memory and freed them all when it exited. When pid 5 asked for its two superpages, gdb printed superalloc takes chunk 63 state 2 nfree 512, then chunk 62: state 2 is SPLIT, with all 512 pages free.

superalloc runs inside sbrk, holding only kmem.lock: noff 1, intena 1.

Step 9 of 18 · commit 4: Map and unmap superpages

mapsuper writes one PTE at level 1

mapsuper asks walklevel for the level-1 slot (level = 1 on entry), allocating the level-1 page-table page if needed, and writes one leaf there. Two refusals:

• An unaligned va or pa is a kernel bug: panic. The hardware would turn an unaligned pa into page faults (clinic 1); catching it here is clearer.
• A valid PTE already in the slot means a level-0 page-table page is there (left behind by earlier pages in this 2 megabytes; xv6 never frees an empty one before exit) or a superpage is. Return -1, and the caller uses pages.

One cost of the second refusal (reasoned from the code, and observed in a run): after a demotion the level-0 page stays, so a later growth that covers that 2 megabytes again allocates a superpage, zeroes it, has mapsuper refuse it, frees it (2 more megabytes of junk fill) and then maps pages. Correct, but wasted work; a kernel could free an empty level-0 page, or check the slot first.

Recorded on hart 1 for pid 5’s sbrk(4 MiB): the leaf for 0x200000 at 0x80022008, entry 1 of the level-1 page at 0x80022000, is 0x21f80017 (PPN 0x87e00, V R W U); the one for 0x400000 at 0x80022010 is 0x21f00017. Each 2 megabytes of heap: one store. noff 0, SIE 1: interrupts are on during the system call outside any lock.

Step 10 of 18 · commit 4: Map and unmap superpages

uvmunmap frees a superpage whole

For a level-1 leaf the loop frees the chunk with superfree, clears the PTE, and advances a past the remaining 511 pages of the range. A range that covers only part of a superpage panics: freeing half of one is impossible, and the caller must split it first (commit 6). Clinic 3 shows what skipping it quietly leads to.

Recorded: pid 5 reaping its first fork child in kwait on hart 2, a = 0x200000, PTE at 0x8030a008, level 1. kwait holds wait_lock and the zombie’s p->lock while freeproc frees its memory: noff 2, intena 1. Inside superfree kmem.lock makes it noff 3; gdb printed that too.

superfree writes 2 megabytes of junk before it takes the lock, but with two spinlocks already held interrupts are off for all of it on this hart. The original kernel did the same total work page by page under the same locks.

Step 11 of 18 · commit 5: Copy superpages in fork

fork gives the child a superpage

At the first page of a parent’s superpage (level == 1 and i aligned), uvmcopy asks for a superpage, copies 2 megabytes, and maps it in the child with the parent’s flags (0xd7 here: V R W U A D; the parent had used it). On success i skips the other 511 pages.

Recorded on hart 1: pid 5 forking for fork copies superpages, i = 0x200000, source pa 0x87e00000, new mem 0x87a00000 (chunk 61). kfork holds the child’s np->lock from allocproc through the copy: noff 1 here, noff 2 inside superalloc (kmem.lock), intena 1. So the 2-megabyte memmove runs with interrupts off on this hart, like the original’s page copies.

The child’s level-1 slot is always empty here: its page table is new and filled in address order, so mapsuper can fail only for lack of a page-table page, and then the whole fork is undone.

Step 12 of 18 · commit 5: Copy superpages in fork

fork without a free superpage

When superalloc returns 0, the loop falls through to the page path. walklevel returns the same level-1 leaf for each of the 512 addresses, and line 381 moves pa to the piece that holds i. The child gets 512 ordinary pages with the same bytes; the parent keeps its superpage.

Recorded during fork without free superpages: gdb stopped here at i = 0x200000, 0x201000, …, and at the 512th piece 0x3ff000, each time with pa = 0x87e00000 before the addition. At that moment freesuper() was 0 while 14,145 pages were free: two helpers had interleaved their allocations so that no chunk was whole. Without this path, fork would fail on a machine with 55 megabytes free.

Step 13 of 18 · commit 6: Split a superpage when sbrk shrinks into it

Splitting a superpage keeps its bytes

demote replaces a level-1 leaf by a level-0 page-table page whose 512 entries map the same chunk piece by piece, with the same flags. Recorded at va 0x4fe000 (shrinktest cutting the second superpage): the leaf 0x21f000d7, the new page at 0x8030a000, and its entries l0[0] 0x21f000d7, l0[1] 0x21f004d7, l0[511] 0x21f7fcd7: PPNs 0x87c00, 0x87c01, 0x87dff.

Order matters a little: the level-0 page is complete before line 242 makes the level-1 PTE point at it, so no walk can see a half-built table. (None could anyway: only this process uses its page table, and it is here.) No sfence.vma either: the hart is on the kernel page table, and userret flushes before the process runs again.

supersplit (in kalloc.c) moves the chunk from SUPER to SPLIT with 0 free pages, under kmem.lock. The kalloc for the new page is the only thing that can fail. noff 0 and SIE 1 here: a plain system call, no lock held.