Kernel Data Structures

In a typical user-space program you might write std::list<Process*> — the list contains pointers to your objects. The list node is external to the process struct; it holds a pointer back to the data. This is called a non-intrusive (or external) container.

The kernel takes the opposite approach. Instead of a list that contains pointers to struct task_struct, the struct task_struct contains a list node inside itself. The bookkeeping is embedded directly in the object. This is called an intrusive container.

Why does this matter so deeply?

1. No extra allocation. Each non-intrusive list node requires a heap allocation for the node itself, separate from the data. In the kernel, allocations are expensive, can fail, and in some contexts (interrupts, NMI handlers) are simply forbidden. An intrusive list has zero additional allocation overhead — the node comes free with the object.

2. Better cache behavior. When you iterate a non-intrusive list, you dereference the list node to get a pointer, then dereference the pointer to get the data — two pointer chases, likely two cache misses. With an intrusive list, the node and the data are in the same allocation, so reaching the data is free once you have the node.

3. An object can belong to multiple lists simultaneously. A struct page in the kernel has several list_head fields: one for the LRU list, one for the buddy allocator free list, one for a memory cgroup. A non-intrusive container cannot do this without multiple external nodes. An intrusive struct just carries multiple embedded list nodes.

4. Type safety through container_of. As you will see in the next concept, C macros give you back type-safe access to the enclosing object from any embedded node — a surprisingly elegant solution given C's limited type system.

The trade-off: intrusive containers couple the object to the container. A plain integer cannot be put in an intrusive list without wrapping it. But kernel objects are always structs, and this trade-off pays handsomely.

/* Non-intrusive (user-space style) — kernel does NOT do this */
struct list_node_external {
    struct task_struct *data;   /* pointer to the real object */
    struct list_node_external *next;
    struct list_node_external *prev;
};

/* Intrusive (kernel style) — list node lives INSIDE the object */
struct task_struct {
    /* ... hundreds of fields ... */
    struct list_head run_list;   /* embedded in the object itself */
    struct list_head tasks;      /* another list, same object! */
    /* ... */
};

The kernel's foundational list implementation lives in include/linux/list.h. The key type is struct list_head, which is breathtakingly simple:

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

That is the entire type. No data field. No type parameter. Just two pointers.

Every list is represented as a circular doubly-linked list with a sentinel head node. The head node's next points to the first real element; its prev points to the last. An empty list has both pointers pointing back to the head itself.

Why circular? Circular lists eliminate special cases. Insertion at the tail is O(1) because head->prev always points to the last node. Deletion of any node is O(1) without knowing whether it's the head or tail. Iteration from either end is symmetric.

Initialization uses INIT_LIST_HEAD(&mylist) to set both pointers to &mylist (the empty-list state), or the static initializer LIST_HEAD(mylist) which declares and initializes in one shot.

Core operations:

• list_add(new, head) — insert after head (prepend = stack push)
• list_add_tail(new, head) — insert before head (append = queue enqueue)
• list_del(entry) — remove an entry, sets its pointers to LIST_POISON1/2 (catches use-after-free bugs)
• list_empty(head) — check if empty
• list_move(list, head) — atomic remove + re-insert

Iteration is done with list_for_each_entry, which under the hood uses container_of (next concept) to recover the enclosing struct from each list_head node encountered.

#include <linux/list.h>
#include <linux/slab.h>

struct my_item {
    int value;
    struct list_head node;   /* embedded list node */
};

/* Declare and initialize a list head */
static LIST_HEAD(my_list);

void demo_list(void)
{
    struct my_item *item, *tmp;

    /* Allocate and add three items */
    for (int i = 0; i < 3; i++) {
        item = kmalloc(sizeof(*item), GFP_KERNEL);
        item->value = i * 10;
        list_add_tail(&item->node, &my_list); /* append */
    }

    /* Iterate safely (safe = allows deletion during iteration) */
    list_for_each_entry_safe(item, tmp, &my_list, node) {
        pr_info("value: %d\n", item->value);
        if (item->value == 10) {
            list_del(&item->node);
            kfree(item);
        }
    }
}

Here is the central puzzle: you are iterating a list. You have a pointer to a struct list_head. But you need a pointer to the struct my_item that contains that list_head. How do you get from the embedded member back to the enclosing object?

The answer is container_of, one of the most important macros in the kernel:

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

Let's unpack this piece by piece.

