Jiri Slaby reported a futex state inconsistency resulting in -EINVAL
during a lock operation for a PI futex. A requirement is that the lock
process is interrupted by a timeout or signal:
T1 T2
*owns* futex
futex_lock_pi()
*create PI state, attach to it, queue RT waiter*
rt_mutex_wait_proxy_lock() /* -ETIMEDOUT */
rt_mutex_cleanup_proxy_lock()
remove_waiter()
futex_unlock_pi()
spin_lock(&hb->lock);
top_waiter = futex_top_waiter(hb, &key);
/* top_waiter is NULL, do_uncontended */
spin_unlock(&hb->lock);
To spice things up, player T3 and T4 enter the game:
T3 T4
*acquires futex in userland*
futex_lock_pi()
futex_q_lock(&q);
futex_lock_pi_atomic()
top_waiter = futex_top_waiter(hb, key);
/* top_waiter is from T1, still */
attach_to_pi_state()
/* Here -EINVAL is returned because uval
* points to T3 but pi_state says T1.
*/
We must not unlock the futex for userland as long as there is still a
state pending in kernel. It can be used by further futex_lock_pi()
caller (as it has been observed by futex_unlock_pi()). The caller will
observe an outdated state of the futex because it was not removed during
unlock operation in kernel.
The lock can not be handed over to T1 because it already gave up and
stared to clean up.
All futex_q entries point to the same pi_state and the pi_mutex has no
waiters. A waiter can not be enqueued because hb->lock +
pi_mutex.wait_lock is acquired (by the unlock operation) and the same
ordering is used by futex_lock_pi() during locking.
Remove all futex_q entries from the hb list which point to the futex if
no waiter has been observed. This closes the race window by removing all
pointer to the previous in-kernel state.
The leaving futex_lock_pi() caller can clean up the pi-state once it
acquires hb->lock. The following futex_lock_pi() caller will create a
new in-kernel state.
The optional removal from hb->chain is only needed if the futex was not
acquired because it might have been done by the unlock path with
hb->lock acquired.
Fixes: fbeb558b0dd0d ("futex/pi: Fix recursive rt_mutex waiter state")
Reported-by: Jiri Slaby <[email protected]>
Closes: [email protected]
Signed-off-by: Sebastian Andrzej Siewior <[email protected]>
---
kernel/futex/core.c | 9 +++++++--
kernel/futex/futex.h | 2 +-
kernel/futex/pi.c | 11 +++++++----
kernel/futex/requeue.c | 2 +-
4 files changed, 16 insertions(+), 8 deletions(-)
diff --git a/kernel/futex/core.c b/kernel/futex/core.c
index dad981a865b84..31505b0a405ae 100644
--- a/kernel/futex/core.c
+++ b/kernel/futex/core.c
@@ -628,10 +628,15 @@ int futex_unqueue(struct futex_q *q)
/*
* PI futexes can not be requeued and must remove themselves from the
* hash bucket. The hash bucket lock (i.e. lock_ptr) is held.
+ * If the PI futex was not acquired (due to timeout or signal) then it removes
+ * its rt_waiter before it removes itself from the futex queue. The unlocker
+ * will remove the futex_q from the queue if it observes an empty waitqueue.
+ * Therefore the unqueue is optional in this case.
*/
-void futex_unqueue_pi(struct futex_q *q)
+void futex_unqueue_pi(struct futex_q *q, bool have_lock)
{
- __futex_unqueue(q);
+ if (have_lock || !plist_node_empty(&q->list))
+ __futex_unqueue(q);
BUG_ON(!q->pi_state);
put_pi_state(q->pi_state);
diff --git a/kernel/futex/futex.h b/kernel/futex/futex.h
index 8b195d06f4e8e..c7133ffb381fd 100644
--- a/kernel/futex/futex.h
+++ b/kernel/futex/futex.h
@@ -252,7 +252,7 @@ static inline void futex_queue(struct futex_q *q, struct futex_hash_bucket *hb)
spin_unlock(&hb->lock);
}
-extern void futex_unqueue_pi(struct futex_q *q);
+extern void futex_unqueue_pi(struct futex_q *q, bool have_lock);
extern void wait_for_owner_exiting(int ret, struct task_struct *exiting);
diff --git a/kernel/futex/pi.c b/kernel/futex/pi.c
index 90e5197f4e569..4023841358eea 100644
--- a/kernel/futex/pi.c
+++ b/kernel/futex/pi.c
@@ -1070,6 +1070,7 @@ int futex_lock_pi(u32 __user *uaddr, unsigned int flags, ktime_t *time, int tryl
* haven't already.
*/
res = fixup_pi_owner(uaddr, &q, !ret);
+ futex_unqueue_pi(&q, !ret);
/*
* If fixup_pi_owner() returned an error, propagate that. If it acquired
* the lock, clear our -ETIMEDOUT or -EINTR.
@@ -1077,7 +1078,6 @@ int futex_lock_pi(u32 __user *uaddr, unsigned int flags, ktime_t *time, int tryl
if (res)
ret = (res < 0) ? res : 0;
- futex_unqueue_pi(&q);
spin_unlock(q.lock_ptr);
goto out;
@@ -1135,6 +1135,7 @@ int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
hb = futex_hash(&key);
spin_lock(&hb->lock);
+retry_hb:
/*
* Check waiters first. We do not trust user space values at
@@ -1177,12 +1178,15 @@ int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
/*
* Futex vs rt_mutex waiter state -- if there are no rt_mutex
* waiters even though futex thinks there are, then the waiter
- * is leaving and the uncontended path is safe to take.
+ * is leaving. We need to remove it from the list so that the
+ * current PI-state is not observed by future pi_futex_lock()
+ * caller before the leaving waiter had a chance to clean up.
*/
rt_waiter = rt_mutex_top_waiter(&pi_state->pi_mutex);
if (!rt_waiter) {
+ __futex_unqueue(top_waiter);
raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
- goto do_uncontended;
+ goto retry_hb;
}
get_pi_state(pi_state);
@@ -1217,7 +1221,6 @@ int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
return ret;
}
-do_uncontended:
/*
* We have no kernel internal state, i.e. no waiters in the
* kernel. Waiters which are about to queue themselves are stuck
diff --git a/kernel/futex/requeue.c b/kernel/futex/requeue.c
index eb21f065816ba..57869ef20bda3 100644
--- a/kernel/futex/requeue.c
+++ b/kernel/futex/requeue.c
@@ -873,7 +873,7 @@ int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
if (res)
ret = (res < 0) ? res : 0;
- futex_unqueue_pi(&q);
+ futex_unqueue_pi(&q, true);
spin_unlock(q.lock_ptr);
if (ret == -EINTR) {
--
2.43.0
On 16. 01. 24, 14:08, Sebastian Andrzej Siewior wrote:
> Jiri Slaby reported a futex state inconsistency resulting in -EINVAL
> during a lock operation for a PI futex. A requirement is that the lock
> process is interrupted by a timeout or signal:
>
> T1 T2
> *owns* futex
> futex_lock_pi()
> *create PI state, attach to it, queue RT waiter*
> rt_mutex_wait_proxy_lock() /* -ETIMEDOUT */
> rt_mutex_cleanup_proxy_lock()
> remove_waiter()
>
> futex_unlock_pi()
> spin_lock(&hb->lock);
> top_waiter = futex_top_waiter(hb, &key);
> /* top_waiter is NULL, do_uncontended */
> spin_unlock(&hb->lock);
>
> To spice things up, player T3 and T4 enter the game:
>
> T3 T4
> *acquires futex in userland*
> futex_lock_pi()
> futex_q_lock(&q);
> futex_lock_pi_atomic()
> top_waiter = futex_top_waiter(hb, key);
> /* top_waiter is from T1, still */
> attach_to_pi_state()
> /* Here -EINVAL is returned because uval
> * points to T3 but pi_state says T1.
> */
>
> We must not unlock the futex for userland as long as there is still a
> state pending in kernel. It can be used by further futex_lock_pi()
> caller (as it has been observed by futex_unlock_pi()). The caller will
> observe an outdated state of the futex because it was not removed during
> unlock operation in kernel.
>
> The lock can not be handed over to T1 because it already gave up and
> stared to clean up.
> All futex_q entries point to the same pi_state and the pi_mutex has no
> waiters. A waiter can not be enqueued because hb->lock +
> pi_mutex.wait_lock is acquired (by the unlock operation) and the same
> ordering is used by futex_lock_pi() during locking.
>
> Remove all futex_q entries from the hb list which point to the futex if
> no waiter has been observed. This closes the race window by removing all
> pointer to the previous in-kernel state.
> The leaving futex_lock_pi() caller can clean up the pi-state once it
> acquires hb->lock. The following futex_lock_pi() caller will create a
> new in-kernel state.
> The optional removal from hb->chain is only needed if the futex was not
> acquired because it might have been done by the unlock path with
> hb->lock acquired.
>
> Fixes: fbeb558b0dd0d ("futex/pi: Fix recursive rt_mutex waiter state")
> Reported-by: Jiri Slaby <[email protected]>
Tested-by: Jiri Slaby <[email protected]>
> Closes: [email protected]
> Signed-off-by: Sebastian Andrzej Siewior <[email protected]>
thanks,
--
js
suse labs
On 2024-01-16 14:08:12 [+0100], To Jiri Slaby wrote:
> --- a/kernel/futex/requeue.c
> +++ b/kernel/futex/requeue.c
> @@ -873,7 +873,7 @@ int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
> if (res)
> ret = (res < 0) ? res : 0;
>
> - futex_unqueue_pi(&q);
> + futex_unqueue_pi(&q, true);
This obviously needs the same change as futex_lock_pi() unless it is
okay to avoid the argument and remove it if it hasn't been removed. I
forgot that the requeue path has also signals & timeouts and so is
subject to the same problem.
Assuming we go that direction…
> spin_unlock(q.lock_ptr);
>
> if (ret == -EINTR) {
Sebastian
On Tue, Jan 16 2024 at 14:08, Sebastian Andrzej Siewior wrote:
> @@ -628,10 +628,15 @@ int futex_unqueue(struct futex_q *q)
> /*
> * PI futexes can not be requeued and must remove themselves from the
> * hash bucket. The hash bucket lock (i.e. lock_ptr) is held.
> + * If the PI futex was not acquired (due to timeout or signal) then it removes
> + * its rt_waiter before it removes itself from the futex queue. The unlocker
> + * will remove the futex_q from the queue if it observes an empty waitqueue.
> + * Therefore the unqueue is optional in this case.
This explanation is as confusing as the changelog.
> */
> -void futex_unqueue_pi(struct futex_q *q)
> +void futex_unqueue_pi(struct futex_q *q, bool have_lock)
> {
> - __futex_unqueue(q);
> + if (have_lock || !plist_node_empty(&q->list))
> + __futex_unqueue(q);
If 'have_lock == true' then 'plist_node_empty()' must be 'false' with
you moving the callsite up, no?
So that 'have_lock' arguments is clearly pointless.
> BUG_ON(!q->pi_state);
> put_pi_state(q->pi_state);
> diff --git a/kernel/futex/futex.h b/kernel/futex/futex.h
> index 8b195d06f4e8e..c7133ffb381fd 100644
> --- a/kernel/futex/futex.h
> +++ b/kernel/futex/futex.h
> @@ -252,7 +252,7 @@ static inline void futex_queue(struct futex_q *q, struct futex_hash_bucket *hb)
> spin_unlock(&hb->lock);
> }
>
> -extern void futex_unqueue_pi(struct futex_q *q);
> +extern void futex_unqueue_pi(struct futex_q *q, bool have_lock);
>
> extern void wait_for_owner_exiting(int ret, struct task_struct *exiting);
>
> diff --git a/kernel/futex/pi.c b/kernel/futex/pi.c
> index 90e5197f4e569..4023841358eea 100644
> --- a/kernel/futex/pi.c
> +++ b/kernel/futex/pi.c
> @@ -1070,6 +1070,7 @@ int futex_lock_pi(u32 __user *uaddr, unsigned int flags, ktime_t *time, int tryl
> * haven't already.
> */
> res = fixup_pi_owner(uaddr, &q, !ret);
> + futex_unqueue_pi(&q, !ret);
> /*
> * If fixup_pi_owner() returned an error, propagate that. If it acquired
> * the lock, clear our -ETIMEDOUT or -EINTR.
> @@ -1077,7 +1078,6 @@ int futex_lock_pi(u32 __user *uaddr, unsigned int flags, ktime_t *time, int tryl
> if (res)
> ret = (res < 0) ? res : 0;
>
> - futex_unqueue_pi(&q);
Without the have_lock argument these two hunks are not required.
> spin_unlock(q.lock_ptr);
> goto out;
>
> @@ -1135,6 +1135,7 @@ int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
>
> hb = futex_hash(&key);
> spin_lock(&hb->lock);
> +retry_hb:
>
> /*
> * Check waiters first. We do not trust user space values at
> @@ -1177,12 +1178,15 @@ int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
> /*
> * Futex vs rt_mutex waiter state -- if there are no rt_mutex
> * waiters even though futex thinks there are, then the waiter
> - * is leaving and the uncontended path is safe to take.
> + * is leaving. We need to remove it from the list so that the
> + * current PI-state is not observed by future pi_futex_lock()
> + * caller before the leaving waiter had a chance to clean up.
> */
> rt_waiter = rt_mutex_top_waiter(&pi_state->pi_mutex);
> if (!rt_waiter) {
> + __futex_unqueue(top_waiter);
> raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
> - goto do_uncontended;
> + goto retry_hb;
This clearly lacks a comment that there might be more than one waiter in
the hash-bucket which removed itself from the rtmutex and is now blocked
on the hash bucket lock.
Thanks,
tglx
Jiri Slaby reported a futex state inconsistency resulting in -EINVAL
during a lock operation for a PI futex. A requirement is that the lock
process is interrupted by a timeout or signal:
T1 Owns the futex in userland.
T2 Tries to acquire the futex in kernel (futex_lock_pi()). Allocates a
pi_state and attaches itself to it.
T2 Times out and removes its rt_waiter from the rt_mutex.
T1 Unlocks the futex (futex_unlock_pi()). Finds a futex_q but no
rt_waiter. Unlocks the futex (do_uncontended) and makes it available
to userland.
T3 Acquires the futex in userland.
T4 Tries to acquire the futex in kernel (futex_lock_pi()). Finds the
existing futex_q and tries to attach itself to the existing pi_state.
This (attach_to_pi_state()) fails with -EINVAL because uval contains
the pid of T3 but pi_state points to T1.
We must not unlock the futex and make it available for userland as long
as there is still an existing state in kernel. It can be used by further
futex_lock_pi() caller and observe inconsistent state.
The lock can not be handed over to T1 because it already gave up and
started to clean up.
All futex_q entries point to the same pi_state and the pi_mutex has no
waiters. A waiter can not be enqueued because hb->lock +
pi_mutex.wait_lock is acquired (by the unlock operation) and the same
ordering is used by futex_lock_pi() during locking.
Remove all futex_q entries from the hb list which point to the futex if
no waiter has been observed in the futex_unlock_pi() path. This closes
the race window by removing all pointer to the previous in-kernel state.
The leaving futex_lock_pi() caller can clean up the pi-state once it
acquires hb->lock. During the process futex_unqueue_pi() must remove
the futex_q item from the hb list only if not yet happened.
Fixes: fbeb558b0dd0d ("futex/pi: Fix recursive rt_mutex waiter state")
Reported-by: Jiri Slaby <[email protected]>
Closes: https://lore.kernel.org/all/[email protected]
Signed-off-by: Sebastian Andrzej Siewior <[email protected]>
Tested-by: Jiri Slaby <[email protected]>
---
v1…v2:
- Removed the argument to futex_unqueue_pi(). __futex_unqueue() is now
always invoked conditionally.
- Rewrote the patch description and comments in the patch.
- Corrected the Closes: link and added Tested-by.
kernel/futex/core.c | 7 ++++++-
kernel/futex/pi.c | 11 ++++++++---
2 files changed, 14 insertions(+), 4 deletions(-)
diff --git a/kernel/futex/core.c b/kernel/futex/core.c
index dad981a865b84..fd56a84b163a1 100644
--- a/kernel/futex/core.c
+++ b/kernel/futex/core.c
@@ -628,10 +628,15 @@ int futex_unqueue(struct futex_q *q)
/*
* PI futexes can not be requeued and must remove themselves from the
* hash bucket. The hash bucket lock (i.e. lock_ptr) is held.
+ * If the lock was not acquired (due to timeout or signal) then the rt_waiter
+ * is removed before futex_q is. If this is observed by unlocker then it will
+ * remove futex_q from the hash bucket list. Thefore the removal here is
+ * optional.
*/
void futex_unqueue_pi(struct futex_q *q)
{
- __futex_unqueue(q);
+ if (!plist_node_empty(&q->list))
+ __futex_unqueue(q);
BUG_ON(!q->pi_state);
put_pi_state(q->pi_state);
diff --git a/kernel/futex/pi.c b/kernel/futex/pi.c
index 90e5197f4e569..50008b7b38e7e 100644
--- a/kernel/futex/pi.c
+++ b/kernel/futex/pi.c
@@ -1135,6 +1135,7 @@ int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
hb = futex_hash(&key);
spin_lock(&hb->lock);
+retry_hb:
/*
* Check waiters first. We do not trust user space values at
@@ -1177,12 +1178,17 @@ int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
/*
* Futex vs rt_mutex waiter state -- if there are no rt_mutex
* waiters even though futex thinks there are, then the waiter
- * is leaving and the uncontended path is safe to take.
+ * is leaving. The entry needs to be removed from the list so a
+ * new futex_lock_pi() is not using this outdated PI-state while
+ * the futex is available in userland again.
+ * There can be more than one task on its way out so it needs
+ * to retry.
*/
rt_waiter = rt_mutex_top_waiter(&pi_state->pi_mutex);
if (!rt_waiter) {
+ __futex_unqueue(top_waiter);
raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
- goto do_uncontended;
+ goto retry_hb;
}
get_pi_state(pi_state);
@@ -1217,7 +1223,6 @@ int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
return ret;
}
-do_uncontended:
/*
* We have no kernel internal state, i.e. no waiters in the
* kernel. Waiters which are about to queue themselves are stuck
--
2.43.0
The following commit has been merged into the locking/urgent branch of tip:
Commit-ID: e626cb02ee8399fd42c415e542d031d185783903
Gitweb: https://git.kernel.org/tip/e626cb02ee8399fd42c415e542d031d185783903
Author: Sebastian Andrzej Siewior <[email protected]>
AuthorDate: Thu, 18 Jan 2024 12:54:51 +01:00
Committer: Thomas Gleixner <[email protected]>
CommitterDate: Fri, 19 Jan 2024 12:58:17 +01:00
futex: Prevent the reuse of stale pi_state
Jiri Slaby reported a futex state inconsistency resulting in -EINVAL during
a lock operation for a PI futex. It requires that the a lock process is
interrupted by a timeout or signal:
T1 Owns the futex in user space.
T2 Tries to acquire the futex in kernel (futex_lock_pi()). Allocates a
pi_state and attaches itself to it.
T2 Times out and removes its rt_waiter from the rt_mutex. Drops the
rtmutex lock and tries to acquire the hash bucket lock to remove
the futex_q. The lock is contended and T2 schedules out.
T1 Unlocks the futex (futex_unlock_pi()). Finds a futex_q but no
rt_waiter. Unlocks the futex (do_uncontended) and makes it available
to user space.
T3 Acquires the futex in user space.
T4 Tries to acquire the futex in kernel (futex_lock_pi()). Finds the
existing futex_q of T2 and tries to attach itself to the existing
pi_state. This (attach_to_pi_state()) fails with -EINVAL because uval
contains the TID of T3 but pi_state points to T1.
It's incorrect to unlock the futex and make it available for user space to
acquire as long as there is still an existing state attached to it in the
kernel.
T1 cannot hand over the futex to T2 because T2 already gave up and started
to clean up and is blocked on the hash bucket lock, so T2's futex_q with
the pi_state pointing to T1 is still queued.
T2 observes the futex_q, but ignores it as there is no waiter on the
corresponding rt_mutex and takes the uncontended path which allows the
subsequent caller of futex_lock_pi() (T4) to observe that stale state.
To prevent this the unlock path must dequeue all futex_q entries which
point to the same pi_state when there is no waiter on the rt mutex. This
requires obviously to make the dequeue conditional in the locking path to
prevent a double dequeue. With that it's guaranteed that user space cannot
observe an uncontended futex which has kernel state attached.
Fixes: fbeb558b0dd0d ("futex/pi: Fix recursive rt_mutex waiter state")
Reported-by: Jiri Slaby <[email protected]>
Signed-off-by: Sebastian Andrzej Siewior <[email protected]>
Signed-off-by: Thomas Gleixner <[email protected]>
Tested-by: Jiri Slaby <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Closes: https://lore.kernel.org/all/[email protected]
---
kernel/futex/core.c | 15 ++++++++++++---
kernel/futex/pi.c | 11 ++++++++---
2 files changed, 20 insertions(+), 6 deletions(-)
diff --git a/kernel/futex/core.c b/kernel/futex/core.c
index e0e8534..1e78ef2 100644
--- a/kernel/futex/core.c
+++ b/kernel/futex/core.c
@@ -627,12 +627,21 @@ retry:
}
/*
- * PI futexes can not be requeued and must remove themselves from the
- * hash bucket. The hash bucket lock (i.e. lock_ptr) is held.
+ * PI futexes can not be requeued and must remove themselves from the hash
+ * bucket. The hash bucket lock (i.e. lock_ptr) is held.
*/
void futex_unqueue_pi(struct futex_q *q)
{
- __futex_unqueue(q);
+ /*
+ * If the lock was not acquired (due to timeout or signal) then the
+ * rt_waiter is removed before futex_q is. If this is observed by
+ * an unlocker after dropping the rtmutex wait lock and before
+ * acquiring the hash bucket lock, then the unlocker dequeues the
+ * futex_q from the hash bucket list to guarantee consistent state
+ * vs. userspace. Therefore the dequeue here must be conditional.
+ */
+ if (!plist_node_empty(&q->list))
+ __futex_unqueue(q);
BUG_ON(!q->pi_state);
put_pi_state(q->pi_state);
diff --git a/kernel/futex/pi.c b/kernel/futex/pi.c
index 90e5197..5722467 100644
--- a/kernel/futex/pi.c
+++ b/kernel/futex/pi.c
@@ -1135,6 +1135,7 @@ retry:
hb = futex_hash(&key);
spin_lock(&hb->lock);
+retry_hb:
/*
* Check waiters first. We do not trust user space values at
@@ -1177,12 +1178,17 @@ retry:
/*
* Futex vs rt_mutex waiter state -- if there are no rt_mutex
* waiters even though futex thinks there are, then the waiter
- * is leaving and the uncontended path is safe to take.
+ * is leaving. The entry needs to be removed from the list so a
+ * new futex_lock_pi() is not using this stale PI-state while
+ * the futex is available in user space again.
+ * There can be more than one task on its way out so it needs
+ * to retry.
*/
rt_waiter = rt_mutex_top_waiter(&pi_state->pi_mutex);
if (!rt_waiter) {
+ __futex_unqueue(top_waiter);
raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
- goto do_uncontended;
+ goto retry_hb;
}
get_pi_state(pi_state);
@@ -1217,7 +1223,6 @@ retry:
return ret;
}
-do_uncontended:
/*
* We have no kernel internal state, i.e. no waiters in the
* kernel. Waiters which are about to queue themselves are stuck