blob: 222c8010bda01722f2197feb3a4b4c23a9620a33
1 | #include <linux/module.h> |
2 | #include <linux/moduleparam.h> |
3 | #include <linux/interval_tree.h> |
4 | #include <linux/random.h> |
5 | #include <linux/slab.h> |
6 | #include <asm/timex.h> |
7 | |
8 | #define __param(type, name, init, msg) \ |
9 | static type name = init; \ |
10 | module_param(name, type, 0444); \ |
11 | MODULE_PARM_DESC(name, msg); |
12 | |
13 | __param(int, nnodes, 100, "Number of nodes in the interval tree"); |
14 | __param(int, perf_loops, 1000, "Number of iterations modifying the tree"); |
15 | |
16 | __param(int, nsearches, 100, "Number of searches to the interval tree"); |
17 | __param(int, search_loops, 1000, "Number of iterations searching the tree"); |
18 | __param(bool, search_all, false, "Searches will iterate all nodes in the tree"); |
19 | |
20 | __param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint"); |
21 | |
22 | static struct rb_root root = RB_ROOT; |
23 | static struct interval_tree_node *nodes = NULL; |
24 | static u32 *queries = NULL; |
25 | |
26 | static struct rnd_state rnd; |
27 | |
28 | static inline unsigned long |
29 | search(struct rb_root *root, unsigned long start, unsigned long last) |
30 | { |
31 | struct interval_tree_node *node; |
32 | unsigned long results = 0; |
33 | |
34 | for (node = interval_tree_iter_first(root, start, last); node; |
35 | node = interval_tree_iter_next(node, start, last)) |
36 | results++; |
37 | return results; |
38 | } |
39 | |
40 | static void init(void) |
41 | { |
42 | int i; |
43 | |
44 | for (i = 0; i < nnodes; i++) { |
45 | u32 b = (prandom_u32_state(&rnd) >> 4) % max_endpoint; |
46 | u32 a = (prandom_u32_state(&rnd) >> 4) % b; |
47 | |
48 | nodes[i].start = a; |
49 | nodes[i].last = b; |
50 | } |
51 | |
52 | /* |
53 | * Limit the search scope to what the user defined. |
54 | * Otherwise we are merely measuring empty walks, |
55 | * which is pointless. |
56 | */ |
57 | for (i = 0; i < nsearches; i++) |
58 | queries[i] = (prandom_u32_state(&rnd) >> 4) % max_endpoint; |
59 | } |
60 | |
61 | static int interval_tree_test_init(void) |
62 | { |
63 | int i, j; |
64 | unsigned long results; |
65 | cycles_t time1, time2, time; |
66 | |
67 | nodes = kmalloc(nnodes * sizeof(struct interval_tree_node), GFP_KERNEL); |
68 | if (!nodes) |
69 | return -ENOMEM; |
70 | |
71 | queries = kmalloc(nsearches * sizeof(int), GFP_KERNEL); |
72 | if (!queries) { |
73 | kfree(nodes); |
74 | return -ENOMEM; |
75 | } |
76 | |
77 | printk(KERN_ALERT "interval tree insert/remove"); |
78 | |
79 | prandom_seed_state(&rnd, 3141592653589793238ULL); |
80 | init(); |
81 | |
82 | time1 = get_cycles(); |
83 | |
84 | for (i = 0; i < perf_loops; i++) { |
85 | for (j = 0; j < nnodes; j++) |
86 | interval_tree_insert(nodes + j, &root); |
87 | for (j = 0; j < nnodes; j++) |
88 | interval_tree_remove(nodes + j, &root); |
89 | } |
90 | |
91 | time2 = get_cycles(); |
92 | time = time2 - time1; |
93 | |
94 | time = div_u64(time, perf_loops); |
95 | printk(" -> %llu cycles\n", (unsigned long long)time); |
96 | |
97 | printk(KERN_ALERT "interval tree search"); |
98 | |
99 | for (j = 0; j < nnodes; j++) |
100 | interval_tree_insert(nodes + j, &root); |
101 | |
102 | time1 = get_cycles(); |
103 | |
104 | results = 0; |
105 | for (i = 0; i < search_loops; i++) |
106 | for (j = 0; j < nsearches; j++) { |
107 | unsigned long start = search_all ? 0 : queries[j]; |
108 | unsigned long last = search_all ? max_endpoint : queries[j]; |
109 | |
110 | results += search(&root, start, last); |
111 | } |
112 | |
113 | time2 = get_cycles(); |
114 | time = time2 - time1; |
115 | |
116 | time = div_u64(time, search_loops); |
117 | results = div_u64(results, search_loops); |
118 | printk(" -> %llu cycles (%lu results)\n", |
119 | (unsigned long long)time, results); |
120 | |
121 | kfree(queries); |
122 | kfree(nodes); |
123 | |
124 | return -EAGAIN; /* Fail will directly unload the module */ |
125 | } |
126 | |
127 | static void interval_tree_test_exit(void) |
128 | { |
129 | printk(KERN_ALERT "test exit\n"); |
130 | } |
131 | |
132 | module_init(interval_tree_test_init) |
133 | module_exit(interval_tree_test_exit) |
134 | |
135 | MODULE_LICENSE("GPL"); |
136 | MODULE_AUTHOR("Michel Lespinasse"); |
137 | MODULE_DESCRIPTION("Interval Tree test"); |
138 |