This is not the current version of the class.

Section 4: Memory iterators

Memory iterators

The pset for this unit asks you to add to WeensyOS, an operating system that we’ll use in this course. WeensyOS has internal interfaces for dealing with virtual memory that we’ll now discuss.

vmiter and ptiter are iterators in WeensyOS for processing page tables. Vmiter helps iterate through pages in virtual memory, and lets you check the underlying physical pages for properties like permissions and physical addresses. Ptiter helps you iterate through page table pages. Let’s walk through the code:

Vmiter

The vmiter class represents an iterator over virtual memory mappings. Here is its interface:

// `vmiter` walks over virtual address mappings.
// `pa()` and `perm()` read current addresses and permissions;
// `map()` installs new mappings.

class vmiter {
  public:
    // initialize a `vmiter` for `pt` pointing at `va`
    inline vmiter(x86_64_pagetable* pt, uintptr_t va = 0);
    inline vmiter(const proc* p, uintptr_t va = 0);

    inline uintptr_t va() const;      // current virtual address
    inline uint64_t pa() const;       // current physical address
    inline void* kptr() const;        // pointer to physical address
    // The return value from `kptr()` can be dereferenced in the kernel.
    // Call `kptr<int*>()` to get an `int*` pointer instead of `void*`.

    inline uint64_t perm() const;     // current permissions
    inline bool present() const;      // is va present?
    inline bool writable() const;     // is va writable?
    inline bool user() const;         // is va user-accessible (unprivileged)?

    inline vmiter& find(uintptr_t va);   // change virtual address to `va`
    inline vmiter& operator+=(intptr_t delta);  // advance `va` by `delta`

    // map current va to `pa` with permissions `perm`
    // Current va must be page-aligned. Calls kalloc() to allocate
    // page table pages if necessary. Panics on failure.
    void map(uintptr_t pa, int perm);

    // like `map`, but returns 0 on success and -1 on failure
    int try_map(uintptr_t pa, int perm);
};

This type 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 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).

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

Ptiter

class ptiter {
  public:
    // initialize a `ptiter` for `pt` pointing at `va`
    inline ptiter(x86_64_pagetable* pt, uintptr_t va = 0);
    inline ptiter(const proc* p, uintptr_t va = 0);

    inline uintptr_t va() const;            // current virtual address
    inline uintptr_t last_va() const;       // one past last va covered by ptp
    inline bool active() const;             // does va exist?
    inline x86_64_pagetable* kptr() const;  // current page table page
    inline uintptr_t pa() const;            // physical address of ptp

    // move to next page table page in depth-first order
    inline void next();
};

ptiter visits the individual page table pages in a multi-level page table, in depth-first order (so all level-1 page tables under a level-2 page table are visited before the level-2 is visited). A ptiter loop makes it easy to find all the page table pages owned by a process, which is usually at least 4 page tables in x86-64 (one per level).

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

A WeensyOS process might print the following:

[0x0, 0x200000): ptp at pa 0xb000
[0x200000, 0x400000): ptp at pa 0xe000
[0x0, 0x40000000): ptp at pa 0xa000
[0x0, 0x8000000000): ptp at 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 instance, when you’re implementing process exit later :)

ptiter never visits the top level-4 page table page, so that will need to be freed independently of the ptiter loop.

Using iterators

On this problem set, you will implement some of the system calls in WeensyOS. Two of the main system calls that you will implement are fork() and exit().

The fork system call allows a process to spawn a child process that is essentially a copy of the parent process. The child process has a copy of the parent processes’ memory, and after the new child process created, both processes execute the next instruction after fork(). The registers and file descriptors are also copied.

The exit system call allows a process to stop its execution. All of the memory belonging to that process, including its page table pages, are returned to the kernel for reuse.

The Lifecycle of a Process

A process: the singular unit of life in an operating system. When a new process is born, it needs its own page table pages, which it gets from its parent. For processes not born from a fork() call, this parent is the kernel, and thus, the process's page table pages will be a copy of the kernel's.

During the normal execution of a process, it refers to memory addresses by their virtual memory addresses -- which means that, to actually access the underlying memory, those virtual memory addresses need to be translated into physical addresses. Fortunately, you have just learned about the basic mechanism behind this process. ;)

