gettimeofday nanoseconds patch (makes it possible for the posix-timer

gettimeofday nanoseconds patch (makes it possible for the posix-timer

[Christoph Lameter]

I am working on some timer issues for the IA64 in order to make the timers
more efficient and return results with a higher accuracy.

However, in various locations do_gettimeofday is used and then the
resulting usecs are multiplied by 1000 to obtain nanoseconds. This is in
particular problematic for the posix timers and especially clock_gettime.

The following patch introduces a new gettimeofday function using
struct timespec instead of struct timeval. If a platforms supports time
interpolation then the new gettimeofday will use that to provide a
gettimeofday function with higher accuracy and then also clock_gettime
will return with nanosecond accuracy.

I would be interested in feedback on this approach. In this context
the time interpolator patches that are being discussed on linux-ia64
would also be of interest. Those provide a generic way to utilize
any memory mapped or CPU counter to do the time interpolations for any
platforms and would allow an easy way to realize a nanosecond resolution
for all platforms.

The way that gettimeofday implements getting the offset may be varied but
I hope that the general approach of providing a gettimeofday handling
nanoseconds is acceptable.

The patch is against 2.6.8-rc1

Index: linux-2.6.7/kernel/time.c
=================================--- linux-2.6.7.orig/kernel/time.c
+++ linux-2.6.7/kernel/time.c
@@ -421,6 +421,40 @@

 EXPORT_SYMBOL(current_kernel_time);

+#ifdef TIME_INTERPOLATION
+void gettimeofday (struct timespec *tv)
+{
+        unsigned long seq;
+
+        do {
+                seq = read_seqbegin(&xtime_lock);
+                tv->tv_sec = xtime.tv_sec;
+                tv->tv_nsec = xtime.tv_nsec+time_interpolator_get_offset();
+        } while (unlikely(read_seqretry(&xtime_lock, seq)));
+
+        while (unlikely(tv->tv_nsec >= NSEC_PER_SEC)) {
+                tv->tv_nsec -= NSEC_PER_SEC;
+                ++tv->tv_sec;
+        }
+}
+
+#else
+/*
+ * Simulate gettimeofday using do_gettimeofday which only allows a timeval
+ * and therefore only yields usec accuracy
+ */
+void gettimeofday(struct timespec *tv)
+{
+	struct timeval x;
+
+	do_gettimeofday(&x);
+	tv->tv_sec = x.tv_sec;
+	tv->tv_nsec = x.tv_usec*NSEC_PER_USEC;
+}
+#endif
+
+EXPORT_SYMBOL(gettimeofday);
+
 #if (BITS_PER_LONG < 64)
 u64 get_jiffies_64(void)
 {
Index: linux-2.6.7/kernel/timer.c
=================================--- linux-2.6.7.orig/kernel/timer.c
+++ linux-2.6.7/kernel/timer.c
@@ -1241,8 +1241,7 @@
 		 * too.
 		 */

-		do_gettimeofday((struct timeval *)&tp);
-		tp.tv_nsec *= NSEC_PER_USEC;
+		gettimeofday(&tp);
 		tp.tv_sec += wall_to_monotonic.tv_sec;
 		tp.tv_nsec += wall_to_monotonic.tv_nsec;
 		if (tp.tv_nsec - NSEC_PER_SEC >= 0) {
Index: linux-2.6.7/kernel/posix-timers.c
=================================--- linux-2.6.7.orig/kernel/posix-timers.c
+++ linux-2.6.7/kernel/posix-timers.c
@@ -1168,15 +1168,10 @@
  */
 static int do_posix_gettime(struct k_clock *clock, struct timespec *tp)
 {
-	struct timeval tv;
-
 	if (clock->clock_get)
 		return clock->clock_get(tp);

-	do_gettimeofday(&tv);
-	tp->tv_sec = tv.tv_sec;
-	tp->tv_nsec = tv.tv_usec * NSEC_PER_USEC;
-
+	gettimeofday(tp);
 	return 0;
 }

@@ -1192,24 +1187,16 @@
 	struct timespec *tp, struct timespec *mo)
 {
 	u64 jiff;
-	struct timeval tpv;
 	unsigned int seq;

 	do {
 		seq = read_seqbegin(&xtime_lock);
-		do_gettimeofday(&tpv);
+		gettimeofday(tp);
 		*mo = wall_to_monotonic;
 		jiff = jiffies_64;

 	} while(read_seqretry(&xtime_lock, seq));

-	/*
-	 * Love to get this before it is converted to usec.
-	 * It would save a div AND a mpy.
-	 */
-	tp->tv_sec = tpv.tv_sec;
-	tp->tv_nsec = tpv.tv_usec * NSEC_PER_USEC;
-
 	return jiff;
 }

Index: linux-2.6.7/include/linux/time.h
=================================--- linux-2.6.7.orig/include/linux/time.h
+++ linux-2.6.7/include/linux/time.h
@@ -348,6 +348,7 @@
 struct itimerval;
 extern int do_setitimer(int which, struct itimerval *value, struct itimerval *ovalue);
 extern int do_getitimer(int which, struct itimerval *value);
+extern void gettimeofday (struct timespec *tv);

 static inline void
 set_normalized_timespec (struct timespec *ts, time_t sec, long nsec)
Index: linux-2.6.7/kernel/time.c
=================================--- linux-2.6.7.orig/kernel/time.c
+++ linux-2.6.7/kernel/time.c
@@ -421,6 +421,40 @@

 EXPORT_SYMBOL(current_kernel_time);

+#ifdef TIME_INTERPOLATION
+void gettimeofday (struct timespec *tv)
+{
+        unsigned long seq;
+
+        do {
+                seq = read_seqbegin(&xtime_lock);
+                tv->tv_sec = xtime.tv_sec;
+                tv->tv_nsec = xtime.tv_nsec+time_interpolator_get_offset();
+        } while (unlikely(read_seqretry(&xtime_lock, seq)));
+
+        while (unlikely(tv->tv_nsec >= NSEC_PER_SEC)) {
+                tv->tv_nsec -= NSEC_PER_SEC;
+                ++tv->tv_sec;
+        }
+}
+
+#else
+/*
+ * Simulate gettimeofday using do_gettimeofday which only allows a timeval
+ * and therefore only yields usec accuracy
+ */
+void gettimeofday(struct timespec *tv)
+{
+	struct timeval x;
+
+	do_gettimeofday(&x);
+	tv->tv_sec = x.tv_sec;
+	tv->tv_nsec = x.tv_usec*NSEC_PER_USEC;
+}
+#endif
+
+EXPORT_SYMBOL(gettimeofday);
+
 #if (BITS_PER_LONG < 64)
 u64 get_jiffies_64(void)
 {
Index: linux-2.6.7/kernel/timer.c
=================================--- linux-2.6.7.orig/kernel/timer.c
+++ linux-2.6.7/kernel/timer.c
@@ -1241,8 +1241,7 @@
 		 * too.
 		 */

-		do_gettimeofday((struct timeval *)&tp);
-		tp.tv_nsec *= NSEC_PER_USEC;
+		gettimeofday(&tp);
 		tp.tv_sec += wall_to_monotonic.tv_sec;
 		tp.tv_nsec += wall_to_monotonic.tv_nsec;
 		if (tp.tv_nsec - NSEC_PER_SEC >= 0) {
Index: linux-2.6.7/kernel/posix-timers.c
=================================--- linux-2.6.7.orig/kernel/posix-timers.c
+++ linux-2.6.7/kernel/posix-timers.c
@@ -1168,15 +1168,10 @@
  */
 static int do_posix_gettime(struct k_clock *clock, struct timespec *tp)
 {
-	struct timeval tv;
-
 	if (clock->clock_get)
 		return clock->clock_get(tp);

-	do_gettimeofday(&tv);
-	tp->tv_sec = tv.tv_sec;
-	tp->tv_nsec = tv.tv_usec * NSEC_PER_USEC;
-
+	gettimeofday(tp);
 	return 0;
 }

@@ -1192,24 +1187,16 @@
 	struct timespec *tp, struct timespec *mo)
 {
 	u64 jiff;
-	struct timeval tpv;
 	unsigned int seq;

 	do {
 		seq = read_seqbegin(&xtime_lock);
-		do_gettimeofday(&tpv);
+		gettimeofday(tp);
 		*mo = wall_to_monotonic;
 		jiff = jiffies_64;

 	} while(read_seqretry(&xtime_lock, seq));

-	/*
-	 * Love to get this before it is converted to usec.
-	 * It would save a div AND a mpy.
-	 */
-	tp->tv_sec = tpv.tv_sec;
-	tp->tv_nsec = tpv.tv_usec * NSEC_PER_USEC;
-
 	return jiff;
 }

Index: linux-2.6.7/include/linux/time.h
=================================--- linux-2.6.7.orig/include/linux/time.h
+++ linux-2.6.7/include/linux/time.h
@@ -348,6 +348,7 @@
 struct itimerval;
 extern int do_setitimer(int which, struct itimerval *value, struct itimerval *ovalue);
 extern int do_getitimer(int which, struct itimerval *value);
+extern void gettimeofday (struct timespec *tv);

 static inline void
 set_normalized_timespec (struct timespec *ts, time_t sec, long nsec)

Re: gettimeofday nanoseconds patch (makes it possible for the

[john stultz]

On Wed, 2004-07-14 at 09:41, Christoph Lameter wrote:
> I am working on some timer issues for the IA64 in order to make the timers
> more efficient and return results with a higher accuracy.
> 
> However, in various locations do_gettimeofday is used and then the
> resulting usecs are multiplied by 1000 to obtain nanoseconds. This is in
> particular problematic for the posix timers and especially clock_gettime.
> 
> The following patch introduces a new gettimeofday function using
> struct timespec instead of struct timeval. If a platforms supports time
> interpolation then the new gettimeofday will use that to provide a
> gettimeofday function with higher accuracy and then also clock_gettime
> will return with nanosecond accuracy.

Honestly, I'm not a fan of the patch. It realistically only helps ia64
and and adds more confusing code to the generic time code. If there
isn't an real/immediate need for this, I'd wait to 2.7 for a better
cleanup. 

None the less, I do understand the desire for the change (and am working
to address it in 2.7), so could you at least use a better name then
gettimeofday()? Maybe get_ns_time() or something? Its just too similar
to do_gettimeofday and the syscall gettimeofday(). 

Really, I feel the cleaner method is to fix do_gettimeofday() so it
returns a timespec and then convert it to a timeval in
sys_gettimeofday(). However this would add overhead to the syscall, so I
doubt folks would go for it.

> I would be interested in feedback on this approach. In this context
> the time interpolator patches that are being discussed on linux-ia64
> would also be of interest. Those provide a generic way to utilize
> any memory mapped or CPU counter to do the time interpolations for any
> platforms and would allow an easy way to realize a nanosecond resolution
> for all platforms.

I think the ia64 time interpolation code is a step in the right
direction (def better then the i386 bits), but it still isn't the
cleanest and clearest way. My plan is to select a reliable timesource
for the system, then use a periodic interrupt to accumulate time from
the timesource (in order to avoid overflows). This avoids lost tick
issues and cleanly separates the timer subsystem from the time of day
subsystem.

> The patch is against 2.6.8-rc1
> 
> Index: linux-2.6.7/kernel/time.c
> =================================> --- linux-2.6.7.orig/kernel/time.c
> +++ linux-2.6.7/kernel/time.c
> @@ -421,6 +421,40 @@
> 
>  EXPORT_SYMBOL(current_kernel_time);
> 
> +#ifdef TIME_INTERPOLATION
> +void gettimeofday (struct timespec *tv)
> +{
> +        unsigned long seq;
> +
> +        do {
> +                seq = read_seqbegin(&xtime_lock);
> +                tv->tv_sec = xtime.tv_sec;
> +                tv->tv_nsec = xtime.tv_nsec+time_interpolator_get_offset();
> +        } while (unlikely(read_seqretry(&xtime_lock, seq)));
> +
> +        while (unlikely(tv->tv_nsec >= NSEC_PER_SEC)) {
> +                tv->tv_nsec -= NSEC_PER_SEC;
> +                ++tv->tv_sec;
> +        }
> +}

You'll need to cap time_interpolator_get_offset() at the maximum NTP
tick size, or else you may have time go backwards right after a timer
interrupt. 

thanks
-john

Re: gettimeofday nanoseconds patch (makes it possible for the

[Christoph Lameter]

On Wed, 14 Jul 2004, john stultz wrote:

> Honestly, I'm not a fan of the patch. It realistically only helps ia64
> and and adds more confusing code to the generic time code. If there
> isn't an real/immediate need for this, I'd wait to 2.7 for a better
> cleanup.

The immediate need is that clock_gettime only returns microseconds scaled
to nanoseconds.

> None the less, I do understand the desire for the change (and am working
> to address it in 2.7), so could you at least use a better name then
> gettimeofday()? Maybe get_ns_time() or something? Its just too similar
> to do_gettimeofday and the syscall gettimeofday().

Right. I had it named getnstimeofday before but the feeling was that the
patch should not introduce a new name. Any approach that would allow
progress on the issue would be fine with me.

> Really, I feel the cleaner method is to fix do_gettimeofday() so it
> returns a timespec and then convert it to a timeval in
> sys_gettimeofday(). However this would add overhead to the syscall, so I
> doubt folks would go for it.

do_gettimeofday is used all over the linux kernel for a variety of
purposes and lots of code depends on the presence of a timeval struct.

> I think the ia64 time interpolation code is a step in the right
> direction (def better then the i386 bits), but it still isn't the
> cleanest and clearest way. My plan is to select a reliable timesource
> for the system, then use a periodic interrupt to accumulate time from
> the timesource (in order to avoid overflows). This avoids lost tick
> issues and cleanly separates the timer subsystem from the time of day
> subsystem.

That is what the changes to the time_interpolator do.

Re: gettimeofday nanoseconds patch (makes it possible for the

[David Mosberger]

>>>>> On Wed, 14 Jul 2004 13:28:39 -0700 (PDT), Christoph Lameter <clameter@sgi.com> said:

  Christoph> Right. I had it named getnstimeofday before but the
  Christoph> feeling was that the patch should not introduce a new
  Christoph> name. Any approach that would allow progress on the issue
  Christoph> would be fine with me.

Just to avoid further confusion: I wasn't objecting to the name, I was
suggesting that do_gettimeofday() should instead use timespec.

  Christoph> do_gettimeofday is used all over the linux kernel for a
  Christoph> variety of purposes and lots of code depends on the
  Christoph> presence of a timeval struct.

Which is true...

	--david

Re: gettimeofday nanoseconds patch (makes it possible for the

[john stultz]

On Wed, 2004-07-14 at 13:28, Christoph Lameter wrote:
> > None the less, I do understand the desire for the change (and am working
> > to address it in 2.7), so could you at least use a better name then
> > gettimeofday()? Maybe get_ns_time() or something? Its just too similar
> > to do_gettimeofday and the syscall gettimeofday().
> 
> Right. I had it named getnstimeofday before but the feeling was that the
> patch should not introduce a new name. Any approach that would allow
> progress on the issue would be fine with me.

Fair enough. getnstimeofday() sounds good enough for me. 

> > Really, I feel the cleaner method is to fix do_gettimeofday() so it
> > returns a timespec and then convert it to a timeval in
> > sys_gettimeofday(). However this would add overhead to the syscall, so I
> > doubt folks would go for it.
> 
> do_gettimeofday is used all over the linux kernel for a variety of
> purposes and lots of code depends on the presence of a timeval struct.

Indeed, it would be a decent amount of work to clean that up as well.

thanks
-john

Re: gettimeofday nanoseconds patch (makes it possible for the

[Christoph Lameter]

On Wed, 14 Jul 2004, john stultz wrote:

> On Wed, 2004-07-14 at 13:28, Christoph Lameter wrote:
> > > None the less, I do understand the desire for the change (and am working
> > > to address it in 2.7), so could you at least use a better name then
> > > gettimeofday()? Maybe get_ns_time() or something? Its just too similar
> > > to do_gettimeofday and the syscall gettimeofday().
> >
> > Right. I had it named getnstimeofday before but the feeling was that the
> > patch should not introduce a new name. Any approach that would allow
> > progress on the issue would be fine with me.
>
> Fair enough. getnstimeofday() sounds good enough for me.

Ok. A modified patch is following.

>
> > > Really, I feel the cleaner method is to fix do_gettimeofday() so it
> > > returns a timespec and then convert it to a timeval in
> > > sys_gettimeofday(). However this would add overhead to the syscall, so I
> > > doubt folks would go for it.
> >
> > do_gettimeofday is used all over the linux kernel for a variety of
> > purposes and lots of code depends on the presence of a timeval struct.
>
> Indeed, it would be a decent amount of work to clean that up as well.

The cleanup can be done gradually after this patch is in. I volunteer
to work on this (hoping that my employer may support that  ;-) ).

Signed-off-by: Christoph Lameter <clameter@sgi.com>

Index: linux-2.6.7/kernel/timer.c
=================================--- linux-2.6.7.orig/kernel/timer.c
+++ linux-2.6.7/kernel/timer.c
@@ -1241,8 +1241,7 @@
 		 * too.
 		 */

-		do_gettimeofday((struct timeval *)&tp);
-		tp.tv_nsec *= NSEC_PER_USEC;
+		getnstimeofday(&tp);
 		tp.tv_sec += wall_to_monotonic.tv_sec;
 		tp.tv_nsec += wall_to_monotonic.tv_nsec;
 		if (tp.tv_nsec - NSEC_PER_SEC >= 0) {
Index: linux-2.6.7/kernel/posix-timers.c
=================================--- linux-2.6.7.orig/kernel/posix-timers.c
+++ linux-2.6.7/kernel/posix-timers.c
@@ -1168,15 +1168,10 @@
  */
 static int do_posix_gettime(struct k_clock *clock, struct timespec *tp)
 {
-	struct timeval tv;
-
 	if (clock->clock_get)
 		return clock->clock_get(tp);

-	do_gettimeofday(&tv);
-	tp->tv_sec = tv.tv_sec;
-	tp->tv_nsec = tv.tv_usec * NSEC_PER_USEC;
-
+	getnstimeofday(tp);
 	return 0;
 }

@@ -1192,24 +1187,16 @@
 	struct timespec *tp, struct timespec *mo)
 {
 	u64 jiff;
-	struct timeval tpv;
 	unsigned int seq;

 	do {
 		seq = read_seqbegin(&xtime_lock);
-		do_gettimeofday(&tpv);
+		getnstimeofday(tp);
 		*mo = wall_to_monotonic;
 		jiff = jiffies_64;

 	} while(read_seqretry(&xtime_lock, seq));

-	/*
-	 * Love to get this before it is converted to usec.
-	 * It would save a div AND a mpy.
-	 */
-	tp->tv_sec = tpv.tv_sec;
-	tp->tv_nsec = tpv.tv_usec * NSEC_PER_USEC;
-
 	return jiff;
 }

Index: linux-2.6.7/include/linux/time.h
=================================--- linux-2.6.7.orig/include/linux/time.h
+++ linux-2.6.7/include/linux/time.h
@@ -348,6 +348,7 @@
 struct itimerval;
 extern int do_setitimer(int which, struct itimerval *value, struct itimerval *ovalue);
 extern int do_getitimer(int which, struct itimerval *value);
+extern void getnstimeofday (struct timespec *tv);

 static inline void
 set_normalized_timespec (struct timespec *ts, time_t sec, long nsec)
Index: linux-2.6.7/kernel/time.c
=================================--- linux-2.6.7.orig/kernel/time.c
+++ linux-2.6.7/kernel/time.c
@@ -22,6 +22,9 @@
  *	"A Kernel Model for Precision Timekeeping" by Dave Mills
  *	Allow time_constant larger than MAXTC(6) for NTP v4 (MAXTC = 10)
  *	(Even though the technical memorandum forbids it)
+ * 2004-07-14	 Christoph Lameter
+ *	Added getnstimeofday to allow the posix timer functions to return
+ *	with nanosecond accuracy
  */

 #include <linux/module.h>
@@ -421,6 +424,41 @@

 EXPORT_SYMBOL(current_kernel_time);

+#ifdef CONFIG_TIME_INTERPOLATION
+void getnstimeofday (struct timespec *tv)
+{
+	unsigned long seq,sec,nsec;
+
+	do {
+		seq = read_seqbegin(&xtime_lock);
+		sec = xtime.tv_sec;
+		nsec = xtime.tv_nsec+time_interpolator_get_offset();
+	} while (unlikely(read_seqretry(&xtime_lock, seq)));
+
+	while (unlikely(nsec >= NSEC_PER_SEC)) {
+		nsec -= NSEC_PER_SEC;
+		++sec;
+	}
+	tv->tv_sec = sec;
+	tv->tv_nsec = nsec;
+}
+#else
+/*
+ * Simulate gettimeofday using do_gettimeofday which only allows a timeval
+ * and therefore only yields usec accuracy
+ */
+void getnstimeofday(struct timespec *tv)
+{
+	struct timeval x;
+
+	do_gettimeofday(&x);
+	tv->tv_sec = x.tv_sec;
+	tv->tv_nsec = x.tv_usec * NSEC_PER_USEC;
+}
+#endif
+
+EXPORT_SYMBOL(getnstimeofday);
+
 #if (BITS_PER_LONG < 64)
 u64 get_jiffies_64(void)
 {

Re: gettimeofday nanoseconds patch (makes it possible for the

[john stultz]

On Wed, 2004-07-14 at 17:08, Christoph Lameter wrote:
> On Wed, 14 Jul 2004, john stultz wrote:
> > On Wed, 2004-07-14 at 13:28, Christoph Lameter wrote:
> > > > None the less, I do understand the desire for the change (and am working
> > > > to address it in 2.7), so could you at least use a better name then
> > > > gettimeofday()? Maybe get_ns_time() or something? Its just too similar
> > > > to do_gettimeofday and the syscall gettimeofday().
> > >
> > > Right. I had it named getnstimeofday before but the feeling was that the
> > > patch should not introduce a new name. Any approach that would allow
> > > progress on the issue would be fine with me.
> >
> > Fair enough. getnstimeofday() sounds good enough for me.
> 
> Ok. A modified patch is following.

I guess it looks good enough for me. I'd say send it to Andrew when
you're ready.

George, do you have any additional comments?

Although you still have the issue w/ NTP adjustments being ignored, but
last time I looked at the time_interpolator code, it seemed it was being
ignored there too, so at least your not doing worse then the ia64
do_gettimeofday(). [If I'm doing the time_interpolator code a great
injustice with the above, someone please correct me]

> > > > Really, I feel the cleaner method is to fix do_gettimeofday() so it
> > > > returns a timespec and then convert it to a timeval in
> > > > sys_gettimeofday(). However this would add overhead to the syscall, so I
> > > > doubt folks would go for it.
> > >
> > > do_gettimeofday is used all over the linux kernel for a variety of
> > > purposes and lots of code depends on the presence of a timeval struct.
> >
> > Indeed, it would be a decent amount of work to clean that up as well.
> 
> The cleanup can be done gradually after this patch is in. I volunteer
> to work on this (hoping that my employer may support that  ;-) ).

I'll try to remember to cc you on the 2.7 code when I get the first pass
ready (re-implementing the NTP mechanism is the last blocker). I'm sure
to appreciate additional feedback from non i386 arch specific views.

thanks
-john

Re: gettimeofday nanoseconds patch (makes it possible for the

[David Mosberger]

>>>>> On Wed, 14 Jul 2004 17:48:06 -0700, john stultz <johnstul@us.ibm.com> said:

  John> Although you still have the issue w/ NTP adjustments being
  John> ignored, but last time I looked at the time_interpolator code,
  John> it seemed it was being ignored there too, so at least your not
  John> doing worse then the ia64 do_gettimeofday(). [If I'm doing the
  John> time_interpolator code a great injustice with the above,
  John> someone please correct me]

The existing time-interpolator code for ia64 never lets time go
backwards (in the absence of a settimeofday(), of course).  There is
no need to special-case NTP.

With Christoph's changes, NTP is an issue again, however.

	--david

Re: gettimeofday nanoseconds patch (makes it possible for the

[john stultz]

On Wed, 2004-07-14 at 18:16, David Mosberger wrote:
> >>>>> On Wed, 14 Jul 2004 17:48:06 -0700, john stultz <johnstul@us.ibm.com> said:
> 
>   John> Although you still have the issue w/ NTP adjustments being
>   John> ignored, but last time I looked at the time_interpolator code,
>   John> it seemed it was being ignored there too, so at least your not
>   John> doing worse then the ia64 do_gettimeofday(). [If I'm doing the
>   John> time_interpolator code a great injustice with the above,
>   John> someone please correct me]
> 
> The existing time-interpolator code for ia64 never lets time go
> backwards (in the absence of a settimeofday(), of course).  There is
> no need to special-case NTP.

I guess I don't understand then, from my looking over it I didn't see
where the time_interpolator_get_offset() is scaled back when NTP is
slewing the clock. It seems that while the time-interpolator code does
keep time from going backwards, it also inadvertently ends up
compensating for NTP slow down. Thus the slewing is not visible to
userspace. 

In order for this to happen, time_interpolator_get_offset() would need
to be scaled or capped as to that it would not return more then the
length of the *NTP adjusted tick* during an actual tick interval.

I may be missing something, so please let me know if I'm wrong.

thanks
-john

Re: gettimeofday nanoseconds patch (makes it possible for the

[David Mosberger]

>>>>> On Wed, 14 Jul 2004 18:35:20 -0700, john stultz <johnstul@us.ibm.com> said:

  john> On Wed, 2004-07-14 at 18:16, David Mosberger wrote:
  >> >>>>> On Wed, 14 Jul 2004 17:48:06 -0700, john stultz
  >> <johnstul@us.ibm.com> said:

  >>  The existing time-interpolator code for ia64 never lets time go
  >> backwards (in the absence of a settimeofday(), of course).  There
  >> is no need to special-case NTP.

  John> I guess I don't understand then, from my looking over it I
  John> didn't see where the time_interpolator_get_offset() is scaled
  John> back when NTP is slewing the clock.

Are you looking at Christoph's code?  My explanation applies to the
old interpolation-code...

	--david

Re: gettimeofday nanoseconds patch (makes it possible for the

[Christoph Lameter]

On Wed, 14 Jul 2004, David Mosberger wrote:

> >>>>> On Wed, 14 Jul 2004 17:48:06 -0700, john stultz <johnstul@us.ibm.com> said:
>
>   John> Although you still have the issue w/ NTP adjustments being
>   John> ignored, but last time I looked at the time_interpolator code,
>   John> it seemed it was being ignored there too, so at least your not
>   John> doing worse then the ia64 do_gettimeofday(). [If I'm doing the
>   John> time_interpolator code a great injustice with the above,
>   John> someone please correct me]
>
> The existing time-interpolator code for ia64 never lets time go
> backwards (in the absence of a settimeofday(), of course).  There is
> no need to special-case NTP.
>
> With Christoph's changes, NTP is an issue again, however.

The new code gains scalability and speed by avoiding the cmpxchg in the
old code. No check is done anymore that the resulting offset is really
later than the last time returned. In order to insure monotonic time the
underlying clock used must also be monotonic. The new code cannot handle
fluctuating time sources like unsynchronized ITCs. If the time source is
fluctuating then a function may be defined to be the source of time. This
function may do a compare to the last value returned in order to insure
that the clock stays monotonic and does not go backward. Doing so may slow
things down to the way they were before.

The old code only insured that the interpolated offset in nanoseconds
after a timer tick never goes backward. Negative corrections to xtime
could also result in time going backward since the offset is
always added to xtime. Both the old and the new code use the logic in
time_interpolator_update (invoked when xtime is advanced) to compensate
for this situation.

Re: gettimeofday nanoseconds patch (makes it possible for the

[john stultz]

On Thu, 2004-07-15 at 08:31, Christoph Lameter wrote:
> On Wed, 14 Jul 2004, David Mosberger wrote:
> 
> > >>>>> On Wed, 14 Jul 2004 17:48:06 -0700, john stultz <johnstul@us.ibm.com> said:
> >
> >   John> Although you still have the issue w/ NTP adjustments being
> >   John> ignored, but last time I looked at the time_interpolator code,
> >   John> it seemed it was being ignored there too, so at least your not
> >   John> doing worse then the ia64 do_gettimeofday(). [If I'm doing the
> >   John> time_interpolator code a great injustice with the above,
> >   John> someone please correct me]
> >
> > The existing time-interpolator code for ia64 never lets time go
> > backwards (in the absence of a settimeofday(), of course).  There is
> > no need to special-case NTP.
> >
> > With Christoph's changes, NTP is an issue again, however.
> 
> The old code only insured that the interpolated offset in nanoseconds
> after a timer tick never goes backward. Negative corrections to xtime
> could also result in time going backward since the offset is
> always added to xtime. Both the old and the new code use the logic in
> time_interpolator_update (invoked when xtime is advanced) to compensate
> for this situation.

However it seems this compensation also negates NTPs adjustment. There
is nothing that scales the time_interpolator_update's output. 

A quick example:
So lets say tick length is 1000us. At time zero we call gettimeofday(),
it returns xtime + time_interpolator_update(), both return zero. 999us
later at time two, the same thing happens and we return (0 + 999). A
usec later at time three, the timer interrupt is called and xtime is
incremented 1000us, and time_interpolator decrements 1000us. Thus a call
to gettimeofday would return (1000 + 0). Immediately following, adjtimex
is called, setting the tick length to 900us. Then 999 usecs later at
time four, we return (1000 + 999). The next usec at time five, the timer
interrupt goes off and increments xtime by 900, and decrements the
time_interpolator by 900. Thus a call to gettimeofday() would return
(1900 + 100). So rather returning the proper NTP adjusted time of 1900,
2000 is being returned as if the NTP adjustment never occured. 

Now, you cannot have time going backwards, so the solution is to cap the
output of time_interpolator_update() by insuring that during an NTP
adjusted tick, we do not return more then the NTP adjusted tick length
added to the base offset we calculated at the last timer interrupt.

Thus at time four above(and during the 99 usecs before it) we would
return (1000 + 900) instead of (1000+999). 

And again, the ia64 code isn't my specialty, so if I'm just being daft,
please let me know. 

thanks
-john

Re: gettimeofday nanoseconds patch (makes it possible for the

[Christoph Lameter]

On Thu, 15 Jul 2004, john stultz wrote:

> > The old code only insured that the interpolated offset in nanoseconds
> > after a timer tick never goes backward. Negative corrections to xtime
> > could also result in time going backward since the offset is
> > always added to xtime. Both the old and the new code use the logic in
> > time_interpolator_update (invoked when xtime is advanced) to compensate
> > for this situation.
>
> However it seems this compensation also negates NTPs adjustment. There
> is nothing that scales the time_interpolator_update's output.
>
> A quick example:
> So lets say tick length is 1000us. At time zero we call gettimeofday(),
> it returns xtime + time_interpolator_update(), both return zero. 999us
> later at time two, the same thing happens and we return (0 + 999). A
> usec later at time three, the timer interrupt is called and xtime is
> incremented 1000us, and time_interpolator decrements 1000us. Thus a call
> to gettimeofday would return (1000 + 0). Immediately following, adjtimex
> is called, setting the tick length to 900us. Then 999 usecs later at
> time four, we return (1000 + 999). The next usec at time five, the timer
> interrupt goes off and increments xtime by 900, and decrements the
> time_interpolator by 900. Thus a call to gettimeofday() would return
> (1900 + 100). So rather returning the proper NTP adjusted time of 1900,
> 2000 is being returned as if the NTP adjustment never occured.

The above omits some details but is basically correct. Note that the
time_interpolator gradually brings time back into sync with xtime because
it looses a few nanoseconds (depending on the clock) each tick. At
some point the correction asked for by the timer tick will be greater than the
offset and at that time the offset is set to zero. Then a resync has
occurred.

> Now, you cannot have time going backwards, so the solution is to cap the
> output of time_interpolator_update() by insuring that during an NTP
> adjusted tick, we do not return more then the NTP adjusted tick length
> added to the base offset we calculated at the last timer interrupt.

> Thus at time four above(and during the 99 usecs before it) we would
> return (1000 + 900) instead of (1000+999).

Having time stand still is an awkward solution: Time may stand
still even longer if the tick is delayed and then time suddenly jumps
ahead when the tick finally occurs.

The existing implementation slowly compensates and is the best solution
IMHO.

> And again, the ia64 code isn't my specialty, so if I'm just being daft,
> please let me know.

What I described was coded by others. I just hope that I have explained it
accurately.

Re: gettimeofday nanoseconds patch (makes it possible for the

[john stultz]

On Thu, 2004-07-15 at 10:03, Christoph Lameter wrote:
> On Thu, 15 Jul 2004, john stultz wrote:
> 
> > > The old code only insured that the interpolated offset in nanoseconds
> > > after a timer tick never goes backward. Negative corrections to xtime
> > > could also result in time going backward since the offset is
> > > always added to xtime. Both the old and the new code use the logic in
> > > time_interpolator_update (invoked when xtime is advanced) to compensate
> > > for this situation.
> >
> > However it seems this compensation also negates NTPs adjustment. There
> > is nothing that scales the time_interpolator_update's output.
> >
> > A quick example:
> > So lets say tick length is 1000us. At time zero we call gettimeofday(),
> > it returns xtime + time_interpolator_update(), both return zero. 999us
> > later at time two, the same thing happens and we return (0 + 999). A
> > usec later at time three, the timer interrupt is called and xtime is
> > incremented 1000us, and time_interpolator decrements 1000us. Thus a call
> > to gettimeofday would return (1000 + 0). Immediately following, adjtimex
> > is called, setting the tick length to 900us. Then 999 usecs later at
> > time four, we return (1000 + 999). The next usec at time five, the timer
> > interrupt goes off and increments xtime by 900, and decrements the
> > time_interpolator by 900. Thus a call to gettimeofday() would return
> > (1900 + 100). So rather returning the proper NTP adjusted time of 1900,
> > 2000 is being returned as if the NTP adjustment never occured.
> 
> The above omits some details but is basically correct. Note that the
> time_interpolator gradually brings time back into sync with xtime because
> it looses a few nanoseconds (depending on the clock) each tick. At
> some point the correction asked for by the timer tick will be greater than the
> offset and at that time the offset is set to zero. Then a resync has
> occurred.

Hmmm. I haven't noticed that bit. I'll have to look at it again. Thanks
for the pointer. 


> > Thus at time four above(and during the 99 usecs before it) we would
> > return (1000 + 900) instead of (1000+999).
> 
> Having time stand still is an awkward solution: Time may stand
> still even longer if the tick is delayed and then time suddenly jumps
> ahead when the tick finally occurs.
> 
> The existing implementation slowly compensates and is the best solution
> IMHO.

Indeed capping time is awkward, I'm working on rewriting the NTP code so
that it appropriately and consistently scales the inter-tick time. But
again, that'll hopefully be a 2.7 thing. 

thanks for the clarifications
-john

Re: gettimeofday nanoseconds patch (makes it possible for the posix-timer

[George Anzinger]

john stultz wrote:
> On Wed, 2004-07-14 at 09:41, Christoph Lameter wrote:
> 
>>I am working on some timer issues for the IA64 in order to make the timers
>>more efficient and return results with a higher accuracy.
>>
>>However, in various locations do_gettimeofday is used and then the
>>resulting usecs are multiplied by 1000 to obtain nanoseconds. This is in
>>particular problematic for the posix timers and especially clock_gettime.
>>
>>The following patch introduces a new gettimeofday function using
>>struct timespec instead of struct timeval. If a platforms supports time
>>interpolation then the new gettimeofday will use that to provide a
>>gettimeofday function with higher accuracy and then also clock_gettime
>>will return with nanosecond accuracy.
> 
> 
> Honestly, I'm not a fan of the patch. It realistically only helps ia64
> and and adds more confusing code to the generic time code. If there
> isn't an real/immediate need for this, I'd wait to 2.7 for a better
> cleanup. 
> 
> None the less, I do understand the desire for the change (and am working
> to address it in 2.7), so could you at least use a better name then
> gettimeofday()? Maybe get_ns_time() or something? Its just too similar
> to do_gettimeofday and the syscall gettimeofday(). 
> 
> Really, I feel the cleaner method is to fix do_gettimeofday() so it
> returns a timespec and then convert it to a timeval in
> sys_gettimeofday(). However this would add overhead to the syscall, so I
> doubt folks would go for it.

Uh, I don't think it adds any overhead.  If the get_offset code returns 
nanoseconds which is added to xtime you get a timespec which you then convert to 
the timeval.  Currently the get_offset code returns usec so the xtime is first 
converted to timeval and then the add is done.  So the timespec to timeval 
conversion is done in both cases.

As to accuracy, the more "accurate" way is to change get_offset to return 
nanoseconds.  This way there is only one round off (by the divide) instead of 
two (the get_offset and the divide).  I ran into this problem in the latest HRT 
patch.  One of my tests is to do a gettimeofday and a clock_gettime and make 
sure there is no "backward" stuff happening.  Test failed by 1 micro second 
"some" of the time because of this double round off.

To fix this the HRT patch changes do_gettimeofday to use the get_offset the 
patch provides to do the full high-res thing.

Oh, and by the way, the divide in the conversion of nsec to usec is not really a 
divide due to the magic of the gcc optimizer.

I actually promised John I would provide a patch to do this, but, well, we have 
customers....

-g
> 
> 
>>I would be interested in feedback on this approach. In this context
>>the time interpolator patches that are being discussed on linux-ia64
>>would also be of interest. Those provide a generic way to utilize
>>any memory mapped or CPU counter to do the time interpolations for any
>>platforms and would allow an easy way to realize a nanosecond resolution
>>for all platforms.
> 
> 
> I think the ia64 time interpolation code is a step in the right
> direction (def better then the i386 bits), but it still isn't the
> cleanest and clearest way. My plan is to select a reliable timesource
> for the system, then use a periodic interrupt to accumulate time from
> the timesource (in order to avoid overflows). This avoids lost tick
> issues and cleanly separates the timer subsystem from the time of day
> subsystem.
> 
> 
>>The patch is against 2.6.8-rc1
>>
>>Index: linux-2.6.7/kernel/time.c
>>=================================>>--- linux-2.6.7.orig/kernel/time.c
>>+++ linux-2.6.7/kernel/time.c
>>@@ -421,6 +421,40 @@
>>
>> EXPORT_SYMBOL(current_kernel_time);
>>
>>+#ifdef TIME_INTERPOLATION
>>+void gettimeofday (struct timespec *tv)
>>+{
>>+        unsigned long seq;
>>+
>>+        do {
>>+                seq = read_seqbegin(&xtime_lock);
>>+                tv->tv_sec = xtime.tv_sec;
>>+                tv->tv_nsec = xtime.tv_nsec+time_interpolator_get_offset();
>>+        } while (unlikely(read_seqretry(&xtime_lock, seq)));
>>+
>>+        while (unlikely(tv->tv_nsec >= NSEC_PER_SEC)) {
>>+                tv->tv_nsec -= NSEC_PER_SEC;
>>+                ++tv->tv_sec;
>>+        }
>>+}
> 
> 
> You'll need to cap time_interpolator_get_offset() at the maximum NTP
> tick size, or else you may have time go backwards right after a timer
> interrupt. 
> 
> thanks
> -john
> 
> 
> 
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Re: gettimeofday nanoseconds patch (makes it possible for the

[Christoph Lameter]

On Thu, 15 Jul 2004, George Anzinger wrote:

> As to accuracy, the more "accurate" way is to change get_offset to return
> nanoseconds.  This way there is only one round off (by the divide) instead of
> two (the get_offset and the divide).  I ran into this problem in the latest HRT
> patch.  One of my tests is to do a gettimeofday and a clock_gettime and make
> sure there is no "backward" stuff happening.  Test failed by 1 micro second
> "some" of the time because of this double round off.

Well yes this is what the interpolator etc does on IA64.
time_interpolator_get_offset returns nanoseconds. I have done
tests to insure that no backward stuff happens. Tests were done
with the mentioned patch and clock_gettime was returning nanosecond
accuracy.

Re: gettimeofday nanoseconds patch (makes it possible for the posix-timer functions to return higher

[Matthew Wilcox]

On Wed, Jul 14, 2004 at 09:41:03AM -0700, Christoph Lameter wrote:
> The following patch introduces a new gettimeofday function using
> struct timespec instead of struct timeval. If a platforms supports time
> interpolation then the new gettimeofday will use that to provide a
> gettimeofday function with higher accuracy and then also clock_gettime
> will return with nanosecond accuracy.

You seem to have included two patches here that are very similar ...
could you send the patch you intended please?

-- 
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain

Re: gettimeofday nanoseconds patch (makes it possible for the

[Christoph Lameter]

On Wed, 14 Jul 2004, Matthew Wilcox wrote:
> You seem to have included two patches here that are very similar ...
> could you send the patch you intended please?

Right. Somehow my patch management system did something strange.
Here is the patch:

Index: linux-2.6.7/kernel/time.c
=================================--- linux-2.6.7.orig/kernel/time.c
+++ linux-2.6.7/kernel/time.c
@@ -421,6 +421,41 @@

 EXPORT_SYMBOL(current_kernel_time);

+#ifdef CONFIG_TIME_INTERPOLATION
+void gettimeofday (struct timespec *tv)
+{
+        unsigned long seq,sec,nsec;
+
+        do {
+                seq = read_seqbegin(&xtime_lock);
+                sec = xtime.tv_sec;
+                nsec = xtime.tv_nsec+time_interpolator_get_offset();
+        } while (unlikely(read_seqretry(&xtime_lock, seq)));
+
+        while (unlikely(nsec >= NSEC_PER_SEC)) {
+                nsec -= NSEC_PER_SEC;
+                ++sec;
+        }
+	tv->tv_sec = sec;
+	tv->tv_nsec = nsec;
+}
+#else
+/*
+ * Simulate gettimeofday using do_gettimeofday which only allows a timeval
+ * and therefore only yields usec accuracy
+ */
+void gettimeofday(struct timespec *tv)
+{
+	struct timeval x;
+
+	do_gettimeofday(&x);
+	tv->tv_sec = x.tv_sec;
+	tv->tv_nsec = x.tv_usec*NSEC_PER_USEC;
+}
+#endif
+
+EXPORT_SYMBOL(gettimeofday);
+
 #if (BITS_PER_LONG < 64)
 u64 get_jiffies_64(void)
 {
Index: linux-2.6.7/kernel/timer.c
=================================--- linux-2.6.7.orig/kernel/timer.c
+++ linux-2.6.7/kernel/timer.c
@@ -1241,8 +1241,7 @@
 		 * too.
 		 */

-		do_gettimeofday((struct timeval *)&tp);
-		tp.tv_nsec *= NSEC_PER_USEC;
+		gettimeofday(&tp);
 		tp.tv_sec += wall_to_monotonic.tv_sec;
 		tp.tv_nsec += wall_to_monotonic.tv_nsec;
 		if (tp.tv_nsec - NSEC_PER_SEC >= 0) {
Index: linux-2.6.7/kernel/posix-timers.c
=================================--- linux-2.6.7.orig/kernel/posix-timers.c
+++ linux-2.6.7/kernel/posix-timers.c
@@ -1168,15 +1168,10 @@
  */
 static int do_posix_gettime(struct k_clock *clock, struct timespec *tp)
 {
-	struct timeval tv;
-
 	if (clock->clock_get)
 		return clock->clock_get(tp);

-	do_gettimeofday(&tv);
-	tp->tv_sec = tv.tv_sec;
-	tp->tv_nsec = tv.tv_usec * NSEC_PER_USEC;
-
+	gettimeofday(tp);
 	return 0;
 }

@@ -1192,24 +1187,16 @@
 	struct timespec *tp, struct timespec *mo)
 {
 	u64 jiff;
-	struct timeval tpv;
 	unsigned int seq;

 	do {
 		seq = read_seqbegin(&xtime_lock);
-		do_gettimeofday(&tpv);
+		gettimeofday(tp);
 		*mo = wall_to_monotonic;
 		jiff = jiffies_64;

 	} while(read_seqretry(&xtime_lock, seq));

-	/*
-	 * Love to get this before it is converted to usec.
-	 * It would save a div AND a mpy.
-	 */
-	tp->tv_sec = tpv.tv_sec;
-	tp->tv_nsec = tpv.tv_usec * NSEC_PER_USEC;
-
 	return jiff;
 }

Index: linux-2.6.7/include/linux/time.h
=================================--- linux-2.6.7.orig/include/linux/time.h
+++ linux-2.6.7/include/linux/time.h
@@ -348,6 +348,7 @@
 struct itimerval;
 extern int do_setitimer(int which, struct itimerval *value, struct itimerval *ovalue);
 extern int do_getitimer(int which, struct itimerval *value);
+extern void gettimeofday (struct timespec *tv);

 static inline void
 set_normalized_timespec (struct timespec *ts, time_t sec, long nsec)