Common Linked Lists VS Linux Kernel Linked Lists

Recently I started to read a pretty old but still really good kernel book Linux Kernel Development It was written by Robert Love (you can find more info about this great guy here) I wanted to share some useful information about kernel internals from his book I believe that this info can be useful for many Linux folks.

Common linked lists VS Linux Kernel linked lists.

Let’s assume that we have date structure that describes a cat:

struct cat {
    unsigned long weight;   /* mass in kg */
    unsigned long height;   /* height in cm */
    bool is_real;           /* is this a real cat or a fictional character? */
};

If we want to transform this data structure into linked lists we should add pointers to the next and the previous elements:

struct cat {
    unsigned long weight;   /* mass in kg */
    unsigned long height;   /* height in cm */
    bool is_real;           /* is this a real cat or a fictional character? */
    struct cat *next;       /* pointer to the next element in the list */
    struct cat *prev;       /* pointer to the previous element in the list */
};

But Linux Kernel has a little bit different approach: built-in linked lists data structure. One can find it on the github It has a pretty simple structure:

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

In the next variable we have a pointer to the next element of the list and in the prev variable - to the previous one. So our cat structure from the first example will become:

struct cat {
    unsigned long weight;   /* mass in kg */
    unsigned long height;   /* height in cm */


    bool is_real;           /* is this a real cat or a fictional character? */
    struct list_head list;  /* list of all cat structures */
};

Now in the list.next variable we have a pointer to the next element of the list and in the list.prev variable - to the previous one. It is really useful because in the kernel we can find a lot of functions for the linked lists. For example if we want to add element to the linked list we can use list_add() function.

References: