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