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

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

[George Dunlap]

# HG changeset patch
# User George Dunlap <george.dunlap@eu.citrix.com>
# Date 1359040980 0
# Node ID e9222438074a73cb3c93cf21d53a6d9224a48e4c
# Parent  14b0f2e95cb21a94fa154bec56e7925c01e81b56
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.

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

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,42 @@ 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 rt_credit, time; /* 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;
         }
     }
 
+    /* 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] xen, credit2: Avoid extra c2t calcuation in csched_runtime

[Jan Beulich]

>>> On 24.01.13 at 16:24, George Dunlap <george.dunlap@eu.citrix.com> wrote:
> --- a/xen/common/sched_credit2.c
> +++ b/xen/common/sched_credit2.c
> @@ -1505,31 +1505,42 @@ 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 rt_credit, time; /* Proposed runtime measured in credits */

Does rt_credit really need to be s_time_t rather than int?

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

... who's ...?

> +     * 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;
>          }
>      }
>  
> +    /* 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. */

The obvious situation is when rt_credit <= 0, which you could
deal with right away.

Jan

> +    time = c2t(rqd, rt_credit, snext);
> +
>      /* Check limits */
>      if ( time < CSCHED_MIN_TIMER )
>          time = CSCHED_MIN_TIMER;

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

[Tim Deegan]

At 15:45 +0000 on 24 Jan (1359042332), Jan Beulich wrote:
> > +    /* 2) If there's someone waiting whose credit is positive,
> 
> ... who's ...?

No; "whose" is correct. 

Tim.

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

[George Dunlap]

On 24/01/13 15:45, Jan Beulich wrote:
>>>> On 24.01.13 at 16:24, George Dunlap <george.dunlap@eu.citrix.com> wrote:
>> --- a/xen/common/sched_credit2.c
>> +++ b/xen/common/sched_credit2.c
>> @@ -1505,31 +1505,42 @@ 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 rt_credit, time; /* Proposed runtime measured in credits */
> Does rt_credit really need to be s_time_t rather than int?

I suppose not...

>
>>       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,
> ... who's ...?

Nope. :-)  "Who's" is short for "who is".  "Whose" is a pronoun which 
links back to "someone waiting".  (I suppose "whose" is the person 
version of "which", which I used in both the previous sentence and this 
one.)
>> +     * 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;
>>           }
>>       }
>>   
>> +    /* 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. */
> The obvious situation is when rt_credit <= 0, which you could
> deal with right away.

That shouldn't be possible:
1. csched_runtime() should only be called on someone about to be 
scheduled (from csched_schedule()).
2. The credit of such an snext should always be higher than anyone else 
on the queue (or they would be scheduled instead).
3. If someone is about to be scheduled with snext->credit <= 0, it will 
trigger reset_credt(), which will make everyone's credit positive.
4. 3 guarantees that snext->credit will be positive
5. 2 guatantees that (snext->credit - swait->credit) will be positive
6 So rt_credit should never be <= 0.

I can add an assert to this effect if you like.

  -George

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

[Jan Beulich]

>>> On 24.01.13 at 16:55, George Dunlap <george.dunlap@eu.citrix.com> wrote:
> On 24/01/13 15:45, Jan Beulich wrote:
>>>>> On 24.01.13 at 16:24, George Dunlap <george.dunlap@eu.citrix.com> wrote:
>>> +    /* 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. */
>> The obvious situation is when rt_credit <= 0, which you could
>> deal with right away.
> 
> That shouldn't be possible:
> 1. csched_runtime() should only be called on someone about to be 
> scheduled (from csched_schedule()).
> 2. The credit of such an snext should always be higher than anyone else 
> on the queue (or they would be scheduled instead).
> 3. If someone is about to be scheduled with snext->credit <= 0, it will 
> trigger reset_credt(), which will make everyone's credit positive.
> 4. 3 guarantees that snext->credit will be positive
> 5. 2 guatantees that (snext->credit - swait->credit) will be positive
> 6 So rt_credit should never be <= 0.
> 
> I can add an assert to this effect if you like.

That would be nice, because I came up with the whole thing just
because I was trying to understand whether the 2nd argument
to c2t() in the invocation this change removes could go negative.

Jan

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

[George Dunlap]

On 24/01/13 15:55, George Dunlap wrote:
>>
>>>       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,
>> ... who's ...?
>
> Nope. :-)  "Who's" is short for "who is".  "Whose" is a pronoun which 
> links back to "someone waiting".  (I suppose "whose" is the person 
> version of "which", which I used in both the previous sentence and 
> this one.)

OK, for the really serious grammar students:

"Whose" isn't a pronoun, it's an adjective indicating "owned by who" or 
"of who"; in this case, "whose" is modifying "credit".  It's a similar 
construction to the following:

"If there's someone waiting who has positive credit, ..."

  -George