Common data structures in the Linux kernel

Timeline

Timeline

2026-05-24

init

2026-08-15

Add complete module examples for hlist, xarray, and plist, and synchronize the list_head、rbtree、radix_and tree examples to linux_driver_learning the latest version of the 82~87 series, and rewrite the examples of the remaining data structures (llist, rhashtable, maple_tree、interval_tree、klist、idr、ida、bitmap、scatterlist、atomic、kref、spinlock、mutex、completion、RCU、wait_queue、workqueue、timer、hrtimer、kobject、notifier、kfifo、percpu、circ_buf) uniformly into loadable modules of the same style

This article introduces common generic data structures in the Linux kernel, organized by actual usage frequency from high to low, covering the doubly circular linked list list_head, hash linked list hlist, red-black tree rbtree, radix tree radix_tree and other core structures, covering their data structure definitions, core APIs, and typical usage scenarios. The article is based on the Linux 6.x kernel and also updates loadable module examples for each data structure to help developers understand and apply them.

---

Overview

The Linux kernel defines a large number of generic data structures, which run through various subsystems such as process scheduling, memory management, file systems, and device drivers. This article organizes them byactual usage frequencyfrom high to low, covering data structure definitions, core APIs, and typical usage scenarios.

info

This article is based on Linux 6.x kernel; some APIs may differ slightly between versions.

Basic Containers

list_head — Doubly Circular Linked List

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

success

Linux’s linked list implementation separatesdata from linked list nodesThe list node is embedded into the structure, rather than the structure containing list pointers. The essence of this design is that one set of list operations works for all data types.

Header file:<linux/list.h>

Data structure:

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

Core API:

API	Description
LIST_HEAD(name)	Statically define and initialize a list head
INIT_LIST_HEAD(ptr)	Dynamically initialize the 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 the node
list_empty(head)	Check whether 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 list and retrieve the containing structure
list_for_each_entry_safe(pos, n, head, member)	Safe traversal (can delete during traversal)
list_move(list, head)	Move a node to a new list
list_splice(list, head)	Merge two linked lists

Usage example:

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

#define CNT 10

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

LIST_HEAD(my_list);

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

	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);
		list_add_tail(&entry->list, &my_list);
	}

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

	return 0;
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("even629");
MODULE_DESCRIPTION("list test");

Run

~ # insmod list_test.ko
[   11.039661] list_test: loading out-of-tree module taints kernel.
[   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

Complete compilable project (including Makefile and QEMU runtime environment):linux_driver_learning/82_listEach data structure in this series has a corresponding example directory (82~87); the running method will not be explained individually in the rest of the text.

---

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, “before head” is logically equal to “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 doubly linked list variant. That is, when hashing the data to be stored, if a collision occurs, usethe linked list methodChain the conflicting data together for storage. Usually, the order of using elements in a hash table is: data storage —> data retrieval —> data deletion. Compared withlist_headthe difference is: the head node uses only onestruct hlist_head(single pointer), saving memory in the hash table array.

Its core design motivation is to solve the standard doubly circular linked listlist_headwhen used as a hash bucket, the existingmemory wasteandsemantic mismatchproblem.

Features	list_head(standard linked list)	hlist_head+hlist_node(hash linked list)
head node structure	full doubly linked pointers (next,prev)	only one singly linked pointer (first)
data node structure	doubly linked pointers (next,prev)	doubly linked pointers (next,pprev)
whether 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
};

pprevis of typestruct hlist_node **(pointer to pointer).
It stores not the “address of the previous node”, but “the memory address of the next field in the previous node”。

For the hlist chain head -> A -> B

• For node B in the middle of the list:B->pprev == &(A->next)
• For node A in the list:A->pprev == &(head->first)

This design makes deletion easy.

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;
}

Usage example(Hash table demonstration, excerpted from linux_driver_learning/83_hlist）：

// SPDX-License-Identifier: GPL-2.0
/* hlist_test.c -- the most typical application scenario of hlist: hash table */

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

/* Hash node: simulates a data structure with an embedded hlist_node in actual use */
struct hlist_item {
	int key;			/* key */
	int value;			/* value, simulating the payload */
	struct hlist_node node;		/* embedded hlist node */
};

/* Helper macro: get the parent structure pointer through the hlist_node pointer */
#define item_entry(ptr)  hlist_entry(ptr, struct hlist_item, node)

#define HASH_TABLE_SIZE  8

static void demo_hash_table(void)
{
	struct hlist_head hashtable[HASH_TABLE_SIZE];
	struct hlist_item *items;
	/* Carefully chosen key to ensure hash collisions */
	int keys[] = { 5, 13, 21, 8, 16, 24, 7, 15, 23, 6, 14, 22 };
	int n = ARRAY_SIZE(keys);
	int i;

	/* Initialize all hash buckets */
	for (i = 0; i < HASH_TABLE_SIZE; i++)
		INIT_HLIST_HEAD(&hashtable[i]);

	items = kcalloc(n, sizeof(*items), GFP_KERNEL);
	if (!items)
		return;

	/* Insertion phase: after taking the key modulo, put it into the corresponding bucket; on collision, use head insertion to form a chain. */
	for (i = 0; i < n; i++) {
		int hash = keys[i] % HASH_TABLE_SIZE;

		items[i].key = keys[i];
		items[i].value = keys[i] * 10;
		hlist_add_head(&items[i].node, &hashtable[hash]);
	}

	/* Print bucket layout: you can visually see the collision chain */
	for (i = 0; i < HASH_TABLE_SIZE; i++) {
		struct hlist_node *pos;
		int count = 0;

		pr_info("  bucket[%d]: ", i);
		hlist_for_each(pos, &hashtable[i]) {
			if (count > 0)
				pr_cont(" -> ");
			pr_cont("%d", item_entry(pos)->key);
			count++;
		}
		pr_cont("%s  (chain len: %d)\n", count ? "" : "(empty)", count);
	}

	/* Lookup phase: first locate the bucket, then traverse and compare on the collision chain. */
	{
		int key = 13;
		int hash = key % HASH_TABLE_SIZE;
		struct hlist_item *found = NULL;

		hlist_for_each_entry(found, &hashtable[hash], node) {
			if (found->key == key)
				break;
		}
		if (found && found->key == key)
			pr_info("  lookup key=%d: found! value=%d (bucket[%d])\n",
				key, found->value, hash);
	}

	/* Deletion phase: hlist_del is an O(1) operation; this is the power of pprev. */
	{
		int key = 13;
		int hash = key % HASH_TABLE_SIZE;
		struct hlist_item *target = NULL;

		hlist_for_each_entry(target, &hashtable[hash], node) {
			if (target->key == key)
				break;
		}
		if (target && target->key == key)
			hlist_del_init(&target->node);
	}

	/*
	 * hlist_move_list Before rehash application in：
	 * hash table expansion/When shrinking, the entire bucket's linked list O(1) is moved to a new bucket
	 */
	{
		struct hlist_head new_bucket;
		struct hlist_node *pos;

		INIT_HLIST_HEAD(&new_bucket);
		hlist_move_list(&hashtable[5], &new_bucket);

		pr_info("  new_bucket: ");
		hlist_for_each(pos, &new_bucket)
			pr_cont("%d ", item_entry(pos)->key);
		pr_cont("\n");
	}

	kfree(items);
}

static int __init hlist_test_init(void)
{
	demo_hash_table();
	return 0;
}

static void __exit hlist_test_exit(void)
{
	pr_info("hlist_test module exit\n");
}

module_init(hlist_test_init);
module_exit(hlist_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("hlist hashtable demo module");

Complete project:linux_driver_learning/83_hlist

---

rbtree — Red-black tree

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

• Each node is either black or red.
• The root node is black.
• Every leaf node (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 nodes contain the same number of black nodes. This property ensures that no path is twice as long as any other path, so the red-black tree is a relatively balanced binary tree.

All operations on the red-black tree must preserve its properties. Red-black trees are widely used, mainly to store ordered data. Their time complexity is O(log n), making them very efficient. 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 first glance, there seems to be no color field defined here, but that is a clever aspect of this red-black tree implementation.__rb_parent_colorThis field actually contains both the color information and the parent node pointer. Because this field is of type long, which requires alignment of sizeof(long), on typical 32-bit machines the lower two bits are always 0, so one of those bits can be used to represent the color.

The key is Memory Alignment：

• struct rb_nodeis required to besizeof(long)aligned.
• On 32-bit systems,sizeof(long) == 4, which means any validrb_nodepointer address must be a multiple of 4, i.e., the lowest binary 2 bits is always00。
• On 64-bit systems,sizeof(long) == 8, the lowest 3 bits is always000。

In fact, the least significant bit is used here to represent color information. The following operations on parent node pointers and color information are essentially all about__rb_parent_colorperforming bit operations.

#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, so it has one less indirection layer than traditional implementations (better cache locality). Eachstruct rb_nodeThe instance of the structure is embedded in the data structure it manages, so there is no need to use pointers to separaterb_nodeit and 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 red-black tree users to write.。

example

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/rbtree.h>
#include <linux/slab.h>
#include <linux/random.h>

struct my_node {
	struct rb_node rb;
	unsigned long data;
};

static struct rb_root my_tree = RB_ROOT;

#define my_rb_entry(ptr) rb_entry((ptr), struct my_node, rb)

/*
 * Find node - O(logn)
 */
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 = my_rb_entry(node);

		if (data < entry->data)
			node = node->rb_left;
		else if (data > entry->data)
			node = node->rb_right;
		else
			return entry;
	}
	return NULL;
}

/*
 * Insert node
 */
static bool my_rb_insert(struct rb_root *root, struct my_node *new_node)
{
	struct rb_node **link = &root->rb_node;
	struct rb_node *parent = NULL;
	unsigned long data = new_node->data;

	while (*link) {
		struct my_node *entry = my_rb_entry(*link);
		parent = *link;

		if (data < entry->data)
			link = &(*link)->rb_left;
		else if (data > entry->data)
			link = &(*link)->rb_right;
		else
			return false; /* The key already exists, no need to insert it again. */
	}

	rb_link_node(&new_node->rb, parent, link);
	rb_insert_color(&new_node->rb, root);
	return true;
}

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

/*
 * Destroy the entire tree
 */
static void my_rb_destroy(struct rb_root *root)
{
	struct rb_node *node;
	while ((node = rb_first_postorder(root))) {
		rb_erase(node, root);
		kfree(my_rb_entry(node));
	}
	*root = RB_ROOT;
}

static int __init rbtree_test_init(void)
{
	int i;
	unsigned long keys[] = { 1, 2, 3, 4, 5, 6, 7 };
	int count = ARRAY_SIZE(keys);

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

	/* Insertion 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("INSERT data=%lu OK\n", keys[i]);
		} else {
			pr_warn("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("SEARCH data=4 => %lu\n", found->data);
		else
			pr_warn("SEARCH data=4 => Not Found\n");

		found = my_rb_search(&my_tree, 99);
		if (found)
			pr_info("SEARCH data=99 => %lu\n", found->data);
		else
			pr_warn("SEARCH data=99 => Not Found\n");
	}
	/* Inorder traversal */
	{
		struct rb_node *node;

		pr_info("IN-ORDER TRAVERSAL:\n");

		for (node = rb_first(&my_tree); node; node = rb_next(node)) {
			struct my_node *entry = my_rb_entry(node);
			pr_info("    data=%lu\n", entry->data);
		}
	}
	/* Postorder traversal */
	{
		struct rb_node *node;

		pr_info("POST-ORDER TRAVERSAL:\n");

		for (node = rb_last(&my_tree); node; node = rb_prev(node)) {
			struct my_node *entry = my_rb_entry(node);
			pr_info("    data=%lu\n", entry->data);
		}
	}

	/* Get minimum/maximum node */
	{
		struct my_node *min = my_rb_entry(rb_first(&my_tree));
		struct my_node *max = my_rb_entry(rb_last(&my_tree));
		pr_info("    MIN=%lu MAX=%lu\n", min->data, max->data);
	}

	/* Deletion test */
	{
		struct my_node *to_del = my_rb_search(&my_tree, 4);
		if (to_del) {
			pr_info("ERASE data=4\n");
			my_rb_erase(&my_tree, to_del);
		}
	}

	/* Traverse in-order again to confirm the result. */
	{
		struct rb_node *node;

		pr_info("AFTER ERASE 4:\n");

		for (node = rb_first(&my_tree); node; node = rb_next(node)) {
			struct my_node *entry = my_rb_entry(node);
			pr_info("    data=%lu\n", entry->data);
		}
	}

	return 0;
}

static void __exit rbtree_test_exit(void)
{
	my_rb_destroy(&my_tree);
	pr_info("%s is called\n", __func__);
}

module_init(rbtree_test_init);
module_exit(rbtree_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("rbtree test");

Complete project:linux_driver_learning/84_rbtree

---

radix_tree — radix tree

xarrayThe predecessor, used for mapping integer IDs to pointers. Althoughxarrayhas gradually replaced it, but there is still a lot of code in the kernel that uses radix trees.

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

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);

It can be seenlinux-5.10.xIn it, xarray has already replaced it

example

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/init.h>
#include <linux/radix-tree.h>
#include <linux/slab.h>
#include <linux/spinlock.h>
#include <linux/rcupdate.h>

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 function wrappers */
static int safe_insert(unsigned long index, struct my_data *data)
{
	int ret;

	/* Preallocate node memory (may sleep) */
	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;
}

/* Lookup node RCU read-side safe */
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);
}

/* Use tags for batch marking and retrieval */
static void demo_tag_operations(void)
{
	struct my_data *d;
	void **slot;
	struct radix_tree_iter iter;

	pr_info("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);

	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);
                        continue;
                }
                if (d)
                        pr_info("TAGGED idex=%lu name=%s\n", iter.index, d->name);
	}
}

/* ========== 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 */

    /* --- Lookup 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 Unload: 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 passes in 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("test for radix_tree_test");

Complete project:linux_driver_learning/85_radix_tree

---

xarray — extensible array

xarrayIntroduced in Linux 4.20Next-generation replacement for the radix tree, providing from integer (unsigned long) to pointer mapping, 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 API:

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);
}

Complete module example(Excerpted from linux_driver_learning/86_xarray, the full version also includesxa_cmpxchgcompare-and-swap andxa_for_each_startdemonstration of starting-point traversal):

// SPDX-License-Identifier: GPL-2.0
/* xarray_test.c -- XArray complete API demo */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/xarray.h>
#include <linux/slab.h>

struct xa_node_data {
	int key;
	int value;
};

static int g_passed;
static int g_failed;

#define test_assert(cond, msg)  do {					\
	if (cond) {							\
		g_passed++;						\
		pr_info("  [PASS] %s\n", msg);				\
	} else {							\
		g_failed++;						\
		pr_err("  [FAIL] %s\n", msg);				\
	}								\
} while (0)

/* ========== Basic operations: load/store/erase ========== */
static void demo_basic_ops(void)
{
	struct xarray xa;
	struct xa_node_data *data, *old;

	xa_init(&xa);
	test_assert(xa_empty(&xa), "xa_init creates empty array");

	data = kmalloc(sizeof(*data), GFP_KERNEL);
	data->key = 42;
	data->value = 420;

	/* xa_store: returns old entry (first store returns NULL) */
	old = xa_store(&xa, 42, data, GFP_KERNEL);
	test_assert(old == NULL, "xa_store at empty index returns NULL");

	old = xa_load(&xa, 42);
	test_assert(old == data, "xa_load returns stored entry");

	/* Empty slot returns NULL */
	old = xa_load(&xa, 100);
	test_assert(old == NULL, "xa_load empty slot returns NULL");

	/* Sparse index: can directly store to a large index */
	data = kmalloc(sizeof(*data), GFP_KERNEL);
	data->key = 1000;
	data->value = 10000;
	xa_store(&xa, 1000, data, GFP_KERNEL);

	old = xa_load(&xa, 1000);
	test_assert(old && old->value == 10000, "sparse index (1000) works");

	/* xa_erase: returns the deleted entry */
	old = xa_erase(&xa, 42);
	test_assert(old && old->key == 42, "xa_erase returns erased entry");
	kfree(old);

	xa_erase(&xa, 1000);
	xa_destroy(&xa);
	test_assert(xa_empty(&xa), "xa_destroy leaves array empty");
}

/* ========== Value storage: small integers stored directly, no memory allocation needed ========== */
static void demo_store_value(void)
{
	struct xarray xa;
	void *entry;
	unsigned long val;

	xa_init(&xa);

	/*
	 * xa_mk_value / xa_to_value / xa_is_value
	 * Principle：Use the lowest bit of the pointer as tag（value entry of bit0 = 1）
	 */
	entry = xa_mk_value(12345);
	xa_store(&xa, 0, entry, GFP_KERNEL);

	entry = xa_load(&xa, 0);
	test_assert(xa_is_value(entry), "loaded entry is a value");
	val = xa_to_value(entry);
	test_assert(val == 12345, "value round-trip correct");

	xa_destroy(&xa);
}

/* ========== Mark mechanism: mark entry status, support traversal by mark ========== */
static void demo_mark_and_tag(void)
{
	struct xarray xa;
	struct xa_node_data *data, *d2, *d3, *found;
	unsigned long index;

	xa_init(&xa);

	/*
	 * 3 piece mark（XA_MARK_0/1/2），Typical applications：
	 * page cache Use mark represents dirty Status
	 */
	data = kmalloc(sizeof(*data), GFP_KERNEL);
	data->key = 1; data->value = 100;
	xa_store(&xa, 10, data, GFP_KERNEL);

	d2 = kmalloc(sizeof(*d2), GFP_KERNEL);
	d2->key = 2; d2->value = 200;
	xa_store(&xa, 20, d2, GFP_KERNEL);

	d3 = kmalloc(sizeof(*d3), GFP_KERNEL);
	d3->key = 3; d3->value = 300;
	xa_store(&xa, 30, d3, GFP_KERNEL);

	/* Set/query/clear mark */
	xa_set_mark(&xa, 10, XA_MARK_0);
	xa_set_mark(&xa, 30, XA_MARK_0);

	test_assert(xa_get_mark(&xa, 10, XA_MARK_0), "XA_MARK_0 set on index 10");
	test_assert(!xa_get_mark(&xa, 20, XA_MARK_0), "XA_MARK_0 not set on index 20");

	xa_clear_mark(&xa, 10, XA_MARK_0);
	test_assert(!xa_get_mark(&xa, 10, XA_MARK_0), "XA_MARK_0 cleared from index 10");

	/* Traverse by mark: only iterate entries with the specified mark set */
	xa_for_each_marked(&xa, index, found, XA_MARK_0)
		pr_info("    index=%lu, key=%d, value=%d\n",
			index, found->key, found->value);

	kfree(data);
	kfree(d2);
	kfree(d3);
	xa_destroy(&xa);
}

/* ========== xa_alloc automatically allocates free IDs (inode numbers, fd allocation) ========== */
static void demo_alloc(void)
{
	struct xarray xa;
	struct xa_node_data *data;
	u32 id;
	int ret, i;

	xa_init_flags(&xa, XA_FLAGS_ALLOC);

	for (i = 0; i < 5; i++) {
		data = kmalloc(sizeof(*data), GFP_KERNEL);
		data->key = i;
		data->value = i * 100;

		ret = xa_alloc(&xa, &id, data, XA_LIMIT(0, 100), GFP_KERNEL);
		test_assert(ret == 0, "xa_alloc succeeds");
		pr_info("  allocated id=%u for key=%d\n", id, i);
	}

	/* Delete one in the middle, and the next allocation should reuse it */
	data = xa_erase(&xa, 2);
	kfree(data);

	data = kmalloc(sizeof(*data), GFP_KERNEL);
	data->key = 99;
	data->value = 9900;
	xa_alloc(&xa, &id, data, XA_LIMIT(0, 100), GFP_KERNEL);
	test_assert(id == 2, "xa_alloc reuses freed id");

	for (i = 0; i <= 4; i++) {
		data = xa_load(&xa, i);
		if (data)
			xa_erase(&xa, i);
		kfree(data);
	}
	xa_destroy(&xa);
}

/* ========== Real-world scenario simulation: page cache index ========== */
static void demo_page_cache_simulation(void)
{
	struct xarray xa;
	struct xa_node_data *page;
	unsigned long index;
	int i, found_count = 0;
	unsigned long pages[] = { 0, 3, 7, 15, 100 };

	/*
	 * Simulate the kernel page cache core mechanism：
	 * - file's page cache Use XArray index（index = page offset）
	 * - Supports sparse access（A file can have hole）
	 * - Use mark Mark dirty page（Needs writeback）
	 */
	xa_init(&xa);

	for (i = 0; i < ARRAY_SIZE(pages); i++) {
		page = kmalloc(sizeof(*page), GFP_KERNEL);
		page->key = pages[i];
		page->value = pages[i] * 4096; /* Simulate page physical address */
		xa_store(&xa, pages[i], page, GFP_KERNEL);

		/* Simulate dirty page mark */
		if (i % 2 == 0)
			xa_set_mark(&xa, pages[i], XA_MARK_0);
	}

	/* Traverse all dirty pages (needing writeback) */
	xa_for_each_marked(&xa, index, page, XA_MARK_0)
		found_count++;
	test_assert(found_count == 3, "3 dirty pages (index 0,7,100)");

	/* Simulate truncate: delete pages with offset >= 7 */
	for (i = 0; i < ARRAY_SIZE(pages); i++) {
		if (pages[i] >= 7) {
			page = xa_erase(&xa, pages[i]);
			kfree(page);
		}
	}

	/* Cleanup */
	xa_for_each(&xa, index, page) {
		xa_erase(&xa, index);
		kfree(page);
	}
	xa_destroy(&xa);
}

static int __init xarray_test_init(void)
{
	demo_basic_ops();
	demo_store_value();
	demo_mark_and_tag();
	demo_alloc();
	demo_page_cache_simulation();

	pr_info("PASS: %d  FAIL: %d\n", g_passed, g_failed);
	return 0;
}

static void __exit xarray_test_exit(void)
{
	pr_info("xarray_test module exit\n");
}

module_init(xarray_test_init);
module_exit(xarray_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("xarray demo module");

Complete project:linux_driver_learning/86_xarray

---

plist — priority linked list

plistBeforelist_headBased on it, addedpriorityThe head always points to the highest-priority node (a smaller prio value means higher priority), often 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 are sorted by priority
};

Core API:

API	Description
plist_head_init(head)	Initialize
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 highest-priority node
plist_head_empty(head)	Check whether it is empty

