latch_tree_find() should be protected by caller via RCU or so.
When it find a node in an attempt, the node must be a valid one
in RCU's point's of view even the tree is (being) updated with a
new node with the same key which is entirely subject to timing
anyway.
Cc: Paul E. McKenney <[email protected]>
Cc: Oleg Nesterov <[email protected]>
Cc: Michel Lespinasse <[email protected]>
Cc: Andrea Arcangeli <[email protected]>
Cc: Rik van Riel <[email protected]>
Cc: Mathieu Desnoyers <[email protected]>
Acked-by: Peter Zijlstra (Intel) <[email protected]>
Signed-off-by: Lai Jiangshan <[email protected]>
---
include/linux/rbtree_latch.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/include/linux/rbtree_latch.h b/include/linux/rbtree_latch.h
index 638942f53c0a..affc4b026d9b 100644
--- a/include/linux/rbtree_latch.h
+++ b/include/linux/rbtree_latch.h
@@ -245,7 +245,7 @@ latch_tree_find(void *key, struct latch_tree_root *root,
do {
seq = raw_read_seqcount_latch(&root->seq);
node = __lt_find(key, root, seq & 1, ops->comp);
- } while (read_seqcount_retry(&root->seq, seq));
+ } while (!node && read_seqcount_retry(&root->seq, seq));
return node;
}
--
2.20.1
On Fri, May 15, 2020 at 03:59:09PM +0000, Lai Jiangshan wrote:
> latch_tree_find() should be protected by caller via RCU or so.
> When it find a node in an attempt, the node must be a valid one
> in RCU's point's of view even the tree is (being) updated with a
> new node with the same key which is entirely subject to timing
> anyway.
I'm not sure I buy this. Even if we get a valid node, is it the one we
were searching for ? I don't see how this could be guaranteed if the
read raced with a tree rebalancing.
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
On Sat, May 16, 2020 at 12:28 PM Michel Lespinasse <[email protected]> wrote:
>
> On Fri, May 15, 2020 at 03:59:09PM +0000, Lai Jiangshan wrote:
> > latch_tree_find() should be protected by caller via RCU or so.
> > When it find a node in an attempt, the node must be a valid one
> > in RCU's point's of view even the tree is (being) updated with a
> > new node with the same key which is entirely subject to timing
> > anyway.
>
> I'm not sure I buy this. Even if we get a valid node, is it the one we
> were searching for ? I don't see how this could be guaranteed if the
> read raced with a tree rebalancing.
It is valid because ops->comp() returns 0 and it should be
the one we were searching for unless ops->comp() is wrong.
The searched one could be possible just deleted, but it is still
a legitimate searched result in RCU's point's of view.
A tree rebalancing can cause a searching fails to find
an existing target. This is the job of read_seqcount_retry()
to tell you to retry.
>
> --
> Michel "Walken" Lespinasse
> A program is never fully debugged until the last user dies.
On Fri, May 15, 2020 at 9:52 PM Lai Jiangshan
<[email protected]> wrote:
>
> On Sat, May 16, 2020 at 12:28 PM Michel Lespinasse <[email protected]> wrote:
> >
> > On Fri, May 15, 2020 at 03:59:09PM +0000, Lai Jiangshan wrote:
> > > latch_tree_find() should be protected by caller via RCU or so.
> > > When it find a node in an attempt, the node must be a valid one
> > > in RCU's point's of view even the tree is (being) updated with a
> > > new node with the same key which is entirely subject to timing
> > > anyway.
> >
> > I'm not sure I buy this. Even if we get a valid node, is it the one we
> > were searching for ? I don't see how this could be guaranteed if the
> > read raced with a tree rebalancing.
>
> It is valid because ops->comp() returns 0 and it should be
> the one we were searching for unless ops->comp() is wrong.
> The searched one could be possible just deleted, but it is still
> a legitimate searched result in RCU's point's of view.
>
> A tree rebalancing can cause a searching fails to find
> an existing target. This is the job of read_seqcount_retry()
> to tell you to retry.
Ah, yes, this is correct. It wouldn't work if we wanted to return the
next higher key for example, but it does work for exact matches. Nice!
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.