]>
git.proxmox.com Git - mirror_ubuntu-artful-kernel.git/blob - tools/testing/radix-tree/main.c
8 #include <linux/slab.h>
9 #include <linux/radix-tree.h>
12 #include "regression.h"
14 void __gang_check(unsigned long middle
, long down
, long up
, int chunk
, int hop
)
17 RADIX_TREE(tree
, GFP_KERNEL
);
21 for (idx
= -down
; idx
< up
; idx
++)
22 item_insert(&tree
, middle
+ idx
);
24 item_check_absent(&tree
, middle
- down
- 1);
25 for (idx
= -down
; idx
< up
; idx
++)
26 item_check_present(&tree
, middle
+ idx
);
27 item_check_absent(&tree
, middle
+ up
);
29 item_gang_check_present(&tree
, middle
- down
,
30 up
+ down
, chunk
, hop
);
31 item_full_scan(&tree
, middle
- down
, down
+ up
, chunk
);
32 item_kill_tree(&tree
);
37 __gang_check(1 << 30, 128, 128, 35, 2);
38 __gang_check(1 << 31, 128, 128, 32, 32);
39 __gang_check(1 << 31, 128, 128, 32, 100);
40 __gang_check(1 << 31, 128, 128, 17, 7);
41 __gang_check(0xffff0000, 0, 65536, 17, 7);
42 __gang_check(0xfffffffe, 1, 1, 17, 7);
45 void __big_gang_check(void)
52 unsigned long old_start
;
54 // printf("0x%08lx\n", start);
55 __gang_check(start
, rand() % 113 + 1, rand() % 71,
56 rand() % 157, rand() % 91 + 1);
58 start
+= rand() % 1000000;
60 if (start
< old_start
)
65 void big_gang_check(bool long_run
)
69 for (i
= 0; i
< (long_run
? 1000 : 3); i
++) {
76 void add_and_check(void)
78 RADIX_TREE(tree
, GFP_KERNEL
);
80 item_insert(&tree
, 44);
81 item_check_present(&tree
, 44);
82 item_check_absent(&tree
, 43);
83 item_kill_tree(&tree
);
86 void dynamic_height_check(void)
89 RADIX_TREE(tree
, GFP_KERNEL
);
90 tree_verify_min_height(&tree
, 0);
92 item_insert(&tree
, 42);
93 tree_verify_min_height(&tree
, 42);
95 item_insert(&tree
, 1000000);
96 tree_verify_min_height(&tree
, 1000000);
98 assert(item_delete(&tree
, 1000000));
99 tree_verify_min_height(&tree
, 42);
101 assert(item_delete(&tree
, 42));
102 tree_verify_min_height(&tree
, 0);
104 for (i
= 0; i
< 1000; i
++) {
105 item_insert(&tree
, i
);
106 tree_verify_min_height(&tree
, i
);
111 assert(item_delete(&tree
, i
));
113 tree_verify_min_height(&tree
, 0);
117 tree_verify_min_height(&tree
, i
);
120 item_kill_tree(&tree
);
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
)
127 for (i
= 0; i
< count
; i
++) {
128 /* if (i % 1000 == 0)
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
));
134 assert(!item_tag_get(tree
, idx
[i
], totag
));
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
));
141 assert(!(item_tag_get(tree
, idx
[i
], fromtag
) ^
142 item_tag_get(tree
, idx
[i
], totag
)));
148 void copy_tag_check(void)
150 RADIX_TREE(tree
, GFP_KERNEL
);
151 unsigned long idx
[ITEMS
];
152 unsigned long start
, end
, count
= 0, tagged
, cur
, tmp
;
155 // printf("generating radix tree indices...\n");
158 if (start
> end
&& (rand() % 10)) {
163 /* Specifically create items around the start and the end of the range
164 * with high probability to check for off by one errors */
167 item_insert(&tree
, start
);
171 item_tag_set(&tree
, start
, 0);
175 item_insert(&tree
, start
-1);
177 item_tag_set(&tree
, start
-1, 0);
180 item_insert(&tree
, end
);
184 item_tag_set(&tree
, end
, 0);
188 item_insert(&tree
, end
+1);
190 item_tag_set(&tree
, end
+1, 0);
193 for (i
= 0; i
< ITEMS
; i
++) {
196 } while (item_lookup(&tree
, idx
[i
]));
198 item_insert(&tree
, idx
[i
]);
200 item_tag_set(&tree
, idx
[i
], 0);
201 if (idx
[i
] >= start
&& idx
[i
] <= end
)
204 /* if (i % 1000 == 0)
208 // printf("\ncopying tags...\n");
209 tagged
= tag_tagged_items(&tree
, NULL
, start
, end
, ITEMS
, 0, 1);
211 // printf("checking copied tags\n");
212 assert(tagged
== count
);
213 check_copied_tags(&tree
, start
, end
, idx
, ITEMS
, 0, 1);
215 /* Copy tags in several rounds */
216 // printf("\ncopying tags...\n");
217 tmp
= rand() % (count
/ 10 + 2);
218 tagged
= tag_tagged_items(&tree
, NULL
, start
, end
, tmp
, 0, 2);
219 assert(tagged
== count
);
221 // printf("%lu %lu %lu\n", tagged, tmp, count);
222 // printf("checking copied tags\n");
223 check_copied_tags(&tree
, start
, end
, idx
, ITEMS
, 0, 2);
224 verify_tag_consistency(&tree
, 0);
225 verify_tag_consistency(&tree
, 1);
226 verify_tag_consistency(&tree
, 2);
228 item_kill_tree(&tree
);
231 static void __locate_check(struct radix_tree_root
*tree
, unsigned long index
,
235 unsigned long index2
;
237 item_insert_order(tree
, index
, order
);
238 item
= item_lookup(tree
, index
);
239 index2
= find_item(tree
, item
);
240 if (index
!= index2
) {
241 printf("index %ld order %d inserted; found %ld\n",
242 index
, order
, index2
);
247 static void __order_0_locate_check(void)
249 RADIX_TREE(tree
, GFP_KERNEL
);
252 for (i
= 0; i
< 50; i
++)
253 __locate_check(&tree
, rand() % INT_MAX
, 0);
255 item_kill_tree(&tree
);
258 static void locate_check(void)
260 RADIX_TREE(tree
, GFP_KERNEL
);
262 unsigned long offset
, index
;
264 __order_0_locate_check();
266 for (order
= 0; order
< 20; order
++) {
267 for (offset
= 0; offset
< (1 << (order
+ 3));
268 offset
+= (1UL << order
)) {
269 for (index
= 0; index
< (1UL << (order
+ 5));
270 index
+= (1UL << order
)) {
271 __locate_check(&tree
, index
+ offset
, order
);
273 if (find_item(&tree
, &tree
) != -1)
276 item_kill_tree(&tree
);
280 if (find_item(&tree
, &tree
) != -1)
282 __locate_check(&tree
, -1, 0);
283 if (find_item(&tree
, &tree
) != -1)
285 item_kill_tree(&tree
);
288 static void single_thread_tests(bool long_run
)
292 printf("starting single_thread_tests: %d allocated, preempt %d\n",
293 nr_allocated
, preempt_count
);
296 printf("after multiorder_check: %d allocated, preempt %d\n",
297 nr_allocated
, preempt_count
);
300 printf("after locate_check: %d allocated, preempt %d\n",
301 nr_allocated
, preempt_count
);
304 printf("after tag_check: %d allocated, preempt %d\n",
305 nr_allocated
, preempt_count
);
308 printf("after gang_check: %d allocated, preempt %d\n",
309 nr_allocated
, preempt_count
);
312 printf("after add_and_check: %d allocated, preempt %d\n",
313 nr_allocated
, preempt_count
);
314 dynamic_height_check();
316 printf("after dynamic_height_check: %d allocated, preempt %d\n",
317 nr_allocated
, preempt_count
);
321 printf("after idr_checks: %d allocated, preempt %d\n",
322 nr_allocated
, preempt_count
);
323 big_gang_check(long_run
);
325 printf("after big_gang_check: %d allocated, preempt %d\n",
326 nr_allocated
, preempt_count
);
327 for (i
= 0; i
< (long_run
? 2000 : 3); i
++) {
333 printf("after copy_tag_check: %d allocated, preempt %d\n",
334 nr_allocated
, preempt_count
);
337 int main(int argc
, char **argv
)
339 bool long_run
= false;
341 unsigned int seed
= time(NULL
);
343 while ((opt
= getopt(argc
, argv
, "ls:")) != -1) {
347 seed
= strtoul(optarg
, NULL
, 0);
350 printf("random seed %u\n", seed
);
353 rcu_register_thread();
359 iteration_test(0, 10);
360 iteration_test(7, 20);
361 single_thread_tests(long_run
);
363 /* Free any remaining preallocated nodes */
364 radix_tree_cpu_dead(0);
369 printf("after rcu_barrier: %d allocated, preempt %d\n",
370 nr_allocated
, preempt_count
);
371 rcu_unregister_thread();