[PATCH 0/7] lib/interval_tree: add some test cases and cleanup

[PATCH 0/7] lib/interval_tree: add some test cases and cleanup

[Wei Yang]

Originally, I sent an interval tree cleanup[1], but lack of reasonable test.

As Matthew suggested, this patch set includes proper test to exercise the
change in interval tree.

Since rbtree/augmented tree/interval tree share similar data structure,
besides new cases for interval tree, this patch set also does cleanup for
others.

Patch 1: There are test cases as kernel module, this patch enable them in
         userland. This would help for testing and debugging.
Patch 2: Split cases for better reading. And prepare for new cases adding.
Patch 3: Add random seed to cover different situations
Patch 4: Add case for interval_tree_iter_xxx() helper
Patch 5: Add case for span iteration
Patch 6: is the original cleanup
Patch 7: fix the comment of interval_tree_span_iter_next_gap()

[1]: https://lkml.kernel.org/r/20250224022239.21976-1-richard.weiyang@gmail.com

Wei Yang (7):
  lib/rbtree: enable userland test suite for rbtree related data
    structure
  lib/rbtree: split tests
  lib/rbtree: add random seed
  lib/interval_tree: add test case for interval_tree_iter_xxx() helpers
  lib/interval_tree: add test case for span iteration
  lib/interval_tree: skip the check before go to the right subtree
  lib/interval_tree: fix the comment of
    interval_tree_span_iter_next_gap()

 include/linux/interval_tree_generic.h         |   8 +-
 lib/interval_tree.c                           |  12 +-
 lib/interval_tree_test.c                      | 237 ++++++++++++++++--
 lib/rbtree_test.c                             |  30 ++-
 tools/include/asm/timex.h                     |  13 +
 tools/include/linux/bitmap.h                  |  21 ++
 tools/include/linux/container_of.h            |   5 +
 tools/include/linux/math64.h                  |   5 +
 tools/include/linux/moduleparam.h             |   7 +
 tools/include/linux/prandom.h                 |  51 ++++
 tools/include/linux/slab.h                    |   1 +
 tools/lib/bitmap.c                            |  20 ++
 tools/lib/slab.c                              |  16 ++
 tools/testing/rbtree/Makefile                 |  33 +++
 tools/testing/rbtree/interval_tree_test.c     |  58 +++++
 tools/testing/rbtree/rbtree_test.c            |  48 ++++
 tools/testing/rbtree/test.h                   |   4 +
 tools/testing/shared/interval_tree-shim.c     |   5 +
 tools/testing/shared/linux/interval_tree.h    |   7 +
 .../shared/linux/interval_tree_generic.h      |   2 +
 tools/testing/shared/linux/rbtree.h           |   8 +
 tools/testing/shared/linux/rbtree_augmented.h |   7 +
 tools/testing/shared/linux/rbtree_types.h     |   8 +
 tools/testing/shared/rbtree-shim.c            |   6 +
 24 files changed, 583 insertions(+), 29 deletions(-)
 create mode 100644 tools/include/asm/timex.h
 create mode 100644 tools/include/linux/container_of.h
 create mode 100644 tools/include/linux/moduleparam.h
 create mode 100644 tools/include/linux/prandom.h
 create mode 100644 tools/testing/rbtree/Makefile
 create mode 100644 tools/testing/rbtree/interval_tree_test.c
 create mode 100644 tools/testing/rbtree/rbtree_test.c
 create mode 100644 tools/testing/rbtree/test.h
 create mode 100644 tools/testing/shared/interval_tree-shim.c
 create mode 100644 tools/testing/shared/linux/interval_tree.h
 create mode 100644 tools/testing/shared/linux/interval_tree_generic.h
 create mode 100644 tools/testing/shared/linux/rbtree.h
 create mode 100644 tools/testing/shared/linux/rbtree_augmented.h
 create mode 100644 tools/testing/shared/linux/rbtree_types.h
 create mode 100644 tools/testing/shared/rbtree-shim.c

-- 
2.34.1

[PATCH 1/7] lib/rbtree: enable userland test suite for rbtree related data structure

[Wei Yang]

Currently we have some tests for rbtree related data structure, e.g.
rbtree, augmented rbtree, interval tree, in lib/ as kernel module.

To facilitate the test and debug for those fundamental data structure,
this patch enable those tests in userland.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Matthew Wilcox <willy@infradead.org>
CC: Michel Lespinasse <michel@lespinasse.org>
---
 tools/include/asm/timex.h                     | 13 +++++
 tools/include/linux/container_of.h            |  5 ++
 tools/include/linux/math64.h                  |  5 ++
 tools/include/linux/moduleparam.h             |  7 +++
 tools/include/linux/prandom.h                 | 51 ++++++++++++++++++
 tools/include/linux/slab.h                    |  1 +
 tools/lib/slab.c                              | 16 ++++++
 tools/testing/rbtree/Makefile                 | 31 +++++++++++
 tools/testing/rbtree/interval_tree_test.c     | 53 +++++++++++++++++++
 tools/testing/rbtree/rbtree_test.c            | 45 ++++++++++++++++
 tools/testing/rbtree/test.h                   |  4 ++
 tools/testing/shared/interval_tree-shim.c     |  5 ++
 tools/testing/shared/linux/interval_tree.h    |  7 +++
 .../shared/linux/interval_tree_generic.h      |  2 +
 tools/testing/shared/linux/rbtree.h           |  8 +++
 tools/testing/shared/linux/rbtree_augmented.h |  7 +++
 tools/testing/shared/linux/rbtree_types.h     |  8 +++
 tools/testing/shared/rbtree-shim.c            |  6 +++
 18 files changed, 274 insertions(+)
 create mode 100644 tools/include/asm/timex.h
 create mode 100644 tools/include/linux/container_of.h
 create mode 100644 tools/include/linux/moduleparam.h
 create mode 100644 tools/include/linux/prandom.h
 create mode 100644 tools/testing/rbtree/Makefile
 create mode 100644 tools/testing/rbtree/interval_tree_test.c
 create mode 100644 tools/testing/rbtree/rbtree_test.c
 create mode 100644 tools/testing/rbtree/test.h
 create mode 100644 tools/testing/shared/interval_tree-shim.c
 create mode 100644 tools/testing/shared/linux/interval_tree.h
 create mode 100644 tools/testing/shared/linux/interval_tree_generic.h
 create mode 100644 tools/testing/shared/linux/rbtree.h
 create mode 100644 tools/testing/shared/linux/rbtree_augmented.h
 create mode 100644 tools/testing/shared/linux/rbtree_types.h
 create mode 100644 tools/testing/shared/rbtree-shim.c

diff --git a/tools/include/asm/timex.h b/tools/include/asm/timex.h
new file mode 100644
index 000000000000..5adfe3c6d326
--- /dev/null
+++ b/tools/include/asm/timex.h
@@ -0,0 +1,13 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __TOOLS_LINUX_ASM_TIMEX_H
+#define __TOOLS_LINUX_ASM_TIMEX_H
+
+#include <time.h>
+
+#define cycles_t clock_t
+
+static inline cycles_t get_cycles(void)
+{
+	return clock();
+}
+#endif // __TOOLS_LINUX_ASM_TIMEX_H
diff --git a/tools/include/linux/container_of.h b/tools/include/linux/container_of.h
new file mode 100644
index 000000000000..9adce874bea9
--- /dev/null
+++ b/tools/include/linux/container_of.h
@@ -0,0 +1,5 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _TOOLS_LINUX_CONTAINER_OF_H
+#define _TOOLS_LINUX_CONTAINER_OF_H
+
+#endif	/* _TOOLS_LINUX_CONTAINER_OF_H */
diff --git a/tools/include/linux/math64.h b/tools/include/linux/math64.h
index 4ad45d5943dc..8a67d478bf19 100644
--- a/tools/include/linux/math64.h
+++ b/tools/include/linux/math64.h
@@ -72,4 +72,9 @@ static inline u64 mul_u64_u64_div64(u64 a, u64 b, u64 c)
 }
 #endif
 
+static inline u64 div_u64(u64 dividend, u32 divisor)
+{
+	return dividend / divisor;
+}
+
 #endif /* _LINUX_MATH64_H */
diff --git a/tools/include/linux/moduleparam.h b/tools/include/linux/moduleparam.h
new file mode 100644
index 000000000000..4c4d05bef0cb
--- /dev/null
+++ b/tools/include/linux/moduleparam.h
@@ -0,0 +1,7 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _TOOLS_LINUX_MODULE_PARAMS_H
+#define _TOOLS_LINUX_MODULE_PARAMS_H
+
+#define MODULE_PARM_DESC(parm, desc)
+
+#endif // _TOOLS_LINUX_MODULE_PARAMS_H
diff --git a/tools/include/linux/prandom.h b/tools/include/linux/prandom.h
new file mode 100644
index 000000000000..b745041ccd6a
--- /dev/null
+++ b/tools/include/linux/prandom.h
@@ -0,0 +1,51 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __TOOLS_LINUX_PRANDOM_H
+#define __TOOLS_LINUX_PRANDOM_H
+
+#include <linux/types.h>
+
+struct rnd_state {
+	__u32 s1, s2, s3, s4;
+};
+
+/*
+ * Handle minimum values for seeds
+ */
+static inline u32 __seed(u32 x, u32 m)
+{
+	return (x < m) ? x + m : x;
+}
+
+/**
+ * prandom_seed_state - set seed for prandom_u32_state().
+ * @state: pointer to state structure to receive the seed.
+ * @seed: arbitrary 64-bit value to use as a seed.
+ */
+static inline void prandom_seed_state(struct rnd_state *state, u64 seed)
+{
+	u32 i = ((seed >> 32) ^ (seed << 10) ^ seed) & 0xffffffffUL;
+
+	state->s1 = __seed(i,   2U);
+	state->s2 = __seed(i,   8U);
+	state->s3 = __seed(i,  16U);
+	state->s4 = __seed(i, 128U);
+}
+
+/**
+ *	prandom_u32_state - seeded pseudo-random number generator.
+ *	@state: pointer to state structure holding seeded state.
+ *
+ *	This is used for pseudo-randomness with no outside seeding.
+ *	For more random results, use get_random_u32().
+ */
+static inline u32 prandom_u32_state(struct rnd_state *state)
+{
+#define TAUSWORTHE(s, a, b, c, d) (((s & c) << d) ^ (((s << a) ^ s) >> b))
+	state->s1 = TAUSWORTHE(state->s1,  6U, 13U, 4294967294U, 18U);
+	state->s2 = TAUSWORTHE(state->s2,  2U, 27U, 4294967288U,  2U);
+	state->s3 = TAUSWORTHE(state->s3, 13U, 21U, 4294967280U,  7U);
+	state->s4 = TAUSWORTHE(state->s4,  3U, 12U, 4294967168U, 13U);
+
+	return (state->s1 ^ state->s2 ^ state->s3 ^ state->s4);
+}
+#endif // __TOOLS_LINUX_PRANDOM_H
diff --git a/tools/include/linux/slab.h b/tools/include/linux/slab.h
index 51b25e9c4ec7..c87051e2b26f 100644
--- a/tools/include/linux/slab.h
+++ b/tools/include/linux/slab.h
@@ -12,6 +12,7 @@
 
 void *kmalloc(size_t size, gfp_t gfp);
 void kfree(void *p);
+void *kmalloc_array(size_t n, size_t size, gfp_t gfp);
 
 bool slab_is_available(void);
 
diff --git a/tools/lib/slab.c b/tools/lib/slab.c
index 959997fb0652..981a21404f32 100644
--- a/tools/lib/slab.c
+++ b/tools/lib/slab.c
@@ -36,3 +36,19 @@ void kfree(void *p)
 		printf("Freeing %p to malloc\n", p);
 	free(p);
 }
+
+void *kmalloc_array(size_t n, size_t size, gfp_t gfp)
+{
+	void *ret;
+
+	if (!(gfp & __GFP_DIRECT_RECLAIM))
+		return NULL;
+
+	ret = calloc(n, size);
+	uatomic_inc(&kmalloc_nr_allocated);
+	if (kmalloc_verbose)
+		printf("Allocating %p from calloc\n", ret);
+	if (gfp & __GFP_ZERO)
+		memset(ret, 0, n * size);
+	return ret;
+}
diff --git a/tools/testing/rbtree/Makefile b/tools/testing/rbtree/Makefile
new file mode 100644
index 000000000000..bac6931b499d
--- /dev/null
+++ b/tools/testing/rbtree/Makefile
@@ -0,0 +1,31 @@
+# SPDX-License-Identifier: GPL-2.0
+
+.PHONY: clean
+
+TARGETS = rbtree_test interval_tree_test
+OFILES = $(LIBS) rbtree-shim.o interval_tree-shim.o
+DEPS = ../../../include/linux/rbtree.h \
+	../../../include/linux/rbtree_types.h \
+	../../../include/linux/rbtree_augmented.h \
+	../../../include/linux/interval_tree.h \
+	../../../include/linux/interval_tree_generic.h \
+	../../../lib/rbtree.c \
+	../../../lib/interval_tree.c
+
+targets: $(TARGETS)
+
+include ../shared/shared.mk
+
+ifeq ($(DEBUG), 1)
+	CFLAGS += -g
+endif
+
+$(TARGETS):	$(OFILES)
+
+rbtree-shim.o: $(DEPS)
+rbtree_test.o:  ../../../lib/rbtree_test.c
+interval_tree-shim.o: $(DEPS)
+interval_tree_test.o: 	../../../lib/interval_tree_test.c
+
+clean:
+	$(RM) $(TARGETS) *.o generated/*
diff --git a/tools/testing/rbtree/interval_tree_test.c b/tools/testing/rbtree/interval_tree_test.c
new file mode 100644
index 000000000000..f1c41f5e28ba
--- /dev/null
+++ b/tools/testing/rbtree/interval_tree_test.c
@@ -0,0 +1,53 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * interval_tree.c: Userspace Interval Tree test-suite
+ * Copyright (c) 2025 Wei Yang <richard.weiyang@gmail.com>
+ */
+#include <linux/math64.h>
+#include <linux/kern_levels.h>
+#include "shared.h"
+
+#include "../../../lib/interval_tree_test.c"
+
+int usage(void)
+{
+	fprintf(stderr, "Userland interval tree test cases\n");
+	fprintf(stderr, "  -n: Number of nodes in the interval tree\n");
+	fprintf(stderr, "  -p: Number of iterations modifying the tree\n");
+	fprintf(stderr, "  -q: Number of searches to the interval tree\n");
+	fprintf(stderr, "  -s: Number of iterations searching the tree\n");
+	fprintf(stderr, "  -a: Searches will iterate all nodes in the tree\n");
+	fprintf(stderr, "  -m: Largest value for the interval's endpoint\n");
+	exit(-1);
+}
+
+void interval_tree_tests(void)
+{
+	interval_tree_test_init();
+	interval_tree_test_exit();
+}
+
+int main(int argc, char **argv)
+{
+	int opt;
+
+	while ((opt = getopt(argc, argv, "n:p:q:s:am:")) != -1) {
+		if (opt == 'n')
+			nnodes = strtoul(optarg, NULL, 0);
+		else if (opt == 'p')
+			perf_loops = strtoul(optarg, NULL, 0);
+		else if (opt == 'q')
+			nsearches = strtoul(optarg, NULL, 0);
+		else if (opt == 's')
+			search_loops = strtoul(optarg, NULL, 0);
+		else if (opt == 'a')
+			search_all = true;
+		else if (opt == 'm')
+			max_endpoint = strtoul(optarg, NULL, 0);
+		else
+			usage();
+	}
+
+	interval_tree_tests();
+	return 0;
+}
diff --git a/tools/testing/rbtree/rbtree_test.c b/tools/testing/rbtree/rbtree_test.c
new file mode 100644
index 000000000000..c723e751b9a9
--- /dev/null
+++ b/tools/testing/rbtree/rbtree_test.c
@@ -0,0 +1,45 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * rbtree_test.c: Userspace Red Black Tree test-suite
+ * Copyright (c) 2025 Wei Yang <richard.weiyang@gmail.com>
+ */
+#include <linux/init.h>
+#include <linux/math64.h>
+#include <linux/kern_levels.h>
+#include "shared.h"
+
+#include "../../../lib/rbtree_test.c"
+
+int usage(void)
+{
+	fprintf(stderr, "Userland rbtree test cases\n");
+	fprintf(stderr, "  -n: Number of nodes in the rb-tree\n");
+	fprintf(stderr, "  -p: Number of iterations modifying the rb-tree\n");
+	fprintf(stderr, "  -c: Number of iterations modifying and verifying the rb-tree\n");
+	exit(-1);
+}
+
+void rbtree_tests(void)
+{
+	rbtree_test_init();
+	rbtree_test_exit();
+}
+
+int main(int argc, char **argv)
+{
+	int opt;
+
+	while ((opt = getopt(argc, argv, "n:p:c:")) != -1) {
+		if (opt == 'n')
+			nnodes = strtoul(optarg, NULL, 0);
+		else if (opt == 'p')
+			perf_loops = strtoul(optarg, NULL, 0);
+		else if (opt == 'c')
+			check_loops = strtoul(optarg, NULL, 0);
+		else
+			usage();
+	}
+
+	rbtree_tests();
+	return 0;
+}
diff --git a/tools/testing/rbtree/test.h b/tools/testing/rbtree/test.h
new file mode 100644
index 000000000000..f1f1b545b55a
--- /dev/null
+++ b/tools/testing/rbtree/test.h
@@ -0,0 +1,4 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+void rbtree_tests(void);
+void interval_tree_tests(void);
diff --git a/tools/testing/shared/interval_tree-shim.c b/tools/testing/shared/interval_tree-shim.c
new file mode 100644
index 000000000000..122e74756571
--- /dev/null
+++ b/tools/testing/shared/interval_tree-shim.c
@@ -0,0 +1,5 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/* Very simple shim around the interval tree. */
+
+#include "../../../lib/interval_tree.c"
diff --git a/tools/testing/shared/linux/interval_tree.h b/tools/testing/shared/linux/interval_tree.h
new file mode 100644
index 000000000000..129faf9f1d0a
--- /dev/null
+++ b/tools/testing/shared/linux/interval_tree.h
@@ -0,0 +1,7 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _TEST_INTERVAL_TREE_H
+#define _TEST_INTERVAL_TREE_H
+
+#include "../../../../include/linux/interval_tree.h"
+
+#endif /* _TEST_INTERVAL_TREE_H */
diff --git a/tools/testing/shared/linux/interval_tree_generic.h b/tools/testing/shared/linux/interval_tree_generic.h
new file mode 100644
index 000000000000..34cd654bee61
--- /dev/null
+++ b/tools/testing/shared/linux/interval_tree_generic.h
@@ -0,0 +1,2 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#include "../../../../include/linux/interval_tree_generic.h"
diff --git a/tools/testing/shared/linux/rbtree.h b/tools/testing/shared/linux/rbtree.h
new file mode 100644
index 000000000000..d644bb7360bf
--- /dev/null
+++ b/tools/testing/shared/linux/rbtree.h
@@ -0,0 +1,8 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _TEST_RBTREE_H
+#define _TEST_RBTREE_H
+
+#include <linux/kernel.h>
+#include "../../../../include/linux/rbtree.h"
+
+#endif /* _TEST_RBTREE_H */
diff --git a/tools/testing/shared/linux/rbtree_augmented.h b/tools/testing/shared/linux/rbtree_augmented.h
new file mode 100644
index 000000000000..ad138fcf6652
--- /dev/null
+++ b/tools/testing/shared/linux/rbtree_augmented.h
@@ -0,0 +1,7 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _TEST_RBTREE_AUGMENTED_H
+#define _TEST_RBTREE_AUGMENTED_H
+
+#include "../../../../include/linux/rbtree_augmented.h"
+
+#endif /* _TEST_RBTREE_AUGMENTED_H */
diff --git a/tools/testing/shared/linux/rbtree_types.h b/tools/testing/shared/linux/rbtree_types.h
new file mode 100644
index 000000000000..194194a5bf92
--- /dev/null
+++ b/tools/testing/shared/linux/rbtree_types.h
@@ -0,0 +1,8 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _TEST_RBTREE_TYPES_H
+#define _TEST_RBTREE_TYPES_H
+
+#include "../../../../include/linux/rbtree_types.h"
+
+#endif /* _TEST_RBTREE_TYPES_H */
+
diff --git a/tools/testing/shared/rbtree-shim.c b/tools/testing/shared/rbtree-shim.c
new file mode 100644
index 000000000000..7692a993e5f1
--- /dev/null
+++ b/tools/testing/shared/rbtree-shim.c
@@ -0,0 +1,6 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/* Very simple shim around the rbtree. */
+
+#include "../../../lib/rbtree.c"
+
-- 
2.34.1

[PATCH 2/7] lib/rbtree: split tests

[Wei Yang]

Current tests are gathered in one big function.

Split tests into its own function for better understanding and also it
is a preparation for introducing new test cases.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Matthew Wilcox <willy@infradead.org>
CC: Michel Lespinasse <michel@lespinasse.org>
---
 lib/interval_tree_test.c | 50 +++++++++++++++++++++++++++++-----------
 lib/rbtree_test.c        | 29 ++++++++++++++++++-----
 2 files changed, 59 insertions(+), 20 deletions(-)

diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c
index 837064b83a6c..12880d772945 100644
--- a/lib/interval_tree_test.c
+++ b/lib/interval_tree_test.c
@@ -59,26 +59,13 @@ static void init(void)
 		queries[i] = (prandom_u32_state(&rnd) >> 4) % max_endpoint;
 }
 
-static int interval_tree_test_init(void)
+static int basic_check(void)
 {
 	int i, j;
-	unsigned long results;
 	cycles_t time1, time2, time;
 
-	nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node),
-			      GFP_KERNEL);
-	if (!nodes)
-		return -ENOMEM;
-
-	queries = kmalloc_array(nsearches, sizeof(int), GFP_KERNEL);
-	if (!queries) {
-		kfree(nodes);
-		return -ENOMEM;
-	}
-
 	printk(KERN_ALERT "interval tree insert/remove");
 
-	prandom_seed_state(&rnd, 3141592653589793238ULL);
 	init();
 
 	time1 = get_cycles();
@@ -96,8 +83,19 @@ static int interval_tree_test_init(void)
 	time = div_u64(time, perf_loops);
 	printk(" -> %llu cycles\n", (unsigned long long)time);
 
+	return 0;
+}
+
+static int search_check(void)
+{
+	int i, j;
+	unsigned long results;
+	cycles_t time1, time2, time;
+
 	printk(KERN_ALERT "interval tree search");
 
+	init();
+
 	for (j = 0; j < nnodes; j++)
 		interval_tree_insert(nodes + j, &root);
 
@@ -120,6 +118,30 @@ static int interval_tree_test_init(void)
 	printk(" -> %llu cycles (%lu results)\n",
 	       (unsigned long long)time, results);
 
+	for (j = 0; j < nnodes; j++)
+		interval_tree_remove(nodes + j, &root);
+
+	return 0;
+}
+
+static int interval_tree_test_init(void)
+{
+	nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node),
+			      GFP_KERNEL);
+	if (!nodes)
+		return -ENOMEM;
+
+	queries = kmalloc_array(nsearches, sizeof(int), GFP_KERNEL);
+	if (!queries) {
+		kfree(nodes);
+		return -ENOMEM;
+	}
+
+	prandom_seed_state(&rnd, 3141592653589793238ULL);
+
+	basic_check();
+	search_check();
+
 	kfree(queries);
 	kfree(nodes);
 
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index 8655a76d29a1..b0e0b26506cb 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -239,19 +239,14 @@ static void check_augmented(int nr_nodes)
 	}
 }
 
-static int __init rbtree_test_init(void)
+static int basic_check(void)
 {
 	int i, j;
 	cycles_t time1, time2, time;
 	struct rb_node *node;
 
-	nodes = kmalloc_array(nnodes, sizeof(*nodes), GFP_KERNEL);
-	if (!nodes)
-		return -ENOMEM;
-
 	printk(KERN_ALERT "rbtree testing");
 
-	prandom_seed_state(&rnd, 3141592653589793238ULL);
 	init();
 
 	time1 = get_cycles();
@@ -343,6 +338,14 @@ static int __init rbtree_test_init(void)
 		check(0);
 	}
 
+	return 0;
+}
+
+static int augmented_check(void)
+{
+	int i, j;
+	cycles_t time1, time2, time;
+
 	printk(KERN_ALERT "augmented rbtree testing");
 
 	init();
@@ -390,6 +393,20 @@ static int __init rbtree_test_init(void)
 		check_augmented(0);
 	}
 
