Assume again a 32-bit address space (2**32 bytes), with 4KB (2**12 byte)
pages and a 4-byte page-table entry. An address space thus has roughly one
million virtual pages in it (2**32/2**12 ); multiply by the page-table entry
size and you see that our page table is 4MB in size. Recall also: we usually
have one page table for every process in the system! With a hundred active
processes (not uncommon on a modern system), we will be allocating hundreds
of megabytes of memory just for page tables!


Multi-level page tables have some obvious advantages over approaches we've
seen thus far. First, and perhaps most obviously, the multi-level table only
allocates page-table space in proportion to the amount of address space you
are using; thus it is generally compact and supports sparse ad- dress spaces.
Second, if carefully constructed, each portion of the page table fits neatly
within a page, making it easier to manage memory; the OS can simply grab
the next free page when it needs to allocate or grow a page table.

It should be noted that there is a cost to multi-level tables; on a TLB
miss, two loads from memory will be required to get the right translation
information from the page table (one for the page directory, and one for the
PTE itself), in contrast to just one load with a linear page table. Thus,
the multi-level table is a small example of a time-space trade-off.

Another obvious negative is complexity. Whether it is the hardware or OS
handling the page-table lookup (on a TLB miss), doing so is undoubtedly more
involved than a simple linear page-table lookup. Often we are willing to
increase complexity in order to improve performance or reduce overheads; in
the case of a multi-level table, we make page-table lookups more complicated
in order to save valuable memory.

HW
--
5-bit pieces: PDBR offset, PTE offset, offset
x = VA
hex((x>>10)&0x1f), hex((x>>5)&0x1f), hex(x&0x1f)

page, offset
x = PA
hex(x>>5), hex(x&0x1f)

---

pdoffset = va >> 10; ptoffset = (va >> 5) & 0x1f; paoffset = va & 0x1f
hex(va), hex(pdoffset), hex(ptoffset), hex(paoffset)
# x = @(PDBR + pdoffset)
pde = x & 0x7f; hex(pde)
# x = @(pde + ptoffset)
pte = x & 0x7f; hex(pte)
# value = @(pte + paoffset)
pa = (pte << 5) | paoffset; hex(pa)