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; 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 ww_mutex_unlock(&cycle->a_mutex); 274 ww_mutex_lock_slow(cycle->b_mutex, &ctx); 275 err = ww_mutex_lock(&cycle->a_mutex, &ctx); 276 } 277 278 if (!err) 279 ww_mutex_unlock(cycle->b_mutex); 280 ww_mutex_unlock(&cycle->a_mutex); 281 ww_acquire_fini(&ctx); 282 283 cycle->result = err; 284 } 285 286 static int __test_cycle(unsigned int nthreads) 287 { 288 struct test_cycle *cycles; 289 unsigned int n, last = nthreads - 1; 290 int ret; 291 292 cycles = kmalloc_array(nthreads, sizeof(*cycles), GFP_KERNEL); 293 if (!cycles) 294 return -ENOMEM; 295 296 for (n = 0; n < nthreads; n++) { 297 struct test_cycle *cycle = &cycles[n]; 298 299 ww_mutex_init(&cycle->a_mutex, &ww_class); 300 if (n == last) 301 cycle->b_mutex = &cycles[0].a_mutex; 302 else 303 cycle->b_mutex = &cycles[n + 1].a_mutex; 304 305 if (n == 0) 306 cycle->a_signal = &cycles[last].b_signal; 307 else 308 cycle->a_signal = &cycles[n - 1].b_signal; 309 init_completion(&cycle->b_signal); 310 311 INIT_WORK(&cycle->work, test_cycle_work); 312 cycle->result = 0; 313 } 314 315 for (n = 0; n < nthreads; n++) 316 queue_work(wq, &cycles[n].work); 317 318 flush_workqueue(wq); 319 320 ret = 0; 321 for (n = 0; n < nthreads; n++) { 322 struct test_cycle *cycle = &cycles[n]; 323 324 if (!cycle->result) 325 continue; 326 327 pr_err("cylic deadlock not resolved, ret[%d/%d] = %d\n", 328 n, nthreads, cycle->result); 329 ret = -EINVAL; 330 break; 331 } 332 333 for (n = 0; n < nthreads; n++) 334 ww_mutex_destroy(&cycles[n].a_mutex); 335 kfree(cycles); 336 return ret; 337 } 338 339 static int test_cycle(unsigned int ncpus) 340 { 341 unsigned int n; 342 int ret; 343 344 for (n = 2; n <= ncpus + 1; n++) { 345 ret = __test_cycle(n); 346 if (ret) 347 return ret; 348 } 349 350 return 0; 351 } 352 353 struct stress { 354 struct work_struct work; 355 struct ww_mutex *locks; 356 unsigned long timeout; 357 int nlocks; 358 }; 359 360 static int *get_random_order(int count) 361 { 362 int *order; 363 int n, r, tmp; 364 365 order = kmalloc_array(count, sizeof(*order), GFP_KERNEL); 366 if (!order) 367 return order; 368 369 for (n = 0; n < count; n++) 370 order[n] = n; 371 372 for (n = count - 1; n > 1; n--) { 373 r = get_random_int() % (n + 1); 374 if (r != n) { 375 tmp = order[n]; 376 order[n] = order[r]; 377 order[r] = tmp; 378 } 379 } 380 381 return order; 382 } 383 384 static void dummy_load(struct stress *stress) 385 { 386 usleep_range(1000, 2000); 387 } 388 389 static void stress_inorder_work(struct work_struct *work) 390 { 391 struct stress *stress = container_of(work, typeof(*stress), work); 392 const int nlocks = stress->nlocks; 393 struct ww_mutex *locks = stress->locks; 394 struct ww_acquire_ctx ctx; 395 int *order; 396 397 order = get_random_order(nlocks); 398 if (!order) 399 return; 400 401 do { 402 int contended = -1; 403 int n, err; 404 405 ww_acquire_init(&ctx, &ww_class); 406 retry: 407 err = 0; 408 for (n = 0; n < nlocks; n++) { 409 if (n == contended) 410 continue; 411 412 err = ww_mutex_lock(&locks[order[n]], &ctx); 413 if (err < 0) 414 break; 415 } 416 if (!err) 417 dummy_load(stress); 418 419 if (contended > n) 420 ww_mutex_unlock(&locks[order[contended]]); 421 contended = n; 422 while (n--) 423 ww_mutex_unlock(&locks[order[n]]); 424 425 if (err == -EDEADLK) { 426 ww_mutex_lock_slow(&locks[order[contended]], &ctx); 427 goto retry; 428 } 429 430 if (err) { 431 pr_err_once("stress (%s) failed with %d\n", 432 __func__, err); 433 break; 434 } 435 436 ww_acquire_fini(&ctx); 437 } while (!time_after(jiffies, stress->timeout)); 438 439 kfree(order); 440 kfree(stress); 441 } 442 443 struct reorder_lock { 444 struct list_head link; 445 struct ww_mutex *lock; 446 }; 447 448 static void stress_reorder_work(struct work_struct *work) 449 { 450 struct stress *stress = container_of(work, typeof(*stress), work); 451 LIST_HEAD(locks); 452 struct ww_acquire_ctx ctx; 453 struct reorder_lock *ll, *ln; 454 int *order; 455 int n, err; 456 457 order = get_random_order(stress->nlocks); 458 if (!order) 459 return; 460 461 for (n = 0; n < stress->nlocks; n++) { 462 ll = kmalloc(sizeof(*ll), GFP_KERNEL); 463 if (!ll) 464 goto out; 465 466 ll->lock = &stress->locks[order[n]]; 467 list_add(&ll->link, &locks); 468 } 469 kfree(order); 470 order = NULL; 471 472 do { 473 ww_acquire_init(&ctx, &ww_class); 474 475 list_for_each_entry(ll, &locks, link) { 476 err = ww_mutex_lock(ll->lock, &ctx); 477 if (!err) 478 continue; 479 480 ln = ll; 481 list_for_each_entry_continue_reverse(ln, &locks, link) 482 ww_mutex_unlock(ln->lock); 483 484 if (err != -EDEADLK) { 485 pr_err_once("stress (%s) failed with %d\n", 486 __func__, err); 487 break; 488 } 489 490 ww_mutex_lock_slow(ll->lock, &ctx); 491 list_move(&ll->link, &locks); /* restarts iteration */ 492 } 493 494 dummy_load(stress); 495 list_for_each_entry(ll, &locks, link) 496 ww_mutex_unlock(ll->lock); 497 498 ww_acquire_fini(&ctx); 499 } while (!time_after(jiffies, stress->timeout)); 500 501 out: 502 list_for_each_entry_safe(ll, ln, &locks, link) 503 kfree(ll); 504 kfree(order); 505 kfree(stress); 506 } 507 508 static void stress_one_work(struct work_struct *work) 509 { 510 struct stress *stress = container_of(work, typeof(*stress), work); 511 const int nlocks = stress->nlocks; 512 struct ww_mutex *lock = stress->locks + (get_random_int() % nlocks); 513 int err; 514 515 do { 516 err = ww_mutex_lock(lock, NULL); 517 if (!err) { 518 dummy_load(stress); 519 ww_mutex_unlock(lock); 520 } else { 521 pr_err_once("stress (%s) failed with %d\n", 522 __func__, err); 523 break; 524 } 525 } while (!time_after(jiffies, stress->timeout)); 526 527 kfree(stress); 528 } 529 530 #define STRESS_INORDER BIT(0) 531 #define STRESS_REORDER BIT(1) 532 #define STRESS_ONE BIT(2) 533 #define STRESS_ALL (STRESS_INORDER | STRESS_REORDER | STRESS_ONE) 534 535 static int stress(int nlocks, int nthreads, unsigned int flags) 536 { 537 struct ww_mutex *locks; 538 int n; 539 540 locks = kmalloc_array(nlocks, sizeof(*locks), GFP_KERNEL); 541 if (!locks) 542 return -ENOMEM; 543 544 for (n = 0; n < nlocks; n++) 545 ww_mutex_init(&locks[n], &ww_class); 546 547 for (n = 0; nthreads; n++) { 548 struct stress *stress; 549 void (*fn)(struct work_struct *work); 550 551 fn = NULL; 552 switch (n & 3) { 553 case 0: 554 if (flags & STRESS_INORDER) 555 fn = stress_inorder_work; 556 break; 557 case 1: 558 if (flags & STRESS_REORDER) 559 fn = stress_reorder_work; 560 break; 561 case 2: 562 if (flags & STRESS_ONE) 563 fn = stress_one_work; 564 break; 565 } 566 567 if (!fn) 568 continue; 569 570 stress = kmalloc(sizeof(*stress), GFP_KERNEL); 571 if (!stress) 572 break; 573 574 INIT_WORK(&stress->work, fn); 575 stress->locks = locks; 576 stress->nlocks = nlocks; 577 stress->timeout = jiffies + 2*HZ; 578 579 queue_work(wq, &stress->work); 580 nthreads--; 581 } 582 583 flush_workqueue(wq); 584 585 for (n = 0; n < nlocks; n++) 586 ww_mutex_destroy(&locks[n]); 587 kfree(locks); 588 589 return 0; 590 } 591 592 static int __init test_ww_mutex_init(void) 593 { 594 int ncpus = num_online_cpus(); 595 int ret; 596 597 wq = alloc_workqueue("test-ww_mutex", WQ_UNBOUND, 0); 598 if (!wq) 599 return -ENOMEM; 600 601 ret = test_mutex(); 602 if (ret) 603 return ret; 604 605 ret = test_aa(); 606 if (ret) 607 return ret; 608 609 ret = test_abba(false); 610 if (ret) 611 return ret; 612 613 ret = test_abba(true); 614 if (ret) 615 return ret; 616 617 ret = test_cycle(ncpus); 618 if (ret) 619 return ret; 620 621 ret = stress(16, 2*ncpus, STRESS_INORDER); 622 if (ret) 623 return ret; 624 625 ret = stress(16, 2*ncpus, STRESS_REORDER); 626 if (ret) 627 return ret; 628 629 ret = stress(4095, hweight32(STRESS_ALL)*ncpus, STRESS_ALL); 630 if (ret) 631 return ret; 632 633 return 0; 634 } 635 636 static void __exit test_ww_mutex_exit(void) 637 { 638 destroy_workqueue(wq); 639 } 640 641 module_init(test_ww_mutex_init); 642 module_exit(test_ww_mutex_exit); 643 644 MODULE_LICENSE("GPL"); 645 MODULE_AUTHOR("Intel Corporation"); 646