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