lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Date: Mon, 28 Dec 2009 09:00:47 +0900 From: KAMEZAWA Hiroyuki <kamezawa.hiroyu@...fujitsu.com> To: Peter Zijlstra <peterz@...radead.org> Cc: "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>, "linux-mm@...ck.org" <linux-mm@...ck.org>, "minchan.kim@...il.com" <minchan.kim@...il.com>, cl@...ux-foundation.org Subject: Re: [RFC PATCH] asynchronous page fault. On Sun, 27 Dec 2009 12:19:56 +0100 Peter Zijlstra <peterz@...radead.org> wrote: > 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. > Ok, I'll remove all. Thanks, -Kame -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists