3. RCU 数据结构基础：链表、哈希表与指针替换技术

RCU（Read-Copy-Update）的核心优势在于，它允许读者在写者进行更新的同时，无需任何锁或原子操作即可安全地访问被保护的数据结构。这种能力依赖于特定的数据结构布局和一种称为“指针替换”（Pointer Swizzling）的技术。本章将深入剖析 RCU 最常用的两种数据结构——链表和哈希表，并详细解释指针替换如何实现无锁读取。

3.1 RCU 保护的单向链表

单向链表是 RCU 最经典、最基础的数据结构。其核心思想是：读者通过一个全局指针（通常称为根指针或头指针）遍历链表；写者通过原子地替换指针来插入或删除节点，并在所有读者完成旧路径的访问后，再安全地回收旧节点内存。

3.1.1 链表节点结构

一个典型的 RCU 链表节点包含数据和指向下一个节点的指针。关键在于，这个指针必须支持原子读写。

struct rcu_node {
    int data;
    struct rcu_node *next;  // 被 RCU 保护的指针
};

3.1.2 无锁遍历（读者路径）

读者在遍历 RCU 链表时，必须使用 rcu_dereference() 宏来安全地读取被保护的指针。这个宏在大多数架构上会被编译为普通的读取指令，但在某些弱一致性模型（如 Alpha）上会插入内存屏障，防止编译器或 CPU 重排序导致读到过时的值。

struct rcu_node *head;
int search_rcu_list(int target) {
    struct rcu_node *p;
    rcu_read_lock();  // 进入 RCU 读端临界区
    p = rcu_dereference(head);
    while (p) {
        if (p->data == target) {
            int ret = p->data;
            rcu_read_unlock();
            return ret;
        }
        p = rcu_dereference(p->next);
    }
    rcu_read_unlock();
    return -1;
}

3.1.3 安全插入（写者路径）

写者插入新节点时，需要先初始化新节点，然后将新节点的 next 指针指向旧的头节点，最后使用 rcu_assign_pointer() 原子地将全局头指针 head 更新为新节点。这个宏确保所有先前的写操作（如初始化新节点）在指针发布之前对其他 CPU 可见。

void insert_rcu_list(int new_data) {
    struct rcu_node *new_node = kmalloc(sizeof(*new_node), GFP_KERNEL);
    new_node->data = new_data;
    new_node->next = rcu_dereference(head);  // 指向旧头
    rcu_assign_pointer(head, new_node);      // 原子发布新头
}
关键点： 在 rcu_assign_pointer() 执行之前，新节点对读者是不可见的。一旦执行，所有后续进入读端临界区的读者都会看到新节点。正在遍历旧链表的读者仍然安全地访问旧节点，因为旧节点的 next 指针没有被修改。

3.1.4 安全删除（写者路径）

删除操作更为复杂。写者需要先将目标节点从链表中“逻辑删除”，即让前驱节点的 next 指针跳过目标节点，指向其后继节点。然后，写者必须等待一个“宽限期”（Grace Period），确保所有在删除操作之前进入读端临界区的读者都已经退出，之后才能安全地释放被删除节点的内存。

void delete_rcu_list(struct rcu_node *target) {
    struct rcu_node **pp;
    rcu_read_lock();
    pp = &head;
    while (*pp != target) {
        pp = &((*pp)->next);
    }
    // 逻辑删除：让前驱的 next 指向 target 的后继
    rcu_assign_pointer(*pp, target->next);
    rcu_read_unlock();

    // 等待宽限期
    synchronize_rcu();

    // 安全释放内存
    kfree(target);
}
注意： 上述删除代码为了简洁省略了并发控制。在实际内核实现中，对链表指针的修改通常需要自旋锁或其他互斥机制来保护，以防止多个写者同时修改同一个指针。RCU 解决的是读者与写者之间的并发，而非写者与写者之间的并发。

3.2 RCU 保护的哈希表

哈希表可以看作是多个链表的集合。RCU 哈希表通常由一个固定大小的指针数组（桶）构成，每个桶指向一个 RCU 链表的头节点。读者通过哈希函数定位到桶，然后遍历该桶对应的链表。写者则对特定桶内的链表进行插入或删除操作。

3.2.1 哈希表结构

#define BUCKET_SIZE 256
struct rcu_bucket {
    struct rcu_node *head;
};
struct rcu_hash_table {
    struct rcu_bucket buckets[BUCKET_SIZE];
};

