From a54dae0338b7f01eb0f9c7571fb9b74f791d1c6b Mon Sep 17 00:00:00 2001 From: Davidlohr Bueso Date: Mon, 10 Jul 2017 15:51:46 -0700 Subject: lib/interval_tree_test.c: make test options module parameters Allows for more flexible debugging. Link: http://lkml.kernel.org/r/20170518174936.20265-3-dave@stgolabs.net Signed-off-by: Davidlohr Bueso Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/interval_tree_test.c | 57 +++++++++++++++++++++++++++++++++--------------- 1 file changed, 40 insertions(+), 17 deletions(-) (limited to 'lib/interval_tree_test.c') diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 245900b98c8e..1093f0496d5e 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -1,16 +1,25 @@ #include +#include #include #include +#include #include -#define NODES 100 -#define PERF_LOOPS 100000 -#define SEARCHES 100 -#define SEARCH_LOOPS 10000 +#define __param(type, name, init, msg) \ + static type name = init; \ + module_param(name, type, 0444); \ + MODULE_PARM_DESC(name, msg); + +__param(int, nnodes, 100, "Number of nodes in the interval tree"); +__param(int, perf_loops, 100000, "Number of iterations modifying the tree"); + +__param(int, nsearches, 100, "Number of searches to the interval tree"); +__param(int, search_loops, 10000, "Number of iterations searching the tree"); + static struct rb_root root = RB_ROOT; -static struct interval_tree_node nodes[NODES]; -static u32 queries[SEARCHES]; +static struct interval_tree_node *nodes = NULL; +static u32 *queries = NULL; static struct rnd_state rnd; @@ -29,7 +38,8 @@ search(unsigned long query, struct rb_root *root) static void init(void) { int i; - for (i = 0; i < NODES; i++) { + + for (i = 0; i < nnodes; i++) { u32 a = prandom_u32_state(&rnd); u32 b = prandom_u32_state(&rnd); if (a <= b) { @@ -40,7 +50,7 @@ static void init(void) nodes[i].last = a; } } - for (i = 0; i < SEARCHES; i++) + for (i = 0; i < nsearches; i++) queries[i] = prandom_u32_state(&rnd); } @@ -50,6 +60,16 @@ static int interval_tree_test_init(void) unsigned long results; cycles_t time1, time2, time; + nodes = kmalloc(nnodes * sizeof(struct interval_tree_node), GFP_KERNEL); + if (!nodes) + return -ENOMEM; + + queries = kmalloc(nsearches * sizeof(int), GFP_KERNEL); + if (!queries) { + kfree(nodes); + return -ENOMEM; + } + printk(KERN_ALERT "interval tree insert/remove"); prandom_seed_state(&rnd, 3141592653589793238ULL); @@ -57,39 +77,42 @@ static int interval_tree_test_init(void) time1 = get_cycles(); - for (i = 0; i < PERF_LOOPS; i++) { - for (j = 0; j < NODES; j++) + for (i = 0; i < perf_loops; i++) { + for (j = 0; j < nnodes; j++) interval_tree_insert(nodes + j, &root); - for (j = 0; j < NODES; j++) + for (j = 0; j < nnodes; j++) interval_tree_remove(nodes + j, &root); } time2 = get_cycles(); time = time2 - time1; - time = div_u64(time, PERF_LOOPS); + time = div_u64(time, perf_loops); printk(" -> %llu cycles\n", (unsigned long long)time); printk(KERN_ALERT "interval tree search"); - for (j = 0; j < NODES; j++) + for (j = 0; j < nnodes; j++) interval_tree_insert(nodes + j, &root); time1 = get_cycles(); results = 0; - for (i = 0; i < SEARCH_LOOPS; i++) - for (j = 0; j < SEARCHES; j++) + for (i = 0; i < search_loops; i++) + for (j = 0; j < nsearches; j++) results += search(queries[j], &root); time2 = get_cycles(); time = time2 - time1; - time = div_u64(time, SEARCH_LOOPS); - results = div_u64(results, SEARCH_LOOPS); + time = div_u64(time, search_loops); + results = div_u64(results, search_loops); printk(" -> %llu cycles (%lu results)\n", (unsigned long long)time, results); + kfree(queries); + kfree(nodes); + return -EAGAIN; /* Fail will directly unload the module */ } -- cgit From a8ec14d4f6aa8e245efacc992c8ee6ea0464ce2a Mon Sep 17 00:00:00 2001 From: Davidlohr Bueso Date: Mon, 10 Jul 2017 15:51:49 -0700 Subject: lib/interval_tree_test.c: allow users to limit scope of endpoint Add a 'max_endpoint' parameter such that users may easily limit the size of the intervals that are randomly generated. Link: http://lkml.kernel.org/r/20170518174936.20265-4-dave@stgolabs.net Signed-off-by: Davidlohr Bueso Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/interval_tree_test.c | 23 +++++++++++++---------- 1 file changed, 13 insertions(+), 10 deletions(-) (limited to 'lib/interval_tree_test.c') diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 1093f0496d5e..0fef6364a958 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -16,6 +16,7 @@ __param(int, perf_loops, 100000, "Number of iterations modifying the tree"); __param(int, nsearches, 100, "Number of searches to the interval tree"); __param(int, search_loops, 10000, "Number of iterations searching the tree"); +__param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint"); static struct rb_root root = RB_ROOT; static struct interval_tree_node *nodes = NULL; @@ -40,18 +41,20 @@ static void init(void) int i; for (i = 0; i < nnodes; i++) { - u32 a = prandom_u32_state(&rnd); - u32 b = prandom_u32_state(&rnd); - if (a <= b) { - nodes[i].start = a; - nodes[i].last = b; - } else { - nodes[i].start = b; - nodes[i].last = a; - } + u32 b = (prandom_u32_state(&rnd) >> 4) % max_endpoint; + u32 a = (prandom_u32_state(&rnd) >> 4) % b; + + nodes[i].start = a; + nodes[i].last = b; } + + /* + * Limit the search scope to what the user defined. + * Otherwise we are merely measuring empty walks, + * which is pointless. + */ for (i = 0; i < nsearches; i++) - queries[i] = prandom_u32_state(&rnd); + queries[i] = (prandom_u32_state(&rnd) >> 4) % max_endpoint; } static int interval_tree_test_init(void) -- cgit From c46ecce431ebe6b1a9551d1f530eb432dae5c39b Mon Sep 17 00:00:00 2001 From: Davidlohr Bueso Date: Mon, 10 Jul 2017 15:51:52 -0700 Subject: lib/interval_tree_test.c: allow full tree search ... such that a user can specify visiting all the nodes in the tree (intersects with the world). This is a nice opposite from the very basic default query which is a single point. Link: http://lkml.kernel.org/r/20170518174936.20265-5-dave@stgolabs.net Signed-off-by: Davidlohr Bueso Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/interval_tree_test.c | 15 ++++++++++----- 1 file changed, 10 insertions(+), 5 deletions(-) (limited to 'lib/interval_tree_test.c') diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 0fef6364a958..df495fe81421 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -15,6 +15,7 @@ __param(int, perf_loops, 100000, "Number of iterations modifying the tree"); __param(int, nsearches, 100, "Number of searches to the interval tree"); __param(int, search_loops, 10000, "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"); @@ -25,13 +26,13 @@ static u32 *queries = NULL; static struct rnd_state rnd; static inline unsigned long -search(unsigned long query, struct rb_root *root) +search(struct rb_root *root, unsigned long start, unsigned long last) { struct interval_tree_node *node; unsigned long results = 0; - for (node = interval_tree_iter_first(root, query, query); node; - node = interval_tree_iter_next(node, query, query)) + for (node = interval_tree_iter_first(root, start, last); node; + node = interval_tree_iter_next(node, start, last)) results++; return results; } @@ -102,8 +103,12 @@ static int interval_tree_test_init(void) results = 0; for (i = 0; i < search_loops; i++) - for (j = 0; j < nsearches; j++) - results += search(queries[j], &root); + for (j = 0; j < nsearches; j++) { + unsigned long start = search_all ? 0 : queries[j]; + unsigned long last = search_all ? max_endpoint : queries[j]; + + results += search(&root, start, last); + } time2 = get_cycles(); time = time2 - time1; -- cgit