Extension labs · lab 13 · Memory · ★★★☆☆

A growable user stack

In this tree every user program gets exactly one page of stack. kexec places a guard page and a single stack page right after the program’s data, and the heap grows from just above them. A recursive function that needs 5 KiB of stack is killed. In this lab the stack moves to the top of the user address space and grows down, one page at a time, as the program touches it, up to a fixed maximum. The heap keeps growing up from the end of the program, and an unmapped gap separates the two.

The fault handler is the easy part. The lazy heap already fills missing pages on demand. What decides which addresses it will fill, and what else in the kernel decides the same thing its own way? Every one of those places has to be asked again: does it still see the whole process? Some of them fail loudly when they get it wrong, some quietly, and one only in a situation usertests never creates. And usertests has opinions about where the stack ends.

The reference solution is seven small commits. With it, 65 recursive calls with 1 KiB of locals each use 70,944 bytes of stack (18 pages), and unbounded recursion is killed one frame above the limit.

Read first: Tour 10: Exceptions and faults, Tour 20: fork, Tour 21: exit, wait and zombies, Tour 22: exec, Tour 25: A user address space, Tour 26: sbrk, eager and lazy, and page faults, Tour 28: Crossing the user/kernel boundary in memory · The stacks of xv6

What this lab teaches

How the user address space is laid out, who decides it, and what it means to move one region of it: which code assumes the old layout without saying so.
What happens when the kernel, not the program, is the first to touch a page of user memory, and where the kernel checks user addresses on its own.
What a fixed-size, page-aligned region buys you compared with tracking a moving boundary per process.
How a guard page works when it is not mapped at all, and what limits it has.
What fork, exec and exit each do with the pages of an address space, and what goes wrong, and how visibly, when one of them overlooks a region.

The reference branch

ext/13-growstack in ShowMeTheStack/xv6-riscv-labs, branched from the frozen commit 06aad25; 7 commits.

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

1. The spec

Behaviour. A process’s stack starts with one page at the top of user memory, just below the trapframe, and grows down by whole pages when the program, or the kernel on its behalf, touches an address below the pages it already has. It grows to at most USERSTACK pages (64, 256 KiB, in the reference). A touch below that limit kills the process, exactly as the guard page does today. The heap starts right after the program image and grows up with sbrk as before, eagerly or lazily, but never so far that it would reach the page just below the stack’s lowest possible page: that page stays unmapped, as a guard between the two.

A new stack page is zero-filled and writable, like a lazy heap page.
fork gives the child its own copy of every stack page the parent has.
exit and exec free the stack pages along with the rest of the old image.
System calls that copy into a stack page nobody has touched yet (read, pipe, wait(&status) with a local status) succeed and grow the stack; they do not fail.
exec’s arguments must still fit in one page, as before.

What must not change. Everything usertests checks about bad pointers, the trapframe, the trampoline, MAXVA, lazy and eager sbrk, and stack overflow. usertests -q must print ALL TESTS PASSED on 3 harts. A few tests know the old layout; the think section finds which, and decides for each one whether it still tests something true.

The test program, growstack, runs five checks, each in a child process (growstack NAME runs one):

$ growstack
growstack: deep: 65 calls used 70944 bytes of stack
growstack: deep: OK
growstack: fork: OK
growstack: read: OK
usertrap(): unexpected scause 0xf pid=8
            sepc=0x36a stval=0x3ffffbdef8
growstack: overflow: status -1, deepest sp 0x3FFFFBE330, limit 0x3FFFFBE000: OK
usertrap(): unexpected scause 0xf pid=9
            sepc=0xce stval=0x3ffffbd000
growstack: collide: OK
growstack: ALL OK

deep: a recursive function with a 1 KiB local array calls itself 64 times (65 frames), filling each array with its depth and checking all of them on the way back.
fork: the same recursion forks at the bottom. The child checks all 65 frames of its copy and scribbles over each one as it unwinds; after the child has exited, the parent checks its own frames.
read: read() from a pipe into a stack buffer that lies in pages nobody has touched, 50 bytes before a page boundary, so the 100 bytes land in two such pages.
overflow: unbounded recursion, with every frame reporting its sp through a pipe. The child must be killed (exit status -1), and its deepest frame must be within one frame of the limit: not killed earlier, not allowed below.
collide: the heap grows (lazily) to exactly the highest address allowed and no further; its last byte works; a store to the guard page above it kills.

The two usertrap() lines are the expected kills of the overflow and collide children. The program checks what the final line claims: each child’s exit status (-1), how deep the overflow child got before it died (its last reported sp lies within one frame above the limit), and that the collide child passed its heap checks before its store into the guard. The stval values are shown for information; the line ALL OK does not depend on them.

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.

1Where does a stack that grows have to live?

In this tree kexec places a guard page and one stack page (USERSTACK is 1) right after the program image, and the heap grows from just above them. Recursion that needs more than 4 KiB dies. In this layout, where could a second stack page come from? Where would you put the stack instead, in which direction does it grow, what stops it, and what does your choice do to p->sz, which today covers everything a process owns?

The reference design

In the original layout the stack is boxed in. Below its page is the guard page, a real page that uvmclear made inaccessible to user mode (kernel/exec.c:95), and below that the program’s data. Above it is the first page of the heap (kernel/exec.c:96 sets the initial sp to sz, which is also where sbrk starts). The stack cannot grow down without overwriting data, and it cannot move up because the heap is there.

The reference moves the stack to the top of user memory, where nothing lives:

address	what
`0x3ffffff000`	TRAMPOLINE (not user-accessible)
`0x3fffffe000`	TRAPFRAME (not user-accessible); also `USTACKTOP`, the stack’s top (exclusive)
`0x3ffffbe000` to `0x3fffffdfff`	the stack region: 64 pages, grown from the top down as needed (`USTACKBASE` is its bottom)
`0x3ffffbd000` to `0x3ffffbdfff`	the guard page, never mapped
up to `0x3ffffbd000`	`MAXHEAP`, the highest `p->sz` the heap may reach
from `0`	text, data, bss, then the heap, growing up

Three constants describe it, in memlayout.h: USTACKTOP (= TRAPFRAME), USTACKBASE (USTACKTOP - USERSTACK * PGSIZE) and MAXHEAP (USTACKBASE - PGSIZE). USERSTACK keeps its name but changes its meaning, from “the stack’s size” to “the most pages it may grow to” (64 here). Virtual addresses cost nothing: the region costs memory only for the pages a program actually touches.

Why a fixed region instead of a per-process “lowest stack page” that moves? With constants, every question below (“is this address a stack address?”, “which pages might the stack have?”) has the same answer for every process, with no new field to keep correct across fork, exec and exit. The price is a fixed maximum. Putting the heap at the top growing down instead would have changed the meaning of sbrk’s return value for every program.

What it does to p->sz is the real subject of this lab. The stack now lies above p->sz, so every piece of kernel code that means “all of this process’s memory” when it says [0, p->sz) is now wrong about the stack. The next three questions find those places.

