Step 1 of 18

The parser needs memory

The shell’s child (Tour 20: fork) calls parsecmd("ls\n"). The parser builds a small tree of command structures, and the first is an execcmd, allocated with malloc.

This is the child’s first malloc ever. The shell itself never calls it, so the child’s heap, inherited from the shell, is empty: p->sz is still 0x5000, ending right after the stack page. malloc has no memory to hand out and must ask the kernel for some.

Note where we are: in the child, on hart 2. Whatever happens to this address space happens to the child’s page table only, not to the shell’s on hart 0.

Step 2 of 18

malloc asks for 64 KiB at a time

malloc finds its free list empty and calls morecore. morecore never asks the kernel for less than 4096 units of 16 bytes (sizeof(Header)): 65536 bytes, 64 KiB, 16 pages. Asking in big chunks keeps the number of system calls low; malloc will carve this chunk up for many later requests.

sbrk returns the old end of memory, which is the start of the new block: 0x5000. morecore writes a header there, at the very start of the new memory, and hands the block to free to put it on the free list.

SBRK_ERROR, (char *)-1, means the kernel refused.

Step 3 of 18

Two flavors of one system call

Both sbrk and sbrklazy are one-line wrappers around the same system call, sys_sbrk, with a second argument choosing the policy: SBRK_EAGER (1) or SBRK_LAZY (2), from kernel/vm.h.

malloc uses the eager one. The stub puts SYS_sbrk (12) in a7, n = 65536 in a0, 1 in a1, and executes ecall (Tour 5: Life of a system call).

Why would anyone choose eager? It fails early and cleanly: if memory is short, sbrk returns -1 now, and malloc returns 0 for the program to handle. With lazy allocation, running out of memory is discovered later, at some random store instruction, and the only thing the kernel can do then is kill the process.

Step 4 of 18

sys_sbrk chooses a path

sys_sbrk fetches n and t, and records the current size as the return value: addr = 0x5000.

Then the policy: eager (t == SBRK_EAGER), or any shrink (n < 0), goes through growproc, which really changes the page table. Only lazy growth takes the other branch. Shrinking is always eager, because pages that exist must be freed now; we return to that at the end.

Our gdb run printed exactly this call: SBRK hart=… pid=3 name=sh n=65536 t=1 addr=0x5000.

Step 5 of 18

growproc, with no lock

growproc first checks the ceiling: the new end may not pass TRAPFRAME (0x3fffffe000), or the heap would run into the trapframe and trampoline pages at the top of the address space (Tour 25: A user address space). 0x5000 + 0x10000 is far below it.

Then uvmalloc maps pages from 0x5000 to 0x15000, and p->sz becomes 0x15000.

No lock is taken, not even p->lock, though p->sz and p->pagetable are fields of a struct proc in a table shared by all harts. kernel/proc.h:95 explains: these fields are private to the process. Only the process itself, in its own system calls, changes them, and an xv6 process has a single thread, so there is never a second writer. No other process reads them while this one is alive: a parent’s wait frees them only once the child is a zombie (Tour 21: exit, wait and zombies).

Step 6 of 18

uvmalloc maps 16 zeroed pages

uvmalloc loops over page addresses 0x5000, 0x6000, …, 0x14000. For each:

1. kalloc a physical page;
2. memset it to zero (more below);
3. mappages it with PTE_R | PTE_U | PTE_W.

All 16 pages fall at level-0 indices 5 to 20, inside the same level-0 page-table page that already maps the code, data and stack (one level-0 page covers 2 MiB). So walk finds every intermediate table already present, and no page-table page is allocated: exactly 16 calls to kalloc.

If kalloc runs dry halfway, uvmdealloc frees the pages added so far and uvmalloc returns 0. All or nothing: the process never ends up with a half-grown heap and a sz that disagrees with its page table.

Why zero? A page from kalloc was last used for something else (as a user page, a page table, a trapframe or a pipe buffer). Handing it over unwiped would leak that data to this program. Zeroing also gives C programs what they expect from fresh memory.

