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