Usage example(Excerpted from linux_driver_learning/87_plist）：

Note

kernel’splist_add()/plist_del()/plist_requeue()No export for module use, so they cannot be directly called within the module. The following example usesmy_plist_The prefix itself implements simplified insertion/deletion to demonstrate the two-level structure and sorting behavior of plist; the traversal/access macros in the header file (plist_for_each_entry、plist_first()etc.) can be used directly.

// SPDX-License-Identifier: GPL-2.0
/* plist_test.c -- Understanding the core principles of plist (priority linked list) */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/plist.h>
#include <linux/slab.h>

/*
 * my_plist_add: Insert node by priority（Simplified version，Kernel not export Original version）
 * algorithm：traverse node_list Find the first one. prio greater than or equal to the position of the new node，Insert before it
 * use >= Ensure that when priorities are equal, new nodes are inserted before existing nodes of the same priority.（LIFO，This is the kernel plist behavior）
 */
static void my_plist_add(struct plist_node *node, struct plist_head *head)
{
	struct list_head *pos;
	struct plist_node *iter;

	list_for_each(pos, &head->node_list) {
		iter = list_entry(pos, struct plist_node, node_list);
		if (iter->prio >= node->prio) {
			list_add_tail(&node->node_list, pos);
			return;
		}
	}
	/* Lowest priority, inserted at the end. */
	list_add_tail(&node->node_list, &head->node_list);
}

/* my_plist_del: O(1) deletion */
static void my_plist_del(struct plist_node *node, struct plist_head *head)
{
	list_del_init(&node->node_list);
}

/* my_plist_requeue: reorder after modifying priority (delete first, then insert) */
static void my_plist_requeue(struct plist_node *node, struct plist_head *head)
{
	if (!plist_node_empty(node))
		my_plist_del(node, head);
	my_plist_add(node, head);
}

/* Test Data Node */
struct plist_data {
	int id;
	int value;
	struct plist_node node;
};

/* ========== Basic Operations: add/del/iterate ========== */
static void demo_basic_ops(void)
{
	PLIST_HEAD(head);
	struct plist_data *d1, *d2, *d3, *pos;

	d1 = kmalloc(sizeof(*d1), GFP_KERNEL);
	d1->id = 1; d1->value = 100;
	plist_node_init(&d1->node, 10);		/* The smaller the value, the higher the priority. */

	d2 = kmalloc(sizeof(*d2), GFP_KERNEL);
	d2->id = 2; d2->value = 200;
	plist_node_init(&d2->node, 20);

	d3 = kmalloc(sizeof(*d3), GFP_KERNEL);
	d3->id = 3; d3->value = 300;
	plist_node_init(&d3->node, 30);

	/* Insert out of order; the final order is determined only by priority. */
	my_plist_add(&d2->node, &head);
	my_plist_add(&d1->node, &head);
	my_plist_add(&d3->node, &head);

	/* plist_first returns the node with the highest priority. */
	pr_info("  first prio=%d, last prio=%d\n",
		plist_first(&head)->prio, plist_last(&head)->prio);

	/* Traverse from highest to lowest priority. */
	plist_for_each_entry(pos, &head, node) {
		pr_info("    id=%d, prio=%d, value=%d\n",
			pos->id, pos->node.prio, pos->value);
	}

	my_plist_del(&d1->node, &head);
	my_plist_del(&d2->node, &head);
	my_plist_del(&d3->node, &head);
	kfree(d1); kfree(d2); kfree(d3);
}

/* ========== Dynamically modifying priority (requeue) ========== */
static void demo_requeue(void)
{
	PLIST_HEAD(head);
	struct plist_data d1, d2, d3;

	plist_node_init(&d1.node, 10);
	plist_node_init(&d2.node, 20);
	plist_node_init(&d3.node, 30);

	my_plist_add(&d1.node, &head);
	my_plist_add(&d2.node, &head);
	my_plist_add(&d3.node, &head);

	/* Initial order: d1(10) > d2(20) > d3(30) */

	/* Change d1 from prio 10 to prio 40 (lowest) and re-sort. */
	d1.node.prio = 40;
	my_plist_requeue(&d1.node, &head);

	/* New order: d2(20) > d3(30) > d1(40) */
	pr_info("  after requeue d1 10->40, first prio=%d, last prio=%d\n",
		plist_first(&head)->prio, plist_last(&head)->prio);

	my_plist_del(&d1.node, &head);
	my_plist_del(&d2.node, &head);
	my_plist_del(&d3.node, &head);
}

/* ========== Real-world scenario simulation: RT scheduler pushable_tasks ========== */
static void demo_rt_sched_pushable(void)
{
	/*
	 * Simulate the kernel RT scheduler's pushable_tasks：
	 * - each RT task has a pushable_node，sorted by priority
	 * - to quickly find the highest-priority pushable task（the next one to migrate to another CPU task）
	 */
	PLIST_HEAD(pushable_tasks);
	struct plist_data tasks[5];
	int prios[] = { 50, 30, 70, 10, 90 };
	int i;

	for (i = 0; i < 5; i++) {
		tasks[i].id = (i + 1) * 100;
		tasks[i].value = prios[i];
		plist_node_init(&tasks[i].node, prios[i]);
		my_plist_add(&tasks[i].node, &pushable_tasks);
	}

	/* Get the highest-priority pushable task */
	pr_info("  Highest prio pushable task: id=%d, prio=%d\n",
		plist_first_entry(&pushable_tasks, struct plist_data, node)->id,
		plist_first(&pushable_tasks)->prio);

	/* Simulate re-sorting after a task dynamically raises its priority. */
	tasks[2].node.prio = 5;
	my_plist_requeue(&tasks[2].node, &pushable_tasks);
	pr_info("  after requeue task300 70->5, first task id=%d\n",
		plist_first_entry(&pushable_tasks, struct plist_data, node)->id);

	for (i = 0; i < 5; i++)
		my_plist_del(&tasks[i].node, &pushable_tasks);
}

static int __init plist_test_init(void)
{
	demo_basic_ops();
	demo_requeue();
	demo_rt_sched_pushable();
	return 0;
}

static void __exit plist_test_exit(void)
{
	pr_info("plist_test module exit\n");
}

module_init(plist_test_init);
module_exit(plist_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("plist demo module");

Complete project:linux_driver_learning/87_plist. The actual users of plist in the kernel are the RT scheduler’spushable_tasks（kernel/sched/rt.c) and rt_mutex’s PI chain, which can be read side by side.

---

llist — lock-less linked list

llist(lock-less list) is alock-free singly linked list, implemented based on CAS operations, and in specific scenarios (such as interrupt and process sharing data) performs better than spinlock +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 API:

API	Description
llist_add(new, head)	Head insertion (lock-free)
llist_del_all(head)	Atomically detach the entire list
llist_del_first(head)	Delete the first node
llist_empty(head)	Check whether it is empty

Typical pattern:

// SPDX-License-Identifier: GPL-2.0
/* llist_test.c -- Lock-free singly linked list: producers accumulate without locking, consumers atomically reap */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/llist.h>
#include <linux/slab.h>

struct llist_item {
	int val;
	struct llist_node node;
};

static LLIST_HEAD(my_llist);

static int __init llist_test_init(void)
{
	struct llist_item *items[5], *pos, *n;
	struct llist_node *list;
	int i;

	/* Producer: head insertion, lock-free (also applicable in interrupt context) */
	for (i = 0; i < 5; i++) {
		items[i] = kmalloc(sizeof(*items[i]), GFP_KERNEL);
		items[i]->val = i;
		llist_add(&items[i]->node, &my_llist);
	}

	/* Consumer: atomically detach the entire list, then process it at leisure */
	list = llist_del_all(&my_llist);

	/* Note that the traversal order is the reverse of the insertion order (a characteristic of head insertion) */
	llist_for_each_entry_safe(pos, n, list, node) {
		pr_info("  val=%d\n", pos->val);
		kfree(pos);
	}

	pr_info("  llist empty: %s\n", llist_empty(&my_llist) ? "yes" : "no");
	return 0;
}

static void __exit llist_test_exit(void)
{
	pr_info("llist_test module exit\n");
}

module_init(llist_test_init);
module_exit(llist_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("llist demo module");

---

rhashtable — resizable hash table

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

Header file:<linux/rhashtable.h>

Core API:

API	Description
rhashtable_init(ht, params)	Initialize
rhashtable_insert_slow(ht, key, obj)	Insert
rhashtable_lookup(ht, key, params)	Lookup
rhashtable_remove(ht, obj, params)	Delete
rhashtable_free_and_destroy(ht, fn, data)	Destroy

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* rhashtable_test.c -- Auto-scaling RCU hash table */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/rhashtable.h>
#include <linux/slab.h>

struct my_obj {
	int key;
	int value;
	struct rhash_head node;		/* Link into hash bucket */
};

/* Describe the position of key/head in the host structure */
static const struct rhashtable_params my_params = {
	.key_offset		= offsetof(struct my_obj, key),
	.head_offset		= offsetof(struct my_obj, node),
	.key_len		= sizeof(int),
	.automatic_shrinking	= true,
};

static struct rhashtable my_ht;

/* Lookup: read-side RCU lock-free */
static struct my_obj *my_lookup(int key)
{
	struct my_obj *obj;

	rcu_read_lock();
	obj = rhashtable_lookup(&my_ht, &key, my_params);
	rcu_read_unlock();
	return obj;
}

static void my_free(void *ptr, void *arg)
{
	kfree(ptr);
}

static int __init rhashtable_test_init(void)
{
	struct my_obj *obj, *found;
	int i;

	rhashtable_init(&my_ht, &my_params);

	for (i = 1; i <= 100; i++) {
		obj = kmalloc(sizeof(*obj), GFP_KERNEL);
		obj->key = i * 10;
		obj->value = i;
		rhashtable_insert_fast(&my_ht, &obj->node, my_params);
	}
	pr_info("  inserted 100 keys, nelems=%d\n", atomic_read(&my_ht.nelems));

	found = my_lookup(500);
	pr_info("  lookup 500 => value=%d\n", found ? found->value : -1);

	/* Delete and free */
	rhashtable_remove_fast(&my_ht, &found->node, my_params);
	kfree(found);

	found = my_lookup(500);
	pr_info("  lookup 500 after remove => %s\n", found ? "found" : "not found");

	return 0;
}

static void __exit rhashtable_test_exit(void)
{
	rhashtable_free_and_destroy(&my_ht, my_free, NULL);
	pr_info("rhashtable_test module exit\n");
}

module_init(rhashtable_test_init);
module_exit(rhashtable_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("rhashtable demo module");

Typical applications in the kernel:

• Network namespace connection tracking table
• XFRM security policy database
• Hash-type implementation of BPF maps

---

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), very efficient for VMA lookup, traversal, and gap search.

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 API:

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

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* maple_tree_test.c -- interval mapping and traversal (same structure as VMA management) */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/maple_tree.h>

static struct maple_tree my_mt;

static int __init maple_test_init(void)
{
	MA_STATE(mas, &my_mt, 0, 0);
	unsigned long index = 35;
	void *entry;

	mt_init(&my_mt);

	/* Write: mas_store maps the [index, last] interval to entry */
	mtree_lock(&my_mt);
	mas_set_range(&mas, 0, 9);
	mas_store(&mas, (void *)1UL);
	mas_set_range(&mas, 10, 19);
	mas_store(&mas, (void *)2UL);
	mas_set_range(&mas, 40, 49);
	mas_store(&mas, (void *)3UL);		/* Leave a gap in the middle 20~39 */
	mtree_unlock(&my_mt);

	/* mas_for_each iterates over all non-empty intervals */
	mtree_lock(&my_mt);
	mas_for_each(&mas, entry, ULONG_MAX)
		pr_info("  [%lu - %lu] -> entry %lu\n",
			mas.index, mas.last, (unsigned long)entry);
	mtree_unlock(&my_mt);

	/* mt_find: find the first non-empty entry starting from index and advance index */
	entry = mt_find(&my_mt, &index, ULONG_MAX);
	pr_info("  mt_find from 35 => found at %lu, entry %lu\n",
		index, (unsigned long)entry);

	/* Delete the interval containing index 10 */
	mtree_lock(&my_mt);
	mas_set(&mas, 10);
	entry = mas_erase(&mas);
	mtree_unlock(&my_mt);
	pr_info("  erased entry %lu\n", (unsigned long)entry);

	return 0;
}

static void __exit maple_test_exit(void)
{
	mtree_destroy(&my_mt);
	pr_info("maple_test module exit\n");
}

module_init(maple_test_init);
module_exit(maple_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("maple tree demo module");

Typical applications in the kernel:

• VMA management: Linux 6.1+ usesmaple_treereplaces 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

The interval tree is an augmented red-black tree used to managerange([start, last]), supports 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 the subtree (augmented information)
};

Core API:

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

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* interval_tree_test.c -- interval insertion and overlap lookup */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/interval_tree.h>

static struct rb_root_cached my_tree = RB_ROOT_CACHED;
static struct interval_tree_node nodes[4];

static int __init interval_tree_test_init(void)
{
	unsigned long ranges[][2] = { {0, 9}, {10, 19}, {15, 24}, {40, 49} };
	struct interval_tree_node *node;
	int i;

	/* Insertion: note that 10~19 and 15~24 partially overlap */
	for (i = 0; i < 4; i++) {
		nodes[i].start = ranges[i][0];
		nodes[i].last = ranges[i][1];
		interval_tree_insert(&nodes[i], &my_tree);
	}

	/* Find all intervals overlapping [16, 20]: expect 10-19 and 15-24 */
	pr_info("  overlaps with [16, 20]:\n");
	for (node = interval_tree_iter_first(&my_tree, 16, 20); node;
	     node = interval_tree_iter_next(node, 16, 20))
		pr_info("    [%lu - %lu]\n", node->start, node->last);

	/* Find again after deleting an interval */
	interval_tree_remove(&nodes[1], &my_tree);

	pr_info("  overlaps after removing [10, 19]:\n");
	for (node = interval_tree_iter_first(&my_tree, 16, 20); node;
	     node = interval_tree_iter_next(node, 16, 20))
		pr_info("    [%lu - %lu]\n", node->start, node->last);

	return 0;
}

static void __exit interval_tree_test_exit(void)
{
	pr_info("interval_tree_test module exit\n");
}

module_init(interval_tree_test_init);
module_exit(interval_tree_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("interval tree demo module");

Typical applications in the kernel:

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

---

klist — kernel object linked list

klistis anlist_heada wrapper for, andkobjectUsed in conjunction with the system, it provides get/put reference count protection: when traversing the linked list, it automatically acquires a reference to the node object, preventing the node from being released during traversal.

Header file:<linux/klist.h>

Data structure:

struct klist_node {
    void            *n_klist;   // Fields 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 API:

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 (automatic get/put)
klist_iter_exit(i)	Clean up iterator

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* klist_test.c -- kernel object linked list with reference count protection */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/klist.h>
#include <linux/slab.h>

struct my_kitem {
	int id;
	struct klist_node n;
};

/* get/put callbacks are NULL: nodes are managed manually by us */
static struct klist my_klist = KLIST_INIT(my_klist, NULL, NULL);

static int __init klist_test_init(void)
{
	struct my_kitem *items[3];
	struct klist_iter iter;
	struct klist_node *kn;
	int i;

	for (i = 0; i < 3; i++) {
		items[i] = kmalloc(sizeof(*items[i]), GFP_KERNEL);
		items[i]->id = i;
		klist_add_tail(&items[i]->n, &my_klist);
	}

	/* Iterator traversal: klist_next automatically gets a reference to the returned node,
	 * preventing the node from being freed by other CPU release */
	klist_iter_init(&my_klist, &iter);
	while ((kn = klist_next(&iter)) != NULL) {
		struct my_kitem *item = container_of(kn, struct my_kitem, n);
		pr_info("  id=%d\n", item->id);
	}
	klist_iter_exit(&iter);

	/* Delete middle node */
	klist_del(&items[1]->n);
	kfree(items[1]);

	klist_iter_init(&my_klist, &iter);
	while ((kn = klist_next(&iter)) != NULL)
		pr_info("  after del: id=%d\n",
			container_of(kn, struct my_kitem, n)->id);
	klist_iter_exit(&iter);

	klist_del(&items[0]->n);
	kfree(items[0]);
	klist_del(&items[2]->n);
	kfree(items[2]);

	return 0;
}

static void __exit klist_test_exit(void)
{
	pr_info("klist_test module exit\n");
}

module_init(klist_test_init);
module_exit(klist_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("klist demo module");

Typical applications in the kernel:

• In the device driver modelbus_typedevice list
• In the device driver modeldriverdevice list

---

ID, Bitmaps, and DMA

idr — ID Allocator

idrprovideInteger ID to PointerA mapping from integer IDs to pointers, automatically allocating a unique integer ID and associating it with a pointer. Suitable for scenarios requiring “an integer handle”.

Header file:<linux/idr.h>

Core API (modern interface):

API	Description
idr_alloc(idr, ptr, start, end, gfp)	Allocate an ID and associate a pointer
idr_find(idr, id)	Look up a pointer by ID
idr_remove(idr, id)	Remove an ID mapping
idr_for_each(idr, fn, data)	Iterate over all entries
idr_destroy(idr)	Destroy an idr
idr_init(idr)	Initialize

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* idr_test.c -- Mapping integer IDs to pointers */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/idr.h>

static DEFINE_IDR(my_idr);

static int my_idr_cb(int id, void *ptr, void *data)
{
	pr_info("  id=%d -> obj%lu\n", id, (unsigned long)ptr);
	return 0;	/* Return non-zero to terminate iteration */
}

static int __init idr_test_init(void)
{
	void *p;
	int id, i;

	/* Allocate an ID and associate a pointer: range [1, 100) */
	for (i = 1; i <= 3; i++) {
		id = idr_alloc(&my_idr, (void *)(unsigned long)i, 1, 100, GFP_KERNEL);
		pr_info("  allocated id=%d -> obj%d\n", id, i);
	}

	/* Allocate another ID: idr does not deduplicate pointers; the same pointer can be associated with multiple IDs */
	id = idr_alloc(&my_idr, (void *)4UL, 1, 100, GFP_KERNEL);
	pr_info("  allocated id=%d -> obj4\n", id);

	p = idr_find(&my_idr, 2);
	pr_info("  idr_find(2) => obj%lu\n", (unsigned long)p);

	/* Iterate over all entries */
	idr_for_each(&my_idr, my_idr_cb, NULL);

	/* After deletion, the ID can be reused */
	idr_remove(&my_idr, 2);
	p = idr_find(&my_idr, 2);
	pr_info("  idr_find(2) after remove => %s\n", p ? "found" : "NULL");

	id = idr_alloc(&my_idr, (void *)5UL, 1, 100, GFP_KERNEL);
	pr_info("  next alloc reuses lowest free id=%d\n", id);

	return 0;
}

static void __exit idr_test_exit(void)
{
	idr_destroy(&my_idr);
	pr_info("idr_test module exit\n");
}

module_init(idr_test_init);
module_exit(idr_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("idr demo module");

Typical applications in the kernel:

• Process PID management
• Device minor number allocation
• Handle management in GPU DRM drivers (GEM buffer handle)

---

ida — IDA Allocator

idaYesidrA simplified version of the IDA allocator, it only allocates integer IDs without associating pointers (use when you only need unique integer IDs; lower memory overhead).

Header file:<linux/idr.h>

Core API:

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

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* ida_test.c -- only allocate unique integer IDs (not associated with pointers) */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/idr.h>

static DEFINE_IDA(my_ida);

static int __init ida_test_init(void)
{
	int ids[5];
	int id, i;

	for (i = 0; i < 5; i++) {
		ids[i] = ida_alloc(&my_ida, GFP_KERNEL);
		pr_info("  allocated id=%d\n", ids[i]);
	}

	/* Free the middle id=2, creating a hole */
	ida_free(&my_ida, ids[2]);
	pr_info("  freed id=%d\n", ids[2]);

	/* Next allocation reuses the smallest hole */
	id = ida_alloc(&my_ida, GFP_KERNEL);
	pr_info("  next id=%d (reuses hole)\n", id);
	ida_free(&my_ida, id);

	/* Range allocation: within [100, 200) */
	id = ida_alloc_range(&my_ida, 100, 200, GFP_KERNEL);
	pr_info("  range alloc id=%d\n", id);

	return 0;
}

static void __exit ida_test_exit(void)
{
	ida_destroy(&my_ida);
	pr_info("ida_test module exit\n");
}

module_init(ida_test_init);
module_exit(ida_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("ida demo module");

---

bitmap / cpumask — bitmap

For kernel useunsigned longArray-based bitmap, providing an efficient set of bit operations.cpumaskIt is a 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
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 whether a CPU is in the mask
for_each_cpu(cpu, mask)	Iterate over CPUs in the mask
cpumask_of(cpu)	Get the 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

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* bitmap_test.c -- bitmap operations and cpumask traversal */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/bitmap.h>
#include <linux/cpumask.h>
#include <linux/smp.h>

static int __init bitmap_test_init(void)
{
	DECLARE_BITMAP(my_bitmap, 64);
	cpumask_var_t cpu_mask;
	int bit, cpu;

	/* bitmap: set bits 3~6, then check bit by bit */
	bitmap_zero(my_bitmap, 64);
	bitmap_set(my_bitmap, 3, 4);

	for_each_set_bit(bit, my_bitmap, 64)
		pr_info("  bit %d set\n", bit);

	/* Find 4 consecutive free bits: expected 7 */
	bit = bitmap_find_next_zero_area(my_bitmap, 64, 0, 4, 0);
	pr_info("  next free area of 4 bits at %d\n", bit);

	/* cpumask: iterate after removing CPU0 from the online CPU mask */
	if (!alloc_cpumask_var(&cpu_mask, GFP_KERNEL))
		return -ENOMEM;

	cpumask_copy(cpu_mask, cpu_online_mask);
	cpumask_clear_cpu(0, cpu_mask);

	for_each_cpu(cpu, cpu_mask)
		pr_info("  cpu %d online (except cpu0)\n", cpu);

	free_cpumask_var(cpu_mask);
	return 0;
}

static void __exit bitmap_test_exit(void)
{
	pr_info("bitmap_test module exit\n");
}

module_init(bitmap_test_init);
module_exit(bitmap_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("bitmap/cpumask demo module");

Typical applications in the kernel:

• IRQ affinity setting (specify which CPUs handle interrupts)
• process’scpus_allowed(set which CPUs the process can run on)
• Memory node’s DMA mask

---

scatterlist — scatter table

scatterlistused to describenon-contiguous memory regions, extremely common 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 API:

API	Description
sg_init_one(sg, buf, len)	Initialize single-entry sg
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:

// SPDX-License-Identifier: GPL-2.0
/* scatterlist_test.c -- description and traversal of non-contiguous memory segments */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/scatterlist.h>
#include <linux/mm.h>

static int __init sg_test_init(void)
{
	struct scatterlist sg[3];
	struct scatterlist *s;
	struct page *page;
	char buf[32];
	int i;

	/* Initialize table (mark end at the end) */
	sg_init_table(sg, 3);

	/* Entry 0: describe a virtually contiguous buffer allocated by kmalloc/vmalloc */
	sg_set_buf(&sg[0], buf, sizeof(buf));

	/* Entry 1: directly describe a physical page */
	page = alloc_page(GFP_KERNEL);
	if (!page)
		return -ENOMEM;
	sg_set_page(&sg[1], page, PAGE_SIZE, 0);

	/* Entry 2: left empty, forming an "initialized but unused" slot */

	for_each_sg(sg, s, 3, i)
		pr_info("  sg[%d]: length=%u offset=%u\n",
			i, s->length, s->offset);

	__free_page(page);

	/*
	 * Real DMA In scenarios，Before initiating transfer, mapping is also required：
	 *   nents = dma_map_sg(dev, sg, 3, DMA_TO_DEVICE);
	 * After completion：dma_unmap_sg(dev, sg, 3, DMA_TO_DEVICE);
	 * The mapping fills in for each entry dma_address，for DMA engine use
	 */
	return 0;
}

static void __exit sg_test_exit(void)
{
	pr_info("sg_test module exit\n");
}

module_init(sg_test_init);
module_exit(sg_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("scatterlist demo module");

Typical applications in the kernel:

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

Concurrency and synchronization

atomic_t — atomic variable

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

Header file:<linux/atomic.h>

Data structure:

typedef struct {
    int counter;
} atomic_t;

Core API:

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

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* atomic_test.c -- atomic variables: counting, dec_and_test and CAS */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/atomic.h>

static atomic_t counter = ATOMIC_INIT(0);

static int __init atomic_test_init(void)
{
	int old;

	atomic_inc(&counter);
	atomic_add(10, &counter);
	pr_info("  read=%d\n", atomic_read(&counter));

	/* dec_and_test: decrement and test if it reaches 0
	 * Typical usage：Trigger cleanup when the reference count reaches zero */
	atomic_set(&counter, 2);
	while (!atomic_dec_and_test(&counter))
		pr_info("  not zero yet: %d\n", atomic_read(&counter));
	pr_info("  reached zero\n");

	/* cmpxchg: CAS atomic update (foundation of lock-free programming) */
	old = atomic_read(&counter);		/* 0 */
	if (atomic_cmpxchg(&counter, old, 42) == old)
		pr_info("  cas ok, now=%d\n", atomic_read(&counter));

	/* xchg: atomic exchange */
	old = atomic_xchg(&counter, 100);
	pr_info("  xchg: old=%d, now=%d\n", old, atomic_read(&counter));

	return 0;
}

static void __exit atomic_test_exit(void)
{
	pr_info("atomic_test module exit\n");
}

module_init(atomic_test_init);
module_exit(atomic_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("atomic_t demo module");

Typical applications in the kernel:

• Reference counting (driver open count)
• Statistical counters (network packet counting, interrupt counting)
• Simple lock-free flags

---

kref / refcount_t — reference counting

kref

Wrapperrefcount_t, provides object reference count management, andreleasea callback automatically releases 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_tYesatomic_tAn enhanced version, providing overflow protection — once the maximum value is reached, it no longer increases, avoiding use-after-free vulnerabilities caused by reference count overflow.

Header file:<linux/refcount.h>

typedef struct refcount_struct {
    atomic_t refs;
} refcount_t;

Typical usage pattern:

// SPDX-License-Identifier: GPL-2.0
/* kref_test.c -- reference counting: automatically release when count reaches zero */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/kref.h>
#include <linux/slab.h>

struct my_object {
	struct kref kref;
	int data;
};

/* release callback: called when the last reference is released */
static void my_object_release(struct kref *kref)
{
	struct my_object *obj = container_of(kref, struct my_object, kref);

	pr_info("  release: refcount hit 0, freeing object\n");
	kfree(obj);
}

static struct my_object *my_object_get(struct my_object *obj)
{
	kref_get(&obj->kref);	/* Reference +1, never fails */
	return obj;
}

static void my_object_put(struct my_object *obj)
{
	kref_put(&obj->kref, my_object_release);	/* Reference -1, release when it reaches 0 */
}

static int __init kref_test_init(void)
{
	struct my_object *obj, *alias;

	obj = kzalloc(sizeof(*obj), GFP_KERNEL);
	if (!obj)
		return -ENOMEM;
	obj->data = 42;
	kref_init(&obj->kref);			/* Reference = 1 */
	pr_info("  created, refcount=%u\n", refcount_read(&obj->kref.refcount));

	alias = my_object_get(obj);		/* Reference = 2 */
	pr_info("  after get, refcount=%u\n", refcount_read(&obj->kref.refcount));

	my_object_put(alias);			/* Reference = 1, object still alive */
	pr_info("  after put, refcount=%u\n", refcount_read(&obj->kref.refcount));

	my_object_put(obj);			/* Reference count = 0, trigger release */
	pr_info("  object freed\n");

	return 0;
}

static void __exit kref_test_exit(void)
{
	pr_info("kref_test module exit\n");
}

module_init(kref_test_init);
module_exit(kref_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("kref demo module");

Typical applications in the kernel:

• struct kobjectreference count of
• struct devicelifecycle management of
• file descriptor (struct file）
• almost all kernel objects that need lifecycle management

---

spinlock_t — spinlock

Linux kernel’s most basicbusy-wait lock, used to protect short critical sections in SMP systems. When the holder is spinning on one CPU, executors on other CPUs are also spinning waiting.

Header file:<linux/spinlock.h>

Data structure (simplified):

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

Core API:

API	Description
spin_lock_init(lock)	Dynamic initialization
DEFINE_SPINLOCK(lock)	Static definition + initialization
spin_lock(lock)	Acquire lock (disable kernel preemption)
spin_unlock(lock)	Release lock
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 halves
spin_trylock(lock)	Try to acquire lock (non-blocking)
spin_is_locked(lock)	Check lock status

warning

While holding a spinlockMust never sleep(cannot callkmalloc(GFP_KERNEL)、copy_from_useroperations that may block, etc.). 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

Usage example(Two kernel threads compare ‘race without locking vs correct with locking’):

// SPDX-License-Identifier: GPL-2.0
/* spinlock_test.c -- Use race experiments to compare results with and without spinlocks */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/spinlock.h>
#include <linux/kthread.h>
#include <linux/completion.h>
#include <linux/delay.h>

#define LOOPS 100000

static DEFINE_SPINLOCK(my_lock);
static int counter;
static DECLARE_COMPLETION(worker_done);

static int worker_fn(void *arg)
{
	bool use_lock = (bool)(unsigned long)arg;
	int i;

	for (i = 0; i < LOOPS; i++) {
		if (use_lock) {
			spin_lock(&my_lock);
			counter++;	/* Critical section: only short non-sleeping operations are allowed */
			spin_unlock(&my_lock);
		} else {
			counter++;	/* Non-atomic read-modify-write, race condition exists */
		}
	}
	complete(&worker_done);
	return 0;
}

static void run_pair(bool use_lock, const char *label)
{
	counter = 0;
	reinit_completion(&worker_done);

	kthread_run(worker_fn, (void *)(unsigned long)use_lock, "spin_worker_a");
	kthread_run(worker_fn, (void *)(unsigned long)use_lock, "spin_worker_b");

	wait_for_completion(&worker_done);
	wait_for_completion(&worker_done);

	pr_info("  %s: counter=%d (expect %d)\n", label, counter, LOOPS * 2);
}

static int __init spinlock_test_init(void)
{
	run_pair(false, "without lock");
	run_pair(true,  "with lock   ");
	return 0;
}

static void __exit spinlock_test_exit(void)
{
	pr_info("spinlock_test module exit\n");
}

module_init(spinlock_test_init);
module_exit(spinlock_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("spinlock demo module");

---

mutex — mutual exclusion lock

Unlike spinlocks,mutexwhen the lock cannot be acquired, it yields the CPU and sleeps, 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;  // Wait queue
    // ...
};

Core API:

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

warning

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

spinlock vs mutex selection:

	spinlock	mutex
When unable to acquire	Spin-wait	Sleep and yield CPU
Critical section	Short (nanoseconds)	Can be longer (milliseconds)
Can sleep?	Absolutely not	OK
Interrupt context	Available	Not available
System overhead	Low	Higher (involves scheduling)

Usage example(Sleeping is allowed in the critical section, which is the essential difference between mutex and spinlock):

// SPDX-License-Identifier: GPL-2.0
/* mutex_test.c -- mutex protects a sleepable critical section */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/mutex.h>
#include <linux/kthread.h>
#include <linux/completion.h>
#include <linux/delay.h>

static DEFINE_MUTEX(my_mutex);
static int shared_counter;
static DECLARE_COMPLETION(worker_done);

static int worker_fn(void *arg)
{
	int i;

	for (i = 0; i < 5; i++) {
		mutex_lock(&my_mutex);

		/* Sleeping is allowed in the critical section (absolutely not allowed with spinlock) */
		shared_counter++;
		msleep(10);	/* Simulate a time-consuming sleepable operation */

		mutex_unlock(&my_mutex);
	}
	complete(&worker_done);
	return 0;
}

static int __init mutex_test_init(void)
{
	kthread_run(worker_fn, NULL, "mutex_worker_a");
	kthread_run(worker_fn, NULL, "mutex_worker_b");

	wait_for_completion(&worker_done);
	wait_for_completion(&worker_done);

	pr_info("  final counter=%d (expect 10)\n", shared_counter);
	return 0;
}

static void __exit mutex_test_exit(void)
{
	pr_info("mutex_test module exit\n");
}

module_init(mutex_test_init);
module_exit(mutex_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("mutex demo module");

---

completion — completion variable

completionis implemented in the kernelone thread waits for another thread to complete a taska synchronization mechanism that is more lightweight and has clearer semantics than semaphores.

Header file:<linux/completion.h>

Data structure:

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

Core API:

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 signals)
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:

// SPDX-License-Identifier: GPL-2.0
/* completion_test.c -- one thread waits for another thread to complete a task */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/completion.h>
#include <linux/kthread.h>
#include <linux/delay.h>

static DECLARE_COMPLETION(work_done);

static int worker_fn(void *arg)
{
	msleep(100);	/* Simulate a time-consuming task */

	pr_info("  worker: task done\n");
	complete(&work_done);		/* Use complete for a one-time event */
	/* If there are multiple waiters, use complete_all() */
	return 0;
}

static int __init completion_test_init(void)
{
	struct task_struct *tsk;

	tsk = kthread_run(worker_fn, NULL, "comp_worker");
	if (IS_ERR(tsk))
		return PTR_ERR(tsk);

	pr_info("  main: waiting for worker...\n");
	wait_for_completion(&work_done);	/* Block until complete */
	pr_info("  main: worker finished, continue\n");

	return 0;
}

static void __exit completion_test_exit(void)
{
	pr_info("completion_test module exit\n");
}

module_init(completion_test_init);
module_exit(completion_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("completion demo module");

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 scenarios with more reads and fewer writes. Readers are completely lock-free; writers copy first, 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 API:

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 reclamation

Typical pattern:

// SPDX-License-Identifier: GPL-2.0
/* rcu_test.c -- lock-free readers, copy-update writers, deferred release */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/rcupdate.h>
#include <linux/slab.h>

struct rcu_item {
	int version;
	struct rcu_head rcu;
};

static struct rcu_item __rcu *global_item;

/* Reader: completely lock-free, only marks the critical section range */
static int rcu_lookup(int *version)
{
	struct rcu_item *item;

	rcu_read_lock();
	item = rcu_dereference(global_item);	/* Read paired with the publishing side */
	if (item)
		*version = item->version;
	rcu_read_unlock();
	return item ? 0 : -1;
}

static int __init rcu_test_init(void)
{
	struct rcu_item *item, *old;
	int v = -1;

	/* Publish v1 */
	item = kzalloc(sizeof(*item), GFP_KERNEL);
	item->version = 1;
	rcu_assign_pointer(global_item, item);	/* Guarantee initialization before publication */

	rcu_lookup(&v);
	pr_info("  after publish: version=%d
", v);

	/* Update to v2: allocate new copy -> atomic replace -> defer release of old copy */
	item = kzalloc(sizeof(*item), GFP_KERNEL);
	item->version = 2;
	old = rcu_access_pointer(global_item);
	rcu_assign_pointer(global_item, item);
	kfree_rcu(old, rcu);	/* The old object is actually freed only after the grace period ends */

	rcu_lookup(&v);
	pr_info("  after update: version=%d
", v);

	return 0;
}

static void __exit rcu_test_exit(void)
{
	/* synchronize_rcu waits for all readers to exit before releasing */
	synchronize_rcu();
	kfree_rcu(rcu_dereference_raw(global_item), rcu);
	pr_info("rcu_test module exit
");
}

module_init(rcu_test_init);
module_exit(rcu_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("rcu demo module");

Typical applications in the kernel:

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

---

---

Waiting and scheduling

wait_queue — wait queue

A wait queue is a more general waiting mechanism: a process adds itself to the wait queue and then sleeps, 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 API:

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)	Interruptible wait
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:

// SPDX-License-Identifier: GPL-2.0
/* waitqueue_test.c -- kernel thread blocks waiting, woken up by an event */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/wait.h>
#include <linux/kthread.h>
#include <linux/completion.h>
#include <linux/delay.h>

static DECLARE_WAIT_QUEUE_HEAD(my_wq);
static int data_ready;
static DECLARE_COMPLETION(waiter_done);

static int waiter_fn(void *arg)
{
	pr_info("  waiter: going to sleep\n");

	/* Block until data_ready != 0 (automatically re-check condition after being woken up) */
	wait_event_interruptible(my_wq, data_ready != 0);

	pr_info("  waiter: woken up, data_ready=%d\n", data_ready);
	complete(&waiter_done);
	return 0;
}

static int __init waitqueue_test_init(void)
{
	kthread_run(waiter_fn, NULL, "wq_waiter");

	msleep(100);	/* Wait for the thread to sleep */

	/* Wake-up side: change the condition first, then wake up */
	data_ready = 1;
	wake_up_interruptible(&my_wq);

	wait_for_completion(&waiter_done);
	return 0;
}

static void __exit waitqueue_test_exit(void)
{
	pr_info("waitqueue_test module exit\n");
}

module_init(waitqueue_test_init);
module_exit(waitqueue_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("wait queue demo module");

Typical applications in the kernel:

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

---

work_struct / workqueue — work queue

The work queuedefers tasks to process contextfor execution, and is one of the common ways for bottom-half processing.

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 API:

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

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* workqueue_test.c -- normal work + delayed work */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/workqueue.h>

static void my_work_handler(struct work_struct *work)
{
	pr_info("  work running in process context (can sleep)\n");
}

static void my_delayed_handler(struct work_struct *work)
{
	pr_info("  delayed work fired after 200ms\n");
}

static DECLARE_WORK(my_work, my_work_handler);
static DECLARE_DELAYED_WORK(my_dwork, my_delayed_handler);

static int __init workqueue_test_init(void)
{
	/* Schedule to the system work queue (can also use queue_work to submit to a custom queue) */
	schedule_work(&my_work);

	/* Execute after 200ms */
	schedule_delayed_work(&my_dwork, msecs_to_jiffies(200));

	/* Wait for both jobs to complete (verify output order) */
	flush_work(&my_work);
	flush_delayed_work(&my_dwork);

	return 0;
}

static void __exit workqueue_test_exit(void)
{
	cancel_work_sync(&my_work);
	cancel_delayed_work_sync(&my_dwork);
	pr_info("workqueue_test module exit\n");
}

module_init(workqueue_test_init);
module_exit(workqueue_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("workqueue demo module");

Typical applications in the kernel:

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

---

timer_list — kernel timer

Used after a specified time toexecute a callback function(softirq context), precision is at jiffies level (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 API:

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 delete (wait for handler to complete)
timer_pending(timer)	Check if pending

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* timer_test.c -- jiffies-level periodic timer (auto-stops after 3 ticks) */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/timer.h>
#include <linux/jiffies.h>
#include <linux/delay.h>

static struct timer_list my_timer;
static int n;

/* Callback runs in softirq context: cannot sleep */
static void my_timer_cb(struct timer_list *t)
{
	n++;

	if (n < 3) {
		pr_info("  tick %d\n", n);
		/* Periodic timer: re-arms itself */
		mod_timer(t, jiffies + msecs_to_jiffies(100));
	} else {
		pr_info("  tick %d, stopping\n", n);
	}
}

static int __init timer_test_init(void)
{
	timer_setup(&my_timer, my_timer_cb, 0);
	mod_timer(&my_timer, jiffies + msecs_to_jiffies(100));

	msleep(500);	/* Wait for the timer to expire */
	return 0;
}

static void __exit timer_test_exit(void)
{
	del_timer_sync(&my_timer);
	pr_info("timer_test module exit\n");
}

module_init(timer_test_init);
module_exit(timer_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("timer_list demo module");

Typical applications in the kernel:

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

---

hrtimer — high-resolution timer

hrtimerprovideNanosecond-levelA precision timer, managed at the bottom layer using a red-black tree. 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 API:

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

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* hrtimer_test.c -- nanosecond-level periodic high-resolution timer */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/hrtimer.h>
#include <linux/ktime.h>
#include <linux/delay.h>

static struct hrtimer my_hrtimer;
static ktime_t period;
static int n;

static enum hrtimer_restart my_hrtimer_cb(struct hrtimer *timer)
{
	if (++n < 3) {
		pr_info("  hrtimer tick %d\n", n);
		hrtimer_forward_now(timer, period);
		return HRTIMER_RESTART;
	}
	pr_info("  hrtimer tick %d, stopping\n", n);
	return HRTIMER_NORESTART;
}

static int __init hrtimer_test_init(void)
{
	period = ns_to_ktime(1000000);	/* 1ms */

	hrtimer_init(&my_hrtimer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
	my_hrtimer.function = my_hrtimer_cb;
	hrtimer_start(&my_hrtimer, period, HRTIMER_MODE_REL);

	msleep(10);	/* Wait for the timer to expire */
	return 0;
}

static void __exit hrtimer_test_exit(void)
{
	hrtimer_cancel(&my_hrtimer);
	pr_info("hrtimer_test module exit\n");
}

module_init(hrtimer_test_init);
module_exit(hrtimer_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("hrtimer demo module");

Typical applications in the kernel:

• Periodic tick of the process scheduler
• POSIX timers
• High-precision sleep (usleep_range）
• Precise delay control of network packets

---

---

Device model and notification

kobject / kset — kernel object model

kobjectis Linux device driver modelthe 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;       // Linked list for kset
    struct kobject      *parent;     // Parent object
    struct kset         *kset;       // Associated 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;             // Itself is also a kobject
    const struct kset_uevent_ops *uevent_ops;
};

Core API:

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

Usage example(after loadingcat /sys/kernel/my_kobj/hello）：

// SPDX-License-Identifier: GPL-2.0
/* kobject_test.c -- Create directories and attribute files under /sys/kernel */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/kobject.h>
#include <linux/sysfs.h>

static struct kobject *my_kobj;

static ssize_t hello_show(struct kobject *kobj,
			  struct kobj_attribute *attr, char *buf)
{
	return sprintf(buf, "hello from my_kobj\n");
}

/* __ATTR_RO(name): read-only property, auto-bound <name>_show callback */
static struct kobj_attribute hello_attr = __ATTR_RO(hello);

static int __init kobject_test_init(void)
{
	int ret;

	/* Create /sys/kernel/my_kobj/（kernel_kobj is /sys/kernel) */
	my_kobj = kobject_create_and_add("my_kobj", kernel_kobj);
	if (!my_kobj)
		return -ENOMEM;

	ret = sysfs_create_file(my_kobj, &hello_attr.attr);
	if (ret) {
		kobject_put(my_kobj);
		return ret;
	}

	pr_info("  see /sys/kernel/my_kobj/hello\n");
	return 0;
}

static void __exit kobject_test_exit(void)
{
	/* Automatically remove the directory from sysfs when the kobject_put reference count drops to zero. */
	kobject_put(my_kobj);
	pr_info("kobject_test module exit\n");
}

module_init(kobject_test_init);
module_exit(kobject_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("kobject demo module");

Typical applications in the kernel:

• /sysEvery directory and file in the file system
• struct device、struct driver、struct bus_typeBase class for device models, etc.
• ueventHot-plug events (such as USB drive insertion notification udev)

---

notifier_block — notification chain

The notification chain (Notifier Chain) is in the kernelPublish-SubscribePattern implementation: 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 API:

API	Description
blocking_notifier_chain_register(head, nb)	Registration notification block
blocking_notifier_chain_unregister(head, nb)	Logout
blocking_notifier_call_chain(head, val, v)	Initiate Notification
raw_notifier_chain_register(head, nb)	Register (atomic context safe)
atomic_notifier_chain_register(head, nb)	Register (atomic context)

Notification chain type:

Type	Callback context	Blockable
atomic_notifier_chain	Atomic context (interrupt/spinlock)	No
blocking_notifier_chain	Process context	Yes
raw_notifier_chain	Any context (caller responsible)	Depends on caller
SRCU_notifier_chain	Process context (SRCU protected)	Yes

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* notifier_test.c -- custom notification chain: publish-subscribe */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/notifier.h>

#define MY_EVENT_FOO	0x0001
#define MY_EVENT_BAR	0x0002

/* Custom blocking notification chain head */
static BLOCKING_NOTIFIER_HEAD(my_chain);

/* Subscriber callback */
static int my_notifier_fn(struct notifier_block *nb,
			  unsigned long event, void *data)
{
	pr_info("  event 0x%04lx received, data=%s\n", event, (char *)data);
	return NOTIFY_OK;	/* NOTIFY_DONE / NOTIFY_OK / NOTIFY_BAD */
}

static struct notifier_block my_nb = {
	.notifier_call	= my_notifier_fn,
};

static int __init notifier_test_init(void)
{
	/* Subscribe */
	blocking_notifier_chain_register(&my_chain, &my_nb);

	/* Publish two events to all subscribers on the chain */
	blocking_notifier_call_chain(&my_chain, MY_EVENT_FOO, "hello");
	blocking_notifier_call_chain(&my_chain, MY_EVENT_BAR, "world");

	return 0;
}

static void __exit notifier_test_exit(void)
{
	blocking_notifier_chain_unregister(&my_chain, &my_nb);
	pr_info("notifier_test module exit\n");
}

module_init(notifier_test_init);
module_exit(notifier_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("notifier chain demo module");

Typical applications in the kernel:

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

---

Memory management and caching

kfifo — kernel FIFO queue

kfifois aLock-free ring buffer(circular buffer), providing lock-free communication for single reader/single writer producer/consumer (multiple readers/writers require external synchronization).

Header file:<linux/kfifo.h>

Core API:

API	Description
DECLARE_KFIFO(fifo, type, size)	Static definition
kfifo_alloc(fifo, size, gfp)	Dynamic allocation
kfifo_put(fifo, val)	Enqueue one element
kfifo_get(fifo, val)	Dequeue one 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:

// SPDX-License-Identifier: GPL-2.0
/* kfifo_test.c -- Lock-free ring FIFO (single-reader single-writer scenario) */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/kfifo.h>

/* Size must be a power of 2 */
static DECLARE_KFIFO(my_fifo, int, 16);

static int __init kfifo_test_init(void)
{
	int val, out, i;

	INIT_KFIFO(my_fifo);

	/* Single-element enqueue */
	for (i = 0; i < 8; i++) {
		val = i * 3;
		if (!kfifo_put(&my_fifo, val))
			pr_info("  fifo full, put %d failed\n", val);
	}
	pr_info("  len=%d\n", kfifo_len(&my_fifo));

	/* Dequeue: order matches enqueue */
	while (kfifo_get(&my_fifo, &out))
		pr_info("  got %d\n", out);

	pr_info("  empty=%s full=%s\n",
		kfifo_is_empty(&my_fifo) ? "yes" : "no",
		kfifo_is_full(&my_fifo) ? "yes" : "no");

	/* Batch enqueue/dequeue (kfifo_in/kfifo_out operates on bytes) */
	{
		int in_buf[4] = { 1, 2, 3, 4 };
		int out_buf[4];
		unsigned int n;

		n = kfifo_in(&my_fifo, in_buf, sizeof(in_buf));
		n = kfifo_out(&my_fifo, out_buf, n);
		for (i = 0; i < (int)(n / sizeof(int)); i++)
			pr_info("  bulk got %d\n", out_buf[i]);
	}

	return 0;
}

static void __exit kfifo_test_exit(void)
{
	pr_info("kfifo_test module exit\n");
}

module_init(kfifo_test_init);
module_exit(kfifo_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("kfifo demo module");

Typical applications in the kernel:

• Serial driver transmit/receive buffer
• Audio driver PCM buffer
• Kernel log buffer (printk ring buffer)

---

percpu — Per-CPU variables

Per-CPU variables areEach CPU is allocated an independent memory copy., the CPU accesses its own copy without locking, and cache utilization is extremely high (the variable is in the CPU’s local cache).

Header file:<linux/percpu.h>

Core API:

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 the current CPU’s copy (with preemption disabled)
put_cpu_var(var)	with get_cpu_var, restore preemption
this_cpu_ptr(ptr)	Get a pointer to the current CPU’s copy
per_cpu_ptr(ptr, cpu)	Get a pointer to the specified CPU’s copy
for_each_possible_cpu(cpu)	Iterate over all CPUs

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* percpu_test.c -- static and dynamic per-CPU variables */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/percpu.h>
#include <linux/smp.h>

static DEFINE_PER_CPU(int, my_counter);
static int __percpu *dynamic_counter;

static int __init percpu_test_init(void)
{
	int cpu, sum = 0;

	/* Statically defined per-CPU variable: atomically incremented on the current CPU, no locking required */
	this_cpu_inc(my_counter);
	this_cpu_add(my_counter, 10);

	/* Aggregate the copies of all CPUs */
	for_each_possible_cpu(cpu)
		sum += per_cpu(my_counter, cpu);
	pr_info("  static percpu sum=%d
", sum);

	/* Dynamic allocation */
	dynamic_counter = alloc_percpu(int);
	if (!dynamic_counter)
		return -ENOMEM;

	for_each_possible_cpu(cpu)
		per_cpu(*dynamic_counter, cpu) = cpu * 100;

	cpu = get_cpu();	/* Disable preemption to prevent migration during execution */
	pr_info("  running on cpu%d, local value=%d
",
		cpu, per_cpu(*dynamic_counter, cpu));
	put_cpu();

	return 0;
}

static void __exit percpu_test_exit(void)
{
	free_percpu(dynamic_counter);
	pr_info("percpu_test module exit
");
}

module_init(percpu_test_init);
module_exit(percpu_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("percpu demo module");

Typical applications in the kernel:

• Statistical counters (network packet counting, interrupt counting)
• Per-CPU caches of memory allocators (slab/slub)
• RCU’s per-CPU state
• Scheduler’s per-CPU run queues

---

circ_buf — ring buffer macro

A set of simple macros for using a plain character array as a ring buffer. Commonly 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)	Bytes used
CIRC_SPACE_TO_END(head, tail, size)	Contiguous space to the end of the buffer

Usage example:

// SPDX-License-Identifier: GPL-2.0
/* circ_buf_test.c -- implementing a lightweight ring buffer with macros */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/circ_buf.h>

#define BUF_SIZE	64		/* must be a power of 2 */

static char buf[BUF_SIZE];
static int head, tail;

static int __init circ_buf_test_init(void)
{
	char msg[] = "hello";
	int i;

	pr_info("  initial: space=%d cnt=%d\n",
		CIRC_SPACE(head, tail, BUF_SIZE),
		CIRC_CNT(head, tail, BUF_SIZE));

	/* Producer: check space before writing (macros ensure safe index wraparound) */
	for (i = 0; i < (int)sizeof(msg); i++) {
		if (!CIRC_SPACE(head, tail, BUF_SIZE)) {
			pr_info("  buffer full\n");
			break;
		}
		buf[head] = msg[i];
		head = (head + 1) & (BUF_SIZE - 1);
	}

	/* Consumer */
	while (CIRC_CNT(head, tail, BUF_SIZE)) {
		pr_info("  got '%c'\n", buf[tail]);
		tail = (tail + 1) & (BUF_SIZE - 1);
	}

	return 0;
}

static void __exit circ_buf_test_exit(void)
{
	pr_info("circ_buf_test module exit\n");
}

module_init(circ_buf_test_init);
module_exit(circ_buf_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("circ_buf demo module");

Typical applications in the kernel:

• TTY driver line discipline buffer
• Simple serial port driver

---

flex_array — flexible array

flex_arrayAllows creatingan array spanning multiple pages, but each element has a fixed size. Compared to a singlekmalloclarge block of memory,flex_arrayit has better tolerance for small memory fragmentation (because each element is distributed across different pages).

warning

Starting from Linux 5.10,flex_arrayhas been marked as deprecated, it is recommended to use the 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 linked 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)	Convert 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 between 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 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 list
    // ...
};

vm_area_struct — virtual memory area

Describes acontiguous virtual address range, each interval 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;  // Operation function table
    struct file *vm_file;               // Mapped file
    // ...
};

Typical applications in the kernel:

• Page fault handler
• mmap()/munmap()System Calls
• /proc/<pid>/mapsinformation source

---

---

Network

sk_buff — Socket buffer

sk_buff(often abbreviated asskb) is Linux network subsystemcore data structure, representing a network packet. It runs through the entire network stack: from NIC driver reception to application layer sending, 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
    sk_buff_data_t      tail;
    sk_buff_data_t      end;
    unsigned char       *head, *data;
    unsigned int        truesize;
    refcount_t          users;
};

sk_buffUse a four-pointer model to manage the data space:

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

Core API:

API	Description
alloc_skb(size, gfp)	Allocate skb
skb_put(skb, len)	Append data to the tail
skb_push(skb, len)	Prepend data (add protocol header)
skb_pull(skb, len)	Remove data from the 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 the head
skb_dequeue(list)	Dequeue

Typical applications in the kernel:

• Packet carrier for the entire network stack
• TUN/TAP virtual network interface
• Packet filtering in Netfilter / iptables

References

[1]

linux listDetailed explanation

[2]

Linux：KernelhashTable——hlist

[3]

LinuxRed-black tree in（rbtree）

[4]

Linux：radixBrief analysis of implementation