The guard is now a page that is simply never mapped, rather than a mapped page with PTE_U cleared. The old guard used a page of physical memory in every process: on the branch, right after boot, 2 more pages are free than on the original kernel (32,547 against 32,545; init and sh each saved one).

Check yourself

1warm-upChoose one

On the original kernel, a program’s stack needs a second page: the next function call stores below the stack page. What is at that address, and what happens?

kernel/exec.c

// Allocate some pages at the next page boundary.
// Make the first inaccessible as a stack guard.
// Use the rest as the user stack.
sz = PGROUNDUP(sz);
uint64 sz1;
if ((sz1 = uvmalloc(pagetable, sz, sz + (USERSTACK + 1) * PGSIZE, PTE_W)) ==
    0)
  goto bad;
sz = sz1;
uvmclear(pagetable, sz - (USERSTACK + 1) * PGSIZE);
sp = sz;
stackbase = sp - USERSTACK * PGSIZE;

The first page of the heap, so the stack silently overwrites the heap.Nothing: the hart lets the store through, because the page is below p->sz.An unmapped address below p->sz, so vmfault gives it a fresh zero page and the stack grows.The guard page: a mapped page with PTE_U cleared. The store faults, vmfault refuses because the page is mapped, and the process is killed.

2solidType a number

With USTACKTOP = TRAPFRAME = 0x3fffffe000, USERSTACK = 64 and one guard page, what is MAXHEAP, the highest value p->sz may reach? (Answer in hex.)

decimal, 0x hex or 0b binary

2Who grows the stack when the program touches a new page?

A function call stores a frame onto a page the stack has never used. What does the hart do, which kernel function decides what happens next, and on what test does it decide today? What must it learn, and how will it tell a stack page from a wild pointer?

The reference design

The store raises a store page fault (scause 15; a load would raise 13), the trampoline takes it to usertrap, and usertrap calls vmfault with the process’s page table, p->sz and stval. Today vmfault's first test, va >= psz, rejects every address at or above p->sz, and the process dies. In the new layout that would kill every program at its first deep call.

The reference changes that one test:

if (va >= psz && (va < USTACKBASE || va >= USTACKTOP))
  return 0;

An address below p->sz (the image and heap) or inside the stack region passes; the rest of vmfault is unchanged. It refuses a page that is already mapped, allocates a page, zeroes it, and maps it readable, writable and user-accessible. Zeroing matters here as it does for the heap: kalloc fills pages with junk (0x05 bytes), and a page that another process freed must never show its old contents to a new owner.

Any address in the region grows the stack, even one far below sp. Telling a real stack access from a wild pointer would need the faulting sp, and a program may legitimately address a local array whose low end lies far below its last touched page (the read check does exactly that). Inside a fixed region the cost of a wild pointer is bounded: at most the region’s 64 pages, all freed at exit.

gdb logged the first five store faults of growstack deep (pid 4, hart 0): the first with stval=0x3fffffce28, then 0x3fffffbd28, 0x3fffffac28, … each about 4 KiB lower, each one in vmfault called from usertrap with interrupts off and no lock held. A counting copy of the kernel counted 17 in all. The process ended with 18 stack pages: the 17 grown by faults and the top one, inherited through fork (exec grew it in the parent, growstack itself).

Check yourself

1solidFill in the machine state

growstack deep (pid 4) stores into a stack page it has never touched, and vmfault, called from usertrap, is about to allocate the page. Fill in the hart’s state at that moment.

kernel/vm.c

458uint64
459vmfault(pagetable_t pagetable, uint64 psz, uint64 va, int read)
460{
uint64 mem;
462
if (va >= psz)
  return 0;
va = PGROUNDDOWN(va);
if (ismapped(pagetable, va)) {
  return 0;
}
mem = (uint64)kalloc();
if (mem == 0)
  return 0;
memset((void *)mem, 0, PGSIZE);
if (mappages(pagetable, va, PGSIZE, mem, PTE_W | PTE_U | PTE_R) != 0) {
  kfree((void *)mem);
  return 0;
}
return mem;
478}

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

2warm-upChoose one

On the reference branch, a program stores to 0x3ffffbd010, with p->sz = 0x3000. What does vmfault return, and what happens to the process?

0, and the kernel panics, because a user address faulted in the guard.A new zeroed page, because the address is inside the stack’s 64 pages.0; usertrap prints an unexpected scause 0xf and kills the process.A new zeroed page, because the stack grows down without a limit.

3The kernel touches the stack too

Not every first touch of a stack page is made by user code. Which kernel paths read or write user memory, and what do they do when the page they need is not mapped yet? Which of them compare a user address with p->sz on their own, before they get that far? And who writes into a new process’s stack before it has run a single instruction?

The reference design

The copy functions need nothing. copyout, copyin and copyinstr look a page up with walkaddr and, if it is missing, call vmfault with the page table and size they were given. Teaching vmfault the region taught all three. growstack read relies on it: its buffer lies in pages the child never touched, and gdb saw copyout grow them, 0x3fffffa000 and then 0x3fffffb000, for piperead in pid 7.

That path holds a spinlock: piperead copies byte by byte under pi->lock (kernel/pipe.c:133). gdb recorded noff 1, intena 1, interrupts off at the allocation. That is safe because growing a stack page never sleeps: vmfault calls kalloc, which takes kmem.lock for a few instructions, and mappages, which may allocate a page-table page the same way. Neither waits for anything. (Compare lab 12, where the fault handler reads from disk and every copy under a lock became a hazard.) The same holds for kwait's copyout of the exit status under wait_lock and the child’s p->lock.

fetchaddr needs a change. It refuses any address at or above p->sz before it copies (kernel/syscall.c:15-kernel/syscall.c:16). sys_exec fetches each argv[i] pointer with it, and a program that builds argv in a local array, like usertests exectest (char *echoargv[] = {"echo", "OK", 0};), would have its exec refused. The reference accepts the 8 bytes if they lie below p->sz or inside the stack region. gdb saw the three fetches for exectest: 0x3fffffde70, 0x3fffffde78, 0x3fffffde80. fetchstr needs nothing: it has no bound of its own and goes straight to copyinstr.

exec writes the first stack page. kexec copies the argument strings and the argv array onto the new stack with copyout into the new page table, before the process has ever run on it. The reference no longer maps a stack page in kexec at all: the first copyout finds USTACKTOP - 4096 unmapped and vmfault grows it. This works because vmfault receives a page table and a size, not a process: it does not care that this page table is not installed yet. The arguments must still fit in that one page (the sp < stackbase test stays, with stackbase = USTACKTOP - PGSIZE).

One of those execs runs with interrupts off: the very first, init’s, called from forkret. gdb saw pid 1’s copyout → vmfault at 0x3fffffd000 with SIE 0 and intena 0. Every later exec, from sys_exec, ran with interrupts on. Neither matters to vmfault, which never sleeps.

4Fork, exec and exit walk the address space too

Which kernel functions copy, walk or free “the process’s memory” by a size? What happens to the stack pages at fork, at exit, at the end of exec (the old image), and on exec’s error path? For each, what exactly would go wrong if you missed it, and how would you notice?

The reference design

