Re: [Xen-devel] [PATCH v7]xen: sched: convert RTDS from time to event driven model

[Dario Faggioli <dario.faggioli@xxxxxxxxxx>]

On Tue, 2016-03-08 at 23:33 -0500, Meng Xu wrote:
> I didn't mark out all repeated style issues. I think you can correct
> all of the style issues, such as the spaces in the code, in the next
> version.
> 
Yes, please. At v7, style issues shouldn't definitely be there any
longer.

Have another look at CODING_STYLE, perhaps, especially focusing on
spaces in conditional expressions and line length.

> Hi Dario,
> Could you help check if my two concerns in the comments below make
> sense?
> One is small, about if we should use () to make the code clearer.
> The other is about the logic in the replenishment handler.
> 
I think tickling during replenishment does have issues, yes. See below.

Anyway, Meng, can you trim your quotes when replying? By this, I mean
cut the part of conversation/patches that are not relevant for what you
are saying in this very email (but leave enough context in place for
making what you want to point out understandable).

That avoids having to scroll pages and pages of quoted text in order to
find the actual content.

> On Fri, Mar 4, 2016 at 8:39 PM, Tianyang Chen <tiche@xxxxxxxxxxxxxx>
> wrote:
> > 
> > @@ -1033,32 +1159,40 @@ rt_vcpu_wake(const struct scheduler *ops,
> > struct vcpu *vc)
> >      else
> >          SCHED_STAT_CRANK(vcpu_wake_not_runnable);
> > 
> > -    /* If context hasn't been saved for this vcpu yet, we can't
> > put it on
> > -     * the Runqueue/DepletedQ. Instead, we set a flag so that it
> > will be
> > -     * put on the Runqueue/DepletedQ after the context has been
> > saved.
> > +    /*
> > +     * If a deadline passed while svc was asleep/blocked, we need
> > new
> > +     * scheduling parameters (a new deadline and full budget).
> > +     */
> > +    if ( (missed = now >= svc->cur_deadline) )
> Dario,
> Is it better to have a () outside of   now >= svc->cur_deadline to
> make the logic clearer, instead of relying on the operator's
> priority?
> 
Yes, go ahead.

You may even compute the value of missed outside of the if, and just
use it (both here and below). As you wish.

