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