How Linux Uses Intrusive Linked Lists to Manage Processes
Intrusive linked lists embed the list node directly into the data structure, eliminating separate allocations and improving cache performance. This article explains the concept, including pointer arithmetic and the offsetof macro, then dives into Linux's implementation using circular doubly linked lists with the list_head structure. It shows how the kernel tracks every process in a task list, adding new tasks via fork and iterating over them for operations like sending signals, all with minimal overhead.
A search for the `struct list_head` structure returns over 10,000 results in Linux 5.2.
- el_pollo_diablo
The go a bit further than the article on the advantages of intrusive data structures, taking linked lists as an example:
As the article mentions, intrusive data structures naturally lead to one fewer indirection. To do the same with a traditional list (where the list node owns the payload), a different node type is needed for each payload type. This is easy to do with the proper support for monomorphized generics, see C++'s std::list. It is awkward in C, where the implementation has to be macro-generated. C naturally pushes towards an indirection through void *, which makes intrusive lists more attractive.
One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections (where traditional collections would require e.g. one collection owning the payloads, and the other collections merely holding non-owning pointers to them).
Las but not least, the defining property of intrusive data structures is that they leave the responsibility of allocating the elements to the user. The elements can be allocated on the heap, on the stack, in a global array (like "initholes" in the article), in a special arena, etc. It is even reasonable to use non-uniform allocation strategies; for example, for a circular list, allocate an anchor node on the stack and the other nodes (those embedded in payloads) on the heap.
- pclmulqdq
I was surprised to see the main benefit of intrusive linking mentioned as a bit of a side note: The ability to move data around between lists (and within a list) without copying. You also get O(1) removal from the middle of the list, assuming you have a pointer to the object somewhere else. As a result, when you have large state structs and you don't do a lot of list scans, intrusive linking makes things a lot faster than use of packed structures like vectors.
- flohofwoe
Hmm interesting, the doubly linked list presented here is missing the elegant 'overlapped list header' trick from AmigaOS (at least that's where I saw it first):
E.g. an AmigaOS list node looks conventional, it has two pointers, one to the next node (succ), and one to the previous node (pred):
struct Node {
struct Node* ln_Succ;
struct Node* ln_Pred;
};
Most AmigaOS structs embed such a Node struct at the start.
...but the list header has three pointers which basically form two overlapped Node structs:
struct List {
struct Node* lh_Head;
struct Node* lh_Tail;
struct Node* lh_TailPred;
};
In an empty list, lh_Head points to &lh_Tail, and lh_TailPred points to &lh_Head. The lh_Tail pointer is always null (this is the 'end marker').
In a populated list, lh_Head points to the embedded Node struct of the first list node, and lh_TailPred points to the embedded Node struct of the last list node. The ln_Succ pointer of the last node points to the address of the list header's lh_Tail pointer (...which is always null).
That way you only need an existing node pointer to walk forward and backward, or insert or remove a node. When walking the list by following the succ or pred pointers you know you've reached the end when encountering a null pointer.
Apparently the Linux-style lists in the article require to know the address of the list header to detect when the end is reached which isn't needed for the Amiga style list (at the cos […]
- zahlman
Is this sort of thing no longer part of a standard computer science or software engineering undergrad curriculum?
- eventualcomp
Waiter, waiter! More optimization articles without benchmarks, please!