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