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  * Author: Matthew Wilcox <willy@infradead.org>
   6  */
   7
   8 #include <linux/xarray.h>
   9 #include <linux/module.h>
  10
  11 static unsigned int tests_run;
  12 static unsigned int tests_passed;
  13
  14 #ifndef XA_DEBUG
  15 # ifdef __KERNEL__
  16 void xa_dump(const struct xarray *xa) { }
  17 # endif
  18 #undef XA_BUG_ON
  19 #define XA_BUG_ON(xa, x) do {                                   \
  20         tests_run++;                                            \
  21         if (x) {                                                \
  22                 printk("BUG at %s:%d\n", __func__, __LINE__);   \
  23                 xa_dump(xa);                                    \
  24                 dump_stack();                                   \
  25         } else {                                                \
  26                 tests_passed++;                                 \
  27         }                                                       \
  28 } while (0)
  29 #endif
  30
  31 static void *xa_store_index(struct xarray *xa, unsigned long index, gfp_t gfp)
  32 {
  33         return xa_store(xa, index, xa_mk_value(index & LONG_MAX), gfp);
  34 }
  35
  36 static void xa_alloc_index(struct xarray *xa, unsigned long index, gfp_t gfp)
  37 {
  38         u32 id = 0;
  39
  40         XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, xa_mk_value(index & LONG_MAX),
  41                                 gfp) != 0);
  42         XA_BUG_ON(xa, id != index);
  43 }
  44
  45 static void xa_erase_index(struct xarray *xa, unsigned long index)
  46 {
  47         XA_BUG_ON(xa, xa_erase(xa, index) != xa_mk_value(index & LONG_MAX));
  48         XA_BUG_ON(xa, xa_load(xa, index) != NULL);
  49 }
  50
  51 /*
  52  * If anyone needs this, please move it to xarray.c.  We have no current
  53  * users outside the test suite because all current multislot users want
  54  * to use the advanced API.
  55  */
  56 static void *xa_store_order(struct xarray *xa, unsigned long index,
  57                 unsigned order, void *entry, gfp_t gfp)
  58 {
  59         XA_STATE_ORDER(xas, xa, index, order);
  60         void *curr;
  61
  62         do {
  63                 xas_lock(&xas);
  64                 curr = xas_store(&xas, entry);
  65                 xas_unlock(&xas);
  66         } while (xas_nomem(&xas, gfp));
  67
  68         return curr;
  69 }
  70
  71 static noinline void check_xa_err(struct xarray *xa)
  72 {
  73         XA_BUG_ON(xa, xa_err(xa_store_index(xa, 0, GFP_NOWAIT)) != 0);
  74         XA_BUG_ON(xa, xa_err(xa_erase(xa, 0)) != 0);
  75 #ifndef __KERNEL__
  76         /* The kernel does not fail GFP_NOWAIT allocations */
  77         XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);
  78         XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);
  79 #endif
  80         XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_KERNEL)) != 0);
  81         XA_BUG_ON(xa, xa_err(xa_store(xa, 1, xa_mk_value(0), GFP_KERNEL)) != 0);
  82         XA_BUG_ON(xa, xa_err(xa_erase(xa, 1)) != 0);
  83 // kills the test-suite :-(
  84 //      XA_BUG_ON(xa, xa_err(xa_store(xa, 0, xa_mk_internal(0), 0)) != -EINVAL);
  85 }
  86
  87 static noinline void check_xas_retry(struct xarray *xa)
  88 {
  89         XA_STATE(xas, xa, 0);
  90         void *entry;
  91
  92         xa_store_index(xa, 0, GFP_KERNEL);
  93         xa_store_index(xa, 1, GFP_KERNEL);
  94
  95         rcu_read_lock();
  96         XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_value(0));
  97         xa_erase_index(xa, 1);
  98         XA_BUG_ON(xa, !xa_is_retry(xas_reload(&xas)));
  99         XA_BUG_ON(xa, xas_retry(&xas, NULL));
 100         XA_BUG_ON(xa, xas_retry(&xas, xa_mk_value(0)));
 101         xas_reset(&xas);
 102         XA_BUG_ON(xa, xas.xa_node != XAS_RESTART);
 103         XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
 104         XA_BUG_ON(xa, xas.xa_node != NULL);
 105
 106         XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
 107         XA_BUG_ON(xa, !xa_is_internal(xas_reload(&xas)));
 108         xas.xa_node = XAS_RESTART;
 109         XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
 110         rcu_read_unlock();
 111
 112         /* Make sure we can iterate through retry entries */
 113         xas_lock(&xas);
 114         xas_set(&xas, 0);
 115         xas_store(&xas, XA_RETRY_ENTRY);
 116         xas_set(&xas, 1);
 117         xas_store(&xas, XA_RETRY_ENTRY);
 118
 119         xas_set(&xas, 0);
 120         xas_for_each(&xas, entry, ULONG_MAX) {
 121                 xas_store(&xas, xa_mk_value(xas.xa_index));
 122         }
 123         xas_unlock(&xas);
 124
 125         xa_erase_index(xa, 0);
 126         xa_erase_index(xa, 1);
 127 }
 128
 129 static noinline void check_xa_load(struct xarray *xa)
 130 {
 131         unsigned long i, j;
 132
 133         for (i = 0; i < 1024; i++) {
 134                 for (j = 0; j < 1024; j++) {
 135                         void *entry = xa_load(xa, j);
 136                         if (j < i)
 137                                 XA_BUG_ON(xa, xa_to_value(entry) != j);
 138                         else
 139                                 XA_BUG_ON(xa, entry);
 140                 }
 141                 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
 142         }
 143
 144         for (i = 0; i < 1024; i++) {
 145                 for (j = 0; j < 1024; j++) {
 146                         void *entry = xa_load(xa, j);
 147                         if (j >= i)
 148                                 XA_BUG_ON(xa, xa_to_value(entry) != j);
 149                         else
 150                                 XA_BUG_ON(xa, entry);
 151                 }
 152                 xa_erase_index(xa, i);
 153         }
 154         XA_BUG_ON(xa, !xa_empty(xa));
 155 }
 156
 157 static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index)
 158 {
 159         unsigned int order;
 160         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 8 : 1;
 161
 162         /* NULL elements have no marks set */
 163         XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
 164         xa_set_mark(xa, index, XA_MARK_0);
 165         XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
 166
 167         /* Storing a pointer will not make a mark appear */
 168         XA_BUG_ON(xa, xa_store_index(xa, index, GFP_KERNEL) != NULL);
 169         XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
 170         xa_set_mark(xa, index, XA_MARK_0);
 171         XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));
 172
 173         /* Setting one mark will not set another mark */
 174         XA_BUG_ON(xa, xa_get_mark(xa, index + 1, XA_MARK_0));
 175         XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_1));
 176
 177         /* Storing NULL clears marks, and they can't be set again */
 178         xa_erase_index(xa, index);
 179         XA_BUG_ON(xa, !xa_empty(xa));
 180         XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
 181         xa_set_mark(xa, index, XA_MARK_0);
 182         XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
 183
 184         /*
 185          * Storing a multi-index entry over entries with marks gives the
 186          * entire entry the union of the marks
 187          */
 188         BUG_ON((index % 4) != 0);
 189         for (order = 2; order < max_order; order++) {
 190                 unsigned long base = round_down(index, 1UL << order);
 191                 unsigned long next = base + (1UL << order);
 192                 unsigned long i;
 193
 194                 XA_BUG_ON(xa, xa_store_index(xa, index + 1, GFP_KERNEL));
 195                 xa_set_mark(xa, index + 1, XA_MARK_0);
 196                 XA_BUG_ON(xa, xa_store_index(xa, index + 2, GFP_KERNEL));
 197                 xa_set_mark(xa, index + 2, XA_MARK_1);
 198                 XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL));
 199                 xa_store_order(xa, index, order, xa_mk_value(index),
 200                                 GFP_KERNEL);
 201                 for (i = base; i < next; i++) {
 202                         XA_STATE(xas, xa, i);
 203                         unsigned int seen = 0;
 204                         void *entry;
 205
 206                         XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
 207                         XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_1));
 208                         XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_2));
 209
 210                         /* We should see two elements in the array */
 211                         rcu_read_lock();
 212                         xas_for_each(&xas, entry, ULONG_MAX)
 213                                 seen++;
 214                         rcu_read_unlock();
 215                         XA_BUG_ON(xa, seen != 2);
 216
 217                         /* One of which is marked */
 218                         xas_set(&xas, 0);
 219                         seen = 0;
 220                         rcu_read_lock();
 221                         xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
 222                                 seen++;
 223                         rcu_read_unlock();
 224                         XA_BUG_ON(xa, seen != 1);
 225                 }
 226                 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_0));
 227                 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_1));
 228                 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_2));
 229                 xa_erase_index(xa, index);
 230                 xa_erase_index(xa, next);
 231                 XA_BUG_ON(xa, !xa_empty(xa));
 232         }
 233         XA_BUG_ON(xa, !xa_empty(xa));
 234 }
 235
 236 static noinline void check_xa_mark_2(struct xarray *xa)
 237 {
 238         XA_STATE(xas, xa, 0);
 239         unsigned long index;
 240         unsigned int count = 0;
 241         void *entry;
 242
 243         xa_store_index(xa, 0, GFP_KERNEL);
 244         xa_set_mark(xa, 0, XA_MARK_0);
 245         xas_lock(&xas);
 246         xas_load(&xas);
 247         xas_init_marks(&xas);
 248         xas_unlock(&xas);
 249         XA_BUG_ON(xa, !xa_get_mark(xa, 0, XA_MARK_0) == 0);
 250
 251         for (index = 3500; index < 4500; index++) {
 252                 xa_store_index(xa, index, GFP_KERNEL);
 253                 xa_set_mark(xa, index, XA_MARK_0);
 254         }
 255
 256         xas_reset(&xas);
 257         rcu_read_lock();
 258         xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
 259                 count++;
 260         rcu_read_unlock();
 261         XA_BUG_ON(xa, count != 1000);
 262
 263         xas_lock(&xas);
 264         xas_for_each(&xas, entry, ULONG_MAX) {
 265                 xas_init_marks(&xas);
 266                 XA_BUG_ON(xa, !xa_get_mark(xa, xas.xa_index, XA_MARK_0));
 267                 XA_BUG_ON(xa, !xas_get_mark(&xas, XA_MARK_0));
 268         }
 269         xas_unlock(&xas);
 270
 271         xa_destroy(xa);
 272 }
 273
 274 static noinline void check_xa_mark(struct xarray *xa)
 275 {
 276         unsigned long index;
 277
 278         for (index = 0; index < 16384; index += 4)
 279                 check_xa_mark_1(xa, index);
 280
 281         check_xa_mark_2(xa);
 282 }
 283
 284 static noinline void check_xa_shrink(struct xarray *xa)
 285 {
 286         XA_STATE(xas, xa, 1);
 287         struct xa_node *node;
 288         unsigned int order;
 289         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 15 : 1;
 290
 291         XA_BUG_ON(xa, !xa_empty(xa));
 292         XA_BUG_ON(xa, xa_store_index(xa, 0, GFP_KERNEL) != NULL);
 293         XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
 294
 295         /*
 296          * Check that erasing the entry at 1 shrinks the tree and properly
 297          * marks the node as being deleted.
 298          */
 299         xas_lock(&xas);
 300         XA_BUG_ON(xa, xas_load(&xas) != xa_mk_value(1));
 301         node = xas.xa_node;
 302         XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != xa_mk_value(0));
 303         XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
 304         XA_BUG_ON(xa, xa_load(xa, 1) != NULL);
 305         XA_BUG_ON(xa, xas.xa_node != XAS_BOUNDS);
 306         XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != XA_RETRY_ENTRY);
 307         XA_BUG_ON(xa, xas_load(&xas) != NULL);
 308         xas_unlock(&xas);
 309         XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
 310         xa_erase_index(xa, 0);
 311         XA_BUG_ON(xa, !xa_empty(xa));
 312
 313         for (order = 0; order < max_order; order++) {
 314                 unsigned long max = (1UL << order) - 1;
 315                 xa_store_order(xa, 0, order, xa_mk_value(0), GFP_KERNEL);
 316                 XA_BUG_ON(xa, xa_load(xa, max) != xa_mk_value(0));
 317                 XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);
 318                 rcu_read_lock();
 319                 node = xa_head(xa);
 320                 rcu_read_unlock();
 321                 XA_BUG_ON(xa, xa_store_index(xa, ULONG_MAX, GFP_KERNEL) !=
 322                                 NULL);
 323                 rcu_read_lock();
 324                 XA_BUG_ON(xa, xa_head(xa) == node);
 325                 rcu_read_unlock();
 326                 XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);
 327                 xa_erase_index(xa, ULONG_MAX);
 328                 XA_BUG_ON(xa, xa->xa_head != node);
 329                 xa_erase_index(xa, 0);
 330         }
 331 }
 332
 333 static noinline void check_cmpxchg(struct xarray *xa)
 334 {
 335         void *FIVE = xa_mk_value(5);
 336         void *SIX = xa_mk_value(6);
 337         void *LOTS = xa_mk_value(12345678);
 338
 339         XA_BUG_ON(xa, !xa_empty(xa));
 340         XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_KERNEL) != NULL);
 341         XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EEXIST);
 342         XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS);
 343         XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS);
 344         XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE);
 345         XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != NULL);
 346         XA_BUG_ON(xa, xa_cmpxchg(xa, 5, NULL, FIVE, GFP_KERNEL) != NULL);
 347         xa_erase_index(xa, 12345678);
 348         xa_erase_index(xa, 5);
 349         XA_BUG_ON(xa, !xa_empty(xa));
 350 }
 351
 352 static noinline void check_reserve(struct xarray *xa)
 353 {
 354         void *entry;
 355         unsigned long index = 0;
 356
 357         /* An array with a reserved entry is not empty */
 358         XA_BUG_ON(xa, !xa_empty(xa));
 359         xa_reserve(xa, 12345678, GFP_KERNEL);
 360         XA_BUG_ON(xa, xa_empty(xa));
 361         XA_BUG_ON(xa, xa_load(xa, 12345678));
 362         xa_release(xa, 12345678);
 363         XA_BUG_ON(xa, !xa_empty(xa));
 364
 365         /* Releasing a used entry does nothing */
 366         xa_reserve(xa, 12345678, GFP_KERNEL);
 367         XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL);
 368         xa_release(xa, 12345678);
 369         xa_erase_index(xa, 12345678);
 370         XA_BUG_ON(xa, !xa_empty(xa));
 371
 372         /* cmpxchg sees a reserved entry as NULL */
 373         xa_reserve(xa, 12345678, GFP_KERNEL);
 374         XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, NULL, xa_mk_value(12345678),
 375                                 GFP_NOWAIT) != NULL);
 376         xa_release(xa, 12345678);
 377         xa_erase_index(xa, 12345678);
 378         XA_BUG_ON(xa, !xa_empty(xa));
 379
 380         /* And so does xa_insert */
 381         xa_reserve(xa, 12345678, GFP_KERNEL);
 382         XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) != 0);
 383         xa_erase_index(xa, 12345678);
 384         XA_BUG_ON(xa, !xa_empty(xa));
 385
 386         /* Can iterate through a reserved entry */
 387         xa_store_index(xa, 5, GFP_KERNEL);
 388         xa_reserve(xa, 6, GFP_KERNEL);
 389         xa_store_index(xa, 7, GFP_KERNEL);
 390
 391         xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) {
 392                 XA_BUG_ON(xa, index != 5 && index != 7);
 393         }
 394         xa_destroy(xa);
 395 }
 396
 397 static noinline void check_xas_erase(struct xarray *xa)
 398 {
 399         XA_STATE(xas, xa, 0);
 400         void *entry;
 401         unsigned long i, j;
 402
 403         for (i = 0; i < 200; i++) {
 404                 for (j = i; j < 2 * i + 17; j++) {
 405                         xas_set(&xas, j);
 406                         do {
 407                                 xas_lock(&xas);
 408                                 xas_store(&xas, xa_mk_value(j));
 409                                 xas_unlock(&xas);
 410                         } while (xas_nomem(&xas, GFP_KERNEL));
 411                 }
 412
 413                 xas_set(&xas, ULONG_MAX);
 414                 do {
 415                         xas_lock(&xas);
 416                         xas_store(&xas, xa_mk_value(0));
 417                         xas_unlock(&xas);
 418                 } while (xas_nomem(&xas, GFP_KERNEL));
 419
 420                 xas_lock(&xas);
 421                 xas_store(&xas, NULL);
 422
 423                 xas_set(&xas, 0);
 424                 j = i;
 425                 xas_for_each(&xas, entry, ULONG_MAX) {
 426                         XA_BUG_ON(xa, entry != xa_mk_value(j));
 427                         xas_store(&xas, NULL);
 428                         j++;
 429                 }
 430                 xas_unlock(&xas);
 431                 XA_BUG_ON(xa, !xa_empty(xa));
 432         }
 433 }
 434
 435 #ifdef CONFIG_XARRAY_MULTI
 436 static noinline void check_multi_store_1(struct xarray *xa, unsigned long index,
 437                 unsigned int order)
 438 {
 439         XA_STATE(xas, xa, index);
 440         unsigned long min = index & ~((1UL << order) - 1);
 441         unsigned long max = min + (1UL << order);
 442
 443         xa_store_order(xa, index, order, xa_mk_value(index), GFP_KERNEL);
 444         XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_value(index));
 445         XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_value(index));
 446         XA_BUG_ON(xa, xa_load(xa, max) != NULL);
 447         XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
 448
 449         xas_lock(&xas);
 450         XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(min)) != xa_mk_value(index));
 451         xas_unlock(&xas);
 452         XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_value(min));
 453         XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_value(min));
 454         XA_BUG_ON(xa, xa_load(xa, max) != NULL);
 455         XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
 456
 457         xa_erase_index(xa, min);
 458         XA_BUG_ON(xa, !xa_empty(xa));
 459 }
 460
 461 static noinline void check_multi_store_2(struct xarray *xa, unsigned long index,
 462                 unsigned int order)
 463 {
 464         XA_STATE(xas, xa, index);
 465         xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL);
 466
 467         xas_lock(&xas);
 468         XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0));
 469         XA_BUG_ON(xa, xas.xa_index != index);
 470         XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
 471         xas_unlock(&xas);
 472         XA_BUG_ON(xa, !xa_empty(xa));
 473 }
 474 #endif
 475
 476 static noinline void check_multi_store(struct xarray *xa)
 477 {
 478 #ifdef CONFIG_XARRAY_MULTI
 479         unsigned long i, j, k;
 480         unsigned int max_order = (sizeof(long) == 4) ? 30 : 60;
 481
 482         /* Loading from any position returns the same value */
 483         xa_store_order(xa, 0, 1, xa_mk_value(0), GFP_KERNEL);
 484         XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
 485         XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
 486         XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
 487         rcu_read_lock();
 488         XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 2);
 489         XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
 490         rcu_read_unlock();
 491
 492         /* Storing adjacent to the value does not alter the value */
 493         xa_store(xa, 3, xa, GFP_KERNEL);
 494         XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
 495         XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
 496         XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
 497         rcu_read_lock();
 498         XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 3);
 499         XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
 500         rcu_read_unlock();
 501
 502         /* Overwriting multiple indexes works */
 503         xa_store_order(xa, 0, 2, xa_mk_value(1), GFP_KERNEL);
 504         XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(1));
 505         XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(1));
 506         XA_BUG_ON(xa, xa_load(xa, 2) != xa_mk_value(1));
 507         XA_BUG_ON(xa, xa_load(xa, 3) != xa_mk_value(1));
 508         XA_BUG_ON(xa, xa_load(xa, 4) != NULL);
 509         rcu_read_lock();
 510         XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 4);
 511         XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 4);
 512         rcu_read_unlock();
 513
 514         /* We can erase multiple values with a single store */
 515         xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL);
 516         XA_BUG_ON(xa, !xa_empty(xa));
 517
 518         /* Even when the first slot is empty but the others aren't */
 519         xa_store_index(xa, 1, GFP_KERNEL);
 520         xa_store_index(xa, 2, GFP_KERNEL);
 521         xa_store_order(xa, 0, 2, NULL, GFP_KERNEL);
 522         XA_BUG_ON(xa, !xa_empty(xa));
 523
 524         for (i = 0; i < max_order; i++) {
 525                 for (j = 0; j < max_order; j++) {
 526                         xa_store_order(xa, 0, i, xa_mk_value(i), GFP_KERNEL);
 527                         xa_store_order(xa, 0, j, xa_mk_value(j), GFP_KERNEL);
 528
 529                         for (k = 0; k < max_order; k++) {
 530                                 void *entry = xa_load(xa, (1UL << k) - 1);
 531                                 if ((i < k) && (j < k))
 532                                         XA_BUG_ON(xa, entry != NULL);
 533                                 else
 534                                         XA_BUG_ON(xa, entry != xa_mk_value(j));
 535                         }
 536
 537                         xa_erase(xa, 0);
 538                         XA_BUG_ON(xa, !xa_empty(xa));
 539                 }
 540         }
 541
 542         for (i = 0; i < 20; i++) {
 543                 check_multi_store_1(xa, 200, i);
 544                 check_multi_store_1(xa, 0, i);
 545                 check_multi_store_1(xa, (1UL << i) + 1, i);
 546         }
 547         check_multi_store_2(xa, 4095, 9);
 548 #endif
 549 }
 550
 551 static DEFINE_XARRAY_ALLOC(xa0);
 552
 553 static noinline void check_xa_alloc(void)
 554 {
 555         int i;
 556         u32 id;
 557
 558         /* An empty array should assign 0 to the first alloc */
 559         xa_alloc_index(&xa0, 0, GFP_KERNEL);
 560
 561         /* Erasing it should make the array empty again */
 562         xa_erase_index(&xa0, 0);
 563         XA_BUG_ON(&xa0, !xa_empty(&xa0));
 564
 565         /* And it should assign 0 again */
 566         xa_alloc_index(&xa0, 0, GFP_KERNEL);
 567
 568         /* The next assigned ID should be 1 */
 569         xa_alloc_index(&xa0, 1, GFP_KERNEL);
 570         xa_erase_index(&xa0, 1);
 571
 572         /* Storing a value should mark it used */
 573         xa_store_index(&xa0, 1, GFP_KERNEL);
 574         xa_alloc_index(&xa0, 2, GFP_KERNEL);
 575
 576         /* If we then erase 0, it should be free */
 577         xa_erase_index(&xa0, 0);
 578         xa_alloc_index(&xa0, 0, GFP_KERNEL);
 579
 580         xa_erase_index(&xa0, 1);
 581         xa_erase_index(&xa0, 2);
 582
 583         for (i = 1; i < 5000; i++) {
 584                 xa_alloc_index(&xa0, i, GFP_KERNEL);
 585         }
 586
 587         xa_destroy(&xa0);
 588
 589         id = 0xfffffffeU;
 590         XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0),
 591                                 GFP_KERNEL) != 0);
 592         XA_BUG_ON(&xa0, id != 0xfffffffeU);
 593         XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0),
 594                                 GFP_KERNEL) != 0);
 595         XA_BUG_ON(&xa0, id != 0xffffffffU);
 596         XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0),
 597                                 GFP_KERNEL) != -ENOSPC);
 598         XA_BUG_ON(&xa0, id != 0xffffffffU);
 599         xa_destroy(&xa0);
 600 }
 601
 602 static noinline void __check_store_iter(struct xarray *xa, unsigned long start,
 603                         unsigned int order, unsigned int present)
 604 {
 605         XA_STATE_ORDER(xas, xa, start, order);
 606         void *entry;
 607         unsigned int count = 0;
 608
 609 retry:
 610         xas_lock(&xas);
 611         xas_for_each_conflict(&xas, entry) {
 612                 XA_BUG_ON(xa, !xa_is_value(entry));
 613                 XA_BUG_ON(xa, entry < xa_mk_value(start));
 614                 XA_BUG_ON(xa, entry > xa_mk_value(start + (1UL << order) - 1));
 615                 count++;
 616         }
 617         xas_store(&xas, xa_mk_value(start));
 618         xas_unlock(&xas);
 619         if (xas_nomem(&xas, GFP_KERNEL)) {
 620                 count = 0;
 621                 goto retry;
 622         }
 623         XA_BUG_ON(xa, xas_error(&xas));
 624         XA_BUG_ON(xa, count != present);
 625         XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_value(start));
 626         XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) !=
 627                         xa_mk_value(start));
 628         xa_erase_index(xa, start);
 629 }
 630
 631 static noinline void check_store_iter(struct xarray *xa)
 632 {
 633         unsigned int i, j;
 634         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;
 635
 636         for (i = 0; i < max_order; i++) {
 637                 unsigned int min = 1 << i;
 638                 unsigned int max = (2 << i) - 1;
 639                 __check_store_iter(xa, 0, i, 0);
 640                 XA_BUG_ON(xa, !xa_empty(xa));
 641                 __check_store_iter(xa, min, i, 0);
 642                 XA_BUG_ON(xa, !xa_empty(xa));
 643
 644                 xa_store_index(xa, min, GFP_KERNEL);
 645                 __check_store_iter(xa, min, i, 1);
 646                 XA_BUG_ON(xa, !xa_empty(xa));
 647                 xa_store_index(xa, max, GFP_KERNEL);
 648                 __check_store_iter(xa, min, i, 1);
 649                 XA_BUG_ON(xa, !xa_empty(xa));
 650
 651                 for (j = 0; j < min; j++)
 652                         xa_store_index(xa, j, GFP_KERNEL);
 653                 __check_store_iter(xa, 0, i, min);
 654                 XA_BUG_ON(xa, !xa_empty(xa));
 655                 for (j = 0; j < min; j++)
 656                         xa_store_index(xa, min + j, GFP_KERNEL);
 657                 __check_store_iter(xa, min, i, min);
 658                 XA_BUG_ON(xa, !xa_empty(xa));
 659         }
 660 #ifdef CONFIG_XARRAY_MULTI
 661         xa_store_index(xa, 63, GFP_KERNEL);
 662         xa_store_index(xa, 65, GFP_KERNEL);
 663         __check_store_iter(xa, 64, 2, 1);
 664         xa_erase_index(xa, 63);
 665 #endif
 666         XA_BUG_ON(xa, !xa_empty(xa));
 667 }
 668
 669 static noinline void check_multi_find(struct xarray *xa)
 670 {
 671 #ifdef CONFIG_XARRAY_MULTI
 672         unsigned long index;
 673
 674         xa_store_order(xa, 12, 2, xa_mk_value(12), GFP_KERNEL);
 675         XA_BUG_ON(xa, xa_store_index(xa, 16, GFP_KERNEL) != NULL);
 676
 677         index = 0;
 678         XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
 679                         xa_mk_value(12));
 680         XA_BUG_ON(xa, index != 12);
 681         index = 13;
 682         XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
 683                         xa_mk_value(12));
 684         XA_BUG_ON(xa, (index < 12) || (index >= 16));
 685         XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) !=
 686                         xa_mk_value(16));
 687         XA_BUG_ON(xa, index != 16);
 688
 689         xa_erase_index(xa, 12);
 690         xa_erase_index(xa, 16);
 691         XA_BUG_ON(xa, !xa_empty(xa));
 692 #endif
 693 }
 694
 695 static noinline void check_multi_find_2(struct xarray *xa)
 696 {
 697         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1;
 698         unsigned int i, j;
 699         void *entry;
 700
 701         for (i = 0; i < max_order; i++) {
 702                 unsigned long index = 1UL << i;
 703                 for (j = 0; j < index; j++) {
 704                         XA_STATE(xas, xa, j + index);
 705                         xa_store_index(xa, index - 1, GFP_KERNEL);
 706                         xa_store_order(xa, index, i, xa_mk_value(index),
 707                                         GFP_KERNEL);
 708                         rcu_read_lock();
 709                         xas_for_each(&xas, entry, ULONG_MAX) {
 710                                 xa_erase_index(xa, index);
 711                         }
 712                         rcu_read_unlock();
 713                         xa_erase_index(xa, index - 1);
 714                         XA_BUG_ON(xa, !xa_empty(xa));
 715                 }
 716         }
 717 }
 718
 719 static noinline void check_find_1(struct xarray *xa)
 720 {
 721         unsigned long i, j, k;
 722
 723         XA_BUG_ON(xa, !xa_empty(xa));
 724
 725         /*
 726          * Check xa_find with all pairs between 0 and 99 inclusive,
 727          * starting at every index between 0 and 99
 728          */
 729         for (i = 0; i < 100; i++) {
 730                 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
 731                 xa_set_mark(xa, i, XA_MARK_0);
 732                 for (j = 0; j < i; j++) {
 733                         XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) !=
 734                                         NULL);
 735                         xa_set_mark(xa, j, XA_MARK_0);
 736                         for (k = 0; k < 100; k++) {
 737                                 unsigned long index = k;
 738                                 void *entry = xa_find(xa, &index, ULONG_MAX,
 739                                                                 XA_PRESENT);
 740                                 if (k <= j)
 741                                         XA_BUG_ON(xa, index != j);
 742                                 else if (k <= i)
 743                                         XA_BUG_ON(xa, index != i);
 744                                 else
 745                                         XA_BUG_ON(xa, entry != NULL);
 746
 747                                 index = k;
 748                                 entry = xa_find(xa, &index, ULONG_MAX,
 749                                                                 XA_MARK_0);
 750                                 if (k <= j)
 751                                         XA_BUG_ON(xa, index != j);
 752                                 else if (k <= i)
 753                                         XA_BUG_ON(xa, index != i);
 754                                 else
 755                                         XA_BUG_ON(xa, entry != NULL);
 756                         }
 757                         xa_erase_index(xa, j);
 758                         XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0));
 759                         XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
 760                 }
 761                 xa_erase_index(xa, i);
 762                 XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0));
 763         }
 764         XA_BUG_ON(xa, !xa_empty(xa));
 765 }
 766
 767 static noinline void check_find_2(struct xarray *xa)
 768 {
 769         void *entry;
 770         unsigned long i, j, index = 0;
 771
 772         xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) {
 773                 XA_BUG_ON(xa, true);
 774         }
 775
 776         for (i = 0; i < 1024; i++) {
 777                 xa_store_index(xa, index, GFP_KERNEL);
 778                 j = 0;
 779                 index = 0;
 780                 xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) {
 781                         XA_BUG_ON(xa, xa_mk_value(index) != entry);
 782                         XA_BUG_ON(xa, index != j++);
 783                 }
 784         }
 785
 786         xa_destroy(xa);
 787 }
 788
 789 static noinline void check_find(struct xarray *xa)
 790 {
 791         check_find_1(xa);
 792         check_find_2(xa);
 793         check_multi_find(xa);
 794         check_multi_find_2(xa);
 795 }
 796
 797 /* See find_swap_entry() in mm/shmem.c */
 798 static noinline unsigned long xa_find_entry(struct xarray *xa, void *item)
 799 {
 800         XA_STATE(xas, xa, 0);
 801         unsigned int checked = 0;
 802         void *entry;
 803
 804         rcu_read_lock();
 805         xas_for_each(&xas, entry, ULONG_MAX) {
 806                 if (xas_retry(&xas, entry))
 807                         continue;
 808                 if (entry == item)
 809                         break;
 810                 checked++;
 811                 if ((checked % 4) != 0)
 812                         continue;
 813                 xas_pause(&xas);
 814         }
 815         rcu_read_unlock();
 816
 817         return entry ? xas.xa_index : -1;
 818 }
 819
 820 static noinline void check_find_entry(struct xarray *xa)
 821 {
 822 #ifdef CONFIG_XARRAY_MULTI
 823         unsigned int order;
 824         unsigned long offset, index;
 825
 826         for (order = 0; order < 20; order++) {
 827                 for (offset = 0; offset < (1UL << (order + 3));
 828                      offset += (1UL << order)) {
 829                         for (index = 0; index < (1UL << (order + 5));
 830                              index += (1UL << order)) {
 831                                 xa_store_order(xa, index, order,
 832                                                 xa_mk_value(index), GFP_KERNEL);
 833                                 XA_BUG_ON(xa, xa_load(xa, index) !=
 834                                                 xa_mk_value(index));
 835                                 XA_BUG_ON(xa, xa_find_entry(xa,
 836                                                 xa_mk_value(index)) != index);
 837                         }
 838                         XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
 839                         xa_destroy(xa);
 840                 }
 841         }
 842 #endif
 843
 844         XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
 845         xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
 846         XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
 847         XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_value(LONG_MAX)) != -1);
 848         xa_erase_index(xa, ULONG_MAX);
 849         XA_BUG_ON(xa, !xa_empty(xa));
 850 }
 851
 852 static noinline void check_move_small(struct xarray *xa, unsigned long idx)
 853 {
 854         XA_STATE(xas, xa, 0);
 855         unsigned long i;
 856
 857         xa_store_index(xa, 0, GFP_KERNEL);
 858         xa_store_index(xa, idx, GFP_KERNEL);
 859
 860         rcu_read_lock();
 861         for (i = 0; i < idx * 4; i++) {
 862                 void *entry = xas_next(&xas);
 863                 if (i <= idx)
 864                         XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
 865                 XA_BUG_ON(xa, xas.xa_index != i);
 866                 if (i == 0 || i == idx)
 867                         XA_BUG_ON(xa, entry != xa_mk_value(i));
 868                 else
 869                         XA_BUG_ON(xa, entry != NULL);
 870         }
 871         xas_next(&xas);
 872         XA_BUG_ON(xa, xas.xa_index != i);
 873
 874         do {
 875                 void *entry = xas_prev(&xas);
 876                 i--;
 877                 if (i <= idx)
 878                         XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
 879                 XA_BUG_ON(xa, xas.xa_index != i);
 880                 if (i == 0 || i == idx)
 881                         XA_BUG_ON(xa, entry != xa_mk_value(i));
 882                 else
 883                         XA_BUG_ON(xa, entry != NULL);
 884         } while (i > 0);
 885
 886         xas_set(&xas, ULONG_MAX);
 887         XA_BUG_ON(xa, xas_next(&xas) != NULL);
 888         XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
 889         XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0));
 890         XA_BUG_ON(xa, xas.xa_index != 0);
 891         XA_BUG_ON(xa, xas_prev(&xas) != NULL);
 892         XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
 893         rcu_read_unlock();
 894
 895         xa_erase_index(xa, 0);
 896         xa_erase_index(xa, idx);
 897         XA_BUG_ON(xa, !xa_empty(xa));
 898 }
 899
 900 static noinline void check_move(struct xarray *xa)
 901 {
 902         XA_STATE(xas, xa, (1 << 16) - 1);
 903         unsigned long i;
 904
 905         for (i = 0; i < (1 << 16); i++)
 906                 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
 907
 908         rcu_read_lock();
 909         do {
 910                 void *entry = xas_prev(&xas);
 911                 i--;
 912                 XA_BUG_ON(xa, entry != xa_mk_value(i));
 913                 XA_BUG_ON(xa, i != xas.xa_index);
 914         } while (i != 0);
 915
 916         XA_BUG_ON(xa, xas_prev(&xas) != NULL);
 917         XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
 918
 919         do {
 920                 void *entry = xas_next(&xas);
 921                 XA_BUG_ON(xa, entry != xa_mk_value(i));
 922                 XA_BUG_ON(xa, i != xas.xa_index);
 923                 i++;
 924         } while (i < (1 << 16));
 925         rcu_read_unlock();
 926
 927         for (i = (1 << 8); i < (1 << 15); i++)
 928                 xa_erase_index(xa, i);
 929
 930         i = xas.xa_index;
 931
 932         rcu_read_lock();
 933         do {
 934                 void *entry = xas_prev(&xas);
 935                 i--;
 936                 if ((i < (1 << 8)) || (i >= (1 << 15)))
 937                         XA_BUG_ON(xa, entry != xa_mk_value(i));
 938                 else
 939                         XA_BUG_ON(xa, entry != NULL);
 940                 XA_BUG_ON(xa, i != xas.xa_index);
 941         } while (i != 0);
 942
 943         XA_BUG_ON(xa, xas_prev(&xas) != NULL);
 944         XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
 945
 946         do {
 947                 void *entry = xas_next(&xas);
 948                 if ((i < (1 << 8)) || (i >= (1 << 15)))
 949                         XA_BUG_ON(xa, entry != xa_mk_value(i));
 950                 else
 951                         XA_BUG_ON(xa, entry != NULL);
 952                 XA_BUG_ON(xa, i != xas.xa_index);
 953                 i++;
 954         } while (i < (1 << 16));
 955         rcu_read_unlock();
 956
 957         xa_destroy(xa);
 958
 959         for (i = 0; i < 16; i++)
 960                 check_move_small(xa, 1UL << i);
 961
 962         for (i = 2; i < 16; i++)
 963                 check_move_small(xa, (1UL << i) - 1);
 964 }
 965
 966 static noinline void xa_store_many_order(struct xarray *xa,
 967                 unsigned long index, unsigned order)
 968 {
 969         XA_STATE_ORDER(xas, xa, index, order);
 970         unsigned int i = 0;
 971
 972         do {
 973                 xas_lock(&xas);
 974                 XA_BUG_ON(xa, xas_find_conflict(&xas));
 975                 xas_create_range(&xas);
 976                 if (xas_error(&xas))
 977                         goto unlock;
 978                 for (i = 0; i < (1U << order); i++) {
 979                         XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(index + i)));
 980                         xas_next(&xas);
 981                 }
 982 unlock:
 983                 xas_unlock(&xas);
 984         } while (xas_nomem(&xas, GFP_KERNEL));
 985
 986         XA_BUG_ON(xa, xas_error(&xas));
 987 }
 988
 989 static noinline void check_create_range_1(struct xarray *xa,
 990                 unsigned long index, unsigned order)
 991 {
 992         unsigned long i;
 993
 994         xa_store_many_order(xa, index, order);
 995         for (i = index; i < index + (1UL << order); i++)
 996                 xa_erase_index(xa, i);
 997         XA_BUG_ON(xa, !xa_empty(xa));
 998 }
 999
1000 static noinline void check_create_range_2(struct xarray *xa, unsigned order)
1001 {
1002         unsigned long i;
1003         unsigned long nr = 1UL << order;
1004
1005         for (i = 0; i < nr * nr; i += nr)
1006                 xa_store_many_order(xa, i, order);
1007         for (i = 0; i < nr * nr; i++)
1008                 xa_erase_index(xa, i);
1009         XA_BUG_ON(xa, !xa_empty(xa));
1010 }
1011
1012 static noinline void check_create_range_3(void)
1013 {
1014         XA_STATE(xas, NULL, 0);
1015         xas_set_err(&xas, -EEXIST);
1016         xas_create_range(&xas);
1017         XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST);
1018 }
1019
1020 static noinline void check_create_range_4(struct xarray *xa,
1021                 unsigned long index, unsigned order)
1022 {
1023         XA_STATE_ORDER(xas, xa, index, order);
1024         unsigned long base = xas.xa_index;
1025         unsigned long i = 0;
1026
1027         xa_store_index(xa, index, GFP_KERNEL);
1028         do {
1029                 xas_lock(&xas);
1030                 xas_create_range(&xas);
1031                 if (xas_error(&xas))
1032                         goto unlock;
1033                 for (i = 0; i < (1UL << order); i++) {
1034                         void *old = xas_store(&xas, xa_mk_value(base + i));
1035                         if (xas.xa_index == index)
1036                                 XA_BUG_ON(xa, old != xa_mk_value(base + i));
1037                         else
1038                                 XA_BUG_ON(xa, old != NULL);
1039                         xas_next(&xas);
1040                 }
1041 unlock:
1042                 xas_unlock(&xas);
1043         } while (xas_nomem(&xas, GFP_KERNEL));
1044
1045         XA_BUG_ON(xa, xas_error(&xas));
1046
1047         for (i = base; i < base + (1UL << order); i++)
1048                 xa_erase_index(xa, i);
1049         XA_BUG_ON(xa, !xa_empty(xa));
1050 }
1051
1052 static noinline void check_create_range(struct xarray *xa)
1053 {
1054         unsigned int order;
1055         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1;
1056
1057         for (order = 0; order < max_order; order++) {
1058                 check_create_range_1(xa, 0, order);
1059                 check_create_range_1(xa, 1U << order, order);
1060                 check_create_range_1(xa, 2U << order, order);
1061                 check_create_range_1(xa, 3U << order, order);
1062                 check_create_range_1(xa, 1U << 24, order);
1063                 if (order < 10)
1064                         check_create_range_2(xa, order);
1065
1066                 check_create_range_4(xa, 0, order);
1067                 check_create_range_4(xa, 1U << order, order);
1068                 check_create_range_4(xa, 2U << order, order);
1069                 check_create_range_4(xa, 3U << order, order);
1070                 check_create_range_4(xa, 1U << 24, order);
1071
1072                 check_create_range_4(xa, 1, order);
1073                 check_create_range_4(xa, (1U << order) + 1, order);
1074                 check_create_range_4(xa, (2U << order) + 1, order);
1075                 check_create_range_4(xa, (2U << order) - 1, order);
1076                 check_create_range_4(xa, (3U << order) + 1, order);
1077                 check_create_range_4(xa, (3U << order) - 1, order);
1078                 check_create_range_4(xa, (1U << 24) + 1, order);
1079         }
1080
1081         check_create_range_3();
1082 }
1083
1084 static noinline void __check_store_range(struct xarray *xa, unsigned long first,
1085                 unsigned long last)
1086 {
1087 #ifdef CONFIG_XARRAY_MULTI
1088         xa_store_range(xa, first, last, xa_mk_value(first), GFP_KERNEL);
1089
1090         XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_value(first));
1091         XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_value(first));
1092         XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL);
1093         XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL);
1094
1095         xa_store_range(xa, first, last, NULL, GFP_KERNEL);
1096 #endif
1097
1098         XA_BUG_ON(xa, !xa_empty(xa));
1099 }
1100
1101 static noinline void check_store_range(struct xarray *xa)
1102 {
1103         unsigned long i, j;
1104
1105         for (i = 0; i < 128; i++) {
1106                 for (j = i; j < 128; j++) {
1107                         __check_store_range(xa, i, j);
1108                         __check_store_range(xa, 128 + i, 128 + j);
1109                         __check_store_range(xa, 4095 + i, 4095 + j);
1110                         __check_store_range(xa, 4096 + i, 4096 + j);
1111                         __check_store_range(xa, 123456 + i, 123456 + j);
1112                         __check_store_range(xa, (1 << 24) + i, (1 << 24) + j);
1113                 }
1114         }
1115 }
1116
1117 static LIST_HEAD(shadow_nodes);
1118
1119 static void test_update_node(struct xa_node *node)
1120 {
1121         if (node->count && node->count == node->nr_values) {
1122                 if (list_empty(&node->private_list))
1123                         list_add(&shadow_nodes, &node->private_list);
1124         } else {
1125                 if (!list_empty(&node->private_list))
1126                         list_del_init(&node->private_list);
1127         }
1128 }
1129
1130 static noinline void shadow_remove(struct xarray *xa)
1131 {
1132         struct xa_node *node;
1133
1134         xa_lock(xa);
1135         while ((node = list_first_entry_or_null(&shadow_nodes,
1136                                         struct xa_node, private_list))) {
1137                 XA_STATE(xas, node->array, 0);
1138                 XA_BUG_ON(xa, node->array != xa);
1139                 list_del_init(&node->private_list);
1140                 xas.xa_node = xa_parent_locked(node->array, node);
1141                 xas.xa_offset = node->offset;
1142                 xas.xa_shift = node->shift + XA_CHUNK_SHIFT;
1143                 xas_set_update(&xas, test_update_node);
1144                 xas_store(&xas, NULL);
1145         }
1146         xa_unlock(xa);
1147 }
1148
1149 static noinline void check_workingset(struct xarray *xa, unsigned long index)
1150 {
1151         XA_STATE(xas, xa, index);
1152         xas_set_update(&xas, test_update_node);
1153
1154         do {
1155                 xas_lock(&xas);
1156                 xas_store(&xas, xa_mk_value(0));
1157                 xas_next(&xas);
1158                 xas_store(&xas, xa_mk_value(1));
1159                 xas_unlock(&xas);
1160         } while (xas_nomem(&xas, GFP_KERNEL));
1161
1162         XA_BUG_ON(xa, list_empty(&shadow_nodes));
1163
1164         xas_lock(&xas);
1165         xas_next(&xas);
1166         xas_store(&xas, &xas);
1167         XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1168
1169         xas_store(&xas, xa_mk_value(2));
1170         xas_unlock(&xas);
1171         XA_BUG_ON(xa, list_empty(&shadow_nodes));
1172
1173         shadow_remove(xa);
1174         XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1175         XA_BUG_ON(xa, !xa_empty(xa));
1176 }
1177
1178 /*
1179  * Check that the pointer / value / sibling entries are accounted the
1180  * way we expect them to be.
1181  */
1182 static noinline void check_account(struct xarray *xa)
1183 {
1184 #ifdef CONFIG_XARRAY_MULTI
1185         unsigned int order;
1186
1187         for (order = 1; order < 12; order++) {
1188                 XA_STATE(xas, xa, 1 << order);
1189
1190                 xa_store_order(xa, 0, order, xa, GFP_KERNEL);
1191                 rcu_read_lock();
1192                 xas_load(&xas);
1193                 XA_BUG_ON(xa, xas.xa_node->count == 0);
1194                 XA_BUG_ON(xa, xas.xa_node->count > (1 << order));
1195                 XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1196                 rcu_read_unlock();
1197
1198                 xa_store_order(xa, 1 << order, order, xa_mk_value(1 << order),
1199                                 GFP_KERNEL);
1200                 XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2);
1201
1202                 xa_erase(xa, 1 << order);
1203                 XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1204
1205                 xa_erase(xa, 0);
1206                 XA_BUG_ON(xa, !xa_empty(xa));
1207         }
1208 #endif
1209 }
1210
1211 static noinline void check_destroy(struct xarray *xa)
1212 {
1213         unsigned long index;
1214
1215         XA_BUG_ON(xa, !xa_empty(xa));
1216
1217         /* Destroying an empty array is a no-op */
1218         xa_destroy(xa);
1219         XA_BUG_ON(xa, !xa_empty(xa));
1220
1221         /* Destroying an array with a single entry */
1222         for (index = 0; index < 1000; index++) {
1223                 xa_store_index(xa, index, GFP_KERNEL);
1224                 XA_BUG_ON(xa, xa_empty(xa));
1225                 xa_destroy(xa);
1226                 XA_BUG_ON(xa, !xa_empty(xa));
1227         }
1228
1229         /* Destroying an array with a single entry at ULONG_MAX */
1230         xa_store(xa, ULONG_MAX, xa, GFP_KERNEL);
1231         XA_BUG_ON(xa, xa_empty(xa));
1232         xa_destroy(xa);
1233         XA_BUG_ON(xa, !xa_empty(xa));
1234
1235 #ifdef CONFIG_XARRAY_MULTI
1236         /* Destroying an array with a multi-index entry */
1237         xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL);
1238         XA_BUG_ON(xa, xa_empty(xa));
1239         xa_destroy(xa);
1240         XA_BUG_ON(xa, !xa_empty(xa));
1241 #endif
1242 }
1243
1244 static DEFINE_XARRAY(array);
1245
1246 static int xarray_checks(void)
1247 {
1248         check_xa_err(&array);
1249         check_xas_retry(&array);
1250         check_xa_load(&array);
1251         check_xa_mark(&array);
1252         check_xa_shrink(&array);
1253         check_xas_erase(&array);
1254         check_cmpxchg(&array);
1255         check_reserve(&array);
1256         check_multi_store(&array);
1257         check_xa_alloc();
1258         check_find(&array);
1259         check_find_entry(&array);
1260         check_account(&array);
1261         check_destroy(&array);
1262         check_move(&array);
1263         check_create_range(&array);
1264         check_store_range(&array);
1265         check_store_iter(&array);
1266
1267         check_workingset(&array, 0);
1268         check_workingset(&array, 64);
1269         check_workingset(&array, 4096);
1270
1271         printk("XArray: %u of %u tests passed\n", tests_passed, tests_run);
1272         return (tests_run == tests_passed) ? 0 : -EINVAL;
1273 }
1274
1275 static void xarray_exit(void)
1276 {
1277 }
1278
1279 module_init(xarray_checks);
1280 module_exit(xarray_exit);
1281 MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
1282 MODULE_LICENSE("GPL");