<style> details { margin-top: 0.5em; margin-bottom: 0.5em; } summary { //font-weight: bolder; } summary:hover { text-decoration: underline; } blockquote { font-size: 16px; } .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 **Steps 1-4 Due Friday, April 4th at 8:00 PM EDT** <br /> **All Steps Due Friday, April 11th at 8: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 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-s25-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 (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 <span style="background-color:red">**reverse-video**</span> if an application process is allowed to access the corresponding address. [Reverse video](https://en.wikipedia.org/wiki/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: | | | |--|--| | `KERNEL_START_ADDR` | Start of kernel code. Equals `0x40000`. | | `KERNEL_STACK_TOP` | Top of kernel stack (the kernel stack is one page long). Equals `0x80000`. | | `CONSOLE_ADDR` | CGA console memory. Equals `0xB8000`. Values written to this page get printed in the terminal. All processes have read/write access to this page. | | `PROC_START_ADDR` | Start of application code. Applications should not be able to access memory below `PROC_START_ADDR`, except for the single page of console memory. Equals `0x100000` (1MB). | | `MEMSIZE_PHYSICAL` | Size of physical memory. WeensyOS does not support physical addresses ≥ `MEMSIZE_PHYSICAL`. Equals `0x200000` (2MB). | | `MEMSIZE_VIRTUAL` | Size of virtual memory. WeensyOS does not support virtual addresses ≥ `MEMSIZE_VIRTUAL`. Equals `0x300000` (3MB). | | `PAGESIZE` | Size of a memory page. Equals `4096` (or equivalently, `1 << 12`). | <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> 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. <details> <summary><i><span style="color:#0000EE">Optional: How does CGA console memory work?</span></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> ## Relevant Files We provide a lot of support code for the WeensyOS, but the code you write will be limited. Don't be overwhelmed by the stencil files! Take a look at `README-OS.md` for more information on the organization of the OS, but you don't have to read through or understand all the files to complete this project. Here is a table summarizing relevant files that you may want to look at (but definitely feel free to browse through the entire codebase if you're curious!): | | | |--|--| | `kernel.hh` | Declares constants and function headers for the kernel. Some of these kernel functions are implemented in `kernel.cc` (while others are in `k-hardware.cc`) | | `kernel.cc` | The core of the kernel program. You will be editing this file throughout the assignment. | | `u-lib.hh` | User-space library with system call specifications and implementations. Your user-space processes can call functions in this file. | | `k-vmiter.hh` | Defines iterators for x86-64 page tables. The `vmiter` enumerates virtual memory mappings, while `ptiter` visits individual *page table* pages. | Here's a diagram of how these files fit together! `u-lib.hh` will invoke system calls which are defined in `kernel.{hh, cc}`. These functions will use the `vmiter` and `ptiter` defined in `k-vmiter.hh`. ``` +--------------+ +------------------------------------------+ | User Space | | Kernel Space | | | | | | | syscall | | | u-lib.hh +---------------------> kernel.{hh, cc} | | | | + | +--------------+ | | page iteration | | +--------------------> k-vmiter.hh | | | | | +------------------------------------------+ ``` In addition to these, it will be useful to know the three permission flags for pages defined in `x86-64.h`: * `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): ```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. ## 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. <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 **It may help to complete Lab 4 (Getting Familiar with WeensyOS) before you attempt to work on this project.** Doing so isn't strictly required since the lab and project are independent, but the lab will get you familiar with the codebase and helpers we provide. ::: ## Goal You will first implement complete and correct memory isolation for WeensyOS processes. After that, you will implement full virtual memory, which will improve memory utilization. Lastly, you will implement the `fork` system call --- creating new processes at runtime --- and the `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. :::info **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()`, the kernel initialization function in `kernel.cc`, so that kernel memory is inaccessible to applications -- except for the CGA 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` function. </details> ## Step 2: Process Isolation **Overview:**<br /> 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. :::info **Why are we doing this?** We don't want processes to interfere with each others' operations; otherwise, one malicious process could inject code into other processes to make them complete unintended actions. ::: <details> <summary><b>Specifications</b></summary> * Read through the comments for `process_setup()` to understand what this function is doing to set up a process to run. * The `process_setup` function should allocate a new, initially empty page table for the process. Do this by calling `kalloc()` (to allocate the level-4 page table page), and then calling `memset` (to ensure the page table is empty). * Read the comments for `kalloc` to make sure you understand the purpose of this function! * Copy the mappings to kernel memory from `kernel_pagetable` into this new page table using `vmiter::map`. This step is to ensure that the required kernel mappings are present in the new page table (which must be included for protected control transfer, see [Kernel and Process Address Spaces](https://csci0300.github.io/assign/projects/project4.html#Kernel-and-Process-Address-Spaces)). The easiest way to do this is to use a loop with two `vmiter`s; or you can set the mappings yourself (they are identity mappings); or, if you’re feeling crazy, you can set up the new page table yourself without using `vmiter` (that will show you really understand page tables!). * Note that `map` will allocate level-1, level-2, and level-3 page table pages on demand, so you don't have to manually allocate more pages for the page table. * Lastly, you will need to make sure that any page that **belongs** to the process is mapped as user-accessible (you will need to change a few places to do this). These are the pages the process needs to access, including its code, data, stack, and heap segments. </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_loader` 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 `program_loader::writable()`! * The `vmiter` supports both `map` and `try_map` operation. Figure out the difference between them, and determine which would allow you to error gracefully in `syscall_page_alloc()`. 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> ## Step 3: Virtual Page Allocation **Overview:**<br /> 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. :::info **Why are we doing this?** Processes must have a contiguous block 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. Our solution is virtual memory -- 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 direct access to the `pages` array. </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` (we provide our own implementations for these in `lib.cc`), and these functions take in physical addresses. Now that the virtual memory to physical memory mapping is not one-to-one, think about how you can figure out what addresses to pass into these functions! </details> ## Step 4: Overlapping Virtual Address Spaces **Overview:**<br /> 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 `link/` 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:** <br /> 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. <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. * You must also copy the process data in every application page shared by the two processes. The processes should not share any *user-accessible memory* except the console (otherwise they wouldn’t be isolated). 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 after pressing "f":  An image like this means you forgot to copy the data for some pages, so the processes are actually *sharing* stack and/or data pages:  </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:** <br /> 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. </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! </details> ## Step 7: Exit **Overview:**<br /> 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` 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 <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? * Change `kalloc` so that it can reuse freed memory (in the stencil code, `kalloc` will never reuse freed memory). * 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! * Read the documentation for `ptiter` in `k-vmiter.hh` to figure out how you can use `ptiter` to free up a page table! * You will also need to change `sycall_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-forkexit`, 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-forkexit` program will make crazy patterns forever like this:  A fully correct OS can run `p-forkexit` indefinitely. An OS with a memory leak will display a persistent blank spot in the physical memory map --- the leaked page --- and if run long enough, blank spots will take over the screen. This OS has a pretty bad leak; within 10 seconds it has run out of memory:  This OS’s leak is slower, but if you look at the bottom row of the physical memory map, you should see a persistently unused pages just above and to the left of the “V” in “VIRTUAL”. Persistently unused pages are a hallmark of leaks.  Reducing `ALLOC_SLOWDOWN` in p-forkexit may encourage errors to manifest, but you may need to be patient. **There should be no memory leaks!** </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> ## 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! Make sure to have a test program for *each* extra credit feature you implement. <details><summary>How to write a new test program:</summary> :::info 1. Choose a name for your test program. We’ll assume `testprogram` for this example. 2. Create a C++ file `p-testprogram.cc` for your test program. You will base this file off one of the existing programs (`p-allocator.cc`, `p-fork.cc`, or `p-forkexit.cc`). 3. Modify `GNUmakefile` to build your test program: add `$(OBJDIR)/p-testprogram` to the `PROCESS_BINARIES` definition, and `$(OBJDIR)/p-testprogram.o` to the `PROCESS_OBJS` definition. 4. Teach the `program_loader` about your test program. Look for `program_loader` code in `k-hardware.cc`. Then add declarations for `_binary_obj_p_testprogram_start` and `_binary_obj_p_testprogram_end`, and add the appropriate entry to the `ramimages` array. 5. Teach `check_keyboard` in `k-hardware.cc` about your program. Pick a keystroke that should correspond to your program and edit the “soft reboot process” accordingly. For instance: ```c++= if (c == 'a') { argument = "allocators"; } else if (c == 'e') { argument = "forkexit"; } else if (c == 't') { argument = "testprogram"; } ``` 6. Teach the `kernel()` function in `kernel.cc` about your program. Replace the current `if (command...)` statements with this: ```c++= if (command && program_loader::program_number(command) > 0) { process_setup(1, command); } else { // ... set up allocator processes ... } ``` (This only needs to be done once, for the first test program you add). Now you should be able to run your test program by typing `t`. ::: </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. We recommend: <!-- * Use assertions to catch problems early (for instance, you can implement a `check_page_table` function that tests a page table for obvious issues, such as missing mappings at virtual addresses that you expect to be mapped).--> * 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. :::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 build/weensyos.gdb`, you must use the command `gdb-multiarch -x build/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). ## Common Exceptions, Panics, and Unexpected Behaviors As with all kernel programming, there are a variety of different errors you can encounter in the WeensyOS project. Here are some common issues you may encouter: | | | |--|--| |Exception 13|This is a **General Protection Error**, i.e. the kernel or process accessed memory in a way that's not allowed, such as accessing memory beyond its allocated portion (a segmentation fault), executing illegal bytes, or attempting to execute a privileged instruction without those privileges. <br/><br/> Some questions to consider: <br/> -Are you be accessing an array out of bounds or dereferencing a null pointer?<br/>-Are you writing outside of the bounds of a page of physical memory?<br/>-Are the permissions set correctly for pages you are interacting with?| |Pages with asterisks (`*`)|A page has been detected as both kernel memory and user memory at the same time. <br/><br/> Some questions to consider: <br/>-How are you ensuring that kernel memory is not accessible for user programs?<br/>-What is the different in permissions between a kernel and user program?| # 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 8:00pm on Friday, April 4th**==, you must have a commit with steps 1-4 completed. ==**By 8:00pm on Friday, April 11th**==, you must have a commit with all steps completed. <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. * Ranking the difficulty and time consumption of the project, compared to other projects so far. We won't use this for grading, but we collect the data to calibrate for future years. * 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. :::info **Note:** If the commit you want graded is not your most recent one, you should flag the one you want graded and the grading commit will be updated after the autograder finishes. ::: **Congratulations, you've completed the fourth CS 300 project, and written part of your own operating system! :computer: :+1:** --- <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>