Revise timercounters to use binary fixed point format internally.

The binary format "bintime" is a 32.64 format, it will go to 64.64
when time_t does.

The bintime format is available to consumers of time in the kernel,
and is preferable where timeintervals needs to be accumulated.

This change simplifies much of the magic math inside the timecounters
and improves the frequency and time precision by a couple of bits.

I have not been able to measure a performance difference which was not
a tiny fraction of the standard deviation on the measurements.

4 files changed, 171 insertions, 115 deletions

diff --git a/sys/kern/kern_ntptime.c b/sys/kern/kern_ntptime.c
index 4701d2f..91daee0 100644
--- a/sys/kern/kern_ntptime.c
+++ b/sys/kern/kern_ntptime.c
@@ -439,7 +439,7 @@ ntp_update_second(struct timecounter *tcp)
 	u_int32_t *newsec;
 	l_fp ftemp;		/* 32/64-bit temporary */
 
-	newsec = &tcp->tc_offset_sec;
+	newsec = &tcp->tc_offset.sec;
 	/*
 	 * On rollover of the second both the nanosecond and microsecond
 	 * clocks are updated and the state machine cranked as
diff --git a/sys/kern/kern_tc.c b/sys/kern/kern_tc.c
index fa1832a..71b9e5a 100644
--- a/sys/kern/kern_tc.c
+++ b/sys/kern/kern_tc.c
@@ -35,6 +35,7 @@ static __inline unsigned tco_delta __P((struct timecounter *tc));
 
 time_t time_second;
 
+struct	bintime boottimebin;
 struct	timeval boottime;
 SYSCTL_STRUCT(_kern, KERN_BOOTTIME, boottime, CTLFLAG_RD,
     &boottime, timeval, "System boottime");
@@ -102,6 +103,24 @@ tco_delta(struct timecounter *tc)
  */
 
 void
+binuptime(struct bintime *bt)
+{
+	struct timecounter *tc;
+
+	tc = timecounter;
+	*bt = tc->tc_offset;
+	bintime_addx(bt, tc->tc_scale * tco_delta(tc));
+}
+
+void
+bintime(struct bintime *bt)
+{
+
+	binuptime(bt);
+	bintime_add(bt, &boottimebin);
+}
+
+void
 getmicrotime(struct timeval *tvp)
 {
 	struct timecounter *tc;
@@ -124,43 +143,21 @@ getnanotime(struct timespec *tsp)
 void
 microtime(struct timeval *tv)
 {
-	struct timecounter *tc;
+	struct bintime bt;
 
 	nmicrotime++;
-	tc = timecounter;
-	tv->tv_sec = tc->tc_offset_sec;
-	tv->tv_usec = tc->tc_offset_micro;
-	tv->tv_usec += ((u_int64_t)tco_delta(tc) * tc->tc_scale_micro) >> 32;
-	tv->tv_usec += boottime.tv_usec;
-	tv->tv_sec += boottime.tv_sec;
-	while (tv->tv_usec >= 1000000) {
-		tv->tv_usec -= 1000000;
-		tv->tv_sec++;
-	}
+	bintime(&bt);
+	bintime2timeval(&bt, tv);
 }
 
 void
 nanotime(struct timespec *ts)
 {
-	unsigned count;
-	u_int64_t delta;
-	struct timecounter *tc;
+	struct bintime bt;
 
 	nnanotime++;
-	tc = timecounter;
-	ts->tv_sec = tc->tc_offset_sec;
-	count = tco_delta(tc);
-	delta = tc->tc_offset_nano;
-	delta += ((u_int64_t)count * tc->tc_scale_nano_f);
-	delta >>= 32;
-	delta += ((u_int64_t)count * tc->tc_scale_nano_i);
-	delta += boottime.tv_usec * 1000;
-	ts->tv_sec += boottime.tv_sec;
-	while (delta >= 1000000000) {
-		delta -= 1000000000;
-		ts->tv_sec++;
-	}
-	ts->tv_nsec = delta;
+	bintime(&bt);
+	bintime2timespec(&bt, ts);
 }
 
 void
@@ -170,8 +167,7 @@ getmicrouptime(struct timeval *tvp)
 
 	ngetmicrouptime++;
 	tc = timecounter;
-	tvp->tv_sec = tc->tc_offset_sec;
-	tvp->tv_usec = tc->tc_offset_micro;
+	bintime2timeval(&tc->tc_offset, tvp);
 }
 
 void
@@ -181,46 +177,27 @@ getnanouptime(struct timespec *tsp)
 
 	ngetnanouptime++;
 	tc = timecounter;
-	tsp->tv_sec = tc->tc_offset_sec;
-	tsp->tv_nsec = tc->tc_offset_nano >> 32;
+	bintime2timespec(&tc->tc_offset, tsp);
 }
 
 void
 microuptime(struct timeval *tv)
 {
-	struct timecounter *tc;
+	struct bintime bt;
 
 	nmicrouptime++;
-	tc = timecounter;
-	tv->tv_sec = tc->tc_offset_sec;
-	tv->tv_usec = tc->tc_offset_micro;
-	tv->tv_usec += ((u_int64_t)tco_delta(tc) * tc->tc_scale_micro) >> 32;
-	while (tv->tv_usec >= 1000000) {
-		tv->tv_usec -= 1000000;
-		tv->tv_sec++;
-	}
+	binuptime(&bt);
+	bintime2timeval(&bt, tv);
 }
 
 void
 nanouptime(struct timespec *ts)
 {
-	unsigned count;
-	u_int64_t delta;
-	struct timecounter *tc;
+	struct bintime bt;
 
 	nnanouptime++;
-	tc = timecounter;
-	ts->tv_sec = tc->tc_offset_sec;
-	count = tco_delta(tc);
-	delta = tc->tc_offset_nano;
-	delta += ((u_int64_t)count * tc->tc_scale_nano_f);
-	delta >>= 32;
-	delta += ((u_int64_t)count * tc->tc_scale_nano_i);
-	while (delta >= 1000000000) {
-		delta -= 1000000000;
-		ts->tv_sec++;
-	}
-	ts->tv_nsec = delta;
+	binuptime(&bt);
+	bintime2timespec(&bt, ts);
 }
 
 static void
@@ -228,12 +205,11 @@ tco_setscales(struct timecounter *tc)
 {
 	u_int64_t scale;
 
-	scale = 1000000000LL << 32;
-	scale += tc->tc_adjustment;
+	/* Sacrifice the lower bit to the deity for code clarity */
+	scale = 1ULL << 63;
+	scale += (tc->tc_adjustment * 4295LL) / 1000LL;
 	scale /= tc->tc_tweak->tc_frequency;
-	tc->tc_scale_micro = scale / 1000;
-	tc->tc_scale_nano_f = scale & 0xffffffff;
-	tc->tc_scale_nano_i = scale >> 32;
+	tc->tc_scale = scale * 2;
 }
 
 void
@@ -245,7 +221,6 @@ tc_update(struct timecounter *tc)
 void
 tc_init(struct timecounter *tc)
 {
-	struct timespec ts1;
 	struct timecounter *t1, *t2, *t3;
 	int i;
 
@@ -279,10 +254,7 @@ tc_init(struct timecounter *tc)
 
 	/* XXX: For now always start using the counter. */
 	tc->tc_offset_count = tc->tc_get_timecount(tc);
-	nanouptime(&ts1);
-	tc->tc_offset_nano = (u_int64_t)ts1.tv_nsec << 32;
-	tc->tc_offset_micro = ts1.tv_nsec / 1000;
-	tc->tc_offset_sec = ts1.tv_sec;
+	binuptime(&tc->tc_offset);
 	timecounter = tc;
 }
 
@@ -298,6 +270,7 @@ tc_setclock(struct timespec *ts)
 		boottime.tv_usec += 1000000;
 		boottime.tv_sec--;
 	}
+	timeval2bintime(&boottime, &boottimebin);
 	/* fiddle all the little crinkly bits around the fiords... */
 	tc_windup();
 }
@@ -307,7 +280,6 @@ switch_timecounter(struct timecounter *newtc)
 {
 	int s;
 	struct timecounter *tc;
-	struct timespec ts;
 
 	s = splclock();
 	tc = timecounter;
@@ -316,10 +288,7 @@ switch_timecounter(struct timecounter *newtc)
 		return;
 	}
 	newtc = newtc->tc_tweak->tc_other;
-	nanouptime(&ts);
-	newtc->tc_offset_sec = ts.tv_sec;
-	newtc->tc_offset_nano = (u_int64_t)ts.tv_nsec << 32;
-	newtc->tc_offset_micro = ts.tv_nsec / 1000;
+	binuptime(&newtc->tc_offset);
 	newtc->tc_offset_count = newtc->tc_get_timecount(newtc);
 	tco_setscales(newtc);
 	timecounter = newtc;
@@ -340,8 +309,7 @@ sync_other_counter(void)
 	delta = tco_delta(tc);
 	tc->tc_offset_count += delta;
 	tc->tc_offset_count &= tc->tc_counter_mask;
-	tc->tc_offset_nano += (u_int64_t)delta * tc->tc_scale_nano_f;
-	tc->tc_offset_nano += (u_int64_t)delta * tc->tc_scale_nano_i << 32;
+	bintime_addx(&tc->tc_offset, tc->tc_scale * delta);
 	return (tc);
 }
 
