Linux Kernel Data Structures

Linux’s list APIs are intrusive: linkage is embedded in the object owned by a subsystem. Intrusion removes a separate node allocation and lets one object participate in several indexes, but the container API does not own memory or provide synchronization.

Circular Doubly Linked Lists #

struct list_head contains only links:

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

struct job {
    unsigned long id;
    struct list_head pending_link;
    struct list_head owner_link;
};

A list head has the same type as an embedded node. In an empty list, next and prev both point back to the head. In a nonempty list, following either direction eventually returns to the head. Because the head is a sentinel rather than a payload object, iteration has no null terminator.

One object can appear in multiple lists through different members. Every operation must name the correct member; mixing pending_link and owner_link corrupts both lists.

Initialization and Basic Mutation #

Use LIST_HEAD() for a declaration and INIT_LIST_HEAD() when initializing an existing object:

static LIST_HEAD(pending_jobs);

struct queue {
    spinlock_t lock;
    struct list_head jobs;
};

static void queue_init(struct queue *queue)
{
    spin_lock_init(&queue->lock);
    INIT_LIST_HEAD(&queue->jobs);
}

LIST_HEAD_INIT(name) is an initializer expression, which is useful inside a larger static initializer. Initialization must occur before any list operation.

Insertion is relative to the sentinel:

list_add(&job->pending_link, &pending_jobs);      /* after head */
list_add_tail(&job->pending_link, &pending_jobs); /* before head */

list_add() implements stack-like insertion at the front; list_add_tail() implements queue-like insertion at the back. list_move() and list_move_tail() unlink an existing node and insert it at the destination’s front or tail.

list_del() unlinks a node and poisons its links to expose accidental reuse. Use list_del_init() when the detached node must become a valid, self-linked empty node again:

if (!list_empty(&pending_jobs)) {
    struct job *job =
        list_first_entry(&pending_jobs, struct job, pending_link);

    list_del_init(&job->pending_link);
    finish_job(job);
}

Do not add one linkage member twice. A self-linked node can be checked with list_empty(&job->pending_link), but that convention works only when every removal reinitializes the node.

Ownership Recovery with container_of #

An iterator reaches a struct list_head *, but subsystem code needs its containing object. container_of(ptr, type, member) subtracts the compile-time offset of member from ptr and preserves compile-time type checking. list_entry() specializes that pattern:

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

struct job *job =
    list_entry(node, struct job, pending_link);

The result is valid only when node really denotes the specified member of a live struct job. Neither macro performs dynamic type validation.

Typed iteration avoids an explicit conversion:

struct job *job;

list_for_each_entry(job, &pending_jobs, pending_link)
    run_job(job);

Reverse and continuation variants exist for less common traversal patterns. Choose the narrowest documented macro rather than open-coding next and prev, because the macros encode sentinel handling.

Deleting While Iterating #

Ordinary iteration reads the current node’s next link after the loop body. Deleting the current node invalidates that operation. A _safe iterator stores the next object first:

struct job *job, *next;

list_for_each_entry_safe(job, next, &pending_jobs, pending_link) {
    if (job_cancelled(job)) {
        list_del(&job->pending_link);
        kfree(job);
    }
}

“Safe” means safe against deletion by this loop. It does not protect against another CPU, interrupt, or callback mutating the list, and it does not establish that kfree() is legal. External references may require reference counting, RCU, or another lifetime protocol.

Splicing Lists #

Splice operations relink an entire list in constant time:

LIST_HEAD(batch);

build_batch(&batch);
list_splice_tail_init(&batch, &pending_jobs);

• list_splice() inserts after the destination head.
• list_splice_tail() inserts before the destination head.
• The _init variants also reinitialize the source head.

After list_splice() without _init, the source head still points into the transferred chain. Iterating that source as an independent list can loop incorrectly because its links no longer describe a separate circular list. Use an _init variant when ownership transfers and the source must become empty.

list_cut_position() moves a prefix into another head. As with every list mutation, the caller must ensure that all nodes and heads belong to the expected list.

Hashed Singly Linked Lists #

Hash tables need many bucket heads, so hlist uses a one-pointer head:

struct hlist_head {
    struct hlist_node *first;
};

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

struct cache_entry {
    unsigned long key;
    struct hlist_node hash_node;
};

pprev points to the link that points at the node: either the bucket’s first member or the previous node’s next member. Deletion can therefore update the predecessor link in constant time without storing a conventional prev pointer. The asymmetric representation saves one pointer in every bucket head, which matters when a table has many buckets.

static struct hlist_head table[256];

static void cache_insert(struct cache_entry *entry)
{
    unsigned int bucket = hash_long(entry->key, 8);

    hlist_add_head(&entry->hash_node, &table[bucket]);
}

static struct cache_entry *cache_find(unsigned long key)
{
    struct cache_entry *entry;

    hlist_for_each_entry(entry, &table[hash_long(key, 8)], hash_node)
        if (entry->key == key)
            return entry;
    return NULL;
}

Initialize standalone nodes with INIT_HLIST_NODE() when code relies on hlist_unhashed(). Use hlist_del_init() for removal followed by reuse, and use hlist_for_each_entry_safe() when the current loop deletes entries.

Concurrency and Lifetime Are Caller Responsibilities #

List and hlist operations are pointer rewrites, not transactions. The API provides no implicit lock, reference count, memory barrier for publishing payload fields, or reclamation grace period. A subsystem must define:

1. which lock serializes insertion and deletion;
2. which contexts may traverse the container;
3. how readers acquire object references;
4. when removed objects can be freed.

A spin lock can protect both traversal and mutation when critical sections cannot sleep. A mutex is preferable in sleepable process context. For read-dominant structures, RCU-specific APIs such as list_add_rcu(), list_del_rcu(), and hlist_for_each_entry_rcu() permit lockless readers, but only with the required publication primitives and delayed reclamation after a grace period. Mixing ordinary and RCU variants without a complete protocol is not safe.

The _safe iteration suffix and the _rcu suffix solve different problems: _safe preserves a loop cursor during local deletion, while _rcu participates in a concurrent-reader lifetime scheme.

References #

• Kernel Documentation: Linked Lists
• Kernel Source: include/linux/list.h
• Kernel Documentation: RCU List APIs