Lab 4 Objectives
● Implementing a userspace swap library
Lab 4 Overview
● Swap / Paging: Extends memory by moving less-used pages to secondary storage, or moving pages back on-demand
Lab 4 Overview
1. Normally, kernels implement swaps
2. Programs can emulate swaps in user-space
Retries instruction i
Segmentation Fault
● [SIGSEGV]: On Linux and POSIX systems -> Segmentation fault when a process performs invalid memory access -> process terminated
● You can install a signal handler for SIGSEGV
● On Linux: return to instruction that caused invalid memory access and re-try the instruction
● Your handler can thus, swap memory in userspace
● Essentially, the handler is a page-fault handler
[Demo] Exercise 0 – Allocating Memory (1%)
Pointer to start of allocated memory
Controlled Memory Region
1. Implement userswap_alloc to allocate the requested memory size
a. Size rounded up to the next multiple of page size
b. Memory should initially be non-resident
c. Return pointer to start of memory
d. Keep track of size of memory allocation using data structure – for freeing later
e. Use mmap –
https://man7.org/linux/man-pages/man2/mmap.2.html
[Demo] Exercise 0 – Allocating Memory (1%)
2. Implement userswap_free to free entire memory allocation starting at a provided address
a. Use munmap – https://man7.org/linux/man-pages/man3/munmap.3p.html
[Demo] Exercise 0 – Allocating Memory (1%)
Signal Fault Handler
Make page resident
3. Implement the SIGSEGV signal handler that simply calls the page fault handler
a. Use sigaction – https://man7.org/linux/man-pages/man2/sigaction.2.html
4. Implement the page fault handler
a. Use mprotect to make the page resident
b. https://man7.org/linux/man-pages/man2/mprotect.2.html
Exercise 1 – Extending Handlers (1% / 2%)
SIGSEGV handler Check Location of Fault
Controlled Memory Region
Non-Controlled Memory Region
Remove itself as handler, reset action and return
Continue Handling Fault
Exercise 1 – Extending Handlers (1% / 2%)
Non-Resident Memory
Resident Memory
PROT_READ | PROT_WRITE
Resident Memory
1. Extend page fault handler to include additional data structures to keep track of page states
a. Consider there are multiple controlled memory regions
i. List of lists of pages
ii. 4-level page table
2. Extend userswap_free to clear up your data structures as well
Exercise 2 – Page Eviction (1%)
Non-Resident Page
Resident Page
Resident Page
Resident Page
Made Resident after eviction of previously resident page
Evicted based on eviction algo
1. Use data structures to keep track of resident pages -> who to evict first?
2. Extend username_free to clear your data structure
3. Implement userswap_set_size to set the LORM to a particular size
a. Size has to be a multiple of page size, or rounded up
Exercise 3 – Implement Swap (2%)
Resident Page
Page is dirty.
Write to Swap file
Resident Page
Brought back to memory
Non-Resident Page
Page not dirty.
PROT_NONE and madvise
Exercise 3 – Implement Swap (2%)
● Size of swap file cannot exceed total memory in controlled regions allocated
● Do not extend swap file if sufficient space from previous frees
● Name your swap file correctly
● Need data structures to help you keep track of where page was
evicted to
● Keep track also of locations that have been freed
1. Implement userswap_map
a. Same as userswap_alloc, except that region should contain
contents of file as offsets
2. Extend page fault handler so that upon read to non-resident page
allocated by userswap_map, page is filled with contents of the file at the
3. When evicting page allocated by userswap_map, just discard the page
without storing contents anywhere
Exercise 4 – Implement userswap_map (2%)
1. Extend page fault handler so that a page allocated by userswap_map and is dirty, when evicted, its contents are written to corresponding location in the backing file
2. If page not modified, it can just be discarded
3. Extend userswap_free so that dirty pages are written back to backing file
a. Do not close the file descriptor
Exercise 5 – Extend handlers (1%)
Exercise 6 (Bonus 2%)
● In ex1-5, you did not have to consider concurrent reads and writes to controlled memory regions
● For ex6, you need to consider this possibility, and implement a way to synchronise concurrent access of controlled memory regions
● Graded based on performance and quality
● Make sure your bonus can work for Ex 1-5 too
● Name your file bonus_userswap.c
● Include a bonus_userswap.txt file with a short description of your idea
Other things to take note
● Page size is 4096
● Make sure you still verify success/failure of every system call
● Implementation should not require way in excess of 128 bytes of
overhead per page of memory in single allocation
● Do not use mmap syscall to map file into memory to perform file I/O. Use
-1 for the fd argument
● Ensure reasonable performance (< 10 seconds)
Lab 4 Implementation Guide
● userswap.c - only modify this file!
● userswap.h
● workload_*.c - feel free to write additional cases
● Makefile - add the additional workloads to the Makefile