Memory iterators

Chickadee offers several types that simplify the examination and modification of x86-64 page tables and the classification of physical memory.

vmiter

The vmiter type (defined in k-vmiter.hh) parses x86-64 page tables and manages virtual-to-physical address mappings. vmiter(pt, va) creates a vmiter object that’s examining virtual address va in page table pt. Methods on this object can return the corresponding physical address:

x86_64_pagetable* pt = ...;
uintptr_t pa = vmiter(pt, va).pa();    // returns uintptr_t(-1) if unmapped

Or the permissions:

if (vmiter(pt, va).writable()) {
    // then `va` is present and writable (PTE_P | PTE_W) in `pt`
}

It’s also possible to use vmiter as a loop variable, calling both methods that query its state and methods that change its current virtual address. For example, this loop prints all present mappings in the lower 64KiB of memory:

for (vmiter it(pt, 0); it.va() < 0x10000; it += PAGESIZE) {
    if (it.present()) {
        log_printf("%p maps to %p\n", it.va(), it.pa());
    }
}

This loop goes one page at a time (the it += PAGESIZE expression increases it.va() by PAGESIZE). But most page tables have large holes in them—regions where upper-level entries are missing. Chickadee processes will have holes that cover terabytes of virtual memory space! Walking page by page over these holes is inefficient, so vmiter offers a method, next(), that skips over them. This loop will always produce the same answer as the loop above, but may complete faster:

for (vmiter it(pt, 0); it.va() < 0x10000; it.next()) {
    if (it.present()) {
        log_printf("%p maps to %p\n", it.va(), it.pa());
    }
}

Finally, the vmiter.map() function is used to add mappings to a page table. This maps physical page 0x3000 at virtual address 0x2000:

int r = vmiter(pt, 0x2000).map(0x3000, PTE_P | PTE_W | PTE_U);
// r == 0 on success, r < 0 on failure

Other notes:

ptiter

ptiter (defined in k-vmiter.hh) visits the internal page table pages in a page table in depth-first order. A ptiter loop makes it easy to find the page table pages owned by a process.

for (ptiter it(pt, 0); it.low(); it.next()) {
    log_printf("[%p, %p): ptp at va %p, pa %p\n",
               it.va(), it.end_va(), it.ptp(), it.ptp_pa());
}

A Chickadee process might print the following:

[0x0, 0x200000): ptp at va 0xffff80000000b000, pa 0xb000
[0x200000, 0x400000): ptp at va 0xffff80000000e000, pa 0xe000
[0x0, 0x40000000): ptp at va 0xffff80000000a000, pa 0xa000
[0x0, 0x8000000000): ptp at va 0xffff800000009000, pa 0x9000

Note the depth-first order: the level-1 page table pages are visited first, then level-2, then level-3. Because of this order (and other implementation choices), a ptiter loop may be used to free a page table:

for (ptiter it(pt, 0); it.low(); it.next()) {
    it.kfree_ptp(); // `kfree(ptp())` + clear mapping
}

ptiter never visits the top level-4 page table page.

memrangeset

The memrangeset type (defined in k-memrange.hh) is used to track the memory types of ranges of physical addresses. Example types are “kernel code and data” (mem_kernel), “reserved for I/O memory” (mem_reserved), and “available for generic use” (mem_available). This information is useful, for example, when writing a kernel allocator.

You will use one instance of memrangeset, the global physical_ranges object. This object is initialized in k-init.cc:init_physical_ranges.

Example uses:

physical_ranges.type(pa);             // return type of memory at `pa`

// Sometimes you want to know where the range ends.
// memrangeset::find() gives you a pointer to a `memrange` object
// that stores that information.
auto r = physical_ranges.find(pa);
log_printf("%p is in [%p, %p) of type %d\n",
           pa, r->first(), r->last(), r->type());

if (r != physical_ranges.end()) {
    auto nextr = r + 1;    // ranges are stored in an array; get next one
    log_printf("next range is [%p, %p) of type %d\n",
               nextr->first(), nextr->last(), nextr->type());
} else {
    log_printf("that was the last range\n");
}

Bugs

vmiter and ptiter currently work with non-canonical virtual addresses. This means they work better on low virtual addresses than high ones. This isn’t so bad in practice; in Chickadee, like many operating systems, the low portion of virtual memory is more “interesting” anyway.