Step 7 of 18

kmem.lock, where the harts meet

kalloc is the one place in this whole path that touches memory shared by all harts: the free list. It takes kmem.lock, pops the first page, and releases. Five instructions or so under the lock, with interrupts off on hart 2 for that time.

The fill with junk (5s) on line 80 is done after releasing the lock. Once the page is off the list, it belongs to this caller alone, so there is no reason to make other harts wait while 4096 bytes are written. (And then uvmalloc overwrites the junk with zeros. The junk fill exists to catch kernel code that uses a page without initializing it.)

Tour 27: The physical page allocator covers the allocator in detail.

Step 8 of 18

The heap is ready

sys_sbrk returns 0x5000, the start of the new memory. The child’s address space now has a 64 KiB heap:

0x15000  sz
         heap: 16 pages, R W U, all present and zero
0x05000  old sz
0x04000  stack
0x03000  guard page
...

malloc carves the execcmd out of the top of that block (morecore freed the whole block onto the free list, and malloc takes from the end of a free chunk) and parsing continues.

This child will call exec a moment later, which frees all 16 pages without the program having used more than about 200 bytes of them (Tour 22: exec). Eager allocation paid for 16 pages, 16 kallocs and 64 KiB of zeroing that nobody needed. That is the case for laziness.

Step 9 of 18

Asking lazily for a gibibyte

A new scenario: you type usertests lazy_alloc. usertests (pid 3) forks a child (pid 4) to run the test, and waits for it. (This is after a fresh boot, so the shell’s child running usertests is pid 3.) In our gdb run the child ran on hart 0.

The test calls sbrklazy(1 << 30): one GiB, on a machine that has 128 MiB of RAM. Eagerly, that would fail. Lazily, it succeeds. Then the loop stores into one 8-byte word every 64 pages (every 256 KiB), starting one page above the old end. That touches 4096 of the 262,144 pages in the region, and checks that the values read back.

The interesting question is what happens at each of those stores.

Step 10 of 18

Lazy growth only moves a number

With t = SBRK_LAZY and n > 0, sys_sbrk takes the second branch. Two checks, and then the entire “allocation”:

• addr + n < addr: the sum wrapped around 2^64 (it cannot while sz stays below TRAPFRAME and n is an int, but it is cheap insurance);
• addr + n > TRAPFRAME: the same ceiling as growproc;
• myproc()->sz += n.

gdb printed n=1073741824 t=2 addr=0x12000: usertests had 0x12000 bytes, and now p->sz = 0x40012000. No page was allocated, and the page table did not change.

From now on, sz and the page table disagree: addresses below sz are legal, but most of them are not mapped. The kernel has promised memory it has not provided. That promise is kept by vmfault, called from usertrap for a user access, and from copyin, copyinstr and copyout when the kernel itself touches user memory on the program’s behalf (Tour 28: Crossing the user/kernel boundary in memory).

Step 11 of 18

A store to a page that is not there

The first iteration stores i at i = 0x13000. The compiler made this one instruction, sd a5,0(a5) at 0x495e in user/usertests.asm.

The hardware walks the page table for 0x13000 (Tour 25: A user address space): level 2 and level 1 are there (they also map the program), but the level-0 entry for page 0x13 is zero, V = 0. The store cannot complete. The CPU raises a store/AMO page fault (it is handled in S-mode, not M-mode, only because start delegated all exceptions with medeleg at kernel/start.c:31):

These are the values gdb printed. As for a system call, sepc points at the trapping instruction; the difference is that this store did not complete, so the kernel will not add 4, and sret will retry it. The trap goes through uservec into usertrap exactly as in Tour 5: Life of a system call (Tour 10: Exceptions and faults surveys the other exceptions).

Step 12 of 18

usertrap recognizes a lazy page

