Purpose

This exercise is designed to cover how to perform a page walk.

Setup

Once you have logged in to Edlab, you can clone this repo using

git clone <https://github.com/umass-cs-377/377-lab-pagewalk.git>

Then you can use cd to open the directory you just cloned:

cd F22-377-pagewalk

This repository includes a Makefile that allows you to locally compile and run all the sample code listed in this tutorial. You can compile them by running make. Feel free to modify the source files yourself, after making changes you can run make again to build new binaries from your modified files. You can also use make clean to remove all the built files, this command is usually used when something went wrong during the compilation so that you can start fresh.

Page Walk

In this assignment, you are asked to implement a simple page walk simulation. A page walk refers to the process of translating the virtual address to the physical address.

Let's start by describing the memory we have to work with. In this example, we have a very small memory space of $2^8 = 256$ bytes (recall, a byte is 8 bits). We divide the address space into $2^2 = 4$ chunks called pages. In total, we have $\frac{2^8}{2^2} = 2^6 = 64$ pages in our memory. For this lab, we will use 3-level paging scheme.

Terminology

Throughout the lab, you'll see the terms MSB and LSB. MSB stands for Most Significant Bit(s). This is the leftmost bit(s). For example, the binary number 10000000 has an MSB of 1. Similarly, LBS stands for Least Significant Bit(s). For example, the binary number 00000001 has a LBS of 1.

For the rest of the page table, we used the Terminology used in the GNU/Linx.

PGD (Page Global Directory)

The PGD is the entry point for every virtual to physical translation. When a program starts, the OS assigns the process a PGD address, and stores the address of the page into the register cr3 register on x86. Each entry in the PGD provides the staring address of the next-level called PMD.

PMD (Page Middle Directory)

The PMD is the second level of the indirection. This has the same structure as the PGD, but (in our example) consists of at most 4 different pages. The addresses of each of these pages is stored in the PGD entries. Each value in the PMD stores the address of the next-level PTE.

PTE (Page Table Entry)

The PTE is the lowest level of indirection. Each value in PTE stores a physical address of a virtual address.