Step 1 of 18 · commit 1: Reserve a stack region below the trapframe

Three constants describe the new layout

The story of this tour was recorded with gdb on the finished branch, three harts: the machine boots, the shell runs growstack, whose children recurse, fork, read into untouched stack pages, overflow and collide, and later usertests exectest. Where a step shows code from an early commit, the machine state comes from those runs of the finished branch, where the same lines are executing.

Commit 1 only names things. The stack region is the top USERSTACK pages below TRAPFRAME: USTACKTOP is its top (exclusive), USTACKBASE its lowest page, and MAXHEAP, one page lower still, is the highest end the heap may have. The page between MAXHEAP and USTACKBASE belongs to nobody: the guard.

USERSTACK is still 1 here, so the region is the single page 0x3fffffd000 and MAXHEAP is 0x3fffffc000. Nothing uses the region yet. Commit 6 raises USERSTACK to 64, and the same three lines then give 0x3ffffbe000 and 0x3ffffbd000.

Why right under the trapframe? It is the highest address user code could use: the trapframe and the trampoline above it are mapped without PTE_U, so the stack’s top page sits directly under a page the program cannot touch. And it is as far as possible from the heap, which starts near 0 and grows up. Because these are constants, every later question (“is this a stack address?”, “which pages might the stack have?”) is answered the same way for every process, with no new field in struct proc.

Step 2 of 18 · commit 1: Reserve a stack region below the trapframe

The eager heap stops below the guard

growproc used to refuse growth past TRAPFRAME; now the ceiling is MAXHEAP. If it did not, uvmalloc would map pages over the guard and then over the stack region, and the two would meet.

gdb stopped at the refusal (return -1 on line 244, address 0x80001c70 in this build) in the collide child, which had already grown its heap lazily to the ceiling: sz = 0x3ffffbd000, n = 0x1000, sz + n = 0x3ffffbe000, which is USTACKBASE. One page more would have been the guard. MAXHEAP itself is an allowed end: the heap’s last byte is then 0x3ffffbcfff.

No lock is taken: p->sz and the page table are private to the process (the comment in struct proc says so, kernel/proc.h:95), and a process has one thread, which is here. Interrupts are on, because this is a system call, and usertrap turned them on before calling syscall.

Step 3 of 18 · commit 1: Reserve a stack region below the trapframe

So does the lazy heap

sbrklazy never calls growproc: it only moves p->sz, and vmfault allocates pages when they are touched. So it needs its own ceiling, the same MAXHEAP. This path matters most here, because it can reach the ceiling without any memory: the collide check moves its heap end from 0x3000 to 0x3ffffbd000 (about 256 GiB) in 1 GiB steps, allocating nothing.

gdb stopped at the refusal with addr (the old end) = 0x3ffffbd000 and addr + n = 0x3ffffbd001: sbrklazy(1) at the ceiling, refused. (The earlier test on line 58 catches a wrap-around of addr + n; the ceiling test needs it, since a wrapped sum would be small.)

Keeping p->sz at or below MAXHEAP is what makes the guard safe from the heap’s side: vmfault gives out heap pages only below p->sz, so the guard page can never become a heap page, however the heap grows.

Step 4 of 18 · commit 1: Reserve a stack region below the trapframe

The one test that knew the old ceiling

lazy_sbrk walks the heap lazily up toward MAXVA in 1 GiB steps, then asks for exactly the rest up to the ceiling, then one eager page, and checks that one more byte fails both ways. It encoded the ceiling as TRAPFRAME. The property it tests (the heap can grow lazily to its ceiling and not one byte further) is still the right one; only the ceiling moved, so the change is TRAPFRAME → MAXHEAP in the two places that name it.

The loop above the change still works unchanged: it stops once the heap end passes MAXVA - 1 GiB = 0x3fc0000000, which is below MAXHEAP (0x3ffffbd000 with 64 stack pages, 0x3fffffc000 at this commit). A stack region bigger than 1 GiB would break that loop; 256 KiB is far from it.

This is the first of two changes to usertests in this lab. Lab 10 made the same one for the same reason: anything fixed at the top of the address space lowers the heap’s ceiling.

Step 5 of 18 · commit 2: Free the stack region with the page table

Every teardown frees the stack region

uvmfree frees [0, sz) and then hands the page-table pages to freewalk, which panics if it finds a page still mapped. Stack pages live above sz. One line before uvmfree unmaps and frees the whole region; uvmunmap skips pages that are not mapped, so it works for a stack of 1 page or 64.

