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"); | |
0b548e33 | 14 | __param(int, perf_loops, 1000, "Number of iterations modifying the tree"); |
a54dae03 DB |
15 | |
16 | __param(int, nsearches, 100, "Number of searches to the interval tree"); | |
0b548e33 | 17 | __param(int, search_loops, 1000, "Number of iterations searching the tree"); |
c46ecce4 | 18 | __param(bool, search_all, false, "Searches will iterate all nodes in the tree"); |
a54dae03 | 19 | |
a8ec14d4 | 20 | __param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint"); |
fff3fd8a | 21 | |
f808c13f | 22 | static struct rb_root_cached root = RB_ROOT_CACHED; |
a54dae03 DB |
23 | static struct interval_tree_node *nodes = NULL; |
24 | static u32 *queries = NULL; | |
fff3fd8a ML |
25 | |
26 | static struct rnd_state rnd; | |
27 | ||
28 | static inline unsigned long | |
f808c13f | 29 | search(struct rb_root_cached *root, unsigned long start, unsigned long last) |
fff3fd8a ML |
30 | { |
31 | struct interval_tree_node *node; | |
32 | unsigned long results = 0; | |
33 | ||
c46ecce4 DB |
34 | for (node = interval_tree_iter_first(root, start, last); node; |
35 | node = interval_tree_iter_next(node, start, last)) | |
fff3fd8a ML |
36 | results++; |
37 | return results; | |
38 | } | |
39 | ||
40 | static void init(void) | |
41 | { | |
42 | int i; | |
a54dae03 DB |
43 | |
44 | for (i = 0; i < nnodes; i++) { | |
a8ec14d4 DB |
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; | |
fff3fd8a | 50 | } |
a8ec14d4 DB |
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 | */ | |
a54dae03 | 57 | for (i = 0; i < nsearches; i++) |
a8ec14d4 | 58 | queries[i] = (prandom_u32_state(&rnd) >> 4) % max_endpoint; |
fff3fd8a ML |
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 | ||
a54dae03 DB |
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 | ||
fff3fd8a ML |
77 | printk(KERN_ALERT "interval tree insert/remove"); |
78 | ||
496f2f93 | 79 | prandom_seed_state(&rnd, 3141592653589793238ULL); |
fff3fd8a ML |
80 | init(); |
81 | ||
82 | time1 = get_cycles(); | |
83 | ||
a54dae03 DB |
84 | for (i = 0; i < perf_loops; i++) { |
85 | for (j = 0; j < nnodes; j++) | |
fff3fd8a | 86 | interval_tree_insert(nodes + j, &root); |
a54dae03 | 87 | for (j = 0; j < nnodes; j++) |
fff3fd8a ML |
88 | interval_tree_remove(nodes + j, &root); |
89 | } | |
90 | ||
91 | time2 = get_cycles(); | |
92 | time = time2 - time1; | |
93 | ||
a54dae03 | 94 | time = div_u64(time, perf_loops); |
fff3fd8a ML |
95 | printk(" -> %llu cycles\n", (unsigned long long)time); |
96 | ||
97 | printk(KERN_ALERT "interval tree search"); | |
98 | ||
a54dae03 | 99 | for (j = 0; j < nnodes; j++) |
fff3fd8a ML |
100 | interval_tree_insert(nodes + j, &root); |
101 | ||
102 | time1 = get_cycles(); | |
103 | ||
104 | results = 0; | |
a54dae03 | 105 | for (i = 0; i < search_loops; i++) |
c46ecce4 DB |
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 | } | |
fff3fd8a ML |
112 | |
113 | time2 = get_cycles(); | |
114 | time = time2 - time1; | |
115 | ||
a54dae03 DB |
116 | time = div_u64(time, search_loops); |
117 | results = div_u64(results, search_loops); | |
fff3fd8a ML |
118 | printk(" -> %llu cycles (%lu results)\n", |
119 | (unsigned long long)time, results); | |
120 | ||
a54dae03 DB |
121 | kfree(queries); |
122 | kfree(nodes); | |
123 | ||
fff3fd8a ML |
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"); |