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

[Dario Faggioli <dario.faggioli@xxxxxxxxxx>]

Hey,

Here I am, sorry for the delay. :-(

On Mon, 2016-02-08 at 23:33 -0500, Tianyang Chen wrote:
> Changes since v4:
> ÂÂÂÂremoved unnecessary replenishment queue checks in vcpu_wake()
> ÂÂÂÂextended replq_remove() to all cases in vcpu_sleep()
> ÂÂÂÂused _deadline_queue_insert() helper function for both queues
> ÂÂÂÂ_replq_insert() and _replq_remove() program timer internally
> 
> Changes since v3:
> ÂÂÂÂremoved running queue.
> ÂÂÂÂadded repl queue to keep track of repl events.
> ÂÂÂÂtimer is now per scheduler.
> ÂÂÂÂtimer is init on a valid cpu in a cpupool.
> 
> Signed-off-by: Tianyang Chen <tiche@xxxxxxxxxxxxxx>
> Signed-off-by: Meng Xu <mengxu@xxxxxxxxxxxxx>
> Signed-off-by: Dagaen Golomb <dgolomb@xxxxxxxxxxxxxx>
>
So, the actual changelog... why did it disappear? :-)

> diff --git a/xen/common/sched_rt.c b/xen/common/sched_rt.c
> index 2e5430f..1f0bb7b 100644
> --- a/xen/common/sched_rt.c
> +++ b/xen/common/sched_rt.c

> @@ -388,6 +424,66 @@ __q_remove(struct rt_vcpu *svc)
> Â}
> Â
> Â/*
> + * Removing a vcpu from the replenishment queue could
> + * re-program the timer for the next replenishment event
> + * if the timer is currently active
> + */
> +static inline void
> +__replq_remove(const struct scheduler *ops, struct rt_vcpu *svc)
> +{
> +ÂÂÂÂstruct rt_private *prv = rt_priv(ops);
> +ÂÂÂÂstruct list_head *replq = rt_replq(ops);
> +ÂÂÂÂstruct timer* repl_timer = prv->repl_timer;
> +
> +ÂÂÂÂif ( __vcpu_on_replq(svc) )
> +ÂÂÂÂ{
So, can this be false? If yes, when and why?

> +ÂÂÂÂÂÂÂÂ/*
> +ÂÂÂÂÂÂÂÂÂ* disarm the timer if removing the first replenishment
> event
> +ÂÂÂÂÂÂÂÂÂ* which is going to happen next
> +ÂÂÂÂÂÂÂÂÂ*/
> +ÂÂÂÂÂÂÂÂif( active_timer(repl_timer) )
> +ÂÂÂÂÂÂÂÂ{
>
And here again, isn't it the case that, if there is a vcpu in the
replenishment queue, then the timer _must_ be active? (I.e., if the
above is true, isn't this also always true?)

> +ÂÂÂÂÂÂÂÂÂÂÂÂstruct rt_vcpu *next_repl = __replq_elem(replq->next);
> +
> +ÂÂÂÂÂÂÂÂÂÂÂÂif( next_repl->cur_deadline == svc->cur_deadline )
> +ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂrepl_timer->expires = 0;
> +
I think we need to call stop_timer() here, don't we? I know that
set_timer() does that itself, but I think it is indeed necessary. E.g.,
right now, you're manipulating the timer without the timer lock.

> +ÂÂÂÂÂÂÂÂÂÂÂÂlist_del_init(&svc->replq_elem);
> +
> +ÂÂÂÂÂÂÂÂÂÂÂÂ/* re-arm the timer for the next replenishment event */
> +ÂÂÂÂÂÂÂÂÂÂÂÂif( !list_empty(replq) )
> +ÂÂÂÂÂÂÂÂÂÂÂÂ{
> +ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂstruct rt_vcpu *svc_next = __replq_elem(replq-
> >next);
> +ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂset_timer(repl_timer, svc_next->cur_deadline);
> +ÂÂÂÂÂÂÂÂÂÂÂÂ}
> +ÂÂÂÂÂÂÂÂ}
> +
> +ÂÂÂÂÂÂÂÂelse
> +ÂÂÂÂÂÂÂÂÂÂÂÂlist_del_init(&svc->replq_elem);
>
I don't like the structure of this function, and I'd ask for a
different if/then/else logic to be used, but let's first see --by
answering the questions above-- if some of these if-s can actually go
away. :-)

> +ÂÂÂÂ}
> +}
> +
> +/*
> + * An utility function that inserts a vcpu to a
> + * queue based on certain order (EDF)
>
End long comments with a full stop.

> + */
> +static void
> +_deadline_queue_insert(struct rt_vcpu * (*_get_q_elem)(struct
> list_head *elem),
>
There's really a lot of "underscore-prefixing" in this file.

This is, of course, not your fault, and should not be addressed in this
patch. But, at least when it comes to new code, let's avoid making
things worse.

So, "deadline_queue_insert()" is just ok, I think. Yes, I know I did
suggest to call it how it's called in this patch, underscore included,
but I now think it would be better to get rid of that.

> +ÂÂÂÂstruct rt_vcpu *svc, struct list_head *elem, struct list_head
> *queue)
> +{
> +ÂÂÂÂstruct list_head *iter;
> +
> +ÂÂÂÂlist_for_each(iter, queue)
> +ÂÂÂÂ{
> +ÂÂÂÂÂÂÂÂstruct rt_vcpu * iter_svc = (*_get_q_elem)(iter);
> +ÂÂÂÂÂÂÂÂif ( svc->cur_deadline <= iter_svc->cur_deadline )
> +ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂbreak;
>
This looks too much indented.

> @@ -405,22 +500,37 @@ __runq_insert(const struct scheduler *ops,
> struct rt_vcpu *svc)
> Â
> ÂÂÂÂÂ/* add svc to runq if svc still has budget */
> ÂÂÂÂÂif ( svc->cur_budget > 0 )
> -ÂÂÂÂ{
> -ÂÂÂÂÂÂÂÂlist_for_each(iter, runq)
> -ÂÂÂÂÂÂÂÂ{
> -ÂÂÂÂÂÂÂÂÂÂÂÂstruct rt_vcpu * iter_svc = __q_elem(iter);
> -ÂÂÂÂÂÂÂÂÂÂÂÂif ( svc->cur_deadline <= iter_svc->cur_deadline )
> -ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂbreak;
> -ÂÂÂÂÂÂÂÂÂ}
> -ÂÂÂÂÂÂÂÂlist_add_tail(&svc->q_elem, iter);
> -ÂÂÂÂ}
> +ÂÂÂÂÂÂÂÂ_deadline_queue_insert(&__q_elem, svc, &svc->q_elem, runq);
> ÂÂÂÂÂelse
> -ÂÂÂÂ{
> ÂÂÂÂÂÂÂÂÂlist_add(&svc->q_elem, &prv->depletedq);
> -ÂÂÂÂ}
Can we ASSERT() something about a replenishment event being queued, in
either case?

As I said already, use full words in comments ("Insert svc in the
replenishment timer queue" or "Insert svc in the replenishment events
list").

> + * vcpus that needs to be repl earlier go first.
>
Ditto. And this can just be something like "in replenishment time
order", added to the sentence above.

> + * scheduler private lock serializes this operation
>
This is true for _everything_ in this scheduler right now, so there's
no real need to say it.

> + * it could re-program the timer if it fires later than
> + * this vcpu's cur_deadline. 
>
Do you mean "The timer may be re-programmed if svc is inserted at the
front of the events list" ?

> Also, this is used to program
> + * the timer for the first time.
>
"Also, this is what programs the timer the first time, when called from
xxx"

> + */
> +static void
> +__replq_insert(const struct scheduler *ops, struct rt_vcpu *svc)
> +{
> +ÂÂÂÂstruct list_head *replq = rt_replq(ops);
> +ÂÂÂÂstruct rt_private *prv = rt_priv(ops);
> +ÂÂÂÂstruct timer *repl_timer = prv->repl_timer;
> +
> +ÂÂÂÂASSERT( !__vcpu_on_replq(svc) );
> +
> +ÂÂÂÂ_deadline_queue_insert(&__replq_elem, svc, &svc->replq_elem,
> replq);
> +
> +ÂÂÂÂif( repl_timer->expires == 0 ||
> +ÂÂÂÂÂÂÂÂ( active_timer(repl_timer) && repl_timer->expires > svc-
> >cur_deadline ) )
> +ÂÂÂÂÂÂÂÂset_timer(repl_timer,svc->cur_deadline);
>
Is it the case that you need to call set_timer() if (and only if) svc
has been inserted at the *front* of the replenishment queue? (If list
was empty, as in the case of first timer activation, it would be the
first and only.)

If that is the case, I'd just make deadline_queue_insert() return a
flag to that effect (e.g., it can return 1 if svc is the new first
element, 0 if it is not), and use the flag itself to guard the (re-)arm 
of the timer... What do you think?

> @@ -651,6 +785,10 @@ rt_vcpu_remove(const struct scheduler *ops,
> struct vcpu *vc)
> ÂÂÂÂÂlock = vcpu_schedule_lock_irq(vc);
> ÂÂÂÂÂif ( __vcpu_on_q(svc) )
> ÂÂÂÂÂÂÂÂÂ__q_remove(svc);
> +
> +ÂÂÂÂif( __vcpu_on_replq(svc) )
> +ÂÂÂÂÂÂÂÂ__replq_remove(ops,svc);
> +
As per the code in this patch looks like, you're
checkingÂ__vcpu_on_replq(svc) twice. In fact, you do it here and inside
__replq_remove(). I've already said that I'd like for the check inside
__rqplq_remove() to go away so, keep this one here (if it's really
necessary) and kill the other one inside the function.

> @@ -924,6 +1027,9 @@ rt_vcpu_sleep(const struct scheduler *ops,
> struct vcpu *vc)
> ÂÂÂÂÂÂÂÂÂ__q_remove(svc);
> ÂÂÂÂÂelse if ( svc->flags & RTDS_delayed_runq_add )
> ÂÂÂÂÂÂÂÂÂclear_bit(__RTDS_delayed_runq_add, &svc->flags);
> +
> +ÂÂÂÂif( __vcpu_on_replq(svc) )
> +ÂÂÂÂÂÂÂÂ__replq_remove(ops, svc);
>
Same here.

> @@ -1051,6 +1153,18 @@ rt_vcpu_wake(const struct scheduler *ops,
> struct vcpu *vc)
> ÂÂÂÂÂelse
> ÂÂÂÂÂÂÂÂÂSCHED_STAT_CRANK(vcpu_wake_not_runnable);
> Â
> +ÂÂÂÂ/* budget repl here is needed before inserting back to runq. If
> so,
>
Comment style.

Also, what do you mean with that "If so"... "If so" what?
> +ÂÂÂÂÂ* it should be re-inserted back to the replenishment queue.
> +ÂÂÂÂÂ*/
> +ÂÂÂÂif ( now >= svc->cur_deadline)
> +ÂÂÂÂ{ÂÂÂ
> +ÂÂÂÂÂÂÂÂrt_update_deadline(now, svc);
> +ÂÂÂÂÂÂÂÂ__replq_remove(ops, svc);
> +ÂÂÂÂ}
> +
> +ÂÂÂÂif( !__vcpu_on_replq(svc) )
> +ÂÂÂÂÂÂÂÂ__replq_insert(ops, svc);
> +ÂÂÂÂ
And here I am again: is it really necessary to check whether svc is not
in the replenishment queue? It looks to me that it really should not be
there... but maybe it can, because we remove the event from the queue
when the vcpu sleeps, but *not* when the vcpu blocks?

> @@ -1168,6 +1259,80 @@ 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 )
> +ÂÂÂÂÂÂÂÂ{
> +ÂÂÂÂÂÂÂÂÂÂÂÂ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);
> +
> +ÂÂÂÂÂÂÂÂÂÂÂÂ/* update replenishment event queue */
> +ÂÂÂÂÂÂÂÂÂÂÂÂ__replq_remove(ops, svc);
> +ÂÂÂÂÂÂÂÂÂÂÂÂ__replq_insert(ops, svc);
> +ÂÂÂÂÂÂÂÂ}
> +
> +ÂÂÂÂÂÂÂÂelse
> +ÂÂÂÂÂÂÂÂÂÂÂÂbreak;
>
Invert the logic here:

  if ( now < svc->cur_deadline )
    break;

 ÂÂrt_update_deadline(now, svc);
  ...

Thanks and 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