« Back to the main CS 300 website

Project 4: WeensyOS

Steps 1-4 Due Friday, April 5th at 6:00 PM EDT
All Steps Due Friday, April 12th at 6:00 PM EDT

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:

• Understand the user vs. kernel privilege split.
• Understand the design and implementation of virtual memory.
• Understand process creation and cleanup.

Question to Think About

Note: You are not required to answer the following questions to complete WeensyOS, and they will not affect your grade for the project. They exist to help you think about how you might want to design your implementation for WeensyOS. If you’re failing tests or stuck debugging, these questions can help you think about edge cases you might not be accounting for!

1. What is the disadvantage of having an identity mapping (where each virtual address is mapped onto the same physical address) between virtual and physical memory? What is the purpose of mapping virtual memory addresses to different physical addresses?
2. 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().
3. 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.
4. Upon exiting, what kind of resources have to be cleaned up and freed?

Assignment installation

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/csci0300/cs300-s24-projects.git

Then run:

$ git pull
$ git pull handout main

This will merge our Project 4 (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.

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:

• make run in the directory containing the project stencil.
• OR make run-console if QEMU’s default display causes accessibility problems.

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 grow 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:

• WeensyOS displays the current state of physical and virtual memory. Each character represents 4KiB (4096 bytes) of memory: a single page. There are 2 MiB of physical memory in total.
• WeensyOS runs four processes, 1 through 4. Each process is compiled from the same source code (p-allocator.cc), but linked to use a different region of memory.
• Each process uses the sys_page_alloc() system call to ask 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:

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 and data 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:

• The virtual memory display cycles between the four processes' address spaces. Notice, however, that initially all the address spaces are the same because all processes share the same single address space.
• 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.
  • Initially the virtual memory and physical memory have identity mapping: virtual address X always uses the page at physical address X. You can see this happen, for example, in syscall_page_alloc() –- given the virtual address addr, the function allocates the page at addr. This is why the growing heaps of the four processes in the virtual memory match with the physical memory display.
• In the virtual memory display, a character is reverse-video if an application process is allowed to access the corresponding address. Reverse video simply means that the background and text color values are inverted (black letter on colored background). Initially, any process can modify all of physical memory, including the kernel. This implies that memory is not properly isolated!

Notes on WeensyOS

Memory System Layout

The WeensyOS memory system layout is described by the following constants:

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 2¹² 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.

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!):

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:

• PTE_P should be set if a page is present in a page table
• PTE_W should be set if a page is writable
• PTE_U should be set if a page is user-accessible

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.

Assignment Roadmap

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.

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.

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.

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.

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.

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.

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!

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! This extra credit work is not required to get an A, unless you are a graduate student taking CSCI 1310, in which case you should complete at least one of the below extra credit ideas:

For each of these additions, you will need to create new test programs to test your new functionality!

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

Kill System Call

Easy. Create a system call that lets one process kill another process (or itself)!

Sleep System Call

Easy. Create a system call that puts the calling process to sleep until a given amount of time (measured in ticks) elapses. Note that ticks will count timer interrupts!

Free System Call

Moderately difficult. Create sys_page_free, a system call that unallocates pages. It should behave like munmap.

Expand sys_page_alloc

Moderately difficult. Currently, sys_page_alloc is like a more restrictive version of mmap. 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. 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 to extend the SYSCALL_PAGE_ALLOC implementation.

Copy-on-Write Page Allocation

Difficult. Usually, all non-read only memory pages get copied over to a child process when fork is called. Instead, have the child process and parent process share the same physical memory page, until one process writes to that memory. When this happens, copy the data into physical memory and have the other process map it!

Debugging

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).
• 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 (e.g., the state of CPU registers at the point of crashing). 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.

GDB

You can run gdb using the following steps:

1. Open two console windows - one for the WeensyOS display, one for GDB
2. In the first console, run the command make run-gdb. This boots the tiny operating system and waits for you to connect to it with GDB. You should see "VGA Blank mode" written on a black screen.
3. In the second console, run gdb -x build/weensyos.gdb to connect GDB to the running emulated computer. Enter c to continue. Now you can set breakpoints anywhere in the kernel code (e.g., b syscall_page_alloc). Then, enter c to start the WeensyOS process with GDB. At this point, the first console should be running WeensyOS normally.

We can now debug the whole emulated computer as if it were a single process (which, actually, it is).

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.

By 6:00pm on Friday, April 7th, you must have a commit with steps 1-4 completed. By 6:00pm on Friday, April 14th, you must have a commit with all steps completed.

Grading breakdown

• 100% (80 points) for completing the implementation steps. Step 1-4 and 6 are each worth 10 points, and steps 5 and 7 are worth 15 points each. If your WeensyOS looks similar to the animated pictures in the handout under each step's "How should WeensyOS look when you're done?" dropdown, you’ve probably got these points.
• There are up to 15 points for extra credit.

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 fourth CS 300 project, and written part of your own operating system!

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