Lines Matching full:mt
30 #define RCU_MT_BUG_ON(test, y) {if (y) { test->stop = true; } MT_BUG_ON(test->mt, y); }
33 struct maple_tree *mt; member
50 struct maple_tree *mt; member
92 static noinline void __init check_new_node(struct maple_tree *mt) in check_new_node() argument
100 MA_STATE(mas, mt, 0, 0); in check_new_node()
105 mtree_lock(mt); in check_new_node()
110 MT_BUG_ON(mt, mas_alloc_req(&mas) != 3); in check_new_node()
112 MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM)); in check_new_node()
113 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
115 MT_BUG_ON(mt, mas_allocated(&mas) != 3); in check_new_node()
117 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
118 MT_BUG_ON(mt, mn == NULL); in check_new_node()
119 MT_BUG_ON(mt, mas.alloc == NULL); in check_new_node()
120 MT_BUG_ON(mt, mas.alloc->slot[0] == NULL); in check_new_node()
124 mtree_unlock(mt); in check_new_node()
128 mtree_lock(mt); in check_new_node()
132 MT_BUG_ON(mt, mas_alloc_req(&mas) != 1); in check_new_node()
135 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
138 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
139 MT_BUG_ON(mt, mn == NULL); in check_new_node()
140 MT_BUG_ON(mt, mn->slot[0] != NULL); in check_new_node()
141 MT_BUG_ON(mt, mn->slot[1] != NULL); in check_new_node()
142 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
153 MT_BUG_ON(mt, mas_allocated(&mas) != 3); in check_new_node()
155 MT_BUG_ON(mt, mas_alloc_req(&mas) != 0); in check_new_node()
157 MT_BUG_ON(mt, mas.alloc == NULL); in check_new_node()
158 MT_BUG_ON(mt, mas.alloc->slot[0] == NULL); in check_new_node()
159 MT_BUG_ON(mt, mas.alloc->slot[1] == NULL); in check_new_node()
161 MT_BUG_ON(mt, mas_allocated(&mas) != 3); in check_new_node()
168 MT_BUG_ON(mt, mas_alloc_req(&mas) != 1); in check_new_node()
171 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
172 MT_BUG_ON(mt, mas_allocated(&mas) != 1); in check_new_node()
175 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
176 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
177 MT_BUG_ON(mt, mn == NULL); in check_new_node()
178 MT_BUG_ON(mt, mn->slot[0] != NULL); in check_new_node()
179 MT_BUG_ON(mt, mn->slot[1] != NULL); in check_new_node()
180 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
182 MT_BUG_ON(mt, mas_allocated(&mas) != 1); in check_new_node()
183 MT_BUG_ON(mt, mas.alloc->node_count); in check_new_node()
186 MT_BUG_ON(mt, mas_alloc_req(&mas) != 2); in check_new_node()
188 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
189 MT_BUG_ON(mt, mas_allocated(&mas) != 3); in check_new_node()
190 MT_BUG_ON(mt, mas.alloc == NULL); in check_new_node()
191 MT_BUG_ON(mt, mas.alloc->slot[0] == NULL); in check_new_node()
192 MT_BUG_ON(mt, mas.alloc->slot[1] == NULL); in check_new_node()
195 MT_BUG_ON(mt, mas_allocated(&mas) != i); in check_new_node()
196 MT_BUG_ON(mt, !mn); in check_new_node()
197 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
204 MT_BUG_ON(mt, mas_alloc_req(&mas) != total); in check_new_node()
206 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
226 MT_BUG_ON(mt, mas.alloc->node_count != e); in check_new_node()
228 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
229 MT_BUG_ON(mt, mas_allocated(&mas) != i - 1); in check_new_node()
230 MT_BUG_ON(mt, !mn); in check_new_node()
239 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
242 MT_BUG_ON(mt, mas_allocated(&mas) != j - 1); in check_new_node()
243 MT_BUG_ON(mt, !mn); in check_new_node()
244 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
246 MT_BUG_ON(mt, mas_allocated(&mas) != j); in check_new_node()
248 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
249 MT_BUG_ON(mt, mas_allocated(&mas) != j - 1); in check_new_node()
253 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
257 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
259 MT_BUG_ON(mt, mas_allocated(&mas) != i - j); in check_new_node()
261 MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1); in check_new_node()
267 MT_BUG_ON(mt, mas_allocated(&mas) != i - j); in check_new_node()
269 MT_BUG_ON(mt, mas_allocated(&mas) != i); in check_new_node()
271 MT_BUG_ON(mt, mas_allocated(&mas) != i - j); in check_new_node()
273 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
276 MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1); in check_new_node()
279 MT_BUG_ON(mt, mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
289 MT_BUG_ON(mt, !mas.alloc); in check_new_node()
295 MT_BUG_ON(mt, !smn->slot[j]); in check_new_node()
301 MT_BUG_ON(mt, mas_allocated(&mas) != total); in check_new_node()
305 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
309 MT_BUG_ON(mt, mas_allocated(&mas) != i); /* check request filled */ in check_new_node()
312 MT_BUG_ON(mt, mn == NULL); in check_new_node()
313 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
317 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
321 MA_STATE(mas2, mt, 0, 0); in check_new_node()
324 MT_BUG_ON(mt, mas_allocated(&mas) != i); /* check request filled */ in check_new_node()
327 MT_BUG_ON(mt, mn == NULL); in check_new_node()
328 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
330 MT_BUG_ON(mt, mas_allocated(&mas2) != j); in check_new_node()
332 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
333 MT_BUG_ON(mt, mas_allocated(&mas2) != i); in check_new_node()
336 MT_BUG_ON(mt, mas_allocated(&mas2) != j); in check_new_node()
338 MT_BUG_ON(mt, mn == NULL); in check_new_node()
339 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
343 MT_BUG_ON(mt, mas_allocated(&mas2) != 0); in check_new_node()
347 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
349 MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM)); in check_new_node()
350 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
351 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1); in check_new_node()
352 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS); in check_new_node()
355 MT_BUG_ON(mt, mn == NULL); in check_new_node()
356 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
357 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS); in check_new_node()
358 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS - 1); in check_new_node()
361 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1); in check_new_node()
362 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS); in check_new_node()
366 MT_BUG_ON(mt, mas_alloc_req(&mas) != 1); in check_new_node()
367 MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM)); in check_new_node()
368 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
369 MT_BUG_ON(mt, mas_alloc_req(&mas)); in check_new_node()
370 MT_BUG_ON(mt, mas.alloc->node_count != 1); in check_new_node()
371 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 2); in check_new_node()
373 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
374 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1); in check_new_node()
375 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS); in check_new_node()
377 MT_BUG_ON(mt, mas.alloc->node_count != 1); in check_new_node()
378 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 2); in check_new_node()
380 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
385 MT_BUG_ON(mt, not_empty(mn)); in check_new_node()
389 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
446 MT_BUG_ON(mt, mas_allocated(&mas) != 5); in check_new_node()
451 MT_BUG_ON(mt, mas_allocated(&mas) != 10); in check_new_node()
457 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS - 1); in check_new_node()
462 MT_BUG_ON(mt, mas_allocated(&mas) != 10 + MAPLE_ALLOC_SLOTS - 1); in check_new_node()
468 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1); in check_new_node()
473 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 2); in check_new_node()
479 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 1); in check_new_node()
484 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 3 + 2); in check_new_node()
487 mtree_unlock(mt); in check_new_node()
493 static noinline void __init check_erase(struct maple_tree *mt, unsigned long index, in check_erase() argument
496 MT_BUG_ON(mt, mtree_test_erase(mt, index) != ptr); in check_erase()
499 #define erase_check_load(mt, i) check_load(mt, set[i], entry[i%2]) argument
500 #define erase_check_insert(mt, i) check_insert(mt, set[i], entry[i%2]) argument
501 #define erase_check_erase(mt, i) check_erase(mt, set[i], entry[i%2]) argument
503 static noinline void __init check_erase_testset(struct maple_tree *mt) in check_erase_testset() argument
521 void *entry[2] = { ptr, mt }; in check_erase_testset()
526 mt_set_in_rcu(mt); in check_erase_testset()
528 erase_check_insert(mt, i); in check_erase_testset()
530 erase_check_load(mt, i); in check_erase_testset()
533 erase_check_erase(mt, 1); in check_erase_testset()
534 erase_check_load(mt, 0); in check_erase_testset()
535 check_load(mt, set[1], NULL); in check_erase_testset()
537 erase_check_load(mt, i); in check_erase_testset()
540 erase_check_erase(mt, 2); in check_erase_testset()
541 erase_check_load(mt, 0); in check_erase_testset()
542 check_load(mt, set[1], NULL); in check_erase_testset()
543 check_load(mt, set[2], NULL); in check_erase_testset()
545 erase_check_insert(mt, 1); in check_erase_testset()
546 erase_check_insert(mt, 2); in check_erase_testset()
549 erase_check_load(mt, i); in check_erase_testset()
552 erase_check_load(mt, 3); in check_erase_testset()
553 erase_check_erase(mt, 1); in check_erase_testset()
554 erase_check_load(mt, 0); in check_erase_testset()
555 check_load(mt, set[1], NULL); in check_erase_testset()
557 erase_check_load(mt, i); in check_erase_testset()
563 root_node = mt->ma_root; in check_erase_testset()
564 erase_check_insert(mt, 1); in check_erase_testset()
566 erase_check_load(mt, 0); in check_erase_testset()
567 check_load(mt, 5016, NULL); in check_erase_testset()
568 erase_check_load(mt, 1); in check_erase_testset()
569 check_load(mt, 5013, NULL); in check_erase_testset()
570 erase_check_load(mt, 2); in check_erase_testset()
571 check_load(mt, 5018, NULL); in check_erase_testset()
572 erase_check_load(mt, 3); in check_erase_testset()
574 erase_check_erase(mt, 2); /* erase 5017 to check append */ in check_erase_testset()
575 erase_check_load(mt, 0); in check_erase_testset()
576 check_load(mt, 5016, NULL); in check_erase_testset()
577 erase_check_load(mt, 1); in check_erase_testset()
578 check_load(mt, 5013, NULL); in check_erase_testset()
579 check_load(mt, set[2], NULL); in check_erase_testset()
580 check_load(mt, 5018, NULL); in check_erase_testset()
582 erase_check_load(mt, 3); in check_erase_testset()
584 root_node = mt->ma_root; in check_erase_testset()
585 erase_check_insert(mt, 2); in check_erase_testset()
587 erase_check_load(mt, 0); in check_erase_testset()
588 check_load(mt, 5016, NULL); in check_erase_testset()
589 erase_check_load(mt, 1); in check_erase_testset()
590 check_load(mt, 5013, NULL); in check_erase_testset()
591 erase_check_load(mt, 2); in check_erase_testset()
592 check_load(mt, 5018, NULL); in check_erase_testset()
593 erase_check_load(mt, 3); in check_erase_testset()
596 erase_check_erase(mt, 2); /* erase 5017 to check append */ in check_erase_testset()
597 erase_check_load(mt, 0); in check_erase_testset()
598 check_load(mt, 5016, NULL); in check_erase_testset()
599 check_load(mt, set[2], NULL); in check_erase_testset()
600 erase_check_erase(mt, 0); /* erase 5015 to check append */ in check_erase_testset()
601 check_load(mt, set[0], NULL); in check_erase_testset()
602 check_load(mt, 5016, NULL); in check_erase_testset()
603 erase_check_insert(mt, 4); /* 1000 < Should not split. */ in check_erase_testset()
604 check_load(mt, set[0], NULL); in check_erase_testset()
605 check_load(mt, 5016, NULL); in check_erase_testset()
606 erase_check_load(mt, 1); in check_erase_testset()
607 check_load(mt, 5013, NULL); in check_erase_testset()
608 check_load(mt, set[2], NULL); in check_erase_testset()
609 check_load(mt, 5018, NULL); in check_erase_testset()
610 erase_check_load(mt, 4); in check_erase_testset()
611 check_load(mt, 999, NULL); in check_erase_testset()
612 check_load(mt, 1001, NULL); in check_erase_testset()
613 erase_check_load(mt, 4); in check_erase_testset()
614 if (mt_in_rcu(mt)) in check_erase_testset()
615 MT_BUG_ON(mt, root_node == mt->ma_root); in check_erase_testset()
617 MT_BUG_ON(mt, root_node != mt->ma_root); in check_erase_testset()
620 MT_BUG_ON(mt, !mte_is_leaf(mt->ma_root)); in check_erase_testset()
624 erase_check_insert(mt, 0); in check_erase_testset()
625 erase_check_insert(mt, 2); in check_erase_testset()
628 erase_check_insert(mt, i); in check_erase_testset()
630 erase_check_load(mt, j); in check_erase_testset()
633 erase_check_erase(mt, 14); /*6015 */ in check_erase_testset()
636 check_load(mt, set[i], NULL); in check_erase_testset()
638 erase_check_load(mt, i); in check_erase_testset()
640 erase_check_erase(mt, 16); /*7002 */ in check_erase_testset()
643 check_load(mt, set[i], NULL); in check_erase_testset()
645 erase_check_load(mt, i); in check_erase_testset()
650 erase_check_erase(mt, 13); /*6012 */ in check_erase_testset()
653 check_load(mt, set[i], NULL); in check_erase_testset()
655 erase_check_load(mt, i); in check_erase_testset()
658 erase_check_erase(mt, 15); /*7003 */ in check_erase_testset()
661 check_load(mt, set[i], NULL); in check_erase_testset()
663 erase_check_load(mt, i); in check_erase_testset()
667 erase_check_erase(mt, 17); /*7008 *should* cause coalesce. */ in check_erase_testset()
670 check_load(mt, set[i], NULL); in check_erase_testset()
672 erase_check_load(mt, i); in check_erase_testset()
675 erase_check_erase(mt, 18); /*7012 */ in check_erase_testset()
678 check_load(mt, set[i], NULL); in check_erase_testset()
680 erase_check_load(mt, i); in check_erase_testset()
684 erase_check_erase(mt, 19); /*7015 */ in check_erase_testset()
687 check_load(mt, set[i], NULL); in check_erase_testset()
689 erase_check_load(mt, i); in check_erase_testset()
692 erase_check_erase(mt, 20); /*8003 */ in check_erase_testset()
695 check_load(mt, set[i], NULL); in check_erase_testset()
697 erase_check_load(mt, i); in check_erase_testset()
700 erase_check_erase(mt, 21); /*8002 */ in check_erase_testset()
703 check_load(mt, set[i], NULL); in check_erase_testset()
705 erase_check_load(mt, i); in check_erase_testset()
709 erase_check_erase(mt, 22); /*8008 */ in check_erase_testset()
712 check_load(mt, set[i], NULL); in check_erase_testset()
714 erase_check_load(mt, i); in check_erase_testset()
717 erase_check_erase(mt, i); in check_erase_testset()
721 check_load(mt, set[i], NULL); in check_erase_testset()
723 erase_check_load(mt, i); in check_erase_testset()
729 erase_check_insert(mt, i); in check_erase_testset()
733 erase_check_erase(mt, i); in check_erase_testset()
736 erase_check_load(mt, j); in check_erase_testset()
738 check_load(mt, set[j], NULL); in check_erase_testset()
743 erase_check_erase(mt, i); in check_erase_testset()
746 erase_check_load(mt, j); in check_erase_testset()
748 check_load(mt, set[j], NULL); in check_erase_testset()
751 erase_check_insert(mt, 8); in check_erase_testset()
752 erase_check_insert(mt, 9); in check_erase_testset()
753 erase_check_erase(mt, 8); in check_erase_testset()
760 #define erase_check_store_range(mt, a, i, ptr) mtree_test_store_range(mt, \ argument
1010 static noinline void __init check_erase2_testset(struct maple_tree *mt, in check_erase2_testset() argument
1019 MA_STATE(mas, mt, 0, 0); in check_erase2_testset()
1026 MA_STATE(mas_start, mt, set[i+1], set[i+1]); in check_erase2_testset()
1027 MA_STATE(mas_end, mt, set[i+2], set[i+2]); in check_erase2_testset()
1054 erase_check_store_range(mt, set, i + 1, value); in check_erase2_testset()
1082 erase_check_store_range(mt, set, i + 1, value); in check_erase2_testset()
1087 check_erase(mt, set[i+1], xa_mk_value(set[i+1])); in check_erase2_testset()
1091 mt_validate(mt); in check_erase2_testset()
1093 MT_BUG_ON(mt, !mt_height(mt)); in check_erase2_testset()
1095 mt_dump(mt, mt_dump_hex); in check_erase2_testset()
1103 mt_for_each(mt, foo, addr, ULONG_MAX) { in check_erase2_testset()
1106 pr_err("mt: %lu -> %p (%d)\n", addr+1, foo, check); in check_erase2_testset()
1116 MT_BUG_ON(mt, check != entry_count); in check_erase2_testset()
1129 MT_BUG_ON(mt, 1); in check_erase2_testset()
1144 mt_validate(mt); in check_erase2_testset()
1147 MT_BUG_ON(mt, check != entry_count); in check_erase2_testset()
1149 MT_BUG_ON(mt, mtree_load(mas.tree, 0) != NULL); in check_erase2_testset()
1155 static noinline void __init check_erase2_sets(struct maple_tree *mt) in check_erase2_sets() argument
33895 * Gap was found: mt 4041162752 gap_end 4041183232 in check_erase2_sets()
33927 MA_STATE(mas, mt, 0, 0); in check_erase2_sets()
33930 check_erase2_testset(mt, set, ARRAY_SIZE(set)); in check_erase2_sets()
33932 mtree_destroy(mt); in check_erase2_sets()
33934 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33935 check_erase2_testset(mt, set2, ARRAY_SIZE(set2)); in check_erase2_sets()
33937 MT_BUG_ON(mt, !!mt_find(mt, &start, 140735933906943UL)); in check_erase2_sets()
33938 mtree_destroy(mt); in check_erase2_sets()
33941 mt_init_flags(mt, 0); in check_erase2_sets()
33942 check_erase2_testset(mt, set3, ARRAY_SIZE(set3)); in check_erase2_sets()
33944 mtree_destroy(mt); in check_erase2_sets()
33946 mt_init_flags(mt, 0); in check_erase2_sets()
33947 check_erase2_testset(mt, set4, ARRAY_SIZE(set4)); in check_erase2_sets()
33955 mtree_destroy(mt); in check_erase2_sets()
33957 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33959 check_erase2_testset(mt, set5, ARRAY_SIZE(set5)); in check_erase2_sets()
33962 mtree_destroy(mt); in check_erase2_sets()
33964 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33965 check_erase2_testset(mt, set6, ARRAY_SIZE(set6)); in check_erase2_sets()
33967 mtree_destroy(mt); in check_erase2_sets()
33969 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33970 check_erase2_testset(mt, set7, ARRAY_SIZE(set7)); in check_erase2_sets()
33972 mtree_destroy(mt); in check_erase2_sets()
33974 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33975 check_erase2_testset(mt, set8, ARRAY_SIZE(set8)); in check_erase2_sets()
33977 mtree_destroy(mt); in check_erase2_sets()
33979 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33980 check_erase2_testset(mt, set9, ARRAY_SIZE(set9)); in check_erase2_sets()
33982 mtree_destroy(mt); in check_erase2_sets()
33984 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33985 check_erase2_testset(mt, set10, ARRAY_SIZE(set10)); in check_erase2_sets()
33987 mtree_destroy(mt); in check_erase2_sets()
33990 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33991 check_erase2_testset(mt, set11, ARRAY_SIZE(set11)); in check_erase2_sets()
33994 MT_BUG_ON(mt, mas.last != 140014592573439); in check_erase2_sets()
33995 mtree_destroy(mt); in check_erase2_sets()
33998 mas.tree = mt; in check_erase2_sets()
34001 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34002 check_erase2_testset(mt, set12, ARRAY_SIZE(set12)); in check_erase2_sets()
34010 mtree_destroy(mt); in check_erase2_sets()
34013 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34014 check_erase2_testset(mt, set13, ARRAY_SIZE(set13)); in check_erase2_sets()
34015 mtree_erase(mt, 140373516443648); in check_erase2_sets()
34019 mtree_destroy(mt); in check_erase2_sets()
34020 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34021 check_erase2_testset(mt, set14, ARRAY_SIZE(set14)); in check_erase2_sets()
34023 mtree_destroy(mt); in check_erase2_sets()
34025 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34026 check_erase2_testset(mt, set15, ARRAY_SIZE(set15)); in check_erase2_sets()
34028 mtree_destroy(mt); in check_erase2_sets()
34033 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34034 check_erase2_testset(mt, set16, ARRAY_SIZE(set16)); in check_erase2_sets()
34037 MT_BUG_ON(mt, mas.last != 139921865547775); in check_erase2_sets()
34039 mtree_destroy(mt); in check_erase2_sets()
34048 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34049 check_erase2_testset(mt, set17, ARRAY_SIZE(set17)); in check_erase2_sets()
34052 MT_BUG_ON(mt, mas.last != 139953197322239); in check_erase2_sets()
34053 /* MT_BUG_ON(mt, mas.index != 139953197318144); */ in check_erase2_sets()
34055 mtree_destroy(mt); in check_erase2_sets()
34064 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34065 check_erase2_testset(mt, set18, ARRAY_SIZE(set18)); in check_erase2_sets()
34068 MT_BUG_ON(mt, mas.last != 140222968475647); in check_erase2_sets()
34069 /*MT_BUG_ON(mt, mas.index != 140222966259712); */ in check_erase2_sets()
34071 mtree_destroy(mt); in check_erase2_sets()
34082 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34083 check_erase2_testset(mt, set19, ARRAY_SIZE(set19)); in check_erase2_sets()
34087 MT_BUG_ON(mt, entry != xa_mk_value(140656779083776)); in check_erase2_sets()
34089 MT_BUG_ON(mt, entry != xa_mk_value(140656766251008)); in check_erase2_sets()
34091 mtree_destroy(mt); in check_erase2_sets()
34098 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34099 check_erase2_testset(mt, set20, ARRAY_SIZE(set20)); in check_erase2_sets()
34101 check_load(mt, 94849009414144, NULL); in check_erase2_sets()
34103 mtree_destroy(mt); in check_erase2_sets()
34106 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34107 check_erase2_testset(mt, set21, ARRAY_SIZE(set21)); in check_erase2_sets()
34109 mt_validate(mt); in check_erase2_sets()
34111 mtree_destroy(mt); in check_erase2_sets()
34114 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34115 check_erase2_testset(mt, set22, ARRAY_SIZE(set22)); in check_erase2_sets()
34117 mt_validate(mt); in check_erase2_sets()
34118 ptr = mtree_load(mt, 140551363362816); in check_erase2_sets()
34119 MT_BUG_ON(mt, ptr == mtree_load(mt, 140551363420159)); in check_erase2_sets()
34121 mtree_destroy(mt); in check_erase2_sets()
34124 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34125 check_erase2_testset(mt, set23, ARRAY_SIZE(set23)); in check_erase2_sets()
34128 mt_validate(mt); in check_erase2_sets()
34129 mtree_destroy(mt); in check_erase2_sets()
34133 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34134 check_erase2_testset(mt, set24, ARRAY_SIZE(set24)); in check_erase2_sets()
34137 mt_validate(mt); in check_erase2_sets()
34138 mtree_destroy(mt); in check_erase2_sets()
34141 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34142 check_erase2_testset(mt, set25, ARRAY_SIZE(set25)); in check_erase2_sets()
34145 mt_validate(mt); in check_erase2_sets()
34146 mtree_destroy(mt); in check_erase2_sets()
34151 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34152 check_erase2_testset(mt, set26, ARRAY_SIZE(set26)); in check_erase2_sets()
34155 MT_BUG_ON(mt, mas.last != 140109040959487); in check_erase2_sets()
34157 mt_validate(mt); in check_erase2_sets()
34158 mtree_destroy(mt); in check_erase2_sets()
34163 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34164 check_erase2_testset(mt, set27, ARRAY_SIZE(set27)); in check_erase2_sets()
34166 MT_BUG_ON(mt, NULL != mtree_load(mt, 140415537422336)); in check_erase2_sets()
34168 mt_validate(mt); in check_erase2_sets()
34169 mtree_destroy(mt); in check_erase2_sets()
34173 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34174 check_erase2_testset(mt, set28, ARRAY_SIZE(set28)); in check_erase2_sets()
34179 MT_BUG_ON(mt, mas.index != 139918401601536); in check_erase2_sets()
34181 mt_validate(mt); in check_erase2_sets()
34182 mtree_destroy(mt); in check_erase2_sets()
34189 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34190 check_erase2_testset(mt, set29, ARRAY_SIZE(set29)); in check_erase2_sets()
34193 mt_validate(mt); in check_erase2_sets()
34194 mtree_destroy(mt); in check_erase2_sets()
34202 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34203 check_erase2_testset(mt, set30, ARRAY_SIZE(set30)); in check_erase2_sets()
34206 mt_validate(mt); in check_erase2_sets()
34207 mtree_destroy(mt); in check_erase2_sets()
34215 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34216 check_erase2_testset(mt, set31, ARRAY_SIZE(set31)); in check_erase2_sets()
34219 mt_validate(mt); in check_erase2_sets()
34220 mtree_destroy(mt); in check_erase2_sets()
34224 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34225 check_erase2_testset(mt, set32, ARRAY_SIZE(set32)); in check_erase2_sets()
34228 mt_validate(mt); in check_erase2_sets()
34229 mtree_destroy(mt); in check_erase2_sets()
34233 * mt 140582827569152 gap_end 140582869532672 in check_erase2_sets()
34244 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34245 check_erase2_testset(mt, set33, ARRAY_SIZE(set33)); in check_erase2_sets()
34248 MT_BUG_ON(mt, mas.last != 140583003750399); in check_erase2_sets()
34250 mt_validate(mt); in check_erase2_sets()
34251 mtree_destroy(mt); in check_erase2_sets()
34259 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34260 check_erase2_testset(mt, set34, ARRAY_SIZE(set34)); in check_erase2_sets()
34263 mt_validate(mt); in check_erase2_sets()
34264 mtree_destroy(mt); in check_erase2_sets()
34269 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34270 check_erase2_testset(mt, set35, ARRAY_SIZE(set35)); in check_erase2_sets()
34273 mt_validate(mt); in check_erase2_sets()
34274 mtree_destroy(mt); in check_erase2_sets()
34279 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34280 check_erase2_testset(mt, set36, ARRAY_SIZE(set36)); in check_erase2_sets()
34283 mt_validate(mt); in check_erase2_sets()
34284 mtree_destroy(mt); in check_erase2_sets()
34287 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34288 check_erase2_testset(mt, set37, ARRAY_SIZE(set37)); in check_erase2_sets()
34290 MT_BUG_ON(mt, NULL != mtree_load(mt, 94637033459712)); in check_erase2_sets()
34291 mt_validate(mt); in check_erase2_sets()
34292 mtree_destroy(mt); in check_erase2_sets()
34295 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34296 check_erase2_testset(mt, set38, ARRAY_SIZE(set38)); in check_erase2_sets()
34298 MT_BUG_ON(mt, NULL != mtree_load(mt, 94637033459712)); in check_erase2_sets()
34299 mt_validate(mt); in check_erase2_sets()
34300 mtree_destroy(mt); in check_erase2_sets()
34303 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34304 check_erase2_testset(mt, set39, ARRAY_SIZE(set39)); in check_erase2_sets()
34306 mt_validate(mt); in check_erase2_sets()
34307 mtree_destroy(mt); in check_erase2_sets()
34310 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34311 check_erase2_testset(mt, set40, ARRAY_SIZE(set40)); in check_erase2_sets()
34313 mt_validate(mt); in check_erase2_sets()
34314 mtree_destroy(mt); in check_erase2_sets()
34317 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34318 check_erase2_testset(mt, set41, ARRAY_SIZE(set41)); in check_erase2_sets()
34320 mt_validate(mt); in check_erase2_sets()
34321 mtree_destroy(mt); in check_erase2_sets()
34326 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34327 check_erase2_testset(mt, set42, ARRAY_SIZE(set42)); in check_erase2_sets()
34330 MT_BUG_ON(mt, mas.last != 4041211903); in check_erase2_sets()
34332 mt_validate(mt); in check_erase2_sets()
34333 mtree_destroy(mt); in check_erase2_sets()
34338 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34339 check_erase2_testset(mt, set43, ARRAY_SIZE(set43)); in check_erase2_sets()
34342 mt_validate(mt); in check_erase2_sets()
34343 mtree_destroy(mt); in check_erase2_sets()
34382 MA_STATE(mas, test->mt, 0, 0); in rcu_reader_fwd()
34492 MA_STATE(mas, test->mt, 0, 0); in rcu_reader_rev()
34554 mt_dump(test->mt, mt_dump_dec); in rcu_reader_rev()
34617 static void rcu_stress_rev(struct maple_tree *mt, struct rcu_test_struct2 *test, in rcu_stress_rev() argument
34637 mtree_store_range(mt, start, end, in rcu_stress_rev()
34647 mtree_store_range(mt, start, end, in rcu_stress_rev()
34658 mtree_store_range(mt, start, end, NULL, GFP_KERNEL); in rcu_stress_rev()
34665 mtree_store_range(mt, start, end, in rcu_stress_rev()
34676 static void rcu_stress_fwd(struct maple_tree *mt, struct rcu_test_struct2 *test, in rcu_stress_fwd() argument
34694 mtree_store_range(mt, start, end, in rcu_stress_fwd()
34704 mtree_store_range(mt, start, end, in rcu_stress_fwd()
34715 mtree_store_range(mt, start, end, NULL, GFP_KERNEL); in rcu_stress_fwd()
34722 mtree_store_range(mt, start, end, in rcu_stress_fwd()
34744 static void rcu_stress(struct maple_tree *mt, bool forward) in rcu_stress() argument
34754 test.mt = mt; in rcu_stress()
34766 mtree_store_range(mt, seed, r, in rcu_stress()
34798 mtree_store_range(mt, test.index[add], test.last[add], in rcu_stress()
34802 mt_set_in_rcu(mt); in rcu_stress()
34808 rcu_stress_fwd(mt, &test, count, test_reader); in rcu_stress()
34810 rcu_stress_rev(mt, &test, count, test_reader); in rcu_stress()
34816 mt_validate(mt); in rcu_stress()
34821 struct maple_tree *mt; /* the maple tree */ member
34900 entry = mtree_load(test->mt, test->index); in rcu_val()
34901 MT_BUG_ON(test->mt, eval_rcu_entry(test, entry, &update_2, in rcu_val()
34921 MA_STATE(mas, test->mt, test->range_start, test->range_start); in rcu_loop()
34942 MT_BUG_ON(test->mt, entry != expected); in rcu_loop()
34950 MT_BUG_ON(test->mt, eval_rcu_entry(test, entry, in rcu_loop()
34963 void run_check_rcu(struct maple_tree *mt, struct rcu_test_struct *vals) in run_check_rcu() argument
34970 mt_set_in_rcu(mt); in run_check_rcu()
34971 MT_BUG_ON(mt, !mt_in_rcu(mt)); in run_check_rcu()
34986 mtree_store_range(mt, vals->index, vals->last, vals->entry2, in run_check_rcu()
34992 MT_BUG_ON(mt, !vals->seen_entry2); in run_check_rcu()
34998 MA_STATE(mas, test->mt, test->index, test->index); in rcu_slot_store_reader()
35015 static noinline void run_check_rcu_slot_store(struct maple_tree *mt) in run_check_rcu_slot_store() argument
35020 struct rcu_test_struct3 test = {.stop = false, .mt = mt}; in run_check_rcu_slot_store()
35028 mtree_store_range(mt, i * len, i * len + len - 1, in run_check_rcu_slot_store()
35032 mt_set_in_rcu(mt); in run_check_rcu_slot_store()
35033 MT_BUG_ON(mt, !mt_in_rcu(mt)); in run_check_rcu_slot_store()
35047 mtree_store_range(mt, --start, ++end, xa_mk_value(100), in run_check_rcu_slot_store()
35056 mt_validate(mt); in run_check_rcu_slot_store()
35060 void run_check_rcu_slowread(struct maple_tree *mt, struct rcu_test_struct *vals) in run_check_rcu_slowread() argument
35068 mt_set_in_rcu(mt); in run_check_rcu_slowread()
35069 MT_BUG_ON(mt, !mt_in_rcu(mt)); in run_check_rcu_slowread()
35086 mtree_store(mt, index, in run_check_rcu_slowread()
35097 MT_BUG_ON(mt, !vals->seen_entry2); in run_check_rcu_slowread()
35098 MT_BUG_ON(mt, !vals->seen_entry3); in run_check_rcu_slowread()
35099 MT_BUG_ON(mt, !vals->seen_both); in run_check_rcu_slowread()
35101 static noinline void __init check_rcu_simulated(struct maple_tree *mt) in check_rcu_simulated() argument
35107 MA_STATE(mas_writer, mt, 0, 0); in check_rcu_simulated()
35108 MA_STATE(mas_reader, mt, target, target); in check_rcu_simulated()
35112 mt_set_in_rcu(mt); in check_rcu_simulated()
35124 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35128 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val)); in check_rcu_simulated()
35141 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35145 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val)); in check_rcu_simulated()
35158 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35162 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35175 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35179 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val)); in check_rcu_simulated()
35191 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35195 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val)); in check_rcu_simulated()
35207 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35211 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val)); in check_rcu_simulated()
35232 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35237 MT_BUG_ON(mt, mas_next(&mas_reader, ULONG_MAX) != xa_mk_value(val)); in check_rcu_simulated()
35251 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35256 MT_BUG_ON(mt, mas_prev(&mas_reader, 0) != xa_mk_value(val)); in check_rcu_simulated()
35262 static noinline void __init check_rcu_threaded(struct maple_tree *mt) in check_rcu_threaded() argument
35272 mtree_store_range(mt, i*10, i*10 + 5, in check_rcu_threaded()
35276 vals.mt = mt; in check_rcu_threaded()
35287 run_check_rcu(mt, &vals); in check_rcu_threaded()
35288 mtree_destroy(mt); in check_rcu_threaded()
35290 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_rcu_threaded()
35292 mtree_store_range(mt, i*10, i*10 + 5, in check_rcu_threaded()
35299 vals.mt = mt; in check_rcu_threaded()
35308 run_check_rcu(mt, &vals); in check_rcu_threaded()
35309 mtree_destroy(mt); in check_rcu_threaded()
35312 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_rcu_threaded()
35313 run_check_rcu_slot_store(mt); in check_rcu_threaded()
35314 mtree_destroy(mt); in check_rcu_threaded()
35317 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_rcu_threaded()
35318 rcu_stress(mt, true); in check_rcu_threaded()
35319 mtree_destroy(mt); in check_rcu_threaded()
35322 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_rcu_threaded()
35323 rcu_stress(mt, false); in check_rcu_threaded()
35324 mtree_destroy(mt); in check_rcu_threaded()
35327 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_rcu_threaded()
35329 mtree_store_range(mt, i*10, i*10 + 5, in check_rcu_threaded()
35336 vals.mt = mt; in check_rcu_threaded()
35357 run_check_rcu_slowread(mt, &vals); in check_rcu_threaded()
35411 static void check_dfs_preorder(struct maple_tree *mt) in check_dfs_preorder() argument
35415 MA_STATE(mas, mt, 0, 0); in check_dfs_preorder()
35422 check_seq(mt, max, false); in check_dfs_preorder()
35427 MT_BUG_ON(mt, count != e); in check_dfs_preorder()
35428 mtree_destroy(mt); in check_dfs_preorder()
35430 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_dfs_preorder()
35436 check_seq(mt, max, false); in check_dfs_preorder()
35442 MT_BUG_ON(mt, count != e); in check_dfs_preorder()
35443 mtree_destroy(mt); in check_dfs_preorder()
35445 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_dfs_preorder()
35448 check_rev_seq(mt, max, false); in check_dfs_preorder()
35454 MT_BUG_ON(mt, count != e); in check_dfs_preorder()
35455 mtree_destroy(mt); in check_dfs_preorder()
35457 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_dfs_preorder()
35465 MT_BUG_ON(mt, mas_is_err(&mas)); in check_dfs_preorder()
35479 static noinline void __init check_prealloc(struct maple_tree *mt) in check_prealloc() argument
35486 MA_STATE(mas, mt, 10, 20); in check_prealloc()
35490 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_prealloc()
35494 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35497 MT_BUG_ON(mt, allocated == 0); in check_prealloc()
35498 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35501 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35503 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35506 MT_BUG_ON(mt, allocated == 0); in check_prealloc()
35507 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35508 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35511 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35514 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35517 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35519 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); in check_prealloc()
35522 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35525 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35527 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35530 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35532 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); in check_prealloc()
35533 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35536 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35540 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35543 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35545 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); in check_prealloc()
35547 MT_BUG_ON(mt, mas_allocated(&mas) != allocated); in check_prealloc()
35548 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35551 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35553 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35556 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35558 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35562 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35564 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35566 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35569 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35572 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35574 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35578 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35581 MT_BUG_ON(mt, allocated != 1 + height * 2); in check_prealloc()
35583 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35587 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0); in check_prealloc()
35590 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35595 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35598 MT_BUG_ON(mt, allocated == 0); in check_prealloc()
35599 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35601 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35604 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0); in check_prealloc()
35607 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35612 static noinline void __init check_spanning_write(struct maple_tree *mt) in check_spanning_write() argument
35615 MA_STATE(mas, mt, 1200, 2380); in check_spanning_write()
35618 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35620 mtree_lock(mt); in check_spanning_write()
35623 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35624 mtree_unlock(mt); in check_spanning_write()
35625 mtree_destroy(mt); in check_spanning_write()
35628 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35630 mtree_lock(mt); in check_spanning_write()
35634 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35635 mtree_unlock(mt); in check_spanning_write()
35636 mt_validate(mt); in check_spanning_write()
35637 mtree_destroy(mt); in check_spanning_write()
35640 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35642 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35645 mtree_lock(mt); in check_spanning_write()
35648 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35649 mtree_unlock(mt); in check_spanning_write()
35650 mtree_destroy(mt); in check_spanning_write()
35653 mt_init_flags(mt, 0); in check_spanning_write()
35655 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35658 mtree_lock(mt); in check_spanning_write()
35661 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35662 mtree_unlock(mt); in check_spanning_write()
35663 mtree_destroy(mt); in check_spanning_write()
35666 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35668 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35671 mtree_lock(mt); in check_spanning_write()
35674 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35675 mtree_unlock(mt); in check_spanning_write()
35676 mtree_destroy(mt); in check_spanning_write()
35679 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35681 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35684 mtree_lock(mt); in check_spanning_write()
35687 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35688 mtree_unlock(mt); in check_spanning_write()
35689 mtree_destroy(mt); in check_spanning_write()
35692 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35694 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35697 mtree_lock(mt); in check_spanning_write()
35700 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35701 mtree_unlock(mt); in check_spanning_write()
35702 mtree_destroy(mt); in check_spanning_write()
35708 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35710 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35713 mtree_lock(mt); in check_spanning_write()
35716 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35717 mtree_unlock(mt); in check_spanning_write()
35718 mtree_destroy(mt); in check_spanning_write()
35724 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35726 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35728 mtree_lock(mt); in check_spanning_write()
35731 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35732 mtree_unlock(mt); in check_spanning_write()
35733 mtree_destroy(mt); in check_spanning_write()
35736 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35738 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35739 mtree_lock(mt); in check_spanning_write()
35750 MT_BUG_ON(mt, (mas_data_end(&mas)) != mt_slot_count(mas.node) - 1); in check_spanning_write()
35753 mtree_unlock(mt); in check_spanning_write()
35754 mtree_destroy(mt); in check_spanning_write()
35757 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35759 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35761 mtree_lock(mt); in check_spanning_write()
35764 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35765 mtree_unlock(mt); in check_spanning_write()
35766 mtree_destroy(mt); in check_spanning_write()
35768 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35770 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35772 mtree_lock(mt); in check_spanning_write()
35775 mtree_unlock(mt); in check_spanning_write()
35780 static noinline void __init check_null_expand(struct maple_tree *mt) in check_null_expand() argument
35784 MA_STATE(mas, mt, 959, 959); in check_null_expand()
35787 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_null_expand()
35794 MT_BUG_ON(mt, mtree_load(mt, 963) != NULL); in check_null_expand()
35795 MT_BUG_ON(mt, data_end != mas_data_end(&mas)); in check_null_expand()
35803 MT_BUG_ON(mt, mtree_load(mt, 884) != NULL); in check_null_expand()
35804 MT_BUG_ON(mt, mtree_load(mt, 889) != NULL); in check_null_expand()
35806 MT_BUG_ON(mt, data_end != mas_data_end(&mas)); in check_null_expand()
35815 MT_BUG_ON(mt, mtree_load(mt, 899) != NULL); in check_null_expand()
35816 MT_BUG_ON(mt, mtree_load(mt, 900) != NULL); in check_null_expand()
35817 MT_BUG_ON(mt, mtree_load(mt, 905) != NULL); in check_null_expand()
35818 MT_BUG_ON(mt, mtree_load(mt, 906) != NULL); in check_null_expand()
35820 MT_BUG_ON(mt, data_end - 2 != mas_data_end(&mas)); in check_null_expand()
35829 MT_BUG_ON(mt, mtree_load(mt, 809) != NULL); in check_null_expand()
35830 MT_BUG_ON(mt, mtree_load(mt, 810) != NULL); in check_null_expand()
35831 MT_BUG_ON(mt, mtree_load(mt, 825) != NULL); in check_null_expand()
35832 MT_BUG_ON(mt, mtree_load(mt, 826) != NULL); in check_null_expand()
35834 MT_BUG_ON(mt, data_end - 4 != mas_data_end(&mas)); in check_null_expand()
35841 static noinline void __init check_nomem(struct maple_tree *mt) in check_nomem() argument
35843 MA_STATE(ms, mt, 1, 1); in check_nomem()
35845 MT_BUG_ON(mt, !mtree_empty(mt)); in check_nomem()
35850 MT_BUG_ON(mt, mtree_insert(mt, 1, &ms, GFP_ATOMIC) != -ENOMEM); in check_nomem()
35852 MT_BUG_ON(mt, mtree_insert(mt, 0, &ms, GFP_ATOMIC) != 0); in check_nomem()
35862 mtree_lock(mt); in check_nomem()
35864 MT_BUG_ON(mt, ms.node != MA_ERROR(-ENOMEM)); in check_nomem()
35866 MT_BUG_ON(mt, ms.status != ma_start); in check_nomem()
35867 mtree_unlock(mt); in check_nomem()
35868 MT_BUG_ON(mt, mtree_insert(mt, 2, mt, GFP_KERNEL) != 0); in check_nomem()
35869 mtree_lock(mt); in check_nomem()
35872 mtree_unlock(mt); in check_nomem()
35874 mtree_destroy(mt); in check_nomem()
35877 static noinline void __init check_locky(struct maple_tree *mt) in check_locky() argument
35879 MA_STATE(ms, mt, 2, 2); in check_locky()
35880 MA_STATE(reader, mt, 2, 2); in check_locky()
35883 mt_set_in_rcu(mt); in check_locky()
35889 mt_clear_in_rcu(mt); in check_locky()
36038 * @mt: The tree to build.
36046 static __init int build_full_tree(struct maple_tree *mt, unsigned int flags, in build_full_tree() argument
36049 MA_STATE(mas, mt, 0, 0); in build_full_tree()
36054 mt_init_flags(mt, flags); in build_full_tree()
36055 mtree_insert_range(mt, 0, ULONG_MAX, xa_mk_value(5), GFP_KERNEL); in build_full_tree()
36057 mtree_lock(mt); in build_full_tree()
36061 if (mt_height(mt) < height) { in build_full_tree()
36092 mtree_unlock(mt); in build_full_tree()
36094 MT_BUG_ON(mt, mt_height(mt) != height); in build_full_tree()
36095 /* pr_info("height:%u number of elements:%d\n", mt_height(mt), cnt); */ in build_full_tree()
36099 static noinline void __init check_mtree_dup(struct maple_tree *mt) in check_mtree_dup() argument
36106 mt_init_flags(mt, 0); in check_mtree_dup()
36107 mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL); in check_mtree_dup()
36108 ret = mtree_dup(mt, &new, GFP_KERNEL); in check_mtree_dup()
36111 if (compare_tree(mt, &new)) in check_mtree_dup()
36114 mtree_destroy(mt); in check_mtree_dup()
36118 mt_init_flags(mt, 0); in check_mtree_dup()
36120 ret = mtree_dup(mt, &new, GFP_KERNEL); in check_mtree_dup()
36122 mtree_destroy(mt); in check_mtree_dup()
36126 mt_init_flags(mt, 0); in check_mtree_dup()
36129 ret = mtree_dup(mt, &new, GFP_KERNEL); in check_mtree_dup()
36131 mtree_destroy(mt); in check_mtree_dup()
36136 ret = build_full_tree(mt, 0, i); in check_mtree_dup()
36137 MT_BUG_ON(mt, ret); in check_mtree_dup()
36140 ret = mtree_dup(mt, &new, GFP_KERNEL); in check_mtree_dup()
36143 if (compare_tree(mt, &new)) in check_mtree_dup()
36146 mtree_destroy(mt); in check_mtree_dup()
36151 ret = build_full_tree(mt, MT_FLAGS_ALLOC_RANGE, i); in check_mtree_dup()
36152 MT_BUG_ON(mt, ret); in check_mtree_dup()
36155 ret = mtree_dup(mt, &new, GFP_KERNEL); in check_mtree_dup()
36158 if (compare_tree(mt, &new)) in check_mtree_dup()
36161 mtree_destroy(mt); in check_mtree_dup()
36168 mt_init_flags(mt, 0); in check_mtree_dup()
36171 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_mtree_dup()
36176 mtree_store_range(mt, j * 10, j * 10 + 5, in check_mtree_dup()
36180 ret = mtree_dup(mt, &new, GFP_KERNEL); in check_mtree_dup()
36183 if (compare_tree(mt, &new)) in check_mtree_dup()
36186 mtree_destroy(mt); in check_mtree_dup()
36191 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_mtree_dup()
36193 mtree_store_range(mt, j * 10, j * 10 + 5, in check_mtree_dup()
36200 ret = mtree_dup(mt, &new, GFP_NOWAIT); in check_mtree_dup()
36203 mtree_destroy(mt); in check_mtree_dup()
36209 mt_init_flags(mt, 0); in check_mtree_dup()
36212 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_mtree_dup()
36217 mtree_store_range(mt, j * 10, j * 10 + 5, in check_mtree_dup()
36228 ret = mtree_dup(mt, &new, GFP_NOWAIT); in check_mtree_dup()
36233 mtree_destroy(mt); in check_mtree_dup()
36238 if (compare_tree(mt, &new)) in check_mtree_dup()
36241 mtree_destroy(mt); in check_mtree_dup()
36254 struct maple_tree *mt = (struct maple_tree *)maple_tree; in writer2() local
36255 MA_STATE(mas, mt, 6, 10); in writer2()
36265 * @mt: The tree to build.
36272 static void check_nomem_writer_race(struct maple_tree *mt) in check_nomem_writer_race() argument
36274 MA_STATE(mas, mt, 0, 5); in check_nomem_writer_race()
36278 mtree_store_range(mt, 0, 5, xa_mk_value(0xA), GFP_KERNEL); in check_nomem_writer_race()
36279 mtree_store_range(mt, 6, 10, NULL, GFP_KERNEL); in check_nomem_writer_race()
36280 mtree_store_range(mt, 11, 15, xa_mk_value(0xB), GFP_KERNEL); in check_nomem_writer_race()
36283 mt_set_private(mt); in check_nomem_writer_race()
36286 mtree_lock(mt); in check_nomem_writer_race()
36291 check_load(mt, 6, xa_mk_value(0xC)); in check_nomem_writer_race()
36292 mtree_unlock(mt); in check_nomem_writer_race()
36295 mtree_store_range(mt, 0, 5, xa_mk_value(0xA), GFP_KERNEL); in check_nomem_writer_race()
36296 mtree_store_range(mt, 6, 10, NULL, GFP_KERNEL); in check_nomem_writer_race()
36299 mtree_lock(mt); in check_nomem_writer_race()
36303 check_load(mt, 6, xa_mk_value(0xC)); in check_nomem_writer_race()
36307 mtree_unlock(mt); in check_nomem_writer_race()
36314 static inline int check_vma_modification(struct maple_tree *mt) in check_vma_modification() argument
36316 MA_STATE(mas, mt, 0, 0); in check_vma_modification()
36318 mtree_lock(mt); in check_vma_modification()
36335 mt_dump(mt, mt_dump_hex); in check_vma_modification()
36338 mtree_unlock(mt); in check_vma_modification()
36346 static inline void check_bulk_rebalance(struct maple_tree *mt) in check_bulk_rebalance() argument
36348 MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX); in check_bulk_rebalance()
36351 build_full_tree(mt, 0, 2); in check_bulk_rebalance()
36358 MT_BUG_ON(mt, mas.store_type == wr_rebalance); in check_bulk_rebalance()
36460 enum maple_type mt = mte_node_type(mas->node); in get_last_index() local
36461 unsigned long *pivots = ma_pivots(node, mt); in get_last_index()