proc_freepagetable is the right place because every teardown goes through it: freeproc when a parent reaps a child, kexec when it drops the old image, and kexec's error path when it drops a half-built new one. At this commit the region is always empty, so the line does nothing yet, and usertests -q passes.

gdb stopped here as growstack (pid 3) reaped its deep child (pid 4): 18 stack pages mapped, 0x3ffffec000 to 0x3fffffd000, all freed by this line. Two spinlocks are held: kwait took wait_lock and then the child’s p->lock (kernel/proc.c:376, kernel/proc.c:384) before calling freeproc, so noff is 2 and interrupts are off; intena 1 records that they were on in the system call. Each kfree takes and releases kmem.lock inside that (noff 3 for a moment).

Step 6 of 18 · commit 3: Copy the stack region in fork

uvmcopy learns a range

uvmcopy copied [0, sz). It now copies [start, end), which needs only three changes: the parameters, the loop’s start, and the error path, which unmaps (and frees) just what this call copied, [start, i). start must be page-aligned, because the loop steps by whole pages from it.

The loop already skipped pages that are not mapped (lines 308-311). That is what makes a copy of the whole 64-page region cheap: only the pages the stack has grown into are copied, and the rest cost one walk each. gdb stopped on the call for the stack region in the fork check: pid 5, at the bottom of its 65 frames (user sp 0x3ffffecad0), had 18 stack pages, 0x3ffffec000 to 0x3fffffd000. A fork from the shell copies one.

Each copy keeps the parent’s PTE flags (line 313), so the child’s stack pages are writable and user-accessible like the parent’s.

Step 7 of 18 · commit 3: Copy the stack region in fork

fork copies two ranges, and sets sz first

kfork copies the image and heap, [0, p->sz), and then the stack region. The child inherits exactly the parent’s stack pages; pages the parent never touched stay unmapped in the child too, and the child grows them on demand, as the parent would have.

np->sz = p->sz moved above the copies. If the first copy succeeds and the second runs out of memory, freeproc frees the child’s page table with proc_freepagetable and np->sz: with the old order np->sz would still be 0, the image pages would stay mapped, and freewalk would panic. The second uvmcopy has already cleaned up after itself, and proc_freepagetable frees the stack region whatever sz is.

Without the second copy (clinic 1) nothing fails here. The child returns from fork with an empty stack region, vmfault gives it zero pages, and it runs on with zeros in place of its saved registers.

Step 8 of 18 · commit 4: Let vmfault grow the stack into its region

vmfault learns the stack region

The whole fault-side change is one condition. An address at or above p->sz used to be refused at once; now it is refused only if it is also outside [USTACKBASE, USTACKTOP). Everything below is shared with the lazy heap and already right for a stack page: refuse a page that is mapped, allocate, zero, map PTE_W | PTE_U | PTE_R.

gdb, in the deep child: the store sd a2,-1080(s0) (0x36a; with s0 = sp + 1088 it is sp + 8) at the start of a new dive frame faulted with scause 15, stval = 0x3fffffce28 (user sp 0x3fffffce20). The page 0x3fffffc000 is above p->sz (0x3000) and inside the region, so vmfault went on to kalloc. gdb logged the next faults at 0x3fffffbd28, 0x3fffffac28, 0x3fffff9f68, … one per page (its breakpoint recorded only the first five); the counting kernel counted 17 in all.

A fault from user mode reaches here with interrupts off and no lock held: usertrap calls intr_on only for system calls. Nothing here sleeps, so that is fine. After the return, the hart retries the store, which now succeeds. The PTEs of these pages read …0d7 at exit: V R W U plus A and D, set by the hardware when the program used them.

Step 9 of 18 · commit 4: Let vmfault grow the stack into its region

The kernel grows the stack too, without a trap

copyout did not change, and it did not need to. When the page it must write is not mapped, it calls vmfault itself (line 358). So the same condition from the previous step decides for kernel copies too.

gdb, in the read child: piperead copies one byte at a time with copyout (kernel/pipe.c:133), into a buffer in pages the child never touched. vmfault grew 0x3fffffa000, and 50 bytes later 0x3fffffb000. No trap was involved: the hart never tried to use those addresses; the kernel looked them up in the page table. When the child exited, these two pages’ PTEs read …457 and …857 (flags 0x57: A set, but no D), unlike the pages the program wrote itself (0xd7). The kernel wrote them through their physical addresses, so the hardware never saw a store through these PTEs.

piperead holds pi->lock here (noff 1, interrupts off). Growing a page under a spinlock is legal because it never sleeps: kalloc and, if a page-table page is needed, walk's kalloc only spin on kmem.lock. (In lab 12 the same path could read from disk, and that made every copy under a lock a hazard.)

