[PATCH] rbtree: stop iteration early in rb_find_first

[PATCH] rbtree: stop iteration early in rb_find_first

[Li RongQing]

stop iteration if match is not NULL and result of cmp is
not zero, this means the matched node has been found, and
the node with same key has been passed

Signed-off-by: Li RongQing <lirongqing@baidu.com>
---
 include/linux/rbtree.h | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index d31ecaf4fdd3..2689771df9bb 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -324,6 +324,9 @@ rb_find_first(const void *key, const struct rb_root *tree,
 		} else if (c > 0) {
 			node = node->rb_right;
 		}
+
+		if (match && c)
+			break;
 	}
 
 	return match;
-- 
2.33.0.69.gc420321.dirty

Re: [PATCH] rbtree: stop iteration early in rb_find_first

[Peter Zijlstra]

On Wed, Aug 25, 2021 at 05:59:48PM +0800, Li RongQing wrote:
> stop iteration if match is not NULL and result of cmp is
> not zero, this means the matched node has been found, and
> the node with same key has been passed
> 
> Signed-off-by: Li RongQing <lirongqing@baidu.com>
> ---
>  include/linux/rbtree.h | 3 +++
>  1 file changed, 3 insertions(+)
> 
> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> index d31ecaf4fdd3..2689771df9bb 100644
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -324,6 +324,9 @@ rb_find_first(const void *key, const struct rb_root *tree,
>  		} else if (c > 0) {
>  			node = node->rb_right;
>  		}
> +
> +		if (match && c)
> +			break;
>  	}
>  
>  	return match;

Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>

Re: [PATCH] rbtree: stop iteration early in rb_find_first

[Michel Lespinasse]

On Wed, Aug 25, 2021 at 01:39:26PM +0200, Peter Zijlstra wrote:
> On Wed, Aug 25, 2021 at 05:59:48PM +0800, Li RongQing wrote:
> > stop iteration if match is not NULL and result of cmp is
> > not zero, this means the matched node has been found, and
> > the node with same key has been passed
> > 
> > Signed-off-by: Li RongQing <lirongqing@baidu.com>
> > ---
> >  include/linux/rbtree.h | 3 +++
> >  1 file changed, 3 insertions(+)
> > 
> > diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> > index d31ecaf4fdd3..2689771df9bb 100644
> > --- a/include/linux/rbtree.h
> > +++ b/include/linux/rbtree.h
> > @@ -324,6 +324,9 @@ rb_find_first(const void *key, const struct rb_root *tree,
> >  		} else if (c > 0) {
> >  			node = node->rb_right;
> >  		}
> > +
> > +		if (match && c)
> > +			break;
> >  	}
> >  
> >  	return match;
> 
> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>

NAK. This looked slightly wrong before, and is more wrong after.

Before:
there was this weird condition  if (c <= 0) {} else if (c > 0) {} ,
making you wonder what the third possibility may be. Easy fix would be
to remove the second condition.

After:
say the key is equal the root, so the code sets match=root and goes left.
Then it stops searching because match is set and c<0.
This doesn't work, the code needs to keep searching for the leftmost match.

--
Michel "walken" Lespinasse

Re: [PATCH] rbtree: stop iteration early in rb_find_first

[Michel Lespinasse]

On Wed, Aug 25, 2021 at 04:53:32AM -0700, Michel Lespinasse wrote:
> On Wed, Aug 25, 2021 at 01:39:26PM +0200, Peter Zijlstra wrote:
> > On Wed, Aug 25, 2021 at 05:59:48PM +0800, Li RongQing wrote:
> > > stop iteration if match is not NULL and result of cmp is
> > > not zero, this means the matched node has been found, and
> > > the node with same key has been passed
> > > 
> > > Signed-off-by: Li RongQing <lirongqing@baidu.com>
> > > ---
> > >  include/linux/rbtree.h | 3 +++
> > >  1 file changed, 3 insertions(+)
> > > 
> > > diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> > > index d31ecaf4fdd3..2689771df9bb 100644
> > > --- a/include/linux/rbtree.h
> > > +++ b/include/linux/rbtree.h
> > > @@ -324,6 +324,9 @@ rb_find_first(const void *key, const struct rb_root *tree,
> > >  		} else if (c > 0) {
> > >  			node = node->rb_right;
> > >  		}
> > > +
> > > +		if (match && c)
> > > +			break;
> > >  	}
> > >  
> > >  	return match;
> > 
> > Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> 
> NAK. This looked slightly wrong before, and is more wrong after.
> 
> Before:
> there was this weird condition  if (c <= 0) {} else if (c > 0) {} ,
> making you wonder what the third possibility may be. Easy fix would be
> to remove the second condition.
> 
> After:
> say the key is equal the root, so the code sets match=root and goes left.
> Then it stops searching because match is set and c<0.
> This doesn't work, the code needs to keep searching for the leftmost match.

