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-hmwk2-teamN.git
(Replace teamN with the name of your team, e.g. team0).
This repository will be accessible to all members of your team, and all team members are expected to
commit (local) and push (update the server) changes / contributions to the repository equally. You
should become familiar with team-based shared repository Git commands such as
git-pull,
git-merge,
git-fetch.
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.
The kernel programming for this assignment will be run using your Linux VM. As a part of this assignment, you will be experimenting with Linux platforms and gaining familiarity with the development environment. Linux platforms can run on many different architectures, but the specific platforms we will be targeting are the X86_64 or Arm64 CPU families. All of your kernel builds will be done in the same Linux VM from homework 1. You will be developing with the Linux 6.1.11 kernel.
For this assignment, you will write a system call to dump the process tree and a user space program to use the system call.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 much time 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).
Build and run a custom kernel for your VM. The source code for the kernel you will use is located in the linux/ folder in the main branch of your team repo. You can checkout to that branch. Clone the main branch in a separate directory–the linux/ folder within this directory will be the root of your kernel tree.
Ensure you have the following dependencies before you begin:
build-essential bc python3 bison flex rsync
libelf-dev libssl-dev libncurses-dev dwarves
make olddefconfig
make menuconfig
sudo make modules_install && sudo make install
$ yes '' | make localmodconfig
Make sure
that CONFIG_BLK_DEV_LOOP
is still set to y
before building and installing this kernel.
Now you have a much
smaller .config.
You can
follow the rest of the steps starting from make (step 3).
Note that you only need to do
make localmodconfig once, not each time you
build the kernel.
sudo make install
assuming you have already done step 4 with the kernel
configuration you are using.
Just to reemphasize the earlier point, when you are hacking kernel code, the standard workflow will be to modify kernel code, then build the kernel and install the updated kernel using the following two steps:
make -j$(nproc)
sudo make install
Then reboot your VM and select your kernel
in grub. In other words,
no need to do step 2 or step 8 each time you build
your kernel; those steps only need to be done once.
The system call you write will retrieve information from each thread associated with each process in some subset of the process tree. That thread information will be stored in a buffer and copied to userspace.
Within the buffer, thread information should be sorted first in breadth-first-search (BFS) order of the process (main threads) within the process tree, and then between the (non-main) threads associated with each process, sorted in ascending order of pid. You may ignore PID rollover for the purposes of ordering threads. See ‘additional requirements’ for an example ordering.
The prototype for your system call will be:int ptree(struct tskinfo *buf, int *nr, int root_pid);
You should define struct tskinfo as:
struct tskinfo {
pid_t pid; /* process id */
pid_t tgid; /* thread group id */
pid_t parent_pid; /* process id of parent */
int level; /* level of this process in the subtree */
char comm[16]; /* name of program executed */
unsigned long userpc; /* pc/ip when task returns to user mode */
unsigned long kernelpc; /* pc/ip when task is run by schedule() */
};
in include/uapi/linux/tskinfo.h
as part of your solution. The uapi directory contains
the user space API of the kernel, which should include
structures used as arguments for system calls. As an example,
you may find it helpful to look at
how struct tms is defined and used in
the kernel, which is another structure that is part of the
user space API and is used for getting process times.
0
/ \
1,2 3,4,5
/ \ / \
6 7 8 9
and you are given a buffer of size 10 * sizeof(struct tskinfo), the buffer should be filled as follows (excluding program counters):
[
tskinfo {pid-0, tgid-0, ppid-0, level-0, … },
tskinfo {pid-1, tgid-1, ppid-0, level-1, … },
tskinfo {pid-2, tgid-1, ppid-0, level-1, … },
tskinfo {pid-3, tgid-3, ppid-0, level-1, … },
tskinfo {pid-4, tgid-3, ppid-0, level-1, … },
tskinfo {pid-5, tgid-3, ppid-0, level-1, … },
tskinfo {pid-6, tgid-6, ppid-1, level-2, … },
tskinfo {pid-7, tgid-7, ppid-2, level-2, … };
tskinfo {pid-8, tgid-8, ppid-4, level-2, … };
tskinfo {pid-9, tgid-9, ppid-4, level-2, … };
]
Note that in this example, there are 7 processes (0, 1, 3, 6, 7, 8, and 9) and 3 threads (2, 4, and 5). Also, 7 is a child of 2 not 1, and 8 and 9 are children of 4. In this scenario, commands like ps might differ from ours in output (see the hint below for an explanation).
rcu_read_lock();
do_some_work();
rcu_read_unlock();
If your code needs to do memory allocation or copying of
data into and out from the kernel, such code should be
before rcu_read_lock() or after
rcu_read_unlock().
Since you do not know the tree size in advance, you should start with some reasonable buffer size for calling ptree, then if the buffer size is not sufficient for storing the tree, repeatedly double the buffer size and call ptree until you have captured the full process tree requested. Print the contents of the buffer from index 0 to the end. For each process, you must use the following format for program output:
printf("%s,%d,%d,%d,%p,%p,%d\n", buf[i].comm, buf[i].pid, buf[i].tgid,
buf[i].parent_pid, (void *)buf[i].userpc, (void *)buf[i].kernelpc, buf[i].level);
$ ./test
swapper/0,0,0,0,(nil),0xffffffff8e7a4281,0
systemd,1,1,0,0x7f8321f27c46,0xffffffff8d7f8b52,1
kthreadd,2,2,0,(nil),0xffffffff8d7f8b52,1
systemd-journal,299,299,1,0x7f6de3927c46,0xffffffff8d7f8b52,2
…
vmware-vmblock-,322,322,1,0x7f30f6c1d4a6,0xffffffff8d7f8b52,2
vmware-vmblock-,324,322,1,0x7f30f6c801bd,0xffffffff8d7f8b52,2
vmware-vmblock-,325,322,1,0x7f30f6c801bd,0xffffffff8d7f8b52,2
…
test,1558,1558,950,0x7f90f7be8539,0xcc0,3
Write answers to the following questions in the user/part4.txt text file, following the provided template exactly. Make sure to include any references you use in your references.txt file.
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
Using the program you developed in part 3, write another program such that you can use the program from part 3 to output the following process tree:
5000,5001
/ \
5002 5003
| |
5004 5005
With foo running in another shell, the console output for running ./test 5000 should be:
$./test 5000
foo,5000,5000,1,x,y,0
foo,5001,5000,1,x,y,0
foo,5002,5002,5000,x,y,1
foo,5003,5003,5000,x,y,1
foo,5004,5004,5002,x,y,2
foo,5005,5005,5003,x,y,2
where x represents the userpc, and x represents the kernelpc. Any valid values of x and y are okay. Otherwise, all of the other fields shown in the output above should exactly match the strings and integers shown.
This program should be in the user/part5 directory of your team repo, and your Makefile should generate the foo executable. While we will be testing your code on a freshly booted system, you may find it helpful to change the maximum possible pid value to make it easier to test your program (this allows pid values to rollover more quickly). For example, using the following commands may be helpful: echo 10000 | sudo tee /proc/sys/kernel/pid_max
Hints
5000
/ \
5001 5002
| |
5003 5004