linux-list

Linux Linked List

How to submit

To obtain the skeleton files that we have provided for you, you need to download the lab tarball, hw1.tgz, from Courseworks, under the Files tab. Inside your VM, you may unpack it with the following command:

$ tar xzf hw1.tgz

This will unpack into a directory named hw1, which is a git repo.

The TAs will use scripts to download, extract, build and display your code. It is essential that you DO NOT change the names of the skeleton files provided to you. If you deviate from the requirements, the grading scripts will fail and you will not receive credit for your work.

You need to have at least 5 git commits total, but we encourage you to have many more. All your work should be committed to the master branch. If you have not used git before, this tutorial can get you started.

At a minimum, your README.txt should contain the following info:

The description should indicate whether your solution for the part is working or not. You may also want to include anything else you would like to communicate to the TA grader, such as extra functionality you implemented or how you tried to fix your non-working code.

Answers to written questions must be added to the skeleton file provided.

Once you have completed the assignment, you must create a tarball of your work. Everything should still be in a directory named hw1/. Create the tarball with the following:

$ tar czf hw1-<UNI>.tgz hw1

where <UNI> is replaced with your UNI. Upload hw1-<UNI>.tgz to Courseworks to submit your assignment.

Part 1: Reading and written assignment

(a) OSTEP book

Please read the following two chapters from OSTEP:

Then answer the following questions:

  1. What actions does a kernel perform to context switch between processes?

  2. What process state does a process enter immediately after it terminates? What is this state for, and when does it leave this state?

(b) LKD book

Read chapter 6 of LKD (pp.85-96) on Linux’s linked list implementation.

If the LKD book’s explanation left you still confused, you can take a look at another book, Understanding the Linux Kernel, 3rd Edition, by Bovet & Cesati, (pp.87-90) for another explanation.

Read the container_of() macro code shown in LKD, page 89 carefully. Answer the following questions:

  1. What is typeof? Is it C language keyword, function, or macro? What does it do?

  2. What is offsetof? Is it keyword, function, or macro? What does it do?

  3. What does the container_of() macro do?

  4. The container_of() macro, in the way it’s currently written, is not portable across C compilers because it uses GNU-specific language extensions. Can you identify what they are?

  5. The container_of() macro has two lines. Is the 1st line (the declaration of __mptr) really necessary? Is it possible to rewrite the macro without it? What is the purpose of that 1st line?

The answers to all these questions can be found by Googling, which you are allowed to do in this case. However, I urge you to make a serious attempt to answer these questions on your own. The point of this exercise is to get you ready for the kind of crazy C code you will encounter in the Linux kernel. Take this opportunity to flex your C legs.

If you find it difficult to answer these questions after reading the books, come back to this after you have completed the programming assignment below.

Part 2: Using Linux Linked Lists

Before starting the programming portion of this assignment, familiarize yourself with writing and using Linux kernel modules. You will be writing your own module using Linux’s linked list implementation, included from <linux/list.h>.

We define a kernel data structure to represent birthdays:

struct birthday {
    int day;
    int month;
    int year;
    struct list_head list;
};

Note that the struct list_head field is embedded within our data structure.

Your task is to write a kernel module that will manipulate a list of birthdays. On initialization, it will add some birthdays to the list, and then print them out. On exit, it will print out those birthdays again, then delete those birthdays from the list.

The skeleton code contains the outline of the kernel module, including the above struct birthday definition, and the entry and exit points, birthday_init and birthday_exit. You should not modify these.

Your job is to fill in the functions called by these entry and exit points. First, you should declare a single struct list_head named birthday_list, which will serve as the head of the list of struct birthdays.

Then, you must fill in following functions, using the macros provided by <linux/list.h>:

Note that your birthdays will need to persist between your module’s entry point and exit point – you may find the functions kmalloc() and kfree() useful. These serve the same purpose as malloc() and free(), except in the kernel execution context. Note that kmalloc() takes an additional flag parameter – for this assignment, you may just use GFP_KERNEL for that argument. See LKD pp.238-244 for more details.

Part 3: (Not Quite) Using Linux Linked Lists

Rewrite part 2 without using the macros and functions defined in <linux/list.h>. In other words, replace the calls to the following functions and macros with your own inline code manipulating pointers:

list_add_tail()
list_for_each_entry()
list_del()
list_for_each_entry_safe()

Note that those functions and macros call other functions and macros in <linux/list.h>. You cannot use any of them (or redefine your own equivalent macros). You should look at how <linux/list.h> is implemented, and manually replicate/inline what those macros and functions do for your struct birthday without using/calling them. You should use the kernel data structures in manner that is consistent with how the <linux/list.h> library uses them.

Part 4: Task List

In Linux, processes are reprsented by the struct task_struct, which is defined in <linux/sched.h>. Each task_struct represents a node in the process tree. To implement this tree data structure, it uses two struct list_head fields: children and sibling. children is the list head to the process’s list of children, while sibling connects each process to its siblings, as well to its parent’s children field.

For this part, the skeleton code we have provided is a minimal kernel module boilerplate. Your task is to write a kernel module, tasklist. Upon initialization, it perform a depth-first traversal of the process tree, and print out the process tree. This module should do nothing on exit.

You should start at the root of the process tree, which you may access via the struct tast_struct init_task variable exposed by <linux/sched.h>. For each process, you should print out its PID and the process name. You may obtain these from the pid and comm fields of the task_struct.

When you print out the processes, you should also display the hierarchical tree. Here is an example output:

[ 9303.501734] Removing Module
[ 9304.846569] Loading Module
[ 9304.846574] -- [0] swapper/0
[ 9304.846576]     \_ [1] systemd
[ 9304.846578]         \_ [95] systemd-journal
[ 9304.846579]         \_ [119] systemd-udevd
[ 9304.846581]             \_ [14948] systemd-udevd
[ 9304.846583]         \_ [150] VBoxService
[ 9304.846585]         \_ [152] systemd-logind
[ 9304.846586]         \_ [153] avahi-daemon
[ 9304.846588]             \_ [160] avahi-daemon
[ 9304.846590]         \_ [154] dbus-daemon
[ 9304.846592]         \_ [155] dhcpcd
[ 9304.846593]         \_ [162] login
[ 9304.846595]             \_ [365] bash
[ 9304.846597]                 \_ [441] startx
[ 9304.846599]                     \_ [458] xinit
[ 9304.846601]                         \_ [459] X
[ 9304.846603]                         \_ [462] sh
[ 9304.846605]                             \_ [474] xfce4-session
[ 9304.846607]                                 \_ [488] xfwm4
[ 9304.846609]                                 \_ [490] Thunar
[ 9304.846611]                                 \_ [491] xfce4-panel
[ 9304.846614]                                     \_ [512] panel-16-systra
[ 9304.846616]                                     \_ [516] panel-17-action
[ 9304.846618]                                 \_ [493] xfdesktop
[ 9304.846621]                                 \_ [496] xfce4-terminal
[ 9304.846623]                                     \_ [556] gnome-pty-helpe
[ 9304.846625]                                     \_ [558] bash
[ 9304.846627]                                     \_ [570] bash
[ 9304.846629]                                     \_ [581] bash
[ 9304.846631]                                     \_ [587] bash
[ 9304.846633]                                         \_ [15189] sudo
[ 9304.846635]                                             \_ [15190] insmod
[ 9304.846638]                                     \_ [8939] bash
[ 9304.846639]         \_ [167] sshd
[ 9304.846641]         \_ [182] rpcbind
[ 9304.846642]         \_ [193] ntpd
[ 9304.846644]         \_ [174] automount
[ 9304.846645]         \_ [195] rpc.gssd
[ 9304.846646]         \_ [362] systemd
[ 9304.846648]             \_ [364] (sd-pam)
[ 9304.846649]         \_ [468] dbus-daemon
[ 9304.846651]         \_ [467] dbus-launch
[ 9304.846652]         \_ [476] polkitd
[ 9304.846654]         \_ [484] xfconfd
[ 9304.846655]         \_ [487] gpg-agent
[ 9304.846657]         \_ [494] xfsettingsd
[ 9304.846659]         \_ [503] xfce4-power-man
[ 9304.846660]         \_ [525] upowerd
[ 9304.846661]         \_ [548] VBoxClient
[ 9304.846662]         \_ [561] VBoxClient
[ 9304.846663]         \_ [578] VBoxClient
[ 9304.846664]         \_ [593] VBoxClient
[ 9304.846665]         \_ [632] rpc.statd
[ 9304.846667]         \_ [1233] at-spi-bus-laun
[ 9304.846668]         \_ [1220] firefox
[ 9304.846669]     \_ [2] kthreadd
[ 9304.846670]         \_ [3] ksoftirqd/0
[ 9304.846671]         \_ [5] kworker/0:0H
[ 9304.846672]         \_ [6] kworker/u2:0
[ 9304.846673]         \_ [7] migration/0
[ 9304.846674]         \_ [8] rcu_bh
[ 9304.846675]         \_ [9] rcu_sched
[ 9304.846676]         \_ [10] watchdog/0
[ 9304.846677]         \_ [11] khelper
[ 9304.846679]         \_ [12] kdevtmpfs
[ 9304.846680]         \_ [13] netns
[ 9304.846681]         \_ [14] writeback
[ 9304.846682]         \_ [15] bioset
[ 9304.846683]         \_ [16] kblockd
[ 9304.846684]         \_ [18] khungtaskd
[ 9304.846685]         \_ [19] kswapd0
[ 9304.846686]         \_ [20] ksmd
[ 9304.846687]         \_ [21] khugepaged
[ 9304.846688]         \_ [22] fsnotify_mark
[ 9304.846689]         \_ [23] crypto
[ 9304.846690]         \_ [27] kthrotld
[ 9304.846691]         \_ [28] deferwq
[ 9304.846693]         \_ [52] ata_sff
[ 9304.846694]         \_ [53] khubd
[ 9304.846695]         \_ [54] scsi_eh_0
[ 9304.846696]         \_ [55] scsi_eh_1
[ 9304.846697]         \_ [56] kworker/u2:2
[ 9304.846698]         \_ [57] scsi_eh_2
[ 9304.846699]         \_ [64] kworker/0:1H
[ 9304.846700]         \_ [72] jbd2/sda1-8
[ 9304.846701]         \_ [73] ext4-dio-unwrit
[ 9304.846702]         \_ [99] rpciod
[ 9304.846703]         \_ [107] nfsiod
[ 9304.846704]         \_ [112] iprt
[ 9304.846705]         \_ [142] kpsmoused
[ 9304.846706]         \_ [8798] lockd
[ 9304.846707]         \_ [11501] kworker/0:1
[ 9304.846709]         \_ [12139] kworker/0:2
[ 9304.846710]         \_ [12956] kworker/0:3

The format doesn’t have to be exactly the same, but the output must clearly show the hierarchical tree.

To avoid printing too much whitespace to your kernel log buffer, you should set a maximum indentation level. We suggest setting this amount to 20. Processes deeper down in the tree will still only receive 20 levels worth of indentation.


Acknowledgements

Parts 2 and 4 adapted from the programming projects in chapters 2 and 3 of Operating Systems Concepts by Abraham Silberschatz, Peter B. Galvin, and Greg Gagne.


Last updated: 2019-01-22