[thirdparty/kernel/stable.git] / kernel / locking / test-ww_mutex.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Module-based API test facility for ww_mutexes
 */

#include <linux/kernel.h>

#include <linux/completion.h>
#include <linux/delay.h>
#include <linux/kthread.h>
#include <linux/module.h>
#include <linux/random.h>
#include <linux/slab.h>
#include <linux/ww_mutex.h>

static DEFINE_WD_CLASS(ww_class);
struct workqueue_struct *wq;

struct test_mutex {
	struct work_struct work;
	struct ww_mutex mutex;
	struct completion ready, go, done;
	unsigned int flags;
};

#define TEST_MTX_SPIN BIT(0)
#define TEST_MTX_TRY BIT(1)
#define TEST_MTX_CTX BIT(2)
#define __TEST_MTX_LAST BIT(3)

static void test_mutex_work(struct work_struct *work)
{
	struct test_mutex *mtx = container_of(work, typeof(*mtx), work);

	complete(&mtx->ready);
	wait_for_completion(&mtx->go);

	if (mtx->flags & TEST_MTX_TRY) {
		while (!ww_mutex_trylock(&mtx->mutex))
			cond_resched();
	} else {
		ww_mutex_lock(&mtx->mutex, NULL);
	}
	complete(&mtx->done);
	ww_mutex_unlock(&mtx->mutex);
}

static int __test_mutex(unsigned int flags)
{
#define TIMEOUT (HZ / 16)
	struct test_mutex mtx;
	struct ww_acquire_ctx ctx;
	int ret;

	ww_mutex_init(&mtx.mutex, &ww_class);
	ww_acquire_init(&ctx, &ww_class);

	INIT_WORK_ONSTACK(&mtx.work, test_mutex_work);
	init_completion(&mtx.ready);
	init_completion(&mtx.go);
	init_completion(&mtx.done);
	mtx.flags = flags;

	schedule_work(&mtx.work);

	wait_for_completion(&mtx.ready);
	ww_mutex_lock(&mtx.mutex, (flags & TEST_MTX_CTX) ? &ctx : NULL);
	complete(&mtx.go);
	if (flags & TEST_MTX_SPIN) {
		unsigned long timeout = jiffies + TIMEOUT;

		ret = 0;
		do {
			if (completion_done(&mtx.done)) {
				ret = -EINVAL;
				break;
			}
			cond_resched();
		} while (time_before(jiffies, timeout));
	} else {
		ret = wait_for_completion_timeout(&mtx.done, TIMEOUT);
	}
	ww_mutex_unlock(&mtx.mutex);
	ww_acquire_fini(&ctx);

	if (ret) {
		pr_err("%s(flags=%x): mutual exclusion failure\n",
		       __func__, flags);
		ret = -EINVAL;
	}

	flush_work(&mtx.work);
	destroy_work_on_stack(&mtx.work);
	return ret;
#undef TIMEOUT
}

static int test_mutex(void)
{
	int ret;
	int i;

	for (i = 0; i < __TEST_MTX_LAST; i++) {
		ret = __test_mutex(i);
		if (ret)
			return ret;
	}

	return 0;
}

static int test_aa(void)
{
	struct ww_mutex mutex;
	struct ww_acquire_ctx ctx;
	int ret;

	ww_mutex_init(&mutex, &ww_class);
	ww_acquire_init(&ctx, &ww_class);

	ww_mutex_lock(&mutex, &ctx);

	if (ww_mutex_trylock(&mutex))  {
		pr_err("%s: trylocked itself!\n", __func__);
		ww_mutex_unlock(&mutex);
		ret = -EINVAL;
		goto out;
	}

	ret = ww_mutex_lock(&mutex, &ctx);
	if (ret != -EALREADY) {
		pr_err("%s: missed deadlock for recursing, ret=%d\n",
		       __func__, ret);
		if (!ret)
			ww_mutex_unlock(&mutex);
		ret = -EINVAL;
		goto out;
	}

	ret = 0;
out:
	ww_mutex_unlock(&mutex);
	ww_acquire_fini(&ctx);
	return ret;
}

struct test_abba {
	struct work_struct work;
	struct ww_mutex a_mutex;
	struct ww_mutex b_mutex;
	struct completion a_ready;
	struct completion b_ready;
	bool resolve;
	int result;
};

static void test_abba_work(struct work_struct *work)
{
	struct test_abba *abba = container_of(work, typeof(*abba), work);
	struct ww_acquire_ctx ctx;
	int err;

	ww_acquire_init(&ctx, &ww_class);
	ww_mutex_lock(&abba->b_mutex, &ctx);

	complete(&abba->b_ready);
	wait_for_completion(&abba->a_ready);

	err = ww_mutex_lock(&abba->a_mutex, &ctx);
	if (abba->resolve && err == -EDEADLK) {
		ww_mutex_unlock(&abba->b_mutex);
		ww_mutex_lock_slow(&abba->a_mutex, &ctx);
		err = ww_mutex_lock(&abba->b_mutex, &ctx);
	}

	if (!err)
		ww_mutex_unlock(&abba->a_mutex);
	ww_mutex_unlock(&abba->b_mutex);
	ww_acquire_fini(&ctx);

	abba->result = err;
}

