Now that you have implemented address translation to traverse existing page table structures, we’re going to add support for mapping new memory into an address space by changing the page table structure. There are two larger pieces of this implementation:
vm_map function that maps a page of memory into an existing address space.If you remember back a few weeks, we wrote code to traverse the bootloader’s list of usable memory. This information tells us which physical addresses are valid to use on the current machine. You will need to implement a simple allocator that can hand out individual pages of physical memory. Here is a suggested interface for your physical memory allocator:
/**
* Allocate a page of physical memory.
* \returns the physical address of the allocated physical memory or 0 on error.
*/
uintptr_t pmem_alloc();
/**
* Free a page of physical memory.
* \param p is the physical address of the page to free, which must be page-aligned.
*/
void pmem_free(uintptr_t p);
You are free to design your allocator however you like, but remember: this is much simpler than the malloc lab in 213.
We are allocating and freeing memory of just one size (a page, or 0x1000 bytes).
I recommend using a freelist (review the OSTEP chapter on Free Space Management if you’ve forgotten how that works) but there are other reasonable approaches you could use.
Just keep in mind that usable pages of memory are not necessarily all contiguous, and they certainly won’t be contiguous once you start freeing pages as they are removed from an address space.
Once you can allocate physical pages you are ready to start adding mappings to an address space.
The signature for the vm_map function, which you will implement, is included below:
/**
* Map a single page of memory into a virtual address space.
* \param root The physical address of the top-level page table structure
* \param address The virtual address to map into the address space, must be page-aligned
* \param user Should the page be user-accessible?
* \param writable Should the page be writable?
* \param executable Should the page be executable?
* \returns true if the mapping succeeded, or false if there was an error
*/
bool vm_map(uintptr_t root, uintptr_t address, bool user, bool writable, bool executable);
Starting at the top-level page table structure (which we called the level-4 page table in class) you will need to traverse down through the levels just as you did in your translate function.
However, this time you need to be prepared for missing entries in the page table.
When you find a missing entry anywhere except the last-level page table you will need to allocate and fill in a new page table.
vm_mapFor our example, let’s assume we are trying to map a page at virtual address 0x50004000.
From that address we can extract the following indices for virtual address translation:
We start the process in the level 4 page table, whose physical address is provided to vm_map.
We look at index 0, which we will assume (for this example) is marked as present.
The entry at index 0 tells us the physical address of the level 3 page table.
Next, we look at index 1 of the level 3 page table.
For the sake of example, let’s assume this entry is not present.
That means there is no level 2 page table corresponding to the virtual address we are mapping.
Call pmem_alloc() to allocate a page of physical memory, fill it with zeros to create a new level 2 page table.
Before we can proceed, we need to update the entry in the level 3 page table to point to the new level 2 table we just allocated;
update the entry to include the necessary bits of the new table’s physical address.
You should also mark the entry as user-accessible, writable, and executable (e.g. leave the no-execute bit set to zero);
it will be much easier for us to manage the page table structure if we only restrict permissions in the level 1 page table.
We just created the level 2 page table, so it should not have any entries present (you did zero it out, right?). We’ll follow the same procedure as above to allocate and attach a level 1 page table at index 128.
And finally, we are in the level 1 page table.
There will be no entry present at index 4 of this table, since the table is new.
Allocate a page of physical memory that will be mapped into the address space.
Then, update the entry at index 4 to reference this physical memory.
Unlike the higher levels, at this level we need to respect the requested user, writable, and executable permissions from the parameters to vm_map.
Once you’ve filled in this entry, the page should be mapped.
Your vm_map function should return success if everything goes as expected.
Return an error if any of your calls to pmem_alloc fail (meaning you are out of physical memory) or if there is already a page mapped at the requested virtual address.
vm_map functionOnce you have vm_map implemented you should be able to map new virtual addresses into your address space and use that memory.
The example below tests vm_map with an arbitrary virtual address.
uintptr_t root = read_cr3() & 0xFFFFFFFFFFFFF000;
int* p = (int*)0x50004000;
bool result = vm_map(root, (uintptr_t)p, false, true, false);
if (result) {
*p = 123;
kprintf("Stored %d at %p\n", *p, p);
} else {
kprintf("vm_map failed with an error\n");
}
If your vm_map function works and the virtual address you test is available the above code should work.
This code will be fairly tricky to troubleshoot, so you may want to start out by adding lots of logging to the vm_map function as you traverse the page table structure.
Make sure you test vm_map with virtual addresses that are already mapped to be sure it returns an error as expected.
If you map a page as read-only you will still be able to write to it; that’s because our kernel is booted with write protection turned off. You can use the following code to enable write protection:
// Enable write protection
uint64_t cr0 = read_cr0();
cr0 |= 0x10000;
write_cr0(cr0);
You’ll need these helper functions to access control register zero:
uint64_t read_cr0() {
uintptr_t value;
__asm__("mov %%cr0, %0" : "=r" (value));
return value;
}
void write_cr0(uint64_t value) {
__asm__("mov %0, %%cr0" : : "r" (value));
}
We’ll eventually need the option to unmap a page or change its protections.
We’ll do that using vm_unmap and vm_protect functions:
/**
* Unmap a page from a virtual address space
* \param root The physical address of the top-level page table structure
* \param address The virtual address to unmap from the address space
* \returns true if successful, or false if anything goes wrong
*/
bool vm_unmap(uintptr_t root, uintptr_t address);
/**
* Change the protections for a page in a virtual address space
* \param root The physical address of the top-level page table structure
* \param address The virtual address to update
* \param user Should the page be user-accessible or kernel only?
* \param writable Should the page be writable?
* \param executable Should the page be executable?
* \returns true if successful, or false if anything goes wrong (e.g. page is not mapped)
*/
bool vm_protect(uintptr_t root, uintptr_t address, bool user, bool writable, bool executable);