[PATCH v2 5/5] locking/ww_mutex/test: Time an ABBA with both owners running

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

In the ABBA cases of test-ww_mutex, an owner never keeps running while
the other context blocks on it. With PREEMPT_RT, a ww_mutex waiter
spins while its owner runs. The wound that resolves an ABBA reaches the
waiter through a wakeup.

Add a wound-wait case where both contexts keep running. Each one runs
on its own CPU at SCHED_FIFO. The younger context holds B and blocks on
A. The older context holds A, then blocks on B, which wounds the
younger one. The older context must get B within 10ms on average, over
10 rounds.

On v7.4-rc1 with PREEMPT_RT, the case fails every time. The two
contexts spin on each other until the fair server preempts them, after
950ms by default. With "locking/rtmutex: Stop spinning on the owner
when the waiter is woken", earlier in this series, the older context
gets B in microseconds. Without PREEMPT_RT, the case passes with or
without that fix.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 kernel/locking/test-ww_mutex.c | 235 +++++++++++++++++++++++++++++++++
 1 file changed, 235 insertions(+)

diff --git a/kernel/locking/test-ww_mutex.c b/kernel/locking/test-ww_mutex.c
index 838d631544ed..9f76647f6c07 100644
--- a/kernel/locking/test-ww_mutex.c
+++ b/kernel/locking/test-ww_mutex.c
@@ -6,10 +6,12 @@
 #include <linux/kernel.h>
 
 #include <linux/completion.h>
+#include <linux/cpu.h>
 #include <linux/delay.h>
 #include <linux/kthread.h>
 #include <linux/module.h>
 #include <linux/prandom.h>
+#include <linux/sched/task.h>
 #include <linux/slab.h>
 #include <linux/ww_mutex.h>
 
@@ -279,6 +281,235 @@ static int test_abba(struct ww_class *class, bool trylock, bool resolve)
 	return ret;
 }
 
