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