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 = 0;
  44
  45         XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, xa_mk_index(index),
  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         id = 0xfffffffeU;
 644         XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, xa_mk_index(id),
 645                                 GFP_KERNEL) != 0);
 646         XA_BUG_ON(xa, id != 0xfffffffeU);
 647         XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, xa_mk_index(id),
 648                                 GFP_KERNEL) != 0);
 649         XA_BUG_ON(xa, id != 0xffffffffU);
 650         XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, xa_mk_index(id),
 651                                 GFP_KERNEL) != -ENOSPC);
 652         XA_BUG_ON(xa, id != 0xffffffffU);
 653         xa_destroy(xa);
 654
 655         id = 10;
 656         XA_BUG_ON(xa, xa_alloc(xa, &id, 5, xa_mk_index(id),
 657                                 GFP_KERNEL) != -ENOSPC);
 658         XA_BUG_ON(xa, xa_store_index(xa, 3, GFP_KERNEL) != 0);
 659         XA_BUG_ON(xa, xa_alloc(xa, &id, 5, xa_mk_index(id),
 660                                 GFP_KERNEL) != -ENOSPC);
 661         xa_erase_index(xa, 3);
 662         XA_BUG_ON(xa, !xa_empty(xa));
 663 }
 664
 665 static DEFINE_XARRAY_ALLOC(xa0);
 666 static DEFINE_XARRAY_ALLOC1(xa1);
 667
 668 static noinline void check_xa_alloc(void)
 669 {
 670         check_xa_alloc_1(&xa0, 0);
 671         check_xa_alloc_1(&xa1, 1);
 672 }
 673
 674 static noinline void __check_store_iter(struct xarray *xa, unsigned long start,
 675                         unsigned int order, unsigned int present)
 676 {
 677         XA_STATE_ORDER(xas, xa, start, order);
 678         void *entry;
 679         unsigned int count = 0;
 680
 681 retry:
 682         xas_lock(&xas);
 683         xas_for_each_conflict(&xas, entry) {
 684                 XA_BUG_ON(xa, !xa_is_value(entry));
 685                 XA_BUG_ON(xa, entry < xa_mk_index(start));
 686                 XA_BUG_ON(xa, entry > xa_mk_index(start + (1UL << order) - 1));
 687                 count++;
 688         }
 689         xas_store(&xas, xa_mk_index(start));
 690         xas_unlock(&xas);
 691         if (xas_nomem(&xas, GFP_KERNEL)) {
 692                 count = 0;
 693                 goto retry;
 694         }
 695         XA_BUG_ON(xa, xas_error(&xas));
 696         XA_BUG_ON(xa, count != present);
 697         XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_index(start));
 698         XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) !=
 699                         xa_mk_index(start));
 700         xa_erase_index(xa, start);
 701 }
 702
 703 static noinline void check_store_iter(struct xarray *xa)
 704 {
 705         unsigned int i, j;
 706         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;
 707
 708         for (i = 0; i < max_order; i++) {
 709                 unsigned int min = 1 << i;
 710                 unsigned int max = (2 << i) - 1;
 711                 __check_store_iter(xa, 0, i, 0);
 712                 XA_BUG_ON(xa, !xa_empty(xa));
 713                 __check_store_iter(xa, min, i, 0);
 714                 XA_BUG_ON(xa, !xa_empty(xa));
 715
 716                 xa_store_index(xa, min, GFP_KERNEL);
 717                 __check_store_iter(xa, min, i, 1);
 718                 XA_BUG_ON(xa, !xa_empty(xa));
 719                 xa_store_index(xa, max, GFP_KERNEL);
 720                 __check_store_iter(xa, min, i, 1);
 721                 XA_BUG_ON(xa, !xa_empty(xa));
 722
 723                 for (j = 0; j < min; j++)
 724                         xa_store_index(xa, j, GFP_KERNEL);
 725                 __check_store_iter(xa, 0, i, min);
 726                 XA_BUG_ON(xa, !xa_empty(xa));
 727                 for (j = 0; j < min; j++)
 728                         xa_store_index(xa, min + j, GFP_KERNEL);
 729                 __check_store_iter(xa, min, i, min);
 730                 XA_BUG_ON(xa, !xa_empty(xa));
 731         }
 732 #ifdef CONFIG_XARRAY_MULTI
 733         xa_store_index(xa, 63, GFP_KERNEL);
 734         xa_store_index(xa, 65, GFP_KERNEL);
 735         __check_store_iter(xa, 64, 2, 1);
 736         xa_erase_index(xa, 63);
 737 #endif
 738         XA_BUG_ON(xa, !xa_empty(xa));
 739 }
 740
 741 static noinline void check_multi_find(struct xarray *xa)
 742 {
 743 #ifdef CONFIG_XARRAY_MULTI
 744         unsigned long index;
 745
 746         xa_store_order(xa, 12, 2, xa_mk_value(12), GFP_KERNEL);
 747         XA_BUG_ON(xa, xa_store_index(xa, 16, GFP_KERNEL) != NULL);
 748
 749         index = 0;
 750         XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
 751                         xa_mk_value(12));
 752         XA_BUG_ON(xa, index != 12);
 753         index = 13;
 754         XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
 755                         xa_mk_value(12));
 756         XA_BUG_ON(xa, (index < 12) || (index >= 16));
 757         XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) !=
 758                         xa_mk_value(16));
 759         XA_BUG_ON(xa, index != 16);
 760
 761         xa_erase_index(xa, 12);
 762         xa_erase_index(xa, 16);
 763         XA_BUG_ON(xa, !xa_empty(xa));
 764 #endif
 765 }
 766
 767 static noinline void check_multi_find_2(struct xarray *xa)
 768 {
 769         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1;
 770         unsigned int i, j;
 771         void *entry;
 772
 773         for (i = 0; i < max_order; i++) {
 774                 unsigned long index = 1UL << i;
 775                 for (j = 0; j < index; j++) {
 776                         XA_STATE(xas, xa, j + index);
 777                         xa_store_index(xa, index - 1, GFP_KERNEL);
 778                         xa_store_order(xa, index, i, xa_mk_index(index),
 779                                         GFP_KERNEL);
 780                         rcu_read_lock();
 781                         xas_for_each(&xas, entry, ULONG_MAX) {
 782                                 xa_erase_index(xa, index);
 783                         }
 784                         rcu_read_unlock();
 785                         xa_erase_index(xa, index - 1);
 786                         XA_BUG_ON(xa, !xa_empty(xa));
 787                 }
 788         }
 789 }
 790
 791 static noinline void check_find_1(struct xarray *xa)
 792 {
 793         unsigned long i, j, k;
 794
 795         XA_BUG_ON(xa, !xa_empty(xa));
 796
 797         /*
 798          * Check xa_find with all pairs between 0 and 99 inclusive,
 799          * starting at every index between 0 and 99
 800          */
 801         for (i = 0; i < 100; i++) {
 802                 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
 803                 xa_set_mark(xa, i, XA_MARK_0);
 804                 for (j = 0; j < i; j++) {
 805                         XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) !=
 806                                         NULL);
 807                         xa_set_mark(xa, j, XA_MARK_0);
 808                         for (k = 0; k < 100; k++) {
 809                                 unsigned long index = k;
 810                                 void *entry = xa_find(xa, &index, ULONG_MAX,
 811                                                                 XA_PRESENT);
 812                                 if (k <= j)
 813                                         XA_BUG_ON(xa, index != j);
 814                                 else if (k <= i)
 815                                         XA_BUG_ON(xa, index != i);
 816                                 else
 817                                         XA_BUG_ON(xa, entry != NULL);
 818
 819                                 index = k;
 820                                 entry = xa_find(xa, &index, ULONG_MAX,
 821                                                                 XA_MARK_0);
 822                                 if (k <= j)
 823                                         XA_BUG_ON(xa, index != j);
 824                                 else if (k <= i)
 825                                         XA_BUG_ON(xa, index != i);
 826                                 else
 827                                         XA_BUG_ON(xa, entry != NULL);
 828                         }
 829                         xa_erase_index(xa, j);
 830                         XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0));
 831                         XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
 832                 }
 833                 xa_erase_index(xa, i);
 834                 XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0));
 835         }
 836         XA_BUG_ON(xa, !xa_empty(xa));
 837 }
 838
 839 static noinline void check_find_2(struct xarray *xa)
 840 {
 841         void *entry;
 842         unsigned long i, j, index;
 843
 844         xa_for_each(xa, index, entry) {
 845                 XA_BUG_ON(xa, true);
 846         }
 847
 848         for (i = 0; i < 1024; i++) {
 849                 xa_store_index(xa, index, GFP_KERNEL);
 850                 j = 0;
 851                 xa_for_each(xa, index, entry) {
 852                         XA_BUG_ON(xa, xa_mk_index(index) != entry);
 853                         XA_BUG_ON(xa, index != j++);
 854                 }
 855         }
 856
 857         xa_destroy(xa);
 858 }
 859
 860 static noinline void check_find_3(struct xarray *xa)
 861 {
 862         XA_STATE(xas, xa, 0);
 863         unsigned long i, j, k;
 864         void *entry;
 865
 866         for (i = 0; i < 100; i++) {
 867                 for (j = 0; j < 100; j++) {
 868                         rcu_read_lock();
 869                         for (k = 0; k < 100; k++) {
 870                                 xas_set(&xas, j);
 871                                 xas_for_each_marked(&xas, entry, k, XA_MARK_0)
 872                                         ;
 873                                 if (j > k)
 874                                         XA_BUG_ON(xa,
 875                                                 xas.xa_node != XAS_RESTART);
 876                         }
 877                         rcu_read_unlock();
 878                 }
 879                 xa_store_index(xa, i, GFP_KERNEL);
 880                 xa_set_mark(xa, i, XA_MARK_0);
 881         }
 882         xa_destroy(xa);
 883 }
 884
 885 static noinline void check_find(struct xarray *xa)
 886 {
 887         check_find_1(xa);
 888         check_find_2(xa);
 889         check_find_3(xa);
 890         check_multi_find(xa);
 891         check_multi_find_2(xa);
 892 }
 893
 894 /* See find_swap_entry() in mm/shmem.c */
 895 static noinline unsigned long xa_find_entry(struct xarray *xa, void *item)
 896 {
 897         XA_STATE(xas, xa, 0);
 898         unsigned int checked = 0;
 899         void *entry;
 900
 901         rcu_read_lock();
 902         xas_for_each(&xas, entry, ULONG_MAX) {
 903                 if (xas_retry(&xas, entry))
 904                         continue;
 905                 if (entry == item)
 906                         break;
 907                 checked++;
 908                 if ((checked % 4) != 0)
 909                         continue;
 910                 xas_pause(&xas);
 911         }
 912         rcu_read_unlock();
 913
 914         return entry ? xas.xa_index : -1;
 915 }
 916
 917 static noinline void check_find_entry(struct xarray *xa)
 918 {
 919 #ifdef CONFIG_XARRAY_MULTI
 920         unsigned int order;
 921         unsigned long offset, index;
 922
 923         for (order = 0; order < 20; order++) {
 924                 for (offset = 0; offset < (1UL << (order + 3));
 925                      offset += (1UL << order)) {
 926                         for (index = 0; index < (1UL << (order + 5));
 927                              index += (1UL << order)) {
 928                                 xa_store_order(xa, index, order,
 929                                                 xa_mk_index(index), GFP_KERNEL);
 930                                 XA_BUG_ON(xa, xa_load(xa, index) !=
 931                                                 xa_mk_index(index));
 932                                 XA_BUG_ON(xa, xa_find_entry(xa,
 933                                                 xa_mk_index(index)) != index);
 934                         }
 935                         XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
 936                         xa_destroy(xa);
 937                 }
 938         }
 939 #endif
 940
 941         XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
 942         xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
 943         XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
 944         XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_index(ULONG_MAX)) != -1);
 945         xa_erase_index(xa, ULONG_MAX);
 946         XA_BUG_ON(xa, !xa_empty(xa));
 947 }
 948
 949 static noinline void check_move_small(struct xarray *xa, unsigned long idx)
 950 {
 951         XA_STATE(xas, xa, 0);
 952         unsigned long i;
 953
 954         xa_store_index(xa, 0, GFP_KERNEL);
 955         xa_store_index(xa, idx, GFP_KERNEL);
 956
 957         rcu_read_lock();
 958         for (i = 0; i < idx * 4; i++) {
 959                 void *entry = xas_next(&xas);
 960                 if (i <= idx)
 961                         XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
 962                 XA_BUG_ON(xa, xas.xa_index != i);
 963                 if (i == 0 || i == idx)
 964                         XA_BUG_ON(xa, entry != xa_mk_index(i));
 965                 else
 966                         XA_BUG_ON(xa, entry != NULL);
 967         }
 968         xas_next(&xas);
 969         XA_BUG_ON(xa, xas.xa_index != i);
 970
 971         do {
 972                 void *entry = xas_prev(&xas);
 973                 i--;
 974                 if (i <= idx)
 975                         XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
 976                 XA_BUG_ON(xa, xas.xa_index != i);
 977                 if (i == 0 || i == idx)
 978                         XA_BUG_ON(xa, entry != xa_mk_index(i));
 979                 else
 980                         XA_BUG_ON(xa, entry != NULL);
 981         } while (i > 0);
 982
 983         xas_set(&xas, ULONG_MAX);
 984         XA_BUG_ON(xa, xas_next(&xas) != NULL);
 985         XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
 986         XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0));
 987         XA_BUG_ON(xa, xas.xa_index != 0);
 988         XA_BUG_ON(xa, xas_prev(&xas) != NULL);
 989         XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
 990         rcu_read_unlock();
 991
 992         xa_erase_index(xa, 0);
 993         xa_erase_index(xa, idx);
 994         XA_BUG_ON(xa, !xa_empty(xa));
 995 }
 996
 997 static noinline void check_move(struct xarray *xa)
 998 {
 999         XA_STATE(xas, xa, (1 << 16) - 1);
1000         unsigned long i;
1001
1002         for (i = 0; i < (1 << 16); i++)
1003                 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
1004
1005         rcu_read_lock();
1006         do {
1007                 void *entry = xas_prev(&xas);
1008                 i--;
1009                 XA_BUG_ON(xa, entry != xa_mk_index(i));
1010                 XA_BUG_ON(xa, i != xas.xa_index);
1011         } while (i != 0);
1012
1013         XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1014         XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1015
1016         do {
1017                 void *entry = xas_next(&xas);
1018                 XA_BUG_ON(xa, entry != xa_mk_index(i));
1019                 XA_BUG_ON(xa, i != xas.xa_index);
1020                 i++;
1021         } while (i < (1 << 16));
1022         rcu_read_unlock();
1023
1024         for (i = (1 << 8); i < (1 << 15); i++)
1025                 xa_erase_index(xa, i);
1026
1027         i = xas.xa_index;
1028
1029         rcu_read_lock();
1030         do {
1031                 void *entry = xas_prev(&xas);
1032                 i--;
1033                 if ((i < (1 << 8)) || (i >= (1 << 15)))
1034                         XA_BUG_ON(xa, entry != xa_mk_index(i));
1035                 else
1036                         XA_BUG_ON(xa, entry != NULL);
1037                 XA_BUG_ON(xa, i != xas.xa_index);
1038         } while (i != 0);
1039
1040         XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1041         XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1042
1043         do {
1044                 void *entry = xas_next(&xas);
1045                 if ((i < (1 << 8)) || (i >= (1 << 15)))
1046                         XA_BUG_ON(xa, entry != xa_mk_index(i));
1047                 else
1048                         XA_BUG_ON(xa, entry != NULL);
1049                 XA_BUG_ON(xa, i != xas.xa_index);
1050                 i++;
1051         } while (i < (1 << 16));
1052         rcu_read_unlock();
1053
1054         xa_destroy(xa);
1055
1056         for (i = 0; i < 16; i++)
1057                 check_move_small(xa, 1UL << i);
1058
1059         for (i = 2; i < 16; i++)
1060                 check_move_small(xa, (1UL << i) - 1);
1061 }
1062
1063 static noinline void xa_store_many_order(struct xarray *xa,
1064                 unsigned long index, unsigned order)
1065 {
1066         XA_STATE_ORDER(xas, xa, index, order);
1067         unsigned int i = 0;
1068
1069         do {
1070                 xas_lock(&xas);
1071                 XA_BUG_ON(xa, xas_find_conflict(&xas));
1072                 xas_create_range(&xas);
1073                 if (xas_error(&xas))
1074                         goto unlock;
1075                 for (i = 0; i < (1U << order); i++) {
1076                         XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(index + i)));
1077                         xas_next(&xas);
1078                 }
1079 unlock:
1080                 xas_unlock(&xas);
1081         } while (xas_nomem(&xas, GFP_KERNEL));
1082
1083         XA_BUG_ON(xa, xas_error(&xas));
1084 }
1085
1086 static noinline void check_create_range_1(struct xarray *xa,
1087                 unsigned long index, unsigned order)
1088 {
1089         unsigned long i;
1090
1091         xa_store_many_order(xa, index, order);
1092         for (i = index; i < index + (1UL << order); i++)
1093                 xa_erase_index(xa, i);
1094         XA_BUG_ON(xa, !xa_empty(xa));
1095 }
1096
1097 static noinline void check_create_range_2(struct xarray *xa, unsigned order)
1098 {
1099         unsigned long i;
1100         unsigned long nr = 1UL << order;
1101
1102         for (i = 0; i < nr * nr; i += nr)
1103                 xa_store_many_order(xa, i, order);
1104         for (i = 0; i < nr * nr; i++)
1105                 xa_erase_index(xa, i);
1106         XA_BUG_ON(xa, !xa_empty(xa));
1107 }
1108
1109 static noinline void check_create_range_3(void)
1110 {
1111         XA_STATE(xas, NULL, 0);
1112         xas_set_err(&xas, -EEXIST);
1113         xas_create_range(&xas);
1114         XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST);
1115 }
1116
1117 static noinline void check_create_range_4(struct xarray *xa,
1118                 unsigned long index, unsigned order)
1119 {
1120         XA_STATE_ORDER(xas, xa, index, order);
1121         unsigned long base = xas.xa_index;
1122         unsigned long i = 0;
1123
1124         xa_store_index(xa, index, GFP_KERNEL);
1125         do {
1126                 xas_lock(&xas);
1127                 xas_create_range(&xas);
1128                 if (xas_error(&xas))
1129                         goto unlock;
1130                 for (i = 0; i < (1UL << order); i++) {
1131                         void *old = xas_store(&xas, xa_mk_index(base + i));
1132                         if (xas.xa_index == index)
1133                                 XA_BUG_ON(xa, old != xa_mk_index(base + i));
1134                         else
1135                                 XA_BUG_ON(xa, old != NULL);
1136                         xas_next(&xas);
1137                 }
1138 unlock:
1139                 xas_unlock(&xas);
1140         } while (xas_nomem(&xas, GFP_KERNEL));
1141
1142         XA_BUG_ON(xa, xas_error(&xas));
1143
1144         for (i = base; i < base + (1UL << order); i++)
1145                 xa_erase_index(xa, i);
1146         XA_BUG_ON(xa, !xa_empty(xa));
1147 }
1148
1149 static noinline void check_create_range(struct xarray *xa)
1150 {
1151         unsigned int order;
1152         unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1;
1153
1154         for (order = 0; order < max_order; order++) {
1155                 check_create_range_1(xa, 0, order);
1156                 check_create_range_1(xa, 1U << order, order);
1157                 check_create_range_1(xa, 2U << order, order);
1158                 check_create_range_1(xa, 3U << order, order);
1159                 check_create_range_1(xa, 1U << 24, order);
1160                 if (order < 10)
1161                         check_create_range_2(xa, order);
1162
1163                 check_create_range_4(xa, 0, order);
1164                 check_create_range_4(xa, 1U << order, order);
1165                 check_create_range_4(xa, 2U << order, order);
1166                 check_create_range_4(xa, 3U << order, order);
1167                 check_create_range_4(xa, 1U << 24, order);
1168
1169                 check_create_range_4(xa, 1, order);
1170                 check_create_range_4(xa, (1U << order) + 1, order);
1171                 check_create_range_4(xa, (2U << order) + 1, order);
1172                 check_create_range_4(xa, (2U << order) - 1, order);
1173                 check_create_range_4(xa, (3U << order) + 1, order);
1174                 check_create_range_4(xa, (3U << order) - 1, order);
1175                 check_create_range_4(xa, (1U << 24) + 1, order);
1176         }
1177
1178         check_create_range_3();
1179 }
1180
1181 static noinline void __check_store_range(struct xarray *xa, unsigned long first,
1182                 unsigned long last)
1183 {
1184 #ifdef CONFIG_XARRAY_MULTI
1185         xa_store_range(xa, first, last, xa_mk_index(first), GFP_KERNEL);
1186
1187         XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_index(first));
1188         XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_index(first));
1189         XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL);
1190         XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL);
1191
1192         xa_store_range(xa, first, last, NULL, GFP_KERNEL);
1193 #endif
1194
1195         XA_BUG_ON(xa, !xa_empty(xa));
1196 }
1197
1198 static noinline void check_store_range(struct xarray *xa)
1199 {
1200         unsigned long i, j;
1201
1202         for (i = 0; i < 128; i++) {
1203                 for (j = i; j < 128; j++) {
1204                         __check_store_range(xa, i, j);
1205                         __check_store_range(xa, 128 + i, 128 + j);
1206                         __check_store_range(xa, 4095 + i, 4095 + j);
1207                         __check_store_range(xa, 4096 + i, 4096 + j);
1208                         __check_store_range(xa, 123456 + i, 123456 + j);
1209                         __check_store_range(xa, (1 << 24) + i, (1 << 24) + j);
1210                 }
1211         }
1212 }
1213
1214 static void check_align_1(struct xarray *xa, char *name)
1215 {
1216         int i;
1217         unsigned int id;
1218         unsigned long index;
1219         void *entry;
1220
1221         for (i = 0; i < 8; i++) {
1222                 id = 0;
1223                 XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, name + i, GFP_KERNEL)
1224                                 != 0);
1225                 XA_BUG_ON(xa, id != i);
1226         }
1227         xa_for_each(xa, index, entry)
1228                 XA_BUG_ON(xa, xa_is_err(entry));
1229         xa_destroy(xa);
1230 }
1231
1232 static noinline void check_align(struct xarray *xa)
1233 {
1234         char name[] = "Motorola 68000";
1235
1236         check_align_1(xa, name);
1237         check_align_1(xa, name + 1);
1238         check_align_1(xa, name + 2);
1239         check_align_1(xa, name + 3);
1240 //      check_align_2(xa, name);
1241 }
1242
1243 static LIST_HEAD(shadow_nodes);
1244
1245 static void test_update_node(struct xa_node *node)
1246 {
1247         if (node->count && node->count == node->nr_values) {
1248                 if (list_empty(&node->private_list))
1249                         list_add(&shadow_nodes, &node->private_list);
1250         } else {
1251                 if (!list_empty(&node->private_list))
1252                         list_del_init(&node->private_list);
1253         }
1254 }
1255
1256 static noinline void shadow_remove(struct xarray *xa)
1257 {
1258         struct xa_node *node;
1259
1260         xa_lock(xa);
1261         while ((node = list_first_entry_or_null(&shadow_nodes,
1262                                         struct xa_node, private_list))) {
1263                 XA_STATE(xas, node->array, 0);
1264                 XA_BUG_ON(xa, node->array != xa);
1265                 list_del_init(&node->private_list);
1266                 xas.xa_node = xa_parent_locked(node->array, node);
1267                 xas.xa_offset = node->offset;
1268                 xas.xa_shift = node->shift + XA_CHUNK_SHIFT;
1269                 xas_set_update(&xas, test_update_node);
1270                 xas_store(&xas, NULL);
1271         }
1272         xa_unlock(xa);
1273 }
1274
1275 static noinline void check_workingset(struct xarray *xa, unsigned long index)
1276 {
1277         XA_STATE(xas, xa, index);
1278         xas_set_update(&xas, test_update_node);
1279
1280         do {
1281                 xas_lock(&xas);
1282                 xas_store(&xas, xa_mk_value(0));
1283                 xas_next(&xas);
1284                 xas_store(&xas, xa_mk_value(1));
1285                 xas_unlock(&xas);
1286         } while (xas_nomem(&xas, GFP_KERNEL));
1287
1288         XA_BUG_ON(xa, list_empty(&shadow_nodes));
1289
1290         xas_lock(&xas);
1291         xas_next(&xas);
1292         xas_store(&xas, &xas);
1293         XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1294
1295         xas_store(&xas, xa_mk_value(2));
1296         xas_unlock(&xas);
1297         XA_BUG_ON(xa, list_empty(&shadow_nodes));
1298
1299         shadow_remove(xa);
1300         XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1301         XA_BUG_ON(xa, !xa_empty(xa));
1302 }
1303
1304 /*
1305  * Check that the pointer / value / sibling entries are accounted the
1306  * way we expect them to be.
1307  */
1308 static noinline void check_account(struct xarray *xa)
1309 {
1310 #ifdef CONFIG_XARRAY_MULTI
1311         unsigned int order;
1312
1313         for (order = 1; order < 12; order++) {
1314                 XA_STATE(xas, xa, 1 << order);
1315
1316                 xa_store_order(xa, 0, order, xa, GFP_KERNEL);
1317                 rcu_read_lock();
1318                 xas_load(&xas);
1319                 XA_BUG_ON(xa, xas.xa_node->count == 0);
1320                 XA_BUG_ON(xa, xas.xa_node->count > (1 << order));
1321                 XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1322                 rcu_read_unlock();
1323
1324                 xa_store_order(xa, 1 << order, order, xa_mk_index(1UL << order),
1325                                 GFP_KERNEL);
1326                 XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2);
1327
1328                 xa_erase(xa, 1 << order);
1329                 XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1330
1331                 xa_erase(xa, 0);
1332                 XA_BUG_ON(xa, !xa_empty(xa));
1333         }
1334 #endif
1335 }
1336
1337 static noinline void check_destroy(struct xarray *xa)
1338 {
1339         unsigned long index;
1340
1341         XA_BUG_ON(xa, !xa_empty(xa));
1342
1343         /* Destroying an empty array is a no-op */
1344         xa_destroy(xa);
1345         XA_BUG_ON(xa, !xa_empty(xa));
1346
1347         /* Destroying an array with a single entry */
1348         for (index = 0; index < 1000; index++) {
1349                 xa_store_index(xa, index, GFP_KERNEL);
1350                 XA_BUG_ON(xa, xa_empty(xa));
1351                 xa_destroy(xa);
1352                 XA_BUG_ON(xa, !xa_empty(xa));
1353         }
1354
1355         /* Destroying an array with a single entry at ULONG_MAX */
1356         xa_store(xa, ULONG_MAX, xa, GFP_KERNEL);
1357         XA_BUG_ON(xa, xa_empty(xa));
1358         xa_destroy(xa);
1359         XA_BUG_ON(xa, !xa_empty(xa));
1360
1361 #ifdef CONFIG_XARRAY_MULTI
1362         /* Destroying an array with a multi-index entry */
1363         xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL);
1364         XA_BUG_ON(xa, xa_empty(xa));
1365         xa_destroy(xa);
1366         XA_BUG_ON(xa, !xa_empty(xa));
1367 #endif
1368 }
1369
1370 static DEFINE_XARRAY(array);
1371
1372 static int xarray_checks(void)
1373 {
1374         check_xa_err(&array);
1375         check_xas_retry(&array);
1376         check_xa_load(&array);
1377         check_xa_mark(&array);
1378         check_xa_shrink(&array);
1379         check_xas_erase(&array);
1380         check_cmpxchg(&array);
1381         check_reserve(&array);
1382         check_multi_store(&array);
1383         check_xa_alloc();
1384         check_find(&array);
1385         check_find_entry(&array);
1386         check_account(&array);
1387         check_destroy(&array);
1388         check_move(&array);
1389         check_create_range(&array);
1390         check_store_range(&array);
1391         check_store_iter(&array);
1392         check_align(&xa0);
1393
1394         check_workingset(&array, 0);
1395         check_workingset(&array, 64);
1396         check_workingset(&array, 4096);
1397
1398         printk("XArray: %u of %u tests passed\n", tests_passed, tests_run);
1399         return (tests_run == tests_passed) ? 0 : -EINVAL;
1400 }
1401
1402 static void xarray_exit(void)
1403 {
1404 }
1405
1406 module_init(xarray_checks);
1407 module_exit(xarray_exit);
1408 MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
1409 MODULE_LICENSE("GPL");