locking/pvqspinlock: Relax cmpxchg's to improve performance on some archs

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

Signed-off-by Waiman Long <[email protected]>

v1->v2:
- Add comments in changelog and code for the rationale of the change.

---
 kernel/locking/qspinlock_paravirt.h | 50 ++++++++++++++++++++++++-------------
 1 file changed, 33 insertions(+), 17 deletions(-)

kernel/locking/qspinlock_paravirt.h +6 -6

index e3b5520..c31d1ab 100644
@@ -72,7 +72,7 @@ static inline bool pv_queued_spin_steal_lock(struct qspinlock *lock)
 	struct __qspinlock *l = (void *)lock;
 
 	if (!(atomic_read(&lock->val) & _Q_LOCKED_PENDING_MASK) &&
-	    (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0)) {
+	    (cmpxchg_acquire(&l->locked, 0, _Q_LOCKED_VAL) == 0)) {
 		qstat_inc(qstat_pv_lock_stealing, true);
 		return true;
 	}

@@ -101,16 +101,16 @@ static __always_inline void clear_pending(struct qspinlock *lock)
 
 /*
  * The pending bit check in pv_queued_spin_steal_lock() isn't a memory
- * barrier. Therefore, an atomic cmpxchg() is used to acquire the lock
- * just to be sure that it will get it.
+ * barrier. Therefore, an atomic cmpxchg_acquire() is used to acquire the
+ * lock to provide the proper memory barrier.
  */
 static __always_inline int trylock_clear_pending(struct qspinlock *lock)
 {
 	struct __qspinlock *l = (void *)lock;
 
 	return !READ_ONCE(l->locked) &&
-	       (cmpxchg(&l->locked_pending, _Q_PENDING_VAL, _Q_LOCKED_VAL)
-			== _Q_PENDING_VAL);
+	       (cmpxchg_acquire(&l->locked_pending, _Q_PENDING_VAL,
+				_Q_LOCKED_VAL) == _Q_PENDING_VAL);
 }
 #else /* _Q_PENDING_BITS == 8 */
 static __always_inline void set_pending(struct qspinlock *lock)

@@ -138,7 +138,7 @@ static __always_inline int trylock_clear_pending(struct qspinlock *lock)
 		 */
 		old = val;
 		new = (val & ~_Q_PENDING_MASK) | _Q_LOCKED_VAL;
-		val = atomic_cmpxchg(&lock->val, old, new);
+		val = atomic_cmpxchg_acquire(&lock->val, old, new);
 
 		if (val == old)
 			return 1;

kernel/locking/qspinlock_paravirt.h +21 -11

 	for_each_hash_entry(he, offset, hash) {
 		hopcnt++;
-		if (!cmpxchg(&he->lock, NULL, lock)) {
+		if (!cmpxchg_relaxed(&he->lock, NULL, lock)) {
 			WRITE_ONCE(he->node, node);
 			qstat_hop(hopcnt);
 			return &he->lock;

@@ -309,7 +315,7 @@ static void pv_wait_node(struct mcs_spinlock *node, struct mcs_spinlock *prev)
 		 *     MB			      MB
 		 * [L] pn->locked		[RmW] pn->state = vcpu_hashed
 		 *
-		 * Matches the cmpxchg() from pv_kick_node().
+		 * Matches the cmpxchg_release() from pv_kick_node().
 		 */
 		smp_store_mb(pn->state, vcpu_halted);
 

@@ -323,8 +329,14 @@ static void pv_wait_node(struct mcs_spinlock *node, struct mcs_spinlock *prev)
 		 * If pv_kick_node() changed us to vcpu_hashed, retain that
 		 * value so that pv_wait_head_or_lock() knows to not also try
 		 * to hash this lock.
+		 *
+		 * The smp_store_mb() and control dependency above will ensure
+		 * that state change won't happen before that. Synchronizing
+		 * with pv_kick_node() wrt hashing by this waiter or by the
+		 * lock holder is done solely by the state variable. There is
+		 * no other ordering requirement.
 		 */
-		cmpxchg(&pn->state, vcpu_halted, vcpu_running);
+		cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_running);
 
 		/*
 		 * If the locked flag is still not set after wakeup, it is a

@@ -360,9 +372,12 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
 	 * pv_wait_node(). If OTOH this fails, the vCPU was running and will
 	 * observe its next->locked value and advance itself.
 	 *
-	 * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
+	 * Matches with smp_store_mb() and cmpxchg_relaxed() in pv_wait_node().
+	 * A release barrier is used here to ensure that node->locked is
+	 * always set before changing the state. See comment in pv_wait_node().
 	 */
-	if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
+	if (cmpxchg_release(&pn->state, vcpu_halted, vcpu_hashed)
+			!= vcpu_halted)
 		return;
 
 	/*

@@ -461,8 +476,8 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
 	}
 
 	/*
-	 * The cmpxchg() or xchg() call before coming here provides the
-	 * acquire semantics for locking. The dummy ORing of _Q_LOCKED_VAL
+	 * The cmpxchg_acquire() or xchg() call before coming here provides
+	 * the acquire semantics for locking. The dummy ORing of _Q_LOCKED_VAL
 	 * here is to indicate to the compiler that the value will always
 	 * be nozero to enable better code optimization.
 	 */

@@ -488,11 +503,12 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
 	}
 
 	/*
-	 * A failed cmpxchg doesn't provide any memory-ordering guarantees,
-	 * so we need a barrier to order the read of the node data in
-	 * pv_unhash *after* we've read the lock being _Q_SLOW_VAL.
+	 * A failed cmpxchg_release doesn't provide any memory-ordering
+	 * guarantees, so we need a barrier to order the read of the node
+	 * data in pv_unhash *after* we've read the lock being _Q_SLOW_VAL.
 	 *
-	 * Matches the cmpxchg() in pv_wait_head_or_lock() setting _Q_SLOW_VAL.
+	 * Matches the cmpxchg_acquire() in pv_wait_head_or_lock() setting
+	 * _Q_SLOW_VAL.
 	 */
 	smp_rmb();
 

Signature · 1 line

1.8.3.1

Hi Wainman,

Quoted 64 lines · Waiman Long

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

Signed-off-by Waiman Long <[email protected]>

v1->v2:
- Add comments in changelog and code for the rationale of the change.

---
 kernel/locking/qspinlock_paravirt.h | 50 ++++++++++++++++++++++++-------------
 1 file changed, 33 insertions(+), 17 deletions(-)

kernel/locking/qspinlock_paravirt.h +6 -6

index e3b5520..c31d1ab 100644
@@ -72,7 +72,7 @@ static inline bool pv_queued_spin_steal_lock(struct qspinlock *lock)
 	struct __qspinlock *l = (void *)lock;
 
 	if (!(atomic_read(&lock->val) & _Q_LOCKED_PENDING_MASK) &&
-	    (cmpxchg(&l->locked, 0, _Q_LOCKED_VAL) == 0)) {
+	    (cmpxchg_acquire(&l->locked, 0, _Q_LOCKED_VAL) == 0)) {
 		qstat_inc(qstat_pv_lock_stealing, true);
 		return true;
 	}

@@ -101,16 +101,16 @@ static __always_inline void clear_pending(struct qspinlock *lock)
 
 /*
  * The pending bit check in pv_queued_spin_steal_lock() isn't a memory
- * barrier. Therefore, an atomic cmpxchg() is used to acquire the lock
- * just to be sure that it will get it.
+ * barrier. Therefore, an atomic cmpxchg_acquire() is used to acquire the
+ * lock to provide the proper memory barrier.
  */
 static __always_inline int trylock_clear_pending(struct qspinlock *lock)
 {
 	struct __qspinlock *l = (void *)lock;
 
 	return !READ_ONCE(l->locked) &&
-	       (cmpxchg(&l->locked_pending, _Q_PENDING_VAL, _Q_LOCKED_VAL)
-			== _Q_PENDING_VAL);
+	       (cmpxchg_acquire(&l->locked_pending, _Q_PENDING_VAL,
+				_Q_LOCKED_VAL) == _Q_PENDING_VAL);
 }
 #else /* _Q_PENDING_BITS == 8 */
 static __always_inline void set_pending(struct qspinlock *lock)

@@ -138,7 +138,7 @@ static __always_inline int trylock_clear_pending(struct qspinlock *lock)
 		 */
 		old = val;
 		new = (val & ~_Q_PENDING_MASK) | _Q_LOCKED_VAL;
-		val = atomic_cmpxchg(&lock->val, old, new);
+		val = atomic_cmpxchg_acquire(&lock->val, old, new);
 
 		if (val == old)
 			return 1;

kernel/locking/qspinlock_paravirt.h static struct qspinlock **pv_hash(struct qspinlock *lock, struct pv_node *node) · line 217

Quoted 9 lines

kernel/locking/qspinlock_paravirt.h +6 -0

@@ -209,9 +209,15 @@ static struct qspinlock **pv_hash(struct qspinlock *lock, struct pv_node *node)
 	struct pv_hash_entry *he;
 	int hopcnt = 0;
 
+	/*
+	 * Synchronizing with the node state variable will control who does
+	 * the hashing - the lock holder or lock waiter. The control
+	 * dependency will ensure that node value is written after the lock
+	 * value. So we don't need other ordering guarantee.
+	 */

By this comment, you mean that

	cmpxchg_relaxed(&he->lock, NULL, lock);
	  r1 = ll he->lock;
	  <compare part>
	  sc he->lock, lock // successed

	if (r1)
		WRITE_ONCE(he->node, node);

the sc and WRITE_ONCE() can not be reordered because of the control dependency? I dont think this is true. Yes the sc must execute before the WRITE_ONCE(), but the memory/cache effects may be reordered. IOW, the following may happen

	CPU 0			CPU 1
	===================	=======================
	{x = 0, y = 0}		if (!cmpxchg_relaxed(&y, 0, 1))
					WRITE_ONCE(x, 1);
	r1 = READ_ONCE(x);

	smp_rmb();

	r2 = READ_ONCE(y);

The following result is possible:

	y = 1 && r1 = 1 && r2 = 0

Or I'm missing your point here? ;-)

Regards,
Boqun

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

Quoted 2 lines · Waiman Long

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

Claim without numbers ;-)

Quoted 4 lines

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

So these seem to make sense in that they're in 'fast' paths..

Quoted 2 lines

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

But these not so much, we're going to put the vcpu to sleep, why does it make sense to 'optimize' the wait/kick stuff?

Quoted 4 lines · Peter Zijlstra

Quoted 2 lines · Waiman Long

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

Claim without numbers ;-)

Well it is hard to produce actual numbers here as I don't have the setup to gather data.

Quoted 4 lines · Waiman Long

Quoted 3 lines · Peter Zijlstra

Quoted 2 lines · Waiman Long

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

Quoted 4 lines

Quoted 1 line

Claim without numbers ;-)

Well it is hard to produce actual numbers here as I don't have the setup to gather data.

Surely RHT has big PPC machines around? I know that getting to them is a wee bit of a bother, but they should be available somewhere.

I do some tests about cmpxchg and cmpxchg_acquire before on ppc.

loops in 15s of each cmpxchg is below.

cmpxchg_relaxed: 336663
cmpxchg_release: 369054
cmpxchg_acquire: 363364
cmpxchg: 179435

so cmpxchg is really expensive than others.
but I also have doubt about the cmpxchg_relaxed, it should be the cheapest, but from the tests, release/acquire are faster than it.

Quoted 5 lines · Peter Zijlstra

Quoted 4 lines · Waiman Long

Quoted 3 lines · Peter Zijlstra

Quoted 2 lines · Waiman Long

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

Quoted 8 lines

Quoted 4 lines

Quoted 1 line

Claim without numbers ;-)

Well it is hard to produce actual numbers here as I don't have the setup to gather data.

