Linux Audio

Check our new training course

Loading...
v5.14.15
   1// SPDX-License-Identifier: GPL-2.0+
   2/*
   3 * test_xarray.c: Test the XArray API
   4 * Copyright (c) 2017-2018 Microsoft Corporation
   5 * Copyright (c) 2019-2020 Oracle
   6 * 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_DEBUG
  19# ifdef __KERNEL__
  20void xa_dump(const struct xarray *xa) { }
  21# endif
  22#undef XA_BUG_ON
  23#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#endif
  34
  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 current
  68 * users outside the test suite because all current multislot users want
  69 * 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#endif
  95	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			else
 157				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			else
 168				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 the
 204	 * entire entry the union of the marks
 205	 */
 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_MULTI
 295	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#endif
 311}
 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 properly
 337	 * 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_reserve(struct xarray *xa)
 427{
 428	void *entry;
 429	unsigned long index;
 430	int count;
 431
 432	/* An array with a reserved entry is not empty */
 433	XA_BUG_ON(xa, !xa_empty(xa));
 434	XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
 435	XA_BUG_ON(xa, xa_empty(xa));
 436	XA_BUG_ON(xa, xa_load(xa, 12345678));
 437	xa_release(xa, 12345678);
 438	XA_BUG_ON(xa, !xa_empty(xa));
 439
 440	/* Releasing a used entry does nothing */
 441	XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
 442	XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL);
 443	xa_release(xa, 12345678);
 444	xa_erase_index(xa, 12345678);
 445	XA_BUG_ON(xa, !xa_empty(xa));
 446
 447	/* cmpxchg sees a reserved entry as ZERO */
 448	XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
 449	XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, XA_ZERO_ENTRY,
 450				xa_mk_value(12345678), GFP_NOWAIT) != NULL);
 451	xa_release(xa, 12345678);
 452	xa_erase_index(xa, 12345678);
 453	XA_BUG_ON(xa, !xa_empty(xa));
 454
 455	/* xa_insert treats it as busy */
 456	XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
 457	XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) !=
 458			-EBUSY);
 459	XA_BUG_ON(xa, xa_empty(xa));
 460	XA_BUG_ON(xa, xa_erase(xa, 12345678) != NULL);
 461	XA_BUG_ON(xa, !xa_empty(xa));
 462
 463	/* Can iterate through a reserved entry */
 464	xa_store_index(xa, 5, GFP_KERNEL);
 465	XA_BUG_ON(xa, xa_reserve(xa, 6, GFP_KERNEL) != 0);
 466	xa_store_index(xa, 7, GFP_KERNEL);
 467
 468	count = 0;
 469	xa_for_each(xa, index, entry) {
 470		XA_BUG_ON(xa, index != 5 && index != 7);
 471		count++;
 472	}
 473	XA_BUG_ON(xa, count != 2);
 474
 475	/* If we free a reserved entry, we should be able to allocate it */
 476	if (xa->xa_flags & XA_FLAGS_ALLOC) {
 477		u32 id;
 478
 479		XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(8),
 480					XA_LIMIT(5, 10), GFP_KERNEL) != 0);
 481		XA_BUG_ON(xa, id != 8);
 482
 483		xa_release(xa, 6);
 484		XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(6),
 485					XA_LIMIT(5, 10), GFP_KERNEL) != 0);
 486		XA_BUG_ON(xa, id != 6);
 487	}
 488
 489	xa_destroy(xa);
 490}
 491
 492static noinline void check_xas_erase(struct xarray *xa)
 493{
 494	XA_STATE(xas, xa, 0);
 495	void *entry;
 496	unsigned long i, j;
 497
 498	for (i = 0; i < 200; i++) {
 499		for (j = i; j < 2 * i + 17; j++) {
 500			xas_set(&xas, j);
 501			do {
 502				xas_lock(&xas);
 503				xas_store(&xas, xa_mk_index(j));
 504				xas_unlock(&xas);
 505			} while (xas_nomem(&xas, GFP_KERNEL));
 506		}
 507
 508		xas_set(&xas, ULONG_MAX);
 509		do {
 510			xas_lock(&xas);
 511			xas_store(&xas, xa_mk_value(0));
 512			xas_unlock(&xas);
 513		} while (xas_nomem(&xas, GFP_KERNEL));
 514
 515		xas_lock(&xas);
 516		xas_store(&xas, NULL);
 517
 518		xas_set(&xas, 0);
 519		j = i;
 520		xas_for_each(&xas, entry, ULONG_MAX) {
 521			XA_BUG_ON(xa, entry != xa_mk_index(j));
 522			xas_store(&xas, NULL);
 523			j++;
 524		}
 525		xas_unlock(&xas);
 526		XA_BUG_ON(xa, !xa_empty(xa));
 527	}
 528}
 529
 530#ifdef CONFIG_XARRAY_MULTI
 531static noinline void check_multi_store_1(struct xarray *xa, unsigned long index,
 532		unsigned int order)
 533{
 534	XA_STATE(xas, xa, index);
 535	unsigned long min = index & ~((1UL << order) - 1);
 536	unsigned long max = min + (1UL << order);
 537
 538	xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
 539	XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(index));
 540	XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(index));
 541	XA_BUG_ON(xa, xa_load(xa, max) != NULL);
 542	XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
 543
 544	xas_lock(&xas);
 545	XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(min)) != xa_mk_index(index));
 546	xas_unlock(&xas);
 547	XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(min));
 548	XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(min));
 549	XA_BUG_ON(xa, xa_load(xa, max) != NULL);
 550	XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
 551
 552	xa_erase_index(xa, min);
 553	XA_BUG_ON(xa, !xa_empty(xa));
 554}
 555
 556static noinline void check_multi_store_2(struct xarray *xa, unsigned long index,
 557		unsigned int order)
 558{
 559	XA_STATE(xas, xa, index);
 560	xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL);
 561
 562	xas_lock(&xas);
 563	XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0));
 564	XA_BUG_ON(xa, xas.xa_index != index);
 565	XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
 566	xas_unlock(&xas);
 567	XA_BUG_ON(xa, !xa_empty(xa));
 568}
 569
 570static noinline void check_multi_store_3(struct xarray *xa, unsigned long index,
 571		unsigned int order)
 572{
 573	XA_STATE(xas, xa, 0);
 574	void *entry;
 575	int n = 0;
 576
 577	xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
 578
 579	xas_lock(&xas);
 580	xas_for_each(&xas, entry, ULONG_MAX) {
 581		XA_BUG_ON(xa, entry != xa_mk_index(index));
 582		n++;
 583	}
 584	XA_BUG_ON(xa, n != 1);
 585	xas_set(&xas, index + 1);
 586	xas_for_each(&xas, entry, ULONG_MAX) {
 587		XA_BUG_ON(xa, entry != xa_mk_index(index));
 588		n++;
 589	}
 590	XA_BUG_ON(xa, n != 2);
 591	xas_unlock(&xas);
 592
 593	xa_destroy(xa);
 594}
 595#endif
 596
 597static noinline void check_multi_store(struct xarray *xa)
 598{
 599#ifdef CONFIG_XARRAY_MULTI
 600	unsigned long i, j, k;
 601	unsigned int max_order = (sizeof(long) == 4) ? 30 : 60;
 602
 603	/* Loading from any position returns the same value */
 604	xa_store_order(xa, 0, 1, xa_mk_value(0), GFP_KERNEL);
 605	XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
 606	XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
 607	XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
 608	rcu_read_lock();
 609	XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 2);
 610	XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
 611	rcu_read_unlock();
 612
 613	/* Storing adjacent to the value does not alter the value */
 614	xa_store(xa, 3, xa, GFP_KERNEL);
 615	XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
 616	XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
 617	XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
 618	rcu_read_lock();
 619	XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 3);
 620	XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
 621	rcu_read_unlock();
 622
 623	/* Overwriting multiple indexes works */
 624	xa_store_order(xa, 0, 2, xa_mk_value(1), GFP_KERNEL);
 625	XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(1));
 626	XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(1));
 627	XA_BUG_ON(xa, xa_load(xa, 2) != xa_mk_value(1));
 628	XA_BUG_ON(xa, xa_load(xa, 3) != xa_mk_value(1));
 629	XA_BUG_ON(xa, xa_load(xa, 4) != NULL);
 630	rcu_read_lock();
 631	XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 4);
 632	XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 4);
 633	rcu_read_unlock();
 634
 635	/* We can erase multiple values with a single store */
 636	xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL);
 637	XA_BUG_ON(xa, !xa_empty(xa));
 638
 639	/* Even when the first slot is empty but the others aren't */
 640	xa_store_index(xa, 1, GFP_KERNEL);
 641	xa_store_index(xa, 2, GFP_KERNEL);
 642	xa_store_order(xa, 0, 2, NULL, GFP_KERNEL);
 643	XA_BUG_ON(xa, !xa_empty(xa));
 644
 645	for (i = 0; i < max_order; i++) {
 646		for (j = 0; j < max_order; j++) {
 647			xa_store_order(xa, 0, i, xa_mk_index(i), GFP_KERNEL);
 648			xa_store_order(xa, 0, j, xa_mk_index(j), GFP_KERNEL);
 649
 650			for (k = 0; k < max_order; k++) {
 651				void *entry = xa_load(xa, (1UL << k) - 1);
 652				if ((i < k) && (j < k))
 653					XA_BUG_ON(xa, entry != NULL);
 654				else
 655					XA_BUG_ON(xa, entry != xa_mk_index(j));
 656			}
 657
 658			xa_erase(xa, 0);
 659			XA_BUG_ON(xa, !xa_empty(xa));
 660		}
 661	}
 662
 663	for (i = 0; i < 20; i++) {
 664		check_multi_store_1(xa, 200, i);
 665		check_multi_store_1(xa, 0, i);
 666		check_multi_store_1(xa, (1UL << i) + 1, i);
 667	}
 668	check_multi_store_2(xa, 4095, 9);
 669
 670	for (i = 1; i < 20; i++) {
 671		check_multi_store_3(xa, 0, i);
 672		check_multi_store_3(xa, 1UL << i, i);
 673	}
 674#endif
 675}
 676
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 677static noinline void check_xa_alloc_1(struct xarray *xa, unsigned int base)
 678{
 679	int i;
 680	u32 id;
 681
 682	XA_BUG_ON(xa, !xa_empty(xa));
 683	/* An empty array should assign %base to the first alloc */
 684	xa_alloc_index(xa, base, GFP_KERNEL);
 685
 686	/* Erasing it should make the array empty again */
 687	xa_erase_index(xa, base);
 688	XA_BUG_ON(xa, !xa_empty(xa));
 689
 690	/* And it should assign %base again */
 691	xa_alloc_index(xa, base, GFP_KERNEL);
 692
 693	/* Allocating and then erasing a lot should not lose base */
 694	for (i = base + 1; i < 2 * XA_CHUNK_SIZE; i++)
 695		xa_alloc_index(xa, i, GFP_KERNEL);
 696	for (i = base; i < 2 * XA_CHUNK_SIZE; i++)
 697		xa_erase_index(xa, i);
 698	xa_alloc_index(xa, base, GFP_KERNEL);
 699
 700	/* Destroying the array should do the same as erasing */
 701	xa_destroy(xa);
 702
 703	/* And it should assign %base again */
 704	xa_alloc_index(xa, base, GFP_KERNEL);
 705
 706	/* The next assigned ID should be base+1 */
 707	xa_alloc_index(xa, base + 1, GFP_KERNEL);
 708	xa_erase_index(xa, base + 1);
 709
 710	/* Storing a value should mark it used */
 711	xa_store_index(xa, base + 1, GFP_KERNEL);
 712	xa_alloc_index(xa, base + 2, GFP_KERNEL);
 713
 714	/* If we then erase base, it should be free */
 715	xa_erase_index(xa, base);
 716	xa_alloc_index(xa, base, GFP_KERNEL);
 717
 718	xa_erase_index(xa, base + 1);
 719	xa_erase_index(xa, base + 2);
 720
 721	for (i = 1; i < 5000; i++) {
 722		xa_alloc_index(xa, base + i, GFP_KERNEL);
 723	}
 724
 725	xa_destroy(xa);
 726
 727	/* Check that we fail properly at the limit of allocation */
 728	XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX - 1),
 729				XA_LIMIT(UINT_MAX - 1, UINT_MAX),
 730				GFP_KERNEL) != 0);
 731	XA_BUG_ON(xa, id != 0xfffffffeU);
 732	XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX),
 733				XA_LIMIT(UINT_MAX - 1, UINT_MAX),
 734				GFP_KERNEL) != 0);
 735	XA_BUG_ON(xa, id != 0xffffffffU);
 736	id = 3;
 737	XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(0),
 738				XA_LIMIT(UINT_MAX - 1, UINT_MAX),
 739				GFP_KERNEL) != -EBUSY);
 740	XA_BUG_ON(xa, id != 3);
 741	xa_destroy(xa);
 742
 743	XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),
 744				GFP_KERNEL) != -EBUSY);
 745	XA_BUG_ON(xa, xa_store_index(xa, 3, GFP_KERNEL) != 0);
 746	XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),
 747				GFP_KERNEL) != -EBUSY);
 748	xa_erase_index(xa, 3);
 749	XA_BUG_ON(xa, !xa_empty(xa));
 750}
 751
 752static noinline void check_xa_alloc_2(struct xarray *xa, unsigned int base)
 753{
 754	unsigned int i, id;
 755	unsigned long index;
 756	void *entry;
 757
 758	/* Allocate and free a NULL and check xa_empty() behaves */
 759	XA_BUG_ON(xa, !xa_empty(xa));
 760	XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
 761	XA_BUG_ON(xa, id != base);
 762	XA_BUG_ON(xa, xa_empty(xa));
 763	XA_BUG_ON(xa, xa_erase(xa, id) != NULL);
 764	XA_BUG_ON(xa, !xa_empty(xa));
 765
 766	/* Ditto, but check destroy instead of erase */
 767	XA_BUG_ON(xa, !xa_empty(xa));
 768	XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
 769	XA_BUG_ON(xa, id != base);
 770	XA_BUG_ON(xa, xa_empty(xa));
 771	xa_destroy(xa);
 772	XA_BUG_ON(xa, !xa_empty(xa));
 773
 774	for (i = base; i < base + 10; i++) {
 775		XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b,
 776					GFP_KERNEL) != 0);
 777		XA_BUG_ON(xa, id != i);
 778	}
 779
 780	XA_BUG_ON(xa, xa_store(xa, 3, xa_mk_index(3), GFP_KERNEL) != NULL);
 781	XA_BUG_ON(xa, xa_store(xa, 4, xa_mk_index(4), GFP_KERNEL) != NULL);
 782	XA_BUG_ON(xa, xa_store(xa, 4, NULL, GFP_KERNEL) != xa_mk_index(4));
 783	XA_BUG_ON(xa, xa_erase(xa, 5) != NULL);
 784	XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
 785	XA_BUG_ON(xa, id != 5);
 786
 787	xa_for_each(xa, index, entry) {
 788		xa_erase_index(xa, index);
 789	}
 790
 791	for (i = base; i < base + 9; i++) {
 792		XA_BUG_ON(xa, xa_erase(xa, i) != NULL);
 793		XA_BUG_ON(xa, xa_empty(xa));
 794	}
 795	XA_BUG_ON(xa, xa_erase(xa, 8) != NULL);
 796	XA_BUG_ON(xa, xa_empty(xa));
 797	XA_BUG_ON(xa, xa_erase(xa, base + 9) != NULL);
 798	XA_BUG_ON(xa, !xa_empty(xa));
 799
 800	xa_destroy(xa);
 801}
 802
 803static noinline void check_xa_alloc_3(struct xarray *xa, unsigned int base)
 804{
 805	struct xa_limit limit = XA_LIMIT(1, 0x3fff);
 806	u32 next = 0;
 807	unsigned int i, id;
 808	unsigned long index;
 809	void *entry;
 810
 811	XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(1), limit,
 812				&next, GFP_KERNEL) != 0);
 813	XA_BUG_ON(xa, id != 1);
 814
 815	next = 0x3ffd;
 816	XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(0x3ffd), limit,
 817				&next, GFP_KERNEL) != 0);
 818	XA_BUG_ON(xa, id != 0x3ffd);
 819	xa_erase_index(xa, 0x3ffd);
 820	xa_erase_index(xa, 1);
 821	XA_BUG_ON(xa, !xa_empty(xa));
 822
 823	for (i = 0x3ffe; i < 0x4003; i++) {
 824		if (i < 0x4000)
 825			entry = xa_mk_index(i);
 826		else
 827			entry = xa_mk_index(i - 0x3fff);
 828		XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, entry, limit,
 829					&next, GFP_KERNEL) != (id == 1));
 830		XA_BUG_ON(xa, xa_mk_index(id) != entry);
 831	}
 832
 833	/* Check wrap-around is handled correctly */
 834	if (base != 0)
 835		xa_erase_index(xa, base);
 836	xa_erase_index(xa, base + 1);
 837	next = UINT_MAX;
 838	XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(UINT_MAX),
 839				xa_limit_32b, &next, GFP_KERNEL) != 0);
 840	XA_BUG_ON(xa, id != UINT_MAX);
 841	XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base),
 842				xa_limit_32b, &next, GFP_KERNEL) != 1);
 843	XA_BUG_ON(xa, id != base);
 844	XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base + 1),
 845				xa_limit_32b, &next, GFP_KERNEL) != 0);
 846	XA_BUG_ON(xa, id != base + 1);
 847
 848	xa_for_each(xa, index, entry)
 849		xa_erase_index(xa, index);
 850
 851	XA_BUG_ON(xa, !xa_empty(xa));
 852}
 853
 854static DEFINE_XARRAY_ALLOC(xa0);
 855static DEFINE_XARRAY_ALLOC1(xa1);
 856
 857static noinline void check_xa_alloc(void)
 858{
 859	check_xa_alloc_1(&xa0, 0);
 860	check_xa_alloc_1(&xa1, 1);
 861	check_xa_alloc_2(&xa0, 0);
 862	check_xa_alloc_2(&xa1, 1);
 863	check_xa_alloc_3(&xa0, 0);
 864	check_xa_alloc_3(&xa1, 1);
 865}
 866
 867static noinline void __check_store_iter(struct xarray *xa, unsigned long start,
 868			unsigned int order, unsigned int present)
 869{
 870	XA_STATE_ORDER(xas, xa, start, order);
 871	void *entry;
 872	unsigned int count = 0;
 873
 874retry:
 875	xas_lock(&xas);
 876	xas_for_each_conflict(&xas, entry) {
 877		XA_BUG_ON(xa, !xa_is_value(entry));
 878		XA_BUG_ON(xa, entry < xa_mk_index(start));
 879		XA_BUG_ON(xa, entry > xa_mk_index(start + (1UL << order) - 1));
 880		count++;
 881	}
 882	xas_store(&xas, xa_mk_index(start));
 883	xas_unlock(&xas);
 884	if (xas_nomem(&xas, GFP_KERNEL)) {
 885		count = 0;
 886		goto retry;
 887	}
 888	XA_BUG_ON(xa, xas_error(&xas));
 889	XA_BUG_ON(xa, count != present);
 890	XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_index(start));
 891	XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) !=
 892			xa_mk_index(start));
 893	xa_erase_index(xa, start);
 894}
 895
 896static noinline void check_store_iter(struct xarray *xa)
 897{
 898	unsigned int i, j;
 899	unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;
 900
 901	for (i = 0; i < max_order; i++) {
 902		unsigned int min = 1 << i;
 903		unsigned int max = (2 << i) - 1;
 904		__check_store_iter(xa, 0, i, 0);
 905		XA_BUG_ON(xa, !xa_empty(xa));
 906		__check_store_iter(xa, min, i, 0);
 907		XA_BUG_ON(xa, !xa_empty(xa));
 908
 909		xa_store_index(xa, min, GFP_KERNEL);
 910		__check_store_iter(xa, min, i, 1);
 911		XA_BUG_ON(xa, !xa_empty(xa));
 912		xa_store_index(xa, max, GFP_KERNEL);
 913		__check_store_iter(xa, min, i, 1);
 914		XA_BUG_ON(xa, !xa_empty(xa));
 915
 916		for (j = 0; j < min; j++)
 917			xa_store_index(xa, j, GFP_KERNEL);
 918		__check_store_iter(xa, 0, i, min);
 919		XA_BUG_ON(xa, !xa_empty(xa));
 920		for (j = 0; j < min; j++)
 921			xa_store_index(xa, min + j, GFP_KERNEL);
 922		__check_store_iter(xa, min, i, min);
 923		XA_BUG_ON(xa, !xa_empty(xa));
 924	}
 925#ifdef CONFIG_XARRAY_MULTI
 926	xa_store_index(xa, 63, GFP_KERNEL);
 927	xa_store_index(xa, 65, GFP_KERNEL);
 928	__check_store_iter(xa, 64, 2, 1);
 929	xa_erase_index(xa, 63);
 930#endif
 931	XA_BUG_ON(xa, !xa_empty(xa));
 932}
 933
 934static noinline void check_multi_find_1(struct xarray *xa, unsigned order)
 935{
 936#ifdef CONFIG_XARRAY_MULTI
 937	unsigned long multi = 3 << order;
 938	unsigned long next = 4 << order;
 939	unsigned long index;
 940
 941	xa_store_order(xa, multi, order, xa_mk_value(multi), GFP_KERNEL);
 942	XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL) != NULL);
 943	XA_BUG_ON(xa, xa_store_index(xa, next + 1, GFP_KERNEL) != NULL);
 944
 945	index = 0;
 946	XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
 947			xa_mk_value(multi));
 948	XA_BUG_ON(xa, index != multi);
 949	index = multi + 1;
 950	XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
 951			xa_mk_value(multi));
 952	XA_BUG_ON(xa, (index < multi) || (index >= next));
 953	XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) !=
 954			xa_mk_value(next));
 955	XA_BUG_ON(xa, index != next);
 956	XA_BUG_ON(xa, xa_find_after(xa, &index, next, XA_PRESENT) != NULL);
 957	XA_BUG_ON(xa, index != next);
 958
 959	xa_erase_index(xa, multi);
 960	xa_erase_index(xa, next);
 961	xa_erase_index(xa, next + 1);
 962	XA_BUG_ON(xa, !xa_empty(xa));
 963#endif
 964}
 965
 966static noinline void check_multi_find_2(struct xarray *xa)
 967{
 968	unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1;
 969	unsigned int i, j;
 970	void *entry;
 971
 972	for (i = 0; i < max_order; i++) {
 973		unsigned long index = 1UL << i;
 974		for (j = 0; j < index; j++) {
 975			XA_STATE(xas, xa, j + index);
 976			xa_store_index(xa, index - 1, GFP_KERNEL);
 977			xa_store_order(xa, index, i, xa_mk_index(index),
 978					GFP_KERNEL);
 979			rcu_read_lock();
 980			xas_for_each(&xas, entry, ULONG_MAX) {
 981				xa_erase_index(xa, index);
 982			}
 983			rcu_read_unlock();
 984			xa_erase_index(xa, index - 1);
 985			XA_BUG_ON(xa, !xa_empty(xa));
 986		}
 987	}
 988}
 989
 990static noinline void check_multi_find_3(struct xarray *xa)
 991{
 992	unsigned int order;
 993
 994	for (order = 5; order < order_limit; order++) {
 995		unsigned long index = 1UL << (order - 5);
 996
 997		XA_BUG_ON(xa, !xa_empty(xa));
 998		xa_store_order(xa, 0, order - 4, xa_mk_index(0), GFP_KERNEL);
 999		XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT));
