Commonly Used Data Structures in the Linux Kernel

Created:2026-05-24 23:08:13Updated:2026-05-25 23:08:13

Linux

GNU, Linux

Words 8.5k

Views

Visitors

Timeline

2026-05-24

init

This article introduces the core data structures with high practical usage frequency in the Linux 6.x kernel, detailing the definitions, core APIs, and typical use cases of structures such as doubly linked circular lists, hash linked lists, red-black trees, radix trees, extensible arrays, and priority linked lists.

Overview

A large number of general-purpose data structures are defined in the Linux kernel, which run through various subsystems such as process scheduling, memory management, file systems, and device drivers. This article organizes these data structures bypractical usage frequencyfrom high to low, covering data structure definitions, core APIs, and typical use cases.

info

This article is based on the Linux 6.x kernel, and some APIs may vary slightly between different versions.

Basic Containers

list_head — Doubly Linked Circular List

Usage frequency: Highest. This is the most widely used data structure in the Linux kernel, bar none. Almost every subsystem uses it.

success

The Linux linked list implementation separatesdata from list nodes, with list nodes embedded into the structure rather than the structure containing list pointers. The essence of this design is that a single set of list operations applies to all data types.

Header file:<linux/list.h>

Data structure:

1
2
3

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

Core APIs:

API	Description
`LIST_HEAD(name)`	Statically define and initialize a list head
`INIT_LIST_HEAD(ptr)`	Dynamically initialize a list head
`list_add(new, head)`	Insert after head
`list_add_tail(new, head)`	Insert before head (tail)
`list_del(entry)`	Delete node
`list_del_init(entry)`	Delete and reinitialize node
`list_empty(head)`	Determine if the list is empty
`list_entry(ptr, type, member)`	Get the containing structure from a list_head pointer
`list_for_each(pos, head)`	Traverse the linked list
`list_for_each_entry(pos, head, member)`	Traverse the linked list and get the containing structure
`list_for_each_entry_safe(pos, n, head, member)`	Safe traversal (can delete during traversal)
`list_move(list, head)`	Move node to a new linked list
`list_splice(list, head)`	Merge two linked lists

Usage example:

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

#define CNT 10

struct my_data {
        int val;
        struct list_head list;
};

// Define the linked list head
LIST_HEAD(my_list);

static int __init list_test_init(void)
{
        int i, ret = 0;
        struct my_data *entry, *tmp;

        pr_info("%s is called\n", __func__);

        for (i = 0; i < CNT; i++) {
                entry = kzalloc(sizeof(*entry), GFP_KERNEL);
                if (!entry) {
                        ret = -ENOMEM;
                        goto cleanup;
                }

                entry->val = i * 2;
                INIT_LIST_HEAD(&entry->list); // Initialize the linked list node
                list_add_tail(&entry->list, &my_list); // Add the linked list to the tail
        }

        list_for_each_entry(entry, &my_list, list)
        {
                pr_info("val is %d\n", entry->val);
        }

        return ret;
cleanup:
        list_for_each_entry_safe(entry, tmp, &my_list, list)
        {
                list_del(&entry->list);
                kfree(entry);
        }
        return ret;
}

static void __exit list_test_exit(void)
{
        struct my_data *entry, *tmp;

        list_for_each_entry_safe(entry, tmp, &my_list, list)
        {
                pr_info("del %d\n", entry->val);
                list_del(&entry->list);
                kfree(entry);
        }
        pr_info("%s is called\n", __func__);
}

module_init(list_test_init);
module_exit(list_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("zhaohang");
MODULE_DESCRIPTION("A test sample for linux link list");

Run

~ # insmod list_test.ko
[   11.039661] list_test: loading out-of-tree module taints kernel.
[   11.050065] list_test_init is called
[   11.050235] val is 0
[   11.050289] val is 2
[   11.050325] val is 4
[   11.050390] val is 6
[   11.050429] val is 8
[   11.050466] val is 10
[   11.050734] val is 12
[   11.050808] val is 14
[   11.050885] val is 16
[   11.050936] val is 18
~ # rmmod list_test.ko
[   17.474727] del 0
[   17.474865] del 2
[   17.474913] del 4
[   17.474950] del 6
[   17.474981] del 8
[   17.475060] del 10
[   17.475103] del 12
[   17.475135] del 14
[   17.475169] del 16
[   17.475221] del 18
[   17.475263] list_test_exit is called

list_addandlist_add_tail:

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}


/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

list_add_tailis inserted intohead->prevandheadbetween. But because this is a ring, “in front of head” logically equals “the end of the linked list”.

list_delandlist_del_initfunction

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */
static inline void list_del(struct list_head *entry)
{
	__list_del_entry(entry);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}


/**
 * list_del_init - deletes entry from list and reinitialize it.
 * @entry: the element to delete from the list.
 */
static inline void list_del_init(struct list_head *entry)
{
	__list_del_entry(entry);
	INIT_LIST_HEAD(entry);
}

list_replacecan replace a linked list node

/**
 * list_replace - replace old entry by new one
 * @old : the element to be replaced
 * @new : the new element to insert
 *
 * If @old was empty, it will be overwritten.
 */
static inline void list_replace(struct list_head *old,
				struct list_head *new)
{
	new->next = old->next;
	new->next->prev = new;
	new->prev = old->prev;
	new->prev->next = new;
}

/**
 * list_replace_init - replace old entry by new one and initialize the old one
 * @old : the element to be replaced
 * @new : the new element to insert
 *
 * If @old was empty, it will be overwritten.
 */
static inline void list_replace_init(struct list_head *old,
				     struct list_head *new)
{
	list_replace(old, new);
	INIT_LIST_HEAD(old);
}

hlist — Hash linked list

hlistis specifically designed forHash Tabledesigned as a variant of a doubly linked list. That is, when hashing data to be stored, if a collision occurs, usea linked listchain the conflicting data together for storage. Typically, the order of element usage in a hash table is: data storage —> data retrieval —> data deletion. Compared withlist_headthe difference is: the head node only uses onestruct hlist_head(single pointer), saving memory in the hash table array.

Its core design motivation is to solve the problem of standard doubly circular linked listslist_headexisting when used as a hash bucketmemory wasteandSemantic mismatchProblem.

Features	`list_head`(Standard linked list)	`hlist_head`+`hlist_node`(Hash linked list)
Head node structure	Complete bidirectional pointer (`next`,`prev`)	Only one unidirectional pointer (`first`)
Data node structure	Bidirectional pointer (`next`,`prev`)	Bidirectional pointer (`next`,`pprev`)
Is circular	Yes (head and tail connected)	No (ends with NULL)
Empty list check	`head->next == head`	`head->first == NULL`
Memory overhead (head node)	2 pointers (16 bytes/64-bit)	1 pointer (8 bytes/64-bit)

Header file:<linux/list.h>

Data structure:

struct hlist_head {
    struct hlist_node *first;  // Only one pointer!
};

struct hlist_node {
    struct hlist_node *next, **pprev;  // pprev points to the next pointer of the previous node
};

pprev's type isstruct hlist_node **(pointer to pointer).
It does not store “the address of the previous node”, but “the memory address of the next field in the previous node”。
For hlist chain head -> A -> B
For node B in the middle of the linked list:B->pprev == &(A->next)
For node A of the linked list:A->pprev == &(head->first)

This design facilitates deletion

static inline void __hlist_del(struct hlist_node *n)
{
	struct hlist_node *next = n->next;
	struct hlist_node **pprev = n->pprev;

	WRITE_ONCE(*pprev, next);
	if (next)
		WRITE_ONCE(next->pprev, pprev);
}

/**
 * hlist_del - Delete the specified hlist_node from its list
 * @n: Node to delete.
 *
 * Note that this function leaves the node in hashed state.  Use
 * hlist_del_init() or similar instead to unhash @n.
 */
