关于rcu的问题

firocu

我在Paul的RCU文章, What is RCU, Fundamentally?
关于文中给出的问题, 百思不得其解, 实际上是没看懂答案:
Quick Quiz 5: How many RCU versions of a given list can be active at any given time?

Answer: That depends on the synchronization design. If a semaphore protecting the update is held across the grace period, then there can be at most two versions, the old and the new.

However, if only the search, the update, and the list_replace_rcu() were protected by a lock, then there could be an arbitrary number of versions active, limited only by memory and by how many updates could be completed within a grace period. But please note that data structures that are updated so frequently probably are not good candidates for RCU. That said, RCU can handle high update rates when necessary.

我认为, list可以任意多个. 不太理解semaphore带来的影响, 为什么只有两个?

nswcfd

Quiz#5是紧跟着Quiz#4来的。

Quiz#4，How would you modify the deletion example to permit more than two versions of the list to be active?
这个问题又是针对正文中的删除算法提出的。

正文的算法，example 1，是这样的

1.   1 p = search(head, key);
   
2.   2 if (p != NULL) {
   
3.   3   list_del_rcu(&p->list);
   
4.   4   synchronize_rcu();
   
5.   5   kfree(p);
   
6.   6 }

复制代码

Quiz#4前有段话，These examples assumed that a mutex was held across the entire update operation, which would mean that there could be at most two versions of the list active at a given time.
即，不允许同时修改，所以最多list有两个版本存在。（<------ 楼主可能是没注意这句话）
并且synchronzie_rcu是包含在这个mutex里的，即Quiz#5里提到的，“... a semaphore protecting the update is held across the grace period”（mutex跨越了grace period）

Quiz#4的（一种）答案是

1. spin_lock(&mylock);
   
2. p = search(head, key);
   
3. if (p == NULL)
   
4.         spin_unlock(&mylock);
   
5. else {
   
6.         list_del_rcu(&p->list);
   
7.         spin_unlock(&mylock);
   
8.         synchronize_rcu();
   
9.         kfree(p);
   
10. }

复制代码

答案跟正文的区别在于，lock的范围不一样（并且一个是spin一个是mutex）。
这样在多核环境下，正文的代码，一个cpu删除一个节点后，其它cpu之后等到其完成synchronize之后才能删除，所以list最多两个版本（一个是带被删除节点的，一个是不带被删除节点的）；
而Quiz#4中，一个cpu删除后其它cpu可以立刻删除，大家都进入synchronize等待状态(multiple concurrent deletions might be waiting in synchronize_rcu())；对于reader而言，list就会有多个版本（原始版本、cpu1删除后的版本、cpu2删除后的版本……）。

这其实跟Quiz#5传递的信息是一致的。
Quiz#5答案的第二段应该说的就是Quiz#4的情况（略有不同，一个是update，一个是delete）。

firocu

回复 2# nswcfd
感谢nswcfd, 细致令人信服的答案.
我没能理解的根源是, 我认为只有一个核在修改, 这个核可以修改任意多次在gp时间内.
我之所以有这种想法是在这篇文章之前有一句:
RCU supports concurrency between a single updater and multiple readers.
我理解成只能有一个synchronize_rcu() 被调用, 同一个gp周期内,

现在理解了
信号量那个只有两个版本, 前提是采用semaphore那种多核更新保护机制时, updater只做了一次更新, 如删除一个node, .如果semaphore保护周期内做了多次修改, 依然会有很多个rcu version list.

再次感谢nswcfd!

   

nswcfd

回复 3# firocu

Paul关于RCU的一系列文章见解非常深刻，在Quiz Q&A里对这些同步原语的剖析细致到了“令人发指”的地步，
很多我也不是很理解，借助cu这个平台，大家一起分享讨论吧。

lwn.net/Kernel/Index/#Read-copy-update
已经演进了10年了~~~


   

firocu

回复 4# nswcfd


lse.sourceforge.net/locking/rcupdate.html
貌似是旧官网