next up previous contents
Next: Page Allocation and Deallocation Up: Linux Virtual Memory Algorithms Previous: Linux Virtual Memory Algorithms

Three Level Page Tables


Figure: Three Level Page Tables

Linux assumes that there are three levels of page tables. Each Page Table accessed contains the PFN of the next level of Page Table. Figure gif shows how a virtual address can be broken into a number of fields; each field providing an offset into a particular Page Table. To translate a virtual address into a physical one, the CPU must take the contents of each level field, convert it into an offset into the physical page containing the Page Table and read the PFN of the next level of Page Table. This is repeated three times until the PFN of the physical page containing the virtual address is found. Now the final field in the virtual address, the byte offset, is used to find the data inside the page.

Each platform that Linux runs on must provide translation macros that allow the kernel to traverse the page tables for a particular process. This way, the kernel does not need to know the format of a the entries or how they are arranged.

David A. Rusling