Project 2: Virtual Memory on xv6

Project Overview

In this project you will become familiar with the xv6 virtual memory system and work to add a few features that are common in modern OSes. The project is composed of two parts, which you must complete in order. This project can be completed in pairs or individually.

Part 1 (50 points)

In part 1, you will change the virtual memory space of user processes so that the address 0x0 is invalid. Currently, 0x0 (NULL) is a valid address for an xv6 user process. You will change xv6 so that dereferencing address 0x0 causes a page fault.

Part 2 (50 points)
In part 2, you will implement a copy-on-write fork in xv6.  This is an important performance optimization.  Currently, the fork syscall copies all of a process' memory.  Most unix-based OSes use copy-on-write instead, and this allows the OS to fork with very little effort.

Technically, part 2 can be developed independently of part1.  However, part 2 is more difficult that part 1 and your experience with part 1 will help you with part 2, so we highly recommend completing part 1, then part 2.  Do not split parts 1 and 2 between the two partners because this will take longer overall.

Educational Objectives

This project aims to achieve several educational objectives:

• Understand how virtual memory is implemented. In particular, understand how virtual addresses are mapped to physical addresses using a page directory and page tables.
• Understand how virtual memory is used to prevent processes from corrupting each other's memory.
• Learn how to implement copy-on-write and why it is useful.
• Practice writing your own test cases.
• Continue to hone your skills as an OS developer.

Part 0: Getting a fresh clone

You should start from a fresh copy of the xv6 code.  Join Project 2 on Github Classroom and clone the repository:

https://classroom.github.com/g/7rx-cLLI 

After you've done this, you should get an email with a link to a private repository like https://github.com/starzia-teaching/project-1-GROUPNAME 

From the github web interface you can click "clone of download" and then "use HTTPS" to get your group's repository URL (used below).  You can clone the repo using the following command:

$ git clone https://USERNAME@github.com/starzia-teaching/project-1-GROUPNAME.git 

Notice that I added my github username to the user above, before "@github.com".  If you get an error related to "gnome-ssh-askpass" then try running "unsetenv SSH_ASKPASS" or "unset SSH_ASKPASS".

Part 1: Making the null pointer invalid

50 points

In your prior C programming experience, you probably became somewhat familiar with the null pointer. In particular, you know that dereferencing a pointer whose value is 0x0 (NULL) causes a segmentation fault. The null pointer serves as a convenient sentinel value because, in most operating systems, address 0x0 is reserved for system use, which means that user programs should not be accessing that address anyway.

However, in xv6, address 0x0 is a valid virtual address. A user process’s address space goes from 0x0 to 0x7FFFFFFF (KERNBASE-1). This means that you can write a C program that dereferences a null pointer and run it on xv6 without causing a segmentation fault. Give it a try! You will be able to use this program later to test your work.

Your Task

Your first task is to modify how xv6 manages the user virtual address space so that 0x0 is no longer a valid address. In particular, if a user program tries to dereference a null pointer, xv6 should trap and kill the process. Luckily for you, xv6 does this automatically for invalid memory accesses.

Your modifications must not prevent xv6 from functioning normally. In other words, don’t break anything.

Guidance and hints

1. Start by writing a test program that dereferences and prints a null pointer.  This should actually run without issues on xv6 and it will print out a random-looking number.  That random number comes from the beginning of your programs code.  The goal of part 1 is to make this program crash.
2. Remember that the OS allocates memory to processes in page-sized chunks.  So, you'll have to make the entire first page of memory inacessible to user processes (not just the one address 0x0).
3. Read the last six pages of Chapter 1 of the xv6 textbook very carefully (starting from "Code: the first address space").  This explains how the first process is started and you must understand this to debug your solution to part 1.
4. Make sure you understand how xv6 uses a page directory and page tables to map a process’s virtual memory to physical memory. In particular, understand what the different bits in a Page Directory Entry and Page Table Entry mean. Chapter 2 of the xv6 textbook is a useful reference. How does a Page Table Entry differ for a valid page compared to an invalid page?
5. Look at the exec() function to understand what memory-related tasks are involved in executing a new process. Make a list of the memory-related functions that are being called, look at how they are implemented and decide which ones will need to change.
6. Look at the fork() function. Again, figure out which memory-related functions are being called and which ones need to change.
7. Keep digging through the rest of the code to find other places that need to change. There are several places where the kernel code makes checks on addresses and pointers. These checks are often based on the implicit assumption that the process’s address space begins at 0x0. For example, when a user program passes an argument in a syscall, the kernel checks the validity of the argument. Some of these checks may need to change.
8. Have a look at the Makefile. This file dictates that user programs (target _%) are compiled so that their entry point (first instruction) is loaded at address 0x0. Since you are changing xv6 so that the first page is invalid, the entry point for user programs will have to change accordingly. For example, you can use the first address of the second page: 0x1000.  Note that gdb assumes that your code starts at location 0x0, so you will have to use the following syntax if you change the start address: "add-symbol-file usertests.o 0x1000"

