locking/rtmutex: Cure two subtle bugs
cover locking/rtmutex: Cure two subtle bugs
The recent updates to rtmutex introduced two subtle bugs:
1) The spinwait mechanism added a UAF which triggers a BUG_ON()
2) The ww_mutex addition leaves a waiter queued in the error exit path resulting in rb tree corruption
The fixes are straight forward, but the rtmutex based ww_mutex implementation still has some more rough egdes which need to be ironed out.
Thanks,
tglx
--- rtmutex.c | 12 +++++++++--- rtmutex_common.h | 13 +++++++++++++ 2 files changed, 22 insertions(+), 3 deletions(-)
PATCH 1/2 locking/rtmutex: Dont dereference waiter lockless
The new rt_mutex_spin_on_onwer() loop checks whether the spinning waiter is still the top waiter on the lock by utilizing rt_mutex_top_waiter(), which is broken because that function contains a sanity check which dereferences the top waiter pointer to check whether the waiter belongs to the lock. That's wrong in the lockless spinwait case:
CPU 0 CPU 1
rt_mutex_lock(lock) rt_mutex_lock(lock);
queue(waiter0)
waiter0 == rt_mutex_top_waiter(lock)
rt_mutex_spin_on_onwer(lock, waiter0) { queue(waiter1)
waiter1 == rt_mutex_top_waiter(lock)
...
top_waiter = rt_mutex_top_waiter(lock)
leftmost = rb_first_cached(&lock->waiters);
-> signal
dequeue(waiter1)
destroy(waiter1)
w = rb_entry(leftmost, ....)
BUG_ON(w->lock != lock) <- UAFThe BUG_ON() is correct for the case where the caller holds lock->wait_lock which guarantees that the leftmost waiter entry cannot vanish. For the lockless spinwait case it's broken.
Create a new helper function which avoids the pointer dereference and just compares the leftmost entry pointer with current's waiter pointer to validate that currrent is still elegible for spinning.
--- kernel/locking/rtmutex.c | 5 +++-- kernel/locking/rtmutex_common.h | 13 +++++++++++++ 2 files changed, 16 insertions(+), 2 deletions(-)
kernel/locking/rtmutex.c +3 -2
@@ -1329,8 +1329,9 @@ static bool rtmutex_spin_on_owner(struct* for CONFIG_PREEMPT_RCU=y) * - the VCPU on which owner runs is preempted */ -if (!owner->on_cpu || waiter !=rt_mutex_top_waiter (lock) || -need_resched () ||vcpu_is_preempted (task_cpu (owner))) { +if (!owner->on_cpu ||need_resched () || +rt_mutex_waiter_is_top_waiter (lock, waiter) || +vcpu_is_preempted (task_cpu (owner))) { res = false;break ; }
kernel/locking/rtmutex_common.h +13 -0
@@ -95,6 +95,19 @@ static inline int rt_mutex_has_waiters(sreturn !RB_EMPTY_ROOT (&lock->waiters.rb_root); } +/* +* Lockless speculative check whether @waiter is still the top waiter on +* @lock. This is solely comparing pointers and not derefencing the +* leftmost entry which might be about to vanish. +*/ +static inline bool rt_mutex_waiter_is_top_waiter (struct rt_mutex_base *lock, +struct rt_mutex_waiter *waiter) +{ +struct rb_node *leftmost =rb_first_cached (&lock->waiters); + + return rb_entry(leftmost, struct rt_mutex_waiter, tree_entry) == waiter; +} +static inline struct rt_mutex_waiter *rt_mutex_top_waiter (struct rt_mutex_base *lock) {struct rb_node *leftmost =rb_first_cached (&lock->waiters);
[tip: locking/core] locking/rtmutex: Dont dereference waiter lockless
The following commit has been merged into the locking/core branch of tip:
The following commit has been merged into the locking/core branch of tip:
Commit-ID: c3123c431447da99db160264506de9897c003513 Gitweb: https://git.kernel.org/tip/c3123c431447da99db160264506de9897c003513 Author: Thomas Gleixner <[email protected]> AuthorDate: Wed, 25 Aug 2021 12:33:12 +02:00 Committer: Peter Zijlstra <[email protected]> CommitterDate: Wed, 25 Aug 2021 15:42:32 +02:00
locking/rtmutex: Dont dereference waiter lockless
The new rt_mutex_spin_on_onwer() loop checks whether the spinning waiter is still the top waiter on the lock by utilizing rt_mutex_top_waiter(), which is broken because that function contains a sanity check which dereferences the top waiter pointer to check whether the waiter belongs to the lock. That's wrong in the lockless spinwait case:
CPU 0 CPU 1
rt_mutex_lock(lock) rt_mutex_lock(lock);
queue(waiter0)
waiter0 == rt_mutex_top_waiter(lock)
rt_mutex_spin_on_onwer(lock, waiter0) { queue(waiter1)
waiter1 == rt_mutex_top_waiter(lock)
...
top_waiter = rt_mutex_top_waiter(lock)
leftmost = rb_first_cached(&lock->waiters);
-> signal
dequeue(waiter1)
destroy(waiter1)
w = rb_entry(leftmost, ....)
BUG_ON(w->lock != lock) <- UAFThe BUG_ON() is correct for the case where the caller holds lock->wait_lock which guarantees that the leftmost waiter entry cannot vanish. For the lockless spinwait case it's broken.
Create a new helper function which avoids the pointer dereference and just compares the leftmost entry pointer with current's waiter pointer to validate that currrent is still elegible for spinning.
--- kernel/locking/rtmutex.c | 5 +++-- kernel/locking/rtmutex_common.h | 13 +++++++++++++ 2 files changed, 16 insertions(+), 2 deletions(-)
kernel/locking/rtmutex.c +3 -2
@@ -1329,8 +1329,9 @@ static bool rtmutex_spin_on_owner(struct rt_mutex_base *lock,* for CONFIG_PREEMPT_RCU=y) * - the VCPU on which owner runs is preempted */ -if (!owner->on_cpu || waiter !=rt_mutex_top_waiter (lock) || -need_resched () ||vcpu_is_preempted (task_cpu (owner))) { +if (!owner->on_cpu ||need_resched () || +rt_mutex_waiter_is_top_waiter (lock, waiter) || +vcpu_is_preempted (task_cpu (owner))) { res = false;break ; }
kernel/locking/rtmutex_common.h +13 -0
@@ -95,6 +95,19 @@ static inline int rt_mutex_has_waiters(struct rt_mutex_base *lock)return !RB_EMPTY_ROOT (&lock->waiters.rb_root); } +/* +* Lockless speculative check whether @waiter is still the top waiter on +* @lock. This is solely comparing pointers and not derefencing the +* leftmost entry which might be about to vanish. +*/ +static inline bool rt_mutex_waiter_is_top_waiter (struct rt_mutex_base *lock, +struct rt_mutex_waiter *waiter) +{ +struct rb_node *leftmost =rb_first_cached (&lock->waiters); + + return rb_entry(leftmost, struct rt_mutex_waiter, tree_entry) == waiter; +} +static inline struct rt_mutex_waiter *rt_mutex_top_waiter (struct rt_mutex_base *lock) {struct rb_node *leftmost =rb_first_cached (&lock->waiters);
PATCH 2/2 locking/rtmutex: Dequeue waiter on ww_mutex deadlock
In reply to Thomas GleixnerThe rt_mutex based ww_mutex variant queues the new waiter first in the lock's rbtree before evaluating the ww_mutex specific conditions which might decide that the waiter should back out. This check and conditional exit happens before the waiter is enqueued into the PI chain.
The failure handling at the call site assumes that the waiter, if it is the top most waiter on the lock, is queued in the PI chain and then proceeds to adjust the unmodified PI chain, which results in RB tree corruption.
Dequeue the waiter from the lock waiter list in the ww_mutex error exit path to prevent this.
--- kernel/locking/rtmutex.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-)
kernel/locking/rtmutex.c +6 -1
@@ -1082,8 +1082,13 @@ static int __sched task_blocks_on_rt_mut/* Check whether the waiter should back out immediately */ rtm = container_of(lock, struct rt_mutex, rtmutex); res =__ww_mutex_add_waiter (waiter, rtm, ww_ctx); -if (res) +if (res) { +raw_spin_lock (&task->pi_lock); +rt_mutex_dequeue (lock, waiter); + task->pi_blocked_on =NULL ; +raw_spin_unlock (&task->pi_lock);return res; + } }if (!owner)
[tip: locking/core] locking/rtmutex: Dequeue waiter on ww_mutex deadlock
The following commit has been merged into the locking/core branch of tip:
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 37e8abff2bebbf9947d6b784f5c75ed48a717089 Gitweb: https://git.kernel.org/tip/37e8abff2bebbf9947d6b784f5c75ed48a717089 Author: Thomas Gleixner <[email protected]> AuthorDate: Wed, 25 Aug 2021 12:33:14 +02:00 Committer: Peter Zijlstra <[email protected]> CommitterDate: Wed, 25 Aug 2021 15:42:33 +02:00
locking/rtmutex: Dequeue waiter on ww_mutex deadlock
The rt_mutex based ww_mutex variant queues the new waiter first in the lock's rbtree before evaluating the ww_mutex specific conditions which might decide that the waiter should back out. This check and conditional exit happens before the waiter is enqueued into the PI chain.
The failure handling at the call site assumes that the waiter, if it is the top most waiter on the lock, is queued in the PI chain and then proceeds to adjust the unmodified PI chain, which results in RB tree corruption.
Dequeue the waiter from the lock waiter list in the ww_mutex error exit path to prevent this.
--- kernel/locking/rtmutex.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-)
kernel/locking/rtmutex.c +6 -1
@@ -1082,8 +1082,13 @@ static int __sched task_blocks_on_rt_mutex(struct rt_mutex_base *lock,/* Check whether the waiter should back out immediately */ rtm = container_of(lock, struct rt_mutex, rtmutex); res =__ww_mutex_add_waiter (waiter, rtm, ww_ctx); -if (res) +if (res) { +raw_spin_lock (&task->pi_lock); +rt_mutex_dequeue (lock, waiter); + task->pi_blocked_on =NULL ; +raw_spin_unlock (&task->pi_lock);return res; + } }if (!owner)
Peter Zijlstra
maintainerQuoted 9 lines · Thomas Gleixner
The recent updates to rtmutex introduced two subtle bugs:
1) The spinwait mechanism added a UAF which triggers a
BUG_ON()2) The
ww_mutexaddition leaves a waiter queued in the error exit path resulting in rb tree corruptionThe fixes are straight forward, but the rtmutex based
ww_muteximplementation still has some more rough egdes which need to be ironed out.
Thanks!
Peter Zijlstra
maintainerQuoted 2 lines · Thomas Gleixner
The fixes are straight forward, but the rtmutex based
ww_muteximplementation still has some more rough egdes which need to be ironed out.
Something like the below (which should be two patches).
There's two issues at hand:
- 'spurious' -EDEADLK reports due to prior loops
- actual deadlock detection that will/should be resolved by ww_mutex instead.
Both stem from the fact that ww_mutex can legitimately create cycles in the lock graph. The first issue is because a blocker (P3 blow) can get trapped in a cycle it didn't cause and hit the iteration depth.
The latter can be observed when we suppose P2 to be the highest priority and thus should win progress rights over P1, but P2 would also be 'late' and be the one to close the cycle. In that case PI-walk would report -EDEADLK to P2, even though w/w would pick and wake P1 to receive -EDEADLK.
Now; afaict these conditions below capture the above, but then fail to adequately handle more complex locking chains where, for example, two w/w classes are inverted, which is a geniune deadlock, which the below will suppress.
Luckily w/w stuff is in-kernel only and lockdep should capture them; any user chains should be unaffected.
famous last words etc..
--- kernel/locking/rtmutex.c | 40 +++++++++++++++++++++++++++++++++++++++- 1 file changed, 39 insertions(+), 1 deletion(-)
kernel/locking/rtmutex.c +39 -1
@@ -656,6 +656,31 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,if (next_lock != waiter->lock) goto out_unlock_pi; +/* +* There could be 'spurious' loops in the lock graph due to ww_mutex, +* consider: +* +* P1: A, ww_A, ww_B +* P2: ww_B, ww_A +* P3: A +* +* P3 should not return -EDEADLK because it gets trapped in the cycle +* created by P1 and P2 (which will resolve -- and runs into +* max_lock_depth above). Therefore disable detect_deadlock such that +* the below termination condition can trigger once all relevant tasks +* are boosted. +* +* Even when we start with ww_mutex we can disable deadlock detection, +* since we would supress a ww_mutex induced deadlock at [6] anyway. +* Supressing it here however is not sufficient since we might still +* hit [6] due to adjustment driven iteration. +* +* NOTE: if someone were to create a deadlock between 2 ww_classes we'd +* utterly fail to report it; lockdep should. +*/ +if (waiter->ww_ctx && detect_deadlock) + detect_deadlock = false; +/* * Drop out, when the task has no waiters. Note, * top_waiter can be NULL, when we are in the deboosting
@@ -717,8 +742,21 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,* walk, we detected a deadlock. */ if (lock == orig_lock ||rt_mutex_owner (lock) == top_task) { -raw_spin_unlock (&lock->wait_lock); ret = -EDEADLK ; + +/* +* When the deadlock is due to ww_mutex; also see above. Don't +* report the deadlock and instead let the ww_mutex wound/die +* logic pick which of the contending threads gets -EDEADLK. +* +* NOTE: assumes the cycle only contains a single ww_class; any +* other configuration and we fail to report; also, see +* lockdep. +*/ +if (orig_waiter->ww_ctx) + ret =0 ; + +raw_spin_unlock (&lock->wait_lock); goto out_unlock_pi; }
Quoted 5 lines · Peter Zijlstra
Quoted 2 lines · Thomas Gleixner
The fixes are straight forward, but the rtmutex based
ww_muteximplementation still has some more rough egdes which need to be ironed out.Something like the below (which should be two patches).
tglx suggested to put an ifdef RT around the two checks since it is only needed by ww-mutex on RT. The patch below is what I committed to my RT tree.
From: Peter Zijlstra <[email protected]>
Date: Thu, 26 Aug 2021 16:39:51 +0200
Subject: [PATCH] locking/rtmutex: Let ww-mutex handle deadlock detection.
There's two issues at hand:
- 'spurious' -EDEADLK reports due to prior loops
- actual deadlock detection that will/should be resolved by ww_mutex instead.
Both stem from the fact that ww_mutex can legitimately create cycles in the lock graph. The first issue is because a blocker (P3 blow) can get trapped in a cycle it didn't cause and hit the iteration depth.
The latter can be observed when we suppose P2 to be the highest priority and thus should win progress rights over P1, but P2 would also be 'late' and be the one to close the cycle. In that case PI-walk would report -EDEADLK to P2, even though w/w would pick and wake P1 to receive -EDEADLK.
Now; afaict these conditions below capture the above, but then fail to adequately handle more complex locking chains where, for example, two w/w classes are inverted, which is a geniune deadlock, which the below will suppress.
Luckily w/w stuff is in-kernel only and lockdep should capture them; any user chains should be unaffected.
famous last words etc..
--- kernel/locking/rtmutex.c | 43 +++++++++++++++++++++++++++++++++++++++- 1 file changed, 42 insertions(+), 1 deletion(-)
kernel/locking/rtmutex.c +42 -1
@@ -656,6 +656,33 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,if (next_lock != waiter->lock) goto out_unlock_pi; +#ifdef CONFIG_PREEMPT_RT +/* +* There could be 'spurious' loops in the lock graph due to ww_mutex, +* consider: +* +* P1: A, ww_A, ww_B +* P2: ww_B, ww_A +* P3: A +* +* P3 should not return -EDEADLK because it gets trapped in the cycle +* created by P1 and P2 (which will resolve -- and runs into +* max_lock_depth above). Therefore disable detect_deadlock such that +* the below termination condition can trigger once all relevant tasks +* are boosted. +* +* Even when we start with ww_mutex we can disable deadlock detection, +* since we would supress a ww_mutex induced deadlock at [6] anyway. +* Supressing it here however is not sufficient since we might still +* hit [6] due to adjustment driven iteration. +* +* NOTE: if someone were to create a deadlock between 2 ww_classes we'd +* utterly fail to report it; lockdep should. +*/ +if (waiter->ww_ctx && detect_deadlock) + detect_deadlock = false; +#endif +/* * Drop out, when the task has no waiters. Note, * top_waiter can be NULL, when we are in the deboosting
@@ -717,8 +744,22 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,* walk, we detected a deadlock. */ if (lock == orig_lock ||rt_mutex_owner (lock) == top_task) { -raw_spin_unlock (&lock->wait_lock); ret = -EDEADLK ; + +#ifdef CONFIG_PREEMPT_RT +/* +* When the deadlock is due to ww_mutex; also see above. Don't +* report the deadlock and instead let the ww_mutex wound/die +* logic pick which of the contending threads gets -EDEADLK. +* +* NOTE: assumes the cycle only contains a single ww_class; any +* other configuration and we fail to report; also, see +* lockdep. +*/ +if (orig_waiter->ww_ctx) + ret =0 ; +#endif +raw_spin_unlock (&lock->wait_lock); goto out_unlock_pi; }
Signature · 1 line
2.33.0
[tip: locking/core] locking/rtmutex: Return success on deadlock for ww_mutex waiters
In reply to Peter ZijlstraThe following commit has been merged into the locking/core branch of tip:
The following commit has been merged into the locking/core branch of tip:
Commit-ID: a055fcc132d4c25b96d1115aea514258810dc6fc Gitweb: https://git.kernel.org/tip/a055fcc132d4c25b96d1115aea514258810dc6fc Author: Peter Zijlstra <[email protected]> AuthorDate: Thu, 26 Aug 2021 10:48:18 +02:00 Committer: Thomas Gleixner <[email protected]> CommitterDate: Fri, 27 Aug 2021 14:28:49 +02:00
locking/rtmutex: Return success on deadlock for ww_mutex waiters
ww_mutexes can legitimately cause a deadlock situation in the lock graph which is resolved afterwards by the wait/wound mechanics. The rtmutex chain walk can detect such a deadlock and returns EDEADLK which in turn skips the wait/wound mechanism and returns EDEADLK to the caller. That's wrong because both lock chains might get EDEADLK or the wrong waiter would back out.
Detect that situation and return 'success' in case that the waiter which initiated the chain walk is a ww_mutex with context. This allows the wait/wound mechanics to resolve the situation according to the rules.
[ tglx: Split it apart and added changelog ]
--- kernel/locking/rtmutex.c | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-)
kernel/locking/rtmutex.c +14 -1
@@ -742,8 +742,21 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,* walk, we detected a deadlock. */ if (lock == orig_lock ||rt_mutex_owner (lock) == top_task) { -raw_spin_unlock (&lock->wait_lock); ret = -EDEADLK ; + +/* +* When the deadlock is due to ww_mutex; also see above. Don't +* report the deadlock and instead let the ww_mutex wound/die +* logic pick which of the contending threads gets -EDEADLK. +* +* NOTE: assumes the cycle only contains a single ww_class; any +* other configuration and we fail to report; also, see +* lockdep. +*/ +if (IS_ENABLED (CONFIG_PREEMPT_RT ) && orig_waiter->ww_ctx) + ret =0 ; + +raw_spin_unlock (&lock->wait_lock); goto out_unlock_pi; }
[tip: locking/core] locking/rtmutex: Prevent spurious EDEADLK return caused by ww_mutexes
In reply to Peter ZijlstraThe following commit has been merged into the locking/core branch of tip:
The following commit has been merged into the locking/core branch of tip:
Commit-ID: 6467822b8cc96e5feda98c7bf5c6329c6a896c91 Gitweb: https://git.kernel.org/tip/6467822b8cc96e5feda98c7bf5c6329c6a896c91 Author: Peter Zijlstra <[email protected]> AuthorDate: Thu, 26 Aug 2021 09:36:53 +02:00 Committer: Thomas Gleixner <[email protected]> CommitterDate: Fri, 27 Aug 2021 14:28:49 +02:00
locking/rtmutex: Prevent spurious EDEADLK return caused by ww_mutexes
rtmutex based ww_mutexes can legitimately create a cycle in the lock graph which can be observed by a blocker which didn't cause the problem:
P1: A, ww_A, ww_B
P2: ww_B, ww_A
P3: A
P3 might therefore be trapped in the ww_mutex induced cycle and run into the lock depth limitation of rt_mutex_adjust_prio_chain() which returns -EDEADLK to the caller.
Disable the deadlock detection walk when the chain walk observes a ww_mutex to prevent this looping.
[ tglx: Split it apart and added changelog ]
--- kernel/locking/rtmutex.c | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+)
kernel/locking/rtmutex.c +25 -0
@@ -657,6 +657,31 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task, goto out_unlock_pi;/* +* There could be 'spurious' loops in the lock graph due to ww_mutex, +* consider: +* +* P1: A, ww_A, ww_B +* P2: ww_B, ww_A +* P3: A +* +* P3 should not return -EDEADLK because it gets trapped in the cycle +* created by P1 and P2 (which will resolve -- and runs into +* max_lock_depth above). Therefore disable detect_deadlock such that +* the below termination condition can trigger once all relevant tasks +* are boosted. +* +* Even when we start with ww_mutex we can disable deadlock detection, +* since we would supress a ww_mutex induced deadlock at [6] anyway. +* Supressing it here however is not sufficient since we might still +* hit [6] due to adjustment driven iteration. +* +* NOTE: if someone were to create a deadlock between 2 ww_classes we'd +* utterly fail to report it; lockdep should. +*/ +if (IS_ENABLED (CONFIG_PREEMPT_RT ) && waiter->ww_ctx && detect_deadlock) + detect_deadlock = false; + +/* * Drop out, when the task has no waiters. Note, * top_waiter can be NULL, when we are in the deboosting * mode!