- sched_clock() broken for ia64 SN platform

sched_clock() is broken in 2.6.0-test9 for ia64 "drifty ITC" platforms, such as the SGI "SN" platform. The CPU Scheduler expects sched_clock() to return a nanosecond value that is synchronized across all CPUs, and the SN platform must use platform's RealTimeClock (RTC).

I attach a patch that fixes this for the SN platform.

We might instead want to implement a more general scheme, along the lines of what is done by (struct time_interpolator), to provide a framework to solve this for other architectures that have "drifty" non-default timebases.

John Hawkes

diff -X /home/hawkes/Patches/ignore.dirs -Naur linux-2.6.0/arch/ia64/kernel/time.c linux-2.6.0-schedclock/arch/ia64/kernel/time.c
@@ -42,12 +42,18 @@
 
 #endif
 
+static unsigned long long
+itc_sched_clock (void)
+{
+	return jiffies * (1000000000/HZ);	/* a crude-granularity hack */
+}
+
+unsigned long long (*ia64_sched_clock)(void) = &itc_sched_clock;
+
 unsigned long long
 sched_clock (void)
 {
-	unsigned long offset = ia64_get_itc();
-
-	return (offset * local_cpu_data->nsec_per_cyc) >> IA64_NSEC_PER_CYC_SHIFT;
+	return ia64_sched_clock();
 }
 
 static void

diff -X /home/hawkes/Patches/ignore.dirs -Naur linux-2.6.0/arch/ia64/sn/kernel/sn2/timer.c linux-2.6.0-schedclock/arch/ia64/sn/kernel/sn2/timer.c
@@ -22,6 +22,8 @@
 extern unsigned long sn_rtc_cycles_per_second;
 static volatile unsigned long last_wall_rtc;
 
+extern unsigned long long (*ia64_sched_clock)(void);
+
 static unsigned long rtc_offset;	/* updated only when xtime write-lock is held! */
 static long rtc_nsecs_per_cycle;
 static long rtc_per_timer_tick;

@@ -55,6 +57,12 @@
 	last_wall_rtc = GET_RTC_COUNTER();
 }
 
+static unsigned long long
+sn_sched_clock(void)
+{
+	return GET_RTC_COUNTER() * rtc_nsecs_per_cycle;
+}
+
 
 static struct time_interpolator sn2_interpolator = {
 	.get_offset =	getoffset,

@@ -73,4 +81,6 @@
 	rtc_nsecs_per_cycle = 1000000000 / sn_rtc_cycles_per_second;
 
 	last_wall_rtc = GET_RTC_COUNTER();
+
+	ia64_sched_clock = &sn_sched_clock;
 }

John> We might instead want to implement a more general scheme, John> along the lines of what is done by (struct time_interpolator), John> to provide a framework to solve this for other architectures John> that have "drifty" non-default timebases.

My sense is that with a bit of thinking, it would be possible to come up with a solution that allows even drifty platforms to use ITC for sched_clock()---it serves very a specific purpose in the scheduler and scalability is key and perfect accuracy is not (unlike for gettimeofday). I don't think anything that goes out to read a single (shared) platform counter will be sufficiently scalable to the number of CPUs you guys are talking about. But yes, it would be much more effort than just adding Yet Another Callback. The rewards would be bigger, though, too...

	--david

From: "David Mosberger" <[email protected]>> >>>>> On Wed, 19 Nov 2003

In 2.4 the scheduler used "jiffies" directly as a timestamp for this purpose. Then for some reason someone decided to abstract that into sched_clock(), to let every architecture decide how to implement it. The alpha architecture implements sched_clock() with jiffies. The i386 uses the TSC (which might not be synchronized for all platforms?). The ia64 uses the ITC.

I'd like to hear an argument about why sched_clock() needs sub-microsecond accuracy, instead of just using jiffies, when one use of sched_clock() is to compare a delta time against cache_decay_ticks, which is a "jiffies"-granularity value, and the other use is to determine the relative computebound-vs-interactive characteristics of the process.

John Hawkes

John> I'd like to hear an argument about why sched_clock() needs John> sub-microsecond accuracy, instead of just using jiffies, when John> one use of sched_clock() is to compare a delta time against John> cache_decay_ticks, which is a "jiffies"-granularity value, and John> the other use is to determine the relative
John> computebound-vs-interactive characteristics of the process.

It's probably best to discuss this on lkml. I didn't follow all the recent scheduler developments but AFAIK, this is largely driven by trying to fix some scheduling corners. I think the "persistent starvation" bug that Stephane found gets fixed by it, for example. Also, supposedly it helps interactivity.

	--david

