x86,smp: make ticket spinlock proportional backoff w/ auto tuning
Subsystems (2)
cover x86,smp: make ticket spinlock proportional backoff w/ auto tuning
Many spinlocks are embedded in data structures; having many CPUs pounce on the cache line the lock is in will slow down the lock holder, and can cause system performance to fall off a cliff.
The paper "Non-scalable locks are dangerous" is a good reference:
http://pdos.csail.mit.edu/papers/linux:lock.pdf
In the Linux kernel, spinlocks are optimized for the case of there not being contention. After all, if there is contention, the data structure can be improved to reduce or eliminate lock contention.
Likewise, the spinlock API should remain simple, and the common case of the lock not being contended should remain as fast as ever.
However, since spinlock contention should be fairly uncommon, we can add functionality into the spinlock slow path that keeps system performance from falling off a cliff when there is lock contention.
Proportional delay in ticket locks is delaying the time between checking the ticket based on a delay factor, and the number of CPUs ahead of us in the queue for this lock. Checking the lock less often allows the lock holder to continue running, resulting in better throughput and preventing performance from dropping off a cliff.
The test case has a number of threads locking and unlocking a semaphore. With just one thread, everything sits in the CPU cache and throughput is around 2.6 million operations per second, with a 5-10% variation.
Once a second thread gets involved, data structures bounce from CPU to CPU, and performance deteriorates to about 1.25 million operations per second, with a 5-10% variation.
However, as more and more threads get added to the mix, performance with the vanilla kernel continues to deteriorate. Once I hit 24 threads, on a 24 CPU, 4 node test system, performance is down to about 290k operations/second.
With a proportional backoff delay added to the spinlock code, performance with 24 threads goes up to about 400k operations/second with a 50x delay, and about 900k operations/second with a 250x delay. However, with a 250x delay, performance with 2-5 threads is worse than with a 50x delay.
Making the code auto-tune the delay factor results in a system that performs well with both light and heavy lock contention, and should also protect against the (likely) case of the fixed delay factor being wrong for other hardware.
The attached graph shows the performance of the multi threaded semaphore lock/unlock test case, with 1-24 threads, on the vanilla kernel, with 10x, 50x, and 250x proportional delay, as well as the v1 patch series with autotuning for 2x and 2.7x spinning before the lock is obtained, and with the v2 series.
The v2 series integrates several ideas from Michel Lespinasse and Eric Dumazet, which should result in better throughput and nicer behaviour in situations with contention on multiple locks.
Please let me know if you manage to break this code in any way, so I can fix it...
Signature · 1 line
All rights reversed.
RFC PATCH 1/5 x86,smp: move waiting on contended ticket lock out of line
Moving the wait loop for congested loops to its own function allows us to add things to that wait loop, without growing the size of the kernel text appreciably.
---
v2: clean up the code a little, after Michel's suggestion
arch/x86/include/asm/spinlock.h | 11 +++++------ arch/x86/kernel/smp.c | 14 ++++++++++++++ 2 files changed, 19 insertions(+), 6 deletions(-)
arch/x86/include/asm/spinlock.h +5 -6
@@ -34,6 +34,8 @@# define UNLOCK_LOCK_PREFIX #endif +extern void ticket_spin_lock_wait (arch_spinlock_t *,struct __raw_tickets ); +/* * Ticket locks are conceptually two parts, one indicating the current head of * the queue, and the other indicating the current tail. The lock is acquired
@@ -53,12 +55,9 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) inc =xadd (&lock->tickets, inc); -for (;;) { -if (inc.head == inc.tail) -break ; -cpu_relax (); - inc.head =ACCESS_ONCE (lock->tickets.head); - } +if (inc.head != inc.tail) +ticket_spin_lock_wait (lock, inc); +barrier ();/* make sure nothing creeps before the lock is taken */ }
arch/x86/kernel/smp.c +14 -0
@@ -113,6 +113,20 @@ static atomic_t stopping_cpu = ATOMIC_INIT(-1);static bool smp_no_nmi_ipi = false;/* +* Wait on a congested ticket spinlock. +*/ +void ticket_spin_lock_wait (arch_spinlock_t *lock,struct __raw_tickets inc) +{ +for (;;) { +cpu_relax (); + inc.head =ACCESS_ONCE (lock->tickets.head); + +if (inc.head == inc.tail) +break ; + } +} + +/* * this function sends a 'reschedule' IPI to another CPU. * it goes straight through and wastes no time serializing * anything. Worst case is that we lose a reschedule ...
Re: [RFC PATCH 1/5] x86,smp: move waiting on contended ticket lock out of line
Quoted 3 lines · Rik van Riel
Moving the wait loop for congested loops to its own function allows us to add things to that wait loop, without growing the size of the kernel text appreciably.
Looks good :)
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
RFC PATCH 2/5 x86,smp: proportional backoff for ticket spinlocks
In reply to Rik van RielSimple fixed value proportional backoff for ticket spinlocks. By pounding on the cacheline with the spin lock less often, bus traffic is reduced. In cases of a data structure with embedded spinlock, the lock holder has a better chance of making progress.
If we are next in line behind the current holder of the lock, we do a fast spin, so as not to waste any time when the lock is released.
The number 50 is likely to be wrong for many setups, and this patch is mostly to illustrate the concept of proportional backup. The next patch automatically tunes the delay value.
--- arch/x86/kernel/smp.c | 23 ++++++++++++++++++++--- 1 files changed, 20 insertions(+), 3 deletions(-)
arch/x86/kernel/smp.c +20 -3
@@ -117,11 +117,28 @@ static bool smp_no_nmi_ipi = false;*/ void ticket_spin_lock_wait (arch_spinlock_t *lock,struct __raw_tickets inc) { +__ticket_t head = inc.head, ticket = inc.tail; +__ticket_t waiters_ahead; +unsigned loops; +for (;;) { -cpu_relax (); - inc.head =ACCESS_ONCE (lock->tickets.head); + waiters_ahead = ticket - head -1 ; +/* +* We are next after the current lock holder. Check often +* to avoid wasting time when the lock is released. +*/ +if (!waiters_ahead) { +do { +cpu_relax (); + }while (ACCESS_ONCE (lock->tickets.head) != ticket); +break ; + } + loops =50 * waiters_ahead; +while (loops--) +cpu_relax (); -if (inc.head == inc.tail) + head =ACCESS_ONCE (lock->tickets.head); +if (head == ticket)break ; } }
Re: [RFC PATCH 2/5] x86,smp: proportional backoff for ticket spinlocks
[Ccing IBM id]
Quoted 26 lines · Rik van Riel
Simple fixed value proportional backoff for ticket spinlocks. By pounding on the cacheline with the spin lock less often, bus traffic is reduced. In cases of a data structure with embedded spinlock, the lock holder has a better chance of making progress.
If we are next in line behind the current holder of the lock, we do a fast spin, so as not to waste any time when the lock is released.
The number 50 is likely to be wrong for many setups, and this patch is mostly to illustrate the concept of proportional backup. The next patch automatically tunes the delay value.
Signed-off-by Rik van Riel <[email protected]>Signed-off-by Michel Lespinasse <[email protected]>--- arch/x86/kernel/smp.c | 23 ++++++++++++++++++++--- 1 files changed, 20 insertions(+), 3 deletions(-)arch/x86/kernel/smp.c +0
-0@@ -117,11 +117,28 @@ static bool smp_no_nmi_ipi = false;*/
arch/x86/kernel/smp.c static bool smp_no_nmi_ipi = false; · line 125
Quoted 10 lines
arch/x86/kernel/smp.c +5
-2void ticket_spin_lock_wait (arch_spinlock_t *lock,struct __raw_tickets inc) { +__ticket_t head = inc.head, ticket = inc.tail; +__ticket_t waiters_ahead; +unsigned loops; +for (;;) { -cpu_relax (); - inc.head =ACCESS_ONCE (lock->tickets.head); + waiters_ahead = ticket - head -1 ;
^^^^^^^^^^^^^^
Just wondering,
Does wraparound affects this?
Re: [RFC PATCH 2/5] x86,smp: proportional backoff for ticket spinlocks
Quoted 39 lines · Raghavendra KT
[Ccing IBM id]
Quoted 26 lines · Rik van Riel
Simple fixed value proportional backoff for ticket spinlocks. By pounding on the cacheline with the spin lock less often, bus traffic is reduced. In cases of a data structure with embedded spinlock, the lock holder has a better chance of making progress.
If we are next in line behind the current holder of the lock, we do a fast spin, so as not to waste any time when the lock is released.
The number 50 is likely to be wrong for many setups, and this patch is mostly to illustrate the concept of proportional backup. The next patch automatically tunes the delay value.
Signed-off-by Rik van Riel <[email protected]>Signed-off-by Michel Lespinasse <[email protected]>--- arch/x86/kernel/smp.c | 23 ++++++++++++++++++++--- 1 files changed, 20 insertions(+), 3 deletions(-)arch/x86/kernel/smp.c +0
-0@@ -117,11 +117,28 @@ static bool smp_no_nmi_ipi = false;*/ arch/x86/kernel/smp.c static bool smp_no_nmi_ipi = false; · line 125
Quoted 10 lines
arch/x86/kernel/smp.c +5
-2void ticket_spin_lock_wait (arch_spinlock_t *lock,struct __raw_tickets inc) { +__ticket_t head = inc.head, ticket = inc.tail; +__ticket_t waiters_ahead; +unsigned loops; +for (;;) { -cpu_relax (); - inc.head =ACCESS_ONCE (lock->tickets.head); + waiters_ahead = ticket - head -1 ;^^^^^^^^^^^^^^
Quoted 2 lines
Just wondering,
Does wraparound affects this?
The result gets stored in waiters_ahead, which is unsigned and has same bit size as ticket and head. So, this takes care of the wraparound issue.
In other words, you may have to add 1<<8 or 1<<16 if the integer difference was negative; but you get that for free by just computing the difference as a 8 or 16 bit unsigned value.
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Re: [RFC PATCH 2/5] x86,smp: proportional backoff for ticket spinlocks
Quoted 44 lines · Michel Lespinasse
Quoted 39 lines · Raghavendra KT
[Ccing IBM id]
Quoted 26 lines · Rik van Riel
Simple fixed value proportional backoff for ticket spinlocks. By pounding on the cacheline with the spin lock less often, bus traffic is reduced. In cases of a data structure with embedded spinlock, the lock holder has a better chance of making progress.
If we are next in line behind the current holder of the lock, we do a fast spin, so as not to waste any time when the lock is released.
The number 50 is likely to be wrong for many setups, and this patch is mostly to illustrate the concept of proportional backup. The next patch automatically tunes the delay value.
Signed-off-by Rik van Riel <[email protected]>Signed-off-by Michel Lespinasse <[email protected]>--- arch/x86/kernel/smp.c | 23 ++++++++++++++++++++--- 1 files changed, 20 insertions(+), 3 deletions(-)arch/x86/kernel/smp.c +0
-0@@ -117,11 +117,28 @@ static bool smp_no_nmi_ipi = false;*/ arch/x86/kernel/smp.c static bool smp_no_nmi_ipi = false; · line 125
Quoted 10 lines
arch/x86/kernel/smp.c +5
-2void ticket_spin_lock_wait (arch_spinlock_t *lock,struct __raw_tickets inc) { +__ticket_t head = inc.head, ticket = inc.tail; +__ticket_t waiters_ahead; +unsigned loops; +for (;;) { -cpu_relax (); - inc.head =ACCESS_ONCE (lock->tickets.head); + waiters_ahead = ticket - head -1 ;^^^^^^^^^^^^^^Quoted 2 lines
Just wondering,
Does wraparound affects this?
Quoted 8 lines
The result gets stored in
waiters_ahead, which is unsigned and has same bit size as ticket and head. So, this takes care of the wraparound issue.In other words, you may have to add 1<<8 or 1<<16 if the integer difference was negative; but you get that for free by just computing the difference as a 8 or 16 bit unsigned value.
Michael,
Sorry for the noise and for missing the simple math :) and Thanks for explanation.
RFC PATCH 3/5 x86,smp: auto tune spinlock backoff delay factor
In reply to Rik van RielMany spinlocks are embedded in data structures; having many CPUs pounce on the cache line the lock is in will slow down the lock holder, and can cause system performance to fall off a cliff.
The paper "Non-scalable locks are dangerous" is a good reference:
http://pdos.csail.mit.edu/papers/linux:lock.pdf
In the Linux kernel, spinlocks are optimized for the case of there not being contention. After all, if there is contention, the data structure can be improved to reduce or eliminate lock contention.
Likewise, the spinlock API should remain simple, and the common case of the lock not being contended should remain as fast as ever.
However, since spinlock contention should be fairly uncommon, we can add functionality into the spinlock slow path that keeps system performance from falling off a cliff when there is lock contention.
Proportional delay in ticket locks is delaying the time between checking the ticket based on a delay factor, and the number of CPUs ahead of us in the queue for this lock. Checking the lock less often allows the lock holder to continue running, resulting in better throughput and preventing performance from dropping off a cliff.
Proportional spinlock delay with a high delay factor works well when there is lots contention on a lock. Likewise, a smaller delay factor works well when a lock is lightly contended.
Making the code auto-tune the delay factor results in a system that performs well with both light and heavy lock contention.
--- arch/x86/kernel/smp.c | 41 ++++++++++++++++++++++++++++++++++++++--- 1 files changed, 38 insertions(+), 3 deletions(-)
arch/x86/kernel/smp.c +38 -3
@@ -113,12 +113,31 @@ static atomic_t stopping_cpu = ATOMIC_INIT(-1);static bool smp_no_nmi_ipi = false;/* -* Wait on a congested ticket spinlock. +* Wait on a congested ticket spinlock. Many spinlocks are embedded in +* data structures; having many CPUs pounce on the cache line with the +* spinlock simultaneously can slow down the lock holder, and the system +* as a whole. +* +* To prevent total performance collapse in case of bad spinlock contention, +* perform proportional backoff. The per-cpu value of delay is automatically +* tuned to limit the number of times spinning CPUs poll the lock before +* obtaining it. This limits the amount of cross-CPU traffic required to obtain +* a spinlock, and keeps system performance from dropping off a cliff. +* +* There is a tradeoff. If we poll too often, the whole system is slowed +* down. If we sleep too long, the lock will go unused for a period of +* time. The solution is to go for a fast spin if we are at the head of +* the queue, to slowly increase the delay if we sleep for too short a +* time, and to decrease the delay if we slept for too long. */ +#define MIN_SPINLOCK_DELAY 1 +#define MAX_SPINLOCK_DELAY 16000 +DEFINE_PER_CPU(int, spinlock_delay) = { MIN_SPINLOCK_DELAY };void ticket_spin_lock_wait (arch_spinlock_t *lock,struct __raw_tickets inc) {__ticket_t head = inc.head, ticket = inc.tail;__ticket_t waiters_ahead; +int delay =__this_cpu_read (spinlock_delay);unsigned loops;for (;;) {
@@ -133,14 +152,30 @@ void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc) }while (ACCESS_ONCE (lock->tickets.head) != ticket);break ; } - loops =50 * waiters_ahead; + +/* +* The lock is still busy; slowly increase the delay. If we +* end up sleeping too long, the code below will reduce the +* delay. Ideally we acquire the lock in the tight loop above. +*/ +if (!(head %7 ) && delay <MAX_SPINLOCK_DELAY ) + delay++; + + loops = delay * waiters_ahead;while (loops--)cpu_relax (); head =ACCESS_ONCE (lock->tickets.head); -if (head == ticket) +if (head == ticket) { +/* +* We overslept and have no idea how long the lock +* went idle. Reduce the delay as a precaution. +*/ + delay -= delay/32 +1 ;break ; + } } +__this_cpu_write (spinlock_delay, delay); }/*
Re: [RFC PATCH 3/5] x86,smp: auto tune spinlock backoff delay factor
Quoted 6 lines · Rik van Riel
Proportional spinlock delay with a high delay factor works well when there is lots contention on a lock. Likewise, a smaller delay factor works well when a lock is lightly contended.
Making the code auto-tune the delay factor results in a system that performs well with both light and heavy lock contention.
I don't quite like that part of the explanation - Ideally I would like to explain that there are huge benefits in having the delay be at least equivalent to the time taken by a no-load spin/release section, and that beyond that there are small additional benefits to using a longer delay when the spinlock hold times are larger, and an explanation of why linear increase / exponential delay works nicely here.
I'll see if I can make a more concrete proposal and still keep it short enough :)
arch/x86/kernel/smp.c static atomic_t stopping_cpu = ATOMIC_INIT(-1); · line 135
Quoted 3 lines
arch/x86/kernel/smp.c +3
-0+#define MIN_SPINLOCK_DELAY 1 +#define MAX_SPINLOCK_DELAY 16000 +DEFINE_PER_CPU(int, spinlock_delay) = { MIN_SPINLOCK_DELAY };
unsigned would seem more natural here, though it's only a tiny detail
Quoted 5 lines
void
ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc){ __ticket_t head = inc.head, ticket = inc.tail; __ticket_t waiters_ahead;+ int delay =
__this_cpu_read(spinlock_delay);
I like that you used __this_cpu_read() - your v1 version wasn't as nice.
arch/x86/kernel/smp.c void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc) · line 164
Quoted 10 lines
arch/x86/kernel/smp.c +10
-0+ +/* +* The lock is still busy; slowly increase the delay. If we +* end up sleeping too long, the code below will reduce the +* delay. Ideally we acquire the lock in the tight loop above. +*/ +if (!(head %7 ) && delay <MAX_SPINLOCK_DELAY ) + delay++; + + loops = delay * waiters_ahead;
I don't like the head % 7 thing. I think using fixed point arithmetic would be nicer:
if (delay < MAX_SPINLOCK_DELAY)
delay += 256/7; /* Or whatever constant we choose */
loops = (delay * waiter_ahead) >> 8;
Also, we should probably skip the delay increment on the first loop iteration - after all, we haven't waited yet, so we can't say that the delay was too short.
arch/x86/kernel/smp.c void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc) · line 174
Quoted 7 lines
arch/x86/kernel/smp.c +6
-1-if (head == ticket) +if (head == ticket) { +/* +* We overslept and have no idea how long the lock +* went idle. Reduce the delay as a precaution. +*/ + delay -= delay/32 +1 ;
There is a possibility of integer underflow here. It seems that the window to hit it would be quite small, but it can happen (at the very least, imagine getting an interrupt at an inopportune time which would make it look like you overslept). I think this may be what was causing the stability issues I noticed.
I'll try to come up with a custom version of this patch. I do feel that we're going in a good direction in general, though.
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Re: [RFC PATCH 3/5] x86,smp: auto tune spinlock backoff delay factor
Quoted 2 lines · Michel Lespinasse
I'll see if I can make a more concrete proposal and still keep it short enough :)
Looking forward to that. I have thought about it some more, and am still not sure about a better description for the changelog...
Quoted 5 lines
arch/x86/kernel/smp.c static atomic_t stopping_cpu = ATOMIC_INIT(-1); · line 135
Quoted 3 lines
arch/x86/kernel/smp.c +3
-0+#define MIN_SPINLOCK_DELAY 1 +#define MAX_SPINLOCK_DELAY 16000 +DEFINE_PER_CPU(int, spinlock_delay) = { MIN_SPINLOCK_DELAY };unsigned would seem more natural here, though it's only a tiny detail
I might as well make that change while addressing the issues you found :)
Quoted 14 lines
arch/x86/kernel/smp.c void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc) · line 164
Quoted 10 lines
arch/x86/kernel/smp.c +10
-0+ +/* +* The lock is still busy; slowly increase the delay. If we +* end up sleeping too long, the code below will reduce the +* delay. Ideally we acquire the lock in the tight loop above. +*/ +if (!(head %7 ) && delay <MAX_SPINLOCK_DELAY ) + delay++; + + loops = delay * waiters_ahead;I don't like the head % 7 thing. I think using fixed point arithmetic would be nicer:
Quoted 4 lines
if (delay <
MAX_SPINLOCK_DELAY)
delay += 256/7; /* Or whatever constant we choose */loops = (delay *
waiter_ahead) >> 8;
I'll do that. That could get completely rid of any artifacts caused by incrementing sometimes, and not other times.
Quoted 3 lines
Also, we should probably skip the delay increment on the first loop iteration - after all, we haven't waited yet, so we can't say that the delay was too short.
Good point. I will do that.
Quoted 9 lines
arch/x86/kernel/smp.c void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc) · line 174
Quoted 7 lines
arch/x86/kernel/smp.c +6
-1-if (head == ticket) +if (head == ticket) { +/* +* We overslept and have no idea how long the lock +* went idle. Reduce the delay as a precaution. +*/ + delay -= delay/32 +1 ;There is a possibility of integer underflow here.
Fixed in my local code base now.
I will build a kernel with the things you pointed out fixed, and will give it a spin this afternoon.
Expect new patches soonish :)
Re: [RFC PATCH 3/5] x86,smp: auto tune spinlock backoff delay factor
Quoted 20 lines · Rik van Riel
Quoted 5 lines
arch/x86/kernel/smp.c void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc) · line 164
Quoted 4 lines
arch/x86/kernel/smp.c +4
-0+if (!(head %7 ) && delay <MAX_SPINLOCK_DELAY ) + delay++; + + loops = delay * waiters_ahead;Quoted 7 lines
I don't like the head % 7 thing. I think using fixed point arithmetic would be nicer:
if (delay <
MAX_SPINLOCK_DELAY)
delay += 256/7; /* Or whatever constant we choose */loops = (delay *
waiter_ahead) >> 8;I'll do that. That could get completely rid of any artifacts caused by incrementing sometimes, and not other times.
Quoted 3 lines
Also, we should probably skip the delay increment on the first loop iteration - after all, we haven't waited yet, so we can't say that the delay was too short.
Quoted 6 lines
Good point. I will do that.
I will build a kernel with the things you pointed out fixed, and will give it a spin this afternoon.
Expect new patches soonish :)
After implementing all the ideas you came up with, which made perfect sense to me, the code performs significantly worse than before.
*sigh*
New patches will be coming ... later.
Signature · 1 line
All rights reversed
RFC PATCH 4/5 x86,smp: keep spinlock delay values per hashed spinlock address
In reply to Rik van RielFrom: Eric Dumazet <[email protected]>
Eric Dumazet found a regression with the spinlock backoff code, in workloads where multiple spinlocks were contended, each having a different wait time.
This patch has multiple delay values per cpu, indexed on a hash of the lock address, to avoid that problem.
Eric Dumazet wrote:
I did some tests with your patches with following configuration :
tc qdisc add dev eth0 root htb r2q 1000 default 3
(to force a contention on qdisc lock, even with a multi queue net device)
and 24 concurrent "netperf -t UDP_STREAM -H other_machine -- -m 128"
Machine : 2 Intel(R) Xeon(R) CPU X5660 @ 2.80GHz
(24 threads), and a fast NIC (10Gbps)
Resulting in a 13 % regression (676 Mbits -> 595 Mbits)
In this workload we have at least two contended spinlocks, with different delays. (spinlocks are not held for the same duration)
It clearly defeats your assumption of a single per cpu delay being OK :
Some cpus are spinning too long while the lock was released.
We might try to use a hash on lock address, and an array of 16 different delays so that different spinlocks have a chance of not sharing the same delay.
With following patch, I get 982 Mbits/s with same bench, so an increase of 45 % instead of a 13 % regression.
--- arch/x86/kernel/smp.c | 22 +++++++++++++++++++--- 1 files changed, 19 insertions(+), 3 deletions(-)
arch/x86/kernel/smp.c +19 -3
@@ -23,6 +23,7 @@#include <linux/interrupt.h> #include <linux/cpu.h> #include <linux/gfp.h> +#include <linux/hash.h> #include <asm/mtrr.h> #include <asm/tlbflush.h>
@@ -135,12 +136,26 @@ static bool smp_no_nmi_ipi = false;*/ #define MIN_SPINLOCK_DELAY 1#define MAX_SPINLOCK_DELAY 16000 -DEFINE_PER_CPU(int, spinlock_delay) = { MIN_SPINLOCK_DELAY }; +#define DELAY_HASH_SHIFT 6 +struct delay_entry { +u32 hash; +u32 delay; +}; +static DEFINE_PER_CPU(struct delay_entry [1 << DELAY_HASH_SHIFT], spinlock_delay) = { + [0 ... (1 <<DELAY_HASH_SHIFT ) -1 ] = { + .hash =0 , + .delay =MIN_SPINLOCK_DELAY , + }, +}; +void ticket_spin_lock_wait (arch_spinlock_t *lock,struct __raw_tickets inc) {__ticket_t head = inc.head, ticket = inc.tail;__ticket_t waiters_ahead; -int delay =__this_cpu_read (spinlock_delay); +u32 hash =hash32_ptr (lock); +u32 slot =hash_32 (hash,DELAY_HASH_SHIFT ); +struct delay_entry *ent = &__get_cpu_var (spinlock_delay[slot]); +u32 delay = (ent->hash == hash) ? ent->delay :MIN_SPINLOCK_DELAY ;unsigned loops;for (;;) {
@@ -178,7 +193,8 @@ void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc)break ; } } -__this_cpu_write (spinlock_delay, delay); + ent->hash = hash; + ent->delay = delay; }/*
Re: [RFC PATCH 4/5] x86,smp: keep spinlock delay values per hashed spinlock address
Quoted 5 lines · Rik van Riel
From: Eric Dumazet <[email protected]>
Eric Dumazet found a regression with the spinlock backoff code, in workloads where multiple spinlocks were contended, each having a different wait time.
I think you should really clarify that the regression was observed with version 1 of your proposal. At that time,
1- the autotune code tended to use too long delays for long held locks, and
2- there was no exponential backoff, which meant that sharing stats between a long held and a short held spinlock could really hurt throughput on the short held spinlock
I believe that with autotune v2, this really shouldnt be a problem and stats sharing should result in just using a delay that's appropriate for the shorter of the two lock hold times - which is not the optimal value, but is actually close enough performance wise and, most importantly, should not cause any regression when compared to current mainline.
(it's important to point that out because otherwise, you might trick Linus into thinking your patches are risky, which I think they shouldn't be after you implemented exponential backoff)
arch/x86/kernel/smp.c static bool smp_no_nmi_ipi = false; · line 158
Quoted 9 lines
void
ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc){ __ticket_t head = inc.head, ticket = inc.tail; __ticket_t waiters_ahead;arch/x86/kernel/smp.c +4
-1-int delay =__this_cpu_read (spinlock_delay); +u32 hash =hash32_ptr (lock); +u32 slot =hash_32 (hash,DELAY_HASH_SHIFT ); +struct delay_entry *ent = &__get_cpu_var (spinlock_delay[slot]); +u32 delay = (ent->hash == hash) ? ent->delay :MIN_SPINLOCK_DELAY ;
IMO we want to avoid MIN_SPINLOCK_DELAY here. The exponential backoff autotune should make us resilient to collisions (if they happen we'll just end up with something very close to the min of the delays that would have been appropriate for either locks), so it should be better to just let collisions happen rather than force the use of MIN_SPINLOCK_DELAY.
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
Re: [RFC PATCH 4/5] x86,smp: keep spinlock delay values per hashed spinlock address
Quoted 38 lines · Michel Lespinasse
Quoted 5 lines · Rik van Riel
From: Eric Dumazet <[email protected]>
Eric Dumazet found a regression with the spinlock backoff code, in workloads where multiple spinlocks were contended, each having a different wait time.
I think you should really clarify that the regression was observed with version 1 of your proposal. At that time,
1- the autotune code tended to use too long delays for long held locks, and
2- there was no exponential backoff, which meant that sharing stats between a long held and a short held spinlock could really hurt throughput on the short held spinlock
I believe that with autotune v2, this really shouldnt be a problem and stats sharing should result in just using a delay that's appropriate for the shorter of the two lock hold times - which is not the optimal value, but is actually close enough performance wise and, most importantly, should not cause any regression when compared to current mainline.
(it's important to point that out because otherwise, you might trick Linus into thinking your patches are risky, which I think they shouldn't be after you implemented exponential backoff)
arch/x86/kernel/smp.c static bool smp_no_nmi_ipi = false; · line 158
Quoted 9 lines
void
ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc){ __ticket_t head = inc.head, ticket = inc.tail; __ticket_t waiters_ahead;arch/x86/kernel/smp.c +4
-1-int delay =__this_cpu_read (spinlock_delay); +u32 hash =hash32_ptr (lock); +u32 slot =hash_32 (hash,DELAY_HASH_SHIFT ); +struct delay_entry *ent = &__get_cpu_var (spinlock_delay[slot]); +u32 delay = (ent->hash == hash) ? ent->delay :MIN_SPINLOCK_DELAY ;
Quoted 7 lines
IMO we want to avoid
MIN_SPINLOCK_DELAYhere. The exponential backoff autotune should make us resilient to collisions (if they happen we'll just end up with something very close to the min of the delays that would have been appropriate for either locks), so it should be better to just let collisions happen rather than force the use ofMIN_SPINLOCK_DELAY.
exponential backoff wont help, I tried this idea last week and found that its better to detect hash collision and safely use MIN_SPINLOCK_DELAY in this case.
Its better to not overestimate the delay and spin much longer than needed.
On a hash collision, we dont know at all the contention history of this lock, unless we store the EWMA delay inside the lock.
(On x86 and NR_CPUS <= 256, we have a 16 bit hole in the spinlock that
we could use for this)
RFC PATCH 5/5 x86,smp: add debugging code to track spinlock delay value
In reply to Rik van RielFrom: Eric Dumazet <[email protected]>
This code prints out the maximum spinlock delay value and the backtrace that pushed it that far.
On systems with serial consoles, the act of printing can cause the spinlock delay value to explode. It can still be useful as a debugging tool, but is probably too verbose to merge upstream in this form.
--- arch/x86/kernel/smp.c | 8 ++++++++ 1 files changed, 8 insertions(+), 0 deletions(-)
arch/x86/kernel/smp.c +8 -0
@@ -148,6 +148,8 @@ static DEFINE_PER_CPU(struct delay_entry [1 << DELAY_HASH_SHIFT], spinlock_delay }, }; +static DEFINE_PER_CPU(u16, maxdelay); +void ticket_spin_lock_wait (arch_spinlock_t *lock,struct __raw_tickets inc) {__ticket_t head = inc.head, ticket = inc.tail;
@@ -195,6 +197,12 @@ void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc) } ent->hash = hash; ent->delay = delay; + +if (__this_cpu_read (maxdelay) < delay) { +pr_err ("cpu %d lock %p delay %d\n" ,smp_processor_id (), lock, delay); +__this_cpu_write (maxdelay, delay); +WARN_ON (1 ); + } }/*
Quoted 6 lines · Rik van Riel
The v2 series integrates several ideas from Michel Lespinasse and Eric Dumazet, which should result in better throughput and nicer behaviour in situations with contention on multiple locks.
Please let me know if you manage to break this code in any way, so I can fix it...
I'm seeing some very weird things on my 3 test machines. Looks like the spinlock delay sometimes gets crazy, at which point spinlock performance becomes unbearable and the network driver freaks out.
# ./spinlock_load_test 1 spinlocks: 24159990 2 spinlocks: 12900657 3 spinlocks: 11547771 4 spinlocks: 9113 6 spinlocks: 259 8 spinlocks: 310 12 spinlocks: 283 16 spinlocks: <seems to be stuck here; meanwhile my serial console fills up with network driver cries>
Well, I take it as an incitation to pay special attention to this code review :)
Signature · 2 lines
Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.
[CCing my ibm id]
Quoted 60 lines · Rik van Riel
Many spinlocks are embedded in data structures; having many CPUs pounce on the cache line the lock is in will slow down the lock holder, and can cause system performance to fall off a cliff.
The paper "Non-scalable locks are dangerous" is a good reference:
http://pdos.csail.mit.edu/papers/linux:lock.pdf
In the Linux kernel, spinlocks are optimized for the case of there not being contention. After all, if there is contention, the data structure can be improved to reduce or eliminate lock contention.
Likewise, the spinlock API should remain simple, and the common case of the lock not being contended should remain as fast as ever.
However, since spinlock contention should be fairly uncommon, we can add functionality into the spinlock slow path that keeps system performance from falling off a cliff when there is lock contention.
Proportional delay in ticket locks is delaying the time between checking the ticket based on a delay factor, and the number of CPUs ahead of us in the queue for this lock. Checking the lock less often allows the lock holder to continue running, resulting in better throughput and preventing performance from dropping off a cliff.
The test case has a number of threads locking and unlocking a semaphore. With just one thread, everything sits in the CPU cache and throughput is around 2.6 million operations per second, with a 5-10% variation.
Once a second thread gets involved, data structures bounce from CPU to CPU, and performance deteriorates to about 1.25 million operations per second, with a 5-10% variation.
However, as more and more threads get added to the mix, performance with the vanilla kernel continues to deteriorate. Once I hit 24 threads, on a 24 CPU, 4 node test system, performance is down to about 290k operations/second.
With a proportional backoff delay added to the spinlock code, performance with 24 threads goes up to about 400k operations/second with a 50x delay, and about 900k operations/second with a 250x delay. However, with a 250x delay, performance with 2-5 threads is worse than with a 50x delay.
Making the code auto-tune the delay factor results in a system that performs well with both light and heavy lock contention, and should also protect against the (likely) case of the fixed delay factor being wrong for other hardware.
The attached graph shows the performance of the multi threaded semaphore lock/unlock test case, with 1-24 threads, on the vanilla kernel, with 10x, 50x, and 250x proportional delay, as well as the v1 patch series with autotuning for 2x and 2.7x spinning before the lock is obtained, and with the v2 series.
Quoted 7 lines
The v2 series integrates several ideas from Michel Lespinasse and Eric Dumazet, which should result in better throughput and nicer behaviour in situations with contention on multiple locks.
Please let me know if you manage to break this code in any way, so I can fix it...
Hi Rik,
Whole series looks very interesting.Thanks for posting spinlock. I am
also curious, how the series affect virtualization cases.
(was about to reply for V1 with Eric changes but delayed because of vacation).
I am planning try V2 on baremetal and guests and comeback.
On a related note,
While experimenting with PV spinlock, I had tried "weighed spinlock". rationale behind the patch is in virtualized environment use case is exactly opposite.
If head and tail difference is more, probability of getting lock is very less so, spin for only little time when difference is high. and after loop is over if we have not got lock, halt (pv spinlock)/ yield to better guy.
Here is the patch for reference that I tried on top of PV spinlocks.
summary of patch :
looping is proportional to
2 * SPIN_THRESHOLD
---------------------------------
( head - tail - 1)
---8<---
arch/x86/include/asm/spinlock.h +0 -0
@@ -53,6 +53,18 @@ static inline void
__ticket_enter_slowpath(arch_spinlock_t *lock)
set_bit(0, (volatile unsigned long *)&lock->tickets.tail);
}
+static inline unsigned get_spin_threshold(int diff)
+{
+ unsigned count = SPIN_THRESHOLD;
+
+ /* handle wrap around */
+ if (unlikely(diff < 0))
+ diff += TICKETLOCK_MAX_VAL;
+
+ count = count >> ((diff - 1) >> 1);
+ return count;
+}
+
#else /* !CONFIG_PARAVIRT_SPINLOCKS */
static __always_inline void __ticket_lock_spinning(arch_spinlock_t *lock,
__ticket_t ticket)
@@ -62,6 +74,10 @@ static inline void __ticket_unlock_kick(arch_spinlock_t *lock,
__ticket_t ticket)
{
}
+static inline unsigned get_spin_threshold(int diff)
+{
+ return SPIN_THRESHOLD;
+}
#endif /* CONFIG_PARAVIRT_SPINLOCKS */
@@ -88,8 +104,8 @@ static __always_inline voidarch_spin_lock(arch_spinlock_t *lock)
inc.tail &= ~TICKET_SLOWPATH_FLAG;
for (;;) {
- unsigned count = SPIN_THRESHOLD;
-
+ unsigned count = get_spin_threshold(inc.tail -
+ ACCESS_ONCE(lock->tickets.head));
do {
if (ACCESS_ONCE(lock->tickets.head) == inc.tail)
goto out;
(quoted diff) +0 -0
b/arch/x86/include/asm/spinlock_types.h
index 4f1bea1..22e38a5 100644
arch/x86/include/asm/spinlock_types.h +2 -0
@@ -14,9 +14,11 @@#if (CONFIG_NR_CPUS < (256 / __TICKET_LOCK_INC))typedef u8 __ticket_t ;typedef u16 __ticketpair_t ; +#define TICKETLOCK_MAX_VAL (1 << 8)#else typedef u16 __ticket_t ;typedef u32 __ticketpair_t ; +#define TICKETLOCK_MAX_VAL (1 << 16)#endif #define TICKET_LOCK_INC ((__ticket_t)__TICKET_LOCK_INC)