Page Table Visitors

[mark-i-m]

We previously had some discussion of using some sort of Visitor pattern to visit and update page tables. I got some time to play around with it a bit today. I think it is promising, but there are some unresolved API questions and some issues that I don't know how to deal with.

Unresolved Problem:

• The visitor doesn't know where in virtual memory a page table is. We need some generic and ergonomic way to figure out this information for Visitors to really work. For now, I have left it abstracted as the Visit::get_page method, which is implemented by each Visitor as needed.

Unresolved questions:

• Should we have visit_huge_page<S: Size>(...)? Is this too fine-grained?

Here is a rough prototype. It doesn't work or compile, but it should give a rough idea: https://github.com/rust-osdev/x86_64/compare/master...mark-i-m:visitor?expand=1

cc #32 #96 #112 #113 #114

[mark-i-m]

Also, cc @Wenzel from #96. Would this sort of API help your use-cases too?

[phil-opp]

I like the idea as a way to give the user maximal control over the page table layout if desired.

* The visitor doesn't know where in virtual memory a page table is. We need some generic and ergonomic way to figure out this information for `Visitors` to really work. For now, I have left it abstracted as the `Visit::get_page` method, which is implemented by each `Visitor` as needed.

The get_page method could be easily implemented for the MappedPageTable type. For the RecursivePageTable type, however, this not possible since it calculates the virtual address from the indexes into the parent tables and the recursive index. I'm not sure whether it is possible to create a visitor trait that supports both page table types.

[Wenzel]

hi @mark-i-m , thanks for pinging me.

A page table parsing implemented using the Visitor pattern seems an interesting approach, to separate the data from the algorithm operating on the data.

In my case, what I have is a primitive to read the guest physical memory,
and what I need is a external crate defining the underlying details of page table definition/parsing, and an API to translate a virtual address.

From the hypervisor I would also have access to the currrent CR3 register, so I know where the root page directory is located in memory.

@mark-i-m do you think your visitor could fit for this usage ?

I'm giving a simplified example of what I need:

// importing your crate
use x86_64::page_tables::{translate_vaddr_to_paddr, Paging};

....

// my own wrapper in libmicrovmi
struct Translation {
    // x86_64 struct
    paging: Paging,
}

fn new(&self) -> Translation {
    // get important control registers involved in paging
    let cr0 = hypervisor.get_cr0()
    let cr4 = hypervisor.get_cr4();
    // guess the guest paging state
    // see https://github.com/libvmi/libvmi/blob/master/libvmi/libvmi.h#L151
    // PM_LEGACY,  /**< x86 32-bit paging */
    // PM_PAE,     /**< x86 PAE paging */
    // PM_IA32E,   /**< x86 IA-32e paging */
    // etc...
    let paging = Paging(cr0, cr4, ...);
    Translation {
          paging,
     }:
}

fn translate(&self, vaddr: u64, cr3: u64) -> u64 {
      self.paging.translate_vaddr_to_paddr(vaddr, cr3)
}

[mark-i-m]

The get_page method could be easily implemented for the MappedPageTable type. For the RecursivePageTable type, however, this not possible since it calculates the virtual address from the indexes into the parent tables and the recursive index. I'm not sure whether it is possible to create a visitor trait that supports both page table types.

I'm not sure. I think it can be done in theory by passing the recursive index to the constructor of the visitor type. I think the argument of the get_page method would have to take more information, though, e.g. the indices of the upper levels of the page tables that we have traversed so far.

In my case, what I have is a primitive to read the guest physical memory, and what I need is a external crate defining the underlying details of page table definition/parsing, and an API to translate a virtual address.

Hmm... in principle, I think you could use this pattern. I think the tricky part is abstracting the memory accesses. For a normal OS, you can just access the page tables directly in memory, but in your case, you would need to access them through the primitive you mentioned. I wonder if that can be abstracted away somehow...

[mark-i-m]

After thinking about it a bit more, I'm no longer convinced that the Visitor pattern is really that useful for page tables. The reason is that Visitors are really designed for the case where you want to iterate over the whole page table structure (i.e. all entries in all levels). While this is useful sometimes (e.g. freeing memory after process exit), it is not what we generally want.

So instead I propose the following lower-level and more general framework (pseudocode). The details and exact API need adjusting, since I don't remember exactly what each level PTE looks like and I haven't actually tried to implement this. But here's the general idea...

First, we define a bunch of very-low-level types that are bitwise-compatible with the ISA definitions of various things, meaning their layouts in memory match the actual layouts defined by the ISA:

// These page table entry types have accessors defined for all the fields of a
// page table entry in x86.