offsetof(type, member) is a standard C macro that returns the byte offset of member within type. For example, if struct my_item is laid out in memory as [value:4 bytes][padding:0 bytes][node:16 bytes], then offsetof(struct my_item, node) is 4.

Now: if you have a pointer ptr that points to the node field, and you know the field starts 4 bytes into the struct, then subtracting 4 from ptr gives you a pointer to the start of the enclosing struct my_item. That is exactly what container_of does: it casts ptr to char * (so pointer arithmetic works in bytes), subtracts the offset, and casts back to type *.

An analogy: imagine a hotel room key that says "Room 205". The key is the list node. You know the key is always found 4 meters down the hallway from the room entrance. So if you find the key hanging in the hallway, you walk 4 meters back and you find the room. container_of is that "walk back" operation.

In a type-safe modern version, the kernel uses a __same_type check (via __builtin_types_compatible_p) to ensure ptr is actually a pointer to the declared member type, catching subtle bugs at compile time.

list_for_each_entry(pos, head, member) is essentially:

for (pos = container_of(head->next, typeof(*pos), member); \
     &pos->member != head; \
     pos = container_of(pos->member.next, typeof(*pos), member))

This single macro, built on container_of, lets one generic list implementation work for any struct type in the entire kernel without templates, generics, or runtime polymorphism. It is pure C, zero overhead, fully type-safe.

#include <stddef.h>   /* offsetof */

struct my_item {
    int   value;
    char  name[16];
    struct list_head node;  /* at offset = offsetof(struct my_item, node) */
};

void example_container_of(struct list_head *ptr)
{
    /* Recover the enclosing struct from a pointer to the embedded node */
    struct my_item *item = container_of(ptr, struct my_item, node);

    pr_info("value=%d name=%s\n", item->value, item->name);

    /*
     * What happened in memory:
     *
     *  &my_item   &my_item.node
     *      |           |
     *      v           v
     *  +-------+------+----------+
     *  | value | name |   node   |
     *  +-------+------+----------+
     *  ^----- offsetof ---------^
     *
     * ptr - offsetof(struct my_item, node) == &my_item
     */
}

A regular list_head uses two pointers per node (8 bytes each on a 64-bit system = 16 bytes). For a hash table with thousands of buckets, most of which are empty or have one element, storing 16 bytes per bucket just for the sentinel head is wasteful.

The kernel provides struct hlist_head and struct hlist_node for this purpose. The head is only one pointer (8 bytes), and the doubly-linked-ness is achieved with a clever trick: instead of prev pointing to the previous node, it points to the pprev field — a pointer to the next pointer of the previous node (or of the head itself). This pointer-to-pointer trick allows O(1) deletion without a full prev pointer in the head.

DECLARE_HASHTABLE(name, bits) declares a hash table with 2^bits buckets. hash_add, hash_del, and hash_for_each / hash_for_each_possible round out the API.

When to use hlist vs list: use hlist whenever you have a large array of list heads (hash buckets, per-slot lists) where minimizing the per-head memory cost matters. Use list for all other purposes.

Hash function: the kernel provides hash_32 / hash_64 (based on the Knuth multiplicative hash) and hash_ptr for pointer hashing. Always hash before using as an index; never use raw values modulo table size, as this produces terrible distribution for common value patterns.

#include <linux/hashtable.h>

/* Declare a hash table with 2^8 = 256 buckets */
DECLARE_HASHTABLE(pid_table, 8);

struct pid_entry {
    pid_t           pid;
    char            comm[16];
    struct hlist_node node;  /* embedded hlist node */
};

void hashtable_demo(void)
{
    struct pid_entry *e, *tmp;
    struct pid_entry *entry = kmalloc(sizeof(*entry), GFP_KERNEL);

    hash_init(pid_table);

    entry->pid = 1234;
    strncpy(entry->comm, "bash", 16);
    /* hash_add hashes the key and picks the right bucket */
    hash_add(pid_table, &entry->node, entry->pid);

    /* Look up entries with key 1234 */
    hash_for_each_possible(pid_table, e, node, 1234) {
        if (e->pid == 1234)
            pr_info("found: %s\n", e->comm);
    }

    /* Iterate ALL entries */
    unsigned bkt;
    hash_for_each_safe(pid_table, bkt, tmp, e, node) {
        hash_del(&e->node);
        kfree(e);
    }
}

