Part 6 of 7 · 3 min read
Comparison
Comparing, and shortening the walk
The four layouts trade table size against lookup time and difficulty:
| Layout | Table memory | Reads for a lookup | Notes |
|---|---|---|---|
| Flat | Large: 4 MiB per process for 32 bits | 1 | Impractical for big spaces |
| Multi-level | Small for sparse processes | One for each level (2 to 4) | Common in general-purpose systems |
| Hashed | Grows with the pages in use | One hash, plus the chain | Used for sparse 64-bit spaces |
| Inverted | Fixed by the size of memory | A hash, plus the chain | Slow sharing |
In plain words: In every layout, the number of memory reads for a miss is the main cost, and the TLB (page 5) is the cure. Another cure is to make pages larger. A huge page is a page much larger than the normal one. On x86-64, a 2 MiB page is mapped by an entry at level 2, and the level-1 table is skipped. A 1 GiB page is mapped by an entry at level 3. For a huge page of 2 MiB, the offset has 21 bits, and the walk reads three entries instead of four. One TLB entry now covers 2 MiB, and not 4 KiB. The price is internal waste: a program that needs 100 KiB, but is given a 2 MiB page, wastes nearly all of it. Huge pages suit programs with large, steady regions, such as databases. Level 7 shows how Linux offers them.
Huge page
A huge page is a page much larger than the base page size, for example 2 MiB or 1 GiB on x86-64, mapped by an entry higher in the page table tree, so that a walk is shorter and one TLB entry covers more memory.
Example: one 2 MiB page replaces 512 normal pages of 4 KiB, and needs one table entry and one TLB entry instead of 512.
Interview angle
"Why do page tables have several levels?" A flat table for a 48-bit space would need 512 GiB for each process, almost all of it for unused addresses. A tree creates tables only for the regions in use. The cost is one memory read for each level on a TLB miss, which the TLB hides in most cases.
Check yourself: 1. Which layout has a table size that depends on the memory installed, and not on the processes? 2. How many entries does a walk read for a 2 MiB page on x86-64? 3. What is the cost of using a huge page for a small region?
Words you will meet
| Word | Meaning |
|---|---|
| Sparse address space | An address space mostly empty, in a few clusters |
| Page directory | The top-level table of a multi-level scheme |
| Multi-level page table | A tree of tables, built only for regions in use |
| Page walk | The reads of one entry per level on a TLB miss |
| Hashed page table | A table indexed by a hash of the page number |
| Inverted page table | One entry for each physical frame |
| Huge page | A page of 2 MiB or 1 GiB |
VmPTE |
The size of a process's page tables in /proc/<pid>/status |
Quick notes
- A sparse address space is an address space in which only a small part of the possible addresses is in use, in a few clusters separated by large unused gaps; this is the usual case for a process.
- 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.
- 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.
- An inverted page table is a single table for the whole system with one entry for each physical frame, recording the process and page that occupy the frame; a translation.
- A huge page is a page much larger than the base page size, for example 2 MiB or 1 GiB on x86-64, mapped by an entry higher in the page.