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

Subject: 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.

Signed-off-by Rik van Riel <[email protected]>

arch/x86/include/asm/spinlock.h +2 -1

index 33692ea..2a45eb0 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,11 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 
        inc = xadd(&lock->tickets, inc);
 
-       for (;;) {

arch/x86/include/asm/spinlock.h +0 -0

        barrier();              /* make sure nothing creeps before the lock is taken */
 }
 

arch/x86/kernel/smp.c +1 -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.

arch/x86/include/asm/spinlock.h static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) · line 62

Quoted 9 lines · Rik van Riel

arch/x86/include/asm/spinlock.h +5 -0

@@ -53,12 +55,11 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 
         inc = xadd(&lock->tickets, inc);
 
+       if (inc.head == inc.tail)
+               goto out;
+
+       ticket_spin_lock_wait(lock, inc);
+ out:

why not just:

if (inc.head != inc.tail)
ticket_spin_lock_wait(lock, inc)

Quoted 6 lines

arch/x86/kernel/smp.c +2 -0

+++ b/arch/x86/kernel/smp.c

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

arch/x86/kernel/smp.c static atomic_t stopping_cpu = ATOMIC_INIT(-1); · line 126

Quoted 10 lines

arch/x86/kernel/smp.c +10 -0

+ */
+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;
+       }

Why not just:

do {
   cpu_relax()
   inc.head = ...
} while (inc.head != inc.tail);

Other than that, no problems with the principle of it.

Subject: 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.

Signed-off-by Rik van Riel <[email protected]>

---

 arch/x86/include/asm/spinlock.h |   13 +++++++------
 arch/x86/kernel/smp.c           |   14 ++++++++++++++
 2 files changed, 21 insertions(+), 6 deletions(-)

arch/x86/include/asm/spinlock.h +7 -6

index 33692ea..2a45eb0 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,11 @@ 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)
+		goto out;
+
+	ticket_spin_lock_wait(lock, inc);
+ out:
 	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 ...

Subject: x86,smp: proportional backoff for ticket spinlocks

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.

Signed-off-by Rik van Riel <[email protected]>

---
 arch/x86/kernel/smp.c |    6 ++++--
 1 files changed, 4 insertions(+), 2 deletions(-)

arch/x86/kernel/smp.c +0 -0

index 20da354..4e44840 100644

arch/x86/kernel/smp.c +1 -1

+		inc.head = ACCESS_ONCE(lock->tickets.head);
 		if (inc.head == inc.tail)
 			break;
 	}
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

arch/x86/kernel/smp.c static bool smp_no_nmi_ipi = false; · line 123

Quoted 13 lines

arch/x86/kernel/smp.c +3 -2

index 20da354..4e44840 100644
@@ -118,9 +118,11 @@ static bool smp_no_nmi_ipi = false;
 void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc)
 {
 	for (;;) {
-		cpu_relax();
-		inc.head = ACCESS_ONCE(lock->tickets.head);
+		int loops = 50 * (__ticket_t)(inc.tail - inc.head);
+		while (loops--)
+			cpu_relax();

-ENOCOMMENT

Please add a comment above to explain what it's doing. Don't expect people to check change logs. Also, explain why you picked 50.

OK, I replied here before reading patch 3 (still reviewing it). Why have this patch at all? Just to test if you broke something between this and patch 3? Or perhaps patch 3 may not get accepted? In that case, you would still need a comment.

Either explicitly state that this patch is just a stepping stone for patch 3, and will either be accepted or rejected along with patch 3. Or keep it as a stand alone patch and add comments as such. Or just get rid of it all together.

Subject: x86,smp: proportional backoff for ticket spinlocks

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.

Signed-off-by Rik van Riel <[email protected]>

Subject: x86,smp: proportional backoff for ticket spinlocks

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.

Signed-off-by Rik van Riel <[email protected]>

---

 arch/x86/kernel/smp.c |    6 ++++--
 1 files changed, 4 insertions(+), 2 deletions(-)

arch/x86/kernel/smp.c +4 -2

index 20da354..4e44840 100644
@@ -118,9 +118,11 @@ static bool smp_no_nmi_ipi = false;
 void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc)
 {
 	for (;;) {
-		cpu_relax();
-		inc.head = ACCESS_ONCE(lock->tickets.head);
+		int loops = 50 * (__ticket_t)(inc.tail - inc.head);
+		while (loops--)
+			cpu_relax();
 
+		inc.head = ACCESS_ONCE(lock->tickets.head);
 		if (inc.head == inc.tail)
 			break;
 	}

Argh, the first one had a typo in it that did not influence performance with fewer threads running, but that made things worse with more than a dozen threads...

Quoted 3 lines · Rik van Riel

Argh, the first one had a typo in it that did not influence performance with fewer threads running, but that made things worse with more than a dozen threads...

arch/x86/kernel/smp.c static atomic_t stopping_cpu = ATOMIC_INIT(-1); · line 169

Quoted 10 lines

arch/x86/kernel/smp.c +10 -0

+
+		/*
+		 * The lock is still busy, the delay was not long enough.
+		 * Going through here 2.7 times will, on average, cancel
+		 * out the decrement above. Using a non-integer number
+		 * gets rid of performance artifacts and reduces oversleeping.
+		 */
+		if (delay < MAX_SPINLOCK_DELAY &&
+				((inc.head & 3) == 0 || (inc.head & 7) == 1))
+			delay++;

((inc.head & 3) == 0 || (inc.head & 7) == 1)) seems a strange condition to me...

Quoted 7 lines · Rik van Riel

Argh, the first one had a typo in it that did not influence performance with fewer threads running, but that made things worse with more than a dozen threads...

Please let me know if you can break these patches. ---8<---
Subject: x86,smp: auto tune spinlock backoff delay factor

arch/x86/kernel/smp.c static atomic_t stopping_cpu = ATOMIC_INIT(-1); · line 138

Quoted 3 lines

arch/x86/kernel/smp.c +3 -0

+#define MIN_SPINLOCK_DELAY 1
+#define MAX_SPINLOCK_DELAY 1000
+DEFINE_PER_CPU(int, spinlock_delay) = { MIN_SPINLOCK_DELAY };

Using a single spinlock_delay per cpu assumes there is a single contended spinlock on the machine, or that contended spinlocks protect the same critical section.

Given that we probably know where the contended spinlocks are, couldnt we use a real scalable implementation for them ?

A known contended one is the Qdisc lock in network layer. We added a second lock (busylock) to lower a bit the pressure on a separate cache line, but a scalable lock would be much better...

I guess there are patent issues...

arch/x86/kernel/smp.c static atomic_t stopping_cpu = ATOMIC_INIT(-1); · line 146

Quoted 2 lines · Rik van Riel

arch/x86/kernel/smp.c +2 -0

+	int *delay_ptr = &per_cpu(spinlock_delay, smp_processor_id());
+	int delay = *delay_ptr;

int delay = __this_cpu_read(spinlock_delay);

arch/x86/kernel/smp.c static atomic_t stopping_cpu = ATOMIC_INIT(-1); · line 171

Quoted 2 lines

  	}

arch/x86/kernel/smp.c +1 -0

+	*delay_ptr = delay;

__this_cpu_write(spinlock_delay, delay);

arch/x86/kernel/smp.c +20 -1

index 4e44840..e44c56f 100644
@@ -113,19 +113,62 @@ 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. Adjusting "delay" to poll, on average, 2.7 times before the
+ * lock is obtained seems to result in low bus traffic. The combination
+ * of aiming for a non-integer amount of average polls, and scaling the
+ * sleep period proportionally to how many CPUs are ahead of us in the
+ * queue for this ticket lock seems to reduce the amount of time spent
+ * "oversleeping" the release of the lock.
  */
+#define MIN_SPINLOCK_DELAY 1

arch/x86/kernel/smp.c +9 -2

+
 	for (;;) {
-		int loops = 50 * (__ticket_t)(inc.tail - inc.head);
+		int loops = delay * (__ticket_t)(inc.tail - inc.head);
 		while (loops--)
 			cpu_relax();
 
 		inc.head = ACCESS_ONCE(lock->tickets.head);
-		if (inc.head == inc.tail)
+		if (inc.head == inc.tail) {
+			/* Decrease the delay, since we may have overslept. */
+			if (delay > MIN_SPINLOCK_DELAY)
+				delay--;
 			break;
+		}
+
+		/*

arch/x86/kernel/smp.c +0 -1

 }
 
 /*
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 30 lines · Rik van Riel

arch/x86/kernel/smp.c +20 -1

index 4e44840..e44c56f 100644
@@ -113,19 +113,62 @@ 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. Adjusting "delay" to poll, on average, 2.7 times before the
+ * lock is obtained seems to result in low bus traffic. The combination
+ * of aiming for a non-integer amount of average polls, and scaling the
+ * sleep period proportionally to how many CPUs are ahead of us in the
+ * queue for this ticket lock seems to reduce the amount of time spent
+ * "oversleeping" the release of the lock.
   */
+#define MIN_SPINLOCK_DELAY 1

arch/x86/kernel/smp.c static atomic_t stopping_cpu = ATOMIC_INIT(-1); · line 146

Quoted 10 lines

arch/x86/kernel/smp.c +8 -0

+#define MAX_SPINLOCK_DELAY 1000
+DEFINE_PER_CPU(int, spinlock_delay) = { MIN_SPINLOCK_DELAY };
  void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc)
  {
+	/*
+	 * Use the raw per-cpu pointer; preemption is disabled in the
+	 * spinlock code. This avoids put_cpu_var once we have the lock.
+	 */
+	int *delay_ptr = &per_cpu(spinlock_delay, smp_processor_id());
+	int delay = *delay_ptr;

I'm confused by the above comment. Why not just:

	int delay = this_cpu_read(spinlock_delay);

?

Too bad you posted this just before break. I currently have access to a 40 core box, and I would have loved to test this. But right now I have it testing other things, and hopefully I'll still have access to it after the break.

I will try to run this test on a really large SMP system in the lab during the break.

Ideally, the auto-tuning will keep the delay value large enough that performance will stay flat even when there are 100 CPUs contending over the same lock.

Maybe it turns out that the maximum allowed delay value needs to be larger. Only one way to find out...

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.

Quoted 6 lines · Eric Dumazet

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.

I will probably keep it as a separate patch 4/4, with your report and performance numbers in it, to preserve the reason why we keep multiple hashed values, etc...

There is enough stuff in this code that will be indishinguishable from magic if we do not document it properly...

If we go with per-spinlock tunings, I feel we'll most likely want to add an associative cache in order to avoid the 1/16 chance (~6%) of getting 595Mbit/s instead of 982Mbit/s when there is a hash collision.

I would still prefer if we could make up something that didn't require per-spinlock tunings, but it's not clear if that'll work. At least we now know of a simple enough workload to figure it out :)

Quoted 7 lines · Michel Lespinasse

If we go with per-spinlock tunings, I feel we'll most likely want to add an associative cache in order to avoid the 1/16 chance (~6%) of getting 595Mbit/s instead of 982Mbit/s when there is a hash collision.

I would still prefer if we could make up something that didn't require per-spinlock tunings, but it's not clear if that'll work. At least we now know of a simple enough workload to figure it out :)

Even with a per spinlock tuning, we can find workloads where holding time depends on the context.

For example, complex qdisc hierarchy typically use different times on enqueue and dequeue operations.

So the hash sounds good to me, because the hash key could mix both lock address and caller IP ( __builtin_return_address(1) in ticket_spin_lock_wait())

Quoted 1 line

Quoted 1 line

Rik van Riel <[email protected]> 12/27/12 4:01 PM >>>

Quoted 3 lines · Eric Dumazet

So the hash sounds good to me, because the hash key could mix both lock address and caller IP ( __builtin_return_address(1) in ticket_spin_lock_wait())

The lock acquisition time depends on the holder of the lock, and what the CPUs ahead of us in line will do with the lock, not on the caller IP of the spinner.

Quoted 9 lines

Quoted 1 line

Quoted 1 line

Rik van Riel <[email protected]> 12/27/12 4:01 PM >>>

Quoted 3 lines · Eric Dumazet

So the hash sounds good to me, because the hash key could mix both lock address and caller IP ( __builtin_return_address(1) in ticket_spin_lock_wait())

The lock acquisition time depends on the holder of the lock, and what the CPUs ahead of us in line will do with the lock, not on the caller IP of the spinner.

The lock holder could supply its __builtin_return_address(0) for use in eventual hashing.

Also, with all of this - did you evaluate the alternative of using monitor/mwait instead?

Quoted 1 line

Quoted 1 line · Rik van Riel

Quoted 10 lines · Jan Beulich

Quoted 9 lines

Quoted 1 line

Quoted 1 line

Rik van Riel <[email protected]> 12/27/12 4:01 PM >>>

Quoted 3 lines · Eric Dumazet

So the hash sounds good to me, because the hash key could mix both lock address and caller IP ( __builtin_return_address(1) in ticket_spin_lock_wait())

The lock acquisition time depends on the holder of the lock, and what the CPUs ahead of us in line will do with the lock, not on the caller IP of the spinner.

Quoted 5 lines

The lock holder could supply its __builtin_return_address(0) for use in eventual hashing.

Also, with all of this - did you evaluate the alternative of using monitor/mwait instead?

How much bus traffic do monitor/mwait cause behind the scenes?

Quoted 1 line

How much bus traffic do monitor/mwait cause behind the scenes?

I would suppose that this just snoops the bus for writes, but the amount of bus traffic involved in this isn't explicitly documented.

One downside of course is that unless a spin lock is made occupy exactly a cache line, false wakeups are possible.

Quoted 5 lines · Jan Beulich

Quoted 1 line

How much bus traffic do monitor/mwait cause behind the scenes?

I would suppose that this just snoops the bus for writes, but the amount of bus traffic involved in this isn't explicitly documented.

Quoted 2 lines

One downside of course is that unless a spin lock is made occupy exactly a cache line, false wakeups are possible.

And that would probably be very likely, as the whole purpose of Rik's patches was to lower cache stalls due to other CPUs pounding on spin locks that share the cache line of what is being protected (and modified).

Quoted 10 lines · Steven Rostedt

Quoted 7 lines · Jan Beulich

Quoted 1 line

How much bus traffic do monitor/mwait cause behind the scenes?

I would suppose that this just snoops the bus for writes, but the amount of bus traffic involved in this isn't explicitly documented.

One downside of course is that unless a spin lock is made occupy exactly a cache line, false wakeups are possible.

Quoted 4 lines

And that would probably be very likely, as the whole purpose of Rik's patches was to lower cache stalls due to other CPUs pounding on spin locks that share the cache line of what is being protected (and modified).

A monitor/mwait would be an option only if using MCS (or K42 variant) locks, where each cpu would wait on a private and dedicated cache line.

Quoted 16 lines · Eric Dumazet

Quoted 14 lines · Steven Rostedt

Quoted 7 lines · Jan Beulich

Quoted 1 line

How much bus traffic do monitor/mwait cause behind the scenes?

I would suppose that this just snoops the bus for writes, but the amount of bus traffic involved in this isn't explicitly documented.

One downside of course is that unless a spin lock is made occupy exactly a cache line, false wakeups are possible.

And that would probably be very likely, as the whole purpose of Rik's patches was to lower cache stalls due to other CPUs pounding on spin locks that share the cache line of what is being protected (and modified).

Quoted 2 lines

A monitor/mwait would be an option only if using MCS (or K42 variant) locks, where each cpu would wait on a private and dedicated cache line.

But then would the problem even exist? If the lock is on its own cache line, it shouldn't cause a performance issue if other CPUs are spinning on it. Would it?

Quoted 3 lines

But then would the problem even exist? If the lock is on its own cache line, it shouldn't cause a performance issue if other CPUs are spinning on it. Would it?

Not sure I understand the question.

Quoted 6 lines · Eric Dumazet

Quoted 3 lines

But then would the problem even exist? If the lock is on its own cache line, it shouldn't cause a performance issue if other CPUs are spinning on it. Would it?

Not sure I understand the question.

I'll explain my question better.

I thought the whole point of Rik's patches was to solve a performance problem caused by contention on a lock that shares a cache line with data.

In the ideal case, locks wont be contented, and are taken and released quickly (being from the RT world, I know this isn't true :-( ). In this case, it's also advantageous to keep the lock on the same cache line as the data that's being updated. This way, the process of grabbing the lock also pulls in the data that you will soon be using.

But then the problem occurs when you have a bunch of other CPUs trying to take this lock in a tight spin. Every time the owner of the lock touches the data, the other CPUs doing a LOCK read on the spinlock will cause bus contention on the owner CPU as the data shares the cache and needs to be synced. As the owner CPU just touched the cache line that is under a tight loop of LOCK reads on other CPUs. By adding the delays, the CPU with the lock doesn't stall at every update of the data protected by the lock.

Thus, if monitor/mwait is ideal only for locks on its own cache line, then they are pointless for the locks that are causing the issue we are trying to fix.

The lock acquisition time depends on the holder of the lock, and what the CPUs ahead of us in line will do with the lock, not on the caller IP of the spinner.

Therefore, I am not convinced that hashing on the caller IP will add much, if anything, except increasing the chance that we end up not backing off when we should...

IMHO it would be good to try keeping this solution as simple as we can get away with.

Quoted 4 lines · Rik van Riel

The lock acquisition time depends on the holder of the lock, and what the CPUs ahead of us in line will do with the lock, not on the caller IP of the spinner.

That would be true only for general cases.

In network land, we do have spinlock acquisition time depending on the context.

A garbage collector usually runs for longer time than the regular fast path.

But even without gc, its pretty often we have consumer/producers that don't have the same amount of work to perform per lock/unlock sections.

The socket lock per example, might be held for very small sections for process contexts (lock_sock() / release_sock()), but longer sections from softirq context. Of course, severe lock contention on a socket seems unlikely in real workloads.

Quoted 7 lines

Therefore, I am not convinced that hashing on the caller IP will add much, if anything, except increasing the chance that we end up not backing off when we should...

IMHO it would be good to try keeping this solution as simple as we can get away with.

unsigned long hash = (unsigned long)lock ^

                      (unsigned long)__builtin_return_address(1);

seems simple enough to me, but I get your point.

I also recorded the max 'delay' value reached on my machine to check how good MAX_SPINLOCK_DELAY value was :

[   89.628265] cpu 16 delay 3710
[   89.631230] cpu 6 delay 2930
[   89.634120] cpu 15 delay 3186
[   89.637092] cpu 18 delay 3789
[   89.640071] cpu 22 delay 4012
[   89.643080] cpu 11 delay 3389
[   89.646057] cpu 21 delay 3123
[   89.649035] cpu 9 delay 3295
[   89.651931] cpu 3 delay 3063
[   89.654811] cpu 14 delay 3335

Although it makes no performance difference to use a bigger/smaller one.

to use a bigger/smaller one.

I guess we want a larger value.

With your hashed lock approach, we can get away with larger values - they will not penalize other locks the same way a single value per cpu might have.

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)

Quoted 6 lines · Eric Dumazet

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)

