Quelle  test_maple_tree.c   Sprache: C

// SPDX-License-Identifier: GPL-2.0+
/*
 * test_maple_tree.c: Test the maple tree API
 * Copyright (c) 2018-2022 Oracle Corporation
 * Author: Liam R. Howlett <Liam.Howlett@Oracle.com>
 *
 * Any tests that only require the interface of the tree.
 */

#include <linux/maple_tree.h>
#include <linux/module.h>
#include <linux/rwsem.h>

#define MTREE_ALLOC_MAX 0x2000000000000Ul
#define CONFIG_MAPLE_SEARCH
#define MAPLE_32BIT (MAPLE_NODE_SLOTS > 31)

#ifndef CONFIG_DEBUG_MAPLE_TREE
#define mt_dump(mt, fmt)  do {} while (0)
#define mt_validate(mt)   do {} while (0)
#define mt_cache_shrink()  do {} while (0)
#define mas_dump(mas)   do {} while (0)
#define mas_wr_dump(mas)  do {} while (0)
atomic_t maple_tree_tests_run;
atomic_t maple_tree_tests_passed;
#undef MT_BUG_ON

#define MT_BUG_ON(__tree, __x) do {     \
 atomic_inc(&maple_tree_tests_run);    \
 if (__x) {       \
  pr_info("BUG at %s:%d (%u)\n",    \
  __func__, __LINE__, __x);    \
  pr_info("Pass: %u Run:%u\n",    \
   atomic_read(&maple_tree_tests_passed),  \
   atomic_read(&maple_tree_tests_run));  \
 } else {       \
  atomic_inc(&maple_tree_tests_passed);   \
 }        \
} while (0)
#endif

/* #define BENCH_SLOT_STORE */
/* #define BENCH_NODE_STORE */
/* #define BENCH_AWALK */
/* #define BENCH_WALK */
/* #define BENCH_LOAD */
/* #define BENCH_MT_FOR_EACH */
/* #define BENCH_FORK */
/* #define BENCH_MAS_FOR_EACH */
/* #define BENCH_MAS_PREV */

#ifdef __KERNEL__
#define mt_set_non_kernel(x)  do {} while (0)
#define mt_zero_nr_tallocated(x) do {} while (0)
#else
#define cond_resched()   do {} while (0)
#endif

#define mas_is_none(x)  ((x)->status == ma_none)
#define mas_is_overflow(x) ((x)->status == ma_overflow)
#define mas_is_underflow(x) ((x)->status == ma_underflow)

static int __init mtree_insert_index(struct maple_tree *mt,
         unsigned long index, gfp_t gfp)
{
 return mtree_insert(mt, index, xa_mk_value(index & LONG_MAX), gfp);
}

static void __init mtree_erase_index(struct maple_tree *mt, unsigned long index)
{
 MT_BUG_ON(mt, mtree_erase(mt, index) != xa_mk_value(index & LONG_MAX));
 MT_BUG_ON(mt, mtree_load(mt, index) != NULL);
}

static int __init mtree_test_insert(struct maple_tree *mt, unsigned long index,
    void *ptr)
{
 return mtree_insert(mt, index, ptr, GFP_KERNEL);
}

static int __init mtree_test_store_range(struct maple_tree *mt,
   unsigned long start, unsigned long end, void *ptr)
{
 return mtree_store_range(mt, start, end, ptr, GFP_KERNEL);
}

static int __init mtree_test_store(struct maple_tree *mt, unsigned long start,
    void *ptr)
{
 return mtree_test_store_range(mt, start, start, ptr);
}

static int __init mtree_test_insert_range(struct maple_tree *mt,
   unsigned long start, unsigned long end, void *ptr)
{
 return mtree_insert_range(mt, start, end, ptr, GFP_KERNEL);
}

static void __init *mtree_test_load(struct maple_tree *mt, unsigned long index)
{
 return mtree_load(mt, index);
}

static void __init *mtree_test_erase(struct maple_tree *mt, unsigned long index)
{
 return mtree_erase(mt, index);
}

#if defined(CONFIG_64BIT)
static noinline void __init check_mtree_alloc_range(struct maple_tree *mt,
  unsigned long start, unsigned long end, unsigned long size,
  unsigned long expected, int eret, void *ptr)
{

 unsigned long result = expected + 1;
 int ret;

 ret = mtree_alloc_range(mt, &result, ptr, size, start, end,
   GFP_KERNEL);
 MT_BUG_ON(mt, ret != eret);
 if (ret)
  return;

 MT_BUG_ON(mt, result != expected);
}

static noinline void __init check_mtree_alloc_rrange(struct maple_tree *mt,
  unsigned long start, unsigned long end, unsigned long size,
  unsigned long expected, int eret, void *ptr)
{

 unsigned long result = expected + 1;
 int ret;

 ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end,
   GFP_KERNEL);
 MT_BUG_ON(mt, ret != eret);
 if (ret)
  return;

 MT_BUG_ON(mt, result != expected);
}
#endif

static noinline void __init check_load(struct maple_tree *mt,
           unsigned long index, void *ptr)
{
 void *ret = mtree_test_load(mt, index);

 if (ret != ptr)
  pr_err("Load %lu returned %p expect %p\n", index, ret, ptr);
 MT_BUG_ON(mt, ret != ptr);
}

static noinline void __init check_store_range(struct maple_tree *mt,
  unsigned long start, unsigned long end, void *ptr, int expected)
{
 int ret = -EINVAL;
 unsigned long i;

 ret = mtree_test_store_range(mt, start, end, ptr);
 MT_BUG_ON(mt, ret != expected);

 if (ret)
  return;

 for (i = start; i <= end; i++)
  check_load(mt, i, ptr);
}

static noinline void __init check_insert_range(struct maple_tree *mt,
  unsigned long start, unsigned long end, void *ptr, int expected)
{
 int ret = -EINVAL;
 unsigned long i;

 ret = mtree_test_insert_range(mt, start, end, ptr);
 MT_BUG_ON(mt, ret != expected);

 if (ret)
  return;

 for (i = start; i <= end; i++)
  check_load(mt, i, ptr);
}

static noinline void __init check_insert(struct maple_tree *mt,
      unsigned long index, void *ptr)
{
 int ret = -EINVAL;

 ret = mtree_test_insert(mt, index, ptr);
 MT_BUG_ON(mt, ret != 0);
}

static noinline void __init check_dup_insert(struct maple_tree *mt,
          unsigned long index, void *ptr)
{
 int ret = -EINVAL;

 ret = mtree_test_insert(mt, index, ptr);
 MT_BUG_ON(mt, ret != -EEXIST);
}


static noinline void __init check_index_load(struct maple_tree *mt,
          unsigned long index)
{
 return check_load(mt, index, xa_mk_value(index & LONG_MAX));
}

static inline __init int not_empty(struct maple_node *node)
{
 int i;

 if (node->parent)
  return 1;

 for (i = 0; i < ARRAY_SIZE(node->slot); i++)
  if (node->slot[i])
   return 1;

 return 0;
}


static noinline void __init check_rev_seq(struct maple_tree *mt,
       unsigned long max, bool verbose)
{
 unsigned long i = max, j;

 MT_BUG_ON(mt, !mtree_empty(mt));

 mt_zero_nr_tallocated();
 while (i) {
  MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL));
  for (j = i; j <= max; j++)
   check_index_load(mt, j);

  check_load(mt, i - 1, NULL);
  mt_set_in_rcu(mt);
  MT_BUG_ON(mt, !mt_height(mt));
  mt_clear_in_rcu(mt);
  MT_BUG_ON(mt, !mt_height(mt));
  i--;
 }
 check_load(mt, max + 1, NULL);

#ifndef __KERNEL__
 if (verbose) {
  rcu_barrier();
  mt_dump(mt, mt_dump_dec);
  pr_info(" %s test of 0-%lu %luK in %d active (%d total)\n",
   __func__, max, mt_get_alloc_size()/1024, mt_nr_allocated(),
   mt_nr_tallocated());
 }
#endif
}

static noinline void __init check_seq(struct maple_tree *mt, unsigned long max,
  bool verbose)
{
 unsigned long i, j;

 MT_BUG_ON(mt, !mtree_empty(mt));

 mt_zero_nr_tallocated();
 for (i = 0; i <= max; i++) {
  MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL));
  for (j = 0; j <= i; j++)
   check_index_load(mt, j);

  if (i)
   MT_BUG_ON(mt, !mt_height(mt));
  check_load(mt, i + 1, NULL);
 }

#ifndef __KERNEL__
 if (verbose) {
  rcu_barrier();
  mt_dump(mt, mt_dump_dec);
  pr_info(" seq test of 0-%lu %luK in %d active (%d total)\n",
   max, mt_get_alloc_size()/1024, mt_nr_allocated(),
   mt_nr_tallocated());
 }
#endif
}

static noinline void __init check_lb_not_empty(struct maple_tree *mt)
{
 unsigned long i, j;
 unsigned long huge = 4000UL * 1000 * 1000;


 i = huge;
 while (i > 4096) {
  check_insert(mt, i, (void *) i);
  for (j = huge; j >= i; j /= 2) {
   check_load(mt, j-1, NULL);
   check_load(mt, j, (void *) j);
   check_load(mt, j+1, NULL);
  }
  i /= 2;
 }
 mtree_destroy(mt);
}

static noinline void __init check_lower_bound_split(struct maple_tree *mt)
{
 MT_BUG_ON(mt, !mtree_empty(mt));
 check_lb_not_empty(mt);
}

static noinline void __init check_upper_bound_split(struct maple_tree *mt)
{
 unsigned long i, j;
 unsigned long huge;

 MT_BUG_ON(mt, !mtree_empty(mt));

 if (MAPLE_32BIT)
  huge = 2147483647UL;
 else
  huge = 4000UL * 1000 * 1000;

 i = 4096;
 while (i < huge) {
  check_insert(mt, i, (void *) i);
  for (j = i; j >= huge; j *= 2) {
   check_load(mt, j-1, NULL);
   check_load(mt, j, (void *) j);
   check_load(mt, j+1, NULL);
  }
  i *= 2;
 }
 mtree_destroy(mt);
}

static noinline void __init check_mid_split(struct maple_tree *mt)
{
 unsigned long huge = 8000UL * 1000 * 1000;

 check_insert(mt, huge, (void *) huge);
 check_insert(mt, 0, xa_mk_value(0));
 check_lb_not_empty(mt);
}

