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