CMSC 412 Project 4

Updates

• Oct 30: Indicated that Enable_Paging takes an argument.
• Nov 1: Clarified the requirement on null pointer references in Part 1.

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, though as always, it may help your testing to have background processes and ps available. You can implement Project 4 on top of any earlier version of the kernel (or directly on the provided distribution).

This project has an intermediate submission (Part I) and a final (Part II) submission. The Part I submission is your implementation of the kernel memory mapping. It is essentially a warm-up for the bulk of the project, and it is worth 10% of your project grade.

Note

• There will be two separate projects on the submit server, one for each part. The submission procedure is the same as always, except that the .submit file has to be updated between submissions of part I and part II. You can do this with svn update (we will update the .submit file on the svn server on November 5) or by hand-editing the file.
• Old discussion slides:
  • Project4-part1.pdf
  • Project4-part2.pdf
  • Yet older: project4.pdf
• Excerpt from Dave Hovemeyer's GeekOS hacking guide: paging.pdf
• Shankar's GeekOS overview; see Sections 4 and 5 and the memory map in Appendix B
• The IA-32 Intel(R) Architecture Software Developer's Manual, Volume 3a. This is an essential reference for this project.
  • Start with sections 3.1, 3.4, and 4.3. You may wish to refer to sections 3.3 and 4.2 for terminology.
  • As you read those sections, refer back and forth to Figure 3-1, "Segmentation and Paging."
  • You will be manipulating data structures that are described in Figures 4.2 and 4.4 and Tables 4.3, 4.5, and 4.6.
  • Sections 3.2, 3.5, 4.6, 4.7, and 4.8 provide additional information once you feel comfortable with the way paging and segmentation combine.
  We are using 32-bit paging and 4KB (not 4MB) pages. You can ignore anything about IA-32e (extended mode) or PAE (physical address extensions).
• Text (depending on your edition, section numbers may differ but titles should not):
  • Memory management: Paging (9.4); Segmentation (9.5); Segmentation with Paging (9.6); Summary (9.7).
  • Virtual memory: Background (10.1); Demand Paging (10.2).

Background

In this project you will add paging to the segmentation that is already present in the GeekOS kernel. You may wish to refer to earlier discussion on segmentation from Project 1. For detailed information on paging, segmentation, and how they are combined on the Intel architecture, please refer to the Intel documentation and text sections mentioned above.

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 (its compiled assembly code, or more precisely, its elf executable). They have the form s:x, where s identifies a segment (e.g., CS, SS, DS in x86) and x is an offset from the start of the segment. A logical address s:x is mapped, via segmentation, to a linear address by adding x to s's base address. A linear address is mapped, via paging, to a physical address, which is a location in main memory. Linear addresses (linear memory) are also referred to as virtual addresses (virtual memory), especially when there is no segmentation.

Paging, like segmentation, allows each process to run in its own memory space. However, paging allows much finer granularity in the mapping of process memory to physical memory. Instead of a process's memory being mapped to one chunk of physical memory (the only flexibility being the offset), it can be mapped to different pages that may be scattered through physical memory. This allows us to implement two useful features: demand paging, which allows a user process's stack to grow dynamically; and paging to disk, which allows a user process's memory to be "paged out" to disk, enabling the runnable processes' memory to be greater than the physical memory.

In GeekOS, your paging system will have two levels: each process has a page directory, whose entries point to page tables, whose entries point to physical pages. When paging is turned on, a register in the processor points to the page directory of the currently executing process. The processor translates a linear address (32 bits in x86) to a physical address as follows:

1. It uses the most significant 10 bits of the linear address to index into the current process's page directory to obtain a page directory entry. (The page directory has 1024 entries.)
2. The processor then accesses the page table pointed to by the page directory entry. It uses the next 10 bits of the linear address to index into the page table to obtain a page table entry. (The page table has 1024 entries.)
3. The processor then accesses the physical page pointed to by the page table entry. It uses the last 12 bits of the linear memory address to index into the physical page. (A page is 4096 bytes in size.)

Each page directory and each page table is itself a 4K page in the system. Each directory entry and each table entry is 4 bytes (so 1024 entries fit in a 4K page).

Part I

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

Kernel Memory Mapping

The kernel currently starts running without paging enabled; linear addresses generated by the segmentation hardware are used as physical addresses. Adding paging introduces a level in between: a logical address is mapped by segmentation to a linear address, and then mapped through the page tables to a physical address. As a first step, we will introduce a page table that maps all linear addresses to themselves: that is, each linear address X is mapped to physical address X. (In Part II, this will become the page table for kernel-only threads.) This scheme enables us to turn on paging in a way that is transparent to much of the other memory-management code.