9. Be bold. In Project 1, you simply had to add code to xv6, so you didn’t have to worry about breaking the existing functionality. In this project, you actually have to modify the provided code. There is no way around it. You will probably break something. Don’t let this scare you. You will be able to repair the damage you cause.  You can use git to see what changes you have made ("git diff" or "git diff 9e2e4f22b")

10. When you type "ls" in xv6, you may have noticed a user program called "usertests." This program runs a series of tests to make sure your kernel is working properly.  This program should still run successfully after you make your changes.  You should also implement additional tests to verify that dereferencing the null pointer causes a segfault.
11. validatetest() will have to change in usertests.c.  The loop should start at 4096 instead of at zero.

Part 2: Copy-on-write fork

50 points

The fork syscall creates a duplicate of the current process.  Making a full copy of the process' memory will be slow if the process is large.  It's also wasteful if the fork is immediately followed by an exec, which is often what happens.  Recall that exec clears the process' memory and replaces it with the code loaded from an executable file (all that freshly copied memory is thrown out!).

Copy-on-write is a strategy that avoids this performance problem.  Under this strategy, the copy is lazy.  In other words, we delay copying until it's absolutely necessary.  The kernel can do this by cleverly managing the page tables for both parent and child processes.  Specifically, we allow the child process to read from the parent's copy of the shared memory page until either the parent or child writes to the page.  At this point, both parent and child need their own copy of the page because they expect to see different values.

Notice that a child can fork again, leading to a page being shared by more than just two processes.  We have to keep a shared page reference count to make sure that it's only cleaned up when no process is referring to it.

Your Tasks

1. Start by writing some tests for the old and new kernel.  Your Qemu machine has only 224 MBytes of physical memory, however your new kernel should allow a user process to malloc 200 Mbytes of memory and then fork itself several times!  The original xv6 kernel will return a -1 error code for fork() if there is not enough free memory (verify this!).  After finishing part 2, you will be able to proceed with the fork.  In your solution, a large child will be killed by the kernel with an "out of memory" error only if it tries to writes to a significant amount of its memory (thus triggering actual page copies).
2. Create a statically-sized array of PHYSTOP/PGSIZE=57,344 8-bit integers (uchars) in the kernel to store the number of times each physical page of memory is being shared (the shared page reference count).  This count will start at zero.  (A more efficient implementation could use a hash table or other clever data structures, but please don't bother trying.)
3. Change the behavior of the kernel's virtual memory management code (vm.c) as follows:
   • Change the implementation of copyuvm (called by fork) to return a "shallow" copy of the passed-in page table.  The table itself will be copied, but it will point to the same physical memory pages.  Be sure to:
     
     • remove all allocations of new pages (remove calls to kalloc), and
     • remove all page copies (calls to memmove) 
     • mark all the page table entries in the child and parent as read-only.
     • increment the shared page reference count for all the active physical pages.
   • Change the implementation of deallocuvm to handle two cleanup cases:
     1. the case when a child process calls sbrk to reduce its memory size.
     2. when a process exits.
   • In both of the above cases, we must decrement the shared page reference count and if it's not still used by another process then free the page. 
4. Change the kernel's interrupt handler to deal with page faults resulting from a process trying to write "shared" pages.  When this happens, you must duplicate the page (similar to what copyuvm used to do) and reduce the unmodified copy's shared page reference count.
   • To do this, you must register a handler for page faults (T_PGFLT) in the trap() function.
   • To distinguish the pages allocated for copy-on-write fork from other pages that might simply be used by other function, like sbrk()/malloc(), you need to add an additional flag for COW pages, like PTE_COW. You can define it in mmu.h with a value, like 0x100.
   • In copyuvm(), you need to update the ptes' permission to both ~PTE_W and PTE_COW.
   • In your page fault handler, you need to first check the validity of the virtual address:
     • if the virtual address is below KERNBASE
     • and if the fault is for an address whose page table includes all the PTE_COW, PTE_U, PTE_P flags

     If not, kill the program as usual by mimicking the codes under "default" statements starting from cprintf() line, which were used to handle page fault in the original xv6 code. After you added part 2, the page fault will be handled by your own page fault handler.

5. The CR3 register holds a pointer to the top-level page directory.  Note that whenever you make changes to the page table of a process, you must "re-install" that page table by writing its address into CR3, by using lcr3() function.  In other words, even if CR3 is not changing, you may still need to write to CR3 to signal to the CPU that the TLB should be flushed (to make your new PTEs visible).  You can take a look at switchkvm() function in vm.c to see how lcr3() is used.
6. The above steps are just a summary, not a complete list!

Guidance and hints

1. Carefully read Chapter 2 of the xv6 book.
2. See mmu.h for low-level details of the x86 page tables.  Notice that the PTE_W bit marks a page table entry as writeable.
3. We have not talked about locks in class yet, but a correct solution needs a lock to prevent concurrent reading/writing of the shared page reference count.  You can see how locks are used in proc.c to protect the page table from concurrent access.  Basically, you have to initialize the lock once, then you have to acquire the lock before each access to the shared data (the shared page reference count) and you have to release the lock when you're reading/writing the shared data.