Chapter F.6: Data Structures Kernels Love§

Authors: Shrey Patel and Jay Patel, Coconut Labs
Book: Think Like an OS. See book/00-INDEX.md

Your data structures course taught you containers that own their contents: you hand a value to a list and the list allocates a node to hold it. The Linux kernel does it the other way around: the node lives inside your struct, and one struct can sit on five lists at once without a single extra allocation. This chapter unfolds that inversion (the intrusive style) then walks the rest of the kernel's standard toolkit: hash tables built from buckets of half-size lists, red-black trees as the ordered map, the maple tree that replaced the VMA rbtree, the xarray behind the page cache, cpumask bitmaps, ring buffers, and per-CPU variables. Both audiences this book serves want the same thing from it. If you are heading for kernel work, kernel/sched/ and mm/ are unreadable without the intrusive style. If you are heading for low-latency work, notice that the two most recent additions here, the maple tree and per-CPU data, both won on cache behavior rather than big-O, and that the chapter ends with a lab where you measure that on your own machine. By the end you can read list_for_each_entry in real kernel code without blinking, and you know which structure you would reach for and why.

The problem§

Every later chapter of this book walks kernel code, and kernel code is saturated with a small set of data structures that almost no CS curriculum teaches in the form the kernel uses them. The scheduler chapter will show you a red-black tree of runnable tasks. The memory chapter will show you a maple tree of virtual memory areas and an xarray of cached file pages. The device chapters will show you structs that are simultaneously on a driver's list, a bus's list, and a global list, iterated with a macro called list_for_each_entry whose three arguments make no sense until you understand container_of.

The gap is specific. University courses teach external containers: ArrayList<Task>, std::vector, Python's list. The container allocates storage; your object goes inside it, or a pointer to your object does. Kernels overwhelmingly use intrusive containers: the linkage pointers are members of your struct, and the "container" is nothing but a head pointer plus arithmetic. If you try to read kernel/sched/ or mm/ with only the external-container mental model, every iteration loop looks like type-punning black magic.

There is also a selection problem. The kernel has roughly eight workhorse structures, each with a sharp niche: unordered membership, keyed lookup, ordered traversal, sparse index-to-pointer mapping, set-of-CPUs, producer/consumer streams, and contention-free counters. Later chapters assume you know which niche is which. This chapter is where you learn it.

Unfolded§

External vs intrusive: who owns the node§

Start with what you already know. An external linked list looks like this: the library defines a node struct holding your data (or a pointer to it), and every insert allocates one.

External (what your courses taught):

  list ──▶ ┌──────────┐    ┌──────────┐    ┌──────────┐
           │ node     │    │ node     │    │ node     │
           │  next ───┼──▶ │  next ───┼──▶ │  next ───┼──▶ NULL
           │  data ─┐ │    │  data ─┐ │    │  data ─┐ │
           └────────┼─┘    └────────┼─┘    └────────┼─┘
                    ▼               ▼               ▼
              ┌─────────┐     ┌─────────┐     ┌─────────┐
              │ your    │     │ your    │     │ your    │
              │ struct  │     │ struct  │     │ struct  │
              └─────────┘     └─────────┘     └─────────┘

Two allocations per element (node + object), two pointer hops per visit, and the node is owned by the container. An intrusive list flips it: the link pointers are embedded in your struct as an ordinary member.

Intrusive (what the kernel does):

  head ──▶ ┌───────────────┐      ┌───────────────┐
           │ struct task   │      │ struct task   │
           │   name        │      │   name        │
           │   prio        │      │   prio        │
           │ ┌───────────┐ │      │ ┌───────────┐ │
           │ │ list_head ─┼─┼───▶ │ │ list_head ─┼─┼──▶ ...
           │ └───────────┘ │      │ └───────────┘ │
           └───────────────┘      └───────────────┘

Three consequences, and they are the whole reason kernels do this:

  1. No per-node allocation. Membership costs zero extra memory operations. This matters enormously in a kernel, where allocation can fail, can sleep, and can deadlock if done in the wrong context (interrupt handlers, for instance, cannot wait for memory). With an intrusive list, once your struct exists, putting it on a list can never fail.
  2. One object, many lists. Embed three list_head members and the same struct sits on three lists simultaneously. A real example: a kernel task is at various times on a runqueue, a wait queue, and its parent's children list. Same task_struct, different embedded nodes.
  3. O(1) removal from anywhere. Given a pointer to the object, you have a pointer to its node (it is a member), and a doubly-linked node can unlink itself without walking the list.

The cost: the linkage points at the member, not at the struct, so iteration needs a way to get from a list_head * back to the enclosing struct. That is container_of, which you built in F.4. Recall the idea: offsetof(type, member) tells you how many bytes into the struct the member lives; subtract that from the member's address and you have the struct's address. In Linux 6.12 it lives in include/linux/container_of.h:

c
#define container_of(ptr, type, member) ({				\
	void *__mptr = (void *)(ptr);					\
	static_assert(__same_type(*(ptr), ((type *)0)->member) ||	\
		      __same_type(*(ptr), void),			\
		      "pointer type mismatch in container_of()");	\
	((type *)(__mptr - offsetof(type, member))); })

The static_assert is a compile-time check that you named a member whose type matches the pointer you passed. It catches the classic bug of doing container_of with the wrong member.

The kernel's list: struct list_head§

The entire definition, from include/linux/types.h in 6.12:

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

That is the whole container. No length field, no data pointer, no head-vs-node distinction in the type system. The design is a circular doubly-linked list with a sentinel: the head is itself a list_head, and an empty list is the head pointing at itself both ways.

Empty:                        Three entries:

  ┌─────────┐                 head ◀──▶ A ◀──▶ B ◀──▶ C ◀──▶ (back to head)
  │  head   │
  │ next ──┐│                 Every node's next and prev are always valid,
  │ prev ──┼┼──▶ itself       no NULL checks anywhere in insert or delete.
  └────────┘│
       ▲────┘

Circularity is not an aesthetic choice. Because no pointer is ever NULL, insertion and deletion have no edge cases: no "am I the first node?" branch, no "am I the last?" branch. Deletion is two stores:

c
entry->prev->next = entry->next;
entry->next->prev = entry->prev;

Iteration is where container_of earns its keep. The kernel defines list_entry as a straight alias (from include/linux/list.h in 6.12):

c
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

and builds the workhorse macro on top of it:

c
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_first_entry(head, typeof(*pos), member);	\
	     !list_entry_is_head(pos, head, member);			\
	     pos = list_next_entry(pos, member))

Read it slowly. pos is a pointer to your struct type. head is the sentinel. member is the name of the embedded list_head field. Each step follows pos->member.next to the next node, then converts node-address to struct-address with container_of. typeof(*pos) (a GCC extension the kernel dialect relies on) means you never spell the struct type out. The macro deduces it from pos. The loop ends when the walk comes back around to the sentinel. Usage reads almost like a for-each in a high-level language:

c
struct task *t;
list_for_each_entry(t, &run_queue, run_node) {
	printk("%s\n", t->name);
}

One subtlety worth knowing now because you will see it in every hot path: the 6.12 insert helper publishes the new node with a special store:

c
	next->prev = new;
	new->next = next;
	new->prev = prev;
	WRITE_ONCE(prev->next, new);

WRITE_ONCE tells the compiler "perform exactly this one store, don't tear it, don't reorder it away". It is the concurrency-aware volatile store you will meet properly in F.7. The order matters too: the new node's own pointers are fully set up before the final store makes it reachable from the list, so a concurrent lockless reader walking next pointers never sees a half-initialized node.

And when a node is deleted with list_del, the kernel does not NULL its pointers. It poisons them, with values from include/linux/poison.h:

c
#define LIST_POISON1  ((void *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x122 + POISON_POINTER_DELTA)

These are non-NULL addresses chosen to fault on dereference. Why not NULL? Because buggy code often checks for NULL and silently skips; a poison value crashes loudly at the exact spot where someone used a node after removing it. Turning "silent corruption" into "immediate loud crash" is a recurring kernel design instinct.

