non-scalar ktime addition and subtraction broken

non-scalar ktime addition and subtraction broken

[Jeff Dike]

The use of 64-bit additions and subtractions on something which is
nominally a struct containing 32-bit second and nanosecond field is
broken when a negative time is involved.  When the structure is
treated as a 64-bit integer, the increment of the upper 32 bits that's
part of two's-complement subtraction is lost.  This leaves the end
result off by one second.

This manifested itself with sleeps inside UML lasting about 1 second
shorter than expected.

The patch below is more a problem statement than a real fix.  People
thought about performance, and I don't know what this does to that
work.

I'm not sure why the hrtimer.c part is needed - I had done that before
tracking down the ktime_add problem.  I see short sleeps without it,
so it is needed somehow.

The ktime_sub piece was done for completeness - UML compiles and boots
with no apparent ill effects, but it's otherwise untested.

As an aside, I fail to see how it can be correct for ktime_sub to add
NSEC_PER_SEC to something without compensating somewhere else for it.

Andrew - please don't drop this into -mm without an OK from Thomas or
someone else who's familiar with this code :-)

				Jeff

Index: linux-2.6.17-mm/include/linux/ktime.h
===================================================================
--- linux-2.6.17-mm.orig/include/linux/ktime.h	2006-06-01 22:15:44.000000000 -0400
+++ linux-2.6.17-mm/include/linux/ktime.h	2006-06-01 23:00:32.000000000 -0400
@@ -148,7 +148,8 @@ static inline ktime_t ktime_sub(const kt
 {
 	ktime_t res;
 
-	res.tv64 = lhs.tv64 - rhs.tv64;
+	res.tv.sec = lhs.tv.sec - rhs.tv.sec;
+	res.tv.nsec = lhs.tv.nsec - rhs.tv.nsec;
 	if (res.tv.nsec < 0)
 		res.tv.nsec += NSEC_PER_SEC;
 
@@ -167,7 +168,8 @@ static inline ktime_t ktime_add(const kt
 {
 	ktime_t res;
 
-	res.tv64 = add1.tv64 + add2.tv64;
+	res.tv.sec = add1.tv.sec + add2.tv.sec;
+	res.tv.nsec = add1.tv.nsec + add2.tv.nsec;
 	/*
 	 * performance trick: the (u32) -NSEC gives 0x00000000Fxxxxxxx
 	 * so we subtract NSEC_PER_SEC and add 1 to the upper 32 bit.
Index: linux-2.6.17-mm/kernel/hrtimer.c
===================================================================
--- linux-2.6.17-mm.orig/kernel/hrtimer.c	2006-06-01 22:15:44.000000000 -0400
+++ linux-2.6.17-mm/kernel/hrtimer.c	2006-06-01 22:57:24.000000000 -0400
@@ -627,7 +627,8 @@ static inline void run_hrtimer_queue(str
 		int restart;
 
 		timer = rb_entry(node, struct hrtimer, node);
-		if (base->softirq_time.tv64 <= timer->expires.tv64)
+		if(ktime_to_ns(base->softirq_time) <=
+		   ktime_to_ns(timer->expires))
 			break;
 
 		fn = timer->function;

Re: non-scalar ktime addition and subtraction broken

[Thomas Gleixner]

On Thu, 2006-06-01 at 23:08 -0400, Jeff Dike wrote:
> The use of 64-bit additions and subtractions on something which is
> nominally a struct containing 32-bit second and nanosecond field is
> broken when a negative time is involved.  When the structure is
> treated as a 64-bit integer, the increment of the upper 32 bits that's
> part of two's-complement subtraction is lost.  This leaves the end
> result off by one second.
> 
> This manifested itself with sleeps inside UML lasting about 1 second
> shorter than expected.
> 
> The patch below is more a problem statement than a real fix.  People
> thought about performance, and I don't know what this does to that
> work.
> 
> I'm not sure why the hrtimer.c part is needed - I had done that before
> tracking down the ktime_add problem.  I see short sleeps without it,
> so it is needed somehow.
> 
> The ktime_sub piece was done for completeness - UML compiles and boots
> with no apparent ill effects, but it's otherwise untested.
> 
> As an aside, I fail to see how it can be correct for ktime_sub to add
> NSEC_PER_SEC to something without compensating somewhere else for it.
> 
> Andrew - please don't drop this into -mm without an OK from Thomas or
> someone else who's familiar with this code :-)

NAK. ktime_t is defined that ist must be normalized the same way as
timespecs. The nsec part must be >= 0 and < NSEC_PER_SEC. Fix the part
which is feeding non normalized values.

	tglx

Re: [uml-devel] Re: non-scalar ktime addition and subtraction broken

[Jeff Dike]

On Fri, Jun 02, 2006 at 08:54:22AM +0200, Thomas Gleixner wrote:
> NAK. ktime_t is defined that ist must be normalized the same way as
> timespecs. The nsec part must be >= 0 and < NSEC_PER_SEC. Fix the part
> which is feeding non normalized values.

Aha, that would be me, initializing wall_to_monotonic incorrectly.  Thanks
for the clue.

				Jeff

Re: [uml-devel] non-scalar ktime addition and subtraction broken

[Blaisorblade]

[-- Attachment #1: Type: text/plain, Size: 1239 bytes --]

On Friday 02 June 2006 17:19, Jeff Dike wrote:
> On Fri, Jun 02, 2006 at 08:54:22AM +0200, Thomas Gleixner wrote:
> > NAK. ktime_t is defined that ist must be normalized the same way as
> > timespecs. The nsec part must be >= 0 and < NSEC_PER_SEC. Fix the part
> > which is feeding non normalized values.
>
> Aha, that would be me, initializing wall_to_monotonic incorrectly.  Thanks
> for the clue.
Ok, since I now I'll never finish it:
$ ll old-patch-scripts/patches/uml-fix-timers.patch
-rw-r--r-- 1 paolo paolo 6763 2005-07-24 06:41 
old-patch-scripts/patches/uml-fix-timers.patch

I'm attaching this incomplete patch. It won't apply (it was written likely 
before 2.6.13 but surely after git was born), it likely introduces bugs and I 
don't remember which ones, but it does point out some theoretical issues 
about timekeeping (including this one):

+       set_normalized_timespec(&wall_to_monotonic, -now.tv_sec, 
-now.tv_nsec);

(I likely was fighting against the loadavg >= 1.0 bug but I went looking for 
every kind of things).
-- 
Inform me of my mistakes, so I can keep imitating Homer Simpson's "Doh!".
Paolo Giarrusso, aka Blaisorblade (Skype ID "PaoloGiarrusso", ICQ 215621894)
http://www.user-mode-linux.org/~blaisorblade

[-- Attachment #2: uml-fix-timers.patch --]
[-- Type: text/x-diff, Size: 6763 bytes --]



*) Rename timer() since it's a global and such a name is a "shooting offense".
Also, it's difficult to find the def with ctags currently, because people miss
fantasy.

*) do_timer must be called with xtime_lock held. I'm not sure
boot_timer_handler needs this, however I don't think it hurts: it simply
disables irq and takes a spinlock.

*) wall_to_monotonic must be normalized and have a posititive ts_nsec part,
see wall_to_monotonic definition and i386 usage in arch/i386/kernel/time.c.
Otherwise you can get negative tv_nsec results with
do_posix_clock_monotonic_gettime and its callers, including sys_timer_gettime.

*) Remove um_time() and um_stime() syscalls since they are identical to
system-wide ones.

*) Move clock_was_set() from do_gettimeofday to do_settimeofday. Not only from
the name you guess this is needed, but I indeed verified that for i386 it's in
arch/i386/kernel/time.c:do_settimeofday().

*) XXX: Probably do_settimeofday should be copied from i386 to replace the
current version.

*) XXX: do_[gs]ettimeofday() should use seqlocks like in i386, instead of
timer_lock() like they do. They also don't synchronize with the rest, beyond
the performance problems!

Signed-off-by: Paolo 'Blaisorblade' Giarrusso <blaisorblade@yahoo.it>
---

 linux-2.6.git-paolo/arch/um/include/time_user.h        |    2 
 linux-2.6.git-paolo/arch/um/kernel/time.c              |   13 ++---
 linux-2.6.git-paolo/arch/um/kernel/time_kern.c         |   42 ++++++-----------
 linux-2.6.git-paolo/arch/um/sys-i386/sys_call_table.S  |    2 
 linux-2.6.git-paolo/arch/um/sys-x86_64/syscall_table.c |    7 --
 5 files changed, 23 insertions(+), 43 deletions(-)

diff -puN arch/um/kernel/time.c~uml-fix-timers arch/um/kernel/time.c
--- linux-2.6.git/arch/um/kernel/time.c~uml-fix-timers	2005-05-21 18:38:18.000000000 +0200
+++ linux-2.6.git-paolo/arch/um/kernel/time.c	2005-05-21 18:38:18.000000000 +0200
@@ -27,7 +27,7 @@ extern struct timeval xtime;
 
 struct timeval local_offset = { 0, 0 };
 
-void timer(void)
+void userspace_timer(void)
 {
 	gettimeofday(&xtime, NULL);
 	timeradd(&xtime, &local_offset, &xtime);
@@ -97,19 +97,16 @@ void uml_idle_timer(void)
 	set_interval(ITIMER_REAL);
 }
 
-extern int do_posix_clock_monotonic_gettime(struct timespec *tp);
+extern void time_init_kern(void);
 
+/* This is called by init/main.c during early boot. */
 void time_init(void)
 {
-	struct timespec now;
-
 	if(signal(SIGVTALRM, boot_timer_handler) == SIG_ERR)
 		panic("Couldn't set SIGVTALRM handler");
 	set_interval(ITIMER_VIRTUAL);
 
-	do_posix_clock_monotonic_gettime(&now);
-	wall_to_monotonic.tv_sec = -now.tv_sec;
-	wall_to_monotonic.tv_nsec = -now.tv_nsec;
+	time_init_kern();
 }
 
 /* Declared in linux/time.h, which can't be included here */
@@ -123,7 +120,6 @@ void do_gettimeofday(struct timeval *tv)
 	gettimeofday(tv, NULL);
 	timeradd(tv, &local_offset, tv);
 	time_unlock(flags);
-	clock_was_set();
 }
 
 int do_settimeofday(struct timespec *tv)
@@ -142,6 +138,7 @@ int do_settimeofday(struct timespec *tv)
 	gettimeofday(&now, NULL);
 	timersub(&tv_in, &now, &local_offset);
 	time_unlock(flags);
+	clock_was_set();
 
 	return(0);
 }
diff -puN arch/um/kernel/time_kern.c~uml-fix-timers arch/um/kernel/time_kern.c
--- linux-2.6.git/arch/um/kernel/time_kern.c~uml-fix-timers	2005-05-21 18:38:18.000000000 +0200
+++ linux-2.6.git-paolo/arch/um/kernel/time_kern.c	2005-05-21 18:38:18.000000000 +0200
@@ -88,52 +88,40 @@ void timer_irq(union uml_pt_regs *regs)
 	}
 }
 
