]> git.ipfire.org Git - thirdparty/linux.git/blob - lib/test_maple_tree.c
projects / thirdparty / linux.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
ARM: tegra: Reuse I2C3 for NVEC
[thirdparty/linux.git] / lib / test_maple_tree.c
1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3 * test_maple_tree.c: Test the maple tree API
4 * Copyright (c) 2018-2022 Oracle Corporation
5 * Author: Liam R. Howlett <Liam.Howlett@Oracle.com>
6 *
7 * Any tests that only require the interface of the tree.
8 */
9
10 #include <linux/maple_tree.h>
11 #include <linux/module.h>
12
13 #define MTREE_ALLOC_MAX 0x2000000000000Ul
14 #define CONFIG_MAPLE_SEARCH
15 #define MAPLE_32BIT (MAPLE_NODE_SLOTS > 31)
16
17 #ifndef CONFIG_DEBUG_MAPLE_TREE
18 #define mt_dump(mt, fmt) do {} while (0)
19 #define mt_validate(mt) do {} while (0)
20 #define mt_cache_shrink() do {} while (0)
21 #define mas_dump(mas) do {} while (0)
22 #define mas_wr_dump(mas) do {} while (0)
23 atomic_t maple_tree_tests_run;
24 atomic_t maple_tree_tests_passed;
25 #undef MT_BUG_ON
26
27 #define MT_BUG_ON(__tree, __x) do { \
28 atomic_inc(&maple_tree_tests_run); \
29 if (__x) { \
30 pr_info("BUG at %s:%d (%u)\n", \
31 __func__, __LINE__, __x); \
32 pr_info("Pass: %u Run:%u\n", \
33 atomic_read(&maple_tree_tests_passed), \
34 atomic_read(&maple_tree_tests_run)); \
35 } else { \
36 atomic_inc(&maple_tree_tests_passed); \
37 } \
38 } while (0)
39 #endif
40
41 /* #define BENCH_SLOT_STORE */
42 /* #define BENCH_NODE_STORE */
43 /* #define BENCH_AWALK */
44 /* #define BENCH_WALK */
45 /* #define BENCH_MT_FOR_EACH */
46 /* #define BENCH_FORK */
47
48 #ifdef __KERNEL__
49 #define mt_set_non_kernel(x) do {} while (0)
50 #define mt_zero_nr_tallocated(x) do {} while (0)
51 #else
52 #define cond_resched() do {} while (0)
53 #endif
54 static int __init mtree_insert_index(struct maple_tree *mt,
55 unsigned long index, gfp_t gfp)
56 {
57 return mtree_insert(mt, index, xa_mk_value(index & LONG_MAX), gfp);
58 }
59
60 static void __init mtree_erase_index(struct maple_tree *mt, unsigned long index)
61 {
62 MT_BUG_ON(mt, mtree_erase(mt, index) != xa_mk_value(index & LONG_MAX));
63 MT_BUG_ON(mt, mtree_load(mt, index) != NULL);
64 }
65
66 static int __init mtree_test_insert(struct maple_tree *mt, unsigned long index,
67 void *ptr)
68 {
69 return mtree_insert(mt, index, ptr, GFP_KERNEL);
70 }
71
72 static int __init mtree_test_store_range(struct maple_tree *mt,
73 unsigned long start, unsigned long end, void *ptr)
74 {
75 return mtree_store_range(mt, start, end, ptr, GFP_KERNEL);
76 }
77
78 static int __init mtree_test_store(struct maple_tree *mt, unsigned long start,
79 void *ptr)
80 {
81 return mtree_test_store_range(mt, start, start, ptr);
82 }
83
84 static int __init mtree_test_insert_range(struct maple_tree *mt,
85 unsigned long start, unsigned long end, void *ptr)
86 {
87 return mtree_insert_range(mt, start, end, ptr, GFP_KERNEL);
88 }
89
90 static void __init *mtree_test_load(struct maple_tree *mt, unsigned long index)
91 {
92 return mtree_load(mt, index);
93 }
94
95 static void __init *mtree_test_erase(struct maple_tree *mt, unsigned long index)
96 {
97 return mtree_erase(mt, index);
98 }
99
100 #if defined(CONFIG_64BIT)
101 static noinline void __init check_mtree_alloc_range(struct maple_tree *mt,
102 unsigned long start, unsigned long end, unsigned long size,
103 unsigned long expected, int eret, void *ptr)
104 {
105
106 unsigned long result = expected + 1;
107 int ret;
108
109 ret = mtree_alloc_range(mt, &result, ptr, size, start, end,
110 GFP_KERNEL);
111 MT_BUG_ON(mt, ret != eret);
112 if (ret)
113 return;
114
115 MT_BUG_ON(mt, result != expected);
116 }
117
118 static noinline void __init check_mtree_alloc_rrange(struct maple_tree *mt,
119 unsigned long start, unsigned long end, unsigned long size,
120 unsigned long expected, int eret, void *ptr)
121 {
122
123 unsigned long result = expected + 1;
124 int ret;
125
126 ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end,
127 GFP_KERNEL);
128 MT_BUG_ON(mt, ret != eret);
129 if (ret)
130 return;
131
132 MT_BUG_ON(mt, result != expected);
133 }
134 #endif
135
136 static noinline void __init check_load(struct maple_tree *mt,
137 unsigned long index, void *ptr)
138 {
139 void *ret = mtree_test_load(mt, index);
140
141 if (ret != ptr)
142 pr_err("Load %lu returned %p expect %p\n", index, ret, ptr);
143 MT_BUG_ON(mt, ret != ptr);
144 }
145
146 static noinline void __init check_store_range(struct maple_tree *mt,
147 unsigned long start, unsigned long end, void *ptr, int expected)
148 {
149 int ret = -EINVAL;
150 unsigned long i;
151
152 ret = mtree_test_store_range(mt, start, end, ptr);
153 MT_BUG_ON(mt, ret != expected);
154
155 if (ret)
156 return;
157
158 for (i = start; i <= end; i++)
159 check_load(mt, i, ptr);
160 }
161
162 static noinline void __init check_insert_range(struct maple_tree *mt,
163 unsigned long start, unsigned long end, void *ptr, int expected)
164 {
165 int ret = -EINVAL;
166 unsigned long i;
167
168 ret = mtree_test_insert_range(mt, start, end, ptr);
169 MT_BUG_ON(mt, ret != expected);
170
171 if (ret)
172 return;
173
174 for (i = start; i <= end; i++)
175 check_load(mt, i, ptr);
176 }
177
178 static noinline void __init check_insert(struct maple_tree *mt,
179 unsigned long index, void *ptr)
180 {
181 int ret = -EINVAL;
182
183 ret = mtree_test_insert(mt, index, ptr);
184 MT_BUG_ON(mt, ret != 0);
185 }
186
187 static noinline void __init check_dup_insert(struct maple_tree *mt,
188 unsigned long index, void *ptr)
189 {
190 int ret = -EINVAL;
191
192 ret = mtree_test_insert(mt, index, ptr);
193 MT_BUG_ON(mt, ret != -EEXIST);
194 }
195
196
197 static noinline void __init check_index_load(struct maple_tree *mt,
198 unsigned long index)
199 {
200 return check_load(mt, index, xa_mk_value(index & LONG_MAX));
201 }
202
203 static inline __init int not_empty(struct maple_node *node)
204 {
205 int i;
206
207 if (node->parent)
208 return 1;
209
210 for (i = 0; i < ARRAY_SIZE(node->slot); i++)
211 if (node->slot[i])
212 return 1;
213
214 return 0;
215 }
216
217
218 static noinline void __init check_rev_seq(struct maple_tree *mt,
219 unsigned long max, bool verbose)
220 {
221 unsigned long i = max, j;
222
223 MT_BUG_ON(mt, !mtree_empty(mt));
224
225 mt_zero_nr_tallocated();
226 while (i) {
227 MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL));
228 for (j = i; j <= max; j++)
229 check_index_load(mt, j);
230
231 check_load(mt, i - 1, NULL);
232 mt_set_in_rcu(mt);
233 MT_BUG_ON(mt, !mt_height(mt));
234 mt_clear_in_rcu(mt);
235 MT_BUG_ON(mt, !mt_height(mt));
236 i--;
237 }
238 check_load(mt, max + 1, NULL);
239
240 #ifndef __KERNEL__
241 if (verbose) {
242 rcu_barrier();
243 mt_dump(mt, mt_dump_dec);
244 pr_info(" %s test of 0-%lu %luK in %d active (%d total)\n",
245 __func__, max, mt_get_alloc_size()/1024, mt_nr_allocated(),
246 mt_nr_tallocated());
247 }
248 #endif
249 }
250
251 static noinline void __init check_seq(struct maple_tree *mt, unsigned long max,
252 bool verbose)
253 {
254 unsigned long i, j;
255
256 MT_BUG_ON(mt, !mtree_empty(mt));
257
258 mt_zero_nr_tallocated();
259 for (i = 0; i <= max; i++) {
260 MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL));
261 for (j = 0; j <= i; j++)
262 check_index_load(mt, j);
263
264 if (i)
265 MT_BUG_ON(mt, !mt_height(mt));
266 check_load(mt, i + 1, NULL);
267 }
268
269 #ifndef __KERNEL__
270 if (verbose) {
271 rcu_barrier();
272 mt_dump(mt, mt_dump_dec);
273 pr_info(" seq test of 0-%lu %luK in %d active (%d total)\n",
274 max, mt_get_alloc_size()/1024, mt_nr_allocated(),
275 mt_nr_tallocated());
276 }
277 #endif
278 }
279
280 static noinline void __init check_lb_not_empty(struct maple_tree *mt)
281 {
282 unsigned long i, j;
283 unsigned long huge = 4000UL * 1000 * 1000;
284
285
286 i = huge;
287 while (i > 4096) {
288 check_insert(mt, i, (void *) i);
289 for (j = huge; j >= i; j /= 2) {
290 check_load(mt, j-1, NULL);
291 check_load(mt, j, (void *) j);
292 check_load(mt, j+1, NULL);
293 }
294 i /= 2;
295 }
296 mtree_destroy(mt);
297 }
298
299 static noinline void __init check_lower_bound_split(struct maple_tree *mt)
300 {
301 MT_BUG_ON(mt, !mtree_empty(mt));
302 check_lb_not_empty(mt);
303 }
304
305 static noinline void __init check_upper_bound_split(struct maple_tree *mt)
306 {
307 unsigned long i, j;
308 unsigned long huge;
309
310 MT_BUG_ON(mt, !mtree_empty(mt));
311
312 if (MAPLE_32BIT)
313 huge = 2147483647UL;
314 else
315 huge = 4000UL * 1000 * 1000;
316
317 i = 4096;
318 while (i < huge) {
319 check_insert(mt, i, (void *) i);
320 for (j = i; j >= huge; j *= 2) {
321 check_load(mt, j-1, NULL);
322 check_load(mt, j, (void *) j);
323 check_load(mt, j+1, NULL);
324 }
325 i *= 2;
326 }
327 mtree_destroy(mt);
328 }
329
330 static noinline void __init check_mid_split(struct maple_tree *mt)
331 {
332 unsigned long huge = 8000UL * 1000 * 1000;
333
334 check_insert(mt, huge, (void *) huge);
335 check_insert(mt, 0, xa_mk_value(0));
336 check_lb_not_empty(mt);
337 }
338
339 static noinline void __init check_rev_find(struct maple_tree *mt)
340 {
341 int i, nr_entries = 200;
342 void *val;
343 MA_STATE(mas, mt, 0, 0);
344
345 for (i = 0; i <= nr_entries; i++)
346 mtree_store_range(mt, i*10, i*10 + 5,
347 xa_mk_value(i), GFP_KERNEL);
348
349 rcu_read_lock();
350 mas_set(&mas, 1000);
351 val = mas_find_rev(&mas, 1000);
352 MT_BUG_ON(mt, val != xa_mk_value(100));
353 val = mas_find_rev(&mas, 1000);
354 MT_BUG_ON(mt, val != NULL);
355
356 mas_set(&mas, 999);
357 val = mas_find_rev(&mas, 997);
358 MT_BUG_ON(mt, val != NULL);
359
360 mas_set(&mas, 1000);
361 val = mas_find_rev(&mas, 900);
362 MT_BUG_ON(mt, val != xa_mk_value(100));
363 val = mas_find_rev(&mas, 900);
364 MT_BUG_ON(mt, val != xa_mk_value(99));
365
366 mas_set(&mas, 20);
367 val = mas_find_rev(&mas, 0);
368 MT_BUG_ON(mt, val != xa_mk_value(2));
369 val = mas_find_rev(&mas, 0);
370 MT_BUG_ON(mt, val != xa_mk_value(1));
371 val = mas_find_rev(&mas, 0);
372 MT_BUG_ON(mt, val != xa_mk_value(0));
373 val = mas_find_rev(&mas, 0);
374 MT_BUG_ON(mt, val != NULL);
375 rcu_read_unlock();
376 }
377
378 static noinline void __init check_find(struct maple_tree *mt)
379 {
380 unsigned long val = 0;
381 unsigned long count;
382 unsigned long max;
383 unsigned long top;
384 unsigned long last = 0, index = 0;
385 void *entry, *entry2;
386
387 MA_STATE(mas, mt, 0, 0);
388
389 /* Insert 0. */
390 MT_BUG_ON(mt, mtree_insert_index(mt, val++, GFP_KERNEL));
391
392 #if defined(CONFIG_64BIT)
393 top = 4398046511104UL;
394 #else
395 top = ULONG_MAX;
396 #endif
397
398 if (MAPLE_32BIT) {
399 count = 15;
400 } else {
401 count = 20;
402 }
403
404 for (int i = 0; i <= count; i++) {
405 if (val != 64)
406 MT_BUG_ON(mt, mtree_insert_index(mt, val, GFP_KERNEL));
407 else
408 MT_BUG_ON(mt, mtree_insert(mt, val,
409 XA_ZERO_ENTRY, GFP_KERNEL));
410
411 val <<= 2;
412 }
413
414 val = 0;
415 mas_set(&mas, val);
416 mas_lock(&mas);
417 while ((entry = mas_find(&mas, 268435456)) != NULL) {
418 if (val != 64)
419 MT_BUG_ON(mt, xa_mk_value(val) != entry);
420 else
421 MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
422
423 val <<= 2;
424 /* For zero check. */
425 if (!val)
426 val = 1;
427 }
428 mas_unlock(&mas);
429
430 val = 0;
431 mas_set(&mas, val);
432 mas_lock(&mas);
433 mas_for_each(&mas, entry, ULONG_MAX) {
434 if (val != 64)
435 MT_BUG_ON(mt, xa_mk_value(val) != entry);
436 else
437 MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
438 val <<= 2;
439 /* For zero check. */
440 if (!val)
441 val = 1;
442 }
443 mas_unlock(&mas);
444
445 /* Test mas_pause */
446 val = 0;
447 mas_set(&mas, val);
448 mas_lock(&mas);
449 mas_for_each(&mas, entry, ULONG_MAX) {
450 if (val != 64)
451 MT_BUG_ON(mt, xa_mk_value(val) != entry);
452 else
453 MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
454 val <<= 2;
455 /* For zero check. */
456 if (!val)
457 val = 1;
458
459 mas_pause(&mas);
460 mas_unlock(&mas);
461 mas_lock(&mas);
462 }
463 mas_unlock(&mas);
464
465 val = 0;
466 max = 300; /* A value big enough to include XA_ZERO_ENTRY at 64. */
467 mt_for_each(mt, entry, index, max) {
468 MT_BUG_ON(mt, xa_mk_value(val) != entry);
469 val <<= 2;
470 if (val == 64) /* Skip zero entry. */
471 val <<= 2;
472 /* For zero check. */
473 if (!val)
474 val = 1;
475 }
476
477 val = 0;
478 max = 0;
479 index = 0;
480 MT_BUG_ON(mt, mtree_insert_index(mt, ULONG_MAX, GFP_KERNEL));
481 mt_for_each(mt, entry, index, ULONG_MAX) {
482 if (val == top)
483 MT_BUG_ON(mt, entry != xa_mk_value(LONG_MAX));
484 else
485 MT_BUG_ON(mt, xa_mk_value(val) != entry);
486
487 /* Workaround for 32bit */
488 if ((val << 2) < val)
489 val = ULONG_MAX;
490 else
491 val <<= 2;
492
493 if (val == 64) /* Skip zero entry. */
494 val <<= 2;
495 /* For zero check. */
496 if (!val)
497 val = 1;
498 max++;
499 MT_BUG_ON(mt, max > 25);
500 }
501 mtree_erase_index(mt, ULONG_MAX);
502
503 mas_reset(&mas);
504 index = 17;
505 entry = mt_find(mt, &index, 512);
506 MT_BUG_ON(mt, xa_mk_value(256) != entry);
507
508 mas_reset(&mas);
509 index = 17;
510 entry = mt_find(mt, &index, 20);
511 MT_BUG_ON(mt, entry != NULL);
512
513
514 /* Range check.. */
515 /* Insert ULONG_MAX */
516 MT_BUG_ON(mt, mtree_insert_index(mt, ULONG_MAX, GFP_KERNEL));
517
518 val = 0;
519 mas_set(&mas, 0);
520 mas_lock(&mas);
521 mas_for_each(&mas, entry, ULONG_MAX) {
522 if (val == 64)
523 MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
524 else if (val == top)
525 MT_BUG_ON(mt, entry != xa_mk_value(LONG_MAX));
526 else
527 MT_BUG_ON(mt, xa_mk_value(val) != entry);
528
529 /* Workaround for 32bit */
530 if ((val << 2) < val)
531 val = ULONG_MAX;
532 else
533 val <<= 2;
534
535 /* For zero check. */
536 if (!val)
537 val = 1;
538 mas_pause(&mas);
539 mas_unlock(&mas);
540 mas_lock(&mas);
541 }
542 mas_unlock(&mas);
543
544 mas_set(&mas, 1048576);
545 mas_lock(&mas);
546 entry = mas_find(&mas, 1048576);
547 mas_unlock(&mas);
548 MT_BUG_ON(mas.tree, entry == NULL);
549
550 /*
551 * Find last value.
552 * 1. get the expected value, leveraging the existence of an end entry
553 * 2. delete end entry
554 * 3. find the last value but searching for ULONG_MAX and then using
555 * prev
556 */
557 /* First, get the expected result. */
558 mas_lock(&mas);
559 mas_reset(&mas);
560 mas.index = ULONG_MAX; /* start at max.. */
561 entry = mas_find(&mas, ULONG_MAX);
562 entry = mas_prev(&mas, 0);
563 index = mas.index;
564 last = mas.last;
565
566 /* Erase the last entry. */
567 mas_reset(&mas);
568 mas.index = ULONG_MAX;
569 mas.last = ULONG_MAX;
570 mas_erase(&mas);
571
572 /* Get the previous value from MAS_START */
573 mas_reset(&mas);
574 entry2 = mas_prev(&mas, 0);
575
576 /* Check results. */
577 MT_BUG_ON(mt, entry != entry2);
578 MT_BUG_ON(mt, index != mas.index);
579 MT_BUG_ON(mt, last != mas.last);
580
581
582 mas.node = MAS_NONE;
583 mas.index = ULONG_MAX;
584 mas.last = ULONG_MAX;
585 entry2 = mas_prev(&mas, 0);
586 MT_BUG_ON(mt, entry != entry2);
587
588 mas_set(&mas, 0);
589 MT_BUG_ON(mt, mas_prev(&mas, 0) != NULL);
590
591 mas_unlock(&mas);
592 mtree_destroy(mt);
593 }
594
595 static noinline void __init check_find_2(struct maple_tree *mt)
596 {
597 unsigned long i, j;
598 void *entry;
599
600 MA_STATE(mas, mt, 0, 0);
601 rcu_read_lock();
602 mas_for_each(&mas, entry, ULONG_MAX)
603 MT_BUG_ON(mt, true);
604 rcu_read_unlock();
605
606 for (i = 0; i < 256; i++) {
607 mtree_insert_index(mt, i, GFP_KERNEL);
608 j = 0;
609 mas_set(&mas, 0);
610 rcu_read_lock();
611 mas_for_each(&mas, entry, ULONG_MAX) {
612 MT_BUG_ON(mt, entry != xa_mk_value(j));
613 j++;
614 }
615 rcu_read_unlock();
616 MT_BUG_ON(mt, j != i + 1);
617 }
618
619 for (i = 0; i < 256; i++) {
620 mtree_erase_index(mt, i);
621 j = i + 1;
622 mas_set(&mas, 0);
623 rcu_read_lock();
624 mas_for_each(&mas, entry, ULONG_MAX) {
625 if (xa_is_zero(entry))
626 continue;
627
628 MT_BUG_ON(mt, entry != xa_mk_value(j));
629 j++;
630 }
631 rcu_read_unlock();
632 MT_BUG_ON(mt, j != 256);
633 }
634
635 /*MT_BUG_ON(mt, !mtree_empty(mt)); */
636 }
637
638
639 #if defined(CONFIG_64BIT)
640 static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
641 {
642 /*
643 * Generated by:
644 * cat /proc/self/maps | awk '{print $1}'|
645 * awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}'
646 */
647
648 static const unsigned long range[] = {
649 /* Inclusive , Exclusive. */
650 0x565234af2000, 0x565234af4000,
651 0x565234af4000, 0x565234af9000,
652 0x565234af9000, 0x565234afb000,
653 0x565234afc000, 0x565234afd000,
654 0x565234afd000, 0x565234afe000,
655 0x565235def000, 0x565235e10000,
656 0x7f36d4bfd000, 0x7f36d4ee2000,
657 0x7f36d4ee2000, 0x7f36d4f04000,
658 0x7f36d4f04000, 0x7f36d504c000,
659 0x7f36d504c000, 0x7f36d5098000,
660 0x7f36d5098000, 0x7f36d5099000,
661 0x7f36d5099000, 0x7f36d509d000,
662 0x7f36d509d000, 0x7f36d509f000,
663 0x7f36d509f000, 0x7f36d50a5000,
664 0x7f36d50b9000, 0x7f36d50db000,
665 0x7f36d50db000, 0x7f36d50dc000,
666 0x7f36d50dc000, 0x7f36d50fa000,
667 0x7f36d50fa000, 0x7f36d5102000,
668 0x7f36d5102000, 0x7f36d5103000,
669 0x7f36d5103000, 0x7f36d5104000,
670 0x7f36d5104000, 0x7f36d5105000,
671 0x7fff5876b000, 0x7fff5878d000,
672 0x7fff5878e000, 0x7fff58791000,
673 0x7fff58791000, 0x7fff58793000,
674 };
675
676 static const unsigned long holes[] = {
677 /*
678 * Note: start of hole is INCLUSIVE
679 * end of hole is EXCLUSIVE
680 * (opposite of the above table.)
681 * Start of hole, end of hole, size of hole (+1)
682 */
683 0x565234afb000, 0x565234afc000, 0x1000,
684 0x565234afe000, 0x565235def000, 0x12F1000,
685 0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000,
686 };
687
688 /*
689 * req_range consists of 4 values.
690 * 1. min index
691 * 2. max index
692 * 3. size
693 * 4. number that should be returned.
694 * 5. return value
695 */
696 static const unsigned long req_range[] = {
697 0x565234af9000, /* Min */
698 0x7fff58791000, /* Max */
699 0x1000, /* Size */
700 0x7fff5878d << 12, /* First rev hole of size 0x1000 */
701 0, /* Return value success. */
702
703 0x0, /* Min */
704 0x565234AF0 << 12, /* Max */
705 0x3000, /* Size */
706 0x565234AEE << 12, /* max - 3. */
707 0, /* Return value success. */
708
709 0x0, /* Min */
710 -1, /* Max */
711 0x1000, /* Size */
712 562949953421311 << 12,/* First rev hole of size 0x1000 */
713 0, /* Return value success. */
714
715 0x0, /* Min */
716 0x7F36D5109 << 12, /* Max */
717 0x4000, /* Size */
718 0x7F36D5106 << 12, /* First rev hole of size 0x4000 */
719 0, /* Return value success. */
720
721 /* Ascend test. */
722 0x0,
723 34148798628 << 12,
724 19 << 12,
725 34148797418 << 12,
726 0x0,
727
728 /* Too big test. */
729 0x0,
730 18446744073709551615UL,
731 562915594369134UL << 12,
732 0x0,
733 -EBUSY,
734
735 /* Single space test. */
736 34148798725 << 12,
737 34148798725 << 12,
738 1 << 12,
739 34148798725 << 12,
740 0,
741 };
742
743 int i, range_count = ARRAY_SIZE(range);
744 int req_range_count = ARRAY_SIZE(req_range);
745 unsigned long min = 0;
746
747 MA_STATE(mas, mt, 0, 0);
748
749 mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY,
750 GFP_KERNEL);
751 #define DEBUG_REV_RANGE 0
752 for (i = 0; i < range_count; i += 2) {
753 /* Inclusive, Inclusive (with the -1) */
754
755 #if DEBUG_REV_RANGE
756 pr_debug("\t%s: Insert %lu-%lu\n", __func__, range[i] >> 12,
757 (range[i + 1] >> 12) - 1);
758 #endif
759 check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1,
760 xa_mk_value(range[i] >> 12), 0);
761 mt_validate(mt);
762 }
763
764
765 mas_lock(&mas);
766 for (i = 0; i < ARRAY_SIZE(holes); i += 3) {
767 #if DEBUG_REV_RANGE
768 pr_debug("Search from %lu-%lu for gap %lu should be at %lu\n",
769 min, holes[i+1]>>12, holes[i+2]>>12,
770 holes[i] >> 12);
771 #endif
772 MT_BUG_ON(mt, mas_empty_area_rev(&mas, min,
773 holes[i+1] >> 12,
774 holes[i+2] >> 12));
775 #if DEBUG_REV_RANGE
776 pr_debug("Found %lu %lu\n", mas.index, mas.last);
777 pr_debug("gap %lu %lu\n", (holes[i] >> 12),
778 (holes[i+1] >> 12));
779 #endif
780 MT_BUG_ON(mt, mas.last + 1 != (holes[i+1] >> 12));
781 MT_BUG_ON(mt, mas.index != (holes[i+1] >> 12) - (holes[i+2] >> 12));
782 min = holes[i+1] >> 12;
783 mas_reset(&mas);
784 }
785
786 mas_unlock(&mas);
787 for (i = 0; i < req_range_count; i += 5) {
788 #if DEBUG_REV_RANGE
789 pr_debug("\tReverse request %d between %lu-%lu size %lu, should get %lu\n",
790 i, req_range[i] >> 12,
791 (req_range[i + 1] >> 12),
792 req_range[i+2] >> 12,
793 req_range[i+3] >> 12);
794 #endif
795 check_mtree_alloc_rrange(mt,
796 req_range[i] >> 12, /* start */
797 req_range[i+1] >> 12, /* end */
798 req_range[i+2] >> 12, /* size */
799 req_range[i+3] >> 12, /* expected address */
800 req_range[i+4], /* expected return */
801 xa_mk_value(req_range[i] >> 12)); /* pointer */
802 mt_validate(mt);
803 }
804
805 mt_set_non_kernel(1);
806 mtree_erase(mt, 34148798727); /* create a deleted range. */
807 mtree_erase(mt, 34148798725);
808 check_mtree_alloc_rrange(mt, 0, 34359052173, 210253414,
809 34148798725, 0, mt);
810
811 mtree_destroy(mt);
812 }
813
814 static noinline void __init check_alloc_range(struct maple_tree *mt)
815 {
816 /*
817 * Generated by:
818 * cat /proc/self/maps|awk '{print $1}'|
819 * awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}'
820 */
821
822 static const unsigned long range[] = {
823 /* Inclusive , Exclusive. */
824 0x565234af2000, 0x565234af4000,
825 0x565234af4000, 0x565234af9000,
826 0x565234af9000, 0x565234afb000,
827 0x565234afc000, 0x565234afd000,
828 0x565234afd000, 0x565234afe000,
829 0x565235def000, 0x565235e10000,
830 0x7f36d4bfd000, 0x7f36d4ee2000,
831 0x7f36d4ee2000, 0x7f36d4f04000,
832 0x7f36d4f04000, 0x7f36d504c000,
833 0x7f36d504c000, 0x7f36d5098000,
834 0x7f36d5098000, 0x7f36d5099000,
835 0x7f36d5099000, 0x7f36d509d000,
836 0x7f36d509d000, 0x7f36d509f000,
837 0x7f36d509f000, 0x7f36d50a5000,
838 0x7f36d50b9000, 0x7f36d50db000,
839 0x7f36d50db000, 0x7f36d50dc000,
840 0x7f36d50dc000, 0x7f36d50fa000,
841 0x7f36d50fa000, 0x7f36d5102000,
842 0x7f36d5102000, 0x7f36d5103000,
843 0x7f36d5103000, 0x7f36d5104000,
844 0x7f36d5104000, 0x7f36d5105000,
845 0x7fff5876b000, 0x7fff5878d000,
846 0x7fff5878e000, 0x7fff58791000,
847 0x7fff58791000, 0x7fff58793000,
848 };
849 static const unsigned long holes[] = {
850 /* Start of hole, end of hole, size of hole (+1) */
851 0x565234afb000, 0x565234afc000, 0x1000,
852 0x565234afe000, 0x565235def000, 0x12F1000,
853 0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000,
854 };
855
856 /*
857 * req_range consists of 4 values.
858 * 1. min index
859 * 2. max index
860 * 3. size
861 * 4. number that should be returned.
862 * 5. return value
863 */
864 static const unsigned long req_range[] = {
865 0x565234af9000, /* Min */
866 0x7fff58791000, /* Max */
867 0x1000, /* Size */
868 0x565234afb000, /* First hole in our data of size 1000. */
869 0, /* Return value success. */
870
871 0x0, /* Min */
872 0x7fff58791000, /* Max */
873 0x1F00, /* Size */
874 0x0, /* First hole in our data of size 2000. */
875 0, /* Return value success. */
876
877 /* Test ascend. */
878 34148797436 << 12, /* Min */
879 0x7fff587AF000, /* Max */
880 0x3000, /* Size */
881 34148798629 << 12, /* Expected location */
882 0, /* Return value success. */
883
884 /* Test failing. */
885 34148798623 << 12, /* Min */
886 34148798683 << 12, /* Max */
887 0x15000, /* Size */
888 0, /* Expected location */
889 -EBUSY, /* Return value failed. */
890
891 /* Test filling entire gap. */
892 34148798623 << 12, /* Min */
893 0x7fff587AF000, /* Max */
894 0x10000, /* Size */
895 34148798632 << 12, /* Expected location */
896 0, /* Return value success. */
897
898 /* Test walking off the end of root. */
899 0, /* Min */
900 -1, /* Max */
901 -1, /* Size */
902 0, /* Expected location */
903 -EBUSY, /* Return value failure. */
904
905 /* Test looking for too large a hole across entire range. */
906 0, /* Min */
907 -1, /* Max */
908 4503599618982063UL << 12, /* Size */
909 34359052178 << 12, /* Expected location */
910 -EBUSY, /* Return failure. */
911
912 /* Test a single entry */
913 34148798648 << 12, /* Min */
914 34148798648 << 12, /* Max */
915 4096, /* Size of 1 */
916 34148798648 << 12, /* Location is the same as min/max */
917 0, /* Success */
918 };
919 int i, range_count = ARRAY_SIZE(range);
920 int req_range_count = ARRAY_SIZE(req_range);
921 unsigned long min = 0x565234af2000;
922 MA_STATE(mas, mt, 0, 0);
923
924 mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY,
925 GFP_KERNEL);
926 for (i = 0; i < range_count; i += 2) {
927 #define DEBUG_ALLOC_RANGE 0
928 #if DEBUG_ALLOC_RANGE
929 pr_debug("\tInsert %lu-%lu\n", range[i] >> 12,
930 (range[i + 1] >> 12) - 1);
931 mt_dump(mt, mt_dump_hex);
932 #endif
933 check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1,
934 xa_mk_value(range[i] >> 12), 0);
935 mt_validate(mt);
936 }
937
938
939
940 mas_lock(&mas);
941 for (i = 0; i < ARRAY_SIZE(holes); i += 3) {
942
943 #if DEBUG_ALLOC_RANGE
944 pr_debug("\tGet empty %lu-%lu size %lu (%lx-%lx)\n", min >> 12,
945 holes[i+1] >> 12, holes[i+2] >> 12,
946 min, holes[i+1]);
947 #endif
948 MT_BUG_ON(mt, mas_empty_area(&mas, min >> 12,
949 holes[i+1] >> 12,
950 holes[i+2] >> 12));
951 MT_BUG_ON(mt, mas.index != holes[i] >> 12);
952 min = holes[i+1];
953 mas_reset(&mas);
954 }
955 mas_unlock(&mas);
956 for (i = 0; i < req_range_count; i += 5) {
957 #if DEBUG_ALLOC_RANGE
958 pr_debug("\tTest %d: %lu-%lu size %lu expected %lu (%lu-%lu)\n",
959 i/5, req_range[i] >> 12, req_range[i + 1] >> 12,
960 req_range[i + 2] >> 12, req_range[i + 3] >> 12,
961 req_range[i], req_range[i+1]);
962 #endif
963 check_mtree_alloc_range(mt,
964 req_range[i] >> 12, /* start */
965 req_range[i+1] >> 12, /* end */
966 req_range[i+2] >> 12, /* size */
967 req_range[i+3] >> 12, /* expected address */
968 req_range[i+4], /* expected return */
969 xa_mk_value(req_range[i] >> 12)); /* pointer */
970 mt_validate(mt);
971 #if DEBUG_ALLOC_RANGE
972 mt_dump(mt, mt_dump_hex);
973 #endif
974 }
975
976 mtree_destroy(mt);
977 }
978 #endif
979
980 static noinline void __init check_ranges(struct maple_tree *mt)
981 {
982 int i, val, val2;
983 static const unsigned long r[] = {
984 10, 15,
985 20, 25,
986 17, 22, /* Overlaps previous range. */
987 9, 1000, /* Huge. */
988 100, 200,
989 45, 168,
990 118, 128,
991 };
992
993 MT_BUG_ON(mt, !mtree_empty(mt));
994 check_insert_range(mt, r[0], r[1], xa_mk_value(r[0]), 0);
995 check_insert_range(mt, r[2], r[3], xa_mk_value(r[2]), 0);
996 check_insert_range(mt, r[4], r[5], xa_mk_value(r[4]), -EEXIST);
997 MT_BUG_ON(mt, !mt_height(mt));
998 /* Store */
999 check_store_range(mt, r[4], r[5], xa_mk_value(r[4]), 0);
1000 check_store_range(mt, r[6], r[7], xa_mk_value(r[6]), 0);
1001 check_store_range(mt, r[8], r[9], xa_mk_value(r[8]), 0);
1002 MT_BUG_ON(mt, !mt_height(mt));
1003 mtree_destroy(mt);
1004 MT_BUG_ON(mt, mt_height(mt));
1005
1006 check_seq(mt, 50, false);
1007 mt_set_non_kernel(4);
1008 check_store_range(mt, 5, 47, xa_mk_value(47), 0);
1009 MT_BUG_ON(mt, !mt_height(mt));
1010 mtree_destroy(mt);
1011
1012 /* Create tree of 1-100 */
1013 check_seq(mt, 100, false);
1014 /* Store 45-168 */
1015 mt_set_non_kernel(10);
1016 check_store_range(mt, r[10], r[11], xa_mk_value(r[10]), 0);
1017 MT_BUG_ON(mt, !mt_height(mt));
1018 mtree_destroy(mt);
1019
1020 /* Create tree of 1-200 */
1021 check_seq(mt, 200, false);
1022 /* Store 45-168 */
1023 check_store_range(mt, r[10], r[11], xa_mk_value(r[10]), 0);
1024 MT_BUG_ON(mt, !mt_height(mt));
1025 mtree_destroy(mt);
1026
1027 check_seq(mt, 30, false);
1028 check_store_range(mt, 6, 18, xa_mk_value(6), 0);
1029 MT_BUG_ON(mt, !mt_height(mt));
1030 mtree_destroy(mt);
1031
1032 /* Overwrite across multiple levels. */
1033 /* Create tree of 1-400 */
1034 check_seq(mt, 400, false);
1035 mt_set_non_kernel(50);
1036 /* Store 118-128 */
1037 check_store_range(mt, r[12], r[13], xa_mk_value(r[12]), 0);
1038 mt_set_non_kernel(50);
1039 mtree_test_erase(mt, 140);
1040 mtree_test_erase(mt, 141);
1041 mtree_test_erase(mt, 142);
1042 mtree_test_erase(mt, 143);
1043 mtree_test_erase(mt, 130);
1044 mtree_test_erase(mt, 131);
1045 mtree_test_erase(mt, 132);
1046 mtree_test_erase(mt, 133);
1047 mtree_test_erase(mt, 134);
1048 mtree_test_erase(mt, 135);
1049 check_load(mt, r[12], xa_mk_value(r[12]));
1050 check_load(mt, r[13], xa_mk_value(r[12]));
1051 check_load(mt, r[13] - 1, xa_mk_value(r[12]));
1052 check_load(mt, r[13] + 1, xa_mk_value(r[13] + 1));
1053 check_load(mt, 135, NULL);
1054 check_load(mt, 140, NULL);
1055 mt_set_non_kernel(0);
1056 MT_BUG_ON(mt, !mt_height(mt));
1057 mtree_destroy(mt);
1058
1059
1060
1061 /* Overwrite multiple levels at the end of the tree (slot 7) */
1062 mt_set_non_kernel(50);
1063 check_seq(mt, 400, false);
1064 check_store_range(mt, 353, 361, xa_mk_value(353), 0);
1065 check_store_range(mt, 347, 352, xa_mk_value(347), 0);
1066
1067 check_load(mt, 346, xa_mk_value(346));
1068 for (i = 347; i <= 352; i++)
1069 check_load(mt, i, xa_mk_value(347));
1070 for (i = 353; i <= 361; i++)
1071 check_load(mt, i, xa_mk_value(353));
1072 check_load(mt, 362, xa_mk_value(362));
1073 mt_set_non_kernel(0);
1074 MT_BUG_ON(mt, !mt_height(mt));
1075 mtree_destroy(mt);
1076
1077 mt_set_non_kernel(50);
1078 check_seq(mt, 400, false);
1079 check_store_range(mt, 352, 364, NULL, 0);
1080 check_store_range(mt, 351, 363, xa_mk_value(352), 0);
1081 check_load(mt, 350, xa_mk_value(350));
1082 check_load(mt, 351, xa_mk_value(352));
1083 for (i = 352; i <= 363; i++)
1084 check_load(mt, i, xa_mk_value(352));
1085 check_load(mt, 364, NULL);
1086 check_load(mt, 365, xa_mk_value(365));
1087 mt_set_non_kernel(0);
1088 MT_BUG_ON(mt, !mt_height(mt));
1089 mtree_destroy(mt);
1090
1091 mt_set_non_kernel(5);
1092 check_seq(mt, 400, false);
1093 check_store_range(mt, 352, 364, NULL, 0);
1094 check_store_range(mt, 351, 364, xa_mk_value(352), 0);
1095 check_load(mt, 350, xa_mk_value(350));
1096 check_load(mt, 351, xa_mk_value(352));
1097 for (i = 352; i <= 364; i++)
1098 check_load(mt, i, xa_mk_value(352));
1099 check_load(mt, 365, xa_mk_value(365));
1100 mt_set_non_kernel(0);
1101 MT_BUG_ON(mt, !mt_height(mt));
1102 mtree_destroy(mt);
1103
1104
1105 mt_set_non_kernel(50);
1106 check_seq(mt, 400, false);
1107 check_store_range(mt, 362, 367, xa_mk_value(362), 0);
1108 check_store_range(mt, 353, 361, xa_mk_value(353), 0);
1109 mt_set_non_kernel(0);
1110 mt_validate(mt);
1111 MT_BUG_ON(mt, !mt_height(mt));
1112 mtree_destroy(mt);
1113 /*
1114 * Interesting cases:
1115 * 1. Overwrite the end of a node and end in the first entry of the next
1116 * node.
1117 * 2. Split a single range
1118 * 3. Overwrite the start of a range
1119 * 4. Overwrite the end of a range
1120 * 5. Overwrite the entire range
1121 * 6. Overwrite a range that causes multiple parent nodes to be
1122 * combined
1123 * 7. Overwrite a range that causes multiple parent nodes and part of
1124 * root to be combined
1125 * 8. Overwrite the whole tree
1126 * 9. Try to overwrite the zero entry of an alloc tree.
1127 * 10. Write a range larger than a nodes current pivot
1128 */
1129
1130 mt_set_non_kernel(50);
1131 for (i = 0; i <= 500; i++) {
1132 val = i*5;
1133 val2 = (i+1)*5;
1134 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1135 }
1136 check_store_range(mt, 2400, 2400, xa_mk_value(2400), 0);
1137 check_store_range(mt, 2411, 2411, xa_mk_value(2411), 0);
1138 check_store_range(mt, 2412, 2412, xa_mk_value(2412), 0);
1139 check_store_range(mt, 2396, 2400, xa_mk_value(4052020), 0);
1140 check_store_range(mt, 2402, 2402, xa_mk_value(2402), 0);
1141 mtree_destroy(mt);
1142 mt_set_non_kernel(0);
1143
1144 mt_set_non_kernel(50);
1145 for (i = 0; i <= 500; i++) {
1146 val = i*5;
1147 val2 = (i+1)*5;
1148 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1149 }
1150 check_store_range(mt, 2422, 2422, xa_mk_value(2422), 0);
1151 check_store_range(mt, 2424, 2424, xa_mk_value(2424), 0);
1152 check_store_range(mt, 2425, 2425, xa_mk_value(2), 0);
1153 check_store_range(mt, 2460, 2470, NULL, 0);
1154 check_store_range(mt, 2435, 2460, xa_mk_value(2435), 0);
1155 check_store_range(mt, 2461, 2470, xa_mk_value(2461), 0);
1156 mt_set_non_kernel(0);
1157 MT_BUG_ON(mt, !mt_height(mt));
1158 mtree_destroy(mt);
1159
1160 /* Test rebalance gaps */
1161 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1162 mt_set_non_kernel(50);
1163 for (i = 0; i <= 50; i++) {
1164 val = i*10;
1165 val2 = (i+1)*10;
1166 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1167 }
1168 check_store_range(mt, 161, 161, xa_mk_value(161), 0);
1169 check_store_range(mt, 162, 162, xa_mk_value(162), 0);
1170 check_store_range(mt, 163, 163, xa_mk_value(163), 0);
1171 check_store_range(mt, 240, 249, NULL, 0);
1172 mtree_erase(mt, 200);
1173 mtree_erase(mt, 210);
1174 mtree_erase(mt, 220);
1175 mtree_erase(mt, 230);
1176 mt_set_non_kernel(0);
1177 MT_BUG_ON(mt, !mt_height(mt));
1178 mtree_destroy(mt);
1179
1180 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1181 for (i = 0; i <= 500; i++) {
1182 val = i*10;
1183 val2 = (i+1)*10;
1184 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1185 }
1186 check_store_range(mt, 4600, 4959, xa_mk_value(1), 0);
1187 mt_validate(mt);
1188 MT_BUG_ON(mt, !mt_height(mt));
1189 mtree_destroy(mt);
1190
1191 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1192 for (i = 0; i <= 500; i++) {
1193 val = i*10;
1194 val2 = (i+1)*10;
1195 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1196 }
1197 check_store_range(mt, 4811, 4811, xa_mk_value(4811), 0);
1198 check_store_range(mt, 4812, 4812, xa_mk_value(4812), 0);
1199 check_store_range(mt, 4861, 4861, xa_mk_value(4861), 0);
1200 check_store_range(mt, 4862, 4862, xa_mk_value(4862), 0);
1201 check_store_range(mt, 4842, 4849, NULL, 0);
1202 mt_validate(mt);
1203 MT_BUG_ON(mt, !mt_height(mt));
1204 mtree_destroy(mt);
1205
1206 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1207 for (i = 0; i <= 1300; i++) {
1208 val = i*10;
1209 val2 = (i+1)*10;
1210 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1211 MT_BUG_ON(mt, mt_height(mt) >= 4);
1212 }
1213 /* Cause a 3 child split all the way up the tree. */
1214 for (i = 5; i < 215; i += 10)
1215 check_store_range(mt, 11450 + i, 11450 + i + 1, NULL, 0);
1216 for (i = 5; i < 65; i += 10)
1217 check_store_range(mt, 11770 + i, 11770 + i + 1, NULL, 0);
1218
1219 MT_BUG_ON(mt, mt_height(mt) >= 4);
1220 for (i = 5; i < 45; i += 10)
1221 check_store_range(mt, 11700 + i, 11700 + i + 1, NULL, 0);
1222 if (!MAPLE_32BIT)
1223 MT_BUG_ON(mt, mt_height(mt) < 4);
1224 mtree_destroy(mt);
1225
1226
1227 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1228 for (i = 0; i <= 1200; i++) {
1229 val = i*10;
1230 val2 = (i+1)*10;
1231 check_store_range(mt, val, val2, xa_mk_value(val), 0);
1232 MT_BUG_ON(mt, mt_height(mt) >= 4);
1233 }
1234 /* Fill parents and leaves before split. */
1235 for (i = 5; i < 455; i += 10)
1236 check_store_range(mt, 7800 + i, 7800 + i + 1, NULL, 0);
1237
1238 for (i = 1; i < 16; i++)
1239 check_store_range(mt, 8185 + i, 8185 + i + 1,
1240 xa_mk_value(8185+i), 0);
1241 MT_BUG_ON(mt, mt_height(mt) >= 4);
1242 /* triple split across multiple levels. */
1243 check_store_range(mt, 8184, 8184, xa_mk_value(8184), 0);
1244 if (!MAPLE_32BIT)
1245 MT_BUG_ON(mt, mt_height(mt) != 4);
1246 }
1247
1248 static noinline void __init check_next_entry(struct maple_tree *mt)
1249 {
1250 void *entry = NULL;
1251 unsigned long limit = 30, i = 0;
1252 MA_STATE(mas, mt, i, i);
1253
1254 MT_BUG_ON(mt, !mtree_empty(mt));
1255
1256 check_seq(mt, limit, false);
1257 rcu_read_lock();
1258
1259 /* Check the first one and get ma_state in the correct state. */
1260 MT_BUG_ON(mt, mas_walk(&mas) != xa_mk_value(i++));
1261 for ( ; i <= limit + 1; i++) {
1262 entry = mas_next(&mas, limit);
1263 if (i > limit)
1264 MT_BUG_ON(mt, entry != NULL);
1265 else
1266 MT_BUG_ON(mt, xa_mk_value(i) != entry);
1267 }
1268 rcu_read_unlock();
1269 mtree_destroy(mt);
1270 }
1271
1272 static noinline void __init check_prev_entry(struct maple_tree *mt)
1273 {
1274 unsigned long index = 16;
1275 void *value;
1276 int i;
1277
1278 MA_STATE(mas, mt, index, index);
1279
1280 MT_BUG_ON(mt, !mtree_empty(mt));
1281 check_seq(mt, 30, false);
1282
1283 rcu_read_lock();
1284 value = mas_find(&mas, ULONG_MAX);
1285 MT_BUG_ON(mt, value != xa_mk_value(index));
1286 value = mas_prev(&mas, 0);
1287 MT_BUG_ON(mt, value != xa_mk_value(index - 1));
1288 rcu_read_unlock();
1289 mtree_destroy(mt);
1290
1291 /* Check limits on prev */
1292 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1293 mas_lock(&mas);
1294 for (i = 0; i <= index; i++) {
1295 mas_set_range(&mas, i*10, i*10+5);
1296 mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL);
1297 }
1298
1299 mas_set(&mas, 20);
1300 value = mas_walk(&mas);
1301 MT_BUG_ON(mt, value != xa_mk_value(2));
1302
1303 value = mas_prev(&mas, 19);
1304 MT_BUG_ON(mt, value != NULL);
1305
1306 mas_set(&mas, 80);
1307 value = mas_walk(&mas);
1308 MT_BUG_ON(mt, value != xa_mk_value(8));
1309
1310 value = mas_prev(&mas, 76);
1311 MT_BUG_ON(mt, value != NULL);
1312
1313 mas_unlock(&mas);
1314 }
1315
1316 static noinline void __init check_root_expand(struct maple_tree *mt)
1317 {
1318 MA_STATE(mas, mt, 0, 0);
1319 void *ptr;
1320
1321
1322 mas_lock(&mas);
1323 mas_set(&mas, 3);
1324 ptr = mas_walk(&mas);
1325 MT_BUG_ON(mt, mas.index != 0);
1326 MT_BUG_ON(mt, ptr != NULL);
1327 MT_BUG_ON(mt, mas.index != 0);
1328 MT_BUG_ON(mt, mas.last != ULONG_MAX);
1329
1330 ptr = &check_prev_entry;
1331 mas_set(&mas, 1);
1332 mas_store_gfp(&mas, ptr, GFP_KERNEL);
1333
1334 mas_set(&mas, 0);
1335 ptr = mas_walk(&mas);
1336 MT_BUG_ON(mt, ptr != NULL);
1337
1338 mas_set(&mas, 1);
1339 ptr = mas_walk(&mas);
1340 MT_BUG_ON(mt, ptr != &check_prev_entry);
1341
1342 mas_set(&mas, 2);
1343 ptr = mas_walk(&mas);
1344 MT_BUG_ON(mt, ptr != NULL);
1345 mas_unlock(&mas);
1346 mtree_destroy(mt);
1347
1348
1349 mt_init_flags(mt, 0);
1350 mas_lock(&mas);
1351
1352 mas_set(&mas, 0);
1353 ptr = &check_prev_entry;
1354 mas_store_gfp(&mas, ptr, GFP_KERNEL);
1355
1356 mas_set(&mas, 5);
1357 ptr = mas_walk(&mas);
1358 MT_BUG_ON(mt, ptr != NULL);
1359 MT_BUG_ON(mt, mas.index != 1);
1360 MT_BUG_ON(mt, mas.last != ULONG_MAX);
1361
1362 mas_set_range(&mas, 0, 100);
1363 ptr = mas_walk(&mas);
1364 MT_BUG_ON(mt, ptr != &check_prev_entry);
1365 MT_BUG_ON(mt, mas.last != 0);
1366 mas_unlock(&mas);
1367 mtree_destroy(mt);
1368
1369 mt_init_flags(mt, 0);
1370 mas_lock(&mas);
1371
1372 mas_set(&mas, 0);
1373 ptr = (void *)((unsigned long) check_prev_entry | 1UL);
1374 mas_store_gfp(&mas, ptr, GFP_KERNEL);
1375 ptr = mas_next(&mas, ULONG_MAX);
1376 MT_BUG_ON(mt, ptr != NULL);
1377 MT_BUG_ON(mt, (mas.index != 1) && (mas.last != ULONG_MAX));
1378
1379 mas_set(&mas, 1);
1380 ptr = mas_prev(&mas, 0);
1381 MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0));
1382 MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 1UL));
1383
1384 mas_unlock(&mas);
1385
1386 mtree_destroy(mt);
1387
1388 mt_init_flags(mt, 0);
1389 mas_lock(&mas);
1390 mas_set(&mas, 0);
1391 ptr = (void *)((unsigned long) check_prev_entry | 2UL);
1392 mas_store_gfp(&mas, ptr, GFP_KERNEL);
1393 ptr = mas_next(&mas, ULONG_MAX);
1394 MT_BUG_ON(mt, ptr != NULL);
1395 MT_BUG_ON(mt, (mas.index != ULONG_MAX) && (mas.last != ULONG_MAX));
1396
1397 mas_set(&mas, 1);
1398 ptr = mas_prev(&mas, 0);
1399 MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0));
1400 MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 2UL));
1401
1402
1403 mas_unlock(&mas);
1404 }
1405
1406 static noinline void __init check_gap_combining(struct maple_tree *mt)
1407 {
1408 struct maple_enode *mn1, *mn2;
1409 void *entry;
1410 unsigned long singletons = 100;
1411 static const unsigned long *seq100;
1412 static const unsigned long seq100_64[] = {
1413 /* 0-5 */
1414 74, 75, 76,
1415 50, 100, 2,
1416
1417 /* 6-12 */
1418 44, 45, 46, 43,
1419 20, 50, 3,
1420
1421 /* 13-20*/
1422 80, 81, 82,
1423 76, 2, 79, 85, 4,
1424 };
1425
1426 static const unsigned long seq100_32[] = {
1427 /* 0-5 */
1428 61, 62, 63,
1429 50, 100, 2,
1430
1431 /* 6-12 */
1432 31, 32, 33, 30,
1433 20, 50, 3,
1434
1435 /* 13-20*/
1436 80, 81, 82,
1437 76, 2, 79, 85, 4,
1438 };
1439
1440 static const unsigned long seq2000[] = {
1441 1152, 1151,
1442 1100, 1200, 2,
1443 };
1444 static const unsigned long seq400[] = {
1445 286, 318,
1446 256, 260, 266, 270, 275, 280, 290, 398,
1447 286, 310,
1448 };
1449
1450 unsigned long index;
1451
1452 MA_STATE(mas, mt, 0, 0);
1453
1454 if (MAPLE_32BIT)
1455 seq100 = seq100_32;
1456 else
1457 seq100 = seq100_64;
1458
1459 index = seq100[0];
1460 mas_set(&mas, index);
1461 MT_BUG_ON(mt, !mtree_empty(mt));
1462 check_seq(mt, singletons, false); /* create 100 singletons. */
1463
1464 mt_set_non_kernel(1);
1465 mtree_test_erase(mt, seq100[2]);
1466 check_load(mt, seq100[2], NULL);
1467 mtree_test_erase(mt, seq100[1]);
1468 check_load(mt, seq100[1], NULL);
1469
1470 rcu_read_lock();
1471 entry = mas_find(&mas, ULONG_MAX);
1472 MT_BUG_ON(mt, entry != xa_mk_value(index));
1473 mn1 = mas.node;
1474 mas_next(&mas, ULONG_MAX);
1475 entry = mas_next(&mas, ULONG_MAX);
1476 MT_BUG_ON(mt, entry != xa_mk_value(index + 4));
1477 mn2 = mas.node;
1478 MT_BUG_ON(mt, mn1 == mn2); /* test the test. */
1479
1480 /*
1481 * At this point, there is a gap of 2 at index + 1 between seq100[3] and
1482 * seq100[4]. Search for the gap.
1483 */
1484 mt_set_non_kernel(1);
1485 mas_reset(&mas);
1486 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[3], seq100[4],
1487 seq100[5]));
1488 MT_BUG_ON(mt, mas.index != index + 1);
1489 rcu_read_unlock();
1490
1491 mtree_test_erase(mt, seq100[6]);
1492 check_load(mt, seq100[6], NULL);
1493 mtree_test_erase(mt, seq100[7]);
1494 check_load(mt, seq100[7], NULL);
1495 mtree_test_erase(mt, seq100[8]);
1496 index = seq100[9];
1497
1498 rcu_read_lock();
1499 mas.index = index;
1500 mas.last = index;
1501 mas_reset(&mas);
1502 entry = mas_find(&mas, ULONG_MAX);
1503 MT_BUG_ON(mt, entry != xa_mk_value(index));
1504 mn1 = mas.node;
1505 entry = mas_next(&mas, ULONG_MAX);
1506 MT_BUG_ON(mt, entry != xa_mk_value(index + 4));
1507 mas_next(&mas, ULONG_MAX); /* go to the next entry. */
1508 mn2 = mas.node;
1509 MT_BUG_ON(mt, mn1 == mn2); /* test the next entry is in the next node. */
1510
1511 /*
1512 * At this point, there is a gap of 3 at seq100[6]. Find it by
1513 * searching 20 - 50 for size 3.
1514 */
1515 mas_reset(&mas);
1516 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[10], seq100[11],
1517 seq100[12]));
1518 MT_BUG_ON(mt, mas.index != seq100[6]);
1519 rcu_read_unlock();
1520
1521 mt_set_non_kernel(1);
1522 mtree_store(mt, seq100[13], NULL, GFP_KERNEL);
1523 check_load(mt, seq100[13], NULL);
1524 check_load(mt, seq100[14], xa_mk_value(seq100[14]));
1525 mtree_store(mt, seq100[14], NULL, GFP_KERNEL);
1526 check_load(mt, seq100[13], NULL);
1527 check_load(mt, seq100[14], NULL);
1528
1529 mas_reset(&mas);
1530 rcu_read_lock();
1531 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[15],
1532 seq100[17]));
1533 MT_BUG_ON(mt, mas.index != seq100[13]);
1534 mt_validate(mt);
1535 rcu_read_unlock();
1536
1537 /*
1538 * *DEPRECATED: no retries anymore* Test retry entry in the start of a
1539 * gap.
1540 */
1541 mt_set_non_kernel(2);
1542 mtree_test_store_range(mt, seq100[18], seq100[14], NULL);
1543 mtree_test_erase(mt, seq100[15]);
1544 mas_reset(&mas);
1545 rcu_read_lock();
1546 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[19],
1547 seq100[20]));
1548 rcu_read_unlock();
1549 MT_BUG_ON(mt, mas.index != seq100[18]);
1550 mt_validate(mt);
1551 mtree_destroy(mt);
1552
1553 /* seq 2000 tests are for multi-level tree gaps */
1554 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1555 check_seq(mt, 2000, false);
1556 mt_set_non_kernel(1);
1557 mtree_test_erase(mt, seq2000[0]);
1558 mtree_test_erase(mt, seq2000[1]);
1559
1560 mt_set_non_kernel(2);
1561 mas_reset(&mas);
1562 rcu_read_lock();
1563 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq2000[2], seq2000[3],
1564 seq2000[4]));
1565 MT_BUG_ON(mt, mas.index != seq2000[1]);
1566 rcu_read_unlock();
1567 mt_validate(mt);
1568 mtree_destroy(mt);
1569
1570 /* seq 400 tests rebalancing over two levels. */
1571 mt_set_non_kernel(99);
1572 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1573 check_seq(mt, 400, false);
1574 mtree_test_store_range(mt, seq400[0], seq400[1], NULL);
1575 mt_set_non_kernel(0);
1576 mtree_destroy(mt);
1577
1578 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1579 check_seq(mt, 400, false);
1580 mt_set_non_kernel(50);
1581 mtree_test_store_range(mt, seq400[2], seq400[9],
1582 xa_mk_value(seq400[2]));
1583 mtree_test_store_range(mt, seq400[3], seq400[9],
1584 xa_mk_value(seq400[3]));
1585 mtree_test_store_range(mt, seq400[4], seq400[9],
1586 xa_mk_value(seq400[4]));
1587 mtree_test_store_range(mt, seq400[5], seq400[9],
1588 xa_mk_value(seq400[5]));
1589 mtree_test_store_range(mt, seq400[0], seq400[9],
1590 xa_mk_value(seq400[0]));
1591 mtree_test_store_range(mt, seq400[6], seq400[9],
1592 xa_mk_value(seq400[6]));
1593 mtree_test_store_range(mt, seq400[7], seq400[9],
1594 xa_mk_value(seq400[7]));
1595 mtree_test_store_range(mt, seq400[8], seq400[9],
1596 xa_mk_value(seq400[8]));
1597 mtree_test_store_range(mt, seq400[10], seq400[11],
1598 xa_mk_value(seq400[10]));
1599 mt_validate(mt);
1600 mt_set_non_kernel(0);
1601 mtree_destroy(mt);
1602 }
1603 static noinline void __init check_node_overwrite(struct maple_tree *mt)
1604 {
1605 int i, max = 4000;
1606
1607 for (i = 0; i < max; i++)
1608 mtree_test_store_range(mt, i*100, i*100 + 50, xa_mk_value(i*100));
1609
1610 mtree_test_store_range(mt, 319951, 367950, NULL);
1611 /*mt_dump(mt, mt_dump_dec); */
1612 mt_validate(mt);
1613 }
1614
1615 #if defined(BENCH_SLOT_STORE)
1616 static noinline void __init bench_slot_store(struct maple_tree *mt)
1617 {
1618 int i, brk = 105, max = 1040, brk_start = 100, count = 20000000;
1619
1620 for (i = 0; i < max; i += 10)
1621 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1622
1623 for (i = 0; i < count; i++) {
1624 mtree_store_range(mt, brk, brk, NULL, GFP_KERNEL);
1625 mtree_store_range(mt, brk_start, brk, xa_mk_value(brk),
1626 GFP_KERNEL);
1627 }
1628 }
1629 #endif
1630
1631 #if defined(BENCH_NODE_STORE)
1632 static noinline void __init bench_node_store(struct maple_tree *mt)
1633 {
1634 int i, overwrite = 76, max = 240, count = 20000000;
1635
1636 for (i = 0; i < max; i += 10)
1637 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1638
1639 for (i = 0; i < count; i++) {
1640 mtree_store_range(mt, overwrite, overwrite + 15,
1641 xa_mk_value(overwrite), GFP_KERNEL);
1642
1643 overwrite += 5;
1644 if (overwrite >= 135)
1645 overwrite = 76;
1646 }
1647 }
1648 #endif
1649
1650 #if defined(BENCH_AWALK)
1651 static noinline void __init bench_awalk(struct maple_tree *mt)
1652 {
1653 int i, max = 2500, count = 50000000;
1654 MA_STATE(mas, mt, 1470, 1470);
1655
1656 for (i = 0; i < max; i += 10)
1657 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1658
1659 mtree_store_range(mt, 1470, 1475, NULL, GFP_KERNEL);
1660
1661 for (i = 0; i < count; i++) {
1662 mas_empty_area_rev(&mas, 0, 2000, 10);
1663 mas_reset(&mas);
1664 }
1665 }
1666 #endif
1667 #if defined(BENCH_WALK)
1668 static noinline void __init bench_walk(struct maple_tree *mt)
1669 {
1670 int i, max = 2500, count = 550000000;
1671 MA_STATE(mas, mt, 1470, 1470);
1672
1673 for (i = 0; i < max; i += 10)
1674 mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1675
1676 for (i = 0; i < count; i++) {
1677 mas_walk(&mas);
1678 mas_reset(&mas);
1679 }
1680
1681 }
1682 #endif
1683
1684 #if defined(BENCH_MT_FOR_EACH)
1685 static noinline void __init bench_mt_for_each(struct maple_tree *mt)
1686 {
1687 int i, count = 1000000;
1688 unsigned long max = 2500, index = 0;
1689 void *entry;
1690
1691 for (i = 0; i < max; i += 5)
1692 mtree_store_range(mt, i, i + 4, xa_mk_value(i), GFP_KERNEL);
1693
1694 for (i = 0; i < count; i++) {
1695 unsigned long j = 0;
1696
1697 mt_for_each(mt, entry, index, max) {
1698 MT_BUG_ON(mt, entry != xa_mk_value(j));
1699 j += 5;
1700 }
1701
1702 index = 0;
1703 }
1704
1705 }
1706 #endif
1707
1708 /* check_forking - simulate the kernel forking sequence with the tree. */
1709 static noinline void __init check_forking(struct maple_tree *mt)
1710 {
1711
1712 struct maple_tree newmt;
1713 int i, nr_entries = 134;
1714 void *val;
1715 MA_STATE(mas, mt, 0, 0);
1716 MA_STATE(newmas, mt, 0, 0);
1717
1718 for (i = 0; i <= nr_entries; i++)
1719 mtree_store_range(mt, i*10, i*10 + 5,
1720 xa_mk_value(i), GFP_KERNEL);
1721
1722 mt_set_non_kernel(99999);
1723 mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
1724 newmas.tree = &newmt;
1725 mas_reset(&newmas);
1726 mas_reset(&mas);
1727 mas_lock(&newmas);
1728 mas.index = 0;
1729 mas.last = 0;
1730 if (mas_expected_entries(&newmas, nr_entries)) {
1731 pr_err("OOM!");
1732 BUG_ON(1);
1733 }
1734 rcu_read_lock();
1735 mas_for_each(&mas, val, ULONG_MAX) {
1736 newmas.index = mas.index;
1737 newmas.last = mas.last;
1738 mas_store(&newmas, val);
1739 }
1740 rcu_read_unlock();
1741 mas_destroy(&newmas);
1742 mas_unlock(&newmas);
1743 mt_validate(&newmt);
1744 mt_set_non_kernel(0);
1745 mtree_destroy(&newmt);
1746 }
1747
1748 static noinline void __init check_iteration(struct maple_tree *mt)
1749 {
1750 int i, nr_entries = 125;
1751 void *val;
1752 MA_STATE(mas, mt, 0, 0);
1753
1754 for (i = 0; i <= nr_entries; i++)
1755 mtree_store_range(mt, i * 10, i * 10 + 9,
1756 xa_mk_value(i), GFP_KERNEL);
1757
1758 mt_set_non_kernel(99999);
1759
1760 i = 0;
1761 mas_lock(&mas);
1762 mas_for_each(&mas, val, 925) {
1763 MT_BUG_ON(mt, mas.index != i * 10);
1764 MT_BUG_ON(mt, mas.last != i * 10 + 9);
1765 /* Overwrite end of entry 92 */
1766 if (i == 92) {
1767 mas.index = 925;
1768 mas.last = 929;
1769 mas_store(&mas, val);
1770 }
1771 i++;
1772 }
1773 /* Ensure mas_find() gets the next value */
1774 val = mas_find(&mas, ULONG_MAX);
1775 MT_BUG_ON(mt, val != xa_mk_value(i));
1776
1777 mas_set(&mas, 0);
1778 i = 0;
1779 mas_for_each(&mas, val, 785) {
1780 MT_BUG_ON(mt, mas.index != i * 10);
1781 MT_BUG_ON(mt, mas.last != i * 10 + 9);
1782 /* Overwrite start of entry 78 */
1783 if (i == 78) {
1784 mas.index = 780;
1785 mas.last = 785;
1786 mas_store(&mas, val);
1787 } else {
1788 i++;
1789 }
1790 }
1791 val = mas_find(&mas, ULONG_MAX);
1792 MT_BUG_ON(mt, val != xa_mk_value(i));
1793
1794 mas_set(&mas, 0);
1795 i = 0;
1796 mas_for_each(&mas, val, 765) {
1797 MT_BUG_ON(mt, mas.index != i * 10);
1798 MT_BUG_ON(mt, mas.last != i * 10 + 9);
1799 /* Overwrite end of entry 76 and advance to the end */
1800 if (i == 76) {
1801 mas.index = 760;
1802 mas.last = 765;
1803 mas_store(&mas, val);
1804 }
1805 i++;
1806 }
1807 /* Make sure the next find returns the one after 765, 766-769 */
1808 val = mas_find(&mas, ULONG_MAX);
1809 MT_BUG_ON(mt, val != xa_mk_value(76));
1810 mas_unlock(&mas);
1811 mas_destroy(&mas);
1812 mt_set_non_kernel(0);
1813 }
1814
1815 static noinline void __init check_mas_store_gfp(struct maple_tree *mt)
1816 {
1817
1818 struct maple_tree newmt;
1819 int i, nr_entries = 135;
1820 void *val;
1821 MA_STATE(mas, mt, 0, 0);
1822 MA_STATE(newmas, mt, 0, 0);
1823
1824 for (i = 0; i <= nr_entries; i++)
1825 mtree_store_range(mt, i*10, i*10 + 5,
1826 xa_mk_value(i), GFP_KERNEL);
1827
1828 mt_set_non_kernel(99999);
1829 mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
1830 newmas.tree = &newmt;
1831 rcu_read_lock();
1832 mas_lock(&newmas);
1833 mas_reset(&newmas);
1834 mas_set(&mas, 0);
1835 mas_for_each(&mas, val, ULONG_MAX) {
1836 newmas.index = mas.index;
1837 newmas.last = mas.last;
1838 mas_store_gfp(&newmas, val, GFP_KERNEL);
1839 }
1840 mas_unlock(&newmas);
1841 rcu_read_unlock();
1842 mt_validate(&newmt);
1843 mt_set_non_kernel(0);
1844 mtree_destroy(&newmt);
1845 }
1846
1847 #if defined(BENCH_FORK)
1848 static noinline void __init bench_forking(struct maple_tree *mt)
1849 {
1850
1851 struct maple_tree newmt;
1852 int i, nr_entries = 134, nr_fork = 80000;
1853 void *val;
1854 MA_STATE(mas, mt, 0, 0);
1855 MA_STATE(newmas, mt, 0, 0);
1856
1857 for (i = 0; i <= nr_entries; i++)
1858 mtree_store_range(mt, i*10, i*10 + 5,
1859 xa_mk_value(i), GFP_KERNEL);
1860
1861 for (i = 0; i < nr_fork; i++) {
1862 mt_set_non_kernel(99999);
1863 mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
1864 newmas.tree = &newmt;
1865 mas_reset(&newmas);
1866 mas_reset(&mas);
1867 mas.index = 0;
1868 mas.last = 0;
1869 rcu_read_lock();
1870 mas_lock(&newmas);
1871 if (mas_expected_entries(&newmas, nr_entries)) {
1872 printk("OOM!");
1873 BUG_ON(1);
1874 }
1875 mas_for_each(&mas, val, ULONG_MAX) {
1876 newmas.index = mas.index;
1877 newmas.last = mas.last;
1878 mas_store(&newmas, val);
1879 }
1880 mas_destroy(&newmas);
1881 mas_unlock(&newmas);
1882 rcu_read_unlock();
1883 mt_validate(&newmt);
1884 mt_set_non_kernel(0);
1885 mtree_destroy(&newmt);
1886 }
1887 }
1888 #endif
1889
1890 static noinline void __init next_prev_test(struct maple_tree *mt)
1891 {
1892 int i, nr_entries;
1893 void *val;
1894 MA_STATE(mas, mt, 0, 0);
1895 struct maple_enode *mn;
1896 static const unsigned long *level2;
1897 static const unsigned long level2_64[] = { 707, 1000, 710, 715, 720,
1898 725};
1899 static const unsigned long level2_32[] = { 1747, 2000, 1750, 1755,
1900 1760, 1765};
1901
1902 if (MAPLE_32BIT) {
1903 nr_entries = 500;
1904 level2 = level2_32;
1905 } else {
1906 nr_entries = 200;
1907 level2 = level2_64;
1908 }
1909
1910 for (i = 0; i <= nr_entries; i++)
1911 mtree_store_range(mt, i*10, i*10 + 5,
1912 xa_mk_value(i), GFP_KERNEL);
1913
1914 mas_lock(&mas);
1915 for (i = 0; i <= nr_entries / 2; i++) {
1916 mas_next(&mas, 1000);
1917 if (mas_is_none(&mas))
1918 break;
1919
1920 }
1921 mas_reset(&mas);
1922 mas_set(&mas, 0);
1923 i = 0;
1924 mas_for_each(&mas, val, 1000) {
1925 i++;
1926 }
1927
1928 mas_reset(&mas);
1929 mas_set(&mas, 0);
1930 i = 0;
1931 mas_for_each(&mas, val, 1000) {
1932 mas_pause(&mas);
1933 i++;
1934 }
1935
1936 /*
1937 * 680 - 685 = 0x61a00001930c
1938 * 686 - 689 = NULL;
1939 * 690 - 695 = 0x61a00001930c
1940 * Check simple next/prev
1941 */
1942 mas_set(&mas, 686);
1943 val = mas_walk(&mas);
1944 MT_BUG_ON(mt, val != NULL);
1945
1946 val = mas_next(&mas, 1000);
1947 MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
1948 MT_BUG_ON(mt, mas.index != 690);
1949 MT_BUG_ON(mt, mas.last != 695);
1950
1951 val = mas_prev(&mas, 0);
1952 MT_BUG_ON(mt, val != xa_mk_value(680 / 10));
1953 MT_BUG_ON(mt, mas.index != 680);
1954 MT_BUG_ON(mt, mas.last != 685);
1955
1956 val = mas_next(&mas, 1000);
1957 MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
1958 MT_BUG_ON(mt, mas.index != 690);
1959 MT_BUG_ON(mt, mas.last != 695);
1960
1961 val = mas_next(&mas, 1000);
1962 MT_BUG_ON(mt, val != xa_mk_value(700 / 10));
1963 MT_BUG_ON(mt, mas.index != 700);
1964 MT_BUG_ON(mt, mas.last != 705);
1965
1966 /* Check across node boundaries of the tree */
1967 mas_set(&mas, 70);
1968 val = mas_walk(&mas);
1969 MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
1970 MT_BUG_ON(mt, mas.index != 70);
1971 MT_BUG_ON(mt, mas.last != 75);
1972
1973 val = mas_next(&mas, 1000);
1974 MT_BUG_ON(mt, val != xa_mk_value(80 / 10));
1975 MT_BUG_ON(mt, mas.index != 80);
1976 MT_BUG_ON(mt, mas.last != 85);
1977
1978 val = mas_prev(&mas, 70);
1979 MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
1980 MT_BUG_ON(mt, mas.index != 70);
1981 MT_BUG_ON(mt, mas.last != 75);
1982
1983 /* Check across two levels of the tree */
1984 mas_reset(&mas);
1985 mas_set(&mas, level2[0]);
1986 val = mas_walk(&mas);
1987 MT_BUG_ON(mt, val != NULL);
1988 val = mas_next(&mas, level2[1]);
1989 MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
1990 MT_BUG_ON(mt, mas.index != level2[2]);
1991 MT_BUG_ON(mt, mas.last != level2[3]);
1992 mn = mas.node;
1993
1994 val = mas_next(&mas, level2[1]);
1995 MT_BUG_ON(mt, val != xa_mk_value(level2[4] / 10));
1996 MT_BUG_ON(mt, mas.index != level2[4]);
1997 MT_BUG_ON(mt, mas.last != level2[5]);
1998 MT_BUG_ON(mt, mn == mas.node);
1999
2000 val = mas_prev(&mas, 0);
2001 MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
2002 MT_BUG_ON(mt, mas.index != level2[2]);
2003 MT_BUG_ON(mt, mas.last != level2[3]);
2004
2005 /* Check running off the end and back on */
2006 mas_set(&mas, nr_entries * 10);
2007 val = mas_walk(&mas);
2008 MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
2009 MT_BUG_ON(mt, mas.index != (nr_entries * 10));
2010 MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
2011
2012 val = mas_next(&mas, ULONG_MAX);
2013 MT_BUG_ON(mt, val != NULL);
2014 MT_BUG_ON(mt, mas.index != 0x7d6);
2015 MT_BUG_ON(mt, mas.last != ULONG_MAX);
2016
2017 val = mas_prev(&mas, 0);
2018 MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
2019 MT_BUG_ON(mt, mas.index != (nr_entries * 10));
2020 MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
2021
2022 /* Check running off the start and back on */
2023 mas_reset(&mas);
2024 mas_set(&mas, 10);
2025 val = mas_walk(&mas);
2026 MT_BUG_ON(mt, val != xa_mk_value(1));
2027 MT_BUG_ON(mt, mas.index != 10);
2028 MT_BUG_ON(mt, mas.last != 15);
2029
2030 val = mas_prev(&mas, 0);
2031 MT_BUG_ON(mt, val != xa_mk_value(0));
2032 MT_BUG_ON(mt, mas.index != 0);
2033 MT_BUG_ON(mt, mas.last != 5);
2034
2035 val = mas_prev(&mas, 0);
2036 MT_BUG_ON(mt, val != NULL);
2037 MT_BUG_ON(mt, mas.index != 0);
2038 MT_BUG_ON(mt, mas.last != 5);
2039 MT_BUG_ON(mt, mas.node != MAS_NONE);
2040
2041 mas.index = 0;
2042 mas.last = 5;
2043 mas_store(&mas, NULL);
2044 mas_reset(&mas);
2045 mas_set(&mas, 10);
2046 mas_walk(&mas);
2047
2048 val = mas_prev(&mas, 0);
2049 MT_BUG_ON(mt, val != NULL);
2050 MT_BUG_ON(mt, mas.index != 0);
2051 MT_BUG_ON(mt, mas.last != 9);
2052 mas_unlock(&mas);
2053
2054 mtree_destroy(mt);
2055
2056 mt_init(mt);
2057 mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL);
2058 mtree_store_range(mt, 5, 5, xa_mk_value(5), GFP_KERNEL);
2059 rcu_read_lock();
2060 mas_set(&mas, 5);
2061 val = mas_prev(&mas, 4);
2062 MT_BUG_ON(mt, val != NULL);
2063 rcu_read_unlock();
2064 }
2065
2066
2067
2068 /* Test spanning writes that require balancing right sibling or right cousin */
2069 static noinline void __init check_spanning_relatives(struct maple_tree *mt)
2070 {
2071
2072 unsigned long i, nr_entries = 1000;
2073
2074 for (i = 0; i <= nr_entries; i++)
2075 mtree_store_range(mt, i*10, i*10 + 5,
2076 xa_mk_value(i), GFP_KERNEL);
2077
2078
2079 mtree_store_range(mt, 9365, 9955, NULL, GFP_KERNEL);
2080 }
2081
2082 static noinline void __init check_fuzzer(struct maple_tree *mt)
2083 {
2084 /*
2085 * 1. Causes a spanning rebalance of a single root node.
2086 * Fixed by setting the correct limit in mast_cp_to_nodes() when the
2087 * entire right side is consumed.
2088 */
2089 mtree_test_insert(mt, 88, (void *)0xb1);
2090 mtree_test_insert(mt, 84, (void *)0xa9);
2091 mtree_test_insert(mt, 2, (void *)0x5);
2092 mtree_test_insert(mt, 4, (void *)0x9);
2093 mtree_test_insert(mt, 14, (void *)0x1d);
2094 mtree_test_insert(mt, 7, (void *)0xf);
2095 mtree_test_insert(mt, 12, (void *)0x19);
2096 mtree_test_insert(mt, 18, (void *)0x25);
2097 mtree_test_store_range(mt, 8, 18, (void *)0x11);
2098 mtree_destroy(mt);
2099
2100
2101 /*
2102 * 2. Cause a spanning rebalance of two nodes in root.
2103 * Fixed by setting mast->r->max correctly.
2104 */
2105 mt_init_flags(mt, 0);
2106 mtree_test_store(mt, 87, (void *)0xaf);
2107 mtree_test_store(mt, 0, (void *)0x1);
2108 mtree_test_load(mt, 4);
2109 mtree_test_insert(mt, 4, (void *)0x9);
2110 mtree_test_store(mt, 8, (void *)0x11);
2111 mtree_test_store(mt, 44, (void *)0x59);
2112 mtree_test_store(mt, 68, (void *)0x89);
2113 mtree_test_store(mt, 2, (void *)0x5);
2114 mtree_test_insert(mt, 43, (void *)0x57);
2115 mtree_test_insert(mt, 24, (void *)0x31);
2116 mtree_test_insert(mt, 844, (void *)0x699);
2117 mtree_test_store(mt, 84, (void *)0xa9);
2118 mtree_test_store(mt, 4, (void *)0x9);
2119 mtree_test_erase(mt, 4);
2120 mtree_test_load(mt, 5);
2121 mtree_test_erase(mt, 0);
2122 mtree_destroy(mt);
2123
2124 /*
2125 * 3. Cause a node overflow on copy
2126 * Fixed by using the correct check for node size in mas_wr_modify()
2127 * Also discovered issue with metadata setting.
2128 */
2129 mt_init_flags(mt, 0);
2130 mtree_test_store_range(mt, 0, ULONG_MAX, (void *)0x1);
2131 mtree_test_store(mt, 4, (void *)0x9);
2132 mtree_test_erase(mt, 5);
2133 mtree_test_erase(mt, 0);
2134 mtree_test_erase(mt, 4);
2135 mtree_test_store(mt, 5, (void *)0xb);
2136 mtree_test_erase(mt, 5);
2137 mtree_test_store(mt, 5, (void *)0xb);
2138 mtree_test_erase(mt, 5);
2139 mtree_test_erase(mt, 4);
2140 mtree_test_store(mt, 4, (void *)0x9);
2141 mtree_test_store(mt, 444, (void *)0x379);
2142 mtree_test_store(mt, 0, (void *)0x1);
2143 mtree_test_load(mt, 0);
2144 mtree_test_store(mt, 5, (void *)0xb);
2145 mtree_test_erase(mt, 0);
2146 mtree_destroy(mt);
2147
2148 /*
2149 * 4. spanning store failure due to writing incorrect pivot value at
2150 * last slot.
2151 * Fixed by setting mast->r->max correctly in mast_cp_to_nodes()
2152 *
2153 */
2154 mt_init_flags(mt, 0);
2155 mtree_test_insert(mt, 261, (void *)0x20b);
2156 mtree_test_store(mt, 516, (void *)0x409);
2157 mtree_test_store(mt, 6, (void *)0xd);
2158 mtree_test_insert(mt, 5, (void *)0xb);
2159 mtree_test_insert(mt, 1256, (void *)0x9d1);
2160 mtree_test_store(mt, 4, (void *)0x9);
2161 mtree_test_erase(mt, 1);
2162 mtree_test_store(mt, 56, (void *)0x71);
2163 mtree_test_insert(mt, 1, (void *)0x3);
2164 mtree_test_store(mt, 24, (void *)0x31);
2165 mtree_test_erase(mt, 1);
2166 mtree_test_insert(mt, 2263, (void *)0x11af);
2167 mtree_test_insert(mt, 446, (void *)0x37d);
2168 mtree_test_store_range(mt, 6, 45, (void *)0xd);
2169 mtree_test_store_range(mt, 3, 446, (void *)0x7);
2170 mtree_destroy(mt);
2171
2172 /*
2173 * 5. mas_wr_extend_null() may overflow slots.
2174 * Fix by checking against wr_mas->node_end.
2175 */
2176 mt_init_flags(mt, 0);
2177 mtree_test_store(mt, 48, (void *)0x61);
2178 mtree_test_store(mt, 3, (void *)0x7);
2179 mtree_test_load(mt, 0);
2180 mtree_test_store(mt, 88, (void *)0xb1);
2181 mtree_test_store(mt, 81, (void *)0xa3);
2182 mtree_test_insert(mt, 0, (void *)0x1);
2183 mtree_test_insert(mt, 8, (void *)0x11);
2184 mtree_test_insert(mt, 4, (void *)0x9);
2185 mtree_test_insert(mt, 2480, (void *)0x1361);
2186 mtree_test_insert(mt, ULONG_MAX,
2187 (void *)0xffffffffffffffff);
2188 mtree_test_erase(mt, ULONG_MAX);
2189 mtree_destroy(mt);
2190
2191 /*
2192 * 6. When reusing a node with an implied pivot and the node is
2193 * shrinking, old data would be left in the implied slot
2194 * Fixed by checking the last pivot for the mas->max and clear
2195 * accordingly. This only affected the left-most node as that node is
2196 * the only one allowed to end in NULL.
2197 */
2198 mt_init_flags(mt, 0);
2199 mtree_test_erase(mt, 3);
2200 mtree_test_insert(mt, 22, (void *)0x2d);
2201 mtree_test_insert(mt, 15, (void *)0x1f);
2202 mtree_test_load(mt, 2);
2203 mtree_test_insert(mt, 1, (void *)0x3);
2204 mtree_test_insert(mt, 1, (void *)0x3);
2205 mtree_test_insert(mt, 5, (void *)0xb);
2206 mtree_test_erase(mt, 1);
2207 mtree_test_insert(mt, 1, (void *)0x3);
2208 mtree_test_insert(mt, 4, (void *)0x9);
2209 mtree_test_insert(mt, 1, (void *)0x3);
2210 mtree_test_erase(mt, 1);
2211 mtree_test_insert(mt, 2, (void *)0x5);
2212 mtree_test_insert(mt, 1, (void *)0x3);
2213 mtree_test_erase(mt, 3);
2214 mtree_test_insert(mt, 22, (void *)0x2d);
2215 mtree_test_insert(mt, 15, (void *)0x1f);
2216 mtree_test_insert(mt, 2, (void *)0x5);
2217 mtree_test_insert(mt, 1, (void *)0x3);
2218 mtree_test_insert(mt, 8, (void *)0x11);
2219 mtree_test_load(mt, 2);
2220 mtree_test_insert(mt, 1, (void *)0x3);
2221 mtree_test_insert(mt, 1, (void *)0x3);
2222 mtree_test_store(mt, 1, (void *)0x3);
2223 mtree_test_insert(mt, 5, (void *)0xb);
2224 mtree_test_erase(mt, 1);
2225 mtree_test_insert(mt, 1, (void *)0x3);
2226 mtree_test_insert(mt, 4, (void *)0x9);
2227 mtree_test_insert(mt, 1, (void *)0x3);
2228 mtree_test_erase(mt, 1);
2229 mtree_test_insert(mt, 2, (void *)0x5);
2230 mtree_test_insert(mt, 1, (void *)0x3);
2231 mtree_test_erase(mt, 3);
2232 mtree_test_insert(mt, 22, (void *)0x2d);
2233 mtree_test_insert(mt, 15, (void *)0x1f);
2234 mtree_test_insert(mt, 2, (void *)0x5);
2235 mtree_test_insert(mt, 1, (void *)0x3);
2236 mtree_test_insert(mt, 8, (void *)0x11);
2237 mtree_test_insert(mt, 12, (void *)0x19);
2238 mtree_test_erase(mt, 1);
2239 mtree_test_store_range(mt, 4, 62, (void *)0x9);
2240 mtree_test_erase(mt, 62);
2241 mtree_test_store_range(mt, 1, 0, (void *)0x3);
2242 mtree_test_insert(mt, 11, (void *)0x17);
2243 mtree_test_insert(mt, 3, (void *)0x7);
2244 mtree_test_insert(mt, 3, (void *)0x7);
2245 mtree_test_store(mt, 62, (void *)0x7d);
2246 mtree_test_erase(mt, 62);
2247 mtree_test_store_range(mt, 1, 15, (void *)0x3);
2248 mtree_test_erase(mt, 1);
2249 mtree_test_insert(mt, 22, (void *)0x2d);
2250 mtree_test_insert(mt, 12, (void *)0x19);
2251 mtree_test_erase(mt, 1);
2252 mtree_test_insert(mt, 3, (void *)0x7);
2253 mtree_test_store(mt, 62, (void *)0x7d);
2254 mtree_test_erase(mt, 62);
2255 mtree_test_insert(mt, 122, (void *)0xf5);
2256 mtree_test_store(mt, 3, (void *)0x7);
2257 mtree_test_insert(mt, 0, (void *)0x1);
2258 mtree_test_store_range(mt, 0, 1, (void *)0x1);
2259 mtree_test_insert(mt, 85, (void *)0xab);
2260 mtree_test_insert(mt, 72, (void *)0x91);
2261 mtree_test_insert(mt, 81, (void *)0xa3);
2262 mtree_test_insert(mt, 726, (void *)0x5ad);
2263 mtree_test_insert(mt, 0, (void *)0x1);
2264 mtree_test_insert(mt, 1, (void *)0x3);
2265 mtree_test_store(mt, 51, (void *)0x67);
2266 mtree_test_insert(mt, 611, (void *)0x4c7);
2267 mtree_test_insert(mt, 485, (void *)0x3cb);
2268 mtree_test_insert(mt, 1, (void *)0x3);
2269 mtree_test_erase(mt, 1);
2270 mtree_test_insert(mt, 0, (void *)0x1);
2271 mtree_test_insert(mt, 1, (void *)0x3);
2272 mtree_test_insert_range(mt, 26, 1, (void *)0x35);
2273 mtree_test_load(mt, 1);
2274 mtree_test_store_range(mt, 1, 22, (void *)0x3);
2275 mtree_test_insert(mt, 1, (void *)0x3);
2276 mtree_test_erase(mt, 1);
2277 mtree_test_load(mt, 53);
2278 mtree_test_load(mt, 1);
2279 mtree_test_store_range(mt, 1, 1, (void *)0x3);
2280 mtree_test_insert(mt, 222, (void *)0x1bd);
2281 mtree_test_insert(mt, 485, (void *)0x3cb);
2282 mtree_test_insert(mt, 1, (void *)0x3);
2283 mtree_test_erase(mt, 1);
2284 mtree_test_load(mt, 0);
2285 mtree_test_insert(mt, 21, (void *)0x2b);
2286 mtree_test_insert(mt, 3, (void *)0x7);
2287 mtree_test_store(mt, 621, (void *)0x4db);
2288 mtree_test_insert(mt, 0, (void *)0x1);
2289 mtree_test_erase(mt, 5);
2290 mtree_test_insert(mt, 1, (void *)0x3);
2291 mtree_test_store(mt, 62, (void *)0x7d);
2292 mtree_test_erase(mt, 62);
2293 mtree_test_store_range(mt, 1, 0, (void *)0x3);
2294 mtree_test_insert(mt, 22, (void *)0x2d);
2295 mtree_test_insert(mt, 12, (void *)0x19);
2296 mtree_test_erase(mt, 1);
2297 mtree_test_insert(mt, 1, (void *)0x3);
2298 mtree_test_store_range(mt, 4, 62, (void *)0x9);
2299 mtree_test_erase(mt, 62);
2300 mtree_test_erase(mt, 1);
2301 mtree_test_load(mt, 1);
2302 mtree_test_store_range(mt, 1, 22, (void *)0x3);
2303 mtree_test_insert(mt, 1, (void *)0x3);
2304 mtree_test_erase(mt, 1);
2305 mtree_test_load(mt, 53);
2306 mtree_test_load(mt, 1);
2307 mtree_test_store_range(mt, 1, 1, (void *)0x3);
2308 mtree_test_insert(mt, 222, (void *)0x1bd);
2309 mtree_test_insert(mt, 485, (void *)0x3cb);
2310 mtree_test_insert(mt, 1, (void *)0x3);
2311 mtree_test_erase(mt, 1);
2312 mtree_test_insert(mt, 1, (void *)0x3);
2313 mtree_test_load(mt, 0);
2314 mtree_test_load(mt, 0);
2315 mtree_destroy(mt);
2316
2317 /*
2318 * 7. Previous fix was incomplete, fix mas_resuse_node() clearing of old
2319 * data by overwriting it first - that way metadata is of no concern.
2320 */
2321 mt_init_flags(mt, 0);
2322 mtree_test_load(mt, 1);
2323 mtree_test_insert(mt, 102, (void *)0xcd);
2324 mtree_test_erase(mt, 2);
2325 mtree_test_erase(mt, 0);
2326 mtree_test_load(mt, 0);
2327 mtree_test_insert(mt, 4, (void *)0x9);
2328 mtree_test_insert(mt, 2, (void *)0x5);
2329 mtree_test_insert(mt, 110, (void *)0xdd);
2330 mtree_test_insert(mt, 1, (void *)0x3);
2331 mtree_test_insert_range(mt, 5, 0, (void *)0xb);
2332 mtree_test_erase(mt, 2);
2333 mtree_test_store(mt, 0, (void *)0x1);
2334 mtree_test_store(mt, 112, (void *)0xe1);
2335 mtree_test_insert(mt, 21, (void *)0x2b);
2336 mtree_test_store(mt, 1, (void *)0x3);
2337 mtree_test_insert_range(mt, 110, 2, (void *)0xdd);
2338 mtree_test_store(mt, 2, (void *)0x5);
2339 mtree_test_load(mt, 22);
2340 mtree_test_erase(mt, 2);
2341 mtree_test_store(mt, 210, (void *)0x1a5);
2342 mtree_test_store_range(mt, 0, 2, (void *)0x1);
2343 mtree_test_store(mt, 2, (void *)0x5);
2344 mtree_test_erase(mt, 2);
2345 mtree_test_erase(mt, 22);
2346 mtree_test_erase(mt, 1);
2347 mtree_test_erase(mt, 2);
2348 mtree_test_store(mt, 0, (void *)0x1);
2349 mtree_test_load(mt, 112);
2350 mtree_test_insert(mt, 2, (void *)0x5);
2351 mtree_test_erase(mt, 2);
2352 mtree_test_store(mt, 1, (void *)0x3);
2353 mtree_test_insert_range(mt, 1, 2, (void *)0x3);
2354 mtree_test_erase(mt, 0);
2355 mtree_test_erase(mt, 2);
2356 mtree_test_store(mt, 2, (void *)0x5);
2357 mtree_test_erase(mt, 0);
2358 mtree_test_erase(mt, 2);
2359 mtree_test_store(mt, 0, (void *)0x1);
2360 mtree_test_store(mt, 0, (void *)0x1);
2361 mtree_test_erase(mt, 2);
2362 mtree_test_store(mt, 2, (void *)0x5);
2363 mtree_test_erase(mt, 2);
2364 mtree_test_insert(mt, 2, (void *)0x5);
2365 mtree_test_insert_range(mt, 1, 2, (void *)0x3);
2366 mtree_test_erase(mt, 0);
2367 mtree_test_erase(mt, 2);
2368 mtree_test_store(mt, 0, (void *)0x1);
2369 mtree_test_load(mt, 112);
2370 mtree_test_store_range(mt, 110, 12, (void *)0xdd);
2371 mtree_test_store(mt, 2, (void *)0x5);
2372 mtree_test_load(mt, 110);
2373 mtree_test_insert_range(mt, 4, 71, (void *)0x9);
2374 mtree_test_load(mt, 2);
2375 mtree_test_store(mt, 2, (void *)0x5);
2376 mtree_test_insert_range(mt, 11, 22, (void *)0x17);
2377 mtree_test_erase(mt, 12);
2378 mtree_test_store(mt, 2, (void *)0x5);
2379 mtree_test_load(mt, 22);
2380 mtree_destroy(mt);
2381
2382
2383 /*
2384 * 8. When rebalancing or spanning_rebalance(), the max of the new node
2385 * may be set incorrectly to the final pivot and not the right max.
2386 * Fix by setting the left max to orig right max if the entire node is
2387 * consumed.
2388 */
2389 mt_init_flags(mt, 0);
2390 mtree_test_store(mt, 6, (void *)0xd);
2391 mtree_test_store(mt, 67, (void *)0x87);
2392 mtree_test_insert(mt, 15, (void *)0x1f);
2393 mtree_test_insert(mt, 6716, (void *)0x3479);
2394 mtree_test_store(mt, 61, (void *)0x7b);
2395 mtree_test_insert(mt, 13, (void *)0x1b);
2396 mtree_test_store(mt, 8, (void *)0x11);
2397 mtree_test_insert(mt, 1, (void *)0x3);
2398 mtree_test_load(mt, 0);
2399 mtree_test_erase(mt, 67167);
2400 mtree_test_insert_range(mt, 6, 7167, (void *)0xd);
2401 mtree_test_insert(mt, 6, (void *)0xd);
2402 mtree_test_erase(mt, 67);
2403 mtree_test_insert(mt, 1, (void *)0x3);
2404 mtree_test_erase(mt, 667167);
2405 mtree_test_insert(mt, 6, (void *)0xd);
2406 mtree_test_store(mt, 67, (void *)0x87);
2407 mtree_test_insert(mt, 5, (void *)0xb);
2408 mtree_test_erase(mt, 1);
2409 mtree_test_insert(mt, 6, (void *)0xd);
2410 mtree_test_erase(mt, 67);
2411 mtree_test_insert(mt, 15, (void *)0x1f);
2412 mtree_test_insert(mt, 67167, (void *)0x20cbf);
2413 mtree_test_insert(mt, 1, (void *)0x3);
2414 mtree_test_load(mt, 7);
2415 mtree_test_insert(mt, 16, (void *)0x21);
2416 mtree_test_insert(mt, 36, (void *)0x49);
2417 mtree_test_store(mt, 67, (void *)0x87);
2418 mtree_test_store(mt, 6, (void *)0xd);
2419 mtree_test_insert(mt, 367, (void *)0x2df);
2420 mtree_test_insert(mt, 115, (void *)0xe7);
2421 mtree_test_store(mt, 0, (void *)0x1);
2422 mtree_test_store_range(mt, 1, 3, (void *)0x3);
2423 mtree_test_store(mt, 1, (void *)0x3);
2424 mtree_test_erase(mt, 67167);
2425 mtree_test_insert_range(mt, 6, 47, (void *)0xd);
2426 mtree_test_store(mt, 1, (void *)0x3);
2427 mtree_test_insert_range(mt, 1, 67, (void *)0x3);
2428 mtree_test_load(mt, 67);
2429 mtree_test_insert(mt, 1, (void *)0x3);
2430 mtree_test_erase(mt, 67167);
2431 mtree_destroy(mt);
2432
2433 /*
2434 * 9. spanning store to the end of data caused an invalid metadata
2435 * length which resulted in a crash eventually.
2436 * Fix by checking if there is a value in pivot before incrementing the
2437 * metadata end in mab_mas_cp(). To ensure this doesn't happen again,
2438 * abstract the two locations this happens into a function called
2439 * mas_leaf_set_meta().
2440 */
2441 mt_init_flags(mt, 0);
2442 mtree_test_insert(mt, 21, (void *)0x2b);
2443 mtree_test_insert(mt, 12, (void *)0x19);
2444 mtree_test_insert(mt, 6, (void *)0xd);
2445 mtree_test_insert(mt, 8, (void *)0x11);
2446 mtree_test_insert(mt, 2, (void *)0x5);
2447 mtree_test_insert(mt, 91, (void *)0xb7);
2448 mtree_test_insert(mt, 18, (void *)0x25);
2449 mtree_test_insert(mt, 81, (void *)0xa3);
2450 mtree_test_store_range(mt, 0, 128, (void *)0x1);
2451 mtree_test_store(mt, 1, (void *)0x3);
2452 mtree_test_erase(mt, 8);
2453 mtree_test_insert(mt, 11, (void *)0x17);
2454 mtree_test_insert(mt, 8, (void *)0x11);
2455 mtree_test_insert(mt, 21, (void *)0x2b);
2456 mtree_test_insert(mt, 2, (void *)0x5);
2457 mtree_test_insert(mt, ULONG_MAX - 10, (void *)0xffffffffffffffeb);
2458 mtree_test_erase(mt, ULONG_MAX - 10);
2459 mtree_test_store_range(mt, 0, 281, (void *)0x1);
2460 mtree_test_erase(mt, 2);
2461 mtree_test_insert(mt, 1211, (void *)0x977);
2462 mtree_test_insert(mt, 111, (void *)0xdf);
2463 mtree_test_insert(mt, 13, (void *)0x1b);
2464 mtree_test_insert(mt, 211, (void *)0x1a7);
2465 mtree_test_insert(mt, 11, (void *)0x17);
2466 mtree_test_insert(mt, 5, (void *)0xb);
2467 mtree_test_insert(mt, 1218, (void *)0x985);
2468 mtree_test_insert(mt, 61, (void *)0x7b);
2469 mtree_test_store(mt, 1, (void *)0x3);
2470 mtree_test_insert(mt, 121, (void *)0xf3);
2471 mtree_test_insert(mt, 8, (void *)0x11);
2472 mtree_test_insert(mt, 21, (void *)0x2b);
2473 mtree_test_insert(mt, 2, (void *)0x5);
2474 mtree_test_insert(mt, ULONG_MAX - 10, (void *)0xffffffffffffffeb);
2475 mtree_test_erase(mt, ULONG_MAX - 10);
2476 }
2477
2478 /* duplicate the tree with a specific gap */
2479 static noinline void __init check_dup_gaps(struct maple_tree *mt,
2480 unsigned long nr_entries, bool zero_start,
2481 unsigned long gap)
2482 {
2483 unsigned long i = 0;
2484 struct maple_tree newmt;
2485 int ret;
2486 void *tmp;
2487 MA_STATE(mas, mt, 0, 0);
2488 MA_STATE(newmas, &newmt, 0, 0);
2489
2490 if (!zero_start)
2491 i = 1;
2492
2493 mt_zero_nr_tallocated();
2494 for (; i <= nr_entries; i++)
2495 mtree_store_range(mt, i*10, (i+1)*10 - gap,
2496 xa_mk_value(i), GFP_KERNEL);
2497
2498 mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
2499 mt_set_non_kernel(99999);
2500 mas_lock(&newmas);
2501 ret = mas_expected_entries(&newmas, nr_entries);
2502 mt_set_non_kernel(0);
2503 MT_BUG_ON(mt, ret != 0);
2504
2505 rcu_read_lock();
2506 mas_for_each(&mas, tmp, ULONG_MAX) {
2507 newmas.index = mas.index;
2508 newmas.last = mas.last;
2509 mas_store(&newmas, tmp);
2510 }
2511 rcu_read_unlock();
2512 mas_destroy(&newmas);
2513 mas_unlock(&newmas);
2514
2515 mtree_destroy(&newmt);
2516 }
2517
2518 /* Duplicate many sizes of trees. Mainly to test expected entry values */
2519 static noinline void __init check_dup(struct maple_tree *mt)
2520 {
2521 int i;
2522 int big_start = 100010;
2523
2524 /* Check with a value at zero */
2525 for (i = 10; i < 1000; i++) {
2526 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2527 check_dup_gaps(mt, i, true, 5);
2528 mtree_destroy(mt);
2529 rcu_barrier();
2530 }
2531
2532 cond_resched();
2533 mt_cache_shrink();
2534 /* Check with a value at zero, no gap */
2535 for (i = 1000; i < 2000; i++) {
2536 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2537 check_dup_gaps(mt, i, true, 0);
2538 mtree_destroy(mt);
2539 rcu_barrier();
2540 }
2541
2542 cond_resched();
2543 mt_cache_shrink();
2544 /* Check with a value at zero and unreasonably large */
2545 for (i = big_start; i < big_start + 10; i++) {
2546 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2547 check_dup_gaps(mt, i, true, 5);
2548 mtree_destroy(mt);
2549 rcu_barrier();
2550 }
2551
2552 cond_resched();
2553 mt_cache_shrink();
2554 /* Small to medium size not starting at zero*/
2555 for (i = 200; i < 1000; i++) {
2556 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2557 check_dup_gaps(mt, i, false, 5);
2558 mtree_destroy(mt);
2559 rcu_barrier();
2560 }
2561
2562 cond_resched();
2563 mt_cache_shrink();
2564 /* Unreasonably large not starting at zero*/
2565 for (i = big_start; i < big_start + 10; i++) {
2566 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2567 check_dup_gaps(mt, i, false, 5);
2568 mtree_destroy(mt);
2569 rcu_barrier();
2570 cond_resched();
2571 mt_cache_shrink();
2572 }
2573
2574 /* Check non-allocation tree not starting at zero */
2575 for (i = 1500; i < 3000; i++) {
2576 mt_init_flags(mt, 0);
2577 check_dup_gaps(mt, i, false, 5);
2578 mtree_destroy(mt);
2579 rcu_barrier();
2580 cond_resched();
2581 if (i % 2 == 0)
2582 mt_cache_shrink();
2583 }
2584
2585 mt_cache_shrink();
2586 /* Check non-allocation tree starting at zero */
2587 for (i = 200; i < 1000; i++) {
2588 mt_init_flags(mt, 0);
2589 check_dup_gaps(mt, i, true, 5);
2590 mtree_destroy(mt);
2591 rcu_barrier();
2592 cond_resched();
2593 }
2594
2595 mt_cache_shrink();
2596 /* Unreasonably large */
2597 for (i = big_start + 5; i < big_start + 10; i++) {
2598 mt_init_flags(mt, 0);
2599 check_dup_gaps(mt, i, true, 5);
2600 mtree_destroy(mt);
2601 rcu_barrier();
2602 mt_cache_shrink();
2603 cond_resched();
2604 }
2605 }
2606
2607 static noinline void __init check_bnode_min_spanning(struct maple_tree *mt)
2608 {
2609 int i = 50;
2610 MA_STATE(mas, mt, 0, 0);
2611
2612 mt_set_non_kernel(9999);
2613 mas_lock(&mas);
2614 do {
2615 mas_set_range(&mas, i*10, i*10+9);
2616 mas_store(&mas, check_bnode_min_spanning);
2617 } while (i--);
2618
2619 mas_set_range(&mas, 240, 509);
2620 mas_store(&mas, NULL);
2621 mas_unlock(&mas);
2622 mas_destroy(&mas);
2623 mt_set_non_kernel(0);
2624 }
2625
2626 static noinline void __init check_empty_area_window(struct maple_tree *mt)
2627 {
2628 unsigned long i, nr_entries = 20;
2629 MA_STATE(mas, mt, 0, 0);
2630
2631 for (i = 1; i <= nr_entries; i++)
2632 mtree_store_range(mt, i*10, i*10 + 9,
2633 xa_mk_value(i), GFP_KERNEL);
2634
2635 /* Create another hole besides the one at 0 */
2636 mtree_store_range(mt, 160, 169, NULL, GFP_KERNEL);
2637
2638 /* Check lower bounds that don't fit */
2639 rcu_read_lock();
2640 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 10) != -EBUSY);
2641
2642 mas_reset(&mas);
2643 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 6, 90, 5) != -EBUSY);
2644
2645 /* Check lower bound that does fit */
2646 mas_reset(&mas);
2647 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 5) != 0);
2648 MT_BUG_ON(mt, mas.index != 5);
2649 MT_BUG_ON(mt, mas.last != 9);
2650 rcu_read_unlock();
2651
2652 /* Check one gap that doesn't fit and one that does */
2653 rcu_read_lock();
2654 mas_reset(&mas);
2655 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 217, 9) != 0);
2656 MT_BUG_ON(mt, mas.index != 161);
2657 MT_BUG_ON(mt, mas.last != 169);
2658
2659 /* Check one gap that does fit above the min */
2660 mas_reset(&mas);
2661 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 3) != 0);
2662 MT_BUG_ON(mt, mas.index != 216);
2663 MT_BUG_ON(mt, mas.last != 218);
2664
2665 /* Check size that doesn't fit any gap */
2666 mas_reset(&mas);
2667 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 16) != -EBUSY);
2668
2669 /*
2670 * Check size that doesn't fit the lower end of the window but
2671 * does fit the gap
2672 */
2673 mas_reset(&mas);
2674 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 167, 200, 4) != -EBUSY);
2675
2676 /*
2677 * Check size that doesn't fit the upper end of the window but
2678 * does fit the gap
2679 */
2680 mas_reset(&mas);
2681 MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 162, 4) != -EBUSY);
2682
2683 /* Check mas_empty_area forward */
2684 mas_reset(&mas);
2685 MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 9) != 0);
2686 MT_BUG_ON(mt, mas.index != 0);
2687 MT_BUG_ON(mt, mas.last != 8);
2688
2689 mas_reset(&mas);
2690 MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 4) != 0);
2691 MT_BUG_ON(mt, mas.index != 0);
2692 MT_BUG_ON(mt, mas.last != 3);
2693
2694 mas_reset(&mas);
2695 MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 11) != -EBUSY);
2696
2697 mas_reset(&mas);
2698 MT_BUG_ON(mt, mas_empty_area(&mas, 5, 100, 6) != -EBUSY);
2699
2700 mas_reset(&mas);
2701 MT_BUG_ON(mt, mas_empty_area(&mas, 0, 8, 10) != -EINVAL);
2702
2703 mas_reset(&mas);
2704 mas_empty_area(&mas, 100, 165, 3);
2705
2706 mas_reset(&mas);
2707 MT_BUG_ON(mt, mas_empty_area(&mas, 100, 163, 6) != -EBUSY);
2708 rcu_read_unlock();
2709 }
2710
2711 static noinline void __init check_empty_area_fill(struct maple_tree *mt)
2712 {
2713 const unsigned long max = 0x25D78000;
2714 unsigned long size;
2715 int loop, shift;
2716 MA_STATE(mas, mt, 0, 0);
2717
2718 mt_set_non_kernel(99999);
2719 for (shift = 12; shift <= 16; shift++) {
2720 loop = 5000;
2721 size = 1 << shift;
2722 while (loop--) {
2723 mas_set(&mas, 0);
2724 mas_lock(&mas);
2725 MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != 0);
2726 MT_BUG_ON(mt, mas.last != mas.index + size - 1);
2727 mas_store_gfp(&mas, (void *)size, GFP_KERNEL);
2728 mas_unlock(&mas);
2729 mas_reset(&mas);
2730 }
2731 }
2732
2733 /* No space left. */
2734 size = 0x1000;
2735 rcu_read_lock();
2736 MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != -EBUSY);
2737 rcu_read_unlock();
2738
2739 /* Fill a depth 3 node to the maximum */
2740 for (unsigned long i = 629440511; i <= 629440800; i += 6)
2741 mtree_store_range(mt, i, i + 5, (void *)i, GFP_KERNEL);
2742 /* Make space in the second-last depth 4 node */
2743 mtree_erase(mt, 631668735);
2744 /* Make space in the last depth 4 node */
2745 mtree_erase(mt, 629506047);
2746 mas_reset(&mas);
2747 /* Search from just after the gap in the second-last depth 4 */
2748 rcu_read_lock();
2749 MT_BUG_ON(mt, mas_empty_area(&mas, 629506048, 690000000, 0x5000) != 0);
2750 rcu_read_unlock();
2751 mt_set_non_kernel(0);
2752 }
2753
2754 /*
2755 * Check MAS_START, MAS_PAUSE, active (implied), and MAS_NONE transitions.
2756 *
2757 * The table below shows the single entry tree (0-0 pointer) and normal tree
2758 * with nodes.
2759 *
2760 * Function ENTRY Start Result index & last
2761 * ┬ ┬ ┬ ┬ ┬
2762 * │ │ │ │ └─ the final range
2763 * │ │ │ └─ The node value after execution
2764 * │ │ └─ The node value before execution
2765 * │ └─ If the entry exists or does not exists (DNE)
2766 * └─ The function name
2767 *
2768 * Function ENTRY Start Result index & last
2769 * mas_next()
2770 * - after last
2771 * Single entry tree at 0-0
2772 * ------------------------
2773 * DNE MAS_START MAS_NONE 1 - oo
2774 * DNE MAS_PAUSE MAS_NONE 1 - oo
2775 * DNE MAS_ROOT MAS_NONE 1 - oo
2776 * when index = 0
2777 * DNE MAS_NONE MAS_ROOT 0
2778 * when index > 0
2779 * DNE MAS_NONE MAS_NONE 1 - oo
2780 *
2781 * Normal tree
2782 * -----------
2783 * exists MAS_START active range
2784 * DNE MAS_START active set to last range
2785 * exists MAS_PAUSE active range
2786 * DNE MAS_PAUSE active set to last range
2787 * exists MAS_NONE active range
2788 * exists active active range
2789 * DNE active active set to last range
2790 *
2791 * Function ENTRY Start Result index & last
2792 * mas_prev()
2793 * - before index
2794 * Single entry tree at 0-0
2795 * ------------------------
2796 * if index > 0
2797 * exists MAS_START MAS_ROOT 0
2798 * exists MAS_PAUSE MAS_ROOT 0
2799 * exists MAS_NONE MAS_ROOT 0
2800 *
2801 * if index == 0
2802 * DNE MAS_START MAS_NONE 0
2803 * DNE MAS_PAUSE MAS_NONE 0
2804 * DNE MAS_NONE MAS_NONE 0
2805 * DNE MAS_ROOT MAS_NONE 0
2806 *
2807 * Normal tree
2808 * -----------
2809 * exists MAS_START active range
2810 * DNE MAS_START active set to min
2811 * exists MAS_PAUSE active range
2812 * DNE MAS_PAUSE active set to min
2813 * exists MAS_NONE active range
2814 * DNE MAS_NONE MAS_NONE set to min
2815 * any MAS_ROOT MAS_NONE 0
2816 * exists active active range
2817 * DNE active active last range
2818 *
2819 * Function ENTRY Start Result index & last
2820 * mas_find()
2821 * - at index or next
2822 * Single entry tree at 0-0
2823 * ------------------------
2824 * if index > 0
2825 * DNE MAS_START MAS_NONE 0
2826 * DNE MAS_PAUSE MAS_NONE 0
2827 * DNE MAS_ROOT MAS_NONE 0
2828 * DNE MAS_NONE MAS_NONE 0
2829 * if index == 0
2830 * exists MAS_START MAS_ROOT 0
2831 * exists MAS_PAUSE MAS_ROOT 0
2832 * exists MAS_NONE MAS_ROOT 0
2833 *
2834 * Normal tree
2835 * -----------
2836 * exists MAS_START active range
2837 * DNE MAS_START active set to max
2838 * exists MAS_PAUSE active range
2839 * DNE MAS_PAUSE active set to max
2840 * exists MAS_NONE active range
2841 * exists active active range
2842 * DNE active active last range (max < last)
2843 *
2844 * Function ENTRY Start Result index & last
2845 * mas_find_rev()
2846 * - at index or before
2847 * Single entry tree at 0-0
2848 * ------------------------
2849 * if index > 0
2850 * exists MAS_START MAS_ROOT 0
2851 * exists MAS_PAUSE MAS_ROOT 0
2852 * exists MAS_NONE MAS_ROOT 0
2853 * if index == 0
2854 * DNE MAS_START MAS_NONE 0
2855 * DNE MAS_PAUSE MAS_NONE 0
2856 * DNE MAS_NONE MAS_NONE 0
2857 * DNE MAS_ROOT MAS_NONE 0
2858 *
2859 * Normal tree
2860 * -----------
2861 * exists MAS_START active range
2862 * DNE MAS_START active set to min
2863 * exists MAS_PAUSE active range
2864 * DNE MAS_PAUSE active set to min
2865 * exists MAS_NONE active range
2866 * exists active active range
2867 * DNE active active last range (min > index)
2868 *
2869 * Function ENTRY Start Result index & last
2870 * mas_walk()
2871 * - Look up index
2872 * Single entry tree at 0-0
2873 * ------------------------
2874 * if index > 0
2875 * DNE MAS_START MAS_ROOT 1 - oo
2876 * DNE MAS_PAUSE MAS_ROOT 1 - oo
2877 * DNE MAS_NONE MAS_ROOT 1 - oo
2878 * DNE MAS_ROOT MAS_ROOT 1 - oo
2879 * if index == 0
2880 * exists MAS_START MAS_ROOT 0
2881 * exists MAS_PAUSE MAS_ROOT 0
2882 * exists MAS_NONE MAS_ROOT 0
2883 * exists MAS_ROOT MAS_ROOT 0
2884 *
2885 * Normal tree
2886 * -----------
2887 * exists MAS_START active range
2888 * DNE MAS_START active range of NULL
2889 * exists MAS_PAUSE active range
2890 * DNE MAS_PAUSE active range of NULL
2891 * exists MAS_NONE active range
2892 * DNE MAS_NONE active range of NULL
2893 * exists active active range
2894 * DNE active active range of NULL
2895 */
2896
2897 #define mas_active(x) (((x).node != MAS_ROOT) && \
2898 ((x).node != MAS_START) && \
2899 ((x).node != MAS_PAUSE) && \
2900 ((x).node != MAS_NONE))
2901 static noinline void __init check_state_handling(struct maple_tree *mt)
2902 {
2903 MA_STATE(mas, mt, 0, 0);
2904 void *entry, *ptr = (void *) 0x1234500;
2905 void *ptr2 = &ptr;
2906 void *ptr3 = &ptr2;
2907
2908 /* Check MAS_ROOT First */
2909 mtree_store_range(mt, 0, 0, ptr, GFP_KERNEL);
2910
2911 mas_lock(&mas);
2912 /* prev: Start -> none */
2913 entry = mas_prev(&mas, 0);
2914 MT_BUG_ON(mt, entry != NULL);
2915 MT_BUG_ON(mt, mas.node != MAS_NONE);
2916
2917 /* prev: Start -> root */
2918 mas_set(&mas, 10);
2919 entry = mas_prev(&mas, 0);
2920 MT_BUG_ON(mt, entry != ptr);
2921 MT_BUG_ON(mt, mas.index != 0);
2922 MT_BUG_ON(mt, mas.last != 0);
2923 MT_BUG_ON(mt, mas.node != MAS_ROOT);
2924
2925 /* prev: pause -> root */
2926 mas_set(&mas, 10);
2927 mas_pause(&mas);
2928 entry = mas_prev(&mas, 0);
2929 MT_BUG_ON(mt, entry != ptr);
2930 MT_BUG_ON(mt, mas.index != 0);
2931 MT_BUG_ON(mt, mas.last != 0);
2932 MT_BUG_ON(mt, mas.node != MAS_ROOT);
2933
2934 /* next: start -> none */
2935 mas_set(&mas, 0);
2936 entry = mas_next(&mas, ULONG_MAX);
2937 MT_BUG_ON(mt, mas.index != 1);
2938 MT_BUG_ON(mt, mas.last != ULONG_MAX);
2939 MT_BUG_ON(mt, entry != NULL);
2940 MT_BUG_ON(mt, mas.node != MAS_NONE);
2941
2942 /* next: start -> none */
2943 mas_set(&mas, 10);
2944 entry = mas_next(&mas, ULONG_MAX);
2945 MT_BUG_ON(mt, mas.index != 1);
2946 MT_BUG_ON(mt, mas.last != ULONG_MAX);
2947 MT_BUG_ON(mt, entry != NULL);
2948 MT_BUG_ON(mt, mas.node != MAS_NONE);
2949
2950 /* find: start -> root */
2951 mas_set(&mas, 0);
2952 entry = mas_find(&mas, ULONG_MAX);
2953 MT_BUG_ON(mt, entry != ptr);
2954 MT_BUG_ON(mt, mas.index != 0);
2955 MT_BUG_ON(mt, mas.last != 0);
2956 MT_BUG_ON(mt, mas.node != MAS_ROOT);
2957
2958 /* find: root -> none */
2959 entry = mas_find(&mas, ULONG_MAX);
2960 MT_BUG_ON(mt, entry != NULL);
2961 MT_BUG_ON(mt, mas.index != 1);
2962 MT_BUG_ON(mt, mas.last != ULONG_MAX);
2963 MT_BUG_ON(mt, mas.node != MAS_NONE);
2964
2965 /* find: none -> none */
2966 entry = mas_find(&mas, ULONG_MAX);
2967 MT_BUG_ON(mt, entry != NULL);
2968 MT_BUG_ON(mt, mas.index != 1);
2969 MT_BUG_ON(mt, mas.last != ULONG_MAX);
2970 MT_BUG_ON(mt, mas.node != MAS_NONE);
2971
2972 /* find: start -> none */
2973 mas_set(&mas, 10);
2974 entry = mas_find(&mas, ULONG_MAX);
2975 MT_BUG_ON(mt, entry != NULL);
2976 MT_BUG_ON(mt, mas.index != 1);
2977 MT_BUG_ON(mt, mas.last != ULONG_MAX);
2978 MT_BUG_ON(mt, mas.node != MAS_NONE);
2979
2980 /* find_rev: none -> root */
2981 entry = mas_find_rev(&mas, 0);
2982 MT_BUG_ON(mt, entry != ptr);
2983 MT_BUG_ON(mt, mas.index != 0);
2984 MT_BUG_ON(mt, mas.last != 0);
2985 MT_BUG_ON(mt, mas.node != MAS_ROOT);
2986
2987 /* find_rev: start -> root */
2988 mas_set(&mas, 0);
2989 entry = mas_find_rev(&mas, 0);
2990 MT_BUG_ON(mt, entry != ptr);
2991 MT_BUG_ON(mt, mas.index != 0);
2992 MT_BUG_ON(mt, mas.last != 0);
2993 MT_BUG_ON(mt, mas.node != MAS_ROOT);
2994
2995 /* find_rev: root -> none */
2996 entry = mas_find_rev(&mas, 0);
2997 MT_BUG_ON(mt, entry != NULL);
2998 MT_BUG_ON(mt, mas.index != 0);
2999 MT_BUG_ON(mt, mas.last != 0);
3000 MT_BUG_ON(mt, mas.node != MAS_NONE);
3001
3002 /* find_rev: none -> none */
3003 entry = mas_find_rev(&mas, 0);
3004 MT_BUG_ON(mt, entry != NULL);
3005 MT_BUG_ON(mt, mas.index != 0);
3006 MT_BUG_ON(mt, mas.last != 0);
3007 MT_BUG_ON(mt, mas.node != MAS_NONE);
3008
3009 /* find_rev: start -> root */
3010 mas_set(&mas, 10);
3011 entry = mas_find_rev(&mas, 0);
3012 MT_BUG_ON(mt, entry != ptr);
3013 MT_BUG_ON(mt, mas.index != 0);
3014 MT_BUG_ON(mt, mas.last != 0);
3015 MT_BUG_ON(mt, mas.node != MAS_ROOT);
3016
3017 /* walk: start -> none */
3018 mas_set(&mas, 10);
3019 entry = mas_walk(&mas);
3020 MT_BUG_ON(mt, entry != NULL);
3021 MT_BUG_ON(mt, mas.index != 1);
3022 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3023 MT_BUG_ON(mt, mas.node != MAS_NONE);
3024
3025 /* walk: pause -> none*/
3026 mas_set(&mas, 10);
3027 mas_pause(&mas);
3028 entry = mas_walk(&mas);
3029 MT_BUG_ON(mt, entry != NULL);
3030 MT_BUG_ON(mt, mas.index != 1);
3031 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3032 MT_BUG_ON(mt, mas.node != MAS_NONE);
3033
3034 /* walk: none -> none */
3035 mas.index = mas.last = 10;
3036 entry = mas_walk(&mas);
3037 MT_BUG_ON(mt, entry != NULL);
3038 MT_BUG_ON(mt, mas.index != 1);
3039 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3040 MT_BUG_ON(mt, mas.node != MAS_NONE);
3041
3042 /* walk: none -> none */
3043 entry = mas_walk(&mas);
3044 MT_BUG_ON(mt, entry != NULL);
3045 MT_BUG_ON(mt, mas.index != 1);
3046 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3047 MT_BUG_ON(mt, mas.node != MAS_NONE);
3048
3049 /* walk: start -> root */
3050 mas_set(&mas, 0);
3051 entry = mas_walk(&mas);
3052 MT_BUG_ON(mt, entry != ptr);
3053 MT_BUG_ON(mt, mas.index != 0);
3054 MT_BUG_ON(mt, mas.last != 0);
3055 MT_BUG_ON(mt, mas.node != MAS_ROOT);
3056
3057 /* walk: pause -> root */
3058 mas_set(&mas, 0);
3059 mas_pause(&mas);
3060 entry = mas_walk(&mas);
3061 MT_BUG_ON(mt, entry != ptr);
3062 MT_BUG_ON(mt, mas.index != 0);
3063 MT_BUG_ON(mt, mas.last != 0);
3064 MT_BUG_ON(mt, mas.node != MAS_ROOT);
3065
3066 /* walk: none -> root */
3067 mas.node = MAS_NONE;
3068 entry = mas_walk(&mas);
3069 MT_BUG_ON(mt, entry != ptr);
3070 MT_BUG_ON(mt, mas.index != 0);
3071 MT_BUG_ON(mt, mas.last != 0);
3072 MT_BUG_ON(mt, mas.node != MAS_ROOT);
3073
3074 /* walk: root -> root */
3075 entry = mas_walk(&mas);
3076 MT_BUG_ON(mt, entry != ptr);
3077 MT_BUG_ON(mt, mas.index != 0);
3078 MT_BUG_ON(mt, mas.last != 0);
3079 MT_BUG_ON(mt, mas.node != MAS_ROOT);
3080
3081 /* walk: root -> none */
3082 mas_set(&mas, 10);
3083 entry = mas_walk(&mas);
3084 MT_BUG_ON(mt, entry != NULL);
3085 MT_BUG_ON(mt, mas.index != 1);
3086 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3087 MT_BUG_ON(mt, mas.node != MAS_NONE);
3088
3089 /* walk: none -> root */
3090 mas.index = mas.last = 0;
3091 entry = mas_walk(&mas);
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.node != MAS_ROOT);
3096
3097 mas_unlock(&mas);
3098
3099 /* Check when there is an actual node */
3100 mtree_store_range(mt, 0, 0, NULL, GFP_KERNEL);
3101 mtree_store_range(mt, 0x1000, 0x1500, ptr, GFP_KERNEL);
3102 mtree_store_range(mt, 0x2000, 0x2500, ptr2, GFP_KERNEL);
3103 mtree_store_range(mt, 0x3000, 0x3500, ptr3, GFP_KERNEL);
3104
3105 mas_lock(&mas);
3106
3107 /* next: start ->active */
3108 mas_set(&mas, 0);
3109 entry = mas_next(&mas, ULONG_MAX);
3110 MT_BUG_ON(mt, entry != ptr);
3111 MT_BUG_ON(mt, mas.index != 0x1000);
3112 MT_BUG_ON(mt, mas.last != 0x1500);
3113 MT_BUG_ON(mt, !mas_active(mas));
3114
3115 /* next: pause ->active */
3116 mas_set(&mas, 0);
3117 mas_pause(&mas);
3118 entry = mas_next(&mas, ULONG_MAX);
3119 MT_BUG_ON(mt, entry != ptr);
3120 MT_BUG_ON(mt, mas.index != 0x1000);
3121 MT_BUG_ON(mt, mas.last != 0x1500);
3122 MT_BUG_ON(mt, !mas_active(mas));
3123
3124 /* next: none ->active */
3125 mas.index = mas.last = 0;
3126 mas.offset = 0;
3127 mas.node = MAS_NONE;
3128 entry = mas_next(&mas, ULONG_MAX);
3129 MT_BUG_ON(mt, entry != ptr);
3130 MT_BUG_ON(mt, mas.index != 0x1000);
3131 MT_BUG_ON(mt, mas.last != 0x1500);
3132 MT_BUG_ON(mt, !mas_active(mas));
3133
3134 /* next:active ->active */
3135 entry = mas_next(&mas, ULONG_MAX);
3136 MT_BUG_ON(mt, entry != ptr2);
3137 MT_BUG_ON(mt, mas.index != 0x2000);
3138 MT_BUG_ON(mt, mas.last != 0x2500);
3139 MT_BUG_ON(mt, !mas_active(mas));
3140
3141 /* next:active -> active out of range*/
3142 entry = mas_next(&mas, 0x2999);
3143 MT_BUG_ON(mt, entry != NULL);
3144 MT_BUG_ON(mt, mas.index != 0x2501);
3145 MT_BUG_ON(mt, mas.last != 0x2fff);
3146 MT_BUG_ON(mt, !mas_active(mas));
3147
3148 /* Continue after out of range*/
3149 entry = mas_next(&mas, ULONG_MAX);
3150 MT_BUG_ON(mt, entry != ptr3);
3151 MT_BUG_ON(mt, mas.index != 0x3000);
3152 MT_BUG_ON(mt, mas.last != 0x3500);
3153 MT_BUG_ON(mt, !mas_active(mas));
3154
3155 /* next:active -> active out of range*/
3156 entry = mas_next(&mas, ULONG_MAX);
3157 MT_BUG_ON(mt, entry != NULL);
3158 MT_BUG_ON(mt, mas.index != 0x3501);
3159 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3160 MT_BUG_ON(mt, !mas_active(mas));
3161
3162 /* next: none -> active, skip value at location */
3163 mas_set(&mas, 0);
3164 entry = mas_next(&mas, ULONG_MAX);
3165 mas.node = MAS_NONE;
3166 mas.offset = 0;
3167 entry = mas_next(&mas, ULONG_MAX);
3168 MT_BUG_ON(mt, entry != ptr2);
3169 MT_BUG_ON(mt, mas.index != 0x2000);
3170 MT_BUG_ON(mt, mas.last != 0x2500);
3171 MT_BUG_ON(mt, !mas_active(mas));
3172
3173 /* prev:active ->active */
3174 entry = mas_prev(&mas, 0);
3175 MT_BUG_ON(mt, entry != ptr);
3176 MT_BUG_ON(mt, mas.index != 0x1000);
3177 MT_BUG_ON(mt, mas.last != 0x1500);
3178 MT_BUG_ON(mt, !mas_active(mas));
3179
3180 /* prev:active -> active out of range*/
3181 entry = mas_prev(&mas, 0);
3182 MT_BUG_ON(mt, entry != NULL);
3183 MT_BUG_ON(mt, mas.index != 0);
3184 MT_BUG_ON(mt, mas.last != 0x0FFF);
3185 MT_BUG_ON(mt, !mas_active(mas));
3186
3187 /* prev: pause ->active */
3188 mas_set(&mas, 0x3600);
3189 entry = mas_prev(&mas, 0);
3190 MT_BUG_ON(mt, entry != ptr3);
3191 mas_pause(&mas);
3192 entry = mas_prev(&mas, 0);
3193 MT_BUG_ON(mt, entry != ptr2);
3194 MT_BUG_ON(mt, mas.index != 0x2000);
3195 MT_BUG_ON(mt, mas.last != 0x2500);
3196 MT_BUG_ON(mt, !mas_active(mas));
3197
3198 /* prev:active -> active out of range*/
3199 entry = mas_prev(&mas, 0x1600);
3200 MT_BUG_ON(mt, entry != NULL);
3201 MT_BUG_ON(mt, mas.index != 0x1501);
3202 MT_BUG_ON(mt, mas.last != 0x1FFF);
3203 MT_BUG_ON(mt, !mas_active(mas));
3204
3205 /* prev: active ->active, continue*/
3206 entry = mas_prev(&mas, 0);
3207 MT_BUG_ON(mt, entry != ptr);
3208 MT_BUG_ON(mt, mas.index != 0x1000);
3209 MT_BUG_ON(mt, mas.last != 0x1500);
3210 MT_BUG_ON(mt, !mas_active(mas));
3211
3212 /* find: start ->active */
3213 mas_set(&mas, 0);
3214 entry = mas_find(&mas, ULONG_MAX);
3215 MT_BUG_ON(mt, entry != ptr);
3216 MT_BUG_ON(mt, mas.index != 0x1000);
3217 MT_BUG_ON(mt, mas.last != 0x1500);
3218 MT_BUG_ON(mt, !mas_active(mas));
3219
3220 /* find: pause ->active */
3221 mas_set(&mas, 0);
3222 mas_pause(&mas);
3223 entry = mas_find(&mas, ULONG_MAX);
3224 MT_BUG_ON(mt, entry != ptr);
3225 MT_BUG_ON(mt, mas.index != 0x1000);
3226 MT_BUG_ON(mt, mas.last != 0x1500);
3227 MT_BUG_ON(mt, !mas_active(mas));
3228
3229 /* find: start ->active on value */;
3230 mas_set(&mas, 1200);
3231 entry = mas_find(&mas, ULONG_MAX);
3232 MT_BUG_ON(mt, entry != ptr);
3233 MT_BUG_ON(mt, mas.index != 0x1000);
3234 MT_BUG_ON(mt, mas.last != 0x1500);
3235 MT_BUG_ON(mt, !mas_active(mas));
3236
3237 /* find:active ->active */
3238 entry = mas_find(&mas, ULONG_MAX);
3239 MT_BUG_ON(mt, entry != ptr2);
3240 MT_BUG_ON(mt, mas.index != 0x2000);
3241 MT_BUG_ON(mt, mas.last != 0x2500);
3242 MT_BUG_ON(mt, !mas_active(mas));
3243
3244
3245 /* find:active -> active (NULL)*/
3246 entry = mas_find(&mas, 0x2700);
3247 MT_BUG_ON(mt, entry != NULL);
3248 MT_BUG_ON(mt, mas.index != 0x2501);
3249 MT_BUG_ON(mt, mas.last != 0x2FFF);
3250 MT_BUG_ON(mt, !mas_active(mas));
3251
3252 /* find: none ->active */
3253 entry = mas_find(&mas, 0x5000);
3254 MT_BUG_ON(mt, entry != ptr3);
3255 MT_BUG_ON(mt, mas.index != 0x3000);
3256 MT_BUG_ON(mt, mas.last != 0x3500);
3257 MT_BUG_ON(mt, !mas_active(mas));
3258
3259 /* find:active -> active (NULL) end*/
3260 entry = mas_find(&mas, ULONG_MAX);
3261 MT_BUG_ON(mt, entry != NULL);
3262 MT_BUG_ON(mt, mas.index != 0x3501);
3263 MT_BUG_ON(mt, mas.last != ULONG_MAX);
3264 MT_BUG_ON(mt, !mas_active(mas));
3265
3266 /* find_rev: active (END) ->active */
3267 entry = mas_find_rev(&mas, 0);
3268 MT_BUG_ON(mt, entry != ptr3);
3269 MT_BUG_ON(mt, mas.index != 0x3000);
3270 MT_BUG_ON(mt, mas.last != 0x3500);
3271 MT_BUG_ON(mt, !mas_active(mas));
3272
3273 /* find_rev:active ->active */
3274 entry = mas_find_rev(&mas, 0);
3275 MT_BUG_ON(mt, entry != ptr2);
3276 MT_BUG_ON(mt, mas.index != 0x2000);
3277 MT_BUG_ON(mt, mas.last != 0x2500);
3278 MT_BUG_ON(mt, !mas_active(mas));
3279
3280 /* find_rev: pause ->active */
3281 mas_pause(&mas);
3282 entry = mas_find_rev(&mas, 0);
3283 MT_BUG_ON(mt, entry != ptr);
3284 MT_BUG_ON(mt, mas.index != 0x1000);
3285 MT_BUG_ON(mt, mas.last != 0x1500);
3286 MT_BUG_ON(mt, !mas_active(mas));
3287
3288 /* find_rev:active -> active */
3289 entry = mas_find_rev(&mas, 0);
3290 MT_BUG_ON(mt, entry != NULL);
3291 MT_BUG_ON(mt, mas.index != 0);
3292 MT_BUG_ON(mt, mas.last != 0x0FFF);
3293 MT_BUG_ON(mt, !mas_active(mas));
3294
3295 /* find_rev: start ->active */
3296 mas_set(&mas, 0x1200);
3297 entry = mas_find_rev(&mas, 0);
3298 MT_BUG_ON(mt, entry != ptr);
3299 MT_BUG_ON(mt, mas.index != 0x1000);
3300 MT_BUG_ON(mt, mas.last != 0x1500);
3301 MT_BUG_ON(mt, !mas_active(mas));
3302
3303 /* mas_walk start ->active */
3304 mas_set(&mas, 0x1200);
3305 entry = mas_walk(&mas);
3306 MT_BUG_ON(mt, entry != ptr);
3307 MT_BUG_ON(mt, mas.index != 0x1000);
3308 MT_BUG_ON(mt, mas.last != 0x1500);
3309 MT_BUG_ON(mt, !mas_active(mas));
3310
3311 /* mas_walk start ->active */
3312 mas_set(&mas, 0x1600);
3313 entry = mas_walk(&mas);
3314 MT_BUG_ON(mt, entry != NULL);
3315 MT_BUG_ON(mt, mas.index != 0x1501);
3316 MT_BUG_ON(mt, mas.last != 0x1fff);
3317 MT_BUG_ON(mt, !mas_active(mas));
3318
3319 /* mas_walk pause ->active */
3320 mas_set(&mas, 0x1200);
3321 mas_pause(&mas);
3322 entry = mas_walk(&mas);
3323 MT_BUG_ON(mt, entry != ptr);
3324 MT_BUG_ON(mt, mas.index != 0x1000);
3325 MT_BUG_ON(mt, mas.last != 0x1500);
3326 MT_BUG_ON(mt, !mas_active(mas));
3327
3328 /* mas_walk pause -> active */
3329 mas_set(&mas, 0x1600);
3330 mas_pause(&mas);
3331 entry = mas_walk(&mas);
3332 MT_BUG_ON(mt, entry != NULL);
3333 MT_BUG_ON(mt, mas.index != 0x1501);
3334 MT_BUG_ON(mt, mas.last != 0x1fff);
3335 MT_BUG_ON(mt, !mas_active(mas));
3336
3337 /* mas_walk none -> active */
3338 mas_set(&mas, 0x1200);
3339 mas.node = MAS_NONE;
3340 entry = mas_walk(&mas);
3341 MT_BUG_ON(mt, entry != ptr);
3342 MT_BUG_ON(mt, mas.index != 0x1000);
3343 MT_BUG_ON(mt, mas.last != 0x1500);
3344 MT_BUG_ON(mt, !mas_active(mas));
3345
3346 /* mas_walk none -> active */
3347 mas_set(&mas, 0x1600);
3348 mas.node = MAS_NONE;
3349 entry = mas_walk(&mas);
3350 MT_BUG_ON(mt, entry != NULL);
3351 MT_BUG_ON(mt, mas.index != 0x1501);
3352 MT_BUG_ON(mt, mas.last != 0x1fff);
3353 MT_BUG_ON(mt, !mas_active(mas));
3354
3355 /* mas_walk active -> active */
3356 mas.index = 0x1200;
3357 mas.last = 0x1200;
3358 mas.offset = 0;
3359 entry = mas_walk(&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_active(mas));
3364
3365 /* mas_walk active -> active */
3366 mas.index = 0x1600;
3367 mas.last = 0x1600;
3368 entry = mas_walk(&mas);
3369 MT_BUG_ON(mt, entry != NULL);
3370 MT_BUG_ON(mt, mas.index != 0x1501);
3371 MT_BUG_ON(mt, mas.last != 0x1fff);
3372 MT_BUG_ON(mt, !mas_active(mas));
3373
3374 mas_unlock(&mas);
3375 }
3376
3377 static DEFINE_MTREE(tree);
3378 static int __init maple_tree_seed(void)
3379 {
3380 unsigned long set[] = { 5015, 5014, 5017, 25, 1000,
3381 1001, 1002, 1003, 1005, 0,
3382 5003, 5002};
3383 void *ptr = &set;
3384
3385 pr_info("\nTEST STARTING\n\n");
3386
3387 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3388 check_root_expand(&tree);
3389 mtree_destroy(&tree);
3390
3391 #if defined(BENCH_SLOT_STORE)
3392 #define BENCH
3393 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3394 bench_slot_store(&tree);
3395 mtree_destroy(&tree);
3396 goto skip;
3397 #endif
3398 #if defined(BENCH_NODE_STORE)
3399 #define BENCH
3400 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3401 bench_node_store(&tree);
3402 mtree_destroy(&tree);
3403 goto skip;
3404 #endif
3405 #if defined(BENCH_AWALK)
3406 #define BENCH
3407 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3408 bench_awalk(&tree);
3409 mtree_destroy(&tree);
3410 goto skip;
3411 #endif
3412 #if defined(BENCH_WALK)
3413 #define BENCH
3414 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3415 bench_walk(&tree);
3416 mtree_destroy(&tree);
3417 goto skip;
3418 #endif
3419 #if defined(BENCH_FORK)
3420 #define BENCH
3421 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3422 bench_forking(&tree);
3423 mtree_destroy(&tree);
3424 goto skip;
3425 #endif
3426 #if defined(BENCH_MT_FOR_EACH)
3427 #define BENCH
3428 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3429 bench_mt_for_each(&tree);
3430 mtree_destroy(&tree);
3431 goto skip;
3432 #endif
3433
3434 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3435 check_iteration(&tree);
3436 mtree_destroy(&tree);
3437
3438 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3439 check_forking(&tree);
3440 mtree_destroy(&tree);
3441
3442 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3443 check_mas_store_gfp(&tree);
3444 mtree_destroy(&tree);
3445
3446 /* Test ranges (store and insert) */
3447 mt_init_flags(&tree, 0);
3448 check_ranges(&tree);
3449 mtree_destroy(&tree);
3450
3451 #if defined(CONFIG_64BIT)
3452 /* These tests have ranges outside of 4GB */
3453 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3454 check_alloc_range(&tree);
3455 mtree_destroy(&tree);
3456
3457 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3458 check_alloc_rev_range(&tree);
3459 mtree_destroy(&tree);
3460 #endif
3461
3462 mt_init_flags(&tree, 0);
3463
3464 check_load(&tree, set[0], NULL); /* See if 5015 -> NULL */
3465
3466 check_insert(&tree, set[9], &tree); /* Insert 0 */
3467 check_load(&tree, set[9], &tree); /* See if 0 -> &tree */
3468 check_load(&tree, set[0], NULL); /* See if 5015 -> NULL */
3469
3470 check_insert(&tree, set[10], ptr); /* Insert 5003 */
3471 check_load(&tree, set[9], &tree); /* See if 0 -> &tree */
3472 check_load(&tree, set[11], NULL); /* See if 5002 -> NULL */
3473 check_load(&tree, set[10], ptr); /* See if 5003 -> ptr */
3474
3475 /* Clear out the tree */
3476 mtree_destroy(&tree);
3477
3478 /* Try to insert, insert a dup, and load back what was inserted. */
3479 mt_init_flags(&tree, 0);
3480 check_insert(&tree, set[0], &tree); /* Insert 5015 */
3481 check_dup_insert(&tree, set[0], &tree); /* Insert 5015 again */
3482 check_load(&tree, set[0], &tree); /* See if 5015 -> &tree */
3483
3484 /*
3485 * Second set of tests try to load a value that doesn't exist, inserts
3486 * a second value, then loads the value again
3487 */
3488 check_load(&tree, set[1], NULL); /* See if 5014 -> NULL */
3489 check_insert(&tree, set[1], ptr); /* insert 5014 -> ptr */
3490 check_load(&tree, set[1], ptr); /* See if 5014 -> ptr */
3491 check_load(&tree, set[0], &tree); /* See if 5015 -> &tree */
3492 /*
3493 * Tree currently contains:
3494 * p[0]: 14 -> (nil) p[1]: 15 -> ptr p[2]: 16 -> &tree p[3]: 0 -> (nil)
3495 */
3496 check_insert(&tree, set[6], ptr); /* insert 1002 -> ptr */
3497 check_insert(&tree, set[7], &tree); /* insert 1003 -> &tree */
3498
3499 check_load(&tree, set[0], &tree); /* See if 5015 -> &tree */
3500 check_load(&tree, set[1], ptr); /* See if 5014 -> ptr */
3501 check_load(&tree, set[6], ptr); /* See if 1002 -> ptr */
3502 check_load(&tree, set[7], &tree); /* 1003 = &tree ? */
3503
3504 /* Clear out tree */
3505 mtree_destroy(&tree);
3506
3507 mt_init_flags(&tree, 0);
3508 /* Test inserting into a NULL hole. */
3509 check_insert(&tree, set[5], ptr); /* insert 1001 -> ptr */
3510 check_insert(&tree, set[7], &tree); /* insert 1003 -> &tree */
3511 check_insert(&tree, set[6], ptr); /* insert 1002 -> ptr */
3512 check_load(&tree, set[5], ptr); /* See if 1001 -> ptr */
3513 check_load(&tree, set[6], ptr); /* See if 1002 -> ptr */
3514 check_load(&tree, set[7], &tree); /* See if 1003 -> &tree */
3515
3516 /* Clear out the tree */
3517 mtree_destroy(&tree);
3518
3519 mt_init_flags(&tree, 0);
3520 /*
3521 * set[] = {5015, 5014, 5017, 25, 1000,
3522 * 1001, 1002, 1003, 1005, 0,
3523 * 5003, 5002};
3524 */
3525
3526 check_insert(&tree, set[0], ptr); /* 5015 */
3527 check_insert(&tree, set[1], &tree); /* 5014 */
3528 check_insert(&tree, set[2], ptr); /* 5017 */
3529 check_insert(&tree, set[3], &tree); /* 25 */
3530 check_load(&tree, set[0], ptr);
3531 check_load(&tree, set[1], &tree);
3532 check_load(&tree, set[2], ptr);
3533 check_load(&tree, set[3], &tree);
3534 check_insert(&tree, set[4], ptr); /* 1000 < Should split. */
3535 check_load(&tree, set[0], ptr);
3536 check_load(&tree, set[1], &tree);
3537 check_load(&tree, set[2], ptr);
3538 check_load(&tree, set[3], &tree); /*25 */
3539 check_load(&tree, set[4], ptr);
3540 check_insert(&tree, set[5], &tree); /* 1001 */
3541 check_load(&tree, set[0], ptr);
3542 check_load(&tree, set[1], &tree);
3543 check_load(&tree, set[2], ptr);
3544 check_load(&tree, set[3], &tree);
3545 check_load(&tree, set[4], ptr);
3546 check_load(&tree, set[5], &tree);
3547 check_insert(&tree, set[6], ptr);
3548 check_load(&tree, set[0], ptr);
3549 check_load(&tree, set[1], &tree);
3550 check_load(&tree, set[2], ptr);
3551 check_load(&tree, set[3], &tree);
3552 check_load(&tree, set[4], ptr);
3553 check_load(&tree, set[5], &tree);
3554 check_load(&tree, set[6], ptr);
3555 check_insert(&tree, set[7], &tree);
3556 check_load(&tree, set[0], ptr);
3557 check_insert(&tree, set[8], ptr);
3558
3559 check_insert(&tree, set[9], &tree);
3560
3561 check_load(&tree, set[0], ptr);
3562 check_load(&tree, set[1], &tree);
3563 check_load(&tree, set[2], ptr);
3564 check_load(&tree, set[3], &tree);
3565 check_load(&tree, set[4], ptr);
3566 check_load(&tree, set[5], &tree);
3567 check_load(&tree, set[6], ptr);
3568 check_load(&tree, set[9], &tree);
3569 mtree_destroy(&tree);
3570
3571 mt_init_flags(&tree, 0);
3572 check_seq(&tree, 16, false);
3573 mtree_destroy(&tree);
3574
3575 mt_init_flags(&tree, 0);
3576 check_seq(&tree, 1000, true);
3577 mtree_destroy(&tree);
3578
3579 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3580 check_rev_seq(&tree, 1000, true);
3581 mtree_destroy(&tree);
3582
3583 check_lower_bound_split(&tree);
3584 check_upper_bound_split(&tree);
3585 check_mid_split(&tree);
3586
3587 mt_init_flags(&tree, 0);
3588 check_next_entry(&tree);
3589 check_find(&tree);
3590 check_find_2(&tree);
3591 mtree_destroy(&tree);
3592
3593 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3594 check_prev_entry(&tree);
3595 mtree_destroy(&tree);
3596
3597 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3598 check_gap_combining(&tree);
3599 mtree_destroy(&tree);
3600
3601 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3602 check_node_overwrite(&tree);
3603 mtree_destroy(&tree);
3604
3605 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3606 next_prev_test(&tree);
3607 mtree_destroy(&tree);
3608
3609 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3610 check_spanning_relatives(&tree);
3611 mtree_destroy(&tree);
3612
3613 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3614 check_rev_find(&tree);
3615 mtree_destroy(&tree);
3616
3617 mt_init_flags(&tree, 0);
3618 check_fuzzer(&tree);
3619 mtree_destroy(&tree);
3620
3621 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3622 check_dup(&tree);
3623 mtree_destroy(&tree);
3624
3625 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3626 check_bnode_min_spanning(&tree);
3627 mtree_destroy(&tree);
3628
3629 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3630 check_empty_area_window(&tree);
3631 mtree_destroy(&tree);
3632
3633 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3634 check_empty_area_fill(&tree);
3635 mtree_destroy(&tree);
3636
3637
3638 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3639 check_state_handling(&tree);
3640 mtree_destroy(&tree);
3641
3642 #if defined(BENCH)
3643 skip:
3644 #endif
3645 rcu_barrier();
3646 pr_info("maple_tree: %u of %u tests passed\n",
3647 atomic_read(&maple_tree_tests_passed),
3648 atomic_read(&maple_tree_tests_run));
3649 if (atomic_read(&maple_tree_tests_run) ==
3650 atomic_read(&maple_tree_tests_passed))
3651 return 0;
3652
3653 return -EINVAL;
3654 }
3655
3656 static void __exit maple_tree_harvest(void)
3657 {
3658
3659 }
3660
3661 module_init(maple_tree_seed);
3662 module_exit(maple_tree_harvest);
3663 MODULE_AUTHOR("Liam R. Howlett <Liam.Howlett@Oracle.com>");
3664 MODULE_LICENSE("GPL");
A mirror of Linus' kernel repository