Lab: Virtual Memory

Assigned:
Tuesday, Feb 6, 2018
Due:
Tuesday, Feb 13, 2018 by 10:30pm
Collaboration:
Work with your assigned partner for this lab. You can use online resources for your lab, provided they do not provide complete answers and you cite them in your code. If you do not know whether it is acceptable use a specific resource you can always ask me.

Overview

In this lab, you will implement two useful program features that are only possible with virtual memory. You’ll learn how Linux processes can manipulate their own address space using mmap and mremap, as well as how to use POSIX signals to run special signal-handling code in response to events. While many labs will be macOS-friendly, this particular lab will only work on Linux (at least for part B). You can find the starter code for this lab at https://github.com/csc213/virtual-memory.

Groups

Group information is no longer available for this course.

Questions & Answers

What happens to the original physical page of memory after both lazy copies have been written?
Our implementation will leak it. That’s okay.
Why doesn’t the sample code call alarm_handler? Where do the parameter values come from?
By calling sigaction, we’re asking the runtime library to call alarm_handler when we get the alarm signal. The runtime fills in these parameters for us.
When we compile our test code, the compiler says it does not have mremap
Add #define _GNU_SOURCE to the first line of your source file, before any includes.
When we return from a signal handler, where does the program pick up again?
It depends on the signal. Some, like timers, return somewhere near what the program was doing when the signal arrived. Others, like segfaults, pick up at the instruction that triggered the signal.
How do we know our program works?
Your code should pass all the tests in the starter code. Lazy copying should be much faster than eager copying, but writing to lazy copies should be slower than writing to eager copies.
Aren’t we doing a lot more copying?
Yes. We could get around this if we were writing an OS, and there are some ways to avoid it in your segfault handler, but it makes the bookkeeping more complex.

Part A: Friendly Segfaults

As you’ve likely noticed, segmentation faults can be quite annoying when you’re working on your programs. For this part of the lab, you will learn how to catch a segmentation fault with a signal handler and offer a more encouraging response to the user than simply “Segmentation Fault”. This part will require some new concepts, so please read the instructions carefully.

Signals

A segmentation fault is delivered to a running program as a signal. A signal is a POSIX standard feature that will interrupt the running program and switch to a designated signal handler. Signal handlers are just functions, although they have some special restrictions. When the signal handler returns, the program resumes where it left off.

Signals are encoded as integers. There are a couple dozen signals defined by default, each assigned a unique signal number. You can see a complete list of the available signals by running man 7 signal. There are two signals that cannot be caught or blocked, SIGKILL and SIGSTOP, but you can at least catch the rest. To introduce signals, we’ll focus on SIGALRM, which is represented by the number 14.

There are two important steps in using POSIX signals. First, we have to set up a signal handler. Second, we need to arrange for a signal to be delivered. For this quick example, we’ll use the sigaction function to set up a signal handler for SIGALRM, and then call alarm to have a signal delivered after a fixed time. The code below contains a complete sample program:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>
#include <unistd.h>

void alarm_handler(int signal, siginfo_t* info, void* ctx);

int main() {
  // Make a sigaction struct to hold our signal handler information
  struct sigaction sa;
  memset(&sa, 0, sizeof(struct sigaction));
  sa.sa_sigaction = alarm_handler;
  sa.sa_flags = SA_SIGINFO;
  
  // Set the signal handler, checking for errors
  if(sigaction(SIGALRM, &sa, NULL) != 0) {
    perror("sigaction failed");
    exit(2);
  } 
  
  // Set an alarm for 1 second
  alarm(1);
  
  // Loop forever
  for(;;){}
} 

void alarm_handler(int signal, siginfo_t* info, void* ctx) {
  // Print a message and set another alarm for one second
  printf("Tick\n");
  alarm(1);
}

We’ll discuss this code in detail in class.

Libraries

It’s often useful to place useful functions inside of libraries rather than copying them into each program where you’d like to use them. You may not have known it, but the POSIX functions you are calling in the labs and assignments for this course reside in libc, a library that is linked with your programs whenever you compile them with gcc or clang. For this part of the lab you’ll be writing your own library. Library code looks just like normal code, except you generally will not write a main function. Typically libraries have accompanying include files that declare (but do not implement) the functions contained in the library.

Here’s a simple C source file that we could compile as a library:

#include <stdio.h>

int add(int a, int b) {
  return a + b;
}

For this library to be useful we would have to add a corresponding .h file that declares our add function. As you’ll see in a moment, we won’t actually need a header file for our library because programs won’t actually interact with it directly. To compile this library, we build it with a slightly different command line:

$ clang -shared -fPIC -o libadder.so add.c

Now, if we want to use this library with another program we’re building we add the -l flag followed by the library name, dropping the “lib” part of the name from the beginning and the “.so” from the end.

$ clang -o myprogram myprogram.c -ladder

If adder.so isn’t in the current directory we can pass a path to its directory with the -L flag.

Library Constructors

The one last small trick you’ll need to know to complete this part of the lab is how to use library constructors. These are just functions, but you can declare them in a special way that tells your program to run them as the program starts up, before main. Here’s a library constructor function:

__attribute__((constructor)) void init() {
  printf("Starting up!\n");
}

Any program that uses a library with this constructor will print “Starting up!” shortly before running main.

Your Task

Your job is to write a library that you can link into a program that will replace the depressing “Segmentation Fault” message with a randomly-selected, encouraging segfault message. You can find the code to start your library in the partA directory of the starter code, and a subdirectory that has a simple test program that will trigger a segmentation fault. This program is configured to link in your helpful library, so you should be able to use make to build as usual. To run the program, make sure you are in the partA directory and run tester/tester.

To complete this part, you will need to set up a signal handler for segmentation faults in a library constructor. Your segmentation fault handler should randomly select one of at least eight different encouraging segfault messages, display it, and then exit the program. Make sure you seed the random number generator with srand before selecting a message or you will always receive the same “random” message.

The friendly faults library is compiled to a file named libetsbefriends.so, so to link it to an arbitrary program you would pass the flag -letsbefriends. You can also attach it to arbitrary programs without linking them. To do this, run the program with the LD_PRELOAD variable set to insert this library into the program, as this example shows:

$ LD_PRELOAD=/home/awesomestudent/virtual-memory/partA/libetsbefriends.so shell/mysh

We’ll use this trick again next week, but first we’ll spend a little time looking at how libraries work and discuss this particular trick in a bit more detail.

Part B: Lazy Copying

Now that you’ve used signals in connection with virtual memory, we’ll build something a bit more useful that takes advantage of virtual memory to speed up copying large blocks of data. Instead of copying data immediately, we’ll create copies by mapping two virtual pages to point to the same memory, but mark that memory as read-only. If the program modifies either copy in the future we will perform the actual copy, but copies that are only read will complete much faster.

We’ll discuss this approach, called copy-on-write, in class. At a high level, the idea is to use the mapping from virtual to physical addresses along with protection to avoid unnecessary copying. Say a program asks for a copy of a 4KB chunk of memory that is perfectly aligned to the beginning of a 4KB page. We could ask for a new 4KB chunk of memory and copy each byte over, but this could take some time. Instead, we’ll ask for a new page of virtual memory and point it at the same memory that holds the original values. This creates two mappings to the same memory, which means changing values in either copy will change both copies.

Our goal with this mechanism is to replicate the appearance of the original slow copying method, but with less work. Since these are supposed to be copies rather than mysteriously linked memory locations we’ll need to prevent writing. To do this, we can mark both copies read-only. Later, if the program tries to write to either copy we will get a segmentation fault. You can catch this segmentation fault with a signal handler. The signal handler will have to split the two connected copies so they no longer share physical memory, while retaining the original values in each copy. These new, split copies can now be made writable.

Requesting New Memory

To make things a bit more manageable, we’ll focus on copying only 64KB chunks of data rather than arbitrary data from inside the program. The starter code includes code to allocate these chunks using the mmap function. This function adds a new entry to the program’s virtual address space. It can do a few other things, but more on that later. You should review the mmap manpage and the starter code to see how mmap works.

Making a Shared Mapping

When the user of this system asks for a copy, we need to add a new virtual address range that shares physical memory with region we’re copying. To do this, we’ll (ab)use the mremap function. This function is meant to resize a virtual memory mapping, but it has a secret mode you can read about at its online manpage (but not on the man mremap page, apparently). Normally we specify the size of an existing virtual memory mapping in the old_size parameter. If we instead pass zero for this parameter mremap will create a new mapping but leave the old one intact, so the two will share the same physical memory.

Making a Mapping Read-Only

To make a virtual memory mapping read-only, we’ll use the mprotect function. This function takes a virtual address where we would like to change protections, the size of the region we’re changing protections for, and the new protection values. To make a region read-only, we’d call mprotect(region_start, region_size, PROT_READ). Making a region readable and writable is similar: mprotect(region_start, region_size, PROT_READ | PROT_WRITE). We’ll talk about OR-ing PROT_READ and PROT_WRITE together in class.

Finding the Address of a Segfault

When the program accesses one of your lazily-copied chunks, you’ll get a segmentation fault. This fault could be triggered by an access anywhere inside a chunk of memory, so you’ll need to do some bookkeeping to remember where chunks begin. You’ll also need to find the address that triggered the segmentation fault so you can find the appropriate chunk. To access this, use the info parameter inside your segfault handler function. The variable, of time siginfo_t*, contains quite a bit of information about what triggered a signal. The field si_addr holds the address that caused the fault.

You’ll need to look for a chunk you copied lazily that holds this pointer, but you can’t directly compare pointers with < and > in C. Instead, you’ll have to cast the pointer to an integer type. You have to make sure the integer is big enough to fit a pointer, but luckily there is a special type for this. The intptr_t type is defined in stdint.h, and is guaranteed to be the same size as a pointer on the current system. While you generally should not convert between pointers and integers, this is one case where it’s actually necessary. We’ll see more cases like this in next week’s lab.

Replacing a Mapping

When a program tries to write one of your lazily-copied chunks of data, you’ll have to split the two mappings apart. To do this, we can call mmap and force it to create a new mapping in place of the old “copy”. If we have a copy at address p of size CHUNK_SIZE, we could call mmap(p, CHUNK_SIZE, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED | MAP_FIXED, -1, 0) to connect some new memory up with the virtual address p. We’ll talk about all the options in class, but the MAP_FIXED flag is particularly important; this tells mmap to make a new mapping at a fixed virtual address. This is required because we can’t change where our copy is placed once we’ve handed the copy off to a program.

Requirements

Your task is to implement the lazy copying interface for large chunks of data. You should review the instructions in the starter code to see exactly how the interface should work. I’ve provided a fairly simple test program that will verify that your copying works as expected, as well as compare the runtime of eager (normal) copying to lazy copying.

There are a few general requirements you should consider as you plan your implementation:

  1. Accesses to lazily-copied memory should return the same values as you would see if you used eager copying.
  2. It must be possible to create lazy copies of many different chunks of data in one program.
  3. Lazy copying must use virtual memory to speed up copying large chunk of data that are only ever read. Chunks that are written may take longer when you factor in the copying that happens on the first write. This is fine.
  4. Accesses anywhere inside a lazily-copied chunk should trigger a copy, not just accesses to the beginning of the chunk.

You will need some sort of global bookkeeping structure to keep track of lazily-copied chunks in order to satisfy requirement 2. You are welcome to use simple but inefficient structures for this bookkeeping data, but do not hard-code an upper limit on the number of lazily-copied chunks of data.

There are a couple extra features you do not need to support, although you could implement them as an additional challenge:

  1. Writing to a lazily-copied chunk can trigger a copy, even if the other copy has already been split off from this one.
  2. You do not need to support multiple lazy copies of a single chunk.
  3. You do not need to support lazy copies of chunks that are themselves lazy copies.
  4. You do not need to support freeing chunks of memory, whether they are copies or not.