CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 3 of 7 · 3 min read

Two levels

In plain words: The idea is to page the page table. The page number is split into two fields. The first field selects an entry in a top-level table, the page directory. That entry points to a second-level table, which holds the frame numbers of up to 1,024 pages. If a whole region of the address space is unused, the top-level entry is marked empty, and the second-level table for it is never built.

Take a 32-bit address with 4 KiB pages. The 12 low bits are the offset. The remaining 20 bits are cut into 10 and 10:

 31          22 21          12 11           0
+--------------+--------------+--------------+
| top index    | second index | offset       |
|   10 bits    |   10 bits    |   12 bits    |
+--------------+--------------+--------------+

Each table has 2^10 = 1,024 entries of 4 bytes, so each table is exactly 4 KiB, one page. The top index picks one of 1,024 second-level tables. Each second-level table covers 1,024 pages, which is 4 MiB of address space.

A worked example. The virtual address is 0x00403ABC. In binary, the top 10 bits are 0000000001, which is 1. The next 10 bits are 0000000011, which is 3. The offset is 0xABC. The lookup is:

  1. Read entry 1 of the top-level table. It names the second-level table.
  2. Read entry 3 of that table. It holds the frame number.
  3. The physical address is the frame number times 4,096 plus 0xABC.

That is two reads of table memory before the data read itself, three memory accesses in all.

The saving is large for a sparse process. Suppose the process of the earlier example has 3 MiB of code, data and heap at the bottom of the address space, and 1 MiB of stack at the top. The lower 3 MiB is 768 pages and fits in one second-level table (which covers 4 MiB). The stack is 256 pages at the top, in the last second-level table. The memory used for tables is:

Table Count Size each Total
Top-level 1 4 KiB 4 KiB
Second-level 2 4 KiB 8 KiB
All tables 12 KiB

A flat table would take 4 MiB for the same process. The multi-level layout used 12 KiB, a saving of a factor of about 340. The price is the extra lookup, and the code of the kernel that builds and frees the tables.

Multi-level page table

A multi-level page table is a page table organised as a tree: the page number is split into several fields, each field indexes one level, and tables for unused parts of the address space are not created.

Example: a two-level table with 10-bit fields needs only a 4 KiB top table and the second-level tables of the regions in use.

Check yourself: 1. For the address 0x00C01234, find the top index, the second index and the offset. 2. How much address space does one second-level table cover? 3. How many memory reads does a lookup need before the data read, with two levels?