Page Table: From Virtual to Physical

Introduction

Hello, in this belong we’ll be talking about the page table and how linear (virtual) addresses are translated to physical addresses. To do this we’re going to have to go into depth about how memory is structured within your computer. This blog will talk about the software and hardware side of this topic.

Physical Memory

To begin with, we’ll need to be familiar with what physical memory is. Now, Physical Memory is the data stored on your RAM. In a paged memory system, your physical memory is split up into chunks referred to as pages. These pages are managed by the MMU (Memory Management Unit) which is a physical component of your CPU. This is also accompanied by the software side called VMM (Virtual Memory Manager). The page table contains a record of all the pages where it’s all managed, the page table maps virtual addresses (we’ll talk more about this soon) to physical addresses where the data is stored.

Linear/Virtual Memory

Now that we know more about physical memory, we need to discuss Linear Memory. Now, linear memory, as we know, is used in accordance with physical memory. We need to discuss more about why it’s used. The way it’s used is by the VMM. Every process is given its own virtual address space where the size varies depending on what architecture the process is using. In a 32-bit process, the virtual address space typically has a 2-gigabyte range of address space. This goes from 0x00000000 through to 0x7FFFFFFF. In a 64-bit process it’s vastly increased, it typically has a 128-gigabyte range of address space. This goes from 0x00000000000 through 0x7FFFFFFFFFFF. Two processes can have overlapping, or the same, virtual address but the data between both will be different as well as the physical address that backs that page, this is because every process has its unique directory base (cr3). The only times when a page table is shared is through shared memory or if it has a parent process (or an inverted page table but we won’t discuss that here).

Page Table

Okay, so we’ve discussed both virtual & physical memory. It’s time to now talk more about the page table and how it’s structured within Windows. We’ll be discussing the 4-level page table as we have no need currently to discuss any system larger than 64TB of RAM. aa 4-level paging system will be used to map linear addresses to physical addresses by using the bits of the linear address to specify quite a few different things.

4KB page : Offsets

To start lite, we’re going to be talking about the 4-kilobyte page using the 4-level paging system. This might look a little confusing at first but I will try my best to explain what exactly we’re looking at right now. As we can see at the top, the linear address is split up into multiple sections so let’s talk about it.

bits 0:11 are used as a page offset, we’ll label it as page_offset. This is used to dictate where the physical address is located in the page.
bits 12:20 are used as the table offset, we’ll label it as table_offset. This is used to dictate where the page table entry is.
bits 21:29 are used as the directory offset, we’ll label it as directory_offset. This is used to dictate where the page directory entry is
bits 30:38 are used as the directory pointer offset, we’ll label it as directory_pointer_offset. This is used to dictate where the page directory pointer entry is
bits 39:47 are used as the PML4 offset, we’ll label it as pml4_offset. This is used to dictate where the PML4 entry is. (PML4 stands for page map level 4)

4KB page : Entries

Now that we’ve discussed the offset side and how the virtual address is broken down into bits. We’ll now talk about how these offsets are used within this entire translation process in order to figure out the entries. The entries in this context refer to, essentially, what page this virtual address belongs to. This picture above will be referred to a couple of times. It might look confusing at first but, once again, I will try my best to explain the real simplicity of this image. To start off with, if we trace from the bottom up, we can see that the address of the 4KB page frame (the physical address of the page frame) is the base of the page. This is stored within the PTE (Page Table Entry). To get the page table entry we’d have to get the address of the page table which is stored in the PDE (Page Directory Entry). So with this being the common gist of how this is all structured and linked together, we’ll now show the path to get the PTE from the cr3 (control register 3).CR3->PML4E->PDPTE->PDE->PTE. Now what might be putting you off is, what’s the difference between the offsets and the entries? The entries are the actual entries of the current virtual address’ page that we’re trying to index. We already extracted all the offsets so we can apply this to the actual addresses that we extract from each entry. Since we’re essentially indexing, almost, an array we’re going to need to multiply each offset (index) by 8. Let’s start tracing this down now!

4KB page : CR3 to PML4E

