]>
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 | ||
fff3fd8a ML |
19 | |
20 | static struct rb_root root = RB_ROOT; | |
a54dae03 DB |
21 | static struct interval_tree_node *nodes = NULL; |
22 | static u32 *queries = NULL; | |
fff3fd8a ML |
23 | |
24 | static struct rnd_state rnd; | |
25 | ||
26 | static inline unsigned long | |
27 | search(unsigned long query, struct rb_root *root) | |
28 | { | |
29 | struct interval_tree_node *node; | |
30 | unsigned long results = 0; | |
31 | ||
32 | for (node = interval_tree_iter_first(root, query, query); node; | |
33 | node = interval_tree_iter_next(node, query, query)) | |
34 | results++; | |
35 | return results; | |
36 | } | |
37 | ||
38 | static void init(void) | |
39 | { | |
40 | int i; | |
a54dae03 DB |
41 | |
42 | for (i = 0; i < nnodes; i++) { | |
496f2f93 AM |
43 | u32 a = prandom_u32_state(&rnd); |
44 | u32 b = prandom_u32_state(&rnd); | |
fff3fd8a ML |
45 | if (a <= b) { |
46 | nodes[i].start = a; | |
47 | nodes[i].last = b; | |
48 | } else { | |
49 | nodes[i].start = b; | |
50 | nodes[i].last = a; | |
51 | } | |
52 | } | |
a54dae03 | 53 | for (i = 0; i < nsearches; i++) |
496f2f93 | 54 | queries[i] = prandom_u32_state(&rnd); |
fff3fd8a ML |
55 | } |
56 | ||
57 | static int interval_tree_test_init(void) | |
58 | { | |
59 | int i, j; | |
60 | unsigned long results; | |
61 | cycles_t time1, time2, time; | |
62 | ||
a54dae03 DB |
63 | nodes = kmalloc(nnodes * sizeof(struct interval_tree_node), GFP_KERNEL); |
64 | if (!nodes) | |
65 | return -ENOMEM; | |
66 | ||
67 | queries = kmalloc(nsearches * sizeof(int), GFP_KERNEL); | |
68 | if (!queries) { | |
69 | kfree(nodes); | |
70 | return -ENOMEM; | |
71 | } | |
72 | ||
fff3fd8a ML |
73 | printk(KERN_ALERT "interval tree insert/remove"); |
74 | ||
496f2f93 | 75 | prandom_seed_state(&rnd, 3141592653589793238ULL); |
fff3fd8a ML |
76 | init(); |
77 | ||
78 | time1 = get_cycles(); | |
79 | ||
a54dae03 DB |
80 | for (i = 0; i < perf_loops; i++) { |
81 | for (j = 0; j < nnodes; j++) | |
fff3fd8a | 82 | interval_tree_insert(nodes + j, &root); |
a54dae03 | 83 | for (j = 0; j < nnodes; j++) |
fff3fd8a ML |
84 | interval_tree_remove(nodes + j, &root); |
85 | } | |
86 | ||
87 | time2 = get_cycles(); | |
88 | time = time2 - time1; | |
89 | ||
a54dae03 | 90 | time = div_u64(time, perf_loops); |
fff3fd8a ML |
91 | printk(" -> %llu cycles\n", (unsigned long long)time); |
92 | ||
93 | printk(KERN_ALERT "interval tree search"); | |
94 | ||
a54dae03 | 95 | for (j = 0; j < nnodes; j++) |
fff3fd8a ML |
96 | interval_tree_insert(nodes + j, &root); |
97 | ||
98 | time1 = get_cycles(); | |
99 | ||
100 | results = 0; | |
a54dae03 DB |
101 | for (i = 0; i < search_loops; i++) |
102 | for (j = 0; j < nsearches; j++) | |
fff3fd8a ML |
103 | results += search(queries[j], &root); |
104 | ||
105 | time2 = get_cycles(); | |
106 | time = time2 - time1; | |
107 | ||
a54dae03 DB |
108 | time = div_u64(time, search_loops); |
109 | results = div_u64(results, search_loops); | |
fff3fd8a ML |
110 | printk(" -> %llu cycles (%lu results)\n", |
111 | (unsigned long long)time, results); | |
112 | ||
a54dae03 DB |
113 | kfree(queries); |
114 | kfree(nodes); | |
115 | ||
fff3fd8a ML |
116 | return -EAGAIN; /* Fail will directly unload the module */ |
117 | } | |
118 | ||
119 | static void interval_tree_test_exit(void) | |
120 | { | |
121 | printk(KERN_ALERT "test exit\n"); | |
122 | } | |
123 | ||
124 | module_init(interval_tree_test_init) | |
125 | module_exit(interval_tree_test_exit) | |
126 | ||
127 | MODULE_LICENSE("GPL"); | |
128 | MODULE_AUTHOR("Michel Lespinasse"); | |
129 | MODULE_DESCRIPTION("Interval Tree test"); |