static noinline void __init check_rev_find(struct maple_tree *mt)
{
 int i, nr_entries = 200;
 void *val;
 MA_STATE(mas, mt, 0, 0);

 for (i = 0; i <= nr_entries; i++)
  mtree_store_range(mt, i*10, i*10 + 5,
      xa_mk_value(i), GFP_KERNEL);

 rcu_read_lock();
 mas_set(&mas, 1000);
 val = mas_find_rev(&mas, 1000);
 MT_BUG_ON(mt, val != xa_mk_value(100));
 val = mas_find_rev(&mas, 1000);
 MT_BUG_ON(mt, val != NULL);

 mas_set(&mas, 999);
 val = mas_find_rev(&mas, 997);
 MT_BUG_ON(mt, val != NULL);

 mas_set(&mas, 1000);
 val = mas_find_rev(&mas, 900);
 MT_BUG_ON(mt, val != xa_mk_value(100));
 val = mas_find_rev(&mas, 900);
 MT_BUG_ON(mt, val != xa_mk_value(99));

 mas_set(&mas, 20);
 val = mas_find_rev(&mas, 0);
 MT_BUG_ON(mt, val != xa_mk_value(2));
 val = mas_find_rev(&mas, 0);
 MT_BUG_ON(mt, val != xa_mk_value(1));
 val = mas_find_rev(&mas, 0);
 MT_BUG_ON(mt, val != xa_mk_value(0));
 val = mas_find_rev(&mas, 0);
 MT_BUG_ON(mt, val != NULL);
 rcu_read_unlock();
}

static noinline void __init check_find(struct maple_tree *mt)
{
 unsigned long val = 0;
 unsigned long count;
 unsigned long max;
 unsigned long top;
 unsigned long last = 0, index = 0;
 void *entry, *entry2;

 MA_STATE(mas, mt, 0, 0);

 /* Insert 0. */
 MT_BUG_ON(mt, mtree_insert_index(mt, val++, GFP_KERNEL));

#if defined(CONFIG_64BIT)
 top = 4398046511104UL;
#else
 top = ULONG_MAX;
#endif

 if (MAPLE_32BIT) {
  count = 15;
 } else {
  count = 20;
 }

 for (int i = 0; i <= count; i++) {
  if (val != 64)
   MT_BUG_ON(mt, mtree_insert_index(mt, val, GFP_KERNEL));
  else
   MT_BUG_ON(mt, mtree_insert(mt, val,
    XA_ZERO_ENTRY, GFP_KERNEL));

  val <<= 2;
 }

 val = 0;
 mas_set(&mas, val);
 mas_lock(&mas);
 while ((entry = mas_find(&mas, 268435456)) != NULL) {
  if (val != 64)
   MT_BUG_ON(mt, xa_mk_value(val) != entry);
  else
   MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);

  val <<= 2;
  /* For zero check. */
  if (!val)
   val = 1;
 }
 mas_unlock(&mas);

 val = 0;
 mas_set(&mas, val);
 mas_lock(&mas);
 mas_for_each(&mas, entry, ULONG_MAX) {
  if (val != 64)
   MT_BUG_ON(mt, xa_mk_value(val) != entry);
  else
   MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
  val <<= 2;
  /* For zero check. */
  if (!val)
   val = 1;
 }
 mas_unlock(&mas);

 /* Test mas_pause */
 val = 0;
 mas_set(&mas, val);
 mas_lock(&mas);
 mas_for_each(&mas, entry, ULONG_MAX) {
  if (val != 64)
   MT_BUG_ON(mt, xa_mk_value(val) != entry);
  else
   MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
  val <<= 2;
  /* For zero check. */
  if (!val)
   val = 1;

  mas_pause(&mas);
  mas_unlock(&mas);
  mas_lock(&mas);
 }
 mas_unlock(&mas);

 val = 0;
 max = 300; /* A value big enough to include XA_ZERO_ENTRY at 64. */
 mt_for_each(mt, entry, index, max) {
  MT_BUG_ON(mt, xa_mk_value(val) != entry);
  val <<= 2;
  if (val == 64) /* Skip zero entry. */
   val <<= 2;
  /* For zero check. */
  if (!val)
   val = 1;
 }

 val = 0;
 max = 0;
 index = 0;
 MT_BUG_ON(mt, mtree_insert_index(mt, ULONG_MAX, GFP_KERNEL));
 mt_for_each(mt, entry, index, ULONG_MAX) {
  if (val == top)
   MT_BUG_ON(mt, entry != xa_mk_value(LONG_MAX));
  else
   MT_BUG_ON(mt, xa_mk_value(val) != entry);

  /* Workaround for 32bit */
  if ((val << 2) < val)
   val = ULONG_MAX;
  else
   val <<= 2;

  if (val == 64) /* Skip zero entry. */
   val <<= 2;
  /* For zero check. */
  if (!val)
   val = 1;
  max++;
  MT_BUG_ON(mt, max > 25);
 }
 mtree_erase_index(mt, ULONG_MAX);

 mas_reset(&mas);
 index = 17;
 entry = mt_find(mt, &index, 512);
 MT_BUG_ON(mt, xa_mk_value(256) != entry);

 mas_reset(&mas);
 index = 17;
 entry = mt_find(mt, &index, 20);
 MT_BUG_ON(mt, entry != NULL);


 /* Range check.. */
 /* Insert ULONG_MAX */
 MT_BUG_ON(mt, mtree_insert_index(mt, ULONG_MAX, GFP_KERNEL));

 val = 0;
 mas_set(&mas, 0);
 mas_lock(&mas);
 mas_for_each(&mas, entry, ULONG_MAX) {
  if (val == 64)
   MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
  else if (val == top)
   MT_BUG_ON(mt, entry != xa_mk_value(LONG_MAX));
  else
   MT_BUG_ON(mt, xa_mk_value(val) != entry);

  /* Workaround for 32bit */
  if ((val << 2) < val)
   val = ULONG_MAX;
  else
   val <<= 2;

  /* For zero check. */
  if (!val)
   val = 1;
  mas_pause(&mas);
  mas_unlock(&mas);
  mas_lock(&mas);
 }
 mas_unlock(&mas);

 mas_set(&mas, 1048576);
 mas_lock(&mas);
 entry = mas_find(&mas, 1048576);
 mas_unlock(&mas);
 MT_BUG_ON(mas.tree, entry == NULL);

 /*
 * Find last value.
 * 1. get the expected value, leveraging the existence of an end entry
 * 2. delete end entry
 * 3. find the last value but searching for ULONG_MAX and then using
 * prev
 */
 /* First, get the expected result. */
 mas_lock(&mas);
 mas_reset(&mas);
 mas.index = ULONG_MAX; /* start at max.. */
 entry = mas_find(&mas, ULONG_MAX);
 entry = mas_prev(&mas, 0);
 index = mas.index;
 last = mas.last;

 /* Erase the last entry. */
 mas_reset(&mas);
 mas.index = ULONG_MAX;
 mas.last = ULONG_MAX;
 mas_erase(&mas);

 /* Get the previous value from MAS_START */
 mas_reset(&mas);
 entry2 = mas_prev(&mas, 0);

 /* Check results. */
 MT_BUG_ON(mt, entry != entry2);
 MT_BUG_ON(mt, index != mas.index);
 MT_BUG_ON(mt, last != mas.last);


 mas.status = ma_none;
 mas.index = ULONG_MAX;
 mas.last = ULONG_MAX;
 entry2 = mas_prev(&mas, 0);
 MT_BUG_ON(mt, entry != entry2);

 mas_set(&mas, 0);
 MT_BUG_ON(mt, mas_prev(&mas, 0) != NULL);

 mas_unlock(&mas);
 mtree_destroy(mt);
}

static noinline void __init check_find_2(struct maple_tree *mt)
{
 unsigned long i, j;
 void *entry;

 MA_STATE(mas, mt, 0, 0);
 rcu_read_lock();
 mas_for_each(&mas, entry, ULONG_MAX)
  MT_BUG_ON(mt, true);
 rcu_read_unlock();

 for (i = 0; i < 256; i++) {
  mtree_insert_index(mt, i, GFP_KERNEL);
  j = 0;
  mas_set(&mas, 0);
  rcu_read_lock();
  mas_for_each(&mas, entry, ULONG_MAX) {
   MT_BUG_ON(mt, entry != xa_mk_value(j));
   j++;
  }
  rcu_read_unlock();
  MT_BUG_ON(mt, j != i + 1);
 }

 for (i = 0; i < 256; i++) {
  mtree_erase_index(mt, i);
  j = i + 1;
  mas_set(&mas, 0);
  rcu_read_lock();
  mas_for_each(&mas, entry, ULONG_MAX) {
   if (xa_is_zero(entry))
    continue;

   MT_BUG_ON(mt, entry != xa_mk_value(j));
   j++;
  }
  rcu_read_unlock();
  MT_BUG_ON(mt, j != 256);
 }

 /*MT_BUG_ON(mt, !mtree_empty(mt)); */
}


#if defined(CONFIG_64BIT)
static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
{
 /*
 * Generated by:
 * cat /proc/self/maps | awk '{print $1}'|
 * awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}'
 */

 static const unsigned long range[] = {
 /*      Inclusive     , Exclusive. */
  0x565234af2000, 0x565234af4000,
  0x565234af4000, 0x565234af9000,
  0x565234af9000, 0x565234afb000,
  0x565234afc000, 0x565234afd000,
  0x565234afd000, 0x565234afe000,
  0x565235def000, 0x565235e10000,
  0x7f36d4bfd000, 0x7f36d4ee2000,
  0x7f36d4ee2000, 0x7f36d4f04000,
  0x7f36d4f04000, 0x7f36d504c000,
  0x7f36d504c000, 0x7f36d5098000,
  0x7f36d5098000, 0x7f36d5099000,
  0x7f36d5099000, 0x7f36d509d000,
  0x7f36d509d000, 0x7f36d509f000,
  0x7f36d509f000, 0x7f36d50a5000,
  0x7f36d50b9000, 0x7f36d50db000,
  0x7f36d50db000, 0x7f36d50dc000,
  0x7f36d50dc000, 0x7f36d50fa000,
  0x7f36d50fa000, 0x7f36d5102000,
  0x7f36d5102000, 0x7f36d5103000,
  0x7f36d5103000, 0x7f36d5104000,
  0x7f36d5104000, 0x7f36d5105000,
  0x7fff5876b000, 0x7fff5878d000,
  0x7fff5878e000, 0x7fff58791000,
  0x7fff58791000, 0x7fff58793000,
 };

 static const unsigned long holes[] = {
  /*
 * Note: start of hole is INCLUSIVE
 *        end of hole is EXCLUSIVE
 *        (opposite of the above table.)
 * Start of hole, end of hole,  size of hole (+1)
 */
  0x565234afb000, 0x565234afc000, 0x1000,
  0x565234afe000, 0x565235def000, 0x12F1000,
  0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000,
 };

 /*
 * req_range consists of 4 values.
 * 1. min index
 * 2. max index
 * 3. size
 * 4. number that should be returned.
 * 5. return value
 */
 static const unsigned long req_range[] = {
  0x565234af9000, /* Min */
  0x7fff58791000, /* Max */
  0x1000,         /* Size */
  0x7fff5878d << 12,  /* First rev hole of size 0x1000 */
  0,              /* Return value success. */

  0x0,            /* Min */
  0x565234AF0 << 12,    /* Max */
  0x3000,         /* Size */
  0x565234AEE << 12,  /* max - 3. */
  0,              /* Return value success. */

  0x0,            /* Min */
  -1,             /* Max */
  0x1000,         /* Size */
  562949953421311 << 12,/* First rev hole of size 0x1000 */
  0,              /* Return value success. */

  0x0,            /* Min */
  0x7F36D5109 << 12,    /* Max */
  0x4000,         /* Size */
  0x7F36D5106 << 12,    /* First rev hole of size 0x4000 */
  0,              /* Return value success. */

  /* Ascend test. */
  0x0,
  34148798628 << 12,
  19 << 12,
  34148797418 << 12,
  0x0,

  /* Too big test. */
  0x0,
  18446744073709551615UL,
  562915594369134UL << 12,
  0x0,
  -EBUSY,

  /* Single space test. */
  34148798725 << 12,
  34148798725 << 12,
  1 << 12,
  34148798725 << 12,
  0,
 };

 int i, range_count = ARRAY_SIZE(range);
 int req_range_count = ARRAY_SIZE(req_range);
 unsigned long min = 0;

 MA_STATE(mas, mt, 0, 0);

 mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY,
     GFP_KERNEL);
