[PATCH v2] xen, credit2: Avoid extra c2t calcuation in csched_runtime

[PATCH v2] xen, credit2: Avoid extra c2t calcuation in csched_runtime

[George Dunlap]

# HG changeset patch
# User George Dunlap <george.dunlap@eu.citrix.com>
# Date 1359046237 0
# Node ID b44d4e03706e032a0454fbef2c59bc37956db499
# Parent  4e8676935f8cd16012b4ba781deaf1baebaa9c4a
xen,credit2: Avoid extra c2t calcuation in csched_runtime

csched_runtime() needs to call the ct2() function to change credits
into time.  The c2t() function, however, is expensive, as it requires
an integer division.

c2t() was being called twice, once for the main vcpu's credit and once
for the difference between its credit and the next in the queue.  But
this is unnecessary; by calculating in "credit" first, we can make it
so that we just do one conversion later in the algorithm.

This also adds more documentation describing the intended algorithm,
along with a relevant assertion..

The effect of the new code should be the same as the old code.

v2:
 - Change rt_credit into an int
 - ASSERT() that rt_credit > 0, with explanation

Spotted-by: Jan Beulich <JBeulich@suse.com>
Signed-off-by: George Dunlap <george.dunlap@eu.citrix.com>

diff --git a/xen/common/sched_credit2.c b/xen/common/sched_credit2.c
--- a/xen/common/sched_credit2.c
+++ b/xen/common/sched_credit2.c
@@ -1505,31 +1505,56 @@ csched_dom_destroy(const struct schedule
 static s_time_t
 csched_runtime(const struct scheduler *ops, int cpu, struct csched_vcpu *snext)
 {
-    s_time_t time = CSCHED_MAX_TIMER;
+    s_time_t time; 
+    int rt_credit; /* Proposed runtime measured in credits */
     struct csched_runqueue_data *rqd = RQD(ops, cpu);
     struct list_head *runq = &rqd->runq;
 
     if ( is_idle_vcpu(snext->vcpu) )
         return CSCHED_MAX_TIMER;
 
-    /* Basic time */
-    time = c2t(rqd, snext->credit, snext);
+    /* General algorithm:
+     * 1) Run until snext's credit will be 0
+     * 2) But if someone is waiting, run until snext's credit is equal
+     * to his
+     * 3) But never run longer than MAX_TIMER or shorter than MIN_TIMER.
+     */
 
-    /* Next guy on runqueue */
+    /* 1) Basic time: Run until credit is 0. */
+    rt_credit = snext->credit;
+
+    /* 2) If there's someone waiting whose credit is positive,
+     * run until your credit ~= his */
     if ( ! list_empty(runq) )
     {
-        struct csched_vcpu *svc = __runq_elem(runq->next);
-        s_time_t ntime;
+        struct csched_vcpu *swait = __runq_elem(runq->next);
 
-        if ( ! is_idle_vcpu(svc->vcpu) )
+        if ( ! is_idle_vcpu(swait->vcpu)
+             && swait->credit > 0 )
         {
-            ntime = c2t(rqd, snext->credit - svc->credit, snext);
-
-            if ( time > ntime )
-                time = ntime;
+            rt_credit = snext->credit - swait->credit;
         }
     }
 
+    /*
+     * snext is about to be scheduled; so:
+     *
+     * 1. if snext->credit were less than 0 when it was taken off the
+     * runqueue, then csched_schedule() should have called
+     * reset_credit().  So at this point snext->credit must be greater
+     * than 0.
+     *
+     * 2. snext must have the highest credit of anyone on the queue;
+     * so snext->credit - swait->credit must be greater than 0.
+     */
+    ASSERT(rt_credit > 0);
+
+    /* FIXME: See if we can eliminate this conversion if we know time
+     * will be outside (MIN,MAX).  Probably requires pre-calculating
+     * credit values of MIN,MAX per vcpu, since each vcpu burns credit
+     * at a different rate. */
+    time = c2t(rqd, rt_credit, snext);
+
     /* Check limits */
     if ( time < CSCHED_MIN_TIMER )
         time = CSCHED_MIN_TIMER;

Re: [PATCH v2] xen, credit2: Avoid extra c2t calcuation in csched_runtime

[Jan Beulich]

>>> On 24.01.13 at 17:51, George Dunlap <george.dunlap@eu.citrix.com> wrote:
> +     * 2. snext must have the highest credit of anyone on the queue;
> +     * so snext->credit - swait->credit must be greater than 0.
> +     */
> +    ASSERT(rt_credit > 0);

And the two can't ever have equal credit?

Jan

Re: [PATCH v2] xen, credit2: Avoid extra c2t calcuation in csched_runtime

[George Dunlap]

[-- Attachment #1.1: Type: text/plain, Size: 492 bytes --]

On Thu, Jan 24, 2013 at 5:03 PM, Jan Beulich <JBeulich@suse.com> wrote:

> >>> On 24.01.13 at 17:51, George Dunlap <george.dunlap@eu.citrix.com>
> wrote:
> > +     * 2. snext must have the highest credit of anyone on the queue;
> > +     * so snext->credit - swait->credit must be greater than 0.
> > +     */
> > +    ASSERT(rt_credit > 0);
>
> And the two can't ever have equal credit?
>

Indeed they can... serves me right for whipping up a patch too quickly.

Standby for v3...

 -George

[-- Attachment #1.2: Type: text/html, Size: 994 bytes --]

[-- Attachment #2: Type: text/plain, Size: 126 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel