Tasks

Design Document

Download the design document template of project 3. Read through questions in the document for motivations, and fill it in afterwards.

Stack Growth

Hint

Following tasks are closely related to each other. You probably want to read through following tasks before designing and coding. A smart design could address multiple tasks at once.

Currently, a user stack is a single page at the top of the user virtual address space, and programs were limited to that much stack. It is your task to enable stack to grow its current size.

The first stack page need not be allocated lazily. You can allocate and initialize it with the command line arguments at load time, with no need to wait for it to be faulted in. But the following stack page need to be allocated lazily -- they shouldn't be allocated until a pagefault happens.

You should impose some absolute limit on stack size, as do most OSes. Some OSes make the limit user-adjustable, e.g. with the ulimit command on many Unix systems. On many GNU/Linux systems, the default limit is 8 MB.

Hint: Extract user program's stack pointer

To extend the stack lazily, you should devise a heuristic that attempts to distinguish stack accesses from other accesses. sp should point to the lowest currently allocated byte. You need to obtain the compare the current value of the user program's stack pointer and the fault address. Within a system call or a page fault generated by a user program, you can retrieve sp from the Frame struct, which records the values of general purpose registers when the trap happens. Read through the trap_entry_u function to see where the user's stack pointer is recorded when a user trap happens.

Note: Managing user program's memory with UserPool

  • As you may have noticed, the first stack page are allocated from UserPool. UserPool is a part of physical memory designed to be used by user programs. Each page in the data/code segment of a user program should comes from UserPool. UserPool::dealloc_pages is used to free a page in UserPool. Calling kfree to free a page allocated from UserPool will cause undefined behavior in UserPool and kalloc.
  • Currently, when a user program exits, it automatically frees every page allocated from UserPool. This is implemented in PageTable::destroy, where we call UserPool::dealloc_pages for every leaf, non-global page. (In Sv39 virtual memory schemes, global mappings exist in all address spaces (ref: RISC-V ISA Vol.2: Privileged Architecture). Tacos kernel exists in all address spaces, we use global maps to avoid flushing them in TLB in context switching. User pages should do not exist in all address spaces and we do not global maps it. Therefore, leaf and non-global implies user page mapping.)
  • Eanbling stack growth, as well as other functionality in this lab, requires you to allocate more pages for user programs. Make sure to allocate from UserPool, and find proper way to manage them! Valid implementations may modify UserPool, or have another data structure to manage the pages in UserPool.

Note: Page table management

  • Stack growth may require you to modify current program's page table. Some interfaces in src/mem/pagetable.rs may be very helpful.
  • Following tasks may require you to frequently modify page tables to map/unmap virtual address to physical address. Some additional interfaces is needed!
  • You should be very careful when you are modifying an active page table. You probably need to use fence to synchronize your change. You could use inline assembly to execute fence instruction, or re-activate the page table using the interface in src/mem/pagetable.rs.

Memory Map Syscalls

The file system is most commonly accessed with read and write system calls. A secondary interface is to "map" the file into virtual pages, using the mmap system call. The program can then use memory instructions directly on the file data. Following example uses mmap and munmap to print a file to the console:

#include "user.h"
void main (int argc, char *argv[]) 
{
  void *data = (void *) 0x10000000;     /* Address at which to map. */

  int fd = open (argv[1]);              /* Open file. */
  mapid_t map = mmap (fd, data);        /* Map file. */
  stat s; fstat(fd, &s);                /* Read file size */
  write (1, data, s.size);              /* Write file to console. */
  munmap (map);                         /* Unmap file (optional). */
}

Detailed syscall's functionality as described below.

mmap

mapid_t mmap (int fd, void *addr);

Mmap maps the file open as fd into the process's virtual address space. The entire file is mapped into consecutive virtual pages starting at addr.

If successful, this function returns a "mapping ID" that uniquely identifies the mapping within the process.

A call to mmap may fail in four cases. First, it should fail if the file open as fd has a length of zero bytes. Second, it must fail if addr is not page-aligned or if the range of pages mapped overlaps any existing set of mapped pages, including the stack or pages mapped at executable load time. Third, it must fail if addr is 0, because 0 is used to represent null pointers. Finally, file descriptors 0, 1 and 2, representing console input and output, are not mappable. On failure, it must return -1, which should not be a valid mapping id.

If the file's length is not a multiple of PGSIZE, then some bytes in the final mapped page "stick out" beyond the end of the file. Set these bytes to zero when the page is faulted in from the file system, and discard them when the page is written back to disk.

Your VM system must lazily load pages in mmap regions and use the mmaped file itself as backing store for the mapping. That is, evicting a page mapped by mmap writes it back to the file it was mapped from.

munmap

void munmap (mapid_t mapping);

munmap unmaps the mapping designated by mapping, which must be a mapping ID returned by a previous call to mmap by the same process that has not yet been unmapped. All mappings are implicitly unmapped when a process exits, whether via exit or by any other means.

When a mapping is unmapped, whether implicitly or explicitly, all pages written to by the process are written back to the file, and pages not written must not be. The pages are then removed from the process's list of virtual pages.

Closing or removing a file does not unmap any of its mappings. Once created, a mapping is valid until munmap is called or the process exits, following the Unix convention.

If two or more processes map the same file, there is no requirement that they see consistent data.

Note

Unix handles consistent by making the two mappings share the same physical page, but the mmap system call also has an argument allowing the client to specify whether the page is shared or private (i.e. copy-on-write).

Hint: Lazily load mmap region

To lazily load page in mmap regions, you need a table of file mappings to track which files are mapped into which pages. This is necessary to properly handle page faults in the mapped regions.

Segments Loading

Originally, Tacos's loader eagerlly loads a executable file's content in the memory (see src/userproc/load.rs for more details). You need to modify the loader such that it lazily load all those pages. That is, a page is loaded only as the kernel intercepts page faults for them.

Hint: Lazily load segments

  • To lazily load page segments, you should record metadata for each lazily-loaded page, which allows you to know what location to read its content from disk later.
  • In particular, originally (without lazily segments loading) if a page's content comes from reading offset X of the executable file, you should still read the content from offset X of the executable file during page fault handling.
  • Valid solution may need to modify load.rs, to record the metadata in the loading process, instead of allocating the pages all at once.

Swapping

Currently, when the work set of user programs exceeds the capacity of the main memory, Tacos will panic due to out of memory. However, if we temporarily swap out some less frequent used pages to secondary memory, such as disk, Tacos can support larger work set.

Note

By default, Tacos's UserPool contains 256 pages. (The value is defined in src/mem/palloc.rs, named USER_POOL_LIMIT). You shouldn't change this value. When those 256 pages are in use, new come allocate request will panic the kernel. You must find a way to either modify UserPool's implementation to avoid panic, or to prevent such requests.

To support swapping, a secondary memory is needed. A special file, named .glbswap, exists in the disk image. You should use it to expand physical memory. See the helper functions in src/disk/swap.rs. To manage the swap space, you need to record which regions in the swap space is free, which regions is in use, and design interfaces that allows other modules to allocate and free slots in the swap space.

Hint: Swap space manager

Implement the swap space manager to support those functionalities.

A swap may happen when a new user page is needed (e.g. when a page fault from user happens), and there is no more free pages in UserPool. Swap usually contains several steps:

  1. Choose a victim page: You should select a victim page based on a global page replacement algorithm. In this lab, we requires you to implement a approximate LRU algorithm, such as "second chance" or "clock" algorithm.
  2. Swap out the victim page: After a victim page is selected, you should decide the swap-out strategy. To avoid unnecessary I/Os, you should not write unmodified pages to the swap space, because they value can be read directly from the executable file. Those pages modified since load (e.g. as indicated by the "dirty bit") should be written to swap. Your swap space manager should be able to serve the allocate request, as well as necessary disk I/Os. Just as segments loading, where you record the lazily load pages, you need to record the pages that are in the swap space.
  3. Swap in the desired page: Desired pages may sit in executable files, or swap space. Use you recorded information to read them from disk.

Hint: Do not implement everything all at once

It is a complex task, you should implement it step by step. First implement a naive replacement policy, debug on it to make sure your swap out & swap in works well, and then move to the replacement policy.

Hint: Supplementary page table and frame table

  • As you may have noticed, both the swapping task and the segments loading task require keeping track of relationship between virtual memory address and their actual store locations (in RAM, in swap space, or in executable files). The datastructure that records this relationship are called supplementary page table. Each user program should have a supplementary page table.
  • To choose a victim page, you probably want to know some additional information about a physical page (e.g. is it a dirty page? is it accessed?). Such additional information could be recorded in a data structure called frame table (Here the frame refers to a physical page). Design a global frame table and implement your page replacement on it.
  • Data structures provided by alloc crate may be very helpful when implementing those tables and managers!

Access user memory

After enabling swapping and lazily loading, accessing memory become more challenging: user is likely to pass addresses that refer to such non-present pages to system calls! If kernel code accesses such non-present user pages, a page fault will result. This means when accessing user memory, your kernel must either be prepared to handle such page faults, or it must prevent them from occurring.

Hint: Access user memory

  • To prevent such page faults from happening, you could extend your frame table to record when a page contained in a frame must not be evicted. (This is also referred to as "pinning" or "locking" the page in its frame.)
  • To be able to handle such page faults, you must prevent page faults when it is holding resources it needs to handle these faults, such as locks. Otherwise deadlocks or other concurrent problems may happen.