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_store_null(struct maple_tree *mt)
1392 MA_STATE(mas, mt, 0, ULONG_MAX);
1398 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1401 MT_BUG_ON(mt, !mtree_empty(mt));
1403 mtree_destroy(mt);
1409 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1413 MT_BUG_ON(mt, !mtree_empty(mt));
1415 mtree_destroy(mt);
1421 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1427 MT_BUG_ON(mt, !mtree_empty(mt));
1429 mtree_destroy(mt);
1435 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1441 MT_BUG_ON(mt, !mtree_empty(mt));
1443 mtree_destroy(mt);
1449 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1455 MT_BUG_ON(mt, mtree_empty(mt));
1456 // MT_BUG_ON(mt, xa_is_node(mas_root(&mas)));
1458 mtree_destroy(mt);
1464 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1468 // MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
1471 MT_BUG_ON(mt, !mtree_empty(mt));
1473 mtree_destroy(mt);
1476 static noinline void __init check_root_expand(struct maple_tree *mt)
1478 MA_STATE(mas, mt, 0, 0);
1485 MT_BUG_ON(mt, mas.index != 0);
1486 MT_BUG_ON(mt, ptr != NULL);
1487 MT_BUG_ON(mt, mas.index != 0);
1488 MT_BUG_ON(mt, mas.last != ULONG_MAX);
1496 MT_BUG_ON(mt, ptr != NULL);
1500 MT_BUG_ON(mt, ptr != &check_prev_entry);
1504 MT_BUG_ON(mt, ptr != NULL);
1506 mtree_destroy(mt);
1509 mt_init_flags(mt, 0);
1518 MT_BUG_ON(mt, ptr != NULL);
1519 MT_BUG_ON(mt, mas.index != 1);
1520 MT_BUG_ON(mt, mas.last != ULONG_MAX);
1524 MT_BUG_ON(mt, ptr != &check_prev_entry);
1525 MT_BUG_ON(mt, mas.last != 0);
1527 mtree_destroy(mt);
1529 mt_init_flags(mt, 0);
1536 MT_BUG_ON(mt, ptr != NULL);
1537 MT_BUG_ON(mt, (mas.index != 1) && (mas.last != ULONG_MAX));
1541 MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0));
1542 MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 1UL));
1546 mtree_destroy(mt);
1548 mt_init_flags(mt, 0);
1554 MT_BUG_ON(mt, ptr != NULL);
1555 MT_BUG_ON(mt, (mas.index != ULONG_MAX) && (mas.last != ULONG_MAX));
1559 MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0));
1560 MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 2UL));
1566 static noinline void __init check_deficient_node(struct maple_tree *mt)
1568 MA_STATE(mas, mt, 0, 0);
1587 mt_validate(mt);
1590 static noinline void __init check_gap_combining(struct maple_tree *mt)
1636 MA_STATE(mas, mt, 0, 0);
1645 MT_BUG_ON(mt, !mtree_empty(mt));
1646 check_seq(mt, singletons, false); /* create 100 singletons. */
1649 mtree_test_erase(mt, seq100[2]);
1650 check_load(mt, seq100[2], NULL);
1651 mtree_test_erase(mt, seq100[1]);
1652 check_load(mt, seq100[1], NULL);
1656 MT_BUG_ON(mt, entry != xa_mk_value(index));
1660 MT_BUG_ON(mt, entry != xa_mk_value(index + 4));
1662 MT_BUG_ON(mt, mn1 == mn2); /* test the test. */
1670 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[3], seq100[4],
1672 MT_BUG_ON(mt, mas.index != index + 1);
1675 mtree_test_erase(mt, seq100[6]);
1676 check_load(mt, seq100[6], NULL);
1677 mtree_test_erase(mt, seq100[7]);
1678 check_load(mt, seq100[7], NULL);
1679 mtree_test_erase(mt, seq100[8]);
1687 MT_BUG_ON(mt, entry != xa_mk_value(index));
1690 MT_BUG_ON(mt, entry != xa_mk_value(index + 4));
1693 MT_BUG_ON(mt, mn1 == mn2); /* test the next entry is in the next node. */
1700 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[10], seq100[11],
1702 MT_BUG_ON(mt, mas.index != seq100[6]);
1706 mtree_store(mt, seq100[13], NULL, GFP_KERNEL);
1707 check_load(mt, seq100[13], NULL);
1708 check_load(mt, seq100[14], xa_mk_value(seq100[14]));
1709 mtree_store(mt, seq100[14], NULL, GFP_KERNEL);
1710 check_load(mt, seq100[13], NULL);
1711 check_load(mt, seq100[14], NULL);
1715 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[15],
1717 MT_BUG_ON(mt, mas.index != seq100[13]);
1718 mt_validate(mt);
1726 mtree_test_store_range(mt, seq100[18], seq100[14], NULL);
1727 mtree_test_erase(mt, seq100[15]);
1730 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[19],
1733 MT_BUG_ON(mt, mas.index != seq100[18]);
1734 mt_validate(mt);
1735 mtree_destroy(mt);
1738 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1739 check_seq(mt, 2000, false);
1741 mtree_test_erase(mt, seq2000[0]);
1742 mtree_test_erase(mt, seq2000[1]);
1747 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq2000[2], seq2000[3],
1749 MT_BUG_ON(mt, mas.index != seq2000[1]);
1751 mt_validate(mt);
1752 mtree_destroy(mt);
1756 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1757 check_seq(mt, 400, false);
1758 mtree_test_store_range(mt, seq400[0], seq400[1], NULL);
1760 mtree_destroy(mt);
1762 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1763 check_seq(mt, 400, false);
1765 mtree_test_store_range(mt, seq400[2], seq400[9],
1767 mtree_test_store_range(mt, seq400[3], seq400[9],
1769 mtree_test_store_range(mt, seq400[4], seq400[9],
1771 mtree_test_store_range(mt, seq400[5], seq400[9],
1773 mtree_test_store_range(mt, seq400[0], seq400[9],
1775 mtree_test_store_range(mt, seq400[6], seq400[9],
1777 mtree_test_store_range(mt, seq400[7], seq400[9],
1779 mtree_test_store_range(mt, seq400[8], seq400[9],
1781 mtree_test_store_range(mt, seq400[10], seq400[11],
1783 mt_validate(mt);
1785 mtree_destroy(mt);
1787 static noinline void __init check_node_overwrite(struct maple_tree *mt)
1792 mtree_test_store_range(mt, i*100, i*100 + 50, xa_mk_value(i*100));
1794 mtree_test_store_range(mt, 319951, 367950, NULL);
1795 /*mt_dump(mt, mt_dump_dec); */
1796 mt_validate(mt);
1800 static noinline void __init bench_slot_store(struct maple_tree *mt)
1805 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1808 mtree_store_range(mt, brk, brk, NULL, GFP_KERNEL);
1809 mtree_store_range(mt, brk_start, brk, xa_mk_value(brk),
1816 static noinline void __init bench_node_store(struct maple_tree *mt)
1821 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1824 mtree_store_range(mt, overwrite, overwrite + 15,
1835 static noinline void __init bench_awalk(struct maple_tree *mt)
1838 MA_STATE(mas, mt, 1470, 1470);
1841 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1843 mtree_store_range(mt, 1470, 1475, NULL, GFP_KERNEL);
1852 static noinline void __init bench_walk(struct maple_tree *mt)
1855 MA_STATE(mas, mt, 1470, 1470);
1858 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1869 static noinline void __init bench_load(struct maple_tree *mt)
1874 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1877 mtree_load(mt, 1470);
1882 static noinline void __init bench_mt_for_each(struct maple_tree *mt)
1889 mtree_store_range(mt, i, i + 4, xa_mk_value(i), GFP_KERNEL);
1894 mt_for_each(mt, entry, index, max) {
1895 MT_BUG_ON(mt, entry != xa_mk_value(j));
1906 static noinline void __init bench_mas_for_each(struct maple_tree *mt)
1911 MA_STATE(mas, mt, 0, 0);
1918 mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
1926 MT_BUG_ON(mt, entry != xa_mk_value(j));
1936 static noinline void __init bench_mas_prev(struct maple_tree *mt)
1941 MA_STATE(mas, mt, 0, 0);
1948 mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
1957 MT_BUG_ON(mt, entry != xa_mk_value(j));
1968 struct maple_tree mt, newmt;
1971 MA_STATE(mas, &mt, 0, 0);
1978 mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
1979 mt_set_external_lock(&mt, &mt_lock);
1991 ret = __mt_dup(&mt, &newmt, GFP_KERNEL);
2005 __mt_destroy(&mt);
2010 static noinline void __init check_iteration(struct maple_tree *mt)
2014 MA_STATE(mas, mt, 0, 0);
2017 mtree_store_range(mt, i * 10, i * 10 + 9,
2025 MT_BUG_ON(mt, mas.index != i * 10);
2026 MT_BUG_ON(mt, mas.last != i * 10 + 9);
2037 MT_BUG_ON(mt, val != xa_mk_value(i));
2042 MT_BUG_ON(mt, mas.index != i * 10);
2043 MT_BUG_ON(mt, mas.last != i * 10 + 9);
2054 MT_BUG_ON(mt, val != xa_mk_value(i));
2059 MT_BUG_ON(mt, mas.index != i * 10);
2060 MT_BUG_ON(mt, mas.last != i * 10 + 9);
2071 MT_BUG_ON(mt, val != xa_mk_value(76));
2077 static noinline void __init check_mas_store_gfp(struct maple_tree *mt)
2083 MA_STATE(mas, mt, 0, 0);
2084 MA_STATE(newmas, mt, 0, 0);
2087 mtree_store_range(mt, i*10, i*10 + 5,
2112 struct maple_tree mt, newmt;
2115 MA_STATE(mas, &mt, 0, 0);
2122 mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
2123 mt_set_external_lock(&mt, &mt_lock);
2137 ret = __mt_dup(&mt, &newmt, GFP_KERNEL);
2153 __mt_destroy(&mt);
2158 static noinline void __init next_prev_test(struct maple_tree *mt)
2162 MA_STATE(mas, mt, 0, 0);
2182 mtree_store_range(mt, i*10, i*10 + 5,
2215 MT_BUG_ON(mt, val != NULL);
2218 MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
2219 MT_BUG_ON(mt, mas.index != 690);
2220 MT_BUG_ON(mt, mas.last != 695);
2223 MT_BUG_ON(mt, val != xa_mk_value(680 / 10));
2224 MT_BUG_ON(mt, mas.index != 680);
2225 MT_BUG_ON(mt, mas.last != 685);
2228 MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
2229 MT_BUG_ON(mt, mas.index != 690);
2230 MT_BUG_ON(mt, mas.last != 695);
2233 MT_BUG_ON(mt, val != xa_mk_value(700 / 10));
2234 MT_BUG_ON(mt, mas.index != 700);
2235 MT_BUG_ON(mt, mas.last != 705);
2240 MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
2241 MT_BUG_ON(mt, mas.index != 70);
2242 MT_BUG_ON(mt, mas.last != 75);
2245 MT_BUG_ON(mt, val != xa_mk_value(80 / 10));
2246 MT_BUG_ON(mt, mas.index != 80);
2247 MT_BUG_ON(mt, mas.last != 85);
2250 MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
2251 MT_BUG_ON(mt, mas.index != 70);
2252 MT_BUG_ON(mt, mas.last != 75);
2258 MT_BUG_ON(mt, val != NULL);
2260 MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
2261 MT_BUG_ON(mt, mas.index != level2[2]);
2262 MT_BUG_ON(mt, mas.last != level2[3]);
2266 MT_BUG_ON(mt, val != xa_mk_value(level2[4] / 10));
2267 MT_BUG_ON(mt, mas.index != level2[4]);
2268 MT_BUG_ON(mt, mas.last != level2[5]);
2269 MT_BUG_ON(mt, mn == mas.node);
2272 MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
2273 MT_BUG_ON(mt, mas.index != level2[2]);
2274 MT_BUG_ON(mt, mas.last != level2[3]);
2279 MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
2280 MT_BUG_ON(mt, mas.index != (nr_entries * 10));
2281 MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
2284 MT_BUG_ON(mt, val != NULL);
2285 MT_BUG_ON(mt, mas.index != last_index);
2286 MT_BUG_ON(mt, mas.last != ULONG_MAX);
2289 MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
2290 MT_BUG_ON(mt, mas.index != (nr_entries * 10));
2291 MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
2297 MT_BUG_ON(mt, val != xa_mk_value(1));
2298 MT_BUG_ON(mt, mas.index != 10);
2299 MT_BUG_ON(mt, mas.last != 15);
2302 MT_BUG_ON(mt, val != xa_mk_value(0));
2303 MT_BUG_ON(mt, mas.index != 0);
2304 MT_BUG_ON(mt, mas.last != 5);
2307 MT_BUG_ON(mt, val != NULL);
2308 MT_BUG_ON(mt, mas.index != 0);
2309 MT_BUG_ON(mt, mas.last != 5);
2310 MT_BUG_ON(mt, !mas_is_underflow(&mas));
2320 MT_BUG_ON(mt, val != NULL);
2321 MT_BUG_ON(mt, mas.index != 0);
2322 MT_BUG_ON(mt, mas.last != 9);
2325 mtree_destroy(mt);
2327 mt_init(mt);
2328 mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL);
2329 mtree_store_range(mt, 5, 5, xa_mk_value(5), GFP_KERNEL);
2333 MT_BUG_ON(mt, val != NULL);
2340 static noinline void __init check_spanning_relatives(struct maple_tree *mt)
2346 mtree_store_range(mt, i*10, i*10 + 5,
2350 mtree_store_range(mt, 9365, 9955, NULL, GFP_KERNEL);
2353 static noinline void __init check_fuzzer(struct maple_tree *mt)
2360 mtree_test_insert(mt, 88, (void *)0xb1);
2361 mtree_test_insert(mt, 84, (void *)0xa9);
2362 mtree_test_insert(mt, 2, (void *)0x5);
2363 mtree_test_insert(mt, 4, (void *)0x9);
2364 mtree_test_insert(mt, 14, (void *)0x1d);
2365 mtree_test_insert(mt, 7, (void *)0xf);
2366 mtree_test_insert(mt, 12, (void *)0x19);
2367 mtree_test_insert(mt, 18, (void *)0x25);
2368 mtree_test_store_range(mt, 8, 18, (void *)0x11);
2369 mtree_destroy(mt);
2376 mt_init_flags(mt, 0);
2377 mtree_test_store(mt, 87, (void *)0xaf);
2378 mtree_test_store(mt, 0, (void *)0x1);
2379 mtree_test_load(mt, 4);
2380 mtree_test_insert(mt, 4, (void *)0x9);
2381 mtree_test_store(mt, 8, (void *)0x11);
2382 mtree_test_store(mt, 44, (void *)0x59);
2383 mtree_test_store(mt, 68, (void *)0x89);
2384 mtree_test_store(mt, 2, (void *)0x5);
2385 mtree_test_insert(mt, 43, (void *)0x57);
2386 mtree_test_insert(mt, 24, (void *)0x31);
2387 mtree_test_insert(mt, 844, (void *)0x699);
2388 mtree_test_store(mt, 84, (void *)0xa9);
2389 mtree_test_store(mt, 4, (void *)0x9);
2390 mtree_test_erase(mt, 4);
2391 mtree_test_load(mt, 5);
2392 mtree_test_erase(mt, 0);
2393 mtree_destroy(mt);
2400 mt_init_flags(mt, 0);
2401 mtree_test_store_range(mt, 0, ULONG_MAX, (void *)0x1);
2402 mtree_test_store(mt, 4, (void *)0x9);
2403 mtree_test_erase(mt, 5);
2404 mtree_test_erase(mt, 0);
2405 mtree_test_erase(mt, 4);
2406 mtree_test_store(mt, 5, (void *)0xb);
2407 mtree_test_erase(mt, 5);
2408 mtree_test_store(mt, 5, (void *)0xb);
2409 mtree_test_erase(mt, 5);
2410 mtree_test_erase(mt, 4);
2411 mtree_test_store(mt, 4, (void *)0x9);
2412 mtree_test_store(mt, 444, (void *)0x379);
2413 mtree_test_store(mt, 0, (void *)0x1);
2414 mtree_test_load(mt, 0);
2415 mtree_test_store(mt, 5, (void *)0xb);
2416 mtree_test_erase(mt, 0);
2417 mtree_destroy(mt);
2425 mt_init_flags(mt, 0);
2426 mtree_test_insert(mt, 261, (void *)0x20b);
2427 mtree_test_store(mt, 516, (void *)0x409);
2428 mtree_test_store(mt, 6, (void *)0xd);
2429 mtree_test_insert(mt, 5, (void *)0xb);
2430 mtree_test_insert(mt, 1256, (void *)0x9d1);
2431 mtree_test_store(mt, 4, (void *)0x9);
2432 mtree_test_erase(mt, 1);
2433 mtree_test_store(mt, 56, (void *)0x71);
2434 mtree_test_insert(mt, 1, (void *)0x3);
2435 mtree_test_store(mt, 24, (void *)0x31);
2436 mtree_test_erase(mt, 1);
2437 mtree_test_insert(mt, 2263, (void *)0x11af);
2438 mtree_test_insert(mt, 446, (void *)0x37d);
2439 mtree_test_store_range(mt, 6, 45, (void *)0xd);
2440 mtree_test_store_range(mt, 3, 446, (void *)0x7);
2441 mtree_destroy(mt);
2447 mt_init_flags(mt, 0);
2448 mtree_test_store(mt, 48, (void *)0x61);
2449 mtree_test_store(mt, 3, (void *)0x7);
2450 mtree_test_load(mt, 0);
2451 mtree_test_store(mt, 88, (void *)0xb1);
2452 mtree_test_store(mt, 81, (void *)0xa3);
2453 mtree_test_insert(mt, 0, (void *)0x1);
2454 mtree_test_insert(mt, 8, (void *)0x11);
2455 mtree_test_insert(mt, 4, (void *)0x9);
2456 mtree_test_insert(mt, 2480, (void *)0x1361);
2457 mtree_test_insert(mt, ULONG_MAX,
2459 mtree_test_erase(mt, ULONG_MAX);
2460 mtree_destroy(mt);
2469 mt_init_flags(mt, 0);
2470 mtree_test_erase(mt, 3);
2471 mtree_test_insert(mt, 22, (void *)0x2d);
2472 mtree_test_insert(mt, 15, (void *)0x1f);
2473 mtree_test_load(mt, 2);
2474 mtree_test_insert(mt, 1, (void *)0x3);
2475 mtree_test_insert(mt, 1, (void *)0x3);
2476 mtree_test_insert(mt, 5, (void *)0xb);
2477 mtree_test_erase(mt, 1);
2478 mtree_test_insert(mt, 1, (void *)0x3);
2479 mtree_test_insert(mt, 4, (void *)0x9);
2480 mtree_test_insert(mt, 1, (void *)0x3);
2481 mtree_test_erase(mt, 1);
2482 mtree_test_insert(mt, 2, (void *)0x5);
2483 mtree_test_insert(mt, 1, (void *)0x3);
2484 mtree_test_erase(mt, 3);
2485 mtree_test_insert(mt, 22, (void *)0x2d);
2486 mtree_test_insert(mt, 15, (void *)0x1f);
2487 mtree_test_insert(mt, 2, (void *)0x5);
2488 mtree_test_insert(mt, 1, (void *)0x3);
2489 mtree_test_insert(mt, 8, (void *)0x11);
2490 mtree_test_load(mt, 2);
2491 mtree_test_insert(mt, 1, (void *)0x3);
2492 mtree_test_insert(mt, 1, (void *)0x3);
2493 mtree_test_store(mt, 1, (void *)0x3);
2494 mtree_test_insert(mt, 5, (void *)0xb);
2495 mtree_test_erase(mt, 1);
2496 mtree_test_insert(mt, 1, (void *)0x3);
2497 mtree_test_insert(mt, 4, (void *)0x9);
2498 mtree_test_insert(mt, 1, (void *)0x3);
2499 mtree_test_erase(mt, 1);
2500 mtree_test_insert(mt, 2, (void *)0x5);
2501 mtree_test_insert(mt, 1, (void *)0x3);
2502 mtree_test_erase(mt, 3);
2503 mtree_test_insert(mt, 22, (void *)0x2d);
2504 mtree_test_insert(mt, 15, (void *)0x1f);
2505 mtree_test_insert(mt, 2, (void *)0x5);
2506 mtree_test_insert(mt, 1, (void *)0x3);
2507 mtree_test_insert(mt, 8, (void *)0x11);
2508 mtree_test_insert(mt, 12, (void *)0x19);
2509 mtree_test_erase(mt, 1);
2510 mtree_test_store_range(mt, 4, 62, (void *)0x9);
2511 mtree_test_erase(mt, 62);
2512 mtree_test_store_range(mt, 1, 0, (void *)0x3);
2513 mtree_test_insert(mt, 11, (void *)0x17);
2514 mtree_test_insert(mt, 3, (void *)0x7);
2515 mtree_test_insert(mt, 3, (void *)0x7);
2516 mtree_test_store(mt, 62, (void *)0x7d);
2517 mtree_test_erase(mt, 62);
2518 mtree_test_store_range(mt, 1, 15, (void *)0x3);
2519 mtree_test_erase(mt, 1);
2520 mtree_test_insert(mt, 22, (void *)0x2d);
2521 mtree_test_insert(mt, 12, (void *)0x19);
2522 mtree_test_erase(mt, 1);
2523 mtree_test_insert(mt, 3, (void *)0x7);
2524 mtree_test_store(mt, 62, (void *)0x7d);
2525 mtree_test_erase(mt, 62);
2526 mtree_test_insert(mt, 122, (void *)0xf5);
2527 mtree_test_store(mt, 3, (void *)0x7);
2528 mtree_test_insert(mt, 0, (void *)0x1);
2529 mtree_test_store_range(mt, 0, 1, (void *)0x1);
2530 mtree_test_insert(mt, 85, (void *)0xab);
2531 mtree_test_insert(mt, 72, (void *)0x91);
2532 mtree_test_insert(mt, 81, (void *)0xa3);
2533 mtree_test_insert(mt, 726, (void *)0x5ad);
2534 mtree_test_insert(mt, 0, (void *)0x1);
2535 mtree_test_insert(mt, 1, (void *)0x3);
2536 mtree_test_store(mt, 51, (void *)0x67);
2537 mtree_test_insert(mt, 611, (void *)0x4c7);
2538 mtree_test_insert(mt, 485, (void *)0x3cb);
2539 mtree_test_insert(mt, 1, (void *)0x3);
2540 mtree_test_erase(mt, 1);
2541 mtree_test_insert(mt, 0, (void *)0x1);
2542 mtree_test_insert(mt, 1, (void *)0x3);
2543 mtree_test_insert_range(mt, 26, 1, (void *)0x35);
2544 mtree_test_load(mt, 1);
2545 mtree_test_store_range(mt, 1, 22, (void *)0x3);
2546 mtree_test_insert(mt, 1, (void *)0x3);
2547 mtree_test_erase(mt, 1);
2548 mtree_test_load(mt, 53);
2549 mtree_test_load(mt, 1);
2550 mtree_test_store_range(mt, 1, 1, (void *)0x3);
2551 mtree_test_insert(mt, 222, (void *)0x1bd);
2552 mtree_test_insert(mt, 485, (void *)0x3cb);
2553 mtree_test_insert(mt, 1, (void *)0x3);
2554 mtree_test_erase(mt, 1);
2555 mtree_test_load(mt, 0);
2556 mtree_test_insert(mt, 21, (void *)0x2b);
2557 mtree_test_insert(mt, 3, (void *)0x7);
2558 mtree_test_store(mt, 621, (void *)0x4db);
2559 mtree_test_insert(mt, 0, (void *)0x1);
2560 mtree_test_erase(mt, 5);
2561 mtree_test_insert(mt, 1, (void *)0x3);
2562 mtree_test_store(mt, 62, (void *)0x7d);
2563 mtree_test_erase(mt, 62);
2564 mtree_test_store_range(mt, 1, 0, (void *)0x3);
2565 mtree_test_insert(mt, 22, (void *)0x2d);
2566 mtree_test_insert(mt, 12, (void *)0x19);
2567 mtree_test_erase(mt, 1);
2568 mtree_test_insert(mt, 1, (void *)0x3);
2569 mtree_test_store_range(mt, 4, 62, (void *)0x9);
2570 mtree_test_erase(mt, 62);
2571 mtree_test_erase(mt, 1);
2572 mtree_test_load(mt, 1);
2573 mtree_test_store_range(mt, 1, 22, (void *)0x3);
2574 mtree_test_insert(mt, 1, (void *)0x3);
2575 mtree_test_erase(mt, 1);
2576 mtree_test_load(mt, 53);
2577 mtree_test_load(mt, 1);
2578 mtree_test_store_range(mt, 1, 1, (void *)0x3);
2579 mtree_test_insert(mt, 222, (void *)0x1bd);
2580 mtree_test_insert(mt, 485, (void *)0x3cb);
2581 mtree_test_insert(mt, 1, (void *)0x3);
2582 mtree_test_erase(mt, 1);
2583 mtree_test_insert(mt, 1, (void *)0x3);
2584 mtree_test_load(mt, 0);
2585 mtree_test_load(mt, 0);
2586 mtree_destroy(mt);
2592 mt_init_flags(mt, 0);
2593 mtree_test_load(mt, 1);
2594 mtree_test_insert(mt, 102, (void *)0xcd);
2595 mtree_test_erase(mt, 2);
2596 mtree_test_erase(mt, 0);
2597 mtree_test_load(mt, 0);
2598 mtree_test_insert(mt, 4, (void *)0x9);
2599 mtree_test_insert(mt, 2, (void *)0x5);
2600 mtree_test_insert(mt, 110, (void *)0xdd);
2601 mtree_test_insert(mt, 1, (void *)0x3);
2602 mtree_test_insert_range(mt, 5, 0, (void *)0xb);
2603 mtree_test_erase(mt, 2);
2604 mtree_test_store(mt, 0, (void *)0x1);
2605 mtree_test_store(mt, 112, (void *)0xe1);
2606 mtree_test_insert(mt, 21, (void *)0x2b);
2607 mtree_test_store(mt, 1, (void *)0x3);
2608 mtree_test_insert_range(mt, 110, 2, (void *)0xdd);
2609 mtree_test_store(mt, 2, (void *)0x5);
2610 mtree_test_load(mt, 22);
2611 mtree_test_erase(mt, 2);
2612 mtree_test_store(mt, 210, (void *)0x1a5);
2613 mtree_test_store_range(mt, 0, 2, (void *)0x1);
2614 mtree_test_store(mt, 2, (void *)0x5);
2615 mtree_test_erase(mt, 2);
2616 mtree_test_erase(mt, 22);
2617 mtree_test_erase(mt, 1);
2618 mtree_test_erase(mt, 2);
2619 mtree_test_store(mt, 0, (void *)0x1);
2620 mtree_test_load(mt, 112);
2621 mtree_test_insert(mt, 2, (void *)0x5);
2622 mtree_test_erase(mt, 2);
2623 mtree_test_store(mt, 1, (void *)0x3);
2624 mtree_test_insert_range(mt, 1, 2, (void *)0x3);
2625 mtree_test_erase(mt, 0);
2626 mtree_test_erase(mt, 2);
2627 mtree_test_store(mt, 2, (void *)0x5);
2628 mtree_test_erase(mt, 0);
2629 mtree_test_erase(mt, 2);
2630 mtree_test_store(mt, 0, (void *)0x1);
2631 mtree_test_store(mt, 0, (void *)0x1);
2632 mtree_test_erase(mt, 2);
2633 mtree_test_store(mt, 2, (void *)0x5);
2634 mtree_test_erase(mt, 2);
2635 mtree_test_insert(mt, 2, (void *)0x5);
2636 mtree_test_insert_range(mt, 1, 2, (void *)0x3);
2637 mtree_test_erase(mt, 0);
2638 mtree_test_erase(mt, 2);
2639 mtree_test_store(mt, 0, (void *)0x1);
2640 mtree_test_load(mt, 112);
2641 mtree_test_store_range(mt, 110, 12, (void *)0xdd);
2642 mtree_test_store(mt, 2, (void *)0x5);
2643 mtree_test_load(mt, 110);
2644 mtree_test_insert_range(mt, 4, 71, (void *)0x9);
2645 mtree_test_load(mt, 2);
2646 mtree_test_store(mt, 2, (void *)0x5);
2647 mtree_test_insert_range(mt, 11, 22, (void *)0x17);
2648 mtree_test_erase(mt, 12);
2649 mtree_test_store(mt, 2, (void *)0x5);
2650 mtree_test_load(mt, 22);
2651 mtree_destroy(mt);
2660 mt_init_flags(mt, 0);
2661 mtree_test_store(mt, 6, (void *)0xd);
2662 mtree_test_store(mt, 67, (void *)0x87);
2663 mtree_test_insert(mt, 15, (void *)0x1f);
2664 mtree_test_insert(mt, 6716, (void *)0x3479);
2665 mtree_test_store(mt, 61, (void *)0x7b);
2666 mtree_test_insert(mt, 13, (void *)0x1b);
2667 mtree_test_store(mt, 8, (void *)0x11);
2668 mtree_test_insert(mt, 1, (void *)0x3);
2669 mtree_test_load(mt, 0);
2670 mtree_test_erase(mt, 67167);
2671 mtree_test_insert_range(mt, 6, 7167, (void *)0xd);
2672 mtree_test_insert(mt, 6, (void *)0xd);
2673 mtree_test_erase(mt, 67);
2674 mtree_test_insert(mt, 1, (void *)0x3);
2675 mtree_test_erase(mt, 667167);
2676 mtree_test_insert(mt, 6, (void *)0xd);
2677 mtree_test_store(mt, 67, (void *)0x87);
2678 mtree_test_insert(mt, 5, (void *)0xb);
2679 mtree_test_erase(mt, 1);
2680 mtree_test_insert(mt, 6, (void *)0xd);
2681 mtree_test_erase(mt, 67);
2682 mtree_test_insert(mt, 15, (void *)0x1f);
2683 mtree_test_insert(mt, 67167, (void *)0x20cbf);
2684 mtree_test_insert(mt, 1, (void *)0x3);
2685 mtree_test_load(mt, 7);
2686 mtree_test_insert(mt, 16, (void *)0x21);
2687 mtree_test_insert(mt, 36, (void *)0x49);
2688 mtree_test_store(mt, 67, (void *)0x87);
2689 mtree_test_store(mt, 6, (void *)0xd);
2690 mtree_test_insert(mt, 367, (void *)0x2df);
2691 mtree_test_insert(mt, 115, (void *)0xe7);
2692 mtree_test_store(mt, 0, (void *)0x1);
2693 mtree_test_store_range(mt, 1, 3, (void *)0x3);
2694 mtree_test_store(mt, 1, (void *)0x3);
2695 mtree_test_erase(mt, 67167);
2696 mtree_test_insert_range(mt, 6, 47, (void *)0xd);
2697 mtree_test_store(mt, 1, (void *)0x3);
2698 mtree_test_insert_range(mt, 1, 67, (void *)0x3);
2699 mtree_test_load(mt, 67);
2700 mtree_test_insert(mt, 1, (void *)0x3);
2701 mtree_test_erase(mt, 67167);
2702 mtree_destroy(mt);
2712 mt_init_flags(mt, 0);
2713 mtree_test_insert(mt, 21, (void *)0x2b);
2714 mtree_test_insert(mt, 12, (void *)0x19);
2715 mtree_test_insert(mt, 6, (void *)0xd);
2716 mtree_test_insert(mt, 8, (void *)0x11);
2717 mtree_test_insert(mt, 2, (void *)0x5);
2718 mtree_test_insert(mt, 91, (void *)0xb7);
2719 mtree_test_insert(mt, 18, (void *)0x25);
2720 mtree_test_insert(mt, 81, (void *)0xa3);
2721 mtree_test_store_range(mt, 0, 128, (void *)0x1);
2722 mtree_test_store(mt, 1, (void *)0x3);
2723 mtree_test_erase(mt, 8);
2724 mtree_test_insert(mt, 11, (void *)0x17);
2725 mtree_test_insert(mt, 8, (void *)0x11);
2726 mtree_test_insert(mt, 21, (void *)0x2b);
2727 mtree_test_insert(mt, 2, (void *)0x5);
2728 mtree_test_insert(mt, ULONG_MAX - 10, (void *)0xffffffffffffffeb);
2729 mtree_test_erase(mt, ULONG_MAX - 10);
2730 mtree_test_store_range(mt, 0, 281, (void *)0x1);
2731 mtree_test_erase(mt, 2);
2732 mtree_test_insert(mt, 1211, (void *)0x977);
2733 mtree_test_insert(mt, 111, (void *)0xdf);
2734 mtree_test_insert(mt, 13, (void *)0x1b);
2735 mtree_test_insert(mt, 211, (void *)0x1a7);
2736 mtree_test_insert(mt, 11, (void *)0x17);
2737 mtree_test_insert(mt, 5, (void *)0xb);
2738 mtree_test_insert(mt, 1218, (void *)0x985);
2739 mtree_test_insert(mt, 61, (void *)0x7b);
2740 mtree_test_store(mt, 1, (void *)0x3);
2741 mtree_test_insert(mt, 121, (void *)0xf3);
2742 mtree_test_insert(mt, 8, (void *)0x11);
2743 mtree_test_insert(mt, 21, (void *)0x2b);
2744 mtree_test_insert(mt, 2, (void *)0x5);
2745 mtree_test_insert(mt, ULONG_MAX - 10, (void *)0xffffffffffffffeb);
2746 mtree_test_erase(mt, ULONG_MAX - 10);
2750 static noinline void __init check_dup_gaps(struct maple_tree *mt,
2758 MA_STATE(mas, mt, 0, 0);
2770 mtree_store_range(mt, i*10, (i+1)*10 - gap,
2778 MT_BUG_ON(mt, ret != 0);
2794 static noinline void __init check_dup(struct maple_tree *mt)
2801 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2802 check_dup_gaps(mt, i, true, 5);
2803 mtree_destroy(mt);
2811 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2812 check_dup_gaps(mt, i, true, 0);
2813 mtree_destroy(mt);
2821 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2822 check_dup_gaps(mt, i, true, 5);
2823 mtree_destroy(mt);
2831 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2832 check_dup_gaps(mt, i, false, 5);
2833 mtree_destroy(mt);
2841 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2842 check_dup_gaps(mt, i, false, 5);
2843 mtree_destroy(mt);
2851 mt_init_flags(mt, 0);
2852 check_dup_gaps(mt, i, false, 5);
2853 mtree_destroy(mt);
2863 mt_init_flags(mt, 0);
2864 check_dup_gaps(mt, i, true, 5);
2865 mtree_destroy(mt);
2873 mt_init_flags(mt, 0);
2874 check_dup_gaps(mt, i, true, 5);
2875 mtree_destroy(mt);
2882 static noinline void __init check_bnode_min_spanning(struct maple_tree *mt)
2885 MA_STATE(mas, mt, 0, 0);
2901 static noinline void __init check_empty_area_window(struct maple_tree *mt)
2904 MA_STATE(mas, mt, 0, 0);
2907 mtree_store_range(mt, i*10, i*10 + 9,
2911 mtree_store_range(mt, 160, 169, NULL, GFP_KERNEL);
2915 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 10) != -EBUSY);
2918 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 6, 90, 5) != -EBUSY);
2922 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 5) != 0);
2923 MT_BUG_ON(mt, mas.index != 5);
2924 MT_BUG_ON(mt, mas.last != 9);
2930 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 217, 9) != 0);
2931 MT_BUG_ON(mt, mas.index != 161);
2932 MT_BUG_ON(mt, mas.last != 169);
2936 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 3) != 0);
2937 MT_BUG_ON(mt, mas.index != 216);
2938 MT_BUG_ON(mt, mas.last != 218);
2942 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 16) != -EBUSY);
2949 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 167, 200, 4) != -EBUSY);
2956 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 162, 4) != -EBUSY);
2960 MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 9) != 0);
2961 MT_BUG_ON(mt, mas.index != 0);
2962 MT_BUG_ON(mt, mas.last != 8);
2965 MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 4) != 0);
2966 MT_BUG_ON(mt, mas.index != 0);
2967 MT_BUG_ON(mt, mas.last != 3);
2970 MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 11) != -EBUSY);
2973 MT_BUG_ON(mt, mas_empty_area(&mas, 5, 100, 6) != -EBUSY);
2976 MT_BUG_ON(mt, mas_empty_area(&mas, 0, 8, 10) != -EINVAL);
2982 MT_BUG_ON(mt, mas_empty_area(&mas, 100, 163, 6) != -EBUSY);
2986 static noinline void __init check_empty_area_fill(struct maple_tree *mt)
2991 MA_STATE(mas, mt, 0, 0);
3000 MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != 0);
3001 MT_BUG_ON(mt, mas.last != mas.index + size - 1);
3011 MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != -EBUSY);
3016 mtree_store_range(mt, i, i + 5, (void *)i, GFP_KERNEL);
3018 mtree_erase(mt, 631668735);
3020 mtree_erase(mt, 629506047);
3024 MT_BUG_ON(mt, mas_empty_area(&mas, 629506048, 690000000, 0x5000) != 0);
3174 static noinline void __init check_state_handling(struct maple_tree *mt)
3176 MA_STATE(mas, mt, 0, 0);
3182 mtree_store_range(mt, 0, 0, ptr, GFP_KERNEL);
3187 MT_BUG_ON(mt, entry != NULL);
3188 MT_BUG_ON(mt, mas.status != ma_underflow);
3193 MT_BUG_ON(mt, entry != ptr);
3194 MT_BUG_ON(mt, mas.index != 0);
3195 MT_BUG_ON(mt, mas.last != 0);
3196 MT_BUG_ON(mt, mas.status != ma_root);
3202 MT_BUG_ON(mt, entry != ptr);
3203 MT_BUG_ON(mt, mas.index != 0);
3204 MT_BUG_ON(mt, mas.last != 0);
3205 MT_BUG_ON(mt, mas.status != ma_root);
3210 MT_BUG_ON(mt, mas.index != 1);
3211 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3212 MT_BUG_ON(mt, entry != NULL);
3213 MT_BUG_ON(mt, mas.status != ma_none);
3218 MT_BUG_ON(mt, mas.index != 1);
3219 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3220 MT_BUG_ON(mt, entry != NULL);
3221 MT_BUG_ON(mt, mas.status != ma_none);
3226 MT_BUG_ON(mt, entry != ptr);
3227 MT_BUG_ON(mt, mas.index != 0);
3228 MT_BUG_ON(mt, mas.last != 0);
3229 MT_BUG_ON(mt, mas.status != ma_root);
3233 MT_BUG_ON(mt, entry != NULL);
3234 MT_BUG_ON(mt, mas.index != 1);
3235 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3236 MT_BUG_ON(mt, mas.status != ma_none);
3240 MT_BUG_ON(mt, entry != NULL);
3241 MT_BUG_ON(mt, mas.index != 1);
3242 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3243 MT_BUG_ON(mt, mas.status != ma_none);
3248 MT_BUG_ON(mt, entry != NULL);
3249 MT_BUG_ON(mt, mas.index != 1);
3250 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3251 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 MT_BUG_ON(mt, entry != ptr);
3264 MT_BUG_ON(mt, mas.index != 0);
3265 MT_BUG_ON(mt, mas.last != 0);
3266 MT_BUG_ON(mt, mas.status != ma_root);
3270 MT_BUG_ON(mt, entry != NULL);
3271 MT_BUG_ON(mt, mas.index != 0);
3272 MT_BUG_ON(mt, mas.last != 0);
3273 MT_BUG_ON(mt, mas.status != ma_none);
3277 MT_BUG_ON(mt, entry != NULL);
3278 MT_BUG_ON(mt, mas.index != 0);
3279 MT_BUG_ON(mt, mas.last != 0);
3280 MT_BUG_ON(mt, mas.status != ma_none);
3285 MT_BUG_ON(mt, entry != ptr);
3286 MT_BUG_ON(mt, mas.index != 0);
3287 MT_BUG_ON(mt, mas.last != 0);
3288 MT_BUG_ON(mt, mas.status != ma_root);
3293 MT_BUG_ON(mt, entry != NULL);
3294 MT_BUG_ON(mt, mas.index != 1);
3295 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3296 MT_BUG_ON(mt, mas.status != ma_none);
3302 MT_BUG_ON(mt, entry != NULL);
3303 MT_BUG_ON(mt, mas.index != 1);
3304 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3305 MT_BUG_ON(mt, mas.status != ma_none);
3310 MT_BUG_ON(mt, entry != NULL);
3311 MT_BUG_ON(mt, mas.index != 1);
3312 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3313 MT_BUG_ON(mt, mas.status != ma_none);
3317 MT_BUG_ON(mt, entry != NULL);
3318 MT_BUG_ON(mt, mas.index != 1);
3319 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3320 MT_BUG_ON(mt, mas.status != ma_none);
3325 MT_BUG_ON(mt, entry != ptr);
3326 MT_BUG_ON(mt, mas.index != 0);
3327 MT_BUG_ON(mt, mas.last != 0);
3328 MT_BUG_ON(mt, mas.status != ma_root);
3334 MT_BUG_ON(mt, entry != ptr);
3335 MT_BUG_ON(mt, mas.index != 0);
3336 MT_BUG_ON(mt, mas.last != 0);
3337 MT_BUG_ON(mt, mas.status != ma_root);
3342 MT_BUG_ON(mt, entry != ptr);
3343 MT_BUG_ON(mt, mas.index != 0);
3344 MT_BUG_ON(mt, mas.last != 0);
3345 MT_BUG_ON(mt, mas.status != ma_root);
3349 MT_BUG_ON(mt, entry != ptr);
3350 MT_BUG_ON(mt, mas.index != 0);
3351 MT_BUG_ON(mt, mas.last != 0);
3352 MT_BUG_ON(mt, mas.status != ma_root);
3357 MT_BUG_ON(mt, entry != NULL);
3358 MT_BUG_ON(mt, mas.index != 1);
3359 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3360 MT_BUG_ON(mt, mas.status != ma_none);
3365 MT_BUG_ON(mt, entry != ptr);
3366 MT_BUG_ON(mt, mas.index != 0);
3367 MT_BUG_ON(mt, mas.last != 0);
3368 MT_BUG_ON(mt, mas.status != ma_root);
3373 mtree_store_range(mt, 0, 0, NULL, GFP_KERNEL);
3374 mtree_store_range(mt, 0x1000, 0x1500, ptr, GFP_KERNEL);
3375 mtree_store_range(mt, 0x2000, 0x2500, ptr2, GFP_KERNEL);
3376 mtree_store_range(mt, 0x3000, 0x3500, ptr3, GFP_KERNEL);
3383 MT_BUG_ON(mt, entry != ptr);
3384 MT_BUG_ON(mt, mas.index != 0x1000);
3385 MT_BUG_ON(mt, mas.last != 0x1500);
3386 MT_BUG_ON(mt, !mas_is_active(&mas));
3392 MT_BUG_ON(mt, entry != ptr);
3393 MT_BUG_ON(mt, mas.index != 0x1000);
3394 MT_BUG_ON(mt, mas.last != 0x1500);
3395 MT_BUG_ON(mt, !mas_is_active(&mas));
3402 MT_BUG_ON(mt, entry != ptr);
3403 MT_BUG_ON(mt, mas.index != 0x1000);
3404 MT_BUG_ON(mt, mas.last != 0x1500);
3405 MT_BUG_ON(mt, !mas_is_active(&mas));
3409 MT_BUG_ON(mt, entry != ptr2);
3410 MT_BUG_ON(mt, mas.index != 0x2000);
3411 MT_BUG_ON(mt, mas.last != 0x2500);
3412 MT_BUG_ON(mt, !mas_is_active(&mas));
3416 MT_BUG_ON(mt, entry != NULL);
3417 MT_BUG_ON(mt, mas.index != 0x2501);
3418 MT_BUG_ON(mt, mas.last != 0x2fff);
3419 MT_BUG_ON(mt, !mas_is_overflow(&mas));
3423 MT_BUG_ON(mt, entry != ptr3);
3424 MT_BUG_ON(mt, mas.index != 0x3000);
3425 MT_BUG_ON(mt, mas.last != 0x3500);
3426 MT_BUG_ON(mt, !mas_is_active(&mas));
3430 MT_BUG_ON(mt, entry != NULL);
3431 MT_BUG_ON(mt, mas.index != 0x3501);
3432 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3433 MT_BUG_ON(mt, !mas_is_overflow(&mas));
3437 MT_BUG_ON(mt, entry != NULL);
3438 MT_BUG_ON(mt, mas.index != 0x3501);
3439 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3440 MT_BUG_ON(mt, !mas_is_overflow(&mas));
3444 MT_BUG_ON(mt, entry != ptr3);
3445 MT_BUG_ON(mt, mas.index != 0x3000);
3446 MT_BUG_ON(mt, mas.last != 0x3500);
3447 MT_BUG_ON(mt, !mas_is_active(&mas));
3455 MT_BUG_ON(mt, entry != ptr2);
3456 MT_BUG_ON(mt, mas.index != 0x2000);
3457 MT_BUG_ON(mt, mas.last != 0x2500);
3458 MT_BUG_ON(mt, !mas_is_active(&mas));
3462 MT_BUG_ON(mt, entry != ptr);
3463 MT_BUG_ON(mt, mas.index != 0x1000);
3464 MT_BUG_ON(mt, mas.last != 0x1500);
3465 MT_BUG_ON(mt, !mas_is_active(&mas));
3470 MT_BUG_ON(mt, entry != ptr);
3471 MT_BUG_ON(mt, mas.index != 0x1000);
3472 MT_BUG_ON(mt, mas.last != 0x1500);
3473 MT_BUG_ON(mt, !mas_is_active(&mas)); /* spanning limit */
3475 MT_BUG_ON(mt, entry != NULL);
3476 MT_BUG_ON(mt, mas.index != 0x1000);
3477 MT_BUG_ON(mt, mas.last != 0x1500);
3478 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3482 MT_BUG_ON(mt, entry != NULL);
3483 MT_BUG_ON(mt, mas.index != 0);
3484 MT_BUG_ON(mt, mas.last != 0x0FFF);
3485 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3489 MT_BUG_ON(mt, entry != NULL);
3490 MT_BUG_ON(mt, mas.index != 0);
3491 MT_BUG_ON(mt, mas.last != 0x0FFF);
3492 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3496 MT_BUG_ON(mt, entry != NULL);
3497 MT_BUG_ON(mt, mas.index != 0);
3498 MT_BUG_ON(mt, mas.last != 0x0FFF);
3499 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3503 MT_BUG_ON(mt, entry != ptr);
3504 MT_BUG_ON(mt, mas.index != 0x1000);
3505 MT_BUG_ON(mt, mas.last != 0x1500);
3506 MT_BUG_ON(mt, !mas_is_active(&mas));
3510 MT_BUG_ON(mt, entry != NULL);
3511 MT_BUG_ON(mt, mas.index != 0x1000);
3512 MT_BUG_ON(mt, mas.last != 0x1500);
3513 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3517 MT_BUG_ON(mt, entry != ptr);
3518 MT_BUG_ON(mt, mas.index != 0x1000);
3519 MT_BUG_ON(mt, mas.last != 0x1500);
3520 MT_BUG_ON(mt, !mas_is_active(&mas));
3525 MT_BUG_ON(mt, entry != ptr3);
3528 MT_BUG_ON(mt, entry != ptr2);
3529 MT_BUG_ON(mt, mas.index != 0x2000);
3530 MT_BUG_ON(mt, mas.last != 0x2500);
3531 MT_BUG_ON(mt, !mas_is_active(&mas));
3535 MT_BUG_ON(mt, entry != NULL);
3536 MT_BUG_ON(mt, mas.index != 0x1501);
3537 MT_BUG_ON(mt, mas.last != 0x1FFF);
3538 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3542 MT_BUG_ON(mt, entry != ptr);
3543 MT_BUG_ON(mt, mas.index != 0x1000);
3544 MT_BUG_ON(mt, mas.last != 0x1500);
3545 MT_BUG_ON(mt, !mas_is_active(&mas));
3550 MT_BUG_ON(mt, entry != ptr);
3551 MT_BUG_ON(mt, mas.index != 0x1000);
3552 MT_BUG_ON(mt, mas.last != 0x1500);
3553 MT_BUG_ON(mt, !mas_is_active(&mas));
3559 MT_BUG_ON(mt, entry != ptr);
3560 MT_BUG_ON(mt, mas.index != 0x1000);
3561 MT_BUG_ON(mt, mas.last != 0x1500);
3562 MT_BUG_ON(mt, !mas_is_active(&mas));
3567 MT_BUG_ON(mt, entry != ptr);
3568 MT_BUG_ON(mt, mas.index != 0x1000);
3569 MT_BUG_ON(mt, mas.last != 0x1500);
3570 MT_BUG_ON(mt, !mas_is_active(&mas));
3574 MT_BUG_ON(mt, entry != ptr2);
3575 MT_BUG_ON(mt, mas.index != 0x2000);
3576 MT_BUG_ON(mt, mas.last != 0x2500);
3577 MT_BUG_ON(mt, !mas_is_active(&mas));
3582 MT_BUG_ON(mt, entry != NULL);
3583 MT_BUG_ON(mt, mas.index != 0x2501);
3584 MT_BUG_ON(mt, mas.last != 0x2FFF);
3589 MT_BUG_ON(mt, entry != ptr3);
3590 MT_BUG_ON(mt, mas.index != 0x3000);
3591 MT_BUG_ON(mt, mas.last != 0x3500);
3592 MT_BUG_ON(mt, !mas_is_active(&mas));
3596 MT_BUG_ON(mt, entry != NULL);
3597 MT_BUG_ON(mt, mas.index != 0x3501);
3598 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3603 MT_BUG_ON(mt, entry != ptr3);
3604 MT_BUG_ON(mt, mas.index != 0x3000);
3605 MT_BUG_ON(mt, mas.last != 0x3500);
3606 MT_BUG_ON(mt, !mas_is_active(&mas));
3610 MT_BUG_ON(mt, entry != ptr2);
3611 MT_BUG_ON(mt, mas.index != 0x2000);
3612 MT_BUG_ON(mt, mas.last != 0x2500);
3613 MT_BUG_ON(mt, !mas_is_active(&mas));
3618 MT_BUG_ON(mt, entry != ptr);
3619 MT_BUG_ON(mt, mas.index != 0x1000);
3620 MT_BUG_ON(mt, mas.last != 0x1500);
3621 MT_BUG_ON(mt, !mas_is_active(&mas));
3625 MT_BUG_ON(mt, entry != NULL);
3626 MT_BUG_ON(mt, mas.index != 0);
3627 MT_BUG_ON(mt, mas.last != 0x0FFF);
3628 MT_BUG_ON(mt, !mas_is_underflow(&mas));
3633 MT_BUG_ON(mt, entry != ptr);
3634 MT_BUG_ON(mt, mas.index != 0x1000);
3635 MT_BUG_ON(mt, mas.last != 0x1500);
3636 MT_BUG_ON(mt, !mas_is_active(&mas));
3641 MT_BUG_ON(mt, entry != ptr);
3642 MT_BUG_ON(mt, mas.index != 0x1000);
3643 MT_BUG_ON(mt, mas.last != 0x1500);
3644 MT_BUG_ON(mt, !mas_is_active(&mas));
3649 MT_BUG_ON(mt, entry != NULL);
3650 MT_BUG_ON(mt, mas.index != 0x1501);
3651 MT_BUG_ON(mt, mas.last != 0x1fff);
3652 MT_BUG_ON(mt, !mas_is_active(&mas));
3658 MT_BUG_ON(mt, entry != ptr);
3659 MT_BUG_ON(mt, mas.index != 0x1000);
3660 MT_BUG_ON(mt, mas.last != 0x1500);
3661 MT_BUG_ON(mt, !mas_is_active(&mas));
3667 MT_BUG_ON(mt, entry != NULL);
3668 MT_BUG_ON(mt, mas.index != 0x1501);
3669 MT_BUG_ON(mt, mas.last != 0x1fff);
3670 MT_BUG_ON(mt, !mas_is_active(&mas));
3676 MT_BUG_ON(mt, entry != ptr);
3677 MT_BUG_ON(mt, mas.index != 0x1000);
3678 MT_BUG_ON(mt, mas.last != 0x1500);
3679 MT_BUG_ON(mt, !mas_is_active(&mas));
3685 MT_BUG_ON(mt, entry != NULL);
3686 MT_BUG_ON(mt, mas.index != 0x1501);
3687 MT_BUG_ON(mt, mas.last != 0x1fff);
3688 MT_BUG_ON(mt, !mas_is_active(&mas));
3695 MT_BUG_ON(mt, entry != ptr);
3696 MT_BUG_ON(mt, mas.index != 0x1000);
3697 MT_BUG_ON(mt, mas.last != 0x1500);
3698 MT_BUG_ON(mt, !mas_is_active(&mas));
3704 MT_BUG_ON(mt, entry != NULL);
3705 MT_BUG_ON(mt, mas.index != 0x1501);
3706 MT_BUG_ON(mt, mas.last != 0x1fff);
3707 MT_BUG_ON(mt, !mas_is_active(&mas));
3712 static noinline void __init alloc_cyclic_testing(struct maple_tree *mt)
3717 MA_STATE(mas, mt, 0, 0);
3720 mtree_lock(mt);
3722 mas_alloc_cyclic(&mas, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3729 mtree_unlock(mt);
3730 mtree_destroy(mt);
3732 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
3734 mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3735 MT_BUG_ON(mt, i != location - 2);
3736 MT_BUG_ON(mt, i != next - 3);
3737 MT_BUG_ON(mt, mtree_load(mt, location) != mt);
3740 mtree_destroy(mt);
3749 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
3751 mtree_alloc_cyclic(mt, &location, mt, 2, 1024, &next, GFP_KERNEL);
3752 MT_BUG_ON(mt, i != location - 2);
3753 MT_BUG_ON(mt, i != next - 3);
3754 MT_BUG_ON(mt, mtree_load(mt, location) != mt);
3756 mtree_erase(mt, 123);
3757 MT_BUG_ON(mt, mtree_load(mt, 123) != NULL);
3758 mtree_alloc_cyclic(mt, &location, mt, 2, 1024, &next, GFP_KERNEL);
3759 MT_BUG_ON(mt, 123 != location);
3760 MT_BUG_ON(mt, 124 != next);
3761 MT_BUG_ON(mt, mtree_load(mt, location) != mt);
3762 mtree_erase(mt, 100);
3763 mtree_alloc_cyclic(mt, &location, mt, 2, 1024, &next, GFP_KERNEL);
3764 MT_BUG_ON(mt, 100 != location);
3765 MT_BUG_ON(mt, 101 != next);
3766 MT_BUG_ON(mt, mtree_load(mt, location) != mt);
3767 mtree_destroy(mt);
3771 ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3772 MT_BUG_ON(mt, ret != 0);
3773 ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3774 MT_BUG_ON(mt, ret != 0);
3775 ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3776 MT_BUG_ON(mt, ret != 1);