qspinlock: Improve performance by reducing load instruction rollback

From: Ma Ling <[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1			mov [ _x], 1  //M3
mov r2, [ _x]  //M2			mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load instructions to be serialization, the destination operand receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

From: Ma Ling <[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1			mov [ _x], 1  //M3
mov r2, [ _x]  //M2			mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load instructions to be serialization, the destination operand receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

Signed-off-by Ma Ling <[email protected]>

---
 kernel/locking/qspinlock.c |   43 ++++++++++++++++++-------------------------
 1 files changed, 18 insertions(+), 25 deletions(-)

kernel/locking/qspinlock.c +0 -0

index 87e9ce6..16421f2 100644

kernel/locking/qspinlock.c +1 -11

 		cpu_relax();
-
-	/*
-	 * take ownership and clear the pending bit.
-	 *
-	 * *,1,0 -> *,0,1
-	 */
-	clear_pending_set_locked(lock);
+
 	return;
 
 	/*

@@ -399,17 +388,21 @@ queue:
 	 * we're at the head of the waitqueue, wait for the owner & pending to
 	 * go away.
 	 *
-	 * *,x,y -> *,0,0
-	 *
-	 * this wait loop must use a load-acquire such that we match the
-	 * store-release that clears the locked bit and create lock

kernel/locking/qspinlock.c +9 -1

+		next = READ_ONCE(node->next);
 		cpu_relax();
+	}
+
+	if (next)
+		goto next_node;
+
+	val = smp_load_acquire(&lock->val.counter);
+	tail = tail | _Q_LOCKED_VAL;
 
 	/*
 	 * claim the lock:

@@ -423,7 +416,6 @@ queue:
 	 */
 	for (;;) {
 		if (val != tail) {
-			set_locked(lock);
 			break;
 		}
 		old = atomic_cmpxchg(&lock->val, val, _Q_LOCKED_VAL);

@@ -439,6 +431,7 @@ queue:
 	while (!(next = READ_ONCE(node->next)))
 		cpu_relax();
 
+next_node:
 	arch_mcs_spin_unlock_contended(&next->locked);
 	pv_kick_node(lock, next);
 

Signature · 1 line

1.7.1

Quoted 26 lines · * [email protected] <[email protected]> wrote:

From: Ma Ling <[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1			mov [ _x], 1  //M3
mov r2, [ _x]  //M2			mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load instructions to be serialization, the destination operand receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Quoted 3 lines

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

So it would be nice to create a new user-space spinlock testing facility, via a new 'perf bench spinlock' feature or so. That way others can test and validate your results on different hardware as well.

From: Ma Ling <[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1			mov [ _x], 1  //M3
mov r2, [ _x]  //M2			mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load

instructions to be serialization,

the destination operand
receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

Quoted 33 lines · Ingo Molnar

Quoted 29 lines · * [email protected] <[email protected]> wrote:

From: Ma Ling <[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1			mov [ _x], 1  //M3
mov r2, [ _x]  //M2			mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load instructions to be serialization, the destination operand receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

Quoted 3 lines

So it would be nice to create a new user-space spinlock testing facility, via a new 'perf bench spinlock' feature or so. That way others can test and validate your results on different hardware as well.

So its trivial to lift this code into userspace -- in fact, I have that somewhere.

The trouble is going to keep them in sync.

From: Ma Ling<[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1			mov [ _x], 1  //M3
mov r2, [ _x]  //M2			mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load instructions to be serialization, the destination operand receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

Thanks
Ling

Signed-off-by Ma Ling<[email protected]>

---
  kernel/locking/qspinlock.c |   43 ++++++++++++++++++-------------------------
  1 files changed, 18 insertions(+), 25 deletions(-)

kernel/locking/qspinlock.c +5 -19

index 87e9ce6..16421f2 100644
@@ -332,25 +332,14 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
  	if (new == _Q_LOCKED_VAL)
  		return;
 
-	/*
-	 * we're pending, wait for the owner to go away.
-	 *
-	 * *,1,1 ->  *,1,0
+	/* we're waiting, and get lock owner
  	 *
-	 * this wait loop must be a load-acquire such that we match the
-	 * store-release that clears the locked bit and create lock
-	 * sequentiality; this is because not all clear_pending_set_locked()
-	 * implementations imply full barriers.
+	 * *,1,* ->  *,0,1
  	 */
-	while ((val = smp_load_acquire(&lock->val.counter))&  _Q_LOCKED_MASK)
+	while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending,
+		_Q_PENDING_VAL, _Q_LOCKED_VAL) != _Q_PENDING_VAL)
  		cpu_relax();
-
-	/*
-	 * take ownership and clear the pending bit.
-	 *
-	 * *,1,0 ->  *,0,1
-	 */
-	clear_pending_set_locked(lock);
+
  	return;
 
  	/*

@@ -399,17 +388,21 @@ queue:
  	 * we're at the head of the waitqueue, wait for the owner&  pending to
  	 * go away.
  	 *
-	 * *,x,y ->  *,0,0
-	 *
-	 * this wait loop must use a load-acquire such that we match the

kernel/locking/qspinlock.c +4 -1

+
+	val = smp_load_acquire(&lock->val.counter);
+	tail = tail | _Q_LOCKED_VAL;
 
  	/*
  	 * claim the lock:

@@ -423,7 +416,6 @@ queue:
  	 */
  	for (;;) {
  		if (val != tail) {
-			set_locked(lock);
  			break;
  		}
  		old = atomic_cmpxchg(&lock->val, val, _Q_LOCKED_VAL);

@@ -439,6 +431,7 @@ queue:
  	while (!(next = READ_ONCE(node->next)))
  		cpu_relax();
 
+next_node:
  	arch_mcs_spin_unlock_contended(&next->locked);
  	pv_kick_node(lock, next);
 

Quoted 26 lines · On Mon, Oct 19, 2015 at 10:27:22AM +0800, [email protected] wrote:

From: Ma Ling<[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1			mov [ _x], 1  //M3
mov r2, [ _x]  //M2			mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load instructions to be serialization, the destination operand receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Quoted 3 lines

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

On what hardware? Also, you forgot to Cc Waiman, who is a prime author of this code. Excessive quoting for his benefit.

Quoted 32 lines · Peter Zijlstra

Quoted 31 lines · Ingo Molnar

Quoted 29 lines · * [email protected]<[email protected]> wrote:

From: Ma Ling<[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1			mov [ _x], 1  //M3
mov r2, [ _x]  //M2			mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load instructions to be serialization, the destination operand receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

Quoted 7 lines

Quoted 3 lines

So it would be nice to create a new user-space spinlock testing facility, via a new 'perf bench spinlock' feature or so. That way others can test and validate your results on different hardware as well.

So its trivial to lift this code into userspace -- in fact, I have that somewhere.

The trouble is going to keep them in sync.

So we can just try this optimistically, and if it keeps breaking, we can use the technique perf uses to sync up the rbtree implementation: we copy the kernel version into tooling, but run diff against the kernel version and warn at tool build time that there's divergence.

I.e. a non-build-fatal force that keeps things in sync.

Thanks,

Ingo

So it would be nice to create a new user-space spinlock testing facility, via a new 'perf bench spinlock' feature or so. That way others can test and validate your results on different hardware as well.

Quoted 26 lines

From: Ma Ling <[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1                   mov [ _x], 1  //M3
mov r2, [ _x]  //M2                   mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load instructions to be serialization, the destination operand receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Quoted 3 lines

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

On what hardware? Also, you forgot to Cc Waiman, who is a prime author of this code. Excessive quoting for his benefit.

Quoted 13 lines

Signed-off-by Ma Ling <[email protected]>

---
 kernel/locking/qspinlock.c |   43 ++++++++++++++++++-------------------------
 1 files changed, 18 insertions(+), 25 deletions(-)

kernel/locking/qspinlock.c +0 -0

index 87e9ce6..16421f2 100644
@@ -332,25 +332,14 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
      if (new == _Q_LOCKED_VAL)
              return;
 

kernel/locking/qspinlock.c void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) · line 335

Quoted 5 lines

kernel/locking/qspinlock.c +1 -4

-     /*
-      * we're pending, wait for the owner to go away.
-      *
-      * *,1,1 -> *,1,0
+     /* we're waiting, and get lock owner

That's incorrect coding style

kernel/locking/qspinlock.c void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) · line 340

Quoted 11 lines

kernel/locking/qspinlock.c +3 -5

       *
-      * this wait loop must be a load-acquire such that we match the
-      * store-release that clears the locked bit and create lock
-      * sequentiality; this is because not all clear_pending_set_locked()
-      * implementations imply full barriers.
+      * *,1,* -> *,0,1
       */
-     while ((val = smp_load_acquire(&lock->val.counter)) & _Q_LOCKED_MASK)
+     while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending,
+             _Q_PENDING_VAL, _Q_LOCKED_VAL) != _Q_PENDING_VAL)

That's both horrible coding style and painful, we should not spin-wait with a cmpxchg instruction like that.

Quoted 21 lines

kernel/locking/qspinlock.c +1 -11

              cpu_relax();
-
-     /*
-      * take ownership and clear the pending bit.
-      *
-      * *,1,0 -> *,0,1
-      */
-     clear_pending_set_locked(lock);
+
      return;
 
      /*

@@ -399,17 +388,21 @@ queue:
       * we're at the head of the waitqueue, wait for the owner & pending to
       * go away.
       *
-      * *,x,y -> *,0,0
-      *
-      * this wait loop must use a load-acquire such that we match the
-      * store-release that clears the locked bit and create lock

kernel/locking/qspinlock.c queue: · line 396

Quoted 10 lines

kernel/locking/qspinlock.c +4 -4

-      * sequentiality; this is because the set_locked() function below
-      * does not imply a full barrier.
-      *
+      * *,x,y -> *,0,1
       */
      pv_wait_head(lock, node);
-     while ((val = smp_load_acquire(&lock->val.counter)) & _Q_LOCKED_PENDING_MASK)
+     next = READ_ONCE(node->next);
+     while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending, 0,
+             _Q_LOCKED_VAL) != 0) {

idem

Quoted 31 lines

kernel/locking/qspinlock.c +9 -2

+             next = READ_ONCE(node->next);
              cpu_relax();
+     }
+
+     if (next)
+             goto next_node;
+
+     val = smp_load_acquire(&lock->val.counter);
+     tail = tail | _Q_LOCKED_VAL;
 
      /*
       * claim the lock:

@@ -423,7 +416,6 @@ queue:
       */
      for (;;) {
              if (val != tail) {
-                     set_locked(lock);
                      break;
              }
              old = atomic_cmpxchg(&lock->val, val, _Q_LOCKED_VAL);

@@ -439,6 +431,7 @@ queue:
      while (!(next = READ_ONCE(node->next)))
              cpu_relax();
 
+next_node:
      arch_mcs_spin_unlock_contended(&next->locked);
      pv_kick_node(lock, next);
 
--

1.7.1

Quoted 13 lines

From: Ma Ling <[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1                   mov [ _x], 1  //M3
mov r2, [ _x]  //M2                   mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

Quoted 8 lines

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load

"lock cmpxchg" makes me think you're working on x86.

Quoted 1 line

instructions to be serialization,

smp_rmb() does that, and that's 'free' on x86. Because x86 doesn't do read reordering.

Quoted 4 lines

the destination operand
receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

And that makes me think I'm not understanding what you're getting at. If you need to force memory order, a "fence" (or smp_mb()) would still be cheaper than endlessly pulling the line into exclusive state for no reason, right?

Quoted 3 lines

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

That just doesn't parse, what?

Quoted 27 lines

From: Ma Ling<[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1                     mov [ _x], 1  //M3
mov r2, [ _x]  //M2                     mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load instructions to be serialization, the destination operand receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Quoted 3 lines

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

What kind of performance test were you running? With the right timing, it is possible that you see some performance gain. However, if the lock hold time is longer so that a fair number of cmpxchg instructions have to be executed before it can get the lock, you may see a performance degradation especially if the lock holder needs to access the lock cacheline.

In general, we try to avoid this kind of cmpxchg loop unless we are sure that at most a few iterations of the loop may happen.

Quoted 66 lines

Thanks
Ling

Signed-off-by Ma Ling<[email protected]>

---
  kernel/locking/qspinlock.c |   43
++++++++++++++++++-------------------------
  1 files changed, 18 insertions(+), 25 deletions(-)

kernel/locking/qspinlock.c +5 -16

index 87e9ce6..16421f2 100644
@@ -332,25 +332,14 @@ void queued_spin_lock_slowpath(struct qspinlock
 *lock, u32 val)
        if (new == _Q_LOCKED_VAL)
                return;
 
-       /*
-        * we're pending, wait for the owner to go away.
-        *
-        * *,1,1 ->  *,1,0
+       /* we're waiting, and get lock owner
         *
-        * this wait loop must be a load-acquire such that we match the
-        * store-release that clears the locked bit and create lock
-        * sequentiality; this is because not all
 clear_pending_set_locked()
-        * implementations imply full barriers.
+        * *,1,* ->  *,0,1
         */
-       while ((val = smp_load_acquire(&lock->val.counter))&
 _Q_LOCKED_MASK)
+       while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending,
+               _Q_PENDING_VAL, _Q_LOCKED_VAL) != _Q_PENDING_VAL)
                cpu_relax();
-
-       /*
-        * take ownership and clear the pending bit.
-        *
-        * *,1,0 ->  *,0,1
-        */
-       clear_pending_set_locked(lock);
+

        return;

        /*

kernel/locking/qspinlock.c +0 -0

@@ -399,17 +388,21 @@ queue:
         * we're at the head of the waitqueue, wait for the owner&

pending to
* go away.
*

kernel/locking/qspinlock.c +1 -8

-        * *,x,y ->  *,0,0
-        *
-        * this wait loop must use a load-acquire such that we match the
-        * store-release that clears the locked bit and create lock
-        * sequentiality; this is because the set_locked() function below
-        * does not imply a full barrier.
-        *
+        * *,x,y ->  *,0,1
         */
        pv_wait_head(lock, node);
-       while ((val = smp_load_acquire(&lock->val.counter))&

_Q_LOCKED_PENDING_MASK)

kernel/locking/qspinlock.c queue: · line 395

Quoted 2 lines

kernel/locking/qspinlock.c +2 -0

+       next = READ_ONCE(node->next);
+       while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending, 0,

The locked_pending field isn't valid if _Q_PENDING_BITS != 8. So it won't work if NR_CPUS is 16k or more.

kernel/locking/qspinlock.c queue: · line 402

Quoted 7 lines

kernel/locking/qspinlock.c +6 -0

+               _Q_LOCKED_VAL) != 0) {
+               next = READ_ONCE(node->next);
                cpu_relax();
+       }
+
+       if (next)
+               goto next_node;

I did notice a slight performance benefit by reading the next pointer early in light load cases myself. However, it is a very minor improvement that I haven't actively pursued it.

Quoted 23 lines

kernel/locking/qspinlock.c +4 -1

+
+       val = smp_load_acquire(&lock->val.counter);
+       tail = tail | _Q_LOCKED_VAL;
 
        /*
         * claim the lock:

@@ -423,7 +416,6 @@ queue:
         */
        for (;;) {
                if (val != tail) {
-                       set_locked(lock);
                        break;
                }
                old = atomic_cmpxchg(&lock->val, val, _Q_LOCKED_VAL);

@@ -439,6 +431,7 @@ queue:
        while (!(next = READ_ONCE(node->next)))
                cpu_relax();
 
+next_node:
        arch_mcs_spin_unlock_contended(&next->locked);
        pv_kick_node(lock, next);
 

Quoted 13 lines

From: Ma Ling <[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1                   mov [ _x], 1  //M3
mov r2, [ _x]  //M2                   mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

Quoted 8 lines

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load

"lock cmpxchg" makes me think you're working on x86.

Quoted 1 line

instructions to be serialization,

smp_rmb() does that, and that's 'free' on x86. Because x86 doesn't do read reordering.

Quoted 4 lines

the destination operand
receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

And that makes me think I'm not understanding what you're getting at. If you need to force memory order, a "fence" (or smp_mb()) would still be cheaper than endlessly pulling the line into exclusive state for no reason, right?

Quoted 4 lines

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

That just doesn't parse, what?

Quoted 3 lines

So it would be nice to create a new user-space spinlock testing facility, via a new 'perf bench spinlock' feature or so. That way others can test and validate your results on different hardware as well.

Attached the spinlock test module . Queued spinlock will run very slowly in user space because process switch context, it is OK for spinlock-test implementation with kernel module ?

Quoted 5 lines

So it would be nice to create a new user-space spinlock testing facility, via a new 'perf bench spinlock' feature or so. That way others can test and validate your results on different hardware as well.

Attached the spinlock test module . Queued spinlock will run very slowly in user space
because process switch context, it is OK for spinlock-test implementation with kernel module ?

2015-10-19 17:46 GMT+08:00 Peter Zijlstra <[email protected]>:

Quoted 35 lines · On Mon, Oct 19, 2015 at 10:27:22AM +0800, [email protected] wrote:

Quoted 13 lines

From: Ma Ling <[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1                   mov [ _x], 1  //M3
mov r2, [ _x]  //M2                   mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

Quoted 8 lines

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load

"lock cmpxchg" makes me think you're working on x86.

Quoted 1 line

instructions to be serialization,

smp_rmb() does that, and that's 'free' on x86. Because x86 doesn't do read reordering.

Quoted 4 lines

the destination operand
receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Quoted 4 lines

And that makes me think I'm not understanding what you're getting at. If you need to force memory order, a "fence" (or smp_mb()) would still be cheaper than endlessly pulling the line into exclusive state for no reason, right?

Peter,

we tested instruction lfence, but we hard to see any benefit, lfence only force load instruction ,
but load instruction still will rollback ,actually cmpxchg behavior is more like write operation,
so we choose it.

2015-10-20 1:18 GMT+08:00 Waiman Long<[email protected]>:

Quoted 31 lines · On 10/18/2015 10:27 PM, [email protected] wrote:

Quoted 26 lines

From: Ma Ling<[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1                     mov [ _x], 1  //M3
mov r2, [ _x]  //M2                     mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load instructions to be serialization, the destination operand receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Quoted 3 lines

Our experiment indicates the performance can be improved by 10%~15% for 2 and 3 threads cases, the conflicts from lock cache line spend them most of the time.

Quoted 8 lines

What kind of performance test were you running? With the right timing, it is possible that you see some performance gain. However, if the lock hold time is longer so that a fair number of cmpxchg instructions have to be executed before it can get the lock, you may see a performance degradation especially if the lock holder needs to access the lock cacheline.

In general, we try to avoid this kind of cmpxchg loop unless we are sure that at most a few iterations of the loop may happen.

Waiman,

The machine is Haswell (2699 V3, COD off, HT on, 2 sockets) (we have sent test module in separate email)

A. Data is located with lock in one cache line On 2 threads cases
(only write struct member data_a)

1. Load version test 5 times, the cost time is below:

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 103904620

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 104351876

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 118599784

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 103064024

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 103389696

Totally cost time is 533310000

2. Lock cmpxchg version test 5 times, the cost time is below:

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 67081220

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 97640708

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 96439612

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 66699296

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 96464800

Totally cost time is 424325636

Above data shows lock cmpxchg is better about average 25% (533310000/424325636)

B. Data is located with lock in different cache line On 2 threads
cases(only write struct member data_b)

1. Load version test 5 times, the cost time is below:

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 174266128

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 205053924

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 160165124

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 173241552

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 205765008

Totally cost time is 918491736

2. Lock cmpxchg version test 5 times, the cost time is below:

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 113410044

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 116293104

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 116064256

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 189320876

[root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c

all cost time is 123735352

Totally cost time is 658823632

Above data shows lock cmpxchg is better about average 39% (918491736/658823632)

Quoted 8 lines

Quoted 4 lines

So it would be nice to create a new user-space spinlock testing facility, via a new 'perf bench spinlock' feature or so. That way others can test and validate your results on different hardware as well.

Attached the spinlock test module . Queued spinlock will run very slowly in user space because process switch context, it is OK for spinlock-test implementation with kernel module ?

Not sure what you mean by 'because process switch context': if you pin the test tasks to individual CPUs and make sure there's nothing else running it should be equivalent to kernel-space execution.

Thanks,

Ingo

Quoted 41 lines

2015-10-19 17:46 GMT+08:00 Peter Zijlstra <[email protected]>:

Quoted 35 lines · On Mon, Oct 19, 2015 at 10:27:22AM +0800, [email protected] wrote:

Quoted 13 lines

From: Ma Ling <[email protected]>

All load instructions can run speculatively but they have to follow memory order rule in multiple cores as below:
_x = _y = 0

Processor 0 Processor 1

mov r1, [ _y]  //M1                   mov [ _x], 1  //M3
mov r2, [ _x]  //M2                   mov [ _y], 1  //M4

If r1 = 1, r2 must be 1

Quoted 8 lines

In order to guarantee above rule, although Processor 0 execute M1 and M2 instruction out of order, they are kept in ROB, when load buffer for _x in Processor 0 received the update message from Processor 1, Processor 0 need to roll back from M2 instruction, which will flush the whole pipeline, the latency is over the penalty from branch prediction miss.

In this patch we use lock cmpxchg instruction to force load

"lock cmpxchg" makes me think you're working on x86.

Quoted 1 line

instructions to be serialization,

smp_rmb() does that, and that's 'free' on x86. Because x86 doesn't do read reordering.

Quoted 4 lines

the destination operand
receives a write cycle without regard to the result of the comparison, which can help us to reduce the penalty from load instruction roll back.

Quoted 4 lines

And that makes me think I'm not understanding what you're getting at. If you need to force memory order, a "fence" (or smp_mb()) would still be cheaper than endlessly pulling the line into exclusive state for no reason, right?

Quoted 7 lines

Peter,

we tested instruction lfence, but we hard to see any benefit, lfence only force load instruction ,
but load instruction still will rollback ,actually cmpxchg behavior is more like write operation,
so we choose it.

But why? I'm just not getting this.

Also LOCK CMPXCHG is 24 cycles when hot, that's almost as bad as a pipeline flush, and it can be many times worse when it needs to actually fetch memory from further than L1.

I did see some performance improvement when I used your test program on a Haswell-EX system. It seems like the use of cmpxchg has forced the changed memory values to be visible to other processors earlier. I also ran your test on an older machine with Westmere-EX processors. This time, I didn't see any performance improvement. In fact, your change actually make it a tiny bit slower. So the benefit of your patch can be highly processor sensitive.

As other architectures like ARM & AA64 are going to adopt qspinlock in the near future, we will also need to make sure that it won't cause a regression there. So I don't see your patch has a big chance of being merged upstream unless you can provide a real world workload that can benefit from your patch. Even then, proving that it won't cause regression in other processors or architectures can be tedious.

Ok, we will put the spinlock test into the perf bench.