Classic RCU

  这篇文章主要了classic rcu 在2.6.31的实现，以及classic rcu 在kmemleak 的应用。

1. Classic RCU 实现

  RCU(Read-copy Update)  是 在 2002年10月引入Linux 2.5 内核，到现在最新的5.6 Linux 内核，已经由Classic RCU, 发展出了 Tiny RCU, Hierarchy RCU, Preemptable RCU, Sleepable RCU, 这里 主要介绍 Classic RCU, 在内核2.6.31 里面的实现，也就是最后一个实现了Classic RCU 的内核版本。RCU 最基本的API 包括：

• rcu_read_lock
• rcu_read_unlock
• synchronize_rcu/call_rcu
• rcu_assign_pointer
• rcu_deference

其最核心的原理也比较直观，就是如何安全的实现对内存资源的回收

现在直接分析对应的内核代码对于 2.6.31 内核版本的代码主要是

/include/linux/rcuclassic.h

/include/linux/rcuupdate.h

/kernel/rcuclassic.c

/kernel/rcuupdate.c

首先看 最核心api 的实现

rcu_read_lock/rcu_read_unlock

可以看到kernel 里面对于 尤其是对于none-preemptable的内核而言，读端的负载基本是0（zero overhead）,对于 preemptable 的场景，只需要禁掉抢占并且 保证 基本 acquire/release 的语义， 这里实现 acquire/release 利用了编译器 提供的 __context__的函数， 本质上 preempt_disable/preempt_enable 已经提供了memory barrier.

rcu_deference

只是加了一些linux 内存模型的原语，保证了读写的顺序，smp_read_barrier_depends 这个语句只在alpha CPU 模型上有意义，其他cpu 都提供了cache coherence 的保证

rcu_assign_pointer

smp_wmb 这里的作用主要利用了 B-Cumulative, 保证其他的执行单元的对于p 的memory  access 是在 smp_wmb  propagated to 对应的cpu 之后。

synchronize_rcu

 

可以看到 synchronize_rcu 的实现本质上是依赖于call_rcu, 都注册一个wake up 的function， 并利用内核了completion同步机制实现 异步到同步转换，内核的completion 可以等效于user space 的 condition variable.

可以看到，对于rcu 的核心的api 除了call_rcu 以后，其他的实现都比较简单，下面分析 call_rcu 的实现，以及rcu背后的state machine.

首先 kernel 内部有一个全局单例的管理object:

里面的核心变量就是 cpu 的bitmap 标记cpu 是否经过了 QS

也是由于这个变量的存在导致之后linux kernel 出现了TinyRCU， HierarchyRCU. 尽管spinlock 以及整个object 都加了 __cacheline_internodealigned_in_smp 以避免出现cacheline trashing,但是随着现代硬件的核心数量增加，还是会出现性能问题。

除了 cpumask 这个变量之外，还有 三个标记batch id 的 变量

 

Cur 表示当前kenerl 内部的正在进行的batch id,

Complete 表示以及完成的上一次的batch id

Pending 表示即将开始的batch id, 所以在任意时刻，kernel 内部rcu_ctrblk batch id 只有三种状态。

这个control block的初始化如下：

除了全局的状态标记结构，per-cpu 还有一个本地object ，记录per-cpu 的状态。

这个object 主要记录了两部分内容，一部分是 当前的 QS(quiescent state) 状态，

quiescbatch 表示当前cpu 的正在经历的batch number

passed_quiesc 表示是否经过了 quiesc state

qs_pending 表示是否未经过quiesc state(本质上这个变量其实是不需要的，这个只是为了 减少对cpumask 的访问，避免 cacheline trashing)

另一部分是对callback 的管理，

rcu_head 是记录callback 简单的数据结构：

利用rcu_head** 管理不同batch 对应的callback 函数

现在具体分析隐藏在rcu api 背后的逻辑：

首先需要明确一点 什么 叫QS, 简单的讲就是cpu 调用了rcu_read_unlock, 离开了临界区，因为classic rcu 是disable preempt , 所以对于reader 而言，只要发生了一次调度，则肯定进入了QS。

然后看看call_rcu 的逻辑：

这里逻辑就是把callback 加入到nxtlist, 并更新nxtlist 里面的tail指针指向的位置。

最后调用如果 qlen > qhimark, 则说明callback 数量太多，则需要强制进入 quiescent_state, 正如前面所说，则需要一次调度。

这个逻辑就是 对当前的cpu 运行逻辑设置调度标记

然后对其他CPU发送IPI interrupt 进行 reschedule。而在进程发生调度的时刻，会调用

这个函数做的事很简单，就rcu_data.passed_quiesc 置位

而对于每个cpu 的状态的检测，则是在timer interrupt handle 里面处理的

这个function 在每个tick 到来的时候都会被调用，并检查对应的cpu是否需要处理。

当调用rcu_check_callbacks, 如果当前进程处于用户态或者处于非中断状态下的 idle 模式，则对应cpu 已经pass了QS，同时触发一个softirq。在rcu 初始化时，会注册对应的interrupt hanlder。

rcu_process_callbacks 函数主要是处理 callback 函数并更新对应rcu_data 以及rcu control block 的状态。

这个就是rcu_process_callback的逻辑，也是整个rcu的核心的逻辑。所以整个rcu 的流程就是通过call_rcu 注册call back,从而增加batch id。而对应的timer interrupt handler 里面更新 rcu control block 以及对应rcu data 的状态，同时处理done 的call back。

2. Classic RCU 在kmemleak 应用

  Kmemleak 是 内核提供的内存泄露的检测工具，这个工具直到5.6内核版本仍然存在，本文介绍的是基于2.6.31内核版本。它的基本原理就是Tracing Garbage Collection。Valgrind 的用户空间内存检测工具也是基于类似的原理实现的。其基本的原理主要就是 因为内核的内存分配器主要是 kmalloc, vmalloc, kmem_cache_alloc 这三类，所以对于分配内存的记录就是在这三类函数里面加了一个hook 的逻辑，标记对象并加入到一个集合中。然后在对应的kfree, vfree, kmem_cache_free 函数中插入一个hook 的逻辑。并通过run 一个kernel thread，到达检测memleak 的目的。

其基本的算法思想如下：

• 对所有分配的对象创建meta object, kmemleak_object, 并将这个object 标记成white
• 首先扫描data section和stack, 检测是否有pointer指向之前的meta object 的集合，则把对应white object 变成 gray object
• 然后扫描gray object 的集合，是否有pointer 指向现有white object, 则把对应white object 加入到gray object list 的 tail, 直到grail object list 扫描完毕
• 则剩余的white object 就是 有memleak 的内核对象

而在实现过程中，使用了rcu 保护了meta object 的 object list。使用了call_rcu 是实现了安全的删除meta object。

这个就是 meta object 其中使用 use_count 作为object 的reference count。当reference count == 0 的时候，就调用call_rcu 注册free 的逻辑。内部通过使用put_object/get_object 控制object 的生命周期。

删除的meta object 的逻辑主要是对于kfree, vfree, kmem_cache_free的hook 逻辑

而核心的逻辑的就是kmemleak_scan_thread, 基本的实现就是前文提到的两次扫描，确定white object。

首先是扫描data section:

然后是扫描task stack

最后就是扫描graylist

通过分析kmemleak 的实现可以发现，这个工具主要是利用了经典的Tri-Color Marking, 而rcu 在里面扮演的角色主要是对meta object的内存管理。保证安全的使用meta object.