Skip to contentSkip to conversation

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

PATCH In review Rik van Riel 8 participants 27 messages Jan 8, 2013 – Jan 24, 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.

For the v3 series, I tried out all the ideas suggested by Michel. They made perfect sense, but in the end it turned out they did not work as well as the simple, aggressive "try to make the delay longer" policy I have now. Several small bug fixes and cleanups have been integrated.

Performance is within the margin of error of v2, so the graph has not been update.

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

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 ...
Reviewed-by on v1 1/5
#2 lore raw

Re: [PATCH 1/5] x86,smp: move waiting on contended ticket lock out of line

Quoted 10 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.

---
v2: clean up the code a little, after Michel's suggestion

Reviewed-by on v1 1/5
#3 lore raw

Re: [PATCH 1/5] x86,smp: move waiting on contended ticket lock out of line

In reply to Rik van Riel
Quoted 8 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.

#4 lore raw

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

In reply to Rik van Riel

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.

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..aa743e9 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;
 	}
 }
Reviewed-by on v1 2/5
#5 lore raw

Re: [PATCH 2/5] x86,smp: proportional backoff for ticket spinlocks

Quoted 49 lines · Rik van Riel

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.

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 +15 -2
index 20da354..aa743e9 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;
+		}

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

Quoted 10 lines
arch/x86/kernel/smp.c +5 -1
+		loops = 50 * waiters_ahead;
+		while (loops--)
+			cpu_relax();
 
-		if (inc.head == inc.tail)
+		head = ACCESS_ONCE(lock->tickets.head);
+		if (head == ticket)
 			break;
 	}
 }

In my tests, I used the following formula :

loops = 50 * ((ticket - head) - 1/2);

or :

delta = ticket - head;
loops = delay * delta - (delay >> 1);

(And I didnt use the special :

	if (!waiters_ahead) {
		do {
			cpu_relax();
		} while (ACCESS_ONCE(lock->tickets.head) != ticket);
		break;
	}

Because it means this wont help machines with 2 cpus.

(or more generally if there _is_ contention, but with one lock holder and one lock waiter)

#6 lore raw

Re: [PATCH 2/5] x86,smp: proportional backoff for ticket spinlocks

Quoted 63 lines · Eric Dumazet
Quoted 49 lines · Rik van Riel

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.

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 +15 -2
index 20da354..aa743e9 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;
+		}

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

Quoted 10 lines
arch/x86/kernel/smp.c +5 -1
+		loops = 50 * waiters_ahead;
+		while (loops--)
+			cpu_relax();
 
-		if (inc.head == inc.tail)
+		head = ACCESS_ONCE(lock->tickets.head);
+		if (head == ticket)
  			break;
  	}
  }
Quoted 8 lines

In my tests, I used the following formula :

loops = 50 * ((ticket - head) - 1/2);

or :

delta = ticket - head;
loops = delay * delta - (delay >> 1);

I suppose that rounding down the delta might result in more stable results, due to undersleeping less often.

Quoted 9 lines

(And I didnt use the special :

	if (!waiters_ahead) {
		do {
			cpu_relax();
		} while (ACCESS_ONCE(lock->tickets.head) != ticket);
		break;
	}
Quoted 4 lines

Because it means this wont help machines with 2 cpus.

(or more generally if there _is_ contention, but with one lock holder and one lock waiter)

Machines with 2 CPUs should not need help, because the cpu_relax() alone gives enough of a pause that the lock holder can make progress.

It may be interesting to try out your rounding-down of delta, to see if that makes things better.

Signature · 1 line
All rights reversed
Acked-by on v1 2/5
#7 lore raw

Re: [PATCH 2/5] x86,smp: proportional backoff for ticket spinlocks

In reply to Rik van Riel
Quoted 12 lines · Rik van Riel

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.

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.

Quoted 7 lines

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.

---

Quoted 40 lines
 arch/x86/kernel/smp.c |   23 ++++++++++++++++++++---
 1 files changed, 20 insertions(+), 3 deletions(-)
arch/x86/kernel/smp.c +20 -3
index 20da354..aa743e9 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;
 	}
 }
#8 lore raw

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.

---
v3: use fixed-point math for the delay calculations, suggested by Michel Lespinasse

 arch/x86/kernel/smp.c |   43 +++++++++++++++++++++++++++++++++++++++----
 1 files changed, 39 insertions(+), 4 deletions(-)
arch/x86/kernel/smp.c +39 -4
index aa743e9..05f828b 100644
@@ -113,13 +113,34 @@ 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 DELAY_SHIFT 8
+#define DELAY_FIXED_1 (1<<DELAY_SHIFT)
+#define MIN_SPINLOCK_DELAY (1 * DELAY_FIXED_1)
+#define MAX_SPINLOCK_DELAY (16000 * DELAY_FIXED_1)
+DEFINE_PER_CPU(unsigned, 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;
-	unsigned loops;
+	unsigned delay = __this_cpu_read(spinlock_delay);
+	unsigned loops = 1;
 
 	for (;;) {
 		waiters_ahead = ticket - head - 1;
@@ -133,14 +154,28 @@ 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;
+
+		/* Aggressively increase delay, to minimize lock accesses. */
+		if (delay < MAX_SPINLOCK_DELAY)
+			delay += DELAY_FIXED_1 / 7;
+
+		loops = (delay * waiters_ahead) >> DELAY_SHIFT;
 		while (loops--)
 			cpu_relax();
 
 		head = ACCESS_ONCE(lock->tickets.head);
-		if (head == ticket)
+		if (head == ticket) {
+			/*
+			 * We overslept, and do not know by how.
+			 * Exponentially decay the value of delay,
+			 * to get it back to a good value quickly.
+			 */
+			if (delay >= 2 * DELAY_FIXED_1)
+				delay -= max(delay/32, DELAY_FIXED_1);
 			break;
+		}
 	}
+	__this_cpu_write(spinlock_delay, delay);
 }
 
 /*
Acked-by on v1 3/5
#9 lore raw

Re: [PATCH 3/5] x86,smp: auto tune spinlock backoff delay factor

Quoted 33 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.

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.

Quoted 7 lines

Making the code auto-tune the delay factor results in a system that performs well with both light and heavy lock contention.

---
v3: use fixed-point math for the delay calculations, suggested by Michel Lespinasse

Quoted 76 lines
 arch/x86/kernel/smp.c |   43 +++++++++++++++++++++++++++++++++++++++----
 1 files changed, 39 insertions(+), 4 deletions(-)
arch/x86/kernel/smp.c +39 -4
index aa743e9..05f828b 100644
@@ -113,13 +113,34 @@ 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 DELAY_SHIFT 8
+#define DELAY_FIXED_1 (1<<DELAY_SHIFT)
+#define MIN_SPINLOCK_DELAY (1 * DELAY_FIXED_1)
+#define MAX_SPINLOCK_DELAY (16000 * DELAY_FIXED_1)
+DEFINE_PER_CPU(unsigned, 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;
-	unsigned loops;
+	unsigned delay = __this_cpu_read(spinlock_delay);
+	unsigned loops = 1;
 
 	for (;;) {
 		waiters_ahead = ticket - head - 1;
@@ -133,14 +154,28 @@ 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;
+
+		/* Aggressively increase delay, to minimize lock accesses. */
+		if (delay < MAX_SPINLOCK_DELAY)
+			delay += DELAY_FIXED_1 / 7;
+
+		loops = (delay * waiters_ahead) >> DELAY_SHIFT;
 		while (loops--)
 			cpu_relax();
 
 		head = ACCESS_ONCE(lock->tickets.head);
-		if (head == ticket)
+		if (head == ticket) {
+			/*
+			 * We overslept, and do not know by how.
+			 * Exponentially decay the value of delay,
+			 * to get it back to a good value quickly.
+			 */
+			if (delay >= 2 * DELAY_FIXED_1)
+				delay -= max(delay/32, DELAY_FIXED_1);
 			break;
+		}
 	}
+	__this_cpu_write(spinlock_delay, delay);
 }
 
 /*
Reviewed-by on v1 3/5
#10 lore raw

Re: [PATCH 3/5] x86,smp: auto tune spinlock backoff delay factor

In reply to Rik van Riel

arch/x86/kernel/smp.c void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc) · line 176

Quoted 13 lines · Rik van Riel

v3: use fixed-point math for the delay calculations, suggested by Michel Lespinasse

arch/x86/kernel/smp.c +9 -1
-               if (head == ticket)
+               if (head == ticket) {
+                       /*
+                        * We overslept, and do not know by how.
+                        * Exponentially decay the value of delay,
+                        * to get it back to a good value quickly.
+                        */
+                       if (delay >= 2 * DELAY_FIXED_1)
+                               delay -= max(delay/32, DELAY_FIXED_1);
                        break;
+               }

I think delay -= (delay - MIN_SPINLOCK_DELAY) / 32 would work too, and avoid the conditions here.

It won't make a difference in practice because delay > 32 * DELAY_FIXED_1 on all machines I tested (even for the shortest possible do-nothing spinlocked regions)

Also - I think we could make MIN_SPINLOCK_DELAY a tunable. There is a limit to how fast the lock cacheline can bounce from one waiter to the next, and we know that this limit isn't DELAY_FIXED_1. Using DELAY_FIXED_1 is OK when we don't know of a better lower bound for a given system, but I think it'd be nice if one could set the correct value if they know it.

Looking at the bigger picture:

The tests I've done haven't shown any regressions over baseline. Your v1 proposal had a tendency to oversleep but this has been fixed in v2 and v3. The only risk I can foresee, and I think this hasn't been tested enough, would be that the algorithm might oversleep when it encounters a mix of short and long held spinlocks. I think the proper behavior when we encounter this is that we want to be conservative and use the shortest encountered spinlock as our delay in that case. There is a strong theorical case that additive increase/exponential decay should achieve that, but I'd like to see it tested in practice.

Trying to lay down the argument why additive increase / exponential decay should work here:
- When we oversleep, we spin (waiters_ahead * delay / DELAY_FIXED_1) iterations (with waiters_ahead < NR_CPUS) and update new_delay = delay
* (31 / 32)
- If we keep oversleeping, delay will converge towards 0 so that the sum of all overslept delay values will be original_delay * sum(i=0...infinity, (31/32)^i) which is 32 * original_delay. So, the total number of oversleeping iterations is bounded by original_delay * (NR_CPUS * 32 / DELAY_FIXED_1)
- Each increase of delay by DELAY_FIXED_1 / 7 can thus be seen as having a potential worst-case future cost of (NR_CPUS * 32 / 7) oversleeping iterations.
I like that this last value is at least bounded, but it's still high enough that I think actual behavior in the face of varying hold durations should be investigated.

As for test results:
running 32 instances of netperf -t UDP_STREAM -H <server> -- -m 128 on a 32 hypercores machine (2 sandybridge sockets) and htb root qdisc:
I am seeing ~650 to ~680 Mbps total with baseline 3.7, and ~860 to ~890 Mbps total with patches 1-3 applied.
(patch 4 makes the results a bit more consistent, in the ~880 to ~890 Mbps range)

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#11 lore raw

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 first version of the spinlock backoff code, in a workload 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 05f828b..1877890 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>
@@ -134,12 +135,26 @@ static bool smp_no_nmi_ipi = false;
 #define DELAY_FIXED_1 (1<<DELAY_SHIFT)
 #define MIN_SPINLOCK_DELAY (1 * DELAY_FIXED_1)
 #define MAX_SPINLOCK_DELAY (16000 * DELAY_FIXED_1)
-DEFINE_PER_CPU(unsigned, 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;
-	unsigned 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 = 1;
 
 	for (;;) {
@@ -175,7 +190,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;
 }
 
 /*
Acked-by on v1 4/5
#12 lore raw

Re: [PATCH 4/5] x86,smp: keep spinlock delay values per hashed spinlock address

Quoted 34 lines · Rik van Riel

From: Eric Dumazet <[email protected]>

Eric Dumazet found a regression with the first version of the spinlock backoff code, in a workload 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.

Quoted 6 lines

With following patch, I get 982 Mbits/s with same bench, so an increase of 45 % instead of a 13 % regression.

---

Quoted 55 lines
 arch/x86/kernel/smp.c |   22 +++++++++++++++++++---
 1 files changed, 19 insertions(+), 3 deletions(-)
arch/x86/kernel/smp.c +19 -3
index 05f828b..1877890 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>
@@ -134,12 +135,26 @@ static bool smp_no_nmi_ipi = false;
 #define DELAY_FIXED_1 (1<<DELAY_SHIFT)
 #define MIN_SPINLOCK_DELAY (1 * DELAY_FIXED_1)
 #define MAX_SPINLOCK_DELAY (16000 * DELAY_FIXED_1)
-DEFINE_PER_CPU(unsigned, 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;
-	unsigned 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 = 1;
 
 	for (;;) {
@@ -175,7 +190,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;
 }
 
 /*
Reviewed-by on v1 4/5
#13 lore raw

Re: [PATCH 4/5] x86,smp: keep spinlock delay values per hashed spinlock address

In reply to Rik van Riel
Quoted 30 lines · Rik van Riel

From: Eric Dumazet <[email protected]>

Eric Dumazet found a regression with the first version of the spinlock backoff code, in a workload 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.

Quoted 6 lines

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.

Note that these results were with your v1 proposal. With v3 proposal, on a slightly different machine (2 socket sandybridge) with a similar NIC, I am not seeing the regression when not using the hash table. I think this is because v3 got more conservative about mixed spinlock hold times, and converges towards the shortest of the hold times in that case.

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

Quoted 5 lines
arch/x86/kernel/smp.c +4 -1
-       unsigned 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;

I think we should actually always use ent->delay here. My reasoning is that I think the base algorithm (from the previous patch) should have robustness against mixed spinlock hold times. We can't rely on detecting hash collisions to protect us against varying hold times, because this case could happen even with a single spinlock. So we need to make sure the base algorithm is robust and converges towards using the shorter of the spinlock hold times; if we have that then forcing a reset to MIN_SPINLOCK_DELAY only hurts since it reduces the delay below what is otherwise necessary.

Other than that:

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#14 lore raw

Re: [PATCH 4/5] x86,smp: keep spinlock delay values per hashed spinlock address

Quoted 38 lines · Michel Lespinasse
Quoted 30 lines · Rik van Riel

From: Eric Dumazet <[email protected]>

Eric Dumazet found a regression with the first version of the spinlock backoff code, in a workload 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.

Quoted 6 lines

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

Note that these results were with your v1 proposal. With v3 proposal, on a slightly different machine (2 socket sandybridge) with a similar NIC, I am not seeing the regression when not using the hash table. I think this is because v3 got more conservative about mixed spinlock hold times, and converges towards the shortest of the hold times in that case.

Eric,

with just patches 1-3, can you still reproduce the regression on your system?

In other words, could we get away with dropping the complexity of patch 4, or do we still need it?

Signature · 1 line
All rights reversed
#15 lore raw

Re: [PATCH 4/5] x86,smp: keep spinlock delay values per hashed spinlock address

Quoted 7 lines · Rik van Riel

Eric,

with just patches 1-3, can you still reproduce the regression on your system?

In other words, could we get away with dropping the complexity of patch 4, or do we still need it?

To be clear, I must say that I'm not opposing patch 4 per se. I think we should not rely on it to avoid regressions, as patch 3 needs to be robust enough to do that on its own. However, it may very well be that having different constants for each lock (or for each hash bucket as a proxy) helps - if lock B has a consistently longer hold time than lock A, having them in separate hash buckets will allow us to use optimal tunings for both, but if they collide or if we don't have a hash table, we'll use a delay that is close to A's value for both, which is safe (shouldn't introduce regressions) but not optimal.

In other words, I really don't want us to depend on the hash table for robustness but I think it's fine to have it for extra performance (as it's actually very short)

Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
#16 lore raw

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 be useful as a debugging tool, but is 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 1877890..d80aee7 100644
@@ -147,6 +147,8 @@ static DEFINE_PER_CPU(struct delay_entry [1 << DELAY_HASH_SHIFT], spinlock_delay
 	},
 };
 
+static DEFINE_PER_CPU(u32, maxdelay);
+
 void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc)
 {
 	__ticket_t head = inc.head, ticket = inc.tail;
@@ -192,6 +194,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) * 4 < delay * 3) {
+		pr_err("cpu %d lock %p delay %d\n", smp_processor_id(), lock, delay>>DELAY_SHIFT);
+		__this_cpu_write(maxdelay, delay);
+		WARN_ON(1);
+	}
 }
 
 /*
#17 lore raw
In reply to Rik van Riel
Quoted 70 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.

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.

For the v3 series, I tried out all the ideas suggested by Michel. They made perfect sense, but in the end it turned out they did not work as well as the simple, aggressive "try to make the delay longer" policy I have now. Several small bug fixes and cleanups have been integrated.

Quoted 6 lines

Performance is within the margin of error of v2, so the graph has not been update.

Please let me know if you manage to break this code in any way, so I can fix it...

Patch series does not show anymore weird behaviour because of the underflow (pointed by Michael) and looks fine.

I ran kernbench on 32 core (mx3850) machine with 3.8-rc2 base. x base_3.8rc2
+ rik_backoff
N Min Max Median Avg Stddev

x   8       222.977        231.16       227.735       227.388     3.1512986
+   8        218.75       232.347      229.1035     228.25425     4.2730225

No difference proven at 95.0% confidence

The run did not show much difference. But I believe a spinlock stress test would have shown the benefit.
I 'll start running benchmarks now on kvm guests and comeback with report.

#18 lore raw
Quoted 7 lines · Raghavendra K T

I ran kernbench on 32 core (mx3850) machine with 3.8-rc2 base. x base_3.8rc2
+ rik_backoff
N Min Max Median Avg Stddev

x   8       222.977        231.16       227.735       227.388     3.1512986
+   8        218.75       232.347      229.1035     228.25425     4.2730225

No difference proven at 95.0% confidence

I got similar results on smaller systems (1 socket, dual-cores and quad-cores) when running Rik's latest series, no big difference for good nor for worse, but I also think Rik's work is meant to address bigger systems with more cores contending for any given spinlock.

#19 lore raw
Quoted 9 lines · Rafael Aquini
Quoted 7 lines · Raghavendra K T

I ran kernbench on 32 core (mx3850) machine with 3.8-rc2 base. x base_3.8rc2
+ rik_backoff
N Min Max Median Avg Stddev

x   8       222.977        231.16       227.735       227.388     3.1512986
+   8        218.75       232.347      229.1035     228.25425     4.2730225

No difference proven at 95.0% confidence

Quoted 4 lines

I got similar results on smaller systems (1 socket, dual-cores and quad-cores) when running Rik's latest series, no big difference for good nor for worse, but I also think Rik's work is meant to address bigger systems with more cores contending for any given spinlock.

I was able to do the test on same 32 core machine with 4 guests (8GB RAM, 32 vcpu).
Here are the results

base = 3.8-rc2
patched = base + Rik V3 backoff series [patch 1-4]

+-----------+-----------+-----------+------------+-----------+
kernbench (sec lower is better)

+-----------+-----------+-----------+------------+-----------+
    base        stdev        patched      stdev     %improve
+-----------+-----------+-----------+------------+-----------+
    44.3000     2.0404	    46.7928     1.7518	  -5.62709
    94.8262     5.1444	   102.4737     7.8406	  -8.06475
   156.0540    14.5797	   167.6888     9.7110	  -7.45562
   202.3225    15.8906	   213.1435    17.1778	  -5.34839
+-----------+-----------+-----------+------------+-----------+
+-----------+-----------+-----------+------------+-----------+
               sysbench (sec lower is better)
+-----------+-----------+-----------+------------+-----------+
    base        stdev        patched      stdev     %improve
+-----------+-----------+-----------+------------+-----------+
    16.8512     0.4164	    17.7301     0.3761	  -5.21565
    13.0411     0.4115	    12.9380     0.1554	   0.79058
    18.4573     0.2123	    18.4662     0.2005	  -0.04822
    24.2021     0.1713	    24.3690     0.3270	  -0.68961
+-----------+-----------+-----------+------------+-----------+
+-----------+-----------+-----------+------------+-----------+
               ebizzy (record/sec higher is better)
+-----------+-----------+-----------+------------+-----------+
    base        stdev        patched      stdev     %improve
+-----------+-----------+-----------+------------+-----------+
  2494.4000    27.5447	  2400.6000    83.4255	  -3.76042
  2636.6000   302.9658	  2757.5000   147.5137	   4.58545
  2236.8333   239.6531	  2131.6667   156.1534	  -4.70158
  1768.8750   142.5437	  1901.3750   295.2147	   7.49064
+-----------+-----------+-----------+------------+-----------+
+-----------+-----------+-----------+------------+-----------+
              dbench (throughput in MB/sec higher is better)
+-----------+-----------+-----------+------------+-----------+
    base        stdev        patched      stdev     %improve
+-----------+-----------+-----------+------------+-----------+
 10076.9180  2410.9655	  5870.7460  4297.4532	  xxxxxxx
  2152.5220    88.2853	  1517.8270    61.9742	 -29.48611
  1334.9608    34.3247	  1078.4275    38.2288	 -19.21654
   946.6355    32.0426	   753.0757    25.5302	 -20.44713
+-----------+-----------+-----------+------------+-----------+

Please note that I have put dbench_1x result as xxxx since I observed very high variance in the result.

#20 lore raw
Quoted 16 lines · Raghavendra K T
Quoted 9 lines · Rafael Aquini
Quoted 7 lines · Raghavendra K T

I ran kernbench on 32 core (mx3850) machine with 3.8-rc2 base. x base_3.8rc2
+ rik_backoff
N Min Max Median Avg Stddev

x   8       222.977        231.16       227.735       227.388     3.1512986
+   8        218.75       232.347      229.1035     228.25425     4.2730225

No difference proven at 95.0% confidence

Quoted 4 lines

I got similar results on smaller systems (1 socket, dual-cores and quad-cores) when running Rik's latest series, no big difference for good nor for worse, but I also think Rik's work is meant to address bigger systems with more cores contending for any given spinlock.

Quoted 6 lines

I was able to do the test on same 32 core machine with 4 guests (8GB RAM, 32 vcpu).
Here are the results

base = 3.8-rc2
patched = base + Rik V3 backoff series [patch 1-4]

I believe I understand why this is happening.

Modern Intel and AMD CPUs have a feature called Pause Loop Exiting (PLE) and Pause Filter (PF), respectively. This feature is used to trap to the host when the guest is spinning on a spinlock.

This allows the host to run something else, and having the spinner temporarily yield the CPU. Effectively, this causes the KVM code to already do some limited amount of spinlock backoff code, in the host.

Adding more backoff code in the guest can lead to wild delays in acquiring locks, and generally bad performance.

I suspect that when running in a virtual machine, we should limit the delay factor to something much smaller, since the host will take care of most of the backoff for us.

Maybe a maximum delay value of ~10 would do the trick for KVM guests.

We should be able to get this right by placing the value for the maximum delay in a __read_mostly section and setting it to something small from an init function when we detect we are running in a virtual machine.

Let me cook up, and test, a patch that does that...

Signature · 1 line
All rights reversed
#21 lore raw
Quoted 36 lines · Rik van Riel
Quoted 22 lines · Raghavendra K T
Quoted 12 lines · Rafael Aquini
Quoted 10 lines · Raghavendra K T

I ran kernbench on 32 core (mx3850) machine with 3.8-rc2 base. x base_3.8rc2
+ rik_backoff
N Min Max Median
Avg Stddev
x 8 222.977 231.16 227.735 227.388
3.1512986
+ 8 218.75 232.347 229.1035 228.25425
4.2730225
No difference proven at 95.0% confidence

Quoted 7 lines

I got similar results on smaller systems (1 socket, dual-cores and quad-cores)
when running Rik's latest series, no big difference for good nor for worse,
but I also think Rik's work is meant to address bigger systems with more cores
contending for any given spinlock.

Quoted 6 lines

I was able to do the test on same 32 core machine with 4 guests (8GB RAM, 32 vcpu).
Here are the results

base = 3.8-rc2
patched = base + Rik V3 backoff series [patch 1-4]

I believe I understand why this is happening.

Modern Intel and AMD CPUs have a feature called Pause Loop Exiting (PLE) and Pause Filter (PF), respectively. This feature is used to trap to the host when the guest is spinning on a spinlock.

Quoted 7 lines

This allows the host to run something else, and having the spinner temporarily yield the CPU. Effectively, this causes the KVM code to already do some limited amount of spinlock backoff code, in the host.

Adding more backoff code in the guest can lead to wild delays in acquiring locks, and generally bad performance.

Yes agree with you.

Quoted 4 lines

I suspect that when running in a virtual machine, we should limit the delay factor to something much smaller, since the host will take care of most of the backoff for us.

Even for non-PLE case I believe it would be difficult to tune delay, because of VCPU scheduling and LHP.

Quoted 9 lines

Maybe a maximum delay value of ~10 would do the trick for KVM guests.

We should be able to get this right by placing the value for the maximum delay in a __read_mostly section and setting it to something small from an init function when we detect we are running in a virtual machine.

Let me cook up, and test, a patch that does that...

Sure.. Awaiting and happy to test the patches.
I also tried few things on my own and also how it behaves without patch
4. Nothing helped.

#22 lore raw
In reply to Rik van Riel
Quoted 2 lines · Rik van Riel

Please let me know if you manage to break this code in any way, so I can fix it...

I didn't break it, but did let it play with rq->lock contention. Using cyclictest -Smp99 -i 100 -d 0, with 3 rt tasks for pull_rt_task() to pull around appears to have been a ~dead heat.

3.6.11 3.6.11-spinlock

PerfTop: 78852 irqs/sec kernel:96.4% exact: 0.0% [1000Hz cycles], (all, 80 CPUs)
-------------------------------------------------------------------------------------------------

             samples  pcnt function                     samples  pcnt function
             _______ _____ ___________________________  _______ _____ ___________________________

           468341.00 52.0% cpupri_set                  471786.00 52.0% cpupri_set
           110259.00 12.2% _raw_spin_lock               88963.00  9.8% ticket_spin_lock_wait
            78863.00  8.8% native_write_msr_safe        77109.00  8.5% native_write_msr_safe
            42882.00  4.8% __schedule                   48858.00  5.4% native_write_cr0
            40930.00  4.5% native_write_cr0             47038.00  5.2% __schedule
            13718.00  1.5% finish_task_switch           24775.00  2.7% _raw_spin_lock
            13188.00  1.5% plist_del                    13117.00  1.4% plist_del
            13078.00  1.5% _raw_spin_lock_irqsave       12372.00  1.4% ttwu_do_wakeup
            12083.00  1.3% ttwu_do_wakeup               11553.00  1.3% _raw_spin_lock_irqsave
             8359.00  0.9% pull_rt_task                  8186.00  0.9% pull_rt_task
             6979.00  0.8% apic_timer_interrupt          7989.00  0.9% finish_task_switch
             4623.00  0.5% __enqueue_rt_entity           6430.00  0.7% apic_timer_interrupt
             3961.00  0.4% resched_task                  4721.00  0.5% resched_task
             3942.00  0.4% __switch_to                   4109.00  0.5% __switch_to
             3128.00  0.3% _raw_spin_trylock             2917.00  0.3% rcu_idle_exit_common
             3081.00  0.3% __tick_nohz_idle_enter        2897.00  0.3% __local_bh_enable
             2561.00  0.3% update_curr_rt                2873.00  0.3% _raw_spin_trylock
             2385.00  0.3% _raw_spin_lock_irq            2674.00  0.3% __enqueue_rt_entity
             2190.00  0.2% __local_bh_enable             2434.00  0.3% update_curr_rt
             1904.00  0.2% rcu_idle_exit_common          2161.00  0.2% hrtimer_interrupt
             1870.00  0.2% clockevents_program_event     2106.00  0.2% ktime_get_update_offsets
             1828.00  0.2% hrtimer_interrupt             1766.00  0.2% tick_nohz_idle_exit
             1741.00  0.2% do_nanosleep                  1608.00  0.2% __tick_nohz_idle_enter
             1681.00  0.2% sys_clock_nanosleep           1437.00  0.2% do_nanosleep
             1639.00  0.2% pick_next_task_rt             1428.00  0.2% hrtimer_init
             1630.00  0.2% pick_next_task_stop           1320.00  0.1% sched_clock_idle_sleep_event
             1535.00  0.2% _raw_spin_unlock_irqrestore   1290.00  0.1% sys_clock_nanosleep
#23 lore raw
Quoted 8 lines · Mike Galbraith
Quoted 2 lines · Rik van Riel

Please let me know if you manage to break this code in any way, so I can fix it...

I didn't break it, but did let it play with rq->lock contention. Using cyclictest -Smp99 -i 100 -d 0, with 3 rt tasks for pull_rt_task() to pull around appears to have been a ~dead heat.

Good to hear that the code seems to be robust. It seems to help prevent performance degradation in some workloads, and nobody seems to have found regressions yet.

Thank you for testing.

#24 lore raw
Quoted 6 lines · Rik van Riel
Quoted 5 lines · Mike Galbraith
Quoted 2 lines · Rik van Riel

Please let me know if you manage to break this code in any way, so I can fix it...

Quoted 7 lines
Quoted 3 lines

I didn't break it, but did let it play with rq->lock contention. Using cyclictest -Smp99 -i 100 -d 0, with 3 rt tasks for pull_rt_task() to pull around appears to have been a ~dead heat.

Good to hear that the code seems to be robust. It seems to help prevent performance degradation in some workloads, and nobody seems to have found regressions yet.

I had hoped for a bit of positive, but a wash isn't surprising given the profile. I tried tbench too, didn't expect to see anything at all there, and got that.. so both results are positive in that respect.

-Mike

#25 lore raw
Quoted 11 lines · Mike Galbraith
Quoted 10 lines · Rik van Riel
Quoted 8 lines · Mike Galbraith
Quoted 2 lines · Rik van Riel

Please let me know if you manage to break this code in any way, so I can fix it...

I didn't break it, but did let it play with rq->lock contention. Using cyclictest -Smp99 -i 100 -d 0, with 3 rt tasks for pull_rt_task() to pull around appears to have been a ~dead heat.

Quoted 8 lines
Quoted 3 lines

Good to hear that the code seems to be robust. It seems to help prevent performance degradation in some workloads, and nobody seems to have found regressions yet.

I had hoped for a bit of positive, but a wash isn't surprising given the profile. I tried tbench too, didn't expect to see anything at all there, and got that.. so both results are positive in that respect.

Ok, that's good.

Rik, mind re-sending the latest series with all the acks and Reviewed-by's added?

Thanks,

Ingo

#26 lore raw
In reply to Rik van Riel

On 1/8/2013 2:26 PM, Rik van Riel wrote:
<...>

Quoted 6 lines

Performance is within the margin of error of v2, so the graph has not been update.

Please let me know if you manage to break this code in any way, so I can fix it...

Attached below is some preliminary data with one of the AIM7 micro-benchmark workloads (i.e. high_systime). This is a kernel intensive workload which does tons of forks/execs etc.and stresses quite a few of the same set of spinlocks and semaphores.

Observed a drop in performance as we go to 40way and 80 way. Wondering if the back off keeps increasing to such an extent that it actually starts to hurt given the nature of this workload ? Also in the case of 80way observed quite a bit of variation from run to run...

Also ran it inside a single KVM guest. There were some perf. dips but interestingly didn't observe the same level of drop (compared to the drop in the native case) as the guest size was scaled up to 40vcpu or 80vcpu.

FYI
Vinod

---

Platform : 8 socket (80 Core) Westmere with 1TB RAM.

Workload: AIM7-highsystime microbenchmark - 2000 users & 100 jobs per user.

Values reported are Jobs Per Minute (Higher is better). The values are average of 3 runs.

1) Native run:
--------------

Config 1:  3.7 kernel
Config 2:  3.7 + Rik's 1-4 patches

------------------------------------------------------------
20way 40way 80way
------------------------------------------------------------
Config 1 ~179K ~159K ~146K
------------------------------------------------------------
Config 2 ~180K ~134K ~21K-43K <- high variation!
------------------------------------------------------------

(Note: Used numactl to restrict workload to

            2 sockets (20way) and 4 sockets(40way))

------

2) KVM run :
------------

Single guest of different sizes (No over commit, NUMA enabled in the guest).

Note: This kernel intensive micro benchmark is exposes the PLE handler issue
esp. for large guests. Since Raghu's PLE changes are not yet in upstream 'have just run with current PLE handler & then by disabling PLE (ple_gap=0).

Config 1 : Host & Guest at 3.7
Config 2 : Host & Guest are at 3.7 + Rik's 1-4 patches

--------------------------------------------------------------------------
20vcpu/128G 40vcpu/256G 80vcpu/512G
(on 2 sockets) (on 4 sockets) (on 8 sockets)
--------------------------------------------------------------------------
Config 1 ~144K ~39K ~10K
--------------------------------------------------------------------------
Config 2 ~143K ~37.5K ~11K
--------------------------------------------------------------------------

Config 3 : Host & Guest at 3.7 AND ple_gap=0
Config 4 : Host & Guest are at 3.7 + Rik's 1-4 patches AND ple_gap=0

--------------------------------------------------------------------------
Config 3 ~154K ~131K ~116K
--------------------------------------------------------------------------
Config 4 ~151K ~130K ~115K
--------------------------------------------------------------------------

(Note: Used numactl to restrict qemu to

            2 sockets (20way) and 4 sockets(40way))