[RFC][PATCH] NTP shift_right cleanup (v. A1)

[RFC][PATCH] NTP shift_right cleanup (v. A1)

[john stultz]

All,
        Here is the updated and hopefully uncontroversial cleanup for
the NTP code. It uses min/max to simplify some conditionals and creates
a macro shift_right() that avoids the numerous ugly conditionals in the
NTP code that look like:
        
        if(a < 0)
                b = -(-a >> shift);
        else
                b = a >> shift;

Replacing it with:

        b = shift_right(a, shift);

This should have zero effect on the logic, however it should probably
have a bit of testing just to be sure. I've compiled it for alpha, arm,
i386, ppc, ppc64, and s390 and its been running fine on my laptop all
day. It applies against Linus' tree from this morning.

Also Thanks to Ingo Oeser and YOSHIFUJI Hideaki for catching bugs in
earlier releases.

Please let me know if you have any comments or feedback.


thanks
-john

linux-2.6.14-rc1_ntp-shiftr-cleanup_A1.patch
============================================
diff --git a/include/linux/timex.h b/include/linux/timex.h
--- a/include/linux/timex.h
+++ b/include/linux/timex.h
@@ -282,6 +282,13 @@ static inline int ntp_synced(void)
 	return !(time_status & STA_UNSYNC);
 }
 
+/* Required to safely shift negative values */
+#define shift_right(x, s) ({	\
+	__typeof__(x) __x = x;	\
+	__typeof__(s) __s = s;	\
+	(__x < 0) ? (-((-__x) >> (__s))) : ((__x) >> (__s));	\
+})
+
 
 #ifdef CONFIG_TIME_INTERPOLATION
 
diff --git a/kernel/time.c b/kernel/time.c
--- a/kernel/time.c
+++ b/kernel/time.c
@@ -338,30 +338,20 @@ int do_adjtimex(struct timex *txc)
 		        if (mtemp >= MINSEC) {
 			    ltemp = (time_offset / mtemp) << (SHIFT_USEC -
 							      SHIFT_UPDATE);
-			    if (ltemp < 0)
-			        time_freq -= -ltemp >> SHIFT_KH;
-			    else
-			        time_freq += ltemp >> SHIFT_KH;
+			    time_freq += shift_right(ltemp, SHIFT_KH);
 			} else /* calibration interval too short (p. 12) */
 				result = TIME_ERROR;
 		    } else {	/* PLL mode */
 		        if (mtemp < MAXSEC) {
 			    ltemp *= mtemp;
-			    if (ltemp < 0)
-			        time_freq -= -ltemp >> (time_constant +
-							time_constant +
-							SHIFT_KF - SHIFT_USEC);
-			    else
-			        time_freq += ltemp >> (time_constant +
+			    time_freq += shift_right(ltemp,(time_constant +
 						       time_constant +
-						       SHIFT_KF - SHIFT_USEC);
+						       SHIFT_KF - SHIFT_USEC));
 			} else /* calibration interval too long (p. 12) */
 				result = TIME_ERROR;
 		    }
-		    if (time_freq > time_tolerance)
-		        time_freq = time_tolerance;
-		    else if (time_freq < -time_tolerance)
-		        time_freq = -time_tolerance;
+		    time_freq = min(time_freq, time_tolerance);
+		    time_freq = max(time_freq, -time_tolerance);
 		} /* STA_PLL || STA_PPSTIME */
 	    } /* txc->modes & ADJ_OFFSET */
 	    if (txc->modes & ADJ_TICK) {
@@ -384,10 +374,7 @@ leave:	if ((time_status & (STA_UNSYNC|ST
 	if ((txc->modes & ADJ_OFFSET_SINGLESHOT) == ADJ_OFFSET_SINGLESHOT)
 	    txc->offset	   = save_adjust;
 	else {
-	    if (time_offset < 0)
-		txc->offset = -(-time_offset >> SHIFT_UPDATE);
-	    else
-		txc->offset = time_offset >> SHIFT_UPDATE;
+	    txc->offset = shift_right(time_offset, SHIFT_UPDATE);
 	}
 	txc->freq	   = time_freq + pps_freq;
 	txc->maxerror	   = time_maxerror;
diff --git a/kernel/timer.c b/kernel/timer.c
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -703,23 +703,13 @@ static void second_overflow(void)
      * the adjustment over not more than the number of
      * seconds between updates.
      */
-    if (time_offset < 0) {
-	ltemp = -time_offset;
-	if (!(time_status & STA_FLL))
-	    ltemp >>= SHIFT_KG + time_constant;
-	if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
-	    ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
-	time_offset += ltemp;
-	time_adj = -ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
-    } else {
 	ltemp = time_offset;
 	if (!(time_status & STA_FLL))
-	    ltemp >>= SHIFT_KG + time_constant;
+		ltemp = shift_right(ltemp, SHIFT_KG + time_constant);
 	if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
-	    ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
+		ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
 	time_offset -= ltemp;
 	time_adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
-    }
 
     /*
      * Compute the frequency estimate and additional phase
@@ -736,30 +726,19 @@ static void second_overflow(void)
 			 STA_PPSWANDER | STA_PPSERROR);
     }
     ltemp = time_freq + pps_freq;
-    if (ltemp < 0)
-	time_adj -= -ltemp >>
-	    (SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE);
-    else
-	time_adj += ltemp >>
-	    (SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE);
+    time_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)
      */
-    if (time_adj < 0)
-	time_adj -= (-time_adj >> 2) + (-time_adj >> 5);
-    else
-	time_adj += (time_adj >> 2) + (time_adj >> 5);
+    time_adj += shift_right(time_adj, 2) + shift_right(time_adj, 5);
 #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)
      */
-    if (time_adj < 0)
-	time_adj -= (-time_adj >> 6) + (-time_adj >> 7);
-    else
-	time_adj += (time_adj >> 6) + (time_adj >> 7);
+    time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
 #endif
 }
 
@@ -778,10 +757,8 @@ static void update_wall_time_one_tick(vo
 	     * Limit the amount of the step to be in the range
 	     * -tickadj .. +tickadj
 	     */
-	     if (time_adjust > tickadj)
-		time_adjust_step = tickadj;
-	     else if (time_adjust < -tickadj)
-		time_adjust_step = -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;
@@ -792,13 +769,8 @@ static void update_wall_time_one_tick(vo
 	 * advance the tick more.
 	 */
 	time_phase += time_adj;
-	if (time_phase <= -FINENSEC) {
-		long ltemp = -time_phase >> (SHIFT_SCALE - 10);
-		time_phase += ltemp << (SHIFT_SCALE - 10);
-		delta_nsec -= ltemp;
-	}
-	else if (time_phase >= FINENSEC) {
-		long ltemp = time_phase >> (SHIFT_SCALE - 10);
+	if (abs(time_phase) >= FINENSEC) {
+		long ltemp = shift_right(time_phase, (SHIFT_SCALE - 10));
 		time_phase -= ltemp << (SHIFT_SCALE - 10);
 		delta_nsec += ltemp;
 	}

Re: [RFC][PATCH] NTP shift_right cleanup (v. A1)

[john stultz]

On Wed, 2005-09-14 at 10:48 -0700, john stultz wrote:
> +/* Required to safely shift negative values */
> +#define shift_right(x, s) ({	\
> +	__typeof__(x) __x = x;	\
> +	__typeof__(s) __s = s;	\
> +	(__x < 0) ? (-((-__x) >> (__s))) : ((__x) >> (__s));	\
> +})
> +

Ah, crud. Scratch that. I forgot to check in the paren change suggested
by Roman. A new patch will follow shortly.

thanks
-john

NTP leap second question

[George Anzinger]

It appears that a leap second is scheduled.  One of our customers is 
concerened about his application around this.  Could one of you NTP 
wizards help me to understand NTP a bit better.

First, I wonder if we suppressed the leap second insert and time then 
became out of sync by a second, would NTP "creap" the time back in sync 
or would the one second out of sync cause it to quit?

Assuming NTP would do the "creap" thing, is there a way to tell NTP not 
to insert the leap second?
-- 
George Anzinger   george@mvista.com
HRT (High-res-timers):  http://sourceforge.net/projects/high-res-timers/

Re: NTP leap second question

[john stultz]

On Wed, 2005-09-14 at 11:39 -0700, George Anzinger wrote:
> It appears that a leap second is scheduled.  One of our customers is 
> concerened about his application around this.  Could one of you NTP 
> wizards help me to understand NTP a bit better.

First: I'm not an NTP wizard by any means, but I'll see if I can't help.

> First, I wonder if we suppressed the leap second insert and time then 
> became out of sync by a second, would NTP "creap" the time back in sync 
> or would the one second out of sync cause it to quit?

The ntpd's slew-bound is .125s I believe, so a second offset would cause
ntpd to adjust the time using stime()/settimeofday(). You could run ntpd
with the -x option which forces it to always slew the clock. This
however could cause the initial sync to take quite some time.


> Assuming NTP would do the "creap" thing, is there a way to tell NTP not 
> to insert the leap second?

If I recall, leapsecond implementations are a pretty contentious issue.
Some folks have suggested having the kernels note the leapsecond and
slew the clock internally. This sounds nicer then just adding or
removing a second, but I do not know how that would affect synchronizing
between a number of systems. So I'll defer the larger discussion to the
real NTP wizards.

Re: NTP leap second question

[Ulrich Windl]

On 14 Sep 2005 at 11:54, john stultz wrote:

> On Wed, 2005-09-14 at 11:39 -0700, George Anzinger wrote:
> > It appears that a leap second is scheduled.  One of our customers is 
> > concerened about his application around this.  Could one of you NTP 
> > wizards help me to understand NTP a bit better.
> 
> First: I'm not an NTP wizard by any means, but I'll see if I can't help.
> 
> > First, I wonder if we suppressed the leap second insert and time then 
> > became out of sync by a second, would NTP "creap" the time back in sync 
> > or would the one second out of sync cause it to quit?
> 
> The ntpd's slew-bound is .125s I believe, so a second offset would cause
> ntpd to adjust the time using stime()/settimeofday(). You could run ntpd
> with the -x option which forces it to always slew the clock. This
> however could cause the initial sync to take quite some time.
> 
> 
> > Assuming NTP would do the "creap" thing, is there a way to tell NTP not 
> > to insert the leap second?
> 
> If I recall, leapsecond implementations are a pretty contentious issue.
> Some folks have suggested having the kernels note the leapsecond and
> slew the clock internally. This sounds nicer then just adding or

No! Never slew a leap second: It will take too long! It's all over after one 
second. If you slew, you time will be incorrect for an extended time.

Ulrich


> removing a second, but I do not know how that would affect synchronizing
> between a number of systems. So I'll defer the larger discussion to the
> real NTP wizards.
> 

Re: NTP leap second question

[Kyle Moffett]

On Sep 15, 2005, at 02:49:21, Ulrich Windl wrote:
> On 14 Sep 2005 at 11:54, john stultz wrote:
>> If I recall, leapsecond implementations are a pretty contentious  
>> issue.  Some folks have suggested having the kernels note the  
>> leapsecond and slew the clock internally. This sounds nicer then  
>> just adding or
>
> No! Never slew a leap second: It will take too long! It's all over  
> after one second. If you slew, you time will be incorrect for an  
> extended time.

I think he said "It's a contentious issue", and "Some have  
suggested".  No need to get your underwear in a bunch over it.  There  
are arguments for both sides.  Besides, it's not like it matters much  
in the grand scheme of things, it's only a second.  With the current  
proposals, the leap-second-slewing would only be in effect for 1000  
seconds, and you'd never be very far off true time (The simplest  
implementation is one second off, if you add one bit of state you'll  
only ever be a half-second off).  If you're willing to make it a bit  
slower and a bit more code, you could even make the slewing nonlinear  
with a continuous derivative, so it's only in place for ~20 seconds,  
and only changes rapidly near the leapsecond boundary itself.  On the  
other hand, if your box is running a nuclear reactor, you might want  
to do a bit more verification, but Linux isn't certified for that  
anyways!! :-D

Cheers,
Kyle Moffett

--
Simple things should be simple and complex things should be possible
   -- Alan Kay

Re: NTP leap second question

[Alan Cox]

On Iau, 2005-09-15 at 13:21 -0400, Kyle Moffett wrote:
> only ever be a half-second off).  If you're willing to make it a bit  
> slower and a bit more code, you could even make the slewing nonlinear  
> with a continuous derivative, so it's only in place for ~20 seconds,  

It all depends what time you are using and how you are using it. There
isn't one time system and assuming there is makes all the mess.

Your kernel time ticks along at a steady rate based on a fixed period
second where that period hopefully is a passable approximation of the
rate of progression of time measured by a big pile of cæsium atomic
clocks and defined in terms of atomic radiation.

UTC (civilian time) effectively follows rotations of the earth but using
fixed interval seconds. The rotation is a bit variable so 'leap seconds'
are inserted to keep the two within 1 second of one another.  A seperate
standard (UT1) computes a 'universal' measure of earth rotation as UT0
(true earth rotation) is dependant on where you are (because the poles
wobble). And you can measure time with seconds defined as a fraction of
an earth rotation (ie variable length seconds) which is what in reality
most people use and think.

In other words, you need to decide what you are measuring before you
decide how to measure it. If you wish to record the point at which an
event occurred in civilian time then UTC is correct. If you wish to
measure the duration elapsed between two points in time then TAI (or raw
time_t) is probably more useful.

If you are recording events to some legally defined standard you have to
go read what the government has inflicted on your radio station/telco
etc and follow that.

Glibc will do the conversion work for you providing your timezone
database is kept up to date.

Alan

Re: [RFC][PATCH] NTP shift_right cleanup (v. A1)

[Roman Zippel]

Hi,

On Wed, 14 Sep 2005, john stultz wrote:

> +/* Required to safely shift negative values */
> +#define shift_right(x, s) ({	\
> +	__typeof__(x) __x = x;	\
> +	__typeof__(s) __s = s;	\
> +	(__x < 0) ? (-((-__x) >> (__s))) : ((__x) >> (__s));	\
> +})

Still too much/little parenthesis.

> @@ -792,13 +769,8 @@ static void update_wall_time_one_tick(vo
>  	 * advance the tick more.
>  	 */
>  	time_phase += time_adj;
> -	if (time_phase <= -FINENSEC) {
> -		long ltemp = -time_phase >> (SHIFT_SCALE - 10);
> -		time_phase += ltemp << (SHIFT_SCALE - 10);
> -		delta_nsec -= ltemp;
> -	}
> -	else if (time_phase >= FINENSEC) {
> -		long ltemp = time_phase >> (SHIFT_SCALE - 10);
> +	if (abs(time_phase) >= FINENSEC) {
> +		long ltemp = shift_right(time_phase, (SHIFT_SCALE - 10));
>  		time_phase -= ltemp << (SHIFT_SCALE - 10);
>  		delta_nsec += ltemp;
>  	}

I checked and this actually generates worse code.

bye, Roman

Re: [RFC][PATCH] NTP shift_right cleanup (v. A1)

[john stultz]

On Wed, 2005-09-14 at 20:13 +0200, Roman Zippel wrote:
> > @@ -792,13 +769,8 @@ static void update_wall_time_one_tick(vo
> >  	 * advance the tick more.
> >  	 */
> >  	time_phase += time_adj;
> > -	if (time_phase <= -FINENSEC) {
> > -		long ltemp = -time_phase >> (SHIFT_SCALE - 10);
> > -		time_phase += ltemp << (SHIFT_SCALE - 10);
> > -		delta_nsec -= ltemp;
> > -	}
> > -	else if (time_phase >= FINENSEC) {
> > -		long ltemp = time_phase >> (SHIFT_SCALE - 10);
> > +	if (abs(time_phase) >= FINENSEC) {
> > +		long ltemp = shift_right(time_phase, (SHIFT_SCALE - 10));
> >  		time_phase -= ltemp << (SHIFT_SCALE - 10);
> >  		delta_nsec += ltemp;
> >  	}
> 
> I checked and this actually generates worse code.

Well, if I drop the abs() and use:
	if ((time_phase >= FINENSEC) || (time_phase <= -FINENSEC))

It looks pretty close in my test. Is that cool with you?

thanks
-john

Re: [RFC][PATCH] NTP shift_right cleanup (v. A1)

[Roman Zippel]

Hi,

On Wed, 14 Sep 2005, john stultz wrote:

> > I checked and this actually generates worse code.
> 
> Well, if I drop the abs() and use:
> 	if ((time_phase >= FINENSEC) || (time_phase <= -FINENSEC))
> 
> It looks pretty close in my test. Is that cool with you?

I think it doesn't hurt to keep it for now, there are other ways to get 
rid of it (e.g. reducing tick_nsec so time_adj is always positive).

bye, Roman

[RFC][PATCH] NTP shift_right cleanup (v. A2)

[john stultz]

On Wed, 2005-09-14 at 10:48 -0700, john stultz wrote:
> All,
>         Here is the updated and hopefully uncontroversial cleanup for
> the NTP code. It uses min/max to simplify some conditionals and creates
> a macro shift_right() that avoids the numerous ugly conditionals in the
> NTP code that look like:
>         
>         if(a < 0)
>                 b = -(-a >> shift);
>         else
>                 b = a >> shift;
> 
> Replacing it with:
> 
>         b = shift_right(a, shift);
> 
> This should have zero effect on the logic, however it should probably
> have a bit of testing just to be sure. 

Here is the updated patch with Roman's parens suggestion. Additionally I
removed the use of abs() to address Roman's optimization concerns.

Once again, let me know if you have any suggestions or objections before
I send it to Andrew for more testing.

thanks
-john

 include/linux/timex.h |    7 +++++++
 kernel/time.c         |   25 ++++++-------------------
 kernel/timer.c        |   46 +++++++++-------------------------------------
 3 files changed, 22 insertions(+), 56 deletions(-)


linux-2.6.14-rc1_ntp-shiftR-cleanup_A2.patch
============================================
diff --git a/include/linux/timex.h b/include/linux/timex.h
--- a/include/linux/timex.h
+++ b/include/linux/timex.h
@@ -282,6 +282,13 @@ static inline int ntp_synced(void)
 	return !(time_status & STA_UNSYNC);
 }
 
+/* Required to safely shift negative values */
+#define shift_right(x, s) ({	\
+	__typeof__(x) __x = (x);	\
+	__typeof__(s) __s = (s);	\
+	__x < 0 ? -(-__x >> __s) : __x >> __s;	\
+})
+
 
 #ifdef CONFIG_TIME_INTERPOLATION
 
diff --git a/kernel/time.c b/kernel/time.c
--- a/kernel/time.c
+++ b/kernel/time.c
@@ -338,30 +338,20 @@ int do_adjtimex(struct timex *txc)
 		        if (mtemp >= MINSEC) {
 			    ltemp = (time_offset / mtemp) << (SHIFT_USEC -
 							      SHIFT_UPDATE);
-			    if (ltemp < 0)
-			        time_freq -= -ltemp >> SHIFT_KH;
-			    else
-			        time_freq += ltemp >> SHIFT_KH;
+			    time_freq += shift_right(ltemp, SHIFT_KH);
 			} else /* calibration interval too short (p. 12) */
 				result = TIME_ERROR;
 		    } else {	/* PLL mode */
 		        if (mtemp < MAXSEC) {
 			    ltemp *= mtemp;
-			    if (ltemp < 0)
-			        time_freq -= -ltemp >> (time_constant +
-							time_constant +
-							SHIFT_KF - SHIFT_USEC);
-			    else
-			        time_freq += ltemp >> (time_constant +
+			    time_freq += shift_right(ltemp,(time_constant +
 						       time_constant +
-						       SHIFT_KF - SHIFT_USEC);
+						       SHIFT_KF - SHIFT_USEC));
 			} else /* calibration interval too long (p. 12) */
 				result = TIME_ERROR;
 		    }
