Lab Lazy: Lazy Allocation for Heap Memory

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’ 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. 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:

$ git fetch origin
$ git checkout -b lazy origin/main
$ make clean

Printing the Page Table

To help you visualize RISC-V page tables, and 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.

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 exec()ing init:

page table 0x0000000087f6e000
 ..0: pte 0x0000000021fda801 pa 0x0000000087f6a000
 .. ..0: pte 0x0000000021fda401 pa 0x0000000087f69000
 .. .. ..0: pte 0x0000000021fdac1f pa 0x0000000087f6b000
 .. .. ..1: pte 0x0000000021fda00f pa 0x0000000087f68000
 .. .. ..2: pte 0x0000000021fd9c1f pa 0x0000000087f67000
 ..255: pte 0x0000000021fdb401 pa 0x0000000087f6d000
 .. ..511: pte 0x0000000021fdb001 pa 0x0000000087f6c000
 .. .. ..510: pte 0x0000000021fdd807 pa 0x0000000087f76000
 .. .. ..511: pte 0x000000002000200b pa 0x0000000080007000

The first line displays the argument to vmprint. After that there is a line for each PTE, including PTEs that refer to table pages deeper in the hierarchy. Each PTE line is indented by a number of “ ..” that indicates its depth. 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 indices corresponding to virtual address ranges should be the same.

Some hints:

• You can put vmprint() in kernel/vm.c.
• Use the macros at the end of the file kernel/riscv.h.
• The function freewalk may be inspirational.
• Define the prototype for vmprint in kernel/defs.h so that you can call it from exec.c.
• Use %p in your printf calls to print out full 64-bit hex PTEs and addresses as shown in the example.

Eliminating Allocation from sbrk

Try to guess what the result of this modification will be (i.e., what will break)!

Make this modification, boot xv6, and type echo hi to the shell. You should see something like this:

init: starting sh
$ echo hi
usertrap(): unexpected scause 0x000000000000000f pid=3
            sepc=0x00000000000011dc stval=0x0000000000004008
va=0x0000000000004000 pte=0x0000000000000000
panic: uvmunmap: not mapped

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 0x4008.

Lazy Allocation

Hints:

• You can check whether a fault is a page fault based on r_scause().
• Look at the arguments to printf() in usertrap() that reports the page fault, in order to see how to find the virtual address that caused the page fault.
• Steal code from uvmalloc() in vm.c, which is what sbrk() calls (via growproc()). You’ll need to call kalloc() and mappages().
• Use 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.
• If the kernel crashes, look up the corresponding sepc in kernel/kernel.asm.
• Use your vmprint function from above to print the content of a page table.
• If you see the error “incomplete type proc”, include proc.h (and spinlock.h).
• The first 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:

• Handle negative sbrk() arguments.
• Kill a process if it page-faults on a virtual memory address higher than any allocated with sbrk().
• Handle fork() correctly.
• Handle the case in which a process passes a valid address from sbrk() to a system call such as read or write, but the memory for that address has not yet been allocated.
• Handle out-of-memory correctly: if kalloc() fails in the page fault handler, kill the current process.
• Handle faults on the invalid page below the stack.

Your solution is acceptable if your kernel passes both lazytests and usertests:

$ lazytests
lazytests starting
running test lazy alloc
test lazy alloc: OK
running test lazy unmap...
usertrap(): ...
test lazy unmap: OK
running test out of memory
usertrap(): ...
test out of memory: OK
ALL TESTS PASSED
$ usertests
...
ALL TESTS PASSED
$

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.

Submission

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.