/// An x86-64 page table entry for a normal translation (either to the next level of PT
/// or to a page). Bitwise-compatible with the ISA.
#[repr(C,packed)]
struct NormalPageTableEntry { ... }
/// x86-64 page table entry for a 2MiB huge page.
struct TwoMiBPageTableEntry { ... }
/// x86-64 page table entry for a 1GiB huge page.
struct OneGiBPageTableEntry { ... }

/// A low-level page table entry union. This is bitwise-compatible with the ISA.
#[repr(C,packed)]
union RawPageTableEntry {
  normal: NormalPageTableEntry,
  huge_2mib: TwoMiBPageTableEntry,
  huge_1gib: OneGiBPageTableEntry,
}

/// A low-level page table struct. This is bitwise-compatible with the ISA.
struct RawPageTable {
  entries: [RawPageTableEntry; 512]
}

impl Index<Item=RawPageTableEntry> for RawPageTable { ... }
impl IndexMut<Item=RawPageTableEntry> for RawPageTable { ... }

Then, we define a PageTableWalker API over this that provides safe ways of walking and manipulating page tables.

/// A `Walk` type defines how to walk a particular level of the page tables. Different
/// page table implementations will provide different implementations for each level.
/// For example, `RecursivePageTables` would make use of its recursive index, etc.
trait Walk {
  /// The type of page table entries at this level of the page tables.
  type PageTableEntry;

  /// The type of thing that `Self::PageTableEntry` points (e.g. `Page` or
  ///  `PageTableWalker<NextLevel>`).
  type Next;

  /// Given a page table entry, point to either a page or a page table.
  fn next(&self, pte: Self::PageTableEntry) -> Self::Next;
}

/// A high-level struct that safely represents a single PTE, which could be for a huge
/// page or a normal translation (i.e. just point to the next level). Because we don't
/// know how large the huge page could be, we make it generic.
enum HugeOrNormalPageTableEntry<Huge> {
  Huge(Huge),
  Normal(NormalPageTableEntry)
}

impl HugeOrNormalPageTableEntry<Huge> {
  fn as_raw(self) -> RawPageTableEntry { ... }
}

/// This is the main API for walking page tables. Page table implementations would
/// provide a method for getting a `PageTableWalker` over themselves.
struct PageTableWalker<W: Walk>;

impl PageTableWalker<W: Walk> {
  /// Access the `i`th page table entry at this level.
  /// Returns `None` if the entry is not present.
  fn entry(i: u16) -> Option<&W::PageTableEntry> { ... }
  unsafe fn entry_mut(i: u16) -> Option<&mut W::PageTableEntry> { ... }

  /// Same but for the raw entry
  fn entry_raw(i: u16) -> &RawPageTableEntry { ... }
  unsafe fn entry_raw_mut(i: u16) -> &mut RawPageTableEntry { ... }

  /// For initializing an entry
  unsafe fn entry_init(i: u16, entry: W::PageTableEntry) { ... }
  unsafe fn entry_raw_init(i: u16, entry: RawPageTableEntry) { ... }

  /// For walking
  next(i: u16) -> Option<W::Next> { ... }
}

Finally, the API would be used as follows:

struct RecursivePageTables {
  raw: RawPageTables,
  rec_idx: u16,
}

impl RecursivePageTables {
  fn walk(&mut self) -> PageTableWalker<Level4> { ... }
}

struct Level4(&mut RecursivePageTables); // root
struct Level3(&mut RecursivePageTables);
struct Level2(&mut RecursivePageTables);
struct Level1(&mut RecursivePageTables); // base page table entry

impl Walk for Level4 {
  type PageTableEntry = NormalPageTableEntry;
  type Next = PageTableWalker<Level3>;

  fn next(&self, entry: NormalPageTableEntry) -> PageTableWalker<Level3> {
    // use self and pte to get `RawPageTableEntry` to next level and
    // make a `Self::Next`... 
  }
}

impl Walk for Level3 {
  type PageTableEntry = HugeOrNormal<OneGiBHugePage>;
  type Next = HugePageOrPageTableWalker<OneGiBHugePage, Level2>;

  fn next(...) -> Self::Next { ... }
}

...

impl Walk for Level1 {
  type PageTableEntry = NormalPageTableEntry;
  type Next = Page<Size4Kib>;

  fn next(...) -> Self::Next { ... }
}

So that we can do, for example, the following:

let recursive_pt = ...;
recursive_pt.walk()
  .next(32).unwrap()
  .next(52).unwrap()
  .entry_mut(42).unwrap()
  .global_bit(true);

The rationale is that the lowest level raw APIs allow lots of control but are very inconvenient. The upper levels allow encoding a bit more in the type system when we can assume more (e.g. with the recursive page tables). The Walk trait encodes those assumptions cleanly, and the PageTableWalker abstracts out all of the boilerplate and keeps any context/state we need to know to actually walk the page tables.