TLBs and Page Table Walks

A translation lookaside buffer, or TLB, is a small cache of recent address translations. Without one, every load, store and instruction fetch would need several extra memory reads just to find out where to go, which would make virtual memory far too slow to use. Because programs have strong locality, a few dozen entries catch nearly all accesses. This article explains how a TLB works, what its reach is and why that matters, what a miss costs, and how the entries are kept correct across context switches and multiple cores.

12 min read | Intermediate

What You'll Learn

• Explain what a TLB stores and how a lookup works
• Calculate TLB reach and explain why superpages help
• Estimate the cost of TLB misses on average access time
• Explain ASIDs, sfence.vma and TLB shootdown

The Problem

Page Tables and Address Translation showed that translating one address under Sv32 takes two memory reads, and 64-bit schemes take three or four. Every instruction needs at least one translated access, for its fetch. If a walk happened each time, memory traffic would triple at least, and a program would run several times slower.

But translations have strong locality. A page holds 4 KB, so a thousand accesses in a row often stay in the same page, and only need the same translation. Remember the last few translations, and nearly all accesses need no walk at all.

What a TLB Is

A TLB is a small cache whose "data" is a translation. An entry holds a virtual page number as its tag, plus the physical page number and permission bits:

The lookup happens on every memory access, usually in the same cycle as the first-level cache lookup, so a TLB must be very fast. First-level TLBs are often fully associative, so the page number is compared with all the entries at once. That is practical because they are tiny: 32 to 64 entries is typical. Because a full walk is expensive, a TLB also needs a very high hit rate, and full associativity avoids conflict misses. The organization follows the same ideas as a data cache, with a line size of one translation.

Modern cores have separate instruction and data TLBs, for the same reason they have separate L1 caches, and a larger shared second-level TLB of a thousand or more entries behind them. That L2 TLB is usually set-associative, takes several cycles, and it saves most misses from needing a full walk.

Reading a TLB Entry

Besides the PPN, an entry stores the permission bits, so the checks in Page Tables and Address Translation take no extra time. It also stores the size of the page, if superpages are supported, and the dirty and accessed state. The first store to a clean page has to go through the slower path, to set the D bit in the table, after which the entry is updated.

How Well TLBs Work

A model on six small programs shows the idea. These programs touch only 1 to 3 pages of 4 KB, so even a tiny TLB is enough:

With one entry, a program bounces between its code page and its data page, as well as between source and destination. With two, nearly all the misses go. Real programs touch thousands of pages, of course, so real TLBs need more entries, but the same effect holds: a small table covers the current working set of pages.

TLB Reach

The memory a TLB can cover without a miss is its reach:

TLB reach = number of entries x page size

With 64 entries and 4 KB pages, the reach is 256 KB. That is much less than a typical L2 cache, and tiny against a data set of gigabytes. A program looping over 10 MB of memory with 4 KB pages will often miss the TLB, even when the data itself is in the cache. For large-memory workloads, TLB misses can take a noticeable share of the run time.

Superpages are the main remedy. One entry mapping a 2 MB or 4 MB page covers as much as 512 or 1,024 small entries. 64 entries of 4 MB reach 256 MB. Large databases and virtual machines are often configured to use them, and the performance gain can be several percent or more. The drawback is that the OS must find large contiguous blocks of physical memory, and it wastes memory if a huge page is only partly used. Why Virtual Memory calls that internal fragmentation.

What a Miss Costs

On a miss, the hardware page table walker reads the tables, level by level, and fills in the TLB. The cost depends on where the PTEs are. Since page tables live in ordinary memory, they can be cached. A walk that hits in the L2 cache may cost tens of cycles. A walk that misses all the caches costs hundreds, at each level.

In AMAT terms, translation adds a term:

extra cycles per access = TLB miss rate x walk time

Take a TLB miss rate of 0.5 percent and a 40-cycle walk, as assumptions for this example. That adds 0.2 cycles per access on average, a small cost for all the benefits. At a 5 percent miss rate, it adds 2 cycles. A system with a poor TLB hit rate can lose a lot, which is why TLB behavior is measured so carefully.

Designers reduce walks in other ways too. Page walk caches remember the upper levels of the tree, so that a walk in Sv48 can often skip straight to the last level. On a large core, several walks can run at once.

A TLB Miss Is Not a Page Fault

The two are often confused. A TLB miss means the translation isn't in the TLB. It may well be in the page table, and the hardware finds it without any software noticing, in tens of cycles. A page fault means the table itself has no usable entry. That raises an exception, and the OS handles it, in thousands of cycles or millions if the disk is involved.

Context Switches and ASIDs

A TLB entry is only correct for one address space. When the OS switches to a different process, the same virtual page means something else. The simple approach is to flush the entire TLB on every switch, but then each new process starts cold, and pays a miss for every page it touches.

The better way is to tag each entry with an address space identifier (ASID), a small number the OS gives to each process. A lookup matches both the page number and the ASID. Now entries for several processes can live in the TLB together, and a switch needs no flush. In RISC-V, the ASID is a field in satp, 9 bits in Sv32 and up to 16 bits in the 64-bit schemes. Pages marked global with the G bit, such as the kernel's, match any ASID, so they survive switches.

Keeping the TLB Correct

A TLB is a cache of a table in memory, but unlike a data cache, it is not kept up to date by hardware. When the OS changes a page table entry, a stale copy may remain. So the OS must tell the hardware, with sfence.vma. With no arguments it applies to everything. With a virtual address and an ASID it can remove a single entry, which is much cheaper, since it does not throw away the rest.

A change to a mapping that gives more access is mostly harmless, because a stale entry just causes a page fault that fixes itself. A change that removes access is dangerous, since a stale entry would let a program go on using a page that is now someone else's. So the OS must finish the flush before it reuses the frame.

TLB Shootdown

With several cores, it is harder. Each core has its own TLB, and sfence.vma only affects the core that runs it. If a process has threads on four cores, and one unmaps a page, the OS must interrupt the other three, make them flush the entry, and wait for them to finish. This is a TLB shootdown. It is expensive: each interrupted core stops what it is doing, and the initiating core has to wait. Large servers with many cores can spend real time on this. Some processor designs offer instructions that broadcast the invalidation in hardware, without any interrupts.

What About the Instruction Side?

Fetching instructions needs translation too, and it behaves differently. Code has very strong locality, and a program's hot code often fits in a few pages, so the instruction TLB can be smaller. A miss there, however, stalls the front end of the pipeline, with nothing in the instruction queue to keep going, and the cost is felt at once. Large server programs with megabytes of code sometimes remap their code onto huge pages, purely to reduce instruction TLB misses.

Common Mistakes