Intrusive Linked Lists: Embedding the Link in the Payload

A conventional linked list allocates a node per element and stores a pointer to the payload inside it. The node is a separate object with its own lifetime, and every insertion costs an allocation. An intrusive list reverses the arrangement: the link fields live inside the payload, and the list does not own the elements at all. The container holds pointers into objects it did not create, and the objects know they are linked.

That inversion is why the pattern dominates kernel code and real-time systems. It is also why it confuses programmers trained on std::list, because the ownership model, the type model, and the failure modes are all different.

The allocation the pattern removes

Consider a queue of 4096-byte I/O buffers. A conventional implementation defines a node that holds a buffer * and a next, allocates one node per enqueue, and frees it on dequeue. That is one allocation and one free per operation, each of which must be accounted for in the allocator’s metadata and each of which can fail.

An intrusive implementation stores the link fields inside the buffer structure itself:

struct buf {
    void  *data;          /* 4096-byte payload elsewhere */
    size_t len;
    struct buf *next;     /* link, used only while queued */
};

struct queue {
    struct buf *head;
    struct buf *tail;
};

Enqueue is now pointer arithmetic with no allocation, and it cannot fail:

void enqueue(struct queue *q, struct buf *b) {
    b->next = NULL;
    if (q->tail) q->tail->next = b;
    else q->head = b;
    q->tail = b;
}

The saving is one allocation per element, which is a constant factor rather than a complexity change, and in allocator terms it is a saving of a whole metadata block plus the fragmentation that comes with interleaving small nodes among large buffers. In a system where the allocation path can block, take a lock, or fail, removing it from the queue operation changes the set of conditions the caller must handle. That is the real argument, more than the byte count.

The cost is that the next pointer is present in every buffer whether or not the buffer is ever queued, and that a buffer can be on at most one such list at a time unless it carries multiple link fields. Both consequences are usually acceptable because the payload is already large.

Recovering the payload from the link

The moment the link lives inside the payload, the list’s cursor is a pointer to a field, not to the object. Something must convert back. In C this is done by subtracting the field’s offset from its address, and the standard idiom wraps that arithmetic:

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

offsetof is defined in <stddef.h> and yields the byte offset of a member within its struct as a size_t. Subtracting it from the address of the member gives the address of the enclosing object, assuming the member really is embedded in an object of that type. Nothing checks that assumption. A cursor built from a different struct that happens to place a compatible link at the same offset will convert to the wrong type and the compiler will not object.

This is why intrusive list APIs are usually macros rather than functions. A function taking struct list_head * cannot know the enclosing type, so either the caller passes the offset and type explicitly, or the API expands per type. The Linux kernel’s list_entry is the accessor built on that expression: it takes a list_head pointer, the enclosing type, and the member name, and expands to the offset subtraction.

In C++ the same recovery is done with static_cast on a pointer to member, or with a link base class and static_cast down. Both are legal only when the object really is of the derived type, and both have the same unchecked character. A reinterpret_cast that crosses to an unrelated type is undefined behaviour, which matters for optimisers that assume the cast is consistent.

One object, several lists

Because each link field is a separate member, an object can be linked into several independent structures simultaneously, each with its own anchor. A kernel object might sit on an LRU list, a superblock list, and an alias chain at the same time, and the link fields for those lists are distinct members.

struct inode {
    /* ... */
    struct list_head i_lru;      /* LRU ordering */
    struct list_head i_sb_list;  /* all inodes of a superblock */
    struct list_head i_dentry;   /* alias chain */
};

Each list_head is 16 bytes on a 64-bit target (two 8-byte pointers), so three members cost 48 bytes in a struct that is already hundreds of bytes. The discipline is that a node is unlinked from one list before being linked into another that shares the same field, and that no field is ever linked twice. The kernel’s list primitives do not enforce either rule. Linking an already-linked node produces a ring that includes the old position and corrupts both lists, and the corruption usually surfaces much later as a hang during traversal.

Some implementations add a debug mode that poisons the link pointers on unlink so that a second unlink faults immediately, and some track the owning list in the node. Neither is free, and both are usually compiled out of the fast path.

Ownership is the design decision

