cs24-21fa Project 05a: weensyos

Introduction to Computing Systems (Fall 2021)

Introduction

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

Setup

Like usual, you should register for the assignment by going to https://grinch.caltech.edu/register which will create you a repository on gitlab with the starter code.

For this assignment, there are no handy gitlab tests. Instead, you should run your instance of Weensy OS and visually compare it to the images you see below in the assignment.

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

To shutdown WeensyOS, just type Control-C and the window should go back to being a terminal.

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.

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.

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.

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. In fact, you don’t need to read any of the other files!

Notes

Running WeensyOS

There are several ways to debug WeensyOS. We recommend adding log_printf statements to your code (the output of log_printf is written to the file log.txt), and use assertions to catch problems early (for instance, call check_page_table to test a page table for obvious issues).

Memory system layout

WeensyOS memory system layout is described by several constants.

Constant Description
KERNEL_START_ADDR Start of kernel code.
KERNEL_STACK_TOP Top of kernel stack. The kernel stack is one page long.
CONSOLE_ADDR 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_ADDR.
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 assignment, 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 can currently stomp all over the kernel’s memory if they want to! Better stop that.

Currently, the kernel has the following two lines:

memory_foreach(kernel_pagetable, MEMSIZE_PHYSICAL, map_to_user_space);
map_to_nobody(kernel_pagetable, (uintptr_t)NULL);

The first line sets the permissions for the memory in the kernel_pagetable starting at 0 and ending at MEMSIZE_PHYSICAL to be accessible in userspace. The second line remaps address 0 (the NULL pointer) to be accessible to nobody.

Checking Your Output

When you have edited the mappings correctly, WeensyOS should look like the following picture. 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.

Step 2: Isolated Address Spaces

Now that the kernel is isolated from the user processes, we’d like to isolate the user processes from each other. To do this, we’ll need to give each process its own independent page table instead of sharing the kernel_pagetable across all of them. We’ll need to edit several distinct functions this time.

Checking Your Output

When you have completed these steps, WeensyOS should look like the following picture. Each process only has permission to access its own pages, which you can tell because only its own pages are shown in reverse video.

Step 3: Virtual Page Allocation

Right now, WeensyOS allocates pages using physical page allocation; that is, all virtual addresses map directly to the same physical address. This is not how virtual memory is usually allocated. One of the reasons we use virtual memory in the first place is to allow a more flexible address mapping. Furthermore, as you will see in the next step, processes should be allowed to have overlapping memory spaces (which is obviously not possible if we use physical page allocation).

Once you complete this step, you will likely be greeted by a kernel that infinitely reboots…

Checking Your Output

When you have completed these steps, WeensyOS should look like the following picture. Note that the physical pages are allocated in order, but the virtual pages look the same as they did before.

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. Interestingly, you’ve already done all the hard work!

Checking Your Output

When you have completed these steps, WeensyOS should look like the following picture. Note that the stacks always appear in the same place and the 3’s and 4’s go past their original rows.

Acknowledgements

This project (and WeensyOS) were originally developed for Harvard’s CS 61 course by Eddie Kohler. We’ve used it with permission.

Submit OpenEndeds For Credit