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.
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.
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
Here’s what’s going on in the physical memory display.
- WeensyOS displays the current state of physical and virtual memory. Each character represents 4 KB of memory: a single page. There are 2 MB of physical memory in total. (How many pages is this?)
- 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 asks 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.
The virtual memory display is similar.
- The virtual memory display cycles between the four processes’ address spaces. However, all the address spaces are the same for now.
- 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.
- In the virtual memory display, a character is reverse video if an application process is allowed to access the corresponding address. Initially, any process can modify all of physical memory, including the kernel. Memory is not properly isolated.
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!
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.
||Start of kernel code.|
||Top of kernel stack. The kernel stack is one page long.|
||CGA console memory.|
||Start of application code. Applications should not be able to access memory below
||Size of physical memory in bytes. WeensyOS does not support physical addresses ≥
||Size of virtual memory. WeensyOS does not support virtual addresses ≥
||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
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
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.
kernel_start function (in
kernel.c), the kernel initialization function to make
kernel memory inaccessible to applications. The relevant part of the
kernel_start function starts at line 68.
The single page at
CONSOLE_ADDR = 0xB8000 should still be accessible to all user processes.
In addition to
map_to_userspace, you will find the
map_to_kernel_space function defined in
util.h to be useful in this step.
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.
kernel_start, you set most of memory to be accessible to everyone. First, fix it so that, initially, kernel memory is only accessible to the kernel and the rest of memory is unmapped.
process_setup, instead of setting the page table to be
kernel_pagetable, you’ll need to create a new per-process page table using
Then, you’ll need to initialize the kernel memory mappings of the new page table in the same way you did in
kernel_start for the kernel page table.
Finally, you will need to make sure that any page that belongs to the process is user-accessible. This will involve two changes to
process_setup. Find both instances of where
refcount of the
pages array is incremented. This increment is allocating the page directly. So, you’ll need to make sure that after it’s allocated, it is user-accessible.
syscall_page_alloc function which also allocates pages for a user process. The current process is always stored in the global variable
and has a
pagetable field which you can access to find the current page table.
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).
As you noticed in the previous part, WeensyOS currently allocates pages by directly editing the
pages array; in this part, you should replace all allocations into userspace with calls to
kalloc function which returns a pointer to a physical page. Then, you can use the
memory_map function to map the required virtual address to the physical address. You will
need to cast the
void * pointer returned by
kalloc to a
uintptr_t before passing it into
memory_map. You can see an example of the permissions you might want in
Once you complete this step, you will likely be greeted by a kernel that infinitely reboots…
memcpy are used to initialize the data in various segments.
Unfortunately, these functions expect you to use physical addresses in the current kernel implementation (because the syscall handlers use the kernel pagetable) rather than the virtual ones that are currently being provided. Use the
memory_virtual_to_physical function to convert
the virtual addresses to physical ones that can be used directly in the calls to
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!
Change each process’s stack to start at address
MEMSIZE_VIRTUAL. Now the processes have enough heap room to use up all of physical memory and will keep growing
until memory runs out!
Once memory runs out, your kernel will fault. This is not good because we can recover from this. Edit
syscall_page_alloc to check the result of the call to
kalloc and return
-1 if there is no memory left.
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.
This project (and WeensyOS) were originally developed for Harvard’s CS 61 course by Eddie Kohler. We’ve used it with permission.