How do x86 page tables work?

Question

I'm familiar with the MIPS architecture, which is has a software-managed TLB. So how and where you (the operating system) wants to store the page tables and the page table entries is completely up to you. For example I did a project with a single inverted page table; I saw others using 2-level page tables per process.

But what's the story with x86? From what I know the TLB is hardware-managed. Does x86 tell basically tell you, "Hey this is where the page table entries you're currently using need to go [physical address range]"? But wait, I've always thought x86 uses multi-level page tables, so would it tell you where to put the 1st level or something...? I'm confused.

Thanks for any help.

Answer 1

Upon entering protected mode, the CR3 register points to a "page directory" (you can put it anywhere you want before you enter protected mode), which is a page of memory (remember, a "small" page is 4 KiB, and a "large" page is 4 MiB) with 1024 page directory entries (PDEs) that point to to "page tables". Each entry is the top 10 bits of a pointer (the address of the page table), plus a bunch of flags that make up the bottom portion of the pointer (present, permission, dirty, etc.).

(The 1024 just comes from the fact that a page is 4096 bytes and a pointer is 4 bytes.)

Each "page table" is itself 1024 "page table entries" (PTEs), which, again, contains 1024 entries that point to physical pages in memory, along with a bunch of (almost the same) flags.

So, to translate a 32-bit virtual address, you take the top 10 bits of the pointer as an index into the table at CR3 (since there are 2¹⁰ entries), and -- if that PDE is further subdivided (meaning it isn't a "large" page, which you can figure out from the flags) -- you take the top 20 bits of the PDE, look up the page table at that address, and index into it with the virtual address's next-topmost 10 bits. Then the topmost 20 bits refer you to the physical page, assuming the bottom 12 bits tell you the physical page is actually present.

If you're using Physical Address Extension (PAE), then you get another level in the hierarchy at the very top.

Note: for your own sanity (and maybe the CPU's), you'd probably want to map the page directory and the page table to themselves, otherwise things get confusing fast. :)

The TLB is hardware-managed -- so the caching of the page tables is transparent -- but there is an instruction, InvlPG, that invalidates a PTE in the the TLB for you. (I don't know exactly when you should use it and when you shouldn't.)

Source: http://wiki.osdev.org/Paging