Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1531281 > unrolled thread

[PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid stampedes

Back to article view | Back to linux.kernel

Contents

  [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid stampedes Nicolai Hähnle <nhaehnle@gmail.com> - 2016-11-28 13:30 +0100
    [PATCH 2/4] locking: Add kselftests for ww_mutex AA deadlock detection Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 01:40 +0100
    [PATCH 4/4] locking: Add kselftests for ww_mutex stress Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 01:40 +0100
      Re: [PATCH 4/4] locking: Add kselftests for ww_mutex stress Maarten Lankhorst <dev@mblankhorst.nl> - 2016-11-30 13:30 +0100
        Re: [PATCH 4/4] locking: Add kselftests for ww_mutex stress Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 14:00 +0100
    [PATCH 1/4] locking: Begin kselftests for ww_mutex Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 01:40 +0100
      [PATCH 3/4] locking: Add kselftests for ww_mutex ABBA deadlock detection Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 01:40 +0100
      Re: [PATCH 1/4] locking: Begin kselftests for ww_mutex Nicolai Hähnle <nhaehnle@gmail.com> - 2016-11-30 09:10 +0100
    Re: [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid  stampedes Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 10:50 +0100
      Re: [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid  stampedes Nicolai Hähnle <nhaehnle@gmail.com> - 2016-11-30 13:10 +0100
        Re: [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid  stampedes Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 13:30 +0100
          Re: [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid  stampedes Nicolai Hähnle <nhaehnle@gmail.com> - 2016-11-30 14:50 +0100

#1531281 — [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid stampedes

It turns out that the deadlock that I found last week was already implicitly
fixed during the lock->owner redesign, by checking the WAITERS bit in the
w/w lock fast path. However, since I had already started looking into
sorting the wait list, here goes.

The basic idea is to make sure that:

1. All waiters that have a ww_ctx appear in stamp order in the wait list.
Waiters without a ww_ctx are still supported and appear in FIFO order as
before.

2. At most one of the waiters can be in a state where it has to check for
back off (i.e., ww_ctx->acquire > 0). Technically, there are short time
windows in which more than one such waiter can be on the list, but all
but the first one are running. This happens when a new waiter with
ww_ctx->acquire > 0 adds itself at the front of the list and wakes up the
previous head of the list, and of course multiple such chained cases can
be in-flight simultaneously.

Then we only ever have to wake up one task at a time. This is _not_ always
the head of the wait list, since there may be waiters without a context. But
among waiters with a context, we only ever have to wake the first one.

To achieve all this, the series adds a new field to mutex_waiter which is
only used for the w/w lock case. As a consequence, calling mutex_lock
directly on w/w locks is now definitely incorrect. That was likely the
intention previously anyway, but grepping through the source I did find one
place that had slipped through.

I've included timings taken from a contention-heavy stress test to some of
the patches. The stress test performs actual GPU operations which take a
good chunk of the wall time, but even so, the series still manages to
improve the wall time quite a bit.

Cheers,
Nicolai

[toc] | [next] | [standalone]

#1532865 — [PATCH 2/4] locking: Add kselftests for ww_mutex AA deadlock detection

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Maarten Lankhorst <dev@mblankhorst.nl>
Cc: Nicolai Hähnle <nhaehnle@gmail.com>
---
 kernel/locking/test-ww_mutex.c | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/kernel/locking/test-ww_mutex.c b/kernel/locking/test-ww_mutex.c
index e94b807e06c2..02a4bacf8aac 100644
--- a/kernel/locking/test-ww_mutex.c
+++ b/kernel/locking/test-ww_mutex.c
@@ -118,6 +118,41 @@ static int test_mutex(void)
 	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;
+}
+
 static int __init test_ww_mutex_init(void)
 {
 	int ret;
@@ -126,6 +161,10 @@ static int __init test_ww_mutex_init(void)
 	if (ret)
 		return ret;
 
+	ret = test_aa();
+	if (ret)
+		return ret;
+
 	return 0;
 }
 
-- 
2.10.2

[toc] | [prev] | [next] | [standalone]

#1532867 — [PATCH 4/4] locking: Add kselftests for ww_mutex stress

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Maarten Lankhorst <dev@mblankhorst.nl>
Cc: Nicolai Hähnle <nhaehnle@gmail.com>
---
 kernel/locking/test-ww_mutex.c | 134 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 134 insertions(+)

diff --git a/kernel/locking/test-ww_mutex.c b/kernel/locking/test-ww_mutex.c
index 63a5031de138..c367014f62dc 100644
--- a/kernel/locking/test-ww_mutex.c
+++ b/kernel/locking/test-ww_mutex.c
@@ -21,6 +21,9 @@
 #include <linux/kthread.h>
 #include <linux/ww_mutex.h>
 #include <linux/completion.h>
+#include <linux/random.h>
+#include <linux/slab.h>
+#include <linux/delay.h>
 
 MODULE_LICENSE("GPL");
 MODULE_AUTHOR("Intel Corporation");
@@ -224,6 +227,129 @@ static int test_abba(void)
 	return ret;
 }
 
+struct stress {
+	struct work_struct work;
+	struct ww_mutex *locks;
+	int nlocks;
+};
+
+static int *get_random_order(int count)
+{
+	int *order;
+	int n, r, tmp;
+
+	order = kmalloc_array(count, sizeof(*order), GFP_TEMPORARY);
+	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 stress_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 contended = -1;
+	int *order;
+	int n, ret;
+
+	order = get_random_order(nlocks);
+	if (!order)
+		return;
+
+	ww_acquire_init(&ctx, &ww_class);
+
+retry:
+	ret = 0;
+	for (n = 0; n < nlocks; n++) {
+		if (n == contended)
+			continue;
+
+		ret = ww_mutex_lock(&locks[order[n]], &ctx);
+		if (ret < 0)
+			break;
+	}
+	if (!ret)
+		usleep_range(1000, 2000); /* dummy load */
+
+	if (contended > n)
+		ww_mutex_unlock(&locks[order[contended]]);
+	contended = n;
+	while (n--)
+		ww_mutex_unlock(&locks[order[n]]);
+
+	if (ret == -EDEADLK) {
+		ww_mutex_lock_slow(&locks[order[contended]], &ctx);
+		goto retry;
+	}
+
+	if (ret)
+		pr_err_once("ww_mutex stress test failed with %d\n", ret);
+
+	ww_acquire_fini(&ctx);
+
+	kfree(order);
+	kfree(stress);
+}
+
+static int stress(int nlocks, int count)
+{
+	struct ww_mutex *locks;
+	struct workqueue_struct *wq;
+	int ret = -ENOMEM;
+	int n;
+
+	wq = alloc_workqueue("test-ww_mutex", WQ_UNBOUND, 0);
+	if (!wq)
+		return -ENOMEM;
+
+	locks = kmalloc_array(nlocks, sizeof(*locks), GFP_KERNEL);
+	if (!locks)
+		goto err;
+
+	for (n = 0; n < nlocks; n++)
+		ww_mutex_init(&locks[n], &ww_class);
+
+	for (n = 0; n < count; n++) {
+		struct stress *stress;
+
+		stress = kmalloc(sizeof(*stress), GFP_KERNEL);
+		if (!stress)
+			break;
+
+		INIT_WORK(&stress->work, stress_work);
+		stress->locks = locks;
+		stress->nlocks = nlocks;
+
+		queue_work(wq, &stress->work);
+	}
+
+	flush_workqueue(wq);
+
+	for (n = 0; n < nlocks; n++)
+		ww_mutex_destroy(&locks[n]);
+	kfree(locks);
+
+	ret = 0;
+err:
+	destroy_workqueue(wq);
+	return ret;
+}
+
 static int __init test_ww_mutex_init(void)
 {
 	int ret;
@@ -240,6 +366,14 @@ static int __init test_ww_mutex_init(void)
 	if (ret)
 		return ret;
 
+	ret = stress(16, 1024);
+	if (ret)
+		return ret;
+
+	ret = stress(4096, 1024);
+	if (ret)
+		return ret;
+
 	return 0;
 }
 
-- 
2.10.2

[toc] | [prev] | [next] | [standalone]

#1533266 — Re: [PATCH 4/4] locking: Add kselftests for ww_mutex stress

Op 30-11-16 om 01:35 schreef Chris Wilson:
> Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Maarten Lankhorst <dev@mblankhorst.nl>
> Cc: Nicolai Hähnle <nhaehnle@gmail.com>
> ---
>  kernel/locking/test-ww_mutex.c | 134 +++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 134 insertions(+)
>
> diff --git a/kernel/locking/test-ww_mutex.c b/kernel/locking/test-ww_mutex.c
> index 63a5031de138..c367014f62dc 100644
> --- a/kernel/locking/test-ww_mutex.c
> +++ b/kernel/locking/test-ww_mutex.c
> @@ -21,6 +21,9 @@
>  #include <linux/kthread.h>
>  #include <linux/ww_mutex.h>
>  #include <linux/completion.h>
> +#include <linux/random.h>
> +#include <linux/slab.h>
> +#include <linux/delay.h>
>  
>  MODULE_LICENSE("GPL");
>  MODULE_AUTHOR("Intel Corporation");
> @@ -224,6 +227,129 @@ static int test_abba(void)
>  	return ret;
>  }
>  
> +struct stress {
> +	struct work_struct work;
> +	struct ww_mutex *locks;
> +	int nlocks;
> +};
> +
> +static int *get_random_order(int count)
> +{
> +	int *order;
> +	int n, r, tmp;
> +
> +	order = kmalloc_array(count, sizeof(*order), GFP_TEMPORARY);
> +	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 stress_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 contended = -1;
> +	int *order;
> +	int n, ret;
> +
> +	order = get_random_order(nlocks);
> +	if (!order)
> +		return;
> +
> +	ww_acquire_init(&ctx, &ww_class);
> +
> +retry:
> +	ret = 0;
> +	for (n = 0; n < nlocks; n++) {
> +		if (n == contended)
> +			continue;
> +
> +		ret = ww_mutex_lock(&locks[order[n]], &ctx);
> +		if (ret < 0)
> +			break;
> +	}
What's wrong with attempting to lock the contended lock here?
Who knows, this might find some more bugs than the functional tests already do.
> +	if (!ret)
> +		usleep_range(1000, 2000); /* dummy load */
> +
> +	if (contended > n)
> +		ww_mutex_unlock(&locks[order[contended]]);
> +	contended = n;
> +	while (n--)
> +		ww_mutex_unlock(&locks[order[n]]);
> +
> +	if (ret == -EDEADLK) {
> +		ww_mutex_lock_slow(&locks[order[contended]], &ctx);
> +		goto retry;
> +	}
> +
> +	if (ret)
> +		pr_err_once("ww_mutex stress test failed with %d\n", ret);
> +
> +	ww_acquire_fini(&ctx);
> +
> +	kfree(order);
> +	kfree(stress);
> +}
> +
> +static int stress(int nlocks, int count)
> +{
> +	struct ww_mutex *locks;
> +	struct workqueue_struct *wq;
> +	int ret = -ENOMEM;
> +	int n;
> +
> +	wq = alloc_workqueue("test-ww_mutex", WQ_UNBOUND, 0);
> +	if (!wq)
> +		return -ENOMEM;
> +
> +	locks = kmalloc_array(nlocks, sizeof(*locks), GFP_KERNEL);
> +	if (!locks)
> +		goto err;
> +
> +	for (n = 0; n < nlocks; n++)
> +		ww_mutex_init(&locks[n], &ww_class);
> +
> +	for (n = 0; n < count; n++) {
> +		struct stress *stress;
> +
> +		stress = kmalloc(sizeof(*stress), GFP_KERNEL);
> +		if (!stress)
> +			break;
> +
> +		INIT_WORK(&stress->work, stress_work);
> +		stress->locks = locks;
> +		stress->nlocks = nlocks;
> +
> +		queue_work(wq, &stress->work);
> +	}
> +
> +	flush_workqueue(wq);
> +
> +	for (n = 0; n < nlocks; n++)
> +		ww_mutex_destroy(&locks[n]);
> +	kfree(locks);
> +
> +	ret = 0;
> +err:
> +	destroy_workqueue(wq);
> +	return ret;
> +}
> +
>  static int __init test_ww_mutex_init(void)
>  {
>  	int ret;
> @@ -240,6 +366,14 @@ static int __init test_ww_mutex_init(void)
>  	if (ret)
>  		return ret;
>  
> +	ret = stress(16, 1024);
> +	if (ret)
> +		return ret;
> +
> +	ret = stress(4096, 1024);
> +	if (ret)
> +		return ret;
> +
>  	return 0;
>  }
>  

[toc] | [prev] | [next] | [standalone]

#1533277 — Re: [PATCH 4/4] locking: Add kselftests for ww_mutex stress

On Wed, Nov 30, 2016 at 01:29:39PM +0100, Maarten Lankhorst wrote:
> > +static void stress_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 contended = -1;
> > +	int *order;
> > +	int n, ret;
> > +
> > +	order = get_random_order(nlocks);
> > +	if (!order)
> > +		return;
> > +
> > +	ww_acquire_init(&ctx, &ww_class);
> > +
> > +retry:
> > +	ret = 0;
> > +	for (n = 0; n < nlocks; n++) {
> > +		if (n == contended)
> > +			continue;
> > +
> > +		ret = ww_mutex_lock(&locks[order[n]], &ctx);
> > +		if (ret < 0)
> > +			break;
> > +	}
> What's wrong with attempting to lock the contended lock here?
> Who knows, this might find some more bugs than the functional tests already do.

I was trying to follow the guide, which was lock, backoff by unlocking
everything, slowlock the contended lock, then lock everything else.

I have now a second worker that follows the reordering method as well.
(As well as a test that slowlock after the ABBA deadlock detection
resolves the locking order.)

If you have a sketch of something else to try, I'll add it.
-Chris

-- 
Chris Wilson, Intel Open Source Technology Centre

[toc] | [prev] | [next] | [standalone]

#1532868 — [PATCH 1/4] locking: Begin kselftests for ww_mutex

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Maarten Lankhorst <dev@mblankhorst.nl>
Cc: Nicolai Hähnle <nhaehnle@gmail.com>
---
 kernel/locking/Makefile        |   1 +
 kernel/locking/test-ww_mutex.c | 137 +++++++++++++++++++++++++++++++++++++++++
 lib/Kconfig.debug              |  10 +++
 3 files changed, 148 insertions(+)
 create mode 100644 kernel/locking/test-ww_mutex.c

diff --git a/kernel/locking/Makefile b/kernel/locking/Makefile
index 6f88e352cd4f..760158d9d98d 100644
--- a/kernel/locking/Makefile
+++ b/kernel/locking/Makefile
@@ -28,3 +28,4 @@ obj-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
 obj-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem-xadd.o
 obj-$(CONFIG_QUEUED_RWLOCKS) += qrwlock.o
 obj-$(CONFIG_LOCK_TORTURE_TEST) += locktorture.o
+obj-$(CONFIG_WW_MUTEX_SELFTEST) += test-ww_mutex.o
diff --git a/kernel/locking/test-ww_mutex.c b/kernel/locking/test-ww_mutex.c
new file mode 100644
index 000000000000..e94b807e06c2
--- /dev/null
+++ b/kernel/locking/test-ww_mutex.c
@@ -0,0 +1,137 @@
+/*
+ * Module-based API test facility for ww_mutexes
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, you can access it online at
+ * http://www.gnu.org/licenses/gpl-2.0.html.
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/kthread.h>
+#include <linux/ww_mutex.h>
+#include <linux/completion.h>
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Intel Corporation");
+
+static DEFINE_WW_CLASS(ww_class);
+
+struct test_mutex {
+	struct work_struct work;
+	struct ww_mutex mutex;
+	struct completion ready, go, done;
+	unsigned flags;
+#define TEST_AB_SPIN BIT(0)
+#define TEST_AB_TRY BIT(1)
+};
+
+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_AB_TRY) {
+		while (!ww_mutex_trylock(&mtx->mutex))
+			cpu_relax();
+	} else {
+		ww_mutex_lock(&mtx->mutex, NULL);
+	}
+	complete(&mtx->done);
+	ww_mutex_unlock(&mtx->mutex);
+}
+
+static int __test_mutex(unsigned flags)
+{
+	struct test_mutex mtx;
+	int ret;
+
+	ww_mutex_init(&mtx.mutex, &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, NULL);
+	complete(&mtx.go);
+	if (flags & TEST_AB_SPIN) {
+		unsigned long timeout = jiffies + HZ;
+
+		ret = 0;
+		do {
+			if (completion_done(&mtx.done)) {
+				ret = -EINVAL;
+				break;
+			}
+			cpu_relax();
+		} while (time_before(jiffies, timeout));
+	} else {
+		ret = wait_for_completion_timeout(&mtx.done, HZ);
+	}
+	ww_mutex_unlock(&mtx.mutex);
+
+	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;
+}
+
+static int test_mutex(void)
+{
+	unsigned int modes[] = {
+		0,
+		TEST_AB_SPIN,
+		TEST_AB_TRY,
+		TEST_AB_SPIN | TEST_AB_TRY,
+	};
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(modes); i++) {
+		int ret;
+
+		ret = __test_mutex(modes[i]);
+		if (ret)
+			return ret;
+	}
+
+	return 0;
+}
+
+static int __init test_ww_mutex_init(void)
+{
+	int ret;
+
+	ret = test_mutex();
+	if (ret)
+		return ret;
+
+	return 0;
+}
+
+static void __exit test_ww_mutex_exit(void)
+{
+}
+
+module_init(test_ww_mutex_init);
+module_exit(test_ww_mutex_exit);
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index a6c8db1d62f6..5ffe7fd34c50 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1161,6 +1161,16 @@ config LOCK_TORTURE_TEST
 	  Say M if you want these torture tests to build as a module.
 	  Say N if you are unsure.
 
+config WW_MUTEX_SELFTEST
+	tristate "Wait/wound mutex selftests"
+	select DEBUG_WW_MUTEX_SLOWPATH
+	help
+	  This option provides a kernel module that runs tests on the
+	  on the struct ww_mutex locking API.
+
+	  Say M if you want these self tests to build as a module.
+	  Say N if you are unsure.
+
 endmenu # lock debugging
 
 config TRACE_IRQFLAGS
-- 
2.10.2

[toc] | [prev] | [next] | [standalone]

#1532869 — [PATCH 3/4] locking: Add kselftests for ww_mutex ABBA deadlock detection

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Maarten Lankhorst <dev@mblankhorst.nl>
Cc: Nicolai Hähnle <nhaehnle@gmail.com>
---
 kernel/locking/test-ww_mutex.c | 75 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)

diff --git a/kernel/locking/test-ww_mutex.c b/kernel/locking/test-ww_mutex.c
index 02a4bacf8aac..63a5031de138 100644
--- a/kernel/locking/test-ww_mutex.c
+++ b/kernel/locking/test-ww_mutex.c
@@ -153,6 +153,77 @@ static int test_aa(void)
 	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;
+	struct completion done;
+	int ret;
+};
+
+static void test_abba_work(struct work_struct *work)
+{
+	struct test_abba *abba = container_of(work, typeof(*abba), work);
+	struct ww_acquire_ctx ctx;
+
+	ww_acquire_init(&ctx, &ww_class);
+	ww_mutex_lock(&abba->b_mutex, &ctx);
+
+	complete(&abba->b_ready);
+	wait_for_completion(&abba->a_ready);
+	abba->ret = ww_mutex_lock(&abba->a_mutex, &ctx);
+	if (!abba->ret)
+		ww_mutex_unlock(&abba->a_mutex);
+
+	ww_mutex_unlock(&abba->b_mutex);
+	ww_acquire_fini(&ctx);
+
+	complete(&abba->done);
+}
+
+static int test_abba(void)
+{
+	struct test_abba abba;
+	struct ww_acquire_ctx ctx;
+	int 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);
+	init_completion(&abba.done);
+
+	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);
+	ret = ww_mutex_lock(&abba.b_mutex, &ctx);
+	if (!ret)
+		ww_mutex_unlock(&abba.b_mutex);
+	ww_mutex_unlock(&abba.a_mutex);
+
+	wait_for_completion(&abba.done);
+
+	if (ret != -EDEADLK && abba.ret != -EDEADLK) {
+		pr_err("%s: missed ABBA deadlock, A ret=%d, B ret=%d\n",
+		       __func__, ret, abba.ret);
+		ret = -EINVAL;
+		goto out;
+	}
+
+	ret = 0;
+out:
+	ww_acquire_fini(&ctx);
+	flush_work(&abba.work);
+	destroy_work_on_stack(&abba.work);
+	return ret;
+}
+
 static int __init test_ww_mutex_init(void)
 {
 	int ret;
@@ -165,6 +236,10 @@ static int __init test_ww_mutex_init(void)
 	if (ret)
 		return ret;
 
+	ret = test_abba();
+	if (ret)
+		return ret;
+
 	return 0;
 }
 
-- 
2.10.2

[toc] | [prev] | [next] | [standalone]

#1533050 — Re: [PATCH 1/4] locking: Begin kselftests for ww_mutex

On 30.11.2016 01:35, Chris Wilson wrote:
> Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Maarten Lankhorst <dev@mblankhorst.nl>
> Cc: Nicolai Hähnle <nhaehnle@gmail.com>
> ---
>  kernel/locking/Makefile        |   1 +
>  kernel/locking/test-ww_mutex.c | 137 +++++++++++++++++++++++++++++++++++++++++
>  lib/Kconfig.debug              |  10 +++
>  3 files changed, 148 insertions(+)
>  create mode 100644 kernel/locking/test-ww_mutex.c
>
> diff --git a/kernel/locking/Makefile b/kernel/locking/Makefile
> index 6f88e352cd4f..760158d9d98d 100644
> --- a/kernel/locking/Makefile
> +++ b/kernel/locking/Makefile
> @@ -28,3 +28,4 @@ obj-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
>  obj-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem-xadd.o
>  obj-$(CONFIG_QUEUED_RWLOCKS) += qrwlock.o
>  obj-$(CONFIG_LOCK_TORTURE_TEST) += locktorture.o
> +obj-$(CONFIG_WW_MUTEX_SELFTEST) += test-ww_mutex.o
> diff --git a/kernel/locking/test-ww_mutex.c b/kernel/locking/test-ww_mutex.c
> new file mode 100644
> index 000000000000..e94b807e06c2
> --- /dev/null
> +++ b/kernel/locking/test-ww_mutex.c
> @@ -0,0 +1,137 @@
> +/*
> + * Module-based API test facility for ww_mutexes
> + *
> + * This program is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License as published by
> + * the Free Software Foundation; either version 2 of the License, or
> + * (at your option) any later version.
> + *
> + * This program is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> + * GNU General Public License for more details.
> + *
> + * You should have received a copy of the GNU General Public License
> + * along with this program; if not, you can access it online at
> + * http://www.gnu.org/licenses/gpl-2.0.html.
> + */
> +
> +#include <linux/kernel.h>
> +#include <linux/module.h>
> +#include <linux/kthread.h>
> +#include <linux/ww_mutex.h>
> +#include <linux/completion.h>
> +
> +MODULE_LICENSE("GPL");
> +MODULE_AUTHOR("Intel Corporation");
> +
> +static DEFINE_WW_CLASS(ww_class);
> +
> +struct test_mutex {
> +	struct work_struct work;
> +	struct ww_mutex mutex;
> +	struct completion ready, go, done;
> +	unsigned flags;
> +#define TEST_AB_SPIN BIT(0)
> +#define TEST_AB_TRY BIT(1)
> +};


Is it common to put #defines inside structs like that? It looks odd to 
me. Apart from that, patches 1-4 all make sense to me.

Thanks,
Nicolai

[toc] | [prev] | [next] | [standalone]

#1533140 — Re: [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid stampedes

On Mon, Nov 28, 2016 at 01:20:01PM +0100, Nicolai Hähnle wrote:
> I've included timings taken from a contention-heavy stress test to some of
> the patches. The stress test performs actual GPU operations which take a
> good chunk of the wall time, but even so, the series still manages to
> improve the wall time quite a bit.

In looking at your contention scenarios, what was the average/max list
size? Just wondering if it makes sense to use an rbtree + first_waiter
instead of a sorted list from the start.
-Chris

-- 
Chris Wilson, Intel Open Source Technology Centre

[toc] | [prev] | [next] | [standalone]

#1533255 — Re: [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid stampedes

On 30.11.2016 10:40, Chris Wilson wrote:
> On Mon, Nov 28, 2016 at 01:20:01PM +0100, Nicolai Hähnle wrote:
>> I've included timings taken from a contention-heavy stress test to some of
>> the patches. The stress test performs actual GPU operations which take a
>> good chunk of the wall time, but even so, the series still manages to
>> improve the wall time quite a bit.
>
> In looking at your contention scenarios, what was the average/max list
> size? Just wondering if it makes sense to use an rbtree + first_waiter
> instead of a sorted list from the start.

I haven't measured this with the new series; previously, while I was 
debugging the deadlock on older kernels, I occasionally saw wait lists 
of up to ~20 tasks, spit-balling the average over all the deadlock cases 
I'd say the average was not more than ~5. The average _without_ 
deadlocks should be lower, if anything.

I saw that your test cases go quite a bit higher, but even the rather 
extreme load I was testing with -- which is not quite a load from an 
actual application, though it is related to one -- has 40 threads and so 
a theoretical maximum of 40.

Nicolai

> -Chris
>

[toc] | [prev] | [next] | [standalone]

#1533264 — Re: [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid stampedes

On Wed, Nov 30, 2016 at 12:52:28PM +0100, Nicolai Hähnle wrote:
> On 30.11.2016 10:40, Chris Wilson wrote:
> >On Mon, Nov 28, 2016 at 01:20:01PM +0100, Nicolai Hähnle wrote:
> >>I've included timings taken from a contention-heavy stress test to some of
> >>the patches. The stress test performs actual GPU operations which take a
> >>good chunk of the wall time, but even so, the series still manages to
> >>improve the wall time quite a bit.
> >
> >In looking at your contention scenarios, what was the average/max list
> >size? Just wondering if it makes sense to use an rbtree + first_waiter
> >instead of a sorted list from the start.
> 
> I haven't measured this with the new series; previously, while I was
> debugging the deadlock on older kernels, I occasionally saw wait
> lists of up to ~20 tasks, spit-balling the average over all the
> deadlock cases I'd say the average was not more than ~5. The average
> _without_ deadlocks should be lower, if anything.

Right, I wasn't expecting the list to be large, certainly no larger than
cores typically. On the borderline of where a more complex tree starts
to pay off.
 
> I saw that your test cases go quite a bit higher, but even the
> rather extreme load I was testing with -- which is not quite a load
> from an actual application, though it is related to one -- has 40
> threads and so a theoretical maximum of 40.

The stress loads were just values plucked out of nowhere to try and have
a reasonable stab at hitting the deadlock. Certainly if we were to wrap
that up in a microbenchmark we would want to have wider coverage (so the
graph against contention is more useful).

Do you have a branch I can pull the patches for (or what did you use as
the base)?
-Chris

-- 
Chris Wilson, Intel Open Source Technology Centre

[toc] | [prev] | [next] | [standalone]

#1533300 — Re: [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid stampedes

On 30.11.2016 13:20, Chris Wilson wrote:
> On Wed, Nov 30, 2016 at 12:52:28PM +0100, Nicolai Hähnle wrote:
>> On 30.11.2016 10:40, Chris Wilson wrote:
>>> On Mon, Nov 28, 2016 at 01:20:01PM +0100, Nicolai Hähnle wrote:
>>>> I've included timings taken from a contention-heavy stress test to some of
>>>> the patches. The stress test performs actual GPU operations which take a
>>>> good chunk of the wall time, but even so, the series still manages to
>>>> improve the wall time quite a bit.
>>>
>>> In looking at your contention scenarios, what was the average/max list
>>> size? Just wondering if it makes sense to use an rbtree + first_waiter
>>> instead of a sorted list from the start.
>>
>> I haven't measured this with the new series; previously, while I was
>> debugging the deadlock on older kernels, I occasionally saw wait
>> lists of up to ~20 tasks, spit-balling the average over all the
>> deadlock cases I'd say the average was not more than ~5. The average
>> _without_ deadlocks should be lower, if anything.
>
> Right, I wasn't expecting the list to be large, certainly no larger than
> cores typically. On the borderline of where a more complex tree starts
> to pay off.
>
>> I saw that your test cases go quite a bit higher, but even the
>> rather extreme load I was testing with -- which is not quite a load
>> from an actual application, though it is related to one -- has 40
>> threads and so a theoretical maximum of 40.
>
> The stress loads were just values plucked out of nowhere to try and have
> a reasonable stab at hitting the deadlock. Certainly if we were to wrap
> that up in a microbenchmark we would want to have wider coverage (so the
> graph against contention is more useful).
>
> Do you have a branch I can pull the patches for (or what did you use as
> the base)?

See git://people.freedesktop.org/~nh/linux mutex or 
https://cgit.freedesktop.org/~nh/linux/log/?h=mutex.

It's based on tip/core/locking + agd5f's drm-next, the latter only 
because I needed it for the test application.

Nicolai

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web