<style> details { margin-top: 0.5em; margin-bottom: 0.5em; } summary { //font-weight: bolder; } summary:hover { text-decoration: underline; } h2 { border-bottom: 2px solid black !important; } blockquote { font-size: 16px; } section { margin-bottom: 2rem; padding: 0em 1em; padding-bottom: 1em; border-radius: 4px; background-color: #f7f7f7; border: 1px solid #ccc; } .todo { color: #ff00ff; border: 2px dashed #ff00ff; padding: 0em 1em; border-radius: 5px; margin-top: 1em; margin-bottom: 1em; //display: none; // UNCOMMENT TO HIDE TODOs } </style> **[&laquo; Back to the main CS 300 website](https://csci0300.github.io/)** # Project 4: WeensyOS **Key deadlines** - **Steps 1-4**: due Friday, November 7 at 8pm EST - **Final submission (all steps)**: due Friday, November 14 at 8pm EST - **[Post-project form](https://forms.gle/n8D2YG3soNdL8NJ26)**: due Wednesday, November 19 --- # 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. <!-- ### Questions 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 To get started on the project, you will need to pull some additional stencil code into your project repo. You can do this as follows: 1. Open a terminal in your container environment and `cd` into the directory you set up as your project repo from Lab 0 (e.g., `cd projects`) 2. Run the following command to pull the latest code from the `handout` remote (see below if you get errors): ``` cs300-user@9899143429a2:~/projects$ git pull handout main ``` If this reports an error, run: ```bash git remote add handout git@github.com:csci0300/cs300-f25-projects.git ``` followed by: ```bash git pull git pull handout main ``` This will merge our Project 4 (`weensyos`) stencil code with your repository. :::warning **Note: If you see a warning about "divergent branches"...** <details> <summary><b>Expand for instructions</b> </summary>  This means you need to set your Git configuration to merge our code by default. To do so, run (within the same directory in your labs repository workspace): ```console $ git config pull.rebase false $ git pull handout main ``` </details> ::: :::danger **If your terminal window changes to something like this**:  <details> <summary><b>Expand for instructions</b> </summary> Your terminal has asked you to add a commit message to explain what code was merged in, and opened a text editor so you can write the message. The top line is a default message, which you can use as-is. To use the message and finish the commit, do the following: - **If your terminal looks like the image above**, press `Ctrl+s` to save, then `Ctrl+q` to quit. (These are shortcuts for the text editor `micro`, which is the program that is running now) - **If your terminal instead has a bar at the top that says `GNU nano`**, you are using a text editor called `nano`. To save your commit and exit, press `Ctrl+x`, then press `y`, and then press `Enter`. </details> ::: Once you have a local working copy of the repository that is up to date with our stencils, you are good to proceed! You should now see a new directory called `weensyos` inside your projects repo: you should do all your work for this project in this directory. # Stencil and Initial State ## Running WeensyOS WeensyOS can, in principle, run on any computer with an x86-64 CPU architecture. For this assignment, however, we will run the OS in QEMU, a CPU emulator. QEMU makes it possible to easily restart and debug WeensyOS, and allows us to test WeensyOS even if we aren't using the x86-64 architecture (example: if you are using a Mac, you are using the ARM64 architecture instead). To run WeensyOS, run: * `make run` in the directory containing the project stencil, or * *(if `make run` doesn't work)* run `make run-console` instead. This will run QEMU in a different display mode that is a bit less pretty, but is more reliable. Once `make` succeeds, you should see something like the image below, which shows four processes running the program `p-allocator.cc`:  :::info **If you don't see anything**: WeensyOS requires that your terminal is big enough in order to display properly: if you don't see any text, of it the viewer is cut off, make your terminal larger until you can see the whole display here. Later, error messages are printed at the bottom of the screen, so it's really important to make sure you can see the whole view! 🤔 **Pro tip for VSCode users**: you can use `Ctrl+J` (Windows) or `Cmd+J` (Mac) to quickly show/hide the terminal pane. This way, you can keep the terminal window big, but easily switch back and forth between it and your code! ::: This image loops forever; in a real 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.) :::warning :eyes: **(Remember for later) Debugging modes**: The **[Debugging section](#Debugging)** and the WeensyOS documentation have some information on how to run WeensyOS in different modes that output more information for debugging. Some highlights: - If WeensyOS fails to boot, you can run it with extra debugging info, see [here](#Debugging) for details - Only one QEMU emulator can be running at a time. If `make run` outputs an error like `Failed to get "write" lock` or `address already in use`, this means that some other tab is running QEMU. If this happens, run `make stop` to kill other QEMU instances, then do `make run` again ::: ## What's happening? **Before you continue**, take a moment to make sure you understand the WeensyOS memory view: Here's what's going on in the physical memory display: - As we've discussed in class, **the WeensyOS display shows the current state of physical and virtual memory**. Each character represents a single page, which is 4KiB (4096 bytes) of memory. There are 2 MiB of physical memory in total. (How many pages is this?) * **WeensyOS initially 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. Processes do this using the system call `sys_page_alloc()`, which you can see in the code for `p-allocator.cc`. As we saw in class, 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--here's what it's doing, and what it shows us about what you'll be implementing in this project: - The virtual memory display cycles between the four processes' address spaces. However, in the handout version, there are some problems (which you can see on the display): - All of the address spaces are the same: in other words, all the processes live in the same address space--i.e., **there is no memory isolation between processes**! :scream: (Don't worry, you will fix this!) - And it gets worse: the kernel shares this address space too, meaning that there is no isolation between kernel and userspace processes!! :scream: (You will fix this too!) - Blank spaces in the virtual memory display correspond to *unmapped* addresses. If a process (or the kernel) tries to access an unmapped address, it will trigger a page fault. - The character shown at address *X* in the virtual memory display identifies the owner of the corresponding physical page. (For example, a `1` is owned by process 1.) - In the virtual memory display, a character is <span style="background-color:green">**reverse-video**</span> (i.e., dark foreground, colored background ([info](https://en.wikipedia.org/wiki/Reverse_video))) if an application process is allowed to access the corresponding address. This also shows a problem: - Initially, any process can modify all of physical memory, including the kernel. This implies that memory is not properly isolated! - **Initially the virtual memory and physical memory use an *identity mapping***: that is, virtual address *X* always uses the page at physical address *X*. This is why the growing heaps of the four processes in the virtual memory match with the physical memory display. In the code, one place you can start to see this is `syscall_page_alloc()`: given the virtual address `addr`, the function allocates the page at `addr`. - As we discussed in lecture, this is inefficient, and doesn't take advantage of virtual memory. (Why?) <!-- :::info 🥺 **Be sure to understand how to interpret these pictures before continuing.** Here's a recap: - For each process, the leftmost pages (i.e., at the lowest address) contain its code and global variables, which corresponds to text and data segments - After the code and data segments are the pages that for that process' heap. As WeensyOS runs, each process periodically requests new pages (by calling `sys_page_alloc`) to grow its heap - Finally, the rightmost page for each process, located as its highest address, is a page for the process' stack - At the moment, all virtual pages use an identity mapping! (What does this mean, and why do we want to change it?) For more information on this, we recommend reviewing Lab 4 and Lectures 12-14. ::: --> # Your goal As we saw in the initial memory view, the stencil version of WeensyOS has some problems--and you will fix them! Specifically: - You will implement memory isolation, to ensure processes are isolated - You will implement virtual memory, to improve utilization of physical memory - You will implement `fork`--creating new proceses at runtime--and exit--destroying processes at runtime As you may have already seen, the stencil code for WeensyOS is quite large, but **all of the code you write will be in `kernel.cc`** (though might modify other files for testing or extra credit). We encourage you to look at other files as they are referenced in this handout and in the code, but you should primarily focus on `kernel.cc`. There is no `make check` or autograder tests for this assignment. Instead, you should run your WeensyOS and inspect the output visually--for each step of the assignment, we've provided some images of how the output should look for comparison. (We will do the same when grading.) <!-- <div class="todo">Check for duplication with introduction</div> --> # Background on WeensyOS The WeensyOS stencil has a lot of files--while you only need to modify `kernel.cc`, you will need to know about some important defintions and conventions in the stencil. This section gives an overview of the most important things to know now, with pointers to items you'll need later. ## Memory System Layout 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 is`0x40000` (`PROC_SIZE`) in size. <pre> 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 </pre> Here's a list of all the constants that refer to the memory layout: | | | |--|--| | `KERNEL_START_ADDR` | Start of kernel code, always `0x40000` | | `KERNEL_STACK_TOP` | Top of kernel stack (always `0x80000`). The kernel stack always one page in size | | `CONSOLE_ADDR` | CGA console memory (`0xB8000`). Values written to this page get printed in the terminal. All processes must have read/write access to this page. See the note below for more info. | | `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 (`0x200000`, which is 2MB). WeensyOS does not support physical addresses ≥ `MEMSIZE_PHYSICAL` | | `MEMSIZE_VIRTUAL` | Size of virtual memory (`0x300000`, or 3MB). WeensyOS does not support virtual addresses ≥ `MEMSIZE_VIRTUAL`| | `PAGESIZE` | Size of a memory page: `4096` (or equivalently, `1 << 12`) | <details> <summary><i>Optional: How does the console memory work?</i></summary> <br /> > 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](https://en.wikipedia.org/wiki/Color_Graphics_Adapter), or Color Graphics Adapter, is just a type of graphics card used in WeensyOS! </details> ## The stencil 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! Almost all of the changes you will make will be in one file: kernel.cc. You may also find it useful to refer to come other files, here are the most important ones to know about: | | | |--|--| | `kernel.cc` | The core of the kernel program. You will be editing this file throughout the assignment. | | `kernel.hh` | Declares constants and function headers for the kernel, most of which are implemented in `kernel.cc` (while others are in `k-hardware.cc`) | | `u-lib.hh` | User-space library with system calls: Userspace programs (like `p-allocator.cc`) call functions from here. | <!-- 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`. --> <!-- 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 --> :::success **How to learn the stencil / how to read this handout**: As you continue reading and get more acquainted with the stencil, two important tips to keep in mind: - **As you work on each step, we'll provide more details about the stencil in "Important background" sections**: like for Snake, these give helpful tips about certain part of the stencil, and how they map to the concepts we're seeing--be sure to look for these! - **Navigating the codebase**: If you use VSCode, remember you can Ctrl+Click on items to find their definition--this will be very helpful for finding where functions are defined! If this isn't working for you, try the fix in [this section](https://csci0300.github.io/assign/labs/lab0.html#Testing-your-VSCode-install-IntelliSense) of lab 0 (in the yellow box) ::: <!-- 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): ```shell $ 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. --> <!-- > --> <!--- ## Background: Kernel and Process Address Spaces <div class="todo">Can this be removed?</div> 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. Thus, when running code in the kernel, each virtual address maps to the physical address with the same number. The WeensyOS code automatically sets up `kernel_pagetable` and switches to it whenever the system switches between user-mode and kernel-mode (i.e., when syscalls, interrupts, or exceptions occur)--this is called *protected control transfer*. As we discussed in class, each process page must contain mappings for the kernel code and stack, in order for protected control transfer to work properly. (For more on this see the note below, and our lecture notes.) 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. <details> <summary><i><span style="color:#0000EE">Optional: How does protected transfer control work?</span></i></summary> <br /> > 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. </details> --> # Assignment Roadmap :::warning **Warning**: Before starting, we highly recommend completing **[Lab 4](https://csci0300.github.io/assign/labs/lab4.html)**, which is designed as an introduction to working in WeensyOS. If you haven't completed Lab 4, we suggest you do it now! ::: ## 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 `exit`system 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](#Debugging-Resources-/-GDB) 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. **Why are we doing this?** The kernel has full privilege over all computer resources with no restrictions! If a malicious process could edit kernel memory, it could inject code and gain control of all of a computer's resources. <details> <summary><b>Specifications</b></summary> * Change `kernel_start()`, the kernel initialization function in `kernel.cc`, so that kernel memory is inaccessible to applications -- except for the console memory (the single page at `CONSOLE_ADDR`). * Now, `sys_page_alloc` must also preserve kernel isolation. Applications shouldn't be able to use `sys_page_alloc` to borrow pages in the kernel or reserved region of memory! This requires changing the `syscall_page_alloc()` function in `kernel.cc` to return -1 when the requested address is invalid. Take a look at the specification of `sys_page_alloc` in `u-lib.hh` to find out how to determine whether the requested address is in the application region of memory. * Note that `sys_page_alloc()` is the user-facing library function for user processes defined in `u-lib.hh`, whereas `syscall_page_alloc()` is a helper function in `kernel.cc` that gets invoked when `sys_page_alloc()` is called. </details> <details> <summary><b>How should WeensyOS look when you're done?</b></summary> 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. </details> <details> <summary><b>Hints</b></summary> * Look into `vmiter` to create memory mappings with appropriate permissions. Take a look at the `vmiter` loop in the `kernel_start` function. </details> <section> ### Important background: Working with page tables (`vmiter`) <details><summary>Click to read</summary> Modifying page permissions and virtual memory mappings involves working with page tables. In WeensyOS, the `vmiter` class examines and modifies x86-64 page tables, especially their virtual-to-physical address mappings. You started using `vmiter` objects in Lab 4--here's a primer on the most important code-level details to know for this project. For the full specification of what methods are available, see `k-vmiter.hh`. #### Examining page tables `vmiter(pt, va)` creates a `vmiter` object examining page table `pt` and with current virtual address `va`: - The `va()` method returns the iterator’s current virtual address. - The `pa()` method returns the physical address mapped at the current virtual address. If there is no page table mapping for this address `pa()` returns -1: ```cpp x86_64_pagetable* pt = ...; uintptr_t pa = vmiter(pt, va).pa(); // returns uintptr_t(-1) if unmapped ``` The `perm()` method returns the permissions of the current mapping based on the `PTE_P`, `PTE_W`, and `PTE_U` flags. There are convenient shorthands—`present()`, `writable()`, and `user()`—to check for `PTE_P`, `PTE_W`, and `PTE_U` to check each flag: ```cpp if ((vmiter(pt, va).writable()) { // `va` is present and writable in `pt` } // Equivalent to: //if ((vmiter(pt, va).perm() & PTE_W) != 0) { // . . . //} ``` #### Traversing page tables It is common to use `vmiter` in loops. This loop prints all present mappings in `MEMSIZE_VIRTUAL`, moving one page at a time: ```cpp for (vmiter it(pt, 0); it.va() < MEMSIZE_VIRTUAL; it += PAGESIZE) { if (it.present()) { log_printf("%p maps to %p with permissions %x\n", it.va(), it.pa(), it.perm()); } } ``` #### Modifying page tables The vmiter `try_map` method can add and modify page table mappings and permissions. For example, this function maps physical page 0x3000 at virtual address 0x2000, with permissions P, W, and U: ```cpp vmiter(pt, 0x2000).try_map(0x3000, PTE_P | PTE_W | PTE_U); ``` When you do this, the `vmiter` automatically traverses each level of the page table, and automatically allocates memory for lower-level page tables if necessary by calling `kalloc`, the kernel version of `malloc` This way, you never need to worry about the four-level page table structure while writing code. An important thing to keep in mind for later, however, is that **`try_map` may fail**: if the system runs out of memory, it won't be able to allocate new memory for page table mappings. On failure, `try_map` will return -1. You don't need to worry about this in step 1 (because the system isn't out of memory when it first starts up), but it will become important in later steps! <!-- ' --> #### Interface summary * `vmiter` walks over virtual address mappings. * `pa()` and `perm()` read current addresses and permissions. * `map()` and `try_map()` modify mappings. * **Check out `k-vmiter.hh` for the complete interface** </details> </section> ## Step 2: Process Isolation **Overview** After step 1, processes can no longer access the kernel memory, but they are still sharing the same address space because they all use the same pagetable (`kernel_pagetable`). As we said, this is a problem: processes can read and write each other's memory arbitrarily, allowing Eve to steal or corrupt another proccess' code or data! In this step, implement process isolation by giving each process its own independent page table. See the specifications and important background below for details. <details> <summary><b>Specifications</b></summary> - For the next few steps, you will mostly focus on the `process_setup` function. This function sets up the memory for each process when WeensyOS starts up. Take a look at the comments in this function for some details on how it works. - In `process_setup`, allocate a new, initially-empty page table for this process by calling `kalloc_pagetable`: ```cpp x86_64_pagetable* pt = kalloc_pagetable(); ``` - First, copy the mappings for kernel memory from `kernel_pagetable` into the new page table you created using `vmiter::try_map`. This ensures that the required kernel mappings are present in the new page table. See the important background below, and the comments in `process_setup` for details on what this means conceptually. - All user pages should match `kernel_pagetable` **up to** `PROC_START_ADDR`, after which the mappings for each process should be different. You can by adding the mappings yourself, similar to `kernel_start` from step 1, or by using two `vmiter`s. - Note that, after creating the initial (level 4) pagetable with `kalloc_pagetable`, `vmiter::try_map` and `vmiter::map` will allocate level-3/2/1 page tables automatically as you add mappings. You don't need to worry about creating the internals of this data structure. - `try_map`: In `process_setup`, all calls to `try_map` are guaranteed to succeed (and, thus, return 0), so it's okay to just `assert` that the return value is zero (like in step 1). However, this won't be the case in later steps: `try_map` may fail if the system runs out of memory, which will be important later! - Then, add mappings for each page of physical memory needed by this process. In doing so, you will need to make sure that any page that **belongs** to this process is mapped as user-accessible--these are the pages the process needs to access, including its **code**, **data**, **stack**, and **heap** segments. Therefore, there are several places you’ll need to change: - Take a look at the background section on program images for details on what this means, and how the `process_setup` code works - After dealing with the two nested loops that set up the program images, be sure to consider the rest of the code in `process_setup`, and other functions where a process may allocate pages. Other than `process_setup`, what other parts of kernel.cc allocate pages for a process? - If you see pages in the memory view marked `L`, this means that a page has been used but not added to any page table--this means you still need to add a mapping! - If you create an incorrect page table, WeensyOS may crazily reboot. Don't panic! See [Debugging](#Debugging) </details> <details> <summary><b>How should WeensyOS look when you're done?</b></summary> 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 red-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. </details> <details> <summary><b>Hints</b></summary> * The `program_image` used in `process_setup` is an iterator that goes through segments of the executable. Recall that some some segments are read-only, whereas others are writable. You can determine which permission is appropriate using `seg.writable()` * On each system call, the global variable `current` points to a struct containing the OS' metadata about the process that made the system call. the current process' page table is at `current->pagetable`. This metadata is stored in a struct of type `proc`; to see all the fields in the `proc` struct, check out `kernel.hh`! * In `process_setup` any calls to `map` or `try_map` are guaranteed to succeed, since this `process_setup` only runs when the OS first starts up. In contrast, `sys_page_alloc` will be called all the time to allocate more memory for each process until it memory runs out. How can you make `sys_page_alloc` return with an error if the mapping fails? 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:  </details> <section> ### Important stencil background: program images and segments (`pgm` and `seg`) <details> <summary>Click to read</summary> As we discussed in class, a *program* is an executable file on disk that contains information about that we can run, but it isn't necessarily running yet. In contrast, a *process* is a "live" instance of a program that can currently run on the processor. But how does a *program* become a *process*? Starting a process involves a part of the operating system called the *loader*, which reads the parts of the program and loads them into the process' memory where it can run. You will interact with the part of the WeensyOS code that does this--we provide a stencil and some helpers, and you'll use them to set up the process' memory and page tables. Here's some important terminology on how it works: - A more accurate version of **what we call a "program" is known as a **program image****: this is the executable file generated by the compiler and linker that defines a process’s initial state. You can think of this as essentially a "recipe" for constructing a process: it describes the process’s initial virtual address space, defines the instruction and data bytes that initialize that address space, and specifies which instruction is the first instruction to execute. Operating systems use program images to initialize new processes. - **Each program image is composed of *segments***: e.g., the code, data, heap, and stack, like we've discussed in lecture. The image contains the data for each segment (e.g., the code segment contains all the bytes that comprise the program's machine code), and some metadata that tells the operating system how they should be loaded into the processs' memory. When a process starts up, the operating system needs to read each segment and copy the data into the appropriate place into the process' memory. - You can print about a program image’s segment definitions using `objdump -p`. - In memory, **each *segment* is composed of *pages***: segments can be arbitrarily large, so one segment could span multiple pages of memory. For each physical page needed, you will need to make sure it's mapped into the process' page table. WeensyOS provides a `program_image` class to make it easy to work with program images. At startup, the kernel has `program_image` objects for each program that the OS knows about (`p-allocator`, `p-allocator2`, `p-fork`, etc.). The `program_image` class has helpers for accessing the different program segments, and determining where they should go in memory. `The program_image` and `program_image_segment` data types allow you to query these images. Their interfaces are as follows: ```cpp struct program_image { ... // Return an iterator to the beginning loadable segment in the image. program_image_segment begin() const; // Return an iterator to the end loadable segment in the image. program_image_segment end() const; // Return the user virtual address of the entry point instruction. uintptr_t entry() const; }; struct program_image_segment { ... // Return the user virtual address where this segment should be loaded. uintptr_t va() const; // Return the size of the segment, including zero-initialized space. size_t size() const; // Return a pointer to the kernel’s copy of the initial segment data. const char* data() const; // Return the number of bytes of initial segment data. size_t data_size() const; // It is always true that `data_size() <= size()`. If `data_size() < size()`, // the remaining bytes must be initialized to zero. // Return true iff the segment is writable. bool writable() const; }; ``` For instance, this loop prints information about a program image. ```cpp void log_program_info(const char* program_name) { program_image pgm(program_name); log_printf("program %s: entry point %p\n", program_name, pgm.entry()); size_t n = 0; for (auto seg = pgm.begin(); seg != pgm.end(); ++seg, ++n) { log_printf(" segment %zu: addr %p, size %lu, data_size %lu, %s\n", n, seg.va(), seg.size(), seg.data_size(), seg.writable() ? "writable" : "not writable"); if (seg.data_size() > 0) { log_printf(" first data byte: %u\n", (unsigned char) *seg.data()); } } } ``` <!-- The relationship between `seg.va()` and `seg.data()` is worth emphasizing. `seg.va()` is a user virtual address. It is the process virtual address where the process code expects the segment to be loaded. `seg.data()`, on the other hand, is a kernel pointer. It points into the program image data in the kernel. WeensyOS `seg.va()` values are all `>= PROC_START_ADDR` (0x100000), and are typically page-aligned, whereas `seg.data()` values are between 0x40000 and 0x80000 and are not aligned. --> </details> </section> ## Step 3: Virtual Page Allocation **Overview:** So far, WeensyOS processes use *identity mappings* 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 break this identity mapping by leveraging virtual memory to map virtual addresses to different physical addresses. Processes don’t have access to the address mapping (only the kernel does), so it should be fine for a process’s virtual address X to map to a different physical page--the process won’t be able to tell the difference. This will also enable new functionality, like running different processes with similar virtual address spaces. In WeensyOS, we will allocate physical pages using **`kalloc`**, which is like a kernel version of `malloc`. Each time `kalloc` is called finds a free page at some place in physical memory, which can then be mapped to whatever virtual address the process needs. <!-- :::info **Why are we doing this?** Processes generally need a contiguous region of memory to run. Right now, we're pre-allocating a block of physical memory per process, but if a process wants to use more memory than is available, there's no way to expand this preallocated block. every process has a block of memory within its own distinct virtual address space, and pages in the block map to regions in physical memory that may not necessarily be contiguous. If the process needs more memory, we give it a new page in the virtual memory block and map that to a free page in physical memory. ::: --> <details> <summary><b>Specifications</b></summary> * Change your OS to allocate all process data, including its code, globals, stack, and heap, using `kalloc` instead of by directly claiming pages in the `physpages` array. For example, you should see several places where the stencil does this: ``` // "Claim" the page at address `addr` assert(physpages[addr / PAGESIZE].refcount == 0); physpages[addr / PAGESIZE].refcount++; ``` The `physpages` array tracks which physical pages are currently allocated: the `refcount` ("reference count") field tracks the number of processes using the page, so a `refcount` of zero means the page is free. The stencil version just allocates a physical page at the same address as the virtual address required, which is inflexible. Instead, you should replace these two lines with a call to `kalloc`, which searches physical memory for a free page (one where `refcount == 0` in `physpages`) instead, so that the physical page can be anywhere in memory! </details> <details> <summary><b>How should WeensyOS look when you're done?</b></summary> Here's how your OS should look like after this step:  </details> <details> <summary><b>Hints</b></summary> - Virtual page allocation will complicate the code that initializes process code in `process_setup`. Specifically, there are a couple of places where we use `memcpy` and `memset`, which copy data into the physical addresses where the code lives. Now that the virtual memory to physical memory mapping is not one-to-one, how would you get the physical address corresponding to the virtual address of each page? (Hint: `vimiter` can help!) - The code that copies data into pages data into physical pages assumes that the physical pages of each segment are contiguous in memory. It's fine to depend on this in `process_setup` since `kalloc` will generally return pages in contiguous order, and no other processes are running when WeensyOS starts up. - If you'd like to change this behavior, feel free, but it's not required. (You can test it by modifying `kalloc` to set `page_increment` to any odd-numbered value higher than 1.) </details> <!-- ## Step 4: Nonsequential physical page allocation :::success **Note**: This step is independent of the others. If you get stuck on it, feel free to continue with the project and then come back to it. (Just make sure you set `page_increment = 1` before continuing.) ::: In the stencil version, `kalloc` always chooses the available physical page that has the lowest address. This means consecutive `kalloc` calls typically return consecutive physical pages. But your code should not depend on this behavior. Change `kalloc` to allocate pages nonsequentially. For example, set `page_increment` to 3 (or any larger odd number). The virtual address spaces should work as before, though the physical memory map will look different. <details><summary>How should WeensyOS look when you're done?</summary>  </details> Once you’re confident in your phase 4 solution, you can go back to setting `page_increment = 1`, but your code should work with any page allocation strategy. <details> <summary>Hints!</summary> - Think back to `process_setup`: remember that each program segment `seg` is composed of multiple pages. Is there any part of the `process_setup` code that assumes that the pages are ordered sequentially? This is the part you'll need to change! - If you see a panic—like: `PAGE FAULT on 0xcccccccccccccccc (pid 3, read missing page, rip=0xcccccccccccccccc)!`, your WeensyOS is trying to read pages that contain unallocated data: this means that you are not copying data into the correct pages. To work on this, go back and think again about how to copy instructions and data from program segments into process memory (e.g., read the box in step 2). </details> --> ## 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. :::info **Why are we doing this?** Despite each process now using virtual memory, the boundaries of the memory block within its virtual address space haven't been changed -- they're still constructed as if all the processes were directly using physical memory. Every process has a completely distinct virtual address space, so we should let it take up as much of its virtual address space as needed. ::: <details> <summary><b>Specifications</b></summary> * Change each process’s stack to grow down starting at address `0x300000 == MEMSIZE_VIRTUAL`. </details> <details> <summary><b>How should WeensyOS look when you're done?</b></summary> Notice how the processes now have enough heap room to use up all of physical memory:  Now that we're taking full advantage of virtual memory, different processes can allocate to the same virtual addresses. You can check your implementation is correct by making each process start allocating memory at the same virtual address. In the `build/` directory, edit the `p-allocator#.ld` files by changing the first line after `SECTIONS{` to ` . = 0x100000;`. All the programs should now start allocating from`0x100000` without error as shown below: <!--  -->  </details> <details> <summary><b>Hints</b></summary> * Read the code that allocates stack in `process_setup` closely (pay attention to how `%rsp` is set to the beginning of the stack)! * Try letting all the processes grow their heaps until you run out of physical memory. If the kernel panics, it may be because your `syscall_page_alloc` is not returning -1 when you can't allocate memory anymore! Think about how you can check for that, and make sure to account for this case. </details> ## 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-fork` or `make run-console-fork`. (Alternately, at any time, run with `make-run` and 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 `p-allocator` processes.) Either way, once the `fork` process starts, 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. <details> <summary><b>Specifications</b></summary> * First, look for a free process slot in the `ptable[]` array. Don’t use slot 0 - this slot is reserved for the kernel. * Next, if a free slot is found, make a copy of `current->pagetable` (the forking process’s page table) for the child. * For addresses below `PROC_START_ADDR` (0x100000), the parent and child page tables should have identical mappings (same physical addresses, same permissions). But for addresses at or above `PROC_START_ADDR`, the child’s page table must map to different pages that contain copies of any **user-accessible, writable** memory. This ensures process isolation: two processes should not share any writable memory except the console. * So `fork` must examine every virtual address in the old page table. Whenever the parent process has a user-accessible page at virtual address *V*, then fork must allocate a new physical page *P*; copy the data from the parent’s page into *P*, using `memcpy`; and finally map page *P* at address *V* in the child process’s page table. * Fill in the fields of the `proc` struct in the `ptable` at the free slot you found earlier. * The child process’s registers are initialized as a copy of the parent process’s registers, except for `reg_rax`. </details> <details> <summary><b>How should WeensyOS look when you're done?</b></summary> When you’re done, you should see something like this (when running `make run-fork`, or via `make run` and then 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:  </details> <details> <summary><b>Hints</b></summary> * The `vmiter` supports both `map` and `try_map` operation. Which one is more appropriate to use in `fork`? * Make sure to error check in appropriate places! If there is any kind of failure while creating a child processs, return -1 to the user. You can see the specification for `sys_fork()` in `u-lib.hh`. </details> ## 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. <details> <summary><b>Specifications</b></summary> * In `syscall_fork`, share read-only pages between processes rather than copying them. * If you have not done so already, make sure that `process_setup` maps non-writable program segments as read-only </details> <details> <summary><b>How should WeensyOS look when you're done?</b></summary> 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 **S**hared by multiple processes. </details> <details> <summary><b>Hints</b></summary> * Make sure to increment the reference counts of the pages being shared between processes! * Avoid using equality tests like `it.perm() == (PTE_P | PTE_U)! vmiter::perm()` to detect if a page is read-only. Instead use `vmiter:writable()`. </details> ## Step 7: Exit and Freeing memory **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 <b>current process</b> to free its memory and resources and exit cleanly and gracefully. Run `make run-exit` or `make run-console-exit`. (Alternately, at any point, run with `make-run` and press the "e" key. This reboots WeensyOS and starts the `p-exit.cc` program. The `p-exit` processes all <b>alternate among forking new children, allocating memory, and exiting.)</b> Your WeensyOS should initially panic because you have not implemented `syscall_exit` in `kernel.cc` yet! <details> <summary><b>Specifications</b></summary> * Complete `kfree` so that `kfree` frees memory. What does it mean to "free" a page from a process? * Implement `syscall_exit` in `kernel.cc`, which is a helper function that gets called when the system call `sys_exit` is invoked. This function should mark the process as free, and free up all of its memory. This includes the process’s code, data, heap, and stack pages, as well as the pages used for its page table. The memory should become available again for future allocations. * We have created the header of a helper function `free_pagetable` for you in `kernel.cc`. Implement it to free all pages stored by a pagetable and also the pages storing the pagetable itself. You can then use the helper in the rest of your code. * Use `vmiter` and `ptiter` to enumerate and iterate through the relevant pages (relevant in this context means user-accessible pages being used by the process). But be careful not to free the console! * See the background box at the end of this section for info about how `ptiter` works. You can also find examples in `k-vmiter.hh` to figure out how you can use `ptiter` to free up a page table! * You will also need to change `syscall_fork` and `syscall_page_alloc` (and perhaps any other helper functions you may have written) to make sure there is no memory leak. Think about all the places that allocate or share memory. In `p-exit`, unlike in previous steps of the project, `sys_fork` and `sys_page_alloc` can run even when there isn’t quite enough memory to create a new process or allocate or map a page. Your code should handle this cleanly, without leaking memory in any situation. * If there isn’t enough free memory to successfully complete `sys_page_alloc`, the system call should return -1 to the caller. * If there isn’t enough free memory to successfully complete `sys_fork`, the system call should clean up (i.e., free any memory that was allocated for the new process before memory ran out), and then return -1 to the caller. </details> <details> <summary><b>How should WeensyOS look when you're done?</b></summary> Once you're done, `p-exit` program will make crazy patterns forever like this:  A fully correct OS can run `p-exit` indefinitely. In an OS with a memory leak, the physical memory map will collect L pages (L for leak), persistent blank spots, or both, and if run long enough, these pages will take over the screen. Here’s an example; note the Ls accumulating at the end of the physical memory map:  <!-- 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-exit may encourage errors to manifest, but you may need to be patient. **There should be no memory leaks!** </details> <details> <summary><b>Hints</b></summary> - If you're struggling to find where your memory leak is coming from, review each place where memory is allocated in WeensyOS, and ensure all allocation sites have corresponding free sites! If there is even *one* allocation site that is missing a free site, you have memory leak. </details> <section> ### Important background: physical memory iters (`ptiter`) <details> <summary>Click to read </summary> When we free a process' memory, we not only need to free the physical pages associated with the process, but the pages used by its page tables (e.g., the L1/L2/L3/L4 tables!). The `ptiter` object iterates through the physical memory used to represent a page table. `ptiter` is useful mostly when freeing page table structures. ```cpp class ptiter { public: // initialize a `ptiter` for `pt` inline ptiter(x86_64_pagetable* pt); inline ptiter(const proc* p); // Return kernel-accessible pointer to current page table page. inline x86_64_pagetable* kptr() const; // Return physical address of current page table page. inline uintptr_t pa() const; // Return first virtual address mapped by this page table page. inline uintptr_t va() const; // Return one past the last virtual address mapped by this page table page. inline uintptr_t last_va() const; // Move to next page table page in depth-first order. inline void next(); // ... }; ``` `ptiter` visits the individual page table pages in a multi-level page table, in depth-first order (so all level-1 page tables under a level-2 page table are visited before the level-2 is visited). A `ptiter` loop can easily visit all the page table pages owned by a process, which is usually at least 4 page tables in x86-64 (one per level): ```cpp for (ptiter it(pt); it.va() < MEMSIZE_VIRTUAL; it.next()) { log_printf("[%p, %p): level-%d ptp at pa %p\n", it.va(), it.last_va(), it.level() + 1, it.kptr()); } ``` A WeensyOS process might print the following: ``` [0x0, 0x200000): level-1 ptp at pa 0x58000 [0x200000, 0x400000): level-1 ptp at pa 0x59000 [0x0, 0x40000000): level-2 ptp at pa 0x57000 [0x0, 0x8000000000): level-3 ptp at pa 0x56000 ``` Note the depth-first order: the level-1 page table pages are visited first, then level-2, then level-3. This makes it safe to use a `ptiter` to free the pages in a page table. `ptiter` never visits the topmost page table page, so that must be freed separately. Note also that `ptiter::level` is one less than you might expect (it returns a number between 0 and 3, rather than between 1 and 4). To free an entire page table, you will need to free each page table page! </details> </section> ## 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 for undergraduate students; graduate students taking CS 1310 must 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! Make sure to have a test program for *each* extra credit feature you implement. <details><summary> <b>How to write a new test program</b></summary> :::info 1. Choose a name for your test program. We’ll assume `testprogram` for this example. 2. Teach `check_keyboard` in `k-hardware.cc` about your program. Pick a keystroke that should correspond to your program and a case to the part shown below--the `argument` defines the name of the program to run when WeensyOS reboots on pressing a key. For instance: ```c++ if (c == 'a') { argument = "allocators"; } else if (c == 'e') { argument = "forkexit"; } else if (c == 't') { argument = "testprogram"; } ``` Now you should be able to run your test program by typing `t`. 3. To test your work, start by running `make`--you should see the makefiles auto-detect your new file and compile your program. Once compilation is finished, run `make run` as usual and then press the key you picked (e.g., `t`) to start your program! (Tip: you can also start your program directly by adding your program name after `run-`, e.g., `make run-testprogram`.) ::: </details> In your README, specify how to run each of your test programs and how they demonstrate the relevant extra credit functionality. ### 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`](https://man7.org/linux/man-pages/man3/munmap.3p.html). ### Expand `sys_page_alloc` **Moderately difficult**. Currently, `sys_page_alloc` is like a more restrictive version of [`mmap`](https://man7.org/linux/man-pages/man2/mmap.2.html). 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 <!-- ## Common Errors * Page Fault - a process tried to access an unmapped address in virtual memory. * Kernel Page Fault - the kernel tried to access an unmapped address in virtual memory. * `PANIC: Unexpected exception 13!` - general protection fault --> There are several ways to debug WeensyOS. Here are some techniques we recommend: - **`log_printf`**: Add log_printf statements to your code to print log messages to log.txt. However, keep in mind that log_printf will dramatically slow down your operating system. Delete log_printfs you don’t need avoid making things too slow. <!-- - Write `assert` statements to catch problems early --> <!-- - Printouts such as assertions and fault reports (e.g. `page fault at address 0x0`) include the virtual address of the faulting instruction, but they do not always include symbol information, and they never contain line number information. Use files obj/kernel.asm (for the kernel) and obj/p-PROCESSNAME.asm (for processes) to map instruction addresses to instructions. --> - [**How to interpret error messages**](#Understanding-memory-errors): WeensyOS prints errors and fault reports at the bottom of the screen (e.g. `page fault at address 0x0`) and a partial stack trace of the error. Look here for examples of common error messages and what they mean. - **[How to trace error messages to code](#Debugging-fault-reports-and-stack-traces)**: Error messages are helpful, but because they're generated by the (limited) kernel, they don't always have the kind of information we're used to seeing in backtraces, so we need to do a bit more work to interpret them. See [**this section**](#Debugging-fault-reports-and-stack-traces) for instructions! - **VGA Blank Mode / no WeensyOS at all**: Sometimes a mistake will cause the OS to crash hard and reboot. Use `make D=1 run` to get additional, super-verbose debugging output, which will be written to the file `qemu.log`. Search through this file for `check_exception` lines to see where the exceptions occur. - **Infinite loops**: A powerful, yet simple, technique for debugging extreme crashes is to narrow down where they occur using infinite loops. Add an infinite loop (while (true) {}) to your kernel. If the resulting kernel crashes, then the infinite loop is after the crash point; if it infinite loops, then the infinite loop is before the crash point. When a kernel infinite-loops on Docker, you must open another terminal to the same Docker instance and make stop to kill it. ### Understanding memory errors The WeensyOS memory viewer, which is defined in `k-memviewer.cc`, checks your memory management data structures and reports any problems it sees. The `memusage::symbol_at()` function chooses which symbol to display for each page and detects some errors. Here’s what some of those symbols and error messages mean. - **L page**: An L page has been leaked. This means that the page has been marked as used (it has a reference count greater than 0), but is not referenced by any process page table. This usually means that you’re missing a try_map call, you called kalloc without freeing or mapping the result, or you didn’t free your pages properly in step 7. - **PAGE TABLE ERROR: nullptr physical page mapped for user**: A process pagetable has mapped the physical page at address 0. This page is reserved and mapping it is illegal. Not checking the return value of kalloc is a common cause of this error. - **PAGE TABLE ERROR: reserved physical page mapped for user**: Some other physical pages are reserved for special purposes, such as internal machine software and device memory. Processes aren’t allowed to map these pages. - **PAGE TABLE ERROR: kernel data page mapped for user**: Processes also aren’t allowed to map physical pages that control kernel instructions or data (that would violate kernel isolation). - **PAGE TABLE ERROR: freed page mapped for user**: A process has an active mapping for a physical page that’s currently marked as free (has refcount 0). This is invalid and dangerous, since the mapping grants access to memory that the kernel could use again at any moment. - **PAGE TABLE ERROR: invalid reference count**: A physical page has a refcount that’s unexpectedly large. In WeensyOS, page reference counts are typically limited to the range `[0, PID_MAX]`, where `PID_MAX` is the number of processes in the system; but if your code decrements page refcounts too little or too much, the counter can easily get out of whack and overflow. - **Unwanted S page**: In step 6, you should start seeing S pages, but only for pages that can be safely shared—namely, program instructions and read-only data. If you see lots of S pages, this indicates that multiple processes are sharing the same writable memory, which is unsafe. (Copy-on-write extra-credit will show a lot of S pages.) The WeensyOS exception handler will also print messages on page faults, which indicate that process memory accesses went wrong. - **PAGE FAULT on `<PTR>` (pid N, read protection problem, rip=`<RIP>`**: A process is trying to read a virtual address that has a kernel-only mapping (not `PTE_P|PTE_U`). This likely means you haven’t mapped a page with the correct PTE_PWU permissions. Other messages include: - **write protection problem**: The process tried to write a page that is present, but unwritable (not `PTE_P|PTE_W|PTE_U`). - **read missing page**: The process tried to read a page that is not present. - **write missing page**: The process tried to write a page that is not present. `<PTR>` gives the address whose access failed, and <RIP> is the address of the instruction that tried to access that address. ### Debugging fault reports and stack traces When certain errors occur, WeensyOS will print a message at the bottom of the console window with the error and some backtrace information (example: `Kernel page fault on <address>`): ``` PANIC: Kernel page fault on 0x256000 (write missing page, rip=0x413ad)! #0 0x413ad <_Z7syscallP8regstate> #1 0x40b28 <_Z13syscall_entryv> ``` These are useful, but there's a catch: because these errors happen inside the kernel (and because the WeensyOS kernel is designed to be small), these errors don't contain line numbers of where errors occur, like the backtraces we've been accustomed to debugging so far. Instead, WeensyOS backtraces contain the *addresses in code memory* where the error occurred, and we need to do the work to manually map it to the source code. Here's how to do this: Say we receive the following error with backtrace: ``` PANIC: Kernel page fault on 0x256000 (write missing page, rip=0x413ad)! #0 0x413ad <_Z7syscallP8regstate> #1 0x40b28 <_Z13syscall_entryv> ``` The backtrace says that the fault happened at `%rip == 0x413ad`, which is an instruction in the function `syscall` function (based on the name `_Z7syscallP8regstate`), which was called by the function `syscall_entry` (from the name `_Z13syscall_entryv`). <details> <summary>Why do the function names look all garbled?</summary> These weird-looking names are called *mangled* symbols, which can refer to functions or variables. When compiling C++ code, the compiler transforms function names into a *mangled* format, which encodes information about the function's arguments, return type, and other C++ specific info. Look [here](https://en.wikipedia.org/wiki/Name_mangling#C++) for more info on why demangling is necessary, and how it works. Usually, we can guess the correct function name just by looking at the mangled version. However, you can also tools like [this one](http://demangler.com/) to convert the mangled form back into a real function signature, which may help. </details> Based on our understanding of the WeensyOS memory map, we know that the address `0x413ad` should be part of the kernel's code segment. To help us see what's there, `make` creates several files that contain the assembly code for all parts of WeensyOS--we can use these to look up what code is at this address! For example, to locate this instruction, **check obj/kernel.asm** for `413ad`, and might find: ``` current[10000].regs.reg_rax = -1; 413ad: 48 c7 80 10 bd 1f 00 movq $0xffffffffffffffff,0x1fbd10(%rax) ``` Oops, I guess `current[10000]` is out of range! A bug in process code (ie, userspace code like `p-allocator.cc`) might produce a message like this in `log.txt`; unfortunately, process backtraces do not have symbol information either. For example: ``` Process 1 page fault on 0xefed937b23 (write missing page, rip=0x100015)! #0 0x100015 #1 0x10011c ``` To figure out what this means, we can check the .asm file for the relevant process (here, `obj/p-allocator.asm`) to decode the instructions and their containing functions, and maybe get insight into the bug: ``` 0000000000100000 <cause_trouble()>: ... void cause_trouble() { 100000: f3 0f 1e fa endbr64 heap_top[1030481984291] = 61; 100004: 48 b8 23 3b 83 ed ef movabs $0xefed833b23,%rax 10000b: 00 00 00 10000e: 48 03 05 f3 1f 00 00 add 0x1ff3(%rip),%rax # 102008 <heap_top> 100015: c6 00 3d movb $0x3d,(%rax) 0000000000100019 <process_main()>: ... cause_trouble(); 100117: e8 e4 fe ff ff call 100000 <cause_trouble()> 10011c: eb 90 jmp 1000ae <process_main()+0x95> ``` Oops, I guess `heap_top[1030481984291]` is out of range! ## 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 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. :::warning <img src="https://csci0300.github.io/assign/labs/assets/apple.png"> **Note if you're using an ARM64 machine (e.g., Apple M1)** **Change: how to connect GDB** In step 3, instead of `gdb -x weensyos.gdb`, you must use the command `gdb-multiarch -x weensyos.gdb`. You should see a line stating: "The target architecture is assumed to be i386:x86-64." This will use a version of GDB that supports multiple different processor architectures, including ones different from your computer's hardware (in this case, it emulates the target architecture). ::: We can now debug the whole emulated computer as if it were a single process (which, actually, it is). # Submitting your work This assignment has two deadlines: - **Intermediate deadline (steps 1-4)**: by **8:00pm on Friday, November 7**, you should push work to your repository that completes steps 1-4, or has made reasonable progress towards doing so. Similar to the Snake intermediate deadlines, this is checkpoint is for your benefit: steps 5-7 are non-trivial, and you should leave yourself the following week to work on them. You do not need to have a completed README for this step. - **Final submission (all steps)**: **8:00pm on Friday, November 14**, you must have a commit with all steps completed, including your README. - After submitting, you should fill out the **[post-project form](https://forms.gle/n8D2YG3soNdL8NJ26)** to tell us about your project experience. The form is due 1 day after the 72-late hour cutoff (i.e., Wednesday, November 19) 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`**. <details> <summary><span>Remind me again what the <code>README.md</code> should contain?</span> </summary> * The `README.md` file will include the following: Any design decisions you made and comments for graders, under *"Design Overview"*. If there's nothing interesting to say, just list "None". * Any collaborators and citations for help that you received, under "*Collaborators"*. CS 300 encourages collaboration, but we expect you to acknowledge help you received, as is standard academic practice. * If you implemented any extra credit features, specify how to run each of your test programs and how they demonstrate the relevant extra credit functionality. </details> ### 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! :computer: :smile:** --- <small>_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.</small>