1d6cd1e9bSThomas Gleixner // SPDX-License-Identifier: GPL-2.0-or-later 2f2a5fec1SChris Wilson /* 3f2a5fec1SChris Wilson * Module-based API test facility for ww_mutexes 4f2a5fec1SChris Wilson */ 5f2a5fec1SChris Wilson 6f2a5fec1SChris Wilson #include <linux/kernel.h> 7f2a5fec1SChris Wilson 8f2a5fec1SChris Wilson #include <linux/completion.h> 92a0c1128SChris Wilson #include <linux/delay.h> 10f2a5fec1SChris Wilson #include <linux/kthread.h> 11f2a5fec1SChris Wilson #include <linux/module.h> 122a0c1128SChris Wilson #include <linux/random.h> 13d1b42b80SChris Wilson #include <linux/slab.h> 14f2a5fec1SChris Wilson #include <linux/ww_mutex.h> 15f2a5fec1SChris Wilson 1608295b3bSThomas Hellstrom static DEFINE_WD_CLASS(ww_class); 17d1b42b80SChris Wilson struct workqueue_struct *wq; 18f2a5fec1SChris Wilson 1912235da8SMaarten Lankhorst #ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH 2012235da8SMaarten Lankhorst #define ww_acquire_init_noinject(a, b) do { \ 2112235da8SMaarten Lankhorst ww_acquire_init((a), (b)); \ 2212235da8SMaarten Lankhorst (a)->deadlock_inject_countdown = ~0U; \ 2312235da8SMaarten Lankhorst } while (0) 2412235da8SMaarten Lankhorst #else 2512235da8SMaarten Lankhorst #define ww_acquire_init_noinject(a, b) ww_acquire_init((a), (b)) 2612235da8SMaarten Lankhorst #endif 2712235da8SMaarten Lankhorst 28f2a5fec1SChris Wilson struct test_mutex { 29f2a5fec1SChris Wilson struct work_struct work; 30f2a5fec1SChris Wilson struct ww_mutex mutex; 31f2a5fec1SChris Wilson struct completion ready, go, done; 32f2a5fec1SChris Wilson unsigned int flags; 33f2a5fec1SChris Wilson }; 34f2a5fec1SChris Wilson 35f2a5fec1SChris Wilson #define TEST_MTX_SPIN BIT(0) 36f2a5fec1SChris Wilson #define TEST_MTX_TRY BIT(1) 37f2a5fec1SChris Wilson #define TEST_MTX_CTX BIT(2) 38f2a5fec1SChris Wilson #define __TEST_MTX_LAST BIT(3) 39f2a5fec1SChris Wilson 40f2a5fec1SChris Wilson static void test_mutex_work(struct work_struct *work) 41f2a5fec1SChris Wilson { 42f2a5fec1SChris Wilson struct test_mutex *mtx = container_of(work, typeof(*mtx), work); 43f2a5fec1SChris Wilson 44f2a5fec1SChris Wilson complete(&mtx->ready); 45f2a5fec1SChris Wilson wait_for_completion(&mtx->go); 46f2a5fec1SChris Wilson 47f2a5fec1SChris Wilson if (mtx->flags & TEST_MTX_TRY) { 4812235da8SMaarten Lankhorst while (!ww_mutex_trylock(&mtx->mutex, NULL)) 492b232e0cSChris Wilson cond_resched(); 50f2a5fec1SChris Wilson } else { 51f2a5fec1SChris Wilson ww_mutex_lock(&mtx->mutex, NULL); 52f2a5fec1SChris Wilson } 53f2a5fec1SChris Wilson complete(&mtx->done); 54f2a5fec1SChris Wilson ww_mutex_unlock(&mtx->mutex); 55f2a5fec1SChris Wilson } 56f2a5fec1SChris Wilson 57f2a5fec1SChris Wilson static int __test_mutex(unsigned int flags) 58f2a5fec1SChris Wilson { 59f2a5fec1SChris Wilson #define TIMEOUT (HZ / 16) 60f2a5fec1SChris Wilson struct test_mutex mtx; 61f2a5fec1SChris Wilson struct ww_acquire_ctx ctx; 62f2a5fec1SChris Wilson int ret; 63f2a5fec1SChris Wilson 64f2a5fec1SChris Wilson ww_mutex_init(&mtx.mutex, &ww_class); 65f2a5fec1SChris Wilson ww_acquire_init(&ctx, &ww_class); 66f2a5fec1SChris Wilson 67f2a5fec1SChris Wilson INIT_WORK_ONSTACK(&mtx.work, test_mutex_work); 68f2a5fec1SChris Wilson init_completion(&mtx.ready); 69f2a5fec1SChris Wilson init_completion(&mtx.go); 70f2a5fec1SChris Wilson init_completion(&mtx.done); 71f2a5fec1SChris Wilson mtx.flags = flags; 72f2a5fec1SChris Wilson 73f2a5fec1SChris Wilson schedule_work(&mtx.work); 74f2a5fec1SChris Wilson 75f2a5fec1SChris Wilson wait_for_completion(&mtx.ready); 76f2a5fec1SChris Wilson ww_mutex_lock(&mtx.mutex, (flags & TEST_MTX_CTX) ? &ctx : NULL); 77f2a5fec1SChris Wilson complete(&mtx.go); 78f2a5fec1SChris Wilson if (flags & TEST_MTX_SPIN) { 79f2a5fec1SChris Wilson unsigned long timeout = jiffies + TIMEOUT; 80f2a5fec1SChris Wilson 81f2a5fec1SChris Wilson ret = 0; 82f2a5fec1SChris Wilson do { 83f2a5fec1SChris Wilson if (completion_done(&mtx.done)) { 84f2a5fec1SChris Wilson ret = -EINVAL; 85f2a5fec1SChris Wilson break; 86f2a5fec1SChris Wilson } 872b232e0cSChris Wilson cond_resched(); 88f2a5fec1SChris Wilson } while (time_before(jiffies, timeout)); 89f2a5fec1SChris Wilson } else { 90f2a5fec1SChris Wilson ret = wait_for_completion_timeout(&mtx.done, TIMEOUT); 91f2a5fec1SChris Wilson } 92f2a5fec1SChris Wilson ww_mutex_unlock(&mtx.mutex); 93f2a5fec1SChris Wilson ww_acquire_fini(&ctx); 94f2a5fec1SChris Wilson 95f2a5fec1SChris Wilson if (ret) { 96f2a5fec1SChris Wilson pr_err("%s(flags=%x): mutual exclusion failure\n", 97f2a5fec1SChris Wilson __func__, flags); 98f2a5fec1SChris Wilson ret = -EINVAL; 99f2a5fec1SChris Wilson } 100f2a5fec1SChris Wilson 101f2a5fec1SChris Wilson flush_work(&mtx.work); 102f2a5fec1SChris Wilson destroy_work_on_stack(&mtx.work); 103f2a5fec1SChris Wilson return ret; 104f2a5fec1SChris Wilson #undef TIMEOUT 105f2a5fec1SChris Wilson } 106f2a5fec1SChris Wilson 107f2a5fec1SChris Wilson static int test_mutex(void) 108f2a5fec1SChris Wilson { 109f2a5fec1SChris Wilson int ret; 110f2a5fec1SChris Wilson int i; 111f2a5fec1SChris Wilson 112f2a5fec1SChris Wilson for (i = 0; i < __TEST_MTX_LAST; i++) { 113f2a5fec1SChris Wilson ret = __test_mutex(i); 114f2a5fec1SChris Wilson if (ret) 115f2a5fec1SChris Wilson return ret; 116f2a5fec1SChris Wilson } 117f2a5fec1SChris Wilson 118f2a5fec1SChris Wilson return 0; 119f2a5fec1SChris Wilson } 120f2a5fec1SChris Wilson 12112235da8SMaarten Lankhorst static int test_aa(bool trylock) 122c22fb380SChris Wilson { 123c22fb380SChris Wilson struct ww_mutex mutex; 124c22fb380SChris Wilson struct ww_acquire_ctx ctx; 125c22fb380SChris Wilson int ret; 12612235da8SMaarten Lankhorst const char *from = trylock ? "trylock" : "lock"; 127c22fb380SChris Wilson 128c22fb380SChris Wilson ww_mutex_init(&mutex, &ww_class); 129c22fb380SChris Wilson ww_acquire_init(&ctx, &ww_class); 130c22fb380SChris Wilson 13112235da8SMaarten Lankhorst if (!trylock) { 13212235da8SMaarten Lankhorst ret = ww_mutex_lock(&mutex, &ctx); 13312235da8SMaarten Lankhorst if (ret) { 13412235da8SMaarten Lankhorst pr_err("%s: initial lock failed!\n", __func__); 13512235da8SMaarten Lankhorst goto out; 13612235da8SMaarten Lankhorst } 13712235da8SMaarten Lankhorst } else { 1381415b49bSNathan Chancellor ret = !ww_mutex_trylock(&mutex, &ctx); 1391415b49bSNathan Chancellor if (ret) { 14012235da8SMaarten Lankhorst pr_err("%s: initial trylock failed!\n", __func__); 14112235da8SMaarten Lankhorst goto out; 14212235da8SMaarten Lankhorst } 14312235da8SMaarten Lankhorst } 144c22fb380SChris Wilson 14512235da8SMaarten Lankhorst if (ww_mutex_trylock(&mutex, NULL)) { 14612235da8SMaarten Lankhorst pr_err("%s: trylocked itself without context from %s!\n", __func__, from); 14712235da8SMaarten Lankhorst ww_mutex_unlock(&mutex); 14812235da8SMaarten Lankhorst ret = -EINVAL; 14912235da8SMaarten Lankhorst goto out; 15012235da8SMaarten Lankhorst } 15112235da8SMaarten Lankhorst 15212235da8SMaarten Lankhorst if (ww_mutex_trylock(&mutex, &ctx)) { 15312235da8SMaarten Lankhorst pr_err("%s: trylocked itself with context from %s!\n", __func__, from); 154c22fb380SChris Wilson ww_mutex_unlock(&mutex); 155c22fb380SChris Wilson ret = -EINVAL; 156c22fb380SChris Wilson goto out; 157c22fb380SChris Wilson } 158c22fb380SChris Wilson 159c22fb380SChris Wilson ret = ww_mutex_lock(&mutex, &ctx); 160c22fb380SChris Wilson if (ret != -EALREADY) { 16112235da8SMaarten Lankhorst pr_err("%s: missed deadlock for recursing, ret=%d from %s\n", 16212235da8SMaarten Lankhorst __func__, ret, from); 163c22fb380SChris Wilson if (!ret) 164c22fb380SChris Wilson ww_mutex_unlock(&mutex); 165c22fb380SChris Wilson ret = -EINVAL; 166c22fb380SChris Wilson goto out; 167c22fb380SChris Wilson } 168c22fb380SChris Wilson 16912235da8SMaarten Lankhorst ww_mutex_unlock(&mutex); 170c22fb380SChris Wilson ret = 0; 171c22fb380SChris Wilson out: 172c22fb380SChris Wilson ww_acquire_fini(&ctx); 173c22fb380SChris Wilson return ret; 174c22fb380SChris Wilson } 175c22fb380SChris Wilson 17670207686SChris Wilson struct test_abba { 17770207686SChris Wilson struct work_struct work; 17870207686SChris Wilson struct ww_mutex a_mutex; 17970207686SChris Wilson struct ww_mutex b_mutex; 18070207686SChris Wilson struct completion a_ready; 18170207686SChris Wilson struct completion b_ready; 18212235da8SMaarten Lankhorst bool resolve, trylock; 18370207686SChris Wilson int result; 18470207686SChris Wilson }; 18570207686SChris Wilson 18670207686SChris Wilson static void test_abba_work(struct work_struct *work) 18770207686SChris Wilson { 18870207686SChris Wilson struct test_abba *abba = container_of(work, typeof(*abba), work); 18970207686SChris Wilson struct ww_acquire_ctx ctx; 19070207686SChris Wilson int err; 19170207686SChris Wilson 19212235da8SMaarten Lankhorst ww_acquire_init_noinject(&ctx, &ww_class); 19312235da8SMaarten Lankhorst if (!abba->trylock) 19470207686SChris Wilson ww_mutex_lock(&abba->b_mutex, &ctx); 19512235da8SMaarten Lankhorst else 19612235da8SMaarten Lankhorst WARN_ON(!ww_mutex_trylock(&abba->b_mutex, &ctx)); 19712235da8SMaarten Lankhorst 19812235da8SMaarten Lankhorst WARN_ON(READ_ONCE(abba->b_mutex.ctx) != &ctx); 19970207686SChris Wilson 20070207686SChris Wilson complete(&abba->b_ready); 20170207686SChris Wilson wait_for_completion(&abba->a_ready); 20270207686SChris Wilson 20370207686SChris Wilson err = ww_mutex_lock(&abba->a_mutex, &ctx); 20470207686SChris Wilson if (abba->resolve && err == -EDEADLK) { 20570207686SChris Wilson ww_mutex_unlock(&abba->b_mutex); 20670207686SChris Wilson ww_mutex_lock_slow(&abba->a_mutex, &ctx); 20770207686SChris Wilson err = ww_mutex_lock(&abba->b_mutex, &ctx); 20870207686SChris Wilson } 20970207686SChris Wilson 21070207686SChris Wilson if (!err) 21170207686SChris Wilson ww_mutex_unlock(&abba->a_mutex); 21270207686SChris Wilson ww_mutex_unlock(&abba->b_mutex); 21370207686SChris Wilson ww_acquire_fini(&ctx); 21470207686SChris Wilson 21570207686SChris Wilson abba->result = err; 21670207686SChris Wilson } 21770207686SChris Wilson 21812235da8SMaarten Lankhorst static int test_abba(bool trylock, bool resolve) 21970207686SChris Wilson { 22070207686SChris Wilson struct test_abba abba; 22170207686SChris Wilson struct ww_acquire_ctx ctx; 22270207686SChris Wilson int err, ret; 22370207686SChris Wilson 22470207686SChris Wilson ww_mutex_init(&abba.a_mutex, &ww_class); 22570207686SChris Wilson ww_mutex_init(&abba.b_mutex, &ww_class); 22670207686SChris Wilson INIT_WORK_ONSTACK(&abba.work, test_abba_work); 22770207686SChris Wilson init_completion(&abba.a_ready); 22870207686SChris Wilson init_completion(&abba.b_ready); 22912235da8SMaarten Lankhorst abba.trylock = trylock; 23070207686SChris Wilson abba.resolve = resolve; 23170207686SChris Wilson 23270207686SChris Wilson schedule_work(&abba.work); 23370207686SChris Wilson 23412235da8SMaarten Lankhorst ww_acquire_init_noinject(&ctx, &ww_class); 23512235da8SMaarten Lankhorst if (!trylock) 23670207686SChris Wilson ww_mutex_lock(&abba.a_mutex, &ctx); 23712235da8SMaarten Lankhorst else 23812235da8SMaarten Lankhorst WARN_ON(!ww_mutex_trylock(&abba.a_mutex, &ctx)); 23912235da8SMaarten Lankhorst 24012235da8SMaarten Lankhorst WARN_ON(READ_ONCE(abba.a_mutex.ctx) != &ctx); 24170207686SChris Wilson 24270207686SChris Wilson complete(&abba.a_ready); 24370207686SChris Wilson wait_for_completion(&abba.b_ready); 24470207686SChris Wilson 24570207686SChris Wilson err = ww_mutex_lock(&abba.b_mutex, &ctx); 24670207686SChris Wilson if (resolve && err == -EDEADLK) { 24770207686SChris Wilson ww_mutex_unlock(&abba.a_mutex); 24870207686SChris Wilson ww_mutex_lock_slow(&abba.b_mutex, &ctx); 24970207686SChris Wilson err = ww_mutex_lock(&abba.a_mutex, &ctx); 25070207686SChris Wilson } 25170207686SChris Wilson 25270207686SChris Wilson if (!err) 25370207686SChris Wilson ww_mutex_unlock(&abba.b_mutex); 25470207686SChris Wilson ww_mutex_unlock(&abba.a_mutex); 25570207686SChris Wilson ww_acquire_fini(&ctx); 25670207686SChris Wilson 25770207686SChris Wilson flush_work(&abba.work); 25870207686SChris Wilson destroy_work_on_stack(&abba.work); 25970207686SChris Wilson 26070207686SChris Wilson ret = 0; 26170207686SChris Wilson if (resolve) { 26270207686SChris Wilson if (err || abba.result) { 26370207686SChris Wilson pr_err("%s: failed to resolve ABBA deadlock, A err=%d, B err=%d\n", 26470207686SChris Wilson __func__, err, abba.result); 26570207686SChris Wilson ret = -EINVAL; 26670207686SChris Wilson } 26770207686SChris Wilson } else { 26870207686SChris Wilson if (err != -EDEADLK && abba.result != -EDEADLK) { 26970207686SChris Wilson pr_err("%s: missed ABBA deadlock, A err=%d, B err=%d\n", 27070207686SChris Wilson __func__, err, abba.result); 27170207686SChris Wilson ret = -EINVAL; 27270207686SChris Wilson } 27370207686SChris Wilson } 27470207686SChris Wilson return ret; 27570207686SChris Wilson } 27670207686SChris Wilson 277d1b42b80SChris Wilson struct test_cycle { 278d1b42b80SChris Wilson struct work_struct work; 279d1b42b80SChris Wilson struct ww_mutex a_mutex; 280d1b42b80SChris Wilson struct ww_mutex *b_mutex; 281d1b42b80SChris Wilson struct completion *a_signal; 282d1b42b80SChris Wilson struct completion b_signal; 283d1b42b80SChris Wilson int result; 284d1b42b80SChris Wilson }; 285d1b42b80SChris Wilson 286d1b42b80SChris Wilson static void test_cycle_work(struct work_struct *work) 287d1b42b80SChris Wilson { 288d1b42b80SChris Wilson struct test_cycle *cycle = container_of(work, typeof(*cycle), work); 289d1b42b80SChris Wilson struct ww_acquire_ctx ctx; 290e4a02ed2SGuenter Roeck int err, erra = 0; 291d1b42b80SChris Wilson 29212235da8SMaarten Lankhorst ww_acquire_init_noinject(&ctx, &ww_class); 293d1b42b80SChris Wilson ww_mutex_lock(&cycle->a_mutex, &ctx); 294d1b42b80SChris Wilson 295d1b42b80SChris Wilson complete(cycle->a_signal); 296d1b42b80SChris Wilson wait_for_completion(&cycle->b_signal); 297d1b42b80SChris Wilson 298d1b42b80SChris Wilson err = ww_mutex_lock(cycle->b_mutex, &ctx); 299d1b42b80SChris Wilson if (err == -EDEADLK) { 300e4a02ed2SGuenter Roeck err = 0; 301d1b42b80SChris Wilson ww_mutex_unlock(&cycle->a_mutex); 302d1b42b80SChris Wilson ww_mutex_lock_slow(cycle->b_mutex, &ctx); 303e4a02ed2SGuenter Roeck erra = ww_mutex_lock(&cycle->a_mutex, &ctx); 304d1b42b80SChris Wilson } 305d1b42b80SChris Wilson 306d1b42b80SChris Wilson if (!err) 307d1b42b80SChris Wilson ww_mutex_unlock(cycle->b_mutex); 308e4a02ed2SGuenter Roeck if (!erra) 309d1b42b80SChris Wilson ww_mutex_unlock(&cycle->a_mutex); 310d1b42b80SChris Wilson ww_acquire_fini(&ctx); 311d1b42b80SChris Wilson 312e4a02ed2SGuenter Roeck cycle->result = err ?: erra; 313d1b42b80SChris Wilson } 314d1b42b80SChris Wilson 315d1b42b80SChris Wilson static int __test_cycle(unsigned int nthreads) 316d1b42b80SChris Wilson { 317d1b42b80SChris Wilson struct test_cycle *cycles; 318d1b42b80SChris Wilson unsigned int n, last = nthreads - 1; 319d1b42b80SChris Wilson int ret; 320d1b42b80SChris Wilson 321d1b42b80SChris Wilson cycles = kmalloc_array(nthreads, sizeof(*cycles), GFP_KERNEL); 322d1b42b80SChris Wilson if (!cycles) 323d1b42b80SChris Wilson return -ENOMEM; 324d1b42b80SChris Wilson 325d1b42b80SChris Wilson for (n = 0; n < nthreads; n++) { 326d1b42b80SChris Wilson struct test_cycle *cycle = &cycles[n]; 327d1b42b80SChris Wilson 328d1b42b80SChris Wilson ww_mutex_init(&cycle->a_mutex, &ww_class); 329d1b42b80SChris Wilson if (n == last) 330d1b42b80SChris Wilson cycle->b_mutex = &cycles[0].a_mutex; 331d1b42b80SChris Wilson else 332d1b42b80SChris Wilson cycle->b_mutex = &cycles[n + 1].a_mutex; 333d1b42b80SChris Wilson 334d1b42b80SChris Wilson if (n == 0) 335d1b42b80SChris Wilson cycle->a_signal = &cycles[last].b_signal; 336d1b42b80SChris Wilson else 337d1b42b80SChris Wilson cycle->a_signal = &cycles[n - 1].b_signal; 338d1b42b80SChris Wilson init_completion(&cycle->b_signal); 339d1b42b80SChris Wilson 340d1b42b80SChris Wilson INIT_WORK(&cycle->work, test_cycle_work); 341d1b42b80SChris Wilson cycle->result = 0; 342d1b42b80SChris Wilson } 343d1b42b80SChris Wilson 344d1b42b80SChris Wilson for (n = 0; n < nthreads; n++) 345d1b42b80SChris Wilson queue_work(wq, &cycles[n].work); 346d1b42b80SChris Wilson 347d1b42b80SChris Wilson flush_workqueue(wq); 348d1b42b80SChris Wilson 349d1b42b80SChris Wilson ret = 0; 350d1b42b80SChris Wilson for (n = 0; n < nthreads; n++) { 351d1b42b80SChris Wilson struct test_cycle *cycle = &cycles[n]; 352d1b42b80SChris Wilson 353d1b42b80SChris Wilson if (!cycle->result) 354d1b42b80SChris Wilson continue; 355d1b42b80SChris Wilson 3560b405c65SColin Ian King pr_err("cyclic deadlock not resolved, ret[%d/%d] = %d\n", 357d1b42b80SChris Wilson n, nthreads, cycle->result); 358d1b42b80SChris Wilson ret = -EINVAL; 359d1b42b80SChris Wilson break; 360d1b42b80SChris Wilson } 361d1b42b80SChris Wilson 362d1b42b80SChris Wilson for (n = 0; n < nthreads; n++) 363d1b42b80SChris Wilson ww_mutex_destroy(&cycles[n].a_mutex); 364d1b42b80SChris Wilson kfree(cycles); 365d1b42b80SChris Wilson return ret; 366d1b42b80SChris Wilson } 367d1b42b80SChris Wilson 368d1b42b80SChris Wilson static int test_cycle(unsigned int ncpus) 369d1b42b80SChris Wilson { 370d1b42b80SChris Wilson unsigned int n; 371d1b42b80SChris Wilson int ret; 372d1b42b80SChris Wilson 373d1b42b80SChris Wilson for (n = 2; n <= ncpus + 1; n++) { 374d1b42b80SChris Wilson ret = __test_cycle(n); 375d1b42b80SChris Wilson if (ret) 376d1b42b80SChris Wilson return ret; 377d1b42b80SChris Wilson } 378d1b42b80SChris Wilson 379d1b42b80SChris Wilson return 0; 380d1b42b80SChris Wilson } 381d1b42b80SChris Wilson 3822a0c1128SChris Wilson struct stress { 3832a0c1128SChris Wilson struct work_struct work; 3842a0c1128SChris Wilson struct ww_mutex *locks; 38557dd924eSChris Wilson unsigned long timeout; 3862a0c1128SChris Wilson int nlocks; 3872a0c1128SChris Wilson }; 3882a0c1128SChris Wilson 3892a0c1128SChris Wilson static int *get_random_order(int count) 3902a0c1128SChris Wilson { 3912a0c1128SChris Wilson int *order; 3922a0c1128SChris Wilson int n, r, tmp; 3932a0c1128SChris Wilson 3940ee931c4SMichal Hocko order = kmalloc_array(count, sizeof(*order), GFP_KERNEL); 3952a0c1128SChris Wilson if (!order) 3962a0c1128SChris Wilson return order; 3972a0c1128SChris Wilson 3982a0c1128SChris Wilson for (n = 0; n < count; n++) 3992a0c1128SChris Wilson order[n] = n; 4002a0c1128SChris Wilson 4012a0c1128SChris Wilson for (n = count - 1; n > 1; n--) { 402*8032bf12SJason A. Donenfeld r = get_random_u32_below(n + 1); 4032a0c1128SChris Wilson if (r != n) { 4042a0c1128SChris Wilson tmp = order[n]; 4052a0c1128SChris Wilson order[n] = order[r]; 4062a0c1128SChris Wilson order[r] = tmp; 4072a0c1128SChris Wilson } 4082a0c1128SChris Wilson } 4092a0c1128SChris Wilson 4102a0c1128SChris Wilson return order; 4112a0c1128SChris Wilson } 4122a0c1128SChris Wilson 4132a0c1128SChris Wilson static void dummy_load(struct stress *stress) 4142a0c1128SChris Wilson { 4152a0c1128SChris Wilson usleep_range(1000, 2000); 4162a0c1128SChris Wilson } 4172a0c1128SChris Wilson 4182a0c1128SChris Wilson static void stress_inorder_work(struct work_struct *work) 4192a0c1128SChris Wilson { 4202a0c1128SChris Wilson struct stress *stress = container_of(work, typeof(*stress), work); 4212a0c1128SChris Wilson const int nlocks = stress->nlocks; 4222a0c1128SChris Wilson struct ww_mutex *locks = stress->locks; 4232a0c1128SChris Wilson struct ww_acquire_ctx ctx; 4242a0c1128SChris Wilson int *order; 4252a0c1128SChris Wilson 4262a0c1128SChris Wilson order = get_random_order(nlocks); 4272a0c1128SChris Wilson if (!order) 4282a0c1128SChris Wilson return; 4292a0c1128SChris Wilson 4302a0c1128SChris Wilson do { 4312a0c1128SChris Wilson int contended = -1; 4322a0c1128SChris Wilson int n, err; 4332a0c1128SChris Wilson 434bf7b3ac2SPeter Zijlstra ww_acquire_init(&ctx, &ww_class); 4352a0c1128SChris Wilson retry: 4362a0c1128SChris Wilson err = 0; 4372a0c1128SChris Wilson for (n = 0; n < nlocks; n++) { 4382a0c1128SChris Wilson if (n == contended) 4392a0c1128SChris Wilson continue; 4402a0c1128SChris Wilson 4412a0c1128SChris Wilson err = ww_mutex_lock(&locks[order[n]], &ctx); 4422a0c1128SChris Wilson if (err < 0) 4432a0c1128SChris Wilson break; 4442a0c1128SChris Wilson } 4452a0c1128SChris Wilson if (!err) 4462a0c1128SChris Wilson dummy_load(stress); 4472a0c1128SChris Wilson 4482a0c1128SChris Wilson if (contended > n) 4492a0c1128SChris Wilson ww_mutex_unlock(&locks[order[contended]]); 4502a0c1128SChris Wilson contended = n; 4512a0c1128SChris Wilson while (n--) 4522a0c1128SChris Wilson ww_mutex_unlock(&locks[order[n]]); 4532a0c1128SChris Wilson 4542a0c1128SChris Wilson if (err == -EDEADLK) { 4552a0c1128SChris Wilson ww_mutex_lock_slow(&locks[order[contended]], &ctx); 4562a0c1128SChris Wilson goto retry; 4572a0c1128SChris Wilson } 4582a0c1128SChris Wilson 4592a0c1128SChris Wilson if (err) { 4602a0c1128SChris Wilson pr_err_once("stress (%s) failed with %d\n", 4612a0c1128SChris Wilson __func__, err); 4622a0c1128SChris Wilson break; 4632a0c1128SChris Wilson } 4642a0c1128SChris Wilson 4652a0c1128SChris Wilson ww_acquire_fini(&ctx); 46657dd924eSChris Wilson } while (!time_after(jiffies, stress->timeout)); 4672a0c1128SChris Wilson 4682a0c1128SChris Wilson kfree(order); 4692a0c1128SChris Wilson kfree(stress); 4702a0c1128SChris Wilson } 4712a0c1128SChris Wilson 4722a0c1128SChris Wilson struct reorder_lock { 4732a0c1128SChris Wilson struct list_head link; 4742a0c1128SChris Wilson struct ww_mutex *lock; 4752a0c1128SChris Wilson }; 4762a0c1128SChris Wilson 4772a0c1128SChris Wilson static void stress_reorder_work(struct work_struct *work) 4782a0c1128SChris Wilson { 4792a0c1128SChris Wilson struct stress *stress = container_of(work, typeof(*stress), work); 4802a0c1128SChris Wilson LIST_HEAD(locks); 4812a0c1128SChris Wilson struct ww_acquire_ctx ctx; 4822a0c1128SChris Wilson struct reorder_lock *ll, *ln; 4832a0c1128SChris Wilson int *order; 4842a0c1128SChris Wilson int n, err; 4852a0c1128SChris Wilson 4862a0c1128SChris Wilson order = get_random_order(stress->nlocks); 4872a0c1128SChris Wilson if (!order) 4882a0c1128SChris Wilson return; 4892a0c1128SChris Wilson 4902a0c1128SChris Wilson for (n = 0; n < stress->nlocks; n++) { 4912a0c1128SChris Wilson ll = kmalloc(sizeof(*ll), GFP_KERNEL); 4922a0c1128SChris Wilson if (!ll) 4932a0c1128SChris Wilson goto out; 4942a0c1128SChris Wilson 4952a0c1128SChris Wilson ll->lock = &stress->locks[order[n]]; 4962a0c1128SChris Wilson list_add(&ll->link, &locks); 4972a0c1128SChris Wilson } 4982a0c1128SChris Wilson kfree(order); 4992a0c1128SChris Wilson order = NULL; 5002a0c1128SChris Wilson 501bf7b3ac2SPeter Zijlstra do { 5022a0c1128SChris Wilson ww_acquire_init(&ctx, &ww_class); 5032a0c1128SChris Wilson 5042a0c1128SChris Wilson list_for_each_entry(ll, &locks, link) { 5052a0c1128SChris Wilson err = ww_mutex_lock(ll->lock, &ctx); 5062a0c1128SChris Wilson if (!err) 5072a0c1128SChris Wilson continue; 5082a0c1128SChris Wilson 5092a0c1128SChris Wilson ln = ll; 5102a0c1128SChris Wilson list_for_each_entry_continue_reverse(ln, &locks, link) 5112a0c1128SChris Wilson ww_mutex_unlock(ln->lock); 5122a0c1128SChris Wilson 5132a0c1128SChris Wilson if (err != -EDEADLK) { 5142a0c1128SChris Wilson pr_err_once("stress (%s) failed with %d\n", 5152a0c1128SChris Wilson __func__, err); 5162a0c1128SChris Wilson break; 5172a0c1128SChris Wilson } 5182a0c1128SChris Wilson 5192a0c1128SChris Wilson ww_mutex_lock_slow(ll->lock, &ctx); 5202a0c1128SChris Wilson list_move(&ll->link, &locks); /* restarts iteration */ 5212a0c1128SChris Wilson } 5222a0c1128SChris Wilson 5232a0c1128SChris Wilson dummy_load(stress); 5242a0c1128SChris Wilson list_for_each_entry(ll, &locks, link) 5252a0c1128SChris Wilson ww_mutex_unlock(ll->lock); 5262a0c1128SChris Wilson 5272a0c1128SChris Wilson ww_acquire_fini(&ctx); 52857dd924eSChris Wilson } while (!time_after(jiffies, stress->timeout)); 5292a0c1128SChris Wilson 5302a0c1128SChris Wilson out: 5312a0c1128SChris Wilson list_for_each_entry_safe(ll, ln, &locks, link) 5322a0c1128SChris Wilson kfree(ll); 5332a0c1128SChris Wilson kfree(order); 5342a0c1128SChris Wilson kfree(stress); 5352a0c1128SChris Wilson } 5362a0c1128SChris Wilson 5372a0c1128SChris Wilson static void stress_one_work(struct work_struct *work) 5382a0c1128SChris Wilson { 5392a0c1128SChris Wilson struct stress *stress = container_of(work, typeof(*stress), work); 5402a0c1128SChris Wilson const int nlocks = stress->nlocks; 541*8032bf12SJason A. Donenfeld struct ww_mutex *lock = stress->locks + get_random_u32_below(nlocks); 5422a0c1128SChris Wilson int err; 5432a0c1128SChris Wilson 5442a0c1128SChris Wilson do { 5452a0c1128SChris Wilson err = ww_mutex_lock(lock, NULL); 5462a0c1128SChris Wilson if (!err) { 5472a0c1128SChris Wilson dummy_load(stress); 5482a0c1128SChris Wilson ww_mutex_unlock(lock); 5492a0c1128SChris Wilson } else { 5502a0c1128SChris Wilson pr_err_once("stress (%s) failed with %d\n", 5512a0c1128SChris Wilson __func__, err); 5522a0c1128SChris Wilson break; 5532a0c1128SChris Wilson } 55457dd924eSChris Wilson } while (!time_after(jiffies, stress->timeout)); 5552a0c1128SChris Wilson 5562a0c1128SChris Wilson kfree(stress); 5572a0c1128SChris Wilson } 5582a0c1128SChris Wilson 5592a0c1128SChris Wilson #define STRESS_INORDER BIT(0) 5602a0c1128SChris Wilson #define STRESS_REORDER BIT(1) 5612a0c1128SChris Wilson #define STRESS_ONE BIT(2) 5622a0c1128SChris Wilson #define STRESS_ALL (STRESS_INORDER | STRESS_REORDER | STRESS_ONE) 5632a0c1128SChris Wilson 56457dd924eSChris Wilson static int stress(int nlocks, int nthreads, unsigned int flags) 5652a0c1128SChris Wilson { 5662a0c1128SChris Wilson struct ww_mutex *locks; 5672a0c1128SChris Wilson int n; 5682a0c1128SChris Wilson 5692a0c1128SChris Wilson locks = kmalloc_array(nlocks, sizeof(*locks), GFP_KERNEL); 5702a0c1128SChris Wilson if (!locks) 5712a0c1128SChris Wilson return -ENOMEM; 5722a0c1128SChris Wilson 5732a0c1128SChris Wilson for (n = 0; n < nlocks; n++) 5742a0c1128SChris Wilson ww_mutex_init(&locks[n], &ww_class); 5752a0c1128SChris Wilson 5762a0c1128SChris Wilson for (n = 0; nthreads; n++) { 5772a0c1128SChris Wilson struct stress *stress; 5782a0c1128SChris Wilson void (*fn)(struct work_struct *work); 5792a0c1128SChris Wilson 5802a0c1128SChris Wilson fn = NULL; 5812a0c1128SChris Wilson switch (n & 3) { 5822a0c1128SChris Wilson case 0: 5832a0c1128SChris Wilson if (flags & STRESS_INORDER) 5842a0c1128SChris Wilson fn = stress_inorder_work; 5852a0c1128SChris Wilson break; 5862a0c1128SChris Wilson case 1: 5872a0c1128SChris Wilson if (flags & STRESS_REORDER) 5882a0c1128SChris Wilson fn = stress_reorder_work; 5892a0c1128SChris Wilson break; 5902a0c1128SChris Wilson case 2: 5912a0c1128SChris Wilson if (flags & STRESS_ONE) 5922a0c1128SChris Wilson fn = stress_one_work; 5932a0c1128SChris Wilson break; 5942a0c1128SChris Wilson } 5952a0c1128SChris Wilson 5962a0c1128SChris Wilson if (!fn) 5972a0c1128SChris Wilson continue; 5982a0c1128SChris Wilson 5992a0c1128SChris Wilson stress = kmalloc(sizeof(*stress), GFP_KERNEL); 6002a0c1128SChris Wilson if (!stress) 6012a0c1128SChris Wilson break; 6022a0c1128SChris Wilson 6032a0c1128SChris Wilson INIT_WORK(&stress->work, fn); 6042a0c1128SChris Wilson stress->locks = locks; 6052a0c1128SChris Wilson stress->nlocks = nlocks; 60657dd924eSChris Wilson stress->timeout = jiffies + 2*HZ; 6072a0c1128SChris Wilson 6082a0c1128SChris Wilson queue_work(wq, &stress->work); 6092a0c1128SChris Wilson nthreads--; 6102a0c1128SChris Wilson } 6112a0c1128SChris Wilson 6122a0c1128SChris Wilson flush_workqueue(wq); 6132a0c1128SChris Wilson 6142a0c1128SChris Wilson for (n = 0; n < nlocks; n++) 6152a0c1128SChris Wilson ww_mutex_destroy(&locks[n]); 6162a0c1128SChris Wilson kfree(locks); 6172a0c1128SChris Wilson 6182a0c1128SChris Wilson return 0; 6192a0c1128SChris Wilson } 6202a0c1128SChris Wilson 621f2a5fec1SChris Wilson static int __init test_ww_mutex_init(void) 622f2a5fec1SChris Wilson { 623d1b42b80SChris Wilson int ncpus = num_online_cpus(); 62412235da8SMaarten Lankhorst int ret, i; 62512235da8SMaarten Lankhorst 62612235da8SMaarten Lankhorst printk(KERN_INFO "Beginning ww mutex selftests\n"); 627f2a5fec1SChris Wilson 628d1b42b80SChris Wilson wq = alloc_workqueue("test-ww_mutex", WQ_UNBOUND, 0); 629d1b42b80SChris Wilson if (!wq) 630d1b42b80SChris Wilson return -ENOMEM; 631d1b42b80SChris Wilson 632f2a5fec1SChris Wilson ret = test_mutex(); 633f2a5fec1SChris Wilson if (ret) 634f2a5fec1SChris Wilson return ret; 635f2a5fec1SChris Wilson 63612235da8SMaarten Lankhorst ret = test_aa(false); 637c22fb380SChris Wilson if (ret) 638c22fb380SChris Wilson return ret; 639c22fb380SChris Wilson 64012235da8SMaarten Lankhorst ret = test_aa(true); 64170207686SChris Wilson if (ret) 64270207686SChris Wilson return ret; 64370207686SChris Wilson 64412235da8SMaarten Lankhorst for (i = 0; i < 4; i++) { 64512235da8SMaarten Lankhorst ret = test_abba(i & 1, i & 2); 64670207686SChris Wilson if (ret) 64770207686SChris Wilson return ret; 64812235da8SMaarten Lankhorst } 64970207686SChris Wilson 650d1b42b80SChris Wilson ret = test_cycle(ncpus); 651d1b42b80SChris Wilson if (ret) 652d1b42b80SChris Wilson return ret; 653d1b42b80SChris Wilson 65457dd924eSChris Wilson ret = stress(16, 2*ncpus, STRESS_INORDER); 6552a0c1128SChris Wilson if (ret) 6562a0c1128SChris Wilson return ret; 6572a0c1128SChris Wilson 65857dd924eSChris Wilson ret = stress(16, 2*ncpus, STRESS_REORDER); 6592a0c1128SChris Wilson if (ret) 6602a0c1128SChris Wilson return ret; 6612a0c1128SChris Wilson 66257dd924eSChris Wilson ret = stress(4095, hweight32(STRESS_ALL)*ncpus, STRESS_ALL); 6632a0c1128SChris Wilson if (ret) 6642a0c1128SChris Wilson return ret; 6652a0c1128SChris Wilson 66612235da8SMaarten Lankhorst printk(KERN_INFO "All ww mutex selftests passed\n"); 667f2a5fec1SChris Wilson return 0; 668f2a5fec1SChris Wilson } 669f2a5fec1SChris Wilson 670f2a5fec1SChris Wilson static void __exit test_ww_mutex_exit(void) 671f2a5fec1SChris Wilson { 672d1b42b80SChris Wilson destroy_workqueue(wq); 673f2a5fec1SChris Wilson } 674f2a5fec1SChris Wilson 675f2a5fec1SChris Wilson module_init(test_ww_mutex_init); 676f2a5fec1SChris Wilson module_exit(test_ww_mutex_exit); 677f2a5fec1SChris Wilson 678f2a5fec1SChris Wilson MODULE_LICENSE("GPL"); 679f2a5fec1SChris Wilson MODULE_AUTHOR("Intel Corporation"); 680