* [RFC PATCH 01/12] sched: Abstract task_struct->blocked_on by locking primitive.
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
@ 2026-09-17 4:33 ` Suleiman Souhlal
2026-09-17 4:33 ` [RFC PATCH 02/12] futex: Switch PI futex to use p->pi_futex_lock instead of p->pi_lock Suleiman Souhlal
` (11 subsequent siblings)
12 siblings, 0 replies; 20+ messages in thread
From: Suleiman Souhlal @ 2026-09-17 4:33 UTC (permalink / raw)
To: linux-kernel
Cc: Suleiman Souhlal, Thomas Gleixner, Ingo Molnar, Peter Zijlstra,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
John Stultz, Qais Yousef, ssouhlal
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(¤t->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(¤t->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
^ permalink raw reply [flat|nested] 20+ messages in thread* [RFC PATCH 02/12] futex: Switch PI futex to use p->pi_futex_lock instead of p->pi_lock.
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
2026-09-17 4:33 ` [RFC PATCH 01/12] sched: Abstract task_struct->blocked_on by locking primitive Suleiman Souhlal
@ 2026-09-17 4:33 ` Suleiman Souhlal
2026-09-17 15:38 ` Peter Zijlstra
2026-09-17 4:33 ` [RFC PATCH 03/12] futex: Add "ping" parameter to pi_state management functions and export them Suleiman Souhlal
` (10 subsequent siblings)
12 siblings, 1 reply; 20+ messages in thread
From: Suleiman Souhlal @ 2026-09-17 4:33 UTC (permalink / raw)
To: linux-kernel
Cc: Suleiman Souhlal, Thomas Gleixner, Ingo Molnar, Peter Zijlstra,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
John Stultz, Qais Yousef, ssouhlal
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
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [RFC PATCH 02/12] futex: Switch PI futex to use p->pi_futex_lock instead of p->pi_lock.
2026-09-17 4:33 ` [RFC PATCH 02/12] futex: Switch PI futex to use p->pi_futex_lock instead of p->pi_lock Suleiman Souhlal
@ 2026-09-17 15:38 ` Peter Zijlstra
0 siblings, 0 replies; 20+ messages in thread
From: Peter Zijlstra @ 2026-09-17 15:38 UTC (permalink / raw)
To: Suleiman Souhlal
Cc: linux-kernel, Thomas Gleixner, Ingo Molnar, Darren Hart,
Davidlohr Bueso, André Almeida, Juri Lelli, Vincent Guittot,
Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, zhidao su, John Stultz,
Qais Yousef, ssouhlal
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.
^ permalink raw reply [flat|nested] 20+ messages in thread
* [RFC PATCH 03/12] futex: Add "ping" parameter to pi_state management functions and export them.
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
2026-09-17 4:33 ` [RFC PATCH 01/12] sched: Abstract task_struct->blocked_on by locking primitive Suleiman Souhlal
2026-09-17 4:33 ` [RFC PATCH 02/12] futex: Switch PI futex to use p->pi_futex_lock instead of p->pi_lock Suleiman Souhlal
@ 2026-09-17 4:33 ` Suleiman Souhlal
2026-09-17 4:33 ` [RFC PATCH 04/12] futex: Introduce stealable PI futex, FUTEX_*_PING Suleiman Souhlal
` (9 subsequent siblings)
12 siblings, 0 replies; 20+ messages in thread
From: Suleiman Souhlal @ 2026-09-17 4:33 UTC (permalink / raw)
To: linux-kernel
Cc: Suleiman Souhlal, Thomas Gleixner, Ingo Molnar, Peter Zijlstra,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
John Stultz, Qais Yousef, ssouhlal
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
^ permalink raw reply [flat|nested] 20+ messages in thread* [RFC PATCH 04/12] futex: Introduce stealable PI futex, FUTEX_*_PING.
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
` (2 preceding siblings ...)
2026-09-17 4:33 ` [RFC PATCH 03/12] futex: Add "ping" parameter to pi_state management functions and export them Suleiman Souhlal
@ 2026-09-17 4:33 ` Suleiman Souhlal
2026-09-17 4:33 ` [RFC PATCH 05/12] futex: Implement exit_ping_state_list() Suleiman Souhlal
` (8 subsequent siblings)
12 siblings, 0 replies; 20+ messages in thread
From: Suleiman Souhlal @ 2026-09-17 4:33 UTC (permalink / raw)
To: linux-kernel
Cc: Suleiman Souhlal, Thomas Gleixner, Ingo Molnar, Peter Zijlstra,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
John Stultz, Qais Yousef, ssouhlal
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
^ permalink raw reply [flat|nested] 20+ messages in thread* [RFC PATCH 05/12] futex: Implement exit_ping_state_list().
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
` (3 preceding siblings ...)
2026-09-17 4:33 ` [RFC PATCH 04/12] futex: Introduce stealable PI futex, FUTEX_*_PING Suleiman Souhlal
@ 2026-09-17 4:33 ` Suleiman Souhlal
2026-09-17 4:33 ` [RFC PATCH 06/12] futex: Address aborting from futex_lock_ping() while owning ping_state Suleiman Souhlal
` (7 subsequent siblings)
12 siblings, 0 replies; 20+ messages in thread
From: Suleiman Souhlal @ 2026-09-17 4:33 UTC (permalink / raw)
To: linux-kernel
Cc: Suleiman Souhlal, Thomas Gleixner, Ingo Molnar, Peter Zijlstra,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
John Stultz, Qais Yousef, ssouhlal
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
^ permalink raw reply [flat|nested] 20+ messages in thread* [RFC PATCH 06/12] futex: Address aborting from futex_lock_ping() while owning ping_state.
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
` (4 preceding siblings ...)
2026-09-17 4:33 ` [RFC PATCH 05/12] futex: Implement exit_ping_state_list() Suleiman Souhlal
@ 2026-09-17 4:33 ` Suleiman Souhlal
2026-09-17 4:33 ` [RFC PATCH 07/12] futex: Make FUTEX_*_PING use Proxy Execution Suleiman Souhlal
` (6 subsequent siblings)
12 siblings, 0 replies; 20+ messages in thread
From: Suleiman Souhlal @ 2026-09-17 4:33 UTC (permalink / raw)
To: linux-kernel
Cc: Suleiman Souhlal, Thomas Gleixner, Ingo Molnar, Peter Zijlstra,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
John Stultz, Qais Yousef, ssouhlal
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
^ permalink raw reply [flat|nested] 20+ messages in thread* [RFC PATCH 07/12] futex: Make FUTEX_*_PING use Proxy Execution.
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
` (5 preceding siblings ...)
2026-09-17 4:33 ` [RFC PATCH 06/12] futex: Address aborting from futex_lock_ping() while owning ping_state Suleiman Souhlal
@ 2026-09-17 4:33 ` Suleiman Souhlal
2026-09-17 13:18 ` Jihan LIN
2026-09-17 4:33 ` [RFC PATCH 08/12] futex: Implement PING futex handoff Suleiman Souhlal
` (5 subsequent siblings)
12 siblings, 1 reply; 20+ messages in thread
From: Suleiman Souhlal @ 2026-09-17 4:33 UTC (permalink / raw)
To: linux-kernel
Cc: Suleiman Souhlal, Thomas Gleixner, Ingo Molnar, Peter Zijlstra,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
John Stultz, Qais Yousef, ssouhlal
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
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [RFC PATCH 07/12] futex: Make FUTEX_*_PING use Proxy Execution.
2026-09-17 4:33 ` [RFC PATCH 07/12] futex: Make FUTEX_*_PING use Proxy Execution Suleiman Souhlal
@ 2026-09-17 13:18 ` Jihan LIN
2026-09-17 14:39 ` K Prateek Nayak
0 siblings, 1 reply; 20+ messages in thread
From: Jihan LIN @ 2026-09-17 13:18 UTC (permalink / raw)
To: suleiman
Cc: andrealmeid, bsegall, dave, dietmar.eggemann, dvhart, jstultz,
juri.lelli, kprateek.nayak, linux-kernel, mgorman, mingo, peterz,
qyousef, rostedt, soolaugust, ssouhlal, tglx, vincent.guittot,
vschneid
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
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [RFC PATCH 07/12] futex: Make FUTEX_*_PING use Proxy Execution.
2026-09-17 13:18 ` Jihan LIN
@ 2026-09-17 14:39 ` K Prateek Nayak
2026-09-17 15:36 ` Peter Zijlstra
0 siblings, 1 reply; 20+ messages in thread
From: K Prateek Nayak @ 2026-09-17 14:39 UTC (permalink / raw)
To: Jihan LIN, suleiman
Cc: andrealmeid, bsegall, dave, dietmar.eggemann, dvhart, jstultz,
juri.lelli, linux-kernel, mgorman, mingo, peterz, qyousef,
rostedt, soolaugust, ssouhlal, tglx, vincent.guittot, vschneid
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
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [RFC PATCH 07/12] futex: Make FUTEX_*_PING use Proxy Execution.
2026-09-17 14:39 ` K Prateek Nayak
@ 2026-09-17 15:36 ` Peter Zijlstra
0 siblings, 0 replies; 20+ messages in thread
From: Peter Zijlstra @ 2026-09-17 15:36 UTC (permalink / raw)
To: K Prateek Nayak
Cc: Jihan LIN, suleiman, andrealmeid, bsegall, dave,
dietmar.eggemann, dvhart, jstultz, juri.lelli, linux-kernel,
mgorman, mingo, qyousef, rostedt, soolaugust, ssouhlal, tglx,
vincent.guittot, vschneid
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.
^ permalink raw reply [flat|nested] 20+ messages in thread
* [RFC PATCH 08/12] futex: Implement PING futex handoff.
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
` (6 preceding siblings ...)
2026-09-17 4:33 ` [RFC PATCH 07/12] futex: Make FUTEX_*_PING use Proxy Execution Suleiman Souhlal
@ 2026-09-17 4:33 ` Suleiman Souhlal
2026-09-17 4:33 ` [RFC PATCH 09/12] futex: Wake up donor in PING futex unlock Suleiman Souhlal
` (4 subsequent siblings)
12 siblings, 0 replies; 20+ messages in thread
From: Suleiman Souhlal @ 2026-09-17 4:33 UTC (permalink / raw)
To: linux-kernel
Cc: Suleiman Souhlal, Thomas Gleixner, Ingo Molnar, Peter Zijlstra,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
John Stultz, Qais Yousef, ssouhlal
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
^ permalink raw reply [flat|nested] 20+ messages in thread* [RFC PATCH 09/12] futex: Wake up donor in PING futex unlock.
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
` (7 preceding siblings ...)
2026-09-17 4:33 ` [RFC PATCH 08/12] futex: Implement PING futex handoff Suleiman Souhlal
@ 2026-09-17 4:33 ` Suleiman Souhlal
2026-09-17 4:33 ` [RFC PATCH 10/12] futex: Optimistic spinning for PING futexes Suleiman Souhlal
` (3 subsequent siblings)
12 siblings, 0 replies; 20+ messages in thread
From: Suleiman Souhlal @ 2026-09-17 4:33 UTC (permalink / raw)
To: linux-kernel
Cc: Suleiman Souhlal, Thomas Gleixner, Ingo Molnar, Peter Zijlstra,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
John Stultz, Qais Yousef, ssouhlal
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(¤t->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(¤t->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
^ permalink raw reply [flat|nested] 20+ messages in thread* [RFC PATCH 10/12] futex: Optimistic spinning for PING futexes.
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
` (8 preceding siblings ...)
2026-09-17 4:33 ` [RFC PATCH 09/12] futex: Wake up donor in PING futex unlock Suleiman Souhlal
@ 2026-09-17 4:33 ` Suleiman Souhlal
2026-09-17 4:33 ` [RFC PATCH 11/12] futex: Allow userspace stealing " Suleiman Souhlal
` (2 subsequent siblings)
12 siblings, 0 replies; 20+ messages in thread
From: Suleiman Souhlal @ 2026-09-17 4:33 UTC (permalink / raw)
To: linux-kernel
Cc: Suleiman Souhlal, Thomas Gleixner, Ingo Molnar, Peter Zijlstra,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
John Stultz, Qais Yousef, ssouhlal
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
^ permalink raw reply [flat|nested] 20+ messages in thread* [RFC PATCH 11/12] futex: Allow userspace stealing for PING futexes.
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
` (9 preceding siblings ...)
2026-09-17 4:33 ` [RFC PATCH 10/12] futex: Optimistic spinning for PING futexes Suleiman Souhlal
@ 2026-09-17 4:33 ` Suleiman Souhlal
2026-09-17 4:33 ` [RFC PATCH 12/12] tools/testing/futex: Add ping_bench, a tool for benchmarking futexes Suleiman Souhlal
2026-09-17 8:58 ` [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Peter Zijlstra
12 siblings, 0 replies; 20+ messages in thread
From: Suleiman Souhlal @ 2026-09-17 4:33 UTC (permalink / raw)
To: linux-kernel
Cc: Suleiman Souhlal, Thomas Gleixner, Ingo Molnar, Peter Zijlstra,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
John Stultz, Qais Yousef, ssouhlal
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
^ permalink raw reply [flat|nested] 20+ messages in thread* [RFC PATCH 12/12] tools/testing/futex: Add ping_bench, a tool for benchmarking futexes.
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
` (10 preceding siblings ...)
2026-09-17 4:33 ` [RFC PATCH 11/12] futex: Allow userspace stealing " Suleiman Souhlal
@ 2026-09-17 4:33 ` Suleiman Souhlal
2026-09-17 8:58 ` [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Peter Zijlstra
12 siblings, 0 replies; 20+ messages in thread
From: Suleiman Souhlal @ 2026-09-17 4:33 UTC (permalink / raw)
To: linux-kernel
Cc: Suleiman Souhlal, Thomas Gleixner, Ingo Molnar, Peter Zijlstra,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
John Stultz, Qais Yousef, ssouhlal
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, ¶m) != 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, ¶m) != 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
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution.
2026-09-17 4:33 [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Suleiman Souhlal
` (11 preceding siblings ...)
2026-09-17 4:33 ` [RFC PATCH 12/12] tools/testing/futex: Add ping_bench, a tool for benchmarking futexes Suleiman Souhlal
@ 2026-09-17 8:58 ` Peter Zijlstra
2026-09-17 17:53 ` John Stultz
12 siblings, 1 reply; 20+ messages in thread
From: Peter Zijlstra @ 2026-09-17 8:58 UTC (permalink / raw)
To: Suleiman Souhlal
Cc: linux-kernel, Thomas Gleixner, Ingo Molnar, Darren Hart,
Davidlohr Bueso, André Almeida, Juri Lelli, Vincent Guittot,
Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, zhidao su, John Stultz,
Qais Yousef, ssouhlal
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.
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution.
2026-09-17 8:58 ` [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution Peter Zijlstra
@ 2026-09-17 17:53 ` John Stultz
2026-09-17 18:51 ` Steven Rostedt
0 siblings, 1 reply; 20+ messages in thread
From: John Stultz @ 2026-09-17 17:53 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Suleiman Souhlal, linux-kernel, Thomas Gleixner, Ingo Molnar,
Darren Hart, Davidlohr Bueso, André Almeida, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
Qais Yousef, ssouhlal
On Thu, Sep 17, 2026 at 1:58 AM Peter Zijlstra <peterz@infradead.org> wrote:
> On Thu, Sep 17, 2026 at 04:33:24AM +0000, Suleiman Souhlal wrote:
> >
> > 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
Thanks for that reference! I'm sure we can learn a lot from that series.
(I do like the straightforward FUTEX_LOCK/UNLOCK over the PING name here :)
> 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.
Indeed, moving rt_mutexes to proxy is a goal. Though the performance
concerns from FUTEX_*_PI have to do with the semantics it (and
rt_mutex) promises: strict RT prio order handoff - esentially FIFO for
SCHED_NORMAL. Not so much the mechanism it uses for boosting.
That's why it seems a new FUTEX op is needed. Since we 1) need to
communicate the owner to the kernel 2) want different semantics for
lock-handoff and stealing.
Even when we get to moving rt_mutexes to proxy, it seems to me we're
likely going to have to keep the rt_mutex itself (even if the PI
boosting is proxy based) as a distinguisher, since the users likely
desire the strict semantics (or at least we will need to add some
behavior flags to the mutex struct so it can still satisfy those
semantics).
> So I'm thinking all of this is way premature.
So it is just an initial RFC, and we are looking for input.
But there is a strong appetite to solve this, as we're already seeing
vendors doing less ideal things, like passing who the waiter thinks
the owner is (racy) in via unused fields of FUTEX_WAIT, so that
out-of-tree custom scheduler boosting can (temporarily - as again it
can be wrong) try to get that owner to release the lock. The longer we
go without a usable upstream solution, the more entrenched these less
ideal solutions become.
thanks
-john
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [RFC PATCH 00/12] FUTEX_PING: A stealable futex using Proxy Execution.
2026-09-17 17:53 ` John Stultz
@ 2026-09-17 18:51 ` Steven Rostedt
0 siblings, 0 replies; 20+ messages in thread
From: Steven Rostedt @ 2026-09-17 18:51 UTC (permalink / raw)
To: John Stultz
Cc: Peter Zijlstra, Suleiman Souhlal, linux-kernel, Thomas Gleixner,
Ingo Molnar, Darren Hart, Davidlohr Bueso, André Almeida,
Juri Lelli, Vincent Guittot, Dietmar Eggemann, Ben Segall,
Mel Gorman, Valentin Schneider, K Prateek Nayak, zhidao su,
Qais Yousef, ssouhlal
On Thu, 17 Sep 2026 10:53:47 -0700
John Stultz <jstultz@google.com> wrote:
> Indeed, moving rt_mutexes to proxy is a goal. Though the performance
> concerns from FUTEX_*_PI have to do with the semantics it (and
> rt_mutex) promises: strict RT prio order handoff - esentially FIFO for
> SCHED_NORMAL. Not so much the mechanism it uses for boosting.
I started working on this while still at Google on the
ChromeOS/Android-on-chrome team. The biggest issue we found with
FUTEX_PI was that it forced all users of it to be fair. Even
SCHED_OTHER which did not even benefit from the PI code. The result, it
killed performance, and nobody wanted to use it.
What I recommended was to have a new futex to allow SCHED_OTHER tasks
to be unfair (just like rt_mutex is in PREEMPT_RT), and also to allow
more to be done in user space and not require every contention to go
into the kernel.
We had a test (Suleiman, can you share that test) which emulated the
code in Chrome and by switching to FUTEX_PI the performance dropped by
a large percentage (I don't recall the actual numbers but I posted them
internally at Google). By switching SCHED_OTHER to be non fair (that
is, when the lock was released, if the next waiting task was
SCHED_OTHER, and the new SCHED_OTHER task coming in could steal the
lock), and the performance almost went back to what normal FUTEX had (I
was assuming that going into the kernel on all contention was the cause
of not getting closer to normal FUTEX). That alone was a big
improvement over FUTEX_PI.
There was talk about changing FUTEX_PI to allow SCHED_OTHER to be
unfair and to steal, but that would change the semantics of it and
there may be some application that requires FUTEX_PI to be fair for all
tasks, even SCHED_OTHER. This is when we decided that we need a new
FUTEX_PI (new generation, which I coined FUTEX_PING, but kinda of a
joke so feel free to change), so that we could change the semantics
without breaking backward compatibility of applications requiring the
current behavior of FUTEX_PI.
But FUTEX_PI requires all contention to be handled in the kernel, where
as we can get even more performance if we could change it to allow the
SCHED_OTHER case (which can steal the lock) to be handled in user space.
I haven't looked at Suleiman's code yet (I'm currently traveling and
don't have time until after Oct 10th). But I would expect this new
futex to keep RT tasks being fair. Otherwise no RT task will use it.
In summary, the motivation of this patch was that we had a few RT tasks
suffering from priority inversion from hundreds of SCHED_OTHER tasks
over a shared mutex. The problem was, if we switched it to FUTEX_PI,
the few RT tasks would perform correctly, but the slowdown from the
hundreds of SCHED_OTHER tasks made it a show stopper. The goal was to
have a futex that allowed nice PI with RT tasks, but still allowed
SCHED_OTHER being unfair and stealing from each other.
-- Steve
^ permalink raw reply [flat|nested] 20+ messages in thread