1
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
15void __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(&tree, middle + idx);
24
25 item_check_absent(&tree, middle - down - 1);
26 for (idx = -down; idx < up; idx++)
27 item_check_present(&tree, middle + idx);
28 item_check_absent(&tree, middle + up);
29
30 if (chunk > 0) {
31 item_gang_check_present(&tree, middle - down, up + down,
32 chunk, hop);
33 item_full_scan(&tree, middle - down, down + up, chunk);
34 }
35 item_kill_tree(&tree);
36}
37
38void gang_check(void)
39{
40 __gang_check(1UL << 30, 128, 128, 35, 2);
41 __gang_check(1UL << 31, 128, 128, 32, 32);
42 __gang_check(1UL << 31, 128, 128, 32, 100);
43 __gang_check(1UL << 31, 128, 128, 17, 7);
44 __gang_check(0xffff0000UL, 0, 65536, 17, 7);
45 __gang_check(0xfffffffeUL, 1, 1, 17, 7);
46}
47
48void __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
58 __gang_check(start, rand() % 113 + 1, rand() % 71,
59 rand() % 157, 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
68void 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
79void add_and_check(void)
80{
81 RADIX_TREE(tree, GFP_KERNEL);
82
83 item_insert(&tree, 44);
84 item_check_present(&tree, 44);
85 item_check_absent(&tree, 43);
86 item_kill_tree(&tree);
87}
88
89void dynamic_height_check(void)
90{
91 int i;
92 RADIX_TREE(tree, GFP_KERNEL);
93 tree_verify_min_height(&tree, 0);
94
95 item_insert(&tree, 42);
96 tree_verify_min_height(&tree, 42);
97
98 item_insert(&tree, 1000000);
99 tree_verify_min_height(&tree, 1000000);
100
101 assert(item_delete(&tree, 1000000));
102 tree_verify_min_height(&tree, 42);
103
104 assert(item_delete(&tree, 42));
105 tree_verify_min_height(&tree, 0);
106
107 for (i = 0; i < 1000; i++) {
108 item_insert(&tree, i);
109 tree_verify_min_height(&tree, i);
110 }
111
112 i--;
113 for (;;) {
114 assert(item_delete(&tree, i));
115 if (i == 0) {
116 tree_verify_min_height(&tree, 0);
117 break;
118 }
119 i--;
120 tree_verify_min_height(&tree, i);
121 }
122
123 item_kill_tree(&tree);
124}
125
126void 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
132
133 if (idx[i] < start || idx[i] > end) {
134 if (item_tag_get(tree, idx[i], totag)) {
135 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start,
136 end, idx[i], item_tag_get(tree, idx[i],
137 fromtag),
138 item_tag_get(tree, idx[i], totag));
139 }
140 assert(!item_tag_get(tree, idx[i], totag));
141 continue;
142 }
143 if (item_tag_get(tree, idx[i], fromtag) ^
144 item_tag_get(tree, idx[i], totag)) {
145 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, end,
146 idx[i], item_tag_get(tree, idx[i], fromtag),
147 item_tag_get(tree, idx[i], totag));
148 }
149 assert(!(item_tag_get(tree, idx[i], fromtag) ^
150 item_tag_get(tree, idx[i], totag)));
151 }
152}
153
154#define ITEMS 50000
155
156void 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
164 start = rand();
165 end = rand();
166 if (start > end && (rand() % 10)) {
167 cur = start;
168 start = end;
169 end = cur;
170 }
171
172
173 cur = rand();
174 if (cur & 1) {
175 item_insert(&tree, start);
176 if (cur & 2) {
177 if (start <= end)
178 count++;
179 item_tag_set(&tree, start, 0);
180 }
181 }
182 if (cur & 4) {
183 item_insert(&tree, start-1);
184 if (cur & 8)
185 item_tag_set(&tree, start-1, 0);
186 }
187 if (cur & 16) {
188 item_insert(&tree, end);
189 if (cur & 32) {
190 if (start <= end)
191 count++;
192 item_tag_set(&tree, end, 0);
193 }
194 }
195 if (cur & 64) {
196 item_insert(&tree, end+1);
197 if (cur & 128)
198 item_tag_set(&tree, end+1, 0);
199 }
200
201 for (i = 0; i < ITEMS; i++) {
202 do {
203 idx[i] = rand();
204 } while (item_lookup(&tree, idx[i]));
205
206 item_insert(&tree, idx[i]);
207 if (rand() & 1) {
208 item_tag_set(&tree, idx[i], 0);
209 if (idx[i] >= start && idx[i] <= end)
210 count++;
211 }
212
213
214 }
215
216
217 tagged = tag_tagged_items(&tree, NULL, start, end, ITEMS, 0, 1);
218
219
220 assert(tagged == count);
221 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
222
223
224
225 tmp = rand() % (count / 10 + 2);
226 tagged = tag_tagged_items(&tree, NULL, start, end, tmp, 0, 2);
227 assert(tagged == count);
228
229
230
231 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
232 verify_tag_consistency(&tree, 0);
233 verify_tag_consistency(&tree, 1);
234 verify_tag_consistency(&tree, 2);
235
236 item_kill_tree(&tree);
237}
238
239static void __locate_check(struct radix_tree_root *tree, unsigned long index,
240 unsigned order)
241{
242 struct item *item;
243 unsigned long index2;
244
245 item_insert_order(tree, index, order);
246 item = item_lookup(tree, index);
247 index2 = find_item(tree, item);
248 if (index != index2) {
249 printv(2, "index %ld order %d inserted; found %ld\n",
250 index, order, index2);
251 abort();
252 }
253}
254
255static void __order_0_locate_check(void)
256{
257 RADIX_TREE(tree, GFP_KERNEL);
258 int i;
259
260 for (i = 0; i < 50; i++)
261 __locate_check(&tree, rand() % INT_MAX, 0);
262
263 item_kill_tree(&tree);
264}
265
266static void locate_check(void)
267{
268 RADIX_TREE(tree, GFP_KERNEL);
269 unsigned order;
270 unsigned long offset, index;
271
272 __order_0_locate_check();
273
274 for (order = 0; order < 20; order++) {
275 for (offset = 0; offset < (1 << (order + 3));
276 offset += (1UL << order)) {
277 for (index = 0; index < (1UL << (order + 5));
278 index += (1UL << order)) {
279 __locate_check(&tree, index + offset, order);
280 }
281 if (find_item(&tree, &tree) != -1)
282 abort();
283
284 item_kill_tree(&tree);
285 }
286 }
287
288 if (find_item(&tree, &tree) != -1)
289 abort();
290 __locate_check(&tree, -1, 0);
291 if (find_item(&tree, &tree) != -1)
292 abort();
293 item_kill_tree(&tree);
294}
295
296static void single_thread_tests(bool long_run)
297{
298 int i;
299
300 printv(1, "starting single_thread_tests: %d allocated, preempt %d\n",
301 nr_allocated, preempt_count);
302 multiorder_checks();
303 rcu_barrier();
304 printv(2, "after multiorder_check: %d allocated, preempt %d\n",
305 nr_allocated, preempt_count);
306 locate_check();
307 rcu_barrier();
308 printv(2, "after locate_check: %d allocated, preempt %d\n",
309 nr_allocated, preempt_count);
310 tag_check();
311 rcu_barrier();
312 printv(2, "after tag_check: %d allocated, preempt %d\n",
313 nr_allocated, preempt_count);
314 gang_check();
315 rcu_barrier();
316 printv(2, "after gang_check: %d allocated, preempt %d\n",
317 nr_allocated, preempt_count);
318 add_and_check();
319 rcu_barrier();
320 printv(2, "after add_and_check: %d allocated, preempt %d\n",
321 nr_allocated, preempt_count);
322 dynamic_height_check();
323 rcu_barrier();
324 printv(2, "after dynamic_height_check: %d allocated, preempt %d\n",
325 nr_allocated, preempt_count);
326 idr_checks();
327 ida_checks();
328 rcu_barrier();
329 printv(2, "after idr_checks: %d allocated, preempt %d\n",
330 nr_allocated, preempt_count);
331 big_gang_check(long_run);
332 rcu_barrier();
333 printv(2, "after big_gang_check: %d allocated, preempt %d\n",
334 nr_allocated, preempt_count);
335 for (i = 0; i < (long_run ? 2000 : 3); i++) {
336 copy_tag_check();
337 printv(2, "%d ", i);
338 fflush(stdout);
339 }
340 rcu_barrier();
341 printv(2, "after copy_tag_check: %d allocated, preempt %d\n",
342 nr_allocated, preempt_count);
343}
344
345int main(int argc, char **argv)
346{
347 bool long_run = false;
348 int opt;
349 unsigned int seed = time(NULL);
350
351 while ((opt = getopt(argc, argv, "ls:v")) != -1) {
352 if (opt == 'l')
353 long_run = true;
354 else if (opt == 's')
355 seed = strtoul(optarg, NULL, 0);
356 else if (opt == 'v')
357 test_verbose++;
358 }
359
360 printf("random seed %u\n", seed);
361 srand(seed);
362
363 printf("running tests\n");
364
365 rcu_register_thread();
366 radix_tree_init();
367
368 regression1_test();
369 regression2_test();
370 regression3_test();
371 iteration_test(0, 10 + 90 * long_run);
372 iteration_test(7, 10 + 90 * long_run);
373 single_thread_tests(long_run);
374 ida_thread_tests();
375
376
377 radix_tree_cpu_dead(0);
378
379 benchmark();
380
381 rcu_barrier();
382 printv(2, "after rcu_barrier: %d allocated, preempt %d\n",
383 nr_allocated, preempt_count);
384 rcu_unregister_thread();
385
386 printf("tests completed\n");
387
388 exit(0);
389}
390
