* [PATCH 1/7] lib/rbtree: enable userland test suite for rbtree related data structure
2025-03-04 1:19 [PATCH 0/7] lib/interval_tree: add some test cases and cleanup Wei Yang
@ 2025-03-04 1:19 ` Wei Yang
2025-03-04 1:46 ` Matthew Wilcox
2025-03-04 1:19 ` [PATCH 2/7] lib/rbtree: split tests Wei Yang
` (5 subsequent siblings)
6 siblings, 1 reply; 17+ messages in thread
From: Wei Yang @ 2025-03-04 1:19 UTC (permalink / raw)
To: akpm; +Cc: willy, michel, linux-mm, 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
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH 1/7] lib/rbtree: enable userland test suite for rbtree related data structure
2025-03-04 1:19 ` [PATCH 1/7] lib/rbtree: enable userland test suite for rbtree related data structure Wei Yang
@ 2025-03-04 1:46 ` Matthew Wilcox
2025-03-04 3:04 ` Wei Yang
0 siblings, 1 reply; 17+ messages in thread
From: Matthew Wilcox @ 2025-03-04 1:46 UTC (permalink / raw)
To: Wei Yang; +Cc: akpm, michel, linux-mm
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?
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH 1/7] lib/rbtree: enable userland test suite for rbtree related data structure
2025-03-04 1:46 ` Matthew Wilcox
@ 2025-03-04 3:04 ` Wei Yang
0 siblings, 0 replies; 17+ messages in thread
From: Wei Yang @ 2025-03-04 3:04 UTC (permalink / raw)
To: Matthew Wilcox; +Cc: Wei Yang, akpm, michel, linux-mm
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH 2/7] lib/rbtree: split tests
2025-03-04 1:19 [PATCH 0/7] lib/interval_tree: add some test cases and cleanup Wei Yang
2025-03-04 1:19 ` [PATCH 1/7] lib/rbtree: enable userland test suite for rbtree related data structure Wei Yang
@ 2025-03-04 1:19 ` Wei Yang
2025-03-04 1:19 ` [PATCH 3/7] lib/rbtree: add random seed Wei Yang
` (4 subsequent siblings)
6 siblings, 0 replies; 17+ messages in thread
From: Wei Yang @ 2025-03-04 1:19 UTC (permalink / raw)
To: akpm; +Cc: willy, michel, linux-mm, 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
^ permalink raw reply [flat|nested] 17+ messages in thread* [PATCH 3/7] lib/rbtree: add random seed
2025-03-04 1:19 [PATCH 0/7] lib/interval_tree: add some test cases and cleanup Wei Yang
2025-03-04 1:19 ` [PATCH 1/7] lib/rbtree: enable userland test suite for rbtree related data structure Wei Yang
2025-03-04 1:19 ` [PATCH 2/7] lib/rbtree: split tests Wei Yang
@ 2025-03-04 1:19 ` Wei Yang
2025-03-05 3:05 ` kernel test robot
` (2 more replies)
2025-03-04 1:19 ` [PATCH 4/7] lib/interval_tree: add test case for interval_tree_iter_xxx() helpers Wei Yang
` (3 subsequent siblings)
6 siblings, 3 replies; 17+ messages in thread
From: Wei Yang @ 2025-03-04 1:19 UTC (permalink / raw)
To: akpm; +Cc: willy, michel, linux-mm, 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
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH 3/7] lib/rbtree: add random seed
2025-03-04 1:19 ` [PATCH 3/7] lib/rbtree: add random seed Wei Yang
@ 2025-03-05 3:05 ` kernel test robot
2025-03-05 9:10 ` Wei Yang
2025-03-06 11:34 ` kernel test robot
2025-03-07 2:36 ` kernel test robot
2 siblings, 1 reply; 17+ messages in thread
From: kernel test robot @ 2025-03-05 3:05 UTC (permalink / raw)
To: Wei Yang, akpm; +Cc: llvm, oe-kbuild-all, willy, michel, linux-mm, Wei Yang
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
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH 3/7] lib/rbtree: add random seed
2025-03-05 3:05 ` kernel test robot
@ 2025-03-05 9:10 ` Wei Yang
0 siblings, 0 replies; 17+ messages in thread
From: Wei Yang @ 2025-03-05 9:10 UTC (permalink / raw)
To: kernel test robot
Cc: Wei Yang, akpm, llvm, oe-kbuild-all, willy, michel, linux-mm
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH 3/7] lib/rbtree: add random seed
2025-03-04 1:19 ` [PATCH 3/7] lib/rbtree: add random seed Wei Yang
2025-03-05 3:05 ` kernel test robot
@ 2025-03-06 11:34 ` kernel test robot
2025-03-07 1:55 ` Wei Yang
2025-03-07 2:36 ` kernel test robot
2 siblings, 1 reply; 17+ messages in thread
From: kernel test robot @ 2025-03-06 11:34 UTC (permalink / raw)
To: Wei Yang, akpm; +Cc: oe-kbuild-all, willy, michel, linux-mm, Wei Yang
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
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH 3/7] lib/rbtree: add random seed
2025-03-06 11:34 ` kernel test robot
@ 2025-03-07 1:55 ` Wei Yang
0 siblings, 0 replies; 17+ messages in thread
From: Wei Yang @ 2025-03-07 1:55 UTC (permalink / raw)
To: kernel test robot; +Cc: Wei Yang, akpm, oe-kbuild-all, willy, michel, linux-mm
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH 3/7] lib/rbtree: add random seed
2025-03-04 1:19 ` [PATCH 3/7] lib/rbtree: add random seed Wei Yang
2025-03-05 3:05 ` kernel test robot
2025-03-06 11:34 ` kernel test robot
@ 2025-03-07 2:36 ` kernel test robot
2 siblings, 0 replies; 17+ messages in thread
From: kernel test robot @ 2025-03-07 2:36 UTC (permalink / raw)
To: Wei Yang, akpm; +Cc: oe-kbuild-all, willy, michel, linux-mm, Wei Yang
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* [PATCH 4/7] lib/interval_tree: add test case for interval_tree_iter_xxx() helpers
2025-03-04 1:19 [PATCH 0/7] lib/interval_tree: add some test cases and cleanup Wei Yang
` (2 preceding siblings ...)
2025-03-04 1:19 ` [PATCH 3/7] lib/rbtree: add random seed Wei Yang
@ 2025-03-04 1:19 ` Wei Yang
2025-03-04 1:19 ` [PATCH 5/7] lib/interval_tree: add test case for span iteration Wei Yang
` (2 subsequent siblings)
6 siblings, 0 replies; 17+ messages in thread
From: Wei Yang @ 2025-03-04 1:19 UTC (permalink / raw)
To: akpm; +Cc: willy, michel, linux-mm, 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
^ permalink raw reply [flat|nested] 17+ messages in thread* [PATCH 5/7] lib/interval_tree: add test case for span iteration
2025-03-04 1:19 [PATCH 0/7] lib/interval_tree: add some test cases and cleanup Wei Yang
` (3 preceding siblings ...)
2025-03-04 1:19 ` [PATCH 4/7] lib/interval_tree: add test case for interval_tree_iter_xxx() helpers Wei Yang
@ 2025-03-04 1:19 ` Wei Yang
2025-03-04 1:19 ` [PATCH 6/7] lib/interval_tree: skip the check before go to the right subtree Wei Yang
2025-03-04 1:19 ` [PATCH 7/7] lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap() Wei Yang
6 siblings, 0 replies; 17+ messages in thread
From: Wei Yang @ 2025-03-04 1:19 UTC (permalink / raw)
To: akpm; +Cc: willy, michel, linux-mm, 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
^ permalink raw reply [flat|nested] 17+ messages in thread* [PATCH 6/7] lib/interval_tree: skip the check before go to the right subtree
2025-03-04 1:19 [PATCH 0/7] lib/interval_tree: add some test cases and cleanup Wei Yang
` (4 preceding siblings ...)
2025-03-04 1:19 ` [PATCH 5/7] lib/interval_tree: add test case for span iteration Wei Yang
@ 2025-03-04 1:19 ` Wei Yang
2025-03-04 1:19 ` [PATCH 7/7] lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap() Wei Yang
6 siblings, 0 replies; 17+ messages in thread
From: Wei Yang @ 2025-03-04 1:19 UTC (permalink / raw)
To: akpm; +Cc: willy, michel, linux-mm, 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
^ permalink raw reply [flat|nested] 17+ messages in thread* [PATCH 7/7] lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap()
2025-03-04 1:19 [PATCH 0/7] lib/interval_tree: add some test cases and cleanup Wei Yang
` (5 preceding siblings ...)
2025-03-04 1:19 ` [PATCH 6/7] lib/interval_tree: skip the check before go to the right subtree Wei Yang
@ 2025-03-04 1:19 ` Wei Yang
2025-03-04 14:12 ` Jason Gunthorpe
6 siblings, 1 reply; 17+ messages in thread
From: Wei Yang @ 2025-03-04 1:19 UTC (permalink / raw)
To: akpm; +Cc: willy, michel, linux-mm, Wei Yang, Jason Gunthorpe
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
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH 7/7] lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap()
2025-03-04 1:19 ` [PATCH 7/7] lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap() Wei Yang
@ 2025-03-04 14:12 ` Jason Gunthorpe
2025-03-05 0:57 ` Wei Yang
0 siblings, 1 reply; 17+ messages in thread
From: Jason Gunthorpe @ 2025-03-04 14:12 UTC (permalink / raw)
To: Wei Yang; +Cc: akpm, willy, michel, linux-mm
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
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH 7/7] lib/interval_tree: fix the comment of interval_tree_span_iter_next_gap()
2025-03-04 14:12 ` Jason Gunthorpe
@ 2025-03-05 0:57 ` Wei Yang
0 siblings, 0 replies; 17+ messages in thread
From: Wei Yang @ 2025-03-05 0:57 UTC (permalink / raw)
To: Jason Gunthorpe; +Cc: Wei Yang, akpm, willy, michel, linux-mm
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
^ permalink raw reply [flat|nested] 17+ messages in thread