lib/interval_tree_test: some debugging improvements
cover lib/interval_tree_test: some debugging improvements
Hi,
Here are some patches that update the interva_tree_test module allowing users to pass finer grained options to run the actual test.
Applies on top of v4.12-rc1.
Thanks!
Davidlohr Bueso (4):
lib/interval_tree_test: allow the module to be compiled-in lib/interval_tree_test: make test options module parameters lib/interval_tree_test: allow users to limit scope of endpoint lib/interval_tree_test: allow full tree search
lib/Kconfig.debug | 2 +- lib/interval_tree_test.c | 93 ++++++++++++++++++++++++++++++++---------------- 2 files changed, 63 insertions(+), 32 deletions(-)
Signature · 1 line
2.12.0
PATCH 1/4 lib/interval_tree_test: allow the module to be compiled-in
It is a tristate after all, and also serves well for quick debugging.
--- lib/Kconfig.debug | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/Kconfig.debug +1 -1
@@ -1773,7 +1773,7 @@ config RBTREE_TEST config INTERVAL_TREE_TEST tristate "Interval tree test" - depends on m && DEBUG_KERNEL + depends on DEBUG_KERNEL select INTERVAL_TREE help A benchmark measuring the performance of the interval tree library
Signature · 1 line
2.12.0
PATCH 2/4 lib/interval_tree_test: make test options module parameters
In reply to Davidlohr BuesoAllows for more flexible debugging.
--- lib/interval_tree_test.c | 57 +++++++++++++++++++++++++++++++++--------------- 1 file changed, 40 insertions(+), 17 deletions(-)
lib/interval_tree_test.c +40 -17
@@ -1,16 +1,25 @@#include <linux/module.h> +#include <linux/moduleparam.h> #include <linux/interval_tree.h> #include <linux/random.h> +#include <linux/slab.h> #include <asm/timex.h> -#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 */ }
Signature · 1 line
2.12.0
PATCH 3/4 lib/interval_tree_test: allow users to limit scope of endpoint
In reply to Davidlohr BuesoAdd a 'max_endpoint' parameter such that users may easily limit the size of the intervals that are randomly generated.
--- lib/interval_tree_test.c | 23 +++++++++++++---------- 1 file changed, 13 insertions(+), 10 deletions(-)
lib/interval_tree_test.c +13 -10
@@ -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 )
Signature · 1 line
2.12.0
PATCH 4/4 lib/interval_tree_test: allow full tree search
In reply to Davidlohr Bueso... 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.
--- lib/interval_tree_test.c | 15 ++++++++++----- 1 file changed, 10 insertions(+), 5 deletions(-)
lib/interval_tree_test.c +10 -5
@@ -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;
Signature · 1 line
2.12.0