HW2: Linux Linked List (100 points)

What to submit

You are to submit a single tar.gz file named as follows:

UNI-hw2.tar.gz

The tarball contains a single top level directory hw2, which contains a git repo, README.txt, and directories for each part containing files as specified in each part. The directory structure looks like this:

hw2/.git
hw2/README.txt
hw2/part1
hw2/part2
...

The TAs will use scripts to download, extract, build and display your code. It is essential that the directory structure and file naming be followed EXACTLY. If you deviate from the requirements, the grading scripts will fail and you will get a ZERO. The class is too big for the TAs to spend time dealing with sloppiness.

Some examples of wrong names and places:

abc1234_hw2.tar.gz
abc1234-hw2.tgz
hw2/README
hw2/part1/README.txt
HW2

You need to have at least 5 git commits total, but I encourage you to have many more. Your work history is your best defense when you’re accused of cheating. If you have not used git before, you need to learn it quickly. The following tutorial can get you started:

Your submission can contain untracked files – editor backups, input/output files, text files containing your notes, etc. – but should not contain any binary files. You will lose points if it does.

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

Unless otherwise specified, the description can be as short as “My code works exactly as specified in the assignment.” You may also want to include anything else you would like to communicate to the grader such as extra functionalities you implemented or how you tried to fix your non-working code.

This submission guideline applies to all future assignments to the extent it’s applicable – the next one will use “hw3” instead of “hw2” for example.

Part 1: Reading and written assignment (20 points)

(a) OSC book

Please read the following two sections from OSC:

Then answer the following Exercise questions from OSC:

(b) LKD book

Read LKD, Chapter 6, page 85–96 on Linux 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, page 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 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 macros 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 Linux kernel. Take this opportunity to pump up your C muscle.

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

Please write your answers in the README.txt file at the top level. Do NOT create part1 directory.

Part 2: Using Linux Linked List (20 points)

Follow the “Programming Projects / Linux Kernel Modules” at the end of Chapter 2 in the OSC book.

The skeleton code – simple.c and Makefile – is available from the book’s web site. (It’s also part of the lecture L03 source code.)

Part 3: (Not Quite) Using Linux Linked List (30 points)

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 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 list.h. You cannot use any of them. Basically what I want you to do is to look at how those macros are written in list.h, and replicate what those macros and functions do manually for your struct birthday.

Part 4: Process List (30 points)

Follow the “Programming Projects / Project 2 - Linux kernel Module for Listing Tasks” at the end of Chapter 3 in the OSC book.

There is a small additional requirement though. When you print out the processes, 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.

You are allowed to set a maximum indentation. In my code, I indent only up to 20 levels even if a process lives deeper in the tree.


Last updated: 2015–01–30