locking/qspinlock: Handle > 4 nesting levels
Subsystems (3)
Waiman Long
reviewerv3 cover locking/qspinlock: Handle > 4 nesting levels
v3:
- Fix typo error in patch 2.
- Rework patches 3/4 to create a new lockevent_* API to handle lock event counting that can be used by other locking code as well as on all architectures that are applicable.
v2:
- Use the simple trylock loop as suggested by PeterZ.
The current allows up to 4 levels of nested slowpath spinlock calls. That should be enough for the process, soft irq, hard irq, and nmi. With the unfortunate event of nested NMIs happening with slowpath spinlock call in each of the previous level, we are going to run out of useable MCS node for queuing.
In this case, we fall back to a simple TAS lock and spin on the lock cacheline until the lock is free. This is not most elegant solution but is simple enough.
Patch 1 implements the TAS loop when all the existing MCS nodes are occupied.
Patch 2 adds a new counter to track the no MCS node available event.
Patches 3 & 4 create a a new lockevent_* API to handle lock event counting that can be used by other locking code as well as on all architectures that are applicable.
By setting MAX_NODES to 1, we can have some usage of the new code path during the booting process as demonstrated by the stat counter values shown below on an 1-socket 22-core 44-thread x86-64 system after booting up the new kernel.
lock_no_node=20
lock_pending=29660
lock_slowpath=172714
Waiman Long (4):
locking/qspinlock: Handle > 4 slowpath nesting levels locking/qspinlock_stat: Track the no MCS node available case locking/qspinlock_stat: Introduce a generic lockevent counting APIs locking/lock_events: Make lock_events available for all archs & other
locks
arch/Kconfig | 10 ++ arch/x86/Kconfig | 8 -- kernel/locking/Makefile | 1 + kernel/locking/lock_events.c | 152 +++++++++++++++++++++++ kernel/locking/lock_events.h | 46 +++++++ kernel/locking/lock_events_list.h | 49 ++++++++ kernel/locking/qspinlock.c | 22 +++- kernel/locking/qspinlock_paravirt.h | 19 +-- kernel/locking/qspinlock_stat.h | 233 +++++++----------------------------- 9 files changed, 330 insertions(+), 210 deletions(-) create mode 100644 kernel/locking/lock_events.c create mode 100644 kernel/locking/lock_events.h create mode 100644 kernel/locking/lock_events_list.h
Signature · 1 line
1.8.3.1
Waiman Long
reviewerPATCH v3 1/4 locking/qspinlock: Handle > 4 slowpath nesting levels
Four queue nodes per cpu are allocated to enable up to 4 nesting levels using the per-cpu nodes. Nested NMIs are possible in some architectures. Still it is very unlikely that we will ever hit more than 4 nested levels with contention in the slowpath.
When that rare condition happens, however, it is likely that the system will hang or crash shortly after that. It is not good and we need to handle this exception case.
This is done by spinning directly on the lock using repeated trylock. This alternative code path should only be used when there is nested NMIs. Assuming that the locks used by those NMI handlers will not be heavily contended, a simple TAS locking should work out.
--- kernel/locking/qspinlock.c | 15 +++++++++++++++ 1 file changed, 15 insertions(+)
kernel/locking/qspinlock.c +15 -0
@@ -412,6 +412,21 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) idx = node->count++; tail =encode_tail (smp_processor_id (), idx); +/* +* 4 nodes are allocated based on the assumption that there will +* not be nested NMIs taking spinlocks. That may not be true in +* some architectures even though the chance of needing more than +* 4 nodes will still be extremely unlikely. When that happens, +* we fall back to spinning on the lock directly without using +* any MCS node. This is not the most elegant solution, but is +* simple enough. +*/ +if (unlikely (idx >=MAX_NODES )) { +while (!queued_spin_trylock (lock)) +cpu_relax (); + goto release; + } + node =grab_mcs_node (node, idx);/*
Signature · 1 line
1.8.3.1
tip-bot for Waiman Long
merge bot[tip:locking/core] locking/qspinlock: Handle > 4 slowpath nesting levels
locking/qspinlock: Handle > 4 slowpath nesting levels
Commit-ID: d682b596d99345ef0000e7017db714ba7f29e017 Gitweb: https://git.kernel.org/tip/d682b596d99345ef0000e7017db714ba7f29e017 Author: Waiman Long <[email protected]> AuthorDate: Tue, 29 Jan 2019 22:53:45 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 4 Feb 2019 09:03:29 +0100
locking/qspinlock: Handle > 4 slowpath nesting levels
Four queue nodes per CPU are allocated to enable up to 4 nesting levels using the per-CPU nodes. Nested NMIs are possible in some architectures. Still it is very unlikely that we will ever hit more than 4 nested levels with contention in the slowpath.
When that rare condition happens, however, it is likely that the system will hang or crash shortly after that. It is not good and we need to handle this exception case.
This is done by spinning directly on the lock using repeated trylock. This alternative code path should only be used when there is nested NMIs. Assuming that the locks used by those NMI handlers will not be heavily contended, a simple TAS locking should work out.
--- kernel/locking/qspinlock.c | 15 +++++++++++++++ 1 file changed, 15 insertions(+)
kernel/locking/qspinlock.c +15 -0
@@ -412,6 +412,21 @@ pv_queue: idx = node->count++; tail =encode_tail (smp_processor_id (), idx); +/* +* 4 nodes are allocated based on the assumption that there will +* not be nested NMIs taking spinlocks. That may not be true in +* some architectures even though the chance of needing more than +* 4 nodes will still be extremely unlikely. When that happens, +* we fall back to spinning on the lock directly without using +* any MCS node. This is not the most elegant solution, but is +* simple enough. +*/ +if (unlikely (idx >=MAX_NODES )) { +while (!queued_spin_trylock (lock)) +cpu_relax (); + goto release; + } + node =grab_mcs_node (node, idx);/*
Waiman Long
reviewerPATCH v3 2/4 locking/qspinlock_stat: Track the no MCS node available case
In reply to Waiman LongTrack the number of slowpath locking operations that are being done without any MCS node available as well renaming lock_index[123] to make them more descriptive.
Using these stat counters is one way to find out if a code path is being exercised.
--- kernel/locking/qspinlock.c | 3 ++- kernel/locking/qspinlock_stat.h | 21 +++++++++++++++------ 2 files changed, 17 insertions(+), 7 deletions(-)
kernel/locking/qspinlock.c +2 -1
@@ -422,6 +422,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)* simple enough. */ if (unlikely (idx >=MAX_NODES )) { +qstat_inc (qstat_lock_no_node, true);while (!queued_spin_trylock (lock))cpu_relax (); goto release;
@@ -432,7 +433,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)/* * Keep counts of non-zero index values: */ -qstat_inc (qstat_lock_idx1 + idx -1 , idx); +qstat_inc (qstat_lock_use_node2 + idx -1 , idx);/* * Ensure that we increment the head node->count before initialising
kernel/locking/qspinlock_stat.h +15 -6
@@ -30,6 +30,13 @@* pv_wait_node - # of vCPU wait's at a non-head queue node * lock_pending - # of locking operations via pending code * lock_slowpath - # of locking operations via MCS lock queue +* lock_use_node2 - # of locking operations that use 2nd percpu node +* lock_use_node3 - # of locking operations that use 3rd percpu node +* lock_use_node4 - # of locking operations that use 4th percpu node +* lock_no_node - # of locking operations without using percpu node +* +* Subtracting lock_use_node[234] from lock_slowpath will give you +* lock_use_node1. * * Writing to the "reset_counters" file will reset all the above counter * values.
@@ -55,9 +62,10 @@ enum qlock_stats { qstat_pv_wait_node, qstat_lock_pending, qstat_lock_slowpath, - qstat_lock_idx1, - qstat_lock_idx2, - qstat_lock_idx3, + qstat_lock_use_node2, + qstat_lock_use_node3, + qstat_lock_use_node4, + qstat_lock_no_node, qstat_num,/* Total number of statistical counters */ qstat_reset_cnts = qstat_num, };
@@ -85,9 +93,10 @@ enum qlock_stats { [qstat_pv_wait_node] = "pv_wait_node", [qstat_lock_pending] = "lock_pending", [qstat_lock_slowpath] = "lock_slowpath", - [qstat_lock_idx1] = "lock_index1", - [qstat_lock_idx2] = "lock_index2", - [qstat_lock_idx3] = "lock_index3", + [qstat_lock_use_node2] = "lock_use_node2", + [qstat_lock_use_node3] = "lock_use_node3", + [qstat_lock_use_node4] = "lock_use_node4", + [qstat_lock_no_node] = "lock_no_node", [qstat_reset_cnts] = "reset_counters", };
Signature · 1 line
1.8.3.1
tip-bot for Waiman Long
merge bot[tip:locking/core] locking/qspinlock_stat: Track the no MCS node available case
locking/qspinlock_stat: Track the no MCS node available case
Commit-ID: 412f34a82ccf7dd52f6b197f6450a33f03342523 Gitweb: https://git.kernel.org/tip/412f34a82ccf7dd52f6b197f6450a33f03342523 Author: Waiman Long <[email protected]> AuthorDate: Tue, 29 Jan 2019 22:53:46 +0100 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 4 Feb 2019 09:03:30 +0100
locking/qspinlock_stat: Track the no MCS node available case
Track the number of slowpath locking operations that are being done without any MCS node available as well renaming lock_index[123] to make them more descriptive.
Using these stat counters is one way to find out if a code path is being exercised.
--- kernel/locking/qspinlock.c | 3 ++- kernel/locking/qspinlock_stat.h | 21 +++++++++++++++------ 2 files changed, 17 insertions(+), 7 deletions(-)
kernel/locking/qspinlock.c +2 -1
@@ -422,6 +422,7 @@ pv_queue:* simple enough. */ if (unlikely (idx >=MAX_NODES )) { +qstat_inc (qstat_lock_no_node, true);while (!queued_spin_trylock (lock))cpu_relax (); goto release;
@@ -432,7 +433,7 @@ pv_queue:/* * Keep counts of non-zero index values: */ -qstat_inc (qstat_lock_idx1 + idx -1 , idx); +qstat_inc (qstat_lock_use_node2 + idx -1 , idx);/* * Ensure that we increment the head node->count before initialising
kernel/locking/qspinlock_stat.h +15 -6
@@ -30,6 +30,13 @@* pv_wait_node - # of vCPU wait's at a non-head queue node * lock_pending - # of locking operations via pending code * lock_slowpath - # of locking operations via MCS lock queue +* lock_use_node2 - # of locking operations that use 2nd per-CPU node +* lock_use_node3 - # of locking operations that use 3rd per-CPU node +* lock_use_node4 - # of locking operations that use 4th per-CPU node +* lock_no_node - # of locking operations without using per-CPU node +* +* Subtracting lock_use_node[234] from lock_slowpath will give you +* lock_use_node1. * * Writing to the "reset_counters" file will reset all the above counter * values.
@@ -55,9 +62,10 @@ enum qlock_stats { qstat_pv_wait_node, qstat_lock_pending, qstat_lock_slowpath, - qstat_lock_idx1, - qstat_lock_idx2, - qstat_lock_idx3, + qstat_lock_use_node2, + qstat_lock_use_node3, + qstat_lock_use_node4, + qstat_lock_no_node, qstat_num,/* Total number of statistical counters */ qstat_reset_cnts = qstat_num, };
@@ -85,9 +93,10 @@ static const char * const qstat_names[qstat_num + 1] = { [qstat_pv_wait_node] = "pv_wait_node", [qstat_lock_pending] = "lock_pending", [qstat_lock_slowpath] = "lock_slowpath", - [qstat_lock_idx1] = "lock_index1", - [qstat_lock_idx2] = "lock_index2", - [qstat_lock_idx3] = "lock_index3", + [qstat_lock_use_node2] = "lock_use_node2", + [qstat_lock_use_node3] = "lock_use_node3", + [qstat_lock_use_node4] = "lock_use_node4", + [qstat_lock_no_node] = "lock_no_node", [qstat_reset_cnts] = "reset_counters", };
Waiman Long
reviewerPATCH v3 3/4 locking/qspinlock_stat: Introduce a generic lockevent counting APIs
In reply to Waiman LongThe percpu event counts used by qspinlock code can be useful for other locking code as well. So a new set of lockevent_* counting APIs is introduced with the lock event names extracted out into the new lock_events_list.h header file for easier addition in the future.
The existing qstat_inc() calls are replaced by either lockevent_inc() or lockevent_cond_inc() calls.
The qstat_hop() call is renamed to lockevent_pv_hop(). The "reset_counters" debugfs file is also renamed to ".reset_counts".
--- kernel/locking/lock_events.h | 46 ++++++++++ kernel/locking/lock_events_list.h | 49 +++++++++++ kernel/locking/qspinlock.c | 8 +- kernel/locking/qspinlock_paravirt.h | 19 +++-- kernel/locking/qspinlock_stat.h | 163 ++++++++++++++---------------------- 5 files changed, 171 insertions(+), 114 deletions(-) create mode 100644 kernel/locking/lock_events.h create mode 100644 kernel/locking/lock_events_list.h
kernel/locking/lock_events.h new file +46 -0
@@ -0,0 +1,46 @@ +/* +* This program is free software; you can redistribute it and/or modify +* it under the terms of the GNU General Public License as published by +* the Free Software Foundation; either version 2 of the License, or +* (at your option) any later version. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* Authors: Waiman Long <[email protected]> +*/ + +enum lock_events { + +#include "lock_events_list.h" + + lockevent_num,/* Total number of lock event counts */ + LOCKEVENT_reset_cnts = lockevent_num, +}; + +#ifdef CONFIG_QUEUED_LOCK_STAT +/* +* Per-cpu counters +*/ +DECLARE_PER_CPU(unsigned long, lockevents[lockevent_num]); + +/* +* Increment the PV qspinlock statistical counters +*/ +static inline void __lockevent_inc (enum lock_events event,bool cond) +{ +if (cond) +this_cpu_inc (lockevents[event]); +} + +#define lockevent_inc (ev) __lockevent_inc(LOCKEVENT_ ##ev, true) +#define lockevent_cond_inc (ev, c) __lockevent_inc(LOCKEVENT_ ##ev, c) + +#else /* CONFIG_QUEUED_LOCK_STAT */ + +#define lockevent_inc (ev) +#define lockevent_cond_inc (ev, c) + +#endif /* CONFIG_QUEUED_LOCK_STAT */
kernel/locking/lock_events_list.h new file +49 -0
49 lines not on this page · raw message
kernel/locking/qspinlock.c +4 -4
@@ -398,7 +398,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)* 0,1,0 -> 0,0,1 */ clear_pending_set_locked (lock); -qstat_inc (qstat_lock_pending, true); +lockevent_inc (lock_pending);return ;/*
@@ -406,7 +406,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)* queuing. */ queue: -qstat_inc (qstat_lock_slowpath, true); +lockevent_inc (lock_slowpath); pv_queue: node =this_cpu_ptr (&qnodes[0 ].mcs); idx = node->count++;
@@ -422,7 +422,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)* simple enough. */ if (unlikely (idx >=MAX_NODES )) { -qstat_inc (qstat_lock_no_node, true); +lockevent_inc (lock_no_node);while (!queued_spin_trylock (lock))cpu_relax (); goto release;
@@ -433,7 +433,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)/* * Keep counts of non-zero index values: */ -qstat_inc (qstat_lock_use_node2 + idx -1 , idx); +lockevent_cond_inc (lock_use_node2 + idx -1 , idx);/* * Ensure that we increment the head node->count before initialising
kernel/locking/qspinlock_paravirt.h +10 -9
@@ -89,7 +89,7 @@ static inline bool pv_hybrid_queued_unfair_trylock(struct qspinlock *lock)if (!(val & _Q_LOCKED_PENDING_MASK) && (cmpxchg_acquire (&lock->locked,0 , _Q_LOCKED_VAL) ==0 )) { -qstat_inc (qstat_pv_lock_stealing, true); +lockevent_inc (pv_lock_stealing);return true; }if (!(val & _Q_TAIL_MASK) || (val & _Q_PENDING_MASK))
@@ -219,7 +219,7 @@ static struct qspinlock **pv_hash(struct qspinlock *lock, struct pv_node *node) hopcnt++;if (!cmpxchg (&he->lock,NULL , lock)) {WRITE_ONCE (he->node, node); -qstat_hop (hopcnt); +lockevent_pv_hop (hopcnt);return &he->lock; } }
@@ -320,8 +320,8 @@ static void pv_wait_node(struct mcs_spinlock *node, struct mcs_spinlock *prev)smp_store_mb (pn->state, vcpu_halted);if (!READ_ONCE (node->locked)) { -qstat_inc (qstat_pv_wait_node, true); -qstat_inc (qstat_pv_wait_early, wait_early); +lockevent_inc (pv_wait_node); +lockevent_cond_inc (pv_wait_early, wait_early);pv_wait (&pn->state, vcpu_halted); }
@@ -339,7 +339,8 @@ static void pv_wait_node(struct mcs_spinlock *node, struct mcs_spinlock *prev)* So it is better to spin for a while in the hope that the * MCS lock will be released soon. */ -qstat_inc (qstat_pv_spurious_wakeup, !READ_ONCE (node->locked)); +lockevent_cond_inc (pv_spurious_wakeup, + !READ_ONCE (node->locked)); }/*
@@ -416,7 +417,7 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)/* * Tracking # of slowpath locking operations */ -qstat_inc (qstat_lock_slowpath, true); +lockevent_inc (lock_slowpath);for (;; waitcnt++) {/*
@@ -464,8 +465,8 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node) } }WRITE_ONCE (pn->state, vcpu_hashed); -qstat_inc (qstat_pv_wait_head, true); -qstat_inc (qstat_pv_wait_again, waitcnt); +lockevent_inc (pv_wait_head); +lockevent_cond_inc (pv_wait_again, waitcnt);pv_wait (&lock->locked, _Q_SLOW_VAL);/*
@@ -528,7 +529,7 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)* vCPU is harmless other than the additional latency in completing * the unlock. */ -qstat_inc (qstat_pv_kick_unlock, true); +lockevent_inc (pv_kick_unlock);pv_kick (node->cpu); }
kernel/locking/qspinlock_stat.h +62 -101
301 lines not on this page · raw message
Signature · 1 line
1.8.3.1
Waiman Long
reviewerPATCH v3 4/4 locking/lock_events: Make lock_events available for all archs & other locks
In reply to Waiman LongThe QUEUED_LOCK_STAT option to report queued spinlocks event counts was previously allowed only on x86 architecture. To make the locking event counting code more useful, it is now renamed to a more generic LOCK_EVENT_COUNTS config option. This new option will be available to all the architectures that use qspinlock at the moment.
Other locking code can now start to use the generic locking event counting code by including lock_events.h and put the new locking event names into the lock_events_list.h header file.
My experience with lock event counting is that it gives valuable insight on how the locking code works and what can be done to make it better. I would like to extend this benefit to other locking code like mutex and rwsem in the near future.
The PV qspinlock specific code will stay in qspinlock_stat.h. The locking event counters will now reside in the <debugfs>/lock_event_counts directory.
--- arch/Kconfig | 10 +++ arch/x86/Kconfig | 8 --- kernel/locking/Makefile | 1 + kernel/locking/lock_events.c | 152 ++++++++++++++++++++++++++++++++++++++++ kernel/locking/lock_events.h | 6 +- kernel/locking/qspinlock_stat.h | 141 ++++--------------------------------- 6 files changed, 178 insertions(+), 140 deletions(-) create mode 100644 kernel/locking/lock_events.c
arch/Kconfig +10 -0
@@ -885,6 +885,16 @@ config HAVE_ARCH_PREL32_RELOCATIONS architectures, and don't require runtime relocation on relocatable kernels. +config LOCK_EVENT_COUNTS + bool "Locking event counts collection" + depends on DEBUG_FS + depends on QUEUED_SPINLOCKS + ---help--- + Enable light-weight counting of various locking related events + in the system with minimal performance impact. This reduces + the chance of application behavior change because of timing + differences. The counts are reported via debugfs. + source "kernel/gcov/Kconfig" source "scripts/gcc-plugins/Kconfig"
arch/x86/Kconfig +0 -8
@@ -784,14 +784,6 @@ config PARAVIRT_SPINLOCKS If you are unsure how to answer this question, answer Y. -config QUEUED_LOCK_STAT - bool "Paravirt queued spinlock statistics" - depends on PARAVIRT_SPINLOCKS && DEBUG_FS - ---help--- - Enable the collection of statistical data on the slowpath - behavior of paravirtualized queued spinlocks and report - them on debugfs. - source "arch/x86/xen/Kconfig" config KVM_GUEST
kernel/locking/Makefile +1 -0
@@ -30,3 +30,4 @@ obj-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem-xadd.o obj-$(CONFIG_QUEUED_RWLOCKS) += qrwlock.o obj-$(CONFIG_LOCK_TORTURE_TEST) += locktorture.o obj-$(CONFIG_WW_MUTEX_SELFTEST) += test-ww_mutex.o +obj-$(CONFIG_LOCK_EVENT_COUNTS) += lock_events.o
kernel/locking/lock_events.c new file +152 -0
152 lines not on this page · raw message
kernel/locking/lock_events.h +3 -3
@@ -20,7 +20,7 @@ enum lock_events { LOCKEVENT_reset_cnts = lockevent_num, }; -#ifdef CONFIG_QUEUED_LOCK_STAT +#ifdef CONFIG_LOCK_EVENT_COUNTS /* * Per-cpu counters */
@@ -38,9 +38,9 @@ static inline void __lockevent_inc(enum lock_events event, bool cond)#define lockevent_inc (ev) __lockevent_inc(LOCKEVENT_ ##ev, true)#define lockevent_cond_inc (ev, c) __lockevent_inc(LOCKEVENT_ ##ev, c) -#else /* CONFIG_QUEUED_LOCK_STAT */ +#else /* CONFIG_LOCK_EVENT_COUNTS */ #define lockevent_inc (ev)#define lockevent_cond_inc (ev, c) -#endif /* CONFIG_QUEUED_LOCK_STAT */ +#endif /* CONFIG_LOCK_EVENT_COUNTS */
kernel/locking/qspinlock_stat.h +12 -129
182 lines not on this page · raw message
Signature · 1 line
1.8.3.1
Peter Zijlstra
maintainerQuoted 3 lines
Waiman Long (4):
locking/qspinlock: Handle > 4 slowpath nesting levels locking/qspinlock_stat: Track the no MCS node available case
I've taken these two,
Quoted 3 lines
locking/qspinlock_stat: Introduce a generic lockevent counting APIs locking/lock_events: Make
lock_eventsavailable for all archs & other
locks
while no real objection to these; I feel we should wait until there are in fact more users of this.
Waiman Long
reviewerQuoted 10 lines · Peter Zijlstra
Quoted 3 lines
Waiman Long (4):
locking/qspinlock: Handle > 4 slowpath nesting levels locking/qspinlock_stat: Track the no MCS node available caseI've taken these two,
Quoted 3 lines
locking/qspinlock_stat: Introduce a generic lockevent counting APIs locking/lock_events: Make
lock_eventsavailable for all archs & other
lockswhile no real objection to these; I feel we should wait until there are in fact more users of this.
I am actually working on a rwsem patch which I plan to use the event counting for my testing purpose. I will include this two patches in my patch series.
Thanks,
Longman