static int test_abba(bool resolve)
{
	struct test_abba abba;
	struct ww_acquire_ctx ctx;
	int err, ret;

	ww_mutex_init(&abba.a_mutex, &ww_class);
	ww_mutex_init(&abba.b_mutex, &ww_class);
	INIT_WORK_ONSTACK(&abba.work, test_abba_work);
	init_completion(&abba.a_ready);
	init_completion(&abba.b_ready);
	abba.resolve = resolve;

	schedule_work(&abba.work);

	ww_acquire_init(&ctx, &ww_class);
	ww_mutex_lock(&abba.a_mutex, &ctx);

	complete(&abba.a_ready);
	wait_for_completion(&abba.b_ready);

	err = ww_mutex_lock(&abba.b_mutex, &ctx);
	if (resolve && err == -EDEADLK) {
		ww_mutex_unlock(&abba.a_mutex);
		ww_mutex_lock_slow(&abba.b_mutex, &ctx);
		err = ww_mutex_lock(&abba.a_mutex, &ctx);
	}

	if (!err)
		ww_mutex_unlock(&abba.b_mutex);
	ww_mutex_unlock(&abba.a_mutex);
	ww_acquire_fini(&ctx);

	flush_work(&abba.work);
	destroy_work_on_stack(&abba.work);

	ret = 0;
	if (resolve) {
		if (err || abba.result) {
			pr_err("%s: failed to resolve ABBA deadlock, A err=%d, B err=%d\n",
			       __func__, err, abba.result);
			ret = -EINVAL;
		}
	} else {
		if (err != -EDEADLK && abba.result != -EDEADLK) {
			pr_err("%s: missed ABBA deadlock, A err=%d, B err=%d\n",
			       __func__, err, abba.result);
			ret = -EINVAL;
		}
	}
	return ret;
}

struct test_cycle {
	struct work_struct work;
	struct ww_mutex a_mutex;
	struct ww_mutex *b_mutex;
	struct completion *a_signal;
	struct completion b_signal;
	int result;
};

static void test_cycle_work(struct work_struct *work)
{
	struct test_cycle *cycle = container_of(work, typeof(*cycle), work);
	struct ww_acquire_ctx ctx;
	int err, erra = 0;

	ww_acquire_init(&ctx, &ww_class);
	ww_mutex_lock(&cycle->a_mutex, &ctx);

	complete(cycle->a_signal);
	wait_for_completion(&cycle->b_signal);

	err = ww_mutex_lock(cycle->b_mutex, &ctx);
	if (err == -EDEADLK) {
		err = 0;
		ww_mutex_unlock(&cycle->a_mutex);
		ww_mutex_lock_slow(cycle->b_mutex, &ctx);
		erra = ww_mutex_lock(&cycle->a_mutex, &ctx);
	}

	if (!err)
		ww_mutex_unlock(cycle->b_mutex);
	if (!erra)
		ww_mutex_unlock(&cycle->a_mutex);
	ww_acquire_fini(&ctx);

	cycle->result = err ?: erra;
}

static int __test_cycle(unsigned int nthreads)
{
	struct test_cycle *cycles;
	unsigned int n, last = nthreads - 1;
	int ret;

	cycles = kmalloc_array(nthreads, sizeof(*cycles), GFP_KERNEL);
	if (!cycles)
		return -ENOMEM;

	for (n = 0; n < nthreads; n++) {
		struct test_cycle *cycle = &cycles[n];

		ww_mutex_init(&cycle->a_mutex, &ww_class);
		if (n == last)
			cycle->b_mutex = &cycles[0].a_mutex;
		else
			cycle->b_mutex = &cycles[n + 1].a_mutex;

		if (n == 0)
			cycle->a_signal = &cycles[last].b_signal;
		else
			cycle->a_signal = &cycles[n - 1].b_signal;
		init_completion(&cycle->b_signal);

		INIT_WORK(&cycle->work, test_cycle_work);
		cycle->result = 0;
	}

	for (n = 0; n < nthreads; n++)
		queue_work(wq, &cycles[n].work);

	flush_workqueue(wq);

	ret = 0;
	for (n = 0; n < nthreads; n++) {
		struct test_cycle *cycle = &cycles[n];

		if (!cycle->result)
			continue;

		pr_err("cyclic deadlock not resolved, ret[%d/%d] = %d\n",
		       n, nthreads, cycle->result);
		ret = -EINVAL;
		break;
	}

	for (n = 0; n < nthreads; n++)
		ww_mutex_destroy(&cycles[n].a_mutex);
	kfree(cycles);
	return ret;
}

