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