Actually, my explanation is wrong too :) but so is the code.
A failing example would searching 10 in the following tree


                        10
		       /
		      5
		       \
		        10

The search would stop after visiting node 5, and miss the leaf which
is the expected node to be returned.

Re: [PATCH] rbtree: stop iteration early in rb_find_first

[Peter Zijlstra]

On Wed, Aug 25, 2021 at 04:53:32AM -0700, Michel Lespinasse wrote:
> On Wed, Aug 25, 2021 at 01:39:26PM +0200, Peter Zijlstra wrote:
> > On Wed, Aug 25, 2021 at 05:59:48PM +0800, Li RongQing wrote:
> > > stop iteration if match is not NULL and result of cmp is
> > > not zero, this means the matched node has been found, and
> > > the node with same key has been passed
> > > 
> > > Signed-off-by: Li RongQing <lirongqing@baidu.com>
> > > ---
> > >  include/linux/rbtree.h | 3 +++
> > >  1 file changed, 3 insertions(+)
> > > 
> > > diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> > > index d31ecaf4fdd3..2689771df9bb 100644
> > > --- a/include/linux/rbtree.h
> > > +++ b/include/linux/rbtree.h
> > > @@ -324,6 +324,9 @@ rb_find_first(const void *key, const struct rb_root *tree,
> > >  		} else if (c > 0) {
> > >  			node = node->rb_right;
> > >  		}
> > > +
> > > +		if (match && c)
> > > +			break;
> > >  	}
> > >  
> > >  	return match;
> > 
> > Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> 
> NAK. This looked slightly wrong before, and is more wrong after.
> 
> Before:
> there was this weird condition  if (c <= 0) {} else if (c > 0) {} ,
> making you wonder what the third possibility may be. Easy fix would be
> to remove the second condition.
> 
> After:
> say the key is equal the root, so the code sets match=root and goes left.
> Then it stops searching because match is set and c<0.
> This doesn't work, the code needs to keep searching for the leftmost match.

I'm not following you. If c!=0 the key didn't match. If c<0 the key is
less than the one we're looking for, meaning we've already found the
left-most matching key, idem for c>0.

More specifically, can you draw me a (binary) tree with elements: A B B
B C, such that a search for B might have match set, hit c!=1 and not
have found the leftmost B ?

Re: [PATCH] rbtree: stop iteration early in rb_find_first

[Peter Zijlstra]

On Wed, Aug 25, 2021 at 04:58:59AM -0700, Michel Lespinasse wrote:
> Actually, my explanation is wrong too :) but so is the code.
> A failing example would searching 10 in the following tree
> 
> 
>                       10
> 		       /
> 		      5
> 		       \
> 		        10
> 
> The search would stop after visiting node 5, and miss the leaf which
> is the expected node to be returned.

Ah! You're quite right.

Re: [PATCH] rbtree: stop iteration early in rb_find_first

[Peter Zijlstra]

On Wed, Aug 25, 2021 at 02:29:19PM +0200, Peter Zijlstra wrote:
> More specifically, can you draw me a (binary) tree with elements: A B B
> B C, such that a search for B might have match set, hit c!=1 and not
> have found the leftmost B ?

We crossed emails, you just did :-)

Re: [PATCH] rbtree: stop iteration early in rb_find_first

[Peter Zijlstra]

On Wed, Aug 25, 2021 at 04:58:59AM -0700, Michel Lespinasse wrote:
> > NAK. This looked slightly wrong before, and is more wrong after.

> Actually, my explanation is wrong too :) but so is the code.
> A failing example would searching 10 in the following tree
> 
> 
>                         10
> 		       /
> 		      5
> 		       \
> 		        10
> 
> The search would stop after visiting node 5, and miss the leaf which
> is the expected node to be returned.

Just to clarify; the current code *does* work here. The proposed patch
breaks it.

答复: [PATCH] rbtree: stop iteration early in rb_find_first

[Li,Rongqing]

>> 
>>  
>>                          10
>>                        /
>>                       5
>>                        \
>>                         10
>>  
>> The search would stop after visiting node 5, and miss the leaf which
>> is the expected node to be returned.

 thanks for explanation.

> Just to clarify; the current code *does* work here. The proposed patch
> breaks it.

true, my patch is wrong.

but rb_find_first seems have other issue.  when the key is equal, we should search right leaf, not left leaf
rb_find_first should like below

	while (node) {
		int c = cmp(key, node);

		if (c < 0) {
			node = node->rb_left;
		} else {
			if (!c)
				match = node;
			node = node->rb_right;
		}
	}
 
since the node  is inserted to right when the key is equal, see rb_add()

 -Li

Re: 答复: [PATCH] rbtree: stop iteration early in rb_find_first

[Peter Zijlstra]

On Wed, Aug 25, 2021 at 04:01:53PM +0000, Li,Rongqing wrote:
> 
> >>
> >>
> >>                         10
> >>                       /
> >>                      5
> >>                       \
> >>                        10
> >>
> >> The search would stop after visiting node 5, and miss the leaf which
> >> is the expected node to be returned.
> 
> thanks for explanation.
> 
> >Just to clarify; the current code *does* work here. The proposed patch
> >breaks it.
> 
> 
> true, my patch is wrong.
> 
> but rb_find_first seems have other issue.  when the key is equal, we should search right leaf, not left leaf

That again breaks the above case.

答复: 答复: [PATCH] rbtree: stop iteration early in rb_find_first

[Li,Rongqing]

    
On Wed, Aug 25, 2021 at 04:01:53PM +0000, Li,Rongqing wrote:
> 
> >>
> >>
> >>                         10
> >>                       /
> >>                      5
> >>                       \
> >>                        10

>That again breaks the above case.

                       10
                     /
                    5
                       \
                      10

the above case should not exist. like below, when second 10 is inserted, it should be inserted to right leaf
                       10
                     /
                    5

as a result, it should be

                       10
                     /     \
                    5      10

since 10 is not less 10, so new 10 is inserted to right.
and it depends on 
bool (*less)(struct rb_node *, const struct rb_node *) which not return true when equal

this case should be ok
                       10
                           \
                           12
                            /
                          10

-Li







    

Re: 答复: 答复: [PATCH] rbtree: stop iteration early in rb_find_first

[Peter Zijlstra]

On Wed, Aug 25, 2021 at 06:26:59PM +0000, Li,Rongqing wrote:
> 
>                        10
>                      /
>                     5
>                        \
>                       10
> 
> the above case should not exist. like below, when second 10 is inserted, it should be inserted to right leaf
>                        10
>                      /
>                     5
> 
> as a result, it should be
> 
>                        10
>                      /     \
>                     5      10
> 
> since 10 is not less 10, so new 10 is inserted to right.

You're right that rb_add() does a tail-add for elements it considers
equal -- there is actually code in the tree that relies on this.

But that doesn't mean rb_find_first() should go right, it *must*not*,
because then it wouldn't find the 'first' aka 'leftmost' instance of the
equal elements.

Also, you're only considering building the tree in-order with rb_add(),
trees get modified all the time and the pattern Michel gave is perfectly
valid (also see rb_prev()).

Sure the snippet is not a balanced tree, but you can construct the
pattern as part of a larger tree just fine, just add some elements:


	 10(b)
	/  \
       5   10(c)
        \
	10(a)

is a tree that is balanced (remember, RB trees only require the left and
right depths to no more than double -- as opposed to AVL trees, which
have a tighter constraint). This tree has order: 5, 10(a), 10(b), 10(c).
Also note that the tree rotations are stable -- they must be since they
do not refence the order function.

As such, if we rb_find_first() for 10, we must find 10(a), the leftmost
10 in the tree.

答复: 答复: 答复: [PATCH] rbtree: stop iteration early in rb_find_first

[Li,Rongqing]

> You're right that rb_add() does a tail-add for elements it considers equal -- there
> is actually code in the tree that relies on this.
> 
> But that doesn't mean rb_find_first() should go right, it *must*not*, because
> then it wouldn't find the 'first' aka 'leftmost' instance of the equal elements.
> 
> Also, you're only considering building the tree in-order with rb_add(), trees get
> modified all the time and the pattern Michel gave is perfectly valid (also see
> rb_prev()).
> 
> Sure the snippet is not a balanced tree, but you can construct the pattern as
> part of a larger tree just fine, just add some elements:
> 
> 
> 	 10(b)
> 	/  \
>        5   10(c)
>         \
> 	10(a)
> 
> is a tree that is balanced (remember, RB trees only require the left and right
> depths to no more than double -- as opposed to AVL trees, which have a tighter
> constraint). This tree has order: 5, 10(a), 10(b), 10(c).
> Also note that the tree rotations are stable -- they must be since they do not
> refence the order function.
> 
> As such, if we rb_find_first() for 10, we must find 10(a), the leftmost
> 10 in the tree.

I see, Thanks for the explanation. Sorry for the noise.

-Li