Introduction

The purpose of this project is to add paging to your GeekOS kernel. This will require many small, but difficult changes. More than any previous project, it will be important to implement one thing, test it, and then move to the next one. A successful implementation of earlier projects is not required for this project. You can implement Project 4 on top of any earlier version of the kernel (or directly on the provided distribution).

This project will involve an intermediate submission and a final poject submission. The intermediate submission should be your implementation of the kernel memory mapping. It is worth 10 points (out of 100 for the project). To submit the intermediate submission just follow the same submission instructions as the final submission of project 4. For details, check the Intermediate submission section in the grading criteria.

Paging

In a system that combines paging and segmentation, there are three kinds of addresses: logical addresses, linear addresses, and physical addresses. Logical addresses are those issued by a process; these are mapped, via segmentation, to linear addresses by merely adding the base address of the relevant process segment to the logical address. A linear address is mapped to a physical address, which will be used by the processor to actually read from main memory, by using page tables set up and maintained by the operating system.  Paging is similar to segmentation because it allows each process to run in its own memory space. However, paging allows a much finer granularity of control by specifiying per-page mappings rather than a constant value offset.

Each page directory and page table are themselves pages in the system. Each page directory/page table entry is 4 bytes and each table contains 1024 entries (4096 bytes / 4 bytes). Each page directory contains a pointer to a page table which in turn contains pointers to the physical memory.

Part I

The first step is to modify your project to use page tables and segmentation rather than just segments to provide memory protection.

Kernel Memory Mapping

To set up page tables, you will need to allocate a page directory (via Alloc_Page) and then allocate page tables for the entire region that will be mapped into this memory context. You will need to fill out the appropriate fields in the page tables and page directories. The definition of paging tables and directories are to be found in paging.h (structs pte_t and pde_t). Finally, to enable paging for the first time, you will need to call the routine Enable_Paging(pdbr) which is already defined for you in lowlevel.asm. It takes the base address of your page directory as a parameter.

The final step of this function is to add a handler for page faults. A default one named Page_Fault_Handler in paging.c has been provided for you. You should install it by calling Install_Interrupt_Handler. You need to register this as a handler for interrupt 14. You should then add a call the Init_VM function from your main.c (after Init_Interrupts).

You should be able to do this step and test it by itself by temporarily giving user mode access to the to these pages - set the flags fields to include VM_USER.  Refer to item 1 in the grading criteria to understand what you should have running at this point.  Once you have this running, you can submit it as your intermediate submission.

Part II

User Memory Mapping

The memory layout for a user process is shown below, where the addresses on the left are linear addresses (which are mapped to physical addresses by the paging system).  User processes still refer to logical addresses, which are mapped by the segmentation system to the linear addresses shown here.  In particular, a user process will still have the same addresses just as it has in prior projects.

The next step is to modify your user processes to use pages in the user range of memory. To help you do this, there is a new file called uservm.c which will replace your userseg.c from previous projects. You should start by taking the implementations from userseg.c and copying them to uservm.c and then modifying them for paging. There is a line in the Makefile in the build directory which specifies whether it should use userseg.c or uservm.c. You can switch between them by modifying USER_IMP_C := uservm.c to be USER_IMP_C := userseg.c and vice versa.

Setting up paging for user processes occurs in Load_User_Program, and takes two steps.  First, you need to allocate a page directory for the process. You should copy all of the entries from the kernel page directory for the bottom 2 GB of linear memory.

At this point, you should test your memory mapping by running bochs. If you are able to load and run shell, you have completed this correctly.

Demand Paging

Virtual Memory

While paging is useful for efficiently managing memory, the processes that can be active are still limited by the amount of physical memory.  To remedy this, you will implement virtual memory as part of GeekOS, in which memory pages can be temporarily stored on disk so that the freed physical memory can be used by another process.  To do this, the OS will need to pick a page to evict from memory and write it to the paging file, stored on disk. You should implement a version of pseudo-LRU (see section 9.4.5 in text, pp. 336). Use the accessed bit in the page tables to keep track of how frequently pages are accessed. To do this, use the clock field in the struct Page in mem.h. You should update the clock on every page fault for all pages that were accessed since the last fault. Alternatively, you can update the clocks in the body of the Idle thread, i.e. walk thru the allocated pages and for ones that were accessed, update their clocks. This will avoid a heavy-weight page fault handler.

The code to page out a page is implemented for you in Alloc_Pageable_Page in mem.c, and works as follows:

Eventually, the page that was put on disk will be needed by some process again. At this point you will have to read it back off disk into memory (possibly while paging out another page to fit it into memory). Since the page that is paged out has its present bit set to 0 in the page table, an access to it will cause a page fault. Your page fault handler should then realize that this page is actually stored on disk and bring it back from disk (the kernelInfo field in the page table entry). When you bring a page in off disk, you may free the disk space used by the page. This will simplify your paging system, but will require that when a page is removed from memory it must always be written to the backing store (since even pages that haven't been written since they were last brought into memory from disk are not already on disk). You will rely on the information stored when a page is paged out to find it on disk and page it back in.

The following table summarizes the actions of your page fault handler.

Process Termination

As part of process termination, you will need to free the memory associated with a process. This includes freeing the pages used by the process, freeing the page tables and page directories. In addition, you will need to release the backing store space used by any pages of the terminating process. You should modify your Destroy_User_Context function in uservm.c to do this.

Extra Credit

As mentioned in recitation (and in recitation slides), you should use Alloc_Page() for allocating page tables and page directories and Alloc_Pageable_Page() for everything else (program memory, arguments, stack). This is intended to make your task easier, since you know the page tables are always in memory. For extra credit (10 points), try to make page tables pageable too, i.e. use Alloc_Pageable_Page() for page tables.