hlist: half the head, same trick§

Hash tables need one list head per bucket, and they need millions of buckets to be cheap. A list_head head costs two pointers; for a table of 2^20 buckets that is 16 MB of heads on a 64-bit machine. So the kernel has a second list flavor, from the same types.h:

c
struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

The head shrinks to one pointer. The trick that preserves O(1) removal is pprev: not a pointer to the previous node, but a pointer to whatever pointer points at me, which is either the previous node's next or the head's first. To unlink, write *pprev = next and you have patched your predecessor without knowing whether it was a node or the head. The cost is that you cannot walk backwards and cannot reach the tail in O(1). Both are irrelevant for hash buckets, which are short and only walked forward.

Hash tables: an array of hlists§

The kernel's basic hash table, include/linux/hashtable.h, is exactly what you would now guess: a power-of-two-sized array of hlist_head buckets. DEFINE_HASHTABLE(name, bits) declares an array of 2^bits empty heads. Insertion hashes the key with hash_32 for keys up to 4 bytes and hash_long for larger ones, then pushes the node onto that bucket's hlist. Lookup is a macro that walks one bucket:

c
#define hash_for_each_possible(name, obj, member, key) \
	hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)

Note the honesty in the name: for_each_possible. Hashing gives you the bucket, not the object. Different keys can share a bucket, so you still compare keys inside the loop. This is the structure you pick when you need average-O(1) lookup by key and do not care about ordering: PID-to-task lookup, file-descriptor tables in various subsystems, all the "find the object for this ID" paths.

Red-black trees: the ordered map§

Some questions need ordered keys: find the smallest, find the neighbor, iterate in sorted order. Hash tables are useless for those, and the kernel reaches for the red-black tree (include/linux/rbtree.h). At concept level, a red-black tree is a binary search tree with a node-coloring rule that keeps it balanced, guaranteeing O(log n) insert, delete, and lookup, with n in the millions still meaning ~20 comparisons. And it is intrusive, exactly like the lists: you embed a struct rb_node in your struct and use container_of (via rb_entry) to get back out. Historically the kernel's rbtree made you write the comparison-and-descent loop for insertion instead of taking a callback, a deliberate trade of ergonomics for speed on hot paths. Since 5.12, rbtree.h also offers rb_add()/rb_find() helpers that take an always-inlined comparison callback; many call sites still hand-roll the descent.

Where it runs in 6.12:

The maple tree: what replaced the VMA rbtree§

In Linux 6.1 (released December 2022), the memory-management subsystem replaced three things (the VMA rbtree, the separate linked list of VMAs, and the VMA cache) with a single new structure: the maple tree, written by Liam Howlett and Matthew Wilcox. In 6.12, struct mm_struct (in include/linux/mm_types.h) holds struct maple_tree mm_mt, and vm_area_struct no longer carries an rb_node for the main VMA tree at all.

Concept level: a maple tree is a B-tree optimized for storing non-overlapping ranges, which is exactly what VMAs are (each VMA covers [start, end) of the address space, and no two overlap). Where an rbtree node holds one entry and two child pointers, a B-tree node holds many entries packed together, so the tree is much shorter and each node fills whole cache lines with useful data instead of pointer-chasing through scattered 24-byte nodes. It is also designed to be RCU-safe, meaning readers can walk it locklessly while a writer modifies it, which serves the long-term goal of reducing contention on mmap_lock, one of the kernel's most contended locks. The lesson to carry: the rbtree lost the kernel's most famous rbtree job not on big-O (both are O(log n)) but on cache behavior, the constant factors that F.1's memory-hierarchy discussion told you dominate real performance.

If you take one sentence out of this chapter and into a job, take that one. It is the sentence behind every "the profiler says this loop is memory-bound" argument you will ever sit in, and the bonus lab at the end of this chapter lets you produce the numbers yourself instead of taking the ranking on faith.

xarray: a giant sparse array of pointers§

