之前在调试Linux Kernel时遇到了一些oops信息是RCU代码中的,看了几天linux kernel的RCU机制,在此记录。

0x01 Linux RCU机制是什么?

RCU全称read only update,是Linux内核中的一种同步机制。RCU的原理可以简述如下:RCU记录了所有对共享数据的使用者。当内核线程需要write某个数据时,先创建一个副本,在副本中修改。当所有读线程都离开临界区后,新的数据才被更新。

相对于其它的同步机制,由于RCU的写时复制,因此如果对于读数据的线程,开销是很小的。只有修改数据时,才会带来额外的开销。

RCU主要针对的数据对象是链表,目的是提高遍历读取数据的效率,为了达到目的使用RCU机制读取数据的时候不对链表进行耗时的加锁操作。这样在同一时间可以有多个线程同时读取该链表,并且允许一个线程对链表进行修改(修改的时候,需要加锁)。RCU适用于需要频繁的读取数据,而相应修改数据并不多的情景,例如在文件系统中,经常需要查找定位目录,而对目录的修改相对来说并不多,这就是RCU发挥作用的最佳场景。

内核中关于RCU的常见接口如下:

  1. **rcu_read_lock()/ rcu_read_unlock() ** RCU临界区
  2. read_newptr = rcu_dereference(ptr) 内核线程读取数据时,获取被RCU保护的指针,进行读操作时,用newptr来读。
  3. rcu_assign_pointer(ptr, newptr) 修改原来的指针,指向被复制并被修改后的数据。步骤可以简述如下:
    1. 在写之前,ptr指向旧的数据,创建一个oldptr和newptr,其中oldptr指向原来的数据,newptr需要malloc之后复制时需要的空间。
    2. 用oldptr复制数据给newptr后,使用newptr更新数据。
    3. 更新数据完成后,修改原来的指针时,就需要调用本接口rcu_assign_pointer(ptr, newptr) 来实现更新原有的数据。
    4. 通常在此时候会用4中的回调函数来删除oldptr。
  4. call_rcu() 注册回调函数,一般是在写的线程中,当所有的读线程离开临界区后,删除旧数据。

0x02 an example to learn linux RCU

例子来源于《奔跑吧linux内核》,详细说明可以参考linux源码中Documentation\RCU\whatisRCU.txt。
在该例子中,我们可以看到上述接口的具体使用说明。通常被rcu保护的struct中会有 struct rcu_head rcu;这个结构体。


在该例子中,需要同步的数据结构为struct foo,并创建了结构体指针g_ptr。

读线程使用rcu_read_lock()/ rcu_read_unlock() 创建临界区后,使用p= rcu_dereference(g_ptr) 来获取被保护的指针,后续使用p来读数据。

写线程创建了old和new_ptr结构体指针,new_ptr调用kmalloc申请了需要复制的结构体的大小,并把old数据复制给new_ptr,之后使用new_ptr修改数据完成后,调用rcu_assign_pointer(g_ptr, new_ptr)来修改原始的g_ptr,并调用call_rcu注册回调函数用户删除old数据。

用一张图片来解释上述过程:

0x03 Tree RCU中的*nxtlist和**nxttail[RCU_NEXT_TAIL]

Linux的RCU机制实现有两种:经典RCU和Tree RCU。RCU机制从linux kernel2.5中开始引入。由于在大型系统中遇到了性能问题,IBM内核专家Paul E. McKenney提出了Tree RCU的实现。

在讲述两种RCU的区别之前,需要明确以下两个概念:宽限期Grace Period(GP)静止状态Quiescent State(QS)。

宽限期GP,宽限期是一个period,可长可短。参考下图,彩色的部分是一个删除的过程。宽限期从删除动作发生后开始,此时time为t1;t1时所有的读线程都结束后宽限期结束,此时time为t2。GP=t2-t1。因此宽限期可长可短,取决于读线程读多久。

