[RFC] exponential update_wall_time

[RFC] exponential update_wall_time

[john stultz]

Hey Roman,
	Just wanted to run this by you for comment. Ingo was finding issues w/
update_wall_clock looping for too long when using dynticks. I also think
this will avoid the bad clocksource caused hangs that have been
occasionally reported (instead of looping forever, time will just
accumulate oddly), which will help point to the issue.

Anyway, just wanted to get your thoughts before I send it to Andrew for
more testing.

thanks
-john

Accumulate time in update_wall_time exponentially. 
This avoids long running loops seen with the dynticks patch
as well as the problematic hang" seen on systems with broken 
clocksources.

This applies on top of 2.6.18-mm1

Signed-off-by: John Stultz <johnstul@us.ibm.com>

 kernel/timer.c |   28 ++++++++++++++++++++--------
 1 file changed, 20 insertions(+), 8 deletions(-)

Index: linux-2.6.18/kernel/timer.c
===================================================================
--- linux-2.6.18.orig/kernel/timer.c	2006-09-20 16:17:54.000000000 +0200
+++ linux-2.6.18/kernel/timer.c	2006-09-20 16:17:59.000000000 +0200
@@ -902,6 +902,7 @@ static void clocksource_adjust(struct cl
 static void update_wall_time(void)
 {
 	cycle_t offset;
+	int shift = 0;
 
 	/* Make sure we're fully resumed: */
 	if (unlikely(timekeeping_suspended))
@@ -914,28 +915,39 @@ static void update_wall_time(void)
 #endif
 	clock->xtime_nsec += (s64)xtime.tv_nsec << clock->shift;
 
+	while (offset > clock->cycle_interval << (shift + 1))
+		shift++;
+
 	/* normally this loop will run just once, however in the
 	 * case of lost or late ticks, it will accumulate correctly.
 	 */
 	while (offset >= clock->cycle_interval) {
+		if (offset < (clock->cycle_interval << shift)) {
+			shift--;
+			continue;
+		}
+
 		/* accumulate one interval */
-		clock->xtime_nsec += clock->xtime_interval;
-		clock->cycle_last += clock->cycle_interval;
-		offset -= clock->cycle_interval;
+		clock->xtime_nsec += clock->xtime_interval << shift;
+		clock->cycle_last += clock->cycle_interval << shift;
+		offset -= clock->cycle_interval << shift;
 
-		if (clock->xtime_nsec >= (u64)NSEC_PER_SEC << clock->shift) {
+		while (clock->xtime_nsec >= (u64)NSEC_PER_SEC << clock->shift) {
 			clock->xtime_nsec -= (u64)NSEC_PER_SEC << clock->shift;
 			xtime.tv_sec++;
 			second_overflow();
 		}
 
 		/* interpolator bits */
-		time_interpolator_update(clock->xtime_interval
-						>> clock->shift);
+		time_interpolator_update((clock->xtime_interval
+						>> clock->shift)<<shift);
 
 		/* accumulate error between NTP and clock interval */
-		clock->error += current_tick_length();
-		clock->error -= clock->xtime_interval << (TICK_LENGTH_SHIFT - clock->shift);
+		clock->error += current_tick_length() << shift;
+		clock->error -= (clock->xtime_interval
+			<< (TICK_LENGTH_SHIFT - clock->shift))<<shift;
+
+		shift--;
 	}
 
 	/* correct the clock when NTP error is too big */

Re: [RFC] exponential update_wall_time

[Ingo Molnar]

* john stultz <johnstul@us.ibm.com> wrote:

> Accumulate time in update_wall_time exponentially. This avoids long 
> running loops seen with the dynticks patch as well as the problematic 
> hang" seen on systems with broken clocksources.
> 
> This applies on top of 2.6.18-mm1
> 
> Signed-off-by: John Stultz <johnstul@us.ibm.com>

Acked-by: Ingo Molnar <mingo@elte.hu>

works fine and is included in 2.6.18-rt too.

	Ingo

Re: [RFC] exponential update_wall_time

[Thomas Gleixner]

On Wed, 2006-09-27 at 22:08 +0200, Ingo Molnar wrote:
> * john stultz <johnstul@us.ibm.com> wrote:
> 
> > Accumulate time in update_wall_time exponentially. This avoids long 
> > running loops seen with the dynticks patch as well as the problematic 
> > hang" seen on systems with broken clocksources.
> > 
> > This applies on top of 2.6.18-mm1
> > 
> > Signed-off-by: John Stultz <johnstul@us.ibm.com>
> 
> Acked-by: Ingo Molnar <mingo@elte.hu>

Acked-by: Thomas Gleixner <tglx@linutronix.de>

> works fine and is included in 2.6.18-rt too.

Same here.

	tglx

Re: [RFC] exponential update_wall_time

[Andrew Morton]

On Wed, 27 Sep 2006 12:35:33 -0700
john stultz <johnstul@us.ibm.com> wrote:

> +	while (offset > clock->cycle_interval << (shift + 1))
> +		shift++;

hurts my brain.  I have a vague feeling that this can be done with
something like ffz(~(offset/clock->cycle_interval))+epsilon, but that hurts
my brain too.

Re: [RFC] exponential update_wall_time

[Roman Zippel]

Hi,

On Wed, 27 Sep 2006, john stultz wrote:

> Accumulate time in update_wall_time exponentially. 
> This avoids long running loops seen with the dynticks patch
> as well as the problematic hang" seen on systems with broken 
> clocksources.

This is the wrong approach, second_overflow() should be called every HZ
increment steps and your patch breaks this.
There are other approaches oo accommodate dyntick. 
1. You could make HZ in ntp_update_frequency() dynamic and thus reduce the 
frequency with which update_wall_time() needs to be called (Note that 
other clock variables like cycle_interval have to be adjusted as well). 
2. If dynticks stops the timer interrupt for a long time, it could 
precalculate a few things, e.g. it could complete the second and then 
advance the time in full seconds.

bye, Roman

Re: [RFC] exponential update_wall_time

[john stultz]

On Thu, 2006-09-28 at 01:04 +0200, Roman Zippel wrote:
> On Wed, 27 Sep 2006, john stultz wrote:
> 
> > Accumulate time in update_wall_time exponentially. 
> > This avoids long running loops seen with the dynticks patch
> > as well as the problematic hang" seen on systems with broken 
> > clocksources.
> 
> This is the wrong approach, second_overflow() should be called every HZ
> increment steps and your patch breaks this.

First, forgive me, since I've got a bit of a head cold, so I'm even
slower then usual. I just don't see how this patch changes the behavior.
Every second we will call second_overflow. But in the case where we
skipped 100 ticks, we don't loop 100 times. Could you explain this a bit
more?


> There are other approaches oo accommodate dyntick. 
> 1. You could make HZ in ntp_update_frequency() dynamic and thus reduce the 
> frequency with which update_wall_time() needs to be called (Note that 
> other clock variables like cycle_interval have to be adjusted as well). 

I'm not sure how this is functionally different from what this patch
does.


> 2. If dynticks stops the timer interrupt for a long time, it could 
> precalculate a few things, e.g. it could complete the second and then 
> advance the time in full seconds.

Not following this one at all.

Again, sorry for being so thick.
-john

Re: [RFC] exponential update_wall_time

[john stultz]

On Wed, 2006-09-27 at 15:05 -0700, Andrew Morton wrote:
> On Wed, 27 Sep 2006 12:35:33 -0700
> john stultz <johnstul@us.ibm.com> wrote:
> 
> > +	while (offset > clock->cycle_interval << (shift + 1))
> > +		shift++;
> 
> hurts my brain.

Yea. Its not the most obvious patch, but the complexity is pretty
isolated.

> I have a vague feeling that this can be done with
> something like ffz(~(offset/clock->cycle_interval))+epsilon, but that hurts
> my brain too.

Agreed. I don't want to obfuscate this code much more. In my opinion,
the loop is tightly bounded and not expensive enough to try to optimize.

thanks
-john

Re: [RFC] exponential update_wall_time

[Roman Zippel]

Hi,

On Wed, 27 Sep 2006, john stultz wrote:

> > This is the wrong approach, second_overflow() should be called every HZ
> > increment steps and your patch breaks this.
> 
> First, forgive me, since I've got a bit of a head cold, so I'm even
> slower then usual. I just don't see how this patch changes the behavior.
> Every second we will call second_overflow. But in the case where we
> skipped 100 ticks, we don't loop 100 times. Could you explain this a bit
> more?

second_overflow() changes the tick length, but the new tick length is now 
applied to varying number of ticks with your patch, which is bad for 
correct timekeeping.

> > There are other approaches oo accommodate dyntick. 
> > 1. You could make HZ in ntp_update_frequency() dynamic and thus reduce the 
> > frequency with which update_wall_time() needs to be called (Note that 
> > other clock variables like cycle_interval have to be adjusted as well). 
> 
> I'm not sure how this is functionally different from what this patch
> does.
> 
> 
> > 2. If dynticks stops the timer interrupt for a long time, it could 
> > precalculate a few things, e.g. it could complete the second and then 
> > advance the time in full seconds.
> 
> Not following this one at all.

You have to keep in mind that ntp time is basically advanced in 1 second 
steps (or HZ ticks or freq cycles to be precise) and you have to keep that 
property. You can slice that second however you like, but it still has to 
add up to 1 second. Right now we slice it into HZ steps, but this can be 
rather easily changed now.

bye, Roman

Re: [RFC] exponential update_wall_time

[john stultz]

On Thu, 2006-09-28 at 01:40 +0200, Roman Zippel wrote:
> Hi,
> 
> On Wed, 27 Sep 2006, john stultz wrote:
> 
> > > This is the wrong approach, second_overflow() should be called every HZ
> > > increment steps and your patch breaks this.
> > 
> > First, forgive me, since I've got a bit of a head cold, so I'm even
> > slower then usual. I just don't see how this patch changes the behavior.
> > Every second we will call second_overflow. But in the case where we
> > skipped 100 ticks, we don't loop 100 times. Could you explain this a bit
> > more?
> 
> second_overflow() changes the tick length, but the new tick length is now 
> applied to varying number of ticks with your patch, which is bad for 
> correct timekeeping.

Hmm.. Ok, I can see that. Thanks for the clarification.

> > > There are other approaches oo accommodate dyntick. 
> > > 1. You could make HZ in ntp_update_frequency() dynamic and thus reduce the 
> > > frequency with which update_wall_time() needs to be called (Note that 
> > > other clock variables like cycle_interval have to be adjusted as well). 
> > 
> > I'm not sure how this is functionally different from what this patch
> > does.
> > 
> > 
> > > 2. If dynticks stops the timer interrupt for a long time, it could 
> > > precalculate a few things, e.g. it could complete the second and then 
> > > advance the time in full seconds.
> > 
> > Not following this one at all.
> 
> You have to keep in mind that ntp time is basically advanced in 1 second 
> steps (or HZ ticks or freq cycles to be precise) and you have to keep that 
> property. You can slice that second however you like, but it still has to 
> add up to 1 second. Right now we slice it into HZ steps, but this can be 
> rather easily changed now.

Right off, it seems it would then make sense to make the ntp "ticks" one
second in length. And set the interval values accordingly.

However, there might be clocksources that are incapable of running
freely for a full second w/o overflowing. In that case we would need to
set the interval values and the ntp tick length accordingly. It seems we
need some sort of interface to ntp to define that base tick length.
Would that be ok by you?

thanks
-john

Re: [RFC] exponential update_wall_time

[Roman Zippel]

Hi,

On Wed, 27 Sep 2006, john stultz wrote:

> > You have to keep in mind that ntp time is basically advanced in 1 second 
> > steps (or HZ ticks or freq cycles to be precise) and you have to keep that 
> > property. You can slice that second however you like, but it still has to 
> > add up to 1 second. Right now we slice it into HZ steps, but this can be 
> > rather easily changed now.
> 
> Right off, it seems it would then make sense to make the ntp "ticks" one
> second in length. And set the interval values accordingly.
> 
> However, there might be clocksources that are incapable of running
> freely for a full second w/o overflowing. In that case we would need to
> set the interval values and the ntp tick length accordingly. It seems we
> need some sort of interface to ntp to define that base tick length.
> Would that be ok by you?

I don't see how you want to do this without some rather complex 
calculations. I doubt this will make anything easier.

bye, Roman

Re: [RFC] exponential update_wall_time

[Ingo Molnar]

* Roman Zippel <zippel@linux-m68k.org> wrote:

> > > add up to 1 second. Right now we slice it into HZ steps, but this 
> > > can be rather easily changed now.
> > 
> > Right off, it seems it would then make sense to make the ntp "ticks" 
> > one second in length. And set the interval values accordingly.
> > 
> > However, there might be clocksources that are incapable of running 
> > freely for a full second w/o overflowing. In that case we would need 
> > to set the interval values and the ntp tick length accordingly. It 
> > seems we need some sort of interface to ntp to define that base tick 
> > length. Would that be ok by you?
> 
> I don't see how you want to do this without some rather complex 
> calculations. I doubt this will make anything easier.

lets figure out a way to solve this in some manner - the loop of 
thousands of function calls on dynticks didnt look too well. Millions of 
kids will be grateful for it :-)

	Ingo