Different niche. The key is an index, a dense-ish unsigned long like "page number 0, 1, 2, ... within a file", and the value is a pointer. You want array semantics (load(i), store(i, p)) over an index space too sparse and too huge to actually allocate. That is the XArray (include/linux/xarray.h): it behaves like an automatically resizing array of pointers indexed by unsigned long, implemented as a chunked tree underneath (it is the successor API to the kernel's radix tree, reworked by Matthew Wilcox; unlike the radix tree it also handles its own locking by default). The kernel's own documentation states its most important user plainly: the page cache. Every file's address_space maps file-page-index to the cached page of that file's data through an xarray, so "give me page 4 1 0 7 of this file" is one xarray lookup. When the memory chapters show you the page cache, this is the structure underneath.

Bitmaps and cpumask§

Sets over small dense integer universes need none of the above machinery. One bit per element is unbeatable. The kernel's bitmaps are arrays of unsigned long with helpers in include/linux/bitmap.h and search ops like find_first_bit in include/linux/find.h. The flagship user is cpumask, "which CPUs?" as a set, from include/linux/cpumask_types.h in 6.12:

c
typedef struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); } cpumask_t;

One bit per possible CPU. A machine with 4096 CPUs describes any subset of them in 512 bytes. The set of CPUs a task is allowed to run on, its affinity, is a cpumask. The set of CPUs currently online is a cpumask. "Find me a CPU in this set" is cpumask_first(), which is literally find_first_bit() over the bits, and word-at-a-time bit scanning means checking 64 CPUs per memory read.

Ring buffers§

Producer/consumer streams (logs, trace events, I/O submissions) want a fixed-size buffer that never allocates in the hot path and, ideally, lets the producer and consumer run without taking the same lock. The shape: a power-of-two array with a head index (producer writes, then advances) and a tail index (consumer reads, then advances), both wrapping around.

             tail (consumer)          head (producer)
                 │                        │
                 ▼                        ▼
  ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
  │ .. │ .. │ D3 │ D4 │ D5 │ D6 │ D7 │    │    │    │
  └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
        ◀── consumed ─┘└─── unread ────┘└── free ──▶     (wraps around)

The lock-friendliness comes from ownership discipline: the producer only writes head, the consumer only writes tail, and each only reads the other's index. With careful ordering (F.7's topic), that can need no lock at all. Three places you will meet the shape:

Per-CPU data§

The last structure is barely a structure at all, and it is the most kernel-flavored idea in the chapter. Any variable shared by all CPUs needs synchronization, and even "cheap" atomic counters get expensive when many CPUs update them, because the cache line holding the counter ping-pongs between cores (each writer must yank exclusive ownership of the line from the previous writer). The kernel's answer for statistics, counters, and scratch state: don't share. A per-CPU variable is N copies, one per CPU, each in that CPU's own region of memory.

The this_cpu_* operations (this_cpu_read, this_cpu_write, this_cpu_inc, ...) act on the current CPU's copy. On x86 they compile to a single instruction with a segment-register prefix. The kernel documentation's example is this_cpu_inc(x) becoming inc gs:[x], where the gs segment base points at the current CPU's per-CPU area. One instruction means there is no window between "figure out which CPU I'm on" and "update its counter" for preemption to slip into, so no locking and no preemption-disabling is needed. The trade: reading a total (say, packets received across the system) means summing all N copies. Per-CPU data optimizes writes at the cost of reads, the exact opposite of a shared atomic. Statistics write constantly and read rarely, so the trade is usually a landslide.

The cache-line ping-pong that motivates all of this is not a kernel-only tax. It is the same effect you will measure in F.7's lab, where four threads sharing one atomic counter end up fighting over a single cache line.

The real thing in Linux§

Everything above was verified against the 6.12 tree; here is the map from concept to source file, plus the details worth reading in situ:

The selection table, the thing to actually memorize:

StructureHeader (6.12)Flagship userWhen YOU would pick it
Intrusive list (list_head)include/linux/list.htask lists, wait queues, nearly everythingUnordered membership; iterate-all; O(1) insert/remove; object on several lists at once
hlist + hashtableinclude/linux/hashtable.hID-to-object lookups (PIDs etc.)Keyed lookup, average O(1), no ordering needed
Red-black tree (rb_node)include/linux/rbtree.hscheduler tasks_timeline, hrtimersOrdered keys; min/next/neighbor queries; O(log n)
Maple treeinclude/linux/maple_tree.hVMAs (mm_mt) since 6.1Non-overlapping ranges; RCU readers; cache-hostile rbtree is too slow
XArrayinclude/linux/xarray.hthe page cacheSparse unsigned long index → pointer, array semantics
Bitmap / cpumaskinclude/linux/cpumask.hCPU sets (affinity, online mask)Sets over small dense integer universes
Ring bufferkernel/printk/printk_ringbuffer.c, io_uringdmesg, io_uring SQ/CQ, ftraceProducer/consumer streams; fixed memory; minimal locking
Per-CPU variableinclude/linux/percpu-defs.hstatistics countersWrite-heavy, read-rarely state; kill cache-line ping-pong

Coconut tie-in§

Coconut's new subsystems are consumers of exactly this toolkit: the agent registry in kernel/agent/ needs keyed lookup (hashtable) plus per-agent membership lists in intrusive style, and the 04-HLD audit pipeline (JSON-lines events at high rate) is the textbook ring-buffer-plus-per-CPU-staging shape before records hit the BLAKE3 hash chain. Reviewing agent_spawn/agent_attest paths in the 6.12 fork means reading list_for_each_entry, container_of, and rbtree walks fluently; this chapter is that fluency.

Lab§

Environment: Docker Linux container for compile/run; files authored on the macOS host. (Everything here is portable C, but we standardize on Linux gcc so the output matches.) Part 1 is short enough to type rather than paste, and the offsets you predict are the whole exercise.

sh
mkdir -p ~/f6lab && cd ~/f6lab

Part 1: build the intrusive list. Create ilist.h:

c
#ifndef ILIST_H
#define ILIST_H
#include <stddef.h>

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

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

#define ILIST_HEAD(name) struct ilist_head name = { &(name), &(name) }

static inline void ilist_add_tail(struct ilist_head *n, struct ilist_head *head)
{
	n->prev = head->prev;
	n->next = head;
	head->prev->next = n;
	head->prev = n;
}

static inline void ilist_del(struct ilist_head *e)
{
	e->prev->next = e->next;
	e->next->prev = e->prev;
	e->next = e->prev = 0;      /* the kernel poisons instead - see Part 2 */
}

#define ilist_entry(ptr, type, member) container_of(ptr, type, member)

#define ilist_for_each_entry(pos, head, member)                              \
	for (pos = ilist_entry((head)->next, __typeof__(*pos), member);      \
	     &pos->member != (head);                                         \
	     pos = ilist_entry(pos->member.next, __typeof__(*pos), member))
#endif

Create main.c, one struct type on two lists at once:

c
#include <stdio.h>
#include "ilist.h"

struct task {
	char name[8];
	int  prio;
	struct ilist_head all_node;   /* linkage for the "all tasks" list */
	struct ilist_head run_node;   /* linkage for the "runnable" list  */
};

int main(void)
{
	ILIST_HEAD(all_list);
	ILIST_HEAD(run_list);
	struct task a = { "alpha", 1 }, b = { "beta", 2 }, c = { "gamma", 3 };
	struct task *t;

	ilist_add_tail(&a.all_node, &all_list);
	ilist_add_tail(&b.all_node, &all_list);
	ilist_add_tail(&c.all_node, &all_list);
	ilist_add_tail(&a.run_node, &run_list);   /* only a and c runnable */
	ilist_add_tail(&c.run_node, &run_list);

	printf("offsetof(all_node)=%zu offsetof(run_node)=%zu\n",
	       offsetof(struct task, all_node), offsetof(struct task, run_node));

	printf("all: ");
	ilist_for_each_entry(t, &all_list, all_node) printf("%s ", t->name);
	printf("\nrun: ");
	ilist_for_each_entry(t, &run_list, run_node) printf("%s ", t->name);

	ilist_del(&c.run_node);                   /* c stops running... */
	printf("\nafter del: run: ");
	ilist_for_each_entry(t, &run_list, run_node) printf("%s ", t->name);
	printf("| all: ");
	ilist_for_each_entry(t, &all_list, all_node) printf("%s ", t->name);
	printf("\n");
	return 0;
}

