I am trying to understand what is a table walk. I have found when it occurs - whenever there is a TLB miss. If no descriptor is found – TLB miss occurs and further behavior depends on the implementation of a paging unit. (TLB - Translation look aside buffer)

But i still do not understand what exactly happens during table walk.


In present computers, the processor manipulates virtual addresses that are generated by the compiler, but the real physical address is determined at run time by the OS.

To do that, memory is organized in pages. Typical page size is 4kB (2^12bytes). To translate from virtual addresses to physical addresses, an address is considered as having two fields: address of a byte within a page (12 bits displacement) and page address (the remaining high order bits). Translation consists to replace virtual page address in he processor by physical address, with respect to a table generated at process creation by the OS (page table).

The problem is that these table can be HUGE. With 64bits virtual addresses (as in present processors), this page address have (64-12)bits (for 4kB pages) and a page table will hold 2^52 page addresses. This is an insane size (~10^18B) largely above most computer physical memory size. Fortunately, these tables are mostly empty and only a small part of potential virtual addresses have a physical translation.

To cope with that, page tables are multi level. Virtual addresses are split in fields addressing the successive table levels. For instance, with a 4kB page, and 64bits (8B) addresses, it is possible to store 512(2^9) addresses per page. The first 9 high order bits select an address within a page, that will give the address of a new page holding 512 page address. The next 9 high order bits select a new page, and so on.

If a page address is 52 bits in at most 6 steps, we can get the final physical page address corresponding to a logical page address.

This "page walk" or "table walk" is a complex process that requires several memory accesses and that must be done for every memory access.

To reduce the translation time, the TLB memorize recent correspondences between virtual and phys page addresses. If the physical translation of a virtual address is in the TLB, it is immediately available.

And if translation is not in the TLB, it is recreated by table walk. TLB misses (and table walk) are very expensive. If all the page tables are already copied to cache memory, it will require some tens of cycles. But if the TLB miss also implies cache misses, the time will be measured by hundreds of cycles.

There are several good tutorials on these problems. Look for instance at the wikepedia page that give good graphical illustrations of table walk. https://en.wikipedia.org/wiki/Page_table


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.