Recursive Page Tables

I just got my page fault handler in my hobby os working so it allocates physical memory and updates page tables. It was hard. The key concept that helped me finally get it working was recursive page tables.

The Problem

It’s tricky modifying page tables once you’ve turned on virtual memory. To update a page table, you first need a virtual address you can use to reference it. That requires you update the page directory with the physical address of the page table. That requires that you have a virtual address for the page directory. And that requires that you modify a page table with the physical address of the page directory. BUT THAT’S WHAT WE WERE TRYING TO DO IN THE FIRST PLACE!

The Solution

The solution I went with was recursive page tables (following advice from /r/osdev).

Under this scheme, the last entry in the page directory points to itself. This leads to a couple cool consequences:

1. Virtual address 0xFFC00000 points to page table 0
2. Virtual address 0xFFFFE000 points to page table 1022
3. Virtual address 0xFFFFF000 points to the page directory (which is also page table 1023)

I’ll explain point 1. The first 10 bits of “0xFFC00000” are set to 1, so the MMU will look in the last entry in the page directory. This points to itself. The next 10 bits are 0, so the MMU will look at entry 0 of the page directory. This points to page table 0.

The same logic applies to point 2.

Now point 3. The first 10 bits are set to 1, so the MMU follows the recursive link, like before. The next 10 bits are also set to 1, so the the MMU again follows the recursive link. That means this virtual address maps to the physical address of the page directory.

This concept can extend to page table structures with more than two levels:

Image from another good article that explains recursive page tables: http://os.phil-opp.com/modifying-page-tables.html

The Implementation

In my operating system, I made a function called initialize_page_directory(). which sets this up. It assumes you already know the physical and virtual addresses of the page directory, and that paging is turned on. Then it follows these steps:

1. Set the last entry in the page directory to point to the physical address of the page directory
2. Allocate physical memory for a page table (that is, choose a piece of physical memory where your page table will reside)
3. Fill in an entry in the page directory with the physical address of the page table
4. Calculate the virtual address of the page table based on the index in the page directory (using the mapping described in the previous section)
5. Use the virtual address of the page table to modify it

There you have it! A high-level description of how recursive page tables work. It’s a pretty neat way to map page tables into virtual memory, the very same structures that determine the mapping! A recursive solution to a recursive problem.