Predict before running: (1) the two offsets. Struct layout is char[8] then int, then the nodes, so where does all_node start? (2) after ilist_del(&c.run_node), is gamma still on the all list? Now run:

sh
docker run --rm -v "$PWD":/lab -w /lab gcc:14 \
    sh -c 'gcc -Wall -O2 -o lab main.c && ./lab'

Expected:

offsetof(all_node)=16 offsetof(run_node)=32
all: alpha beta gamma
run: alpha gamma
after del: run: alpha | all: alpha beta gamma

Check your predictions: all_node lands at 16, not 12, because the pointer members force 8-byte alignment (F.3's padding rules). And gamma survives on the all list, because deleting from one list never touches the other list's node. That independence is the multi-list property.

Part 2: read the real one and account for every difference.

sh
curl -sO https://raw.githubusercontent.com/torvalds/linux/v6.12/include/linux/list.h
grep -n "WRITE_ONCE\|LIST_POISON\|__list_add_valid" list.h | head -20

Walk list.h next to your ilist.h and account for each delta: (1) INIT_LIST_HEAD and __list_add use WRITE_ONCE, a single-store publish for lockless concurrent readers, which your single-threaded version doesn't need; (2) list_del sets LIST_POISON1/LIST_POISON2 instead of your zeros, giving crash-on-use-after-del rather than maybe-silently-skip; (3) __list_add_valid/__list_del_entry_valid are hardening hooks that check pointer consistency before mutating; (4) the entire second half of the file is the hlist_* family from this chapter. If you can justify all four, you can read any list code in the tree.

Bonus: cache behavior, intrusive vs pointer-array. Create bench.c: allocate 1<<20 nodes, then sum a field three ways. First, a contiguous array walked by index. Second, an array of pointers to individually-malloc'd, address-shuffled nodes. Third, an intrusive list threaded through those same shuffled nodes. Time each with clock_gettime(CLOCK_MONOTONIC, ...). Predict the ranking first. Expected: the contiguous array wins big (perfect prefetch), and both pointer-chasing variants land within sight of each other but several times slower. The scattered node placement, not the list-vs-array API, is what murders the cache. That is the maple-tree lesson from this chapter measured on your own machine, and it ties straight back to the memory-hierarchy chapter: intrusive lists win on allocation and multi-membership, while B-tree-style packing wins on traversal locality.

One line of edit buys the next data point. Rerun the benchmark with the nodes allocated contiguously instead of shuffled, so the list threads through neighbors rather than scattered addresses. The API has not changed and the big-O has not changed; only the placement has. Whatever the gap does is your own measurement of the argument this chapter has been making since the maple tree.

What you can do now: open kernel/sched/ or mm/ in the 6.12 tree, find a list_for_each_entry, and say out loud which struct it walks and which of that struct's embedded nodes it follows. That one sentence is the entire intrusive style, and Chapters 9 and 11 assume you can produce it without stopping.

Bridge notes§

You know rbtrees, hash tables, and ring buffers from coursework. Skim those subsections for the kernel-specific flavor only (rb_root_cached, buckets-of-hlists, pprev). Four things are genuinely new even with MS-level background. (1) The intrusive style itself: container_of-based iteration, zero-allocation membership, one object on N lists. Internalize list_for_each_entry until it reads as plain English. (2) The maple tree, which post-dates most curricula (merged 6.1) and is the current answer for VMA-style range indexing. Note why it beat the rbtree: cache-line economics, not asymptotics. (3) The XArray as the page-cache index. If you learned "radix tree" for this role, update: same lineage, new API, internal locking. (4) Per-CPU data and the single-instruction this_cpu_* ops, a locking-avoidance idiom with no userspace-coursework equivalent. Also worth 60 seconds even for veterans: the WRITE_ONCE publish ordering in __list_add and the poison-on-delete convention. Both are idioms you must recognize on sight in kernel review.

Sources§