list

发表于2025-10-03|更新于2025-10-06|linuxlib

|总字数:11.8k|阅读时长:37分钟|浏览量:|评论数:

[TOC]

include/linux/list.h 内核双向循环链表(Kernel Doubly-Linked List) 内核数据结构的基础构建块

历史与背景

这项技术是为了解决什么特定问题而诞生的？

include/linux/list.h 提供了一套宏和内联函数，用于实现侵入式（Intrusive）的双向循环链表（Doubly-Linked Circular List）。它的诞生是为了解决在C语言编写的操作系统内核中一个极其普遍和基础的问题：如何以一种高效、类型安全且代码复用度高的方式，将任意类型的数据结构组织成一个链表。

在没有这样一个通用实现的情况下，每个需要使用链表的子系统都可能会：

重复造轮子：自己定义一套链表节点和操作函数，导致代码冗余和不一致。
使用非侵入式链表：创建一个通用的链表节点结构，其中包含一个void *指针来指向实际数据。这种方式的缺点是：
- 额外的内存开销：每次向链表中添加一个元素，都需要额外分配一个链表节点。
- 性能开销：访问实际数据需要两次指针解引用（list_node->data），这会降低缓存效率。
- 类型不安全：从void *转回实际类型时，依赖于程序员自己保证类型正确，编译器无法提供帮助。

list.h通过侵入式的设计完美地解决了这些问题。它不要求数据去适应链表，而是让链表结构嵌入到数据结构中。

它的发展经历了哪些重要的里程碑或版本迭代？

list.h是内核中最古老、最稳定、设计最精巧的头文件之一。它的核心设计自诞生以来几乎没有改变，堪称C语言宏编程的典范。

Linus Torvalds的创造：这个实现被广泛认为是Linus Torvalds本人的一项杰作。他巧妙地利用了C语言的宏、offsetof宏和container_of宏，创造出了一套既通用又类型安全的API。
不断完善的辅助宏：随着内核的发展，社区为其添加了大量的辅助宏和函数，以应对各种常见的链表操作模式，例如：
- list_for_each_entry_safe()：用于在遍历链表的同时安全地删除节点。
- list_is_singular()：检查链表是否只有一个节点。
- list_splice()：高效地将一个链表合并到另一个链表中。
哈希链表（Hlist）的引入：对于需要实现哈希表的场景，标准的双向循环链表在链表头（list_head）上有轻微的内存浪费（两个指针）。因此，内核引入了哈希链表（hlist_head和hlist_node），它的链表头只有一个指针，更适合用作哈希桶。

目前该技术的社区活跃度和主流应用情况如何？

list.h是Linux内核中使用最广泛、最基础的数据结构，没有之一。

主流应用：你几乎可以在内核的任何一个子系统中找到它的身影。
- 进程调度器：运行队列中的进程列表。
- 文件系统：VFS中的dentry、inode列表，以及文件描述符列表。
- 网络：Socket的接收队列。
- 设备驱动：管理设备实例的列表。
- 内存管理：管理空闲页面的列表。

核心原理与设计

它的核心工作原理是什么？

list.h的精髓在于**“侵入式”设计和container_of宏**的巧妙运用。

侵入式数据结构：
- list.h只定义了链表节点本身——struct list_head，它包含两个指针：next和prev。
- 开发者在定义自己的数据结构时，直接将struct list_head作为一个成员嵌入进去。
  1
  2
  3
  4
  5
  struct my_struct {
  int data;
  const char *name;
  struct list_head list_node; // 链表节点被嵌入
  };
- 这样，my_struct的实例本身就包含了链表节点，无需额外分配内存。
链表操作：
- 所有的链表操作（如list_add, list_del）都是直接针对这个嵌入的list_head成员进行的。这些操作只关心next和prev指针，完全不知道也不关心包含它的my_struct的存在。
从节点找回容器 (container_of宏)：
- 这是整个设计的**“魔法”**所在。当你遍历链表时，你得到的是一个指向嵌入的list_head成员的指针。但你真正需要的是指向包含它的、完整的my_struct的指针。
- container_of(ptr, type, member)宏解决了这个问题。它的工作原理是：
  a. ptr：指向成员的指针（struct list_head *）。
  b. type：容器的类型（struct my_struct）。
  c. member：成员在容器中的名字（list_node）。
- 它通过一个编译时技巧：获取成员在结构体中的偏移量（offset），然后用成员的地址减去这个偏移量，就能精确地计算出整个结构体的起始地址。
  1
  2
  // 伪代码
  (type *) ( (char *)ptr - offsetof(type, member) );
- list_entry(ptr, type, member)是专门为list_head封装的container_of。

遍历 (Iteration)：

list_for_each_entry(pos, head, member)这个宏将遍历过程和list_entry的转换完美地封装在一起，使得遍历代码既简洁又类型安全。

struct list_head my_list_head;
struct my_struct *current_entry;

list_for_each_entry(current_entry, &my_list_head, list_node) {
    // 在循环体中，current_entry直接就是指向my_struct的指针
    printk("Found entry: %s\n", current_entry->name);
}

它的主要优势体现在哪些方面？

高效：没有额外的内存分配，访问数据也无需间接指针跳转。
类型安全：container_of宏在编译时进行类型检查，最终得到的指针是强类型的。
代码复用：一套API被内核中成千上万个地方复用。
灵活性：一个数据结构可以包含多个list_head成员，从而同时被加入到多个不同的链表中。

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

非线程安全：list.h本身不提供任何锁机制。在多线程或中断上下文中使用时，程序员必须自己负责使用自旋锁、互斥锁等来保护链表。
查找性能：它只是一个链表，查找一个特定元素的平均时间复杂度是O(N)。对于需要快速查找的场景，应该使用哈希表（通常用hlist实现）或树（如红黑树）。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？

