Problem set 3b: WeensyOS Fork

This assignment builds on problem set 3a to add fork support.

• Pset 3b is due Sunday 10/18.

Get the code

The p-fork.cc and p-exit.cc programs that exercise pset 3b functionality are new. Get them with

$ git pull; git pull --no-rebase handout main

or, alternately

$ git pull; git pull --no-rebase https://github.com/cs61/cs61-f26-psets.git main

You should have no conflicts, but if you do the usual advice applies.

Phase 6: Fork

The fork system call starts a new process by copying 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.

Implement fork.

• Look at other WeensyOS system calls as models for implementing your own system call. Also take a look at the fork man page to understand what this system call does.

• When a process calls fork, look for a free process slot in the ptable[] array for the child. Don’t use slot 0. The ptable[] array is made up of proc process descriptor objects, which are defined in kernel.hh.

• 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, which is initialized to 0.

• The child process should be runnable.

• 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 procedure must reset the child process slot to the free state. Eventually, after phase 7, it will also free any memory that was allocated during the fork attempt.

When you’re done, you should see something like this after make run-fork (or 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:

Phase 7: Freeing memory

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

In this phase, you’ll implement the sys_exit system call, which exits the current process. This 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 reboots WeensyOS to run the p-exit program. (Initially it’ll crash because sys_exit() isn’t implemented yet.) p-exit processes 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:

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:

Reducing ALLOC_SLOWDOWN in p-exit may encourage errors to manifest, but you may need to be patient.

Here’s your task.

1. Complete kfree so that kfree frees memory. Make sure that kalloc can re-use freed memory.

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

3. You may also need to change fork and perhaps other places. In p-exit, unlike in previous parts of the pset, 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.

There should be no memory leaks!

About 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

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

Phase 8: Shared read-only memory

It’s wasteful for fork() to copy all of a process’s memory. For example, most processes, including p-fork, never change their code. So 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.

Change process_setup to map read-only program segments using read-only memory. Use the seg.writable() function to detect whether a program segment can use read-only memory. Then, in fork, share read-only pages between processes rather than copying them; and, in exit, ensure that shared pages are correctly accounted for when a process exits.

Use vmiter::writable() to detect whether a page is read-only. Do not use an equality test like it.perm() == (PTE_P | PTE_U)! vmiter::perm() values often include bits like PTE_A and PTE_D that are automatically set by processor hardware, so equality tests on it.perm() will usually fail.

When you’re done, running p-exit should look like this:

Each process’s virtual address space begins with an “S”, indicating that the corresponding physical page is Shared by multiple processes.

Turnin

You will turn in your code by pushing your git repository to github.com/cs61/YOUR-PSET_REPO.git and updating the grading server.