operatingsystems - 0368-2162 - Multi-Level Page Tables Assignment - Solved

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 change it to thoroughly test the functions that you implemented.

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.

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:

virtual page #
offset
63  57 56      12 11      0 signext

Physical addresses         The physical address size of our hardware is also 64 bits.

Page table structure The page/frame size is 4KB (4096 bytes). Page table nodes occupy a physical page frame, i.e., they are 4KB in size. The size of a page table entry is 64 bits. Bit 0 is the 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

frame #
 
 V

valid?

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 
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().

(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 tableupdate().

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.