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