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: <alpine.DEB.2.21.1807301234310.2518@nanos.tec.linutronix.de>
Date:   Mon, 30 Jul 2018 13:03:16 +0200 (CEST)
From:   Thomas Gleixner <tglx@...utronix.de>
To:     Xu YiPing <xuyiping@...ilicon.com>
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 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.

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