Quoted 6 lines

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)

I've been trying to use this workload on a similar machine. I am getting some confusing results however:

with 24 concurrent netperf -t UDP_STREAM -H $target -- -m 128 -R 1 , I am seeing some non-trivial run-to-run performance variation - about 5% in v3.7 baseline, but very significant after applying rik's 3 patches. my last few runs gave me results of 890.92, 1073.74, 963.13, 1234.41, 754.18, 893.82. This is generally better than what I'm getting with baseline, but the variance is huge (which is somewhat surprising given that rik's patches don't have the issue of hash collisions).

Also,
this is significant in that I am not seeing the regression you were observing with just these 3 patches.

If I add a 1 second delay in the netperf command line (netperf -t UDP_STREAM -s 1 -H lpk18 -- -m 128 -R 1), I am seeing a very constant 660 Mbps result, but then I don't see any benefit from applying rik's patches. I have no explanation for these results, but I am getting them very consistently...

Quoted 2 lines

In this workload we have at least two contended spinlocks, with different delays. (spinlocks are not held for the same duration)

Just to confirm, I believe you are refering to qdisc->q.lock and qdisc->busylock ?

Subject: x86,smp: auto tune spinlock backoff delay factor

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.

Signed-off-by Rik van Riel <[email protected]>

---
  arch/x86/kernel/smp.c |   49 ++++++++++++++++++++++++++++++++++++++++++++++---
  1 files changed, 46 insertions(+), 3 deletions(-)

