------------------------- Virtual Address Simulator ------------------------- 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). ------------------------- Building ------------------------- This project uses make as it's build system. The default target creates libmlpt.a which contains the pagetable allocation and translation code. This can be build by running `make`. This project also includes a test program which can be built by running `make pagetableTest` and then can be run with `./pagetableTest` ------------------------- Configuration ------------------------- In the `config.h` there are some options that change how the pagetable allocation and lookup works. The options available are - POBITS (the number of bits used for the pagetable offset) - LEVELS (the number of pagetable levels used for lookup) - DEBUG (A logical value that determines whether or not to print out debug information) 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; ` } ```