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(struct xarray *xa) 1050 { 1051 check_find_1(xa); 1052 check_find_2(xa); 1053 check_find_3(xa); 1054 check_multi_find(xa); 1055 check_multi_find_2(xa); 1056 } 1057 1058 /* See find_swap_entry() in mm/shmem.c */ 1059 static noinline unsigned long xa_find_entry(struct xarray *xa, void *item) 1060 { 1061 XA_STATE(xas, xa, 0); 1062 unsigned int checked = 0; 1063 void *entry; 1064 1065 rcu_read_lock(); 1066 xas_for_each(&xas, entry, ULONG_MAX) { 1067 if (xas_retry(&xas, entry)) 1068 continue; 1069 if (entry == item) 1070 break; 1071 checked++; 1072 if ((checked % 4) != 0) 1073 continue; 1074 xas_pause(&xas); 1075 } 1076 rcu_read_unlock(); 1077 1078 return entry ? xas.xa_index : -1; 1079 } 1080 1081 static noinline void check_find_entry(struct xarray *xa) 1082 { 1083 #ifdef CONFIG_XARRAY_MULTI 1084 unsigned int order; 1085 unsigned long offset, index; 1086 1087 for (order = 0; order < 20; order++) { 1088 for (offset = 0; offset < (1UL << (order + 3)); 1089 offset += (1UL << order)) { 1090 for (index = 0; index < (1UL << (order + 5)); 1091 index += (1UL << order)) { 1092 xa_store_order(xa, index, order, 1093 xa_mk_index(index), GFP_KERNEL); 1094 XA_BUG_ON(xa, xa_load(xa, index) != 1095 xa_mk_index(index)); 1096 XA_BUG_ON(xa, xa_find_entry(xa, 1097 xa_mk_index(index)) != index); 1098 } 1099 XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1); 1100 xa_destroy(xa); 1101 } 1102 } 1103 #endif 1104 1105 XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1); 1106 xa_store_index(xa, ULONG_MAX, GFP_KERNEL); 1107 XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1); 1108 XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_index(ULONG_MAX)) != -1); 1109 xa_erase_index(xa, ULONG_MAX); 1110 XA_BUG_ON(xa, !xa_empty(xa)); 1111 } 1112 1113 static noinline void check_move_tiny(struct xarray *xa) 1114 { 1115 XA_STATE(xas, xa, 0); 1116 1117 XA_BUG_ON(xa, !xa_empty(xa)); 1118 rcu_read_lock(); 1119 XA_BUG_ON(xa, xas_next(&xas) != NULL); 1120 XA_BUG_ON(xa, xas_next(&xas) != NULL); 1121 rcu_read_unlock(); 1122 xa_store_index(xa, 0, GFP_KERNEL); 1123 rcu_read_lock(); 1124 xas_set(&xas, 0); 1125 XA_BUG_ON(xa, xas_next(&xas) != xa_mk_index(0)); 1126 XA_BUG_ON(xa, xas_next(&xas) != NULL); 1127 xas_set(&xas, 0); 1128 XA_BUG_ON(xa, xas_prev(&xas) != xa_mk_index(0)); 1129 XA_BUG_ON(xa, xas_prev(&xas) != NULL); 1130 rcu_read_unlock(); 1131 xa_erase_index(xa, 0); 1132 XA_BUG_ON(xa, !xa_empty(xa)); 1133 } 1134 1135 static noinline void check_move_max(struct xarray *xa) 1136 { 1137 XA_STATE(xas, xa, 0); 1138 1139 xa_store_index(xa, ULONG_MAX, GFP_KERNEL); 1140 rcu_read_lock(); 1141 XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX)); 1142 XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL); 1143 rcu_read_unlock(); 1144 1145 xas_set(&xas, 0); 1146 rcu_read_lock(); 1147 XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX)); 1148 xas_pause(&xas); 1149 XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL); 1150 rcu_read_unlock(); 1151 1152 xa_erase_index(xa, ULONG_MAX); 1153 XA_BUG_ON(xa, !xa_empty(xa)); 1154 } 1155 1156 static noinline void check_move_small(struct xarray *xa, unsigned long idx) 1157 { 1158 XA_STATE(xas, xa, 0); 1159 unsigned long i; 1160 1161 xa_store_index(xa, 0, GFP_KERNEL); 1162 xa_store_index(xa, idx, GFP_KERNEL); 1163 1164 rcu_read_lock(); 1165 for (i = 0; i < idx * 4; i++) { 1166 void *entry = xas_next(&xas); 1167 if (i <= idx) 1168 XA_BUG_ON(xa, xas.xa_node == XAS_RESTART); 1169 XA_BUG_ON(xa, xas.xa_index != i); 1170 if (i == 0 || i == idx) 1171 XA_BUG_ON(xa, entry != xa_mk_index(i)); 1172 else 1173 XA_BUG_ON(xa, entry != NULL); 1174 } 1175 xas_next(&xas); 1176 XA_BUG_ON(xa, xas.xa_index != i); 1177 1178 do { 1179 void *entry = xas_prev(&xas); 1180 i--; 1181 if (i <= idx) 1182 XA_BUG_ON(xa, xas.xa_node == XAS_RESTART); 1183 XA_BUG_ON(xa, xas.xa_index != i); 1184 if (i == 0 || i == idx) 1185 XA_BUG_ON(xa, entry != xa_mk_index(i)); 1186 else 1187 XA_BUG_ON(xa, entry != NULL); 1188 } while (i > 0); 1189 1190 xas_set(&xas, ULONG_MAX); 1191 XA_BUG_ON(xa, xas_next(&xas) != NULL); 1192 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 1193 XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0)); 1194 XA_BUG_ON(xa, xas.xa_index != 0); 1195 XA_BUG_ON(xa, xas_prev(&xas) != NULL); 1196 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 1197 rcu_read_unlock(); 1198 1199 xa_erase_index(xa, 0); 1200 xa_erase_index(xa, idx); 1201 XA_BUG_ON(xa, !xa_empty(xa)); 1202 } 1203 1204 static noinline void check_move(struct xarray *xa) 1205 { 1206 XA_STATE(xas, xa, (1 << 16) - 1); 1207 unsigned long i; 1208 1209 for (i = 0; i < (1 << 16); i++) 1210 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL); 1211 1212 rcu_read_lock(); 1213 do { 1214 void *entry = xas_prev(&xas); 1215 i--; 1216 XA_BUG_ON(xa, entry != xa_mk_index(i)); 1217 XA_BUG_ON(xa, i != xas.xa_index); 1218 } while (i != 0); 1219 1220 XA_BUG_ON(xa, xas_prev(&xas) != NULL); 1221 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 1222 1223 do { 1224 void *entry = xas_next(&xas); 1225 XA_BUG_ON(xa, entry != xa_mk_index(i)); 1226 XA_BUG_ON(xa, i != xas.xa_index); 1227 i++; 1228 } while (i < (1 << 16)); 1229 rcu_read_unlock(); 1230 1231 for (i = (1 << 8); i < (1 << 15); i++) 1232 xa_erase_index(xa, i); 1233 1234 i = xas.xa_index; 1235 1236 rcu_read_lock(); 1237 do { 1238 void *entry = xas_prev(&xas); 1239 i--; 1240 if ((i < (1 << 8)) || (i >= (1 << 15))) 1241 XA_BUG_ON(xa, entry != xa_mk_index(i)); 1242 else 1243 XA_BUG_ON(xa, entry != NULL); 1244 XA_BUG_ON(xa, i != xas.xa_index); 1245 } while (i != 0); 1246 1247 XA_BUG_ON(xa, xas_prev(&xas) != NULL); 1248 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 1249 1250 do { 1251 void *entry = xas_next(&xas); 1252 if ((i < (1 << 8)) || (i >= (1 << 15))) 1253 XA_BUG_ON(xa, entry != xa_mk_index(i)); 1254 else 1255 XA_BUG_ON(xa, entry != NULL); 1256 XA_BUG_ON(xa, i != xas.xa_index); 1257 i++; 1258 } while (i < (1 << 16)); 1259 rcu_read_unlock(); 1260 1261 xa_destroy(xa); 1262 1263 check_move_tiny(xa); 1264 check_move_max(xa); 1265 1266 for (i = 0; i < 16; i++) 1267 check_move_small(xa, 1UL << i); 1268 1269 for (i = 2; i < 16; i++) 1270 check_move_small(xa, (1UL << i) - 1); 1271 } 1272 1273 static noinline void xa_store_many_order(struct xarray *xa, 1274 unsigned long index, unsigned order) 1275 { 1276 XA_STATE_ORDER(xas, xa, index, order); 1277 unsigned int i = 0; 1278 1279 do { 1280 xas_lock(&xas); 1281 XA_BUG_ON(xa, xas_find_conflict(&xas)); 1282 xas_create_range(&xas); 1283 if (xas_error(&xas)) 1284 goto unlock; 1285 for (i = 0; i < (1U << order); i++) { 1286 XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(index + i))); 1287 xas_next(&xas); 1288 } 1289 unlock: 1290 xas_unlock(&xas); 1291 } while (xas_nomem(&xas, GFP_KERNEL)); 1292 1293 XA_BUG_ON(xa, xas_error(&xas)); 1294 } 1295 1296 static noinline void check_create_range_1(struct xarray *xa, 1297 unsigned long index, unsigned order) 1298 { 1299 unsigned long i; 1300 1301 xa_store_many_order(xa, index, order); 1302 for (i = index; i < index + (1UL << order); i++) 1303 xa_erase_index(xa, i); 1304 XA_BUG_ON(xa, !xa_empty(xa)); 1305 } 1306 1307 static noinline void check_create_range_2(struct xarray *xa, unsigned order) 1308 { 1309 unsigned long i; 1310 unsigned long nr = 1UL << order; 1311 1312 for (i = 0; i < nr * nr; i += nr) 1313 xa_store_many_order(xa, i, order); 1314 for (i = 0; i < nr * nr; i++) 1315 xa_erase_index(xa, i); 1316 XA_BUG_ON(xa, !xa_empty(xa)); 1317 } 1318 1319 static noinline void check_create_range_3(void) 1320 { 1321 XA_STATE(xas, NULL, 0); 1322 xas_set_err(&xas, -EEXIST); 1323 xas_create_range(&xas); 1324 XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST); 1325 } 1326 1327 static noinline void check_create_range_4(struct xarray *xa, 1328 unsigned long index, unsigned order) 1329 { 1330 XA_STATE_ORDER(xas, xa, index, order); 1331 unsigned long base = xas.xa_index; 1332 unsigned long i = 0; 1333 1334 xa_store_index(xa, index, GFP_KERNEL); 1335 do { 1336 xas_lock(&xas); 1337 xas_create_range(&xas); 1338 if (xas_error(&xas)) 1339 goto unlock; 1340 for (i = 0; i < (1UL << order); i++) { 1341 void *old = xas_store(&xas, xa_mk_index(base + i)); 1342 if (xas.xa_index == index) 1343 XA_BUG_ON(xa, old != xa_mk_index(base + i)); 1344 else 1345 XA_BUG_ON(xa, old != NULL); 1346 xas_next(&xas); 1347 } 1348 unlock: 1349 xas_unlock(&xas); 1350 } while (xas_nomem(&xas, GFP_KERNEL)); 1351 1352 XA_BUG_ON(xa, xas_error(&xas)); 1353 1354 for (i = base; i < base + (1UL << order); i++) 1355 xa_erase_index(xa, i); 1356 XA_BUG_ON(xa, !xa_empty(xa)); 1357 } 1358 1359 static noinline void check_create_range(struct xarray *xa) 1360 { 1361 unsigned int order; 1362 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1; 1363 1364 for (order = 0; order < max_order; order++) { 1365 check_create_range_1(xa, 0, order); 1366 check_create_range_1(xa, 1U << order, order); 1367 check_create_range_1(xa, 2U << order, order); 1368 check_create_range_1(xa, 3U << order, order); 1369 check_create_range_1(xa, 1U << 24, order); 1370 if (order < 10) 1371 check_create_range_2(xa, order); 1372 1373 check_create_range_4(xa, 0, order); 1374 check_create_range_4(xa, 1U << order, order); 1375 check_create_range_4(xa, 2U << order, order); 1376 check_create_range_4(xa, 3U << order, order); 1377 check_create_range_4(xa, 1U << 24, order); 1378 1379 check_create_range_4(xa, 1, order); 1380 check_create_range_4(xa, (1U << order) + 1, order); 1381 check_create_range_4(xa, (2U << order) + 1, order); 1382 check_create_range_4(xa, (2U << order) - 1, order); 1383 check_create_range_4(xa, (3U << order) + 1, order); 1384 check_create_range_4(xa, (3U << order) - 1, order); 1385 check_create_range_4(xa, (1U << 24) + 1, order); 1386 } 1387 1388 check_create_range_3(); 1389 } 1390 1391 static noinline void __check_store_range(struct xarray *xa, unsigned long first, 1392 unsigned long last) 1393 { 1394 #ifdef CONFIG_XARRAY_MULTI 1395 xa_store_range(xa, first, last, xa_mk_index(first), GFP_KERNEL); 1396 1397 XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_index(first)); 1398 XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_index(first)); 1399 XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL); 1400 XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL); 1401 1402 xa_store_range(xa, first, last, NULL, GFP_KERNEL); 1403 #endif 1404 1405 XA_BUG_ON(xa, !xa_empty(xa)); 1406 } 1407 1408 static noinline void check_store_range(struct xarray *xa) 1409 { 1410 unsigned long i, j; 1411 1412 for (i = 0; i < 128; i++) { 1413 for (j = i; j < 128; j++) { 1414 __check_store_range(xa, i, j); 1415 __check_store_range(xa, 128 + i, 128 + j); 1416 __check_store_range(xa, 4095 + i, 4095 + j); 1417 __check_store_range(xa, 4096 + i, 4096 + j); 1418 __check_store_range(xa, 123456 + i, 123456 + j); 1419 __check_store_range(xa, (1 << 24) + i, (1 << 24) + j); 1420 } 1421 } 1422 } 1423 1424 static void check_align_1(struct xarray *xa, char *name) 1425 { 1426 int i; 1427 unsigned int id; 1428 unsigned long index; 1429 void *entry; 1430 1431 for (i = 0; i < 8; i++) { 1432 XA_BUG_ON(xa, xa_alloc(xa, &id, name + i, xa_limit_32b, 1433 GFP_KERNEL) != 0); 1434 XA_BUG_ON(xa, id != i); 1435 } 1436 xa_for_each(xa, index, entry) 1437 XA_BUG_ON(xa, xa_is_err(entry)); 1438 xa_destroy(xa); 1439 } 1440 1441 /* 1442 * We should always be able to store without allocating memory after 1443 * reserving a slot. 1444 */ 1445 static void check_align_2(struct xarray *xa, char *name) 1446 { 1447 int i; 1448 1449 XA_BUG_ON(xa, !xa_empty(xa)); 1450 1451 for (i = 0; i < 8; i++) { 1452 XA_BUG_ON(xa, xa_store(xa, 0, name + i, GFP_KERNEL) != NULL); 1453 xa_erase(xa, 0); 1454 } 1455 1456 for (i = 0; i < 8; i++) { 1457 XA_BUG_ON(xa, xa_reserve(xa, 0, GFP_KERNEL) != 0); 1458 XA_BUG_ON(xa, xa_store(xa, 0, name + i, 0) != NULL); 1459 xa_erase(xa, 0); 1460 } 1461 1462 XA_BUG_ON(xa, !xa_empty(xa)); 1463 } 1464 1465 static noinline void check_align(struct xarray *xa) 1466 { 1467 char name[] = "Motorola 68000"; 1468 1469 check_align_1(xa, name); 1470 check_align_1(xa, name + 1); 1471 check_align_1(xa, name + 2); 1472 check_align_1(xa, name + 3); 1473 check_align_2(xa, name); 1474 } 1475 1476 static LIST_HEAD(shadow_nodes); 1477 1478 static void test_update_node(struct xa_node *node) 1479 { 1480 if (node->count && node->count == node->nr_values) { 1481 if (list_empty(&node->private_list)) 1482 list_add(&shadow_nodes, &node->private_list); 1483 } else { 1484 if (!list_empty(&node->private_list)) 1485 list_del_init(&node->private_list); 1486 } 1487 } 1488 1489 static noinline void shadow_remove(struct xarray *xa) 1490 { 1491 struct xa_node *node; 1492 1493 xa_lock(xa); 1494 while ((node = list_first_entry_or_null(&shadow_nodes, 1495 struct xa_node, private_list))) { 1496 XA_STATE(xas, node->array, 0); 1497 XA_BUG_ON(xa, node->array != xa); 1498 list_del_init(&node->private_list); 1499 xas.xa_node = xa_parent_locked(node->array, node); 1500 xas.xa_offset = node->offset; 1501 xas.xa_shift = node->shift + XA_CHUNK_SHIFT; 1502 xas_set_update(&xas, test_update_node); 1503 xas_store(&xas, NULL); 1504 } 1505 xa_unlock(xa); 1506 } 1507 1508 static noinline void check_workingset(struct xarray *xa, unsigned long index) 1509 { 1510 XA_STATE(xas, xa, index); 1511 xas_set_update(&xas, test_update_node); 1512 1513 do { 1514 xas_lock(&xas); 1515 xas_store(&xas, xa_mk_value(0)); 1516 xas_next(&xas); 1517 xas_store(&xas, xa_mk_value(1)); 1518 xas_unlock(&xas); 1519 } while (xas_nomem(&xas, GFP_KERNEL)); 1520 1521 XA_BUG_ON(xa, list_empty(&shadow_nodes)); 1522 1523 xas_lock(&xas); 1524 xas_next(&xas); 1525 xas_store(&xas, &xas); 1526 XA_BUG_ON(xa, !list_empty(&shadow_nodes)); 1527 1528 xas_store(&xas, xa_mk_value(2)); 1529 xas_unlock(&xas); 1530 XA_BUG_ON(xa, list_empty(&shadow_nodes)); 1531 1532 shadow_remove(xa); 1533 XA_BUG_ON(xa, !list_empty(&shadow_nodes)); 1534 XA_BUG_ON(xa, !xa_empty(xa)); 1535 } 1536 1537 /* 1538 * Check that the pointer / value / sibling entries are accounted the 1539 * way we expect them to be. 1540 */ 1541 static noinline void check_account(struct xarray *xa) 1542 { 1543 #ifdef CONFIG_XARRAY_MULTI 1544 unsigned int order; 1545 1546 for (order = 1; order < 12; order++) { 1547 XA_STATE(xas, xa, 1 << order); 1548 1549 xa_store_order(xa, 0, order, xa, GFP_KERNEL); 1550 rcu_read_lock(); 1551 xas_load(&xas); 1552 XA_BUG_ON(xa, xas.xa_node->count == 0); 1553 XA_BUG_ON(xa, xas.xa_node->count > (1 << order)); 1554 XA_BUG_ON(xa, xas.xa_node->nr_values != 0); 1555 rcu_read_unlock(); 1556 1557 xa_store_order(xa, 1 << order, order, xa_mk_index(1UL << order), 1558 GFP_KERNEL); 1559 XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2); 1560 1561 xa_erase(xa, 1 << order); 1562 XA_BUG_ON(xa, xas.xa_node->nr_values != 0); 1563 1564 xa_erase(xa, 0); 1565 XA_BUG_ON(xa, !xa_empty(xa)); 1566 } 1567 #endif 1568 } 1569 1570 static noinline void check_destroy(struct xarray *xa) 1571 { 1572 unsigned long index; 1573 1574 XA_BUG_ON(xa, !xa_empty(xa)); 1575 1576 /* Destroying an empty array is a no-op */ 1577 xa_destroy(xa); 1578 XA_BUG_ON(xa, !xa_empty(xa)); 1579 1580 /* Destroying an array with a single entry */ 1581 for (index = 0; index < 1000; index++) { 1582 xa_store_index(xa, index, GFP_KERNEL); 1583 XA_BUG_ON(xa, xa_empty(xa)); 1584 xa_destroy(xa); 1585 XA_BUG_ON(xa, !xa_empty(xa)); 1586 } 1587 1588 /* Destroying an array with a single entry at ULONG_MAX */ 1589 xa_store(xa, ULONG_MAX, xa, GFP_KERNEL); 1590 XA_BUG_ON(xa, xa_empty(xa)); 1591 xa_destroy(xa); 1592 XA_BUG_ON(xa, !xa_empty(xa)); 1593 1594 #ifdef CONFIG_XARRAY_MULTI 1595 /* Destroying an array with a multi-index entry */ 1596 xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL); 1597 XA_BUG_ON(xa, xa_empty(xa)); 1598 xa_destroy(xa); 1599 XA_BUG_ON(xa, !xa_empty(xa)); 1600 #endif 1601 } 1602 1603 static DEFINE_XARRAY(array); 1604 1605 static int xarray_checks(void) 1606 { 1607 check_xa_err(&array); 1608 check_xas_retry(&array); 1609 check_xa_load(&array); 1610 check_xa_mark(&array); 1611 check_xa_shrink(&array); 1612 check_xas_erase(&array); 1613 check_insert(&array); 1614 check_cmpxchg(&array); 1615 check_reserve(&array); 1616 check_reserve(&xa0); 1617 check_multi_store(&array); 1618 check_xa_alloc(); 1619 check_find(&array); 1620 check_find_entry(&array); 1621 check_account(&array); 1622 check_destroy(&array); 1623 check_move(&array); 1624 check_create_range(&array); 1625 check_store_range(&array); 1626 check_store_iter(&array); 1627 check_align(&xa0); 1628 1629 check_workingset(&array, 0); 1630 check_workingset(&array, 64); 1631 check_workingset(&array, 4096); 1632 1633 printk("XArray: %u of %u tests passed\n", tests_passed, tests_run); 1634 return (tests_run == tests_passed) ? 0 : -EINVAL; 1635 } 1636 1637 static void xarray_exit(void) 1638 { 1639 } 1640 1641 module_init(xarray_checks); 1642 module_exit(xarray_exit); 1643 MODULE_AUTHOR("Matthew Wilcox <[email protected]>"); 1644 MODULE_LICENSE("GPL"); 1645