How the K-ary tree is used in x86
ID: x86-paging/how-the-k-ary-tree-is-used-in-x86
x86 Paging Tutorial How the K-ary tree is used in x86 by
Ciro Santilli 36 Updated 2025-04-24 +Created 1970-01-01
Addresses are now split as:
| directory (10 bits) | table (10 bits) | offset (12 bits) |
Then:
- The top table is called a "directory of page tables".
cr3
now points to the location on RAM of the page directory of the current process instead of page tables.Page directory entries are very similar to page table entries except that they point to the physical addresses of page tables instead of physical addresses of pages.Each directory entry also takes up 4 bytes, just like page entries, so that makes 4 KiB per process minimum.Page directory entries also contain a valid flag: if invalid, the OS does not allocate a page table for that entry, and saves memory.Each process has one and only one page directory associated to it (and pointed to bycr3
), so it will contain at least2^10 = 1K
page directory entries, much better than the minimum 1M entries required on a single-level scheme. - Second level entries are also called page tables like the single level scheme.Each page table has only
2^10 = 1K
page table entries instead of2^20
for the single paging scheme. - the offset is again not used for translation, it only gives the offset within a page
One reason for using 10 bits on the first two levels (and not, say,
12 | 8 | 12
) is that each Page Table entry is 4 bytes long. Then the 2^10 entries of Page directories and Page Tables will fit nicely into 4Kb pages. This means that it faster and simpler to allocate and deallocate pages for that purpose. New to topics? Read the docs here!