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

Groups > linux.kernel > #1431127 > unrolled thread

[PATCH] locking/osq: Drop the overload of osq lock

Back to article view | Back to linux.kernel

Contents

  [PATCH] locking/osq: Drop the overload of osq lock Pan Xinhui <xinhui.pan@linux.vnet.ibm.com> - 2016-06-25 15:50 +0200
    Re: [PATCH] locking/osq: Drop the overload of osq lock Peter Zijlstra <peterz@infradead.org> - 2016-06-25 16:30 +0200
      Re: [PATCH] locking/osq: Drop the overload of osq lock Boqun Feng <boqun.feng@gmail.com> - 2016-06-25 17:20 +0200
        Re: [PATCH] locking/osq: Drop the overload of osq lock Peter Zijlstra <peterz@infradead.org> - 2016-06-25 18:10 +0200
          Re: [PATCH] locking/osq: Drop the overload of osq lock Peter Zijlstra <peterz@infradead.org> - 2016-06-25 18:20 +0200
            Re: [PATCH] locking/osq: Drop the overload of osq lock panxinhui <xinhui@linux.vnet.ibm.com> - 2016-06-25 19:30 +0200
              Re: [PATCH] locking/osq: Drop the overload of osq lock Peter Zijlstra <peterz@infradead.org> - 2016-06-25 21:20 +0200
                Re: [PATCH] locking/osq: Drop the overload of osq lock panxinhui <xinhui@linux.vnet.ibm.com> - 2016-06-26 07:00 +0200
                  Re: [PATCH] locking/osq: Drop the overload of osq lock Peter Zijlstra <peterz@infradead.org> - 2016-06-27 10:00 +0200
                    Re: [PATCH] locking/osq: Drop the overload of osq lock xinhui <xinhui.pan@linux.vnet.ibm.com> - 2016-06-27 12:30 +0200
          Re: [PATCH] locking/osq: Drop the overload of osq lock Boqun Feng <boqun.feng@gmail.com> - 2016-06-25 18:30 +0200
            Re: [PATCH] locking/osq: Drop the overload of osq lock Peter Zijlstra <peterz@infradead.org> - 2016-06-25 20:30 +0200
        Re: [PATCH] locking/osq: Drop the overload of osq lock Peter Zijlstra <peterz@infradead.org> - 2016-06-25 18:20 +0200
          Re: [PATCH] locking/osq: Drop the overload of osq lock Boqun Feng <boqun.feng@gmail.com> - 2016-06-25 18:50 +0200
            Re: [PATCH] locking/osq: Drop the overload of osq lock panxinhui <xinhui@linux.vnet.ibm.com> - 2016-06-25 19:30 +0200
              Re: [PATCH] locking/osq: Drop the overload of osq lock Peter Zijlstra <peterz@infradead.org> - 2016-06-25 21:30 +0200
                Re: [PATCH] locking/osq: Drop the overload of osq lock Peter Zijlstra <peterz@infradead.org> - 2016-06-25 21:40 +0200
                Re: [PATCH] locking/osq: Drop the overload of osq lock Boqun Feng <boqun.feng@gmail.com> - 2016-06-26 04:30 +0200
                Re: [PATCH] locking/osq: Drop the overload of osq lock panxinhui <xinhui@linux.vnet.ibm.com> - 2016-06-26 07:30 +0200
                  Re: [PATCH] locking/osq: Drop the overload of osq lock Boqun Feng <boqun.feng@gmail.com> - 2016-06-26 08:10 +0200
                    Re: [PATCH] locking/osq: Drop the overload of osq lock panxinhui <xinhui@linux.vnet.ibm.com> - 2016-06-26 09:00 +0200
                      Re: [PATCH] locking/osq: Drop the overload of osq lock Boqun Feng <boqun.feng@gmail.com> - 2016-06-26 16:10 +0200
                        Re: [PATCH] locking/osq: Drop the overload of osq lock panxinhui <xinhui@linux.vnet.ibm.com> - 2016-06-26 18:00 +0200
                    Re: [PATCH] locking/osq: Drop the overload of osq lock Boqun Feng <boqun.feng@gmail.com> - 2016-06-26 09:00 +0200
                      Re: [PATCH] locking/osq: Drop the overload of osq lock panxinhui <xinhui@linux.vnet.ibm.com> - 2016-06-26 09:10 +0200
                        Re: [PATCH] locking/osq: Drop the overload of osq lock Boqun Feng <boqun.feng@gmail.com> - 2016-06-26 16:30 +0200
                          Re: [PATCH] locking/osq: Drop the overload of osq lock panxinhui <xinhui@linux.vnet.ibm.com> - 2016-06-26 17:20 +0200
                      Re: [PATCH] locking/osq: Drop the overload of osq lock Boqun Feng <boqun.feng@gmail.com> - 2016-06-27 08:50 +0200
                        Re: [PATCH] locking/osq: Drop the overload of osq lock xinhui <xinhui.pan@linux.vnet.ibm.com> - 2016-06-27 09:40 +0200
                        Re: [PATCH] locking/osq: Drop the overload of osq lock Peter Zijlstra <peterz@infradead.org> - 2016-06-27 10:20 +0200
                          Re: [PATCH] locking/osq: Drop the overload of osq lock Boqun Feng <boqun.feng@gmail.com> - 2016-06-27 12:30 +0200