#define DEBUG_REV_RANGE 0
 for (i = 0; i < range_count; i += 2) {
  /* Inclusive, Inclusive (with the -1) */

#if DEBUG_REV_RANGE
  pr_debug("\t%s: Insert %lu-%lu\n", __func__, range[i] >> 12,
    (range[i + 1] >> 12) - 1);
#endif
  check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1,
    xa_mk_value(range[i] >> 12), 0);
  mt_validate(mt);
 }


 mas_lock(&mas);
 for (i = 0; i < ARRAY_SIZE(holes); i += 3) {
#if DEBUG_REV_RANGE
  pr_debug("Search from %lu-%lu for gap %lu should be at %lu\n",
    min, holes[i+1]>>12, holes[i+2]>>12,
    holes[i] >> 12);
#endif
  MT_BUG_ON(mt, mas_empty_area_rev(&mas, min,
     holes[i+1] >> 12,
     holes[i+2] >> 12));
#if DEBUG_REV_RANGE
  pr_debug("Found %lu %lu\n", mas.index, mas.last);
  pr_debug("gap %lu %lu\n", (holes[i] >> 12),
    (holes[i+1] >> 12));
#endif
  MT_BUG_ON(mt, mas.last + 1 != (holes[i+1] >> 12));
  MT_BUG_ON(mt, mas.index != (holes[i+1] >> 12) - (holes[i+2] >> 12));
  min = holes[i+1] >> 12;
  mas_reset(&mas);
 }

 mas_unlock(&mas);
 for (i = 0; i < req_range_count; i += 5) {
#if DEBUG_REV_RANGE
  pr_debug("\tReverse request %d between %lu-%lu size %lu, should get %lu\n",
    i, req_range[i] >> 12,
    (req_range[i + 1] >> 12),
    req_range[i+2] >> 12,
    req_range[i+3] >> 12);
#endif
  check_mtree_alloc_rrange(mt,
    req_range[i]   >> 12, /* start */
    req_range[i+1] >> 12, /* end */
    req_range[i+2] >> 12, /* size */
    req_range[i+3] >> 12, /* expected address */
    req_range[i+4],       /* expected return */
    xa_mk_value(req_range[i] >> 12)); /* pointer */
  mt_validate(mt);
 }

 mt_set_non_kernel(1);
 mtree_erase(mt, 34148798727); /* create a deleted range. */
 mtree_erase(mt, 34148798725);
 check_mtree_alloc_rrange(mt, 0, 34359052173, 210253414,
   34148798725, 0, mt);

 mtree_destroy(mt);
}

static noinline void __init check_alloc_range(struct maple_tree *mt)
{
 /*
 * Generated by:
 * cat /proc/self/maps|awk '{print $1}'|
 * awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}'
 */

 static const unsigned long range[] = {
 /*      Inclusive     , Exclusive. */
  0x565234af2000, 0x565234af4000,
  0x565234af4000, 0x565234af9000,
  0x565234af9000, 0x565234afb000,
  0x565234afc000, 0x565234afd000,
  0x565234afd000, 0x565234afe000,
  0x565235def000, 0x565235e10000,
  0x7f36d4bfd000, 0x7f36d4ee2000,
  0x7f36d4ee2000, 0x7f36d4f04000,
  0x7f36d4f04000, 0x7f36d504c000,
  0x7f36d504c000, 0x7f36d5098000,
  0x7f36d5098000, 0x7f36d5099000,
  0x7f36d5099000, 0x7f36d509d000,
  0x7f36d509d000, 0x7f36d509f000,
  0x7f36d509f000, 0x7f36d50a5000,
  0x7f36d50b9000, 0x7f36d50db000,
  0x7f36d50db000, 0x7f36d50dc000,
  0x7f36d50dc000, 0x7f36d50fa000,
  0x7f36d50fa000, 0x7f36d5102000,
  0x7f36d5102000, 0x7f36d5103000,
  0x7f36d5103000, 0x7f36d5104000,
  0x7f36d5104000, 0x7f36d5105000,
  0x7fff5876b000, 0x7fff5878d000,
  0x7fff5878e000, 0x7fff58791000,
  0x7fff58791000, 0x7fff58793000,
 };
 static const unsigned long holes[] = {
  /* Start of hole, end of hole,  size of hole (+1) */
  0x565234afb000, 0x565234afc000, 0x1000,
  0x565234afe000, 0x565235def000, 0x12F1000,
  0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000,
 };

 /*
 * req_range consists of 4 values.
 * 1. min index
 * 2. max index
 * 3. size
 * 4. number that should be returned.
 * 5. return value
 */
 static const unsigned long req_range[] = {
  0x565234af9000, /* Min */
  0x7fff58791000, /* Max */
  0x1000,         /* Size */
  0x565234afb000, /* First hole in our data of size 1000. */
  0,              /* Return value success. */

  0x0,            /* Min */
  0x7fff58791000, /* Max */
  0x1F00,         /* Size */
  0x0,            /* First hole in our data of size 2000. */
  0,              /* Return value success. */

  /* Test ascend. */
  34148797436 << 12, /* Min */
  0x7fff587AF000,    /* Max */
  0x3000,         /* Size */
  34148798629 << 12,             /* Expected location */
  0,              /* Return value success. */

  /* Test failing. */
  34148798623 << 12,  /* Min */
  34148798683 << 12,  /* Max */
  0x15000,            /* Size */
  0,             /* Expected location */
  -EBUSY,              /* Return value failed. */

  /* Test filling entire gap. */
  34148798623 << 12,  /* Min */
  0x7fff587AF000,    /* Max */
  0x10000,           /* Size */
  34148798632 << 12,             /* Expected location */
  0,              /* Return value success. */

  /* Test walking off the end of root. */
  0,                  /* Min */
  -1,                 /* Max */
  -1,                 /* Size */
  0,                  /* Expected location */
  -EBUSY,             /* Return value failure. */

  /* Test looking for too large a hole across entire range. */
  0,                  /* Min */
  -1,                 /* Max */
  4503599618982063UL << 12,  /* Size */
  34359052178 << 12,  /* Expected location */
  -EBUSY,             /* Return failure. */

  /* Test a single entry */
  34148798648 << 12,  /* Min */
  34148798648 << 12,  /* Max */
  4096,   /* Size of 1 */
  34148798648 << 12, /* Location is the same as min/max */
  0,   /* Success */
 };
 int i, range_count = ARRAY_SIZE(range);
 int req_range_count = ARRAY_SIZE(req_range);
 unsigned long min = 0x565234af2000;
 MA_STATE(mas, mt, 0, 0);

 mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY,
     GFP_KERNEL);
 for (i = 0; i < range_count; i += 2) {
#define DEBUG_ALLOC_RANGE 0
#if DEBUG_ALLOC_RANGE
  pr_debug("\tInsert %lu-%lu\n", range[i] >> 12,
    (range[i + 1] >> 12) - 1);
  mt_dump(mt, mt_dump_hex);
#endif
  check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1,
    xa_mk_value(range[i] >> 12), 0);
  mt_validate(mt);
 }



 mas_lock(&mas);
 for (i = 0; i < ARRAY_SIZE(holes); i += 3) {

#if DEBUG_ALLOC_RANGE
  pr_debug("\tGet empty %lu-%lu size %lu (%lx-%lx)\n", min >> 12,
   holes[i+1] >> 12, holes[i+2] >> 12,
   min, holes[i+1]);
#endif
  MT_BUG_ON(mt, mas_empty_area(&mas, min >> 12,
     holes[i+1] >> 12,
     holes[i+2] >> 12));
  MT_BUG_ON(mt, mas.index != holes[i] >> 12);
  min = holes[i+1];
  mas_reset(&mas);
 }
 mas_unlock(&mas);
 for (i = 0; i < req_range_count; i += 5) {
#if DEBUG_ALLOC_RANGE
  pr_debug("\tTest %d: %lu-%lu size %lu expected %lu (%lu-%lu)\n",
    i/5, req_range[i]   >> 12, req_range[i + 1]   >> 12,
    req_range[i + 2]   >> 12, req_range[i + 3]   >> 12,
    req_range[i], req_range[i+1]);
#endif
  check_mtree_alloc_range(mt,
    req_range[i]   >> 12, /* start */
    req_range[i+1] >> 12, /* end */
    req_range[i+2] >> 12, /* size */
    req_range[i+3] >> 12, /* expected address */
    req_range[i+4],       /* expected return */
    xa_mk_value(req_range[i] >> 12)); /* pointer */
  mt_validate(mt);
#if DEBUG_ALLOC_RANGE
  mt_dump(mt, mt_dump_hex);
#endif
 }

 mtree_destroy(mt);
}
#endif

static noinline void __init check_ranges(struct maple_tree *mt)
{
 int i, val, val2;
 static const unsigned long r[] = {
  10, 15,
  20, 25,
  17, 22, /* Overlaps previous range. */
  9, 1000, /* Huge. */
  100, 200,
  45, 168,
  118, 128,
   };

 MT_BUG_ON(mt, !mtree_empty(mt));
 check_insert_range(mt, r[0], r[1], xa_mk_value(r[0]), 0);
 check_insert_range(mt, r[2], r[3], xa_mk_value(r[2]), 0);
 check_insert_range(mt, r[4], r[5], xa_mk_value(r[4]), -EEXIST);
 MT_BUG_ON(mt, !mt_height(mt));
 /* Store */
 check_store_range(mt, r[4], r[5], xa_mk_value(r[4]), 0);
 check_store_range(mt, r[6], r[7], xa_mk_value(r[6]), 0);
 check_store_range(mt, r[8], r[9], xa_mk_value(r[8]), 0);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);
 MT_BUG_ON(mt, mt_height(mt));

 check_seq(mt, 50, false);
 mt_set_non_kernel(4);
 check_store_range(mt, 5, 47,  xa_mk_value(47), 0);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);

 /* Create tree of 1-100 */
 check_seq(mt, 100, false);
 /* Store 45-168 */
 mt_set_non_kernel(10);
 check_store_range(mt, r[10], r[11], xa_mk_value(r[10]), 0);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);

 /* Create tree of 1-200 */
 check_seq(mt, 200, false);
 /* Store 45-168 */
 check_store_range(mt, r[10], r[11], xa_mk_value(r[10]), 0);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);

 check_seq(mt, 30, false);
 check_store_range(mt, 6, 18, xa_mk_value(6), 0);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);

 /* Overwrite across multiple levels. */
 /* Create tree of 1-400 */
 check_seq(mt, 400, false);
 mt_set_non_kernel(50);
 /* Store 118-128 */
 check_store_range(mt, r[12], r[13], xa_mk_value(r[12]), 0);
 mt_set_non_kernel(50);
 mtree_test_erase(mt, 140);
 mtree_test_erase(mt, 141);
 mtree_test_erase(mt, 142);
 mtree_test_erase(mt, 143);
 mtree_test_erase(mt, 130);
 mtree_test_erase(mt, 131);
 mtree_test_erase(mt, 132);
 mtree_test_erase(mt, 133);
 mtree_test_erase(mt, 134);
 mtree_test_erase(mt, 135);
 check_load(mt, r[12], xa_mk_value(r[12]));
 check_load(mt, r[13], xa_mk_value(r[12]));
 check_load(mt, r[13] - 1, xa_mk_value(r[12]));
 check_load(mt, r[13] + 1, xa_mk_value(r[13] + 1));
 check_load(mt, 135, NULL);
 check_load(mt, 140, NULL);
 mt_set_non_kernel(0);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);



 /* Overwrite multiple levels at the end of the tree (slot 7) */
 mt_set_non_kernel(50);
 check_seq(mt, 400, false);
 check_store_range(mt, 353, 361, xa_mk_value(353), 0);
 check_store_range(mt, 347, 352, xa_mk_value(347), 0);

 check_load(mt, 346, xa_mk_value(346));
 for (i = 347; i <= 352; i++)
  check_load(mt, i, xa_mk_value(347));
 for (i = 353; i <= 361; i++)
  check_load(mt, i, xa_mk_value(353));
 check_load(mt, 362, xa_mk_value(362));
 mt_set_non_kernel(0);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);

 mt_set_non_kernel(50);
 check_seq(mt, 400, false);
 check_store_range(mt, 352, 364, NULL, 0);
 check_store_range(mt, 351, 363, xa_mk_value(352), 0);
 check_load(mt, 350, xa_mk_value(350));
 check_load(mt, 351, xa_mk_value(352));
 for (i = 352; i <= 363; i++)
  check_load(mt, i, xa_mk_value(352));
 check_load(mt, 364, NULL);
 check_load(mt, 365, xa_mk_value(365));
 mt_set_non_kernel(0);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);

 mt_set_non_kernel(5);
 check_seq(mt, 400, false);
 check_store_range(mt, 352, 364, NULL, 0);
 check_store_range(mt, 351, 364, xa_mk_value(352), 0);
 check_load(mt, 350, xa_mk_value(350));
 check_load(mt, 351, xa_mk_value(352));
 for (i = 352; i <= 364; i++)
  check_load(mt, i, xa_mk_value(352));
 check_load(mt, 365, xa_mk_value(365));
 mt_set_non_kernel(0);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);


 mt_set_non_kernel(50);
 check_seq(mt, 400, false);
 check_store_range(mt, 362, 367, xa_mk_value(362), 0);
 check_store_range(mt, 353, 361, xa_mk_value(353), 0);
 mt_set_non_kernel(0);
 mt_validate(mt);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);
 /*
 * Interesting cases:
 * 1. Overwrite the end of a node and end in the first entry of the next
 * node.
 * 2. Split a single range
 * 3. Overwrite the start of a range
 * 4. Overwrite the end of a range
 * 5. Overwrite the entire range
 * 6. Overwrite a range that causes multiple parent nodes to be
 * combined
 * 7. Overwrite a range that causes multiple parent nodes and part of
 * root to be combined
 * 8. Overwrite the whole tree
 * 9. Try to overwrite the zero entry of an alloc tree.
 * 10. Write a range larger than a nodes current pivot
 */

 mt_set_non_kernel(50);
 for (i = 0; i <= 500; i++) {
  val = i*5;
  val2 = (i+1)*5;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
 }
 check_store_range(mt, 2400, 2400, xa_mk_value(2400), 0);
 check_store_range(mt, 2411, 2411, xa_mk_value(2411), 0);
 check_store_range(mt, 2412, 2412, xa_mk_value(2412), 0);
 check_store_range(mt, 2396, 2400, xa_mk_value(4052020), 0);
 check_store_range(mt, 2402, 2402, xa_mk_value(2402), 0);
 mtree_destroy(mt);
 mt_set_non_kernel(0);

 mt_set_non_kernel(50);
 for (i = 0; i <= 500; i++) {
  val = i*5;
  val2 = (i+1)*5;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
 }
 check_store_range(mt, 2422, 2422, xa_mk_value(2422), 0);
 check_store_range(mt, 2424, 2424, xa_mk_value(2424), 0);
 check_store_range(mt, 2425, 2425, xa_mk_value(2), 0);
 check_store_range(mt, 2460, 2470, NULL, 0);
 check_store_range(mt, 2435, 2460, xa_mk_value(2435), 0);
 check_store_range(mt, 2461, 2470, xa_mk_value(2461), 0);
 mt_set_non_kernel(0);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);

 /* Check in-place modifications */
 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 /* Append to the start of last range */
 mt_set_non_kernel(50);
 for (i = 0; i <= 500; i++) {
  val = i * 5 + 1;
  val2 = val + 4;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
 }

 /* Append to the last range without touching any boundaries */
 for (i = 0; i < 10; i++) {
  val = val2 + 5;
  val2 = val + 4;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
 }

 /* Append to the end of last range */
 val = val2;
 for (i = 0; i < 10; i++) {
  val += 5;
  MT_BUG_ON(mt, mtree_test_store_range(mt, val, ULONG_MAX,
           xa_mk_value(val)) != 0);
 }

 /* Overwriting the range and over a part of the next range */
 for (i = 10; i < 30; i += 2) {
  val = i * 5 + 1;
  val2 = val + 5;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
 }

 /* Overwriting a part of the range and over the next range */
 for (i = 50; i < 70; i += 2) {
  val2 = i * 5;
  val = val2 - 5;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
 }

 /*
 * Expand the range, only partially overwriting the previous and
 * next ranges
 */
 for (i = 100; i < 130; i += 3) {
  val = i * 5 - 5;
  val2 = i * 5 + 1;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
 }

 /*
 * Expand the range, only partially overwriting the previous and
 * next ranges, in RCU mode
 */
 mt_set_in_rcu(mt);
 for (i = 150; i < 180; i += 3) {
  val = i * 5 - 5;
  val2 = i * 5 + 1;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
 }

 MT_BUG_ON(mt, !mt_height(mt));
 mt_validate(mt);
 mt_set_non_kernel(0);
 mtree_destroy(mt);

 /* Test rebalance gaps */
 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 mt_set_non_kernel(50);
 for (i = 0; i <= 50; i++) {
  val = i*10;
  val2 = (i+1)*10;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
 }
 check_store_range(mt, 161, 161, xa_mk_value(161), 0);
 check_store_range(mt, 162, 162, xa_mk_value(162), 0);
 check_store_range(mt, 163, 163, xa_mk_value(163), 0);
 check_store_range(mt, 240, 249, NULL, 0);
 mtree_erase(mt, 200);
 mtree_erase(mt, 210);
 mtree_erase(mt, 220);
 mtree_erase(mt, 230);
 mt_set_non_kernel(0);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);

 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 for (i = 0; i <= 500; i++) {
  val = i*10;
  val2 = (i+1)*10;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
 }
 check_store_range(mt, 4600, 4959, xa_mk_value(1), 0);
 mt_validate(mt);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);

 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 for (i = 0; i <= 500; i++) {
  val = i*10;
  val2 = (i+1)*10;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
 }
 check_store_range(mt, 4811, 4811, xa_mk_value(4811), 0);
 check_store_range(mt, 4812, 4812, xa_mk_value(4812), 0);
 check_store_range(mt, 4861, 4861, xa_mk_value(4861), 0);
 check_store_range(mt, 4862, 4862, xa_mk_value(4862), 0);
 check_store_range(mt, 4842, 4849, NULL, 0);
 mt_validate(mt);
 MT_BUG_ON(mt, !mt_height(mt));
 mtree_destroy(mt);

 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 for (i = 0; i <= 1300; i++) {
  val = i*10;
  val2 = (i+1)*10;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
  MT_BUG_ON(mt, mt_height(mt) >= 4);
 }
 /*  Cause a 3 child split all the way up the tree. */
 for (i = 5; i < 215; i += 10)
  check_store_range(mt, 11450 + i, 11450 + i + 1, NULL, 0);
 for (i = 5; i < 65; i += 10)
  check_store_range(mt, 11770 + i, 11770 + i + 1, NULL, 0);

 MT_BUG_ON(mt, mt_height(mt) >= 4);
 for (i = 5; i < 45; i += 10)
  check_store_range(mt, 11700 + i, 11700 + i + 1, NULL, 0);
 if (!MAPLE_32BIT)
  MT_BUG_ON(mt, mt_height(mt) < 4);
 mtree_destroy(mt);


 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 for (i = 0; i <= 1200; i++) {
  val = i*10;
  val2 = (i+1)*10;
  check_store_range(mt, val, val2, xa_mk_value(val), 0);
  MT_BUG_ON(mt, mt_height(mt) >= 4);
 }
 /* Fill parents and leaves before split. */
 for (i = 5; i < 455; i += 10)
  check_store_range(mt, 7800 + i, 7800 + i + 1, NULL, 0);

 for (i = 1; i < 16; i++)
  check_store_range(mt, 8185 + i, 8185 + i + 1,
      xa_mk_value(8185+i), 0);
 MT_BUG_ON(mt, mt_height(mt) >= 4);
 /* triple split across multiple levels. */
 check_store_range(mt, 8184, 8184, xa_mk_value(8184), 0);
 if (!MAPLE_32BIT)
  MT_BUG_ON(mt, mt_height(mt) != 4);
}

static noinline void __init check_next_entry(struct maple_tree *mt)
{
 void *entry = NULL;
 unsigned long limit = 30, i = 0;
 MA_STATE(mas, mt, i, i);

 MT_BUG_ON(mt, !mtree_empty(mt));

 check_seq(mt, limit, false);
 rcu_read_lock();

 /* Check the first one and get ma_state in the correct state. */
 MT_BUG_ON(mt, mas_walk(&mas) != xa_mk_value(i++));
 for ( ; i <= limit + 1; i++) {
  entry = mas_next(&mas, limit);
  if (i > limit)
   MT_BUG_ON(mt, entry != NULL);
  else
   MT_BUG_ON(mt, xa_mk_value(i) != entry);
 }
 rcu_read_unlock();
 mtree_destroy(mt);
}

static noinline void __init check_prev_entry(struct maple_tree *mt)
{
 unsigned long index = 16;
 void *value;
 int i;

 MA_STATE(mas, mt, index, index);

 MT_BUG_ON(mt, !mtree_empty(mt));
 check_seq(mt, 30, false);

 rcu_read_lock();
 value = mas_find(&mas, ULONG_MAX);
 MT_BUG_ON(mt, value != xa_mk_value(index));
 value = mas_prev(&mas, 0);
 MT_BUG_ON(mt, value != xa_mk_value(index - 1));
 rcu_read_unlock();
 mtree_destroy(mt);

 /* Check limits on prev */
 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 mas_lock(&mas);
 for (i = 0; i <= index; i++) {
  mas_set_range(&mas, i*10, i*10+5);
  mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL);
 }

 mas_set(&mas, 20);
 value = mas_walk(&mas);
 MT_BUG_ON(mt, value != xa_mk_value(2));

 value = mas_prev(&mas, 19);
 MT_BUG_ON(mt, value != NULL);

 mas_set(&mas, 80);
 value = mas_walk(&mas);
 MT_BUG_ON(mt, value != xa_mk_value(8));

 value = mas_prev(&mas, 76);
 MT_BUG_ON(mt, value != NULL);

 mas_unlock(&mas);
}

static noinline void __init check_store_null(struct maple_tree *mt)
{
 MA_STATE(mas, mt, 0, ULONG_MAX);

 /*
 * Store NULL at range [0, ULONG_MAX] to an empty tree should result
 * in an empty tree
 */
 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 mas_lock(&mas);
 mas_store_gfp(&mas, NULL, GFP_KERNEL);
 MT_BUG_ON(mt, !mtree_empty(mt));
 mas_unlock(&mas);
 mtree_destroy(mt);

 /*
 * Store NULL at any range to an empty tree should result in an empty
 * tree
 */
 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 mas_lock(&mas);
 mas_set_range(&mas, 3, 10);
 mas_store_gfp(&mas, NULL, GFP_KERNEL);
 MT_BUG_ON(mt, !mtree_empty(mt));
 mas_unlock(&mas);
 mtree_destroy(mt);

 /*
 * Store NULL at range [0, ULONG_MAX] to a single entry tree should
 * result in an empty tree
 */
 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 mas_lock(&mas);
 mas_set(&mas, 0);
 mas_store_gfp(&mas, &mas, GFP_KERNEL);
 mas_set_range(&mas, 0, ULONG_MAX);
 mas_store_gfp(&mas, NULL, GFP_KERNEL);
 MT_BUG_ON(mt, !mtree_empty(mt));
 mas_unlock(&mas);
 mtree_destroy(mt);

 /*
 * Store NULL at range [0, n] to a single entry tree should
 * result in an empty tree
 */
 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 mas_lock(&mas);
 mas_set(&mas, 0);
 mas_store_gfp(&mas, &mas, GFP_KERNEL);
 mas_set_range(&mas, 0, 5);
 mas_store_gfp(&mas, NULL, GFP_KERNEL);
 MT_BUG_ON(mt, !mtree_empty(mt));
 mas_unlock(&mas);
 mtree_destroy(mt);

 /*
 * Store NULL at range [m, n] where m > 0 to a single entry tree
 * should still be a single entry tree
 */
 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 mas_lock(&mas);
 mas_set(&mas, 0);
 mas_store_gfp(&mas, &mas, GFP_KERNEL);
 mas_set_range(&mas, 2, 5);
 mas_store_gfp(&mas, NULL, GFP_KERNEL);
 MT_BUG_ON(mt, mtree_empty(mt));
// MT_BUG_ON(mt, xa_is_node(mas_root(&mas)));
 mas_unlock(&mas);
 mtree_destroy(mt);

 /*
 * Store NULL at range [0, ULONG_MAX] to a tree with node should
 * result in an empty tree
 */
 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 mas_lock(&mas);
 mas_set_range(&mas, 1, 3);
 mas_store_gfp(&mas, &mas, GFP_KERNEL);
// MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
 mas_set_range(&mas, 0, ULONG_MAX);
 mas_store_gfp(&mas, NULL, GFP_KERNEL);
 MT_BUG_ON(mt, !mtree_empty(mt));
 mas_unlock(&mas);
 mtree_destroy(mt);
}

static noinline void __init check_root_expand(struct maple_tree *mt)
{
 MA_STATE(mas, mt, 0, 0);
 void *ptr;


 mas_lock(&mas);
 mas_set(&mas, 3);
 ptr = mas_walk(&mas);
 MT_BUG_ON(mt, mas.index != 0);
 MT_BUG_ON(mt, ptr != NULL);
 MT_BUG_ON(mt, mas.index != 0);
 MT_BUG_ON(mt, mas.last != ULONG_MAX);

 ptr = &check_prev_entry;
 mas_set(&mas, 1);
 mas_store_gfp(&mas, ptr, GFP_KERNEL);

 mas_set(&mas, 0);
 ptr = mas_walk(&mas);
 MT_BUG_ON(mt, ptr != NULL);

 mas_set(&mas, 1);
 ptr = mas_walk(&mas);
 MT_BUG_ON(mt, ptr != &check_prev_entry);

 mas_set(&mas, 2);
 ptr = mas_walk(&mas);
 MT_BUG_ON(mt, ptr != NULL);
 mas_unlock(&mas);
 mtree_destroy(mt);


 mt_init_flags(mt, 0);
 mas_lock(&mas);

 mas_set(&mas, 0);
 ptr = &check_prev_entry;
 mas_store_gfp(&mas, ptr, GFP_KERNEL);

 mas_set(&mas, 5);
 ptr = mas_walk(&mas);
 MT_BUG_ON(mt, ptr != NULL);
 MT_BUG_ON(mt, mas.index != 1);
 MT_BUG_ON(mt, mas.last != ULONG_MAX);

 mas_set_range(&mas, 0, 100);
 ptr = mas_walk(&mas);
 MT_BUG_ON(mt, ptr != &check_prev_entry);
 MT_BUG_ON(mt, mas.last != 0);
 mas_unlock(&mas);
 mtree_destroy(mt);

 mt_init_flags(mt, 0);
 mas_lock(&mas);

 mas_set(&mas, 0);
 ptr = (void *)((unsigned long) check_prev_entry | 1UL);
 mas_store_gfp(&mas, ptr, GFP_KERNEL);
 ptr = mas_next(&mas, ULONG_MAX);
 MT_BUG_ON(mt, ptr != NULL);
 MT_BUG_ON(mt, (mas.index != 1) && (mas.last != ULONG_MAX));

 mas_set(&mas, 1);
 ptr = mas_prev(&mas, 0);
 MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0));
 MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 1UL));

 mas_unlock(&mas);

 mtree_destroy(mt);

 mt_init_flags(mt, 0);
 mas_lock(&mas);
 mas_set(&mas, 0);
 ptr = (void *)((unsigned long) check_prev_entry | 2UL);
 mas_store_gfp(&mas, ptr, GFP_KERNEL);
 ptr = mas_next(&mas, ULONG_MAX);
 MT_BUG_ON(mt, ptr != NULL);
 MT_BUG_ON(mt, (mas.index != ULONG_MAX) && (mas.last != ULONG_MAX));

 mas_set(&mas, 1);
 ptr = mas_prev(&mas, 0);
 MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0));
 MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 2UL));


 mas_unlock(&mas);
}

static noinline void __init check_deficient_node(struct maple_tree *mt)
{
 MA_STATE(mas, mt, 0, 0);
 int count;

 mas_lock(&mas);
 for (count = 0; count < 10; count++) {
  mas_set(&mas, count);
  mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
 }

 for (count = 20; count < 39; count++) {
  mas_set(&mas, count);
  mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
 }

 for (count = 10; count < 12; count++) {
  mas_set(&mas, count);
  mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
 }
 mas_unlock(&mas);
 mt_validate(mt);
}

static noinline void __init check_gap_combining(struct maple_tree *mt)
{
 struct maple_enode *mn1, *mn2;
 void *entry;
 unsigned long singletons = 100;
 static const unsigned long *seq100;
 static const unsigned long seq100_64[] = {
  /* 0-5 */
  74, 75, 76,
  50, 100, 2,

  /* 6-12 */
  44, 45, 46, 43,
  20, 50, 3,

  /* 13-20*/
  80, 81, 82,
  76, 2, 79, 85, 4,
 };

 static const unsigned long seq100_32[] = {
  /* 0-5 */
  61, 62, 63,
  50, 100, 2,

  /* 6-12 */
  31, 32, 33, 30,
  20, 50, 3,

  /* 13-20*/
  80, 81, 82,
  76, 2, 79, 85, 4,
 };

 static const unsigned long seq2000[] = {
  1152, 1151,
  1100, 1200, 2,
 };
 static const unsigned long seq400[] = {
  286, 318,
  256, 260, 266, 270, 275, 280, 290, 398,
  286, 310,
 };

 unsigned long index;

 MA_STATE(mas, mt, 0, 0);

 if (MAPLE_32BIT)
  seq100 = seq100_32;
 else
  seq100 = seq100_64;

 index = seq100[0];
 mas_set(&mas, index);
 MT_BUG_ON(mt, !mtree_empty(mt));
 check_seq(mt, singletons, false); /* create 100 singletons. */

 mt_set_non_kernel(1);
 mtree_test_erase(mt, seq100[2]);
 check_load(mt, seq100[2], NULL);
 mtree_test_erase(mt, seq100[1]);
 check_load(mt, seq100[1], NULL);

 rcu_read_lock();
 entry = mas_find(&mas, ULONG_MAX);
 MT_BUG_ON(mt, entry != xa_mk_value(index));
 mn1 = mas.node;
 mas_next(&mas, ULONG_MAX);
 entry = mas_next(&mas, ULONG_MAX);
 MT_BUG_ON(mt, entry != xa_mk_value(index + 4));
 mn2 = mas.node;
 MT_BUG_ON(mt, mn1 == mn2); /* test the test. */

 /*
 * At this point, there is a gap of 2 at index + 1 between seq100[3] and
 * seq100[4]. Search for the gap.
 */
 mt_set_non_kernel(1);
 mas_reset(&mas);
 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[3], seq100[4],
          seq100[5]));
 MT_BUG_ON(mt, mas.index != index + 1);
 rcu_read_unlock();

 mtree_test_erase(mt, seq100[6]);
 check_load(mt, seq100[6], NULL);
 mtree_test_erase(mt, seq100[7]);
 check_load(mt, seq100[7], NULL);
 mtree_test_erase(mt, seq100[8]);
 index = seq100[9];

 rcu_read_lock();
 mas.index = index;
 mas.last = index;
 mas_reset(&mas);
 entry = mas_find(&mas, ULONG_MAX);
 MT_BUG_ON(mt, entry != xa_mk_value(index));
 mn1 = mas.node;
 entry = mas_next(&mas, ULONG_MAX);
 MT_BUG_ON(mt, entry != xa_mk_value(index + 4));
 mas_next(&mas, ULONG_MAX); /* go to the next entry. */
 mn2 = mas.node;
 MT_BUG_ON(mt, mn1 == mn2); /* test the next entry is in the next node. */

 /*
 * At this point, there is a gap of 3 at seq100[6].  Find it by
 * searching 20 - 50 for size 3.
 */
 mas_reset(&mas);
 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[10], seq100[11],
          seq100[12]));
 MT_BUG_ON(mt, mas.index != seq100[6]);
 rcu_read_unlock();

 mt_set_non_kernel(1);
 mtree_store(mt, seq100[13], NULL, GFP_KERNEL);
 check_load(mt, seq100[13], NULL);
 check_load(mt, seq100[14], xa_mk_value(seq100[14]));
 mtree_store(mt, seq100[14], NULL, GFP_KERNEL);
 check_load(mt, seq100[13], NULL);
 check_load(mt, seq100[14], NULL);

 mas_reset(&mas);
 rcu_read_lock();
 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[15],
          seq100[17]));
 MT_BUG_ON(mt, mas.index != seq100[13]);
 mt_validate(mt);
 rcu_read_unlock();

 /*
 * *DEPRECATED: no retries anymore* Test retry entry in the start of a
 * gap.
 */
 mt_set_non_kernel(2);
 mtree_test_store_range(mt, seq100[18], seq100[14], NULL);
 mtree_test_erase(mt, seq100[15]);
 mas_reset(&mas);
 rcu_read_lock();
 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[19],
          seq100[20]));
 rcu_read_unlock();
 MT_BUG_ON(mt, mas.index != seq100[18]);
 mt_validate(mt);
 mtree_destroy(mt);

 /* seq 2000 tests are for multi-level tree gaps */
 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 check_seq(mt, 2000, false);
 mt_set_non_kernel(1);
 mtree_test_erase(mt, seq2000[0]);
 mtree_test_erase(mt, seq2000[1]);

 mt_set_non_kernel(2);
 mas_reset(&mas);
 rcu_read_lock();
 MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq2000[2], seq2000[3],
          seq2000[4]));
 MT_BUG_ON(mt, mas.index != seq2000[1]);
 rcu_read_unlock();
 mt_validate(mt);
 mtree_destroy(mt);

 /* seq 400 tests rebalancing over two levels. */
 mt_set_non_kernel(99);
 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 check_seq(mt, 400, false);
 mtree_test_store_range(mt, seq400[0], seq400[1], NULL);
 mt_set_non_kernel(0);
 mtree_destroy(mt);

 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 check_seq(mt, 400, false);
 mt_set_non_kernel(50);
 mtree_test_store_range(mt, seq400[2], seq400[9],
          xa_mk_value(seq400[2]));
 mtree_test_store_range(mt, seq400[3], seq400[9],
          xa_mk_value(seq400[3]));
 mtree_test_store_range(mt, seq400[4], seq400[9],
          xa_mk_value(seq400[4]));
 mtree_test_store_range(mt, seq400[5], seq400[9],
          xa_mk_value(seq400[5]));
 mtree_test_store_range(mt, seq400[0], seq400[9],
          xa_mk_value(seq400[0]));
 mtree_test_store_range(mt, seq400[6], seq400[9],
          xa_mk_value(seq400[6]));
 mtree_test_store_range(mt, seq400[7], seq400[9],
          xa_mk_value(seq400[7]));
 mtree_test_store_range(mt, seq400[8], seq400[9],
          xa_mk_value(seq400[8]));
 mtree_test_store_range(mt, seq400[10], seq400[11],
          xa_mk_value(seq400[10]));
 mt_validate(mt);
 mt_set_non_kernel(0);
 mtree_destroy(mt);
}
static noinline void __init check_node_overwrite(struct maple_tree *mt)
{
 int i, max = 4000;

 for (i = 0; i < max; i++)
  mtree_test_store_range(mt, i*100, i*100 + 50, xa_mk_value(i*100));

 mtree_test_store_range(mt, 319951, 367950, NULL);
 /*mt_dump(mt, mt_dump_dec); */
 mt_validate(mt);
}

#if defined(BENCH_SLOT_STORE)
static noinline void __init bench_slot_store(struct maple_tree *mt)
{
 int i, brk = 105, max = 1040, brk_start = 100, count = 20000000;

 for (i = 0; i < max; i += 10)
  mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);

 for (i = 0; i < count; i++) {
  mtree_store_range(mt, brk, brk, NULL, GFP_KERNEL);
  mtree_store_range(mt, brk_start, brk, xa_mk_value(brk),
      GFP_KERNEL);
 }
}
#endif

#if defined(BENCH_NODE_STORE)
static noinline void __init bench_node_store(struct maple_tree *mt)
{
 int i, overwrite = 76, max = 240, count = 20000000;

 for (i = 0; i < max; i += 10)
  mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);

 for (i = 0; i < count; i++) {
  mtree_store_range(mt, overwrite,  overwrite + 15,
      xa_mk_value(overwrite), GFP_KERNEL);

  overwrite += 5;
  if (overwrite >= 135)
   overwrite = 76;
 }
}
#endif

#if defined(BENCH_AWALK)
static noinline void __init bench_awalk(struct maple_tree *mt)
{
 int i, max = 2500, count = 50000000;
 MA_STATE(mas, mt, 1470, 1470);

 for (i = 0; i < max; i += 10)
  mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);

 mtree_store_range(mt, 1470, 1475, NULL, GFP_KERNEL);

 for (i = 0; i < count; i++) {
  mas_empty_area_rev(&mas, 0, 2000, 10);
  mas_reset(&mas);
 }
}
#endif
#if defined(BENCH_WALK)
static noinline void __init bench_walk(struct maple_tree *mt)
{
 int i, max = 2500, count = 550000000;
 MA_STATE(mas, mt, 1470, 1470);

 for (i = 0; i < max; i += 10)
  mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);

 for (i = 0; i < count; i++) {
  mas_walk(&mas);
  mas_reset(&mas);
 }

}
#endif

#if defined(BENCH_LOAD)
static noinline void __init bench_load(struct maple_tree *mt)
{
 int i, max = 2500, count = 550000000;

 for (i = 0; i < max; i += 10)
  mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);

 for (i = 0; i < count; i++)
  mtree_load(mt, 1470);
}
#endif

#if defined(BENCH_MT_FOR_EACH)
static noinline void __init bench_mt_for_each(struct maple_tree *mt)
{
 int i, count = 1000000;
 unsigned long max = 2500, index = 0;
 void *entry;

 for (i = 0; i < max; i += 5)
  mtree_store_range(mt, i, i + 4, xa_mk_value(i), GFP_KERNEL);

 for (i = 0; i < count; i++) {
  unsigned long j = 0;

  mt_for_each(mt, entry, index, max) {
   MT_BUG_ON(mt, entry != xa_mk_value(j));
   j += 5;
  }

  index = 0;
 }

}
#endif

#if defined(BENCH_MAS_FOR_EACH)
static noinline void __init bench_mas_for_each(struct maple_tree *mt)
{
 int i, count = 1000000;
 unsigned long max = 2500;
 void *entry;
 MA_STATE(mas, mt, 0, 0);

 for (i = 0; i < max; i += 5) {
  int gap = 4;

  if (i % 30 == 0)
   gap = 3;
  mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
 }

 rcu_read_lock();
 for (i = 0; i < count; i++) {
  unsigned long j = 0;

  mas_for_each(&mas, entry, max) {
   MT_BUG_ON(mt, entry != xa_mk_value(j));
   j += 5;
  }
  mas_set(&mas, 0);
 }
 rcu_read_unlock();

}
#endif
#if defined(BENCH_MAS_PREV)
static noinline void __init bench_mas_prev(struct maple_tree *mt)
{
 int i, count = 1000000;
 unsigned long max = 2500;
 void *entry;
 MA_STATE(mas, mt, 0, 0);

 for (i = 0; i < max; i += 5) {
  int gap = 4;

  if (i % 30 == 0)
   gap = 3;
  mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
 }

 rcu_read_lock();
 for (i = 0; i < count; i++) {
  unsigned long j = 2495;

  mas_set(&mas, ULONG_MAX);
  while ((entry = mas_prev(&mas, 0)) != NULL) {
   MT_BUG_ON(mt, entry != xa_mk_value(j));
   j -= 5;
  }
 }
 rcu_read_unlock();

}
#endif
/* check_forking - simulate the kernel forking sequence with the tree. */
static noinline void __init check_forking(void)
{
 struct maple_tree mt, newmt;
 int i, nr_entries = 134, ret;
 void *val;
 MA_STATE(mas, &mt, 0, 0);
 MA_STATE(newmas, &newmt, 0, 0);
 struct rw_semaphore mt_lock, newmt_lock;

 init_rwsem(&mt_lock);
 init_rwsem(&newmt_lock);

 mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
 mt_set_external_lock(&mt, &mt_lock);

 mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
 mt_set_external_lock(&newmt, &newmt_lock);

 down_write(&mt_lock);
 for (i = 0; i <= nr_entries; i++) {
  mas_set_range(&mas, i*10, i*10 + 5);
  mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL);
 }

 down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING);
 ret = __mt_dup(&mt, &newmt, GFP_KERNEL);
 if (ret) {
  pr_err("OOM!");
  BUG_ON(1);
 }

 mas_set(&newmas, 0);
 mas_for_each(&newmas, val, ULONG_MAX)
  mas_store(&newmas, val);

 mas_destroy(&newmas);
 mas_destroy(&mas);
 mt_validate(&newmt);
 __mt_destroy(&newmt);
 __mt_destroy(&mt);
 up_write(&newmt_lock);
 up_write(&mt_lock);
}

