This is not the current version of the class.

Kernel Section 1: WeensyOS

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 step 1 (links to the pset page will only work when pset 3 has been released).

Simultaneously enrolled college students are responsible for attending section live (in-person or via zoom). If you cannot attend any section live in a particular week, you may watch a recording (Canvas > Zoom > Cloud Recordings) instead. Please self-report your live attendance (or that you watched a recording) using this attendance form.

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 make run-hello to see the exciting result of the p-hello.cc program!

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.

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_startup 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 step 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 steps 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.

Offline Part G: Efficient communication

The central theme of Unit 3 is isolation and security, but kernels also can offer design features that transform overall 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.

EXERCISE G1. 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? How do their parameters differ from the parameters to analogous functions in Unix/Linux?
  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 might 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?

EXERCISE G2. 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.