[PATCH] USER_HZ & NTP problems

I've been playing with different HZ values in the 2.4 kernel for a while
now, and apparantly Linus also has decided to introduce a USER_HZ
constant (I used CLOCKS_PER_SEC) while raising the HZ value on x86 to
1000.

On x86 timekeeping has shown to be relative fragile when raising HZ (OK,
I tried HZ=2048 which is quite high) because of the way the interrupt
timer is configured to fire HZ times each second.  This is done by
configuring a divisor in the timer chip (LATCH) which divides a certain
clock (1193180) and makes the chip fire interrupts at the resulting
frequency.

Now comes the catch: NTP requires a clock accuracy of 500 ppm.  For some
HZ values the clock is not accurate enough to meet this requirement,
hence NTP won't work well.

An example HZ value is 1020 which exceeds the 500 ppm requirement.  In
this case the best approximation is 1019.8 Hz.  the xtime.tv_usec value
is raised with a value of 980 each tick which means that after one
second the tv_usec value has increased with 999404 (should be 1000000)
which is an accuracy of 596 ppm.

Some more examples:
	  HZ Accuracy (ppm)
	---- --------------
	 100             17
	1000            151
	1024            632
	2000            687
	2008            343
	2011             18
	2048           1249

What I've been doing is replace tv_usec by tv_nsec, meaning xtime is now
a timespec instead of a timeval.  This allows the accuracy to be
improved by a factor of 1000 for any (well ...  any?) HZ value. 

Of course all kinds of calculations had te be improved as well.  The
ACTHZ constantant is introduced to approximate the actual HZ value, it's
used to do some approximations of other related values. 

2 files changed, 25 insertions, 2 deletions

diff --git a/include/linux/time.h b/include/linux/time.h
index d9f9c6a340d8..088c52d09449 100644
--- a/include/linux/time.h
+++ b/include/linux/time.h
@@ -113,7 +113,7 @@ mktime (unsigned int year, unsigned int mon,
 	)*60 + sec; /* finally seconds */
 }
 
-extern struct timeval xtime;
+extern struct timespec xtime;
 
 #define CURRENT_TIME (xtime.tv_sec)
 
diff --git a/include/linux/timex.h b/include/linux/timex.h
index b82cbdc776f7..5b2b0ac18ae7 100644
--- a/include/linux/timex.h
+++ b/include/linux/timex.h
@@ -155,6 +155,28 @@
 /* LATCH is used in the interval timer and ftape setup. */
 #define LATCH  ((CLOCK_TICK_RATE + HZ/2) / HZ)	/* For divider */
 
+/* Suppose we want to devide two numbers NOM and DEN: NOM/DEN, the we can
+ * improve accuracy by shifting LSH bits, hence calculating:
+ *     (NOM << LSH) / DEN
+ * This however means trouble for large NOM, because (NOM << LSH) may no
+ * longer fit in 32 bits. The following way of calculating this gives us
+ * some slack, under the following onditions:
+ *   - (NOM / DEN) fits in (32 - LSH) bits.
+ *   - (NOM % DEN) fits in (32 - LSH) bits.
+ */
+#define SH_DIV(NOM,DEN,LSH) (   ((NOM / DEN) << LSH)                    \
+                             + (((NOM % DEN) << LSH) + DEN / 2) / DEN)
+
+/* HZ is the requested value. ACTHZ is actual HZ ("<< 8" is for accuracy) */
+#define ACTHZ (SH_DIV (CLOCK_TICK_RATE, LATCH, 8))
+
+/* TICK_USEC is the time between ticks in usec assuming fake USER_HZ */
+#define TICK_USEC ((1000000UL + USER_HZ/2) / USER_HZ)
+
+/* TICK_NSEC is the time between ticks in nsec assuming real ACTHZ and	*/
+/* a value TUSEC for TICK_USEC (can be set bij adjtimex)		*/
+#define TICK_NSEC(TUSEC) (SH_DIV (TUSEC * USER_HZ * 1000, ACTHZ, 8))
+
 /*
  * syscall interface - used (mainly by NTP daemon)
  * to discipline kernel clock oscillator
@@ -251,7 +273,8 @@ struct timex {
  * Note: maximum error = NTP synch distance = dispersion + delay / 2;
  * estimated error = NTP dispersion.
  */
-extern long tick;                      /* timer interrupt period */
+extern unsigned long tick_usec;		/* USER_HZ period (usec) */
+extern unsigned long tick_nsec;		/* ACTHZ          period (nsec) */
 extern int tickadj;			/* amount of adjustment per tick */
 
 /*