c - Linux RCU 和双链表

Question

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

Answer 1

我问自己同样的问题，快速搜索得到了对评论的回复，该评论摘自Paul McKenney对 RCU 的介绍文章（据我所知，他是 RCU 背后想法的多个并发发明者之一） .

问题：

我想知道示例中省略反向链接是否是一件好事。遗漏使这项技术变得微不足道，因为发布只涉及一个替换一个指针。

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

不过，谢谢你的文章。期待下一期！

答案：

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

因此，很可能会有一段时间，Linux 内核允许 RCU 保护的链表双向遍历，但我们需要在实现它之前看到对此的迫切需求。

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