fork. uvmcopy copied [0, sz). The reference gives it a start and an end (start page-aligned, the error path unmapping only [start, i)), and kfork calls it twice: 0 to p->sz, then USTACKBASE to USTACKTOP. Unmapped pages are skipped, so the second call copies exactly the pages the parent’s stack has grown into. gdb saw the growstack fork process (pid 5, at the bottom of its 65 frames, user sp 0x3ffffecad0) fork with 18 stack pages, 0x3ffffec000 to 0x3fffffd000. A fork from the shell copies one.

The child’s np->sz is now set before the copies. If the first copy succeeds and the second fails, freeproc frees the child’s page table with proc_freepagetable and np->sz; with np->sz still 0 it would leave the first copy’s pages mapped, and freewalk would panic.

Forget the stack copy and the child gets an empty stack region. Its first stack access does not fail: vmfault hands it a zero page. So the child reads zeros where its frames should be, and returns to address 0 (clinic 1: every command the shell forks prints a second prompt and dies).

exit and exec. uvmfree unmaps [0, sz) and then freewalk frees the page-table pages, panicking with freewalk: leaf if any page is still mapped. Stack pages above sz are such leaves. All three teardown paths go through proc_freepagetable: freeproc (when a parent reaps its child in kwait), the end of kexec (the old image) and kexec's bad: path (a half-built new image, which may already have its first stack page). The reference adds one line there: uvmunmap(pagetable, USTACKBASE, USERSTACK, 1), which frees whatever is mapped in the region and skips the rest. gdb saw it free 18 pages for the deep child, 3 for the read child and 64 for the overflow child.

Forget it entirely and the kernel panics with freewalk: leaf at the first exec of a process that has a stack page (clinic 2’s why: init’s child exec’ing sh). Unmap the region without freeing it (do_free 0) and nothing panics: the pages are simply lost (clinic 2).

Check yourself

1solidType a number

growstack fork forks at the bottom of 65 frames of 1,088 bytes each (the frame dive allocates), which started near the top of the stack. How many stack pages did uvmcopy copy for that fork?

decimal, 0x hex or 0b binary

2solidChoose one

A kernel has everything right except that kfork still copies only [0, p->sz). It boots to the shell prompt. You type growstack. What do you see?

panic: freewalk: leafgrowstack: fork: FAIL, and the other checks pass.Another "$ " prompt, then usertrap(): unexpected scause 0xf with stval=0x0, then the next prompt; growstack never runs.Nothing: the child faults on its stack and is killed silently.

5Where exactly does the stack stop?

Name every limit and what enforces it: how far down the stack may grow, what happens one byte below that, how the heap is kept out of the gap, and how much of the stack exec may fill with arguments. At each boundary, check the comparison for an off-by-one.

The reference design

limit	value	enforced by	one past it
lowest stack address	`USTACKBASE` = `0x3ffffbe000`	`vmfault`: `va < USTACKBASE` is not a stack address	a touch at `0x3ffffbdfff` is in the guard: killed
highest heap end	`MAXHEAP` = `0x3ffffbd000`	`growproc` and the lazy path of `sys_sbrk`: `sz + n > MAXHEAP` → -1	`sbrk` refuses; `p->sz` never covers the guard
arguments	one page below `USTACKTOP`	`kexec`: `sp < stackbase` → fail	`exec` returns -1, as `bigargtest` expects

gdb saw both sbrk refusals in growstack collide (pid 6, heap at 0x3ffffbd000): sys_sbrk's lazy path with addr + n = 0x3ffffbd001, and growproc with sz = 0x3ffffbd000, n = 0x1000. The one-byte case matters: MAXHEAP itself is allowed as the end (the heap’s last byte is 0x3ffffbcfff), and one byte more is not.

growstack overflow shows the stack’s limit from the other side. Each frame of dive is 1,088 bytes; the deepest frame that reported its sp had sp = 0x3ffffbe330, 816 bytes above USTACKBASE. The next frame’s first store below USTACKBASE (stval=0x3ffffbdef8, in the guard page) was refused and the child was killed, with exactly 64 stack pages mapped.

The guard has a known hole: it is one page. A function whose frame is larger than a page can move sp past the guard in one step, and its first store can land in a heap page that is already mapped, with no fault at all. The same was true of the original guard page. (Not run here; real systems add a larger gap, or make the compiler touch every page of a large frame in order, which is called stack probing.)

Off by one page in either direction is a real bug. A heap ceiling of USTACKBASE instead of MAXHEAP leaves no guard (clinic 5). A stack test of va >= USTACKTOP alone, with no lower bound, lets the stack grow over anything above p->sz (clinic 3).

Check yourself

1deepTrue or false, and why

True or false: on the reference branch, with the heap grown to MAXHEAP and the stack grown to its limit, any further stack growth is caught by the guard page and kills the process.

TrueFalse

Why?

A single frame larger than 4 KiB can move sp past the guard, and its first store can land in a mapped heap page without any fault.sbrk can always map the guard page later, so the guard is not reliable.vmfault grows the stack into the guard page when the heap has not reached it.

2solidType a number

growstack overflow recurses until it is killed. How many stack pages does the child have when its address space is freed?

decimal, 0x hex or 0b binary

6What does usertests think?

Some tests in usertests know the old layout. Find each test that depends on where the stack, its guard or the heap’s ceiling is. For each one, decide: does the property it checks still hold (then it must pass unchanged), or did this lab change that property on purpose (then change the expectation, as little as possible, and say why)?

The reference design

test	what it assumed	on the branch
`stacktest`	the page below the stack is a guard	reads `USERSTACK * PGSIZE` (256 KiB) below `sp`: below `USTACKBASE`, in the guard. Still killed, unchanged
`lazy_sbrk`	the heap may grow up to `TRAPFRAME`	ceiling is `MAXHEAP` now: `TRAPFRAME` → `MAXHEAP` in two places, changed
`lazy_copy`	`read`/`write` at `0x3fffffc000` and `0x3fffffd000` must fail	those are stack pages now (`0x3fffffd000` is the one every process has); probes replaced by `MAXHEAP - PGSIZE` and `MAXHEAP` (the guard), which must fail, changed
`bigargtest`	arguments larger than a page make `exec` fail	the argument area is still one page, unchanged
`copyin`, `copyout`, `copyinstr1`, `nowrite`	`0x3fffffe000` (`TRAPFRAME`) is not user memory	`USTACKTOP` is exclusive, and the page is mapped without `PTE_U`; still refused, unchanged

stacktest is the nicest case. It was written as “read one stack’s worth below sp”, with USERSTACK meaning the stack’s size. With USERSTACK meaning the maximum, the same expression lands just below the maximum, which is exactly the overflow the new guard must catch. On the branch it faulted at stval=0x3ffffbde90, in the guard page; with the old layout (commit 1) at stval=0x10e90.

The lazy_copy change is the one to defend. The test wants “addresses that are not this process’s memory”. 0x3fffffd000 was such an address and is now the top stack page of every process: a read into it succeeds (it would write into the test’s own unused stack space). The replacements keep the intent: the last page the heap could have but does not, and the guard. Keeping the old addresses would have meant putting the stack somewhere other than the top for no reason except the test.