list.h是内核中需要将一组对象组织成一个有序（按插入顺序）或无序的集合，并且不关心快速查找时的首选解决方案。

管理一组动态对象：一个驱动需要管理所有被它驱动的设备实例。
实现队列：可以轻松地在链表头（list_add）或链表尾（list_add_tail）添加元素，实现FIFO或LIFO队列。
作为更复杂数据结构的基础：许多内核中的缓存（cache）实现，都会使用一个哈希表和一个LRU（最近最少使用）链表。哈希表用于快速查找，而LRU链表（用list.h实现）则用于在缓存满时淘汰最旧的条目。

是否有不推荐使用该技术的场景？为什么？

需要通过键值快速查找：应使用哈希表（hlist）或红黑树 (rbtree)。
需要频繁地在列表中间插入且要求有序：如果列表是按某个值排序的，每次插入都需要遍历找到正确位置，效率较低。

对比分析

请将其与其他相似技术进行详细对比。

特性	`list.h` (双向循环链表)	`hlist.h` (哈希链表)	红黑树 (`rbtree.h`)
数据结构	双向循环链表。	单向链表，但链表头特殊优化。	自平衡二叉搜索树。
主要用途	通用的、无序或按插入顺序的集合。	哈希表的桶链。	有序的集合，需要高效的查找、插入和删除。
查找复杂度	O(N)	O(N) (在单个桶内)，但哈希表的平均查找是O(1)。	O(log N)
内存开销 (per node)	中 (`next`, `prev`两个指针)。	低 (`next`指针, `pprev`指针的指针)。	高 (左、右、父指针，颜色位)。
链表头开销	中 (`next`, `prev`两个指针)。	极低 (`first`一个指针)。	中 (一个根指针)。
适用场景	任务队列、对象列表、LRU列表。	实现内核中的哈希表。	调度器的运行队列、内存管理中的VMA列表、文件描述符管理。

__list_del 通过使 prev/next 条目彼此指向来删除列表条目

/*
 * 通过使 prev/next 条目彼此指向来删除列表条目。
 *
 * 这仅适用于内部列表作，我们已经知道 prev/next 条目！
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	WRITE_ONCE(prev->next, next);
}

static inline void __list_del_entry(struct list_head *entry)
{
	if (!__list_del_entry_valid(entry))
		return;

	__list_del(entry->prev, entry->next);
}

list_add 在指定的 head 后插入新条目

/*
 * new 插入在prev 和 next 之间。
 * 在两个已知的连续条目之间插入新条目。
 *
 * 这仅适用于内部列表作，我们已经知道 prev/next 条目！
 */
static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	if (!__list_add_valid(new, prev, next))
		return;

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

/**
 * new 插入在head的后面
 * list_add - 添加新条目
 * @new：新增条目
 * @head：列表头添加后
 *
 * 在指定的 head 后插入新条目。这对于实现堆栈非常有用。
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

/**
 * new 插入在head的前面即尾部
 * list_add_tail - 添加新条目
 * @new：新增条目
 * @head：列表头添加前
 *
 * 在指定的 head 之前插入新条目。这对于实现队列很有用。
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

list_move 从一个列表中删除并添加到另一个列表的head后面

/**
 * list_move - 从一个列表中删除并添加为另一个列表的 head
 * @list：要移动的入口
 * @head：在我们进入之前
 */
static inline void list_move(struct list_head *list, struct list_head *head)
{
	__list_del_entry(list);
	list_add(list, head);
}

list_move_tail 从一个列表中删除并添加到另一个列表的尾部

/**
 * list_move_tail - 从一个列表中删除并添加为另一个列表的尾部
 * @list：要移动的入口
 * @head：跟随我们进入的头部
 */
static inline void list_move_tail(struct list_head *list,
				  struct list_head *head)
{
	__list_del_entry(list);
	list_add_tail(list, head);
}

include/linux/list_bl.h 内核带位锁的链表(Kernel List with Bit Lock) 为大规模哈希表优化的内存效率方案

历史与背景

这项技术是为了解决什么特定问题而诞生的？

include/linux/list_bl.h 提供了一种**带位锁（Bit-Locked）**的链表实现。它的诞生是为了解决一个在特定场景下（主要是大规模哈希表）内存开销过大的问题。

在标准内核编程中，当一个链表需要被多个CPU并发访问时，它必须被一个锁保护起来。通常的做法是这样的：

struct my_hash_bucket {
    struct list_head chain;
    spinlock_t lock; // 每个链表头都需要一个独立的自旋锁
};

这种模式非常清晰，但也存在一个问题：spinlock_t 结构本身会占用内存（在64位系统上通常是4字节）。在只有少数几个链表的情况下，这点开销无足轻重。但是，在一些需要海量链表头的场景，这个开销会变得无法接受。

最经典的例子就是Linux的目录项缓存（dcache）。dcache使用一个巨大的哈希表来加速路径查找，这个哈希表可能有数百万个桶（buckets）。如果每个桶（就是一个链表头）都配一个独立的spinlock_t，仅仅是这些锁本身就会消耗掉数十兆字节的内核内存。

list_bl就是为了消除这个独立的锁对象而设计的。它巧妙地将锁的功能集成到了链表头的指针自身中，从而为每个链表头节省了存储一个完整锁对象的内存。

它的发展经历了哪些重要的里程碑或版本迭代？

list_bl本身就是内核为了极致优化而进行的一次重要创新，其发展主要体现在：

概念的实现：内核开发者（以Nick Piggin为代表）提出了这个想法，并利用了指针地址对齐的特性，将指针的最低位“挪用”为锁定位。
与哈希链表（Hlist）的结合：由于其主要应用场景是哈希表，所以list_bl的实现与hlist（专门为哈希表优化的链表）紧密结合，形成了hlist_bl。list_bl可以看作是hlist_bl的一个封装或变体。
在dcache中的成功应用：list_bl最重要的里程碑就是它被成功地应用于重构dcache的锁机制。这次重构为系统节省了大量的内核内存，证明了该技术在特定场景下的巨大价值。

目前该技术的社区活跃度和主流应用情况如何？

list_bl是内核中一个稳定、成熟但高度特化的组件。它不像list.h那样被普遍使用，但在其设计的特定领域是不可或缺的。

主流应用：
- dcache：这是list_bl最著名、最典型的应用场景。
- 其他需要实现超大规模、每个桶都需要独立锁的哈希表的内核子系统。

核心原理与设计

它的核心工作原理是什么？

list_bl的“魔法”在于指针最低位的重用（repurposing the least significant bit of a pointer）。

地址对齐的前提：在现代计算机体系结构中，为了性能，所有多字节的数据结构（如struct hlist_bl_node）都会被对齐（aligned）到4字节或8字节的内存边界上。这意味着它们的内存地址永远是4或8的倍数，因此其二进制表示的最低两位或三位永远是0。
位锁（Bit Lock）：list_bl利用了这个特性，将指针的最低有效位（bit 0）挪作他用，把它当作一个锁定位。
- 当 bit 0 为 0 时，表示该链表是未锁定的。
- 当 bit 0 为 1 时，表示该链表是已锁定的。
核心数据结构：struct list_bl_head的核心是一个指针。这个指针的值同时编码了两种信息：链表第一个节点的地址（除了bit 0之外的其他所有位）和锁的状态（bit 0）。
上锁与解锁：
- 上锁 (list_bl_lock())：这个函数会使用一个原子的、CPU提供的test-and-set-bit指令来尝试将指针的bit 0设置为1。这是一个**自旋（spin）**过程：如果设置成功（说明之前是0），则获得锁；如果设置失败（说明之前已经是1），则在一个循环中不断重试，直到成功为止。
- 解锁 (list_bl_unlock())：这个函数使用一个原子的clear-bit指令将指针的bit 0清零。
获取真实指针：当需要访问链表的第一个节点时，必须先将锁定位屏蔽掉。代码会执行一个位操作 (pointer & ~1UL) 来获取真实的、对齐的节点地址。所有list_bl的辅助函数都会在内部自动处理这个屏蔽操作。

它的主要优势体现在哪些方面？

极高的内存效率：这是其最核心的优势。它完全消除了对独立spinlock_t对象的需求，在需要大量锁的场景下可以节省巨量的内存。
良好的性能：位锁的实现基于高效的原子指令，对于短时间的临界区保护，其性能与标准的自旋锁相当。

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

只能是自旋锁：list_bl实现的锁是一种自旋锁。这意味着在持有该锁的临界区内，代码绝对不能睡眠。
API更复杂：开发者不能再使用标准的list.h函数，而必须使用list_bl.h提供的一套专用API（如hlist_bl_add_head, hlist_bl_for_each_entry等），并且必须手动调用list_bl_lock/unlock。
缺乏高级锁特性：它只是一个简单的锁，不像标准的spinlock_t那样拥有丰富的调试支持（如lockdep死锁检测）。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？

list_bl是当且仅当你需要实现一个包含海量桶（数万到数百万）的哈希表，并且每个桶都需要一个独立的、非睡眠的锁来保护时的首选解决方案。

文件系统目录项缓存（dcache）：这是教科书般的应用案例。
任何类似的、内存占用极其敏感的大规模哈希表实现。

是否有不推荐使用该技术的场景？为什么？

少量链表：如果你只需要保护几个或几十个链表，那么使用list_bl带来的API复杂性完全没有必要。直接使用struct list_head + spinlock_t的组合更清晰、更标准，且节省的内存可以忽略不计。
临界区需要睡眠：如果保护链表的操作中可能涉及到睡眠（如内存分配、I/O），那么绝对不能使用list_bl。必须使用可以睡眠的锁，如mutex。
需要复杂的锁调试：在开发和调试阶段，使用带有完整lockdep支持的标准spinlock_t可以帮助发现潜在的死锁问题。

对比分析

请将其与其他相似技术进行详细对比。

特性	`list_bl.h` (带位锁的链表)	`list.h` + `spinlock_t` (标准组合)	`list.h` + `mutex_t` (睡眠锁组合)
内存开销 (每个链表头)	极低 (仅一个指针)。	中等 (一个链表头 + 一个自旋锁对象)。	高 (一个链表头 + 一个互斥锁对象)。
锁类型	自旋锁 (Spinlock)。	自旋锁 (Spinlock)。	互斥锁 (Mutex, Sleeping Lock)。
临界区能否睡眠	否	否	是
性能 (短临界区)	高 (原子位操作)。	高 (原子指令)。	低 (涉及上下文切换的潜在开销)。
使用复杂度	中等 (需要使用专用API)。	低 (非常标准和常见的模式)。	低 (标准模式)。
适用场景	大规模哈希表，内存极度敏感。	通用的、非睡眠的链表保护。	需要在临界区内睡眠的链表保护。

/*
* 列表的特殊版本，其中列表的头部在最低位有一个锁。这对于可扩展的哈希表非常有用，同时不会增加内存开销。
* 对于修改操作，必须设置 hlist_bl_head->first 指针的第 0 位。
* 通过一些小的修改，这可以轻松适配以存储多个任意位（不仅仅是单个锁位），如果需要存储一些快速且紧凑的辅助数据。

INIT_HLIST_BL_HEAD

1 2	#define INIT_HLIST_BL_HEAD(ptr) \ ((ptr)->first = NULL)

include/linux/llist.h 无锁单向链表(Lock-Less Singly-Linked List) 高并发场景下的高效数据结构

历史与背景

这项技术是为了解决什么特定问题而诞生的？

llist（lock-less list）是为了解决在高并发和中断上下文中，对链表进行操作时的锁竞争问题而诞生的。传统的链表在多核（SMP）或抢占式（preemptive）环境中，当多个线程或中断处理程序同时尝试修改链表时，必须使用自旋锁（spinlock）或互斥锁（mutex）来保护其完整性。然而，使用锁会带来一系列问题：

性能开销：在高并发场景下，锁的获取和释放会引入显著的性能开销。当锁被一个CPU持有时，其他尝试获取该锁的CPU只能忙等待（spinning），浪费了宝贵的CPU周期。
死锁风险：在复杂的代码路径中，不当的锁使用顺序可能导致死锁。
中断上下文限制：中断处理程序不能睡眠，因此不能使用会导致阻塞的互斥锁。虽然可以使用自旋锁，但这要求临界区必须非常短，否则会增加中断延迟。

llist 通过提供一套基于原子操作（atomic operations）的无锁API，允许多个“生产者”（Producers）在无须加锁的情况下，安全地向链表头部添加节点，同时一个“消费者”（Consumer）也可以安全地从链表头部移除节点。

它的发展经历了哪些重要的里程碑或版本迭代？

llist 的引入是内核向更高并发、更低延迟方向演进的一部分。它作为一种基础数据结构，其API自诞生以来相对稳定。它的发展主要体现在其在内核中应用范围的不断扩大，越来越多的子系统开始采用 llist 来替代原有的基于锁的链表，以优化其在高并发环境下的性能。例如，在网络协议栈、RCU（Read-Copy-Update）机制以及各种驱动程序的异步处理队列中，都能看到 llist 的身影。

目前该技术的社区活跃度和主流应用情况如何？

llist 是Linux内核中一个非常基础、成熟且广泛使用的数据结构。它不是一个试验性功能，而是解决特定类型并发问题的标准工具。内核开发者在处理多生产者/单消费者（MP/SC）或多生产者/多消费者（MP/MC，但消费端需要额外加锁）队列场景时，会优先考虑使用 llist。

核心原理与设计

它的核心工作原理是什么？

llist 的核心是巧妙地利用了CPU提供的原子操作指令，如“比较并交换”（Compare-and-Swap, CAS）。其无锁添加（llist_add）操作的原理大致如下：

读取旧头：生产者线程首先原子性地读取当前链表的头指针（head->first）。
准备新节点：生产者将新节点的 next 指针指向刚才读取的旧头。
原子更新：生产者使用CAS操作尝试将链表的头指针从“旧头”更新为“新节点”。
- 成功：如果在此期间没有其他线程修改过头指针，CAS操作就会成功，新节点被原子性地插入到链表头部。
- 失败：如果在此期间有其他线程已经修改了头指针，CAS操作就会失败。此时，生产者会回到第一步，重新读取新的头指针，并重试整个过程，直到成功为止。

由于整个更新过程是通过一条原子指令完成的，因此它保证了即使有多个生产者同时执行此操作，链表也始终处于一致的状态，不会损坏。

它的主要优势体现在哪些方面？

无锁并发：允许多个生产者线程在没有任何锁的情况下并发地向链表添加节点，极大地提高了在多核系统上的扩展性。
高性能：避免了锁操作带来的缓存行争抢（cache line bouncing）和CPU忙等待，性能开销非常低。
适用于中断上下文：由于其非阻塞特性，llist 的添加操作可以在中断处理程序中安全使用。
避免ABA问题：llist 的设计天然地避免了无锁算法中常见的ABA问题。

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

功能受限：llist 的API非常精简，功能远不如内核标准的双向循环链表（list_head）。它主要支持在链表头部添加节点，以及从头部移除第一个节点或整个链表。不支持在链表中间或尾部进行插入/删除操作。
单向遍历：它是单向链表，只能从头到尾遍历。
消费端限制：虽然允许多个生产者，但标准的无锁API（llist_del_first）只支持单个消费者。如果需要多个消费者，必须在消费者端引入额外的锁机制来保护对链表的移除操作。
内存序要求：正确使用 llist 需要对内存屏障（memory barriers）和处理器的内存模型有深入的理解，不过其API封装了这些复杂性。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？请举例说明。

llist 是多生产者、单消费者（MP/SC）队列场景的理想选择，特别是当生产者可能来自中断上下文时。

网络数据包处理：网卡驱动的中断处理程序（生产者）接收到数据包后，可以无锁地将数据包描述符添加到一个 llist 队列中。然后，一个单独的内核线程（消费者，如NAPI中的软中断处理）会从该队列中取出所有数据包进行后续处理。
RCU回调：RCU机制使用 llist 来收集在宽限期（grace period）结束后需要被释放的内存块。内核中不同的部分都可以在不需要加锁的情况下，将待释放的对象添加到per-CPU的 llist 中。
异步工作分发：一个驱动程序可能会有多个事件源（如不同的中断、用户空间请求等）作为生产者，它们将需要处理的工作项添加到 llist 中，由一个统一的工作队列（worker thread）作为消费者来执行。

是否有不推荐使用该技术的场景？为什么？

需要复杂链表操作的场景：如果需要频繁地在链表中间插入/删除节点，或者需要双向遍历，那么应该使用内核标准的、由锁保护的 list_head 双向链表。
单生产者、单消费者场景：在这种场景下，虽然 llist 也能工作，但可能存在更简单的、不需要原子操作的队列实现，开销更低。
对顺序有严格要求的队列：llist 是一个LIFO（后进先出）的栈结构。如果需要FIFO（先进先出）的队列行为，需要进行额外处理或使用其他数据结构（如kfifo）。

对比分析

请将其与其他相似技术进行详细对比。

llist 的主要对比对象是使用自旋锁保护的标准链表（struct list_head）。

特性	llist (无锁单向链表)	spinlock + list_head (锁保护的双向链表)
实现方式	基于CPU原子操作（如CAS），无需锁。	使用自旋锁（spinlock）来保护临界区。
性能开销	低。在无竞争时，只有原子指令的开销。在高并发下，几乎没有扩展性瓶颈。	中到高。无竞争时，锁的获取/释放有固定开销。在高并发下，锁的争用会导致CPU忙等，性能会急剧下降。
资源占用	内存占用更小（只有一个 `next` 指针）。	内存占用稍大（有 `next` 和 `prev` 两个指针）。
隔离级别/并发模型	无锁（Lock-Free）。允许多个生产者并发地在头部添加。仅支持单个消费者无锁地移除。	互斥（Mutual Exclusion）。在任何时刻，只允许一个线程进入临界区对链表进行任何操作。
功能丰富度	功能有限。只支持头部的添加和移除，单向遍历。	功能非常丰富。支持在任意位置添加、删除、替换、拼接节点，支持双向遍历。
使用复杂度	API简单，但需要理解其使用场景限制（如MP/SC模型）。	API丰富，使用灵活，但必须时刻注意正确的加锁和解锁。
适用场景	高并发、对延迟敏感的MP/SC队列，尤其适用于中断上下文。	通用的链表需求，需要丰富的链表操作，且并发竞争不成为瓶颈的场景。

此代码片段是Linux内核中一个基础且性能极高的数据结构——无锁单向链表(llist)的完整实现。它的设计目标是在特定的并发场景下, 提供一种完全不需要使用锁(如自旋锁或互斥锁)即可安全地进行添加和删除操作的链表。

llist是为解决经典”生产者-消费者”问题而生的, 特别是在性能要求极高的内核路径中。最典型的应用场景就是我们之前分析的blk-mq I/O完成路径:

生产者 (Producers): 多个硬件中断处理程序(ISRs)。当I/O完成时, 它们需要极快地将一个request结构体添加到一个”已完成”列表中。中断处理程序不能睡眠, 且持有锁的时间越短越好。
消费者 (Consumer): 一个软中断(softirq)处理函数。它需要在稍后的时间点, 一次性地取走所有已完成的request进行处理。

llist完美地满足了这个需求, 它允许多个生产者(llist_add)和一个消费者(llist_del_all)在没有任何锁的情况下并发操作。

核心原理: 原子操作

llist的”无锁”特性完全依赖于CPU提供的原子指令(atomic instructions)。这些指令能够在硬件层面保证一个”读-改-写”序列的原子性, 不会被其他CPU核心或中断打断。

cmpxchg (Compare-and-Exchange / 比较并交换): 这是llist添加和单个删除操作的核心。它的伪代码是:
1
2
3
4
5
6
7
8
bool cmpxchg(pointer *p, pointer old, pointer new) {
// 以下操作是原子的
if (*p == old) {
*p = new;
return true;
}
return false;
}
llist_add使用它在一个循环中尝试将新节点插入链表头, 只有当链表头在”读”和”写”之间没有被其他生产者改变时, 操作才会成功。
xchg (Exchange / 交换): 这是llist_del_all批量删除操作的核心。它原子地将一个内存位置的值与一个新值交换, 并返回旧值。llist_del_all简单地调用xchg(&head->first, NULL), 这一条指令就安全地将整个链表”摘下”, 并将链表头清空。

在STM32H750 (ARMv7-M)上的实现:
ARMv7-M架构提供了LDREX (Load-Exclusive) 和 STREX (Store-Exclusive) 指令对, 内核和GCC编译器使用这对指令来实现cmpxchg等原子操作。因此, 即使是在单核系统上, llist的原子性也由硬件保证, 能够安全地处理任务上下文与中断上下文之间的并发访问。

使用规则与并发性 (非常重要)

头文件注释中的矩阵清晰地总结了使用规则:

多个生产者(llist_add)可以与一个消费者(llist_del_all)并发, 无需锁。
多个生产者(llist_add)可以与一个消费者(llist_del_first)并发, 无需锁。
不能让多个消费者同时使用llist_del_first或llist_del_all, 除非它们之间由外部的锁来保护。这是因为llist_del_first的实现依赖于对head->first->next的读取, 存在ABA问题, 多个消费者并发删除可能破坏链表。

`llist_add`: 添加一个新节点 (生产者)

/* llist_add: 将一个新节点添加到链表头. */
static inline bool llist_add(struct llist_node *new, struct llist_head *head)
{
	/* 它调用了 llist_add_batch, 这是一个更通用的版本. */
	return llist_add_batch(new, new, head);
}

static inline bool llist_add_batch(struct llist_node *new_first,
				   struct llist_node *new_last,
				   struct llist_head *head)
{
	/* 步骤1: 读取当前链表的头节点. READ_ONCE确保这是一次原子的读取. */
	struct llist_node *first = READ_ONCE(head->first);

	/* 步骤2: 进入一个循环, 尝试将新节点插入. */
	do {
		/* 将新节点的next指针指向我们刚才看到的头节点, 准备插入. */
		new_last->next = first;
		/*
		 * 步骤3: 原子地尝试更新链表头.
		 * try_cmpxchg(&head->first, &first, new_first) 的意思是:
		 * "如果 head->first 的值仍然是 first (即没有其他线程修改过它),
		 *  那么就将 head->first 更新为 new_first, 并返回 true."
		 * "如果 head->first 的值已经被其他线程改变了, 那么更新失败,
		 *  返回 false, 并且将 first 的值更新为当前最新的 head->first 值."
		 */
	} while (!try_cmpxchg(&head->first, &first, new_first));

	/* 如果在我们插入之前链表为空(first为NULL), 则返回true. */
	return !first;
}

`llist_del_all`: 原子地取走整个链表 (消费者)

/* llist_del_all: 从链表中删除所有节点. */
static inline struct llist_node *llist_del_all(struct llist_head *head)
{
	/*
	 * xchg(&head->first, NULL) 是一条原子指令.
	 * 它原子地将 head->first 的值设置为 NULL, 并返回它之前的值.
	 * 这一步操作就干净利落地将整个链表从全局头中断开, 并返回了链表的第一个节点.
	 * 这是极其高效的.
	 */
	return xchg(&head->first, NULL);
}

`llist_del_first`: 原子地取走第一个节点 (消费者)

/* llist_del_first: 从链表中删除第一个节点. */
struct llist_node *llist_del_first(struct llist_head *head)
{
	struct llist_node *entry, *next;

	/*
	 * smp_load_acquire 是一种带内存屏障的原子读取,
	 * 确保我们能看到其他CPU上最新的 head->first 值.
	 */
	entry = smp_load_acquire(&head->first);
	/* 进入一个循环, 逻辑与 llist_add 类似. */
	do {
		/* 如果链表为空, 直接返回NULL. */
		if (entry == NULL)
			return NULL;
		/* 读取第一个节点的下一个节点. */
		next = READ_ONCE(entry->next);
		/*
		 * 尝试原子地将链表头指向 next,
		 * 但前提是链表头仍然是我们之前看到的 entry.
		 */
	} while (!try_cmpxchg(&head->first, &entry, next));

	/* 成功删除, 返回被删除的节点. */
	return entry;
}
EXPORT_SYMBOL_GPL(llist_del_first);

`llist_reverse_order`: 反转链表

llist是一个LIFO(后进先出)的栈结构。llist_del_all取出的链表是按”最新到最旧”的顺序排列的。在I/O完成等场景下, 我们通常希望按FIFO(先进先出)的顺序处理, 以保证公平性。此函数就是用于将LIFO链表反转为FIFO链表的。

/* llist_reverse_order: 反转一个llist链表的顺序. */
struct llist_node *llist_reverse_order(struct llist_node *head)
{
	/* 这是一个标准的、非原子的单向链表反转算法. */
	struct llist_node *new_head = NULL;

	while (head) {
		struct llist_node *tmp = head;
		head = head->next;
		tmp->next = new_head;
		new_head = tmp;
	}

	return new_head;
}
EXPORT_SYMBOL_GPL(llist_reverse_order);

遍历宏 (`llist_for_each_*`)

这些宏提供了与内核标准list.h类似的遍历接口, 但有一个极其重要的规则: 它们只能用于遍历一个已经通过llist_del_all从主链表中安全删除的、本地的链表。绝对不能在llist还处于”活跃”状态时尝试遍历它, 因为生产者可能随时在修改链表头, 会导致遍历出错。

lib/klist.c 内核链表(Kernel List) 支持安全遍历的设备模型专用链表

历史与背景

这项技术是为了解决什么特定问题而诞生的？

klist 是一种特殊的内核链表实现，它的诞生主要是为了解决在Linux设备模型中一个非常棘手且常见的并发问题：如何在遍历一个链表的同时，安全地允许链表中的节点被移除？

并发的设备操作：在Linux内核中，一个总线（bus）上可能挂载了多个设备（device）。内核代码（例如电源管理子系统）经常需要遍历这个总线上的所有设备来执行某个操作（如 suspend）。与此同时，用户可能会通过热插拔（hotplug）移除其中一个设备。
传统链表的危险性：如果使用标准的、由自旋锁保护的 list_head 链表，要实现安全遍历，就必须在整个遍历开始之前锁住链表，直到遍历结束后才解锁。这会导致非常长的锁持有时间，严重影响系统性能和响应性。例如，在一个设备 suspend 的过程中锁住总线，会阻止任何其他设备的添加或移除操作。
Use-After-Free风险：如果不锁住整个遍历过程，那么当遍历器指向一个节点时，另一个线程（如热插拔处理线程）可能会释放这个节点，导致遍历器后续访问一个无效的内存地址，引发系统崩溃。

klist 被设计出来，就是为了在不需要长时间锁定的情况下，优雅地解决这个问题。

它的发展经历了哪些重要的里程碑或版本迭代？

klist 是与Linux设备驱动模型（Driver Model）一起诞生和演进的。它的出现本身就是设备模型设计的一个重要里程碑，标志着内核有了一种健壮的机制来管理动态的设备集合。自被引入以来，klist 的核心设计（基于引用计数）一直非常稳定，其发展主要体现在它在内核中，特别是在 drivers/base/ 目录下的驱动核心代码中的深度集成和广泛应用。它已经成为设备模型中处理“一对多”关系（如一个总线对应多个设备）的标准实现。

目前该技术的社区活跃度和主流应用情况如何？

klist 是一个非常成熟和稳定的内核基础组件。它的代码不经常变动，但它作为设备模型正常运转的基石，被内核中几乎所有的总线和设备驱动所依赖。它的主流应用场景高度集中在：

管理总线上的设备列表（bus_type->p->klist_devices）。
管理驱动程序绑定的设备列表（driver->p->klist_devices）。
其他需要安全地遍历动态集合的内核子系统。

核心原理与设计

它的核心工作原理是什么？

klist 的核心魔力在于它将链表操作与**引用计数（reference counting）**机制巧妙地结合在一起。

数据结构：
- klist：包含一个自旋锁 k_lock 和一个标准的链表头 k_list。
- klist_node：要加入 klist 的每个节点都必须包含一个 klist_node 结构。这个结构内部除了有标准的 list_head 节点 n_node 之外，还有一个关键成员：kref 引用计数器 n_ref。
遍历 (klist_iter)：
- 当你使用 klist_iter_init 初始化一个遍历器并调用 klist_next 来获取下一个节点时，klist_next 函数在内部会**增加（get）**该节点的引用计数（kref_get）。
- 这意味着，只要遍历器指向这个节点，该节点就至少有一次额外的引用，保证了它不会被彻底释放。
- 当遍历器移动到下一个节点时，它会**减少（put）**上一个节点的引用计数（kref_put）。
移除 (klist_del)：
- 当一个节点需要从 klist 中被移除时（例如设备被拔出），代码会调用 klist_del。
- klist_del 会短暂地获取 klist 的自旋锁，将该节点从 k_list 链表中移除（这样新的遍历就不会再看到它）。
- 然后，它会减少该节点的引用计数。
安全保证：
- 现在考虑并发场景：一个遍历器正指向节点A（已对A的 kref 加一）。此时，另一个线程调用 klist_del 来移除节点A。
- 节点A被从链表中移除，但它的引用计数因为被遍历器持有，所以不会降到0。因此，节点A的内存不会被释放。
- 遍历器可以安全地访问节点A的内容，并顺着它之前保存的 next 指针继续下一次遍历。
- 当遍历器最终离开节点A时，它会减少A的引用计数。如果此时没有其他引用，计数会降为0，这时才会触发真正的内存释放操作。

通过这种方式，klist 实现了“移除”和“最终销毁”的分离，从而保证了遍历的安全性。

它的主要优势体现在哪些方面？

遍历安全：这是其最核心的优势。它允许在遍历一个列表的同时，列表中的节点被安全地移除，而不会导致 use-after-free 错误。
细粒度锁：它仅在添加或删除节点的瞬间使用自旋锁，而整个遍历过程是无需持有这个锁的。这大大提高了系统的并发性能。
健壮性：为动态变化的设备集合提供了一个非常可靠的管理模型。

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

性能开销：与简单的 list_head 相比，klist 有额外的开销。每一次遍历节点都需要进行原子操作来增减引用计数。每个节点也需要额外的内存来存储 kref 对象。
使用复杂性：它的API和使用模式比标准链表更复杂。开发者需要理解其引用计数的工作原理。
并非通用：它是一个特化设计。如果你的场景中不存在“遍历与移除”的并发问题，那么使用更简单的、由锁保护的 list_head 会更高效、更直接。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？请举例说明。

klist 是处理需要安全遍历的动态内核对象集合的首选，尤其是在驱动模型中。

场景一：设备热插拔
电源管理子系统需要让一个USB总线上的所有设备都进入休眠状态。它会启动一个 klist_iter 来遍历该总线的所有设备。当它正在处理第一个设备时，用户拔掉了第二个设备。klist 机制确保，即使第二个设备的移除逻辑已经开始执行，遍历器在后续步骤中访问它时也不会导致系统崩溃。
场景二：驱动卸载
一个总线驱动（如PCI总线驱动）正在被卸载（rmmod）。卸载逻辑需要遍历所有它管理的设备，并执行清理操作。klist 确保了这个遍历过程的安全性，即使在遍历期间有其他事件发生。

是否有不推荐使用该技术的场景？为什么？

无并发修改的场景：如果一个链表只被单个线程访问，或者对它的所有访问（包括遍历和修改）都已经由一个外部的锁完美保护，那么使用 klist 是不必要的，只会增加开销。
静态或极少变化的列表：对于内容基本不变的列表，klist 的引用计数机制就成了纯粹的开销。

对比分析

请将其与其他相似技术进行详细对比。

klist 的主要对比对象是使用锁保护的标准链表（spinlock + list_head）以及RCU（Read-Copy-Update）保护的链表。

特性	klist	spinlock + list_head	RCU (Read-Copy-Update)
并发模型	细粒度的引用计数，保证遍历器安全。写操作（add/del）受短时自旋锁保护。	粗粒度的互斥。读（遍历）和写（修改）操作都必须获取同一个锁。	读操作完全无锁（wait-free）。写操作需要复制、修改，并通过“宽限期”延迟释放。
遍历安全	内置安全。专为此场景设计。	不安全，除非在整个遍历期间都持有锁，但这会严重影响性能。	安全。读取器看到的是修改发生前的一个一致性快照。
性能开销	遍历时每次移动都有原子操作的开销。写操作有自旋锁开销。	遍历本身无开销，但获取/释放锁以及锁竞争的开销可能非常大。	读操作几乎无开销。写操作的开销较大，且有延迟释放的内存压力。
使用复杂度	中等。需要理解其API和引用计数模型。	低。概念简单，但容易因锁使用不当导致死锁或性能问题。	高。要求开发者对RCU原理、内存屏障有深入理解。
典型应用	设备模型中的总线-设备、驱动-设备列表。	内核中绝大多数通用的、并发度不极端的链表。	性能极其敏感的、读多写少的数据结构，如网络路由表、系统调用表。

klist (Kernel List) 是一种增强型的内核链表。与标准的 struct list_head 双向链表相比，klist 额外提供了两个核心功能：
1. 并发安全 (Concurrency Safety): klist 内嵌了一个自旋锁 (spinlock)，用于保护链表在被多个执行上下文（例如，不同的内核线程，或者任务与中断处理程序之间）同时访问或修改时的数据一致性。
2. 引用计数集成 (Reference Counting Integration): klist 允许在初始化时注册两个回调函数：get 和 put。这两个函数与链表成员所嵌入的宿主对象的生命周期管理（通常是引用计数）相绑定。这使得在遍历 klist 的过程中，可以安全地处理成员的动态添加和删除，从根本上杜绝了“使用已释放内存”(use-after-free) 的风险。

klist_init 初始化一个 klist 结构体

