Reading the OpenSolaris Kernel: A Linked List Worth Studying
Practical lessons in software design from the OpenSolaris kernel
Today we are looking at the OpenSolaris kernel, and we are analyzing an implementation of a linked list.
Most programmers are first introduced to linked lists in a classroom setting: a small struct with a next pointer, perhaps followed by a prev pointer, and a few insertion and deletion functions written by the professor on a whiteboard. Those examples are useful, but they are not how the idea becomes real-world-truly-interesting. To see this, study a linked list in a real operating system - albeit a dead one.
The OpenSolaris kernel offers exactly that: a generic linked list implementation that is compact, carefully crafted, and revealing. It lives in usr/src/uts/common/sys/list_impl.h and usr/src/uts/common/os/list.c, and it truly rewards slow reading.
The first surprise is that the list is intrusive. In a textbook implementation, the list node often wraps the payload: a node contains data and links. Here, the payload object only contains the links. The fundamental node type is only this:
struct list_node {
struct list_node *list_next;
struct list_node *list_prev;
};
And the list itself looks like this:
struct list {
size_t list_size;
size_t list_offset;
struct list_node list_head;
};
That list_offset field is the key to the whole design. It tells the list code where, inside a larger object, the embedded list_node lives. This allows the same implementation to manage lists of many different object types without allocating wrapper nodes. In kernel code, that is an excellent trade: fewer allocations, less indirection, and tighter control over memory layout.
Once you understand that design, two small macros become the bridge between “user object” and “list node”:
#define list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset))
#define list_object(a, node) ((void *)(((char *)node) - (a)->list_offset))
The first takes an object and finds its embedded link field. The second takes a link field and reconstructs the object that contains it. This is a classic systems-programming move: keep the abstraction generic, but make the cost explicit and low.
The second thing worth noticing is the use of a sentinel head node. When the list is created, the head’s next and prev pointers both point back to the head itself:
list->list_head.list_next = list->list_head.list_prev = &list->list_head;
This means an empty list is represented not by a NULL, but by a tiny circular structure. That choice simplifies the rest of the code - insertion and removal do not need separate “empty list” logic and head & tail operations become ordinary pointer updates around the sentinel.
The insertion code is a nice example of how much clarity can fit in a few lines. Here is the essence of inserting after a node:
lnew->list_prev = node;
lnew->list_next = node->list_next;
node->list_next->list_prev = lnew;
node->list_next = lnew;
This is the kind of source code worth reading - it is short, but it encodes a structural invariant: every forward link must have a matching backward link, and every update must preserve that symmetry. There are only four assignments.
Removal is equally direct:
node->list_prev->list_next = node->list_next;
node->list_next->list_prev = node->list_prev;
node->list_next = node->list_prev = NULL;
The last line is especially telling. The implementation deliberately clears the removed node’s pointers. That is not strictly necessary for the list to function, but it is good engineering practice. A removed node is now visibly inactive. If somebody tries to remove it again, or mistakes it for a live element - the bug would be easier to detect.
Traversal is built on the same sentinel idea. Internally, the list is circular. Externally, the API presents a simpler interface: once iteration reaches the head again, it returns NULL. So client code gets the clean, familiar form:
for (p = list_head(listp); p != NULL; p = list_next(listp, p)) {/* use p */}
That pattern appears in real OpenSolaris code. In pci_boot.c, for example, the kernel walks a list of cached PCI unit-address entries using list_head() and list_next(). This is such simple abstraction!
What, then, does this implementation teach us about linked lists?
First, linked lists are less about the shape of a node than about the invariants that govern mutation. Good list code makes those invariants easy to see and hard to violate.
Second, production systems code often chooses intrusive structures because they are efficient and flexible. A beginner may think of this as an advanced trick but in reality, it is an expression of a basic principle: put the machinery where it costs the least.
Third, elegance in low-level code often means removing special cases. The sentinel node is not decorative. It exists because it simplifies every operation around it.
And finally, reading code like this reminds us that “data structures” are not just academic exercises. In a kernel, a linked list is not there to illustrate a concept. It is there because someone needed a generic, reusable, predictable mechanism, and this was the design that best satisfied those constraints.
If you want to get better at reading systems software, this is an ideal specimen. Start with the structures. Then read the conversion macros. Then insertion, removal, and traversal. With this you learn more than just how a linked list works - you get an intuition of how experienced engineers turn a familiar idea into robust infrastructure.
