All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH 1/2] rbtree_latch: quit searching when reaching to maximum depth
@ 2020-05-15 12:47 Lai Jiangshan
  2020-05-15 12:47 ` [PATCH 2/2] rbtree_latch: don't need to check seq when it found a node Lai Jiangshan
                   ` (2 more replies)
  0 siblings, 3 replies; 13+ messages in thread
From: Lai Jiangshan @ 2020-05-15 12:47 UTC (permalink / raw)
  To: linux-kernel
  Cc: Lai Jiangshan, Peter Zijlstra, Paul E . McKenney, Oleg Nesterov,
	Michel Lespinasse, Andrea Arcangeli, David Woodhouse,
	Rik van Riel, Mathieu Desnoyers

lib/rbtree.c has ensured that there is not possible to
inadvertently cause (temporary) loops in the tree structure
as seen in program order of the modifier. But loop is still
possible to be seen in searcher due to CPU's reordering.

for example:
modifier				searcher

left rotate at parent
parent->rb_right is node
					search to parent
					parent->rb_right is node
				     +->see node->rb_left changed
WRITE_ONCE(parent->rb_right, tmp);-+ |  node->rb_left is parennt
no smp_wmb(), some arch can        | |
reorder these two writes           | |  loop long between
WRITE_ONCE(node->rb_left, parent);-+-+  parent and node
				   |
				   +--->finally see
					parent->rb_right

The long loop won't stop until the modifer's CPU flushes
its writes. Too avoid it, we should limit the searching depth.
There are no more than (1<<BITS_PER_LONG)-1 nodes in the tree.
And the max_depth of a tree is no more than 2*lg(node_count+1),
which is no mare than 2*BITS_PER_LONG.

So the serarch should stop when diving down up to
2*BITS_PER_LONG depth.

Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Paul E. McKenney <paulmck@kernel.org>
Cc: Oleg Nesterov <oleg@redhat.com>
Cc: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <David.Woodhouse@intel.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Lai Jiangshan <laijs@linux.alibaba.com>
---
 include/linux/rbtree_latch.h | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/include/linux/rbtree_latch.h b/include/linux/rbtree_latch.h
index 7d012faa509a..b012bd95eabf 100644
--- a/include/linux/rbtree_latch.h
+++ b/include/linux/rbtree_latch.h
@@ -107,10 +107,11 @@ __lt_find(void *key, struct latch_tree_root *ltr, int idx,
 	  int (*comp)(void *key, struct latch_tree_node *node))
 {
 	struct rb_node *node = rcu_dereference_raw(ltr->tree[idx].rb_node);
+	int depth = 2 * BITS_PER_LONG;
 	struct latch_tree_node *ltn;
 	int c;
 
-	while (node) {
+	while (node && depth > 0) {
 		ltn = __lt_from_rb(node, idx);
 		c = comp(key, ltn);
 
@@ -120,6 +121,7 @@ __lt_find(void *key, struct latch_tree_root *ltr, int idx,
 			node = rcu_dereference_raw(node->rb_right);
 		else
 			return ltn;
+		depth--;
 	}
 
 	return NULL;
-- 
2.20.1


^ permalink raw reply related	[flat|nested] 13+ messages in thread

end of thread, other threads:[~2020-05-23  0:56 UTC | newest]

Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-05-15 12:47 [PATCH 1/2] rbtree_latch: quit searching when reaching to maximum depth Lai Jiangshan
2020-05-15 12:47 ` [PATCH 2/2] rbtree_latch: don't need to check seq when it found a node Lai Jiangshan
2020-05-15 13:04   ` Peter Zijlstra
2020-05-15 13:00 ` [PATCH 1/2] rbtree_latch: quit searching when reaching to maximum depth Peter Zijlstra
2020-05-15 14:39   ` Lai Jiangshan
2020-05-15 15:01     ` Peter Zijlstra
2020-05-15 15:59       ` [PATCH V2 " Lai Jiangshan
2020-05-15 15:59         ` [PATCH V2 2/2] rbtree_latch: don't need to check seq when it found a node Lai Jiangshan
2020-05-16  4:27           ` Michel Lespinasse
2020-05-16  4:52             ` Lai Jiangshan
2020-05-16  5:03               ` Michel Lespinasse
2020-05-23  0:56         ` [PATCH V2 1/2] rbtree_latch: quit searching when reaching to maximum depth Lai Jiangshan
2020-05-15 13:14 ` [PATCH " Mathieu Desnoyers

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.