Assignment 3: Virtual Memory

Due Date: 8am (08:00), Monday 7th November (Stuvac)

Worth 30 marks (of the 100 available for the class mark component of the course)

The 10% bonus for one week early applies

The extra 5% bonus for a submitted, working assignment within 48 hours of release, also applies

See course intro for exact details. The notional release time is 8am, Saturday, 15th October

Up to a 20% bonus is available for the advanced part of the assignment

To attempt the advanced part, you must finish the standard assignment at least one week early, and get permission from Gabriele.

Any bonus awarded for the advanced part can be used to make up for lost marks in any class mark component of the course. The familiarisation questions contained herein are the subject of your week 12 tutorial. Please answer the questions and bring them to your tutorial.

Contents

Introduction

In this assignment you will implement the virtual memory sub-system of OS/161. The existing VM implementation in OS/161, dumbvm, is a minimal implementation with a number of shortcomings. In this assignment you will adapt OS/161 to take full advantage of the simulated hardware by implementing management of the MIPS software-managed Translation Lookaside Buffer (TLB). You will write the code to manage this TLB. You will also write code to manage system memory.

If you attempt the advanced portion of this assignment, you will implement paging, the mechanism by which memory pages of an active process can be sent to disk when memory is needed, and restored to memory when required by the program.

The System/161 TLB

In the System/161 machine, each TLB entry includes a 20-bit virtual page number and a 20-bit physical page number as well as the following five fields: All these bits/values are maintained by the operating system. When the valid bit is set, the TLB entry contains a valid translation. This implies that the virtual page is present in physical memory. A TLB miss occurs when no TLB entry can be found with a matching virtual page and address space ID (unless the global bit is set in which case the address space ID is ignored) and a valid bit that is set.

Note: for this assignment, we strongly recommend that you ignore the pid field. Note, however, that you must then flush the TLB on a context switch (why?).

The System/161 Virtual Address Space Map

The MIPS divides its address space into several regions that have hardwired properties. These are: Both direct-mapped segments map to the first 512 megabytes of the physical address space.

The top of kuseg is 0x80000000. The top of kseg0 is 0xa0000000, and the top of kseg1 is 0xc0000000.

The memory map thus looks like this:

Address Segment Special properties
0xffffffff kseg2  
0xc0000000  
0xbfffffff kseg1  
0xbfc00180 Exception address if BEV set.
0xbfc00100 UTLB exception address if BEV set.
0xbfc00000 Execution begins here after processor reset.
0xa0000000  
0x9fffffff kseg0  
0x80000080 Exception address if BEV not set.
0x80000000 UTLB exception address if BEV not set.
0x7fffffff kuseg  
0x00000000  

Setting Up Assignment 3

Remember to use a 3231 subshell (or continue using your modified PATH) for this assignment, as outlined in ASST0. In this section, you will (again) be setting up the cvs repository that will contain your code. Only one of you needs to do the following. We suggest your partner sit in on this part of the assignment. You have now completed setting up a shared repository for both partners. The following instructions are now for both partners. You will need to increase the amount of physical memory to run some of the provided tests. Update ~/cs3231/root/sys161.conf so that the ramsize is as follows 
31      busctl  ramsize=16777216
Or, download a fresh, appropriately configured, version from here, and install it.

Configure OS/161 for Assignment 3

Remember to set your PATH environment variable as in previous assignments (e.g. run the 3231 command).

Before proceeding further, configure your new sources, and build and install the user-level libraries and binaries. 

% cd ~/cs3231/asst3-src
% ./configure
% make

You have to reconfigure your kernel before you can use the framework provided to do this assignment. The procedure for configuring a kernel is the same as before, except you will use the ASST3 configuration file: 

% cd ~/cs3231/asst3-src/kern/conf	
% ./config ASST3
You should now see an ASST3 directory in the compile directory.

Building for ASST3

When you built OS/161 for ASST0, you ran make from compile/ASST0 . In ASST3, you run make from (you guessed it) compile/ASST3 . 
% cd ../compile/ASST3
% make depend
% make
% make install
If you now run the kernel as you did for previous assignments, you should get to the menu prompt. If you try and run a program, the kernel should panic with a message about vm_fault being unimplemented. For example, run p /bin/true at the OS/161 prompt to run the program /bin/true in ~/cs3231/root.

