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