Module project1::page_table

Expand description

4-level page table of x86_64.

Implement x86_64’s 4-level page table scheme. More specifically, implement PageTable::map, PageTable::unmap and PageTable::walk.

Background

Memory Protection

One of the main role of operating system is resource abstraction. From now, you build an abstraction for CPU resources. The other important resource of computer system is memory.

Each process has their own memory. Each process’s memory must not visible from others. For example, your web browser should not be able to access the memory of your music player. To do so, the harware introduce the memory protection mechanism to isolate the memory between processes.

Virtual Memory

The concept of virtual memory is to abstract memory addresses from the underlying physical storage device. Instead of accessing the storage device directly, it is authenticated and translated through the memory management unit (MMU). To distinguish the two types of addresses, the pre-translation address is called a virtual address, and the post-translation address is called a physical address. One important difference between these two types of addresses is that the physical addresses are unique and always refer to the same memory location. For virtual addresses, two different virtual addresses can refer to the same physical address. The same virtual address can also refer to different physical addresses.

Paging

Paging is a technique that divides physical and virtual memory space into small chunks of the same size. Each lump is called a page, and it’s typically 4096 bytes. The mapping of physical and virtual memory spaces is managed through the page table. Typically, the currently active page table is managed through a register on a special CPU (e.g. cr3 in x86_64).

Page table

For each memory access, the CPU translates the virtual memory address to the physical memory address through the page table. Because it is inefficient to check the page table for each conversion, the CPU stores the previous results in a cache called Translation Lookaside Buffer (TLB). The page table is also used to set attributes such as access permissions (e.g. read/write) for each page. Note that attributes of all levels are ANDed.

Paging in x86_64

x86_64 uses a 4096-byte page and a 4-level page table. Each table has 4096 bytes, the same size as the page, and an entry of table is 8 bytes. Therefore, the 4-level page table can cover up to 48bit physical address.

The index for each level can be calculated from the virtual memory address:

63          48 47            39 38            30 29            21 20         12 11         0
+-------------+----------------+----------------+----------------+-------------+------------+
| Sign Extend |    Page-Map    | Page-Directory | Page-directory |  Page-Table |    Page    |
|             | Level-4 Offset |    Pointer     |     Offset     |   Offset    |   Offset   |
+-------------+----------------+----------------+----------------+-------------+------------+
              |                |                |                |             |            |
              +------- 9 ------+------- 9 ------+------- 9 ------+----- 9 -----+---- 12 ----+
                                          Virtual Address

A page must be page-aligned, that is, start on a virtual address evenly divisible by the page size. Thus, the last 12 bits of a 64-bit virtual address is the page offset (or just offset). The upper bits are used to indicate the index in the page table.

Each process has an independent set of user pages, which are those pages below the kernel base. The set of kernel pages, on the other hand, is global, and thus remain in the same position regardless of what thread or process is running. The kernel may access both user and kernel pages, but a user process may access only its own user pages.

KeOS provides several useful functions for working with virtual addresses and physical addresses. See Pa and Va for details.

Translation lookaside Buffer

The TLB entry is not updated when the content of page table is changed. Therefore, the kernel must invalidates the updated entry from the TLB by calling a special CPU instruction. In x86_64, invlpg removes the entry according to the specified entry. You can use TLBInvalidate to invalidate the TLB entry. Note that TLB is fully flushed when cr3 is reloaded.