[PATCH] Add an offset in the cyc2ns computation to fix sched_clock jumps

[PATCH] Add an offset in the cyc2ns computation to fix sched_clock jumps

[Guillaume Chazarain]

Hello,

The scheduling problems I reported in the thread:
http://lkml.org/lkml/2007/3/3/128
are caused by the set_cyc2ns_scale() function called when the CPU speed changes.
Changing the scale causes a warp in the value returned by sched_clock().

The attached patch fixes the problem by adding an offset to the cyc2ns code to
smooth CPU frequency transitions. It also makes the cyc2ns parameters
per-CPU as cpufreq seems to support SMP but I don't have the hardware
to test. If you want
a version without the per-CPU or irqsave stuff, just ask.

Although it solved all my scheduler issues, it may not be fully satisfactory
as for example my TSC can run at a frequency as low as 350 MHz when the CPU is
idle and slowed down to the max at 798 MHz by ondemand. So in this case,
sched_clock() does not return nanoseconds as it thinks it does. Hopefully this
is a non-issue as the scheduler is not stressed when the CPU is idle.

For me, this is needed in 2.6.21 if I want to be able to listen to music while
compiling a kernel using the ondemand governor.

Thanks.

Signed-off-by: Guillaume Chazarain <guichaz@yahoo.fr>
---

diff -r fb83e6d92a4c arch/i386/kernel/tsc.c
--- a/arch/i386/kernel/tsc.c
+++ b/arch/i386/kernel/tsc.c
@@ -10,6 +10,7 @@
 #include <linux/jiffies.h>
 #include <linux/init.h>
 #include <linux/dmi.h>
+#include <linux/percpu.h>

 #include <asm/delay.h>
 #include <asm/tsc.h>