静止状态QS,QS是用来描述CPU的。假设有4个CPU(每个CPU一个thread)对数据进行读操作,当CPU离开临界区后,该CPU就处于静止状态。

在经典RCU中,使用一个全局的cpumask位图(理解为一个全局变量)来标记所有CPU是否处于QS中。当GP开始时,CPU修改cpumask中的对应位,GP结束时,清楚cpumask中的对应位。由于多个CPU的竞争,需要引入锁的机制。那么当CPU很多时,则竞争的激烈程度成线性增长。

因此,为了解决对cpumask位图的竞争,就引入了Tree RCU。Tree RCU使用rcu_node节点来管理CPU。假设在4核CPU中,一个rcu_node管理2个CPU(假设为CPU1和CPU2),可以用2个rcu_node来管理4个CPU。继续增加一个rcu_node0就可以管理这2个rcu_node,从而管理所有的CPU状态。

当这4个CPU都经历过一个QS后,CPU1和CPU2竞争清除rcu_node1中的对应位,CPU3和CPU4来竞争清除rcu_node2中的对应位。此时,竞争的数量就大大减小了。当rcu_node1和rcu_node2中的对应位都清除后,就可以清除增加的rcu_node0中的对应位。可见Tree RCU的实现就是通过增加rcu_node的方式来减少竞争。实现的过程类似下图中的树形结构:

0x04 rcu_head单链表的增加过程

rcu_head的结构体指针会作为成员出现在RCU机制保护的结构体中,作用是保存写者thread删除old数据时的回调函数(函数作用是删除old数据)。对于该结构体的操作会在call_rcu()中实现。介绍call_rcu()之前需要介绍一下RCU机制中的相关数据结构。

Linux Kernel中在实现Tree RCU中有三个比较重要的数据结构:struct rcu_data、struct rcu_node、struct rcu_state。

  • struct rcu_data: 每个CPU一个,可以理解上图中的cpu叶子节点。
  • struct rcu_node: 管理rcu_data,可以理解为上图中的rcu_node。
  • struct rcu_state:描述不同类型的RCU系统状态的,暂时没用到,先跳过吧。

其中struct rcu_data中具有两个比较重要的成员    struct rcu_head *nxtlist;struct rcu_head **nxttail[RCU_NEXT_SIZE];

这两个成员实现了对rcu_head的管理。具体如下。

初始化时,nxtlist为NULL,nxttail[RCU_NEXT_TAIL]指向nxlist,保存着nxtlist的地址。

当写者thread调用call_rcu()删除数据时,最终调用__call_rcu()来增加rcu_head结构体链表中的成员。

上述代码中,head指向新加入的rcu_head结构体的指针。

  • *rdp->nxttail[RCU_NEXT_TAIL] = head; 起始时,rdp->nxttail[RCU_NEXT_TAIL] 指向nxlist,则nxlist指向了rcu_head,因此此rdp->nxttail[RCU_NEXT_TAIL]总是指向新加入的rcu_head(也就是修改了当前链表中最后一个rcu_head中next为新加入的rcu_head的地址。

  • rdp->nxttail[RCU_NEXT_TAIL] = &head->next;  修改了rdp->nxttail[RCU_NEXT_TAIL] 的内容,指向rcu_head->next,保存存了新加入的rcu_head中next成员的地址,以便后续再加入新的rcu_head。

修改了两个指针的过程如下,对应两个箭头的修改:

后续再增加new rcu_head时,先修改最后一个rcu_head中的next为new rcu_head的地址,再修改rdp->nxttail[RCU_NEXT_TAIL] 的内容,指向new rcu_head->next。

最终形成了rcu_head单链表,保存着一个GP结束后,需要调用的回调函数。

0x05 参考

  1. 《奔跑吧Linux内核》
  2. 《Linux内核设计与实现》
  3. https://blog.csdn.net/junguo/article/details/8244530