c - Linux RCU 和双向链表

Question

我正在阅读 Read-copy-update (RCU) .对于 SMP，我不确定我是否理解正确。据我所知，RCU 确保更新以原子方式执行。在单链表的例子中，很明显可以在一个操作中完成用新元素交换旧元素，因为它是通过改变指针来完成的。但是如何保证在双向链表的情况下RCU仍然是原子执行的呢？有两个指针指向给定元素(next 和 prev)，因此该元素的每次更改都需要更改这两个指针。如何确保更改这两个指针将作为原子操作完成？在 Linux 中是如何完成的？

Answer 1

我在问自己同样的问题，快速搜索找到了 a reply to a comment , 摘自 an introduction article to RCU作者 Paul McKenney(据我所知，他是 RCU 背后思想的多个并发发明者之一)。

问题:

I'm wondering whether the omission of the backlinks in the examples is a good thing. The omission makes the technique trivial, since publishing only involves one replacing one pointer.

What about the second, back, one? Without support for atomic two-pointer updates, how can both the p->prev->next = q and p->next->prev = q updates be performed without risking clients to see an inconsistent view of the doubly linked list? Or is that not a problem in practice?

Thanks for the article, though. Looking forward to the next installment!

答案:

Glad you liked the article, and thank you for the excellent question! I could give any number of answers, including: In production systems, trivial techniques are a very good thing. Show me an example where it is useful to traverse the ->prev pointers under RCU protection. Given several such examples, we could work out how best to support this. Consistency is grossly overrated. (Not everyone agrees with me on this, though!) Even with atomic two-pointer updates, consider the following sequence of events: (1) task 1 does p=p->next (2) task 2 inserts a new element between the two that task 1 just dealt with (3) task 1 does p=p->prev and fails to end up where it started! Even double-pointer atomic update fails to banish inconsistency! ;-) If you need consistency, use locks. Given the example above, we could support a level of consistency equivalent to the double-pointer atomic update simply by assigning the pointers in sequence -- just remove the prev-pointer poisoning from list_del_rcu(), for example. But doing this would sacrifice the ability to catch those bugs that pointer-poisoning currently catches.

So, there might well come a time when the Linux kernel permits RCU-protected traversal of linked lists in both directions, but we need to see a compelling need for this before implementing it.

所以基本上，Linux 在执行 RCU 时“不允许”在两个方向上向后遍历。如评论中所述，您可以使用一些较新的硬件机制，如 Double Compare And Swap ，但它们并非随处可用，并且如前所述，您仍然会遇到内存一致性问题。