CS5600 Lab4: WeensyOS

Introduction

In this lab, you will implement process memory isolation, virtual memory, and a system call (fork()) in a tiny (but real!) operating system, called WeensyOS.

This will introduce you to virtual memory and reinforce some of the concepts that we have covered this semester.

The WeensyOS kernel runs on x86-64 CPUs. Because the OS kernel runs on the “bare” hardware, debugging kernel code can be tough: if a bug causes misconfiguration of the hardware, the usual result is a crash of the entire kernel (and all the applications running on top of it) or keep rebooting. And because the kernel itself provides the most basic system services (for example, causing the display hardware to display error messages), deducing what led to a kernel crash can be particularly challenging. In the old days, the usual way to develop code for an OS (whether as part of a class, in a research lab, or in industry) was to boot it on a physical CPU. The lives of kernel developers have gotten much better since. You will run WeensyOS in QEMU.

QEMU is a software-based x86-64 emulator: it “looks” to WeensyOS just like a physical x86-64 CPU, but if your WeensyOS code-in-progress wedges the (virtual) hardware, QEMU itself and the whole OS that is running on the “real” hardware (that is, the Linux OS you booted and that QEMU is running on) survive unscathed (“real” is in quotation marks because if you’re using VMWare or VirtualBox, your Linux OS devbox is itself running on a virtualized environment). So, for example, your last few debugging printf()s before a kernel crash will still get logged to disk (by QEMU running on Linux), and “rebooting” the kernel you’re developing amounts to re-running the QEMU emulator application.

heads up: As always, it’s important to start on time. In this case, on time means starting at day one, as you will almost certainly need all of the allotted time to complete the lab. This is likely your first time to do kernel development. Kernel development is less forgiving than developing user-level applications; tiny deviations in the configuration of hardware (such as the MMU) by the OS tend to bring the whole (emulated) machine to a halt.

To save yourself headaches later, read this lab writeup in its entirety before you begin.

Challenge: Lab4’s challenge is optional. In this challenge, you will complete the tiny kernel with some necessary functions, which is described at the end of the lab.

Section 0: Getting started

1. Click the GitHub Lab4 link on Canvas homepage to create your Lab4 clone on GitHub.
2. Start your VM and open the VM’s terminal.
3. Clone Lab4 repo to VM:

   $ cd ~
   $ git clone git@github.com:NEU-CS5600-labs/lab4-<Your-GitHub-Username>.git lab4
   

   Note that the repo address git@github.com:... can be obtained by going to GitHub repo page (your cloned lab4), clicking the green “Code” button, then choose “SSH”.

4. Check contents:

   $ cd ~/lab4
   $ ls
   // you should see:
   COPYRIGHT       build           k-hardware.cc   kernel.cc       p-allocator.cc  u-lib.cc
   GNUmakefile     cbyteswap.hh    k-memviewer.cc  kernel.hh       p-exit.cc       u-lib.hh
   atomic.hh       elf.h           k-pci.hh        lib.cc          p-fork.cc       weensyos.gdb
   boot.cc         k-apic.hh       k-vmiter.cc     lib.hh          slack.txt       x86-64.h
   bootentry.S     k-exception.S   k-vmiter.hh     log.txt         types.h
   

5. Install required packages:

   sudo apt install qemu qemu-system-x86
   

Note: all the shell commands below happen within the folder ~/lab4/.

Another heads up. Given the complexity of this lab, and the possibility of breaking the functionality of the kernel if you code in some errors, make sure to commit and push your code often! It’s very important that your commits have working versions of the code, so if something goes wrong, you can always go back to a previous commit and get back a working copy! At the very least, for this lab, you should be committing once per step (and probably more often), so you can go back to the last step if necessary.

Section 1: Introducing WeensyOS

WeensyOS is a tiny kernel that can run on bare-metal x86-64 machines (for lab4, QEMU’s emulated CPUs), developed by Eddie Kohler. The initial state of the kernel contains code for bootstrapping kernel, handling exceptions/syscalls, executing user-level program, and helper functions for your Lab4 exercises.

Goals

In Lab4, you will implement

• memory isolation for WeensyOS processes
• full virtual memory, which will improve utilization
• implement fork() (creating new processes at runtime)

We’ve provided you with a lot of support code; the code you will need to write is in fact limited in extent. Our complete solution (excluding the challenge) consists of well under 200 lines of code beyond what we initially hand out to you. All the code you write will go in kernel.cc.

Checking if your kernel works as expected

For this assignment, your primary checking method will be to run your instance of Weensy OS and visually compare it to the images you see below in the assignment.

Studying these graphical memory maps carefully is the best way to determine whether your WeensyOS code for each stage is working correctly. Therefore, you will definitely want to make sure you understand how to read these maps before you start to code (see below).

Compile, run, and initial state

Apple M1/2 users (ARM CPU) In your VMWare virtual machine, you need to do the following configuration before compiling:

(1) $ sudo apt install g++-11-x86-64-linux-gnu
(2) create a file "config.mk" under "~/lab4" with
    """
    CCPREFIX = x86_64-linux-gnu-
    """

update 03/16 If you have problem installing g++-11-x86-64-linux-gnu, try sudo apt install g++-x86-64-linux-gnu.

Exercise 0 Compile and play with WeensyOS.

• Run make run. You should see something like the below, which shows four processes running in parallel, each running a version of the program in p-allocator:
• This above image loops forever; in an actual run, the bars will move to the right and stay there. Don’t worry if your image has different numbers of K’s or otherwise has different details.
• Stop now to read and understand p-allocator.cc.
• If your bars run painfully slowly, edit the p-allocator.cc file and reduce the ALLOC_SLOWDOWN constant.
• If QEMU’s default display causes accessibility problems, you will want to run make run-console.

Understanding memory display

Here’s how to interpret the memory map display:

• WeensyOS displays the current state of physical and virtual memory. Each character represents 4 KB of memory: a single page. There are 2 MB of physical memory in total. (How many pages is this?)

• WeensyOS runs four processes, 1 through 4. Each process runs a different program. The four programs are compiled from the same source code (p-allocator.cc), but for each program the compiler is told to use a different region of memory for its text and data segments.

• Each process asks the kernel for more heap space, one page at a time, until it runs out of room. Each process’s heap begins just above its code and global data, and ends just below its stack. The processes allocate space at different rates: compared to Process 1, Process 2 allocates space twice as quickly, Process 3 goes three times faster, and Process 4 goes four times faster. (A random number generator is used, so the exact rates may vary.) The marching rows of numbers show how quickly the heap spaces for processes 1, 2, 3, and 4 are allocated.

• Here are two labeled memory diagrams, showing what the characters mean and how memory is arranged.

The virtual memory display is similar.

• The virtual memory display cycles between the four processes’ address spaces. However, all the address spaces are the same for now.
• Blank spaces in the virtual memory display correspond to unmapped addresses. If a process (or the kernel) tries to access such an address, the processor will page fault.
• The character shown at address X in the virtual memory display identifies the owner of the corresponding physical page.
• In the virtual memory display, a character is highlighted (i.e., black foreground and colored background, or “reverse video”) if an application process is allowed to access the corresponding address. Initially, any process can modify all of physical memory, including the kernel. Memory is not properly isolated.

Debugging your kernel

There are several ways to debug your kernel. We recommend:

• Add log_printf statements to your code (the output of log_printf is written to the file log.txt).
• Use assertions to catch problems early (for instance, call check_page_table to test a page table for obvious issues, or add your own).
• Sometimes a mistake will cause the OS to crash hard and reboot. Use make D=1 run 2>debuglog.txt to get additional, painfully-verbose debugging output. Search through debuglog.txt for check_exception lines to see where the exceptions occur.
• 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.

Kernel design I: memory layout

Initial physical memory layout (see also in kernel.cc):

  +-------------- 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

WeensyOS memory system layout is described by several constants.

Kernel design II: kernel and process address spaces

Kernel address space. WeensyOS begins with the kernel and all processes sharing a single address space (which is a bad design, but a good starting point for Lab4). This is defined by the kernel_pagetable page table. kernel_pagetable is initialized to the identity mapping: virtual address X (e.g., 0x2000) maps to physical address X (0x2000).

Why identity mapping? The kernel, though running with virtual memory, still needs the ability to access all of physical memory. It will be much easier (compared to real kernel) to manage pages when kernel’s virtual addresses mapping to the physical addresses with the same number.

User address space. Though starting with using the same space between kernel and processes, as you work through Lab4, you will shift processes to use independent address spaces, where each process can access only a subset of physical memory.

Note that each process page table must contain kernel mappings (addresses before PROC_START_ADDR). Why? Because WeensyOS’s syscalls need the kernel stack for the exception_entry and syscall_entry code paths. (The exception_entry and syscall_entry assembly codes explicitly install kernel_pagetable when they begin, and exception_return and the syscall return path install the process’s page table as they exit.)

