the TLB miss and the page-walk

When the TLB does not hold the translation you need, the answer is not lost — it just has to be looked up the slow way, by reading the page tables themselves. This lookup is called the page-walk, and on a TLB miss the CPU's hardware page walker performs it automatically before the original memory access can complete. It is the price of a TLB miss, and understanding it explains why TLB misses can hurt so much more than ordinary cache misses.

Page tables are not one flat table — that would be enormous. They are a multi-level tree. On x86-64 with 4 KiB pages there are four levels (the page-map-level-4 down through the page directory and page table), so translating one virtual address means following four pointers, each read from memory: read level 4 to find level 3, read level 3 to find level 2, and so on, until the final entry gives the physical page frame. That is up to four dependent memory accesses just to translate ONE address before you can even touch the data you wanted. Each of those accesses can itself hit or miss in the data caches, so a worst-case walk is several DRAM round-trips. The successful translation is then inserted into the TLB so the next access to that page is fast.

This is why TLB misses are insidious: an ordinary cache miss costs one trip to a lower level, but a TLB miss can cost a whole pointer-chasing walk through up-to-four cache-able levels, and only THEN the actual data access. Programs that touch a huge address range with poor page locality spend real time in page-walks. The cures are the same as for TLB pressure generally — improve locality so you reuse a small set of pages, or use huge pages so each TLB entry (and each walk) covers far more memory, and the tree is shallower per byte mapped.