Project 5: Virtual Memory

Overview

Your previous kernels used a single global memory layout, where the kernel and all processes shared access to the same memory, and granted kernel permissions to all user processes.

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 allocation
• paging to and from disk
• page fault handler

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.

Steps

Checklist

• memory.h
  • page_map_entry_t
• memory.c
  • page_addr()
  • page_replacement_policy()
  • page_alloc()
  • init_mem()
  • setup_page_table()
  • page_swap_in() and page_swap_out()
  • page_fault_handler()

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? Make use of the provided functions init_ptab_entry(), insert_ptab_dir(), and set_ptab_entry_flags() when setting page table entries, page directory entries, and page entry flags.

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 page tables to make. Each kernel page table should contain PAGE_N_ENTRIES (1024) entries, until the page base address of a page reaches MAX_PHYSICAL_MEMORY.

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

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

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. This means that each process has four types of pages: page directory, page table, stack page table, and stack 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 setup_page_table() to load the code and data of a user process into its virtual address space. You will need to allocate its pages and load the process. The page directory of a task is determined by pcb->page_directory. This needs to be set when you're setting up the page tables.

There are two more things that you will need to set up the address space and that will help you with keeping track of page mappings:

• You will need a way to obtain the physical address of a page based on its page frame index. To do this, implement the page_addr() function
• To help you keep track of all pages and their metadata (e.g. whether or not it's pinned), you should define the page_map_entry_t data structure in memory.h

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.

NOTE: You will probably want to clear the page at this point. Doing later will be hard!

Paging to/from Disk

Check out the PCB fields swap_loc and swap_size. They will be very helpful here.

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: This is a good place to make sure that you are flushing the TLB appropriately.

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

Page Fault Handler

• Find the faulting page in the page directory and page table
• 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. You will want to use some synchronization primitives to handle this.

Testing

Unlike project3, which could be broken down into several phases for testing, you will need to understand and implement project 5 in its entirety before you can test your work.

This will be frustrating, but Don't Panic! The test processes that are part of the start code and are built into the disk image upon compilation should demonstrate where your problems lie.

To test your project 5, simply make your code, and run with Bochs.

Design Review

Hints and FAQs

Program Submission

Extra Credit

For 2 points of extra credit, implement a FIFO with Second Chance paging policy. To test this, you can modify the loaded the processes, threads, etc. If you're particularly clever, you can test it by adjusting some of the constants in the memory.h and then running process 3 and 4.