Skip to contentSkip to conversation

x86,smp: make ticket spinlock proportional backoff w/ auto tuning

RFC PATCH In review Rik van Riel 5 participants 17 messages Jan 3, 2013 – Jan 5, 2013

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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.
#1 lore raw

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
index 33692ea..dc492f6 100644
@@ -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
index 48d2b7d..20da354 100644
@@ -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 ...
#2 lore raw

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.
#3 lore raw

RFC PATCH 2/5 x86,smp: proportional backoff for ticket spinlocks

In reply to 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.

---
 arch/x86/kernel/smp.c |   23 ++++++++++++++++++++---
 1 files changed, 20 insertions(+), 3 deletions(-)
arch/x86/kernel/smp.c +20 -3
index 20da354..9c56fe3 100644
@@ -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;
 	}
 }
#4 lore raw

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.

---
 arch/x86/kernel/smp.c |   23 ++++++++++++++++++++---
 1 files changed, 20 insertions(+), 3 deletions(-)
arch/x86/kernel/smp.c +0 -0
index 20da354..9c56fe3 100644
@@ -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 -2
 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;
                                             ^^^^^^^^^^^^^^

Just wondering,
Does wraparound affects this?

#5 lore raw

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.

---
 arch/x86/kernel/smp.c |   23 ++++++++++++++++++++---
 1 files changed, 20 insertions(+), 3 deletions(-)
arch/x86/kernel/smp.c +0 -0
index 20da354..9c56fe3 100644
@@ -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 -2
 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;
                                             ^^^^^^^^^^^^^^
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.
#6 lore raw

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.

---
  arch/x86/kernel/smp.c |   23 ++++++++++++++++++++---
  1 files changed, 20 insertions(+), 3 deletions(-)
arch/x86/kernel/smp.c +0 -0
index 20da354..9c56fe3 100644
@@ -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 -2
  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;
                                              ^^^^^^^^^^^^^^
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.

#7 lore raw

RFC PATCH 3/5 x86,smp: auto tune spinlock backoff delay factor

In reply to 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.

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
index aa743e9..f1ec7f7 100644
@@ -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);
 }
 
 /*
#8 lore raw

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.
#9 lore raw

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 :)

#10 lore raw

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
#11 lore raw

RFC PATCH 4/5 x86,smp: keep spinlock delay values per hashed spinlock address

In reply to 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.

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
index 6065291..29360c4 100644
@@ -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;
 }
 
 /*
#12 lore raw

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.
#13 lore raw

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_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.

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)

#14 lore raw

RFC PATCH 5/5 x86,smp: add debugging code to track spinlock delay value

In reply to Rik van Riel

From: 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
index 29360c4..a4401ed 100644
@@ -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);
+	}
 }
 
 /*
#15 lore raw
In reply to Rik van Riel
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.
#16 lore raw
In reply to Rik van Riel

[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
index e6881fd..2f637ce 100644
@@ -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 void
arch_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)