To set up paging, you need to allocate a page directory (via Alloc_Page) and then allocate page tables (also via Alloc_Page) to cover the entire physical memory. Do this in function Init_VM in paging.c. Fill in the appropriate fields in the page directory entries and page table entries. The definitions of these entries are in paging.h (structs pte_t and pde_t). They are also described in Figure 4-4 of the Intel manual.

When you create the page tables and page directory, do not map the page with linear address zero. Leaving this page unmapped means that null pointer references will cause a page fault, instead of silently succeeding with an unexpected result.

You also need to enable paging (recall that GeekOS does not use paging by default). Do this also in function Init_VM, by calling the routine Enable_Paging, which is already defined for you in lowlevel.asm. It takes the base address of your page directory as a parameter.

You also need to register a handler for page faults. Do this also in function Init_VM. Currently, a page fault can occur only when a process attempts to access an invalid address (not present in physical memory). Therefore, we have provided a default handler, Page_Fault_Handler in paging.c, which terminates a user program that does this. Register it for the page fault interrupt, interrupt 14, by calling Install_Interrupt_Handler.

You should then add a call to the Init_VM function from your main.c (after Init_Interrupts).

You should be able to test this part by temporarily giving user mode access to these pages, by setting the flags field in the page table and page directory entries to include VM_USER. This allows user programs complete access to the pages referenced by the table.

To complete your intermediate submission, insert a call to checkPaging() before and after you call Enable_Paging() in Init_VM(). So your code should look like:

      checkPaging();
      Enable_Paging(dir);
      checkPaging();

      Paging on?: 0
      Paging on?: 1

Part II

User Memory Mapping

You will add a page directory for each user process. The page directory for a user process will contain entries mapping user logical memory to linear memory, and will also contain entries to address the kernel memory. This is not so that user processes can access kernel memory directly (set the access flags of the kernel memory to prevent them from doing so), but rather so that when an interrupt occurs, the page directory does not need to be changed for the kernel to access its own memory; it will simply use the page directory of the user process that was running when the interrupt occurred.

The layout of the linear address space of a user process is shown below. The particular (linear) addresses shown at the left will be important in your paging implementation, so define constants in paging.h to represent them.

The next step is to modify your user processes so that the logical addresses they generate are mapped to linear addresses in the user range of memory (i.e., from 0x8000 0000 to 0xFFFF FFFF). To help you do this, there is a new file called uservm.c that 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. In the file Makefile.common in the build directory, there is a line which specifies which of userseg.c or uservm.c should be used. You can switch between them by modifying the variable USER_IMP_C. If you do svn update in your network directory, this change will already be in place.

To set up paging for user processes, you will make changes to Load_User_Program in uservm.c. There are two steps.

1. 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 physical pages at the bottom of the address space.
2. Next, allocate page table entries for the user process's text, data, and stack regions. Each of these regions will consist of some number of pages allocated by the routine Alloc_Pageable_Page. This routine differs from Alloc_Page in that the allocated page it returns will have a special flag PAGE_PAGEABLE set in the flags field of its entry in the struct Page data structure (see mem.h). This bit tells the kernel that the page can be written to disk (paged out) when a page of memory is needed elsewhere but no free pages are available. All pages (but not page directories and page tables) for a user space process should be allocated using this routine.

Contrast this with the current implementation: with segmentation, one big chunk of memory was allocated for the entire user process. Paging allows per-page mappings for user memory; each user page is now allocated and mapped individually, and so the user memory need not be contiguous in physical memory. (More sophisticated use of segmentation would let us use non-contiguous physical memory, but paging gives us much more granularity and control.)

Once you have these changes in place in Load_User_Program, you will need to rewrite some of the code that actually loads the program into memory. A basic (somewhat inefficient) way to do this is the following:

• Calculate the size of the text and data segment of the process as is done now, without including the size of the stack (do round to PAGE_SIZE, though), and Malloc it.
• Load the program into this memory, as now. Copy the image, page by page, into the newly allocated pages.
• Allocate two pages of memory at the end of the linear address range (i.e., the last two entries in the last page table, as shown in the figure above). One is for the arguments, the other one is for stack. Make sure the flags bits in both the page directory and page table entries allow user mode access (contain the VM_USER flag).
• Unmap the first page to support null pointer checking.