Check yourself

1solidMatch the pairs

Match each usertests test with what the branch does about it.

stacktestlazy_sbrklazy_copybigargtest

2warm-upChoose one

stacktest’s child reads at sp - USERSTACK * PGSIZE. On the branch, where is that?

user/usertests.c

2442stacktest(char *s)
2443{
int pid;
int xstatus;
2446
pid = fork();
if (pid == 0) {
  char *sp = (char *)r_sp();
  sp -= USERSTACK * PGSIZE;
  // the *sp should cause a trap.
  printf("%s: stacktest: read below stack %d\n", s, *sp);
  exit(1);
} else if (pid < 0) {
  printf("%s: fork failed\n", s);
  exit(1);
}
wait(&xstatus);
if (xstatus == -1) // kernel killed child?
  exit(0);
else

In an ungrown stack page, so the read returns 0 and the test fails.Below MAXVA’s user half, so the kernel panics.In the heap, so the read succeeds.In the guard page below USTACKBASE, so the read faults and the child is killed.

3. Build it

Start.

git checkout -b my-13 06aad25

Milestones, in an order that keeps usertests -q passing after each one. The trick is to prepare every piece of code that will have to know about the stack region before the stack moves there; until the last kernel milestone the region is empty, so each new piece is tested by the existing suite while it carries no weight. (The reference branch has the same changes, with the test program committed last; usertests -q passed on 3 harts at every one of its commits.)

Name the layout. Three constants in memlayout.h for the stack’s top, its lowest page and the heap’s ceiling (leave USERSTACK at 1 for now). Lower the ceiling in growproc and in sys_sbrk's lazy path, and update the one test that walks the heap up to its ceiling. Test: usertests -q.
Write the test program now, user/growstack.c with the spec’s five checks, and add $U/_growstack\ to UPROGS. On this kernel deep, fork, read and overflow print FAIL and collide prints OK: that is the test working.
Free the region. One line in proc_freepagetable. Test: usertests -q.
Copy the region in fork. A range for uvmcopy, two calls in kfork, and the child’s sz set before anything can fail. Test: usertests -q.
Grow on demand. The region test in vmfault. One of lazy_copy’s probes (0x3fffffd000) now points into the one-page region and will succeed; the other (0x3fffffc000) joins the region at milestone 7. Replace both with MAXHEAP - PGSIZE and MAXHEAP. Test: usertests -q.
Let exec find arguments on the stack: fetchaddr. Test: usertests -q.
Move the stack. kexec stops mapping a guard and a stack page after the image and starts sp at the top; USERSTACK becomes the maximum. Test: growstack, then usertests -q, then growstack again.

Debugging advice.

A process killed with stval in the region (0x3ffffbe000-0x3fffffdfff) means vmfault refused a stack address; one killed with stval 0 and a sepc in a function such as memset or sh’s getcmd usually means it returned through a zeroed frame: look at the fork path.
panic: freewalk: leaf: break on panic, run bt, and read the leaf’s page table. With gdb attached, a small Python helper that walks the three levels of a page table from a pagetable_t (reading physical memory, which the kernel maps one to one) lists which pages are still mapped; for a stack bug they are in 0x3ffffbe000-0x3fffffd000.
To watch growth, break on the kalloc call in vmfault with a condition on va (va >= 0x3ffffbe000 && va < 0x3fffffe000) and print bt: the second frame tells you whether a fault (usertrap) or a kernel copy (copyout from piperead, kexec, …) grew the page.
The kernel’s printk prints hex in lower case and user printf in upper case, so the same address appears as 0x3ffffbe000 and 0x3FFFFBE000.

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.

1fork copies only the pages below p->sz

Milestone 4 is skipped: kfork still copies one range.

-  if (uvmcopy(p->pagetable, np->pagetable, 0, p->sz) < 0 ||
-      uvmcopy(p->pagetable, np->pagetable, USTACKBASE, USTACKTOP) < 0) {
+  if (uvmcopy(p->pagetable, np->pagetable, 0, p->sz) < 0) {

What happened when we ran it

xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
$ growstack
$ usertrap(): unexpected scause 0xf pid=3
            sepc=0xa70 stval=0x0
$ usertests -q
$ usertrap(): unexpected scause 0xf pid=4
            sepc=0xa70 stval=0x0
$

2Stack pages are unmapped but not freed

Milestone 3 with the wrong last argument: the pages leave the page table but are never given back to kalloc.

-  uvmunmap(pagetable, USTACKBASE, USERSTACK, 1);
+  uvmunmap(pagetable, USTACKBASE, USERSTACK, 0);

What happened when we ran it

$ growstack
growstack: deep: 65 calls used 70944 bytes of stack
[...]
growstack: ALL OK
$ usertests -q
usertests starting
test copyin: OK
[...]
test sbrkfail: sbrkfail: failed sbrk leaked memory
FAILED
SOME TESTS FAILED

3The stack has no lower limit

The region test in vmfault only checks the top:

-  if (va >= psz && (va < USTACKBASE || va >= USTACKTOP))
+  if (va >= psz && va >= USTACKTOP)
     return 0;

What happened when we ran it

$ usertests -q
usertests starting
test copyin: write(fd, 0x0000000080000000, 8192) returned 8192, not -1
panic: freewalk: leaf

# another boot of the same kernel
$ growstack
growstack: deep: 65 calls used 70944 bytes of stack
growstack: deep: OK
growstack: fork: OK
growstack: read: OK
usertrap(): unexpected scause 0xf pid=8
            sepc=0x36a stval=0x3ff812dcb8
panic: freewalk: leaf

4The stack grows only in usertrap

The learner adds a branch to usertrap that maps a page when stval is in the region, leaves vmfault unchanged, and lets kexec map the first stack page itself (it can no longer rely on copyout to grow it):

   } else if ((r_scause() == 15 || r_scause() == 13) &&
+             r_stval() >= USTACKBASE && r_stval() < USTACKTOP &&
+             uvmalloc(p->pagetable, PGROUNDDOWN(r_stval()),
+                      PGROUNDDOWN(r_stval()) + PGSIZE, PTE_W) != 0) {
+    // grew the stack
+  } else if ((r_scause() == 15 || r_scause() == 13) &&
              vmfault(p->pagetable, p->sz, r_stval(),

   sz = PGROUNDUP(sz);
+  if (uvmalloc(pagetable, USTACKTOP - PGSIZE, USTACKTOP, PTE_W) == 0)
+    goto bad;
   sp = USTACKTOP;

What happened when we ran it

$ growstack
growstack: deep: 65 calls used 70944 bytes of stack
growstack: deep: OK
growstack: fork: OK
growstack: read: FAIL
usertrap(): unexpected scause 0xf pid=8
            sepc=0x36a stval=0x3ffffbdef8
growstack: overflow: status -1, deepest sp 0x3FFFFBE330, limit 0x3FFFFBE000: OK
usertrap(): unexpected scause 0xf pid=9
            sepc=0xce stval=0x3ffffbd000
growstack: collide: OK
growstack: SOME FAILED
$ usertests -q
usertests starting
[...]
ALL TESTS PASSED

5No gap between heap and stack

An off-by-one page at the guard: the heap may grow right up to the stack’s lowest page.

-#define MAXHEAP    (USTACKBASE - PGSIZE)
+#define MAXHEAP    USTACKBASE

What happened when we ran it

$ growstack
[...]
growstack: overflow: status -1, deepest sp 0x3FFFFBE330, limit 0x3FFFFBE000: OK
growstack: collide: FAIL
growstack: collide: heap checks passed, exit status 4
growstack: SOME FAILED
$ usertests -q
usertests starting
[...]
test lazy_copy: read succeeded
FAILED
SOME TESTS FAILED

6fetchaddr still checks only p->sz

Milestone 6 is skipped:

-  int inmem = addr < p->sz && addr + sizeof(uint64) <= p->sz;
-  int instack = addr >= USTACKBASE && addr < USTACKTOP &&
-                addr + sizeof(uint64) <= USTACKTOP;
-  if (!inmem && !instack)
+  if (addr >= p->sz ||
+      addr + sizeof(uint64) > p->sz) // both tests needed, in case of overflow
     return -1;

What happened when we ran it

$ growstack
[...]
growstack: ALL OK
$ usertests -q
usertests starting
test copyin: OK
[...]
test exectest: exectest: exec echo failed
exectest: nonzero wait status 1
FAILED
SOME TESTS FAILED

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

b4b42d5 Reserve a stack region below the trapframe
kernel/memlayout.h
@@ -60,4 +60,13 @@
6060// ...
6161// TRAPFRAME (p->trapframe, used by the trampoline)
6262// TRAMPOLINE (the same page as in the kernel)
6363#define TRAPFRAME (TRAMPOLINE - PGSIZE)
64
65// The user stack region: the top USERSTACK pages below
66// TRAPFRAME. The stack grows down from USTACKTOP, one page
67// at a time, but never below USTACKBASE. The heap must end
68// at or below MAXHEAP, which leaves one unmapped guard page
69// between the heap and the lowest possible stack page.
70#define USTACKTOP TRAPFRAME
71#define USTACKBASE (USTACKTOP - USERSTACK * PGSIZE)
72#define MAXHEAP (USTACKBASE - PGSIZE)
kernel/proc.c
@@ -239,9 +239,9 @@ growproc(int n)
239239 struct proc *p = myproc();
240240
241241 sz = p->sz;
242242 if (n > 0) {
243 if (sz + n > TRAPFRAME) {
243 if (sz + n > MAXHEAP) {
244244 return -1;
245245 }
246246 if ((sz = uvmalloc(p->pagetable, sz, sz + n, PTE_W)) == 0) {
247247 return -1;
kernel/sysproc.c
@@ -56,9 +56,9 @@ sys_sbrk(void)
5656 // size but don't allocate memory. If the processes uses the
5757 // memory, vmfault() will allocate it.
5858 if (addr + n < addr)
5959 return -1;
60 if (addr + n > TRAPFRAME)
60 if (addr + n > MAXHEAP)
6161 return -1;
6262 myproc()->sz += n;
6363 }
6464 return addr;
user/usertests.c
@@ -2789,19 +2789,19 @@ lazy_sbrk(char *s)
27892789
27902790 p = sbrklazy(0);
27912791 }
27922792
2793 int n = TRAPFRAME - PGSIZE - (uint64)p;
2793 int n = MAXHEAP - PGSIZE - (uint64)p;
27942794
27952795 char *p1 = sbrklazy(n);
27962796 if (p1 < 0 || p1 != p) {
27972797 printf("sbrklazy(%d) returned %p, not expected %p\n", n, p1, p);
27982798 exit(1);
27992799 }
28002800
28012801 p = sbrk(PGSIZE);
2802 if (p < 0 || (uint64)p != TRAPFRAME - PGSIZE) {
2803 printf("sbrk(%d) returned %p, not expected TRAPFRAME-PGSIZE\n", PGSIZE, p);
2802 if (p < 0 || (uint64)p != MAXHEAP - PGSIZE) {
2803 printf("sbrk(%d) returned %p, not expected MAXHEAP-PGSIZE\n", PGSIZE, p);
28042804 exit(1);
28052805 }
28062806
28072807 p[0] = 1;
9f6808b Free the stack region with the page table
kernel/proc.c
@@ -204,14 +204,16 @@ proc_pagetable(struct proc *p)
204204 return pagetable;
205205}
206206
207207// Free a process's page table, and free the
208// physical memory it refers to.
208// physical memory it refers to: the pages below sz
209// and the pages the stack has grown into.
209210void
210211proc_freepagetable(pagetable_t pagetable, uint64 sz)
211212{
212213 uvmunmap(pagetable, TRAMPOLINE, 1, 0);
213214 uvmunmap(pagetable, TRAPFRAME, 1, 0);
215 uvmunmap(pagetable, USTACKBASE, USERSTACK, 1);
214216 uvmfree(pagetable, sz);
215217}
216218
217219// Set up first user process.
db90ac0 Copy the stack region in fork
kernel/defs.h
@@ -158,9 +158,9 @@ void kvmmap(pagetable_t, uint64, uint64, uint64, int);
158158int mappages(pagetable_t, uint64, uint64, uint64, int);
159159pagetable_t uvmcreate(void);
160160uint64 uvmalloc(pagetable_t, uint64, uint64, int);
161161uint64 uvmdealloc(pagetable_t, uint64, uint64);
162int uvmcopy(pagetable_t, pagetable_t, uint64);
162int uvmcopy(pagetable_t, pagetable_t, uint64, 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);
kernel/proc.c
@@ -268,15 +268,19 @@ kfork(void)
268268 if ((np = allocproc()) == 0) {
269269 return -1;
270270 }
271271
272 // Copy user memory from parent to child.
273 if (uvmcopy(p->pagetable, np->pagetable, p->sz) < 0) {
272 // Copy user memory from parent to child: everything below
273 // p->sz, and the pages the parent's stack has grown into.
274 // Set np->sz first, so that if the second copy fails,
275 // freeproc() frees what the first one copied.
276 np->sz = p->sz;
277 if (uvmcopy(p->pagetable, np->pagetable, 0, p->sz) < 0 ||
278 uvmcopy(p->pagetable, np->pagetable, USTACKBASE, USTACKTOP) < 0) {
274279 freeproc(np);
275280 release(&np->lock);
276281 return -1;
277282 }
278 np->sz = p->sz;
279283
280284 // copy saved user registers.
281285 *(np->trapframe) = *(p->trapframe);
282286
kernel/vm.c
@@ -289,22 +289,23 @@ uvmfree(pagetable_t pagetable, uint64 sz)
289289 freewalk(pagetable);
290290}
291291
292292// Given a parent process's page table, copy
293// its memory into a child's page table.
293// the pages it maps in [start, end) into a child's
294// page table. start must be page-aligned.
294295// Copies both the page table and the
295296// physical memory.
296297// returns 0 on success, -1 on failure.
297298// frees any allocated pages on failure.
298299int
299uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
300uvmcopy(pagetable_t old, pagetable_t new, uint64 start, uint64 end)
300301{
301302 pte_t *pte;
302303 uint64 pa, i;
303304 uint flags;
304305 char *mem;
305306
306 for (i = 0; i < sz; i += PGSIZE) {
307 for (i = start; i < end; i += PGSIZE) {
307308 if ((pte = walk(old, i, 0)) == 0)
308309 continue; // page table entry hasn't been allocated
309310 if ((*pte & PTE_V) == 0)
310311 continue; // physical page hasn't been allocated
@@ -320,9 +321,9 @@ uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
320321 }
321322 return 0;
322323
323324err:
324 uvmunmap(new, 0, i / PGSIZE, 1);
325 uvmunmap(new, start, (i - start) / PGSIZE, 1);
325326 return -1;
326327}
327328
328329// mark a PTE invalid for user access.
a58bc15 Let vmfault grow the stack into its region
kernel/vm.c
@@ -452,17 +452,18 @@ copyinstr(pagetable_t pagetable, uint64 psz, char *dst, uint64 srcva,
452452 }
453453}
454454
455455// allocate and map user memory if process is referencing a page
456// that was lazily allocated in sys_sbrk().
456// that was lazily allocated in sys_sbrk(), or a page of the
457// stack region that the stack has not grown into yet.
457458// returns 0 if va is invalid or already mapped, or if
458459// out of physical memory, and physical address if successful.
459460uint64
460461vmfault(pagetable_t pagetable, uint64 psz, uint64 va, int read)
461462{
462463 uint64 mem;
463464
464 if (va >= psz)
465 if (va >= psz && (va < USTACKBASE || va >= USTACKTOP))
465466 return 0;
466467 va = PGROUNDDOWN(va);
467468 if (ismapped(pagetable, va)) {
468469 return 0;
user/usertests.c
@@ -2710,9 +2710,9 @@ lazy_copy(char *s)
27102710 }
27112711
27122712 // read() and write() to these addresses should fail.
27132713 unsigned long bad[] = {
2714 0x3fffffc000, 0x3fffffd000, 0x3fffffe000,
2714 MAXHEAP - PGSIZE, MAXHEAP, 0x3fffffe000,
27152715 0x3ffffff000, 0x4000000000, 0x8000000000,
27162716 };
27172717 for (int i = 0; i < sizeof(bad) / sizeof(bad[0]); i++) {
27182718 int fd = open("README", 0);
ebafc2a Accept stack addresses in fetchaddr
kernel/syscall.c
@@ -11,10 +11,14 @@
1111int
1212fetchaddr(uint64 addr, uint64 *ip)
1313{
1414 struct proc *p = myproc();
15 if (addr >= p->sz ||
16 addr + sizeof(uint64) > p->sz) // both tests needed, in case of overflow
15 // the 8 bytes must lie below p->sz or inside the stack region.
16 // addr is tested first, so that addr + 8 cannot overflow.
17 int inmem = addr < p->sz && addr + sizeof(uint64) <= p->sz;
18 int instack = addr >= USTACKBASE && addr < USTACKTOP &&
19 addr + sizeof(uint64) <= USTACKTOP;
20 if (!inmem && !instack)
1721 return -1;
1822 if (copyin(p->pagetable, p->sz, (char *)ip, addr, sizeof(*ip)) != 0)
1923 return -1;
2024 return 0;
d9c1517 Build the user stack at the top in exec
kernel/defs.h
@@ -161,9 +161,8 @@ uint64 uvmalloc(pagetable_t, uint64, uint64, int);
161161uint64 uvmdealloc(pagetable_t, uint64, uint64);
162162int uvmcopy(pagetable_t, pagetable_t, uint64, uint64);
163163void uvmfree(pagetable_t, uint64);
164164void uvmunmap(pagetable_t, uint64, uint64, int);
165void uvmclear(pagetable_t, uint64);
166165pte_t * walk(pagetable_t, uint64, int);
167166uint64 walkaddr(pagetable_t, uint64);
168167int copyout(pagetable_t, uint64, uint64, char *, uint64);
169168int copyin(pagetable_t, uint64, char *, uint64, uint64);
kernel/exec.c
@@ -82,20 +82,15 @@ kexec(char *path, char **argv)
8282
8383 p = myproc();
8484 uint64 oldsz = p->sz;
8585
86 // Allocate some pages at the next page boundary.
87 // Make the first inaccessible as a stack guard.
88 // Use the rest as the user stack.
86 // The heap will start at the next page boundary. The stack
87 // starts empty at USTACKTOP: the first copyout() below grows
88 // its first page, and page faults grow it down from there.
89 // The arguments must fit in that first page.
8990 sz = PGROUNDUP(sz);
90 uint64 sz1;
91 if ((sz1 = uvmalloc(pagetable, sz, sz + (USERSTACK + 1) * PGSIZE, PTE_W)) ==
92 0)
93 goto bad;
94 sz = sz1;
95 uvmclear(pagetable, sz - (USERSTACK + 1) * PGSIZE);
96 sp = sz;
97 stackbase = sp - USERSTACK * PGSIZE;
91 sp = USTACKTOP;
92 stackbase = sp - PGSIZE;
9893
9994 // Copy argument strings into new stack, remember their
10095 // addresses in ustack[].
10196 for (argc = 0; argv[argc]; argc++) {
kernel/memlayout.h
@@ -54,11 +54,12 @@
5454// User memory layout.
5555// Address zero first:
5656// text
5757// original data and bss
58// fixed-size stack
59// expandable heap
58// expandable heap, up to MAXHEAP
6059// ...
60// guard page
61// stack, growing down from USTACKTOP, at most USERSTACK pages
6162// TRAPFRAME (p->trapframe, used by the trampoline)
6263// TRAMPOLINE (the same page as in the kernel)
6364#define TRAPFRAME (TRAMPOLINE - PGSIZE)
6465
kernel/param.h
@@ -10,5 +10,5 @@
1010#define LOGBLOCKS (MAXOPBLOCKS * 3) // max data blocks in on-disk log
1111#define NBUF (MAXOPBLOCKS * 3) // size of disk block cache
1212#define FSSIZE 2000 // size of file system in blocks
1313#define MAXPATH 128 // maximum file path name
14#define USERSTACK 1 // user stack pages
14#define USERSTACK 64 // max user stack pages
kernel/vm.c
@@ -325,21 +325,8 @@ err:
325325 uvmunmap(new, start, (i - start) / PGSIZE, 1);
326326 return -1;
327327}
328328
329// mark a PTE invalid for user access.
330// used by exec for the user stack guard page.
331void
332uvmclear(pagetable_t pagetable, uint64 va)
333{
334 pte_t *pte;
335
336 pte = walk(pagetable, va, 0);
337 if (pte == 0)
338 panic("uvmclear");
339 *pte &= ~PTE_U;
340}
341
342329// Copy from kernel to user.
343330// Copy len bytes from src to virtual address dstva in a given page table.
344331// Return 0 on success, -1 on error.
345332int
c10daef Add growstack, a test for the growable stack
Makefile
@@ -149,8 +149,9 @@ UPROGS=\
149149 $U/_logstress\
150150 $U/_forphan\
151151 $U/_dorphan\
152152 $U/_sync\
153 $U/_growstack\
153154
154155fs.img: mkfs/mkfs README $(UPROGS)
155156 mkfs/mkfs fs.img README $(UPROGS)
156157
user/growstack.c
@@ -0,0 +1,292 @@
1// growstack: tests for the growable user stack.
2// growstack runs every check; growstack NAME runs one.
3// Each check runs in a child, so that the stack it grows,
4// or the kill it expects, does not touch this process.
5
6#include "kernel/param.h"
7#include "kernel/types.h"
8#include "kernel/riscv.h"
9#include "kernel/memlayout.h"
10#include "user/user.h"
11
12#define FRAME 1024 // bytes of local array in each recursive call
13
14int failed;
15uint64 lowest; // lowest sp seen by dive()
16int report = -1; // if >= 0, dive() writes its sp to this fd
17
18void forkbottom(void);
19
20// Recurse depth more levels, each with FRAME bytes of locals filled
21// with its own depth; check them on the way back. At the bottom,
22// call forkbottom() if dofork is set. Returns 1 if every array
23// was intact.
24int
25dive(int depth, int dofork)
26{
27 volatile char a[FRAME];
28 uint64 sp = r_sp();
29 int ok;
30
31 for (int i = 0; i < FRAME; i++)
32 a[i] = depth;
33 if (sp < lowest)
34 lowest = sp;
35 if (report >= 0)
36 write(report, &sp, sizeof(sp));
37 if (depth > 0)
38 ok = dive(depth - 1, dofork);
39 else {
40 ok = 1;
41 if (dofork)
42 forkbottom();
43 }
44 for (int i = 0; i < FRAME; i++) {
45 if (a[i] != (char)depth)
46 ok = 0;
47 a[i] = ~depth; // scribble, so a shared copy would show
48 }
49 return ok;
50}
51
52// run f in a child; return its exit status.
53int
54inchild(void (*f)(void))
55{
56 int pid = fork();
57 if (pid < 0) {
58 printf("growstack: fork failed\n");
59 exit(1);
60 }
61 if (pid == 0) {
62 f();
63 exit(0);
64 }
65 int status;
66 wait(&status);
67 return status;
68}
69
70void
71deep1(void)
72{
73 lowest = USTACKTOP;
74 int ok = dive(64, 0);
75 printf("growstack: deep: 65 calls used %ld bytes of stack\n",
76 USTACKTOP - lowest);
77 exit(ok && USTACKTOP - lowest > 64 * FRAME ? 0 : 1);
78}
79
80// deep: recursion far beyond one page of stack.
81void
82deep(void)
83{
84 int st = inchild(deep1);
85 printf("growstack: deep: %s\n", st == 0 ? "OK" : "FAIL");
86 if (st != 0)
87 failed = 1;
88}
89
90int forkchild;
91
92void
93forkbottom(void)
94{
95 int pid = fork();
96 if (pid < 0) {
97 printf("growstack: fork: fork failed\n");
98 exit(1);
99 }
100 if (pid == 0) {
101 forkchild = 1;
102 return; // the child unwinds its copy, checking and scribbling
103 }
104 int status;
105 wait(&status); // the parent unwinds only after the child is done
106 if (status != 0) {
107 printf("growstack: fork: child's copy of the stack was wrong\n");
108 exit(1);
109 }
110}
111
112void
113fork1(void)
114{
115 int ok = dive(64, 1);
116 if (forkchild)
117 exit(ok ? 0 : 1);
118 if (!ok)
119 printf("growstack: fork: parent's stack changed under it\n");
120 exit(ok ? 0 : 1);
121}
122
123// fork: fork with 65 frames on the stack. The child checks every
124// frame and scribbles over it; then the parent checks its own.
125void
126forktest(void)
127{
128 int st = inchild(fork1);
129 printf("growstack: fork: %s\n", st == 0 ? "OK" : "FAIL");
130 if (st != 0)
131 failed = 1;
132}
133
134// read into buf, which lies up to 4 pages below the caller's
135// frame: nothing has touched those pages, so only the kernel's
136// copyout() can grow the stack to them. b is 50 bytes below a page
137// boundary inside buf, so the 100 bytes land in two such pages.
138int
139readlow(int fd)
140{
141 char buf[4 * PGSIZE];
142 char *b = (char *)PGROUNDUP((uint64)buf + PGSIZE) - 50;
143
144 if (read(fd, b, 100) != 100)
145 return 0;
146 for (int i = 0; i < 100; i++)
147 if (b[i] != (char)i)
148 return 0;
149 return 1;
150}
151
152void
153read1(void)
154{
155 int fds[2];
156 char data[100];
157
158 for (int i = 0; i < 100; i++)
159 data[i] = i;
160 if (pipe(fds) < 0 || write(fds[1], data, 100) != 100)
161 exit(1);
162 exit(readlow(fds[0]) ? 0 : 1);
163}
164
165// read: read() into stack pages nobody has touched.
166void
167readtest(void)
168{
169 int st = inchild(read1);
170 printf("growstack: read: %s\n", st == 0 ? "OK" : "FAIL");
171 if (st != 0)
172 failed = 1;
173}
174
175void
176forever(void)
177{
178 dive(1 << 20, 0);
179}
180
181// overflow: unbounded recursion must be killed at the limit, not
182// before it, and not below it. The child reports every frame's sp
183// through a pipe; the last one is the deepest frame it reached.
184void
185overflow(void)
186{
187 int fds[2];
188 uint64 sp, last = 0;
189
190 if (pipe(fds) < 0) {
191 printf("growstack: overflow: pipe failed\n");
192 exit(1);
193 }
194 int pid = fork();
195 if (pid == 0) {
196 close(fds[0]);
197 report = fds[1];
198 forever();
199 exit(0);
200 }
201 close(fds[1]);
202 while (read(fds[0], &sp, sizeof(sp)) == sizeof(sp))
203 last = sp;
204 close(fds[0]);
205 int status;
206 wait(&status);
207 // the frame below the last one did not fit above USTACKBASE.
208 int ok = status == -1 && last >= USTACKBASE &&
209 last < USTACKBASE + FRAME + 128;
210 printf("growstack: overflow: status %d, deepest sp 0x%lx, limit 0x%lx: %s\n",
211 status, last, USTACKBASE, ok ? "OK" : "FAIL");
212 if (!ok)
213 failed = 1;
214}
215
216int collidefd;
217
218void
219collide1(void)
220{
221 // grow the heap to MAXHEAP, lazily, in steps sbrk's int can take.
222 uint64 top = (uint64)sbrk(0);
223 while (top < MAXHEAP) {
224 uint64 n = MAXHEAP - top;
225 if (n > (1 << 30))
226 n = 1 << 30;
227 if (sbrklazy(n) == SBRK_ERROR)
228 exit(1);
229 top = (uint64)sbrk(0);
230 }
231 if (top != MAXHEAP)
232 exit(2);
233 if (sbrklazy(1) != SBRK_ERROR || sbrk(PGSIZE) != SBRK_ERROR)
234 exit(3); // the heap must not grow past MAXHEAP
235 *(volatile char *)(MAXHEAP - 1) = 1; // the heap's last byte works
236 write(collidefd, "h", 1);
237 *(volatile char *)MAXHEAP = 1; // the guard page: must be killed
238 exit(4);
239}
240
241// collide: the heap grows up to MAXHEAP and no further, and the
242// guard page between heap and stack kills.
243void
244collide(void)
245{
246 int fds[2];
247 char c = 0;
248
249 if (pipe(fds) < 0) {
250 printf("growstack: collide: pipe failed\n");
251 exit(1);
252 }
253 collidefd = fds[1];
254 int st = inchild(collide1);
255 close(fds[1]);
256 read(fds[0], &c, 1);
257 close(fds[0]);
258 int ok = c == 'h' && st == -1;
259 printf("growstack: collide: %s\n", ok ? "OK" : "FAIL");
260 if (!ok) {
261 printf("growstack: collide: heap checks %s, exit status %d\n",
262 c == 'h' ? "passed" : "failed", st);
263 failed = 1;
264 }
265}
266
267struct test {
268 void (*f)(void);
269 char *name;
270} tests[] = {
271 {deep, "deep"}, {forktest, "fork"}, {readtest, "read"},
272 {overflow, "overflow"}, {collide, "collide"},
273};
274
275int
276main(int argc, char *argv[])
277{
278 int ran = 0;
279
280 for (int i = 0; i < sizeof(tests) / sizeof(tests[0]); i++) {
281 if (argc > 1 && strcmp(argv[1], tests[i].name) != 0)
282 continue;
283 tests[i].f();
284 ran++;
285 }
286 if (ran == 0) {
287 printf("usage: growstack [deep|fork|read|overflow|collide]\n");
288 exit(1);
289 }
290 printf(failed ? "growstack: SOME FAILED\n" : "growstack: ALL OK\n");
291 exit(failed);
292}

6. Verify and measure

On the branch (ext/13-growstack, 7 commits), built with the project toolchain and run on 3 harts (-smp 3 -m 128M), one boot:

$ growstack
growstack: deep: 65 calls used 70944 bytes of stack
growstack: deep: OK
growstack: fork: OK
growstack: read: OK
usertrap(): unexpected scause 0xf pid=8
            sepc=0x36a stval=0x3ffffbdef8
growstack: overflow: status -1, deepest sp 0x3FFFFBE330, limit 0x3FFFFBE000: OK
usertrap(): unexpected scause 0xf pid=9
            sepc=0xce stval=0x3ffffbd000
growstack: collide: OK
growstack: ALL OK
$ usertests -q
usertests starting
test copyin: OK
[...]
test stacktest: usertrap(): unexpected scause 0xd pid=6569
            sepc=0x1c40 stval=0x3ffffbde90
OK
[...]
test lazy_copy: OK
test lazy_copyinstr: OK
test lazy_sbrk: OK
test partial_write: OK
test unlinkcwd: OK
ALL TESTS PASSED
$ growstack
growstack: deep: 65 calls used 70944 bytes of stack
growstack: deep: OK
growstack: fork: OK
growstack: read: OK
usertrap(): unexpected scause 0xf pid=6661
            sepc=0x36a stval=0x3ffffbdef8
growstack: overflow: status -1, deepest sp 0x3FFFFBE330, limit 0x3FFFFBE000: OK
usertrap(): unexpected scause 0xf pid=6662
            sepc=0xce stval=0x3ffffbd000
growstack: collide: OK
growstack: ALL OK

The two usertrap() lines in each growstack run are the expected kills: the overflow child’s store into the guard page below the stack (stval 0x3ffffbdef8), and the collide child’s store into the guard page above the heap (0x3ffffbd000, its first byte). Both are the same page, seen from two sides. In usertests, stacktest’s kill is the guard doing its job; usertests -q passing shows that bad pointers, the trapframe, the trampoline, MAXVA, lazy and eager sbrk, exec’s argument limit and memory accounting all still work.

Every commit builds with make kernel/kernel fs.img, and usertests -q printed ALL TESTS PASSED on 3 harts at each of the 7 commits. At commits 1-5 (old layout, with growstack added to the tree) growstack printed deep, fork, read and overflow FAIL and collide OK; from commit 6 on, ALL OK.

A counting copy of the branch (instrumentation not on the branch) counted every stack page grown, and how many of them came from page faults, and recorded, for every address space freed, how many stack pages it had. A counting copy of the original kernel printed only free pages. Both printed their counters on Ctrl-P; one boot each.

Who uses how much stack.

command	stack growths (by page faults)	address spaces freed, by stack pages
boot and `echo hi`	3 (0)	1 page: 3 (and one empty: the first process’s, before its exec)
`growstack deep`	18 (17)	1 page: 2, 18 pages: 1
`growstack` (all five checks)	100 (97)	1 page: 3, 3 pages: 1, 18 pages: 3, 64 pages: 1
`usertests -q`	3 (0)	1 page: 6,649

Every growth that did not come from a page fault came from a kernel copy: one for each exec that got as far as copying its arguments (copyout into the new page table), and two in growstack read (copyout from piperead). growstack’s 97 faults are 17 (deep) + 17 (fork) + 63 (overflow). The forked grandchild in the fork check grew nothing: uvmcopy gave it all 18 pages.

The usertests -q row is the interesting one. 6,649 address spaces were torn down during the run, and every one had exactly one stack page: no test in usertests ever needed more than 4 KiB of stack. That is why the original layout was enough for xv6’s own programs, and why a growable stack costs them nothing. Each of them uses one stack page, as before, and no guard page.

Memory. Free pages after boot, with init and sh running: 32,545 on the original kernel, 32,547 on the branch. The 2 pages are the two old guard pages, which uvmalloc allocated and uvmclear only hid from user mode. The same page was also copied by every fork, since it lies below sz: on the original kernel each of usertests’ thousands of forks copied two pages of stack (the guard and the stack), on the branch one. (That last point is reasoned from uvmcopy, not counted.)

7. Go further

Shrink the stack. Pages the stack grew into stay mapped until exit, even after the recursion returns. Free pages below sp on some event (a system call, a timer tick), and think about what makes it safe: can the program still use memory below its own sp? (RISC-V’s calling convention has no “red zone”, but check what the compiler does.)
Close the guard’s hole. A frame larger than a page can jump over a one-page guard. Make the gap larger, or check at fault time that the address is not far below the faulting sp, and write a test with a 64 KiB local array near the limit.
A per-process limit. Replace the constant with a field set by a new system call (setstacklimit), as Unix does with RLIMIT_STACK. Which of the places you changed now need the process instead of a constant, and how does fork inherit the limit?
Randomize the top. Start the stack a random number of pages below USTACKTOP at each exec. What does that defend against, and what in this lab would have to learn the per-process top?
Copy-on-write stacks. With lab 11, fork would share the stack pages instead of copying them. The fork check here scribbles over every frame in the child: what does that cost under copy-on-write, page by page?