let pml4_offset = //... extracted pml4 bits
// assuming we're in the process' context
let directory_base : cr3 = __readcr3();
// Add the pml4 index onto the page frame of the directory base
// The reason we shift left by 12 bits is because we need to append the first 12 bits that were extracted already
let pseudo_addr : u64 = (directory_base.page_frame.rotate_left(12)) + (pml4_offset * 8);
// read physical memory to get the pml4 entry
let pml4_entry : pml4e = read_physical_mem(pseudo_addr);

Voila, this is the general premise of how we get the entries of all the page table sections, let’s continue.

4KB page : PML4E to PDPTE

let pdpt_offset = //... extracted pdpt bits
let pml4_entry : pml4e = //... pml4e from previous calculation
// Add the pdpt index onto the page frame of the pml4e
let pseudo_addr : u64 = (pml4_entry.page_frame.rotate_left(12)) + (pdpt_offset * 8);
let pdpt_entry : pdpte = read_physical_mem(pseudo_addr);

4KB page : PDPTE to PDE

let pd_offset = //... extracted pd bits
let pdpt_entry : pdpte = //... pdpte from previous calculation
// Add the pd index onto the page frame of the pdpte
let pseudo_addr : u64 = (pdpt_entry.page_frame.rotate_left(12)) + (pde_offset * 8);
let pd_entry : pde = read_physical_mem(pseudo_addr);

4KB page : PDE to PTE

let pt_offset = //... extracted pt bits
let pd_entry : pde = //... pde from previous calculation
// Add the pt index onto the page frame of the pde
let pseudo_addr : u64 = (pd_entry.page_frame.rotate_left(12)) + (pt_offset * 8);
let pt_entry : pte = read_physical_mem(pseudo_addr);

4KB page : PTE to Physical Address

let page_offset = //... extracted offset bits
let pt_entry : pte //... pte from previous calculation
// Now that we've got the address offset and the pte
// we can just add that same offset onto the page frame of the PTE
// to get the physical address that the virtual address is associated to
let physical_address : u64 = (pt_entry.page_frame.rotate_left(12) + page_offset);

There we go, we’ve successfully translated a virtual address to a physical address in a 4kb page frame.

2MB page : Offsets

We’ve discussed a 4kb page, but what if the page is 2 MB large? This section of the blog will now detail if a page is 2 MB. The offsets extracted from the virtual address are different as seen in the image below. You’ll notice there is no table entry or offset, that’s because there is no need for it.

bits 0:20 are used as a page offset, we’ll label it as page_offset. This is used to dictate where the physical address is located in the page.
bits 21:29 are used as the directory offset, we’ll label it as directory_offset. This is used to dictate where the page directory entry is
bits 30:38 are used as the directory pointer offset, we’ll label it as directory_pointer_offset. This is used to dictate where the page directory pointer entry is
bits 39:47 are used as the PML4 offset, we’ll label it as pml4_offset. This is used to dictate where the PML4 entry is. (PML4 stands for page map level 4)

2MB page : CR3 to PML4E

let pml4_offset = //... extracted pml4 bits
// assuming we're in the process' context
let directory_base : cr3 = __readcr3();
// Add the pml4 index onto the page frame of the directory base
let pseudo_addr : u64 = (directory_base.page_frame.rotate_left(12)) + (pml4_offset * 8);
// read physical memory to get the pml4 entry
let pml4_entry : pml4e = read_physical_mem(pseudo_addr);

2MB page : PML4E to PDPTE

let pdpt_offset = //... extracted pdpt bits
let pml4_entry : pml4e = //... pml4e from previous calculation
// Add the pdpt index onto the page frame of the pml4e
let pseudo_addr : u64 = (pml4_entry.page_frame.rotate_left(12)) + (pdpt_offset * 8);
let pdpt_entry : pdpte = read_physical_mem(pseudo_addr);

2MB page : PDPTE to PDE

let pd_offset = //... extracted pd bits
let pdpt_entry : pdpte = //... pdpte from previous calculation
// Add the pd index onto the page frame of the pdpte
let pseudo_addr : u64 = (pdpt_entry.page_frame.rotate_left(12)) + (pde_offset * 8);
let pd_entry : pde = read_physical_mem(pseudo_addr);

2MB page : Understanding the PDE struct

This is where it gets different from translating a 4kb page frame. In the PDE struct you’ll notice that there are two different scenarios (excluding if the present bit is not set). The first scenario is if the page is 2mb in size, and the other scenario is if it’s just a regular 4kb page frame. This is dictated by the 8th bit at index 7.

2MB page : Obtaining a 2MB PA

So, you might be wondering now - how do we get the physical address of a virtual address within a 2MB page? Simple, we’ll have to convert the current PDE struct to a large one and just extract the page frame from it and shift it according to the 2MB structure.

let pd_entry : pde = //... pde from previous calculation
// Check if it's a large page
if pd_entry.page_size {
    // Convert to large pde struct
    let pd_entry_large : large_pde = large_pde::from_u64(pd_entry.raw_value);
    // extract the page offset
    let large_page_offset : u64 = (virtual_address & !((!0u64).rotate_left(21)));
    // get physical address
    let physical_address : u64 = (pd_entry_large.page_frame.rotate_left(21) + large_page_offset);
}

There we go, now we have the physical address of a 2MB page.

1GB page : Offsets

This is essentially going to be the same as 2MB, let’s get started!

bits 0:29 are used as a page offset, we’ll label it as page_offset. This is used to dictate where the physical address is located in the page.
bits 30:38 are used as the directory pointer offset, we’ll label it as directory_pointer_offset. This is used to dictate where the page directory pointer entry is
bits 39:47 are used as the PML4 offset, we’ll label it as pml4_offset. This is used to dictate where the PML4 entry is. (PML4 stands for page map level 4)

1GB page : CR3 to PML4E

let pml4_offset = //... extracted pml4 bits
// assuming we're in the process' context
let directory_base : cr3 = __readcr3();
// Add the pml4 index onto the page frame of the directory base
let pseudo_addr : u64 = (directory_base.page_frame.rotate_left(12)) + (pml4_offset * 8);
// read physical memory to get the pml4 entry
let pml4_entry : pml4e = read_physical_mem(pseudo_addr);

1GB page : PML4E to PDPTE

let pdpt_offset = //... extracted pdpt bits
let pml4_entry : pml4e = //... pml4e from previous calculation
// Add the pdpt index onto the page frame of the pml4e
let pseudo_addr : u64 = (pml4_entry.page_frame.rotate_left(12)) + (pdpt_offset * 8);
let pdpt_entry : pdpte = read_physical_mem(pseudo_addr);

1GB page : Understanding the PDPTE struct

Just like the 2MB page, this is similar with having three possible outcomes. Now since we know the specifics we’ll just get into what bit dictates what. For the PDPTE struct, it’s the same as a 2MB page. The 8th bit (7th index) being set to 1 will say that this is a 1GB page.

1GB page : Obtaining a 1GB PA

let pdpt_entry : pdpte = //... pdpte from previous calculation
// Check if it's a large page
if pdpt_entry.page_size {
    // Convert to large pdpte struct
    let pdpt_entry_large : large_pdpte = large_pdpte::from_u64(pdpt_entry.raw_value);
    // extract the page offset
    let large_page_offset : u64 = (virtual_address & !((!0u64).rotate_left(30)));
    // get physical address
    let physical_address : u64 = (pdpt_entry_large.page_frame.rotate_left(30) + large_page_offset);
}

Great, now we have the physical address of a 1GB page.

Conclusion

That wraps it all up, this is my take on translating linear addresses into physical and the methodology behind it. I do hope you enjoyed this blog and perhaps learned something new. This is not as detailed as how it works internally but it should give you a good idea. Any mistakes within my work I do apologise and would love for you to correct me! Thank you for reading!

References

Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3 (3A, 3B, 3C, & 3D): System Programming Guide

Introduction#

Physical Memory#

Linear/Virtual Memory#

Page Table#

4KB page : Offsets#

4KB page : Entries#

4KB page : CR3 to PML4E#

4KB page : PML4E to PDPTE#

4KB page : PDPTE to PDE#

4KB page : PDE to PTE#

4KB page : PTE to Physical Address#

2MB page : Offsets#

2MB page : CR3 to PML4E#

2MB page : PML4E to PDPTE#

2MB page : PDPTE to PDE#

2MB page : Understanding the PDE struct#

2MB page : Obtaining a 2MB PA#

1GB page : Offsets#

1GB page : CR3 to PML4E#

1GB page : PML4E to PDPTE#

1GB page : Understanding the PDPTE struct#

1GB page : Obtaining a 1GB PA#

Conclusion#

References#