Surely RHT has big PPC machines around? I know that getting to them is a wee bit of a bother, but they should be available somewhere.

hi,

I do some tests about cmpxchg and cmpxchg_acquire before on ppc.

loops in 15s of each cmpxchg is below.

cmpxchg_relaxed: 336663
cmpxchg_release: 369054
cmpxchg_acquire: 363364
cmpxchg: 179435

so cmpxchg is really expensive than others.
but I also have doubt about the cmpxchg_relaxed, it should be the cheapest, but from the tests, release/acquire are faster than it.

thanks
xinhui

Quoted 7 lines · Peter Zijlstra

Quoted 6 lines · Waiman Long

Quoted 5 lines · Peter Zijlstra

Quoted 4 lines · Waiman Long

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more
relaxed versions to improve performance on architectures that use LL/SC.

Quoted 9 lines

Quoted 5 lines

Quoted 1 line

Claim without numbers ;-)

Well it is hard to produce actual numbers here as I don't have the setup
to gather data.

Surely RHT has big PPC machines around? I know that getting to them is a wee bit of a bother, but they should be available somewhere.

hi,

I do some tests about cmpxchg and cmpxchg_acquire before on ppc.

loops in 15s of each cmpxchg is below.

cmpxchg_relaxed: 336663
cmpxchg_release: 369054
cmpxchg_acquire: 363364
cmpxchg: 179435

so cmpxchg is really expensive than others.
but I also have doubt about the cmpxchg_relaxed, it should be the cheapest, but from the tests, release/acquire are faster than it.

thanks
xinhui

Quoted 34 lines · Pan Xinhui

Quoted 7 lines · Peter Zijlstra

Quoted 6 lines · Waiman Long

Quoted 5 lines · Peter Zijlstra

Quoted 4 lines · Waiman Long

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more
relaxed versions to improve performance on architectures that use LL/SC.

Quoted 9 lines

Quoted 5 lines

Quoted 1 line

Claim without numbers ;-)

Well it is hard to produce actual numbers here as I don't have the setup
to gather data.

Surely RHT has big PPC machines around? I know that getting to them is a wee bit of a bother, but they should be available somewhere.

hi,

I do some tests about cmpxchg and cmpxchg_acquire before on ppc.

loops in 15s of each cmpxchg is below.

cmpxchg_relaxed: 336663
cmpxchg_release: 369054
cmpxchg_acquire: 363364
cmpxchg: 179435

so cmpxchg is really expensive than others.
but I also have doubt about the cmpxchg_relaxed, it should be the cheapest, but from the tests, release/acquire are faster than it.

Quoted 3 lines

thanks
xinhui

Thanks for doing the test. It looks like we should just focus on using either cmpxchg_release or cmpxchg_acquire and forget about cmpxchg_relaxed.

Cheers,
Longman

Quoted 7 lines · Waiman Long

Quoted 4 lines · Peter Zijlstra

Quoted 2 lines · Waiman Long

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

Claim without numbers ;-)

Well it is hard to produce actual numbers here as I don't have the setup to gather data.

Surely RHT has big PPC machines around? I know that getting to them is a wee bit of a bother, but they should be available somewhere.

2016-12-26 4:26 GMT+08:00 Waiman Long <[email protected]>:

Quoted 62 lines

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

Signed-off-by Waiman Long <[email protected]>

v1->v2:
- Add comments in changelog and code for the rationale of the change.

---
 kernel/locking/qspinlock_paravirt.h | 50 ++++++++++++++++++++++++------
-------
 1 file changed, 33 insertions(+), 17 deletions(-)

(quoted diff) +0 -0

@@ -323,8 +329,14 @@ static void pv_wait_node(struct mcs_spinlock *node,
 struct mcs_spinlock *prev)
                 * If pv_kick_node() changed us to vcpu_hashed, retain that
                 * value so that pv_wait_head_or_lock() knows to not also

try
* to hash this lock.

(quoted diff) +2 -0

+                *
+                * The smp_store_mb() and control dependency above will

ensure
+ * that state change won't happen before that.
Synchronizing

(quoted diff) +2 -0

+                * with pv_kick_node() wrt hashing by this waiter or by the
+                * lock holder is done solely by the state variable. There

is

kernel/locking/qspinlock_paravirt.h +2 -1

+                * no other ordering requirement.
                 */
-               cmpxchg(&pn->state, vcpu_halted, vcpu_running);
+               cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_running);
 
                /*
                 * If the locked flag is still not set after wakeup, it is

a

(quoted diff) +0 -0

@@ -360,9 +372,12 @@ static void pv_kick_node(struct qspinlock *lock,
 struct mcs_spinlock *node)
         * pv_wait_node(). If OTOH this fails, the vCPU was running and

will
* observe its next->locked value and advance itself. *

(quoted diff) +1 -1

-        * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
+        * Matches with smp_store_mb() and cmpxchg_relaxed() in

pv_wait_node().

(quoted diff) +2 -0

+        * A release barrier is used here to ensure that node->locked is
+        * always set before changing the state. See comment in

pv_wait_node().

         */

kernel/locking/qspinlock_paravirt.h +2 -1

-       if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
+       if (cmpxchg_release(&pn->state, vcpu_halted, vcpu_hashed)
+                       != vcpu_halted)
                return;

Quoted 1 line

hi, Waiman

We can't use _release here, a full barrier is needed.

There is pv_kick_node vs pv_wait_head_or_lock

[w] l->locked = _Q_SLOW_VAL //reordered here

if (READ_ONCE(pn->state) == vcpu_hashed) //False.

                   lp = (struct qspinlock **)1;

[STORE] pn->state = vcpu_hashed lp = pv_hash(lock,
pn);
pv_hash() if
(xchg(&l->locked, _Q_SLOW_VAL) == 0) // fasle, not unhashed.

Then the same lock has hashed twice but only unhashed once. So at last as the hash table grows big, we hit RCU stall.

I hit RCU stall when I run netperf benchmark

thanks
xinhui

