-1

I am trying to calculate the number of page table levels that are required to support 35 virtual address bits.

The input is giving me: The paging unit uses 16B page descriptors and page size is 2KiB. The number of descriptors stored in a descriptor table is 128.

The correct answer that is given for the page table levels is 4.

I tried to calculate it using various methods but it doesn't work out.

I also tried this formula (virtual address space size)/(page size)

Could someone please help me?

CNSpary
  • 13
  • 4
noxeko9028
  • 1
  • 1
  • 128 = 2^7 entries in a table means each level handles 7 bits, of the page-number bits. Like how x86-64 uses 9 bits per level with 4 levels, for its 4k pages: [How do AMD64 page entry base address fields encode a 52-bit address in 40 bits?](https://stackoverflow.com/q/67167482). Remember you don't need to translate the offset-within-page bits. – Peter Cordes Jun 20 '21 at 16:03
  • still, I don't know how to go about solving this @PeterCordes could you please help further? – noxeko9028 Jun 20 '21 at 17:09

1 Answers1

1

The most generic formula is like:

total_virtual_address_bits <= bits_for_offset_in_page + levels * bits_per_page_table_index

This formula is derived from splitting a virtual address up into several fields.

You can plug your values in and see that it works:

35 <= 11 + 4 * 7
35 <= 39

You can also rearrange the formula:

total_virtual_address_bits <= bits_for_offset_in_page + levels * bits_per_page_table_index

total_virtual_address_bits - bits_for_offset_in_page <=  levels * bits_per_page_table_index

levels >= (total_virtual_address_bits - bits_for_offset_in_page) / bits_per_page_table_index

You can plug your values into this formula, like:

levels >= (35 - 11) / 7

levels >= 3.4285714

And here is the confusion part. The maths doesn't quite work perfectly (3.4285714 isn't a nice integer) so it gets rounded up.

This means that the highest level table will only be partially used (more specifically, we only need 3 bits for the index into the highest level page table, so only 8 entries in that table will be used and the other 120 entries will be wasted).

Note that this "rounding up" does happen in practice. One example was 32-bit 80x86 with PAE, where the highest level page table was only 32 bytes (and the size of page tables and page size where all 4 KiB).

Brendan
  • 35,656
  • 2
  • 39
  • 66