Why using hierarchical page tables?

Question

I'm learning the Linux kernel and reading the book The Linux Kernel.

Can anybody explain why can't we just use the table which maps directly between logical and physical memory instead of the tree-like multilevel structure?

Added:

The total number of entries needed is fixed, so I assume that it's more space wasting to store a complicated structure than a simple one.

Chuipek

Answer 1

You will appreciate the space optimization of multi-level page tables when we go into the 64-bit address space.

Assume you have a 64-bit computer ( which means 64 bit virtual address space ), which has 4KB pages and 4 GB of physical memory. If we have a single level page table as you suggest, then it should contain one entry per virtual page per process.

One entry per virtual page – 2⁶⁴ addressable bytes / 2¹² bytes per page = 2⁵² page table entries

One page table entry contains: Access control bits ( Bits like Page present, RW etc ) + Physical page number

4 GB of Physical Memory = 2³² bytes.

2³² bytes of memory/2¹² bytes per page = 2²⁰ physical pages

20 bits required for physical page number.

So each page table entry is approx 4 bytes. ( 20 bits physical page number is approx 3 bytes and access control contributes 1 byte )

Now, Page table Size = 2⁵² page table entries * 4 bytes = 2⁵⁴ bytes ( 16 petabytes ) !

16 petabytes per process is a very very huge amount of memory.

Now, if we page the pagetable too, ie if we use multi level page tables we can magically bring down the memory required to as low a single page. ie just 4 KB.

Now, we shall calculate how many levels are required to squeeze the page table into just 4 KB. 4 KB page / 4 bytes per page table entry = 1024 entries. 10 bits of address space required. i.e 52/10 ceiled is 6. ie 6 levels of page table can bring down the page table size to just 4KB.

6 level accesses are definitely slower. But I wanted to illustrate the space savings out of multi level page tables.

Wigeon

Could u plz explain the detail on the space cost of paging? – Chuipek

@ymfoi I've completely rephrased my answer to explain you clearly the space optimizations. – Wigeon

Hello, @PavanManjunath. I am studying an operating systems course and this obviously came up in class. I am still confused about the advantage that multi level paging offers. Please explain this: 1. Is there an underlying assumption that the physical memory also uses a 64 bit address space? 2. Can you do the calculation for two level paging so that the gradual improvement is visible? Thanks for the above answer! 😁 – Barbarous

I think using multilevel paging does not save the potentially large memory space used by the page table if the program actually uses all the 2^64 virtual address space. Instead, it removes the need to allocate a huge page table contiguously upfront, and also allows the possibility to lazily create the mappings when needed. – Toro

x86-64 PTEs are 8 bytes each, so they have room for up to 52-bit physical page addresses. 64-bit virtual address-space with 4K pages doesn't make much sense with such small PTEs. Also note that x86-64 virtual addresses are only 48-bit (4 levels of page tables, each translating 9 bits) or 57-bit (5 levels.) Why in x86-64 the virtual address are 4 bits shorter than physical (48 bits vs. 52 long)? . Some other 64-bit ISAs allow larger pages, but are broadly similar in limiting physical and virtual addresses to less than 64. – Jinn

Your overall point is correct that a flat array of PTEs isn't usable; even for 32-bit x86 is would take 4 MiB per process, which is a lot to waste even today, and would have been totally unacceptable when 386 was new and that was more total RAM than some systems had. – Jinn

Answer 2

http://en.wikipedia.org/wiki/Page_table#Multilevel_page_table is to overcome the Inverted page table's pitfalls.

Thymic