2 * Module-based API test facility for ww_mutexes
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.
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.
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.
19 #include <linux/kernel.h>
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>
29 static DEFINE_WD_CLASS(ww_class);
30 struct workqueue_struct *wq;
33 struct work_struct work;
34 struct ww_mutex mutex;
35 struct completion ready, go, done;
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)
44 static void test_mutex_work(struct work_struct *work)
46 struct test_mutex *mtx = container_of(work, typeof(*mtx), work);
48 complete(&mtx->ready);
49 wait_for_completion(&mtx->go);
51 if (mtx->flags & TEST_MTX_TRY) {
52 while (!ww_mutex_trylock(&mtx->mutex))
55 ww_mutex_lock(&mtx->mutex, NULL);
58 ww_mutex_unlock(&mtx->mutex);
61 static int __test_mutex(unsigned int flags)
63 #define TIMEOUT (HZ / 16)
64 struct test_mutex mtx;
65 struct ww_acquire_ctx ctx;
68 ww_mutex_init(&mtx.mutex, &ww_class);
69 ww_acquire_init(&ctx, &ww_class);
71 INIT_WORK_ONSTACK(&mtx.work, test_mutex_work);
72 init_completion(&mtx.ready);
73 init_completion(&mtx.go);
74 init_completion(&mtx.done);
77 schedule_work(&mtx.work);
79 wait_for_completion(&mtx.ready);
80 ww_mutex_lock(&mtx.mutex, (flags & TEST_MTX_CTX) ? &ctx : NULL);
82 if (flags & TEST_MTX_SPIN) {
83 unsigned long timeout = jiffies + TIMEOUT;
87 if (completion_done(&mtx.done)) {
92 } while (time_before(jiffies, timeout));
94 ret = wait_for_completion_timeout(&mtx.done, TIMEOUT);
96 ww_mutex_unlock(&mtx.mutex);
97 ww_acquire_fini(&ctx);
100 pr_err("%s(flags=%x): mutual exclusion failure\n",
105 flush_work(&mtx.work);
106 destroy_work_on_stack(&mtx.work);
111 static int test_mutex(void)
116 for (i = 0; i < __TEST_MTX_LAST; i++) {
117 ret = __test_mutex(i);
125 static int test_aa(void)
127 struct ww_mutex mutex;
128 struct ww_acquire_ctx ctx;
131 ww_mutex_init(&mutex, &ww_class);
132 ww_acquire_init(&ctx, &ww_class);
134 ww_mutex_lock(&mutex, &ctx);
136 if (ww_mutex_trylock(&mutex)) {
137 pr_err("%s: trylocked itself!\n", __func__);
138 ww_mutex_unlock(&mutex);
143 ret = ww_mutex_lock(&mutex, &ctx);
144 if (ret != -EALREADY) {
145 pr_err("%s: missed deadlock for recursing, ret=%d\n",
148 ww_mutex_unlock(&mutex);
155 ww_mutex_unlock(&mutex);
156 ww_acquire_fini(&ctx);
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;
170 static void test_abba_work(struct work_struct *work)
172 struct test_abba *abba = container_of(work, typeof(*abba), work);
173 struct ww_acquire_ctx ctx;
176 ww_acquire_init(&ctx, &ww_class);
177 ww_mutex_lock(&abba->b_mutex, &ctx);
179 complete(&abba->b_ready);
180 wait_for_completion(&abba->a_ready);
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);
190 ww_mutex_unlock(&abba->a_mutex);
191 ww_mutex_unlock(&abba->b_mutex);
192 ww_acquire_fini(&ctx);
197 static int test_abba(bool resolve)
199 struct test_abba abba;
200 struct ww_acquire_ctx ctx;
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;
210 schedule_work(&abba.work);
212 ww_acquire_init(&ctx, &ww_class);
213 ww_mutex_lock(&abba.a_mutex, &ctx);
215 complete(&abba.a_ready);
216 wait_for_completion(&abba.b_ready);
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);
226 ww_mutex_unlock(&abba.b_mutex);
227 ww_mutex_unlock(&abba.a_mutex);
228 ww_acquire_fini(&ctx);
230 flush_work(&abba.work);
231 destroy_work_on_stack(&abba.work);
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);
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);
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;
259 static void test_cycle_work(struct work_struct *work)
261 struct test_cycle *cycle = container_of(work, typeof(*cycle), work);
262 struct ww_acquire_ctx ctx;
265 ww_acquire_init(&ctx, &ww_class);
266 ww_mutex_lock(&cycle->a_mutex, &ctx);
268 complete(cycle->a_signal);
269 wait_for_completion(&cycle->b_signal);
271 err = ww_mutex_lock(cycle->b_mutex, &ctx);
272 if (err == -EDEADLK) {
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);
280 ww_mutex_unlock(cycle->b_mutex);
282 ww_mutex_unlock(&cycle->a_mutex);
283 ww_acquire_fini(&ctx);
285 cycle->result = err ?: erra;
288 static int __test_cycle(unsigned int nthreads)
290 struct test_cycle *cycles;
291 unsigned int n, last = nthreads - 1;
294 cycles = kmalloc_array(nthreads, sizeof(*cycles), GFP_KERNEL);
298 for (n = 0; n < nthreads; n++) {
299 struct test_cycle *cycle = &cycles[n];
301 ww_mutex_init(&cycle->a_mutex, &ww_class);
303 cycle->b_mutex = &cycles[0].a_mutex;
305 cycle->b_mutex = &cycles[n + 1].a_mutex;
308 cycle->a_signal = &cycles[last].b_signal;
310 cycle->a_signal = &cycles[n - 1].b_signal;
311 init_completion(&cycle->b_signal);
313 INIT_WORK(&cycle->work, test_cycle_work);
317 for (n = 0; n < nthreads; n++)
318 queue_work(wq, &cycles[n].work);
323 for (n = 0; n < nthreads; n++) {
324 struct test_cycle *cycle = &cycles[n];
329 pr_err("cyclic deadlock not resolved, ret[%d/%d] = %d\n",
330 n, nthreads, cycle->result);
335 for (n = 0; n < nthreads; n++)
336 ww_mutex_destroy(&cycles[n].a_mutex);
341 static int test_cycle(unsigned int ncpus)
346 for (n = 2; n <= ncpus + 1; n++) {
347 ret = __test_cycle(n);
356 struct work_struct work;
357 struct ww_mutex *locks;
358 unsigned long timeout;
362 static int *get_random_order(int count)
367 order = kmalloc_array(count, sizeof(*order), GFP_KERNEL);
371 for (n = 0; n < count; n++)
374 for (n = count - 1; n > 1; n--) {
375 r = get_random_int() % (n + 1);
386 static void dummy_load(struct stress *stress)
388 usleep_range(1000, 2000);
391 static void stress_inorder_work(struct work_struct *work)
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;
399 order = get_random_order(nlocks);
407 ww_acquire_init(&ctx, &ww_class);
410 for (n = 0; n < nlocks; n++) {
414 err = ww_mutex_lock(&locks[order[n]], &ctx);
422 ww_mutex_unlock(&locks[order[contended]]);
425 ww_mutex_unlock(&locks[order[n]]);
427 if (err == -EDEADLK) {
428 ww_mutex_lock_slow(&locks[order[contended]], &ctx);
433 pr_err_once("stress (%s) failed with %d\n",
438 ww_acquire_fini(&ctx);
439 } while (!time_after(jiffies, stress->timeout));
445 struct reorder_lock {
446 struct list_head link;
447 struct ww_mutex *lock;
450 static void stress_reorder_work(struct work_struct *work)
452 struct stress *stress = container_of(work, typeof(*stress), work);
454 struct ww_acquire_ctx ctx;
455 struct reorder_lock *ll, *ln;
459 order = get_random_order(stress->nlocks);
463 for (n = 0; n < stress->nlocks; n++) {
464 ll = kmalloc(sizeof(*ll), GFP_KERNEL);
468 ll->lock = &stress->locks[order[n]];
469 list_add(&ll->link, &locks);
475 ww_acquire_init(&ctx, &ww_class);
477 list_for_each_entry(ll, &locks, link) {
478 err = ww_mutex_lock(ll->lock, &ctx);
483 list_for_each_entry_continue_reverse(ln, &locks, link)
484 ww_mutex_unlock(ln->lock);
486 if (err != -EDEADLK) {
487 pr_err_once("stress (%s) failed with %d\n",
492 ww_mutex_lock_slow(ll->lock, &ctx);
493 list_move(&ll->link, &locks); /* restarts iteration */
497 list_for_each_entry(ll, &locks, link)
498 ww_mutex_unlock(ll->lock);
500 ww_acquire_fini(&ctx);
501 } while (!time_after(jiffies, stress->timeout));
504 list_for_each_entry_safe(ll, ln, &locks, link)
510 static void stress_one_work(struct work_struct *work)
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);
518 err = ww_mutex_lock(lock, NULL);
521 ww_mutex_unlock(lock);
523 pr_err_once("stress (%s) failed with %d\n",
527 } while (!time_after(jiffies, stress->timeout));
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)
537 static int stress(int nlocks, int nthreads, unsigned int flags)
539 struct ww_mutex *locks;
542 locks = kmalloc_array(nlocks, sizeof(*locks), GFP_KERNEL);
546 for (n = 0; n < nlocks; n++)
547 ww_mutex_init(&locks[n], &ww_class);
549 for (n = 0; nthreads; n++) {
550 struct stress *stress;
551 void (*fn)(struct work_struct *work);
556 if (flags & STRESS_INORDER)
557 fn = stress_inorder_work;
560 if (flags & STRESS_REORDER)
561 fn = stress_reorder_work;
564 if (flags & STRESS_ONE)
565 fn = stress_one_work;
572 stress = kmalloc(sizeof(*stress), GFP_KERNEL);
576 INIT_WORK(&stress->work, fn);
577 stress->locks = locks;
578 stress->nlocks = nlocks;
579 stress->timeout = jiffies + 2*HZ;
581 queue_work(wq, &stress->work);
587 for (n = 0; n < nlocks; n++)
588 ww_mutex_destroy(&locks[n]);
594 static int __init test_ww_mutex_init(void)
596 int ncpus = num_online_cpus();
599 wq = alloc_workqueue("test-ww_mutex", WQ_UNBOUND, 0);
611 ret = test_abba(false);
615 ret = test_abba(true);
619 ret = test_cycle(ncpus);
623 ret = stress(16, 2*ncpus, STRESS_INORDER);
627 ret = stress(16, 2*ncpus, STRESS_REORDER);
631 ret = stress(4095, hweight32(STRESS_ALL)*ncpus, STRESS_ALL);
638 static void __exit test_ww_mutex_exit(void)
640 destroy_workqueue(wq);
643 module_init(test_ww_mutex_init);
644 module_exit(test_ww_mutex_exit);
646 MODULE_LICENSE("GPL");
647 MODULE_AUTHOR("Intel Corporation");