CODEWITHSUNDEEP
x86cpu-architecturepage-tables
minglotus
minglotus

Reputation: 93

Page table look-up vs TLB look-up

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.

Upvotes: 0

Views: 549

Answers (1)

user555045
user555045

Reputation: 64904

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

Upvotes: 2

Related Questions