3.2.2 查找与插入

查找操作与链表类似，只是多了一步哈希计算。插入操作则是在定位到桶后，对该桶的头指针执行 rcu_assign_pointer()。

struct rcu_node *search_hash(struct rcu_hash_table *ht, int key) {
    int bucket_idx = hash_function(key);
    struct rcu_node *p;
    rcu_read_lock();
    p = rcu_dereference(ht->buckets[bucket_idx].head);
    while (p) {
        if (p->data == key) {
            rcu_read_unlock();
            return p;
        }
        p = rcu_dereference(p->next);
    }
    rcu_read_unlock();
    return NULL;
}

3.2.3 哈希表扩容（Resize）

RCU 哈希表的一个高级应用是动态扩容。当负载因子过高时，可以分配一个更大的新桶数组，然后将所有旧桶中的节点重新哈希并链接到新桶中。这个过程可以完全在后台进行，读者在扩容期间仍然可以访问旧表。当新表准备就绪后，通过一个原子指针替换操作，将全局哈希表指针从旧表切换到新表。之后，等待一个宽限期，再释放旧表的内存。

性能优势： 在 RCU 哈希表中，读操作完全不需要锁，也不涉及原子操作（除了指针读取本身），因此可以实现极高的读并发性能。这对于读多写少的场景（如路由表、DNS 缓存、文件系统路径查找）至关重要。

3.3 指针替换（Pointer Swizzling）技术

指针替换是 RCU 实现无锁读取的核心机制。它指的是通过原子地更新一个指针，来“瞬间”改变整个数据结构的视图，而无需原地修改数据结构内部的复杂状态。

3.3.1 工作原理

指针替换的本质是“发布-订阅”模式：

  1. 写者准备新版本： 写者创建一个新的数据结构副本（或新节点），并在其上完成所有修改。
  2. 原子发布： 写者使用 rcu_assign_pointer() 将全局的根指针从旧版本原子地切换到新版本。
  3. 读者无感切换： 在切换之后，新进入的读者会看到新版本。而正在访问旧版本的读者，由于持有指向旧版本的指针，仍然可以安全地完成其操作。
  4. 延迟回收： 写者等待一个宽限期，确保所有可能持有旧版本指针的读者都已经退出，然后才回收旧版本的内存。

3.3.2 与原地更新的对比

特性 指针替换（RCU 方式） 原地更新（传统锁方式）
读操作 无锁、无阻塞、无原子操作（除指针读取） 需要获取锁，可能被写者阻塞
写操作 需要分配新内存、复制数据、更新指针 直接在原数据上修改
内存开销 较高（需要维护新旧两个版本） 较低（只有一份数据）
一致性 读者看到的是某个时间点的完整快照 读者看到的是实时更新的数据
适用场景 读多写少，对读延迟敏感 写多读少，对内存敏感

3.3.3 指针替换的典型应用：RCU 链表头插入

下图展示了指针替换在链表头插入操作中的具体过程。

RCU 链表头插入：指针替换过程 步骤 1：初始状态 head Node A Node B NULL 步骤 2：写者创建新节点 New Node New Node Node A (新节点的 next 指向旧 head) 步骤 3：原子替换 head 指针 (rcu_assign_pointer) head New Node Node A Node B 读者视角 旧读者：仍通过旧指针访问 A→B 新读者：通过新 head 访问 New→A→B 两者互不干扰！

3.4 指针替换的硬件基础：原子指针操作

指针替换依赖于硬件提供的原子指针写入能力。在大多数现代 CPU 架构上，对一个对齐的指针（如 64 位系统上的 8 字节指针）的写入是天然的原子操作。这意味着，一个 CPU 核心在写入指针时，其他核心要么看到旧值，要么看到新值，而不会看到部分更新的、损坏的中间值。

rcu_assign_pointer() 宏正是利用了这一点，并在此基础上添加了必要的内存屏障（Memory Barrier），以确保在指针发布之前，所有对数据结构的修改（如初始化新节点）都已经全局可见。

总结： 指针替换是 RCU 的基石。它将“修改数据”和“发布数据”两个步骤解耦，使得读者可以在无锁的情况下，始终看到一个一致的数据视图。这种设计哲学是 RCU 能够实现卓越读性能的关键。
← 上一章 📖 返回目录 下一章 →