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