1 /*
2  * multiorder.c: Multi-order radix tree entry testing
3  * Copyright (c) 2016 Intel Corporation
4  * Author: Ross Zwisler <ross.zwisler@linux.intel.com>
5  * Author: Matthew Wilcox <matthew.r.wilcox@intel.com>
6  *
7  * This program is free software; you can redistribute it and/or modify it
8  * under the terms and conditions of the GNU General Public License,
9  * version 2, as published by the Free Software Foundation.
10  *
11  * This program is distributed in the hope it will be useful, but WITHOUT
12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
14  * more details.
15  */
16 #include <linux/radix-tree.h>
17 #include <linux/slab.h>
18 #include <linux/errno.h>
19 #include <pthread.h>
20 
21 #include "test.h"
22 
23 #define for_each_index(i, base, order) \
24 	for (i = base; i < base + (1 << order); i++)
25 
26 static void __multiorder_tag_test(int index, int order)
27 {
28 	RADIX_TREE(tree, GFP_KERNEL);
29 	int base, err, i;
30 
31 	/* our canonical entry */
32 	base = index & ~((1 << order) - 1);
33 
34 	printv(2, "Multiorder tag test with index %d, canonical entry %d\n",
35 			index, base);
36 
37 	err = item_insert_order(&tree, index, order);
38 	assert(!err);
39 
40 	/*
41 	 * Verify we get collisions for covered indices.  We try and fail to
42 	 * insert an exceptional entry so we don't leak memory via
43 	 * item_insert_order().
44 	 */
45 	for_each_index(i, base, order) {
46 		err = __radix_tree_insert(&tree, i, order,
47 				(void *)(0xA0 | RADIX_TREE_EXCEPTIONAL_ENTRY));
48 		assert(err == -EEXIST);
49 	}
50 
51 	for_each_index(i, base, order) {
52 		assert(!radix_tree_tag_get(&tree, i, 0));
53 		assert(!radix_tree_tag_get(&tree, i, 1));
54 	}
55 
56 	assert(radix_tree_tag_set(&tree, index, 0));
57 
58 	for_each_index(i, base, order) {
59 		assert(radix_tree_tag_get(&tree, i, 0));
60 		assert(!radix_tree_tag_get(&tree, i, 1));
61 	}
62 
63 	assert(tag_tagged_items(&tree, NULL, 0, ~0UL, 10, 0, 1) == 1);
64 	assert(radix_tree_tag_clear(&tree, index, 0));
65 
66 	for_each_index(i, base, order) {
67 		assert(!radix_tree_tag_get(&tree, i, 0));
68 		assert(radix_tree_tag_get(&tree, i, 1));
69 	}
70 
71 	assert(radix_tree_tag_clear(&tree, index, 1));
72 
73 	assert(!radix_tree_tagged(&tree, 0));
74 	assert(!radix_tree_tagged(&tree, 1));
75 
76 	item_kill_tree(&tree);
77 }
78 
79 static void __multiorder_tag_test2(unsigned order, unsigned long index2)
80 {
81 	RADIX_TREE(tree, GFP_KERNEL);
82 	unsigned long index = (1 << order);
83 	index2 += index;
84 
85 	assert(item_insert_order(&tree, 0, order) == 0);
86 	assert(item_insert(&tree, index2) == 0);
87 
88 	assert(radix_tree_tag_set(&tree, 0, 0));
89 	assert(radix_tree_tag_set(&tree, index2, 0));
90 
91 	assert(tag_tagged_items(&tree, NULL, 0, ~0UL, 10, 0, 1) == 2);
92 
93 	item_kill_tree(&tree);
94 }
95 
96 static void multiorder_tag_tests(void)
97 {
98 	int i, j;
99 
100 	/* test multi-order entry for indices 0-7 with no sibling pointers */
101 	__multiorder_tag_test(0, 3);
102 	__multiorder_tag_test(5, 3);
103 
104 	/* test multi-order entry for indices 8-15 with no sibling pointers */
105 	__multiorder_tag_test(8, 3);
106 	__multiorder_tag_test(15, 3);
107 
108 	/*
109 	 * Our order 5 entry covers indices 0-31 in a tree with height=2.
110 	 * This is broken up as follows:
111 	 * 0-7:		canonical entry
112 	 * 8-15:	sibling 1
113 	 * 16-23:	sibling 2
114 	 * 24-31:	sibling 3
115 	 */
116 	__multiorder_tag_test(0, 5);
117 	__multiorder_tag_test(29, 5);
118 
119 	/* same test, but with indices 32-63 */
120 	__multiorder_tag_test(32, 5);
121 	__multiorder_tag_test(44, 5);
122 
123 	/*
124 	 * Our order 8 entry covers indices 0-255 in a tree with height=3.
125 	 * This is broken up as follows:
126 	 * 0-63:	canonical entry
127 	 * 64-127:	sibling 1
128 	 * 128-191:	sibling 2
129 	 * 192-255:	sibling 3
130 	 */
131 	__multiorder_tag_test(0, 8);
132 	__multiorder_tag_test(190, 8);
133 
134 	/* same test, but with indices 256-511 */
135 	__multiorder_tag_test(256, 8);
136 	__multiorder_tag_test(300, 8);
137 
138 	__multiorder_tag_test(0x12345678UL, 8);
139 
140 	for (i = 1; i < 10; i++)
141 		for (j = 0; j < (10 << i); j++)
142 			__multiorder_tag_test2(i, j);
143 }
144 
145 static void multiorder_check(unsigned long index, int order)
146 {
147 	unsigned long i;
148 	unsigned long min = index & ~((1UL << order) - 1);
149 	unsigned long max = min + (1UL << order);
150 	void **slot;
151 	struct item *item2 = item_create(min, order);
152 	RADIX_TREE(tree, GFP_KERNEL);
153 
154 	printv(2, "Multiorder index %ld, order %d\n", index, order);
155 
156 	assert(item_insert_order(&tree, index, order) == 0);
157 
158 	for (i = min; i < max; i++) {
159 		struct item *item = item_lookup(&tree, i);
160 		assert(item != 0);
161 		assert(item->index == index);
162 	}
163 	for (i = 0; i < min; i++)
164 		item_check_absent(&tree, i);
165 	for (i = max; i < 2*max; i++)
166 		item_check_absent(&tree, i);
167 	for (i = min; i < max; i++)
168 		assert(radix_tree_insert(&tree, i, item2) == -EEXIST);
169 
170 	slot = radix_tree_lookup_slot(&tree, index);
171 	free(*slot);
172 	radix_tree_replace_slot(&tree, slot, item2);
173 	for (i = min; i < max; i++) {
174 		struct item *item = item_lookup(&tree, i);
175 		assert(item != 0);
176 		assert(item->index == min);
177 	}
178 
179 	assert(item_delete(&tree, min) != 0);
180 
181 	for (i = 0; i < 2*max; i++)
182 		item_check_absent(&tree, i);
183 }
184 
185 static void multiorder_shrink(unsigned long index, int order)
186 {
187 	unsigned long i;
188 	unsigned long max = 1 << order;
189 	RADIX_TREE(tree, GFP_KERNEL);
190 	struct radix_tree_node *node;
191 
192 	printv(2, "Multiorder shrink index %ld, order %d\n", index, order);
193 
194 	assert(item_insert_order(&tree, 0, order) == 0);
195 
196 	node = tree.rnode;
197 
198 	assert(item_insert(&tree, index) == 0);
199 	assert(node != tree.rnode);
200 
201 	assert(item_delete(&tree, index) != 0);
202 	assert(node == tree.rnode);
203 
204 	for (i = 0; i < max; i++) {
205 		struct item *item = item_lookup(&tree, i);
206 		assert(item != 0);
207 		assert(item->index == 0);
208 	}
209 	for (i = max; i < 2*max; i++)
210 		item_check_absent(&tree, i);
211 
212 	if (!item_delete(&tree, 0)) {
213 		printv(2, "failed to delete index %ld (order %d)\n", index, order);
214 		abort();
215 	}
216 
217 	for (i = 0; i < 2*max; i++)
218 		item_check_absent(&tree, i);
219 }
220 
221 static void multiorder_insert_bug(void)
222 {
223 	RADIX_TREE(tree, GFP_KERNEL);
224 
225 	item_insert(&tree, 0);
226 	radix_tree_tag_set(&tree, 0, 0);
227 	item_insert_order(&tree, 3 << 6, 6);
228 
229 	item_kill_tree(&tree);
230 }
231 
232 void multiorder_iteration(void)
233 {
234 	RADIX_TREE(tree, GFP_KERNEL);
235 	struct radix_tree_iter iter;
236 	void **slot;
237 	int i, j, err;
238 
239 	printv(1, "Multiorder iteration test\n");
240 
241 #define NUM_ENTRIES 11
242 	int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128};
243 	int order[NUM_ENTRIES] = {1, 1, 2, 3,  4,  1,  0,  1,  3,  0, 7};
244 
245 	for (i = 0; i < NUM_ENTRIES; i++) {
246 		err = item_insert_order(&tree, index[i], order[i]);
247 		assert(!err);
248 	}
249 
250 	for (j = 0; j < 256; j++) {
251 		for (i = 0; i < NUM_ENTRIES; i++)
252 			if (j <= (index[i] | ((1 << order[i]) - 1)))
253 				break;
254 
255 		radix_tree_for_each_slot(slot, &tree, &iter, j) {
256 			int height = order[i] / RADIX_TREE_MAP_SHIFT;
257 			int shift = height * RADIX_TREE_MAP_SHIFT;
258 			unsigned long mask = (1UL << order[i]) - 1;
259 			struct item *item = *slot;
260 
261 			assert((iter.index | mask) == (index[i] | mask));
262 			assert(iter.shift == shift);
263 			assert(!radix_tree_is_internal_node(item));
264 			assert((item->index | mask) == (index[i] | mask));
265 			assert(item->order == order[i]);
266 			i++;
267 		}
268 	}
269 
270 	item_kill_tree(&tree);
271 }
272 
273 void multiorder_tagged_iteration(void)
274 {
275 	RADIX_TREE(tree, GFP_KERNEL);
276 	struct radix_tree_iter iter;
277 	void **slot;
278 	int i, j;
279 
280 	printv(1, "Multiorder tagged iteration test\n");
281 
282 #define MT_NUM_ENTRIES 9
283 	int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128};
284 	int order[MT_NUM_ENTRIES] = {1, 0, 2, 4,  3,  1,  3,  0,   7};
285 
286 #define TAG_ENTRIES 7
287 	int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128};
288 
289 	for (i = 0; i < MT_NUM_ENTRIES; i++)
290 		assert(!item_insert_order(&tree, index[i], order[i]));
291 
292 	assert(!radix_tree_tagged(&tree, 1));
293 
294 	for (i = 0; i < TAG_ENTRIES; i++)
295 		assert(radix_tree_tag_set(&tree, tag_index[i], 1));
296 
297 	for (j = 0; j < 256; j++) {
298 		int k;
299 
300 		for (i = 0; i < TAG_ENTRIES; i++) {
301 			for (k = i; index[k] < tag_index[i]; k++)
302 				;
303 			if (j <= (index[k] | ((1 << order[k]) - 1)))
304 				break;
305 		}
306 
307 		radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
308 			unsigned long mask;
309 			struct item *item = *slot;
310 			for (k = i; index[k] < tag_index[i]; k++)
311 				;
312 			mask = (1UL << order[k]) - 1;
313 
314 			assert((iter.index | mask) == (tag_index[i] | mask));
315 			assert(!radix_tree_is_internal_node(item));
316 			assert((item->index | mask) == (tag_index[i] | mask));
317 			assert(item->order == order[k]);
318 			i++;
319 		}
320 	}
321 
322 	assert(tag_tagged_items(&tree, NULL, 0, ~0UL, TAG_ENTRIES, 1, 2) ==
323 				TAG_ENTRIES);
324 
325 	for (j = 0; j < 256; j++) {
326 		int mask, k;
327 
328 		for (i = 0; i < TAG_ENTRIES; i++) {
329 			for (k = i; index[k] < tag_index[i]; k++)
330 				;
331 			if (j <= (index[k] | ((1 << order[k]) - 1)))
332 				break;
333 		}
334 
335 		radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
336 			struct item *item = *slot;
337 			for (k = i; index[k] < tag_index[i]; k++)
338 				;
339 			mask = (1 << order[k]) - 1;
340 
341 			assert((iter.index | mask) == (tag_index[i] | mask));
342 			assert(!radix_tree_is_internal_node(item));
343 			assert((item->index | mask) == (tag_index[i] | mask));
344 			assert(item->order == order[k]);
345 			i++;
346 		}
347 	}
348 
349 	assert(tag_tagged_items(&tree, NULL, 1, ~0UL, MT_NUM_ENTRIES * 2, 1, 0)
350 			== TAG_ENTRIES);
351 	i = 0;
352 	radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) {
353 		assert(iter.index == tag_index[i]);
354 		i++;
355 	}
356 
357 	item_kill_tree(&tree);
358 }
359 
360 /*
361  * Basic join checks: make sure we can't find an entry in the tree after
362  * a larger entry has replaced it
363  */
364 static void multiorder_join1(unsigned long index,
365 				unsigned order1, unsigned order2)
366 {
367 	unsigned long loc;
368 	void *item, *item2 = item_create(index + 1, order1);
369 	RADIX_TREE(tree, GFP_KERNEL);
370 
371 	item_insert_order(&tree, index, order2);
372 	item = radix_tree_lookup(&tree, index);
373 	radix_tree_join(&tree, index + 1, order1, item2);
374 	loc = find_item(&tree, item);
375 	if (loc == -1)
376 		free(item);
377 	item = radix_tree_lookup(&tree, index + 1);
378 	assert(item == item2);
379 	item_kill_tree(&tree);
380 }
381 
382 /*
383  * Check that the accounting of exceptional entries is handled correctly
384  * by joining an exceptional entry to a normal pointer.
385  */
386 static void multiorder_join2(unsigned order1, unsigned order2)
387 {
388 	RADIX_TREE(tree, GFP_KERNEL);
389 	struct radix_tree_node *node;
390 	void *item1 = item_create(0, order1);
391 	void *item2;
392 
393 	item_insert_order(&tree, 0, order2);
394 	radix_tree_insert(&tree, 1 << order2, (void *)0x12UL);
395 	item2 = __radix_tree_lookup(&tree, 1 << order2, &node, NULL);
396 	assert(item2 == (void *)0x12UL);
397 	assert(node->exceptional == 1);
398 
399 	item2 = radix_tree_lookup(&tree, 0);
400 	free(item2);
401 
402 	radix_tree_join(&tree, 0, order1, item1);
403 	item2 = __radix_tree_lookup(&tree, 1 << order2, &node, NULL);
404 	assert(item2 == item1);
405 	assert(node->exceptional == 0);
406 	item_kill_tree(&tree);
407 }
408 
409 /*
410  * This test revealed an accounting bug for exceptional entries at one point.
411  * Nodes were being freed back into the pool with an elevated exception count
412  * by radix_tree_join() and then radix_tree_split() was failing to zero the
413  * count of exceptional entries.
414  */
415 static void multiorder_join3(unsigned int order)
416 {
417 	RADIX_TREE(tree, GFP_KERNEL);
418 	struct radix_tree_node *node;
419 	void **slot;
420 	struct radix_tree_iter iter;
421 	unsigned long i;
422 
423 	for (i = 0; i < (1 << order); i++) {
424 		radix_tree_insert(&tree, i, (void *)0x12UL);
425 	}
426 
427 	radix_tree_join(&tree, 0, order, (void *)0x16UL);
428 	rcu_barrier();
429 
430 	radix_tree_split(&tree, 0, 0);
431 
432 	radix_tree_for_each_slot(slot, &tree, &iter, 0) {
433 		radix_tree_iter_replace(&tree, &iter, slot, (void *)0x12UL);
434 	}
435 
436 	__radix_tree_lookup(&tree, 0, &node, NULL);
437 	assert(node->exceptional == node->count);
438 
439 	item_kill_tree(&tree);
440 }
441 
442 static void multiorder_join(void)
443 {
444 	int i, j, idx;
445 
446 	for (idx = 0; idx < 1024; idx = idx * 2 + 3) {
447 		for (i = 1; i < 15; i++) {
448 			for (j = 0; j < i; j++) {
449 				multiorder_join1(idx, i, j);
450 			}
451 		}
452 	}
453 
454 	for (i = 1; i < 15; i++) {
455 		for (j = 0; j < i; j++) {
456 			multiorder_join2(i, j);
457 		}
458 	}
459 
460 	for (i = 3; i < 10; i++) {
461 		multiorder_join3(i);
462 	}
463 }
464 
465 static void check_mem(unsigned old_order, unsigned new_order, unsigned alloc)
466 {
467 	struct radix_tree_preload *rtp = &radix_tree_preloads;
468 	if (rtp->nr != 0)
469 		printv(2, "split(%u %u) remaining %u\n", old_order, new_order,
470 							rtp->nr);
471 	/*
472 	 * Can't check for equality here as some nodes may have been
473 	 * RCU-freed while we ran.  But we should never finish with more
474 	 * nodes allocated since they should have all been preloaded.
475 	 */
476 	if (nr_allocated > alloc)
477 		printv(2, "split(%u %u) allocated %u %u\n", old_order, new_order,
478 							alloc, nr_allocated);
479 }
480 
481 static void __multiorder_split(int old_order, int new_order)
482 {
483 	RADIX_TREE(tree, GFP_ATOMIC);
484 	void **slot;
485 	struct radix_tree_iter iter;
486 	unsigned alloc;
487 	struct item *item;
488 
489 	radix_tree_preload(GFP_KERNEL);
490 	assert(item_insert_order(&tree, 0, old_order) == 0);
491 	radix_tree_preload_end();
492 
493 	/* Wipe out the preloaded cache or it'll confuse check_mem() */
494 	radix_tree_cpu_dead(0);
495 
496 	item = radix_tree_tag_set(&tree, 0, 2);
497 
498 	radix_tree_split_preload(old_order, new_order, GFP_KERNEL);
499 	alloc = nr_allocated;
500 	radix_tree_split(&tree, 0, new_order);
501 	check_mem(old_order, new_order, alloc);
502 	radix_tree_for_each_slot(slot, &tree, &iter, 0) {
503 		radix_tree_iter_replace(&tree, &iter, slot,
504 					item_create(iter.index, new_order));
505 	}
506 	radix_tree_preload_end();
507 
508 	item_kill_tree(&tree);
509 	free(item);
510 }
511 
512 static void __multiorder_split2(int old_order, int new_order)
513 {
514 	RADIX_TREE(tree, GFP_KERNEL);
515 	void **slot;
516 	struct radix_tree_iter iter;
517 	struct radix_tree_node *node;
518 	void *item;
519 
520 	__radix_tree_insert(&tree, 0, old_order, (void *)0x12);
521 
522 	item = __radix_tree_lookup(&tree, 0, &node, NULL);
523 	assert(item == (void *)0x12);
524 	assert(node->exceptional > 0);
525 
526 	radix_tree_split(&tree, 0, new_order);
527 	radix_tree_for_each_slot(slot, &tree, &iter, 0) {
528 		radix_tree_iter_replace(&tree, &iter, slot,
529 					item_create(iter.index, new_order));
530 	}
531 
532 	item = __radix_tree_lookup(&tree, 0, &node, NULL);
533 	assert(item != (void *)0x12);
534 	assert(node->exceptional == 0);
535 
536 	item_kill_tree(&tree);
537 }
538 
539 static void __multiorder_split3(int old_order, int new_order)
540 {
541 	RADIX_TREE(tree, GFP_KERNEL);
542 	void **slot;
543 	struct radix_tree_iter iter;
544 	struct radix_tree_node *node;
545 	void *item;
546 
547 	__radix_tree_insert(&tree, 0, old_order, (void *)0x12);
548 
549 	item = __radix_tree_lookup(&tree, 0, &node, NULL);
550 	assert(item == (void *)0x12);
551 	assert(node->exceptional > 0);
552 
553 	radix_tree_split(&tree, 0, new_order);
554 	radix_tree_for_each_slot(slot, &tree, &iter, 0) {
555 		radix_tree_iter_replace(&tree, &iter, slot, (void *)0x16);
556 	}
557 
558 	item = __radix_tree_lookup(&tree, 0, &node, NULL);
559 	assert(item == (void *)0x16);
560 	assert(node->exceptional > 0);
561 
562 	item_kill_tree(&tree);
563 
564 	__radix_tree_insert(&tree, 0, old_order, (void *)0x12);
565 
566 	item = __radix_tree_lookup(&tree, 0, &node, NULL);
567 	assert(item == (void *)0x12);
568 	assert(node->exceptional > 0);
569 
570 	radix_tree_split(&tree, 0, new_order);
571 	radix_tree_for_each_slot(slot, &tree, &iter, 0) {
572 		if (iter.index == (1 << new_order))
573 			radix_tree_iter_replace(&tree, &iter, slot,
574 						(void *)0x16);
575 		else
576 			radix_tree_iter_replace(&tree, &iter, slot, NULL);
577 	}
578 
579 	item = __radix_tree_lookup(&tree, 1 << new_order, &node, NULL);
580 	assert(item == (void *)0x16);
581 	assert(node->count == node->exceptional);
582 	do {
583 		node = node->parent;
584 		if (!node)
585 			break;
586 		assert(node->count == 1);
587 		assert(node->exceptional == 0);
588 	} while (1);
589 
590 	item_kill_tree(&tree);
591 }
592 
593 static void multiorder_split(void)
594 {
595 	int i, j;
596 
597 	for (i = 3; i < 11; i++)
598 		for (j = 0; j < i; j++) {
599 			__multiorder_split(i, j);
600 			__multiorder_split2(i, j);
601 			__multiorder_split3(i, j);
602 		}
603 }
604 
605 static void multiorder_account(void)
606 {
607 	RADIX_TREE(tree, GFP_KERNEL);
608 	struct radix_tree_node *node;
609 	void **slot;
610 
611 	item_insert_order(&tree, 0, 5);
612 
613 	__radix_tree_insert(&tree, 1 << 5, 5, (void *)0x12);
614 	__radix_tree_lookup(&tree, 0, &node, NULL);
615 	assert(node->count == node->exceptional * 2);
616 	radix_tree_delete(&tree, 1 << 5);
617 	assert(node->exceptional == 0);
618 
619 	__radix_tree_insert(&tree, 1 << 5, 5, (void *)0x12);
620 	__radix_tree_lookup(&tree, 1 << 5, &node, &slot);
621 	assert(node->count == node->exceptional * 2);
622 	__radix_tree_replace(&tree, node, slot, NULL, NULL);
623 	assert(node->exceptional == 0);
624 
625 	item_kill_tree(&tree);
626 }
627 
628 bool stop_iteration = false;
629 
630 static void *creator_func(void *ptr)
631 {
632 	/* 'order' is set up to ensure we have sibling entries */
633 	unsigned int order = RADIX_TREE_MAP_SHIFT - 1;
634 	struct radix_tree_root *tree = ptr;
635 	int i;
636 
637 	for (i = 0; i < 10000; i++) {
638 		item_insert_order(tree, 0, order);
639 		item_delete_rcu(tree, 0);
640 	}
641 
642 	stop_iteration = true;
643 	return NULL;
644 }
645 
646 static void *iterator_func(void *ptr)
647 {
648 	struct radix_tree_root *tree = ptr;
649 	struct radix_tree_iter iter;
650 	struct item *item;
651 	void **slot;
652 
653 	while (!stop_iteration) {
654 		rcu_read_lock();
655 		radix_tree_for_each_slot(slot, tree, &iter, 0) {
656 			item = radix_tree_deref_slot(slot);
657 
658 			if (!item)
659 				continue;
660 			if (radix_tree_deref_retry(item)) {
661 				slot = radix_tree_iter_retry(&iter);
662 				continue;
663 			}
664 
665 			item_sanity(item, iter.index);
666 		}
667 		rcu_read_unlock();
668 	}
669 	return NULL;
670 }
671 
672 static void multiorder_iteration_race(void)
673 {
674 	const int num_threads = sysconf(_SC_NPROCESSORS_ONLN);
675 	pthread_t worker_thread[num_threads];
676 	RADIX_TREE(tree, GFP_KERNEL);
677 	int i;
678 
679 	pthread_create(&worker_thread[0], NULL, &creator_func, &tree);
680 	for (i = 1; i < num_threads; i++)
681 		pthread_create(&worker_thread[i], NULL, &iterator_func, &tree);
682 
683 	for (i = 0; i < num_threads; i++)
684 		pthread_join(worker_thread[i], NULL);
685 
686 	item_kill_tree(&tree);
687 }
688 
689 void multiorder_checks(void)
690 {
691 	int i;
692 
693 	for (i = 0; i < 20; i++) {
694 		multiorder_check(200, i);
695 		multiorder_check(0, i);
696 		multiorder_check((1UL << i) + 1, i);
697 	}
698 
699 	for (i = 0; i < 15; i++)
700 		multiorder_shrink((1UL << (i + RADIX_TREE_MAP_SHIFT)), i);
701 
702 	multiorder_insert_bug();
703 	multiorder_tag_tests();
704 	multiorder_iteration();
705 	multiorder_tagged_iteration();
706 	multiorder_join();
707 	multiorder_split();
708 	multiorder_account();
709 	multiorder_iteration_race();
710 
711 	radix_tree_cpu_dead(0);
712 }
713 
714 int __weak main(void)
715 {
716 	radix_tree_init();
717 	multiorder_checks();
718 	return 0;
719 }
720