Linked list implementation in Linux kernel

Tags: , , ,

Linked list implementation in Linux kernel

We learned a lot about linked and solve around 30 odd problems : Linked list problems. However, the actual implementation of a linked list in Linux kernel is very different than what we learned. Let us understand how a linked list is implemented in Linux kernel and used in kernel code.

In a simple linked list, nodes contain data and point to the next node in the linked list. In other words, its the list which contains nodes which are linked. A typical example of the structure of a node of this kind of a list is:

class Node {
  private int data;
  private Node next;

  public Node (int data, int next){
      this.data = data;
      this.next = next;   
  }

  //Getters
};

However, linked lists in the Linux 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 the node and each node is effectively a head node like a circular linked list. Also, it is a doubly linked list. A lot of things in one sentence!!

Linked list implementation in Kernel

Let’s understand it in detail. As said above, linked list is contained inside the node, structure of node is 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. The most interesting part of this kind of definition of a node is that same node can be part of multiple lists without being reallocated for each list. For example, in traditionally linked lists, if we need two linked lists: one as odd numbers and other as prime numbers, we would have to define two linked lists, one with odd numbers and other with prime numbers. With implementation provided in the Linux kernel, we can attach the same node to two lists as shown below, where an odd number which is also prime is allocated only once.

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 list in Linux Kernel

We understood the node structure, how can we access a given node of a linked list. It was simple to do in a normal linked list as the base address of node accessible. In list implemented in Linux kernel, we have a pointer to the list_head structure in the next node and not a pointer to next node itself, as shown below.

linked list representation in linux kernel

There is a beautiful trick in C, which is used here to access the base address of the node whose list_head pointer is given. Once the base address of a node is known, accessing the node becomes similar to a normal linked list. The trick is that given a pointer to list_head in the structure; to find the base pointer of structure, 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

node representation in linked list in linux kernel

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 the 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)))
<pre>#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

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

Please refer to this file to understand various macros which are used in Linux kernel.

In next post, we will use these constructs and see how can we created a 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.