Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Subject: Re: [PATCH] timers: fix offset calculation when the expires align
 with LVL_GRAN
To:     Thomas Gleixner <tglx@linutronix.de>
CC:     <john.stultz@linaro.org>, <sboyd@kernel.org>,
        <linux-kernel@vger.kernel.org>
References: <1532669610-103892-1-git-send-email-xuyiping@hisilicon.com>
 <alpine.DEB.2.21.1807301234310.2518@nanos.tec.linutronix.de>
From:   Xu YiPing <xuyiping@hisilicon.com>
Message-ID: <c68d9944-1fcc-dcd5-1e3d-07f979323b8c@hisilicon.com>
Date:   Tue, 31 Jul 2018 21:45:11 +0800
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:52.0) Gecko/20100101
 Thunderbird/52.6.0
MIME-Version: 1.0
In-Reply-To: <alpine.DEB.2.21.1807301234310.2518@nanos.tec.linutronix.de>
Content-Type: text/plain; charset="utf-8"
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk


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@hisilicon.com>
>> ---
>>  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
> 
> .
>