Page tables and address spaces · xv6, line by line

1warm-upChoose one

In kvminithart, line 80 turns paging on with csrw satp. Nothing jumps to a new address afterwards: the program counter simply moves on to the next instruction. Why does that next instruction (the second sfence.vma) still get fetched correctly?

kernel/vm.c

72// Switch the current CPU's h/w page table register to
73// the kernel's page table, and enable paging.
74void
75kvminithart()
76{
77  // wait for any previous writes to the page table memory to finish.
78  sfence_vma();
79
80  w_satp(MAKE_SATP(kernel_pagetable));
81
82  // flush stale entries from the TLB.
83  sfence_vma();
84}

The trampoline page is mapped at the same virtual address in every table, and kvminithart runs from it.The kernel page table maps the kernel’s code at virtual addresses equal to its physical addresses, so the same PC value finds the same bytes before and after translation starts.The second sfence.vma flushes the TLB, and fetching it is allowed to fail harmlessly.The CPU keeps fetching physical addresses until the next sret or mret, so translation only starts later.

2warm-upType a number

A page-table page in Sv39 is one 4096-byte page. How many page-table entries (PTEs) does it hold?

kernel/vm.c

86// Return the address of the PTE in page table pagetable
87// that corresponds to virtual address va.  If alloc!=0,
88// create any required page-table pages.
89//
90// The risc-v Sv39 scheme has three levels of page-table
91// pages. A page-table page contains 512 64-bit PTEs.
92// A 64-bit virtual address is split into five fields:
93//   39..63 -- must be zero.
94//   30..38 -- 9 bits of level-2 index.
95//   21..29 -- 9 bits of level-1 index.
96//   12..20 -- 9 bits of level-0 index.
97//    0..11 -- 12 bits of byte offset within the page.

decimal, 0x hex or 0b binary

3solidDecode the bits

Right after exec, the level-0 PTE for sh’s data page (virtual 0x2000) read 0x21fce817 in our run. Decode it using the macros in kernel/riscv.h.

kernel/riscv.h

395#define PTE_V (1L << 0) // valid
396#define PTE_R (1L << 1)
397#define PTE_W (1L << 2)
398#define PTE_X (1L << 3)
399#define PTE_U (1L << 4) // user can access
400
401// shift a physical address to the right place for a PTE.
402#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
403
404#define PTE2PA(pte) (((pte) >> 10) << 12)
405
406#define PTE_FLAGS(pte) ((pte) & 0x3FF)

Value: 0x21fce817

V (bit 0)R, W, X (bits 1-3)U (bit 4)Physical page it maps (PTE2PA)

4solidType a number

TRAMPOLINE is 0x3ffffff000. What is its index in the root (level-2) page-table page, PX(2, TRAMPOLINE)?

kernel/riscv.h

408// extract the three 9-bit page table indices from a virtual address.
409#define PXMASK         0x1FF // 9 bits
410#define PXSHIFT(level) (PGSHIFT + (9 * (level)))
411#define PX(level, va)  ((((uint64)(va)) >> PXSHIFT(level)) & PXMASK)
412
413// one beyond the highest possible virtual address.
414// MAXVA is actually one bit less than the max allowed by
415// Sv39, to avoid having to sign-extend virtual addresses
416// that have the high bit set.
417#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))

decimal, 0x hex or 0b binary

5solidChoose one

Sv39 can translate 39-bit virtual addresses, 512 GiB. Why does xv6 set MAXVA to 1 << 38 (256 GiB) instead?

kernel/riscv.h

413// one beyond the highest possible virtual address.
414// MAXVA is actually one bit less than the max allowed by
415// Sv39, to avoid having to sign-extend virtual addresses
416// that have the high bit set.
417#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))

Half the address space is reserved for the kernel and the other half for user programs.QEMU’s virt machine has only 256 GiB of address space.Sv39 requires bits 63…39 to be copies of bit 38, so addresses with bit 38 set would be huge sign-extended 64-bit numbers; xv6 avoids them by never using bit 38.The top bit of the root index is reserved for the hardware’s accessed and dirty bits.

