导图社区 RCU
- 118
- 1
- 0
- 举报
RCU
RCU，即英文Room Control Unit的简称，意为“客房控制器”，属中高档酒店宾馆以及智能建筑，智能家居行业的专用术语。其中酒店部署客房控制系统时使用的较多。RCU具备微处理功能，即集成MCU(Micro Control Unit)中文名称为微电脑控制单元，能通过无线控制所有的客房电器、灯具及插座等。这个思维导图整理了RCU锁核心思想和内核和DPDK用户态实现细节的精华内容。
编辑于2021-04-04 22:52:31- 内核
- RCU锁
- 无锁编程
- 相似推荐
- 大纲
RCU
核心原理
理论基础
QSBR算法 Quiescent State-Based Reclamation
https://blog.csdn.net/zhangyifei216/article/details/52767236
https://preshing.com/20160726/using-quiescent-states-to-reclaim-memory/
QSBR是通过quiescent state来检测grace period。如果线程T在某时刻不再持有共享对象的引用，那么该线程T在此时就处于quiescent state。如果一个时间区间内，所有线程都曾处于quiescent state，那么这个区间就是一个grace period。QSBR需要实现时明确手动指明在算法某一步处于quiescent state。 具体实现时，可以在时间轴上划分出interval，每个interval内，每一个线程至少有一次quiescent state。那么当前interval删除的对象的内存可以在下一个interval结束时释放掉。 需要注意的是，QSBR是个blocking的算法。如果某个线程卡死了，那么就等不到grace period了，最终导致内存都无法释放
有时间段[a,b]，如果在b之后，所有在a之前删除的元素都可以被释放，那么[a,b]被称为a grace period
在多线程场景下，经常我们需要并发访问一个数据结构，为了保证线程安全我们会考虑使用互斥设施来进行同步，更进一步我们会根据对这个数据结构的读写比例而选用读写锁进行优化。但是读写锁不是唯一的方式，我们可以借助于COW技术来做到写操作不需要加锁，也就是在读的时候正常读，写的时候，先加锁拷贝一份，然后进行写，写完就原子的更新回去，使用COW实现避免了频繁加读写锁本身的性能开销
论文地址：http://csng.cs.toronto.edu/publication_files/0000/0159/jpdc07.pdf
基本架构
三个重要概念
静止状态QS（Quiescent State）
CPU发生了上下文切换称为经历一个quiescent state
宽限期GP（Grace Period）
grace period就是所有CPU都经历一次quiescent state所需要的等待的时间
也即系统中所有的读者完成对共享临界区的访问
读侧临界部分RCS（Read-Side Critical Section)
保护禁止其他CPU修改的代码区域，但允许多个CPU同时读
三个主要的角色
读者reader
更新者updater
回收者reclaimer
三个重要机制
a publish-subscribe mechanism for adding new data
发布/订阅机制，主要用于更新数据，
RCU最重要的属性是：即使在数据被同时修改时线程也能安全浏览数据。RCU通过出版-预订机制（Publish-Subscribe Mechanism）实现这种并发的插入操作能力
， Wait For Pre-Existing RCU Readers to Complete，
1）重置每cpu变量，值为0。 2）当某个cpu经历一次上下文切换后，就将自己的变量设为1。 3）当所有的cpu变量都为1后，就可以唤醒写者了。
等待已经存在的RCU读者完成，用于删除老数据
Maintain Multiple Versions of Recently Updated Objects
维护最近更新对象的多个版本，用于允许读者容忍并发的插入和删除
论文
http://www.rdrop.com/users/paulmck/rclock/RCUdissertation.2004.07.14e1.pdf
发展历程
经典RCU
经典RCU状态
可抢占的RCU
2 可抢占的RCU 如果config文件定义了CONFIG_TREE_PREEMPT_RCU=y，那么sychronize_rcu将默认使用rcu_preempt_state。这类rcu的特点就在于read_lock期间是允许其它进程抢占的，因此它判断宽限期度过的方法就不太一样。 从rcu_read_lock和rcu_read_unlock的定义就可以知道，TREE_PREEMPT_RCU并不是以简单的经过抢占为CPU渡过GP的标准，而是有个rcu_read_lock_nesting计数
当抢占发生时，__schedule函数会调用rcu_note_context_switch来通知RCU更新状态，如果当前CPU处于rcu_read_lock状态，当前进程将会放入rnp->blkd_tasks阻塞队列，并呈现在rnp->gp_tasks链表中
上文1.3节宽限期的结束处理过程我们可以知道，rcu_gp_kthread会判断! (rnp->qsmask) && !rcu_preempt_blocked_readers_cgp(rnp))两个条件来决定GP是否完成，其中!rnp->qsmask代表每个CPU都经过一次quiescent state，quiescent state的定义与传统RCU一致；!rcu_preempt_blocked_readers_cgp(rnp)这个条件就代表了rcu是否还有阻塞的进程
可睡眠RCU
产生背景
realtime linux kernel要求不可抢占的临界区要尽量的短，在这样的需求背景下，spin lock的临界区都因此而修改成为preemptible（只有raw spin lock保持了不可抢占的特性），RCU的临界区也不能豁免，必须作出相应的改动，这也就是srcu的源由
改造
既然sleepable RCU势在必行，那么我们必须要面对的问题就是如何减少RCU callback请求的数量，要知道SRCU的GP可能非常的长。
（1）不再提供GP的异步接口（也就是call_rcu API），仅仅保留同步接口。如果提供了call_srcu这样的接口，那么每一个使用rcu的线程可以提交任意多的RCU callback请求。而同步接口synchronize_srcu（类似RCU的synchronize_rcu接口）会阻塞当前的thread，因此可以确保一个线程只会提交一个请求，从而大大降低请求的数目
（2）细分GP。classic RCU的GP是一个批次一个批次的处理，一个批次的GP是for整个系统的，换句话说，一个RCU reader side临界区如果delay了，那么整个系统的RCU callback都会delay。对于SRCU而言，虽然GP比较长，但是如果能够将使用SRCU的各个内核子系统隔离开来，每个子系统都有自己GP，也就是说，一个RCU reader side临界区如果delay了，那么只是影响该子系统的RCU callback请求处理
API
int init_srcu_struct(struct srcu_struct *sp); void cleanup_srcu_struct(struct srcu_struct *sp); int srcu_read_lock(struct srcu_struct *sp) __acquires(sp); void srcu_read_unlock(struct srcu_struct *sp, int idx) __releases(sp); void synchronize_srcu(struct srcu_struct *sp);
分级RCU
分级RCU状态
no_hz
...
实现
简单demo实现
内核实现
在kernel中，rcu有tiny rcu和tree rcu两种实现，tiny rcu更加简洁，通常用在小型嵌入式系统中，tree rcu则被广泛使用在了server, desktop以及android系统中
treeRCU
核心API
发布订阅机制实现
关键角色
Publish-Subscribe Mechanism (for insertion)
Wait For Pre-Existing RCU Readers to Complete (for deletion)
Maintain Multiple Versions of Recently Updated Objects (for readers)
读
rcu_read_lock()/rcu_read_unlock()
RCU读取侧进入临界区的标志是调用rcu_read_lock
rcu_read_lock()和rcu_read_unlock()用来保持一个读者的RCU临界区.在该临界区内不允许发生上下文切换，即不能被阻塞。为什么不能发生切换呢？因为内核要根据“是否发生过切换”来判断读者是否已结束读操作。
实现细节
#define rcu_read_lock() __rcu_read_lock() #define rcu_read_unlock() __rcu_read_unlock() #define __rcu_read_lock() do { preempt_disable(); __acquire(RCU); rcu_read_acquire(); } while (0) #define __rcu_read_unlock() do { rcu_read_release(); __release(RCU); preempt_enable(); } while (0)
使用要点
rcu_read_lock(),rcu_read_unlock()只是禁止和启用抢占.因为在读者临界区，不允许发生上下文切换
子主题
rcu_read_lock_bh()/rcu_read_unlock_bh()
使用要点
在softirq上下文中,使用rcu_read_lock_bh/rcu_read_unlock_bh,则完成一次softirq handler则认为是一次qs
rcu_dereference()
读者调用它来获得一个被RCU保护的指针
更新
rcu_assign_pointer()
写者使用该函数来为被RCU保护的指针分配一个新的值
单链表的核心就在于指针域，RCU就是利用了指针的一些特性，完成了多版本的维护。RCU保护的是指针，因为指针赋值是一条单指令。配合内存屏障与Lock前缀，指针赋值是一个原子操作，更改指针指向没必要考虑它的同步，只需要考虑cache的影响
实现细节
主要在写之前加了内存屏障 #define rcu_assign_pointer(p, v) \ __rcu_assign_pointer((p), (v), __rcu) #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0)
同步回收
synchronize_rcu()
这是RCU的核心所在，它挂起写者，等待读者都退出后释放老的数据
异步回收
call_run
把回调函数（一般内存释放函数）放入callback列表，等待grace period周期结束进行回调函数处理回收内存更新；
实现细节
/* * Queue a preemptible -RCU callback for invocation after a grace period. */ void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu)) { unsigned long flags; debug_rcu_head_queue(head); head->func = func; head->next = NULL; local_irq_save(flags); *rcu_preempt_ctrlblk.nexttail = head; rcu_preempt_ctrlblk.nexttail = &head->next; RCU_TRACE(rcu_preempt_ctrlblk.rcb.qlen++); rcu_preempt_start_gp(); /* checks to see if GP needed. */ local_irq_restore(flags); }
使用要点
子主题
等待RCU callback执行完成
rcu_barrier()
使用要点
模块卸载，如果还有callback函数，需要调用此函数等待callback完成；
接口对应bh版本
bh版本主要用在中断上下文，使得宽限期更快度过， 细分这些场景是为了提高RCU的效率
rcu_read_lock_bh()/rcu_read_unlock_bh()
使用要点
在softirq上下文中,使用rcu_read_lock_bh/rcu_read_unlock_bh,则完成一次softirq handler则认为是一次qs
rcu_dereference()
rcu_assign_pointer()
synchronize_rcu()
call_run_bh
list-RCU接口
RCU checklist
内核RCU接口使用规范检查
内部实现
初始化
rcu_init
rcu_bootup_announce
rcu_init_geometry
rcu_init_one(&rcu_sched_state, &rcu_sched_data); rcu_init_one(&rcu_bh_state, &rcu_bh_data);
__rcu_init_preempt
open_softirq(RCU_SOFTIRQ, rcu_process_callbacks)
cpu_notifier(rcu_cpu_notify, 0); for_each_online_cpu(cpu) rcu_cpu_notify(NULL, CPU_UP_PREPARE, (void *)(long)cpu);
数据结构
The purpose of this combining tree is to allow per-CPU events such as quiescent states, dyntick-idle transitions, and CPU hotplug operations to be processed efficiently and scalably
quiescent states
dyntick-idle transitions
CPU hotplug operations
rcu_state
Tree RCU有多个类型的RCU State，用于不同的RCU场景，包括rcu_sched_state、rcu_bh_state和rcu_preempt_state。不同的场景使用不同的RCU API，度过宽限期的方式就有所区别
1 用于node和data之间关联； 2 跟踪grace periods状态； 3 serves as short-term repository for callbacks orphaned by CPU-hotplug events 4 维护rcu barrier状态 5 跟踪快速grace period state 6 维护状态用于强行执行quiescent states当grace priode太长时候
rcu_node
RCU树形结构节点，用于构造一颗树
跟踪GP过程
跟踪QS过程
阻塞任务管理针对抢占RCU特性
rcu_data
per cpu结构
和其他node通信
cpu
rcu_node *mynode
unsigned long grpmask
struct rcu_state *rsp;
记录该CPU的QS 和 GP过程状态
completed
gpnum
passed_quiesce
qs_pending
grpmask
RCU 回调函数处理相关的
nxtlist
nxtcompleted[RCU_NEXT_SIZE]
qlen
qlen_lazy
qlen_last_fqs_check
子主题
n_force_qs_snap
batch handling
**nxttail[RCU_NEXT_SIZE]
RCU_DONE_TAIL
RCU_WAIT_TAIL
RCU_NEXT_READY_TAIL
RCU_NEXT_TAIL
blimit
一次处理最大cb个数
n_cbs_invoked
当前CPU处理自己Callback计数
n_cbs_orphaned
本CPUoffline，让其他CPU处理callback计数
n_cbs_adopted
其他CPUoffline，接收处理其他CPUcallback计数
n_nocbs_invoked
本CPU的callback offload到内核线程处理计数
cb offload
nocb_head
nocb_tail
nocb_q_count
nocb_q_count_lazy
nocb_p_count
nocb_p_count_lazy
nocb_wq
nocb_kthread
Dyntick-Idle Handling
rcu_dynticks *dynticks
per cpu 跟踪dynticks idle状态
dynticks_snap
dynticks_fqs
beenonline
offline_fqs
rcu_head
每个节点代表一个RCU callback
该结构嵌入在RCU data结构
rcu_head *next
The ->next field is used to link the rcu_head structures together in the lists within the rcu_data structures
void (*func)(struct rcu_head *head)
The ->func field is a pointer to the function to be called when the callback is ready to be invoked, and this function is passed a pointer to the rcu_head structure
其他
内部同步机制
Each rcu_state structures has a lock and a mutex, and some fields are protected by the corresponding root rcu_node structure's lock
Each rcu_node structure has a spinlock.
The fields in rcu_data are private to the corresponding CPU, although a few can be read and written by other CPUs
主要流程
检查当前CPU是否度过QS
每个CPU上报完成抢占的过程。kernel把这个完成抢占的状态称为quiescent state。每个CPU在时钟中断的处理函数中，都会判断当前CPU是否度过quiescent state，timer_interrupt->hrtimer_interrupt->update_process_times rcu_check_callbacks
普通的RCU例如内核线程、系统调用等场景，使用rcu_read_lock或者rcu_read_lock_sched，他们的实现是一样的；软中断上下文则可以使用rcu_read_lock_bh，使得宽限期更快度过， 细分这些场景是为了提高RCU的效率
rcu_sched_qs
主要是针对rcu_read_lock/rcu_read_unlock临界区
只是禁止和启用抢占.因为在读者临界 区，不允许发生上下文切换，发生上下文切换认为是一次qs
rcu_bh_qs
如果调用在softirq上下文中rcu_read_lock_bh/rcu_read_unlock_bh,则完成一次softirq handler则认为是一次qs，
QS report(汇报宽限期度过)
每个CPU度过quiescent state之后，需要向上汇报直至所有CPU完成quiescent state，从而标识宽限期的完成，这个汇报过程在软中断RCU_SOFTIRQ中完成。软中断的唤醒则是在上述的时钟中断中进行
rcu_report_qs_rdp
更新rcu data qs状态
rcu_report_qs_rnp
其中rcu_report_qs_rnp是从叶子节点向根节点的遍历过程，同一个节点的子节点都通过quiescent state后，该节点也设置为通过
树结构每层的节点数量和叶子节点数量由一系列的宏定义来决定
rcu_report_qs_rsp
向上node更新完后，更新RCU state GP状态，start the grace period
宽限期的发起与完成
rcu_gp_kthread
所有宽限期的发起和完成都是由同一个内核线程rcu_gp_kthread来完成。通过判断rsp->gp_flags & RCU_GP_FLAG_INIT来决定是否发起一个gp；通过判断! (rnp->qsmask) && !rcu_preempt_blocked_readers_cgp(rnp))来决定是否结束一个gp
发起一个GP时，rsp->gpnum++； 结束一个GP时，rsp->completed 等于 rsp->gpnum
rcu callbacks处理
同步处理
rcu的callback通常是在sychronize_rcu中添加的wakeme_after_rcu，也就是唤醒synchronize_rcu的进程，它正在等待GP的结束
异步处理
rcu把cb挂到相应链表上然后退出，它在等待GP的结束再有RCU软中断或者rcu kthread（offload）处理
CONFIG_RCU_NOCB_CPU特性
提供了rcu callback offload， 使rcu callback跑到rcuo kthread上
这里RCU的callbacks链表采用了一种分段链表的方式，整个callback链表，根据具体GP结束的时间，分成若干段：nxtlist -- *nxttail[RCU_DONE_TAIL] -- *nxttail[RCU_WAIT_TAIL] -- *nxttail[RCU_NEXT_READY_TAIL] -- *nxttail[RCU_NEXT_TAIL]
rcu_do_batch只处理nxtlist -- *nxttail[RCU_DONE_TAIL]之间的callbacks。每个GP结束都会重新调整callback所处的段位，每个新的callback将会添加在末尾，也就是*nxttail[RCU_NEXT_TAIL]
实现考虑问题
中断调度，NMI中断，CPU热插拔
bh接口
模块卸载
rcu_barrier()
内核各种调度特性（抢占，RT等）
抢占RCU
节能特性
NO_HZ: Reducing Scheduling-Clock Ticks
https://lwn.net/Articles/549580/
https://lwn.net/Articles/549593/
对应的Dyntick-Idle Handling
EQS
性能和多核扩展性
分级树形RCU
加速gp，expedited gp
正确-稳定性
RCU压力测试
rcutorture
https://lwn.net/Articles/607117/
dpdk实现
PAL实现
读接口
不需要提供read 接口
异步回收
循环等待所有线程释放；
listRCU
类似内核listRCU接口
也采用内存barrier
特点
属于用户态RCU
只有进程上下文
dpdk官方实现（19.08）
参考liburcu--rcu-qsbr实现
用户态的RCU
原理
参考RCU论文和内核RCU实现
它提供了与内核RCU相似的功能，使得在多核多线程并发访问共享数据时，reader线程不用阻塞于writer线程的操作，从而使reader线程运行的更快，非常适合于读多写少的场景
liburcu
rcu-qsbr
性能最好的RCU实现，可以做到reader 0 zerohead，但是需要改动代码，侵入式
核心点
QSBR数据结构-全局计数器
读临界区
读线程函数
读者 注册(register)\去注册(unregister)\上线(online)\下线(offline)
rcu_read_lock和rcu_read_unlock来标记临界区
Quiescent State
写线程函数——synchronize_rcu
rcu-signal
性能仅次于qsbr的实现，不需要改动代码，代价是需要牺牲一个signal给urcu实现
rcu-generic
性能最差的rcu实现（但也比mutex强多了），不需要改动代码，可以作为初始的第一选择
性能对比
urcu_read_only是只有读线程，没有写线程的测试。相当于无锁的版本，也是性能最好的。
urcu_qsbr_test是用urcu-qsbr的实现
urcu_signal_test是用urcu-signal的实现
urcu_generic_test是用urcu-mb的实现
single_mutex_test是用一个mutex来保护共享数据的实现，也是我们最熟悉的实现。
mutex_per_thread_test是每一个读线程都独占一个mutex，写线程需要获取所有读线程的mutex来进入临界区。
wiki
http://liburcu.org/
https://lwn.net/Articles/573424/#Using%20URCU
http://airekans.github.io/c/2016/05/10/dive-into-liburcu
优缺点
因此不会导致锁竞争，内存延迟以及流水线停滞
不需要锁也使得使用更容易，因为死锁问题就不需要考虑了。写者的同步开销比较大，它需要延迟数据结构的释放，复制被修改的数据结构，它也必须使用某种锁机制同步并行的其它写者的修改操作
业界最佳实践
RCU规则对读取者与写入者之间因指针切换所造成的短暂的资源视图不一致问题是允许的。
所有对老指针的引用只可能发生在rcu_read_lock与rcu_read_unlock所包括的临界区中，而在这个临界区中不可能发生进程切换，而一旦出了该临界区就不应该再有任何形式的对老指针p的引用
这个规则要求读取者在临界区中不能发生进程切换，因为一旦有进程切换，释放老指针的回调函数就有可能被调用，从而导致老指针被释放掉，当被切换掉的进程被重新调度运行时它就有可能引用到一个被释放掉的内存空间
现在我们看到为什么rcu_read_lock只需要关闭内核可抢占性就可以了，因为它使得即便在临界区中发生了中断，当前进程也不可能被切换除去
临界区不能睡眠
使用者的责任了，如果在rcu的临界区中调用了一个函数，该函数可能睡眠，那么RCU的设计规则就遭到了破坏，系统将进入一种不稳定的状态
并行程序设计演进
spinlock
互斥锁mutex
信号量
读写锁
RCU相较于rwLock的读端性能优势。从图中可以明显的看出，随着CPU数目的增多，rwlock读取性能下降明显。这是因为在读写锁中，写锁排斥读取的特点导致很多CPU的读取被整体拖慢。而对于RCU来说，CPU的增多却不会明显导致读取性能下降。因为RCU的读端基本是没有锁的
顺序锁
Seqlock也可以让读者和写者并发执行，但是二者有什么区别？
首先是二者的目的不一样。Seqlock是为了保证读端在读取值的时候，写者没有对它进行修改，而RCU是为了多核扩展性
其次是保护的数据结构大小不一样。Seqlock可以保护一组相关联的数据，而RCU只能保护指针这样的unsigned long类型的数据
最重要的区别还在于效率，Seqlock本质上是与自旋锁同等重量级的原语，其效率与RCU不在同一个数量级上面
内存屏障
CPU执行乱序
编译乱序
lock-free
RCU
出现背景
高性能并行程序中，数据一致性访问是一个非常重要的部分，一般都是采用锁机制（semaphore、spinlock、rwlock等）进行保护共享数据，根本的思想就是在访问临界资源时，首先访问一个全局的变量（锁），通过全局变量的状态来控制线程对临界资源的访问。但是，这种思想是需要硬件支持的，硬件需要配合实现全局变量（锁）的读-修改-写，现代CPU都会提供这样的原子化指令
采用锁机制实现数据访问的一致性存在如下两个问题
效率问题。锁机制的实现需要对内存的原子化访问，这种访问操作会破坏流水线操作，降低了流水线效率，这是影响性能的一个因素。另外，在采用读写锁机制的情况下，写锁是排他锁，无法实现写锁与读锁的并发操作，在某些应用下回降低性能
扩展性问题。例如，当系统中CPU数量增多的时候，采用锁机制实现数据的同步访问效率偏低。并且随着CPU数量的增多，效率降低，由此可见锁机制实现的数据一致性访问扩展性差
原始的RCU思想
在多线程场景下，经常我们需要并发访问一个数据结构，为了保证线程安全我们会考虑使用互斥设施来进行同步，更进一步我们会根据对这个数据结构的读写比例而选用读写锁进行优化。但是读写锁不是唯一的方式，我们可以借助于COW技术来做到写操作不需要加锁，也就是在读的时候正常读，写的时候，先加锁拷贝一份，然后进行写，写完就原子的更新回去，使用COW实现避免了频繁加读写锁本身的性能开销
引发的问题
当更新的时候会导致其他在读取的线程轻则只是读取到错误的信息，重则进行指针的二次引用访问了非法地址导致core dump
解决方案
解决二三两个读取错误问题
问题是什么
CPU乱序和编译器过度优化导致的读取错误的问题，这个因为乱序导致的读取不正确的问题。
解决方案
防止乱序的通常做法就是内存栅。巧的是，内存栅同时可以预防编译器的过度优化，所以用内存栅的方法就可以同时解决二三两个问题，为了解决CPU乱序和编译器过度优化导致的读取错误的问题，有rcu_assign_pointer和rcu_dereference两个函数的实现，用内存栅的方式达到了这个目的
引申问题
为什么CPU乱序执行
为什么编译器会乱序优化
真正理解RCU容忍的脏数据到底是怎么界定的
解决第一个读错误的问题
问题是什么
写操作一个很大的问题是要同时删除之前的数据结构，这个时候有其他的读者在使用这个结构的时候，就会导致读取问题