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/random.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 	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 
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 
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 
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 
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 
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 
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 
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 static int *get_random_order(int count)
390 {
391 	int *order;
392 	int n, r, tmp;
393 
394 	order = kmalloc_array(count, sizeof(*order), GFP_KERNEL);
395 	if (!order)
396 		return order;
397 
398 	for (n = 0; n < count; n++)
399 		order[n] = n;
400 
401 	for (n = count - 1; n > 1; n--) {
402 		r = get_random_u32_below(n + 1);
403 		if (r != n) {
404 			tmp = order[n];
405 			order[n] = order[r];
406 			order[r] = tmp;
407 		}
408 	}
409 
410 	return order;
411 }
412 
413 static void dummy_load(struct stress *stress)
414 {
415 	usleep_range(1000, 2000);
416 }
417 
418 static void stress_inorder_work(struct work_struct *work)
419 {
420 	struct stress *stress = container_of(work, typeof(*stress), work);
421 	const int nlocks = stress->nlocks;
422 	struct ww_mutex *locks = stress->locks;
423 	struct ww_acquire_ctx ctx;
424 	int *order;
425 
426 	order = get_random_order(nlocks);
427 	if (!order)
428 		return;
429 
430 	do {
431 		int contended = -1;
432 		int n, err;
433 
434 		ww_acquire_init(&ctx, &ww_class);
435 retry:
436 		err = 0;
437 		for (n = 0; n < nlocks; n++) {
438 			if (n == contended)
439 				continue;
440 
441 			err = ww_mutex_lock(&locks[order[n]], &ctx);
442 			if (err < 0)
443 				break;
444 		}
445 		if (!err)
446 			dummy_load(stress);
447 
448 		if (contended > n)
449 			ww_mutex_unlock(&locks[order[contended]]);
450 		contended = n;
451 		while (n--)
452 			ww_mutex_unlock(&locks[order[n]]);
453 
454 		if (err == -EDEADLK) {
455 			ww_mutex_lock_slow(&locks[order[contended]], &ctx);
456 			goto retry;
457 		}
458 
459 		if (err) {
460 			pr_err_once("stress (%s) failed with %d\n",
461 				    __func__, err);
462 			break;
463 		}
464 
465 		ww_acquire_fini(&ctx);
466 	} while (!time_after(jiffies, stress->timeout));
467 
468 	kfree(order);
469 	kfree(stress);
470 }
471 
472 struct reorder_lock {
473 	struct list_head link;
474 	struct ww_mutex *lock;
475 };
476 
477 static void stress_reorder_work(struct work_struct *work)
478 {
479 	struct stress *stress = container_of(work, typeof(*stress), work);
480 	LIST_HEAD(locks);
481 	struct ww_acquire_ctx ctx;
482 	struct reorder_lock *ll, *ln;
483 	int *order;
484 	int n, err;
485 
486 	order = get_random_order(stress->nlocks);
487 	if (!order)
488 		return;
489 
490 	for (n = 0; n < stress->nlocks; n++) {
491 		ll = kmalloc(sizeof(*ll), GFP_KERNEL);
492 		if (!ll)
493 			goto out;
494 
495 		ll->lock = &stress->locks[order[n]];
496 		list_add(&ll->link, &locks);
497 	}
498 	kfree(order);
499 	order = NULL;
500 
501 	do {
502 		ww_acquire_init(&ctx, &ww_class);
503 
504 		list_for_each_entry(ll, &locks, link) {
505 			err = ww_mutex_lock(ll->lock, &ctx);
506 			if (!err)
507 				continue;
508 
509 			ln = ll;
510 			list_for_each_entry_continue_reverse(ln, &locks, link)
511 				ww_mutex_unlock(ln->lock);
512 
513 			if (err != -EDEADLK) {
514 				pr_err_once("stress (%s) failed with %d\n",
515 					    __func__, err);
516 				break;
517 			}
518 
519 			ww_mutex_lock_slow(ll->lock, &ctx);
520 			list_move(&ll->link, &locks); /* restarts iteration */
521 		}
522 
523 		dummy_load(stress);
524 		list_for_each_entry(ll, &locks, link)
525 			ww_mutex_unlock(ll->lock);
526 
527 		ww_acquire_fini(&ctx);
528 	} while (!time_after(jiffies, stress->timeout));
529 
530 out:
531 	list_for_each_entry_safe(ll, ln, &locks, link)
532 		kfree(ll);
533 	kfree(order);
534 	kfree(stress);
535 }
536 
537 static void stress_one_work(struct work_struct *work)
538 {
539 	struct stress *stress = container_of(work, typeof(*stress), work);
540 	const int nlocks = stress->nlocks;
541 	struct ww_mutex *lock = stress->locks + get_random_u32_below(nlocks);
542 	int err;
543 
544 	do {
545 		err = ww_mutex_lock(lock, NULL);
546 		if (!err) {
547 			dummy_load(stress);
548 			ww_mutex_unlock(lock);
549 		} else {
550 			pr_err_once("stress (%s) failed with %d\n",
551 				    __func__, err);
552 			break;
553 		}
554 	} while (!time_after(jiffies, stress->timeout));
555 
556 	kfree(stress);
557 }
558 
559 #define STRESS_INORDER BIT(0)
560 #define STRESS_REORDER BIT(1)
561 #define STRESS_ONE BIT(2)
562 #define STRESS_ALL (STRESS_INORDER | STRESS_REORDER | STRESS_ONE)
563 
564 static int stress(int nlocks, int nthreads, unsigned int flags)
565 {
566 	struct ww_mutex *locks;
567 	int n;
568 
569 	locks = kmalloc_array(nlocks, sizeof(*locks), GFP_KERNEL);
570 	if (!locks)
571 		return -ENOMEM;
572 
573 	for (n = 0; n < nlocks; n++)
574 		ww_mutex_init(&locks[n], &ww_class);
575 
576 	for (n = 0; nthreads; n++) {
577 		struct stress *stress;
578 		void (*fn)(struct work_struct *work);
579 
580 		fn = NULL;
581 		switch (n & 3) {
582 		case 0:
583 			if (flags & STRESS_INORDER)
584 				fn = stress_inorder_work;
585 			break;
586 		case 1:
587 			if (flags & STRESS_REORDER)
588 				fn = stress_reorder_work;
589 			break;
590 		case 2:
591 			if (flags & STRESS_ONE)
592 				fn = stress_one_work;
593 			break;
594 		}
595 
596 		if (!fn)
597 			continue;
598 
599 		stress = kmalloc(sizeof(*stress), GFP_KERNEL);
600 		if (!stress)
601 			break;
602 
603 		INIT_WORK(&stress->work, fn);
604 		stress->locks = locks;
605 		stress->nlocks = nlocks;
606 		stress->timeout = jiffies + 2*HZ;
607 
608 		queue_work(wq, &stress->work);
609 		nthreads--;
610 	}
611 
612 	flush_workqueue(wq);
613 
614 	for (n = 0; n < nlocks; n++)
615 		ww_mutex_destroy(&locks[n]);
616 	kfree(locks);
617 
618 	return 0;
619 }
620 
621 static int __init test_ww_mutex_init(void)
622 {
623 	int ncpus = num_online_cpus();
624 	int ret, i;
625 
626 	printk(KERN_INFO "Beginning ww mutex selftests\n");
627 
628 	wq = alloc_workqueue("test-ww_mutex", WQ_UNBOUND, 0);
629 	if (!wq)
630 		return -ENOMEM;
631 
632 	ret = test_mutex();
633 	if (ret)
634 		return ret;
635 
636 	ret = test_aa(false);
637 	if (ret)
638 		return ret;
639 
640 	ret = test_aa(true);
641 	if (ret)
642 		return ret;
643 
644 	for (i = 0; i < 4; i++) {
645 		ret = test_abba(i & 1, i & 2);
646 		if (ret)
647 			return ret;
648 	}
649 
650 	ret = test_cycle(ncpus);
651 	if (ret)
652 		return ret;
653 
654 	ret = stress(16, 2*ncpus, STRESS_INORDER);
655 	if (ret)
656 		return ret;
657 
658 	ret = stress(16, 2*ncpus, STRESS_REORDER);
659 	if (ret)
660 		return ret;
661 
662 	ret = stress(2047, hweight32(STRESS_ALL)*ncpus, STRESS_ALL);
663 	if (ret)
664 		return ret;
665 
666 	printk(KERN_INFO "All ww mutex selftests passed\n");
667 	return 0;
668 }
669 
670 static void __exit test_ww_mutex_exit(void)
671 {
672 	destroy_workqueue(wq);
673 }
674 
675 module_init(test_ww_mutex_init);
676 module_exit(test_ww_mutex_exit);
677 
678 MODULE_LICENSE("GPL");
679 MODULE_AUTHOR("Intel Corporation");
680