@@ -349,7 +317,9 @@ void
 tc_windup(void)
 {
 	struct timecounter *tc, *tco;
+	struct bintime bt;
 	struct timeval tvt;
+	int i;
 
 	tco = timecounter;
 	tc = sync_other_counter();
@@ -375,30 +345,19 @@ tc_windup(void)
 			tvt.tv_usec += 1000000;
 		}
 		boottime = tvt;
+		timeval2bintime(&boottime, &boottimebin);
 		timedelta -= tickdelta;
 	}
-
-	while (tc->tc_offset_nano >= 1000000000ULL << 32) {
-		tc->tc_offset_nano -= 1000000000ULL << 32;
-		tc->tc_offset_sec++;
+	for (i = tc->tc_offset.sec - tco->tc_offset.sec; i > 0; i--) {
 		ntp_update_second(tc);	/* XXX only needed if xntpd runs */
 		tco_setscales(tc);
 	}
 
-	tc->tc_offset_micro = (tc->tc_offset_nano / 1000) >> 32;
-
-	/* Figure out the wall-clock time */
-	tc->tc_nanotime.tv_sec = tc->tc_offset_sec + boottime.tv_sec;
-	tc->tc_nanotime.tv_nsec = 
-	    (tc->tc_offset_nano >> 32) + boottime.tv_usec * 1000;
-	tc->tc_microtime.tv_usec = tc->tc_offset_micro + boottime.tv_usec;
-	if (tc->tc_nanotime.tv_nsec >= 1000000000) {
-		tc->tc_nanotime.tv_nsec -= 1000000000;
-		tc->tc_microtime.tv_usec -= 1000000;
-		tc->tc_nanotime.tv_sec++;
-	}
-	time_second = tc->tc_microtime.tv_sec = tc->tc_nanotime.tv_sec;
-
+	bt = tc->tc_offset;
+	bintime_add(&bt, &boottimebin);
+	bintime2timeval(&bt, &tc->tc_microtime);
+	bintime2timespec(&bt, &tc->tc_nanotime);
+	time_second = tc->tc_microtime.tv_sec;
 	timecounter = tc;
 }
 
