Project 3: Virtual Memory
*************************

By now you should be familiar with the inner workings of Pintos. You've already come a long way: your OS can properly handle multiple threads of execution with proper synchronization, and can load multiple user programs at once.  However, when loading user programs, your OS is limited by how much main memory the simulated machine has. In this assignment, you will remove that limitation.

You will be using the vm directory for this project.  The vm directory contains only the Makefiles.  The only change from userprog is that this new Makefile turns on the setting -DVM.  All code you write will either be newly generated files (e.g. if you choose to implement your paging code in their own source files), or will be modifications to pre-existing code (e.g. you will change the behavior of process.c significantly).

There are only a couple of source files you will probably be encountering for the first time:

devices/disk.h
devices/disk.c
     Provides access to the physical disk, abstracting away the rather awful IDE interface.

You will be building this assignment on the last one.  It will benefit you to get your project 2 in good working order before this assignment so those bugs don't keep haunting you.

All the test programs from the previous project should also work with this project.  You should also write programs to test the new features introduced in this project.

You will continue to handle Pintos disks and file systems the same way you did in the previous assignment (see Using the File System).

Your submission should define THREAD_JOIN_IMPLEMENTED in constants.h (see Conditional Compilation).

A Word about Design
===================

It is important for you to note that in addition to getting virtual memory working, this assignment is also meant to be an open-ended design problem.  We will expect you to come up with a design that makes sense.  You will have the freedom to choose how to handle page faults, how to organize the swap disk, how to implement paging, etc. In each case, we will expect you to provide a defensible justification in your design documentation as to why your choices are reasonable. You should evaluate your design on all the available criteria: speed of handling a page fault, space overhead in memory, minimizing the number of page faults, simplicity, etc.

In keeping with this, you will find that we are going to say as little as possible about how to do things.  Instead we will focus on what end functionality we require your OS to support.

Page Faults
===========

For the last assignment, whenever a context switch occurred, the new process would install its own page table into the machine.  The page table contained all the virtual-to-physical translations for the process.  Whenever the processor needed to look up a translation, it consulted the page table.  As long as the process only accessed memory that it owned, all was well.  If the process accessed memory it didn't own, it ``page faulted'' and page_fault terminated the process.

When we implement virtual memory, the rules have to change.  A page fault is no longer necessarily an error, since it might only indicate that the page must be brought in from a disk file or from swap.  You will have to implement a more sophisticated page fault handler to handle these cases.

On the 80X86, the page table format is fixed by hardware.  We have provided code for managing page tables for you to use in userprog/pagedir.c.  The functions in there should provide an abstract interface to all the page table functionality that you need to complete the project.  However, you may still find it worthwhile to understand a little about the hardware page table format, so we'll go into a little of detail about that in this section.

The top-level paging data structure is a 4 kB page called the ``page directory'' (PD) arranged as an array of 1,024 32-bit page directory entries (PDEs), each of which represents 4 MB of virtual memory.  Each PDE may point to the physical address of another 4 kB page called a ``page table'' (PT) arranged in the same fashion as an array of 1,024 32-bit page table entries (PTEs), each of which translates a single 4 kB virtual page into physical memory.

