[RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution.

[RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution.

[Suleiman Souhlal]

Hello,

This patch series adds a new type of PI futexes, PI Next Generation,
or PING (name coined by Steven Rostedt) (but other name suggestions
are welcome!), that differs from classic PI futexes in that they can
be stolen from the top waiter, and use Proxy Execution instead of
rtmutexes internally. 

The reason to allow the futexes to be stolen is that with classic PI
futex's strict handoff to the top waiter, new contending lockers are
now forced to wait in queue, which means that any locking operation
now becomes a scheduling event. With stealing, a contending locker has
the chance of taking the lock without blocking. The longer wait time
of blocked tasks can be mitigated by forcing the lock to be handed
off to them in a way that can't be stolen, when they've been stolen
from too much, to ensure they don't get starved.

The use of Proxy Execution lets us also get Priority Inheritance for
for fair tasks, which PI futexes don't really allow.


PING futexes are used similarly to FUTEX_*_PI, where the owner is
expected to write its TID in the futex.

The main user-visible difference with regular PI futexes is that the
kernel is allowed to set the FUTEX_WAITERS bit with an empty TID.
This is to allow for a new locker to steal the lock from the top
waiter, which is supposed to improve performance in workloads that
don't need strict RT handling.
The user is also allowed to notice that the futex is unlocked but
has waiters, and steal it without going to the kernel.

An example of how they're meant to be used:
Lock:
        static __thread pid_t tid = gettid();
        uint32_t oldval = 0;
        if (atomic_compare_exchange_strong(ftx, &oldval, tid)
                return;
        oldval = FUTEX_WAITERS;
        // The user could also spin here a bit.
        if (atomic_compare_exchange_strong(ftx, &oldval,
            tid | FUTEX_WAITERS))
                return;
        if (futex(ftx, FUTEX_LOCK_PING, 0, NULL) != 0)
                err(1, "FUTEX_LOCK_PING");

Unlock:
        static __thread pid_t tid = gettid();
        uint32_t oldval = tid;
        if (atomic_compare_exchange_strong(ftx, &oldval, 0))
                return;
        if (futex(ftx, FUTEX_UNLOCK_PING, 0, NULL) != 0)
                err(1, "FUTEX_UNLOCK_PING");


Why did we opt for a new futex type instead of making PI futexes
and rtmutex use Proxy Execution?

PI futexes have strict rtmutex semantics, which while important
for RT workloads, could also potentially result in performance
penalties in workloads where maintaining those semantics isn't
as important. Since we don't want to break existing applications,
creating a new futex type seems appropriate.
Making a new futex type also lets us change the user interface a bit,
to allow for userspace stealing.

We do hope to eventually enable rtmutexes to use Proxy Execution
but the rtmutex wait_lock and pi_lock ordering is backwards for
Proxy Execution, so a potentially complicated rework might be needed
before rtmutexes can use it.
In the meantime, Proxy Execution boosting and rtmutex boosting
can continue to coexist.


Some features of PING futexes:
- Uses Proxy Execution.
- Optimistic spinning (can also be done in userspace, similarly to
  FUTEX_WAIT futexes).
- Allows for userspace stealing.
- Starvation prevention with handoff.


Some performance numbers (lock acquisition time, in nsec, lower is better):
(The numbers were kindly gathered by John on a machine with 11th Gen
Intel(R) Core(TM) i5.)
(How PING performs compared to PI and FUTEX_WAIT seems to vary a lot
based on hardware and ping_bench parameters, and the results look a
bit more impressive on my device :-), but I did not include them since
they are based on an older kernel version.)

With all fair tasks:
"ping_bench -a -w 50000 -s 1000 -t 16"

x FUTEX_PING
+ FUTEX_PI
* glibc pthread_mutex_t (using FUTEX_WAIT)
    N      Mean    Stddev     Min     25p     50p     75p     Max
x 159984  214377.3 859183.23      21   13703   15580   75343 1.15e+07
+ 159984 240690.75 23090.391  234635  237833  239962  241565 1.07e+06
Difference at 95.0% confidence
      26313.4 +/- 4211.65 [22101.8 30525.1]
      12.274363% +/- 1.9646%
      (z 12.2454 p-val 1.77893e-34 crit val 1.95996 se 2148.84)
* 159984 203941.44  14257763      17      20      21      21 1.21e+09
No difference proven at 95.0% confidence
      (z -0.292232 p-val 0.770109 crit val 1.95996 se 35710.9)

With priority inversions with a RT foreground task:
"ping_bench -t 8 -b 16 -r 1 -p -w 10000 -S 500"

x FUTEX_PING
+ FUTEX_PI
* glibc pthread_mutex_t (using FUTEX_WAIT)
    N      Mean    Stddev     Min     25p     50p     75p     Max
x 9999 615.55326 3387.2647      21      50      52      54 8.2e+04
+ 9999 701.18222 3450.3964      21      49      52      53 3.34e+04
No difference proven at 95.0% confidence
      (z 1.77087 p-val 0.0765815 crit val 1.95996 se 48.354)
* 9999 205935.36 2881211.5      24      53      54      55 1.24e+08
Difference at 95.0% confidence
      205320 +/- 56473.6 [148846 261793]
      33355.327862% +/- 9174.44%
      (z 7.1258 p-val 1.03486e-12 crit val 1.95996 se 28813.6)


The patches apply on top of Linus' HEAD.

Any feedback is welcome!


Suleiman Souhlal (12):
  sched: Abstract task_struct->blocked_on by locking primitive.
  futex: Switch PI futex to use p->pi_futex_lock instead of p->pi_lock.
  futex: Add "ping" parameter to pi_state management functions and
    export them.
  futex: Introduce stealable PI futex, FUTEX_*_PING.
  futex: Implement exit_ping_state_list().
  futex: Address aborting from futex_lock_ping() while owning
    ping_state.
  futex: Make FUTEX_*_PING use Proxy Execution.
  futex: Implement PING futex handoff.
  futex: Wake up donor in PING futex unlock.
  futex: Optimistic spinning for PING futexes.
  futex: Allow userspace stealing for PING futexes.
  tools/testing/futex: Add ping_bench, a tool for benchmarking futexes.

 include/linux/futex.h            |  22 +
 include/linux/futex_types.h      |   1 +
 include/linux/sched.h            |  53 ++-
 include/uapi/linux/futex.h       |   3 +
 init/init_task.c                 |   1 +
 kernel/fork.c                    |   3 +-
 kernel/futex/Makefile            |   2 +-
 kernel/futex/core.c              | 102 ++++-
 kernel/futex/futex.h             |  27 +-
 kernel/futex/pi.c                | 132 +++---
 kernel/futex/ping.c              | 707 +++++++++++++++++++++++++++++++
 kernel/futex/syscalls.c          |   6 +
 kernel/locking/mutex.c           |   8 +-
 kernel/sched/core.c              |  69 ++-
 kernel/sched/sched.h             |   2 +-
 tools/testing/futex/Makefile     |  13 +
 tools/testing/futex/ping_bench.c | 428 +++++++++++++++++++
 17 files changed, 1484 insertions(+), 95 deletions(-)
 create mode 100644 kernel/futex/ping.c
 create mode 100644 tools/testing/futex/Makefile
 create mode 100644 tools/testing/futex/ping_bench.c

-- 
2.55.0.1082.g2b9226bbc0-goog

[RFC PATCH 01/12] sched: Abstract task_struct->blocked_on by locking primitive.

[Suleiman Souhlal]

Abstract task_struct->blocked_on by type of locking primitive, so
that it can be used by things other than mutexes.

Signed-off-by: John Stultz <jstultz@google.com>
Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 include/linux/sched.h  | 40 +++++++++++++++++++--------
 kernel/fork.c          |  2 +-
 kernel/locking/mutex.c |  8 +++---
 kernel/sched/core.c    | 62 ++++++++++++++++++++++++++++++++++++------
 kernel/sched/sched.h   |  2 +-
 5 files changed, 89 insertions(+), 25 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 705970d07614..6edd0c7891c5 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -832,6 +832,16 @@ struct task_ipi_mask {
 struct task_ipi_mask { };
 #endif
 
+enum blocked_on_type {
+	BO_T_NONE,
+	BO_T_MUTEX,
+};
+
+struct blocked_on_lock {
+	void *lock;
+	enum blocked_on_type type;
+};
+
 struct task_struct {
 #ifdef CONFIG_THREAD_INFO_IN_TASK
 	/*
@@ -1259,7 +1269,7 @@ struct task_struct {
 	struct rt_mutex_waiter		*pi_blocked_on;
 #endif
 
-	struct mutex			*blocked_on;	/* lock we're blocked on */
+	struct blocked_on_lock		blocked_on;	/* lock we're blocked on */
 	raw_spinlock_t			blocked_lock;
 
 	/*
@@ -2221,10 +2231,15 @@ extern int __cond_resched_rwlock_write(rwlock_t *lock) __must_hold(lock);
 static inline struct mutex *__get_task_blocked_on(struct task_struct *p)
 {
 	lockdep_assert_held_once(&p->blocked_lock);
-	return p->blocked_on;
+	return p->blocked_on.lock;
 }
 
-static inline void __set_task_blocked_on(struct task_struct *p, struct mutex *m)
+/*
+ * These helpers set and clear the task blocked_on pointer, as well
+ * as setting the initial blocked_on_state, or clearing it
+ */
+static inline void __set_task_blocked_on(struct task_struct *p, void *m,
+					 enum blocked_on_type type)
 {
 	WARN_ON_ONCE(!m);
 	/* The task should only be setting itself as blocked */
@@ -2236,11 +2251,12 @@ static inline void __set_task_blocked_on(struct task_struct *p, struct mutex *m)
 	 * with a different mutex. Note, setting it to the same
 	 * lock repeatedly is ok.
 	 */
-	WARN_ON_ONCE(p->blocked_on && p->blocked_on != m);
-	p->blocked_on = m;
+	WARN_ON_ONCE(p->blocked_on.lock && p->blocked_on.lock != m);
+	p->blocked_on.lock = m;
+	p->blocked_on.type = type;
 }
 
-static inline void __clear_task_blocked_on(struct task_struct *p, struct mutex *m)
+static inline void __clear_task_blocked_on(struct task_struct *p, void *m)
 {
 	/* Currently we serialize blocked_on under the task::blocked_lock */
 	lockdep_assert_held_once(&p->blocked_lock);
@@ -2249,21 +2265,23 @@ static inline void __clear_task_blocked_on(struct task_struct *p, struct mutex *
 	 * blocked_on relationships, but make sure we are not
 	 * clearing the relationship with a different lock.
 	 */
-	WARN_ON_ONCE(m && p->blocked_on && p->blocked_on != m);
-	p->blocked_on = NULL;
+	WARN_ON_ONCE(m && p->blocked_on.lock && p->blocked_on.lock != m);
+	p->blocked_on.lock = NULL;
+	p->blocked_on.type = BO_T_NONE;
 }
 
-static inline void clear_task_blocked_on(struct task_struct *p, struct mutex *m)
+static inline void clear_task_blocked_on(struct task_struct *p, void *m)
 {
 	guard(raw_spinlock_irqsave)(&p->blocked_lock);
 	__clear_task_blocked_on(p, m);
 }
+
 #else
-static inline void __clear_task_blocked_on(struct task_struct *p, struct rt_mutex *m)
+static inline void __clear_task_blocked_on(struct task_struct *p, void *m)
 {
 }
 
-static inline void clear_task_blocked_on(struct task_struct *p, struct rt_mutex *m)
+static inline void clear_task_blocked_on(struct task_struct *p, void *m)
 {
 }
 #endif /* !CONFIG_PREEMPT_RT */
diff --git a/kernel/fork.c b/kernel/fork.c
index a5934a317634..6b3f369aad2b 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -2266,7 +2266,7 @@ __latent_entropy struct task_struct *copy_process(
 
 	lockdep_init_task(p);
 
-	p->blocked_on = NULL; /* not blocked yet */
+	p->blocked_on.lock = NULL; /* not blocked yet */
 	p->blocked_donor = NULL; /* nobody is boosting p yet */
 
 #ifdef CONFIG_BCACHE
diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c
index 942a939cee95..b7565ad15494 100644
--- a/kernel/locking/mutex.c
+++ b/kernel/locking/mutex.c
@@ -689,7 +689,7 @@ __mutex_lock_common(struct mutex *lock, unsigned int state, unsigned int subclas
 	}
 
 	raw_spin_lock(&current->blocked_lock);
-	__set_task_blocked_on(current, lock);
+	__set_task_blocked_on(current, lock, BO_T_MUTEX);
 	set_current_state(state);
 	trace_contention_begin(lock, LCB_F_MUTEX);
 	for (;;) {
@@ -734,7 +734,7 @@ __mutex_lock_common(struct mutex *lock, unsigned int state, unsigned int subclas
 		 * that has cleared our blocked_on state, re-set
 		 * it to the lock we are trying to acquire.
 		 */
-		__set_task_blocked_on(current, lock);
+		__set_task_blocked_on(current, lock, BO_T_MUTEX);
 		set_current_state(state);
 		/*
 		 * Here we order against unlock; we must either see it change
@@ -762,7 +762,7 @@ __mutex_lock_common(struct mutex *lock, unsigned int state, unsigned int subclas
 
 			raw_spin_lock_irqsave(&lock->wait_lock, flags);
 			raw_spin_lock(&current->blocked_lock);
-			__set_task_blocked_on(current, lock);
+			__set_task_blocked_on(current, lock, BO_T_MUTEX);
 			set_current_state(state);
 
 			if (opt_acquired)
@@ -1038,7 +1038,7 @@ static noinline void __sched __mutex_unlock_slowpath(struct mutex *lock, unsigne
 		 */
 		donor = current->blocked_donor;
 		if (donor) {
-			struct mutex *next_lock;
+			void *next_lock;
 
 			raw_spin_lock_nested(&donor->blocked_lock, SINGLE_DEPTH_NESTING);
 			next_lock = __get_task_blocked_on(donor);
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 7885ff76e69f..2e8fe4b9bb88 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -150,6 +150,24 @@ static int __init setup_proxy_exec(char *str)
 	}
 	return 1;
 }
+
+static inline struct task_struct *__blocked_on_owner(struct blocked_on_lock *bo)
+{
+	switch (bo->type) {
+	case BO_T_NONE:
+		return NULL;
+	case BO_T_MUTEX:
+		return __mutex_owner(bo->lock);
+	default:
+		WARN_ON_ONCE(1);
+		return NULL;
+	}
+}
+
+static inline struct task_struct *task_blocked_on_owner(struct task_struct *p)
+{
+	return __blocked_on_owner(&p->blocked_on);
+}
 #else
 static int __init setup_proxy_exec(char *str)
 {
@@ -6799,7 +6817,7 @@ static void proxy_deactivate(struct rq *rq, struct task_struct *donor)
 	unsigned long state = READ_ONCE(donor->__state);
 
 	WARN_ON_ONCE(state == TASK_RUNNING);
-	WARN_ON_ONCE(donor->blocked_on);
+	WARN_ON_ONCE(donor->blocked_on.lock);
 	/*
 	 * Because we got donor from pick_next_task(), it is *crucial*
 	 * that we call proxy_resched_idle() before we deactivate it.
@@ -6884,6 +6902,28 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 	proxy_reacquire_rq_lock(rq, rf);
 }
 
+static void
+lock_blocked_on_lock(struct blocked_on_lock *bo)
+{
+	if (bo->type == BO_T_MUTEX)
+		raw_spin_lock(&((struct mutex *)bo->lock)->wait_lock);
+	else
+		WARN_ON_ONCE(1);
+}
+
+static void
+unlock_blocked_on_lock(struct blocked_on_lock *bo)
+{
+	if (bo->type == BO_T_MUTEX)
+		raw_spin_unlock(&((struct mutex *)bo->lock)->wait_lock);
+	else
+		WARN_ON_ONCE(1);
+}
+
+DEFINE_LOCK_GUARD_1(blocked_on_lock, struct blocked_on_lock,
+		    lock_blocked_on_lock(_T->lock),
+		    unlock_blocked_on_lock(_T->lock))
+
 /*
  * Find runnable lock owner to proxy for mutex blocked donor
  *
@@ -6914,6 +6954,7 @@ static struct task_struct *
 find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	__must_hold(__rq_lockp(rq))
 {
+	struct blocked_on_lock bo, *blocked_on;
 	struct task_struct *owner = NULL;
 	bool curr_in_chain = false;
 	int this_cpu = cpu_of(rq);
@@ -6922,10 +6963,15 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
-		/* if its PROXY_WAKING, do return migration or run if current */
-		struct mutex *mutex = p->blocked_on;
-		if (!mutex) {
-			clear_task_blocked_on(p, mutex);
+		/* copy the entire blocked_on structure */
+		raw_spin_lock(&p->blocked_lock);
+		bo = p->blocked_on;
+		raw_spin_unlock(&p->blocked_lock);
+		blocked_on = &bo;
+
+		/* Something changed in the chain, so pick again */
+		if (!blocked_on->lock) {
+			clear_task_blocked_on(p, NULL);
 			if (task_current(rq, p)) {
 				p->is_blocked = 0;
 				return p;
@@ -6937,11 +6983,11 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 		 * By taking mutex->wait_lock we hold off concurrent mutex_unlock()
 		 * and ensure @owner sticks around.
 		 */
-		guard(raw_spinlock)(&mutex->wait_lock);
+		guard(blocked_on_lock)(blocked_on);
 		guard(raw_spinlock)(&p->blocked_lock);
 
 		/* Check again that p is blocked with blocked_lock held */
-		if (mutex != __get_task_blocked_on(p)) {
+		if (blocked_on->lock != __get_task_blocked_on(p)) {
 			/*
 			 * Something changed in the blocked_on chain and
 			 * we don't know if only at this level. So, let's
@@ -6954,7 +7000,7 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 		if (task_current(rq, p))
 			curr_in_chain = true;
 
-		owner = __mutex_owner(mutex);
+		owner = __blocked_on_owner(blocked_on);
 		if (!owner) {
 			/*
 			 * If there is no owner, either clear blocked_on
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index e656c7059bf8..a386ac33e295 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2505,7 +2505,7 @@ static inline bool task_is_blocked(struct task_struct *p)
 	if (!sched_proxy_exec())
 		return false;
 
-	return !!p->blocked_on;
+	return !!p->blocked_on.lock;
 }
 
 static inline int task_on_cpu(struct rq *rq, struct task_struct *p)
-- 
2.55.0.1082.g2b9226bbc0-goog

[RFC PATCH 02/12] futex: Switch PI futex to use p->pi_futex_lock instead of p->pi_lock.

[Suleiman Souhlal]

Switch PI futexes to use p->pi_futex_lock instead of p->pi_lock.

When augmenting PING futexes with proxy execution, we get lock order
inversions, due to the lock order being p->pi_lock -> mutex->wait_lock
in the scheduler, but wait_lock -> p->pi_lock in futex code.

So move the futex code to use a new lock, p->pi_futex_lock, to
protect p->pi_state_list and pi_state->owner.

Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 include/linux/sched.h |  1 +
 init/init_task.c      |  1 +
 kernel/fork.c         |  1 +
 kernel/futex/core.c   | 39 ++++++++++++++++++++------------------
 kernel/futex/pi.c     | 44 +++++++++++++++++++++----------------------
 5 files changed, 46 insertions(+), 40 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 6edd0c7891c5..a7de5c496e3c 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1257,6 +1257,7 @@ struct task_struct {
 
 	/* Protection of the PI data structures: */
 	raw_spinlock_t			pi_lock;
+	raw_spinlock_t			pi_futex_lock;
 
 	struct wake_q_node		wake_q;
 
diff --git a/init/init_task.c b/init/init_task.c
index adb207cd987c..3e9d62f2668a 100644
--- a/init/init_task.c
+++ b/init/init_task.c
@@ -181,6 +181,7 @@ struct task_struct init_task __aligned(L1_CACHE_BYTES) = {
 	.journal_info	= NULL,
 	INIT_CPU_TIMERS(init_task)
 	.pi_lock	= __RAW_SPIN_LOCK_UNLOCKED(init_task.pi_lock),
+	.pi_futex_lock	= __RAW_SPIN_LOCK_UNLOCKED(init_task.pi_futex_lock),
 	.blocked_lock	= __RAW_SPIN_LOCK_UNLOCKED(init_task.blocked_lock),
 	.timer_slack_ns = 50000, /* 50 usec default slack */
 	.thread_pid	= &init_struct_pid,
diff --git a/kernel/fork.c b/kernel/fork.c
index 6b3f369aad2b..80fa3c2d6ea4 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1835,6 +1835,7 @@ SYSCALL_DEFINE1(set_tid_address, int __user *, tidptr)
 static void rt_mutex_init_task(struct task_struct *p)
 {
 	raw_spin_lock_init(&p->pi_lock);
+	raw_spin_lock_init(&p->pi_futex_lock);
 #ifdef CONFIG_RT_MUTEXES
 	p->pi_waiters = RB_ROOT_CACHED;
 	p->pi_top_task = NULL;
diff --git a/kernel/futex/core.c b/kernel/futex/core.c
index a061f54b606d..13c7ea3a26b3 100644
--- a/kernel/futex/core.c
+++ b/kernel/futex/core.c
@@ -1354,8 +1354,8 @@ static void exit_pi_state_list(struct task_struct *curr)
 	might_sleep();
 	/*
 	 * Ensure the hash remains stable (no resize) during the while loop
-	 * below. The hb pointer is acquired under the pi_lock so we can't block
-	 * on the mutex.
+	 * below. The hb pointer is acquired under the pi_futex_lock so we
+	 * can't block on the mutex.
 	 */
 	WARN_ON(curr != current);
 	guard(private_hash)(current->mm);
@@ -1364,7 +1364,7 @@ static void exit_pi_state_list(struct task_struct *curr)
 	 * pi_state_list anymore, but we have to be careful
 	 * versus waiters unqueueing themselves:
 	 */
-	raw_spin_lock_irq(&curr->pi_lock);
+	raw_spin_lock_irq(&curr->pi_futex_lock);
 	while (!list_empty(head)) {
 		next = head->next;
 		pi_state = list_entry(next, struct futex_pi_state, list);
@@ -1384,22 +1384,25 @@ static void exit_pi_state_list(struct task_struct *curr)
 			 * progress and retry the loop.
 			 */
 			if (!refcount_inc_not_zero(&pi_state->refcount)) {
-				raw_spin_unlock_irq(&curr->pi_lock);
+				raw_spin_unlock_irq(&curr->pi_futex_lock);
 				cpu_relax();
-				raw_spin_lock_irq(&curr->pi_lock);
+				raw_spin_lock_irq(&curr->pi_futex_lock);
 				continue;
 			}
-			raw_spin_unlock_irq(&curr->pi_lock);
+			raw_spin_unlock_irq(&curr->pi_futex_lock);
 
 			spin_lock(&hb->lock);
 			raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
-			raw_spin_lock(&curr->pi_lock);
+			raw_spin_lock(&curr->pi_futex_lock);
 			/*
 			 * We dropped the pi-lock, so re-check whether this
 			 * task still owns the PI-state:
 			 */
 			if (head->next != next) {
-				/* retain curr->pi_lock for the loop invariant */
+				/*
+				 * retain curr->pi_futex_lock for the loop
+				 * invariant
+				 */
 				raw_spin_unlock(&pi_state->pi_mutex.wait_lock);
 				spin_unlock(&hb->lock);
 				put_pi_state(pi_state);
@@ -1411,7 +1414,7 @@ static void exit_pi_state_list(struct task_struct *curr)
 			list_del_init(&pi_state->list);
 			pi_state->owner = NULL;
 
-			raw_spin_unlock(&curr->pi_lock);
+			raw_spin_unlock(&curr->pi_futex_lock);
 			raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
 			spin_unlock(&hb->lock);
 		}
@@ -1419,9 +1422,9 @@ static void exit_pi_state_list(struct task_struct *curr)
 		rt_mutex_futex_unlock(&pi_state->pi_mutex);
 		put_pi_state(pi_state);
 
-		raw_spin_lock_irq(&curr->pi_lock);
+		raw_spin_lock_irq(&curr->pi_futex_lock);
 	}
-	raw_spin_unlock_irq(&curr->pi_lock);
+	raw_spin_unlock_irq(&curr->pi_futex_lock);
 }
 #else
 static inline void exit_pi_state_list(struct task_struct *curr) { }
@@ -1513,25 +1516,25 @@ static void futex_cleanup_begin(struct task_struct *tsk)
 	mutex_lock(&tsk->futex.exit_mutex);
 
 	/*
-	 * Switch the state to FUTEX_STATE_EXITING under tsk->pi_lock.
+	 * Switch the state to FUTEX_STATE_EXITING under tsk->pi_futex_lock.
 	 *
 	 * This ensures that all subsequent checks of tsk->futex_state in
 	 * attach_to_pi_owner() must observe FUTEX_STATE_EXITING with
-	 * tsk->pi_lock held.
+	 * tsk->pi_futex_lock held.
 	 *
 	 * It guarantees also that a pi_state which was queued right before
-	 * the state change under tsk->pi_lock by a concurrent waiter must
+	 * the state change under tsk->pi_futex_lock by a concurrent waiter must
 	 * be observed in exit_pi_state_list().
 	 */
-	raw_spin_lock_irq(&tsk->pi_lock);
+	raw_spin_lock_irq(&tsk->pi_futex_lock);
 	tsk->futex.state = FUTEX_STATE_EXITING;
-	raw_spin_unlock_irq(&tsk->pi_lock);
+	raw_spin_unlock_irq(&tsk->pi_futex_lock);
 }
 
 static void futex_cleanup_end(struct task_struct *tsk)
 	__releases(&tsk->futex.exit_mutex)
 {
-	scoped_guard(raw_spinlock_irq, &tsk->pi_lock)
+	scoped_guard(raw_spinlock_irq, &tsk->pi_futex_lock)
 		tsk->futex.state = FUTEX_STATE_DEAD;
 
 	/*
@@ -1579,7 +1582,7 @@ void futex_exec_done(struct task_struct *tsk)
 	 * ordering guarantee required here is that the previous store to
 	 * tsk::mm in the calling code cannot be reordered against this store.
 	 */
-	guard(raw_spinlock_irq)(&tsk->pi_lock);
+	guard(raw_spinlock_irq)(&tsk->pi_futex_lock);
 	tsk->futex.state = FUTEX_STATE_OK;
 }
 
diff --git a/kernel/futex/pi.c b/kernel/futex/pi.c
index 98f1b962e59a..ceeeca1910ca 100644
--- a/kernel/futex/pi.c
+++ b/kernel/futex/pi.c
@@ -51,18 +51,18 @@ static void pi_state_update_owner(struct futex_pi_state *pi_state,
 	lockdep_assert_held(&pi_state->pi_mutex.wait_lock);
 
 	if (old_owner) {
-		raw_spin_lock(&old_owner->pi_lock);
+		raw_spin_lock(&old_owner->pi_futex_lock);
 		WARN_ON(list_empty(&pi_state->list));
 		list_del_init(&pi_state->list);
-		raw_spin_unlock(&old_owner->pi_lock);
+		raw_spin_unlock(&old_owner->pi_futex_lock);
 	}
 
 	if (new_owner) {
-		raw_spin_lock(&new_owner->pi_lock);
+		raw_spin_lock(&new_owner->pi_futex_lock);
 		WARN_ON(!list_empty(&pi_state->list));
 		list_add(&pi_state->list, &new_owner->futex.pi_state_list);
 		pi_state->owner = new_owner;
-		raw_spin_unlock(&new_owner->pi_lock);
+		raw_spin_unlock(&new_owner->pi_futex_lock);
 	}
 }
 
@@ -177,7 +177,7 @@ void put_pi_state(struct futex_pi_state *pi_state)
  *
  *	(and pi_mutex 'obviously')
  *
- * p->pi_lock:
+ * p->pi_futex_lock:
  *
  *	p->futex.pi_state_list -> pi_state->list, relation
  *	pi_mutex->owner -> pi_state->owner, relation
@@ -191,7 +191,7 @@ void put_pi_state(struct futex_pi_state *pi_state)
  *
  *   hb->lock
  *     pi_mutex->wait_lock
- *       p->pi_lock
+ *       p->pi_futex_lock
  *
  * Futex kernel state:
  *
@@ -222,12 +222,12 @@ void put_pi_state(struct futex_pi_state *pi_state)
  *
  * The state has two related locks:
  *
- * 1) p::pi_lock
+ * 1) p::pi_futex_lock
  *
- *    p::pi_lock has to be taken by the waiter when evaluating the state to
- *    protect against a concurrent exit/exec cleanup by the owner. If the state
- *    is OK then the waiter can be attached to the owner while still holding
- *    pi_lock.
+ *    p::pi_futex_lock has to be taken by the waiter when evaluating the state
+ *    to protect against a concurrent exit/exec cleanup by the owner. If the
+ *    state is OK then the waiter can be attached to the owner while still
+ *    holding pi_futex_lock.
  *
  *    The cleanup code has to hold it for all state transitions to ensure that
  *    the stores to the state cannot be reordered against previous stores on
@@ -482,13 +482,13 @@ static int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
 	 * We need to look at the task state to figure out whether the task is
 	 * exiting. To protect against the change of the task state from
 	 * FUTEX_STATE_OK to FUTEX_STATE_EXISTING in futex_cleanup_begin() it is
-	 * required to do this protected by p->pi_lock, which prevents the owner
-	 * from concurrently starting the exit cleanup.
+	 * required to do this protected by p->pi_futex_lock, which prevents
+	 * the owner from concurrently starting the exit cleanup.
 	 *
-	 * If the state is FUTEX_STATE_OK pi_lock must be held until the waiter
-	 * is attached to protect against a concurrent exit()/exec().
+	 * If the state is FUTEX_STATE_OK pi_futex_lock must be held until the
+	 * waiter is attached to protect against a concurrent exit()/exec().
 	 */
-	raw_spin_lock_irq(&p->pi_lock);
+	raw_spin_lock_irq(&p->pi_futex_lock);
 
 	/* Validate that the task is ready for futex operations. */
 	if (unlikely(p->futex.state != FUTEX_STATE_OK)) {
@@ -503,14 +503,14 @@ static int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
 		 * re-evaluates the situation.
 		 */
 		if (p->futex.state == FUTEX_STATE_EXITING) {
-			raw_spin_unlock_irq(&p->pi_lock);
+			raw_spin_unlock_irq(&p->pi_futex_lock);
 			*exiting = p;
 			return -EBUSY;
 		}
 
 		int ret = handle_exit_race(uaddr, uval);
 
-		raw_spin_unlock_irq(&p->pi_lock);
+		raw_spin_unlock_irq(&p->pi_futex_lock);
 		put_task_struct(p);
 		return ret;
 	}
@@ -524,14 +524,14 @@ static int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
 		 * key's mm is freed.
 		 */
 		if (unlikely(p->mm != key->private.mm)) {
-			raw_spin_unlock_irq(&p->pi_lock);
+			raw_spin_unlock_irq(&p->pi_futex_lock);
 			put_task_struct(p);
 			return -EPERM;
 		}
 	}
 
 	__attach_to_pi_owner(p, key, ps);
-	raw_spin_unlock_irq(&p->pi_lock);
+	raw_spin_unlock_irq(&p->pi_futex_lock);
 
 	put_task_struct(p);
 
@@ -650,9 +650,9 @@ int futex_lock_pi_atomic(u32 __user *uaddr, struct futex_hash_bucket *hb,
 		 * because @task is known and valid.
 		 */
 		if (set_waiters) {
-			raw_spin_lock_irq(&task->pi_lock);
+			raw_spin_lock_irq(&task->pi_futex_lock);
 			__attach_to_pi_owner(task, key, ps);
-			raw_spin_unlock_irq(&task->pi_lock);
+			raw_spin_unlock_irq(&task->pi_futex_lock);
 		}
 		return 1;
 	}
-- 
2.55.0.1082.g2b9226bbc0-goog

[RFC PATCH 03/12] futex: Add "ping" parameter to pi_state management functions and export them.

[Suleiman Souhlal]

In preparation to adding FUTEX_PING, allow the pi_state management
functions to use a different wait_lock, and make them non-static.
Also rename handle_exit_race() to pi_handle_exit_race().

Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 kernel/futex/futex.h | 10 ++++++++
 kernel/futex/pi.c    | 61 +++++++++++++++++++++++++-------------------
 2 files changed, 45 insertions(+), 26 deletions(-)

diff --git a/kernel/futex/futex.h b/kernel/futex/futex.h
index f00f0863ed44..e450f60b180b 100644
--- a/kernel/futex/futex.h
+++ b/kernel/futex/futex.h
@@ -395,6 +395,16 @@ extern int refill_pi_state_cache(void);
 extern void get_pi_state(struct futex_pi_state *pi_state);
 extern void put_pi_state(struct futex_pi_state *pi_state);
 extern int fixup_pi_owner(u32 __user *uaddr, struct futex_q *q, int locked);
+extern int pi_handle_exit_race(u32 __user *uaddr, u32 uval);
+extern struct futex_pi_state *alloc_pi_state(void);
+extern int attach_to_pi_state(u32 __user *uaddr, u32 uval,
+			      struct futex_pi_state *pi_state,
+			      struct futex_pi_state **ps,
+			      bool ping);
+extern int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
+			      struct futex_pi_state **ps,
+			      struct task_struct **exiting,
+			      bool ping);
 
 /*
  * Express the locking dependencies for lockdep:
diff --git a/kernel/futex/pi.c b/kernel/futex/pi.c
index ceeeca1910ca..aefcc0491d60 100644
--- a/kernel/futex/pi.c
+++ b/kernel/futex/pi.c
@@ -33,7 +33,7 @@ int refill_pi_state_cache(void)
 	return 0;
 }
 
-static struct futex_pi_state *alloc_pi_state(void)
+struct futex_pi_state *alloc_pi_state(void)
 {
 	struct futex_pi_state *pi_state = current->futex.pi_state_cache;
 
@@ -252,9 +252,10 @@ void put_pi_state(struct futex_pi_state *pi_state)
  * the pi_state against the user space value. If correct, attach to
  * it.
  */
-static int attach_to_pi_state(u32 __user *uaddr, u32 uval,
-			      struct futex_pi_state *pi_state,
-			      struct futex_pi_state **ps)
+int attach_to_pi_state(u32 __user *uaddr, u32 uval,
+		       struct futex_pi_state *pi_state,
+		       struct futex_pi_state **ps,
+		       bool ping)
 {
 	pid_t pid = uval & FUTEX_TID_MASK;
 	u32 uval2;
@@ -284,7 +285,8 @@ static int attach_to_pi_state(u32 __user *uaddr, u32 uval,
 	 * Now that we have a pi_state, we can acquire wait_lock
 	 * and do the state validation.
 	 */
-	raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
+	if (!ping)
+		raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
 
 	/*
 	 * Since {uval, pi_state} is serialized by wait_lock, and our current
@@ -348,8 +350,10 @@ static int attach_to_pi_state(u32 __user *uaddr, u32 uval,
 		goto out_einval;
 
 out_attach:
-	get_pi_state(pi_state);
-	raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
+	if (!ping) {
+		get_pi_state(pi_state);
+		raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
+	}
 	*ps = pi_state;
 	return 0;
 
@@ -370,7 +374,7 @@ static int attach_to_pi_state(u32 __user *uaddr, u32 uval,
 	return ret;
 }
 
-static int handle_exit_race(u32 __user *uaddr, u32 uval)
+int pi_handle_exit_race(u32 __user *uaddr, u32 uval)
 {
 	u32 uval2;
 
@@ -419,7 +423,8 @@ static int handle_exit_race(u32 __user *uaddr, u32 uval)
 }
 
 static void __attach_to_pi_owner(struct task_struct *p, union futex_key *key,
-				 struct futex_pi_state **ps)
+				 struct futex_pi_state **ps,
+				 bool ping)
 {
 	/*
 	 * No existing pi state. First waiter. [2]
@@ -429,18 +434,20 @@ static void __attach_to_pi_owner(struct task_struct *p, union futex_key *key,
 	 */
 	struct futex_pi_state *pi_state = alloc_pi_state();
 
-	/*
-	 * Initialize the pi_mutex in locked state and make @p
-	 * the owner of it:
-	 */
-	__assume_ctx_lock(&pi_state->pi_mutex.wait_lock);
-	rt_mutex_init_proxy_locked(&pi_state->pi_mutex, p);
+	if (!ping) {
+		/*
+		 * Initialize the pi_mutex in locked state and make @p
+		 * the owner of it:
+		 */
+		__assume_ctx_lock(&pi_state->pi_mutex.wait_lock);
+		rt_mutex_init_proxy_locked(&pi_state->pi_mutex, p);
+		WARN_ON(!list_empty(&pi_state->list));
+		list_add(&pi_state->list, &p->futex.pi_state_list);
+	}
 
 	/* Store the key for possible exit cleanups: */
 	pi_state->key = *key;
 
-	WARN_ON(!list_empty(&pi_state->list));
-	list_add(&pi_state->list, &p->futex.pi_state_list);
 	/*
 	 * Assignment without holding pi_state->pi_mutex.wait_lock is safe
 	 * because there is no concurrency as the object is not published yet.
@@ -453,9 +460,10 @@ static void __attach_to_pi_owner(struct task_struct *p, union futex_key *key,
  * Lookup the task for the TID provided from user space and attach to
  * it after doing proper sanity checks.
  */
-static int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
-			      struct futex_pi_state **ps,
-			      struct task_struct **exiting)
+int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
+		       struct futex_pi_state **ps,
+		       struct task_struct **exiting,
+		       bool ping)
 {
 	pid_t pid = uval & FUTEX_TID_MASK;
 	struct task_struct *p;
@@ -471,7 +479,7 @@ static int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
 		return -EAGAIN;
 	p = find_get_task_by_vpid(pid);
 	if (!p)
-		return handle_exit_race(uaddr, uval);
+		return pi_handle_exit_race(uaddr, uval);
 
 	if (unlikely(p->flags & PF_KTHREAD)) {
 		put_task_struct(p);
@@ -508,7 +516,7 @@ static int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
 			return -EBUSY;
 		}
 
-		int ret = handle_exit_race(uaddr, uval);
+		int ret = pi_handle_exit_race(uaddr, uval);
 
 		raw_spin_unlock_irq(&p->pi_futex_lock);
 		put_task_struct(p);
@@ -530,7 +538,7 @@ static int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
 		}
 	}
 
-	__attach_to_pi_owner(p, key, ps);
+	__attach_to_pi_owner(p, key, ps, ping);
 	raw_spin_unlock_irq(&p->pi_futex_lock);
 
 	put_task_struct(p);
@@ -614,7 +622,8 @@ int futex_lock_pi_atomic(u32 __user *uaddr, struct futex_hash_bucket *hb,
 	 */
 	top_waiter = futex_top_waiter(hb, key);
 	if (top_waiter)
-		return attach_to_pi_state(uaddr, uval, top_waiter->pi_state, ps);
+		return attach_to_pi_state(uaddr, uval, top_waiter->pi_state,
+		    ps, false);
 
 	/*
 	 * No waiter and user TID is 0. We are here because the
@@ -651,7 +660,7 @@ int futex_lock_pi_atomic(u32 __user *uaddr, struct futex_hash_bucket *hb,
 		 */
 		if (set_waiters) {
 			raw_spin_lock_irq(&task->pi_futex_lock);
-			__attach_to_pi_owner(task, key, ps);
+			__attach_to_pi_owner(task, key, ps, false);
 			raw_spin_unlock_irq(&task->pi_futex_lock);
 		}
 		return 1;
@@ -671,7 +680,7 @@ int futex_lock_pi_atomic(u32 __user *uaddr, struct futex_hash_bucket *hb,
 	 * attach to the owner. If that fails, no harm done, we only
 	 * set the FUTEX_WAITERS bit in the user space variable.
 	 */
-	return attach_to_pi_owner(uaddr, newval, key, ps, exiting);
+	return attach_to_pi_owner(uaddr, newval, key, ps, exiting, false);
 }
 
 /*
-- 
2.55.0.1082.g2b9226bbc0-goog

[RFC PATCH 04/12] futex: Introduce stealable PI futex, FUTEX_*_PING.

[Suleiman Souhlal]

Introduce a New Generation of PI futexes, FUTEX_*_PING.

They are used similarly to FUTEX_*_PI, where the owner is expected
to write its TID in the futex.

The main user-visible difference with regular PI futexes is that the
kernel is allowed to set the FUTEX_WAITERS bit with an empty TID.
This is to allow for a new locker to steal the lock from the top
waiter, which is supposed to improve performance in workloads that
don't need strict RT handling.

An example of how they're meant to be used:
Lock:
	static __thread pid_t tid = gettid();
	uint32_t oldval = 0;
	if (atomic_compare_exchange_strong(ftx, &oldval, tid)
		return;
	if (futex(ftx, FUTEX_LOCK_PING, 0, NULL) != 0)
		err(1, "FUTEX_LOCK_PING");

Unlock:
	static __thread pid_t tid = gettid();
	uint32_t oldval = tid;
	if (atomic_compare_exchange_strong(ftx, &oldval, 0))
		return;
	if (futex(ftx, FUTEX_UNLOCK_PING, 0, NULL) != 0)
		err(1, "FUTEX_UNLOCK_PING");

Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 include/linux/futex.h       |  11 +
 include/linux/futex_types.h |   1 +
 include/uapi/linux/futex.h  |   3 +
 kernel/futex/Makefile       |   2 +-
 kernel/futex/futex.h        |  13 +-
 kernel/futex/pi.c           |  15 ++
 kernel/futex/ping.c         | 503 ++++++++++++++++++++++++++++++++++++
 kernel/futex/syscalls.c     |   6 +
 8 files changed, 552 insertions(+), 2 deletions(-)
 create mode 100644 kernel/futex/ping.c

diff --git a/include/linux/futex.h b/include/linux/futex.h
index 18ed18d5cbc1..b1b422b480fb 100644
--- a/include/linux/futex.h
+++ b/include/linux/futex.h
@@ -66,6 +66,7 @@ static inline void futex_init_task(struct task_struct *tsk)
 {
 	memset(&tsk->futex, 0, sizeof(tsk->futex));
 	INIT_LIST_HEAD(&tsk->futex.pi_state_list);
+	INIT_LIST_HEAD(&tsk->futex.ping_state_list);
 	tsk->futex.state = FUTEX_STATE_OK;
 	mutex_init(&tsk->futex.exit_mutex);
 }
@@ -159,4 +160,14 @@ void futex_mm_init(struct mm_struct *mm);
 static inline void futex_mm_init(struct mm_struct *mm) { }
 #endif
 
+struct ping_mutex {
+	raw_spinlock_t wait_lock;
+	struct task_struct *owner;
+};
+
+static inline struct task_struct *ping_mutex_owner(struct ping_mutex *ping_mutex)
+{
+	return READ_ONCE(ping_mutex->owner);
+}
+
 #endif /* _LINUX_FUTEX_H */
diff --git a/include/linux/futex_types.h b/include/linux/futex_types.h
index d320c0571f0c..50cb30d6e54b 100644
--- a/include/linux/futex_types.h
+++ b/include/linux/futex_types.h
@@ -26,6 +26,7 @@ struct futex_sched_data {
 	struct compat_robust_list_head __user	*compat_robust_list;
 #endif
 	struct list_head			pi_state_list;
+	struct list_head			ping_state_list;
 	struct futex_pi_state			*pi_state_cache;
 	struct mutex				exit_mutex;
 	unsigned int				state;
diff --git a/include/uapi/linux/futex.h b/include/uapi/linux/futex.h
index 10a36c551675..e2c15db7274e 100644
--- a/include/uapi/linux/futex.h
+++ b/include/uapi/linux/futex.h
@@ -22,6 +22,9 @@
 #define FUTEX_WAIT_REQUEUE_PI	11
 #define FUTEX_CMP_REQUEUE_PI	12
 #define FUTEX_LOCK_PI2		13
+#define	FUTEX_LOCK_PING		14
+#define	FUTEX_UNLOCK_PING	15
+#define	FUTEX_TRYLOCK_PING	16
 
 #define FUTEX_PRIVATE_FLAG	128
 #define FUTEX_CLOCK_REALTIME	256
diff --git a/kernel/futex/Makefile b/kernel/futex/Makefile
index dce70f8a322b..c4cfaf122894 100644
--- a/kernel/futex/Makefile
+++ b/kernel/futex/Makefile
@@ -2,4 +2,4 @@
 
 CONTEXT_ANALYSIS := y
 
-obj-y += core.o syscalls.o pi.o requeue.o waitwake.o
+obj-y += core.o syscalls.o pi.o ping.o requeue.o waitwake.o
diff --git a/kernel/futex/futex.h b/kernel/futex/futex.h
index e450f60b180b..c0560d30aaaa 100644
--- a/kernel/futex/futex.h
+++ b/kernel/futex/futex.h
@@ -167,7 +167,10 @@ struct futex_pi_state {
 	/*
 	 * The PI object:
 	 */
-	struct rt_mutex_base pi_mutex;
+	union {
+		struct rt_mutex_base pi_mutex;
+		struct ping_mutex ping_mutex;
+	};
 
 	struct task_struct *owner;
 	refcount_t refcount;
@@ -214,6 +217,7 @@ struct futex_q {
 	void *wake_data;
 	union futex_key key;
 	struct futex_pi_state *pi_state;
+	struct futex_pi_state *ping_state;
 	struct rt_mutex_waiter *rt_waiter;
 	union futex_key *requeue_pi_key;
 	u32 bitset;
@@ -405,6 +409,8 @@ extern int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
 			      struct futex_pi_state **ps,
 			      struct task_struct **exiting,
 			      bool ping);
+extern void get_ping_state(struct futex_pi_state *ping_state);
+extern void put_ping_state(struct futex_pi_state *ping_state);
 
 /*
  * Express the locking dependencies for lockdep:
@@ -488,4 +494,9 @@ extern int futex_lock_pi(u32 __user *uaddr, unsigned int flags, ktime_t *time, i
 
 bool futex_robust_list_clear_pending(void __user *pop, unsigned int flags);
 
+extern int futex_unlock_ping(u32 __user *uaddr, unsigned int flags);
+
+extern int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
+			   int trylock);
+
 #endif /* _FUTEX_H */
diff --git a/kernel/futex/pi.c b/kernel/futex/pi.c
index aefcc0491d60..e7e6e347f97d 100644
--- a/kernel/futex/pi.c
+++ b/kernel/futex/pi.c
@@ -287,6 +287,8 @@ int attach_to_pi_state(u32 __user *uaddr, u32 uval,
 	 */
 	if (!ping)
 		raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
+	else
+		raw_spin_lock_irq(&pi_state->ping_mutex.wait_lock);
 
 	/*
 	 * Since {uval, pi_state} is serialized by wait_lock, and our current
@@ -353,6 +355,9 @@ int attach_to_pi_state(u32 __user *uaddr, u32 uval,
 	if (!ping) {
 		get_pi_state(pi_state);
 		raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
+	} else {
+		get_ping_state(pi_state);
+		raw_spin_unlock_irq(&pi_state->ping_mutex.wait_lock);
 	}
 	*ps = pi_state;
 	return 0;
@@ -443,6 +448,16 @@ static void __attach_to_pi_owner(struct task_struct *p, union futex_key *key,
 		rt_mutex_init_proxy_locked(&pi_state->pi_mutex, p);
 		WARN_ON(!list_empty(&pi_state->list));
 		list_add(&pi_state->list, &p->futex.pi_state_list);
+	} else {
+		/*
+		 * Initialize the pi_mutex in locked state and make @p
+		 * the owner of it:
+		 */
+		pi_state->ping_mutex.owner = p;
+		raw_spin_lock_init(&pi_state->ping_mutex.wait_lock);
+
+		WARN_ON(!list_empty(&pi_state->list));
+		list_add(&pi_state->list, &p->futex.ping_state_list);
 	}
 
 	/* Store the key for possible exit cleanups: */
diff --git a/kernel/futex/ping.c b/kernel/futex/ping.c
new file mode 100644
index 000000000000..3d732489513b
--- /dev/null
+++ b/kernel/futex/ping.c
@@ -0,0 +1,503 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#include <linux/plist.h>
+#include <linux/slab.h>
+#include <linux/sched/task.h>
+
+#include "futex.h"
+
+static int futex_trylock_ping_state(u32 __user *uaddr,
+				    struct futex_pi_state *ping_state);
+
+static void ping_state_update_owner(struct futex_pi_state *ping_state,
+				    struct task_struct *new_owner)
+{
+	struct task_struct *old_owner = ping_state->owner;
+
+	lockdep_assert_held(&ping_state->ping_mutex.wait_lock);
+
+	if (old_owner) {
+		raw_spin_lock(&old_owner->pi_futex_lock);
+		WARN_ON(list_empty(&ping_state->list));
+		list_del_init(&ping_state->list);
+		raw_spin_unlock(&old_owner->pi_futex_lock);
+	}
+
+	if (new_owner) {
+		raw_spin_lock(&new_owner->pi_futex_lock);
+		WARN_ON(!list_empty(&ping_state->list));
+		list_add(&ping_state->list, &new_owner->futex.ping_state_list);
+		ping_state->owner = new_owner;
+		raw_spin_unlock(&new_owner->pi_futex_lock);
+	}
+}
+
+static int lock_pi_update_atomic(u32 __user *uaddr, u32 uval, u32 newval)
+{
+	int err;
+	u32 curval;
+
+	if (unlikely(should_fail_futex(true)))
+		return -EFAULT;
+
+	err = futex_cmpxchg_value_locked(&curval, uaddr, uval, newval);
+	if (unlikely(err))
+		return err;
+
+	/* If user space value changed, let the caller retry */
+	return curval != uval ? -EAGAIN : 0;
+}
+
+void
+get_ping_state(struct futex_pi_state *ping_state)
+{
+	WARN_ON_ONCE(!refcount_inc_not_zero(&ping_state->refcount));
+}
+
+/*
+ * Drops a reference to the pi_state object and frees or caches it
+ * when the last reference is gone.
+ */
+void
+put_ping_state(struct futex_pi_state *ping_state)
+{
+	if (!ping_state)
+		return;
+
+	if (!refcount_dec_and_test(&ping_state->refcount))
+		return;
+
+	/*
+	 * If ping_state->owner is NULL, the owner is most probably dying
+	 * and has cleaned up the pi_state already
+	 */
+	if (ping_state->owner) {
+		unsigned long flags;
+
+		raw_spin_lock_irqsave(&ping_state->ping_mutex.wait_lock, flags);
+		ping_state_update_owner(ping_state, NULL);
+		WRITE_ONCE(ping_state->ping_mutex.owner, NULL);
+		raw_spin_unlock_irqrestore(&ping_state->ping_mutex.wait_lock,
+					   flags);
+	}
+
+	if (current->futex.pi_state_cache) {
+		kfree(ping_state);
+	} else {
+		/*
+		 * pi_state->list is already empty.
+		 * clear pi_state->owner.
+		 * refcount is at 0 - put it back to 1.
+		 */
+		ping_state->owner = NULL;
+		refcount_set(&ping_state->refcount, 1);
+		current->futex.pi_state_cache = ping_state;
+	}
+}
+
+static void futex_unqueue_ping(struct futex_q *q)
+{
+	if (!plist_node_empty(&q->list))
+		__futex_unqueue(q);
+
+	WARN_ON(!q->ping_state);
+	put_ping_state(q->ping_state);
+	q->ping_state = NULL;
+}
+
+/* Returns >0 if lock acquired, <0 on error */
+static int futex_trylock_ping_state(u32 __user *uaddr,
+				    struct futex_pi_state *ping_state)
+{
+	struct task_struct *owner;
+	u32 uval, new, newtid;
+	int ret;
+
+	ret = 0;
+	raw_spin_lock_irq(&ping_state->ping_mutex.wait_lock);
+	owner = ping_mutex_owner(&ping_state->ping_mutex);
+	if (owner == NULL) {
+		newtid = task_pid_vnr(current);
+
+		ret = futex_get_value_locked(&uval, uaddr);
+		if (ret)
+			goto err;
+		if (uval & FUTEX_TID_MASK) {
+			ret = -EAGAIN;
+			goto err;
+		}
+		new = newtid | FUTEX_WAITERS;
+		ret = lock_pi_update_atomic(uaddr, uval, new);
+		if (ret)
+			goto err;
+		if (ping_state->owner != current)
+			ping_state_update_owner(ping_state, current);
+		WRITE_ONCE(ping_state->ping_mutex.owner, current);
+		ret = 1;
+	}
+	raw_spin_unlock_irq(&ping_state->ping_mutex.wait_lock);
+	return ret;
+
+err:
+	raw_spin_unlock_irq(&ping_state->ping_mutex.wait_lock);
+	switch (ret) {
+	case -EFAULT:
+		ret = fault_in_user_writeable(uaddr);
+		break;
+	case -EAGAIN:
+		ret = 0;
+		break;
+	case -EINVAL:
+		break;
+	default:
+		WARN_ON(1);
+	}
+	return ret;
+}
+
+static int futex_lock_ping_atomic(u32 __user *uaddr,
+				  struct futex_hash_bucket *hb,
+				  union futex_key *key,
+				  struct futex_pi_state **ps,
+				  struct task_struct *task,
+				  struct task_struct **exiting)
+{
+	u32 uval, newval, vpid = task_pid_vnr(task);
+	struct futex_q *top_waiter;
+	int ret;
+
+	/*
+	 * Read the user space value first so we can validate a few
+	 * things before proceeding further.
+	 */
+	if (futex_get_value_locked(&uval, uaddr))
+		return -EFAULT;
+
+	if (unlikely(should_fail_futex(true)))
+		return -EFAULT;
+
+	/*
+	 * Detect deadlocks.
+	 */
+	if ((unlikely((uval & FUTEX_TID_MASK) == vpid)))
+		return -EDEADLK;
+
+	if ((unlikely(should_fail_futex(true))))
+		return -EDEADLK;
+
+	/*
+	 * Lookup existing state first. If it exists, try to attach to
+	 * its ping_state.
+	 */
+	top_waiter = futex_top_waiter(hb, key);
+	if (top_waiter) {
+		struct futex_pi_state *_ps;
+
+		_ps = top_waiter->ping_state;
+		if (_ps == NULL)
+			return -EINVAL;
+		ret = futex_trylock_ping_state(uaddr, _ps);
+		if (ret > 0) {
+			/* We stole the lock from the top waiter. */
+			raw_spin_lock_irq(&_ps->ping_mutex.wait_lock);
+			WARN_ON_ONCE(!refcount_read(&_ps->refcount));
+			get_ping_state(_ps);
+			raw_spin_unlock_irq(&_ps->ping_mutex.wait_lock);
+			*ps = _ps;
+			return 1;
+		} else if (ret < 0)
+			return ret;
+		return attach_to_pi_state(uaddr, uval, top_waiter->ping_state,
+					  ps, true);
+	}
+
+	/*
+	 * No waiter and user TID is 0. We are here because the
+	 * waiters or the owner died bit is set or called from
+	 * requeue_cmp_pi or for whatever reason something took the
+	 * syscall.
+	 */
+	if (!(uval & FUTEX_TID_MASK)) {
+		/*
+		 * We take over the futex. No other waiters and the user space
+		 * TID is 0. We preserve the owner died bit.
+		 */
+		newval = uval & FUTEX_OWNER_DIED;
+		newval |= vpid;
+
+		ret = lock_pi_update_atomic(uaddr, uval, newval);
+		if (ret)
+			return ret;
+		return 1;
+	}
+
+	/*
+	 * First waiter. Set the waiters bit before attaching ourself to
+	 * the owner. If owner tries to unlock, it will be forced into
+	 * the kernel and blocked on hb->lock.
+	 */
+	newval = uval | FUTEX_WAITERS;
+	ret = lock_pi_update_atomic(uaddr, uval, newval);
+	if (ret)
+		return ret;
+	/*
+	 * If the update of the user space value succeeded, we try to
+	 * attach to the owner. If that fails, no harm done, we only
+	 * set the FUTEX_WAITERS bit in the user space variable.
+	 */
+	return attach_to_pi_owner(uaddr, newval, key, ps, exiting, true);
+}
+
+/*
+ * Return values:
+ *     < 0: error.
+ *     0: did not get the lock.
+ *     1: got the lock.
+ */
+int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
+		    int trylock)
+{
+	struct hrtimer_sleeper timeout, *to;
+	struct task_struct *exiting;
+	struct futex_q q = futex_q_init;
+	bool queued;
+	int ret;
+
+	if (refill_pi_state_cache())
+		return -ENOMEM;
+
+	to = futex_setup_timer(time, &timeout, flags, 0);
+
+retry:
+	ret = get_futex_key(uaddr, flags, &q.key, FUTEX_WRITE);
+	if (unlikely(ret != 0))
+		goto out;
+
+retry_private:
+	if (1) {
+		CLASS(hbr, hbr)(&q.key);
+		auto hb = hbr.hb;
+
+		futex_q_lock(&q, hb);
+
+		ret = futex_lock_ping_atomic(uaddr, hb, &q.key, &q.ping_state,
+					     current, &exiting);
+		if (unlikely(ret)) {
+			/*
+			 * Atomic work succeeded and we got the lock,
+			 * or failed. Either way, we do _not_ block.
+			 */
+			switch (ret) {
+			case 1:
+				ret = 0;
+				/* Got the lock */
+				put_ping_state(q.ping_state);
+				q.ping_state = NULL;
+				goto out_unlock;
+			case -EFAULT:
+				goto uaddr_faulted;
+			case -EBUSY:
+			case -EAGAIN:
+				/*
+				 * Two reasons for this:
+				 * - EBUSY: Task is exiting and we just wait
+				 * for the exit to complete.
+				 * - EAGAIN: The user space value changed.
+				 */
+				futex_q_unlock(hb);
+				/*
+				 * Handle the case where the owner is in the
+				 * middle of exiting. Wait for the exit to
+				 * complete otherwise this task might loop
+				 * forever, aka. live lock.
+				 */
+				wait_for_owner_exiting(ret, exiting);
+				cond_resched();
+				goto retry;
+			default:
+				goto out_unlock;
+			}
+		}
+
+		WARN_ON(!q.ping_state);
+		if (trylock) {
+			/*
+			 * futex_lock_ping_atomic() trylocks and we did not
+			 * get the lock.
+			 */
+			put_ping_state(q.ping_state);
+			q.ping_state = NULL;
+			ret = -EWOULDBLOCK;
+			goto out_unlock;
+		}
+
+		queued = false;
+		while (1) {
+			set_current_state(TASK_INTERRUPTIBLE|TASK_FREEZABLE);
+			if (!queued) {
+				futex_queue(&q, hb, current);
+				queued = true;
+			} else {
+				WARN_ON_ONCE(plist_node_empty(&q.list));
+				spin_unlock(&hb->lock);
+				__release(q->lock_ptr);
+			}
+
+			futex_do_wait(&q, to);
+
+			futex_q_lockptr_lock(&q);
+			if (to && !to->task) {
+				ret = -ETIMEDOUT;
+				goto out_unqueue;
+			}
+			if (signal_pending(current)) {
+				ret = -EINTR;
+				goto out_unqueue;
+			}
+
+			ret = futex_trylock_ping_state(uaddr, q.ping_state);
+			if (ret > 0) {
+				/* Got the futex */
+				ret = 0;
+				goto out_unqueue;
+			} else if (ret < 0)
+				goto out_unqueue;
+		}
+
+out_unqueue:
+		if (ret != 0 && q.ping_state->owner == current) {
+			/*
+			 * We are pi_state owner but don't own the futex.
+			 * This can happen if we get picked by the previous
+			 * owner but get out without acquiring the lock for
+			 * some reason.
+			 * A later commit addresses this.
+			 */
+			WARN_ON_ONCE(1);
+		}
+		/* This also puts the ping_state */
+		futex_unqueue_ping(&q);
+out_unlock:
+		futex_q_unlock(hb);
+		__release(q.lock_ptr);
+		goto out;
+
+uaddr_faulted:
+		futex_q_unlock(hb);
+		__release(q.lock_ptr);
+
+		ret = fault_in_user_writeable(uaddr);
+		if (ret)
+			goto out;
+		if (!(flags & FLAGS_SHARED))
+			goto retry_private;
+		goto retry;
+	}
+
+out:
+	if (to) {
+		hrtimer_cancel(&to->timer);
+		destroy_hrtimer_on_stack(&to->timer);
+	}
+
+	return ret;
+}
+
+int futex_unlock_ping(u32 __user *uaddr, unsigned int flags)
+{
+	struct futex_pi_state *ping_state;
+	u32 new, uval, vpid = task_pid_vnr(current);
+	union futex_key key = FUTEX_KEY_INIT;
+	struct futex_q *top_waiter;
+	DEFINE_WAKE_Q(wake_q);
+	int ret;
+
+retry:
+	if (get_user(uval, uaddr))
+		return -EFAULT;
+	/*
+	 * We release only a lock we actually own:
+	 */
+	if ((uval & FUTEX_TID_MASK) != vpid)
+		return -EPERM;
+
+	ret = get_futex_key(uaddr, flags, &key, FUTEX_WRITE);
+	if (ret)
+		return ret;
+
+	CLASS(hbr, hbr)(&key);
+	auto hb = hbr.hb;
+	spin_lock(&hb->lock);
+	top_waiter = futex_top_waiter(hb, &key);
+
+	if (!top_waiter) {
+		spin_unlock(&hb->lock);
+		/* No waiters in the kernel, we can just clear FUTEX_WAITERS */
+		ret = lock_pi_update_atomic(uaddr, uval, 0);
+		if (ret) {
+			switch (ret) {
+			case -EFAULT:
+				goto uaddr_faulted;
+			case -EAGAIN:
+				cond_resched();
+				goto retry;
+			default:
+				WARN_ON_ONCE(1);
+			}
+		}
+		return ret;
+	}
+
+	ping_state = top_waiter->ping_state;
+	ret = -EINVAL;
+	if (!ping_state)
+		goto out_unlock;
+	raw_spin_lock_irq(&ping_state->ping_mutex.wait_lock);
+	if (ping_state->owner != current) {
+		raw_spin_unlock_irq(&ping_state->ping_mutex.wait_lock);
+		goto out_unlock;
+	}
+	get_ping_state(ping_state);
+	/* Leave it queued, it gets unqueued on the lock side */
+	get_task_struct(top_waiter->task);
+	wake_q_add_safe(&wake_q, top_waiter->task);
+	spin_unlock(&hb->lock);
+
+	/*
+	 * Unconditionally set FUTEX_WAITERS.
+	 * It will get removed by the next unlocker who notices there is
+	 * no top_waiter.
+	 */
+	new = FUTEX_WAITERS;
+	ret = lock_pi_update_atomic(uaddr, uval, new);
+	if (ret) {
+		raw_spin_unlock_irq(&ping_state->ping_mutex.wait_lock);
+		put_ping_state(ping_state);
+		switch (ret) {
+		case -EFAULT:
+			goto uaddr_faulted;
+		case -EAGAIN:
+			cond_resched();
+			goto retry;
+		default:
+			WARN_ON_ONCE(1);
+			return ret;
+		}
+	}
+
+	ping_state_update_owner(ping_state, top_waiter->task);
+	WRITE_ONCE(ping_state->ping_mutex.owner, NULL);
+	raw_spin_unlock_irq_wake(&ping_state->ping_mutex.wait_lock, &wake_q);
+	put_ping_state(ping_state);
+	return 0;
+
+out_unlock:
+	spin_unlock(&hb->lock);
+	return ret;
+
+uaddr_faulted:
+	ret = fault_in_user_writeable(uaddr);
+	if (ret)
+		return ret;
+	goto retry;
+}
diff --git a/kernel/futex/syscalls.c b/kernel/futex/syscalls.c
index 2fa19d9d008d..2e6847f0be79 100644
--- a/kernel/futex/syscalls.c
+++ b/kernel/futex/syscalls.c
@@ -151,6 +151,12 @@ long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
 		return futex_unlock_pi(uaddr, flags, uaddr2);
 	case FUTEX_TRYLOCK_PI:
 		return futex_lock_pi(uaddr, flags, NULL, 1);
+	case FUTEX_LOCK_PING:
+		return futex_lock_ping(uaddr, flags, timeout, 0);
+	case FUTEX_UNLOCK_PING:
+		return futex_unlock_ping(uaddr, flags);
+	case FUTEX_TRYLOCK_PING:
+		return futex_lock_ping(uaddr, flags, NULL, 1);
 	case FUTEX_WAIT_REQUEUE_PI:
 		val3 = FUTEX_BITSET_MATCH_ANY;
 		return futex_wait_requeue_pi(uaddr, flags, val, timeout, val3,
-- 
2.55.0.1082.g2b9226bbc0-goog

[RFC PATCH 05/12] futex: Implement exit_ping_state_list().

[Suleiman Souhlal]

Handle the case when a task exits while holding some ping_states,
unowning them and dropping their references.

Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 kernel/futex/core.c | 55 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)

diff --git a/kernel/futex/core.c b/kernel/futex/core.c
index 13c7ea3a26b3..56c7e2d5faac 100644
--- a/kernel/futex/core.c
+++ b/kernel/futex/core.c
@@ -1430,6 +1430,58 @@ static void exit_pi_state_list(struct task_struct *curr)
 static inline void exit_pi_state_list(struct task_struct *curr) { }
 #endif
 
+/* Similar to exit_pi_state_list() */
+static void exit_ping_state_list(struct task_struct *curr)
+{
+	struct list_head *next, *head = &curr->futex.ping_state_list;
+	struct futex_pi_state *ping_state;
+	union futex_key key = FUTEX_KEY_INIT;
+
+	might_sleep();
+	WARN_ON(curr != current);
+	guard(private_hash)(current->mm);
+
+	raw_spin_lock_irq(&curr->pi_futex_lock);
+	while (!list_empty(head)) {
+		next = head->next;
+		ping_state = list_entry(next, struct futex_pi_state, list);
+		if (1) {
+			CLASS(hbr, hbr)(&key);
+			auto hb = hbr.hb;
+
+			if (!refcount_inc_not_zero(&ping_state->refcount)) {
+				raw_spin_unlock_irq(&curr->pi_futex_lock);
+				cpu_relax();
+				raw_spin_lock_irq(&curr->pi_futex_lock);
+				continue;
+			}
+			raw_spin_unlock_irq(&curr->pi_futex_lock);
+
+			spin_lock(&hb->lock);
+			raw_spin_lock_irq(&ping_state->ping_mutex.wait_lock);
+			raw_spin_lock(&curr->pi_futex_lock);
+			if (head->next != next) {
+				raw_spin_unlock(&ping_state->ping_mutex.wait_lock);
+				spin_unlock(&hb->lock);
+				put_ping_state(ping_state);
+				continue;
+			}
+
+			WARN_ON(ping_state->owner != curr);
+			WARN_ON(list_empty(&ping_state->list));
+			list_del_init(&ping_state->list);
+			ping_state->owner = NULL;
+			raw_spin_unlock(&curr->pi_futex_lock);
+			raw_spin_unlock_irq(&ping_state->ping_mutex.wait_lock);
+			spin_unlock(&hb->lock);
+		}
+		put_ping_state(ping_state);
+
+		raw_spin_lock_irq(&curr->pi_futex_lock);
+	}
+	raw_spin_unlock_irq(&curr->pi_futex_lock);
+}
+
 bool futex_robust_list_clear_pending(void __user *pop, unsigned int flags)
 {
 	bool size32bit = !!(flags & FLAGS_ROBUST_LIST32);
@@ -1475,6 +1527,9 @@ static void futex_cleanup(struct task_struct *tsk)
 
 	if (unlikely(!list_empty(&tsk->futex.pi_state_list)))
 		exit_pi_state_list(tsk);
+
+	if (unlikely(!list_empty(&tsk->futex.ping_state_list)))
+		exit_ping_state_list(tsk);
 }
 
 /**
-- 
2.55.0.1082.g2b9226bbc0-goog

[RFC PATCH 06/12] futex: Address aborting from futex_lock_ping() while owning ping_state.

[Suleiman Souhlal]

It is possible to unsuccesfully get out of the futex_lock_ping() loop
while owning the ping_state. This can happen when a waiting task gets
chosen by an unlocker as the top waiter, but gets a signal or its timeout
expires.
When this happens, wake up the next waiter and give them the ping_state.

Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 kernel/futex/ping.c | 72 ++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 61 insertions(+), 11 deletions(-)

diff --git a/kernel/futex/ping.c b/kernel/futex/ping.c
index 3d732489513b..ebcd3c4a7793 100644
--- a/kernel/futex/ping.c
+++ b/kernel/futex/ping.c
@@ -105,6 +105,43 @@ static void futex_unqueue_ping(struct futex_q *q)
 	q->ping_state = NULL;
 }
 
+/*
+ * We own the ping_state but weren't able to get the futex.
+ * Wake up the next waiter and give them ownership.
+ */
+static void give_ping_state_to_next_waiter(struct futex_hash_bucket *hb,
+					   union futex_key *key,
+					   struct futex_pi_state *ping_state)
+{
+	struct futex_q *top_waiter;
+	DEFINE_WAKE_Q(wake_q);
+
+	raw_spin_lock_irq(&ping_state->ping_mutex.wait_lock);
+	/*
+	 * Someone else got the futex and we don't need to do anything
+	 * anymore, as it's their responsibility now.
+	 */
+	if (ping_state->owner && ping_state->owner != current)
+		goto out;
+
+	top_waiter = futex_top_waiter(hb, key);
+	/*
+	 * There are no other waiters but we leave the WAITERS bit set
+	 * (with no owner or ping_state) to be cleaned up at a later unlock,
+	 * at the cost of an extra syscall at the next lock operation, to
+	 * keep things simple.
+	 */
+	if (!top_waiter)
+		goto out;
+	get_ping_state(ping_state);
+	get_task_struct(top_waiter->task);
+	wake_q_add_safe(&wake_q, top_waiter->task);
+	ping_state_update_owner(ping_state, top_waiter->task);
+
+out:
+	raw_spin_unlock_irq_wake(&ping_state->ping_mutex.wait_lock, &wake_q);
+}
+
 /* Returns >0 if lock acquired, <0 on error */
 static int futex_trylock_ping_state(u32 __user *uaddr,
 				    struct futex_pi_state *ping_state)
@@ -365,18 +402,31 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 		}
 
 out_unqueue:
+		/*
+		 * We got a pending signal or timeout, but the futex was handed
+		 * off to us. Fix up the return value to indicate success.
+		 */
+		if ((ret == -EINTR || ret == -ETIMEDOUT) &&
+		    ping_mutex_owner(&q.ping_state->ping_mutex) == current)
+			ret = 0;
+
+		/*
+		 * We are the pi_state owner but don't own the futex.
+		 * This can happen if we get picked by the previous
+		 * owner but get out without acquiring the lock for
+		 * some reason.
+		 * Wake up the next waiter and give the ping_state to them.
+		 */
 		if (ret != 0 && q.ping_state->owner == current) {
-			/*
-			 * We are pi_state owner but don't own the futex.
-			 * This can happen if we get picked by the previous
-			 * owner but get out without acquiring the lock for
-			 * some reason.
-			 * A later commit addresses this.
-			 */
-			WARN_ON_ONCE(1);
-		}
-		/* This also puts the ping_state */
-		futex_unqueue_ping(&q);
+			if (!plist_node_empty(&q.list))
+				__futex_unqueue(&q);
+			give_ping_state_to_next_waiter(hb, &q.key,
+						       q.ping_state);
+			put_ping_state(q.ping_state);
+		} else
+			/* This also puts the ping_state */
+			futex_unqueue_ping(&q);
+
 out_unlock:
 		futex_q_unlock(hb);
 		__release(q.lock_ptr);
-- 
2.55.0.1082.g2b9226bbc0-goog

[RFC PATCH 07/12] futex: Make FUTEX_*_PING use Proxy Execution.

[Suleiman Souhlal]

Set the locker side proxy execution bits, so that a task blocked on
a PING futex can act as a donor.

Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 include/linux/futex.h | 11 +++++++++++
 include/linux/sched.h | 12 ++++++++++++
 kernel/futex/ping.c   |  7 +++++++
 kernel/sched/core.c   |  7 +++++++
 4 files changed, 37 insertions(+)

diff --git a/include/linux/futex.h b/include/linux/futex.h
index b1b422b480fb..84eca792e44a 100644
--- a/include/linux/futex.h
+++ b/include/linux/futex.h
@@ -170,4 +170,15 @@ static inline struct task_struct *ping_mutex_owner(struct ping_mutex *ping_mutex
 	return READ_ONCE(ping_mutex->owner);
 }
 
+static inline void ping_mutex_lock_wait_lock(struct ping_mutex *ping_mutex)
+{
+	lockdep_assert_irqs_disabled();
+	raw_spin_lock(&ping_mutex->wait_lock);
+}
+
+static inline void ping_mutex_unlock_wait_lock(struct ping_mutex *ping_mutex)
+{
+	raw_spin_unlock(&ping_mutex->wait_lock);
+}
+
 #endif /* _LINUX_FUTEX_H */
diff --git a/include/linux/sched.h b/include/linux/sched.h
index a7de5c496e3c..200f41c38333 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -835,6 +835,7 @@ struct task_ipi_mask { };
 enum blocked_on_type {
 	BO_T_NONE,
 	BO_T_MUTEX,
+	BO_T_PING_FUTEX,
 };
 
 struct blocked_on_lock {
@@ -2257,6 +2258,13 @@ static inline void __set_task_blocked_on(struct task_struct *p, void *m,
 	p->blocked_on.type = type;
 }
 
+static inline void set_task_blocked_on(struct task_struct *p, void *m,
+				       enum blocked_on_type type)
+{
+	guard(raw_spinlock_irqsave)(&p->blocked_lock);
+	__set_task_blocked_on(p, m, type);
+}
+
 static inline void __clear_task_blocked_on(struct task_struct *p, void *m)
 {
 	/* Currently we serialize blocked_on under the task::blocked_lock */
@@ -2278,6 +2286,10 @@ static inline void clear_task_blocked_on(struct task_struct *p, void *m)
 }
 
 #else
+static inline void set_task_blocked_on(struct task_struct *p, void *m,
+				       enum blocked_on_type type)
+{
+}
 static inline void __clear_task_blocked_on(struct task_struct *p, void *m)
 {
 }
diff --git a/kernel/futex/ping.c b/kernel/futex/ping.c
index ebcd3c4a7793..689f149f7150 100644
--- a/kernel/futex/ping.c
+++ b/kernel/futex/ping.c
@@ -370,6 +370,9 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 
 		queued = false;
 		while (1) {
+			set_task_blocked_on(current, &q.ping_state->ping_mutex,
+					    BO_T_PING_FUTEX);
+
 			set_current_state(TASK_INTERRUPTIBLE|TASK_FREEZABLE);
 			if (!queued) {
 				futex_queue(&q, hb, current);
@@ -382,6 +385,9 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 
 			futex_do_wait(&q, to);
 
+			clear_task_blocked_on(current,
+					      &q.ping_state->ping_mutex);
+
 			futex_q_lockptr_lock(&q);
 			if (to && !to->task) {
 				ret = -ETIMEDOUT;
@@ -511,6 +517,7 @@ int futex_unlock_ping(u32 __user *uaddr, unsigned int flags)
 	/* Leave it queued, it gets unqueued on the lock side */
 	get_task_struct(top_waiter->task);
 	wake_q_add_safe(&wake_q, top_waiter->task);
+	clear_task_blocked_on(top_waiter->task, &ping_state->ping_mutex);
 	spin_unlock(&hb->lock);
 
 	/*
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 2e8fe4b9bb88..1d35b1d90ea2 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -68,6 +68,7 @@
 #include <linux/wait_api.h>
 #include <linux/workqueue_api.h>
 #include <linux/livepatch_sched.h>
+#include <linux/futex.h>
 
 #ifdef CONFIG_PREEMPT_DYNAMIC
 # ifdef CONFIG_GENERIC_IRQ_ENTRY
@@ -158,6 +159,8 @@ static inline struct task_struct *__blocked_on_owner(struct blocked_on_lock *bo)
 		return NULL;
 	case BO_T_MUTEX:
 		return __mutex_owner(bo->lock);
+	case BO_T_PING_FUTEX:
+		return ping_mutex_owner(bo->lock);
 	default:
 		WARN_ON_ONCE(1);
 		return NULL;
@@ -6907,6 +6910,8 @@ lock_blocked_on_lock(struct blocked_on_lock *bo)
 {
 	if (bo->type == BO_T_MUTEX)
 		raw_spin_lock(&((struct mutex *)bo->lock)->wait_lock);
+	else if (bo->type == BO_T_PING_FUTEX)
+		ping_mutex_lock_wait_lock(bo->lock);
 	else
 		WARN_ON_ONCE(1);
 }
@@ -6916,6 +6921,8 @@ unlock_blocked_on_lock(struct blocked_on_lock *bo)
 {
 	if (bo->type == BO_T_MUTEX)
 		raw_spin_unlock(&((struct mutex *)bo->lock)->wait_lock);
+	else if (bo->type == BO_T_PING_FUTEX)
+		ping_mutex_unlock_wait_lock(bo->lock);
 	else
 		WARN_ON_ONCE(1);
 }
-- 
2.55.0.1082.g2b9226bbc0-goog

[RFC PATCH 08/12] futex: Implement PING futex handoff.

[Suleiman Souhlal]

Implement handoff for PING futexes, to prevent starvation in case of
a waiter being repeatedly stolen from.

Currently engages after being stolen from once, after which the next
unlocker hands off the futex such that it can't be stolen.

Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 kernel/futex/futex.h |  2 ++
 kernel/futex/ping.c  | 45 ++++++++++++++++++++++++++++++++++----------
 2 files changed, 37 insertions(+), 10 deletions(-)

diff --git a/kernel/futex/futex.h b/kernel/futex/futex.h
index c0560d30aaaa..113289779dd1 100644
--- a/kernel/futex/futex.h
+++ b/kernel/futex/futex.h
@@ -174,6 +174,8 @@ struct futex_pi_state {
 
 	struct task_struct *owner;
 	refcount_t refcount;
+	bool handoff;
+	bool pickup;
 
 	union futex_key key;
 } __randomize_layout;
diff --git a/kernel/futex/ping.c b/kernel/futex/ping.c
index 689f149f7150..5bf2293bf582 100644
--- a/kernel/futex/ping.c
+++ b/kernel/futex/ping.c
@@ -7,7 +7,8 @@
 #include "futex.h"
 
 static int futex_trylock_ping_state(u32 __user *uaddr,
-				    struct futex_pi_state *ping_state);
+				    struct futex_pi_state *ping_state,
+				    bool handoff);
 
 static void ping_state_update_owner(struct futex_pi_state *ping_state,
 				    struct task_struct *new_owner)
@@ -144,7 +145,8 @@ static void give_ping_state_to_next_waiter(struct futex_hash_bucket *hb,
 
 /* Returns >0 if lock acquired, <0 on error */
 static int futex_trylock_ping_state(u32 __user *uaddr,
-				    struct futex_pi_state *ping_state)
+				    struct futex_pi_state *ping_state,
+				    bool handoff)
 {
 	struct task_struct *owner;
 	u32 uval, new, newtid;
@@ -152,13 +154,15 @@ static int futex_trylock_ping_state(u32 __user *uaddr,
 
 	ret = 0;
 	raw_spin_lock_irq(&ping_state->ping_mutex.wait_lock);
+	ret = futex_get_value_locked(&uval, uaddr);
+	if (ret)
+		goto err;
 	owner = ping_mutex_owner(&ping_state->ping_mutex);
 	if (owner == NULL) {
 		newtid = task_pid_vnr(current);
 
-		ret = futex_get_value_locked(&uval, uaddr);
-		if (ret)
-			goto err;
+		WARN_ON_ONCE(ping_state->handoff || ping_state->pickup);
+
 		if (uval & FUTEX_TID_MASK) {
 			ret = -EAGAIN;
 			goto err;
@@ -171,7 +175,19 @@ static int futex_trylock_ping_state(u32 __user *uaddr,
 			ping_state_update_owner(ping_state, current);
 		WRITE_ONCE(ping_state->ping_mutex.owner, current);
 		ret = 1;
-	}
+	} else if (ping_state->pickup) {
+		if (owner != current) {
+			ret = -EAGAIN;
+			goto err;
+		}
+		if ((uval & FUTEX_TID_MASK) != task_pid_vnr(current)) {
+			ret = -EINVAL;
+			goto err;
+		}
+		ping_state->pickup = 0;
+		ret = 1;
+	} else if (handoff && !ping_state->handoff)
+		ping_state->handoff = 1;
 	raw_spin_unlock_irq(&ping_state->ping_mutex.wait_lock);
 	return ret;
 
@@ -233,7 +249,7 @@ static int futex_lock_ping_atomic(u32 __user *uaddr,
 		_ps = top_waiter->ping_state;
 		if (_ps == NULL)
 			return -EINVAL;
-		ret = futex_trylock_ping_state(uaddr, _ps);
+		ret = futex_trylock_ping_state(uaddr, _ps, false);
 		if (ret > 0) {
 			/* We stole the lock from the top waiter. */
 			raw_spin_lock_irq(&_ps->ping_mutex.wait_lock);
@@ -297,7 +313,7 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 	struct hrtimer_sleeper timeout, *to;
 	struct task_struct *exiting;
 	struct futex_q q = futex_q_init;
-	bool queued;
+	bool queued, should_handoff;
 	int ret;
 
 	if (refill_pi_state_cache())
@@ -369,6 +385,7 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 		}
 
 		queued = false;
+		should_handoff = false;
 		while (1) {
 			set_task_blocked_on(current, &q.ping_state->ping_mutex,
 					    BO_T_PING_FUTEX);
@@ -398,13 +415,15 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 				goto out_unqueue;
 			}
 
-			ret = futex_trylock_ping_state(uaddr, q.ping_state);
+			ret = futex_trylock_ping_state(uaddr, q.ping_state,
+						       should_handoff);
 			if (ret > 0) {
 				/* Got the futex */
 				ret = 0;
 				goto out_unqueue;
 			} else if (ret < 0)
 				goto out_unqueue;
+			should_handoff = true;
 		}
 
 out_unqueue:
@@ -526,6 +545,13 @@ int futex_unlock_ping(u32 __user *uaddr, unsigned int flags)
 	 * no top_waiter.
 	 */
 	new = FUTEX_WAITERS;
+	if (ping_state->handoff) {
+		new |= task_pid_vnr(top_waiter->task);
+		ping_state->handoff = 0;
+		ping_state->pickup = 1;
+		WRITE_ONCE(ping_state->ping_mutex.owner, top_waiter->task);
+	} else
+		WRITE_ONCE(ping_state->ping_mutex.owner, NULL);
 	ret = lock_pi_update_atomic(uaddr, uval, new);
 	if (ret) {
 		raw_spin_unlock_irq(&ping_state->ping_mutex.wait_lock);
@@ -543,7 +569,6 @@ int futex_unlock_ping(u32 __user *uaddr, unsigned int flags)
 	}
 
 	ping_state_update_owner(ping_state, top_waiter->task);
-	WRITE_ONCE(ping_state->ping_mutex.owner, NULL);
 	raw_spin_unlock_irq_wake(&ping_state->ping_mutex.wait_lock, &wake_q);
 	put_ping_state(ping_state);
 	return 0;
-- 
2.55.0.1082.g2b9226bbc0-goog

[RFC PATCH 09/12] futex: Wake up donor in PING futex unlock.

[Suleiman Souhlal]

Now that PING blockers can act as donors, it makes sense to wake up
the donor instead of the top_waiter when unlocking.

Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 kernel/futex/ping.c | 56 +++++++++++++++++++++++++++++++++++++--------
 1 file changed, 46 insertions(+), 10 deletions(-)

diff --git a/kernel/futex/ping.c b/kernel/futex/ping.c
index 5bf2293bf582..df701b437f16 100644
--- a/kernel/futex/ping.c
+++ b/kernel/futex/ping.c
@@ -478,10 +478,46 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 	return ret;
 }
 
+#ifdef CONFIG_SCHED_PROXY_EXEC
+static inline
+struct task_struct *ping_current_proxy_donor(struct futex_pi_state *ping_state)
+{
+	struct task_struct *ret = NULL;
+
+	if (sched_proxy_exec()) {
+		struct task_struct *donor;
+
+		raw_spin_lock(&current->blocked_lock);
+		donor = current->blocked_donor;
+		if (donor) {
+			void *ping_lock = (void *)&ping_state->ping_mutex;
+
+			raw_spin_lock_nested(&donor->blocked_lock,
+					     SINGLE_DEPTH_NESTING);
+			if (__get_task_blocked_on(donor) == ping_lock) {
+				ret = get_task_struct(donor);
+				__clear_task_blocked_on(donor, ping_lock);
+				current->blocked_donor = NULL;
+			}
+			raw_spin_unlock(&donor->blocked_lock);
+		}
+		raw_spin_unlock(&current->blocked_lock);
+	}
+	return ret;
+}
+#else
+static inline
+struct task_struct *ping_current_proxy_donor(struct futex_pi_state *ping_state)
+{
+	return NULL;
+}
+#endif
+
 int futex_unlock_ping(u32 __user *uaddr, unsigned int flags)
 {
 	struct futex_pi_state *ping_state;
 	u32 new, uval, vpid = task_pid_vnr(current);
+	struct task_struct *next;
 	union futex_key key = FUTEX_KEY_INIT;
 	struct futex_q *top_waiter;
 	DEFINE_WAKE_Q(wake_q);
@@ -528,15 +564,15 @@ int futex_unlock_ping(u32 __user *uaddr, unsigned int flags)
 	if (!ping_state)
 		goto out_unlock;
 	raw_spin_lock_irq(&ping_state->ping_mutex.wait_lock);
-	if (ping_state->owner != current) {
-		raw_spin_unlock_irq(&ping_state->ping_mutex.wait_lock);
-		goto out_unlock;
-	}
+
+	next = ping_current_proxy_donor(ping_state);
 	get_ping_state(ping_state);
 	/* Leave it queued, it gets unqueued on the lock side */
-	get_task_struct(top_waiter->task);
-	wake_q_add_safe(&wake_q, top_waiter->task);
-	clear_task_blocked_on(top_waiter->task, &ping_state->ping_mutex);
+	if (next == NULL) {
+		next = get_task_struct(top_waiter->task);
+		clear_task_blocked_on(next, &ping_state->ping_mutex);
+	}
+	wake_q_add_safe(&wake_q, next);
 	spin_unlock(&hb->lock);
 
 	/*
@@ -546,10 +582,10 @@ int futex_unlock_ping(u32 __user *uaddr, unsigned int flags)
 	 */
 	new = FUTEX_WAITERS;
 	if (ping_state->handoff) {
-		new |= task_pid_vnr(top_waiter->task);
+		new |= task_pid_vnr(next);
 		ping_state->handoff = 0;
 		ping_state->pickup = 1;
-		WRITE_ONCE(ping_state->ping_mutex.owner, top_waiter->task);
+		WRITE_ONCE(ping_state->ping_mutex.owner, next);
 	} else
 		WRITE_ONCE(ping_state->ping_mutex.owner, NULL);
 	ret = lock_pi_update_atomic(uaddr, uval, new);
@@ -568,7 +604,7 @@ int futex_unlock_ping(u32 __user *uaddr, unsigned int flags)
 		}
 	}
 
-	ping_state_update_owner(ping_state, top_waiter->task);
+	ping_state_update_owner(ping_state, next);
 	raw_spin_unlock_irq_wake(&ping_state->ping_mutex.wait_lock, &wake_q);
 	put_ping_state(ping_state);
 	return 0;
-- 
2.55.0.1082.g2b9226bbc0-goog

[RFC PATCH 10/12] futex: Optimistic spinning for PING futexes.

[Suleiman Souhlal]

This allows a thread to spin on the owner of the futex instead of
unconditionally spinning, if the owner is currently running on
another CPU.

TODO: Currently allows every task to attempt to spin at the same time.
In the future, spinning will probably either use an osq or only the
top waiter will be allowed to wait. We've seen some long latencies
when using an osq that we still need to investigate.

Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 kernel/futex/ping.c | 80 +++++++++++++++++++++++++++++++++++++--------
 1 file changed, 67 insertions(+), 13 deletions(-)

diff --git a/kernel/futex/ping.c b/kernel/futex/ping.c
index df701b437f16..e5765b2d3834 100644
--- a/kernel/futex/ping.c
+++ b/kernel/futex/ping.c
@@ -301,6 +301,50 @@ static int futex_lock_ping_atomic(u32 __user *uaddr,
 	return attach_to_pi_owner(uaddr, newval, key, ps, exiting, true);
 }
 
+/*
+ * Returns >0 on successfully having taken the lock, <0 on error
+ */
+static int ping_spin_or_trylock(u32 __user *uaddr,
+				struct futex_pi_state *ping_state,
+				bool handoff)
+{
+	struct task_struct *owner = ping_mutex_owner(&ping_state->ping_mutex);
+	struct task_struct *new;
+	int ret;
+
+	if (owner && !owner_on_cpu(owner))
+		return 0;
+
+	/*
+	 * XXX We'll want to try to limit spinning either with an osq or
+	 * by only allowing the top waiter to spin.
+	 */
+
+	while (1) {
+		new = ping_mutex_owner(&ping_state->ping_mutex);
+		ret = 0;
+		if (!owner || !new || new == current) {
+			ret = futex_trylock_ping_state(uaddr, ping_state,
+			    handoff);
+			if (ret != 0)
+				break;
+			/* Spin on new owner if we didn't get the lock */
+			owner = ping_mutex_owner(&ping_state->ping_mutex);
+			goto next;
+		}
+		if (new != owner) {
+			owner = ping_mutex_owner(&ping_state->ping_mutex);
+			goto next;
+		}
+		if (!owner_on_cpu(owner) || need_resched())
+			break;
+next:
+		cpu_relax();
+	}
+
+	return ret;
+}
+
 /*
  * Return values:
  *     < 0: error.
@@ -387,9 +431,6 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 		queued = false;
 		should_handoff = false;
 		while (1) {
-			set_task_blocked_on(current, &q.ping_state->ping_mutex,
-					    BO_T_PING_FUTEX);
-
 			set_current_state(TASK_INTERRUPTIBLE|TASK_FREEZABLE);
 			if (!queued) {
 				futex_queue(&q, hb, current);
@@ -400,6 +441,26 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 				__release(q->lock_ptr);
 			}
 
+			preempt_disable();
+			set_current_state(TASK_INTERRUPTIBLE|TASK_FREEZABLE);
+			ret = ping_spin_or_trylock(uaddr, q.ping_state,
+						   should_handoff);
+			if (ret > 0) {
+				/* Got the futex */
+				ret = 0;
+				preempt_enable();
+				futex_q_lockptr_lock(&q);
+				goto out_unqueue;
+			} else if (ret < 0) {
+				preempt_enable();
+				futex_q_lockptr_lock(&q);
+				goto out_unqueue;
+			}
+			preempt_enable();
+
+			set_task_blocked_on(current, &q.ping_state->ping_mutex,
+					    BO_T_PING_FUTEX);
+
 			futex_do_wait(&q, to);
 
 			clear_task_blocked_on(current,
@@ -414,19 +475,12 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 				ret = -EINTR;
 				goto out_unqueue;
 			}
-
-			ret = futex_trylock_ping_state(uaddr, q.ping_state,
-						       should_handoff);
-			if (ret > 0) {
-				/* Got the futex */
-				ret = 0;
-				goto out_unqueue;
-			} else if (ret < 0)
-				goto out_unqueue;
 			should_handoff = true;
 		}
 
 out_unqueue:
+		__set_current_state(TASK_RUNNING);
+
 		/*
 		 * We got a pending signal or timeout, but the futex was handed
 		 * off to us. Fix up the return value to indicate success.
@@ -581,7 +635,7 @@ int futex_unlock_ping(u32 __user *uaddr, unsigned int flags)
 	 * no top_waiter.
 	 */
 	new = FUTEX_WAITERS;
-	if (ping_state->handoff) {
+	if (ping_state->handoff) { /* Don't handoff to donor */
 		new |= task_pid_vnr(next);
 		ping_state->handoff = 0;
 		ping_state->pickup = 1;
-- 
2.55.0.1082.g2b9226bbc0-goog

[RFC PATCH 11/12] futex: Allow userspace stealing for PING futexes.

[Suleiman Souhlal]

Similarly to how the kernel part of PING locking can steal the futex
from the top waiter, it is also possible for userspace to also take
advantage of this and try to steal without going to the kernel.

When a new (contending) locker notices that the lock has been stolen
from userspace, the ownership of the ping_state and the ping_mutex
are fixed up to the real owner.

TODO: Verify that the case where the ping_state owner exits with the
  futex having been user stolen is handled correctly.
  In other words, when ping_state->owner = task getting killed,
  ping_mutex.owner = NULL and uval = real owner (set by userspace).
  Right now, it seems like we might be doing the wrong thing in such
  cases. exit_ping_state_list() needs to detect such situations
  (by walking the uvals?) and fixup the ownerships.

Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 kernel/futex/core.c  |  8 ++++++++
 kernel/futex/futex.h |  2 ++
 kernel/futex/pi.c    | 12 ++++++++++--
 kernel/futex/ping.c  | 38 +++++++++++++++++++++++++++++++++++---
 4 files changed, 55 insertions(+), 5 deletions(-)

diff --git a/kernel/futex/core.c b/kernel/futex/core.c
index 56c7e2d5faac..023531c4b45a 100644
--- a/kernel/futex/core.c
+++ b/kernel/futex/core.c
@@ -1445,6 +1445,14 @@ static void exit_ping_state_list(struct task_struct *curr)
 	while (!list_empty(head)) {
 		next = head->next;
 		ping_state = list_entry(next, struct futex_pi_state, list);
+		/*
+		 * XXX In the case when we are ping_state owner but
+		 * the futex is actually owned by someone who stole it
+		 * from userspace, is setting ping_state.owner = NULL here
+		 * enough? Probably not, otherwise the ping_state could leak
+		 * if they also exit before unlocking or someone else
+		 * fixing up the ownership.
+		 */
 		if (1) {
 			CLASS(hbr, hbr)(&key);
 			auto hb = hbr.hb;
diff --git a/kernel/futex/futex.h b/kernel/futex/futex.h
index 113289779dd1..922d130c5b44 100644
--- a/kernel/futex/futex.h
+++ b/kernel/futex/futex.h
@@ -413,6 +413,8 @@ extern int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
 			      bool ping);
 extern void get_ping_state(struct futex_pi_state *ping_state);
 extern void put_ping_state(struct futex_pi_state *ping_state);
+extern int fixup_ping_owner_after_user_steal(struct futex_pi_state *ping_state,
+				      u32 __user *uaddr, u32 uval);
 
 /*
  * Express the locking dependencies for lockdep:
diff --git a/kernel/futex/pi.c b/kernel/futex/pi.c
index e7e6e347f97d..dfd2da5188b0 100644
--- a/kernel/futex/pi.c
+++ b/kernel/futex/pi.c
@@ -348,8 +348,16 @@ int attach_to_pi_state(u32 __user *uaddr, u32 uval,
 	 * state exists then the owner TID must be the same as the
 	 * user space TID. [9/10]
 	 */
-	if (pid != task_pid_vnr(pi_state->owner))
-		goto out_einval;
+	if (pid != task_pid_vnr(pi_state->owner)) {
+		if (!ping) {
+			goto out_einval;
+		} else {
+			ret = fixup_ping_owner_after_user_steal(pi_state,
+								uaddr, uval);
+			if (ret)
+				goto out_error;
+		}
+	}
 
 out_attach:
 	if (!ping) {
diff --git a/kernel/futex/ping.c b/kernel/futex/ping.c
index e5765b2d3834..4cef1c46b4c6 100644
--- a/kernel/futex/ping.c
+++ b/kernel/futex/ping.c
@@ -96,6 +96,22 @@ put_ping_state(struct futex_pi_state *ping_state)
 	}
 }
 
+int fixup_ping_owner_after_user_steal(struct futex_pi_state *ping_state,
+				      u32 __user *uaddr, u32 uval)
+{
+	struct task_struct *p;
+
+	p = find_get_task_by_vpid(uval & FUTEX_TID_MASK);
+	if (p == NULL)
+		return pi_handle_exit_race(uaddr, uval);
+	if (unlikely(p->flags & PF_KTHREAD))
+		return -EPERM;
+	ping_state_update_owner(ping_state, p);
+	WRITE_ONCE(ping_state->ping_mutex.owner, p);
+
+	return 0;
+}
+
 static void futex_unqueue_ping(struct futex_q *q)
 {
 	if (!plist_node_empty(&q->list))
@@ -149,6 +165,7 @@ static int futex_trylock_ping_state(u32 __user *uaddr,
 				    bool handoff)
 {
 	struct task_struct *owner;
+	pid_t pid;
 	u32 uval, new, newtid;
 	int ret;
 
@@ -163,8 +180,17 @@ static int futex_trylock_ping_state(u32 __user *uaddr,
 
 		WARN_ON_ONCE(ping_state->handoff || ping_state->pickup);
 
-		if (uval & FUTEX_TID_MASK) {
-			ret = -EAGAIN;
+		/*
+		 * No owner but a userspace TID means that it got stolen
+		 * from userspace.
+		 * Fix up the ownership.
+		 */
+		pid = uval & FUTEX_TID_MASK;
+		if (pid) {
+			ret = fixup_ping_owner_after_user_steal(ping_state,
+								uaddr, uval);
+			if (ret == 0)
+				ret = -EAGAIN;
 			goto err;
 		}
 		new = newtid | FUTEX_WAITERS;
@@ -203,7 +229,7 @@ static int futex_trylock_ping_state(u32 __user *uaddr,
 	case -EINVAL:
 		break;
 	default:
-		WARN_ON(1);
+		break;
 	}
 	return ret;
 }
@@ -619,6 +645,12 @@ int futex_unlock_ping(u32 __user *uaddr, unsigned int flags)
 		goto out_unlock;
 	raw_spin_lock_irq(&ping_state->ping_mutex.wait_lock);
 
+	/*
+	 * If we're unlocking a lock we stole from userspace,
+	 * it's possible that we don't own the ping_state or the
+	 * ping_mutex. But we'll give them to the next task here anyway.
+	 */
+
 	next = ping_current_proxy_donor(ping_state);
 	get_ping_state(ping_state);
 	/* Leave it queued, it gets unqueued on the lock side */
-- 
2.55.0.1082.g2b9226bbc0-goog

[RFC PATCH 12/12] tools/testing/futex: Add ping_bench, a tool for benchmarking futexes.

[Suleiman Souhlal]

It can generate metrics across a number of configurations, measuring
how long locking takes.

It prints out lock call durations for the foreground thread to
stdout (unless -q is passed), for analysis with other tools such as
ministat or turning into histograms.

Some parameters:
    -a:  Print out durations for all threads instead of only for the
         foreground thread.
    -q:  Don't print out locking durations.
    -f:  Type of futex ("f" FUTEX_WAIT, "p" FUTEX_LOCK_PI,
         "n" FUTEX_LOCK_PING, "N" FUTEX_LOCK_PING with userspace stealing,
         "m" pthread_mutex_t).
    -t:  Number of threads acquiring/releasing the lock.
    -n:  Number of iterations the threads will take the lock.
    -s:  How frequently a thread tries to take the lock.
    -S:  Duration in usec to sleep instead of spinning after unlocking
         (use instead of -s).
    -w:  Lock hold time.
    -b:  Number of “busy” cpu spinner threads.
    -r:  Number of threads using RT prio.
    -p:  Use nice() biasing (foreground thread gets more cpu time,
         background threads get less - allows for priority inversions).

Co-developed-by: John Stultz <jstultz@google.com>
Signed-off-by: John Stultz <jstultz@google.com>
Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 tools/testing/futex/Makefile     |  13 +
 tools/testing/futex/ping_bench.c | 428 +++++++++++++++++++++++++++++++
 2 files changed, 441 insertions(+)
 create mode 100644 tools/testing/futex/Makefile
 create mode 100644 tools/testing/futex/ping_bench.c

diff --git a/tools/testing/futex/Makefile b/tools/testing/futex/Makefile
new file mode 100644
index 000000000000..cbb2deb30923
--- /dev/null
+++ b/tools/testing/futex/Makefile
@@ -0,0 +1,13 @@
+# SPDX-License-Identifier: GPL-2.0
+
+.PHONY: clean
+
+TARGETS = ping_bench
+CFLAGS = -O -Wall -g
+OFILES = ping_bench.o
+TARGETS = ping_bench
+
+ping_bench: $(OFILES)
+
+clean:
+	$(RM) $(TARGETS) $(OFILES)
diff --git a/tools/testing/futex/ping_bench.c b/tools/testing/futex/ping_bench.c
new file mode 100644
index 000000000000..418e147174d0
--- /dev/null
+++ b/tools/testing/futex/ping_bench.c
@@ -0,0 +1,428 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#define _GNU_SOURCE
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdatomic.h>
+#include <string.h>
+#include <stdbool.h>
+#include <err.h>
+#include <unistd.h>
+#include <stdint.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <string.h>
+#include <time.h>
+#include <stdatomic.h>
+#include <stdarg.h>
+#include <pthread.h>
+#include <limits.h>
+#include <linux/futex.h>
+#include <sys/prctl.h>
+#include <sys/syscall.h>
+#include <sys/time.h>
+
+#define	MAX_THR 512
+
+#define	FUTEX_LOCK_PING		14
+#define	FUTEX_UNLOCK_PING	15
+
+#define	READ_ONCE(x) (*(volatile typeof(x) *)&(x))
+
+struct thread {
+	pthread_t pthr;
+	uint64_t *dur;
+	int id;
+};
+
+static struct thread bthr[MAX_THR];
+static struct thread thr[MAX_THR];
+static pthread_barrier_t bar;
+
+uint32_t _lock;
+pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
+void *lock = &_lock;
+
+static long counter;
+static int num_thr;
+static int num_rt;
+static int busy_thr;
+static uint64_t num_iter = 10000;
+static  __thread pid_t tid;
+static int work_times = 100000;
+static uint64_t sleep_dur = 1000;
+static bool do_sleep;
+static bool print_all;
+static bool quiet;
+static bool bias;
+
+enum futex_type {
+	FUTEX,
+	FUTEX_PI,
+	FUTEX_PING,
+	FUTEX_PING_USTEAL,
+	MUTEX,
+};
+static enum futex_type futex_type = FUTEX_PING;
+
+extern char *optarg;
+extern int optind;
+
+int trace_marker_fd;
+
+static void
+init_trace_marker(void)
+{
+	trace_marker_fd = open("/sys/kernel/tracing/trace_marker", O_WRONLY);
+	if (trace_marker_fd < 0)
+		perror("Failed to open trace_marker");
+}
+
+static int
+write_trace_marker(const char *format, ...)
+{
+	char buffer[256];
+	va_list args;
+	int len;
+
+	if (trace_marker_fd <= 0)
+		return -1;
+
+	va_start(args, format);
+	len = vsnprintf(buffer, sizeof(buffer), format, args);
+	va_end(args);
+
+	if (len > 0)
+		write(trace_marker_fd, buffer, len);
+
+	return (0);
+}
+
+static inline uint64_t
+now_ns(void)
+{
+	struct timespec ts;
+
+	if (clock_gettime(CLOCK_MONOTONIC, &ts) != 0)
+		err(1, "clock_gettime");
+
+	return (ts.tv_sec * 1000000000UL + ts.tv_nsec);
+}
+
+static int
+futex(uint32_t *uaddr, int op, uint32_t val, struct timespec *to)
+{
+	return (syscall(SYS_futex, uaddr, op, val, to));
+}
+
+static void
+futex_lock(void *lock)
+{
+	pthread_mutex_t *mu;
+	uint32_t *fu, old;
+	int ret;
+
+	fu = lock;
+	mu = lock;
+	switch (futex_type) {
+	case FUTEX:
+		while (1) {
+			old = 0;
+			if (atomic_compare_exchange_strong(fu, &old, 1))
+				return;
+			if (futex(fu, FUTEX_WAIT, 1, NULL) != 0 && errno !=
+			    EAGAIN)
+				err(1, "FUTEX_WAIT");
+		}
+		break;
+	case FUTEX_PI:
+		old = 0;
+		if (atomic_compare_exchange_strong(fu, &old, tid))
+			return;
+		if ((ret = futex(fu, FUTEX_LOCK_PI, 0, NULL)) != 0)
+			errx(1, "FUTEX_LOCK_PI %s", strerror(ret));
+		break;
+	case FUTEX_PING:
+	case FUTEX_PING_USTEAL:
+		old = 0;
+		if (atomic_compare_exchange_strong(fu, &old, tid))
+			return;
+		old = FUTEX_WAITERS;
+		if (futex_type == FUTEX_PING_USTEAL &&
+		    atomic_compare_exchange_strong(fu, &old, tid |
+		    FUTEX_WAITERS))
+			return;
+		if ((ret = futex(fu, FUTEX_LOCK_PING, 0, NULL)) != 0)
+			err(1, "FUTEX_LOCK_PING");
+		break;
+	case MUTEX:
+		if (pthread_mutex_lock(mu) < 0)
+			err(1, "pthread_mutex_lock");
+		break;
+	}
+}
+
+static void
+futex_unlock(void *lock)
+{
+	pthread_mutex_t *mu;
+	uint32_t *fu, old;
+
+	fu = lock;
+	mu = lock;
+	switch (futex_type) {
+	case FUTEX:
+		old = 1;
+		if (atomic_compare_exchange_strong(fu, &old, 0))
+			if (futex(fu, FUTEX_WAKE, 1, NULL) < 0)
+				err(1, "FUTEX_WAKE");
+		break;
+	case FUTEX_PI:
+		old = tid;
+		if (atomic_compare_exchange_strong(fu, &old, 0))
+			return;
+		if (futex(fu, FUTEX_UNLOCK_PI, 0, NULL) != 0)
+			err(1, "FUTEX_UNLOCK_PI t %x old %x", tid,
+			    READ_ONCE(*fu));
+		break;
+	case FUTEX_PING:
+	case FUTEX_PING_USTEAL:
+		old = tid;
+		if (atomic_compare_exchange_strong(fu, &old, 0))
+			return;
+		if (futex(fu, FUTEX_UNLOCK_PING, 0, NULL) != 0)
+			err(1, "FUTEX_UNLOCK_PING t %x old %x", tid,
+			    READ_ONCE(*fu));
+		break;
+	case MUTEX:
+		if (pthread_mutex_unlock(mu) < 0)
+			err(1, "pthread_mutex_unlock");
+		break;
+	}
+}
+
+atomic_int stop_spinners = 0;
+
+static void *
+func(void *p)
+{
+	struct thread *thr;
+	uint64_t end, start;
+	uint64_t i, j, _num_iter;
+	uint64_t my_sleep_dur = sleep_dur;
+	uint64_t my_work_times = work_times;
+	struct timespec ts;
+
+	tid = gettid();
+
+	thr = p;
+	thr->dur = malloc(num_iter * sizeof(uint64_t));
+	_num_iter = num_iter;
+
+	if (thr->id == 0) {
+		prctl(PR_SET_NAME, "foreground", 0, 0, 0);
+		if (bias) {
+			nice(-5);
+			my_sleep_dur *= 10;
+			if (my_work_times)
+				my_work_times /= 10;
+		}
+	} else {
+		prctl(PR_SET_NAME, "background", 0, 0, 0);
+		if (bias) {
+			if (my_sleep_dur)
+				my_sleep_dur /= 10;
+			my_work_times *= 10;
+			nice(19);
+		}
+	}
+
+	ts.tv_sec  = my_sleep_dur / 1000000;
+	ts.tv_nsec = (my_sleep_dur % 1000000) * 1000;
+
+
+	if (thr->id < num_rt) {
+		struct sched_param param = { .sched_priority = 10 };
+
+		if (sched_setscheduler(0, SCHED_FIFO, &param) != 0)
+			err(1, "sched_setscheduler");
+	}
+
+	pthread_barrier_wait(&bar);
+
+	for (i = 0; i < _num_iter; i++) {
+		if (thr->id == 0)
+			write_trace_marker("B|%lu|Locking", (unsigned long)tid);
+
+		start = now_ns();
+		futex_lock(lock);
+		end = now_ns();
+
+		if (thr->id == 0)
+			write_trace_marker("E|%lu|Locking", (unsigned long)tid);
+		thr->dur[i] = end - start;
+
+		for (j = 0; j < my_work_times; j++)
+			__asm __volatile("" ::: "memory");
+
+		counter++;
+		futex_unlock(lock);
+
+		if (atomic_load(&stop_spinners))
+			break;
+
+		if (sleep_dur) {
+			if (do_sleep)
+				clock_nanosleep(CLOCK_MONOTONIC, 0, &ts, 0);
+			else
+				for (j = 0; j < my_sleep_dur; j++)
+					__asm __volatile("" ::: "memory");
+		}
+	}
+
+	if (thr->id == 0)
+		atomic_store(&stop_spinners, 1);
+	return (NULL);
+}
+
+static void *
+busy(void *p)
+{
+	prctl(PR_SET_NAME, "spinner", 0, 0, 0);
+	if (0 &&  num_rt) {
+		struct sched_param param = { .sched_priority = 1 };
+
+		if (sched_setscheduler(0, SCHED_FIFO, &param) != 0)
+			err(1, "sched_setscheduler");
+	}
+
+	pthread_barrier_wait(&bar);
+
+	while (!atomic_load(&stop_spinners))
+		__asm __volatile("" ::: "memory");
+
+	return (NULL);
+}
+
+
+static void
+usage(char *a)
+{
+	fprintf(stderr, "Usage: %s [-a] [-b n] [-c] [-f f/m/n/N/p] [-n n] [-q]"
+	    " [-r n] [-s n] [-S n] [-t n] [-w n]\n", a);
+	exit(1);
+}
+
+int
+main(int argc, char **argv)
+{
+	int c, i, j, ret;
+
+	while ((c = getopt(argc, argv, "ab:f:n:pqr:S:s:t:w:")) != -1) {
+		switch (c) {
+		case 'a':
+			print_all = 1;
+			break;
+		case 'f':
+			switch (*optarg) {
+			case 'f':
+				futex_type = FUTEX;
+				break;
+			case 'm':
+				futex_type = MUTEX;
+				lock = &mtx;
+				break;
+			case 'n':
+				futex_type = FUTEX_PING;
+				break;
+			case 'N':
+				futex_type = FUTEX_PING_USTEAL;
+				break;
+			case 'p':
+				futex_type = FUTEX_PI;
+				break;
+			default:
+				usage(argv[0]);
+			}
+			break;
+		case 'n':
+			num_iter = atoi(optarg);
+			break;
+		case 'q':
+			quiet = 1;
+			break;
+		case 'p':
+			bias = 1;
+			break;
+		case 'r':
+			num_rt = atoi(optarg);
+			break;
+		case 'S':
+			do_sleep = 1;
+			/* Fallthrough */
+		case 's':
+			sleep_dur = atoi(optarg);
+			break;
+		case 't':
+			num_thr = atoi(optarg);
+			break;
+		case 'b':
+			busy_thr = atoi(optarg);
+			break;
+		case 'w':
+			work_times = atoi(optarg);
+			break;
+		default:
+			usage(argv[0]);
+		}
+	}
+
+	init_trace_marker();
+
+	if (num_thr < num_rt)
+		num_thr = num_rt;
+
+	num_thr -= num_rt;
+	if (num_thr > MAX_THR)
+		num_thr = MAX_THR;
+
+	tid = gettid();
+
+	ret = pthread_barrier_init(&bar, NULL, num_thr + num_rt + busy_thr);
+	if (ret != 0)
+		errx(1, "pthread_barrier_init %s", strerror(ret));
+
+	for (i = 0; i < num_thr + num_rt; i++) {
+		thr[i].id = i;
+		if ((ret = pthread_create(&thr[i].pthr, NULL, func, &thr[i]))
+		    != 0)
+			errx(1, "pthread_create %d: %s", i, strerror(ret));
+	}
+	
+	for (i = 0; i < busy_thr; i++) {
+		if ((ret = pthread_create(&bthr[i].pthr, NULL, busy, &bthr[i]))
+		    != 0)
+			errx(1, "pthread_create %d: %s", i, strerror(ret));
+	}
+
+	for (i = 0; i < busy_thr; i++)
+		if ((ret = pthread_join(bthr[i].pthr, NULL)) != 0)
+			errx(1, "pthread_join: %s\n", strerror(ret));
+
+	for (i = 0; i < num_thr + num_rt; i++)
+		if ((ret = pthread_join(thr[i].pthr, NULL)) != 0)
+			errx(1, "pthread_join: %s\n", strerror(ret));
+
+	if (!quiet) {
+		/* skip the first run */
+		if (print_all)
+			for (i = 0; i < num_thr; i++)
+				for (j = 1; j < num_iter; j++)
+					printf("%lu\n", thr[0].dur[j]);
+		else
+			for (j = 1; j < num_iter; j++)
+				printf("%lu\n", thr[0].dur[j]);
+	}
+
+	return (0);
+}
-- 
2.55.0.1082.g2b9226bbc0-goog

Re: [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution.

[Peter Zijlstra]

On Thu, Sep 17, 2026 at 04:33:24AM +0000, Suleiman Souhlal wrote:
> Hello,
> 
> This patch series adds a new type of PI futexes, PI Next Generation,
> or PING (name coined by Steven Rostedt) (but other name suggestions
> are welcome!), that differs from classic PI futexes in that they can
> be stolen from the top waiter, and use Proxy Execution instead of
> rtmutexes internally. 
> 
> The reason to allow the futexes to be stolen is that with classic PI
> futex's strict handoff to the top waiter, new contending lockers are
> now forced to wait in queue, which means that any locking operation
> now becomes a scheduling event. With stealing, a contending locker has
> the chance of taking the lock without blocking. The longer wait time
> of blocked tasks can be mitigated by forcing the lock to be handed
> off to them in a way that can't be stolen, when they've been stolen
> from too much, to ensure they don't get starved.
> 
> The use of Proxy Execution lets us also get Priority Inheritance for
> for fair tasks, which PI futexes don't really allow.

https://patch.msgid.link/1490204338-1856-1-git-send-email-longman%40redhat.com

Also, the goal is to eventually delete rt_mutex and have it be the
normal mutex, in which case the existing FUTEX_*_PI things will
automagically work.

So I'm thinking all of this is way premature.

Re: [RFC PATCH 07/12] futex: Make FUTEX_*_PING use Proxy Execution.

[Jihan LIN]

Hi Suleiman,

Thanks for your RFC series.

> diff --git a/kernel/futex/ping.c b/kernel/futex/ping.c
> index ebcd3c4a7793..689f149f7150 100644
> --- a/kernel/futex/ping.c
> +++ b/kernel/futex/ping.c
> @@ -370,6 +370,9 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
>  
>  		queued = false;
>  		while (1) {
> +			set_task_blocked_on(current, &q.ping_state->ping_mutex,
> +					    BO_T_PING_FUTEX);
> +
>  			set_current_state(TASK_INTERRUPTIBLE|TASK_FREEZABLE);
>  			if (!queued) {
> 

A userspace deadlock seems to turn into a kernel lockup.
Consider threads A and B on CPU0, unlocked PING futexes F1 and F2, with
the following ordering:

  A: CAS(F1, gettid(A))
  B: CAS(F2, gettid(B))
  A: futex(&F2, FUTEX_LOCK_PING) <-- T1
  B: futex(&F1, FUTEX_LOCK_PING) <-- T2

Since futex_lock_ping_atomic() only checks self-lock, both tasks end
up blocked on each other after T2. And task_is_blocked() is true for both
tasks, try_to_block_task() would keep them on runqueue with
tsk->is_blocked set.  So if pick_next_task() picks A or B,
find_proxy_task() will stuck walking on A -> B -> A -> ... with rq->lock.

Could we handle cycles in find_proxy_task(), or add a chain walk for
deadlock detection for FUTEX_LOCK_PING like rtmutex?

Best regards,
Jihan

Re: [RFC PATCH 07/12] futex: Make FUTEX_*_PING use Proxy Execution.

[K Prateek Nayak]

On 9/17/2026 6:48 PM, Jihan LIN wrote:
> [You don't often get email from linjh22s@gmail.com. Learn why this is important at https://aka.ms/LearnAboutSenderIdentification ]
> 
> Hi Suleiman,
> 
> Thanks for your RFC series.
> 
>> diff --git a/kernel/futex/ping.c b/kernel/futex/ping.c
>> index ebcd3c4a7793..689f149f7150 100644
>> --- a/kernel/futex/ping.c
>> +++ b/kernel/futex/ping.c
>> @@ -370,6 +370,9 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
>>
>>               queued = false;
>>               while (1) {
>> +                     set_task_blocked_on(current, &q.ping_state->ping_mutex,
>> +                                         BO_T_PING_FUTEX);
>> +
>>                       set_current_state(TASK_INTERRUPTIBLE|TASK_FREEZABLE);
>>                       if (!queued) {
>>
> 
> A userspace deadlock seems to turn into a kernel lockup.
> Consider threads A and B on CPU0, unlocked PING futexes F1 and F2, with
> the following ordering:
> 
>   A: CAS(F1, gettid(A))
>   B: CAS(F2, gettid(B))
>   A: futex(&F2, FUTEX_LOCK_PING) <-- T1
>   B: futex(&F1, FUTEX_LOCK_PING) <-- T2
> 
> Since futex_lock_ping_atomic() only checks self-lock, both tasks end
> up blocked on each other after T2. And task_is_blocked() is true for both
> tasks, try_to_block_task() would keep them on runqueue with
> tsk->is_blocked set.  So if pick_next_task() picks A or B,
> find_proxy_task() will stuck walking on A -> B -> A -> ... with rq->lock.
> 
> Could we handle cycles in find_proxy_task(), or add a chain walk for
> deadlock detection for FUTEX_LOCK_PING like rtmutex?

https://lore.kernel.org/lkml/20260714152220.4046736-1-soolaugust@gmail.com/

-- 
Thanks and Regards,
Prateek

Re: [RFC PATCH 07/12] futex: Make FUTEX_*_PING use Proxy Execution.

[Peter Zijlstra]

On Thu, Sep 17, 2026 at 08:09:34PM +0530, K Prateek Nayak wrote:
> On 9/17/2026 6:48 PM, Jihan LIN wrote:
> > [You don't often get email from linjh22s@gmail.com. Learn why this is important at https://aka.ms/LearnAboutSenderIdentification ]
> > 
> > Hi Suleiman,
> > 
> > Thanks for your RFC series.
> > 
> >> diff --git a/kernel/futex/ping.c b/kernel/futex/ping.c
> >> index ebcd3c4a7793..689f149f7150 100644
> >> --- a/kernel/futex/ping.c
> >> +++ b/kernel/futex/ping.c
> >> @@ -370,6 +370,9 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
> >>
> >>               queued = false;
> >>               while (1) {
> >> +                     set_task_blocked_on(current, &q.ping_state->ping_mutex,
> >> +                                         BO_T_PING_FUTEX);
> >> +
> >>                       set_current_state(TASK_INTERRUPTIBLE|TASK_FREEZABLE);
> >>                       if (!queued) {
> >>
> > 
> > A userspace deadlock seems to turn into a kernel lockup.
> > Consider threads A and B on CPU0, unlocked PING futexes F1 and F2, with
> > the following ordering:
> > 
> >   A: CAS(F1, gettid(A))
> >   B: CAS(F2, gettid(B))
> >   A: futex(&F2, FUTEX_LOCK_PING) <-- T1
> >   B: futex(&F1, FUTEX_LOCK_PING) <-- T2
> > 
> > Since futex_lock_ping_atomic() only checks self-lock, both tasks end
> > up blocked on each other after T2. And task_is_blocked() is true for both
> > tasks, try_to_block_task() would keep them on runqueue with
> > tsk->is_blocked set.  So if pick_next_task() picks A or B,
> > find_proxy_task() will stuck walking on A -> B -> A -> ... with rq->lock.
> > 
> > Could we handle cycles in find_proxy_task(), or add a chain walk for
> > deadlock detection for FUTEX_LOCK_PING like rtmutex?
> 
> https://lore.kernel.org/lkml/20260714152220.4046736-1-soolaugust@gmail.com/

Ah yes, that thing. I would suggest to still have a hard-coded limit,
but perhaps in addition to the sequence mark.

Without a hard-coded limit, userspace is free to create chains of
arbitrary length. This should be discouraged :-)

Also, we need to be able to return -EDEADLK to userspace.

Ideally userspace gets to have an extra graph walk on block though, and
not rely on pick time sanity checks.

Re: [RFC PATCH 02/12] futex: Switch PI futex to use p->pi_futex_lock instead of p->pi_lock.

[Peter Zijlstra]

On Thu, Sep 17, 2026 at 04:33:26AM +0000, Suleiman Souhlal wrote:
> Switch PI futexes to use p->pi_futex_lock instead of p->pi_lock.
> 
> When augmenting PING futexes with proxy execution, we get lock order
> inversions, due to the lock order being p->pi_lock -> mutex->wait_lock
> in the scheduler, but wait_lock -> p->pi_lock in futex code.
> 
> So move the futex code to use a new lock, p->pi_futex_lock, to
> protect p->pi_state_list and pi_state->owner.

This is of course horrible. Lets not do this.