> > @@ -1150,6 +1276,71 @@ rt_dom_cntl(
> >      return rc;
> >  }
> > 
> > +/*
> > + * The replenishment timer handler picks vcpus
> > + * from the replq and does the actual replenishment.
> > + */
> > +static void repl_handler(void *data){
> > +    unsigned long flags;
> > +    s_time_t now = NOW();
> > +    struct scheduler *ops = data;
> > +    struct rt_private *prv = rt_priv(ops);
> > +    struct list_head *replq = rt_replq(ops);
> > +    struct timer *repl_timer = prv->repl_timer;
> > +    struct list_head *iter, *tmp;
> > +    struct rt_vcpu *svc = NULL;
> > +
> > +    spin_lock_irqsave(&prv->lock, flags);
> > +
> > +    stop_timer(repl_timer);
> > +
> > +    list_for_each_safe(iter, tmp, replq)
> > +    {
> > +        svc = replq_elem(iter);
> > +
> > +        if ( now < svc->cur_deadline )
> > +            break;
> > +
> > +        rt_update_deadline(now, svc);
> > +
> > +        /*
> > +         * when the replenishment happens
> > +         * svc is either on a pcpu or on
> > +         * runq/depletedq
> > +         */
> > +        if( __vcpu_on_q(svc) )
> > +        {
> > +            /* put back to runq */
> > +            __q_remove(svc);
> > +            __runq_insert(ops, svc);
> > +        }
> > +
> > +        /*
> > +         * tickle regardless where it's at
> > +         * because a running vcpu could have
> > +         * a later deadline than others after
> > +         * replenishment
> > +         */
> > +        runq_tickle(ops, svc);
> Well, I'm thinking about the correctness of tickle here.
> The svc is running on a core, say P_i, right now. After replenishing
> the budget for svc, svc's deadline also changes. So svc  should
> probably be preempted by the head vcpu in the runq. If that's the
> case, we should use the head of runq to tickle, instead of using svc.
> Right?
> 
I agree that, in case of replenishment of a running vcpu, calling
runq_tickle() like this is not correct. In fact, the whole idea of
tickling in Credit1 and 2, from which it has been borrowed to here, was
meant at (potentially) putting a vcpu in execution, not vice versa. :-/

I therefore agree that, if svc ends up with a later deadline than the
first vcpu in the runque, we should actually call run_tickle() on the
latter!

> Actually, is the runq_tickle necessary here? Can we just check if the
> updated svc has higher priority (smaller deadline) than the head vcpu
> in the runq? If so, we just tickle the cpu P_i, where svc is
> currently
> running on. 
>
Well, if we are replenishing a vcpu that is depleted, whose new
deadline can be earlier than any of the ones of the vcpus that are
running (can't it?) and/or there can be idle vcpus on which you can run
it, now that it has budget. So, in this case, I think we need what's
done in runq_tickle()...

The third case is that we replenish a vcpu that is in the runqueue, so
it had budget, but was not running. In that case, there should be no
chance that it should preempt a running vcpu, as it was waiting in the
runqueue, which means --if we have M pcpus-- it was not among the M
earliest deadline vcpus, and we just pushed its deadline away!
It should also not be necessary to do any deadline comparison with
other vcpus in the runqueue. In fact, still considering that we are
moving the deadline ahead, it's going to either be in the same or
"worst" position in the runqueue.

> But either way, I'm thinking the logic here is incorrect. If the
> updated svc has a lower priority, you will end up tickle no core
> although the svc should be preempted.
> 
It seems to me that the logic here could be (sort-of):

  for_each_to_be_replenished_vcpu(v)
  {
    deadline_queue_remove(replq, v);
    rt_update_deadline(v);

    if ( curr_on_cpu(v->processor) == v)) //running
    {
        if ( v->cur_deadline >= runq[0]->cur_deadline )
          tickle(runq[0]); /* runq[0] => first vcpu in the runq */
    }
    else if ( __vcpu_on_q(v) )
    {
        if ( v->cur_budget == 0 )         //depleted
          tickle(v);
        else                              //runnable
          /* do nothing */
    }
    deadline_queue_insert(v, replq);
  }

Thoughts?

I actually think there may be room for a nasty race, in case we do more
than one replenishments.

In fact, assume that, at time t:
 - we do the replenishment of v1, which is running and v2, which is
   runnable,
 - we have 1 cpu,
 - v1 and v2 have, currently, the same deadline == t,
 - v1's new deadline is going to be t+100, and v2's new deadline is
   going to be t+150,
 - v2 is the only (i.e., also the first) runnable vcpu,
 - v1's replenishment event comes first in the replenishment queue.

With the code above, we update v1's deadline (to t+100), go check it
against v2's _not_updated_ deadline (t) and (since t+100 > t) find that
a preemption is necessary, so we call tickle(v2). That will raise
SCHEDULE_SOFTIRQ for the cpu, because v2 should --as far as situation
is right now-- preempt v1.

However, right after that, we update v2's deadline to t+150, and we do
nothing. So, even if the vcpu with the earliest deadline (v1) is
running, we reschedule.

This should be harmless, as we do figure out during rt_schedule() that
no real context switch is necessary, but I think it would better be
avoided, if possible.

It looks to me that we can re-arrange the code above as follows:

  for_each_to_be_replenished_vcpu(v)
  {
    rt_update_deadline(v);
  }

  for_each_to_be_replenished_vcpu(v)
  {
    deadline_queue_remove(replq, v);

    if ( curr_on_cpu(v->processor) == v)) //running
    {
        if ( v->cur_deadline >= runq[0]->cur_deadline )
          tickle(runq[0]); /* runq[0] => first vcpu in the runq */
    }
    else if ( __vcpu_on_q(v) )
    {
        if ( v->cur_budget == 0 )         //depleted
          tickle(v);
        else                              //runnable
          /* do nothing */
    }
    deadline_queue_insert(v, replq);
  }

Basically, by doing all the replenishments (which includes updating all
the deadlines) upfront, we should be able to prevent the above
situation.

So, again, thoughts?

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

Attachment: signature.asc
Description: This is a digitally signed message part

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