[PATCH] Fix clock_gettime to increment monotonically on PV-domain/x86

[PATCH] Fix clock_gettime to increment monotonically on PV-domain/x86

[Atsushi SAKAI]

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

Hi, Keir

  This patch intends to increment do_gettimeofday monotonically.
This is for PV-domain/x86.

Signed-off-by: Atsushi SAKAI <sakaia@jp.fujitsu.com>

By applying patch, the time rollback for SMP is fixed.
This is important fixes for database software.

Thanks
Atsushi SAKAI


[-- Attachment #2: fix_timerollback_pvx86.patch --]
[-- Type: application/octet-stream, Size: 1320 bytes --]

diff -r 089696e0c603 linux-2.6-xen-sparse/arch/i386/kernel/time-xen.c
--- a/linux-2.6-xen-sparse/arch/i386/kernel/time-xen.c	Thu May 17 11:42:46 2007 +0100
+++ b/linux-2.6-xen-sparse/arch/i386/kernel/time-xen.c	Fri Jun 15 18:10:03 2007 +0900
@@ -113,6 +113,8 @@ static struct timespec shadow_tv;
 static struct timespec shadow_tv;
 static u32 shadow_tv_version;
 
+static struct timeval monotonic_tv;
+
 /* Keep track of last time we did processing/updating of jiffies and xtime. */
 static u64 processed_system_time;   /* System time (ns) at last processing. */
 static DEFINE_PER_CPU(u64, processed_system_time);
@@ -413,15 +415,25 @@ void do_gettimeofday(struct timeval *tv)
 			get_time_values_from_xen(cpu);
 			continue;
 		}
+
+		/* for monotonic counting */
+		while (usec >= USEC_PER_SEC) {
+			usec -= USEC_PER_SEC;
+			sec++;
+		}
+		if ( sec > monotonic_tv.tv_sec || 
+			(monotonic_tv.tv_sec == sec && usec > monotonic_tv.tv_usec))
+		{
+			monotonic_tv.tv_sec = sec;
+			monotonic_tv.tv_usec = usec;
+		} else {
+			sec = monotonic_tv.tv_sec;
+			usec = monotonic_tv.tv_usec;
+		}
 	} while (read_seqretry(&xtime_lock, seq) ||
 		 (local_time_version != shadow->version));
 
 	put_cpu();
-
-	while (usec >= USEC_PER_SEC) {
-		usec -= USEC_PER_SEC;
-		sec++;
-	}
 
 	tv->tv_sec = sec;
 	tv->tv_usec = usec;

[-- Attachment #3: Type: text/plain, Size: 138 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

Re: [PATCH] Fix clock_gettime to increment monotonically onPV-domain/x86

[Jan Beulich]

I'm afraid this isn't MP-safe - you're in a (pseudo-)read-locked section of code,
yet write a global variable (and even in two pieces). Jan

>>> Atsushi SAKAI <sakaia@jp.fujitsu.com> 15.06.07 11:47 >>>
Hi, Keir

  This patch intends to increment do_gettimeofday monotonically.
This is for PV-domain/x86.

Signed-off-by: Atsushi SAKAI <sakaia@jp.fujitsu.com>

By applying patch, the time rollback for SMP is fixed.
This is important fixes for database software.

Thanks
Atsushi SAKAI

Re: [PATCH] Fix clock_gettime to increment monotonically onPV-domain/x86

[Keir Fraser]

Yeah, it needs a spinlock. Which is a shame, but it's still going to be much
faster than trapping into the hypervisor, which is the only other way we're
going to be able to achieve guaranteed monotonic time.

We could avoid the lock if we guaranteed monotonic time only per task
(thread). Or is that not really good enough? :-)

 -- Keir

On 15/6/07 11:19, "Jan Beulich" <jbeulich@novell.com> wrote:

> I'm afraid this isn't MP-safe - you're in a (pseudo-)read-locked section of
> code,
> yet write a global variable (and even in two pieces). Jan
> 
>>>> Atsushi SAKAI <sakaia@jp.fujitsu.com> 15.06.07 11:47 >>>
> Hi, Keir
> 
>   This patch intends to increment do_gettimeofday monotonically.
> This is for PV-domain/x86.
> 
> Signed-off-by: Atsushi SAKAI <sakaia@jp.fujitsu.com>
> 
> By applying patch, the time rollback for SMP is fixed.
> This is important fixes for database software.
> 
> Thanks
> Atsushi SAKAI
> 
> 
> 
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xensource.com
> http://lists.xensource.com/xen-devel

Re: [PATCH] Fix clock_gettime to increment monotonically onPV-domain/x86

[Jan Beulich]

An alternative to a spin lock would be to use a 64-bit variable storing the raw
nanosecond value, and use cmpxchg to check/update it. I did it this way for
the clocksource monotonicity:

static cycle_t xen_clocksource_read(void)
{
	int cpu = get_cpu();
	struct shadow_time_info *shadow = &per_cpu(shadow_time, cpu);
	cycle_t ret;

	get_time_values_from_xen(cpu);

	ret = shadow->system_timestamp + get_nsec_offset(shadow);

	put_cpu();

#ifdef CONFIG_SMP
	for (;;) {
		static cycle_t last_ret;
#ifndef CONFIG_64BIT
		cycle_t last = cmpxchg64(&last_ret, 0, 0);
#else
		cycle_t last = last_ret;
#define cmpxchg64 cmpxchg
#endif

		if ((s64)(ret - last) < 0) {
			if (last - ret > permitted_clock_jitter
			    && printk_ratelimit())
				printk(KERN_WARNING "clocksource/%d: "
				       "Time went backwards: "
				       "delta=%Ld shadow=%Lu offset=%Lu\n",
				       cpu, ret - last,
				       shadow->system_timestamp,
				       get_nsec_offset(shadow));
			ret = last;
		}
		if (cmpxchg64(&last_ret, last, ret) == last)
			break;
	}
#endif

	return ret;
}

Jan

>>> Keir Fraser <keir@xensource.com> 15.06.07 12:26 >>>
Yeah, it needs a spinlock. Which is a shame, but it's still going to be much
faster than trapping into the hypervisor, which is the only other way we're
going to be able to achieve guaranteed monotonic time.

We could avoid the lock if we guaranteed monotonic time only per task
(thread). Or is that not really good enough? :-)

 -- Keir

On 15/6/07 11:19, "Jan Beulich" <jbeulich@novell.com> wrote:

> I'm afraid this isn't MP-safe - you're in a (pseudo-)read-locked section of
> code,
> yet write a global variable (and even in two pieces). Jan
> 
>>>> Atsushi SAKAI <sakaia@jp.fujitsu.com> 15.06.07 11:47 >>>
> Hi, Keir
> 
>   This patch intends to increment do_gettimeofday monotonically.
> This is for PV-domain/x86.
> 
> Signed-off-by: Atsushi SAKAI <sakaia@jp.fujitsu.com>
> 
> By applying patch, the time rollback for SMP is fixed.
> This is important fixes for database software.
> 
> Thanks
> Atsushi SAKAI
> 
> 
> 
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xensource.com 
> http://lists.xensource.com/xen-devel 

Re: [PATCH] Fix clock_gettime to increment monotonically onPV-domain/x86

[Keir Fraser]

A spinlock is almost certainly no slower. Since the critical region is so
tiny the likelihood of spinning is very small. And the spin_lock() fast path
is probably faster than a CMPXCHG8B.

 -- Keir

On 15/6/07 12:12, "Jan Beulich" <jbeulich@novell.com> wrote:

