HW2-linked-list

HW2: Linux Linked List (100 points)

How to submit

The TAs and I are using GitHub for distributing and collecting your assignments. At this point you should have already set up your repository. If you have not yet done so, please follow the instructions sent to you over the class listserv.

To obtain the skeleton files that we have provided for you, you need to clone your private repository. Your repository page should have a link titled “clone or download” – copy the link from there. For example:

$ git clone https://github.com/cs4118-hw/hw2-<your-github-username>.git

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 get a ZERO. The class is too big for the TAs to spend time dealing with sloppiness.

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: git tutorial

After you commit, you can push your changes to your repository as follows:

$ git push origin master

To hand in your assignment, you will create and push a tag:

$ git tag -a -m "I completed hw2." hw2handin
$ git push origin master
$ git push origin hw2handin

You should verify that you are able to see your final commit and your hw2handin tag on your GitHub repository page for this assignment.

If you made a mistake and wish to resubmit your assignment, you can do the following:

$ git push --delete origin hw2handin
$ git tag --delete hw2handin

You may then repeat the submission process.

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 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 we have provided.

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 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 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.

Part 2: Using Linux Linked List (20 points)

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

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 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 list.h. You cannot use any of them (or redefine your own equivalent macros). Basically what I want you to do is to look at how list.h is implemented, and manually replicate/inline what those macros and functions do for your struct birthday without using/calling them.

Part 4: Process List (30 points)

Follow the “Programming Projects / Project 2 - Linux kernel Module for Listing Tasks” section 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: 2018-01-23