Lab 5: Copy-On-Write

Important deadlines

• Design document due 2/17 (Thursday) at 9:00pm (post to your design pod channel on Slack)
• Peer feedback due 2/21 (Monday) at 9:00pm (also post your design pod Slack channel)
• Lab implementation due 2/25 (Friday) at 9:00pm (submit on Gradescope).

Introduction

In this lab, you will further reduce osv’s memory consumption. In lab 4, you helped osv avoid allocating memory unnecessarily by growing the stack and the heap on demand. The next optimization improves the performance of fork by using a copy-on-write mechanism. Currently, fork duplicates every page of user memory in the parent process. Depending on the size of the parent process, this can consume a lot of memory and can potentially take a long time (see as_copy_as, memregion_copy_internal, and vpmap_copy).

Here, we can reduce the cost of fork by allowing multiple processes to share the same physical memory, while at a logical level still behaving as if the memory was copied. As long as neither process modifies the memory, it can stay shared; if either process changes a page, a copy of that page will be made at that point (that is, copy-on-write).

When this improved fork returns, the child process is given a page table that points to the same memory pages as the parent. No additional memory is allocated for the new process, other than to hold the new page table. However, the page table entries of both processes will need to be changed to be read-only. That way, if either process tries to alter the content of their memory, a trap to the kernel will occur, and the kernel can make a copy of the memory page at that point, before resuming the user code.

To pull any new changes and tests for this lab, run the command

$ git pull upstream master

and merge. After the merge, double check that your code still passes tests for previous labs.

Implementation

To implement copy-on-write, you will want to implement a vpmap_cow_copy function that is similar to vpmap_copy (in arch/x86_64/kernel/mm/vpmap.c, with a declaration in include/kernel/vpmap.h). Where the two functions will differ is that instead of making a copy of the parent’s physical page, vpmap_cow_copy will update the parent’s page table entry permission to read-only and set the child’s page table entry to the same content as the parent’s. To make a page table entry read-only, consider using bitwise operations to ensure the bits of the entry corresponding to PTE_W are 0. vpmap_cow_copy will also need increment the reference count for each physical page by calling pmem_inc_refcnt with the physical address of the page. You can get the physical page address by applying PTE_ADDR() macro on the content of a page table entry.

Once you have the vpmap_cow_copy function, you can update memregion_copy_internal to use the new function instead of vpmap_copy. Note that since this function changes the memory mapping permission in the calling process, you must call vpmap_flush_tlb() at the end to invalidate previously cached page table entries.

On a page fault, if the fault address is present, being written to, and the corresponding memregion has write permission, then you know it is a copy-on-write page. From there you can allocate a physical page, copy the data from the copy-on-write page, and let the faulting process start writing to that freshly-allocated page. You can use vpmap_set_perm to change the permissions of a virtual page. Note that when you are no longer using the read only page, you should decrement its reference count using pmem_dec_refcnt. An optional optimization is to check the physical page’s reference count and if you are the last reference, you can simply use that page as your “new” read/write page, instead of making a copy of the read only page.

Both checking a page’s reference count and copying over a page will require a physical address. You can use vpmap_lookup_vaddr to retrieve the physical address corresponding to a virtual address. Beware this function will give you the exact matching physical address—if you need the address of the start of the page, be sure to use pg_round_down().

Testing

After you implement the features described above, test your lab 5 code by either running individual tests in osv shell (i.e., make qemu and then enter the name of the test file in user/lab5 without the .c), or run python3 test.py 5 to run all the tests. The cow-low-mem test specifically tests the correctness of your implementation when memory is very limited. To get an accurate result from this test, use make qemu-low-mem to start osv.

When debugging, I would recommend running individual tests in osv. test.py depends on observing TEST-NAME passed in the output from osv, and the presence of debugging print statements can interfere with this (as output from various processes can get mixed together). It’s also important, therefore, that you disable any print statements before submission to Gradescope.

What to turn in

You will submit your work for this project via Gradescope.

Gradescope lets you submit via GitHub, which is probably the easiest method. All you’ll need to do is connect your GitHub account (the Gradescope submission page has a button for this) and select the repository and branch you wish to submit. Alternatively, you can create a zip file of the osv-w22 directory and upload that. The the arch, include and kernel directories from your submission will be used.

When you submit, the autograder will compile your code and run the test cases. The Gradescope autograder will run each test multiple times.

Although you are allowed submit your answers as many times as you like, you should not treat Gradescope as your only debugging tool. Many people may submit their projects near the deadline, and thus it will Gradescope take longer to process the requests. You may not get feedback in a timely manner to help you debug problems.

Grading

This lab will be graded out of 90 points, as shown in the table below. Comments explaining your approach can help earn partial credit if there are tests that don’t pass. Poor coding style can lose points, so make sure to submit clean, well-organized code.