/*
 * klist_init - 初始化一个 klist 结构体
 * @k: 我们要初始化的 klist 结构体的指针
 * @get: 用于获取宿主对象引用的函数 (如果没有则为 NULL)
 * @put: 用于释放宿主对象引用的函数 (如果没有则为 NULL)
 *
 * 本函数用于初始化 klist 结构体。如果 klist_node 节点被嵌入在
 * 需要进行引用计数的对象中（这对于安全删除是必需的），那么 get 和 put
 * 参数将被用来初始化对应的函数，这两个函数负责获取和释放
 * 宿主对象的引用。
 */
void klist_init(struct klist *k, void (*get)(struct klist_node *),
		void (*put)(struct klist_node *))
{
	/*
	 * 初始化 klist 结构体内部的双向链表头。
	 * INIT_LIST_HEAD 宏会将链表头的 'next' 和 'prev' 指针都指向它自身，
	 * 这表示链表当前为空。
	 * 'k->k_list' 是一个标准的 'struct list_head' 成员。
	 */
	INIT_LIST_HEAD(&k->k_list);

	/*
	 * 初始化 klist 结构体内部的自旋锁。
	 * spin_lock_init 宏会设置锁为“未锁定”状态。
	 * 这个锁 ('k->k_lock') 用于保护对 'k->k_list' 链表的所有访问操作，
	 * 确保在并发环境（即使是单核的中断抢占场景）下的数据完整性。
	 */
	spin_lock_init(&k->k_lock);

	/*
	 * 将调用者提供的 'get' 函数指针保存到 klist 结构体中。
	 * 这个函数将在 klist 迭代器访问一个节点时被调用，用于增加
	 * 该节点所属的宿主对象的引用计数。
	 * 如果传入的 'get' 为 NULL，则表示不需要进行引用计数管理。
	 */
	k->get = get;

	/*
	 * 将调用者提供的 'put' 函数指针保存到 klist 结构体中。
	 * 这个函数将在 klist 迭代器结束对一个节点的访问时被调用，
	 * 用于减少宿主对象的引用计数。
	 * 'put' 函数必须与 'get' 函数成对提供。
	 */
	k->put = put;
}
/*
 * 将 klist_init 函数导出，使其可以被内核模块调用。
 * _GPL 后缀表示只有遵循 GPL 兼容许可证的模块才能使用此函数。
 */
EXPORT_SYMBOL_GPL(klist_init);

文章作者: Liya Huang

文章链接: https://wdfk-prog.space/posts/44c8f818/

linux lib

赞助

微信
支付寶

include/linux/list.h 内核双向循环链表(Kernel Doubly-Linked List) 内核数据结构的基础构建块

历史与背景

这项技术是为了解决什么特定问题而诞生的？

它的发展经历了哪些重要的里程碑或版本迭代？

目前该技术的社区活跃度和主流应用情况如何？

核心原理与设计

它的核心工作原理是什么？

它的主要优势体现在哪些方面？

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？

是否有不推荐使用该技术的场景？为什么？

对比分析

请将其 与 其他相似技术 进行详细对比。

__list_del 通过使 prev/next 条目彼此指向来删除列表条目

list_add 在指定的 head 后插入新条目

list_move 从一个列表中删除并添加到另一个列表的head后面

list_move_tail 从一个列表中删除并添加到另一个列表的尾部

include/linux/list_bl.h 内核带位锁的链表(Kernel List with Bit Lock) 为大规模哈希表优化的内存效率方案

历史与背景

这项技术是为了解决什么特定问题而诞生的？

它的发展经历了哪些重要的里程碑或版本迭代？

目前该技术的社区活跃度和主流应用情况如何？

核心原理与设计

它的核心工作原理是什么？

它的主要优势体现在哪些方面？

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？

是否有不推荐使用该技术的场景？为什么？

对比分析

请将其 与 其他相似技术 进行详细对比。

INIT_HLIST_BL_HEAD

include/linux/llist.h 无锁单向链表(Lock-Less Singly-Linked List) 高并发场景下的高效数据结构

历史与背景

这项技术是为了解决什么特定问题而诞生的？

它的发展经历了哪些重要的里程碑或版本迭代？

目前该技术的社区活跃度和主流应用情况如何？

核心原理与设计

它的核心工作原理是什么？

它的主要优势体现在哪些方面？

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？请举例说明。

是否有不推荐使用该技术的场景？为什么？

对比分析

请将其 与 其他相似技术 进行详细对比。

核心原理: 原子操作

使用规则与并发性 (非常重要)

llist_add: 添加一个新节点 (生产者)

llist_del_all: 原子地取走整个链表 (消费者)

llist_del_first: 原子地取走第一个节点 (消费者)

llist_reverse_order: 反转链表

遍历宏 (llist_for_each_*)

lib/klist.c 内核链表(Kernel List) 支持安全遍历的设备模型专用链表

历史与背景

这项技术是为了解决什么特定问题而诞生的？

它的发展经历了哪些重要的里程碑或版本迭代？

目前该技术的社区活跃度和主流应用情况如何？

核心原理与设计

它的核心工作原理是什么？

它的主要优势体现在哪些方面？

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？请举例说明。

是否有不推荐使用该技术的场景？为什么？

对比分析

请将其 与 其他相似技术 进行详细对比。

klist_init 初始化一个 klist 结构体

请将其与其他相似技术进行详细对比。

请将其与其他相似技术进行详细对比。

请将其与其他相似技术进行详细对比。

`llist_add`: 添加一个新节点 (生产者)

`llist_del_all`: 原子地取走整个链表 (消费者)

`llist_del_first`: 原子地取走第一个节点 (消费者)

`llist_reverse_order`: 反转链表

遍历宏 (`llist_for_each_*`)

请将其与其他相似技术进行详细对比。