+void time_init_kern(void)
+{
+	struct timespec now;
+
+	do_posix_clock_monotonic_gettime(&now);
+	set_normalized_timespec(&wall_to_monotonic, -now.tv_sec, -now.tv_nsec);
+}
+
+/* This is used during boot only, later it's replaced by
+ * user_time_init_{tt,skas} with alarm_handler, during timer_init() */
 void boot_timer_handler(int sig)
 {
+	unsigned long flags;
 	struct pt_regs regs;
 
 	CHOOSE_MODE((void) 
 		    (UPT_SC(&regs.regs) = (struct sigcontext *) (&sig + 1)),
 		    (void) (regs.regs.skas.is_user = 0));
+	write_seqlock_irqsave(&xtime_lock, flags);
 	do_timer(&regs);
+	write_sequnlock_irqrestore(&xtime_lock, flags);
 }
 
 irqreturn_t um_timer(int irq, void *dev, struct pt_regs *regs)
 {
 	unsigned long flags;
 
-	do_timer(regs);
 	write_seqlock_irqsave(&xtime_lock, flags);
-	timer();
+	do_timer(regs);
+	userspace_timer();
 	write_sequnlock_irqrestore(&xtime_lock, flags);
 	return(IRQ_HANDLED);
 }
 
-long um_time(int __user *tloc)
-{
-	struct timeval now;
-
-	do_gettimeofday(&now);
-	if (tloc) {
- 		if (put_user(now.tv_sec, tloc))
-			now.tv_sec = -EFAULT;
-	}
-	return now.tv_sec;
-}
-
-long um_stime(int __user *tptr)
-{
-	int value;
-	struct timespec new;
-
-	if (get_user(value, tptr))
-                return -EFAULT;
-	new.tv_sec = value;
-	new.tv_nsec = 0;
-	do_settimeofday(&new);
-	return 0;
-}
-
 void timer_handler(int sig, union uml_pt_regs *regs)
 {
 	local_irq_disable();
diff -puN arch/um/include/time_user.h~uml-fix-timers arch/um/include/time_user.h
--- linux-2.6.git/arch/um/include/time_user.h~uml-fix-timers	2005-05-21 18:38:18.000000000 +0200
+++ linux-2.6.git-paolo/arch/um/include/time_user.h	2005-05-21 18:38:18.000000000 +0200
@@ -6,7 +6,7 @@
 #ifndef __TIME_USER_H__
 #define __TIME_USER_H__
 
-extern void timer(void);
+extern void userspace_timer(void);
 extern void switch_timers(int to_real);
 extern void set_interval(int timer_type);
 extern void idle_sleep(int secs);
diff -puN arch/um/sys-i386/sys_call_table.S~uml-fix-timers arch/um/sys-i386/sys_call_table.S
--- linux-2.6.git/arch/um/sys-i386/sys_call_table.S~uml-fix-timers	2005-05-21 18:38:18.000000000 +0200
+++ linux-2.6.git-paolo/arch/um/sys-i386/sys_call_table.S	2005-05-21 18:38:18.000000000 +0200
@@ -7,8 +7,6 @@
 #define sys_vm86old sys_ni_syscall
 #define sys_vm86 sys_ni_syscall
 
-#define sys_stime um_stime
-#define sys_time um_time
 #define old_mmap old_mmap_i386
 
 #include "../../i386/kernel/syscall_table.S"
diff -puN arch/um/sys-x86_64/syscall_table.c~uml-fix-timers arch/um/sys-x86_64/syscall_table.c
--- linux-2.6.git/arch/um/sys-x86_64/syscall_table.c~uml-fix-timers	2005-05-21 18:38:18.000000000 +0200
+++ linux-2.6.git-paolo/arch/um/sys-x86_64/syscall_table.c	2005-05-21 18:38:18.000000000 +0200
@@ -20,11 +20,8 @@
 /*#define sys_set_thread_area sys_ni_syscall
 #define sys_get_thread_area sys_ni_syscall*/
 
-/* For __NR_time. The x86-64 name hopefully will change from sys_time64 to
- * sys_time (since the current situation is bogus). I've sent a patch to cleanup
- * this. Remove below the obsoleted line. */
-#define sys_time64 um_time
-#define sys_time um_time
+/*To remove when x86_64 fixes the syscall name.*/
+#define sys_time64 sys_time
 
 /* On UML we call it this way ("old" means it's not mmap2) */
 #define sys_mmap old_mmap
_

Re: [uml-devel] non-scalar ktime addition and subtraction broken

[Jeff Dike]

On Fri, Jun 02, 2006 at 08:28:37PM +0200, Blaisorblade wrote:
> Ok, since I now I'll never finish it:
> $ ll old-patch-scripts/patches/uml-fix-timers.patch
> -rw-r--r-- 1 paolo paolo 6763 2005-07-24 06:41 
> old-patch-scripts/patches/uml-fix-timers.patch
> 
> I'm attaching this incomplete patch. It won't apply (it was written likely 
> before 2.6.13 but surely after git was born), it likely introduces bugs and I

> *) Rename timer() since it's a global and such a name is a "shooting 
> offense".  Also, it's difficult to find the def with ctags
> currently, because people miss fantasy.

