[PATCH] lib/interval_tree: skip the check before go to the right subtree

[PATCH] lib/interval_tree: skip the check before go to the right subtree

[Wei Yang]

The interval_tree_subtree_search() holds the loop invariant:

    start <= node->ITSUBTREE

Let's say we have a following tree:

         node
         /  \
      left  right

So we know node->ITSUBTREE is contributed by one of the following:

  * left->ITSUBTREE
  * ITLAST(node)
  * right->ITSUBTREE

When we come to the right node, we are sure the first two don't
contribute to node->ITSUBTREE and it must be the right node does the
job.

So skip the check before go to the right subtree.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 include/linux/interval_tree_generic.h | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/include/linux/interval_tree_generic.h b/include/linux/interval_tree_generic.h
index aaa8a0767aa3..1b400f26f63d 100644
--- a/include/linux/interval_tree_generic.h
+++ b/include/linux/interval_tree_generic.h
@@ -104,12 +104,8 @@ ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last)	      \
 		if (ITSTART(node) <= last) {		/* Cond1 */	      \
 			if (start <= ITLAST(node))	/* Cond2 */	      \
 				return node;	/* node is leftmost match */  \
-			if (node->ITRB.rb_right) {			      \
-				node = rb_entry(node->ITRB.rb_right,	      \
-						ITSTRUCT, ITRB);	      \
-				if (start <= node->ITSUBTREE)		      \
-					continue;			      \
-			}						      \
+			node = rb_entry(node->ITRB.rb_right, ITSTRUCT, ITRB); \
+			continue;					      \
 		}							      \
 		return NULL;	/* No match */				      \
 	}								      \
-- 
2.34.1

Re: [PATCH] lib/interval_tree: skip the check before go to the right subtree

[Matthew Wilcox]

On Mon, Feb 24, 2025 at 02:22:39AM +0000, Wei Yang wrote:
> So skip the check before go to the right subtree.

what testing have you done?

Re: [PATCH] lib/interval_tree: skip the check before go to the right subtree

[Wei Yang]

On Mon, Feb 24, 2025 at 05:15:46AM +0000, Matthew Wilcox wrote:
>On Mon, Feb 24, 2025 at 02:22:39AM +0000, Wei Yang wrote:
>> So skip the check before go to the right subtree.
>
>what testing have you done?

I did kernel build test for about 50+ rounds on top of recent mmunstable tree.

-- 
Wei Yang
Help you, Help me

Re: [PATCH] lib/interval_tree: skip the check before go to the right subtree

[Matthew Wilcox]

On Mon, Feb 24, 2025 at 07:08:42AM +0000, Wei Yang wrote:
> On Mon, Feb 24, 2025 at 05:15:46AM +0000, Matthew Wilcox wrote:
> >On Mon, Feb 24, 2025 at 02:22:39AM +0000, Wei Yang wrote:
> >> So skip the check before go to the right subtree.
> >
> >what testing have you done?
> 
> I did kernel build test for about 50+ rounds on top of recent mmunstable tree.

And did anything improve?