Quoted 4 lines

--
1.8.3.1

Quoted 75 lines · Xinhui Pan

2016-12-26 4:26 GMT+08:00 Waiman Long <[email protected]>:

Quoted 62 lines

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

Signed-off-by Waiman Long <[email protected]>

v1->v2:
- Add comments in changelog and code for the rationale of the change.

---
 kernel/locking/qspinlock_paravirt.h | 50 ++++++++++++++++++++++++------
-------
 1 file changed, 33 insertions(+), 17 deletions(-)

(quoted diff) +0 -0

@@ -323,8 +329,14 @@ static void pv_wait_node(struct mcs_spinlock *node,
 struct mcs_spinlock *prev)
                 * If pv_kick_node() changed us to vcpu_hashed, retain that
                 * value so that pv_wait_head_or_lock() knows to not also

try
* to hash this lock.

(quoted diff) +2 -0

+                *
+                * The smp_store_mb() and control dependency above will

ensure
+ * that state change won't happen before that.
Synchronizing

(quoted diff) +2 -0

+                * with pv_kick_node() wrt hashing by this waiter or by the
+                * lock holder is done solely by the state variable. There

is

kernel/locking/qspinlock_paravirt.h +2 -1

+                * no other ordering requirement.
                 */
-               cmpxchg(&pn->state, vcpu_halted, vcpu_running);
+               cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_running);
 
                /*
                 * If the locked flag is still not set after wakeup, it is

a

(quoted diff) +0 -0

@@ -360,9 +372,12 @@ static void pv_kick_node(struct qspinlock *lock,
 struct mcs_spinlock *node)
         * pv_wait_node(). If OTOH this fails, the vCPU was running and

will
* observe its next->locked value and advance itself. *

(quoted diff) +1 -1

-        * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
+        * Matches with smp_store_mb() and cmpxchg_relaxed() in

pv_wait_node().

(quoted diff) +2 -0

+        * A release barrier is used here to ensure that node->locked is
+        * always set before changing the state. See comment in

pv_wait_node().

         */

kernel/locking/qspinlock_paravirt.h +2 -1

-       if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
+       if (cmpxchg_release(&pn->state, vcpu_halted, vcpu_hashed)
+                       != vcpu_halted)
                return;

Quoted 1 line

hi, Waiman

We can't use _release here, a full barrier is needed.

There is pv_kick_node vs pv_wait_head_or_lock

[w] l->locked = _Q_SLOW_VAL //reordered here

if (READ_ONCE(pn->state) == vcpu_hashed) //False.

                   lp = (struct qspinlock **)1;

Quoted 5 lines

[STORE] pn->state = vcpu_hashed lp = pv_hash(lock,
pn);
pv_hash() if
(xchg(&l->locked, _Q_SLOW_VAL) == 0) // fasle, not unhashed.

This analysis is correct, but..

Quoted 5 lines

Then the same lock has hashed twice but only unhashed once. So at last as the hash table grows big, we hit RCU stall.

I hit RCU stall when I run netperf benchmark

how will a big hash table hit RCU stall? Do you have the call trace for your RCU stall?

Regards,
Boqun

Quoted 8 lines

thanks
xinhui

Quoted 4 lines

--
1.8.3.1

Quoted 76 lines · Boqun Feng

Quoted 75 lines · Xinhui Pan

2016-12-26 4:26 GMT+08:00 Waiman Long <[email protected]>:

Quoted 62 lines

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

Signed-off-by Waiman Long <[email protected]>

v1->v2:
- Add comments in changelog and code for the rationale of the change.

---
 kernel/locking/qspinlock_paravirt.h | 50 ++++++++++++++++++++++++------
-------
 1 file changed, 33 insertions(+), 17 deletions(-)

(quoted diff) +0 -0

@@ -323,8 +329,14 @@ static void pv_wait_node(struct mcs_spinlock *node,
 struct mcs_spinlock *prev)
                 * If pv_kick_node() changed us to vcpu_hashed, retain that
                 * value so that pv_wait_head_or_lock() knows to not also

try
* to hash this lock.

(quoted diff) +2 -0

+                *
+                * The smp_store_mb() and control dependency above will

ensure
+ * that state change won't happen before that.
Synchronizing

(quoted diff) +2 -0

+                * with pv_kick_node() wrt hashing by this waiter or by the
+                * lock holder is done solely by the state variable. There

is

kernel/locking/qspinlock_paravirt.h +2 -1

+                * no other ordering requirement.
                 */
-               cmpxchg(&pn->state, vcpu_halted, vcpu_running);
+               cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_running);
 
                /*
                 * If the locked flag is still not set after wakeup, it is

a

(quoted diff) +0 -0

@@ -360,9 +372,12 @@ static void pv_kick_node(struct qspinlock *lock,
 struct mcs_spinlock *node)
         * pv_wait_node(). If OTOH this fails, the vCPU was running and

will
* observe its next->locked value and advance itself. *

(quoted diff) +1 -1

-        * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
+        * Matches with smp_store_mb() and cmpxchg_relaxed() in

pv_wait_node().

(quoted diff) +2 -0

+        * A release barrier is used here to ensure that node->locked is
+        * always set before changing the state. See comment in

pv_wait_node().

         */

kernel/locking/qspinlock_paravirt.h +2 -1

-       if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
+       if (cmpxchg_release(&pn->state, vcpu_halted, vcpu_hashed)
+                       != vcpu_halted)
                return;

Quoted 1 line

hi, Waiman

We can't use _release here, a full barrier is needed.

There is pv_kick_node vs pv_wait_head_or_lock

[w] l->locked = _Q_SLOW_VAL //reordered here

if (READ_ONCE(pn->state) == vcpu_hashed) //False.

                   lp = (struct qspinlock **)1;

Quoted 8 lines

Quoted 5 lines

[STORE] pn->state = vcpu_hashed lp = pv_hash(lock,
pn);
pv_hash() if
(xchg(&l->locked, _Q_SLOW_VAL) == 0) // fasle, not unhashed.

