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