static int test_cycle(unsigned int ncpus)
{
	unsigned int n;
	int ret;

	for (n = 2; n <= ncpus + 1; n++) {
		ret = __test_cycle(n);
		if (ret)
			return ret;
	}

	return 0;
}

struct stress {
	struct work_struct work;
	struct ww_mutex *locks;
	unsigned long timeout;
	int nlocks;
};

static int *get_random_order(int count)
{
	int *order;
	int n, r, tmp;

	order = kmalloc_array(count, sizeof(*order), GFP_KERNEL);
	if (!order)
		return order;

	for (n = 0; n < count; n++)
		order[n] = n;

	for (n = count - 1; n > 1; n--) {
		r = get_random_int() % (n + 1);
		if (r != n) {
			tmp = order[n];
			order[n] = order[r];
			order[r] = tmp;
		}
	}

	return order;
}

static void dummy_load(struct stress *stress)
{
	usleep_range(1000, 2000);
}

static void stress_inorder_work(struct work_struct *work)
{
	struct stress *stress = container_of(work, typeof(*stress), work);
	const int nlocks = stress->nlocks;
	struct ww_mutex *locks = stress->locks;
	struct ww_acquire_ctx ctx;
	int *order;

	order = get_random_order(nlocks);
	if (!order)
		return;

	do {
		int contended = -1;
		int n, err;

		ww_acquire_init(&ctx, &ww_class);
retry:
		err = 0;
		for (n = 0; n < nlocks; n++) {
			if (n == contended)
				continue;

			err = ww_mutex_lock(&locks[order[n]], &ctx);
			if (err < 0)
				break;
		}
		if (!err)
			dummy_load(stress);

		if (contended > n)
			ww_mutex_unlock(&locks[order[contended]]);
		contended = n;
		while (n--)
			ww_mutex_unlock(&locks[order[n]]);

		if (err == -EDEADLK) {
			ww_mutex_lock_slow(&locks[order[contended]], &ctx);
			goto retry;
		}

		if (err) {
			pr_err_once("stress (%s) failed with %d\n",
				    __func__, err);
			break;
		}

		ww_acquire_fini(&ctx);
	} while (!time_after(jiffies, stress->timeout));

	kfree(order);
	kfree(stress);
}

struct reorder_lock {
	struct list_head link;
	struct ww_mutex *lock;
};

static void stress_reorder_work(struct work_struct *work)
{
	struct stress *stress = container_of(work, typeof(*stress), work);
	LIST_HEAD(locks);
	struct ww_acquire_ctx ctx;
	struct reorder_lock *ll, *ln;
	int *order;
	int n, err;

	order = get_random_order(stress->nlocks);
	if (!order)
		return;

	for (n = 0; n < stress->nlocks; n++) {
		ll = kmalloc(sizeof(*ll), GFP_KERNEL);
		if (!ll)
			goto out;

		ll->lock = &stress->locks[order[n]];
		list_add(&ll->link, &locks);
	}
	kfree(order);
	order = NULL;

	do {
		ww_acquire_init(&ctx, &ww_class);

		list_for_each_entry(ll, &locks, link) {
			err = ww_mutex_lock(ll->lock, &ctx);
			if (!err)
				continue;

			ln = ll;
			list_for_each_entry_continue_reverse(ln, &locks, link)
				ww_mutex_unlock(ln->lock);

			if (err != -EDEADLK) {
				pr_err_once("stress (%s) failed with %d\n",
					    __func__, err);
				break;
			}

			ww_mutex_lock_slow(ll->lock, &ctx);
			list_move(&ll->link, &locks); /* restarts iteration */
		}

		dummy_load(stress);
		list_for_each_entry(ll, &locks, link)
			ww_mutex_unlock(ll->lock);

		ww_acquire_fini(&ctx);
	} while (!time_after(jiffies, stress->timeout));

out:
	list_for_each_entry_safe(ll, ln, &locks, link)
		kfree(ll);
	kfree(order);
	kfree(stress);
}

static void stress_one_work(struct work_struct *work)
{
	struct stress *stress = container_of(work, typeof(*stress), work);
	const int nlocks = stress->nlocks;
	struct ww_mutex *lock = stress->locks + (get_random_int() % nlocks);
	int err;

	do {
		err = ww_mutex_lock(lock, NULL);
		if (!err) {
			dummy_load(stress);
			ww_mutex_unlock(lock);
		} else {
			pr_err_once("stress (%s) failed with %d\n",
				    __func__, err);
			break;
		}
	} while (!time_after(jiffies, stress->timeout));

	kfree(stress);
}

#define STRESS_INORDER BIT(0)
#define STRESS_REORDER BIT(1)
#define STRESS_ONE BIT(2)
#define STRESS_ALL (STRESS_INORDER | STRESS_REORDER | STRESS_ONE)

static int stress(int nlocks, int nthreads, unsigned int flags)
{
	struct ww_mutex *locks;
	int n;

	locks = kmalloc_array(nlocks, sizeof(*locks), GFP_KERNEL);
	if (!locks)
		return -ENOMEM;

	for (n = 0; n < nlocks; n++)
		ww_mutex_init(&locks[n], &ww_class);

	for (n = 0; nthreads; n++) {
		struct stress *stress;
		void (*fn)(struct work_struct *work);

		fn = NULL;
		switch (n & 3) {
		case 0:
			if (flags & STRESS_INORDER)
				fn = stress_inorder_work;
			break;
		case 1:
			if (flags & STRESS_REORDER)
				fn = stress_reorder_work;
			break;
		case 2:
			if (flags & STRESS_ONE)
				fn = stress_one_work;
			break;
		}

		if (!fn)
			continue;

		stress = kmalloc(sizeof(*stress), GFP_KERNEL);
		if (!stress)
			break;

		INIT_WORK(&stress->work, fn);
		stress->locks = locks;
		stress->nlocks = nlocks;
		stress->timeout = jiffies + 2*HZ;

		queue_work(wq, &stress->work);
		nthreads--;
	}

	flush_workqueue(wq);

	for (n = 0; n < nlocks; n++)
		ww_mutex_destroy(&locks[n]);
	kfree(locks);

	return 0;
}

static int __init test_ww_mutex_init(void)
{
	int ncpus = num_online_cpus();
	int ret;

	wq = alloc_workqueue("test-ww_mutex", WQ_UNBOUND, 0);
	if (!wq)
		return -ENOMEM;

	ret = test_mutex();
	if (ret)
		return ret;

	ret = test_aa();
	if (ret)
		return ret;

	ret = test_abba(false);
	if (ret)
		return ret;

	ret = test_abba(true);
	if (ret)
		return ret;

	ret = test_cycle(ncpus);
	if (ret)
		return ret;

	ret = stress(16, 2*ncpus, STRESS_INORDER);
	if (ret)
		return ret;

	ret = stress(16, 2*ncpus, STRESS_REORDER);
	if (ret)
		return ret;

	ret = stress(4095, hweight32(STRESS_ALL)*ncpus, STRESS_ALL);
	if (ret)
		return ret;

	return 0;
}

static void __exit test_ww_mutex_exit(void)
{
	destroy_workqueue(wq);
}

module_init(test_ww_mutex_init);
module_exit(test_ww_mutex_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Intel Corporation");
Commit	Line	Data
d6cd1e9b	1	// SPDX-License-Identifier: GPL-2.0-or-later
f2a5fec1 CW	2	/*
f2a5fec1 CW	3	* Module-based API test facility for ww_mutexes
f2a5fec1 CW	4	*/
	5
	6	#include <linux/kernel.h>
	7
	8	#include <linux/completion.h>
2a0c1128	9	#include <linux/delay.h>
f2a5fec1 CW	10	#include <linux/kthread.h>
f2a5fec1 CW	11	#include <linux/module.h>
2a0c1128	12	#include <linux/random.h>
d1b42b80	13	#include <linux/slab.h>
f2a5fec1 CW	14	#include <linux/ww_mutex.h>
f2a5fec1 CW	15
08295b3b	16	static DEFINE_WD_CLASS(ww_class);
d1b42b80	17	struct workqueue_struct *wq;
f2a5fec1 CW	18
	19	struct test_mutex {
	20	struct work_struct work;
	21	struct ww_mutex mutex;
	22	struct completion ready, go, done;
	23	unsigned int flags;
	24	};
	25
	26	#define TEST_MTX_SPIN BIT(0)
	27	#define TEST_MTX_TRY BIT(1)
	28	#define TEST_MTX_CTX BIT(2)
	29	#define __TEST_MTX_LAST BIT(3)
	30
	31	static void test_mutex_work(struct work_struct *work)
	32	{
	33	struct test_mutex mtx = container_of(work, typeof(mtx), work);
	34
	35	complete(&mtx->ready);
	36	wait_for_completion(&mtx->go);
	37
	38	if (mtx->flags & TEST_MTX_TRY) {
	39	while (!ww_mutex_trylock(&mtx->mutex))
2b232e0c	40	cond_resched();
f2a5fec1 CW	41	} else {
	42	ww_mutex_lock(&mtx->mutex, NULL);
	43	}
	44	complete(&mtx->done);
	45	ww_mutex_unlock(&mtx->mutex);
	46	}
	47
	48	static int __test_mutex(unsigned int flags)
	49	{
	50	#define TIMEOUT (HZ / 16)
	51	struct test_mutex mtx;
	52	struct ww_acquire_ctx ctx;
	53	int ret;
	54
	55	ww_mutex_init(&mtx.mutex, &ww_class);
	56	ww_acquire_init(&ctx, &ww_class);
	57
	58	INIT_WORK_ONSTACK(&mtx.work, test_mutex_work);
	59	init_completion(&mtx.ready);
	60	init_completion(&mtx.go);
	61	init_completion(&mtx.done);
	62	mtx.flags = flags;
	63
	64	schedule_work(&mtx.work);
	65
	66	wait_for_completion(&mtx.ready);
	67	ww_mutex_lock(&mtx.mutex, (flags & TEST_MTX_CTX) ? &ctx : NULL);
	68	complete(&mtx.go);
	69	if (flags & TEST_MTX_SPIN) {
	70	unsigned long timeout = jiffies + TIMEOUT;
	71
	72	ret = 0;
	73	do {
	74	if (completion_done(&mtx.done)) {
	75	ret = -EINVAL;
	76	break;
	77	}
2b232e0c	78	cond_resched();
f2a5fec1 CW	79	} while (time_before(jiffies, timeout));
	80	} else {
	81	ret = wait_for_completion_timeout(&mtx.done, TIMEOUT);
	82	}
	83	ww_mutex_unlock(&mtx.mutex);
	84	ww_acquire_fini(&ctx);
	85
	86	if (ret) {
	87	pr_err("%s(flags=%x): mutual exclusion failure\n",
	88	__func__, flags);
	89	ret = -EINVAL;
	90	}
	91
	92	flush_work(&mtx.work);
	93	destroy_work_on_stack(&mtx.work);
	94	return ret;
	95	#undef TIMEOUT
	96	}
	97
	98	static int test_mutex(void)
	99	{
	100	int ret;
	101	int i;
	102
	103	for (i = 0; i < __TEST_MTX_LAST; i++) {
	104	ret = __test_mutex(i);
	105	if (ret)
	106	return ret;
	107	}
	108
	109	return 0;
	110	}
	111
c22fb380 CW	112	static int test_aa(void)
	113	{
	114	struct ww_mutex mutex;
	115	struct ww_acquire_ctx ctx;
	116	int ret;
	117
	118	ww_mutex_init(&mutex, &ww_class);
	119	ww_acquire_init(&ctx, &ww_class);
	120
	121	ww_mutex_lock(&mutex, &ctx);
	122
	123	if (ww_mutex_trylock(&mutex)) {
	124	pr_err("%s: trylocked itself!\n", __func__);
	125	ww_mutex_unlock(&mutex);
	126	ret = -EINVAL;
	127	goto out;
	128	}
	129
	130	ret = ww_mutex_lock(&mutex, &ctx);
	131	if (ret != -EALREADY) {
	132	pr_err("%s: missed deadlock for recursing, ret=%d\n",
	133	__func__, ret);
	134	if (!ret)
	135	ww_mutex_unlock(&mutex);
	136	ret = -EINVAL;
	137	goto out;
	138	}
	139
	140	ret = 0;
	141	out:
	142	ww_mutex_unlock(&mutex);
	143	ww_acquire_fini(&ctx);
	144	return ret;
	145	}
	146
70207686 CW	147	struct test_abba {
	148	struct work_struct work;
	149	struct ww_mutex a_mutex;
	150	struct ww_mutex b_mutex;
	151	struct completion a_ready;
	152	struct completion b_ready;
	153	bool resolve;
	154	int result;
	155	};
	156
	157	static void test_abba_work(struct work_struct *work)
	158	{
	159	struct test_abba abba = container_of(work, typeof(abba), work);
	160	struct ww_acquire_ctx ctx;
	161	int err;
	162
	163	ww_acquire_init(&ctx, &ww_class);
	164	ww_mutex_lock(&abba->b_mutex, &ctx);
	165
	166	complete(&abba->b_ready);
	167	wait_for_completion(&abba->a_ready);
	168
	169	err = ww_mutex_lock(&abba->a_mutex, &ctx);
	170	if (abba->resolve && err == -EDEADLK) {
	171	ww_mutex_unlock(&abba->b_mutex);
	172	ww_mutex_lock_slow(&abba->a_mutex, &ctx);
	173	err = ww_mutex_lock(&abba->b_mutex, &ctx);
	174	}
	175
	176	if (!err)
	177	ww_mutex_unlock(&abba->a_mutex);
	178	ww_mutex_unlock(&abba->b_mutex);
	179	ww_acquire_fini(&ctx);
	180
	181	abba->result = err;
	182	}
	183
	184	static int test_abba(bool resolve)
	185	{
	186	struct test_abba abba;
	187	struct ww_acquire_ctx ctx;
	188	int err, ret;
	189
	190	ww_mutex_init(&abba.a_mutex, &ww_class);
	191	ww_mutex_init(&abba.b_mutex, &ww_class);
	192	INIT_WORK_ONSTACK(&abba.work, test_abba_work);
	193	init_completion(&abba.a_ready);
	194	init_completion(&abba.b_ready);
	195	abba.resolve = resolve;
	196
	197	schedule_work(&abba.work);
	198
	199	ww_acquire_init(&ctx, &ww_class);
	200	ww_mutex_lock(&abba.a_mutex, &ctx);
	201
	202	complete(&abba.a_ready);
	203	wait_for_completion(&abba.b_ready);
	204
	205	err = ww_mutex_lock(&abba.b_mutex, &ctx);
	206	if (resolve && err == -EDEADLK) {
	207	ww_mutex_unlock(&abba.a_mutex);
	208	ww_mutex_lock_slow(&abba.b_mutex, &ctx);
	209	err = ww_mutex_lock(&abba.a_mutex, &ctx);
	210	}
211
212	if (!err)
213	ww_mutex_unlock(&abba.b_mutex);
214	ww_mutex_unlock(&abba.a_mutex);
215	ww_acquire_fini(&ctx);
216
217	flush_work(&abba.work);
218	destroy_work_on_stack(&abba.work);
219
220	ret = 0;
221	if (resolve) {
222	if (err \|\| abba.result) {
223	pr_err("%s: failed to resolve ABBA deadlock, A err=%d, B err=%d\n",
224	__func__, err, abba.result);
225	ret = -EINVAL;
226	}
227	} else {
228	if (err != -EDEADLK && abba.result != -EDEADLK) {
229	pr_err("%s: missed ABBA deadlock, A err=%d, B err=%d\n",
230	__func__, err, abba.result);
231	ret = -EINVAL;
232	}
233	}
234	return ret;
235	}
236
d1b42b80 CW	237	struct test_cycle {
	238	struct work_struct work;
	239	struct ww_mutex a_mutex;
	240	struct ww_mutex *b_mutex;
	241	struct completion *a_signal;
	242	struct completion b_signal;
	243	int result;
	244	};
	245
	246	static void test_cycle_work(struct work_struct *work)
	247	{
	248	struct test_cycle cycle = container_of(work, typeof(cycle), work);
	249	struct ww_acquire_ctx ctx;
e4a02ed2	250	int err, erra = 0;
d1b42b80 CW	251
	252	ww_acquire_init(&ctx, &ww_class);
	253	ww_mutex_lock(&cycle->a_mutex, &ctx);
	254
	255	complete(cycle->a_signal);
	256	wait_for_completion(&cycle->b_signal);
	257
	258	err = ww_mutex_lock(cycle->b_mutex, &ctx);
	259	if (err == -EDEADLK) {
e4a02ed2	260	err = 0;
d1b42b80 CW	261	ww_mutex_unlock(&cycle->a_mutex);
d1b42b80 CW	262	ww_mutex_lock_slow(cycle->b_mutex, &ctx);
e4a02ed2	263	erra = ww_mutex_lock(&cycle->a_mutex, &ctx);
d1b42b80 CW	264	}
	265
	266	if (!err)
	267	ww_mutex_unlock(cycle->b_mutex);
e4a02ed2 GR	268	if (!erra)
e4a02ed2 GR	269	ww_mutex_unlock(&cycle->a_mutex);
d1b42b80 CW	270	ww_acquire_fini(&ctx);
d1b42b80 CW	271
e4a02ed2	272	cycle->result = err ?: erra;
d1b42b80 CW	273	}
	274
	275	static int __test_cycle(unsigned int nthreads)
	276	{
	277	struct test_cycle *cycles;
	278	unsigned int n, last = nthreads - 1;
	279	int ret;
	280
	281	cycles = kmalloc_array(nthreads, sizeof(*cycles), GFP_KERNEL);
	282	if (!cycles)
	283	return -ENOMEM;
	284
	285	for (n = 0; n < nthreads; n++) {
	286	struct test_cycle *cycle = &cycles[n];
	287
	288	ww_mutex_init(&cycle->a_mutex, &ww_class);
	289	if (n == last)
	290	cycle->b_mutex = &cycles[0].a_mutex;
	291	else
	292	cycle->b_mutex = &cycles[n + 1].a_mutex;
	293
	294	if (n == 0)
	295	cycle->a_signal = &cycles[last].b_signal;
	296	else
	297	cycle->a_signal = &cycles[n - 1].b_signal;
	298	init_completion(&cycle->b_signal);
	299
	300	INIT_WORK(&cycle->work, test_cycle_work);
	301	cycle->result = 0;
	302	}
	303
	304	for (n = 0; n < nthreads; n++)
	305	queue_work(wq, &cycles[n].work);
	306
	307	flush_workqueue(wq);
	308
	309	ret = 0;
	310	for (n = 0; n < nthreads; n++) {
	311	struct test_cycle *cycle = &cycles[n];
	312
	313	if (!cycle->result)
	314	continue;
	315
0b405c65	316	pr_err("cyclic deadlock not resolved, ret[%d/%d] = %d\n",
d1b42b80 CW	317	n, nthreads, cycle->result);
	318	ret = -EINVAL;
	319	break;
	320	}
	321
	322	for (n = 0; n < nthreads; n++)
	323	ww_mutex_destroy(&cycles[n].a_mutex);
	324	kfree(cycles);
	325	return ret;
	326	}
	327
	328	static int test_cycle(unsigned int ncpus)
	329	{
	330	unsigned int n;
	331	int ret;
	332
	333	for (n = 2; n <= ncpus + 1; n++) {
	334	ret = __test_cycle(n);
	335	if (ret)
	336	return ret;
	337	}
	338
	339	return 0;
	340	}
	341
2a0c1128 CW	342	struct stress {
	343	struct work_struct work;
	344	struct ww_mutex *locks;
57dd924e	345	unsigned long timeout;
2a0c1128	346	int nlocks;
2a0c1128 CW	347	};
	348
	349	static int *get_random_order(int count)
	350	{
	351	int *order;
	352	int n, r, tmp;
	353
0ee931c4	354	order = kmalloc_array(count, sizeof(*order), GFP_KERNEL);
2a0c1128 CW	355	if (!order)
	356	return order;
	357
	358	for (n = 0; n < count; n++)
	359	order[n] = n;
	360
	361	for (n = count - 1; n > 1; n--) {
	362	r = get_random_int() % (n + 1);
	363	if (r != n) {
	364	tmp = order[n];
	365	order[n] = order[r];
	366	order[r] = tmp;
	367	}
	368	}
	369
	370	return order;
	371	}
	372
	373	static void dummy_load(struct stress *stress)
	374	{
	375	usleep_range(1000, 2000);
	376	}
	377
	378	static void stress_inorder_work(struct work_struct *work)
	379	{
	380	struct stress stress = container_of(work, typeof(stress), work);
	381	const int nlocks = stress->nlocks;
	382	struct ww_mutex *locks = stress->locks;
	383	struct ww_acquire_ctx ctx;
	384	int *order;
	385
	386	order = get_random_order(nlocks);
	387	if (!order)
	388	return;
	389
2a0c1128 CW	390	do {
	391	int contended = -1;
	392	int n, err;
	393
bf7b3ac2	394	ww_acquire_init(&ctx, &ww_class);
2a0c1128 CW	395	retry:
	396	err = 0;
	397	for (n = 0; n < nlocks; n++) {
	398	if (n == contended)
	399	continue;
	400
	401	err = ww_mutex_lock(&locks[order[n]], &ctx);
	402	if (err < 0)
	403	break;
	404	}
	405	if (!err)
	406	dummy_load(stress);
	407
	408	if (contended > n)
	409	ww_mutex_unlock(&locks[order[contended]]);
	410	contended = n;
	411	while (n--)
	412	ww_mutex_unlock(&locks[order[n]]);
	413
	414	if (err == -EDEADLK) {
	415	ww_mutex_lock_slow(&locks[order[contended]], &ctx);
	416	goto retry;
	417	}
	418
	419	if (err) {
	420	pr_err_once("stress (%s) failed with %d\n",
	421	__func__, err);
	422	break;
	423	}
2a0c1128	424
bf7b3ac2	425	ww_acquire_fini(&ctx);
57dd924e	426	} while (!time_after(jiffies, stress->timeout));
2a0c1128 CW	427
	428	kfree(order);
	429	kfree(stress);
	430	}
	431
	432	struct reorder_lock {
	433	struct list_head link;
	434	struct ww_mutex *lock;
	435	};
	436
	437	static void stress_reorder_work(struct work_struct *work)
	438	{
	439	struct stress stress = container_of(work, typeof(stress), work);
	440	LIST_HEAD(locks);
	441	struct ww_acquire_ctx ctx;
	442	struct reorder_lock ll, ln;
	443	int *order;
	444	int n, err;
	445
	446	order = get_random_order(stress->nlocks);
	447	if (!order)
	448	return;
	449
	450	for (n = 0; n < stress->nlocks; n++) {
	451	ll = kmalloc(sizeof(*ll), GFP_KERNEL);
	452	if (!ll)
	453	goto out;
	454
	455	ll->lock = &stress->locks[order[n]];
	456	list_add(&ll->link, &locks);
	457	}
	458	kfree(order);
	459	order = NULL;
	460
2a0c1128	461	do {
bf7b3ac2 PZ	462	ww_acquire_init(&ctx, &ww_class);
bf7b3ac2 PZ	463
2a0c1128 CW	464	list_for_each_entry(ll, &locks, link) {
	465	err = ww_mutex_lock(ll->lock, &ctx);
	466	if (!err)
	467	continue;
	468
	469	ln = ll;
	470	list_for_each_entry_continue_reverse(ln, &locks, link)
	471	ww_mutex_unlock(ln->lock);
	472
	473	if (err != -EDEADLK) {
	474	pr_err_once("stress (%s) failed with %d\n",
	475	__func__, err);
	476	break;
	477	}
	478
	479	ww_mutex_lock_slow(ll->lock, &ctx);
	480	list_move(&ll->link, &locks); /* restarts iteration */
	481	}
	482
	483	dummy_load(stress);
	484	list_for_each_entry(ll, &locks, link)
	485	ww_mutex_unlock(ll->lock);
2a0c1128	486
bf7b3ac2	487	ww_acquire_fini(&ctx);
57dd924e	488	} while (!time_after(jiffies, stress->timeout));
2a0c1128 CW	489
	490	out:
	491	list_for_each_entry_safe(ll, ln, &locks, link)
	492	kfree(ll);
	493	kfree(order);
	494	kfree(stress);
	495	}
	496
	497	static void stress_one_work(struct work_struct *work)
	498	{
	499	struct stress stress = container_of(work, typeof(stress), work);
	500	const int nlocks = stress->nlocks;
	501	struct ww_mutex *lock = stress->locks + (get_random_int() % nlocks);
	502	int err;
	503
	504	do {
	505	err = ww_mutex_lock(lock, NULL);
	506	if (!err) {
	507	dummy_load(stress);
	508	ww_mutex_unlock(lock);
	509	} else {
	510	pr_err_once("stress (%s) failed with %d\n",
	511	__func__, err);
	512	break;
	513	}
57dd924e	514	} while (!time_after(jiffies, stress->timeout));
2a0c1128 CW	515
	516	kfree(stress);
	517	}
	518
	519	#define STRESS_INORDER BIT(0)
	520	#define STRESS_REORDER BIT(1)
	521	#define STRESS_ONE BIT(2)
	522	#define STRESS_ALL (STRESS_INORDER \| STRESS_REORDER \| STRESS_ONE)
	523
57dd924e	524	static int stress(int nlocks, int nthreads, unsigned int flags)
2a0c1128 CW	525	{
	526	struct ww_mutex *locks;
	527	int n;
	528
	529	locks = kmalloc_array(nlocks, sizeof(*locks), GFP_KERNEL);
	530	if (!locks)
	531	return -ENOMEM;
	532
	533	for (n = 0; n < nlocks; n++)
	534	ww_mutex_init(&locks[n], &ww_class);
	535
	536	for (n = 0; nthreads; n++) {
	537	struct stress *stress;
	538	void (fn)(struct work_struct work);
	539
	540	fn = NULL;
	541	switch (n & 3) {
	542	case 0:
	543	if (flags & STRESS_INORDER)
	544	fn = stress_inorder_work;
	545	break;
	546	case 1:
	547	if (flags & STRESS_REORDER)
	548	fn = stress_reorder_work;
	549	break;
	550	case 2:
	551	if (flags & STRESS_ONE)
	552	fn = stress_one_work;
	553	break;
	554	}
	555
	556	if (!fn)
	557	continue;
	558
	559	stress = kmalloc(sizeof(*stress), GFP_KERNEL);
	560	if (!stress)
	561	break;
	562
	563	INIT_WORK(&stress->work, fn);
	564	stress->locks = locks;
	565	stress->nlocks = nlocks;
57dd924e	566	stress->timeout = jiffies + 2*HZ;
2a0c1128 CW	567
	568	queue_work(wq, &stress->work);
	569	nthreads--;
	570	}
	571
	572	flush_workqueue(wq);
	573
	574	for (n = 0; n < nlocks; n++)
	575	ww_mutex_destroy(&locks[n]);
	576	kfree(locks);
	577
	578	return 0;
	579	}
	580
f2a5fec1 CW	581	static int __init test_ww_mutex_init(void)
f2a5fec1 CW	582	{
d1b42b80	583	int ncpus = num_online_cpus();
f2a5fec1 CW	584	int ret;
f2a5fec1 CW	585
d1b42b80 CW	586	wq = alloc_workqueue("test-ww_mutex", WQ_UNBOUND, 0);
	587	if (!wq)
	588	return -ENOMEM;
	589
f2a5fec1 CW	590	ret = test_mutex();
	591	if (ret)
	592	return ret;
	593
c22fb380 CW	594	ret = test_aa();
	595	if (ret)
	596	return ret;
	597
70207686 CW	598	ret = test_abba(false);
	599	if (ret)
	600	return ret;
	601
	602	ret = test_abba(true);
	603	if (ret)
	604	return ret;
	605
d1b42b80 CW	606	ret = test_cycle(ncpus);
	607	if (ret)
	608	return ret;
	609
57dd924e	610	ret = stress(16, 2*ncpus, STRESS_INORDER);
2a0c1128 CW	611	if (ret)
	612	return ret;
	613
57dd924e	614	ret = stress(16, 2*ncpus, STRESS_REORDER);
2a0c1128 CW	615	if (ret)
	616	return ret;
	617
57dd924e	618	ret = stress(4095, hweight32(STRESS_ALL)*ncpus, STRESS_ALL);
2a0c1128 CW	619	if (ret)
	620	return ret;
	621
f2a5fec1 CW	622	return 0;
	623	}
	624
	625	static void __exit test_ww_mutex_exit(void)
	626	{
d1b42b80	627	destroy_workqueue(wq);
f2a5fec1 CW	628	}
	629
	630	module_init(test_ww_mutex_init);
	631	module_exit(test_ww_mutex_exit);
	632
	633	MODULE_LICENSE("GPL");
	634	MODULE_AUTHOR("Intel Corporation");