From 4164e1525d37d463bbd0a808709fd75abcfc89a5 Mon Sep 17 00:00:00 2001 From: Wei Yang Date: Mon, 10 Mar 2025 07:49:32 +0000 Subject: lib/rbtree: enable userland test suite for rbtree related data structure Patch series "lib/interval_tree: add some test cases and cleanup", v2. Since rbtree/augmented tree/interval tree share similar data structure, besides new cases for interval tree, this patch set also does cleanup for others. This patch (of 7): 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. Link: https://lkml.kernel.org/r/20250310074938.26756-1-richard.weiyang@gmail.com Link: https://lkml.kernel.org/r/20250310074938.26756-2-richard.weiyang@gmail.com Signed-off-by: Wei Yang Cc: Matthew Wilcox Cc: Michel Lespinasse Cc: Jason Gunthorpe Signed-off-by: Andrew Morton --- tools/testing/rbtree/interval_tree_test.c | 53 +++++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) create mode 100644 tools/testing/rbtree/interval_tree_test.c (limited to 'tools/testing/rbtree/interval_tree_test.c') 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 + */ +#include +#include +#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; +} -- cgit v1.2.3-59-g8ed1b From 16b1936ae6d1858252413bf4bae8bcf247eb4b4c Mon Sep 17 00:00:00 2001 From: Wei Yang Date: Mon, 10 Mar 2025 07:49:34 +0000 Subject: lib/rbtree: add random seed 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. Link: https://lkml.kernel.org/r/20250310074938.26756-4-richard.weiyang@gmail.com Signed-off-by: Wei Yang Cc: Matthew Wilcox Cc: Michel Lespinasse Cc: Jason Gunthorpe Signed-off-by: Andrew Morton --- include/linux/types.h | 1 + lib/interval_tree_test.c | 3 ++- lib/rbtree_test.c | 3 ++- tools/include/linux/types.h | 2 ++ tools/testing/rbtree/interval_tree_test.c | 5 ++++- tools/testing/rbtree/rbtree_test.c | 5 ++++- 6 files changed, 15 insertions(+), 4 deletions(-) (limited to 'tools/testing/rbtree/interval_tree_test.c') diff --git a/include/linux/types.h b/include/linux/types.h index 1c509ce8f7f6..864ab701f297 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 12880d772945..51863077d4ec 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(ullong, 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..690cede46ac2 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(ullong, 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/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 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(); } -- cgit v1.2.3-59-g8ed1b From ccaf3efceefc2c3abc6c23277d5a93238efa5c58 Mon Sep 17 00:00:00 2001 From: Wei Yang Date: Mon, 10 Mar 2025 07:49:36 +0000 Subject: lib/interval_tree: add test case for span iteration Verify interval_tree_span_iter_xxx() helpers works as expected. Link: https://lkml.kernel.org/r/20250310074938.26756-6-richard.weiyang@gmail.com Signed-off-by: Wei Yang Cc: Matthew Wilcox Cc: Michel Lespinasse Cc: Jason Gunthorpe Signed-off-by: Andrew Morton --- 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(-) (limited to 'tools/testing/rbtree/interval_tree_test.c') diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 7821379e2c21..5fd62656f42e 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -6,6 +6,7 @@ #include #include #include +#include #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 #include #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; } -- cgit v1.2.3-59-g8ed1b