6warm-upTrue or false, and why

True or false: every xv6 user page table maps the whole kernel, protected from the program only by leaving PTE_U clear.

TrueFalse

Why?

User page tables map nothing above p->sz.The kernel is mapped in every user table, but with U set and W clear, so programs can read it but not change it.It maps only the trampoline and the trapframe (without U); everything else in the kernel exists only in the kernel page table, which is why uservec switches satp before it uses the kernel stack.

7solidClick the line

Click the line in walk without which a freshly allocated page-table page would be full of entries that look valid, so that walk would follow garbage pointers or mappages would panic with “remap”.

kernel/vm.c

98pte_t *
99walk(pagetable_t pagetable, uint64 va, int alloc)
100{
if (va >= MAXVA)
  panic("walk");
103
for (int level = 2; level > 0; level--) {
  pte_t *pte = &pagetable[PX(level, va)];
  if (*pte & PTE_V) {
    pagetable = (pagetable_t)PTE2PA(*pte);
  } else {
    if (!alloc || (pagetable = (pde_t *)kalloc()) == 0)
      return 0;
    memset(pagetable, 0, PGSIZE);
    *pte = PA2PTE(pagetable) | PTE_V;
  }
}
return &pagetable[PX(0, va)];
116}

Your pick: none yet (click a line in the code)

8warm-upChoose all that apply

sh’s address space has these pages. Which of them have PTE_U set, so that sh itself, in user mode, may touch them?

9solidChoose one

Line 47 of kvmmake maps the trampoline page at TRAMPOLINE, although the direct map (line 39) already covers its physical page 0x80006000. Why is this second mapping necessary?

kernel/vm.c

// map kernel text executable and read-only.
kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext - KERNBASE, PTE_R | PTE_X);
40
// map kernel data and the physical RAM we'll make use of.
kvmmap(kpgtbl, (uint64)etext, (uint64)etext, PHYSTOP - (uint64)etext,
       PTE_R | PTE_W);
44
// map the trampoline for trap entry/exit to
// the highest virtual address in the kernel.
kvmmap(kpgtbl, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);

Because the kernel’s code above 0x80006000 is not mapped until later.So that user programs can call the trampoline directly instead of using ecall.The direct-mapped copy is read-only, and the trampoline needs to be writable.The trap code switches satp between a user table and this one while executing in the trampoline, so the page must be at the same virtual address in both tables, and user tables have only the TRAMPOLINE mapping.

10deepChoose one

A buggy program passes its trapframe’s address, 0x3fffffe000, as a buffer to a system call, and the kernel calls copyout(p->pagetable, p->sz, 0x3fffffe000, src, 8). The page is mapped in the user table (R W, no U). What happens?

kernel/vm.c

344int
345copyout(pagetable_t pagetable, uint64 psz, uint64 dstva, char *src, uint64 len)
346{
uint64 n, va0, pa0;
pte_t *pte;
349
while (len > 0) {
  va0 = PGROUNDDOWN(dstva);
  if (va0 >= MAXVA)
    return -1;
354
  pa0 = walkaddr(pagetable, va0);
  if (pa0 == 0) {
    if ((pa0 = vmfault(pagetable, psz, va0, 0)) == 0) {
      return -1;
    }
  }
361
  pte = walk(pagetable, va0, 0);
  // forbid copyout over read-only user text pages.
  if ((*pte & PTE_W) == 0)
    return -1;
366
  n = PGSIZE - (dstva - va0);
  if (n > len)
    n = len;
  memmove((void *)(pa0 + (dstva - va0)), src, n);
371
  len -= n;
  src += n;
  dstva = va0 + PGSIZE;
}
return 0;
377}

The kernel takes a page fault and panics in kerneltrap.The 8 bytes are written into the trapframe, because the kernel reaches physical pages through its direct map and ignores U.vmfault allocates a fresh page and maps it at 0x3fffffe000.copyout returns -1 and writes nothing.

11solidPut in order

sh runs lb a5, 0(a0) with a0 = 0x2020 in user mode, and the translation is not in the TLB. Put the hardware’s steps in order.

Read the level-2 PTE at index bits 38…30 (0); it has V and no R/W/X, so follow it
Take the root page-table page’s physical address from satp’s PPN field
Add the offset 0x020 to the leaf’s page address and load the byte
Read the level-1 PTE at index bits 29…21 (0) and follow it
Look up virtual page 0x2 in this hart’s TLB, and miss
Read the level-0 PTE at index bits 20…12 (2) and check V, U and R

12warm-upMatch the pairs

Match each macro from kernel/riscv.h with what it computes.

PX(level, va)PTE2PA(pte)PA2PTE(pa)PTE_FLAGS(pte)PGROUNDDOWN(a)MAKE_SATP(pt)

13warm-upChoose one

Hart 0 runs sh and hart 2 runs ls. At the same instant both execute a load from virtual address 0x0. Why don’t they interfere?

The kernel holds a lock on each page table while its process is running.Only one program can be at address 0x0 at a time; the other was relocated by the linker.They do interfere, but code pages are read-only, so both read the same bytes.Each hart’s satp names a different page table, so the same virtual address translates to different physical pages.

14solidType a number

Line 36 of kvmmake maps the PLIC: 64 MiB (0x4000000) starting at 0x0c000000. The level-2 and level-1 tables for the first GiB already exist. How many level-0 page-table pages does walk allocate for this one call?

kernel/vm.c

// uart registers
kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W);
31
// virtio mmio disk interface
kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
34
// PLIC
kvmmap(kpgtbl, PLIC, PLIC, 0x4000000, PTE_R | PTE_W);

decimal, 0x hex or 0b binary

15solidDecode the bits

gdb shows satp = 0x8000000000087f41 on a hart. In this build the kernel’s root page is at 0x87fff000. Decode it.

Value: 0x8000000000087f41

MODE (bits 63-60)ASID (bits 59-44)Physical address of the root page-table pageWhich table is this?

16deepFill in the machine state

Hart 1 has left its spin loop in main, printed hart 1 starting, and has just executed the csrw satp on line 80 of kvminithart (called from main line 39). What is hart 1’s state?

kernel/vm.c

72// Switch the current CPU's h/w page table register to
73// the kernel's page table, and enable paging.
74void
75kvminithart()
76{
77  // wait for any previous writes to the page table memory to finish.
78  sfence_vma();
79
80  w_satp(MAKE_SATP(kernel_pagetable));
81
82  // flush stale entries from the TLB.
83  sfence_vma();
84}

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

17warm-upChoose one

Hart 0 executed sfence.vma around its csrw satp at boot. Why must harts 1 and 2 run kvminithart, with its own two sfence.vma, for themselves?

kernel/vm.c

72// Switch the current CPU's h/w page table register to
73// the kernel's page table, and enable paging.
74void
75kvminithart()
76{
77  // wait for any previous writes to the page table memory to finish.
78  sfence_vma();
79
80  w_satp(MAKE_SATP(kernel_pagetable));
81
82  // flush stale entries from the TLB.
83  sfence_vma();
84}

sfence.vma acts only on the hart that executes it: its own TLB and its own page-table walker; every hart also has its own satp.They are only needed because harts 1 and 2 use a different kernel page table.Harts 1 and 2 don’t actually need the fences; they are there only for symmetry with hart 0.Hart 0’s fence was broadcast to the other harts, but they were in Bare mode and ignored it.

18solidTrue or false, and why

True or false: because three harts translate through kernel_pagetable at the same time, xv6 must protect it with a lock.

TrueFalse

Why?

Each hart has its own copy of the kernel page table.No software modifies the kernel page table after boot: kvmmap is only used by kvmmake and proc_mapstacks, and even the 64 kernel stacks are mapped once, up front.The TLB serialises access, so walkers never read the table at the same time.

