Mastering Linux Kernel Linked Lists: From Theory to High‑Performance Code

Linux Kernel Linked List Overview

The Linux kernel uses an intrusive linked‑list implementation: a struct list_head node is embedded directly inside user‑defined structures, eliminating the need for a separate wrapper node and allowing any data type to be linked with the same macros.

Core structure

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

This two‑pointer structure forms a circular doubly‑linked list where the head’s next and prev point to itself when the list is empty.

Embedding the node

struct my_node {
    struct list_head list;   /* list node */
    int data;                /* payload */
};

Any structure can contain a list member and be managed by the kernel list API.

Basic operations

Initialisation

#include <linux/list.h>
struct list_head my_list;
INIT_LIST_HEAD(&my_list);

Insertion Head insertion (LIFO) uses list_add :

#include <linux/list.h>
struct my_struct {
    int data;
    struct list_head list;
};
void add_head(struct list_head *head, int val) {
    struct my_struct *node = kmalloc(sizeof(*node), GFP_KERNEL);
    node->data = val;
    list_add(&node->list, head);
}

Tail insertion (FIFO) uses list_add_tail :

#include <linux/list.h>
void add_tail(struct list_head *head, int val) {
    struct my_struct *node = kmalloc(sizeof(*node), GFP_KERNEL);
    node->data = val;
    list_add_tail(&node->list, head);
}

Deletion Safe traversal with list_for_each_entry_safe prevents pointer corruption while removing nodes:

#include <linux/list.h>
void del_node(struct list_head *head, int target) {
    struct my_struct *cur, *tmp;
    list_for_each_entry_safe(cur, tmp, head, list) {
        if (cur->data == target) {
            list_del(&cur->list);
            kfree(cur);
            break;
        }
    }
}

Search Linear search using list_for_each_entry :

#include <linux/list.h>
struct my_struct *find(struct list_head *head, int target) {
    struct my_struct *cur;
    list_for_each_entry(cur, head, list) {
        if (cur->data == target)
            return cur;
    }
    return NULL;
}

Memory‑usage comparison

Because only two pointers are stored per node, the kernel list uses less memory than a traditional node that also stores a data pointer. The following user‑space benchmark (compiled outside the kernel) illustrates the difference for 1 000 integers:

#include <stdio.h>
#include <stdlib.h>
struct TraditionalNode { int data; struct TraditionalNode *next; };
struct CustomStruct { int data; struct list_head list; };
int main(void) {
    size_t trad = sizeof(struct TraditionalNode) * 1000;
    size_t kern = sizeof(struct list_head) * 1000 + sizeof(int) * 1000;
    printf("Traditional list memory: %zu bytes
", trad);
    printf("Kernel list memory: %zu bytes
", kern);
    return 0;
}

Traversal optimisation

Repeated use of list_entry can be avoided by pre‑computing the offset of the list member:

struct my_struct { int data; struct list_head list; };
size_t offset = offsetof(struct my_struct, list);
struct list_head *pos;
struct my_struct *entry;
list_for_each(pos, &my_list) {
    entry = (struct my_struct *)((char *)pos - offset);
    /* operate on entry->data */
}

Benchmarks with 100 000 nodes show a measurable speed‑up over the macro‑based version.

Concurrency control with RCU

Read‑Copy‑Update (RCU) enables lock‑free reads. Writers create a new node, link it, and defer freeing the old node with call_rcu after a grace period:

list_add(&new_node->list, &my_list);
smp_mb();               /* ensure visibility */
call_rcu(&old_node->rcu_head, rcu_free_func);

This pattern is common in read‑heavy subsystems such as the networking stack.

Memory barriers

Barriers guarantee ordering of memory operations across CPUs. After inserting a node, a full barrier ( smp_mb()) ensures other CPUs see the new links before any subsequent writes:

list_add(&new_node->list, &my_list);
smp_mb();   /* publish the new node */

Similarly, a barrier before list_del ensures all prior accesses to the node complete.

Real‑world kernel examples

Device driver model

struct char_device {
    dev_t dev_num;
    const char *name;
    const struct file_operations *fops;
    struct list_head list;
};

static LIST_HEAD(char_device_list);

int char_device_register(struct char_device *dev) {
    INIT_LIST_HEAD(&dev->list);
    list_add_tail(&dev->list, &char_device_list);
    return 0;
}

void char_device_unregister(struct char_device *dev) {
    list_del(&dev->list);
}

Process scheduling

struct task_struct {
    pid_t pid;
    int priority;
    struct list_head list;
};

static LIST_HEAD(priority_queue);

void insert_process(struct task_struct *p) {
    struct list_head *pos;
    list_for_each(pos, &priority_queue) {
        struct task_struct *e = list_entry(pos, struct task_struct, list);
        if (p->priority > e->priority) {
            list_add_before(&p->list, pos);
            return;
        }
    }
    list_add_tail(&p->list, &priority_queue);
}

Common pitfalls and debugging tips

Null‑pointer dereference : always verify the list is non‑empty before using list_for_each or list_entry.

Memory leaks : every kmalloc must be paired with a kfree after list_del.

Corrupted links : ensure both next and prev are updated when inserting or removing nodes; use the provided macros instead of manual pointer manipulation.

Debugging : insert printk(KERN_INFO "node data=%d\n", e->data); at allocation, insertion, and deletion points; use kgdb for step‑by‑step inspection; tools like dmesg, perf and sysdig help analyse performance and correctness.