Problem set 3: WeensyOS

In this assignment, you implement process memory isolation, virtual memory, and some system calls in a tiny operating system. This will introduce you to virtual memory and operating system design.

• Due Friday 10/25 11:59:59pm (extension 3 days later, Monday 10/28 11:59:59pm)
• You must run this assignment on a Linux machine, such as a virtual machine. Running on Mac or a Windows box without a VM is not likely to work.

You may want to ponder Chapter 9 of the text. The 64-bit x86 virtual memory architecture is described in Section 9.7. The PTE_P, PTE_W, and PTE_U bits are shown in Figure 9.23 and discussed in Section 9.7.1.

Get the code

Start with the cs61-psets repository you used for Problem Set 1.

First, ensure that your repository has a handout remote. Type

$ git remote show handout

If this reports an error, run

$ git remote add handout git://github.com/cs61/cs61-f19-psets.git

Then run

$ git pull; git pull handout master

This will merge our Problem Set 3 code with your previous work. If you have any “conflicts” from Problem Set 1, resolve them before continuing further. Run git push to save your work back to your personal repository.

You may also create a new cs61-psets repository for this assignment.

Don’t forget to enter your repository URL on the grading server.

Initial state

For this assignment, there is no handy make check functionality. Instead, you should run your instance of WeensyOS and visually compare it to the images you see below in the assignment.

Run make run in your pset3 directory. You should see something like this, which shows four versions of the p-allocator process running in parallel:

This image loops forever; in an actual run, the bars will move to the right and stay there. Don’t worry if your image has different numbers of K’s or otherwise has different details.

If your bars run painfully slowly, edit the p-allocator.cc file and reduce the ALLOC_SLOWDOWN constant. Stop now to read and understand p-allocator.cc.

Here’s what’s going on in the physical memory display.

• WeensyOS displays the current state of physical and virtual memory. Each character represents 4 KiB of memory: a single page. There are 2 MiB of physical memory in total. (How many pages is this?)
• WeensyOS runs four processes, 1 through 4. Each process is compiled from the same source code (p-allocator.c), but linked to use a different region of memory.
• Each process asks the kernel for more heap space, one page at a time, until it runs out of room. As usual, each process’s heap begins just above its code and global data, and ends just below its stack. The processes allocate space at different rates: compared to Process 1, Process 2 allocates space twice as quickly, Process 3 goes three times faster, and Process 4 goes four times faster. (A random number generator is used, so the exact rates may vary.) The marching rows of numbers show how quickly the heap spaces for processes 1, 2, 3, and 4 are allocated.

Here are two labeled memory diagrams, showing what the characters mean and how memory is arranged.

The virtual memory display is similar.

• The virtual memory display cycles between the four processes' address spaces. However, all the address spaces are the same for now.
• Blank spaces in the virtual memory display correspond to unmapped addresses. If a process (or the kernel) tries to access such an address, the processor will page fault.
• The character shown at address X in the virtual memory display identifies the owner of the corresponding physical page.
• In the virtual memory display, a character is reverse video if an application process is allowed to access the corresponding address. Initially, any process can modify all of physical memory, including the kernel. Memory is not properly isolated.

Goal

You will implement complete and correct memory isolation for WeensyOS processes. Then you'll implement full virtual memory, which will improve utilization. You'll implement fork—creating new processes at runtime—and exit—destroying processes at runtime.

We need to provide a lot of support code for this assignment, but the code you write will be limited. All your code goes in kernel.cc.

Notes

Running WeensyOS

If QEMU’s default display causes accessibility problems, you will want to run make run-console.

There are several ways to debug WeensyOS. We recommend:

• Add log_printf statements to your code (the output of log_printf is written to the file log.txt).

• Use assertions to catch problems early (for instance, call check_page_table to test a page table for obvious issues, or add your own).

• Sometimes a mistake will cause the OS to crash hard and reboot. Use make D=1 run 2>debuglog.txt to get additional verbose debugging output. Search through debuglog.txt for check_exception lines to see where the exceptions occur.

• Printouts such as assertions and fault reports include the virtual address of the faulting instruction, but they do not always include symbol information. Use files obj/kernel.asm (for the kernel) and obj/p-PROCESSNAME.asm (for processes) to map instruction addresses to instructions.

• You can track down the worst problems using infinite loops. Say that you’re not sure whether a reboot-causing problem occurs before or after line 100 in your fork function. So add an infinite loop at line 100! If the problem does occur, then the problem is located before line 100; if the OS hangs instead, then the problem is located after line 100.

