# Page Table Size in a 4 Level Hierarchical Page Table

An Intel 64 bit CPU uses a four-level hierarchical page table. Each of the four levels of the page table can contain 512 entries, and the page table size is 4KB. You should be able to see that it cannot actually address 2^64 bytes of virtual memory. If a process on the system used 12MB of text, 5MB of heap and 7MB of stack, calculate the page table size, the number of page table entries required and the number of second level page tables.

Disclaimer: This question is not from an academic assessment. It is a past paper question in preparation for an examination.

If the page table size is 4096 bytes then $\log_2(4096) = 12$. Thus, the offset is 12 bits. Since there are 4 levels in this page table and each level can support 512 entries, the index into each entry is $\log_2(512) = 9$. Thus, you have 4x 9 bit indexes in the virtual address and a 12 bit offset.

One question arises: $9 * 4 + 12 = 48$ bits. But we have 64 bit virtual addresses? What happens to the other 16 bits? I would assume these are zeroed as the 16 most significant bits. Is that correct?

If this is true, does that mean this paging system can address 2^36 pages of virtual and physical memory, and therefore, it can address at most 2^48 bytes of virtual and physical memory. Is that correct?

Under the assumption outlined above: 12MB of text requires 3072 pages, 5MB of heap requires 1280 pages and 7MB of stack requires 1792 pages.

We know that the address space looks like this:

|----------| 2^36
|  Stack   | (Stack expands down)
|          |
|          |
|          |
|   Heap   | (Heap expands up)
|   Text   |
|----------| 0x0


Since the stack is at the top of the address space, it must have it's own second level page table. However, the program text and heap are at the bottom of the address space. Since each second level page table can address 512GB of memory (512^3 * 4096) the program text and heap can share a second level page table. Then, since each third level page table can address 1GB (512^2 * 4096) the program text and heap can share a third level page table too. Thus, we have 18 page table entries. Since this is a 64 bit architecture, each page table consumes 64 bits, and therefore the size of the page table is $18 * 512 * {64 \over 8} = 72KB$.

4th level can address $512 \times 4096$ bytes,

3rd level can address $512^2 \times 4096$ bytes,

2nd level can address $512^3 \times 4096$ bytes,

1st level can address $512^4 \times 4096$ bytes.

     L1       L2       L3       L4
2^32 |---|--->[---]--->[---]--->[---]   }
|---|                  --->[---]   }  7MB STACK
|---|                  --->[---]   }
|---|                  --->[---]   }
|---|
|---|
|---|
|---|
|---|                      L4
|---|                      |->[---] }
|---|                      |->[---] } 5MB HEAP
|---|    L2       L3       |->[---] }
0 |---|--->[---]--->[---]--->|
|->[---] }
|->[---] }
|->[---] } 12MB TEXT
|->[---] }
|->[---] }
|->[---] }

Key [---] Level in Page Table
---> Pointer to Lower Level Page Table


That is independent from the maximum physical address, which is not "canonical" in that way but just goes from 0 to some large number determined by MAXPHYADDR. You can find MAXPHYADDR using CPUID:80000008H, the lowest 8 bits in eax. It specifies the bit index in the page table entries (and some other places where you specify a physical address) at which the physical address stops and the reserved region begins. It's at least 36. It could be 48, but that wouldn't have anything to do with the limits on virtual addresses. The page table entry format allows it to go up to 52 (allowing you to address 4PB of RAM), but that hasn't happened yet. Intel seems to like 39 and 46, AMD seems to mostly use 48 now (they've used lower in the past) (source).