Messages in this thread | | | Subject | Re: [RFC PATCH] asynchronous page fault. | From | Peter Zijlstra <> | Date | Sun, 27 Dec 2009 12:19:56 +0100 |
| |
On Fri, 2009-12-25 at 10:51 +0900, KAMEZAWA Hiroyuki wrote: > Index: linux-2.6.33-rc2/lib/rbtree.c > =================================================================== > --- linux-2.6.33-rc2.orig/lib/rbtree.c > +++ linux-2.6.33-rc2/lib/rbtree.c > @@ -30,19 +30,19 @@ static void __rb_rotate_left(struct rb_n > > if ((node->rb_right = right->rb_left)) > rb_set_parent(right->rb_left, node); > - right->rb_left = node; > + rcu_assign_pointer(right->rb_left, node); > > rb_set_parent(right, parent); > > if (parent) > { > if (node == parent->rb_left) > - parent->rb_left = right; > + rcu_assign_pointer(parent->rb_left, right); > else > - parent->rb_right = right; > + rcu_assign_pointer(parent->rb_right, right); > } > else > - root->rb_node = right; > + rcu_assign_pointer(root->rb_node, right); > rb_set_parent(node, right); > } > > @@ -53,19 +53,19 @@ static void __rb_rotate_right(struct rb_ > > if ((node->rb_left = left->rb_right)) > rb_set_parent(left->rb_right, node); > - left->rb_right = node; > + rcu_assign_pointer(left->rb_right, node); > > rb_set_parent(left, parent); > > if (parent) > { > if (node == parent->rb_right) > - parent->rb_right = left; > + rcu_assign_pointer(parent->rb_right, left); > else > - parent->rb_left = left; > + rcu_assign_pointer(parent->rb_left, left); > } > else > - root->rb_node = left; > + rcu_assign_pointer(root->rb_node, left); > rb_set_parent(node, left); > }
Consider the tree rotation:
Q P / \ / \ P C A Q / \ / \ A B B C
Since this comprises of 3 assignments (assuming right rotation):
Q.left = B P.right = Q parent = P
it is non-atomic. This in turn means that any lock-less decent into the tree will be able to miss a whole subtree or worse (imagine us being at Q, needing to go to A, then the rotation happens, and all we can choose from is B or C).
Your changelog states as much.
"Even if RB-tree rotation occurs while we walk tree for look-up, we just miss vma without oops."
However, since this is the case, do we still need the rcu_assign_pointer() conversion your patch does? All I can see it do is slow down all RB-tree users, without any gain.
| |