-		    if (time_freq > time_tolerance)
-		        time_freq = time_tolerance;
-		    else if (time_freq < -time_tolerance)
-		        time_freq = -time_tolerance;
+		    time_freq = min(time_freq, time_tolerance);
+		    time_freq = max(time_freq, -time_tolerance);
 		} /* STA_PLL || STA_PPSTIME */
 	    } /* txc->modes & ADJ_OFFSET */
 	    if (txc->modes & ADJ_TICK) {
@@ -384,10 +374,7 @@ leave:	if ((time_status & (STA_UNSYNC|ST
 	if ((txc->modes & ADJ_OFFSET_SINGLESHOT) == ADJ_OFFSET_SINGLESHOT)
 	    txc->offset	   = save_adjust;
 	else {
-	    if (time_offset < 0)
-		txc->offset = -(-time_offset >> SHIFT_UPDATE);
-	    else
-		txc->offset = time_offset >> SHIFT_UPDATE;
+	    txc->offset = shift_right(time_offset, SHIFT_UPDATE);
 	}
 	txc->freq	   = time_freq + pps_freq;
 	txc->maxerror	   = time_maxerror;
diff --git a/kernel/timer.c b/kernel/timer.c
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -703,23 +703,13 @@ static void second_overflow(void)
      * the adjustment over not more than the number of
      * seconds between updates.
      */
-    if (time_offset < 0) {
-	ltemp = -time_offset;
-	if (!(time_status & STA_FLL))
-	    ltemp >>= SHIFT_KG + time_constant;
-	if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
-	    ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
-	time_offset += ltemp;
-	time_adj = -ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
-    } else {
 	ltemp = time_offset;
 	if (!(time_status & STA_FLL))
-	    ltemp >>= SHIFT_KG + time_constant;
+		ltemp = shift_right(ltemp, SHIFT_KG + time_constant);
 	if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
-	    ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
+		ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
 	time_offset -= ltemp;
 	time_adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
-    }
 
     /*
      * Compute the frequency estimate and additional phase
@@ -736,30 +726,19 @@ static void second_overflow(void)
 			 STA_PPSWANDER | STA_PPSERROR);
     }
     ltemp = time_freq + pps_freq;
-    if (ltemp < 0)
-	time_adj -= -ltemp >>
-	    (SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE);
-    else
-	time_adj += ltemp >>
-	    (SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE);
+    time_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)
      */
-    if (time_adj < 0)
-	time_adj -= (-time_adj >> 2) + (-time_adj >> 5);
-    else
-	time_adj += (time_adj >> 2) + (time_adj >> 5);
+    time_adj += shift_right(time_adj, 2) + shift_right(time_adj, 5);
 #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)
      */
-    if (time_adj < 0)
-	time_adj -= (-time_adj >> 6) + (-time_adj >> 7);
-    else
-	time_adj += (time_adj >> 6) + (time_adj >> 7);
+    time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
 #endif
 }
 
@@ -778,10 +757,8 @@ static void update_wall_time_one_tick(vo
 	     * Limit the amount of the step to be in the range
 	     * -tickadj .. +tickadj
 	     */
-	     if (time_adjust > tickadj)
-		time_adjust_step = tickadj;
-	     else if (time_adjust < -tickadj)
-		time_adjust_step = -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;
@@ -792,13 +769,8 @@ static void update_wall_time_one_tick(vo
 	 * advance the tick more.
 	 */
 	time_phase += time_adj;
-	if (time_phase <= -FINENSEC) {
-		long ltemp = -time_phase >> (SHIFT_SCALE - 10);
-		time_phase += ltemp << (SHIFT_SCALE - 10);
-		delta_nsec -= ltemp;
-	}
-	else if (time_phase >= FINENSEC) {
-		long ltemp = time_phase >> (SHIFT_SCALE - 10);
+	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;
 	}

[PATCH] NTP shift_right cleanup (v. A2)

[john stultz]

On Wed, 2005-09-14 at 10:48 -0700, john stultz wrote:
> All,
>         Here is the updated and hopefully uncontroversial cleanup for
> the NTP code. It uses min/max to simplify some conditionals and creates
> a macro shift_right() that avoids the numerous ugly conditionals in the
> NTP code that look like:
>         
>         if(a < 0)
>                 b = -(-a >> shift);
>         else
>                 b = a >> shift;
> 
> Replacing it with:
> 
>         b = shift_right(a, shift);
> 
> This should have zero effect on the logic, however it should probably
> have a bit of testing just to be sure. 

Andrew, All,

Here is the updated patch with Roman's parens suggestion. Additionally I
removed the use of abs() to address Roman's optimization concerns.

Andrew, Please consider for inclusion into your tree.

thanks
-john

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

 include/linux/timex.h |    7 +++++++
 kernel/time.c         |   25 ++++++-------------------
 kernel/timer.c        |   46 +++++++++-------------------------------------
 3 files changed, 22 insertions(+), 56 deletions(-)

linux-2.6.14-rc1_ntp-shiftR-cleanup_A2.patch
============================================
diff --git a/include/linux/timex.h b/include/linux/timex.h
--- a/include/linux/timex.h
+++ b/include/linux/timex.h
@@ -282,6 +282,13 @@ static inline int ntp_synced(void)
 	return !(time_status & STA_UNSYNC);
 }
 
+/* Required to safely shift negative values */
+#define shift_right(x, s) ({	\
+	__typeof__(x) __x = (x);	\
+	__typeof__(s) __s = (s);	\
+	__x < 0 ? -(-__x >> __s) : __x >> __s;	\
+})
+
 
 #ifdef CONFIG_TIME_INTERPOLATION
 
diff --git a/kernel/time.c b/kernel/time.c
--- a/kernel/time.c
+++ b/kernel/time.c
@@ -338,30 +338,20 @@ int do_adjtimex(struct timex *txc)
 		        if (mtemp >= MINSEC) {
 			    ltemp = (time_offset / mtemp) << (SHIFT_USEC -
 							      SHIFT_UPDATE);
-			    if (ltemp < 0)
-			        time_freq -= -ltemp >> SHIFT_KH;
-			    else
-			        time_freq += ltemp >> SHIFT_KH;
+			    time_freq += shift_right(ltemp, SHIFT_KH);
 			} else /* calibration interval too short (p. 12) */
 				result = TIME_ERROR;
 		    } else {	/* PLL mode */
 		        if (mtemp < MAXSEC) {
 			    ltemp *= mtemp;
-			    if (ltemp < 0)
-			        time_freq -= -ltemp >> (time_constant +
-							time_constant +
-							SHIFT_KF - SHIFT_USEC);
-			    else
-			        time_freq += ltemp >> (time_constant +
+			    time_freq += shift_right(ltemp,(time_constant +
 						       time_constant +
-						       SHIFT_KF - SHIFT_USEC);
+						       SHIFT_KF - SHIFT_USEC));
 			} else /* calibration interval too long (p. 12) */
 				result = TIME_ERROR;
 		    }
-		    if (time_freq > time_tolerance)
-		        time_freq = time_tolerance;
-		    else if (time_freq < -time_tolerance)
-		        time_freq = -time_tolerance;
+		    time_freq = min(time_freq, time_tolerance);
+		    time_freq = max(time_freq, -time_tolerance);
 		} /* STA_PLL || STA_PPSTIME */
 	    } /* txc->modes & ADJ_OFFSET */
 	    if (txc->modes & ADJ_TICK) {
@@ -384,10 +374,7 @@ leave:	if ((time_status & (STA_UNSYNC|ST
 	if ((txc->modes & ADJ_OFFSET_SINGLESHOT) == ADJ_OFFSET_SINGLESHOT)
 	    txc->offset	   = save_adjust;
 	else {
-	    if (time_offset < 0)
-		txc->offset = -(-time_offset >> SHIFT_UPDATE);
-	    else
-		txc->offset = time_offset >> SHIFT_UPDATE;
+	    txc->offset = shift_right(time_offset, SHIFT_UPDATE);
 	}
 	txc->freq	   = time_freq + pps_freq;
 	txc->maxerror	   = time_maxerror;
diff --git a/kernel/timer.c b/kernel/timer.c
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -703,23 +703,13 @@ static void second_overflow(void)
      * the adjustment over not more than the number of
      * seconds between updates.
      */
-    if (time_offset < 0) {
-	ltemp = -time_offset;
-	if (!(time_status & STA_FLL))
-	    ltemp >>= SHIFT_KG + time_constant;
-	if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
-	    ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
-	time_offset += ltemp;
-	time_adj = -ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
-    } else {
 	ltemp = time_offset;
 	if (!(time_status & STA_FLL))
-	    ltemp >>= SHIFT_KG + time_constant;
+		ltemp = shift_right(ltemp, SHIFT_KG + time_constant);
 	if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
-	    ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
+		ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
 	time_offset -= ltemp;
 	time_adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
-    }
 
     /*
      * Compute the frequency estimate and additional phase
@@ -736,30 +726,19 @@ static void second_overflow(void)
 			 STA_PPSWANDER | STA_PPSERROR);
     }
     ltemp = time_freq + pps_freq;
-    if (ltemp < 0)
-	time_adj -= -ltemp >>
-	    (SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE);
-    else
-	time_adj += ltemp >>
-	    (SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE);
+    time_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)
      */
-    if (time_adj < 0)
-	time_adj -= (-time_adj >> 2) + (-time_adj >> 5);
-    else
-	time_adj += (time_adj >> 2) + (time_adj >> 5);
+    time_adj += shift_right(time_adj, 2) + shift_right(time_adj, 5);
 #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)
      */
-    if (time_adj < 0)
-	time_adj -= (-time_adj >> 6) + (-time_adj >> 7);
-    else
-	time_adj += (time_adj >> 6) + (time_adj >> 7);
+    time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
 #endif
 }
 
@@ -778,10 +757,8 @@ static void update_wall_time_one_tick(vo
 	     * Limit the amount of the step to be in the range
 	     * -tickadj .. +tickadj
 	     */
-	     if (time_adjust > tickadj)
-		time_adjust_step = tickadj;
-	     else if (time_adjust < -tickadj)
-		time_adjust_step = -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;
@@ -792,13 +769,8 @@ static void update_wall_time_one_tick(vo
 	 * advance the tick more.
 	 */
 	time_phase += time_adj;
-	if (time_phase <= -FINENSEC) {
-		long ltemp = -time_phase >> (SHIFT_SCALE - 10);
-		time_phase += ltemp << (SHIFT_SCALE - 10);
-		delta_nsec -= ltemp;
-	}
-	else if (time_phase >= FINENSEC) {
-		long ltemp = time_phase >> (SHIFT_SCALE - 10);
+	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;
 	}

[PATCH] NTP shift_right cleanup (v. A3)

[john stultz]

Andrew,
	After some close scrutiny I found a mistake in the A2 version of this
patch. I guess it just goes to prove how difficult to read the current
code is. 


In one part of the old patch, a nested if stated:

       if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
               ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;

However that only bounds ltemp if it is positive, when the current
mainline code bounds it if it is negative as well. Replacing the above
with:

       ltemp = min(ltemp, (MAXPHASE / MINSEC) << SHIFT_UPDATE);
       ltemp = max(ltemp, -(MAXPHASE / MINSEC) << SHIFT_UPDATE);

Corrects the issue.

Below is the corrected patch which should replace the
ntp-shift_right-cleanup.patch file in your tree.

Thanks
-john


Create a macro shift_right() that avoids the numerous ugly conditionals
in the NTP code that look like:

        if(a < 0)
                b = -(-a >> shift);
        else
                b = a >> shift;

Replacing it with:

        b = shift_right(a, shift);

This should have zero effect on the logic, however it should probably
have a bit of testing just to be sure.

Also replace open-coded min/max with the macros.

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

 include/linux/timex.h |    7 +++++++
 kernel/time.c         |   25 ++++++-------------------
 kernel/timer.c        |   48 ++++++++++--------------------------------------
 3 files changed, 23 insertions(+), 57 deletions(-)

diff --git a/include/linux/timex.h b/include/linux/timex.h
--- a/include/linux/timex.h
+++ b/include/linux/timex.h
@@ -282,6 +282,13 @@ static inline int ntp_synced(void)
 	return !(time_status & STA_UNSYNC);
 }
 
+/* Required to safely shift negative values */
+#define shift_right(x, s) ({	\
+	__typeof__(x) __x = (x);	\
+	__typeof__(s) __s = (s);	\
+	__x < 0 ? -(-__x >> __s) : __x >> __s;	\
+})
+
 
 #ifdef CONFIG_TIME_INTERPOLATION
 
diff --git a/kernel/time.c b/kernel/time.c
--- a/kernel/time.c
+++ b/kernel/time.c
@@ -338,30 +338,20 @@ int do_adjtimex(struct timex *txc)
 		        if (mtemp >= MINSEC) {
 			    ltemp = (time_offset / mtemp) << (SHIFT_USEC -
 							      SHIFT_UPDATE);
-			    if (ltemp < 0)
-			        time_freq -= -ltemp >> SHIFT_KH;
-			    else
-			        time_freq += ltemp >> SHIFT_KH;
+			    time_freq += shift_right(ltemp, SHIFT_KH);
 			} else /* calibration interval too short (p. 12) */
 				result = TIME_ERROR;
 		    } else {	/* PLL mode */
 		        if (mtemp < MAXSEC) {
 			    ltemp *= mtemp;
-			    if (ltemp < 0)
-			        time_freq -= -ltemp >> (time_constant +
-							time_constant +
-							SHIFT_KF - SHIFT_USEC);
-			    else
-			        time_freq += ltemp >> (time_constant +
+			    time_freq += shift_right(ltemp,(time_constant +
 						       time_constant +
-						       SHIFT_KF - SHIFT_USEC);
+						       SHIFT_KF - SHIFT_USEC));
 			} else /* calibration interval too long (p. 12) */
 				result = TIME_ERROR;
 		    }
-		    if (time_freq > time_tolerance)
-		        time_freq = time_tolerance;
-		    else if (time_freq < -time_tolerance)
-		        time_freq = -time_tolerance;
+		    time_freq = min(time_freq, time_tolerance);
+		    time_freq = max(time_freq, -time_tolerance);
 		} /* STA_PLL || STA_PPSTIME */
 	    } /* txc->modes & ADJ_OFFSET */
 	    if (txc->modes & ADJ_TICK) {
@@ -384,10 +374,7 @@ leave:	if ((time_status & (STA_UNSYNC|ST
 	if ((txc->modes & ADJ_OFFSET_SINGLESHOT) == ADJ_OFFSET_SINGLESHOT)
 	    txc->offset	   = save_adjust;
 	else {
-	    if (time_offset < 0)
-		txc->offset = -(-time_offset >> SHIFT_UPDATE);
-	    else
-		txc->offset = time_offset >> SHIFT_UPDATE;
+	    txc->offset = shift_right(time_offset, SHIFT_UPDATE);
 	}
 	txc->freq	   = time_freq + pps_freq;
 	txc->maxerror	   = time_maxerror;
diff --git a/kernel/timer.c b/kernel/timer.c
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -703,23 +703,13 @@ static void second_overflow(void)
      * the adjustment over not more than the number of
      * seconds between updates.
      */
-    if (time_offset < 0) {
-	ltemp = -time_offset;
-	if (!(time_status & STA_FLL))
-	    ltemp >>= SHIFT_KG + time_constant;
-	if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
-	    ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
-	time_offset += ltemp;
-	time_adj = -ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
-    } else {
 	ltemp = time_offset;
 	if (!(time_status & STA_FLL))
-	    ltemp >>= SHIFT_KG + time_constant;
-	if (ltemp > (MAXPHASE / MINSEC) << SHIFT_UPDATE)
-	    ltemp = (MAXPHASE / MINSEC) << SHIFT_UPDATE;
+		ltemp = shift_right(ltemp, SHIFT_KG + time_constant);
+	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);
-    }
 
     /*
      * Compute the frequency estimate and additional phase
@@ -736,30 +726,19 @@ static void second_overflow(void)
 			 STA_PPSWANDER | STA_PPSERROR);
     }
     ltemp = time_freq + pps_freq;
-    if (ltemp < 0)
-	time_adj -= -ltemp >>
-	    (SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE);
-    else
-	time_adj += ltemp >>
-	    (SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE);
+    time_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)
      */
-    if (time_adj < 0)
-	time_adj -= (-time_adj >> 2) + (-time_adj >> 5);
-    else
-	time_adj += (time_adj >> 2) + (time_adj >> 5);
+    time_adj += shift_right(time_adj, 2) + shift_right(time_adj, 5);
 #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)
      */
-    if (time_adj < 0)
-	time_adj -= (-time_adj >> 6) + (-time_adj >> 7);
-    else
-	time_adj += (time_adj >> 6) + (time_adj >> 7);
+    time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
 #endif
 }
 
@@ -778,10 +757,8 @@ static void update_wall_time_one_tick(vo
 	     * Limit the amount of the step to be in the range
 	     * -tickadj .. +tickadj
 	     */
-	     if (time_adjust > tickadj)
-		time_adjust_step = tickadj;
-	     else if (time_adjust < -tickadj)
-		time_adjust_step = -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;
@@ -792,13 +769,8 @@ static void update_wall_time_one_tick(vo
 	 * advance the tick more.
 	 */
 	time_phase += time_adj;
-	if (time_phase <= -FINENSEC) {
-		long ltemp = -time_phase >> (SHIFT_SCALE - 10);
-		time_phase += ltemp << (SHIFT_SCALE - 10);
-		delta_nsec -= ltemp;
-	}
-	else if (time_phase >= FINENSEC) {
-		long ltemp = time_phase >> (SHIFT_SCALE - 10);
+	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;
 	}

Re: [PATCH] NTP shift_right cleanup (v. A3)

[Nick Piggin]

john stultz wrote:

> 
>+/* Required to safely shift negative values */
>+#define shift_right(x, s) ({	\
>+	__typeof__(x) __x = (x);	\
>+	__typeof__(s) __s = (s);	\
>+	__x < 0 ? -(-__x >> __s) : __x >> __s;	\
>+})
>+
>

I'd hate to be the one to make you do another version of this ;)

However, how about having something more descriptive than shift_right?
signed_shift_right / shift_right_signed, maybe?

Nick


Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] NTP shift_right cleanup (v. A3)

[Ulrich Windl]

On 21 Sep 2005 at 15:24, Nick Piggin wrote:

> john stultz wrote:
> 
> > 
> >+/* Required to safely shift negative values */
> >+#define shift_right(x, s) ({	\
> >+	__typeof__(x) __x = (x);	\
> >+	__typeof__(s) __s = (s);	\
> >+	__x < 0 ? -(-__x >> __s) : __x >> __s;	\
> >+})
> >+
> >
> 
> I'd hate to be the one to make you do another version of this ;)
> 
> However, how about having something more descriptive than shift_right?
> signed_shift_right / shift_right_signed, maybe?

Hi,

I'm against "signed shift right", because the reason for the macro is exaclty that 
CPUs do a "signed" shift right. John does a "signum(arg) * right_shift(abs(arg), 
number_of_positions)". So maybe it's the signed_unsigned_shift_right(), susr() to 
be cryptic ;-)

I'm only surprised that there are many places where such a routine is needed, and 
still it's missing in sime bitops.h #include.

Regards,
Ulrich

Re: [PATCH] NTP shift_right cleanup (v. A3)

[Nick Piggin]

Ulrich Windl wrote:

> 
> Hi,
> 
> I'm against "signed shift right", because the reason for the macro is exaclty that 
> CPUs do a "signed" shift right. John does a "signum(arg) * right_shift(abs(arg), 
> number_of_positions)". So maybe it's the signed_unsigned_shift_right(), susr() to 
> be cryptic ;-)
> 

I see, so that would be a divide by 2^shift?

Well, nevermind - I guess the patch is better than what was
there before.

-- 
SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] NTP shift_right cleanup (v. A3)

[linux]

- For fixed shifts, you can just write it as a divide; GCC will DTRT.
  For interest's sake, GCC 4.0 generates, for x /= 64:
        testl   %eax, %eax
	jns	.L2
	addl	$63, %eax
.L2:
	sarl	$6, %eax

- If you want to be more verbose with the explanation, try something like:
  (Public domain, copyright abandoned, use freely, yadda yadda.)
/*
 * NTP uses power-of-two divides a lot for speed, but it wants to use
 * negative numbers.
 * 1) ANSI C does not guarantee signed right shifts (but GCC does)
 * 2) Such a shift is like a divide that rounds to -infinity.
 *    NTP wants rounding to zero, i.e. -3/2 = -2, while -3>>1 = -2.
 */

Interestingly, _Hacker's Delight_ chapter 10 skips over this particular
case, signed division by a variable power of two.