= Two-level address translation
Choose an original teaching model with 16-<bit> <virtual addresses>, 16-<bit> <physical addresses>, and 256-<byte> <memory pages> and <page frames>. The eight high <bits> identify a virtual <memory page>; divide these into two four-<bit> indices. The eight low <bits> are the offset within the <memory page>. Thus each <page table> has 16 entries: the root selects a lower-level <page table>, and that table selects a data <page frame>. Every <page table entry> is four <bytes>, including its reference and flags. These are chosen model parameters, not a hardware entry encoding.
For a <virtual address> $v$, extract the root index $i$, lower-level index $j$, and offset $d$ by <Euclidean division>:
$$
i=\left\lfloor\frac{v}{4096}\right\rfloor,\qquad
j=\left\lfloor\frac{v}{256}\right\rfloor\bmod16,\qquad
d=v\bmod256,\qquad
v=4096i+256j+d.
$$
Here $\lfloor\cdot\rfloor$ is the <floor function> and $\bmod$ denotes the remainder in <Euclidean division>. Each index ranges from 0 to 15, and $d$ ranges from 0 to 255. In <hexadecimal>, <virtual address> `0x1234` splits into $i=1$, $j=2$, and $d=\mathtt{0x34}=52$; its <binary numeral system> representation is `0001 | 0010 | 00110100`.
Fix the requested operation to be a one-<byte> user read. Assume both table nodes and the data <page frame> are resident, table reads are allowed, and no mapping changes during the <page table walk>. The model requires presence at both levels and takes the <set intersection> of the two entries' read, write, execute, and user-access permissions. This is an explicit <memory protection> rule for this model; <Sv39 page tables> use different rules. The root's <physical address> is `0x8000`; the relevant entries are:
|| Record
|| <Physical address> of record
|| Reference held in the <page table entry>
|| Presence and permissions
| Root entry 1
| `0x8000 + 1*4 = 0x8004`
| Lower-level table at `0x9000`
| Present; user; read/write; no execute
| Lower-level entry 2
| `0x9000 + 2*4 = 0x9008`
| Data <page frame> `0x07`, base `0x0700`
| Present; user; read-only; no execute
The first lookup obtains a table reference, not the final data <physical address>. The second lookup obtains <page frame> number 7. Both entries permit a user read, so the original offset is added to the data <page frame> base:
$$
a=7\cdot256+52=1844=\mathtt{0x0734}.
$$
The <page table walk> therefore reads records at `0x8004` and `0x9008`, then the requested read accesses data at `0x0734`. All three are distinct <physical addresses>. These are two dependent table lookups followed by one data access, not a claim of three accesses to main <computer memory>: a <memory cache> can satisfy table lookups, and cached intermediate translations can skip them.
\Image[/two-level-page-table-address-walk.png]
{title=The model's 4+4+8-bit address split and complete read translation from 0x1234 to 0x0734}
Under the same <memory protection> rule, a user write at `0x1234` fails because lower-level entry 2 denies writes, even though root entry 1 allows them. Clearing either entry's presence flag also prevents the access. An absent root entry stops the <page table walk> before any lower-level lookup. A <page fault> then requires the <operating system> to determine whether a permitted mapping needs storage or the access is invalid; absence alone does not establish <demand paging> eligibility.
With an empty <translation lookaside buffer>, the permitted read causes a <TLB miss> and this successful <page table walk>, with no <page fault>. If the resulting mapping and permissions are cached for the current <address space>, a later read at `0x1235` can use a <TLB hit> to reach `0x0735`. A later write can cause a protection <page fault> on a <TLB hit> because the cached mapping remains read-only. Assume cached permissions are current; changing them requires the architecture's prescribed invalidation. A <TLB miss> describes a missing cached translation, while a <page fault> describes an access that cannot proceed under the translation or protection rules. <Page Tables by The kernel development community>[MMU, TLB, and Page Faults: translation caches, page walks, and faults for missing or forbidden mappings]{ref}
Back to article page