+	return 0;
+}
+
+static int __init rbtree_test_init(void)
+{
+	nodes = kmalloc_array(nnodes, sizeof(*nodes), GFP_KERNEL);
+	if (!nodes)
+		return -ENOMEM;
+
+	prandom_seed_state(&rnd, 3141592653589793238ULL);
+
+	basic_check();
+	augmented_check();
+
 	kfree(nodes);
 
 	return -EAGAIN; /* Fail will directly unload the module */
-- 
2.34.1

[PATCH 3/7] lib/rbtree: add random seed

[Wei Yang]

Current test use pseudo rand function with fixed seed, which means the
test data is the same pattern each time.

Add random seed parameter to randomize the test.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Matthew Wilcox <willy@infradead.org>
CC: Michel Lespinasse <michel@lespinasse.org>
---
 lib/interval_tree_test.c                  | 3 ++-
 lib/rbtree_test.c                         | 3 ++-
 tools/testing/rbtree/interval_tree_test.c | 5 ++++-
 tools/testing/rbtree/rbtree_test.c        | 5 ++++-
 4 files changed, 12 insertions(+), 4 deletions(-)

diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c
index 12880d772945..51cbc50d4cc5 100644
--- a/lib/interval_tree_test.c
+++ b/lib/interval_tree_test.c
@@ -19,6 +19,7 @@ __param(int, search_loops, 1000, "Number of iterations searching the tree");
 __param(bool, search_all, false, "Searches will iterate all nodes in the tree");
 
 __param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint");
+__param(ulong, seed, 3141592653589793238ULL, "Random seed");
 
 static struct rb_root_cached root = RB_ROOT_CACHED;
 static struct interval_tree_node *nodes = NULL;
@@ -137,7 +138,7 @@ static int interval_tree_test_init(void)
 		return -ENOMEM;
 	}
 
-	prandom_seed_state(&rnd, 3141592653589793238ULL);
+	prandom_seed_state(&rnd, seed);
 
 	basic_check();
 	search_check();
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index b0e0b26506cb..94ace8f0fbf8 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -14,6 +14,7 @@
 __param(int, nnodes, 100, "Number of nodes in the rb-tree");
 __param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");
 __param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");
+__param(ulong, seed, 3141592653589793238ULL, "Random seed");
 
 struct test_node {
 	u32 key;
@@ -402,7 +403,7 @@ static int __init rbtree_test_init(void)
 	if (!nodes)
 		return -ENOMEM;
 
-	prandom_seed_state(&rnd, 3141592653589793238ULL);
+	prandom_seed_state(&rnd, seed);
 
 	basic_check();
 	augmented_check();
diff --git a/tools/testing/rbtree/interval_tree_test.c b/tools/testing/rbtree/interval_tree_test.c
index f1c41f5e28ba..63775b831c1c 100644
--- a/tools/testing/rbtree/interval_tree_test.c
+++ b/tools/testing/rbtree/interval_tree_test.c
@@ -18,6 +18,7 @@ int usage(void)
 	fprintf(stderr, "  -s: Number of iterations searching the tree\n");
 	fprintf(stderr, "  -a: Searches will iterate all nodes in the tree\n");
 	fprintf(stderr, "  -m: Largest value for the interval's endpoint\n");
+	fprintf(stderr, "  -r: Random seed\n");
 	exit(-1);
 }
 
@@ -31,7 +32,7 @@ int main(int argc, char **argv)
 {
 	int opt;
 
-	while ((opt = getopt(argc, argv, "n:p:q:s:am:")) != -1) {
+	while ((opt = getopt(argc, argv, "n:p:q:s:am:r:")) != -1) {
 		if (opt == 'n')
 			nnodes = strtoul(optarg, NULL, 0);
 		else if (opt == 'p')
@@ -44,6 +45,8 @@ int main(int argc, char **argv)
 			search_all = true;
 		else if (opt == 'm')
 			max_endpoint = strtoul(optarg, NULL, 0);
+		else if (opt == 'r')
+			seed = strtoul(optarg, NULL, 0);
 		else
 			usage();
 	}
diff --git a/tools/testing/rbtree/rbtree_test.c b/tools/testing/rbtree/rbtree_test.c
index c723e751b9a9..585c970f679e 100644
--- a/tools/testing/rbtree/rbtree_test.c
+++ b/tools/testing/rbtree/rbtree_test.c
@@ -16,6 +16,7 @@ int usage(void)
 	fprintf(stderr, "  -n: Number of nodes in the rb-tree\n");
 	fprintf(stderr, "  -p: Number of iterations modifying the rb-tree\n");
 	fprintf(stderr, "  -c: Number of iterations modifying and verifying the rb-tree\n");
+	fprintf(stderr, "  -r: Random seed\n");
 	exit(-1);
 }
 
@@ -29,13 +30,15 @@ int main(int argc, char **argv)
 {
 	int opt;
 
-	while ((opt = getopt(argc, argv, "n:p:c:")) != -1) {
+	while ((opt = getopt(argc, argv, "n:p:c:r:")) != -1) {
 		if (opt == 'n')
 			nnodes = strtoul(optarg, NULL, 0);
 		else if (opt == 'p')
 			perf_loops = strtoul(optarg, NULL, 0);
 		else if (opt == 'c')
 			check_loops = strtoul(optarg, NULL, 0);
+		else if (opt == 'r')
+			seed = strtoul(optarg, NULL, 0);
 		else
 			usage();
 	}
-- 
2.34.1

[PATCH 4/7] lib/interval_tree: add test case for interval_tree_iter_xxx() helpers

[Wei Yang]

Verify interval_tree_iter_xxx() helpers could find intersection ranges
as expected.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Matthew Wilcox <willy@infradead.org>
CC: Michel Lespinasse <michel@lespinasse.org>
---
 lib/interval_tree_test.c     | 69 ++++++++++++++++++++++++++++++++++++
 tools/include/linux/bitmap.h | 21 +++++++++++
 tools/lib/bitmap.c           | 20 +++++++++++
 3 files changed, 110 insertions(+)

diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c
index 51cbc50d4cc5..383b547e8929 100644
--- a/lib/interval_tree_test.c
+++ b/lib/interval_tree_test.c
@@ -5,6 +5,7 @@
 #include <linux/prandom.h>
 #include <linux/slab.h>
 #include <asm/timex.h>
+#include <linux/bitmap.h>
 
 #define __param(type, name, init, msg)		\
 	static type name = init;		\
@@ -125,6 +126,73 @@ static int search_check(void)
 	return 0;
 }
 
+static int intersection_range_check(void)
+{
+	int i, j, k;
+	unsigned long start, last;
+	struct interval_tree_node *node;
+	unsigned long *intxn1;
+	unsigned long *intxn2;
+
+	printk(KERN_ALERT "interval tree iteration\n");
+
+	intxn1 = bitmap_alloc(nnodes, GFP_KERNEL);
+	if (!intxn1) {
+		WARN_ON_ONCE("Failed to allocate intxn1\n");
+		return -ENOMEM;
+	}
+
+	intxn2 = bitmap_alloc(nnodes, GFP_KERNEL);
+	if (!intxn2) {
+		WARN_ON_ONCE("Failed to allocate intxn2\n");
+		bitmap_free(intxn1);
+		return -ENOMEM;
+	}
+
+	for (i = 0; i < search_loops; i++) {
+		/* Initialize interval tree for each round */
+		init();
+		for (j = 0; j < nnodes; j++)
+			interval_tree_insert(nodes + j, &root);
+
+		/* Let's try nsearches different ranges */
+		for (k = 0; k < nsearches; k++) {
+			/* Try whole range once */
+			if (!k) {
+				start = 0UL;
+				last = ULONG_MAX;
+			} else {
+				last = (prandom_u32_state(&rnd) >> 4) % max_endpoint;
+				start = (prandom_u32_state(&rnd) >> 4) % last;
+			}
+
+			/* Walk nodes to mark intersection nodes */
+			bitmap_zero(intxn1, nnodes);
+			for (j = 0; j < nnodes; j++) {
+				node = nodes + j;
+
+				if (start <= node->last && last >= node->start)
+					bitmap_set(intxn1, j, 1);
+			}
+
+			/* Iterate tree to clear intersection nodes */
+			bitmap_zero(intxn2, nnodes);
+			for (node = interval_tree_iter_first(&root, start, last); node;
+			     node = interval_tree_iter_next(node, start, last))
+				bitmap_set(intxn2, node - nodes, 1);
+
+			WARN_ON_ONCE(!bitmap_equal(intxn1, intxn2, nnodes));
+		}
+
+		for (j = 0; j < nnodes; j++)
+			interval_tree_remove(nodes + j, &root);
+	}
+
+	bitmap_free(intxn1);
+	bitmap_free(intxn2);
+	return 0;
+}
+
 static int interval_tree_test_init(void)
 {
 	nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node),
@@ -142,6 +210,7 @@ static int interval_tree_test_init(void)
 
 	basic_check();
 	search_check();
+	intersection_range_check();
 
 	kfree(queries);
 	kfree(nodes);
diff --git a/tools/include/linux/bitmap.h b/tools/include/linux/bitmap.h
index 2a7f260ef9dc..8166719178f7 100644
--- a/tools/include/linux/bitmap.h
+++ b/tools/include/linux/bitmap.h
@@ -19,6 +19,7 @@ bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
 		 const unsigned long *bitmap2, unsigned int bits);
 bool __bitmap_equal(const unsigned long *bitmap1,
 		    const unsigned long *bitmap2, unsigned int bits);
+void __bitmap_set(unsigned long *map, unsigned int start, int len);
 void __bitmap_clear(unsigned long *map, unsigned int start, int len);
 bool __bitmap_intersects(const unsigned long *bitmap1,
 			 const unsigned long *bitmap2, unsigned int bits);
@@ -79,6 +80,11 @@ static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
 		__bitmap_or(dst, src1, src2, nbits);
 }
 
