Assignment 3: Virtual Memory

Contents

1. Due Dates and Mark Distribution
2. Introduction
3. Setting Up
4. Tutorial Exercises
5. Coding Assignment
6. Submission of Simplified Assignment
7. Assignment Submission
8. Advanced Assignment

• Due Dates:

  • Simplified Version: 8am, Monday October 25th
  • Full Version: 8am, Monday November 1st

• Marks: Worth 35 marks (of the 100 available for the class mark component of the course)

• 10% of the marks are allocated for submitting a simplified version of the assignment at least one week early. This is explained further below. We won't automark the simplified version, and use a very crude marking scheme: full marks if the code at least looks reasonable (even if it does not compile), 50% (i.e. 5% of overall) if only parts of the simplified assignment are implemented or code is marginal, 0 marks if nothing reasonable is submitted.

  This is basically an easy a way for you to get marks as long as you take the time and seriously think about the problem well before the final deadline: if you are stuck somewhere, add comments to describe the problem. You can also add pseudo-code in comments in case you know only roughly what should happen is a certain function.

• The 10% bonus for one week early is available for the basic assignment. Deadline: 8am, Monday October 25th.
• The extra 5% bonus for a submitted, working assignment within 48-ish hours of release, is also available for the basic assignment. We are stretching this because it's a more difficult assignment. Deadline: 8am, Monday October 11th. See course intro for exact details. Note the demonstration requirement.
• 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 the lecturer in charge, Gabriele Keller.

  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 or the subject of your Week 11 tutorial. Please answer the questions and bring them to your tutorial.

Make sure you have plenty of disk quota available before you start. The OS/161 distribution can be copied from the class account into your home direcory. Assuming you've set up your account as describe earlier, use this command:

% cp -r ~cs3231/assigns/asst3/src ~/cs3231/src

You should now have a src directory to work on.

You will need to increase the amount of physical memory to run some of the provided tests. Update your sys161.conf so that the ramsize is as follows

31      busctl  ramsize=16777216

If you do not have a sys161.conf file you can download this one.

Compile and run the kernel. 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.

You are now ready to start the assignment.

Please answer the following questions and bring them to your tutorial in week 11. 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_finish_load()?
7. What does vm_fault do? When is it called?
8. Assuming a 2-level hierarchical page table (4k pages), show for the following virtual addresses:
   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, with no L2 pages. 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.
   • 0x100008
   • 0x101008
   • 0x1000f0
   • 0x41000
   • 0x41b00

Due to the difficulty of this assignment, and the historical behaviour of students attempting to do this assignment at the last minute, we are providing an incentive scheme to encourage early work. It involves submitting a simplified version of the assignment a week early. This is described later in the Hints Section, and instructions on how to submit this are found here. You do not have to implement the simple version if you're confident of completing the full version, but you must submit some version a week early in order to gain the marks.

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.

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 (through 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 free frame information is initialised. You should just call ram_stealmem() if it 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

• What information do you need to store for each page?
• How does the page table get populated?

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 IPT!
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! Once you're happy with it submit this to asst2_simple as described below. You can submit your full version to asst2_simple if you'd rather not implement the simple version.
7. Understand how the inverted 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.

Once your assignment works, you now need to generate a diff of the changes you made to OS/161. Firstly, you need to clean the source tree.

% cd ~/cs3231/src
% make clean
% cd kern/compile/ASST3
% make clean

You will be submitting a diff of your changes to the original tree. So generate a file containing this diff.

% cd ~/cs3231
% diff -N -r -u -X ~cs3231/assigns/asst3/src/.diffex ~cs3231/assigns/asst3/src src > ~/asst3_simple.diff

The arguments to diff are as follows
• -N: Include any new files you add to diff's output.
• -r: Recursively compare directories
• -u: Generate unified diff output.
• -X: Exclude files listed in .diffex from being included in the 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_simple asst3_simple.diff

You're now done.

Students who wish to attempt the advanced part of this assignment may gain up to an extra 7 marks (20%) for one (or multiple) of the following:
• (easy) Shared pages and copy-on-write.
• (hard) Implement mmap() and related system calls.
• (hard) Implement demand-loading. You should load pages only when they are referenced by the user process, as opposed to at process creation.
• (harder) Implement paging. You should implement some page replacement algorithm and demonstrate your solution running under memory pressure.

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.

Once again, you need to clean the source tree.

% cd ~/cs3231/src
% make clean
% cd kern/compile/ASST2
% make clean

Generate a file containing these differences.

% cd ~/cs3231
% diff -N -r -u -X ~cs3231/assigns/asst3/src/.diffex ~cs3231/assigns/asst3/src src > ~/asst3_adv.diff

To check your diff file, see the assignment Submission Guidelines

Now submit the diff as your assignment. Be careful to submit to the asst3_adv assignment, and not accidently re-submit over your basic assignment submission.

% cd ~
% give cs3231 asst3_adv asst3_adv.diff

You're now done.