Thus, translation of a virtual address into a physical address follows the three-step process illustrated in the diagram below: (Actually, virtual to physical translation on the 80X86 architecture happens via an intermediate ``linear address,'' but Pintos (and most other 80X86 OSes) set up the CPU so that linear and virtual addresses are one and the same, so that you can effectively ignore this CPU feature.)

 1. The top 10 bits of the virtual address (bits 22:32) are used to index into the page directory.  If the PDE is marked ``present,'' the physical address of a page table is read from the PDE thus obtained. If the PDE is marked ``not present'' then a page fault occurs.

 2. The next 10 bits of the virtual address (bits 12:22) are used to index into the page table.  If the PTE is marked ``present,'' the physical address of a data page is read from the PTE thus obtained.  If the PTE is marked ``not present'' then a page fault occurs.

 3. The bottom 12 bits of the virtual address (bits 0:12) are added to the data page's physical base address, producing the final physical address.

     32                    22                     12                      0
     +--------------------------------------------------------------------+
     | Page Directory Index |   Page Table Index   |    Page Offset       |
     +--------------------------------------------------------------------+
                  |                    |                     |
          _______/             _______/                _____/
         /                    /                       /
        /    Page Directory  /      Page Table       /    Data Page
       /     .____________. /     .____________.    /   .____________.
       |1,023|____________| |1,023|____________|    |   |____________|
       |1,022|____________| |1,022|____________|    |   |____________|
       |1,021|____________| |1,021|____________|    \__\|____________|
       |1,020|____________| |1,020|____________|       /|____________|
       |     |            | |     |            |        |            |
       |     |            | \____\|            |_       |            |
       |     |      .     |      /|      .     | \      |      .     |
       \____\|      .     |_      |      .     |  |     |      .     |
            /|      .     | \     |      .     |  |     |      .     |
             |      .     |  |    |      .     |  |     |      .     |
             |            |  |    |            |  |     |            |
             |____________|  |    |____________|  |     |____________|
            4|____________|  |   4|____________|  |     |____________|
            3|____________|  |   3|____________|  |     |____________|
            2|____________|  |   2|____________|  |     |____________|
            1|____________|  |   1|____________|  |     |____________|
            0|____________|  \__\0|____________|  \____\|____________|
                                /                      /

Header threads/mmu.h has useful functions for various operations on virtual addresses.  You should look over the header yourself, but its most important functions include these:

pd_no(VA)
     Returns the page directory index in virtual address VA.

pt_no(VA)
     Returns the page table index in virtual address VA.

pg_ofs(VA)
     Returns the page offset in virtual address VA.

pg_round_down(VA)
     Returns VA rounded down to the nearest page boundary, that is, VA but with its page offset set to 0.

pg_round_up(VA)
     Returns VA rounded up to the nearest page boundary.

Disk as Backing Store
=====================

In VM systems, since memory is less plentiful than disk, you will effectively use memory as a cache for disk.  Looking at it from another angle, you will use disk as a backing store for memory.  This provides the abstraction of an (almost) unlimited virtual memory size. Part of your task in this project is to do this, with the additional constraint that your performance should be close to that provided by physical memory.  You will use the page tables' ``dirty'' bits to denote whether pages need to be written back to disk when they're evicted from main memory and the ``accessed'' bit for page replacement algorithms.  Whenever the hardware writes memory, it sets the dirty bit, and if it reads or writes to the page, it sets the accessed bit.

As with any caching system, performance depends on the policy used to decide which things are kept in memory and which are only stored on disk.  On a page fault, the kernel must decide which page to replace. Ideally, it will throw out a page that will not be referenced for a long time, keeping in memory those pages that are soon to be referenced.  Another consideration is that if the replaced page has been modified, the page must be first saved to disk before the needed page can be brought in.  Many virtual memory systems avoid this extra overhead by writing modified pages to disk in advance, so that later page faults can be completed more quickly (but you do not have to implement this optimization).

Memory Mapped Files
===================

The traditional way to access the file system is via read and write system calls, but that requires an extra level of copying between the kernel and the user level.  A secondary interface is simply to ``map'' the file into the virtual address space.  The program can then use load and store instructions directly on the file data.  (An alternative way of viewing the file system is as ``durable memory.''  Files just store data structures.  If you access data structures in memory using load and store instructions, why not access data structures in files the same way?)

Memory mapped files are typically implemented using system calls.  One system call maps the file to a particular part of the address space. For example, one might conceptually map the file foo, which is 1000 bytes long, starting at address 5000.  Assuming that nothing else is already at virtual addresses 5000...6000, any memory accesses to these locations will access the corresponding bytes of foo.

A consequence of memory mapped files is that address spaces are sparsely populated with lots of segments, one for each memory mapped file (plus one each for code, data, and stack).  You will implement memory mapped files in problem 3-3.  You should design your solutions to problems 3-1 and 3-2 to anticipate this.

Stack
=====