This is now gone, replaced by get_time.  I can rename that if you feel
it's objectionable.

> *) do_timer must be called with xtime_lock held. I'm not sure
> boot_timer_handler needs this, however I don't think it hurts: it simply
> disables irq and takes a spinlock.

Fixed.

> *) wall_to_monotonic must be normalized and have a posititive ts_nsec part,
> see wall_to_monotonic definition and i386 usage in arch/i386/kernel/time.c.
> Otherwise you can get negative tv_nsec results with
> do_posix_clock_monotonic_gettime and its callers, including
> sys_timer_gettime.

Bah, you almost completely diagnosed the bug.  Fixed now.

> *) Remove um_time() and um_stime() syscalls since they are identical to
> system-wide ones.

Fixed.  sys_time64 seems to be gone on x86_64, so I deleted it from
here as well.

> *) Move clock_was_set() from do_gettimeofday to do_settimeofday. Not
> only from the name you guess this is needed, but I indeed verified
> that for i386 it's in arch/i386/kernel/time.c:do_settimeofday().

I had already fixed this.

> *) XXX: Probably do_settimeofday should be copied from i386 to
> replace the current version.
>
> *) XXX: do_[gs]ettimeofday() should use seqlocks like in i386,
> instead of timer_lock() like they do. They also don't synchronize
> with the rest, beyond the performance problems!

