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] [day] [month] [year] [list]

Message-ID: <alpine.DEB.2.21.1808010855500.1713@nanos.tec.linutronix.de>
Date:   Wed, 1 Aug 2018 09:10:56 +0200 (CEST)
From:   Thomas Gleixner <tglx@...utronix.de>
To:     Xu YiPing <xuyiping@...ilicon.com>
cc:     John Stultz <john.stultz@...aro.org>, sboyd@...nel.org,
        LKML <linux-kernel@...r.kernel.org>, anna-maria@...utronix.de
Subject: Re: [PATCH] timers: fix offset calculation when the expires align
 with LVL_GRAN

On Wed, 1 Aug 2018, Xu YiPing wrote:
> On 2018/7/31 22:34, Thomas Gleixner wrote:
> > 
> > 
> > On Tue, 31 Jul 2018, Thomas Gleixner wrote:
> > 
> >> On Tue, 31 Jul 2018, Xu YiPing wrote:
> >>> On 2018/7/30 19:03, Thomas Gleixner wrote:
> >>>>
> >>>> __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 ?
> >>
> >> Indeed. You're right. Math is hard... So the index would be 1 and still not
> >> fulfil the below:
> > 
> > Hmm, crap. Let me think about it some more. 34C is way too hot to think.
> > 
> 
> 	when the expire is aligned with LVL_GRAN(x), it could be triggered at expire,
> no need to wait another LVL_GRAN(x).
> 
> 	just a little improvement, useful when expire is small.

The expire early problem still persists:

schedule_timeout(x)
   expires = jiffies + x;
   mod_timer(timer, expires);

This will return _BEFORE_ X jiffies have elapsed in 99% of the cases, so it's
not a little improvement, it's a big regression.

Again for schedule_timeout(1):

   |-------------------|-------------------|--------------------|
  tick               tick                tick			
 jiffies           jiffies + 1        jiffies + 2

   |                   |
   |  Any timer armed  |                   ^
   |  here must be     |                   |
   |  queued here -------------------------|
                       |                   |
                       |  Any timer armed  |                   ^
                       |  here must be     |                   |
                       |  queued here -------------------------|

The only case where your change would be correct is if _all_ timers are
armed exactly at the jiffies boundary. Can you guarantee that? Not at all.

And even hrtiemrs suffer from this issue when high resolution mode is
disabled because then they are expired on the tick boundary as well and if
the expiry time is past the current time at the tick boundary then the
timer will be expired one tick later.

It's a fundamental property of timers which are driven by a periodic tick
and you can argue in circles it wont change.

Thanks,

	tglx