lib/test_xarray.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * test_xarray.c: Test the XArray API
   4  * Copyright (c) 2017-2018 Microsoft Corporation
   5  * Copyright (c) 2019-2020 Oracle
   6  * Author: Matthew Wilcox <willy@infradead.org>
   7  */
   8
   9 #include <linux/xarray.h>
  10 #include <linux/module.h>
  11
  12 static unsigned int tests_run;
  13 static unsigned int tests_passed;
  14
  15 static const unsigned int order_limit =
  16                 IS_ENABLED(CONFIG_XARRAY_MULTI) ? BITS_PER_LONG : 1;
  17
  18 #ifndef XA_DEBUG
  19 # ifdef __KERNEL__
  20 void xa_dump(const struct xarray *xa) { }
  21 # endif
  22 #undef XA_BUG_ON
  23 #define XA_BUG_ON(xa, x) do {                                   \
  24         tests_run++;                                            \
  25         if (x) {                                                \
  26                 printk("BUG at %s:%d\n", __func__, __LINE__);   \
  27                 xa_dump(xa);                                    \
  28                 dump_stack();                                   \
  29         } else {                                                \
  30                 tests_passed++;                                 \
  31         }                                                       \
  32 } while (0)
  33 #endif
  34
  35 static void *xa_mk_index(unsigned long index)
  36 {
  37         return xa_mk_value(index & LONG_MAX);
  38 }
  39
  40 static void *xa_store_index(struct xarray *xa, unsigned long index, gfp_t gfp)
  41 {
  42         return xa_store(xa, index, xa_mk_index(index), gfp);
  43 }
  44
  45 static void xa_insert_index(struct xarray *xa, unsigned long index)
  46 {
  47         XA_BUG_ON(xa, xa_insert(xa, index, xa_mk_index(index),
  48                                 GFP_KERNEL) != 0);
  49 }
  50
  51 static void xa_alloc_index(struct xarray *xa, unsigned long index, gfp_t gfp)
  52 {
  53         u32 id;
  54
  55         XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(index), xa_limit_32b,
  56                                 gfp) != 0);
  57         XA_BUG_ON(xa, id != index);
  58 }
  59
  60 static void xa_erase_index(struct xarray *xa, unsigned long index)
  61 {
  62         XA_BUG_ON(xa, xa_erase(xa, index) != xa_mk_index(index));
  63         XA_BUG_ON(xa, xa_load(xa, index) != NULL);
  64 }
  65
  66 /*
  67  * If anyone needs this, please move it to xarray.c.  We have no current
  68  * users outside the test suite because all current multislot users want
  69  * to use the advanced API.
  70  */
  71 static void *xa_store_order(struct xarray *xa, unsigned long index,
  72                 unsigned order, void *entry, gfp_t gfp)
  73 {
  74         XA_STATE_ORDER(xas, xa, index, order);
  75         void *curr;
  76
  77         do {
  78                 xas_lock(&xas);
  79                 curr = xas_store(&xas, entry);
  80                 xas_unlock(&xas);
  81         } while (xas_nomem(&xas, gfp));
  82
  83         return curr;
  84 }
  85
  86 static noinline void check_xa_err(struct xarray *xa)
  87 {
  88         XA_BUG_ON(xa, xa_err(xa_store_index(xa, 0, GFP_NOWAIT)) != 0);
  89         XA_BUG_ON(xa, xa_err(xa_erase(xa, 0)) != 0);
  90 #ifndef __KERNEL__
  91         /* The kernel does not fail GFP_NOWAIT allocations */
  92         XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);
  93         XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);
  94 #endif
  95         XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_KERNEL)) != 0);
  96         XA_BUG_ON(xa, xa_err(xa_store(xa, 1, xa_mk_value(0), GFP_KERNEL)) != 0);
  97         XA_BUG_ON(xa, xa_err(xa_erase(xa, 1)) != 0);
  98 // kills the test-suite :-(
  99 //      XA_BUG_ON(xa, xa_err(xa_store(xa, 0, xa_mk_internal(0), 0)) != -EINVAL);
 100 }
 101
 102 static noinline void check_xas_retry(struct xarray *xa)
 103 {
 104         XA_STATE(xas, xa, 0);
 105         void *entry;
 106
 107         xa_store_index(xa, 0, GFP_KERNEL);
 108         xa_store_index(xa, 1, GFP_KERNEL);
 109
 110         rcu_read_lock();
 111         XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_value(0));
 112         xa_erase_index(xa, 1);
 113         XA_BUG_ON(xa, !xa_is_retry(xas_reload(&xas)));
 114         XA_BUG_ON(xa, xas_retry(&xas, NULL));
 115         XA_BUG_ON(xa, xas_retry(&xas, xa_mk_value(0)));
 116         xas_reset(&xas);
 117         XA_BUG_ON(xa, xas.xa_node != XAS_RESTART);
 118         XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
 119         XA_BUG_ON(xa, xas.xa_node != NULL);
 120         rcu_read_unlock();
 121
 122         XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
 123
 124         rcu_read_lock();
 125         XA_BUG_ON(xa, !xa_is_internal(xas_reload(&xas)));
 126         xas.xa_node = XAS_RESTART;
 127         XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
 128         rcu_read_unlock();
 129
 130         /* Make sure we can iterate through retry entries */
 131         xas_lock(&xas);
 132         xas_set(&xas, 0);
 133         xas_store(&xas, XA_RETRY_ENTRY);
 134         xas_set(&xas, 1);
 135         xas_store(&xas, XA_RETRY_ENTRY);
 136
 137         xas_set(&xas, 0);
 138         xas_for_each(&xas, entry, ULONG_MAX) {
 139                 xas_store(&xas, xa_mk_index(xas.xa_index));
 140         }
 141         xas_unlock(&xas);
 142
 143         xa_erase_index(xa, 0);
 144         xa_erase_index(xa, 1);
 145 }
 146
 147 static noinline void check_xa_load(struct xarray *xa)
 148 {
 149         unsigned long i, j;
 150
 151         for (i = 0; i < 1024; i++) {
 152                 for (j = 0; j < 1024; j++) {
 153                         void *entry = xa_load(xa, j);
 154                         if (j < i)
 155                                 XA_BUG_ON(xa, xa_to_value(entry) != j);
 156                         else
 157                                 XA_BUG_ON(xa, entry);
 158                 }
 159                 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
 160         }
 161
 162         for (i = 0; i < 1024; i++) {
 163                 for (j = 0; j < 1024; j++) {
 164                         void *entry = xa_load(xa, j);
 165                         if (j >= i)
 166                                 XA_BUG_ON(xa, xa_to_value(entry) != j);
 167                         else
 168                                 XA_BUG_ON(xa, entry);
 169                 }
 170                 xa_erase_index(xa, i);
 171         }
 172         XA_BUG_ON(xa, !xa_empty(xa));
 173 }
 174
 175 static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index)
 176 {
 177         unsigned int order;
 178         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 8 : 1;
 179
 180         /* NULL elements have no marks set */
 181         XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
 182         xa_set_mark(xa, index, XA_MARK_0);
 183         XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
 184
 185         /* Storing a pointer will not make a mark appear */
 186         XA_BUG_ON(xa, xa_store_index(xa, index, GFP_KERNEL) != NULL);
 187         XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
 188         xa_set_mark(xa, index, XA_MARK_0);
 189         XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));
 190
 191         /* Setting one mark will not set another mark */
 192         XA_BUG_ON(xa, xa_get_mark(xa, index + 1, XA_MARK_0));
 193         XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_1));
 194
 195         /* Storing NULL clears marks, and they can't be set again */
 196         xa_erase_index(xa, index);
 197         XA_BUG_ON(xa, !xa_empty(xa));
 198         XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
 199         xa_set_mark(xa, index, XA_MARK_0);
 200         XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
 201
 202         /*
 203          * Storing a multi-index entry over entries with marks gives the
 204          * entire entry the union of the marks
 205          */
 206         BUG_ON((index % 4) != 0);
 207         for (order = 2; order < max_order; order++) {
 208                 unsigned long base = round_down(index, 1UL << order);
 209                 unsigned long next = base + (1UL << order);
 210                 unsigned long i;
 211
 212                 XA_BUG_ON(xa, xa_store_index(xa, index + 1, GFP_KERNEL));
 213                 xa_set_mark(xa, index + 1, XA_MARK_0);
 214                 XA_BUG_ON(xa, xa_store_index(xa, index + 2, GFP_KERNEL));
 215                 xa_set_mark(xa, index + 2, XA_MARK_2);
 216                 XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL));
 217                 xa_store_order(xa, index, order, xa_mk_index(index),
 218                                 GFP_KERNEL);
 219                 for (i = base; i < next; i++) {
 220                         XA_STATE(xas, xa, i);
 221                         unsigned int seen = 0;
 222                         void *entry;
 223
 224                         XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
 225                         XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_1));
 226                         XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_2));
 227
 228                         /* We should see two elements in the array */
 229                         rcu_read_lock();
 230                         xas_for_each(&xas, entry, ULONG_MAX)
 231                                 seen++;
 232                         rcu_read_unlock();
 233                         XA_BUG_ON(xa, seen != 2);
 234
 235                         /* One of which is marked */
 236                         xas_set(&xas, 0);
 237                         seen = 0;
 238                         rcu_read_lock();
 239                         xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
 240                                 seen++;
 241                         rcu_read_unlock();
 242                         XA_BUG_ON(xa, seen != 1);
 243                 }
 244                 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_0));
 245                 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_1));
 246                 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_2));
 247                 xa_erase_index(xa, index);
 248                 xa_erase_index(xa, next);
 249                 XA_BUG_ON(xa, !xa_empty(xa));
 250         }
 251         XA_BUG_ON(xa, !xa_empty(xa));
 252 }
 253
 254 static noinline void check_xa_mark_2(struct xarray *xa)
 255 {
 256         XA_STATE(xas, xa, 0);
 257         unsigned long index;
 258         unsigned int count = 0;
 259         void *entry;
 260
 261         xa_store_index(xa, 0, GFP_KERNEL);
 262         xa_set_mark(xa, 0, XA_MARK_0);
 263         xas_lock(&xas);
 264         xas_load(&xas);
 265         xas_init_marks(&xas);
 266         xas_unlock(&xas);
 267         XA_BUG_ON(xa, !xa_get_mark(xa, 0, XA_MARK_0) == 0);
 268
 269         for (index = 3500; index < 4500; index++) {
 270                 xa_store_index(xa, index, GFP_KERNEL);
 271                 xa_set_mark(xa, index, XA_MARK_0);
 272         }
 273
 274         xas_reset(&xas);
 275         rcu_read_lock();
 276         xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
 277                 count++;
 278         rcu_read_unlock();
 279         XA_BUG_ON(xa, count != 1000);
 280
 281         xas_lock(&xas);
 282         xas_for_each(&xas, entry, ULONG_MAX) {
 283                 xas_init_marks(&xas);
 284                 XA_BUG_ON(xa, !xa_get_mark(xa, xas.xa_index, XA_MARK_0));
 285                 XA_BUG_ON(xa, !xas_get_mark(&xas, XA_MARK_0));
 286         }
 287         xas_unlock(&xas);
 288
 289         xa_destroy(xa);
 290 }
 291
 292 static noinline void check_xa_mark(struct xarray *xa)
 293 {
 294         unsigned long index;
 295
 296         for (index = 0; index < 16384; index += 4)
 297                 check_xa_mark_1(xa, index);
 298
 299         check_xa_mark_2(xa);
 300 }
 301
 302 static noinline void check_xa_shrink(struct xarray *xa)
 303 {
 304         XA_STATE(xas, xa, 1);
 305         struct xa_node *node;
 306         unsigned int order;
 307         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 15 : 1;
 308
 309         XA_BUG_ON(xa, !xa_empty(xa));
 310         XA_BUG_ON(xa, xa_store_index(xa, 0, GFP_KERNEL) != NULL);
 311         XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
 312
 313         /*
 314          * Check that erasing the entry at 1 shrinks the tree and properly
 315          * marks the node as being deleted.
 316          */
 317         xas_lock(&xas);
 318         XA_BUG_ON(xa, xas_load(&xas) != xa_mk_value(1));
 319         node = xas.xa_node;
 320         XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != xa_mk_value(0));
 321         XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
 322         XA_BUG_ON(xa, xa_load(xa, 1) != NULL);
 323         XA_BUG_ON(xa, xas.xa_node != XAS_BOUNDS);
 324         XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != XA_RETRY_ENTRY);
 325         XA_BUG_ON(xa, xas_load(&xas) != NULL);
 326         xas_unlock(&xas);
 327         XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
 328         xa_erase_index(xa, 0);
 329         XA_BUG_ON(xa, !xa_empty(xa));
 330
 331         for (order = 0; order < max_order; order++) {
 332                 unsigned long max = (1UL << order) - 1;
 333                 xa_store_order(xa, 0, order, xa_mk_value(0), GFP_KERNEL);
 334                 XA_BUG_ON(xa, xa_load(xa, max) != xa_mk_value(0));
 335                 XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);
 336                 rcu_read_lock();
 337                 node = xa_head(xa);
 338                 rcu_read_unlock();
 339                 XA_BUG_ON(xa, xa_store_index(xa, ULONG_MAX, GFP_KERNEL) !=
 340                                 NULL);
 341                 rcu_read_lock();
 342                 XA_BUG_ON(xa, xa_head(xa) == node);
 343                 rcu_read_unlock();
 344                 XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);
 345                 xa_erase_index(xa, ULONG_MAX);
 346                 XA_BUG_ON(xa, xa->xa_head != node);
 347                 xa_erase_index(xa, 0);
 348         }
 349 }
 350
 351 static noinline void check_insert(struct xarray *xa)
 352 {
 353         unsigned long i;
 354
 355         for (i = 0; i < 1024; i++) {
 356                 xa_insert_index(xa, i);
 357                 XA_BUG_ON(xa, xa_load(xa, i - 1) != NULL);
 358                 XA_BUG_ON(xa, xa_load(xa, i + 1) != NULL);
 359                 xa_erase_index(xa, i);
 360         }
 361
 362         for (i = 10; i < BITS_PER_LONG; i++) {
 363                 xa_insert_index(xa, 1UL << i);
 364                 XA_BUG_ON(xa, xa_load(xa, (1UL << i) - 1) != NULL);
 365                 XA_BUG_ON(xa, xa_load(xa, (1UL << i) + 1) != NULL);
 366                 xa_erase_index(xa, 1UL << i);
 367
 368                 xa_insert_index(xa, (1UL << i) - 1);
 369                 XA_BUG_ON(xa, xa_load(xa, (1UL << i) - 2) != NULL);
 370                 XA_BUG_ON(xa, xa_load(xa, 1UL << i) != NULL);
 371                 xa_erase_index(xa, (1UL << i) - 1);
 372         }
 373
 374         xa_insert_index(xa, ~0UL);
 375         XA_BUG_ON(xa, xa_load(xa, 0UL) != NULL);
 376         XA_BUG_ON(xa, xa_load(xa, ~1UL) != NULL);
 377         xa_erase_index(xa, ~0UL);
 378
 379         XA_BUG_ON(xa, !xa_empty(xa));
 380 }
 381
 382 static noinline void check_cmpxchg(struct xarray *xa)
 383 {
 384         void *FIVE = xa_mk_value(5);
 385         void *SIX = xa_mk_value(6);
 386         void *LOTS = xa_mk_value(12345678);
 387
 388         XA_BUG_ON(xa, !xa_empty(xa));
 389         XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_KERNEL) != NULL);
 390         XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EBUSY);
 391         XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS);
 392         XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS);
 393         XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE);
 394         XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != NULL);
 395         XA_BUG_ON(xa, xa_cmpxchg(xa, 5, NULL, FIVE, GFP_KERNEL) != NULL);
 396         xa_erase_index(xa, 12345678);
 397         xa_erase_index(xa, 5);
 398         XA_BUG_ON(xa, !xa_empty(xa));
 399 }
 400
 401 static noinline void check_reserve(struct xarray *xa)
 402 {
 403         void *entry;
 404         unsigned long index;
 405         int count;
 406
 407         /* An array with a reserved entry is not empty */
 408         XA_BUG_ON(xa, !xa_empty(xa));
 409         XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
 410         XA_BUG_ON(xa, xa_empty(xa));
 411         XA_BUG_ON(xa, xa_load(xa, 12345678));
 412         xa_release(xa, 12345678);
 413         XA_BUG_ON(xa, !xa_empty(xa));
 414
 415         /* Releasing a used entry does nothing */
 416         XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
 417         XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL);
 418         xa_release(xa, 12345678);
 419         xa_erase_index(xa, 12345678);
 420         XA_BUG_ON(xa, !xa_empty(xa));
 421
 422         /* cmpxchg sees a reserved entry as ZERO */
 423         XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
 424         XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, XA_ZERO_ENTRY,
 425                                 xa_mk_value(12345678), GFP_NOWAIT) != NULL);
 426         xa_release(xa, 12345678);
 427         xa_erase_index(xa, 12345678);
 428         XA_BUG_ON(xa, !xa_empty(xa));
 429
 430         /* xa_insert treats it as busy */
 431         XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
 432         XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) !=
 433                         -EBUSY);
 434         XA_BUG_ON(xa, xa_empty(xa));
 435         XA_BUG_ON(xa, xa_erase(xa, 12345678) != NULL);
 436         XA_BUG_ON(xa, !xa_empty(xa));
 437
 438         /* Can iterate through a reserved entry */
 439         xa_store_index(xa, 5, GFP_KERNEL);
 440         XA_BUG_ON(xa, xa_reserve(xa, 6, GFP_KERNEL) != 0);
 441         xa_store_index(xa, 7, GFP_KERNEL);
 442
 443         count = 0;
 444         xa_for_each(xa, index, entry) {
 445                 XA_BUG_ON(xa, index != 5 && index != 7);
 446                 count++;
 447         }
 448         XA_BUG_ON(xa, count != 2);
 449
 450         /* If we free a reserved entry, we should be able to allocate it */
 451         if (xa->xa_flags & XA_FLAGS_ALLOC) {
 452                 u32 id;
 453
 454                 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(8),
 455                                         XA_LIMIT(5, 10), GFP_KERNEL) != 0);
 456                 XA_BUG_ON(xa, id != 8);
 457
 458                 xa_release(xa, 6);
 459                 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(6),
 460                                         XA_LIMIT(5, 10), GFP_KERNEL) != 0);
 461                 XA_BUG_ON(xa, id != 6);
 462         }
 463
 464         xa_destroy(xa);
 465 }
 466
 467 static noinline void check_xas_erase(struct xarray *xa)
 468 {
 469         XA_STATE(xas, xa, 0);
 470         void *entry;
 471         unsigned long i, j;
 472
 473         for (i = 0; i < 200; i++) {
 474                 for (j = i; j < 2 * i + 17; j++) {
 475                         xas_set(&xas, j);
 476                         do {
 477                                 xas_lock(&xas);
 478                                 xas_store(&xas, xa_mk_index(j));
 479                                 xas_unlock(&xas);
 480                         } while (xas_nomem(&xas, GFP_KERNEL));
 481                 }
 482
 483                 xas_set(&xas, ULONG_MAX);
 484                 do {
 485                         xas_lock(&xas);
 486                         xas_store(&xas, xa_mk_value(0));
 487                         xas_unlock(&xas);
 488                 } while (xas_nomem(&xas, GFP_KERNEL));
 489
 490                 xas_lock(&xas);
 491                 xas_store(&xas, NULL);
 492
 493                 xas_set(&xas, 0);
 494                 j = i;
 495                 xas_for_each(&xas, entry, ULONG_MAX) {
 496                         XA_BUG_ON(xa, entry != xa_mk_index(j));
 497                         xas_store(&xas, NULL);
 498                         j++;
 499                 }
 500                 xas_unlock(&xas);
 501                 XA_BUG_ON(xa, !xa_empty(xa));
 502         }
 503 }
 504
 505 #ifdef CONFIG_XARRAY_MULTI
 506 static noinline void check_multi_store_1(struct xarray *xa, unsigned long index,
 507                 unsigned int order)
 508 {
 509         XA_STATE(xas, xa, index);
 510         unsigned long min = index & ~((1UL << order) - 1);
 511         unsigned long max = min + (1UL << order);
 512
 513         xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
 514         XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(index));
 515         XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(index));
 516         XA_BUG_ON(xa, xa_load(xa, max) != NULL);
 517         XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
 518
 519         xas_lock(&xas);
 520         XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(min)) != xa_mk_index(index));
 521         xas_unlock(&xas);
 522         XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(min));
 523         XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(min));
 524         XA_BUG_ON(xa, xa_load(xa, max) != NULL);
 525         XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
 526
 527         xa_erase_index(xa, min);
 528         XA_BUG_ON(xa, !xa_empty(xa));
 529 }
 530
 531 static noinline void check_multi_store_2(struct xarray *xa, unsigned long index,
 532                 unsigned int order)
 533 {
 534         XA_STATE(xas, xa, index);
 535         xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL);
 536
 537         xas_lock(&xas);
 538         XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0));
 539         XA_BUG_ON(xa, xas.xa_index != index);
 540         XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
 541         xas_unlock(&xas);
 542         XA_BUG_ON(xa, !xa_empty(xa));
 543 }
 544
 545 static noinline void check_multi_store_3(struct xarray *xa, unsigned long index,
 546                 unsigned int order)
 547 {
 548         XA_STATE(xas, xa, 0);
 549         void *entry;
 550         int n = 0;
 551
 552         xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
 553
 554         xas_lock(&xas);
 555         xas_for_each(&xas, entry, ULONG_MAX) {
 556                 XA_BUG_ON(xa, entry != xa_mk_index(index));
 557                 n++;
 558         }
 559         XA_BUG_ON(xa, n != 1);
 560         xas_set(&xas, index + 1);
 561         xas_for_each(&xas, entry, ULONG_MAX) {
 562                 XA_BUG_ON(xa, entry != xa_mk_index(index));
 563                 n++;
 564         }
 565         XA_BUG_ON(xa, n != 2);
 566         xas_unlock(&xas);
 567
 568         xa_destroy(xa);
 569 }
 570 #endif
 571
 572 static noinline void check_multi_store(struct xarray *xa)
 573 {
 574 #ifdef CONFIG_XARRAY_MULTI
 575         unsigned long i, j, k;
 576         unsigned int max_order = (sizeof(long) == 4) ? 30 : 60;
 577
 578         /* Loading from any position returns the same value */
 579         xa_store_order(xa, 0, 1, xa_mk_value(0), GFP_KERNEL);
 580         XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
 581         XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
 582         XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
 583         rcu_read_lock();
 584         XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 2);
 585         XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
 586         rcu_read_unlock();
 587
 588         /* Storing adjacent to the value does not alter the value */
 589         xa_store(xa, 3, xa, GFP_KERNEL);
 590         XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
 591         XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
 592         XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
 593         rcu_read_lock();
 594         XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 3);
 595         XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
 596         rcu_read_unlock();
 597
 598         /* Overwriting multiple indexes works */
 599         xa_store_order(xa, 0, 2, xa_mk_value(1), GFP_KERNEL);
 600         XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(1));
 601         XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(1));
 602         XA_BUG_ON(xa, xa_load(xa, 2) != xa_mk_value(1));
 603         XA_BUG_ON(xa, xa_load(xa, 3) != xa_mk_value(1));
 604         XA_BUG_ON(xa, xa_load(xa, 4) != NULL);
 605         rcu_read_lock();
 606         XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 4);
 607         XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 4);
 608         rcu_read_unlock();
 609
 610         /* We can erase multiple values with a single store */
 611         xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL);
 612         XA_BUG_ON(xa, !xa_empty(xa));
 613
 614         /* Even when the first slot is empty but the others aren't */
 615         xa_store_index(xa, 1, GFP_KERNEL);
 616         xa_store_index(xa, 2, GFP_KERNEL);
 617         xa_store_order(xa, 0, 2, NULL, GFP_KERNEL);
 618         XA_BUG_ON(xa, !xa_empty(xa));
 619
 620         for (i = 0; i < max_order; i++) {
 621                 for (j = 0; j < max_order; j++) {
 622                         xa_store_order(xa, 0, i, xa_mk_index(i), GFP_KERNEL);
 623                         xa_store_order(xa, 0, j, xa_mk_index(j), GFP_KERNEL);
 624
 625                         for (k = 0; k < max_order; k++) {
 626                                 void *entry = xa_load(xa, (1UL << k) - 1);
 627                                 if ((i < k) && (j < k))
 628                                         XA_BUG_ON(xa, entry != NULL);
 629                                 else
 630                                         XA_BUG_ON(xa, entry != xa_mk_index(j));
 631                         }
 632
 633                         xa_erase(xa, 0);
 634                         XA_BUG_ON(xa, !xa_empty(xa));
 635                 }
 636         }
 637
 638         for (i = 0; i < 20; i++) {
 639                 check_multi_store_1(xa, 200, i);
 640                 check_multi_store_1(xa, 0, i);
 641                 check_multi_store_1(xa, (1UL << i) + 1, i);
 642         }
 643         check_multi_store_2(xa, 4095, 9);
 644
 645         for (i = 1; i < 20; i++) {
 646                 check_multi_store_3(xa, 0, i);
 647                 check_multi_store_3(xa, 1UL << i, i);
 648         }
 649 #endif
 650 }
 651
 652 static noinline void check_xa_alloc_1(struct xarray *xa, unsigned int base)
 653 {
 654         int i;
 655         u32 id;
 656
 657         XA_BUG_ON(xa, !xa_empty(xa));
 658         /* An empty array should assign %base to the first alloc */
 659         xa_alloc_index(xa, base, GFP_KERNEL);
 660
 661         /* Erasing it should make the array empty again */
 662         xa_erase_index(xa, base);
 663         XA_BUG_ON(xa, !xa_empty(xa));
 664
 665         /* And it should assign %base again */
 666         xa_alloc_index(xa, base, GFP_KERNEL);
 667
 668         /* Allocating and then erasing a lot should not lose base */
 669         for (i = base + 1; i < 2 * XA_CHUNK_SIZE; i++)
 670                 xa_alloc_index(xa, i, GFP_KERNEL);
 671         for (i = base; i < 2 * XA_CHUNK_SIZE; i++)
 672                 xa_erase_index(xa, i);
 673         xa_alloc_index(xa, base, GFP_KERNEL);
 674
 675         /* Destroying the array should do the same as erasing */
 676         xa_destroy(xa);
 677
 678         /* And it should assign %base again */
 679         xa_alloc_index(xa, base, GFP_KERNEL);
 680
 681         /* The next assigned ID should be base+1 */
 682         xa_alloc_index(xa, base + 1, GFP_KERNEL);
 683         xa_erase_index(xa, base + 1);
 684
 685         /* Storing a value should mark it used */
 686         xa_store_index(xa, base + 1, GFP_KERNEL);
 687         xa_alloc_index(xa, base + 2, GFP_KERNEL);
 688
 689         /* If we then erase base, it should be free */
 690         xa_erase_index(xa, base);
 691         xa_alloc_index(xa, base, GFP_KERNEL);
 692
 693         xa_erase_index(xa, base + 1);
 694         xa_erase_index(xa, base + 2);
 695
 696         for (i = 1; i < 5000; i++) {
 697                 xa_alloc_index(xa, base + i, GFP_KERNEL);
 698         }
 699
 700         xa_destroy(xa);
 701
 702         /* Check that we fail properly at the limit of allocation */
 703         XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX - 1),
 704                                 XA_LIMIT(UINT_MAX - 1, UINT_MAX),
 705                                 GFP_KERNEL) != 0);
 706         XA_BUG_ON(xa, id != 0xfffffffeU);
 707         XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX),
 708                                 XA_LIMIT(UINT_MAX - 1, UINT_MAX),
 709                                 GFP_KERNEL) != 0);
 710         XA_BUG_ON(xa, id != 0xffffffffU);
 711         id = 3;
 712         XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(0),
 713                                 XA_LIMIT(UINT_MAX - 1, UINT_MAX),
 714                                 GFP_KERNEL) != -EBUSY);
 715         XA_BUG_ON(xa, id != 3);
 716         xa_destroy(xa);
 717
 718         XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),
 719                                 GFP_KERNEL) != -EBUSY);
 720         XA_BUG_ON(xa, xa_store_index(xa, 3, GFP_KERNEL) != 0);
 721         XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),
 722                                 GFP_KERNEL) != -EBUSY);
 723         xa_erase_index(xa, 3);
 724         XA_BUG_ON(xa, !xa_empty(xa));
 725 }
 726
 727 static noinline void check_xa_alloc_2(struct xarray *xa, unsigned int base)
 728 {
 729         unsigned int i, id;
 730         unsigned long index;
 731         void *entry;
 732
 733         /* Allocate and free a NULL and check xa_empty() behaves */
 734         XA_BUG_ON(xa, !xa_empty(xa));
 735         XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
 736         XA_BUG_ON(xa, id != base);
 737         XA_BUG_ON(xa, xa_empty(xa));
 738         XA_BUG_ON(xa, xa_erase(xa, id) != NULL);
 739         XA_BUG_ON(xa, !xa_empty(xa));
 740
 741         /* Ditto, but check destroy instead of erase */
 742         XA_BUG_ON(xa, !xa_empty(xa));
 743         XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
 744         XA_BUG_ON(xa, id != base);
 745         XA_BUG_ON(xa, xa_empty(xa));
 746         xa_destroy(xa);
 747         XA_BUG_ON(xa, !xa_empty(xa));
 748
 749         for (i = base; i < base + 10; i++) {
 750                 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b,
 751                                         GFP_KERNEL) != 0);
 752                 XA_BUG_ON(xa, id != i);
 753         }
 754
 755         XA_BUG_ON(xa, xa_store(xa, 3, xa_mk_index(3), GFP_KERNEL) != NULL);
 756         XA_BUG_ON(xa, xa_store(xa, 4, xa_mk_index(4), GFP_KERNEL) != NULL);
 757         XA_BUG_ON(xa, xa_store(xa, 4, NULL, GFP_KERNEL) != xa_mk_index(4));
 758         XA_BUG_ON(xa, xa_erase(xa, 5) != NULL);
 759         XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
 760         XA_BUG_ON(xa, id != 5);
 761
 762         xa_for_each(xa, index, entry) {
 763                 xa_erase_index(xa, index);
 764         }
 765
 766         for (i = base; i < base + 9; i++) {
 767                 XA_BUG_ON(xa, xa_erase(xa, i) != NULL);
 768                 XA_BUG_ON(xa, xa_empty(xa));
 769         }
 770         XA_BUG_ON(xa, xa_erase(xa, 8) != NULL);
 771         XA_BUG_ON(xa, xa_empty(xa));
 772         XA_BUG_ON(xa, xa_erase(xa, base + 9) != NULL);
 773         XA_BUG_ON(xa, !xa_empty(xa));
 774
 775         xa_destroy(xa);
 776 }
 777
 778 static noinline void check_xa_alloc_3(struct xarray *xa, unsigned int base)
 779 {
 780         struct xa_limit limit = XA_LIMIT(1, 0x3fff);
 781         u32 next = 0;
 782         unsigned int i, id;
 783         unsigned long index;
 784         void *entry;
 785
 786         XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(1), limit,
 787                                 &next, GFP_KERNEL) != 0);
 788         XA_BUG_ON(xa, id != 1);
 789
 790         next = 0x3ffd;
 791         XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(0x3ffd), limit,
 792                                 &next, GFP_KERNEL) != 0);
 793         XA_BUG_ON(xa, id != 0x3ffd);
 794         xa_erase_index(xa, 0x3ffd);
 795         xa_erase_index(xa, 1);
 796         XA_BUG_ON(xa, !xa_empty(xa));
 797
 798         for (i = 0x3ffe; i < 0x4003; i++) {
 799                 if (i < 0x4000)
 800                         entry = xa_mk_index(i);
 801                 else
 802                         entry = xa_mk_index(i - 0x3fff);
 803                 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, entry, limit,
 804                                         &next, GFP_KERNEL) != (id == 1));
 805                 XA_BUG_ON(xa, xa_mk_index(id) != entry);
 806         }
 807
 808         /* Check wrap-around is handled correctly */
 809         if (base != 0)
 810                 xa_erase_index(xa, base);
 811         xa_erase_index(xa, base + 1);
 812         next = UINT_MAX;
 813         XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(UINT_MAX),
 814                                 xa_limit_32b, &next, GFP_KERNEL) != 0);
 815         XA_BUG_ON(xa, id != UINT_MAX);
 816         XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base),
 817                                 xa_limit_32b, &next, GFP_KERNEL) != 1);
 818         XA_BUG_ON(xa, id != base);
 819         XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base + 1),
 820                                 xa_limit_32b, &next, GFP_KERNEL) != 0);
 821         XA_BUG_ON(xa, id != base + 1);
 822
 823         xa_for_each(xa, index, entry)
 824                 xa_erase_index(xa, index);
 825
 826         XA_BUG_ON(xa, !xa_empty(xa));
 827 }
 828
 829 static DEFINE_XARRAY_ALLOC(xa0);
 830 static DEFINE_XARRAY_ALLOC1(xa1);
 831
 832 static noinline void check_xa_alloc(void)
 833 {
 834         check_xa_alloc_1(&xa0, 0);
 835         check_xa_alloc_1(&xa1, 1);
 836         check_xa_alloc_2(&xa0, 0);
 837         check_xa_alloc_2(&xa1, 1);
 838         check_xa_alloc_3(&xa0, 0);
 839         check_xa_alloc_3(&xa1, 1);
 840 }
 841
 842 static noinline void __check_store_iter(struct xarray *xa, unsigned long start,
 843                         unsigned int order, unsigned int present)
 844 {
 845         XA_STATE_ORDER(xas, xa, start, order);
 846         void *entry;
 847         unsigned int count = 0;
 848
 849 retry:
 850         xas_lock(&xas);
 851         xas_for_each_conflict(&xas, entry) {
 852                 XA_BUG_ON(xa, !xa_is_value(entry));
 853                 XA_BUG_ON(xa, entry < xa_mk_index(start));
 854                 XA_BUG_ON(xa, entry > xa_mk_index(start + (1UL << order) - 1));
 855                 count++;
 856         }
 857         xas_store(&xas, xa_mk_index(start));
 858         xas_unlock(&xas);
 859         if (xas_nomem(&xas, GFP_KERNEL)) {
 860                 count = 0;
 861                 goto retry;
 862         }
 863         XA_BUG_ON(xa, xas_error(&xas));
 864         XA_BUG_ON(xa, count != present);
 865         XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_index(start));
 866         XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) !=
 867                         xa_mk_index(start));
 868         xa_erase_index(xa, start);
 869 }
 870
 871 static noinline void check_store_iter(struct xarray *xa)
 872 {
 873         unsigned int i, j;
 874         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;
 875
 876         for (i = 0; i < max_order; i++) {
 877                 unsigned int min = 1 << i;
 878                 unsigned int max = (2 << i) - 1;
 879                 __check_store_iter(xa, 0, i, 0);
 880                 XA_BUG_ON(xa, !xa_empty(xa));
 881                 __check_store_iter(xa, min, i, 0);
 882                 XA_BUG_ON(xa, !xa_empty(xa));
 883
 884                 xa_store_index(xa, min, GFP_KERNEL);
 885                 __check_store_iter(xa, min, i, 1);
 886                 XA_BUG_ON(xa, !xa_empty(xa));
 887                 xa_store_index(xa, max, GFP_KERNEL);
 888                 __check_store_iter(xa, min, i, 1);
 889                 XA_BUG_ON(xa, !xa_empty(xa));
 890
 891                 for (j = 0; j < min; j++)
 892                         xa_store_index(xa, j, GFP_KERNEL);
 893                 __check_store_iter(xa, 0, i, min);
 894                 XA_BUG_ON(xa, !xa_empty(xa));
 895                 for (j = 0; j < min; j++)
 896                         xa_store_index(xa, min + j, GFP_KERNEL);
 897                 __check_store_iter(xa, min, i, min);
 898                 XA_BUG_ON(xa, !xa_empty(xa));
 899         }
 900 #ifdef CONFIG_XARRAY_MULTI
 901         xa_store_index(xa, 63, GFP_KERNEL);
 902         xa_store_index(xa, 65, GFP_KERNEL);
 903         __check_store_iter(xa, 64, 2, 1);
 904         xa_erase_index(xa, 63);
 905 #endif
 906         XA_BUG_ON(xa, !xa_empty(xa));
 907 }
 908
 909 static noinline void check_multi_find_1(struct xarray *xa, unsigned order)
 910 {
 911 #ifdef CONFIG_XARRAY_MULTI
 912         unsigned long multi = 3 << order;
 913         unsigned long next = 4 << order;
 914         unsigned long index;
 915
 916         xa_store_order(xa, multi, order, xa_mk_value(multi), GFP_KERNEL);
 917         XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL) != NULL);
 918         XA_BUG_ON(xa, xa_store_index(xa, next + 1, GFP_KERNEL) != NULL);
 919
 920         index = 0;
 921         XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
 922                         xa_mk_value(multi));
 923         XA_BUG_ON(xa, index != multi);
 924         index = multi + 1;
 925         XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
 926                         xa_mk_value(multi));
 927         XA_BUG_ON(xa, (index < multi) || (index >= next));
 928         XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) !=
 929                         xa_mk_value(next));
 930         XA_BUG_ON(xa, index != next);
 931         XA_BUG_ON(xa, xa_find_after(xa, &index, next, XA_PRESENT) != NULL);
 932         XA_BUG_ON(xa, index != next);
 933
 934         xa_erase_index(xa, multi);
 935         xa_erase_index(xa, next);
 936         xa_erase_index(xa, next + 1);
 937         XA_BUG_ON(xa, !xa_empty(xa));
 938 #endif
 939 }
 940
 941 static noinline void check_multi_find_2(struct xarray *xa)
 942 {
 943         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1;
 944         unsigned int i, j;
 945         void *entry;
 946
 947         for (i = 0; i < max_order; i++) {
 948                 unsigned long index = 1UL << i;
 949                 for (j = 0; j < index; j++) {
 950                         XA_STATE(xas, xa, j + index);
 951                         xa_store_index(xa, index - 1, GFP_KERNEL);
 952                         xa_store_order(xa, index, i, xa_mk_index(index),
 953                                         GFP_KERNEL);
 954                         rcu_read_lock();
 955                         xas_for_each(&xas, entry, ULONG_MAX) {
 956                                 xa_erase_index(xa, index);
 957                         }
 958                         rcu_read_unlock();
 959                         xa_erase_index(xa, index - 1);
 960                         XA_BUG_ON(xa, !xa_empty(xa));
 961                 }
 962         }
 963 }
 964
 965 static noinline void check_multi_find_3(struct xarray *xa)
 966 {
 967         unsigned int order;
 968
 969         for (order = 5; order < order_limit; order++) {
 970                 unsigned long index = 1UL << (order - 5);
 971
 972                 XA_BUG_ON(xa, !xa_empty(xa));
 973                 xa_store_order(xa, 0, order - 4, xa_mk_index(0), GFP_KERNEL);
 974                 XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT));
 975                 xa_erase_index(xa, 0);
 976         }
 977 }
 978
 979 static noinline void check_find_1(struct xarray *xa)
 980 {
 981         unsigned long i, j, k;
 982
 983         XA_BUG_ON(xa, !xa_empty(xa));
 984
 985         /*
 986          * Check xa_find with all pairs between 0 and 99 inclusive,
 987          * starting at every index between 0 and 99
 988          */
 989         for (i = 0; i < 100; i++) {
 990                 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
 991                 xa_set_mark(xa, i, XA_MARK_0);
 992                 for (j = 0; j < i; j++) {
 993                         XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) !=
 994                                         NULL);
 995                         xa_set_mark(xa, j, XA_MARK_0);
 996                         for (k = 0; k < 100; k++) {
 997                                 unsigned long index = k;
 998                                 void *entry = xa_find(xa, &index, ULONG_MAX,
 999                                                                 XA_PRESENT);
1000                                 if (k <= j)
1001                                         XA_BUG_ON(xa, index != j);
1002                                 else if (k <= i)
1003                                         XA_BUG_ON(xa, index != i);
1004                                 else
1005                                         XA_BUG_ON(xa, entry != NULL);
1006
1007                                 index = k;
1008                                 entry = xa_find(xa, &index, ULONG_MAX,
1009                                                                 XA_MARK_0);
1010                                 if (k <= j)
1011                                         XA_BUG_ON(xa, index != j);
1012                                 else if (k <= i)
1013                                         XA_BUG_ON(xa, index != i);
1014                                 else
1015                                         XA_BUG_ON(xa, entry != NULL);
1016                         }
1017                         xa_erase_index(xa, j);
1018                         XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0));
1019                         XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
1020                 }
1021                 xa_erase_index(xa, i);
1022                 XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0));
1023         }
1024         XA_BUG_ON(xa, !xa_empty(xa));
1025 }
1026
1027 static noinline void check_find_2(struct xarray *xa)
1028 {
1029         void *entry;
1030         unsigned long i, j, index;
1031
1032         xa_for_each(xa, index, entry) {
1033                 XA_BUG_ON(xa, true);
1034         }
1035
1036         for (i = 0; i < 1024; i++) {
1037                 xa_store_index(xa, index, GFP_KERNEL);
1038                 j = 0;
1039                 xa_for_each(xa, index, entry) {
1040                         XA_BUG_ON(xa, xa_mk_index(index) != entry);
1041                         XA_BUG_ON(xa, index != j++);
1042                 }
1043         }
1044
1045         xa_destroy(xa);
1046 }
1047
1048 static noinline void check_find_3(struct xarray *xa)
1049 {
1050         XA_STATE(xas, xa, 0);
1051         unsigned long i, j, k;
1052         void *entry;
1053
1054         for (i = 0; i < 100; i++) {
1055                 for (j = 0; j < 100; j++) {
1056                         rcu_read_lock();
1057                         for (k = 0; k < 100; k++) {
1058                                 xas_set(&xas, j);
1059                                 xas_for_each_marked(&xas, entry, k, XA_MARK_0)
1060                                         ;
1061                                 if (j > k)
1062                                         XA_BUG_ON(xa,
1063                                                 xas.xa_node != XAS_RESTART);
1064                         }
1065                         rcu_read_unlock();
1066                 }
1067                 xa_store_index(xa, i, GFP_KERNEL);
1068                 xa_set_mark(xa, i, XA_MARK_0);
1069         }
1070         xa_destroy(xa);
1071 }
1072
1073 static noinline void check_find_4(struct xarray *xa)
1074 {
1075         unsigned long index = 0;
1076         void *entry;
1077
1078         xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
1079
1080         entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);
1081         XA_BUG_ON(xa, entry != xa_mk_index(ULONG_MAX));
1082
1083         entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);
1084         XA_BUG_ON(xa, entry);
1085
1086         xa_erase_index(xa, ULONG_MAX);
1087 }
1088
1089 static noinline void check_find(struct xarray *xa)
1090 {
1091         unsigned i;
1092
1093         check_find_1(xa);
1094         check_find_2(xa);
1095         check_find_3(xa);
1096         check_find_4(xa);
1097
1098         for (i = 2; i < 10; i++)
1099                 check_multi_find_1(xa, i);
1100         check_multi_find_2(xa);
1101         check_multi_find_3(xa);
1102 }
1103
1104 /* See find_swap_entry() in mm/shmem.c */
1105 static noinline unsigned long xa_find_entry(struct xarray *xa, void *item)
1106 {
1107         XA_STATE(xas, xa, 0);
1108         unsigned int checked = 0;
1109         void *entry;
1110
1111         rcu_read_lock();
1112         xas_for_each(&xas, entry, ULONG_MAX) {
1113                 if (xas_retry(&xas, entry))
1114                         continue;
1115                 if (entry == item)
1116                         break;
1117                 checked++;
1118                 if ((checked % 4) != 0)
1119                         continue;
1120                 xas_pause(&xas);
1121         }
1122         rcu_read_unlock();
1123
1124         return entry ? xas.xa_index : -1;
1125 }
1126
1127 static noinline void check_find_entry(struct xarray *xa)
1128 {
1129 #ifdef CONFIG_XARRAY_MULTI
1130         unsigned int order;
1131         unsigned long offset, index;
1132
1133         for (order = 0; order < 20; order++) {
1134                 for (offset = 0; offset < (1UL << (order + 3));
1135                      offset += (1UL << order)) {
1136                         for (index = 0; index < (1UL << (order + 5));
1137                              index += (1UL << order)) {
1138                                 xa_store_order(xa, index, order,
1139                                                 xa_mk_index(index), GFP_KERNEL);
1140                                 XA_BUG_ON(xa, xa_load(xa, index) !=
1141                                                 xa_mk_index(index));
1142                                 XA_BUG_ON(xa, xa_find_entry(xa,
1143                                                 xa_mk_index(index)) != index);
1144                         }
1145                         XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
1146                         xa_destroy(xa);
1147                 }
1148         }
1149 #endif
1150
1151         XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
1152         xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
1153         XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
1154         XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_index(ULONG_MAX)) != -1);
1155         xa_erase_index(xa, ULONG_MAX);
1156         XA_BUG_ON(xa, !xa_empty(xa));
1157 }
1158
1159 static noinline void check_pause(struct xarray *xa)
1160 {
1161         XA_STATE(xas, xa, 0);
1162         void *entry;
1163         unsigned int order;
1164         unsigned long index = 1;
1165         unsigned int count = 0;
1166
1167         for (order = 0; order < order_limit; order++) {
1168                 XA_BUG_ON(xa, xa_store_order(xa, index, order,
1169                                         xa_mk_index(index), GFP_KERNEL));
1170                 index += 1UL << order;
1171         }
1172
1173         rcu_read_lock();
1174         xas_for_each(&xas, entry, ULONG_MAX) {
1175                 XA_BUG_ON(xa, entry != xa_mk_index(1UL << count));
1176                 count++;
1177         }
1178         rcu_read_unlock();
1179         XA_BUG_ON(xa, count != order_limit);
1180
1181         count = 0;
1182         xas_set(&xas, 0);
1183         rcu_read_lock();
1184         xas_for_each(&xas, entry, ULONG_MAX) {
1185                 XA_BUG_ON(xa, entry != xa_mk_index(1UL << count));
1186                 count++;
1187                 xas_pause(&xas);
1188         }
1189         rcu_read_unlock();
1190         XA_BUG_ON(xa, count != order_limit);
1191
1192         xa_destroy(xa);
1193 }
1194
1195 static noinline void check_move_tiny(struct xarray *xa)
1196 {
1197         XA_STATE(xas, xa, 0);
1198
1199         XA_BUG_ON(xa, !xa_empty(xa));
1200         rcu_read_lock();
1201         XA_BUG_ON(xa, xas_next(&xas) != NULL);
1202         XA_BUG_ON(xa, xas_next(&xas) != NULL);
1203         rcu_read_unlock();
1204         xa_store_index(xa, 0, GFP_KERNEL);
1205         rcu_read_lock();
1206         xas_set(&xas, 0);
1207         XA_BUG_ON(xa, xas_next(&xas) != xa_mk_index(0));
1208         XA_BUG_ON(xa, xas_next(&xas) != NULL);
1209         xas_set(&xas, 0);
1210         XA_BUG_ON(xa, xas_prev(&xas) != xa_mk_index(0));
1211         XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1212         rcu_read_unlock();
1213         xa_erase_index(xa, 0);
1214         XA_BUG_ON(xa, !xa_empty(xa));
1215 }
1216
1217 static noinline void check_move_max(struct xarray *xa)
1218 {
1219         XA_STATE(xas, xa, 0);
1220
1221         xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
1222         rcu_read_lock();
1223         XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));
1224         XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);
1225         rcu_read_unlock();
1226
1227         xas_set(&xas, 0);
1228         rcu_read_lock();
1229         XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));
1230         xas_pause(&xas);
1231         XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);
1232         rcu_read_unlock();
1233
1234         xa_erase_index(xa, ULONG_MAX);
1235         XA_BUG_ON(xa, !xa_empty(xa));
1236 }
1237
1238 static noinline void check_move_small(struct xarray *xa, unsigned long idx)
1239 {
1240         XA_STATE(xas, xa, 0);
1241         unsigned long i;
1242
1243         xa_store_index(xa, 0, GFP_KERNEL);
1244         xa_store_index(xa, idx, GFP_KERNEL);
1245
1246         rcu_read_lock();
1247         for (i = 0; i < idx * 4; i++) {
1248                 void *entry = xas_next(&xas);
1249                 if (i <= idx)
1250                         XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
1251                 XA_BUG_ON(xa, xas.xa_index != i);
1252                 if (i == 0 || i == idx)
1253                         XA_BUG_ON(xa, entry != xa_mk_index(i));
1254                 else
1255                         XA_BUG_ON(xa, entry != NULL);
1256         }
1257         xas_next(&xas);
1258         XA_BUG_ON(xa, xas.xa_index != i);
1259
1260         do {
1261                 void *entry = xas_prev(&xas);
1262                 i--;
1263                 if (i <= idx)
1264                         XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
1265                 XA_BUG_ON(xa, xas.xa_index != i);
1266                 if (i == 0 || i == idx)
1267                         XA_BUG_ON(xa, entry != xa_mk_index(i));
1268                 else
1269                         XA_BUG_ON(xa, entry != NULL);
1270         } while (i > 0);
1271
1272         xas_set(&xas, ULONG_MAX);
1273         XA_BUG_ON(xa, xas_next(&xas) != NULL);
1274         XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1275         XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0));
1276         XA_BUG_ON(xa, xas.xa_index != 0);
1277         XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1278         XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1279         rcu_read_unlock();
1280
1281         xa_erase_index(xa, 0);
1282         xa_erase_index(xa, idx);
1283         XA_BUG_ON(xa, !xa_empty(xa));
1284 }
1285
1286 static noinline void check_move(struct xarray *xa)
1287 {
1288         XA_STATE(xas, xa, (1 << 16) - 1);
1289         unsigned long i;
1290
1291         for (i = 0; i < (1 << 16); i++)
1292                 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
1293
1294         rcu_read_lock();
1295         do {
1296                 void *entry = xas_prev(&xas);
1297                 i--;
1298                 XA_BUG_ON(xa, entry != xa_mk_index(i));
1299                 XA_BUG_ON(xa, i != xas.xa_index);
1300         } while (i != 0);
1301
1302         XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1303         XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1304
1305         do {
1306                 void *entry = xas_next(&xas);
1307                 XA_BUG_ON(xa, entry != xa_mk_index(i));
1308                 XA_BUG_ON(xa, i != xas.xa_index);
1309                 i++;
1310         } while (i < (1 << 16));
1311         rcu_read_unlock();
1312
1313         for (i = (1 << 8); i < (1 << 15); i++)
1314                 xa_erase_index(xa, i);
1315
1316         i = xas.xa_index;
1317
1318         rcu_read_lock();
1319         do {
1320                 void *entry = xas_prev(&xas);
1321                 i--;
1322                 if ((i < (1 << 8)) || (i >= (1 << 15)))
1323                         XA_BUG_ON(xa, entry != xa_mk_index(i));
1324                 else
1325                         XA_BUG_ON(xa, entry != NULL);
1326                 XA_BUG_ON(xa, i != xas.xa_index);
1327         } while (i != 0);
1328
1329         XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1330         XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1331
1332         do {
1333                 void *entry = xas_next(&xas);
1334                 if ((i < (1 << 8)) || (i >= (1 << 15)))
1335                         XA_BUG_ON(xa, entry != xa_mk_index(i));
1336                 else
1337                         XA_BUG_ON(xa, entry != NULL);
1338                 XA_BUG_ON(xa, i != xas.xa_index);
1339                 i++;
1340         } while (i < (1 << 16));
1341         rcu_read_unlock();
1342
1343         xa_destroy(xa);
1344
1345         check_move_tiny(xa);
1346         check_move_max(xa);
1347
1348         for (i = 0; i < 16; i++)
1349                 check_move_small(xa, 1UL << i);
1350
1351         for (i = 2; i < 16; i++)
1352                 check_move_small(xa, (1UL << i) - 1);
1353 }
1354
1355 static noinline void xa_store_many_order(struct xarray *xa,
1356                 unsigned long index, unsigned order)
1357 {
1358         XA_STATE_ORDER(xas, xa, index, order);
1359         unsigned int i = 0;
1360
1361         do {
1362                 xas_lock(&xas);
1363                 XA_BUG_ON(xa, xas_find_conflict(&xas));
1364                 xas_create_range(&xas);
1365                 if (xas_error(&xas))
1366                         goto unlock;
1367                 for (i = 0; i < (1U << order); i++) {
1368                         XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(index + i)));
1369                         xas_next(&xas);
1370                 }
1371 unlock:
1372                 xas_unlock(&xas);
1373         } while (xas_nomem(&xas, GFP_KERNEL));
1374
1375         XA_BUG_ON(xa, xas_error(&xas));
1376 }
1377
1378 static noinline void check_create_range_1(struct xarray *xa,
1379                 unsigned long index, unsigned order)
1380 {
1381         unsigned long i;
1382
1383         xa_store_many_order(xa, index, order);
1384         for (i = index; i < index + (1UL << order); i++)
1385                 xa_erase_index(xa, i);
1386         XA_BUG_ON(xa, !xa_empty(xa));
1387 }
1388
1389 static noinline void check_create_range_2(struct xarray *xa, unsigned order)
1390 {
1391         unsigned long i;
1392         unsigned long nr = 1UL << order;
1393
1394         for (i = 0; i < nr * nr; i += nr)
1395                 xa_store_many_order(xa, i, order);
1396         for (i = 0; i < nr * nr; i++)
1397                 xa_erase_index(xa, i);
1398         XA_BUG_ON(xa, !xa_empty(xa));
1399 }
1400
1401 static noinline void check_create_range_3(void)
1402 {
1403         XA_STATE(xas, NULL, 0);
1404         xas_set_err(&xas, -EEXIST);
1405         xas_create_range(&xas);
1406         XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST);
1407 }
1408
1409 static noinline void check_create_range_4(struct xarray *xa,
1410                 unsigned long index, unsigned order)
1411 {
1412         XA_STATE_ORDER(xas, xa, index, order);
1413         unsigned long base = xas.xa_index;
1414         unsigned long i = 0;
1415
1416         xa_store_index(xa, index, GFP_KERNEL);
1417         do {
1418                 xas_lock(&xas);
1419                 xas_create_range(&xas);
1420                 if (xas_error(&xas))
1421                         goto unlock;
1422                 for (i = 0; i < (1UL << order); i++) {
1423                         void *old = xas_store(&xas, xa_mk_index(base + i));
1424                         if (xas.xa_index == index)
1425                                 XA_BUG_ON(xa, old != xa_mk_index(base + i));
1426                         else
1427                                 XA_BUG_ON(xa, old != NULL);
1428                         xas_next(&xas);
1429                 }
1430 unlock:
1431                 xas_unlock(&xas);
1432         } while (xas_nomem(&xas, GFP_KERNEL));
1433
1434         XA_BUG_ON(xa, xas_error(&xas));
1435
1436         for (i = base; i < base + (1UL << order); i++)
1437                 xa_erase_index(xa, i);
1438         XA_BUG_ON(xa, !xa_empty(xa));
1439 }
1440
1441 static noinline void check_create_range(struct xarray *xa)
1442 {
1443         unsigned int order;
1444         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1;
1445
1446         for (order = 0; order < max_order; order++) {
1447                 check_create_range_1(xa, 0, order);
1448                 check_create_range_1(xa, 1U << order, order);
1449                 check_create_range_1(xa, 2U << order, order);
1450                 check_create_range_1(xa, 3U << order, order);
1451                 check_create_range_1(xa, 1U << 24, order);
1452                 if (order < 10)
1453                         check_create_range_2(xa, order);
1454
1455                 check_create_range_4(xa, 0, order);
1456                 check_create_range_4(xa, 1U << order, order);
1457                 check_create_range_4(xa, 2U << order, order);
1458                 check_create_range_4(xa, 3U << order, order);
1459                 check_create_range_4(xa, 1U << 24, order);
1460
1461                 check_create_range_4(xa, 1, order);
1462                 check_create_range_4(xa, (1U << order) + 1, order);
1463                 check_create_range_4(xa, (2U << order) + 1, order);
1464                 check_create_range_4(xa, (2U << order) - 1, order);
1465                 check_create_range_4(xa, (3U << order) + 1, order);
1466                 check_create_range_4(xa, (3U << order) - 1, order);
1467                 check_create_range_4(xa, (1U << 24) + 1, order);
1468         }
1469
1470         check_create_range_3();
1471 }
1472
1473 static noinline void __check_store_range(struct xarray *xa, unsigned long first,
1474                 unsigned long last)
1475 {
1476 #ifdef CONFIG_XARRAY_MULTI
1477         xa_store_range(xa, first, last, xa_mk_index(first), GFP_KERNEL);
1478
1479         XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_index(first));
1480         XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_index(first));
1481         XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL);
1482         XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL);
1483
1484         xa_store_range(xa, first, last, NULL, GFP_KERNEL);
1485 #endif
1486
1487         XA_BUG_ON(xa, !xa_empty(xa));
1488 }
1489
1490 static noinline void check_store_range(struct xarray *xa)
1491 {
1492         unsigned long i, j;
1493
1494         for (i = 0; i < 128; i++) {
1495                 for (j = i; j < 128; j++) {
1496                         __check_store_range(xa, i, j);
1497                         __check_store_range(xa, 128 + i, 128 + j);
1498                         __check_store_range(xa, 4095 + i, 4095 + j);
1499                         __check_store_range(xa, 4096 + i, 4096 + j);
1500                         __check_store_range(xa, 123456 + i, 123456 + j);
1501                         __check_store_range(xa, (1 << 24) + i, (1 << 24) + j);
1502                 }
1503         }
1504 }
1505
1506 #ifdef CONFIG_XARRAY_MULTI
1507 static void check_split_1(struct xarray *xa, unsigned long index,
1508                                                         unsigned int order)
1509 {
1510         XA_STATE(xas, xa, index);
1511         void *entry;
1512         unsigned int i = 0;
1513
1514         xa_store_order(xa, index, order, xa, GFP_KERNEL);
1515
1516         xas_split_alloc(&xas, xa, order, GFP_KERNEL);
1517         xas_lock(&xas);
1518         xas_split(&xas, xa, order);
1519         xas_unlock(&xas);
1520
1521         xa_for_each(xa, index, entry) {
1522                 XA_BUG_ON(xa, entry != xa);
1523                 i++;
1524         }
1525         XA_BUG_ON(xa, i != 1 << order);
1526
1527         xa_set_mark(xa, index, XA_MARK_0);
1528         XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));
1529
1530         xa_destroy(xa);
1531 }
1532
1533 static noinline void check_split(struct xarray *xa)
1534 {
1535         unsigned int order;
1536
1537         XA_BUG_ON(xa, !xa_empty(xa));
1538
1539         for (order = 1; order < 2 * XA_CHUNK_SHIFT; order++) {
1540                 check_split_1(xa, 0, order);
1541                 check_split_1(xa, 1UL << order, order);
1542                 check_split_1(xa, 3UL << order, order);
1543         }
1544 }
1545 #else
1546 static void check_split(struct xarray *xa) { }
1547 #endif
1548
1549 static void check_align_1(struct xarray *xa, char *name)
1550 {
1551         int i;
1552         unsigned int id;
1553         unsigned long index;
1554         void *entry;
1555
1556         for (i = 0; i < 8; i++) {
1557                 XA_BUG_ON(xa, xa_alloc(xa, &id, name + i, xa_limit_32b,
1558                                         GFP_KERNEL) != 0);
1559                 XA_BUG_ON(xa, id != i);
1560         }
1561         xa_for_each(xa, index, entry)
1562                 XA_BUG_ON(xa, xa_is_err(entry));
1563         xa_destroy(xa);
1564 }
1565
1566 /*
1567  * We should always be able to store without allocating memory after
1568  * reserving a slot.
1569  */
1570 static void check_align_2(struct xarray *xa, char *name)
1571 {
1572         int i;
1573
1574         XA_BUG_ON(xa, !xa_empty(xa));
1575
1576         for (i = 0; i < 8; i++) {
1577                 XA_BUG_ON(xa, xa_store(xa, 0, name + i, GFP_KERNEL) != NULL);
1578                 xa_erase(xa, 0);
1579         }
1580
1581         for (i = 0; i < 8; i++) {
1582                 XA_BUG_ON(xa, xa_reserve(xa, 0, GFP_KERNEL) != 0);
1583                 XA_BUG_ON(xa, xa_store(xa, 0, name + i, 0) != NULL);
1584                 xa_erase(xa, 0);
1585         }
1586
1587         XA_BUG_ON(xa, !xa_empty(xa));
1588 }
1589
1590 static noinline void check_align(struct xarray *xa)
1591 {
1592         char name[] = "Motorola 68000";
1593
1594         check_align_1(xa, name);
1595         check_align_1(xa, name + 1);
1596         check_align_1(xa, name + 2);
1597         check_align_1(xa, name + 3);
1598         check_align_2(xa, name);
1599 }
1600
1601 static LIST_HEAD(shadow_nodes);
1602
1603 static void test_update_node(struct xa_node *node)
1604 {
1605         if (node->count && node->count == node->nr_values) {
1606                 if (list_empty(&node->private_list))
1607                         list_add(&shadow_nodes, &node->private_list);
1608         } else {
1609                 if (!list_empty(&node->private_list))
1610                         list_del_init(&node->private_list);
1611         }
1612 }
1613
1614 static noinline void shadow_remove(struct xarray *xa)
1615 {
1616         struct xa_node *node;
1617
1618         xa_lock(xa);
1619         while ((node = list_first_entry_or_null(&shadow_nodes,
1620                                         struct xa_node, private_list))) {
1621                 XA_STATE(xas, node->array, 0);
1622                 XA_BUG_ON(xa, node->array != xa);
1623                 list_del_init(&node->private_list);
1624                 xas.xa_node = xa_parent_locked(node->array, node);
1625                 xas.xa_offset = node->offset;
1626                 xas.xa_shift = node->shift + XA_CHUNK_SHIFT;
1627                 xas_set_update(&xas, test_update_node);
1628                 xas_store(&xas, NULL);
1629         }
1630         xa_unlock(xa);
1631 }
1632
1633 static noinline void check_workingset(struct xarray *xa, unsigned long index)
1634 {
1635         XA_STATE(xas, xa, index);
1636         xas_set_update(&xas, test_update_node);
1637
1638         do {
1639                 xas_lock(&xas);
1640                 xas_store(&xas, xa_mk_value(0));
1641                 xas_next(&xas);
1642                 xas_store(&xas, xa_mk_value(1));
1643                 xas_unlock(&xas);
1644         } while (xas_nomem(&xas, GFP_KERNEL));
1645
1646         XA_BUG_ON(xa, list_empty(&shadow_nodes));
1647
1648         xas_lock(&xas);
1649         xas_next(&xas);
1650         xas_store(&xas, &xas);
1651         XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1652
1653         xas_store(&xas, xa_mk_value(2));
1654         xas_unlock(&xas);
1655         XA_BUG_ON(xa, list_empty(&shadow_nodes));
1656
1657         shadow_remove(xa);
1658         XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1659         XA_BUG_ON(xa, !xa_empty(xa));
1660 }
1661
1662 /*
1663  * Check that the pointer / value / sibling entries are accounted the
1664  * way we expect them to be.
1665  */
1666 static noinline void check_account(struct xarray *xa)
1667 {
1668 #ifdef CONFIG_XARRAY_MULTI
1669         unsigned int order;
1670
1671         for (order = 1; order < 12; order++) {
1672                 XA_STATE(xas, xa, 1 << order);
1673
1674                 xa_store_order(xa, 0, order, xa, GFP_KERNEL);
1675                 rcu_read_lock();
1676                 xas_load(&xas);
1677                 XA_BUG_ON(xa, xas.xa_node->count == 0);
1678                 XA_BUG_ON(xa, xas.xa_node->count > (1 << order));
1679                 XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1680                 rcu_read_unlock();
1681
1682                 xa_store_order(xa, 1 << order, order, xa_mk_index(1UL << order),
1683                                 GFP_KERNEL);
1684                 XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2);
1685
1686                 xa_erase(xa, 1 << order);
1687                 XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1688
1689                 xa_erase(xa, 0);
1690                 XA_BUG_ON(xa, !xa_empty(xa));
1691         }
1692 #endif
1693 }
1694
1695 static noinline void check_get_order(struct xarray *xa)
1696 {
1697         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;
1698         unsigned int order;
1699         unsigned long i, j;
1700
1701         for (i = 0; i < 3; i++)
1702                 XA_BUG_ON(xa, xa_get_order(xa, i) != 0);
1703
1704         for (order = 0; order < max_order; order++) {
1705                 for (i = 0; i < 10; i++) {
1706                         xa_store_order(xa, i << order, order,
1707                                         xa_mk_index(i << order), GFP_KERNEL);
1708                         for (j = i << order; j < (i + 1) << order; j++)
1709                                 XA_BUG_ON(xa, xa_get_order(xa, j) != order);
1710                         xa_erase(xa, i << order);
1711                 }
1712         }
1713 }
1714
1715 static noinline void check_destroy(struct xarray *xa)
1716 {
1717         unsigned long index;
1718
1719         XA_BUG_ON(xa, !xa_empty(xa));
1720
1721         /* Destroying an empty array is a no-op */
1722         xa_destroy(xa);
1723         XA_BUG_ON(xa, !xa_empty(xa));
1724
1725         /* Destroying an array with a single entry */
1726         for (index = 0; index < 1000; index++) {
1727                 xa_store_index(xa, index, GFP_KERNEL);
1728                 XA_BUG_ON(xa, xa_empty(xa));
1729                 xa_destroy(xa);
1730                 XA_BUG_ON(xa, !xa_empty(xa));
1731         }
1732
1733         /* Destroying an array with a single entry at ULONG_MAX */
1734         xa_store(xa, ULONG_MAX, xa, GFP_KERNEL);
1735         XA_BUG_ON(xa, xa_empty(xa));
1736         xa_destroy(xa);
1737         XA_BUG_ON(xa, !xa_empty(xa));
1738
1739 #ifdef CONFIG_XARRAY_MULTI
1740         /* Destroying an array with a multi-index entry */
1741         xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL);
1742         XA_BUG_ON(xa, xa_empty(xa));
1743         xa_destroy(xa);
1744         XA_BUG_ON(xa, !xa_empty(xa));
1745 #endif
1746 }
1747
1748 static DEFINE_XARRAY(array);
1749
1750 static int xarray_checks(void)
1751 {
1752         check_xa_err(&array);
1753         check_xas_retry(&array);
1754         check_xa_load(&array);
1755         check_xa_mark(&array);
1756         check_xa_shrink(&array);
1757         check_xas_erase(&array);
1758         check_insert(&array);
1759         check_cmpxchg(&array);
1760         check_reserve(&array);
1761         check_reserve(&xa0);
1762         check_multi_store(&array);
1763         check_get_order(&array);
1764         check_xa_alloc();
1765         check_find(&array);
1766         check_find_entry(&array);
1767         check_pause(&array);
1768         check_account(&array);
1769         check_destroy(&array);
1770         check_move(&array);
1771         check_create_range(&array);
1772         check_store_range(&array);
1773         check_store_iter(&array);
1774         check_align(&xa0);
1775         check_split(&array);
1776
1777         check_workingset(&array, 0);
1778         check_workingset(&array, 64);
1779         check_workingset(&array, 4096);
1780
1781         printk("XArray: %u of %u tests passed\n", tests_passed, tests_run);
1782         return (tests_run == tests_passed) ? 0 : -EINVAL;
1783 }
1784
1785 static void xarray_exit(void)
1786 {
1787 }
1788
1789 module_init(xarray_checks);
1790 module_exit(xarray_exit);
1791 MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
1792 MODULE_LICENSE("GPL");