static noinline void __init check_iteration(struct maple_tree *mt)
{
 int i, nr_entries = 125;
 void *val;
 MA_STATE(mas, mt, 0, 0);

 for (i = 0; i <= nr_entries; i++)
  mtree_store_range(mt, i * 10, i * 10 + 9,
      xa_mk_value(i), GFP_KERNEL);

 mt_set_non_kernel(99999);

 i = 0;
 mas_lock(&mas);
 mas_for_each(&mas, val, 925) {
  MT_BUG_ON(mt, mas.index != i * 10);
  MT_BUG_ON(mt, mas.last != i * 10 + 9);
  /* Overwrite end of entry 92 */
  if (i == 92) {
   mas.index = 925;
   mas.last = 929;
   mas_store(&mas, val);
  }
  i++;
 }
 /* Ensure mas_find() gets the next value */
 val = mas_find(&mas, ULONG_MAX);
 MT_BUG_ON(mt, val != xa_mk_value(i));

 mas_set(&mas, 0);
 i = 0;
 mas_for_each(&mas, val, 785) {
  MT_BUG_ON(mt, mas.index != i * 10);
  MT_BUG_ON(mt, mas.last != i * 10 + 9);
  /* Overwrite start of entry 78 */
  if (i == 78) {
   mas.index = 780;
   mas.last = 785;
   mas_store(&mas, val);
  } else {
   i++;
  }
 }
 val = mas_find(&mas, ULONG_MAX);
 MT_BUG_ON(mt, val != xa_mk_value(i));

 mas_set(&mas, 0);
 i = 0;
 mas_for_each(&mas, val, 765) {
  MT_BUG_ON(mt, mas.index != i * 10);
  MT_BUG_ON(mt, mas.last != i * 10 + 9);
  /* Overwrite end of entry 76 and advance to the end */
  if (i == 76) {
   mas.index = 760;
   mas.last = 765;
   mas_store(&mas, val);
  }
  i++;
 }
 /* Make sure the next find returns the one after 765, 766-769 */
 val = mas_find(&mas, ULONG_MAX);
 MT_BUG_ON(mt, val != xa_mk_value(76));
 mas_unlock(&mas);
 mas_destroy(&mas);
 mt_set_non_kernel(0);
}

static noinline void __init check_mas_store_gfp(struct maple_tree *mt)
{

 struct maple_tree newmt;
 int i, nr_entries = 135;
 void *val;
 MA_STATE(mas, mt, 0, 0);
 MA_STATE(newmas, mt, 0, 0);

 for (i = 0; i <= nr_entries; i++)
  mtree_store_range(mt, i*10, i*10 + 5,
      xa_mk_value(i), GFP_KERNEL);

 mt_set_non_kernel(99999);
 mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
 newmas.tree = &newmt;
 rcu_read_lock();
 mas_lock(&newmas);
 mas_reset(&newmas);
 mas_set(&mas, 0);
 mas_for_each(&mas, val, ULONG_MAX) {
  newmas.index = mas.index;
  newmas.last = mas.last;
  mas_store_gfp(&newmas, val, GFP_KERNEL);
 }
 mas_unlock(&newmas);
 rcu_read_unlock();
 mt_validate(&newmt);
 mt_set_non_kernel(0);
 mtree_destroy(&newmt);
}

#if defined(BENCH_FORK)
static noinline void __init bench_forking(void)
{
 struct maple_tree mt, newmt;
 int i, nr_entries = 134, nr_fork = 80000, ret;
 void *val;
 MA_STATE(mas, &mt, 0, 0);
 MA_STATE(newmas, &newmt, 0, 0);
 struct rw_semaphore mt_lock, newmt_lock;

 init_rwsem(&mt_lock);
 init_rwsem(&newmt_lock);

 mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
 mt_set_external_lock(&mt, &mt_lock);

 down_write(&mt_lock);
 for (i = 0; i <= nr_entries; i++) {
  mas_set_range(&mas, i*10, i*10 + 5);
  mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL);
 }

 for (i = 0; i < nr_fork; i++) {
  mt_init_flags(&newmt,
         MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
  mt_set_external_lock(&newmt, &newmt_lock);

  down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING);
  ret = __mt_dup(&mt, &newmt, GFP_KERNEL);
  if (ret) {
   pr_err("OOM!");
   BUG_ON(1);
  }

  mas_set(&newmas, 0);
  mas_for_each(&newmas, val, ULONG_MAX)
   mas_store(&newmas, val);

  mas_destroy(&newmas);
  mt_validate(&newmt);
  __mt_destroy(&newmt);
  up_write(&newmt_lock);
 }
 mas_destroy(&mas);
 __mt_destroy(&mt);
 up_write(&mt_lock);
}
#endif

static noinline void __init next_prev_test(struct maple_tree *mt)
{
 int i, nr_entries;
 void *val;
 MA_STATE(mas, mt, 0, 0);
 struct maple_enode *mn;
 static const unsigned long *level2;
 static const unsigned long level2_64[] = { 707, 1000, 710, 715, 720,
         725};
 static const unsigned long level2_32[] = { 1747, 2000, 1750, 1755,
         1760, 1765};
 unsigned long last_index;

 if (MAPLE_32BIT) {
  nr_entries = 500;
  level2 = level2_32;
  last_index = 0x138e;
 } else {
  nr_entries = 200;
  level2 = level2_64;
  last_index = 0x7d6;
 }

 for (i = 0; i <= nr_entries; i++)
  mtree_store_range(mt, i*10, i*10 + 5,
      xa_mk_value(i), GFP_KERNEL);

 mas_lock(&mas);
 for (i = 0; i <= nr_entries / 2; i++) {
  mas_next(&mas, 1000);
  if (mas_is_none(&mas))
   break;

 }
 mas_reset(&mas);
 mas_set(&mas, 0);
 i = 0;
 mas_for_each(&mas, val, 1000) {
  i++;
 }

 mas_reset(&mas);
 mas_set(&mas, 0);
 i = 0;
 mas_for_each(&mas, val, 1000) {
  mas_pause(&mas);
  i++;
 }

 /*
 * 680 - 685 = 0x61a00001930c
 * 686 - 689 = NULL;
 * 690 - 695 = 0x61a00001930c
 * Check simple next/prev
 */
 mas_set(&mas, 686);
 val = mas_walk(&mas);
 MT_BUG_ON(mt, val != NULL);

 val = mas_next(&mas, 1000);
 MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
 MT_BUG_ON(mt, mas.index != 690);
 MT_BUG_ON(mt, mas.last != 695);

 val = mas_prev(&mas, 0);
 MT_BUG_ON(mt, val != xa_mk_value(680 / 10));
 MT_BUG_ON(mt, mas.index != 680);
 MT_BUG_ON(mt, mas.last != 685);

 val = mas_next(&mas, 1000);
 MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
 MT_BUG_ON(mt, mas.index != 690);
 MT_BUG_ON(mt, mas.last != 695);

 val = mas_next(&mas, 1000);
 MT_BUG_ON(mt, val != xa_mk_value(700 / 10));
 MT_BUG_ON(mt, mas.index != 700);
 MT_BUG_ON(mt, mas.last != 705);

 /* Check across node boundaries of the tree */
 mas_set(&mas, 70);
 val = mas_walk(&mas);
 MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
 MT_BUG_ON(mt, mas.index != 70);
 MT_BUG_ON(mt, mas.last != 75);

 val = mas_next(&mas, 1000);
 MT_BUG_ON(mt, val != xa_mk_value(80 / 10));
 MT_BUG_ON(mt, mas.index != 80);
 MT_BUG_ON(mt, mas.last != 85);

 val = mas_prev(&mas, 70);
 MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
 MT_BUG_ON(mt, mas.index != 70);
 MT_BUG_ON(mt, mas.last != 75);

 /* Check across two levels of the tree */
 mas_reset(&mas);
 mas_set(&mas, level2[0]);
 val = mas_walk(&mas);
 MT_BUG_ON(mt, val != NULL);
 val = mas_next(&mas, level2[1]);
 MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
 MT_BUG_ON(mt, mas.index != level2[2]);
 MT_BUG_ON(mt, mas.last != level2[3]);
 mn = mas.node;

 val = mas_next(&mas, level2[1]);
 MT_BUG_ON(mt, val != xa_mk_value(level2[4] / 10));
 MT_BUG_ON(mt, mas.index != level2[4]);
 MT_BUG_ON(mt, mas.last != level2[5]);
 MT_BUG_ON(mt, mn == mas.node);

 val = mas_prev(&mas, 0);
 MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
 MT_BUG_ON(mt, mas.index != level2[2]);
 MT_BUG_ON(mt, mas.last != level2[3]);

 /* Check running off the end and back on */
 mas_set(&mas, nr_entries * 10);
 val = mas_walk(&mas);
 MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
 MT_BUG_ON(mt, mas.index != (nr_entries * 10));
 MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));

 val = mas_next(&mas, ULONG_MAX);
 MT_BUG_ON(mt, val != NULL);
 MT_BUG_ON(mt, mas.index != last_index);
 MT_BUG_ON(mt, mas.last != ULONG_MAX);

 val = mas_prev(&mas, 0);
 MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
 MT_BUG_ON(mt, mas.index != (nr_entries * 10));
 MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));

 /* Check running off the start and back on */
 mas_reset(&mas);
 mas_set(&mas, 10);
 val = mas_walk(&mas);
 MT_BUG_ON(mt, val != xa_mk_value(1));
 MT_BUG_ON(mt, mas.index != 10);
 MT_BUG_ON(mt, mas.last != 15);

 val = mas_prev(&mas, 0);
 MT_BUG_ON(mt, val != xa_mk_value(0));
 MT_BUG_ON(mt, mas.index != 0);
 MT_BUG_ON(mt, mas.last != 5);

 val = mas_prev(&mas, 0);
 MT_BUG_ON(mt, val != NULL);
 MT_BUG_ON(mt, mas.index != 0);
 MT_BUG_ON(mt, mas.last != 5);
 MT_BUG_ON(mt, !mas_is_underflow(&mas));

 mas.index = 0;
 mas.last = 5;
 mas_store(&mas, NULL);
 mas_reset(&mas);
 mas_set(&mas, 10);
 mas_walk(&mas);

 val = mas_prev(&mas, 0);
 MT_BUG_ON(mt, val != NULL);
 MT_BUG_ON(mt, mas.index != 0);
 MT_BUG_ON(mt, mas.last != 9);
 mas_unlock(&mas);

 mtree_destroy(mt);

 mt_init(mt);
 mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL);
 mtree_store_range(mt, 5, 5, xa_mk_value(5), GFP_KERNEL);
 rcu_read_lock();
 mas_set(&mas, 5);
 val = mas_prev(&mas, 4);
 MT_BUG_ON(mt, val != NULL);
 rcu_read_unlock();
}



