[patch 1/] timers: tsc using for cpu scheduling

[patch 1/] timers: tsc using for cpu scheduling

[Ananiev, Leonid I]

		Patch for using TSC but not PMT in cpu scheduler.

	It was noted that under high memory load the process which
generates a lot page faults does not lose own priority at all if
processor has Power Management Timer (PMT) and for this reason Linux
uses jiffies_64 for process priority calculation instead of Time Stamp
Clock (TSC). As a result time is measured with 1000000 nsec granularity:
				if (!use_tsc)
					return jiffies_64 * (1000000000
/ HZ);
	If process regularly uses processor much less than 1 msec
scheduler does not see processor using by this process and does not
decrease priority of process as it is performed on platforms which have
not PMT or PMT using is suppressed in .config file. The "list of timers,
ordered by preference" in linux kernel dictates to use Power Management
timer, if it is on processor and measure process run time in
milliseconds (jiffies) actually but not in nanoseconds. As a result the
process which provoke to memory threshing and bad cpu and cash using has
much higher priority than regular interactive process. You can see that
cpu using time grows (it is measured by other way - not by function
sched_clock()) but priority is not bring down and the process is
considered as high priority interactive one.
It is known that TSC is incorrect according to astronomical real time as
a result of PM throttling. But for scheduler purposes the value of work
executed for each process but not real time spent on cpu makes sense.
The scheduler actually does not consider process run time as a real
time: it uses division of variable run_time  on CURRENT_BONUS before
comparison it with sleep average time:
			run_time /= CURRENT_BONUS;
			task->sleep_avg -= run_time;
	So run_time is not a real time but some measure of cpu work
which is performed for current process and we have the right and have to
use TSC for scheduler purpose if TSC is there on processor and does
function. Proposed patch makes corresponding modifications. The
multiplier value which is used for converting TSC ticks to nanoseconds
in function cycles_2_ns() may be corrected when cpu frequency is changed
and so scheduler will use ajusted time.  But it is not necessarily if we
agree to measure processor work but not processor time for scheduling.
If CPU clock speed is variable (PM throttling) it is more correctly to
use TSC for processor work performed for each process measuring.
If PMT and jiffies is used for scheduler, some times run_time will be
increased by 1,000,000 nanoseconds if between begin and end scheduler
time marks the variable jiffies_64 is increased. It seams that run_time
will be correct on average. It is not so because the events 'mark begin
run' and 'jiffies increase' are not independent. They are very
dependant. Task gets CPU just after jiffies modification.
The patch for using TSC in sched_clock() function is divided on two
parts: first part moves duplicated code lines from  timer_tsc.c and
timer_hpet.c to common.c. Second patch deletes global variable use_tsc;
makes function sched_clock() to use TSC only. . Now the variable
cyc2ns_scale may be used instead of use_tsc because this variable is not
0 if kernel had tested TSC successfully.

	Patch moves duplicated code lines from  timer_tsc.c and
timer_hpet.c to common.c:

--- a/arch/i386/kernel/timers/common.c	2005-06-14 15:35:20.000000000
+0400
+++ b/arch/i386/kernel/timers/common.c	2005-06-16 18:39:03.000000000
+0400
@@ -138,6 +138,32 @@
 	return 0;
 }
 #endif
+/* convert from cycles(64bits) => nanoseconds (64bits)
+ *  basic equation:
+ *		ns = cycles / (freq / ns_per_sec)
+ *		ns = cycles * (ns_per_sec / freq)
+ *		ns = cycles * (10^9 / (cpu_mhz * 10^6))
+ *		ns = cycles * (10^3 / cpu_mhz)
+ *
+ *	Then we use scaling math (suggested by george@mvista.com) to
get:
+ *		ns = cycles * (10^3 * SC / cpu_mhz) / SC
+ *		ns = cycles * cyc2ns_scale / SC
+ *
+ *	And since SC is a constant power of two, we can convert the div
+ *  into a shift.   
+ *			-johnstul@us.ibm.com "math is hard, lets go
shopping!"
+ */
+unsigned long cyc2ns_scale; 
+#define CYC2NS_SCALE_FACTOR 10 /* 2^10, carefully chosen */
+
+inline void set_cyc2ns_scale(unsigned long cpu_mhz)
+{
+	cyc2ns_scale = (1000 << CYC2NS_SCALE_FACTOR)/cpu_mhz;
+}
+inline unsigned long long cycles_2_ns(unsigned long long cyc)
+{
+	return (cyc * cyc2ns_scale) >> CYC2NS_SCALE_FACTOR;
+}
 
 /* calculate cpu_khz */
 void init_cpu_khz(void)
@@ -156,6 +182,7 @@
 	                	"0" (eax), "1" (edx));
 				printk("Detected %lu.%03lu MHz
processor.\n", cpu_khz / 1000, cpu_khz % 1000);
 			}
+			set_cyc2ns_scale(cpu_khz/1000);
 		}
 	}
 }
