Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1250292 > unrolled thread

[RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback ling.ma.program@gmail.com - 2015-10-19 04:30 +0200
    Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Ingo Molnar <mingo@kernel.org> - 2015-10-19 10:00 +0200
      Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Peter Zijlstra <peterz@infradead.org> - 2015-10-19 11:40 +0200
        Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Ingo Molnar <mingo@kernel.org> - 2015-10-19 13:30 +0200
          Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction  rollback Waiman Long <waiman.long@hpe.com> - 2015-10-19 19:30 +0200
      Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Ling Ma <ling.ma.program@gmail.com> - 2015-10-20 05:00 +0200
        Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Ingo Molnar <mingo@kernel.org> - 2015-10-20 10:50 +0200
          Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Ling Ma <ling.ma.program@gmail.com> - 2015-10-21 07:30 +0200
        Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Peter Zijlstra <peterz@infradead.org> - 2015-10-20 11:20 +0200
    Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Peter Zijlstra <peterz@infradead.org> - 2015-10-19 11:40 +0200
      Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction  rollback Waiman Long <waiman.long@hpe.com> - 2015-10-19 19:30 +0200
      Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Ling Ma <ling.ma.program@gmail.com> - 2015-10-20 05:10 +0200
    Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Peter Zijlstra <peterz@infradead.org> - 2015-10-19 11:50 +0200
      Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Ling Ma <ling.ma.program@gmail.com> - 2015-10-20 05:10 +0200
      Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Ling Ma <ling.ma.program@gmail.com> - 2015-10-20 05:30 +0200
        Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Peter Zijlstra <peterz@infradead.org> - 2015-10-20 11:20 +0200
          Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Ling Ma <ling.ma.program@gmail.com> - 2015-10-21 07:40 +0200
    Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction  rollback Waiman Long <waiman.long@hpe.com> - 2015-10-19 19:20 +0200
      Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Ling Ma <ling.ma.program@gmail.com> - 2015-10-20 05:20 +0200
        Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction  rollback Waiman Long <waiman.long@hpe.com> - 2015-10-20 21:00 +0200
          Re: [RFC PATCH] qspinlock: Improve performance by reducing load  instruction rollback Ling Ma <ling.ma.program@gmail.com> - 2015-10-21 07:50 +0200

Page 1 of 2  [1] 2  Next page →

#1250292 — [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

From: Ma Ling <ling.ml@alibaba-inc.com>

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

Processor 0				Processor 1

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

If r1 = 1, r2 must be 1

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

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

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

Thanks
Ling

Signed-off-by: Ma Ling <ling.ml@alibaba-inc.com>
---
 kernel/locking/qspinlock.c |   43 ++++++++++++++++++-------------------------
 1 files changed, 18 insertions(+), 25 deletions(-)

diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index 87e9ce6..16421f2 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -332,25 +332,14 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 	if (new == _Q_LOCKED_VAL)
 		return;
 
-	/*
-	 * we're pending, wait for the owner to go away.
-	 *
-	 * *,1,1 -> *,1,0
+	/* we're waiting, and get lock owner
 	 *
-	 * this wait loop must be a load-acquire such that we match the
-	 * store-release that clears the locked bit and create lock
-	 * sequentiality; this is because not all clear_pending_set_locked()
-	 * implementations imply full barriers.
+	 * *,1,* -> *,0,1
 	 */
-	while ((val = smp_load_acquire(&lock->val.counter)) & _Q_LOCKED_MASK)
+	while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending,
+		_Q_PENDING_VAL, _Q_LOCKED_VAL) != _Q_PENDING_VAL)
 		cpu_relax();
-
-	/*
-	 * take ownership and clear the pending bit.
-	 *
-	 * *,1,0 -> *,0,1
-	 */
-	clear_pending_set_locked(lock);
+
 	return;
 
 	/*
@@ -399,17 +388,21 @@ queue:
 	 * we're at the head of the waitqueue, wait for the owner & pending to
 	 * go away.
 	 *
-	 * *,x,y -> *,0,0
-	 *
-	 * this wait loop must use a load-acquire such that we match the
-	 * store-release that clears the locked bit and create lock
-	 * sequentiality; this is because the set_locked() function below
-	 * does not imply a full barrier.
-	 *
+	 * *,x,y -> *,0,1
 	 */
 	pv_wait_head(lock, node);
