kernel/locking/test-ww_mutex.c

   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");