[RFC][PATCH 1/2] Reduced NTP rework (part 1)

[RFC][PATCH 1/2] Reduced NTP rework (part 1)

[john stultz]

Roman, All,
	
	With Roman's suggestions, I've been working on reducing the footprint
of my timeofday patches. This is the first of two patches that I wanted
to float by the list for feedback before I merge it into my patchset.

This patch reworks some of the interrupt time NTP adjustments so that it
could be re-used with the timeofday patches. The motivation of the
change is to logically separate the code which adjusts xtime and the
code that decides (based on the NTP state variables) how much per tick
to adjust xtime. 

Thus this patch should not affect the existing behavior, but just
separate the logical functionality so it can be re-used.

This is mainly for review, so I don't think anyone will really use it,
but it applies ontop of my ntp-shift-right_A3 cleanup patch I sent out
earlier.

thanks
-john

linux-2.6.14-rc2_timeofday-ntp-part1_B6test.patch
============================================
diff --git a/kernel/timer.c b/kernel/timer.c
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -742,46 +742,47 @@ static void second_overflow(void)
 #endif
 }
 
-/* in the NTP reference this is called "hardclock()" */
-static void update_wall_time_one_tick(void)
+long time_adjust_step;
+
+static void ntp_advance(unsigned long interval_ns)
 {
-	long time_adjust_step, delta_nsec;
+	static unsigned long interval_sum;
 
-	if ( (time_adjust_step = time_adjust) != 0 ) {
-	    /* We are doing an adjtime thing. 
-	     *
-	     * Prepare time_adjust_step to be within bounds.
-	     * Note that a positive time_adjust means we want the clock
-	     * to run faster.
-	     *
-	     * Limit the amount of the step to be in the range
-	     * -tickadj .. +tickadj
-	     */
-	     time_adjust_step = min(time_adjust_step, (long)tickadj);
-	     time_adjust_step = max(time_adjust_step, (long)-tickadj);
+	/* increment the interval sum */
+	interval_sum += interval_ns;
 
-	    /* Reduce by this step the amount of time left  */
-	    time_adjust -= time_adjust_step;
-	}
-	delta_nsec = tick_nsec + time_adjust_step * 1000;
-	/*
-	 * Advance the phase, once it gets to one microsecond, then
-	 * advance the tick more.
-	 */
-	time_phase += time_adj;
-	if ((time_phase >= FINENSEC) || (time_phase <= -FINENSEC)) {
-		long ltemp = shift_right(time_phase, (SHIFT_SCALE - 10));
-		time_phase -= ltemp << (SHIFT_SCALE - 10);
-		delta_nsec += ltemp;
+	/* calculate the per tick singleshot adjtime adjustment step */
+	while (interval_ns >= tick_nsec) {
+		time_adjust_step = time_adjust;
+		if (time_adjust_step) {
+	    	/* We are doing an adjtime thing.
+		     *
+		     * Prepare time_adjust_step to be within bounds.
+		     * Note that a positive time_adjust means we want the clock
+	    	 * to run faster.
+		     *
+	    	 * Limit the amount of the step to be in the range
+		     * -tickadj .. +tickadj
+		     */
+	    	 time_adjust_step = min(time_adjust_step, (long)tickadj);
+		     time_adjust_step = max(time_adjust_step, (long)-tickadj);
+
+		    /* Reduce by this step the amount of time left  */
+	    	time_adjust -= time_adjust_step;
+		}
+		interval_ns -= tick_nsec;
 	}
-	xtime.tv_nsec += delta_nsec;
-	time_interpolator_update(delta_nsec);
 
 	/* Changes by adjtime() do not take effect till next tick. */
-	if (time_next_adjust != 0) {
+	if (time_next_adjust) {
 		time_adjust = time_next_adjust;
 		time_next_adjust = 0;
 	}
+
+	while (interval_sum > NSEC_PER_SEC) {
+		interval_sum -= NSEC_PER_SEC;
+		second_overflow();
+	}
 }
 
 /*
@@ -793,14 +794,35 @@ static void update_wall_time_one_tick(vo
  */
 static void update_wall_time(unsigned long ticks)
 {
+	long delta_nsec;
+
 	do {
 		ticks--;
-		update_wall_time_one_tick();
+
+		/* Calculate the nsec delta using the
+		 * precomputed NTP adjustments:
+		 *     tick_nsec, time_adjust_step, time_adj
+		 */
+		delta_nsec = tick_nsec + time_adjust_step * 1000;
+		/*
+		 * Advance the phase, once it gets to one microsecond, then
+		 * advance the tick more.
+		 */
+		time_phase += time_adj;
+		if ((time_phase >= FINENSEC) || (time_phase <= -FINENSEC)) {
+			long ltemp = shift_right(time_phase, (SHIFT_SCALE - 10));
+			time_phase -= ltemp << (SHIFT_SCALE - 10);
+			delta_nsec += ltemp;
+		}
+
+		xtime.tv_nsec += delta_nsec;
 		if (xtime.tv_nsec >= 1000000000) {
 			xtime.tv_nsec -= 1000000000;
 			xtime.tv_sec++;
-			second_overflow();
 		}
+		ntp_advance(tick_nsec);
+		time_interpolator_update(delta_nsec);
+
 	} while (ticks);
 }
 

[RFC][PATCH 2/2] Reduced NTP rework (part 2)

[john stultz]

Roman, All,

	Here is the second of two patches which try a minimized version of my
ntp rework patches. 
	
This patch further changes the interrupt time NTP code, breaking out the
leapsecond processing and introduces an accessor to a shifted ppm
adjustment value.  

Again, this patch should not affect the existing behavior, but just
separate the logical functionality so it can be re-used by my timeofday
patches.

thanks
-john

linux-2.6.14-rc2_timeofday-ntp-part2_B6test.patch
============================================
diff --git a/kernel/timer.c b/kernel/timer.c
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -620,6 +620,78 @@ static long time_adj;			/* tick adjust (
 long time_reftime;			/* time at last adjustment (s)	*/
 long time_adjust;
 long time_next_adjust;
+long time_adjust_step;	/* per tick time_adjust step */
+
+long total_sppm;	/* shifted ppm sum of all NTP adjustments */
+long offset_adj_ppm;
+long tick_adj_ppm;
+long singleshot_adj_ppm;
+
+#define MAX_SINGLESHOT_ADJ 500 /* (ppm) */
+#define SEC_PER_DAY 86400
+
+/**
+ * ntp_leapsecond - NTP leapsecond processing code.
+ * now: the current time
+ *
+ * Returns the number of seconds (-1, 0, or 1) that
+ * should be added to the current time to properly
+ * adjust for leapseconds.
+ */
+int ntp_leapsecond(struct timespec now)
+{
+	/*
+	 * Leap second processing. If in leap-insert state at
+	 * the end of the day, the system clock is set back one
+	 * second; if in leap-delete state, the system clock is
+	 * set ahead one second.
+	 */
+	static time_t leaptime = 0;
+
+	switch (time_state) {
+
+	case TIME_OK:
+		if (time_status & STA_INS)
+			time_state = TIME_INS;
+		else if (time_status & STA_DEL)
+			time_state = TIME_DEL;
+
+		/* calculate end of today (23:59:59)*/
+		leaptime = now.tv_sec + SEC_PER_DAY -
+					(now.tv_sec % SEC_PER_DAY) - 1;
+		break;
+
+	case TIME_INS:
+		/* Once we are at (or past) leaptime, insert the second */
+		if (now.tv_sec >= leaptime) {
+			time_state = TIME_OOP;
+			printk(KERN_NOTICE "Clock: inserting leap second 23:59:60 UTC\n");
+			return -1;
+		}
+		break;
+
+	case TIME_DEL:
+		/* Once we are at (or past) leaptime, delete the second */
+		if (now.tv_sec >= leaptime) {
+			time_state = TIME_WAIT;
+			printk(KERN_NOTICE "Clock: deleting leap second 23:59:59 UTC\n");
+			return 1;
+		}
+		break;
+
+	case TIME_OOP:
+		/*  Wait for the end of the leap second*/
+		if (now.tv_sec > (leaptime + 1))
+			time_state = TIME_WAIT;
+		time_state = TIME_WAIT;
+		break;
+
+	case TIME_WAIT:
+		if (!(time_status & (STA_INS | STA_DEL)))
+			time_state = TIME_OK;
+	}
+	return 0;
+}
 
 /*
  * this routine handles the overflow of the microsecond field
@@ -642,59 +714,6 @@ static void second_overflow(void)
     }
 
     /*
-     * Leap second processing. If in leap-insert state at
-     * the end of the day, the system clock is set back one
-     * second; if in leap-delete state, the system clock is
-     * set ahead one second. The microtime() routine or
-     * external clock driver will insure that reported time
-     * is always monotonic. The ugly divides should be
-     * replaced.
-     */
-    switch (time_state) {
-
-    case TIME_OK:
-	if (time_status & STA_INS)
-	    time_state = TIME_INS;
-	else if (time_status & STA_DEL)
-	    time_state = TIME_DEL;
-	break;
-
-    case TIME_INS:
-	if (xtime.tv_sec % 86400 == 0) {
-	    xtime.tv_sec--;
-	    wall_to_monotonic.tv_sec++;
-	    /* The timer interpolator will make time change gradually instead
-	     * of an immediate jump by one second.
-	     */
-	    time_interpolator_update(-NSEC_PER_SEC);
-	    time_state = TIME_OOP;
-	    clock_was_set();
-	    printk(KERN_NOTICE "Clock: inserting leap second 23:59:60 UTC\n");
-	}
-	break;
-
-    case TIME_DEL:
-	if ((xtime.tv_sec + 1) % 86400 == 0) {
-	    xtime.tv_sec++;
-	    wall_to_monotonic.tv_sec--;
-	    /* Use of time interpolator for a gradual change of time */
-	    time_interpolator_update(NSEC_PER_SEC);
-	    time_state = TIME_WAIT;
-	    clock_was_set();
-	    printk(KERN_NOTICE "Clock: deleting leap second 23:59:59 UTC\n");
-	}
-	break;
-
-    case TIME_OOP:
-	time_state = TIME_WAIT;
-	break;
-
-    case TIME_WAIT:
-	if (!(time_status & (STA_INS | STA_DEL)))
-	    time_state = TIME_OK;
-    }
-
-    /*
      * Compute the phase adjustment for the next second. In
      * PLL mode, the offset is reduced by a fixed factor
      * times the time constant. In FLL mode the offset is
@@ -711,6 +730,13 @@ static void second_overflow(void)
 	time_offset -= ltemp;
 	time_adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
 
+	offset_adj_ppm = shift_right(ltemp, SHIFT_UPDATE); /* ppm */
+
+	/* first calculate usec/user_tick offset */
+	tick_adj_ppm = ((USEC_PER_SEC + USER_HZ/2)/USER_HZ) - tick_usec;
+	/* multiply by user_hz to get usec/sec => ppm */
+	tick_adj_ppm *= USER_HZ;
+
     /*
      * Compute the frequency estimate and additional phase
      * adjustment due to frequency error for the next
@@ -742,9 +768,17 @@ static void second_overflow(void)
 #endif
 }
 
-long time_adjust_step;
 
-static void ntp_advance(unsigned long interval_ns)
+/**
+ * ntp_get_ppm_adjustment - Returns Shifted PPM adjustment
+ *
+ */
+long ntp_get_ppm_adjustment(void)
+{
+	return total_sppm;
+}
+
+void ntp_advance(unsigned long interval_ns)
 {
 	static unsigned long interval_sum;
 
@@ -772,6 +806,7 @@ static void ntp_advance(unsigned long in
 		}
 		interval_ns -= tick_nsec;
 	}
+	singleshot_adj_ppm = time_adjust_step*(1000000/HZ); /* usec/tick => ppm */
 
 	/* Changes by adjtime() do not take effect till next tick. */
 	if (time_next_adjust) {
@@ -783,6 +818,12 @@ static void ntp_advance(unsigned long in
 		interval_sum -= NSEC_PER_SEC;
 		second_overflow();
 	}
+
+	/* calculate the total continuous ppm adjustment */
+	total_sppm = time_freq; /* already shifted by SHIFT_USEC */
+	total_sppm += offset_adj_ppm << SHIFT_USEC;
+	total_sppm += tick_adj_ppm << SHIFT_USEC;
+	total_sppm += singleshot_adj_ppm << SHIFT_USEC;
 }
 
 /*
@@ -817,8 +858,18 @@ static void update_wall_time(unsigned lo
 
 		xtime.tv_nsec += delta_nsec;
 		if (xtime.tv_nsec >= 1000000000) {
+			int leapsecond;
 			xtime.tv_nsec -= 1000000000;
 			xtime.tv_sec++;
+			/* process leapsecond */
+			leapsecond = ntp_leapsecond(xtime);
+			if (leapsecond) {
+				xtime.tv_sec += leapsecond;
+				wall_to_monotonic.tv_sec -= leapsecond;
+				/* Use of time interpolator for a gradual change of time */
+				time_interpolator_update(leapsecond*NSEC_PER_SEC);
+				clock_was_set();
+			}
 		}
 		ntp_advance(tick_nsec);
 		time_interpolator_update(delta_nsec);

Re: [RFC][PATCH 2/2] Reduced NTP rework (part 2)

[Roman Zippel]

Hi,

On Thu, 22 Sep 2005, john stultz wrote:

> +
> +	/* calculate the total continuous ppm adjustment */
> +	total_sppm = time_freq; /* already shifted by SHIFT_USEC */
> +	total_sppm += offset_adj_ppm << SHIFT_USEC;
> +	total_sppm += tick_adj_ppm << SHIFT_USEC;
> +	total_sppm += singleshot_adj_ppm << SHIFT_USEC;
>  }

I'm not sure, why you still need this.
As I already said, I don't think you need to change the kernel NTP model. 
This means in particular that the NTP time is still incremented in fixed 
intervals (although it's not necessary to do it at HZ frequency).
I showed you how to do most of the calculation, so I'm a little confused, 
why the above is still used.

In general I would prefer to see the introduction of the timesource 
abstraction, which will first replace the arch callbacks do_gettimeofday/ 
do_settimeofday.

bye, Roman

Re: [RFC][PATCH 2/2] Reduced NTP rework (part 2)

[john stultz]

On Tue, 2005-09-27 at 18:37 +0200, Roman Zippel wrote:
> Hi,
> 
> On Thu, 22 Sep 2005, john stultz wrote:
> 
> > +
> > +	/* calculate the total continuous ppm adjustment */
> > +	total_sppm = time_freq; /* already shifted by SHIFT_USEC */
> > +	total_sppm += offset_adj_ppm << SHIFT_USEC;
> > +	total_sppm += tick_adj_ppm << SHIFT_USEC;
> > +	total_sppm += singleshot_adj_ppm << SHIFT_USEC;
> >  }
> 
> I'm not sure, why you still need this.
> As I already said, I don't think you need to change the kernel NTP model. 
> This means in particular that the NTP time is still incremented in fixed 
> intervals (although it's not necessary to do it at HZ frequency).
> I showed you how to do most of the calculation, so I'm a little confused, 
> why the above is still used.

Yea. I had spent some time implementing your idea about having a
reference xtime that is only NTP adjusted, then timesource based
system_time which adjusts the frequency of time timesource when
system_time and the ntp adjusted xtime drift apart. 

The biggest concern was having duplicate timekeeping subsystems in play
at once. 

With the approach I was taking earlier, I didn't like the idea of having
2 duplicate generic timekeeping systems that are different on different
arches, but I figured it would be be an improvement, since a number of
arches would then not need any arch specific timekeeping code (which is
not the case now).

However, with you idea, on some arches we have to keep two timekeeping
subsystems running at once, with code trying to smoothly synchronize
them. I got a little frustrated trying to generate a clean
implementation and decided to skip that idea for now. I'm not ruling it
out, but I wanted to explore some other ideas I have.

So I started playing with a few different approaches in the short term,
trying to adapt some of your ideas (such as using fixed interval time
accumulation to avoid the multiply at tick time) to my existing code.

Further I'm trying to slowly manipulate both the current tick based
update_wall_clock() and my timekeeping_periodic_hook() functions so that
they begin to resemble each other. This way I can begin to show
equivalence between the two. 


The idea being:

update_wall_clock():
	ticks = jiffies - wall_jiffies
	while (ticks):
		ticks--
		xtime += tick_nsec + ntp_adjustment


isn't that different from:

timekeeping_periodic_hook():
	now = timesource_read(ts)
	delta_cycle = now - last
	while (delta_cycle > interval_cycle):
		delta_cycle -= interval_cycle
		system_time += interval_nsec


Where ts is the jiffies timesource and the interval_nsec is a
precomputed equivalent to (tick_nsec + ntp_adjustment). 

The only difference between continuous and tick based systems would then
be in gettimeofday() (which really could be the same with a simple
#define)

continuous_gettimeofday():
	now = timesource_read(ts)
	delta_cycle = now - last
	delta_nsec = cyc2ns(timesource, delta_cycle)
	return system_time + delta_nsec

tick_gettime():
	now = timesource_read(jiffes_timesource)
	delta_cycle = now - last
	delta_nsec = cyc2ns(timesource, delta_cycle)
	delta_nsec += arch_get_offset()
	return system_time + delta_nsec


Which isn't all that different from the existing:
	usec = mach_gettimeoffset();
	lost = jiffies - wall_jiffies;
	/*
	 * If time_adjust is negative then NTP is slowing the clock
	 * so make sure not to go into next possible interval.
	 * Better to lose some accuracy than have time go backwards..
	 */
	if (unlikely(time_adjust < 0)) {
		usec = min(usec, max_ntp_tick);
		if (lost)
			usec += lost * max_ntp_tick;
	}
	else if (unlikely(lost))
		usec += lost * tick_usec;

	sec = xtime.tv_sec;
	usec += xtime.tv_nsec/1000;

Logic seen in the m68k time.c

With luck I'll have something more then just pseudo code to review soon.

thanks
-john

Re: [RFC][PATCH 2/2] Reduced NTP rework (part 2)

[Thomas Gleixner]

On Tue, 2005-09-27 at 13:19 -0700, john stultz wrote:
> Yea. I had spent some time implementing your idea about having a
> reference xtime that is only NTP adjusted, then timesource based
> system_time which adjusts the frequency of time timesource when
> system_time and the ntp adjusted xtime drift apart. 
> 
> The biggest concern was having duplicate timekeeping subsystems in play
> at once. 

Which would be wrong IMNSHO.

Please keep the current xtime centric implementation out of your mind. 

As I pointed out in the ktimers thread already the  correct chain of
processing is

raw timesource 
	-> freqency adjustment (== CLOCK_MONOTONIC) 
		-> wall time adjustment (== CLOCK_REALTIME)

This is the way all real world time sources work. Nobody screws on an
atomic clock because the earth rotation is not constant. Why should
Linux be different ? For historic reasons - because it was that way
since v0.95 ?

There is no performance penalty involved doing it this way. It just
changes the order of corrections. The performance critical stuff is a
question of implementation details not of processing order.

> Which isn't all that different from the existing:
> 	usec = mach_gettimeoffset();
<SNIP>
> 	sec = xtime.tv_sec;
> 	usec += xtime.tv_nsec/1000;
> 
> Logic seen in the m68k time.c

Same code in most other archs.

tglx

Re: [RFC][PATCH 2/2] Reduced NTP rework (part 2)

[Roman Zippel]

Hi,

On Tue, 27 Sep 2005, john stultz wrote:

> However, with you idea, on some arches we have to keep two timekeeping
> subsystems running at once, with code trying to smoothly synchronize
> them. I got a little frustrated trying to generate a clean
> implementation and decided to skip that idea for now. I'm not ruling it
> out, but I wanted to explore some other ideas I have.
> 
> So I started playing with a few different approaches in the short term,
> trying to adapt some of your ideas (such as using fixed interval time
> accumulation to avoid the multiply at tick time) to my existing code.

I don't want to keep you from playing with different ideas, but I would 
strongly suggest you do it first with an userspace simulator. If you 
change too much, be prepared to do some sort of analysis of these changes. 
A simulator would be one way, but plain math would be fine too.
It's really important that you get the math right first and then develop 
the kernel model from that. It would also be ok if you do a first 
prototype using nsec, but it's important to also look at the long term 
stability of the clock and how well it works together with the NTP daemon.

> The idea being:
> 
> update_wall_clock():
> 	ticks = jiffies - wall_jiffies
> 	while (ticks):
> 		ticks--
> 		xtime += tick_nsec + ntp_adjustment
> 
> 
> isn't that different from:
> 
> timekeeping_periodic_hook():
> 	now = timesource_read(ts)
> 	delta_cycle = now - last
> 	while (delta_cycle > interval_cycle):
> 		delta_cycle -= interval_cycle
> 		system_time += interval_nsec

BTW that's not what you do in the first part of the patch:

+static void ntp_advance(unsigned long interval_ns)

I'm quite sure that the interval_ns is wrong, it's important to advance 
the ntp state in constant intervals (i.e. interval_cycle). Your patch 
already includes time adjustments and e.g. the "while (interval_ns >= 
tick_nsec)" loop is not executed anymore, once time_adjust_step becomes 
negative.
In general I would prefer it if we could finalize the basic design first, 
before doing such changes, otherwise I'm afraid we need a cleanup of the 
cleanup.

> The only difference between continuous and tick based systems would then
> be in gettimeofday() (which really could be the same with a simple
> #define)
> 
> continuous_gettimeofday():
> 	now = timesource_read(ts)
> 	delta_cycle = now - last
> 	delta_nsec = cyc2ns(timesource, delta_cycle)
> 	return system_time + delta_nsec
> 
> tick_gettime():
> 	now = timesource_read(jiffes_timesource)
> 	delta_cycle = now - last
> 	delta_nsec = cyc2ns(timesource, delta_cycle)
> 	delta_nsec += arch_get_offset()
> 	return system_time + delta_nsec

The basic idea of gettimeofday is of course always the same: "base + 
get_offset() * mult". I can understand the temptation to unify the 
implementation, but please accept the current reality that we have 
different gettimeofday implementations (for whatever reasons), so unifying 
them would be a premature change. If the situation changes later we can 
still do that unification.

> Logic seen in the m68k time.c

I know that code and I really want to replace it with something better. :) 
Unfortunately I didn't catch the crap introduced by nsec conversion.

bye, Roman

Re: [RFC][PATCH 2/2] Reduced NTP rework (part 2)

[john stultz]

On Thu, 2005-09-29 at 20:43 +0200, Roman Zippel wrote:
> On Tue, 27 Sep 2005, john stultz wrote:
> > The idea being:
> > 
> > update_wall_clock():
> > 	ticks = jiffies - wall_jiffies
> > 	while (ticks):
> > 		ticks--
> > 		xtime += tick_nsec + ntp_adjustment
> > 
> > 
> > isn't that different from:
> > 
> > timekeeping_periodic_hook():
> > 	now = timesource_read(ts)
> > 	delta_cycle = now - last
> > 	while (delta_cycle > interval_cycle):
> > 		delta_cycle -= interval_cycle
> > 		system_time += interval_nsec
> 
> BTW that's not what you do in the first part of the patch:
> 
> +static void ntp_advance(unsigned long interval_ns)

Well, I was trying to describe what I am going to follow the NTP patches
with. 

So yes, the reduced NTP rework patches are not discussed in the above
(but ntp_advance() does have a place in the above, I just left it out to
shorten the comparison), but they allow the two examples above to look
similar. 

For clarity here's the ntp details included

update_wall_clock():
	ticks = jiffies - wall_jiffies
	while (ticks):
		ticks--
		xtime += tick_nsec + ntp_adjustment
		ntp_advance(tick_nsec)


timekeeping_periodic_hook():
	now = timesource_read(ts)
	delta_cycle = now - last
	while (delta_cycle > interval_cycle):
		delta_cycle -= interval_cycle
		system_time += interval_nsec
		ntp_advance(interval_nsec)


> I'm quite sure that the interval_ns is wrong, it's important to advance 
> the ntp state in constant intervals (i.e. interval_cycle). Your patch 
> already includes time adjustments and e.g. the "while (interval_ns >= 
> tick_nsec)" loop is not executed anymore, once time_adjust_step becomes 
> negative.