Hash tables give O(1) average-case lookup but no ordering. When you need to iterate over objects in sorted order, or find the nearest object to a given key, you need a balanced binary search tree.

The kernel uses red-black trees (include/linux/rbtree.h). A red-black tree is a self-balancing BST where each node is colored red or black, with invariants that guarantee the tree height is at most 2 log₂(n). This means worst-case O(log n) for insert, delete, and lookup — guaranteed, not just average.

The kernel's rbtree is also intrusive. You embed struct rb_node in your struct, and the tree is anchored by struct rb_root. Unlike the linked list API, the kernel's rbtree API is deliberately low-level: the kernel does not provide a generic rb_insert function. Instead, you write your own insertion function that does the BST walk with your key comparison logic, and then calls rb_link_node and rb_insert_color to fix up colors. This design is intentional — it avoids a function pointer callback and keeps the comparison inline for maximum performance.

Why red-black trees specifically? AVL trees are more rigidly balanced (height ≤ 1.44 log n vs RB's 2 log n) so they have faster lookups, but they require more rotations on insert/delete. Since the kernel's workloads (CFS scheduler, virtual memory areas, file range locks) involve many inserts and deletes, RB trees win overall. The CFS scheduler famously uses an RB tree to pick the next task to run in O(log n) — the leftmost node (smallest virtual runtime) is cached for O(1) access.

Augmented RB trees (rbtree_augmented.h) let you store additional derived data in each node (e.g., the max endpoint in a subtree for interval trees). The memory management subsystem uses augmented RB trees for the vm_area_struct interval tree that maps virtual address ranges.

#include <linux/rbtree.h>

struct interval {
    unsigned long start;
    unsigned long end;
    struct rb_node node;   /* embedded RB node */
};

static struct rb_root root = RB_ROOT;

/* Caller must write the BST walk + call rb_link_node + rb_insert_color */
void rb_insert_interval(struct interval *new)
{
    struct rb_node **link = &root.rb_node;
    struct rb_node  *parent = NULL;

    while (*link) {
        struct interval *this = rb_entry(*link, struct interval, node);
        parent = *link;
        if (new->start < this->start)
            link = &(*link)->rb_left;
        else if (new->start > this->start)
            link = &(*link)->rb_right;
        else
            return; /* duplicate key */
    }

    rb_link_node(&new->node, parent, link);  /* BST link */
    rb_insert_color(&new->node, &root);      /* RB rebalance */
}

struct interval *rb_find_interval(unsigned long start)
{
    struct rb_node *node = root.rb_node;
    while (node) {
        struct interval *i = rb_entry(node, struct interval, node);
        if (start < i->start)      node = node->rb_left;
        else if (start > i->start) node = node->rb_right;
        else                       return i;
    }
    return NULL;
}

Consider the page cache: the kernel needs to map file offsets (unsigned long integers, potentially very large) to struct page * objects. A hash table works but cannot efficiently answer "give me all pages in range [A, B]". A sorted RB tree works but has O(log n) operations and poor cache behavior for sequential access.

The kernel historically used a radix tree for this. Since Linux 4.20, the radix tree has been superseded by the XArray (include/linux/xarray.h), which provides a cleaner API over the same underlying multi-level tree structure.

An XArray is conceptually a sparse array mapping unsigned long indices to pointers. Internally it is a trie (prefix tree) where each internal node fans out by XA_CHUNK_SHIFT bits (typically 6 bits = 64 children per node). The tree height grows automatically as you insert larger indices. This gives:

• O(log n) worst-case, but in practice O(1) amortized for sequential access patterns because the trie depth is bounded by the key width (64 / 6 ≈ 11 levels max)
• Efficient range operations: find the next set index, erase a range, mark ranges with flags
• Built-in locking: the XArray uses an internal spinlock, with a "locked" API variant for when you hold the lock yourself

Special values: XA_ZERO_ENTRY and multi-index entries (where one entry spans multiple indices) support the page cache's huge-page needs.

The old radix tree API (radix_tree_insert, etc.) still exists for legacy code but new code should use XArray. If you see xa_store, xa_load, xa_erase, xa_for_each in kernel source, that is the XArray.

#include <linux/xarray.h>

static DEFINE_XARRAY(my_xa);

void xarray_demo(void)
{
    struct my_obj *obj;
    unsigned long index;

    /* Store: map index 42 -> obj */
    obj = kmalloc(sizeof(*obj), GFP_KERNEL);
    xa_store(&my_xa, 42, obj, GFP_KERNEL);

    /* Load: retrieve by index */
    obj = xa_load(&my_xa, 42);
    if (obj)
        pr_info("found object at index 42\n");

    /* Iterate over all populated entries */
    xa_for_each(&my_xa, index, obj) {
        pr_info("index=%lu obj=%p\n", index, obj);
    }

    /* Range erase */
    xa_erase(&my_xa, 42);

    /* Allocate the next available index automatically */
    xa_alloc(&my_xa, &index, obj, xa_limit_32b, GFP_KERNEL);
    pr_info("allocated index %lu\n", index);
}

A FIFO queue (ring buffer) is a fundamental building block for producer-consumer communication. The kernel provides struct kfifo (include/linux/kfifo.h) — a power-of-two sized circular byte buffer.

The key insight in kfifo's design is its lock-free single-producer single-consumer (SPSC) property. When there is exactly one producer and one consumer, kfifo needs no spinlock at all. The producer writes to in % size, incrementing in. The consumer reads from out % size, incrementing out. Because in and out are unsigned integers, wrap-around is automatic. The available bytes = in - out (unsigned subtraction wraps correctly). Since only the producer writes in and only the consumer writes out, no atomic operations are needed — just memory barriers (handled internally) to ensure the CPU's out-of-order execution does not reorder the index update with the data write.

For multi-producer or multi-consumer cases, you use kfifo_in_spinlocked / kfifo_out_spinlocked variants.

Typed kfifos: the kernel provides type-safe variants via macros:

• DECLARE_KFIFO(fifo, type, size) — declares a kfifo of type elements
• kfifo_put / kfifo_get — push/pop single elements
• kfifo_in / kfifo_out — push/pop arrays

Use cases in the kernel: the serial/TTY layer uses kfifos for transmit/receive buffers. The input subsystem uses them for event queues. Any driver with a simple producer-consumer pipeline between an interrupt handler (producer) and a work queue or process context (consumer) is a natural fit.

#include <linux/kfifo.h>

/* Declare a kfifo holding up to 64 unsigned int values */
DECLARE_KFIFO(event_queue, unsigned int, 64);

void kfifo_demo(void)
{
    unsigned int val;

    INIT_KFIFO(event_queue);

    /* Producer side (e.g., interrupt handler) */
    unsigned int event = 0xDEADBEEF;
    if (kfifo_put(&event_queue, event))
        pr_info("enqueued\n");
    else
        pr_warn("fifo full!\n");

    /* Consumer side (e.g., work queue / process context) */
    if (kfifo_get(&event_queue, &val))
        pr_info("got event: 0x%x\n", val);

    /* Check state */
    pr_info("len=%u avail=%u\n",
            kfifo_len(&event_queue),
            kfifo_avail(&event_queue));
}

Many kernel subsystems need to assign small, unique integer IDs to objects and later look up the object by ID. Examples: process IDs (pid_t), inotify watch descriptors, DRM GPU context handles. The naive approach — a linear scan over an array — is O(n). A hash table works but wastes memory and cannot guarantee finding the smallest available ID.

The IDR (include/linux/idr.h) solves this. It is built on top of the XArray (formerly the radix tree) and provides:

• idr_alloc(idr, ptr, start, end, gfp) — allocate the smallest available integer in [start, end) and store ptr at that index. O(log n).
• idr_find(idr, id) — look up ptr by id. O(log n).
• idr_remove(idr, id) — remove an entry.
• idr_for_each — iterate all entries.

The IDR guarantees that allocated IDs are densely packed starting from start. When you remove an ID and later allocate again, the freed slot is reused. This is critical for PIDs: Linux recycles process IDs (wrapping around at PID_MAX = 32768 by default) to avoid PID exhaustion.

IDA (Integer ID Allocator) is the variant that only tracks which integers are allocated without associating a pointer. It uses a bitmap internally and is smaller and faster when you only need the ID itself, not an associated pointer.

#include <linux/idr.h>

static DEFINE_IDR(my_idr);

void idr_demo(void)
{
    struct my_obj *obj = kmalloc(sizeof(*obj), GFP_KERNEL);
    int id;

    /* Allocate smallest available ID in [1, 1024) */
    id = idr_alloc(&my_idr, obj, 1, 1024, GFP_KERNEL);
    if (id < 0) {
        pr_err("idr_alloc failed: %d\n", id);
        kfree(obj);
        return;
    }
    pr_info("allocated id=%d\n", id);   /* will be 1 on first call */

    /* Look up by ID */
    struct my_obj *found = idr_find(&my_idr, id);
    pr_info("found=%p\n", found);

    /* Release */
    idr_remove(&my_idr, id);
    kfree(obj);

    /* IDA example: just allocate IDs, no pointer */
    DEFINE_IDA(my_ida);
    int new_id = ida_alloc(&my_ida, GFP_KERNEL);
    pr_info("IDA id=%d\n", new_id);
    ida_free(&my_ida, new_id);
}

One of the most profound ideas in the kernel's approach to scalability is per-CPU variables: instead of one shared variable protected by a lock, give each CPU its own private copy.

Why does this work? Because if CPU 0 only ever touches its own copy and CPU 1 only ever touches its own copy, there is no sharing — and no locks needed. The total work across all CPUs is the same, but there is zero contention.

Declaration:

DEFINE_PER_CPU(int, my_counter);

This allocates one int per CPU in a special memory section (.data..percpu). At boot, the kernel sets up per-CPU areas so that each CPU has its own physical copy.

Access requires disabling preemption (to prevent the scheduler from migrating your task to a different CPU mid-access, which would corrupt the invariant that you're only touching your CPU's copy):

get_cpu_var(my_counter)++;   /* disables preemption, returns lvalue */
put_cpu_var(my_counter);      /* re-enables preemption */

Or in interrupt/NMI context (where preemption is already disabled):

__this_cpu_inc(my_counter);   /* no preempt guard needed */

Real examples in the kernel:

• vmstat page statistics (vm_zone_stat, vm_node_stat) are per-CPU counters summed lazily
• The slab allocator's kmem_cache_cpu is a per-CPU cache of pre-allocated objects — the hot path of kmalloc never touches a spinlock, it just pops from the per-CPU cache
• Network receive queues (softnet_data) are per-CPU to avoid lock contention between CPUs processing different NICs

The deeper point: per-CPU variables embody the principle of data partitioning — a universal technique for scalability. When you partition data by CPU (or by thread, or by NUMA node), you eliminate cache ping-pong (false sharing) and lock contention simultaneously.

#include <linux/percpu.h>
#include <linux/preempt.h>

/* Declare a per-CPU counter */
DEFINE_PER_CPU(long, page_faults);

/* In interrupt/exception handler — preemption already off */
void on_page_fault(void)
{
    __this_cpu_inc(page_faults);  /* touch ONLY this CPU's copy */
}

/* Reading the system-wide total requires summing all CPUs */
long get_total_faults(void)
{
    long total = 0;
    int cpu;
    for_each_possible_cpu(cpu)
        total += per_cpu(page_faults, cpu);
    return total;
}

/* In process context: preempt guard is needed */
void process_context_example(void)
{
    long val;
    val = get_cpu_var(page_faults);   /* disables preemption */
    val += 5;
    put_cpu_var(page_faults);          /* re-enables preemption */
}

With this toolkit in hand, knowing which structure to reach for in a given situation is a skill that comes with practice. Here is a mental framework:

Ordered iteration needed?

• Yes, and key is an integer index → XArray (page cache, sparse arrays)
• Yes, and key is arbitrary (pid, address, custom) → RB tree
• No ordering needed → Hash table (hlist + DECLARE_HASHTABLE)

Need to assign and reclaim integer IDs? → IDR / IDA

Linked collection of objects needing O(1) insert/delete/iteration? → list_head (doubly-linked)

• Large number of mostly-empty bucket heads → hlist_head instead

Single-producer single-consumer byte/element stream (ISR → thread)? → kfifo

Per-CPU counters or caches to avoid lock contention? → per-CPU variables

A note on complexity constants: in the kernel, O(1) with high constants can be worse than O(log n) with small constants for realistic n. A list_head traversal touches every element sequentially — great cache behavior, O(n) but fast in practice for small lists. An RB tree has O(log n) but each step is a pointer chase. For n < ~32 elements, a plain list often wins over an RB tree in wall-clock time.

Locking considerations: every data structure here is lock-free for single-threaded use. In a multi-threaded kernel context, you must protect them with appropriate locks (spinlock, mutex, RCU) except for per-CPU variables (partitioned by design) and kfifo in the SPSC case. Choosing the data structure and choosing the locking strategy are coupled decisions — this will be a major theme in the Locking and Synchronization module.