Problem set 4: 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.

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

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-f18-psets.git

Then run git pull handout master. This will merge our Assignment 4 code with your previous work. If you have any “conflicts” from Problem Set 3, 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 pset4 directory. You should see something like this, which shows four versions of the p-allocator process running in parallel:

Initial WeensyOS state

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.c file and reduce the ALLOC_SLOWDOWN constant.

Stop now to read and understand p-allocator.c. Here’s what’s going on in the physical memory display.

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

Physical memory map 1

Physical memory map 2

The virtual memory display is similar.

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:

Memory system layout

WeensyOS memory system layout is described by several constants.

KERNEL_START_ADDR Start of kernel code.
KERNEL_STACK_TOP Top of kernel stack. The kernel stack is one page long.
console CGA console memory.
PROC_START_ADDR Start of application code. Applications should not be able to access memory below PROC_START_ADDR, except for the single page at console.
MEMSIZE_PHYSICAL Size of physical memory in bytes. WeensyOS does not support physical addresses ≥ MEMSIZE_PHYSICAL. Equals 0x200000 (2MB).
MEMSIZE_VIRTUAL Size of virtual memory. WeensyOS does not support virtual addresses ≥ MEMSIZE_VIRTUAL. Equals 0x300000 (3MB).
PAGESIZE Size of a memory page. Equals 4096 (or, equivalently, 1 << 12).

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 (uintptr_t) console == 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.

Kernel isolation

Hints:

Step 2: Isolated address spaces

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

Per-process isolation

Thus, each process only has permission to access its own pages. You can tell this because only its own pages are shown in reverse video.

How to implement per-process page tables:

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 dark blue 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 needed to fill out the page table.

One common solution, shown above, leaves addresses above PROC_START_ADDR totally unmapped by default, but that’s not the only valid choice. 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:

Per-process isolation, alternate

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 call kalloc instead of kalloc_physical_page for process data. No calls to kalloc_physical_page should remain (and you can remove it from your source code).

Here’s how our OS looks after this step.

Virtual page allocation

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.

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 start from address 0x300000 == MEMSIZE_VIRTUAL. Now the processes have enough heap room to use up all of physical memory!

Overlapping address spaces

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 is one of Unix’s great ideas. It 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:

Initial fork state

This is because you haven’t implemented fork yet.

Implement fork.

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

Fork works

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:

Incorrect fork

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:

Shared read-only memory

Each process’s virtual address space begins with a dark-colored “S”, indicating that the corresponding physical page is Shared by multiple processes. (The color difference is only visible on graphical QEMU; the console version doesn’t distinguish between light reverse-video and dark reverse-video.)

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 do that, 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 combines two types of behavior:

The result is that once your code is correct, p-forkexit makes crazy patterns forever. An example:

Fork with exit

A fully correct OS can run p-forkexit indefinitely. If you reduce ALLOC_SLOWDOWN in p-forkexit, even rare errors should turn up within a minute or two.

Here’s your task.

There should be no memory leaks! (A memory leak will show up as a blank spot on the memory map that never gets used.) Remember that vmiter::map can fail if memory is low.

Extra credit

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

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.