Extension labs · lab 14 · Memory · ★★★★☆

Superpages

Every user page in this tree is 4096 bytes, mapped by a PTE (page-table entry) in a level-0 page-table page that walk reaches through two higher levels. A process that grows its heap by 4 megabytes gets 1,024 PTEs, two level-0 page-table pages to hold them, and 1,024 translations for the hardware to cache. Yet the Sv39 hardware can map 2 megabytes with a single PTE one level higher up: a superpage (the RISC-V specification calls it a megapage).

In this lab you let sbrk use them. The idea is one sentence; the consequences reach into every corner of the memory system. Where does 2 megabytes of physically contiguous, aligned memory come from, when the allocator hands out single pages in no particular order, and what happens to that supply after the machine has been running for a while? Which page-table functions assume, without saying so, that every leaf sits at level 0, and what does each of them do when it meets one that does not? What does fork do with a superpage when no 2-megabyte chunk is free, and what does sbrk(-n) do when the new end falls in the middle of one?

The reference solution is nine small commits. With it, a 4-megabyte sbrk is mapped by two PTEs, a 64-megabyte heap needs 32 fewer page-table pages, and the allocator keeps all 63 chunks of RAM above the kernel available as superpages even after a full usertests run. You will also measure, honestly, what superpages do not buy on QEMU.

Read first: Tour 20: fork, Tour 24: The kernel page table and turning paging on, Tour 25: A user address space, Tour 26: sbrk, eager and lazy, and page faults, Tour 27: The physical page allocator, Tour 28: Crossing the user/kernel boundary in memory · The stacks of xv6, Locks and interrupt state

What this lab teaches

How the Sv39 walk decides that a PTE is a leaf, why a leaf may sit at any level, and what the hardware requires of a leaf above level 0 (and what it does when the requirement is not met).
Which of the kernel’s page-table functions silently assume that every leaf is at level 0, and what each of them does with a superpage when nobody tells it.
Why physically contiguous memory is a resource of its own, how an allocator can hand out both pages and 2-megabyte chunks, and what physical fragmentation looks like on a running system.
What sbrk must do when the new end falls inside a superpage, and what can go wrong.
What locks are held when fork and wait copy and free superpages, and why that rules out sleeping in the allocator.
What superpages buy (page-table pages, TLB reach on real hardware) and how to measure what they buy on an emulator.

The reference branch

ext/14-superpages in ShowMeTheStack/xv6-riscv-labs, branched from the frozen commit 06aad25; 9 commits.

git clone https://github.com/ShowMeTheStack/xv6-riscv-labs
cd xv6-riscv-labs
git checkout -b my-superpages 06aad25   # start your own
git diff 06aad25 origin/ext/14-superpages   # only when you want the answer

1. The spec

Behaviour. When a process grows its memory with an eager sbrk(n) (not sbrklazy), every 2-megabyte-aligned, 2-megabyte range that lies entirely inside the new memory is mapped by one leaf PTE in a level-1 page-table page: a superpage, backed by 2 megabytes of physical memory that is contiguous and 2-megabyte aligned. Whatever does not fit (the unaligned ends, or every range when no such physical memory is free) gets ordinary 4096-byte pages, as before.

fork gives the child a superpage of its own where it can, and otherwise the same bytes in 4096-byte pages. It must not fail just because no 2-megabyte chunk is free.
sbrk(-n) that ends in the middle of a superpage keeps the bytes below the new end.
Lazy growth (sbrklazy and vmfault) keeps using 4096-byte pages.
Two new system calls for testing: int pglevel(void *va) returns the level of the leaf PTE that maps va (0 for a page, 1 for a superpage, -1 if unmapped); int freesuper(void) returns how many superpages could be allocated right now.

What must not change. Every system call behaves as before: copyin, copyout and friends must work on superpages; out of memory must never panic the kernel; no page may leak. usertests -q must print ALL TESTS PASSED on 3 harts.

The test program, supertest, prints one line per check (two lines are information):

$ supertest
supertest: heap at 0x0000000000005000, superpages at 0x0000000000200000 and 0x0000000000400000
supertest: superpages: OK
supertest: every byte: OK
supertest: system calls: OK
supertest: fork copies superpages: OK
supertest: fragmented: 0 free superpages, 14145 free pages
supertest: fork without free superpages: OK
supertest: shrink splits: OK
supertest: unaligned growth uses pages: OK
supertest: lazy growth uses pages: OK
supertest: free pages 32459 before, 32459 after
supertest: free superpages 63 before, 63 after
supertest: no leaks: OK
supertest: ALL OK

superpages: grow the heap to a 2-megabyte boundary, then by 4 megabytes; pglevel must report level 1 at both 2-megabyte halves and at the last byte, level 0 for the padding below, and freesuper must have dropped by exactly 2.
every byte: all 4,194,304 bytes read as zero, then hold a pattern.
system calls: 400 bytes that cross a page boundary inside the second superpage go into a pipe with write and come back with read into the first superpage, across a page boundary there too.
fork copies superpages: the child sees level 1 and the same bytes; its writes do not reach the parent.
fork without free superpages: two helper processes take turns allocating 64 pages at a time until no superpage is free, then one exits. With about half of memory free but no whole 2-megabyte chunk, a fork must still work, with the child at level 0.
shrink splits: sbrk back to 2 pages below the 3-megabyte mark of the region: the first superpage stays, the second becomes pages, the bytes below the new end survive, and growing again gives zeroed memory.
unaligned growth, lazy growth: 2 megabytes of growth that starts one page past a boundary, and 2 megabytes of lazy growth, use level-0 pages.
no leaks: the tests run in a child process; free pages (counted with sbrk in yet another child) and free superpages are equal before and after.

2. Think first

Answer each question in your head (or on paper) before opening a hint. Hints get more specific; the reference answer comes last.

1What does the hardware do with a leaf at level 1?

Read the comment above walk and the PTE bits in kernel/riscv.h:395. walk always goes down to level 0, and every leaf this kernel writes sits there. But the hardware walk runs on its own, from satp, on every access that misses the TLB (translation lookaside buffer). What makes it stop at a PTE instead of descending, and could it stop at level 1? If it does, how big is the region that one PTE maps, where does the low part of the physical address come from, and what must be true of the physical page number in that PTE? Commit to answers before the hints.

Check yourself

1solidDecode the bits

On the reference branch, gdb stopped in mapsuper right after it wrote the leaf for user address 0x200000 into the level-1 page-table page: 0x21f80017. Decode it.

Value: 0x21f80017

V (bit 0)R, W, X (bits 1-3)U (bit 4)A and D (bits 6, 7)Physical address it mapsIs the PPN 2-megabyte aligned?

2warm-upType a number

A process’s heap grows by exactly 4 megabytes, starting at a 2-megabyte boundary. With 4096-byte pages, how many level-0 page-table pages does this growth need (assuming none of them existed)? With superpages, the answer is 0.

decimal, 0x hex or 0b binary

2Where do 2 megabytes of contiguous memory come from?

Read kalloc and kfree. A superpage needs 2 megabytes of physical memory that is contiguous and starts at a multiple of 2 megabytes. Could you build one from 512 calls to kalloc? If not, what must the allocator know that it does not know today, and how will it keep 4096-byte allocations (page tables, kernel stacks, pipes, the pages of every small process) working at the same time? Think about where the kernel itself sits in RAM, too.

Check yourself

1warm-upType a number

RAM runs from KERNBASE (0x80000000) to PHYSTOP (0x88000000). The kernel image ends at 0x80021f88. How many whole, 2-megabyte-aligned chunks of RAM lie entirely above the kernel?

kernel/memlayout.h

40// the kernel expects there to be RAM
41// for use by the kernel and user pages
42// from physical address 0x80000000 to PHYSTOP.
43#define KERNBASE 0x80000000L
44#define PHYSTOP  (KERNBASE + 128 * 1024 * 1024)

decimal, 0x hex or 0b binary

2solidChoose one

A learner builds superalloc as “call kalloc 512 times and keep the pages if they happen to be consecutive and the first is 2-megabyte aligned”. Why is this a poor design in this kernel?

The free list returns pages in the order they were freed; after the system has run for a while, 512 consecutive aligned pages in a row almost never come out, so it would almost always fail.kalloc cannot be called 512 times while holding a lock.The hardware does not require physical contiguity for superpages.It is fine; kalloc returns increasing addresses.

3Which chunk should a small allocation use?