In project 2, the stack was a single page at the top of the user virtual address space.  The stack's location does not change in this project, but your kernel should allocate additional pages to the stack on demand.  That is, if the stack grows past its current bottom, the system should allocate additional pages for the stack as necessary (unless those pages are unavailable because they are in use by another segment).

It is impossible to predict how large the stack will grow at compile time, so we must allocate pages as necessary.  You should only allocate additional pages if they ``appear'' to be stack accesses.  You must devise a heuristic that attempts to distinguish stack accesses from other accesses.  Document and explain the heuristic in your design documentation.

The first stack page need not be loaded lazily.  You can initialize it with the command line at load time, with no need to wait for it to be faulted in.  Even if you did wait, the very first instruction in the user program is likely to be one that faults in the page.

Stack facts:

  * The user program's current stack pointer is in the intr_frame's esp member.

  * Only buggy user programs write to memory within the stack but below the stack pointer.  This is because more advanced OSes may interrupt a process at any time to deliver a ``signal'' and this uses the stack.

  * The 80X86 push instruction may cause a page fault 4 bytes below the stack pointer, because it checks access permissions before it adjusts the stack pointer.  (Otherwise, the instruction would not be restartable in a straightforward fashion.)

  * Similarly, the 80X86 pusha instruction, which pushes all 32 bytes of the 8 general-purpose registers at once, may cause a page fault 32 bytes below the stack pointer.

  * Most OSes impose some sort of limit on the stack size.  Sometimes it is user-adjustable.

Problem 3-1: Page Table Management
==================================

Implement page directory and page table management to support virtual memory.  You will need data structures to accomplish the following tasks:

  * Some way of translating in software from virtual page frames to physical page frames.  Consider using a hash table (see Hash Table).

     It is possible to do this translation without adding a new data structure, by modifying the code in userprog/pagedir.c.  However, if you do that you'll need to carefully study and understand section 3.7 in IA32-v3, and in practice it is probably easier to add a new data structure.

  * Some way of finding a page on disk if it is not in memory.  You won't need this data structure until problem 3-2, but planning ahead is a good idea.

     You can generalize the virtual-to-physical page table, so that it allows you to locate a page wherever it is in physical memory or on disk, or you can make this a separate table.

  * Some way of translating from physical page frames back to virtual page frames, so that when you evict a physical page from its frame, you can invalidate its translation(s).

The page fault handler, page_fault in threads/exception.c, needs to do roughly the following:

 1. Locate the page backing the virtual address that faulted.  It might be in the file system, in swap, or it might be an invalid virtual address. If you implement sharing, it might even already be in physical memory and just not set up in the page table,

     If the virtual address is invalid, that is, if there's nothing assigned to go there, or if the virtual address is above PHYS_BASE, meaning that it belongs to the kernel instead of the user, then the process's memory access must be disallowed.  You should terminate the process at this point, being sure to free all of its resources.

 2. If the page is not in physical memory, fetch it by appropriate means. If necessary to make room, first evict some other page from memory. (When you do that you need to first remove references to the page from any page table that refers to it.)

 3. Point the page table entry for the faulting virtual address to the physical page.  You can use the functions in userprog/pagedir.c.

You'll need to modify the ELF loader in userprog/process.c to do page table management according to your new design.  As supplied, it reads all the process's pages from disk and initializes the page tables for them at the same time.  For testing purposes, you'll probably want to leave the code that reads the pages from disk, but use your new page table management code to construct the page tables only as page faults occur for them.

You should use the palloc_get_page function to get the page frames that you use for storing user virtual pages.  Be sure to pass the PAL_USER flag to this function when you do so, because that allocates pages from a ``user pool'' separate from the ``kernel pool'' that other calls to palloc_get_page make.

There are many possible ways to implement virtual memory.  The above is simply an outline of our suggested implementation.

Problem 3-2: Paging To and From Disk
====================================

Implement paging to and from files and the swap disk.  You may use the disk on interface hd1:1 as the swap disk, using the disk interface prototyped in devices/disk.h.  From the vm/build directory, use the command pintos make-disk swap.dsk N to create an N MB swap disk named swap.dsk.  Afterward, swap.dsk will automatically be attached when you run pintos.

