2
$\begingroup$

The question is in context to multilevel page table. I was trying to solve numerical on multi-level paging and noticed that page size might not be same at all levels. I came across the point "Outer level page tables need not be page aligned to inner page tables".

Question 1: Does this mean that outer level page tables need not have same page size as inner page tables?

Question 2: If the sizes at different levels of paging are different, then will an outer page table's entry have to contain the exact frame address, i.e., frame number + offset, because page sizes are different across all levels?

$\endgroup$
2
$\begingroup$

Having different subtable sizes for different levels of a multilevel page table just means that a different number of bits from the virtual address will be used. The size of each level's subtable is independent of the sizes of subtables in other levels. (Yes, "outer level page tables need not have same page size as inner page table".)

Each subtable would be aligned to its size and pointers to that table in earlier levels could exploit this to elide zero bits in the address. The index would still be provided by the selection of virtual address bits. (No, outer page tables entry will not have to contain frame number + offset.)

For example, with a 47-bit virtual address space with a 50-bit physical address space (8-byte PTEs), an 8 KiB subtable with entries pointing to a 16 KiB subtable whose entries point to a 64 KiB subtable that points to 8 KiB pages:

root 8KiB subtable entry physical address
   PA[49:13] = root_pointer[39:0]
   PA[12:03] = VA[46:37] // 8 KiB subtable index
   PA[02:00] = 000       // PTE is 8-byte aligned
16 KiB subtable entry physical address
   PA[49:14] = pointer_to_16KiB_subtable[38:0]
   PA[13:03] = VA[36:26] // 16 KiB subtable index
   PA[02:00] = 000
64 KiB subtable entry physical address
   PA[49:16] = pointer_to_64KiB_subtable[36:0]
   PA[15:03] = VA[25:13] // 64 KiB subtable index
   PA[02:00] = 000
page address
   PA[49:13] = PTE_in_64KiB_subtable[36:0]
   PA[12:00] = 0_0000_0000_0000  // 8 KiB aligned page

The above example assumes a fixed size associated with each level. With variable sizes, the size of the targeted subtable would have to be included with its pointer.

The subtable size could be determined by a subtable size number such that three bits would support eight different subtable sizes or using a single extra bit with the size boundary marked by the first set bit starting from the least significant bit (e.g., aa...aa_1000 would indicate a subtable eight times larger (three bits before the set bit) than the smallest size supported). The former allows additional alignment bits of larger subtables to be used to extend the physical address space or provide more metadata; the latter saves bits (two in the example) that can be used for metadata or larger physical addresses even for the smallest subtables. Supported subtable sizes could also be dependent on the level of the subtable or even the sizes (or other metadata provided) in previous levels, though that seems inappropriately complex.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.