CPSC–410/611/613 Machine Problem 3 Page Table Management solved

Introduction The objective of this machine problem is to get you started on a demand-paging based virtual memory system for our kernel. You will study the paging mechanism on the x86 architecture and set up and initialize the paging system and the page table infrastructure for a single address space, with an eye towards extending it to multiple processes, and therefore multiple address spaces, in the future. In this machine problem we limit ourselves to managing small amounts of memory, which in turn allows us to keep the page table in physical memory. (In a future MP we will store the page table itself in virtual memory!) Make sure that you are familiar with the lesson on “Paging on the x86” before starting work on this Machine Problem. Page Management in Our Kernel The memory layout in our kernel looks as follows: • The total amount of memory in the machine is 32MB. • The memory layout is such that the first 4MB are reserved for the kernel (code and kernel data) and are shared by all processes. • Memory within the first 4MB will be direct-mapped to physical memory. By this we mean that logical address say 0x01000 will be mapped to physical address 0x01000. Any portion of the address space that extends beyond 4MB will be freely mapped: every page in this address range will be mapped to whatever physical frame was available when the page was allocated. • The first 1MB contains all global data, memory that is mapped to devices, and other stuff. • The actual kernel code starts at address 0x100000, i.e. at 1MB. In this machine problem we limit ourselves to a single process, and therefore a single address space. When we support multiple address spaces later, the first 4MB of each address space will map to the same first 4MB of physical memory, and the remaining portion of the address spaces will map to non-overlapping sets of memory frames. The paging subsystem represents an address space by an object of class PageTable to the rest of the kernel. The class PageTable provides support for paging in general (through static variables and functions) and address spaces. The page table is defined as follows: class PageTable { private : /* THESE MEMBERS ARE COMMON TO ENTIRE PAGING SUBSYSTEM */ static PageTable * current_page_table ;/* pointer to currently loaded page table object */ static unsigned int paging_enabled ; /* is paging turned on? (i.e. are addresses logical )? */ static FramePool * kernel_mem_pool ; /* Frame pool for the kernel memory */   CPSC–410/611/613 Machine Problem 3 static FramePool * process_mem_pool ; /* Frame pool for the process memory */ static unsigned long shared_size ; /* size of shared address space */ /* DATA FOR CURRENT PAGE TABLE */ unsigned long * page_directory ; /* where is the page directory ? */ public : static const unsigned int PAGE_SIZE = Machine :: FRAME_SIZE ; /* in bytes */ static const unsigned int ENTRIES_PER_PAGE = Machine :: PT_ENTRIES_PER_PAGE ; /* in entries */ static void init_paging ( FramePool * _kernel_mem_pool , FramePool * _process_mem_pool , const unsigned long _shared_size ) ; /* Set the global parameters for the paging subsystem . */ PageTable () ; /* NOTE1 : The PageTable * object * still must be stored somewhere ! Probably it is best to have it on the stack , as there is no memory manager yet ... NOTE2 : It may also be simpler to create the first page table * before * paging has been enabled . */ void load () ; /* Makes the given page table the current table . This must be done once during system startup and whenever the address space is switched (e.g. during process switching ). Loading a page table also flushes the TLB. */ static void enable_paging () ; /* Enable paging on the CPU. Typically , a CPU start with paging disabled , and memory is accessed by addressing physical memory directly . After paging is enabled , memory is addressed logically . */ static void handle_fault ( REGS * _r) ; /* The page fault handler . This method will be invoked by the hardware . */ }; We tacitly assume that the address space (and the base address of the direct-mapped portion of memory) starts at address 0x0. The shared size defines the size of the shared, direct-mapped portion (i.e. 4MB in our case). The page directory is the address of the page directory page. The physical memory will be managed by two so-called Frame Pools, which you implemented in a previous MP. Frame pools support the get and release operations for frames. Each address space is managed by two such pools (see kernel.C): • The kernel mem pool, between 2MB and 4MB, manages frames in the shared portion of memory, typically for use by the kernel for its data structures. Note that the kernel pool is located in direct-mapped memory; where physical and logical addresses are identical. • The process mem pool, above 4MB, manages frames in the non-shared memory portion. (For details see below.) Note that this pool is located in freely-mapped memory, where logical addresses are not the same as physical addresses. After the pools are initialized, the kernel goes through the following steps:  CPSC–410/611/613 Machine Problem 3 1. It calls the function init paging to set the parameters for the paging subsystem. 2. Once paging is configured, the kernel sets up the first address space by creating a first page table object1 . 3. The PageTable constructor sets up the entries in the page directory and the page table. The page table entries for the shared portion of the memory (i.e. the first 4MB) must be marked valid (“present” in x86 parlance). The remaining pages must be managed explicitly. (For more details see below.) NOTE: The constructor will need to grab a frame for the page directory; so make sure that you have access to a configured frame pool before you initialize the page table. Before returning, the constructor stores all the relevant information in the page table object. 4. After the page table is created, the kernel loads it into the processor context through the load() function. The page table is loaded by storing the address of the page directory into the CR3 register. The hardware, when needing to translate a virtual address into its corresponding frame, will know to start ”walking” the page tables by getting the address of the page directory from CR3. During a context switch, the system simply loads the page directory of the new process to switch the address space. 5. After everything is set up correctly, the kernel switches from physical addressing to logical addressing by enabling the paging through the enable paging() function. The paging is easily enabled by setting a particular bit in the CR0 register. Be careful that the page directory and page table is set up and loaded correctly before you turn on paging! The essence of this MP is to first set up the page table correctly and then to implement the method PageTable::handle fault(), which will handle the page-fault exception of the CPU. This method will look up the appropriate entry in the page table and decide how to handle the page fault. If there is no physical memory (frame) associated with the page, an available frame is brought in and the page-table entry is updated. If a new page-table page has to be initialized, a frame is brought in for that, and the new page table page and the directory are updated accordingly. Frame Management above the 4MB Boundary The memory below the 4MB mark will be direct mapped, and requires no additional management after the initial setup of the page tables. The memory above 4MB will have to be managed. The memory addressable by a single process in the x86 is 4GB. It is unlikely that a single process will need that much memory ever. Since we cannot predict which portions of the address space will be used, we will map the used portions of logical memory to physical memory frames. By default, memory pages above the 4MB mark have initially no physical memory associated. Whenever such a page is referenced, a page fault occurs (Exception 14), and a page fault handler takes over. The page fault handler performs the following steps: 1. It finds a free frame from a common free-frame pool. 2. It allocates this new frame to the process. 3. The page entry is updated accordingly. 1Remember that we don’t have a memory manager yet, and the new operator does not work. Therefore, we create the first page table object on the stack (we did the same before with the frame pools).   CPSC–410/611/613 Machine Problem 3 4. The page fault handler returns. 5. The CPU then retries the instruction and this time finds the physical-to-virtual mapping ready to be used in the paging data structures. A Note about the First 4MB Don’t get confused by the fact that the kernel frame pool does not extend across the entire initial 4MB, and ranges from 2MB to 4MB only. The first MB contains the GDT2 , the IDT3 , video memory, and other stuff. The second MB contains the kernel code and the stack space. We don’t want to hand part of the memory to the kernel to store its own data. Nevertheless, do not forget to initialize the page table to correctly map the entire first 4MB! Where to store Memory Management Data Structures Given that we don’t have a memory manager yet, we find ourselves in a bit of a dilemma when it comes to storing the data structures needed for the memory management. The stack space is limited, so it has to be used judiciously. A better solution is to request frames from the appropriate pool and store the data structures there. (The objects themselves, such as the page table object or the frame pool objects, can of course be stored on the stack. These objects are small, mostly pointers to data structures that are held elsewhere.) The page directory and the page table pages can be stored in kernel pool frames; so can the management information for the process frame pool4 . The management for the kernel frame pool is maintained inside the kernel frame pool itself (we took care of this in the implementation of the FramePool class). The question now is: Where to store the management information for the kernel frame pool? This works like a charm, because this portion of the memory is directly mapped. So nothing bad happens when you turn on paging. Other Implementation Issues A few hints that may come in handy for your implementation: • You enable paging, load the page table, and have access to the faulting address by reading and writing to the registers CR0, CR2, and CR3. The functions to do this are given in file paging low.asm and defined in file paging low.H for inclusion in the rest of your C/C++ programs. • The page table can be represented as an array of page table entries. Each entry has the following structure: 31 · · · 12 11 · · · 9 8 · · · 7 6 5 4 · · · 3 2 1 0 Page frame Avail Reserved D A Reserved U/S R/W Present where 2GDT: Global Descriptor Table, the x86 data structure defining characteristics of various memory areas. 3 IDT: Interrupt Descriptor Table, the x86 data structure that realizes the interrupt vector table. 4Don’t put it in the process frame pool. Once you turn on paging, you may not be able to find it anymore!   CPSC–410/611/613 Machine Problem 3 Page frame = number of physical frame storing this page Avail = feel free to use these bits Reserved = reserved by Intel; do not use! D = Dirty A = Accessed U/S = User or supervisor level R/W = Read or Read and Write Present = use bit • A page fault triggers Exception 14. This exception pushes a word with the exception error code onto the stack, which can be accessed (field err code) in the exception handler through the register context argument of type REGS. The lower 3 bits of the word are interpreted as follows: value bit 2 bit 1 bit 0 0 kernel read page not present 1 user write protection fault Also, note that the 32-bit address of the address that caused the page fault is stored in register CR2, and can be read using the function read cr2(). The Assignment 1. Study the lesson “Paging on the x86”. You can find additional material in Read K.J.’s tutorial on “Implementing Basic Paging” (http://www.osdever.net/tutorials/view/implementing-basic-paging) to understand how to set up basic paging. Also, the beginning of Tim Robinson’s tutorial “Memory Management 1” (http://www.osdever.net/tutorials/view/memory-management-1) helps you understand some of the intricacies of setting up a memory manager. 2. Implement the functionality defined in file page table.H (and described above) to initialize and load the page table, and to enable paging. Additional details about how to implement these routines can be found in K.J.’s tutorial. 3. Hint: Test the routines with a page table for 4MB of memory and 4MB of the memory being direct-mapped. Because all the memory is direct-mapped, it should all be valid (“present”), and there is no need to bother with a page-fault handler. Make sure that you can address memory inside the 4MB boundary. If – after setting up your page table – the program crashes when you turn on paging, then something is wrong with your code to set up the page table. 4. Once you have convinced yourself that the page table is implemented correctly to handle the direct-mapped memory portion, extend the code to handle more than the 4MB shared memory. For this, you need to add the following: (a) The memory beyond the first 4MB will not be direct-mapped, and therefore must be marked as invalid (“not present”).   CPSC–410/611/613 Machine Problem 3 (b) A page-fault hander must be implemented and installed, which is called whenever an invalid page is referenced. It locates a frame in the frame pool, maps the page to it, marks the page as “present”, and returns from the exception. (c) Keep in mind that we have a two-level page table. A page fault can therefore be caused by an invalid entry in the page directory as well as an invalid entry in a page table page. You need to handle both cases correctly for the page fault handler to work. You should have access to a set of source files, BOCHS environment files, and a makefile that should make your implementation easier. In particular, the kernel.C file will contain documentation that describes where to add code an how to proceed about testing the code as you progress through the machine problem. What to Hand In You are to hand in the following items: • A ZIP file, with name mp3.zip, containing the following files: 1. A design document, called design.pdf (in PDF format) that describes your implementation of the page table and the page-fault handler. 2. All the source files and the makefile needed to compile the code. 3. The assignment should not require modifications to files other than cont frame pool.H/C and page table.H/C. If you find yourself modifying and/or adding other files, add them to the mp3.zip file as well. You may have to modify and submit the makefile also. Describe what you modified and why you are modifying and/or adding these additional files in your design document! • Any modification to the provided .H files must be well motivated and documented. Do not modify the public interface provided by the .H files. We are using our own test code to check the correctness of your implementations, and we have to ensure that your code is compatible with our tests. • Grading of these MPs is a very tedious chore. These handin instructions are meant to mitigate the difficulty of grading, and to ensure that the grader does not overlook any of your efforts. • Failure to follow the handin instructions will result in lost points.