Deadlines

• Tell me partners: due Friday, February 9th, at 4:00pm

• Design document: due Monday, February 12th Wednesday, February 14th, at 10:00pm (post on a “design pod” channel on Slack)

• Peer feedback: due Friday, February 16th, at 10:00pm (again as a post on Slack)

• Lab #3 retrospective: due Friday, February 16th, at 10:00pm (on Gradescope)

• Code implementation: due Friday, February 23rd, at 10:00pm (on Gradescope)

Introduction

In this lab, we are going to allocate pages of physical memory for a user process. For stack memory, this will be just at the moment the process needs them (i.e., allocating them on-demand). For the heap, it will be when a user process requests more heap memory.

Goals

To complete this lab, we will explore page faults, physical vs. memory, and the system call sbrk.

This lab is broken into two parts:

• Part 1: Grow the user stack
• Part 2: Grow the user heap

Collaboration policy

For this and most other assignments, you are encouraged to talk at a high level with your classmates. However, any low-level discussions (e.g., that involve actual code instead of ideas) should be with at most one other student in the class.

See our class collaboration policy for more information.

Lab Assignment #3 retrospective

Instead of doing quite so much peer review for this lab, you’ll spend some of that time reflecting on how Lab #3 went. Your goal is to generate ~2 paragraphs answering the following questions:

• What went well?
• What really didn’t go well?
• What are some things that took more time than you expected?
• What, if anything, went better than you expected?
• Did you follow your implementation plan from your design? Did you swap over to my design? What parts of yours did you keep?
• If you could tell students in future offerings of this course something to help them with this lab, what would you tell them?

You should complete this individually and submit it on Gradescope.

Getting started

Pull any changes to the baseline code by running

git pull upstream main

and merging. If you have any issues with this, please let me know!

After the merge, double check that your code still passes the Lab Assignments #1, #2, and #3 tests.

Background

Memory regions

In osv, information about a virtual address space is tracked via a list of memory regions (i.e., segments). A memory region tracks a contiguous region of memory within an address space. A memory region belongs to only one address space; an address space can have many memory regions. The kernel sets up memory regions for each process and uses them to track valid memory ranges for a process to access. Each user process has a memory region for code, stack, and heap on startup.

More details can be found here.

Page tables

In addition to managing each process’s virtual address space, the kernel is also responsible for setting up the address translation table (page table) which maps a virtual address to a physical address. Each virtual address space has its own page table, which is why when two processes access the same virtual address they are actually accessing different data. In osv, a struct vpmap is used to represent a page table. In the file include/kernel/vpmap.h there is a list of operations defined for a page table. For example, vpmap_map maps a virtual page to a physical page.

Page faults

A page fault is a hardware exception that occurs when a process accesses a virtual memory page without a valid page table mapping, or with a valid mapping, but where the process does not have permission to perform the operation.

On a page fault, the process will trap into the kernel and trigger the page fault handler. If the fault address is within a valid memory region and has the proper permission, the page fault handler should allocate a physical page, map it to the process’s page table, and resume process execution (i.e., return). Note that a write on a read-only memory permission is not a valid access and the calling process should terminate.

In osv, the page fault handler is kernel/pgfault.c:handle_page_fault (look familiar?):

void
handle_page_fault(vaddr_t fault_addr, int present, int write, int user) {
    if (user) {
        __sync_add_and_fetch(&user_pgfault, 1);
    }
    // turn on interrupt now that we have the fault address
    intr_set_level(INTR_ON);

    /* Your Code Here. */

    if (user) {
        // kprintf("fault addres %p, present %d, wrie %d, user %d\n", fault_addr, present, write, user);
        proc_exit(-1);
        panic("unreachable");
    } else {
        // kprintf("fault addr %p\n", fault_addr);
        panic("Kernel error in page fault handler\n");
    }
}

• fault_addr is the address that was attempted to be accessed
• present is set to 1 if it was a page protection issue (e.g., the fault address has a corresponding physical page mapped, but permission is off); this is not set if the page is not present
• write is set to 1 if the fault occurred on a write
• user is set to 1 if the fault occurred in user mode

Allocating pages for the stack

A simple approach is to give each process one page of stack memory when the process is created. Great! But what if a process wants to use more stack? One option is to allocate more physical pages for the stack on startup and map them into the process’s address space. But if a process doesn’t actually use all of its stack, the allocated physical pages are wasted while the process executes.

To reduce this waste, a common technique is to allocate physical pages for additional stack pages on demand. For this part of the lab, you will extend osv to do on-demand stack growth. This means that the physical memory of the additional stack page is allocated at run-time. Whenever a user application issues an instruction that reads or writes to the user stack (e.g., creating a stack frame, accessing local variables), we grow the stack as needed.

Allocating pages for the heap

Heap growth differs from stack growth in that a process must explicitly request more virtual addresses to be allocated to its heap. A process that needs more memory at runtime can call sbrk (“set program break”) to grow its heap size. The kernel implementation of sbrk is in kernel/syscall.c:sys_sbrk. The common use case is the situation in which a user library routine (e.g., malloc in C or new in C++) calls sbrk whenever the application asks to allocate memory that cannot fit on the current heap (e.g., if the hepa is completely allocated due to prior calls to malloc).

If a user application wants to increase the heap size by n bytes, it calls sbrk(n); the call sbrk(n) returns the OLD limit. The user application can also decrease the amount of the heap by passing negative values to sbrk. Generally, the user library asks sbrk to provide more space than immediately needed, to reduce the number of later system calls.

Implementation

Part 1: Grow the user stack on-demand

You can find the current code to set up each process with a page of stack memory in kernel/proc.c:stack_setup. Currently stack_setup does the following:

1. Allocate one page of physical memory (pmem_alloc).
2. Add a one-page memory region (segment) to the process’s address space (as_map_memregion). Note that as_map_memregion takes the address of the start of the region as its second argument, which will be the lowest address within the region.
3. Add a page table entry to map the virtual address of the stack’s page to the address of the newly allocated physical page (vpmap_map). This function also takes the address of the start of a page, which will again be the lowest address within the page.

For this lab, you should limit your overall stack size of USTACK_PAGES (10) pages total. To support stack growth, you should first expand the range of stack memory region so that any address within [10 pages below USTACK_UPPERBOUND, USTACK_UPPERBOUND] is valid.

You will want to modify Step #2 above to allow 10 stack pages. Step #1 should remain unchanged, as you want to allocate additional pages only on demand (i.e., as part of the page fault handler). Step #3 is conceptually the same, but you will need to make sure it is mapping the first (i.e., the highest) page in the stack. You should ignore the /* Your Code Here. */ comment in stack_setup for now—a different extension of stack behavior is an option for the final project.

Your next step will be to implement the page fault handler. To avoid information leaking, you need to memset the allocated physical page to 0s. Note that you cannot directly access physical memory, so you need to translate the physical address to a kernel virtual address using kmap_p2v(paddr) before you do the memset. (If you want to look at it, memset is declared in include/lib/string.h and implemented in lib/string.c.)

For this part, the reference solution modified:

• kernel/proc.c
• kernel/pgfault.c

Part 2: Create a user-level heap

After you have set up the page fault handler to handle on-demand stack growth, you will next support dynamic heap growth.

When a user process is first spawned, its heap memory region is initialized to size 0, so the first call to malloc always calls sbrk. In osv, the kernel needs to track how much memory has been allocated to each process’s heap and also extend/decrease the size of the heap based on the process’s request. To do so, you will need to implement kernel/mm/vm.c:memregion_extend.

Once you have properly set up the memory region range for dynamic heap growth, you can handle page faults from heap addresses similar to how you handle on-demand stack growth. osv internally allocates and frees user memory at page granularity, but a process can call sbrk to allocate/deallocate memory at byte granularity. The OS does this to be portable, as an application should not depend on the machine adopting a specific page size.

In user space, we have provided an implementation of malloc and free (in lib/malloc.c) that uses sbrk. After the implementation of sbrk is done, user-level applications should be able to call malloc and free.

For this part, the reference solution modified:

• kernel/mm/vm.c
• kernel/syscall.c
• kernel/pgfault.c

Testing

After you implement the system calls described above, test your Lab Assignment #4 code by either running individual tests in the osv shell (i.e., make qemu and then enter the name of the test file in user/lab4 without the .c) or run python3 test.py 4 to run all of the tests.

Debugging

When debugging, I would recommend running individual tests in osv. Note that test.py depends on observing TEST-NAME passed in the output from osv, and the presence of debugging print statements can interfere with this (as output from various processes can get mixed together). It’s also important, therefore, that you disable any debugging print statements before submission to Gradescope.

What to turn in

You will submit your work for this assignment via Gradescope.

Gradescope lets you submit via GitHub, which is probably the easiest method. All you’ll need to do is to connect your GitHub account (the Gradescope submission page has a button for this) and select the repository and the branch you wish to submit. Alternatively, you can create a .zip file of the osv-w24 directory and upload that. The arch, include, and kernel directories from your submission will be used in testing.

When you submit, the autograder will compile your code and run the test cases. The Gradescope autograder will run each test multiple times.

Although you are allowed to submit your answers as many times as you like, you should not treat Gradescope as your only debugging tool. Many people may submit their assignments near the deadline, and thus Gradescope will take longer to process the requests. You may not get feedback in a timely manner to help you debug problems.

Grading

This assignment will be graded out of 100 points, with 90 points coming from the tests shown in the table below. Comments explaining your approach can help earn partial credit if there are tests that don’t pass. The remaining 10 points are based on coding style, so make sure to submit clean, well-organized code.