More about WeensyOS—Lab4 “info session”

WeensyOS, though minimum, still has basics of a real kernel that runs on bare-metal machines. The info session has more details of

• kernel troubleshooting,
• the meaning of source files,
• the meaning the build files,
• and helper functions/classes: virtual memory iterators and program images and segments

Section 2: Kernel isolation

In the following, all your work will happen in kernel.cc. Feel free to scan the file to get a knowledge of what it will be about. The kernel starts to run from the kernel_start function.

You will use vmiter to create memory mappings, and use log_printf to debug.

Exercise 1 Confirm kernel’s identity mapping

This is a warming-up exercise for you to understand how vmiter and log_printf work. The goal is to confirm by yourself that kernel space (i.e., using the kernel_pagetable) indeed uses identity mapping. Here is what you should do:

• Go to function kernel_start in kernel.cc.
• Finish the TODO for Exercise 1.
• Please expect to spend some time understand how vmiter works. See an introduction in info session: vmiter.
• The best way to learn (especially in systems) is to do it and learn from your mistakes.

WeensyOS processes could stomp all over the kernel’s memory if they wanted. Better stop that.

Exercise 2 Stop processes accessing kernel memory.

• Change kernel_start, the kernel initialization function, so that kernel memory is inaccessible to applications—except for the memory holding the CGA console (the single page at CONSOLE_ADDR == 0xB8000).
• When you are done, WeensyOS should look like this:
• In the virtual map, kernel memory is no longer highlighted (i.e., reverse-video), since the user can’t access it.
• Also note the lonely CGA console memory block.
• In addition, make sure that your sys_page_alloc system call preserves kernel isolation: Applications shouldn’t be able to use sys_page_alloc to screw up the kernel. This requires changes to the SYSCALL_PAGE_ALLOC case in syscall. Read the description of sys_page_alloc in u-lib.hh to get a feeling for the possible errors.

When you’re done with this section, make sure to commit and push your code!

Section 3: Isolated address spaces

Before moving to fix more permission problems of your kernel (for example, a process can see other processes’ memory), you need to have a better understanding of the program and its process memory layout.

Exercise 3 Understand program images and segments

• Read info session: program images and segments.
• Copy the following code to process_setup in kernel.cc:

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("  seg[%zu]: addr %p, size %p, data_size %p, read-only? (%s)\n",
               n, 0xffff /* your code here */,
               0 /* your code here */,
               0 /* your code here */,
               "UNKNOWN" /* your code here */); }

• Fill in the above blanks (i.e., /*your code here*/) by using segment’s interfaces.
• Check if your outputs (in log.txt) is accurate by comparing with the ground truth:
  • run objdump -p obj/p-allocator (also p-allocator2/3/4) to get the ground truth.
  • compare the vaddr, memsz, and flags (r: read, w: write, x: executable) from the objdump with your ouptuts.
• (after finishing the above) 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.

For your current kernel, though kernel memory has been isolated, processes still see each other’s memory. This is of course not ideal. Next, you will isolate applications’ memory by creating an address space for each process.

Exercise 4 Isolate address spaces

• What we want to achieve is: each process only has permission to access its own pages.
• Implement process isolation by giving each process its own independent page table. Your kernel should look like this:
• Each process only has permission to access its own pages, which you can tell because only its own pages are shown highlighted (i.e., reverse-video).
• How to implement per-process page tables in process_setup:
  • Allocate a new, initially-empty page table for the process by calling kalloc_pagetable.
  • Copy the mappings from kernel_pagetable into this new page table using vmiter’s try_map. This ensures that the required kernel mappings are present in the new page table. You can do this using a loop with two vmiters, or you can set the mappings yourself (they are identity mappings).
  • Note: vmiter’s try_map will allocate page table pages as needed. All calls to try_map in process_setup are guaranteed to succeed. (That won’t be true for later parts of the lab.) In process_setup, feel free to assert that the return value from try_map is 0.
  • Then you will need to make sure that any page that belongs to the process is mapped as user-accessible. These are the pages the process needs to access, including its code, data, stack, and heap segments.
  • You’ll also need to update syscall_page_alloc. Why?
    • Think of what will happen when a process p-allocator allocates memory?
    • Is the newly allocated memory (in syscall_page_alloc) mapped into the process’s virtual address space?
    • hint: the global variable proc* current is useful.
• If you create an incorrect page table, WeensyOS might crazily reboot. Don’t panic! Add log_printf statements and infinit loop while (true) {} to debug.

Note the diagram now has four pages (why four? because of 4-level page table) for each process in the kernel area, starting at 0x1000. These are the four-level page tables for each process. (The colored background indicates that these pages contain kernel-private page table data, even though the pages “belong” to the process.) The first page was allocated explicitly in process_setup; the other pages were allocated by vmiter’s try_map as the page table was initialized.

Again, once finished with excersize 4, commit and push!

Section 4: Virtual page allocation

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. Next, you will fix this.

From here forward, you will not see “Exercise X” or “your code here” in the “kernel.cc”. For one, you should be pretty familiar with your kernel. For another, your modification will be all over the place.

Exercise 5 Virtual page allocation

• Change your operating system to allocate all process data, including its code, globals, stack, and heap, using kalloc instead of direct access to the pages array.
• Here’s how our OS looks after this step.
• As essence, your task is to use kalloc to replace direct accesses to physical memory physpages for better memory management. (hint: search in kernel.cc for physpages)
• Virtual page allocation will complicate the code that initializes process code in process_setup.
• You’ll need to figure out why (hint: which page table is in force in process_setup? and does memcpy works as before?) and find a way around it (hint: vmiter or set_pagetable).

Now the processes are isolated, which is awesome, but they’re still not taking full advantage of virtual memory. Isolated address spaces can use the same virtual addresses for different physical memory. There’s no need to keep the four process address spaces disjoint.

Exercise 6 Overlapping address spaces

• In this exercise, change each process’s stack to grow down starting at address 0x300000 == MEMSIZE_VIRTUAL. Now the processes have enough heap room to use up all of physical memory!
• Here is what your kernel will look like:
• If there’s no physical memory available, sys_page_alloc should return an error code to the calling process, such as -1. Do not kill the calling process! Lack of memory is a potentially recoverable problem.

As always, make sure to commit and push after finishing this step!

Section 5: Fork

The fork() system call is one of Unix’s great ideas (as we stressed in class). It starts a new process as a copy of an existing process. The process that calls fork() is called the parent process, and the newly created copy is called the child process. The system call appears to return twice: it returns 0 to the child, and returns the child’s process ID to the parent.

Run WeensyOS with make run-fork. Alternately, at any time, press the ‘f’ key; this will soft-reboot WeensyOS and ask it to run a single p-fork process, rather than the gang of allocators. You should see something like this:

This is because you haven’t implemented fork yet. (The error message might be slightly different due to the updated skeleton code.)

Exercise 7 Implement fork.

• Implement SYSCALL_FORK in syscall(...).
• When a process calls fork, look for a free process slot in the ptable[] array for the child. Don’t use slot 0.
• If a free slot is found, copy the parent’s page table for the child.
  • For addresses below PROC_START_ADDR (0x100000), the parent and child page tables will have identical mappings (same physical addresses, same permissions).
  • But for addresses at or above PROC_START_ADDR, the child’s page table must map 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 parent page table. Whenever the parent process has an application-writable, non-console 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 page table, using the permissions from the parent page table.
• The child process’s registers are initialized as a copy of the parent process’s registers, except for reg_rax.
• If fork fails in any way—if there is no free process slot, or there’s not enough memory to create a complete copy of the parent process—then fork must clean up after itself and return -1. The cleanup process must free process slots that were allocated during the fork attempt.
• When you’re done, you should see something like this after pressing ‘f’.
• A result like this means you forgot to copy the data for some pages, so the processes are actually sharing stack and/or data pages:

Info session: more about WeensyOS

[A] Troubleshooting

There are several ways to kill a recalcitrant WeensyOS (if, for instance, your OS has become unresponsive).

• If QEMU is running in its own graphical window, then close the window. This will kill the embedded OS.

• Open another terminal, change into the WeensyOS directory, and run make stop to stop all running QEMUs.

• Run make run-gdb to start up the OS with support for GDB debugging. This will start the OS, but not GDB. You must run gdb -ix build/weensyos.gdb to connect to the running emulator; when GDB connects, it will stop the OS and wait for instructions.

• If you experience runtime errors involving obj/libqemu-nograb.so.1, put QEMU_PRELOAD_LIBRARY= in build/rules.mk. This disables a shim we use that prevents QEMU from grabbing the mouse.

[B] Source files

Real operating systems are big. We have tried to boil down this OS to a minimum, comment it to help you, and separate x86-64 specifics from more fundamental issues.

Common files

Boot loader

Kernel core

Kernel libraries

Processes

[C] Build files

The main output of the build process is a disk image, weensyos.img. QEMU “boots” off this disk image, but the image could conceivably boot on real hardware! The build process also produces other files that can be useful to examine.

[D] Virtual memory iterators (vmiter)

The vmiter class examines and modifies x86-64 page tables, especially their virtual-to-physical address mappings.

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:

x86_64_pagetable* pt = ...;
uintptr_t pa = vmiter(pt, va).pa();    // returns uintptr_t(-1) if unmapped

The kptr method returns a pointer corresponding to the physical address. Use this method if you need to examine the physical memory located at va. If the virtual address is mapped, then kptr’s address value is the same as pa (because the kernel is identity mapped). kptr returns nullptr if the virtual address is unmapped.

The perm method returns the permissions of the current mapping.

if ((vmiter(pt, va).perm() & PTE_W) != 0) {
    // then `va` is present and writable in `pt`
}

perm returns a bitwise—or of flags, possibly including PTE_P (numeric value 1), PTE_W (numeric value 2), and PTE_U (numeric value 4). PTE_P marks Present pages (pages that are mapped). PTE_W marks Writable pages. PTE_U marks User-accessible pages—pages accessible to unprivileged processes. Kernel memory should be mapped with permissions PTE_P|PTE_W, which allows the kernel to read or write the memory, but prevents all access by processes.

(Note that perm()’s return value may include other bits than PTE_P, PTE_W, and PTE_U, because the processor automatically modifies some bits as it runs. There are convenient shorthands—present(), writable(), and user()—for PTE_P, PTE_W, and PTE_U.)

Traversing page tables

The find(va) method changes the iterator’s current virtual address to va. You can also say it += DELTA, which increments the current virtual address by DELTA.

It is common to use vmiter in loops. This loop prints all present mappings in the lower 64KiB of memory, moving one page at a time:

for (vmiter it(pt, 0); it.va() < 0x10000; 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’s try_map function modifies mappings in a page table. This code maps physical page 0x3000 at virtual address 0x2000, with permissions P, W, and U:

int r = vmiter(pt, 0x2000).try_map(0x3000, PTE_P | PTE_W | PTE_U);
if (r < 0) {
    // there was an error; mappings remain unchanged
}

vmiter’s try_map returns -1 if it cannot add a mapping (this happens if it fails to allocate memory for a page table page).

You can also use try_map to change a mapping’s permissions; this adds PTE_W to the permissions for virtual address va:

vmiter it(pt, va);
assert(it.present());
int r = it.try_map(it.pa(), it.perm() | PTE_W);

Interface summary

• vmiter walks over virtual address mappings.
• pa() and perm() read current addresses and permissions;
• map() and try_map() modify mappings.
• See all interfaces of vmiter in k-vmiter.hh.

[E] Program images and segments

Program image

A program image is the data generated by the compiler and linker that defines a program’s initial state. It’s essentially a recipe for constructing a process. It defines how the process’s initial virtual address space should be organized, contains the instruction and data bytes that should be used to initialize that address space, and specifies which instruction byte is the first instruction to execute. Operating systems use program images to initialize new processes.

Segment

A segment is a region of process memory. We mentioned segments a lot in process memory layout: they are text, data, heap, and stack segments. Most program image data consists of information about the segments that must be loaded into processes’ initial memory state. (The operating system decides on the size and location of the stack segment itself, and the heap segment starts out empty.) You can print about a program image’s segment definitions using objdump -p.

WeensyOS program images and segments

The WeensyOS kernel includes, as part of its kernel data, program images for all the processes it knows how to run (e.g., p-allocator, p-allocator2, p-fork). The program_image and program_image_segment data types allow you to query these images.

To understand their interfaces, read program_image and program_image_segment in kernel.hh.

(optional) Challenge: Freeing memory

So far none of your test programs have ever freed memory or exited. Memory allocation’s pretty easy until you add free! So let’s add free by allowing applications to exit.

Challenge process exit and free memory

• In this exercise you’ll implement the sys_exit system call, which exits the current process. This exercise is a capstone since freeing memory will tend to expose weaknesses and problems in your other code.

• To test your work, use make run-exit. Alternately, you can press ‘e’ at any time, which his reboots WeensyOS to run the p-exit program.
  • (Initially it’ll crash because sys_exit() isn’t implemented yet.)
  • p-exit processes all alternate among forking new children, allocating memory, and exiting. The result is that once your code is correct, p-exit makes crazy patterns forever, like this:

• (Your picture will not have ‘S’ characters, which represent shared pages.)

• A fully correct OS can run p-exit indefinitely. An OS with a memory leak will display Ls in the physical memory map—the leaked page—and if run long enough, Ls will take over the screen. This OS leaks memory:
• Here’s your task:
  • Study ptiter, physical memory iterators.
  • Complete kfree so that kfree frees memory. Make sure that kalloc can re-use freed memory.
  • sys_exit should mark a process as free and free all of its memory. This includes the process’s code, data, heap, and stack pages, as well as the pages used for its page directory and page table pages. The memory should become available again for future allocations.
  • Use vmiter and ptiter to enumerate the relevant pages. But be careful not to free the console.
  • You may also need to change fork and perhaps other places. In p-exit, unlike in previous parts of the lab, sys_fork and sys_page_alloc might be called when there’s not 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 a sys_page_alloc or sys_fork system call runs out of memory during its operation:
    • The system call must clean up after itself. Any kernel memory or other resources (e.g., process slots) allocated during the system call must be freed.
    • The system call must return -1 to the caller.
• Note that out-of-memory events in system calls must not panic the kernel, and they must not cause the calling process to exit. It is not an error when a system call fails! Instead the error return value is passed to the process to handle as it prefers.
• Reducing ALLOC_SLOWDOWN in p-exit may encourage errors to manifest, but you may need to be patient.

There should be no memory leaks!

Physical memory iterators (ptiter)

The ptiter type iterates through the physical memory used to represent a page table. (x86-64 page tables are hierarchical structures that can comprise multiple pages of memory.) ptiter is useful mostly when freeing page table structures.

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

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

Notes:

• 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.
• ptiter also doesn’t visit the actual data page.
• Note also that ptiter’s level is one less than you might expect (it returns a number between 0 and 3, rather than between 1 and 4).

Finally, submit your work

Submitting consists of three steps:

1. Executing this checklist:
   • Fill in slack.txt with (1) your name and NUID, (2) slack hours you used, (3) if you took the challenge, and (4) acknowledge your influences.
   • Make sure that your code can build without problems.
   • Make sure you have committed all your changes (check with git status).

2. Push your code to GitHub:

    $ cd ~/lab4
    $ git commit -am 'submit lab4'
    $ git push origin
   
    Counting objects: ...
     ....
     To ssh://github.com/NEU-CS5600-labs/lab4-<username>.git
      7447116..deadbeef  main -> main
   

3. Actually commit your lab (with timestamp and git commit id):

   1. Get the git commit id of your work. A commit id is a 40-character hexadecimal string. You can obtain the commit id for the last commit by running the command git log -1 --format=oneline.

   2. Submit a file named git.txt to Canvas. (there will be an assignment for this lab on Canvas.) The file git.txt contains two lines: the first line is your github repo url; the second line is the git commit id that you want us to grade. Here is an example:

       git@github.com:NEU-CS5600-labs/lab4-<username>.git
       29dfdadeadbeefe33421f242b5dd8312732fd3c9
      

      Notice: the repo address must start with git@github.com:... (not https://...). You can get your repo address on GitHub repo page by clicking the green “Code” button, then choose “SSH”.

   3. Note: You can submit as many times as you want; we will grade the last commit id submitted to Canvas. Also, you can submit any commit id in your pushed git history; again, we will grade the commit id submitted to Canvas.
      Notice: if you submit multiple times, the file name (git.txt) changes to git-N.txt where N is an integer and represents how many times you’ve submitted. We will grade the file with the largest N.

NOTE: Ground truth is what and when you submitted to Canvas.

• alertA non-existent commit id in Canvas means that you have not submitted the lab, regardless of what you have pushed to GitHub—we will not grade it. So, please double check your submitted commit id!

• The time of your submission for the purposes of tracking lateness is the timestamp on Canvas, not the timestamp on GitHub.

This completes the lab.

Acknowledgments

This lab is created by Eddie Kohler, with modifications by the CS5600 staff. The lab instructions are borrowed from Eddie Kholer’s CS61 at Harvard University and Mike Walfish’s CS202 at NYU.