Lines Matching refs:mt
29 #define RCU_MT_BUG_ON(test, y) {if (y) { test->stop = true; } MT_BUG_ON(test->mt, y); }
32 struct maple_tree *mt;
49 struct maple_tree *mt;
91 static noinline void __init check_new_node(struct maple_tree *mt)
99 MA_STATE(mas, mt, 0, 0);
104 mtree_lock(mt);
109 MT_BUG_ON(mt, mas_alloc_req(&mas) != 3);
111 MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM));
112 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
114 MT_BUG_ON(mt, mas_allocated(&mas) != 3);
116 MT_BUG_ON(mt, not_empty(mn));
117 MT_BUG_ON(mt, mn == NULL);
118 MT_BUG_ON(mt, mas.alloc == NULL);
119 MT_BUG_ON(mt, mas.alloc->slot[0] == NULL);
122 mtree_unlock(mt);
126 mtree_lock(mt);
130 MT_BUG_ON(mt, mas_alloc_req(&mas) != 1);
133 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
136 MT_BUG_ON(mt, not_empty(mn));
137 MT_BUG_ON(mt, mn == NULL);
138 MT_BUG_ON(mt, mn->slot[0] != NULL);
139 MT_BUG_ON(mt, mn->slot[1] != NULL);
140 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
151 MT_BUG_ON(mt, mas_allocated(&mas) != 3);
153 MT_BUG_ON(mt, mas_alloc_req(&mas) != 0);
155 MT_BUG_ON(mt, mas.alloc == NULL);
156 MT_BUG_ON(mt, mas.alloc->slot[0] == NULL);
157 MT_BUG_ON(mt, mas.alloc->slot[1] == NULL);
159 MT_BUG_ON(mt, mas_allocated(&mas) != 3);
165 MT_BUG_ON(mt, mas_alloc_req(&mas) != 1);
168 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
169 MT_BUG_ON(mt, mas_allocated(&mas) != 1);
172 MT_BUG_ON(mt, not_empty(mn));
173 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
174 MT_BUG_ON(mt, mn == NULL);
175 MT_BUG_ON(mt, mn->slot[0] != NULL);
176 MT_BUG_ON(mt, mn->slot[1] != NULL);
177 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
179 MT_BUG_ON(mt, mas_allocated(&mas) != 1);
180 MT_BUG_ON(mt, mas.alloc->node_count);
183 MT_BUG_ON(mt, mas_alloc_req(&mas) != 2);
185 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
186 MT_BUG_ON(mt, mas_allocated(&mas) != 3);
187 MT_BUG_ON(mt, mas.alloc == NULL);
188 MT_BUG_ON(mt, mas.alloc->slot[0] == NULL);
189 MT_BUG_ON(mt, mas.alloc->slot[1] == NULL);
192 MT_BUG_ON(mt, mas_allocated(&mas) != i);
193 MT_BUG_ON(mt, !mn);
194 MT_BUG_ON(mt, not_empty(mn));
201 MT_BUG_ON(mt, mas_alloc_req(&mas) != total);
203 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
223 MT_BUG_ON(mt, mas.alloc->node_count != e);
225 MT_BUG_ON(mt, not_empty(mn));
226 MT_BUG_ON(mt, mas_allocated(&mas) != i - 1);
227 MT_BUG_ON(mt, !mn);
236 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
239 MT_BUG_ON(mt, mas_allocated(&mas) != j - 1);
240 MT_BUG_ON(mt, !mn);
241 MT_BUG_ON(mt, not_empty(mn));
243 MT_BUG_ON(mt, mas_allocated(&mas) != j);
245 MT_BUG_ON(mt, not_empty(mn));
246 MT_BUG_ON(mt, mas_allocated(&mas) != j - 1);
250 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
254 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
256 MT_BUG_ON(mt, mas_allocated(&mas) != i - j);
258 MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1);
264 MT_BUG_ON(mt, mas_allocated(&mas) != i - j);
266 MT_BUG_ON(mt, mas_allocated(&mas) != i);
268 MT_BUG_ON(mt, mas_allocated(&mas) != i - j);
270 MT_BUG_ON(mt, not_empty(mn));
273 MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1);
275 MT_BUG_ON(mt, mas_nomem(&mas, GFP_KERNEL));
284 MT_BUG_ON(mt, !mas.alloc);
290 MT_BUG_ON(mt, !smn->slot[j]);
296 MT_BUG_ON(mt, mas_allocated(&mas) != total);
299 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
303 MT_BUG_ON(mt, mas_allocated(&mas) != i); /* check request filled */
306 MT_BUG_ON(mt, mn == NULL);
307 MT_BUG_ON(mt, not_empty(mn));
311 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
315 MA_STATE(mas2, mt, 0, 0);
318 MT_BUG_ON(mt, mas_allocated(&mas) != i); /* check request filled */
321 MT_BUG_ON(mt, mn == NULL);
322 MT_BUG_ON(mt, not_empty(mn));
324 MT_BUG_ON(mt, mas_allocated(&mas2) != j);
326 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
327 MT_BUG_ON(mt, mas_allocated(&mas2) != i);
330 MT_BUG_ON(mt, mas_allocated(&mas2) != j);
332 MT_BUG_ON(mt, mn == NULL);
333 MT_BUG_ON(mt, not_empty(mn));
337 MT_BUG_ON(mt, mas_allocated(&mas2) != 0);
341 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
343 MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM));
344 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
345 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
346 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS);
349 MT_BUG_ON(mt, mn == NULL);
350 MT_BUG_ON(mt, not_empty(mn));
351 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS);
352 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS - 1);
355 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
356 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS);
360 MT_BUG_ON(mt, mas_alloc_req(&mas) != 1);
361 MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM));
362 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
363 MT_BUG_ON(mt, mas_alloc_req(&mas));
364 MT_BUG_ON(mt, mas.alloc->node_count != 1);
365 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 2);
367 MT_BUG_ON(mt, not_empty(mn));
368 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
369 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS);
371 MT_BUG_ON(mt, mas.alloc->node_count != 1);
372 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 2);
374 MT_BUG_ON(mt, not_empty(mn));
379 MT_BUG_ON(mt, not_empty(mn));
383 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
440 MT_BUG_ON(mt, mas_allocated(&mas) != 5);
445 MT_BUG_ON(mt, mas_allocated(&mas) != 10);
451 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS - 1);
456 MT_BUG_ON(mt, mas_allocated(&mas) != 10 + MAPLE_ALLOC_SLOTS - 1);
459 mtree_unlock(mt);
465 static noinline void __init check_erase(struct maple_tree *mt, unsigned long index,
468 MT_BUG_ON(mt, mtree_test_erase(mt, index) != ptr);
471 #define erase_check_load(mt, i) check_load(mt, set[i], entry[i%2])
472 #define erase_check_insert(mt, i) check_insert(mt, set[i], entry[i%2])
473 #define erase_check_erase(mt, i) check_erase(mt, set[i], entry[i%2])
475 static noinline void __init check_erase_testset(struct maple_tree *mt)
493 void *entry[2] = { ptr, mt };
498 mt_set_in_rcu(mt);
500 erase_check_insert(mt, i);
502 erase_check_load(mt, i);
505 erase_check_erase(mt, 1);
506 erase_check_load(mt, 0);
507 check_load(mt, set[1], NULL);
509 erase_check_load(mt, i);
512 erase_check_erase(mt, 2);
513 erase_check_load(mt, 0);
514 check_load(mt, set[1], NULL);
515 check_load(mt, set[2], NULL);
517 erase_check_insert(mt, 1);
518 erase_check_insert(mt, 2);
521 erase_check_load(mt, i);
524 erase_check_load(mt, 3);
525 erase_check_erase(mt, 1);
526 erase_check_load(mt, 0);
527 check_load(mt, set[1], NULL);
529 erase_check_load(mt, i);
535 root_node = mt->ma_root;
536 erase_check_insert(mt, 1);
538 erase_check_load(mt, 0);
539 check_load(mt, 5016, NULL);
540 erase_check_load(mt, 1);
541 check_load(mt, 5013, NULL);
542 erase_check_load(mt, 2);
543 check_load(mt, 5018, NULL);
544 erase_check_load(mt, 3);
546 erase_check_erase(mt, 2); /* erase 5017 to check append */
547 erase_check_load(mt, 0);
548 check_load(mt, 5016, NULL);
549 erase_check_load(mt, 1);
550 check_load(mt, 5013, NULL);
551 check_load(mt, set[2], NULL);
552 check_load(mt, 5018, NULL);
554 erase_check_load(mt, 3);
556 root_node = mt->ma_root;
557 erase_check_insert(mt, 2);
559 erase_check_load(mt, 0);
560 check_load(mt, 5016, NULL);
561 erase_check_load(mt, 1);
562 check_load(mt, 5013, NULL);
563 erase_check_load(mt, 2);
564 check_load(mt, 5018, NULL);
565 erase_check_load(mt, 3);
568 erase_check_erase(mt, 2); /* erase 5017 to check append */
569 erase_check_load(mt, 0);
570 check_load(mt, 5016, NULL);
571 check_load(mt, set[2], NULL);
572 erase_check_erase(mt, 0); /* erase 5015 to check append */
573 check_load(mt, set[0], NULL);
574 check_load(mt, 5016, NULL);
575 erase_check_insert(mt, 4); /* 1000 < Should not split. */
576 check_load(mt, set[0], NULL);
577 check_load(mt, 5016, NULL);
578 erase_check_load(mt, 1);
579 check_load(mt, 5013, NULL);
580 check_load(mt, set[2], NULL);
581 check_load(mt, 5018, NULL);
582 erase_check_load(mt, 4);
583 check_load(mt, 999, NULL);
584 check_load(mt, 1001, NULL);
585 erase_check_load(mt, 4);
586 if (mt_in_rcu(mt))
587 MT_BUG_ON(mt, root_node == mt->ma_root);
589 MT_BUG_ON(mt, root_node != mt->ma_root);
592 MT_BUG_ON(mt, !mte_is_leaf(mt->ma_root));
596 erase_check_insert(mt, 0);
597 erase_check_insert(mt, 2);
600 erase_check_insert(mt, i);
602 erase_check_load(mt, j);
605 erase_check_erase(mt, 14); /*6015 */
608 check_load(mt, set[i], NULL);
610 erase_check_load(mt, i);
612 erase_check_erase(mt, 16); /*7002 */
615 check_load(mt, set[i], NULL);
617 erase_check_load(mt, i);
622 erase_check_erase(mt, 13); /*6012 */
625 check_load(mt, set[i], NULL);
627 erase_check_load(mt, i);
630 erase_check_erase(mt, 15); /*7003 */
633 check_load(mt, set[i], NULL);
635 erase_check_load(mt, i);
639 erase_check_erase(mt, 17); /*7008 *should* cause coalesce. */
642 check_load(mt, set[i], NULL);
644 erase_check_load(mt, i);
647 erase_check_erase(mt, 18); /*7012 */
650 check_load(mt, set[i], NULL);
652 erase_check_load(mt, i);
656 erase_check_erase(mt, 19); /*7015 */
659 check_load(mt, set[i], NULL);
661 erase_check_load(mt, i);
664 erase_check_erase(mt, 20); /*8003 */
667 check_load(mt, set[i], NULL);
669 erase_check_load(mt, i);
672 erase_check_erase(mt, 21); /*8002 */
675 check_load(mt, set[i], NULL);
677 erase_check_load(mt, i);
681 erase_check_erase(mt, 22); /*8008 */
684 check_load(mt, set[i], NULL);
686 erase_check_load(mt, i);
689 erase_check_erase(mt, i);
693 check_load(mt, set[i], NULL);
695 erase_check_load(mt, i);
701 erase_check_insert(mt, i);
705 erase_check_erase(mt, i);
708 erase_check_load(mt, j);
710 check_load(mt, set[j], NULL);
715 erase_check_erase(mt, i);
718 erase_check_load(mt, j);
720 check_load(mt, set[j], NULL);
723 erase_check_insert(mt, 8);
724 erase_check_insert(mt, 9);
725 erase_check_erase(mt, 8);
732 #define erase_check_store_range(mt, a, i, ptr) mtree_test_store_range(mt, \
979 static noinline void __init check_erase2_testset(struct maple_tree *mt,
988 MA_STATE(mas, mt, 0, 0);
995 MA_STATE(mas_start, mt, set[i+1], set[i+1]);
996 MA_STATE(mas_end, mt, set[i+2], set[i+2]);
1023 erase_check_store_range(mt, set, i + 1, value);
1051 erase_check_store_range(mt, set, i + 1, value);
1056 check_erase(mt, set[i+1], xa_mk_value(set[i+1]));
1060 mt_validate(mt);
1062 MT_BUG_ON(mt, !mt_height(mt));
1064 mt_dump(mt, mt_dump_hex);
1072 mt_for_each(mt, foo, addr, ULONG_MAX) {
1075 pr_err("mt: %lu -> %p (%d)\n", addr+1, foo, check);
1085 MT_BUG_ON(mt, check != entry_count);
1098 MT_BUG_ON(mt, 1);
1113 mt_validate(mt);
1116 MT_BUG_ON(mt, check != entry_count);
1118 MT_BUG_ON(mt, mtree_load(mas.tree, 0) != NULL);
1124 static noinline void __init check_erase2_sets(struct maple_tree *mt)
33864 * Gap was found: mt 4041162752 gap_end 4041183232
33896 MA_STATE(mas, mt, 0, 0);
33899 check_erase2_testset(mt, set, ARRAY_SIZE(set));
33901 mtree_destroy(mt);
33903 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
33904 check_erase2_testset(mt, set2, ARRAY_SIZE(set2));
33906 MT_BUG_ON(mt, !!mt_find(mt, &start, 140735933906943UL));
33907 mtree_destroy(mt);
33910 mt_init_flags(mt, 0);
33911 check_erase2_testset(mt, set3, ARRAY_SIZE(set3));
33913 mtree_destroy(mt);
33915 mt_init_flags(mt, 0);
33916 check_erase2_testset(mt, set4, ARRAY_SIZE(set4));
33924 mtree_destroy(mt);
33926 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
33928 check_erase2_testset(mt, set5, ARRAY_SIZE(set5));
33931 mtree_destroy(mt);
33933 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
33934 check_erase2_testset(mt, set6, ARRAY_SIZE(set6));
33936 mtree_destroy(mt);
33938 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
33939 check_erase2_testset(mt, set7, ARRAY_SIZE(set7));
33941 mtree_destroy(mt);
33943 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
33944 check_erase2_testset(mt, set8, ARRAY_SIZE(set8));
33946 mtree_destroy(mt);
33948 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
33949 check_erase2_testset(mt, set9, ARRAY_SIZE(set9));
33951 mtree_destroy(mt);
33953 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
33954 check_erase2_testset(mt, set10, ARRAY_SIZE(set10));
33956 mtree_destroy(mt);
33959 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
33960 check_erase2_testset(mt, set11, ARRAY_SIZE(set11));
33963 MT_BUG_ON(mt, mas.last != 140014592573439);
33964 mtree_destroy(mt);
33967 mas.tree = mt;
33970 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
33971 check_erase2_testset(mt, set12, ARRAY_SIZE(set12));
33979 mtree_destroy(mt);
33982 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
33983 check_erase2_testset(mt, set13, ARRAY_SIZE(set13));
33984 mtree_erase(mt, 140373516443648);
33988 mtree_destroy(mt);
33989 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
33990 check_erase2_testset(mt, set14, ARRAY_SIZE(set14));
33992 mtree_destroy(mt);
33994 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
33995 check_erase2_testset(mt, set15, ARRAY_SIZE(set15));
33997 mtree_destroy(mt);
34002 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34003 check_erase2_testset(mt, set16, ARRAY_SIZE(set16));
34006 MT_BUG_ON(mt, mas.last != 139921865547775);
34008 mtree_destroy(mt);
34017 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34018 check_erase2_testset(mt, set17, ARRAY_SIZE(set17));
34021 MT_BUG_ON(mt, mas.last != 139953197322239);
34022 /* MT_BUG_ON(mt, mas.index != 139953197318144); */
34024 mtree_destroy(mt);
34033 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34034 check_erase2_testset(mt, set18, ARRAY_SIZE(set18));
34037 MT_BUG_ON(mt, mas.last != 140222968475647);
34038 /*MT_BUG_ON(mt, mas.index != 140222966259712); */
34040 mtree_destroy(mt);
34051 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34052 check_erase2_testset(mt, set19, ARRAY_SIZE(set19));
34056 MT_BUG_ON(mt, entry != xa_mk_value(140656779083776));
34058 MT_BUG_ON(mt, entry != xa_mk_value(140656766251008));
34060 mtree_destroy(mt);
34067 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34068 check_erase2_testset(mt, set20, ARRAY_SIZE(set20));
34070 check_load(mt, 94849009414144, NULL);
34072 mtree_destroy(mt);
34075 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34076 check_erase2_testset(mt, set21, ARRAY_SIZE(set21));
34078 mt_validate(mt);
34080 mtree_destroy(mt);
34083 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34084 check_erase2_testset(mt, set22, ARRAY_SIZE(set22));
34086 mt_validate(mt);
34087 ptr = mtree_load(mt, 140551363362816);
34088 MT_BUG_ON(mt, ptr == mtree_load(mt, 140551363420159));
34090 mtree_destroy(mt);
34093 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34094 check_erase2_testset(mt, set23, ARRAY_SIZE(set23));
34097 mt_validate(mt);
34098 mtree_destroy(mt);
34102 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34103 check_erase2_testset(mt, set24, ARRAY_SIZE(set24));
34106 mt_validate(mt);
34107 mtree_destroy(mt);
34110 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34111 check_erase2_testset(mt, set25, ARRAY_SIZE(set25));
34114 mt_validate(mt);
34115 mtree_destroy(mt);
34120 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34121 check_erase2_testset(mt, set26, ARRAY_SIZE(set26));
34124 MT_BUG_ON(mt, mas.last != 140109040959487);
34126 mt_validate(mt);
34127 mtree_destroy(mt);
34132 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34133 check_erase2_testset(mt, set27, ARRAY_SIZE(set27));
34135 MT_BUG_ON(mt, 0 != mtree_load(mt, 140415537422336));
34137 mt_validate(mt);
34138 mtree_destroy(mt);
34142 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34143 check_erase2_testset(mt, set28, ARRAY_SIZE(set28));
34148 MT_BUG_ON(mt, mas.index != 139918401601536);
34150 mt_validate(mt);
34151 mtree_destroy(mt);
34158 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34159 check_erase2_testset(mt, set29, ARRAY_SIZE(set29));
34162 mt_validate(mt);
34163 mtree_destroy(mt);
34171 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34172 check_erase2_testset(mt, set30, ARRAY_SIZE(set30));
34175 mt_validate(mt);
34176 mtree_destroy(mt);
34184 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34185 check_erase2_testset(mt, set31, ARRAY_SIZE(set31));
34188 mt_validate(mt);
34189 mtree_destroy(mt);
34193 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34194 check_erase2_testset(mt, set32, ARRAY_SIZE(set32));
34197 mt_validate(mt);
34198 mtree_destroy(mt);
34202 * mt 140582827569152 gap_end 140582869532672
34213 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34214 check_erase2_testset(mt, set33, ARRAY_SIZE(set33));
34217 MT_BUG_ON(mt, mas.last != 140583003750399);
34219 mt_validate(mt);
34220 mtree_destroy(mt);
34228 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34229 check_erase2_testset(mt, set34, ARRAY_SIZE(set34));
34232 mt_validate(mt);
34233 mtree_destroy(mt);
34238 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34239 check_erase2_testset(mt, set35, ARRAY_SIZE(set35));
34242 mt_validate(mt);
34243 mtree_destroy(mt);
34248 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34249 check_erase2_testset(mt, set36, ARRAY_SIZE(set36));
34252 mt_validate(mt);
34253 mtree_destroy(mt);
34256 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34257 check_erase2_testset(mt, set37, ARRAY_SIZE(set37));
34259 MT_BUG_ON(mt, 0 != mtree_load(mt, 94637033459712));
34260 mt_validate(mt);
34261 mtree_destroy(mt);
34264 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34265 check_erase2_testset(mt, set38, ARRAY_SIZE(set38));
34267 MT_BUG_ON(mt, 0 != mtree_load(mt, 94637033459712));
34268 mt_validate(mt);
34269 mtree_destroy(mt);
34272 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34273 check_erase2_testset(mt, set39, ARRAY_SIZE(set39));
34275 mt_validate(mt);
34276 mtree_destroy(mt);
34279 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34280 check_erase2_testset(mt, set40, ARRAY_SIZE(set40));
34282 mt_validate(mt);
34283 mtree_destroy(mt);
34286 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34287 check_erase2_testset(mt, set41, ARRAY_SIZE(set41));
34289 mt_validate(mt);
34290 mtree_destroy(mt);
34295 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34296 check_erase2_testset(mt, set42, ARRAY_SIZE(set42));
34299 MT_BUG_ON(mt, mas.last != 4041211903);
34301 mt_validate(mt);
34302 mtree_destroy(mt);
34307 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
34308 check_erase2_testset(mt, set43, ARRAY_SIZE(set43));
34311 mt_validate(mt);
34312 mtree_destroy(mt);
34351 MA_STATE(mas, test->mt, 0, 0);
34461 MA_STATE(mas, test->mt, 0, 0);
34523 mt_dump(test->mt, mt_dump_dec);
34586 static void rcu_stress_rev(struct maple_tree *mt, struct rcu_test_struct2 *test,
34606 mtree_store_range(mt, start, end,
34616 mtree_store_range(mt, start, end,
34627 mtree_store_range(mt, start, end, NULL, GFP_KERNEL);
34634 mtree_store_range(mt, start, end,
34645 static void rcu_stress_fwd(struct maple_tree *mt, struct rcu_test_struct2 *test,
34663 mtree_store_range(mt, start, end,
34673 mtree_store_range(mt, start, end,
34684 mtree_store_range(mt, start, end, NULL, GFP_KERNEL);
34691 mtree_store_range(mt, start, end,
34713 static void rcu_stress(struct maple_tree *mt, bool forward)
34723 test.mt = mt;
34735 mtree_store_range(mt, seed, r,
34767 mtree_store_range(mt, test.index[add], test.last[add],
34771 mt_set_in_rcu(mt);
34777 rcu_stress_fwd(mt, &test, count, test_reader);
34779 rcu_stress_rev(mt, &test, count, test_reader);
34785 mt_validate(mt);
34790 struct maple_tree *mt; /* the maple tree */
34869 entry = mtree_load(test->mt, test->index);
34870 MT_BUG_ON(test->mt, eval_rcu_entry(test, entry, &update_2,
34890 MA_STATE(mas, test->mt, test->range_start, test->range_start);
34911 MT_BUG_ON(test->mt, entry != expected);
34919 MT_BUG_ON(test->mt, eval_rcu_entry(test, entry,
34932 void run_check_rcu(struct maple_tree *mt, struct rcu_test_struct *vals)
34939 mt_set_in_rcu(mt);
34940 MT_BUG_ON(mt, !mt_in_rcu(mt));
34955 mtree_store_range(mt, vals->index, vals->last, vals->entry2,
34961 MT_BUG_ON(mt, !vals->seen_entry2);
34967 MA_STATE(mas, test->mt, test->index, test->index);
34984 static noinline void run_check_rcu_slot_store(struct maple_tree *mt)
34989 struct rcu_test_struct3 test = {.stop = false, .mt = mt};
34997 mtree_store_range(mt, i * len, i * len + len - 1,
35001 mt_set_in_rcu(mt);
35002 MT_BUG_ON(mt, !mt_in_rcu(mt));
35016 mtree_store_range(mt, --start, ++end, xa_mk_value(100),
35025 mt_validate(mt);
35029 void run_check_rcu_slowread(struct maple_tree *mt, struct rcu_test_struct *vals)
35037 mt_set_in_rcu(mt);
35038 MT_BUG_ON(mt, !mt_in_rcu(mt));
35055 mtree_store(mt, index,
35066 MT_BUG_ON(mt, !vals->seen_entry2);
35067 MT_BUG_ON(mt, !vals->seen_entry3);
35068 MT_BUG_ON(mt, !vals->seen_both);
35070 static noinline void __init check_rcu_simulated(struct maple_tree *mt)
35076 MA_STATE(mas_writer, mt, 0, 0);
35077 MA_STATE(mas_reader, mt, target, target);
35081 mt_set_in_rcu(mt);
35093 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10));
35097 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val));
35110 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10));
35114 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val));
35127 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10));
35131 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10));
35144 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10));
35148 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val));
35160 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10));
35164 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val));
35176 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10));
35180 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val));
35201 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10));
35206 MT_BUG_ON(mt, mas_next(&mas_reader, ULONG_MAX) != xa_mk_value(val));
35220 MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10));
35225 MT_BUG_ON(mt, mas_prev(&mas_reader, 0) != xa_mk_value(val));
35231 static noinline void __init check_rcu_threaded(struct maple_tree *mt)
35241 mtree_store_range(mt, i*10, i*10 + 5,
35245 vals.mt = mt;
35256 run_check_rcu(mt, &vals);
35257 mtree_destroy(mt);
35259 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35261 mtree_store_range(mt, i*10, i*10 + 5,
35268 vals.mt = mt;
35277 run_check_rcu(mt, &vals);
35278 mtree_destroy(mt);
35281 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35282 run_check_rcu_slot_store(mt);
35283 mtree_destroy(mt);
35286 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35287 rcu_stress(mt, true);
35288 mtree_destroy(mt);
35291 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35292 rcu_stress(mt, false);
35293 mtree_destroy(mt);
35296 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35298 mtree_store_range(mt, i*10, i*10 + 5,
35305 vals.mt = mt;
35326 run_check_rcu_slowread(mt, &vals);
35380 static void check_dfs_preorder(struct maple_tree *mt)
35384 MA_STATE(mas, mt, 0, 0);
35391 check_seq(mt, max, false);
35396 MT_BUG_ON(mt, count != e);
35397 mtree_destroy(mt);
35399 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35405 check_seq(mt, max, false);
35411 MT_BUG_ON(mt, count != e);
35412 mtree_destroy(mt);
35414 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35417 check_rev_seq(mt, max, false);
35423 MT_BUG_ON(mt, count != e);
35424 mtree_destroy(mt);
35426 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35434 MT_BUG_ON(mt, mas_is_err(&mas));
35448 static noinline void __init check_prealloc(struct maple_tree *mt)
35455 MA_STATE(mas, mt, 10, 20);
35459 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35463 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35466 MT_BUG_ON(mt, allocated == 0);
35467 MT_BUG_ON(mt, allocated != 1 + height * 3);
35470 MT_BUG_ON(mt, allocated != 0);
35472 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35475 MT_BUG_ON(mt, allocated == 0);
35476 MT_BUG_ON(mt, allocated != 1 + height * 3);
35477 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35480 MT_BUG_ON(mt, allocated != 0);
35483 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35486 MT_BUG_ON(mt, allocated != 1 + height * 3);
35488 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
35491 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35494 MT_BUG_ON(mt, allocated != 0);
35496 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35499 MT_BUG_ON(mt, allocated != 1 + height * 3);
35501 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
35502 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35505 MT_BUG_ON(mt, allocated != 0);
35509 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35512 MT_BUG_ON(mt, allocated != 1 + height * 3);
35514 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
35516 MT_BUG_ON(mt, mas_allocated(&mas) != allocated);
35517 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35520 MT_BUG_ON(mt, allocated != 0);
35522 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35525 MT_BUG_ON(mt, allocated != 1 + height * 3);
35527 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
35531 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35533 MT_BUG_ON(mt, allocated != 0);
35535 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
35538 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35541 MT_BUG_ON(mt, allocated != 0);
35543 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
35547 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35550 MT_BUG_ON(mt, allocated != 1 + height * 2);
35552 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
35556 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0);
35559 MT_BUG_ON(mt, allocated != 0);
35564 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35567 MT_BUG_ON(mt, allocated == 0);
35568 MT_BUG_ON(mt, allocated != 1 + height * 3);
35570 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
35573 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0);
35576 MT_BUG_ON(mt, allocated != 0);
35581 static noinline void __init check_spanning_write(struct maple_tree *mt)
35584 MA_STATE(mas, mt, 1200, 2380);
35587 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35589 mtree_lock(mt);
35592 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35593 mtree_unlock(mt);
35594 mtree_destroy(mt);
35597 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35599 mtree_lock(mt);
35603 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35604 mtree_unlock(mt);
35605 mt_validate(mt);
35606 mtree_destroy(mt);
35609 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35611 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35614 mtree_lock(mt);
35617 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35618 mtree_unlock(mt);
35619 mtree_destroy(mt);
35622 mt_init_flags(mt, 0);
35624 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35627 mtree_lock(mt);
35630 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35631 mtree_unlock(mt);
35632 mtree_destroy(mt);
35635 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35637 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35640 mtree_lock(mt);
35643 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35644 mtree_unlock(mt);
35645 mtree_destroy(mt);
35648 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35650 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35653 mtree_lock(mt);
35656 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35657 mtree_unlock(mt);
35658 mtree_destroy(mt);
35661 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35663 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35666 mtree_lock(mt);
35669 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35670 mtree_unlock(mt);
35671 mtree_destroy(mt);
35677 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35679 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35682 mtree_lock(mt);
35685 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35686 mtree_unlock(mt);
35687 mtree_destroy(mt);
35693 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35695 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35697 mtree_lock(mt);
35700 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35701 mtree_unlock(mt);
35702 mtree_destroy(mt);
35705 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35707 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35708 mtree_lock(mt);
35719 MT_BUG_ON(mt, (mas_data_end(&mas)) != mt_slot_count(mas.node) - 1);
35722 mtree_unlock(mt);
35723 mtree_destroy(mt);
35726 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35728 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35730 mtree_lock(mt);
35733 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35734 mtree_unlock(mt);
35735 mtree_destroy(mt);
35737 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
35739 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35741 mtree_lock(mt);
35744 mtree_unlock(mt);
35749 static noinline void __init check_null_expand(struct maple_tree *mt)
35753 MA_STATE(mas, mt, 959, 959);
35756 mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
35763 MT_BUG_ON(mt, mtree_load(mt, 963) != NULL);
35764 MT_BUG_ON(mt, data_end != mas_data_end(&mas));
35772 MT_BUG_ON(mt, mtree_load(mt, 884) != NULL);
35773 MT_BUG_ON(mt, mtree_load(mt, 889) != NULL);
35775 MT_BUG_ON(mt, data_end != mas_data_end(&mas));
35784 MT_BUG_ON(mt, mtree_load(mt, 899) != NULL);
35785 MT_BUG_ON(mt, mtree_load(mt, 900) != NULL);
35786 MT_BUG_ON(mt, mtree_load(mt, 905) != NULL);
35787 MT_BUG_ON(mt, mtree_load(mt, 906) != NULL);
35789 MT_BUG_ON(mt, data_end - 2 != mas_data_end(&mas));
35798 MT_BUG_ON(mt, mtree_load(mt, 809) != NULL);
35799 MT_BUG_ON(mt, mtree_load(mt, 810) != NULL);
35800 MT_BUG_ON(mt, mtree_load(mt, 825) != NULL);
35801 MT_BUG_ON(mt, mtree_load(mt, 826) != NULL);
35803 MT_BUG_ON(mt, data_end - 4 != mas_data_end(&mas));
35810 static noinline void __init check_nomem(struct maple_tree *mt)
35812 MA_STATE(ms, mt, 1, 1);
35814 MT_BUG_ON(mt, !mtree_empty(mt));
35819 MT_BUG_ON(mt, mtree_insert(mt, 1, &ms, GFP_ATOMIC) != -ENOMEM);
35821 MT_BUG_ON(mt, mtree_insert(mt, 0, &ms, GFP_ATOMIC) != 0);
35831 mtree_lock(mt);
35833 MT_BUG_ON(mt, ms.node != MA_ERROR(-ENOMEM));
35835 MT_BUG_ON(mt, ms.node != MAS_START);
35836 mtree_unlock(mt);
35837 MT_BUG_ON(mt, mtree_insert(mt, 2, mt, GFP_KERNEL) != 0);
35838 mtree_lock(mt);
35841 mtree_unlock(mt);
35842 mtree_destroy(mt);
35845 static noinline void __init check_locky(struct maple_tree *mt)
35847 MA_STATE(ms, mt, 2, 2);
35848 MA_STATE(reader, mt, 2, 2);
35851 mt_set_in_rcu(mt);
35857 mt_clear_in_rcu(mt);