DEV Community

Saurav Shah
Saurav Shah

Posted on

Linked List in the Linux Kernel

#linux #datastructures #tutorial #architecture

The traditional way of implementing a linked list is to add a pointer to the next node (and a previous node in the case of a doubly linked list). The Linux kernel’s implementation is somewhat different. This post explores the implementation of the doubly linked list in the Linux kernel. 🧵

Example Code

Let’s start with an example. This example creates a circular doubly linked list and shows how to add/delete nodes and loop through the entries.

#include <linux/module.h>
#include <linux/list.h>

#define MODULE_NAME "KERNEL_LL "

struct data {
    u32 count;
    char *name;
    struct list_head node;
};

static LIST_HEAD(data_head);

static int __init kernelLL_init_module(void)
{
    struct data v1 = {
        .count = 1,
        .name = "data1"
    };
    struct data v2 = {
        .count = 2,
        .name = "data2"
    };
    struct data v3 = {
        .count = 3,
        .name = "data3"
    };
    struct data *curr;
    pr_info(MODULE_NAME"init\n");

    list_add_tail(&v1.node, &data_head);
    list_add(&v2.node, &data_head);
    list_add(&v3.node, &data_head);

    pr_info(MODULE_NAME"After Adding:\n");
    list_for_each_entry(curr, &data_head, node)
        pr_info(MODULE_NAME"%d: %s\n", 
                    curr->count, curr->name);

    pr_info(MODULE_NAME"Invalid access:\n");
    list_for_each_entry(curr, &v2.node, node)
        pr_info(MODULE_NAME"%d: %s\n", 
                    curr->count, curr->name);

    list_del(&v2.node);
    pr_info(MODULE_NAME"After Deleting:\n");
    list_for_each_entry(curr, &data_head, node)
        pr_info(MODULE_NAME"%d: %s\n", 
                    curr->count, curr->name);

    return -EINVAL; //Don't load the module
}
module_init(kernelLL_init_module);
MODULE_LICENSE("GPL");
Enter fullscreen mode Exit fullscreen mode

This is the output

$ dmesg
[962638.228544] KERNEL_LL init
[962638.228545] KERNEL_LL After Adding:
[962638.228545] KERNEL_LL 3: data3
[962638.228546] KERNEL_LL 2: data2
[962638.228546] KERNEL_LL 1: data1
[962638.228546] KERNEL_LL After Deleting:
[962638.228546] KERNEL_LL 3: data3
[962638.228546] KERNEL_LL 3: data1
Enter fullscreen mode Exit fullscreen mode

struct data is just like any custom container with an additional field named node of type struct list_head. Isn’t that sleek? 😄 You can add a member of type struct list_head in any container to make it a list node.

container_of Macro

Before that, let me talk about container_of(ptr, type, member) macro in the kernel.

struct data *pval = (struct data*) kzalloc(sizeof(struct data), GFP_KERNEL);
struct data *pcontainer = container_of(&pval->count, struct data, count);
//pval and pcontainer points to same address
Enter fullscreen mode Exit fullscreen mode

Say you have a pointer to a member in a container (a struct), and you want to get the address of the container; you can use container_of to get the container’s address. The kernel’s linked list uses this container_of pattern heavily. 💡

struct list_head type

LIST_HEAD(name) declares and initializes a list head of type struct list_head. Any node you add to the list must have a member of type struct list_head, and that member is what actually links the nodes together (via prev/next). The container structs (struct data in our case) are never linked directly; only their struct list_head members are.

Adding / Deleting a node

You can use list_add(new, head) to add the node to the front of the linked list. Use list_add_tail(new, head) to add the node to the end. Note how you use list_add(&v1.node, &data_head) and not list_add(&v1, &data_head), essentially adding the struct list_head and not the struct data type.

  1. You start with an empty list. 
static LIST_HEAD(data_head);
Enter fullscreen mode Exit fullscreen mode

LIST_HEAD

  1. Add a node to the tail of the list 
list_add_tail(&v1.node, &data_head);
Enter fullscreen mode Exit fullscreen mode

LIST_HEAD

  1. Add a node to the head of the list 
list_add(&v2.node, &data_head);
Enter fullscreen mode Exit fullscreen mode

LIST_HEAD

  1. Delete a node 
list_del(&v2.node);
Enter fullscreen mode Exit fullscreen mode