This analysis is correct, but..

Hmm.. look at this again, I don't think this analysis is meaningful, let's say the reordering didn't happen, we still got(similar to your case):

						if (READ_ONCE(pn->state) == vcpu_hashed) // false.
						  lp = (struct qspinlock **)1;

cmpxchg(pn->state, vcpu_halted, vcpu_hashed);
						  if(!lp) {
						    lp = pv_hash(lock, pn);
WRITE_ONCE(l->locked, _Q_SLOW_VAL);
pv_hash();
						    if (xchg(&l->locked, _Q_SLOW_VAL) == 0) // fasle, not unhashed.

, right?

Actually, I think this or your case could not happen because we have

	cmpxchg(pn->state, vcpu_halted, vcpu_running);

in pv_wait_node(), which makes us either observe vcpu_hashed or set pn->state to vcpu_running before pv_kick_node() trying to do the hash.

I may miss something subtle, but does switching back to cmpxchg() could fix the RCU stall you observed?

Regards,
Boqun

Quoted 20 lines

Quoted 5 lines

Then the same lock has hashed twice but only unhashed once. So at last as the hash table grows big, we hit RCU stall.

I hit RCU stall when I run netperf benchmark

how will a big hash table hit RCU stall? Do you have the call trace for your RCU stall?

Regards,
Boqun

Quoted 8 lines

thanks
xinhui

Quoted 4 lines

--
1.8.3.1

Quoted 76 lines · Boqun Feng

Quoted 75 lines · Xinhui Pan

2016-12-26 4:26 GMT+08:00 Waiman Long <[email protected]>:

Quoted 62 lines

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

Signed-off-by Waiman Long <[email protected]>

v1->v2:
- Add comments in changelog and code for the rationale of the change.

---
 kernel/locking/qspinlock_paravirt.h | 50 ++++++++++++++++++++++++------
-------
 1 file changed, 33 insertions(+), 17 deletions(-)

(quoted diff) +0 -0

@@ -323,8 +329,14 @@ static void pv_wait_node(struct mcs_spinlock *node,
 struct mcs_spinlock *prev)
                 * If pv_kick_node() changed us to vcpu_hashed, retain that
                 * value so that pv_wait_head_or_lock() knows to not also

try
* to hash this lock.

(quoted diff) +2 -0

+                *
+                * The smp_store_mb() and control dependency above will

ensure
+ * that state change won't happen before that.
Synchronizing

(quoted diff) +2 -0

+                * with pv_kick_node() wrt hashing by this waiter or by the
+                * lock holder is done solely by the state variable. There

is

kernel/locking/qspinlock_paravirt.h +2 -1

+                * no other ordering requirement.
                 */
-               cmpxchg(&pn->state, vcpu_halted, vcpu_running);
+               cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_running);
 
                /*
                 * If the locked flag is still not set after wakeup, it is

a

(quoted diff) +0 -0

@@ -360,9 +372,12 @@ static void pv_kick_node(struct qspinlock *lock,
 struct mcs_spinlock *node)
         * pv_wait_node(). If OTOH this fails, the vCPU was running and

will
* observe its next->locked value and advance itself. *

(quoted diff) +1 -1

-        * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
+        * Matches with smp_store_mb() and cmpxchg_relaxed() in

pv_wait_node().

(quoted diff) +2 -0

+        * A release barrier is used here to ensure that node->locked is
+        * always set before changing the state. See comment in

pv_wait_node().

         */

kernel/locking/qspinlock_paravirt.h +2 -1

-       if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
+       if (cmpxchg_release(&pn->state, vcpu_halted, vcpu_hashed)
+                       != vcpu_halted)
                return;

Quoted 1 line

hi, Waiman

We can't use _release here, a full barrier is needed.

There is pv_kick_node vs pv_wait_head_or_lock

[w] l->locked = _Q_SLOW_VAL //reordered here

if (READ_ONCE(pn->state) == vcpu_hashed) //False.

                   lp = (struct qspinlock **)1;

Quoted 8 lines

Quoted 5 lines

[STORE] pn->state = vcpu_hashed lp = pv_hash(lock,
pn);
pv_hash() if
(xchg(&l->locked, _Q_SLOW_VAL) == 0) // fasle, not unhashed.

This analysis is correct, but..

Hmm.. look at this again, I don't think this analysis is meaningful, let's say the reordering didn't happen, we still got(similar to your case):

						if (READ_ONCE(pn->state) == vcpu_hashed) // false.
						  lp = (struct qspinlock **)1;

