How the Kernel Does Linked Lists: Intrusive Nodes and container_of

The textbook linked list node looks like this:

struct node {
    void *data;       // points at your actual object
    struct node *next;
};

To put an object in the list, you allocate a node, point its data at your object, and link it in. Every insertion is a malloc. Every traversal is a pointer chase to data and then a cast. And an object can only really live in one such list at a time without a tangle of bookkeeping.

The Linux kernel does it the other way around, and once you see it you cannot unsee it. The link does not point at your struct. The link lives inside your struct.

The link goes in the object

typedef struct list_node {
    struct list_node *prev, *next;
} list_node;

struct task {
    int pid;
    list_node run_queue;  // the link is a field
    list_node timer_list; // and you can have more than one
};

A task carries its own list links as ordinary fields. To put a task on the run queue, you splice its embedded run_queue node into the list. No allocation happens, because the node was already part of the object you already had. And because a struct can hold several link fields, the same task can be on the run queue and a timer list and a hash bucket simultaneously, each through a different embedded node. That is impossible to do cleanly with the textbook design and trivial here.

But how do you get the object back?

Here is the puzzle. When you walk the list, you have a list_node *, a pointer to the link field. You need the task that contains it. The link does not point back to the object, so how do you recover it?

You recover it with arithmetic. You know the type of the container and the name of the field, so the compiler knows the field's byte offset within the struct. Subtract that offset from the node pointer and you land on the start of the container:

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

// walking a list of tasks:
for (list_node *p = head->next; p != head; p = p->next) {
    struct task *t = container_of(p, struct task, run_queue);
    // ... use t->pid ...
}

offsetof(struct task, run_queue) is the distance, in bytes, from the top of a task to its run_queue field. A list_node * points at that field; subtract the offset and you are pointing at the task. Cast and done. This one macro is the keystone of the entire design, and it appears, by exactly this name, thousands of times in the kernel source.

The circular sentinel that kills edge cases

The other elegant trick is the head. It is not a null-terminated chain; it is a circular list with a sentinel node that links to itself when empty:

void list_init(list_node *head) { head->next = head; head->prev = head; }
bool list_empty(const list_node *head) { return head->next == head; }

void list_remove(list_node *n) {
    n->prev->next = n->next;   // no NULL checks needed
    n->next->prev = n->prev;
    n->prev = n->next = n;     // safe to remove again
}

Because every node, including the head, always has a real prev and next (the empty list's head points at itself), insertion and removal are branch-free. There is no "is this the first element" or "is this the last element" special case, no NULL checks scattered through the splice logic. An empty list is just a sentinel pointing at itself, and a one-line list_remove works whether the node is at the front, the back, or the middle. Fewer branches means fewer bugs and faster code, which matters when you are the kernel doing this millions of times a second.

Why it is worth knowing

• Zero allocation for membership. Putting an object in a list never calls the allocator, because the list machinery is already inside the object. In a context where allocation is expensive or forbidden, that is the difference between possible and not.
• One object, many lists. Multiple embedded link fields let the same object participate in several independent lists at once, which real systems constantly need.
• container_of is a transferable trick. The "store a generic node inside a typed struct and recover the struct by offset" pattern shows up far beyond lists: intrusive trees, hash tables, and any C code that wants generic containers without void * and casts everywhere.

Intrusive lists feel like a magic trick the first time, and then they feel like the obvious way to do it. The kernel has known this for decades. The whole secret is putting the link where the data already is, and doing a little subtraction to find your way home.

Build it yourself. Solve the Intrusive Linked List challenge on barehands and get graded on correctness and speed. No libraries, just cc -std=c11.