October 17th, 2005


Code Reading - The Linux kernel doubly linked list

It's great if students are exposed to professional, high quality code early in their engineering education. The difficulty is in identifying code which challenges the newbie student intellectually but doesn't fly far above his head. I am trying to build a small collection of code snippets taken from real programs which demonstrates the subtleties of the art of programming - as my only real code reading experience comes from the Linux kernel, most of my examples are going to be taken from there.

Linked lists are taught as part of every data structure course - the Linux kernel has a simple implementation (in include/linux/list.h) which will surely surprise (and enlighten) the beginner. The very first declaration in the file is:

struct list_head {
    struct list_head *next, *prev;
Of what use is a linked list node without the data part? The student will discover the answer when he decodes the list_entry macro:
#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
Understanding this simple macro requires the student to learn about type manipulations (I always stress the fact that learning pointers is nothing but learning more about type manipulations) and compiler code generation issues. This is one example which I use quite effectively in class these days.

Can somebody suggest more examples?