Garrett Burroughs

Pagetable Simulator

A project that simulates OS pagetables

Summary

This is a virtual address simulator that uses page tables to translate “Virtual Addresses” to “Physical Addresses”. The virtual addresses are defined by the user, and can be allocated through page_allocate(size_t ptr) and the physical addresses are the addresses that the C program can actually use (see pagetable.c for an example of this).

Configuration

In the config.h there are some options that change how the pagetable allocation and lookup works. The options available are

In order to change these values, simply edit the config.h. For example a config.h that looks like:

#define LEVELS 2
#define POBITS 14
#define DEBUG 1

would have a two level pagetable lookup, 14 bits for the page offset in the virtual address, and would print out debug information.

Increasing the POBITS will increase the page size (and decreasing POBITS will decrease page size). This means that there will need to be less allocations, however, there will be more unused pagetable entries due to the larger size. The recommended value for POBITS is 12, giving a pagetable size of 4KB. Valid values are between 1 and 6 inclusive

Increasing LEVELS will increase the number of pagetable levels are used for lookups. More levels allow for a larger address space at the tradeoff of more time being used for each lookup. More LEVELS also allows for a more efficient storing of pagetable entries, as if a top level entry is marked invalid, the lower levels will not be allocated. Valid values are between 4 and 18 inclusive

The values of LEVELS and POBITS also affects the virtual address layout and page size. The page size is 2^POBITS bytes. Each pagetable entry is the size of a size_t. This means that there will be 2^POBITS / (sizeof size_t) entries in each pagetable. To reference all of those entries, the bits used for each pagetable lookup will be log2(2^POBITS / (sizeof size_t) or POBITS - log2(sizeof size_t) bits long. For example. Given size_t is 8 bytes, and POBITS is 12, the bits used for pagetable lookups will be 9 bits long. The virtual pagenumber will therefore be (POBITS - log2(sizeof size_t)) * LEVELS bits long, to store the information needed for each level lookup. This also imposes a limitation on the values of LEVELS and POBITS because virtual address must fit in one size_t. This means that the following must be true (POBITS - log2(sizeof size_t)) * LEVELS + POBITS <= sizeof(size_t) * 8. On a 64 bit system, this would be (POBITS - 3) * LEVELS + POBITS <= 64.

Virtual Address Layout

As discussed in the configuration section, the VPN and page offset depend on the values of LEVELS and POBITS, as well as the size of a size_t on the system the program is running on. For this example, we will assume a LEVELS of 4, POBITS of 12 and a size_t is 64 bits. This gives us level lookup numbers of 9 bits, VPNs that are 36 bits, page offsets that are 12 bits, and virtual addresses that are 48 bits long.

For a virtual address, the least significant POBITS are used as the page offset. For example an address of 0x123456 would have a page offset of 0x456. The remaining least significant bits will be the Virtual page number, split into even parts

+---------------------------------------+-------------------+
| Virtual Page Number                   | Page Offset       | 
+---------+---------+---------+---------+-------------------+ 
| Level 1 | Level 2 | Level 3 | Level 4 |                   | 
+---------+---------+---------+---------+-------------------+ 
| 9 bits  | 9 bits  | 9 bits  | 9 bits  | 12 bits           | 
+---------+---------+---------+---------+-------------------+

Example Use Cases

The main purpose of this program is to demonstrate how pagetable lookups and virtual memory work. By enabling the DEBUG option in config.h the program will print out all of the parts of the pagetable lookup, allowing a user to trace the process. This allows the user to gain a deeper and interactive understanding of the pagetable lookup process.

Bugs and Limitations

Currently, it is not possible to de-allocate memory allocated with page_allocate. The reason the limitation is currently in place is because memroy is allocated a page at a time, and the data structures in place only store which pages are allocated. To add a deallocate interface would mean to deallocate the entire page that a memory address references, as opposed to that specific location in memory. Consider the following code snippit with a hypothetical page_deallocate that works in the same manner as page_allocate but deallocates the page the memory address lives in. For this example POBITS is 12 and LEVELS is 1:

page_allocate(0x1000); // Virtual page 1 is allocated
page_allocate(0x1001); // This address is at the same page as 0x1000, so no new pages are allocated
size_t p1 = translate(0x1000);
int* p2 = (int *)translate(0x1001);
*p2 = 42; // Store some data at p2

deallocate(0x1000); // Virtual page 1 is deallocated
int num = *p2; // Potential use after free error because the memory that p2 pointed to was deallocated, even though we never deallocted 0x1001

A fix to this issue would be to store the allocated and deallocated addresses and only deallocate a page when all of it’s entries have been deallocated, however this would cause extreme memory useage as every single vitual address in use would have to be marked as allocated or deallocated.

Example Usage

To use this library, first include mlpt.h, once it is included, memory can be allocated using the page_allocate function

#include "mlpt.h"

int main(void) {
    size_t pointer = page_allocate(0x123456); // This will create a mapping from "virtual" address 0x123456 to a "physical" address
}

Once virtual memory has been created, you can then access the physical address by using the translate function

#include "mlpt.h"

int main(void) {
    page_allocate(0x123456); // This will create a mapping from "virtual" address 0x123456 to a "physical" address
    int* physical_address = (int *)translate(0x123456); // translate will return a pointer to the "physical" memory that can then be used as normal
    *physical_address = 10; `
}

Languages Used: C

Contributors

This work was created in CS3130 at the University of Virginia and was reviewed by: