Backlinks [LWN.net]

Backlinks

Posted Dec 28, 2007 12:37 UTC (Fri) by mmutz (guest, #5642)
Parent article: What is RCU, Fundamentally?

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!

to post comments

Backlinks

Posted Dec 28, 2007 15:35 UTC (Fri) by PaulMcKenney (✭ supporter ✭, #9624) [Link]

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.