CSE Roadmap

Core tier · about 5 hours · 7 parts

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.