Skip to contentSkip to conversation

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

PATCH Superseded Waiman Long 4 participants 21 messages Dec 25, 2016 – Feb 17, 2017 2 messages not in the archive Locking primitives

v2 of 6 Superseded Latest is v6 →

lore
Share & tools
lore

Waiman Long

author reviewer
#0 lore raw

PATCH v2 1/1 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 +33 -17
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;

@@ -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.
+	 */
 	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
#1 lore raw

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

Quoted 78 lines
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
author reviewer
#2 lore raw
Quoted 103 lines · Boqun Feng

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);
Quoted 9 lines

The following result is possible:

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

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

Regards,
Boqun

You are probably right. I know the code is somewhat risky. That is why I am waiting for expert like you to see if this is really the case. Now it seems that it may not be the case. I will revise the patch to take that out.

Cheers,
Longman

maintainer
#3 lore raw
In reply to Waiman Long
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 5 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?

author reviewer
#4 lore raw
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 11 lines
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?

I haven't thought too much about fast/slow paths when I was making the patch. You are right that we properly don't need to do that for the slowpath cases. I can modify the patch to do just the fast patch change.

Cheers,
Longman

maintainer
#5 lore raw
Quoted 8 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.

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

maintainer
#7 lore raw
Quoted 11 lines · Pan Xinhui

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.

Right, curious about that relaxed one. In any case, I was more wondering about the performance impact on the larger construct of the pvlock itself.

#8 lore raw
In reply to Pan Xinhui
Quoted 22 lines · Pan Xinhui
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.

Quoted 8 lines

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.

I have observed something similar before. But the performance number for a single atomic operation itself is not that useful.

Here is my understanding(basically guessing ;-))

If your testcase is only committing those cmpxchg in a loop then the overhead of the barrier in _release and _acquire is much small and may even help the performance because of their side effects on prefetchs or cache invalidations.

But if your testcase get complex even that committing barriers is not cheap, you probably will see cmpxchg_relaxed beats _acquire and _release variants.

Regards,
Boqun

Quoted 3 lines

thanks
xinhui

author reviewer
#9 lore raw
In reply to Pan Xinhui
Quoted 30 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

Quoted 7 lines

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

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

#10 lore raw
Quoted 35 lines · Waiman Long
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 6 lines
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.

_relaxed is more lightweight in two aspects:

1. _relaxed is not a compiler barrier, so it allows compilers do
more optimizations than _acquire and _release.

2. _relaxed doesn't introduce HW barriers and doesn't performs
worse than _acquire and _release in _most_ _usual_ cases.

And on some ll/sc archs without a lightweigt barrier like "lwsync" for _acquire and _release, #2 could be more significant.

So don't hesitate to use _relaxed whenever it's possible and reasonable ;-)

Regards,
Boqun

Quoted 3 lines

Cheers,
Longman

author reviewer
#11 lore raw
In reply to Peter Zijlstra
Quoted 10 lines · Peter Zijlstra
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.

Yes, RHT does have PPC machines around. It is just I don't have experience dealing with those machines yet. I will try to run some test and include the numbers in the next version of the patch.

Cheers,
Longman

A message that is not in the archive (sent off-list or not yet received): CAH4ORazqsCBA4G5paHtsp8PMfM=J3P6rvyR-53-ZLjn=7U6J0g@mail.gmail.com

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

Quoted 9 lines

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.

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

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

#15 lore raw
Quoted 100 lines · Boqun Feng
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.
Quoted 9 lines

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

yep, there is still a race. We have to fix it.
so I think
we must check old = xchg(&l->locked, _Q_SLOW_VAL)
if (old == 0)
do something
else if (old == _Q_SLOW_VAL)
do something else

Quoted 3 lines

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

yes, just fix this cmpxchg and then no RCU stall.

Quoted 25 lines

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

#16 lore raw
In reply to Boqun Feng
Quoted 100 lines · Boqun Feng
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.
Quoted 9 lines

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

yep, there is still a race. We have to fix it.
so I think
we must check old = xchg(&l->locked, _Q_SLOW_VAL)
if (old == 0)
do something
else if (old == _Q_SLOW_VAL)
do something else

Quoted 3 lines

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

yes, just fix this cmpxchg and then no RCU stall.

Quoted 12 lines

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?

maybe too many time on hashing? I am not sure.

Quoted 13 lines
Quoted 11 lines

Regards,
Boqun

Quoted 8 lines

thanks
xinhui

Quoted 4 lines

--
1.8.3.1

#17 lore raw
In reply to Boqun Feng
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 44 lines
						  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

#18 lore raw
Quoted 94 lines · Pan Xinhui
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

Quoted 9 lines
						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..

And we got the same guarantee if we use cmpxchg_release(), no?

Regards,
Boqun

A message that is not in the archive (sent off-list or not yet received): [email protected]

#20 lore raw
Quoted 76 lines · Waiman Long
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 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

Quoted 3 lines

Cheers,
Longman

#21 lore raw
Quoted 83 lines · panxinhui
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 6 lines
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.

Yes, I believe that's the case, as the comment before smp_store_mb() in pv_wait_node states. Good show!

Regards,
Boqun

Quoted 22 lines

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

author reviewer
#22 lore raw
In reply to panxinhui
Quoted 98 lines · panxinhui
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.
Quoted 7 lines

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

Sorry for the late reply and thank for the explanation. I am not aware that the load of cmpxchg_release can be moved up like that. I will need to be more careful of using relaxed form of cmpxchg next time.

Cheers,
Longman