You're probably right.  These two are related, and I'm not sure what
to do with them offhand.

				Jeff

Re: [uml-devel] non-scalar ktime addition and subtraction broken

[Blaisorblade]

On Friday 02 June 2006 23:34, Jeff Dike wrote:
> On Fri, Jun 02, 2006 at 08:28:37PM +0200, Blaisorblade wrote:
> > Ok, since I now I'll never finish it:
> > $ ll old-patch-scripts/patches/uml-fix-timers.patch
> > -rw-r--r-- 1 paolo paolo 6763 2005-07-24 06:41
> > old-patch-scripts/patches/uml-fix-timers.patch
> >
> > I'm attaching this incomplete patch. It won't apply (it was written
> > likely before 2.6.13 but surely after git was born), it likely introduces
> > bugs and I
> >
> > *) Rename timer() since it's a global and such a name is a "shooting
> > offense".  Also, it's difficult to find the def with ctags
> > currently, because people miss fantasy.
>
> This is now gone, replaced by get_time.  I can rename that if you feel
> it's objectionable.

I still see (around 2.6.17-rc3) timer() existing in the same place and with 
the same definition - even if it now seems unused:

void timer(void)
{
        gettimeofday(&xtime, NULL);
        timeradd(&xtime, &local_offset, &xtime);
}

