Skip to contentSkip to conversation

Add an offset in the cyc2ns computation to fix sched_clock jumps

PATCH In review Guillaume Chazarain 5 participants 9 messages Mar 16, 2007 – Mar 18, 2007

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Add an offset in the cyc2ns computation to fix sched_clock jumps

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.

---

arch/i386/kernel/tsc.c +0 -0
diff -r fb83e6d92a4c 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.
* ([email protected])
*
+ * ns += offset to avoid sched_clock jumps with cpufreq ([email protected])
+ *
* [email protected] "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);
}

/*

Signature · 1 line
Guillaume
#1 lore raw
Quoted 6 lines · 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().

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

#2 lore raw

2007/3/16, Andi Kleen <[email protected]>:

Quoted 1 line

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.

Signature · 1 line
Guillaume
Acked-by on v1 1/1
#3 lore raw
In reply to Guillaume Chazarain
Quoted 7 lines · 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().

Quoted 5 lines

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!

Quoted 5 lines

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.

Quoted 6 lines

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.

#4 lore raw
In reply to Guillaume Chazarain
Quoted 7 lines · 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().

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

Daniel

#5 lore raw

Am Fr 16.03.2007 19:30 schrieb Daniel Walker <[email protected]>:

Quoted 11 lines · Guillaume Chazarain
Quoted 9 lines

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

Quoted 1 line

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

#6 lore raw
In reply to Daniel Walker

2007/3/16, Daniel Walker <[email protected]>:

Quoted 1 line

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.

Signature · 1 line
Guillaume
#7 lore raw
In reply to Guillaume Chazarain

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

Quoted 114 lines · * Guillaume Chazarain ([email protected]) 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.

---

diff -r fb83e6d92a4c arch/i386/kernel/tsc.c

arch/i386/kernel/tsc.c +44 -6
@@ -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.
 *  ([email protected])
 *
+ *  ns += offset to avoid sched_clock jumps with cpufreq ([email protected])
+ *
 *			[email protected] "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);

}

/*

Signature · 1 line
Guillaume
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#8 lore raw

2007/3/18, Mathieu Desnoyers <[email protected]>:

Quoted 1 line

Hi Guillaume,

Hi Mathieu, thanks for your extensive reply.

Quoted 1 line

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.

Quoted 1 line

broken architecture : AMD 7th and 8th generations

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

Quoted 1 line

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.

Quoted 3 lines

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.

Quoted 2 lines

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.

Signature · 1 line
Guillaume