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