7 #include <linux/slab.h>
8 #include <linux/radix-tree.h>
11 #include "regression.h"
13 void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
16 RADIX_TREE(tree, GFP_KERNEL);
20 for (idx = -down; idx < up; idx++)
21 item_insert(&tree, middle + idx);
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);
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);
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);
44 void __big_gang_check(void)
51 unsigned long old_start;
53 // printf("0x%08lx\n", start);
54 __gang_check(start, rand() % 113 + 1, rand() % 71,
55 rand() % 157, rand() % 91 + 1);
57 start += rand() % 1000000;
59 if (start < old_start)
64 void big_gang_check(bool long_run)
68 for (i = 0; i < (long_run ? 1000 : 3); i++) {
75 void add_and_check(void)
77 RADIX_TREE(tree, GFP_KERNEL);
79 item_insert(&tree, 44);
80 item_check_present(&tree, 44);
81 item_check_absent(&tree, 43);
82 item_kill_tree(&tree);
85 void dynamic_height_check(void)
88 RADIX_TREE(tree, GFP_KERNEL);
89 tree_verify_min_height(&tree, 0);
91 item_insert(&tree, 42);
92 tree_verify_min_height(&tree, 42);
94 item_insert(&tree, 1000000);
95 tree_verify_min_height(&tree, 1000000);
97 assert(item_delete(&tree, 1000000));
98 tree_verify_min_height(&tree, 42);
100 assert(item_delete(&tree, 42));
101 tree_verify_min_height(&tree, 0);
103 for (i = 0; i < 1000; i++) {
104 item_insert(&tree, i);
105 tree_verify_min_height(&tree, i);
110 assert(item_delete(&tree, i));
112 tree_verify_min_height(&tree, 0);
116 tree_verify_min_height(&tree, i);
119 item_kill_tree(&tree);
122 void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag)
126 for (i = 0; i < count; i++) {
127 /* if (i % 1000 == 0)
129 if (idx[i] < start || idx[i] > end) {
130 if (item_tag_get(tree, idx[i], totag)) {
131 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 assert(!item_tag_get(tree, idx[i], totag));
136 if (item_tag_get(tree, idx[i], fromtag) ^
137 item_tag_get(tree, idx[i], totag)) {
138 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 assert(!(item_tag_get(tree, idx[i], fromtag) ^
141 item_tag_get(tree, idx[i], totag)));
147 void copy_tag_check(void)
149 RADIX_TREE(tree, GFP_KERNEL);
150 unsigned long idx[ITEMS];
151 unsigned long start, end, count = 0, tagged, cur, tmp;
154 // printf("generating radix tree indices...\n");
157 if (start > end && (rand() % 10)) {
162 /* Specifically create items around the start and the end of the range
163 * with high probability to check for off by one errors */
166 item_insert(&tree, start);
170 item_tag_set(&tree, start, 0);
174 item_insert(&tree, start-1);
176 item_tag_set(&tree, start-1, 0);
179 item_insert(&tree, end);
183 item_tag_set(&tree, end, 0);
187 item_insert(&tree, end+1);
189 item_tag_set(&tree, end+1, 0);
192 for (i = 0; i < ITEMS; i++) {
195 } while (item_lookup(&tree, idx[i]));
197 item_insert(&tree, idx[i]);
199 item_tag_set(&tree, idx[i], 0);
200 if (idx[i] >= start && idx[i] <= end)
203 /* if (i % 1000 == 0)
207 // printf("\ncopying tags...\n");
208 tagged = tag_tagged_items(&tree, NULL, start, end, ITEMS, 0, 1);
210 // printf("checking copied tags\n");
211 assert(tagged == count);
212 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
214 /* Copy tags in several rounds */
215 // printf("\ncopying tags...\n");
216 tmp = rand() % (count / 10 + 2);
217 tagged = tag_tagged_items(&tree, NULL, start, end, tmp, 0, 2);
218 assert(tagged == count);
220 // printf("%lu %lu %lu\n", tagged, tmp, count);
221 // printf("checking copied tags\n");
222 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
223 verify_tag_consistency(&tree, 0);
224 verify_tag_consistency(&tree, 1);
225 verify_tag_consistency(&tree, 2);
227 item_kill_tree(&tree);
230 static void __locate_check(struct radix_tree_root *tree, unsigned long index,
234 unsigned long index2;
236 item_insert_order(tree, index, order);
237 item = item_lookup(tree, index);
238 index2 = find_item(tree, item);
239 if (index != index2) {
240 printf("index %ld order %d inserted; found %ld\n",
241 index, order, index2);
246 static void __order_0_locate_check(void)
248 RADIX_TREE(tree, GFP_KERNEL);
251 for (i = 0; i < 50; i++)
252 __locate_check(&tree, rand() % INT_MAX, 0);
254 item_kill_tree(&tree);
257 static void locate_check(void)
259 RADIX_TREE(tree, GFP_KERNEL);
261 unsigned long offset, index;
263 __order_0_locate_check();
265 for (order = 0; order < 20; order++) {
266 for (offset = 0; offset < (1 << (order + 3));
267 offset += (1UL << order)) {
268 for (index = 0; index < (1UL << (order + 5));
269 index += (1UL << order)) {
270 __locate_check(&tree, index + offset, order);
272 if (find_item(&tree, &tree) != -1)
275 item_kill_tree(&tree);
279 if (find_item(&tree, &tree) != -1)
281 __locate_check(&tree, -1, 0);
282 if (find_item(&tree, &tree) != -1)
284 item_kill_tree(&tree);
287 static void single_thread_tests(bool long_run)
291 printf("starting single_thread_tests: %d allocated, preempt %d\n",
292 nr_allocated, preempt_count);
295 printf("after multiorder_check: %d allocated, preempt %d\n",
296 nr_allocated, preempt_count);
299 printf("after locate_check: %d allocated, preempt %d\n",
300 nr_allocated, preempt_count);
303 printf("after tag_check: %d allocated, preempt %d\n",
304 nr_allocated, preempt_count);
307 printf("after gang_check: %d allocated, preempt %d\n",
308 nr_allocated, preempt_count);
311 printf("after add_and_check: %d allocated, preempt %d\n",
312 nr_allocated, preempt_count);
313 dynamic_height_check();
315 printf("after dynamic_height_check: %d allocated, preempt %d\n",
316 nr_allocated, preempt_count);
317 big_gang_check(long_run);
319 printf("after big_gang_check: %d allocated, preempt %d\n",
320 nr_allocated, preempt_count);
321 for (i = 0; i < (long_run ? 2000 : 3); i++) {
327 printf("after copy_tag_check: %d allocated, preempt %d\n",
328 nr_allocated, preempt_count);
331 int main(int argc, char **argv)
333 bool long_run = false;
335 unsigned int seed = time(NULL);
337 while ((opt = getopt(argc, argv, "ls:")) != -1) {
341 seed = strtoul(optarg, NULL, 0);
344 printf("random seed %u\n", seed);
347 rcu_register_thread();
353 iteration_test(0, 10);
354 iteration_test(7, 20);
355 single_thread_tests(long_run);
357 /* Free any remaining preallocated nodes */
358 radix_tree_cpu_dead(0);
363 printf("after rcu_barrier: %d allocated, preempt %d\n",
364 nr_allocated, preempt_count);
365 rcu_unregister_thread();