With chunks in place, every kalloc has a choice: which split chunk to take a page from, and, when none has one, which free chunk to split. And when the 512 pages of a split chunk are all free again, should it become a superpage again? Consider a design with one free list for all pages of all split chunks, used like the original (last freed, first allocated), that turns a chunk back into a superpage when its 512 pages are free. Where would long-lived small allocations (page-table pages, kernel stacks, pipe buffers) land under that rule? Then predict what supertest sees with that design, on a fresh boot. One fact you need: before its tests, supertest counts free pages in a child process that calls sbrk(4096) until it fails, then exits; its exit frees its data pages first and its page-table pages last.

Check yourself

1solidChoose one

Right after fragment() in supertest, 14,145 pages are free but freesuper() returns 0. What is true?

Every split chunk still has at least one page in use, so none can be handed out whole; the free memory is scattered over many chunks.The free pages are page-table pages of the exited process.The kernel reserves the free memory for small allocations.freesuper only counts chunks that were never split.

4Which page-table functions assume every leaf is at level 0?

Go through vm.c function by function: walk, walkaddr, mappages, uvmunmap, uvmalloc, uvmdealloc, uvmcopy, uvmfree, freewalk, copyout, copyin, ismapped, vmfault. For each, imagine it handed an address inside a superpage. Which do something wrong today, and what exactly? Start with walk: what does its loop do when the level-1 PTE is valid?

The reference design

walk is the root of it. Its loop descends through any valid PTE. At a superpage leaf it would take the superpage’s first 4096 bytes of user data as a level-0 table and return a pointer into them. Everything built on walk then works on garbage that the user wrote; clinic 2 shows what happened when that was left in. The reference walklevel stops at a leaf, like the hardware, and says which level it stopped at; walk keeps its interface.

Then, for a superpage address:

function	with the leaf-stopping walk, function unchanged	needs
`walkaddr`	returns the superpage’s first page for every address in it	add the offset of va’s 4096-byte piece
`mappages`	finds the level-1 leaf valid and panics `remap`	nothing: mapping a page over a superpage is a bug
`uvmunmap`	`kfree`s the first page only, as if it were a page	free the superpage whole, skip its 512 pages; refuse to free part of one
`uvmcopy`	copies the first 4096 bytes 512 times	copy the superpage, or its 512 pieces
`uvmdealloc`	cuts a superpage in two	split it first (question 5)
`uvmalloc`	—	where the superpages are made
`freewalk`	panics `freewalk: leaf` on any leaf	nothing: no leaf may be left
`uvmclear`	would clear `PTE_U` on the whole superpage	nothing: it is only used on `exec`’s guard page, and the guard page and stack are 2 pages, never a superpage
`copyin`, `copyout`, `ismapped`, `vmfault`	correct once `walkaddr` and `walk` are	nothing

freewalk is the instructive one. Its test (pte & (PTE_R|PTE_W|PTE_X)) == 0 is exactly the hardware’s leaf rule, applied at every level, and its panic is the safety net: if uvmunmap ever leaves a superpage mapped, the process cannot be freed. Lazy allocation stays as it is: vmfault maps one page at a time and refuses addresses that are mapped, including those inside a superpage.

5What happens when sbrk shrinks into the middle of a superpage?

A process has a superpage at 0x400000 and calls sbrk so that its new size is 0x4fe000. The pages from 0x4fe000 up must be freed; the 1,016 KiB below must keep their bytes. One PTE cannot map half of 2 megabytes. What has to happen to the page table, what has to happen in the allocator, and what can fail? And what would happen if uvmdealloc left the superpage alone because it could not free all of it?

Check yourself

1solidTrue or false, and why

True or false: demoting a superpage requires copying its 2 megabytes into 512 newly allocated pages.

TrueFalse

Why?

Copying is needed so that the old superpage can be freed with superfree.The hardware requires level-0 pages to be allocated by kalloc.The 512 new level-0 PTEs point at the 512 pieces of the same physical chunk; only one page (the new page-table page) is allocated.

2solidChoose one

On the reference branch, under memory pressure, sbrk(-4096) returns -1. What happened?

The process has no superpages; shrinking never fails for pages.uvmunmap panicked and the system call returned -1.sbrk can never shrink a superpage, so it always fails there.The new end falls inside a superpage, and demote could not allocate the level-0 page-table page it needs; nothing was freed.

6What does fork do with a superpage, and under which locks?

kfork calls uvmcopy while holding the child’s np->lock (taken in allocproc). The parent has a superpage. Should the child get a superpage too, and what if none is free (remember the fragmented case of question 3)? Then: which spinlocks are held while 2 megabytes are being copied, what does that mean for interrupts on this hart, and which functions may therefore be called?

Check yourself

1solidFill in the machine state

The shell’s child supertest (a process with two superpages) calls fork. uvmcopy reaches the first superpage and calls superalloc, which acquires kmem.lock. Fill in this hart’s state at that moment.

kernel/proc.c

