0

From https://cs.stackexchange.com/questions/119744/how-does-a-tlb-lookup-compare-all-keys-simultaneously and https://en.wikipedia.org/wiki/Content-addressable_memory, look-up a key in TLB could be paralleled.

What about look-up operations in a page-table? Is it supposed to be linear?

p.s. Given page-tables are stored in RAM [1] (not CAM), and hash tables are used to speed up inverted-page-table look-up, it seems look-up operations in a page-table is at least not taking constant time (constant in terms of the number of entries in a page-table). Still I wonder if it's a common sense that page-table look-ups are performed by comparing input with each row linearly, or this information is documented in (x86) hardware spec or manual.

[1] https://stackoverflow.com/questions/56619431/where-is-page-table-located#:~:text=In%20x86%20systems%2C%20page%20tables,they%20are%20kept%20in%20RAM.

minglotus
  • 83
  • 6
  • Page table look ups are array element references, so array indexing. Subject to cache misses, but they are not scans, not linear scans. – Erik Eidt Apr 17 '22 at 22:11

1 Answers1

2

Page table indexing does not involve any search: the index for each level of the page table is given by some bits of the linear address. So RAM is exactly the right structure to use.

Searching based on page table content is not just unnecessary but also impossible, since the contents of an entry do not identify the linear address that the entry corresponds to.

Diagram from Intel Software Developer's Manual volume 3:

4-level paging, 4KB pages

harold
  • 61,398
  • 6
  • 86
  • 164
  • > the index for each level of the page table is given by some bits of the linear address. Ahh how come I forgot this.. thanks for the correction! – minglotus Apr 17 '22 at 22:11
  • @minglotus: Page tables are basically a [radix tree](https://en.wikipedia.org/wiki/Radix_tree), with the keys implicit by position. – Peter Cordes Apr 17 '22 at 22:38