Skip to contentSkip to conversation

exponential update_wall_time

RFC In review john stultz 5 participants 11 messages Sep 27, 2006 – Sep 28, 2006

lore
Share & tools
lore
#0 lore raw

RFC 1/1 exponential update_wall_time

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

 kernel/timer.c |   28 ++++++++++++++++++++--------
 1 file changed, 20 insertions(+), 8 deletions(-)
kernel/timer.c +20 -8
Index: linux-2.6.18/kernel/timer.c
===================================================================
@@ -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 */
Acked-by on v1 1/1
#1 lore raw
Quoted 7 lines · john stultz

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

works fine and is included in 2.6.18-rt too.

Ingo

#2 lore raw
Quoted 11 lines · Ingo Molnar
Quoted 7 lines · john stultz

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

Quoted 1 line

works fine and is included in 2.6.18-rt too.

Same here.

tglx

#3 lore raw
In reply to john stultz

kernel/timer.c static void update_wall_time(void) · line 919

Quoted 2 lines · On Wed, 27 Sep 2006 12:35:33 -0700 john stultz <[email protected]> wrote:
kernel/timer.c +2 -0
+	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.

#5 lore raw
In reply to john stultz

Hi,

Quoted 4 lines · john stultz

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

#6 lore raw
Quoted 9 lines · Roman Zippel
Quoted 4 lines · john stultz

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?

Quoted 4 lines

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.

Quoted 3 lines

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

#4 lore raw
In reply to Andrew Morton
Quoted 7 lines · Andrew Morton

kernel/timer.c static void update_wall_time(void) · line 919

Quoted 2 lines · On Wed, 27 Sep 2006 12:35:33 -0700 john stultz <[email protected]> wrote:
kernel/timer.c +2 -0
+	while (offset > clock->cycle_interval << (shift + 1))
+		shift++;

hurts my brain.

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

Quoted 3 lines

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

#7 lore raw
In reply to john stultz

Hi,

Quoted 8 lines · john stultz
Quoted 2 lines

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.

Quoted 9 lines
Quoted 4 lines

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.

Quoted 5 lines
Quoted 3 lines

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

#8 lore raw
Quoted 13 lines · Roman Zippel

Hi,

Quoted 8 lines · john stultz
Quoted 2 lines

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?

Quoted 3 lines

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.

Quoted 13 lines
Quoted 13 lines
Quoted 4 lines

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.

Quoted 3 lines

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.

Quoted 7 lines
Quoted 1 line

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

#9 lore raw

Hi,

Quoted 6 lines · john stultz
Quoted 5 lines

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.

Quoted 8 lines

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

#10 lore raw
Quoted 6 lines · Roman Zippel
Quoted 6 lines
Quoted 2 lines

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.

Quoted 8 lines
Quoted 5 lines

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