kernel/locking/test-ww_mutex.c

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