George Dunlap
2013-Jan-24 15:24 UTC
[PATCH] xen, credit2: Avoid extra c2t calcuation in csched_runtime
# HG changeset patch # User George Dunlap <george.dunlap@eu.citrix.com> # Date 1359040980 0 # Node ID e9222438074a73cb3c93cf21d53a6d9224a48e4c # Parent 14b0f2e95cb21a94fa154bec56e7925c01e81b56 xen,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. The effect of the new code should be the same as the old code. Spotted-by: Jan Beulich <JBeulich@suse.com> Signed-off-by: George Dunlap <george.dunlap@eu.citrix.com> diff --git a/xen/common/sched_credit2.c b/xen/common/sched_credit2.c --- a/xen/common/sched_credit2.c +++ b/xen/common/sched_credit2.c @@ -1505,31 +1505,42 @@ csched_dom_destroy(const struct schedule 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 rt_credit, time; /* 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. + */ - /* Next guy on runqueue */ + /* 1) Basic time: Run until credit is 0. */ + rt_credit = snext->credit; + + /* 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; } } + /* 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;
Jan Beulich
2013-Jan-24 15:45 UTC
Re: [PATCH] xen, credit2: Avoid extra c2t calcuation in csched_runtime
>>> On 24.01.13 at 16:24, George Dunlap <george.dunlap@eu.citrix.com> wrote: > --- a/xen/common/sched_credit2.c > +++ b/xen/common/sched_credit2.c > @@ -1505,31 +1505,42 @@ csched_dom_destroy(const struct schedule > 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 rt_credit, time; /* Proposed runtime measured in credits */Does rt_credit really need to be s_time_t rather than int?> 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. > + */ > > - /* Next guy on runqueue */ > + /* 1) Basic time: Run until credit is 0. */ > + rt_credit = snext->credit; > + > + /* 2) If there''s someone waiting whose credit is positive,... who''s ...?> + * 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; > } > } > > + /* 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. */The obvious situation is when rt_credit <= 0, which you could deal with right away. Jan> + time = c2t(rqd, rt_credit, snext); > + > /* Check limits */ > if ( time < CSCHED_MIN_TIMER ) > time = CSCHED_MIN_TIMER;
Tim Deegan
2013-Jan-24 15:53 UTC
Re: [PATCH] xen, credit2: Avoid extra c2t calcuation in csched_runtime
At 15:45 +0000 on 24 Jan (1359042332), Jan Beulich wrote:> > + /* 2) If there''s someone waiting whose credit is positive, > > ... who''s ...?No; "whose" is correct. Tim.
George Dunlap
2013-Jan-24 15:55 UTC
Re: [PATCH] xen, credit2: Avoid extra c2t calcuation in csched_runtime
On 24/01/13 15:45, Jan Beulich wrote:>>>> On 24.01.13 at 16:24, George Dunlap <george.dunlap@eu.citrix.com> wrote: >> --- a/xen/common/sched_credit2.c >> +++ b/xen/common/sched_credit2.c >> @@ -1505,31 +1505,42 @@ csched_dom_destroy(const struct schedule >> 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 rt_credit, time; /* Proposed runtime measured in credits */ > Does rt_credit really need to be s_time_t rather than int?I suppose not...> >> 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. >> + */ >> >> - /* Next guy on runqueue */ >> + /* 1) Basic time: Run until credit is 0. */ >> + rt_credit = snext->credit; >> + >> + /* 2) If there''s someone waiting whose credit is positive, > ... who''s ...?Nope. :-) "Who''s" is short for "who is". "Whose" is a pronoun which links back to "someone waiting". (I suppose "whose" is the person version of "which", which I used in both the previous sentence and this one.)>> + * 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; >> } >> } >> >> + /* 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. */ > The obvious situation is when rt_credit <= 0, which you could > deal with right away.That shouldn''t be possible: 1. csched_runtime() should only be called on someone about to be scheduled (from csched_schedule()). 2. The credit of such an snext should always be higher than anyone else on the queue (or they would be scheduled instead). 3. If someone is about to be scheduled with snext->credit <= 0, it will trigger reset_credt(), which will make everyone''s credit positive. 4. 3 guarantees that snext->credit will be positive 5. 2 guatantees that (snext->credit - swait->credit) will be positive 6 So rt_credit should never be <= 0. I can add an assert to this effect if you like. -George
Jan Beulich
2013-Jan-24 16:10 UTC
Re: [PATCH] xen, credit2: Avoid extra c2t calcuation in csched_runtime
>>> On 24.01.13 at 16:55, George Dunlap <george.dunlap@eu.citrix.com> wrote: > On 24/01/13 15:45, Jan Beulich wrote: >>>>> On 24.01.13 at 16:24, George Dunlap <george.dunlap@eu.citrix.com> wrote: >>> + /* 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. */ >> The obvious situation is when rt_credit <= 0, which you could >> deal with right away. > > That shouldn''t be possible: > 1. csched_runtime() should only be called on someone about to be > scheduled (from csched_schedule()). > 2. The credit of such an snext should always be higher than anyone else > on the queue (or they would be scheduled instead). > 3. If someone is about to be scheduled with snext->credit <= 0, it will > trigger reset_credt(), which will make everyone''s credit positive. > 4. 3 guarantees that snext->credit will be positive > 5. 2 guatantees that (snext->credit - swait->credit) will be positive > 6 So rt_credit should never be <= 0. > > I can add an assert to this effect if you like.That would be nice, because I came up with the whole thing just because I was trying to understand whether the 2nd argument to c2t() in the invocation this change removes could go negative. Jan
George Dunlap
2013-Jan-24 16:10 UTC
Re: [PATCH] xen, credit2: Avoid extra c2t calcuation in csched_runtime
On 24/01/13 15:55, George Dunlap wrote:>> >>> 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. >>> + */ >>> - /* Next guy on runqueue */ >>> + /* 1) Basic time: Run until credit is 0. */ >>> + rt_credit = snext->credit; >>> + >>> + /* 2) If there''s someone waiting whose credit is positive, >> ... who''s ...? > > Nope. :-) "Who''s" is short for "who is". "Whose" is a pronoun which > links back to "someone waiting". (I suppose "whose" is the person > version of "which", which I used in both the previous sentence and > this one.)OK, for the really serious grammar students: "Whose" isn''t a pronoun, it''s an adjective indicating "owned by who" or "of who"; in this case, "whose" is modifying "credit". It''s a similar construction to the following: "If there''s someone waiting who has positive credit, ..." -George