http://blog.csdn.net/junguo/article/details/8258231
http://blog.csdn.net/junguo/article/details/8258261
http://blog.csdn.net/junguo/article/details/8268277
TREE RCU实现之一 —— 数据结构
代码分布
在分析代码之前, 先看看代码的分布情况。RCU实现的代码包含在下列一些文件中,此处用到的是linux 3.6.4的代码。
< include/linux/rcupdate.h > RCU实现的头文件,所有使用RCU的代码都需要包含它
< include/rcutree.h > 包含rcupdate.h中没有包含的函数声明。
< include/rcutiny.h > 包含rcupdate.h中没有包含的函数声明。
< kernel/rcupdate.c > 包括一些RCU实现的基础函数的实现。
< kernel/rcutree.h > 包含Tree RCU用到的结构信息,TREE_RCU将所有的CPU组织成一颗树,通过层次结构来判别进程是否通过了宽限期,这种方式适用于多个CPU的系统。
< kernel/rcutree.c > 包含Tree RCU的主要实现代码。
< kernel/rcutree_plugin.h > 其实也是TREE RCU实现的一部分。主要包含了抢入式TreeRCU的代码。适用于抢入式的系统,抢入式的系统适用于需要低延迟的桌面或者嵌入式系统。
< kernel/rcutiny.c > Tiny RCU的主要实现代码,TINY_RCU适用于单个CPU,尤其是嵌入式操作系统。
< kernel/rcutiny_plugin.h > 主要包含了抢入式Tiny RCU的代码
< kernel/rcu.h > 定义了debug的接口,实现了__rcu_reclaim
。
< kernel/rcutorture.c> 对RCU进行稳定性测试的代码,通过配置CONFIG_RCU_TORTURE_TEST,可以在系统启动的时候运行稳定性测试。
< kernel/rcutree_trace.c> 通过配置CONFIG_RCU_TRACE,可以记录RCU的运行信息。
< include/trace/events/rcu.h> 为rcutree_trace.c定义的头文件。
RCU处理的基本流程
RCU实现的关键集中在宽限期的处理上,这个过程需要保证销毁对象前,当前系统中所有CPU上运行的进程都通过了静止状态(quiescent state)。
1, 程序调用call_rcu,将要删除的对象保存起来。并标记或者开始一个宽限期(同一时间只能运行一个宽限期,所以当已经有宽限期在运行的时候,其它的宽限期必须等待)。
2, 在读取数据开始和结尾处增加 rcu_read_lock 和 rcu_read_unlock来标记读过程。为了保证删除过程知道读过程的结束,在非抢占式RCU实现中是在rcu_read_lock开始处禁止进程抢占。这样做就可以保证再运行下一次进程切换的时候,读过程已经结束。其实系统也不会去统计各个CPU上是否存在过读线程,所以所有的CPU都会在进程切换的时候通知系统它处于进制状态。当所有的CPU都通过静止状态的时候,系统就会标记它通过了一个宽限期。
3,由于一个宽限期结束的时候,只有最后一个通过静止状态的CPU知道当前的宽限期已经结束,它并不会去通知其它CPU;同时出于性能考虑,系统也不会在宽限期结束后,马上去执行销毁过程。所以每个CPU都有一个固定的函数去检测是否有等待执行的宽限期,如果没有特别紧急的任务时,会去执行这些过程。
接下来,要分析Tree RCU的实现,先来看看它提供的一些接口函数。
1, call_rcu 与 synchronize_rcu都是删除对象时调用的函数。call_rcu将数据提交后会返回,而synchronize_rcu会调用call_rcu,并一直等待对象被删除后才返回。还有call_rcu_bh与synchronize_rcu_bh等接口函数,会在后续讲述。
2,rcu_read_lock 和 rcu_read_unlock
<linux/rcuupdate.h>
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
rcu_read_lock与rcu_read_unlock在非抢占式下的实现比较简单就是 preempt_disable与preempt_enable。这样做的目的是当调用schedule的时候,就可以肯定读的过程已经结束。其它_acquire(RCU)等函数是调试用的代码,暂不做讨论。
3, rcu_note_context_switch 在schedule中调用,每次进程切换就代表着一个静止状态。该函数会把当前的CPU状态设置为通过状态。
4, rcu_check_callbacks 在每次时钟周期里调用(update_process_times)。通过它会触发软件中断,软件中断对应着rcu_process_callbacks,这是一个真正繁忙的函数,他会检测当前CPU的状态,向父节点传递静止状态信息,调用注册函数等一系列工作。
在进一步了解这些函数之前,我们先来看看你Tree RCU的结构。
TREE RCU简介
在统计CPU的状态的时候,需要用到一个结构来存放所有CPU的状态。在早期的实现中,所有的状态都保存在一个结构中,这样做的后果是所有的CPU在更新自己状态的时候,都需要锁定该结构对象,一定程度上影响了系统性能。为了提高性能,把一定数目的CPU组成了一个节点(默认设定64个CPU为一个节点);当节点超过64个的时候,再把这些节点按64为单位划分为归属不同的父节点;如此类推,最后的一个单独的节点作为根节点。这样在更新CPU状态的时候,只需要锁定自己所属的节点就可以了。按节点设置的数目,可见这个结构只对CPU数成百上千的系统才真正起作用(我都没见过超过32个cpu的机器,不知道是啥样的感觉)。
这样所有的CPU就按层级结构组织了起来,也就是一个树结构。当一个系统的CPU数少于64个的时候,只要一个rcu_node就可以。
每个CPU在完成宽限期检测的时候,就会去更新它所属的rcu_node的值,当一个rcu_node所包含的CPU的状态都更新过以后,该node就会去更新它所属的父节点的值。直到最后一个根节点。
TREE RCU数据结构
为了实现该结构,系统提供了以下结构。
rcu_data
由于RCU需要统计每个CPU是否通过了宽限期,提供了rcu_data来保存信息。另外每个销毁的对象并不是直接删除,也保存在rcu_data中,等到合适的时机来执行。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
|
1,completed ,gpnum , passed_quiesce_gpnum
gpnum表示当前正在运行的宽限期的个数,每当一个宽限期开始的时候,会设置这个值与其父节点相同。passed_quiesce_gpnum为当前CPU通过的宽限期个数,它的值在宽限期开始的时候小于gpnum,当这个CPU经过一个静止状态的时候,会把它设置成gpnum的值,通过对比它与父节点中的gpnum是否相同,可以确定该CPU是否通过了宽限期。passed_quiesce_gpnum只是表示这个CPU通过了宽限期,而completed表示所有的CPU都通过了宽限期,设置该值的同时,可以将nxtlist中等待的回调函数移动到完成队列。
2,nxtlist 与nxttail
nxtlist保存的是指向rcu_head对象,rcu_head的定义如下:
1 2 3 4 5 |
|
rcu_head的结构并不复杂,它包含一个回调函数指针。而next可以把rcu_head连成一个列表。
nxtlist指向一个rcu_head 列表,而nxttail的四个元素是指向指针的指针,它们指向的是rcu_head对象的next。RCU_DONE_TAIL指向的rcu_head对象之前的对象是可以销毁的对象。RCU_WAIT_TAIL指向的正在等待宽限期的元素,RCU_NEXT_READ_TAIL指向的是等待下次宽限期的元素,RCU_NEXT_TAIL指向最后一个元素,这个元素总是指向NULL。
rcu_node
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
|
每个rcu_node代表着 一组CPU或者子节点。在非抢占式下,它的结构并不复杂。由于可能有多个CPU对它进行处理,所有进行相应操作的时候,需要lock保护。
rcu_state
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
|
rcu_state 保存了所有的node,宽限期的判断只要取出根节点,也就是第一个元素就可以。还有一些初始化要用到的变量。还有孤儿回调函数用于处理离线CPU遗留的信息。剩下还有很多统计信息,这些内容在讲解代码实现的时候再仔细考虑。
TREE RCU实现之二 —— 主干函数
RCU的实现集中在以下几个步骤:
1, 调用call_rcu,将回调函数增加到列表。
2, 开始一个宽限期。
3, 每个CPU报告自己的状态,直到最后一个CPU,结束一个宽限期。
4, 宽限期结束,每个CPU处理自己的回调函数。
call_rcu的实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
|
call_rcu中最主要的工作,就是将回调函数加入到CPU的nxtlist列表。这里用到了指针处理的小技巧,我们来看看。首先看看nxttail的初始化:
1 2 3 4 5 6 7 8 |
|
我们看到nxttail的全部成员都指向了nxtlist的地址。当nxtlist为空的时候,也是这个情形。
1
|
|
当nxtlist为空的时候, *rdp->nxttail[RCU_NEXT_TAIL] 得到的其实就是nxtlist,将head的值赋予它。
1
|
|
之后 RCU_NEXT_TAIL指向 head的next指针。这样当再有一个节点加入的时候,*rdp->nxttail[RCU_NEXT_TAIL]得到的其实就是前一次加入的head的next指针,它将指向新加入的值。如此,nxtlist就成为了一个链表。或者这样理解,rdp->nxttail[RCU_NEXT_TAIL] 指向的就是nxtlist中最后一个节点的 next指针。
除了将回调函数插入,该函数其它代码多为检查代码。而最后要调用__call_rcu_core
,该函数的功用主要是在回调函数太多或者等待时间过长的状态下,强制执行RCU状态更新。我们暂时不关注。
开始一个宽限期
在一个宽限期结束,或者当一个CPU检测到自身有需要一个宽限期的时候会开始一个新的宽限期,开始宽限期的代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
|
标记一个新的宽限期开始,rcu_state要做的就是将gp_num加1。然后再设置所有node,qsmask被设置成qsmasinit,qsmask每个bit代表一个CPU,所有在线的CPU都将被设置成1;gpnum将被设置成新值。嗯,一个新宽限期的开始只需要设置这些标记位。
CPU的宽限期检测
当一个宽限期开始后,每个CPU都需要检测自己的状态,如果已经通过静止状态,那么就向上一级node进行报告。
这个处理过程,可以分为两个步骤:
1, 检测新的处理过程开始,设置rcu_data中的gpnum和passed_quiesce,另外用qs_pending标记一个待处理的新宽限期的开始。
2, 一个静止状态结束,向上一级node报告这个过程。
这两个过程通过rcu_check_quiescent_state()来实现,需要注意的是这个函数隔一段时间调用一次,并不只调用一次。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
A, CPU检测新宽限期的开始
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
|
check_for_new_grace_period 和 note_new_gpnum分别用来检测rdp的gpnum与rsp已经对应的rnp的值是否相同,来确定是否有一个新的宽限期开始。之所以需要检测两次,是因为在rsp设置以后,rnp可能并没有设置完成。
__note_new_gpnum
将设置gpnum的值。另外设置 qs_pending为1,该标记位代表该节点还没有向父节点报告自己的状态;passed_quiesce为0,表示需要一个静止状态,设置该位是因为下次调用rcu_check_quiescent_state()可能是在一个读过程还没有结束的时候。
qs_pending的状态有可能为0,这只在以下情形下出现:当前CPU在宽限期开始的时候实在离线状态,而现在变成了在线。
我们注意到在 check_for_new_grace_period检测到有新的宽限期开始后,rcu_check_quiescent_state将直接返回,因为这个宽限期可能是在该CPU的上一个静止状态之前已经开始,所以需要等待下一个静止状态。
B,CPU报告静止状态
当再一次调用到rcu_check_quiescent_state()的时候,check_for_new_grace_period()将返回FALSE,接着运行后面的函数来判断 qs_pending 和 passed_quiesce 的值来决定是否调用rcu_report_qs_rdp。需要判断qs_peding是因为当这次rcu_report_qs_rdp调用成功的时候,下次再运行rcu_check_quiescent_state()则不需要继续运行后续函数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
从我看来,这个函数只会调用到最后一个else分支,而之前的连个if分支都不会调用到。因为在调用该函数前,代码已经做了必要的检测。
以此来看,这个函数的功用就是设置qs_pending的值,阻止这次宽限期没有完成之前再次调用掉该函数;设置nxttail,决定下次宽限期后可以执行的回调函数;然后向父节点报告静止状态完成。
C,向上报告
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
|
这个过程并不复杂,清理rnp中qsmask对应该CPU的bit。然后判断该节点是否处理完成,如果是则继续向上调用,否则就退出函数。最后一个CPU调用后,可以调用到rcu_report_qs_rsp()。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
|
这个过程最主要的内容就是设置rsp->completed的值,中间多了对node的处理。因为在rcu_start_gp中也会对node进行处理,当前CPU无法判断其它CPU是否需要一个宽限期,但它自身还有等待宽限期的回调函数的时候,它确定会有一个新的宽限期马上开始,所以忽略这个过程。
CPU的宽限期结束处理
这个过程也可以分为两个步骤,第一步是检查宽限期是否结束,第二步是调用已完成的回调函数。
A, CPU检测宽限期的结束
每个CPU都会定期检查当前的宽限期是否结束,如果结束将处理自身状态已经nxtlist表。rcu_process_gp_end就是用来做这个事情:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
当 rdp->completed与rnp->completed的值不同的时候,会调用__rcu_process_gp_end
来完成具体的工作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
|
这个过程的重点是设置nxttail的值,将根据它来进行下一步的处理。
B,回调函数的调用
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
|
rcu_do_batch主要作用是取出nxtlist中,nxttail[RCU_DONE_TAIL]之前的元素,遍历执行它们。这时候销毁过程真正的执行了。这段函数需要仔细想想nxttail的处理。
到此RCU中涉及到的主干函数介绍完了,但是还需要与进程切换等过程交互。将在下节分析它们。
TREE RCU实现之三 —— 定期调用
上一节,介绍过了RCU实现中用到的主要函数。不过还需要定期的运行这些函数,整个机制才完整。
RCU的实现是通过在update_process_times() 中调用rcu_check_callbacks()来达到这个目的的。每个CPU都会定期的调用update_process_times()。rcu_check_callbacks()会去检查当前的RCU机制中是否有需要处理的内容,如当前CPU需要开启一个新的宽限期,当前CPU上的宽限期还没有处理完成。如果有需要处理的内容,将触发一个软件中断,真正的操作由软件中断触发的rcu_process_callbacks()来完成。
rcu_check_callbacks
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
该函数的主要功能是通过 rcu_pending()判断是否当前有需要处理的rcu内容,如果有调用invoke_rcu_core()。
1 2 3 4 5 6 7 8 9 |
|
rcu_pending会循环所有的rcu_state,在非抢占式模式下,有rcu_sched_state 和rcu_bh_state 两个实例。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
|
__rcu_pending
判断了可能存在的各种情形,如果有需要处理的工作的话,就返回1,否则返回0。
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
软件中断其实就是调用之前提到过的函数来完成具体的任务。