2178 lines · c
1// SPDX-License-Identifier: GPL-2.0+2/*3 * test_xarray.c: Test the XArray API4 * Copyright (c) 2017-2018 Microsoft Corporation5 * Copyright (c) 2019-2020 Oracle6 * Author: Matthew Wilcox <willy@infradead.org>7 */8 9#include <linux/xarray.h>10#include <linux/module.h>11 12static unsigned int tests_run;13static unsigned int tests_passed;14 15static const unsigned int order_limit =16 IS_ENABLED(CONFIG_XARRAY_MULTI) ? BITS_PER_LONG : 1;17 18#ifndef XA_DEBUG19# ifdef __KERNEL__20void xa_dump(const struct xarray *xa) { }21# endif22#undef XA_BUG_ON23#define XA_BUG_ON(xa, x) do { \24 tests_run++; \25 if (x) { \26 printk("BUG at %s:%d\n", __func__, __LINE__); \27 xa_dump(xa); \28 dump_stack(); \29 } else { \30 tests_passed++; \31 } \32} while (0)33#endif34 35static void *xa_mk_index(unsigned long index)36{37 return xa_mk_value(index & LONG_MAX);38}39 40static void *xa_store_index(struct xarray *xa, unsigned long index, gfp_t gfp)41{42 return xa_store(xa, index, xa_mk_index(index), gfp);43}44 45static void xa_insert_index(struct xarray *xa, unsigned long index)46{47 XA_BUG_ON(xa, xa_insert(xa, index, xa_mk_index(index),48 GFP_KERNEL) != 0);49}50 51static void xa_alloc_index(struct xarray *xa, unsigned long index, gfp_t gfp)52{53 u32 id;54 55 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(index), xa_limit_32b,56 gfp) != 0);57 XA_BUG_ON(xa, id != index);58}59 60static void xa_erase_index(struct xarray *xa, unsigned long index)61{62 XA_BUG_ON(xa, xa_erase(xa, index) != xa_mk_index(index));63 XA_BUG_ON(xa, xa_load(xa, index) != NULL);64}65 66/*67 * If anyone needs this, please move it to xarray.c. We have no current68 * users outside the test suite because all current multislot users want69 * to use the advanced API.70 */71static void *xa_store_order(struct xarray *xa, unsigned long index,72 unsigned order, void *entry, gfp_t gfp)73{74 XA_STATE_ORDER(xas, xa, index, order);75 void *curr;76 77 do {78 xas_lock(&xas);79 curr = xas_store(&xas, entry);80 xas_unlock(&xas);81 } while (xas_nomem(&xas, gfp));82 83 return curr;84}85 86static noinline void check_xa_err(struct xarray *xa)87{88 XA_BUG_ON(xa, xa_err(xa_store_index(xa, 0, GFP_NOWAIT)) != 0);89 XA_BUG_ON(xa, xa_err(xa_erase(xa, 0)) != 0);90#ifndef __KERNEL__91 /* The kernel does not fail GFP_NOWAIT allocations */92 XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);93 XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);94#endif95 XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_KERNEL)) != 0);96 XA_BUG_ON(xa, xa_err(xa_store(xa, 1, xa_mk_value(0), GFP_KERNEL)) != 0);97 XA_BUG_ON(xa, xa_err(xa_erase(xa, 1)) != 0);98// kills the test-suite :-(99// XA_BUG_ON(xa, xa_err(xa_store(xa, 0, xa_mk_internal(0), 0)) != -EINVAL);100}101 102static noinline void check_xas_retry(struct xarray *xa)103{104 XA_STATE(xas, xa, 0);105 void *entry;106 107 xa_store_index(xa, 0, GFP_KERNEL);108 xa_store_index(xa, 1, GFP_KERNEL);109 110 rcu_read_lock();111 XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_value(0));112 xa_erase_index(xa, 1);113 XA_BUG_ON(xa, !xa_is_retry(xas_reload(&xas)));114 XA_BUG_ON(xa, xas_retry(&xas, NULL));115 XA_BUG_ON(xa, xas_retry(&xas, xa_mk_value(0)));116 xas_reset(&xas);117 XA_BUG_ON(xa, xas.xa_node != XAS_RESTART);118 XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));119 XA_BUG_ON(xa, xas.xa_node != NULL);120 rcu_read_unlock();121 122 XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);123 124 rcu_read_lock();125 XA_BUG_ON(xa, !xa_is_internal(xas_reload(&xas)));126 xas.xa_node = XAS_RESTART;127 XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));128 rcu_read_unlock();129 130 /* Make sure we can iterate through retry entries */131 xas_lock(&xas);132 xas_set(&xas, 0);133 xas_store(&xas, XA_RETRY_ENTRY);134 xas_set(&xas, 1);135 xas_store(&xas, XA_RETRY_ENTRY);136 137 xas_set(&xas, 0);138 xas_for_each(&xas, entry, ULONG_MAX) {139 xas_store(&xas, xa_mk_index(xas.xa_index));140 }141 xas_unlock(&xas);142 143 xa_erase_index(xa, 0);144 xa_erase_index(xa, 1);145}146 147static noinline void check_xa_load(struct xarray *xa)148{149 unsigned long i, j;150 151 for (i = 0; i < 1024; i++) {152 for (j = 0; j < 1024; j++) {153 void *entry = xa_load(xa, j);154 if (j < i)155 XA_BUG_ON(xa, xa_to_value(entry) != j);156 else157 XA_BUG_ON(xa, entry);158 }159 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);160 }161 162 for (i = 0; i < 1024; i++) {163 for (j = 0; j < 1024; j++) {164 void *entry = xa_load(xa, j);165 if (j >= i)166 XA_BUG_ON(xa, xa_to_value(entry) != j);167 else168 XA_BUG_ON(xa, entry);169 }170 xa_erase_index(xa, i);171 }172 XA_BUG_ON(xa, !xa_empty(xa));173}174 175static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index)176{177 unsigned int order;178 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 8 : 1;179 180 /* NULL elements have no marks set */181 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));182 xa_set_mark(xa, index, XA_MARK_0);183 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));184 185 /* Storing a pointer will not make a mark appear */186 XA_BUG_ON(xa, xa_store_index(xa, index, GFP_KERNEL) != NULL);187 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));188 xa_set_mark(xa, index, XA_MARK_0);189 XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));190 191 /* Setting one mark will not set another mark */192 XA_BUG_ON(xa, xa_get_mark(xa, index + 1, XA_MARK_0));193 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_1));194 195 /* Storing NULL clears marks, and they can't be set again */196 xa_erase_index(xa, index);197 XA_BUG_ON(xa, !xa_empty(xa));198 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));199 xa_set_mark(xa, index, XA_MARK_0);200 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));201 202 /*203 * Storing a multi-index entry over entries with marks gives the204 * entire entry the union of the marks205 */206 BUG_ON((index % 4) != 0);207 for (order = 2; order < max_order; order++) {208 unsigned long base = round_down(index, 1UL << order);209 unsigned long next = base + (1UL << order);210 unsigned long i;211 212 XA_BUG_ON(xa, xa_store_index(xa, index + 1, GFP_KERNEL));213 xa_set_mark(xa, index + 1, XA_MARK_0);214 XA_BUG_ON(xa, xa_store_index(xa, index + 2, GFP_KERNEL));215 xa_set_mark(xa, index + 2, XA_MARK_2);216 XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL));217 xa_store_order(xa, index, order, xa_mk_index(index),218 GFP_KERNEL);219 for (i = base; i < next; i++) {220 XA_STATE(xas, xa, i);221 unsigned int seen = 0;222 void *entry;223 224 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));225 XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_1));226 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_2));227 228 /* We should see two elements in the array */229 rcu_read_lock();230 xas_for_each(&xas, entry, ULONG_MAX)231 seen++;232 rcu_read_unlock();233 XA_BUG_ON(xa, seen != 2);234 235 /* One of which is marked */236 xas_set(&xas, 0);237 seen = 0;238 rcu_read_lock();239 xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)240 seen++;241 rcu_read_unlock();242 XA_BUG_ON(xa, seen != 1);243 }244 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_0));245 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_1));246 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_2));247 xa_erase_index(xa, index);248 xa_erase_index(xa, next);249 XA_BUG_ON(xa, !xa_empty(xa));250 }251 XA_BUG_ON(xa, !xa_empty(xa));252}253 254static noinline void check_xa_mark_2(struct xarray *xa)255{256 XA_STATE(xas, xa, 0);257 unsigned long index;258 unsigned int count = 0;259 void *entry;260 261 xa_store_index(xa, 0, GFP_KERNEL);262 xa_set_mark(xa, 0, XA_MARK_0);263 xas_lock(&xas);264 xas_load(&xas);265 xas_init_marks(&xas);266 xas_unlock(&xas);267 XA_BUG_ON(xa, !xa_get_mark(xa, 0, XA_MARK_0) == 0);268 269 for (index = 3500; index < 4500; index++) {270 xa_store_index(xa, index, GFP_KERNEL);271 xa_set_mark(xa, index, XA_MARK_0);272 }273 274 xas_reset(&xas);275 rcu_read_lock();276 xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)277 count++;278 rcu_read_unlock();279 XA_BUG_ON(xa, count != 1000);280 281 xas_lock(&xas);282 xas_for_each(&xas, entry, ULONG_MAX) {283 xas_init_marks(&xas);284 XA_BUG_ON(xa, !xa_get_mark(xa, xas.xa_index, XA_MARK_0));285 XA_BUG_ON(xa, !xas_get_mark(&xas, XA_MARK_0));286 }287 xas_unlock(&xas);288 289 xa_destroy(xa);290}291 292static noinline void check_xa_mark_3(struct xarray *xa)293{294#ifdef CONFIG_XARRAY_MULTI295 XA_STATE(xas, xa, 0x41);296 void *entry;297 int count = 0;298 299 xa_store_order(xa, 0x40, 2, xa_mk_index(0x40), GFP_KERNEL);300 xa_set_mark(xa, 0x41, XA_MARK_0);301 302 rcu_read_lock();303 xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0) {304 count++;305 XA_BUG_ON(xa, entry != xa_mk_index(0x40));306 }307 XA_BUG_ON(xa, count != 1);308 rcu_read_unlock();309 xa_destroy(xa);310#endif311}312 313static noinline void check_xa_mark(struct xarray *xa)314{315 unsigned long index;316 317 for (index = 0; index < 16384; index += 4)318 check_xa_mark_1(xa, index);319 320 check_xa_mark_2(xa);321 check_xa_mark_3(xa);322}323 324static noinline void check_xa_shrink(struct xarray *xa)325{326 XA_STATE(xas, xa, 1);327 struct xa_node *node;328 unsigned int order;329 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 15 : 1;330 331 XA_BUG_ON(xa, !xa_empty(xa));332 XA_BUG_ON(xa, xa_store_index(xa, 0, GFP_KERNEL) != NULL);333 XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);334 335 /*336 * Check that erasing the entry at 1 shrinks the tree and properly337 * marks the node as being deleted.338 */339 xas_lock(&xas);340 XA_BUG_ON(xa, xas_load(&xas) != xa_mk_value(1));341 node = xas.xa_node;342 XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != xa_mk_value(0));343 XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));344 XA_BUG_ON(xa, xa_load(xa, 1) != NULL);345 XA_BUG_ON(xa, xas.xa_node != XAS_BOUNDS);346 XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != XA_RETRY_ENTRY);347 XA_BUG_ON(xa, xas_load(&xas) != NULL);348 xas_unlock(&xas);349 XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));350 xa_erase_index(xa, 0);351 XA_BUG_ON(xa, !xa_empty(xa));352 353 for (order = 0; order < max_order; order++) {354 unsigned long max = (1UL << order) - 1;355 xa_store_order(xa, 0, order, xa_mk_value(0), GFP_KERNEL);356 XA_BUG_ON(xa, xa_load(xa, max) != xa_mk_value(0));357 XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);358 rcu_read_lock();359 node = xa_head(xa);360 rcu_read_unlock();361 XA_BUG_ON(xa, xa_store_index(xa, ULONG_MAX, GFP_KERNEL) !=362 NULL);363 rcu_read_lock();364 XA_BUG_ON(xa, xa_head(xa) == node);365 rcu_read_unlock();366 XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);367 xa_erase_index(xa, ULONG_MAX);368 XA_BUG_ON(xa, xa->xa_head != node);369 xa_erase_index(xa, 0);370 }371}372 373static noinline void check_insert(struct xarray *xa)374{375 unsigned long i;376 377 for (i = 0; i < 1024; i++) {378 xa_insert_index(xa, i);379 XA_BUG_ON(xa, xa_load(xa, i - 1) != NULL);380 XA_BUG_ON(xa, xa_load(xa, i + 1) != NULL);381 xa_erase_index(xa, i);382 }383 384 for (i = 10; i < BITS_PER_LONG; i++) {385 xa_insert_index(xa, 1UL << i);386 XA_BUG_ON(xa, xa_load(xa, (1UL << i) - 1) != NULL);387 XA_BUG_ON(xa, xa_load(xa, (1UL << i) + 1) != NULL);388 xa_erase_index(xa, 1UL << i);389 390 xa_insert_index(xa, (1UL << i) - 1);391 XA_BUG_ON(xa, xa_load(xa, (1UL << i) - 2) != NULL);392 XA_BUG_ON(xa, xa_load(xa, 1UL << i) != NULL);393 xa_erase_index(xa, (1UL << i) - 1);394 }395 396 xa_insert_index(xa, ~0UL);397 XA_BUG_ON(xa, xa_load(xa, 0UL) != NULL);398 XA_BUG_ON(xa, xa_load(xa, ~1UL) != NULL);399 xa_erase_index(xa, ~0UL);400 401 XA_BUG_ON(xa, !xa_empty(xa));402}403 404static noinline void check_cmpxchg(struct xarray *xa)405{406 void *FIVE = xa_mk_value(5);407 void *SIX = xa_mk_value(6);408 void *LOTS = xa_mk_value(12345678);409 410 XA_BUG_ON(xa, !xa_empty(xa));411 XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_KERNEL) != NULL);412 XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EBUSY);413 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS);414 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS);415 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE);416 XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != NULL);417 XA_BUG_ON(xa, xa_cmpxchg(xa, 5, NULL, FIVE, GFP_KERNEL) != NULL);418 XA_BUG_ON(xa, xa_insert(xa, 5, FIVE, GFP_KERNEL) != -EBUSY);419 XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != FIVE);420 XA_BUG_ON(xa, xa_insert(xa, 5, FIVE, GFP_KERNEL) == -EBUSY);421 xa_erase_index(xa, 12345678);422 xa_erase_index(xa, 5);423 XA_BUG_ON(xa, !xa_empty(xa));424}425 426static noinline void check_cmpxchg_order(struct xarray *xa)427{428#ifdef CONFIG_XARRAY_MULTI429 void *FIVE = xa_mk_value(5);430 unsigned int i, order = 3;431 432 XA_BUG_ON(xa, xa_store_order(xa, 0, order, FIVE, GFP_KERNEL));433 434 /* Check entry FIVE has the order saved */435 XA_BUG_ON(xa, xa_get_order(xa, xa_to_value(FIVE)) != order);436 437 /* Check all the tied indexes have the same entry and order */438 for (i = 0; i < (1 << order); i++) {439 XA_BUG_ON(xa, xa_load(xa, i) != FIVE);440 XA_BUG_ON(xa, xa_get_order(xa, i) != order);441 }442 443 /* Ensure that nothing is stored at index '1 << order' */444 XA_BUG_ON(xa, xa_load(xa, 1 << order) != NULL);445 446 /*447 * Additionally, keep the node information and the order at448 * '1 << order'449 */450 XA_BUG_ON(xa, xa_store_order(xa, 1 << order, order, FIVE, GFP_KERNEL));451 for (i = (1 << order); i < (1 << order) + (1 << order) - 1; i++) {452 XA_BUG_ON(xa, xa_load(xa, i) != FIVE);453 XA_BUG_ON(xa, xa_get_order(xa, i) != order);454 }455 456 /* Conditionally replace FIVE entry at index '0' with NULL */457 XA_BUG_ON(xa, xa_cmpxchg(xa, 0, FIVE, NULL, GFP_KERNEL) != FIVE);458 459 /* Verify the order is lost at FIVE (and old) entries */460 XA_BUG_ON(xa, xa_get_order(xa, xa_to_value(FIVE)) != 0);461 462 /* Verify the order and entries are lost in all the tied indexes */463 for (i = 0; i < (1 << order); i++) {464 XA_BUG_ON(xa, xa_load(xa, i) != NULL);465 XA_BUG_ON(xa, xa_get_order(xa, i) != 0);466 }467 468 /* Verify node and order are kept at '1 << order' */469 for (i = (1 << order); i < (1 << order) + (1 << order) - 1; i++) {470 XA_BUG_ON(xa, xa_load(xa, i) != FIVE);471 XA_BUG_ON(xa, xa_get_order(xa, i) != order);472 }473 474 xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL);475 XA_BUG_ON(xa, !xa_empty(xa));476#endif477}478 479static noinline void check_reserve(struct xarray *xa)480{481 void *entry;482 unsigned long index;483 int count;484 485 /* An array with a reserved entry is not empty */486 XA_BUG_ON(xa, !xa_empty(xa));487 XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);488 XA_BUG_ON(xa, xa_empty(xa));489 XA_BUG_ON(xa, xa_load(xa, 12345678));490 xa_release(xa, 12345678);491 XA_BUG_ON(xa, !xa_empty(xa));492 493 /* Releasing a used entry does nothing */494 XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);495 XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL);496 xa_release(xa, 12345678);497 xa_erase_index(xa, 12345678);498 XA_BUG_ON(xa, !xa_empty(xa));499 500 /* cmpxchg sees a reserved entry as ZERO */501 XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);502 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, XA_ZERO_ENTRY,503 xa_mk_value(12345678), GFP_NOWAIT) != NULL);504 xa_release(xa, 12345678);505 xa_erase_index(xa, 12345678);506 XA_BUG_ON(xa, !xa_empty(xa));507 508 /* xa_insert treats it as busy */509 XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);510 XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) !=511 -EBUSY);512 XA_BUG_ON(xa, xa_empty(xa));513 XA_BUG_ON(xa, xa_erase(xa, 12345678) != NULL);514 XA_BUG_ON(xa, !xa_empty(xa));515 516 /* Can iterate through a reserved entry */517 xa_store_index(xa, 5, GFP_KERNEL);518 XA_BUG_ON(xa, xa_reserve(xa, 6, GFP_KERNEL) != 0);519 xa_store_index(xa, 7, GFP_KERNEL);520 521 count = 0;522 xa_for_each(xa, index, entry) {523 XA_BUG_ON(xa, index != 5 && index != 7);524 count++;525 }526 XA_BUG_ON(xa, count != 2);527 528 /* If we free a reserved entry, we should be able to allocate it */529 if (xa->xa_flags & XA_FLAGS_ALLOC) {530 u32 id;531 532 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(8),533 XA_LIMIT(5, 10), GFP_KERNEL) != 0);534 XA_BUG_ON(xa, id != 8);535 536 xa_release(xa, 6);537 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(6),538 XA_LIMIT(5, 10), GFP_KERNEL) != 0);539 XA_BUG_ON(xa, id != 6);540 }541 542 xa_destroy(xa);543}544 545static noinline void check_xas_erase(struct xarray *xa)546{547 XA_STATE(xas, xa, 0);548 void *entry;549 unsigned long i, j;550 551 for (i = 0; i < 200; i++) {552 for (j = i; j < 2 * i + 17; j++) {553 xas_set(&xas, j);554 do {555 xas_lock(&xas);556 xas_store(&xas, xa_mk_index(j));557 xas_unlock(&xas);558 } while (xas_nomem(&xas, GFP_KERNEL));559 }560 561 xas_set(&xas, ULONG_MAX);562 do {563 xas_lock(&xas);564 xas_store(&xas, xa_mk_value(0));565 xas_unlock(&xas);566 } while (xas_nomem(&xas, GFP_KERNEL));567 568 xas_lock(&xas);569 xas_store(&xas, NULL);570 571 xas_set(&xas, 0);572 j = i;573 xas_for_each(&xas, entry, ULONG_MAX) {574 XA_BUG_ON(xa, entry != xa_mk_index(j));575 xas_store(&xas, NULL);576 j++;577 }578 xas_unlock(&xas);579 XA_BUG_ON(xa, !xa_empty(xa));580 }581}582 583#ifdef CONFIG_XARRAY_MULTI584static noinline void check_multi_store_1(struct xarray *xa, unsigned long index,585 unsigned int order)586{587 XA_STATE(xas, xa, index);588 unsigned long min = index & ~((1UL << order) - 1);589 unsigned long max = min + (1UL << order);590 591 xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);592 XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(index));593 XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(index));594 XA_BUG_ON(xa, xa_load(xa, max) != NULL);595 XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);596 597 xas_lock(&xas);598 XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(min)) != xa_mk_index(index));599 xas_unlock(&xas);600 XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(min));601 XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(min));602 XA_BUG_ON(xa, xa_load(xa, max) != NULL);603 XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);604 605 xa_erase_index(xa, min);606 XA_BUG_ON(xa, !xa_empty(xa));607}608 609static noinline void check_multi_store_2(struct xarray *xa, unsigned long index,610 unsigned int order)611{612 XA_STATE(xas, xa, index);613 xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL);614 615 xas_lock(&xas);616 XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0));617 XA_BUG_ON(xa, xas.xa_index != index);618 XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));619 xas_unlock(&xas);620 XA_BUG_ON(xa, !xa_empty(xa));621}622 623static noinline void check_multi_store_3(struct xarray *xa, unsigned long index,624 unsigned int order)625{626 XA_STATE(xas, xa, 0);627 void *entry;628 int n = 0;629 630 xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);631 632 xas_lock(&xas);633 xas_for_each(&xas, entry, ULONG_MAX) {634 XA_BUG_ON(xa, entry != xa_mk_index(index));635 n++;636 }637 XA_BUG_ON(xa, n != 1);638 xas_set(&xas, index + 1);639 xas_for_each(&xas, entry, ULONG_MAX) {640 XA_BUG_ON(xa, entry != xa_mk_index(index));641 n++;642 }643 XA_BUG_ON(xa, n != 2);644 xas_unlock(&xas);645 646 xa_destroy(xa);647}648#endif649 650static noinline void check_multi_store(struct xarray *xa)651{652#ifdef CONFIG_XARRAY_MULTI653 unsigned long i, j, k;654 unsigned int max_order = (sizeof(long) == 4) ? 30 : 60;655 656 /* Loading from any position returns the same value */657 xa_store_order(xa, 0, 1, xa_mk_value(0), GFP_KERNEL);658 XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));659 XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));660 XA_BUG_ON(xa, xa_load(xa, 2) != NULL);661 rcu_read_lock();662 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 2);663 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);664 rcu_read_unlock();665 666 /* Storing adjacent to the value does not alter the value */667 xa_store(xa, 3, xa, GFP_KERNEL);668 XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));669 XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));670 XA_BUG_ON(xa, xa_load(xa, 2) != NULL);671 rcu_read_lock();672 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 3);673 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);674 rcu_read_unlock();675 676 /* Overwriting multiple indexes works */677 xa_store_order(xa, 0, 2, xa_mk_value(1), GFP_KERNEL);678 XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(1));679 XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(1));680 XA_BUG_ON(xa, xa_load(xa, 2) != xa_mk_value(1));681 XA_BUG_ON(xa, xa_load(xa, 3) != xa_mk_value(1));682 XA_BUG_ON(xa, xa_load(xa, 4) != NULL);683 rcu_read_lock();684 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 4);685 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 4);686 rcu_read_unlock();687 688 /* We can erase multiple values with a single store */689 xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL);690 XA_BUG_ON(xa, !xa_empty(xa));691 692 /* Even when the first slot is empty but the others aren't */693 xa_store_index(xa, 1, GFP_KERNEL);694 xa_store_index(xa, 2, GFP_KERNEL);695 xa_store_order(xa, 0, 2, NULL, GFP_KERNEL);696 XA_BUG_ON(xa, !xa_empty(xa));697 698 for (i = 0; i < max_order; i++) {699 for (j = 0; j < max_order; j++) {700 xa_store_order(xa, 0, i, xa_mk_index(i), GFP_KERNEL);701 xa_store_order(xa, 0, j, xa_mk_index(j), GFP_KERNEL);702 703 for (k = 0; k < max_order; k++) {704 void *entry = xa_load(xa, (1UL << k) - 1);705 if ((i < k) && (j < k))706 XA_BUG_ON(xa, entry != NULL);707 else708 XA_BUG_ON(xa, entry != xa_mk_index(j));709 }710 711 xa_erase(xa, 0);712 XA_BUG_ON(xa, !xa_empty(xa));713 }714 }715 716 for (i = 0; i < 20; i++) {717 check_multi_store_1(xa, 200, i);718 check_multi_store_1(xa, 0, i);719 check_multi_store_1(xa, (1UL << i) + 1, i);720 }721 check_multi_store_2(xa, 4095, 9);722 723 for (i = 1; i < 20; i++) {724 check_multi_store_3(xa, 0, i);725 check_multi_store_3(xa, 1UL << i, i);726 }727#endif728}729 730#ifdef CONFIG_XARRAY_MULTI731/* mimics page cache __filemap_add_folio() */732static noinline void check_xa_multi_store_adv_add(struct xarray *xa,733 unsigned long index,734 unsigned int order,735 void *p)736{737 XA_STATE(xas, xa, index);738 unsigned int nrpages = 1UL << order;739 740 /* users are responsible for index alignemnt to the order when adding */741 XA_BUG_ON(xa, index & (nrpages - 1));742 743 xas_set_order(&xas, index, order);744 745 do {746 xas_lock_irq(&xas);747 xas_store(&xas, p);748 xas_unlock_irq(&xas);749 /*750 * In our selftest case the only failure we can expect is for751 * there not to be enough memory as we're not mimicking the752 * entire page cache, so verify that's the only error we can run753 * into here. The xas_nomem() which follows will ensure to fix754 * that condition for us so to chug on on the loop.755 */756 XA_BUG_ON(xa, xas_error(&xas) && xas_error(&xas) != -ENOMEM);757 } while (xas_nomem(&xas, GFP_KERNEL));758 759 XA_BUG_ON(xa, xas_error(&xas));760 XA_BUG_ON(xa, xa_load(xa, index) != p);761}762 763/* mimics page_cache_delete() */764static noinline void check_xa_multi_store_adv_del_entry(struct xarray *xa,765 unsigned long index,766 unsigned int order)767{768 XA_STATE(xas, xa, index);769 770 xas_set_order(&xas, index, order);771 xas_store(&xas, NULL);772 xas_init_marks(&xas);773}774 775static noinline void check_xa_multi_store_adv_delete(struct xarray *xa,776 unsigned long index,777 unsigned int order)778{779 xa_lock_irq(xa);780 check_xa_multi_store_adv_del_entry(xa, index, order);781 xa_unlock_irq(xa);782}783 784/* mimics page cache filemap_get_entry() */785static noinline void *test_get_entry(struct xarray *xa, unsigned long index)786{787 XA_STATE(xas, xa, index);788 void *p;789 static unsigned int loops = 0;790 791 rcu_read_lock();792repeat:793 xas_reset(&xas);794 p = xas_load(&xas);795 if (xas_retry(&xas, p))796 goto repeat;797 rcu_read_unlock();798 799 /*800 * This is not part of the page cache, this selftest is pretty801 * aggressive and does not want to trust the xarray API but rather802 * test it, and for order 20 (4 GiB block size) we can loop over803 * over a million entries which can cause a soft lockup. Page cache804 * APIs won't be stupid, proper page cache APIs loop over the proper805 * order so when using a larger order we skip shared entries.806 */807 if (++loops % XA_CHECK_SCHED == 0)808 schedule();809 810 return p;811}812 813static unsigned long some_val = 0xdeadbeef;814static unsigned long some_val_2 = 0xdeaddead;815 816/* mimics the page cache usage */817static noinline void check_xa_multi_store_adv(struct xarray *xa,818 unsigned long pos,819 unsigned int order)820{821 unsigned int nrpages = 1UL << order;822 unsigned long index, base, next_index, next_next_index;823 unsigned int i;824 825 index = pos >> PAGE_SHIFT;826 base = round_down(index, nrpages);827 next_index = round_down(base + nrpages, nrpages);828 next_next_index = round_down(next_index + nrpages, nrpages);829 830 check_xa_multi_store_adv_add(xa, base, order, &some_val);831 832 for (i = 0; i < nrpages; i++)833 XA_BUG_ON(xa, test_get_entry(xa, base + i) != &some_val);834 835 XA_BUG_ON(xa, test_get_entry(xa, next_index) != NULL);836 837 /* Use order 0 for the next item */838 check_xa_multi_store_adv_add(xa, next_index, 0, &some_val_2);839 XA_BUG_ON(xa, test_get_entry(xa, next_index) != &some_val_2);840 841 /* Remove the next item */842 check_xa_multi_store_adv_delete(xa, next_index, 0);843 844 /* Now use order for a new pointer */845 check_xa_multi_store_adv_add(xa, next_index, order, &some_val_2);846 847 for (i = 0; i < nrpages; i++)848 XA_BUG_ON(xa, test_get_entry(xa, next_index + i) != &some_val_2);849 850 check_xa_multi_store_adv_delete(xa, next_index, order);851 check_xa_multi_store_adv_delete(xa, base, order);852 XA_BUG_ON(xa, !xa_empty(xa));853 854 /* starting fresh again */855 856 /* let's test some holes now */857 858 /* hole at base and next_next */859 check_xa_multi_store_adv_add(xa, next_index, order, &some_val_2);860 861 for (i = 0; i < nrpages; i++)862 XA_BUG_ON(xa, test_get_entry(xa, base + i) != NULL);863 864 for (i = 0; i < nrpages; i++)865 XA_BUG_ON(xa, test_get_entry(xa, next_index + i) != &some_val_2);866 867 for (i = 0; i < nrpages; i++)868 XA_BUG_ON(xa, test_get_entry(xa, next_next_index + i) != NULL);869 870 check_xa_multi_store_adv_delete(xa, next_index, order);871 XA_BUG_ON(xa, !xa_empty(xa));872 873 /* hole at base and next */874 875 check_xa_multi_store_adv_add(xa, next_next_index, order, &some_val_2);876 877 for (i = 0; i < nrpages; i++)878 XA_BUG_ON(xa, test_get_entry(xa, base + i) != NULL);879 880 for (i = 0; i < nrpages; i++)881 XA_BUG_ON(xa, test_get_entry(xa, next_index + i) != NULL);882 883 for (i = 0; i < nrpages; i++)884 XA_BUG_ON(xa, test_get_entry(xa, next_next_index + i) != &some_val_2);885 886 check_xa_multi_store_adv_delete(xa, next_next_index, order);887 XA_BUG_ON(xa, !xa_empty(xa));888}889#endif890 891static noinline void check_multi_store_advanced(struct xarray *xa)892{893#ifdef CONFIG_XARRAY_MULTI894 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;895 unsigned long end = ULONG_MAX/2;896 unsigned long pos, i;897 898 /*899 * About 117 million tests below.900 */901 for (pos = 7; pos < end; pos = (pos * pos) + 564) {902 for (i = 0; i < max_order; i++) {903 check_xa_multi_store_adv(xa, pos, i);904 check_xa_multi_store_adv(xa, pos + 157, i);905 }906 }907#endif908}909 910static noinline void check_xa_alloc_1(struct xarray *xa, unsigned int base)911{912 int i;913 u32 id;914 915 XA_BUG_ON(xa, !xa_empty(xa));916 /* An empty array should assign %base to the first alloc */917 xa_alloc_index(xa, base, GFP_KERNEL);918 919 /* Erasing it should make the array empty again */920 xa_erase_index(xa, base);921 XA_BUG_ON(xa, !xa_empty(xa));922 923 /* And it should assign %base again */924 xa_alloc_index(xa, base, GFP_KERNEL);925 926 /* Allocating and then erasing a lot should not lose base */927 for (i = base + 1; i < 2 * XA_CHUNK_SIZE; i++)928 xa_alloc_index(xa, i, GFP_KERNEL);929 for (i = base; i < 2 * XA_CHUNK_SIZE; i++)930 xa_erase_index(xa, i);931 xa_alloc_index(xa, base, GFP_KERNEL);932 933 /* Destroying the array should do the same as erasing */934 xa_destroy(xa);935 936 /* And it should assign %base again */937 xa_alloc_index(xa, base, GFP_KERNEL);938 939 /* The next assigned ID should be base+1 */940 xa_alloc_index(xa, base + 1, GFP_KERNEL);941 xa_erase_index(xa, base + 1);942 943 /* Storing a value should mark it used */944 xa_store_index(xa, base + 1, GFP_KERNEL);945 xa_alloc_index(xa, base + 2, GFP_KERNEL);946 947 /* If we then erase base, it should be free */948 xa_erase_index(xa, base);949 xa_alloc_index(xa, base, GFP_KERNEL);950 951 xa_erase_index(xa, base + 1);952 xa_erase_index(xa, base + 2);953 954 for (i = 1; i < 5000; i++) {955 xa_alloc_index(xa, base + i, GFP_KERNEL);956 }957 958 xa_destroy(xa);959 960 /* Check that we fail properly at the limit of allocation */961 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX - 1),962 XA_LIMIT(UINT_MAX - 1, UINT_MAX),963 GFP_KERNEL) != 0);964 XA_BUG_ON(xa, id != 0xfffffffeU);965 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX),966 XA_LIMIT(UINT_MAX - 1, UINT_MAX),967 GFP_KERNEL) != 0);968 XA_BUG_ON(xa, id != 0xffffffffU);969 id = 3;970 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(0),971 XA_LIMIT(UINT_MAX - 1, UINT_MAX),972 GFP_KERNEL) != -EBUSY);973 XA_BUG_ON(xa, id != 3);974 xa_destroy(xa);975 976 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),977 GFP_KERNEL) != -EBUSY);978 XA_BUG_ON(xa, xa_store_index(xa, 3, GFP_KERNEL) != 0);979 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),980 GFP_KERNEL) != -EBUSY);981 xa_erase_index(xa, 3);982 XA_BUG_ON(xa, !xa_empty(xa));983}984 985static noinline void check_xa_alloc_2(struct xarray *xa, unsigned int base)986{987 unsigned int i, id;988 unsigned long index;989 void *entry;990 991 /* Allocate and free a NULL and check xa_empty() behaves */992 XA_BUG_ON(xa, !xa_empty(xa));993 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);994 XA_BUG_ON(xa, id != base);995 XA_BUG_ON(xa, xa_empty(xa));996 XA_BUG_ON(xa, xa_erase(xa, id) != NULL);997 XA_BUG_ON(xa, !xa_empty(xa));998 999 /* Ditto, but check destroy instead of erase */1000 XA_BUG_ON(xa, !xa_empty(xa));1001 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);1002 XA_BUG_ON(xa, id != base);1003 XA_BUG_ON(xa, xa_empty(xa));1004 xa_destroy(xa);1005 XA_BUG_ON(xa, !xa_empty(xa));1006 1007 for (i = base; i < base + 10; i++) {1008 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b,1009 GFP_KERNEL) != 0);1010 XA_BUG_ON(xa, id != i);1011 }1012 1013 XA_BUG_ON(xa, xa_store(xa, 3, xa_mk_index(3), GFP_KERNEL) != NULL);1014 XA_BUG_ON(xa, xa_store(xa, 4, xa_mk_index(4), GFP_KERNEL) != NULL);1015 XA_BUG_ON(xa, xa_store(xa, 4, NULL, GFP_KERNEL) != xa_mk_index(4));1016 XA_BUG_ON(xa, xa_erase(xa, 5) != NULL);1017 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);1018 XA_BUG_ON(xa, id != 5);1019 1020 xa_for_each(xa, index, entry) {1021 xa_erase_index(xa, index);1022 }1023 1024 for (i = base; i < base + 9; i++) {1025 XA_BUG_ON(xa, xa_erase(xa, i) != NULL);1026 XA_BUG_ON(xa, xa_empty(xa));1027 }1028 XA_BUG_ON(xa, xa_erase(xa, 8) != NULL);1029 XA_BUG_ON(xa, xa_empty(xa));1030 XA_BUG_ON(xa, xa_erase(xa, base + 9) != NULL);1031 XA_BUG_ON(xa, !xa_empty(xa));1032 1033 xa_destroy(xa);1034}1035 1036static noinline void check_xa_alloc_3(struct xarray *xa, unsigned int base)1037{1038 struct xa_limit limit = XA_LIMIT(1, 0x3fff);1039 u32 next = 0;1040 unsigned int i, id;1041 unsigned long index;1042 void *entry;1043 1044 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(1), limit,1045 &next, GFP_KERNEL) != 0);1046 XA_BUG_ON(xa, id != 1);1047 1048 next = 0x3ffd;1049 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(0x3ffd), limit,1050 &next, GFP_KERNEL) != 0);1051 XA_BUG_ON(xa, id != 0x3ffd);1052 xa_erase_index(xa, 0x3ffd);1053 xa_erase_index(xa, 1);1054 XA_BUG_ON(xa, !xa_empty(xa));1055 1056 for (i = 0x3ffe; i < 0x4003; i++) {1057 if (i < 0x4000)1058 entry = xa_mk_index(i);1059 else1060 entry = xa_mk_index(i - 0x3fff);1061 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, entry, limit,1062 &next, GFP_KERNEL) != (id == 1));1063 XA_BUG_ON(xa, xa_mk_index(id) != entry);1064 }1065 1066 /* Check wrap-around is handled correctly */1067 if (base != 0)1068 xa_erase_index(xa, base);1069 xa_erase_index(xa, base + 1);1070 next = UINT_MAX;1071 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(UINT_MAX),1072 xa_limit_32b, &next, GFP_KERNEL) != 0);1073 XA_BUG_ON(xa, id != UINT_MAX);1074 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base),1075 xa_limit_32b, &next, GFP_KERNEL) != 1);1076 XA_BUG_ON(xa, id != base);1077 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base + 1),1078 xa_limit_32b, &next, GFP_KERNEL) != 0);1079 XA_BUG_ON(xa, id != base + 1);1080 1081 xa_for_each(xa, index, entry)1082 xa_erase_index(xa, index);1083 1084 XA_BUG_ON(xa, !xa_empty(xa));1085}1086 1087static DEFINE_XARRAY_ALLOC(xa0);1088static DEFINE_XARRAY_ALLOC1(xa1);1089 1090static noinline void check_xa_alloc(void)1091{1092 check_xa_alloc_1(&xa0, 0);1093 check_xa_alloc_1(&xa1, 1);1094 check_xa_alloc_2(&xa0, 0);1095 check_xa_alloc_2(&xa1, 1);1096 check_xa_alloc_3(&xa0, 0);1097 check_xa_alloc_3(&xa1, 1);1098}1099 1100static noinline void __check_store_iter(struct xarray *xa, unsigned long start,1101 unsigned int order, unsigned int present)1102{1103 XA_STATE_ORDER(xas, xa, start, order);1104 void *entry;1105 unsigned int count = 0;1106 1107retry:1108 xas_lock(&xas);1109 xas_for_each_conflict(&xas, entry) {1110 XA_BUG_ON(xa, !xa_is_value(entry));1111 XA_BUG_ON(xa, entry < xa_mk_index(start));1112 XA_BUG_ON(xa, entry > xa_mk_index(start + (1UL << order) - 1));1113 count++;1114 }1115 xas_store(&xas, xa_mk_index(start));1116 xas_unlock(&xas);1117 if (xas_nomem(&xas, GFP_KERNEL)) {1118 count = 0;1119 goto retry;1120 }1121 XA_BUG_ON(xa, xas_error(&xas));1122 XA_BUG_ON(xa, count != present);1123 XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_index(start));1124 XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) !=1125 xa_mk_index(start));1126 xa_erase_index(xa, start);1127}1128 1129static noinline void check_store_iter(struct xarray *xa)1130{1131 unsigned int i, j;1132 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;1133 1134 for (i = 0; i < max_order; i++) {1135 unsigned int min = 1 << i;1136 unsigned int max = (2 << i) - 1;1137 __check_store_iter(xa, 0, i, 0);1138 XA_BUG_ON(xa, !xa_empty(xa));1139 __check_store_iter(xa, min, i, 0);1140 XA_BUG_ON(xa, !xa_empty(xa));1141 1142 xa_store_index(xa, min, GFP_KERNEL);1143 __check_store_iter(xa, min, i, 1);1144 XA_BUG_ON(xa, !xa_empty(xa));1145 xa_store_index(xa, max, GFP_KERNEL);1146 __check_store_iter(xa, min, i, 1);1147 XA_BUG_ON(xa, !xa_empty(xa));1148 1149 for (j = 0; j < min; j++)1150 xa_store_index(xa, j, GFP_KERNEL);1151 __check_store_iter(xa, 0, i, min);1152 XA_BUG_ON(xa, !xa_empty(xa));1153 for (j = 0; j < min; j++)1154 xa_store_index(xa, min + j, GFP_KERNEL);1155 __check_store_iter(xa, min, i, min);1156 XA_BUG_ON(xa, !xa_empty(xa));1157 }1158#ifdef CONFIG_XARRAY_MULTI1159 xa_store_index(xa, 63, GFP_KERNEL);1160 xa_store_index(xa, 65, GFP_KERNEL);1161 __check_store_iter(xa, 64, 2, 1);1162 xa_erase_index(xa, 63);1163#endif1164 XA_BUG_ON(xa, !xa_empty(xa));1165}1166 1167static noinline void check_multi_find_1(struct xarray *xa, unsigned order)1168{1169#ifdef CONFIG_XARRAY_MULTI1170 unsigned long multi = 3 << order;1171 unsigned long next = 4 << order;1172 unsigned long index;1173 1174 xa_store_order(xa, multi, order, xa_mk_value(multi), GFP_KERNEL);1175 XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL) != NULL);1176 XA_BUG_ON(xa, xa_store_index(xa, next + 1, GFP_KERNEL) != NULL);1177 1178 index = 0;1179 XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=1180 xa_mk_value(multi));1181 XA_BUG_ON(xa, index != multi);1182 index = multi + 1;1183 XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=1184 xa_mk_value(multi));1185 XA_BUG_ON(xa, (index < multi) || (index >= next));1186 XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) !=1187 xa_mk_value(next));1188 XA_BUG_ON(xa, index != next);1189 XA_BUG_ON(xa, xa_find_after(xa, &index, next, XA_PRESENT) != NULL);1190 XA_BUG_ON(xa, index != next);1191 1192 xa_erase_index(xa, multi);1193 xa_erase_index(xa, next);1194 xa_erase_index(xa, next + 1);1195 XA_BUG_ON(xa, !xa_empty(xa));1196#endif1197}1198 1199static noinline void check_multi_find_2(struct xarray *xa)1200{1201 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1;1202 unsigned int i, j;1203 void *entry;1204 1205 for (i = 0; i < max_order; i++) {1206 unsigned long index = 1UL << i;1207 for (j = 0; j < index; j++) {1208 XA_STATE(xas, xa, j + index);1209 xa_store_index(xa, index - 1, GFP_KERNEL);1210 xa_store_order(xa, index, i, xa_mk_index(index),1211 GFP_KERNEL);1212 rcu_read_lock();1213 xas_for_each(&xas, entry, ULONG_MAX) {1214 xa_erase_index(xa, index);1215 }1216 rcu_read_unlock();1217 xa_erase_index(xa, index - 1);1218 XA_BUG_ON(xa, !xa_empty(xa));1219 }1220 }1221}1222 1223static noinline void check_multi_find_3(struct xarray *xa)1224{1225 unsigned int order;1226 1227 for (order = 5; order < order_limit; order++) {1228 unsigned long index = 1UL << (order - 5);1229 1230 XA_BUG_ON(xa, !xa_empty(xa));1231 xa_store_order(xa, 0, order - 4, xa_mk_index(0), GFP_KERNEL);1232 XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT));1233 xa_erase_index(xa, 0);1234 }1235}1236 1237static noinline void check_find_1(struct xarray *xa)1238{1239 unsigned long i, j, k;1240 1241 XA_BUG_ON(xa, !xa_empty(xa));1242 1243 /*1244 * Check xa_find with all pairs between 0 and 99 inclusive,1245 * starting at every index between 0 and 991246 */1247 for (i = 0; i < 100; i++) {1248 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);1249 xa_set_mark(xa, i, XA_MARK_0);1250 for (j = 0; j < i; j++) {1251 XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) !=1252 NULL);1253 xa_set_mark(xa, j, XA_MARK_0);1254 for (k = 0; k < 100; k++) {1255 unsigned long index = k;1256 void *entry = xa_find(xa, &index, ULONG_MAX,1257 XA_PRESENT);1258 if (k <= j)1259 XA_BUG_ON(xa, index != j);1260 else if (k <= i)1261 XA_BUG_ON(xa, index != i);1262 else1263 XA_BUG_ON(xa, entry != NULL);1264 1265 index = k;1266 entry = xa_find(xa, &index, ULONG_MAX,1267 XA_MARK_0);1268 if (k <= j)1269 XA_BUG_ON(xa, index != j);1270 else if (k <= i)1271 XA_BUG_ON(xa, index != i);1272 else1273 XA_BUG_ON(xa, entry != NULL);1274 }1275 xa_erase_index(xa, j);1276 XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0));1277 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));1278 }1279 xa_erase_index(xa, i);1280 XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0));1281 }1282 XA_BUG_ON(xa, !xa_empty(xa));1283}1284 1285static noinline void check_find_2(struct xarray *xa)1286{1287 void *entry;1288 unsigned long i, j, index;1289 1290 xa_for_each(xa, index, entry) {1291 XA_BUG_ON(xa, true);1292 }1293 1294 for (i = 0; i < 1024; i++) {1295 xa_store_index(xa, index, GFP_KERNEL);1296 j = 0;1297 xa_for_each(xa, index, entry) {1298 XA_BUG_ON(xa, xa_mk_index(index) != entry);1299 XA_BUG_ON(xa, index != j++);1300 }1301 }1302 1303 xa_destroy(xa);1304}1305 1306static noinline void check_find_3(struct xarray *xa)1307{1308 XA_STATE(xas, xa, 0);1309 unsigned long i, j, k;1310 void *entry;1311 1312 for (i = 0; i < 100; i++) {1313 for (j = 0; j < 100; j++) {1314 rcu_read_lock();1315 for (k = 0; k < 100; k++) {1316 xas_set(&xas, j);1317 xas_for_each_marked(&xas, entry, k, XA_MARK_0)1318 ;1319 if (j > k)1320 XA_BUG_ON(xa,1321 xas.xa_node != XAS_RESTART);1322 }1323 rcu_read_unlock();1324 }1325 xa_store_index(xa, i, GFP_KERNEL);1326 xa_set_mark(xa, i, XA_MARK_0);1327 }1328 xa_destroy(xa);1329}1330 1331static noinline void check_find_4(struct xarray *xa)1332{1333 unsigned long index = 0;1334 void *entry;1335 1336 xa_store_index(xa, ULONG_MAX, GFP_KERNEL);1337 1338 entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);1339 XA_BUG_ON(xa, entry != xa_mk_index(ULONG_MAX));1340 1341 entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);1342 XA_BUG_ON(xa, entry);1343 1344 xa_erase_index(xa, ULONG_MAX);1345}1346 1347static noinline void check_find(struct xarray *xa)1348{1349 unsigned i;1350 1351 check_find_1(xa);1352 check_find_2(xa);1353 check_find_3(xa);1354 check_find_4(xa);1355 1356 for (i = 2; i < 10; i++)1357 check_multi_find_1(xa, i);1358 check_multi_find_2(xa);1359 check_multi_find_3(xa);1360}1361 1362/* See find_swap_entry() in mm/shmem.c */1363static noinline unsigned long xa_find_entry(struct xarray *xa, void *item)1364{1365 XA_STATE(xas, xa, 0);1366 unsigned int checked = 0;1367 void *entry;1368 1369 rcu_read_lock();1370 xas_for_each(&xas, entry, ULONG_MAX) {1371 if (xas_retry(&xas, entry))1372 continue;1373 if (entry == item)1374 break;1375 checked++;1376 if ((checked % 4) != 0)1377 continue;1378 xas_pause(&xas);1379 }1380 rcu_read_unlock();1381 1382 return entry ? xas.xa_index : -1;1383}1384 1385static noinline void check_find_entry(struct xarray *xa)1386{1387#ifdef CONFIG_XARRAY_MULTI1388 unsigned int order;1389 unsigned long offset, index;1390 1391 for (order = 0; order < 20; order++) {1392 for (offset = 0; offset < (1UL << (order + 3));1393 offset += (1UL << order)) {1394 for (index = 0; index < (1UL << (order + 5));1395 index += (1UL << order)) {1396 xa_store_order(xa, index, order,1397 xa_mk_index(index), GFP_KERNEL);1398 XA_BUG_ON(xa, xa_load(xa, index) !=1399 xa_mk_index(index));1400 XA_BUG_ON(xa, xa_find_entry(xa,1401 xa_mk_index(index)) != index);1402 }1403 XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);1404 xa_destroy(xa);1405 }1406 }1407#endif1408 1409 XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);1410 xa_store_index(xa, ULONG_MAX, GFP_KERNEL);1411 XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);1412 XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_index(ULONG_MAX)) != -1);1413 xa_erase_index(xa, ULONG_MAX);1414 XA_BUG_ON(xa, !xa_empty(xa));1415}1416 1417static noinline void check_pause(struct xarray *xa)1418{1419 XA_STATE(xas, xa, 0);1420 void *entry;1421 unsigned int order;1422 unsigned long index = 1;1423 unsigned int count = 0;1424 1425 for (order = 0; order < order_limit; order++) {1426 XA_BUG_ON(xa, xa_store_order(xa, index, order,1427 xa_mk_index(index), GFP_KERNEL));1428 index += 1UL << order;1429 }1430 1431 rcu_read_lock();1432 xas_for_each(&xas, entry, ULONG_MAX) {1433 XA_BUG_ON(xa, entry != xa_mk_index(1UL << count));1434 count++;1435 }1436 rcu_read_unlock();1437 XA_BUG_ON(xa, count != order_limit);1438 1439 count = 0;1440 xas_set(&xas, 0);1441 rcu_read_lock();1442 xas_for_each(&xas, entry, ULONG_MAX) {1443 XA_BUG_ON(xa, entry != xa_mk_index(1UL << count));1444 count++;1445 xas_pause(&xas);1446 }1447 rcu_read_unlock();1448 XA_BUG_ON(xa, count != order_limit);1449 1450 xa_destroy(xa);1451}1452 1453static noinline void check_move_tiny(struct xarray *xa)1454{1455 XA_STATE(xas, xa, 0);1456 1457 XA_BUG_ON(xa, !xa_empty(xa));1458 rcu_read_lock();1459 XA_BUG_ON(xa, xas_next(&xas) != NULL);1460 XA_BUG_ON(xa, xas_next(&xas) != NULL);1461 rcu_read_unlock();1462 xa_store_index(xa, 0, GFP_KERNEL);1463 rcu_read_lock();1464 xas_set(&xas, 0);1465 XA_BUG_ON(xa, xas_next(&xas) != xa_mk_index(0));1466 XA_BUG_ON(xa, xas_next(&xas) != NULL);1467 xas_set(&xas, 0);1468 XA_BUG_ON(xa, xas_prev(&xas) != xa_mk_index(0));1469 XA_BUG_ON(xa, xas_prev(&xas) != NULL);1470 rcu_read_unlock();1471 xa_erase_index(xa, 0);1472 XA_BUG_ON(xa, !xa_empty(xa));1473}1474 1475static noinline void check_move_max(struct xarray *xa)1476{1477 XA_STATE(xas, xa, 0);1478 1479 xa_store_index(xa, ULONG_MAX, GFP_KERNEL);1480 rcu_read_lock();1481 XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));1482 XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);1483 rcu_read_unlock();1484 1485 xas_set(&xas, 0);1486 rcu_read_lock();1487 XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));1488 xas_pause(&xas);1489 XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);1490 rcu_read_unlock();1491 1492 xa_erase_index(xa, ULONG_MAX);1493 XA_BUG_ON(xa, !xa_empty(xa));1494}1495 1496static noinline void check_move_small(struct xarray *xa, unsigned long idx)1497{1498 XA_STATE(xas, xa, 0);1499 unsigned long i;1500 1501 xa_store_index(xa, 0, GFP_KERNEL);1502 xa_store_index(xa, idx, GFP_KERNEL);1503 1504 rcu_read_lock();1505 for (i = 0; i < idx * 4; i++) {1506 void *entry = xas_next(&xas);1507 if (i <= idx)1508 XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);1509 XA_BUG_ON(xa, xas.xa_index != i);1510 if (i == 0 || i == idx)1511 XA_BUG_ON(xa, entry != xa_mk_index(i));1512 else1513 XA_BUG_ON(xa, entry != NULL);1514 }1515 xas_next(&xas);1516 XA_BUG_ON(xa, xas.xa_index != i);1517 1518 do {1519 void *entry = xas_prev(&xas);1520 i--;1521 if (i <= idx)1522 XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);1523 XA_BUG_ON(xa, xas.xa_index != i);1524 if (i == 0 || i == idx)1525 XA_BUG_ON(xa, entry != xa_mk_index(i));1526 else1527 XA_BUG_ON(xa, entry != NULL);1528 } while (i > 0);1529 1530 xas_set(&xas, ULONG_MAX);1531 XA_BUG_ON(xa, xas_next(&xas) != NULL);1532 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);1533 XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0));1534 XA_BUG_ON(xa, xas.xa_index != 0);1535 XA_BUG_ON(xa, xas_prev(&xas) != NULL);1536 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);1537 rcu_read_unlock();1538 1539 xa_erase_index(xa, 0);1540 xa_erase_index(xa, idx);1541 XA_BUG_ON(xa, !xa_empty(xa));1542}1543 1544static noinline void check_move(struct xarray *xa)1545{1546 XA_STATE(xas, xa, (1 << 16) - 1);1547 unsigned long i;1548 1549 for (i = 0; i < (1 << 16); i++)1550 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);1551 1552 rcu_read_lock();1553 do {1554 void *entry = xas_prev(&xas);1555 i--;1556 XA_BUG_ON(xa, entry != xa_mk_index(i));1557 XA_BUG_ON(xa, i != xas.xa_index);1558 } while (i != 0);1559 1560 XA_BUG_ON(xa, xas_prev(&xas) != NULL);1561 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);1562 1563 do {1564 void *entry = xas_next(&xas);1565 XA_BUG_ON(xa, entry != xa_mk_index(i));1566 XA_BUG_ON(xa, i != xas.xa_index);1567 i++;1568 } while (i < (1 << 16));1569 rcu_read_unlock();1570 1571 for (i = (1 << 8); i < (1 << 15); i++)1572 xa_erase_index(xa, i);1573 1574 i = xas.xa_index;1575 1576 rcu_read_lock();1577 do {1578 void *entry = xas_prev(&xas);1579 i--;1580 if ((i < (1 << 8)) || (i >= (1 << 15)))1581 XA_BUG_ON(xa, entry != xa_mk_index(i));1582 else1583 XA_BUG_ON(xa, entry != NULL);1584 XA_BUG_ON(xa, i != xas.xa_index);1585 } while (i != 0);1586 1587 XA_BUG_ON(xa, xas_prev(&xas) != NULL);1588 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);1589 1590 do {1591 void *entry = xas_next(&xas);1592 if ((i < (1 << 8)) || (i >= (1 << 15)))1593 XA_BUG_ON(xa, entry != xa_mk_index(i));1594 else1595 XA_BUG_ON(xa, entry != NULL);1596 XA_BUG_ON(xa, i != xas.xa_index);1597 i++;1598 } while (i < (1 << 16));1599 rcu_read_unlock();1600 1601 xa_destroy(xa);1602 1603 check_move_tiny(xa);1604 check_move_max(xa);1605 1606 for (i = 0; i < 16; i++)1607 check_move_small(xa, 1UL << i);1608 1609 for (i = 2; i < 16; i++)1610 check_move_small(xa, (1UL << i) - 1);1611}1612 1613static noinline void xa_store_many_order(struct xarray *xa,1614 unsigned long index, unsigned order)1615{1616 XA_STATE_ORDER(xas, xa, index, order);1617 unsigned int i = 0;1618 1619 do {1620 xas_lock(&xas);1621 XA_BUG_ON(xa, xas_find_conflict(&xas));1622 xas_create_range(&xas);1623 if (xas_error(&xas))1624 goto unlock;1625 for (i = 0; i < (1U << order); i++) {1626 XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(index + i)));1627 xas_next(&xas);1628 }1629unlock:1630 xas_unlock(&xas);1631 } while (xas_nomem(&xas, GFP_KERNEL));1632 1633 XA_BUG_ON(xa, xas_error(&xas));1634}1635 1636static noinline void check_create_range_1(struct xarray *xa,1637 unsigned long index, unsigned order)1638{1639 unsigned long i;1640 1641 xa_store_many_order(xa, index, order);1642 for (i = index; i < index + (1UL << order); i++)1643 xa_erase_index(xa, i);1644 XA_BUG_ON(xa, !xa_empty(xa));1645}1646 1647static noinline void check_create_range_2(struct xarray *xa, unsigned order)1648{1649 unsigned long i;1650 unsigned long nr = 1UL << order;1651 1652 for (i = 0; i < nr * nr; i += nr)1653 xa_store_many_order(xa, i, order);1654 for (i = 0; i < nr * nr; i++)1655 xa_erase_index(xa, i);1656 XA_BUG_ON(xa, !xa_empty(xa));1657}1658 1659static noinline void check_create_range_3(void)1660{1661 XA_STATE(xas, NULL, 0);1662 xas_set_err(&xas, -EEXIST);1663 xas_create_range(&xas);1664 XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST);1665}1666 1667static noinline void check_create_range_4(struct xarray *xa,1668 unsigned long index, unsigned order)1669{1670 XA_STATE_ORDER(xas, xa, index, order);1671 unsigned long base = xas.xa_index;1672 unsigned long i = 0;1673 1674 xa_store_index(xa, index, GFP_KERNEL);1675 do {1676 xas_lock(&xas);1677 xas_create_range(&xas);1678 if (xas_error(&xas))1679 goto unlock;1680 for (i = 0; i < (1UL << order); i++) {1681 void *old = xas_store(&xas, xa_mk_index(base + i));1682 if (xas.xa_index == index)1683 XA_BUG_ON(xa, old != xa_mk_index(base + i));1684 else1685 XA_BUG_ON(xa, old != NULL);1686 xas_next(&xas);1687 }1688unlock:1689 xas_unlock(&xas);1690 } while (xas_nomem(&xas, GFP_KERNEL));1691 1692 XA_BUG_ON(xa, xas_error(&xas));1693 1694 for (i = base; i < base + (1UL << order); i++)1695 xa_erase_index(xa, i);1696 XA_BUG_ON(xa, !xa_empty(xa));1697}1698 1699static noinline void check_create_range_5(struct xarray *xa,1700 unsigned long index, unsigned int order)1701{1702 XA_STATE_ORDER(xas, xa, index, order);1703 unsigned int i;1704 1705 xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);1706 1707 for (i = 0; i < order + 10; i++) {1708 do {1709 xas_lock(&xas);1710 xas_create_range(&xas);1711 xas_unlock(&xas);1712 } while (xas_nomem(&xas, GFP_KERNEL));1713 }1714 1715 xa_destroy(xa);1716}1717 1718static noinline void check_create_range(struct xarray *xa)1719{1720 unsigned int order;1721 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1;1722 1723 for (order = 0; order < max_order; order++) {1724 check_create_range_1(xa, 0, order);1725 check_create_range_1(xa, 1U << order, order);1726 check_create_range_1(xa, 2U << order, order);1727 check_create_range_1(xa, 3U << order, order);1728 check_create_range_1(xa, 1U << 24, order);1729 if (order < 10)1730 check_create_range_2(xa, order);1731 1732 check_create_range_4(xa, 0, order);1733 check_create_range_4(xa, 1U << order, order);1734 check_create_range_4(xa, 2U << order, order);1735 check_create_range_4(xa, 3U << order, order);1736 check_create_range_4(xa, 1U << 24, order);1737 1738 check_create_range_4(xa, 1, order);1739 check_create_range_4(xa, (1U << order) + 1, order);1740 check_create_range_4(xa, (2U << order) + 1, order);1741 check_create_range_4(xa, (2U << order) - 1, order);1742 check_create_range_4(xa, (3U << order) + 1, order);1743 check_create_range_4(xa, (3U << order) - 1, order);1744 check_create_range_4(xa, (1U << 24) + 1, order);1745 1746 check_create_range_5(xa, 0, order);1747 check_create_range_5(xa, (1U << order), order);1748 }1749 1750 check_create_range_3();1751}1752 1753static noinline void __check_store_range(struct xarray *xa, unsigned long first,1754 unsigned long last)1755{1756#ifdef CONFIG_XARRAY_MULTI1757 xa_store_range(xa, first, last, xa_mk_index(first), GFP_KERNEL);1758 1759 XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_index(first));1760 XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_index(first));1761 XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL);1762 XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL);1763 1764 xa_store_range(xa, first, last, NULL, GFP_KERNEL);1765#endif1766 1767 XA_BUG_ON(xa, !xa_empty(xa));1768}1769 1770static noinline void check_store_range(struct xarray *xa)1771{1772 unsigned long i, j;1773 1774 for (i = 0; i < 128; i++) {1775 for (j = i; j < 128; j++) {1776 __check_store_range(xa, i, j);1777 __check_store_range(xa, 128 + i, 128 + j);1778 __check_store_range(xa, 4095 + i, 4095 + j);1779 __check_store_range(xa, 4096 + i, 4096 + j);1780 __check_store_range(xa, 123456 + i, 123456 + j);1781 __check_store_range(xa, (1 << 24) + i, (1 << 24) + j);1782 }1783 }1784}1785 1786#ifdef CONFIG_XARRAY_MULTI1787static void check_split_1(struct xarray *xa, unsigned long index,1788 unsigned int order, unsigned int new_order)1789{1790 XA_STATE_ORDER(xas, xa, index, new_order);1791 unsigned int i, found;1792 void *entry;1793 1794 xa_store_order(xa, index, order, xa, GFP_KERNEL);1795 xa_set_mark(xa, index, XA_MARK_1);1796 1797 xas_split_alloc(&xas, xa, order, GFP_KERNEL);1798 xas_lock(&xas);1799 xas_split(&xas, xa, order);1800 for (i = 0; i < (1 << order); i += (1 << new_order))1801 __xa_store(xa, index + i, xa_mk_index(index + i), 0);1802 xas_unlock(&xas);1803 1804 for (i = 0; i < (1 << order); i++) {1805 unsigned int val = index + (i & ~((1 << new_order) - 1));1806 XA_BUG_ON(xa, xa_load(xa, index + i) != xa_mk_index(val));1807 }1808 1809 xa_set_mark(xa, index, XA_MARK_0);1810 XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));1811 1812 xas_set_order(&xas, index, 0);1813 found = 0;1814 rcu_read_lock();1815 xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_1) {1816 found++;1817 XA_BUG_ON(xa, xa_is_internal(entry));1818 }1819 rcu_read_unlock();1820 XA_BUG_ON(xa, found != 1 << (order - new_order));1821 1822 xa_destroy(xa);1823}1824 1825static noinline void check_split(struct xarray *xa)1826{1827 unsigned int order, new_order;1828 1829 XA_BUG_ON(xa, !xa_empty(xa));1830 1831 for (order = 1; order < 2 * XA_CHUNK_SHIFT; order++) {1832 for (new_order = 0; new_order < order; new_order++) {1833 check_split_1(xa, 0, order, new_order);1834 check_split_1(xa, 1UL << order, order, new_order);1835 check_split_1(xa, 3UL << order, order, new_order);1836 }1837 }1838}1839#else1840static void check_split(struct xarray *xa) { }1841#endif1842 1843static void check_align_1(struct xarray *xa, char *name)1844{1845 int i;1846 unsigned int id;1847 unsigned long index;1848 void *entry;1849 1850 for (i = 0; i < 8; i++) {1851 XA_BUG_ON(xa, xa_alloc(xa, &id, name + i, xa_limit_32b,1852 GFP_KERNEL) != 0);1853 XA_BUG_ON(xa, id != i);1854 }1855 xa_for_each(xa, index, entry)1856 XA_BUG_ON(xa, xa_is_err(entry));1857 xa_destroy(xa);1858}1859 1860/*1861 * We should always be able to store without allocating memory after1862 * reserving a slot.1863 */1864static void check_align_2(struct xarray *xa, char *name)1865{1866 int i;1867 1868 XA_BUG_ON(xa, !xa_empty(xa));1869 1870 for (i = 0; i < 8; i++) {1871 XA_BUG_ON(xa, xa_store(xa, 0, name + i, GFP_KERNEL) != NULL);1872 xa_erase(xa, 0);1873 }1874 1875 for (i = 0; i < 8; i++) {1876 XA_BUG_ON(xa, xa_reserve(xa, 0, GFP_KERNEL) != 0);1877 XA_BUG_ON(xa, xa_store(xa, 0, name + i, 0) != NULL);1878 xa_erase(xa, 0);1879 }1880 1881 XA_BUG_ON(xa, !xa_empty(xa));1882}1883 1884static noinline void check_align(struct xarray *xa)1885{1886 char name[] = "Motorola 68000";1887 1888 check_align_1(xa, name);1889 check_align_1(xa, name + 1);1890 check_align_1(xa, name + 2);1891 check_align_1(xa, name + 3);1892 check_align_2(xa, name);1893}1894 1895static LIST_HEAD(shadow_nodes);1896 1897static void test_update_node(struct xa_node *node)1898{1899 if (node->count && node->count == node->nr_values) {1900 if (list_empty(&node->private_list))1901 list_add(&shadow_nodes, &node->private_list);1902 } else {1903 if (!list_empty(&node->private_list))1904 list_del_init(&node->private_list);1905 }1906}1907 1908static noinline void shadow_remove(struct xarray *xa)1909{1910 struct xa_node *node;1911 1912 xa_lock(xa);1913 while ((node = list_first_entry_or_null(&shadow_nodes,1914 struct xa_node, private_list))) {1915 XA_BUG_ON(xa, node->array != xa);1916 list_del_init(&node->private_list);1917 xa_delete_node(node, test_update_node);1918 }1919 xa_unlock(xa);1920}1921 1922static noinline void check_workingset(struct xarray *xa, unsigned long index)1923{1924 XA_STATE(xas, xa, index);1925 xas_set_update(&xas, test_update_node);1926 1927 do {1928 xas_lock(&xas);1929 xas_store(&xas, xa_mk_value(0));1930 xas_next(&xas);1931 xas_store(&xas, xa_mk_value(1));1932 xas_unlock(&xas);1933 } while (xas_nomem(&xas, GFP_KERNEL));1934 1935 XA_BUG_ON(xa, list_empty(&shadow_nodes));1936 1937 xas_lock(&xas);1938 xas_next(&xas);1939 xas_store(&xas, &xas);1940 XA_BUG_ON(xa, !list_empty(&shadow_nodes));1941 1942 xas_store(&xas, xa_mk_value(2));1943 xas_unlock(&xas);1944 XA_BUG_ON(xa, list_empty(&shadow_nodes));1945 1946 shadow_remove(xa);1947 XA_BUG_ON(xa, !list_empty(&shadow_nodes));1948 XA_BUG_ON(xa, !xa_empty(xa));1949}1950 1951/*1952 * Check that the pointer / value / sibling entries are accounted the1953 * way we expect them to be.1954 */1955static noinline void check_account(struct xarray *xa)1956{1957#ifdef CONFIG_XARRAY_MULTI1958 unsigned int order;1959 1960 for (order = 1; order < 12; order++) {1961 XA_STATE(xas, xa, 1 << order);1962 1963 xa_store_order(xa, 0, order, xa, GFP_KERNEL);1964 rcu_read_lock();1965 xas_load(&xas);1966 XA_BUG_ON(xa, xas.xa_node->count == 0);1967 XA_BUG_ON(xa, xas.xa_node->count > (1 << order));1968 XA_BUG_ON(xa, xas.xa_node->nr_values != 0);1969 rcu_read_unlock();1970 1971 xa_store_order(xa, 1 << order, order, xa_mk_index(1UL << order),1972 GFP_KERNEL);1973 XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2);1974 1975 xa_erase(xa, 1 << order);1976 XA_BUG_ON(xa, xas.xa_node->nr_values != 0);1977 1978 xa_erase(xa, 0);1979 XA_BUG_ON(xa, !xa_empty(xa));1980 }1981#endif1982}1983 1984static noinline void check_get_order(struct xarray *xa)1985{1986 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;1987 unsigned int order;1988 unsigned long i, j;1989 1990 for (i = 0; i < 3; i++)1991 XA_BUG_ON(xa, xa_get_order(xa, i) != 0);1992 1993 for (order = 0; order < max_order; order++) {1994 for (i = 0; i < 10; i++) {1995 xa_store_order(xa, i << order, order,1996 xa_mk_index(i << order), GFP_KERNEL);1997 for (j = i << order; j < (i + 1) << order; j++)1998 XA_BUG_ON(xa, xa_get_order(xa, j) != order);1999 xa_erase(xa, i << order);2000 }2001 }2002}2003 2004static noinline void check_xas_get_order(struct xarray *xa)2005{2006 XA_STATE(xas, xa, 0);2007 2008 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;2009 unsigned int order;2010 unsigned long i, j;2011 2012 for (order = 0; order < max_order; order++) {2013 for (i = 0; i < 10; i++) {2014 xas_set_order(&xas, i << order, order);2015 do {2016 xas_lock(&xas);2017 xas_store(&xas, xa_mk_value(i));2018 xas_unlock(&xas);2019 } while (xas_nomem(&xas, GFP_KERNEL));2020 2021 for (j = i << order; j < (i + 1) << order; j++) {2022 xas_set_order(&xas, j, 0);2023 rcu_read_lock();2024 xas_load(&xas);2025 XA_BUG_ON(xa, xas_get_order(&xas) != order);2026 rcu_read_unlock();2027 }2028 2029 xas_lock(&xas);2030 xas_set_order(&xas, i << order, order);2031 xas_store(&xas, NULL);2032 xas_unlock(&xas);2033 }2034 }2035}2036 2037static noinline void check_xas_conflict_get_order(struct xarray *xa)2038{2039 XA_STATE(xas, xa, 0);2040 2041 void *entry;2042 int only_once;2043 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;2044 unsigned int order;2045 unsigned long i, j, k;2046 2047 for (order = 0; order < max_order; order++) {2048 for (i = 0; i < 10; i++) {2049 xas_set_order(&xas, i << order, order);2050 do {2051 xas_lock(&xas);2052 xas_store(&xas, xa_mk_value(i));2053 xas_unlock(&xas);2054 } while (xas_nomem(&xas, GFP_KERNEL));2055 2056 /*2057 * Ensure xas_get_order works with xas_for_each_conflict.2058 */2059 j = i << order;2060 for (k = 0; k < order; k++) {2061 only_once = 0;2062 xas_set_order(&xas, j + (1 << k), k);2063 xas_lock(&xas);2064 xas_for_each_conflict(&xas, entry) {2065 XA_BUG_ON(xa, entry != xa_mk_value(i));2066 XA_BUG_ON(xa, xas_get_order(&xas) != order);2067 only_once++;2068 }2069 XA_BUG_ON(xa, only_once != 1);2070 xas_unlock(&xas);2071 }2072 2073 if (order < max_order - 1) {2074 only_once = 0;2075 xas_set_order(&xas, (i & ~1UL) << order, order + 1);2076 xas_lock(&xas);2077 xas_for_each_conflict(&xas, entry) {2078 XA_BUG_ON(xa, entry != xa_mk_value(i));2079 XA_BUG_ON(xa, xas_get_order(&xas) != order);2080 only_once++;2081 }2082 XA_BUG_ON(xa, only_once != 1);2083 xas_unlock(&xas);2084 }2085 2086 xas_set_order(&xas, i << order, order);2087 xas_lock(&xas);2088 xas_store(&xas, NULL);2089 xas_unlock(&xas);2090 }2091 }2092}2093 2094 2095static noinline void check_destroy(struct xarray *xa)2096{2097 unsigned long index;2098 2099 XA_BUG_ON(xa, !xa_empty(xa));2100 2101 /* Destroying an empty array is a no-op */2102 xa_destroy(xa);2103 XA_BUG_ON(xa, !xa_empty(xa));2104 2105 /* Destroying an array with a single entry */2106 for (index = 0; index < 1000; index++) {2107 xa_store_index(xa, index, GFP_KERNEL);2108 XA_BUG_ON(xa, xa_empty(xa));2109 xa_destroy(xa);2110 XA_BUG_ON(xa, !xa_empty(xa));2111 }2112 2113 /* Destroying an array with a single entry at ULONG_MAX */2114 xa_store(xa, ULONG_MAX, xa, GFP_KERNEL);2115 XA_BUG_ON(xa, xa_empty(xa));2116 xa_destroy(xa);2117 XA_BUG_ON(xa, !xa_empty(xa));2118 2119#ifdef CONFIG_XARRAY_MULTI2120 /* Destroying an array with a multi-index entry */2121 xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL);2122 XA_BUG_ON(xa, xa_empty(xa));2123 xa_destroy(xa);2124 XA_BUG_ON(xa, !xa_empty(xa));2125#endif2126}2127 2128static DEFINE_XARRAY(array);2129 2130static int xarray_checks(void)2131{2132 check_xa_err(&array);2133 check_xas_retry(&array);2134 check_xa_load(&array);2135 check_xa_mark(&array);2136 check_xa_shrink(&array);2137 check_xas_erase(&array);2138 check_insert(&array);2139 check_cmpxchg(&array);2140 check_cmpxchg_order(&array);2141 check_reserve(&array);2142 check_reserve(&xa0);2143 check_multi_store(&array);2144 check_multi_store_advanced(&array);2145 check_get_order(&array);2146 check_xas_get_order(&array);2147 check_xas_conflict_get_order(&array);2148 check_xa_alloc();2149 check_find(&array);2150 check_find_entry(&array);2151 check_pause(&array);2152 check_account(&array);2153 check_destroy(&array);2154 check_move(&array);2155 check_create_range(&array);2156 check_store_range(&array);2157 check_store_iter(&array);2158 check_align(&xa0);2159 check_split(&array);2160 2161 check_workingset(&array, 0);2162 check_workingset(&array, 64);2163 check_workingset(&array, 4096);2164 2165 printk("XArray: %u of %u tests passed\n", tests_passed, tests_run);2166 return (tests_run == tests_passed) ? 0 : -EINVAL;2167}2168 2169static void xarray_exit(void)2170{2171}2172 2173module_init(xarray_checks);2174module_exit(xarray_exit);2175MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");2176MODULE_DESCRIPTION("XArray API test module");2177MODULE_LICENSE("GPL");2178