1 Introduction
The goal in this assignment is to implement simulated OS code that handles a multi-level (trie-based) page table. You will implement two functions. The first function creates/destroys virtual memory mappings in a page table. The second function checks if an address is mapped in a page table. (The second function is needed if the OS wants to figure out which physical address a process virtual address maps to.)
Your code will be a simulation because it will run in a normal process. We provide two files,
os.c and os.h, which contain helper functions that simulate some OS functionality that your code
will need to call. For your convenience, there’s also a main() function demonstrating usage of the
code. However, the provided main() only exercises your code in trivial ways. We recommend that
you c6h3ange it t4o8th4o7roughly3t9est3t8he funct3io0n2s9that you2i1mp20lemented.
12 11 0
level 0 offset level 1 offset level 2 offset level 3 offset flags
1.1 Target hardware
Our simulated OS targets an imaginary 64-bit x86-like CPU. When talking about addresses (virtual or physical), we refer to the least significant bit as bit 0 and to the most significant bit as bit 63.
63 12 11 1 0 frame# WV
Virtual addresses The virtual address size of our hardware is 64 bits, of which only the lower 57 bits are used for translation. The top 7 bits are guaranteed to be identical to bit 56, i.e., they
are either all ones or all zeroes. The following depicts the virtual address layout:
write allowed? valid?
|
sign ext |
virtual page # |
offset |
63 5756
1211 0
V valid?
63
12 11 0
Physical addresses
The physical address size of our hardware is also 64 bits.
frame #
1
63
Page table structure
12 11 1 0 frame# WV
write allowed? valid?
The page/frame size is 4KB (4096 bytes). Page table nodes occupy a
63 5756
1211 0
physical page frame, i.e., they are 4 KB in size. The size of a page table entry is 64 bits. Bit 0 is the
sign ext virtual page # offset
valid bit. Bits 1–11 are unused and must be set to zero. (This means that our target CPU does not implement page access rights.) The top 52 bits contain the page frame number that this entry points to. The following depicts the PTE format:
63 12 11 0 valid?
|
frame # |
V |
Number of page table levels To successfully complete the assignment, you must answer to yourself: how many levels are there in our target machine’s multi-level page table? As mentioned, assume that only the lowest 57 bits of the virtual address are used for translation.
1.2 OS physical memory manager
To write code that manipulates page tables, you need to be able to perform the following: (1) obtain the page number of an unused physical page, which marks it as used; and (2) obtain the kernel virtual address of a given physical address. The provided os.c contains functions simulating this functionality:
1. Use the following function to allocate a physical page (also called page frame): uint64 t alloc page frame(void);
This function returns the physical page number of the allocated page. In this assignment, you do not need to free physical pages. If alloc page frame() is unable to allocate a physical page, it will exit the program. The content of the allocated page frame is all zeroes.
2. Use the following function to obtain a pointer (i.e., virtual address) to a physical address: void* phys to virt(uint64 t phys addr);
The valid inputs to phys to virt() are addresses that reside in physical pages that were previously returned by alloc page frame(). If it is called with an invalid input, it returns NULL.
2 Assignment description
Implement the following two functions in a file named pt.c. This file should #include “os.h” to obtain the function prototypes.
1. A function to create/destroy virtual memory mappings in a page table:
void page table update(uint64 t pt, uint64 t vpn, uint64 t ppn);
This function takes the following arguments:
(a) pt: The physical page number of the page table root (this is the physical page that the page table base register in the CPU state will point to). You can assume that pt has been previously returned by alloc page frame().
2
(b) vpn: The virtual page number the caller wishes to map/unmap.
(c) ppn: Can be one of two cases. If ppn is equal to a special NO MAPPING value (defined in os.h), then vpn’s mapping (if it exists) should be destroyed. Otherwise, ppn specifies the physical page number that vpn should be mapped to.
2. A function to query the mapping of a virtual page number in a page table: uint64 t page table query(uint64 t pt, uint64 t vpn);
This function returns the physical page number that vpn is mapped to, or NO MAPPING if no mapping exists. The meaning of the pt argument is the same as with page table update().
You can implement helper functions for your code, but make sake sure to implement them in your pt.c file. You may not submit additional files (not even header files).
IMPORTANT: A page table node should be treated as an array of uint64 ts. 2.1 Something to think about (no need to submit)
How would your code change if you were required to free a page table node once all of the PTEs it contains become invalid? How would you detect this condition? How efficient would your approach be (i.e., how much overhead would it add on every page table update)?
