So a page table entry contains the physical page address in memory, some bits like dirty/valid/use bit and maybe some unused bits correct?

Given a system that can be 32 bits, or 64 bits, or even 128 bits (theoretically speaking of course), how do you determine the size of each page table entry?

As a follow-up question, how many levels of page tables, if a red-black, radix tree structure is used for the paging scheme, are needed?

1

There are 1 answers

3
user22405329 On BEST ANSWER

You look up that information in the manual for the specific system.

There is no direct relationship between the bitness of the system, and the sizes you've mentioned. There is a lot of leeway for the hardware designers to decide.

Page table entry has to be as long as needed to store all necessary information. It depends on the functions the MMU supports, and on the width of the physical address (which might be different from the stated "bitness" of the CPU, different from the size of the registers and the virtual address!). For example:

  • Intel 80286 is a 16 bit CPU. Its "page table" (called Descriptor table - but serves a similar function) has entries of... 64 bits! Why? Because its physical address is 24 bits, and it also allows pages of arbitrary size, down to a byte! So it has to store full 24 bit address and a 16 bit size field!
  • Most systems require pages to be a specific size, and also aligned on that size - that allows to reuse some bits of the address, that would be 0 otherwise.
  • 32 bit x86 with PAE extension can have up to 51 bits of physical address - despite being a 32 bit system. Its page entry is 64 bits long.

Number of levels has even more leeway. We start from virtual address bitsize (which can be smaller than the stated bitness - 64-bit CPUs currently have less than 64 virtual address bits!) and subtract the page offset bitsize (which depends on the minimal page size), and we get page index size - but how to split it between layers is entirely up to an architecture designer!

  • Ultimately, it goes down to a page table size. In x86, page tables must be the size of a minimal page (4kiB), but there is no law that that must be the case on other systems. A system designer can pick a size smaller or bigger.
  • Uneven splits are also possible. A 32-bit x86 with PAE uses a (2, 9, 9) split of index bits - where the top page contains just 4 entries and has a size of 32 bytes!