Kernel Section 1: WeensyOS

College students: Attendance at section is required and recorded for all college students. All college students should fill out this attendance form when attending section. For more on the attendance policy and what to do if you miss section refer to the syllabus here and here.

Extension School students: Extension School students are required to self-report weekly section participation using this participation form. There are two ways to participate in section: (1) attend section live (for most students, this is one of the zoom sections, but local students are welcome to attend in-person sections) OR (2) watch a section recording (Canvas > Zoom > Published Recordings). Both participation methods are equally valid towards your participation grade.

The pset for this unit concerns our tiny WeensyOS operating system. Our section introduces WeensyOS, and especially its internal interfaces for dealing with virtual memory.

The coding exercises in this section use the cs61-sections/kernels1 subdirectory. This version of WeensyOS uses identity mappings; all processes share the same page table (the kernel page table), but the kernel is isolated. This resembles the state of your pset 3 after phase 1.

Part A: WeensyOS architecture

WeensyOS is a full operating system for x86-64 machines that fits in one directory. In the first part of section, TFs will walk you through the way files are laid out in the operating system and where different operating system functions are located, and show you how to run the operating system in different modes.

Update your cs61-sections repository and change into the kernels1 subdirectory. Run docker. make run-hello to see the exciting result of the p-hello.cc program! Type q to quit.

Part B: Virtual memory mappings and permissions

Virtual memory is the processor feature that supports process isolation for primary memory (the part of the computer that stores data and has addresses). It allows different processes to have completely different views of memory. For instance, the data stored at address 0x100000 in the two processes might be totally different, even though the addresses are the same.

Virtual memory is a powerful technique with many uses, though isolation is its most important use now.

x86-64 virtual memory is implemented by page table structures the kernel maintains. A page table maps a virtual address, which is the kind of address used in software and machine instructions, to a physical address, which names a specific set of transistors and capacitors on machine memory chips capable of holding a byte. The virtual-to-physical mapping can be almost arbitrary! All virtual addresses might map to the same set of physical addresses. There is just one constraint: Page tables work in units of aligned chunks of memory 4,096 bytes (212 bytes) big. These aligned units are called pages.

Page tables also associate permissions with each mapping. A mapping can be read-only, which prevents software from writing to memory, and/or kernel-only, which prevents processes from reading or writing memory.

A specific register, the %cr3 register, holds the current page table. If two processes run with different page tables (different %cr3 values), then they might have completely different views of memory. This feature lets the kernel isolate the processes from one another.

Examining mappings and permissions

vmiter and ptiter are WeensyOS iterators that process page tables. vmiter answers the question “In the context of page table pt, what does the virtual address va map to in terms of physical address and permissions?” It also lets you modify mappings, thereby changing a process’s view of memory. ptiter answers the question “Which physical pages are used to represent this page table?” This lets you free a page table relatively easily.

About virtual memory iterators (vmiter)

About physical memory iterators (ptiter)

EXERCISE B1. Let’s use vmiter and log_printf to log information about kernel_pagetable’s mappings for the following virtual addresses:

  1. The syscall_entry function;
  2. The kernel_pagetable;
  3. The p-hello process’s entry point, process_main.

First log the physical addresses mapped for these virtual addresses immediately before the call to process_setup in kernel.cc. What are they?

EXERCISE B2. Now log the physical addresses immediately after the call to process_setup. Do the values change? Why or why not? Refer to specific properties of process_setup.

EXERCISE B3. Log the permissions associated with those virtual addresses immediately before the call to process_setup. What are they? What permissions do they correspond to? (Look for the PTE_ constants in x86-64.h to understand the meaning of each permission bit.)

EXERCISE B4. What about these permissions indicate that the kernel appears to implement kernel isolation (in terms of virtual memory access)?

EXERCISE B5. Log the permissions associated with those virtual addresses immediately after the call to process_setup. Did they change?

Part C: Warped virtual memory

Run make run-bigdata. Boo!

EXERCISE C1. Add one line of virtual memory map manipulation code to process_setup so that the bigdata process prints CS 61 Is Amazing. Don’t change p-bigdata.cc or the contents of physical memory, just change memory mappings. If you get stuck, uncomment the console_printf lines in p-bigdata.cc: what do you see?

Make sure you remove your VM manipulation code before moving on to another problem.

Part D: Using iterators

In the problem set, you will implement fork and exit system calls. At the center of these system calls are operations on virtual memory that you’ll use vmiter and ptiter to implement. In section we investigate related problems for practice.

EXERCISE D1. 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),
    // and that all calls to `vmiter::map` succeed.

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

    ... 
}

The fork system call, which you’ll implement in the pset, is the original system call that Unix-based operating systems used to start new processes. fork works by creating a new process, called the child process, that is essentially a copy of the parent process (the process that called fork). The child process has a copy of the parent process’s memory, as well as its registers and other state. After the system call completes, then, there are two processes whose contents of memory are identical. The memory contents quickly diverge, though: changes to the child process’s memory are not visible in the parent’s memory or vice versa.

EXERCISE D2. Does copy_mappings suffice to implement the memory copying required by fork? Why or why not?

EXERCISE D3. Use vmiter and ptiter to implement the following function.

void free_everything(x86_64_pagetable* pt) {
    // Free the following pages by passing their kernel pointers
    // to `kfree(void*)`:
    // 1. All memory accessible via unprivileged mappings in `pt` from virtual
    //    addresses in [0,MEMSIZE_VIRTUAL).
    // 2. All page table pages that are part of `pt`.
    ...
}

The exit system call allows a process to stop executing. All memory belonging to or representing that process must be returned to the kernel for reuse. This will include some memory that is accessible only to the kernel, such as memory storing the process’s page table.

EXERCISE D4. Does free_everything suffice to implement the memory freeing required by exit? Why or why not?

Offline Part E: Spawn

This and the following parts won’t be covered in section by default. They are optional practice to prepare for the problem set or exams. We suggest groups of students get together and work through them on their own.

In the first part, we start a new process in WeensyOS. Starting a new process requires a couple things: choosing a struct proc member of the ptable array, initializing memory, initializing registers, and marking the process as runnable. The fork system call in pset 3 phase 5 starts a process by copying an already-running process, but other interfaces are possible. The spawn interface, for example, starts a new process from scratch.

EXERCISE E1. The p-spawn.cc process tries to start another process—a copy of the p-alice program—by calling sys_spawn("alice"). Use make run-spawn (or make run-console-spawn, etc.) to run this program.

  1. The system call is not working. 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? Refer to the phases of pset 3.
  4. Does your implementation of syscall_spawn check its arguments for validity? If not, how would you change it to do this?

Offline Part F: Confused deputy

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. However, a system call asks the kernel to perform an operation on behalf of a process, making the kernel act as a privileged deputy. A confused deputy attack occurs if the process, by invoking system calls, can somehow convince the kernel to perform a function that violates process isolation.

EXERCISE F1. p-eve.cc and p-alice.cc may be familiar from class. Use make run-friends to run Alice and Eve together.

  1. It is possible to change one argument of one 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.