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");