Step 1 of 17

The linker decides the addresses

Every xv6 user program is linked with this linker script. Line 5 starts the program at virtual address 0. Code (.text) and read-only data (.rodata) follow, then line 23 jumps to the next 4096-byte boundary before writable data (.data, then .bss). Code and data must be on different pages, because permissions are set per page: code should be executable and not writable, data the reverse.

${TOOLPREFIX}readelf -l user/_sh (TOOLPREFIX is your RISC-V toolchain’s prefix; see Tour 1: From make qemu to a disk image and a kernel) shows the result as two loadable segments:

So sh’s code spans two pages (0x0 and 0x1000), and its data fits in one page at 0x2000. The symbol table puts the static buf of main at 0x2020, inside .bss, and the entry point start at 0x9d0.

Every program uses the same addresses. That is not a conflict, because each process gets its own page table: 0x2020 in sh and 0x2020 in ls are different bytes.

Step 2 of 17

The whole map

kexec (Tour 22: exec) placed the two segments, then a guard page and a one-page stack above them, and the kernel added two special pages at the very top. Here is sh’s address space, with every mapped page:

0x40_0000_0000  MAXVA (256 GiB), nothing at or above
0x3f_ffff_f000  TRAMPOLINE   R X     (shared kernel code)
0x3f_ffff_e000  TRAPFRAME    R W     (sh's saved registers)
                 ... unmapped: about 256 GiB of nothing ...
0x00_0000_5000  sz: end of sh's memory; the heap would grow from here
0x00_0000_4000  stack        R W U   (sp starts at 0x4fe0)
0x00_0000_3000  guard page   R W     (no U)
0x00_0000_2000  data + bss   R W U   (buf at 0x2020)
0x00_0000_1000  code         R X U
0x00_0000_0000  code         R X U   (start at 0x9d0)

p->sz, the process size, is 0x5000: everything from 0 up to it is the program’s own memory. sh itself never calls malloc (its child does the parsing), so sh’s heap stays empty: 0 bytes, for its whole life.

The comment on lines 54–62 lists the same order. The two top pages are the only ones not counted in sz.

Step 3 of 17

Why 256 GiB and not 512

Sv39 translates 39-bit virtual addresses: 3 × 9 bits of page-table index plus 12 bits of offset. That would give 2^39 bytes, 512 GiB.

But the hardware requires bits 63…39 of an address to be copies of bit 38. An address with bit 38 set therefore looks like 0xffffffc000000000, a huge 64-bit number. xv6 avoids that complication by never using bit 38: MAXVA is 2^38 = 0x4000000000, and every valid user or kernel virtual address is below it.

TRAMPOLINE is MAXVA - PGSIZE = 0x3ffffff000 and TRAPFRAME is one page lower, 0x3fffffe000. walk panics on any address at or above MAXVA, and walkaddr and copyout reject them, so a user pointer like 0x8000000000 never reaches the page table at all.

Step 4 of 17

Two pages every process has

Every user page table starts life in proc_pagetable (called here from the exec that made sh): an empty top-level page, then two mappings.

• The trampoline page at TRAMPOLINE, pointing at the kernel’s own trampoline code, physical 0x80006000 in this build. R X, no U.
• This process’s trapframe at TRAPFRAME, pointing at the page allocproc allocated for it. R W, no U.

Neither page has PTE_U, so user code cannot touch either: if sh loaded from 0x3fffffe000, it would take a page fault and be killed. They are mapped in the user page table only for the supervisor, who runs the trampoline code while satp still points at the user table (Tour 7: The trampoline and the trapframe).

Step 5 of 17

The register that names the page table

The hardware finds a page table through satp: the top 4 bits select the mode (8 = Sv39), and the low 44 bits hold the physical page number of the top-level page-table page, its address divided by 4096.

In our run, exec built sh’s top-level page at physical 0x87f41000. So:

MAKE_SATP(0x87f41000) = (8 << 60) | (0x87f41000 >> 12)
                      = 0x8000000000000000 | 0x87f41
                      = 0x8000000000087f41

userret wrote that value into hart 0’s satp the last time sh returned to user mode. From then on, every address sh uses is translated through that table.

Step 6 of 17

One load from buf

Our specimen: getcmd has just read a line, and line 140 tests buf[0] == 0 (empty input means end of file). buf is main’s static array, passed in as a pointer, so this compiles to a one-byte load from address 0x2020.

The CPU never sends 0x2020 to memory. In user mode with Sv39 on, every address is virtual: the hardware first looks for it in the TLB (translation lookaside buffer), and on a miss it walks the page table in memory, starting from satp. Let’s do that walk ourselves, the way the hardware does it (and the way walk does it in software).

Step 7 of 17

Cutting the address into fields

The comment above walk gives the split. Write 0x2020 in binary and cut:

0x2020 = 0b 000000000 000000000 000000010 000000100000
            |  L2   | |  L1   | |  L0   | |  offset  |
            bits     bits      bits      bits
            38..30   29..21    20..12    11..0

Each index picks one of the 512 eight-byte entries in a 4096-byte page-table page (512 × 8 = 4096). The offset is carried through unchanged: pages are 4096 bytes, so the low 12 bits are the position inside the page.

For small addresses like this one, the upper indices are 0. All of sh’s memory (0x0–0x4fff) shares the same level-2 and level-1 entries and differs only in the level-0 index, 0 through 4.

Step 8 of 17

PX, the field extractor

PX(level, va) is the software version of that cut: shift right by 12 + 9 * level, keep 9 bits.

• PX(2, 0x2020) = (0x2020 >> 30) & 0x1ff = 0
• PX(1, 0x2020) = (0x2020 >> 21) & 0x1ff = 0
• PX(0, 0x2020) = (0x2020 >> 12) & 0x1ff = 2

Lines 401–406 are the other half of the toolkit. A page-table entry stores a physical page number in bits 53…10 and flags in bits 9…0. PTE2PA shifts out the flags and shifts in 12 zero bits to get a byte address; PA2PTE goes the other way; PTE_FLAGS keeps the low 10 bits.

Step 9 of 17

Level 2 and level 1

The hardware (or the loop in walk) now descends. Values are from the gdb dump of sh’s page table:

Level 2. Root page = satp’s PPN × 4096 = 0x87f41000. Entry 0 is at 0x87f41000 + 0 × 8. It holds 0x21fcf401:

• flags 0x001: only V (valid). R, W and X are all 0, which means “this is not a page of memory, it points to the next level”;
• next table = (0x21fcf401 >> 10) << 12 = 0x87f3d000.

Level 1. Entry 0 of 0x87f3d000 holds 0x21fcf001: again only V, pointing to 0x87f3c000, the level-0 page.

If any entry on the way had V = 0, the walk would stop with a page fault. That is what happens for the 256 GiB of unmapped space between sz and TRAPFRAME: the level-2 entries 1 through 254 are all zero, and most of the space is ruled out by a single empty entry per GiB.

Step 10 of 17

The leaf, and the physical byte

Level 0. Entry 2 of 0x87f3c000, at physical 0x87f3c010, holds 0x21fce8d7:

R, W or X is set, so this is a leaf: a real page. The hardware checks the permissions for this access (a load in U-mode: needs U and R; both set), then forms the physical address:

0x87f3a000 + 0x020 = 0x87f3a020

That is where buf[0] lives in RAM, and the byte 'l' of "ls\n" is there. Three page-table reads before the byte itself can be fetched, which is why the TLB caches the answer: later loads from page 0x2000 skip the walk as long as the translation stays in the TLB.

(Right after exec this entry was 0x21fce817: no A, no D. start enables hardware updating of the A and D bits (kernel/start.c:41, Svadu extension (A and D bits)), so the MMU set A and D when getcmd’s memset (user/sh.c:138) stored to the page, and low byte 0x17 became 0xd7; we observed this in our run. The kernel’s copyout of "ls\n" does not set D here, because the kernel writes through its own direct map, not through sh’s table.)

Step 11 of 17

Every leaf in sh's table

The five flag bits xv6 uses, and every leaf entry of sh as gdb printed it right after exec:

By sh’s first read, the hardware had set A or A+D on several entries: page 0x0 → 0x…5b; 0x2000 and 0x4000 → 0x…d7; trapframe → 0x21fd54c7 (A and D, from uservec's stores); trampoline → 0x2000184b (A). Page 0x1000 still had no A.

What the hardware enforces with them:

• U: in user mode, only U pages are accessible. In supervisor mode, U pages are not accessible unless sstatus.SUM is set, which xv6 never does.
• R / W / X: a load needs R, a store needs W, an instruction fetch needs X. So sh cannot overwrite its own code (no W) or run its data (no X).

Any violation raises a page fault: scause 12 (fetch), 13 (load) or 15 (store), with the faulting address in stval (Tour 10: Exceptions and faults).

Notice the physical pages run downward and are not in virtual order: page 0x0 is at 0x87f3e000, and the next two pages the allocator handed out became sh’s level-1 and level-0 page-table pages, so page 0x1000 landed at 0x87f3b000. Contiguous virtual memory need not be contiguous physically; kalloc just hands out whatever page is at the head of its free list (Tour 27: The physical page allocator).

Step 12 of 17

The guard page is mapped, but not for you

Page 0x3000 is present, valid, readable and writable, but has no U bit. kexec allocated it like a stack page and then uvmclear removed PTE_U.

sh’s stack is the page above it, 0x4000–0x4fff, with sp starting at 0x4fe0. Stacks grow downward. A runaway recursion that pushes sp below 0x4000 next touches 0x3fxx, and the U check fails: page fault, and usertrap kills sh instead of letting it scribble over buf and the rest of its data at 0x2000.

Why keep it mapped instead of leaving it empty? Because the page sits inside sz, and vmfault would treat an unmapped page inside sz as a lazily allocated one and quietly supply a fresh page. A mapped page is refused (Tour 26: sbrk, eager and lazy, and page faults shows the check).

Both pages come from one call in kexec: it allocates USERSTACK + 1 pages above the data (kernel/exec.c:91; USERSTACK is 1 in kernel/param.h), clears PTE_U on the lower one (kernel/exec.c:95), and starts sp at the top. Then it copies the arguments in, which is why sp starts at 0x4fe0 and not 0x5000:

sh's user stack, when exec finished
  0x5000  top (= sz)
  0x4ff0  "sh\0"                 argv[0] string, padded to 16 bytes
  0x4fe0  { 0x4ff0, 0 }          the argv[] array; sp = 0x4fe0
    …     main's frame and everything it calls grow down from here
  0x4000  bottom of the one stack page
  0x3000  guard page (no U)

That is all the stack sh will ever have: one fixed page, 4 KiB. It cannot grow, because the heap starts right above it. This is the stack sp points into whenever sh runs in user mode (The stacks of xv6). It exists only in sh’s page table. Apart from exec copying the arguments in, the kernel never puts anything on it: traps and system calls run on sh’s kernel stack instead.

Step 13 of 17

Walking to the top of the address space

The trampoline and trapframe are used in supervisor mode with sh’s table still in satp: uservec stores the user registers to TRAPFRAME before it switches tables. Walk 0x3fffffe000 the same way:

0x3fffffe000 = 0b 011111111 111111111 111111110 000000000000
                  L2 = 255  L1 = 511  L0 = 510  offset 0

0x87f55000 is exactly p->trapframe, as gdb printed it. Entry 511 of the same level-0 page is the trampoline, 0x2000180b, physical 0x80006000.

So sh’s page table uses five page-table pages: the root, a level-1 and level-0 page for the bottom of the address space, and a level-1 and level-0 page for the top. The 254 GiB in between cost nothing.

Notice what is not in that top level-0 page: sh’s kernel stack. In our run sh (pid 2) has process slot 1, so its kernel stack is KSTACK(1) = 0x3fffffb000, entry 507 of the same region. That entry is zero in sh’s table; only the kernel page table maps it. That is why uservec does nothing with sp at this point except save it: at this instant sp still holds sh’s user stack pointer, and the hart has no stack it could use. Line 76 loads p->trapframe->kernel_sp (0x3fffffc000, the top of that page) into sp, and nothing is pushed until line 92 has installed the kernel table, where that address is mapped.

Step 14 of 17

Why the kernel cannot dereference 0x2020

When sh calls read(0, buf, ...), it passes the number 0x2020 to the kernel. Why can’t the kernel write to *(char *)0x2020?

1. Wrong page table. In the kernel, satp holds the kernel page table (Tour 24: The kernel page table and turning paging on), built by kvmmake. Its lowest mapping is the PLIC at 0x0c000000. Nothing is mapped at 0x2020, so the access would page-fault in supervisor mode, and kerneltrap panics on any exception (kernel/trap.c:153).
2. It would mean the wrong thing. Even if something were mapped there, it would be kernel memory, the same for every process, not sh’s buf.
3. The U bit. Even with sh’s table loaded, supervisor mode may not touch U pages, because xv6 leaves sstatus.SUM clear. A kernel bug that follows a user pointer faults instead of silently reading user data.

A user pointer is a number that only sh’s page table can interpret.

The same goes for the stack. The kernel code here runs on sh’s kernel stack at 0x3fffffb000, which sh’s page table does not map, while sh’s user stack at 0x4000 is, to the kernel, just another user page it can reach only by translating it. Two stacks per process, each visible in only one of the two page tables.

Step 15 of 17

So the kernel walks the user table itself

The kernel’s answer is to do in software what the MMU does in hardware. walkaddr takes sh’s page table (p->pagetable, the same 0x87f41000) and 0x2000, calls walk to run the three levels exactly as we did by hand, and returns the physical page 0x87f3a000. The kernel can then write 0x87f3a020 directly, because it maps all of RAM at its own physical address (direct map).

walkaddr refuses entries without V and entries without U: if a program passes the address of its guard page, or of its trapframe, the kernel will not write there on its behalf. That keeps the kernel’s checks equal to the hardware’s.

copyin and copyout wrap this in a loop that handles crossings between pages; Tour 28: Crossing the user/kernel boundary in memory follows them.

Step 16 of 17

Where the heap would go

The address space is not fixed after exec. sz is a movable boundary: growproc maps new pages above it, and the region between the stack and sz is the heap.

sh itself never grows, but its child does. When the shell’s child (pid 3) parses ls, malloc asks for 64 KiB, and growproc moves the child’s sz from 0x5000 to 0x15000: 16 new pages, at level-0 indices 5 through 20 of the same level-0 page (so no new page-table pages). This is on hart 2, in a different page table: the child’s copy, which fork made. sh’s map on hart 0 is unaffected.

The upper limit is TRAPFRAME: the heap may grow until it would collide with the two special pages. Tour 26: sbrk, eager and lazy, and page faults tells the whole story of growth, including lazy growth that maps pages only when they are touched.

Step 17 of 17

What an address space costs

Add up sh:

Nearly half of it is bookkeeping. For a large program the page-table overhead becomes tiny (one level-0 page maps 2 MiB), but for xv6’s small programs it is a real share.

The ideas to keep:

• Same addresses, different memory. Every process sees 0x2020; each page table sends it somewhere else.
• Permissions per page, checked by the hardware on every access: U, R, W, X.
• Sparse tables. One empty entry rules out a whole GiB.
• The kernel cannot trust or use user pointers directly. It translates them itself, with the same checks, against the caller’s own table.