> > *) do_timer must be called with xtime_lock held. I'm not sure
> > boot_timer_handler needs this, however I don't think it hurts: it simply
> > disables irq and takes a spinlock.
>
> Fixed.
>
> > *) wall_to_monotonic must be normalized and have a posititive ts_nsec
> > part, see wall_to_monotonic definition and i386 usage in
> > arch/i386/kernel/time.c. Otherwise you can get negative tv_nsec results
> > with
> > do_posix_clock_monotonic_gettime and its callers, including
> > sys_timer_gettime.
>
> Bah, you almost completely diagnosed the bug.  Fixed now.

Yep, however I didn't reproduce any misbehaviour at that time.

> > *) Remove um_time() and um_stime() syscalls since they are identical to
> > system-wide ones.

> Fixed.  sys_time64 seems to be gone on x86_64, so I deleted it from
> here as well.

Yes, I deleted sys_time64 time ago, forgot to update 
arch/um/sys-x86_64/syscall_table.c.

> > *) Move clock_was_set() from do_gettimeofday to do_settimeofday. Not
> > only from the name you guess this is needed, but I indeed verified
> > that for i386 it's in arch/i386/kernel/time.c:do_settimeofday().

> > *) XXX: Probably do_settimeofday should be copied from i386 to
> > replace the current version.
> >
> > *) XXX: do_[gs]ettimeofday() should use seqlocks like in i386,
> > instead of timer_lock() like they do. They also don't synchronize
> > with the rest, beyond the performance problems!
>
> You're probably right.  These two are related, and I'm not sure what
> to do with them offhand.

And that's why I didn't send the patches then in first place - I wanted to 
complete them (I have too many incomplete patches, and too little time to 
finish them :-( ).
-- 
Inform me of my mistakes, so I can keep imitating Homer Simpson's "Doh!".
Paolo Giarrusso, aka Blaisorblade (Skype ID "PaoloGiarrusso", ICQ 215621894)
http://www.user-mode-linux.org/~blaisorblade

Chiacchiera con i tuoi amici in tempo reale! 
 http://it.yahoo.com/mail_it/foot/*http://it.messenger.yahoo.com