OS/161 Virtual Memory Implementation

Overview

In this project 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 project you will adapt OS/161 to take full advantage of the simulated hardware by implementing address space management, page table management, and management of the MIPS software-managed Translation Lookaside Buffer (TLB).

The System/161 TLB

This section provides a summary of the R3000 (System/161) virtual memory mechanisms. Further info is provided in the lectures and in the R3000 Reference Manual and Hardware Guide on the course website.

The R3000 TLB entry includes a 20-bit virtual page number and a 20-bit physical frame number as well as the following five fields:

• global: 1 bit; if set, ignore the PID bits in the TLB.
• valid: 1 bit; set if the TLB entry contains a valid translation.
• dirty: 1 bit; enables writing to the page referenced by the entry; if this bit is 0, the page is only accessible for reading.
• nocache: 1 bit; unused in System/161. In a real processor, indicates that the hardware cache will be disabled when accessing this page.
• asid: 6 bits; a context or address space ID that can be used to allow entries to remain in the TLB after a context switch.

All these bits/values are maintained by the operating system (i.e. your code). When the valid bit is set, the TLB entry contains a valid translation. This implies 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.

For this project, you may largely ignore the ASID field and set it to zero in your TLB entries. Note: In OS/161, as_activate() is called whenever a new address space becomes active in the TLB, so as_activate() is typically programmed to flush the TLB (why?).

The System/161 Virtual Address Space Map

The MIPS divides its address space into several regions that have hardwired properties. These are:

• kseg2, TLB-mapped cacheable kernel space
• kseg1, direct-mapped uncached kernel space
• kseg0, direct-mapped cached kernel space
• kuseg, TLB-mapped cacheable user space

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.

Memory Map Layout

Address	Segment	Special Properties
0xffffffff	kseg2
0xc0000000
0xbfffffff	kseg1
0xbfc00100		UTLB exception address if BEV set.
0xbfc00180		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

Implementation Requirements

Address Space Management

OS/161 uses struct addrspace to encapsulate address space book-keeping. You'll need to implement functions in kern/vm/addrspace.c and potentially modify the data type. Function semantics are documented in kern/include/addrspace.h.

Note: Use a fixed-size stack region (say 16 pages) for each process.

Address Translation and Page Table Implementation

The main goal is providing virtual memory translation for user programs by:

1. Extending OS/161 address spaces with a page table
2. Implementing a TLB refill handler for the page table

The project requires implementing a 2-level hierarchical page table:

• First Level:
  • Indexed using 11 most significant bits of page number
  • Contains 2048 (2^11) entries
• Second Level:
  • Indexed using 9 least significant bits of page number
  • Contains 512 (2^9) entries per node

Lazy Allocation Strategy

The page table implements a lazy data-structure approach:

• The contents of the page table, including second-level nodes, are only allocated when needed
• The final solution must allocate pages (and level-2 nodes if needed) only when a page-fault occurs
• Newly allocated frames used to back pages must be zero-filled before mapping

Design Considerations

Key questions to address when implementing the page table:

1. What information needs to be stored for each page?
2. How is the page table populated?
3. Should the data structure be global or per-process?

Note: Applications expect pages to contain zeros when first used. This requires zero-filling newly allocated frames before mapping them.