cmpxchg(pn->state, vcpu_halted, vcpu_hashed);
						  if(!lp) {
						    lp = pv_hash(lock, pn);
WRITE_ONCE(l->locked, _Q_SLOW_VAL);
pv_hash();
						    if (xchg(&l->locked, _Q_SLOW_VAL) == 0) // fasle, not unhashed.

, right?

Actually, I think this or your case could not happen because we have

	cmpxchg(pn->state, vcpu_halted, vcpu_running);

in pv_wait_node(), which makes us either observe vcpu_hashed or set pn->state to vcpu_running before pv_kick_node() trying to do the hash.

I may miss something subtle, but does switching back to cmpxchg() could fix the RCU stall you observed?

Regards,
Boqun

Quoted 9 lines

Quoted 5 lines

Then the same lock has hashed twice but only unhashed once. So at last as the hash table grows big, we hit RCU stall.

I hit RCU stall when I run netperf benchmark

how will a big hash table hit RCU stall? Do you have the call trace for your RCU stall?

Quoted 11 lines

Regards,
Boqun

Quoted 8 lines

thanks
xinhui

Quoted 4 lines

--
1.8.3.1

Quoted 82 lines · Boqun Feng

Quoted 80 lines · Xinhui Pan

2016-12-26 4:26 GMT+08:00 Waiman Long <[email protected]>:

Quoted 62 lines

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

Signed-off-by Waiman Long <[email protected]>

v1->v2:
- Add comments in changelog and code for the rationale of the change.

---
 kernel/locking/qspinlock_paravirt.h | 50 ++++++++++++++++++++++++------
-------
 1 file changed, 33 insertions(+), 17 deletions(-)

(quoted diff) +0 -0

@@ -323,8 +329,14 @@ static void pv_wait_node(struct mcs_spinlock *node,
 struct mcs_spinlock *prev)
                 * If pv_kick_node() changed us to vcpu_hashed, retain that
                 * value so that pv_wait_head_or_lock() knows to not also

try
* to hash this lock.

(quoted diff) +2 -0

+                *
+                * The smp_store_mb() and control dependency above will

ensure
+ * that state change won't happen before that.
Synchronizing

(quoted diff) +2 -0

+                * with pv_kick_node() wrt hashing by this waiter or by the
+                * lock holder is done solely by the state variable. There

is

kernel/locking/qspinlock_paravirt.h +2 -1

+                * no other ordering requirement.
                 */
-               cmpxchg(&pn->state, vcpu_halted, vcpu_running);
+               cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_running);
 
                /*
                 * If the locked flag is still not set after wakeup, it is

a

(quoted diff) +0 -0

@@ -360,9 +372,12 @@ static void pv_kick_node(struct qspinlock *lock,
 struct mcs_spinlock *node)
         * pv_wait_node(). If OTOH this fails, the vCPU was running and

will
* observe its next->locked value and advance itself. *

(quoted diff) +1 -1

-        * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
+        * Matches with smp_store_mb() and cmpxchg_relaxed() in

pv_wait_node().

(quoted diff) +2 -0

+        * A release barrier is used here to ensure that node->locked is
+        * always set before changing the state. See comment in

pv_wait_node().

         */

kernel/locking/qspinlock_paravirt.h +2 -1

-       if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
+       if (cmpxchg_release(&pn->state, vcpu_halted, vcpu_hashed)
+                       != vcpu_halted)
                return;

Quoted 1 line

hi, Waiman

We can't use _release here, a full barrier is needed.

There is pv_kick_node vs pv_wait_head_or_lock

[w] l->locked = _Q_SLOW_VAL //reordered here

if (READ_ONCE(pn->state) == vcpu_hashed) //False.

                   lp = (struct qspinlock **)1;

[STORE] pn->state = vcpu_hashed lp = pv_hash(lock,
pn);
pv_hash() if
(xchg(&l->locked, _Q_SLOW_VAL) == 0) // fasle, not unhashed.

Quoted 2 lines

This analysis is correct, but..

Hmm.. look at this again, I don't think this analysis is meaningful, let's say the reordering didn't happen, we still got(similar to your case):

						if (READ_ONCE(pn->state) == vcpu_hashed) // false.
						  lp = (struct qspinlock **)1;

cmpxchg(pn->state, vcpu_halted, vcpu_hashed);

						  if(!lp) {
						    lp = pv_hash(lock, pn);
WRITE_ONCE(l->locked, _Q_SLOW_VAL);
pv_hash();
						    if (xchg(&l->locked, _Q_SLOW_VAL) == 0) // fasle, not unhashed.

, right?

Actually, I think this or your case could not happen because we have

	cmpxchg(pn->state, vcpu_halted, vcpu_running);

in pv_wait_node(), which makes us either observe vcpu_hashed or set pn->state to vcpu_running before pv_kick_node() trying to do the hash.

I may miss something subtle, but does switching back to cmpxchg() could fix the RCU stall you observed?

Regards,
Boqun

Quoted 20 lines

Quoted 5 lines

Then the same lock has hashed twice but only unhashed once. So at last as the hash table grows big, we hit RCU stall.

I hit RCU stall when I run netperf benchmark

how will a big hash table hit RCU stall? Do you have the call trace for your RCU stall?

Regards,
Boqun

Quoted 8 lines

thanks
xinhui

Quoted 4 lines

--
1.8.3.1

Quoted 83 lines · Boqun Feng

Quoted 82 lines · Boqun Feng

Quoted 80 lines · Xinhui Pan

2016-12-26 4:26 GMT+08:00 Waiman Long <[email protected]>:

Quoted 62 lines

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

Signed-off-by Waiman Long <[email protected]>

v1->v2:
- Add comments in changelog and code for the rationale of the change.

---
 kernel/locking/qspinlock_paravirt.h | 50 ++++++++++++++++++++++++------
-------
 1 file changed, 33 insertions(+), 17 deletions(-)

(quoted diff) +0 -0

@@ -323,8 +329,14 @@ static void pv_wait_node(struct mcs_spinlock *node,
 struct mcs_spinlock *prev)
                 * If pv_kick_node() changed us to vcpu_hashed, retain that
                 * value so that pv_wait_head_or_lock() knows to not also

try
* to hash this lock.

(quoted diff) +2 -0

+                *
+                * The smp_store_mb() and control dependency above will

ensure
+ * that state change won't happen before that.
Synchronizing

(quoted diff) +2 -0

+                * with pv_kick_node() wrt hashing by this waiter or by the
+                * lock holder is done solely by the state variable. There

is

kernel/locking/qspinlock_paravirt.h +2 -1

+                * no other ordering requirement.
                 */
-               cmpxchg(&pn->state, vcpu_halted, vcpu_running);
+               cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_running);
 
                /*
                 * If the locked flag is still not set after wakeup, it is

a

(quoted diff) +0 -0

@@ -360,9 +372,12 @@ static void pv_kick_node(struct qspinlock *lock,
 struct mcs_spinlock *node)
         * pv_wait_node(). If OTOH this fails, the vCPU was running and

will
* observe its next->locked value and advance itself. *

(quoted diff) +1 -1

-        * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
+        * Matches with smp_store_mb() and cmpxchg_relaxed() in

pv_wait_node().

(quoted diff) +2 -0

+        * A release barrier is used here to ensure that node->locked is
+        * always set before changing the state. See comment in

pv_wait_node().

         */

