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 }
470 
471 struct reorder_lock {
472 	struct list_head link;
473 	struct ww_mutex *lock;
474 };
475 
476 static void stress_reorder_work(struct work_struct *work)
477 {
478 	struct stress *stress = container_of(work, typeof(*stress), work);
479 	LIST_HEAD(locks);
480 	struct ww_acquire_ctx ctx;
481 	struct reorder_lock *ll, *ln;
482 	int *order;
483 	int n, err;
484 
485 	order = get_random_order(stress->nlocks);
486 	if (!order)
487 		return;
488 
489 	for (n = 0; n < stress->nlocks; n++) {
490 		ll = kmalloc(sizeof(*ll), GFP_KERNEL);
491 		if (!ll)
492 			goto out;
493 
494 		ll->lock = &stress->locks[order[n]];
495 		list_add(&ll->link, &locks);
496 	}
497 	kfree(order);
498 	order = NULL;
499 
500 	do {
501 		ww_acquire_init(&ctx, &ww_class);
502 
503 		list_for_each_entry(ll, &locks, link) {
504 			err = ww_mutex_lock(ll->lock, &ctx);
505 			if (!err)
506 				continue;
507 
508 			ln = ll;
509 			list_for_each_entry_continue_reverse(ln, &locks, link)
510 				ww_mutex_unlock(ln->lock);
511 
512 			if (err != -EDEADLK) {
513 				pr_err_once("stress (%s) failed with %d\n",
514 					    __func__, err);
515 				break;
516 			}
517 
518 			ww_mutex_lock_slow(ll->lock, &ctx);
519 			list_move(&ll->link, &locks); /* restarts iteration */
520 		}
521 
522 		dummy_load(stress);
523 		list_for_each_entry(ll, &locks, link)
524 			ww_mutex_unlock(ll->lock);
525 
526 		ww_acquire_fini(&ctx);
527 	} while (!time_after(jiffies, stress->timeout));
528 
529 out:
530 	list_for_each_entry_safe(ll, ln, &locks, link)
531 		kfree(ll);
532 	kfree(order);
533 }
534 
535 static void stress_one_work(struct work_struct *work)
536 {
537 	struct stress *stress = container_of(work, typeof(*stress), work);
538 	const int nlocks = stress->nlocks;
539 	struct ww_mutex *lock = stress->locks + get_random_u32_below(nlocks);
540 	int err;
541 
542 	do {
543 		err = ww_mutex_lock(lock, NULL);
544 		if (!err) {
545 			dummy_load(stress);
546 			ww_mutex_unlock(lock);
547 		} else {
548 			pr_err_once("stress (%s) failed with %d\n",
549 				    __func__, err);
550 			break;
551 		}
552 	} while (!time_after(jiffies, stress->timeout));
553 }
554 
555 #define STRESS_INORDER BIT(0)
556 #define STRESS_REORDER BIT(1)
557 #define STRESS_ONE BIT(2)
558 #define STRESS_ALL (STRESS_INORDER | STRESS_REORDER | STRESS_ONE)
559 
560 static int stress(int nlocks, int nthreads, unsigned int flags)
561 {
562 	struct ww_mutex *locks;
563 	struct stress *stress_array;
564 	int n, count;
565 
566 	locks = kmalloc_array(nlocks, sizeof(*locks), GFP_KERNEL);
567 	if (!locks)
568 		return -ENOMEM;
569 
570 	stress_array = kmalloc_array(nthreads, sizeof(*stress_array),
571 				     GFP_KERNEL);
572 	if (!stress_array) {
573 		kfree(locks);
574 		return -ENOMEM;
575 	}
576 
577 	for (n = 0; n < nlocks; n++)
578 		ww_mutex_init(&locks[n], &ww_class);
579 
580 	count = 0;
581 	for (n = 0; nthreads; n++) {
582 		struct stress *stress;
583 		void (*fn)(struct work_struct *work);
584 
585 		fn = NULL;
586 		switch (n & 3) {
587 		case 0:
588 			if (flags & STRESS_INORDER)
589 				fn = stress_inorder_work;
590 			break;
591 		case 1:
592 			if (flags & STRESS_REORDER)
593 				fn = stress_reorder_work;
594 			break;
595 		case 2:
596 			if (flags & STRESS_ONE)
597 				fn = stress_one_work;
598 			break;
599 		}
600 
601 		if (!fn)
602 			continue;
603 
604 		stress = &stress_array[count++];
605 
606 		INIT_WORK(&stress->work, fn);
607 		stress->locks = locks;
608 		stress->nlocks = nlocks;
609 		stress->timeout = jiffies + 2*HZ;
610 
611 		queue_work(wq, &stress->work);
612 		nthreads--;
613 	}
614 
615 	flush_workqueue(wq);
616 
617 	for (n = 0; n < nlocks; n++)
618 		ww_mutex_destroy(&locks[n]);
619 	kfree(stress_array);
620 	kfree(locks);
621 
622 	return 0;
623 }
624 
625 static int __init test_ww_mutex_init(void)
626 {
627 	int ncpus = num_online_cpus();
628 	int ret, i;
629 
630 	printk(KERN_INFO "Beginning ww mutex selftests\n");
631 
632 	wq = alloc_workqueue("test-ww_mutex", WQ_UNBOUND, 0);
633 	if (!wq)
634 		return -ENOMEM;
635 
636 	ret = test_mutex();
637 	if (ret)
638 		return ret;
639 
640 	ret = test_aa(false);
641 	if (ret)
642 		return ret;
643 
644 	ret = test_aa(true);
645 	if (ret)
646 		return ret;
647 
648 	for (i = 0; i < 4; i++) {
649 		ret = test_abba(i & 1, i & 2);
650 		if (ret)
651 			return ret;
652 	}
653 
654 	ret = test_cycle(ncpus);
655 	if (ret)
656 		return ret;
657 
658 	ret = stress(16, 2*ncpus, STRESS_INORDER);
659 	if (ret)
660 		return ret;
661 
662 	ret = stress(16, 2*ncpus, STRESS_REORDER);
663 	if (ret)
664 		return ret;
665 
666 	ret = stress(2047, hweight32(STRESS_ALL)*ncpus, STRESS_ALL);
667 	if (ret)
668 		return ret;
669 
670 	printk(KERN_INFO "All ww mutex selftests passed\n");
671 	return 0;
672 }
673 
674 static void __exit test_ww_mutex_exit(void)
675 {
676 	destroy_workqueue(wq);
677 }
678 
679 module_init(test_ww_mutex_init);
680 module_exit(test_ww_mutex_exit);
681 
682 MODULE_LICENSE("GPL");
683 MODULE_AUTHOR("Intel Corporation");
684