+/*
+ * An ABBA where both contexts keep running. Each one runs on its own CPU
+ * at SCHED_FIFO. The younger context holds B and blocks on A. The older
+ * context holds A and stays on its CPU. Then it blocks on B, which wounds
+ * the younger context.
+ *
+ * The wound reaches the younger context through a wakeup. A waiter that
+ * spins while its owner runs must stop spinning on that wakeup. If it
+ * does not, the two contexts spin on each other until something else
+ * needs one of the two CPUs.
+ *
+ * The older context must get B within 10ms on average, over 10 rounds.
+ * It takes microseconds when the spin stops on the wakeup.
+ *
+ * Wound-wait only. With wait-die, the younger context backs out as soon
+ * as it blocks on the older one.
+ */
+struct test_abba_spin {
+	struct ww_class *class;
+	struct ww_mutex a_mutex, b_mutex;
+	struct completion start, done[2];
+	struct task_struct *young;
+	atomic_t stage;
+	u64 wait_ns;
+	int err[2];
+};
+
+/*
+ * Spin until @s->stage reaches @stage. Give up after 5s. The acquire pairs
+ * with the release that sets each stage. This makes sure that:
+ * - the younger context takes its stamp after the older one;
+ * - a lock that a stage reports as taken is held before the other
+ *   context goes on.
+ */
+static bool abba_spin_until(struct test_abba_spin *s, int stage)
+{
+	u64 end = ktime_get_ns() + 5ULL * NSEC_PER_SEC;
+
+	while (atomic_read_acquire(&s->stage) < stage) {
+		if (ktime_get_ns() > end)
+			return false;
+		cpu_relax();
+	}
+	return true;
+}
+
+/*
+ * Spin until the younger context blocks on a lock. Its state is then no
+ * longer TASK_RUNNING. Give up after 5s.
+ */
+static bool abba_spin_until_waiting(struct test_abba_spin *s)
+{
+	u64 end = ktime_get_ns() + 5ULL * NSEC_PER_SEC;
+
+	while (task_is_running(s->young)) {
+		if (ktime_get_ns() > end)
+			return false;
+		cpu_relax();
+	}
+	return true;
+}
+
+static int abba_spin_old(void *arg)
+{
+	struct test_abba_spin *s = arg;
+	struct ww_acquire_ctx ctx;
+	u64 t, end;
+	int err = -ETIMEDOUT;
+
+	sched_set_fifo_low(current);
+	wait_for_completion(&s->start);
+	ww_acquire_init_noinject(&ctx, s->class);
+	atomic_set_release(&s->stage, 1);
+	if (!abba_spin_until(s, 2))
+		goto fini;
+	err = ww_mutex_lock(&s->a_mutex, &ctx);
+	if (err)
+		goto fini;
+	atomic_set_release(&s->stage, 3);
+	err = -ETIMEDOUT;
+	if (!abba_spin_until(s, 4) || !abba_spin_until_waiting(s))
+		goto unlock;
+	/* The younger context waits on A. Give it 1ms to start its spin. */
+	end = ktime_get_ns() + NSEC_PER_MSEC;
+	while (ktime_get_ns() < end)
+		cpu_relax();
+	t = ktime_get_ns();
+	err = ww_mutex_lock(&s->b_mutex, &ctx);
+	s->wait_ns = ktime_get_ns() - t;
+	if (!err)
+		ww_mutex_unlock(&s->b_mutex);
+unlock:
+	ww_mutex_unlock(&s->a_mutex);
+fini:
+	ww_acquire_fini(&ctx);
+	s->err[0] = err;
+	complete(&s->done[0]);
+	return 0;
+}
+
+static int abba_spin_young(void *arg)
+{
+	struct test_abba_spin *s = arg;
+	struct ww_acquire_ctx ctx;
+	int err = -ETIMEDOUT;
+
+	sched_set_fifo_low(current);
+	wait_for_completion(&s->start);
+	if (!abba_spin_until(s, 1))
+		goto out;
+	ww_acquire_init_noinject(&ctx, s->class);
+	err = ww_mutex_lock(&s->b_mutex, &ctx);
+	if (err)
+		goto fini;
+	atomic_set_release(&s->stage, 2);
+	if (!abba_spin_until(s, 3)) {
+		err = -ETIMEDOUT;
+		ww_mutex_unlock(&s->b_mutex);
+		goto fini;
+	}
+	atomic_set_release(&s->stage, 4);
+	err = ww_mutex_lock(&s->a_mutex, &ctx);
+	if (err == -EDEADLK) {
+		/* Wounded. Release B, wait for A, then take B again. */
+		ww_mutex_unlock(&s->b_mutex);
+		ww_mutex_lock_slow(&s->a_mutex, &ctx);
+		err = ww_mutex_lock(&s->b_mutex, &ctx);
+		if (err) {
+			ww_mutex_unlock(&s->a_mutex);
+			goto fini;
+		}
+	} else if (err) {
+		ww_mutex_unlock(&s->b_mutex);
+		goto fini;
+	}
+	ww_mutex_unlock(&s->b_mutex);
+	ww_mutex_unlock(&s->a_mutex);
+fini:
+	ww_acquire_fini(&ctx);
+out:
+	s->err[1] = err;
+	complete(&s->done[1]);
+	return 0;
+}
+
+static int test_abba_spin(struct ww_class *class)
+{
+	int (*fn[2])(void *) = { abba_spin_old, abba_spin_young };
+	unsigned int c, cpu[2] = { nr_cpu_ids, nr_cpu_ids };
+	u64 total = 0, longest = 0;
+	struct test_abba_spin s;
+	int i, round, ret = 0;
+
+	if (class->is_wait_die)
+		return 0;
+	cpus_read_lock();
+	/* Use the last two online CPUs. Boot and housekeeping use them least. */
+	for_each_online_cpu(c) {
+		cpu[0] = cpu[1];
+		cpu[1] = c;
+	}
+	for (round = 0; cpu[0] < nr_cpu_ids && round < 10 && !ret; round++) {
+		struct task_struct *t[2];
+
+		ww_mutex_init(&s.a_mutex, class);
+		ww_mutex_init(&s.b_mutex, class);
+		init_completion(&s.start);
+		atomic_set(&s.stage, 0);
+		s.class = class;
+		s.wait_ns = 0;
+		for (i = 0; i < 2; i++) {
+			init_completion(&s.done[i]);
+			s.err[i] = -EINVAL;
+		}
+		for (i = 0; i < 2; i++) {
+			t[i] = kthread_create_on_cpu(fn[i], &s, cpu[i], "ww_abba_spin/%u");
+			if (IS_ERR(t[i])) {
+				ret = PTR_ERR(t[i]);
+				if (i)
+					kthread_stop(t[0]);
+				goto unlock;
+			}
+		}
+		s.young = t[1];
+		/*
+		 * Hold a reference. kthread_stop() may run after the thread
+		 * has returned.
+		 */
+		for (i = 0; i < 2; i++) {
+			get_task_struct(t[i]);
+			wake_up_process(t[i]);
+		}
+		/*
+		 * Release both threads at once. Neither one starts spinning
+		 * before the other.
+		 */
+		complete_all(&s.start);
+		for (i = 0; i < 2; i++) {
+			int err;
+
+			wait_for_completion(&s.done[i]);
+			err = kthread_stop(t[i]);
+			put_task_struct(t[i]);
+			if (err && !ret) {
+				pr_err("%s: kthread_stop: %d\n", __func__, err);
+				ret = err;
+			}
+		}
+		if (s.err[0] || s.err[1]) {
+			pr_err("%s: ABBA with both owners running not resolved, err %d and %d\n",
+			       __func__, s.err[0], s.err[1]);
+			ret = -EINVAL;
+		}
+		total += s.wait_ns;
+		longest = max(longest, s.wait_ns);
+	}
+	if (cpu[0] >= nr_cpu_ids)
+		pr_info("%s: skipped, two online CPUs needed\n", __func__);
+	if (!ret && round && total > 10 * NSEC_PER_MSEC * round) {
+		pr_err("%s: ABBA with both owners running resolved in %llu us on average, %llu us at most\n",
+		       __func__, div_u64(total, round * NSEC_PER_USEC),
+		       div_u64(longest, NSEC_PER_USEC));
+		ret = -EINVAL;
+	}
+unlock:
+	cpus_read_unlock();
+	return ret;
+}
+
 struct test_cycle {
 	struct work_struct work;
 	struct ww_class *class;
@@ -664,6 +895,10 @@ static int run_tests(struct ww_class *class)
 			return ret;
 	}
 
+	ret = test_abba_spin(class);
+	if (ret)
+		return ret;
+
 	ret = test_cycle(class, ncpus);
 	if (ret)
 		return ret;
-- 
2.47.3