Skip to content

Volume ITechnology

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 addressUsed 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) The n after a number makes it a bigint, a TypeScript integer with no size limit. Ordinary numbers cannot hold 64-bit addresses exactly. 0xfff is twelve 1-bits, so ANDing with it keeps the offset.
  • (2) Shift right by 12 to drop the offset, then keep 9 bits with 0x1ff, 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:

  1. Read CR3 to find this process's level-4 table. Take entry 254. It holds the physical address of a level-3 table.
  2. In that level-3 table, take entry 232. It points to a level-2 table.
  3. In that level-2 table, take entry 145. It points to a level-1 table.
  4. In that level-1 table, take entry 325. It holds the frame number, plus the permission bits from 2.5.1.
  5. Attach the offset, 1656, to the frame. That is the physical byte.
CR3level 4entry 254level 3entry 232level 2entry 145level 1entry 325frame+ 1656four memory reads to find one frame; each table is one 4 KB page of 512 entries
Figure 1 — A page-table walk. The CR3 register points to the top table. Each 9-bit piece of the address picks one entry, which points to the next table down. The last entry gives the frame; the offset is added to find the 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:

  1. Check the TLB first. It is checked in parallel with other work, so a hit costs nearly nothing.
  2. On a TLB hit, the translation is already known. The access continues immediately.
  3. 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 entriesPage sizeReach
1,5364 KB6 MB
1,5362 MB3 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. CR3 holds 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:

  1. Bits 0–11 are the offset inside the 4 KB page.
  2. Bits 12–20 index the level-1 table.
  3. Bits 21–29 index the level-2 table.
  4. Bits 30–38 index the level-3 table.
  5. 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 0x00007f3a12345678 the 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:

  1. Keep and reuse buffers instead of freeing them, for example with a buffer pool.
  2. Use an allocator that holds freed memory rather than returning it to the kernel immediately.
  3. Allocate per thread, so memory used by one thread is less likely to be cached on other cores.
  4. 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.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet