Re: [PATCH] timers: fix offset calculation when the expires align with LVL_GRAN

[Xu YiPing]

On 2018/7/30 19:03, Thomas Gleixner wrote:
> On Fri, 27 Jul 2018, Xu YiPing wrote:
> 
>> when the expires of timer is align with LVL_GRAN(n), it will be trigged
>> in 'expires + LVL_GRAN(n)'.
>>
>> Some drivers like power runtime use the timer to start a power down
>> of device, it could saves power if the timer is triggerd in time,
>> especially when LEVEL=0 with low expires.
> 
>>From the above I have no idea what you are trying to 'fix', but see below.
> 
>> Signed-off-by: Xu YiPing <xuyiping@xxxxxxxxxxxxx>
>> ---
>>  kernel/time/timer.c | 3 ++-
>>  1 file changed, 2 insertions(+), 1 deletion(-)
>>
>> diff --git a/kernel/time/timer.c b/kernel/time/timer.c
>> index cc2d23e..76655e2 100644
>> --- a/kernel/time/timer.c
>> +++ b/kernel/time/timer.c
>> @@ -487,7 +487,8 @@ static inline void timer_set_idx(struct timer_list *timer, unsigned int idx)
>>   */
>>  static inline unsigned calc_index(unsigned expires, unsigned lvl)
>>  {
>> -	expires = (expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl);
>> +	expires = (expires + LVL_GRAN(lvl) - 1) >> LVL_SHIFT(lvl);
>> +
>>  	return LVL_OFFS(lvl) + (expires & LVL_MASK);
> 
> This is fundamentally wrong.
> 
> Assume the following scenario:
> 
>     base->clk = 1;
>     timer->expires = 1;
> 
> __internal_add_timer(base, timer)
> {  
>    idx = calc_wheel_index(timer->expires, base->clk)
>        {
>            delta = expires - clk;
> 
>            if (delta < LVL_START(1))
>                idx = calc_index(expires, 0)
>                     {
>                         expires = (expires + LVL_GRAN(0) - 1) >> LVL_SHIFT(0);
> 			return LVL_OFFS(0) + (expires & LVL_MASK);
> 
> Now lets use real numbers:
> 
> __internal_add_timer(base, timer)
> {  
>    idx = calc_wheel_index(1, 1)
>        {
>            delta = 1 - 1;	<-   0
> 
>            if (0 < LVL_START(1))
>                idx = calc_index(1, 0)
>                     {
>                         expires = (1 + LVL_GRAN(0) - 1) >> LVL_SHIFT(0);
> 			----> expires = 0
			
			LVL_GRAN(0) = 1 and LVL_SHIFT(0) = 0
			
			after the calculation, expires = 1 ?

> 			return LVL_OFFS(0) + (0 & LVL_MASK);
> 			----> 0
> 
> So the returned index is 0, which means that the timer will expire in
> LVL_SIZE - 1 == 63 ticks.
> 
> The above example is the worst case, but you broke other assumptions as
> well. The timer wheel guarantees that a timer armed with:
> 
>       mod_timer(timer, jiffies + 1)
> 
> will not fire before aty least one jiffy has elapsed. Let's look at the
> time line:
> 
>    |-------------------|-------------------|----------------|
>   tick               tick                tick
>  jiffies	   jiffies + 1        jiffies + 2
> 
>    |                   |
>    |  Any timer armed  |                   ^
>    |  here must be     |                   |
>    |  queued here -------------------------|
> 
> in order to guarantee that. Timer wheel timers are not accurate and never
> can be.
> 
> Thanks,
> 
> 	tglx
> 
> .
>