- 24 October 2018: clarify comment about avoiding triggering page faults in kernel mode with example of trying to make stack allocate-on-demand.
- 26 October 2018: clarify in copy-on-write hints that new/old page table entries point to original physical pages
- 28 October 2018: correct
- 28 October 2018: correct “pages referenced a page table” to “ pages referenced by a page table”
- 29 October 2018: clarify “available by calling
rcr2()” to “the faulting address is avialable by calling
rcr2()” in copy-on-write instructions to avoid ambiguity with how the page table entry is available.
- 29 October 2018 3:20pm: fix bugs in
pagingtest.cthat would cause copy-on-write tests to erroneously pass sometimes
- 29 October 2018 before 10:10pm: fix additional cases where
pagingtest.cwould erroneously allow copy-on-write tests to pass sometimes
- 31 October 2018: correct
- 31 October 2018: add some notes about common errors from not checking
walkpgdir’s return value and not passing page-aligned addresses to
- 1/2 November 2018: add clarificaiton re:
freevms relationship to
deallocuvmdoes all the work of deallocating user pages;
freevmdoes the work of deallocating page table pages
- 2 November 2018: fix bug in pagingtest.c where it would report cases where out-of-bounds accesses did not crash as cases where they did crash. (We will not deduct points based on whether or not you kill a program for accessing out-of-bounds memory.)
xv6 currently allocates stack and heap memory immediately. More commonly, OSs will allocate this memory on demand, saving memory when not all of the stack or heap is used immediately. Modify xv6 to allocate heap memory based on page faults rather than immediately. It is okay if non-heap memory is still allocated statically.
If you attempt to allocate memory on demand for a process and you run out of memory, kill that process (such as by settting
myproc()->killedto 1 before returning to
trap()) and write a message to the console using
You do not need to handle the case where the uninitialized memory is passed to a system call. This means you only need to allocate memory when a page fault occurs in the user program and do not need to handle page faults occuring when the kernel is running.
Add copy-on-write support for xv6’s
fork()system call. xv6 currently makes a copy of each page of a process when it forks. Instead, you should not copy the page and instead mark each page as read-only. Then, when a protection fault happens, actually make a copy of the page, update the corresponding page table entry, and mark it as writeable.
If a process attempts to write to a copy-on-write page, but allocating new memory to make a copy of that page to write to fails, kill that process and write a message to console using
To make sure you eventually free pages, track a reference count for each page that is shared between processes. Increment this count each time you add a read-only page table entry for a page. Decrement each time you remove one, either because a process terminates or because you make a copy of the page. When the reference count becomes 0, free the physical page.
You do not need to handle the case where the copy-on-write memory is written to by a system call. This means you only need to copy pages when a page fault occurs in the user program and do not need to handle page faults occuring when the kernel is running.
make submitto create an archive and upload the result to Collab.
Note: This testing program was last modified 29 October 2018 before 10:10pm to detect some additional ways of implementing copy-on-write wrong. It was modified again on 2 November around 4:40pm to make the initial tests that check if you crash for out-of-heap accesses not report some cases that do not crash as crashes. (We will not deduct points based on whether or not you kill programs which access memory out-of-bounds memory.)
- We have supplied a program called pagingtest.c as an example of how you can verify that your implementation works. We may run other and/or additional tests when grading your submission.
xv6 book reading
- Chapter 2 of the xv6 book describes how xv6 manages its page table structures.
Handy xv6 functions/code snippets
walkpgdirtakes a page directory (first-level page table) and returns a pointer to the page table entry for a particular virtual address. It optionally will allocate any needed second-level page tables.
You can find a page directory to pass to
walkpgdirwith something like
On an error, like failing to allocate a second-level page table,
walkpgdirreturn the address 0x0 converted to a
pte_t*. You should check for this address explicitly. In particular, accessing address
0x0will not crash, but instead will read memory from the code of the currently running program. Trying to interpret this memory as a page table entry is likely to lead to surprising results.
mappagestakes a page directory (first-level page table), a virtual address, a physical address, and a size, and modifies that page directory so size bytes of virtual memory starting the specified virtual address point to the specified physical address. It will panic if the specified virtual address is already mapped to a physical address.
If you pass mappages a range of address that spans multiple pages, it will remap multiple pages. For example,
mappages(pgdir, 0x1800, PGSIZE, ...)will try to remap virtual page number 1 (virtual addresses 0x1000 through 0x1FFF) and virtual page number 2 (virtual addresses 0x2000 through 0x2FFF) since they both overlap with the range 0x1800 through 0x1800+PGSIZE = (0x2800). To avoid this problem, you can use
PGROUNDDOWN()to convert an address in the middle of a page to an address at the beginning of the page. (For example,
P2Vconverts from a physical address to a virtual address in the kernel’s memory. The xv6 kernel makes sure that every page table maps (for the kernel’s use only) virtual address
0x80000000+xto physical address
P2Vuses these addresses (that is, it adds
V2Pdoes the opposite mapping.
kfreeallocate or free a physical page. They both return pointers to the virtual address of the page in the kernel’s memory.
You can check if a page table entry pointed to by a
pte_t *pteis present with
*pte & PTE_P. Similarly, you can check if it is writeable with
*pte & PTE_W. You can set that page table entry to point to physical page
mypageas writeable, present, and accessible in usermode using
*pte = mypage | PTE_P | PTE_W | PTE_U;. You can also call the utility function
mappagesto do this, provided the page is not already marked as present.
Allocating pages on demand
Currently, when a program tries to allocate more heap space it calls the
sbrk()system call, which calls
growproc(). This sets the
szvariable to track the size of the allocation and uses
allocuvm(). to create new page table entries. With your modification,
growproc()will no longer need to create new page table entries.
You could potentially modify
growproc(), but you would need to modify
loaduvm()to handle loading data into a page table entry that is not yet allocated. (
loaduvm()is used to implement
exec()in xv6, for loading data from an executable into memory when the program starts.)
We only require you to allocate pages on demand for stack and heap pages which are first used by the user program. This is primarily because xv6 is not setup to support handling page faults triggered by the kernel — in particular, it currently will overwrite the trapframe of the original operation (e.g. system call) that invokes the kernel with the trapframe for the page fault triggered by the kernel. Because of this, you should make sure you never trigger page faults in kernel mode. For example, you might do this by accident if you tried to make the stack allocate-on-demand, causing the kernel code that sets up the user stack to trigger a page fault to allocate the stack page.
You might find it helpful to add a
panic()to detect this case (e.g. if you do an out-of-bounds memory access).
You can test if an exception handler was run from kernel mode using
(tf->cs&3) == 0.
The xv6 book chapter on trap handling is useful.
You can modify the functions in
trap.cto detect when a page marked invalid in the page table is accessed.
traps.hdefines the constant
T_PGFLT, which is the code x86 uses to identify page faults. This will be placed in the
trapnomember variable of the
When a page fault occurs in x86, the processor sets control register 2 (CR2) to the address the program was attempting to access. You can read this in xv6 using
You need to make sure that your allocate-on-demand code does not trigger for out-of-range memory access, such as attempts to access kernel memory from userspace or accesses to unallocated memory.
xv6 contains page allocation and deallocation functions in
kalloc.c, which are
kalloc()(allocates a page) and
kfree()(deallocates a page).
You should use code similar to what’s in
allocuvm()to set each page table entry. But you should not call
allocuvm()since it allocates all pages up to the maximum. If a program accesses address 0x400000, then only the page at address 0x400000 should be created, not all the pages between 0x0 and 0x400000.
copyuvm()should only copy pages that are actually allocated. Later on, you will modify this function more to implement copy-on-write.
Adding copy-on-write support
You will need to track the number of processes that reference each physical page. The simplest way to do this is an array like:
unsigned char cow_reference_count[PHYSTOP / PGSIZE];
Then, use the physical address of the page divided by
PGSIZE(that is, the physical page number) to access the appropriate element of the array.
PHYSTOPis the maximum physical memory address xv6 supports.)
copyuvmcurrently copies all the physical pages referenced by a page table. Modify it to not actually copy those pages, but instead:
- if the original page table entry is writeable, set both the old and new page table entry to read-only (and pointing to the the original physical page) and set the reference count for the physical page to 2.
- if the original page table entry is not writeable (but it is accessible), make the new page table entry a copy of it (pointing to the same physical page), and increment the reference count for the physical page.
When a program attempts to write to a read-only page, it will trigger a fault where the
trapnomember variable of
T_PGFLT, just like it does for virtual pages which are marked as not present. Most simply, you can distinguish it from a “normal” page fault by looking up the page table entry for the faulting address (the faulting address is available by calling
rcr2()) and checking if that page table entry is marked as present (valid) but not writable.
Fortunately, xv6 has no other reason it mark user pages as read-only, so you can always assume that a page fault for a present, read-only user page is because of your copy-on-write scenario. (Even pages that only contain machine code are still loaded as writeable).
To copy page contents to a newly allocated page, you can use the function
memmovelike the original xv6
After you change page table entries for the currently running process from writeable to not writeable, you need to flush the TLB. (At least the entries of the TLB corresponding to the changed pages.) One way to do this is by reloading the page table base register CR3 using:
(It would be better to use an instruction that only flushes the TLB entries for a particular page, like
invlpg, but xv6 doesn’t have a convenient way to run that.)
deallocuvmare called to deallocate pages from a page table. Currently, they unconditionally call
kfreeon each page. In
deallocuvm, for user pages which are read-only, you should have them decrement the reference count of the page. Then, only if the reference count is 0, they should actually call
deallocuvmto the deallocation of user pages, then does the additional work to handle deallocating the kernel pages for the page table. For this homework, you probably aren’t changing how the page table pages are allocated, so you’ll probably be able to just change