BUAA OS 2023 Spring

We use mutiple levels of pages to manage virtual memory, but how does it work?

Basic Concepts

Before we start, there are some concepts that we should be aware of:

  • In 32 bit operating system, virtual memory is $4GB$ ($2^{32}$B).
  • Usually, page size is 4KB, so it require $4G \div 4K = 1M$ page table entry, one page table entry is $4B$, so one process need $4MB$ space to store page table. Therefore, the virtual memory is aligned in $4M$ to make mapping esier.
  • The space of page table is mapped to $4G$ virtual memory together with the program. Since $4M$ page table describes all $4GB$ virtual memory, there is one special page that will be mapped to the $4M$ virtual memory that stores page table, which is the so-called page directory.
  • For 2-level page table, the 1 level is called page directory. One page directory covers $1K$ page table, while $1K$ page table covers $1K \times 4KB = 4MB$ virtual memory. So there are $1K$ page directory, which precisely occupy one page.

Page Table in Virtual Memory

Here is a really good figure to show the mapping mechanism.

Self Mapping

Notice that, page directory and page table all comes from the red $4M$ space in virtual memory.

Be careful about the mapping relationship.

Page Table Base

$PT_{base}$ is assigned by OS, and is fixed. The $4M$ space after it is the page table.

Page Directory Base

$PD_{base}$ is mapped to $PT_{base}$, the $4K$ space after it is the page directory, which covers the $4M$ page table in virtual memory.

To calculate $PD_{base}$, we just need the offset of it from $PT_{base}$. There are two ways to understand this.

One page table entry ($4B$) covers $4K$ virtual memory, so we just need to find how many $4K$ are there before $PT_{base}$.
$$
PD_{offset} = (PT_{base} >> 12) << 2
$$
$$
PD_{base} = PT_{base} + PD_{offset} = PT_{base} + (PT_{base} >> 10)
$$

One page directory covers $4M$ virtual memory, and since virtual memory is aligned with $4M$, it is easy to get how many page directories are there before $PT_{base}$. The number of PD is just the number of $4K$ in $PD_{offset}$.
$$
PD_{count} = PT_{base} >> 22
$$
$$
PD_{offset} = PD_{count} << 12
$$

$$
PD_{base} = PT_{base} + PD_{offset} = PT_{base} + (PT_{base} >> 10)
$$

Page Directory Self Mapping

Similar to $PD_{base}$ in page table, which is mapped to $PT_{base}$, there is an entry called $PDE_{self-mapping}$ in page directory which is mapped to $PD_{base}$.

So, with similar idea, we want to find the offset from $PD_{base}$ to $PDE_{self-mapping}$. Through carefully ovservation, we can find that the number of $PDE$ before $PDE_{self-mapping}$ is the number of $4K$ in page table before $PD_{base}$. Furthermore, the number of $4K$ in page table before $PD_{base}$ is exactly the number of $4M$ in virtual memory before $PT_{base}$! What an amazing coincidence! (I guess this is the benefit of $4MB$ alignment.)

So the solution is easy.
$$
PDE_{count} = PT_{base} >> 22
$$

$$
PDE_{self-mapping} = PD_{base} + (PDE_{count} << 2) = PD_{base} + (PT_{base} >> 20)
$$

We can substitute $PD_{base}$ here.
$$
PDE_{self-mapping} = PT_{base} + (PT_{base} >> 10) + (PT_{base} >> 20)
$$

Page Table in Physical Memory

Above is how page table is represented in virtual memory as virtual address. Program, or more directly, CPU send instructions with virtual address, which is then intercepted by MMU. MMU will interpret this address to PDX, PTX and VPO (equals to PPO), and use CR3 register, which stores the physical address of page directory, to find the corresponding physical address.

So, how could this be done?

Before we start, there’s one thing to get through, and it is the key to the following stuffs.

We use virtual address to find the page table entry, but the content of the page table entry is actually physical address! All jumps from page table entry to page table entry or physical page is through physical address!

To access memory through virtual address, we have to use page table to translate it to physical address. To achieve this, we need two parameters: CR3 and virtual address.

CR3 is the register in MMU, which stores the physical address of the page directory of the current process. It is known as Env::env_pgdir in MOS.

Virtual address is what the CPU sends to MMU, which is in the format of PDX | PTX | VPO.

Having these in mind, we could draw a simple figure to show how virtual address is translated to be used in page table. Page table entry stores the physical page number of the page it mapped to in the high 20 bits, and permission bits in the low 12 bits.

Page Table-Page-1

Now, let’s have a look at how we access the physical address via virtual address. Here’s another figure to elaborate this process.

Page Table-Page-2

Step 1) As mentioned before, we need CR3 (a.k.a. Env::env_pgdir) and virtual address. CR3 stores the physical address of page directory, which is the value of Pde* Env::env_pgdir (just the value of the pointer, not the content it points to, it is the beginning of page directory entry array). And we can easily get PDX, PTX and PPO (equals to VPO) from virtual address.

Step 2) Use PDX as offset from Env::env_pgdir to get the page directory entry we want. Usually, we first check the permission bit PTE_V to ensure the page is valid, and some other bits like PTE_D to determine whether it is writable. Then, we can get the corresponding physical address of the second-level page table using PTE_ADDR() macro.

Step 3) Since page table and page directory are the same at the very essence, the process of getting the physical address of the page frame is of no difference.

If we want to use self mapping, we just need to get the self-mapping page directory entry in page directory, and the PTE_ADDR() of this entry is always set to the physical address of page directory, which is Env::env_pgdir.

What? How to get this page directory entry? Check out the previous section, as we already know $PD_{base}$, which is the Env::env_pgdir, we only need the corresponding PDX. And it is easy to get.
$$
PDX_{self-mapping} = PDX(PT_{base})
$$

So, here is a piece of code regarding this process.

1
2
3
4
5
6
7
8
9
10
11
12
u_long pdx = PDX(va);  // #define PDX(va) ((((u_long)(va)) >> 22) & 0x03FF)
u_long ptx = PTX(va);  // #define PTX(va) ((((u_long)(va)) >> 12) & 0x03FF)
u_long ppo = PPO(va);  // #define PPO(va) (((u_long)(va)) & 0xFFF)
if (pgdir[pdx] & PTEV)
{
    Pte* pgtbl = KADDR(PTE_ADDR(pgdir[pdx]));
    if (pgtbl[ptx] & PTE_V)
    {
        u_long pa = PTE_ADDR(pgtbl[ptx]) | ppo;
        // some other actions...
    }
}

Why KADDR()? Because page operation is done by our kernel in kuseg0, and this macro simply adds an offset to the address to make it a kuseg0 address. A further reason is that when kuseg0 address intercepted by MMU, it will not go through TLB, but go directly to the physical address with the offset erased. So we just add KADDR() for page table access. Later, physical page won’t need this.

Well, I guess this is it. Just keep in mind that page table is a mediator to translate virtual address into physical address.