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