Changelog:

Your Task

  1. 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()->killed to 1 before returning to trap()) and write a message to the console using cprintf.

    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.

  2. 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 cprintf.

    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.

  3. Run make submit to create an archive and upload the result to Collab.

Testing

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.)

  1. 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.

Hints

xv6 book reading

  1. Chapter 2 of the xv6 book describes how xv6 manages its page table structures.

Handy xv6 functions/code snippets

  1. walkpgdir takes 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 walkpgdir with something like myproc()->pgdir.

    On an error, like failing to allocate a second-level page table, walkpgdir return the address 0x0 converted to a pte_t*. You should check for this address explicitly. In particular, accessing address 0x0 will 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.

  2. mappages takes 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, PGROUNDDOWN(0x1800) is 0x1000.)

  3. P2V converts 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+x to physical address x, and P2V uses these addresses (that is, it adds 0x80000000). V2P does the opposite mapping.

  4. kalloc and kfree allocate or free a physical page. They both return pointers to the virtual address of the page in the kernel’s memory.

  5. You can check if a page table entry pointed to by a pte_t *pte is 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 mypage as writeable, present, and accessible in usermode using *pte = mypage | PTE_P | PTE_W | PTE_U;. You can also call the utility function mappages to do this, provided the page is not already marked as present.

Allocating pages on demand

  1. Currently, when a program tries to allocate more heap space it calls the sbrk() system call, which calls growproc(). This sets the sz variable 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 allocuvm() instead of 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.)

  2. 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.

  3. The xv6 book chapter on trap handling is useful.

  4. You can modify the functions in trap.c to detect when a page marked invalid in the page table is accessed.

  5. traps.h defines the constant T_PGFLT, which is the code x86 uses to identify page faults. This will be placed in the trapno member variable of the trapframe.

  6. 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 rcr2().

  7. 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.

  8. xv6 contains page allocation and deallocation functions in kalloc.c, which are kalloc() (allocates a page) and kfree() (deallocates a page).

  9. 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.

  10. To make fork() work correctly, 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

  1. 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.

    (PHYSTOP is the maximum physical memory address xv6 supports.)

  2. copyuvm currently 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.

  3. When a program attempts to write to a read-only page, it will trigger a fault where the trapno member variable of trapframe is 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).

  4. To copy page contents to a newly allocated page, you can use the function memmove like the original xv6 copyuvm function does.

  5. 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:

    lcr3(V2P(myproc()->pgdir));

    (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.)

  6. freevm and deallocuvm are called to deallocate pages from a page table. Currently, they unconditionally call kfree on 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 kfree.

    freevm calls deallocuvm to 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 deallocuvm.