Kernel Implementation: Paging (phase 1)

We’re going to shift gears a bit and move away from handling keyboard input. We will need to create and manipulate page tables before our kernel can start running programs, but we’ll start off by just examining the page table structure the bootloader set up for us. For this implementation task, you will write a translate function that takes a virtual address and translates it to the physical address it is mapped to. This function will have the following signature:

/**
 * Translate a virtual address to its mapped physical address
 *
 * \param address     The virtual address to translate
 */
void translate(uintptr_t page_table, void* address) {
  ...
}

We’re just writing this function to explore page tables, so it doesn’t need to return anything; we’ll just print information about the page table structure as we traverse it.

Finding the top-level page table pointer

The pointer to the top-level page table is stored in a special processor register called cr3. The code below reads the value of cr3 and returns it:

uintptr_t read_cr3() {
  uintptr_t value;
  __asm__("mov %%cr3, %0" : "=r" (value));
  return value;
}

The cr3 register holds the page table pointer, but the table’s starting address is always aligned to a page boundary, meaning the bottom 12 bits of the address are available for other uses. You will need to mask off the bottom 12 bits to find the true starting address of the page table structure.

Page table entry structure

We will spend time in class coming up with a C struct to represent a page table entry. Here is the page table entry structure we wrote together in class:

typedef struct page_table_entry {
  bool present : 1;
  bool writable : 1;
  bool kernel : 1;
  uint16_t unused : 9;
  uint64_t address : 51;
  bool no_execute : 1;
} __attribute__((packed)) pt_entry_t;

Feel free to break apart the unused field to look at the accessed and dirty bits if you like, but we won’t need them for our implementation.

What to implement

Your implementation should produce output to show each level of the virtual address translation. Here is example output from a call to translate(_start):

Translating 0xffffffff80000510
  Level 4 (index 511 of 0x7f5ed000)
    user writable executable -> 0x7f5ec000
  Level 3 (index 510 of 0x7f5ec000)
    user writable executable -> 0x7f5eb000
  Level 2 (index 0 of 0x7f5eb000)
    user writable executable -> 0x7f5ea000
  Level 1 (index 0 of 0x7f5ea000)
    kernel executable -> 0x7f600000
  0xffffffff80000510 maps to 0x7f600510

Notice that this output shows whether each mapping is user-accessible or only kernel-accessible, and whether the mapping allows write and/or execute permissions for the mapped pages.

Here is another example output for translate(NULL):

Translating 0x0
  Level 4 (index 0 of 0x7f5ed000)
    user writable executable -> 0x7f5e4000
  Level 3 (index 0 of 0x7f5e4000)
    user writable executable -> 0x7f5e3000
  Level 2 (index 0 of 0x7f5e3000)
    user writable executable -> 0x7f5e2000
  Level 1 (index 0 of 0x7f5e2000)
    not present

It is okay if your implementation produces slightly different output, but make sure you test a variety of pointers to ensure you have reasonable output from your address translation code. Accessing a page table is easier than creating or modifying one, so make sure you have this working before our next class, where we will start modifying page table structures.