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/random.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 static int *get_random_order(int count) 390 { 391 int *order; 392 int n, r, tmp; 393 394 order = kmalloc_array(count, sizeof(*order), GFP_KERNEL); 395 if (!order) 396 return order; 397 398 for (n = 0; n < count; n++) 399 order[n] = n; 400 401 for (n = count - 1; n > 1; n--) { 402 r = get_random_u32_below(n + 1); 403 if (r != n) { 404 tmp = order[n]; 405 order[n] = order[r]; 406 order[r] = tmp; 407 } 408 } 409 410 return order; 411 } 412 413 static void dummy_load(struct stress *stress) 414 { 415 usleep_range(1000, 2000); 416 } 417 418 static void stress_inorder_work(struct work_struct *work) 419 { 420 struct stress *stress = container_of(work, typeof(*stress), work); 421 const int nlocks = stress->nlocks; 422 struct ww_mutex *locks = stress->locks; 423 struct ww_acquire_ctx ctx; 424 int *order; 425 426 order = get_random_order(nlocks); 427 if (!order) 428 return; 429 430 do { 431 int contended = -1; 432 int n, err; 433 434 ww_acquire_init(&ctx, &ww_class); 435 retry: 436 err = 0; 437 for (n = 0; n < nlocks; n++) { 438 if (n == contended) 439 continue; 440 441 err = ww_mutex_lock(&locks[order[n]], &ctx); 442 if (err < 0) 443 break; 444 } 445 if (!err) 446 dummy_load(stress); 447 448 if (contended > n) 449 ww_mutex_unlock(&locks[order[contended]]); 450 contended = n; 451 while (n--) 452 ww_mutex_unlock(&locks[order[n]]); 453 454 if (err == -EDEADLK) { 455 ww_mutex_lock_slow(&locks[order[contended]], &ctx); 456 goto retry; 457 } 458 459 if (err) { 460 pr_err_once("stress (%s) failed with %d\n", 461 __func__, err); 462 break; 463 } 464 465 ww_acquire_fini(&ctx); 466 } while (!time_after(jiffies, stress->timeout)); 467 468 kfree(order); 469 kfree(stress); 470 } 471 472 struct reorder_lock { 473 struct list_head link; 474 struct ww_mutex *lock; 475 }; 476 477 static void stress_reorder_work(struct work_struct *work) 478 { 479 struct stress *stress = container_of(work, typeof(*stress), work); 480 LIST_HEAD(locks); 481 struct ww_acquire_ctx ctx; 482 struct reorder_lock *ll, *ln; 483 int *order; 484 int n, err; 485 486 order = get_random_order(stress->nlocks); 487 if (!order) 488 return; 489 490 for (n = 0; n < stress->nlocks; n++) { 491 ll = kmalloc(sizeof(*ll), GFP_KERNEL); 492 if (!ll) 493 goto out; 494 495 ll->lock = &stress->locks[order[n]]; 496 list_add(&ll->link, &locks); 497 } 498 kfree(order); 499 order = NULL; 500 501 do { 502 ww_acquire_init(&ctx, &ww_class); 503 504 list_for_each_entry(ll, &locks, link) { 505 err = ww_mutex_lock(ll->lock, &ctx); 506 if (!err) 507 continue; 508 509 ln = ll; 510 list_for_each_entry_continue_reverse(ln, &locks, link) 511 ww_mutex_unlock(ln->lock); 512 513 if (err != -EDEADLK) { 514 pr_err_once("stress (%s) failed with %d\n", 515 __func__, err); 516 break; 517 } 518 519 ww_mutex_lock_slow(ll->lock, &ctx); 520 list_move(&ll->link, &locks); /* restarts iteration */ 521 } 522 523 dummy_load(stress); 524 list_for_each_entry(ll, &locks, link) 525 ww_mutex_unlock(ll->lock); 526 527 ww_acquire_fini(&ctx); 528 } while (!time_after(jiffies, stress->timeout)); 529 530 out: 531 list_for_each_entry_safe(ll, ln, &locks, link) 532 kfree(ll); 533 kfree(order); 534 kfree(stress); 535 } 536 537 static void stress_one_work(struct work_struct *work) 538 { 539 struct stress *stress = container_of(work, typeof(*stress), work); 540 const int nlocks = stress->nlocks; 541 struct ww_mutex *lock = stress->locks + get_random_u32_below(nlocks); 542 int err; 543 544 do { 545 err = ww_mutex_lock(lock, NULL); 546 if (!err) { 547 dummy_load(stress); 548 ww_mutex_unlock(lock); 549 } else { 550 pr_err_once("stress (%s) failed with %d\n", 551 __func__, err); 552 break; 553 } 554 } while (!time_after(jiffies, stress->timeout)); 555 556 kfree(stress); 557 } 558 559 #define STRESS_INORDER BIT(0) 560 #define STRESS_REORDER BIT(1) 561 #define STRESS_ONE BIT(2) 562 #define STRESS_ALL (STRESS_INORDER | STRESS_REORDER | STRESS_ONE) 563 564 static int stress(int nlocks, int nthreads, unsigned int flags) 565 { 566 struct ww_mutex *locks; 567 int n; 568 569 locks = kmalloc_array(nlocks, sizeof(*locks), GFP_KERNEL); 570 if (!locks) 571 return -ENOMEM; 572 573 for (n = 0; n < nlocks; n++) 574 ww_mutex_init(&locks[n], &ww_class); 575 576 for (n = 0; nthreads; n++) { 577 struct stress *stress; 578 void (*fn)(struct work_struct *work); 579 580 fn = NULL; 581 switch (n & 3) { 582 case 0: 583 if (flags & STRESS_INORDER) 584 fn = stress_inorder_work; 585 break; 586 case 1: 587 if (flags & STRESS_REORDER) 588 fn = stress_reorder_work; 589 break; 590 case 2: 591 if (flags & STRESS_ONE) 592 fn = stress_one_work; 593 break; 594 } 595 596 if (!fn) 597 continue; 598 599 stress = kmalloc(sizeof(*stress), GFP_KERNEL); 600 if (!stress) 601 break; 602 603 INIT_WORK(&stress->work, fn); 604 stress->locks = locks; 605 stress->nlocks = nlocks; 606 stress->timeout = jiffies + 2*HZ; 607 608 queue_work(wq, &stress->work); 609 nthreads--; 610 } 611 612 flush_workqueue(wq); 613 614 for (n = 0; n < nlocks; n++) 615 ww_mutex_destroy(&locks[n]); 616 kfree(locks); 617 618 return 0; 619 } 620 621 static int __init test_ww_mutex_init(void) 622 { 623 int ncpus = num_online_cpus(); 624 int ret, i; 625 626 printk(KERN_INFO "Beginning ww mutex selftests\n"); 627 628 wq = alloc_workqueue("test-ww_mutex", WQ_UNBOUND, 0); 629 if (!wq) 630 return -ENOMEM; 631 632 ret = test_mutex(); 633 if (ret) 634 return ret; 635 636 ret = test_aa(false); 637 if (ret) 638 return ret; 639 640 ret = test_aa(true); 641 if (ret) 642 return ret; 643 644 for (i = 0; i < 4; i++) { 645 ret = test_abba(i & 1, i & 2); 646 if (ret) 647 return ret; 648 } 649 650 ret = test_cycle(ncpus); 651 if (ret) 652 return ret; 653 654 ret = stress(16, 2*ncpus, STRESS_INORDER); 655 if (ret) 656 return ret; 657 658 ret = stress(16, 2*ncpus, STRESS_REORDER); 659 if (ret) 660 return ret; 661 662 ret = stress(2047, hweight32(STRESS_ALL)*ncpus, STRESS_ALL); 663 if (ret) 664 return ret; 665 666 printk(KERN_INFO "All ww mutex selftests passed\n"); 667 return 0; 668 } 669 670 static void __exit test_ww_mutex_exit(void) 671 { 672 destroy_workqueue(wq); 673 } 674 675 module_init(test_ww_mutex_init); 676 module_exit(test_ww_mutex_exit); 677 678 MODULE_LICENSE("GPL"); 679 MODULE_AUTHOR("Intel Corporation"); 680