You will need routines to move a page from memory to disk and from disk to memory, where ``disk'' is either a file or the swap disk.  If you do everything correctly, your VM should still work when you implement your own file system for the next assignment.

You will need a way to track pages which are used by a process but which are not in physical memory, to fully handle page faults.  Pages that you write to swap should not be constrained to be in sequential order.  You will also need a way to track all of the physical memory pages, to find an unused one when needed, or to evict a page when memory is needed but no empty pages are available.  The data structures that you designed for problem 3-1 should do most of the work for you.

You will need a page replacement algorithm.  The hardware sets the accessed and dirty bits when it accesses memory.  You can gain access to this information using the functions prototyped in userprog/pagedir.h.  You should be able to take advantage of this information to implement some algorithm which attempts to achieve LRU-type behavior.  We expect that your algorithm perform at least as well as a reasonable implementation of the second-chance (clock) algorithm.  You will need to show in your test cases the value of your page replacement algorithm by demonstrating for some workload that it pages less frequently using your algorithm than using some inferior page replacement policy.  The canonical example of a poor page replacement policy is random replacement.

You must write your code so that we can choose a page replacement policy at compile time.  By default, the LRU-like algorithm must be in effect, but we must be able to choose random replacement by inserting the line #define RANDOM_REPLACEMENT 1 in constants.h. See Conditional Compilation, for details.

Since you will already be paging from disk, you should implement a ``lazy'' loading scheme for new processes.  When a process is created, it will not run immediately.  Therefore, it doesn't make sense to load all its code, data, and stack into memory when the process is created, since it might incur additional disk accesses to do so (if it gets paged out before it runs).  When loading a new process, you should leave most pages on disk, and bring them in as demanded when the program begins running.  Your VM system should also use the executable file itself as backing store for read-only segments, since these segments won't change.

There are a few special cases.  Look at the loop in load_segment in userprog/process.c.  Each time around the loop, read_bytes represents the number of bytes to read from the executable file and zero_bytes represents the number of bytes to initialize to zero following the bytes read.  The two always sum to PGSIZE.  The page handling depends on these variables' values:

  * If read_bytes equals PGSIZE, the page should be demand paged from disk on its first access.

  * If zero_bytes equals PGSIZE, the page does not need to be read from disk at all because it is all zeroes.  You should handle such pages by creating a new page consisting of all zeroes at the first page fault.

  * If neither read_bytes nor zero_bytes equals PGSIZE, then part of the page is to be read from disk and the remainder zeroed.  This is a special case.  You are allowed to handle it by reading the partial page from disk at executable load time and zeroing the rest of the page.  This is the only case in which we will allow you to load a page in a non-``lazy'' fashion.  Many real OSes such as Linux do not load partial pages lazily.

Incidentally, if you have trouble handling the third case above, you can eliminate it temporarily by linking the test programs with a special ``linker script.''  Read tests/userprog/Makefile for details.  We will not test your submission with this special linker script, so the code you turn in must properly handle all cases.

For extra credit, you may implement sharing: when multiple processes are created that use the same executable file, share read-only pages among those processes instead of creating separate copies of read-only segments for each process.  If you carefully designed your data structures in problem 3-1, sharing of read-only pages should not make this part significantly harder.

Problem 3-3: Memory Mapped Files
================================

Implement memory mapped files.

You will need to implement the following system calls:

SYS_mmap
bool mmap (int FD, void *ADDR, unsigned LENGTH)

     Maps the file open as FD into the process's address space starting at ADDR for LENGTH bytes.  Returns true if successful, false on failure.  Failure cases include the following:

       * ADDR is not page-aligned.

       * LENGTH is not positive.

       * The range of pages mapped overlaps any existing set of mapped pages, including the stack or pages mapped at executable load time.

     LENGTH is treated as if it were rounded up to the nearest multiple of the page size, that is, as if the first statement in the system call's implementation were

          length = ROUND_UP (length, PGSIZE);

     (The ROUND_UP macro is defined in <round.h>.) The remainder of this description assumes that this has been done.

     If LENGTH is less than FD's length, you should only map the first LENGTH bytes of the file.  If LENGTH is greater than FD's length, when the file's length is also rounded up to a page multiple, the call should fail.  Ideally it would extend the file, but our file system does not yet support growing files.

     If LENGTH is greater than FD's (unrounded) length, then some bytes in the final mapped page ``stick out'' beyond the end of the file.  Set these bytes to zero when the page is faulted in from disk, and discard them when the page is written back to disk.

     Your VM system should use the mmap'd file itself as backing store for the mapped segment.  That is, to evict a page mapped by mmap must be evicted, write it to the file it was mapped from. (In fact, you may choose to implement executable mappings as a special case of file mappings.)

SYS_munmap
bool munmap (void *addr, unsigned length)

     Unmaps LENGTH bytes starting at ADDR.  Returns true on success, false on failure.  Failure cases include the following:

       * ADDR is not page-aligned.

       * LENGTH is not positive.

       * One or more pages within the range to be unmapped were not mapped using the mmap system call.

     As with mmap, LENGTH is treated as if it were rounded up to the nearest multiple of the page size.

     It is valid to unmap only some of the pages that were mapped in a previous system call.

All mappings are implicitly unmapped when a process exits, whether via exit or by any other means.  When a file is unmapped, whether implicitly or explicitly, all outstanding changes are written to the file, and the pages are removed from the process's list of used virtual pages.

FAQ
===

 1. Do we need a working HW 2 to implement HW 3?

     Yes.

 2. How do I use the hash table provided in lib/kernel/hash.c?

     First, you need to embed a hash_elem object as a member of the object that the hash table will contain.  Each hash_elem allows the object to a member of at most one hash table at a given time.  All the hash table functions that deal with hash table items actually use the address of a hash_elem.  You can convert a pointer to a hash_elem member into a pointer to the structure in which member is embedded using the hash_entry macro.

     Second, you need to decide on a key type.  The key should be something that is unique for each object, because a given hash table may not contain two objects with equal keys.  Then you need to write two functions.  The first is a hash function that converts a key into an integer.  Some sample hash functions that you can use or just examine are given in lib/kernel/hash.c.  The second function needed is a comparison function that compares a pair and returns true if the first is less than the second.  These two functions have to be compatible with the prototypes for hash_hash_func and hash_less_func in lib/kernel/hash.h.

     Here's a quick example.  Suppose you want to put threads in a hash table.  First, add a hash_elem to the thread structure by adding a line to its definition:

          hash_elem h_elem;               /* Hash table element. */

     We'll choose the tid member in thread as the key, and write a hash function and a comparison function:

          /* Returns a hash for E. */
          unsigned
          thread_hash (const hash_elem *e, void *aux UNUSED)
          {
            struct thread *t = hash_entry (e, struct thread, h_elem);
            return hash_int (t->tid);
          }

          /* Returns true if A's tid is less than B's tid. */
          bool
          thread_less (const hash_elem *a_, const hash_elem *b_,
                       void *aux UNUSED)
          {
            struct thread *a = hash_entry (a_, struct thread, h_elem);
            struct thread *b = hash_entry (b_, struct thread, h_elem);
            return a->tid < b->tid;
          }

     Then we can create a hash table like this:

          struct hash threads;

          hash_init (&threads, thread_hash, thread_less, NULL);

     Finally, if T is a pointer to a thread, then we can insert it into the hash table with:

          hash_insert (&threads, &T->h_elem);

     If you have any other questions about hash tables, the CS109 and CS161 textbooks have good chapters on them, or you can come to any of the TA's office hours for further clarification.

 3. What are the AUX parameters to the hash table functions good for?

     In simple cases you won't have any need for the AUX parameters. In these cases you can just pass a null pointer to hash_init for AUX and ignore the values passed to the hash function and comparison functions.  (You'll get a compiler warning if you don't use the AUX parameter, but you can turn that off with the UNUSED macro, as shown above, or you can just ignore it.)

     AUX is useful when you have some property of the data in the hash table that's both constant and needed for hashing or comparisons, but which is not stored in the data items themselves.  For example, if the items in a hash table contain fixed-length strings, but the items themselves don't indicate what that fixed length is, you could pass the length as an AUX parameter.

 4. The current implementation of the hash table does not do something that we need it to do. What gives?

     You are welcome to modify it.  It is not used by any of the code we provided, so modifying it won't affect any code but yours.  Do whatever it takes to make it work the way you want.

 5. What controls the layout of user programs?

     The linker is responsible for the layout of a user program in memory. The linker is directed by a ``linker script'' which tells it the names and locations of the various program segments.  You can learn more about linker scripts by reading the ``Scripts'' chapter in the linker manual, accessible via info ld.

