[PATCH] timers: Fix timer inaccuracy

[Joonwoo Park]

When a new timer list enqueued into the time wheel, array index
for the given expiry time is:

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

The granularity of the expiry time level is being added to the index
in order to fire the timer after its expiry time for the case when
the timer cannot fire at the exact time because of each level's
granularity.  However current index calculation also increases index
of timer list even if the timer can fire at exact time.  Consequently
timers which can fire at exact time including all in the first level
of bucket fire with one jiffy delay at present.

Fix such inaccuracy by adding granularity of expiry time level only
when a given timer cannot fire at exact time.

With CONFIG_HZ_100=y

Before:
  225.768008: timer_start: timer=ffffffffa00042c0 function=timer_func [timer] expires=4294959868 [timeout=2] flags=0x0e800000
  <snip>
  225.797961: timer_expire_entry: timer=ffffffffa00042c0 function=timer_func [timer] now=4294959869

After:
   54.424805: timer_start: timer=ffffffffa00042c0 function=timer_func [timer] expires=4294942730 [timeout=2] flags=0x10400000
   <snip>
   54.444764: timer_expire_entry: timer=ffffffffa00042c0 function=timer_func [timer] now=4294942730

Fixes: 500462a9de65 "timers: Switch to a non-cascading wheel"
Cc: Thomas Gleixner <tglx@xxxxxxxxxxxxx>
Cc: John Stultz <john.stultz@xxxxxxxxxx>
Cc: Eric Dumazet <edumazet@xxxxxxxxxx>
Cc: Frederic Weisbecker <fweisbec@xxxxxxxxx>
Cc: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
Cc: Paul E. McKenney <paulmck@xxxxxxxxxxxxxxxxxx>
Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Cc: linux-kernel@xxxxxxxxxxxxxxx
Signed-off-by: Joonwoo Park <joonwoop@xxxxxxxxxxxxxx>
---
 kernel/time/timer.c | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index c611c47..f6ad4e9 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -467,17 +467,29 @@ 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);
+	if (expires & ~(UINT_MAX << LVL_SHIFT(lvl)))
+		expires = (expires + LVL_GRAN(lvl)) >> LVL_SHIFT(lvl);
+	else
+		expires = expires >> LVL_SHIFT(lvl);
 	return LVL_OFFS(lvl) + (expires & LVL_MASK);
 }
 
+static inline unsigned calc_index_min_granularity(unsigned expires)
+{
+	return LVL_OFFS(0) + ((expires >> LVL_SHIFT(0)) & LVL_MASK);
+}
+
 static int calc_wheel_index(unsigned long expires, unsigned long clk)
 {
 	unsigned long delta = expires - clk;
 	unsigned int idx;
 
 	if (delta < LVL_START(1)) {
-		idx = calc_index(expires, 0);
+		/*
+		 * calc_index(expires, 0) should still work but we can
+		 * optimize as LVL_SHIFT(0) is always 0.
+		 */
+		idx = calc_index_min_granularity(expires);
 	} else if (delta < LVL_START(2)) {
 		idx = calc_index(expires, 1);
 	} else if (delta < LVL_START(3)) {
-- 
2.9.3