Are page table walks cached?

Question

On a microprocessor with hardware TLB management (say an Intel x86-64) if a TLB miss occurs and the processor is walking the page table, are these (off-chip) memory accesses going through the cache hierarchy (L1,L2,etc.)?

Answer 1

Yes, as far as I can tell, on Intel x86-64 processors, when a TLB miss occurs and the processor is walking the page table, those off-chip memory accesses go through the cache hierarchy.

I'm still a little fuzzy on a few details, and I hope some other answer will fill them in -- isn't there an Intel or AMD manual that describes the page walk in excruciating detail? My understanding is that:

• The virtual address in some address register is first handed off to a fast TLB to be converted to a physical address -- the address in the PC is handed off to the L1 ITLB, the address in any other register is handed off to the L1 DTLB.
• If that first lookup misses, there another level of slower, larger TLB that is attempted. (Is this L2 TLB split into a ITLB and a DTLB also, or is it a unified TLB cache? Are there further TLB levels -- L3 ? L4 ?)
• If the TLB lookup completely fails, and the x86 and x86-64 VHPT walker is disabled, the CPU signals a TLB miss fault, which is intercepted by the OS kernel. My understanding is that practically all non-x86 CPUs do the same thing -- handle TLB misses entirely in software. If enabled, x86 and x86-64 processors have hardware-assisted VHPT table walker that handles the next few steps. (Do the x86 and x86-64 chips have one bit that entirely disables VHPT, or are there many bits that can enable VHPT for some address ranges and disable VHPT for other address ranges? Where are those bits located?)
• if the TLB lookup completely fails, the original (probably user-mode) virtual address V1 is converted to V2, the virtual address of the page table entry PTE that holds the physical page number for V1.
• Because V2 is again a virtual address, the CPU goes through the normal virtual-to-physical address translation, except it skips L1 and goes right to L2.
• The hardware looks up virtual address V2 in the TLB in parallel with fetching that PTE from the (virtually-indexed) L2 cache.
• Because V2 is not the address of an instruction, it does not go through the L1 instruction cache; and because V2 is not the address of normal user data, it does not go through the L1 data cache. V2 is fed initially into the L2 unified cache (a unified instruction+data+PTE cache). See the "cache hierarchy example".
• If the L2 cache (or L3 or any other virtually-indexed cache) contains the PTE, then the VHPT fetches the PTE from cache memory and installs the PTE for V1 in the TLB, and the physical address in that PTE is used to translate the original virtual address V1 into the physical RAM address, eventually fetching that data or instruction entirely in hardware without any assistance from the OS.
• If all levels of virtually-indexed cache fail, but this second TLB lookup succeeds for V2, then the VHPT fetches the PTE from physically-indexed cache or from main memory, installs the PTE for V1 in the TLB, and the physical address in that PTE is used to translate the original virtual address V1 into the physical RAM address, eventually fetching that data or instruction entirely in hardware without any assistance from the OS.
• If this second TLB lookup fails, the hardware VHPT walker gives up with a VHPT TRANSLATION FAULT.
• When a VHPT TRANSLATION FAULT occurs, the CPU traps to the OS. The OS has to figure out what went wrong and fix things up:
• (a) perhaps the page containing V2 is currently swapped-out to disk, so the OS reads it into RAM and re-starts the failed instruction, or
• (b) perhaps a buggy program is trying to read or write or execute some invalid location, and the OS terminates the process, or
• (c) a variety of other tricks the OS writers do to use this mechanism to trap various kinds of access -- load the page containing V1 which may be swapped-out to disk; various traps used to debug new programs; to simulate "W^X" on CPUs that don't directly support it; to support copy-on-write; etc.

The diagram on page 2 of Thomas W. Barr, Alan L. Cox, Scott Rixner. "Translation Caching: Skip, Don’t Walk (the Page Table)" that draws a line between "Entries stored by MMU cache" and "entries stored by L2 data cache". (This may be a useful paper for people designing new CPUs, which is totally on-topic for "Electronics design").

Stephane Eranian and David Mosberger. "Virtual Memory in the IA-64 Linux Kernel" and Ulrich Drepper. "What every programmer should know about memory" (This may be a useful paper for people writing operating systems that deal with the IA-64 page table, which is a bit off-topic for ED -- perhaps Stack Overflow with the "operating-system" tag or the "osdev" tag or the OSDev.org wiki would be a better place for that topic ).

Table A-10 on Page 533 of Intel. "Intel® 64 and IA-32 Architectures Software Developer’s Manual" "PAGE_WALKS.CYCLES ... can hint at whether most of the page-walks are satisfied by the caches or cause an L2 cache miss."

Answer 2

I tend to agree that this belongs in a computer architecture stackexchange, not an electronics stackexchange, but since this is here:

@davidcary is correct.

Some history:

Intel x86 page table walks were NOT cached all the way up to P5, aka Pentium. More precisely, the page table walk memory accesses were not cached, bypassed the cache. Since most machines up to that time were write-through, they received values consistent with the cache. But they did not snoop the caches.

P6, aka Pentium Pro, and AFAIK all subsequent processors page table walks were allowed to access the cache, and to use a value pulled from the cache. Thus, they worked with write-back caches. (You could of course place the page tables in uncacheable memory, defined, e.g. by the MTRRs. But that is a big performance loss, although it can be useful for debugging OSes.)

By the way, this "page table walk memory accesses may access the data caches" is separate from "page table entries may be stored (cached) in a TLB Ttranslation Lookaside Buffer)." On some machines the TLB is called a "Translation Cache".

Another related issue is that interior nodes of the page tables may be cached in still more TLB-like datastructures, e.g. the PDE-cache.

One key difference: the data cache is coherent, and snooped. But the TLB and PDE caches are not snooped, i.e. are not coherent. The bottom line is that, since the page tables may be cached in noncoherent TLBs and PDE caches, etc., software must explicitly flush either individual entries or bulk groups (like, the entire TLB), when page table entries that may have been so cached are changed. At least when changed in a "dangerous" way, going from RW->R->I, or changing addresses.

I think that is fair to say that every time a new type of non-coherent TLB-like caching has been added, some OS has broken, because it had implicit assumptions that this was not being done.