19deepChoose one

Suppose a buggy kernel function, handling sh’s read(0, buf, 100), did *(char *)0x2020 = 'l' with the user’s address (buf is at 0x2020). What would happen?

The store succeeds but writes to physical address 0x2020.A store page fault in supervisor mode; kerneltrap finds no device interrupt and panics.The byte lands in sh’s buf, because the kernel can write any address.vmfault allocates a page at 0x2020 in the kernel page table and the store succeeds.

20solidChoose one

With KSTACK(p) = TRAMPOLINE - (p+1) × 2 × PGSIZE, what is mapped at virtual address 0x3fffffc000 in the kernel page table?

kernel/memlayout.h

46// map the trampoline page to the highest address,
47// in both user and kernel space.
48#define TRAMPOLINE (MAXVA - PGSIZE)
49
50// map kernel stacks beneath the trampoline,
51// each surrounded by invalid guard pages.
52#define KSTACK(p) (TRAMPOLINE - ((p) + 1) * 2 * PGSIZE)

proc[1]'s kernel stackNothing; it is the unmapped guard page between proc[0]'s and proc[1]'s kernel stacks.proc[0]'s kernel stackproc[0]'s trapframe

21deepChoose one

Why does proc_freepagetable unmap TRAMPOLINE and TRAPFRAME (with do_free = 0) before calling uvmfree?

kernel/proc.c

207// Free a process's page table, and free the
208// physical memory it refers to.
209void
210proc_freepagetable(pagetable_t pagetable, uint64 sz)
211{
212  uvmunmap(pagetable, TRAMPOLINE, 1, 0);
213  uvmunmap(pagetable, TRAPFRAME, 1, 0);
214  uvmfree(pagetable, sz);
215}

The order doesn’t matter; it is only for readability.Because uvmfree would otherwise free the trampoline’s physical page twice.To flush those two pages from the TLB before the table is freed.uvmfree only unmaps 0…sz, and freewalk panics on any leaf still present; do_free is 0 because the trampoline is kernel code and the trapframe is freed separately by freeproc.

22solidChoose all that apply

Which of these mappings in the kernel page table have PTE_X (executable) set?

kernel/vm.c

// uart registers
kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W);
31
// virtio mmio disk interface
kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
34
// PLIC
kvmmap(kpgtbl, PLIC, PLIC, 0x4000000, PTE_R | PTE_W);
37
// map kernel text executable and read-only.
kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext - KERNBASE, PTE_R | PTE_X);
40
// map kernel data and the physical RAM we'll make use of.
kvmmap(kpgtbl, (uint64)etext, (uint64)etext, PHYSTOP - (uint64)etext,
       PTE_R | PTE_W);
44
// map the trampoline for trap entry/exit to
// the highest virtual address in the kernel.
kvmmap(kpgtbl, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
48
// allocate and map a kernel stack for each process.
proc_mapstacks(kpgtbl);

23deepChoose all that apply

sh’s layout: code 0x0–0x1fff (R X U), data 0x2000 (R W U), guard 0x3000 (R W), stack 0x4000 (R W U), sz = 0x5000, trapframe at 0x3fffffe000 (R W). Which of these, executed by sh in user mode, raise a page fault?

24warm-upChoose one

What does the satp register give the hardware?

kernel/riscv.h

245// use riscv's sv39 page table scheme.
246#define SATP_SV39 (8L << 60)
247
248#define MAKE_SATP(pagetable) (SATP_SV39 | (((uint64)pagetable) >> 12))

The pid of the running process.The virtual address of the root page-table page.The address of the first PTE for the current program counter.The translation mode and the physical page number of the root page-table page.

25deepType a number

sh’s page table uses 5 page-table pages (root; a level-1 and a level-0 page for the bottom; a level-1 and a level-0 page for the top). If its heap grew eagerly from 0x5000 by 4 MiB (to sz = 0x405000), how many page-table pages would the table use in total?

decimal, 0x hex or 0b binary