LIST_HEAD

Traversing a node

You can use the macros list_for_each(pos, head) and list_for_each_entry(pos, head, member) to traverse the list.

  • list_for_each loops through the list starting from head->next and gives you a struct list_head *pos pointing to the node member.
  • list_for_each_entry does essentially the same traversal, but additionally uses container_of to give you the actual container (struct data * in this case) at each position.

Note that traversing a list doesn’t do any safety checks. It will start from head->next, follow next pointers, and stop when it reaches head again in this circular list implementation.

Say you have a linked list 3 <-> 2 <-> 1 (head is data_head) and you run this code:

list_for_each_entry(curr, &v2.node, node)
    pr_info(MODULE_NAME"%d: %s\n", 
                curr->count, curr->name);
Enter fullscreen mode Exit fullscreen mode

This is the output.

[966562.045245] KERNEL_LL 3: data1
[966562.045245] KERNEL_LL 0: (null)
[966562.045245] KERNEL_LL 3: data3
Enter fullscreen mode Exit fullscreen mode

You see! We gave v2.node as the “head”. So while traversing, it starts with head->next, which is 1, so it prints 1. Next iteration is 1->next, which is the real head (data_head). When you call container_of on the real head (which is just a struct list_head, not embedded in any struct), it doesn’t have a valid container, so members like count and name are garbage/uninitialized. That’s what we see as 0 and null. Finally it continues from there and prints 3 again.

So:

  • list_for_each_entry assumes the head argument is a proper list head (not a list node embedded inside a struct).
  • It is a good practice to name the head in a way that is distinct from the node members and to use that head consistently. In our example, we should always use data_head as the head. ✅

Start using the Linux kernel linked list now! 🚀

Please note that it’s always a good practice to use arrays wherever possible when your data is naturally contiguous, since contiguous data is faster to access and more cache–friendly. Linked lists are great when you need frequent insertions/removals in the middle of the sequence, or when you don’t know the size in advance.

List APIs

These are some of the APIs you can use to manipulate/access linked lists in the kernel. Please refer to the kernel documentation for more detailed information. 📚

  1. LIST_HEAD_INIT(name) : Initialize the list during initial assignment
  2. INIT_LIST_HEAD(*list) : Initialize the list that already exists
  3. list_add(*new, *head) : Add a node to the head of the list
  4. list_add_tail(*new, *head) : Add a node to the tail of the list
  5. list_for_each(pos, head) : Traver through the list, pos point to the current struct list_head while traversing
  6. list_entry(ptr, type, member) : Get the cotnainer for the node pointed by ptr of type struct list_head
  7. list_for_each_entry(pos, head, member) : Iterate over the list to get the container of current position
  8. list_del(*entry) : Remove the entry from the list. The node removed will have the list pointers set to poision value.
  9. list_del_init(*entry) : Remove the entry from the list and reinitialize the removed node (to point to itself)
  10. list_for_each_safe(pos, head) / list_for_each_entry_safe(pos, head, member) : Same as 5 and 6 with additional logic to handle the case where you delete the node while traversing the list
  11. list_cut_position(*list, *head, *entry) : Removes all the entries from head till (including) entry and put it in the list
  12. list_cut_before(*list, *head, *entry): Removes all the entries from head till (exclusing) entry and put it in the list
  13. list_move(*list, *head): Removes one list entry head and adds it to the front (head) of another list list
  14. list_move_tail(*list, *head) : Removes one list entry head and adds it to the back (tail) of another list list
  15. list_bulk_move_tail(*head, *first, *last): Moves a bulk entry starting from first till last to the tail of another list head
  16. list_rotate_left(*head): Rotates the circular list counter-clockwise (left) by one entry
  17. list_rotate_to_front(*list, *head): Rotates the circular list counter-clockwise (left) until head comes to the front
  18. list_swap(*entry1, *entry2): Swaps the nodes pointed by entry1 and entry2
  19. list_splice(*list, *head): Takes the list pointed by list and puts it just after the node pointed by head. Note the list pointed by list will still point to the next node.
  20. list_splice_init(*list, *head): Same as 18, nut reinitializes the list poited by list (it will point to itself).

There are more APIs; you can refer to the Kernel Documentation for the full list and detailed explanations. 🔍

Top comments (0)