1000		xa_erase_index(xa, 0);
1001	}
1002}
1003
1004static noinline void check_find_1(struct xarray *xa)
1005{
1006	unsigned long i, j, k;
1007
1008	XA_BUG_ON(xa, !xa_empty(xa));
1009
1010	/*
1011	 * Check xa_find with all pairs between 0 and 99 inclusive,
1012	 * starting at every index between 0 and 99
1013	 */
1014	for (i = 0; i < 100; i++) {
1015		XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
1016		xa_set_mark(xa, i, XA_MARK_0);
1017		for (j = 0; j < i; j++) {
1018			XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) !=
1019					NULL);
1020			xa_set_mark(xa, j, XA_MARK_0);
1021			for (k = 0; k < 100; k++) {
1022				unsigned long index = k;
1023				void *entry = xa_find(xa, &index, ULONG_MAX,
1024								XA_PRESENT);
1025				if (k <= j)
1026					XA_BUG_ON(xa, index != j);
1027				else if (k <= i)
1028					XA_BUG_ON(xa, index != i);
1029				else
1030					XA_BUG_ON(xa, entry != NULL);
1031
1032				index = k;
1033				entry = xa_find(xa, &index, ULONG_MAX,
1034								XA_MARK_0);
1035				if (k <= j)
1036					XA_BUG_ON(xa, index != j);
1037				else if (k <= i)
1038					XA_BUG_ON(xa, index != i);
1039				else
1040					XA_BUG_ON(xa, entry != NULL);
1041			}
1042			xa_erase_index(xa, j);
1043			XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0));
1044			XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
1045		}
1046		xa_erase_index(xa, i);
1047		XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0));
1048	}
1049	XA_BUG_ON(xa, !xa_empty(xa));
1050}
1051
1052static noinline void check_find_2(struct xarray *xa)
1053{
1054	void *entry;
1055	unsigned long i, j, index;
1056
1057	xa_for_each(xa, index, entry) {
1058		XA_BUG_ON(xa, true);
1059	}
1060
1061	for (i = 0; i < 1024; i++) {
1062		xa_store_index(xa, index, GFP_KERNEL);
1063		j = 0;
1064		xa_for_each(xa, index, entry) {
1065			XA_BUG_ON(xa, xa_mk_index(index) != entry);
1066			XA_BUG_ON(xa, index != j++);
1067		}
1068	}
1069
1070	xa_destroy(xa);
1071}
1072
1073static noinline void check_find_3(struct xarray *xa)
1074{
1075	XA_STATE(xas, xa, 0);
1076	unsigned long i, j, k;
1077	void *entry;
1078
1079	for (i = 0; i < 100; i++) {
1080		for (j = 0; j < 100; j++) {
1081			rcu_read_lock();
1082			for (k = 0; k < 100; k++) {
1083				xas_set(&xas, j);
1084				xas_for_each_marked(&xas, entry, k, XA_MARK_0)
1085					;
1086				if (j > k)
1087					XA_BUG_ON(xa,
1088						xas.xa_node != XAS_RESTART);
1089			}
1090			rcu_read_unlock();
1091		}
1092		xa_store_index(xa, i, GFP_KERNEL);
1093		xa_set_mark(xa, i, XA_MARK_0);
1094	}
1095	xa_destroy(xa);
1096}
1097
1098static noinline void check_find_4(struct xarray *xa)
1099{
1100	unsigned long index = 0;
1101	void *entry;
1102
1103	xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
1104
1105	entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);
1106	XA_BUG_ON(xa, entry != xa_mk_index(ULONG_MAX));
1107
1108	entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);
1109	XA_BUG_ON(xa, entry);
1110
1111	xa_erase_index(xa, ULONG_MAX);
1112}
1113
1114static noinline void check_find(struct xarray *xa)
1115{
1116	unsigned i;
1117
1118	check_find_1(xa);
1119	check_find_2(xa);
1120	check_find_3(xa);
1121	check_find_4(xa);
1122
1123	for (i = 2; i < 10; i++)
1124		check_multi_find_1(xa, i);
1125	check_multi_find_2(xa);
1126	check_multi_find_3(xa);
1127}
1128
1129/* See find_swap_entry() in mm/shmem.c */
1130static noinline unsigned long xa_find_entry(struct xarray *xa, void *item)
1131{
1132	XA_STATE(xas, xa, 0);
1133	unsigned int checked = 0;
1134	void *entry;
1135
1136	rcu_read_lock();
1137	xas_for_each(&xas, entry, ULONG_MAX) {
1138		if (xas_retry(&xas, entry))
1139			continue;
1140		if (entry == item)
1141			break;
1142		checked++;
1143		if ((checked % 4) != 0)
1144			continue;
1145		xas_pause(&xas);
1146	}
1147	rcu_read_unlock();
1148
1149	return entry ? xas.xa_index : -1;
1150}
1151
1152static noinline void check_find_entry(struct xarray *xa)
1153{
1154#ifdef CONFIG_XARRAY_MULTI
1155	unsigned int order;
1156	unsigned long offset, index;
1157
1158	for (order = 0; order < 20; order++) {
1159		for (offset = 0; offset < (1UL << (order + 3));
1160		     offset += (1UL << order)) {
1161			for (index = 0; index < (1UL << (order + 5));
1162			     index += (1UL << order)) {
1163				xa_store_order(xa, index, order,
1164						xa_mk_index(index), GFP_KERNEL);
1165				XA_BUG_ON(xa, xa_load(xa, index) !=
1166						xa_mk_index(index));
1167				XA_BUG_ON(xa, xa_find_entry(xa,
1168						xa_mk_index(index)) != index);
1169			}
1170			XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
1171			xa_destroy(xa);
1172		}
1173	}
1174#endif
1175
1176	XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
1177	xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
1178	XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
1179	XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_index(ULONG_MAX)) != -1);
1180	xa_erase_index(xa, ULONG_MAX);
1181	XA_BUG_ON(xa, !xa_empty(xa));
1182}
1183
1184static noinline void check_pause(struct xarray *xa)
1185{
1186	XA_STATE(xas, xa, 0);
1187	void *entry;
1188	unsigned int order;
1189	unsigned long index = 1;
1190	unsigned int count = 0;
1191
1192	for (order = 0; order < order_limit; order++) {
1193		XA_BUG_ON(xa, xa_store_order(xa, index, order,
1194					xa_mk_index(index), GFP_KERNEL));
1195		index += 1UL << order;
1196	}
1197
1198	rcu_read_lock();
1199	xas_for_each(&xas, entry, ULONG_MAX) {
1200		XA_BUG_ON(xa, entry != xa_mk_index(1UL << count));
1201		count++;
1202	}
1203	rcu_read_unlock();
1204	XA_BUG_ON(xa, count != order_limit);
1205
1206	count = 0;
1207	xas_set(&xas, 0);
1208	rcu_read_lock();
1209	xas_for_each(&xas, entry, ULONG_MAX) {
1210		XA_BUG_ON(xa, entry != xa_mk_index(1UL << count));
1211		count++;
1212		xas_pause(&xas);
1213	}
1214	rcu_read_unlock();
1215	XA_BUG_ON(xa, count != order_limit);
1216
1217	xa_destroy(xa);
1218}
1219
1220static noinline void check_move_tiny(struct xarray *xa)
1221{
1222	XA_STATE(xas, xa, 0);
1223
1224	XA_BUG_ON(xa, !xa_empty(xa));
1225	rcu_read_lock();
1226	XA_BUG_ON(xa, xas_next(&xas) != NULL);
1227	XA_BUG_ON(xa, xas_next(&xas) != NULL);
1228	rcu_read_unlock();
1229	xa_store_index(xa, 0, GFP_KERNEL);
1230	rcu_read_lock();
1231	xas_set(&xas, 0);
1232	XA_BUG_ON(xa, xas_next(&xas) != xa_mk_index(0));
1233	XA_BUG_ON(xa, xas_next(&xas) != NULL);
1234	xas_set(&xas, 0);
1235	XA_BUG_ON(xa, xas_prev(&xas) != xa_mk_index(0));
1236	XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1237	rcu_read_unlock();
1238	xa_erase_index(xa, 0);
1239	XA_BUG_ON(xa, !xa_empty(xa));
1240}
1241
1242static noinline void check_move_max(struct xarray *xa)
1243{
1244	XA_STATE(xas, xa, 0);
1245
1246	xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
1247	rcu_read_lock();
1248	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));
1249	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);
1250	rcu_read_unlock();
1251
1252	xas_set(&xas, 0);
1253	rcu_read_lock();
1254	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX));
1255	xas_pause(&xas);
1256	XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL);
1257	rcu_read_unlock();
1258
1259	xa_erase_index(xa, ULONG_MAX);
1260	XA_BUG_ON(xa, !xa_empty(xa));
1261}
1262
1263static noinline void check_move_small(struct xarray *xa, unsigned long idx)
1264{
1265	XA_STATE(xas, xa, 0);
1266	unsigned long i;
1267
1268	xa_store_index(xa, 0, GFP_KERNEL);
1269	xa_store_index(xa, idx, GFP_KERNEL);
1270
1271	rcu_read_lock();
1272	for (i = 0; i < idx * 4; i++) {
1273		void *entry = xas_next(&xas);
1274		if (i <= idx)
1275			XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
1276		XA_BUG_ON(xa, xas.xa_index != i);
1277		if (i == 0 || i == idx)
1278			XA_BUG_ON(xa, entry != xa_mk_index(i));
1279		else
1280			XA_BUG_ON(xa, entry != NULL);
1281	}
1282	xas_next(&xas);
1283	XA_BUG_ON(xa, xas.xa_index != i);
1284
1285	do {
1286		void *entry = xas_prev(&xas);
1287		i--;
1288		if (i <= idx)
1289			XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
1290		XA_BUG_ON(xa, xas.xa_index != i);
1291		if (i == 0 || i == idx)
1292			XA_BUG_ON(xa, entry != xa_mk_index(i));
1293		else
1294			XA_BUG_ON(xa, entry != NULL);
1295	} while (i > 0);
1296
1297	xas_set(&xas, ULONG_MAX);
1298	XA_BUG_ON(xa, xas_next(&xas) != NULL);
1299	XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1300	XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0));
1301	XA_BUG_ON(xa, xas.xa_index != 0);
1302	XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1303	XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1304	rcu_read_unlock();
1305
1306	xa_erase_index(xa, 0);
1307	xa_erase_index(xa, idx);
1308	XA_BUG_ON(xa, !xa_empty(xa));
1309}
1310
1311static noinline void check_move(struct xarray *xa)
1312{
1313	XA_STATE(xas, xa, (1 << 16) - 1);
1314	unsigned long i;
1315
1316	for (i = 0; i < (1 << 16); i++)
1317		XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
1318
1319	rcu_read_lock();
1320	do {
1321		void *entry = xas_prev(&xas);
1322		i--;
1323		XA_BUG_ON(xa, entry != xa_mk_index(i));
1324		XA_BUG_ON(xa, i != xas.xa_index);
1325	} while (i != 0);
1326
1327	XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1328	XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1329
1330	do {
1331		void *entry = xas_next(&xas);
1332		XA_BUG_ON(xa, entry != xa_mk_index(i));
1333		XA_BUG_ON(xa, i != xas.xa_index);
1334		i++;
1335	} while (i < (1 << 16));
1336	rcu_read_unlock();
1337
1338	for (i = (1 << 8); i < (1 << 15); i++)
1339		xa_erase_index(xa, i);
1340
1341	i = xas.xa_index;
1342
1343	rcu_read_lock();
1344	do {
1345		void *entry = xas_prev(&xas);
1346		i--;
1347		if ((i < (1 << 8)) || (i >= (1 << 15)))
1348			XA_BUG_ON(xa, entry != xa_mk_index(i));
1349		else
1350			XA_BUG_ON(xa, entry != NULL);
1351		XA_BUG_ON(xa, i != xas.xa_index);
1352	} while (i != 0);
1353
1354	XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1355	XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1356
1357	do {
1358		void *entry = xas_next(&xas);
1359		if ((i < (1 << 8)) || (i >= (1 << 15)))
1360			XA_BUG_ON(xa, entry != xa_mk_index(i));
1361		else
1362			XA_BUG_ON(xa, entry != NULL);
1363		XA_BUG_ON(xa, i != xas.xa_index);
1364		i++;
1365	} while (i < (1 << 16));
1366	rcu_read_unlock();
1367
1368	xa_destroy(xa);
1369
1370	check_move_tiny(xa);
1371	check_move_max(xa);
1372
1373	for (i = 0; i < 16; i++)
1374		check_move_small(xa, 1UL << i);
1375
1376	for (i = 2; i < 16; i++)
1377		check_move_small(xa, (1UL << i) - 1);
1378}
1379
1380static noinline void xa_store_many_order(struct xarray *xa,
1381		unsigned long index, unsigned order)
1382{
1383	XA_STATE_ORDER(xas, xa, index, order);
1384	unsigned int i = 0;
1385
1386	do {
1387		xas_lock(&xas);
1388		XA_BUG_ON(xa, xas_find_conflict(&xas));
1389		xas_create_range(&xas);
1390		if (xas_error(&xas))
1391			goto unlock;
1392		for (i = 0; i < (1U << order); i++) {
1393			XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(index + i)));
1394			xas_next(&xas);
1395		}
1396unlock:
1397		xas_unlock(&xas);
1398	} while (xas_nomem(&xas, GFP_KERNEL));
1399
1400	XA_BUG_ON(xa, xas_error(&xas));
1401}
1402
1403static noinline void check_create_range_1(struct xarray *xa,
1404		unsigned long index, unsigned order)
1405{
1406	unsigned long i;
1407
1408	xa_store_many_order(xa, index, order);
1409	for (i = index; i < index + (1UL << order); i++)
1410		xa_erase_index(xa, i);
1411	XA_BUG_ON(xa, !xa_empty(xa));
1412}
1413
1414static noinline void check_create_range_2(struct xarray *xa, unsigned order)
1415{
1416	unsigned long i;
1417	unsigned long nr = 1UL << order;
1418
1419	for (i = 0; i < nr * nr; i += nr)
1420		xa_store_many_order(xa, i, order);
1421	for (i = 0; i < nr * nr; i++)
1422		xa_erase_index(xa, i);
1423	XA_BUG_ON(xa, !xa_empty(xa));
1424}
1425
1426static noinline void check_create_range_3(void)
1427{
1428	XA_STATE(xas, NULL, 0);
1429	xas_set_err(&xas, -EEXIST);
1430	xas_create_range(&xas);
1431	XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST);
1432}
1433
1434static noinline void check_create_range_4(struct xarray *xa,
1435		unsigned long index, unsigned order)
1436{
1437	XA_STATE_ORDER(xas, xa, index, order);
1438	unsigned long base = xas.xa_index;
1439	unsigned long i = 0;
1440
1441	xa_store_index(xa, index, GFP_KERNEL);
1442	do {
1443		xas_lock(&xas);
1444		xas_create_range(&xas);
1445		if (xas_error(&xas))
1446			goto unlock;
1447		for (i = 0; i < (1UL << order); i++) {
1448			void *old = xas_store(&xas, xa_mk_index(base + i));
1449			if (xas.xa_index == index)
1450				XA_BUG_ON(xa, old != xa_mk_index(base + i));
1451			else
1452				XA_BUG_ON(xa, old != NULL);
1453			xas_next(&xas);
1454		}
1455unlock:
1456		xas_unlock(&xas);
1457	} while (xas_nomem(&xas, GFP_KERNEL));
1458
1459	XA_BUG_ON(xa, xas_error(&xas));
1460
1461	for (i = base; i < base + (1UL << order); i++)
1462		xa_erase_index(xa, i);
1463	XA_BUG_ON(xa, !xa_empty(xa));
1464}
1465
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1466static noinline void check_create_range(struct xarray *xa)
1467{
1468	unsigned int order;
1469	unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1;
1470
1471	for (order = 0; order < max_order; order++) {
1472		check_create_range_1(xa, 0, order);
1473		check_create_range_1(xa, 1U << order, order);
1474		check_create_range_1(xa, 2U << order, order);
1475		check_create_range_1(xa, 3U << order, order);
1476		check_create_range_1(xa, 1U << 24, order);
1477		if (order < 10)
1478			check_create_range_2(xa, order);
1479
1480		check_create_range_4(xa, 0, order);
1481		check_create_range_4(xa, 1U << order, order);
1482		check_create_range_4(xa, 2U << order, order);
1483		check_create_range_4(xa, 3U << order, order);
1484		check_create_range_4(xa, 1U << 24, order);
1485
1486		check_create_range_4(xa, 1, order);
1487		check_create_range_4(xa, (1U << order) + 1, order);
1488		check_create_range_4(xa, (2U << order) + 1, order);
1489		check_create_range_4(xa, (2U << order) - 1, order);
1490		check_create_range_4(xa, (3U << order) + 1, order);
1491		check_create_range_4(xa, (3U << order) - 1, order);
1492		check_create_range_4(xa, (1U << 24) + 1, order);
 
 
 
1493	}
1494
1495	check_create_range_3();
1496}
1497
1498static noinline void __check_store_range(struct xarray *xa, unsigned long first,
1499		unsigned long last)
1500{
1501#ifdef CONFIG_XARRAY_MULTI
1502	xa_store_range(xa, first, last, xa_mk_index(first), GFP_KERNEL);
1503
1504	XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_index(first));
1505	XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_index(first));
1506	XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL);
1507	XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL);
1508
1509	xa_store_range(xa, first, last, NULL, GFP_KERNEL);
1510#endif
1511
1512	XA_BUG_ON(xa, !xa_empty(xa));
1513}
1514
1515static noinline void check_store_range(struct xarray *xa)
1516{
1517	unsigned long i, j;
1518
1519	for (i = 0; i < 128; i++) {
1520		for (j = i; j < 128; j++) {
1521			__check_store_range(xa, i, j);
1522			__check_store_range(xa, 128 + i, 128 + j);
1523			__check_store_range(xa, 4095 + i, 4095 + j);
1524			__check_store_range(xa, 4096 + i, 4096 + j);
1525			__check_store_range(xa, 123456 + i, 123456 + j);
1526			__check_store_range(xa, (1 << 24) + i, (1 << 24) + j);
1527		}
1528	}
1529}
1530
1531#ifdef CONFIG_XARRAY_MULTI
1532static void check_split_1(struct xarray *xa, unsigned long index,
1533				unsigned int order, unsigned int new_order)
1534{
1535	XA_STATE_ORDER(xas, xa, index, new_order);
1536	unsigned int i;
 
1537
1538	xa_store_order(xa, index, order, xa, GFP_KERNEL);
 
1539
1540	xas_split_alloc(&xas, xa, order, GFP_KERNEL);
1541	xas_lock(&xas);
1542	xas_split(&xas, xa, order);
1543	for (i = 0; i < (1 << order); i += (1 << new_order))
1544		__xa_store(xa, index + i, xa_mk_index(index + i), 0);
1545	xas_unlock(&xas);
1546
1547	for (i = 0; i < (1 << order); i++) {
1548		unsigned int val = index + (i & ~((1 << new_order) - 1));
1549		XA_BUG_ON(xa, xa_load(xa, index + i) != xa_mk_index(val));
1550	}
1551
1552	xa_set_mark(xa, index, XA_MARK_0);
1553	XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));
1554
 
 
 
 
 
 
 
 
 
 
1555	xa_destroy(xa);
1556}
1557
1558static noinline void check_split(struct xarray *xa)
1559{
1560	unsigned int order, new_order;
1561
1562	XA_BUG_ON(xa, !xa_empty(xa));
1563
1564	for (order = 1; order < 2 * XA_CHUNK_SHIFT; order++) {
1565		for (new_order = 0; new_order < order; new_order++) {
1566			check_split_1(xa, 0, order, new_order);
1567			check_split_1(xa, 1UL << order, order, new_order);
1568			check_split_1(xa, 3UL << order, order, new_order);
1569		}
1570	}
1571}
1572#else
1573static void check_split(struct xarray *xa) { }
1574#endif
1575
1576static void check_align_1(struct xarray *xa, char *name)
1577{
1578	int i;
1579	unsigned int id;
1580	unsigned long index;
1581	void *entry;
1582
1583	for (i = 0; i < 8; i++) {
1584		XA_BUG_ON(xa, xa_alloc(xa, &id, name + i, xa_limit_32b,
1585					GFP_KERNEL) != 0);
1586		XA_BUG_ON(xa, id != i);
1587	}
1588	xa_for_each(xa, index, entry)
1589		XA_BUG_ON(xa, xa_is_err(entry));
1590	xa_destroy(xa);
1591}
1592
1593/*
1594 * We should always be able to store without allocating memory after
1595 * reserving a slot.
1596 */
1597static void check_align_2(struct xarray *xa, char *name)
1598{
1599	int i;
1600
1601	XA_BUG_ON(xa, !xa_empty(xa));
1602
1603	for (i = 0; i < 8; i++) {
1604		XA_BUG_ON(xa, xa_store(xa, 0, name + i, GFP_KERNEL) != NULL);
1605		xa_erase(xa, 0);
1606	}
1607
1608	for (i = 0; i < 8; i++) {
1609		XA_BUG_ON(xa, xa_reserve(xa, 0, GFP_KERNEL) != 0);
1610		XA_BUG_ON(xa, xa_store(xa, 0, name + i, 0) != NULL);
1611		xa_erase(xa, 0);
1612	}
1613
1614	XA_BUG_ON(xa, !xa_empty(xa));
1615}
1616
1617static noinline void check_align(struct xarray *xa)
1618{
1619	char name[] = "Motorola 68000";
1620
1621	check_align_1(xa, name);
1622	check_align_1(xa, name + 1);
1623	check_align_1(xa, name + 2);
1624	check_align_1(xa, name + 3);
1625	check_align_2(xa, name);
1626}
1627
1628static LIST_HEAD(shadow_nodes);
1629
1630static void test_update_node(struct xa_node *node)
1631{
1632	if (node->count && node->count == node->nr_values) {
1633		if (list_empty(&node->private_list))
1634			list_add(&shadow_nodes, &node->private_list);
1635	} else {
1636		if (!list_empty(&node->private_list))
1637			list_del_init(&node->private_list);
1638	}
1639}
1640
1641static noinline void shadow_remove(struct xarray *xa)
1642{
1643	struct xa_node *node;
1644
1645	xa_lock(xa);
1646	while ((node = list_first_entry_or_null(&shadow_nodes,
1647					struct xa_node, private_list))) {
1648		XA_BUG_ON(xa, node->array != xa);
1649		list_del_init(&node->private_list);
1650		xa_delete_node(node, test_update_node);
1651	}
1652	xa_unlock(xa);
1653}
1654
1655static noinline void check_workingset(struct xarray *xa, unsigned long index)
1656{
1657	XA_STATE(xas, xa, index);
1658	xas_set_update(&xas, test_update_node);
1659
1660	do {
1661		xas_lock(&xas);
1662		xas_store(&xas, xa_mk_value(0));
1663		xas_next(&xas);
1664		xas_store(&xas, xa_mk_value(1));
1665		xas_unlock(&xas);
1666	} while (xas_nomem(&xas, GFP_KERNEL));
1667
1668	XA_BUG_ON(xa, list_empty(&shadow_nodes));
1669
1670	xas_lock(&xas);
1671	xas_next(&xas);
1672	xas_store(&xas, &xas);
1673	XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1674
1675	xas_store(&xas, xa_mk_value(2));
1676	xas_unlock(&xas);
1677	XA_BUG_ON(xa, list_empty(&shadow_nodes));
1678
1679	shadow_remove(xa);
1680	XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1681	XA_BUG_ON(xa, !xa_empty(xa));
1682}
1683
1684/*
1685 * Check that the pointer / value / sibling entries are accounted the
1686 * way we expect them to be.
1687 */
1688static noinline void check_account(struct xarray *xa)
1689{
1690#ifdef CONFIG_XARRAY_MULTI
1691	unsigned int order;
1692
1693	for (order = 1; order < 12; order++) {
1694		XA_STATE(xas, xa, 1 << order);
1695
1696		xa_store_order(xa, 0, order, xa, GFP_KERNEL);
1697		rcu_read_lock();
1698		xas_load(&xas);
1699		XA_BUG_ON(xa, xas.xa_node->count == 0);
1700		XA_BUG_ON(xa, xas.xa_node->count > (1 << order));
1701		XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1702		rcu_read_unlock();
1703
1704		xa_store_order(xa, 1 << order, order, xa_mk_index(1UL << order),
1705				GFP_KERNEL);
1706		XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2);
1707
1708		xa_erase(xa, 1 << order);
1709		XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1710
1711		xa_erase(xa, 0);
1712		XA_BUG_ON(xa, !xa_empty(xa));
1713	}
1714#endif
1715}
1716
1717static noinline void check_get_order(struct xarray *xa)
1718{
1719	unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;
1720	unsigned int order;
1721	unsigned long i, j;
1722
1723	for (i = 0; i < 3; i++)
1724		XA_BUG_ON(xa, xa_get_order(xa, i) != 0);
1725
1726	for (order = 0; order < max_order; order++) {
1727		for (i = 0; i < 10; i++) {
1728			xa_store_order(xa, i << order, order,
1729					xa_mk_index(i << order), GFP_KERNEL);
1730			for (j = i << order; j < (i + 1) << order; j++)
1731				XA_BUG_ON(xa, xa_get_order(xa, j) != order);
1732			xa_erase(xa, i << order);
1733		}
1734	}
1735}
1736
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1737static noinline void check_destroy(struct xarray *xa)
1738{
1739	unsigned long index;
1740
1741	XA_BUG_ON(xa, !xa_empty(xa));
1742
1743	/* Destroying an empty array is a no-op */
1744	xa_destroy(xa);
1745	XA_BUG_ON(xa, !xa_empty(xa));
1746
1747	/* Destroying an array with a single entry */
1748	for (index = 0; index < 1000; index++) {
1749		xa_store_index(xa, index, GFP_KERNEL);
1750		XA_BUG_ON(xa, xa_empty(xa));
1751		xa_destroy(xa);
1752		XA_BUG_ON(xa, !xa_empty(xa));
1753	}
1754
1755	/* Destroying an array with a single entry at ULONG_MAX */
1756	xa_store(xa, ULONG_MAX, xa, GFP_KERNEL);
1757	XA_BUG_ON(xa, xa_empty(xa));
1758	xa_destroy(xa);
1759	XA_BUG_ON(xa, !xa_empty(xa));
1760
1761#ifdef CONFIG_XARRAY_MULTI
1762	/* Destroying an array with a multi-index entry */
1763	xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL);
1764	XA_BUG_ON(xa, xa_empty(xa));
1765	xa_destroy(xa);
1766	XA_BUG_ON(xa, !xa_empty(xa));
1767#endif
1768}
1769
1770static DEFINE_XARRAY(array);
1771
1772static int xarray_checks(void)
1773{
1774	check_xa_err(&array);
1775	check_xas_retry(&array);
1776	check_xa_load(&array);
1777	check_xa_mark(&array);
1778	check_xa_shrink(&array);
1779	check_xas_erase(&array);
1780	check_insert(&array);
1781	check_cmpxchg(&array);
 
1782	check_reserve(&array);
1783	check_reserve(&xa0);
1784	check_multi_store(&array);
 
1785	check_get_order(&array);
 
 
1786	check_xa_alloc();
1787	check_find(&array);
1788	check_find_entry(&array);
1789	check_pause(&array);
1790	check_account(&array);
1791	check_destroy(&array);
1792	check_move(&array);
1793	check_create_range(&array);
1794	check_store_range(&array);
1795	check_store_iter(&array);
1796	check_align(&xa0);
1797	check_split(&array);
1798
1799	check_workingset(&array, 0);
1800	check_workingset(&array, 64);
1801	check_workingset(&array, 4096);
1802
1803	printk("XArray: %u of %u tests passed\n", tests_passed, tests_run);
1804	return (tests_run == tests_passed) ? 0 : -EINVAL;
1805}
1806
1807static void xarray_exit(void)
1808{
1809}
1810
1811module_init(xarray_checks);
1812module_exit(xarray_exit);
1813MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
 
1814MODULE_LICENSE("GPL");
v6.13.7
   1// SPDX-License-Identifier: GPL-2.0+
   2/*
   3 * test_xarray.c: Test the XArray API
   4 * Copyright (c) 2017-2018 Microsoft Corporation
   5 * Copyright (c) 2019-2020 Oracle
   6 * 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_DEBUG
  19# ifdef __KERNEL__
  20void xa_dump(const struct xarray *xa) { }
  21# endif
  22#undef XA_BUG_ON
  23#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#endif
  34
  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 current
  68 * users outside the test suite because all current multislot users want
  69 * 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#endif
  95	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			else
 157				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			else
 168				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 the
 204	 * entire entry the union of the marks
 205	 */
 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_MULTI
 295	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#endif
 311}
 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 properly
 337	 * 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_MULTI
 429	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 at
 448	 * '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#endif
 477}
 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_MULTI
 584static 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#endif
 649
 650static noinline void check_multi_store(struct xarray *xa)
 651{
 652#ifdef CONFIG_XARRAY_MULTI
 653	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				else
 708					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#endif
 728}
 729
 730#ifdef CONFIG_XARRAY_MULTI
 731/* 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 for
 751		 * there not to be enough memory as we're not mimicking the
 752		 * entire page cache, so verify that's the only error we can run
 753		 * into here. The xas_nomem() which follows will ensure to fix
 754		 * 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 pretty
 801	 * aggressive and does not want to trust the xarray API but rather
 802	 * test it, and for order 20 (4 GiB block size) we can loop over
 803	 * over a million entries which can cause a soft lockup. Page cache
 804	 * APIs won't be stupid, proper page cache APIs loop over the proper
 805	 * 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#endif
 890
 891static noinline void check_multi_store_advanced(struct xarray *xa)
 892{
 893#ifdef CONFIG_XARRAY_MULTI
 894	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#endif
 908}
 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		else
1060			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_MULTI
1159	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#endif
1164	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_MULTI
1170	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#endif
1197}
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 99
1246	 */
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				else
1263					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				else
1273					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_MULTI
1388	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#endif
1408
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		else
1513			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		else
1527			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		else
1583			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		else
1595			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			else
1685				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_MULTI
1757	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#endif
1766
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_MULTI
1787static 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#else
1840static void check_split(struct xarray *xa) { }
1841#endif
1842
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 after
1862 * 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 the
1953 * way we expect them to be.
1954 */
1955static noinline void check_account(struct xarray *xa)
1956{
1957#ifdef CONFIG_XARRAY_MULTI
1958	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#endif
1982}
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_MULTI
2120	/* 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#endif
2126}
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");