Lines Matching refs:mt
19 #define mt_dump(mt, fmt) do {} while (0)
20 #define mt_validate(mt) do {} while (0)
63 static int __init mtree_insert_index(struct maple_tree *mt,
66 return mtree_insert(mt, index, xa_mk_value(index & LONG_MAX), gfp);
69 static void __init mtree_erase_index(struct maple_tree *mt, unsigned long index)
71 MT_BUG_ON(mt, mtree_erase(mt, index) != xa_mk_value(index & LONG_MAX));
72 MT_BUG_ON(mt, mtree_load(mt, index) != NULL);
75 static int __init mtree_test_insert(struct maple_tree *mt, unsigned long index,
78 return mtree_insert(mt, index, ptr, GFP_KERNEL);
81 static int __init mtree_test_store_range(struct maple_tree *mt,
84 return mtree_store_range(mt, start, end, ptr, GFP_KERNEL);
87 static int __init mtree_test_store(struct maple_tree *mt, unsigned long start,
90 return mtree_test_store_range(mt, start, start, ptr);
93 static int __init mtree_test_insert_range(struct maple_tree *mt,
96 return mtree_insert_range(mt, start, end, ptr, GFP_KERNEL);
99 static void __init *mtree_test_load(struct maple_tree *mt, unsigned long index)
101 return mtree_load(mt, index);
104 static void __init *mtree_test_erase(struct maple_tree *mt, unsigned long index)
106 return mtree_erase(mt, index);
110 static noinline void __init check_mtree_alloc_range(struct maple_tree *mt,
118 ret = mtree_alloc_range(mt, &result, ptr, size, start, end,
120 MT_BUG_ON(mt, ret != eret);
124 MT_BUG_ON(mt, result != expected);
127 static noinline void __init check_mtree_alloc_rrange(struct maple_tree *mt,
135 ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end,
137 MT_BUG_ON(mt, ret != eret);
141 MT_BUG_ON(mt, result != expected);
145 static noinline void __init check_load(struct maple_tree *mt,
148 void *ret = mtree_test_load(mt, index);
152 MT_BUG_ON(mt, ret != ptr);
155 static noinline void __init check_store_range(struct maple_tree *mt,
161 ret = mtree_test_store_range(mt, start, end, ptr);
162 MT_BUG_ON(mt, ret != expected);
168 check_load(mt, i, ptr);
171 static noinline void __init check_insert_range(struct maple_tree *mt,
177 ret = mtree_test_insert_range(mt, start, end, ptr);
178 MT_BUG_ON(mt, ret != expected);
184 check_load(mt, i, ptr);
187 static noinline void __init check_insert(struct maple_tree *mt,
192 ret = mtree_test_insert(mt, index, ptr);
193 MT_BUG_ON(mt, ret != 0);
196 static noinline void __init check_dup_insert(struct maple_tree *mt,
201 ret = mtree_test_insert(mt, index, ptr);
202 MT_BUG_ON(mt, ret != -EEXIST);
206 static noinline void __init check_index_load(struct maple_tree *mt,
209 return check_load(mt, index, xa_mk_value(index & LONG_MAX));
227 static noinline void __init check_rev_seq(struct maple_tree *mt,
232 MT_BUG_ON(mt, !mtree_empty(mt));
236 MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL));
238 check_index_load(mt, j);
240 check_load(mt, i - 1, NULL);
241 mt_set_in_rcu(mt);
242 MT_BUG_ON(mt, !mt_height(mt));
243 mt_clear_in_rcu(mt);
244 MT_BUG_ON(mt, !mt_height(mt));
247 check_load(mt, max + 1, NULL);
252 mt_dump(mt, mt_dump_dec);
260 static noinline void __init check_seq(struct maple_tree *mt, unsigned long max,
265 MT_BUG_ON(mt, !mtree_empty(mt));
269 MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL));
271 check_index_load(mt, j);
274 MT_BUG_ON(mt, !mt_height(mt));
275 check_load(mt, i + 1, NULL);
281 mt_dump(mt, mt_dump_dec);
289 static noinline void __init check_lb_not_empty(struct maple_tree *mt)
297 check_insert(mt, i, (void *) i);
299 check_load(mt, j-1, NULL);
300 check_load(mt, j, (void *) j);
301 check_load(mt, j+1, NULL);
305 mtree_destroy(mt);
308 static noinline void __init check_lower_bound_split(struct maple_tree *mt)
310 MT_BUG_ON(mt, !mtree_empty(mt));
311 check_lb_not_empty(mt);
314 static noinline void __init check_upper_bound_split(struct maple_tree *mt)
319 MT_BUG_ON(mt, !mtree_empty(mt));
328 check_insert(mt, i, (void *) i);
330 check_load(mt, j-1, NULL);
331 check_load(mt, j, (void *) j);
332 check_load(mt, j+1, NULL);
336 mtree_destroy(mt);
339 static noinline void __init check_mid_split(struct maple_tree *mt)
343 check_insert(mt, huge, (void *) huge);
344 check_insert(mt, 0, xa_mk_value(0));
345 check_lb_not_empty(mt);
348 static noinline void __init check_rev_find(struct maple_tree *mt)
352 MA_STATE(mas, mt, 0, 0);
355 mtree_store_range(mt, i*10, i*10 + 5,
361 MT_BUG_ON(mt, val != xa_mk_value(100));
363 MT_BUG_ON(mt, val != NULL);
367 MT_BUG_ON(mt, val != NULL);
371 MT_BUG_ON(mt, val != xa_mk_value(100));
373 MT_BUG_ON(mt, val != xa_mk_value(99));
377 MT_BUG_ON(mt, val != xa_mk_value(2));
379 MT_BUG_ON(mt, val != xa_mk_value(1));
381 MT_BUG_ON(mt, val != xa_mk_value(0));
383 MT_BUG_ON(mt, val != NULL);
387 static noinline void __init check_find(struct maple_tree *mt)
396 MA_STATE(mas, mt, 0, 0);
399 MT_BUG_ON(mt, mtree_insert_index(mt, val++, GFP_KERNEL));
415 MT_BUG_ON(mt, mtree_insert_index(mt, val, GFP_KERNEL));
417 MT_BUG_ON(mt, mtree_insert(mt, val,
428 MT_BUG_ON(mt, xa_mk_value(val) != entry);
430 MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
444 MT_BUG_ON(mt, xa_mk_value(val) != entry);
446 MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
460 MT_BUG_ON(mt, xa_mk_value(val) != entry);
462 MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
476 mt_for_each(mt, entry, index, max) {
477 MT_BUG_ON(mt, xa_mk_value(val) != entry);
489 MT_BUG_ON(mt, mtree_insert_index(mt, ULONG_MAX, GFP_KERNEL));
490 mt_for_each(mt, entry, index, ULONG_MAX) {
492 MT_BUG_ON(mt, entry != xa_mk_value(LONG_MAX));
494 MT_BUG_ON(mt, xa_mk_value(val) != entry);
508 MT_BUG_ON(mt, max > 25);
510 mtree_erase_index(mt, ULONG_MAX);
514 entry = mt_find(mt, &index, 512);
515 MT_BUG_ON(mt, xa_mk_value(256) != entry);
519 entry = mt_find(mt, &index, 20);
520 MT_BUG_ON(mt, entry != NULL);
525 MT_BUG_ON(mt, mtree_insert_index(mt, ULONG_MAX, GFP_KERNEL));
532 MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
534 MT_BUG_ON(mt, entry != xa_mk_value(LONG_MAX));
536 MT_BUG_ON(mt, xa_mk_value(val) != entry);
586 MT_BUG_ON(mt, entry != entry2);
587 MT_BUG_ON(mt, index != mas.index);
588 MT_BUG_ON(mt, last != mas.last);
595 MT_BUG_ON(mt, entry != entry2);
598 MT_BUG_ON(mt, mas_prev(&mas, 0) != NULL);
601 mtree_destroy(mt);
604 static noinline void __init check_find_2(struct maple_tree *mt)
609 MA_STATE(mas, mt, 0, 0);
612 MT_BUG_ON(mt, true);
616 mtree_insert_index(mt, i, GFP_KERNEL);
621 MT_BUG_ON(mt, entry != xa_mk_value(j));
625 MT_BUG_ON(mt, j != i + 1);
629 mtree_erase_index(mt, i);
637 MT_BUG_ON(mt, entry != xa_mk_value(j));
641 MT_BUG_ON(mt, j != 256);
644 /*MT_BUG_ON(mt, !mtree_empty(mt)); */
649 static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
756 MA_STATE(mas, mt, 0, 0);
758 mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY,
768 check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1,
770 mt_validate(mt);
781 MT_BUG_ON(mt, mas_empty_area_rev(&mas, min,
789 MT_BUG_ON(mt, mas.last + 1 != (holes[i+1] >> 12));
790 MT_BUG_ON(mt, mas.index != (holes[i+1] >> 12) - (holes[i+2] >> 12));
804 check_mtree_alloc_rrange(mt,
811 mt_validate(mt);
815 mtree_erase(mt, 34148798727); /* create a deleted range. */
816 mtree_erase(mt, 34148798725);
817 check_mtree_alloc_rrange(mt, 0, 34359052173, 210253414,
818 34148798725, 0, mt);
820 mtree_destroy(mt);
823 static noinline void __init check_alloc_range(struct maple_tree *mt)
931 MA_STATE(mas, mt, 0, 0);
933 mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY,
940 mt_dump(mt, mt_dump_hex);
942 check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1,
944 mt_validate(mt);
957 MT_BUG_ON(mt, mas_empty_area(&mas, min >> 12,
960 MT_BUG_ON(mt, mas.index != holes[i] >> 12);
972 check_mtree_alloc_range(mt,
979 mt_validate(mt);
981 mt_dump(mt, mt_dump_hex);
985 mtree_destroy(mt);
989 static noinline void __init check_ranges(struct maple_tree *mt)
1002 MT_BUG_ON(mt, !mtree_empty(mt));
1003 check_insert_range(mt, r[0], r[1], xa_mk_value(r[0]), 0);
1004 check_insert_range(mt, r[2], r[3], xa_mk_value(r[2]), 0);
1005 check_insert_range(mt, r[4], r[5], xa_mk_value(r[4]), -EEXIST);
1006 MT_BUG_ON(mt, !mt_height(mt));
1008 check_store_range(mt, r[4], r[5], xa_mk_value(r[4]), 0);
1009 check_store_range(mt, r[6], r[7], xa_mk_value(r[6]), 0);
1010 check_store_range(mt, r[8], r[9], xa_mk_value(r[8]), 0);
1011 MT_BUG_ON(mt, !mt_height(mt));
1012 mtree_destroy(mt);
1013 MT_BUG_ON(mt, mt_height(mt));
1015 check_seq(mt, 50, false);
1017 check_store_range(mt, 5, 47, xa_mk_value(47), 0);
1018 MT_BUG_ON(mt, !mt_height(mt));
1019 mtree_destroy(mt);
1022 check_seq(mt, 100, false);
1025 check_store_range(mt, r[10], r[11], xa_mk_value(r[10]), 0);
1026 MT_BUG_ON(mt, !mt_height(mt));
1027 mtree_destroy(mt);
1030 check_seq(mt, 200, false);
1032 check_store_range(mt, r[10], r[11], xa_mk_value(r[10]), 0);
1033 MT_BUG_ON(mt, !mt_height(mt));
1034 mtree_destroy(mt);
1036 check_seq(mt, 30, false);
1037 check_store_range(mt, 6, 18, xa_mk_value(6), 0);
1038 MT_BUG_ON(mt, !mt_height(mt));
1039 mtree_destroy(mt);
1043 check_seq(mt, 400, false);
1046 check_store_range(mt, r[12], r[13], xa_mk_value(r[12]), 0);
1048 mtree_test_erase(mt, 140);
1049 mtree_test_erase(mt, 141);
1050 mtree_test_erase(mt, 142);
1051 mtree_test_erase(mt, 143);
1052 mtree_test_erase(mt, 130);
1053 mtree_test_erase(mt, 131);
1054 mtree_test_erase(mt, 132);
1055 mtree_test_erase(mt, 133);
1056 mtree_test_erase(mt, 134);
1057 mtree_test_erase(mt, 135);
1058 check_load(mt, r[12], xa_mk_value(r[12]));
1059 check_load(mt, r[13], xa_mk_value(r[12]));
1060 check_load(mt, r[13] - 1, xa_mk_value(r[12]));
1061 check_load(mt, r[13] + 1, xa_mk_value(r[13] + 1));
1062 check_load(mt, 135, NULL);
1063 check_load(mt, 140, NULL);
1065 MT_BUG_ON(mt, !mt_height(mt));
1066 mtree_destroy(mt);
1072 check_seq(mt, 400, false);
1073 check_store_range(mt, 353, 361, xa_mk_value(353), 0);
1074 check_store_range(mt, 347, 352, xa_mk_value(347), 0);
1076 check_load(mt, 346, xa_mk_value(346));
1078 check_load(mt, i, xa_mk_value(347));
1080 check_load(mt, i, xa_mk_value(353));
1081 check_load(mt, 362, xa_mk_value(362));
1083 MT_BUG_ON(mt, !mt_height(mt));
1084 mtree_destroy(mt);
1087 check_seq(mt, 400, false);
1088 check_store_range(mt, 352, 364, NULL, 0);
1089 check_store_range(mt, 351, 363, xa_mk_value(352), 0);
1090 check_load(mt, 350, xa_mk_value(350));
1091 check_load(mt, 351, xa_mk_value(352));
1093 check_load(mt, i, xa_mk_value(352));
1094 check_load(mt, 364, NULL);
1095 check_load(mt, 365, xa_mk_value(365));
1097 MT_BUG_ON(mt, !mt_height(mt));
1098 mtree_destroy(mt);
1101 check_seq(mt, 400, false);
1102 check_store_range(mt, 352, 364, NULL, 0);
1103 check_store_range(mt, 351, 364, xa_mk_value(352), 0);
1104 check_load(mt, 350, xa_mk_value(350));
1105 check_load(mt, 351, xa_mk_value(352));
1107 check_load(mt, i, xa_mk_value(352));
1108 check_load(mt, 365, xa_mk_value(365));
1110 MT_BUG_ON(mt, !mt_height(mt));
1111 mtree_destroy(mt);
1115 check_seq(mt, 400, false);
1116 check_store_range(mt, 362, 367, xa_mk_value(362), 0);
1117 check_store_range(mt, 353, 361, xa_mk_value(353), 0);
1119 mt_validate(mt);
1120 MT_BUG_ON(mt, !mt_height(mt));
1121 mtree_destroy(mt);
1143 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1145 check_store_range(mt, 2400, 2400, xa_mk_value(2400), 0);
1146 check_store_range(mt, 2411, 2411, xa_mk_value(2411), 0);
1147 check_store_range(mt, 2412, 2412, xa_mk_value(2412), 0);
1148 check_store_range(mt, 2396, 2400, xa_mk_value(4052020), 0);
1149 check_store_range(mt, 2402, 2402, xa_mk_value(2402), 0);
1150 mtree_destroy(mt);
1157 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1159 check_store_range(mt, 2422, 2422, xa_mk_value(2422), 0);
1160 check_store_range(mt, 2424, 2424, xa_mk_value(2424), 0);
1161 check_store_range(mt, 2425, 2425, xa_mk_value(2), 0);
1162 check_store_range(mt, 2460, 2470, NULL, 0);
1163 check_store_range(mt, 2435, 2460, xa_mk_value(2435), 0);
1164 check_store_range(mt, 2461, 2470, xa_mk_value(2461), 0);
1166 MT_BUG_ON(mt, !mt_height(mt));
1167 mtree_destroy(mt);
1170 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1176 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1183 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1190 MT_BUG_ON(mt, mtree_test_store_range(mt, val, ULONG_MAX,
1198 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1205 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1215 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1222 mt_set_in_rcu(mt);
1226 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1229 MT_BUG_ON(mt, !mt_height(mt));
1230 mt_validate(mt);
1232 mtree_destroy(mt);
1235 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1240 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1242 check_store_range(mt, 161, 161, xa_mk_value(161), 0);
1243 check_store_range(mt, 162, 162, xa_mk_value(162), 0);
1244 check_store_range(mt, 163, 163, xa_mk_value(163), 0);
1245 check_store_range(mt, 240, 249, NULL, 0);
1246 mtree_erase(mt, 200);
1247 mtree_erase(mt, 210);
1248 mtree_erase(mt, 220);
1249 mtree_erase(mt, 230);
1251 MT_BUG_ON(mt, !mt_height(mt));
1252 mtree_destroy(mt);
1254 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1258 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1260 check_store_range(mt, 4600, 4959, xa_mk_value(1), 0);
1261 mt_validate(mt);
1262 MT_BUG_ON(mt, !mt_height(mt));
1263 mtree_destroy(mt);
1265 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1269 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1271 check_store_range(mt, 4811, 4811, xa_mk_value(4811), 0);
1272 check_store_range(mt, 4812, 4812, xa_mk_value(4812), 0);
1273 check_store_range(mt, 4861, 4861, xa_mk_value(4861), 0);
1274 check_store_range(mt, 4862, 4862, xa_mk_value(4862), 0);
1275 check_store_range(mt, 4842, 4849, NULL, 0);
1276 mt_validate(mt);
1277 MT_BUG_ON(mt, !mt_height(mt));
1278 mtree_destroy(mt);
1280 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1284 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1285 MT_BUG_ON(mt, mt_height(mt) >= 4);
1289 check_store_range(mt, 11450 + i, 11450 + i + 1, NULL, 0);
1291 check_store_range(mt, 11770 + i, 11770 + i + 1, NULL, 0);
1293 MT_BUG_ON(mt, mt_height(mt) >= 4);
1295 check_store_range(mt, 11700 + i, 11700 + i + 1, NULL, 0);
1297 MT_BUG_ON(mt, mt_height(mt) < 4);
1298 mtree_destroy(mt);
1301 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1305 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1306 MT_BUG_ON(mt, mt_height(mt) >= 4);
1310 check_store_range(mt, 7800 + i, 7800 + i + 1, NULL, 0);
1313 check_store_range(mt, 8185 + i, 8185 + i + 1,
1315 MT_BUG_ON(mt, mt_height(mt) >= 4);
1317 check_store_range(mt, 8184, 8184, xa_mk_value(8184), 0);
1319 MT_BUG_ON(mt, mt_height(mt) != 4);
1322 static noinline void __init check_next_entry(struct maple_tree *mt)
1326 MA_STATE(mas, mt, i, i);
1328 MT_BUG_ON(mt, !mtree_empty(mt));
1330 check_seq(mt, limit, false);
1334 MT_BUG_ON(mt, mas_walk(&mas) != xa_mk_value(i++));
1338 MT_BUG_ON(mt, entry != NULL);
1340 MT_BUG_ON(mt, xa_mk_value(i) != entry);
1343 mtree_destroy(mt);
1346 static noinline void __init check_prev_entry(struct maple_tree *mt)
1352 MA_STATE(mas, mt, index, index);
1354 MT_BUG_ON(mt, !mtree_empty(mt));
1355 check_seq(mt, 30, false);
1359 MT_BUG_ON(mt, value != xa_mk_value(index));
1361 MT_BUG_ON(mt, value != xa_mk_value(index - 1));
1363 mtree_destroy(mt);
1366 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1375 MT_BUG_ON(mt, value != xa_mk_value(2));
1378 MT_BUG_ON(mt, value != NULL);
1382 MT_BUG_ON(mt, value != xa_mk_value(8));
1385 MT_BUG_ON(mt, value != NULL);
1390 static noinline void __init check_root_expand(struct maple_tree *mt)
1392 MA_STATE(mas, mt, 0, 0);
1399 MT_BUG_ON(mt, mas.index != 0);
1400 MT_BUG_ON(mt, ptr != NULL);
1401 MT_BUG_ON(mt, mas.index != 0);
1402 MT_BUG_ON(mt, mas.last != ULONG_MAX);
1410 MT_BUG_ON(mt, ptr != NULL);
1414 MT_BUG_ON(mt, ptr != &check_prev_entry);
1418 MT_BUG_ON(mt, ptr != NULL);
1420 mtree_destroy(mt);
1423 mt_init_flags(mt, 0);
1432 MT_BUG_ON(mt, ptr != NULL);
1433 MT_BUG_ON(mt, mas.index != 1);
1434 MT_BUG_ON(mt, mas.last != ULONG_MAX);
1438 MT_BUG_ON(mt, ptr != &check_prev_entry);
1439 MT_BUG_ON(mt, mas.last != 0);
1441 mtree_destroy(mt);
1443 mt_init_flags(mt, 0);
1450 MT_BUG_ON(mt, ptr != NULL);
1451 MT_BUG_ON(mt, (mas.index != 1) && (mas.last != ULONG_MAX));
1455 MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0));
1456 MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 1UL));
1460 mtree_destroy(mt);
1462 mt_init_flags(mt, 0);
1468 MT_BUG_ON(mt, ptr != NULL);
1469 MT_BUG_ON(mt, (mas.index != ULONG_MAX) && (mas.last != ULONG_MAX));
1473 MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0));
1474 MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 2UL));
1480 static noinline void __init check_gap_combining(struct maple_tree *mt)
1526 MA_STATE(mas, mt, 0, 0);
1535 MT_BUG_ON(mt, !mtree_empty(mt));
1536 check_seq(mt, singletons, false); /* create 100 singletons. */
1539 mtree_test_erase(mt, seq100[2]);
1540 check_load(mt, seq100[2], NULL);
1541 mtree_test_erase(mt, seq100[1]);
1542 check_load(mt, seq100[1], NULL);
1546 MT_BUG_ON(mt, entry != xa_mk_value(index));
1550 MT_BUG_ON(mt, entry != xa_mk_value(index + 4));
1552 MT_BUG_ON(mt, mn1 == mn2); /* test the test. */
1560 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[3], seq100[4],
1562 MT_BUG_ON(mt, mas.index != index + 1);
1565 mtree_test_erase(mt, seq100[6]);
1566 check_load(mt, seq100[6], NULL);
1567 mtree_test_erase(mt, seq100[7]);
1568 check_load(mt, seq100[7], NULL);
1569 mtree_test_erase(mt, seq100[8]);
1577 MT_BUG_ON(mt, entry != xa_mk_value(index));
1580 MT_BUG_ON(mt, entry != xa_mk_value(index + 4));
1583 MT_BUG_ON(mt, mn1 == mn2); /* test the next entry is in the next node. */
1590 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[10], seq100[11],
1592 MT_BUG_ON(mt, mas.index != seq100[6]);
1596 mtree_store(mt, seq100[13], NULL, GFP_KERNEL);
1597 check_load(mt, seq100[13], NULL);
1598 check_load(mt, seq100[14], xa_mk_value(seq100[14]));
1599 mtree_store(mt, seq100[14], NULL, GFP_KERNEL);
1600 check_load(mt, seq100[13], NULL);
1601 check_load(mt, seq100[14], NULL);
1605 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[15],
1607 MT_BUG_ON(mt, mas.index != seq100[13]);
1608 mt_validate(mt);
1616 mtree_test_store_range(mt, seq100[18], seq100[14], NULL);
1617 mtree_test_erase(mt, seq100[15]);
1620 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[19],
1623 MT_BUG_ON(mt, mas.index != seq100[18]);
1624 mt_validate(mt);
1625 mtree_destroy(mt);
1628 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1629 check_seq(mt, 2000, false);
1631 mtree_test_erase(mt, seq2000[0]);
1632 mtree_test_erase(mt, seq2000[1]);
1637 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq2000[2], seq2000[3],
1639 MT_BUG_ON(mt, mas.index != seq2000[1]);
1641 mt_validate(mt);
1642 mtree_destroy(mt);
1646 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1647 check_seq(mt, 400, false);
1648 mtree_test_store_range(mt, seq400[0], seq400[1], NULL);
1650 mtree_destroy(mt);
1652 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1653 check_seq(mt, 400, false);
1655 mtree_test_store_range(mt, seq400[2], seq400[9],
1657 mtree_test_store_range(mt, seq400[3], seq400[9],
1659 mtree_test_store_range(mt, seq400[4], seq400[9],
1661 mtree_test_store_range(mt, seq400[5], seq400[9],
1663 mtree_test_store_range(mt, seq400[0], seq400[9],
1665 mtree_test_store_range(mt, seq400[6], seq400[9],
1667 mtree_test_store_range(mt, seq400[7], seq400[9],
1669 mtree_test_store_range(mt, seq400[8], seq400[9],
1671 mtree_test_store_range(mt, seq400[10], seq400[11],
1673 mt_validate(mt);
1675 mtree_destroy(mt);
1677 static noinline void __init check_node_overwrite(struct maple_tree *mt)
1682 mtree_test_store_range(mt, i*100, i*100 + 50, xa_mk_value(i*100));
1684 mtree_test_store_range(mt, 319951, 367950, NULL);
1685 /*mt_dump(mt, mt_dump_dec); */
1686 mt_validate(mt);
1690 static noinline void __init bench_slot_store(struct maple_tree *mt)
1695 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1698 mtree_store_range(mt, brk, brk, NULL, GFP_KERNEL);
1699 mtree_store_range(mt, brk_start, brk, xa_mk_value(brk),
1706 static noinline void __init bench_node_store(struct maple_tree *mt)
1711 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1714 mtree_store_range(mt, overwrite, overwrite + 15,
1725 static noinline void __init bench_awalk(struct maple_tree *mt)
1728 MA_STATE(mas, mt, 1470, 1470);
1731 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1733 mtree_store_range(mt, 1470, 1475, NULL, GFP_KERNEL);
1742 static noinline void __init bench_walk(struct maple_tree *mt)
1745 MA_STATE(mas, mt, 1470, 1470);
1748 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1759 static noinline void __init bench_load(struct maple_tree *mt)
1764 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1767 mtree_load(mt, 1470);
1772 static noinline void __init bench_mt_for_each(struct maple_tree *mt)
1779 mtree_store_range(mt, i, i + 4, xa_mk_value(i), GFP_KERNEL);
1784 mt_for_each(mt, entry, index, max) {
1785 MT_BUG_ON(mt, entry != xa_mk_value(j));
1796 static noinline void __init bench_mas_for_each(struct maple_tree *mt)
1801 MA_STATE(mas, mt, 0, 0);
1808 mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
1816 MT_BUG_ON(mt, entry != xa_mk_value(j));
1826 static noinline void __init bench_mas_prev(struct maple_tree *mt)
1831 MA_STATE(mas, mt, 0, 0);
1838 mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
1847 MT_BUG_ON(mt, entry != xa_mk_value(j));
1858 struct maple_tree mt, newmt;
1861 MA_STATE(mas, &mt, 0, 0);
1868 mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
1869 mt_set_external_lock(&mt, &mt_lock);
1881 ret = __mt_dup(&mt, &newmt, GFP_KERNEL);
1895 __mt_destroy(&mt);
1900 static noinline void __init check_iteration(struct maple_tree *mt)
1904 MA_STATE(mas, mt, 0, 0);
1907 mtree_store_range(mt, i * 10, i * 10 + 9,
1915 MT_BUG_ON(mt, mas.index != i * 10);
1916 MT_BUG_ON(mt, mas.last != i * 10 + 9);
1927 MT_BUG_ON(mt, val != xa_mk_value(i));
1932 MT_BUG_ON(mt, mas.index != i * 10);
1933 MT_BUG_ON(mt, mas.last != i * 10 + 9);
1944 MT_BUG_ON(mt, val != xa_mk_value(i));
1949 MT_BUG_ON(mt, mas.index != i * 10);
1950 MT_BUG_ON(mt, mas.last != i * 10 + 9);
1961 MT_BUG_ON(mt, val != xa_mk_value(76));
1967 static noinline void __init check_mas_store_gfp(struct maple_tree *mt)
1973 MA_STATE(mas, mt, 0, 0);
1974 MA_STATE(newmas, mt, 0, 0);
1977 mtree_store_range(mt, i*10, i*10 + 5,
2002 struct maple_tree mt, newmt;
2005 MA_STATE(mas, &mt, 0, 0);
2012 mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
2013 mt_set_external_lock(&mt, &mt_lock);
2027 ret = __mt_dup(&mt, &newmt, GFP_KERNEL);
2043 __mt_destroy(&mt);
2048 static noinline void __init next_prev_test(struct maple_tree *mt)
2052 MA_STATE(mas, mt, 0, 0);
2072 mtree_store_range(mt, i*10, i*10 + 5,
2105 MT_BUG_ON(mt, val != NULL);
2108 MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
2109 MT_BUG_ON(mt, mas.index != 690);
2110 MT_BUG_ON(mt, mas.last != 695);
2113 MT_BUG_ON(mt, val != xa_mk_value(680 / 10));
2114 MT_BUG_ON(mt, mas.index != 680);
2115 MT_BUG_ON(mt, mas.last != 685);
2118 MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
2119 MT_BUG_ON(mt, mas.index != 690);
2120 MT_BUG_ON(mt, mas.last != 695);
2123 MT_BUG_ON(mt, val != xa_mk_value(700 / 10));
2124 MT_BUG_ON(mt, mas.index != 700);
2125 MT_BUG_ON(mt, mas.last != 705);
2130 MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
2131 MT_BUG_ON(mt, mas.index != 70);
2132 MT_BUG_ON(mt, mas.last != 75);
2135 MT_BUG_ON(mt, val != xa_mk_value(80 / 10));
2136 MT_BUG_ON(mt, mas.index != 80);
2137 MT_BUG_ON(mt, mas.last != 85);
2140 MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
2141 MT_BUG_ON(mt, mas.index != 70);
2142 MT_BUG_ON(mt, mas.last != 75);
2148 MT_BUG_ON(mt, val != NULL);
2150 MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
2151 MT_BUG_ON(mt, mas.index != level2[2]);
2152 MT_BUG_ON(mt, mas.last != level2[3]);
2156 MT_BUG_ON(mt, val != xa_mk_value(level2[4] / 10));
2157 MT_BUG_ON(mt, mas.index != level2[4]);
2158 MT_BUG_ON(mt, mas.last != level2[5]);
2159 MT_BUG_ON(mt, mn == mas.node);
2162 MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
2163 MT_BUG_ON(mt, mas.index != level2[2]);
2164 MT_BUG_ON(mt, mas.last != level2[3]);
2169 MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
2170 MT_BUG_ON(mt, mas.index != (nr_entries * 10));
2171 MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
2174 MT_BUG_ON(mt, val != NULL);
2175 MT_BUG_ON(mt, mas.index != last_index);
2176 MT_BUG_ON(mt, mas.last != ULONG_MAX);
2179 MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
2180 MT_BUG_ON(mt, mas.index != (nr_entries * 10));
2181 MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
2187 MT_BUG_ON(mt, val != xa_mk_value(1));
2188 MT_BUG_ON(mt, mas.index != 10);
2189 MT_BUG_ON(mt, mas.last != 15);
2192 MT_BUG_ON(mt, val != xa_mk_value(0));
2193 MT_BUG_ON(mt, mas.index != 0);
2194 MT_BUG_ON(mt, mas.last != 5);
2197 MT_BUG_ON(mt, val != NULL);
2198 MT_BUG_ON(mt, mas.index != 0);
2199 MT_BUG_ON(mt, mas.last != 5);
2200 MT_BUG_ON(mt, !mas_is_underflow(&mas));
2210 MT_BUG_ON(mt, val != NULL);
2211 MT_BUG_ON(mt, mas.index != 0);
2212 MT_BUG_ON(mt, mas.last != 9);
2215 mtree_destroy(mt);
2217 mt_init(mt);
2218 mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL);
2219 mtree_store_range(mt, 5, 5, xa_mk_value(5), GFP_KERNEL);
2223 MT_BUG_ON(mt, val != NULL);
2230 static noinline void __init check_spanning_relatives(struct maple_tree *mt)
2236 mtree_store_range(mt, i*10, i*10 + 5,
2240 mtree_store_range(mt, 9365, 9955, NULL, GFP_KERNEL);
2243 static noinline void __init check_fuzzer(struct maple_tree *mt)
2250 mtree_test_insert(mt, 88, (void *)0xb1);
2251 mtree_test_insert(mt, 84, (void *)0xa9);
2252 mtree_test_insert(mt, 2, (void *)0x5);
2253 mtree_test_insert(mt, 4, (void *)0x9);
2254 mtree_test_insert(mt, 14, (void *)0x1d);
2255 mtree_test_insert(mt, 7, (void *)0xf);
2256 mtree_test_insert(mt, 12, (void *)0x19);
2257 mtree_test_insert(mt, 18, (void *)0x25);
2258 mtree_test_store_range(mt, 8, 18, (void *)0x11);
2259 mtree_destroy(mt);
2266 mt_init_flags(mt, 0);
2267 mtree_test_store(mt, 87, (void *)0xaf);
2268 mtree_test_store(mt, 0, (void *)0x1);
2269 mtree_test_load(mt, 4);
2270 mtree_test_insert(mt, 4, (void *)0x9);
2271 mtree_test_store(mt, 8, (void *)0x11);
2272 mtree_test_store(mt, 44, (void *)0x59);
2273 mtree_test_store(mt, 68, (void *)0x89);
2274 mtree_test_store(mt, 2, (void *)0x5);
2275 mtree_test_insert(mt, 43, (void *)0x57);
2276 mtree_test_insert(mt, 24, (void *)0x31);
2277 mtree_test_insert(mt, 844, (void *)0x699);
2278 mtree_test_store(mt, 84, (void *)0xa9);
2279 mtree_test_store(mt, 4, (void *)0x9);
2280 mtree_test_erase(mt, 4);
2281 mtree_test_load(mt, 5);
2282 mtree_test_erase(mt, 0);
2283 mtree_destroy(mt);
2290 mt_init_flags(mt, 0);
2291 mtree_test_store_range(mt, 0, ULONG_MAX, (void *)0x1);
2292 mtree_test_store(mt, 4, (void *)0x9);
2293 mtree_test_erase(mt, 5);
2294 mtree_test_erase(mt, 0);
2295 mtree_test_erase(mt, 4);
2296 mtree_test_store(mt, 5, (void *)0xb);
2297 mtree_test_erase(mt, 5);
2298 mtree_test_store(mt, 5, (void *)0xb);
2299 mtree_test_erase(mt, 5);
2300 mtree_test_erase(mt, 4);
2301 mtree_test_store(mt, 4, (void *)0x9);
2302 mtree_test_store(mt, 444, (void *)0x379);
2303 mtree_test_store(mt, 0, (void *)0x1);
2304 mtree_test_load(mt, 0);
2305 mtree_test_store(mt, 5, (void *)0xb);
2306 mtree_test_erase(mt, 0);
2307 mtree_destroy(mt);
2315 mt_init_flags(mt, 0);
2316 mtree_test_insert(mt, 261, (void *)0x20b);
2317 mtree_test_store(mt, 516, (void *)0x409);
2318 mtree_test_store(mt, 6, (void *)0xd);
2319 mtree_test_insert(mt, 5, (void *)0xb);
2320 mtree_test_insert(mt, 1256, (void *)0x9d1);
2321 mtree_test_store(mt, 4, (void *)0x9);
2322 mtree_test_erase(mt, 1);
2323 mtree_test_store(mt, 56, (void *)0x71);
2324 mtree_test_insert(mt, 1, (void *)0x3);
2325 mtree_test_store(mt, 24, (void *)0x31);
2326 mtree_test_erase(mt, 1);
2327 mtree_test_insert(mt, 2263, (void *)0x11af);
2328 mtree_test_insert(mt, 446, (void *)0x37d);
2329 mtree_test_store_range(mt, 6, 45, (void *)0xd);
2330 mtree_test_store_range(mt, 3, 446, (void *)0x7);
2331 mtree_destroy(mt);
2337 mt_init_flags(mt, 0);
2338 mtree_test_store(mt, 48, (void *)0x61);
2339 mtree_test_store(mt, 3, (void *)0x7);
2340 mtree_test_load(mt, 0);
2341 mtree_test_store(mt, 88, (void *)0xb1);
2342 mtree_test_store(mt, 81, (void *)0xa3);
2343 mtree_test_insert(mt, 0, (void *)0x1);
2344 mtree_test_insert(mt, 8, (void *)0x11);
2345 mtree_test_insert(mt, 4, (void *)0x9);
2346 mtree_test_insert(mt, 2480, (void *)0x1361);
2347 mtree_test_insert(mt, ULONG_MAX,
2349 mtree_test_erase(mt, ULONG_MAX);
2350 mtree_destroy(mt);
2359 mt_init_flags(mt, 0);
2360 mtree_test_erase(mt, 3);
2361 mtree_test_insert(mt, 22, (void *)0x2d);
2362 mtree_test_insert(mt, 15, (void *)0x1f);
2363 mtree_test_load(mt, 2);
2364 mtree_test_insert(mt, 1, (void *)0x3);
2365 mtree_test_insert(mt, 1, (void *)0x3);
2366 mtree_test_insert(mt, 5, (void *)0xb);
2367 mtree_test_erase(mt, 1);
2368 mtree_test_insert(mt, 1, (void *)0x3);
2369 mtree_test_insert(mt, 4, (void *)0x9);
2370 mtree_test_insert(mt, 1, (void *)0x3);
2371 mtree_test_erase(mt, 1);
2372 mtree_test_insert(mt, 2, (void *)0x5);
2373 mtree_test_insert(mt, 1, (void *)0x3);
2374 mtree_test_erase(mt, 3);
2375 mtree_test_insert(mt, 22, (void *)0x2d);
2376 mtree_test_insert(mt, 15, (void *)0x1f);
2377 mtree_test_insert(mt, 2, (void *)0x5);
2378 mtree_test_insert(mt, 1, (void *)0x3);
2379 mtree_test_insert(mt, 8, (void *)0x11);
2380 mtree_test_load(mt, 2);
2381 mtree_test_insert(mt, 1, (void *)0x3);
2382 mtree_test_insert(mt, 1, (void *)0x3);
2383 mtree_test_store(mt, 1, (void *)0x3);
2384 mtree_test_insert(mt, 5, (void *)0xb);
2385 mtree_test_erase(mt, 1);
2386 mtree_test_insert(mt, 1, (void *)0x3);
2387 mtree_test_insert(mt, 4, (void *)0x9);
2388 mtree_test_insert(mt, 1, (void *)0x3);
2389 mtree_test_erase(mt, 1);
2390 mtree_test_insert(mt, 2, (void *)0x5);
2391 mtree_test_insert(mt, 1, (void *)0x3);
2392 mtree_test_erase(mt, 3);
2393 mtree_test_insert(mt, 22, (void *)0x2d);
2394 mtree_test_insert(mt, 15, (void *)0x1f);
2395 mtree_test_insert(mt, 2, (void *)0x5);
2396 mtree_test_insert(mt, 1, (void *)0x3);
2397 mtree_test_insert(mt, 8, (void *)0x11);
2398 mtree_test_insert(mt, 12, (void *)0x19);
2399 mtree_test_erase(mt, 1);
2400 mtree_test_store_range(mt, 4, 62, (void *)0x9);
2401 mtree_test_erase(mt, 62);
2402 mtree_test_store_range(mt, 1, 0, (void *)0x3);
2403 mtree_test_insert(mt, 11, (void *)0x17);
2404 mtree_test_insert(mt, 3, (void *)0x7);
2405 mtree_test_insert(mt, 3, (void *)0x7);
2406 mtree_test_store(mt, 62, (void *)0x7d);
2407 mtree_test_erase(mt, 62);
2408 mtree_test_store_range(mt, 1, 15, (void *)0x3);
2409 mtree_test_erase(mt, 1);
2410 mtree_test_insert(mt, 22, (void *)0x2d);
2411 mtree_test_insert(mt, 12, (void *)0x19);
2412 mtree_test_erase(mt, 1);
2413 mtree_test_insert(mt, 3, (void *)0x7);
2414 mtree_test_store(mt, 62, (void *)0x7d);
2415 mtree_test_erase(mt, 62);
2416 mtree_test_insert(mt, 122, (void *)0xf5);
2417 mtree_test_store(mt, 3, (void *)0x7);
2418 mtree_test_insert(mt, 0, (void *)0x1);
2419 mtree_test_store_range(mt, 0, 1, (void *)0x1);
2420 mtree_test_insert(mt, 85, (void *)0xab);
2421 mtree_test_insert(mt, 72, (void *)0x91);
2422 mtree_test_insert(mt, 81, (void *)0xa3);
2423 mtree_test_insert(mt, 726, (void *)0x5ad);
2424 mtree_test_insert(mt, 0, (void *)0x1);
2425 mtree_test_insert(mt, 1, (void *)0x3);
2426 mtree_test_store(mt, 51, (void *)0x67);
2427 mtree_test_insert(mt, 611, (void *)0x4c7);
2428 mtree_test_insert(mt, 485, (void *)0x3cb);
2429 mtree_test_insert(mt, 1, (void *)0x3);
2430 mtree_test_erase(mt, 1);
2431 mtree_test_insert(mt, 0, (void *)0x1);
2432 mtree_test_insert(mt, 1, (void *)0x3);
2433 mtree_test_insert_range(mt, 26, 1, (void *)0x35);
2434 mtree_test_load(mt, 1);
2435 mtree_test_store_range(mt, 1, 22, (void *)0x3);
2436 mtree_test_insert(mt, 1, (void *)0x3);
2437 mtree_test_erase(mt, 1);
2438 mtree_test_load(mt, 53);
2439 mtree_test_load(mt, 1);
2440 mtree_test_store_range(mt, 1, 1, (void *)0x3);
2441 mtree_test_insert(mt, 222, (void *)0x1bd);
2442 mtree_test_insert(mt, 485, (void *)0x3cb);
2443 mtree_test_insert(mt, 1, (void *)0x3);
2444 mtree_test_erase(mt, 1);
2445 mtree_test_load(mt, 0);
2446 mtree_test_insert(mt, 21, (void *)0x2b);
2447 mtree_test_insert(mt, 3, (void *)0x7);
2448 mtree_test_store(mt, 621, (void *)0x4db);
2449 mtree_test_insert(mt, 0, (void *)0x1);
2450 mtree_test_erase(mt, 5);
2451 mtree_test_insert(mt, 1, (void *)0x3);
2452 mtree_test_store(mt, 62, (void *)0x7d);
2453 mtree_test_erase(mt, 62);
2454 mtree_test_store_range(mt, 1, 0, (void *)0x3);
2455 mtree_test_insert(mt, 22, (void *)0x2d);
2456 mtree_test_insert(mt, 12, (void *)0x19);
2457 mtree_test_erase(mt, 1);
2458 mtree_test_insert(mt, 1, (void *)0x3);
2459 mtree_test_store_range(mt, 4, 62, (void *)0x9);
2460 mtree_test_erase(mt, 62);
2461 mtree_test_erase(mt, 1);
2462 mtree_test_load(mt, 1);
2463 mtree_test_store_range(mt, 1, 22, (void *)0x3);
2464 mtree_test_insert(mt, 1, (void *)0x3);
2465 mtree_test_erase(mt, 1);
2466 mtree_test_load(mt, 53);
2467 mtree_test_load(mt, 1);
2468 mtree_test_store_range(mt, 1, 1, (void *)0x3);
2469 mtree_test_insert(mt, 222, (void *)0x1bd);
2470 mtree_test_insert(mt, 485, (void *)0x3cb);
2471 mtree_test_insert(mt, 1, (void *)0x3);
2472 mtree_test_erase(mt, 1);
2473 mtree_test_insert(mt, 1, (void *)0x3);
2474 mtree_test_load(mt, 0);
2475 mtree_test_load(mt, 0);
2476 mtree_destroy(mt);
2482 mt_init_flags(mt, 0);
2483 mtree_test_load(mt, 1);
2484 mtree_test_insert(mt, 102, (void *)0xcd);
2485 mtree_test_erase(mt, 2);
2486 mtree_test_erase(mt, 0);
2487 mtree_test_load(mt, 0);
2488 mtree_test_insert(mt, 4, (void *)0x9);
2489 mtree_test_insert(mt, 2, (void *)0x5);
2490 mtree_test_insert(mt, 110, (void *)0xdd);
2491 mtree_test_insert(mt, 1, (void *)0x3);
2492 mtree_test_insert_range(mt, 5, 0, (void *)0xb);
2493 mtree_test_erase(mt, 2);
2494 mtree_test_store(mt, 0, (void *)0x1);
2495 mtree_test_store(mt, 112, (void *)0xe1);
2496 mtree_test_insert(mt, 21, (void *)0x2b);
2497 mtree_test_store(mt, 1, (void *)0x3);
2498 mtree_test_insert_range(mt, 110, 2, (void *)0xdd);
2499 mtree_test_store(mt, 2, (void *)0x5);
2500 mtree_test_load(mt, 22);
2501 mtree_test_erase(mt, 2);
2502 mtree_test_store(mt, 210, (void *)0x1a5);
2503 mtree_test_store_range(mt, 0, 2, (void *)0x1);
2504 mtree_test_store(mt, 2, (void *)0x5);
2505 mtree_test_erase(mt, 2);
2506 mtree_test_erase(mt, 22);
2507 mtree_test_erase(mt, 1);
2508 mtree_test_erase(mt, 2);
2509 mtree_test_store(mt, 0, (void *)0x1);
2510 mtree_test_load(mt, 112);
2511 mtree_test_insert(mt, 2, (void *)0x5);
2512 mtree_test_erase(mt, 2);
2513 mtree_test_store(mt, 1, (void *)0x3);
2514 mtree_test_insert_range(mt, 1, 2, (void *)0x3);
2515 mtree_test_erase(mt, 0);
2516 mtree_test_erase(mt, 2);
2517 mtree_test_store(mt, 2, (void *)0x5);
2518 mtree_test_erase(mt, 0);
2519 mtree_test_erase(mt, 2);
2520 mtree_test_store(mt, 0, (void *)0x1);
2521 mtree_test_store(mt, 0, (void *)0x1);
2522 mtree_test_erase(mt, 2);
2523 mtree_test_store(mt, 2, (void *)0x5);
2524 mtree_test_erase(mt, 2);
2525 mtree_test_insert(mt, 2, (void *)0x5);
2526 mtree_test_insert_range(mt, 1, 2, (void *)0x3);
2527 mtree_test_erase(mt, 0);
2528 mtree_test_erase(mt, 2);
2529 mtree_test_store(mt, 0, (void *)0x1);
2530 mtree_test_load(mt, 112);
2531 mtree_test_store_range(mt, 110, 12, (void *)0xdd);
2532 mtree_test_store(mt, 2, (void *)0x5);
2533 mtree_test_load(mt, 110);
2534 mtree_test_insert_range(mt, 4, 71, (void *)0x9);
2535 mtree_test_load(mt, 2);
2536 mtree_test_store(mt, 2, (void *)0x5);
2537 mtree_test_insert_range(mt, 11, 22, (void *)0x17);
2538 mtree_test_erase(mt, 12);
2539 mtree_test_store(mt, 2, (void *)0x5);
2540 mtree_test_load(mt, 22);
2541 mtree_destroy(mt);
2550 mt_init_flags(mt, 0);
2551 mtree_test_store(mt, 6, (void *)0xd);
2552 mtree_test_store(mt, 67, (void *)0x87);
2553 mtree_test_insert(mt, 15, (void *)0x1f);
2554 mtree_test_insert(mt, 6716, (void *)0x3479);
2555 mtree_test_store(mt, 61, (void *)0x7b);
2556 mtree_test_insert(mt, 13, (void *)0x1b);
2557 mtree_test_store(mt, 8, (void *)0x11);
2558 mtree_test_insert(mt, 1, (void *)0x3);
2559 mtree_test_load(mt, 0);
2560 mtree_test_erase(mt, 67167);
2561 mtree_test_insert_range(mt, 6, 7167, (void *)0xd);
2562 mtree_test_insert(mt, 6, (void *)0xd);
2563 mtree_test_erase(mt, 67);
2564 mtree_test_insert(mt, 1, (void *)0x3);
2565 mtree_test_erase(mt, 667167);
2566 mtree_test_insert(mt, 6, (void *)0xd);
2567 mtree_test_store(mt, 67, (void *)0x87);
2568 mtree_test_insert(mt, 5, (void *)0xb);
2569 mtree_test_erase(mt, 1);
2570 mtree_test_insert(mt, 6, (void *)0xd);
2571 mtree_test_erase(mt, 67);
2572 mtree_test_insert(mt, 15, (void *)0x1f);
2573 mtree_test_insert(mt, 67167, (void *)0x20cbf);
2574 mtree_test_insert(mt, 1, (void *)0x3);
2575 mtree_test_load(mt, 7);
2576 mtree_test_insert(mt, 16, (void *)0x21);
2577 mtree_test_insert(mt, 36, (void *)0x49);
2578 mtree_test_store(mt, 67, (void *)0x87);
2579 mtree_test_store(mt, 6, (void *)0xd);
2580 mtree_test_insert(mt, 367, (void *)0x2df);
2581 mtree_test_insert(mt, 115, (void *)0xe7);
2582 mtree_test_store(mt, 0, (void *)0x1);
2583 mtree_test_store_range(mt, 1, 3, (void *)0x3);
2584 mtree_test_store(mt, 1, (void *)0x3);
2585 mtree_test_erase(mt, 67167);
2586 mtree_test_insert_range(mt, 6, 47, (void *)0xd);
2587 mtree_test_store(mt, 1, (void *)0x3);
2588 mtree_test_insert_range(mt, 1, 67, (void *)0x3);
2589 mtree_test_load(mt, 67);
2590 mtree_test_insert(mt, 1, (void *)0x3);
2591 mtree_test_erase(mt, 67167);
2592 mtree_destroy(mt);
2602 mt_init_flags(mt, 0);
2603 mtree_test_insert(mt, 21, (void *)0x2b);
2604 mtree_test_insert(mt, 12, (void *)0x19);
2605 mtree_test_insert(mt, 6, (void *)0xd);
2606 mtree_test_insert(mt, 8, (void *)0x11);
2607 mtree_test_insert(mt, 2, (void *)0x5);
2608 mtree_test_insert(mt, 91, (void *)0xb7);
2609 mtree_test_insert(mt, 18, (void *)0x25);
2610 mtree_test_insert(mt, 81, (void *)0xa3);
2611 mtree_test_store_range(mt, 0, 128, (void *)0x1);
2612 mtree_test_store(mt, 1, (void *)0x3);
2613 mtree_test_erase(mt, 8);
2614 mtree_test_insert(mt, 11, (void *)0x17);
2615 mtree_test_insert(mt, 8, (void *)0x11);
2616 mtree_test_insert(mt, 21, (void *)0x2b);
2617 mtree_test_insert(mt, 2, (void *)0x5);
2618 mtree_test_insert(mt, ULONG_MAX - 10, (void *)0xffffffffffffffeb);
2619 mtree_test_erase(mt, ULONG_MAX - 10);
2620 mtree_test_store_range(mt, 0, 281, (void *)0x1);
2621 mtree_test_erase(mt, 2);
2622 mtree_test_insert(mt, 1211, (void *)0x977);
2623 mtree_test_insert(mt, 111, (void *)0xdf);
2624 mtree_test_insert(mt, 13, (void *)0x1b);
2625 mtree_test_insert(mt, 211, (void *)0x1a7);
2626 mtree_test_insert(mt, 11, (void *)0x17);
2627 mtree_test_insert(mt, 5, (void *)0xb);
2628 mtree_test_insert(mt, 1218, (void *)0x985);
2629 mtree_test_insert(mt, 61, (void *)0x7b);
2630 mtree_test_store(mt, 1, (void *)0x3);
2631 mtree_test_insert(mt, 121, (void *)0xf3);
2632 mtree_test_insert(mt, 8, (void *)0x11);
2633 mtree_test_insert(mt, 21, (void *)0x2b);
2634 mtree_test_insert(mt, 2, (void *)0x5);
2635 mtree_test_insert(mt, ULONG_MAX - 10, (void *)0xffffffffffffffeb);
2636 mtree_test_erase(mt, ULONG_MAX - 10);
2640 static noinline void __init check_dup_gaps(struct maple_tree *mt,
2648 MA_STATE(mas, mt, 0, 0);
2660 mtree_store_range(mt, i*10, (i+1)*10 - gap,
2668 MT_BUG_ON(mt, ret != 0);
2684 static noinline void __init check_dup(struct maple_tree *mt)
2691 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2692 check_dup_gaps(mt, i, true, 5);
2693 mtree_destroy(mt);
2701 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2702 check_dup_gaps(mt, i, true, 0);
2703 mtree_destroy(mt);
2711 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2712 check_dup_gaps(mt, i, true, 5);
2713 mtree_destroy(mt);
2721 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2722 check_dup_gaps(mt, i, false, 5);
2723 mtree_destroy(mt);
2731 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2732 check_dup_gaps(mt, i, false, 5);
2733 mtree_destroy(mt);
2741 mt_init_flags(mt, 0);
2742 check_dup_gaps(mt, i, false, 5);
2743 mtree_destroy(mt);
2753 mt_init_flags(mt, 0);
2754 check_dup_gaps(mt, i, true, 5);
2755 mtree_destroy(mt);
2763 mt_init_flags(mt, 0);
2764 check_dup_gaps(mt, i, true, 5);
2765 mtree_destroy(mt);
2772 static noinline void __init check_bnode_min_spanning(struct maple_tree *mt)
2775 MA_STATE(mas, mt, 0, 0);
2791 static noinline void __init check_empty_area_window(struct maple_tree *mt)
2794 MA_STATE(mas, mt, 0, 0);
2797 mtree_store_range(mt, i*10, i*10 + 9,
2801 mtree_store_range(mt, 160, 169, NULL, GFP_KERNEL);
2805 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 10) != -EBUSY);
2808 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 6, 90, 5) != -EBUSY);
2812 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 5) != 0);
2813 MT_BUG_ON(mt, mas.index != 5);
2814 MT_BUG_ON(mt, mas.last != 9);
2820 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 217, 9) != 0);
2821 MT_BUG_ON(mt, mas.index != 161);
2822 MT_BUG_ON(mt, mas.last != 169);
2826 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 3) != 0);
2827 MT_BUG_ON(mt, mas.index != 216);
2828 MT_BUG_ON(mt, mas.last != 218);
2832 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 16) != -EBUSY);
2839 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 167, 200, 4) != -EBUSY);
2846 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 162, 4) != -EBUSY);
2850 MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 9) != 0);
2851 MT_BUG_ON(mt, mas.index != 0);
2852 MT_BUG_ON(mt, mas.last != 8);
2855 MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 4) != 0);
2856 MT_BUG_ON(mt, mas.index != 0);
2857 MT_BUG_ON(mt, mas.last != 3);
2860 MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 11) != -EBUSY);
2863 MT_BUG_ON(mt, mas_empty_area(&mas, 5, 100, 6) != -EBUSY);
2866 MT_BUG_ON(mt, mas_empty_area(&mas, 0, 8, 10) != -EINVAL);
2872 MT_BUG_ON(mt, mas_empty_area(&mas, 100, 163, 6) != -EBUSY);
2876 static noinline void __init check_empty_area_fill(struct maple_tree *mt)
2881 MA_STATE(mas, mt, 0, 0);
2890 MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != 0);
2891 MT_BUG_ON(mt, mas.last != mas.index + size - 1);
2901 MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != -EBUSY);
2906 mtree_store_range(mt, i, i + 5, (void *)i, GFP_KERNEL);
2908 mtree_erase(mt, 631668735);
2910 mtree_erase(mt, 629506047);
2914 MT_BUG_ON(mt, mas_empty_area(&mas, 629506048, 690000000, 0x5000) != 0);
3064 static noinline void __init check_state_handling(struct maple_tree *mt)
3066 MA_STATE(mas, mt, 0, 0);
3072 mtree_store_range(mt, 0, 0, ptr, GFP_KERNEL);
3077 MT_BUG_ON(mt, entry != NULL);
3078 MT_BUG_ON(mt, mas.status != ma_underflow);
3083 MT_BUG_ON(mt, entry != ptr);
3084 MT_BUG_ON(mt, mas.index != 0);
3085 MT_BUG_ON(mt, mas.last != 0);
3086 MT_BUG_ON(mt, mas.status != ma_root);
3092 MT_BUG_ON(mt, entry != ptr);
3093 MT_BUG_ON(mt, mas.index != 0);
3094 MT_BUG_ON(mt, mas.last != 0);
3095 MT_BUG_ON(mt, mas.status != ma_root);
3100 MT_BUG_ON(mt, mas.index != 1);
3101 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3102 MT_BUG_ON(mt, entry != NULL);
3103 MT_BUG_ON(mt, mas.status != ma_none);
3108 MT_BUG_ON(mt, mas.index != 1);
3109 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3110 MT_BUG_ON(mt, entry != NULL);
3111 MT_BUG_ON(mt, mas.status != ma_none);
3116 MT_BUG_ON(mt, entry != ptr);
3117 MT_BUG_ON(mt, mas.index != 0);
3118 MT_BUG_ON(mt, mas.last != 0);
3119 MT_BUG_ON(mt, mas.status != ma_root);
3123 MT_BUG_ON(mt, entry != NULL);
3124 MT_BUG_ON(mt, mas.index != 1);
3125 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3126 MT_BUG_ON(mt, mas.status != ma_none);
3130 MT_BUG_ON(mt, entry != NULL);
3131 MT_BUG_ON(mt, mas.index != 1);
3132 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3133 MT_BUG_ON(mt, mas.status != ma_none);
3138 MT_BUG_ON(mt, entry != NULL);
3139 MT_BUG_ON(mt, mas.index != 1);
3140 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3141 MT_BUG_ON(mt, mas.status != ma_none);
3145 MT_BUG_ON(mt, entry != ptr);
3146 MT_BUG_ON(mt, mas.index != 0);
3147 MT_BUG_ON(mt, mas.last != 0);
3148 MT_BUG_ON(mt, mas.status != ma_root);
3153 MT_BUG_ON(mt, entry != ptr);
3154 MT_BUG_ON(mt, mas.index != 0);
3155 MT_BUG_ON(mt, mas.last != 0);
3156 MT_BUG_ON(mt, mas.status != ma_root);
3160 MT_BUG_ON(mt, entry != NULL);
3161 MT_BUG_ON(mt, mas.index != 0);
3162 MT_BUG_ON(mt, mas.last != 0);
3163 MT_BUG_ON(mt, mas.status != ma_none);
3167 MT_BUG_ON(mt, entry != NULL);
3168 MT_BUG_ON(mt, mas.index != 0);
3169 MT_BUG_ON(mt, mas.last != 0);
3170 MT_BUG_ON(mt, mas.status != ma_none);
3175 MT_BUG_ON(mt, entry != ptr);
3176 MT_BUG_ON(mt, mas.index != 0);
3177 MT_BUG_ON(mt, mas.last != 0);
3178 MT_BUG_ON(mt, mas.status != ma_root);
3183 MT_BUG_ON(mt, entry != NULL);
3184 MT_BUG_ON(mt, mas.index != 1);
3185 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3186 MT_BUG_ON(mt, mas.status != ma_none);
3192 MT_BUG_ON(mt, entry != NULL);
3193 MT_BUG_ON(mt, mas.index != 1);
3194 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3195 MT_BUG_ON(mt, mas.status != ma_none);
3200 MT_BUG_ON(mt, entry != NULL);
3201 MT_BUG_ON(mt, mas.index != 1);
3202 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3203 MT_BUG_ON(mt, mas.status != ma_none);
3207 MT_BUG_ON(mt, entry != NULL);
3208 MT_BUG_ON(mt, mas.index != 1);
3209 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3210 MT_BUG_ON(mt, mas.status != ma_none);
3215 MT_BUG_ON(mt, entry != ptr);
3216 MT_BUG_ON(mt, mas.index != 0);
3217 MT_BUG_ON(mt, mas.last != 0);
3218 MT_BUG_ON(mt, mas.status != ma_root);
3224 MT_BUG_ON(mt, entry != ptr);
3225 MT_BUG_ON(mt, mas.index != 0);
3226 MT_BUG_ON(mt, mas.last != 0);
3227 MT_BUG_ON(mt, mas.status != ma_root);
3232 MT_BUG_ON(mt, entry != ptr);
3233 MT_BUG_ON(mt, mas.index != 0);
3234 MT_BUG_ON(mt, mas.last != 0);
3235 MT_BUG_ON(mt, mas.status != ma_root);
3239 MT_BUG_ON(mt, entry != ptr);
3240 MT_BUG_ON(mt, mas.index != 0);
3241 MT_BUG_ON(mt, mas.last != 0);
3242 MT_BUG_ON(mt, mas.status != ma_root);
3247 MT_BUG_ON(mt, entry != NULL);
3248 MT_BUG_ON(mt, mas.index != 1);
3249 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3250 MT_BUG_ON(mt, mas.status != ma_none);
3255 MT_BUG_ON(mt, entry != ptr);
3256 MT_BUG_ON(mt, mas.index != 0);
3257 MT_BUG_ON(mt, mas.last != 0);
3258 MT_BUG_ON(mt, mas.status != ma_root);
3263 mtree_store_range(mt, 0, 0, NULL, GFP_KERNEL);
3264 mtree_store_range(mt, 0x1000, 0x1500, ptr, GFP_KERNEL);
3265 mtree_store_range(mt, 0x2000, 0x2500, ptr2, GFP_KERNEL);
3266 mtree_store_range(mt, 0x3000, 0x3500, ptr3, GFP_KERNEL);
3273 MT_BUG_ON(mt, entry != ptr);
3274 MT_BUG_ON(mt, mas.index != 0x1000);
3275 MT_BUG_ON(mt, mas.last != 0x1500);
3276 MT_BUG_ON(mt, !mas_is_active(&mas));
3282 MT_BUG_ON(mt, entry != ptr);
3283 MT_BUG_ON(mt, mas.index != 0x1000);
3284 MT_BUG_ON(mt, mas.last != 0x1500);
3285 MT_BUG_ON(mt, !mas_is_active(&mas));
3292 MT_BUG_ON(mt, entry != ptr);
3293 MT_BUG_ON(mt, mas.index != 0x1000);
3294 MT_BUG_ON(mt, mas.last != 0x1500);
3295 MT_BUG_ON(mt, !mas_is_active(&mas));
3299 MT_BUG_ON(mt, entry != ptr2);
3300 MT_BUG_ON(mt, mas.index != 0x2000);
3301 MT_BUG_ON(mt, mas.last != 0x2500);
3302 MT_BUG_ON(mt, !mas_is_active(&mas));
3306 MT_BUG_ON(mt, entry != NULL);
3307 MT_BUG_ON(mt, mas.index != 0x2501);
3308 MT_BUG_ON(mt, mas.last != 0x2fff);
3309 MT_BUG_ON(mt, !mas_is_overflow(&mas));
3313 MT_BUG_ON(mt, entry != ptr3);
3314 MT_BUG_ON(mt, mas.index != 0x3000);
3315 MT_BUG_ON(mt, mas.last != 0x3500);
3316 MT_BUG_ON(mt, !mas_is_active(&mas));
3320 MT_BUG_ON(mt, entry != NULL);
3321 MT_BUG_ON(mt, mas.index != 0x3501);
3322 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3323 MT_BUG_ON(mt, !mas_is_overflow(&mas));
3327 MT_BUG_ON(mt, entry != NULL);
3328 MT_BUG_ON(mt, mas.index != 0x3501);
3329 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3330 MT_BUG_ON(mt, !mas_is_overflow(&mas));
3334 MT_BUG_ON(mt, entry != ptr3);
3335 MT_BUG_ON(mt, mas.index != 0x3000);
3336 MT_BUG_ON(mt, mas.last != 0x3500);
3337 MT_BUG_ON(mt, !mas_is_active(&mas));
3345 MT_BUG_ON(mt, entry != ptr2);
3346 MT_BUG_ON(mt, mas.index != 0x2000);
3347 MT_BUG_ON(mt, mas.last != 0x2500);
3348 MT_BUG_ON(mt, !mas_is_active(&mas));
3352 MT_BUG_ON(mt, entry != ptr);
3353 MT_BUG_ON(mt, mas.index != 0x1000);
3354 MT_BUG_ON(mt, mas.last != 0x1500);
3355 MT_BUG_ON(mt, !mas_is_active(&mas));
3360 MT_BUG_ON(mt, entry != ptr);
3361 MT_BUG_ON(mt, mas.index != 0x1000);
3362 MT_BUG_ON(mt, mas.last != 0x1500);
3363 MT_BUG_ON(mt, !mas_is_active(&mas)); /* spanning limit */
3365 MT_BUG_ON(mt, entry != NULL);
3366 MT_BUG_ON(mt, mas.index != 0x1000);
3367 MT_BUG_ON(mt, mas.last != 0x1500);
3368 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3372 MT_BUG_ON(mt, entry != NULL);
3373 MT_BUG_ON(mt, mas.index != 0);
3374 MT_BUG_ON(mt, mas.last != 0x0FFF);
3375 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3379 MT_BUG_ON(mt, entry != NULL);
3380 MT_BUG_ON(mt, mas.index != 0);
3381 MT_BUG_ON(mt, mas.last != 0x0FFF);
3382 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3386 MT_BUG_ON(mt, entry != NULL);
3387 MT_BUG_ON(mt, mas.index != 0);
3388 MT_BUG_ON(mt, mas.last != 0x0FFF);
3389 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3393 MT_BUG_ON(mt, entry != ptr);
3394 MT_BUG_ON(mt, mas.index != 0x1000);
3395 MT_BUG_ON(mt, mas.last != 0x1500);
3396 MT_BUG_ON(mt, !mas_is_active(&mas));
3400 MT_BUG_ON(mt, entry != NULL);
3401 MT_BUG_ON(mt, mas.index != 0x1000);
3402 MT_BUG_ON(mt, mas.last != 0x1500);
3403 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3407 MT_BUG_ON(mt, entry != ptr);
3408 MT_BUG_ON(mt, mas.index != 0x1000);
3409 MT_BUG_ON(mt, mas.last != 0x1500);
3410 MT_BUG_ON(mt, !mas_is_active(&mas));
3415 MT_BUG_ON(mt, entry != ptr3);
3418 MT_BUG_ON(mt, entry != ptr2);
3419 MT_BUG_ON(mt, mas.index != 0x2000);
3420 MT_BUG_ON(mt, mas.last != 0x2500);
3421 MT_BUG_ON(mt, !mas_is_active(&mas));
3425 MT_BUG_ON(mt, entry != NULL);
3426 MT_BUG_ON(mt, mas.index != 0x1501);
3427 MT_BUG_ON(mt, mas.last != 0x1FFF);
3428 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3432 MT_BUG_ON(mt, entry != ptr);
3433 MT_BUG_ON(mt, mas.index != 0x1000);
3434 MT_BUG_ON(mt, mas.last != 0x1500);
3435 MT_BUG_ON(mt, !mas_is_active(&mas));
3440 MT_BUG_ON(mt, entry != ptr);
3441 MT_BUG_ON(mt, mas.index != 0x1000);
3442 MT_BUG_ON(mt, mas.last != 0x1500);
3443 MT_BUG_ON(mt, !mas_is_active(&mas));
3449 MT_BUG_ON(mt, entry != ptr);
3450 MT_BUG_ON(mt, mas.index != 0x1000);
3451 MT_BUG_ON(mt, mas.last != 0x1500);
3452 MT_BUG_ON(mt, !mas_is_active(&mas));
3457 MT_BUG_ON(mt, entry != ptr);
3458 MT_BUG_ON(mt, mas.index != 0x1000);
3459 MT_BUG_ON(mt, mas.last != 0x1500);
3460 MT_BUG_ON(mt, !mas_is_active(&mas));
3464 MT_BUG_ON(mt, entry != ptr2);
3465 MT_BUG_ON(mt, mas.index != 0x2000);
3466 MT_BUG_ON(mt, mas.last != 0x2500);
3467 MT_BUG_ON(mt, !mas_is_active(&mas));
3472 MT_BUG_ON(mt, entry != NULL);
3473 MT_BUG_ON(mt, mas.index != 0x2501);
3474 MT_BUG_ON(mt, mas.last != 0x2FFF);
3479 MT_BUG_ON(mt, entry != ptr3);
3480 MT_BUG_ON(mt, mas.index != 0x3000);
3481 MT_BUG_ON(mt, mas.last != 0x3500);
3482 MT_BUG_ON(mt, !mas_is_active(&mas));
3486 MT_BUG_ON(mt, entry != NULL);
3487 MT_BUG_ON(mt, mas.index != 0x3501);
3488 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3493 MT_BUG_ON(mt, entry != ptr3);
3494 MT_BUG_ON(mt, mas.index != 0x3000);
3495 MT_BUG_ON(mt, mas.last != 0x3500);
3496 MT_BUG_ON(mt, !mas_is_active(&mas));
3500 MT_BUG_ON(mt, entry != ptr2);
3501 MT_BUG_ON(mt, mas.index != 0x2000);
3502 MT_BUG_ON(mt, mas.last != 0x2500);
3503 MT_BUG_ON(mt, !mas_is_active(&mas));
3508 MT_BUG_ON(mt, entry != ptr);
3509 MT_BUG_ON(mt, mas.index != 0x1000);
3510 MT_BUG_ON(mt, mas.last != 0x1500);
3511 MT_BUG_ON(mt, !mas_is_active(&mas));
3515 MT_BUG_ON(mt, entry != NULL);
3516 MT_BUG_ON(mt, mas.index != 0);
3517 MT_BUG_ON(mt, mas.last != 0x0FFF);
3518 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3523 MT_BUG_ON(mt, entry != ptr);
3524 MT_BUG_ON(mt, mas.index != 0x1000);
3525 MT_BUG_ON(mt, mas.last != 0x1500);
3526 MT_BUG_ON(mt, !mas_is_active(&mas));
3531 MT_BUG_ON(mt, entry != ptr);
3532 MT_BUG_ON(mt, mas.index != 0x1000);
3533 MT_BUG_ON(mt, mas.last != 0x1500);
3534 MT_BUG_ON(mt, !mas_is_active(&mas));
3539 MT_BUG_ON(mt, entry != NULL);
3540 MT_BUG_ON(mt, mas.index != 0x1501);
3541 MT_BUG_ON(mt, mas.last != 0x1fff);
3542 MT_BUG_ON(mt, !mas_is_active(&mas));
3548 MT_BUG_ON(mt, entry != ptr);
3549 MT_BUG_ON(mt, mas.index != 0x1000);
3550 MT_BUG_ON(mt, mas.last != 0x1500);
3551 MT_BUG_ON(mt, !mas_is_active(&mas));
3557 MT_BUG_ON(mt, entry != NULL);
3558 MT_BUG_ON(mt, mas.index != 0x1501);
3559 MT_BUG_ON(mt, mas.last != 0x1fff);
3560 MT_BUG_ON(mt, !mas_is_active(&mas));
3566 MT_BUG_ON(mt, entry != ptr);
3567 MT_BUG_ON(mt, mas.index != 0x1000);
3568 MT_BUG_ON(mt, mas.last != 0x1500);
3569 MT_BUG_ON(mt, !mas_is_active(&mas));
3575 MT_BUG_ON(mt, entry != NULL);
3576 MT_BUG_ON(mt, mas.index != 0x1501);
3577 MT_BUG_ON(mt, mas.last != 0x1fff);
3578 MT_BUG_ON(mt, !mas_is_active(&mas));
3585 MT_BUG_ON(mt, entry != ptr);
3586 MT_BUG_ON(mt, mas.index != 0x1000);
3587 MT_BUG_ON(mt, mas.last != 0x1500);
3588 MT_BUG_ON(mt, !mas_is_active(&mas));
3594 MT_BUG_ON(mt, entry != NULL);
3595 MT_BUG_ON(mt, mas.index != 0x1501);
3596 MT_BUG_ON(mt, mas.last != 0x1fff);
3597 MT_BUG_ON(mt, !mas_is_active(&mas));
3602 static noinline void __init alloc_cyclic_testing(struct maple_tree *mt)
3607 MA_STATE(mas, mt, 0, 0);
3610 mtree_lock(mt);
3612 mas_alloc_cyclic(&mas, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3619 mtree_unlock(mt);
3620 mtree_destroy(mt);
3622 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
3624 mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3625 MT_BUG_ON(mt, i != location - 2);
3626 MT_BUG_ON(mt, i != next - 3);
3627 MT_BUG_ON(mt, mtree_load(mt, location) != mt);
3630 mtree_destroy(mt);
3633 ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3634 MT_BUG_ON(mt, ret != 0);
3635 ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3636 MT_BUG_ON(mt, ret != 0);
3637 ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3638 MT_BUG_ON(mt, ret != 1);