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