[TOC]

在这里插入图片描述

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

历史与背景

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

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

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

  1. 重复造轮子：自己定义一套链表节点和操作函数，导致代码冗余和不一致。
  2. 使用非侵入式链表：创建一个通用的链表节点结构，其中包含一个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宏**的巧妙运用。

  1. 侵入式数据结构：

    • 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的实例本身就包含了链表节点，无需额外分配内存。

  2. 链表操作：

    • 所有的链表操作（如list_add, list_del）都是直接针对这个嵌入的list_head成员进行的。这些操作只关心next和prev指针，完全不知道也不关心包含它的my_struct的存在。

  3. 从节点找回容器 (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。

  4. 遍历 (Iteration)：

    • list_for_each_entry(pos, head, member)这个宏将遍历过程和list_entry的转换完美地封装在一起，使得遍历代码既简洁又类型安全。
      1
      2
      3
      4
      5
      6
      7
      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 条目彼此指向来删除列表条目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 * 通过使 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 后插入新条目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
 * 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后面

1
2
3
4
5
6
7
8
9
10
/**
 * 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 从一个列表中删除并添加到另一个列表的尾部

1
2
3
4
5
6
7
8
9
10
11
/**
 * 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并发访问时，它必须被一个锁保护起来。通常的做法是这样的：

1
2
3
4
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）。

  1. 地址对齐的前提：在现代计算机体系结构中，为了性能，所有多字节的数据结构（如struct hlist_bl_node）都会被对齐（aligned）到4字节或8字节的内存边界上。这意味着它们的内存地址永远是4或8的倍数，因此其二进制表示的最低两位或三位永远是0。
  2. 位锁（Bit Lock）：list_bl利用了这个特性，将指针的最低有效位（bit 0）挪作他用，把它当作一个锁定位。
    • 当 bit 0 为 0 时，表示该链表是未锁定的。
    • 当 bit 0 为 1 时，表示该链表是已锁定的。
  3. 核心数据结构：struct list_bl_head的核心是一个指针。这个指针的值同时编码了两种信息：链表第一个节点的地址（除了bit 0之外的其他所有位）和锁的状态（bit 0）。
  4. 上锁与解锁：
    • 上锁 (list_bl_lock())：这个函数会使用一个原子的、CPU提供的test-and-set-bit指令来尝试将指针的bit 0设置为1。这是一个**自旋（spin）**过程：如果设置成功（说明之前是0），则获得锁；如果设置失败（说明之前已经是1），则在一个循环中不断重试，直到成功为止。
    • 解锁 (list_bl_unlock())：这个函数使用一个原子的clear-bit指令将指针的bit 0清零。
  5. 获取真实指针：当需要访问链表的第一个节点时，必须先将锁定位屏蔽掉。代码会执行一个位操作 (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)。 低 (非常标准和常见的模式)。 低 (标准模式)。
适用场景 大规模哈希表，内存极度敏感。 通用的、非睡眠的链表保护。 需要在临界区内睡眠的链表保护。 
1
2
3
4
/*
* 列表的特殊版本，其中列表的头部在最低位有一个锁。这对于可扩展的哈希表非常有用，同时不会增加内存开销。
* 对于修改操作，必须设置 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）操作的原理大致如下：

  1. 读取旧头：生产者线程首先原子性地读取当前链表的头指针（head->first）。
  2. 准备新节点：生产者将新节点的 next 指针指向刚才读取的旧头。
  3. 原子更新：生产者使用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核心或中断打断。

  1. 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使用它在一个循环中尝试将新节点插入链表头, 只有当链表头在”读”和”写”之间没有被其他生产者改变时, 操作才会成功。

  2. 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: 添加一个新节点 (生产者)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* 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: 原子地取走整个链表 (消费者)

1
2
3
4
5
6
7
8
9
10
11
/* 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: 原子地取走第一个节点 (消费者)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* 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链表的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 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）**机制巧妙地结合在一起。

  1. 数据结构：
    • klist：包含一个自旋锁 k_lock 和一个标准的链表头 k_list。
    • klist_node：要加入 klist 的每个节点都必须包含一个 klist_node 结构。这个结构内部除了有标准的 list_head 节点 n_node 之外，还有一个关键成员：kref 引用计数器 n_ref。
  2. 遍历 (klist_iter)：
    • 当你使用 klist_iter_init 初始化一个遍历器并调用 klist_next 来获取下一个节点时，klist_next 函数在内部会**增加（get）**该节点的引用计数（kref_get）。
    • 这意味着，只要遍历器指向这个节点，该节点就至少有一次额外的引用，保证了它不会被彻底释放。
    • 当遍历器移动到下一个节点时，它会**减少（put）**上一个节点的引用计数（kref_put）。
  3. 移除 (klist_del)：
    • 当一个节点需要从 klist 中被移除时（例如设备被拔出），代码会调用 klist_del。
    • klist_del 会短暂地获取 klist 的自旋锁，将该节点从 k_list 链表中移除（这样新的遍历就不会再看到它）。
    • 然后，它会减少该节点的引用计数。
  4. 安全保证：
    • 现在考虑并发场景：一个遍历器正指向节点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 结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
 * 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);

klist 迭代器初始化：klist_iter_init_node 与 klist_iter_init

本代码片段展示了 Linux 内核中 klist（一种引用计数的链表）迭代器的初始化函数。其核心功能是为一个 klist_iter 结构体（迭代器/游标）设置其初始状态，使其准备好开始遍历一个 klist。它通过安全地获取对指定起始节点的引用，来确保遍历的起点是有效且不会被并发释放的，从而为后续的 klist_next 操作提供了安全保障。

实现原理分析

此代码是 klist 安全遍历机制的入口点，其实现原理的关键在于利用引用计数来解决并发环境下的 use-after-free 问题。

  1. 引用计数作为安全保障:

    • klist 的设计哲学是，任何对链表节点的有效访问都必须持有该节点的一个引用。迭代器 klist_iter 也不例外，它的 i_cur 字段指向的当前节点，必须是一个已经被迭代器持有了引用的节点。
    • 初始化过程的本质，就是为迭代器安全地获取对第一个节点（即起始节点）的引用。

  2. kref_get_unless_zero 原子操作:

    • klist_iter_init_node 函数中最核心的操作是 kref_get_unless_zero(&n->n_ref)。这是一个原子的、有条件的引用计数增加操作。
    • 原子性: 它能保证在检查和增加引用计数的过程中，不会被其他任务或中断打断。
    • 条件性 (_unless_zero): 这是最关键的特性。它只在节点的当前引用计数不为零的情况下，才会成功地将引用计数加一并返回 true。如果引用计数已经为零，意味着该节点正处于被销毁的过程中，此时尝试获取一个新的引用是不安全的。在这种情况下，kref_get_unless_zero 会失败并返回 false。
    • 目的: 这个函数完美地解决了在初始化迭代器时可能发生的竞态条件：当一个任务尝试以节点 n 为起点初始化迭代器时，另一个任务（或中断）可能正在释放节点 n。kref_get_unless_zero 确保了只有当节点 n 仍然“存活”（引用计数 > 0）时，迭代器才能成功地将其设置为当前节点，否则 i->i_cur 将保持为 NULL，表示一个无效或空的起始点。

  3. 封装与便利性 (klist_iter_init):

    • klist_iter_init 是一个简单的内联封装函数。它调用 klist_iter_init_node 并将起始节点 n 显式地设置为 NULL。
    • 这为最常见的用例——从链表的头部开始遍历——提供了一个更简洁的 API。当 n 为 NULL 时，i_cur 会被初始化为 NULL，后续的 klist_next 调用将自动从 klist 的链表头开始查找第一个有效的节点。

代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * @brief klist_iter_init_node - 初始化一个 klist_iter 结构体。
 * @param k: 要遍历的 klist。
 * @param i: 要被初始化的 klist_iter 结构体。
 * @param n: 迭代开始的节点。
 *
 * 与 klist_iter_init() 类似，但从指定的节点 @n 开始，而不是从链表头开始。
 */
void klist_iter_init_node(struct klist *k, struct klist_iter *i,
			  struct klist_node *n)
{
	// 在迭代器中保存要遍历的 klist 的指针。
	i->i_klist = k;
	// 将迭代器的当前节点指针初始化为 NULL，这是一个安全默认值。
	i->i_cur = NULL;
	// 如果提供了一个有效的起始节点 n，并且...
	// ...成功地获取了该节点的引用（即该节点的引用计数不为0），则...
	if (n && kref_get_unless_zero(&n->n_ref))
		// ...将迭代器的当前节点设置为该起始节点。
		// 这确保了迭代器持有一个对起始节点的有效引用。
		i->i_cur = n;
}
EXPORT_SYMBOL_GPL(klist_iter_init_node);

/**
 * @brief klist_iter_init - 初始化一个 klist_iter 结构体。
 * @param k: 要遍历的 klist。
 * @param i: 要被初始化的 klist_iter 结构体。
 *
 * 与 klist_iter_init_node() 类似，但总是从链表的头部开始。
 */
void klist_iter_init(struct klist *k, struct klist_iter *i)
{
	// 调用核心实现，并将起始节点设置为 NULL，
	// 表示后续的 klist_next() 将从链表头开始查找。
	klist_iter_init_node(k, i, NULL);
}
EXPORT_SYMBOL_GPL(klist_iter_init);

/**
 * klist_iter_exit - Finish a list iteration.
 * @i: Iterator structure.
 *
 * Must be called when done iterating over list, as it decrements the
 * refcount of the current node. Necessary in case iteration exited before
 * the end of the list was reached, and always good form.
 */
void klist_iter_exit(struct klist_iter *i)
{
	if (i->i_cur) {
		klist_put(i->i_cur, false);
		i->i_cur = NULL;
	}
}
EXPORT_SYMBOL_GPL(klist_iter_exit);

klist 迭代器移动原语：klist_next 与 klist_prev

本代码片段展示了 Linux 内核 klist 迭代器的核心驱动引擎：klist_next 和 klist_prev。其主要功能是以一种并发安全的方式，将迭代器（klist_iter）从当前节点移动到下一个或上一个有效节点。这个过程的核心是精妙的引用计数管理：在移动时，它会安全地释放对前一个节点的引用，并获取对新节点的引用，从而保证迭代器在任何时刻都持有一个有效的、不会被释放的“游标”。

实现原理分析

klist_next 和 klist_prev 的实现逻辑几乎完全对称，是内核中“获取锁-操作-释放锁”和引用计数模式的典范。以 klist_next 为例：

  1. 锁定与状态保存:

    • spin_lock_irqsave(&i->i_klist->k_lock, flags): 这是第一步也是最关键的一步。它获取了 klist 自己的自旋锁，并禁用了本地中断。这确保了在整个移动操作的关键区内，链表本身 (k_list) 不会被任何其他任务或中断并发地修改。

  2. 释放旧引用:

    • last = i->i_cur: 保存迭代器当前指向的节点（即上一步的节点）。
    • next = to_klist_node(last->n_node.next): 找到物理上的下一个链表节点。
    • klist_dec_and_del(last): 对 last 节点（如果存在）执行“减少引用计数并测试是否为零”的原子操作。
      • 如果引用计数不变为零，意味着还有其他用户持有该节点的引用，此时迭代器只需放弃自己的引用即可。为了避免后续调用 put 函数（可能导致重复释放），put 指针被设为 NULL。
      • 如果引用计数变为零，意味着迭代器是最后一个持有者。此时节点可以被安全地从链表中移除（klist_dec_and_del 内部会这样做）。put 指针保持有效，以便在锁释放后调用。

  3. 查找并获取新引用:

    • i->i_cur = NULL: 先将迭代器的当前指针清空，这是一个安全措施。
    • while (next != ...): 从物理上的下一个节点开始循环。
    • knode_dead(next): 这是一个关键的检查。即使一个节点仍在链表中，它也可能已经被标记为“死亡”（正在被移除的过程中）。这个检查会跳过这些“僵尸”节点。
    • kref_get(&next->n_ref): 一旦找到了一个“存活”的节点 next，就立即增加其引用计数。这为迭代器获取了对新节点的“所有权”。
    • i->i_cur = next; break;: 将迭代器指向这个新获取的节点，并退出循环。

  4. 解锁与延迟调用 (put):

    • spin_unlock_irqrestore(...): 释放自旋锁并恢复中断状态。
    • if (put && last) put(last);: 这是一个非常重要的延迟调用。put 函数（通常是 kfree 或更复杂的清理函数）可能需要睡眠或执行耗时操作，这在自旋锁保护的关键区内是绝对禁止的。因此，只有在完全释放锁之后，才调用 put 函数来执行最终的清理工作。

代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/**
 * @brief to_klist_node - 将 list_head 指针转换为其所属的 klist_node 指针。
 * @param n: 指向 list_head 成员的指针。
 * @return struct klist_node*: 指向 klist_node 结构体的指针。
 * @note 这是一个使用 container_of 宏实现的类型安全的转换。
 */
static struct klist_node *to_klist_node(struct list_head *n)
{
	return container_of(n, struct klist_node, n_node);
}

/**
 * @brief klist_prev - 将迭代器移动到前一个有效节点。
 * @param i: 迭代器结构体。
 * @return struct klist_node*: 成功则返回前一个节点的指针，遍历结束返回 NULL。
 */
struct klist_node *klist_prev(struct klist_iter *i)
{
	// 获取 klist 中定义的对象释放函数。
	void (*put)(struct klist_node *) = i->i_klist->put;
	struct klist_node *last = i->i_cur; /// < 保存迭代器当前指向的节点。
	struct klist_node *prev; /// < 用于指向下一个目标节点。
	unsigned long flags;

	// 获取自旋锁并禁用中断，保护对 klist 的访问。
	spin_lock_irqsave(&i->i_klist->k_lock, flags);

	if (last) { // 如果迭代器当前指向一个有效节点...
		// ...找到其物理上的前一个节点。
		prev = to_klist_node(last->n_node.prev);
		// 减少当前节点的引用计数。如果计数不为0，则不需要调用 put 函数。
		if (!klist_dec_and_del(last))
			put = NULL;
	} else // 如果迭代器是新初始化的 (i_cur 为 NULL)...
		// ...则从 klist 的尾部开始。
		prev = to_klist_node(i->i_klist->k_list.prev);

	i->i_cur = NULL; // 先将当前指针清空。
	// 从 prev 开始向前遍历，直到回到链表头。
	while (prev != to_klist_node(&i->i_klist->k_list)) {
		// 如果节点不是“死亡”状态...
		if (likely(!knode_dead(prev))) {
			// ...则增加其引用计数，为迭代器获取所有权。
			kref_get(&prev->n_ref);
			// 更新迭代器的当前指针。
			i->i_cur = prev;
			break; // 找到有效节点，退出循环。
		}
		// 如果是死亡节点，则继续向前查找。
		prev = to_klist_node(prev->n_node.prev);
	}

	// 释放自旋锁并恢复中断。
	spin_unlock_irqrestore(&i->i_klist->k_lock, flags);

	// 在锁之外，如果需要，则调用释放函数。
	if (put && last)
		put(last);
	return i->i_cur;
}
EXPORT_SYMBOL_GPL(klist_prev);

/**
 * @brief klist_next - 将迭代器移动到下一个有效节点。
 * @param i: 迭代器结构体。
 * @return struct klist_node*: 成功则返回下一个节点的指针，遍历结束返回 NULL。
 */
struct klist_node *klist_next(struct klist_iter *i)
{
	// (此函数逻辑与 klist_prev 完全对称)
	void (*put)(struct klist_node *) = i->i_klist->put;
	struct klist_node *last = i->i_cur;
	struct klist_node *next;
	unsigned long flags;

	spin_lock_irqsave(&i->i_klist->k_lock, flags);

	if (last) {
		next = to_klist_node(last->n_node.next);
		if (!klist_dec_and_del(last))
			put = NULL;
	} else
		next = to_klist_node(i->i_klist->k_list.next);

	i->i_cur = NULL;
	while (next != to_klist_node(&i->i_klist->k_list)) {
		if (likely(!knode_dead(next))) {
			kref_get(&next->n_ref);
			i->i_cur = next;
			break;
		}
		next = to_klist_node(next->n_node.next);
	}

	spin_unlock_irqrestore(&i->i_klist->k_lock, flags);

	if (put && last)
		put(last);
	return i->i_cur;
}
EXPORT_SYMBOL_GPL(klist_next);

klist 节点最终释放与同步等待：klist_release 与 klist_dec_and_del

本代码片段展示了 klist（引用计数链表）生命周期管理的最后、也是最关键的一步：当一个 klist_node 的最后一个引用被释放时，所触发的最终清理和同步唤醒机制。klist_dec_and_del 是一个便捷的封装器，用于安全地减少节点的引用计数；而 klist_release 则是当引用计数降至零时被自动调用的“析构函数”，它负责将节点从链表中物理移除，并唤醒任何正在同步等待此节点彻底消失的任务。

实现原理分析

此机制的核心是 kref（内核引用计数）框架与一个全局“等待者”链表的精妙结合，以解决复杂的同步删除问题。

  1. kref 驱动的析构 (klist_dec_and_del):

    • klist_dec_and_del 是 klist 引用计数管理的主要接口。它并不直接执行删除操作，而是调用 kref_put(&n->n_ref, klist_release)。
    • kref_put 是 kref 框架的核心函数。它会原子地将引用计数减一。
    • 条件析构: 只有当 kref_put 发现引用计数恰好从 1 降为 0 时，它才会调用作为第二个参数传入的函数指针，即 klist_release。如果引用计数减一后仍大于 0，kref_put 就直接返回。
    • 返回值: klist_dec_and_del 返回 kref_put 的结果，该结果可以告诉调用者，这次 put 操作是否触发了最终的释放。

  2. 最终释放与唤醒 (klist_release):

    • 此函数是 klist_node 的真正“析构函数”，只在节点生命周期的最后一刻被调用。
    • 健全性检查 (WARN_ON): WARN_ON(!knode_dead(n)) 是一个重要的断言。它确保了只有在节点已经被逻辑上标记为“死亡”（通常由 klist_del 或类似函数完成）之后，它的最后一个引用才能被释放。这是一种强制的生命周期管理，防止了意外的释放。
    • 物理摘除: list_del(&n->n_node) 将节点从其 list_head 双向链表中物理地摘除。
    • 同步等待者机制: 这是此函数最复杂的部分。
      a. 内核维护一个全局的等待者链表 klist_remove_waiters，受全局锁 klist_remove_lock 保护。
      b. 当一个任务需要同步地等待某个 klist_node 被彻底移除时，它会创建一个 klist_waiter 结构（包含目标节点指针和自身 task_struct 指针），将其加入全局等待者链表，然后进入睡眠。
      c. klist_release 在摘除节点后，会锁定并遍历这个全局等待者链表。
      d. 它找到所有正在等待当前被释放节点 n 的 waiter，将它们从等待者链表中移除，并调用 wake_up_process 来唤醒对应的睡眠任务。
    • 内存屏障 (mb()): 在设置 waiter->woken = 1 和 wake_up_process 之间有一个内存屏障。这是为了确保被唤醒的任务在检查 woken 标志时，一定能看到最新的值（1），防止了因指令重排或 CPU 缓存导致的伪唤醒（spurious wakeup）问题。

代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * @brief klist_release - klist_node 的最终释放函数 (析构函数)。
 * @param kref: 指向 klist_node 内 n_ref 成员的指针。
 * @note 此函数由 kref_put 在引用计数降为0时自动调用。
 */
static void klist_release(struct kref *kref)
{
	struct klist_waiter *waiter, *tmp;
	// 从 kref 指针反向推导出其所属的 klist_node 结构。
	struct klist_node *n = container_of(kref, struct klist_node, n_ref);

	// 这是一个健全性检查：确保只有在节点已被标记为“死亡”时才调用此函数。
	WARN_ON(!knode_dead(n));
	// 将节点从其 list_head 双向链表中物理地移除。
	list_del(&n->n_node);
	// 获取全局锁，以保护对全局等待者链表的访问。
	spin_lock(&klist_remove_lock);
	// 安全地遍历全局等待者链表。
	list_for_each_entry_safe(waiter, tmp, &klist_remove_waiters, list) {
		// 如果这个 waiter 等待的不是当前节点，则跳过。
		if (waiter->node != n)
			continue;

		// 如果是，则将此 waiter 从等待者链表中移除。
		list_del(&waiter->list);
		// 设置一个标志，告知被唤醒的进程它确实是被正常唤醒的。
		waiter->woken = 1;
		// 内存屏障，确保 woken=1 的写入对其他CPU/任务可见，先于 wake_up_process。
		mb();
		// 唤醒正在等待此节点被移除的进程。
		wake_up_process(waiter->process);
	}
	// 释放全局锁。
	spin_unlock(&klist_remove_lock);
	// 清理节点对 klist 的反向指针。
	knode_set_klist(n, NULL);
}

/**
 * @brief klist_dec_and_del - 减少一个 klist_node 的引用计数。
 * @param n: 指向 klist_node 的指针。
 * @return int: 如果此次操作导致节点被释放，则返回1，否则返回0。
 */
static int klist_dec_and_del(struct klist_node *n)
{
	// 调用 kref 框架的核心函数。
	// 它会原子地将 n->n_ref 减一，如果结果为0，则调用 klist_release。
	return kref_put(&n->n_ref, klist_release);
}

klist 节点删除与同步等待：klist_del, klist_remove 与 klist_put

本代码片段展示了 Linux 内核 klist（引用计数链表）中用于安全移除节点的两个核心接口：klist_del（异步删除）和 klist_remove（同步删除）。其核心功能是：提供一套机制来逻辑上标记一个节点为“待删除”，减少其引用计数，并在必要时让调用任务睡眠，直到该节点的最后一个引用被释放，节点被彻底从内存中清理后才返回。klist_put 是实现这一逻辑的底层工作函数。

实现原理分析

此机制是内核中一个经典的、用于解决“同步删除一个被多方引用的对象”问题的范例。它通过组合逻辑标记、引用计数和睡眠/唤醒机制来实现。

  1. 底层工作函数 (klist_put):

    • klist_put 是删除操作的核心。它接受一个 kill 标志，用于区分两种场景。
    • 锁定: spin_lock(&k->k_lock) 获取 klist 自身的锁，保护对链表和节点状态的修改。
    • 逻辑删除 (knode_kill): 如果 kill 标志为 true，它会调用 knode_kill(n)。这个函数并不从链表中移除节点，而是在节点内部设置一个“死亡”标志位。这使得其他遍历者（如 klist_next）可以识别并跳过这个“僵尸”节点。这是一个关键的解耦步骤，它将“意图删除”与“物理删除”分离开。
    • 引用递减: 调用 klist_dec_and_del(n) 来减少引用计数。如果这次递减导致引用计数降为 0，klist_release 将会被触发，节点会被物理摘除并最终释放。
    • 延迟调用 put: 与 klist_next 类似，它只有在释放锁之后才会调用节点的 put 函数（如果需要），以避免在锁内执行可能睡眠的操作。

  2. 异步删除 (klist_del):

    • klist_del 是一个非常简单的封装器。它调用 klist_put(n, true)。
    • 行为: 它会标记节点为“死亡”，减少其引用计数，然后立即返回。它不等待节点被真正释放。如果此时还有其他任务持有该节点的引用，该节点将暂时作为一个“僵尸”节点保留在链表中，直到最后一个引用被释放。这是一种高效的“即发即忘”（fire-and-forget）式删除。

  3. 同步删除 (klist_remove):

    • klist_remove 实现了阻塞式的、同步的删除。这是在需要确保一个对象在代码继续执行前被完全清理的场景下（例如卸载模块时）所必需的。
    • 注册等待者:
      a. 它在栈上创建一个 klist_waiter 结构，填入目标节点 n 和当前任务的 task_struct 指针 (current)。
      b. 然后，它锁定全局的 klist_remove_lock，将这个 waiter 添加到全局等待者链表 klist_remove_waiters 中。
    • 触发删除: 注册完等待者后，它调用 klist_del(n) 来启动异步删除流程。
    • 睡眠与等待:
      a. 它进入一个 for (;;) 循环。
      b. set_current_state(TASK_UNINTERRUPTIBLE) 将当前任务标记为不可中断的睡眠状态。
      c. if (waiter.woken) 检查一个标志位。这个标志位将由 klist_release 函数在节点被真正释放时设置。
      d. schedule() 主动放弃 CPU，让调度器运行其他任务。
    • 唤醒: 当 n 的最后一个引用被释放时，klist_release 会被调用。它会遍历 klist_remove_waiters 链表，找到对应的 waiter，设置其 woken 标志，并调用 wake_up_process 唤醒这个正在睡眠的任务。
    • 循环退出: 被唤醒后，任务从 schedule() 返回，再次进入循环。此时，waiter.woken 为 true，循环 break，函数结束。

代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * @brief klist_put - klist 节点的底层引用递减和可选的“杀死”操作。
 * @param n:    要操作的 klist_node。
 * @param kill: 如果为 true，则在递减引用前将节点标记为“死亡”。
 */
static void klist_put(struct klist_node *n, bool kill)
{
	struct klist *k = knode_klist(n); /// < 获取节点所属的 klist。
	void (*put)(struct klist_node *) = k->put; /// < 获取 klist 的自定义释放函数。

	// 获取 klist 的自旋锁，保护链表和节点状态。
	spin_lock(&k->k_lock);
	if (kill)
		// 如果需要，则将节点在逻辑上标记为“死亡”。
		knode_kill(n);
	// 减少节点的引用计数。如果计数降为0，klist_release 会被调用。
	// 如果计数未降为0，则不需要调用 put 函数，将其设为 NULL。
	if (!klist_dec_and_del(n))
		put = NULL;
	spin_unlock(&k->k_lock);
	// 在锁之外，如果需要，则调用自定义释放函数。
	if (put)
		put(n);
}

/**
 * @brief klist_del - 异步删除一个 klist 节点。
 * @param n: 要删除的节点。
 * @note 此函数会标记节点为“死亡”，减少其引用计数，然后立即返回。
 *       它不等待节点被真正释放。
 */
void klist_del(struct klist_node *n)
{
	// 调用底层函数，并设置 kill 标志为 true。
	klist_put(n, true);
}
EXPORT_SYMBOL_GPL(klist_del);

/**
 * @brief klist_remove - 同步删除一个 klist 节点。
 * @param n: 要移除的节点。
 * @note 此函数会启动删除过程，然后睡眠等待，直到节点被完全释放后才返回。
 */
void klist_remove(struct klist_node *n)
{
	struct klist_waiter waiter; /// < 在栈上创建一个等待者结构。

	// 初始化等待者：记录目标节点和当前进程。
	waiter.node = n;
	waiter.process = current;
	waiter.woken = 0; // 初始化唤醒标志为0。
	// 获取全局锁，保护全局等待者链表。
	spin_lock(&klist_remove_lock);
	// 将自己添加到等待者链表中。
	list_add(&waiter.list, &klist_remove_waiters);
	spin_unlock(&klist_remove_lock);

	// 触发节点的异步删除流程。
	klist_del(n);

	// 进入睡眠-等待循环。
	for (;;) {
		// 将当前任务状态设置为不可中断睡眠。
		set_current_state(TASK_UNINTERRUPTIBLE);
		// 检查是否已被 klist_release 唤醒。
		if (waiter.woken)
			break;
		// 主动放弃 CPU，进入睡眠。
		schedule();
	}
	// 被唤醒后，将任务状态恢复为运行状态。
	__set_current_state(TASK_RUNNING);
}
EXPORT_SYMBOL_GPL(klist_remove);