CS 39 -- Assignment 2

Supporting virtual memory

There is a new version of the virtual machine (hereafter the CPU) that now sports a memory management unit (MMU). As a result, some things have disappeared from the CPU: specifically, the base and limit registers that controlled memory access.

Along with their disappearence comes the need, in the kernel, to add offsets (such as getMemoryBegin()) in order to access the contents within the virtual machine's main memory. Thus, all access to that main memory will be via the MMU.

This MMU will perform mapping from virtual addresses to physical addresses (which are within the virtual machine's main memory). The MMU, at any given moment, will only be able to translate virtual to physical addresses for a small set of pages. These few mappings will be TLB Mapping Information Entries (MIEs) held in the Translation Lookaside Buffer (TLB).

The CPU itself (particularly the LOAD and STOR instructions) have been modified to work through the MMU. One other addition to the CPU has been a current process ID register. The integer identifier for the current process must be loaded into this register, as the MMU uses that identifier to distinguish between pages belonging to different processes that may have the same virtual address.

So, your goal in this assignment will be to provide virtual memory for processes running on the virtual platform. The details are described below, but first, a note: You will not be implementing a full virtual memory system! There are simplifications to the virtual memory support that we want for this assignment, so be sure to read the requirements carefully, and ask questions if the requirements aren't clear!

The MMU interface

We describe here how the kernel can interact with the new CPU/MMU features. We will break the interaction into two categories: Submitting MMU requests, and Handling MMU-generated traps.

Submitting MMU requests

The MMU allows the kernel (or the CPU) to read from or write to a specific location in the virtual memory space of the current process. (It is important to note that the MMU uses the current process ID when mapping pages.) Below are descriptions of the four functions that allow this access, plus one function needed for TLB management:

• boolean readWord (virtualAddress, hardwareAddress)

  This function allows the caller to specify, via virtualAddress, the location of a word within the address space of the current process. The MMU will perform the translation from virtual to physical address, and then copy the requested machine word into the location specified by hardwareAddress. In our virtual platform, the hardware address is usually a register, but it can be any location that the kernel wants to use. Note that the virtual address provided must be word-aligned. The function returns whether or not it was able successfully to perform the translation and read the word.

• boolean writeWord (virtualAddress, hardwareAddress)

  This function allows the caller to specify, via virtualAddress, the location of a word within the address space of the current process. The MMU will perform the translation from virtual to physical address, and then copy the machine word contained at location specified by hardwareAddress into the location specified by the mapped physical address. Again, the virtual address provided must be word-aligned. The function returns whether or not it was able successfully to perform the translation and write the word.

• boolean readByte (virtualAddress, hardwareAddress)

  This function allows the caller to specify, via virtualAddress, the location of a byte within the address space of the current process. The MMU will perform the translation from virtual to physical address, and then copy the requested byte into the location specified by hardwareAddress. The function returns whether or not it was able successfully to perform the translation and read the byte.

• boolean writeByte (virtualAddress, hardwareAddress)

  This function allows the caller to specify, via virtualAddress, the location of a byte within the address space of the current process. The MMU will perform the translation from virtual to physical address, and then copy the bytecontained at location specified by hardwareAddress into the location specified by the mapped physical address. The function returns whether or not it was able successfully to perform the translation and write the byte.

• void flushTLB ()

  Thus function repeatedly calls the TLB miss handler, once for each entry, each time requesting a mapping for a page that does not exist. Thus, each entry of the TLB will be flushed out, and the TLB will be left holding only invalid entries. Note that the invalid page for which a mapping is request is simply the 0^th page for the process whose ID is 0. It thus relies on the process ID of 0 not being valid, and so your process manager should never used that ID.

Handling MMU-generated traps

When the four functions above attempt to translate the given virtual address to a physical address, that mapping can fail in a number of ways. When the failure occurs, the MMU/CPU trap into the kernel for assistance. There are two kinds of traps that your kernel must support:

• TLB miss trap

  Normally, a TLB miss is handled either by the hardware itself, or by a small sequence of provided code loaded into the MMU. However, for simplicity, we will treat this kind of miss like any other trap.

  When the MMU attempts to perform a mapping, it looks into the TLB to see if the mapping information is available. If it is not in the TLB, then the MMU must evict one the currently resident TLB entries (if the TLB is full), and then trap into the kernel, which should provide the MMU with a new TLB entry that will fulfill the needed mapping. It is important to note that the TLB miss handler gets only one chance to provide the correct mapping information. If that information is wrong, the virtual platform will behave unpredictably.

  Before the trap into the kernel occurs, the MMU places four pieces of information into trap registers. Specifically:

  • The requested virtual address is placed in trap register 0.
  • The process ID of the evicted TLB entry is placed in trap register 1.
  • The virtual page address associated with the evicted MIE (specifically, the address of the first word of that page) is placed in trap register 2.
  • The MIE itself is placed in trap register 3.

  Each MIE contains a number of pieces of information. Specifically, each MIE is a single machine word that has the following format:

  • Bits 31 to 9 are the physical page number.
  • Bit 8 is the referenced bit.
  • Bit 7 is the modified bit.
  • Bit 6 is the read permission bit.
  • Bit 5 is the write permission bit.
  • Bit 4 is the resident bit.
  • Bits 3 to 0 are unused.

  The first thing that the TLB miss handler must do is to take this evicted MIE and update the kernel's page tables accordingly. For example, if the modified bit was set while the MIE resided in the TLB, then the corresponding Page Table Entry (PTE) should reflect the dirty status of that page.

  The next thing that the TLB miss handler must do is to find the information for the page corresponding to the virtual address. Specifically, the handler should replace the value in trap register 3 with a new MIE -- one in the same format as shown above, dthat contains all of the correct information for the requested virtual page as derive from the requested virtual page's PTE.

  If there is no PTE in the kernel's page tables for the requested virtual address (that is, the requested address is invalid), then a bogus MIE entry should be provided in trap register 3; specifically, an entry with the resident bit turned off should be used. When the MMU tries to use this new entry, and discovers that the page isn't resident, the MMU will trap into the kernel again (see below). The TLB should not try to do anything else with an invalid virtual address -- it should only provide this bogus MIE with the resident bit turned off.

  When the trap handler completes, control is returned to the MMU. It will insert the new MIE provided by the TLB miss hanlder into the TLB, and then attempt to do the mapping.

• The invalid memory access trap

  Once the MMU has obtained, from the TLB, a MIE corresponding do the desired virtual memory page, it will use that MIE to translate the virtual address to a physical one. However, before it attempts to use the physical address it has constructed to access the requested location, it must ensure that it has constructed a valid physical address.

  The MMU will check the validity of the mapping, and it may find one of the following conditions holds:

  • The physical address specified is outside of the virtual machine's address space.
  • The MIE indicates that the page is not actually resident.
  • The MIE indicates that permission to perform the requested read or write operation on this page has not been granted.

  If any one of these (or perhaps others) is true, the MMU is going to issue an invalid memory access trap. Before it does, it will place the following data in the trap registers:

  • The requested virtual address is placed in trap register 0.
  • The MIE for the requested virtual page is placed in trap register 1.
  • The operation that caused the invalid access is placed in trap register 2; the value 0x0 is placed in that register if a read operation was being performed, and the value 0x1 is placed in that register if a write operation was being performed.

  The kernel's trap handler will then be given control. It must determine why the MMU could not proceed, based on the possible problems listed above. The problem may be one that is "legitimate"; for example, the requested virtual page have been evicted to the backing store, and needs to be reloaded. The handler can perform that page swapping, update the MIE held in trap register 1 to indicate that the page is now resident, and return control to the MMU. When the MMU regains control, it will take the MIE found in trap register 1 as a modified entry for the TLB.

  The problem that caused the trap may not be "legitimate". For example, a process that attempts to access a page that for which no mapping exists, and for which the kernel has not created a mapping. Rather than update the MIE, the process should be killed, another scheduled (if available), and control returned to the MMU.

  Important note on returning control to the MMU: After this trap handler is used, the MMU does not immediately try again to perform the mapping and access the space. Rather, it returns a failure to perform the requested operation. If the memory access was caused by a LOAD or STOR operation, then the CPU will take the failure of the MMU as an indication not to advance the PC to the next instruction. Instead, the PC will continue point to that same LOAD or STOR instruction, and the CPU will try, from scratch, to process that instruction. If the trap handler has done its job (i.e. fetched the page from backing store), then the second attempt to process such an instruction will succeed without a trap into the kernel.

  If, however, the MMU fails on a request from the kernel itself, then the behavior is context specific. If the kernel expected that the request to the MMU might fail, then it can try the request again. If it is not appropriate for the MMU to fail on the kernel's request, then the kernel should probably panic -- that is, it should probably abort due to an unrecoverable error.

The format of the page table, stored and managed within the kernel, is completely up to you. Within these trap handlers, you can do whatever is needed to translate information between the MMU's format (specifically MIE's) and your own, internal, kernel format for PTE's.

Your assignment (specifically)

Login to your account on the CS UNIX systems. You should copy the following tarball into your group's project directory:

~sfkaplan/cs39/assignment-2-code.tar.gz

(If you don't recall how to decompress and un-archive the tarball, revisit the Getting Started page under the course's Projects page.)

Note that, unlike last time, the tarball does not include a kernel -- it's just the machine itself. You will have to adapt your kernel to the new and different capabilities of the CPU and MMU. There are also some new executables that load some data and manipulate it, thus stressing the correctness of your page swapping.

The following points should describe what you need to do:

1. Create a page table structure. This structure should allow you to look up any requested virtual page and find it's corresponding physical address (if any) and attributes (read/write permissions, modified/referenced bits, etc.)
2. Write functions/methods that allow for insertion, deletion, and modification of the page table. These may evolve as you see how other parts of your kernel will use them.
3. Write the TLB miss handler. It should be able to take evicted TLB entries and use them to update the page table as needed. It should also be able to provide an appropriate MIE to the MMU for a given virtual address.
4. Write the invalid memory access handler. It should be able to determine the cause of the trap, and then deal with it appropriately, either by killing an offending process, or by managing the pages so that the MMU can succeed the next time. This handler should include the capability for automatic page swapping to a backing store. Backing store space should be "fake" -- that is, your kernel should allocate a chunk of space that it can use as a backing store, outside of the virtual machine's main memory. Note that your PTEs must be able to indicate not only that a page isn't resident, but that it resides at a specific location in the backing store.
5. Change how space is allocated for a process. Before, you took a fixed slice of space from main memory, and allocated that to a given process. Instead, if the kernel needs to allocate space for a process, it should create a new page mapping in the address space of that process, and insert the mapping into its page table. Then, when the process or the kernel attempts to use that space, the MMU (along with the trap handlers) can successfully provide access to it.
6. Update the function for loading an executable image for a new process. In particular, ensure that it uses the allocation facilities created in the previous step, and that it loads the executable image into the virtual machine's main memory via the MMU functions.
7. Create a new system call, MMAP, which should have the constant 0x11111100. When a process issues this system call, the register specified by operand-1 will contain a virtual address. The kernel should create a new page table entry for the virtual page that contains the given virtual address. If such a page is already mapped, the system call should simply ignore the request.
8. Update the FORK system call -- specifically, update the part of that system call which makes an identical copy of the main memory space for the child process. Unlike before, this copying will require the mapping of new pages in the context of the new process, as well as the copying of the data itself from the parent's virtual pages to the child's virtual pages.

Remember, no changes to the virtual machine, including the MMU, should be needed. Bugs should be reported to me, as I may need to modify the virtual machine and issue an update to all of the groups.

Submitting your work

All of your work should be done in your project directory. More specifically, within your project directory, be sure to create a new subdirectory for this assignment -- Don't clobber your old work!

When your group has completed its project, it should gather all of the files that are part of the completed project, and place a copy of those files in a directory named assignment-2 within your group's project directory. I will go and find them there. Some groups forgot this step on the last assignment!