LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
* [PATCH] rbtree: stop iteration early in rb_find_first
@ 2021-08-25  9:59 Li RongQing
  2021-08-25 11:39 ` Peter Zijlstra
  0 siblings, 1 reply; 13+ messages in thread
From: Li RongQing @ 2021-08-25  9:59 UTC (permalink / raw)
  To: peterz, dbueso, mingo, michel, linux-kernel, lirongqing

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


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

* Re: [PATCH] rbtree: stop iteration early in rb_find_first
  2021-08-25  9:59 [PATCH] rbtree: stop iteration early in rb_find_first Li RongQing
@ 2021-08-25 11:39 ` Peter Zijlstra
  2021-08-25 11:53   ` Michel Lespinasse
  0 siblings, 1 reply; 13+ messages in thread
From: Peter Zijlstra @ 2021-08-25 11:39 UTC (permalink / raw)
  To: Li RongQing; +Cc: dbueso, mingo, michel, linux-kernel

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>

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

* Re: [PATCH] rbtree: stop iteration early in rb_find_first
  2021-08-25 11:39 ` Peter Zijlstra
@ 2021-08-25 11:53   ` Michel Lespinasse
  2021-08-25 11:58     ` Michel Lespinasse
  2021-08-25 12:29     ` Peter Zijlstra
  0 siblings, 2 replies; 13+ messages in thread
From: Michel Lespinasse @ 2021-08-25 11:53 UTC (permalink / raw)
  To: Peter Zijlstra; +Cc: Li RongQing, dbueso, mingo, michel, linux-kernel

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

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

* Re: [PATCH] rbtree: stop iteration early in rb_find_first
  2021-08-25 11:53   ` Michel Lespinasse
@ 2021-08-25 11:58     ` Michel Lespinasse
  2021-08-25 12:31       ` Peter Zijlstra
  2021-08-25 13:21       ` Peter Zijlstra
  2021-08-25 12:29     ` Peter Zijlstra
  1 sibling, 2 replies; 13+ messages in thread
From: Michel Lespinasse @ 2021-08-25 11:58 UTC (permalink / raw)
  To: Michel Lespinasse
  Cc: Peter Zijlstra, Li RongQing, dbueso, mingo, linux-kernel

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.

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

* Re: [PATCH] rbtree: stop iteration early in rb_find_first
  2021-08-25 11:53   ` Michel Lespinasse
  2021-08-25 11:58     ` Michel Lespinasse
@ 2021-08-25 12:29     ` Peter Zijlstra
  2021-08-25 12:32       ` Peter Zijlstra
  1 sibling, 1 reply; 13+ messages in thread
From: Peter Zijlstra @ 2021-08-25 12:29 UTC (permalink / raw)
  To: Michel Lespinasse; +Cc: Li RongQing, dbueso, mingo, linux-kernel

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 ?

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

* Re: [PATCH] rbtree: stop iteration early in rb_find_first
  2021-08-25 11:58     ` Michel Lespinasse
@ 2021-08-25 12:31       ` Peter Zijlstra
  2021-08-25 13:21       ` Peter Zijlstra
  1 sibling, 0 replies; 13+ messages in thread
From: Peter Zijlstra @ 2021-08-25 12:31 UTC (permalink / raw)
  To: Michel Lespinasse; +Cc: Li RongQing, dbueso, mingo, linux-kernel

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.

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

* Re: [PATCH] rbtree: stop iteration early in rb_find_first
  2021-08-25 12:29     ` Peter Zijlstra
@ 2021-08-25 12:32       ` Peter Zijlstra
  0 siblings, 0 replies; 13+ messages in thread
From: Peter Zijlstra @ 2021-08-25 12:32 UTC (permalink / raw)
  To: Michel Lespinasse; +Cc: Li RongQing, dbueso, mingo, linux-kernel

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 :-)

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

* Re: [PATCH] rbtree: stop iteration early in rb_find_first
  2021-08-25 11:58     ` Michel Lespinasse
  2021-08-25 12:31       ` Peter Zijlstra
@ 2021-08-25 13:21       ` Peter Zijlstra
  2021-08-25 16:08         ` 答复: " Li,Rongqing
       [not found]         ` <90ea3457ddc7485fbc8db5f7ca5b07ab@baidu.com>
  1 sibling, 2 replies; 13+ messages in thread