Step 10 of 18 · commit 4: Let vmfault grow the stack into its region

An address in lazy_copy is now a stack page

lazy_copy checks that read and write refuse addresses that are not the process’s memory. Two of them, 0x3fffffc000 and 0x3fffffd000, were simply “high and unused”. From this commit on, vmfault grows any page in the stack region, and 0x3fffffd000 is that region’s only page (USERSTACK is still 1); at commit 6 it becomes the stack page every process has. A read into it would succeed, and the test would fail even though nothing is wrong. 0x3fffffc000 is still refused at this commit (it is MAXHEAP, the guard), but it joins the region at commit 6, when the region grows to 64 pages, so it has to go too.

The replacements keep the test’s intent with the new layout: MAXHEAP - PGSIZE, the highest page the heap could have but this process does not, and MAXHEAP, the guard. Both must still fail: the first is heap address space this process has not claimed (it is above p->sz), and the second can never belong to anyone. The other four addresses (the trapframe, the trampoline, MAXVA and above) are unchanged.

This is the second and last change to usertests. Clinic 5 shows that the replaced probe at MAXHEAP is also a good guard detector: with no gap, read into it succeeds.

Step 11 of 18 · commit 5: Accept stack addresses in fetchaddr

fetchaddr accepts the stack

fetchaddr is the one place that checks a user address against p->sz on its own, before any copy. sys_exec uses it to fetch each pointer of the argv array, and a program that builds argv in a local array passes a stack address. The new test accepts 8 bytes that lie entirely below p->sz (inmem) or entirely inside the stack region (instack). In each case addr is compared first, so addr + 8 cannot wrap around.

gdb, during usertests exectest: three calls with addr = 0x3fffffde70, 0x3fffffde78 and 0x3fffffde80, the three slots of echoargv ("echo", "OK", 0) in the test’s stack frame. Each passes instack, and copyin reads the pointer from a page that is mapped. Had the array been in a stack page not grown yet, copyin would have grown it.

fetchstr, just below, needed nothing: it has no bound of its own and relies on copyinstr, which relies on vmfault. Clinic 6 removes this commit: exectest fails with exec echo failed.

Step 12 of 18 · commit 6: Build the user stack at the top in exec

exec starts the stack empty, at the top

This is the switch. kexec no longer maps a guard page and a stack page after the image. sz, rounded up to a page, is now just the end of the image, where the heap will start. sp starts at USTACKTOP, and stackbase, the lowest address the arguments may use, is one page lower: arguments must fit in one page, as before.

Nothing maps that page explicitly. The first copyout of an argument string (line 101) finds 0x3fffffd000 unmapped in the new page table and calls vmfault, which grows it. That works because vmfault is given a page table and a size, not a process: gdb saw it map the page into page table 0x87f43000 (the new one, for sh) with psz = 0x3000, sh’s new image size, while the process was still running on init’s old one.

The very first exec of the system, init’s from forkret, takes the same path with interrupts off (gdb: pid 1, SIE 0, intena 0); every later exec comes from sys_exec with interrupts on, as here. vmfault works either way: it never sleeps. If the page cannot be allocated, copyout fails and kexec goes to bad:.

Step 13 of 18 · commit 6: Build the user stack at the top in exec

Committing the image, and freeing the old stack

p->sz = sz now records only the image (the heap is empty); the stack is described by the constants and the page table, not by any field. p->trapframe->sp is the sp the argument copies left, a little below USTACKTOP, so the program starts on its one stack page.

proc_freepagetable then frees the old image. gdb: the old page table (a copy of init’s, made by fork) had sz = 0x2000 and one stack page at 0x3fffffd000, which commit 2’s line freed. The error path (line 139) calls the same function on the half-built new page table, which may already hold the first stack page if a later argument did not fit (usertests bigargtest does exactly that: the first argument fits, the eleventh does not).

The name is copied before the commit (line 125), which is why gdb already reported pid 2 as sh here.

Step 14 of 18 · commit 6: Build the user stack at the top in exec

USERSTACK becomes a maximum

param.h changes in the same commit: #define USERSTACK 64 // max user stack pages. The name stays and the meaning changes, from “the stack’s size” to “the most it may grow to”, 256 KiB. With it the constants become USTACKBASE = 0x3ffffbe000 and MAXHEAP = 0x3ffffbd000, and the layout comment now tells the truth: heap up to MAXHEAP, a guard page, then the stack, growing down from USTACKTOP.

