4. Multi-level page tables

Calculating Page Table Size

In a 32-bit address space with $4\text{ kB}$ pages:

page number $p$	offset $o$
$00005$	$123$

$o$ is a 12-bit number $\in [0,4095]$ $p$ is a 20-bit number $\in p[0,1048575]$

In addition to this, real page table entries (PTEs) are not just a frame number, but may also include ‘valid’, permissions, ‘dirty’, ‘used’:

V	R	W	X	D	U	frame#

We’re considering a ‘flat’ page table, i.e. one big long array with one entry per page. If $p$ is a number $n$ bits wide, there are $2^n$ pages. If each PTE is $m$ bytes, then the page table size is $m\times 2^n$.

In our example above, this means our page table is $4194304$ bytes. It is unacceptable for each process’s page table to require megabytes of memory space.

Page Table Length Register

We could allocate a short page initially and grow it on demand, updating the PTLR. Any entries beyond the PTLR are implicitly invalid.

This creates two problems:

• Virtual address space must be contiguous and this is not a property of the usual ‘stack grows down, heap grows up’ memory layout.
• Growing the page table requires contiguous physical memory which can cause external fragmentation.

Multi-level Page Tables

Most processes however, do not need all $2^n$ pages, so they don’t need a page table with $2^n$ entries. So we could use a data structure that handles sparseness better such as a tree.

The only caveat is it must be a tree of fixed depth as hardware is not recursive.

We conceptually divide the flat page table into chunks:

We add a root node (page directory / top-level table). For example, here it is the root of a 1024-ary tree, of exactly two levels:

‘X’ in the page directory $\to$ an entire chunk of the page table is unused:

Chunks that are entirely unused don’t need to be stored:

Translation now needs to occur in two stages:

We split $p$ into top bits (first lookup) and bottom bits (second lookup). The idea generalises, most modern 64-bit architectures have 4-level page tables. (in x86-64 these levels are called PML4, PDP, PD, PT)

However, now the performance really depends on the TLB as we now need to do $4$ extra memory accesses.