static inline void hlist_del(struct hlist_node *n)
{
	__hlist_del(n);
	n->next = LIST_POISON1;
	n->pprev = LIST_POISON2;
}

/**
 * hlist_del_init - Delete the specified hlist_node from its list and initialize
 * @n: Node to delete.
 *
 * Note that this function leaves the node in unhashed state.
 */
static inline void hlist_del_init(struct hlist_node *n)
{
	if (!hlist_unhashed(n)) {
		__hlist_del(n);
		INIT_HLIST_NODE(n);
	}
}

add related

/**
 * hlist_add_head - add a new entry at the beginning of the hlist
 * @n: new entry to be added
 * @h: hlist head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
	struct hlist_node *first = h->first;
	WRITE_ONCE(n->next, first);
	if (first)
		WRITE_ONCE(first->pprev, &n->next);
	WRITE_ONCE(h->first, n);
	WRITE_ONCE(n->pprev, &h->first);
}

/**
 * hlist_add_before - add a new entry before the one specified
 * @n: new entry to be added
 * @next: hlist node to add it before, which must be non-NULL
 */
static inline void hlist_add_before(struct hlist_node *n,
				    struct hlist_node *next)
{
	WRITE_ONCE(n->pprev, next->pprev);
	WRITE_ONCE(n->next, next);
	WRITE_ONCE(next->pprev, &n->next);
	WRITE_ONCE(*(n->pprev), n);
}

/**
 * hlist_add_behing - add a new entry after the one specified
 * @n: new entry to be added
 * @prev: hlist node to add it after, which must be non-NULL
 */
static inline void hlist_add_behind(struct hlist_node *n,
				    struct hlist_node *prev)
{
	WRITE_ONCE(n->next, prev->next);
	WRITE_ONCE(prev->next, n);
	WRITE_ONCE(n->pprev, &prev->next);

	if (n->next)
		WRITE_ONCE(n->next->pprev, &n->next);
}

/**
 * hlist_add_fake - create a fake hlist consisting of a single headless node
 * @n: Node to make a fake list out of
 *
 * This makes @n appear to be its own predecessor on a headless hlist.
 * The point of this is to allow things like hlist_del() to work correctly
 * in cases where there is no list.
 */
static inline void hlist_add_fake(struct hlist_node *n)
{
	n->pprev = &n->next;
}

/**
 * hlist_fake: Is this node a fake hlist?
 * @h: Node to check for being a self-referential fake hlist.
 */
static inline bool hlist_fake(struct hlist_node *h)
{
	return h->pprev == &h->next;
}

rbtree — Red-Black Tree

The most used in the kernelSelf-balancing binary search tree, providing O(log n) search, insertion, and deletion. Each node in a Red-Black Tree has a storage bit indicating the node’s color, which can be Red or Black. Properties of Red-Black Trees:

Every node is either red or black.
The root is black.
Every leaf (NIL) is black. [Note: Here, leaf nodes refer to empty (NIL or NULL) leaf nodes!]
If a node is red, then its children must be black.
All paths from a node to its descendant leaves contain the same number of black nodes. This property ensures that no path is more than twice as long as any other, making the Red-Black Tree relatively balanced.

All operations on a Red-Black Tree must maintain its properties. Red-Black Trees are widely used, mainly for storing ordered data, with a time complexity of O(log n) and very high efficiency. cfs_rq uses a Red-Black Tree to store tasks.

Header file:<linux/rbtree.h>/<linux/rbtree_augmented.h>

Data structure:

struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root {
	struct rb_node *rb_node;
};

At a glance, it seems there is no field defined for color here, but this is the clever part of this Red-Black Tree implementation.__rb_parent_colorThis field actually contains both color information and the parent node’s pointer. Because this field is of type long and requires alignment of size sizeof(long), on a typical 32-bit machine, the last two bits are always 0, so one of these bits can be used to represent the color.
The key is Memory Alignment：
struct rb_nodeis forced to align bysizeof(long)alignment.
On a 32-bit system,sizeof(long) == 4, meaning any validrb_nodepointer address must be multiples of 4, i.e., the lowest binary 2 bits always00。
On a 64-bit system,sizeof(long) == 8, the lowest 3 bits always000。
In fact, the lowest bit is used here to represent color information. The following operations on the parent pointer and color information are essentially operations on therb_parent_color’s bits.
1
2
3
4
5
6
7
8
9
10
11
12
#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

#define RB_ROOT	(struct rb_root) { NULL, }
#define	rb_entry(ptr, type, member) container_of(ptr, type, member)

#define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)

/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
#define RB_EMPTY_NODE(node)  \
	((node)->__rb_parent_color == (unsigned long)(node))
#define RB_CLEAR_NODE(node)  \
	((node)->__rb_parent_color = (unsigned long)(node))

Linux’s red-black tree implementation is optimized for speed, thus having one less indirection than traditional implementations (better cache locality). Eachstruct rb_nodeinstance of the structure is embedded in the data structure it manages, so there is no need to use a pointer to separaterb_nodeand the data structure it manages.

Users should write their own tree search and insertion functions to call the provided red-black tree functions, rather than using a comparison callback function pointer.
Locking code is also left to the user of the red-black tree to write。

Example

// SPDX-License-Identifier: GPL-2.0
/*
 * rbtree_demo.c - Linux 5.10.x Red-Black Tree Module Demo
 * Demo: Insert、Search、Delete、in-order traversal、reverse-order traversal、get first and last nodes
 */
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/rbtree.h>
#include <linux/slab.h>
#include <linux/random.h>

/* ========== 1. Define a custom structure containing rb_node ========== */
struct my_node {
        struct rb_node rb; /* must be embedded as a member, usually at the beginning or anywhere */
        unsigned long data; /* data */
};

/* global red-black tree root node */
static struct rb_root my_tree = RB_ROOT;

/* ========== 2. Helper macro: retrieve the host structure from rb_node ========== */
#define rb_entry_my(ptr) rb_entry((ptr), struct my_node, rb)

/* ========== 3. Core operation encapsulation ========== */

/**
 * Find node - O(log n)
 */
static struct my_node *my_rb_search(struct rb_root *root, unsigned long data)
{
        struct rb_node *node = root->rb_node;

        while (node) {
                struct my_node *entry = rb_entry_my(node);

                if (data < entry->data) // Current node is greater than the key to find, go to left subtree
                        node = node->rb_left;
                else if (data > entry->data) // Current node is less than the key to find, go right
                        node = node->rb_right;
                else
                        return entry; /* Found */
        }
        return NULL; /* Not found */
}

/**
 * Insert node - O(log n)
 * Return: true=Newly inserted, false=keyAlready exists(Not inserted)
 *
 * 【Critical】Linux 5.10.x Use two-step method:
 *   1) rb_link_node()  : Link node under parent node（Do not color）
 *   2) rb_insert_color(): Fix red-black tree properties（Rotate+Recolor）
 */
static bool my_rb_insert(struct rb_root *root, struct my_node *new_node)
{
        struct rb_node **link = &root->rb_node; // Insertion position to find
        struct rb_node *parent = NULL;
        unsigned long data = new_node->data;

        /* Step 1: Standard BST search for insertion position */
        while (*link) {
                struct my_node *entry = rb_entry_my(*link);
                parent = *link;

                if (data < entry->data)
                        link = &(*link)->rb_left;
                else if (data > entry->data)
                        link = &(*link)->rb_right;
                else
                        return false; /* Key already exists, do not insert duplicate */
        }

        /* Step 2: Link and color */
        rb_link_node(&new_node->rb, parent, link);
        rb_insert_color(&new_node->rb, root);
        return true;
}

/**
 * Delete node - O(log n)
 */
static void my_rb_erase(struct rb_root *root, struct my_node *node)
{
        rb_erase(&node->rb, root);
        kfree(node);
}

/**
 * Destroy entire tree
 */
static void my_rb_destroy(struct rb_root *root)
{
        struct rb_node *node;
        /* Safely release in postorder manner to avoid accessing freed child nodes */
        while ((node = rb_first_postorder(root))) {
                rb_erase(node, root);
                kfree(rb_entry_my(node));
        }
        *root = RB_ROOT;
}

/* ========== 4. Module Initialization: Batch Insert + Verification ========== */
static int __init rbtree_demo_init(void)
{
        int i;
        unsigned long keys[] = { 1, 2, 3, 4, 5, 6, 7 };
        int count = ARRAY_SIZE(keys);

        pr_info("rbtree_demo: === Module Loaded ===\n");

        /* --- Insert Test --- */
        for (i = 0; i < count; i++) {
                struct my_node *node = kzalloc(sizeof(*node), GFP_KERNEL);
                if (!node)
                        return -ENOMEM;

                node->data = keys[i];

                if (my_rb_insert(&my_tree, node))
                        pr_info("rbtree_demo: INSERT data=%lu OK\n", keys[i]);
                else {
                        pr_warn("rbtree_demo: INSERT data=%lu DUPLICATE\n", keys[i]);
                        kfree(node);
                }
        }

        /* --- Search Test --- */
        {
                struct my_node *found = my_rb_search(&my_tree, 4);
                if (found)
                        pr_info("rbtree_demo: SEARCH data=4 => %lu\n", found->data);
                else
                        pr_warn("rbtree_demo: SEARCH data=4 => Not Found\n");
                

                found = my_rb_search(&my_tree, 666);
                if (found)
                        pr_info("rbtree_demo: SEARCH data=99 => %lu\n", found->data);
                else
                        pr_warn("rbtree_demo: SEARCH data=99 => Not Found\n");
        }

        /* --- In-order Traversal --- */
        pr_info("rbtree_demo: IN-ORDER TRAVERSAL:\n");
        {
                struct rb_node *node;
                for (node = rb_first(&my_tree); node; node = rb_next(node)) {
                        struct my_node *entry = rb_entry_my(node);
                        pr_info("       data=%lu\n", entry->data);
                }
        }

        /* --- Reverse Traversal --- */
        pr_info("rbtree_demo: REVERSE TRAVERSAL:\n");
        {
                struct rb_node *node;
                for (node = rb_last(&my_tree); node; node = rb_prev(node)) {
                        struct my_node *entry = rb_entry_my(node);
                        pr_info("       data=%lu\n", entry->data);
                }
        }

        /* --- Get Min/Max Node --- */
        {
                struct my_node *min = rb_entry_my(rb_first(&my_tree));
                struct my_node *max = rb_entry_my(rb_last(&my_tree));
                pr_info("rbtree_demo: MIN=%lu MAX=%lu\n", min->data, max->data);
        }

        /* --- Delete Test --- */
        {
                struct my_node *to_del = my_rb_search(&my_tree, 4);
                if (to_del) {
                        pr_info("rbtree_demo: ERASE data=4\n");
                        my_rb_erase(&my_tree, to_del);
                }
        }

        /* Traverse in-order again to confirm deletion result */
        pr_info("rbtree_demo: AFTER ERASE 30:\n");
        {
                struct rb_node *node;
                for (node = rb_first(&my_tree); node; node = rb_next(node)) {
                        struct my_node *entry = rb_entry_my(node);
                        pr_info("data=%lu\n", entry->data);
                }
        }

        return 0;
}

/* ========== 5. Module Unload: Clean Up All Resources ========== */
static void __exit rbtree_demo_exit(void)
{
        my_rb_destroy(&my_tree);
        pr_info("rbtree_demo: === Module Unloaded ===\n");
}

module_init(rbtree_demo_init);
module_exit(rbtree_demo_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("Linux 5.10.x rbtree operations demo");

radix_tree — Radix Tree

xarraypredecessor, used for mapping integer IDs to pointers. Althoughxarrayhas gradually replaced it, there is still a large amount of code using radix trees in the kernel.

If it is a new project, please use directly<linux/xarray.h>XArray API in . XArray fixes many design flaws of radix_tree (such as preload complexity, index offset issues), and the API is more concise. radix_tree in 5.10.x is just a compatibility layer on top of XArray.

Header file:<linux/radix-tree.h>

#define radix_tree_root		xarray
#define radix_tree_node		xa_node

struct radix_tree_preload {
	local_lock_t lock;
	unsigned nr;
	/* nodes->parent points to next preallocated node */
	struct radix_tree_node *nodes;
};
DECLARE_PER_CPU(struct radix_tree_preload, radix_tree_preloads);

As can be seenlinux-5.10.xxarray has already replaced it in

Example

// SPDX-License-Identifier: GPL-2.0
/*
 * radix_tree_demo.c - Linux 5.10.x Radix Tree Module Demo (Fixed)
 * Demo: Initialization、Preload、Insert、Search、Delete、Tags(tag)Operation、Safe Destroy
 */
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/radix-tree.h>
#include <linux/slab.h>
#include <linux/spinlock.h>
#include <linux/rcupdate.h>

/* Data structure for custom storage */
struct my_data {
    unsigned long id;
    char name[32];
};

/* Global radix tree and protection lock */
static RADIX_TREE(my_rtree, GFP_ATOMIC);
static DEFINE_SPINLOCK(my_rtree_lock);

/* ========== Helper Functions ========== */
static struct my_data *create_data(unsigned long id, const char *name)
{
    struct my_data *d = kmalloc(sizeof(*d), GFP_KERNEL);
    if (d) {
        d->id = id;
        strscpy(d->name, name, sizeof(d->name));
    }
    return d;
}

/* ========== Core Operation Encapsulation ========== */

/**
 * Safe node insertion
 * 【Critical】Must first preload Then insert inside the lock，Avoid triggering sleep allocation while holding the lock, leading to deadlock or OOM
 */
static int safe_insert(unsigned long index, struct my_data *data)
{
    int ret;

    /* Pre-allocate node memory (sleep allowed) */
    ret = radix_tree_preload(GFP_KERNEL);
    if (ret)
        return ret;

    spin_lock(&my_rtree_lock);
    ret = radix_tree_insert(&my_rtree, index, data);
    spin_unlock(&my_rtree_lock);

    radix_tree_preload_end();
    return ret;
}

/**
 * Find node - RCU Read-side safety
 */
static struct my_data *safe_lookup(unsigned long index)
{
    struct my_data *data;

    rcu_read_lock();
    data = radix_tree_lookup(&my_rtree, index);
    rcu_read_unlock();

    return data;
}

/**
 * Delete and free node
 */
static void safe_delete(unsigned long index)
{
    struct my_data *data;

    spin_lock(&my_rtree_lock);
    data = radix_tree_delete(&my_rtree, index);
    spin_unlock(&my_rtree_lock);

    kfree(data); /* delete returns the removed pointer; caller is responsible for freeing */
}

/**
 * Use Tag Batch marking and retrieval
 * Fixed：Use struct radix_tree_iter As iterator
 */
static void demo_tag_operations(void)
{
    struct my_data *d;
    void **slot;
    struct radix_tree_iter iter; /* Correct Iterator Type */

    pr_info("rtree_demo: === TAG Operations ===\n");

    /* Tag index=100 with tag 0 */
    spin_lock(&my_rtree_lock);
    radix_tree_tag_set(&my_rtree, 100, 0);
    spin_unlock(&my_rtree_lock);

    /* Batch retrieval by tag */
    rcu_read_lock();
    radix_tree_for_each_tagged(slot, &my_rtree, &iter, 0, 0) {
        d = radix_tree_deref_slot(slot);
        if (unlikely(radix_tree_deref_retry(d))) {
            slot = radix_tree_iter_retry(&iter); /* retry passing iter */
            continue;
        }
        if (d)
            pr_info("rtree_demo: TAGGED index=%lu name=%s\n",
                    iter.index, d->name); /* Get index from iter.index */
    }
    rcu_read_unlock();
}

/* ========== Module Entry ========== */
static int __init radix_tree_demo_init(void)
{
    struct my_data *d;
    int ret;

    pr_info("rtree_demo: === Module Loaded ===\n");

    /* RADIX_TREE() macro is statically initialized, no manual INIT needed_RADIX_TREE */

    /* --- Insert Test --- */
    d = create_data(42, "hello");
    ret = safe_insert(42, d);
    pr_info("rtree_demo: INSERT index=42 ret=%d\n", ret);

    d = create_data(100, "world");
    ret = safe_insert(100, d);
    pr_info("rtree_demo: INSERT index=100 ret=%d\n", ret);

    /* Test duplicate insertion */
    d = create_data(42, "duplicate");
    ret = safe_insert(42, d);
    pr_info("rtree_demo: INSERT DUP index=42 ret=%d (expect -EEXIST)\n", ret);
    kfree(d); /* Duplicate insertion failed, manually free */

    /* --- Search Test --- */
    d = safe_lookup(42);
    pr_info("rtree_demo: LOOKUP 42 => %s\n", d ? d->name : "NULL");

    d = safe_lookup(999);
    pr_info("rtree_demo: LOOKUP 999 => %s\n", d ? d->name : "NULL");

    /* --- Tag Test --- */
    demo_tag_operations();

    /* --- Delete Test --- */
    safe_delete(42);
    d = safe_lookup(42);
    pr_info("rtree_demo: AFTER DELETE 42 => %s\n", d ? d->name : "NULL");

    return 0;
}

/* ========== Module Unloading: Safely Traverse and Free All Remaining Nodes ========== */
static void __exit radix_tree_demo_exit(void)
{
    struct my_data *d;
    void **slot;
    struct radix_tree_iter iter; /* Correct Iterator Type */

    rcu_read_lock();
    radix_tree_for_each_slot(slot, &my_rtree, &iter, 0) {
        d = radix_tree_deref_slot(slot);
        if (unlikely(radix_tree_deref_retry(d))) {
            slot = radix_tree_iter_retry(&iter); /* retry passing iter */
            continue;
        }
        if (d) {
            /* Must delete within the lock, and use iter.index */
            spin_lock(&my_rtree_lock);
            radix_tree_delete(&my_rtree, iter.index);
            spin_unlock(&my_rtree_lock);
            kfree(d);
        }
    }
    rcu_read_unlock();

    pr_info("rtree_demo: === Module Unloaded ===\n");
}

module_init(radix_tree_demo_init);
module_exit(radix_tree_demo_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("Linux 5.10.x radix_tree operations demo (fixed iterator)");

xarray — Extensible Array

xarrayIntroduced in Linux 4.20Next-generation radix tree replacement, providing a mapping from integers (unsigned long) to pointers, with a cleaner API and better performance.

Header file:<linux/xarray.h>

Data structure:

struct xarray {
    spinlock_t  xa_lock;
    gfp_t       xa_flags;
    void __rcu *xa_head;
};

Core APIs:

API	Description
`DEFINE_XARRAY(name)`	Statically define xarray
`xa_init(xa)`	Dynamic initialization
`xa_store(xa, index, entry, gfp)`	Store entry
`xa_load(xa, index)`	Read entry
`xa_erase(xa, index)`	Delete entry
`xa_insert(xa, index, entry, gfp)`	Insert (key must not already exist)
`xa_for_each(xa, index, entry)`	Iterate over all entries
`xa_find(xa, indexp, max, filter)`	Find entries in range

Usage example:

DEFINE_XARRAY(my_xa);

// Store
xa_store(&my_xa, 0, ptr1, GFP_KERNEL);
xa_store(&my_xa, 42, ptr2, GFP_KERNEL);

// read
void *p = xa_load(&my_xa, 42);

// Traverse
unsigned long index;
void *entry;
xa_for_each(&my_xa, index, entry) {
    pr_info("index=%lu, entry=%p\n", index, entry);
}

plist — Priority Linked List

plistInlist_headadded on the basis ofPriority, the head always points to the node with the highest priority (a smaller prio value represents a higher priority), commonly used in scenarios where “always process the highest priority first” is required.

Header file:<linux/plist.h>

Data structure:

struct plist_node {
    int             prio;
    struct list_head    prio_list;  // Link to nodes of the same priority
    struct list_head    node_list;  // Overall linked list
};

struct plist_head {
    struct list_head node_list;  // All nodes sorted by priority
};

Core APIs:

API	Description
`plist_head_init(head)`	Initialization
`plist_node_init(node, prio)`	Initialize node
`plist_add(node, head)`	Insert by priority
`plist_del(node, head)`	Delete node
`plist_first(head)`	Get the node with the highest priority
`plist_head_empty(head)`	Check if empty

llist — lockless linked list

llist(lock-less list) is alockless singly linked list, implemented based on CAS operations, which performs better than spinlock + in specific scenarios (such as interrupts and processes sharing data)list_headhas better performance.

Header file:<linux/llist.h>

Data structure:

struct llist_head {
    struct llist_node *first;
};

struct llist_node {
    struct llist_node *next;
};

Core APIs:

API	Description
`llist_add(new, head)`	Insert at head (lockless)
`llist_del_all(head)`	Atomically detach the entire linked list
`llist_del_first(head)`	Delete the first node
`llist_empty(head)`	Check if empty

Typical pattern:

// Producer (can be in interrupt context)
struct llist_node *node = kmalloc(sizeof(*node), GFP_ATOMIC);
llist_add(node, &my_llist);

// Consumer (process context)
struct llist_node *list = llist_del_all(&my_llist);  // Atomically take the entire linked list
struct llist_node *entry, *tmp;
llist_for_each_entry_safe(entry, tmp, list) {
    process(entry);
    kfree(entry);
}

rhashtable — resizable hash table

rhashtableis aCan automatically expand and shrinkhash table implementation that supports RCU lookups, suitable for hash scenarios requiring dynamic growth.

Header file:<linux/rhashtable.h>

Core APIs:

API	Description
`rhashtable_init(ht, params)`	Initialization
`rhashtable_insert_slow(ht, key, obj)`	Insert
`rhashtable_lookup(ht, key, params)`	Search
`rhashtable_remove(ht, obj, params)`	Delete
`rhashtable_free_and_destroy(ht, fn, data)`	Destroy

Typical applications in the kernel:

Connection tracking table for network namespaces
XFRM security policy database
Hash type implementation of BPF map

maple_tree — Maple Tree

A new data structure introduced in Linux 6.1, used to replace the red-black tree + linked list combination in VMA management.maple_treeis a B-tree variant, supportsrange operations(range operations), which is very efficient for VMA lookup, traversal, and gap searching.

Header file:<linux/maple_tree.h>

Data structure:

struct maple_tree {
    spinlock_t      ma_lock;
    unsigned int    ma_flags;
    void __rcu     *ma_root;  // RCU protection
};

Core APIs:

API	Description
`mt_init(mt)`	Initialization
`mtree_lock(mt)`	Acquire write lock
`mtree_unlock(mt)`	Release write lock
`mas_store(mas, entry)`	Store entry
`mas_find(mas, max)`	Search
`mas_erase(mas)`	Delete
`MTREE_INIT(mt, flags)`	Static initialization
`mtree_destroy(mt)`	Destroy

Typical applications in the kernel:

VMA management: Linux 6.1+ usesmaple_treeto replace red-black tree + doubly linked list managementvm_area_struct
User-space programs (the user-space RCU library URCU also implements maple tree)

interval_tree — Interval tree

Interval tree is an augmented red-black tree used to manageRange([start, last]), supporting fast lookup of all intervals overlapping a given interval. Based onrbtree_augmentedimplementation.

Header file:<linux/interval_tree.h>

Data structure:

struct interval_tree_node {
    struct rb_node rb;
    unsigned long start;     // Interval start
    unsigned long last;      // Interval end
    unsigned long __subtree_last;  // Maximum last in subtree (augmented information)
};

Core APIs:

API	Description
`interval_tree_insert(node, root)`	Insert
`interval_tree_remove(node, root)`	Delete
`interval_tree_iter_first(root, start, last)`	Find first overlapping interval
`interval_tree_iter_next(node, start, last)`	Find next overlapping interval

Typical applications in the kernel:

VMA interval lookup (finding virtual memory areas overlapping a given address range)
GEM buffer management for DRM GPU drivers

klist — Kernel object linked list

klistis an alias forlist_headwrapper, which, together withkobjectsystem, provides get/put reference count protection: automatically acquires a reference to the node object while traversing the list, preventing the node from being freed during traversal.

Header file:<linux/klist.h>

Data structure:

struct klist_node {
    void            *n_klist;   // Field no longer used
    struct list_head    n_node;
    struct kref     n_ref;      // Reference count
};

struct klist {
    spinlock_t      k_lock;
    struct list_head    k_list;
    void            (*get)(struct klist_node *);
    void            (*put)(struct klist_node *);
};

Core APIs:

API	Description
`klist_add_head(n, k)`	Add to head
`klist_add_tail(n, k)`	Add to tail
`klist_del(n)`	Delete
`klist_iter_init(k, i)`	Initialize iterator
`klist_next(i)`	Get next node (auto get/put)
`klist_iter_exit(i)`	Cleanup iterator

Typical applications in the kernel:

In the device driver modelbus_type's device list
In the device driver modeldriver's device list

IDs, Bitmaps, and DMA

idr — ID allocator

idrProvidesInteger ID to pointermapping, automatically allocates a unique integer ID and associates it with a pointer. Suitable for scenarios where “an integer handle is needed”.

Header file:<linux/idr.h>

Core API (modern interface):

API	Description
`idr_alloc(idr, ptr, start, end, gfp)`	Assign ID and associate pointer
`idr_find(idr, id)`	Find pointer by ID
`idr_remove(idr, id)`	Delete ID mapping
`idr_for_each(idr, fn, data)`	Iterate over all entries
`idr_destroy(idr)`	Destroy idr
`idr_init(idr)`	Initialization

Usage example:

DEFINE_IDR(my_idr);

// Allocate
int id;
id = idr_alloc(&my_idr, ptr, 1, 0, GFP_KERNEL);  // Allocate starting from 1

// Search
void *p = idr_find(&my_idr, id);

// Free
idr_remove(&my_idr, id);

Typical applications in the kernel:

Process PID management
Device minor number allocation
GPU DRM driver handle management (GEM buffer handle)

ida — IDA allocator

idaisidrA simplified version that only allocates integer IDs without associating pointers (used when only a unique integer ID is needed, with lower memory overhead).

Header file:<linux/idr.h>

Core APIs:

API	Description
`ida_alloc(ida, gfp)`	Allocate an ID
`ida_free(ida, id)`	Free an ID
`ida_alloc_range(ida, min, max, gfp)`	Allocate an ID within a range
`ida_init(ida)`	Initialization
`ida_destroy(ida)`	Destroy

bitmap / cpumask — Bitmap

Used by the kernelunsigned longImplements bitmaps using arrays, providing an efficient set of bit operations.cpumaskA special form of bitmap, specifically describing CPU sets.

Header file:<linux/bitmap.h>/<linux/cpumask.h>

Core API (bitmap):

API	Description
`bitmap_zero(dst, nbits)`	Clear all bits
`bitmap_set(dst, pos, nbits)`	Set bit
`bitmap_clear(dst, pos, nbits)`	Clear bit
`bitmap_find_next_zero_area(buf, len, start, n, mask)`	Find contiguous zero region
`bitmap_and(dst, src1, src2, nbits)`	Bitwise AND
`bitmap_or(dst, src1, src2, nbits)`	Bitwise OR

Core API (cpumask):

API	Description
`cpumask_set_cpu(cpu, mask)`	Add CPU to mask
`cpumask_clear_cpu(cpu, mask)`	Remove CPU from mask
`cpumask_test_cpu(cpu, mask)`	Test if CPU is in mask
`for_each_cpu(cpu, mask)`	Iterate over CPUs in mask
`cpumask_of(cpu)`	Get mask for a single CPU
`cpu_possible_mask`	All possible CPUs in the system
`cpu_online_mask`	Currently online CPUs
`cpu_present_mask`	Currently present CPUs

Typical applications in the kernel:

IRQ affinity setting (specify which CPUs handle interrupts)
Process’scpus_allowed(set which CPUs a process can run on)
DMA mask for memory node

scatterlist — scatter-gather list

scatterlistUsed to describeNon-contiguous memory regions, which is extremely commonly used in DMA (Direct Memory Access) scenarios: linking scattered physical memory fragments into a whole for the DMA engine to process at once.

Header file:<linux/scatterlist.h>

Data structure:

struct scatterlist {
    unsigned long   page_link;   // Encodes page + offset + chain information
    unsigned int    offset;      // Page offset
    unsigned int    length;      // Data length
    dma_addr_t      dma_address; // DMA address
    unsigned int    dma_length;
};

Core APIs:

API	Description
`sg_init_one(sg, buf, len)`	Initialize a single sg entry
`sg_init_table(sg, nents)`	Initialize sg table
`sg_set_buf(sg, buf, len)`	Set entry
`sg_set_page(sg, page, len, offset)`	Set page entry
`sg_next(sg)`	Get next entry
`sg_nents(sg)`	Calculate number of entries
`dma_map_sg(dev, sg, nents, dir)`	Map sg table for DMA
`dma_unmap_sg(dev, sg, nents, dir)`	Unmap DMA

Usage example:

struct scatterlist sg[2];
sg_init_table(sg, 2);
sg_set_buf(&sg[0], buf1, len1);
sg_set_buf(&sg[1], buf2, len2);

int nents = dma_map_sg(dev, sg, 2, DMA_TO_DEVICE);
// ... initiate DMA transfer ...
dma_unmap_sg(dev, sg, 2, DMA_TO_DEVICE);

Typical applications in the kernel:

Block device I/O (scatter-gather linked list in bio)
Network drivers (scatter-gather Tx/Rx)
Any data transfer involving DMA
Data buffers for encryption/decryption subsystems

Concurrency and synchronization

atomic_t — atomic variable

Atomic operations in the kernel used for simple counting and flags, the foundation of lock-free programming. On 32-bit platformsatomic_tis 32-bit, on 64-bit platforms there is alsoatomic64_t。

Header file:<linux/atomic.h>

Data structure:

1
2
3

typedef struct {
    int counter;
} atomic_t;

Core APIs:

API	Description
`atomic_read(v)`	Read value
`atomic_set(v, i)`	Set value
`atomic_inc(v)`	Increment
`atomic_dec(v)`	Decrement
`atomic_add(i, v)`	Add
`atomic_sub(i, v)`	Subtract
`atomic_inc_return(v)`	Increment and return new value
`atomic_dec_and_test(v)`	Decrement and test if zero
`atomic_cmpxchg(v, old, new)`	CAS operation
`atomic_xchg(v, new)`	Swap and return old value

Typical applications in the kernel:

Reference counting (open count for drivers)
Statistical counters (network packet count, interrupt count)
Simple lock-free flag

kref / refcount_t — reference counting

kref

Encapsulationrefcount_t, provides reference counting management for objects, withreleasecallback to automatically release resources when the count reaches zero.

Header file:<linux/kref.h>

struct kref {
    refcount_t refcount;
};

void kref_init(struct kref *kref);
void kref_get(struct kref *kref);           // Increment reference
int kref_put(struct kref *kref, void (*release)(struct kref *kref));  // Decrement reference, call release when it reaches 0

refcount_t

refcount_tisatomic_tAn enhanced version that provides overflow protection—stops incrementing after reaching the maximum value, preventing use-after-free vulnerabilities caused by reference count overflow.

Header file:<linux/refcount.h>

1
2
3

typedef struct refcount_struct {
    atomic_t refs;
} refcount_t;

Typical usage pattern:

struct my_object {
    struct kref kref;
    // ... other data
};

void release_callback(struct kref *kref)
{
    struct my_object *obj = container_of(kref, struct my_object, kref);
    kfree(obj);
}

// Acquire reference
struct my_object *get_object(struct my_object *obj)
{
    if (obj)
        kref_get(&obj->kref);
    return obj;
}

// Release reference
void put_object(struct my_object *obj)
{
    if (obj)
        kref_put(&obj->kref, release_callback);
}

Typical applications in the kernel:

struct kobject's reference count
struct device's lifecycle management
File descriptor (struct file）
Almost all kernel objects that require lifecycle management

spinlock_t — Spinlock

The most basic in the Linux kernelBusy-wait lock, used for short critical section protection in SMP systems. When the holder spins waiting on one CPU, executors on other CPUs also spin wait.

Header file:<linux/spinlock.h>

Data structure (simplified):

typedef struct spinlock {
    union {
        struct raw_spinlock rlock;
        // ...
    };
} spinlock_t;

Core APIs:

API	Description
`spin_lock_init(lock)`	Dynamic initialization
`DEFINE_SPINLOCK(lock)`	Static definition + initialization
`spin_lock(lock)`	Acquire lock (disables kernel preemption)
`spin_unlock(lock)`	Unlock
`spin_lock_irq(lock)`	Acquire lock and disable local interrupts
`spin_unlock_irq(lock)`	Release lock and enable local interrupts
`spin_lock_irqsave(lock, flags)`	Acquire lock, save interrupt state
`spin_unlock_irqrestore(lock, flags)`	Release lock, restore interrupt state
`spin_lock_bh(lock)`	Acquire lock and disable bottom half
`spin_trylock(lock)`	Try to acquire lock (non-blocking)
`spin_is_locked(lock)`	Check lock state

warning

While holding spinlockMust not sleep(Cannot callkmalloc(GFP_KERNEL)、copy_from_useroperations that may block). This is one of the most common sources of bugs in the kernel.

Selection guide:

Scenario	API
Between process contexts	`spin_lock`/`spin_unlock`
Between process and interrupt	`spin_lock_irqsave`/`spin_unlock_irqrestore`
Between different interrupts	`spin_lock_irqsave`/`spin_unlock_irqrestore`
Between process and bottom half	`spin_lock_bh`/`spin_unlock_bh`

mutex — mutual exclusion lock

Unlike spinlock,mutexwhen the lock cannot be acquired, it yields the CPU and goes to sleep, suitable forcritical sections that may sleep。

Header file:<linux/mutex.h>

Data structure:

struct mutex {
    atomic_long_t       owner;
    raw_spinlock_t      wait_lock;
    struct list_head    wait_list;  // Waiter queue
    // ...
};

Core APIs:

API	Description
`mutex_init(lock)`	Dynamic initialization
`DEFINE_MUTEX(lock)`	Static definition
`mutex_lock(lock)`	Acquire lock (may sleep)
`mutex_unlock(lock)`	Unlock
`mutex_lock_interruptible(lock)`	Interruptible acquisition
`mutex_trylock(lock)`	Try to acquire (non-blocking)
`mutex_is_locked(lock)`	Check status

warning

mutexThe locker must be responsible for unlocking (lock/unlock in different contexts is not allowed). The kernel strictly checks this.

Choice between spinlock and mutex:

	spinlock	mutex
When unable to acquire	Spin wait	Sleep and yield CPU
Critical section	Short (nanosecond level)	Can be longer (millisecond level)
Can sleep	Absolutely not	can
Interrupt context	Available	Unavailable
System overhead	Low	Higher (involves scheduling)

completion — Completion

completionImplemented in the kernelA synchronization mechanism where one thread waits for another thread to complete a taskLighter and has clearer semantics than semaphores.

Header file:<linux/completion.h>

Data structure:

struct completion {
    unsigned int done;
    struct swait_queue_head wait;
};

Core APIs:

API	Description
`DECLARE_COMPLETION(comp)`	Static definition
`init_completion(comp)`	Dynamic initialization
`wait_for_completion(comp)`	Wait for completion (uninterruptible)
`wait_for_completion_interruptible(comp)`	Wait for completion (interruptible by signal)
`wait_for_completion_timeout(comp, timeout)`	Wait with timeout
`complete(comp)`	Wake up one waiter
`complete_all(comp)`	Wake up all waiters
`try_wait_for_completion(comp)`	Non-blocking attempt

Usage example:

// Thread A: Wait
DECLARE_COMPLETION(done);

int thread_a(void *data)
{
    wait_for_completion(&done);
    pr_info("任务完成\n");
    return 0;
}

// Thread B: Notify after completion
int thread_b(void *data)
{
    do_something();
    complete(&done);
    return 0;
}

Typical applications in the kernel:

Kernel thread creation/destruction wait
Device initialization completion notification
Asynchronous I/O completion notification
Module unload wait

RCU (rcu_head) — Read-Copy-Update

RCU (Read-Copy-Update) is an importantlock-free synchronization mechanism, suitable for read-mostly scenarios. Readers are completely lock-free, writers copy first and then update, and wait for all readers to finish before reclaiming old data.

Header file:<linux/rcupdate.h>/<linux/srcu.h>

Data structure:

struct rcu_head {
    struct callback_head *next;
    void (*func)(struct callback_head *head);
};

Core APIs:

API	Description
`rcu_read_lock()`	Reader enters critical section
`rcu_read_unlock()`	Reader leaves critical section
`call_rcu(head, func)`	Register reclamation callback
`synchronize_rcu()`	Wait for all readers to complete (blocking)
`rcu_assign_pointer(p, v)`	Writer updates pointer
`rcu_dereference(p)`	Reader dereferences pointer
`kfree_rcu(ptr, rcu_field)`	RCU safe memory release

Typical pattern:

// Reader — completely lock-free
rcu_read_lock();
struct my_data *p = rcu_dereference(global_ptr);
if (p)
    do_something(p);
rcu_read_unlock();

// Writer — copy + update
struct my_data *old = global_ptr;
struct my_data *new = kmemdup(old, sizeof(*old), GFP_KERNEL);
update_data(new);
rcu_assign_pointer(global_ptr, new);
call_rcu(&old->rcu, my_free_callback);

Typical applications in the kernel:

Network routing table lookup
Filesystem dentry cache
radix_tree/xarraylock-free lookup
fdtableExpansion of (file descriptor table)

Waiting and scheduling

wait_queue — wait queue

A wait queue is a more general waiting mechanism: a process puts itself into the wait queue and goes to sleep, and is woken up when the condition is met.

Header file:<linux/wait.h>

Data structure:

struct wait_queue_head {
    spinlock_t          lock;
    struct list_head    head;     // Wait entry linked list
};

struct wait_queue_entry {
    unsigned int        flags;
    void               *private;  // Usually points to task_struct
    wait_queue_func_t   func;     // Wakeup callback (usually autoremove)_wake_function）
    struct list_head    entry;
};

Core APIs:

API	Description
`DECLARE_WAIT_QUEUE_HEAD(wq)`	Static definition
`init_waitqueue_head(wq)`	Dynamic initialization
`wait_event(wq, condition)`	Wait until condition is true
`wait_event_interruptible(wq, condition)`	Wait interruptible by signal
`wait_event_timeout(wq, condition, timeout)`	Wait with timeout
`wake_up(wq)`	Wake up all waiters
`wake_up_interruptible(wq)`	Wake up TASK_INTERRUPTIBLE waiters
`wake_up_nr(wq, nr)`	Wake up nr waiters

Usage example:

DECLARE_WAIT_QUEUE_HEAD(wq);
int data_ready = 0;

// Wait side
wait_event_interruptible(wq, data_ready != 0);

// Wakeup side
data_ready = 1;
wake_up_interruptible(&wq);

Typical applications in the kernel:

Process state switching (TASK_INTERRUPTIBLE / TASK_UNINTERRUPTIBLE）
Blocking I/O in device drivers (read/write waiting for data)
Read/write waiting for Pipe, Socket

work_struct / workqueue — Work queue

Work queue deferstasks to process contextfor execution, which is one of the common ways to handle interrupt bottom halves.

Header file:<linux/workqueue.h>

Data structure:

struct work_struct {
    atomic_long_t data;
    struct list_head entry;
    work_func_t func;  // Work function
};

// Work function signature:
typedef void (*work_func_t)(struct work_struct *work);

Core APIs:

API	Description
`DECLARE_WORK(work, func)`	Static definition
`INIT_WORK(work, func)`	Dynamic initialization
`schedule_work(work)`	Dispatch to system workqueue
`schedule_delayed_work(dwork, delay)`	Delayed dispatch
`queue_work(wq, work)`	Dispatch to specified workqueue
`cancel_work_sync(work)`	Cancel and wait for completion
`flush_work(work)`	Wait for work completion
`alloc_ordered_workqueue(name, flags)`	Create ordered workqueue

Usage example:

static void my_work_handler(struct work_struct *work)
{
    pr_info("工作在进程上下文执行\n");
    // Can sleep here!
}

DECLARE_WORK(my_work, my_work_handler);

// Trigger (e.g., in interrupt handling)
schedule_work(&my_work);

Typical applications in the kernel:

Interrupt bottom-half processing
Delayed initialization of device drivers
Packet processing in the network stack
GPU driver command submission

timer_list — kernel timer

Used to, after a specified timeexecute a callback function(softirq context), with jiffies-level precision (usually 1ms~10ms). For higher precision, usehrtimer。

Header file:<linux/timer.h>

Data structure:

struct timer_list {
    struct hlist_node   entry;
    unsigned long       expires;  // Expiration time (jiffies)
    void                (*function)(struct timer_list *);
    u32                 flags;
    // ...
};

Core APIs:

API	Description
`timer_setup(timer, callback, flags)`	Initialize timer
`mod_timer(timer, expires)`	Modify expiration time
`add_timer(timer)`	Add timer
`del_timer(timer)`	Delete timer
`del_timer_sync(timer)`	Synchronous deletion (wait for handler to complete)
`timer_pending(timer)`	Check if submitted

Usage example:

static void my_timer_callback(struct timer_list *t)
{
    pr_info("定时器到期\n");
    // Periodic timer: reset
    mod_timer(t, jiffies + msecs_to_jiffies(500));
}

struct timer_list my_timer;
timer_setup(&my_timer, my_timer_callback, 0);
mod_timer(&my_timer, jiffies + msecs_to_jiffies(500));

Typical applications in the kernel:

TCP retransmission timer, keepalive timer
Watchdog timer
Device driver polling
LED blinking control

hrtimer — High-resolution timer

hrtimerProvidesNanosecond levelprecision timer, managed by a red-black tree at the bottom layer. It is the foundation of the modern Linux timer subsystem.

Header file:<linux/hrtimer.h>

Data structure:

struct hrtimer {
    struct timerqueue_node      node;   // Red-black tree node
    ktime_t                     _softexpires;
    enum hrtimer_restart        (*function)(struct hrtimer *);
    // ...
};

Core APIs:

API	Description
`hrtimer_init(timer, clock_id, mode)`	Initialization
`hrtimer_start(timer, time, mode)`	Start timer
`hrtimer_cancel(timer)`	Cancel timer
`hrtimer_forward_now(timer, interval)`	Advance from current time

Usage example:

static enum hrtimer_restart my_hrtimer_cb(struct hrtimer *timer)
{
    pr_info("高精度定时器到期\n");
    hrtimer_forward_now(timer, ns_to_ktime(1000000));  // 1ms
    return HRTIMER_RESTART;
}

struct hrtimer hr_timer;
hrtimer_init(&hr_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
hr_timer.function = my_hrtimer_cb;
hrtimer_start(&hr_timer, ns_to_ktime(1000000), HRTIMER_MODE_REL);

Typical applications in the kernel:

Periodic tick of the process scheduler
POSIX timer
High-resolution sleep (usleep_range）
Precise latency control of network packets

Device model and notifications

kobject / kset — Kernel object model

kobjectis Linux device driver model’s cornerstone, providing unified reference counting, sysfs representation, and hotplug event support for all kernel objects.

Header file:<linux/kobject.h>

Data structure:

struct kobject {
    const char      *name;
    struct list_head    entry;       // List linked into kset
    struct kobject      *parent;     // Parent object
    struct kset         *kset;       // Owning kset
    struct kobj_type    *ktype;      // Type descriptor (including sysfs operations)
    struct kernfs_node  *sd;        // sysfs directory node
    struct kref         kref;        // Reference count
    unsigned int state_initialized:1;
    // ...
};

struct kset {
    struct list_head list;           // All kobjects belonging to this kset
    spinlock_t list_lock;
    struct kobject kobj;             // It is also a kobject itself
    const struct kset_uevent_ops *uevent_ops;
};

Core APIs:

API	Description
`kobject_init(obj, ktype)`	Initialize kobject
`kobject_add(obj, parent, fmt, ...)`	Add to sysfs
`kobject_init_and_add(obj, ktype, parent, fmt, ...)`	Initialize + Add
`kobject_put(obj)`	Decrement reference count
`kobject_get(obj)`	Increment reference count
`kobject_uevent(obj, action)`	Send uevent to userspace
`kset_register(kset)`	Register kset
`kobject_create_and_add(name, parent)`	Quickly create kobject

Typical applications in the kernel:

/sysEach directory and file in the file system
struct device、struct driver、struct bus_typebase classes of the device model, etc.
ueventHotplug events (e.g., USB insertion notifying udev)

notifier_block — Notifier Chain

The Notifier Chain is apublish-subscribepattern implementation in the kernel: a subsystem publishes events, and other interested modules register callbacks to receive notifications.

Header file:<linux/notifier.h>

Data structure:

struct notifier_block {
    notifier_fn_t notifier_call;    // Callback function
    struct notifier_block __rcu *next;  // Linked list next
    int priority;                   // Priority
};

Core APIs:

API	Description
`blocking_notifier_chain_register(head, nb)`	Register notifier block
`blocking_notifier_chain_unregister(head, nb)`	Unregister
`blocking_notifier_call_chain(head, val, v)`	Notifier call
`raw_notifier_chain_register(head, nb)`	Register (atomic context safe)
`atomic_notifier_chain_register(head, nb)`	Register (atomic context)

Notifier chain types:

Type	Callback context	Can block
`atomic_notifier_chain`	Atomic context (interrupt/spinlock)	No
`blocking_notifier_chain`	Process context	is
`raw_notifier_chain`	Any context (caller’s responsibility)	Depends on the caller
`SRCU_notifier_chain`	Process context (SRCU protected)	is

Typical applications in the kernel:

Kernel panic notification
CPU hotplug events
Network device events (netdev registration/deregistration)
System reboot/suspend notification
Out-of-memory (OOM) notification

Memory management and caching

kfifo — kernel FIFO queue

kfifois aLock-free circular buffer(circular buffer), providing lock-free communication for single-reader/single-writer producer/consumer (multi-reader/multi-writer requires external synchronization).

Header file:<linux/kfifo.h>

Core APIs:

API	Description
`DECLARE_KFIFO(fifo, type, size)`	Static definition
`kfifo_alloc(fifo, size, gfp)`	Dynamic allocation
`kfifo_put(fifo, val)`	Enqueue an element
`kfifo_get(fifo, val)`	Dequeue an element
`kfifo_in(fifo, buf, n)`	Enqueue multiple bytes
`kfifo_out(fifo, buf, n)`	Dequeue multiple bytes
`kfifo_is_empty(fifo)`	Is empty
`kfifo_is_full(fifo)`	Is full
`kfifo_len(fifo)`	Number of used elements
`kfifo_reset(fifo)`	Clear queue
`kfifo_free(fifo)`	Free memory

Usage example:

DECLARE_KFIFO(fifo, int, 32);

// Enqueue
int val = 42;
kfifo_put(&fifo, val);

// Dequeue
int out;
if (kfifo_get(&fifo, &out))
    pr_info("got: %d\n", out);

Typical applications in the kernel:

Serial port driver’s transmit/receive buffer
Audio driver’s PCM buffer
Kernel log buffer (printk ring buffer)

percpu — Per-CPU variables

Per-CPU variables allocateindependent memory copies for each CPU, CPUs can access their own copies without locking, and cache utilization is extremely high (variables are in the CPU’s local cache).

Header file:<linux/percpu.h>

Core APIs:

API	Description
`DEFINE_PER_CPU(type, name)`	Static definition
`alloc_percpu(type)`	Dynamic allocation
`per_cpu(var, cpu)`	Access the copy of a specified CPU
`get_cpu_var(var)`	Get this CPU’s copy (preemption disabled)
`put_cpu_var(var)`	Paired with get_cpu_var, restore preemption
`this_cpu_ptr(ptr)`	Get the pointer to this CPU’s copy
`per_cpu_ptr(ptr, cpu)`	Get the pointer to a specified CPU’s copy
`for_each_possible_cpu(cpu)`	Iterate over all CPUs

Usage example:

static DEFINE_PER_CPU(int, my_counter);

// Increment this CPU's counter — no locking required
int cpu = get_cpu();
per_cpu(my_counter, cpu)++;
put_cpu();

// A more concise way (better performance)
this_cpu_inc(my_counter);

Typical applications in the kernel:

Statistical counters (network packet count, interrupt count)
Memory allocator per-CPU caches (slab/slub)
RCU per-CPU state
Scheduler per-CPU run queues

circ_buf — circular buffer macros

A set of simple macros for using ordinary character arrays as circular buffers. Often used to implement lightweight producer/consumer queues.

Header file:<linux/circ_buf.h>

Data structure:

struct circ_buf {
    char *buf;
    int head;   // Producer write position
    int tail;   // Consumer read position
};

Core macros:

Macro	Description
`CIRC_SPACE(head, tail, size)`	Available space
`CIRC_CNT(head, tail, size)`	Used bytes
`CIRC_SPACE_TO_END(head, tail, size)`	Contiguous space to the end of the buffer

Typical applications in the kernel:

TTY driver line discipline buffer
Simple serial port driver

flex_array — flexible array

flex_arrayAllows creatingarrays spanning multiple pages, but with a fixed element size. Compared to allocating akmalloclarge block of memory at once,flex_arrayit is more tolerant of small memory fragmentation (because each element is distributed across different pages).

warning

Starting from Linux 5.10,flex_arrayit has been marked as deprecated, and it is recommended to use ordinarykmalloc_arrayorkvmalloc_arrayinstead.

Header file:<linux/flex_array.h>(deleted)

Alternative:kvmalloc_array(n, size, GFP_KERNEL)will automatically selectkmallocorvmalloc。

page — physical page descriptor

struct pageis in Linux memory managementthe most important data structure, each physical memory page has a correspondingpagestructure.

Header file:<linux/mm_types.h>

Data structure (greatly simplified):

struct page {
    unsigned long flags;         // Page flags (PG_locked, PG_dirty, etc.)
    union {
        struct {
            struct list_head lru;    // LRU list
            struct address_space *mapping;  // Associated file mapping
            pgoff_t index;           // Page offset
            unsigned long private;
        };
        // ... SLUB/slab related fields
    };
    refcount_t _refcount;        // Reference count
    // ...
};

Core API (partial):

API	Description
`alloc_pages(gfp_mask, order)`	Allocate 2^order pages
`__free_pages(page, order)`	Free pages
`get_page(page)`	Increment reference count
`put_page(page)`	Decrement reference count
`page_to_pfn(page)`	Get page frame number
`pfn_to_page(pfn)`	Page frame number to page
`kmap(page)`	Map to kernel address space
`kunmap(page)`	Unmap

Typical applications in the kernel:

Page Cache
Underlying foundation of SLUB/SLAB allocator
User space page table mapping (page fault handling)

mm_struct / vm_area_struct — Process address space

mm_struct — Memory descriptor

Describes a process’sComplete virtual address space, each process has a uniquemm_struct(can be shared among threads).

Header file:<linux/mm_types.h>

struct mm_struct {
    struct maple_tree   mm_mt;          // VMA maple tree (6.1+)
    struct vm_area_struct *mmap;        // VMA linked list head
    unsigned long task_size;            // Address space size
    pgd_t *pgd;                         // Page Global Directory
    atomic_t mm_users;                  // User count
    atomic_t mm_count;                  // Reference count
    unsigned long total_vm;             // Total number of pages
    spinlock_t page_table_lock;
    struct list_head mmlist;            // Global mm_struct linked list
    // ...
};

vm_area_struct — Virtual memory area

Describes a segment ofContiguous virtual address range, each range has the same protection attributes and mapping type.

struct vm_area_struct {
    unsigned long vm_start;             // Start address
    unsigned long vm_end;               // End address (exclusive)
    struct vm_area_struct *vm_next;     // Linked list next
    pgprot_t vm_page_prot;              // Page protection
    unsigned long vm_flags;             // VM_READ, VM_WRITE, VM_EXEC, etc.
    struct rb_node vm_rb;               // Red-black tree node (legacy)
    struct mm_struct *vm_mm;            // Owning mm_struct
    const struct vm_operations_struct *vm_ops;  // Operations function table
    struct file *vm_file;               // Mapped file
    // ...
};

Typical applications in the kernel:

Page fault handler
mmap()/munmap()System call
/proc/<pid>/mapsinformation source of

Network

sk_buff — Socket buffer

sk_buff(usually abbreviated asskb) is the Linux network subsystem’s core data structure, representing a network packet. It runs through the entire network stack: from network card driver reception to application layer transmission, all usesk_buffas the carrier.

Header file:<linux/skbuff.h>

Data structure (simplified):

struct sk_buff {
    union {
        struct {
            struct sk_buff      *next;   // Doubly linked list
            struct sk_buff      *prev;
        };
        struct list_head    list;
    };
    struct sock     *sk;
    ktime_t         tstamp;
    struct net_device   *dev;
    char            cb[48] __aligned(8);  // Per-layer private data
    unsigned int    len,           // Total data length
                    data_len;      // Non-linear data length
    __u16           mac_len,
                    hdr_len;
    // ... followed by pointers such as head, data, tail, end, etc.
    sk_buff_data_t      tail;
    sk_buff_data_t      end;
    unsigned char       *head, *data;
    unsigned int        truesize;
    refcount_t          users;
};

sk_buffManaging data space using a four-pointer model:

head  data        tail  end
 |     |           |     |
 v     v           v     v
+-----+-----------+-----+
|headroom|  data   |tailroom|
+-----+-----------+-----+

Core APIs:

API	Description
`alloc_skb(size, gfp)`	Allocate skb
`skb_put(skb, len)`	Add data to tail
`skb_push(skb, len)`	Add data to head (add protocol header)
`skb_pull(skb, len)`	Remove data from head (strip protocol header)
`skb_clone(skb, gfp)`	Clone skb (shared data)
`skb_copy(skb, gfp)`	Deep copy (copy data)
`kfree_skb(skb)`	Free skb
`skb_queue_head(list, skb)`	Enqueue to head
`skb_dequeue(list)`	Dequeue