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). Your VMM will implement:

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. Furthurmore, paging memory will allow programs to use more data than is available in RAM.

CJ Bell is the TA in charge.

Design Review

First, take a look at what we expect from you in general.

You must explain:

You will find details on virtual address translation in chapters 2 to 4 of the Intel Architecture Software Developer's Manual, Volume 3: System Programming Guide.

Getting Started

Download the starter code.

Refer to previous projects for information on building and testing your project.

We have already provided a

Project Files

Miscellaneous
common.h Common constants, macros, and type definitions
createimage.c Tool to create a bootable operating system image on a USB disk
Makefile A makefile for you to compile with the right options.
util.c
util.h		 Library of useful support routines

Bootloader
bootblock.s Code for the bootblock of a bootable disk
cantboot.s Code for the bootblock of a non-bootable disk

Kernel
entry.S Code for entry point of interrupts
interrupt.c
interrupt.h		 Interrupt handlers
kernel.c
kernel.h		 Kernel code
keyboard.c
keyboard.h		 Keyboard handling code
mbox.c
mbox.h		 The implementation of the mailbox mechanism
memory.c
memory.h		 Physical memory page allocator, page table handling, and virtual memory mapping
scheduler.c
scheduler.h		 Scheduler code
sleep.c
sleep.h		 Contains function to allow processes to sleep for some milleseconds
thread.c
thread.h		 Synchronization primitives
time.c
time.h		 Time calibration
usb.c
usb.h		 Code to access the USB disk
usbV86.S Code for the USB disk driver

Threads
th.h Header file of th1.c and th2.c
th1.c Code of the loader thread and the clock thread
th2.c Code of two kernel threads to test synchronization primitives

Processes
shell.c A primitive shell that uses the keyboard input
syslib.c
syslib.h		 System calls
process1.c The first user process
process2.c The second user process
process3.c One of the processes to test the mailboxes
process4.c The other process used to test the mailboxes

Page Table Setup

You must setup a two-level page table to map virtual to physical addresses, as described in class (REF) and in your course textbook (REF), 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.

Kernel threads all share the same kernel address space, so they can use the same page table.

User process' virtual address space:

Implement init_memory to initially map your physical memory pages to run the kernel threads and 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 first run and on each first-access of 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

Write a page fault handler in page_fault_handler to handle the case where a process tries to access a page that is not currently in RAM. The handler should:

Page Allocator

Write a physical page frame allocator, allocate_page, to prepare a free page of physical memory. If there are free pages available, the job is simple: pick one. Otherwise, you must choose one to page-out to disk, implemented in page_replacement_policy, and then reset the page to be used again.

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 they are never evicted by your page allocator.

We artificially limit the amount of physical RAM available to your OS by setting PAGEABLE_PAGES in memory.h to 29. 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 pagaing implementation. This is a helpful value to change for testing.

Paging to/from Disk

If there are no more free physical pages for your page allocator to allocate, you must choose a page to evict, writing it to a backing store on disk: implement swap_out. You also must page in from disk in swap_in.

You may simplify the mapping between virtual addresses and disk addresses (the backing store) on the USB disk by mapping addresses in a process to the process' location in the image file on disk. In other words, when a page is paged-out of physical memory, write it back to the USB disk in the same location it was loaded from. Mind the boundary cases.

For this, you may assume that processes do not use a heap for dynamic memory allocation: a process does not change size. Note that with this approach, you will have to cat the image to disk each time you run the OS in order to reset the state of the programs.

Using this approach doesn't allow you to page out a process' stack because it does not exist in the image. You may pin stack segments, so they are never evicted, when you initialize each process' address space.

A better approach will earn you extra credit.

Checklist

Note: this is not intended to be a thorough list; just a quick reference.

Functions to implement in memory.h:

init_memory setup page table entries for kernel threads
setup_page_table setup a page table entry for a new user process (and effectively load the code and data)
page_fault_handler handle when a page is accessed that is not currently loaded into RAM (or doesn't exist)
allocate_page allocate a free page
page_replacement_policy decides which pages to swap in and out
swap_in loads a page from the backing store
swap_out writes a page to the backing store
We only provide definitions for the functions above that other parts of the kernel use.

Grading

The writeup should include: Your writeup does not need to cover how to build and run your code; we expect those details to remain the same.

We don't have strict rules concerning style; strive for clear code with meaningful comments.

Submission

Don't forget to complete the general requirements for each project!

When you are ready to submit, first run make distclean.

Submit via blackboard; only one person per group should submit.

Extra Credit

FIFO Replacement Policy

 For 0.5 points, implement the FIFO replacement policy described in class. For an additional 0.5 points, implement the FIFO with a second-chance replacement policy.

Paging

 For 1 point, implement a backing store that doesn't overwrite programs in the disk image, pages out stack pages instead of pinning them, and finally, only writes back a page if it has been modified. This extra credit will be due a few days after the main project