locking/pvqspinlock: Hybrid PV queued/unfair locks
Waiman Long
reviewerPATCH 1/1 locking/pvqspinlock: Hybrid PV queued/unfair locks
Currently, all the lock waiters entering the slowpath will do one lock stealing attempt to acquire the lock. That helps performance, especially in VMs with over-committed vCPUs. However, the current pvqspinlocks still don't perform as good as unfair locks in many cases. On the other hands, unfair locks do have the problem of lock starvation that pvqspinlocks don't have.
This patch combines the best attributes of an unfair lock and a pvqspinlock into a hybrid lock with 2 modes - queued mode & unfair mode. A lock waiter goes into the unfair mode when there are waiters in the wait queue but the pending bit isn't set. Otherwise, it will go into the queued mode waiting in the queue for its turn.
On a 2-socket 36-core E5-2699 v3 system (HT off), a kernel build (make -j<n>) was done in a VM with unpinned vCPUs 3 times with the best time selected and <n> is the number of vCPUs available. The build times of the original pvqspinlock, hybrid pvqspinlock and unfair lock with various number of vCPUs are as follows:
vCPUs pvqlock hybrid pvqlock unfair lock
----- ------- -------------- -----------
30 342.1s 329.1s 329.1s
36 314.1s 305.3s 307.3s
45 345.0s 302.1s 306.6s
54 365.4s 308.6s 307.8s
72 358.9s 293.6s 303.9s
108 343.0s 285.9s 304.2sThe hybrid pvqspinlock performs better or comparable to the unfair lock.
By turning on QUEUED_LOCK_STAT, the table below showed the number of lock acquisitions in unfair mode and queue mode after a kernel build with various number of vCPUs.
vCPUs queued mode unfair mode
----- ----------- -----------
30 9,130,518 294,954
36 10,856,614 386,809
45 8,467,264 11,475,373
54 6,409,987 19,670,855
72 4,782,063 25,712,180It can be seen that as the VM became more and more over-committed, the ratio of locks acquired in unfair mode increases. This is all done automatically to get the best overall performance as possible.
The table below shows the kernel build times on a smaller 2-socket 16-core 32-thread E5-2620 v4 system.
vCPUs pvqlock hybrid pvqlock unfair lock
----- ------- -------------- -----------
16 436.8s 433.4s 435.6s
36 366.2s 364.8s 364.5s
48 423.6s 376.3s 370.2s
64 433.1s 376.6s 376.8sAgain, the performance of the hybrid pvqspinlock was comparable to that of the unfair lock.
--- kernel/locking/qspinlock_paravirt.h | 28 +++++++++++++++++++++------- 1 file changed, 21 insertions(+), 7 deletions(-)
kernel/locking/qspinlock_paravirt.h +21 -7
@@ -60,21 +60,35 @@ struct pv_node {#include "qspinlock_stat.h" /* +* Hybrid PV queued/unfair lock +* * By replacing the regular queued_spin_trylock() with the function below, * it will be called once when a lock waiter enter the PV slowpath before -* being queued. By allowing one lock stealing attempt here when the pending -* bit is off, it helps to reduce the performance impact of lock waiter -* preemption without the drawback of lock starvation. +* being queued. By allowing lock stealing attempts here when there are +* waiters but the pending bit is off, it helps to reduce the performance +* impact of lock waiter preemption without the drawback of lock starvation. */ #define queued_spin_trylock (l) pv_queued_spin_steal_lock(l)static inline bool pv_queued_spin_steal_lock (struct qspinlock *lock) {struct __qspinlock *l = (void *)lock; -if (!(atomic_read (&lock->val) & _Q_LOCKED_PENDING_MASK) && - (cmpxchg_acquire (&l->locked,0 , _Q_LOCKED_VAL) ==0 )) { -qstat_inc (qstat_pv_lock_stealing, true); -return true; +/* +* Stay in unfair lock mode as long as waiters are present but +* the pending bit isn't set. +*/ +for (;;) { +int val =atomic_read (&lock->val); + +if (!(val & _Q_LOCKED_PENDING_MASK) && + (cmpxchg_acquire (&l->locked,0 , _Q_LOCKED_VAL) ==0 )) { +qstat_inc (qstat_pv_lock_stealing, true); +return true; + } +if (!(val & _Q_TAIL_MASK) || (val & _Q_PENDING_MASK)) +break ; + +cpu_relax (); }return false;
Signature · 1 line
1.8.3.1
Quoted 57 lines · Waiman Long
Currently, all the lock waiters entering the slowpath will do one lock stealing attempt to acquire the lock. That helps performance, especially in VMs with over-committed vCPUs. However, the current pvqspinlocks still don't perform as good as unfair locks in many cases. On the other hands, unfair locks do have the problem of lock starvation that pvqspinlocks don't have.
This patch combines the best attributes of an unfair lock and a pvqspinlock into a hybrid lock with 2 modes - queued mode & unfair mode. A lock waiter goes into the unfair mode when there are waiters in the wait queue but the pending bit isn't set. Otherwise, it will go into the queued mode waiting in the queue for its turn.
On a 2-socket 36-core E5-2699 v3 system (HT off), a kernel build (make -j<n>) was done in a VM with unpinned vCPUs 3 times with the best time selected and <n> is the number of vCPUs available. The build times of the original pvqspinlock, hybrid pvqspinlock and unfair lock with various number of vCPUs are as follows:
vCPUs pvqlock hybrid pvqlock unfair lock ----- ------- -------------- ----------- 30 342.1s 329.1s 329.1s 36 314.1s 305.3s 307.3s 45 345.0s 302.1s 306.6s 54 365.4s 308.6s 307.8s 72 358.9s 293.6s 303.9s 108 343.0s 285.9s 304.2sThe hybrid pvqspinlock performs better or comparable to the unfair lock.
By turning on
QUEUED_LOCK_STAT, the table below showed the number of lock acquisitions in unfair mode and queue mode after a kernel build with various number of vCPUs.vCPUs queued mode unfair mode ----- ----------- ----------- 30 9,130,518 294,954 36 10,856,614 386,809 45 8,467,264 11,475,373 54 6,409,987 19,670,855 72 4,782,063 25,712,180It can be seen that as the VM became more and more over-committed, the ratio of locks acquired in unfair mode increases. This is all done automatically to get the best overall performance as possible.
The table below shows the kernel build times on a smaller 2-socket 16-core 32-thread E5-2620 v4 system.
vCPUs pvqlock hybrid pvqlock unfair lock ----- ------- -------------- ----------- 16 436.8s 433.4s 435.6s 36 366.2s 364.8s 364.5s 48 423.6s 376.3s 370.2s 64 433.1s 376.6s 376.8s
Quoted 4 lines
Again, the performance of the hybrid pvqspinlock was comparable to that of the unfair lock.
Signed-off-by Waiman Long <[email protected]>
Juergen
Quoted 103 lines · Waiman Long
Currently, all the lock waiters entering the slowpath will do one lock stealing attempt to acquire the lock. That helps performance, especially in VMs with over-committed vCPUs. However, the current pvqspinlocks still don't perform as good as unfair locks in many cases. On the other hands, unfair locks do have the problem of lock starvation that pvqspinlocks don't have.
This patch combines the best attributes of an unfair lock and a pvqspinlock into a hybrid lock with 2 modes - queued mode & unfair mode. A lock waiter goes into the unfair mode when there are waiters in the wait queue but the pending bit isn't set. Otherwise, it will go into the queued mode waiting in the queue for its turn.
On a 2-socket 36-core E5-2699 v3 system (HT off), a kernel build (make -j<n>) was done in a VM with unpinned vCPUs 3 times with the best time selected and <n> is the number of vCPUs available. The build times of the original pvqspinlock, hybrid pvqspinlock and unfair lock with various number of vCPUs are as follows:
vCPUs pvqlock hybrid pvqlock unfair lock ----- ------- -------------- ----------- 30 342.1s 329.1s 329.1s 36 314.1s 305.3s 307.3s 45 345.0s 302.1s 306.6s 54 365.4s 308.6s 307.8s 72 358.9s 293.6s 303.9s 108 343.0s 285.9s 304.2sThe hybrid pvqspinlock performs better or comparable to the unfair lock.
By turning on
QUEUED_LOCK_STAT, the table below showed the number of lock acquisitions in unfair mode and queue mode after a kernel build with various number of vCPUs.vCPUs queued mode unfair mode ----- ----------- ----------- 30 9,130,518 294,954 36 10,856,614 386,809 45 8,467,264 11,475,373 54 6,409,987 19,670,855 72 4,782,063 25,712,180It can be seen that as the VM became more and more over-committed, the ratio of locks acquired in unfair mode increases. This is all done automatically to get the best overall performance as possible.
The table below shows the kernel build times on a smaller 2-socket 16-core 32-thread E5-2620 v4 system.
vCPUs pvqlock hybrid pvqlock unfair lock ----- ------- -------------- ----------- 16 436.8s 433.4s 435.6s 36 366.2s 364.8s 364.5s 48 423.6s 376.3s 370.2s 64 433.1s 376.6s 376.8sAgain, the performance of the hybrid pvqspinlock was comparable to that of the unfair lock.
Signed-off-by Waiman Long <[email protected]>--- kernel/locking/qspinlock_paravirt.h | 28 +++++++++++++++++++++------- 1 file changed, 21 insertions(+), 7 deletions(-)kernel/locking/qspinlock_paravirt.h +14
-7@@ -60,21 +60,35 @@ struct pv_node {#include "qspinlock_stat.h" /* +* Hybrid PV queued/unfair lock +* * By replacing the regular queued_spin_trylock() with the function below, * it will be called once when a lock waiter enter the PV slowpath before -* being queued. By allowing one lock stealing attempt here when the pending -* bit is off, it helps to reduce the performance impact of lock waiter -* preemption without the drawback of lock starvation. +* being queued. By allowing lock stealing attempts here when there are +* waiters but the pending bit is off, it helps to reduce the performance +* impact of lock waiter preemption without the drawback of lock starvation. */ #define queued_spin_trylock (l) pv_queued_spin_steal_lock(l)static inline bool pv_queued_spin_steal_lock (struct qspinlock *lock) {struct __qspinlock *l = (void *)lock; -if (!(atomic_read (&lock->val) & _Q_LOCKED_PENDING_MASK) && - (cmpxchg_acquire (&l->locked,0 , _Q_LOCKED_VAL) ==0 )) { -qstat_inc (qstat_pv_lock_stealing, true); -return true; +/* +* Stay in unfair lock mode as long as waiters are present but +* the pending bit isn't set. +*/ +for (;;) { +int val =atomic_read (&lock->val); + +if (!(val & _Q_LOCKED_PENDING_MASK) && + (cmpxchg_acquire (&l->locked,0 , _Q_LOCKED_VAL) ==0 )) {
kernel/locking/qspinlock_paravirt.h struct pv_node { · line 94
Quoted 10 lines
kernel/locking/qspinlock_paravirt.h +7
-0+qstat_inc (qstat_pv_lock_stealing, true); +return true; + } +if (!(val & _Q_TAIL_MASK) || (val & _Q_PENDING_MASK)) +break ; + +cpu_relax (); }return false;
Awesome! Thanks Waiman.
Paolo
Peter Zijlstra
maintainerQuoted 57 lines · Waiman Long
Currently, all the lock waiters entering the slowpath will do one lock stealing attempt to acquire the lock. That helps performance, especially in VMs with over-committed vCPUs. However, the current pvqspinlocks still don't perform as good as unfair locks in many cases. On the other hands, unfair locks do have the problem of lock starvation that pvqspinlocks don't have.
This patch combines the best attributes of an unfair lock and a pvqspinlock into a hybrid lock with 2 modes - queued mode & unfair mode. A lock waiter goes into the unfair mode when there are waiters in the wait queue but the pending bit isn't set. Otherwise, it will go into the queued mode waiting in the queue for its turn.
On a 2-socket 36-core E5-2699 v3 system (HT off), a kernel build (make -j<n>) was done in a VM with unpinned vCPUs 3 times with the best time selected and <n> is the number of vCPUs available. The build times of the original pvqspinlock, hybrid pvqspinlock and unfair lock with various number of vCPUs are as follows:
vCPUs pvqlock hybrid pvqlock unfair lock ----- ------- -------------- ----------- 30 342.1s 329.1s 329.1s 36 314.1s 305.3s 307.3s 45 345.0s 302.1s 306.6s 54 365.4s 308.6s 307.8s 72 358.9s 293.6s 303.9s 108 343.0s 285.9s 304.2sThe hybrid pvqspinlock performs better or comparable to the unfair lock.
By turning on
QUEUED_LOCK_STAT, the table below showed the number of lock acquisitions in unfair mode and queue mode after a kernel build with various number of vCPUs.vCPUs queued mode unfair mode ----- ----------- ----------- 30 9,130,518 294,954 36 10,856,614 386,809 45 8,467,264 11,475,373 54 6,409,987 19,670,855 72 4,782,063 25,712,180It can be seen that as the VM became more and more over-committed, the ratio of locks acquired in unfair mode increases. This is all done automatically to get the best overall performance as possible.
The table below shows the kernel build times on a smaller 2-socket 16-core 32-thread E5-2620 v4 system.
vCPUs pvqlock hybrid pvqlock unfair lock ----- ------- -------------- ----------- 16 436.8s 433.4s 435.6s 36 366.2s 364.8s 364.5s 48 423.6s 376.3s 370.2s 64 433.1s 376.6s 376.8s
Quoted 2 lines
Again, the performance of the hybrid pvqspinlock was comparable to that of the unfair lock.
You forgot to test a starvation case. And you also forgot to describe how they cannot happen. I really cannot remember how all this is supposed to work.
Waiman Long
reviewerQuoted 58 lines · Peter Zijlstra
Quoted 57 lines · Waiman Long
Currently, all the lock waiters entering the slowpath will do one lock stealing attempt to acquire the lock. That helps performance, especially in VMs with over-committed vCPUs. However, the current pvqspinlocks still don't perform as good as unfair locks in many cases. On the other hands, unfair locks do have the problem of lock starvation that pvqspinlocks don't have.
This patch combines the best attributes of an unfair lock and a pvqspinlock into a hybrid lock with 2 modes - queued mode & unfair mode. A lock waiter goes into the unfair mode when there are waiters in the wait queue but the pending bit isn't set. Otherwise, it will go into the queued mode waiting in the queue for its turn.
On a 2-socket 36-core E5-2699 v3 system (HT off), a kernel build (make -j<n>) was done in a VM with unpinned vCPUs 3 times with the best time selected and <n> is the number of vCPUs available. The build times of the original pvqspinlock, hybrid pvqspinlock and unfair lock with various number of vCPUs are as follows:
vCPUs pvqlock hybrid pvqlock unfair lock ----- ------- -------------- ----------- 30 342.1s 329.1s 329.1s 36 314.1s 305.3s 307.3s 45 345.0s 302.1s 306.6s 54 365.4s 308.6s 307.8s 72 358.9s 293.6s 303.9s 108 343.0s 285.9s 304.2sThe hybrid pvqspinlock performs better or comparable to the unfair lock.
By turning on
QUEUED_LOCK_STAT, the table below showed the number of lock acquisitions in unfair mode and queue mode after a kernel build with various number of vCPUs.vCPUs queued mode unfair mode ----- ----------- ----------- 30 9,130,518 294,954 36 10,856,614 386,809 45 8,467,264 11,475,373 54 6,409,987 19,670,855 72 4,782,063 25,712,180It can be seen that as the VM became more and more over-committed, the ratio of locks acquired in unfair mode increases. This is all done automatically to get the best overall performance as possible.
The table below shows the kernel build times on a smaller 2-socket 16-core 32-thread E5-2620 v4 system.
vCPUs pvqlock hybrid pvqlock unfair lock ----- ------- -------------- ----------- 16 436.8s 433.4s 435.6s 36 366.2s 364.8s 364.5s 48 423.6s 376.3s 370.2s 64 433.1s 376.6s 376.8s
Quoted 5 lines
Quoted 2 lines
Again, the performance of the hybrid pvqspinlock was comparable to that of the unfair lock.
You forgot to test a starvation case. And you also forgot to describe how they cannot happen. I really cannot remember how all this is supposed to work.
Lock starvation shouldn't happen. The pending bit is set by the queue head to indicate its readiness before spinning on the lock. Once the pending bit is made visible to all the CPUs, no one can steal the lock and they will all queued up in the wait queue.
I ran my locking microbenchmark on a 2-socket 36-core system (HT off) with # of locking threads equals to the number of vCPUs in a kvm VM. The table below show the the min/mean/max per-thread locking ops done in 5 seconds:
#vCPUs min/avg/max lockops
36 822,135/881,063/950,363 54 542,435/581,664/625,937 72 397,500/428,177/499,299
It is obvious that there was no lock starvation here.
Cheers,
Longman
Peter Zijlstra
maintainerQuoted 9 lines · Waiman Long
Quoted 7 lines · Peter Zijlstra
Quoted 5 lines · Waiman Long
This patch combines the best attributes of an unfair lock and a pvqspinlock into a hybrid lock with 2 modes - queued mode & unfair mode. A lock waiter goes into the unfair mode when there are waiters in the wait queue but the pending bit isn't set. Otherwise, it will go into the queued mode waiting in the queue for its turn.
Quoted 8 lines
Quoted 3 lines
You forgot to test a starvation case. And you also forgot to describe how they cannot happen. I really cannot remember how all this is supposed to work.
Lock starvation shouldn't happen. The pending bit is set by the queue head to indicate its readiness before spinning on the lock. Once the pending bit is made visible to all the CPUs, no one can steal the lock and they will all queued up in the wait queue.
So the queue path of queued_spin_lock_slowpath() does queued_spin_trylock() which, for PV, ends up being that pv_queued_spin_steal_lock(), which you changed to spin util PENDING.
Now PENDING is set by pv_wait_head_or_lock(), but that is far after queued_spin_trylock().
The way I'm reading this is that we'll never get there... because we'll all be spinning in pv_queued_spin_steal_lock().
So how will we fail pv_queued_spin_steal_lock() in order to then end up in pv_wait_head_or_lock() to set PENDING such that pv_queued_spin_steal_lock() will fail?
The comment with your new pv_queued_spin_steal_lock() should very clearly spell out how this works.
Quoted 11 lines
I ran my locking microbenchmark on a 2-socket 36-core system (HT off) with # of locking threads equals to the number of vCPUs in a kvm VM. The table below show the the min/mean/max per-thread locking ops done in 5 seconds:
#vCPUs min/avg/max lockops
36 822,135/881,063/950,363 54 542,435/581,664/625,937 72 397,500/428,177/499,299It is obvious that there was no lock starvation here.
It is however not obvious if that is the worst case; at the very least you should compare to the test-and-set variant which has known starvation. If this test doesn't show starvation with the test-and-set then this test is bad.
Waiman Long
reviewerQuoted 25 lines · Peter Zijlstra
Quoted 7 lines · Waiman Long
Quoted 6 lines · Peter Zijlstra
Quoted 5 lines · Waiman Long
This patch combines the best attributes of an unfair lock and a pvqspinlock into a hybrid lock with 2 modes - queued mode & unfair mode. A lock waiter goes into the unfair mode when there are waiters in the wait queue but the pending bit isn't set. Otherwise, it will go into the queued mode waiting in the queue for its turn.
Quoted 7 lines
Quoted 3 lines
You forgot to test a starvation case. And you also forgot to describe how they cannot happen. I really cannot remember how all this is supposed to work.
Lock starvation shouldn't happen. The pending bit is set by the queue head to indicate its readiness before spinning on the lock. Once the pending bit is made visible to all the CPUs, no one can steal the lock and they will all queued up in the wait queue.
So the queue path of
queued_spin_lock_slowpath()doesqueued_spin_trylock()which, for PV, ends up being thatpv_queued_spin_steal_lock(), which you changed to spin util PENDING.Now PENDING is set by
pv_wait_head_or_lock(), but that is far afterqueued_spin_trylock().The way I'm reading this is that we'll never get there... because we'll all be spinning in
pv_queued_spin_steal_lock().
Quoted 6 lines
So how will we fail
pv_queued_spin_steal_lock()in order to then end up inpv_wait_head_or_lock()to set PENDING such thatpv_queued_spin_steal_lock()will fail?The comment with your new
pv_queued_spin_steal_lock()should very clearly spell out how this works.
I did add a comment to say that the lock waiter will stay in unfair mode only when there are WAITERS and the pending bit is not set. So if no CPU is in the wait queue, it will just do one trylock as is before the patch and move on to the regular slowpath. I will update the comments to clarify that I mean waiters in the wait queue.
Quoted 11 lines
Quoted 11 lines
I ran my locking microbenchmark on a 2-socket 36-core system (HT off) with # of locking threads equals to the number of vCPUs in a kvm VM. The table below show the the min/mean/max per-thread locking ops done in 5 seconds:
#vCPUs min/avg/max lockops
36 822,135/881,063/950,363 54 542,435/581,664/625,937 72 397,500/428,177/499,299
Quoted 5 lines
Quoted 1 line
It is obvious that there was no lock starvation here.
It is however not obvious if that is the worst case; at the very least you should compare to the test-and-set variant which has known starvation. If this test doesn't show starvation with the test-and-set then this test is bad.
Sure, I will add the unfair lock case for comparison.
Cheers,
Longman