CS2106: Introduction to Operating Systems
Lab Assignment 4: User space Swap
The deadline of submission through LumiNUS: Fri, 12 Nov, 2pm. The total weightage is 8% + [Bonus 2%]:
• Exercise 0: Optional 1% demo
• Exercise 1: 1% if Ex0 is demoed, else 2%
• Exercise 2: 1%
• Exercise 3: 2%
• Exercise 4: 2%
• Exercise 5: 1%
• Exercise 6: 2% bonus
You must ensure the exercises work properly on the SoC Compute Cluster, hostnames: xcne0 – xcne7, Ubuntu 20.04, x86_64, GCC 9.3.0.
1. Introduction
As you know from the lectures, swap, or paging, is a way of “extending” the memory capacity of a computer by moving less-used pages to secondary storage, thereby making room for new pages, and moving pages back into main memory on-demand.
Although swap is typically implemented and provided by a kernel transparently to user programs, some operating systems provide features that allow programs to emulate swap in a similarly transparent fashion as well.
On Linux and other POSIX systems, when a process performs an invalid memory access, the kernel sends the SIGSEGV signal to the process. The default action for the signal is to terminate the process, and, in most cases, this is the only sensible thing to do: an invalid memory access usually implies a severe bug in the program or that memory corruption has occurred.
However, it is also possible to install a signal handler for SIGSEGV. While the C and POSIX specifications both state that the behaviour upon returning from a SIGSEGV signal handler is undefined, the behaviour on Linux is clear: it will return to the instruction that caused the invalid memory access and re-try the instruction. This means that by installing a SIGSEGV handler and performing actions to move memory, etc., it is possible to implement swap in user space. In effect, our SIGSEGV handler is acting as a page fault handler.
AY21/22 S1 A4 CS2106
In this lab, you will implement a user space swap library, as will be further described below.
Frequently asked questions
Frequently asked questions by students for this assignment will be answered here. The most recent questions will be added at the top; questions will be dated. Check this file before asking questions. If you have questions regarding the assignment, please ask on the LumiNUS forum created for this assignment.
Reminder for Windows, macOS, and other non-Linux POSIX OS users
This lab uses Linux-specific behaviours, including the ability to return normally from a SIGSEGV handler and certain syscall arguments and operations. Your program may compile successfully on macOS or other POSIX OSes, but is unlikely to behave correctly.
If you are on Windows, the lab should work fine in WSL 2 (given that WSL 2 is just Linux), but it may not work in WSL 1.
Regardless, you are strongly encouraged to test your implementation on the SoC Compute Cluster xcne nodes, as that is where grading will be performed.
AY21/22 S1 A4 CS2106
2. Overall specifications
The overall specifications for the library are as follows. If you are up for a challenge, you may implement the lab solely based on these specifications; otherwise, they are broken down into exercises below. In either case, please read the specification carefully, as it defines key terms that will be used in the rest of the document.
Controlled memory regions
A controlled memory region is a memory region controlled by the user space swap library.
In the rest of the document, we use page fault to denote when a memory access to a controlled memory region causes a SIGSEGV. Note that this is independent of whether the memory access causes an actual page fault in the kernel.
A page of memory in a controlled memory region has these properties:
• Residency: A non-resident page is not present in memory, and accessing it will cause a page fault. A resident page is present in memory, and must not cause a page fault on access.
• Contents: Each page of memory has some contents. These contents are independent of the residency of the page, and must be preserved when a page is evicted and then brought back into memory.
• Dirtiness: A page is dirty if it has been written to since the last time the page was made resident; otherwise, the page is clean.
A controlled memory region is allocated as private anonymous pages using mmap. The pages should initially be in the non-resident state. If the memory region is allocated using userswap_alloc, then the pages’ contents are initialised to zero. If the region is allocated using userswap_map, they should contain the contents of the backing file at the corresponding locations.
Upon a page fault accessing a non-resident page, the page should be brought into memory and thereby made resident. If doing so will cause the total size of resident memory in all controlled memory regions to exceed the LORM (Limit Of Resident Memory, defined in a section below), then before the new page is brought into memory, the minimum number of pages should be evicted according to the page eviction algorithm until the total size after the new page is brought in will be under or equal to the LORM.
If a dirty page in an allocation by userswap_alloc is evicted from memory, the contents should be saved in a swap file. Each process should have at most one swap file regardless of the number of allocations made. The swap file should be named
AY21/22 S1 A4 CS2106
are freed, but the swap file must not be extended if there is sufficient space already, e.g., due to previous allocations that have since been freed. Your implementation should be able to deal with an existing swap file; it is sufficient to just truncate or delete the existing file.
If a dirty page in an allocation by userswap_map is evicted from memory, its contents should be updated in the backing file in the corresponding location.
If a clean page is evicted from memory, no file writes should be done due to that eviction. This is because if the page is already in a swap file or a backing file and it is clean, its contents in the file should be identical to that in memory. Hence no writes are needed. Note that a page that was allocated by userswap_alloc and that is read from but never written to, and therefore containing all zeroes, is considered a clean page.
When a page is evicted from memory, the kernel must be advised to actually free the backing physical pages by using madvise with MADV_DONTNEED; see the man pages for madvise.
SIGSEGV handler
The signal handler should check if the faulting memory access is to a controlled memory region. If so, the fault should be handled as described above. If not, it should remove itself as a SIGSEGV signal handler, reset the action taken for a SIGSEGV signal, and return immediately, in order to allow the program to crash as it would without the user space swap library.
Page eviction algorithm
A first-in-first-out eviction algorithm should be used. That is, when a page is to be evicted, the page that was least recently made resident should be chosen for eviction. This applies across all controlled memory regions i.e., this is a global replacement algorithm.
Limit of resident memory in all controlled memory regions (LORM)
This is a global setting that can be controlled by userswap_set_size. The limit applies to all controlled memory regions in total, not per-region. The default value of the LORM should be 8,626,176 bytes (that is, 2,106 pages :-)), i.e., this is the value of the LORM prior to any calls to userswap_set_size.
AY21/22 S1 A4 CS2106
Function specifications
• void *userswap_alloc(size_t size);
This function should allocate size bytes of memory that is controlled by the swap scheme described above in the “Controlled memory regions” section, and return a pointer to the start of the memory.
If size is not a multiple of the page size, size should be rounded up to the next multiple of the page size.
This function may be called multiple times without any intervening userswap_free, i.e., there may be multiple memory allocations active at any given time.
If the SIGSEGV handler has not yet been installed when this function is called, then this function should do so.
• void *userswap_map(int fd, size_t size);
This function should map the first size bytes of the file open in the file descriptor fd, using the swap scheme described above in the “Controlled memory regions” section.
If size is not a multiple of the page size, size should be rounded up to the next multiple of the page size.
The file shall be known as the backing file. fd can be assumed to be a valid file descriptor opened in read-write mode using the open syscall, but no assumptions should be made as to the current offset of the file descriptor. The file descriptor, once handed to userswap_map, can be assumed to be fully controlled by your library, i.e., no other code will perform operations using the file descriptor.
If the file is shorter than size bytes, then this function should also cause the file to be zero-filled to size bytes.
Like userswap_alloc, this function may be called multiple times without any intervening userswap_free, i.e., there may be multiple memory allocations active at any given time.
If the SIGSEGV handler has not yet been installed when this function is called, then this function should do so.
• void userswap_free(void *mem);
This function should free the block of memory starting from mem.
AY21/22 S1 A4 CS2106
AY21/22 S1 A4 CS2106 mem can be assumed to be a pointer previously returned by userswap_alloc
or userswap_map, and that has not been previously freed.
If the memory region was allocated by userswap_map, then any changes made to the memory region must be written to the file accordingly. The file descriptor should not be closed.
• void userswap_set_size(size_t size); This function sets the LORM to size.
If size is not a multiple of the page size, size should be rounded up to the next multiple of the page size.
If the total size of resident memory in all controlled regions is above the new LORM, then the minimum number of pages should be evicted according to the page eviction algorithm until the total size is under or equal to the LORM.
Assumptions
You may assume that:
• The size of a page is 4096. You may, but are not required to, ignore the high 16 bits of virtual addresses when designing your data structures.
• All arguments passed to the userswap functions are valid.
• All system calls made with valid arguments succeed. Despite this, you should
still check the success of every system call, and emit some warning, as they may fail during development due to programmer error, e.g., providing wrong arguments. Omitting error-checking may lead to difficult-to-debug issues.
• There will be no concurrent accesses to controlled memory regions. (Relaxed in the bonus exercise.)
• There will be no attempts to execute memory in a controlled memory region.
• No other code will alter the memory protection of controlled memory regions
using mprotect, or perform operations on those regions using madvise, etc. Limitations
• Your implementation should have no more than about 128 bytes of overhead (i.e., used for metadata tracking the state of each page) per page of memory in a single allocation. It is okay to exceed this limit for small allocations below 512 pages. This requirement will not be strictly checked, but egregious cases may be penalised.
• You must not use the mmap syscall to map a file into memory to perform file I/O. That is, when you use mmap, the fd argument must always be -1, even for userswap_map.
• Your implementation should work with reasonable performance. We will not be grading based on performance (except for the bonus), but all provided test workloads should still run within reasonable time (i.e., less than 10 seconds).
3. Implementation guide
Please read the overall specifications before reading this section. Each successive exercise builds upon previous exercises; when you complete all exercises, you will have fulfilled the specifications above.
In the lab archive, you will find these files:
• userswap.c: A skeleton for you to start from. You should implement everything in this file.
• userswap.h: Prewritten header; defines function prototypes.
• Makefile: .
• workload_*.c: Provided workloads to test your library, as described above.
You should modify only userswap.c. If you write additional workloads for your own testing, you may wish to add them to the Makefile for your convenience.
Compiling, running and testing
To compile the workloads with your library, simply type make. The -Werror flag is set. You may remove it while developing, but you are strongly advised to fix all warnings before submitting, as warnings are indicative of undefined behaviour. When grading, we will do so without -Werror, but all other flags will be kept as-is.
In each exercise below, workloads are suggested to test the functionality in that exercise. All workloads are self-contained and require no input, so you can simply run the workload and inspect the output/result. Note that the suggested workloads are in no way exhaustive tests; passing them does not guarantee full credit.
• workload_readonly: This workload simply allocates an array and then reads each element of the array as an integer, sums all the elements, and then prints the sum.
• workload_wraddr: This workload simply allocates an array of pointers, and then writes the address of the array element to each element itself. It then goes back to read each element of the array, verifying each element as it reads. No output is printed if it succeeds.
• workload_rdfile: This workload creates a file with some data, and then maps the file and verifies that the contents of the mapping are identical to those of the file.
• workload_wrfile: This workload does the same as workload_rdfile, then it writes to the mapping, frees the mapping and then verifies that the file contents are updated.
A tip for debugging: GDB by default breaks on SIGSEGV even though there is a signal handler for it. To disable this, use the GDB command handle SIGSEGV nostop. You can also make GDB not print on each SIGSEGV by handle SIGSEGV noprint.
AY21/22 S1 A4 CS2106
3.1. Exercise 0 [Optional 1% demo]
To get started, in this exercise, you will simply get to a base upon which you can build the rest of the library.
1. Implement userswap_alloc to simply allocate the requested amount of memory (rounded up as needed; see the specifications) using mmap. Per the specifications, the memory should be initially non-resident and therefore should be allocated as PROT_NONE, in order for any accesses to the memory to cause a page fault. userswap_alloc should also install the SIGSEGV handler, if it has not already been done.
2. Implement userswap_free, which should free the entire allocation starting at the provided address using munmap.
o You will need to track the size of each allocation in userswap_alloc. A simple linked list of allocations, storing the start address (from mmap) and the size, will be sufficient, but you are free to design and use more performant structures.
3. WriteaSIGSEGVhandler.Forthisexercise,thehandlerdoesnotneedtocheck whether the faulting memory address is within a controlled memory region; it can simply call the page fault handler. The page fault handler will need the address to perform mprotect, however; the faulting memory address can be found in the siginfo_t struct passed to the signal handler.
4. Writeafunctiontohandlepagefaults.Thisiswherethebulkofthelogicforthe “Controlled memory regions” will reside. For this exercise, the page fault handler only needs to use mprotect to make the page containing the accessed memory PROT_READ, thereby making the page resident.
o Note that the specifications say that memory newly allocated by userswap_alloc should be initialised to zero. Nothing needs to be done for this, as memory allocated by mmap is always initialised to zero.
Suggested test workloads: workload_readonly Syscall hints: mmap, mprotect, munmap, sigaction
AY21/22 S1 A4 CS2106
3.2. Exercise 1 [1% if Ex0 is demoed, else 2%]
In this exercise, you will implement more of the basic functionality of the library, stopping short of page eviction.
1. Extend the SIGSEGV handler to verify that the faulting memory address is actually in a controlled memory region, and if not, it should reset the action for the SIGSEGV signal and return. This completes the functionality for the SIGSEGV handler.
2. Extendthepagefaulthandlersothat,uponawrite,theaccessedpageismade PROT_READ | PROT_WRITE. In the case where non-resident memory is written to, it is acceptable to take two page faults, where the first makes the page PROT_READ, and the second makes the page PROT_READ | PROT_WRITE. To do this, you will need to track the state of each page; if a page fault happens on a resident page, the only possibility (given the assumptions) is that a write was attempted on a PROT_READ page.
o Pages are only made PROT_WRITE on the second fault so that it is possible to tell which pages are dirty, which will be needed for later exercises.
o It is also possible to directly figure out if a SIGSEGV was caused by a read or write, but this is not required.
3. Extenduserswap_freesothatitcleansupthedatastructurescorresponding to the allocation as well.
Here, you will need to design data structures to track the state of pages. You are free to design them as you wish. Remember that there can be multiple controlled memory regions. Keep in mind the overall requirements (i.e., the requirements of subsequent exercises) when designing these data structures. Also take note of the limit on memory overhead as mentioned above, although it is unlikely that you will hit the limit unintentionally.
Note that the data structures you create for this lab will be slightly different from those used by an OS in that they do not map logical or virtual addresses to physical addresses; they just store the state of pages.
Here are some suggestions for data structures:
• A 4-level page table, mirroring the structure used by x86_64. (The assumption above that allows you to ignore the high 16 bits of virtual addresses is relevant for this structure.) This has constant-time lookup and update once every level of page table is initialised for a particular address.
• Some kind of list of allocations that contains a list of pages in each allocation. The lookup and update performance will depend on how the list of allocations is designed.
Suggested test workloads: workload_wraddr Syscall hints: No new syscalls needed.
AY21/22 S1 A4 CS2106
3.3. Exercise 2 [1%]
In this exercise, you will implement page eviction, but without swap.
1. Extend the page fault handler so that, if the LORM will be exceeded when making a page resident, a page should be evicted according to the page eviction algorithm before the new page is made resident. In this exercise, it will be sufficient to make the page PROT_NONE, without performing madvise(MADV_DONTNEED); therefore, a swap file is not needed in this exercise.
2. Implementtheuserswap_set_sizefunction.
You will likely need an additional data structure for the page eviction algorithm. Some form of queue of resident pages, such as a doubly linked list or dynamic array will work well here. Remember to extend userswap_free so that it updates that data structure as well when an allocation is freed.
Suggested test workloads: workload_wraddr Syscall hints: No new syscalls needed.
AY21/22 S1 A4 CS2106
3.4. Exercise 3 [2%]
In this exercise, you will implement swap. Extend the page fault handler so that: