* [PATCH 1/4] lib/interval_tree_test: allow the module to be compiled-in
2017-05-18 17:49 [PATCH -next 0/4] lib/interval_tree_test: some debugging improvements Davidlohr Bueso
@ 2017-05-18 17:49 ` Davidlohr Bueso
2017-05-18 17:49 ` [PATCH 2/4] lib/interval_tree_test: make test options module parameters Davidlohr Bueso
` (2 subsequent siblings)
3 siblings, 0 replies; 5+ messages in thread
From: Davidlohr Bueso @ 2017-05-18 17:49 UTC (permalink / raw)
To: akpm; +Cc: dave, linux-kernel, Davidlohr Bueso
It is a tristate after all, and also serves well for quick debugging.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
lib/Kconfig.debug | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index e4587ebe52c7..b29bf26e653c 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -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
--
2.12.0
^ permalink raw reply related [flat|nested] 5+ messages in thread
* [PATCH 2/4] lib/interval_tree_test: make test options module parameters
2017-05-18 17:49 [PATCH -next 0/4] lib/interval_tree_test: some debugging improvements Davidlohr Bueso
2017-05-18 17:49 ` [PATCH 1/4] lib/interval_tree_test: allow the module to be compiled-in Davidlohr Bueso
@ 2017-05-18 17:49 ` Davidlohr Bueso
2017-05-18 17:49 ` [PATCH 3/4] lib/interval_tree_test: allow users to limit scope of endpoint Davidlohr Bueso
2017-05-18 17:49 ` [PATCH 4/4] lib/interval_tree_test: allow full tree search Davidlohr Bueso
3 siblings, 0 replies; 5+ messages in thread
From: Davidlohr Bueso @ 2017-05-18 17:49 UTC (permalink / raw)
To: akpm; +Cc: dave, linux-kernel, Davidlohr Bueso
Allows for more flexible debugging.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
lib/interval_tree_test.c | 57 +++++++++++++++++++++++++++++++++---------------
1 file changed, 40 insertions(+), 17 deletions(-)
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 <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 */
}
--
2.12.0
^ permalink raw reply related [flat|nested] 5+ messages in thread
* [PATCH 3/4] lib/interval_tree_test: allow users to limit scope of endpoint
2017-05-18 17:49 [PATCH -next 0/4] lib/interval_tree_test: some debugging improvements Davidlohr Bueso
2017-05-18 17:49 ` [PATCH 1/4] lib/interval_tree_test: allow the module to be compiled-in Davidlohr Bueso
2017-05-18 17:49 ` [PATCH 2/4] lib/interval_tree_test: make test options module parameters Davidlohr Bueso
@ 2017-05-18 17:49 ` Davidlohr Bueso
2017-05-18 17:49 ` [PATCH 4/4] lib/interval_tree_test: allow full tree search Davidlohr Bueso
3 siblings, 0 replies; 5+ messages in thread
From: Davidlohr Bueso @ 2017-05-18 17:49 UTC (permalink / raw)
To: akpm; +Cc: dave, linux-kernel, Davidlohr Bueso
Add a 'max_endpoint' parameter such that users may easily
limit the size of the intervals that are randomly generated.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
lib/interval_tree_test.c | 23 +++++++++++++----------
1 file changed, 13 insertions(+), 10 deletions(-)
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)
--
2.12.0
^ permalink raw reply related [flat|nested] 5+ messages in thread
* [PATCH 4/4] lib/interval_tree_test: allow full tree search
2017-05-18 17:49 [PATCH -next 0/4] lib/interval_tree_test: some debugging improvements Davidlohr Bueso
` (2 preceding siblings ...)
2017-05-18 17:49 ` [PATCH 3/4] lib/interval_tree_test: allow users to limit scope of endpoint Davidlohr Bueso
@ 2017-05-18 17:49 ` Davidlohr Bueso
3 siblings, 0 replies; 5+ messages in thread
From: Davidlohr Bueso @ 2017-05-18 17:49 UTC (permalink / raw)
To: akpm; +Cc: dave, linux-kernel, 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.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
---
lib/interval_tree_test.c | 15 ++++++++++-----
1 file changed, 10 insertions(+), 5 deletions(-)
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;
--
2.12.0
^ permalink raw reply related [flat|nested] 5+ messages in thread