« Back to the main CS 131 website

Project 3: WeensyOS

Introduction

Virtual memory is a component of the operating system that helps the OS safely run multiple applications atop the same physical memory (the computer’s RAM). Each process gets its own virtual memory address space, and these virtual addresses are mapped to specific physical addresses. This gives the process an illusion of a contiguous memory space in which only its data exists.

The kernel is the core program of the OS that runs with full machine privilege to manage processes and their virtual memory. Its main goals are to fairly share machine resources among processes, and provide convenient and safe access to the hardware while protecting the OS from malicious programs.

Almost all modern operating systems use virtual memory (for example, since Windows XP and the original Mac OS X, you can’t turn off virtual memory – it’s always on!). In this assignment, you will write OS kernel code that implements the virtual memory architecture and a few important system calls for a small operating system called WeensyOS. The WeensyOS supports 3MB of virtual memory on top of 2MB of physical memory.

In order to implement full virtual memory with complete and correct memory isolation, you will need to interact with page tables, kernel and user memory spaces, processes, and virtual and physical memories. All of these topics are important to know as you become more familiar with operating systems.

Learning Objectives

This project will help you:

Conceptual Questions

General Questions
DUE: April 3

  1. What is the disadvantage of having an identity mapping between virtual and physical memory? What is the purpose of mapping virtual memory addresses to different physical addresses?
  2. The OS kernel is privileged because it can access any memory in the computer and grant or deny user processes access to hardware resources such as memory or CPU time. Why do we give the kernel so much more power than we give to user processes? Give two specific examples of ways in which the OS kernel uses its privilege to the benefit of user processes.

Project Specific Questions
DUE: April 10
Focus on the life cycle of a process in WeensyOS. Specifically, answer the following questions:

  1. How does a new page table get prepared for a new process? Talk both about processes born from fork() and those not born from fork().
  2. During the normal execution of the process, how does the process refer to its memory? Go through an example of translating a virtual memory address to an actual physical memory address.
  3. Upon exiting, what kind of resources have to be cleaned up and freed?

Assignment installation

You must run this assignment on a Linux machine, such as your course VM. Running on Mac OS X, on Windows without a VM, or on the department machines is unlikely to work!

Ensure that your project repository has a handout remote. Type:

$ git remote show handout

If this reports an error, run:

$ git remote add handout https://github.com/csci1310/cs131-s20-projects.git

Then run:

$ git pull
$ git pull handout master

This will merge our Project 3 (WeensyOS) stencil code with your repository.

Once you have a local working copy of the repository that is up to date with our stencils, you are good to proceed. You’ll be doing all your work for this project inside the weensyOS directory in the working copy of your projects repository.

Infrastructure Help

Stencil and Initial State

Running WeensyOS:

WeensyOS can, in principle, run on any computer with an x86-64 CPU architecture (like yours, most likely). For this assignment, however, you will run the OS in QEMU, a CPU emulator. QEMU makes it possible to easily restart and debug WeensyOS.

To run WeensyOS, run:

You may receive an error telling you to install a package called qemu-system-x86 in your course VM. If so, go ahead and install it using the command quoted in the error message (sudo apt-get -y install qemu-system-x86).

Once make succeeds, you should see something like the image below, which shows four processes running p-allocator.cc 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, you can edit the p-allocator.cc file and reduce the ALLOC_SLOWDOWN constant.

What’s happening?

Take a moment to read and understand what p-allocator.cc is doing.

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:

Make sure to understand the organization of process data — for each process, the leftmost pages at the lowest address contain its code and global variables (corresponds to text, data, and bss segments). Following those, we have a few pages for the heap. Finally, the rightmost page at the highest address is the stack.

The virtual memory display is similar:

Notes on WeensyOS

Memory System Layout

The WeensyOS memory system layout is described by the following constants:
KERNEL_START_ADDR Start of kernel code. Equals 0x40000.
KERNEL_STACK_TOP Top of kernel stack (the kernel stack is one page long). Equals 0x80000.
CONSOLE_ADDR CGA console memory. Equals 0xB8000. Values written to this page get printed in the terminal. All processes have read/write access to this page.
PROC_START_ADDR Start of application code. Applications should not be able to access memory below PROC_START_ADDR, except for the single page of console memory. Equals 0x100000 (1MB).
MEMSIZE_PHYSICAL Size of physical memory. 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). 
INITIAL PHYSICAL MEMORY LAYOUT

  +-------------- Base Memory --------------+
  v                                         v
 +-----+--------------------+----------------+--------------------+---------/
 |     | Kernel      Kernel |       :    I/O | App 1        App 1 | App 2
 |     | Code + Data  Stack |  ...  : Memory | Code + Data  Stack | Code ...
 +-----+--------------------+----------------+--------------------+---------/
 0  0x40000              0x80000 0xA0000 0x100000             0x140000
                                             ^
                                             | \___ PROC_SIZE ___/
                                      PROC_START_ADDR

In WeensyOS, the physical memory is divided into units called pages, where a page is a contiguous memory of 212 bytes (0x1000, or 4096). Kernel memory starts at 0x40000 (KERNEL_START_ADDR), and process memory starts at 0x100000 (PROC_START_ADDR). Each process has a distinct region of memory that is0x40000 (PROC_SIZE) in size.

Optional: How does CGA console memory work?

Processes can write to 0xB8000 (CONSOLE_ADDR), which, as you can see in the display, is in the reserved memory region. Writing a 2-byte value to this particular page causes the value to be printed on the terminal. This is called memory-mapped I/O — a technique of performing I/O operations between the CPU and the I/O device through reads and writes to a shared region of memory. Different operating systems implement memory-mapped I/O differently, but in WeensyOS, any user process can modify the screen because all user processes have read/write access to this single page of console memory. CGA, or Color Graphics Adapter, is just a type of graphics card used in WeensyOS!

Relevant Files

We provide a lot of support code for the WeensyOS, but the code you write will be limited. Don’t be overwhelmed by the stencil files! Take a look at README-OS.md for more information on the organization of the OS, but you don’t have to read through or understand all the files to complete this project. Here is a table summarizing relevant files that you may want to look at (but definitely feel free to browse through the entire codebase if you’re curious!):
kernel.hh Declares constants and function headers for the kernel. Some of these kernel functions are implemented in kernel.cc (while others are in k-hardware.cc)
kernel.cc The core of the kernel program. You will be editing this file throughout the assignment.
u-lib.hh User-space library with system call specifications and implementations. Your user-space processes can call functions in this file.
k-vmiter.hh Defines iterators for x86-64 page tables. The vmiter enumerates virtual memory mappings, while ptiter visits individual page table pages.

Here’s a diagram of how these files fit together! u-lib.hh will invoke system calls which are defined in kernel.{hh, cc}. These functions will use the vmiter and ptiter defined in k-vmiter.hh.

+--------------+               +------------------------------------------+
|  User Space  |               |               Kernel Space               |
|              |               |                                          |
|              |  syscall      |                                          |
|  u-lib.hh +---------------------> kernel.{hh, cc}                       |
|              |               |       +                                  |
+--------------+               |       |  page iteration                  |
                               |       +--------------------> k-vmiter.hh |
                               |                                          |
                               |                                          |
                               +------------------------------------------+

In addition to these, it will be useful to know the three permission flags for pages defined in x86-64.h:

Some tips for navigating the code base:
For this project and its large stencil, using an IDE, such as CLion and VSCode may be helpful — these IDEs help you click through function definitions and declarations, look up usages of variables and functions, and navigate through the extensive codebase.

Additionally, and especially if you are using a simple editor, it can be useful to run a recursive grep command in your terminal to explore the code. For example, you could look for instances of the keyword kernel_pagetable as follows (run the command inside your WeensyOS directory):

$ grep -rn "kernel_pagetable"
kernel.cc:69:    for (vmiter it(kernel_pagetable); it.va() < MEMSIZE_PHYSICAL; it += PAGESIZE) {
kernel.cc:157:    ptable[pid].pagetable = kernel_pagetable;
k-exception.S:94:        movq $kernel_pagetable, %rax
k-exception.S:174:        movq $kernel_pagetable, %rax
kernel.hh:97:extern x86_64_pagetable kernel_pagetable[];
[...]

This will search in the directory for kernel_pagetable and return every instance where it appears with file names and line numbers. Note that some auto-generated files also contain symbols; you may have an easier time if you run make clean before grepping.

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. The kernel_pagetable is initialized to the identity mapping: virtual address X maps to physical address X.

As you work through the project, 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.

There also must be a mechanism to transfer control from a user process to the kernel program when traps, interrupts, or faults occur so that the kernel can take appropriate actions on behalf of the process that produced those events. This is done in x86-64 and WeensyOS through a mechanism called protected control transfer, where the process switches to the pre-configured exception entry and kernel stack. This is why the process page table must contain kernel mappings for the kernel stack and for exception and syscall entry code paths.

Optional: How does protected transfer control work?

In x86-64 and WeensyOS, the kernel configures entry points for protected control transfer: one entry point for each trap, each interrupt, and each fault. When these events happen, the processor must switch to the pre-configured kernel entry before transferring control — this is why each process page table must contain kernel mappings for the kernel stack and for the exception_entry and syscall_entry code paths, which are defined in k-exception.S. In this file, you can see that the exception_entry and syscall_entry assembly codes install kernel_pagetable when they begin, and exception_return and the syscall return path install the process’s page table upon exiting.

As a concrete example, suppose a user process invokes the sys_page_alloc system call (all of the user-facing system calls are defined in u-lib.hh). This is also the system call that is used in p-allocator.cc to ask for more heap space.

System calls are a type of traps, so the process needs to transfer control to the kernel so that the kernel can perform the system call on behalf of the process. First, sys_page_alloc invokes make_syscall and passes the SYSCALL_PAGE_ALLOC, the system call number for sys_page_alloc. This will get us to the syscall_entry assembly code in k-exception.S, which calls the syscall function in kernel.cc. We’ve now switched to the kernel! You can see in this function that there is a case for SYSCALL_PAGE_ALLOC, which in turn calls the syscall_page_alloc helper function that finally handles the system call. Upon returning, the syscall_entry assembly code in k-exception.S loads back the process’s page table, and returns to the process.

Assignment Roadmap

It may help to complete Lab 5 (Introduction to WeensyOS) before you attempt to work on this project. Doing so isn’t strictly required (the lab and project are independent), but the lab will get you familiar with the codebase and helpers we provide.

Goal

You will first implement complete and correct memory isolation for WeensyOS processes. After that, you will implement full virtual memory, which will improve memory utilization. Lastly, you will implement the fork system call — creating new processes at runtime — and the exitsystem call — destroying processes at runtime. We do not provide unit or system tests for this project. Verify that you’re on the right track for each step of the assignment by running your instance of WeensyOS and visually comparing it to the images you see below.

All the code you write goes into kernel.cc.

Note: Kernel programming is rough, as any mistake may cause your (emulated) computer to crash with no way to recover. We understand how frustrating this can be, but if you find yourself struggling to find a bug, please do not be discouraged! The best debugging technique is to double-check your conceptual understanding. Go through the logic of your code (there should not be a lot of lines of code for each step), and make sure that the change you’re making to the kernel makes sense to you. The second-best debugging technique is to put calls to log_printf into your code, which will write to a file called log.txt in your WeensyOS directory. Check out our debugging section for additional debugging tips as well!

Step 1: Kernel Isolation

Overview:
Currently, the processes and the kernel share the same single address space by sharing a single page table—kernel_pagetable—and the processes can easily access the kernel memory. You will need to implement kernel isolation so that kernel memory is inaccessible from user processes.

Specifications
How should WeensyOS look when you're done?

When you’re done, your WeensyOS should look like the following:

Notice how the kernel memory is no longer reverse-video since the user processes can’t access it, but the lonely single page of CGA console memory is still reverse-video.

Hints

Look into vmiter to create memory mappings with appropriate permissions. Take a look at the vmiter loop in the kernel function.

Step 2: Process Isolation

Overview:
The processes can no longer access the kernel memory, but they are still sharing the same address space by having access to the kernel-pagetable. Give each process its own independent page table so that it has permission to access only its own pages.

Specifications
How should WeensyOS look when you're done?

Once you’re done, your WeensyOS should look like the following:

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

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 for the top-level page table was allocated explicitly in process_setup; the other pages were allocated by vmiter::map as the page table was initialized.

Hints

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:

Step 3: Virtual Page Allocation

Overview:
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. For this step, we’re going to support virtual page allocation.

Specifications
How should WeensyOS look when you're done?

Here’s how your OS should look like after this step:

Hints

Step 4: Overlapping Virtual Address Spaces

Overview:
Now the processes are isolated, but they’re still not taking full advantage of virtual memory. Isolated processes don’t have to use disjoint addresses for their virtual memory. You’re going to change each process to use the same virtual addresses for different physical memory.

Specifications
How should WeensyOS look when you're done?

Notice how the processes now have enough heap room to use up all of physical memory:

Hints

Step 5: Fork

Overview:
The fork system call creates a new child process by duplicating the calling parent process. The fork system call appears to return twice, once to each process — it returns 0 to the child process, and it returns the child’s process ID to the parent process.

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 create a single process running p-fork.cc, rather than the gang of processes running p-allocator.cc. You should see something like this:

The kernel panics because you haven’t implemented WeensyOS’s version of fork. Your new task is to fill in the syscall_fork function in kernel.cc! This is a helper function that gets called when the system call sys_fork is invoked.

Specifications
How should WeensyOS look when you're done? 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:

Hints

Step 6: Shared Read-Only Memory

Overview:
It is wasteful for fork to copy all of a process’s memory because most processes, including p-fork, never change their code. 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.

Specifications
How should WeensyOS look when you're done? When you're done, running `p-fork` should look like the image below:

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

Hints

Step 7: Exit

Overview:
So far none of your test programs have ever freed memory or exited. In this last step, you will need to support WeensyOS version of the exit system call. This allows the current process to free its memory and resoruces and exit cleanly and gracefully.

Run make run or make run-console, and at any point, press the “e” key. This reboots WeensyOS and start running the p-forkexit.cc program. The p-forkexit processes all alternate among forking new children, allocating memory, and exiting. Your WeensyOS should initially panic because you have not implemented syscall_exit in kernel.cc yet!

Specifications
How should WeensyOS look when you're done?

Once you’re done, p-forkexit program will make 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.

There should be no memory leaks!

Hints

Extra Credit

If you are finished and can’t wait to do more of this type of work, here are some more features you can add.

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

How to write a new test program
  1. Choose a name for your test program. We’ll assume testprogram for this example.
  2. 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).
  3. 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.
  4. 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.
  5. 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";
  }
  1. 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.

