One of the many neat tricks an OS can play with page table hardware is lazy allocation of heap memory. xv6 applications ask the kernel for heap memory using the
sbrk system call. In the kernel we’ve given you,
sbrk allocates physical memory and maps it into the process’s virtual address space. There are programs that allocate memory but never use it; for example, to implement large sparse arrays. Sophisticated kernels delay allocation of each page of memory until the application tries to use that page—as signaled by a page fault. You’ll add this lazy allocation feature to xv6 in this lab.
To start the lab, update your repository and create a new branch for your solution:
To help you visualize RISC-V page tables, and perhaps to aid future debugging, your first task is to write a function that prints the contents of a page table. This function needs to be implemented correctly to pass the tests.
Define a function called
vmprint. It should take a
pagetable_t argument, and print that pagetable in the format described below. Insert
if(p->pid==1) vmprint(p->pagetable); in
kernel/exec.c just before the
to print the first process’s page table.
Now when you start xv6 it should print output like this, describing the page table of the first process at the point when it has just finished
The first line displays the argument to
vmprint. After that there is a line for each PTE, including PTEs that refer to page-table pages deeper in the tree. Each PTE line is indented by a number of “ ..” that indicates its depth in the tree. Each PTE line shows the PTE index in its page-table page, the pte bits, and the physical address extracted from the PTE. Don’t print PTEs that are not valid. In the above example, the top-level page-table page has mappings for entries 0 and 255. The next level down for entry 0 has only index 0 mapped, and the bottom-level for that index 0 has entries 0, 1, and 2 mapped.
Your code might emit different physical addresses than those shown above. The number of entries and the virtual addresses should be the same.
freewalk may be inspirational.
kernel/defs.h so that you can call it from
%p in your printf calls to print out full 64-bit hex PTEs and addresses as shown in the example.
Explain the output of
What does page 0 contain? What is in page 2?
When running in user mode, could the process read/write the memory mapped by page 1?
What do last two pages contain?
You don’t need to submit answers to the questions in this lab. Do answer them for yourself though!
Delete page allocation from the
sbrk(n) system call implementation, which is the function
sbrk(n) system call grows the process’s memory size by
n bytes, and then returns the start of the newly allocated region (i.e., the old size). Your new
sbrk(n) should just increment the process’s size (
n and return the old size. It should not allocate memory—so you should delete the call to
growproc() (but you still need to increase the process’s size!).
Try to guess what the result of this modification will be: what will break?
Make this modification, boot xv6, and type echo hi to the shell. You should see something like this:
The “usertrap(): …” message is from the user trap handler in
trap.c; it has caught an exception that it does not know how to
handle. Make sure you understand why this page fault occurs. The
“stval=0x0..04008” indicates that the virtual address that caused
the page fault is
Modify the code in
trap.c to respond to a page fault from user space
by mapping a newly allocated page of physical memory at the faulting
address, and then returning back to user space to let the process
continue executing. You should add your code just before the
call that produced the “usertrap(): …” message. Your solution is
acceptable if it passes both
usertrap() that reports the page fault,
in order to see how to find the virtual address that caused the page fault.
vm.c, which is what
sbrk() calls (via
You’ll need to call
PGROUNDDOWN(va) to round the faulting virtual address down to a page boundary.
uvmunmap() will panic; modify it to not panic if some pages aren’t mapped.
vmprint function from above to print the content of a page table.
sbrk() test in
usertests allocates something large; this should succeed now.
If all goes well, your lazy allocation code should result in echo hi working. You should get at least one page fault (and thus lazy allocation) in the shell, and perhaps two.
If you have the basics working, now turn your implementation into one that handles the corner cases too:
sbrk() to a system call such as
write, but the memory for
that address has not yet been allocated.
kalloc() fails in the page
fault handler, kill the current process.
Your solution is acceptable if your kernel passes both
You may run python3 grade_lab_lazy.py to ensure that your code passes all of the tests. Note: You need to keep the
vmprint in the first task to pass this grading script.
When you are ready to submit your work to Gradescope to be automatically graded, you can run make gradescope which generates a
submission.zip file that can be uploaded to Gradescope. This file should only contain the files that were changed as a result of completing the lab assignment.