/* Test spanning writes that require balancing right sibling or right cousin */
static noinline void __init check_spanning_relatives(struct maple_tree *mt)
{

 unsigned long i, nr_entries = 1000;

 for (i = 0; i <= nr_entries; i++)
  mtree_store_range(mt, i*10, i*10 + 5,
      xa_mk_value(i), GFP_KERNEL);


 mtree_store_range(mt, 9365, 9955, NULL, GFP_KERNEL);
}

static noinline void __init check_fuzzer(struct maple_tree *mt)
{
 /*
 * 1. Causes a spanning rebalance of a single root node.
 * Fixed by setting the correct limit in mast_cp_to_nodes() when the
 * entire right side is consumed.
 */
 mtree_test_insert(mt, 88, (void *)0xb1);
 mtree_test_insert(mt, 84, (void *)0xa9);
 mtree_test_insert(mt, 2,  (void *)0x5);
 mtree_test_insert(mt, 4,  (void *)0x9);
 mtree_test_insert(mt, 14, (void *)0x1d);
 mtree_test_insert(mt, 7,  (void *)0xf);
 mtree_test_insert(mt, 12, (void *)0x19);
 mtree_test_insert(mt, 18, (void *)0x25);
 mtree_test_store_range(mt, 8, 18, (void *)0x11);
 mtree_destroy(mt);


 /*
 * 2. Cause a spanning rebalance of two nodes in root.
 * Fixed by setting mast->r->max correctly.
 */
 mt_init_flags(mt, 0);
 mtree_test_store(mt, 87, (void *)0xaf);
 mtree_test_store(mt, 0, (void *)0x1);
 mtree_test_load(mt, 4);
 mtree_test_insert(mt, 4, (void *)0x9);
 mtree_test_store(mt, 8, (void *)0x11);
 mtree_test_store(mt, 44, (void *)0x59);
 mtree_test_store(mt, 68, (void *)0x89);
 mtree_test_store(mt, 2, (void *)0x5);
 mtree_test_insert(mt, 43, (void *)0x57);
 mtree_test_insert(mt, 24, (void *)0x31);
 mtree_test_insert(mt, 844, (void *)0x699);
 mtree_test_store(mt, 84, (void *)0xa9);
 mtree_test_store(mt, 4, (void *)0x9);
 mtree_test_erase(mt, 4);
 mtree_test_load(mt, 5);
 mtree_test_erase(mt, 0);
 mtree_destroy(mt);

 /*
 * 3. Cause a node overflow on copy
 * Fixed by using the correct check for node size in mas_wr_modify()
 * Also discovered issue with metadata setting.
 */
 mt_init_flags(mt, 0);
 mtree_test_store_range(mt, 0, ULONG_MAX, (void *)0x1);
 mtree_test_store(mt, 4, (void *)0x9);
 mtree_test_erase(mt, 5);
 mtree_test_erase(mt, 0);
 mtree_test_erase(mt, 4);
 mtree_test_store(mt, 5, (void *)0xb);
 mtree_test_erase(mt, 5);
 mtree_test_store(mt, 5, (void *)0xb);
 mtree_test_erase(mt, 5);
 mtree_test_erase(mt, 4);
 mtree_test_store(mt, 4, (void *)0x9);
 mtree_test_store(mt, 444, (void *)0x379);
 mtree_test_store(mt, 0, (void *)0x1);
 mtree_test_load(mt, 0);
 mtree_test_store(mt, 5, (void *)0xb);
 mtree_test_erase(mt, 0);
 mtree_destroy(mt);

 /*
 * 4. spanning store failure due to writing incorrect pivot value at
 * last slot.
 * Fixed by setting mast->r->max correctly in mast_cp_to_nodes()
 *
 */
 mt_init_flags(mt, 0);
 mtree_test_insert(mt, 261, (void *)0x20b);
 mtree_test_store(mt, 516, (void *)0x409);
 mtree_test_store(mt, 6, (void *)0xd);
 mtree_test_insert(mt, 5, (void *)0xb);
 mtree_test_insert(mt, 1256, (void *)0x9d1);
 mtree_test_store(mt, 4, (void *)0x9);
 mtree_test_erase(mt, 1);
 mtree_test_store(mt, 56, (void *)0x71);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_store(mt, 24, (void *)0x31);
 mtree_test_erase(mt, 1);
 mtree_test_insert(mt, 2263, (void *)0x11af);
 mtree_test_insert(mt, 446, (void *)0x37d);
 mtree_test_store_range(mt, 6, 45, (void *)0xd);
 mtree_test_store_range(mt, 3, 446, (void *)0x7);
 mtree_destroy(mt);

 /*
 * 5. mas_wr_extend_null() may overflow slots.
 * Fix by checking against wr_mas->node_end.
 */
 mt_init_flags(mt, 0);
 mtree_test_store(mt, 48, (void *)0x61);
 mtree_test_store(mt, 3, (void *)0x7);
 mtree_test_load(mt, 0);
 mtree_test_store(mt, 88, (void *)0xb1);
 mtree_test_store(mt, 81, (void *)0xa3);
 mtree_test_insert(mt, 0, (void *)0x1);
 mtree_test_insert(mt, 8, (void *)0x11);
 mtree_test_insert(mt, 4, (void *)0x9);
 mtree_test_insert(mt, 2480, (void *)0x1361);
 mtree_test_insert(mt, ULONG_MAX,
     (void *)0xffffffffffffffff);
 mtree_test_erase(mt, ULONG_MAX);
 mtree_destroy(mt);

 /*
 * 6.  When reusing a node with an implied pivot and the node is
 * shrinking, old data would be left in the implied slot
 * Fixed by checking the last pivot for the mas->max and clear
 * accordingly.  This only affected the left-most node as that node is
 * the only one allowed to end in NULL.
 */
 mt_init_flags(mt, 0);
 mtree_test_erase(mt, 3);
 mtree_test_insert(mt, 22, (void *)0x2d);
 mtree_test_insert(mt, 15, (void *)0x1f);
 mtree_test_load(mt, 2);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_insert(mt, 5, (void *)0xb);
 mtree_test_erase(mt, 1);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_insert(mt, 4, (void *)0x9);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_erase(mt, 1);
 mtree_test_insert(mt, 2, (void *)0x5);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_erase(mt, 3);
 mtree_test_insert(mt, 22, (void *)0x2d);
 mtree_test_insert(mt, 15, (void *)0x1f);
 mtree_test_insert(mt, 2, (void *)0x5);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_insert(mt, 8, (void *)0x11);
 mtree_test_load(mt, 2);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_store(mt, 1, (void *)0x3);
 mtree_test_insert(mt, 5, (void *)0xb);
 mtree_test_erase(mt, 1);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_insert(mt, 4, (void *)0x9);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_erase(mt, 1);
 mtree_test_insert(mt, 2, (void *)0x5);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_erase(mt, 3);
 mtree_test_insert(mt, 22, (void *)0x2d);
 mtree_test_insert(mt, 15, (void *)0x1f);
 mtree_test_insert(mt, 2, (void *)0x5);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_insert(mt, 8, (void *)0x11);
 mtree_test_insert(mt, 12, (void *)0x19);
 mtree_test_erase(mt, 1);
 mtree_test_store_range(mt, 4, 62, (void *)0x9);
 mtree_test_erase(mt, 62);
 mtree_test_store_range(mt, 1, 0, (void *)0x3);
 mtree_test_insert(mt, 11, (void *)0x17);
 mtree_test_insert(mt, 3, (void *)0x7);
 mtree_test_insert(mt, 3, (void *)0x7);
 mtree_test_store(mt, 62, (void *)0x7d);
 mtree_test_erase(mt, 62);
 mtree_test_store_range(mt, 1, 15, (void *)0x3);
 mtree_test_erase(mt, 1);
 mtree_test_insert(mt, 22, (void *)0x2d);
 mtree_test_insert(mt, 12, (void *)0x19);
 mtree_test_erase(mt, 1);
 mtree_test_insert(mt, 3, (void *)0x7);
 mtree_test_store(mt, 62, (void *)0x7d);
 mtree_test_erase(mt, 62);
 mtree_test_insert(mt, 122, (void *)0xf5);
 mtree_test_store(mt, 3, (void *)0x7);
 mtree_test_insert(mt, 0, (void *)0x1);
 mtree_test_store_range(mt, 0, 1, (void *)0x1);
 mtree_test_insert(mt, 85, (void *)0xab);
 mtree_test_insert(mt, 72, (void *)0x91);
 mtree_test_insert(mt, 81, (void *)0xa3);
 mtree_test_insert(mt, 726, (void *)0x5ad);
 mtree_test_insert(mt, 0, (void *)0x1);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_store(mt, 51, (void *)0x67);
 mtree_test_insert(mt, 611, (void *)0x4c7);
 mtree_test_insert(mt, 485, (void *)0x3cb);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_erase(mt, 1);
 mtree_test_insert(mt, 0, (void *)0x1);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_insert_range(mt, 26, 1, (void *)0x35);
 mtree_test_load(mt, 1);
 mtree_test_store_range(mt, 1, 22, (void *)0x3);
 mtree_test_insert(mt, 1, (void *)0x3);
 mtree_test_erase(mt, 1);
 mtree_test_load(mt, 53);
--> --------------------

--> maximum size reached

--> --------------------