1 | // SPDX-License-Identifier: GPL-2.0 |
2 | #include <stdio.h> |
3 | #include <stdlib.h> |
4 | #include <unistd.h> |
5 | #include <time.h> |
6 | #include <assert.h> |
7 | #include <limits.h> |
8 | |
9 | #include <linux/slab.h> |
10 | #include <linux/radix-tree.h> |
11 | |
12 | #include "test.h" |
13 | #include "regression.h" |
14 | |
15 | void __gang_check(unsigned long middle, long down, long up, int chunk, int hop) |
16 | { |
17 | long idx; |
18 | RADIX_TREE(tree, GFP_KERNEL); |
19 | |
20 | middle = 1 << 30; |
21 | |
22 | for (idx = -down; idx < up; idx++) |
23 | item_insert(root: &tree, index: middle + idx); |
24 | |
25 | item_check_absent(root: &tree, index: middle - down - 1); |
26 | for (idx = -down; idx < up; idx++) |
27 | item_check_present(root: &tree, index: middle + idx); |
28 | item_check_absent(root: &tree, index: middle + up); |
29 | |
30 | if (chunk > 0) { |
31 | item_gang_check_present(root: &tree, start: middle - down, nr: up + down, |
32 | chunk, hop); |
33 | item_full_scan(root: &tree, start: middle - down, nr: down + up, chunk); |
34 | } |
35 | item_kill_tree(root: &tree); |
36 | } |
37 | |
38 | void gang_check(void) |
39 | { |
40 | __gang_check(middle: 1UL << 30, down: 128, up: 128, chunk: 35, hop: 2); |
41 | __gang_check(middle: 1UL << 31, down: 128, up: 128, chunk: 32, hop: 32); |
42 | __gang_check(middle: 1UL << 31, down: 128, up: 128, chunk: 32, hop: 100); |
43 | __gang_check(middle: 1UL << 31, down: 128, up: 128, chunk: 17, hop: 7); |
44 | __gang_check(middle: 0xffff0000UL, down: 0, up: 65536, chunk: 17, hop: 7); |
45 | __gang_check(middle: 0xfffffffeUL, down: 1, up: 1, chunk: 17, hop: 7); |
46 | } |
47 | |
48 | void __big_gang_check(void) |
49 | { |
50 | unsigned long start; |
51 | int wrapped = 0; |
52 | |
53 | start = 0; |
54 | do { |
55 | unsigned long old_start; |
56 | |
57 | // printf("0x%08lx\n", start); |
58 | __gang_check(middle: start, down: rand() % 113 + 1, up: rand() % 71, |
59 | chunk: rand() % 157, hop: rand() % 91 + 1); |
60 | old_start = start; |
61 | start += rand() % 1000000; |
62 | start %= 1ULL << 33; |
63 | if (start < old_start) |
64 | wrapped = 1; |
65 | } while (!wrapped); |
66 | } |
67 | |
68 | void big_gang_check(bool long_run) |
69 | { |
70 | int i; |
71 | |
72 | for (i = 0; i < (long_run ? 1000 : 3); i++) { |
73 | __big_gang_check(); |
74 | printv(2, "%d " , i); |
75 | fflush(stdout); |
76 | } |
77 | } |
78 | |
79 | void add_and_check(void) |
80 | { |
81 | RADIX_TREE(tree, GFP_KERNEL); |
82 | |
83 | item_insert(root: &tree, index: 44); |
84 | item_check_present(root: &tree, index: 44); |
85 | item_check_absent(root: &tree, index: 43); |
86 | item_kill_tree(root: &tree); |
87 | } |
88 | |
89 | void dynamic_height_check(void) |
90 | { |
91 | int i; |
92 | RADIX_TREE(tree, GFP_KERNEL); |
93 | tree_verify_min_height(root: &tree, maxindex: 0); |
94 | |
95 | item_insert(root: &tree, index: 42); |
96 | tree_verify_min_height(root: &tree, maxindex: 42); |
97 | |
98 | item_insert(root: &tree, index: 1000000); |
99 | tree_verify_min_height(root: &tree, maxindex: 1000000); |
100 | |
101 | assert(item_delete(root: &tree, index: 1000000)); |
102 | tree_verify_min_height(root: &tree, maxindex: 42); |
103 | |
104 | assert(item_delete(root: &tree, index: 42)); |
105 | tree_verify_min_height(root: &tree, maxindex: 0); |
106 | |
107 | for (i = 0; i < 1000; i++) { |
108 | item_insert(root: &tree, index: i); |
109 | tree_verify_min_height(root: &tree, maxindex: i); |
110 | } |
111 | |
112 | i--; |
113 | for (;;) { |
114 | assert(item_delete(root: &tree, index: i)); |
115 | if (i == 0) { |
116 | tree_verify_min_height(root: &tree, maxindex: 0); |
117 | break; |
118 | } |
119 | i--; |
120 | tree_verify_min_height(root: &tree, maxindex: i); |
121 | } |
122 | |
123 | item_kill_tree(root: &tree); |
124 | } |
125 | |
126 | void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag) |
127 | { |
128 | int i; |
129 | |
130 | for (i = 0; i < count; i++) { |
131 | /* if (i % 1000 == 0) |
132 | putchar('.'); */ |
133 | if (idx[i] < start || idx[i] > end) { |
134 | if (item_tag_get(root: tree, index: idx[i], tag: totag)) { |
135 | printv(2, "%lu-%lu: %lu, tags %d-%d\n" , start, |
136 | end, idx[i], item_tag_get(root: tree, index: idx[i], |
137 | tag: fromtag), |
138 | item_tag_get(root: tree, index: idx[i], tag: totag)); |
139 | } |
140 | assert(!item_tag_get(root: tree, index: idx[i], tag: totag)); |
141 | continue; |
142 | } |
143 | if (item_tag_get(root: tree, index: idx[i], tag: fromtag) ^ |
144 | item_tag_get(root: tree, index: idx[i], tag: totag)) { |
145 | printv(2, "%lu-%lu: %lu, tags %d-%d\n" , start, end, |
146 | idx[i], item_tag_get(root: tree, index: idx[i], tag: fromtag), |
147 | item_tag_get(root: tree, index: idx[i], tag: totag)); |
148 | } |
149 | assert(!(item_tag_get(root: tree, index: idx[i], tag: fromtag) ^ |
150 | item_tag_get(root: tree, index: idx[i], tag: totag))); |
151 | } |
152 | } |
153 | |
154 | #define ITEMS 50000 |
155 | |
156 | void copy_tag_check(void) |
157 | { |
158 | RADIX_TREE(tree, GFP_KERNEL); |
159 | unsigned long idx[ITEMS]; |
160 | unsigned long start, end, count = 0, tagged, cur, tmp; |
161 | int i; |
162 | |
163 | // printf("generating radix tree indices...\n"); |
164 | start = rand(); |
165 | end = rand(); |
166 | if (start > end && (rand() % 10)) { |
167 | cur = start; |
168 | start = end; |
169 | end = cur; |
170 | } |
171 | /* Specifically create items around the start and the end of the range |
172 | * with high probability to check for off by one errors */ |
173 | cur = rand(); |
174 | if (cur & 1) { |
175 | item_insert(root: &tree, index: start); |
176 | if (cur & 2) { |
177 | if (start <= end) |
178 | count++; |
179 | item_tag_set(root: &tree, index: start, tag: 0); |
180 | } |
181 | } |
182 | if (cur & 4) { |
183 | item_insert(root: &tree, index: start-1); |
184 | if (cur & 8) |
185 | item_tag_set(root: &tree, index: start-1, tag: 0); |
186 | } |
187 | if (cur & 16) { |
188 | item_insert(root: &tree, index: end); |
189 | if (cur & 32) { |
190 | if (start <= end) |
191 | count++; |
192 | item_tag_set(root: &tree, index: end, tag: 0); |
193 | } |
194 | } |
195 | if (cur & 64) { |
196 | item_insert(root: &tree, index: end+1); |
197 | if (cur & 128) |
198 | item_tag_set(root: &tree, index: end+1, tag: 0); |
199 | } |
200 | |
201 | for (i = 0; i < ITEMS; i++) { |
202 | do { |
203 | idx[i] = rand(); |
204 | } while (item_lookup(root: &tree, index: idx[i])); |
205 | |
206 | item_insert(root: &tree, index: idx[i]); |
207 | if (rand() & 1) { |
208 | item_tag_set(root: &tree, index: idx[i], tag: 0); |
209 | if (idx[i] >= start && idx[i] <= end) |
210 | count++; |
211 | } |
212 | /* if (i % 1000 == 0) |
213 | putchar('.'); */ |
214 | } |
215 | |
216 | // printf("\ncopying tags...\n"); |
217 | tagged = tag_tagged_items(&tree, start, end, ITEMS, XA_MARK_0, XA_MARK_1); |
218 | |
219 | // printf("checking copied tags\n"); |
220 | assert(tagged == count); |
221 | check_copied_tags(tree: &tree, start, end, idx, ITEMS, fromtag: 0, totag: 1); |
222 | |
223 | /* Copy tags in several rounds */ |
224 | // printf("\ncopying tags...\n"); |
225 | tmp = rand() % (count / 10 + 2); |
226 | tagged = tag_tagged_items(&tree, start, end, batch: tmp, XA_MARK_0, XA_MARK_2); |
227 | assert(tagged == count); |
228 | |
229 | // printf("%lu %lu %lu\n", tagged, tmp, count); |
230 | // printf("checking copied tags\n"); |
231 | check_copied_tags(tree: &tree, start, end, idx, ITEMS, fromtag: 0, totag: 2); |
232 | verify_tag_consistency(root: &tree, tag: 0); |
233 | verify_tag_consistency(root: &tree, tag: 1); |
234 | verify_tag_consistency(root: &tree, tag: 2); |
235 | // printf("\n"); |
236 | item_kill_tree(root: &tree); |
237 | } |
238 | |
239 | static void single_thread_tests(bool long_run) |
240 | { |
241 | int i; |
242 | |
243 | printv(1, "starting single_thread_tests: %d allocated, preempt %d\n" , |
244 | nr_allocated, preempt_count); |
245 | multiorder_checks(); |
246 | rcu_barrier(); |
247 | printv(2, "after multiorder_check: %d allocated, preempt %d\n" , |
248 | nr_allocated, preempt_count); |
249 | tag_check(); |
250 | rcu_barrier(); |
251 | printv(2, "after tag_check: %d allocated, preempt %d\n" , |
252 | nr_allocated, preempt_count); |
253 | gang_check(); |
254 | rcu_barrier(); |
255 | printv(2, "after gang_check: %d allocated, preempt %d\n" , |
256 | nr_allocated, preempt_count); |
257 | add_and_check(); |
258 | rcu_barrier(); |
259 | printv(2, "after add_and_check: %d allocated, preempt %d\n" , |
260 | nr_allocated, preempt_count); |
261 | dynamic_height_check(); |
262 | rcu_barrier(); |
263 | printv(2, "after dynamic_height_check: %d allocated, preempt %d\n" , |
264 | nr_allocated, preempt_count); |
265 | idr_checks(); |
266 | ida_tests(); |
267 | rcu_barrier(); |
268 | printv(2, "after idr_checks: %d allocated, preempt %d\n" , |
269 | nr_allocated, preempt_count); |
270 | big_gang_check(long_run); |
271 | rcu_barrier(); |
272 | printv(2, "after big_gang_check: %d allocated, preempt %d\n" , |
273 | nr_allocated, preempt_count); |
274 | for (i = 0; i < (long_run ? 2000 : 3); i++) { |
275 | copy_tag_check(); |
276 | printv(2, "%d " , i); |
277 | fflush(stdout); |
278 | } |
279 | rcu_barrier(); |
280 | printv(2, "after copy_tag_check: %d allocated, preempt %d\n" , |
281 | nr_allocated, preempt_count); |
282 | } |
283 | |
284 | int main(int argc, char **argv) |
285 | { |
286 | bool long_run = false; |
287 | int opt; |
288 | unsigned int seed = time(NULL); |
289 | |
290 | while ((opt = getopt(argc, argv, "ls:v" )) != -1) { |
291 | if (opt == 'l') |
292 | long_run = true; |
293 | else if (opt == 's') |
294 | seed = strtoul(optarg, NULL, 0); |
295 | else if (opt == 'v') |
296 | test_verbose++; |
297 | } |
298 | |
299 | printf("random seed %u\n" , seed); |
300 | srand(seed); |
301 | |
302 | printf("running tests\n" ); |
303 | |
304 | rcu_register_thread(); |
305 | radix_tree_init(); |
306 | |
307 | xarray_tests(); |
308 | regression1_test(); |
309 | regression2_test(); |
310 | regression3_test(); |
311 | regression4_test(); |
312 | iteration_test(order: 0, duration: 10 + 90 * long_run); |
313 | iteration_test(order: 7, duration: 10 + 90 * long_run); |
314 | iteration_test2(duration: 10 + 90 * long_run); |
315 | single_thread_tests(long_run); |
316 | |
317 | /* Free any remaining preallocated nodes */ |
318 | radix_tree_cpu_dead(cpu: 0); |
319 | |
320 | benchmark(); |
321 | |
322 | rcu_barrier(); |
323 | printv(2, "after rcu_barrier: %d allocated, preempt %d\n" , |
324 | nr_allocated, preempt_count); |
325 | rcu_unregister_thread(); |
326 | |
327 | printf("tests completed\n" ); |
328 | |
329 | exit(0); |
330 | } |
331 | |