+static inline unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags)
+{
+	return malloc(bitmap_size(nbits));
+}
+
 /**
  * bitmap_zalloc - Allocate bitmap
  * @nbits: Number of bits
@@ -150,6 +156,21 @@ static inline bool bitmap_intersects(const unsigned long *src1,
 		return __bitmap_intersects(src1, src2, nbits);
 }
 
+static inline void bitmap_set(unsigned long *map, unsigned int start, unsigned int nbits)
+{
+	if (__builtin_constant_p(nbits) && nbits == 1)
+		__set_bit(start, map);
+	else if (small_const_nbits(start + nbits))
+		*map |= GENMASK(start + nbits - 1, start);
+	else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
+		 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
+		 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
+		 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
+		memset((char *)map + start / 8, 0xff, nbits / 8);
+	else
+		__bitmap_set(map, start, nbits);
+}
+
 static inline void bitmap_clear(unsigned long *map, unsigned int start,
 			       unsigned int nbits)
 {
diff --git a/tools/lib/bitmap.c b/tools/lib/bitmap.c
index 2178862bb114..51255c69754d 100644
--- a/tools/lib/bitmap.c
+++ b/tools/lib/bitmap.c
@@ -101,6 +101,26 @@ bool __bitmap_intersects(const unsigned long *bitmap1,
 	return false;
 }
 
+void __bitmap_set(unsigned long *map, unsigned int start, int len)
+{
+	unsigned long *p = map + BIT_WORD(start);
+	const unsigned int size = start + len;
+	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
+	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
+
+	while (len - bits_to_set >= 0) {
+		*p |= mask_to_set;
+		len -= bits_to_set;
+		bits_to_set = BITS_PER_LONG;
+		mask_to_set = ~0UL;
+		p++;
+	}
+	if (len) {
+		mask_to_set &= BITMAP_LAST_WORD_MASK(size);
+		*p |= mask_to_set;
+	}
+}
+
 void __bitmap_clear(unsigned long *map, unsigned int start, int len)
 {
 	unsigned long *p = map + BIT_WORD(start);
-- 
2.34.1

[PATCH 5/7] lib/interval_tree: add test case for span iteration

[Wei Yang]

Verify interval_tree_span_iter_xxx() helpers works as expected.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Matthew Wilcox <willy@infradead.org>
CC: Michel Lespinasse <michel@lespinasse.org>
---
 lib/interval_tree_test.c                  | 117 ++++++++++++++++++++++
 tools/testing/rbtree/Makefile             |   6 +-
 tools/testing/rbtree/interval_tree_test.c |   2 +
 3 files changed, 123 insertions(+), 2 deletions(-)

diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c
index 383b547e8929..37198afa87ed 100644
--- a/lib/interval_tree_test.c
+++ b/lib/interval_tree_test.c
@@ -6,6 +6,7 @@
 #include <linux/slab.h>
 #include <asm/timex.h>
 #include <linux/bitmap.h>
+#include <linux/maple_tree.h>
 
 #define __param(type, name, init, msg)		\
 	static type name = init;		\
@@ -193,6 +194,121 @@ static int intersection_range_check(void)
 	return 0;
 }
 
+#ifdef CONFIG_INTERVAL_TREE_SPAN_ITER
+/*
+ * Helper function to get span of current position from maple tree point of
+ * view.
+ */
+static void mas_cur_span(struct ma_state *mas, struct interval_tree_span_iter *state)
+{
+	unsigned long cur_start;
+	unsigned long cur_last;
+	int is_hole;
+
+	if (mas->status == ma_overflow)
+		return;
+
+	/* walk to current position */
+	state->is_hole = mas_walk(mas) ? 0 : 1;
+
+	cur_start = mas->index < state->first_index ?
+			state->first_index : mas->index;
+
+	/* whether we have followers */
+	do {
+
+		cur_last = mas->last > state->last_index ?
+				state->last_index : mas->last;
+
+		is_hole = mas_next_range(mas, state->last_index) ? 0 : 1;
+
+	} while (mas->status != ma_overflow && is_hole == state->is_hole);
+
+	if (state->is_hole) {
+		state->start_hole = cur_start;
+		state->last_hole = cur_last;
+	} else {
+		state->start_used = cur_start;
+		state->last_used = cur_last;
+	}
+
+	/* advance position for next round */
+	if (mas->status != ma_overflow)
+		mas_set(mas, cur_last + 1);
+}
+
+static int span_iteration_check(void)
+{
+	int i, j, k;
+	unsigned long start, last;
+	struct interval_tree_span_iter span, mas_span;
+
+	DEFINE_MTREE(tree);
+
+	MA_STATE(mas, &tree, 0, 0);
+
+	printk(KERN_ALERT "interval tree span iteration\n");
+
+	for (i = 0; i < search_loops; i++) {
+		/* Initialize interval tree for each round */
+		init();
+		for (j = 0; j < nnodes; j++)
+			interval_tree_insert(nodes + j, &root);
+
+		/* Put all the range into maple tree */
+		mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+		mt_set_in_rcu(&tree);
+
+		for (j = 0; j < nnodes; j++)
+			WARN_ON_ONCE(mtree_store_range(&tree, nodes[j].start,
+					nodes[j].last, nodes + j, GFP_KERNEL));
+
+		/* Let's try nsearches different ranges */
+		for (k = 0; k < nsearches; k++) {
+			/* Try whole range once */
+			if (!k) {
+				start = 0UL;
+				last = ULONG_MAX;
+			} else {
+				last = (prandom_u32_state(&rnd) >> 4) % max_endpoint;
+				start = (prandom_u32_state(&rnd) >> 4) % last;
+			}
+
+			mas_span.first_index = start;
+			mas_span.last_index = last;
+			mas_span.is_hole = -1;
+			mas_set(&mas, start);
+
+			interval_tree_for_each_span(&span, &root, start, last) {
+				mas_cur_span(&mas, &mas_span);
+
+				WARN_ON_ONCE(span.is_hole != mas_span.is_hole);
+
+				if (span.is_hole) {
+					WARN_ON_ONCE(span.start_hole != mas_span.start_hole);
+					WARN_ON_ONCE(span.last_hole != mas_span.last_hole);
+				} else {
+					WARN_ON_ONCE(span.start_used != mas_span.start_used);
+					WARN_ON_ONCE(span.last_used != mas_span.last_used);
+				}
+			}
+
+		}
+
+		WARN_ON_ONCE(mas.status != ma_overflow);
+
+		/* Cleanup maple tree for each round */
+		mtree_destroy(&tree);
+		/* Cleanup interval tree for each round */
+		for (j = 0; j < nnodes; j++)
+			interval_tree_remove(nodes + j, &root);
+	}
+	return 0;
+}
+#else
+static inline int span_iteration_check(void) {return 0; }
+#endif
+
 static int interval_tree_test_init(void)
 {
 	nodes = kmalloc_array(nnodes, sizeof(struct interval_tree_node),
@@ -211,6 +327,7 @@ static int interval_tree_test_init(void)
 	basic_check();
 	search_check();
 	intersection_range_check();
+	span_iteration_check();
 
 	kfree(queries);
 	kfree(nodes);
diff --git a/tools/testing/rbtree/Makefile b/tools/testing/rbtree/Makefile
index bac6931b499d..d7bbae2af4c7 100644
--- a/tools/testing/rbtree/Makefile
+++ b/tools/testing/rbtree/Makefile
@@ -3,7 +3,7 @@
 .PHONY: clean
 
 TARGETS = rbtree_test interval_tree_test
-OFILES = $(LIBS) rbtree-shim.o interval_tree-shim.o
+OFILES = $(SHARED_OFILES) rbtree-shim.o interval_tree-shim.o maple-shim.o
 DEPS = ../../../include/linux/rbtree.h \
 	../../../include/linux/rbtree_types.h \
 	../../../include/linux/rbtree_augmented.h \
@@ -25,7 +25,9 @@ $(TARGETS):	$(OFILES)
 rbtree-shim.o: $(DEPS)
 rbtree_test.o:  ../../../lib/rbtree_test.c
 interval_tree-shim.o: $(DEPS)
+interval_tree-shim.o: CFLAGS += -DCONFIG_INTERVAL_TREE_SPAN_ITER
 interval_tree_test.o: 	../../../lib/interval_tree_test.c
+interval_tree_test.o: CFLAGS += -DCONFIG_INTERVAL_TREE_SPAN_ITER
 
 clean:
-	$(RM) $(TARGETS) *.o generated/*
+	$(RM) $(TARGETS) *.o radix-tree.c idr.c generated/*
diff --git a/tools/testing/rbtree/interval_tree_test.c b/tools/testing/rbtree/interval_tree_test.c
index 63775b831c1c..49bc5b534330 100644
--- a/tools/testing/rbtree/interval_tree_test.c
+++ b/tools/testing/rbtree/interval_tree_test.c
@@ -6,6 +6,7 @@
 #include <linux/math64.h>
 #include <linux/kern_levels.h>
 #include "shared.h"
+#include "maple-shared.h"
 
 #include "../../../lib/interval_tree_test.c"
 
@@ -51,6 +52,7 @@ int main(int argc, char **argv)
 			usage();
 	}
 
+	maple_tree_init();
 	interval_tree_tests();
 	return 0;
 }
-- 
2.34.1

[PATCH 6/7] 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>
CC: Matthew Wilcox <willy@infradead.org>
CC: Michel Lespinasse <michel@lespinasse.org>
---
 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

[PATCH 7/7] lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap()

[Wei Yang]

The comment of interval_tree_span_iter_next_gap() is not exact, nodes[1]
is not always !NULL.

There are threes cases here. If there is an interior hole, the statement
is correct. If there is a tailing hole or the contiguous used range span
to the end, nodes[1] is NULL.

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@ziepe.ca>
---
 lib/interval_tree.c | 12 +++++++++---
 1 file changed, 9 insertions(+), 3 deletions(-)

diff --git a/lib/interval_tree.c b/lib/interval_tree.c
index 3412737ff365..87bcdd387d1a 100644
--- a/lib/interval_tree.c
+++ b/lib/interval_tree.c
@@ -20,9 +20,15 @@ EXPORT_SYMBOL_GPL(interval_tree_iter_next);
 /*
  * Roll nodes[1] into nodes[0] by advancing nodes[1] to the end of a contiguous
  * span of nodes. This makes nodes[0]->last the end of that contiguous used span
- * indexes that started at the original nodes[1]->start. nodes[1] is now the
- * first node starting the next used span. A hole span is between nodes[0]->last
- * and nodes[1]->start. nodes[1] must be !NULL.
+ * indexes that started at the original nodes[1]->start.
+ *
+ * If there is an interior hole, nodes[1] is now the first node starting the
+ * next used span. A hole span is between nodes[0]->last and nodes[1]->start.
+ *
+ * If there is a tailing hole, nodes[1] is now NULL. A hole span is between
+ * nodes[0]->last and last_index.
+ *
+ * If the contiguous used range span to last_index, nodes[1] is set to NULL.
  */
 static void
 interval_tree_span_iter_next_gap(struct interval_tree_span_iter *state)
-- 
2.34.1

Re: [PATCH 1/7] lib/rbtree: enable userland test suite for rbtree related data structure

[Matthew Wilcox]

On Tue, Mar 04, 2025 at 01:19:46AM +0000, Wei Yang wrote:
> diff --git a/tools/include/linux/container_of.h b/tools/include/linux/container_of.h
> new file mode 100644
> index 000000000000..9adce874bea9
> --- /dev/null
> +++ b/tools/include/linux/container_of.h
> @@ -0,0 +1,5 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
> +#ifndef _TOOLS_LINUX_CONTAINER_OF_H
> +#define _TOOLS_LINUX_CONTAINER_OF_H
> +
> +#endif	/* _TOOLS_LINUX_CONTAINER_OF_H */

Is there a reason you didn't move container_of() from
tools/include/linux/kernel.h to here?

Re: [PATCH 1/7] lib/rbtree: enable userland test suite for rbtree related data structure

[Wei Yang]

On Tue, Mar 04, 2025 at 01:46:31AM +0000, Matthew Wilcox wrote:
>On Tue, Mar 04, 2025 at 01:19:46AM +0000, Wei Yang wrote:
>> diff --git a/tools/include/linux/container_of.h b/tools/include/linux/container_of.h
>> new file mode 100644
>> index 000000000000..9adce874bea9
>> --- /dev/null
>> +++ b/tools/include/linux/container_of.h
>> @@ -0,0 +1,5 @@
>> +/* SPDX-License-Identifier: GPL-2.0 */
>> +#ifndef _TOOLS_LINUX_CONTAINER_OF_H
>> +#define _TOOLS_LINUX_CONTAINER_OF_H
>> +
>> +#endif	/* _TOOLS_LINUX_CONTAINER_OF_H */
>
>Is there a reason you didn't move container_of() from
>tools/include/linux/kernel.h to here?

Thanks, I would fix this.

-- 
Wei Yang
Help you, Help me

Re: [PATCH 7/7] lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap()

[Jason Gunthorpe]

On Tue, Mar 04, 2025 at 01:19:52AM +0000, Wei Yang wrote:
> The comment of interval_tree_span_iter_next_gap() is not exact, nodes[1]
> is not always !NULL.
> 
> There are threes cases here. If there is an interior hole, the statement
> is correct. If there is a tailing hole or the contiguous used range span
> to the end, nodes[1] is NULL.
> 
> 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@ziepe.ca>
> ---
>  lib/interval_tree.c | 12 +++++++++---
>  1 file changed, 9 insertions(+), 3 deletions(-)

Reviewed-by: Jason Gunthorpe <jgg@nvidia.com>

> @@ -20,9 +20,15 @@ EXPORT_SYMBOL_GPL(interval_tree_iter_next);
>  /*
>   * Roll nodes[1] into nodes[0] by advancing nodes[1] to the end of a contiguous
>   * span of nodes. This makes nodes[0]->last the end of that contiguous used span
> + * indexes that started at the original nodes[1]->start.

"span [of] indexes"

Jason

Re: [PATCH 7/7] lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap()

[Wei Yang]

On Tue, Mar 04, 2025 at 10:12:30AM -0400, Jason Gunthorpe wrote:
>On Tue, Mar 04, 2025 at 01:19:52AM +0000, Wei Yang wrote:
>> The comment of interval_tree_span_iter_next_gap() is not exact, nodes[1]
>> is not always !NULL.
>> 
>> There are threes cases here. If there is an interior hole, the statement
>> is correct. If there is a tailing hole or the contiguous used range span
>> to the end, nodes[1] is NULL.
>> 
>> 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@ziepe.ca>
>> ---
>>  lib/interval_tree.c | 12 +++++++++---
>>  1 file changed, 9 insertions(+), 3 deletions(-)
>
>Reviewed-by: Jason Gunthorpe <jgg@nvidia.com>
>

Thanks

>> @@ -20,9 +20,15 @@ EXPORT_SYMBOL_GPL(interval_tree_iter_next);
>>  /*
>>   * Roll nodes[1] into nodes[0] by advancing nodes[1] to the end of a contiguous
>>   * span of nodes. This makes nodes[0]->last the end of that contiguous used span
>> + * indexes that started at the original nodes[1]->start.
>
>"span [of] indexes"
>

Ok, will add this "of".

>Jason

-- 
Wei Yang
Help you, Help me

Re: [PATCH 3/7] lib/rbtree: add random seed

[kernel test robot]

Hi Wei,

kernel test robot noticed the following build warnings:

[auto build test WARNING on linus/master]
[also build test WARNING on v6.14-rc5 next-20250304]
[cannot apply to akpm-mm/mm-nonmm-unstable akpm-mm/mm-everything]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Wei-Yang/lib-rbtree-enable-userland-test-suite-for-rbtree-related-data-structure/20250304-092345
base:   linus/master
patch link:    https://lore.kernel.org/r/20250304011952.29182-4-richard.weiyang%40gmail.com
patch subject: [PATCH 3/7] lib/rbtree: add random seed
config: i386-buildonly-randconfig-004-20250305 (https://download.01.org/0day-ci/archive/20250305/202503051009.iTp8hlJy-lkp@intel.com/config)
compiler: clang version 19.1.7 (https://github.com/llvm/llvm-project cd708029e0b2869e80abe31ddb175f7c35361f90)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250305/202503051009.iTp8hlJy-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202503051009.iTp8hlJy-lkp@intel.com/

All warnings (new ones prefixed by >>):

>> lib/rbtree_test.c:17:22: warning: implicit conversion from 'unsigned long long' to 'ulong' (aka 'unsigned long') changes value from 3141592653589793238 to 2721204694 [-Wconstant-conversion]
      17 | __param(ulong, seed, 3141592653589793238ULL, "Random seed");
         |                ~~~~  ^~~~~~~~~~~~~~~~~~~~~~
   lib/rbtree_test.c:10:21: note: expanded from macro '__param'
      10 |         static type name = init;                \
         |                     ~~~~   ^~~~
   1 warning generated.
--
>> lib/interval_tree_test.c:22:22: warning: implicit conversion from 'unsigned long long' to 'ulong' (aka 'unsigned long') changes value from 3141592653589793238 to 2721204694 [-Wconstant-conversion]
      22 | __param(ulong, seed, 3141592653589793238ULL, "Random seed");
         |                ~~~~  ^~~~~~~~~~~~~~~~~~~~~~
   lib/interval_tree_test.c:10:21: note: expanded from macro '__param'
      10 |         static type name = init;                \
         |                     ~~~~   ^~~~
   1 warning generated.


vim +17 lib/rbtree_test.c

     8	
     9	#define __param(type, name, init, msg)		\
    10		static type name = init;		\
    11		module_param(name, type, 0444);		\
    12		MODULE_PARM_DESC(name, msg);
    13	
    14	__param(int, nnodes, 100, "Number of nodes in the rb-tree");
    15	__param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");
    16	__param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");
  > 17	__param(ulong, seed, 3141592653589793238ULL, "Random seed");
    18	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH 3/7] lib/rbtree: add random seed

[Wei Yang]

On Wed, Mar 05, 2025 at 11:05:13AM +0800, kernel test robot wrote:
>Hi Wei,
>
>kernel test robot noticed the following build warnings:
>
>[auto build test WARNING on linus/master]
>[also build test WARNING on v6.14-rc5 next-20250304]
>[cannot apply to akpm-mm/mm-nonmm-unstable akpm-mm/mm-everything]
>[If your patch is applied to the wrong git tree, kindly drop us a note.
>And when submitting patch, we suggest to use '--base' as documented in
>https://git-scm.com/docs/git-format-patch#_base_tree_information]
>
>url:    https://github.com/intel-lab-lkp/linux/commits/Wei-Yang/lib-rbtree-enable-userland-test-suite-for-rbtree-related-data-structure/20250304-092345
>base:   linus/master
>patch link:    https://lore.kernel.org/r/20250304011952.29182-4-richard.weiyang%40gmail.com
>patch subject: [PATCH 3/7] lib/rbtree: add random seed
>config: i386-buildonly-randconfig-004-20250305 (https://download.01.org/0day-ci/archive/20250305/202503051009.iTp8hlJy-lkp@intel.com/config)
>compiler: clang version 19.1.7 (https://github.com/llvm/llvm-project cd708029e0b2869e80abe31ddb175f7c35361f90)
>reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250305/202503051009.iTp8hlJy-lkp@intel.com/reproduce)
>
>If you fix the issue in a separate patch/commit (i.e. not just a new version of
>the same patch/commit), kindly add following tags
>| Reported-by: kernel test robot <lkp@intel.com>
>| Closes: https://lore.kernel.org/oe-kbuild-all/202503051009.iTp8hlJy-lkp@intel.com/
>
>All warnings (new ones prefixed by >>):
>
>>> lib/rbtree_test.c:17:22: warning: implicit conversion from 'unsigned long long' to 'ulong' (aka 'unsigned long') changes value from 3141592653589793238 to 2721204694 [-Wconstant-conversion]
>      17 | __param(ulong, seed, 3141592653589793238ULL, "Random seed");
>         |                ~~~~  ^~~~~~~~~~~~~~~~~~~~~~
>   lib/rbtree_test.c:10:21: note: expanded from macro '__param'
>      10 |         static type name = init;                \
>         |                     ~~~~   ^~~~
>   1 warning generated.
>--
>>> lib/interval_tree_test.c:22:22: warning: implicit conversion from 'unsigned long long' to 'ulong' (aka 'unsigned long') changes value from 3141592653589793238 to 2721204694 [-Wconstant-conversion]
>      22 | __param(ulong, seed, 3141592653589793238ULL, "Random seed");
>         |                ~~~~  ^~~~~~~~~~~~~~~~~~~~~~
>   lib/interval_tree_test.c:10:21: note: expanded from macro '__param'
>      10 |         static type name = init;                \
>         |                     ~~~~   ^~~~
>   1 warning generated.
>
>
>vim +17 lib/rbtree_test.c
>
>     8	
>     9	#define __param(type, name, init, msg)		\
>    10		static type name = init;		\
>    11		module_param(name, type, 0444);		\
>    12		MODULE_PARM_DESC(name, msg);
>    13	
>    14	__param(int, nnodes, 100, "Number of nodes in the rb-tree");
>    15	__param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");
>    16	__param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");
>  > 17	__param(ulong, seed, 3141592653589793238ULL, "Random seed");
>    18	

Thanks, will fix it.

>
>-- 
>0-DAY CI Kernel Test Service
>https://github.com/intel/lkp-tests/wiki

-- 
Wei Yang
Help you, Help me

Re: [PATCH 3/7] lib/rbtree: add random seed

[kernel test robot]

Hi Wei,

kernel test robot noticed the following build warnings:

[auto build test WARNING on linus/master]
[also build test WARNING on v6.14-rc5 next-20250306]
[cannot apply to akpm-mm/mm-nonmm-unstable akpm-mm/mm-everything]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Wei-Yang/lib-rbtree-enable-userland-test-suite-for-rbtree-related-data-structure/20250304-092345
base:   linus/master
patch link:    https://lore.kernel.org/r/20250304011952.29182-4-richard.weiyang%40gmail.com
patch subject: [PATCH 3/7] lib/rbtree: add random seed
config: csky-randconfig-002-20250305 (https://download.01.org/0day-ci/archive/20250306/202503061924.hFdFosTG-lkp@intel.com/config)
compiler: csky-linux-gcc (GCC) 14.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250306/202503061924.hFdFosTG-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202503061924.hFdFosTG-lkp@intel.com/

All warnings (new ones prefixed by >>):

>> lib/interval_tree_test.c:22:22: warning: conversion from 'long long unsigned int' to 'ulong' {aka 'long unsigned int'} changes value from '3141592653589793238' to '2721204694' [-Woverflow]
      22 | __param(ulong, seed, 3141592653589793238ULL, "Random seed");
         |                      ^~~~~~~~~~~~~~~~~~~~~~
   lib/interval_tree_test.c:10:28: note: in definition of macro '__param'
      10 |         static type name = init;                \
         |                            ^~~~
--
>> lib/rbtree_test.c:17:22: warning: conversion from 'long long unsigned int' to 'ulong' {aka 'long unsigned int'} changes value from '3141592653589793238' to '2721204694' [-Woverflow]
      17 | __param(ulong, seed, 3141592653589793238ULL, "Random seed");
         |                      ^~~~~~~~~~~~~~~~~~~~~~
   lib/rbtree_test.c:10:28: note: in definition of macro '__param'
      10 |         static type name = init;                \
         |                            ^~~~


vim +22 lib/interval_tree_test.c

    20	
    21	__param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint");
  > 22	__param(ulong, seed, 3141592653589793238ULL, "Random seed");
    23	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH 3/7] lib/rbtree: add random seed

[Wei Yang]

On Thu, Mar 06, 2025 at 07:34:21PM +0800, kernel test robot wrote:
>Hi Wei,
>
>kernel test robot noticed the following build warnings:
>
>[auto build test WARNING on linus/master]
>[also build test WARNING on v6.14-rc5 next-20250306]
>[cannot apply to akpm-mm/mm-nonmm-unstable akpm-mm/mm-everything]
>[If your patch is applied to the wrong git tree, kindly drop us a note.
>And when submitting patch, we suggest to use '--base' as documented in
>https://git-scm.com/docs/git-format-patch#_base_tree_information]
>
>url:    https://github.com/intel-lab-lkp/linux/commits/Wei-Yang/lib-rbtree-enable-userland-test-suite-for-rbtree-related-data-structure/20250304-092345
>base:   linus/master
>patch link:    https://lore.kernel.org/r/20250304011952.29182-4-richard.weiyang%40gmail.com
>patch subject: [PATCH 3/7] lib/rbtree: add random seed
>config: csky-randconfig-002-20250305 (https://download.01.org/0day-ci/archive/20250306/202503061924.hFdFosTG-lkp@intel.com/config)
>compiler: csky-linux-gcc (GCC) 14.2.0
>reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250306/202503061924.hFdFosTG-lkp@intel.com/reproduce)
>
>If you fix the issue in a separate patch/commit (i.e. not just a new version of
>the same patch/commit), kindly add following tags
>| Reported-by: kernel test robot <lkp@intel.com>
>| Closes: https://lore.kernel.org/oe-kbuild-all/202503061924.hFdFosTG-lkp@intel.com/
>
>All warnings (new ones prefixed by >>):
>
>>> lib/interval_tree_test.c:22:22: warning: conversion from 'long long unsigned int' to 'ulong' {aka 'long unsigned int'} changes value from '3141592653589793238' to '2721204694' [-Woverflow]
>      22 | __param(ulong, seed, 3141592653589793238ULL, "Random seed");
>         |                      ^~~~~~~~~~~~~~~~~~~~~~
>   lib/interval_tree_test.c:10:28: note: in definition of macro '__param'
>      10 |         static type name = init;                \
>         |                            ^~~~
>--
>>> lib/rbtree_test.c:17:22: warning: conversion from 'long long unsigned int' to 'ulong' {aka 'long unsigned int'} changes value from '3141592653589793238' to '2721204694' [-Woverflow]
>      17 | __param(ulong, seed, 3141592653589793238ULL, "Random seed");
>         |                      ^~~~~~~~~~~~~~~~~~~~~~
>   lib/rbtree_test.c:10:28: note: in definition of macro '__param'
>      10 |         static type name = init;                \
>         |                            ^~~~
>
>
>vim +22 lib/interval_tree_test.c
>
>    20	
>    21	__param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint");
>  > 22	__param(ulong, seed, 3141592653589793238ULL, "Random seed");
>    23	
>

Thanks for reporting. I went through the mail list, it seems I need send a diff
reply here.

Since we already have proper definition of param_xxx_ullong(), I choose
following fix. If any comment, just let me know.

Thanks

diff --git a/include/linux/types.h b/include/linux/types.h
index a3d2182c2686..49b79c8bb1a9 100644
--- a/include/linux/types.h
+++ b/include/linux/types.h
@@ -92,6 +92,7 @@ typedef unsigned char		unchar;
 typedef unsigned short		ushort;
 typedef unsigned int		uint;
 typedef unsigned long		ulong;
+typedef unsigned long long	ullong;
 
 #ifndef __BIT_TYPES_DEFINED__
 #define __BIT_TYPES_DEFINED__
diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c
index 37198afa87ed..5fd62656f42e 100644
--- a/lib/interval_tree_test.c
+++ b/lib/interval_tree_test.c
@@ -21,7 +21,7 @@ __param(int, search_loops, 1000, "Number of iterations searching the tree");
 __param(bool, search_all, false, "Searches will iterate all nodes in the tree");
 
 __param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint");
-__param(ulong, seed, 3141592653589793238ULL, "Random seed");
+__param(ullong, seed, 3141592653589793238ULL, "Random seed");
 
 static struct rb_root_cached root = RB_ROOT_CACHED;
 static struct interval_tree_node *nodes = NULL;
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index 94ace8f0fbf8..690cede46ac2 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -14,7 +14,7 @@
 __param(int, nnodes, 100, "Number of nodes in the rb-tree");
 __param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");
 __param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");
-__param(ulong, seed, 3141592653589793238ULL, "Random seed");
+__param(ullong, seed, 3141592653589793238ULL, "Random seed");
 
 struct test_node {
 	u32 key;
diff --git a/tools/include/linux/types.h b/tools/include/linux/types.h
index 8519386acd23..4928e33d44ac 100644
--- a/tools/include/linux/types.h
+++ b/tools/include/linux/types.h
@@ -42,6 +42,8 @@ typedef __s16 s16;
 typedef __u8  u8;
 typedef __s8  s8;
 
+typedef unsigned long long	ullong;
+
 #ifdef __CHECKER__
 #define __bitwise	__attribute__((bitwise))
 #else

-- 
Wei Yang
Help you, Help me

Re: [PATCH 3/7] lib/rbtree: add random seed

[kernel test robot]

Hi Wei,

kernel test robot noticed the following build warnings:

[auto build test WARNING on linus/master]
[also build test WARNING on v6.14-rc5 next-20250306]
[cannot apply to akpm-mm/mm-nonmm-unstable akpm-mm/mm-everything]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Wei-Yang/lib-rbtree-enable-userland-test-suite-for-rbtree-related-data-structure/20250304-092345
base:   linus/master
patch link:    https://lore.kernel.org/r/20250304011952.29182-4-richard.weiyang%40gmail.com
patch subject: [PATCH 3/7] lib/rbtree: add random seed
config: riscv-randconfig-r133-20250307 (https://download.01.org/0day-ci/archive/20250307/202503071016.2u0gPG0V-lkp@intel.com/config)
compiler: clang version 16.0.6 (https://github.com/llvm/llvm-project 7cbf1a2591520c2491aa35339f227775f4d3adf6)
reproduce: (https://download.01.org/0day-ci/archive/20250307/202503071016.2u0gPG0V-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202503071016.2u0gPG0V-lkp@intel.com/

sparse warnings: (new ones prefixed by >>)
>> lib/interval_tree_test.c:22:1: sparse: sparse: cast truncates bits from constant value (2b992ddfa23249d6 becomes a23249d6)
   lib/interval_tree_test.c: note: in included file (through include/linux/timex.h, include/linux/time32.h, include/linux/time.h, ...):
   arch/riscv/include/asm/timex.h:25:16: sparse: sparse: cast removes address space '__iomem' of expression
   arch/riscv/include/asm/timex.h:25:16: sparse: sparse: incorrect type in argument 1 (different address spaces) @@     expected void const volatile [noderef] __iomem *addr @@     got unsigned int [usertype] * @@
   arch/riscv/include/asm/timex.h:25:16: sparse:     expected void const volatile [noderef] __iomem *addr
   arch/riscv/include/asm/timex.h:25:16: sparse:     got unsigned int [usertype] *
   arch/riscv/include/asm/timex.h:25:16: sparse: sparse: incorrect type in argument 1 (different address spaces) @@     expected void const volatile [noderef] __iomem *addr @@     got unsigned int [usertype] * @@
   arch/riscv/include/asm/timex.h:25:16: sparse:     expected void const volatile [noderef] __iomem *addr
   arch/riscv/include/asm/timex.h:25:16: sparse:     got unsigned int [usertype] *
   arch/riscv/include/asm/timex.h:25:16: sparse: sparse: incorrect type in argument 1 (different address spaces) @@     expected void const volatile [noderef] __iomem *addr @@     got unsigned int [usertype] * @@
   arch/riscv/include/asm/timex.h:25:16: sparse:     expected void const volatile [noderef] __iomem *addr
   arch/riscv/include/asm/timex.h:25:16: sparse:     got unsigned int [usertype] *
   arch/riscv/include/asm/timex.h:25:16: sparse: sparse: incorrect type in argument 1 (different address spaces) @@     expected void const volatile [noderef] __iomem *addr @@     got unsigned int [usertype] * @@
   arch/riscv/include/asm/timex.h:25:16: sparse:     expected void const volatile [noderef] __iomem *addr
   arch/riscv/include/asm/timex.h:25:16: sparse:     got unsigned int [usertype] *

vim +22 lib/interval_tree_test.c

    20	
    21	__param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint");
  > 22	__param(ulong, seed, 3141592653589793238ULL, "Random seed");
    23	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki