Re: [RFC][PATCH] Improving directed yield scalability for PLE handler

* Andrew Theurer [off-list ref] [2012-09-11 13:27:41]:

On Tue, 2012-09-11 at 11:38 +0530, Raghavendra K T wrote:

quoted

On 09/11/2012 01:42 AM, Andrew Theurer wrote:

quoted

On Mon, 2012-09-10 at 19:12 +0200, Peter Zijlstra wrote:

quoted

On Mon, 2012-09-10 at 22:26 +0530, Srikar Dronamraju wrote:

quoted

quoted

+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p)
+{
+     if (!curr->sched_class->yield_to_task)
+             return false;
+
+     if (curr->sched_class != p->sched_class)
+             return false;

Peter,

Should we also add a check if the runq has a skip buddy (as pointed out
by Raghu) and return if the skip buddy is already set.

Oh right, I missed that suggestion.. the performance improvement went
from 81% to 139% using this, right?

It might make more sense to keep that separate, outside of this
function, since its not a strict prerequisite.

quoted

quoted

+     if (task_running(p_rq, p) || p->state)
+             return false;
+
+     return true;
+}

quoted

quoted

@@ -4323,6 +4340,10 @@ bool __sched yield_to(struct task_struct *p,

bool preempt)

quoted

       rq = this_rq();

  again:
+     /* optimistic test to avoid taking locks */
+     if (!__yield_to_candidate(curr, p))
+             goto out_irq;
+

So add something like:

	/* Optimistic, if we 'raced' with another yield_to(), don't bother */
	if (p_rq->cfs_rq->skip)
		goto out_irq;

quoted

quoted

       p_rq = task_rq(p);
       double_rq_lock(rq, p_rq);

But I do have a question on this optimization though,.. Why do we check
p_rq->cfs_rq->skip and not rq->cfs_rq->skip ?

That is, I'd like to see this thing explained a little better.

Does it go something like: p_rq is the runqueue of the task we'd like to
yield to, rq is our own, they might be the same. If we have a ->skip,
there's nothing we can do about it, OTOH p_rq having a ->skip and
failing the yield_to() simply means us picking the next VCPU thread,
which might be running on an entirely different cpu (rq) and could
succeed?

Here's two new versions, both include a __yield_to_candidate(): "v3"
uses the check for p_rq->curr in guest mode, and "v4" uses the cfs_rq
skip check.  Raghu, I am not sure if this is exactly what you want
implemented in v4.

Andrew, Yes that is what I had. I think there was a mis-understanding. 
My intention was to if there is a directed_yield happened in runqueue 
(say rqA), do not bother to directed yield to that. But unfortunately as 
PeterZ pointed that would have resulted in setting next buddy of a 
different run queue than rqA.
So we can drop this "skip" idea. Pondering more over what to do? can we 
use next buddy itself ... thinking..

As I mentioned earlier today, I did not have your changes from kvm.git
tree when I tested my changes.  Here are your changes and my changes
compared:

			  throughput in MB/sec

kvm_vcpu_on_spin changes:  4636 +/- 15.74%
yield_to changes:	   4515 +/- 12.73%

I would be inclined to stick with your changes which are kept in kvm
code.  I did try both combined, and did not get good results:

both changes:		   4074 +/- 19.12%

So, having both is probably not a good idea.  However, I feel like
there's more work to be done.  With no over-commit (10 VMs), total
throughput is 23427 +/- 2.76%.  A 2x over-commit will no doubt have some
overhead, but a reduction to ~4500 is still terrible.  By contrast,
8-way VMs with 2x over-commit have a total throughput roughly 10% less
than 8-way VMs with no overcommit (20 vs 10 8-way VMs on 80 cpu-thread
host).  We still have what appears to be scalability problems, but now
it's not so much in runqueue locks for yield_to(), but now
get_pid_task():

Hi Andrew,
IMHO, reducing the double runqueue lock overhead is a good idea,
and may be  we see the benefits when we increase the overcommit further.

The explaination for not seeing good benefit on top of PLE handler
optimization patch is because we filter the yield_to candidates,
and hence resulting in less contention for double runqueue lock.
and extra code overhead during genuine yield_to might have resulted in
some degradation in the case you tested.

However, did you use cfs.next also?. I hope it helps, when we combine.

Here is the result that is showing positive benefit.
I experimented on a 32 core (no HT) PLE machine with 32 vcpu guest(s).
  
+-----------+-----------+-----------+------------+-----------+
        kernbench time in sec, lower is better 
+-----------+-----------+-----------+------------+-----------+
       base      stddev     patched     stddev      %improve
+-----------+-----------+-----------+------------+-----------+
1x    44.3880     1.8699    40.8180     1.9173	   8.04271
2x    96.7580     4.2787    93.4188     3.5150	   3.45108
+-----------+-----------+-----------+------------+-----------+


+-----------+-----------+-----------+------------+-----------+
        ebizzy record/sec higher is better
+-----------+-----------+-----------+------------+-----------+
       base      stddev     patched     stddev      %improve
+-----------+-----------+-----------+------------+-----------+
1x  2374.1250    50.9718   3816.2500    54.0681	  60.74343
2x  2536.2500    93.0403   2789.3750   204.7897	   9.98029
+-----------+-----------+-----------+------------+-----------+


Below is the patch which combine suggestions of peterZ on your
original approach with cfs.next (already posted by Srikar in the other
thread)

----8<----

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index fbf1fd0..8551f57 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c

@@ -4820,6 +4820,24 @@ void __sched yield(void)
 }
 EXPORT_SYMBOL(yield);
 
+/*
+ * Tests preconditions required for sched_class::yield_to().
+ */
+static bool __yield_to_candidate(struct task_struct *curr, struct task_struct *p,
+					 struct rq *p_rq)
+{
+	if (!curr->sched_class->yield_to_task)
+		return false;
+
+	if (curr->sched_class != p->sched_class)
+		return false;
+
+	if (task_running(p_rq, p) || p->state)
+		return false;
+
+	return true;
+}
+
 /**
  * yield_to - yield the current processor to another thread in
  * your thread group, or accelerate that thread toward the

@@ -4844,20 +4862,24 @@ bool __sched yield_to(struct task_struct *p, bool preempt)
 
 again:
 	p_rq = task_rq(p);
+
+	/* optimistic test to avoid taking locks */
+	if (!__yield_to_candidate(curr, p, p_rq))
+		goto out_irq;
+
+	/* if next buddy is set, assume yield is in progress */
+	if (p_rq->cfs.next)
+		goto out_irq;
+
 	double_rq_lock(rq, p_rq);
 	while (task_rq(p) != p_rq) {
 		double_rq_unlock(rq, p_rq);
 		goto again;
 	}
 
-	if (!curr->sched_class->yield_to_task)
-		goto out;
-
-	if (curr->sched_class != p->sched_class)
-		goto out;
-
-	if (task_running(p_rq, p) || p->state)
-		goto out;
+	/* validate state, holding p_rq ensures p's state cannot change */
+	if (!__yield_to_candidate(curr, p, p_rq))
+		goto out_unlock;
 
 	yielded = curr->sched_class->yield_to_task(rq, p, preempt);
 	if (yielded) {

@@ -4877,8 +4899,9 @@ again:
 		rq->skip_clock_update = 0;
 	}
 
-out:
+out_unlock:
 	double_rq_unlock(rq, p_rq);
+out_irq:
 	local_irq_restore(flags);
 
 	if (yielded)