A normal linked list owns its nodes: push(list, obj) allocates a node, points it at your object, links it in. The Linux kernel — which keeps every task, timer, inode, and network buffer on lists, and manipulates them millions of times per second — does the opposite: the node lives inside your object, and the “list library” is thirty lines of pointer math that has no idea your object exists. I wrote a standalone library around this pattern to have it outside kernel code; the design is worth knowing even if you never use mine, because it deletes three problems at once.

The Shape

c
struct list_head { struct list_head *next, *prev; };

struct task {
    int   pid;
    struct list_head run_node;    /* membership in the run queue */
    struct list_head all_node;    /* membership in the global task list */
};

The list is list_heads linked to list_heads — a circular doubly linked chain threading through your objects. Insert and remove take the embedded node directly; no allocation, no lookup, O(1), can’t fail:

c
list_add(&t->run_node, &runqueue);
list_del(&t->run_node);           /* no search — you already hold the node */

The puzzle is the other direction: given a list_head * from traversal, where is the task it lives inside? At a fixed, compile-time-known offset — subtract it:

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

struct task *t = container_of(pos, struct task, run_node);

container_of looks like a pointer crime, but offsetof is standard C and the arithmetic is exact. This macro is load-bearing across the entire kernel — lists, rbtrees, hlist hash chains, work items all use embedded nodes and recover their containers this way.

What the Pattern Buys

No per-node allocation. External lists malloc a node per element — a latency cost, a failure path, and heap scatter. Intrusive membership is allocated with the object, so linking can’t fail and can run in contexts where allocation is illegal (interrupt handlers — not a coincidence this is the kernel’s idiom). Allocator free-lists exploit the degenerate case: the freed memory is the node.

Cache locality where it counts. Traversal touches your object anyway; the links arrive on the same cache line as the fields you’re reading (you choose the neighborhood — put the node next to the hot fields; pahole is your layout auditor). An external list pays a separate miss per node before even reaching the object.

Multi-membership without multiplication. A task is on the run queue, a wait queue, its parent’s children list, and the global list — four list_heads in one struct, one object, zero duplication. With external containers that’s four node allocations pointing at one object and a lifetime-coordination headache. Which leads to the real discipline the pattern demands: lifetime is yours now. The list doesn’t own anything, so freeing an object still linked somewhere leaves dangling prev/next in the chain — the classic kernel use-after-free shape. The kernel’s answers are worth copying: list_del poisons the removed node’s pointers (LIST_POISON1/2 — a crash at the bug instead of downstream), objects with multiple memberships carry refcounts, and CONFIG_DEBUG_LIST validates prev/next consistency on every operation.

The costs are symmetrical and honest: one struct can only be on one list per embedded node (add members deliberately); the object’s type must be known to recover it (this is a monomorphic pattern — heterogeneous lists need a type tag or vtable anyway); and your public headers now expose the node member, coupling layout to the containers used. C++ has the same trade productized as boost::intrusive, and every serious allocator, runtime, and game engine has a hand-rolled equivalent.

Takeaways

  • Intrusive = node inside the object; container_of/offsetof recovers the object from the node with exact, legal arithmetic.
  • Wins: zero allocations (unfailable insert, interrupt-safe), links on the object’s cache line, cheap membership in many lists at once.
  • Cost: the container no longer manages lifetime — poison on delete, refcount shared objects, turn on debug checks.
  • The pattern generalizes past lists: kernel rbtrees, hash chains, and work queues all embed nodes the same way.
  • Reach for it when allocation is forbidden, elements live on multiple structures, or per-node mallocs show up in profiles.