CMSC 412 Project #4

Paging

Extended thru Friday, November 12th, 2004 (6:00 PM)

Intermediate submission Due October 27th, 2004 (6:00 PM)

  • Grading Criteria
  • Submission Instructions
  • Recitation material: proj4.ppt
  • The IA-32 Intel(R) Architecture Software Developer's Manual,Volume 3
       Sections : 3.1, 3.6 (without subsections 3.6.1 and 3.6.2), 3.7.1, 3.7.6 (Figure 3-14 and associated bits only)

    New project files

  • project4-cyclone.tgz - new project distribution


  • Introduction

    The purpose of this project is to add paging to your project. This will require many small, but difficult changes to your project. More than any previous project, it will be important to implement one thing, test it and then move to the next one. A successfull implementation of Project 3 is not required for this project. You can implement Project 4 on top of either your Project 2, sample solution for Project 2, or your Project 3.

    This project will involve an intermediate submission and a final poject submission. The intermediate submission should be your implementation of the kernel mapping. There must a good faith effort submission or up to 10% may be taken off the final grade. To submit the intermediate submission just follow the same submission instructions as the final submission of project 4.

    Paging Introduction

    In this project you will add paging to the GeekOS kernel. You will be implementing a two-level paging system that includes page tables and directories. 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. The purpose of paging is to provide a mapping from a user address to a physical address. 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.

    This project will combine paging that you will implement in this project with the segmentation implemented in project 2. Each memory access by a user process will involve two steps. First, the base address of the user process will be added to the user memory address. Finally, the resulting linear address will be mapped to the physical address using the page directory and page tables.

    Each memory address in the x86 system is 32 bits long. When the system sees an access to a virtual address, it will first find the page directory currently in use (this is analagous to finding an LDT for a process). It will then use the most significant 10 bits to index into the page directory (10 bits allows you to write numbers between 0 and 1023 thus the page directory has 1024 entries). The page directory entry is used to find the appropriate page table. The next 10 bits are used to index the page table (again 10 bits allows you to write numbers between 0 and 1023 thus the page table has 1024 entries). Finally, the page table entry is used to find the base of the physical memory page. The last 12 bits of the virtual memory address is used to index into the physical page (12 bits allows you to write numbers between 0 and 4095 thus a page is 4096 bytes in size). For more information on paging please review your texbook (section 9.4) as well as the sections of the Intel documentation specified above.

    Changing the Project to Use Page Tables

    The first step is to modify your project to use page tables and segmentation rather than just segments to provide memory protection. To enable using page tables, every region of memory your access (both kernel and data segment) must have an entry in a page table. The way this will work is that there will be a single page table for all kernel only threads, and a page table for each user process. In addition, the page tables for user mode processes will also contain entries to address the kernel mode memory. The memory layout for this is shown below.



    VA 0x0000 0000 Kernel Memory

    Start of kernel memory

    (map all physical memory here)

    VA 0x8000 0000 User Memory Data/Text start here


    <gap>


    VA 0xFFFF E000 User Memory Initial stack at top of this page
    VA 0xFFFF F000 User Memory Args in this page
    VA 0xFFFF FFFF   Memory space ends here

    Kernel Memory Mapping

    The kernel memory should be a one to one mapping of all of the physical memory in the processor (this limits the physical memory of the processor to 2GB, but this is not a critical limit for this project). The page table entries for this memory should be marked so that this memory is only accessible from kernel mode (i.e. the flags bit in the page directory and page table should not contain VM_USER). To make this change, you should start by creating a page directory and page table entries for the kernel threads by filling in the Init_VM in the paging.c.

    To setup 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 kernel pages - set the flags fields to include VM_USER)

    User Memory Mapping

    The next step is to modify your user processes to use pages in the user region. 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 is a two-step process. This is done when you load the user program in Load_User_Program. First, you need to allocate a page directory for this user space. You should copy all of the entries from the kernel page directory you've set up in Init_VM. (This makes interrupt handling easy because you don't have to change the page tables when you switch back and forth).

    Next you need to allocate page table entries for the user processes text and data regions. When you create the executable image don't include space for the stack (but do round to PAGE_SIZE, though). Allocate (a page at a time) as many pages as needed to hold the executable image. Then copy the image, page by page into the newly allocated pages. Do not forget to add an entry for each newly allocated page in your process' s page table.

    Finally, you should allocate space for two pages of memory at the end of the virtual address range (i.e. the last two entries in the last page table). One is for the parameters, the other one is for stack. For the user space page mappings, make sure the flags bits in both the page directory and page table entries allow user mode access (contain VM_USER flag).

    Contrast this with what was done in project 2. There, one big chunk of memory was allocated for the entire user process. Paging allows per-page mappings for user memory as described in the introduction. Therefore, each page of the user process is now allocated and mapped individually.

    You will also need to change some aspects of how the code from project #2 sets things up. The base address for the user mode process should be 0x8000 0000, and the limit should be 0xFFFF FFFF. Segmentation, as described in the introduction will allow the user space process to think that its virtual location 0 is the 2GB point in the page layout and will greatly simplify your kernel compared to traditional paged systems. You will also need to add code to switch the PDBR register. For this, in Switch_To_Address_Space you should add a call to Set_PDBR (provided for you in lowlevel.asm) as part of a context switch, after you load the LDT. You will use the pageDir field in the userContext structure that will store the address of the process's page directory).

    You have been provided with a second version of Alloc_Page (in mem.c). This version is called Alloc_Pageable_Page. The primary difference is that any page allocated by this routine should have a special flag PAGE_PAGEABLE set in the flags field of its entry in the struct Page data structure (see mem.h). All pages (but not page directories and page tables) for a user space process should be allocated using this routine.

    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.

    Handling Page Faults

    This step involves modifying the default page fault handler that has been used until now. One of the key features of using paging is to have the operating system handle page faults. To do this you will use a page fault interrupt handler. The provided default page fault handler figures out the address of the page fault and prints it out. You will modify it to determine an appropriate action to take based on the address. Possible reasons for a page fault, and the action to take are shown in the table below.


    Cause Indication Action
    Stack growing to new page Fault is within one page of the current stack limit Allocate a new page and continue.
    Fault for paged out page Bits in page table indicate page is on disk Read page from paging device (sector indicated in PTE) and continue.
    Fault for invalid address None of the other conditions apply Terminate user process

    You should already have installed a default page fault handler when setting up the kernel mapping. In order to test the page fault handler, run the provided program rec.c.

    The fault handler reads register cr2 to determine the faulting address. It also prints the errorCode field defined in the struct pageFaultErrorCode in paging.h

    Paging Out Pages

    At some point, your operating system will run out of pages to assign to processes. In this case, you will need to pick a page to evict from memory and write it to the backing store (paging file). You should implement a version of pseudo-LRU (see section 10.4.5 in textbook). 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.

    You will also need to manage the use of the paging file. The paging file consists of a group of consecutive 512 (SECTOR_SIZE) bytes disk blocks. Calling the routine Get_Paging_Device in vfs.h, will return a Paging_Device structure containing the first disk block number of the paging file and the number of disk blocks in the paging file. Each page will consume 8 consecutive disk blocks (PAGE_SIZE/SECTOR_SIZE). To read/write the paging file, use the functions Block_Read and Block_Write provided in blockdev.h. These functions write SECTOR_SIZE bytes at a time. How you manage your paging file is completely up to you. A good idea would be to write a Init_Pagefile function in paging.c and call it from main.c

    The following paragraph describes what is done whenever a page is paged out. However, the high level code to page out a page is implemented for you in Alloc_Pageable_Page in mem.c. The function will do the following:

  • Find a page to page out using Find_Page_To_Page_Out which you will implement in mem.c. (This function relies on the clock field in the Page structure which you must manage).
  • Find space on the paging file using Find_Space_On_Paging_File which you will implement in paging.c
  • Write the page to the paging file using Write_To_Paging_File which you will implement in paging.c
  • Update the page table entry for the page to clear the present bit.
  • Update the pageBaseAddr in the page table entry to be the first disk block that contains the page.
  • Update the kernelInfo bits (3 bits holding a number from 0-7) in the page table entry to be KINFO_PAGE_ON_DISK (used to indicate that the page is on disk rather than not valid).
  • Flush the TLB using Flush_TLB from lowlevel.asm
  • Page Ins

    In the previous section on page outs, it was described how a page is picked and stored on disk to make space for another page. 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, 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 discard its disk version (i.e. 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 clean pages no longer have a version 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.

    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.