Project 5: Virtual Memory

Overview

Now, you will extend the provided kernel with a demand-paged virtual memory manager and restrict user processes to user mode privileges (ring 3) instead of kernel mode privileges (ring 0). You will implement:

• virtual address spaces for user processes
• page fault handler
• page allocation
• paging to and from disk

As a result, each process will get its own address space and will not be allowed to use certain instructions that could be used to interfere with the rest of the system. Assuming the kernel and kernel threads have no bugs/vulnerabilities, this will prevent buggy or malicious processes from corrupting the kernel and other processes. Furthermore, paging memory will allow programs to use more data than is available in RAM.

Aaron Blankstein is the TA in charge.

Important Dates

Finding Your Way Around this Project

The big stuff of this project is going to be in memory.c and memory.h. The code for this project is a bit different from the other projects so far (e.g., PCB structure is different.) Don't Panic! It'll make sense to you if you look at it and you won't actually need to mess with much of the code outside of memory.[ch]

There are a bunch of constants hanging around these files that you'll want to use:
$ grep "PROCESS_STACK" *.h
$ grep "PROCESS_START" Makefile
$ grep "PAGE" *.h

Note: this start code ships with its own bochs VGAROM and ROM. You may have to edit the provided bochsrc to get it to point to the right places... but it should be okay!

Design Review

• Page table + Page Faults (2 points)
  Explain how virtual addresses are translated to physical addresses on i386. When are page faults triggered? How are you going to figure out what address a fault occurred on?
• Page Map (1 point)
  You're going to need a data structure to track information about pages. What information should you track?
• Calling Relationships (2 point)
  For the functions page_alloc, page_swap_in, page_swap_out, and page_fault_handler, please describe the caller-callee relationship graph.

Also, you should read through the whole project description before showing up to design review. Students missed points last time around for questions with answers directly on the project description.

Page Table Setup

You must set up a two-level page table to map virtual to physical addresses, as described in class and in your course textbook, for each process. The i386 architecture uses a two-level table structure: one page of memory is set aside as a directory that has 1024 entries pointing to the actual page tables. Each of these page tables also has 1024 entries describing pages of virtual memory. You need to understand this structure well.

That last statement needs to be reiterated. You will need to understand what page table entries must look like. How are flags set? How do you map a virtual address to a particular entry? How do you store the physical page address for the entry?

The page directory of a task is determined by pcb->page_directory. You should set that.

Kernel threads all share the same kernel address space and screen memory, so they can use the same page table. Use N_KERNEL_PTS (the number of kernel page tables in the kernel page directory) to determine how many kernel pages tables to make. Each kernel page table should contain 1024 entries until MAX_PHYSICAL_MEMORY has been mapped.

Notice that our initial values for you can all fit in one table. It's OK to map more than required (for example, you can map the whole page table).

User process's virtual address space:

• Map kernel and screen to their physical addresses ( virtual = physical )
• Map addresses for the process' code and data segments to its own pages. Look at PROCESS_START and PROCESS_STACK for an idea of where in virtual memory everything resides. You should allocate N_PROCESS_STACK_PAGES pages for a process stack.
• Kernel memory: inaccessible
• Screen memory: read-write
• Other memory: read-write

Implement init_memory to initially map your physical memory pages to run the kernel threads.

Implement setup_page_table to load the code and data of a user process into its virtual address space. However, you do not need to load the process or allocate its pages right away. Instead, prepare its virtual address space and mark all of the pages as invalid. When the process is run and first accesses its pages, a page fault will be generated and your handler will automatically take care of allocating and loading the needed page.

Page Fault Handler

• Allocate a page of physical memory.
• Load the contents of the page from the appropriate swap location on the USB disk. (How are you going to figure out the swap location?)
• Update the page table of the process.

page_fault_handler may be interrupted, which means there might be two concurrent page_fault_handler calls. Use the necessary synchronization primitives to protect your data structures.

Page Allocator

Some pages may be so important or frequently used (or it might just be more convenient for you) that they should never be paged out. For example, you should never evict page tables. Such pages are pinned. Implement a mechanism for pinning pages so that they are never evicted by your page allocator.

We can artificially limit the amount of physical RAM available to your OS by setting PAGEABLE_PAGES to some lower number (try the 20s) in memory.h. This way, the total available physical memory is smaller than the total memory needed to run all the processes, requiring the system to use your paging implementation. This is a helpful value to change for testing.

You are probably going to want to clean the page at this point. Doing it later will be hard!

Paging to/from Disk

Check out the pcb variables swap_loc and swap_size. They will be very helpful

You may assume that processes do not use a heap for dynamic memory allocation: a process does not change size. In this case, the user memory space of a process contains an interval of pcb->swap_size sectors starting from PROCESS_START, plus the memory for user stack.

Note that you will need to flush the TLB (tlb.h) appropriately for this project.

You will find the functions in usb.h helpful for this part of the assignment.

Checklist

• page_alloc()
• init_memory() to set up the kernel pages and any other data structures your memory.c code will be using.
• setup_page_table() to set up the page table for a new task. For kernel threads, they should use the pages from init_memory(). For processes, each process needs a different set of pages.
• page_fault_handler() and page_swap_in()
  With all of the above implemented, increase PAGEABLE_PAGES and you should be able to run the test
• Implement swapping pages out with page_swap_out() and page_replacement_policy().