uvmclear is gone from vm.c and defs.h: it existed only to make the old guard page inaccessible. The new guard is a page that is never mapped at all, so it costs no memory. Right after boot the branch has 2 more free pages than the original kernel (32,547 against 32,545): the guard pages of init and sh. Every fork also copies one page less, since uvmcopy used to copy the old guard page along with everything else below sz.

Keeping the name was deliberate: usertests stacktest uses it (next step).

Step 15 of 18 · commit 6: Build the user stack at the top in exec

stacktest passes without a change

stacktest reads one byte USERSTACK * PGSIZE below its own sp and expects to be killed. Written for the old layout, it meant “just below the one stack page, in the guard”. With USERSTACK the maximum, the same expression means “just below the deepest the stack may go”, which is the new guard. The test checks the right thing without knowing anything moved.

The recorded runs, same test on two kernels:

original:  test stacktest: usertrap(): unexpected scause 0xd pid=6568
                       sepc=0x1c3e stval=0x10e90
branch:    test stacktest: usertrap(): unexpected scause 0xd pid=6569
                       sepc=0x1c40 stval=0x3ffffbde90

(The first is from commit 1 of the branch, which still has the old layout.) On the original kernel 0x10e90 is in usertests’ guard page at 0x10000, right after its 16 pages of image. On the branch, 0x3ffffbde90 is in the guard page 0x3ffffbd000. A load gives scause 13 (0xd).

Step 16 of 18 · commit 7: Add growstack, a test for the growable stack

The test recurses through 18 pages

dive has a 1 KiB volatile array, so the compiler must keep it in memory and write every byte; its frame is 1,088 bytes (addi sp,sp,-1088 in growstack.asm). It fills its array with its depth, recurses, and on the way back checks the array and scribbles over it. Sixty-five frames are about 69 KiB, so the stack must grow by 17 pages beyond the top page the child inherited through fork (exec grew that one in growstack itself).

The recorded run: 65 calls used 70944 bytes of stack. The deepest sp was 0x3fffffe000 - 70944 = 0x3ffffecae0, in page 0x3ffffec000; the child’s address space was freed with 18 stack pages. A counting copy of the kernel (instrumentation not on the branch) counted 18 stack growths for this command: 17 from the child’s page faults, plus the one from growstack’s exec.

Each check runs in its own child (inchild), so growstack itself keeps a one-page stack. That matters for read (its buffer must lie in pages nobody has touched, and a child inherits its parent’s stack pages) and for overflow and collide, which are supposed to die.

On the original layout (commit 1) this check dies at the first frame past the page: usertrap(): unexpected scause 0xf pid=4, stval=0x3e28, in growstack’s old guard page 0x3000, and the line reads deep: FAIL.

Step 17 of 18 · commit 7: Add growstack, a test for the growable stack

Overflow, killed one frame above the limit

The child recurses without end and writes each frame’s sp into a pipe; the parent keeps the last value it reads. When the child dies, the pipe’s write end closes, read returns 0, and the parent checks three things: the child was killed (status -1), its deepest frame is not below USTACKBASE, and it is within one frame (plus a little) of it, so the kill came at the limit and not earlier.

Recorded: status -1, deepest sp 0x3FFFFBE330, limit 0x3FFFFBE000 (user printf prints hex in upper case). 0x3ffffbe330 is 816 bytes above USTACKBASE; the next frame starts 1,088 bytes lower, at 0x3ffffbdef0, and its first store, at sp + 8 = 0x3ffffbdef8, is in the guard page. That is exactly the stval on the console.

The program does not read stval; its sp window already pins the kill to the first frame below the limit. The next step is the kernel’s side of that moment.

Step 18 of 18 · commit 7: Add growstack, a test for the growable stack

The kill, and 64 pages freed

usertrap did not change in this lab. The fault (scause 15, stval 0x3ffffbdef8) goes to vmfault as always; 0x3ffffbdef8 is above p->sz (0x3000) and below USTACKBASE, so vmfault returns 0, and the else branch prints the two lines and marks the process killed. gdb stopped at the setkilled call (line 78), right after the two lines were printed, and read exactly these values from scause and stval.

The child exits, and its parent reaps it in kwait. gdb read the child’s page table in proc_freepagetable at that moment: 64 valid stack PTEs, 0x3ffffbe000 to 0x3fffffd000, the whole region, all freed by commit 2’s line. 63 were grown by page faults; the top one came through fork (exec grew it in the parent).

What did the lab cost? Seven commits: three constants, one condition in vmfault, a range for uvmcopy, one line in proc_freepagetable, a widened test in fetchaddr, a shorter kexec, and two changed expectations in usertests. What it took to find them: every place the kernel says “the process’s memory” by [0, p->sz), found by asking, for each one, whether it still sees the whole process.