]>
Commit | Line | Data |
---|---|---|
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, 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 | __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"); |