Commenting the specific code would help clarify this. If I'm
understanding you, you're talking about the following logic:

static void ntp_advance(unsigned long interval_ns):
	static unsigned long interval_sum;

	/* increment the interval sum */
	interval_sum += interval_ns

	/* calculate the per tick singleshot adjtime adjustment step */
	while (interval_ns >= tick_nsec):
		time_adjust_step = time_adjust
		if (time_adjust_step):
			time_adjust_step = min(time_adjust_step, tickadj)
			time_adjust_step = max(time_adjust_step, -tickadj)
			time_adjust -= time_adjust_step
		interval_ns -= tick_nsec

I'm not sure I understand the problem if time_adjust_step becomes
negative.

> In general I would prefer it if we could finalize the basic design first, 
> before doing such changes, otherwise I'm afraid we need a cleanup of the 
> cleanup.

Well, that's evolution. :)  But really, the reduced ntp rework stuff
isn't a cleanup. Its just the bare minimum changes to NTP that I'm
needing for my generic timeofday code. Hopefully the reduced changes
will clarify what exactly I need (or think I need ;) from the NTP
subsystem to get my timekeeping code to function properly. Then maybe
you (or anyone else - don't let Roman have all the fun) can point to a
better way. 


> > The only difference between continuous and tick based systems would then
> > be in gettimeofday() (which really could be the same with a simple
> > #define)
> > 
> > continuous_gettimeofday():
> > 	now = timesource_read(ts)
> > 	delta_cycle = now - last
> > 	delta_nsec = cyc2ns(timesource, delta_cycle)
> > 	return system_time + delta_nsec
> > 
> > tick_gettime():
> > 	now = timesource_read(jiffes_timesource)
> > 	delta_cycle = now - last
> > 	delta_nsec = cyc2ns(timesource, delta_cycle)
> > 	delta_nsec += arch_get_offset()
> > 	return system_time + delta_nsec
> 
> The basic idea of gettimeofday is of course always the same: "base + 
> get_offset() * mult". I can understand the temptation to unify the 
> implementation, but please accept the current reality that we have 
> different gettimeofday implementations (for whatever reasons), so unifying 
> them would be a premature change. If the situation changes later we can 
> still do that unification.

I'm sorta going at it from the other way (call me optimistic :), where
I'm trying to unify what I can until I hit the exception. Then I'll
happily break out an arch specific gettimeofday implementation.

Once again, I do appreciate your feedback. Hopefully I'll have patches
out later today for you to look at.

thanks
-john

Re: [RFC][PATCH 2/2] Reduced NTP rework (part 2)

[Roman Zippel]

Hi,

On Thu, 29 Sep 2005, john stultz wrote:

> timekeeping_periodic_hook():
> 	now = timesource_read(ts)
> 	delta_cycle = now - last
> 	while (delta_cycle > interval_cycle):
> 		delta_cycle -= interval_cycle
> 		system_time += interval_nsec
> 		ntp_advance(interval_nsec)

I'm concerned about the clock stability of your code. By rounding it to 
nsec you throwing away a few bits of resolution (unless I'm missing 
something).

At http://www.xs4all.nl/~zippel/ntp/ there are a few patches to cleanup 
the kernel ntp calculations. I extracted the first two patches from your 
patches, the other patches precompute as much as possible so that the 
interrupt functions become quite simple and also fix a few rounding 
problems. What might be useful for you how second_overflow() calculates 
the advancement for the next HZ ticks. This means ntp_advance() isn't 
really needed at all, but instead second_overflow() precalculates 
everything for next second.

(The patches aren't documented yet and only for 2.6.13, I'll fix this 
soon).

I also included the modification for old ntp reference implementation to 
match this behaviour, so I could verify and test my changes in a 
simulator. I'd really like to have something like this for your 
implementation, so it's easier to look at its behaviour.

I started looking through the nanokernel implementation to see how it can 
be applied to Linux.

> > The basic idea of gettimeofday is of course always the same: "base + 
> > get_offset() * mult". I can understand the temptation to unify the 
> > implementation, but please accept the current reality that we have 
> > different gettimeofday implementations (for whatever reasons), so unifying 
> > them would be a premature change. If the situation changes later we can 
> > still do that unification.
> 
> I'm sorta going at it from the other way (call me optimistic :), where
> I'm trying to unify what I can until I hit the exception. Then I'll
> happily break out an arch specific gettimeofday implementation.

That's fine as long as doesn't change too much, but OTOH a little code 
duplication doesn't hurt. Concentration on introducing the time source 
abstraction is IMO currently more important, having more than one ntp 
implemenation is not such a big problem during development, so the need 
for a config option disappears and people can quickly switch between 
implementations, if there should be a problem.
In the end we actually may have slightly different NTP implementations, as 
each timesource may have different requirements of what needs to be 
precalculated for an efficient timer implementation. The unification 
should really be the last step, first we need to get the basic stuff 
right, then we can look at what can and should be optimized and only then 
should we cleanup the common things.

bye, Roman

Re: [RFC][PATCH 2/2] Reduced NTP rework (part 2)

[john stultz]

On Mon, 2005-10-10 at 14:39 +0200, Roman Zippel wrote:
> Hi,
> 
> On Thu, 29 Sep 2005, john stultz wrote:
> 
> > timekeeping_periodic_hook():
> > 	now = timesource_read(ts)
> > 	delta_cycle = now - last
> > 	while (delta_cycle > interval_cycle):
> > 		delta_cycle -= interval_cycle
> > 		system_time += interval_nsec
> > 		ntp_advance(interval_nsec)
> 
> I'm concerned about the clock stability of your code. By rounding it to 
> nsec you throwing away a few bits of resolution (unless I'm missing 
> something).

Nope, you're right. That's very much an issue that I glossed over in
this example. In fact, in the B6 release, I added a remainder field to
the interval structure, but I didn't get to implementing the details. I
do have the code implemented for B7, which I hope to release later this
week.


> At http://www.xs4all.nl/~zippel/ntp/ there are a few patches to cleanup 
> the kernel ntp calculations. I extracted the first two patches from your 
> patches, the other patches precompute as much as possible so that the 
> interrupt functions become quite simple and also fix a few rounding 
> problems. What might be useful for you how second_overflow() calculates 
> the advancement for the next HZ ticks. This means ntp_advance() isn't 
> really needed at all, but instead second_overflow() precalculates 
> everything for next second.

Great! I think having more minds working at cleaning up this code will
really help. Hopefully having concrete code implementations to compare
will give us additional common ground to work from. 

I think calculating all the adjustments into second overflow doesn't
sound objectionable, although it does seemingly bind us to second
intervals. Having the ntp_advance interface allows the implementation
internally to be flexible for whatever interval. But it doesn't sound
like a major issue at the moment.


> (The patches aren't documented yet and only for 2.6.13, I'll fix this 
> soon).

Let me know when they've been updated. I've looked over them and have a
few questions that probably would be easily answered with a small
comment.


> I also included the modification for old ntp reference implementation to 
> match this behaviour, so I could verify and test my changes in a 
> simulator. I'd really like to have something like this for your 
> implementation, so it's easier to look at its behaviour.

I'll take a look at this and see if I can do similar. Its a little more
difficult because moving from tick based to continuous adds some
complexity to the simulation.


> I started looking through the nanokernel implementation to see how it can 
> be applied to Linux.

Nice.


> > > The basic idea of gettimeofday is of course always the same: "base + 
> > > get_offset() * mult". I can understand the temptation to unify the 
> > > implementation, but please accept the current reality that we have 
> > > different gettimeofday implementations (for whatever reasons), so unifying 
> > > them would be a premature change. If the situation changes later we can 
> > > still do that unification.
> > 
> > I'm sorta going at it from the other way (call me optimistic :), where
> > I'm trying to unify what I can until I hit the exception. Then I'll
> > happily break out an arch specific gettimeofday implementation.
> 
> That's fine as long as doesn't change too much, but OTOH a little code 
> duplication doesn't hurt. Concentration on introducing the time source 
> abstraction is IMO currently more important, having more than one ntp 
> implemenation is not such a big problem during development, so the need 
> for a config option disappears and people can quickly switch between 
> implementations, if there should be a problem.

I'm not too worried about needing separate NTP implementations, as
fundamentally all we do is take a number of adjustment values, merge
them into one adjustment value and apply that as we maintain time. If
the output is a flat per-tick nanosecond adjustment or a continuous
shifted ppm adjustment, the core state machine management will be the
same.

> In the end we actually may have slightly different NTP implementations, as 
> each timesource may have different requirements of what needs to be 
> precalculated for an efficient timer implementation. The unification 
> should really be the last step, first we need to get the basic stuff 
> right, then we can look at what can and should be optimized and only then 
> should we cleanup the common things.

Again, with my smaller set of changes and with your new changes I don't
think fully separate implementations will be required (and even more so
WRT per-timesource ntp implementations). But I think working this from
multiple approaches will better clarify the specific needs we both have.

thanks
-john

Re: [RFC][PATCH 2/2] Reduced NTP rework (part 2)

[Ulrich Windl]

On 27 Sep 2005 at 18:37, Roman Zippel wrote:

> Hi,
> 
> On Thu, 22 Sep 2005, john stultz wrote:
> 
> > +
> > +	/* calculate the total continuous ppm adjustment */
> > +	total_sppm = time_freq; /* already shifted by SHIFT_USEC */
> > +	total_sppm += offset_adj_ppm << SHIFT_USEC;
> > +	total_sppm += tick_adj_ppm << SHIFT_USEC;
> > +	total_sppm += singleshot_adj_ppm << SHIFT_USEC;
> >  }
> 
> I'm not sure, why you still need this.
> As I already said, I don't think you need to change the kernel NTP model. 
> This means in particular that the NTP time is still incremented in fixed 
> intervals (although it's not necessary to do it at HZ frequency).
> I showed you how to do most of the calculation, so I'm a little confused, 
> why the above is still used.

Hi all!

As playing with "tick" is considered obsolete by the NTP people, frequency errors 
up to 500 PPM are corrected by the NTP kernel code. Thus, to provide continuous 
time, you might be interested in adjusting tick interpolation (i.e. _use_ the 
adjusted value whenever the clock is read).

Ulrich

> 
> In general I would prefer to see the introduction of the timesource 
> abstraction, which will first replace the arch callbacks do_gettimeofday/ 
> do_settimeofday.
> 
> bye, Roman

Re: [RFC][PATCH 2/2] Reduced NTP rework (part 2)

[john stultz]

On Tue, 2005-10-04 at 09:58 +0200, Ulrich Windl wrote:
> As playing with "tick" is considered obsolete by the NTP people, frequency errors 
> up to 500 PPM are corrected by the NTP kernel code. Thus, to provide continuous 
> time, you might be interested in adjusting tick interpolation (i.e. _use_ the 
> adjusted value whenever the clock is read).

Not sure if I followed that. Could you go into more detail please?

thanks
-john