Changelog:

To get support for running a test program in place of init as described below, you may need to git pull to get a more up-to-date version of xv6 or to git clone the repostory again. (I initially neglected to push to the master branch of the git repository.)

Your Task

  1. (required for checkpoint) 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.

    Your automatic allocation scheme:

    • Should initialize all newly allocated memory to zeroes, like happens with a stock version of xv6.
    • Should kill a process when it attempts to access memory outside of its allocation, including memory beyond the end of heap (except that heap allocations should be rounded up to a whole number of pages) or kernel memory, like happens with a stock version of xv6.
    • Should kill a process when it attempts to access memory requiring an allocation on demand and no more memory can be allocated. Make sure a message is printed to the console when this happens.
    • Should never make the “guard page” xv6 allocates below the user stack accessible in user mode.
    • Must make system calls that attempt to read or write to not-yet-allocated parts of the heap work. For example, malloc()ing a very large buffer, then using read() to fill it must work.
    • Should not leak memory.
  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. Your copy-on-write scheme:
    • Should kill a process when it attempts to write to memory, but there is not enough memory to allocate a copy-on-write page. Make sure a message is printed to the console when it happens.
    • Should not leak memory.
    • Should never make the “guard page” xv6 allocates below the user stack accessible.
    • Must make system calls that attempt to read or write to not-yet-allocated parts of the heap work. For example, malloc()ing a very large buffer, then using read() to fill it must work.
  3. Run make submit to create an archive and upload the result to Collab.

Testing

  1. We have supplied a program called pagingtest.c as an example of how you can verify that your implementation works. We will run other and/or additional tests when grading your submission, so this is not a substitute for doing additional testing.

    This includes tests for both allocate on demand and copy-on-write. The tests do a mix of things that should work regardless of whether you’ve implemented these features, and things which will run out of memory unless you’ve implemented allocate-on-demand and/or copy-on-write. When fork()ing fails (such as due to running out of memory), some of the copy-on-write tests may print a message about this a hang rather than printing a clear failure message. (Yes, this is probably a bug.)

  2. Since the xv6 shell uses fork and sbrk and you might break the implementation of these, it may be very difficult to debug when you break one of these. One strategy for debugging is to run xv6 with a test program acting as init (the first program the xv6 kernel runs). We have supplied some suitable test programs that work this way. Each of them uses this pagingtestlib.h header file which contains functions from pagingtest.c above and an additional setup() function that duplicates code from init needed to make outputting the console work correctly:

    To run these files as init, make sure you have a copy of our xv6 repository where you ran git pull or cloned it after 11 March 2019, put them in your xv6 directory and instead of running make qemu or make qemu-nox run something like

    make qemu-nox FS=fs-alloc_small-as-init.img

    This will create a virtual disk fs-alloc_small-as-init.img which is a copy of the xv6 filesystem, but with init program replaced by alloc_small, then boot xv6 using this virtual disk instead of the normal fs.img virtual disk.

    (When these tests work they should print a message like TEST:PASS: before exiting. Messages about a Makefile recipe failing are spurious if xv6 is actually run and prints the TEST:PASS: message.)

    If you get an error from make about temp-_alloc_small or something similar existing, you can remove this temporary directory and try again. (This is a bug in the Makefile.)

    When debugging, I would suggest using cprintf() in the kernel to print out what is happpening (e.g., what page table entries you are changing for what pid, when page faults happen, etc.).

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.

  6. Sometimes you may need to flush the TLB after a changing a valid page table entry that might be cached in the TLB. 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.)

On NULL pointers

  1. NULL, which is address 0, is a valid memory address in on xv6 and usually contains some of the machine code for the currently running program. However, some xv6 routines return NULL to indicate errors, like walkpgdir() and kalloc(). Be careful to always check for these routines returning NULL, because otherwise you’re only likely to know there’s a problem because of very weird behavior.

  2. Compilers generally assume that if you can successful access a pointer that it is not NULL, despite situations like in xv6 where NULL is a valid pointer. This means, for example, that many compilers will optimize:

    int *ptr = get_pointer_or_null();
int value = *ptr;
if (ptr != NULL) {
    do_something_with(value);
} else {
    panic();
}

    in a way that will never call panic(), no matter what get_pointer_or_null returns.

    To avoid this issue, make sure any checks for pointers being NULL occur before you use a potentially NULL pointer.

Handling/avoiding kernel page faults

  1. For debugging, I strongly recommend having code to print out a message and/or panicing when a page fault occurs within your page fault handling code. Otherwise, it is extremely difficult to figure out what’s going on when a memory error occurs.

    You will probably want to disable this code later on so you can handle page faults from system calls like read(). (Alternately, you could have system calls like read() and write() check for allocate-on-demand or copy-on-write in other than by triggering a page fault.)

  2. xv6 supports nested exception handlers, but you must be careful to not exhaust the single kernel stack, which must have enough space to handle both a system call and a page fault that occurs within the system call.

    When an exception occurs in kernel mode, the processor recognizes that it’s running in kernel mode already and doesn’t change the stack pointer to the top of the kernel stack, unlike an exception that occurs in user mode. This means that a page fault that occurs in the middle of a system call won’t overwrite information on the stack used by the system call.

    (In contrast, when an exception occurs in user mode, the processor switches to the kernel-mode stack specified in the “Task State Segment”. This is set by switchuvm().)

  3. If a page fault triggers a second page fault that triggers a third fault, the processor reboots the machine. This is also known as a triple fault.

On synchronization

  1. When implementing copy-on-write, there is a potential for synchronization issues when modifying information about pages (like reference counts) shared between different processes from system calls. To avoid this, you can use a spinlock or disable interrupts when accessing such potentially shared data.

    xv6 disables interrupts while handling page faults — so on a single core (which we will use), you don’t need to worry about the page fault handlers being interrupted. However, system calls are run without page faults or timer interrupts being disabled.

xv6’s guard page

  1. xv6 allocates a guard page below the user stack to catch stack overflows. This is the only page in the user’s memory which is marked as present but not user-accessible in the stock version of xv6.

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. The xv6 book chapter on trap handling is useful.

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

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

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

  6. 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 (beyond end of heap) memory.

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

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

  9. 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. For copy-on-write, you will essentially be changing:
    • the code that copies the pages on fork() in copyuvm() to only mark the pages read-only, and
    • moving the copying that was previously done by copyuvm() to the page fault handler, which will be run whenever the process attepmts to write to a read-only page.

  2. 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. (It also posssible to determine that a page fault was caused due to a page table entry not being marked writeable through the value of tf->err, see the Intel manuals, volume 3A, page 6-40, section “Exception Error Code”.)

    Fortunately, xv6 has no other reason it marks 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.) Alternately, you could add extra entries to struct proc to track where a process’s writeable memory is and look this up when a page fault occurs.

  3. The xv6 function memmove is handy for copying the contents of pages.

  4. When changing a valid page table entry to another valid page table entry, you may need to clear the TLB (as in the lcr3() code snippet above).

  5. deallocuvm is called to deallocate user pages from a page table. Currently, it unconditional call kfree on each page. You should change it to not deallocate pages that other processes have a reference to.

  6. You will need to track the number of processes that reference each physical page. Since scanning all page tables for references ot a page is really slow, it would make sense to have store a reference count for each phsyical page. A simple 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.)

    If you want to store extra information for each physical page, you can use a similar approach but with an array of structs.