usertrap saves sepc into the trapframe, as for any trap. scause is not 8, so it is not a system call; devintr says it is not a device interrupt. The third branch tests for a page fault: scause 15 (store) or 13 (load), and vmfault agrees to fix it.

Note what is not in the list: 12, the instruction page fault. Jumping into lazily allocated memory is not supported; it falls to the last branch and the process is killed.

Note also the interrupt state. Only the system-call branch calls intr_on. For a page fault, interrupts stay off for the whole of vmfault, including the kalloc and the memset of a page. That is fine: the work is short and never sleeps. (When copyin or copyout calls vmfault during a system call, interrupts are on unless the caller holds a spinlock, as consoleread and piperead do.)

No epc += 4 here. When usertrap returns, sret goes back to 0x495e, and the sd runs again, this time successfully.

Which stack is all this on? The same one as a system call. The hardware pushes nothing when it takes the fault. uservec saved the user’s sp into the trapframe (kernel/trampoline.S:41) and loaded the top of pid 4’s kernel stack (kernel/trampoline.S:76), which is empty every time a process enters from user mode. The only difference from a system call is how little gets pushed:

pid 4's kernel stack, during the fault
  top ─► usertrap
         vmfault
         kalloc / mappages …   (while they run)

The faulting store was to the heap. The user stack page was not involved, and is untouched until sret puts the saved sp back.

Step 13 of 18

vmfault keeps the promise

vmfault decides whether this fault is a lazy page:

1. va >= psz: beyond the process size, a genuinely bad address. Refuse.
2. Round down to the page, 0x13000.
3. ismapped: if the page is already mapped, this is not a missing page but a permission problem (more in step 15). Refuse.
4. kalloc a page, zero it, and mappages it with R W U. Return its physical address.

0x13000 < 0x40012000, and it is not mapped, so a page appears. Since the level-0 page for 0x0–0x1fffff already existed, no page-table page was needed. The next seven faults (0x53000, gdb’s second hit, then 0x93000 … 0x1d3000) land in the same 2 MiB region, so they don’t need one either. The ninth, at 0x213000, is the first in a new 2 MiB region: there walk, called inside mappages, allocates a level-0 page-table page (another kalloc), and the same happens every 8 faults after that. By the end of the test, 4096 data pages and 511 level-0 pages, about 18 MiB, have been allocated: about 1.8% of the GiB that was “allocated” by the system call.

The read parameter is not used: loads and stores are treated the same.

Step 14 of 18

Retry, 4096 times

vmfault returned a non-zero physical address, so the branch is satisfied. The process is not killed, which_dev is 0 so there is no yield, and usertrap returns to user mode through prepare_return and userret, with sepc = 0x495e.

The sd executes again. On the way out, userret ran sfence.vma after installing the user page table; the RISC-V spec requires that fence before a hart is guaranteed to see a PTE that just changed from invalid to valid. So the hardware walks the page table afresh, finds the new PTE, and the 8 bytes land in a fresh, zeroed page. (Without that fence the store could fault a second time, and vmfault would refuse it because the page is now mapped.)

The loop continues to 0x53000, which faults the same way, and so on. Our gdb counter on vmfault's allocation counted 4096 hits during the test, one per touched page, exactly as predicted. The second loop reads the same 4096 words; they are all mapped by now, so it runs without a single fault.

From the program’s point of view, nothing happened: a store took a few microseconds longer than usual. That invisibility is what makes lazy allocation a policy the kernel can choose without the program’s cooperation, apart from asking for it with sbrklazy.

Step 15 of 18

The guard page refuses

Now a fault that must not be fixed. Take ls from Tour 22: exec, with sz = 0x4000, its stack at 0x3000–0x3fff and its guard page at 0x2000. Suppose (as a thought experiment; ls does not do this) a deep recursion pushed sp below 0x3000 and stored to 0x2ff8.

The hardware finds the PTE for 0x2000: valid, R W, but no U. A user-mode store fails the U check: scause 15, stval = 0x2ff8, the same exception as a lazy page.

