+ lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch added to mm-nonmm-unstable branch

+ lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch added to mm-nonmm-unstable branch

[Andrew Morton]

The patch titled
     Subject: lib/interval_tree: skip the check before go to the right subtree
has been added to the -mm mm-nonmm-unstable branch.  Its filename is
     lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch

This patch will shortly appear at
     https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch

This patch will later appear in the mm-nonmm-unstable branch at
    git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

Before you just go and hit "reply", please:
   a) Consider who else should be cc'ed
   b) Prefer to cc a suitable mailing list as well
   c) Ideally: find the original patch on the mailing list and do a
      reply-to-all to that, adding suitable additional cc's

*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***

The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days

------------------------------------------------------
From: Wei Yang <richard.weiyang@gmail.com>
Subject: lib/interval_tree: skip the check before go to the right subtree
Date: Mon, 24 Feb 2025 02:22:39 +0000

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.

Link: https://lkml.kernel.org/r/20250224022239.21976-1-richard.weiyang@gmail.com
Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
Cc: Matthew Wilcox <willy@infradead.org>
Cc: Michel Lespinasse <michel@lespinasse.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 include/linux/interval_tree_generic.h |    8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

--- a/include/linux/interval_tree_generic.h~lib-interval_tree-skip-the-check-before-go-to-the-right-subtree
+++ a/include/linux/interval_tree_generic.h
@@ -104,12 +104,8 @@ ITPREFIX ## _subtree_search(ITSTRUCT *no
 		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 */				      \
 	}								      \
_

Patches currently in -mm which might be from richard.weiyang@gmail.com are

mm-mm_initc-use-round_up-to-align-movable-range.patch
mm-mm_initc-only-align-start-of-zone_movalbe-on-nodes-with-memory.patch
mm-mm_initc-use-round_up-to-calculate-usermap-size.patch
lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch

Re: + lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch added to mm-nonmm-unstable branch

[Matthew Wilcox]

On Mon, Feb 24, 2025 at 08:22:34PM -0800, Andrew Morton wrote:
> The patch titled
>      Subject: lib/interval_tree: skip the check before go to the right subtree
> has been added to the -mm mm-nonmm-unstable branch.  Its filename is
>      lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch

I don't think this patch should be added.  There's no claim of any
performance win.  Wei has a long history of tweaky little patches that
may or may not be buggy.  The interval tree has been around a long time
and doesn't have a test suite.  This feels like unnecessary risk.

Re: + lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch added to mm-nonmm-unstable branch

[Wei Yang]

On Tue, Feb 25, 2025 at 12:35:29PM +0000, Matthew Wilcox wrote:
>On Mon, Feb 24, 2025 at 08:22:34PM -0800, Andrew Morton wrote:
>> The patch titled
>>      Subject: lib/interval_tree: skip the check before go to the right subtree
>> has been added to the -mm mm-nonmm-unstable branch.  Its filename is
>>      lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch
>
>I don't think this patch should be added.  There's no claim of any
>performance win.  Wei has a long history of tweaky little patches that
>may or may not be buggy.  The interval tree has been around a long time
>and doesn't have a test suite.  This feels like unnecessary risk.

Your concern is understandable. A change in fundamental data structure should
be very careful. But I thought we don't take things personal.

-- 
Wei Yang
Help you, Help me

Re: + lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch added to mm-nonmm-unstable branch

[Matthew Wilcox]

On Wed, Feb 26, 2025 at 02:22:33AM +0000, Wei Yang wrote:
> On Tue, Feb 25, 2025 at 12:35:29PM +0000, Matthew Wilcox wrote:
> >On Mon, Feb 24, 2025 at 08:22:34PM -0800, Andrew Morton wrote:
> >> The patch titled
> >>      Subject: lib/interval_tree: skip the check before go to the right subtree
> >> has been added to the -mm mm-nonmm-unstable branch.  Its filename is
> >>      lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch
> >
> >I don't think this patch should be added.  There's no claim of any
> >performance win.  Wei has a long history of tweaky little patches that
> >may or may not be buggy.  The interval tree has been around a long time
> >and doesn't have a test suite.  This feels like unnecessary risk.
> 
> Your concern is understandable. A change in fundamental data structure should
> be very careful. But I thought we don't take things personal.

This isn't personal.  It's noting your history.

If you want to add a test suite for the interval tree to the kernel,
that would be a useful set of patches.  And it would remove my concern
if we can demonstrate that we've exercised the code paths that you're
modifying and everything is fine.

Re: + lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch added to mm-nonmm-unstable branch

[Wei Yang]

On Wed, Feb 26, 2025 at 04:33:39AM +0000, Matthew Wilcox wrote:
>On Wed, Feb 26, 2025 at 02:22:33AM +0000, Wei Yang wrote:
>> On Tue, Feb 25, 2025 at 12:35:29PM +0000, Matthew Wilcox wrote:
>> >On Mon, Feb 24, 2025 at 08:22:34PM -0800, Andrew Morton wrote:
>> >> The patch titled
>> >>      Subject: lib/interval_tree: skip the check before go to the right subtree
>> >> has been added to the -mm mm-nonmm-unstable branch.  Its filename is
>> >>      lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch
>> >
>> >I don't think this patch should be added.  There's no claim of any
>> >performance win.  Wei has a long history of tweaky little patches that
>> >may or may not be buggy.  The interval tree has been around a long time
>> >and doesn't have a test suite.  This feels like unnecessary risk.
>> 
>> Your concern is understandable. A change in fundamental data structure should
>> be very careful. But I thought we don't take things personal.
>
>This isn't personal.  It's noting your history.
>
>If you want to add a test suite for the interval tree to the kernel,
>that would be a useful set of patches.  And it would remove my concern
>if we can demonstrate that we've exercised the code paths that you're
>modifying and everything is fine.

Sure, if my understanding is correct, the test suite is supposed to be put
tools/testing/, right?

-- 
Wei Yang
Help you, Help me

Re: + lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch added to mm-nonmm-unstable branch

[Michel Lespinasse]

On Wed, Feb 26, 2025 at 01:19:13PM +0000, Wei Yang wrote:
> On Wed, Feb 26, 2025 at 04:33:39AM +0000, Matthew Wilcox wrote:
> >On Wed, Feb 26, 2025 at 02:22:33AM +0000, Wei Yang wrote:
> >> On Tue, Feb 25, 2025 at 12:35:29PM +0000, Matthew Wilcox wrote:
> >> >On Mon, Feb 24, 2025 at 08:22:34PM -0800, Andrew Morton wrote:
> >> >> The patch titled
> >> >>      Subject: lib/interval_tree: skip the check before go to the right subtree
> >> >> has been added to the -mm mm-nonmm-unstable branch.  Its filename is
> >> >>      lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch
> >> >
> >> >I don't think this patch should be added.  There's no claim of any
> >> >performance win.  Wei has a long history of tweaky little patches that
> >> >may or may not be buggy.  The interval tree has been around a long time
> >> >and doesn't have a test suite.  This feels like unnecessary risk.
> >> 
> >> Your concern is understandable. A change in fundamental data structure should
> >> be very careful. But I thought we don't take things personal.
> >
> >This isn't personal.  It's noting your history.
> >
> >If you want to add a test suite for the interval tree to the kernel,
> >that would be a useful set of patches.  And it would remove my concern
> >if we can demonstrate that we've exercised the code paths that you're
> >modifying and everything is fine.
> 
> Sure, if my understanding is correct, the test suite is supposed to be put
> tools/testing/, right?

(I accidentally sent this privately at first, resending publicly now)

I haven't touched the code much since I originally wrote it, but I
think the logic of Wei's patch is sound.

Even then, I agree a more robust test suite would be nice. There is an
existing suite at lib/interval_tree_test.c, but it's more oriented
towards performance testing that correctness. It would be nice if it
checked the interval tree invariants (i.e. that each node's ITSUBTREE
is the max of its ITLAST and its children's ITSUBTREE) between
operations, like lib/rbtree_test.c check_augmented() does.

I know many people don't like test suites that involve randomness, but
personally I think verifying that inserting 1000 random nodes works as
expected, and repeating that test 10000 times or so, should give
reasonable confidence in this code.

--
Michel "walken" Lespinasse

Re: + lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch added to mm-nonmm-unstable branch

[Wei Yang]

On Thu, Feb 27, 2025 at 02:59:57PM -0800, Michel Lespinasse wrote:
>On Wed, Feb 26, 2025 at 01:19:13PM +0000, Wei Yang wrote:
>> On Wed, Feb 26, 2025 at 04:33:39AM +0000, Matthew Wilcox wrote:
>> >On Wed, Feb 26, 2025 at 02:22:33AM +0000, Wei Yang wrote:
>> >> On Tue, Feb 25, 2025 at 12:35:29PM +0000, Matthew Wilcox wrote:
>> >> >On Mon, Feb 24, 2025 at 08:22:34PM -0800, Andrew Morton wrote:
>> >> >> The patch titled
>> >> >>      Subject: lib/interval_tree: skip the check before go to the right subtree
>> >> >> has been added to the -mm mm-nonmm-unstable branch.  Its filename is
>> >> >>      lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch
>> >> >
>> >> >I don't think this patch should be added.  There's no claim of any
>> >> >performance win.  Wei has a long history of tweaky little patches that
>> >> >may or may not be buggy.  The interval tree has been around a long time
>> >> >and doesn't have a test suite.  This feels like unnecessary risk.
>> >> 
>> >> Your concern is understandable. A change in fundamental data structure should
>> >> be very careful. But I thought we don't take things personal.
>> >
>> >This isn't personal.  It's noting your history.
>> >
>> >If you want to add a test suite for the interval tree to the kernel,
>> >that would be a useful set of patches.  And it would remove my concern
>> >if we can demonstrate that we've exercised the code paths that you're
>> >modifying and everything is fine.
>> 
>> Sure, if my understanding is correct, the test suite is supposed to be put
>> tools/testing/, right?
>
>(I accidentally sent this privately at first, resending publicly now)
>
>I haven't touched the code much since I originally wrote it, but I
>think the logic of Wei's patch is sound.
>

Thanks.

>Even then, I agree a more robust test suite would be nice. There is an
>existing suite at lib/interval_tree_test.c, but it's more oriented
>towards performance testing that correctness. It would be nice if it
>checked the interval tree invariants (i.e. that each node's ITSUBTREE
>is the max of its ITLAST and its children's ITSUBTREE) between
>operations, like lib/rbtree_test.c check_augmented() does.
>
>I know many people don't like test suites that involve randomness, but
>personally I think verifying that inserting 1000 random nodes works as
>expected, and repeating that test 10000 times or so, should give
>reasonable confidence in this code.
>

Let me have a try.

>--
>Michel "walken" Lespinasse

-- 
Wei Yang
Help you, Help me

+ lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch added to mm-nonmm-unstable branch

[Andrew Morton]

The patch titled
     Subject: lib/interval_tree: skip the check before go to the right subtree
has been added to the -mm mm-nonmm-unstable branch.  Its filename is
     lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch

This patch will shortly appear at
     https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch

This patch will later appear in the mm-nonmm-unstable branch at
    git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

Before you just go and hit "reply", please:
   a) Consider who else should be cc'ed
   b) Prefer to cc a suitable mailing list as well
   c) Ideally: find the original patch on the mailing list and do a
      reply-to-all to that, adding suitable additional cc's

*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***

The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days

------------------------------------------------------
From: Wei Yang <richard.weiyang@gmail.com>
Subject: lib/interval_tree: skip the check before go to the right subtree
Date: Mon, 10 Mar 2025 07:49:37 +0000

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.

Link: https://lkml.kernel.org/r/20250310074938.26756-7-richard.weiyang@gmail.com
Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
Cc: Matthew Wilcox <willy@infradead.org>
Cc: Michel Lespinasse <michel@lespinasse.org>
Cc: Jason Gunthorpe <jgg@nvidia.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 include/linux/interval_tree_generic.h |    8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

--- a/include/linux/interval_tree_generic.h~lib-interval_tree-skip-the-check-before-go-to-the-right-subtree
+++ a/include/linux/interval_tree_generic.h
@@ -104,12 +104,8 @@ ITPREFIX ## _subtree_search(ITSTRUCT *no
 		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 */				      \
 	}								      \
_

Patches currently in -mm which might be from richard.weiyang@gmail.com are

mm-mm_initc-use-round_up-to-align-movable-range.patch
mm-mm_initc-only-align-start-of-zone_movalbe-on-nodes-with-memory.patch
mm-mm_initc-use-round_up-to-calculate-usermap-size.patch
lib-rbtree-enable-userland-test-suite-for-rbtree-related-data-structure.patch
lib-rbtree-split-tests.patch
lib-rbtree-add-random-seed.patch
lib-interval_tree-add-test-case-for-interval_tree_iter_xxx-helpers.patch
lib-interval_tree-add-test-case-for-span-iteration.patch
lib-interval_tree-skip-the-check-before-go-to-the-right-subtree.patch
lib-interval_tree-fix-the-comment-of-interval_tree_span_iter_next_gap.patch