All homework submissions are to be made via Git. You must submit a detailed list of references as part of your homework submission indicating clearly what sources you referenced for each homework problem. You do not need to cite the course textbooks and instructional staff. All other sources must be cited. Please edit and include this file in the top-level directory of your homework submission in the main branch of your team repo. Be aware that commits pushed after the deadline will not be considered. Refer to the homework policy section on the class web site for further details.
Group programming problems are to be done in your assigned groups. The Git repository for your group has been setup already on Github. It can be cloned using:
git clone git@github.com:W4118/f23-hmwk5-teamN.git
All team members should make at least five commits to the team's Git repository. The point is to make incremental changes and use an iterative development cycle. Follow the Linux kernel coding style and check your commits with the checkpatch.pl (or provided run_checkpatch.sh) script on the default path in the provided VM. Errors from the script in your submission will cause a deduction of points.
For students on Arm Mac computers (e.g. with M1 or M2 CPU): if you want your submission to be built/tested for Arm, you must create and submit a file called .armpls in the top-level directory of your repo; feel free to use the following one-liner: cd "$(git rev-parse --show-toplevel)" && touch .armpls && git add .armpls && git commit -m "Arm pls" You should do this first so that this file is present in any code you submit for grading.
For all programming problems you should submit your source code as well as a single README file documenting your files and code for each part. Please do NOT submit kernel images. The README should explain any way in which your solution differs from what was assigned, and any assumptions you made. You are welcome to include a test run in your README showing how your system call works.It should also state explicitly how each group member contributed to the submission and how many hours each member spent on the homework. The README should be placed in the top level directory of the main branch of your team repo (on the same level as the linux/ and user/ directories).
A core feature of memory management in Linux (and most other operating systems) is the concept of virtual address spaces. To each process running in userspace, it appears as if it is the only process using the memory. It can allocate, read, write, and deallocate memory at any allowed ‘virtual’ address without worrying if some other process happens to be using that same address. However, in reality multiple virtual address spaces are coexisting in physical memory.
The Linux kernel is responsible for providing this abstraction to userspace processes; it keeps track of every virtual address for each running process, and maps those addresses to physical memory. However, storing an exact, one-to-one mapping from every virtual address of every process to a corresponding physical address is clearly impossible given physical memory limitations. Instead, the kernel uses some smart data structures (in combination with hardware support) to provide the virtual memory abstraction transparently to processes, while in reality storing only a tiny fraction of all possible mappings.
In this assignment, you will explore the two main data structures the kernel uses to do memory mapping: virtual memory areas and page tables.
Virtual memory areas (VMAs), also called memory regions, are how the kernel tracks the memory that a process thinks it has allocated, along with some associated state. They represent regions in the virtual address space, but are independent of physical pages in memory.
Page tables, on the other hand, map those virtual memory addresses to physical memory addresses once real memory is actually required. In addition to mappings, the page tables also include state information (like whether pages are read-only or dirty, for example).
In this assignment, you will see how VMAs and page tables are managed and updated by tracing these updates for a specified process. We will create system calls that allow an ‘inspector’ process to access a continuously updating ‘shadow’ page table describing a small segment of the virtual address space of some other target process.
For simplicity, our shadow page table will only have a single level, and will store information about both the real page tables and the virtual memory areas of the target process. Think of the shadow page table as a single-level map from a page in the virtual address space to a frame of physical memory.
First, set up the data structures for the shadow page table that you will provide to inspecting processes. Since both your internal kernel logic and the userspace processes that use your system call need to know how these are structured, you should place them in a uAPI header. Create the file include/uapi/linux/shadowpt.h, and add the following components:
/* The data structure representing a single entry in the page table */
struct shadow_pte {
unsigned long vaddr; /* Virtual address of the base of this page */
unsigned long pfn; /* Physical frame number of the assocated physical page */
unsigned long state_flags; /* Flags describing the mapping state */
};
#define SPTE_VADDR_ALLOCATED 1 /* the page is allocated */
#define SPTE_VADDR_ANONYMOUS 2 /* the page is for anonymous memory */
#define SPTE_VADDR_WRITEABLE 4 /* the page is writable (else read only) */
#define SPTE_PTE_MAPPED 8 /* a physical frame of memory is mapped */
#define SPTE_PTE_WRITEABLE 16 /* the frame of memory is writable */
/* Macros for testing whether each state flag is set */
#define is_vaddr_allocated(state) (state & SPTE_VADDR_ALLOCATED)
#define is_vaddr_anonymous(state) (state & SPTE_VADDR_ANONYMOUS)
#define is_vaddr_writeable(state) (state & SPTE_VADDR_WRITEABLE)
#define is_pte_mapped(state) (state & SPTE_PTE_MAPPED)
#define is_pte_writeable(state) (state & SPTE_PTE_WRITEABLE)
#define MAX_SPT_RANGE (8388608)
/* The data structure representing the full page table */
struct user_shadow_pt {
unsigned long start_vaddr; /* first virtual address in the target range */
unsigned long end_vaddr; /* last virtual address in the target range + 1 */
struct shadow_pte __user *entries; /* array of all page table entries */
};
As you write your code, you may find it helpful to add some helper functions or macros to this header file to more easily access information related to these structures. However, do not modify the provided data structures or add additional data structures to pass information between userspace and the kernel. The provided data structures make up the minimal and complete API for your system call; any additions you make should be for convenience only.
In addition to the UAPI header, you should create a separate include/linux/shadowpt.h header. Here, you’ll want to both include the UAPI header (with #include <uapi/linux/shadowpt.h>) and define any additional data structures, short helper functions, or prototypes that might need to be accessible from within the kernel, but shouldn’t be exposed to userspace. When you do this, make sure you have appropriate include guards in both header files.
Tasks:Next you will write the system call to create our shadow page table and make it available to the inspector process, but don’t worry about populating or destroying it yet.
The first system call (with syscall number 451), should have the following interface:
/*
* Syscall No. 451
* Set up the shadow page table in kernelspace,
* and remaps the memory for that pagetable into the indicated userspace range.
* target should be a process, not a thread.
*/
long shadowpt_enable(pid_t target, struct user_shadow_pt *dest);
An inspector process will call this system call with the pid of the process it would like to inspect and a user_shadow_pt struct. This struct should be populated to contain the target start and end addresses, and a linear, preallocated entries array.
In the system call function, the kernel should take these inputs, validate them, and build a corresponding shadow page table in kernel space. Once this has been done, your function should remap the pages storing the shadow page table into the inspector’s virtual memory, at the entries pointer provided in the user_shadow_pt struct. Once this is done, the entries pointer provided by the userspace process should map to the same physical memory as the shadow page table created by the kernel.
Input CheckingIf any of the provided arguments are invalid (for example, if the target process does not exist, or the start address is greater than the end address), your system call should return -EINVAL. In addition to basic sanity checking of the inputs, there are some additional limitations you should impose on callers:
Unlike in Homework 3, where you wrote to a ring buffer located in kernel space and later copied to userspace, we now want shadowpt_enable() to make the shadow page table directly accessible in the userspace process’s memory. Remember that writing directly to userspace memory wasn’t allowed; to safely share data with a caller, we needed to use the copy_to_user() function, which was (relatively) slow and could sleep.
To get around the problem of needing to repeatedly copy to userspace whenever an update is made to the page table, this time you should allocate pages in the kernel, then modify the inspector’s page tables to directly point to those pages in the kernel. In other words, you will end up with two references to the same set of physical pages: one in kernel memory, which you use to write, and one in userspace memory, which you use to read. This means that any updates to the shadow page tables in the kernel effectively happen instantly for the inspecting process as well.
Take a look at the remap_pfn_range() function to implement this remapping. It is well documented for use in kernel drivers, but it can also be used elsewhere. Look at how it is implemented and try to understand in broad terms how it works (this will be useful for the next parts of the assignment).
Notes:After successfully remapping a shadow page table placeholder, you now should now allow disabling of the shadow page tables, both intentionally and automatically when something goes wrong.
The system call to handle disabling should have syscall number 452, and should use the following prototype:
/*
* Syscall No. 452
* Release the shadow page table and clean up.
*/
long shadowpt_disable();
This system call attempts to disable and clean up a shadow page table. It should reset any global state set up by shadowpt_enable(), to allow new calls to shadowpt_enable() to succeed.
Only the exact process which successfully called shadowpt_enable() should be able to successfully disable its shadow page table.
Since you don’t want to leave the inspector process with access to kernel pages, you should ‘undo’ the remap_pfn_range() to disconnect the virtual addresses of the process from these physical pages. There are multiple ways to do this, but a good place to begin is by looking through the munmap() system call to see how it breaks down a regular mmap’d region. You may also find zap_vma_ptes() helpful.
Once the disable syscall is made, the entries range can either no longer be mapped (i.e. an access causes a segmentation fault in userspace) or can behave as if shadowpt_enable were never called, and the region was just mmap’d.
An important edge case you need to handle is if the inspector process exits before making the disabled system call, particularly since we only allow the inspector process itself to successfully make that call.
You should make sure that no matter how the inspector process exits, your kernel behaves as if the disable system call was made and cleans up properly.
Notes:Now that you can create and destroy the page table, the next step is to populate it with the correct values, both on initialization and then whenever those values change as described below. In particular, we suggest treating initialization similar to any other update to the shadow page table as the required functionality is similar. The difference is that initialization will require populating the entire shadow page table with the existing status of the VMAs and real page table by modifying your earlier implementation of shadowpt_enable() accordingly.
First, focus on correctly tracking changes to VMAs (both existence and state) within our target range. Then extend to tracking PTE states.
When the virtual address space representation (i.e. the VMA structs) is updated for an address (or some range of addresses) within the given range, you should update the shadow page table in kernel space for that address.
An example ‘hook’ function prototype might look something like this:
/*
* Update the shadow page table when virtual addresses in the given range is
* modified.
*
* This function should log properties (file-backed, anonymous, read-only,
* writeable) for virtual addresses.
*/
void update_shadow_vaddr(struct mm_struct *mm, struct vm_area_struct *vma);
You should track the following pieces of information about each page in the target range, and update its shadow_pte struct accordingly using the constant flag values we defined above:
There are a reasonably large number of edge cases that can cause an update to the VMA, so for our purposes you only need to place hooks in various places throughout the memory management code to track changes that happen for one of the following reasons:
Just like VMA structs, page table entries (PTEs) have some state flags associated with them, and can either be mapped or not. Your shadow page table should track the current state of PTEs in addition to VMA flags for particular pages.
Again, it makes sense to create some kind of update function that you can call to track changes. An example could look something like this:
/*
* Update the shadow page table when a physical page is updated
*/
void update_shadowpte(struct mm_struct *mm, unsigned long vaddr);
You should track the following pieces of information for each virtual page in the target range:
The key to this part is identifying where in the kernel a PTE is modified. Again there are a few edge cases you don’t need to handle, but you should track:
For simplicity, you do not need to track updates that involve huge pages, but your shadow page table should work correctly to track standard 4 KB pages even in the presence of huge pages.
Notes:With the previous system calls, you now should be able to inspect a target process and see its virtual to physical mappings for some range in userspace. To help test this functionality, you should implement one final system call with the following prototype:
/*
* Retrieve the contents of memory at a particular physical page
*/
long shadowpt_page_contents(unsigned long pfn, void __user *buffer);
This system call should take in a physical address and a userspace buffer. If the caller has superuser permissions, the shadow page table is active, and the provided pfn is currently mapped by a target process virtual address in the target range, then the system call should copy the contents of that page into the userspace buffer.
Notes:Write a user program that calls your system call and reports changes to the page table information. The program should be in the user/part4 directory of your team repo, and your Makefile should generate an executable named inspector. The program should be run as follows:
$ ./inspector <target_pid> <start_address> <end_address>
You should properly initialize your user_shadow_pt, which you will be passing as an argument to shadowpte_enable(), and allocate memory for the struct shadow_pte array. This memory is what will be eventually remapped in the syscall itself. Once you enable the page table, you should repeatedly print out the contents of your shadow page table once per second until the user terminates the program by pressing ctrl+c. Make sure you set up a signal handler so that the shadowpt_disable() system call is still properly called when you exit this way.
In addition, you should also write another program, which compiles to the executable target. This program will generate a variety of page table changes for you to observe with the inspector program. This program should update the contents of the page table by writing to and unmapping pages within its own virtual address space. You should be able to see the page table updating in the inspector as you perform these writes/unmaps.
Again, the only changes you need to generate are the ones you were asked to track above.
Notes:Write answers to the following questions in the user/part5.txt text file, following the provided template exactly. Make sure to include any references you use in your references.txt file, and that you are referencing the correct kernel version in bootlin (v6.1.11). For reference, the URLs you answer with should be in the following format: https://elixir.bootlin.com/linux/v6.1.11/source/kernel/sched/core.c#L6432
int main() {
int *ptr = NULL;
*ptr = 5;
}
Identify the kernel functions from those listed below that will get executed, and put them in the order in which they will be called. Start your trace at the time when the process begins executing the first instruction of main(), and end your trace when the process will no longer run anymore. Functions may be called multiple times. Not all functions need to be used. Also, not all functions that are executed are listed below – limit your answer to include only these functions. In your answer, you should write each function exactly how it appears below (no extra tabs, bullets, spaces, uppercase letters, etc.), with each function on a separate line. We will be grading your answers based on a diff – if you do not follow the formatting specifications, you will not receive credit.