The final part of the Virtualisation section is Memory Management, I hope you know why we need virtualisation in memory; if not, read OSTEP! I have covered memory management in xv6 here.

As this topic is quite large, we are going to cover it in parts!

Page Tables

Definition

pub struct PageTable<A> {
    base: VirtualAddress,
    phys: PhysicalAddress,
    level: usize,
    phantom: PhantomData<A>,
}

We abstract the PageTable struct over arch A.

1. base contains the start of the range of Virtual Addresses covered by this table.
2. phys gives us the actual physical address of where this particular table is located.
3. level, as evident by the name, stores the level of this table. Level 0 indicates leaf where the entries contain Page Table Entries, and level n stores level n-1 tables as its entries.
4. phantom is more of a Rust thing than OS, as I said earlier, many values differ on different archs (like PAGE_ENTRIES), therefore we need to abstract the PageTable struct over these archs. However as you might notice, none of our fields contain a generic A which would result in a compile time error, PhantomData is a zero-sized placeholder that satisfies the requirement without any runtime costs.

Associated Methods

Let’s take a look at the non-trivial methods associated with our struct.

next

The first thing that you might ask is how do I traverse this table, how do I get the child Table sitting at index i?

pub unsafe fn next(&self, i: usize) -> Option<Self> {
    if self.level == 0 {
        return None;
    }

    unsafe {
        Some(PageTable::new(
            self.entry_base(i)?,
            self.entry(i)?.address().ok()?,
            self.level - 1,
        ))
    }
}

If this is the lowest level, we do not have any more tables as children and therefore return None. Otherwise, we calculate the start of the range of Virtual Addresses that the child table covers, the physical address it is sitting at and its level, and return that!

entry_base

How do I calculate the start of the range of VA that a child table covers?

pub fn entry_base(&self, i: usize) -> Option<VirtualAddress> {
    if i < A::PAGE_ENTRIES {
        let level_shift = self.level * A::PAGE_ENTRY_SHIFT + A::PAGE_SHIFT;
        Some(self.base.add(i << level_shift))
    } else {
        None
    }
}

The first thing we do is check if i even exists in our current table, if it does not, we simply return None.

To truly understand it, let’s work through an example, where the level of the table is 1 (PD), i = 2 and arch is x86_64, therefore

const PAGE_SHIFT: usize = 12;       // 4096 bytes = 2^12
const PAGE_ENTRY_SHIFT: usize = 9;  // 512 entries = 2^9
const PAGE_LEVELS: usize = 4;       // PML4, PDP, PD, PT

At level 0, each entry covers one 4KB page, therefore at level 1, each entry covers one level 0 table worth of address space, i.e., 4KB * 512, so the size jumps from 2¹² to 2⁹ * 2¹². Each additional level multiplies it by 2⁹! To get to entry i, we just multiply it by i.

Therefore,

• level_shift = 21
• i << level_shift = 2 * 2²¹ = 0x400000

Therefore we get the formula,

VA_start = base + (i * 2^(level * PAGE_ENTRY_SHIFT + PAGE_SHIFT))

entry

How do I find where the entry itself lives? Let e be an entry in a level n table, that points to a level n-1 table, this next method gives us the VA of e itself, not the table it points to!

pub unsafe fn entry(&self, i: usize) -> Option<PageEntry<A>> {
    unsafe {
        let addr = self.entry_virt(i)?;
        Some(PageEntry::from_data(A::read::<usize>(addr)))
    }
}

Uh oh, this method just wraps the result of entry_virt in a PageEntry struct, so let’s take a look at that directly!

unsafe fn entry_virt(&self, i: usize) -> Option<VirtualAddress> {
    if i < A::PAGE_ENTRIES {
        Some(A::phys_to_virt(self.phys).add(i * A::PAGE_ENTRY_SIZE))
    } else {
        None
    }
}

This method, as you can see, is much simpler than entry_base, we just check i for bounds; if it exists, we just use simple C-like array indexing of memory.

set_entry

How do I write to e?

pub(super) unsafe fn set_entry(&mut self, i: usize, entry: PageEntry<A>) -> Option<()> {
    unsafe {
        let addr = self.entry_virt(i)?;
        A::write::<usize>(addr, entry.data());
        Some(())
    }
}

Well, we just use the previous method again to get the address, and then write to it!

A::write() takes two arguments, address and data to write.

As expected, direct memory access (read and write) are unsafe, thus extra attention should be paid.

index_of

