Paging

This homework covers how paging and memory allocation is done in xv6.

You can go through the following files:

• kernel/memlayout.h
• kernel/vm.c
• kernel/kalloc.c
• kernel/riscv.h
• kernel/exec.c
• kernel/sysproc.c (sbrk())
• kernel/trap.c (usertrap())
• kernel/vm.c (vmfault())

Chapters 3 and 5 of the book (Page Tables and Page Faults) will help, especially sections 3.2, 3.6, 3.7 and 5.1.

xv6 uses page tables to give each process its own virtual address space, translating virtual addresses to physical memory while enforcing access through PTE permissions. The kernel builds and manages these mappings using functions such as walk() and mappages(), while kalloc()/kfree() manage the physical pages backing them; page faults allow the kernel to handle invalid or unauthorized accesses and allocate memory lazily when required.

Questions

1. In loadseg(), after obtaining the physical address pa, what allows readi() to write directly to that address? Which line of code makes the physical address usable as a kernel virtual address?

DIY: understanding lazy allocation

sbrk() syscall grows a process’s address space. xv6 has two ways of handling this growth: (i) eager allocation, physical memory is allocated and mapped when the address space is expanded; (ii) lazy allocation, only the process’s address-space size is increased, a physical page is accessed when the memory is first accessed.

Task

Write a user program that grows its address space by one byte by calling the both sbrk() and sbrklazy().

Inspect the process’s page table before and after the call in each case. For the lazy allocation case, also access the newly allocated memory and inspect the table again.

Use the page-table information to determine how much memory is allocated in each case and how the PTE for the newly allocated memory changes. (Hint: Look at the walk() function in kernel/vm.c. It is used to locate the PTE corresponding to a given virtual address. The newly allocated byte lies at the old value of the process’s sz, so inspecting the PTE for that virtual address before and after sbrk(1) / sbrklazy(1) will help you answer the questions above).

Running your program

1. Create a user program user/test_sbrk that calls sbrk(1) and sbrklazy(1).
2. Add $U/_test_sbrk to UPROGS in Makefile.
3. Run your program in QEMU:

   make qemu

4. Inspect the process’s page table before and after each call, and after accessing the lazily allocated memory.