--- a/arch/i386/kernel/timers/timer_hpet.c	2005-06-14
15:35:20.000000000 +0400
+++ b/arch/i386/kernel/timers/timer_hpet.c	2005-06-16
17:04:20.000000000 +0400
@@ -26,34 +26,6 @@
 static unsigned long long monotonic_base;
 static seqlock_t monotonic_lock = SEQLOCK_UNLOCKED;
 
-/* convert from cycles(64bits) => nanoseconds (64bits)
- *  basic equation:
- *		ns = cycles / (freq / ns_per_sec)
- *		ns = cycles * (ns_per_sec / freq)
- *		ns = cycles * (10^9 / (cpu_mhz * 10^6))
- *		ns = cycles * (10^3 / cpu_mhz)
- *
- *	Then we use scaling math (suggested by george@mvista.com) to
get:
- *		ns = cycles * (10^3 * SC / cpu_mhz) / SC
- *		ns = cycles * cyc2ns_scale / SC
- *
- *	And since SC is a constant power of two, we can convert the div
- *  into a shift.
- *			-johnstul@us.ibm.com "math is hard, lets go
shopping!"
- */
-static unsigned long cyc2ns_scale;
-#define CYC2NS_SCALE_FACTOR 10 /* 2^10, carefully chosen */
-
-static inline void set_cyc2ns_scale(unsigned long cpu_mhz)
-{
-	cyc2ns_scale = (1000 << CYC2NS_SCALE_FACTOR)/cpu_mhz;
-}
-
-static inline unsigned long long cycles_2_ns(unsigned long long cyc)
-{
-	return (cyc * cyc2ns_scale) >> CYC2NS_SCALE_FACTOR;
-}
-
 static unsigned long long monotonic_clock_hpet(void)
 {
 	unsigned long long last_offset, this_offset, base;
--- a/arch/i386/kernel/timers/timer_tsc.c	2005-06-14
15:35:20.000000000 +0400
+++ b/arch/i386/kernel/timers/timer_tsc.c	2005-06-16
18:46:40.000000000 +0400
@@ -46,34 +45,6 @@
 static unsigned long long monotonic_base;
 static seqlock_t monotonic_lock = SEQLOCK_UNLOCKED;
 
-/* convert from cycles(64bits) => nanoseconds (64bits)
- *  basic equation:
- *		ns = cycles / (freq / ns_per_sec)
- *		ns = cycles * (ns_per_sec / freq)
- *		ns = cycles * (10^9 / (cpu_mhz * 10^6))
- *		ns = cycles * (10^3 / cpu_mhz)
- *
- *	Then we use scaling math (suggested by george@mvista.com) to
get:
- *		ns = cycles * (10^3 * SC / cpu_mhz) / SC
- *		ns = cycles * cyc2ns_scale / SC
- *
- *	And since SC is a constant power of two, we can convert the div
- *  into a shift.   
- *			-johnstul@us.ibm.com "math is hard, lets go
shopping!"
- */
-static unsigned long cyc2ns_scale; 
-#define CYC2NS_SCALE_FACTOR 10 /* 2^10, carefully chosen */
-
-static inline void set_cyc2ns_scale(unsigned long cpu_mhz)
-{
-	cyc2ns_scale = (1000 << CYC2NS_SCALE_FACTOR)/cpu_mhz;
-}
-
-static inline unsigned long long cycles_2_ns(unsigned long long cyc)
-{
-	return (cyc * cyc2ns_scale) >> CYC2NS_SCALE_FACTOR;
-}
-
 static int count2; /* counter for mark_offset_tsc() */
 
 /* Cached *multiplier* to convert TSC counts to microseconds.

Patch for using TSC in cpu scheduler:
--- a/arch/i386/kernel/timers/common.c	2005-06-20 15:34:10.000000000
+0400
+++ b/arch/i386/kernel/timers/common.c	2005-06-20 16:42:13.000000000
+0400
@@ -164,6 +164,16 @@
 {
 	return (cyc * cyc2ns_scale) >> CYC2NS_SCALE_FACTOR;
 }
+/*
+ * Scheduler clock - returns current time in nanosec units.
+ */
+unsigned long long sched_clock(void)
+{
+	unsigned long long this_offset;
+
+	rdtscll(this_offset);
+	return cycles_2_ns(this_offset);
+}
 
 /* calculate cpu_khz */
 void init_cpu_khz(void)
--- a/arch/i386/kernel/timers/timer_tsc.c	2005-06-20
15:34:10.000000000 +0400
+++ b/arch/i386/kernel/timers/timer_tsc.c	2005-06-20
16:47:50.000000000 +0400
@@ -37,7 +37,6 @@
 
 extern spinlock_t i8253_lock;
 
-static int use_tsc;
 /* Number of usecs that the last interrupt was delayed */
 static int delay_at_last_interrupt;
 
@@ -103,30 +102,6 @@
 	return base + cycles_2_ns(this_offset - last_offset);
 }
 