arch/x86/kernel/smp.c +13 -1

index 1c1eb02..8786476 100644
@@ -113,19 +113,62 @@ 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

arch/x86/kernel/smp.c +24 -3

  void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc)
  {
+	/*
+	 * Use the raw per-cpu pointer; preemption is disabled in the
+	 * spinlock code. This avoids put_cpu_var once we have the lock.
+	 */
+	int *delay_ptr = &per_cpu(spinlock_delay, smp_processor_id());
+	int delay = *delay_ptr;
+
  	for (;;) {
-		int loops = 50 * (__ticket_t)(inc.tail - inc.head);
+		int loops = delay * (__ticket_t)(inc.tail - inc.head);
  		while (loops--)
  			cpu_relax();
 
  		inc.head = ACCESS_ONCE(lock->tickets.head);
-		if (inc.head == inc.tail)
+		if (inc.head == inc.tail) {
+			/* Decrease the delay, since we may have overslept. */
+			if (delay > MIN_SPINLOCK_DELAY)
+				delay--;
  			break;
+		}
+
+		/*
+		 * The lock is still busy, the delay was not long enough.
+		 * Going through here 2.7 times will, on average, cancel
+		 * out the decrement above. Using a non-integer number
+		 * gets rid of performance artifacts and reduces oversleeping.
+		 */
+		if (delay < MAX_SPINLOCK_DELAY &&
+				(!(inc.head & 3) == 0 || (inc.head & 7) == 1))
+			delay++;
  	}
+	*delay_ptr = delay;
  }
 
  /*
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

arch/x86/kernel/smp.c static atomic_t stopping_cpu = ATOMIC_INIT(-1); · line 138

Quoted 3 lines

arch/x86/kernel/smp.c +3 -0

+#define MIN_SPINLOCK_DELAY 1
+#define MAX_SPINLOCK_DELAY 1000
+DEFINE_PER_CPU(int, spinlock_delay) = { MIN_SPINLOCK_DELAY };

This gives the same delay for all locks in the system, but the amount of work done under each lock is different. So, for any given lock, the delay is not optimal.

This is an untested idea that came to me after looking at this:

o Assume that for any given lock, the optimal delay is the same for all CPUs in the system.

o Store a per-lock delay value in arch_spinlock_t.

o Once a CPU owns the lock it can update the delay as you do for the per_cpu version. Tuning the delay on fewer of the locking operations reduces bus traffic, but makes it converge more slowly.

o Bonus points if you can update the delay as part of the releasing store.

Quoted 9 lines · David Daney

arch/x86/kernel/smp.c static atomic_t stopping_cpu = ATOMIC_INIT(-1); · line 138

Quoted 3 lines

arch/x86/kernel/smp.c +3 -0

+#define MIN_SPINLOCK_DELAY 1
+#define MAX_SPINLOCK_DELAY 1000
+DEFINE_PER_CPU(int, spinlock_delay) = { MIN_SPINLOCK_DELAY };

This gives the same delay for all locks in the system, but the amount of work done under each lock is different. So, for any given lock, the delay is not optimal.

Quoted 6 lines

This is an untested idea that came to me after looking at this:

o Assume that for any given lock, the optimal delay is the same for all CPUs in the system.

o Store a per-lock delay value in arch_spinlock_t.

Quoted 6 lines

o Once a CPU owns the lock it can update the delay as you do for the per_cpu version. Tuning the delay on fewer of the locking operations reduces bus traffic, but makes it converge more slowly.

o Bonus points if you can update the delay as part of the releasing store.

It would absolutely have to be part of the same load and store cycle, otherwise we would increase bus traffic and defeat the purpose.

However, since spinlock contention should not be the usual state, and all a scalable lock does is make sure that N+1 CPUs does not perform worse than N CPUs, using scalable locks is a stop-gap measure.

I believe a stop-gap measure should be kept as simple as we can. I am willing to consider moving to a per-lock delay factor if we can figure out an easy way to do it, but I would like to avoid too much extra complexity...

Quoted 9 lines · Rik van Riel

However, since spinlock contention should not be the usual state, and all a scalable lock does is make sure that N+1 CPUs does not perform worse than N CPUs, using scalable locks is a stop-gap measure.

I believe a stop-gap measure should be kept as simple as we can. I am willing to consider moving to a per-lock delay factor if we can figure out an easy way to do it, but I would like to avoid too much extra complexity...

Rik,

I like your solution. It's rather simple and simple solutions tend to end up being the closest to optimal. The more complex a solution gets, the more it starts chasing fireflies.

Anyway, I'd like to see this code tested, and more benchmarks run against it.

Quoted 12 lines · Steven Rostedt

Quoted 9 lines · Rik van Riel

However, since spinlock contention should not be the usual state, and all a scalable lock does is make sure that N+1 CPUs does not perform worse than N CPUs, using scalable locks is a stop-gap measure.

I believe a stop-gap measure should be kept as simple as we can. I am willing to consider moving to a per-lock delay factor if we can figure out an easy way to do it, but I would like to avoid too much extra complexity...

Quoted 8 lines

Rik,

I like your solution. It's rather simple and simple solutions tend to end up being the closest to optimal. The more complex a solution gets, the more it starts chasing fireflies.

Anyway, I'd like to see this code tested, and more benchmarks run against it.

Absolutely. I would love to see if this code actually causes regressions anywhere.

It is simple enough that I suspect it will not, but there really is only one way to find out.

The more people test this with different workloads on different SMP systems, the better.

Subject: x86,smp: auto tune spinlock backoff delay factor

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.

Signed-off-by Rik van Riel <[email protected]>

However, I have a few concerns about the behavior of this, which I think deserve more experimentation (I may try helping with it after new years).

One thing you mentioned in 0/3 is that the best value varies depending on the number of CPUs contending. This is somewhat surprising to me; I would have guessed/hoped that the (inc.tail - inc.head) multiplicative factor would account for that already.

What I'm getting at is that I would be more confident that the autotune algorithm will work well in all cases if the value only depended on the system parameters such as CPU type and frequency, rather than per-spinlock parameters such as number of waiters and hold time.

I feel this review is too high-level to be really helpful, so I'll stop until I can find time to experiment :)

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

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.

Just cosmetic - avoid an unnecessary goto construct

Signed-off-by Michel Lespinasse <[email protected]>