Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1517852 > unrolled thread

[PATCH] timers: Fix timer inaccuracy

Back to article view | Back to linux.kernel

Contents

  [PATCH] timers: Fix timer inaccuracy Joonwoo Park <joonwoop@codeaurora.org> - 2016-11-09 10:40 +0100
    Re: [PATCH] timers: Fix timer inaccuracy Thomas Gleixner <tglx@linutronix.de> - 2016-11-09 11:00 +0100
      Re: [PATCH] timers: Fix timer inaccuracy Joonwoo Park <joonwoop@codeaurora.org> - 2016-11-10 02:40 +0100
        Re: [PATCH] timers: Fix timer inaccuracy Thomas Gleixner <tglx@linutronix.de> - 2016-11-10 11:20 +0100

#1517852 — [PATCH] timers: Fix timer inaccuracy

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@linutronix.de>
Cc: John Stultz <john.stultz@linaro.org>
Cc: Eric Dumazet <edumazet@google.com>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: linux-kernel@vger.kernel.org
Signed-off-by: Joonwoo Park <joonwoop@codeaurora.org>
---
 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

[toc] | [next] | [standalone]

#1517872

On Wed, 9 Nov 2016, Joonwoo Park wrote:

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

That's simply wrong. We guarantee that the timer sleeps for at least a
jiffy. So in case of the first wheel we _must_ increment by one simply
because the next jiffie might be immanent and not doing so would expire the
timer early.

The wheel is not meant to be accurate at all and I really don't want an
extra conditional in that path just to make it accurate for some expiry
values. That's a completely pointless exercise.

Thanks,

	tglx

[toc] | [prev] | [next] | [standalone]

#1518631

On 11/09/2016 01:56 AM, Thomas Gleixner wrote:
> On Wed, 9 Nov 2016, Joonwoo Park wrote:
>
>> 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.
>
> That's simply wrong. We guarantee that the timer sleeps for at least a
> jiffy. So in case of the first wheel we _must_ increment by one simply
> because the next jiffie might be immanent and not doing so would expire the
> timer early.
>
> The wheel is not meant to be accurate at all and I really don't want an
> extra conditional in that path just to make it accurate for some expiry
> values. That's a completely pointless exercise.

I understand it's not meant to provide much of accuracy and also don't 
really care about accuracy of sporadic timer aim and fire.
What I'm worried about is case that relies on periodic timer with 
relatively short interval.
If you see bus scaling driver function devfreq_monitor() in 
drivers/devfreq/devfreq.c, it polls hardware every configured interval 
by using deferrable delayed work.  I'm not quite familiar with bus 
scaling so cc'ing linux-pm.

My guess is that ever since we have timer refactoring, above driver is 
polling every configured jiffy + 1 most of time.
When CONFIG_HZ_100=y and the interval is 1, polling will be happening 
every 20ms rather than configured 10ms which is 100% later than ideal.

If that kind of drivers want to run periodic polling at similar level of 
accuracy like pre v4.8, each drivers have to switch to hrtimer but there 
are problems apart from the fact there is no nicely written deferred 
processing mechanism like workqueue with hrtimer -
1) there is no deferrable hrtimer.
2) hrtimer has more overhead more than low res timer, especially hrtimer 
will fire interrupt for individual timer lists which will cause power 
impact.

It also makes sense to me that queued timer especially with long delay 
is tolerable to inaccuracy especially when most of them got canceled 
prior to its expiry time.
But by drivers which use timer as polling mechanism which never cancel 
it, IMHO this behaviour change could be a regression.

Thanks,
Joonwoo

>
> Thanks,
>
> 	tglx
>

[toc] | [prev] | [next] | [standalone]

#1518832

On Wed, 9 Nov 2016, Joonwoo Park wrote:
> On 11/09/2016 01:56 AM, Thomas Gleixner wrote:
> > That's simply wrong. We guarantee that the timer sleeps for at least a
> > jiffy. So in case of the first wheel we _must_ increment by one simply
> > because the next jiffie might be immanent and not doing so would expire the
> > timer early.
> > 
> > The wheel is not meant to be accurate at all and I really don't want an
> > extra conditional in that path just to make it accurate for some expiry
> > values. That's a completely pointless exercise.
> 
> I understand it's not meant to provide much of accuracy and also don't really
> care about accuracy of sporadic timer aim and fire.
> What I'm worried about is case that relies on periodic timer with relatively
> short interval.
> If you see bus scaling driver function devfreq_monitor() in
> drivers/devfreq/devfreq.c, it polls hardware every configured interval by
> using deferrable delayed work.  I'm not quite familiar with bus scaling so
> cc'ing linux-pm.

So you are not familiar with that and therefor use it as an argument for a
potential problem. Pretty scientific approach.

You already mentioned the keyword: DEFERRABLE, which is designed to be
inaccurate.
 
> My guess is that ever since we have timer refactoring, above driver is polling
> every configured jiffy + 1 most of time.

Sure, guess work is the right approach here.

> When CONFIG_HZ_100=y and the interval is 1, polling will be happening every
> 20ms rather than configured 10ms which is 100% later than ideal.

The wheel guarantees that the timer sleeps at least 1 jiffie and this can
only be done by adding one jiffie simply because:

CPU 0	   	CPU 1
		mod_timer(jiffies + 1)
timer irq
jiffies++	queue_timer
		timer_irq
		expire timer

So this timer expired exactly a few micro seconds after arming and therefor
violates the guarantee of firing not before the specified interval.

So depending on when you arm the timer the expiry is going to be:

   1 jiffie <= expiry <= 2 jiffies

If you disable high resolution timers then your user space program using
nanosleep will have exactly the same behaviour.

And this is the only sane behaviour you can expect from timers: To not
expire early.

Every user must cope with late expiry anyway as there is no guarantee that
the task is scheduled right away. Neither is there a guarantee that the
softirq (it might be deferred to ksoftirqd) invokes the callback on time.

The timer wheel is optimized for enqueue/dequeue speed and implicit
batching. Making it artificial accurate for one particular case is just
adding pointless overhead and aside of that it's going to violate the valid
assumption that a 1 jiffie sleep is going to sleep at least 1 jiffie.

> If that kind of drivers want to run periodic polling at similar level of
> accuracy like pre v4.8, each drivers have to switch to hrtimer but there are
> problems apart from the fact there is no nicely written deferred processing
> mechanism like workqueue with hrtimer -
> 1) there is no deferrable hrtimer.
> 2) hrtimer has more overhead more than low res timer, especially hrtimer will
> fire interrupt for individual timer lists which will cause power impact.

Deferrable timers shouldn't have been invented in the first place and yes,
they are not going to happen on hrtimers, quite the contrary, I'm working
on eliminating them completely.
 
> It also makes sense to me that queued timer especially with long delay is
> tolerable to inaccuracy especially when most of them got canceled prior to its
> expiry time.
> But by drivers which use timer as polling mechanism which never cancel it,
> IMHO this behaviour change could be a regression.

When you can come up with a real regression caused by the rework and not
just some handwaving theories then we can revisit that, but until then it's
going to stay as is.

Thanks,

	tglx

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web