[PATCH v2 0/5] locking/rtmutex: priority inheritance fixes and tests

[PATCH v2 0/5] locking/rtmutex: priority inheritance fixes and tests

[Mathieu Desnoyers]

Hi Peter, Thomas,

This series fixes three rt_mutex priority inheritance bugs on v7.4-rc1,
and adds two tests that catch them. The bugs came out of the work on
"sched/deadline: bandwidth accounting fixes and selftests". Its v5,
posted after this series, applies on top of it. Its patch 8 takes a
deadline boost from the waiter's rt_mutex node, and needs patch 3 here
to keep that node current.

The fixes
=========

 1  Stop spinning on a running owner once the waiter is woken, so that
    timeouts and signals are no longer delayed.
 2  Initialize the ww_mutex context of a waiter, so that PREEMPT_RT
    reports PI futex deadlocks again.
 3  Clone a waiter's sort keys as it enters pi_waiters, so that the
    owner inherits the right priority.

Patch 4 adds futex_lock_pi_inherit to the futex selftests. It checks the
priority an owner runs at, and the EDEADLK of FUTEX_LOCK_PI. It also
checks how late a timeout or a signal ends a wait behind a running
owner. Patch 5 adds an ABBA with both owners running to test-ww_mutex.
v7.4-rc1 fails the cases of each fix. The series passes them, with and
without PREEMPT_RT. So do the locking API selftests, the ww_mutex
selftest, locktorture's rtmutex_lock and the futex selftests.

How this was developed
======================

An LLM coding assistant wrote these patches, their messages and the
tests, under my direction and review. Patch 1 came out of a stress test
of the deadline boost. Patch 3 came out of a review of the deadline fix
by a second model. Patch 2 came out of futex_lock_pi_inherit, on its
first run with PREEMPT_RT. A local run of the Sashiko AI review checked
each patch before posting.

Changes since v1
================

- Commit messages and comments rewritten to read more easily, after
  Peter's and Steven's reviews.
- Patch 1: Steven's wording, with the two paragraphs on the impact
  added. It carries his Reviewed-by.
- Patch 3: new subject, "locking/rtmutex: Clone the sort keys in
  rt_mutex_enqueue_pi()". The message shows the sequence that leaves
  stale keys, and the comment is one line.
- Patch 5: the stage handoff of the ABBA test uses release and acquire,
  as the Sashiko review of v1 found. On a weakly ordered CPU, the test
  could fail falsely with EDEADLK.
- No change to the kernel code.

Based on v7.4-rc1, 6628e7d4c6b2. It also applies as is to tip
sched/urgent (006991aa8997), which the deadline series is based on.

v1: https://lore.kernel.org/lkml/20261106235931.1478800-1-mathieu.desnoyers@efficios.com

Mathieu Desnoyers (5):
  locking/rtmutex: Stop spinning on the owner when the waiter is woken
  locking/rtmutex: Initialize the ww_mutex context of a waiter
  locking/rtmutex: Clone the sort keys in rt_mutex_enqueue_pi()
  selftests/futex: Test priority inheritance on PI futexes
  locking/ww_mutex/test: Time an ABBA with both owners running

 kernel/locking/rtmutex.c                      |   9 +-
 kernel/locking/rtmutex_common.h               |   1 +
 kernel/locking/test-ww_mutex.c                | 235 ++++++
 .../selftests/futex/functional/.gitignore     |   1 +
 .../selftests/futex/functional/Makefile       |   3 +-
 .../futex/functional/futex_lock_pi_inherit.c  | 773 ++++++++++++++++++
 .../testing/selftests/futex/functional/run.sh |   3 +
 7 files changed, 1021 insertions(+), 4 deletions(-)
 create mode 100644 tools/testing/selftests/futex/functional/futex_lock_pi_inherit.c


base-commit: 6628e7d4c6b25c8d18f1345e3a20d21829aae7e4
-- 
2.47.3

[PATCH v2 1/5] locking/rtmutex: Stop spinning on the owner when the waiter is woken

[Mathieu Desnoyers]

The top waiter of an rt_mutex sets its sleep state. Then it spins in
rtmutex_spin_on_owner() as long as the owner is running. A wakeup sets
the waiter back to TASK_RUNNING. The spin loop does not check for this.
So a timeout or a signal is only handled when the owner blocks, or when
the waiter has to reschedule.

The rtmutex_spin_on_owner() is just an optimization with the idea that
if the owner is still running on a CPU, it will likely release it soon.
If the owner gets preempted or schedules out on its own, the spinning
will stop and the waiter will sleep. This came from PREEMPT_RT adaptive
spinning for rt_spin_locks that allowed them to behave more like normal
spin locks and speed up PREEMPT_RT performance.

The problem is that when this was implemented for futex and normal
mutexes it did not account for timeouts or other mechanisms where
the owner releasing the lock wasn't the only way for the spinning
task to exit the mutex acquire. The spinning currently does not
account for anything else but the lock being released or the owner
sleeping.

The owner of a PI futex is a user task. It can run for a long time.
With an owner spinning in userspace, a 1ms pthread_mutex_timedlock()
returned up to 1.4s late in testing. The timeout signal or any signal
to the waiter will not stop it from spinning, and the signal will be
delayed until it exits the spin.

With PREEMPT_RT, two contexts that take two ww_mutexes in opposite
order spin on each other. Only something else that needs one of the two
CPUs stops them. By default, the fair server does it after 950ms, to
run SCHED_OTHER tasks.

Luckily, when the spinning task needs to exit the mutex lock code, its
state is set to TASK_RUNNING. By having the spin check the spinning
task's state to see if it switches to running, it can exit the spin
appropriately.

Fixes: 992caf7f1724 ("locking/rtmutex: Add adaptive spinwait mechanism")
Cc: stable@vger.kernel.org
Reviewed-by: Steven Rostedt <rostedt@goodmis.org>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 kernel/locking/rtmutex.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
index 5a9534c715b8..323973be2074 100644
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -1516,9 +1516,13 @@ static bool rtmutex_spin_on_owner(struct rt_mutex_base *lock,
 		 *  - current is not longer the top waiter
 		 *  - current is requested to reschedule (redundant
 		 *    for CONFIG_PREEMPT_RCU=y)
+		 *  - current is woken, by its timeout, a signal or
+		 *    whatever else would end the sleep the spin
+		 *    stands in for
 		 *  - the VCPU on which owner runs is preempted
 		 */
 		if (!owner_on_cpu(owner) || need_resched() ||
+		    task_is_running(current) ||
 		    !data_race(rt_mutex_waiter_is_top_waiter(lock, waiter))) {
 			res = false;
 			break;
-- 
2.47.3

[PATCH v2 2/5] locking/rtmutex: Initialize the ww_mutex context of a waiter

[Mathieu Desnoyers]

With PREEMPT_RT and CONFIG_DEBUG_RT_MUTEXES, FUTEX_LOCK_PI reports no
deadlock. Two threads that each block on a PI futex the other holds
sleep forever. Without PREEMPT_RT, the second one gets EDEADLK. A chain
deeper than max_lock_depth is also admitted.

With PREEMPT_RT, ww_mutexes are built on rtmutexes. They can create a
cycle in the lock graph legitimately, and the wound/die logic resolves
it. So the PREEMPT_RT chain walk turns deadlock detection off when it
finds a waiter with a ww_mutex context, waiter->ww_ctx. It also drops
the -EDEADLK of a walk that started from such a waiter.

But rt_mutex_init_waiter() does not set waiter->ww_ctx. Only
__rt_mutex_slowlock_locked() sets it. So the waiters of PI futexes and
rtlocks keep the 0x11 poison of CONFIG_DEBUG_RT_MUTEXES. Without that
option, they keep what was on the stack, unless the compiler zeroes it.
The chain walk then takes them for ww_mutex waiters.

The ww_mutex build of the chain walk can also requeue such waiters. On
two of them with equal priority, __waiter_less() would dereference the
poison.

Fix this by clearing waiter->ww_ctx in rt_mutex_init_waiter().

With this patch, the ABBA and the deep chain both get EDEADLK. The
futex_lock_pi_inherit selftest added later in this series found this.
Its deadlock and max_lock_depth cases cover it.

Fixes: 6467822b8cc9 ("locking/rtmutex: Prevent spurious EDEADLK return caused by ww_mutexes")
Cc: stable@vger.kernel.org
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 kernel/locking/rtmutex_common.h | 1 +
 1 file changed, 1 insertion(+)

diff --git a/kernel/locking/rtmutex_common.h b/kernel/locking/rtmutex_common.h
index c38b7bdea7b3..1f56d40c3e66 100644
--- a/kernel/locking/rtmutex_common.h
+++ b/kernel/locking/rtmutex_common.h
@@ -218,6 +218,7 @@ static inline void rt_mutex_init_waiter(struct rt_mutex_waiter *waiter)
 	RB_CLEAR_NODE(&waiter->tree.entry);
 	waiter->wake_state = TASK_NORMAL;
 	waiter->task = NULL;
+	waiter->ww_ctx = NULL;
 }
 
 static inline void rt_mutex_init_rtlock_waiter(struct rt_mutex_waiter *waiter)
-- 
2.47.3

[PATCH v2 3/5] locking/rtmutex: Clone the sort keys in rt_mutex_enqueue_pi()

[Mathieu Desnoyers]

An rt_mutex waiter has two copies of its sort keys. waiter->tree sorts
the waiters of its lock. waiter->pi_tree sorts the pi_waiters of the
lock owner. Only the top waiter of each lock is in pi_waiters.

When the priority of a waiter changes, the chain walk updates
waiter->tree. It copies waiter->tree to waiter->pi_tree for the top
waiter only. A waiter that is not the top waiter keeps its old pi_tree
keys.

Such a waiter can become the top waiter later. remove_waiter() does this
when the top waiter leaves. try_to_take_rt_mutex() does it when the lock
changes owner. Both put the new top waiter in pi_waiters without a new
copy. So pi_waiters sorts it by a priority it no longer has. The owner
then inherits from the wrong waiter, at that waiter's current priority.

In this example, O is the owner, a SCHED_OTHER task. L1 and L2 are two
rt_mutexes. W1, W2 and W3 are waiters. Their SCHED_FIFO priority is
under their name. T is any other task. It changes the priority of W2:

  T                         O                W1                            W2           W3
                                             FIFO 80                       FIFO 70      FIFO 50

                            locks L1, L2
                                                                                        blocks on L2
                                             blocks on L1 (timed)
                                                                           blocks on L1
  sched_setscheduler(W2)
    W2 now at FIFO 10
    rt_mutex_adjust_pi(W2)
      W2->tree: FIFO 10
      W2 not top: no copy
      W2->pi_tree: FIFO 70
                                             <timeout>
                                             remove_waiter()
                                               rt_mutex_enqueue_pi(O, W2)
                                                 W2 sorted as FIFO 70,
                                                 ahead of W3
                                               rt_mutex_adjust_prio(O)
                                                 O inherits W2's FIFO 10
                            runs at FIFO 10                                             still waits

The owner runs at SCHED_FIFO 10 while a SCHED_FIFO 50 task waits for
it. This needs no race. Each step can come long after the one before.

Fix this by copying the keys in rt_mutex_enqueue_pi(). All callers hold
the wait_lock and the owner's pi_lock, as waiter_clone_prio() requires.
Remove the three copies the callers made.

With this patch, the owner runs at SCHED_FIFO 50. The
futex_lock_pi_inherit selftest added later in this series tests this
case (promoted_waiter).

Fixes: f7853c342418 ("locking/rtmutex: Fix task->pi_waiters integrity")
Cc: stable@vger.kernel.org
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 kernel/locking/rtmutex.c | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
index 323973be2074..975efa1d864c 100644
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -517,6 +517,8 @@ rt_mutex_enqueue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
 {
 	lockdep_assert_held(&task->pi_lock);
 
+	/* The tree keys can change while @waiter is not in pi_waiters. */
+	waiter_clone_prio(waiter, task);
 	rb_add_cached(&waiter->pi_tree.entry, &task->pi_waiters, __pi_waiter_less);
 }
 
@@ -1005,7 +1007,6 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,
 		 * and adjust the priority of the owner.
 		 */
 		rt_mutex_dequeue_pi(task, prerequeue_top_waiter);
-		waiter_clone_prio(waiter, task);
 		rt_mutex_enqueue_pi(task, waiter);
 		rt_mutex_adjust_prio(lock, task);
 
@@ -1022,7 +1023,6 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,
 		 */
 		rt_mutex_dequeue_pi(task, waiter);
 		waiter = rt_mutex_top_waiter(lock);
-		waiter_clone_prio(waiter, task);
 		rt_mutex_enqueue_pi(task, waiter);
 		rt_mutex_adjust_prio(lock, task);
 	} else {
@@ -1243,7 +1243,6 @@ static int __sched task_blocks_on_rt_mutex(struct rt_mutex_base *lock,
 	waiter->task = task;
 	waiter->lock = lock;
 	waiter_update_prio(waiter, task);
-	waiter_clone_prio(waiter, task);
 
 	/* Get the top priority waiter on the lock */
 	if (rt_mutex_has_waiters(lock))
-- 
2.47.3

[PATCH v2 4/5] selftests/futex: Test priority inheritance on PI futexes

[Mathieu Desnoyers]

The PI futex selftests check what FUTEX_LOCK_PI returns. In these tests,
the owner always sleeps. No test checks the priority an owner runs at.
No test waits behind an owner that keeps running.

Add futex_lock_pi_inherit, with nine cases:
- The priority each owner runs at, read from /proc. It must follow the
  waiters as they block, time out, get a signal or change priority. This
  is also checked along a chain of owners, and when a waiter becomes the
  top waiter of its lock.
- A lock cycle, and a chain one deeper than max_lock_depth, must get
  EDEADLK.
- A 1ms timeout and a signal behind an owner spinning in userspace. On
  average, each must end the wait at most 5ms late.

The priority cases need CAP_SYS_NICE, and skip without it.

On v7.4-rc1, in 8-CPU VMs, these cases fail:
- promoted_waiter. "locking/rtmutex: Clone the sort keys in
  rt_mutex_enqueue_pi()" fixes it.
- timeout_owner_running and signal_owner_running. "locking/rtmutex: Stop
  spinning on the owner when the waiter is woken" fixes them. With
  PREEMPT_RT, signal_owner_running fails in one VM of two.
- With PREEMPT_RT and CONFIG_DEBUG_RT_MUTEXES, deadlock and
  max_lock_depth. "locking/rtmutex: Initialize the ww_mutex context of a
  waiter" fixes them.

With the whole series, the nine cases pass, with and without PREEMPT_RT.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 .../selftests/futex/functional/.gitignore     |   1 +
 .../selftests/futex/functional/Makefile       |   3 +-
 .../futex/functional/futex_lock_pi_inherit.c  | 773 ++++++++++++++++++
 .../testing/selftests/futex/functional/run.sh |   3 +
 4 files changed, 779 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/futex/functional/futex_lock_pi_inherit.c

diff --git a/tools/testing/selftests/futex/functional/.gitignore b/tools/testing/selftests/futex/functional/.gitignore
index 7c39d10b38e4..fb5bfd1387da 100644
--- a/tools/testing/selftests/futex/functional/.gitignore
+++ b/tools/testing/selftests/futex/functional/.gitignore
@@ -1,5 +1,6 @@
 # SPDX-License-Identifier: GPL-2.0-only
 futex_lock_pi_exiting
+futex_lock_pi_inherit
 futex_numa_mpol
 futex_priv_hash
 futex_requeue
diff --git a/tools/testing/selftests/futex/functional/Makefile b/tools/testing/selftests/futex/functional/Makefile
index a03bd5acba50..f32a05fc46d6 100644
--- a/tools/testing/selftests/futex/functional/Makefile
+++ b/tools/testing/selftests/futex/functional/Makefile
@@ -28,7 +28,8 @@ TEST_GEN_PROGS := \
 	futex_waitv \
 	futex_numa \
 	robust_list \
-	futex_lock_pi_exiting
+	futex_lock_pi_exiting \
+	futex_lock_pi_inherit
 
 TEST_PROGS := run.sh
 
diff --git a/tools/testing/selftests/futex/functional/futex_lock_pi_inherit.c b/tools/testing/selftests/futex/functional/futex_lock_pi_inherit.c
new file mode 100644
index 000000000000..37aa4436c124
--- /dev/null
+++ b/tools/testing/selftests/futex/functional/futex_lock_pi_inherit.c
@@ -0,0 +1,773 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * futex_lock_pi_inherit.c
+ *
+ * Test priority inheritance on PI futexes. The other PI futex tests check
+ * what FUTEX_LOCK_PI returns. These tests check three other things:
+ *
+ * - The priority each owner runs at. A waiter blocks, times out, gets a
+ *   signal or changes its priority. The owner's priority must follow.
+ *   This is also checked along a chain of owners, and when a waiter
+ *   becomes the top waiter of its lock.
+ * - FUTEX_LOCK_PI refuses a lock cycle, and a chain deeper than
+ *   max_lock_depth, with EDEADLK.
+ * - A timeout or a signal still ends a wait in time when the owner keeps
+ *   running in userspace. The top waiter then spins in the kernel.
+ *
+ * The priority is read from /proc as prio - 100. That is 20 for
+ * SCHED_OTHER at nice 0, and -1 - n for SCHED_FIFO n.
+ *
+ * Requirements:
+ * - the priority tests need CAP_SYS_NICE for SCHED_FIFO, and skip
+ *   without it;
+ * - the depth test starts max_lock_depth + 2 threads, 1026 by default;
+ * - the running-owner tests need two CPUs, and three for the signal.
+ */
+
+#define _GNU_SOURCE
+
+#include <errno.h>
+#include <fcntl.h>
+#include <pthread.h>
+#include <sched.h>
+#include <signal.h>
+#include <stdatomic.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <unistd.h>
+#include <sys/syscall.h>
+
+#include "futextest.h"
+#include "kselftest_harness.h"
+
+#define NSEC_PER_USEC	1000ULL
+#define NSEC_PER_MSEC	1000000ULL
+#define NSEC_PER_SEC	1000000000ULL
+
+#define PRIO_OTHER	20
+#define PRIO_FIFO(n)	(-1 - (n))
+
+static pid_t sys_gettid(void)
+{
+	return syscall(SYS_gettid);
+}
+
+static uint64_t now_ns(void)
+{
+	struct timespec ts;
+
+	clock_gettime(CLOCK_MONOTONIC, &ts);
+	return ts.tv_sec * NSEC_PER_SEC + ts.tv_nsec;
+}
+
+/* An absolute CLOCK_REALTIME timeout @ns from now, for FUTEX_LOCK_PI. */
+static struct timespec abs_timeout(uint64_t ns)
+{
+	struct timespec ts;
+
+	clock_gettime(CLOCK_REALTIME, &ts);
+	ts.tv_sec += ns / NSEC_PER_SEC;
+	ts.tv_nsec += ns % NSEC_PER_SEC;
+	if (ts.tv_nsec >= (long)NSEC_PER_SEC) {
+		ts.tv_nsec -= NSEC_PER_SEC;
+		ts.tv_sec++;
+	}
+	return ts;
+}
+
+/*
+ * Return field @field of the stat line @buf, or -1000 on error. Fields are
+ * numbered from 1, as in proc(5). If @state is not NULL, store the state
+ * field in it.
+ */
+static int stat_field(char *buf, int field, char *state)
+{
+	char *p;
+	int i;
+
+	p = strrchr(buf, ')');
+	if (!p || !p[1] || !p[2])
+		return -1000;
+	if (state)
+		*state = p[2];
+	for (i = 2; p && i < field; i++)
+		p = strchr(p + 1, ' ');
+	return p ? atoi(p + 1) : -1000;
+}
+
+/* Field @field of /proc/self/task/@tid/stat, or -1000 on error. */
+static int task_stat(pid_t tid, int field, char *state)
+{
+	char path[64], buf[1024];
+	ssize_t n;
+	int fd;
+
+	snprintf(path, sizeof(path), "/proc/self/task/%d/stat", tid);
+	fd = open(path, O_RDONLY);
+	if (fd < 0)
+		return -1000;
+	n = read(fd, buf, sizeof(buf) - 1);
+	close(fd);
+	if (n <= 0)
+		return -1000;
+	buf[n] = '\0';
+	return stat_field(buf, field, state);
+}
+
+/* The priority @tid runs at. */
+static int task_prio(pid_t tid)
+{
+	return task_stat(tid, 18, NULL);
+}
+
+/* Wait up to 2s for @tid to run at @prio. Return the last priority read. */
+static int wait_prio(pid_t tid, int prio)
+{
+	uint64_t end = now_ns() + 2 * NSEC_PER_SEC;
+	int p;
+
+	while ((p = task_prio(tid)) != prio && now_ns() < end)
+		usleep(1000);
+	return p;
+}
+
+static int set_fifo(pid_t tid, int prio)
+{
+	struct sched_param sp = { .sched_priority = prio };
+
+	return prio ? sched_setscheduler(tid, SCHED_FIFO, &sp) :
+		      sched_setscheduler(tid, SCHED_OTHER, &sp);
+}
+
+/* Can this thread use SCHED_FIFO 80, the highest priority the tests use? */
+static bool can_fifo(void)
+{
+	if (set_fifo(0, 80))
+		return false;
+	set_fifo(0, 0);
+	return true;
+}
+
+/*
+ * A test thread. It takes the locks in @hold, then blocks on @wait. Without
+ * @wait, it sleeps until release_all(). A @timeout_ns other than 0 limits
+ * the wait on @wait. The thread sets @tid when it starts, and @blocking
+ * just before it blocks.
+ */
+struct pi_thread {
+	pthread_t thread;
+	futex_t *hold[2];
+	futex_t *wait;
+	uint64_t timeout_ns;
+	int fifo;
+	atomic_int tid;
+	atomic_int blocking;
+	atomic_int done;
+	int ret;		/* 0, or the errno of the lock of @wait */
+	int err;		/* 0, or the errno of the first failed call */
+};
+
+static futex_t release_word;
+
+static void release_all(void)
+{
+	release_word = 1;
+	futex_wake(&release_word, INT32_MAX, FUTEX_PRIVATE_FLAG);
+}
+
+/* Record errno @err for @t, unless an earlier call of @t failed. */
+static void thread_fail(struct pi_thread *t, int err)
+{
+	if (!t->err)
+		t->err = err ? err : EINVAL;
+}
+
+static void *pi_thread_fn(void *arg)
+{
+	struct pi_thread *t = arg;
+	int held = 0;
+
+	atomic_store(&t->tid, sys_gettid());
+	if (t->fifo && set_fifo(0, t->fifo)) {
+		thread_fail(t, errno);
+		goto out;
+	}
+	for (; held < 2 && t->hold[held]; held++) {
+		if (futex_lock_pi(t->hold[held], NULL, 0, FUTEX_PRIVATE_FLAG)) {
+			thread_fail(t, errno);
+			goto unlock;
+		}
+	}
+	atomic_store_explicit(&t->blocking, 1, memory_order_release);
+	if (t->wait) {
+		struct timespec ts = abs_timeout(t->timeout_ns);
+
+		t->ret = futex_lock_pi(t->wait, t->timeout_ns ? &ts : NULL, 0,
+				       FUTEX_PRIVATE_FLAG) ? errno : 0;
+		if (!t->ret && futex_unlock_pi(t->wait, FUTEX_PRIVATE_FLAG))
+			thread_fail(t, errno);
+	} else {
+		while (!release_word) {
+			if (futex_wait(&release_word, 0, NULL, FUTEX_PRIVATE_FLAG) &&
+			    errno != EAGAIN && errno != EINTR) {
+				thread_fail(t, errno);
+				break;
+			}
+		}
+	}
+unlock:
+	while (held--)
+		if (futex_unlock_pi(t->hold[held], FUTEX_PRIVATE_FLAG))
+			thread_fail(t, errno);
+out:
+	atomic_store_explicit(&t->done, 1, memory_order_release);
+	return NULL;
+}
+
+/*
+ * Start @t and wait until it sleeps where it blocks. Return false if it
+ * could not be created, if it failed, or if it did not block within 2s.
+ * Unless it could not be created, the caller must still join it.
+ */
+static bool start(struct pi_thread *t)
+{
+	uint64_t end = now_ns() + 2 * NSEC_PER_SEC;
+	pthread_attr_t attr;
+	char state = 0;
+	int err;
+
+	pthread_attr_init(&attr);
+	pthread_attr_setstacksize(&attr, 64 * 1024);
+	err = pthread_create(&t->thread, &attr, pi_thread_fn, t);
+	pthread_attr_destroy(&attr);
+	if (err) {
+		t->thread = pthread_self();
+		t->err = err;
+		atomic_store(&t->done, 1);
+		ksft_print_msg("pthread_create: %s\n", strerror(err));
+		return false;
+	}
+	while (now_ns() < end) {
+		if (atomic_load_explicit(&t->done, memory_order_acquire)) {
+			ksft_print_msg("a thread failed before blocking: %s\n",
+				       strerror(t->err ? t->err : t->ret));
+			return false;
+		}
+		if (atomic_load_explicit(&t->blocking, memory_order_acquire) &&
+		    task_stat(atomic_load(&t->tid), 3, &state) != -1000 && state == 'S')
+			return true;
+		usleep(1000);
+	}
+	ksft_print_msg("a thread did not block within 2s\n");
+	return false;
+}
+
+static void pi_thread_init(struct pi_thread *t, futex_t *hold0, futex_t *hold1,
+			   futex_t *wait, int fifo, uint64_t timeout_ns)
+{
+	memset(t, 0, sizeof(*t));
+	t->hold[0] = hold0;
+	t->hold[1] = hold1;
+	t->wait = wait;
+	t->fifo = fifo;
+	t->timeout_ns = timeout_ns;
+}
+
+/*
+ * Join @t. Return the error of pthread_join(). Without one, return the first
+ * error of @t, or 0.
+ */
+static int join(struct pi_thread *t)
+{
+	int err = 0;
+
+	if (!pthread_equal(t->thread, pthread_self()))
+		err = pthread_join(t->thread, NULL);
+	return err ? err : t->err;
+}
+
+/* A SCHED_FIFO 50 waiter boosts the owner until the waiter times out. */
+TEST(boost_timeout)
+{
+	futex_t l = FUTEX_INITIALIZER;
+	struct pi_thread o, w;
+
+	if (!can_fifo())
+		SKIP(return, "SCHED_FIFO not permitted: %s", strerror(errno));
+	release_word = 0;
+	pi_thread_init(&o, &l, NULL, NULL, 0, 0);
+	ASSERT_TRUE(start(&o));
+	pi_thread_init(&w, NULL, NULL, &l, 50, NSEC_PER_SEC);
+	ASSERT_TRUE(start(&w));
+	EXPECT_EQ(wait_prio(o.tid, PRIO_FIFO(50)), PRIO_FIFO(50));
+	EXPECT_EQ(join(&w), 0);
+	EXPECT_EQ(w.ret, ETIMEDOUT);
+	EXPECT_EQ(wait_prio(o.tid, PRIO_OTHER), PRIO_OTHER);
+	release_all();
+	EXPECT_EQ(join(&o), 0);
+}
+
+/* The owner's priority follows each priority change of a blocked waiter. */
+TEST(waiter_priority_change)
+{
+	futex_t l = FUTEX_INITIALIZER;
+	struct pi_thread o, w;
+
+	if (!can_fifo())
+		SKIP(return, "SCHED_FIFO not permitted: %s", strerror(errno));
+	release_word = 0;
+	pi_thread_init(&o, &l, NULL, NULL, 0, 0);
+	ASSERT_TRUE(start(&o));
+	pi_thread_init(&w, NULL, NULL, &l, 50, 0);
+	ASSERT_TRUE(start(&w));
+	EXPECT_EQ(wait_prio(o.tid, PRIO_FIFO(50)), PRIO_FIFO(50));
+	ASSERT_EQ(set_fifo(w.tid, 70), 0);
+	EXPECT_EQ(task_prio(o.tid), PRIO_FIFO(70));
+	ASSERT_EQ(set_fifo(w.tid, 30), 0);
+	EXPECT_EQ(task_prio(o.tid), PRIO_FIFO(30));
+	ASSERT_EQ(set_fifo(w.tid, 0), 0);
+	EXPECT_EQ(task_prio(o.tid), PRIO_OTHER);
+	release_all();
+	EXPECT_EQ(join(&o), 0);
+	EXPECT_EQ(join(&w), 0);
+	EXPECT_EQ(w.ret, 0);
+}
+
+/*
+ * A waiter changes priority while it is not the top waiter of its lock.
+ * When it becomes the top waiter, it must be sorted by its new priority.
+ *
+ * The owner holds L1 and L2. On L1, W1 (SCHED_FIFO 80, with a timeout) is
+ * the top waiter. W2 (SCHED_FIFO 70) waits behind it. On L2, W3
+ * (SCHED_FIFO 50) waits. W2 is set to SCHED_FIFO 10. When W1 times out,
+ * W2 becomes the top waiter of L1. The owner must then run at 50, the
+ * priority of W3.
+ */
+TEST(promoted_waiter)
+{
+	futex_t l1 = FUTEX_INITIALIZER, l2 = FUTEX_INITIALIZER;
+	struct pi_thread o, w1, w2, w3;
+
+	if (!can_fifo())
+		SKIP(return, "SCHED_FIFO not permitted: %s", strerror(errno));
+	release_word = 0;
+	pi_thread_init(&o, &l1, &l2, NULL, 0, 0);
+	ASSERT_TRUE(start(&o));
+	pi_thread_init(&w3, NULL, NULL, &l2, 50, 0);
+	ASSERT_TRUE(start(&w3));
+	pi_thread_init(&w1, NULL, NULL, &l1, 80, NSEC_PER_SEC);
+	ASSERT_TRUE(start(&w1));
+	pi_thread_init(&w2, NULL, NULL, &l1, 70, 0);
+	ASSERT_TRUE(start(&w2));
+	EXPECT_EQ(wait_prio(o.tid, PRIO_FIFO(80)), PRIO_FIFO(80));
+	ASSERT_EQ(set_fifo(w2.tid, 10), 0);
+	EXPECT_EQ(task_prio(o.tid), PRIO_FIFO(80));
+	EXPECT_EQ(join(&w1), 0);
+	EXPECT_EQ(w1.ret, ETIMEDOUT);
+	EXPECT_EQ(wait_prio(o.tid, PRIO_FIFO(50)), PRIO_FIFO(50))
+		TH_LOG("the owner inherits from the wrong waiter");
+	release_all();
+	EXPECT_EQ(join(&o), 0);
+	EXPECT_EQ(join(&w2), 0);
+	EXPECT_EQ(join(&w3), 0);
+}
+
+/*
+ * The signal handler of W reads the stat file of T1. It only calls open(),
+ * read() and close(), which are async-signal-safe.
+ */
+static char chain_path[64], chain_buf[1024];
+static _Atomic int chain_read = -1;
+
+static void chain_handler(int sig)
+{
+	int fd = open(chain_path, O_RDONLY);
+	ssize_t n = fd < 0 ? 0 : read(fd, chain_buf, sizeof(chain_buf) - 1);
+
+	if (fd >= 0)
+		close(fd);
+	atomic_store_explicit(&chain_read, n > 0 ? n : 0, memory_order_release);
+}
+
+/*
+ * A chain of owners. T1 holds L1. T2 holds L2 and blocks on L1. W
+ * (SCHED_FIFO 60) blocks on L2. While W waits, T1 and T2 run at 60.
+ *
+ * With @timeout, W times out, and T1 and T2 go back to SCHED_OTHER.
+ * Without it, T2 is set to SCHED_FIFO 70 and back, and T1 follows. Then W
+ * gets a signal. While W handles it, W is out of the chain, and T1 runs
+ * at SCHED_OTHER.
+ */
+static void chain(struct __test_metadata *_metadata, bool timeout)
+{
+	futex_t l1 = FUTEX_INITIALIZER, l2 = FUTEX_INITIALIZER;
+	struct pi_thread t1, t2, w;
+	int n;
+
+	release_word = 0;
+	pi_thread_init(&t1, &l1, NULL, NULL, 0, 0);
+	ASSERT_TRUE(start(&t1));
+	pi_thread_init(&t2, &l2, NULL, &l1, 0, 0);
+	ASSERT_TRUE(start(&t2));
+	pi_thread_init(&w, NULL, NULL, &l2, 60, timeout ? NSEC_PER_SEC : 0);
+	ASSERT_TRUE(start(&w));
+	EXPECT_EQ(wait_prio(t1.tid, PRIO_FIFO(60)), PRIO_FIFO(60));
+	EXPECT_EQ(task_prio(t2.tid), PRIO_FIFO(60));
+	if (timeout) {
+		EXPECT_EQ(join(&w), 0);
+		EXPECT_EQ(w.ret, ETIMEDOUT);
+		EXPECT_EQ(wait_prio(t1.tid, PRIO_OTHER), PRIO_OTHER);
+		EXPECT_EQ(task_prio(t2.tid), PRIO_OTHER);
+	} else {
+		/* T2 above the priority of W, then below it again. */
+		ASSERT_EQ(set_fifo(t2.tid, 70), 0);
+		EXPECT_EQ(task_prio(t1.tid), PRIO_FIFO(70));
+		ASSERT_EQ(set_fifo(t2.tid, 0), 0);
+		EXPECT_EQ(task_prio(t1.tid), PRIO_FIFO(60));
+		/* W leaves the chain in its signal handler, then comes back. */
+		snprintf(chain_path, sizeof(chain_path), "/proc/self/task/%d/stat", t1.tid);
+		struct sigaction sa = { .sa_handler = chain_handler };
+		uint64_t end = now_ns() + 2 * NSEC_PER_SEC;
+
+		atomic_store(&chain_read, -1);
+		ASSERT_EQ(sigaction(SIGUSR1, &sa, NULL), 0);
+		ASSERT_EQ(pthread_kill(w.thread, SIGUSR1), 0);
+		while ((n = atomic_load_explicit(&chain_read, memory_order_acquire)) < 0 &&
+		       now_ns() < end)
+			usleep(1000);
+		ASSERT_GE(n, 0) TH_LOG("the signal was not handled within 2s");
+		chain_buf[n] = '\0';
+		EXPECT_EQ(stat_field(chain_buf, 18, NULL), PRIO_OTHER);
+		EXPECT_EQ(wait_prio(t1.tid, PRIO_FIFO(60)), PRIO_FIFO(60));
+		release_all();
+		EXPECT_EQ(join(&w), 0);
+		EXPECT_EQ(w.ret, 0);
+	}
+	release_all();
+	EXPECT_EQ(join(&t1), 0);
+	EXPECT_EQ(join(&t2), 0);
+}
+
+TEST(chain_timeout)
+{
+	if (!can_fifo())
+		SKIP(return, "SCHED_FIFO not permitted: %s", strerror(errno));
+	chain(_metadata, true);
+}
+
+TEST(chain_priority_change_and_signal)
+{
+	if (!can_fifo())
+		SKIP(return, "SCHED_FIFO not permitted: %s", strerror(errno));
+	chain(_metadata, false);
+}
+
+/* Two owners block on each other's lock. The second one gets EDEADLK. */
+TEST(deadlock)
+{
+	futex_t l1 = FUTEX_INITIALIZER, l2 = FUTEX_INITIALIZER;
+	struct pi_thread a;
+	int ret;
+
+	struct timespec ts;
+
+	release_word = 0;
+	pi_thread_init(&a, &l1, NULL, &l2, 0, 2 * NSEC_PER_SEC);
+	ASSERT_EQ(futex_lock_pi(&l2, NULL, 0, FUTEX_PRIVATE_FLAG), 0);
+	ASSERT_TRUE(start(&a));
+	ts = abs_timeout(NSEC_PER_SEC);
+	ret = futex_lock_pi(&l1, &ts, 0, FUTEX_PRIVATE_FLAG) ? errno : 0;
+	if (!ret)
+		EXPECT_EQ(futex_unlock_pi(&l1, FUTEX_PRIVATE_FLAG), 0);
+	EXPECT_EQ(futex_unlock_pi(&l2, FUTEX_PRIVATE_FLAG), 0);
+	EXPECT_EQ(join(&a), 0);
+	EXPECT_EQ(ret, EDEADLK)
+		TH_LOG("the second of an ABBA got %s, the first %s",
+		       strerror(ret), strerror(a.ret));
+	EXPECT_EQ(a.ret, 0);
+}
+
+/*
+ * A chain one deeper than max_lock_depth. depth_t[0] holds depth_l[0].
+ * Each depth_t[i] holds depth_l[i] and blocks on depth_l[i - 1].
+ *
+ * The chain walk counts the blocked owners it finds. When depth_t[i]
+ * blocks, it finds i - 1 of them. So the threads up to depth_t[depth + 1]
+ * are admitted. This thread then blocks on depth_l[depth + 1]. It would
+ * find depth + 1 blocked owners, so it gets EDEADLK.
+ */
+#define MAX_DEPTH	4096
+static struct pi_thread depth_t[MAX_DEPTH + 2];
+static futex_t depth_l[MAX_DEPTH + 2];
+
+TEST(max_lock_depth)
+{
+	int depth = 0, i, n, blocked, ret = -1;
+	bool created = true;
+	struct timespec ts;
+	char buf[32] = "";
+	ssize_t len;
+	int fd;
+
+	fd = open("/proc/sys/kernel/max_lock_depth", O_RDONLY);
+	len = fd < 0 ? -1 : read(fd, buf, sizeof(buf) - 1);
+	if (fd >= 0)
+		close(fd);
+	if (len > 0)
+		depth = atoi(buf);
+	if (depth <= 0 || depth > MAX_DEPTH)
+		SKIP(return, "max_lock_depth %s not in 1 to %d", buf, MAX_DEPTH);
+	release_word = 0;
+	for (i = 0; i < depth + 2; i++) {
+		depth_l[i] = FUTEX_INITIALIZER;
+		pi_thread_init(&depth_t[i], &depth_l[i], NULL, i ? &depth_l[i - 1] : NULL, 0, 0);
+		if (!start(&depth_t[i]))
+			break;
+	}
+	blocked = n = i;
+	/* A thread that was created but did not block must still be joined. */
+	if (i < depth + 2) {
+		if (pthread_equal(depth_t[i].thread, pthread_self()))
+			created = false;
+		else
+			n++;
+	}
+	if (blocked == depth + 2) {
+		ts = abs_timeout(NSEC_PER_SEC);
+		ret = futex_lock_pi(&depth_l[blocked - 1], &ts, 0, FUTEX_PRIVATE_FLAG) ? errno : 0;
+		if (!ret)
+			EXPECT_EQ(futex_unlock_pi(&depth_l[blocked - 1], FUTEX_PRIVATE_FLAG), 0);
+	}
+	release_all();
+	for (i = 0; i < n; i++)
+		EXPECT_EQ(join(&depth_t[i]), 0);
+	if (!created)
+		SKIP(return, "%d threads of the chain could not be created", depth + 2);
+	ASSERT_EQ(blocked, depth + 2)
+		TH_LOG("thread %d of the chain did not block", blocked);
+	EXPECT_EQ(ret, EDEADLK);
+	for (i = 1; i < blocked; i++)
+		EXPECT_EQ(depth_t[i].ret, 0);
+}
+
+/*
+ * The owner of a PI futex spins in userspace on one CPU. Its waiter runs
+ * on another CPU, and spins in the kernel while the owner runs. A timeout
+ * or a signal must still end the wait in time.
+ */
+static atomic_int owner_stop, owner_holds, owner_err;
+static futex_t running_lock;
+
+/* Pin the calling thread on @cpu. Return 0 or an errno. */
+static int pin(int cpu)
+{
+	cpu_set_t set;
+
+	CPU_ZERO(&set);
+	CPU_SET(cpu, &set);
+	return sched_setaffinity(0, sizeof(set), &set) ? errno : 0;
+}
+
+static void *running_owner(void *arg)
+{
+	int err = pin((long)arg);
+
+	if (!err && futex_lock_pi(&running_lock, NULL, 0, FUTEX_PRIVATE_FLAG))
+		err = errno;
+	if (err) {
+		atomic_store_explicit(&owner_err, err, memory_order_release);
+		return NULL;
+	}
+	atomic_store_explicit(&owner_holds, 1, memory_order_release);
+	while (!atomic_load_explicit(&owner_stop, memory_order_acquire))
+		;
+	if (futex_unlock_pi(&running_lock, FUTEX_PRIVATE_FLAG))
+		atomic_store_explicit(&owner_err, errno, memory_order_release);
+	return NULL;
+}
+
+/* Store in @cpu @n CPUs this thread may run on. False if there are fewer. */
+static bool pick_cpus(int *cpu, int n)
+{
+	cpu_set_t set;
+	int c, i = 0;
+
+	if (sched_getaffinity(0, sizeof(set), &set))
+		return false;
+	for (c = 0; c < CPU_SETSIZE && i < n; c++)
+		if (CPU_ISSET(c, &set))
+			cpu[i++] = c;
+	return i == n;
+}
+
+/*
+ * Start the owner thread @o on @cpu. It takes running_lock, then spins.
+ * Return false on a failure.
+ */
+static bool start_running_owner(int cpu, pthread_t *o)
+{
+	uint64_t end = now_ns() + 2 * NSEC_PER_SEC;
+	int err;
+
+	running_lock = FUTEX_INITIALIZER;
+	atomic_store(&owner_stop, 0);
+	atomic_store(&owner_holds, 0);
+	atomic_store(&owner_err, 0);
+	err = pthread_create(o, NULL, running_owner, (void *)(long)cpu);
+	if (err) {
+		ksft_print_msg("pthread_create: %s\n", strerror(err));
+		return false;
+	}
+	while (!atomic_load_explicit(&owner_holds, memory_order_acquire) &&
+	       !atomic_load_explicit(&owner_err, memory_order_acquire) && now_ns() < end)
+		usleep(100);
+	if (atomic_load_explicit(&owner_holds, memory_order_acquire))
+		return true;
+	atomic_store_explicit(&owner_stop, 1, memory_order_release);
+	err = pthread_join(*o, NULL);
+	if (err)
+		ksft_print_msg("pthread_join: %s\n", strerror(err));
+	err = atomic_load(&owner_err);
+	ksft_print_msg("the owner did not take the lock: %s\n", err ? strerror(err) : "timeout");
+	return false;
+}
+
+/*
+ * Stop the owner. Return the error of pthread_join(). Without one, return
+ * the error of the owner, or 0.
+ */
+static int stop_running_owner(pthread_t o)
+{
+	int err;
+
+	atomic_store_explicit(&owner_stop, 1, memory_order_release);
+	err = pthread_join(o, NULL);
+	return err ? err : atomic_load(&owner_err);
+}
+
+/*
+ * 20 waits with a 1ms timeout behind a running owner. On average, a wait
+ * must end at most 5ms late. A kernel that stops the spin on the wakeup
+ * is tens of microseconds late. A kernel that keeps spinning is late
+ * until something else needs one of the two CPUs.
+ */
+TEST(timeout_owner_running)
+{
+	uint64_t late = 0, t;
+	int cpu[2], i, ret;
+	pthread_t o;
+
+	if (!pick_cpus(cpu, 2))
+		SKIP(return, "two CPUs needed");
+	ASSERT_EQ(pin(cpu[1]), 0);
+	ASSERT_TRUE(start_running_owner(cpu[0], &o));
+	for (i = 0; i < 20; i++) {
+		struct timespec ts = abs_timeout(NSEC_PER_MSEC);
+
+		t = now_ns();
+		ret = futex_lock_pi(&running_lock, &ts, 0, FUTEX_PRIVATE_FLAG) ? errno : 0;
+		t = now_ns() - t;
+		EXPECT_EQ(ret, ETIMEDOUT);
+		late += t > NSEC_PER_MSEC ? t - NSEC_PER_MSEC : 0;
+	}
+	EXPECT_EQ(stop_running_owner(o), 0);
+	TH_LOG("a timeout of 1ms ends %llu us late on average",
+	       (unsigned long long)(late / 20 / NSEC_PER_USEC));
+	EXPECT_LT(late / 20, 5 * NSEC_PER_MSEC);
+}
+
+static _Atomic uint64_t handled_ns;
+static atomic_int waiter_tid, waiter_ret;
+
+static void running_handler(int sig)
+{
+	atomic_store(&handled_ns, now_ns());
+}
+
+static void *running_waiter(void *arg)
+{
+	int ret = pin((long)arg);
+
+	atomic_store(&waiter_tid, sys_gettid());
+	if (!ret)
+		ret = futex_lock_pi(&running_lock, NULL, 0, FUTEX_PRIVATE_FLAG) ? errno : 0;
+	if (!ret && futex_unlock_pi(&running_lock, FUTEX_PRIVATE_FLAG))
+		ret = errno;
+	atomic_store(&waiter_ret, ret);
+	return NULL;
+}
+
+/*
+ * Wait up to 2s for the waiter to block on running_lock. The futex word
+ * must show waiters, and the state of the waiter must be S.
+ */
+static bool waiter_blocked(void)
+{
+	uint64_t end = now_ns() + 2 * NSEC_PER_SEC;
+	char state = 0;
+	pid_t tid;
+
+	while (now_ns() < end) {
+		tid = atomic_load(&waiter_tid);
+		if (tid && (running_lock & FUTEX_WAITERS) &&
+		    task_stat(tid, 3, &state) != -1000 && state == 'S')
+			return true;
+		usleep(100);
+	}
+	return false;
+}
+
+/*
+ * 10 signals to a waiter behind a running owner. Each one is sent from a
+ * third CPU, once the waiter is blocked on the lock. On average, a signal
+ * must be handled within 5ms, as for the timeouts above. A signal not
+ * handled within 2s counts as 2s.
+ */
+TEST(signal_owner_running)
+{
+	struct sigaction sa = { .sa_handler = running_handler };
+	uint64_t total = 0, t, end;
+	int cpu[3], i, err, n = 0;
+	bool blocked = true;
+	pthread_t o, w;
+
+	if (!pick_cpus(cpu, 3))
+		SKIP(return, "three CPUs needed");
+	ASSERT_EQ(sigaction(SIGUSR1, &sa, NULL), 0);
+	ASSERT_EQ(pin(cpu[2]), 0);
+	ASSERT_TRUE(start_running_owner(cpu[0], &o));
+	atomic_store(&waiter_tid, 0);
+	atomic_store(&waiter_ret, -1);
+	err = pthread_create(&w, NULL, running_waiter, (void *)(long)cpu[1]);
+	if (err) {
+		stop_running_owner(o);
+		ASSERT_EQ(err, 0) TH_LOG("pthread_create: %s", strerror(err));
+	}
+	for (i = 0; i < 10; i++) {
+		if (!waiter_blocked()) {
+			blocked = false;
+			break;
+		}
+		atomic_store(&handled_ns, 0);
+		t = now_ns();
+		EXPECT_EQ(pthread_kill(w, SIGUSR1), 0);
+		end = t + 2 * NSEC_PER_SEC;
+		while (!atomic_load(&handled_ns) && now_ns() < end)
+			usleep(50);
+		total += (atomic_load(&handled_ns) ? atomic_load(&handled_ns) : end) - t;
+		n++;
+	}
+	EXPECT_EQ(stop_running_owner(o), 0);
+	EXPECT_EQ(pthread_join(w, NULL), 0);
+	EXPECT_EQ(atomic_load(&waiter_ret), 0);
+	ASSERT_TRUE(blocked) TH_LOG("the waiter did not block on the lock");
+	TH_LOG("a signal is handled after %llu us on average",
+	       (unsigned long long)(total / n / NSEC_PER_USEC));
+	EXPECT_LT(total / n, 5 * NSEC_PER_MSEC);
+}
+
+TEST_HARNESS_MAIN
diff --git a/tools/testing/selftests/futex/functional/run.sh b/tools/testing/selftests/futex/functional/run.sh
index d1a681b798bd..ed37522af5c3 100755
--- a/tools/testing/selftests/futex/functional/run.sh
+++ b/tools/testing/selftests/futex/functional/run.sh
@@ -54,3 +54,6 @@ echo
 
 echo
 ./futex_lock_pi_exiting
+
+echo
+./futex_lock_pi_inherit
-- 
2.47.3

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

[Mathieu Desnoyers]

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