Re: [Xen-devel] [PATCH 2/2] credit2: Reset until the front of the runqueue is positive

["Jan Beulich" <JBeulich@xxxxxxxx>]

>>> On 08.03.13 at 16:04, George Dunlap <george.dunlap@xxxxxxxxxxxxx> wrote:
> On 08/03/13 14:35, Jan Beulich wrote:
>>>>> On 08.03.13 at 15:14, George Dunlap <george.dunlap@xxxxxxxxxxxxx> wrote:
>>> 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.
>>>
>>> Signed-off-by: George Dunlap <george.dunlap@xxxxxxxxxxxxx>
>>> ---
>>>   xen/common/sched_credit2.c |   81 
>>> +++++++++++++++++++++++++++-----------------
>>>   1 file changed, 49 insertions(+), 32 deletions(-)
>>>
>>> diff --git a/xen/common/sched_credit2.c b/xen/common/sched_credit2.c
>>> index 5bf5ebc..7265d5b 100644
>>> --- a/xen/common/sched_credit2.c
>>> +++ b/xen/common/sched_credit2.c
>>> @@ -588,41 +588,58 @@ 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;
>>>   
>>> -    list_for_each( iter, &rqd->svc )
>>> -    {
>>> -        struct csched_vcpu * svc = list_entry(iter, struct csched_vcpu,
>>> rqd_elem);
>>> -
>>> -        int start_credit;
>>> -
>>> -        BUG_ON( is_idle_vcpu(svc->vcpu) );
>>> -        BUG_ON( svc->rqd != rqd );
>>> -
>>> -        start_credit = svc->credit;
>>> -
>>> -        /* "Clip" credits to max carryover */
>>> -        if ( svc->credit > CSCHED_CARRYOVER_MAX )
>>> -            svc->credit = CSCHED_CARRYOVER_MAX;
>>> -        /* And add INIT */
>>> -        svc->credit += CSCHED_CREDIT_INIT;
>>> -        svc->start_time = now;
>>> -
>>> -        /* TRACE */ {
>>> -            struct {
>>> -                unsigned dom:16,vcpu:16;
>>> -                unsigned credit_start, credit_end;
>>> -            } d;
>>> -            d.dom = svc->vcpu->domain->domain_id;
>>> -            d.vcpu = svc->vcpu->vcpu_id;
>>> -            d.credit_start = start_credit;
>>> -            d.credit_end = svc->credit;
>>> -            trace_var(TRC_CSCHED2_CREDIT_RESET, 1,
>>> -                      sizeof(d),
>>> -                      (unsigned char *)&d);
>>> +    /*
>>> +     * 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.
>>> +     */
>>> +    while (snext->credit <= CSCHED_CREDIT_RESET ) {
>> So how long can this loop last? Can't you get away with a loop
>> altogether, considering that you only add CSCHED_CREDIT_INIT
>> inside the loop?
> 
> I'm not sure what you mean?
> 
> The point of doing the whole loop over is to make sure that everyone 
> gets the same number of CSCHED_CREDIT_INITs added.
> 
> While testing this I saw a couple of instances where it did the loop 20 
> times; the vast majority of the times it went around mutliple times it 
> only went twice.
> 
> I suppose we could do something like this:
> 
> if(snext->credit < -CSCHED_CREDIT_INIT) {
>    x = (-snext->credit)/CSCHED_CREDIT_INIT;
> } else {
>    x = 1;
> }
> 
> Then add (x * CSCHED_CREDIT_INIT) to each one.   Then in the common case 
> we're not doing any integer division, but in the uncommon case we have a 
> bounded algorithm.  Does that sound better?

Yes, it was something along those lines that I was hoping to get.
The division still seems better than perhaps quite a few iterations
of the loop.

>> Also, I hope there is some sort of guarantee that snext gets
>> updated by the loop in the first place.
> 
> The inner loop iterates over the list of all vcpus assigned to this 
> runqueue, whether or not they are actually on the current "queue" (i.e., 
> runnable and waiting for the cpu) or not.  snext was just taken from the 
> top the queue, so it should be on that list.
> 
> Unfortunately there's not a simple ASSERT() we can add to make sure that 
> snext is actually in that list; we can only ASSERT that the runqueue of 
> snext->cpu is this runqueue.  But if we're trying to check whether the 
> invariants are being upheld, there's no sense in assuming one of the 
> invariants we're trying to check.
> 
> But if we go the "multiplier" route this whole question disappears.

Indeed.

Jan

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