# Your Tasks

## Task 0: Design Document

* Download the [project 3b design document template](https://github.com/PKU-OS/pintos/blob/master/docs/p3b.md). Read through it to motivate your design and fill it in after you finish the project.
* We recommend that you read the design document template before you start working on the project.
* See section [Project Documentation](../../appendix/project-documentation), for a sample design document that goes along with a fictitious project.

{% hint style="success" %}
<mark style="color:green;">**Here are all the tests you need to pass to get a full score in Lab3b.**</mark>

1. <mark style="color:green;">**All tests in**</mark> `tests/userprog`
2. <mark style="color:green;">**All tests in**</mark> `tests/filesys/base`
3. <mark style="color:green;">**Part of the tests in**</mark> `tests/vm`
   * page-merge-mm
   * page-merge-stk
   * pt-grow-stack
   * pt-grow-stk-sc
   * pt-big-stk-obj
   * pt-grow-pusha
   * mmap-read
   * mmap-write
   * mmap-shuffle
   * mmap-twice
   * mmap-unmap
   * mmap-exit
   * mmap-clean
   * mmap-close
   * mmap-remove
   * mmap-bad-fd
   * mmap-inherit
   * mmap-null
   * mmap-zero
   * mmap-misalign
   * mmap-over-code
   * mmap-over-data
   * mmap-over-stk
   * mmap-overlap
{% endhint %}

## Task 1: Stack Growth

### **Exercise 1.1**

{% hint style="success" %}
<mark style="color:green;">**Exercise 1.1**</mark>

<mark style="color:green;">**Implement stack growth.**</mark>

* <mark style="color:green;">In project 2, the stack was</mark> <mark style="color:green;">**a single page**</mark> <mark style="color:green;">at the top of the user virtual address space, and programs were limited to that much stack.</mark>
* <mark style="color:green;">Now,</mark> <mark style="color:green;">**if the stack grows past its current size, allocate additional pages as necessary**</mark><mark style="color:green;">.</mark>
{% endhint %}

**Allocate additional pages only if they "appear" to be stack accesses.** Devise a heuristic that attempts to distinguish stack accesses from other accesses.

#### Some Important Notes

* User programs are buggy if they write to the stack below the stack pointer, because typical real OSes may interrupt a process at any time to deliver a "signal," which pushes data on the stack. However, **the 80x86 `PUSH` instruction checks access permissions before it adjusts the stack pointer**, so it may cause a page fault 4 bytes below the stack pointer. (Otherwise, `PUSH` would not be restartable in a straightforward fashion.) Similarly, the `PUSHA` instruction pushes 32 bytes at once, so it can fault 32 bytes below the stack pointer.
* **You will need to be able to obtain the current value of the user program's stack pointer.** **Within a system call or a page fault generated by a user program, you can retrieve it from the `esp` member of the `struct intr_frame` passed to `syscall_handler()` or `page_fault()`, respectively.**
  * If you **verify user pointers before accessing them** (see section 3 [Accessing User Memory](../../lab2-user-programs/your-tasks#task-3-accessing-user-memory) in project 2), these are the only cases you need to handle.
  * On the other hand, if you **depend on page faults to detect invalid memory access**, you will need to handle another case, where **a page fault occurs in the kernel**. Since the processor only saves the stack pointer when an exception causes a switch from user to kernel mode, reading `esp` out of the `struct intr_frame` passed to `page_fault()` would yield an undefined value, not the user stack pointer. **You will need to arrange another way, such as saving `esp` into `struct thread` on the initial transition from user to kernel mode.**
* **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.
* **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.
* **All stack pages should be candidates for eviction.** An evicted stack page should be written **to swap**.

## Task 2: Memory Mapped Files

### **Exercise 2.1**

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

* Suppose file foo is 0x1000 bytes (4 kB, or one page) long. If foo is mapped into memory starting at address 0x5000, then any memory accesses to locations 0x5000...0x5fff will access the corresponding bytes of foo.

**Here's a program that uses `mmap` to print a file to the console.**

* It opens the file specified on the command line.
* Then it maps the file at virtual address 0x10000000.
* Finally, it writes the mapped data to the console (fd 1), and unmaps the file.

```cpp
#include <stdio.h>
#include <syscall.h>
int main (int argc UNUSED, 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. */
  write (1, data, filesize (fd));       /* Write file to console. */
  munmap (map);                         /* Unmap file (optional). */
  return 0;
}
```

A similar program with full error handling is included as `mcat.c` in the examples directory, which also contains `mcp.c` as a second example of `mmap`.

<mark style="color:red;">**Your submission must be able to track what memory is used by memory mapped files.**</mark> <mark style="color:red;">**You need a table of file mappings to track which files are mapped into which pages.**</mark> This is necessary to properly handle page faults in the mapped regions and to ensure that mapped files do not overlap any other segments within the process.

{% hint style="success" %}
<mark style="color:green;">**Exercise 2.1**</mark>

<mark style="color:green;">**Implement memory mapped files**</mark><mark style="color:green;">, including the following system calls.</mark>

* <mark style="color:green;">mapid\_t</mark> <mark style="color:green;">**mmap**</mark> <mark style="color:green;">(int fd, void \*addr)</mark>
* <mark style="color:green;">void</mark> <mark style="color:green;">**munmap**</mark> <mark style="color:green;">(mapid\_t mapping)</mark>
{% endhint %}

* <mark style="color:blue;">**System Call: mapid\_t mmap (int fd, void \*addr)**</mark>
  * **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.
  * **Your VM system must lazily load pages in `mmap` regions and use the `mmap`ed 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**.
  * 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.
  * If successful, this function **returns a "mapping ID"** that uniquely identifies the mapping within the process. On failure, it must return **-1**, which otherwise should not be a valid mapping id, and **the process's mappings must be unchanged**.
  * **A call to `mmap` may fail if the file open as fd has a length of zero bytes.**
  * **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.
  * **It must also fail if addr is 0**, because some Pintos code assumes virtual page 0 is not mapped.
  * Finally, **file descriptors 0 and 1, representing console input and output, are not mappable.**
* <mark style="color:blue;">**System Call: void munmap (mapid\_t mapping)**</mark>
  * **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. See [Removing an Open File](../../lab2-user-programs/background#using-the-file-system), for more information. **You should use the `file_reopen` function to obtain a separate and independent reference to the file for each of its mappings.**
  * <mark style="color:red;">**If two or more processes map the same file, there is no requirement that they see consistent data.**</mark> Unix handles this 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).