Note: You can get a perfect score for this project (and in the course in general) without doing any extra credit work. If you do extra credit work, it may compensate for lost credit elsewhere, but it serves primarily for your enjoyment and education. Keep in mind that we may not be able to help you with the extra credit section in TA hours.

Debugging Resources / GDB

There are several ways to debug WeensyOS. We recommend:

Handing In & Grading

Handin instructions

As before, you will hand in your code using Git. In the weensyOS/ subdirectory of your project repository, you MUST fill in the text file called README.md.

Due to the COVID-19 outbreak, we have lifted the March 13 deadline for steps 1-4 of the project and the general conceptual questions.

Steps 1-4 and the general conceptual quetions will be due on April 3rd now, and the rest of the project on April 10.

By 6:00pm on April 3rd, you must have a commit with steps 1-4 and the general conceptual questions completed.
By 6:00pm on April 10th, you must have a commit with all steps and conceptual questions completed (general and project specific).

Remind me again what the README.md should contain?

Grading breakdown

Now head to the grading server, make sure that you have the “WeensyOS” page configured correctly with your project repository, and check that your WeensyOS runs on the grading server as expected.

Congratulations, you’ve completed the third CS 131 project, and written part of your own operating system! :computer: :+1:

Acknowledgements: WeensyOS and this project were originally developed for Harvard’s CS 61 course. We are grateful to Eddie Kohler for allowing us to use the assignment for CS 131.