Once a process has completed its run, there is some cleanup to be done -- namely, the relinquishment of its virtual memory mappings. First, the process needs to disassociate itself from the kernel's page table pages -- an exited process shouldn't need them anymore, anyway. Next, the process needs to tell the kernel that it is no longer using its page table pages -- this is not just the level-1 page table pages, but also the higher-level ones as well! Finally, the process can rest in peace. RIP.

QUESTION: Use vmiter to implement the following function.

void copy_mappings(x86_64_pagetable* dst, x86_64_pagetable* src) {
    // Copy all virtual memory mappings from `src` into `dst`
    // for addresses in the range [0, MEMSIZE_VIRTUAL).
    // You may assume that `dst` starts out empty (has no mappings).

    // After this function completes, for any va with
    // 0 <= va < MEMSIZE_VIRTUAL, dst and src should map that va
    // to the same pa with the same permissions.






}

QUESTION: Use vmiter and ptiter to implement the following function.

void free_everything(x86_64_pagetable* pt) {
    // Free the following pages by passing their physical addresses
    // to `kfree()`:
    // 1. All memory accessible by unprivileged mappings in `pt`.
    // 2. All page table pages that are part of `pt`.






}

WeensyOS exercise 1: Spawn

Goal: Start a new process in WeensyOS

These exercises use the code in cs61-sections/s04-weensyos.

Look at p-spawn.cc. This process tries to run another command, using the sys_spawn system call. Read the system call’s specification in u-lib.hh. Find the place in kernel.cc that would implement the system call.

Use make run-spawn (or make run-console-spawn, etc.) to run this program.

  1. Is the system call working currently? How can you tell?
  2. Complete the system call implementation so that p-spawn.cc successfully starts a new process.
  3. Modify p-spawn.cc so that it tries to start two copies of alice. What happens and why? How could you fix this?
  4. Does your implementation of syscall_spawn check its arguments for validity? If not, how would you change it to do this?

WeensyOS exercise 2: Confused deputy

Goal: Understand attack mechanisms

A confused deputy attack occurs when a low-privilege attacker convinces a privileged “deputy” to complete an attack on its behalf. In the context of operating systems, a process is unprivileged, while the kernel has full privilege; but the kernel frequently acts as a privileged deputy on behalf of processes when it handles system calls. A confused deputy attack may occur if the process, by invoking system calls, can somehow convince the kernel to perform a function that violates process isolation.

Look at p-eve.cc. This is the program from class. Understand the system calls it makes (check their specifications in u-lib.hh).

Use make run-friends to run Alice and Eve together.

  1. It is possible to change one argument of one existing system call in p-eve.cc to execute a successful confused deputy attack that breaks the kernel or otherwise prevents Alice from running. What is the system call? What is the confused deputy attack?
  2. Complete the attack.
  3. Modify the kernel’s system call checking to prevent the attack. The kernel might kill the Eve process upon detecting the attack, or (better perhaps) return -1 from the relevant system call.

WeensyOS exercise 3: Process communication

Goal: Gain experience with scheduling and other kernel design features that can improve system performance

The p-pipewriter.cc and p-pipereader.cc programs implement a simple form of communication, mediated by the kernel. The pipewriter program picks a random message and writes it to a shared “pipe,” which is just a memory buffer located in the kernel. The pipereader program reads this message by reading from the pipe.

Use make run-pipe to run the pipewriter and pipereader together.

  1. Read the explanations for the sys_piperead and sys_pipewrite system calls in u-lib.hh. What do these system calls remind you of? What arguments are missing, if any?
  2. Find the implementations of SYSCALL_PIPEWRITE and SYSCALL_PIPEREAD in kernel.cc. What is the maximum number of bytes these system calls can read or write at a time? How can this be a performance problem?
  3. How many system calls do the writer and reader make per message? Is there a discrepancy? Look at their code; can you explain the discrepancy?
  4. Your goal for the rest of this exercise is to change the kernel, and only the kernel, to reduce the number of system calls required to transfer a message to the minimum, which is less than five. Here are some techniques you can use:
    • Scheduling. When process P is unlikely to be doing useful work, it often makes sense to run a process other than P. The handout kernel does not follow this rule of thumb.
    • Batching/buffering. It is more efficient to transfer more than one byte at a time.
    • Blocking. When process P cannot make progress until some state changes, it can be more efficient overall to put process P to sleep. This is called blocking process P. For instance, perhaps the sys_piperead system call might block the calling process until there is at least one byte available to read.