[Xen-changelog] [xen master] credit2: Avoid extra c2t calcuation in csched_runtime

[patchbot@xxxxxxx]

commit 8b3072a050a67405022f9e7911c37ccff9c0cdb5
Author:     George Dunlap <george.dunlap@xxxxxxxxxxxxx>
AuthorDate: Mon Mar 4 13:38:45 2013 +0100
Commit:     Jan Beulich <jbeulich@xxxxxxxx>
CommitDate: Mon Mar 4 13:38:45 2013 +0100

    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.
    
    Spotted-by: Jan Beulich <JBeulich@xxxxxxxx>
    Signed-off-by: George Dunlap <george.dunlap@xxxxxxxxxxxxx>
---
 xen/common/sched_credit2.c |   48 +++++++++++++++++++++++++++++++++----------
 1 files changed, 37 insertions(+), 11 deletions(-)

diff --git a/xen/common/sched_credit2.c b/xen/common/sched_credit2.c
index b0af010..804049e 100644
--- a/xen/common/sched_credit2.c
+++ b/xen/common/sched_credit2.c
@@ -1505,31 +1505,57 @@ csched_dom_destroy(const struct scheduler *ops, struct 
domain *dom)
 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.
+     */
+
+    /* 1) Basic time: Run until credit is 0. */
+    rt_credit = snext->credit;
 
-    /* Next guy on runqueue */
+    /* 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's credit must be greater than or equal to anyone else
+     * in the queue, so snext->credit - swait->credit must be greater
+     * than or equal to 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;
--
generated by git-patchbot for /home/xen/git/xen.git#master

_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxx
http://lists.xensource.com/xen-changelog