Problem 3-1 and 3-2 FAQ
-----------------------

 1. Does the virtual memory system need to support growth of the data segment?

     No.  The size of the data segment is determined by the linker.  We still have no dynamic allocation in Pintos (although it is possible to ``fake'' it at the user level by using memory-mapped files).  However, implementing it would add little additional complexity to a well-designed system.

 2. Why do I need to pass PAL_USER to palloc_get_page when I allocate physical page frames?

     You can layer some other allocator on top of palloc_get_page if you like, but it should be the underlying mechanism, directly or indirectly, for two reasons.  First, running out of pages in the user pool just causes user programs to page, but running out of pages in the kernel pool will cause all kinds of problems, because many kernel functions depend on being able to allocate memory.  Second, you can use the -ul option to pintos to limit the size of the user pool, which makes it easy to test your VM implementation with various user memory sizes.

Problem 3-3: Memory Mapped File FAQ
-----------------------------------

 1. How do we interact with memory-mapped files?

     Let's say you want to map a file called foo into your address space at address 0x10000000. You open the file, determine its length, and then use mmap:

          #include <stdio.h>
          #include <syscall.h>

          int main (void)
          {
              void *addr = (void *) 0x10000000;
              int fd = open ("foo");
              int length = filesize (fd);
              if (mmap (fd, addr, length))
                  printf ("success!\n");
          }

     Suppose foo is a text file and you want to print the first 64 bytes on the screen (assuming, of course, that the length of the file is at least 64).  Without mmap, you'd need to allocate a buffer, use read to get the data from the file into the buffer, and finally use write to put the buffer out to the display. But with the file mapped into your address space, you can directly address it like so:

          write (addr, 64, STDOUT_FILENO);

     Similarly, if you wanted to replace the first byte of the file, all you need to do is:

          addr[0] = 'b';

     When you're done using the memory-mapped file, you simply unmap it:

          munmap (addr, length);

 2. What if two processes memory-map the same file?

     There is no requirement in Pintos that the two processes see consistent data.  Unix handles this by making the processes share the same physical page, but the mmap system call also has an argument allowing the client to specify whether the page is shared or private (i.e. copy-on-write).

 3. What happens if a user removes a mmap'd file?

     You should follow the Unix convention and the mapping should still be valid.  See Removing an Open File, for more information.

 4. What if a process writes to a page that is memory-mapped, but the location written to in the memory-mapped page is past the end of the memory-mapped file?

     Can't happen.  mmap checks that the mapped region is within the file's length and Pintos provides no way to shorten a file.  (Until project 4, there's no way to extend a file either.)  You can remove a file, but the mapping remains valid (see the previous question).

 5. Do we have to handle memory mapping stdin or stdout?

     No.  Memory mapping implies that a file has a length and that a user can seek to any location in the file.  Since the console device has neither of these properties, mmap should return false when the user attempts to memory map a file descriptor for the console device.

 6. What happens when a process exits with mapped files?

     When a process finishes, each of its mapped files is implicitly unmapped.  When a process mmaps a file and then writes into the area for the file it is making the assumption the changes will be written to the file.

 7. If a user closes a mapped file, should it be automatically unmapped?

     No, once created the mapping is valid until munmap is called or the process exits.