rcu

发表评论

记录看代码的一些思路:
当时的疑问:
1. rcu call_back没有带有加入的时候对应的gp_num, 怎么才能确保是对的?
两个方面保证的:
1) rnp->completed 是在start_gp时候设置的,和rsp->completed相同的以及rnp->gp_num.
2) rcu_process_gp_end 是per cpu调用的, 会用到rdp per cpu的数据.
在每次调用rcu_process_gp_end的情况下, 如果当前的rdp->completed != rnp->completed
代表的是rdp从上次结束到当前截至加入的callback 对应的graceperiod已经过去了,可以调用
callback了,这里

RCU 对于callback的理解:

178         /*
179          * If nxtlist is not NULL, it is partitioned as follows.                                                                
180          * Any of the partitions might be empty, in which case the                                                              
181          * pointer to that partition will be equal to the pointer for                                                            
182          * the following partition.  When the list is empty, all of
183          * the nxttail elements point to the ->nxtlist pointer itself,
184          * which in that case is NULL.
185          *
186          * [nxtlist, *nxttail[RCU_DONE_TAIL]):                                                                                  
187          *      Entries that batch # <= ->completed
188          *      The grace period for these entries has completed, and
189          *      the other grace-period-completed entries may be moved
190          *      here temporarily in rcu_process_callbacks().                                                                    
191          * [*nxttail[RCU_DONE_TAIL], *nxttail[RCU_WAIT_TAIL]):                                                                  
192          *      Entries that batch # <= ->completed - 1: waiting for current GP                                                  
193          * [*nxttail[RCU_WAIT_TAIL], *nxttail[RCU_NEXT_READY_TAIL]):                                                            
194          *      Entries known to have arrived before current GP ended                                                            
195          * [*nxttail[RCU_NEXT_READY_TAIL], *nxttail[RCU_NEXT_TAIL]):
196          *      Entries that might have arrived after current GP ended                                                          
197          *      Note that the value of *nxttail[RCU_NEXT_TAIL] will                                                              
198          *      always be NULL, as this is the end of the list.                                                                  
199          */
  • [nxtlist, *nxttail[RCU_DONE_TAIL])]: 这些callback对应的gp已经结束了, 需要处理.
  • [*nxttail[RCU_DONE_TAIL], *nxttail[RCU_WAIT_TAIL])]: 这些callback对应的在等待当前的当前gp结束:
    (1)当发现当前gp结束后可以通过 nxttail[RCU_DONE_TAIL]) = nxttail[RCU_WAIT_TAIL]) 这个动作将对应的这些callback放入到已经接受callback里面.
    (2) 对应WAIT_TAIL的更新有两个地方, 一个是当前CPU开始了一个新的gp: 很显然 在这个动作之前发生加入的callback都可以认为是等待当前的这个新开始的gp完成, 也就是nxttail[RCU_WAIT_TAIL] = nxttail[RCU_NEXT_TAIL]. 第二个更新点是发生在: 当前的gp已经完成, 那么能够确认是在该gp end前加入的callback就可以明确的被加入到等待下一个gp完成队列中, 也就是nxttail[RCU_WAIT_TAIL] = nxttail[RCU_NEXT_READY_TAIL](这里相当于在等待下一个gp结束).
  • [*nxttail[RCU_WAIT_TAIL], *nxttail[RCU_NEXT_READY_TAIL])]:代表的是在该gp结束前确认被加入的callback:
    (1) RCU_NEXT_READY_TAIL 更新有两个地方: 第一个地方在该cpu report qs的时候, 因为当前的gp end依赖于当前cpu report qs, 所以可以认为当前已经加入的callback 可以被认为是该gp end之前加入的, 也就是 nxttail[RCU_NEXT_READY_TAIL] = nxttail[RCU_NEXT_TAIL]. 第二个地方是在该gp已经完成, 并且这个CPU看到了这个完成的动作, 那么可以认为所有新加入的RCU_NEXT_TAIL之前的callback可以认为是新的gp结束前加入的, nxttail[RCU_NEXT_READY_TAIL] =nxttail[RCU_NEXT_TAIL]. 这个我们无法假设这些加入的callback是等待新gp结束的, 这个原因在于, 如果其他的CPUB开始了新的gp, CPUA 需要一段时间才能知道这个新的gp, 在这段时间内加入的callback, 可能需要看到其他的CPU发生了一次调度, 但是无法确保的是任意时刻加入的callback都能保证在新gp结束后都能看到一个调度, 举个例子. CPUB开始了一个新的gp, CPUC 完成了一次调度并且 report 了一个qs, CPUA 可能同时加入了一个callback这个callback需要等待一个其他所有的CPUs都发生一个调度, 但是对于新gp来说的话, 它只需要等待除了CPUC之外的所有cpu发生了一次调度, 这和CPUA新加入的callback是需要的条件是不一样的. 所以如果只是看拿到了当前的gp 完成, 是无法假设中间加入的callback是等待新的gp完成的. 只能假设这些callback是在等待新gp结束前加入的.
  • [*nxttail[RCU_NEXT_READY_TAIL], *nxttail[RCU_NEXT_TAIL])]:代表的是这些callback可能是在当前gp结束后加入的.

start_new_gp
rsp->gp_num ++;
rnp->gp_num = rsp->gp_num;
rnp->gp_completed = rsp->gp_completed;
(here rsp->gp_completed + 1 = rsp->gp_num)

for CPUA
sched_..
rdp->passed_quiesc_completed = rdp->gp_num –;
notice_new_period:
rdp->gp_num = rnp->gp_num;

