non-scalar ktime addition and subtraction broken

PATCH Jeff Dike 3 participants 6 messages Jun 2, 2006 – Jun 4, 2006 User-mode Linux (UML)

Share & tools

Jeff Dike

author

2006-06-02 03:08 UTC #0 lore raw

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

include/linux/ktime.h +4 -2

Index: linux-2.6.17-mm/include/linux/ktime.h
===================================================================
@@ -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.

kernel/hrtimer.c +2 -1

Index: linux-2.6.17-mm/kernel/hrtimer.c
===================================================================
@@ -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;

-------------------------------------------------------
All the advantages of Linux Managed Hosting--Without the Cost and Risk! Fully trained technicians. The highest number of Red Hat certifications in the hosting industry. Fanatical Support. Click to learn more
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=107521&bid=248729&dat=121642
_______________________________________________
User-mode-linux-devel mailing list [email protected]
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Thomas Gleixner

2006-06-02 06:53 UTC #1 lore raw

Quoted 18 lines · 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.

Quoted 8 lines

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

Jeff Dike

author

2006-06-02 15:18 UTC #2 lore raw

Quoted 3 lines · Thomas Gleixner

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

_______________________________________________
User-mode-linux-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Blaisorblade

2006-06-02 18:29 UTC #3 lore raw

Quoted 7 lines · Jeff Dike

Quoted 3 lines · Thomas Gleixner
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).

Signature · 3 lines

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

*) 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 <[email protected]>

---

 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(-)

arch/um/kernel/time.c renamed from arch/um/kernel/time.c~uml-fix-timers +5 -8

diff -puN arch/um/kernel/time.c~uml-fix-timers arch/um/kernel/time.c
@@ -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);
 }

arch/um/kernel/time_kern.c renamed from arch/um/kernel/time_kern.c~uml-fix-timers +15 ~~-27~~

67 lines not on this page · raw message

arch/um/include/time_user.h renamed from arch/um/include/time_user.h~uml-fix-timers +1 -1

diff -puN arch/um/include/time_user.h~uml-fix-timers arch/um/include/time_user.h
@@ -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);

arch/um/sys-i386/sys_call_table.S renamed from arch/um/sys-i386/sys_call_table.S~uml-fix-timers +0 -2

diff -puN arch/um/sys-i386/sys_call_table.S~uml-fix-timers arch/um/sys-i386/sys_call_table.S
@@ -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"

arch/um/sys-x86_64/syscall_table.c renamed from arch/um/sys-x86_64/syscall_table.c~uml-fix-timers +2 -5

diff -puN arch/um/sys-x86_64/syscall_table.c~uml-fix-timers arch/um/sys-x86_64/syscall_table.c
@@ -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

Jeff Dike

author

2006-06-02 21:35 UTC #4 lore raw

Quoted 11 lines · Blaisorblade

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.

Quoted 3 lines

*) 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.

Quoted 5 lines

*) 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.

Quoted 2 lines

*) 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.

Quoted 3 lines

*) 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.

Quoted 6 lines

*) 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

_______________________________________________
User-mode-linux-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/user-mode-linux-devel

Blaisorblade

2006-06-04 15:15 UTC #5 lore raw

Quoted 10 lines · Jeff Dike

Quoted 9 lines · Blaisorblade
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

Quoted 6 lines

Quoted 3 lines
*) 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);
}

Quoted 6 lines

Quoted 3 lines
*) 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.

Quoted 8 lines

Quoted 6 lines
*) 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.

Quoted 5 lines

Quoted 2 lines
*) 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.

Quoted 7 lines

Quoted 7 lines
*) 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.

Quoted 6 lines

Quoted 3 lines
*) 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 :-( ).

Signature · 6 lines

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