The central question an intrusive list forces is who frees the element. The list cannot do it, because it does not know how the element was allocated, or whether it was allocated at all. Elements are often statically allocated, carved from a slab, or embedded in a larger structure, and free on any of those is wrong.

This has three consequences that shape real code.

The list is a view, not a container. Its lifetime is independent of its elements, and the elements’ lifetime is independent of the list. A structure can be removed from a list, kept alive by another reference, and reinserted later. This is what makes intrusive lists usable for caches and for structures that migrate between owners.

Destruction is explicit. Clearing a list must unlink each element and let the owner dispose of it. There is no destructor that walks and frees. Code that forgets leaves elements linked to a dead anchor, which is the intrusive equivalent of a memory leak and is harder to find because the element is still reachable through the stale link.

Iteration must tolerate concurrent unlink. Since unlink does not free, a traversal that removes the current element and continues is safe as long as it saved the successor. The list_for_each_safe variant exists for that reason, and the naming convention is a warning: the plain loop is invalidated by removal of the current node.

Cache behaviour of the embedded link

Embedding the link in the payload changes the memory access pattern in a way that is easy to underestimate. With a separate node, a traversal touches the node (16 or 24 bytes) and then, if it needs the payload, touches a second allocation. That is two cache lines per element in the worst case. With an intrusive link, the link is inside the payload’s allocation, so the traversal touches the payload’s line and the payload is already there.

For a queue where the consumer reads a header field out of each element, that halves the number of distinct lines touched per element. It does not remove the pointer chase; the successor address is still data-dependent and the prefetcher still cannot follow it. The improvement is in lines per element, not in the dependency structure, which is why Unrolled Linked Lists remain the answer for traversal-bound workloads.

There is a counter-effect when the payload is large and the traversal only needs the link. An intrusive list forces the traversal to pull in a whole payload line to read eight bytes of pointer. A separate node would keep the links dense and the payload untouched. The rule of thumb is that intrusive links help when the consumer needs the payload anyway and hurt when it does not.

Where the pattern is inappropriate

Intrusive lists are a poor fit for several situations, and recognising them avoids most of the pain.

• Elements with multiple concurrent memberships in the same list. A single link field permits one position per list. A structure that must appear twice in the same ordering, such as a task with two priorities, needs two fields or a different structure.
• Shared or immutable payloads. If two owners share one element, neither can safely modify its link field. Intrusive linking requires unique ownership of the link even when the payload is shared.
• Elements of foreign type. A library cannot require that caller objects embed its link type. This is the reason generic containers use wrapper nodes.
• Copyable values. An intrusive element cannot be copied by value while linked, because the copy’s link would point into the original’s neighbours and the original would still be in the list. Value semantics and intrusive links are incompatible; the pattern requires reference semantics.

The pattern’s natural home is a system with a single allocator discipline, known object layouts, and a need to link existing objects without allocating. Outside those conditions, the separate-node list is simpler and the extra allocation is usually affordable.

A complete minimal anchor

The smallest useful intrusive list is a circular doubly linked anchor with a single element type. The following is complete and compiles as C99:

#include <stddef.h>

struct link { struct link *prev, *next; };

static void link_init(struct link *l) { l->prev = l->next = l; }

static void link_insert(struct link *pos, struct link *n) {
    n->prev = pos->prev;
    n->next = pos;
    pos->prev->next = n;
    pos->prev = n;
}

static void link_remove(struct link *n) {
    n->prev->next = n->next;
    n->next->prev = n->prev;
    n->prev = n->next = n;   /* self-linked: detects double removal */
}

#define link_entry(l, T, m) ((T *)((char *)(l) - offsetof(T, m)))

The self-link on removal is the cheapest available precondition check: after a removal the node points at itself in both directions, and a second link_remove on that node writes to its own fields and leaves it isolated rather than splicing it into a list it no longer belongs to. That keeps the corruption local, and code that iterates an anchor can still notice a node that is not reachable from it. It does not make double removal correct.

An anchor embedded in a struct, rather than allocated, means the list header is part of whatever object owns the list, so the header’s lifetime is the owner’s lifetime and no separate free is required. That is the same sentinel trick described in Doubly Linked Lists and the Sentinel Header, applied one level up: the anchor is a sentinel that is also the container.