Xen devel - Mar 2013 - [PATCH v2 1/2] credit2: Fix erronous ASSERT

In order to avoid high-frequency cpu migration, vcpus may in fact be
scheduled slightly out-of-order.  Account for this situation properly.

Signed-off-by: George Dunlap <george.dunlap@eu.citrix.com>
credit2: Fix erronous ASSERT

In order to avoid high-frequency cpu migration, vcpus may in fact be
scheduled slightly out-of-order.  Account for this situation properly.

v2:
 - Update comment
 - <= 0

Signed-off-by: George Dunlap <george.dunlap@eu.citrix.com>
---
 xen/common/sched_credit2.c |   41 +++++++++++++++++------------------------
 1 file changed, 17 insertions(+), 24 deletions(-)

diff --git a/xen/common/sched_credit2.c b/xen/common/sched_credit2.c
index a7bd2ee..03814b7 100644
--- a/xen/common/sched_credit2.c
+++ b/xen/common/sched_credit2.c
@@ -1544,31 +1544,24 @@ csched_runtime(const struct scheduler *ops, int cpu,
struct csched_vcpu *snext)
         }
     }
 
-    /*
-     * 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 )
+    /* The next guy may actually have a higher credit, if we''ve tried
to
+     * avoid migrating him from a different cpu.  DTRT.  */
+    if ( rt_credit <= 0 )
         time = CSCHED_MIN_TIMER;
-    else if ( time > CSCHED_MAX_TIMER )
-        time = CSCHED_MAX_TIMER;
+    else
+    {
+        /* 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;
+        else if ( time > CSCHED_MAX_TIMER )
+            time = CSCHED_MAX_TIMER;
+    }
 
     return time;
 }
-- 
1.7.9.5

Under normal circumstances, snext->credit should never be less than
-CSCHED_MIN_TIMER.  However, under some circumstances, a vcpu with low
credits may be allowed to run long enough that its credits are
actually less than -CSCHED_CREDIT_INIT.

(Instances have been observed, for example, where a vcpu with 200us of
credit was allowed to run for 11ms, giving it -10.8ms of credit.  Thus
it was still negative even after the reset.)

If this is the case for snext, we simply want to keep moving everyone
up until it is in the black again.  This fair because none of the
other vcpus want to run at the moment.

Rather than loop, just detect how many times we want to add
CSCHED_CREDIT_INIT.  Try to avoid integer divides and multiplies in
the common case.

v2:
 - Take out loop and do division instead.
 - Clip after the addition rather than before.

Signed-off-by: George Dunlap <george.dunlap@eu.citrix.com>
credit2: Reset until the front of the runqueue is positive
---
 xen/common/sched_credit2.c |   48 ++++++++++++++++++++++++++++++++++++--------
 1 file changed, 40 insertions(+), 8 deletions(-)

diff --git a/xen/common/sched_credit2.c b/xen/common/sched_credit2.c
index 03814b7..825ec98 100644
--- a/xen/common/sched_credit2.c
+++ b/xen/common/sched_credit2.c
@@ -588,38 +588,70 @@ no_tickle:
 /*
  * Credit-related code
  */
-static void reset_credit(const struct scheduler *ops, int cpu, s_time_t now)
+static void reset_credit(const struct scheduler *ops, int cpu, s_time_t now,
+                         struct csched_vcpu *snext)
 {
     struct csched_runqueue_data *rqd = RQD(ops, cpu);
     struct list_head *iter;
+    int m;
+
+    /*
+     * Under normal circumstances, snext->credit should never be less
+     * than -CSCHED_MIN_TIMER.  However, under some circumstances, a
+     * vcpu with low credits may be allowed to run long enough that
+     * its credits are actually less than -CSCHED_CREDIT_INIT.
+     * (Instances have been observed, for example, where a vcpu with
+     * 200us of credit was allowed to run for 11ms, giving it -10.8ms
+     * of credit.  Thus it was still negative even after the reset.)
+     *
+     * If this is the case for snext, we simply want to keep moving
+     * everyone up until it is in the black again.  This fair because
+     * none of the other vcpus want to run at the moment.
+     *
+     * Rather than looping, however, we just calculate a multiplier,
+     * avoiding an integer division and multiplication in the common
+     * case.
+     */
+    m = 1;
+    if ( snext->credit < -CSCHED_CREDIT_INIT )
+        m += (-snext->credit) / CSCHED_CREDIT_INIT;
 
     list_for_each( iter, &rqd->svc )
     {
-        struct csched_vcpu * svc = list_entry(iter, struct csched_vcpu,
rqd_elem);
-
+        struct csched_vcpu * svc;
         int start_credit;
 
+        svc = list_entry(iter, struct csched_vcpu, rqd_elem);
+
         BUG_ON( is_idle_vcpu(svc->vcpu) );
         BUG_ON( svc->rqd != rqd );
 
         start_credit = svc->credit;
 
+        /* And add INIT * m, avoiding integer multiplication in the
+         * common case. */
+        if ( likely(m==1) )
+            svc->credit += CSCHED_CREDIT_INIT;
+        else
+            svc->credit += m * CSCHED_CREDIT_INIT;
+
         /* "Clip" credits to max carryover */
-        if ( svc->credit > CSCHED_CARRYOVER_MAX )
-            svc->credit = CSCHED_CARRYOVER_MAX;
-        /* And add INIT */
-        svc->credit += CSCHED_CREDIT_INIT;
+        if ( svc->credit > CSCHED_CREDIT_INIT + CSCHED_CARRYOVER_MAX )
+            svc->credit = CSCHED_CREDIT_INIT + CSCHED_CARRYOVER_MAX;
+
         svc->start_time = now;
 
         /* TRACE */ {
             struct {
                 unsigned dom:16,vcpu:16;
                 unsigned credit_start, credit_end;
+                unsigned multiplier;
             } d;
             d.dom = svc->vcpu->domain->domain_id;
             d.vcpu = svc->vcpu->vcpu_id;
             d.credit_start = start_credit;
             d.credit_end = svc->credit;
+            d.multiplier = m;
             trace_var(TRC_CSCHED2_CREDIT_RESET, 1,
                       sizeof(d),
                       (unsigned char *)&d);
@@ -1732,7 +1764,7 @@ csched_schedule(
         /* Check for the reset condition */
         if ( snext->credit <= CSCHED_CREDIT_RESET )
         {
-            reset_credit(ops, cpu, now);
+            reset_credit(ops, cpu, now, snext);
             balance_load(ops, cpu, now);
         }
 
-- 
1.7.9.5

On 08/03/13 18:08, George Dunlap wrote:
> In order to avoid high-frequency cpu migration, vcpus may in fact be
> scheduled slightly out-of-order.  Account for this situation properly.
>
> Signed-off-by: George Dunlap <george.dunlap@eu.citrix.com>
> credit2: Fix erronous ASSERT
>
> In order to avoid high-frequency cpu migration, vcpus may in fact be
> scheduled slightly out-of-order.  Account for this situation properly.
>
> v2:
>   - Update comment
>   - <= 0
>
> Signed-off-by: George Dunlap <george.dunlap@eu.citrix.com>
Hmm -- sorry for the duplicate messages; I''m still sorting out my git 
workflow...

  -George