Can the page table be paged out?

Question

According to my understanding it shouldn't be, since it's in kernel space and kernel space is non pageable. But with 64 bit address space I don't see how it can hold the full page table since it would be prohibitively large. Any ideas on how this achieved?

Also I guess even holding it on disk fully would take a lot of space. Since most of the VM space would be unused is there way to limit the page table to contain only used VM address ranges?

Answer 1

The page table is actually a tree: it consists of multiple child tables. The head (root) table stores pointers to child tables, the child tables may also store the pointers to their child tables, and so on (the last table in chain stores the actual page table entry, of course). As the most memory in 64-bit address space is unused, it is not necessary to actually allocate memory for all the tables. The root table just sets most of its pointers to null.

On x86_64, there are 4-5 levels of such indirection.

Answer 2

The page table only needs to hold some subset of the pages that are available. There is no rule that it be complete. When an attempt is made to access a virtual address not mapped by the page table, the kernel is invoked. It can then put that mapping into the page table, removing other mappings that haven't been used recently if desired.

The OS is free to keep every possible mapping that a process might access in the page tables if it wants. Alternatively, it can keep only those recently used if it would prefer that arrangement.

Answer 3

Yes.

Quote from wiki - page table

It was mentioned that creating a page table structure that contained mappings for every virtual page in the virtual address space could end up being wasteful. But, we can get around the excessive space concerns by putting the page table in virtual memory, and letting the virtual memory system manage the memory for the page table.

However, part of this linear page table structure must always stay resident in physical memory, in order to prevent against circular page faults, that look for a key part of the page table that is not present in the page table, which is not present in the page table, etc.