locking/rtmutex: Delete save_state member of struct rt_mutex
PATCH 1/2 locking/rtmutex: Delete save_state member of struct rt_mutex
This field (debug) is unused. Furthermore it looks like a result of rtmutex from -rt into upstream, where it serves to determine if the wakeup is for a task blocked on a "sleeping spinlock", iow if this is a regular rt_mutex_lock() or rt_spin_lock().
Of course, upstream we only have regular rt_mutexes, thus we can safely assume nothing will be done with this field anyway. There is also the fact that this is under debug.
--- include/linux/rtmutex.h | 1 - 1 file changed, 1 deletion(-)
include/linux/rtmutex.h +0 -1
@@ -32,7 +32,6 @@ struct rt_mutex {struct rb_root_cached waiters;struct task_struct *owner;#ifdef CONFIG_DEBUG_RT_MUTEXES -int save_state;const char *name, *file;int line;void *magic;
Signature · 1 line
2.13.6
PATCH 2/2 rtmutex: Reduce top-waiter blocking on a lock
By applying well known spin-on-lock-owner techniques, we can avoid the blocking overhead during the process of when the task is trying to take the rtmutex. The idea is that as long as the owner is running, there is a fair chance it'll release the lock soon, and thus a task trying to acquire the rtmutex will better off spinning instead of blocking immediately after the fastpath. This is similar to what we use for other locks, borrowed from -rt. The main difference (due to the obvious realtime constraints) is that top-waiter spinning must account for any new higher priority waiter, and therefore cannot steal the lock and avoid any pi-dance. As such there will be at most only one spinner waiter upon contended lock.
Conditions to stop spinning and block are simple:
(1) Upon need_resched()
(2) Current lock owner blocks
(3) The top-waiter has changed while spinning.
The unlock side remains unchanged as wake_up_process can safely deal with calls where the task is not actually blocked (TASK_NORMAL). As such, there is only unnecessary overhead dealing with the wake_q, but this allows us not to miss any wakeups between the spinning step and the unlocking side.
Passes running the pi_stress program with increasing thread-group counts.
--- kernel/Kconfig.locks | 6 ++++- kernel/locking/rtmutex.c | 62 +++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 66 insertions(+), 2 deletions(-)
kernel/Kconfig.locks +5 -1
@@ -227,13 +227,17 @@ config MUTEX_SPIN_ON_OWNER def_bool y depends on SMP && ARCH_SUPPORTS_ATOMIC_RMW +config RT_MUTEX_SPIN_ON_OWNER + def_bool y + depends on SMP && RT_MUTEXES && !DEBUG_RT_MUTEXES && ARCH_SUPPORTS_ATOMIC_RMW + config RWSEM_SPIN_ON_OWNER def_bool y depends on SMP && RWSEM_XCHGADD_ALGORITHM && ARCH_SUPPORTS_ATOMIC_RMW config LOCK_SPIN_ON_OWNER def_bool y - depends on MUTEX_SPIN_ON_OWNER || RWSEM_SPIN_ON_OWNER + depends on MUTEX_SPIN_ON_OWNER || RWSEM_SPIN_ON_OWNER || RT_MUTEX_SPIN_ON_OWNER config ARCH_USE_QUEUED_SPINLOCKS bool
kernel/locking/rtmutex.c +61 -1
84 lines not on this page · raw message
Signature · 1 line
2.13.6
kbuild test robot
build botRe: [PATCH 2/2] rtmutex: Reduce top-waiter blocking on a lock
I love your patch! Perhaps something to improve:
Hi Davidlohr,
I love your patch! Perhaps something to improve:
[auto build test WARNING on linus/master]
[also build test WARNING on v4.16 next-20180411]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
url: https://github.com/0day-ci/linux/commits/Davidlohr-Bueso/locking-rtmutex-Delete-save_state-member-of-struct-rt_mutex/20180411-155733
reproduce:
# apt-get install sparse
make ARCH=x86_64 allmodconfig
make C=1 CF=-D__CHECK_ENDIAN__sparse warnings: (new ones prefixed by >>)
>> kernel/locking/rtmutex_common.h:62:9: sparse: context imbalance in '__rt_mutex_slowlock' - unexpected unlock
vim +/__rt_mutex_slowlock +62 kernel/locking/rtmutex_common.h
23f78d4a0 kernel/rtmutex_common.h Ingo Molnar 2006-06-27 51
23f78d4a0 kernel/rtmutex_common.h Ingo Molnar 2006-06-27 52 static inline struct rt_mutex_waiter *
23f78d4a0 kernel/rtmutex_common.h Ingo Molnar 2006-06-27 53 rt_mutex_top_waiter(struct rt_mutex *lock)
23f78d4a0 kernel/rtmutex_common.h Ingo Molnar 2006-06-27 54 {
c28d62cf5 kernel/locking/rtmutex_common.h Peter Zijlstra 2018-03-27 55 struct rb_node *leftmost = rb_first_cached(&lock->waiters);
c28d62cf5 kernel/locking/rtmutex_common.h Peter Zijlstra 2018-03-27 56 struct rt_mutex_waiter *w = NULL;
23f78d4a0 kernel/rtmutex_common.h Ingo Molnar 2006-06-27 57
c28d62cf5 kernel/locking/rtmutex_common.h Peter Zijlstra 2018-03-27 58 if (leftmost) {
c28d62cf5 kernel/locking/rtmutex_common.h Peter Zijlstra 2018-03-27 59 w = rb_entry(leftmost, struct rt_mutex_waiter, tree_entry);
23f78d4a0 kernel/rtmutex_common.h Ingo Molnar 2006-06-27 60 BUG_ON(w->lock != lock);
c28d62cf5 kernel/locking/rtmutex_common.h Peter Zijlstra 2018-03-27 61 }
23f78d4a0 kernel/rtmutex_common.h Ingo Molnar 2006-06-27 @62 return w;
23f78d4a0 kernel/rtmutex_common.h Ingo Molnar 2006-06-27 63 }
23f78d4a0 kernel/rtmutex_common.h Ingo Molnar 2006-06-27 64 :::::: The code at line 62 was first introduced by commit
:::::: 23f78d4a03c53cbd75d87a795378ea540aa08c86 [PATCH] pi-futex: rt mutex core
:::::: TO: Ingo Molnar <[email protected]>
:::::: CC: Linus Torvalds <[email protected]>
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation
Re: [PATCH 2/2] rtmutex: Reduce top-waiter blocking on a lock
Quoted 8 lines · kbuild test robot
Hi Davidlohr,
I love your patch! Perhaps something to improve:
[auto build test WARNING on linus/master]
[also build test WARNING on v4.16 next-20180411]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
Quoted 5 lines
url: https://github.com/0day-ci/linux/commits/Davidlohr-Bueso/locking-rtmutex-Delete-save_state-member-of-struct-rt_mutex/20180411-155733
reproduce:# apt-get install sparse make ARCH=x86_64 allmodconfig make C=1 CF=-D__CHECK_ENDIAN__
Ok.
Quoted 5 lines
sparse warnings: (new ones prefixed by >>)
Quoted 1 line
Quoted 1 line
kernel/locking/rtmutex_common.h:62:9: sparse: context imbalance in '__rt_mutex_slowlock' - unexpected unlock
I did:
make C=1 CF=-D__CHECK_ENDIAN__ kernel/locking/rtmutex.o
But cannot trigger this message. There are however a ton of other sparse issues with 'indirect_branch'. Ie:
./arch/x86/include/asm/nospec-branch.h:144:38: warning: Unknown escape '@' ./include/linux/init.h:134:6: error: attribute 'indirect_branch': unknown attribute ./include/linux/init.h:135:5: error: attribute 'indirect_branch': unknown attribute
More importantly, I don't follow where this "unexpected unlock" would come from considering that rtmutex doesn't use __acquires/__releases annotations. Nor do I understand why this patch would produce a new context imbalance.
Thanks,
Davidlohr
Peter Zijlstra
maintainerRe: [PATCH 2/2] rtmutex: Reduce top-waiter blocking on a lock
In reply to Davidlohr BuesoQuoted 17 lines · Davidlohr Bueso
By applying well known spin-on-lock-owner techniques, we can avoid the blocking overhead during the process of when the task is trying to take the rtmutex. The idea is that as long as the owner is running, there is a fair chance it'll release the lock soon, and thus a task trying to acquire the rtmutex will better off spinning instead of blocking immediately after the fastpath. This is similar to what we use for other locks, borrowed from -rt. The main difference (due to the obvious realtime constraints) is that top-waiter spinning must account for any new higher priority waiter, and therefore cannot steal the lock and avoid any pi-dance. As such there will be at most only one spinner waiter upon contended lock.
Conditions to stop spinning and block are simple:
(1) Upon
need_resched()
(2) Current lock owner blocks
(3) The top-waiter has changed while spinning.
Quoted 6 lines
The unlock side remains unchanged as
wake_up_processcan safely deal with calls where the task is not actually blocked (TASK_NORMAL). As such, there is only unnecessary overhead dealing with thewake_q, but this allows us not to miss any wakeups between the spinning step and the unlocking side.Passes running the
pi_stressprogram with increasing thread-group counts.
Is this similar to what we have in RT (which, IIRC, has an optimistic spinning implementation as well)?
ISTR there being some contention over the exact semantics of (3) many years ago. IIRC the question was if an equal priority task was allowed to steal; because lock stealing can lead to fairness issues. One would expect two FIFO-50 tasks to be 'fair' wrt lock acquisition and not starve one another.
Therefore I think we only allowed higher prio tasks to steal and kept FIFO order for equal prioty tasks.
Re: [PATCH 2/2] rtmutex: Reduce top-waiter blocking on a lock
Quoted 23 lines · Peter Zijlstra
Quoted 22 lines · Davidlohr Bueso
By applying well known spin-on-lock-owner techniques, we can avoid the blocking overhead during the process of when the task is trying to take the rtmutex. The idea is that as long as the owner is running, there is a fair chance it'll release the lock soon, and thus a task trying to acquire the rtmutex will better off spinning instead of blocking immediately after the fastpath. This is similar to what we use for other locks, borrowed from -rt. The main difference (due to the obvious realtime constraints) is that top-waiter spinning must account for any new higher priority waiter, and therefore cannot steal the lock and avoid any pi-dance. As such there will be at most only one spinner waiter upon contended lock.
Conditions to stop spinning and block are simple:
(1) Upon
need_resched()
(2) Current lock owner blocks
(3) The top-waiter has changed while spinning.The unlock side remains unchanged as
wake_up_processcan safely deal with calls where the task is not actually blocked (TASK_NORMAL). As such, there is only unnecessary overhead dealing with thewake_q, but this allows us not to miss any wakeups between the spinning step and the unlocking side.
Quoted 4 lines
Quoted 1 line
Passes running the
pi_stressprogram with increasing thread-group counts.Is this similar to what we have in RT (which, IIRC, has an optimistic spinning implementation as well)?
For the RT spinlock replacement, the top waiter can spin.
Quoted 8 lines
ISTR there being some contention over the exact semantics of (3) many years ago. IIRC the question was if an equal priority task was allowed to steal; because lock stealing can lead to fairness issues. One would expect two FIFO-50 tasks to be 'fair' wrt lock acquisition and not starve one another.
Therefore I think we only allowed higher prio tasks to steal and kept FIFO order for equal prioty tasks.
Yup, lateral steal is expressly forbidden for RT classes.
+#define STEAL_NORMAL 0
+#define STEAL_LATERAL 1
+
+static inline int
+rt_mutex_steal(struct rt_mutex *lock, struct rt_mutex_waiter *waiter, int mode) +{
+ struct rt_mutex_waiter *top_waiter = rt_mutex_top_waiter(lock); +
+ if (waiter == top_waiter || rt_mutex_waiter_less(waiter, top_waiter)) + return 1;
+
+ /*
+ * Note that RT tasks are excluded from lateral-steals
+ * to prevent the introduction of an unbounded latency.
+ */
+ if (mode == STEAL_NORMAL || rt_task(waiter->task))
+ return 0;
+
+ return rt_mutex_waiter_equal(waiter, top_waiter);
+}
+
Re: [PATCH 2/2] rtmutex: Reduce top-waiter blocking on a lock
Quoted 5 lines · Mike Galbraith
Quoted 2 lines · Peter Zijlstra
Is this similar to what we have in RT (which, IIRC, has an optimistic spinning implementation as well)?
For the RT spinlock replacement, the top waiter can spin.
Yeah and the difference with the rt-spinlock and this patch are points
(1) and (3). Probably worth mentioning and, at least at first thought, the rt version might benefit from these breaking out of the spin loop; lateral or normal, I doubt the rt-spinlock wants to adaptive_wait() if the top_waiter changed.
Quoted 6 lines
Quoted 6 lines
ISTR there being some contention over the exact semantics of (3) many years ago. IIRC the question was if an equal priority task was allowed to steal; because lock stealing can lead to fairness issues. One would expect two FIFO-50 tasks to be 'fair' wrt lock acquisition and not starve one another.
Indeed.
Quoted 3 lines
Quoted 3 lines
Therefore I think we only allowed higher prio tasks to steal and kept FIFO order for equal prioty tasks.
Right. In fact this patch is a very limited version of optimistic spinning because we have little room too break fairness and rt constraints (ie no osq, etc).
So say waiter task A is spinning for the rtmutex when task B (with equal prio) comes in and tries to take it as well. Because when B is being enqueued we don't comply with rt_mutex_waiter_less(A, B), so we go rb_right. As such the top-waiter pointer is not updated and therefore B blocks while A keeps spinning and take the lock hopefully without blocking. And if we do block we're still top-waiter so fifo wrt waiter B all the way.
Quoted 2 lines
Yup, lateral steal is expressly forbidden for RT classes.
Only rt-spinlocks allow lateral stealing, this patch uses the same normal stealing semantics as what rtmutex already provide. And either way I don't see how rt_mutex_spin_on_owner() will influence on current rtmutex semantics as all that changes is not calling schedule(), and we are already accounted for and queued in the waiter tree.
Thanks,
Davidlohr
Re: [PATCH 2/2] rtmutex: Reduce top-waiter blocking on a lock
In reply to Davidlohr BuesoIf there are no objections, now that the merge window closed, could this be considered for v4.19?
Thanks,
Davidlohr
Quoted 147 lines · Davidlohr Bueso
By applying well known spin-on-lock-owner techniques, we can avoid the blocking overhead during the process of when the task is trying to take the rtmutex. The idea is that as long as the owner is running, there is a fair chance it'll release the lock soon, and thus a task trying to acquire the rtmutex will better off spinning instead of blocking immediately after the fastpath. This is similar to what we use for other locks, borrowed from -rt. The main difference (due to the obvious realtime constraints) is that top-waiter spinning must account for any new higher priority waiter, and therefore cannot steal the lock and avoid any pi-dance. As such there will be at most only one spinner waiter upon contended lock.
Conditions to stop spinning and block are simple:
(1) Upon
need_resched()
(2) Current lock owner blocks
(3) The top-waiter has changed while spinning.The unlock side remains unchanged as
wake_up_processcan safely deal with calls where the task is not actually blocked (TASK_NORMAL). As such, there is only unnecessary overhead dealing with thewake_q, but this allows us not to miss any wakeups between the spinning step and the unlocking side.Passes running the
pi_stressprogram with increasing thread-group counts.Signed-off-by Davidlohr Bueso <[email protected]>---
kernel/Kconfig.locks| 6 ++++-kernel/locking/rtmutex.c| 62 +++++++++++++++++++++++++++++++++++++++++++++++-2 files changed, 66 insertions(+), 2 deletions(-)kernel/Kconfig.locks +4
-0@@ -227,13 +227,17 @@ config MUTEX_SPIN_ON_OWNER def_bool y depends on SMP && ARCH_SUPPORTS_ATOMIC_RMW +config RT_MUTEX_SPIN_ON_OWNER + def_bool y + depends on SMP && RT_MUTEXES && !DEBUG_RT_MUTEXES && ARCH_SUPPORTS_ATOMIC_RMW +config
RWSEM_SPIN_ON_OWNERdef_bool y depends on SMP && RWSEM_XCHGADD_ALGORITHM && ARCH_SUPPORTS_ATOMIC_RMWconfig
LOCK_SPIN_ON_OWNER
def_boolykernel/Kconfig.locks +1
-1- depends on MUTEX_SPIN_ON_OWNER || RWSEM_SPIN_ON_OWNER + depends on MUTEX_SPIN_ON_OWNER || RWSEM_SPIN_ON_OWNER || RT_MUTEX_SPIN_ON_OWNERconfig
ARCH_USE_QUEUED_SPINLOCKS
boolkernel/locking/rtmutex.c +61
-1@@ -1154,6 +1154,55 @@ void rt_mutex_init_waiter(struct rt_mutex_waiter *waiter) waiter->task =NULL ; } +#ifdef CONFIG_RT_MUTEX_SPIN_ON_OWNER +static bool rt_mutex_spin_on_owner (struct rt_mutex *lock, +struct rt_mutex_waiter *waiter, +struct task_struct *owner) +{ +bool ret = true; + +/* +* The last owner could have just released the lock, +* immediately try taking it again. +*/ +if (!owner) + goto done; + +rcu_read_lock (); +while (rt_mutex_owner (lock) == owner) { +/* +* Ensure we emit the owner->on_cpu, dereference _after_ +* checking lock->owner still matches owner. If that fails, +* owner might point to freed memory. If it still matches, +* the rcu_read_lock() ensures the memory stays valid. +* +* Also account for changes in the lock's top-waiter, if it's +* not us, it was updated while busy waiting. +*/ +barrier (); + +if (!owner->on_cpu ||need_resched () || + waiter !=rt_mutex_top_waiter (lock)) { + ret = false; +break ; + } + +cpu_relax (); + } +rcu_read_unlock (); +done: +return ret; +} + +#else +static bool rt_mutex_spin_on_owner (struct rt_mutex *lock, +struct rt_mutex_waiter *waiter, +struct task_struct *owner) +{ +return false; +} +#endif +/** * __rt_mutex_slowlock() - Perform the wait-wake-try-to-take loop * @lock: the rt_mutex to take @@ -1172,6 +1221,8 @@ __rt_mutex_slowlock(struct rt_mutex *lock, int state,int ret =0 ;for (;;) { +struct rt_mutex_waiter *top_waiter =NULL ; +/* Try to acquire the lock: */ if (try_to_take_rt_mutex (lock, current, waiter))break ;@@ -1190,11 +1241,20 @@ __rt_mutex_slowlock(struct rt_mutex *lock, int state,break ; } + top_waiter =rt_mutex_top_waiter (lock);raw_spin_unlock_irq (&lock->wait_lock);debug_rt_mutex_print_deadlock (waiter); -schedule (); +/* +* At this point the PI-dance is done, and, as the top waiter, +* we are next in line for the lock. Try to spin on the current +* owner for a while, in the hope that the lock will be released +* soon. Otherwise fallback and block. +*/ +if (top_waiter != waiter || + !rt_mutex_spin_on_owner (lock, waiter,rt_mutex_owner (lock))) +schedule ();raw_spin_lock_irq (&lock->wait_lock);set_current_state (state);Signature · 1 line
2.13.6
[PATCH 3/2] rtmutex: Use waiter debug init,free magic numbers
In reply to Davidlohr Bueso... we already use these for regular mutexes, rtmutex can also use it, and while at it rename the whole thing since this is specific to waiters.
---
include/linux/poison.h | 4 ++-- kernel/locking/mutex-debug.c | 4 ++-- kernel/locking/rtmutex-debug.c | 4 ++-- 3 files changed, 6 insertions(+), 6 deletions(-)
include/linux/poison.h +0 -0
@@ -79,8 +79,8 @@
#define ATM_POISON 0xdeadbeef
/********** kernel/mutexes **********/
-#define MUTEX_DEBUG_INIT 0x11
-#define MUTEX_DEBUG_FREE 0x22
+#define MUTEX_WAITER_DEBUG_INIT 0x11
+#define MUTEX_WAITER_DEBUG_FREE 0x22
#define MUTEX_POISON_WW_CTX ((void *) 0x500 + POISON_POINTER_DELTA)
/********** lib/flex_array.c **********/
kernel/locking/mutex-debug.c +0 -0
@@ -29,7 +29,7 @@*/
void debug_mutex_lock_common(struct mutex *lock, struct mutex_waiter *waiter) {
- memset(waiter, MUTEX_DEBUG_INIT, sizeof(*waiter));
+ memset(waiter, MUTEX_WAITER_DEBUG_INIT, sizeof(*waiter));
waiter->magic = waiter;
INIT_LIST_HEAD(&waiter->list);
}
@@ -45,7 +45,7 @@ void debug_mutex_wake_waiter(struct mutex *lock, struct mutex_waiter *waiter)
void debug_mutex_free_waiter(struct mutex_waiter *waiter)
{
DEBUG_LOCKS_WARN_ON(!list_empty(&waiter->list));- memset(waiter, MUTEX_DEBUG_FREE, sizeof(*waiter));
+ memset(waiter, MUTEX_WAITER_DEBUG_FREE, sizeof(*waiter));
}
void debug_mutex_add_waiter(struct mutex *lock, struct mutex_waiter *waiter,
kernel/locking/rtmutex-debug.c +0 -0
@@ -157,14 +157,14 @@ void debug_rt_mutex_proxy_unlock(struct rt_mutex *lock)
void debug_rt_mutex_init_waiter(struct rt_mutex_waiter *waiter) {
- memset(waiter, 0x11, sizeof(*waiter));
+ memset(waiter, MUTEX_WAITER_DEBUG_INIT, sizeof(*waiter)); waiter->deadlock_task_pid = NULL; }
void debug_rt_mutex_free_waiter(struct rt_mutex_waiter *waiter)
{
put_pid(waiter->deadlock_task_pid);- memset(waiter, 0x22, sizeof(*waiter));
+ memset(waiter, MUTEX_WAITER_DEBUG_FREE, sizeof(*waiter));
}
void debug_rt_mutex_init(struct rt_mutex *lock, const char *name, struct lock_class_key *key)
Signature · 1 line
2.13.6