Virtual memory provides a level of indirection: the kernel can intercept memory references by marking PTEs invalid or read-only, leading to page faults, and can change what addresses mean by modifying PTEs. There is a saying in computer systems that any systems problem can be solved with a level of indirection. This lab explores one example of this: copy-on write fork.
To start the lab, update your repository and create a new branch for your solution:
fork() system call in xv6 copies all of the parent process’s
user-space memory into the child. If the parent is large, copying
can take a long time.
Worse, the work is often largely wasted; for example, a
exec() in the child will cause the child to discard the copied memory,
probably without ever using most of it.
On the other hand, if both parent and child use a page
and one or both writes it, a copy is truly needed.
The goal of copy-on-write (COW)
fork() is to defer allocating and
copying physical memory pages for the child until the copies are
actually needed, if ever.
fork() creates just a pagetable for the child, with PTEs for
user memory pointing to the parent’s physical pages. COW
marks all the writeable user PTEs in both parent and child as read-only. When
either process tries to write one of these COW pages, the CPU will
force a page fault. The kernel page-fault handler detects this case,
allocates a page of physical memory for the faulting process, copies
the original page into the new page, and modifies the relevant PTE
in the faulting process to refer to the new page, this time with
the PTE marked writeable. When the page fault handler returns, the
user process will be able to write its copy of the page.
fork() makes freeing of the physical pages that implement user
memory a little trickier. A given physical page may be referred to
by multiple processes’ page tables, and should be freed only when the
last reference disappears.
Your task is to implement copy-on-write fork in the xv6 kernel.
You are done if your modified kernel executes both the
usertests programs successfully.
To help you test your implementation, we’ve provided an xv6 program
cowtest (source in
cowtest runs various tests, but even
the first will fail on unmodified xv6. Thus, initially, you will
The “simple” test allocates more than half of available physical
memory, and then
fork fails because there is not enough
free physical memory to give the child a complete copy of the parent.
When you are done, your kernel should be able to run both
usertests. That is:
Here’s one reasonable plan of attack:
uvmcopy() to map the parent’s physical pages into the
child, instead of allocating new pages, and clear
PTE_W in the
PTEs of both child and parent.
usertrap() to recognize page faults. When a page-fault
occurs on a COW page, allocate a new page with
kalloc(), copy the
old page to the new page, and install the new page in the PTE with
kalloc() allocates it.
Increment a page’s reference count when
fork causes a child to share the page,
and decrement a page’s count each time any process drops the page from its page table.
kfree() should only place a page back on the free list if its reference count is zero.
It’s OK to to keep these counts in a fixed-size array of integers.
You’ll have to work out a scheme for how to index the array and how to choose its size.
For example, you could index the array with the page’s physical address divided by 4096,
and give the array a number of elements equal to highest physical address of
any page placed on the free list by
copyout() to use the same scheme as page faults
when it encounters a COW page.
Since you completed Lab Lazy prior to this lab, you will notice that a lot of the locations to modify code are similar (in addition to much of the high-level structure). This should make tackling this lab easier, since you can use knowledge gained from that earlier lab!
#define macro in
kernel/riscv.h for accessing that bit.
usertests explores scenarios that
cowtest does not test, so don’t forget to check that all tests pass for both. However, please focus on
cowtest first and debugging any issues.