-/*
- * Scheduler clock - returns current time in nanosec units.
- */
-unsigned long long sched_clock(void)
-{
-	unsigned long long this_offset;
-
-	/*
-	 * In the NUMA case we dont use the TSC as they are not
-	 * synchronized across all CPUs.
-	 */
-#ifndef CONFIG_NUMA
-	if (!use_tsc)
-#endif
-		/* no locking but a rare wrong value is not a big deal
*/
-		return jiffies_64 * (1000000000 / HZ);
-
-	/* Read the Time Stamp Counter */
-	rdtscll(this_offset);
-
-	/* return the value in ns */
-	return cycles_2_ns(this_offset);
-}
-
 static void delay_tsc(unsigned long loops)
 {
 	unsigned long bclock, now;
@@ -256,7 +231,7 @@
 #ifndef CONFIG_SMP
 		if (cpu_khz)
 			cpu_khz = cpufreq_scale(cpu_khz_ref, ref_freq,
freq->new);
-		if (use_tsc) {
+		if (cyc2ns_scale) {
 			if (!(freq->flags & CPUFREQ_CONST_LOOPS)) {
 				fast_gettimeoffset_quotient =
cpufreq_scale(fast_gettimeoffset_ref, freq->new, ref_freq);
 				set_cyc2ns_scale(cpu_khz/1000);
@@ -492,7 +467,6 @@
 
 		if (tsc_quotient) {
 			fast_gettimeoffset_quotient = tsc_quotient;
-			use_tsc = 1;
 			/*
 			 *	We could be more selective here I
suspect
 			 *	and just enable this for the next intel
chips ?

Leonid Ananiev
leonid.i.ananiev@intel.com

Re: [patch 1/] timers: tsc using for cpu scheduling

[john stultz]

On Thu, 2005-06-30 at 15:43 +0400, Ananiev, Leonid I wrote:
> 		Patch for using TSC but not PMT in cpu scheduler.
> 
> 	It was noted that under high memory load the process which
> generates a lot page faults does not lose own priority at all if
> processor has Power Management Timer (PMT) and for this reason Linux
> uses jiffies_64 for process priority calculation instead of Time Stamp
> Clock (TSC). As a result time is measured with 1000000 nsec granularity:

[snip]

> 	If process regularly uses processor much less than 1 msec
> scheduler does not see processor using by this process and does not
> decrease priority of process as it is performed on platforms which have
> not PMT or PMT using is suppressed in .config file. The "list of timers,
> ordered by preference" in linux kernel dictates to use Power Management
> timer, if it is on processor and measure process run time in
> milliseconds (jiffies) actually but not in nanoseconds. As a result the
> process which provoke to memory threshing and bad cpu and cash using has
> much higher priority than regular interactive process. You can see that
> cpu using time grows (it is measured by other way - not by function
> sched_clock()) but priority is not bring down and the process is
> considered as high priority interactive one.


So let me try to restate the problem, and you can let me know if I'm
misunderstanding you.

When the TSC is not used for timekeeping, sched_clock() uses jiffies to
measure time. This results in very course 1ms (or really 1/HZ)
granularity from sched_clock().

This course granularity is causing issues in the scheduler, as best that
I can understand, where processes that cause lots of pagefaults are not
properly dinged for their time.

Is that about right?


> It is known that TSC is incorrect according to astronomical real time as
> a result of PM throttling. But for scheduler purposes the value of work
> executed for each process but not real time spent on cpu makes sense.
> The scheduler actually does not consider process run time as a real
> time: it uses division of variable run_time  on CURRENT_BONUS before
> comparison it with sleep average time:
> 			run_time /= CURRENT_BONUS;
> 			task->sleep_avg -= run_time;
> 	So run_time is not a real time but some measure of cpu work
> which is performed for current process and we have the right and have to
> use TSC for scheduler purpose if TSC is there on processor and does
> function. 


Well, not quite. First of all, I believe (Dominik would know better)
that not all CPUs that support frequency scaling actually modify their
TSC frequency. So in some cases the TSC is time and in others it is
work.

Further, there are other cases where the TSC cannot be used for
sched_clock, such as on systems that do not have TSCs, and NUMA systems
where the TSCs are not synched. 



> Proposed patch makes corresponding modifications. The
> multiplier value which is used for converting TSC ticks to nanoseconds
> in function cycles_2_ns() may be corrected when cpu frequency is changed
> and so scheduler will use ajusted time.  


You're patch removes any fallback for the case where the TSC cannot be
used.



> But it is not necessarily if we
> agree to measure processor work but not processor time for scheduling.
> If CPU clock speed is variable (PM throttling) it is more correctly to
> use TSC for processor work performed for each process measuring.
> If PMT and jiffies is used for scheduler, some times run_time will be
> increased by 1,000,000 nanoseconds if between begin and end scheduler
> time marks the variable jiffies_64 is increased. It seams that run_time
> will be correct on average. It is not so because the events 'mark begin
> run' and 'jiffies increase' are not independent. They are very
> dependant. Task gets CPU just after jiffies modification.


For i386 sched_clock() is quite broken on cpufreq scaling systems
anyway, as it uses the cyc2ns code (which was borrowed from the TSC's
monotonic_clock interface) against the raw TSC value. When the cyc2ns
multiplier changes it applys the new value to the full TSC count, rather
then just the interval at which the cpu has been running at the new
frequency. This can cause sched_clock to jump forwards and backwards in
time. 

I'm not a scheduler head, but my understanding was that sched_clock()
wasn't given *too* much weight in scheduling decisions, as it is
expected to give crazy values every once in a while.

If sched_clock()'s semantics need to change, that's fine with me, but it
should probably be consistent across all the arches, so this would need
to be discussed with other arches that have cpufreq scaling.

Maybe is there not a better way other then using sched_clock to ding
processes that are causing pagefaults?


> The patch for using TSC in sched_clock() function is divided on two
> parts: first part moves duplicated code lines from  timer_tsc.c and
> timer_hpet.c to common.c. 

Removing the duplicated code probably isn't a bad idea. 


> Second patch deletes global variable use_tsc;
> makes function sched_clock() to use TSC only. . Now the variable
> cyc2ns_scale may be used instead of use_tsc because this variable is not
> 0 if kernel had tested TSC successfully.

This I don't agree with because there are situations where we cannot use
the TSC.

thanks
-john

Re: [patch 1/] timers: tsc using for cpu scheduling

[Dominik Brodowski]

On Thu, Jun 30, 2005 at 12:07:48PM -0700, john stultz wrote:
> Well, not quite. First of all, I believe (Dominik would know better)
> that not all CPUs that support frequency scaling actually modify their
> TSC frequency. So in some cases the TSC is time and in others it is
> work.

Indeed. For example, P4s capable of Enhanced SpeedStep do not modify the TSC
tick rate.

	Dominik

RE: [patch 1/] timers: tsc using for cpu scheduling

[Ananiev, Leonid I]

I should underline that patch deal with the alternative which timer to
use for task priority calculation when both TSC and PMT function.

You writes
> it will need some additional documentation and its likely you don't
want
> to use the cycles_2_ns() functions.

	It is not need any additional documentation because using CPU
time as a measure of CPU work for scheduling is described in the Linux
kernel books. But when PMT was added in computers it was nominated for
scheduling time measurement because TSC may miss 2-3 clocks during CPU
frequency variation. But in that frequency variation period instruction
ticks are missed as well as TSC ticks. So TSC using is more correct in
this case. My patch returns only to original way scheduling time
calculation.

	About NUMA Chen Kenneth gives argument:
> It is safe to use cpu local rdtsc since the scheduler will never
consume > > two timestamps taken from two different cpus.

I have added a comment in the patched source code according to your
recommends:
+ * It is not recommended to use this function for other than scheduler
purposes
+ * when time marks may be get on different cpus or cpu frequency is
varied.

You write
> As it was written it would have broken NUMAQ and other systems that do
> not have usable TSCs (ie: i386/i486).

According to documentation TSC presents in IA32 any computer. But:
	 *	NOTE: this doesn't yet handle SMP 486 machines where
only
 	 *	some CPU's have a TSC. Thats never worked and nobody has
 	 *	moaned if you have the only one in the world - you fix
it!
- says  arch/i386/kernel/timers/timer_tsc.c

You are right. It is good to save check and I restored it:
+	if (!cyc2ns_scale)
+		return jiffies_64 * (1000000000 / HZ);

The patch:

diff -ur a/arch/i386/kernel/timers/common.c
b/arch/i386/kernel/timers/common.c
--- a/arch/i386/kernel/timers/common.c	2005-06-17 23:48:29.000000000
+0400
+++ b/arch/i386/kernel/timers/common.c	2005-07-17 23:02:16.000000000
+0400
@@ -138,6 +138,48 @@
 	return 0;
 }
 #endif
+/* convert from cycles(64bits) => nanoseconds (64bits)
+ *  basic equation:
+ *		ns = cycles / (freq / ns_per_sec)
+ *		ns = cycles * (ns_per_sec / freq)
+ *		ns = cycles * (10^9 / (cpu_mhz * 10^6))
+ *		ns = cycles * (10^3 / cpu_mhz)
+ *
+ *	Then we use scaling math (suggested by george@mvista.com) to
get:
+ *		ns = cycles * (10^3 * SC / cpu_mhz) / SC
+ *		ns = cycles * cyc2ns_scale / SC
+ *
+ *	And since SC is a constant power of two, we can convert the div
+ *  into a shift.   
+ *			-johnstul@us.ibm.com "math is hard, lets go
shopping!"
+ */
+unsigned long cyc2ns_scale; 
+#define CYC2NS_SCALE_FACTOR 10 /* 2^10, carefully chosen */
+
+inline void set_cyc2ns_scale(unsigned long cpu_mhz)
+{
+	cyc2ns_scale = (1000 << CYC2NS_SCALE_FACTOR)/cpu_mhz;
+}
+inline unsigned long long cycles_2_ns(unsigned long long cyc)
+{
+	return (cyc * cyc2ns_scale) >> CYC2NS_SCALE_FACTOR;
+}
+/*
+ * Scheduler clock - returns current time in nanosec units.
+ * It is not recommended to use this function for other than scheduler
purposes
+ * when time marks may be get on different cpus or cpu frequency is
varied.
+ */
+unsigned long long sched_clock(void)
+{
+	unsigned long long this_offset;
+
+	if (!cyc2ns_scale)
+		/* no locking but a rare wrong value is not a big deal
*/
+		return jiffies_64 * (1000000000 / HZ);
+
+	rdtscll(this_offset);
+	return cycles_2_ns(this_offset);
+}
 
 /* calculate cpu_khz */
 void init_cpu_khz(void)
@@ -156,6 +198,7 @@
 	                	"0" (eax), "1" (edx));
 				printk("Detected %lu.%03lu MHz
processor.\n", cpu_khz / 1000, cpu_khz % 1000);
 			}
+			set_cyc2ns_scale(cpu_khz/1000);
 		}
 	}
 }
diff -ur a/arch/i386/kernel/timers/timer_hpet.c
b/arch/i386/kernel/timers/timer_hpet.c
--- a/arch/i386/kernel/timers/timer_hpet.c	2005-06-17
23:48:29.000000000 +0400
+++ b/arch/i386/kernel/timers/timer_hpet.c	2005-07-17
22:28:00.000000000 +0400
@@ -26,34 +26,6 @@
 static unsigned long long monotonic_base;
 static seqlock_t monotonic_lock = SEQLOCK_UNLOCKED;
 
-/* convert from cycles(64bits) => nanoseconds (64bits)
- *  basic equation:
- *		ns = cycles / (freq / ns_per_sec)
- *		ns = cycles * (ns_per_sec / freq)
- *		ns = cycles * (10^9 / (cpu_mhz * 10^6))
- *		ns = cycles * (10^3 / cpu_mhz)
- *
- *	Then we use scaling math (suggested by george@mvista.com) to
get:
- *		ns = cycles * (10^3 * SC / cpu_mhz) / SC
- *		ns = cycles * cyc2ns_scale / SC
- *
- *	And since SC is a constant power of two, we can convert the div
- *  into a shift.
- *			-johnstul@us.ibm.com "math is hard, lets go
shopping!"
- */
-static unsigned long cyc2ns_scale;
-#define CYC2NS_SCALE_FACTOR 10 /* 2^10, carefully chosen */
-
-static inline void set_cyc2ns_scale(unsigned long cpu_mhz)
-{
-	cyc2ns_scale = (1000 << CYC2NS_SCALE_FACTOR)/cpu_mhz;
-}
-
-static inline unsigned long long cycles_2_ns(unsigned long long cyc)
-{
-	return (cyc * cyc2ns_scale) >> CYC2NS_SCALE_FACTOR;
-}
-
 static unsigned long long monotonic_clock_hpet(void)
 {
 	unsigned long long last_offset, this_offset, base;
diff -ur a/arch/i386/kernel/timers/timer_tsc.c
b/arch/i386/kernel/timers/timer_tsc.c
--- a/arch/i386/kernel/timers/timer_tsc.c	2005-06-17
23:48:29.000000000 +0400
+++ b/arch/i386/kernel/timers/timer_tsc.c	2005-07-17
22:28:00.000000000 +0400
@@ -37,7 +37,6 @@
 
 extern spinlock_t i8253_lock;
 
-static int use_tsc;
 /* Number of usecs that the last interrupt was delayed */
 static int delay_at_last_interrupt;
 
@@ -46,34 +45,6 @@
 static unsigned long long monotonic_base;
 static seqlock_t monotonic_lock = SEQLOCK_UNLOCKED;
 
-/* convert from cycles(64bits) => nanoseconds (64bits)
- *  basic equation:
- *		ns = cycles / (freq / ns_per_sec)
- *		ns = cycles * (ns_per_sec / freq)
- *		ns = cycles * (10^9 / (cpu_mhz * 10^6))
- *		ns = cycles * (10^3 / cpu_mhz)
- *
- *	Then we use scaling math (suggested by george@mvista.com) to
get:
- *		ns = cycles * (10^3 * SC / cpu_mhz) / SC
- *		ns = cycles * cyc2ns_scale / SC
- *
- *	And since SC is a constant power of two, we can convert the div
- *  into a shift.   
- *			-johnstul@us.ibm.com "math is hard, lets go
shopping!"
- */
-static unsigned long cyc2ns_scale; 
-#define CYC2NS_SCALE_FACTOR 10 /* 2^10, carefully chosen */
-
-static inline void set_cyc2ns_scale(unsigned long cpu_mhz)
-{
-	cyc2ns_scale = (1000 << CYC2NS_SCALE_FACTOR)/cpu_mhz;
-}
-
-static inline unsigned long long cycles_2_ns(unsigned long long cyc)
-{
-	return (cyc * cyc2ns_scale) >> CYC2NS_SCALE_FACTOR;
-}
-
 static int count2; /* counter for mark_offset_tsc() */
 
 /* Cached *multiplier* to convert TSC counts to microseconds.
@@ -131,30 +102,6 @@
 	return base + cycles_2_ns(this_offset - last_offset);
 }
 
-/*
- * Scheduler clock - returns current time in nanosec units.
- */
-unsigned long long sched_clock(void)
-{
-	unsigned long long this_offset;
-
-	/*
-	 * In the NUMA case we dont use the TSC as they are not
-	 * synchronized across all CPUs.
-	 */
-#ifndef CONFIG_NUMA
-	if (!use_tsc)
-#endif
-		/* no locking but a rare wrong value is not a big deal
*/
-		return jiffies_64 * (1000000000 / HZ);
-
-	/* Read the Time Stamp Counter */
-	rdtscll(this_offset);
-
-	/* return the value in ns */
-	return cycles_2_ns(this_offset);
-}
-
 static void delay_tsc(unsigned long loops)
 {
 	unsigned long bclock, now;
@@ -284,7 +231,7 @@
 #ifndef CONFIG_SMP
 		if (cpu_khz)
 			cpu_khz = cpufreq_scale(cpu_khz_ref, ref_freq,
freq->new);
-		if (use_tsc) {
+		if (cyc2ns_scale) {
 			if (!(freq->flags & CPUFREQ_CONST_LOOPS)) {
 				fast_gettimeoffset_quotient =
cpufreq_scale(fast_gettimeoffset_ref, freq->new, ref_freq);
 				set_cyc2ns_scale(cpu_khz/1000);
@@ -520,7 +467,6 @@
 
 		if (tsc_quotient) {
 			fast_gettimeoffset_quotient = tsc_quotient;
-			use_tsc = 1;
 			/*
 			 *	We could be more selective here I
suspect
 			 *	and just enable this for the next intel
chips ?



-----Original Message-----
From: john stultz [mailto:johnstul@us.ibm.com] 
Sent: Wednesday, July 06, 2005 5:43 AM
To: Ananiev, Leonid I
Cc: lkml; Dominik Brodowski; Semenikhin, Sergey V
Subject: RE: [patch 1/] timers: tsc using for cpu scheduling

On Tue, 2005-07-05 at 21:08 +0400, Ananiev, Leonid I wrote:
> 	Not only page faults may increase process priority. Someone can
> write two threads with mutexes so that each thread will spent much
less
> than 1 msec for calculations on cpu than lock-unlock mutexes and yield
> cpu to brother which wait mutex unlock and will do the same. Both
> threads will have high priority according to other threads during
> infinite time. The scheduler will not see the time spent by both
> considered threads on cpu.

Oh, I don't doubt there is a problem. I'm just asking if using the TSC
is really the only way to properly ding the process? 

I'm not a scheduler guy, so forgive my ignorance, but since the TSC may
not be available everywhere, might there be an alternative way to ding
the process? Surely something is keeping track of how many pagefaults a
process causes. Maybe a counter of how many times it has switched off
the cpu within the current tick? Couldn't these values be used as
scheduler weights?

I realize that ideally having super a fine grained notion of how much
cputime every process has had executing would be great. But it isn't
possible everywhere, so what can we do instead?

> 	The cpu scheduler does not need in real time value. It is need
> the number of cpu clocks spent for considered task/thread for priority
> calculation. It is not need to modify TSC tick rate for cpu
scheduling.

The problem is that some CPUs give you time, others give you work, and
sometimes those values are related. If you really want to re-define
sched_clock so that it gives you some vague work-unit instead of
nanoseconds, then that's fine, but it will need some additional
documentation and its likely you don't want to use the cycles_2_ns()
functions.

I don't really care too much about changes to sched_clock() as its
always been a special case interface just for the scheduler. I just want
it documented well enough so others don't think its a valid timekeeping
interface.


> 	The TSC can be used for priority calculation in NUMA because we
> do not compare TSCs of different cpu's. 

If you can guarantee that, then great! I know that was the original
intention, but some folks had problems with it which resulting in the
conditional #if NUMA code.


> > there are other cases where the TSC cannot be used for
> > sched_clock, such as on systems that do not have TSCs...
> 
> > You're patch removes any fallback for the case where the TSC cannot
be
> used.
> No. Now there is two global kernel values: cyc2ns_scale and use_tsc.
> We may say that
>  	use_tsc = (cyc2ns_scale != 0);
> Now instead of 
>  'if (use_tsc) than ...'
> 					I propose to write
>  'if ((cyc2ns_scale != 0) than...'


That's fine if its what you propose, I just didn't see it in your patch.
As it was written it would have broken NUMAQ and other systems that do
not have usable TSCs (ie: i386/i486).

> > This I don't agree with because there are situations where we cannot
> use
> the TSC.
> 
> The patch says that if there are PMT and TSC timers concurrently than
> Linux will use TSC for CPU scheduler priority calculatin.
> 1 millisecond jiffies on the base of PMT were used patch in Linux
before
> this. So user can see that if CPU has TSC it is worst than CPU which
has
> not TSC because Linux choose slightly more precise but exactly 1000000
> times more gross variant in this case.

Try re-spinning the patch to address the above issues and I'll happily
review it again. I just want to make sure the issue is addressed
properly and doesn't break other systems.

thanks
-john

RE: [patch 1/] timers: tsc using for cpu scheduling

[john stultz]

On Tue, 2005-07-05 at 21:08 +0400, Ananiev, Leonid I wrote:
> 	Not only page faults may increase process priority. Someone can
> write two threads with mutexes so that each thread will spent much less
> than 1 msec for calculations on cpu than lock-unlock mutexes and yield
> cpu to brother which wait mutex unlock and will do the same. Both
> threads will have high priority according to other threads during
> infinite time. The scheduler will not see the time spent by both
> considered threads on cpu.

Oh, I don't doubt there is a problem. I'm just asking if using the TSC
is really the only way to properly ding the process? 

I'm not a scheduler guy, so forgive my ignorance, but since the TSC may
not be available everywhere, might there be an alternative way to ding
the process? Surely something is keeping track of how many pagefaults a
process causes. Maybe a counter of how many times it has switched off
the cpu within the current tick? Couldn't these values be used as
scheduler weights?

I realize that ideally having super a fine grained notion of how much
cputime every process has had executing would be great. But it isn't
possible everywhere, so what can we do instead?

> 	The cpu scheduler does not need in real time value. It is need
> the number of cpu clocks spent for considered task/thread for priority
> calculation. It is not need to modify TSC tick rate for cpu scheduling.

The problem is that some CPUs give you time, others give you work, and
sometimes those values are related. If you really want to re-define
sched_clock so that it gives you some vague work-unit instead of
nanoseconds, then that's fine, but it will need some additional
documentation and its likely you don't want to use the cycles_2_ns()
functions.

I don't really care too much about changes to sched_clock() as its
always been a special case interface just for the scheduler. I just want
it documented well enough so others don't think its a valid timekeeping
interface.


> 	The TSC can be used for priority calculation in NUMA because we
> do not compare TSCs of different cpu's. 

If you can guarantee that, then great! I know that was the original
intention, but some folks had problems with it which resulting in the
conditional #if NUMA code.


> > there are other cases where the TSC cannot be used for
> > sched_clock, such as on systems that do not have TSCs...
> 
> > You're patch removes any fallback for the case where the TSC cannot be
> used.
> No. Now there is two global kernel values: cyc2ns_scale and use_tsc.
> We may say that
>  	use_tsc = (cyc2ns_scale != 0);
> Now instead of 
>  'if (use_tsc) than ...'
> 					I propose to write
>  'if ((cyc2ns_scale != 0) than...'


That's fine if its what you propose, I just didn't see it in your patch.
As it was written it would have broken NUMAQ and other systems that do
not have usable TSCs (ie: i386/i486).

> > This I don't agree with because there are situations where we cannot
> use
> the TSC.
> 
> The patch says that if there are PMT and TSC timers concurrently than
> Linux will use TSC for CPU scheduler priority calculatin.
> 1 millisecond jiffies on the base of PMT were used patch in Linux before
> this. So user can see that if CPU has TSC it is worst than CPU which has
> not TSC because Linux choose slightly more precise but exactly 1000000
> times more gross variant in this case.

Try re-spinning the patch to address the above issues and I'll happily
review it again. I just want to make sure the issue is addressed
properly and doesn't break other systems.

thanks
-john

RE: [patch 1/] timers: tsc using for cpu scheduling

[Ananiev, Leonid I]

John,

	Not only page faults may increase process priority. Someone can
write two threads with mutexes so that each thread will spent much less
than 1 msec for calculations on cpu than lock-unlock mutexes and yield
cpu to brother which wait mutex unlock and will do the same. Both
threads will have high priority according to other threads during
infinite time. The scheduler will not see the time spent by both
considered threads on cpu.
	The cpu scheduler does not need in real time value. It is need
the number of cpu clocks spent for considered task/thread for priority
calculation. It is not need to modify TSC tick rate for cpu scheduling.
	The TSC can be used for priority calculation in NUMA because we
do not compare TSCs of different cpu's. 

> there are other cases where the TSC cannot be used for
> sched_clock, such as on systems that do not have TSCs...

> You're patch removes any fallback for the case where the TSC cannot be
used.
No. Now there is two global kernel values: cyc2ns_scale and use_tsc.
We may say that
 	use_tsc = (cyc2ns_scale != 0);
Now instead of 
 'if (use_tsc) than ...'
					I propose to write
 'if ((cyc2ns_scale != 0) than...'

> This I don't agree with because there are situations where we cannot
use
the TSC.

The patch says that if there are PMT and TSC timers concurrently than
Linux will use TSC for CPU scheduler priority calculatin.
1 millisecond jiffies on the base of PMT were used patch in Linux before
this. So user can see that if CPU has TSC it is worst than CPU which has
not TSC because Linux choose slightly more precise but exactly 1000000
times more gross variant in this case.

Leonid


-----Original Message-----
From: john stultz [mailto:johnstul@us.ibm.com] 
Sent: Thursday, June 30, 2005 11:08 PM
To: Ananiev, Leonid I
Cc: lkml; Dominik Brodowski
Subject: Re: [patch 1/] timers: tsc using for cpu scheduling

On Thu, 2005-06-30 at 15:43 +0400, Ananiev, Leonid I wrote:
> 		Patch for using TSC but not PMT in cpu scheduler.
> 
> 	It was noted that under high memory load the process which
> generates a lot page faults does not lose own priority at all if
> processor has Power Management Timer (PMT) and for this reason Linux
> uses jiffies_64 for process priority calculation instead of Time Stamp
> Clock (TSC). As a result time is measured with 1000000 nsec
granularity:

[snip]

> 	If process regularly uses processor much less than 1 msec
> scheduler does not see processor using by this process and does not
> decrease priority of process as it is performed on platforms which
have
> not PMT or PMT using is suppressed in .config file. The "list of
timers,
> ordered by preference" in linux kernel dictates to use Power
Management
> timer, if it is on processor and measure process run time in
> milliseconds (jiffies) actually but not in nanoseconds. As a result
the
> process which provoke to memory threshing and bad cpu and cash using
has
> much higher priority than regular interactive process. You can see
that
> cpu using time grows (it is measured by other way - not by function
> sched_clock()) but priority is not bring down and the process is
> considered as high priority interactive one.


So let me try to restate the problem, and you can let me know if I'm
misunderstanding you.

When the TSC is not used for timekeeping, sched_clock() uses jiffies to
measure time. This results in very course 1ms (or really 1/HZ)
granularity from sched_clock().

This course granularity is causing issues in the scheduler, as best that
I can understand, where processes that cause lots of pagefaults are not
properly dinged for their time.

Is that about right?


> It is known that TSC is incorrect according to astronomical real time
as
> a result of PM throttling. But for scheduler purposes the value of
work
> executed for each process but not real time spent on cpu makes sense.
> The scheduler actually does not consider process run time as a real
> time: it uses division of variable run_time  on CURRENT_BONUS before
> comparison it with sleep average time:
> 			run_time /= CURRENT_BONUS;
> 			task->sleep_avg -= run_time;
> 	So run_time is not a real time but some measure of cpu work
> which is performed for current process and we have the right and have
to
> use TSC for scheduler purpose if TSC is there on processor and does
> function. 


Well, not quite. First of all, I believe (Dominik would know better)
that not all CPUs that support frequency scaling actually modify their
TSC frequency. So in some cases the TSC is time and in others it is
work.

Further, there are other cases where the TSC cannot be used for
sched_clock, such as on systems that do not have TSCs, and NUMA systems
where the TSCs are not synched. 



> Proposed patch makes corresponding modifications. The
> multiplier value which is used for converting TSC ticks to nanoseconds
> in function cycles_2_ns() may be corrected when cpu frequency is
changed
> and so scheduler will use ajusted time.  


You're patch removes any fallback for the case where the TSC cannot be
used.



> But it is not necessarily if we
> agree to measure processor work but not processor time for scheduling.
> If CPU clock speed is variable (PM throttling) it is more correctly to
> use TSC for processor work performed for each process measuring.
> If PMT and jiffies is used for scheduler, some times run_time will be
> increased by 1,000,000 nanoseconds if between begin and end scheduler
> time marks the variable jiffies_64 is increased. It seams that
run_time
> will be correct on average. It is not so because the events 'mark
begin
> run' and 'jiffies increase' are not independent. They are very
> dependant. Task gets CPU just after jiffies modification.


For i386 sched_clock() is quite broken on cpufreq scaling systems
anyway, as it uses the cyc2ns code (which was borrowed from the TSC's
monotonic_clock interface) against the raw TSC value. When the cyc2ns
multiplier changes it applys the new value to the full TSC count, rather
then just the interval at which the cpu has been running at the new
frequency. This can cause sched_clock to jump forwards and backwards in
time. 

I'm not a scheduler head, but my understanding was that sched_clock()
wasn't given *too* much weight in scheduling decisions, as it is
expected to give crazy values every once in a while.

If sched_clock()'s semantics need to change, that's fine with me, but it
should probably be consistent across all the arches, so this would need
to be discussed with other arches that have cpufreq scaling.

Maybe is there not a better way other then using sched_clock to ding
processes that are causing pagefaults?


> The patch for using TSC in sched_clock() function is divided on two
> parts: first part moves duplicated code lines from  timer_tsc.c and
> timer_hpet.c to common.c. 

Removing the duplicated code probably isn't a bad idea. 


> Second patch deletes global variable use_tsc;
> makes function sched_clock() to use TSC only. . Now the variable
> cyc2ns_scale may be used instead of use_tsc because this variable is
not
> 0 if kernel had tested TSC successfully.

This I don't agree with because there are situations where we cannot use
the TSC.

thanks
-john