Linux RCU机制

Linux内核中的RCU（Read-Copy-Update） 是一种至关重要的同步机制，专为读多写少的场景设计，目标是实现极高性能的并发读取操作。它的核心思想是：读取操作完全无锁，写入操作通过复制和延迟回收来避免阻塞读取者。

核心原理

  1. 无锁读取：

    • 读者（读取数据的线程）在访问共享数据时不需要获取任何锁。
    • 读者只需要在访问数据前后标记进入/退出“读侧临界区”（通常通过 rcu_read_lock()/rcu_read_unlock() 或特定的 RCU 遍历原语如 list_for_each_entry_rcu() 完成）。
    • 读者在临界区内访问的数据指针保证是有效的（不会因写入者操作而立即释放）。

  2. 写入操作（更新）：

    • 当写入者（更新数据的线程）需要修改共享数据时，它遵循“读-复制-更新”流程：
      • 读： 读取当前数据（如果需要基于旧数据修改）。
      • 复制： 创建要修改数据的一个新副本。
      • 修改： 在这个新副本上进行所需的更改。
      • 更新： 使用一个原子操作（如指针赋值或 rcu_assign_pointer()）将指向数据的指针（例如链表节点指针、全局结构指针）切换到指向新副本。这个原子操作是“发布”新版本数据的关键点。
    • 在更新指针之后，旧版本的数据并没有被立即销毁或回收。

  3. 延迟回收：

    • 旧数据不能立即释放，因为可能还有旧的读取者（在指针切换前进入读临界区的读者）正在访问它。
    • RCU 机制会等待一个宽限期。
    • 宽限期的定义是：所有在指针切换前开始的读临界区都已经结束。这意味着系统中不再有任何读者可能持有指向旧数据的引用。
    • 一旦宽限期结束，内核就可以安全地回收（释放）旧数据的内存。这个回收动作通常通过调用 call_rcu() 或 synchronize_rcu() 来触发或等待。
      • call_rcu(callback_func)：异步方式。注册一个回调函数，内核会在宽限期结束后自动调用该回调函数来释放旧数据。写入者无需等待。
      • synchronize_rcu()：同步方式。写入者阻塞等待，直到当前宽限期结束（意味着所有旧读者都已完成），然后写入者自己释放旧数据。

关键概念

  • 宽限期： RCU 的核心概念。指从更新指针开始，到所有可能访问旧数据的读者都退出了他们的读临界区为止的时间段。内核通过跟踪 CPU 的“静止状态”（Quiescent State，QS）—— 例如进程切换、空闲循环、用户态执行 —— 来检测宽限期是否结束。
  • 读侧临界区： 读者通过 rcu_read_lock() 和 rcu_read_unlock() 界定的一段代码区域。在该区域内，读者访问的 RCU 保护的数据不会被释放。
  • 发布-订阅语义：
    • rcu_assign_pointer(p, v)：发布新数据。确保新数据 v 的初始化对看到新指针 p 的读者是可见的（内存屏障）。
    • rcu_dereference(p)：订阅数据。确保读者获取到指针 p 指向的最新有效数据（内存屏障），并在临界区内安全地解引用它。

为什么 RCU 高效？

  1. 读操作零开销： 没有锁争用，没有缓存行失效（在无写操作时），读取速度极快。
  2. 写操作不阻塞读： 写入者创建副本和更新指针的操作非常快（通常是原子指针赋值）。读者永远不会被写入者阻塞，它们要么看到旧数据，要么看到新数据（取决于指针切换的时刻），但看到的总是有效数据。
  3. 写操作开销可预测： 复制和内存分配的开销相对固定（取决于数据结构大小）。等待宽限期结束的开销取决于系统负载（读者退出临界区的速度），但写入者通常可以使用 call_rcu() 来避免阻塞。

与其他同步机制对比

特性 自旋锁 (Spinlock) 读写信号量 (rw_semaphore) RCU
读开销 高 (锁争用) 中等 (可能阻塞在写者后) 极低 (无锁)
写开销 高 (锁争用) 高 (阻塞所有读写者) 中等 (复制+宽限期)
读阻塞写? 是 是 否
写阻塞读? 是 是 否
内存开销 低 低 较高 (旧数据副本)
适用场景 临界区小, 争用低 读多写少, 临界区长 读极多, 写极少

典型应用场景

  1. 内核数据结构遍历： 遍历链表、哈希表等（如 vfsmount 列表、dentry 缓存、网络路由表）。读遍历非常频繁。
  2. 路由表更新： 网络栈中路由信息的更新相对较少，但查询极其频繁。
  3. 状态统计： 需要频繁读取但偶尔更新的统计计数器。
  4. 模块卸载： 确保在卸载模块前，所有使用该模块导出函数的调用都已返回。
  5. 文件描述符表： 快速查找文件描述符对应的 file 结构。
  6. 虚拟文件系统 (VFS)： 管理 dentry 和 inode 缓存。

使用注意事项

  1. 写少读多： RCU 的优势在写入极其稀少时最大。频繁写入会导致大量内存复制和宽限期等待，开销可能超过传统锁。
  2. 内存开销： 写入时需要复制数据，旧数据需要延迟释放，增加了内存占用压力。
  3. 写延迟： 虽然 call_rcu() 让写入者不阻塞，但实际内存回收可能延迟发生。synchronize_rcu() 会阻塞写入者直到宽限期结束。
  4. 读者约束：
    • 读临界区不能阻塞/睡眠。因为宽限期需要等待读者退出，睡眠的读者会无限期延迟宽限期，导致内存泄漏甚至系统挂起。
    • 读临界区内访问的数据结构应该是稳定的（写入者只修改副本，不修改读者当前看到的数据）。
  5. 正确使用原语： 必须严格使用 rcu_read_lock()/unlock(), rcu_assign_pointer(), rcu_dereference(), call_rcu()/synchronize_rcu() 等 API，并理解其内存屏障语义。

总结

Linux RCU 是一种革命性的同步机制，通过无锁读取和延迟回收旧数据副本，在“读多写少”的场景下提供了卓越的性能和可扩展性。理解其核心原理（无锁读、复制更新、宽限期、延迟回收）以及适用场景和约束条件，对于开发高性能内核代码至关重要。它是现代 Linux 内核高性能并发的基础设施之一。

给一个示例

下面是一个使用Linux内核RCU机制的示例代码，展示如何安全地读写共享链表。这个例子演示了读者无锁访问，而写者通过复制更新来修改链表：

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
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/rcupdate.h>
#include <linux/slab.h>

// 链表节点结构
struct my_data {
    int value;
    struct list_head list;
    struct rcu_head rcu;  // RCU回调头
};

// 全局链表头
static LIST_HEAD(global_list);

// 读者线程：无锁遍历链表
static void reader_thread(void)
{
    struct my_data *node;

    rcu_read_lock();  // 进入RCU读端临界区
    
    // 安全遍历RCU保护的链表
    list_for_each_entry_rcu(node, &global_list, list) {
        // 读者可以安全访问节点
        printk("Reader: value = %d\n", node->value);
    }
    
    rcu_read_unlock();  // 退出RCU读端临界区
}

// 节点释放回调（宽限期结束后调用）
static void my_data_free(struct rcu_head *rcu)
{
    struct my_data *node = container_of(rcu, struct my_data, rcu);
    kfree(node);
    printk("Reclaimed node %d\n", node->value);
}

// 写者线程：添加新节点
static void writer_thread(int new_value)
{
    struct my_data *new_node, *old_head;

    // 1. 分配并初始化新节点
    new_node = kmalloc(sizeof(*new_node), GFP_KERNEL);
    new_node->value = new_value;
    INIT_LIST_HEAD(&new_node->list);

    // 2. 复制并更新
    spin_lock(&list_lock);  // 需要锁保护写操作
    
    // 获取当前链表头（旧值）
    old_head = list_first_entry_or_null(&global_list, 
                                       struct my_data, list);
    
    // 将新节点插入链表头部
    list_add_rcu(&new_node->list, &global_list);
    
    spin_unlock(&list_lock);

    // 3. 延迟回收旧节点（如果替换了头节点）
    if (old_head) {
        // 从链表中移除旧头节点
        list_del_rcu(&old_head->list);
        // 异步释放旧节点（宽限期结束后）
        call_rcu(&old_head->rcu, my_data_free);
    }
}

// 示例使用
static void example_usage(void)
{
    // 初始添加节点
    writer_thread(10);
    writer_thread(20);

    // 并发访问
    reader_thread();  // 可能看到10,20或20,10

    // 更新头节点为30
    writer_thread(30);

    // 再次读取（可能看到30,20或30,10）
    reader_thread();
}

关键点解析：

  1. **读者端 (reader_thread)**：

    • 使用rcu_read_lock()/rcu_read_unlock()界定临界区
    • list_for_each_entry_rcu()安全遍历链表
    • 零锁开销：多个读者可并发执行

  2. **写者端 (writer_thread)**：

    • 复制：创建新节点（不修改现有数据）
    • 更新：
      • 用自旋锁保护写操作（防止多个写者冲突）
      • 使用list_add_rcu()原子更新指针
    • 延迟回收：
      • list_del_rcu()移除旧节点
      • call_rcu()注册回收回调

  3. **内存回收 (my_data_free)**：

    • 通过rcu_head嵌入回调
    • 在宽限期（所有读者退出临界区）后自动触发
    • 安全释放旧节点内存

  4. 同步机制：

    • 读者/写者并行：新数据立即对后续读者可见
    • 旧数据保持有效直到所有当前读者完成
    • 写者不会阻塞读者执行

典型输出时序：

1
2
3
4
5
6
Reader: value = 20
Reader: value = 10
Writer: Added 30
Reclaimed node 20  # 延迟回收
Reader: value = 30
Reader: value = 10

重要注意事项：

  1. 读者约束：

    • 临界区内不能阻塞/睡眠
    • 访问的数据必须通过RCU原语获取

  2. 写者开销：

    • 复制成本与数据大小成正比
    • 宽限期时长取决于系统负载

  3. 内存序保证：

    • rcu_assign_pointer()确保更新可见性
    • rcu_dereference()保证读者获取有效指针

  4. 变体选择：

    • 用户态：liburcu
    • 内核密集读：SRCU（可睡眠RCU）
    • 实时系统：PREEMPT_RT

这个示例展示了RCU如何实现高性能并发：读者路径完全无锁，写者通过复制+延迟回收避免阻塞读者，特别适合路由表、内核对象列表等读密集型场景。