vmfault: 0x2ff8 < sz, so the first check passes. But ismapped finds the page mapped (V is set) and returns 1, so vmfault returns 0. In usertrap the branch fails, and the last one runs: it prints

usertrap(): unexpected scause 0xf pid=3
            sepc=… stval=0x2ff8

calls setkilled, and line 81 sends the process to kexit with status -1.

With lazy allocation, it matters that the guard page is mapped without U rather than unmapped: an unmapped page below sz would look exactly like a lazy page, and vmfault would cheerfully give the runaway stack a fresh page.

Compare the two kinds of fault (The stacks of xv6):

The user stack itself never faults lazily: kexec maps its one page eagerly (kernel/exec.c:91), and it cannot grow, because the heap begins right above it. So a stack that creeps downward off its page, a frame smaller than a page at a time, faults at the guard. That is never a missing page to supply. (A single frame larger than 4 KiB could jump over the one guard page into the data below; xv6 does not catch that.)

One more thing makes this fault survivable: ls’s sp now points into a page it may not touch, yet the kernel never needs it. uservec stores sp into the trapframe without using it and switches to ls’s kernel stack, so usertrap, vmfault and kexit all run on a stack that is fine. The broken user stack is simply freed with the rest of ls’s memory when its parent reaps it.

Step 16 of 18

Giving memory back

usertests’s lazy_unmap test does the reverse: after a lazy GiB with some pages touched, a child calls sbrklazy(-(1 << 30)). A negative n always goes to growproc (step 4), which calls uvmdealloc(pagetable, sz, sz + n).

uvmdealloc works in whole pages: it unmaps from PGROUNDUP(newsz) up to PGROUNDUP(oldsz), with do_free = 1, so uvmunmap gives every present page back to kfree. Pages that were never touched have no PTE, and uvmunmap skips them (its comment at kernel/vm.c:191 says “It’s OK if the mappings don’t exist”; the skips are at kernel/vm.c:203 and kernel/vm.c:205). That tolerance is what makes lazy regions shrinkable. It still visits all 262,144 page addresses, calling walk for each.

What is not freed: the level-0 page-table pages that are now empty. They stay until the process exits and freewalk frees the whole table.

Then p->sz drops, and the test’s child stores to an address in the freed region. That address is now >= sz, vmfault refuses, and the child is killed, which is what the test expects (it treats exit status 0 as “memory not unmapped”).

Step 17 of 18

No TLB flush needed

The hart’s TLB (translation lookaside buffer) caches translations. If it still held “page 0x13000 → physical page X” after X was freed and reused by another process, this process could read and write someone else’s memory. Real kernels must carefully flush TLB entries when unmapping. uvmdealloc doesn’t flush anything. Why is that safe?

Because on xv6 a user translation can only be in a TLB while the hart is in user mode or in the trampoline. Look at uservec: on every trap from user mode, right after csrw satp installs the kernel page table, sfence.vma zero, zero (line 95) discards all cached translations. So by the time any kernel code runs, including uvmdealloc, this hart’s TLB holds no user translations at all. On the way back, userret switches to the user table between two more sfence.vmas (lines 110–112), so translations are reloaded fresh from the page table, without the freed pages.

(Simplified: xv6 pays for this with a full flush on every trap and return. Kernels that keep TLB entries across traps use address-space IDs and targeted flushes.)

Step 18 of 18

What growth costs

The two policies side by side, for the runs in this tour:

And the locks: none for the address space itself, ever. p->sz and the page table belong to one single-threaded process, and the hart runs on the kernel page table while they change. The only shared state is the free-page list, guarded by kmem.lock for a handful of instructions per page. Even the TLB, the per-hart cache that is a nightmare in other kernels, is handled by the trampoline’s flushes without any coordination between harts.

The ideas to keep: sz is a promise and the page table is what has been delivered; a page fault is a chance to deliver late; and a guard page works only because it is present and forbidden, not absent.