@@ -504,8 +463,8 @@ void
 pps_event(struct pps_state *pps, struct timecounter *tc, unsigned count, int event)
 {
 	struct timespec ts, *tsp, *osp;
-	u_int64_t delta;
 	unsigned tcount, *pcount;
+	struct bintime bt;
 	int foff, fhard;
 	pps_seq_t	*pseq;
 
@@ -542,20 +501,11 @@ pps_event(struct pps_state *pps, struct timecounter *tc, unsigned count, int eve
 	*pcount = count;
 
 	/* Convert the count to timespec */
-	ts.tv_sec = tc->tc_offset_sec;
 	tcount = count - tc->tc_offset_count;
 	tcount &= tc->tc_counter_mask;
-	delta = tc->tc_offset_nano;
-	delta += ((u_int64_t)tcount * tc->tc_scale_nano_f);
-	delta >>= 32;
-	delta += ((u_int64_t)tcount * tc->tc_scale_nano_i);
-	delta += boottime.tv_usec * 1000;
-	ts.tv_sec += boottime.tv_sec;
-	while (delta >= 1000000000) {
-		delta -= 1000000000;
-		ts.tv_sec++;
-	}
-	ts.tv_nsec = delta;
+	bt = tc->tc_offset;
+	bintime_addx(&bt, tc->tc_scale * tcount);
+	bintime2timespec(&bt, &ts);
 
 	(*pseq)++;
 	*tsp = ts;
@@ -569,14 +519,16 @@ pps_event(struct pps_state *pps, struct timecounter *tc, unsigned count, int eve
 	}
 #ifdef PPS_SYNC
 	if (fhard) {
+		u_int64_t delta;
 		/* magic, at its best... */
 		tcount = count - pps->ppscount[2];
 		pps->ppscount[2] = count;
 		tcount &= tc->tc_counter_mask;
-		delta = ((u_int64_t)tcount * tc->tc_tweak->tc_scale_nano_f);
-		delta >>= 32;
-		delta += ((u_int64_t)tcount * tc->tc_tweak->tc_scale_nano_i);
-		hardpps(tsp, delta);
+		bt.sec = 0;
+		bt.frac = 0;
+		bintime_addx(&bt, tc->tc_scale * tcount);
+		bintime2timespec(&bt, &ts);
+		hardpps(tsp, ts.tv_nsec + 1000000000 * ts.tv_sec);
 	}
 #endif
 }
diff --git a/sys/sys/time.h b/sys/sys/time.h
index 5f43d8d..bfa8193 100644
--- a/sys/sys/time.h
+++ b/sys/sys/time.h
@@ -79,6 +79,112 @@ struct timezone {
 #define	DST_EET		5	/* Eastern European dst */
 #define	DST_CAN		6	/* Canada */
 
+/* start of struct bintime stuff */
+
+struct bintime {
+	time_t		sec;
+	u_int64_t	frac;
+};
+
+static __inline void
+bintime_addx(struct bintime *bt, u_int64_t x)
+{
+#ifdef __i386
+	__asm(	"
+		addl %%eax,4(%%ecx)
+		adcl %%edx,8(%%ecx)
+		adcl $0,0(%%ecx)
+		" : : "A" (x), "c" (bt));
+#else
+	u_int64_t u;
+
+	u = bt->frac;
+	bt->frac += x;
+	if (u > bt->frac)
+		bt->sec++;
+#endif
+}
+
+static __inline void
+bintime_add(struct bintime *bt, struct bintime *bt2)
+{
+#ifdef __i386
+	__asm(	"
+		movl 4(%%edx),%%eax
+		addl %%eax,4(%%ecx)
+		movl 8(%%edx),%%eax
+		adcl %%eax,8(%%ecx)
+		movl 0(%%edx),%%eax
+		adcl %%eax,0(%%ecx)
+		" : : "c" (bt), "d" (bt2));
+#else
+	u_int64_t u;
+
+	u = bt->frac;
+	bt->frac += bt2->frac;
+	if (u > bt->frac)
+		bt->sec++;
+	bt->sec += bt2->sec;
+#endif
+}
+
+static __inline void
+bintime_sub(struct bintime *bt, struct bintime *bt2)
+{
+#ifdef __i386
+	__asm(	"
+		movl 4(%%edx),%%eax
+		subl %%eax,4(%%ecx)
+		movl 8(%%edx),%%eax
+		sbbl %%eax,8(%%ecx)
+		movl 0(%%edx),%%eax
+		sbbl %%eax,0(%%ecx)
+		" : : "c" (bt), "d" (bt2));
+#else
+	u_int64_t u;
+
+	u = bt->frac;
+	bt->frac -= bt2->frac;
+	if (u < bt->frac)
+		bt->sec--;
+	bt->sec -= bt2->sec;
+#endif
+}
+
+static __inline void
+bintime2timespec(struct bintime *bt, struct timespec *ts)
+{
+
+	ts->tv_sec = bt->sec;
+	ts->tv_nsec =  (1000000000ULL * (u_int32_t)(bt->frac >> 32)) >> 32;
+}
+
+static __inline void
+timespec2bintime(struct timespec *ts, struct bintime *bt)
+{
+
+	bt->sec = ts->tv_sec;
+	bt->frac = ts->tv_nsec * 18446744073;  /* int(2^64 / 1000000000) */
+}
+
+static __inline void
+bintime2timeval(struct bintime *bt, struct timeval *tv)
+{
+
+	tv->tv_sec = bt->sec;
+	tv->tv_usec =  (1000000ULL * (u_int32_t)(bt->frac >> 32)) >> 32;
+}
+
+static __inline void
+timeval2bintime(struct timeval *tv, struct bintime *bt)
+{
+
+	bt->sec = tv->tv_sec;
+	bt->frac = tv->tv_usec * 18446744073709;  /* int(2^64 / 1000000) */
+}
+
+/* end of struct bintime stuff */
+
 #ifdef _KERNEL
 
 /* Operations on timespecs */
@@ -188,6 +294,8 @@ struct clockinfo {
 #ifdef _KERNEL
 extern time_t	time_second;
 
+void	binuptime(struct bintime *bt);
+void	bintime(struct bintime *bt);
 void	getmicrouptime __P((struct timeval *tv));
 void	getmicrotime __P((struct timeval *tv));
 void	getnanouptime __P((struct timespec *tsp));
diff --git a/sys/sys/timetc.h b/sys/sys/timetc.h
index 9897f4d..0d79626 100644
--- a/sys/sys/timetc.h
+++ b/sys/sys/timetc.h
@@ -78,13 +78,9 @@ struct timecounter {
 	void			*tc_priv;
 	/* These fields will be managed by the generic code. */
 	int64_t			tc_adjustment;
-	u_int32_t		tc_scale_micro;
-	u_int32_t		tc_scale_nano_i;
-	u_int32_t		tc_scale_nano_f;
+	u_int64_t		tc_scale;
 	unsigned 		tc_offset_count;
-	u_int32_t		tc_offset_sec;
-	u_int32_t		tc_offset_micro;
-	u_int64_t		tc_offset_nano;
+	struct bintime		tc_offset;
 	struct timeval		tc_microtime;
 	struct timespec		tc_nanotime;
 	struct timecounter	*tc_avail;