Intrusive Linked Lists (2019)

Data structures in practice: An exploration of Intrusive Linked Lists Date: 2019.9.23

This guide explains the concept of intrusive linked lists and details their specific application within the Linux kernel for process management.

---

Understanding the Concept

An intrusive linked list is a specialized version of a linked list where the linkage mechanism (the pointers) is embedded directly within the data structure being managed.

Standard vs. Intrusive Lists

In a traditional linked list, the "node" is a wrapper. It contains a pointer to the actual data and a pointer to the next node. In contrast, an intrusive list removes the data pointer entirely because the list node is a member of the data object.

Visualizing the Difference

Figure 1: Standard Linked List

Figure 2: Intrusive Linked List

---

Technical Implementation

For a basic intrusive singly linked list, the structure is minimal:

typedef struct list {
    struct list * next;
} list;

This list structure is then placed inside a larger object. For instance, consider an item structure:

typedef struct item {
    int val;
    list items; // The intrusive node
} item;

To link two items (i1 and i2), you point the node inside the first to the node inside the second:

item * i1 = create_item(16);
item * i2 = create_item(18);

// Link i1 to i2
i1->items.next = &i2->items;

Recovering the Parent Object

Since we only have a pointer to the list node, we must calculate the address of the containing item object. This is done by subtracting the offset (the number of bytes from the start of the object to the start of the list member).

Figure 3: Memory Layout If object i2 is at memory address $0x10$ and the items member is offset by $8$ bytes, the node address is $0x18$. To go backward:

$\text{Object Address} = \text{Node Address} - \text{Offset}$ $0x10 = 0x18 - 8$

Implementation in C (GCC)

In GCC, you can perform this by casting to a void * (which GCC treats as 1 byte). Standard C forbids pointer arithmetic on void pointers, but GCC allows it. However, for portability across different CPU architectures, offsetof is used:

// Portable way to retrieve the containing structure
item * _s2 = (void *)(i1->items.next) - (offsetof(item, items));

Summary of Object Retrieval

• Identify the address of the embedded list node.
• Determine the byte offset of that node within the parent struct.
• Subtract the offset from the node address to find the base address.

---

Why Use Intrusive Lists?

"Why would any sane developer choose this over a standard linked list?"

There are two primary architectural advantages:

1. Reduced Memory Overhead:
   • Non-intrusive: Requires two allocations (one for the object, one for the node).
   • Intrusive: Requires only one allocation.
   • Result: Fewer potential memory allocation failures to handle.
2. Cache Efficiency:
   • Non-intrusive lists cause more cache thrashing because you must dereference the node and then dereference the data pointer (two separate memory locations).
   • Intrusive lists only require dereferencing the next node, as the data is right there.

---

Advanced Variations

Doubly and Circular Lists

Linux utilizes circular doubly linked lists.

• Doubly Linked: Contains both next and prev pointers. This simplifies insertion and deletion since you only need a reference to the node being operated on.
• Circular: The list never ends in NULL; the tail points back to the head.

typedef struct dlist {
    struct dlist * next;
    struct dlist * prev;
} dlist;

A circular list allows iteration from any starting point without needing a specific head pointer:

void list_print_each (list * node) {
    list * start = node;
    do {
        printf("%d,", node->val);
        node = node->next;
    } while (node != start);
}

---

Intrusive Lists in the Linux Kernel

The Linux kernel relies heavily on these structures, specifically the struct list_head defined in include/linux/list.h. In version 5.2, there are over 10,000 references to this structure.

Usage Patterns

Interestingly, Linux uses linked lists primarily for storage rather than frequent searching. According to analysis by Rusty Russell:

• Traversals account for only 6% of total linked list operations.
• Of those traversals, 28% are performed on empty lists or lists with only one element.

Conclusion: Linux employs intrusive circular doubly linked lists because they are highly efficient for adding and removing objects, which are the most frequent operations, especially when list sizes remain small or traversal is rare.