Linux RCU和双链接列表

Question

我在读关于阅读-复制-更新(RCU)的书。我不确定我是否正确地理解了它，以防SMP。据我所知，RCU确保自动执行Update。例如，在单链列表中，很明显，与新元素交换旧元素可以在一个操作中完成，因为它是通过更改指针来完成的。但是，如何确保在出现双链接列表的情况下，RCU仍将被原子地执行？有两个指向给定元素的指针(next和prev)，因此该元素上的每一个更改都需要更改这两个指针。如何确保将这两个指针更改为原子操作？它是如何在Linux中完成的？

Answer 1

我问自己同样的问题，然后快速搜索了对评论的答复，这是Paul从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-指针中毒。但这样做将牺牲捕捉指针中毒目前捕获的错误的能力。 因此，Linux内核很可能会允许RCU保护的双向遍历链接列表，但在实现它之前，我们需要看到这方面的迫切需求。

因此，基本上，Linux在执行RCU时“不允许”双向反向遍历。正如注释中提到的那样，您可以使用一些较新的硬件机制，比如双比较与互换，但是它们并不是随处可见的，而且正如前面提到的，您仍然会遇到内存一致性问题。