259kfork(void)
260{
int i, pid;
struct proc *np;
struct proc *p = myproc();
264
// Allocate process.
if ((np = allocproc()) == 0) {
  return -1;
}
269
// Copy user memory from parent to child.
if (uvmcopy(p->pagetable, np->pagetable, p->sz) < 0) {
  freeproc(np);
  release(&np->lock);
  return -1;
}

Privilege modeActive stackPage table (satp)Interrupts (sstatus.SIE)noffintena

7What does all this buy on QEMU?

Superpages save page-table pages and, on real hardware, TLB entries and walk steps. Before you measure, predict: for a 64-megabyte heap, how many page-table pages are saved? And will a loop that loads one byte from each of the 16,384 pages, many times over, run measurably faster on QEMU with superpages? Think about what QEMU caches when it translates a guest address.

Check yourself

1warm-upType a number

A process maps 64 megabytes of heap, 2-megabyte aligned. How many level-0 page-table pages does it need with superpages, compared to pages? Give the difference.

decimal, 0x hex or 0b binary

3. Build it

Start.

git checkout -b my-superpages 06aad25

Write the test first: user/supertest.c with the checks from the spec, and add $U/_supertest\ to UPROGS. You will need the two test system calls early (add them to syscall.h, syscall.c, sysproc.c, usys.pl and user.h; pglevel can return 0 for every mapped page until superpages exist).

Milestones, in an order that keeps the system bootable and usertests -q passing after each one.

A walk that stops at a leaf. SUPERPGSIZE, the rounding macros and a leaf test in riscv.h; a walk that reports the level where it stopped; walkaddr adding the offset. Nothing maps a superpage yet. Test: usertests -q.
Chunks in the allocator. Chunk states, per-chunk free lists, superalloc and superfree, kalloc splitting chunks lowest first. Test: usertests -q (it exhausts memory more than once, a good test of splitting).
Whole again. A split chunk with all 512 pages free counts as whole.
Map and unmap. A function that installs a level-1 leaf; uvmunmap freeing it whole.
fork. uvmcopy with both cases.
Demotion. Split a superpage in uvmdealloc; let the allocator know.
Flip the switch in uvmalloc. Now everything above is exercised. Test: supertest, usertests -q, supertest again (it must still find 63 free superpages).

Debugging advice. For breakpoints at boot, start QEMU halted with make qemu-gdb (it waits for gdb on the port it prints); for later events, attaching to a running QEMU also works.

The kernel is built with -O: gdb often says <optimized out> for locals, and an error in a breakpoint’s commands aborts the whole script. Use info args and info locals, which print <optimized out> without failing.
To see a mapping, stop in your mapping function and p/x *pte; decode it by hand (PPN = value >> 10, flags = low 10 bits) and check that the PPN’s low 9 bits are 0.
QEMU can tell you why a translation failed: run it with -d guest_errors. A misaligned superpage is reported as get_physical_address: PPN bits in PTE is misaligned.
Print the chunk states: p kmem.state and p kmem.nfree in gdb show at a glance which chunks are split and how full they are.
panic: freewalk: leaf means a leaf survived uvmunmap: break on panic, go up to freewalk and print i: in a level-1 page, index i is the 2-megabyte region i << 21.

4. Debugging clinic

Each of these bugs was put into the reference solution on purpose and run on three harts. The symptom is exactly what happened. Try to explain it before revealing why.

1The superpage’s PPN is counted in 2-megabyte units

A natural misconception: “a superpage number counts superpages”. In mapsuper:

-  *pte = PA2PTE(pa) | perm | PTE_V;
+  *pte = ((pa >> 21) << 10) | perm | PTE_V; // PPN of a superpage

What happened when we ran it

$ supertest
supertest: heap at 0x0000000000005000, superpages at 0x0000000000200000 and 0x0000000000400000
supertest: superpages: OK
usertrap(): unexpected scause 0xd pid=5
            sepc=0x258 stval=0x200000
panic: superfree

# another run of the same kernel, QEMU started with -d guest_errors:
get_physical_address: PPN bits in PTE is misaligned: addr: 0x80022008 pte: 0x000000000010fc17
usertrap(): unexpected scause 0xd pid=5

# a third run, gdb, breakpoint on panic:
== hart 2 pid 3 supertest noff 2 intena 1 sie 0 sp 0x3fffff9e50
[...]
#1  0x0000000080000dbc in superfree (pa=<optimized out>) at kernel/kalloc.c:146
#2  0x00000000800017e0 in uvmunmap (pagetable=0x80153000, va=va@entry=0, npages=npages@entry=1536, do_free=do_free@entry=1) at kernel/vm.c:283
[...]
#6  0x00000000800028f4 in kwait (addr=20348) at kernel/proc.c:400
[...]
uvmunmap a 0x200000 pte 0x10fc17 ppn 0x43f

2walk does not stop at a leaf

Everything as in the reference except the leaf test in walklevel, which a learner who thinks “only level 0 has leaves” leaves out:

     if (*pte & PTE_V) {
-      if (PTE_LEAF(*pte))
-        return pte; // a superpage: no page-table page below
       pagetable = (pagetable_t)PTE2PA(*pte);

What happened when we ran it

$ supertest
supertest: heap at 0x0000000000005000, superpages at 0x0000000000200000 and 0x0000000000400000
supertest: superpages: FAIL
supertest: every byte: OK
supertest: system calls: FAIL
supertest: fork copies superpages: FAIL
supertest: fragmented: 0 free superpages, 15159 free pages
supertest: fork without free superpages: FAIL
supertest: shrink splits: FAIL
supertest: unaligned growth uses pages: OK
supertest: lazy growth uses pages: OK
panic: freewalk: leaf

# gdb, breakpoint on panic:
== hart 1 pid 3 supertest noff 2 intena 1 sie 0 sp 0x3fffff9e90
#0  panic (s=s@entry=0x800081e0 "freewalk: leaf") at kernel/printk.c:139
#1  0x00000000800019e4 in freewalk (pagetable=0x80022000) at kernel/vm.c:371
#2  0x0000000080001a02 in freewalk (pagetable=pagetable@entry=0x80153000) at kernel/vm.c:368
#3  0x0000000080001a30 in uvmfree (pagetable=pagetable@entry=0x80153000, sz=sz@entry=6291456) at kernel/vm.c:384
[...]
#6  0x00000000800028ea in kwait (addr=20348) at kernel/proc.c:400

3Shrinking leaves the superpage alone instead of splitting it

No demotion in uvmdealloc, and uvmunmap quietly skips a superpage it cannot free whole, which looks harmless (“free what you can”):

   if (PGROUNDUP(newsz) < PGROUNDUP(oldsz)) {
-    // a superpage that straddles the new end must be split first.
-    if ((PGROUNDUP(newsz) % SUPERPGSIZE) != 0 &&
-        demote(pagetable, PGROUNDUP(newsz)) != 0)
-      return oldsz;
     int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;

       if ((a % SUPERPGSIZE) != 0 || a + SUPERPGSIZE > va + npages * PGSIZE)
-        panic("uvmunmap: part of a superpage");
+        continue; // can't free part of it: leave it alone

What happened when we ran it

$ supertest
supertest: heap at 0x0000000000005000, superpages at 0x0000000000200000 and 0x0000000000400000
supertest: superpages: OK
supertest: every byte: OK
supertest: system calls: OK
supertest: fork copies superpages: OK
supertest: fragmented: 0 free superpages, 14145 free pages
supertest: fork without free superpages: OK
panic: mappages: remap

# gdb, breakpoint on panic:
== hart 2 pid 5 supertest noff 0 intena 1 sie 1 sp 0x3fffff7ec0
#0  panic (s=s@entry=0x80008178 "mappages: remap") at kernel/printk.c:139
#1  0x000000008000151e in mappages (pagetable=pagetable@entry=0x80153000, va=va@entry=5234688, size=size@entry=4096, pa=<optimized out>, pa@entry=2150670336, perm=perm@entry=22) at kernel/vm.c:188
#2  0x00000000800018da in uvmalloc (pagetable=0x80153000, oldsz=5234688, newsz=6291456, xperm=xperm@entry=4) at kernel/vm.c:326
#3  0x00000000800022be in growproc (n=1056768) at kernel/proc.c:246

4uvmunmap treats a superpage as a page

The superpage branch is missing from uvmunmap; with the new walk, a superpage address gets the level-1 leaf, and the old code frees PTE2PA(*pte) as one page:

-    if (level == 1) {
-      if ((a % SUPERPGSIZE) != 0 || a + SUPERPGSIZE > va + npages * PGSIZE)
-        panic("uvmunmap: part of a superpage");
-      if (do_free)
-        superfree((void *)PTE2PA(*pte));
-      *pte = 0;
-      a += SUPERPGSIZE - PGSIZE; // skip the rest of it
-      continue;
-    }
     if (do_free) {
       uint64 pa = PTE2PA(*pte);
       kfree((void *)pa);

What happened when we ran it

$ supertest
supertest: heap at 0x0000000000005000, superpages at 0x0000000000200000 and 0x0000000000400000
supertest: superpages: OK
supertest: every byte: OK
supertest: system calls: OK
panic: kfree: whole chunk

# gdb, breakpoint on panic:
== hart 2 pid 5 supertest noff 3 intena 1 sie 0 sp 0x3fffff7e70
#0  panic (s=s@entry=0x80008040 "kfree: whole chunk") at kernel/printk.c:139
#1  0x0000000080000b44 in kfree (pa=0x87a00000) at kernel/kalloc.c:77
#2  0x00000000800017c8 in uvmunmap (pagetable=0x8030e000, va=va@entry=0, npages=npages@entry=1536, do_free=do_free@entry=1) at kernel/vm.c:281
[...]
#6  0x0000000080002898 in kwait (addr=20316) at kernel/proc.c:400
[...]
uvmunmap va 0x0 npages 1536 a 0x200000 pte 0x21e800d7

5fork copies only the first 4096 bytes of a superpage

A leftover from the page loop in uvmcopy's superpage branch:

-      memmove(mem, (char *)pa, SUPERPGSIZE);
+      memmove(mem, (char *)pa, PGSIZE);

What happened when we ran it

$ supertest
supertest: heap at 0x0000000000005000, superpages at 0x0000000000200000 and 0x0000000000400000
supertest: superpages: OK
supertest: every byte: OK
supertest: system calls: OK
supertest: fork copies superpages: FAIL
supertest: fragmented: 0 free superpages, 14145 free pages
supertest: fork without free superpages: OK
supertest: shrink splits: OK
supertest: unaligned growth uses pages: OK
supertest: lazy growth uses pages: OK
supertest: free pages 32459 before, 32459 after
supertest: free superpages 63 before, 63 after
supertest: no leaks: OK
supertest: SOME TESTS FAILED
$ usertests -q
usertests starting
[...]
ALL TESTS PASSED

# a copy of supertest that prints what the child saw:
child: pglevel 1 1
child: first difference at offset 0x1000: 0x5, expected 0x1

6Demotion points every piece at the first page

The offset is forgotten when filling the new level-0 page:

   for (int i = 0; i < 512; i++)
-    l0[i] = PA2PTE(pa + i * PGSIZE) | PTE_FLAGS(*pte);
+    l0[i] = PA2PTE(pa) | PTE_FLAGS(*pte);

What happened when we ran it

$ supertest
[...]
supertest: fork without free superpages: OK
supertest: shrink splits: FAIL
supertest: unaligned growth uses pages: OK
supertest: lazy growth uses pages: OK
scause=0xd sepc=0x80000c5e stval=0x0
panic: kerneltrap

# gdb, same run:
### demote va 0x4fe000 pte 0x21f000d7 l0[0] 0x21f000d7 l0[1] 0x21f000d7 l0[511] 0x21f000d7
[...]
### panic: kerneltrap
== hart 1 pid 11 supertest noff 1 intena 1 sie 0 sp 0x3fffff7dc0
[...]
$1 = {0 <repeats 62 times>, 510, 0}
$2 = {0x0 <repeats 64 times>}

5. The reference solution

Take the guided tour through the reference solution, one commit at a time, with the machine state at every step:

Open the reveal tour →

Or read the commits

1731360 Make walk stop at a leaf PTE at any level
kernel/defs.h
@@ -163,8 +163,9 @@ int uvmcopy(pagetable_t, pagetable_t, uint64);
163163void uvmfree(pagetable_t, uint64);
164164void uvmunmap(pagetable_t, uint64, uint64, int);
165165void uvmclear(pagetable_t, uint64);
166166pte_t * walk(pagetable_t, uint64, int);
167pte_t * walklevel(pagetable_t, uint64, int, int *);
167168uint64 walkaddr(pagetable_t, uint64);
168169int copyout(pagetable_t, uint64, uint64, char *, uint64);
169170int copyin(pagetable_t, uint64, char *, uint64, uint64);
170171int copyinstr(pagetable_t, uint64, char *, uint64, uint64);
kernel/riscv.h
@@ -391,14 +391,24 @@ typedef uint64 *pagetable_t; // 512 PTEs
391391
392392#define PGROUNDUP(sz) (((sz) + PGSIZE - 1) & ~(PGSIZE - 1))
393393#define PGROUNDDOWN(a) (((a)) & ~(PGSIZE - 1))
394394
395// a superpage (a "megapage" in the RISC-V spec) is mapped by one
396// leaf PTE in a level-1 page-table page: 512 pages, 2 megabytes.
397#define SUPERPGSIZE (1L << 21)
398#define SUPERPGROUNDUP(sz) (((sz) + SUPERPGSIZE - 1) & ~(SUPERPGSIZE - 1))
399#define SUPERPGROUNDDOWN(a) (((a)) & ~(SUPERPGSIZE - 1))
400
395401#define PTE_V (1L << 0) // valid
396402#define PTE_R (1L << 1)
397403#define PTE_W (1L << 2)
398404#define PTE_X (1L << 3)
399405#define PTE_U (1L << 4) // user can access
400406
407// a valid PTE with any of R, W, X set is a leaf, at any level;
408// with all three clear it points to the next page-table page.
409#define PTE_LEAF(pte) ((pte) & (PTE_R | PTE_W | PTE_X))
410
401411// shift a physical address to the right place for a PTE.
402412#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
403413
404414#define PTE2PA(pte) (((pte) >> 10) << 12)
kernel/vm.c
@@ -94,26 +94,44 @@ kvminithart()
9494// 30..38 -- 9 bits of level-2 index.
9595// 21..29 -- 9 bits of level-1 index.
9696// 12..20 -- 9 bits of level-0 index.
9797// 0..11 -- 12 bits of byte offset within the page.
98//
99// On entry *level is the level to walk down to (0 for a
100// 4096-byte page, 1 for a superpage). Like the hardware, the
101// walk stops early at a leaf; *level then says where it stopped.
98102pte_t *
99walk(pagetable_t pagetable, uint64 va, int alloc)
103walklevel(pagetable_t pagetable, uint64 va, int alloc, int *level)
100104{
105 int stop = *level;
106
101107 if (va >= MAXVA)
102108 panic("walk");
103109
104 for (int level = 2; level > 0; level--) {
105 pte_t *pte = &pagetable[PX(level, va)];
110 for (*level = 2; *level > stop; (*level)--) {
111 pte_t *pte = &pagetable[PX(*level, va)];
106112 if (*pte & PTE_V) {
113 if (PTE_LEAF(*pte))
114 return pte; // a superpage: no page-table page below
107115 pagetable = (pagetable_t)PTE2PA(*pte);
108116 } else {
109117 if (!alloc || (pagetable = (pde_t *)kalloc()) == 0)
110118 return 0;
111119 memset(pagetable, 0, PGSIZE);
112120 *pte = PA2PTE(pagetable) | PTE_V;
113121 }
114122 }
115 return &pagetable[PX(0, va)];
123 return &pagetable[PX(stop, va)];
124}
125
126// Return the address of the leaf PTE for va: a level-0 PTE,
127// or a level-1 PTE if va lies in a superpage.
128pte_t *
129walk(pagetable_t pagetable, uint64 va, int alloc)
130{
131 int level = 0;
132
133 return walklevel(pagetable, va, alloc, &level);
116134}
117135
118136// Look up a virtual address, return the physical address,
119137// or 0 if not mapped.
@@ -122,20 +140,23 @@ uint64
122140walkaddr(pagetable_t pagetable, uint64 va)
123141{
124142 pte_t *pte;
125143 uint64 pa;
144 int level = 0;
126145
127146 if (va >= MAXVA)
128147 return 0;
129148
130 pte = walk(pagetable, va, 0);
149 pte = walklevel(pagetable, va, 0, &level);
131150 if (pte == 0)
132151 return 0;
133152 if ((*pte & PTE_V) == 0)
134153 return 0;
135154 if ((*pte & PTE_U) == 0)
136155 return 0;
137156 pa = PTE2PA(*pte);
157 if (level == 1) // the 4096-byte piece of the superpage that holds va
158 pa += PGROUNDDOWN(va) - SUPERPGROUNDDOWN(va);
138159 return pa;
139160}
140161
141162// Create PTEs for virtual addresses starting at va that refer to
145ad81 Keep free memory in 2-megabyte chunks
kernel/defs.h
@@ -59,8 +59,10 @@ void ireclaim(int);
5959// kalloc.c
6060void* kalloc(void);
6161void kfree(void *);
6262void kinit(void);
63void* superalloc(void);
64void superfree(void *);
6365
6466// log.c
6567void initlog(int, struct superblock*);
6668void log_write(struct buf*);
kernel/kalloc.c
@@ -1,7 +1,8 @@
11// Physical memory allocator, for user processes,
22// kernel stacks, page-table pages,
3// and pipe buffers. Allocates whole 4096-byte pages.
3// and pipe buffers. Allocates whole 4096-byte pages,
4// and 2-megabyte superpages for user memory.
45
56#include "types.h"
67#include "param.h"
78#include "memlayout.h"
@@ -17,18 +18,32 @@ extern char end[]; // first address after kernel.
1718struct run {
1819 struct run *next;
1920};
2021
22// RAM is divided into 2-megabyte-aligned chunks, each in one
23// of three states.
24#define NCHUNK ((PHYSTOP - KERNBASE) / SUPERPGSIZE)
25#define CHUNK(pa) (((uint64)(pa) - KERNBASE) / SUPERPGSIZE)
26#define FREE 0 // whole and free
27#define SUPER 1 // whole, in use as a superpage
28#define SPLIT 2 // split into 512 pages, each free or in use
29
2130struct {
2231 struct spinlock lock;
23 struct run *freelist;
32 char state[NCHUNK];
33 struct run *freelist[NCHUNK]; // a split chunk's free pages
34 int nfree[NCHUNK]; // how many there are
2435} kmem;
2536
2637void
2738kinit()
2839{
2940 initlock(&kmem.lock, "kmem");
30 freerange(end, (void *)PHYSTOP);
41 // the chunk that holds the kernel is split from the start;
42 // every chunk above it starts whole and free.
43 for (int c = 0; c < CHUNK(SUPERPGROUNDUP((uint64)end)); c++)
44 kmem.state[c] = SPLIT;
45 freerange(end, (void *)SUPERPGROUNDUP((uint64)end));
3146}
3247
3348void
3449freerange(void *pa_start, void *pa_end)
@@ -46,8 +61,9 @@ freerange(void *pa_start, void *pa_end)
4661void
4762kfree(void *pa)
4863{
4964 struct run *r;
65 int c = CHUNK(pa);
5066
5167 if (((uint64)pa % PGSIZE) != 0 || (char *)pa < end || (uint64)pa >= PHYSTOP)
5268 panic("kfree");
5369
@@ -56,27 +72,109 @@ kfree(void *pa)
5672
5773 r = (struct run *)pa;
5874
5975 acquire(&kmem.lock);
60 r->next = kmem.freelist;
61 kmem.freelist = r;
76 if (kmem.state[c] != SPLIT)
77 panic("kfree: whole chunk");
78 if (kmem.nfree[c] >= SUPERPGSIZE / PGSIZE)
79 panic("kfree: double free"); // more free pages than the chunk has
80 r->next = kmem.freelist[c];
81 kmem.freelist[c] = r;
82 kmem.nfree[c]++;
6283 release(&kmem.lock);
6384}
6485
86// Make free chunk c 512 free pages.
87// Caller holds kmem.lock.
88static void
89split(int c)
90{
91 char *start = (char *)(KERNBASE + (uint64)c * SUPERPGSIZE);
92 struct run *r;
93
94 for (char *p = start + SUPERPGSIZE - PGSIZE; p >= start; p -= PGSIZE) {
95 r = (struct run *)p;
96 r->next = kmem.freelist[c];
97 kmem.freelist[c] = r;
98 }
99 kmem.nfree[c] = SUPERPGSIZE / PGSIZE;
100 kmem.state[c] = SPLIT;
101}
102
65103// Allocate one 4096-byte page of physical memory.
66104// Returns a pointer that the kernel can use.
67105// Returns 0 if the memory cannot be allocated.
68106void *
69107kalloc(void)
70108{
71 struct run *r;
109 struct run *r = 0;
110 int c;
72111
73112 acquire(&kmem.lock);
74 r = kmem.freelist;
75 if (r)
76 kmem.freelist = r->next;
113 // take a page from the lowest split chunk that has one,
114 // so that the high chunks stay whole as long as possible.
115 for (c = 0; c < NCHUNK; c++)
116 if (kmem.state[c] == SPLIT && kmem.nfree[c] > 0)
117 break;
118 if (c == NCHUNK) {
119 // none: split the lowest free chunk.
120 for (c = 0; c < NCHUNK; c++)
121 if (kmem.state[c] == FREE)
122 break;
123 if (c < NCHUNK)
124 split(c);
125 }
126 if (c < NCHUNK) {
127 r = kmem.freelist[c];
128 kmem.freelist[c] = r->next;
129 kmem.nfree[c]--;
130 }
77131 release(&kmem.lock);
78132
79133 if (r)
80134 memset((char *)r, 5, PGSIZE); // fill with junk
81135 return (void *)r;
82136}
137
138// Free a superpage that superalloc() returned.
139void
140superfree(void *pa)
141{
142 int c = CHUNK(pa);
143
144 if (((uint64)pa % SUPERPGSIZE) != 0 || (char *)pa < end ||
145 (uint64)pa >= PHYSTOP)
146 panic("superfree");
147
148 // Fill with junk to catch dangling refs.
149 memset(pa, 1, SUPERPGSIZE);
150
151 acquire(&kmem.lock);
152 if (kmem.state[c] != SUPER)
153 panic("superfree: not a superpage");
154 kmem.state[c] = FREE;
155 release(&kmem.lock);
156}
157
158// Allocate one 2-megabyte, 2-megabyte-aligned chunk of
159// physical memory, the highest free one.
160// Returns 0 if no chunk is free.
161void *
162superalloc(void)
163{
164 int c;
165 char *pa = 0;
166
167 acquire(&kmem.lock);
168 for (c = NCHUNK - 1; c >= 0; c--) {
169 if (kmem.state[c] == FREE) {
170 kmem.state[c] = SUPER;
171 pa = (char *)(KERNBASE + (uint64)c * SUPERPGSIZE);
172 break;
173 }
174 }
175 release(&kmem.lock);
176
177 if (pa)
178 memset(pa, 5, SUPERPGSIZE); // fill with junk
179 return (void *)pa;
180}
a54f033 Let a split chunk become a superpage again
kernel/kalloc.c
@@ -154,8 +154,17 @@ superfree(void *pa)
154154 kmem.state[c] = FREE;
155155 release(&kmem.lock);
156156}
157157
158// Can chunk c become a superpage? Caller holds kmem.lock.
159static int
160whole(int c)
161{
162 // a split chunk whose 512 pages are all free counts too.
163 return kmem.state[c] == FREE ||
164 (kmem.state[c] == SPLIT && kmem.nfree[c] == SUPERPGSIZE / PGSIZE);
165}
166
158167// Allocate one 2-megabyte, 2-megabyte-aligned chunk of
159168// physical memory, the highest free one.
160169// Returns 0 if no chunk is free.
161170void *
@@ -165,10 +174,12 @@ superalloc(void)
165174 char *pa = 0;
166175
167176 acquire(&kmem.lock);
168177 for (c = NCHUNK - 1; c >= 0; c--) {
169 if (kmem.state[c] == FREE) {
178 if (whole(c)) {
170179 kmem.state[c] = SUPER;
180 kmem.freelist[c] = 0; // its pages are no longer free pages
181 kmem.nfree[c] = 0;
171182 pa = (char *)(KERNBASE + (uint64)c * SUPERPGSIZE);
172183 break;
173184 }
174185 }
200401b Map and unmap superpages
kernel/defs.h
@@ -157,8 +157,9 @@ void uartputc_sync(int);
157157void kvminit(void);
158158void kvminithart(void);
159159void kvmmap(pagetable_t, uint64, uint64, uint64, int);
160160int mappages(pagetable_t, uint64, uint64, uint64, int);
161int mapsuper(pagetable_t, uint64, uint64, int);
161162pagetable_t uvmcreate(void);
162163uint64 uvmalloc(pagetable_t, uint64, uint64, int);
163164uint64 uvmdealloc(pagetable_t, uint64, uint64);
164165int uvmcopy(pagetable_t, pagetable_t, uint64);
kernel/vm.c
@@ -194,8 +194,30 @@ mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
194194 }
195195 return 0;
196196}
197197
198// Map the 2-megabyte superpage at physical address pa at va
199// with one leaf PTE in a level-1 page-table page. Both must be
200// 2-megabyte aligned. Returns 0 on success, -1 if a level-0
201// page-table page is already in the way or walklevel() couldn't
202// allocate a needed page-table page.
203int
204mapsuper(pagetable_t pagetable, uint64 va, uint64 pa, int perm)
205{
206 pte_t *pte;
207 int level = 1;
208
209 if ((va % SUPERPGSIZE) != 0 || (pa % SUPERPGSIZE) != 0)
210 panic("mapsuper: not aligned");
211
212 if ((pte = walklevel(pagetable, va, 1, &level)) == 0)
213 return -1;
214 if (*pte & PTE_V)
215 return -1;
216 *pte = PA2PTE(pa) | perm | PTE_V;
217 return 0;
218}
219
198220// create an empty user page table.
199221// returns 0 if out of memory.
200222pagetable_t
201223uvmcreate()
@@ -209,23 +231,35 @@ uvmcreate()
209231}
210232
211233// Remove npages of mappings starting from va. va must be
212234// page-aligned. It's OK if the mappings don't exist.
235// A superpage must be removed whole.
213236// Optionally free the physical memory.
214237void
215238uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
216239{
217240 uint64 a;
218241 pte_t *pte;
242 int level;
219243
220244 if ((va % PGSIZE) != 0)
221245 panic("uvmunmap: not aligned");
222246
223247 for (a = va; a < va + npages * PGSIZE; a += PGSIZE) {
224 if ((pte = walk(pagetable, a, 0)) == 0) // leaf page table entry allocated?
248 level = 0;
249 if ((pte = walklevel(pagetable, a, 0, &level)) == 0) // leaf page table entry allocated?
225250 continue;
226251 if ((*pte & PTE_V) == 0) // has physical page been allocated?
227252 continue;
253 if (level == 1) {
254 if ((a % SUPERPGSIZE) != 0 || a + SUPERPGSIZE > va + npages * PGSIZE)
255 panic("uvmunmap: part of a superpage");
256 if (do_free)
257 superfree((void *)PTE2PA(*pte));
258 *pte = 0;
259 a += SUPERPGSIZE - PGSIZE; // skip the rest of it
260 continue;
261 }
228262 if (do_free) {
229263 uint64 pa = PTE2PA(*pte);
230264 kfree((void *)pa);
231265 }
6791c75 Copy superpages in fork
kernel/vm.c
@@ -346,9 +346,10 @@ uvmfree(pagetable_t pagetable, uint64 sz)
346346
347347// Given a parent process's page table, copy
348348// its memory into a child's page table.
349349// Copies both the page table and the
350// physical memory.
350// physical memory. A superpage is copied into a
351// superpage if one is free, else into 512 pages.
351352// returns 0 on success, -1 on failure.
352353// frees any allocated pages on failure.
353354int
354355uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
@@ -356,16 +357,29 @@ uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
356357 pte_t *pte;
357358 uint64 pa, i;
358359 uint flags;
359360 char *mem;
361 int level;
360362
361363 for (i = 0; i < sz; i += PGSIZE) {
362 if ((pte = walk(old, i, 0)) == 0)
364 level = 0;
365 if ((pte = walklevel(old, i, 0, &level)) == 0)
363366 continue; // page table entry hasn't been allocated
364367 if ((*pte & PTE_V) == 0)
365368 continue; // physical page hasn't been allocated
366369 pa = PTE2PA(*pte);
367370 flags = PTE_FLAGS(*pte);
371 if (level == 1 && (i % SUPERPGSIZE) == 0 && (mem = superalloc()) != 0) {
372 memmove(mem, (char *)pa, SUPERPGSIZE);
373 if (mapsuper(new, i, (uint64)mem, flags) != 0) {
374 superfree(mem);
375 goto err;
376 }
377 i += SUPERPGSIZE - PGSIZE;
378 continue;
379 }
380 if (level == 1) // copy the 4096-byte piece that holds i
381 pa += i - SUPERPGROUNDDOWN(i);
368382 if ((mem = kalloc()) == 0)
369383 goto err;
370384 memmove(mem, (char *)pa, PGSIZE);
371385 if (mappages(new, i, PGSIZE, (uint64)mem, flags) != 0) {
1eeeed9 Split a superpage when sbrk shrinks into it
kernel/defs.h
@@ -61,8 +61,9 @@ void* kalloc(void);
6161void kfree(void *);
6262void kinit(void);
6363void* superalloc(void);
6464void superfree(void *);
65void supersplit(void *);
6566
6667// log.c
6768void initlog(int, struct superblock*);
6869void log_write(struct buf*);
@@ -158,8 +159,9 @@ void kvminit(void);
158159void kvminithart(void);
159160void kvmmap(pagetable_t, uint64, uint64, uint64, int);
160161int mappages(pagetable_t, uint64, uint64, uint64, int);
161162int mapsuper(pagetable_t, uint64, uint64, int);
163int demote(pagetable_t, uint64);
162164pagetable_t uvmcreate(void);
163165uint64 uvmalloc(pagetable_t, uint64, uint64, int);
164166uint64 uvmdealloc(pagetable_t, uint64, uint64);
165167int uvmcopy(pagetable_t, pagetable_t, uint64);
kernel/kalloc.c
@@ -154,8 +154,24 @@ superfree(void *pa)
154154 kmem.state[c] = FREE;
155155 release(&kmem.lock);
156156}
157157
158// A superpage in use becomes 512 pages in use: from now
159// on they are freed one at a time with kfree().
160void
161supersplit(void *pa)
162{
163 int c = CHUNK(pa);
164
165 acquire(&kmem.lock);
166 if (kmem.state[c] != SUPER)
167 panic("supersplit");
168 kmem.state[c] = SPLIT;
169 kmem.freelist[c] = 0;
170 kmem.nfree[c] = 0;
171 release(&kmem.lock);
172}
173
158174// Can chunk c become a superpage? Caller holds kmem.lock.
159175static int
160176whole(int c)
161177{
kernel/proc.c
@@ -247,8 +247,10 @@ growproc(int n)
247247 return -1;
248248 }
249249 } else if (n < 0) {
250250 sz = uvmdealloc(p->pagetable, sz, sz + n);
251 if (sz == p->sz && sz + n < sz)
252 return -1; // couldn't split a superpage
251253 }
252254 p->sz = sz;
253255 return 0;
254256}
kernel/vm.c
@@ -216,8 +216,34 @@ mapsuper(pagetable_t pagetable, uint64 va, uint64 pa, int perm)
216216 *pte = PA2PTE(pa) | perm | PTE_V;
217217 return 0;
218218}
219219
220// If va lies in a superpage, split it: a new level-0
221// page-table page maps the same 2 megabytes of physical
222// memory as 512 pages with the same permissions, so the
223// data stays where it is. Returns 0 on success (or if va is
224// not in a superpage), -1 if out of memory.
225int
226demote(pagetable_t pagetable, uint64 va)
227{
228 pte_t *pte;
229 pagetable_t l0;
230 uint64 pa;
231 int level = 0;
232
233 pte = walklevel(pagetable, va, 0, &level);
234 if (pte == 0 || (*pte & PTE_V) == 0 || level != 1)
235 return 0;
236 if ((l0 = (pagetable_t)kalloc()) == 0)
237 return -1;
238 pa = PTE2PA(*pte);
239 for (int i = 0; i < 512; i++)
240 l0[i] = PA2PTE(pa + i * PGSIZE) | PTE_FLAGS(*pte);
241 supersplit((void *)pa);
242 *pte = PA2PTE(l0) | PTE_V;
243 return 0;
244}
245
220246// create an empty user page table.
221247// returns 0 if out of memory.
222248pagetable_t
223249uvmcreate()
@@ -298,16 +324,21 @@ uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
298324
299325// Deallocate user pages to bring the process size from oldsz to
300326// newsz. oldsz and newsz need not be page-aligned, nor does newsz
301327// need to be less than oldsz. oldsz can be larger than the actual
302// process size. Returns the new process size.
328// process size. Returns the new process size, which is oldsz
329// if a superpage that newsz cuts could not be split.
303330uint64
304331uvmdealloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
305332{
306333 if (newsz >= oldsz)
307334 return oldsz;
308335
309336 if (PGROUNDUP(newsz) < PGROUNDUP(oldsz)) {
337 // a superpage that straddles the new end must be split first.
338 if ((PGROUNDUP(newsz) % SUPERPGSIZE) != 0 &&
339 demote(pagetable, PGROUNDUP(newsz)) != 0)
340 return oldsz;
310341 int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;
311342 uvmunmap(pagetable, PGROUNDUP(newsz), npages, 1);
312343 }
313344
ee28838 Map sbrk growth with superpages
kernel/vm.c
@@ -294,8 +294,10 @@ uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
294294}
295295
296296// Allocate PTEs and physical memory to grow a process from oldsz to
297297// newsz, which need not be page aligned. Returns new size or 0 on error.
298// Every 2-megabyte-aligned 2 megabytes of the new range gets a
299// superpage if one is free.
298300uint64
299301uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
300302{
301303 char *mem;
@@ -305,8 +307,17 @@ uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
305307 return oldsz;
306308
307309 oldsz = PGROUNDUP(oldsz);
308310 for (a = oldsz; a < newsz; a += PGSIZE) {
311 if ((a % SUPERPGSIZE) == 0 && a + SUPERPGSIZE <= newsz &&
312 (mem = superalloc()) != 0) {
313 memset(mem, 0, SUPERPGSIZE);
314 if (mapsuper(pagetable, a, (uint64)mem, PTE_R | PTE_U | xperm) == 0) {
315 a += SUPERPGSIZE - PGSIZE;
316 continue;
317 }
318 superfree(mem); // no room for a superpage here: use pages
319 }
309320 mem = kalloc();
310321 if (mem == 0) {
311322 uvmdealloc(pagetable, a, oldsz);
312323 return 0;
e4e4aa3 Add pglevel and freesuper for testing
kernel/defs.h
@@ -62,8 +62,9 @@ void kfree(void *);
6262void kinit(void);
6363void* superalloc(void);
6464void superfree(void *);
6565void supersplit(void *);
66int nfreesuper(void);
6667
6768// log.c
6869void initlog(int, struct superblock*);
6970void log_write(struct buf*);
kernel/kalloc.c
@@ -204,4 +204,18 @@ superalloc(void)
204204 if (pa)
205205 memset(pa, 5, SUPERPGSIZE); // fill with junk
206206 return (void *)pa;
207207}
208
209// How many superpages could superalloc() hand out now?
210int
211nfreesuper(void)
212{
213 int n = 0;
214
215 acquire(&kmem.lock);
216 for (int c = 0; c < NCHUNK; c++)
217 if (whole(c))
218 n++;
219 release(&kmem.lock);
220 return n;
221}
kernel/syscall.c
@@ -102,8 +102,10 @@ extern uint64 sys_unlink(void);
102102extern uint64 sys_link(void);
103103extern uint64 sys_mkdir(void);
104104extern uint64 sys_close(void);
105105extern uint64 sys_sync(void);
106extern uint64 sys_pglevel(void);
107extern uint64 sys_freesuper(void);
106108
107109// An array mapping syscall numbers from syscall.h
108110// to the function that handles the system call.
109111static uint64 (*syscalls[])(void) = {
@@ -129,8 +131,10 @@ static uint64 (*syscalls[])(void) = {
129131 [SYS_link] = sys_link,
130132 [SYS_mkdir] = sys_mkdir,
131133 [SYS_close] = sys_close,
132134 [SYS_sync] = sys_sync,
135 [SYS_pglevel] = sys_pglevel,
136 [SYS_freesuper] = sys_freesuper,
133137 // clang-format on
134138};
135139
136140void
kernel/syscall.h
@@ -20,4 +20,6 @@
2020#define SYS_link 19
2121#define SYS_mkdir 20
2222#define SYS_close 21
2323#define SYS_sync 22
24#define SYS_pglevel 23
25#define SYS_freesuper 24
kernel/sysproc.c
@@ -109,4 +109,29 @@ sys_uptime(void)
109109 xticks = ticks;
110110 release(&tickslock);
111111 return xticks;
112112}
113
114// return the level of the leaf PTE that maps user address va:
115// 0 for a 4096-byte page, 1 for a superpage, -1 if unmapped.
116uint64
117sys_pglevel(void)
118{
119 uint64 va;
120 pte_t *pte;
121 int level = 0;
122
123 argaddr(0, &va);
124 if (va >= MAXVA)
125 return -1;
126 pte = walklevel(myproc()->pagetable, va, 0, &level);
127 if (pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_U) == 0)
128 return -1;
129 return level;
130}
131
132// return how many superpages superalloc() could hand out now.
133uint64
134sys_freesuper(void)
135{
136 return nfreesuper();
137}
user/user.h
@@ -24,8 +24,10 @@ int getpid(void);
2424char *sys_sbrk(int, int);
2525int pause(int);
2626int uptime(void);
2727int sync(void);
28int pglevel(void *);
29int freesuper(void);
2830
2931// ulib.c
3032int stat(const char *, struct stat *);
3133char *strcpy(char *, const char *);
user/usys.pl
@@ -42,4 +42,6 @@ entry("getpid");
4242entry("sbrk");
4343entry("pause");
4444entry("uptime");
4545entry("sync");
46entry("pglevel");
47entry("freesuper");
d5fd431 Add supertest
Makefile
@@ -149,8 +149,9 @@ UPROGS=\
149149 $U/_logstress\
150150 $U/_forphan\
151151 $U/_dorphan\
152152 $U/_sync\
153 $U/_supertest\
153154
154155fs.img: mkfs/mkfs README $(UPROGS)
155156 mkfs/mkfs fs.img README $(UPROGS)
156157
user/supertest.c
@@ -0,0 +1,301 @@
1//
2// tests for superpages.
3// each test prints "supertest: <name>: OK" or "... FAIL".
4//
5
6#include "kernel/types.h"
7#include "kernel/riscv.h"
8#include "user/user.h"
9
10#define MB (1024 * 1024)
11#define BATCH (64 * PGSIZE) // fragment: 64 pages per turn
12
13int failed;
14char *base; // 4 megabytes of heap, 2-megabyte aligned
15char *heap0; // the break before the test grew the heap
16
17void
18result(char *name, int ok)
19{
20 printf("supertest: %s: %s\n", name, ok ? "OK" : "FAIL");
21 if (!ok)
22 failed = 1;
23}
24
25// wait for one child; return 1 if it exited with status 0.
26int
27childok(void)
28{
29 int xstatus;
30
31 if (wait(&xstatus) < 0)
32 return 0;
33 return xstatus == 0;
34}
35
36// count free pages by allocating them all with sbrk, in a child:
37// the page-table pages that the count needs are freed when it
38// exits, so they cannot pin 2-megabyte chunks.
39int
40countfree(void)
41{
42 int n = 0;
43 int pid = fork();
44
45 if (pid < 0)
46 return -1;
47 if (pid == 0) {
48 while (sbrk(PGSIZE) != SBRK_ERROR)
49 n++;
50 exit(n);
51 }
52 wait(&n);
53 return n;
54}
55
56// the byte that offset i of the region should hold.
57char
58pattern(uint64 i)
59{
60 return (i * 131 + (i >> 12)) & 0xff;
61}
62
63// do bytes [from, to) of the region hold the pattern?
64int
65checkpattern(uint64 from, uint64 to)
66{
67 for (uint64 i = from; i < to; i++)
68 if (base[i] != pattern(i))
69 return 0;
70 return 1;
71}
72
73// grow the heap to a 2-megabyte boundary, then by 4 megabytes:
74// two superpages.
75void
76supertest(void)
77{
78 int free0;
79 char *pad;
80
81 heap0 = sbrk(0);
82 pad = sbrk(SUPERPGROUNDUP((uint64)heap0) - (uint64)heap0);
83 free0 = freesuper();
84 base = sbrk(4 * MB);
85 if (pad == SBRK_ERROR || base == SBRK_ERROR) {
86 printf("supertest: sbrk failed\n");
87 exit(1);
88 }
89 printf("supertest: heap at %p, superpages at %p and %p\n", heap0, base,
90 base + 2 * MB);
91 result("superpages",
92 pglevel(base) == 1 && pglevel(base + 2 * MB) == 1 &&
93 pglevel(base + 4 * MB - 1) == 1 && pglevel(heap0) == 0 &&
94 freesuper() == free0 - 2);
95}
96
97// read and write every byte of the two superpages.
98void
99bytetest(void)
100{
101 int ok = 1;
102
103 for (uint64 i = 0; i < 4 * MB; i++)
104 if (base[i] != 0)
105 ok = 0;
106 for (uint64 i = 0; i < 4 * MB; i++)
107 base[i] = pattern(i);
108 result("every byte", ok && checkpattern(0, 4 * MB));
109}
110
111// the kernel reads and writes superpages too (copyin, copyout):
112// send 400 bytes that straddle a page boundary in the second
113// superpage through a pipe, and read them back into the first
114// superpage, across a page boundary there too.
115void
116syscalltest(void)
117{
118 uint64 from = 2 * MB + 3 * PGSIZE - 200;
119 uint64 to = 1 * MB + 5 * PGSIZE - 100;
120 int fds[2], ok;
121
122 if (pipe(fds) < 0) {
123 result("system calls", 0);
124 return;
125 }
126 ok = write(fds[1], base + from, 400) == 400 &&
127 read(fds[0], base + to, 400) == 400;
128 for (int i = 0; i < 400; i++)
129 if (base[to + i] != pattern(from + i))
130 ok = 0;
131 for (uint64 i = to; i < to + 400; i++) // put the pattern back
132 base[i] = pattern(i);
133 close(fds[0]);
134 close(fds[1]);
135 result("system calls", ok);
136}
137
138// fork: the child must see the same bytes in pages of the given
139// level, and its writes must not reach the parent.
140int
141forkcheck(int level)
142{
143 int pid = fork();
144
145 if (pid < 0) {
146 printf("supertest: fork failed\n");
147 return 0;
148 }
149 if (pid == 0) {
150 if (pglevel(base) != level || pglevel(base + 2 * MB) != level)
151 exit(1);
152 if (!checkpattern(0, 4 * MB))
153 exit(2);
154 for (uint64 i = 0; i < 4 * MB; i += 997)
155 base[i] = ~pattern(i);
156 exit(0);
157 }
158 int ok = childok();
159 return ok && checkpattern(0, 4 * MB);
160}
161
162// fill memory so that every 2-megabyte chunk holds pages of two
163// processes, then let one of them exit: half of memory is free,
164// but not one superpage. Returns the pid of the one left (it
165// exits when its pipe closes), or -1.
166int
167fragment(int *keep)
168{
169 int cmd[2][2], ack[2], pid[2];
170 char c;
171
172 if (pipe(ack) < 0)
173 return -1;
174 for (int k = 0; k < 2; k++) {
175 if (pipe(cmd[k]) < 0)
176 return -1;
177 if ((pid[k] = fork()) == 0) {
178 sbrk(-(sbrk(0) - heap0)); // give back the inherited superpages
179 close(cmd[k][1]);
180 while (read(cmd[k][0], &c, 1) == 1) {
181 if (c == 'q')
182 exit(0);
183 c = sbrk(BATCH) == SBRK_ERROR ? 'n' : 'y';
184 write(ack[1], &c, 1);
185 }
186 exit(0);
187 }
188 close(cmd[k][0]);
189 }
190 // take turns until no superpage is left.
191 for (int k = 0; freesuper() > 0; k = 1 - k) {
192 write(cmd[k][1], "a", 1);
193 if (read(ack[0], &c, 1) != 1 || c != 'y')
194 break;
195 }
196 write(cmd[1][1], "q", 1);
197 wait(0);
198 close(cmd[1][1]);
199 close(ack[0]);
200 close(ack[1]);
201 *keep = cmd[0][1];
202 return pid[0];
203}
204
205// with no superpage free, fork must still copy a superpage, into
206// 512 pages.
207void
208demotefork(void)
209{
210 int keep, pid;
211
212 if ((pid = fragment(&keep)) < 0) {
213 result("fork without free superpages", 0);
214 return;
215 }
216 int n = freesuper();
217 int npages = countfree();
218 printf("supertest: fragmented: %d free superpages, %d free pages\n", n,
219 npages);
220 int ok = forkcheck(0);
221 close(keep); // the other process exits
222 wait(0);
223 result("fork without free superpages", n == 0 && ok);
224}
225
226// shrink into the middle of the second superpage: it must be split,
227// and the bytes below the new break kept.
228void
229shrinktest(void)
230{
231 uint64 cut = 3 * MB - 2 * PGSIZE; // new end, inside superpage 2
232 int ok;
233
234 if (sbrk(-(4 * MB - cut)) == SBRK_ERROR) {
235 result("shrink splits", 0);
236 return;
237 }
238 ok = pglevel(base) == 1 && pglevel(base + 2 * MB) == 0 &&
239 pglevel(base + cut - 1) == 0 && pglevel(base + cut) == -1 &&
240 checkpattern(0, cut);
241 // grow back: the new pages must be zero.
242 if (sbrk(4 * MB - cut) == SBRK_ERROR)
243 ok = 0;
244 for (uint64 i = cut; ok && i < 4 * MB; i++)
245 if (base[i] != 0)
246 ok = 0;
247 result("shrink splits", ok);
248}
249
250// growth that is not 2-megabyte aligned, and lazy growth, use
251// 4096-byte pages.
252void
253smalltest(void)
254{
255 char *top = sbrk(0), *p;
256 int ok;
257
258 sbrk(SUPERPGROUNDUP((uint64)top) - (uint64)top + PGSIZE);
259 p = sbrk(2 * MB); // starts one page past a boundary
260 ok = p != SBRK_ERROR && pglevel(p) == 0 && pglevel(p + 2 * MB - 1) == 0;
261 sbrk(-(sbrk(0) - top));
262 result("unaligned growth uses pages", ok);
263
264 sbrk(SUPERPGROUNDUP((uint64)top) - (uint64)top);
265 p = sbrklazy(2 * MB); // 2-megabyte aligned, but lazy
266 ok = p != SBRK_ERROR && pglevel(p) == -1;
267 for (uint64 i = 0; i < 2 * MB; i += PGSIZE)
268 p[i] = 1;
269 ok = ok && pglevel(p) == 0 && pglevel(p + 2 * MB - 1) == 0;
270 sbrk(-(sbrk(0) - top));
271 result("lazy growth uses pages", ok);
272}
273
274int
275main(int argc, char *argv[])
276{
277 int super0 = freesuper();
278 int free0 = countfree();
279
280 // run the tests in a child, so that every page they use,
281 // page-table pages included, is free again when it exits.
282 if (fork() == 0) {
283 supertest();
284 bytetest();
285 syscalltest();
286 result("fork copies superpages", forkcheck(1));
287 demotefork();
288 shrinktest();
289 smalltest();
290 exit(failed);
291 }
292 failed = !childok();
293
294 int super1 = freesuper();
295 int free1 = countfree();
296 printf("supertest: free pages %d before, %d after\n", free0, free1);
297 printf("supertest: free superpages %d before, %d after\n", super0, super1);
298 result("no leaks", free0 == free1 && super0 == super1);
299 printf("supertest: %s\n", failed ? "SOME TESTS FAILED" : "ALL OK");
300 exit(failed);
301}

6. Verify and measure

On the branch (ext/14-superpages, 9 commits), built with the project toolchain and run on 3 harts (-smp 3 -m 128M), in one boot:

$ supertest
supertest: heap at 0x0000000000005000, superpages at 0x0000000000200000 and 0x0000000000400000
supertest: superpages: OK
supertest: every byte: OK
supertest: system calls: OK
supertest: fork copies superpages: OK
supertest: fragmented: 0 free superpages, 14145 free pages
supertest: fork without free superpages: OK
supertest: shrink splits: OK
supertest: unaligned growth uses pages: OK
supertest: lazy growth uses pages: OK
supertest: free pages 32459 before, 32459 after
supertest: free superpages 63 before, 63 after
supertest: no leaks: OK
supertest: ALL OK
$ usertests -q
usertests starting
test copyin: OK
test copyout: OK
[...]
test MAXVAplus: usertrap(): unexpected scause 0xf pid=6526
[...]
ALL TESTS PASSED
$ supertest
[...]
supertest: free pages 32459 before, 32459 after
supertest: free superpages 63 before, 63 after
supertest: no leaks: OK
supertest: ALL OK

Every line of supertest is checked by the program itself; the two information lines are printed for the reader. The usertrap() lines inside usertests are the expected kills of tests that touch memory they must not, as on the original kernel. usertests exercises the superpage paths (from reading its code; we did not trace them during the run): sbrkmuch grows to 100 megabytes, which can take up to 49 superpages, shrinks by one page, which demotes the last one, and grows back; sbrkfail runs memory out with ten processes. And supertest after it still finds all 63 superpages free: nothing usertests did left a stray page in a chunk.

Every commit was built on its own, and usertests -q passed on 3 harts at every commit of the branch.

Page-table pages. A measurement program (not on the branch) aligned its heap, grew it by 64 megabytes either in one sbrk (superpages on the branch) or in 64 steps of 1 megabyte (no step contains a whole aligned 2 megabytes, so pages), and counted free pages before and after with helper processes forked while it was still small:

kernel	grown in one `sbrk`	grown in 1 MiB steps
reference branch	16,352 pages counted as used	16,384
original 06aad25	16,384	16,384

Both rows include the same distortion: the counting helper itself needs fewer page-table pages when less memory is free, which cancels the 32 level-0 pages of the page-only case. The difference is what matters, and it is exactly 32 pages (128 KiB): one level-0 page per 2 megabytes, present with pages, absent with superpages. Same numbers in every run on each kernel (six on the branch, three on the original).

Fragmentation. Free superpages reported by supertest (before its own tests run):

allocator	fresh boot	after `usertests -q`
reference (lowest split chunk first)	63	63
one free list, last freed first	63, but `supertest` got no superpage at all	52

With one free list the pages freed last by supertest’s counting child (its page-table pages, one in nearly every chunk) were the first ones handed out again, so every chunk had a page in use by the time the test asked for a superpage.

Time, honestly. The same program timed four things: six runs on the branch (three of them without its final one-line check in kfree), three on the original kernel (ticks are tenths of a second):

	branch, superpages	branch, pages	original
one load per page, 16,384 pages × 20,000	44-55	44-59	48-59
every word, 64 MiB × 400	55-105	52-110	64-100
`fork` + `exit` + `wait` of the 64 MiB process × 20	19-20	20	19-20
grow 64 MiB	1-3	1-3	1-3

No difference stands out from the noise. The loop with one load per page is the one that would show TLB reach on hardware: 16,384 pages are more than typical TLBs hold as 4096-byte entries, and 32 superpage entries would cover them. QEMU does not show it; the explanation is in QEMU’s source, not in a timing run: in QEMU 10.2.1, riscv_cpu_tlb_fill in target/riscv/cpu_helper.c installs every translation with tlb_size = TARGET_PAGE_SIZE (only PMP can make it smaller), so its software TLB holds one entry per 4096-byte guest page whatever the guest’s leaf size, and a superpage saves QEMU at most a shorter walk on a miss. Measure superpages on real hardware; on QEMU, count page-table pages.

7. Go further

Transparent promotion. When a process has touched all 512 pages of an aligned 2 megabytes (lazily, or after a demotion), copy them into a free chunk and replace the level-0 page by one leaf. It teaches when the kernel may move a process’s memory under it, and why the TLB must then be flushed on every hart that might use the old entries.
Compaction. When no chunk is whole, move the few pages in use out of an almost-free chunk. Page-table pages and kernel stacks cannot be moved this way, which is why real kernels allocate them from different chunks than user pages (Linux’s migrate types).
Superpages for exec. kexec already gets them for any segment that spans an aligned 2 megabytes; link a program whose code is that large and check with pglevel. Think about what PTE_X on a superpage means for fence.i.
Gigapages. A level-2 leaf maps 1 gigabyte. This machine has 128 megabytes, but the kernel’s own direct map could use level-1 leaves: map RAM in kvmmake with superpages and count the page-table pages saved (the direct map of RAM alone uses one level-0 page per 2 megabytes, 64 of them).
Shared superpages with copy-on-write. Combine with lab 11: what does a store fault on a shared superpage copy, 4096 bytes after a demotion or all 2 megabytes?