From: Peter Zijlstra @ 2021-08-25 13:21 UTC (permalink / raw)
  To: Michel Lespinasse; +Cc: Li RongQing, dbueso, mingo, linux-kernel

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.

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

* 答复: [PATCH] rbtree: stop iteration early in rb_find_first
  2021-08-25 13:21       ` Peter Zijlstra
@ 2021-08-25 16:08         ` Li,Rongqing
       [not found]         ` <90ea3457ddc7485fbc8db5f7ca5b07ab@baidu.com>
  1 sibling, 0 replies; 13+ messages in thread
From: Li,Rongqing @ 2021-08-25 16:08 UTC (permalink / raw)
  To: Peter Zijlstra, Michel Lespinasse; +Cc: dbueso, mingo, linux-kernel



>> 
>>  
>>                          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


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

* Re: 答复: [PATCH] rbtree: stop iteration early in rb_find_first
       [not found]         ` <90ea3457ddc7485fbc8db5f7ca5b07ab@baidu.com>
@ 2021-08-25 17:18           ` Peter Zijlstra
  2021-08-25 18:26             ` 答复: " Li,Rongqing
  0 siblings, 1 reply; 13+ messages in thread
From: Peter Zijlstra @ 2021-08-25 17:18 UTC (permalink / raw)
  To: Li,Rongqing; +Cc: Michel Lespinasse, dbueso, mingo, linux-kernel

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.

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

* 答复: 答复: [PATCH] rbtree: stop iteration early in rb_find_first
  2021-08-25 17:18           ` Peter Zijlstra
@ 2021-08-25 18:26             ` Li,Rongqing
  2021-08-25 19:20               ` Peter Zijlstra
  0 siblings, 1 reply; 13+ messages in thread
From: Li,Rongqing @ 2021-08-25 18:26 UTC (permalink / raw)
  To: Peter Zijlstra; +Cc: Michel Lespinasse, dbueso, mingo, linux-kernel









    
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







    

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

* Re: 答复: 答复: [PATCH] rbtree: stop iteration early in rb_find_first
  2021-08-25 18:26             ` 答复: " Li,Rongqing
@ 2021-08-25 19:20               ` Peter Zijlstra
  2021-08-26  5:03                 ` 答复: " Li,Rongqing
  0 siblings, 1 reply; 13+ messages in thread
From: Peter Zijlstra @ 2021-08-25 19:20 UTC (permalink / raw)
  To: Li,Rongqing; +Cc: Michel Lespinasse, dbueso, mingo, linux-kernel

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.


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

* 答复: 答复: 答复: [PATCH] rbtree: stop iteration early in rb_find_first
  2021-08-25 19:20               ` Peter Zijlstra
@ 2021-08-26  5:03                 ` Li,Rongqing
  0 siblings, 0 replies; 13+ messages in thread
From: Li,Rongqing @ 2021-08-26  5:03 UTC (permalink / raw)
  To: Peter Zijlstra; +Cc: Michel Lespinasse, dbueso, mingo, linux-kernel

> 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

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

end of thread, other threads:[~2021-08-26  5:04 UTC | newest]

Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-08-25  9:59 [PATCH] rbtree: stop iteration early in rb_find_first Li RongQing
2021-08-25 11:39 ` Peter Zijlstra
2021-08-25 11:53   ` Michel Lespinasse
2021-08-25 11:58     ` Michel Lespinasse
2021-08-25 12:31       ` Peter Zijlstra
2021-08-25 13:21       ` Peter Zijlstra
2021-08-25 16:08         ` 答复: " Li,Rongqing
     [not found]         ` <90ea3457ddc7485fbc8db5f7ca5b07ab@baidu.com>
2021-08-25 17:18           ` Peter Zijlstra
2021-08-25 18:26             ` 答复: " Li,Rongqing
2021-08-25 19:20               ` Peter Zijlstra
2021-08-26  5:03                 ` 答复: " Li,Rongqing
2021-08-25 12:29     ` Peter Zijlstra
2021-08-25 12:32       ` Peter Zijlstra

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).