Ancient CS 61 Content Warning!!!!!1!!!
This is not the current version of the class.
This site was automatically translated from a wiki. The translation may have introduced mistakes (and the content might have been wrong to begin with).

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

We will update this problem set description. You may also want to ponder Chapter 9 of CS:APP2e. The 32-bit x86 virtual memory architecture is described in Section 9.6.3. The PTE_P, PTE_W, and PTE_U bits are mentioned in Section 9.7.1.

Get the code

Start with the cs61-psets Git repository you created for Assignment 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://code.seas.harvard.edu/cs61/cs61-psets.git

Then run git pull handout master. This will merge our Assignment 3 code with your previous work. If you have any “conflicts” from Assignment 1, resolve them before continuing further. Run git push to save your work back to code.seas.

You may also create a new cs61-psets repository for this assignment. You’ll need to tell us if you do.

Initial state

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:

File:fig-memos-initial.gif

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.

File:fig-memos-physmap.gif
File:fig-memos-physmap2.gif

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. Finally, for extra credit, you'll implement exit.

We need to provide a lot of support code for this assignment, but the code you write will be limited. Our solutions contain less than 200 lines. All your code goes in kernel.c (except for part of step 6).

Notes

Running WeensyOS

Read the README-OS.md file for information on how to run WeensyOS. If QEMU’s default display causes accessibility problems, you will want to run make run-console. To make run-console the default, run export QEMUCONSOLE=1 in your shell. We recommend make run-gdb for debugging, as well as adding log_printf statements to your code (the output of log_printf is written to the file log.txt).

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).
NPAGES Number of physical pages. Equals MEMSIZE_PHYSICAL / PAGESIZE.
MEMSIZE_VIRTUAL Size of virtual memory. WeensyOS does not support virtual addresses ≥ MEMSIZE_VIRTUAL. Equals 0x300000 (3MB).

Kernel and process address spaces

WeensyOS begins with the kernel and all processes sharing a single address space. This is defined by the kernel_pagedir page directory. kernel_pagedir 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 using their own independent address spaces. Only a subset of physical memory is accessible through any individual process’s address space.

The kernel, though, still needs the ability to access any location in physical memory. Therefore, all kernel functions use the kernel_pagedir page directory, and in kernel functions, each accessible virtual address has the same numeric value as the corresponding physical address. Code in interrupt explicitly installs kernel_pagedir on entry.

There is one exception—after Step 2 and before Step 3, the kernel can’t necessarily access all of physical memory. Why?

WeensyOS system calls are more expensive than they need to be, since every system call switches address spaces twice (once to kernel_pagedir and once back to the process’s page directory). Real operating systems avoid this overhead. In real OSes kernels access memory using process page directories, rather than a kernel-specific kernel_pagedir. This makes the kernel code more complicated, since kernels can’t always access all of physical memory directly.

Step 1: Kernel isolation

WeensyOS processes could stamp all over the kernel’s memory if they wanted. Better stop that. Change start, 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.

File:fig-memos-kernelprot.gif

Hints:

Step 2: Virtual page allocation

You could also do step 3 first.

So far, WeensyOS processes use physical page allocation: the page with physical address X is used to satisfy the sys_page_alloc(X) allocation request for virtual address X. This is inflexible and limits utilization. Change the implementation of the INT_SYS_PAGE_ALLOC system call so that it can use any free physical page to satisfy a sys_page_alloc(X) request.

Your new INT_SYS_PAGE_ALLOC code must perform the following tasks.

Don’t modify the page_alloc helper function, which is also used by the program loader. You can write a new function if you want.

Here’s how our OS looks after this step.

File:fig-memos-virtual.gif

Hints:

Step 3: Isolated address spaces

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

File:fig-memos-isolated.gif

What goes in per-process page directories:

File:fig-memos-isolated2.gif

The reverse video shows that this OS also implements process isolation correctly.

How to implement per-process page directories:

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!

File:fig-memos-overlapping.gif

(Our solution prints “Out of physical memory!” to the console when a sys_page_alloc fails for that reason. You don’t need to implement this.)

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:

File:fig-memos-forkinitial.gif

This is because you haven’t implemented fork yet.

Implement fork.

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

File:fig-memos-fork.gif

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:

File:fig-memos-badfork.gif

Step 6: Shared read-only memory

You must complete at least one of Step 6 and Step 7. Step 6 is easier.

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 in k-loader.c to detect read-only program segments and map them as read-only for applications (PTE_P|PTE_U). A program segment ph is read-only iff (ph->p_flags & ELF_PFLAG_WRITE) == 0.

Your fork() code shouldn’t copy shareable pages, but it should keep track of the number of active references to each user page. Specifically, if pageinfo[pn].refcount > 0 and pageinfo[pn].owner > 0, then pageinfo[pn].refcount should equal the number of times pn is mapped in process page directories.

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

File:fig-memos-sharedreadonly.gif

Each process’s virtual address space begins with a darker-colored “1”. The dark color indicates that the corresponding physical page has reference count (refcount) greater than 1. (The color difference is only visible on graphical QEMU; the console version doesn’t distinguish between light reverse-video and dark reverse-video.)

Hint:

Step 7 (Optional/Extra Credit): 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.

We hope everyone tries this exercise, but it is optional, and definitely harder than the others. 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:

File:fig-memos-forkexit.gif

Here’s your task.

The virtual_memory_check function, which runs periodically, should help catch some errors. Feel free to add checks of your own.

More extra credit ideas

Turnin

You will turn in your code by pushing your git repository to code.seas.harvard.edu.


This pset was created for CS61, Fall 2012, completely revised from “minilabs” written for classes at UCLA.