Given a VA, which index should I look up in this table?

This is the inverse of the entry_base function

pub(super) fn index_of(&self, address: VirtualAddress) -> Option<usize> {
    // Canonicalize address first
    let address = VirtualAddress::new(address.data() & A::PAGE_ADDRESS_MASK);
    let level_shift = self.level * A::PAGE_ENTRY_SHIFT + A::PAGE_SHIFT;
    // Intentionally wraps around at last-level table to get all-ones mask on architectures
    // where addressable physical address space covers entire usized space (e.g. x86)
    let level_mask = A::PAGE_ENTRIES
        .wrapping_shl(level_shift as u32)
        .wrapping_sub(1);
    if address >= self.base && address <= self.base.add(level_mask) {
        Some((address.data() >> level_shift) & A::PAGE_ENTRY_MASK)
    } else {
        None
    }
}

• We first canonicalize the address, i.e., mask off any bits above the architecture’s usable VA width.
• We compute the same level_shift as entry_base.
• The level_mask is a new part, PAGE_ENTRIES << level_shift is the span of the entire table, we subtract 1 from it to make the range inclusive (Homework: why are we using wrapping here, hint in the comments!).
• We check if the requested address is covered by this table; if no, return None.
• If yes, we reject the lower and higher order bits to keep only the chunk associated with this level, which gives us the index!

Worked example for the last step, level 1 table (PD), address 0x400123, base 0:

• 0x400123 >> 21 discard the lower 21 bits giving us, 2
• 2 & 0x1FF discards the higher order bits that belong to other/higher levels, keeping only this level’s 9 bit chunk, which in this case is unchanged.
• Therefore, index = 2!

Page Table Entry

Definition

pub struct PageEntry<A> {
    data: usize,
    phantom: PhantomData<A>,
}

This is quite simple, data contains the actual entry.

Associated Methods

new

How do I build a Page Entry from an actual Physical Address?

pub fn new(address: usize, flags: usize) -> Self {
    let data = (((address >> A::PAGE_SHIFT) & A::ENTRY_ADDRESS_MASK) << A::ENTRY_ADDRESS_SHIFT)
        | flags;
    Self::from_data(data)
}

So we have the actual physical address and the related flags as our input. What do we do to make it a Page Entry?

1. Because we have frames of 4KB (2¹²) size, we can safely ignore the lower 12 bits which are used for indexing INSIDE the frame. As a result we can use those lower 12 bits to store other information, such as the different flags!
2. We thus bit shift the address to the right, mask off the higher unused bits and bit shift it all to the left again. What this results in is the middle part is kept as-it-is, while the lower and higher bits are zeroed.
3. We finally OR this number with our flags!

And we thus get the result!

from_data

Once you’ve converted it, who am I to stop you from using it.

pub fn from_data(data: usize) -> Self {
    Self {
        data,
        phantom: PhantomData,
    }
}

address

You have the PageEntry, how do you get the Physical Address?

pub fn address(&self) -> Result<PhysicalAddress, PhysicalAddress> {
    let addr = PhysicalAddress(
        ((self.data >> A::ENTRY_ADDRESS_SHIFT) & A::ENTRY_ADDRESS_MASK) << A::PAGE_SHIFT,
    );

    if self.present() {
        Ok(addr)
    } else {
        Err(addr)
    }
}

It is the inverse of the new method, we bit shift to the right to clear the flag bits, mask off the higher bits, and bit shift to the left again to the correct position.

The next part is a little interesting, we check the present bit, if the Page exists in the memory, we return it wrapped in Ok(), otherwise as an Err. Take a look at the PageTable’s next method again, when the result from this method is not Ok, we stop the walk!

flags and set_flags

pub fn flags(&self) -> PageFlags<A> {
    unsafe { PageFlags::from_data(self.data & A::ENTRY_FLAGS_MASK) }
}
pub fn set_flags(&mut self, flags: PageFlags<A>) {
    self.data &= !A::ENTRY_FLAGS_MASK;
    self.data |= flags.data();
}

flags masks out the flag bit region and returns them wrapped in the PageFlags struct.

set_flags zeros the flag bits, then ORs them with the input flags.

present

pub fn present(&self) -> bool {
    self.data & A::ENTRY_FLAG_PRESENT != 0
}

The simplest of the batch, we just mask off and check for a single bit, the PRESENT bit.

Conclusion

Read more books so you understand pages better. Better yet, write a few page tables yourself, and then write a book!