locking/qspinlock: Add stat tracking for pending vs slowpath
Waiman Long
reviewerPATCH 1/2 locking/qspinlock: Add stat tracking for pending vs slowpath
Currently, the qspinlock_stat code tracks only statistical counts in the PV qspinlock code. However, it may also be useful to track the number of locking operations done via the pending code vs. the MCS lock queue slowpath for the non-PV case.
The qspinlock stat code is modified to do that. The stat counter pv_lock_slowpath is renamed to lock_slowpath so that it can be used by both the PV and non-PV cases.
--- kernel/locking/qspinlock.c | 14 +++++++++++--- kernel/locking/qspinlock_paravirt.h | 7 +------ kernel/locking/qspinlock_stat.h | 9 ++++++--- 3 files changed, 18 insertions(+), 12 deletions(-)
kernel/locking/qspinlock.c +11 -3
@@ -12,11 +12,11 @@* GNU General Public License for more details. * * (C) Copyright 2013-2015 Hewlett-Packard Development Company, L.P. -* (C) Copyright 2013-2014 Red Hat, Inc. +* (C) Copyright 2013-2014,2018 Red Hat, Inc. * (C) Copyright 2015 Intel Corp. * (C) Copyright 2015 Hewlett-Packard Enterprise Development LP * -* Authors: Waiman Long <[email protected]> +* Authors: Waiman Long <[email protected]> * Peter Zijlstra <[email protected]> */
@@ -33,6 +33,11 @@#include <asm/qspinlock.h> /* +* Include queued spinlock statistics code +*/ +#include "qspinlock_stat.h" + +/* * The basic principle of a queue-based spinlock can best be understood * by studying a classic queue-based spinlock implementation called the * MCS lock. The paper below provides a good description for this kind
@@ -300,7 +305,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)BUILD_BUG_ON (CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));if (pv_enabled ()) - goto queue; + goto pv_queue;if (virt_spin_lock (lock))return ;
@@ -342,6 +347,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) val = old; } +qstat_inc (qstat_lock_pending, true);/* * we won the trylock
@@ -374,6 +380,8 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)* queuing. */ queue: +qstat_inc (qstat_lock_slowpath, true); +pv_queue: node =this_cpu_ptr (&mcs_nodes[0 ]); idx = node->count++; tail =encode_tail (smp_processor_id (), idx);
kernel/locking/qspinlock_paravirt.h +1 -6
@@ -56,11 +56,6 @@ struct pv_node { };/* -* Include queued spinlock statistics code -*/ -#include "qspinlock_stat.h" - -/* * Hybrid PV queued/unfair lock * * By replacing the regular queued_spin_trylock() with the function below,
@@ -443,7 +438,7 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)/* * Tracking # of slowpath locking operations */ -qstat_inc (qstat_pv_lock_slowpath, true); +qstat_inc (qstat_lock_slowpath, true);for (;; waitcnt++) {/*
kernel/locking/qspinlock_stat.h +6 -3
@@ -22,13 +22,14 @@* pv_kick_wake - # of vCPU kicks used for computing pv_latency_wake * pv_latency_kick - average latency (ns) of vCPU kick operation * pv_latency_wake - average latency (ns) from vCPU kick to wakeup -* pv_lock_slowpath - # of locking operations via the slowpath * pv_lock_stealing - # of lock stealing operations * pv_spurious_wakeup - # of spurious wakeups in non-head vCPUs * pv_wait_again - # of wait's after a queue head vCPU kick * pv_wait_early - # of early vCPU wait's * pv_wait_head - # of vCPU wait's at the queue head * 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 * * Writing to the "reset_counters" file will reset all the above counter * values.
@@ -46,13 +47,14 @@ enum qlock_stats { qstat_pv_kick_wake, qstat_pv_latency_kick, qstat_pv_latency_wake, - qstat_pv_lock_slowpath, qstat_pv_lock_stealing, qstat_pv_spurious_wakeup, qstat_pv_wait_again, qstat_pv_wait_early, qstat_pv_wait_head, qstat_pv_wait_node, + qstat_lock_pending, + qstat_lock_slowpath, qstat_num,/* Total number of statistical counters */ qstat_reset_cnts = qstat_num, };
@@ -73,12 +75,13 @@ enum qlock_stats { [qstat_pv_spurious_wakeup] = "pv_spurious_wakeup", [qstat_pv_latency_kick] = "pv_latency_kick", [qstat_pv_latency_wake] = "pv_latency_wake", - [qstat_pv_lock_slowpath] = "pv_lock_slowpath", [qstat_pv_lock_stealing] = "pv_lock_stealing", [qstat_pv_wait_again] = "pv_wait_again", [qstat_pv_wait_early] = "pv_wait_early", [qstat_pv_wait_head] = "pv_wait_head", [qstat_pv_wait_node] = "pv_wait_node", + [qstat_lock_pending] = "lock_pending", + [qstat_lock_slowpath] = "lock_slowpath", [qstat_reset_cnts] = "reset_counters", };
Signature · 1 line
1.8.3.1
Waiman Long
reviewerPATCH 2/2 locking/qspinlock: Limit # of spins in _Q_PENDING_VAL wait loop
A locker in the pending code path is doing an infinite number of spins when waiting for the _Q_PENDING_VAL to _Q_LOCK_VAL transition. There is a concern that lock starvation can happen concurrent lockers are able to take the lock in the cmpxchg loop without queuing and pass it around amongst themselves.
To ensure forward progress while still taking advantage of using the pending code path without queuing, the code is now modified to do a limited number of spins before aborting the effort and going to queue itself.
Ideally, the spinning times should be at least a few times the typical cacheline load time from memory which I think can be down to 100ns or so for each cacheline load with the newest systems or up to several hundreds ns for older systems.
--- kernel/locking/qspinlock.c | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-)
kernel/locking/qspinlock.c +17 -2
@@ -82,6 +82,15 @@#endif /* +* The pending bit spinning loop count. +* This parameter can be overridden by another architecture specific +* constant. Default is 512. +*/ +#ifndef _Q_PENDING_LOOP +#define _Q_PENDING_LOOP (1 << 9) +#endif + +/* * Per-CPU queue node structures; we can never have more than 4 nested * contexts: task, softirq, hardirq, nmi. *
@@ -311,13 +320,19 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)return ;/* -* wait for in-progress pending->locked hand-overs +* wait for in-progress pending->locked hand-overs with a +* limited number of spins. * * 0,1,0 -> 0,0,1 */ if (val == _Q_PENDING_VAL) { -while ((val =atomic_read (&lock->val)) == _Q_PENDING_VAL) +int cnt = _Q_PENDING_LOOP; + +while ((val =atomic_read (&lock->val)) == _Q_PENDING_VAL) { +if (!--cnt) + goto queue;cpu_relax (); + } }/*
Signature · 1 line
1.8.3.1
Re: [PATCH 2/2] locking/qspinlock: Limit # of spins in _Q_PENDING_VAL wait loop
Hi Waiman,
Quoted 26 lines · Waiman Long
A locker in the pending code path is doing an infinite number of spins when waiting for the
_Q_PENDING_VALto_Q_LOCK_VALtransition. There is a concern that lock starvation can happen concurrent lockers are able to take the lock in the cmpxchg loop without queuing and pass it around amongst themselves.To ensure forward progress while still taking advantage of using the pending code path without queuing, the code is now modified to do a limited number of spins before aborting the effort and going to queue itself.
Ideally, the spinning times should be at least a few times the typical cacheline load time from memory which I think can be down to 100ns or so for each cacheline load with the newest systems or up to several hundreds ns for older systems.
Signed-off-by Waiman Long <[email protected]>--- kernel/locking/qspinlock.c | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-)kernel/locking/qspinlock.c +0
-0
kernel/locking/qspinlock.c line 91
Quoted 10 lines
kernel/locking/qspinlock.c +7
-0@@ -82,6 +82,15 @@#endif /* +* The pending bit spinning loop count. +* This parameter can be overridden by another architecture specific +* constant. Default is 512. +*/ +#ifndef _Q_PENDING_LOOP +#define _Q_PENDING_LOOP (1 << 9) +#endif
I really dislike heuristics like this because there's never a good number to choose and it almost certainly varies between systems and workloads rather than just by architecture. However, I've also not managed to come up with something better.
If I rewrite your code slightly to look like:
if (val == _Q_PENDING_VAL) {
int cnt = _Q_PENDING_LOOP;
val = atomic_cond_read_relaxed(&lock->val, (VAL != _Q_PENDING_VAL) || !cnt--);
}then architectures that implement atomic_cond_read_relaxed as something more interesting than a spinning loop will probably be happy with _Q_PENDING_LOOP == 1;
I'll post a v2 tomorrow with that change, and I'll add your stat patch to the series too so that everything is kept together.
Will
Waiman Long
reviewerRe: [PATCH 2/2] locking/qspinlock: Limit # of spins in _Q_PENDING_VAL wait loop
Quoted 31 lines · Will Deacon
Hi Waiman,
Quoted 28 lines · Waiman Long
A locker in the pending code path is doing an infinite number of spins when waiting for the
_Q_PENDING_VALto_Q_LOCK_VALtransition. There is a concern that lock starvation can happen concurrent lockers are able to take the lock in the cmpxchg loop without queuing and pass it around amongst themselves.To ensure forward progress while still taking advantage of using the pending code path without queuing, the code is now modified to do a limited number of spins before aborting the effort and going to queue itself.
Ideally, the spinning times should be at least a few times the typical cacheline load time from memory which I think can be down to 100ns or so for each cacheline load with the newest systems or up to several hundreds ns for older systems.
Signed-off-by Waiman Long <[email protected]>--- kernel/locking/qspinlock.c | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-)kernel/locking/qspinlock.c +0
-0@@ -82,6 +82,15 @@#endif
Quoted 12 lines
kernel/locking/qspinlock.c line 91
Quoted 8 lines
kernel/locking/qspinlock.c +7
-0/* +* The pending bit spinning loop count. +* This parameter can be overridden by another architecture specific +* constant. Default is 512. +*/ +#ifndef _Q_PENDING_LOOP +#define _Q_PENDING_LOOP (1 << 9) +#endif I really dislike heuristics like this because there's never a good number to choose and it almost certainly varies between systems and workloads rather than just by architecture. However, I've also not managed to come up with something better.
I share your concern about heuristic like this, but I can't think of another easy way out.
Quoted 10 lines
If I rewrite your code slightly to look like:
if (val == _Q_PENDING_VAL) { int cnt = _Q_PENDING_LOOP; val = atomic_cond_read_relaxed(&lock->val, (VAL != _Q_PENDING_VAL) || !cnt--); }then architectures that implement
atomic_cond_read_relaxedas something more interesting than a spinning loop will probably be happy with_Q_PENDING_LOOP== 1;
Right. That is why I state that _Q_PENDING_LOOP is an architecture specific constant.
Cheers,
Longman
Re: [PATCH 2/2] locking/qspinlock: Limit # of spins in _Q_PENDING_VAL wait loop
In reply to Waiman LongHi Waiman,
Quoted 10 lines · Waiman Long
kernel/locking/qspinlock.c +2
-1@@ -311,13 +320,19 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)return ;/* -* wait for in-progress pending->locked hand-overs +* wait for in-progress pending->locked hand-overs with a +* limited number of spins. * * 0,1,0 -> 0,0,1 */
kernel/locking/qspinlock.c void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) · line 336
Quoted 10 lines
kernel/locking/qspinlock.c +6
-1if (val == _Q_PENDING_VAL) { -while ((val =atomic_read (&lock->val)) == _Q_PENDING_VAL) +int cnt = _Q_PENDING_LOOP; + +while ((val =atomic_read (&lock->val)) == _Q_PENDING_VAL) { +if (!--cnt) + goto queue;cpu_relax (); + } }
In my model, the pathological case is not this loop but the following one (trylock || pending):
P0: P1:queued_spin_lock() fails queued_spin_lock() succeedsqueued_spin_lock_slowpath()
val == _Q_LOCKED_VAL
new = _Q_LOCKED_VAL |
_Q_PENDING_VAL
queued_spin_unlock()
lock->val == 0
cmpxchg(&lock->val, val, new)
fails
val = old (0)
repeat for (;;) loop:
new = _Q_LOCKED_VAL
queued_spin_lock() succeeds
lock->val == _Q_LOCKED_VAL
cmpxchg(&lock->val, val, new)
fails
val = old (_Q_LOCKED_VAL)
repeat for (;;) loop:
... and we are back to the P0 state above when it first entered the loop, hence no progress. P1 never enters slowpath.
I think the pending bounded loop in your patch is needed for a three CPU scenario where two of them can hand over _Q_PENDING_VAL while the third doesn't make progress. I tried modeling 3 CPUs to see but the tool still hits the for (;;) loop case rather than pending wait loop. Maybe a combination of Will's changes to the (trylock || pending) loop with your bounded pending hand-over?
Signature · 1 line
Catalin
Waiman Long
reviewerRe: [PATCH 2/2] locking/qspinlock: Limit # of spins in _Q_PENDING_VAL wait loop
Quoted 46 lines · Catalin Marinas
Hi Waiman,
Quoted 10 lines · Waiman Long
kernel/locking/qspinlock.c +2
-1@@ -311,13 +320,19 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)return ;/* -* wait for in-progress pending->locked hand-overs +* wait for in-progress pending->locked hand-overs with a +* limited number of spins. * * 0,1,0 -> 0,0,1 */ kernel/locking/qspinlock.c void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) · line 336
Quoted 10 lines
kernel/locking/qspinlock.c +6
-1if (val == _Q_PENDING_VAL) { -while ((val =atomic_read (&lock->val)) == _Q_PENDING_VAL) +int cnt = _Q_PENDING_LOOP; + +while ((val =atomic_read (&lock->val)) == _Q_PENDING_VAL) { +if (!--cnt) + goto queue;cpu_relax (); + } }In my model, the pathological case is not this loop but the following one (trylock || pending):
P0: P1:
queued_spin_lock()failsqueued_spin_lock()succeedsqueued_spin_lock_slowpath()
val ==_Q_LOCKED_VAL
new =_Q_LOCKED_VAL|
_Q_PENDING_VAL
queued_spin_unlock()
lock->val== 0
cmpxchg(&lock->val, val, new)
fails
val = old (0)
repeat for (;;) loop:
new =_Q_LOCKED_VAL
queued_spin_lock()succeeds
lock->val==_Q_LOCKED_VAL
cmpxchg(&lock->val, val, new)
fails
val = old (_Q_LOCKED_VAL)
repeat for (;;) loop:
Quoted 2 lines
... and we are back to the P0 state above when it first entered the loop, hence no progress. P1 never enters slowpath.
I don't see any problem in removing this second loop. Thanks for running tool to check for problem.
-Longman