kernel/locking/qspinlock_paravirt.h +2 -1

-       if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
+       if (cmpxchg_release(&pn->state, vcpu_halted, vcpu_hashed)
+                       != vcpu_halted)
                return;

Quoted 1 line

hi, Waiman

We can't use _release here, a full barrier is needed.

There is pv_kick_node vs pv_wait_head_or_lock

[w] l->locked = _Q_SLOW_VAL //reordered here

if (READ_ONCE(pn->state) == vcpu_hashed) //False.

                   lp = (struct qspinlock **)1;

[STORE] pn->state = vcpu_hashed lp = pv_hash(lock,
pn);
pv_hash() if
(xchg(&l->locked, _Q_SLOW_VAL) == 0) // fasle, not unhashed.

Quoted 7 lines

Quoted 2 lines

This analysis is correct, but..

Hmm.. look at this again, I don't think this analysis is meaningful, let's say the reordering didn't happen, we still got(similar to your case):

but there is

						cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_running);

Quoted 4 lines

						if (READ_ONCE(pn->state) == vcpu_hashed) // false.
						  lp = (struct qspinlock **)1;

cmpxchg(pn->state, vcpu_halted, vcpu_hashed);

this cmpxchg will observe the cmpxchg_relaxed above, so this cmpxchg will fail as pn->state is vcpu_running. No bug here..

Quoted 75 lines · Xinhui Pan

2016-12-26 4:26 GMT+08:00 Waiman Long <[email protected] <mailto:[email protected]>>:

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

Signed-off-by Waiman Long <[email protected] <mailto:[email protected]>>

v1->v2:
- Add comments in changelog and code for the rationale of the change.

---
kernel/locking/qspinlock_paravirt.h | 50 ++++++++++++++++++++++++------------- 1 file changed, 33 insertions(+), 17 deletions(-)

@@ -323,8 +329,14 @@ static void pv_wait_node(struct mcs_spinlock *node, struct mcs_spinlock *prev)
* If pv_kick_node() changed us to vcpu_hashed, retain that
* value so that pv_wait_head_or_lock() knows to not also try
* to hash this lock.
+ *
+ * The smp_store_mb() and control dependency above will ensure
+ * that state change won't happen before that. Synchronizing
+ * with pv_kick_node() wrt hashing by this waiter or by the
+ * lock holder is done solely by the state variable. There is
+ * no other ordering requirement.
*/
- cmpxchg(&pn->state, vcpu_halted, vcpu_running);
+ cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_running);

/*
* If the locked flag is still not set after wakeup, it is a
@@ -360,9 +372,12 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
* pv_wait_node(). If OTOH this fails, the vCPU was running and will
* observe its next->locked value and advance itself.
*
- * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
+ * Matches with smp_store_mb() and cmpxchg_relaxed() in pv_wait_node().
+ * A release barrier is used here to ensure that node->locked is
+ * always set before changing the state. See comment in pv_wait_node().
*/
- if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
+ if (cmpxchg_release(&pn->state, vcpu_halted, vcpu_hashed)
+ != vcpu_halted)
return;

hi, Waiman
We can't use _release here, a full barrier is needed.

There is pv_kick_node vs pv_wait_head_or_lock

[w] l->locked = _Q_SLOW_VAL //reordered here

                                                                                if (READ_ONCE(pn->state) == vcpu_hashed) //False.
                                                                                               lp = (struct qspinlock **)1;

[STORE] pn->state = vcpu_hashed lp = pv_hash(lock, pn);
pv_hash() if (xchg(&l->locked, _Q_SLOW_VAL) == 0) // fasle, not unhashed.

Then the same lock has hashed twice but only unhashed once. So at last as the hash table grows big, we hit RCU stall.

I hit RCU stall when I run netperf benchmark

thanks
xinhui

Quoted 4 lines

    --
    1.8.3.1

Yes, I know I am being too aggressive in this patch. I am going to tone it down a bit. I just don't have time to run a performance test on PPC system to verify the gain yet. I am planning to send an updated patch soon.

Cheers,
Longman

Quoted 80 lines · Waiman Long

Quoted 79 lines · Xinhui Pan

2016-12-26 4:26 GMT+08:00 Waiman Long <[email protected] <mailto:[email protected]>>:

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

Signed-off-by Waiman Long <[email protected] <mailto:[email protected]>>

v1->v2:
- Add comments in changelog and code for the rationale of the change.

---
kernel/locking/qspinlock_paravirt.h | 50 ++++++++++++++++++++++++------------- 1 file changed, 33 insertions(+), 17 deletions(-)

@@ -323,8 +329,14 @@ static void pv_wait_node(struct mcs_spinlock *node, struct mcs_spinlock *prev)
* If pv_kick_node() changed us to vcpu_hashed, retain that
* value so that pv_wait_head_or_lock() knows to not also try
* to hash this lock.
+ *
+ * The smp_store_mb() and control dependency above will ensure
+ * that state change won't happen before that. Synchronizing
+ * with pv_kick_node() wrt hashing by this waiter or by the
+ * lock holder is done solely by the state variable. There is
+ * no other ordering requirement.
*/
- cmpxchg(&pn->state, vcpu_halted, vcpu_running);
+ cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_running);

/*
* If the locked flag is still not set after wakeup, it is a
@@ -360,9 +372,12 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
* pv_wait_node(). If OTOH this fails, the vCPU was running and will
* observe its next->locked value and advance itself.
*
- * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
+ * Matches with smp_store_mb() and cmpxchg_relaxed() in pv_wait_node().
+ * A release barrier is used here to ensure that node->locked is
+ * always set before changing the state. See comment in pv_wait_node().
*/
- if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
+ if (cmpxchg_release(&pn->state, vcpu_halted, vcpu_hashed)
+ != vcpu_halted)
return;

hi, Waiman
We can't use _release here, a full barrier is needed.

There is pv_kick_node vs pv_wait_head_or_lock

