Linux RCU和双链表

I'm reading about Read-copy-update (RCU). I'm not sure if I understood it correctly in case of SMP. As far as I know RCU ensures that Update is executed atomically. In case for example single linked list it is obvious that exchanging old element with the new one can be done in one operation, because it is done by changing pointer. But how to ensure that RCU will still be atomically executed in case of doubly-linked list? There are two pointers points to given element (next and prev), so every change on this element needs to change those two pointers. How to ensure that changing those two pointers will be done as atomic operation? How it is done in Linux?

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

1 个解决方案

#1

I was asking myself the same question, and a quick search brought a reply to a comment, extracted from an introduction article to RCU by Paul McKenney (who, from what I gather, is one of the multiple concurrent inventors of the ideas behind RCU).

我问自己同样的问题，快速搜索回复了一条评论，摘自Paul McKenney从RCU的介绍性文章中摘录（我收集的是RCU背后的多个同时发明者之一）。

The question:

问题是：

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?

第二个，后面一个怎么样？如果不支持原子双指针更新，那么如何执行p-> prev-> next = q和p-> next-> prev = q更新而不会让客户看到双向链表的不一致视图？或者这在实践中不是问题？

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

谢谢你的文章。期待下一期！

The answer:

答案：

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.

很高兴你喜欢这篇文章，谢谢你提出的优秀问题！我可以给出任意数量的答案，包括：在生产系统中，琐碎的技术是一件非常好的事情。给我看一个例子，它可以在RCU保护下遍历 - > prev指针。鉴于几个这样的例子，我们可以找出最好的支持方式。一致性被严重高估。（虽然不是每个人都同意我的意思！）即使使用原子双指针更新，也要考虑以下事件序列：（1）任务1执行p = p-> next（2）任务2在两者之间插入一个新元素两个任务1刚刚处理（3）任务1确实p = p-> prev并且无法在它开始的地方结束！即使是双指针原子更新也无法消除不一致！ ;-)如果您需要一致性，请使用锁。鉴于上面的例子，我们可以通过简单地按顺序分配指针来支持等同于双指针原子更新的一致性级别 - 例如，只需从list_del_rcu（）中删除prev-pointer中毒。但这样做会牺牲捕获指针中毒当前捕获的那些错误的能力。

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保护遍历链接列表，但我们需要在实现它之前看到对此的迫切需求。

So basically, Linux "disallows" backwards traversal in both directions when doing RCU. As mentioned in the comment, you could use some newer hardware mechanisms like Double Compare And Swap, but they're not available everywhere, and as mentioned, you can still get memory consistency issues.

所以基本上，当做RCU时，Linux“禁止”在两个方向上向后遍历。正如评论中所提到的，您可以使用一些较新的硬件机制，如Double Compare和Swap，但它们并不是随处可用，如上所述，您仍然可以获得内存一致性问题。

1 个解决方案

#1

更多相关文章

随机推荐