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

2016-03-19 Thread Dario Faggioli 
On Wed, 2016-03-16 at 11:43 -0400, Chen, Tianyang wrote:
> 
> On 03/16/2016 10:25 AM, Dario Faggioli wrote:
> > 
> > This is too detailed for a changelog. If you want this information
> > to
> > live somewhere (it already lives in the list archives, actually),
> > make
> > a cover letter (this is just one patch, so it's not required, but
> > nothing forbids that). Or put it in a wiki page. Or write a blog
> > post.
> > Or (which would be kind of nice) all of them! :-)
> > 
> I was thinking about this as well. The wiki will look a bit outdated
> for 
> RTDS if this patch goes through. Meng: Do you think we should put
> extra 
> information in the wiki? Someone's gotta update it sooner or later.
> 
No need to ask. More information / more updated information on the wiki
is just __always__ a good thing.

So, feel free to go ahead and make it so. If no one of you has write
access, there is a procedure in the wiki itself to request for that (or
just create an user and tell it to me, I think I should be able to
enable that for you).

Regards,
Dario
-- 
<> (Raistlin Majere)
-
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R Ltd., Cambridge (UK)



signature.asc
Description: This is a digitally signed message part
___
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel

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

2016-03-19 Thread Dario Faggioli 
Ok, it's about time that we deal with this changelog!

On Mon, 2016-03-14 at 20:04 -0400, Tianyang Chen wrote:
> Budget replenishment and enforcement are separated by adding
> a replenishment timer, which fires at the next most imminent
> release time of all runnable vcpus.
> 
First of all, state (quickly) the "problems". So, right now:
 - the scheduler, although the algorithm is event driven by nature, 
   follow a time driven model (is invoked periodically!), making the 
   code looks unnatural;
 - budget replenishment logic, budget enforcement logic and scheduling
   decisions are mixed and entangled, making the code hard to 
   understand;
 - the various queues of vcpus are scanned various times, making the 
   code inefficient;

Then describe your solution. The first sentence you've got up above is
ok...

> A replenishment queue has been added to keep track of all vcpus that
> are runnable.
> 
...and this one too.

> The following functions have major changes to manage the
> replenishment
> events and timer.
> 
> repl_handler(): It is a timer handler which is re-programmed
> to fire at the nearest vcpu deadline to replenish vcpus.
> 
> rt_schedule(): picks the highest runnable vcpu based on cpu
> affinity and ret.time will be passed to schedule(). If an idle
> vcpu is picked, -1 is returned to avoid busy-waiting. repl_update()
> has been removed.
> 
> rt_vcpu_wake(): when a vcpu wakes up, it tickles instead of
> picking one from the run queue.
> 
> rt_context_saved(): when context switching is finished, the
> preempted vcpu will be put back into the runq.
> 
This is too detailed for a changelog. If you want this information to
live somewhere (it already lives in the list archives, actually), make
a cover letter (this is just one patch, so it's not required, but
nothing forbids that). Or put it in a wiki page. Or write a blog post.
Or (which would be kind of nice) all of them! :-)

Just a few more words, in addition of the above two sentences, covering
the other changes done in the patch are more than enough. Such as:

"In the main scheduling function, we now return the next time when a
making a scheduling decision is going to be necessary, such as when the
budget of the currently running vcpu will run over.

Finally, when waking up a vcpu, it is now enough to tickle the various
CPUs appropriately, like all other schedulers also do."

> Simplified funtional graph:
> 
> schedule.c SCHEDULE_SOFTIRQ:
> rt_schedule():
> [spin_lock]
> burn_budget(scurr)
> snext = runq_pick()
> [spin_unlock]
> 
> sched_rt.c TIMER_SOFTIRQ
> replenishment_timer_handler()
> [spin_lock]
>  {
> replenish(i)
> runq_tickle(i)
> }>
> program_timer()
> [spin_lock]
> 
And kill this (or, again, move to cover, wiki, blog, etc.) as well.

Also, trying to apply this gave:

/* 
:194: trailing whitespace.
 * A helper function that only removes a vcpu from a queue 
:355: trailing whitespace.
/* 
:356: trailing whitespace.
 * The timer initialization will happen later when 
:380: trailing whitespace.
{   
warning: squelched 10 whitespace errors
warning: 15 lines add whitespace errors.

And I think there are a couple of long lines as well.

> --- a/xen/common/sched_rt.c
> +++ b/xen/common/sched_rt.c
> @@ -3,7 +3,9 @@
>   * EDF scheduling is a real-time scheduling algorithm used in
> embedded field.
>   *
>   * by Sisu Xi, 2013, Washington University in Saint Louis
> - * and Meng Xu, 2014, University of Pennsylvania
> + * Meng Xu, 2014-2016, University of Pennsylvania
> + * Tianyang Chen, 2016, University of Pennsylvania
> + * Dagaen Golomb, 2016, University of Pennsylvania
>   *
 * Meng Xu, 2014-2016, University of Pennsylvania.
 *
 * Conversion toward event drive model by Tianyang Chen
 * and Dagaen Golomb, 2016, University of Pennsylvania.

> @@ -115,6 +118,18 @@
>  #define RTDS_delayed_runq_add (1<<__RTDS_delayed_runq_add)
>  
>  /*
> + * The replenishment timer handler needs to check this bit
> + * to know where a replenished vcpu was, when deciding which
> + * vcpu should tickle.
> + * A replenished vcpu should tickle if it was moved from the
> + * depleted queue to the run queue.
> + * + Set in burn_budget() if a vcpu has zero budget left.
> + * + Cleared and checked in the repenishment handler.
> + */
>
Stuff about how the replenishment timer handler uses it, with this
level of details, is better said in the replenishment timer handler
itself. Such that, if at some point we'll use this flag for other
things, we will not have to change this comment!

Just limit to what the flag is meant at representing. So, to sort of
follow the style of other similar comments (yes, perhaps it's not too
bad :-D).

And I'd lose the _was in the name.

/*
 * RTDS_depleted: does this vcpu run out of budget?
 * This flag is:
 * + set in burn_budget(), if a vcpu has zero budget left;
 * + checked and cleared in the

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

2016-03-19 Thread Meng Xu 
On Wed, Mar 16, 2016 at 6:23 AM, Dario Faggioli
 wrote:
> On Tue, 2016-03-15 at 23:40 -0400, Meng Xu wrote:
>> > > > @@ -115,6 +118,18 @@
>> > > >   #define RTDS_delayed_runq_add (1<<__RTDS_delayed_runq_add)
>> > > >
>> > > >   /*
>> > > > + * The replenishment timer handler needs to check this bit
>> > > > + * to know where a replenished vcpu was, when deciding which
>> > > > + * vcpu should tickle.
>> > > > + * A replenished vcpu should tickle if it was moved from the
>> > > > + * depleted queue to the run queue.
>> > > > + * + Set in burn_budget() if a vcpu has zero budget left.
>> > > > + * + Cleared and checked in the repenishment handler.
>> > >
>> > > It seems you have an extra + here...
>> > > Need to be removed.
>> > >
>> > > My bad, I didn't spot it out in last patch... :-(
>> > >
>> > You mean before "Cleared"? For __RTDS_scheduled there are '+'
>> > before
>> > 'Cleared', 'Checked', 'Set'.
>> Yes, those two +, are unnecessary. Isn't it?
>>
> I *think* the idea here was to sort of put down a bullet-ed list, but
> maybe we should ask the author. According to `git blame', is a certain
> Meng Xu, guy (commit 8726c055), anyone has his email address? :-D :-D

Ah-ha, let me try to find the Meng Xu. ;-)
Here we go. I cc.ed him... ;-)

>
> However, I don't particularly like either the style or the final result
> (in terms of wording), so, let's avoid doing more of that in new code
> (see my other email).

I checked the sched_credit.c and sched_credit2.c, it seems that either
+ or - is used as the list. When there are two levels of lists, both
are used.
However, it's inconsistent which one should be used at the top level.
Probably to keep the consistence in this file, we keep using + and
later when we want to clean up this style issue, if we will ,we can
replace them.

As to the comment, I will suggest:

/*
 * RTDS_was_depleted: Is a vcpus budget depleted?

 * + Set in burn_budget() when a vcpus budget turns to zero

 * + Checked and cleared in repl_handler() to replenish the budget

 */

What do you think?

BTW, how about other parts of the patch? Is there something that you don't like?
I think the invalid budget returned in rt_schedule() in this patch is
a serious logical bug.
If all of my comments are solved, I think it is in a good state and
I'm considering to send the reviewed-by tag in the near future.
However, I won't send the reviewed-by until I get your confirmation,
since this will be the first reviewed-by I will be giving as
maintainer. I'd like to take a safe step. :-D

Thanks and Best Regards,

Meng

-- 
Meng Xu
PhD Student in Computer and Information Science
University of Pennsylvania
http://www.cis.upenn.edu/~mengxu/

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

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

2016-03-19 Thread Chen, Tianyang 



On 03/16/2016 10:25 AM, Dario Faggioli wrote:

Ok, it's about time that we deal with this changelog!

On Mon, 2016-03-14 at 20:04 -0400, Tianyang Chen wrote:

Budget replenishment and enforcement are separated by adding
a replenishment timer, which fires at the next most imminent
release time of all runnable vcpus.


First of all, state (quickly) the "problems". So, right now:
  - the scheduler, although the algorithm is event driven by nature,
follow a time driven model (is invoked periodically!), making the
code looks unnatural;
  - budget replenishment logic, budget enforcement logic and scheduling
decisions are mixed and entangled, making the code hard to
understand;
  - the various queues of vcpus are scanned various times, making the
code inefficient;

Then describe your solution. The first sentence you've got up above is
ok...


A replenishment queue has been added to keep track of all vcpus that
are runnable.


...and this one too.


The following functions have major changes to manage the
replenishment
events and timer.

repl_handler(): It is a timer handler which is re-programmed
to fire at the nearest vcpu deadline to replenish vcpus.

rt_schedule(): picks the highest runnable vcpu based on cpu
affinity and ret.time will be passed to schedule(). If an idle
vcpu is picked, -1 is returned to avoid busy-waiting. repl_update()
has been removed.

rt_vcpu_wake(): when a vcpu wakes up, it tickles instead of
picking one from the run queue.

rt_context_saved(): when context switching is finished, the
preempted vcpu will be put back into the runq.


This is too detailed for a changelog. If you want this information to
live somewhere (it already lives in the list archives, actually), make
a cover letter (this is just one patch, so it's not required, but
nothing forbids that). Or put it in a wiki page. Or write a blog post.
Or (which would be kind of nice) all of them! :-)



I was thinking about this as well. The wiki will look a bit outdated for 
RTDS if this patch goes through. Meng: Do you think we should put extra 
information in the wiki? Someone's gotta update it sooner or later.


Thanks for the review Dario. I will put everything together soon.

Tianyang


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

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

2016-03-19 Thread Chen, Tianyang 



On 03/16/2016 10:25 AM, Dario Faggioli wrote:

+if ( curr_on_cpu(vc->processor) == vc &&
>+ ( !list_empty(runq) ) )
>

So, this is because, since we don't keep the idle vcpus in the
runqueues, we need to catch the case where v is running, but no other
vcpu is waiting on the runqueue in runnable state, is this right?

In any case, parentheses around the second part of the && seems
pointless.



Yes. If there is no vcpu waiting on the run queue then there is no need 
to compare deadlines and tickle.


Tianyang

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

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

2016-03-19 Thread Dario Faggioli 
On Wed, 2016-03-16 at 10:20 -0400, Meng Xu wrote:
> As to the comment, I will suggest:
> 
> /*
>  * RTDS_was_depleted: Is a vcpus budget depleted?
> 
>  * + Set in burn_budget() when a vcpus budget turns to zero
> 
>  * + Checked and cleared in repl_handler() to replenish the budget
> 
>  */
> 
> What do you think?
> 
Wow, we really are on the same page, I just suggested something quite
similar to this.

> BTW, how about other parts of the patch? Is there something that you
> don't like?
>
I just sent in my comments. I did have a few of them, I'm afraid.

Still, there weren't anything really substantial, from the logical or
algorithmical point of view. They almost all are about how to make both
the patch and the final result as easy to understand as possible.

This patch is doing some important and serious rework, of a piece of
code which is not in the best possible shape, so I consider the above
really really important.

> I think the invalid budget returned in rt_schedule() in this patch is
> a serious logical bug.
>
It's a bug. And you did a good job catching it. That's it. :-)

> If all of my comments are solved, I think it is in a good state and
> I'm considering to send the reviewed-by tag in the near future.
>
Sure!

I don't expect it to take much longer for me to also be able to give
green light. :-)

> However, I won't send the reviewed-by until I get your confirmation,
> since this will be the first reviewed-by I will be giving as
> maintainer. I'd like to take a safe step. :-D
> 
Mmm... That's not how it works, though. I know the feeling, and we've
all been there, I guess. However, you see and are saying yourself
already that such attitude from you can't really fly, in the long run.

Do as you wish, but you must know that you lost the right of "taking
safe steps" when you've become part of the MAINTAINERS file. :-P

So, jokes aside, it's perfectly fine that, as soon as you're happy
about the status of the patch, you send in your tag. In this specific
case, even if you are a maintainer, that would not mean the patch could
go in, because there are outstanding comments from another maintainer. 

And yes, this means that co-maintainers are not entirely agreeing on
the readiness of a particular patch, but it's not at all a big deal...
It happens quite frequently, actually! :-)

So, again, I understand the feeling... But it really reduces to "with
great powers comes great responsibility". And just like in the movie
(which I don't even like that much!! :-/), the sooner you accept that,
the better. For you. For us. For the project. For the World. :-D :-D

Regards,
Dario
-- 
<> (Raistlin Majere)
-
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R Ltd., Cambridge (UK)



signature.asc
Description: This is a digitally signed message part
___
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel

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

2016-03-19 Thread Meng Xu 
>> This is too detailed for a changelog. If you want this information to
>> live somewhere (it already lives in the list archives, actually), make
>> a cover letter (this is just one patch, so it's not required, but
>> nothing forbids that). Or put it in a wiki page. Or write a blog post.
>> Or (which would be kind of nice) all of them! :-)
>>
>
> I was thinking about this as well. The wiki will look a bit outdated for
> RTDS if this patch goes through. Meng: Do you think we should put extra
> information in the wiki? Someone's gotta update it sooner or later.
>
> Thanks for the review Dario. I will put everything together soon.

You can just register an account on Xen wiki and you can update it directly...

It's always good to have more detailed correct information on the wiki.

Thanks and best regards,

Meng

-- 
Meng Xu
PhD Student in Computer and Information Science
University of Pennsylvania
http://www.cis.upenn.edu/~mengxu/

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

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

2016-03-18 Thread Meng Xu 
>>
>> sched_rt.c TIMER_SOFTIRQ
>> replenishment_timer_handler()
>> [spin_lock]
>>  {
>> replenish(i)
>> runq_tickle(i)
>> }>
>> program_timer()
>> [spin_lock]
>>
> And kill this (or, again, move to cover, wiki, blog, etc.) as well.
>
> Also, trying to apply this gave:
>
> /*
> :194: trailing whitespace.
>  * A helper function that only removes a vcpu from a queue
> :355: trailing whitespace.
> /*
> :356: trailing whitespace.
>  * The timer initialization will happen later when
> :380: trailing whitespace.
> {
> warning: squelched 10 whitespace errors
> warning: 15 lines add whitespace errors.
>
> And I think there are a couple of long lines as well.
Tianyang,

You can configure the git to mark whitespace in color.
One approach can be found at
http://stackoverflow.com/questions/5257553/coloring-white-space-in-git-diffs-output

Thanks,

Meng

-- 
Meng Xu
PhD Student in Computer and Information Science
University of Pennsylvania
http://www.cis.upenn.edu/~mengxu/

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

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

2016-03-18 Thread Meng Xu 
On Wed, Mar 16, 2016 at 10:44 AM, Dario Faggioli
 wrote:
> On Wed, 2016-03-16 at 10:20 -0400, Meng Xu wrote:
>> As to the comment, I will suggest:
>>
>> /*
>>  * RTDS_was_depleted: Is a vcpus budget depleted?
>>
>>  * + Set in burn_budget() when a vcpus budget turns to zero
>>
>>  * + Checked and cleared in repl_handler() to replenish the budget
>>
>>  */
>>
>> What do you think?
>>
> Wow, we really are on the same page, I just suggested something quite
> similar to this.

Right. :-)

>
>> BTW, how about other parts of the patch? Is there something that you
>> don't like?
>>
> I just sent in my comments. I did have a few of them, I'm afraid.

Thank you very much! I saw it! I see the point. I didn't think too
much about the better choice of the comments.
Those suggestions make the comment more useful... Thank you very much! :-)

>
> This patch is doing some important and serious rework, of a piece of
> code which is not in the best possible shape, so I consider the above
> really really important.

Right! But those are easy to solve. :-)

>
>> I think the invalid budget returned in rt_schedule() in this patch is
>> a serious logical bug.
>>
> It's a bug. And you did a good job catching it. That's it. :-)
>
>> If all of my comments are solved, I think it is in a good state and
>> I'm considering to send the reviewed-by tag in the near future.
>>
> Sure!
>
> I don't expect it to take much longer for me to also be able to give
> green light. :-)

Great!

>
>> However, I won't send the reviewed-by until I get your confirmation,
>> since this will be the first reviewed-by I will be giving as
>> maintainer. I'd like to take a safe step. :-D
>>
> Mmm... That's not how it works, though. I know the feeling, and we've
> all been there, I guess. However, you see and are saying yourself
> already that such attitude from you can't really fly, in the long run.

Right! I understood...

>
> Do as you wish, but you must know that you lost the right of "taking
> safe steps" when you've become part of the MAINTAINERS file. :-P

OK... Then I will send the tag when I feel comfortable with the patch then.

>
> So, jokes aside, it's perfectly fine that, as soon as you're happy
> about the status of the patch, you send in your tag. In this specific
> case, even if you are a maintainer, that would not mean the patch could
> go in, because there are outstanding comments from another maintainer.

I see. Good to know that. :-)

>
> And yes, this means that co-maintainers are not entirely agreeing on
> the readiness of a particular patch, but it's not at all a big deal...
> It happens quite frequently, actually! :-)
>
> So, again, I understand the feeling... But it really reduces to "with
> great powers comes great responsibility". And just like in the movie
> (which I don't even like that much!! :-/), the sooner you accept that,
> the better. For you. For us. For the project. For the World. :-D :-D

Sure! OK... No problem. The worst case is that I have to "kill the
bug" that passed me. :-D

Thank you very much!

Best Regards,

Meng

---
Meng Xu
PhD Student in Computer and Information Science
University of Pennsylvania
http://www.cis.upenn.edu/~mengxu/

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

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

2016-03-16 Thread Dario Faggioli 
On Tue, 2016-03-15 at 23:40 -0400, Meng Xu wrote:
> > > > @@ -115,6 +118,18 @@
> > > >   #define RTDS_delayed_runq_add (1<<__RTDS_delayed_runq_add)
> > > > 
> > > >   /*
> > > > + * The replenishment timer handler needs to check this bit
> > > > + * to know where a replenished vcpu was, when deciding which
> > > > + * vcpu should tickle.
> > > > + * A replenished vcpu should tickle if it was moved from the
> > > > + * depleted queue to the run queue.
> > > > + * + Set in burn_budget() if a vcpu has zero budget left.
> > > > + * + Cleared and checked in the repenishment handler.
> > > 
> > > It seems you have an extra + here...
> > > Need to be removed.
> > > 
> > > My bad, I didn't spot it out in last patch... :-(
> > > 
> > You mean before "Cleared"? For __RTDS_scheduled there are '+'
> > before
> > 'Cleared', 'Checked', 'Set'.
> Yes, those two +, are unnecessary. Isn't it?
> 
I *think* the idea here was to sort of put down a bullet-ed list, but
maybe we should ask the author. According to `git blame', is a certain
Meng Xu, guy (commit 8726c055), anyone has his email address? :-D :-D

However, I don't particularly like either the style or the final result
(in terms of wording), so, let's avoid doing more of that in new code
(see my other email).

Regards,
Dario
-- 
<> (Raistlin Majere)
-
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R Ltd., Cambridge (UK)



signature.asc
Description: This is a digitally signed message part
___
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel

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

2016-03-15 Thread Meng Xu 
>>> @@ -115,6 +118,18 @@
>>>   #define RTDS_delayed_runq_add (1<<__RTDS_delayed_runq_add)
>>>
>>>   /*
>>> + * The replenishment timer handler needs to check this bit
>>> + * to know where a replenished vcpu was, when deciding which
>>> + * vcpu should tickle.
>>> + * A replenished vcpu should tickle if it was moved from the
>>> + * depleted queue to the run queue.
>>> + * + Set in burn_budget() if a vcpu has zero budget left.
>>> + * + Cleared and checked in the repenishment handler.
>>
>>
>> It seems you have an extra + here...
>> Need to be removed.
>>
>> My bad, I didn't spot it out in last patch... :-(
>>
>
> You mean before "Cleared"? For __RTDS_scheduled there are '+' before
> 'Cleared', 'Checked', 'Set'.

Yes, those two +, are unnecessary. Isn't it?

>
>>> @@ -840,8 +991,6 @@ rt_schedule(const struct scheduler *ops, s_time_t
>>> now, bool_t tasklet_work_sched
>>>   /* burn_budget would return for IDLE VCPU */
>>>   burn_budget(ops, scurr, now);
>>>
>>> -__repl_update(ops, now);
>>> -
>>>   if ( tasklet_work_scheduled )
>>>   {
>>>   trace_var(TRC_RTDS_SCHED_TASKLET, 1, 0,  NULL);
>>> @@ -868,6 +1017,7 @@ rt_schedule(const struct scheduler *ops, s_time_t
>>> now, bool_t tasklet_work_sched
>>>   set_bit(__RTDS_delayed_runq_add, >flags);
>>>
>>>   snext->last_start = now;
>>> +ret.time =  -1; /* if an idle vcpu is picked */
>>>   if ( !is_idle_vcpu(snext->vcpu) )
>>>   {
>>>   if ( snext != scurr )
>>> @@ -880,9 +1030,8 @@ rt_schedule(const struct scheduler *ops, s_time_t
>>> now, bool_t tasklet_work_sched
>>>   snext->vcpu->processor = cpu;
>>>   ret.migrated = 1;
>>>   }
>>> +ret.time = snext->budget; /* invoke the scheduler next time */
>>
>>
>> Ah, this is incorrect, although this is easy to fix.
>>
>> The ret.time is the relative time when the *budget enforcement* timer
>> should be invoked.
>> Since snext is not always full budget, it may have already consumed some
>> budget.
>>
>> It should be
>> ret.time = snext->cur_budget
>>
>> Isn't it? :-)
>
> Good catch. This bug kinda ruins the fix for busy waiting.

Right! This just shows why we may need some semi-automated testing
tools to test the logic correctness. ;-)

Meng



-- 
---
Meng Xu
PhD Student in Computer and Information Science
University of Pennsylvania
http://www.cis.upenn.edu/~mengxu/

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

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

2016-03-15 Thread Chen, Tianyang 



On 03/15/2016 11:11 PM, Meng Xu wrote:

+
  /*
   * Flags
   */
@@ -115,6 +118,18 @@
  #define RTDS_delayed_runq_add (1<<__RTDS_delayed_runq_add)

  /*
+ * The replenishment timer handler needs to check this bit
+ * to know where a replenished vcpu was, when deciding which
+ * vcpu should tickle.
+ * A replenished vcpu should tickle if it was moved from the
+ * depleted queue to the run queue.
+ * + Set in burn_budget() if a vcpu has zero budget left.
+ * + Cleared and checked in the repenishment handler.


It seems you have an extra + here...
Need to be removed.

My bad, I didn't spot it out in last patch... :-(



You mean before "Cleared"? For __RTDS_scheduled there are '+' before 
'Cleared', 'Checked', 'Set'.



@@ -840,8 +991,6 @@ rt_schedule(const struct scheduler *ops, s_time_t now, 
bool_t tasklet_work_sched
  /* burn_budget would return for IDLE VCPU */
  burn_budget(ops, scurr, now);

-__repl_update(ops, now);
-
  if ( tasklet_work_scheduled )
  {
  trace_var(TRC_RTDS_SCHED_TASKLET, 1, 0,  NULL);
@@ -868,6 +1017,7 @@ rt_schedule(const struct scheduler *ops, s_time_t now, 
bool_t tasklet_work_sched
  set_bit(__RTDS_delayed_runq_add, >flags);

  snext->last_start = now;
+ret.time =  -1; /* if an idle vcpu is picked */
  if ( !is_idle_vcpu(snext->vcpu) )
  {
  if ( snext != scurr )
@@ -880,9 +1030,8 @@ rt_schedule(const struct scheduler *ops, s_time_t now, 
bool_t tasklet_work_sched
  snext->vcpu->processor = cpu;
  ret.migrated = 1;
  }
+ret.time = snext->budget; /* invoke the scheduler next time */


Ah, this is incorrect, although this is easy to fix.

The ret.time is the relative time when the *budget enforcement* timer
should be invoked.
Since snext is not always full budget, it may have already consumed some budget.

It should be
ret.time = snext->cur_budget

Isn't it? :-)

Good catch. This bug kinda ruins the fix for busy waiting.

Thanks,
Tianyang


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

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

2016-03-15 Thread Meng Xu 
On Mon, Mar 14, 2016 at 8:04 PM, Tianyang Chen  wrote:
> Budget replenishment and enforcement are separated by adding
> a replenishment timer, which fires at the next most imminent
> release time of all runnable vcpus.
>
> A replenishment queue has been added to keep track of all vcpus that
> are runnable.
>
> The following functions have major changes to manage the replenishment
> events and timer.
>
> repl_handler(): It is a timer handler which is re-programmed
> to fire at the nearest vcpu deadline to replenish vcpus.
>
> rt_schedule(): picks the highest runnable vcpu based on cpu
> affinity and ret.time will be passed to schedule(). If an idle
> vcpu is picked, -1 is returned to avoid busy-waiting. repl_update()
> has been removed.
>
> rt_vcpu_wake(): when a vcpu wakes up, it tickles instead of
> picking one from the run queue.
>
> rt_context_saved(): when context switching is finished, the
> preempted vcpu will be put back into the runq.
>
> Simplified funtional graph:
>
> schedule.c SCHEDULE_SOFTIRQ:
> rt_schedule():
> [spin_lock]
> burn_budget(scurr)
> snext = runq_pick()
> [spin_unlock]
>
> sched_rt.c TIMER_SOFTIRQ
> replenishment_timer_handler()
> [spin_lock]
>  {
> replenish(i)
> runq_tickle(i)
> }>
> program_timer()
> [spin_lock]
>
> Signed-off-by: Tianyang Chen 
> Signed-off-by: Meng Xu 
> Signed-off-by: Dagaen Golomb 
> ---
> changes since v8:
> Replaced spin_lock_irqsave with spin_lock_irq.
> Bug fix in burn_budget() where budget == 0.
> Removed unnecessary tickling in the timer handler when
> vcpus have the same deadline.
>
> changes since v7:
> Coding sytle.
> Added a flag to indicate that a vcpu was depleted.
> Added a local list including updated vcpus in the
> timer handler. It is used to decide which vcpu should
> tickle.
>
> changes since v6:
> Removed unnecessary vcpu_on_q() checks for runq_insert()
> Renamed replenishment queue related functions without
> underscores
> New replq_reinsert() function for rt_vcpu_wake()
>
> changes since v5:
> Removed unnecessary vcpu_on_replq() checks
> deadline_queue_insert() returns a flag to indicate if it's
> needed to re-program the timer
> Removed unnecessary timer checks
> Added helper functions to remove vcpus from queues
> coding style
>
> 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.
> ---
>  xen/common/sched_rt.c |  437 
> ++---
>  1 file changed, 341 insertions(+), 96 deletions(-)
>
> diff --git a/xen/common/sched_rt.c b/xen/common/sched_rt.c
> index bfed2e2..b491915 100644
> --- a/xen/common/sched_rt.c
> +++ b/xen/common/sched_rt.c
> @@ -3,7 +3,9 @@
>   * EDF scheduling is a real-time scheduling algorithm used in embedded field.
>   *
>   * by Sisu Xi, 2013, Washington University in Saint Louis
> - * and Meng Xu, 2014, University of Pennsylvania
> + * Meng Xu, 2014-2016, University of Pennsylvania
> + * Tianyang Chen, 2016, University of Pennsylvania
> + * Dagaen Golomb, 2016, University of Pennsylvania
>   *
>   * based on the code of credit Scheduler
>   */
> @@ -16,6 +18,7 @@
>  #include 
>  #include 
>  #include 
> +#include 
>  #include 
>  #include 
>  #include 
> @@ -87,7 +90,7 @@
>  #define RTDS_DEFAULT_BUDGET (MICROSECS(4000))
>
>  #define UPDATE_LIMIT_SHIFT  10
> -#define MAX_SCHEDULE(MILLISECS(1))
> +
>  /*
>   * Flags
>   */
> @@ -115,6 +118,18 @@
>  #define RTDS_delayed_runq_add (1<<__RTDS_delayed_runq_add)
>
>  /*
> + * The replenishment timer handler needs to check this bit
> + * to know where a replenished vcpu was, when deciding which
> + * vcpu should tickle.
> + * A replenished vcpu should tickle if it was moved from the
> + * depleted queue to the run queue.
> + * + Set in burn_budget() if a vcpu has zero budget left.
> + * + Cleared and checked in the repenishment handler.

It seems you have an extra + here...
Need to be removed.

My bad, I didn't spot it out in last patch... :-(

> + */
> +#define __RTDS_was_depleted 3
> +#define RTDS_was_depleted (1<<__RTDS_was_depleted)
> +
> +/*
>   * rt tracing events ("only" 512 available!). Check
>   * include/public/trace.h for more details.
>   */
> @@ -142,6 +157,9 @@ static cpumask_var_t *_cpumask_scratch;
>   */
>  static unsigned int nr_rt_ops;
>
> +/* handler for the replenishment timer */
> +static void

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

2016-03-14 Thread Tianyang Chen 
Budget replenishment and enforcement are separated by adding
a replenishment timer, which fires at the next most imminent
release time of all runnable vcpus.

A replenishment queue has been added to keep track of all vcpus that
are runnable.

The following functions have major changes to manage the replenishment
events and timer.

repl_handler(): It is a timer handler which is re-programmed
to fire at the nearest vcpu deadline to replenish vcpus.

rt_schedule(): picks the highest runnable vcpu based on cpu
affinity and ret.time will be passed to schedule(). If an idle
vcpu is picked, -1 is returned to avoid busy-waiting. repl_update()
has been removed.

rt_vcpu_wake(): when a vcpu wakes up, it tickles instead of
picking one from the run queue.

rt_context_saved(): when context switching is finished, the
preempted vcpu will be put back into the runq.

Simplified funtional graph:

schedule.c SCHEDULE_SOFTIRQ:
rt_schedule():
[spin_lock]
burn_budget(scurr)
snext = runq_pick()
[spin_unlock]

sched_rt.c TIMER_SOFTIRQ
replenishment_timer_handler()
[spin_lock]
 {
replenish(i)
runq_tickle(i)
}>
program_timer()
[spin_lock]

Signed-off-by: Tianyang Chen 
Signed-off-by: Meng Xu 
Signed-off-by: Dagaen Golomb 
---
changes since v8:
Replaced spin_lock_irqsave with spin_lock_irq.
Bug fix in burn_budget() where budget == 0.
Removed unnecessary tickling in the timer handler when
vcpus have the same deadline.

changes since v7:
Coding sytle.
Added a flag to indicate that a vcpu was depleted.
Added a local list including updated vcpus in the
timer handler. It is used to decide which vcpu should
tickle.

changes since v6:
Removed unnecessary vcpu_on_q() checks for runq_insert()
Renamed replenishment queue related functions without
underscores
New replq_reinsert() function for rt_vcpu_wake()

changes since v5:
Removed unnecessary vcpu_on_replq() checks
deadline_queue_insert() returns a flag to indicate if it's
needed to re-program the timer
Removed unnecessary timer checks
Added helper functions to remove vcpus from queues
coding style

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.
---
 xen/common/sched_rt.c |  437 ++---
 1 file changed, 341 insertions(+), 96 deletions(-)

diff --git a/xen/common/sched_rt.c b/xen/common/sched_rt.c
index bfed2e2..b491915 100644
--- a/xen/common/sched_rt.c
+++ b/xen/common/sched_rt.c
@@ -3,7 +3,9 @@
  * EDF scheduling is a real-time scheduling algorithm used in embedded field.
  *
  * by Sisu Xi, 2013, Washington University in Saint Louis
- * and Meng Xu, 2014, University of Pennsylvania
+ * Meng Xu, 2014-2016, University of Pennsylvania
+ * Tianyang Chen, 2016, University of Pennsylvania
+ * Dagaen Golomb, 2016, University of Pennsylvania
  *
  * based on the code of credit Scheduler
  */
@@ -16,6 +18,7 @@
 #include 
 #include 
 #include 
+#include 
 #include 
 #include 
 #include 
@@ -87,7 +90,7 @@
 #define RTDS_DEFAULT_BUDGET (MICROSECS(4000))
 
 #define UPDATE_LIMIT_SHIFT  10
-#define MAX_SCHEDULE(MILLISECS(1))
+
 /*
  * Flags
  */
@@ -115,6 +118,18 @@
 #define RTDS_delayed_runq_add (1<<__RTDS_delayed_runq_add)
 
 /*
+ * The replenishment timer handler needs to check this bit
+ * to know where a replenished vcpu was, when deciding which
+ * vcpu should tickle.
+ * A replenished vcpu should tickle if it was moved from the
+ * depleted queue to the run queue.
+ * + Set in burn_budget() if a vcpu has zero budget left.
+ * + Cleared and checked in the repenishment handler.
+ */
+#define __RTDS_was_depleted 3
+#define RTDS_was_depleted (1<<__RTDS_was_depleted)
+
+/*
  * rt tracing events ("only" 512 available!). Check
  * include/public/trace.h for more details.
  */
@@ -142,6 +157,9 @@ static cpumask_var_t *_cpumask_scratch;
  */
 static unsigned int nr_rt_ops;
 
+/* handler for the replenishment timer */
+static void repl_handler(void *data);
+
 /*
  * Systme-wide private data, include global RunQueue/DepletedQ
  * Global lock is referenced by schedule_data.schedule_lock from all
@@ -152,7 +170,9 @@ struct rt_private {
 struct list_head sdom;  /* list of availalbe domains, used for dump */
 struct list_head runq;  /* ordered list of runnable vcpus */
 struct list_head depletedq; /* unordered list of depleted vcpus */
+struct list_head replq;