Step 1 of 19

The root of the tree

kvminit (line 69) calls kvmmake, and kvmmake starts with one page from kalloc: the root of the page table. It is the head of the free list, 0x87fff000, the highest page of RAM. Line 27 zeroes it: 512 entries, all invalid.

A page table on RISC-V is a tree of 4096-byte pages, each holding 512 eight-byte page-table entries (PTEs). The CPU’s hardware walks this tree on every memory access it cannot answer from its TLB (translation lookaside buffer). The kernel’s job is only to fill it in.

Paging is still off on hart 0 (satp is 0 since start), so kvmmake writes the tree through physical addresses. Its own stack is physical too: hart 0 is still on the boot stack that _entry set up, its 4 KiB slice of stack0, a plain array in the kernel’s .bss (The stacks of xv6). That works because nothing is translated yet; later, with paging on, it will keep working because the kernel maps physical memory at the same addresses (direct map).

Step 2 of 19

How Sv39 splits an address

xv6 uses Sv39: 39-bit virtual addresses, three levels. A virtual address splits into three 9-bit indexes and a 12-bit offset, which PX extracts:

A PTE holds a physical page number in bits 53–10 (PA2PTE, PTE2PA) and flags in the low bits: V valid, R read, W write, X execute, U user. A valid PTE with none of R, W, X points to the next level down; one with any of them is a leaf. xv6 puts leaves only in level-0 pages, where each maps one 4 KiB page (a leaf higher up would map a 2 MiB or 1 GiB “superpage”, which xv6 never uses).

MAXVA is 1 << 38, 256 GiB: xv6 uses only the lower half of the Sv39 space, to avoid the sign-extension rule for addresses with bit 38 set. So the root index never exceeds 255.

Step 3 of 19

mappages, one page at a time

Every mapping in kvmmake goes through kvmmap, which calls mappages and panics on failure (at boot, failure means the machine is broken).

mappages maps a range page by page: for each page, walk finds (and if needed creates) the level-0 PTE, and line 168 fills it with the physical page number, the permissions and PTE_V. The remap panic on line 167 catches a kernel bug where two mappings overlap.

There is no huge-page support here. The 128 MiB of RAM become 32,768 separate 4 KiB mappings, written one by one. It costs a little memory and boot time and keeps walk simple.

Step 4 of 19

walk grows the tree

walk descends from the root. At each level it reads the PTE for this address’s index. If it is valid, it follows it down. If not, and alloc is set, it takes a new page from kalloc, zeroes it, and points the PTE at it (with only V set: an inner node).

The very first mapping, the UART at 0x10000000, shows it from scratch. With gdb, after kvmmake finished:

The two lower pages, 0x87ffe000 and 0x87ffd000, are the next two pages kalloc handed out, allocated by walk for this mapping. The VIRTIO0 mapping that follows, at 0x10001000, reuses both: same level-1 and level-0 pages, index 1.

Step 5 of 19

Every table page passes through kmem.lock

Each new table page comes from kalloc, which pops the free list under kmem.lock. By the end of kvmmake it will have done this 166 times: 102 page-table pages and 64 kernel-stack pages. The free list’s head moves from 0x87fff000 down to 0x87f59000.

Here every one of those acquisitions succeeds on the first amoswap. Hart 0 is the only hart running kernel code, and its interrupts are off, so nothing can compete for the lock and nothing can interrupt the critical section. The lock is taken because kalloc does not know it is being called at boot, and should not have to. push_off copes with boot too: interrupts were already off when it ran, so it records intena 0 and the release leaves them off (Locks and interrupt state).

Note also line 80: kalloc fills each page with junk (5 bytes) after taking it. walk zeroes table pages itself (line 111), because a table full of 0x05 bytes would be full of “valid” entries.

Step 6 of 19

Devices first

The first three mappings make the device registers reachable once paging is on, each at the same virtual address as its physical address, readable and writable, not executable:

The PLIC is large because it has register blocks for many harts and many interrupt sources; xv6 maps all of it rather than work out which pages it uses. Its range, 0x0c000000–0x10000000, covers level-1 indexes 96–127 of the first gigabyte, each needing its own level-0 table.

Without these mappings, the first printk after paging was turned on would fault: uartputc_sync writes to 0x10000000 with a plain store, and with paging on that store is translated like any other.

Step 7 of 19

Kernel code read-execute, everything else read-write

Then all of RAM, in two parts split at etext (0x80007000, page-aligned by the linker script, Tour 1: From make qemu to a disk image and a kernel):

They need a new level-1 page for the third gigabyte (0x87fdc000) and 64 level-0 pages, 0x87fdb000 down to 0x87f9c000.

Code is not writable, so a stray store into the kernel’s instructions faults instead of silently corrupting them. Data is not executable.

The second range is far more than the kernel’s data. It is every free page: everything kalloc will ever hand out, including the pages of this very page table. The kernel can read and write any physical page through its own address, which is how walk can follow PTE2PA(*pte) as an ordinary pointer once paging is on, and how copyin reaches user pages (Tour 28: Crossing the user/kernel boundary in memory).

Step 8 of 19

The trampoline, mapped twice

The trampoline page, physically at 0x80006000, is already mapped at 0x80006000 by the previous step. Line 47 maps it a second time, at TRAMPOLINE = 0x3ffffff000, the highest page below MAXVA, read-execute. Its PTE is 0x2000180b, the same physical page as the 0x80006000 mapping.

Why twice? Every user page table maps the trampoline at 0x3ffffff000 too (proc_pagetable). The trap code in the trampoline switches satp between a user table and this one (Tour 7: The trampoline and the trapframe). The instruction after the csrw satp is fetched under the new table, so it must be at the same virtual address in both. The direct-mapped copy at 0x80006000 does not exist in user tables; the one at 0x3ffffff000 exists everywhere.

This mapping needs a new level-1 page (0x87f9b000, root index 255) and level-0 page (0x87f9a000, index 511). The kernel stacks, next, will share that level-0 page.

Step 9 of 19

64 kernel stacks with guard pages

proc_mapstacks gives each of the 64 process slots one page of kernel stack, mapped just below the trampoline at KSTACK(i) = TRAMPOLINE - (i+1) × 2 × 4096:

Every other page is left unmapped, so each stack has an unmapped page directly below it: for proc[0], the gap at 0x3fffffc000 (which is also the gap above proc[1]'s stack). Stacks grow down, so a kernel stack that overflows runs into that page, and the access faults instead of silently overwriting a neighbor’s data (guard page). (What happens after the fault is messier; see the quiz.) With a direct-mapped stack, an overflow would silently overwrite whatever page happened to be adjacent in physical memory.

These stacks are virtually contiguous and physically scattered: exactly what a page table is for.

Some facts worth fixing in mind now, because every later tour depends on them:

• All 64 are allocated and mapped here, once, before any process exists. A stack belongs to a slot of proc[], not to a process: procinit records p->kstack = KSTACK(slot) (kernel/proc.c:57), fork never allocates a kernel stack and exit never frees one (Tour 20: fork, Tour 21: exit, wait and zombies).
• They exist only in this page table. No user page table maps them, which is why uservec switches satp to the kernel table before the first push on the kernel stack (Tour 7: The trampoline and the trapframe).
• The stack this code runs on right now has no guard page. Hart 0 is on its slice of stack0, 0x80007890–0x80008890, inside the direct-mapped RAM range. Below hart 0’s slice lie ticks, initproc, kernel_pagetable and started (kernel/kernel.sym); below hart 1’s slice lies hart 0’s. An overflow there would corrupt them silently. That slice becomes hart 0’s scheduler stack later and stays unguarded for the machine’s whole life.

Step 10 of 19

The finished table

kvmmake returns the root, and line 69 stores it in the global kernel_pagetable = 0x87fff000. The root has exactly three valid entries:

In total: 102 page-table pages (1 root, 3 level-1, 98 level-0), which is 408 KiB, holding 49,219 leaf entries (1 + 1 + 16,384 device pages, 7 + 32,761 RAM pages, 1 trampoline, 64 stacks), plus the 64 stack pages themselves. That matches the free list’s head moving from 0x87fff000 to 0x87f59000: 166 pages.

Nothing here is mapped with PTE_U. User mode, if it somehow used this table, could touch none of it.

Step 11 of 19

Building the value for satp

Line 21 of main calls kvminithart. It writes satp with MAKE_SATP(kernel_pagetable):

Together: 0x8000000000087fff. The compiler turned this into a load of kernel_pagetable, a right shift by 12, and an OR with 1 << 63, just before the csrw at 0x80000f2e.

xv6 never uses the ASID field (address-space identifier). Because of that it must flush the TLB on every satp change; with ASIDs, entries for different address spaces could coexist in the TLB.

Step 12 of 19

The fence before the switch

sfence_vma executes sfence.vma zero, zero. The comment says why: “wait for any previous writes to the page table memory to finish”. The page-table walker is a separate part of the CPU that reads memory on its own. The RISC-V spec does not promise that it sees this hart’s earlier ordinary stores to the page table unless an sfence.vma comes between them. Hart 0 just wrote tens of thousands of PTEs with ordinary stores; the fence makes sure the walker will see all of them.

This instruction affects only hart 0. It orders hart 0’s own stores against hart 0’s own page-table walks. It says nothing to harts 1 and 2.

Step 13 of 19

The instant paging turns on

csrw satp, a5 at 0x80000f2e. From the very next instruction on, every address hart 0 uses, for fetching instructions, for loads, for stores, goes through the tree.

The next instruction is at 0x80000f32. Nothing in the program says “jump to the virtual version of the kernel”; the program counter simply keeps counting. This works only because the kernel is mapped at the address where it already is: virtual 0x80000f32 translates (root index 2, level-1 index 0, level-0 index 0) to physical 0x80000f32. If the kernel had been mapped anywhere else, this fetch would get some other bytes, or fault, and since stvec is not set yet the fault would go to whatever address stvec held at reset.

The same holds for the stack: sp is in hart 0’s slice of stack0, just below 0x80008890, which is in the read-write range, so kvminithart’s ret and everything after keep working. sp is not changed by csrw satp: the very same number simply starts being translated, and the direct map translates it to itself. (The kernel stacks at KSTACK(i) are the opposite case: their addresses are not physical addresses, so they work only while this table is installed.)

Step 14 of 19

Flushing hart 0's TLB

The second sfence.vma discards any cached translations in hart 0’s translation lookaside buffer, the small per-hart cache of recent virtual-to-physical lookups. Here there are none worth keeping (in Bare mode there are no translations to cache), but the rule is: after changing satp or a page table, fence before relying on the new translations. xv6 follows it every time it installs a page table: here, and in the trampoline (kernel/trampoline.S:95, kernel/trampoline.S:112). The only satp write without fences is start's w_satp(0), which turns translation off at reset, when nothing is cached.

From now on, hart 0’s TLB will fill with kernel translations as it runs: 0x80000f32 → 0x80000f32, 0x10000000 → 0x10000000, and so on. Each hart has its own TLB. Nothing hart 0 caches is visible to hart 1, and nothing hart 0 flushes is flushed for hart 1.

Step 15 of 19

Harts 1 and 2 are let in, still with paging off

Much later in story time, after userinit, hart 0 sets started with a release store. Harts 1 and 2 see it with acquire loads, leave their loop, and each prints hart N starting with printk.

They are still in Bare mode here. The acquire load of started, the printk and the UART store at 0x10000000 all use physical addresses, exactly as they did before hart 0 built anything. That works because the kernel’s page table maps every one of those addresses to itself: the code is about to switch views, and both views agree.

The acquire is what matters for the next step. Hart 0’s stores to the 102 table pages and to kernel_pagetable happened before its release store of started, so once a hart has seen started == 1 with acquire ordering, it is guaranteed to see all of them too (Tour 3: main: one hart builds the kernel, the others wait).

Step 16 of 19

Harts 1 and 2 load the same table

Line 39 of main: each of harts 1 and 2 calls kvminithart: fence, csrw satp with the same 0x8000000000087fff, fence. The state above is after the csrw. Two things had to be true for this to be safe:

1. They see a complete table. The acquire in the previous step guarantees that hart 0’s page-table stores are visible to harts 1 and 2.
2. Their own walkers see it. The RISC-V spec says an sfence.vma orders every store already visible to the executing hart before that hart’s later page-table walks. Thanks to the acquire, hart 0’s page-table stores are already visible to harts 1 and 2, so each hart’s first sfence.vma guarantees its walker sees the finished table.

Each hart flushes its own TLB. No hart can flush another’s: sfence.vma is local.

Step 17 of 19

One table, three walkers, no lock

Three harts use kernel_pagetable for the rest of the machine’s life: every kernel instruction fetch, every kernel load and store, on every hart. There is no lock around it. Why that is safe:

• Software never changes it after boot. The comment on kvmmap says “only used when booting”, and indeed its only callers are kvmmake and proc_mapstacks. Even the kernel stacks of processes that come and go are mapped once, for all 64 slots, up front. Process creation and exit change only user page tables.
• Data that nobody writes can be read by any number of harts at once. A lock exists to order a writer against readers; with no writer, there is nothing to order.

One honest qualification: the hardware may write it. start enabled Svadu, so when a hart uses a leaf PTE whose accessed (A) bit is clear, or stores through one whose dirty (D) bit is clear, the hardware sets that bit in memory. The PTEs above were written with A = D = 0 (0x...07, 0x...0b). The RISC-V spec requires those updates to be atomic, and xv6 never reads the A and D bits, so the concurrent hardware updates do not need a software lock either.

Step 18 of 19

Every trap comes back to this table

After boot, harts spend much of their time in user page tables. They return to the kernel’s table on every trap. prepare_return stores the current satp, the kernel’s, in each process’s trapframe as kernel_satp (line 116), and uservec in the trampoline loads it back into satp, with an sfence.vma on each side, on the way into the kernel (Tour 7: The trampoline and the trapframe).

Line 117 stores the other half of the pair: kernel_sp = p->kstack + PGSIZE, the top of this process’s KSTACK page. That address means something only under this table. uservec loads it into sp (kernel/trampoline.S:76) while the user table is still installed, but does not push anything until after csrw satp has brought this table back; the first push is usertrap's prologue.

So the value 0x8000000000087fff circulates through every process’s trapframe, and any hart can switch to it at any moment. Because the table never changes, it does not matter which hart saved it or when.

The price of xv6’s simple design shows up here: every switch between a user table and this one flushes the hart’s whole TLB, so after each system call the kernel starts with a cold TLB and refills it, one walk per page touched. Kernels that care more about speed map the kernel into every user page table, or use ASIDs.

Step 19 of 19

What it cost, and what it bought

The kernel page table cost 166 pages from the allocator (102 table pages, 64 stacks), about 49,000 PTE writes, 166 trips through kmem.lock, and one csrw satp plus two sfence.vma on each hart: 3 satp writes that turn paging on (after the 3 w_satp(0) in start that turned it off) and 6 fences for the whole machine.

What it bought:

• Protection inside the kernel: code is not writable, data is not executable, nothing is user-accessible, and the 64 kernel stacks have unmapped guard pages. (The three harts’ own boot-turned-scheduler stacks in stack0 do not: they are plain direct-mapped RAM.)
• The trampoline at one address shared with every user table, which makes trap entry and exit possible at all.
• A direct map of all RAM, so the kernel can treat any physical address as a pointer, which is how it reaches page tables and user pages.

And the concurrency lesson of this tour: build shared data on one hart, publish it with a release/acquire pair, never modify it again, and it can be shared by every hart with no lock at all. The only per-hart work left is the part that is truly per-hart: each CPU’s own satp and its own TLB.