This is slightly off-topic, but the shared platform counter on the SGI platform isnt a single counter. The counter is replicated in each chipset It is synchronized thruout the system so that all cpus will see the same value - ie., no drift. Reading the counter does not required any off-node references. There shouldnt be any scaling issues. However, reading the ITC is faster & preferred if intercpu drift is not an issue.

Thanks

Jack Steiner ([email protected])          651-683-5302
Principal Engineer                      SGI - Silicon Graphics, Inc.

In general, it seems like bouncing the jiffies cacheline around is more of a problem than the need for accuracy. This sounds like a similar problem Jack Steiner wrote about before (updating interrupt counts):

| Updating the counter causes a cache line to be bounced between
| cpus at a rate of at least HZ*active_cpus. (The number of bus transactions
| is at least 2X higher because the line is first obtained for
| shared usage, then upgraded to modified. In addition, multiple references
| are made to the line for each interrupt. On a big system, it is unlikely that
| a cpu can hold the line for entire time that the interrupt is being
| serviced).

hth,
grant

Just to add a small note to Jack's comments, the reason for the existance of this "globally synchronized hi-res" counter is exactly for scheduling. On IRIX we use this in the frame-scheduler, to achieve order(tens of microsecond) simultaneous launch of processes on multiple CPUs for hard realtime.

The counter is replicated in each memory controller, where the NUMAflex interconnect provides a broadcast clock signal to drive them. It's a fairly cool feature, and the realtime people love it...

FYI, Rich

Jack> This is slightly off-topic, but the shared platform counter on Jack> the SGI platform isnt a single counter. The counter is Jack> replicated in each chipset It is synchronized thruout the Jack> system so that all cpus will see the same value - ie., no Jack> drift. Reading the counter does not required any off-node Jack> references. There shouldnt be any scaling issues.

Ah, that's good. Just for future reference, what's the approximate latency of reading this counter?

Jack> However, reading the ITC is faster & preferred if intercpu Jack> drift is not an issue.

Yes. Plus we could solve the problem once and for all, not once for each drifty platform.

As I remember it, sched_clock() was originally invented to measure fine-grained "how long have I run" times. This can be done with ITC without synchronization, since the start and stop "times" will be measured on the same CPU. Howver, as John points out, at the moment sched_clock() is also used for migration-decisions. My guess is that this part is just due to someone trying to be overly clever. At least on drifty platforms, you can just as easily make this decision based on jiffies. All it would do is add one word to the task_struct and reading both sched_clock() and jiffies when updating the timestamp(s).

	--david

The jiffies cacheline is always used shared except by cpu 0 when updating it once per tick. The interrupt counts problem was that every cpu would receive the tick interrupt and try to update (grab exclusive copy) the same cacheline.

Different problem. Jiffies is not as much of a concern.

I haven't tested it recently, but it was approx 55nSec on a 900Mhz Madison.

From: "David Mosberger" <[email protected]>

I doubt this double-count would ever be accepted by the wider Linux Community, as it bloats mainline arch-independent code, just to fix a problem with a handful of drifty platforms.

The i386 code is uglier than my patch, as it makes NUMA platforms use the gross-granularity "jiffies" as the time base. So much for any of the benefits in the scheduler to a high-precision task->timestamp. At least with my ia64 patch, it allows for a platform-specific sched_clock() that returns a high-precision value and doesn't appreciably add bloat.

John Hawkes

John> I doubt this double-count would ever be accepted by the wider John> Linux Community, as it bloats mainline arch-independent code, John> just to fix a problem with a handful of drifty platforms.

That's not an argument: the "bloat" can be trivially hidden for non-drifty architectures with an inline routine or macro. I for one would be perfectly happy to pay an extra word in the ia64-version of task_struct if that would yield a generic and scalable solution to the problem. The problem right now is that the generic kernel code is structured in a way that prevents this.

	--david

I too was confused why per-cpu start and stop times were not just used for this high-res accounting. I'm not sure I can look into it now, but I'd be interested to hear why we'd compare timestamps across cpus (rather then just use time deltas calculated on a single cpu).

Oh, and that last thought, keep it around for when 2.7 opens ;)

-john

From: "john stultz" <[email protected]>

sched_clock() and task->timestamp are used in two different ways. One is for supposedly high-res accounting. The other is for can_migrate_task(), called during load-balancing, to determine if the process has slept long enough to consider it to no longer be cache-hot. It's this latter use that suffers from a drifty timebase.

John Hawkes