Linux 内核 RCU 链表实战：用 RCU 保护只读为主的链表的五大经典模式（基于 Documentation/RCU/listRCU.rst）

Linux 内核 RCU 链表实战用 RCU 保护只读为主的链表的五大经典模式基于 Documentation/RCU/listRCU.rst【免费下载链接】linuxLinux kernel source tree项目地址: https://gitcode.com/GitHub_Trending/li/linuxRCURead-Copy Update是 Linux 内核中保护读多写少数据结构的核心机制其中最常见、也最容易上手的用法就是保护双向链表struct list_head。本文基于内核仓库中的官方文档 Documentation/RCU/listRCU.rst系统讲解如何用 RCU 保护只读为主链表的完整方法论RCU 链表的并发保证模型、五大典型用例延迟销毁、锁外使用结果、就地更新、拒绝过期数据、跳过陈旧对象并结合 include/linux/rculist.h、fs/timerfd.c、kernel/exit.c、kernel/sched/signal.h 等真实源码逐一印证。读完本文你将能够判断自己的链表场景该套用哪一种 RCU 模式并掌握list_add_rcu()、list_del_rcu()、list_replace_rcu()、list_for_each_entry_rcu()等原语的正确用法与底层内存屏障语义。一、RCU 链表的并发保证模型读者到底能看到什么RCU 链表的第一大优势是所有需要的内存序memory ordering都由链表宏本身提供使用者不需要手动安排额外的内存屏障。这是 include/linux/rculist.h 中各个_rcu原语通过rcu_assign_pointer()、rcu_dereference()、READ_ONCE()实现的。在持有rcu_read_lock()遍历链表期间写者可以随意修改链表。此时读者获得如下保证引自原文档核心定义一定看得到读者在进入rcu_read_lock()之前就已加入链表、且在读者释放rcu_read_unlock()时仍在链表中的元素可能看也可能看不到读者持锁期间新加入或被删除的元素——看到与否均合法原子替换的确定性如果写者调用了list_replace_rcu()读者要么看到旧元素、要么看到新元素绝不会同时看到两者也绝不会两者都看不到。从源码结构看第 3 条保证由 include/linux/rculist.h 中的list_replace_rcu()实现先写new-next/new-prev再用rcu_assign_pointer(list_next_rcu(new-prev), new)一次性原子地让前驱节点的next指向新节点最后把旧节点的prev打成LIST_POISON2。读者侧的list_for_each_entry_rcu()通过rcu_dereference()见list_for_each_rcu()include/linux/rculist.h读取next指针从而保证读到新指针时一定能看到新节点的完整内容。二、模式一只读为主链表与延迟销毁——进程链表 for_each_process()内核中最广泛使用的 RCU 链表用例之一是无锁遍历全系统进程表。task_struct::tasks是所有进程串成的链表节点遍历可以与任意增删并发进行。2.1 遍历侧两个宏include/linux/sched/signal.h 中与文档一致的真实定义#define next_task(p) \ list_entry_rcu((p)-tasks.next, struct task_struct, tasks) #define for_each_process(p) \ for (p init_task ; (p next_task(p)) ! init_task ; )典型读侧代码就是文档给出的三段式rcu_read_lock(); for_each_process(p) { /* Do something with p */ } rcu_read_unlock();注意next_task()使用list_entry_rcu()而非list_entry()——前者通过READ_ONCE()读取next指针见 include/linux/rculist.h防止编译器对-next做重复读取/优化这是并发读正确性的前提。2.2 写侧list_del_rcu() call_rcu() 延迟释放文档中简化后的删除流程void release_task(struct task_struct *p) { write_lock(tasklist_lock); list_del_rcu(p-tasks); write_unlock(tasklist_lock); call_rcu(p-rcu, delayed_put_task_struct); }当前内核中的真实实现与之对应release_task()kernel/exit.c经由__exit_signal()与__unhash_process()在tasklist_lock写锁保护下执行list_del_rcu(p-tasks)kernel/exit.c。这里的关键设计是延迟销毁tasklist_lock只用于排除写者之间的并发增删防止链表结构被破坏读者不持有该锁task_struct对象不会立即释放而是通过call_rcu()注册delayed_put_task_struct回调等待一个或多个 RCU 宽限期grace period结束后才真正释放因此任何正在遍历的读者看到的p-tasks.next指针永远指向有效内存删除/释放与遍历完全并行。这种模式被称为existence lock存在锁RCU 保证在所有可能引用该对象的读者都退出读临界区之前不会执行回收回调从而保证对象在其存在窗口内始终有效。删除原语list_del_rcu()的实现include/linux/rculist.h只把entry-prev打成LIST_POISON2刻意不投毒前向next指针——因为并发的 RCU 读者可能正在顺着next链走注释中同时明确要求删除后不能立即释放条目必须用call_rcu()/synchronize_rcu()延迟到宽限期之后。三、模式二读侧在锁外使用结果——把读写锁换成 RCUaudit 规则表有些场景是持读锁期间算出一个值但释放锁之后才真正使用这个值。这类场景非常适合改造成 RCU既然值的消费发生在锁外那么即使列表在消费前发生变化也无所谓——典型例子是网络路由路由数据追踪的是机器外部设备的状态外部网络本身就在变化锁住路由表也锁不住 Internet。文档以系统调用审计audit模块为例。读-写锁版本的audit_filter_task()在read_lock(auditsc_lock)下搜索audit_tsklist命中后kstrdup()复制 filterkey、释放锁再返回RCU 版本几乎逐行对应只是三处替换static enum audit_state audit_filter_task(struct task_struct *tsk, char **key) { struct audit_entry *e; enum audit_state state; rcu_read_lock(); /* Note: audit_filter_mutex held by caller. */ list_for_each_entry_rcu(e, audit_tsklist, list) { if (audit_filter_rules(tsk, e-rule, NULL, state)) { if (state AUDIT_STATE_RECORD) *key kstrdup(e-rule.filterkey, GFP_ATOMIC); rcu_read_unlock(); return state; } } rcu_read_unlock(); return AUDIT_BUILD_CONTEXT; }对比要点read_lock()/read_unlock()变为rcu_read_lock()/rcu_read_unlock()list_for_each_entry()变为list_for_each_entry_rcu()。带_rcu的遍历原语加入了READ_ONCE()和是否在 RCU 读临界区内的诊断检查——当开启CONFIG_PROVE_RCU_LIST时include/linux/rculist.h 中的__list_check_rcu()会用 lockdep 对在非读者区遍历 RCU 链表发出RCU-list traversed in non-reader section!告警。更新侧的改造同样直接。写侧原为write_lock(auditsc_lock)下的删除/插入/* 删除RCU 版 */ static inline int audit_del_rule(struct audit_rule *rule, struct list_head *list) { struct audit_entry *e; /* No need to use the _rcu iterator here, since this is the only * deletion routine. */ list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, e-rule)) { list_del_rcu(e-list); call_rcu(e-rcu, audit_free_rule); return 0; } } return -EFAULT; /* No matching rule */ } /* 插入RCU 版 */ static inline int audit_add_rule(struct audit_entry *entry, struct list_head *list) { if (entry-rule.flags AUDIT_PREPEND) { entry-rule.flags ~AUDIT_PREPEND; list_add_rcu(entry-list, list); } else { list_add_tail_rcu(entry-list, list); } return 0; }由于本例所有调用者都持有audit_filter_mutex写者之间已被串行化auditsc_lock这把读写锁可以整个删掉——因为 RCU 本身消灭了写者必须排斥读者的需求写者只需排斥写者这里由 mutex 承担。_rcu版链表操作原语与普通信道的差异对照 include/linux/rculist.h 源码list_add_rcu()/list_add_tail_rcu()通过rcu_assign_pointer()更新相邻节点指向新节点的指针在弱内存序 CPU 上提供必需的写屏障保证读者看到指针时必然看到新节点已初始化好的字段list_del_rcu()省略了普通list_del()的指针投毒调试代码保留投毒会让并发读者立刻触发明显的错误保证读者沿next链前进时不踩到被投毒的指针语义上写者用锁或别的串行化手段互相排斥但与list_for_each_entry_rcu()这类_rcu遍历原语并发运行是合法的——这正是文档反复强调的不变量。小结当读者能容忍陈旧数据、且条目只增删不做就地修改时套用 RCU 非常容易。四、模式三就地更新——Read-Copy-Update 名字的由来audit 模块恰好不就地更新规则。但如果必须就地修改读-写锁版会直接在write_lock下改字段static inline int audit_upd_rule(struct audit_rule *rule, struct list_head *list, __u32 newaction, __u32 newfield_count) { struct audit_entry *e; write_lock(auditsc_lock); /* Note: audit_filter_mutex held by caller. */ list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, e-rule)) { e-rule.action newaction; e-rule.field_count newfield_count; write_unlock(auditsc_lock); return 0; } } write_unlock(auditsc_lock); return -EFAULT; /* No matching rule */ }RCU 版的处理策略是三步复制 → 更新副本 → 原子替换然后旧副本延迟释放static inline int audit_upd_rule(struct audit_rule *rule, struct list_head *list, __u32 newaction, __u32 newfield_count) { struct audit_entry *e; struct audit_entry *ne; list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, e-rule)) { ne kmalloc_obj(*entry, GFP_ATOMIC); if (ne NULL) return -ENOMEM; audit_copy_rule(ne-rule, e-rule); ne-rule.action newaction; ne-rule.field_count newfield_count; list_replace_rcu(e-list, ne-list); call_rcu(e-rcu, audit_free_rule); return 0; } } return -EFAULT; /* No matching rule */ }允许并发读的同时通过复制来完成更新正是RCUread-copy update名称的由来。旧条目经list_replace_rcu()摘链后不会立即失效——宽限期内仍可能有读者持有它的引用因此必须call_rcu()延迟回收。读者侧则天然获得一致性要么完整看到旧规则要么完整看到新规则第一节保证模型的list_replace_rcu()原子替换语义。内核中还有两个可参考的真实实现文档提到update_lsm_rule()采用了非常相似的做法另一个是用 RCU 管理哈希链表的 openswitch 驱动连接跟踪表——ct_limit_set()分配新的 per-zone limit 对象用list_replace_rcu()替换旧对象旧对象随后用kfree_rcu()在宽限期后释放。五、模式四拒绝过期数据——deleted 标志 每条目自旋锁跟踪外部状态的算法大多能容忍陈旧数据外部状态变化后本就有感知延迟RCU 引入的额外陈旧量无关痛痒。但有些场景绝不能容忍文档给出的内核实例是 System V IPC 的shm_lock()见 ipc/shm.c——它在每条目自旋锁下检查deleted标志若已标记删除就当作条目不存在并且搜索函数必须持有该自旋锁返回否则标志检查毫无意义。快速小测为了让 deleted 标志技术真正有效为什么搜索函数必须在返回时仍持有每条目锁答案如果搜索函数返回前就放下每条目锁调用方无论如何都会在处理陈旧数据——既然陈旧数据可以接受你根本不需要 deleted 标志如果陈旧数据真的不能接受你就必须在使用返回值的全部代码期间一直持有该条目锁。如果 audit 模块某天必须拒绝陈旧数据可给audit_entry增加deleted标志和lock自旋锁读侧改为static struct audit_entry *audit_filter_task(struct task_struct *tsk, char **key) { struct audit_entry *e; enum audit_state state; rcu_read_lock(); list_for_each_entry_rcu(e, audit_tsklist, list) { if (audit_filter_rules(tsk, e-rule, NULL, state)) { spin_lock(e-lock); if (e-deleted) { spin_unlock(e-lock); rcu_read_unlock(); return NULL; } rcu_read_unlock(); if (state AUDIT_STATE_RECORD) *key kstrdup(e-rule.filterkey, GFP_ATOMIC); /* As long as e-lock is held, e is valid and * its value is not stale */ return e; } } rcu_read_unlock(); return NULL; }配套的删除函数必须在自旋锁内设置标志static inline int audit_del_rule(struct audit_rule *rule, struct list_head *list) { struct audit_entry *e; /* No need to use the _rcu iterator here, since this * is the only deletion routine. */ list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, e-rule)) { spin_lock(e-lock); list_del_rcu(e-list); e-deleted 1; spin_unlock(e-lock); call_rcu(e-rcu, audit_free_rule); return 0; } } return -EFAULT; /* No matching rule */ }两个注意点其一读侧在自旋锁内检查deleted后立即解锁返回条目指针——调用方要真正获得非陈旧保证必须在使用返回值期间自己持有e-lock其二该模式假设条目只增删。若同时存在audit_upd_rule()这种就地更新还需要额外机制例如list_replace_rcu()执行期间必须同时持有新旧两个audit_entry的锁。六、模式五跳过陈旧对象——timerfd 的 cancel_list有些场景可以更进一步在读侧遍历时主动跳过那些即将被移除销毁的陈旧对象提升读路径性能。内核 timerfd 子系统是标准范例当CLOCK_REALTIME时钟被重新编程例如设置系统时间时所有依赖该时钟且带TFD_TIMER_CANCEL_ON_SET的 timerfd 会被提前触发、等待进程被唤醒。建表侧timerfd_setup_cancel()在满足条件CLOCK_REALTIME/CLOCK_REALTIME_ALARM ABSTIME CANCEL_ON_SET且might_cancel尚未置位时把上下文加入 RCU 管理的cancel_list。当前内核的真实实现fs/timerfd.c与文档示例一致static void timerfd_setup_cancel(struct timerfd_ctx *ctx, int flags) { spin_lock(ctx-cancel_lock); if ((ctx-clockid CLOCK_REALTIME || ctx-clockid CLOCK_REALTIME_ALARM) (flags TFD_TIMER_ABSTIME) (flags TFD_TIMER_CANCEL_ON_SET)) { if (!ctx-might_cancel) { ctx-might_cancel true; spin_lock(cancel_lock); list_add_rcu(ctx-clist, cancel_list); spin_unlock(cancel_lock); } } else { __timerfd_remove_cancel(ctx); } spin_unlock(ctx-cancel_lock); }销毁侧fd 关闭时timerfd_release()先清might_cancel、在cancel_lock下list_del_rcu()摘链最后kfree_rcu(ctx, rcu)延迟释放。摘链逻辑现由__timerfd_remove_cancel()承担fs/timerfd.cstatic void __timerfd_remove_cancel(struct timerfd_ctx *ctx) { if (ctx-might_cancel) { ctx-might_cancel false; spin_lock(cancel_lock); list_del_rcu(ctx-clist); spin_unlock(cancel_lock); } }遍历侧时钟被设置时 hrtimer 框架回调timerfd_clock_was_set()在 RCU 读侧遍历cancel_list并唤醒等待进程。真实实现fs/timerfd.c中查might_cancel跳过陈旧对象是文档强调的关键一行void timerfd_clock_was_set(void) { ktime_t moffs ktime_mono_to_real(0); struct timerfd_ctx *ctx; unsigned long flags; rcu_read_lock(); list_for_each_entry_rcu(ctx, cancel_list, clist) { if (!ctx-might_cancel) continue; spin_lock_irqsave(ctx-wqh.lock, flags); if (ctx-moffs ! moffs) { ctx-moffs KTIME_MAX; ctx-ticks; wake_up_locked_poll(ctx-wqh, EPOLLIN); } spin_unlock_irqrestore(ctx-wqh.lock, flags); } rcu_read_unlock(); }为什么必须跳过RCU 保护的遍历与对象的增删并发进行遍历过程中可能看到一个已被list_del_rcu()摘链、尚在宽限期内的对象。might_cancel标志充当该对象是否还活跃的软判断——已摘链对象会被continue跳过而对象内存本身由kfree_rcu()保证在读侧仍然有效。七、五种模式总结与选型决策综合文档的 Summary 与以上源码印证RCU 链表模式的选型可以归纳为场景特征推荐模式核心 API内核实例只增删读者容忍陈旧数据延迟销毁list_add_rcu()/list_del_rcu()call_rcu()进程表 kernel/exit.c读者在锁外消费结果读侧换 RCUlist_for_each_entry_rcu()rcu_read_lock()audit 规则表文档示例需要修改已有条目复制-更新-替换read-copy-updatelist_replace_rcu()call_rcu()update_lsm_rule()、openswitchct_limit_set()绝对不容忍陈旧数据deleted 标志 每条目自旋锁spin_lock 标志位持锁返回ipc/shm.c 的shm_lock()遍历中想省掉已死对象跳过陈旧对象活跃标志 list_for_each_entry_rcu()fs/timerfd.c 的cancel_list三条总原则能容忍陈旧数据的只读为主链表最适合 RCU改造成本最低非原子的就地修改可以复制-更新-替换化解代价是一次内存分配与一次宽限期延迟回收不能容忍陈旧数据时用 deleted 标志 每条目自旋锁让搜索函数能够拒绝刚刚被删除的数据且调用方使用返回值期间必须保持条目锁。此外若你的链表是单向哈希链表hlist同一套思想对应hlist_add_head_rcu()、hlist_del_rcu()、hlist_replace_rcu()、hlist_for_each_entry_rcu()等原语均在 include/linux/rculist.h 中定义语义与本文双向链表部分完全平行需要理解 RCU 机制本身时可继续阅读同目录下的 Documentation/RCU/whatisRCU.rst需要 nulls-RCU 变体时可看 Documentation/RCU/rculist_nulls.rst。【免费下载链接】linuxLinux kernel source tree项目地址: https://gitcode.com/GitHub_Trending/li/linux创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考