COMS W4118 Operating Systems I

x86 Page Tables

1-Level Paging

With a 32-bit virtual address, we have 4GB of virtual memory. Assume 4KB page size.

We therefore have 4GB / 4KB == 2^ 20 == 1M virtual pages. Need 20 bits to index into page table, 12 bits for offset (2 ^ 12 == 4KB).

+---------------------------+----------+
|    virtual page number    |  offset  | 
+---------------------------+----------+

|----------20 bits----------|--12 bits-|

Assume 4GB of physical memory. Physical addresses are therefore also 32 bits, with the same layout as above.

The page table must have 1M entries, one for each virtual page. Each PFN is 20 bits and let’s assume metadata takes up the remaining 12 bits. Page table entries are therefore 32 bits (4B). The total page table size is 4MB, which is huge!

x86-1-level

Observation: virtual address space is sparse… most of the page table is unused. We had to make the page table an array to do 1-level translation, but this is wasteful. Can we only allocate the portions of the page table we are actually using?

x86-1-level-sparse

2-Level Paging

Let’s break up the page table into pages. If a page table entry is 4B and a page is 4KB, we can fit 4KB / 4B == 1024 entries into one page.

1M entries split into 1024-entry sized chunks yields 1M / 1K == 1K pages. Let’s only allocate the pages of the page table that we’re actually going to use.

In the above example, the middle of the page table is unused, so we won’t allocate those pages. How do we find the pages of the page table that are actually being used?

Introduce page table global directory (PGD), which has 1024 entries, 1 entry per page table chunk. Look up the page table chunk index here to find where the chunk is in memory. The PGD has 1024 entries and each entry is 4B, so the PGD fits exactly into 1 page.

Still need 12 bits for offset into the physical frame. Since the page table chunk only has 1024 entries, just need 10 bits to index into it. Since PGD has 1024 entries, need 10 bits to index into it.

x86-2-level

Each portion of the virtual address acts as an index into its corresponding page. Apply index to base of the page to get address:

Hierarchical structure (as opposed to linear structures) reduces memory consumption.

3-Level Paging

32-bit physical address means we can only have 4GB physical memory. Mid/late-90s: machines are OK with 4GB virtual address space but want to run A LOT of processes… need more physical memory because 4GB isn’t enough anymore.

32-bit virtual address is still fine for 4GB virtual address space.

To allow for more RAM, change physical address to 36-bits (12-bit offset, 24-bit PFN). 16M frames * 4KB page size == 64GB physical memory.

Problem: 32-bit page table entry size is too small, not enough room for 24-bit PFN and metadata bits. Double PTE size to 64 bits (8B).

Recall that with 32-bit page table entries, we could fit 1K entries into 1 page. Since we doubled the size of PTE, we can only fit 512 entries into page table now. Since virtual address space has 1M pages, we still need 1M entries. 1M entries split into 512-entry sized chunks yields 1M / 1K == 2K pages.

PGD used to have 1024 entries so that it can address the 1K page table chunks. Two problems:

Instead of 1 PGD, we now have 4 PGDs. How do we choose what PGD to use?

Recall 32-bit virtual address: 12 bits for frame offset. Since page table chunk only has 512 entries, we only need 9 bits to index into it. Likewise, each PGD only has 512 entries, so another 9 bits for PGD index. Remaining 2 bits are used to choose within the 4 PGDs.

x86-3-level-pae

Basic idea: to add more physical memory, add more levels!

4-Level Paging

64-bit CPU, but 64-bit virtual memory is huge (16 EB)! Let’s use 48-bit virtual address, that’s 256 TB of addressable virtual memory.

With 64 byte page table entries and 4KB pages, our virtual address would be partitioned as: x86-4-level

Page table levels:

5-Level Paging

Relatively new, not yet implemented on all processors. Linux support added in v4.14.

Increase virtual address size to 57 bits. That’s 128 PB of addressable virtual memory!

With 64 byte page table entries and 4KB pages, our virtual address would be partitioned as: x86-5-level

New level: Page 4th Level Directory (P4D).

Linux supported is gated behind feature macro guard, check if CONFIG_PGTABLE_LEVELS > 4. If P4D isn’t present, it is “folded” into the PGD. This allows page table traversal code to be written the same way regardless of P4D support.