Skip to contentSkip to conversation

Experimental enhanced NTP error accounting patch

RFC PATCH In review john stultz 2 participants 4 messages Mar 4, 2006 – Mar 10, 2006

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 Experimental enhanced NTP error accounting patch

Hey Roman,
I'm sure you've got a number of things going on, but since I didn't
hear anything back from you last time I posted this, I figured I'd try again.

Here is my first pass implementation of your suggested enhanced NTP error accounting for the generic timekeeping code.

If you could get a chance to review it and let me know if it addresses the issues you are concerned about, I would really appreciate it.

Currently it is a bit ugly and I've noted in the comments what I'm concerned with, but hopefully we can find a way to clean it up a bit.

The patch applies against 2.6.16-rc5-mm2.

Again, I really appreciate the time you've taken in reviewing my patches and explaining your ideas.

thanks
-john

 Documentation/timekeeping.txt   |   22 +---
 include/asm-generic/timeofday.h |    5 -
 include/linux/clocksource.h     |  195 +++++++++++++++++++---------------------
 kernel/time/timeofday.c         |  140 ++++++++++++++--------------
 4 files changed, 173 insertions(+), 189 deletions(-)

linux-2.6.16-rc5_timeofday-ntp-error-fix_B20.patch
============================================

Documentation/timekeeping.txt +7 -15
index 23a5d9d..4ac91b2 100644
@@ -37,12 +37,6 @@ this value in cycle_last.
 cycle_t cycle_last;
 
 
-Further since all clocks drift somewhat from each other, we use the adjustment
-values provided via adjtimex() to correct our clocksource frequency for each
-interval. This frequency adjustment value is stored in ntp_adj.
-
-long ntp_adj;
-
 Now that we've covered the core global variables for timekeeping, lets look at
 how we maintain these values.
 
@@ -54,7 +48,7 @@ presented as:
 timeofday_periodic_hook():
 	cycle_now = read_clocksource(clock)
 	cycle_delta = (cycle_now - cycle_last) & clock->mask
-	nsec = cyc2ns(clock, cycle_delta, ntp_adj)
+	nsec = cyc2ns(clock, cycle_delta)
 	system_time += nsec
 	cycle_last = cycle_now
 
@@ -62,10 +56,9 @@ timeofday_periodic_hook():
 
 You can see we read the cycle value from the clocksource, calculate a cycle
 delta for the interval since we last called timeofday_periodic_hook(), convert
-that cycle delta to a nanosecond interval (for now ignore ntp_adj), add it to
-the system time and finally set our cycle_last value to cycle_now for the next
-interval. Using this simple algorithm we can correctly measure and record the
-passing of time.
+that cycle delta to a nanosecond interval, add it to the system time and finally
+set our cycle_last value to cycle_now for the next interval. Using this simple
+algorithm we can correctly measure and record the passing of time.
 
 But just storing this info isn't very useful, we also want to make it available
 to be used elsewhere. So how do we provide a notion of how much time has passed
@@ -77,7 +70,7 @@ timeofday_peridoic_hook().
 get_nsec_offset():
 	cycle_now = read_clocksource(clock)
 	cycle_delta = (cycle_now - cycle_last) & clock->mask
-	nsec = cyc2ns(clock, cycle_delta, ntp_adj)
+	nsec = cyc2ns(clock, cycle_delta)
 	return nsec
 
 Here you can see, we read the clocksource, calculate a cycle interval, and
@@ -119,14 +112,14 @@ at a safe point, we use the update_callb
 see "How to write a clocksource driver" below), this too must be done
 in-between intervals in the periodic_hook call. Finally, since the ntp
 adjustment made in the cyc2ns conversion is not static, we need to update the
-ntp state machine and get a calculate a new adjustment value.
+ntp state machine and adjust the clocksource mult value.
 
 This adds some extra pseudo code to the timeofday_periodic_hook function:
 
 timeofday_periodic_hook():
 	cycle_now = read_clocksource(clock)
 	cycle_delta = (cycle_now - cycle_last) & clock->mask
-	nsec = cyc2ns(clock, cycle_delta, ntp_adj)
+	nsec = cyc2ns(clock, cycle_delta)
 	system_time += nsec
 	cycle_last = cycle_now
 
@@ -140,7 +133,6 @@ timeofday_periodic_hook():
 
 	ntp_advance(nsec)
 	ppm = ntp_get_ppm_adjustment()
-	ntp_adj = ppm_to_mult_adj(clock, ppm)
 
 
 Unfortunately, the actual timeofday_periodic_hook code is not as simple as this
include/asm-generic/timeofday.h +2 -3
index 79b952f..ddcae35 100644
@@ -20,10 +20,9 @@ extern void sync_persistent_clock(struct
 
 #ifdef CONFIG_GENERIC_TIME_VSYSCALL
 extern void arch_update_vsyscall_gtod(struct timespec wall_time,
-				cycle_t offset_base, struct clocksource* clock,
-				int ntp_adj);
+				cycle_t offset_base, struct clocksource* clock);
 #else
-# define arch_update_vsyscall_gtod(x,y,z,w) do { } while(0)
+# define arch_update_vsyscall_gtod(x,y,z) do { } while(0)
 #endif /* CONFIG_GENERIC_TIME_VSYSCALL */
 
 #endif /* CONFIG_GENERIC_TIME */
include/linux/clocksource.h +95 -100

265 lines not on this page · raw message

kernel/time/timeofday.c +69 -71

240 lines not on this page · raw message

#1 lore raw

Hi,

Quoted 4 lines · john stultz

Hey Roman,
I'm sure you've got a number of things going on, but since I didn't
hear anything back from you last time I posted this, I figured I'd try again.

Sorry about that, I was working on other things. Below are some notes which hopefully help to understand the basic parts.

Quoted 2 lines

Here is my first pass implementation of your suggested enhanced NTP error accounting for the generic timekeeping code.

I don't think it's the right way to go. You do a lot of extra work and adding pieces of my code on top of it is going to be error-prone. To help understanding the basics of my patch let me outline the core math of it. The ntp code provides the time update per tick:

ntp_update = 1sec + adjustments

That's all the clock code needs from the ntp code (the details of its calculation is not really important here) and ntp updates are done in tick intervals. For simplicity let's assume HZ=1 so that the clock is updated every tick by:

	xtime += freq * mult

Due to resolution differences this produces an error with every update, which we accumulate as:

	error += ntp_update - freq * mult

As soon as the error is large we can calculate a new multiplier:

freq * mult_new = freq * mult + error

which becomes:

mult_adj = mult_new - mult = error / freq

Implementation note: The adjustment calculation is a bit more complicated than this for various reasons, but that's really just an implementation detail.

To keep timeofday the same after changing the multiplier we also have to change the base xtime:

timeofday = xtime + off * mult = xtime_new + off * mult_new

so simplified xtime is changed as:

xtime -= off * mult_adj

After changing the multiplier this will also reduce the error:

error -= freq * mult - (off * mult + (freq - off) * mult_new)

This is the difference between the old update and the new update (where the new multiplier is only applied for the rest of the tick), simplified this becomes:

error -= (freq - off) * mult_adj

Finally setting time and changing clock can be done with the same mechanism:

xtime = timeofday - off * mult

timeofday is simply the new time or the current time of the old clock, this means that a clock change can be done outside the periodic hook.

This is basically the core part of my prototype to implement a continous timeofday, the rest is just an implementation detail (e.g. how mult_adj becomes a shift). It's maybe not trivial, but I don't think it's that hard to understand (at least using an example) and results in very simple code.

Maybe the main question I have about your code now is why you want to calculate nsec intervals during the update, but as you can see above, it's not really necessary, so what do you want to use it for?

Another problem is timeofday_periodic_hook(), while I can understand that you want to make it independent of the timer tick, some kind of timer tick is still needed at which ntp time and clock time is synchronized. You go to great lengths to hide it, but it's needed nevertheless, which makes your code harder to read and more complex than needed.
It would be a lot simpler to keep the updates at first at HZ frequency. Later we can still change the update frequency, but ntp time has to be updated in fixed intervals if we want precise time keeping. Note that error adjustments can still be done asynchronously as shown above, but dynamic interval ntp updates are just too complex and error-prone.

I could give it a try to remove all that extra complexity to get it into something mergable, but that would mean dropping quite some bits and I'd prefered if we could agree on something. I simply don't have the time right now to work on patches, which are rejected again in the end.

bye, Roman

#2 lore raw
Quoted 11 lines · Roman Zippel

Hi,

Quoted 4 lines · john stultz

Hey Roman,
I'm sure you've got a number of things going on, but since I didn't
hear anything back from you last time I posted this, I figured I'd try again.

Sorry about that, I was working on other things. Below are some notes which hopefully help to understand the basic parts.

Quite understandable :) We've all got other things to do.

Quoted 7 lines
Quoted 2 lines

Here is my first pass implementation of your suggested enhanced NTP error accounting for the generic timekeeping code.

I don't think it's the right way to go. You do a lot of extra work and adding pieces of my code on top of it is going to be error-prone. To help understanding the basics of my patch let me outline the core math of it.

While I do appreciate the overview (it helps verify or correct the similar proofs I had to do earlier in implementing this patch), I'm not sure I agree that integrating your ideas with the TOD patches is a bad thing. While I think the NTP bits will have to be reconciled, I'm not opposed to your ideas there, so I don't know exactly where the problem is.

The "extra work" I do should have some purpose (as I'm not doing this for fun), so either it can be eliminated or I need to justify it. Being more specific here, like quoting the parts in my patch you don't like would help.

This is an iterative approach, and while I know its frustrating to walk me through all of this, I do think we're making progress.

Quoted 10 lines

The ntp code provides the time update per tick:

ntp_update = 1sec + adjustments

That's all the clock code needs from the ntp code (the details of its calculation is not really important here) and ntp updates are done in tick intervals. For simplicity let's assume HZ=1 so that the clock is updated every tick by:

	xtime += freq * mult

Yep, fundamentally this is the same, although I store (freq/interval)*mult into clocksource.interval_snsecs and use the current cycle value to sort out how many full intervals have passed instead of assuming one-interval per tick. Just like your prototype.

Quoted 4 lines

Due to resolution differences this produces an error with every update, which we accumulate as:

	error += ntp_update - freq * mult

Yep. Same calculation is done in my patch. And we accumulate the error on a per-interval basis.

Quoted 11 lines

As soon as the error is large we can calculate a new multiplier:

freq * mult_new = freq * mult + error

which becomes:

mult_adj = mult_new - mult = error / freq

Implementation note: The adjustment calculation is a bit more complicated than this for various reasons, but that's really just an implementation detail.

I think I have this covered in the make_ntp_adj and error_approximation functions.

Quoted 8 lines

To keep timeofday the same after changing the multiplier we also have to change the base xtime:

timeofday = xtime + off * mult = xtime_new + off * mult_new

so simplified xtime is changed as:

xtime -= off * mult_adj

Again, I believe this is done correctly by the return value of make_ntp_adj().

Quoted 9 lines

After changing the multiplier this will also reduce the error:

error -= freq * mult - (off * mult + (freq - off) * mult_new)

This is the difference between the old update and the new update (where the new multiplier is only applied for the rest of the tick), simplified this becomes:

error -= (freq - off) * mult_adj

This part I'll need to study a bit more as it is not so clear why the error must be corrected, instead of letting it be corrected in the next tick. I know it is required, as the error does not get dampened without it, but the why is less clear. I suspect it has to do with the fact that xtime was adjusted, and since we accumulate error as we accumulate xtime, we have to compensate there as well.

Quoted 7 lines

Finally setting time and changing clock can be done with the same mechanism:

xtime = timeofday - off * mult

timeofday is simply the new time or the current time of the old clock, this means that a clock change can be done outside the periodic hook.

This piques my interest, as I still do not quite see how the clocksource change can occur outside the periodic hook. I'm open to changing this as the clocksource changing code along with the per-interval accumulation does make the periodic_hook code a bit long. Breaking it up sounds like a nice idea, however I'm not following this part.

Quoted 4 lines

This is basically the core part of my prototype to implement a continous timeofday, the rest is just an implementation detail (e.g. how mult_adj becomes a shift). It's maybe not trivial, but I don't think it's that hard to understand (at least using an example) and results in very simple code.

I do agree it is much computationally simpler. However more state must be maintained and the bit about subtracting from xtime to correct for the multiplier adjustment is not trivial to understand at first glance.

Now, after I sat down and proved that bit to myself, it is quite efficient code and I do like the idea of using it. I just want to maintain the readability while getting the efficiency.

Quoted 3 lines

Maybe the main question I have about your code now is why you want to calculate nsec intervals during the update, but as you can see above, it's not really necessary, so what do you want to use it for?

Calculate nsec intervals during the update? I'm not sure specifically which bit you're talking about. Since you didn't really comment specifically on the code I posted, it makes it hard for me to respond. Could you point to a line number or a specific variable name?

Quoted 5 lines

Another problem is timeofday_periodic_hook(), while I can understand that you want to make it independent of the timer tick, some kind of timer tick is still needed at which ntp time and clock time is synchronized. You go to great lengths to hide it, but it's needed nevertheless, which makes your code harder to read and more complex than needed.

I'm not sure I understand what you're getting at here. The only actual tick based code is in ntp_advance() where we calculate the singleshot adjtime adjustment, which is just done to preserve the NTP behavior. This isn't something I'm hiding. Instead it has the benefit of allowing the timekeeping code to not need to run every interrupt, which is needed to handle lost or irregular ticks.

Quoted 5 lines

It would be a lot simpler to keep the updates at first at HZ frequency. Later we can still change the update frequency, but ntp time has to be updated in fixed intervals if we want precise time keeping. Note that error adjustments can still be done asynchronously as shown above, but dynamic interval ntp updates are just too complex and error-prone.

I'd be interested if you could be more specific here. What parts of the NTP state machine has be updated a real fixed intervals and what parts do not?

What I'm trying to do w/ ntp_advance() is inform the NTP state machine that the last total_sppm value calculated was used for the last X nsecs. So a value for the next period can be calculated. It may be that the last total_sppm value was applied for too long, but at least it knows that after the fact rather then not at all.

Really, I'm not so picky about the NTP adjustments as I am about time not going backwards. So I'm very open to your ideas regarding the NTP state machine as long as they don't conflict with correct timekeeping. Running periodic_hook() at HZ frequency is ok by me. However I think using 50ms intervals is a good default because ticks will be missed on users machines and we should have correct behavior in those cases. With the -rt tree, we may only run once a second! I think much like INITIAL_JIFFIES, using 50ms intervals forces the issue rather then ignoring it.

Quoted 4 lines

I could give it a try to remove all that extra complexity to get it into something mergable, but that would mean dropping quite some bits and I'd prefered if we could agree on something. I simply don't have the time right now to work on patches, which are rejected again in the end.

I'm not asking you to drop your work, I just want to understand your objections and try to integrate your ideas. Please also realize that my time is not infinite as well, so the sooner I can understand your ideas and we can agree and get this into mainline, the better. :)

thanks
-john

#3 lore raw

Hi,

Quoted 11 lines · john stultz

While I do appreciate the overview (it helps verify or correct the similar proofs I had to do earlier in implementing this patch), I'm not sure I agree that integrating your ideas with the TOD patches is a bad thing. While I think the NTP bits will have to be reconciled, I'm not opposed to your ideas there, so I don't know exactly where the problem is.

The "extra work" I do should have some purpose (as I'm not doing this for fun), so either it can be eliminated or I need to justify it. Being more specific here, like quoting the parts in my patch you don't like would help.

The point is that it practically completely changes the NTP specific parts, so it should be part of the initial patches.

Quoted 2 lines

This is an iterative approach, and while I know its frustrating to walk me through all of this, I do think we're making progress.

I'm not worried about making progress, I'm worried that this gets merged before it's ready and the NTP bits are not ready yet.

Quoted 8 lines
Quoted 8 lines

After changing the multiplier this will also reduce the error:

error -= freq * mult - (off * mult + (freq - off) * mult_new)

This is the difference between the old update and the new update (where the new multiplier is only applied for the rest of the tick), simplified this becomes:

Quoted 8 lines
Quoted 1 line

error -= (freq - off) * mult_adj

This part I'll need to study a bit more as it is not so clear why the error must be corrected, instead of letting it be corrected in the next tick. I know it is required, as the error does not get dampened without it, but the why is less clear. I suspect it has to do with the fact that xtime was adjusted, and since we accumulate error as we accumulate xtime, we have to compensate there as well.

This is the error of the next tick, we look ahead to the next tick, so we have reduced the error at the time we reach it.
So if we update the error with (ntp_update - mult * freq) we use the values for the current tick and if we change the multiplier we also have to correct the error for the remainder of the current tick. This way we keep the error within the limits and keep it from oscillating.

Quoted 5 lines
Quoted 5 lines

Finally setting time and changing clock can be done with the same mechanism:

xtime = timeofday - off * mult

Quoted 8 lines
Quoted 2 lines

timeofday is simply the new time or the current time of the old clock, this means that a clock change can be done outside the periodic hook.

This piques my interest, as I still do not quite see how the clocksource change can occur outside the periodic hook. I'm open to changing this as the clocksource changing code along with the per-interval accumulation does make the periodic_hook code a bit long. Breaking it up sounds like a nice idea, however I'm not following this part.

The basic idea is really simple:

	lock();
	new_clock->set_time(current_clock->get_time());
	current_clock = new_clock;
	unlock();

I don't quite understand the problem you see with this, only some currently static state has to become per clock state (which is actually a more general problem - too much clock state is global right now).

Quoted 8 lines
Quoted 4 lines

This is basically the core part of my prototype to implement a continous timeofday, the rest is just an implementation detail (e.g. how mult_adj becomes a shift). It's maybe not trivial, but I don't think it's that hard to understand (at least using an example) and results in very simple code.

I do agree it is much computationally simpler. However more state must be maintained and the bit about subtracting from xtime to correct for the multiplier adjustment is not trivial to understand at first glance.

The only really new state is the error value, which you didn't maintain before.

Quoted 3 lines

Now, after I sat down and proved that bit to myself, it is quite efficient code and I do like the idea of using it. I just want to maintain the readability while getting the efficiency.

I guess it's in the eye of the beholder. :)
While I do agree, it's not immediately obvious what the code does, I really would prefer to add the complementing information via documentation.

Quoted 8 lines
Quoted 3 lines

Maybe the main question I have about your code now is why you want to calculate nsec intervals during the update, but as you can see above, it's not really necessary, so what do you want to use it for?

Calculate nsec intervals during the update? I'm not sure specifically which bit you're talking about. Since you didn't really comment specifically on the code I posted, it makes it hard for me to respond. Could you point to a line number or a specific variable name?

For example you still calculate a delta_nsec and ppm values. It also would really help to concentrate first on the current time services and add new time services (which e.g. return ktime_t) in a second patch. I think it's possible that the extra state information for it is updated once a second, in any way a separate patch would be easier to review and improve.

Quoted 9 lines
Quoted 5 lines

It would be a lot simpler to keep the updates at first at HZ frequency. Later we can still change the update frequency, but ntp time has to be updated in fixed intervals if we want precise time keeping. Note that error adjustments can still be done asynchronously as shown above, but dynamic interval ntp updates are just too complex and error-prone.

I'd be interested if you could be more specific here. What parts of the NTP state machine has be updated a real fixed intervals and what parts do not?

I think it's better to give an example of what I have in mind. A lot is already possible without my NTP patches, the periodic function could look something like this:

	off = cycles - cycles_offset;
	while (off >= update_cycles) {
		off -= update_cycles;
		cycles_offset += update_cycles;
		jiffies_64++;
		xtime_nsec += xtime_update;
		if (xtime_nsec >= (u64)NSEC_PER_SEC << 22) {
			xtime_nsec -= (u64)NSEC_PER_SEC << 22;
			xtime.tv_sec++;
			second_overflow();
		}
		xtime.tv_nsec = xtime_nsec >> 22;
		xtime_error += current_tick_length() - xtime_update;
		time_adjust_step = adjtime_adjustment();
		if (time_adjust_step)
			time_adjust -= time_adjust_step;
	}
	[error adjustment]

My patches would move the time_adjust stuff into second_overflow() and make it easier to change the tick length for current_tick_length(). Anyway, this loop does the fixed interval updates (and also basically does the same work as update_times()) and the error adjustment uses "off" for the asynchronous updates and please don't split the loop into multiple loops all over the place.
Most of the NTP work is still done in second_overflow(), there is no need to calculate any ppm values and no need to separate the leapsecond handling (at least initially) - IOW the two NTP rework patches become unnecessary.

Quoted 5 lines

What I'm trying to do w/ ntp_advance() is inform the NTP state machine that the last total_sppm value calculated was used for the last X nsecs. So a value for the next period can be calculated. It may be that the last total_sppm value was applied for too long, but at least it knows that after the fact rather then not at all.

What should it do with this knowledge?

Quoted 3 lines

Really, I'm not so picky about the NTP adjustments as I am about time not going backwards. So I'm very open to your ideas regarding the NTP state machine as long as they don't conflict with correct timekeeping.

Correct timekeeping has two aspects - short-term and long-term correctness. The old code maintains long-term stability by simply jumping to the correct time at every tick. Your code now lets the clock run free loosely controlled via NTP. I would really to like see to keep both aspects correct and preferably before it gets merged.

Quoted 6 lines

Running periodic_hook() at HZ frequency is ok by me. However I think using 50ms intervals is a good default because ticks will be missed on users machines and we should have correct behavior in those cases. With the -rt tree, we may only run once a second! I think much like INITIAL_JIFFIES, using 50ms intervals forces the issue rather then ignoring it.

The point is that you try to fix too many things at once. The current NTP code is very much HZ based and correct timekeeping is also possible at HZ frequency, so let's concentrate first on this and I'm certain it will be simpler than what you have right now.
The update interval can still be changed, but that requires the functional cleanup my NTP patches provide.

Quoted 9 lines
Quoted 4 lines

I could give it a try to remove all that extra complexity to get it into something mergable, but that would mean dropping quite some bits and I'd prefered if we could agree on something. I simply don't have the time right now to work on patches, which are rejected again in the end.

I'm not asking you to drop your work, I just want to understand your objections and try to integrate your ideas. Please also realize that my time is not infinite as well, so the sooner I can understand your ideas and we can agree and get this into mainline, the better. :)

That wouldn't be a problem, if there wasn't the pressure to get this merged as soon as possible. It seems lately it has been more important to get new features merged, than taking the time to do the necessary groundwork thoroughly.

bye, Roman