One of the many neat tricks an O/S can play with page table hardware is lazy allocation of user-space 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. It can take a long time for a kernel to allocate and map memory for a large request. Consider, for example, that a gigabyte consists of 262,144 4096-byte pages; that's a huge number of allocations even if each is individually cheap. In addition, some programs allocate more memory than they actually use (e.g., to implement sparse arrays), or allocate memory well in advance of use. To allow sbrk() to complete more quickly in these cases, sophisticated kernels allocate user memory lazily. That is, sbrk() doesn't allocate physical memory, but just remembers which user addresses are allocated and marks those addresses as invalid in the user page table. When the process first tries to use any given page of lazily-allocated memory, the CPU generates a page fault, which the kernel handles by allocating physical memory, zeroing it, and mapping it. You'll add this lazy allocation feature to xv6 in this lab.
Before you start coding, read Chapter 4 (in particular 4.6) of the xv6 book, and related files you are likely to modify:
To start the lab, switch to the lazy branch:
$ git fetch $ git checkout lazy $ make clean
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:
init: starting sh $ echo hi usertrap(): unexpected scause 0x000000000000000f pid=3 sepc=0x0000000000001258 stval=0x0000000000004008 va=0x0000000000004000 pte=0x0000000000000000 panic: uvmunmap: not mappedThe "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.
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), and perhaps two.
We've supplied you with lazytests, an xv6 user program that tests some specific situations that may stress your lazy memory allocator. Modify your kernel code so that all of both lazytests and usertests pass.
Your solution is acceptable if your kernel passes 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 $
This completes the lab. Make sure you pass all of the make
grade tests. If this lab had questions, don't forget to write up your
answers to the questions in answers-lab-name.txt. Commit your changes
(including adding answers-lab-name.txt) and type make handin in the lab
directory to hand in your lab.
Create a new file, time.txt, and put in it a single integer, the
number of hours you spent on the lab. Don't forget to git add and
git commit the file.
Submit the lab
You will turn in your assignments using
website. You need to request once an API key from the submission
website before you can turn in any assignments or labs.
This completes the lab. Make sure you pass all of the make grade tests. If this lab had questions, don't forget to write up your answers to the questions in answers-lab-name.txt. Commit your changes (including adding answers-lab-name.txt) and type make handin in the lab directory to hand in your lab.
Create a new file, time.txt, and put in it a single integer, the number of hours you spent on the lab. Don't forget to git add and git commit the file.
After committing your final changes to the lab, type make handin to submit your lab.
$ git commit -am "ready to submit my lab" [util c2e3c8b] ready to submit my lab 2 files changed, 18 insertions(+), 2 deletions(-) $ make handin tar: Removing leading `/' from member names Get an API key for yourself by visiting https://6828.scripts.mit.edu/2020/handin.py/ Please enter your API key: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX % Total % Received % Xferd Average Speed Time Time Time Current Dload Upload Total Spent Left Speed 100 79258 100 239 100 79019 853 275k --:--:-- --:--:-- --:--:-- 276k $make handin will store your API key in myapi.key. If you need to change your API key, just remove this file and let make handin generate it again (myapi.key must not include newline characters).
If you run make handin and you have either uncomitted changes or untracked files, you will see output similar to the following:
M hello.c ?? bar.c ?? foo.pyc Untracked files will not be handed in. Continue? [y/N]Inspect the above lines and make sure all files that your lab solution needs are tracked i.e. not listed in a line that begins with ??. You can cause git to track a new file that you create using git add filename.
If make handin does not work properly, try fixing the problem with the curl or Git commands. Or you can run make tarball. This will make a tar file for you, which you can then upload via our web interface.