Understanding the Page Table Step by Step

The concept of the Page Table can be challenging to grasp, and it has puzzled me for a long time. However, during a recent revisit to xv6, a simple Unix-like teaching operating system, I realized that it becomes much easier to understand by thinking of it as a specialized hash map and breaking it down into smaller steps.

What is a Page Table?

A page table is a specialized hash map that maps contiguous virtual memory to contiguous physical memory. Then we can use a large array to store the page table. Finally, multi-level page tables help reduce memory usage by allowing lazy memory allocation.

Step 1: Mapping Contiguous Virtual Memory to Contiguous Physical Memory

Let’s simplify the problem further: mapping virtual memory to physical memory. In programming, we can use a hash map to achieve this.

uint64 virtual_memory_to_physical_memory(uint64 virtual_addr) {
  // Each process has its own hash map, mapping the same virtual memory
  // to different physical memory.
  HashMap map = current_process_map();

  return map[virtual_addr];
}

Due to spatial locality, we prefer to map contiguous virtual memory to contiguous physical memory. Instead of requiring the entire virtual memory to be contiguous in physical memory, we divide it into smaller units called pages. Within a page, all its virtual memory is mapped to the same physical memory page which fulfills performance requirements and allows us to allocate physical memory lazily.

Now, each page table entry corresponds to the starting address of a page. Assuming a page size of 4KB, the last 12 bits of the virtual address are irrelevant for determining the index.

uint64 index = virtual_addr >> 12;

The last 12 bits of the virtual address act as an offset. The mapping function now looks like this:

uint64 virtual_addr_to_physical_addr(uint64 virtual_addr) {
  HashMap page_table = current_process_map();
  uint64 index = virtual_addr >> 12;
  uint64 offset = virtual_addr & 0xFFF;

  return page_table[index] + offset;
}

Step 2: Representing the Page Table in Memory

Now let’s consider how to represent the hash map in memory. Since virtual_addr_to_physical_addr maps different virtual addresses to the starting addresses of physical pages and the indices are continuous, we can use an array to represent the hash map. Each array item is a page table entry (PTE).

In memory, the structure looks like this:

Step 3: Multi-Level Page Tables

From the above image, we notice an obvious problem: it needs to allocate a large page table, even though most of the virtual memory might not be in use. For example, to map 64GB of virtual memory to 4KB pages, we need an array of length 64 * 1024 * 1024 / 4 = 2 ^ 24. If each entry requires 8 bytes, the page table would require 32MB of memory.

To reduce memory usage, we can use multi-level page tables. For example, a two-level page table setup allows the root page table’s entries to point to secondary page tables. Using a 4KB page to store a page table, each can contain 2 ^ 12 addresses, pointing to other page tables. Each of these secondary page tables can map 512 × 4 KB = 2 MB of virtual memory. Thus, one root page table can map 2 × 512 = 1024MB or 1GB of virtual memory. Memory for secondary page tables is allocated only when necessary.

The function for two-level page tables is as follows:

uint64 virtual_addr_to_physical_addr(uint64 virtual_addr) {
  uint64 *root_page_table = current_process_map();
  uint64 root_index = (virtual_addr >> (9 + 12)) & 0x1FF;

  uint64 *page_table = root_page_table[root_index];
  uint64 page_table_index = (virtual_addr >> 12) & 0x1FF;

  uint64 offset = virtual_addr & 0xFFF;

  return page_table[page_table_index] + offset;
}

Others

There are many other aspects of page tables, such as storing page permissions in PTEs and using the Translation Lookaside Buffer (TLB) to cache PTEs. These topics are beyond the scope of this article but are covered in the xv6 textbook and the MIT operating systems course.

In computer science, many concepts appear complex at first. However, by breaking them into smaller steps, their underlying ideas become clear and manageable. Taking baby steps is often the golden rule.