Part 4 of 7 · 2 min read
Four levels
In plain words: For 64-bit machines the same idea needs more levels. Current x86-64 processors use 48 bits of virtual address with 4 KiB pages: 12 bits of offset and 36 bits of page number. Entries are 8 bytes, so a table of 4 KiB holds 512 entries, which takes 9 bits of index. The 36 bits are therefore cut into four fields of 9 bits, giving four levels. The levels are called, from the top, PML4, PDPT, PD and PT in the processor manuals.
The fields of three real addresses, printed by the layout program of page 1 with randomisation off:
| Item | Address | Level 4 | Level 3 | Level 2 | Level 1 | Offset |
|---|---|---|---|---|---|---|
main |
0x555555555199 |
170 | 341 | 170 | 341 | 0x199 |
printf in libc |
0x7ffff7c60100 |
255 | 511 | 446 | 96 | 0x100 |
| stack variable | 0x7fffffff9be4 |
255 | 511 | 511 | 505 | 0xbe4 |
The library and the stack share the top two indexes (255 and 511). So the upper tables are shared between them, and only the lower tables differ. This is why the tables stay small: the clusters of the address space are close to each other in the tree.
A translation that finds nothing in the TLB (page 5) must walk the tree: read the level-4 entry, then the level-3, level-2 and level-1 entries, and finally the data. That is four table reads and one data read, five memory accesses. The processor has hardware to do this walk. It also keeps small caches of the upper levels, to make the walk shorter.
The memory taken by tables can be read from the kernel. The file /proc/self/status has a line VmPTE, the size of the process's page tables. A test mapped a range of address space and touched 16 pages:
| Layout of the 16 touched pages | VmPTE before |
VmPTE after |
|---|---|---|
| 16 pages side by side | 52 kB | 52 kB |
| 16 pages, each 1 GiB apart | 48 kB | 176 kB |
With the pages side by side, the tables did not grow: the pages fitted into tables that already existed. With the pages spread out, the growth was 128 kB, which is 8 kB for each page. That fits the structure: each page that lies in a different 1 GiB region needs its own level-1 table and its own level-2 table, 4 KiB each. The tables for scattered pages cost more than for pages that sit together.
Page walk
A page walk is the series of reads of table entries, one for each level of the page table, that the hardware makes to find the frame for a virtual address that is not in the TLB.
Example: with four levels, a page walk reads four entries, and the data read makes five memory accesses in all.
Check yourself: 1. How many bits of index does each level use on x86-64, and why? 2. Why do the library and the stack addresses share the first two indexes? 3. Why did 16 pages 1 GiB apart cost 128 kB of tables?