linux-kernel - Re: [PATCH] timers: fix offset calculation when the expires align with LVL

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <4738717a-0ca7-8fc4-567d-8bd669f9eaf6@hisilicon.com>
Date:   Tue, 31 Jul 2018 20:37:26 +0800
From:   Xu YiPing <xuyiping@...ilicon.com>
To:     Thomas Gleixner <tglx@...utronix.de>
CC:     <john.stultz@...aro.org>, <sboyd@...nel.org>,
        <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] timers: fix offset calculation when the expires align
 with LVL_GRAN



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@...ilicon.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
> 			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.
> 
	yes, i missed this case.

> 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.
> 
	understand, thanks.

> Thanks,
> 
> 	tglx
> 
> .
>