| Message ID | 1532669610-103892-1-git-send-email-xuyiping@hisilicon.com |
|---|---|
| State | New |
| Headers | show |
| Series | timers: fix offset calculation when the expires align with LVL_GRAN | expand |
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 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
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 > 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 > > . >
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 > > . >
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: > > 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
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. Thanks, tglx
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. > Thanks, > > tglx > > . >
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
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); }
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. Signed-off-by: Xu YiPing <xuyiping@hisilicon.com> --- kernel/time/timer.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) -- 2.7.4