[PATCH] timers: Reconcile the code and the comment for the 250HZ case

[PATCH] timers: Reconcile the code and the comment for the 250HZ case

[Zhihui Zhang]

Adjust the time start of each level to match the comments. Note that
LVL_START(n) is never used for n = 0 case.  Also, each level (except
level 0) has more than enough room to accommodate all its timers.

Signed-off-by: Zhihui Zhang <zzhsuny@gmail.com>
---
 kernel/time/timer.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index ec33a69..268d5ae 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -132,7 +132,7 @@ EXPORT_SYMBOL(jiffies_64);
  *  5	 320    131072 ms (~2m)    1048576 ms -    8388607 ms (~17m - ~2h)
  *  6	 384   1048576 ms (~17m)   8388608 ms -   67108863 ms (~2h - ~18h)
  *  7	 448   8388608 ms (~2h)   67108864 ms -  536870911 ms (~18h - ~6d)
- *  8    512  67108864 ms (~18h) 536870912 ms - 4294967288 ms (~6d - ~49d)
+ *  8    512  67108864 ms (~18h) 536870912 ms - 4294967295 ms (~6d - ~49d)
  *
  * HZ  100
  * Level Offset  Granularity            Range
@@ -157,7 +157,7 @@ EXPORT_SYMBOL(jiffies_64);
  * The time start value for each level to select the bucket at enqueue
  * time.
  */
-#define LVL_START(n)	((LVL_SIZE - 1) << (((n) - 1) * LVL_CLK_SHIFT))
+#define LVL_START(n)	(LVL_SIZE << (((n) - 1) * LVL_CLK_SHIFT))
 
 /* Size of each clock level */
 #define LVL_BITS	6
-- 
2.7.4

Re: [PATCH] timers: Reconcile the code and the comment for the 250HZ case

[John Stultz]

On Mon, Jan 2, 2017 at 1:14 PM, Zhihui Zhang <zzhsuny@gmail.com> wrote:
> Adjust the time start of each level to match the comments. Note that
> LVL_START(n) is never used for n = 0 case.  Also, each level (except
> level 0) has more than enough room to accommodate all its timers.

So instead of just covering what your patch does, can you explain in
some detail why this patch is useful? What net effect does it bring?
What sort of bugs would it solve?

thanks
-john

Re: [PATCH] timers: Reconcile the code and the comment for the 250HZ case

[Zhihui Zhang]

Sure, I believe that comments should always match the code. In this
case, using either LVL_SIZE - 1 or LVL_SIZE is fine based on my
understanding about 20 days ago. But I could be wrong and miss some
subtle details. Anyway, my point is about readability.

thanks,

On Fri, Jan 20, 2017 at 5:41 PM, John Stultz <john.stultz@linaro.org> wrote:
> On Mon, Jan 2, 2017 at 1:14 PM, Zhihui Zhang <zzhsuny@gmail.com> wrote:
>> Adjust the time start of each level to match the comments. Note that
>> LVL_START(n) is never used for n = 0 case.  Also, each level (except
>> level 0) has more than enough room to accommodate all its timers.
>
> So instead of just covering what your patch does, can you explain in
> some detail why this patch is useful? What net effect does it bring?
> What sort of bugs would it solve?
>
> thanks
> -john

Re: [PATCH] timers: Reconcile the code and the comment for the 250HZ case

[Thomas Gleixner]

On Sat, 21 Jan 2017, Zhihui Zhang wrote:

> Sure, I believe that comments should always match the code. In this

That's fine.

> case, using either LVL_SIZE - 1 or LVL_SIZE is fine based on my
> understanding about 20 days ago. But I could be wrong and miss some
> subtle details. Anyway, my point is about readability.

Well, readability is one thing, but correctness is more important, right?

Let's assume we have 4 buckets per level and base->clk is 0. So Level 0
has the following expiry times:

