Appearance
2.5.2 — Page Tables & the TLB
2.5.1 translated an address using a page table with three entries. Now make it real. On a modern 64-bit PC, a process's virtual addresses are 48 bits long. With 4 KB pages, the offset takes 12 of those bits, so the page number has 36 bits. That means a process could have
2^{36} = 68{,}719{,}476{,}736
pages, read "two to the thirty-sixth", about 69 billion. If the page table had one 8-byte entry for every possible page, a single process's table would take 2^{36} \times 8 bytes, which is 512 GB. For every process. On a laptop with 16 GB of RAM.
And there is a second problem. The page table lives in memory. If every memory access first had to read the page table from memory, every access would cost at least two trips to memory instead of one, and memory is already the slow part of the machine (1.6).
This page solves both problems. The first is solved by shaping the page table as a tree. The second is solved by a tiny, very fast cache inside the CPU, called the TLB.
1. A tree of small tables
The fix for the 512 GB table comes from one observation: almost all of a process's address space is empty. Our upload service uses perhaps a few hundred megabytes, in a handful of regions: its code, its heap, some libraries and its stack (2.2.1). The rest of its 128 TB of possible user addresses is never touched. A flat table would spend almost all its entries saying "nothing here".
So instead of one giant table, x86-64 processors use a tree of small tables, each exactly one page in size. Each table holds 512 entries of 8 bytes, which is 4,096 bytes. The 36-bit page number is cut into four pieces of 9 bits each, because 2^9 = 512. Each piece picks one entry in one level of the tree.
| Bits of the address | Used for |
|---|---|
| 39–47 (9 bits) | entry in the level-4 table, the top |
| 30–38 (9 bits) | entry in a level-3 table |
| 21–29 (9 bits) | entry in a level-2 table |
| 12–20 (9 bits) | entry in a level-1 table, the bottom |
| 0–11 (12 bits) | the offset inside the page |
Add them up: 9 + 9 + 9 + 9 + 12 = 48 bits, the whole address. This is called a multi-level page table. The top table's location is kept in a special CPU register. On x86 it is called CR3, and the kernel changes it every time it switches to a different process. That one register change is how "switch to that process's memory map" from 2.2.1 actually happens.
Walking the tree, by hand
Take a real-looking address from the upload service's heap: 0x00007f3a12345678. Here is a snippet that cuts it into its five pieces.
ts
// page-table-walk.ts — split a 64-bit virtual address into its four table indexes
function split(address: bigint) {
const offset = Number(address & 0xfffn); // (1) bits 0–11
const level1 = Number((address >> 12n) & 0x1ffn); // (2) bits 12–20, 9 bits each
const level2 = Number((address >> 21n) & 0x1ffn);
const level3 = Number((address >> 30n) & 0x1ffn);
const level4 = Number((address >> 39n) & 0x1ffn); // (3) bits 39–47, the top table
return { level4, level3, level2, level1, offset };
}
console.log(split(0x00007f3a12345678n));
console.log(split(0x00007f3a12345679n)); // the next byte
console.log(split(0x00007f3a12346000n)); // the next page
// Prints:
// { level4: 254, level3: 232, level2: 145, level1: 325, offset: 1656 }
// { level4: 254, level3: 232, level2: 145, level1: 325, offset: 1657 }
// { level4: 254, level3: 232, level2: 145, level1: 326, offset: 0 }(1)Thenafter a number makes it abigint, a TypeScript integer with no size limit. Ordinary numbers cannot hold 64-bit addresses exactly.0xfffis twelve 1-bits, so ANDing with it keeps the offset.(2)Shift right by 12 to drop the offset, then keep 9 bits with0x1ff, which is nine 1-bits. That is the level-1 index. Each higher level shifts 9 bits further.(3)The top 9 of the 48 bits select the entry in the level-4 table.
Now follow the walk the hardware does for the first address:
- Read
CR3to find this process's level-4 table. Take entry 254. It holds the physical address of a level-3 table. - In that level-3 table, take entry 232. It points to a level-2 table.
- In that level-2 table, take entry 145. It points to a level-1 table.
- In that level-1 table, take entry 325. It holds the frame number, plus the permission bits from 2.5.1.
- Attach the offset, 1656, to the frame. That is the physical byte.
The output also shows something important. The next byte, ...679, used exactly the same four entries; only the offset changed. The next page, ...6000, changed only the level-1 entry. Addresses that are close together share almost all of their path through the tree.
Why the tree saves so much memory
Lower-level tables only exist where they are needed. If no address in a whole region is in use, the entry above it simply says "nothing here", and the tables below it are never created.
Work it through for a process with a 10 MB heap and nothing else. 10 MB is 2,560 pages. Each level-1 table covers 512 pages, so the heap needs 5 level-1 tables. Those fit under 1 level-2 table, which fits under 1 level-3 table, under the 1 level-4 table. That is 8 tables of 4 KB each, about 32 KB, instead of 512 GB. Real processes have a few more regions, so their tables come to some megabytes, but never anything like the flat table.
Newer processors and kernels can also use a fifth level, extending addresses to 57 bits for machines with enormous amounts of memory. It works exactly the same way, one more 9-bit piece.
2. The price of the tree: four extra reads
The tree saved memory, but made the second problem worse. Finding one frame now takes four memory reads, one per level, before the program's real read can even start. If each came from main memory, that would be four trips of about 100 nanoseconds each, five times slower than an access with no translation. A CPU that does billions of memory accesses a second cannot afford that.
The CPU's ordinary caches help a little, because recently used page-table entries may still be cached. But the real fix is a dedicated cache just for translations.
3. The TLB: a cache of recent translations
Inside the CPU, next to each core, there is a small, extremely fast memory called the translation lookaside buffer, or TLB. It remembers recent translations: "virtual page 0x7f3a12345 is in frame such-and-such, with these permission bits". It is a cache, exactly like the memory caches in 1.6, but it caches translations instead of data.
On every memory access, the hardware does this:
- Check the TLB first. It is checked in parallel with other work, so a hit costs nearly nothing.
- On a TLB hit, the translation is already known. The access continues immediately.
- On a TLB miss, the hardware walks the page-table tree from Figure 1, which takes the four reads. Then it saves the result in the TLB, throwing out an older entry if the TLB is full.
How often does it hit? Almost always, for the same reason caches work: locality. Programs keep touching the same pages. A loop over an array walks through one page for 4,096 bytes before it moves to the next. Our heap address and the byte after it shared one translation. So typical programs hit the TLB far more than 99 % of the time, and virtual memory costs almost nothing in practice even though it sounds expensive.
TLB reach: how much memory the TLB can cover
A TLB is small. A typical modern core has a first-level TLB of a few dozen entries and a second level of one or two thousand (exact sizes vary between processor models). Multiply the number of entries by the page size, and you get the TLB's reach: how much memory it can translate without a miss.
| TLB entries | Page size | Reach |
|---|---|---|
| 1,536 | 4 KB | 6 MB |
| 1,536 | 2 MB | 3 GB |
With 4 KB pages, about 1,500 entries cover only 6 MB. A program that jumps randomly around a much bigger area, such as a database looking up rows in a 10 GB table, will miss the TLB constantly, and pay for a page walk on many accesses. That is the reason for the second row.
4. Huge pages
Pages do not have to be 4 KB. x86-64 processors also support pages of 2 MB and 1 GB, called huge pages. A 2 MB page is translated by stopping the walk one level early: the level-2 entry points straight at a 2 MB frame, and the last 21 bits of the address become the offset. A 1 GB page stops at level 3.
Huge pages help in two ways. Each TLB entry now covers 512 times more memory, so the same 1,536 entries reach 3 GB instead of 6 MB, as the table above shows. And a walk, when it does happen, is one level shorter.
They have costs too. A 2 MB page must be one continuous 2 MB block of physical memory, which can be hard to find on a machine that has been running a long time and whose free memory is in small pieces. And a program that touches one byte of a 2 MB page gets the whole 2 MB.
Linux offers them in two ways. A program can ask for them explicitly. Or the kernel can quietly use them where it can, called transparent huge pages. Large databases and virtual machines benefit most. Some databases, Redis among them, warn against transparent huge pages, because the kernel's background work to assemble 2 MB blocks, and copy-on-write of a whole 2 MB page after fork, can cause sudden pauses (2.2.2 showed Redis forking for snapshots).
5. What happens to the TLB on a context switch
Each process has its own page table, so each process's translations are different. When the kernel switches from process A to process B (2.2.1), the TLB is full of A's translations. Using them for B would be a disaster: B would read A's memory.
The simple solution is to throw the TLB away on every switch. Writing a new value into CR3 does exactly that, except for a few entries marked global, such as the kernel's own memory, which is the same in every process. Process B then starts with an empty TLB and misses on everything for a while, until its own translations build up. This is a big part of the hidden cost of a context switch.
Modern CPUs soften this with tags. Each TLB entry is labelled with a small number saying which process's address space it belongs to. On x86 this is called a process-context identifier, or PCID. Now the kernel can switch page tables without flushing: B's entries are used for B, A's sit unused until A runs again. When A comes back, some of its translations may still be there.
Threads of the same process share one page table (2.3.1), so switching between them needs no TLB change at all. That is one of the reasons a thread switch is cheaper than a process switch.
TLB shootdowns
There is one more cost, and it appears on machines with many cores. Suppose the upload service has threads on eight cores, and one thread frees a large buffer. The kernel removes that memory from the page table. But the other seven cores may still have the old translation in their TLBs. If they kept using it, they would read memory that now belongs to someone else.
So the kernel must interrupt every core that might have the old entry, and make each one remove it. This is called a TLB shootdown. It costs a few microseconds of interrupt work on every affected core. A program that keeps mapping and unmapping memory across many threads can spend surprising amounts of time in shootdowns. That is one reason good memory allocators avoid giving memory back to the kernel too eagerly (2.5.4).
What the interviewer will push on
"Why are page tables multi-level?" They are checking whether you can do the arithmetic. A 48-bit address space with 4 KB pages has 2^{36} pages; a flat table of 8-byte entries is 512 GB per process. A tree of 512-entry tables only creates the lower tables for regions in use, so a real process needs kilobytes to a few megabytes.
"How many memory accesses does a translation take?" Four on a TLB miss with 4-level tables, plus the data access itself. On a TLB hit, effectively none. The tell is mentioning CR3 as the starting point and the 9-bit split.
"What is the TLB, and what happens on a miss?" A cache of recent translations inside the CPU. On a miss, the hardware walks the page tables and saves the result. The strong answer explains why hits are almost universal: locality.
"What are huge pages, and when do they help?" 2 MB or 1 GB pages. They multiply TLB reach and shorten walks, so they help programs with large, randomly accessed memory, such as databases and virtual machines. Mention the costs: they need continuous physical memory, and transparent huge pages can cause latency spikes.
"Why is a process switch more expensive than a thread switch?" A process switch changes CR3, which flushes or at least sidelines the TLB, so the new process starts with misses. Threads of one process share a page table, so the TLB stays valid.
Something to volunteer that nobody asks for: TLB shootdowns. Freeing memory in a program with many threads makes the kernel interrupt every core that might hold the stale translation. It is a real, measurable cost that explains why allocators hold on to freed memory.
Recall
- A flat table for a 48-bit address space would be 512 GB per process, so x86-64 uses a multi-level page table: four levels of 512-entry, 4 KB tables, indexed by four 9-bit pieces of the address, plus a 12-bit offset.
CR3holds the top table's address. - Lower tables exist only for regions in use, so a process with a 10 MB heap needs about 32 KB of tables. Nearby addresses share almost their whole path.
- A walk costs four memory reads, so the translation lookaside buffer caches recent translations; TLB hits are near-universal thanks to locality, and a TLB miss walks the tree.
- TLB reach is entries × page size, only about 6 MB with 4 KB pages. Huge pages of 2 MB or 1 GB multiply reach, at the cost of needing continuous physical memory.
- A process switch changes
CR3, flushing or sidelining the TLB (PCID tags soften this); thread switches keep it. Unmapping memory used on several cores forces a TLB shootdown.
Self-test: Work out the size of a flat page table for 48-bit addresses. Split 0x00007f3a12345678 into its five pieces. Why does the next byte use the same four table entries? What is the TLB reach of 1,536 entries with 4 KB pages, and with 2 MB pages? Why does freeing memory in a many-threaded program cost time on other cores?
Quiz Bank
FoundationalWhy does the TLB exist, and what happens on a TLB miss?
Every memory access needs its virtual address translated, and a translation through four levels of page tables takes four memory reads. Doing that on every access would make memory several times slower. The translation lookaside buffer is a small, very fast cache inside the CPU of recent translations, so the common case, a TLB hit, needs no extra reads. On a TLB miss, the hardware walks the page-table tree from the top table named in CR3, finds the frame and its permission bits, uses it, and saves it in the TLB, evicting an older entry if needed. Locality makes hits the overwhelming majority.
FoundationalWhy are page tables arranged as a tree of levels instead of one flat table?
Because a flat table must have an entry for every possible page, used or not. With 48-bit addresses and 4 KB pages there are 2^{36} pages, and at 8 bytes per entry that is 512 GB per process. A multi-level page table splits the page number into pieces, each indexing a small table, and creates the lower tables only for regions that are actually in use. Since almost all of an address space is empty, real processes need only kilobytes to a few megabytes of page tables.
AppliedSplit a 48-bit x86-64 virtual address into its page-table indexes.
From the lowest bits up:
- Bits 0–11 are the offset inside the 4 KB page.
- Bits 12–20 index the level-1 table.
- Bits 21–29 index the level-2 table.
- Bits 30–38 index the level-3 table.
- Bits 39–47 index the level-4 table at the top. Each index is 9 bits, because each table has 2^9 = 512 entries. For
0x00007f3a12345678the pieces are level 4 = 254, level 3 = 232, level 2 = 145, level 1 = 325 and offset = 1656. Each index is computed by shifting right by 12, 21, 30 or 39 and keeping 9 bits.
InterviewWhat are huge pages, and what are their benefits and costs?
Huge pages are 2 MB or 1 GB pages instead of 4 KB. The walk stops one or two levels early, with the remaining address bits used as the offset. Benefits: each TLB entry covers 512 or 262,144 times more memory, so programs with large, randomly accessed memory, such as databases and virtual machines, miss the TLB far less, and walks are shorter.
Costs come in three kinds. A huge page needs one continuous block of physical memory, which can be hard to find after a long uptime. Memory is handed out in large units, so a little use can waste a lot. And the kernel's work to assemble huge pages automatically can cause pauses, which is why some databases recommend turning transparent huge pages off.
InterviewWhat happens to the TLB when the kernel switches between processes, and between threads?
Different processes have different page tables, so one process's cached translations must never be used by another. Switching processes means loading a new top-level table address into CR3, which traditionally flushes every non-global TLB entry, so the new process starts with misses. CPUs with address-space tags, PCID on x86, label entries by process so the kernel can switch without flushing, and a returning process may find some translations still cached.
Threads of the same process share one page table, so switching between them changes nothing in the TLB. That is a large part of why thread switches are cheaper than process switches.
StaffA service that builds and frees large buffers on 32 threads shows heavy time in the kernel, in functions related to flushing translations. Explain and suggest fixes.
Each time a large buffer is returned to the kernel, its pages are removed from the shared page table. Any of the 32 cores running the service's threads might still have those translations cached, so the kernel sends an inter-processor interrupt to each and makes it invalidate them: a TLB shootdown. With frequent allocate-and-free cycles across many threads, the shootdowns add up to real CPU time on every core and add latency to the threads they interrupt.
Fixes:
- Keep and reuse buffers instead of freeing them, for example with a buffer pool.
- Use an allocator that holds freed memory rather than returning it to the kernel immediately.
- Allocate per thread, so memory used by one thread is less likely to be cached on other cores.
- Avoid repeatedly mapping and unmapping large regions.
Huge pages can also reduce the number of entries involved.
Scenario Drill
DrillThe photo-upload service builds an in-memory index of 5 GB of photo metadata and looks entries up at random. It is much slower per lookup than the same code on a 50 MB index. Using this page, explain one hidden cause and one fix.
One hidden cause is TLB misses. With 4 KB pages, the TLB's reach is only a few megabytes. A 50 MB index fits largely in the TLB's view and the caches, but random lookups across 5 GB touch a different page almost every time, so nearly every lookup misses the TLB and pays a four-level page walk, each level itself possibly missing the CPU caches. Data-cache misses add to this, but the translation cost alone can be a large share.
One fix is huge pages: backing the index with 2 MB pages raises the TLB's reach to gigabytes, so far fewer lookups miss, and those that do take a shorter walk. Another is to improve locality, for example by laying the index out so related entries sit in the same pages. Measure both, since the effect depends on the access pattern.
Next: a page-table entry can say "not present", and the demand-paging demo in 2.5.1 showed the kernel filling pages in only as they are touched. Page 2.5.3 follows a page fault from start to finish, works out which page to throw out when RAM is full, and explains the failure every engineer meets eventually: thrashing.