You are now ready to start the assignment.

Tutorial Exercises

Please answer the following questions and bring them to your tutorial in week 12. You should be familiar enough with navigating the kernel source that you can find the answers to the below questions by yourself (Hint: use the grep utility). You may also find the MIPS r3000 reference useful.

1. What is the difference between the different MIPS address space segments? What is the use of each segment?

2. What functions exist to help you manage the TLB? Describe their use. (Hint: look in kern/arch/mips/include/tlb.h)

3. What macros are used to convert from a physical address to a kernel virtual address?

4. What address should the initial user stack pointer be?

5. What are the entryhi and entrylo co-processor registers? Describe their contents.

6. What do the as_* functions do? Why do we need as_prepare_load() and as_complete_load()?

7. What does vm_fault do? When is it called?

8. Assuming an inverted page table (4k pages), show for the following virtual addresses (assume 16 frames):

  1. The page number and offset;
  2. the translated address (after any page allocation); and
  3. the contents of the page table after the TLB miss.
The page table is initially empty. You may assume that the allocator returns frames in order, so that the first frame allocated is frame 0, then frames 1, 2, 3, etc.

Coding Assignment

This assignment involves designing and implementing a number of data-structures. Before you start, you should work out what data you need to keep track of, and what operations are required.

Like previous assignments, you are required to submit a small design doc that identifies the major issues you tackled in this assignment, and also describes your solutions to these issues.

The document will be used to guide our markers in their evaluation of your solution to the assignment. In the case of a poor results in the functional testing combined with a poor design document, we will base our assessment on these components alone. If you can't describe your own solution clearly, you can't expect us to reverse engineer the code to a poor and complex solution to the assignment.

Create your design document to the top of the source tree to OS/161 (~/cs3231/asst3-src), and include it in cvs as follows. 

% cd ~/cs3231/asst3-src
% cvs add design.txt

When you later commit your changes into your repository, your design doc will be included in the commit, and later in your submission.

Also, please word wrap you design doc if your have not already done so. You can use the unix fmt command to achieve this if your editor cannot.

Memory Management

This assignment requires you to keep track of physical memory. The current memory management implementation in dumbvm never frees memory; your implementation should handle both allocation and freeing of frames.

In the basic assignment you will need to keep track of whether a frame is used or not - you don't need an extra data structure for this, as you can use the pointer of the collision chain to connect all the free frames in the IPT. In the advanced part, however, you will need to keep track of reference statistics and other information about the frames.

The functions that deal with memory are described in kern/include/vm.h. You may assume that only one page will be allocated at a time --- designing a page allocator that can allocate multiple pages at a time is surprisingly tricky. However, make sure that you never allocate memory (though kmalloc) that is larger than a page!

Note that alloc_kpages() should return the virtual address of the page, i.e., an address in kseg0.

Warning: alloc_kpages() can be called before vm_bootstrap(). The means that your implementation of alloc_kpages() must work before your frametable is initialised. You should just call ram_stealmem() if the frametable hasn't been initialised.

Address Space Management

OS/161 has an address space abstraction, the struct addrspace. To enable OS/161 to interact with your VM implementation, you will need to fill in the functions in kern/vm/addrspace.c, The semantics of these functions is documented in kern/include/addrspace.h.

You may use a fixed-size stack region (say 16 pages) for each process.

Address Translation

The main goal for this assignment is to provide virtual memory translation for user programs. To do this, you will need to implement a TLB refill handler. You will also need to implement a page table. For this assignment, you will implement an inverted page table (IPT).

Hashing functions for TLBs tend to be optimised for speed rather than uniform coverage, and are therefore very simple. An appropriate choice of the hash is the least significant bits of the page number value.

The following questions may assist you in designing the contents of your page table

Testing and Debugging Your Assignment

To test this assignment, you should run a process that requires more virtual memory than the TLB can map at any one time. You should also ensure that touching memory not in a valid region will raise an exception. The huge and faulter tests in testbin may be useful.

Apart from GDB, you may also find the trace161 command useful. trace161 will run the simulator with tracing, for example 

% trace161 -t t -f outfile kernel
will record all TLB accesses in outfile.

Hints

Have a close look at the dumbvm implementation, especially vm_fault(). Although it is simple, you should get an idea on how to approach the rest of the assignment.