Memory system layout

WeensyOS memory system layout is described by several constants.

Kernel and process address spaces

WeensyOS begins with the kernel and all processes sharing a single address space. This is defined by the kernel_pagetable page table. kernel_pagetable is initialized to the identity mapping: virtual address X maps to physical address X.

As you work through the pset, you will shift processes to use independent address spaces, where each process can access only a subset of physical memory.

The kernel, though, still needs the ability to access all of physical memory. Therefore, all kernel functions run using the kernel_pagetable page table. Thus, in kernel functions, each virtual address maps to the physical address with the same number. The exception_entry and syscall_entry assembly codes explicitly install kernel_pagetable when they begin, and exception_return and the syscall return path install the process’s page table as they exit.

Each process page table must contain kernel mappings for the kernel stack and for the exception_entry and syscall_entry code paths.

Step 1: Kernel isolation

WeensyOS processes could stomp all over the kernel’s memory if they wanted. Better stop that. Change kernel, the kernel initialization function, so that kernel memory is inaccessible to applications—except for the memory holding the CGA console (the single page at CONSOLE_ADDR == 0xB8000).

When you are done, WeensyOS should look like this. In the virtual map, kernel memory is no longer reverse-video, since the user can’t access it. Note the lonely CGA console memory block.

Use vmiter to create memory mappings. Start from the vmiter loop in the kernel() function.

Virtual memory iterators

The vmiter class examines and modifies x86-64 page tables, especially their virtual-to-physical address 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);


    // examine the current mapping:
    inline uintptr_t va() const;      // current virtual address
    inline uint64_t pa() const;       // current physical address
    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)?


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


    // change the mapping at the current address:

    // map current va to `pa` with permissions `perm`
    // Current va must be page-aligned. Calls kallocpage() 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);
};

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, moving one page at a time (the it += PAGESIZE expression increases it.va() by PAGESIZE).

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

The perm function returns a bitwise-or of flags, possibly including PTE_P (numeric value 1), PTE_W (numeric value 2), and PTE_U (numeric value 4). PTE_P marks Present pages (pages that are mapped). PTE_W marks Writable pages. PTE_U marks User-accessible pages—pages accessible to unprivileged processes. Kernel memory should be mapped with permissions PTE_P|PTE_W, which allows the kernel to read or write the memory, but prevents all access by processes.

The vmiter::map() function is used to add mappings to a page table. This line maps physical page 0x3000 at virtual address 0x2000, with permissions P, W, and U:

vmiter(pt, 0x2000).map(0x3000, PTE_P | PTE_W | PTE_U);

vmiter::map() panics if it cannot add a mapping (this usually happens if it fails to allocate memory for a page table page). If you want to check for errors instead, use try_map:

int r = vmiter(pt, 0x2000).try_map(0x3000, PTE_P | PTE_W | PTE_U);
if (r < 0) {
    // there was an error
}

vmiter can change a mapping’s permissions. This adds PTE_W to the permissions for virtual address va:

vmiter it(pt, va);
assert(it.present());
it.map(it.pa(), it.perm() | PTE_W);

In addition, make sure that your sys_page_alloc system call preserves kernel isolation: Applications shouldn’t be able to use sys_page_alloc to screw up the kernel. This requires changes to the SYSCALL_PAGE_ALLOC case in syscall. Read the description of sys_page_alloc in u-lib.hh to get a feeling for the possible errors.

Step 2: Isolated address spaces

Implement process isolation by giving each process its own independent page table. Your OS should look like this:

Each process only has permission to access its own pages, which you can tell because only its own pages are shown in reverse video.

How to implement per-process page tables:

• process_setup should allocate a new, initially-empty page table for the process. It will do this by calling kalloc (to allocate the level-4 page table page), and then calling memset (to ensure the page table is empty).

• Copy the mappings from kernel_pagetable into this new page table using vmiter::map. This step is to ensure that the required kernel mappings are present in the new page table. You can do this using a loop with two vmiters; or you can set the mappings yourself (they are identity mappings); or, if you’re feeling crazy, you can set up the new page table yourself without using vmiter (that will show you really understand page tables!).

  Note: vmiter::map will allocate level-1, level-2, and level-3 page table pages on demand.

• Then you will need to make sure that any page that belongs to the process is mapped as user-accessible. These are the pages the process needs to access, including its code, data, stack, and heap segments. There are several places you’ll need to change.