@@ -79,20 +80,57 @@ static inline int check_tsc_unstable(voi
  *  cyc2ns_scale is limited to 10^6 * 2^10, which fits in 32 bits.
  *  (mathieu.desnoyers@polymtl.ca)
  *
+ *  ns += offset to avoid sched_clock jumps with cpufreq (guichaz@yahoo.fr)
+ *
  *			-johnstul@us.ibm.com "math is hard, lets go shopping!"
  */
-static unsigned long cyc2ns_scale __read_mostly;
-
 #define CYC2NS_SCALE_FACTOR 10 /* 2^10, carefully chosen */

-static inline void set_cyc2ns_scale(unsigned long cpu_khz)
-{
-	cyc2ns_scale = (1000000 << CYC2NS_SCALE_FACTOR)/cpu_khz;
+struct cyc2ns_params {
+	unsigned long scale;
+	unsigned long long offset;
+};
+DEFINE_PER_CPU(struct cyc2ns_params, cyc2ns) __read_mostly;
+
+static inline unsigned long long __cycles_2_ns(struct cyc2ns_params *params,
+					       unsigned long long cyc)
+{
+	return ((cyc * params->scale) >> CYC2NS_SCALE_FACTOR) + params->offset;
 }

 static inline unsigned long long cycles_2_ns(unsigned long long cyc)
 {
-	return (cyc * cyc2ns_scale) >> CYC2NS_SCALE_FACTOR;
+	struct cyc2ns_params *params;
+	unsigned long flags;
+	unsigned long long ns;
+
+	params = &get_cpu_var(cyc2ns);
+
+	local_irq_save(flags);
+	ns = __cycles_2_ns(params, cyc);
+	local_irq_restore(flags);
+
+	put_cpu_var(cyc2ns);
+	return ns;
+}
+
+static void set_cyc2ns_scale(unsigned long cpu_khz)
+{
+	struct cyc2ns_params *params;
+	unsigned long flags;
+	unsigned long long tsc_now, ns_now;
+
+	get_scheduled_cycles(tsc_now);
+	params = &get_cpu_var(cyc2ns);
+
+	local_irq_save(flags);
+	ns_now = __cycles_2_ns(params, tsc_now);
+
+	params->scale = (1000000 << CYC2NS_SCALE_FACTOR)/cpu_khz;
+	params->offset += ns_now - __cycles_2_ns(params, tsc_now);
+	local_irq_restore(flags);
+
+	put_cpu_var(cyc2ns);
 }

 /*


-- 
Guillaume

Re: [PATCH] Add an offset in the cyc2ns computation to fix sched_clock jumps

[Andi Kleen]

On Friday 16 March 2007 19:14, Guillaume Chazarain wrote:
> Hello,
> 
> The scheduling problems I reported in the thread:
> http://lkml.org/lkml/2007/3/3/128
> are caused by the set_cyc2ns_scale() function called when the CPU speed changes.
> Changing the scale causes a warp in the value returned by sched_clock().

I already fixed this myself in a similar way (but didn't push it out yet) 

But for .21 I ended up deciding on your revert patch, even though it will give bad
performance.

-Andi

Re: [PATCH] Add an offset in the cyc2ns computation to fix sched_clock jumps

[john stultz]

On Fri, 2007-03-16 at 19:14 +0100, Guillaume Chazarain wrote:
> Hello,
> 
> The scheduling problems I reported in the thread:
> http://lkml.org/lkml/2007/3/3/128
> are caused by the set_cyc2ns_scale() function called when the CPU speed changes.
> Changing the scale causes a warp in the value returned by sched_clock().
> 
> The attached patch fixes the problem by adding an offset to the cyc2ns code to
> smooth CPU frequency transitions. It also makes the cyc2ns parameters
> per-CPU as cpufreq seems to support SMP but I don't have the hardware
> to test. If you want
> a version without the per-CPU or irqsave stuff, just ask.

Oh great! This has been a long standing issue I've never managed to get
around to and your approach to fixing it is simpler then what I was
thinking it would take.

Thanks for knocking this off!

> Although it solved all my scheduler issues, it may not be fully satisfactory
> as for example my TSC can run at a frequency as low as 350 MHz when the CPU is
> idle and slowed down to the max at 798 MHz by ondemand. So in this case,
> sched_clock() does not return nanoseconds as it thinks it does. Hopefully this
> is a non-issue as the scheduler is not stressed when the CPU is idle.

Hmm.. It drops to 350MHz on idle, but only ~800Mhz by on-demand? That
sounds more like the C3 idle TSC halt issue.

> For me, this is needed in 2.6.21 if I want to be able to listen to music while
> compiling a kernel using the ondemand governor.
> 
> Thanks.
> 
> Signed-off-by: Guillaume Chazarain <guichaz@yahoo.fr>

Acked-by: John Stultz <johnstul@us.ibm.com>

Re: [PATCH] Add an offset in the cyc2ns computation to fix sched_clock jumps

[Daniel Walker]

On Fri, 2007-03-16 at 19:14 +0100, Guillaume Chazarain wrote:
> Hello,
> 
> The scheduling problems I reported in the thread:
> http://lkml.org/lkml/2007/3/3/128
> are caused by the set_cyc2ns_scale() function called when the CPU speed changes.
> Changing the scale causes a warp in the value returned by sched_clock().
> 

Did you explain what the "werirdnes" was exactly? If not, could you?

Daniel

Re: [PATCH] Add an offset in the cyc2ns computation to fix sched_clock jumps

[Andreas Kleen]

Am Fr 16.03.2007 19:30 schrieb Daniel Walker <dwalker@mvista.com>:

> On Fri, 2007-03-16 at 19:14 +0100, Guillaume Chazarain wrote:
> > Hello,
> >
> > The scheduling problems I reported in the thread:
> > http://lkml.org/lkml/2007/3/3/128
> > are caused by the set_cyc2ns_scale() function called when the CPU
> > speed changes.
> > Changing the scale causes a warp in the value returned by
> > sched_clock().
> >
>
> Did you explain what the "werirdnes" was exactly? If not, could you?

I fixed this in my own version of the change by marking it unstable
during the transition
(concept stolen from Jiri's patch). Basically watch the notifiers for
before/after
and while the transition is in progress always ask for that underlying
monotonic ktime.

-Andi

Re: [PATCH] Add an offset in the cyc2ns computation to fix sched_clock jumps

[Guillaume Chazarain]

2007/3/16, Daniel Walker <dwalker@mvista.com>:
> Did you explain what the "werirdnes" was exactly? If not, could you?

I didn't track these weirdnesses in the scheduler code, but the symptom
is audio skipping and the mouse stops moving when the CPU becomes
busy and the ondemand governor increases the frequency. This lasts for
0.1~0.5 seconds and after that everything is fine.

Thank you all for the quick responses.

-- 
Guillaume

Re: [PATCH] Add an offset in the cyc2ns computation to fix sched_clock jumps

[Guillaume Chazarain]

2007/3/16, Andi Kleen <ak@suse.de>:
> I already fixed this myself in a similar way (but didn't push it out yet)

Out of insatiable curiosity, I'd be interested in seeing what the
patch looks like
if you agree.

Thanks.

-- 
Guillaume

Re: [PATCH] Add an offset in the cyc2ns computation to fix sched_clock jumps

[Mathieu Desnoyers]

Hi Guillaume,

I understand your need for a working system, but the impression I get
is that this looks too much like yet another level of band-aid over a
broken architecture : AMD 7th and 8th generations, which does not give a
synchronized TSC.

The patch you suggest may work for scheduler purposes, but I wonder if
other parts of the kernel suffers from those TSC inconsistencies and
therefore would need to have this problem addressed differently that
smoothing the per-cpu frequency changes.

The approach you use implies hooking in the frequency change callback,
but it does not deal with frequency scaling due to temperature related
events, and does not, as I recall, deal with frequency scaling in halt
mode. It may also have problems with the values in the period of time
close to the frequency change.

For what it's worth, I would be tempted to use a "simple" approach for
these broken architectures, which would give a monotonic clock source.
Either :

- Use HPET or PM, as suggested by AMD. http://lkml.org/lkml/2005/11/4/173
  For some reasons, x86_64 does not use it for sched_clock, because it
  takes too long to access and is not enabled before the scheduler. I
  don't disagree about optimizing for broken hardware, except when it
  implies multiple layers of band-aids.

- I am currently developing a completely monotonic clock source for
  tracing purposes on those AMD systems. It uses LOCKed atomic operation
  to update the "global" last_tsc value to the count of the CPU with
  highest TSC value at each TSC read and increments this global TSC
  count of the amount of cycles necessary to read the TSC by the other
  CPUs to generate a logical clock. I also plan to update this global
  last_tsc every timer tick to give a higher bound to time accuracy.
  This is a workaround that :
  - Does not scale perfectly (uses locked atomic operation, shares a
    variable between the CPUs, therefore causes contention)
  - Takes about 225 cycles per TSC read instead of 181.
  - Requires an IPI every timer tick.
  - Give a worse case time precision of 1/HZ (1ms to 10ms).
  - Can get a much better time precision by sending an IPI to each CPU
    in a special read operation if necessary, but this is awfully slow.
  - Gives the time in cycles since boot, but does not match perfectly a
    conversion from cycles to ns, since the scaling value is inaccurate.

Therefore, depending on your needs (accuracy vs granularity), I would be
tempted to use either the HPET or my monotonic TSC workaround.

Regards,

Mathieu

* Guillaume Chazarain (guichaz@gmail.com) wrote:
> Hello,
> 
> The scheduling problems I reported in the thread:
> http://lkml.org/lkml/2007/3/3/128
> are caused by the set_cyc2ns_scale() function called when the CPU speed 
> changes.
> Changing the scale causes a warp in the value returned by sched_clock().
> 
> The attached patch fixes the problem by adding an offset to the cyc2ns code 
> to
> smooth CPU frequency transitions. It also makes the cyc2ns parameters
> per-CPU as cpufreq seems to support SMP but I don't have the hardware
> to test. If you want
> a version without the per-CPU or irqsave stuff, just ask.
> 
> Although it solved all my scheduler issues, it may not be fully satisfactory
> as for example my TSC can run at a frequency as low as 350 MHz when the CPU 
> is
> idle and slowed down to the max at 798 MHz by ondemand. So in this case,
> sched_clock() does not return nanoseconds as it thinks it does. Hopefully 
> this
> is a non-issue as the scheduler is not stressed when the CPU is idle.
> 
> For me, this is needed in 2.6.21 if I want to be able to listen to music 
> while
> compiling a kernel using the ondemand governor.
> 
> Thanks.
> 
> Signed-off-by: Guillaume Chazarain <guichaz@yahoo.fr>
> ---
> 
> diff -r fb83e6d92a4c arch/i386/kernel/tsc.c
> --- a/arch/i386/kernel/tsc.c
> +++ b/arch/i386/kernel/tsc.c
> @@ -10,6 +10,7 @@
> #include <linux/jiffies.h>
> #include <linux/init.h>
> #include <linux/dmi.h>
> +#include <linux/percpu.h>
> 
> #include <asm/delay.h>
> #include <asm/tsc.h>
> @@ -79,20 +80,57 @@ static inline int check_tsc_unstable(voi
>  *  cyc2ns_scale is limited to 10^6 * 2^10, which fits in 32 bits.
>  *  (mathieu.desnoyers@polymtl.ca)
>  *
> + *  ns += offset to avoid sched_clock jumps with cpufreq (guichaz@yahoo.fr)
> + *
>  *			-johnstul@us.ibm.com "math is hard, lets go 
>  shopping!"
>  */
> -static unsigned long cyc2ns_scale __read_mostly;
> -
> #define CYC2NS_SCALE_FACTOR 10 /* 2^10, carefully chosen */
> 
> -static inline void set_cyc2ns_scale(unsigned long cpu_khz)
> -{
> -	cyc2ns_scale = (1000000 << CYC2NS_SCALE_FACTOR)/cpu_khz;
> +struct cyc2ns_params {
> +	unsigned long scale;
> +	unsigned long long offset;
> +};
> +DEFINE_PER_CPU(struct cyc2ns_params, cyc2ns) __read_mostly;
> +
> +static inline unsigned long long __cycles_2_ns(struct cyc2ns_params 
> *params,
> +					       unsigned long long cyc)
> +{
> +	return ((cyc * params->scale) >> CYC2NS_SCALE_FACTOR) + 
> params->offset;
> }
> 
> static inline unsigned long long cycles_2_ns(unsigned long long cyc)
> {
> -	return (cyc * cyc2ns_scale) >> CYC2NS_SCALE_FACTOR;
> +	struct cyc2ns_params *params;
> +	unsigned long flags;
> +	unsigned long long ns;
> +
> +	params = &get_cpu_var(cyc2ns);
> +
> +	local_irq_save(flags);
> +	ns = __cycles_2_ns(params, cyc);
> +	local_irq_restore(flags);
> +
> +	put_cpu_var(cyc2ns);
> +	return ns;
> +}
> +
> +static void set_cyc2ns_scale(unsigned long cpu_khz)
> +{
> +	struct cyc2ns_params *params;
> +	unsigned long flags;
> +	unsigned long long tsc_now, ns_now;
> +
> +	get_scheduled_cycles(tsc_now);
> +	params = &get_cpu_var(cyc2ns);
> +
> +	local_irq_save(flags);
> +	ns_now = __cycles_2_ns(params, tsc_now);
> +
> +	params->scale = (1000000 << CYC2NS_SCALE_FACTOR)/cpu_khz;
> +	params->offset += ns_now - __cycles_2_ns(params, tsc_now);
> +	local_irq_restore(flags);
> +
> +	put_cpu_var(cyc2ns);
> }
> 
> /*
> 
> 
> -- 
> Guillaume

-- 
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Re: [PATCH] Add an offset in the cyc2ns computation to fix sched_clock jumps

[Guillaume Chazarain]

2007/3/18, Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>:
> Hi Guillaume,

Hi Mathieu, thanks for your extensive reply.

> yet another level of band-aid over a

I don't agree it's a band-aid, changing the scaling coefficient
without adjusting an offset is a bug.

> broken architecture : AMD 7th and 8th generations

Actually in my case it's Intel Pentium M Dothan.

> other parts of the kernel suffers from those TSC inconsistencies

These other parts should not use sched_clock() but the clocksource
mechanism which in my case rightly avoids the TSC and uses the
ACPI timer. And I hope it will stay that way as the TSC definitely is
not a reliable time source in my case for the reasons you gave.

> it does not deal with frequency scaling due to temperature related
> events, and does not, as I recall, deal with frequency scaling in halt
> mode.

Yep, I saw this, that's why I said in this case sched_clock() does not
return nanoseconds as it thinks it does. Thankfully, the scheduler is
not stressed when the CPU is idle. Anyway, spilling on another thread,
this is a bonus point for the RSDL scheduler as it does not account
the sleeping time of tasks.

> I also plan to update this global last_tsc every timer tick to give a
> higher bound to time accuracy.

Then I don't see how this is significantly better than the ACPI timer
except for the increased precision in short durations. For example,
my CPU can lower its frequency down to 798 MHz and the TSC
down to 350 MHz or so (measured). So your clock will think the
TSC runs at 798 MHz  when it runs at 350MHz, and every tick the
clock will make a half tick jump to catch up with its delay.

The best solution seems to buy a new computer with a reliable
TSC ;-)

Thanks.

-- 
Guillaume