Linked list in linux kernel implementation

Linked list in linux kernel implementation

We learned a lot about linked and solve around 30 odd problems : Linked List Problems. However, actual implementation of linked list in linux kernel is very different that what we learned. So, let’s understand how linked list is implemented in linux kernel and how it is used in kernel code.

In simple linked list, we have nodes which contain data and these nodes point to next node of them. In other words, its the list which contains nodes which are linked. Typical example of structure of node of this kind of list is:

struct node {
  int data;
  struct node * next;
} Node;

However, in linked lists in kernel, it’s the other way around, that is linked list is contained inside the node. This means, that there is no next pointer inside node and every node is effectively a head node, nature of linked list circular and it is doubly linked list. Lot of things in one sentence!!

Linked list implementation in Linux

Let’s understand things in detail. As said, linked list is contained inside the node, structure of node is something like this:

struct node {
 int data;
 list_head list; // list is inside the node
};

Here list_head is what defined as :

struct list_head{
  struct list_head *next, *prev;
}

See it has two pointers, essentially, making any node which contains this structure, part of a doubly linked list. Most interesting part of this kind of definition of node is that same node can be part of multiple list without being reallocated for each list. For example, in traditional linked lists, if I need two linked one as odd numbers and other as prime numbers, i would have to define two linked lists , one containing odd numbers and other for primer number. With implementation provided in linux kernel, we can attache the same node to two lists as shown below.

struct numbers {
 int number;
 list_head odd_numbers; // contains all odd numbers
 list_head primer_numbers; // Contains all prime numbers
};

How to access a node in linked list in Linux Kernel

Now that we have changed the node structure, how can we access a give node of linked list. It was simple to do in normal linked list as base address of node was easily accessible. In linked list in linux kernel, we have pointer to list_head structure in next node and not pointer to next node itself, as shown below.

linked list in linux

There is a beautiful trick in C, which is used here to access base address of node whose list_head pointer is given. Once base address of node is found, accessing becomes similar to normal linked list. Trick is that given a pointer to list_head in structure, and to find the base pointer of structure in which it is present, we need to find the offset at which list_head is stored in list. Once, we know the offset, (how many bytes, it is far from base address), then just subtract that offset from the absolute address of the pointer (which is given) and we get the base address. Figure explains

linked list in linux kernel example

Let’s take an example, we will use structure numbers as given above. To get offset of element number in that, code is:

(unsigned long)(&((struct numbers *)0)->number)

Now, that we have offset of number and absolute address of number, we can get the base address of struct numbers as :

((struct numbers *)((char *)(pos) - (unsigned long)(&((numbers *)0)->number)))

ANSI C defines the offsetof() macro in , which lets you compute the offset of field f in struct s as offsetof(struct s, f). If for some reason you have to code this sort of thing yourself, one possibility is

#define offsetof(type, f) ((size_t) \
 ((char *)&((type *)0)->f - (char *)(type *)0))

Above code is not portable and some compilers may have problems with it.

There are some MACROS which are defined in linux kernel which are useful in dealing with linked lists. Below are some examples:

#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))


#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \
	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

Please refer to this file to understand various macros which are used in linux kernel. In next post, using these constructs, we shall create a linked list , access it and delete a list.

Please share if there is something wrong or suggestion for improvements. Also, if you like the content, please share it.