關于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.
即，不允許同時修改，所以最多l(xiāng)ist有兩個版本存在。（<------ 樓主可能是沒注意這句話）
并且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. }

復制代碼

答案跟正文的區(qū)別在于，lock的范圍不一樣（并且一個是spin一個是mutex）。
這樣在多核環(huán)境下，正文的代碼，一個cpu刪除一個節(jié)點后，其它cpu之后等到其完成synchronize之后才能刪除，所以list最多兩個版本（一個是帶被刪除節(jié)點的，一個是不帶被刪除節(jié)點的）；
而Quiz#4中，一個cpu刪除后其它cpu可以立刻刪除，大家都進入synchronize等待狀態(tài)(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時間內(nèi).
我之所以有這種想法是在這篇文章之前有一句:
RCU supports concurrency between a single updater and multiple readers.
我理解成只能有一個synchronize_rcu() 被調(diào)用, 同一個gp周期內(nèi),

現(xiàn)在理解了
信號量那個只有兩個版本, 前提是采用semaphore那種多核更新保護機制時, updater只做了一次更新, 如刪除一個node, .如果semaphore保護周期內(nèi)做了多次修改, 依然會有很多個rcu version list.

再次感謝nswcfd!

   

nswcfd

回復 3# firocu

Paul關于RCU的一系列文章見解非常深刻，在Quiz Q&A里對這些同步原語的剖析細致到了“令人發(fā)指”的地步，
很多我也不是很理解，借助cu這個平臺，大家一起分享討論吧。

lwn.net/Kernel/Index/#Read-copy-update
已經(jīng)演進了10年了~~~


   

firocu

回復 4# nswcfd


lse.sourceforge.net/locking/rcupdate.html
貌似是舊官網(wǎng)