Re: [PATCH 2/2] credit2: track residual from divisions done during accounting

[George Dunlap <george.dunlap@eu.citrix.com>]

On 27/02/13 12:48, Jan Beulich wrote:
>>>> On 27.02.13 at 13:31, George Dunlap <George.Dunlap@eu.citrix.com> wrote:
>> On Wed, Feb 27, 2013 at 11:35 AM, George Dunlap <George.Dunlap@eu.citrix.com
>>> wrote:
>>> On Wed, Feb 27, 2013 at 9:40 AM, Jan Beulich <JBeulich@suse.com> wrote:
>>>
>>>>>>> On 26.02.13 at 18:08, George Dunlap <george.dunlap@eu.citrix.com>
>>>> wrote:
>>>>> @@ -271,16 +272,24 @@ struct csched_dom {
>>>>>
>>>>>   /*
>>>>>    * Time-to-credit, credit-to-time.
>>>>> + *
>>>>> + * We keep track of the "residual" time to make sure that frequent
>>>> short
>>>>> + * schedules still get accounted for in the end.
>>>>> + *
>>>>>    * FIXME: Do pre-calculated division?
>>>>>    */
>>>>> -static s_time_t t2c(struct csched_runqueue_data *rqd, s_time_t time,
>>>> struct csched_vcpu *svc)
>>>>> +static void t2c_update(struct csched_runqueue_data *rqd, s_time_t time,
>>>>> +                          struct csched_vcpu *svc)
>>>>>   {
>>>>> -    return time * rqd->max_weight / svc->weight;
>>>>> +    uint64_t val = time * rqd->max_weight + svc->residual;
>>>>> +
>>>>> +    svc->residual = do_div(val, svc->weight);
>>>>> +    svc->credit -= val;
>>>>>   }
>>>>>
>>>>>   static s_time_t c2t(struct csched_runqueue_data *rqd, s_time_t credit,
>>>> struct csched_vcpu *svc)
>>>>>   {
>>>>> -    return credit * svc->weight / rqd->max_weight;
>>>>> +    return (credit * svc->weight) / rqd->max_weight;
>>>> So you dropped the subtraction of svc->residual here - why?
>>>>
>>>> And if indeed intended, the insertion of parentheses here could be
>>>> dropped?
>>>>
>>> Well for one I think the equation was wrong -- the residual is units of
>>> "time", so you should have subtracted the residual after dividing by
>>> max_weight.  (From a mathematical perspective, svc->weight /
>>> rqd->max_weight is the ratio that changes units of "credit" into units of
>>> "time; if we were using floating point ops I might put parentheses around
>>> that ratio to make it more clear that's what's going on.)
>>>
>>
>> Hmm, on further investigation, I think I've convinced myself that this
>> reasoning is wrong, and your original equation was correct.
>>
>> However, the difference will only ever end up to be one nanosecond, which
>> (if used) will be subtracted from the credit after the reset; so I think we
>> might as well do without the subtraction here.
> Oh, I didn't realize this would only be a nanosecond - my
> understanding was that it would be up to (but not including) a
> credit unit.

The "residual" will always be less than the svc->weight, which will 
always be less than or equal to rqd->max_weight.  So adding it in to the 
equation before dividing by rqd->max_weight can at most increase the 
result by 1.

Empiraclly, I've been playing around with values in a spreadsheet to 
make sure the logic was behaving as one would expect, and the difference 
between the calculation of c2t with and without the residual was never 
more than 1.

  -George