Lab 4: On-Demand Paging

Important deadlines

• Design document due 2/11 (Friday) at 9:00pm (post to your design pod channel on Slack)
• Peer feedback due 2/4 (Monday) at 9:00pm (also post your design pod Slack channel)
• Lab implementation due 2/18 (Friday) at 9:00pm (submit on Gradescope).

Introduction

In this lab, we are going to cover allocating pages of physical memory for user process just at the moment the process needs them (i.e., allocating them on-demand).

osv uses an address space and a list of memory regions (i.e., segments) to track information about a virtual address space. A virtual address space ranges from virtual address [0, 0xffffffffffffffff] on a 64-bit machine. 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 use them to track valid memory ranges for a process to access. Each user process has a memory region for code, stack, and heap on start up. More details can be found here.

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 access different data. osv uses struct vpmap to represent the page table. include/kernel/vpmap.h defines a list of operations on the page table. For example vpmap_map maps a virtual page to a physical page.

You will be interacting with all these abstractions in this lab.

To pull any new changes and tests for this lab, run the command

$ git pull upstream master

and merge. After the merge, double check that your code still passes tests for previous labs.

Part 1: Grow user stack on-demand

In the stack_setup function in kernel/proc.c currently sets up each new process with a page of stack memory. Great! But what if a process wants to use more stack? One option is to allocate more physical pages for stack on start up 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. For this lab, you should limit your overall stack size to USTACK_PAGES (10) pages total.

To implement on-demand stack growth, you will need to understand how to handle 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.

osv’s page fault handler is kernel/pgfault.c:handle_page_fault.

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

• fault_addr is the address that was attempted to be accessed
• present is set if it was a page protection issue (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 if the fault occurred on a write.
• user is set if the fault occurred in user mode.

To support stack growth, you should first expand the range of stack memory region so any address within [10 pages below USTACK_UPPERBOUND, USTACK_UPPERBOUND] is valid. Currently stack_setup

1. Allocates one page of physical memory (pmem_alloc)
2. Adds 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 the second argument, which will be the lowest address within the region.
3. Adds a page table entry mapping the virtual address of the stack’s page to the address of the newly allocated physical page (vpmap_map). Again this function takes the address of the start of a page, which will be the lowest address within the page.

You will want to modify step (2.) 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 (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 may be part of lab 5.

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. memset is defined in include/lib/string.h and implemented in lib/string.c.

For this part, the reference solution modified kernel/proc.c and kernel/pgfault.c.

Part 2: Create a user-level heap

After you have set up page fault handler to handle on-demand stack growth, you will now support dynamic heap growth. Heap growth differs in that a process has to explicitly request for more virtual address 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 sys_sbrk in syscall.c. The common use case is the situation where a user library routine, 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 heap 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). 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 system calls.

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. osv needs to track how much memory has been allocated to each process’s heap, and also extend/decrease size of heap based on the process’s request. To do so, you 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 fault from heap address 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, since an application cannot 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 is going to use 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, and kernel/pgfault.c.

Testing

After you implement the system calls described above, test your lab 4 code by either running individual tests in 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 the tests.

When debugging, I would recommend running individual tests in osv. 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 print statements before submission to Gradescope.

What to turn in

You will submit your work for this project via Gradescope.

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

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 submit your answers as many times as you like, you should not treat Gradescope as your only debugging tool. Many people may submit their projects near the deadline, and thus it will Gradescope take longer to process the requests. You may not get feedback in a timely manner to help you debug problems.

Grading

This lab will be graded out of 90 points, as shown in the table below. Comments explaining your approach can help earn partial credit if there are tests that don’t pass. Poor coding style can lose points, so make sure to submit clean, well-organized code.