Section 3: System calls

System calls on Linux

Notes

System calls on WeensyOS

Protection in Linux

Protection in WeensyOS

Virtual memory

Virtual memory is the hardware mechanism that allows a kernel—which needs complete privilege over all operations of the machine, and must be protected at all costs—to run without inappropriate interference from user-level processes—which have no privilege and might have bugs.

+-------------------------------------------------------------------------------+
|          |   Kernel data   |                  | Unprivileged data |           |
+-------------------------------------------------------------------------------+
           ^                                    ^
        0x40000                             0x100000

Memory iterators (advanced material)

We didn’t get to this material on Monday because we weren’t prepared for it in class.

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`.






}