[PATCH] timers: fix offset calculation when the expires align with LVL_GRAN

[PATCH] timers: fix offset calculation when the expires align with LVL_GRAN

[Xu YiPing]

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(-)

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);
 }
 
-- 
2.7.4

Re: [PATCH] timers: fix offset calculation when the expires align with LVL_GRAN

[Thomas Gleixner]

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

Re: [PATCH] timers: fix offset calculation when the expires align with LVL_GRAN

[Xu YiPing]

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
> 
> .
> 

Re: [PATCH] timers: fix offset calculation when the expires align with LVL_GRAN

[Xu YiPing]

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
> 
> .
> 

Re: [PATCH] timers: fix offset calculation when the expires align with LVL_GRAN

[Thomas Gleixner]

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

Re: [PATCH] timers: fix offset calculation when the expires align with LVL_GRAN

[Thomas Gleixner]

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

Re: [PATCH] timers: fix offset calculation when the expires align with LVL_GRAN

[Xu YiPing]

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
> 
> .
> 

Re: [PATCH] timers: fix offset calculation when the expires align with LVL_GRAN

[Thomas Gleixner]

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