We suggest you implement the assignment in the following order:

  1. Understand how a page table works, and its relationship with the TLB.
  2. Understand the specification and the supplied code.
  3. Work out a basic design for you implementation.
    Start simple: assume a small address space. This means you can use a straight-forward static array as the page table (without collision chain), and can keep you code and data structures simple.
  4. Implement the TLB exception handlers in vm.c using this simplified page table. Note, your final solution should use an inverted page table!
  5. Implement the functions in kern/vm/addrspace.c that are required for basic functionality (e.g. as_create(), as_prepare_load(), etc.). Allocating user pages in as_define_region() may also simplify your assignment.
  6. Test and debug this. Use the debugger!
    If you really get stuck, submit at least this much of the solution, and you should get some marks for it.
  7. Understand how the page table works.
  8. Decide exactly what data structures you need.
  9. Work out the design for the proper solution, using the IPT.
  10. Modify your implementation to include the IPT.
  11. Write routines in kern/vm/frametable.c to manage free frames and copy pages. Modify kern/arch/mips/mips/vm.c to create and delete page table entries, and keep the TLB consistent with the page table.
  12. Use these routines to finish the functions in kern/vm/addrspace.c.
  13. Test and debug.

Basic Assignment Submission

As with the previous assignments, you again will be submitting a diff of your changes to the original tree.

You should first commit your changes back to the repository using the following command. Note: You will have to supply a comment on your changes. You also need to coordinate with your partner that the changes you have (or potentially both have) made are committed consistently by you and your partner, such that the repository contains the work you want from both partners. 

% cd ~/cs3231/asst3-src
% cvs commit
If the above fails, you may need to run cvs update to bring your source tree up to date with commits made by your partner. If you do this, you should double check and test your assignment prior to submission.

Now tag the repository so that you can always retrieve your current version in the future. 

% cd ~/cs3231/asst3-src
% cvs tag asst3-finish

Now generate a file containing the diff. 

% cvs -q rdiff -r asst3-base -r asst3-finish -u asst3-src > ~/asst3.diff

Testing Your Submission

Look here for information on testing and resubmitting your assignment.

Submitting Your Assignment

Now submit the diff as your assignment. 
% cd ~
% give cs3231 asst3 asst3.diff
You're now done.

Note: If for some reason you need to change and re-submit your assignment after you have tagged it asst3-final, you will need to either delete the asst3-final tag, commit the new changes, re-tag, and re-diff your assignment, or choose a different final tag name and commit the new changes, tag with the new tag, and re-diff with the new tag. To delete a cvs tag, use 

% cvs rtag -d asst3-final asst3-src

Even though the generated diff output should represent all the changes you have made to the supplied code, occasionally students do something "ingenious" and generate non representative diff output.

We strongly suggest keeping a your cvs repository intact to allow for recovery of your work if need be.

Advanced Assignment

Students who wish to attempt the advanced part of this assignment may gain up to an extra 6 marks (20%) for one (or multiple) of the following:

Advanced Assignment Submission

Submission for the advanced assignment is similar to the basic assignment, except the advance component is given to a distinguished assignment name: asst3_adv

Basically, at the end of the assignment you will need to generate a rdiff between your final version and asst3-base. It is up to you how you get there. Two obvious options are: continue developing along your mainline branch, or create a new branch from where you finished the basic part of asst3. Warning: don't submit a cvs diff! Only submit a cvs rdiff as cvs diff generates broken patches.

An example branch 

% cvs rtag -r asst3-finished  -b asst3-adv asst3-src
You can now checkout the asst3-adv branch to work on. 
% cd ~/cs3231
% rm -rf asst3-src
% cvs checkout -r asst3-adv asst3-src
When you need to generate a diff based on the original source tree, 
% cd ~/cs3231/asst3-src
% cvs commit

Now tag the repository so that you can always retrieve your current version in the future. 

% cd ~/cs3231/asst3-src
% cvs tag asst3-adv-finish

Now generate a file containing the diff. 

% cvs -q rdiff -r asst3-base -r asst3-adv-finish -u asst3-src > ~/asst3_adv.diff
Submit your solution 
% cd ~
% give cs3231 asst3_adv asst3_adv.diff
You're now done.