Note the diagram now has four pages for each process in the kernel area, starting at 0x1000. These are the four-level page tables for each process. (The colored background indicates that these pages contain kernel-private page table data, even though the pages “belong” to the process.) The first page was allocated explicitly in process_setup; the other pages were allocated by vmiter::map as the page table was initialized.

One common solution, shown above, leaves addresses above PROC_START_ADDR totally unmapped by default, but other designs work too. As long as a virtual address mapping has no PTE_U bit, its process isolation properties are unchanged. For instance, this solution, in which all mappings are present but accessible only to the kernel, also implements process isolation correctly:

If you create an incorrect page table, WeensyOS might crazily reboot. Don’t panic; see the debugging hints above.

Step 3: Virtual page allocation

So far, WeensyOS processes use physical page allocation for process memory: Process code, data, stack, and heap pages with virtual address X always use the physical pages with physical address X. This is inflexible and limits utilization.

Change your operating system to allocate all process data, including its code, globals, stack, and heap, using kalloc instead of direct access to the pages array.

Here’s how our OS looks after this step.

Virtual page allocation will complicate the code that initializes process code in process_setup. You’ll need to figure out why (hint: which page table is in force in process_setup?) and find a way around it (hint: vmiter or set_pagetable).

Step 4: Overlapping address spaces

Now the processes are isolated, which is awesome, but they’re still not taking full advantage of virtual memory. Isolated address spaces can use the same virtual addresses for different physical memory. There’s no need to keep the four process address spaces disjoint.

In this step, change each process’s stack to grow down starting at address 0x300000 == MEMSIZE_VIRTUAL. Now the processes have enough heap room to use up all of physical memory!

If there’s no physical memory available, sys_page_alloc should return an error to the caller (by returning -1). (If you want, you can also print “Out of physical memory!” or something to the console; you don’t need to.)

Step 5: Fork

The fork system call starts a new process as a copy of an existing process. The fork system call appears to return twice, once to each process. To the child process, it returns 0. To the parent process, it returns the child’s process ID.

Run WeensyOS with make run or make run-console. At any time, press the ‘f’ key. This will soft-reboot WeensyOS and ask it to run a single p-fork process, rather than the gang of allocators. You should see something like this:

This is because you haven’t implemented fork yet.

Implement fork.

• When a process calls fork, look for a free process slot in the ptable[] array. Don’t use slot 0. If no slot exists, return -1 to the caller.

• If a free slot is found, make a copy of current->pagetable, the forking process’s page table, for the child.

• But you must also copy the process data in every application page shared by the two processes. The processes should not share any writable memory except the console (otherwise they wouldn’t be isolated). So fork must examine every virtual address in the old page table. Whenever the parent process has an application-writable page at virtual address V, then fork must allocate a new physical page P; copy the data from the parent’s page into P, using memcpy; and finally map page P at address V in the child process’s page table.

• The child process’s registers are initialized as a copy of the parent process’s registers, except for reg_rax.

When you’re done, you should see something like this after pressing ‘f’.

An image like this means you forgot to copy the data for some pages, so the processes are actually sharing stack and/or data pages:

Step 6: Shared read-only memory

It’s wasteful for fork() to copy all of a process’s memory. For example, most processes, including p-fork, never change their code. So what if we shared the memory containing the code? That’d be fine for process isolation, as long as neither process could write the code.

Change the process loader to map read-only program segments using read-only memory. Use the program_loader::writable() function (loader.writable() in context) to detect whether a program segment can use read-only memory. Then, in fork, share read-only pages between processes rather than copying them.

When you’re done, running p-fork should look like this:

Each process’s virtual address space begins with an “S”, indicating that the corresponding physical page is Shared by multiple processes.

Step 7: Freeing memory

So far none of your test programs have ever freed memory or exited. Memory allocation’s pretty easy until you add free! So let’s add free by allowing applications to exit.

In this exercise you’ll implement the sys_exit system call, which exits the current process. This exercise is a capstone since freeing memory will tend to expose weaknesses and problems in your other code.

To test your work, use make run and then type ‘e’. This reboots WeensyOS to run the p-forkexit program. (Initially it’ll crash because sys_exit() isn’t implemented yet.) p-forkexit processes all alternate among forking new children, allocating memory, and exiting. The result is that once your code is correct, p-forkexit makes crazy patterns forever, like this:

A fully correct OS can run p-forkexit indefinitely. An OS with a memory leak will display a persistent blank spot in the physical memory map—the leaked page—and if run long enough, blank spots will take over the screen. This OS has a pretty bad leak; within 10 seconds it has run out of memory:

This OS’s leak is slower, but if you look at the bottom row of the physical memory map, you should see a persistently unused pages just above and to the left of the “V” in “VIRTUAL”. Persistently unused pages are a hallmark of leaks.

Reducing ALLOC_SLOWDOWN in p-forkexit may encourage errors to manifest, but you may need to be patient.

Here’s your task.

1. Complete kfree so that kfree frees memory.

2. Change kalloc so that it can reuse freed memory. (In the handout code, kalloc will never reuse freed memory!)

3. sys_exit should mark a process as free and free all of its memory. This includes the process’s code, data, heap, and stack pages, as well as the pages used for its page directory and page table pages. The memory should become available again for future allocations.

   Use vmiter and ptiter (see below) to enumerate the relevant pages. But be careful not to free the console. Also, don’t free any shared pages until they are totally unused (the last sharing process exits)!

4. You will also need to change fork and perhaps other places. Think about all the places that allocate or share memory: what information must they maintain? In p-forkexit, unlike in previous parts of the pset, sys_fork and sys_page_alloc can run when there isn’t quite enough memory to create a new process or allocate or map a page. Your code should handle this cleanly, without leaking memory in any situation.

   • If there isn’t enough free memory to successfully complete sys_page_alloc, the system call should return -1 to the caller.

   • If there isn’t enough free memory to successfully complete sys_fork, the system call should clean up (i.e., free any memory that was allocated for the new process before memory ran out), and then return -1 to the caller.

There should be no memory leaks!

Ptiter

The ptiter type also iterates through page tables, but it returns page table memory rather than mappings. This is useful mostly when freeing page table structures.

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
    inline int level() const;               // current level (0-2)

    // 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.end_va(), it.kptr());
}

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.

Extra credit

If you are finished and can't wait to do more of this type of work, try:

• Copy-on-write page allocation!

• Write more system calls and test programs! Some ideas:

  • sys_page_alloc is like a restricted mmap system call: the user always defines where the page lives (so addr == nullptr is not supported), the system call allocates exactly one page (so sz == PAGESIZE always), and the map is copied when a process forks (so the flags are like MAP_ANON | MAP_PRIVATE and the protection is PROT_READ | PROT_WRITE | PROT_EXEC). Eliminate some of these restrictions by passing more arguments to the kernel and extending the SYSCALL_PAGE_ALLOC implementation.

  • Implement sys_page_free/munmap.

  • Implement a system call that puts the calling process to sleep until a given amount of time has elapsed, as measured by ticks (which counts timer interrupts).

  • Implement a kill system call that lets one process kill others!

  You will need to write a new test program to test this functionality.

  How to write a new test program

  1. Run git pull handout master or equivalent to ensure you’re using our latest code (you need commit 2badb947).
  2. Choose a name for your test program. We’ll assume testprogram for this example.
  3. Create a C++ file p-testprogram.cc for your test program. You will base this file off one of the existing programs (p-allocator.cc, p-fork.cc, or p-forkexit.cc).
  4. Modify GNUmakefile to build your test program: add $(OBJ)/p-testprogram to the PROCESS_BINARIES definition, and $(OBJ)/p-testprogram.o to the PROCESS_OBJS definition.
  5. Teach the program_loader about your test program. Look for program_loader code in k-hardware.cc. Then add declarations for _binary_obj_p_testprogram_start and _binary_obj_p_testprogram_end, and add the appropriate entry to the ramimages array.

  6. Teach check_keyboard in k-hardware.cc about your program. Pick a keystroke that should correspond to your program and edit the “soft reboot process” accordingly. For instance:

       if (c == 'a') {
           argument = "allocators";
       } else if (c == 'e') {
           argument = "forkexit";
       } else if (c == 't') {
           argument = "testprogram";
       }
     

  7. Teach the kernel() function in kernel.cc about your program. Replace the current if (command...) statements with this:

       if (command && program_loader::program_number(command) > 0) {
           process_setup(1, program_loader::program_number(command));
       } else {
           // ... set up allocator processes ...
       }
     

     (This only needs to be done once, for the first test program you add.)

  Now you should be able to run your test program by typing t.

Turnin

You will turn in your code by pushing your git repository to github.com/cs61/YOUR-PSET_REPO.git and updating the grading server.