Page 1 of 2  [1] 2  Next page →

#1431127 — [PATCH] locking/osq: Drop the overload of osq lock

An over-committed guest with more vCPUs than pCPUs has a heavy overload
in osq_lock().

This is because vCPU A hold the osq lock and yield out, vCPU B wait
per_cpu node->locked to be set. IOW, vCPU B wait vCPU A to run and
unlock the osq lock. Even there is need_resched(), it did not help on
such scenario.

To fix such bad issue, add a threshold in one while-loop of osq_lock().
The value of threshold is somehow equal to SPIN_THRESHOLD.

perf record -a perf bench sched messaging -g 400 -p && perf report

before patch:
18.09%  sched-messaging  [kernel.vmlinux]  [k] osq_lock
12.28%  sched-messaging  [kernel.vmlinux]  [k] rwsem_spin_on_owner
 5.27%  sched-messaging  [kernel.vmlinux]  [k] mutex_unlock
 3.89%  sched-messaging  [kernel.vmlinux]  [k] wait_consider_task
 3.64%  sched-messaging  [kernel.vmlinux]  [k] _raw_write_lock_irq
 3.41%  sched-messaging  [kernel.vmlinux]  [k] mutex_spin_on_owner.is
 2.49%  sched-messaging  [kernel.vmlinux]  [k] system_call

after patch:
7.62%  sched-messaging  [kernel.kallsyms]  [k] wait_consider_task
7.30%  sched-messaging  [kernel.kallsyms]  [k] _raw_write_lock_irq
5.93%  sched-messaging  [kernel.kallsyms]  [k] mutex_unlock
5.74%  sched-messaging  [unknown]          [H] 0xc000000000077590
4.37%  sched-messaging  [kernel.kallsyms]  [k] __copy_tofrom_user_powe
2.58%  sched-messaging  [kernel.kallsyms]  [k] system_call

Signed-off-by: Pan Xinhui <xinhui.pan@linux.vnet.ibm.com>
---
 kernel/locking/osq_lock.c | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

diff --git a/kernel/locking/osq_lock.c b/kernel/locking/osq_lock.c
index 05a3785..922fe5d 100644
--- a/kernel/locking/osq_lock.c
+++ b/kernel/locking/osq_lock.c
@@ -81,12 +81,16 @@ osq_wait_next(struct optimistic_spin_queue *lock,
 	return next;
 }
 
