Skip to contentSkip to conversation

timers: Reconcile the code and the comment for the 250HZ case

PATCH In review Zhihui Zhang 3 participants 5 messages Jan 2, 2017 – Jan 24, 2017 High-resolution timers, timer wheel, clockevents

lore
Share & tools
lore

Zhihui Zhang

author
#0 lore raw

PATCH 1/1 timers: Reconcile the code and the comment for the 250HZ case

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 <[email protected]>
---
 kernel/time/timer.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
kernel/time/timer.c +2 -2
index ec33a69..268d5ae 100644
@@ -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
Signature · 1 line
2.7.4
#1 lore raw
Quoted 3 lines · 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.

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

author
#2 lore raw

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,

Quoted 11 lines · John Stultz
Quoted 3 lines · 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.

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

#3 lore raw
Quoted 1 line · Zhihui Zhang

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

That's fine.

Quoted 3 lines

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

author
#4 lore raw

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

-Zhihui

Quoted 66 lines · Thomas Gleixner
Quoted 1 line · Zhihui Zhang

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

That's fine.

Quoted 3 lines

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