hw6 - Implement mmap() (Optional)

In this homework, we will explore a little bit about memory hierarchy (and the filesystem interface) by adding a widely used Unix feature to xv6: mmap().

While mmap can be (and is) used to allocate large chunks of memory, the more interesting use of mmap() is that of mapping a file into memory. This means you call mmap once, with a file descriptor as an argument, and the file immediately appears in virtual memory.

There are at least two main ways to do this. The first is eager: when mmap is called, have the kernel read the file as instructed, put it somewhere convenient in memory, and return a pointer to the location (Part 1).

The second is lazy: take note of the user's request, and return without doing anything further. When the user tries to access the memory, deal with the resulting page-fault, reading in only those pages that the user tries to read, when the user tries to read them (Part 2).

Getting Started

First, pull the latest code and switch to hw6.

git pull origin
git checkout hw6

A solution template is provided in the public class repository, under the name hw6.

The changes on top of the master branch can be seen using this link: https://github.com/sysec-uic/xv6-public/compare/master...hw6. (Select the tab "files changed" to see the differences.) Read the diff carefully for changes related to the homework.

The correct implementation will make three new programs -- eager, lazy, and bad -- print expected results.

Read the source code of the three programs to understand their expected behavior.

Part 1: Eager mmap() (5 pt)

sys_mmap()

The system call sys_mmap() has already been created for you, only it doesn't do much yet. The majority of the homework solution should go here, or in functions called by sys_mmap(). When you run the test programs eager and lazy, they crash with the current sys_mmap() implementation. This is expected.

Eager solution

In the eager solution, where the second argument of the mmap system call is 0, sys_mmap() allocates and maps all the memory needed for the file contents (see allocuvm() for an example of how to do this. allocuvm is only for the heap), and reads all of the file contents into the newly allocated memory. To read part of a file, you can use fileread() in file.c, or borrow some code from fileread() to directly call readi(). You only need the code that handles type == FD_INODE.

For both the eager and the lazy, you should map mmap() regions into addresses 0x400000000000 and above. You should expect there are multiple calls to mmap(). You should not overwrite or reuse any mmap areas that have been created by earlier calls. You’ll need to store some information inside struct proc. You need to add a few lines of code for the necessary initialization. See the TODO in proc.c.

A macro has been added to memlayout.h:

#define MMAPBASE 0x0000400000000000

To test your program, run the user program eager. It should show the output posted below.

$ eager
About to make first mmap. Next, you should see the first sentence from README
xv6 is a re-implementation of Dennis Ritchie's and Ken Thompson's Unix
Version 6 (v6)

Second mmap coming
xv6 @ UIC ROCKS!!!

Checking that first mmap is still ok, you should see the first sentence from README
xv6 is a re-implementation of Dennis Ritchie's and Ken Thompson's Unix
Version 6 (v6)
Exiting process. System free pages is 57003

Submission

Please follow instructions on Gradescope to submit your solution.

Notes on mmap()

  1. The very original motivation for the mmap system call is to map a file into the process's address space.
  • It's intuitive to use read/write system calls to transfer file contents: user <-> kernel <-> disk
  • mmap provides a clean interface and rich functionality.
  1. mmap() in Linux
  • On-demand file I/O handled transparently by the OS (through page-fault exception handler).
  • Sync a range of mapped files back to the disk -- you specify the memory address, and the kernel figures out where to write on the disk.
  • Allocating process memory without a backing file. It's also used for allocating "huge pages".
  1. Back to xv6:
  • eager mmap: allocate process memory and read file content into it -- page faults are not involved. In other words, everything should be done in the mmap system call.
  • lazy mmap: record the metadata for the process about which file is mapped to which address range. When the syscall returns, pages are still unallocated, and the first access to each virtual page will raise a page fault (traps.h: T_PGFLT). Using the metadata associated with the process, the page fault handler can allocate memory and load the corresponding file contents one page at a time.
  1. The context of the mmap system call (mmap/sys_mmap)
  • Current process (the per-code global variable proc)
  • An active file descriptor/struct file (the first syscall argument)
  • A flag (0/1) to choose eager or lazy mapping. (the second syscall argument)
  1. The procedure of eager mmap:
  • First, we need to know the size of the mapping, which should be equal to the file size. In hw6, we only consider regular files, which correspond to the "inode" with type FD_INODE.
  • Record/update the metadata for the process.
  • Allocate the memory for the user process. The xv6 kernel already provides a few functions for memory-related operations. See Hints below.
  • Read the entire file's data into the newly allocated memory. You may use either the kernel address or the user address. Make sure the addresses used are "really" valid when being accessed.
  1. More hints:
  • mappages() are already provided. Read the code first to see how it can help you.
  • kalloc() -- allocate physical pages
  • It's recommended to finish each file's mappings at an aligned address. For example, mmap of a 5KB file will occupy two pages from MMAPBASE to MMAPBASE + 8KB. The next mmap will start from MMAPBASE + 8KB, leaving an accessible but uninitialized gap between the two memory ranges. The PGROUNDUP macro in mmu.h can be helpful.
  • The CPU never checks the updates in the page table. We need to flush the TLB to force the CPU to use the up-to-date mappings. Reloading the page table root into the system register %cr3 does this. switchkvm() shows an example.
  • Read filewrite() and fileread() in file.c.

Part 2: Lazy mmap() (5 pt)

The 2nd part of this homework asks you to implement a lazy mmap(). You need to build on top of your hw6 (part 1) code, and later push your new code changes (with a new git commit) to the same GitHub remote repository.

The lazy solution works quite differently. When the lazy argument is 1, sys_mmap() should not allocate or map any memory, nor does it read anything from disk. Instead, it records the request in struct proc, and returns a pointer immediately. Initially, this pointer points to an unallocated and unmapped part of the virtual address space.

Later, when the process tries to read from or write to the memory area it just mmap()-ed, a page fault occurs. You need to implement the page fault handling code (handle_pagefault) that allocates the appropriate page to serve this read/write, and fills the page with the appropriate contents from the file. To figure out what address the program was trying to access, we just need to read the %CR2 register. The hook code is already provided for you in trap.c. See "case T_PGFLT:" for details.

To test your program, run the user program lazy. The hw6 template has a modification to exit(), which prints out the number of system free pages before exiting. The lazy solution should have about 17 more free pages than the eager solution. A sample of solution output is provided below.

$ lazy
About to make first mmap. Next, you should see the first sentence from README
xv6 is a re-implementation of Dennis Ritchie's and Ken Thompson's Unix
Version 6 (v6)

Second mmap coming
xv6 @ UIC ROCKS!!!

Checking that first mmap is still ok, you should see the first sentence from README
xv6 is a re-implementation of Dennis Ritchie's and Ken Thompson's Unix
Version 6 (v6)
Exiting process. System free pages is 57020

Submission

Please follow instructions on Gradescope to submit your solution.

More notes on mmap()

  1. The procedure of lazy mmap:
  • Only the first two steps in the eager mmap should be done in the syscall, as we are being LAZY!

  1. To make lazy mmap work correctly, we need to install the page fault handler in the kernel. The corresponding trap number is T_PGFLT, defined in traps.h. Check the added code in trap.c and think: what causes the execution to reach this place?

  2. When handling a page fault, the faulty address is stored in %cr2 by the CPU. The rcr2() function reads the %cr2 register.