-	while ((val = smp_load_acquire(&lock->val.counter)) & _Q_LOCKED_PENDING_MASK)
+	next = READ_ONCE(node->next);
+	while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending, 0,
+		_Q_LOCKED_VAL) != 0) {
+		next = READ_ONCE(node->next);
 		cpu_relax();
+	}
+
+	if (next)
+		goto next_node;
+
+	val = smp_load_acquire(&lock->val.counter);
+	tail = tail | _Q_LOCKED_VAL;
 
 	/*
 	 * claim the lock:
@@ -423,7 +416,6 @@ queue:
 	 */
 	for (;;) {
 		if (val != tail) {
-			set_locked(lock);
 			break;
 		}
 		old = atomic_cmpxchg(&lock->val, val, _Q_LOCKED_VAL);
@@ -439,6 +431,7 @@ queue:
 	while (!(next = READ_ONCE(node->next)))
 		cpu_relax();
 
+next_node:
 	arch_mcs_spin_unlock_contended(&next->locked);
 	pv_kick_node(lock, next);
 
-- 
1.7.1

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

[toc] | [next] | [standalone]

#1250414 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

* ling.ma.program@gmail.com <ling.ma.program@gmail.com> wrote:

> From: Ma Ling <ling.ml@alibaba-inc.com>
> 
> All load instructions can run speculatively but they have to follow
> memory order rule in multiple cores as below:
> _x = _y = 0
> 
> Processor 0				Processor 1
> 
> mov r1, [ _y]  //M1			mov [ _x], 1  //M3
> mov r2, [ _x]  //M2			mov [ _y], 1  //M4
> 
> If r1 = 1, r2 must be 1
> 
> In order to guarantee above rule, although Processor 0 execute
> M1 and M2 instruction out of order, they are kept in ROB,
> when load buffer for _x in Processor 0 received the update 
> message from Processor 1, Processor 0 need to roll back
> from M2 instruction, which will flush the whole pipeline,
> the latency is over the penalty from branch prediction miss.
> 
> In this patch we use lock cmpxchg instruction to force load
> instructions to be serialization, the destination operand
> receives a write cycle without regard to the result of
> the comparison, which can help us to reduce the penalty
> from load instruction roll back.
> 
> Our experiment indicates the performance can be improved by 10%~15%
> for 2 and 3 threads cases, the conflicts from lock cache line
> spend them most of the time.

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

Thanks,

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

[toc] | [prev] | [next] | [standalone]

#1250509 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

On Mon, Oct 19, 2015 at 09:58:23AM +0200, Ingo Molnar wrote:
> 
> * ling.ma.program@gmail.com <ling.ma.program@gmail.com> wrote:
> 
> > From: Ma Ling <ling.ml@alibaba-inc.com>
> > 
> > All load instructions can run speculatively but they have to follow
> > memory order rule in multiple cores as below:
> > _x = _y = 0
> > 
> > Processor 0				Processor 1
> > 
> > mov r1, [ _y]  //M1			mov [ _x], 1  //M3
> > mov r2, [ _x]  //M2			mov [ _y], 1  //M4
> > 
> > If r1 = 1, r2 must be 1
> > 
> > In order to guarantee above rule, although Processor 0 execute
> > M1 and M2 instruction out of order, they are kept in ROB,
> > when load buffer for _x in Processor 0 received the update 
> > message from Processor 1, Processor 0 need to roll back
> > from M2 instruction, which will flush the whole pipeline,
> > the latency is over the penalty from branch prediction miss.
> > 
> > In this patch we use lock cmpxchg instruction to force load
> > instructions to be serialization, the destination operand
> > receives a write cycle without regard to the result of
> > the comparison, which can help us to reduce the penalty
> > from load instruction roll back.
> > 
> > Our experiment indicates the performance can be improved by 10%~15%
> > for 2 and 3 threads cases, the conflicts from lock cache line
> > spend them most of the time.
> 
> So it would be nice to create a new user-space spinlock testing facility, via a 
> new 'perf bench spinlock' feature or so. That way others can test and validate 
> your results on different hardware as well.

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

The trouble is going to keep them in sync.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1250574 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

* Peter Zijlstra <peterz@infradead.org> wrote:

> On Mon, Oct 19, 2015 at 09:58:23AM +0200, Ingo Molnar wrote:
> > 
> > * ling.ma.program@gmail.com <ling.ma.program@gmail.com> wrote:
> > 
> > > From: Ma Ling <ling.ml@alibaba-inc.com>
> > > 
> > > All load instructions can run speculatively but they have to follow
> > > memory order rule in multiple cores as below:
> > > _x = _y = 0
> > > 
> > > Processor 0				Processor 1
> > > 
> > > mov r1, [ _y]  //M1			mov [ _x], 1  //M3
> > > mov r2, [ _x]  //M2			mov [ _y], 1  //M4
> > > 
> > > If r1 = 1, r2 must be 1
> > > 
> > > In order to guarantee above rule, although Processor 0 execute
> > > M1 and M2 instruction out of order, they are kept in ROB,
> > > when load buffer for _x in Processor 0 received the update 
> > > message from Processor 1, Processor 0 need to roll back
> > > from M2 instruction, which will flush the whole pipeline,
> > > the latency is over the penalty from branch prediction miss.
> > > 
> > > In this patch we use lock cmpxchg instruction to force load
> > > instructions to be serialization, the destination operand
> > > receives a write cycle without regard to the result of
> > > the comparison, which can help us to reduce the penalty
> > > from load instruction roll back.
> > > 
> > > Our experiment indicates the performance can be improved by 10%~15%
> > > for 2 and 3 threads cases, the conflicts from lock cache line
> > > spend them most of the time.
> > 
> > So it would be nice to create a new user-space spinlock testing facility, via a 
> > new 'perf bench spinlock' feature or so. That way others can test and validate 
> > your results on different hardware as well.
> 
> So its trivial to lift this code into userspace -- in fact, I have that
> somewhere.
> 
> The trouble is going to keep them in sync.

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

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

Thanks,

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

[toc] | [prev] | [next] | [standalone]

#1250951 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

On 10/19/2015 07:24 AM, Ingo Molnar wrote:
> * Peter Zijlstra<peterz@infradead.org>  wrote:
>
>> On Mon, Oct 19, 2015 at 09:58:23AM +0200, Ingo Molnar wrote:
>>> * ling.ma.program@gmail.com<ling.ma.program@gmail.com>  wrote:
>>>
>>>> From: Ma Ling<ling.ml@alibaba-inc.com>
>>>>
>>>> All load instructions can run speculatively but they have to follow
>>>> memory order rule in multiple cores as below:
>>>> _x = _y = 0
>>>>
>>>> Processor 0				Processor 1
>>>>
>>>> mov r1, [ _y]  //M1			mov [ _x], 1  //M3
>>>> mov r2, [ _x]  //M2			mov [ _y], 1  //M4
>>>>
>>>> If r1 = 1, r2 must be 1
>>>>
>>>> In order to guarantee above rule, although Processor 0 execute
>>>> M1 and M2 instruction out of order, they are kept in ROB,
>>>> when load buffer for _x in Processor 0 received the update
>>>> message from Processor 1, Processor 0 need to roll back
>>>> from M2 instruction, which will flush the whole pipeline,
>>>> the latency is over the penalty from branch prediction miss.
>>>>
>>>> In this patch we use lock cmpxchg instruction to force load
>>>> instructions to be serialization, the destination operand
>>>> receives a write cycle without regard to the result of
>>>> the comparison, which can help us to reduce the penalty
>>>> from load instruction roll back.
>>>>
>>>> Our experiment indicates the performance can be improved by 10%~15%
>>>> for 2 and 3 threads cases, the conflicts from lock cache line
>>>> spend them most of the time.
>>> So it would be nice to create a new user-space spinlock testing facility, via a
>>> new 'perf bench spinlock' feature or so. That way others can test and validate
>>> your results on different hardware as well.
>> So its trivial to lift this code into userspace -- in fact, I have that
>> somewhere.
>>
>> The trouble is going to keep them in sync.
> So we can just try this optimistically, and if it keeps breaking, we can use the
> technique perf uses to sync up the rbtree implementation: we copy the kernel
> version into tooling, but run diff against the kernel version and warn at tool
> build time that there's divergence.
>
> I.e. a non-build-fatal force that keeps things in sync.
>
> Thanks,
>
> 	Ingo
>

It is on my to-do list. I just want to wrap up my latest PV qspinlock 
patch before embarking on this adventure.

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

[toc] | [prev] | [next] | [standalone]

#1251274 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

[Multipart message — attachments visible in raw view] — view raw

>
> So it would be nice to create a new user-space spinlock testing facility, via a
> new 'perf bench spinlock' feature or so. That way others can test and validate
> your results on different hardware as well.
>
Attached the spinlock test module . Queued spinlock will run very
slowly in user space
because process switch context, it is OK for  spinlock-test
implementation with kernel module ?

Thanks
Ling

[toc] | [prev] | [next] | [standalone]

#1251453 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

* Ling Ma <ling.ma.program@gmail.com> wrote:

> > So it would be nice to create a new user-space spinlock testing facility, via 
> > a new 'perf bench spinlock' feature or so. That way others can test and 
> > validate your results on different hardware as well.
>
> Attached the spinlock test module . Queued spinlock will run very slowly in user 
> space because process switch context, it is OK for spinlock-test implementation 
> with kernel module ?

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

Thanks,

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

[toc] | [prev] | [next] | [standalone]

#1252478 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

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

Thanks
Ling

2015-10-20 16:48 GMT+08:00 Ingo Molnar <mingo@kernel.org>:
>
> * Ling Ma <ling.ma.program@gmail.com> wrote:
>
>> > So it would be nice to create a new user-space spinlock testing facility, via
>> > a new 'perf bench spinlock' feature or so. That way others can test and
>> > validate your results on different hardware as well.
>>
>> Attached the spinlock test module . Queued spinlock will run very slowly in user
>> space because process switch context, it is OK for spinlock-test implementation
>> with kernel module ?
>
> Not sure what you mean by 'because process switch context': if you pin the test
> tasks to individual CPUs and make sure there's nothing else running it should be
> equivalent to kernel-space execution.
>
> Thanks,
>
>         Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1251489 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

On Tue, Oct 20, 2015 at 10:57:53AM +0800, Ling Ma wrote:
> >
> > So it would be nice to create a new user-space spinlock testing facility, via a
> > new 'perf bench spinlock' feature or so. That way others can test and validate
> > your results on different hardware as well.
> >
> Attached the spinlock test module . Queued spinlock will run very
> slowly in user space
> because process switch context, it is OK for  spinlock-test
> implementation with kernel module ?

Works just fine in userspace if you pin each thread to a cpu and ensure
there's nothing else running on the system.

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

[toc] | [prev] | [next] | [standalone]

#1250505 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

On Mon, Oct 19, 2015 at 10:27:22AM +0800, ling.ma.program@gmail.com wrote:
> From: Ma Ling <ling.ml@alibaba-inc.com>
> 
> All load instructions can run speculatively but they have to follow
> memory order rule in multiple cores as below:
> _x = _y = 0
> 
> Processor 0				Processor 1
> 
> mov r1, [ _y]  //M1			mov [ _x], 1  //M3
> mov r2, [ _x]  //M2			mov [ _y], 1  //M4
> 
> If r1 = 1, r2 must be 1
> 
> In order to guarantee above rule, although Processor 0 execute
> M1 and M2 instruction out of order, they are kept in ROB,
> when load buffer for _x in Processor 0 received the update 
> message from Processor 1, Processor 0 need to roll back
> from M2 instruction, which will flush the whole pipeline,
> the latency is over the penalty from branch prediction miss.
> 
> In this patch we use lock cmpxchg instruction to force load
> instructions to be serialization, the destination operand
> receives a write cycle without regard to the result of
> the comparison, which can help us to reduce the penalty
> from load instruction roll back.
> 
> Our experiment indicates the performance can be improved by 10%~15%
> for 2 and 3 threads cases, the conflicts from lock cache line
> spend them most of the time.

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

> Signed-off-by: Ma Ling <ling.ml@alibaba-inc.com>
> ---
>  kernel/locking/qspinlock.c |   43 ++++++++++++++++++-------------------------
>  1 files changed, 18 insertions(+), 25 deletions(-)
> 
> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
> index 87e9ce6..16421f2 100644
> --- a/kernel/locking/qspinlock.c
> +++ b/kernel/locking/qspinlock.c
> @@ -332,25 +332,14 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
>  	if (new == _Q_LOCKED_VAL)
>  		return;
>  
> -	/*
> -	 * we're pending, wait for the owner to go away.
> -	 *
> -	 * *,1,1 -> *,1,0
> +	/* we're waiting, and get lock owner

That's incorrect coding style

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

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

>  		cpu_relax();
> -
> -	/*
> -	 * take ownership and clear the pending bit.
> -	 *
> -	 * *,1,0 -> *,0,1
> -	 */
> -	clear_pending_set_locked(lock);
> +
>  	return;
>  
>  	/*
> @@ -399,17 +388,21 @@ queue:
>  	 * we're at the head of the waitqueue, wait for the owner & pending to
>  	 * go away.
>  	 *
> -	 * *,x,y -> *,0,0
> -	 *
> -	 * this wait loop must use a load-acquire such that we match the
> -	 * store-release that clears the locked bit and create lock
> -	 * sequentiality; this is because the set_locked() function below
> -	 * does not imply a full barrier.
> -	 *
> +	 * *,x,y -> *,0,1
>  	 */
>  	pv_wait_head(lock, node);
> -	while ((val = smp_load_acquire(&lock->val.counter)) & _Q_LOCKED_PENDING_MASK)
> +	next = READ_ONCE(node->next);
> +	while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending, 0,
> +		_Q_LOCKED_VAL) != 0) {

idem

> +		next = READ_ONCE(node->next);
>  		cpu_relax();
> +	}
> +
> +	if (next)
> +		goto next_node;
> +
> +	val = smp_load_acquire(&lock->val.counter);
> +	tail = tail | _Q_LOCKED_VAL;
>  
>  	/*
>  	 * claim the lock:
> @@ -423,7 +416,6 @@ queue:
>  	 */
>  	for (;;) {
>  		if (val != tail) {
> -			set_locked(lock);
>  			break;
>  		}
>  		old = atomic_cmpxchg(&lock->val, val, _Q_LOCKED_VAL);
> @@ -439,6 +431,7 @@ queue:
>  	while (!(next = READ_ONCE(node->next)))
>  		cpu_relax();
>  
> +next_node:
>  	arch_mcs_spin_unlock_contended(&next->locked);
>  	pv_kick_node(lock, next);
>  
> -- 
> 1.7.1
> 
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1250948 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

On 10/19/2015 05:33 AM, Peter Zijlstra wrote:
> On Mon, Oct 19, 2015 at 10:27:22AM +0800, ling.ma.program@gmail.com wrote:
>> From: Ma Ling<ling.ml@alibaba-inc.com>
>>
>> All load instructions can run speculatively but they have to follow
>> memory order rule in multiple cores as below:
>> _x = _y = 0
>>
>> Processor 0				Processor 1
>>
>> mov r1, [ _y]  //M1			mov [ _x], 1  //M3
>> mov r2, [ _x]  //M2			mov [ _y], 1  //M4
>>
>> If r1 = 1, r2 must be 1
>>
>> In order to guarantee above rule, although Processor 0 execute
>> M1 and M2 instruction out of order, they are kept in ROB,
>> when load buffer for _x in Processor 0 received the update
>> message from Processor 1, Processor 0 need to roll back
>> from M2 instruction, which will flush the whole pipeline,
>> the latency is over the penalty from branch prediction miss.
>>
>> In this patch we use lock cmpxchg instruction to force load
>> instructions to be serialization, the destination operand
>> receives a write cycle without regard to the result of
>> the comparison, which can help us to reduce the penalty
>> from load instruction roll back.
>>
>> Our experiment indicates the performance can be improved by 10%~15%
>> for 2 and 3 threads cases, the conflicts from lock cache line
>> spend them most of the time.
> On what hardware? Also, you forgot to Cc Waiman, who is a prime author
> of this code. Excessive quoting for his benefit.

Thanks for letting me aware of this patch. I had commented on the patch 
in a separate mail.

Cheers,
Longman

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

[toc] | [prev] | [next] | [standalone]

#1251276 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

2015-10-19 17:33 GMT+08:00 Peter Zijlstra <peterz@infradead.org>:
> On Mon, Oct 19, 2015 at 10:27:22AM +0800, ling.ma.program@gmail.com wrote:
>> From: Ma Ling <ling.ml@alibaba-inc.com>
>>
>> All load instructions can run speculatively but they have to follow
>> memory order rule in multiple cores as below:
>> _x = _y = 0
>>
>> Processor 0                           Processor 1
>>
>> mov r1, [ _y]  //M1                   mov [ _x], 1  //M3
>> mov r2, [ _x]  //M2                   mov [ _y], 1  //M4
>>
>> If r1 = 1, r2 must be 1
>>
>> In order to guarantee above rule, although Processor 0 execute
>> M1 and M2 instruction out of order, they are kept in ROB,
>> when load buffer for _x in Processor 0 received the update
>> message from Processor 1, Processor 0 need to roll back
>> from M2 instruction, which will flush the whole pipeline,
>> the latency is over the penalty from branch prediction miss.
>>
>> In this patch we use lock cmpxchg instruction to force load
>> instructions to be serialization, the destination operand
>> receives a write cycle without regard to the result of
>> the comparison, which can help us to reduce the penalty
>> from load instruction roll back.
>>
>> Our experiment indicates the performance can be improved by 10%~15%
>> for 2 and 3 threads cases, the conflicts from lock cache line
>> spend them most of the time.
>
> On what hardware? Also, you forgot to Cc Waiman, who is a prime author
> of this code. Excessive quoting for his benefit.
>
>> Signed-off-by: Ma Ling <ling.ml@alibaba-inc.com>
>> ---
>>  kernel/locking/qspinlock.c |   43 ++++++++++++++++++-------------------------
>>  1 files changed, 18 insertions(+), 25 deletions(-)
>>
>> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
>> index 87e9ce6..16421f2 100644
>> --- a/kernel/locking/qspinlock.c
>> +++ b/kernel/locking/qspinlock.c
>> @@ -332,25 +332,14 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
>>       if (new == _Q_LOCKED_VAL)
>>               return;
>>
>> -     /*
>> -      * we're pending, wait for the owner to go away.
>> -      *
>> -      * *,1,1 -> *,1,0
>> +     /* we're waiting, and get lock owner
>
> That's incorrect coding style
Ok, I will fix, thx.
>
>>        *
>> -      * this wait loop must be a load-acquire such that we match the
>> -      * store-release that clears the locked bit and create lock
>> -      * sequentiality; this is because not all clear_pending_set_locked()
>> -      * implementations imply full barriers.
>> +      * *,1,* -> *,0,1
>>        */
>> -     while ((val = smp_load_acquire(&lock->val.counter)) & _Q_LOCKED_MASK)
>> +     while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending,
>> +             _Q_PENDING_VAL, _Q_LOCKED_VAL) != _Q_PENDING_VAL)
>
> That's both horrible coding style and painful, we should not spin-wait
> with a cmpxchg instruction like that.
Ok I will fix
>
>>               cpu_relax();
>> -
>> -     /*
>> -      * take ownership and clear the pending bit.
>> -      *
>> -      * *,1,0 -> *,0,1
>> -      */
>> -     clear_pending_set_locked(lock);
>> +
>>       return;
>>
>>       /*
>> @@ -399,17 +388,21 @@ queue:
>>        * we're at the head of the waitqueue, wait for the owner & pending to
>>        * go away.
>>        *
>> -      * *,x,y -> *,0,0
>> -      *
>> -      * this wait loop must use a load-acquire such that we match the
>> -      * store-release that clears the locked bit and create lock
>> -      * sequentiality; this is because the set_locked() function below
>> -      * does not imply a full barrier.
>> -      *
>> +      * *,x,y -> *,0,1
>>        */
>>       pv_wait_head(lock, node);
>> -     while ((val = smp_load_acquire(&lock->val.counter)) & _Q_LOCKED_PENDING_MASK)
>> +     next = READ_ONCE(node->next);
>> +     while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending, 0,
>> +             _Q_LOCKED_VAL) != 0) {
>
> idem
>
>> +             next = READ_ONCE(node->next);
>>               cpu_relax();
>> +     }
>> +
>> +     if (next)
>> +             goto next_node;
>> +
>> +     val = smp_load_acquire(&lock->val.counter);
>> +     tail = tail | _Q_LOCKED_VAL;
>>
>>       /*
>>        * claim the lock:
>> @@ -423,7 +416,6 @@ queue:
>>        */
>>       for (;;) {
>>               if (val != tail) {
>> -                     set_locked(lock);
>>                       break;
>>               }
>>               old = atomic_cmpxchg(&lock->val, val, _Q_LOCKED_VAL);
>> @@ -439,6 +431,7 @@ queue:
>>       while (!(next = READ_ONCE(node->next)))
>>               cpu_relax();
>>
>> +next_node:
>>       arch_mcs_spin_unlock_contended(&next->locked);
>>       pv_kick_node(lock, next);
>>
>> --
>> 1.7.1
>>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1250526 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

On Mon, Oct 19, 2015 at 10:27:22AM +0800, ling.ma.program@gmail.com wrote:
> From: Ma Ling <ling.ml@alibaba-inc.com>
> 
> All load instructions can run speculatively but they have to follow
> memory order rule in multiple cores as below:
> _x = _y = 0
> 
> Processor 0				Processor 1
> 
> mov r1, [ _y]  //M1			mov [ _x], 1  //M3
> mov r2, [ _x]  //M2			mov [ _y], 1  //M4
> 
> If r1 = 1, r2 must be 1
> 
> In order to guarantee above rule, although Processor 0 execute
> M1 and M2 instruction out of order, they are kept in ROB,
> when load buffer for _x in Processor 0 received the update
> message from Processor 1, Processor 0 need to roll back
> from M2 instruction, which will flush the whole pipeline,
> the latency is over the penalty from branch prediction miss.
> 
> In this patch we use lock cmpxchg instruction to force load

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

> instructions to be serialization,

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

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

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

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

That just doesn't parse, what?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1251275 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

2015-10-19 17:46 GMT+08:00 Peter Zijlstra <peterz@infradead.org>:
> On Mon, Oct 19, 2015 at 10:27:22AM +0800, ling.ma.program@gmail.com wrote:
>> From: Ma Ling <ling.ml@alibaba-inc.com>
>>
>> All load instructions can run speculatively but they have to follow
>> memory order rule in multiple cores as below:
>> _x = _y = 0
>>
>> Processor 0                           Processor 1
>>
>> mov r1, [ _y]  //M1                   mov [ _x], 1  //M3
>> mov r2, [ _x]  //M2                   mov [ _y], 1  //M4
>>
>> If r1 = 1, r2 must be 1
>>
>> In order to guarantee above rule, although Processor 0 execute
>> M1 and M2 instruction out of order, they are kept in ROB,
>> when load buffer for _x in Processor 0 received the update
>> message from Processor 1, Processor 0 need to roll back
>> from M2 instruction, which will flush the whole pipeline,
>> the latency is over the penalty from branch prediction miss.
>>
>> In this patch we use lock cmpxchg instruction to force load
>
> "lock cmpxchg" makes me think you're working on x86.
>
>> instructions to be serialization,
>
> smp_rmb() does that, and that's 'free' on x86. Because x86 doesn't do
> read reordering.
>
>> the destination operand
>> receives a write cycle without regard to the result of
>> the comparison, which can help us to reduce the penalty
>> from load instruction roll back.
>
> And that makes me think I'm not understanding what you're getting at. If
> you need to force memory order, a "fence" (or smp_mb()) would still be
> cheaper than endlessly pulling the line into exclusive state for no
> reason, right?
>
>> Our experiment indicates the performance can be improved by 10%~15%
>> for 2 and 3 threads cases, the conflicts from lock cache line
>> spend them most of the time.
>
> That just doesn't parse, what?
When the thread number is 2 or 3, only lock cache line will generate conflicts,
and cost them the most of the time.

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

[toc] | [prev] | [next] | [standalone]

#1251280 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

2015-10-19 17:46 GMT+08:00 Peter Zijlstra <peterz@infradead.org>:
> On Mon, Oct 19, 2015 at 10:27:22AM +0800, ling.ma.program@gmail.com wrote:
>> From: Ma Ling <ling.ml@alibaba-inc.com>
>>
>> All load instructions can run speculatively but they have to follow
>> memory order rule in multiple cores as below:
>> _x = _y = 0
>>
>> Processor 0                           Processor 1
>>
>> mov r1, [ _y]  //M1                   mov [ _x], 1  //M3
>> mov r2, [ _x]  //M2                   mov [ _y], 1  //M4
>>
>> If r1 = 1, r2 must be 1
>>
>> In order to guarantee above rule, although Processor 0 execute
>> M1 and M2 instruction out of order, they are kept in ROB,
>> when load buffer for _x in Processor 0 received the update
>> message from Processor 1, Processor 0 need to roll back
>> from M2 instruction, which will flush the whole pipeline,
>> the latency is over the penalty from branch prediction miss.
>>
>> In this patch we use lock cmpxchg instruction to force load
>
> "lock cmpxchg" makes me think you're working on x86.
>
>> instructions to be serialization,
>
> smp_rmb() does that, and that's 'free' on x86. Because x86 doesn't do
> read reordering.
>
>> the destination operand
>> receives a write cycle without regard to the result of
>> the comparison, which can help us to reduce the penalty
>> from load instruction roll back.
>
> And that makes me think I'm not understanding what you're getting at. If
> you need to force memory order, a "fence" (or smp_mb()) would still be
> cheaper than endlessly pulling the line into exclusive state for no
> reason, right?

Peter,

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

Thanks
Ling
>
>> Our experiment indicates the performance can be improved by 10%~15%
>> for 2 and 3 threads cases, the conflicts from lock cache line
>> spend them most of the time.
>
> That just doesn't parse, what?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1251492 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

On Tue, Oct 20, 2015 at 11:24:02AM +0800, Ling Ma wrote:
> 2015-10-19 17:46 GMT+08:00 Peter Zijlstra <peterz@infradead.org>:
> > On Mon, Oct 19, 2015 at 10:27:22AM +0800, ling.ma.program@gmail.com wrote:
> >> From: Ma Ling <ling.ml@alibaba-inc.com>
> >>
> >> All load instructions can run speculatively but they have to follow
> >> memory order rule in multiple cores as below:
> >> _x = _y = 0
> >>
> >> Processor 0                           Processor 1
> >>
> >> mov r1, [ _y]  //M1                   mov [ _x], 1  //M3
> >> mov r2, [ _x]  //M2                   mov [ _y], 1  //M4
> >>
> >> If r1 = 1, r2 must be 1
> >>
> >> In order to guarantee above rule, although Processor 0 execute
> >> M1 and M2 instruction out of order, they are kept in ROB,
> >> when load buffer for _x in Processor 0 received the update
> >> message from Processor 1, Processor 0 need to roll back
> >> from M2 instruction, which will flush the whole pipeline,
> >> the latency is over the penalty from branch prediction miss.
> >>
> >> In this patch we use lock cmpxchg instruction to force load
> >
> > "lock cmpxchg" makes me think you're working on x86.
> >
> >> instructions to be serialization,
> >
> > smp_rmb() does that, and that's 'free' on x86. Because x86 doesn't do
> > read reordering.
> >
> >> the destination operand
> >> receives a write cycle without regard to the result of
> >> the comparison, which can help us to reduce the penalty
> >> from load instruction roll back.
> >
> > And that makes me think I'm not understanding what you're getting at. If
> > you need to force memory order, a "fence" (or smp_mb()) would still be
> > cheaper than endlessly pulling the line into exclusive state for no
> > reason, right?
> 
> Peter,
> 
> we tested instruction lfence, but we hard to see any benefit, lfence
> only force load instruction ,
> but load instruction still will rollback ,actually cmpxchg behavior is
> more like write operation,
> so we choose it.

But why? I'm just not getting this.

Also LOCK CMPXCHG is 24 cycles when hot, that's almost as bad as
a pipeline flush, and it can be many times worse when it needs to
actually fetch memory from further than L1.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1252479 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

2015-10-20 17:16 GMT+08:00 Peter Zijlstra <peterz@infradead.org>:
> On Tue, Oct 20, 2015 at 11:24:02AM +0800, Ling Ma wrote:
>> 2015-10-19 17:46 GMT+08:00 Peter Zijlstra <peterz@infradead.org>:
>> > On Mon, Oct 19, 2015 at 10:27:22AM +0800, ling.ma.program@gmail.com wrote:
>> >> From: Ma Ling <ling.ml@alibaba-inc.com>
>> >>
>> >> All load instructions can run speculatively but they have to follow
>> >> memory order rule in multiple cores as below:
>> >> _x = _y = 0
>> >>
>> >> Processor 0                           Processor 1
>> >>
>> >> mov r1, [ _y]  //M1                   mov [ _x], 1  //M3
>> >> mov r2, [ _x]  //M2                   mov [ _y], 1  //M4
>> >>
>> >> If r1 = 1, r2 must be 1
>> >>
>> >> In order to guarantee above rule, although Processor 0 execute
>> >> M1 and M2 instruction out of order, they are kept in ROB,
>> >> when load buffer for _x in Processor 0 received the update
>> >> message from Processor 1, Processor 0 need to roll back
>> >> from M2 instruction, which will flush the whole pipeline,
>> >> the latency is over the penalty from branch prediction miss.
>> >>
>> >> In this patch we use lock cmpxchg instruction to force load
>> >
>> > "lock cmpxchg" makes me think you're working on x86.
>> >
>> >> instructions to be serialization,
>> >
>> > smp_rmb() does that, and that's 'free' on x86. Because x86 doesn't do
>> > read reordering.
>> >
>> >> the destination operand
>> >> receives a write cycle without regard to the result of
>> >> the comparison, which can help us to reduce the penalty
>> >> from load instruction roll back.
>> >
>> > And that makes me think I'm not understanding what you're getting at. If
>> > you need to force memory order, a "fence" (or smp_mb()) would still be
>> > cheaper than endlessly pulling the line into exclusive state for no
>> > reason, right?
>>
>> Peter,
>>
>> we tested instruction lfence, but we hard to see any benefit, lfence
>> only force load instruction ,
>> but load instruction still will rollback ,actually cmpxchg behavior is
>> more like write operation,
>> so we choose it.
>
> But why? I'm just not getting this.
>
> Also LOCK CMPXCHG is 24 cycles when hot, that's almost as bad as
> a pipeline flush, and it can be many times worse when it needs to
> actually fetch memory from further than L1.

We will clarify the root cause about this question soon.

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

[toc] | [prev] | [next] | [standalone]

#1250942 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

On 10/18/2015 10:27 PM, ling.ma.program@gmail.com wrote:
> From: Ma Ling<ling.ml@alibaba-inc.com>
>
> All load instructions can run speculatively but they have to follow
> memory order rule in multiple cores as below:
> _x = _y = 0
>
> Processor 0				Processor 1
>
> mov r1, [ _y]  //M1			mov [ _x], 1  //M3
> mov r2, [ _x]  //M2			mov [ _y], 1  //M4
>
> If r1 = 1, r2 must be 1
>
> In order to guarantee above rule, although Processor 0 execute
> M1 and M2 instruction out of order, they are kept in ROB,
> when load buffer for _x in Processor 0 received the update
> message from Processor 1, Processor 0 need to roll back
> from M2 instruction, which will flush the whole pipeline,
> the latency is over the penalty from branch prediction miss.
>
> In this patch we use lock cmpxchg instruction to force load
> instructions to be serialization, the destination operand
> receives a write cycle without regard to the result of
> the comparison, which can help us to reduce the penalty
> from load instruction roll back.
>
> Our experiment indicates the performance can be improved by 10%~15%
> for 2 and 3 threads cases, the conflicts from lock cache line
> spend them most of the time.

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

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

>
> Thanks
> Ling
>
> Signed-off-by: Ma Ling<ling.ml@alibaba-inc.com>
> ---
>   kernel/locking/qspinlock.c |   43 ++++++++++++++++++-------------------------
>   1 files changed, 18 insertions(+), 25 deletions(-)
>
> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
> index 87e9ce6..16421f2 100644
> --- a/kernel/locking/qspinlock.c
> +++ b/kernel/locking/qspinlock.c
> @@ -332,25 +332,14 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
>   	if (new == _Q_LOCKED_VAL)
>   		return;
>
> -	/*
> -	 * we're pending, wait for the owner to go away.
> -	 *
> -	 * *,1,1 ->  *,1,0
> +	/* we're waiting, and get lock owner
>   	 *
> -	 * this wait loop must be a load-acquire such that we match the
> -	 * store-release that clears the locked bit and create lock
> -	 * sequentiality; this is because not all clear_pending_set_locked()
> -	 * implementations imply full barriers.
> +	 * *,1,* ->  *,0,1
>   	 */
> -	while ((val = smp_load_acquire(&lock->val.counter))&  _Q_LOCKED_MASK)
> +	while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending,
> +		_Q_PENDING_VAL, _Q_LOCKED_VAL) != _Q_PENDING_VAL)
>   		cpu_relax();
> -
> -	/*
> -	 * take ownership and clear the pending bit.
> -	 *
> -	 * *,1,0 ->  *,0,1
> -	 */
> -	clear_pending_set_locked(lock);
> +
>   	return;
>
>   	/*
> @@ -399,17 +388,21 @@ queue:
>   	 * we're at the head of the waitqueue, wait for the owner&  pending to
>   	 * go away.
>   	 *
> -	 * *,x,y ->  *,0,0
> -	 *
> -	 * this wait loop must use a load-acquire such that we match the
> -	 * store-release that clears the locked bit and create lock
> -	 * sequentiality; this is because the set_locked() function below
> -	 * does not imply a full barrier.
> -	 *
> +	 * *,x,y ->  *,0,1
>   	 */
>   	pv_wait_head(lock, node);
> -	while ((val = smp_load_acquire(&lock->val.counter))&  _Q_LOCKED_PENDING_MASK)
> +	next = READ_ONCE(node->next);
> +	while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending, 0,

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

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

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

> +
> +	val = smp_load_acquire(&lock->val.counter);
> +	tail = tail | _Q_LOCKED_VAL;
>
>   	/*
>   	 * claim the lock:
> @@ -423,7 +416,6 @@ queue:
>   	 */
>   	for (;;) {
>   		if (val != tail) {
> -			set_locked(lock);
>   			break;
>   		}
>   		old = atomic_cmpxchg(&lock->val, val, _Q_LOCKED_VAL);
> @@ -439,6 +431,7 @@ queue:
>   	while (!(next = READ_ONCE(node->next)))
>   		cpu_relax();
>
> +next_node:
>   	arch_mcs_spin_unlock_contended(&next->locked);
>   	pv_kick_node(lock, next);
>

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

[toc] | [prev] | [next] | [standalone]

#1251278 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

2015-10-20 1:18 GMT+08:00 Waiman Long <waiman.long@hpe.com>:
> On 10/18/2015 10:27 PM, ling.ma.program@gmail.com wrote:
>>
>> From: Ma Ling<ling.ml@alibaba-inc.com>
>>
>> All load instructions can run speculatively but they have to follow
>> memory order rule in multiple cores as below:
>> _x = _y = 0
>>
>> Processor 0                             Processor 1
>>
>> mov r1, [ _y]  //M1                     mov [ _x], 1  //M3
>> mov r2, [ _x]  //M2                     mov [ _y], 1  //M4
>>
>> If r1 = 1, r2 must be 1
>>
>> In order to guarantee above rule, although Processor 0 execute
>> M1 and M2 instruction out of order, they are kept in ROB,
>> when load buffer for _x in Processor 0 received the update
>> message from Processor 1, Processor 0 need to roll back
>> from M2 instruction, which will flush the whole pipeline,
>> the latency is over the penalty from branch prediction miss.
>>
>> In this patch we use lock cmpxchg instruction to force load
>> instructions to be serialization, the destination operand
>> receives a write cycle without regard to the result of
>> the comparison, which can help us to reduce the penalty
>> from load instruction roll back.
>>
>> Our experiment indicates the performance can be improved by 10%~15%
>> for 2 and 3 threads cases, the conflicts from lock cache line
>> spend them most of the time.
>
>
> What kind of performance test were you running? With the right timing, it is
> possible that you see some performance gain. However, if the lock hold time
> is longer so that a fair number of cmpxchg instructions have to be executed
> before it can get the lock, you may see a performance degradation especially
> if the lock holder needs to access the lock cacheline.
>
> In general, we try to avoid this kind of cmpxchg loop unless we are sure
> that at most a few iterations of the loop may happen.

Waiman,

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



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

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


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



 all cost time is 103904620

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



 all cost time is 104351876

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



 all cost time is 118599784

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



 all cost time is 103064024

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



 all cost time is 103389696

Totally cost time is 533310000

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

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



 all cost time is 67081220

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



 all cost time is 97640708

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



 all cost time is 96439612

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



 all cost time is 66699296

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



 all cost time is 96464800



Totally cost time is 424325636



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



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



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



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



 all cost time is 174266128

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



 all cost time is 205053924

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



 all cost time is 160165124

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



 all cost time is 173241552

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



 all cost time is 205765008

Totally cost time is 918491736



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

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



 all cost time is 113410044

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



 all cost time is 116293104

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



 all cost time is 116064256

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



 all cost time is 189320876

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



 all cost time is 123735352

Totally cost time is 658823632



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




>
>>
>> Thanks
>> Ling
>>
>> Signed-off-by: Ma Ling<ling.ml@alibaba-inc.com>
>> ---
>>   kernel/locking/qspinlock.c |   43
>> ++++++++++++++++++-------------------------
>>   1 files changed, 18 insertions(+), 25 deletions(-)
>>
>> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
>> index 87e9ce6..16421f2 100644
>> --- a/kernel/locking/qspinlock.c
>> +++ b/kernel/locking/qspinlock.c
>> @@ -332,25 +332,14 @@ void queued_spin_lock_slowpath(struct qspinlock
>> *lock, u32 val)
>>         if (new == _Q_LOCKED_VAL)
>>                 return;
>>
>> -       /*
>> -        * we're pending, wait for the owner to go away.
>> -        *
>> -        * *,1,1 ->  *,1,0
>> +       /* we're waiting, and get lock owner
>>          *
>> -        * this wait loop must be a load-acquire such that we match the
>> -        * store-release that clears the locked bit and create lock
>> -        * sequentiality; this is because not all
>> clear_pending_set_locked()
>> -        * implementations imply full barriers.
>> +        * *,1,* ->  *,0,1
>>          */
>> -       while ((val = smp_load_acquire(&lock->val.counter))&
>> _Q_LOCKED_MASK)
>> +       while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending,
>> +               _Q_PENDING_VAL, _Q_LOCKED_VAL) != _Q_PENDING_VAL)
>>                 cpu_relax();
>> -
>> -       /*
>> -        * take ownership and clear the pending bit.
>> -        *
>> -        * *,1,0 ->  *,0,1
>> -        */
>> -       clear_pending_set_locked(lock);
>> +
>>         return;
>>
>>         /*
>> @@ -399,17 +388,21 @@ queue:
>>          * we're at the head of the waitqueue, wait for the owner&
>> pending to
>>          * go away.
>>          *
>> -        * *,x,y ->  *,0,0
>> -        *
>> -        * this wait loop must use a load-acquire such that we match the
>> -        * store-release that clears the locked bit and create lock
>> -        * sequentiality; this is because the set_locked() function below
>> -        * does not imply a full barrier.
>> -        *
>> +        * *,x,y ->  *,0,1
>>          */
>>         pv_wait_head(lock, node);
>> -       while ((val = smp_load_acquire(&lock->val.counter))&
>> _Q_LOCKED_PENDING_MASK)
>> +       next = READ_ONCE(node->next);
>> +       while (cmpxchg(&((struct __qspinlock *)lock)->locked_pending, 0,
>
>
> The locked_pending field isn't valid if _Q_PENDING_BITS != 8. So it won't
> work if NR_CPUS is 16k or more.
>
>> +               _Q_LOCKED_VAL) != 0) {
>> +               next = READ_ONCE(node->next);
>>                 cpu_relax();
>> +       }
>> +
>> +       if (next)
>> +               goto next_node;
>
>
> I did notice a slight performance benefit by reading the next pointer early
> in light load cases myself. However, it is a very minor improvement that I
> haven't actively pursued it.

We use "next" to avoid smp_load_acquire(&lock->val.counter)
instruction rollback.

>
>> +
>> +       val = smp_load_acquire(&lock->val.counter);
>> +       tail = tail | _Q_LOCKED_VAL;
>>
>>         /*
>>          * claim the lock:
>> @@ -423,7 +416,6 @@ queue:
>>          */
>>         for (;;) {
>>                 if (val != tail) {
>> -                       set_locked(lock);
>>                         break;
>>                 }
>>                 old = atomic_cmpxchg(&lock->val, val, _Q_LOCKED_VAL);
>> @@ -439,6 +431,7 @@ queue:
>>         while (!(next = READ_ONCE(node->next)))
>>                 cpu_relax();
>>
>> +next_node:
>>         arch_mcs_spin_unlock_contended(&next->locked);
>>         pv_kick_node(lock, next);
>>
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1251964 — Re: [RFC PATCH] qspinlock: Improve performance by reducing load instruction rollback

On 10/19/2015 11:12 PM, Ling Ma wrote:
> 2015-10-20 1:18 GMT+08:00 Waiman Long<waiman.long@hpe.com>:
>> On 10/18/2015 10:27 PM, ling.ma.program@gmail.com wrote:
>>> From: Ma Ling<ling.ml@alibaba-inc.com>
>>>
>>> All load instructions can run speculatively but they have to follow
>>> memory order rule in multiple cores as below:
>>> _x = _y = 0
>>>
>>> Processor 0                             Processor 1
>>>
>>> mov r1, [ _y]  //M1                     mov [ _x], 1  //M3
>>> mov r2, [ _x]  //M2                     mov [ _y], 1  //M4
>>>
>>> If r1 = 1, r2 must be 1
>>>
>>> In order to guarantee above rule, although Processor 0 execute
>>> M1 and M2 instruction out of order, they are kept in ROB,
>>> when load buffer for _x in Processor 0 received the update
>>> message from Processor 1, Processor 0 need to roll back
>>> from M2 instruction, which will flush the whole pipeline,
>>> the latency is over the penalty from branch prediction miss.
>>>
>>> In this patch we use lock cmpxchg instruction to force load
>>> instructions to be serialization, the destination operand
>>> receives a write cycle without regard to the result of
>>> the comparison, which can help us to reduce the penalty
>>> from load instruction roll back.
>>>
>>> Our experiment indicates the performance can be improved by 10%~15%
>>> for 2 and 3 threads cases, the conflicts from lock cache line
>>> spend them most of the time.
>>
>> What kind of performance test were you running? With the right timing, it is
>> possible that you see some performance gain. However, if the lock hold time
>> is longer so that a fair number of cmpxchg instructions have to be executed
>> before it can get the lock, you may see a performance degradation especially
>> if the lock holder needs to access the lock cacheline.
>>
>> In general, we try to avoid this kind of cmpxchg loop unless we are sure
>> that at most a few iterations of the loop may happen.
> Waiman,
>
> The machine is Haswell (2699 V3, COD off, HT on, 2 sockets)
> (we have sent test module in separate email)
>
>
>
> A.      Data is located with lock in one cache line On 2 threads cases
> (only write struct member data_a)
>
>   1.       Load version test 5 times, the cost time is below:
>
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 103904620
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 104351876
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 118599784
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 103064024
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 103389696
>
> Totally cost time is 533310000
>
> 2.       Lock cmpxchg version test 5 times, the cost time is below:
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 67081220
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 97640708
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 96439612
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 66699296
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 96464800
>
>
>
> Totally cost time is 424325636
>
>
>
> Above data shows lock cmpxchg is better about average 25% (533310000/424325636)
>
>
>
> B.      Data is located with lock in different cache line On 2 threads
> cases(only write struct member data_b)
>
>
>
> 1.       Load version test 5 times, the cost time is below:
>
>
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 174266128
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 205053924
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 160165124
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 173241552
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 205765008
>
> Totally cost time is 918491736
>
>
>
> 2.       Lock cmpxchg version test 5 times, the cost time is below:
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 113410044
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 116293104
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 116064256
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 189320876
>
> [root@localhost spinlock]# insmod dummy.ko; rmmod dummy;dmesg -c
>
>
>
>   all cost time is 123735352
>
> Totally cost time is 658823632
>
>
>
> Above data shows lock cmpxchg is better about average 39%  (918491736/658823632)
>
>

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

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

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web