+/* The threahold should take nearly 0.5ms on most archs */
+#define OSQ_SPIN_THRESHOLD (1 << 15)
+
 bool osq_lock(struct optimistic_spin_queue *lock)
 {
 	struct optimistic_spin_node *node = this_cpu_ptr(&osq_node);
 	struct optimistic_spin_node *prev, *next;
 	int curr = encode_cpu(smp_processor_id());
 	int old;
+	int loops;
 
 	node->locked = 0;
 	node->next = NULL;
@@ -118,8 +122,14 @@ bool osq_lock(struct optimistic_spin_queue *lock)
 	while (!READ_ONCE(node->locked)) {
 		/*
 		 * If we need to reschedule bail... so we can block.
+		 * An over-committed guest with more vCPUs than pCPUs
+		 * might fall in this loop and cause a huge overload.
+		 * This is because vCPU A(prev) hold the osq lock and yield out,
+		 * vCPU B(node) wait ->locked to be set, IOW, wait till
+		 * vCPU A run and unlock the osq lock.
+		 * NOTE that vCPU A and vCPU B might run on same physical cpu.
 		 */
-		if (need_resched())
+		if (need_resched() || loops++ == OSQ_SPIN_THRESHOLD)
 			goto unqueue;
 
 		cpu_relax_lowlatency();
-- 
2.4.11

[toc] | [next] | [standalone]

#1431130

On Sat, Jun 25, 2016 at 01:42:03PM -0400, Pan Xinhui wrote:
> An over-committed guest with more vCPUs than pCPUs has a heavy overload
> in osq_lock().
> 
> This is because vCPU A hold the osq lock and yield out, vCPU B wait
> per_cpu node->locked to be set. IOW, vCPU B wait vCPU A to run and
> unlock the osq lock. Even there is need_resched(), it did not help on
> such scenario.
> 
> To fix such bad issue, add a threshold in one while-loop of osq_lock().
> The value of threshold is somehow equal to SPIN_THRESHOLD.

Blergh, virt ...

So yes, lock holder preemption sucks. You would also want to limit the
immediate spin on owner.

Also; I really hate these random number spin-loop thresholds.

Is it at all possible to get feedback from your LPAR stuff that the vcpu
was preempted? Because at that point we can add do something like:


	int vpc = vcpu_preempt_count();

	...

	for (;;) {

		/* the big spin loop */

		if (need_resched() || vpc != vcpu_preempt_count())
			/* bail */

	}


With a default implementation like:

static inline int vcpu_preempt_count(void)
{
	return 0;
}

So the compiler can make it all go away.


But on virt muck it would stop spinning the moment the vcpu gets
preempted, which is the right moment I'm thinking.

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

#1431143

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

On Sat, Jun 25, 2016 at 04:24:47PM +0200, Peter Zijlstra wrote:
> On Sat, Jun 25, 2016 at 01:42:03PM -0400, Pan Xinhui wrote:
> > An over-committed guest with more vCPUs than pCPUs has a heavy overload
> > in osq_lock().
> > 
> > This is because vCPU A hold the osq lock and yield out, vCPU B wait
> > per_cpu node->locked to be set. IOW, vCPU B wait vCPU A to run and
> > unlock the osq lock. Even there is need_resched(), it did not help on
> > such scenario.
> > 
> > To fix such bad issue, add a threshold in one while-loop of osq_lock().
> > The value of threshold is somehow equal to SPIN_THRESHOLD.
> 
> Blergh, virt ...
> 
> So yes, lock holder preemption sucks. You would also want to limit the
> immediate spin on owner.
> 
> Also; I really hate these random number spin-loop thresholds.
> 
> Is it at all possible to get feedback from your LPAR stuff that the vcpu
> was preempted? Because at that point we can add do something like:
> 

Good point!

> 
> 	int vpc = vcpu_preempt_count();
> 
> 	...
> 
> 	for (;;) {
> 
> 		/* the big spin loop */
> 
> 		if (need_resched() || vpc != vcpu_preempt_count())

So on PPC, we have lppaca::yield_count to detect when an vcpu is
preempted, if the yield_count is even, the vcpu is running, otherwise it
is preempted(__spin_yield() is a user of this).

Therefore it makes more sense we

		if (need_resched() || vcpu_is_preempted(old))

here, and implement vcpu_is_preempted() on PPC as

bool vcpu_is_preempted(int cpu)
{
	return !!(be32_to_cpu(lppaca_of(cpu).yield_count) & 1)
}

Thoughts?

Regards,
Boqun

> 			/* bail */
> 
> 	}
> 
> 
> With a default implementation like:
> 
> static inline int vcpu_preempt_count(void)
> {
> 	return 0;
> }
> 
> So the compiler can make it all go away.
> 
> 
> But on virt muck it would stop spinning the moment the vcpu gets
> preempted, which is the right moment I'm thinking.

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

#1431156

On Sat, Jun 25, 2016 at 11:21:30PM +0800, Boqun Feng wrote:
> > 
> > 	int vpc = vcpu_preempt_count();
> > 
> > 	...
> > 
> > 	for (;;) {
> > 
> > 		/* the big spin loop */
> > 
> > 		if (need_resched() || vpc != vcpu_preempt_count())
> 
> So on PPC, we have lppaca::yield_count to detect when an vcpu is

Which sounds like just the value we want.. And I suspect that on x86 KVM
and Xen have similar numbers stashed away someplace.

> preempted, if the yield_count is even, the vcpu is running, otherwise it
> is preempted(__spin_yield() is a user of this).
> 
> Therefore it makes more sense we
> 
> 		if (need_resched() || vcpu_is_preempted(old))
> 
> here, and implement vcpu_is_preempted() on PPC as
> 
> bool vcpu_is_preempted(int cpu)
> {
> 	return !!(be32_to_cpu(lppaca_of(cpu).yield_count) & 1)
> }
> 
> Thoughts?

That works here, but it would not work for the need_resched() in
mutex_spin_on_owner() and mutex_optimistic_spin() which need equal
treatment.

Because those too we want to limit.

The count thing, while a little more cumbersome, is more widely
applicable than just the one OSQ case where we happen to have a cpu
number.

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

#1431158

On Sat, Jun 25, 2016 at 06:09:22PM +0200, Peter Zijlstra wrote:
> That works here, but it would not work for the need_resched() in
> mutex_spin_on_owner() and mutex_optimistic_spin() which need equal
> treatment.
> 
> Because those too we want to limit.
> 
> The count thing, while a little more cumbersome, is more widely
> applicable than just the one OSQ case where we happen to have a cpu
> number.

Although I suppose that mutex_spin_on_owner() (and with that the rsem
variant) could use task_cpu(lock->owner) once we've established that the
owner pointer is still valid.

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

#1431174

> 在 2016年6月26日，00:13，Peter Zijlstra <peterz@infradead.org> 写道：
> 
> On Sat, Jun 25, 2016 at 06:09:22PM +0200, Peter Zijlstra wrote:
>> That works here, but it would not work for the need_resched() in
>> mutex_spin_on_owner() and mutex_optimistic_spin() which need equal
>> treatment.
>> 
>> Because those too we want to limit.
>> 
>> The count thing, while a little more cumbersome, is more widely
>> applicable than just the one OSQ case where we happen to have a cpu
>> number.
> 
> Although I suppose that mutex_spin_on_owner() (and with that the rsem
> variant) could use task_cpu(lock->owner) once we've established that the
> owner pointer is still valid.
> 
> 
yes, What I am going to fix next is these XXX_spin_on_owner, including  mutex_spin_on_owner, rwsem_spin_on_owner ….

by the way I still think mutex_unlock has a big overload too. 

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

#1431203

On Sun, Jun 26, 2016 at 01:27:51AM +0800, panxinhui wrote:

> by the way I still think mutex_unlock has a big overload too. 

Do you mean overhead?

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

#1431331

> 在 2016年6月26日，03:12，Peter Zijlstra <peterz@infradead.org> 写道：
> 
> On Sun, Jun 26, 2016 at 01:27:51AM +0800, panxinhui wrote:
> 
>> by the way I still think mutex_unlock has a big overload too. 
> 
> Do you mean overhead?
> 
oh, maybe you are right. 
mutex_unlock ’s implementation uses inc_return variant on  ppc, and that’s expensive. I am thinking of using  cmpxchg instead. 

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

#1431790

On Sun, Jun 26, 2016 at 12:59:01PM +0800, panxinhui wrote:
> 
> > 在 2016年6月26日，03:12，Peter Zijlstra <peterz@infradead.org> 写道：
> > 
> > On Sun, Jun 26, 2016 at 01:27:51AM +0800, panxinhui wrote:
> > 
> >> by the way I still think mutex_unlock has a big overload too. 
> > 
> > Do you mean overhead?
> > 
> oh, maybe you are right. 

> mutex_unlock ’s implementation uses inc_return variant on  ppc, and
> that’s expensive. I am thinking of using  cmpxchg instead. 

That statement doesn't make any sense. PPC is an LL/SC arch, inc_return
and cmpxchg are the 'same' LL/SC loop.

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

#1431902

On 2016年06月27日 15:55, Peter Zijlstra wrote:
> On Sun, Jun 26, 2016 at 12:59:01PM +0800, panxinhui wrote:
>>
>>> 在 2016年6月26日，03:12，Peter Zijlstra <peterz@infradead.org> 写道：
>>>
>>> On Sun, Jun 26, 2016 at 01:27:51AM +0800, panxinhui wrote:
>>>
>>>> by the way I still think mutex_unlock has a big overload too.
>>>
>>> Do you mean overhead?
>>>
>> oh, maybe you are right.
>
>> mutex_unlock ’s implementation uses inc_return variant on  ppc, and
>> that’s expensive. I am thinking of using  cmpxchg instead.
>
> That statement doesn't make any sense. PPC is an LL/SC arch, inc_return
> and cmpxchg are the 'same' LL/SC loop.
>
This is a little optimize.
if there are lock waiters, the lockval is minus X, when we call unlock, it will inc the lockval, if it is <= 0, enter unlockslowpath to wakeup the waiters, and set lockval to 1 in the slowpath.
SO there is no need to inc lockval if it is already a minus number. therefore we can save one store or loads/stores in LL/SC loops

the base idea is from code below,
if (!atomic_read(&lk)//no need to call atomic_inc_return which is expensive.
	atomic_inc_return(&lk))

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

#1431164

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

On Sat, Jun 25, 2016 at 06:09:22PM +0200, Peter Zijlstra wrote:
> On Sat, Jun 25, 2016 at 11:21:30PM +0800, Boqun Feng wrote:
> > > 
> > > 	int vpc = vcpu_preempt_count();
> > > 
> > > 	...
> > > 
> > > 	for (;;) {
> > > 
> > > 		/* the big spin loop */
> > > 
> > > 		if (need_resched() || vpc != vcpu_preempt_count())
> > 
> > So on PPC, we have lppaca::yield_count to detect when an vcpu is
> 
> Which sounds like just the value we want.. And I suspect that on x86 KVM
> and Xen have similar numbers stashed away someplace.
> 
> > preempted, if the yield_count is even, the vcpu is running, otherwise it
> > is preempted(__spin_yield() is a user of this).
> > 
> > Therefore it makes more sense we
> > 
> > 		if (need_resched() || vcpu_is_preempted(old))
> > 
> > here, and implement vcpu_is_preempted() on PPC as
> > 
> > bool vcpu_is_preempted(int cpu)
> > {
> > 	return !!(be32_to_cpu(lppaca_of(cpu).yield_count) & 1)
> > }
> > 
> > Thoughts?
> 
> That works here, but it would not work for the need_resched() in
> mutex_spin_on_owner() and mutex_optimistic_spin() which need equal
> treatment.
> 
> Because those too we want to limit.
> 
> The count thing, while a little more cumbersome, is more widely
> applicable than just the one OSQ case where we happen to have a cpu
> number.
> 

But if we don't have a cpu number, which vcpu's preemption are we
trying to detect? I think the logic here is that if _this_ vcpu sees the
_owner_ vcpu is preempted, it should just stop spinning. Therefore, we
need to know the owner cpu number.

Am I missing something here?

Regards,
Boqun

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

#1431193

On Sun, Jun 26, 2016 at 12:28:13AM +0800, Boqun Feng wrote:
> On Sat, Jun 25, 2016 at 06:09:22PM +0200, Peter Zijlstra wrote:
> > That works here, but it would not work for the need_resched() in
> > mutex_spin_on_owner() and mutex_optimistic_spin() which need equal
> > treatment.
> > 
> > Because those too we want to limit.
> > 
> > The count thing, while a little more cumbersome, is more widely
> > applicable than just the one OSQ case where we happen to have a cpu
> > number.
> > 
> 
> But if we don't have a cpu number, which vcpu's preemption are we
> trying to detect? 

_this_ vcpu's preemption. If the yield count of this cpu changes, we
know this vcpu has been scheduled and we should stop spinning.

This is similar to the need_resched() case, which check is _this_ cpu
should reschedule.

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

#1431162

On Sat, Jun 25, 2016 at 11:21:30PM +0800, Boqun Feng wrote:
> So on PPC, we have lppaca::yield_count to detect when an vcpu is
> preempted, if the yield_count is even, the vcpu is running, otherwise it
> is preempted(__spin_yield() is a user of this).
> 
> Therefore it makes more sense we
> 
> 		if (need_resched() || vcpu_is_preempted(old))
> 
> here, and implement vcpu_is_preempted() on PPC as
> 
> bool vcpu_is_preempted(int cpu)
> {
> 	return !!(be32_to_cpu(lppaca_of(cpu).yield_count) & 1)
> }
> 
> Thoughts?

Would that not have issues where the owner cpu is kept running but the
spinner (ie. _this_ vcpu) gets preempted? I would think that in that
case we too want to stop spinning.

Although, if all vcpus are scheduled equal, it might not matter on
average.

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

#1431168

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

On Sat, Jun 25, 2016 at 06:15:40PM +0200, Peter Zijlstra wrote:
> On Sat, Jun 25, 2016 at 11:21:30PM +0800, Boqun Feng wrote:
> > So on PPC, we have lppaca::yield_count to detect when an vcpu is
> > preempted, if the yield_count is even, the vcpu is running, otherwise it
> > is preempted(__spin_yield() is a user of this).
> > 
> > Therefore it makes more sense we
> > 
> > 		if (need_resched() || vcpu_is_preempted(old))
> > 
> > here, and implement vcpu_is_preempted() on PPC as
> > 
> > bool vcpu_is_preempted(int cpu)
> > {
> > 	return !!(be32_to_cpu(lppaca_of(cpu).yield_count) & 1)
> > }
> > 
> > Thoughts?
> 
> Would that not have issues where the owner cpu is kept running but the
> spinner (ie. _this_ vcpu) gets preempted? I would think that in that
> case we too want to stop spinning.
> 

I don't think we want(or need) to stop the spinning of _this_ vcpu in
that case? Because it has already been preempted, when it gets back to
run, the owner may still be running and haven't set ->locked to 1 yet,
which means spinning on this vcpu is still worthwhile.

I think the proper logic here is that in the optimistic spin queue, if
any one found its predecessor's vcpu was preempted, it should stop
spinning, because it's very likely that it would not see ->locked
becoming 1 in a short time.

> Although, if all vcpus are scheduled equal, it might not matter on
> average.

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

#1431173

> 在 2016年6月26日，00:45，Boqun Feng <boqun.feng@gmail.com> 写道：
> 
> On Sat, Jun 25, 2016 at 06:15:40PM +0200, Peter Zijlstra wrote:
>> On Sat, Jun 25, 2016 at 11:21:30PM +0800, Boqun Feng wrote:
>>> So on PPC, we have lppaca::yield_count to detect when an vcpu is
>>> preempted, if the yield_count is even, the vcpu is running, otherwise it
>>> is preempted(__spin_yield() is a user of this).
>>> 
>>> Therefore it makes more sense we
>>> 
>>> 		if (need_resched() || vcpu_is_preempted(old))
>>> 
>>> here, and implement vcpu_is_preempted() on PPC as
>>> 
>>> bool vcpu_is_preempted(int cpu)
>>> {
>>> 	return !!(be32_to_cpu(lppaca_of(cpu).yield_count) & 1)
>>> }
>>> 
>>> Thoughts?
>> 
>> Would that not have issues where the owner cpu is kept running but the
>> spinner (ie. _this_ vcpu) gets preempted? I would think that in that
>> case we too want to stop spinning.
>> 
> 
do  you mean that the spinner detect itself had yield out during the big spin loop?

It is very possible to happen.  BUT if spinner(on this vcpu) yield out, the next spinner would break the spin loop.
AND if spinner detect itself yield out once, it’s very possible to get the osq lock soon as long as the ower vcpu is running.

SO I think we need just check the owner vcpu’s yield_count.

> I don't think we want(or need) to stop the spinning of _this_ vcpu in
> that case? Because it has already been preempted, when it gets back to
> run, the owner may still be running and haven't set ->locked to 1 yet,
> which means spinning on this vcpu is still worthwhile.
> 

> I think the proper logic here is that in the optimistic spin queue, if
> any one found its predecessor's vcpu was preempted, it should stop
> spinning, because it's very likely that it would not see ->locked
> becoming 1 in a short time.
> 
agree!!!
this  vcpu need yield out too if the owner’s vcpu has yield out.


>> Although, if all vcpus are scheduled equal, it might not matter on
>> average.

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

#1431206

On Sun, Jun 26, 2016 at 01:27:56AM +0800, panxinhui wrote:
> >> Would that not have issues where the owner cpu is kept running but the
> >> spinner (ie. _this_ vcpu) gets preempted? I would think that in that
> >> case we too want to stop spinning.
> >> 
> > 
> do  you mean that the spinner detect itself had yield out during the
> big spin loop?
> 
> It is very possible to happen.  BUT if spinner(on this vcpu) yield
> out, the next spinner would break the spin loop.  AND if spinner
> detect itself yield out once, it’s very possible to get the osq lock
> soon as long as the ower vcpu is running.
> 
> SO I think we need just check the owner vcpu’s yield_count.

I had a quick look at KVM and it looks like it only has
kvm_cpu::preempted, which would suggest the interface boqun proposed.

We'll have to look at many of the other virt platforms as well to see
what they can do.

We could also provide _both_ interfaces and a platform can implement
whichever variant (or both) it can.

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

#1431207

On Sat, Jun 25, 2016 at 09:20:25PM +0200, Peter Zijlstra wrote:
> On Sun, Jun 26, 2016 at 01:27:56AM +0800, panxinhui wrote:
> > >> Would that not have issues where the owner cpu is kept running but the
> > >> spinner (ie. _this_ vcpu) gets preempted? I would think that in that
> > >> case we too want to stop spinning.
> > >> 
> > > 
> > do  you mean that the spinner detect itself had yield out during the
> > big spin loop?
> > 
> > It is very possible to happen.  BUT if spinner(on this vcpu) yield
> > out, the next spinner would break the spin loop.  AND if spinner
> > detect itself yield out once, it’s very possible to get the osq lock
> > soon as long as the ower vcpu is running.
> > 
> > SO I think we need just check the owner vcpu’s yield_count.
> 
> I had a quick look at KVM and it looks like it only has
> kvm_cpu::preempted, which would suggest the interface boqun proposed.

Xen seems to have vcpu_runstate_info::state where any !0 state means its
not running, so that too allows implementing that variant.

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

#1431286

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

On Sat, Jun 25, 2016 at 09:20:25PM +0200, Peter Zijlstra wrote:
> On Sun, Jun 26, 2016 at 01:27:56AM +0800, panxinhui wrote:
> > >> Would that not have issues where the owner cpu is kept running but the
> > >> spinner (ie. _this_ vcpu) gets preempted? I would think that in that
> > >> case we too want to stop spinning.
> > >> 
> > > 
> > do  you mean that the spinner detect itself had yield out during the
> > big spin loop?
> > 
> > It is very possible to happen.  BUT if spinner(on this vcpu) yield
> > out, the next spinner would break the spin loop.  AND if spinner
> > detect itself yield out once, it’s very possible to get the osq lock
> > soon as long as the ower vcpu is running.
> > 
> > SO I think we need just check the owner vcpu’s yield_count.
> 
> I had a quick look at KVM and it looks like it only has
> kvm_cpu::preempted, which would suggest the interface boqun proposed.
> 
> We'll have to look at many of the other virt platforms as well to see
> what they can do.
> 
> We could also provide _both_ interfaces and a platform can implement
> whichever variant (or both) it can.
> 

Make sense ;-)

Lemme cook something for further discussions.

Regards,
Boqun

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

#1431334

> 在 2016年6月26日，03:20，Peter Zijlstra <peterz@infradead.org> 写道：
> 
> On Sun, Jun 26, 2016 at 01:27:56AM +0800, panxinhui wrote:
>>>> Would that not have issues where the owner cpu is kept running but the
>>>> spinner (ie. _this_ vcpu) gets preempted? I would think that in that
>>>> case we too want to stop spinning.
>>>> 
>>> 
>> do  you mean that the spinner detect itself had yield out during the
>> big spin loop?
>> 
>> It is very possible to happen.  BUT if spinner(on this vcpu) yield
>> out, the next spinner would break the spin loop.  AND if spinner
>> detect itself yield out once, it’s very possible to get the osq lock
>> soon as long as the ower vcpu is running.
>> 
>> SO I think we need just check the owner vcpu’s yield_count.
> 
> I had a quick look at KVM and it looks like it only has
> kvm_cpu::preempted, which would suggest the interface boqun proposed.
> 
> We'll have to look at many of the other virt platforms as well to see
> what they can do.
> 
> We could also provide _both_ interfaces and a platform can implement
> whichever variant (or both) it can.
> 
the kvm code on ppc has implemented  yield_count.
It let me feel a little relaxed. :)

looks like we could  introduce the interface like below.

bool vcpu_is_preempted(int cpu)
{
	return arch_vcpu_is_preempted(cpu);
}

#ifdef arch_vcpu_has_yield_count 
bool vcpu_has_preemtped_once(int cpu, unsigned int yield_count)
 {
	return arch_get_vcpu_yield_count() != yield_count;
}

#else
bool vcpu_has_preemtped_once(int cpu, unsigned int yield_count)
{
	/*just let called know it is preepmpted*/
	return vcpu_is_preempted(cpu);
}
#endif

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

#1431345

On Sun, Jun 26, 2016 at 01:21:04PM +0800, panxinhui wrote:
> 
> > 在 2016年6月26日，03:20，Peter Zijlstra <peterz@infradead.org> 写道：
> > 
> > On Sun, Jun 26, 2016 at 01:27:56AM +0800, panxinhui wrote:
> >>>> Would that not have issues where the owner cpu is kept running but the
> >>>> spinner (ie. _this_ vcpu) gets preempted? I would think that in that
> >>>> case we too want to stop spinning.
> >>>> 
> >>> 
> >> do  you mean that the spinner detect itself had yield out during the
> >> big spin loop?
> >> 
> >> It is very possible to happen.  BUT if spinner(on this vcpu) yield
> >> out, the next spinner would break the spin loop.  AND if spinner
> >> detect itself yield out once, it’s very possible to get the osq lock
> >> soon as long as the ower vcpu is running.
> >> 
> >> SO I think we need just check the owner vcpu’s yield_count.
> > 
> > I had a quick look at KVM and it looks like it only has
> > kvm_cpu::preempted, which would suggest the interface boqun proposed.
> > 
> > We'll have to look at many of the other virt platforms as well to see
> > what they can do.
> > 
> > We could also provide _both_ interfaces and a platform can implement
> > whichever variant (or both) it can.
> > 
> the kvm code on ppc has implemented  yield_count.
> It let me feel a little relaxed. :)
> 
> looks like we could  introduce the interface like below.
> 
> bool vcpu_is_preempted(int cpu)
> {
> 	return arch_vcpu_is_preempted(cpu);
> }
> 
> #ifdef arch_vcpu_has_yield_count 
> bool vcpu_has_preemtped_once(int cpu, unsigned int yield_count)
>  {
> 	return arch_get_vcpu_yield_count() != yield_count;
> }
> 
> #else
> bool vcpu_has_preemtped_once(int cpu, unsigned int yield_count)
> {
> 	/*just let called know it is preepmpted*/
> 	return vcpu_is_preempted(cpu);
> }
> #endif
> 

Unfortunately, on PPC, we compile pseries code along with powernv code
in a kernel binary, therefore we need to wire the proper primitives at
runtime.

I've cooked the following patch, please note I haven't test this, this
is just a POC.

Regards,
Boqun

---------------->8
virt: Introduce vcpu preemption detection functions

Lock holder preemption is an serious problem in virtualized environment
for locking. Different archs and hypervisors employ different ways to
try to solve the problem in different locking mechanisms. And recently
Pan Xinhui found a significant performance drop in osq_lock(), which
could be solved by providing a mechanism to detect the preemption of
vcpu.

Therefore this patch introduces several vcpu preemption detection
primitives, which allows locking primtives to save the time of
unnecesarry spinning. These primitives act as an abstract layer between
locking functions and arch or hypervisor related code.

There are two sets of primitives:

1.	vcpu_preempt_count() and vcpu_has_preempted(), they must be used
	pairwisely in a same preempt disable critical section. And they
	could detect whether a vcpu preemption happens between them.

2.	vcpu_is_preempted(), used to check whether other cpu's vcpu is
	preempted.

This patch also implements those primitives on pseries and wire them up.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 arch/powerpc/platforms/pseries/Kconfig |  1 +
 arch/powerpc/platforms/pseries/setup.c | 28 +++++++++++
 include/linux/vcpu_preempt.h           | 90 ++++++++++++++++++++++++++++++++++
 3 files changed, 119 insertions(+)
 create mode 100644 include/linux/vcpu_preempt.h

diff --git a/arch/powerpc/platforms/pseries/Kconfig b/arch/powerpc/platforms/pseries/Kconfig
index bec90fb30425..7d24c3e48878 100644
--- a/arch/powerpc/platforms/pseries/Kconfig
+++ b/arch/powerpc/platforms/pseries/Kconfig
@@ -21,6 +21,7 @@ config PPC_PSERIES
 	select HOTPLUG_CPU if SMP
 	select ARCH_RANDOM
 	select PPC_DOORBELL
+	select HAS_VCPU_PREEMPTION_DETECTION
 	default y
 
 config PPC_SPLPAR
diff --git a/arch/powerpc/platforms/pseries/setup.c b/arch/powerpc/platforms/pseries/setup.c
index 9883bc7ea007..5d4aed54e039 100644
--- a/arch/powerpc/platforms/pseries/setup.c
+++ b/arch/powerpc/platforms/pseries/setup.c
@@ -42,6 +42,7 @@
 #include <linux/of.h>
 #include <linux/of_pci.h>
 #include <linux/kexec.h>
+#include <linux/vcpu_preempt.h>
 
 #include <asm/mmu.h>
 #include <asm/processor.h>
@@ -501,6 +502,31 @@ static void __init find_and_init_phbs(void)
 	of_pci_check_probe_only();
 }
 
+struct vcpu_preempt_ops vcpu_preempt_ops = DEFAULT_VCPU_PREEMPT_OPS;
+EXPORT_SYMBOL(vcpu_preempt_ops);
+
+static long pseries_vcpu_preempt_count(void)
+{
+	return be32_to_cpu(get_lppaca()->yield_count);
+}
+
+static bool pseries_vcpu_is_preempted(int cpu)
+{
+	return !!(be32_to_cpu(lppaca_of(cpu).yield_count) & 1);
+}
+
+static bool pseries_vcpu_has_preempted(long vpc)
+{
+	return pseries_vcpu_preempt_count() != vpc;
+}
+
+static void __init pseries_setup_vcpu_preempt_ops(void)
+{
+	vcpu_preempt_ops.preempt_count = pseries_vcpu_preempt_count;
+	vcpu_preempt_ops.is_preempted = pseries_vcpu_is_preempted;
+	vcpu_preempt_ops.has_preempted = pseries_vcpu_has_preempted;
+}
+
 static void __init pSeries_setup_arch(void)
 {
 	set_arch_panic_timeout(10, ARCH_PANIC_TIMEOUT);
@@ -549,6 +575,8 @@ static void __init pSeries_setup_arch(void)
 				"%ld\n", rc);
 		}
 	}
+
+	pseries_setup_vcpu_preempt_ops();
 }
 
 static int __init pSeries_init_panel(void)
diff --git a/include/linux/vcpu_preempt.h b/include/linux/vcpu_preempt.h
new file mode 100644
index 000000000000..4a88414bb83f
--- /dev/null
+++ b/include/linux/vcpu_preempt.h
@@ -0,0 +1,90 @@
+/*
+ * Primitives for checking the vcpu preemption from the guest.
+ */
+
+static long __vcpu_preempt_count(void)
+{
+	return 0;
+}
+
+static bool __vcpu_has_preempted(long vpc)
+{
+	return false;
+}
+
+static bool __vcpu_is_preempted(int cpu)
+{
+	return false;
+}
+
+struct vcpu_preempt_ops {
+	/*
+	 * Get the current vcpu's "preempt count", which is going to use for
+	 * checking whether the current vcpu has ever been preempted
+	 */
+	long (*preempt_count)(void);
+
+	/*
+	 * Return whether a vcpu is preempted
+	 */
+	bool (*is_preempted)(int cpu);
+
+	/*
+	 * Given a "vcpu preempt count", Return whether a vcpu preemption ever
+	 * happened after the .preempt_count() was called.
+	 */
+	bool (*has_preempted)(long vpc);
+};
+
+struct vcpu_preempt_ops vcpu_preempt_ops;
+
+/* Default boilerplate */
+#define DEFAULT_VCPU_PREEMPT_OPS			\
+	{						\
+		.preempt_count = __vcpu_preempt_count,	\
+		.is_preempted = __vcpu_is_preempted,	\
+		.has_preempted = __vcpu_has_preempted	\
+	}
+
+#ifdef CONFIG_HAS_VCPU_PREEMPTION_DETECTION
+/*
+ * vcpu_preempt_count: Get the current cpu's "vcpu preempt count"(vpc).
+ *
+ * The vpc is used for checking whether the current vcpu has ever been
+ * preempted via vcpu_has_preempted().
+ *
+ * This function and vcpu_has_preepmted() should be called in the same
+ * preemption disabled critical section.
+ */
+static long vcpu_preempt_count(void)
+{
+	return vcpu_preempt_ops.preempt_count();
+}
+
+/*
+ * vcpu_is_preempted: Check whether @cpu's vcpu is preempted.
+ */
+static bool vcpu_is_preempted(int cpu)
+{
+	return vcpu_preempt_ops.is_preempted(cpu);
+}
+
+/*
+ * vcpu_has_preepmted: Check whether the current cpu's vcpu has ever been
+ * preempted.
+ *
+ * The checked duration is between the vcpu_preempt_count() which returns @vpc
+ * is called and this function called.
+ *
+ * This function and corresponding vcpu_preempt_count() should be in the same
+ * preemption disabled cirtial section.
+ */
+static bool vcpu_has_preempted(long vpc)
+{
+	return vcpu_preempt_ops.has_preempt(vpc);
+}
+#else /* CONFIG_HAS_VCPU_PREEMPTION_DETECTION */
+#define vcpu_preempt_count() __vcpu_preempt_count()
+#define vcpu_is_preempted(cpu) __vcpu_is_preempted(cpu)
+#define vcpu_has_preempted(vpc) __vcpu_has_preempted(vpc)
+#endif /* CONFIG_HAS_VCPU_PREEPMTION_DETECTION */
-- 
2.9.0

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

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web