1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * Module-based API test facility for ww_mutexes 4 */ 5 6 #include <linux/kernel.h> 7 8 #include <linux/completion.h> 9 #include <linux/delay.h> 10 #include <linux/kthread.h> 11 #include <linux/module.h> 12 #include <linux/prandom.h> 13 #include <linux/slab.h> 14 #include <linux/ww_mutex.h> 15 16 static DEFINE_WD_CLASS(ww_class); 17 struct workqueue_struct *wq; 18 19 #ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH 20 #define ww_acquire_init_noinject(a, b) do { \ 21 ww_acquire_init((a), (b)); \ 22 (a)->deadlock_inject_countdown = ~0U; \ 23 } while (0) 24 #else 25 #define ww_acquire_init_noinject(a, b) ww_acquire_init((a), (b)) 26 #endif 27 28 struct test_mutex { 29 struct work_struct work; 30 struct ww_mutex mutex; 31 struct completion ready, go, done; 32 unsigned int flags; 33 }; 34 35 #define TEST_MTX_SPIN BIT(0) 36 #define TEST_MTX_TRY BIT(1) 37 #define TEST_MTX_CTX BIT(2) 38 #define __TEST_MTX_LAST BIT(3) 39 40 static void test_mutex_work(struct work_struct *work) 41 { 42 struct test_mutex *mtx = container_of(work, typeof(*mtx), work); 43 44 complete(&mtx->ready); 45 wait_for_completion(&mtx->go); 46 47 if (mtx->flags & TEST_MTX_TRY) { 48 while (!ww_mutex_trylock(&mtx->mutex, NULL)) 49 cond_resched(); 50 } else { 51 ww_mutex_lock(&mtx->mutex, NULL); 52 } 53 complete(&mtx->done); 54 ww_mutex_unlock(&mtx->mutex); 55 } 56 57 static int __test_mutex(unsigned int flags) 58 { 59 #define TIMEOUT (HZ / 16) 60 struct test_mutex mtx; 61 struct ww_acquire_ctx ctx; 62 int ret; 63 64 ww_mutex_init(&mtx.mutex, &ww_class); 65 if (flags & TEST_MTX_CTX) 66 ww_acquire_init(&ctx, &ww_class); 67 68 INIT_WORK_ONSTACK(&mtx.work, test_mutex_work); 69 init_completion(&mtx.ready); 70 init_completion(&mtx.go); 71 init_completion(&mtx.done); 72 mtx.flags = flags; 73 74 schedule_work(&mtx.work); 75 76 wait_for_completion(&mtx.ready); 77 ww_mutex_lock(&mtx.mutex, (flags & TEST_MTX_CTX) ? &ctx : NULL); 78 complete(&mtx.go); 79 if (flags & TEST_MTX_SPIN) { 80 unsigned long timeout = jiffies + TIMEOUT; 81 82 ret = 0; 83 do { 84 if (completion_done(&mtx.done)) { 85 ret = -EINVAL; 86 break; 87 } 88 cond_resched(); 89 } while (time_before(jiffies, timeout)); 90 } else { 91 ret = wait_for_completion_timeout(&mtx.done, TIMEOUT); 92 } 93 ww_mutex_unlock(&mtx.mutex); 94 if (flags & TEST_MTX_CTX) 95 ww_acquire_fini(&ctx); 96 97 if (ret) { 98 pr_err("%s(flags=%x): mutual exclusion failure\n", 99 __func__, flags); 100 ret = -EINVAL; 101 } 102 103 flush_work(&mtx.work); 104 destroy_work_on_stack(&mtx.work); 105 return ret; 106 #undef TIMEOUT 107 } 108 109 static int test_mutex(void) 110 { 111 int ret; 112 int i; 113 114 for (i = 0; i < __TEST_MTX_LAST; i++) { 115 ret = __test_mutex(i); 116 if (ret) 117 return ret; 118 } 119 120 return 0; 121 } 122 123 static int test_aa(bool trylock) 124 { 125 struct ww_mutex mutex; 126 struct ww_acquire_ctx ctx; 127 int ret; 128 const char *from = trylock ? "trylock" : "lock"; 129 130 ww_mutex_init(&mutex, &ww_class); 131 ww_acquire_init(&ctx, &ww_class); 132 133 if (!trylock) { 134 ret = ww_mutex_lock(&mutex, &ctx); 135 if (ret) { 136 pr_err("%s: initial lock failed!\n", __func__); 137 goto out; 138 } 139 } else { 140 ret = !ww_mutex_trylock(&mutex, &ctx); 141 if (ret) { 142 pr_err("%s: initial trylock failed!\n", __func__); 143 goto out; 144 } 145 } 146 147 if (ww_mutex_trylock(&mutex, NULL)) { 148 pr_err("%s: trylocked itself without context from %s!\n", __func__, from); 149 ww_mutex_unlock(&mutex); 150 ret = -EINVAL; 151 goto out; 152 } 153 154 if (ww_mutex_trylock(&mutex, &ctx)) { 155 pr_err("%s: trylocked itself with context from %s!\n", __func__, from); 156 ww_mutex_unlock(&mutex); 157 ret = -EINVAL; 158 goto out; 159 } 160 161 ret = ww_mutex_lock(&mutex, &ctx); 162 if (ret != -EALREADY) { 163 pr_err("%s: missed deadlock for recursing, ret=%d from %s\n", 164 __func__, ret, from); 165 if (!ret) 166 ww_mutex_unlock(&mutex); 167 ret = -EINVAL; 168 goto out; 169 } 170 171 ww_mutex_unlock(&mutex); 172 ret = 0; 173 out: 174 ww_acquire_fini(&ctx); 175 return ret; 176 } 177 178 struct test_abba { 179 struct work_struct work; 180 struct ww_mutex a_mutex; 181 struct ww_mutex b_mutex; 182 struct completion a_ready; 183 struct completion b_ready; 184 bool resolve, trylock; 185 int result; 186 }; 187 188 static void test_abba_work(struct work_struct *work) 189 { 190 struct test_abba *abba = container_of(work, typeof(*abba), work); 191 struct ww_acquire_ctx ctx; 192 int err; 193 194 ww_acquire_init_noinject(&ctx, &ww_class); 195 if (!abba->trylock) 196 ww_mutex_lock(&abba->b_mutex, &ctx); 197 else 198 WARN_ON(!ww_mutex_trylock(&abba->b_mutex, &ctx)); 199 200 WARN_ON(READ_ONCE(abba->b_mutex.ctx) != &ctx); 201 202 complete(&abba->b_ready); 203 wait_for_completion(&abba->a_ready); 204 205 err = ww_mutex_lock(&abba->a_mutex, &ctx); 206 if (abba->resolve && err == -EDEADLK) { 207 ww_mutex_unlock(&abba->b_mutex); 208 ww_mutex_lock_slow(&abba->a_mutex, &ctx); 209 err = ww_mutex_lock(&abba->b_mutex, &ctx); 210 } 211 212 if (!err) 213 ww_mutex_unlock(&abba->a_mutex); 214 ww_mutex_unlock(&abba->b_mutex); 215 ww_acquire_fini(&ctx); 216 217 abba->result = err; 218 } 219 220 static int test_abba(bool trylock, bool resolve) 221 { 222 struct test_abba abba; 223 struct ww_acquire_ctx ctx; 224 int err, ret; 225 226 ww_mutex_init(&abba.a_mutex, &ww_class); 227 ww_mutex_init(&abba.b_mutex, &ww_class); 228 INIT_WORK_ONSTACK(&abba.work, test_abba_work); 229 init_completion(&abba.a_ready); 230 init_completion(&abba.b_ready); 231 abba.trylock = trylock; 232 abba.resolve = resolve; 233 234 schedule_work(&abba.work); 235 236 ww_acquire_init_noinject(&ctx, &ww_class); 237 if (!trylock) 238 ww_mutex_lock(&abba.a_mutex, &ctx); 239 else 240 WARN_ON(!ww_mutex_trylock(&abba.a_mutex, &ctx)); 241 242 WARN_ON(READ_ONCE(abba.a_mutex.ctx) != &ctx); 243 244 complete(&abba.a_ready); 245 wait_for_completion(&abba.b_ready); 246 247 err = ww_mutex_lock(&abba.b_mutex, &ctx); 248 if (resolve && err == -EDEADLK) { 249 ww_mutex_unlock(&abba.a_mutex); 250 ww_mutex_lock_slow(&abba.b_mutex, &ctx); 251 err = ww_mutex_lock(&abba.a_mutex, &ctx); 252 } 253 254 if (!err) 255 ww_mutex_unlock(&abba.b_mutex); 256 ww_mutex_unlock(&abba.a_mutex); 257 ww_acquire_fini(&ctx); 258 259 flush_work(&abba.work); 260 destroy_work_on_stack(&abba.work); 261 262 ret = 0; 263 if (resolve) { 264 if (err || abba.result) { 265 pr_err("%s: failed to resolve ABBA deadlock, A err=%d, B err=%d\n", 266 __func__, err, abba.result); 267 ret = -EINVAL; 268 } 269 } else { 270 if (err != -EDEADLK && abba.result != -EDEADLK) { 271 pr_err("%s: missed ABBA deadlock, A err=%d, B err=%d\n", 272 __func__, err, abba.result); 273 ret = -EINVAL; 274 } 275 } 276 return ret; 277 } 278 279 struct test_cycle { 280 struct work_struct work; 281 struct ww_mutex a_mutex; 282 struct ww_mutex *b_mutex; 283 struct completion *a_signal; 284 struct completion b_signal; 285 int result; 286 }; 287 288 static void test_cycle_work(struct work_struct *work) 289 { 290 struct test_cycle *cycle = container_of(work, typeof(*cycle), work); 291 struct ww_acquire_ctx ctx; 292 int err, erra = 0; 293 294 ww_acquire_init_noinject(&ctx, &ww_class); 295 ww_mutex_lock(&cycle->a_mutex, &ctx); 296 297 complete(cycle->a_signal); 298 wait_for_completion(&cycle->b_signal); 299 300 err = ww_mutex_lock(cycle->b_mutex, &ctx); 301 if (err == -EDEADLK) { 302 err = 0; 303 ww_mutex_unlock(&cycle->a_mutex); 304 ww_mutex_lock_slow(cycle->b_mutex, &ctx); 305 erra = ww_mutex_lock(&cycle->a_mutex, &ctx); 306 } 307 308 if (!err) 309 ww_mutex_unlock(cycle->b_mutex); 310 if (!erra) 311 ww_mutex_unlock(&cycle->a_mutex); 312 ww_acquire_fini(&ctx); 313 314 cycle->result = err ?: erra; 315 } 316 317 static int __test_cycle(unsigned int nthreads) 318 { 319 struct test_cycle *cycles; 320 unsigned int n, last = nthreads - 1; 321 int ret; 322 323 cycles = kmalloc_array(nthreads, sizeof(*cycles), GFP_KERNEL); 324 if (!cycles) 325 return -ENOMEM; 326 327 for (n = 0; n < nthreads; n++) { 328 struct test_cycle *cycle = &cycles[n]; 329 330 ww_mutex_init(&cycle->a_mutex, &ww_class); 331 if (n == last) 332 cycle->b_mutex = &cycles[0].a_mutex; 333 else 334 cycle->b_mutex = &cycles[n + 1].a_mutex; 335 336 if (n == 0) 337 cycle->a_signal = &cycles[last].b_signal; 338 else 339 cycle->a_signal = &cycles[n - 1].b_signal; 340 init_completion(&cycle->b_signal); 341 342 INIT_WORK(&cycle->work, test_cycle_work); 343 cycle->result = 0; 344 } 345 346 for (n = 0; n < nthreads; n++) 347 queue_work(wq, &cycles[n].work); 348 349 flush_workqueue(wq); 350 351 ret = 0; 352 for (n = 0; n < nthreads; n++) { 353 struct test_cycle *cycle = &cycles[n]; 354 355 if (!cycle->result) 356 continue; 357 358 pr_err("cyclic deadlock not resolved, ret[%d/%d] = %d\n", 359 n, nthreads, cycle->result); 360 ret = -EINVAL; 361 break; 362 } 363 364 for (n = 0; n < nthreads; n++) 365 ww_mutex_destroy(&cycles[n].a_mutex); 366 kfree(cycles); 367 return ret; 368 } 369 370 static int test_cycle(unsigned int ncpus) 371 { 372 unsigned int n; 373 int ret; 374 375 for (n = 2; n <= ncpus + 1; n++) { 376 ret = __test_cycle(n); 377 if (ret) 378 return ret; 379 } 380 381 return 0; 382 } 383 384 struct stress { 385 struct work_struct work; 386 struct ww_mutex *locks; 387 unsigned long timeout; 388 int nlocks; 389 }; 390 391 struct rnd_state rng; 392 DEFINE_SPINLOCK(rng_lock); 393 394 static inline u32 prandom_u32_below(u32 ceil) 395 { 396 u32 ret; 397 398 spin_lock(&rng_lock); 399 ret = prandom_u32_state(&rng) % ceil; 400 spin_unlock(&rng_lock); 401 return ret; 402 } 403 404 static int *get_random_order(int count) 405 { 406 int *order; 407 int n, r, tmp; 408 409 order = kmalloc_array(count, sizeof(*order), GFP_KERNEL); 410 if (!order) 411 return order; 412 413 for (n = 0; n < count; n++) 414 order[n] = n; 415 416 for (n = count - 1; n > 1; n--) { 417 r = prandom_u32_below(n + 1); 418 if (r != n) { 419 tmp = order[n]; 420 order[n] = order[r]; 421 order[r] = tmp; 422 } 423 } 424 425 return order; 426 } 427 428 static void dummy_load(struct stress *stress) 429 { 430 usleep_range(1000, 2000); 431 } 432 433 static void stress_inorder_work(struct work_struct *work) 434 { 435 struct stress *stress = container_of(work, typeof(*stress), work); 436 const int nlocks = stress->nlocks; 437 struct ww_mutex *locks = stress->locks; 438 struct ww_acquire_ctx ctx; 439 int *order; 440 441 order = get_random_order(nlocks); 442 if (!order) 443 return; 444 445 do { 446 int contended = -1; 447 int n, err; 448 449 ww_acquire_init(&ctx, &ww_class); 450 retry: 451 err = 0; 452 for (n = 0; n < nlocks; n++) { 453 if (n == contended) 454 continue; 455 456 err = ww_mutex_lock(&locks[order[n]], &ctx); 457 if (err < 0) 458 break; 459 } 460 if (!err) 461 dummy_load(stress); 462 463 if (contended > n) 464 ww_mutex_unlock(&locks[order[contended]]); 465 contended = n; 466 while (n--) 467 ww_mutex_unlock(&locks[order[n]]); 468 469 if (err == -EDEADLK) { 470 if (!time_after(jiffies, stress->timeout)) { 471 ww_mutex_lock_slow(&locks[order[contended]], &ctx); 472 goto retry; 473 } 474 } 475 476 ww_acquire_fini(&ctx); 477 if (err) { 478 pr_err_once("stress (%s) failed with %d\n", 479 __func__, err); 480 break; 481 } 482 } while (!time_after(jiffies, stress->timeout)); 483 484 kfree(order); 485 } 486 487 struct reorder_lock { 488 struct list_head link; 489 struct ww_mutex *lock; 490 }; 491 492 static void stress_reorder_work(struct work_struct *work) 493 { 494 struct stress *stress = container_of(work, typeof(*stress), work); 495 LIST_HEAD(locks); 496 struct ww_acquire_ctx ctx; 497 struct reorder_lock *ll, *ln; 498 int *order; 499 int n, err; 500 501 order = get_random_order(stress->nlocks); 502 if (!order) 503 return; 504 505 for (n = 0; n < stress->nlocks; n++) { 506 ll = kmalloc(sizeof(*ll), GFP_KERNEL); 507 if (!ll) 508 goto out; 509 510 ll->lock = &stress->locks[order[n]]; 511 list_add(&ll->link, &locks); 512 } 513 kfree(order); 514 order = NULL; 515 516 do { 517 ww_acquire_init(&ctx, &ww_class); 518 519 list_for_each_entry(ll, &locks, link) { 520 err = ww_mutex_lock(ll->lock, &ctx); 521 if (!err) 522 continue; 523 524 ln = ll; 525 list_for_each_entry_continue_reverse(ln, &locks, link) 526 ww_mutex_unlock(ln->lock); 527 528 if (err != -EDEADLK) { 529 pr_err_once("stress (%s) failed with %d\n", 530 __func__, err); 531 break; 532 } 533 534 ww_mutex_lock_slow(ll->lock, &ctx); 535 list_move(&ll->link, &locks); /* restarts iteration */ 536 } 537 538 dummy_load(stress); 539 list_for_each_entry(ll, &locks, link) 540 ww_mutex_unlock(ll->lock); 541 542 ww_acquire_fini(&ctx); 543 } while (!time_after(jiffies, stress->timeout)); 544 545 out: 546 list_for_each_entry_safe(ll, ln, &locks, link) 547 kfree(ll); 548 kfree(order); 549 } 550 551 static void stress_one_work(struct work_struct *work) 552 { 553 struct stress *stress = container_of(work, typeof(*stress), work); 554 const int nlocks = stress->nlocks; 555 struct ww_mutex *lock = stress->locks + get_random_u32_below(nlocks); 556 int err; 557 558 do { 559 err = ww_mutex_lock(lock, NULL); 560 if (!err) { 561 dummy_load(stress); 562 ww_mutex_unlock(lock); 563 } else { 564 pr_err_once("stress (%s) failed with %d\n", 565 __func__, err); 566 break; 567 } 568 } while (!time_after(jiffies, stress->timeout)); 569 } 570 571 #define STRESS_INORDER BIT(0) 572 #define STRESS_REORDER BIT(1) 573 #define STRESS_ONE BIT(2) 574 #define STRESS_ALL (STRESS_INORDER | STRESS_REORDER | STRESS_ONE) 575 576 static int stress(int nlocks, int nthreads, unsigned int flags) 577 { 578 struct ww_mutex *locks; 579 struct stress *stress_array; 580 int n, count; 581 582 locks = kmalloc_array(nlocks, sizeof(*locks), GFP_KERNEL); 583 if (!locks) 584 return -ENOMEM; 585 586 stress_array = kmalloc_array(nthreads, sizeof(*stress_array), 587 GFP_KERNEL); 588 if (!stress_array) { 589 kfree(locks); 590 return -ENOMEM; 591 } 592 593 for (n = 0; n < nlocks; n++) 594 ww_mutex_init(&locks[n], &ww_class); 595 596 count = 0; 597 for (n = 0; nthreads; n++) { 598 struct stress *stress; 599 void (*fn)(struct work_struct *work); 600 601 fn = NULL; 602 switch (n & 3) { 603 case 0: 604 if (flags & STRESS_INORDER) 605 fn = stress_inorder_work; 606 break; 607 case 1: 608 if (flags & STRESS_REORDER) 609 fn = stress_reorder_work; 610 break; 611 case 2: 612 if (flags & STRESS_ONE) 613 fn = stress_one_work; 614 break; 615 } 616 617 if (!fn) 618 continue; 619 620 stress = &stress_array[count++]; 621 622 INIT_WORK(&stress->work, fn); 623 stress->locks = locks; 624 stress->nlocks = nlocks; 625 stress->timeout = jiffies + 2*HZ; 626 627 queue_work(wq, &stress->work); 628 nthreads--; 629 } 630 631 flush_workqueue(wq); 632 633 for (n = 0; n < nlocks; n++) 634 ww_mutex_destroy(&locks[n]); 635 kfree(stress_array); 636 kfree(locks); 637 638 return 0; 639 } 640 641 static int __init test_ww_mutex_init(void) 642 { 643 int ncpus = num_online_cpus(); 644 int ret, i; 645 646 printk(KERN_INFO "Beginning ww mutex selftests\n"); 647 648 prandom_seed_state(&rng, get_random_u64()); 649 650 wq = alloc_workqueue("test-ww_mutex", WQ_UNBOUND, 0); 651 if (!wq) 652 return -ENOMEM; 653 654 ret = test_mutex(); 655 if (ret) 656 return ret; 657 658 ret = test_aa(false); 659 if (ret) 660 return ret; 661 662 ret = test_aa(true); 663 if (ret) 664 return ret; 665 666 for (i = 0; i < 4; i++) { 667 ret = test_abba(i & 1, i & 2); 668 if (ret) 669 return ret; 670 } 671 672 ret = test_cycle(ncpus); 673 if (ret) 674 return ret; 675 676 ret = stress(16, 2*ncpus, STRESS_INORDER); 677 if (ret) 678 return ret; 679 680 ret = stress(16, 2*ncpus, STRESS_REORDER); 681 if (ret) 682 return ret; 683 684 ret = stress(2046, hweight32(STRESS_ALL)*ncpus, STRESS_ALL); 685 if (ret) 686 return ret; 687 688 printk(KERN_INFO "All ww mutex selftests passed\n"); 689 return 0; 690 } 691 692 static void __exit test_ww_mutex_exit(void) 693 { 694 destroy_workqueue(wq); 695 } 696 697 module_init(test_ww_mutex_init); 698 module_exit(test_ww_mutex_exit); 699 700 MODULE_LICENSE("GPL"); 701 MODULE_AUTHOR("Intel Corporation"); 702 MODULE_DESCRIPTION("API test facility for ww_mutexes"); 703