Finally, you will need to tweak some aspects of the current segmentation implementation so that it works with paging. The base linear address for the user mode process (that is, the base address for the code and data segments set in Create_User_Context) should be 0x80000000 (USER_VM_START in paging.h), and the limit should be (USER_VM_END – USER_VM_START) / PAGE_SIZE, rounded up. This will allow the user process to use logical address 0 to refer to the 2GB point in the linear address layout.

You will also need to add code to switch the PDBR (cr3) register as part of a context switch. For this, in Switch_To_Address_Space you should add a call to Set_PDBR (provided for you in lowlevel.asm), after you load the LDT. You will use the pageDir field in the User_Context structure that will store the address of the process's page directory.

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

Demand Paging

A nice benefit of paging is that it is straightforward to dynamically allocate physical memory to a page in a process's linear address space. For example, you can allow the process's stack to grow beyond its initial allocation. To implement stack growth, you need to modify the default page fault handler from Part I. The fault handler reads register cr2 to determine the faulting address. It also prints the errorCode defined in InterruptState and the fault defined in the struct faultcode_t in paging.h.

You will modify this page fault handler to determine an appropriate action to take based on the address. If the address is within one page of the current stack limit, allocate a new physical page, map the appropriate virtual page (which expands the stack) to this physical page, and return normally from the handler. The program will now be able to use the memory that you just allocated to grow the stack beyond its old page. In order to test your new page fault handler, run the provided program rec.c.

Paging to Disk

Paging, as you have implemented it up to this point, is useful for efficiently managing memory. However, all active processes must still fit in physical memory. To remedy this, you will implement paging to disk, 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 an approximate-LRU algorithm (see section 9.4.5 or 10.4.5 in the text, depending on your edition). Use the accessed bit in the page tables to keep track of what pages have been accessed. To implement the second-chance page replacement algorithm (also called the clock algorithm), you will maintain a static "clock" value that points to a struct Page in the array of pages. (Note that this value has nothing to do with time: it's called the clock because of the analogy with a clock hand in the algorithm.) To find a page that can be paged out, you will look at the page's accessed bit. If it is set, clear it and increment the clock value. If it is clear, claim the page. When the clock value reaches the end of the array of pages, set it back to the beginning.

The paging file consists of consecutive disk blocks of SECTOR_SIZE (512) bytes. 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 eight consecutive disk blocks (PAGE_SIZE/SECTOR_SIZE). To read and write the paging file, use the functions Block_Read and Block_Write. These functions write SECTOR_SIZE bytes at a time. Note that you must call these functions with interrupts enabled, since disk I/O depends on interrupts. How you manage your paging file is up to you. You may want to write a Init_Pagefile function in paging.c and call it from main.c.

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

• Find a page to page out using Find_Page_To_Page_Out, which you will implement in mem.c.
• 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.

Eventually, the page that was put on disk will be needed by some process again. The process will simply access memory from the page, without knowing that it has been paged out. 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, using the kernelInfo field in the page table, and bring it back from disk. (Of course, you may have to store some other page on disk to make space for the page you are paging in.) 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 requires that a page must be written to the page file at the time it is paged out (rather than being written earlier, so that its physical memory can be reclaimed quickly). 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.

Copying Data Between Kernel and User Memory

Because the GeekOS kernel is preemptible and user memory pages can be stolen at any time, some subtle issues arise when copying data between the kernel and user memory spaces. Specifically, the kernel must never read or write data on a user memory page if that page has the PAGE_PAGEABLE bit set at any time that a thread switch could occur. If a thread switch did occur, another process could run and steal the page. When control returned to the original thread, it would be reading or writing the wrong data, causing memory corruption.

There are two general approaches to dealing with this problem. One is that interrupts (and thus preemption) should be disabled while touching user memory. This approach is not a complete solution, because it is not legal to do I/O (i.e., Block_Read and Block_Write) while interrupts are disabled. The second approach is to use page locking. Before touching a user memory page, the kernel will atomically clear the PAGE_PAGEABLE flag for the page; this is referred to as locking the page. Once a page is locked, the kernel can then freely modify the page, safe in the knowledge that the page will not be stolen by another process. When it is done reading or writing the page, it can unlock the page by clearing the PAGE_PAGEABLE flag. Page flags are shared data, so they should only be modified when interrupts are disabled.

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 page file space used by any pages of the terminating process. You should modify your Destroy_User_Context function in uservm.c to do this.