RCU的整体描述(假设只有3个CPU):
(1). CPU1 调用了synchronize_sched, 该函数会把对应的callback加入到CPU1对应的rdp->nxttail[RCU_NEXT_AVAIL] 中, 并CPU1运行的进程会wait_completitionCPU1对应的进行睡眠. CPU1现在需要等待的是CPU2/3 发生一次调度. 假设当前没有启动任何的gp, 那么会调用rcu_start_gp开始新的gp, rsp->gpnum++, 并且更新CPU1/2/3对应的rnp的内容(如下面函数), 这里可以看到rsp->gpnum会被同步到rnp->gpnum, rsp->completed 会被同步到rnp->completed, 这样需要注意更新时是拿着rnp->lock的.

 766         rcu_for_each_node_breadth_first(rsp, rnp) {                                                                            
 767                 raw_spin_lock(&amp;rnp-&gt;lock);      /* irqs already disabled. */                                                    
 768                 rcu_preempt_check_blocked_tasks(rnp);                                                                          
 769                 rnp-&gt;qsmask = rnp-&gt;qsmaskinit;                                                                                  
 770                 rnp-&gt;gpnum = rsp-&gt;gpnum;                                                                                        
 771                 rnp-&gt;completed = rsp-&gt;completed;                                                                                
 772                 if (rnp == rdp-&gt;mynode)                                                                                        
 773                         rcu_start_gp_per_cpu(rsp, rnp, rdp);                                                                    
 774                 raw_spin_unlock(&amp;rnp-&gt;lock);    /* irqs remain disabled. */                                                    
 775         }

(2). CPU2 这个情况下发生了一次调度, 在发生schedule中会调用rcu_sched_qs. 并且

 102 void rcu_sched_qs(int cpu)
 103 {              
 104         struct rcu_data *rdp;
 105                        
 106         rdp = &amp;per_cpu(rcu_sched_data, cpu);
 107         rdp-&gt;passed_quiesc_completed = rdp-&gt;gpnum - 1;
 108         barrier();
 109         rdp-&gt;passed_quiesc = 1;
 110         rcu_preempt_note_context_switch(cpu);
 111 }

然后在每次update_process_times (hrtime的调用函数) 中会调用rcu_check_callbacks, 在上面的函数中会调用raise_softirq(RCU_SOFTIRQ); 最终会调用RCU_SOFTIRQ对应的处理函数rcu_process_callbacks.

1308 __rcu_process_callbacks(struct rcu_state *rsp, struct rcu_data *rdp)
1309 {
1310         unsigned long flags;
1311
1312         WARN_ON_ONCE(rdp-&gt;beenonline == 0);
1313
1314         /*
1315          * If an RCU GP has gone long enough, go check for dyntick
1316          * idle CPUs and, if needed, send resched IPIs.
1317          */
1318         if (ULONG_CMP_LT(ACCESS_ONCE(rsp-&gt;jiffies_force_qs), jiffies))
1319                 force_quiescent_state(rsp, 1);
1320        
1321         /*
1322          * Advance callbacks in response to end of earlier grace
1323          * period that some other CPU ended.
1324          */
1325         rcu_process_gp_end(rsp, rdp);
1326
1327         /* Update RCU state based on any recent quiescent states. */
1328         rcu_check_quiescent_state(rsp, rdp);
1329
1330         /* Does this CPU require a not-yet-started grace period? */
1331         if (cpu_needs_another_gp(rsp, rdp)) {
1332                 raw_spin_lock_irqsave(&amp;rcu_get_root(rsp)-&gt;lock, flags);
1333                 rcu_start_gp(rsp, flags);  /* releases above lock */
1334         }
1335
1336         /* If there are callbacks ready, invoke them. */
1337         rcu_do_batch(rsp, rdp);
1338 }

这里简单假设CPU2上没有callback, 那么最重要的是rcu_check_quiescent_state, 这个函数会依次向上面report rdp->passed_quiesc_completed. 以为当前有3个CPU. 那么实际rsp下面最后一层的rnp 是有3个rnp. 当前假设只有CPU1/CPU2完成了一次调度.也就是当前3个CPU都完成了一次调度, 有当所有的3个rnp都report 给rsp自己已经完成了一个调度后, 并且对应的passed_quiesc_completed都等于rnp->completed,( 这个很重要, 如果在一个CPUA report之间, 发生了其他CPUB开始了新的gp, 简单情况下每个rnp->completed都会被更新到新值, 如果report期间看到了rnp->completed 和rdp->passed_quises_completed不一样的话, 说明确实出现了上面的情况, 那么不需要向上面report)(前面提到了start_gp的时候会把rnp->completed = rsp->completed. 而我们这里可以认为rnp->completed 代表的是下一次需要completed的值).

791 static void rcu_report_qs_rsp(struct rcu_state *rsp, unsigned long flags)
 792         __releases(rcu_get_root(rsp)-&gt;lock)
 793 {
 794         WARN_ON_ONCE(!rcu_gp_in_progress(rsp));
 795         rsp-&gt;completed = rsp-&gt;gpnum;
 796         rsp-&gt;signaled = RCU_GP_IDLE;
 797         rcu_start_gp(rsp, flags);  /* releases root node's rnp-&gt;lock. */
 798 }

(3) CPU3 完成了调度, 所有的CPU都report了自己完成了一次调度, 那么在rcu_report_qs_rsp会完成rsp->completed = rsp->gpnum. 这里应该注意出现rsp->completed 只在这里更新. 然后会调用rcu_start_gp 看是否需要在次启动一个另外一个gp.

发表评论