lib/test_xarray.c

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