Bucket 0:   base->clk + 0
Bucket 1:   base->clk + 1
Bucket 2:   base->clk + 2
Bucket 3:   base->clk + 3

So we can accomodate 4 timers here, but there is a nifty detail. We
guarantee that expiries are not short, so a timer armed for base->clk
will expire at base->clk + 1.

The reason for this is that we have no distinction between absolute and
relative timeouts. But for relative timeouts we have to guarantee that the
timeout does not expire before the number of jiffies has elapsed.

Now a timer armed with 1 jiffie relativ to now (jiffies) cannot be queued
to bucket 0 because jiffies can be incremented immediately after queueing
the timer which would expire it early. So it's queued to bucket 1 and
that's why we need to have LVL_SIZE - 1 and not LVL_SIZE. See also
calc_index().

Your change completely breaks the wheel. Let's assume the above and a
timer expiring at base->clk + 3.

With your change the timer would fall into Level 0. So no calc_index()
does:

	expires = (expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl);
	return LVL_OFFS(lvl) + (expires & LVL_MASK);

Let's substitute that for the expires = base->clk + 3 case:

        expires = (base->clk + 3 + 1) >> 0;

--->	expires = 4;

	return 0 + (4 & 0x03);

--->	index = 0

So the timer gets queued into bucket 0 and expires 4 jiffies too early.

So using either LVL_SIZE - 1 or LVL_SIZE is _NOT_ fine.

Thanks,

	tglx





	

Re: [PATCH] timers: Reconcile the code and the comment for the 250HZ case

[Zhihui Zhang]

Ah, I see your point. Thanks for the detail explanation.

-Zhihui

On Mon, Jan 23, 2017 at 6:10 AM, Thomas Gleixner <tglx@linutronix.de> wrote:
> On Sat, 21 Jan 2017, Zhihui Zhang wrote:
>
>> Sure, I believe that comments should always match the code. In this
>
> That's fine.
>
>> case, using either LVL_SIZE - 1 or LVL_SIZE is fine based on my
>> understanding about 20 days ago. But I could be wrong and miss some
>> subtle details. Anyway, my point is about readability.
>
> Well, readability is one thing, but correctness is more important, right?
>
> Let's assume we have 4 buckets per level and base->clk is 0. So Level 0
> has the following expiry times:
>
> Bucket 0:   base->clk + 0
> Bucket 1:   base->clk + 1
> Bucket 2:   base->clk + 2
> Bucket 3:   base->clk + 3
>
> So we can accomodate 4 timers here, but there is a nifty detail. We
> guarantee that expiries are not short, so a timer armed for base->clk
> will expire at base->clk + 1.
>
> The reason for this is that we have no distinction between absolute and
> relative timeouts. But for relative timeouts we have to guarantee that the
> timeout does not expire before the number of jiffies has elapsed.
>
> Now a timer armed with 1 jiffie relativ to now (jiffies) cannot be queued
> to bucket 0 because jiffies can be incremented immediately after queueing
> the timer which would expire it early. So it's queued to bucket 1 and
> that's why we need to have LVL_SIZE - 1 and not LVL_SIZE. See also
> calc_index().
>
> Your change completely breaks the wheel. Let's assume the above and a
> timer expiring at base->clk + 3.
>
> With your change the timer would fall into Level 0. So no calc_index()
> does:
>
>         expires = (expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl);
>         return LVL_OFFS(lvl) + (expires & LVL_MASK);
>
> Let's substitute that for the expires = base->clk + 3 case:
>
>         expires = (base->clk + 3 + 1) >> 0;
>
> --->    expires = 4;
>
>         return 0 + (4 & 0x03);
>
> --->    index = 0
>
> So the timer gets queued into bucket 0 and expires 4 jiffies too early.
>
> So using either LVL_SIZE - 1 or LVL_SIZE is _NOT_ fine.
>
> Thanks,
>
>         tglx
>
>
>
>
>
>