Linux RCU and double linked list

Question

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?

Answer 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).

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?

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.

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.

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.