> An alternative to a spin lock would be to use a 64-bit variable storing the
> raw
> nanosecond value, and use cmpxchg to check/update it. I did it this way for
> the clocksource monotonicity:
> 
> static cycle_t xen_clocksource_read(void)
> {
> int cpu = get_cpu();
> struct shadow_time_info *shadow = &per_cpu(shadow_time, cpu);
> cycle_t ret;
> 
> get_time_values_from_xen(cpu);
> 
> ret = shadow->system_timestamp + get_nsec_offset(shadow);
> 
> put_cpu();
> 
> #ifdef CONFIG_SMP
> for (;;) {
> static cycle_t last_ret;
> #ifndef CONFIG_64BIT
> cycle_t last = cmpxchg64(&last_ret, 0, 0);
> #else
> cycle_t last = last_ret;
> #define cmpxchg64 cmpxchg
> #endif
> 
> if ((s64)(ret - last) < 0) {
> if (last - ret > permitted_clock_jitter
>    && printk_ratelimit())
> printk(KERN_WARNING "clocksource/%d: "
>       "Time went backwards: "
>       "delta=%Ld shadow=%Lu offset=%Lu\n",
>       cpu, ret - last,
>       shadow->system_timestamp,
>       get_nsec_offset(shadow));
> ret = last;
> }
> if (cmpxchg64(&last_ret, last, ret) == last)
> break;
> }
> #endif
> 
> return ret;
> }
> 
> Jan
> 
>>>> Keir Fraser <keir@xensource.com> 15.06.07 12:26 >>>
> Yeah, it needs a spinlock. Which is a shame, but it's still going to be much
> faster than trapping into the hypervisor, which is the only other way we're
> going to be able to achieve guaranteed monotonic time.
> 
> We could avoid the lock if we guaranteed monotonic time only per task
> (thread). Or is that not really good enough? :-)
> 
>  -- Keir
> 
> On 15/6/07 11:19, "Jan Beulich" <jbeulich@novell.com> wrote:
> 
>> I'm afraid this isn't MP-safe - you're in a (pseudo-)read-locked section of
>> code,
>> yet write a global variable (and even in two pieces). Jan
>> 
>>>>> Atsushi SAKAI <sakaia@jp.fujitsu.com> 15.06.07 11:47 >>>
>> Hi, Keir
>> 
>>   This patch intends to increment do_gettimeofday monotonically.
>> This is for PV-domain/x86.
>> 
>> Signed-off-by: Atsushi SAKAI <sakaia@jp.fujitsu.com>
>> 
>> By applying patch, the time rollback for SMP is fixed.
>> This is important fixes for database software.
>> 
>> Thanks
>> Atsushi SAKAI
>> 
>> 
>> 
>> _______________________________________________
>> Xen-devel mailing list
>> Xen-devel@lists.xensource.com
>> http://lists.xensource.com/xen-devel
> 
> 
> 
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xensource.com
> http://lists.xensource.com/xen-devel

Re: [PATCH] Fix clock_gettime to incrementmonotonically onPV-domain/x86

[Atsushi SAKAI]

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

Hi, Keir and Jan

 Thank you for various discussions.
I rewrite it to spin_lock version.

Database software uses this kind of information.
And problematic is running OK on Native and Not on Xen

Thanks
Atsushi SAKAI



Keir Fraser <keir@xensource.com> wrote:

> Yeah, it needs a spinlock. Which is a shame, but it's still going to be much
> faster than trapping into the hypervisor, which is the only other way we're
> going to be able to achieve guaranteed monotonic time.
> 
> We could avoid the lock if we guaranteed monotonic time only per task
> (thread). Or is that not really good enough? :-)
> 
>  -- Keir
> 
> On 15/6/07 11:19, "Jan Beulich" <jbeulich@novell.com> wrote:
> 
> > I'm afraid this isn't MP-safe - you're in a (pseudo-)read-locked section of
> > code,
> > yet write a global variable (and even in two pieces). Jan
> > 
> >>>> Atsushi SAKAI <sakaia@jp.fujitsu.com> 15.06.07 11:47 >>>
> > Hi, Keir
> > 
> >   This patch intends to increment do_gettimeofday monotonically.
> > This is for PV-domain/x86.
> > 
> > Signed-off-by: Atsushi SAKAI <sakaia@jp.fujitsu.com>
> > 
> > By applying patch, the time rollback for SMP is fixed.
> > This is important fixes for database software.
> > 
> > Thanks
> > Atsushi SAKAI
> > 
> > 
> > 
> > _______________________________________________
> > Xen-devel mailing list
> > Xen-devel@lists.xensource.com
> > http://lists.xensource.com/xen-devel
> 

[-- Attachment #2: fix_pvx86_timerollback_use_spinlock.patch --]
[-- Type: application/octet-stream, Size: 1132 bytes --]

diff -r 089696e0c603 linux-2.6-xen-sparse/arch/i386/kernel/time-xen.c
--- a/linux-2.6-xen-sparse/arch/i386/kernel/time-xen.c	Thu May 17 11:42:46 2007 +0100
+++ b/linux-2.6-xen-sparse/arch/i386/kernel/time-xen.c	Fri Jun 15 20:07:01 2007 +0900
@@ -113,6 +113,9 @@ static struct timespec shadow_tv;
 static struct timespec shadow_tv;
 static u32 shadow_tv_version;
 
+static struct timeval monotonic_tv;
+static spinlock_t monotonic_lock;
+
 /* Keep track of last time we did processing/updating of jiffies and xtime. */
 static u64 processed_system_time;   /* System time (ns) at last processing. */
 static DEFINE_PER_CPU(u64, processed_system_time);
@@ -422,6 +425,18 @@ void do_gettimeofday(struct timeval *tv)
 		usec -= USEC_PER_SEC;
 		sec++;
 	}
+	/* for monotonic counting */
+	spin_lock(&monotonic_lock);
+	if ( sec > monotonic_tv.tv_sec || 
+		(monotonic_tv.tv_sec == sec && usec > monotonic_tv.tv_usec))
+	{
+		monotonic_tv.tv_sec = sec;
+		monotonic_tv.tv_usec = usec;
+	} else {
+		sec = monotonic_tv.tv_sec;
+		usec = monotonic_tv.tv_usec;
+	}
+	spin_unlock(&monotonic_lock);
 
 	tv->tv_sec = sec;
 	tv->tv_usec = usec;

[-- Attachment #3: Type: text/plain, Size: 138 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

Re: [PATCH] Fix clock_gettime to increment monotonically onPV-domain/x86

[John Levon]

On Fri, Jun 15, 2007 at 01:12:21PM +0200, Jan Beulich wrote:

> An alternative to a spin lock would be to use a 64-bit variable storing the raw
> nanosecond value, and use cmpxchg to check/update it. I did it this way for
> the clocksource monotonicity:

This is essentially what we've got now in Solaris. It seems like a
terrible shame not to just fix it in Xen, especially given all that
traffic from all CPUs to 'last_ret'.

regards
john

Re: [PATCH] Fix clock_gettime to increment monotonically onPV-domain/x86

[Keir Fraser]

On 15/6/07 13:47, "John Levon" <levon@movementarian.org> wrote:

> On Fri, Jun 15, 2007 at 01:12:21PM +0200, Jan Beulich wrote:
> 
>> An alternative to a spin lock would be to use a 64-bit variable storing the
>> raw
>> nanosecond value, and use cmpxchg to check/update it. I did it this way for
>> the clocksource monotonicity:
> 
> This is essentially what we've got now in Solaris. It seems like a
> terrible shame not to just fix it in Xen, especially given all that
> traffic from all CPUs to 'last_ret'.

How would we fix it in Xen in a way that is faster and more scalable?

 -- Keir

Re: [PATCH] Fix clock_gettime to increment monotonically onPV-domain/x86

[John Levon]

On Fri, Jun 15, 2007 at 01:59:36PM +0100, Keir Fraser wrote:

> >> An alternative to a spin lock would be to use a 64-bit variable storing the
> >> raw
> >> nanosecond value, and use cmpxchg to check/update it. I did it this way for
> >> the clocksource monotonicity:
> > 
> > This is essentially what we've got now in Solaris. It seems like a
> > terrible shame not to just fix it in Xen, especially given all that
> > traffic from all CPUs to 'last_ret'.
> 
> How would we fix it in Xen in a way that is faster and more scalable?

A good question :)

One thing we've considered is losing some precision based upon how much
of a delta there is between the real CPUs (i.e. drop lower bits and
round up). But we're still (slowly) looking into the problem.

regards
john

Re: [PATCH] Fix clock_gettime to increment monotonically onPV-domain/x86

[Keir Fraser]

On 15/6/07 14:08, "John Levon" <levon@movementarian.org> wrote:

>>> This is essentially what we've got now in Solaris. It seems like a
>>> terrible shame not to just fix it in Xen, especially given all that
>>> traffic from all CPUs to 'last_ret'.
>> 
>> How would we fix it in Xen in a way that is faster and more scalable?
> 
> A good question :)
> 
> One thing we've considered is losing some precision based upon how much
> of a delta there is between the real CPUs (i.e. drop lower bits and
> round up). But we're still (slowly) looking into the problem.

IIUC this would make it less likely to see time going backwards, but when
you do it'll be by a lot more (the size of your precision granularity), and
it'll occur when your time values are unlucky enough to be just on the wrong
sides of a boundary between two time intervals which map to different
lower-precision time values.

I believe it's a pretty fundamental property of a monotonically-increasing
counter in a distributed system that communication is required to implement
it. Time is a funny thing.

 -- Keir

Re: [PATCH] Fix clock_gettime to increment monotonicallyonPV-domain/x86

[Atsushi SAKAI]

Hi, John

Is there any plan to use vsyscall for clock_gettime on PV-dom?
I think this is the best solution for this.

But this kind of change is very large.

In this meaning, my patch is temporaly solution like within 4CPU.

Thanks
Atsushi SAKAI


John Levon <levon@movementarian.org> wrote:

> On Fri, Jun 15, 2007 at 01:59:36PM +0100, Keir Fraser wrote:
> 
> > >> An alternative to a spin lock would be to use a 64-bit variable storing the
> > >> raw
> > >> nanosecond value, and use cmpxchg to check/update it. I did it this way for
> > >> the clocksource monotonicity:
> > > 
> > > This is essentially what we've got now in Solaris. It seems like a
> > > terrible shame not to just fix it in Xen, especially given all that
> > > traffic from all CPUs to 'last_ret'.
> > 
> > How would we fix it in Xen in a way that is faster and more scalable?
> 
> A good question :)
> 
> One thing we've considered is losing some precision based upon how much
> of a delta there is between the real CPUs (i.e. drop lower bits and
> round up). But we're still (slowly) looking into the problem.
> 
> regards
> john
> 
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xensource.com
> http://lists.xensource.com/xen-devel

Re: [PATCH] Fix clock_gettime to increment monotonically onPV-domain/x86

[John Levon]

On Fri, Jun 15, 2007 at 02:21:12PM +0100, Keir Fraser wrote:

> >>> This is essentially what we've got now in Solaris. It seems like a
> >>> terrible shame not to just fix it in Xen, especially given all that
> >>> traffic from all CPUs to 'last_ret'.
> >> 
> >> How would we fix it in Xen in a way that is faster and more scalable?
> > 
> > A good question :)
> > 
> > One thing we've considered is losing some precision based upon how much
> > of a delta there is between the real CPUs (i.e. drop lower bits and
> > round up). But we're still (slowly) looking into the problem.
> 
> IIUC this would make it less likely to see time going backwards, but when
> you do it'll be by a lot more (the size of your precision granularity), and
> it'll occur when your time values are unlucky enough to be just on the wrong
> sides of a boundary between two time intervals which map to different
> lower-precision time values.

The idea is that it would never be wrong enough to hit that case (taken
to extremes we wouldn't expect to see it go backwards by a minute!)

> I believe it's a pretty fundamental property of a monotonically-increasing
> counter in a distributed system that communication is required to implement
> it. Time is a funny thing.

Well. It's proven a reasonable assumption for us on the x86 systems
we're supporting that the TSC difference between CPUs is stable enough
for us to provide effective monotonicity. This is much harder to do from
a virtual CPU for obvious reasons :)

regards
john

Re: [PATCH] Fix clock_gettime to increment monotonically onPV-domain/x86

[Keir Fraser]

On 15/6/07 15:00, "John Levon" <levon@movementarian.org> wrote:

>> IIUC this would make it less likely to see time going backwards, but when
>> you do it'll be by a lot more (the size of your precision granularity), and
>> it'll occur when your time values are unlucky enough to be just on the wrong
>> sides of a boundary between two time intervals which map to different
>> lower-precision time values.
> 
> The idea is that it would never be wrong enough to hit that case (taken
> to extremes we wouldn't expect to see it go backwards by a minute!)

Then I don't understand what you're proposing (I thought you were just
shaving off least-significant bits, but it must be smarter than that).

 -- Keir

Re: [PATCH] Fix clock_gettime to increment monotonically onPV-domain/x86

[John Levon]

On Fri, Jun 15, 2007 at 03:18:16PM +0100, Keir Fraser wrote:

> >> IIUC this would make it less likely to see time going backwards, but when
> >> you do it'll be by a lot more (the size of your precision granularity), and
> >> it'll occur when your time values are unlucky enough to be just on the wrong
> >> sides of a boundary between two time intervals which map to different
> >> lower-precision time values.
> > 
> > The idea is that it would never be wrong enough to hit that case (taken
> > to extremes we wouldn't expect to see it go backwards by a minute!)
> 
> Then I don't understand what you're proposing (I thought you were just
> shaving off least-significant bits, but it must be smarter than that).

Sorry, I misunderstood you. Yes, you're right, this doesn't seem
workable. Bah.

john

Re: [PATCH] Fix clock_gettime to incrementmonotonicallyonPV-domain/x86

[Atsushi SAKAI]

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

Hi, Keir

  I accidentally lent Xeon E5310(Quad-core) x 2.
And I test it with 8thread 1hour running.(8thread version of pvx86test)
It works fine without seeing softlockup with attached patch.

In 8thread running,
top shows 300-400 % of CPU consumption.
and it's ratio is 3.0%us 32.9%sy 0.0%ni 60.5%id 0.0%wa 0.0%hi 0.0%si 3.6%st

xentop shows 600 - 700 % of CPU consumption.

Signed-off-by: Atsushi SAKAI <sakaia@jp.fujitsu.com>

Thanks
Atsushi SAKAI



[-- Attachment #2: fix_pvx86_timebackwards_take2.patch --]
[-- Type: application/octet-stream, Size: 1404 bytes --]

diff -r a413dd61e7e5 arch/i386/kernel/time-xen.c
--- a/arch/i386/kernel/time-xen.c	Fri Jun 15 13:33:47 2007 -0600
+++ b/arch/i386/kernel/time-xen.c	Tue Jun 19 16:41:51 2007 +0900
@@ -113,6 +113,9 @@ static struct timespec shadow_tv;
 static struct timespec shadow_tv;
 static u32 shadow_tv_version;
 
+static struct timeval monotonic_tv;
+static spinlock_t monotonic_lock = SPIN_LOCK_UNLOCKED;
+
 /* Keep track of last time we did processing/updating of jiffies and xtime. */
 static u64 processed_system_time;   /* System time (ns) at last processing. */
 static DEFINE_PER_CPU(u64, processed_system_time);
@@ -422,6 +425,18 @@ void do_gettimeofday(struct timeval *tv)
 		usec -= USEC_PER_SEC;
 		sec++;
 	}
+	/* for monotonic counting */
+	spin_lock(&monotonic_lock);
+	if ( sec > monotonic_tv.tv_sec || 
+		(monotonic_tv.tv_sec == sec && usec > monotonic_tv.tv_usec))
+	{
+		monotonic_tv.tv_sec = sec;
+		monotonic_tv.tv_usec = usec;
+	} else {
+		sec = monotonic_tv.tv_sec;
+		usec = monotonic_tv.tv_usec;
+	}
+	spin_unlock(&monotonic_lock);
 
 	tv->tv_sec = sec;
 	tv->tv_usec = usec;
@@ -471,6 +486,11 @@ int do_settimeofday(struct timespec *tv)
 		__normalize_time(&sec, &nsec);
 		__update_wallclock(sec, nsec);
 	}
+
+	spin_lock(&monotonic_lock);
+	monotonic_tv.tv_sec = sec;
+	monotonic_tv.tv_usec = nsec / NSEC_PER_USEC;
+	spin_unlock(&monotonic_lock);
 
 	write_sequnlock_irq(&xtime_lock);
 

[-- Attachment #3: Type: text/plain, Size: 138 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel