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()
465 mtree_unlock(mt); in check_new_node()
471 static noinline void __init check_erase(struct maple_tree *mt, unsigned long index, in check_erase() argument
474 MT_BUG_ON(mt, mtree_test_erase(mt, index) != ptr); in check_erase()
477 #define erase_check_load(mt, i) check_load(mt, set[i], entry[i%2]) argument
478 #define erase_check_insert(mt, i) check_insert(mt, set[i], entry[i%2]) argument
479 #define erase_check_erase(mt, i) check_erase(mt, set[i], entry[i%2]) argument
481 static noinline void __init check_erase_testset(struct maple_tree *mt) in check_erase_testset() argument
499 void *entry[2] = { ptr, mt }; in check_erase_testset()
504 mt_set_in_rcu(mt); in check_erase_testset()
506 erase_check_insert(mt, i); in check_erase_testset()
508 erase_check_load(mt, i); in check_erase_testset()
511 erase_check_erase(mt, 1); in check_erase_testset()
512 erase_check_load(mt, 0); in check_erase_testset()
513 check_load(mt, set[1], NULL); in check_erase_testset()
515 erase_check_load(mt, i); in check_erase_testset()
518 erase_check_erase(mt, 2); in check_erase_testset()
519 erase_check_load(mt, 0); in check_erase_testset()
520 check_load(mt, set[1], NULL); in check_erase_testset()
521 check_load(mt, set[2], NULL); in check_erase_testset()
523 erase_check_insert(mt, 1); in check_erase_testset()
524 erase_check_insert(mt, 2); in check_erase_testset()
527 erase_check_load(mt, i); in check_erase_testset()
530 erase_check_load(mt, 3); in check_erase_testset()
531 erase_check_erase(mt, 1); in check_erase_testset()
532 erase_check_load(mt, 0); in check_erase_testset()
533 check_load(mt, set[1], NULL); in check_erase_testset()
535 erase_check_load(mt, i); in check_erase_testset()
541 root_node = mt->ma_root; in check_erase_testset()
542 erase_check_insert(mt, 1); in check_erase_testset()
544 erase_check_load(mt, 0); in check_erase_testset()
545 check_load(mt, 5016, NULL); in check_erase_testset()
546 erase_check_load(mt, 1); in check_erase_testset()
547 check_load(mt, 5013, NULL); in check_erase_testset()
548 erase_check_load(mt, 2); in check_erase_testset()
549 check_load(mt, 5018, NULL); in check_erase_testset()
550 erase_check_load(mt, 3); in check_erase_testset()
552 erase_check_erase(mt, 2); /* erase 5017 to check append */ in check_erase_testset()
553 erase_check_load(mt, 0); in check_erase_testset()
554 check_load(mt, 5016, NULL); in check_erase_testset()
555 erase_check_load(mt, 1); in check_erase_testset()
556 check_load(mt, 5013, NULL); in check_erase_testset()
557 check_load(mt, set[2], NULL); in check_erase_testset()
558 check_load(mt, 5018, NULL); in check_erase_testset()
560 erase_check_load(mt, 3); in check_erase_testset()
562 root_node = mt->ma_root; in check_erase_testset()
563 erase_check_insert(mt, 2); in check_erase_testset()
565 erase_check_load(mt, 0); in check_erase_testset()
566 check_load(mt, 5016, NULL); in check_erase_testset()
567 erase_check_load(mt, 1); in check_erase_testset()
568 check_load(mt, 5013, NULL); in check_erase_testset()
569 erase_check_load(mt, 2); in check_erase_testset()
570 check_load(mt, 5018, NULL); in check_erase_testset()
571 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 check_load(mt, set[2], NULL); in check_erase_testset()
578 erase_check_erase(mt, 0); /* erase 5015 to check append */ in check_erase_testset()
579 check_load(mt, set[0], NULL); in check_erase_testset()
580 check_load(mt, 5016, NULL); in check_erase_testset()
581 erase_check_insert(mt, 4); /* 1000 < Should not split. */ in check_erase_testset()
582 check_load(mt, set[0], NULL); in check_erase_testset()
583 check_load(mt, 5016, NULL); in check_erase_testset()
584 erase_check_load(mt, 1); in check_erase_testset()
585 check_load(mt, 5013, NULL); in check_erase_testset()
586 check_load(mt, set[2], NULL); in check_erase_testset()
587 check_load(mt, 5018, NULL); in check_erase_testset()
588 erase_check_load(mt, 4); in check_erase_testset()
589 check_load(mt, 999, NULL); in check_erase_testset()
590 check_load(mt, 1001, NULL); in check_erase_testset()
591 erase_check_load(mt, 4); in check_erase_testset()
592 if (mt_in_rcu(mt)) in check_erase_testset()
593 MT_BUG_ON(mt, root_node == mt->ma_root); in check_erase_testset()
595 MT_BUG_ON(mt, root_node != mt->ma_root); in check_erase_testset()
598 MT_BUG_ON(mt, !mte_is_leaf(mt->ma_root)); in check_erase_testset()
602 erase_check_insert(mt, 0); in check_erase_testset()
603 erase_check_insert(mt, 2); in check_erase_testset()
606 erase_check_insert(mt, i); in check_erase_testset()
608 erase_check_load(mt, j); in check_erase_testset()
611 erase_check_erase(mt, 14); /*6015 */ in check_erase_testset()
614 check_load(mt, set[i], NULL); in check_erase_testset()
616 erase_check_load(mt, i); in check_erase_testset()
618 erase_check_erase(mt, 16); /*7002 */ in check_erase_testset()
621 check_load(mt, set[i], NULL); in check_erase_testset()
623 erase_check_load(mt, i); in check_erase_testset()
628 erase_check_erase(mt, 13); /*6012 */ in check_erase_testset()
631 check_load(mt, set[i], NULL); in check_erase_testset()
633 erase_check_load(mt, i); in check_erase_testset()
636 erase_check_erase(mt, 15); /*7003 */ in check_erase_testset()
639 check_load(mt, set[i], NULL); in check_erase_testset()
641 erase_check_load(mt, i); in check_erase_testset()
645 erase_check_erase(mt, 17); /*7008 *should* cause coalesce. */ in check_erase_testset()
648 check_load(mt, set[i], NULL); in check_erase_testset()
650 erase_check_load(mt, i); in check_erase_testset()
653 erase_check_erase(mt, 18); /*7012 */ in check_erase_testset()
656 check_load(mt, set[i], NULL); in check_erase_testset()
658 erase_check_load(mt, i); in check_erase_testset()
662 erase_check_erase(mt, 19); /*7015 */ in check_erase_testset()
665 check_load(mt, set[i], NULL); in check_erase_testset()
667 erase_check_load(mt, i); in check_erase_testset()
670 erase_check_erase(mt, 20); /*8003 */ in check_erase_testset()
673 check_load(mt, set[i], NULL); in check_erase_testset()
675 erase_check_load(mt, i); in check_erase_testset()
678 erase_check_erase(mt, 21); /*8002 */ in check_erase_testset()
681 check_load(mt, set[i], NULL); in check_erase_testset()
683 erase_check_load(mt, i); in check_erase_testset()
687 erase_check_erase(mt, 22); /*8008 */ in check_erase_testset()
690 check_load(mt, set[i], NULL); in check_erase_testset()
692 erase_check_load(mt, i); in check_erase_testset()
695 erase_check_erase(mt, i); in check_erase_testset()
699 check_load(mt, set[i], NULL); in check_erase_testset()
701 erase_check_load(mt, i); in check_erase_testset()
707 erase_check_insert(mt, i); in check_erase_testset()
711 erase_check_erase(mt, i); in check_erase_testset()
714 erase_check_load(mt, j); in check_erase_testset()
716 check_load(mt, set[j], NULL); in check_erase_testset()
721 erase_check_erase(mt, i); in check_erase_testset()
724 erase_check_load(mt, j); in check_erase_testset()
726 check_load(mt, set[j], NULL); in check_erase_testset()
729 erase_check_insert(mt, 8); in check_erase_testset()
730 erase_check_insert(mt, 9); in check_erase_testset()
731 erase_check_erase(mt, 8); in check_erase_testset()
738 #define erase_check_store_range(mt, a, i, ptr) mtree_test_store_range(mt, \ argument
988 static noinline void __init check_erase2_testset(struct maple_tree *mt, in check_erase2_testset() argument
997 MA_STATE(mas, mt, 0, 0); in check_erase2_testset()
1004 MA_STATE(mas_start, mt, set[i+1], set[i+1]); in check_erase2_testset()
1005 MA_STATE(mas_end, mt, set[i+2], set[i+2]); in check_erase2_testset()
1032 erase_check_store_range(mt, set, i + 1, value); in check_erase2_testset()
1060 erase_check_store_range(mt, set, i + 1, value); in check_erase2_testset()
1065 check_erase(mt, set[i+1], xa_mk_value(set[i+1])); in check_erase2_testset()
1069 mt_validate(mt); in check_erase2_testset()
1071 MT_BUG_ON(mt, !mt_height(mt)); in check_erase2_testset()
1073 mt_dump(mt, mt_dump_hex); in check_erase2_testset()
1081 mt_for_each(mt, foo, addr, ULONG_MAX) { in check_erase2_testset()
1084 pr_err("mt: %lu -> %p (%d)\n", addr+1, foo, check); in check_erase2_testset()
1094 MT_BUG_ON(mt, check != entry_count); in check_erase2_testset()
1107 MT_BUG_ON(mt, 1); in check_erase2_testset()
1122 mt_validate(mt); in check_erase2_testset()
1125 MT_BUG_ON(mt, check != entry_count); in check_erase2_testset()
1127 MT_BUG_ON(mt, mtree_load(mas.tree, 0) != NULL); in check_erase2_testset()
1133 static noinline void __init check_erase2_sets(struct maple_tree *mt) in check_erase2_sets() argument
33873 * Gap was found: mt 4041162752 gap_end 4041183232 in check_erase2_sets()
33905 MA_STATE(mas, mt, 0, 0); in check_erase2_sets()
33908 check_erase2_testset(mt, set, ARRAY_SIZE(set)); in check_erase2_sets()
33910 mtree_destroy(mt); in check_erase2_sets()
33912 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33913 check_erase2_testset(mt, set2, ARRAY_SIZE(set2)); in check_erase2_sets()
33915 MT_BUG_ON(mt, !!mt_find(mt, &start, 140735933906943UL)); in check_erase2_sets()
33916 mtree_destroy(mt); in check_erase2_sets()
33919 mt_init_flags(mt, 0); in check_erase2_sets()
33920 check_erase2_testset(mt, set3, ARRAY_SIZE(set3)); in check_erase2_sets()
33922 mtree_destroy(mt); in check_erase2_sets()
33924 mt_init_flags(mt, 0); in check_erase2_sets()
33925 check_erase2_testset(mt, set4, ARRAY_SIZE(set4)); in check_erase2_sets()
33933 mtree_destroy(mt); in check_erase2_sets()
33935 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33937 check_erase2_testset(mt, set5, ARRAY_SIZE(set5)); in check_erase2_sets()
33940 mtree_destroy(mt); in check_erase2_sets()
33942 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33943 check_erase2_testset(mt, set6, ARRAY_SIZE(set6)); in check_erase2_sets()
33945 mtree_destroy(mt); in check_erase2_sets()
33947 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33948 check_erase2_testset(mt, set7, ARRAY_SIZE(set7)); in check_erase2_sets()
33950 mtree_destroy(mt); in check_erase2_sets()
33952 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33953 check_erase2_testset(mt, set8, ARRAY_SIZE(set8)); 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()
33958 check_erase2_testset(mt, set9, ARRAY_SIZE(set9)); in check_erase2_sets()
33960 mtree_destroy(mt); in check_erase2_sets()
33962 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33963 check_erase2_testset(mt, set10, ARRAY_SIZE(set10)); in check_erase2_sets()
33965 mtree_destroy(mt); in check_erase2_sets()
33968 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33969 check_erase2_testset(mt, set11, ARRAY_SIZE(set11)); in check_erase2_sets()
33972 MT_BUG_ON(mt, mas.last != 140014592573439); in check_erase2_sets()
33973 mtree_destroy(mt); in check_erase2_sets()
33976 mas.tree = mt; in check_erase2_sets()
33979 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33980 check_erase2_testset(mt, set12, ARRAY_SIZE(set12)); in check_erase2_sets()
33988 mtree_destroy(mt); in check_erase2_sets()
33991 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33992 check_erase2_testset(mt, set13, ARRAY_SIZE(set13)); in check_erase2_sets()
33993 mtree_erase(mt, 140373516443648); in check_erase2_sets()
33997 mtree_destroy(mt); in check_erase2_sets()
33998 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
33999 check_erase2_testset(mt, set14, ARRAY_SIZE(set14)); in check_erase2_sets()
34001 mtree_destroy(mt); in check_erase2_sets()
34003 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34004 check_erase2_testset(mt, set15, ARRAY_SIZE(set15)); in check_erase2_sets()
34006 mtree_destroy(mt); in check_erase2_sets()
34011 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34012 check_erase2_testset(mt, set16, ARRAY_SIZE(set16)); in check_erase2_sets()
34015 MT_BUG_ON(mt, mas.last != 139921865547775); in check_erase2_sets()
34017 mtree_destroy(mt); in check_erase2_sets()
34026 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34027 check_erase2_testset(mt, set17, ARRAY_SIZE(set17)); in check_erase2_sets()
34030 MT_BUG_ON(mt, mas.last != 139953197322239); in check_erase2_sets()
34031 /* MT_BUG_ON(mt, mas.index != 139953197318144); */ in check_erase2_sets()
34033 mtree_destroy(mt); in check_erase2_sets()
34042 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34043 check_erase2_testset(mt, set18, ARRAY_SIZE(set18)); in check_erase2_sets()
34046 MT_BUG_ON(mt, mas.last != 140222968475647); in check_erase2_sets()
34047 /*MT_BUG_ON(mt, mas.index != 140222966259712); */ in check_erase2_sets()
34049 mtree_destroy(mt); in check_erase2_sets()
34060 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34061 check_erase2_testset(mt, set19, ARRAY_SIZE(set19)); in check_erase2_sets()
34065 MT_BUG_ON(mt, entry != xa_mk_value(140656779083776)); in check_erase2_sets()
34067 MT_BUG_ON(mt, entry != xa_mk_value(140656766251008)); in check_erase2_sets()
34069 mtree_destroy(mt); in check_erase2_sets()
34076 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34077 check_erase2_testset(mt, set20, ARRAY_SIZE(set20)); in check_erase2_sets()
34079 check_load(mt, 94849009414144, NULL); in check_erase2_sets()
34081 mtree_destroy(mt); in check_erase2_sets()
34084 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34085 check_erase2_testset(mt, set21, ARRAY_SIZE(set21)); in check_erase2_sets()
34087 mt_validate(mt); in check_erase2_sets()
34089 mtree_destroy(mt); in check_erase2_sets()
34092 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34093 check_erase2_testset(mt, set22, ARRAY_SIZE(set22)); in check_erase2_sets()
34095 mt_validate(mt); in check_erase2_sets()
34096 ptr = mtree_load(mt, 140551363362816); in check_erase2_sets()
34097 MT_BUG_ON(mt, ptr == mtree_load(mt, 140551363420159)); in check_erase2_sets()
34099 mtree_destroy(mt); in check_erase2_sets()
34102 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34103 check_erase2_testset(mt, set23, ARRAY_SIZE(set23)); in check_erase2_sets()
34106 mt_validate(mt); in check_erase2_sets()
34107 mtree_destroy(mt); in check_erase2_sets()
34111 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34112 check_erase2_testset(mt, set24, ARRAY_SIZE(set24)); in check_erase2_sets()
34115 mt_validate(mt); in check_erase2_sets()
34116 mtree_destroy(mt); in check_erase2_sets()
34119 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34120 check_erase2_testset(mt, set25, ARRAY_SIZE(set25)); in check_erase2_sets()
34123 mt_validate(mt); in check_erase2_sets()
34124 mtree_destroy(mt); in check_erase2_sets()
34129 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34130 check_erase2_testset(mt, set26, ARRAY_SIZE(set26)); in check_erase2_sets()
34133 MT_BUG_ON(mt, mas.last != 140109040959487); in check_erase2_sets()
34135 mt_validate(mt); in check_erase2_sets()
34136 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, set27, ARRAY_SIZE(set27)); in check_erase2_sets()
34144 MT_BUG_ON(mt, NULL != mtree_load(mt, 140415537422336)); in check_erase2_sets()
34146 mt_validate(mt); in check_erase2_sets()
34147 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, set28, ARRAY_SIZE(set28)); in check_erase2_sets()
34157 MT_BUG_ON(mt, mas.index != 139918401601536); in check_erase2_sets()
34159 mt_validate(mt); in check_erase2_sets()
34160 mtree_destroy(mt); in check_erase2_sets()
34167 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34168 check_erase2_testset(mt, set29, ARRAY_SIZE(set29)); in check_erase2_sets()
34171 mt_validate(mt); in check_erase2_sets()
34172 mtree_destroy(mt); in check_erase2_sets()
34180 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34181 check_erase2_testset(mt, set30, ARRAY_SIZE(set30)); in check_erase2_sets()
34184 mt_validate(mt); in check_erase2_sets()
34185 mtree_destroy(mt); in check_erase2_sets()
34193 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34194 check_erase2_testset(mt, set31, ARRAY_SIZE(set31)); in check_erase2_sets()
34197 mt_validate(mt); in check_erase2_sets()
34198 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, set32, ARRAY_SIZE(set32)); in check_erase2_sets()
34206 mt_validate(mt); in check_erase2_sets()
34207 mtree_destroy(mt); in check_erase2_sets()
34211 * mt 140582827569152 gap_end 140582869532672 in check_erase2_sets()
34222 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34223 check_erase2_testset(mt, set33, ARRAY_SIZE(set33)); in check_erase2_sets()
34226 MT_BUG_ON(mt, mas.last != 140583003750399); in check_erase2_sets()
34228 mt_validate(mt); in check_erase2_sets()
34229 mtree_destroy(mt); in check_erase2_sets()
34237 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34238 check_erase2_testset(mt, set34, ARRAY_SIZE(set34)); in check_erase2_sets()
34241 mt_validate(mt); in check_erase2_sets()
34242 mtree_destroy(mt); in check_erase2_sets()
34247 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34248 check_erase2_testset(mt, set35, ARRAY_SIZE(set35)); in check_erase2_sets()
34251 mt_validate(mt); in check_erase2_sets()
34252 mtree_destroy(mt); in check_erase2_sets()
34257 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34258 check_erase2_testset(mt, set36, ARRAY_SIZE(set36)); in check_erase2_sets()
34261 mt_validate(mt); in check_erase2_sets()
34262 mtree_destroy(mt); in check_erase2_sets()
34265 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34266 check_erase2_testset(mt, set37, ARRAY_SIZE(set37)); in check_erase2_sets()
34268 MT_BUG_ON(mt, NULL != mtree_load(mt, 94637033459712)); in check_erase2_sets()
34269 mt_validate(mt); in check_erase2_sets()
34270 mtree_destroy(mt); in check_erase2_sets()
34273 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34274 check_erase2_testset(mt, set38, ARRAY_SIZE(set38)); in check_erase2_sets()
34276 MT_BUG_ON(mt, NULL != mtree_load(mt, 94637033459712)); in check_erase2_sets()
34277 mt_validate(mt); in check_erase2_sets()
34278 mtree_destroy(mt); in check_erase2_sets()
34281 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34282 check_erase2_testset(mt, set39, ARRAY_SIZE(set39)); in check_erase2_sets()
34284 mt_validate(mt); in check_erase2_sets()
34285 mtree_destroy(mt); in check_erase2_sets()
34288 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34289 check_erase2_testset(mt, set40, ARRAY_SIZE(set40)); 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, set41, ARRAY_SIZE(set41)); in check_erase2_sets()
34298 mt_validate(mt); in check_erase2_sets()
34299 mtree_destroy(mt); in check_erase2_sets()
34304 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34305 check_erase2_testset(mt, set42, ARRAY_SIZE(set42)); in check_erase2_sets()
34308 MT_BUG_ON(mt, mas.last != 4041211903); in check_erase2_sets()
34310 mt_validate(mt); in check_erase2_sets()
34311 mtree_destroy(mt); in check_erase2_sets()
34316 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_erase2_sets()
34317 check_erase2_testset(mt, set43, ARRAY_SIZE(set43)); in check_erase2_sets()
34320 mt_validate(mt); in check_erase2_sets()
34321 mtree_destroy(mt); in check_erase2_sets()
34360 MA_STATE(mas, test->mt, 0, 0); in rcu_reader_fwd()
34470 MA_STATE(mas, test->mt, 0, 0); in rcu_reader_rev()
34532 mt_dump(test->mt, mt_dump_dec); in rcu_reader_rev()
34595 static void rcu_stress_rev(struct maple_tree *mt, struct rcu_test_struct2 *test, in rcu_stress_rev() argument
34615 mtree_store_range(mt, start, end, in rcu_stress_rev()
34625 mtree_store_range(mt, start, end, in rcu_stress_rev()
34636 mtree_store_range(mt, start, end, NULL, GFP_KERNEL); in rcu_stress_rev()
34643 mtree_store_range(mt, start, end, in rcu_stress_rev()
34654 static void rcu_stress_fwd(struct maple_tree *mt, struct rcu_test_struct2 *test, in rcu_stress_fwd() argument
34672 mtree_store_range(mt, start, end, in rcu_stress_fwd()
34682 mtree_store_range(mt, start, end, in rcu_stress_fwd()
34693 mtree_store_range(mt, start, end, NULL, GFP_KERNEL); in rcu_stress_fwd()
34700 mtree_store_range(mt, start, end, in rcu_stress_fwd()
34722 static void rcu_stress(struct maple_tree *mt, bool forward) in rcu_stress() argument
34732 test.mt = mt; in rcu_stress()
34744 mtree_store_range(mt, seed, r, in rcu_stress()
34776 mtree_store_range(mt, test.index[add], test.last[add], in rcu_stress()
34780 mt_set_in_rcu(mt); in rcu_stress()
34786 rcu_stress_fwd(mt, &test, count, test_reader); in rcu_stress()
34788 rcu_stress_rev(mt, &test, count, test_reader); in rcu_stress()
34794 mt_validate(mt); in rcu_stress()
34799 struct maple_tree *mt; /* the maple tree */ member
34878 entry = mtree_load(test->mt, test->index); in rcu_val()
34879 MT_BUG_ON(test->mt, eval_rcu_entry(test, entry, &update_2, in rcu_val()
34899 MA_STATE(mas, test->mt, test->range_start, test->range_start); in rcu_loop()
34920 MT_BUG_ON(test->mt, entry != expected); in rcu_loop()
34928 MT_BUG_ON(test->mt, eval_rcu_entry(test, entry, in rcu_loop()
34941 void run_check_rcu(struct maple_tree *mt, struct rcu_test_struct *vals) in run_check_rcu() argument
34948 mt_set_in_rcu(mt); in run_check_rcu()
34949 MT_BUG_ON(mt, !mt_in_rcu(mt)); in run_check_rcu()
34964 mtree_store_range(mt, vals->index, vals->last, vals->entry2, in run_check_rcu()
34970 MT_BUG_ON(mt, !vals->seen_entry2); in run_check_rcu()
34976 MA_STATE(mas, test->mt, test->index, test->index); in rcu_slot_store_reader()
34993 static noinline void run_check_rcu_slot_store(struct maple_tree *mt) in run_check_rcu_slot_store() argument
34998 struct rcu_test_struct3 test = {.stop = false, .mt = mt}; in run_check_rcu_slot_store()
35006 mtree_store_range(mt, i * len, i * len + len - 1, in run_check_rcu_slot_store()
35010 mt_set_in_rcu(mt); in run_check_rcu_slot_store()
35011 MT_BUG_ON(mt, !mt_in_rcu(mt)); in run_check_rcu_slot_store()
35025 mtree_store_range(mt, --start, ++end, xa_mk_value(100), in run_check_rcu_slot_store()
35034 mt_validate(mt); in run_check_rcu_slot_store()
35038 void run_check_rcu_slowread(struct maple_tree *mt, struct rcu_test_struct *vals) in run_check_rcu_slowread() argument
35046 mt_set_in_rcu(mt); in run_check_rcu_slowread()
35047 MT_BUG_ON(mt, !mt_in_rcu(mt)); in run_check_rcu_slowread()
35064 mtree_store(mt, index, in run_check_rcu_slowread()
35075 MT_BUG_ON(mt, !vals->seen_entry2); in run_check_rcu_slowread()
35076 MT_BUG_ON(mt, !vals->seen_entry3); in run_check_rcu_slowread()
35077 MT_BUG_ON(mt, !vals->seen_both); in run_check_rcu_slowread()
35079 static noinline void __init check_rcu_simulated(struct maple_tree *mt) in check_rcu_simulated() argument
35085 MA_STATE(mas_writer, mt, 0, 0); in check_rcu_simulated()
35086 MA_STATE(mas_reader, mt, target, target); in check_rcu_simulated()
35090 mt_set_in_rcu(mt); in check_rcu_simulated()
35102 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35106 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val)); in check_rcu_simulated()
35119 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35123 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val)); in check_rcu_simulated()
35136 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35140 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35153 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35157 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val)); in check_rcu_simulated()
35169 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35173 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val)); in check_rcu_simulated()
35185 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35189 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val)); in check_rcu_simulated()
35210 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35215 MT_BUG_ON(mt, mas_next(&mas_reader, ULONG_MAX) != xa_mk_value(val)); in check_rcu_simulated()
35229 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10)); in check_rcu_simulated()
35234 MT_BUG_ON(mt, mas_prev(&mas_reader, 0) != xa_mk_value(val)); in check_rcu_simulated()
35240 static noinline void __init check_rcu_threaded(struct maple_tree *mt) in check_rcu_threaded() argument
35250 mtree_store_range(mt, i*10, i*10 + 5, in check_rcu_threaded()
35254 vals.mt = mt; in check_rcu_threaded()
35265 run_check_rcu(mt, &vals); in check_rcu_threaded()
35266 mtree_destroy(mt); in check_rcu_threaded()
35268 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_rcu_threaded()
35270 mtree_store_range(mt, i*10, i*10 + 5, in check_rcu_threaded()
35277 vals.mt = mt; in check_rcu_threaded()
35286 run_check_rcu(mt, &vals); in check_rcu_threaded()
35287 mtree_destroy(mt); in check_rcu_threaded()
35290 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_rcu_threaded()
35291 run_check_rcu_slot_store(mt); in check_rcu_threaded()
35292 mtree_destroy(mt); in check_rcu_threaded()
35295 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_rcu_threaded()
35296 rcu_stress(mt, true); in check_rcu_threaded()
35297 mtree_destroy(mt); in check_rcu_threaded()
35300 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_rcu_threaded()
35301 rcu_stress(mt, false); in check_rcu_threaded()
35302 mtree_destroy(mt); in check_rcu_threaded()
35305 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_rcu_threaded()
35307 mtree_store_range(mt, i*10, i*10 + 5, in check_rcu_threaded()
35314 vals.mt = mt; in check_rcu_threaded()
35335 run_check_rcu_slowread(mt, &vals); in check_rcu_threaded()
35389 static void check_dfs_preorder(struct maple_tree *mt) in check_dfs_preorder() argument
35393 MA_STATE(mas, mt, 0, 0); in check_dfs_preorder()
35400 check_seq(mt, max, false); in check_dfs_preorder()
35405 MT_BUG_ON(mt, count != e); in check_dfs_preorder()
35406 mtree_destroy(mt); in check_dfs_preorder()
35408 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_dfs_preorder()
35414 check_seq(mt, max, false); in check_dfs_preorder()
35420 MT_BUG_ON(mt, count != e); in check_dfs_preorder()
35421 mtree_destroy(mt); in check_dfs_preorder()
35423 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_dfs_preorder()
35426 check_rev_seq(mt, max, false); in check_dfs_preorder()
35432 MT_BUG_ON(mt, count != e); in check_dfs_preorder()
35433 mtree_destroy(mt); in check_dfs_preorder()
35435 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_dfs_preorder()
35443 MT_BUG_ON(mt, mas_is_err(&mas)); in check_dfs_preorder()
35457 static noinline void __init check_prealloc(struct maple_tree *mt) in check_prealloc() argument
35464 MA_STATE(mas, mt, 10, 20); in check_prealloc()
35468 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_prealloc()
35472 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35475 MT_BUG_ON(mt, allocated == 0); in check_prealloc()
35476 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35479 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35481 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35484 MT_BUG_ON(mt, allocated == 0); in check_prealloc()
35485 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35486 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35489 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35492 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35495 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35497 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); in check_prealloc()
35500 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35503 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35505 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35508 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35510 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); in check_prealloc()
35511 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35514 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35518 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35521 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35523 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); in check_prealloc()
35525 MT_BUG_ON(mt, mas_allocated(&mas) != allocated); in check_prealloc()
35526 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35529 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35531 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35534 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35536 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35540 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35542 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35544 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35547 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35550 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35552 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35556 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35559 MT_BUG_ON(mt, allocated != 1 + height * 2); in check_prealloc()
35561 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35565 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0); in check_prealloc()
35568 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35573 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35576 MT_BUG_ON(mt, allocated == 0); in check_prealloc()
35577 MT_BUG_ON(mt, allocated != 1 + height * 3); in check_prealloc()
35579 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35582 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0); in check_prealloc()
35585 MT_BUG_ON(mt, allocated != 0); in check_prealloc()
35590 static noinline void __init check_spanning_write(struct maple_tree *mt) in check_spanning_write() argument
35593 MA_STATE(mas, mt, 1200, 2380); in check_spanning_write()
35596 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35598 mtree_lock(mt); in check_spanning_write()
35601 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35602 mtree_unlock(mt); in check_spanning_write()
35603 mtree_destroy(mt); in check_spanning_write()
35606 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35608 mtree_lock(mt); in check_spanning_write()
35612 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35613 mtree_unlock(mt); in check_spanning_write()
35614 mt_validate(mt); in check_spanning_write()
35615 mtree_destroy(mt); in check_spanning_write()
35618 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35620 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35623 mtree_lock(mt); in check_spanning_write()
35626 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35627 mtree_unlock(mt); in check_spanning_write()
35628 mtree_destroy(mt); in check_spanning_write()
35631 mt_init_flags(mt, 0); in check_spanning_write()
35633 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35636 mtree_lock(mt); in check_spanning_write()
35639 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35640 mtree_unlock(mt); in check_spanning_write()
35641 mtree_destroy(mt); in check_spanning_write()
35644 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35646 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35649 mtree_lock(mt); in check_spanning_write()
35652 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35653 mtree_unlock(mt); in check_spanning_write()
35654 mtree_destroy(mt); in check_spanning_write()
35657 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35659 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35662 mtree_lock(mt); in check_spanning_write()
35665 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35666 mtree_unlock(mt); in check_spanning_write()
35667 mtree_destroy(mt); in check_spanning_write()
35670 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35672 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35675 mtree_lock(mt); in check_spanning_write()
35678 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35679 mtree_unlock(mt); in check_spanning_write()
35680 mtree_destroy(mt); in check_spanning_write()
35686 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35688 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35691 mtree_lock(mt); in check_spanning_write()
35694 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35695 mtree_unlock(mt); in check_spanning_write()
35696 mtree_destroy(mt); in check_spanning_write()
35702 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35704 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35706 mtree_lock(mt); in check_spanning_write()
35709 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35710 mtree_unlock(mt); in check_spanning_write()
35711 mtree_destroy(mt); in check_spanning_write()
35714 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35716 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35717 mtree_lock(mt); in check_spanning_write()
35728 MT_BUG_ON(mt, (mas_data_end(&mas)) != mt_slot_count(mas.node) - 1); in check_spanning_write()
35731 mtree_unlock(mt); in check_spanning_write()
35732 mtree_destroy(mt); in check_spanning_write()
35735 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35737 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35739 mtree_lock(mt); in check_spanning_write()
35742 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35743 mtree_unlock(mt); in check_spanning_write()
35744 mtree_destroy(mt); in check_spanning_write()
35746 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_spanning_write()
35748 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_spanning_write()
35750 mtree_lock(mt); in check_spanning_write()
35753 mtree_unlock(mt); in check_spanning_write()
35758 static noinline void __init check_null_expand(struct maple_tree *mt) in check_null_expand() argument
35762 MA_STATE(mas, mt, 959, 959); in check_null_expand()
35765 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i); in check_null_expand()
35772 MT_BUG_ON(mt, mtree_load(mt, 963) != NULL); in check_null_expand()
35773 MT_BUG_ON(mt, data_end != mas_data_end(&mas)); in check_null_expand()
35781 MT_BUG_ON(mt, mtree_load(mt, 884) != NULL); in check_null_expand()
35782 MT_BUG_ON(mt, mtree_load(mt, 889) != NULL); in check_null_expand()
35784 MT_BUG_ON(mt, data_end != mas_data_end(&mas)); in check_null_expand()
35793 MT_BUG_ON(mt, mtree_load(mt, 899) != NULL); in check_null_expand()
35794 MT_BUG_ON(mt, mtree_load(mt, 900) != NULL); in check_null_expand()
35795 MT_BUG_ON(mt, mtree_load(mt, 905) != NULL); in check_null_expand()
35796 MT_BUG_ON(mt, mtree_load(mt, 906) != NULL); in check_null_expand()
35798 MT_BUG_ON(mt, data_end - 2 != mas_data_end(&mas)); in check_null_expand()
35807 MT_BUG_ON(mt, mtree_load(mt, 809) != NULL); in check_null_expand()
35808 MT_BUG_ON(mt, mtree_load(mt, 810) != NULL); in check_null_expand()
35809 MT_BUG_ON(mt, mtree_load(mt, 825) != NULL); in check_null_expand()
35810 MT_BUG_ON(mt, mtree_load(mt, 826) != NULL); in check_null_expand()
35812 MT_BUG_ON(mt, data_end - 4 != mas_data_end(&mas)); in check_null_expand()
35819 static noinline void __init check_nomem(struct maple_tree *mt) in check_nomem() argument
35821 MA_STATE(ms, mt, 1, 1); in check_nomem()
35823 MT_BUG_ON(mt, !mtree_empty(mt)); in check_nomem()
35828 MT_BUG_ON(mt, mtree_insert(mt, 1, &ms, GFP_ATOMIC) != -ENOMEM); in check_nomem()
35830 MT_BUG_ON(mt, mtree_insert(mt, 0, &ms, GFP_ATOMIC) != 0); in check_nomem()
35840 mtree_lock(mt); in check_nomem()
35842 MT_BUG_ON(mt, ms.node != MA_ERROR(-ENOMEM)); in check_nomem()
35844 MT_BUG_ON(mt, ms.status != ma_start); in check_nomem()
35845 mtree_unlock(mt); in check_nomem()
35846 MT_BUG_ON(mt, mtree_insert(mt, 2, mt, GFP_KERNEL) != 0); in check_nomem()
35847 mtree_lock(mt); in check_nomem()
35850 mtree_unlock(mt); in check_nomem()
35852 mtree_destroy(mt); in check_nomem()
35855 static noinline void __init check_locky(struct maple_tree *mt) in check_locky() argument
35857 MA_STATE(ms, mt, 2, 2); in check_locky()
35858 MA_STATE(reader, mt, 2, 2); in check_locky()
35861 mt_set_in_rcu(mt); in check_locky()
35867 mt_clear_in_rcu(mt); in check_locky()
36016 * @mt: The tree to build.
36024 static __init int build_full_tree(struct maple_tree *mt, unsigned int flags, in build_full_tree() argument
36027 MA_STATE(mas, mt, 0, 0); in build_full_tree()
36032 mt_init_flags(mt, flags); in build_full_tree()
36033 mtree_insert_range(mt, 0, ULONG_MAX, xa_mk_value(5), GFP_KERNEL); in build_full_tree()
36035 mtree_lock(mt); in build_full_tree()
36039 if (mt_height(mt) < height) { in build_full_tree()
36070 mtree_unlock(mt); in build_full_tree()
36072 MT_BUG_ON(mt, mt_height(mt) != height); in build_full_tree()
36073 /* pr_info("height:%u number of elements:%d\n", mt_height(mt), cnt); */ in build_full_tree()
36077 static noinline void __init check_mtree_dup(struct maple_tree *mt) in check_mtree_dup() argument
36084 mt_init_flags(mt, 0); in check_mtree_dup()
36085 mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL); in check_mtree_dup()
36086 ret = mtree_dup(mt, &new, GFP_KERNEL); in check_mtree_dup()
36089 if (compare_tree(mt, &new)) in check_mtree_dup()
36092 mtree_destroy(mt); in check_mtree_dup()
36096 mt_init_flags(mt, 0); in check_mtree_dup()
36098 ret = mtree_dup(mt, &new, GFP_KERNEL); in check_mtree_dup()
36100 mtree_destroy(mt); in check_mtree_dup()
36104 mt_init_flags(mt, 0); in check_mtree_dup()
36107 ret = mtree_dup(mt, &new, GFP_KERNEL); in check_mtree_dup()
36109 mtree_destroy(mt); in check_mtree_dup()
36114 ret = build_full_tree(mt, 0, i); in check_mtree_dup()
36115 MT_BUG_ON(mt, ret); in check_mtree_dup()
36118 ret = mtree_dup(mt, &new, GFP_KERNEL); in check_mtree_dup()
36121 if (compare_tree(mt, &new)) in check_mtree_dup()
36124 mtree_destroy(mt); in check_mtree_dup()
36129 ret = build_full_tree(mt, MT_FLAGS_ALLOC_RANGE, i); in check_mtree_dup()
36130 MT_BUG_ON(mt, ret); in check_mtree_dup()
36133 ret = mtree_dup(mt, &new, GFP_KERNEL); in check_mtree_dup()
36136 if (compare_tree(mt, &new)) in check_mtree_dup()
36139 mtree_destroy(mt); in check_mtree_dup()
36146 mt_init_flags(mt, 0); in check_mtree_dup()
36149 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_mtree_dup()
36154 mtree_store_range(mt, j * 10, j * 10 + 5, in check_mtree_dup()
36158 ret = mtree_dup(mt, &new, GFP_KERNEL); in check_mtree_dup()
36161 if (compare_tree(mt, &new)) in check_mtree_dup()
36164 mtree_destroy(mt); in check_mtree_dup()
36169 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_mtree_dup()
36171 mtree_store_range(mt, j * 10, j * 10 + 5, in check_mtree_dup()
36178 ret = mtree_dup(mt, &new, GFP_NOWAIT); in check_mtree_dup()
36181 mtree_destroy(mt); in check_mtree_dup()
36187 mt_init_flags(mt, 0); in check_mtree_dup()
36190 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); in check_mtree_dup()
36195 mtree_store_range(mt, j * 10, j * 10 + 5, in check_mtree_dup()
36206 ret = mtree_dup(mt, &new, GFP_NOWAIT); in check_mtree_dup()
36211 mtree_destroy(mt); in check_mtree_dup()
36216 if (compare_tree(mt, &new)) in check_mtree_dup()
36219 mtree_destroy(mt); in check_mtree_dup()
36232 struct maple_tree *mt = (struct maple_tree *)maple_tree; in writer2() local
36233 MA_STATE(mas, mt, 6, 10); in writer2()
36243 * @mt: The tree to build.
36250 static void check_nomem_writer_race(struct maple_tree *mt) in check_nomem_writer_race() argument
36252 MA_STATE(mas, mt, 0, 5); in check_nomem_writer_race()
36256 mtree_store_range(mt, 0, 5, xa_mk_value(0xA), GFP_KERNEL); in check_nomem_writer_race()
36257 mtree_store_range(mt, 6, 10, NULL, GFP_KERNEL); in check_nomem_writer_race()
36258 mtree_store_range(mt, 11, 15, xa_mk_value(0xB), GFP_KERNEL); in check_nomem_writer_race()
36261 mt_set_private(mt); in check_nomem_writer_race()
36264 mtree_lock(mt); in check_nomem_writer_race()
36269 check_load(mt, 6, xa_mk_value(0xC)); in check_nomem_writer_race()
36270 mtree_unlock(mt); in check_nomem_writer_race()
36273 mtree_store_range(mt, 0, 5, xa_mk_value(0xA), GFP_KERNEL); in check_nomem_writer_race()
36274 mtree_store_range(mt, 6, 10, NULL, GFP_KERNEL); in check_nomem_writer_race()
36277 mtree_lock(mt); in check_nomem_writer_race()
36281 check_load(mt, 6, xa_mk_value(0xC)); in check_nomem_writer_race()
36285 mtree_unlock(mt); in check_nomem_writer_race()
36292 static inline int check_vma_modification(struct maple_tree *mt) in check_vma_modification() argument
36294 MA_STATE(mas, mt, 0, 0); in check_vma_modification()
36296 mtree_lock(mt); in check_vma_modification()
36313 mt_dump(mt, mt_dump_hex); in check_vma_modification()
36316 mtree_unlock(mt); in check_vma_modification()
36324 static inline void check_bulk_rebalance(struct maple_tree *mt) in check_bulk_rebalance() argument
36326 MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX); in check_bulk_rebalance()
36329 build_full_tree(mt, 0, 2); in check_bulk_rebalance()
36336 MT_BUG_ON(mt, mas.store_type == wr_rebalance); in check_bulk_rebalance()
36438 enum maple_type mt = mte_node_type(mas->node); in get_last_index() local
36439 unsigned long *pivots = ma_pivots(node, mt); in get_last_index()