[PATCH 2/10] NTP: normalize time_adj

[PATCH 2/10] NTP: normalize time_adj

[Roman Zippel]

This normalizes the calculated value time_adj in second_overflow() to be
always positive. The difference is added to tick_nsec and stored in
tick_nsec_curr. This simplifies the work needed in
update_wall_time_one_tick() as time_phase is always positive.

Signed-off-by: Roman Zippel <zippel@linux-m68k.org>

---

 include/linux/timex.h |    2 +-
 kernel/timer.c        |   24 ++++++++++++++----------
 2 files changed, 15 insertions(+), 11 deletions(-)

Index: linux-2.6-mm/include/linux/timex.h
===================================================================
--- linux-2.6-mm.orig/include/linux/timex.h	2005-12-21 12:11:48.000000000 +0100
+++ linux-2.6-mm/include/linux/timex.h	2005-12-21 12:11:56.000000000 +0100
@@ -93,7 +93,7 @@
 #define SHIFT_SCALE 22		/* phase scale (shift) */
 #define SHIFT_UPDATE (SHIFT_KG + MAXTC) /* time offset scale (shift) */
 #define SHIFT_USEC 16		/* frequency offset scale (shift) */
-#define FINENSEC (1L << (SHIFT_SCALE - 10)) /* ~1 ns in phase units */
+#define FINENSEC (1L << SHIFT_SCALE) /* ~1 ns in phase units */
 
 #define MAXPHASE 512000L        /* max phase error (us) */
 #define MAXFREQ (512L << SHIFT_USEC)  /* max frequency error (ppm) */
Index: linux-2.6-mm/kernel/timer.c
===================================================================
--- linux-2.6-mm.orig/kernel/timer.c	2005-12-21 12:11:48.000000000 +0100
+++ linux-2.6-mm/kernel/timer.c	2005-12-21 12:11:56.000000000 +0100
@@ -552,6 +552,7 @@ found:
  */
 unsigned long tick_usec = TICK_USEC; 		/* USER_HZ period (usec) */
 unsigned long tick_nsec = TICK_NSEC;		/* ACTHZ period (nsec) */
+static unsigned long tick_nsec_curr = TICK_NSEC;
 
 /* 
  * The current time 
@@ -601,7 +602,7 @@ long time_next_adjust;
  */
 static void second_overflow(void)
 {
-	long ltemp;
+	long ltemp, adj;
 
 	/* Bump the maxerror field */
 	time_maxerror += time_tolerance >> SHIFT_USEC;
@@ -662,6 +663,7 @@ static void second_overflow(void)
 		time_state = TIME_OK;
 	}
 
+	tick_nsec_curr = tick_nsec;
 	/*
 	 * 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
@@ -675,36 +677,38 @@ static void second_overflow(void)
 	ltemp = min(ltemp, (MAXPHASE / MINSEC) << SHIFT_UPDATE);
 	ltemp = max(ltemp, -(MAXPHASE / MINSEC) << SHIFT_UPDATE);
 	time_offset -= ltemp;
-	time_adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
+	adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
 
 	/*
 	 * Compute the frequency estimate and additional phase adjustment due
 	 * to frequency error for the next second.
 	 */
 	ltemp = time_freq;
-	time_adj += shift_right(ltemp,(SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE));
+	adj += shift_right(ltemp,(SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE));
 
 #if HZ == 100
 	/*
 	 * Compensate for (HZ==100) != (1 << SHIFT_HZ).  Add 25% and 3.125% to
 	 * get 128.125; => only 0.125% error (p. 14)
 	 */
-	time_adj += shift_right(time_adj, 2) + shift_right(time_adj, 5);
+	adj += shift_right(adj, 2) + shift_right(adj, 5);
 #endif
 #if HZ == 250
 	/*
 	 * Compensate for (HZ==250) != (1 << SHIFT_HZ).  Add 1.5625% and
 	 * 0.78125% to get 255.85938; => only 0.05% error (p. 14)
 	 */
-	time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
+	adj += shift_right(adj, 6) + shift_right(adj, 7);
 #endif
 #if HZ == 1000
 	/*
 	 * Compensate for (HZ==1000) != (1 << SHIFT_HZ).  Add 1.5625% and
 	 * 0.78125% to get 1023.4375; => only 0.05% error (p. 14)
 	 */
-	time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
+	adj += shift_right(adj, 6) + shift_right(adj, 7);
 #endif
+	tick_nsec_curr += adj >> (SHIFT_SCALE - 10);
+	time_adj = (adj << 10) & (FINENSEC - 1);
 }
 
 /* in the NTP reference this is called "hardclock()" */
@@ -727,15 +731,15 @@ static void update_wall_time_one_tick(vo
 		/* Reduce by this step the amount of time left  */
 		time_adjust -= time_adjust_step;
 	}
-	delta_nsec = tick_nsec + time_adjust_step * 1000;
+	delta_nsec = tick_nsec_curr + 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);
+	if (time_phase >= FINENSEC) {
+		long ltemp = time_phase >> SHIFT_SCALE;
+		time_phase -= ltemp << SHIFT_SCALE;
 		delta_nsec += ltemp;
 	}
 	xtime.tv_nsec += delta_nsec;

Re: [PATCH 2/10] NTP: normalize time_adj

[john stultz]

On Thu, 2005-12-22 at 00:21 +0100, Roman Zippel wrote:
> This normalizes the calculated value time_adj in second_overflow() to be
> always positive. The difference is added to tick_nsec and stored in
> tick_nsec_curr. This simplifies the work needed in
> update_wall_time_one_tick() as time_phase is always positive.
> 
> Signed-off-by: Roman Zippel <zippel@linux-m68k.org>

Ok, trying to look this code over a bit more closely. 

I really think this area of code needs a lot of work, so I really think
your changes here are cool. That said, this code is difficult to review,
mainly because the existing code is so poorly commented (and probably
also because I'm a bit slow). Not your fault at all, but maybe since
you've grokked it well enough to change it, might you help clarify whats
going on as well? Some (likely incorrect) suggestions below.


> ---
> 
>  include/linux/timex.h |    2 +-
>  kernel/timer.c        |   24 ++++++++++++++----------
>  2 files changed, 15 insertions(+), 11 deletions(-)
> 
> Index: linux-2.6-mm/include/linux/timex.h
> ===================================================================
> --- linux-2.6-mm.orig/include/linux/timex.h	2005-12-21 12:11:48.000000000 +0100
> +++ linux-2.6-mm/include/linux/timex.h	2005-12-21 12:11:56.000000000 +0100
> @@ -93,7 +93,7 @@
>  #define SHIFT_SCALE 22		/* phase scale (shift) */
>  #define SHIFT_UPDATE (SHIFT_KG + MAXTC) /* time offset scale (shift) */
>  #define SHIFT_USEC 16		/* frequency offset scale (shift) */
> -#define FINENSEC (1L << (SHIFT_SCALE - 10)) /* ~1 ns in phase units */
> +#define FINENSEC (1L << SHIFT_SCALE) /* ~1 ns in phase units */

So this effectively increases the granularity of the phase units, right?
Or does the comment need changing?


>  #define MAXPHASE 512000L        /* max phase error (us) */
>  #define MAXFREQ (512L << SHIFT_USEC)  /* max frequency error (ppm) */
> Index: linux-2.6-mm/kernel/timer.c
> ===================================================================
> --- linux-2.6-mm.orig/kernel/timer.c	2005-12-21 12:11:48.000000000 +0100
> +++ linux-2.6-mm/kernel/timer.c	2005-12-21 12:11:56.000000000 +0100
> @@ -552,6 +552,7 @@ found:
>   */
>  unsigned long tick_usec = TICK_USEC; 		/* USER_HZ period (usec) */
>  unsigned long tick_nsec = TICK_NSEC;		/* ACTHZ period (nsec) */
> +static unsigned long tick_nsec_curr = TICK_NSEC;
>  
>  /* 
>   * The current time 
> @@ -601,7 +602,7 @@ long time_next_adjust;
>   */
>  static void second_overflow(void)
>  {
> -	long ltemp;
> +	long ltemp, adj;
>  
>  	/* Bump the maxerror field */
>  	time_maxerror += time_tolerance >> SHIFT_USEC;
> @@ -662,6 +663,7 @@ static void second_overflow(void)
>  		time_state = TIME_OK;
>  	}


Maybe:
	/* reset current nsec_per_tick value for the next tick */
> +	tick_nsec_curr = tick_nsec;
>  	/*
>  	 * 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
> @@ -675,36 +677,38 @@ static void second_overflow(void)
>  	ltemp = min(ltemp, (MAXPHASE / MINSEC) << SHIFT_UPDATE);
>  	ltemp = max(ltemp, -(MAXPHASE / MINSEC) << SHIFT_UPDATE);
>  	time_offset -= ltemp;
> -	time_adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
> +	adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);

	That could maybe use a better comment. The larger comment makes it
clear we're converting the usec offset to phase adjustment units, but
maybe something further to explain how usecs -> phase is connected to
multiplying by 2^(SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE) would help?
 
>  	/*
>  	 * Compute the frequency estimate and additional phase adjustment due
>  	 * to frequency error for the next second.
>  	 */
>  	ltemp = time_freq;
> -	time_adj += shift_right(ltemp,(SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE));
> +	adj += shift_right(ltemp,(SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE));

Why not drop ltemp here all together and just use time_freq directly?
Also maybe a brief note about how dividing the shifted ppm frequency by
2^(SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE) converts us to phase units?

>  #if HZ == 100
>  	/*
>  	 * Compensate for (HZ==100) != (1 << SHIFT_HZ).  Add 25% and 3.125% to
>  	 * get 128.125; => only 0.125% error (p. 14)
>  	 */
> -	time_adj += shift_right(time_adj, 2) + shift_right(time_adj, 5);
> +	adj += shift_right(adj, 2) + shift_right(adj, 5);
>  #endif
>  #if HZ == 250
>  	/*
>  	 * Compensate for (HZ==250) != (1 << SHIFT_HZ).  Add 1.5625% and
>  	 * 0.78125% to get 255.85938; => only 0.05% error (p. 14)
>  	 */
> -	time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
> +	adj += shift_right(adj, 6) + shift_right(adj, 7);
>  #endif
>  #if HZ == 1000
>  	/*
>  	 * Compensate for (HZ==1000) != (1 << SHIFT_HZ).  Add 1.5625% and
>  	 * 0.78125% to get 1023.4375; => only 0.05% error (p. 14)
>  	 */
> -	time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
> +	adj += shift_right(adj, 6) + shift_right(adj, 7);
>  #endif
> +	tick_nsec_curr += adj >> (SHIFT_SCALE - 10);
> +	time_adj = (adj << 10) & (FINENSEC - 1);

Again, a comment here would help. 

We use time_adj to increment the phase which will adjust the per-tick
nsec interval in update_wall_time_one_tick, so why are we adjusting
tick_nsec_curr which is used there as well?

Also why SHIFT_SCALE - 10?  And (adj<<10)&(FINSEC -1) looks like magic
to me. :)

>  }
>  
>  /* in the NTP reference this is called "hardclock()" */
> @@ -727,15 +731,15 @@ static void update_wall_time_one_tick(vo
>  		/* Reduce by this step the amount of time left  */
>  		time_adjust -= time_adjust_step;
>  	}
> -	delta_nsec = tick_nsec + time_adjust_step * 1000;
> +	delta_nsec = tick_nsec_curr + 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);
> +	if (time_phase >= FINENSEC) {
> +		long ltemp = time_phase >> SHIFT_SCALE;
> +		time_phase -= ltemp << SHIFT_SCALE;
>  		delta_nsec += ltemp;
>  	}
>  	xtime.tv_nsec += delta_nsec;

Again, same point as the last comment.


I'll try to provide similar comments for the other patches tomorrow.

thanks
-john

Re: [PATCH 2/10] NTP: normalize time_adj

[Roman Zippel]

Hi,

On Tue, 10 Jan 2006, john stultz wrote:

> > Index: linux-2.6-mm/include/linux/timex.h
> > ===================================================================
> > --- linux-2.6-mm.orig/include/linux/timex.h	2005-12-21 12:11:48.000000000 +0100
> > +++ linux-2.6-mm/include/linux/timex.h	2005-12-21 12:11:56.000000000 +0100
> > @@ -93,7 +93,7 @@
> >  #define SHIFT_SCALE 22		/* phase scale (shift) */
> >  #define SHIFT_UPDATE (SHIFT_KG + MAXTC) /* time offset scale (shift) */
> >  #define SHIFT_USEC 16		/* frequency offset scale (shift) */
> > -#define FINENSEC (1L << (SHIFT_SCALE - 10)) /* ~1 ns in phase units */
> > +#define FINENSEC (1L << SHIFT_SCALE) /* ~1 ns in phase units */
> 
> So this effectively increases the granularity of the phase units, right?

Basically yes, but it's part of a small cleanup I forgot to comment. (See 
below)

> > @@ -675,36 +677,38 @@ static void second_overflow(void)
> >  	ltemp = min(ltemp, (MAXPHASE / MINSEC) << SHIFT_UPDATE);
> >  	ltemp = max(ltemp, -(MAXPHASE / MINSEC) << SHIFT_UPDATE);
> >  	time_offset -= ltemp;
> > -	time_adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
> > +	adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
> 
> 	That could maybe use a better comment. The larger comment makes it
> clear we're converting the usec offset to phase adjustment units, but
> maybe something further to explain how usecs -> phase is connected to
> multiplying by 2^(SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE) would help?

I agree that this could use better comments, although some changes are 
only temporary, so some things I'll probably only comment better in the 
changelog.

> >  	 * 0.78125% to get 1023.4375; => only 0.05% error (p. 14)
> >  	 */
> > -	time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
> > +	adj += shift_right(adj, 6) + shift_right(adj, 7);
> >  #endif
> > +	tick_nsec_curr += adj >> (SHIFT_SCALE - 10);
> > +	time_adj = (adj << 10) & (FINENSEC - 1);
> 
> Again, a comment here would help. 
> 
> We use time_adj to increment the phase which will adjust the per-tick
> nsec interval in update_wall_time_one_tick, so why are we adjusting
> tick_nsec_curr which is used there as well?

This is the part which normalizes time_adj, so it's always positive and 
saves two checks in update_wall_time_one_tick().
(BTW in the long term I want to merge these two into a single 64 bit 
variable, but it requires a few more changes.)

> Also why SHIFT_SCALE - 10?  And (adj<<10)&(FINSEC -1) looks like magic
> to me. :)

It's connected to the removed "- 10" above and below, it moves the crude 
usec to nsec conversion (it divides by 1024 instead of 1000) to a single 
spot, so it's easier to remove in a later patch.
I initially wanted to mention this in the changelog, but forgot about it, 
I'll update it.

> >  	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);
> > +	if (time_phase >= FINENSEC) {
> > +		long ltemp = time_phase >> SHIFT_SCALE;
> > +		time_phase -= ltemp << SHIFT_SCALE;
> >  		delta_nsec += ltemp;
> >  	}
> >  	xtime.tv_nsec += delta_nsec;
> 
> Again, same point as the last comment.

See above.

> I'll try to provide similar comments for the other patches tomorrow.

Thanks. :)

bye, Roman