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