Paging

The Story So Far

We've moved from arranging memory using segments,

to arranging memory using pages,

Terminology

• Page: A fixed-size chunk of memory that holds code or data.
  • 4 KB is a common size for pages, but it isn't the only option. For example, macOS on ARM CPUs uses 16 KB pages.
• Page Table: A data structure that maps logical addresses to physical addresses.
• Page Table Entry: A single entry in the page table that maps a single page.
• Frame: A fixed-size chunk of physical memory that holds a page. (Sometimes called a page frame.)

Mapping Logical Addresses to Physical Addresses

The page table maps each page to a page frame. In this design, we're imagining the table is external to the CPU because it's too big to fit on the chip.

Fun with Logical to Physical Address Translation: Aliasing

Given our arrangement of memory, it's technically possible to have multiple pages in our logical address space map to the same frame of physical memory: page aliasing. It's not necessarily particularly useful, but it's possible. If you click the link below, it will take you to a page in OnlineGDB where you can see page aliasing in action.

• Try out page aliasing in OnlineGDB

Created two mappings of the same page:
addr1: 0x78f9f10db000
addr2: 0x78f9f10a1000

Writing first string to addr1...
At address 0x78f9f10db000: "Hello from first mapping!"
At address 0x78f9f10a1000: "Hello from first mapping!"

Writing second string to addr2...
At address 0x78f9f10db000: "Greetings from second mapping!"
At address 0x78f9f10a1000: "Greetings from second mapping!"

Improving Efficiency

Because the page table is large, we placed it off-chip in memory. So every memory access actually requires two memory accesses: one to get the page-table entry and another to get the data. Which is slow.

One approach to making address translation more efficient is to add a cache that remembers a small number of recently used page-table entries. In a sane world, this feature would be called the address translation cache, but in the world of computer science, it's called the translation lookaside buffer (TLB), in part because it was invented before people started using the term “cache”.

The diagram below shows how the TLB fits into the picture. We're looking for page 4, which happens to be in frame 3. We could find that by looking in the page table, but since it's in the TLB, we can skip that step.

Saving Memory with Multi-Level Page Tables

First, let's take a look at a slightly bigger page table.

We can make two (other) observations about this page table:

• It's sparse. Many of the entries are empty.
• Pages are allocated in contiguous regions, so the page table tends to have long runs of unused entries.

Which suggests a way we could shorten our page table—and use less memory!

Notice that the page table has a blue line every eight entries, dividing the table into blocks of eight pages.

If we look at each block of pages, we can see that some blocks have pages in use (darker colors), and some do not. Since we only care about the memory that's in use, we can drop the empty blocks, which leaves us with three separate eight-slot page tables with pointers to physical memory frames.

Now we add a new eight-slot upper-level page table whose in-use slots point to the appropriate subtable, giving us a hierarchical or multi-level page table.

(Notice that the two lower-level page tables with purple blocks are contiguous in the upper-level page table.

A Real Process Memory Map

Let's look at a real-world process. Here's a memory map for Neovim, a popular text editor, running on a Raspberry Pi Zero (a 32-bit system). The code and data are at the bottom of memory (top of the diagram), followed by the heap and then a huge gap, and then the stack. Afterwards (in blue), there are a number of shared libraries that Neovim uses. The top quarter of the address space is reserved for the kernel.

(Because sizes vary dramatically, the diagram is not drawn to scale—in fact, the height of each block is based on the cube root of the size of the block. If you hover over any block, it'll tell you more details about it.)

Realistic Multi-Level Page Tables (32-bit Addressing)

On a 32-bit system, we can use the two-level approach for page tables. We have 32 bits of address with 4 KB pages, so we'll break things down as follows:

• The low 12 bits will be the offset within the page.
• The remaining 20 bits are the page number, but we break those 20 bits into two 10-bit chunks:
  • The top 10 bits will be the index into the top-level table.
  • The next 10 bits will be the index into the second-level table.

Thus, for example, the address 0x016980d0 (representing an address inside Neovim's heap) is encoded in binary as

• 0000 0001 0110 1001 1000 0000 1101 0000; thus,
  • The top 10 bits, representing the upper-level page number are 0000 0001 01 or 0x005;
  • The next 10 bits, representing the lower-level page number are 10 1001 1000 or 0x298;
  • The low 12 bits are the offset within the page, 0000 1101 0000 or 0x0d0.

Each table has 1024 entries (2¹⁰). If we can fit all the data we need into four bytes per entry, then each table will be 4 KB, which is also the size of a page, so very convenient. We can imagine each entry in the second-level table has

• 24 bits for the frame number, allowing 2²⁴ frames (since a frame is 4 KB, that's 64 GB of physical memory).
• 8 bits for flags, like whether the page is present or read-only.

Realistic Multi-Level Page Tables (64-bit Addressing)

The architecture of an x86_64 system supports 64-bit addresses, but current implementations typically use 48-bit virtual addresses (the high 16 bits must be sign-extended from bit 47). With 4 KB pages (like our 32-bit example), the low 12 bits are still the page offset, which leaves us with 36 bits for the page number, which we break into four 9-bit chunks. These chunks serve as indices into a four-level page table hierarchy, often called the PGD (Page Global Directory), PUD (Page Upper Directory), PMD (Page Middle Directory), and PTE (Page Table Entry). Each 9-bit index allows 512 entries per table, and, with 8-byte entries, each table consumes 4 KB.

For example, the address 0x00007f3144816042 (a typical location for shared library code) is encoded in binary as

• 000000000011111110001100010010000010000000100100; thus,
  • The L4 (PGD) index bits are 000000000 or 0x000;
  • The L3 (PUD) index bits are 011111110 or 0x1FE;
  • The L2 (PMD) index bits are 001100010 or 0x062;
  • The L1 (PTE) index bits are 010000010 or 0x082;
  • The page offset bits are 000000100100 or 0x042.

Note that the high 16 bits (not shown) must be either all 0s or all 1s, matching bit 47, forming the “canonical form” required by x86_64. So we have a 256 TB virtual address space, split evenly between user and kernel space.

(When logged in, completion status appears here.)