[w] l->locked = _Q_SLOW_VAL //reordered here

                                                                                if (READ_ONCE(pn->state) == vcpu_hashed) //False.
                                                                                               lp = (struct qspinlock **)1;

[STORE] pn->state = vcpu_hashed lp = pv_hash(lock, pn);
pv_hash() if (xchg(&l->locked, _Q_SLOW_VAL) == 0) // fasle, not unhashed.

Then the same lock has hashed twice but only unhashed once. So at last as the hash table grows big, we hit RCU stall.

I hit RCU stall when I run netperf benchmark

thanks
xinhui

    --
    1.8.3.1

Quoted 2 lines

Yes, I know I am being too aggressive in this patch. I am going to tone it down a bit. I just don't have time to run a performance test on PPC system to verify the gain yet. I am planning to send an updated patch soon.

hi, All

I guess I have found the scenario that causes the RCU stall.

pv_wait_node

										[L] pn->state // this load is reordered from cmxchg_release.
	smp_store_mb(pn->state, vcpu_halted);					
	if (!READ_ONCE(node->locked))						
										arch_mcs_spin_unlock_contended(&next->locked);
										pv_kick_node
											[-L]cmpxchg_release(&pn->state, vcpu_halted, vcpu_hashed)
											//cmpxchg_release fails, so pn->state keep as it is.
		pv_wait(&pn->state, vcpu_halted);
		//on PPC, It will not return until pn->state != vcpu_halted.

And when rcu stall hit, I fire an BUG(), and enter debug mode, it seems most cpus are in pv_wait...

So the soltuion to solve this problems is simple, keep the cmpxchg as it is in pv_kick_node, cmpxchg on ppc provides full barriers.

thanks
xinhui

Quoted 3 lines

Cheers,
Longman

Quoted 75 lines · Waiman Long

Quoted 74 lines · Xinhui Pan

2016-12-26 4:26 GMT+08:00 Waiman Long <[email protected] <mailto:[email protected]>>:

A number of cmpxchg calls in qspinlock_paravirt.h were replaced by more relaxed versions to improve performance on architectures that use LL/SC.

All the locking related cmpxchg's are replaced with the _acquire variants:
- pv_queued_spin_steal_lock()
- trylock_clear_pending()

The cmpxchg's related to hashing are replaced by either by the _release or the _relaxed variants. See the inline comment for details.

Signed-off-by Waiman Long <[email protected] <mailto:[email protected]>>

v1->v2:
- Add comments in changelog and code for the rationale of the change.

---
kernel/locking/qspinlock_paravirt.h | 50 ++++++++++++++++++++++++------------- 1 file changed, 33 insertions(+), 17 deletions(-)

@@ -323,8 +329,14 @@ static void pv_wait_node(struct mcs_spinlock *node, struct mcs_spinlock *prev)
* If pv_kick_node() changed us to vcpu_hashed, retain that
* value so that pv_wait_head_or_lock() knows to not also try
* to hash this lock.
+ *
+ * The smp_store_mb() and control dependency above will ensure
+ * that state change won't happen before that. Synchronizing
+ * with pv_kick_node() wrt hashing by this waiter or by the
+ * lock holder is done solely by the state variable. There is
+ * no other ordering requirement.
*/
- cmpxchg(&pn->state, vcpu_halted, vcpu_running);
+ cmpxchg_relaxed(&pn->state, vcpu_halted, vcpu_running);

/*
* If the locked flag is still not set after wakeup, it is a
@@ -360,9 +372,12 @@ static void pv_kick_node(struct qspinlock *lock, struct mcs_spinlock *node)
* pv_wait_node(). If OTOH this fails, the vCPU was running and will
* observe its next->locked value and advance itself.
*
- * Matches with smp_store_mb() and cmpxchg() in pv_wait_node()
+ * Matches with smp_store_mb() and cmpxchg_relaxed() in pv_wait_node().
+ * A release barrier is used here to ensure that node->locked is
+ * always set before changing the state. See comment in pv_wait_node().
*/
- if (cmpxchg(&pn->state, vcpu_halted, vcpu_hashed) != vcpu_halted)
+ if (cmpxchg_release(&pn->state, vcpu_halted, vcpu_hashed)
+ != vcpu_halted)
return;

hi, Waiman
We can't use _release here, a full barrier is needed.

There is pv_kick_node vs pv_wait_head_or_lock

[w] l->locked = _Q_SLOW_VAL //reordered here

                                                                                if (READ_ONCE(pn->state) == vcpu_hashed) //False.
                                                                                               lp = (struct qspinlock **)1;

[STORE] pn->state = vcpu_hashed lp = pv_hash(lock, pn);
pv_hash() if (xchg(&l->locked, _Q_SLOW_VAL) == 0) // fasle, not unhashed.

Then the same lock has hashed twice but only unhashed once. So at last as the hash table grows big, we hit RCU stall.

I hit RCU stall when I run netperf benchmark

thanks
xinhui

Quoted 6 lines

Quoted 4 lines

    --
    1.8.3.1

Yes, I know I am being too aggressive in this patch. I am going to tone it down a bit. I just don't have time to run a performance test on PPC system to verify the gain yet. I am planning to send an updated patch soon.

hi, All

I guess I have found the scenario that causes the RCU stall.

pv_wait_node

										[L] pn->state // this load is reordered from cmxchg_release.
	smp_store_mb(pn->state, vcpu_halted);					
	if (!READ_ONCE(node->locked))						
										arch_mcs_spin_unlock_contended(&next->locked);
										pv_kick_node
											[-L]cmpxchg_release(&pn->state, vcpu_halted, vcpu_hashed)
											//cmpxchg_release fails, so pn->state keep as it is.
		pv_wait(&pn->state, vcpu_halted);
		//on PPC, It will not return until pn->state != vcpu_halted.

And when rcu stall hit, I fire an BUG(), and enter debug mode, it seems most cpus are in pv_wait...

So the soltuion to solve this problems is simple, keep the cmpxchg as it is in pv_kick_node, cmpxchg on ppc provides full barriers.

thanks
xinhui