# Intrusive Lists: How the Kernel Does Data Structures

> The Linux kernel's list_head puts the container inside the object instead of the object inside the container — one implementation, zero allocations, and a container_of macro that looks illegal but isn't. I built a library around the pattern; here's why it wins.

URL: https://harshith.in/blog/intrusive-lists/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: systems, memory, kernel

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](https://harshith.in/projects/generic-dll-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_head`s linked to `list_head`s — 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_head`s 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.