2.6.0-test11 sched_clock() broken for "drifty ITC"

David Mosberger suggests raising this issue on LKML to encourage a search for a more general solution to my ia64 problem.

My specific problem is that the generic ia64 sched_clock() is broken for "drifty ITC" (the per-CPU cycle counter clock) platforms, such as the SGI sn. sched_clock() currently uses its local CPU's ITC and therefore on drifty platforms its values are not synchronized across the CPUs. This results (in part) in an invalid load_balance() is-the-cache-hot-or-not calculation.

I proposed fixing this in arch/ia64 by making sched_clock() support an optional platform-specific implementation. I insert a quick summary of that patch here, and append the full patch at the end of this email. In my patch the generic ia64 implementation remains the same, and the sn platform- specific implementation uses the sn's synchronized RTC to return a high- resolution sched_clock() value.

The generic part of my patch:

+static unsigned long long
+itc_sched_clock (void)
+{
+ return (offset * local_cpu_data->nsec_per_cyc) >> IA64_NSEC_PER_CY
C_SHIFT;
+}
+
+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();
}

However, David Mosberger rejected this patch, and he seeks instead some hypothetical more generic approach to "drifty timebase platforms". One possible generic change would be to relax the semantics of sched_clock() to no longer expect that the values be synchronized across all CPUs. Some amount of code would need to be added to sched.c to deal with unsynchronized values: scheduler_tick() remembers a local jiffies- granularity sched_clock() in the runqueue struct, and load_balance's can_migrate_task() uses that saved timestamp to compare against the tested task->timestamp to determine cache-hot-or-not, rather than using the local CPU's sched_clock() value. Also, task->timestamp needs to be readjusted when the task migrates:

diff -X /home/hawkes/Patches/ignore.dirs -Naur linux-2.6.0/kernel/sched.c linux-2.6.0-schedclock2/kernel/sched.c
@@ -199,7 +199,7 @@
 struct runqueue {
 	spinlock_t lock;
 	unsigned long nr_running, nr_switches, expired_timestamp,
-			nr_uninterruptible;
+			nr_uninterruptible, timestamp_last_tick;
 	task_t *curr, *idle;
 	struct mm_struct *prev_mm;
 	prio_array_t *active, *expired, arrays[2];

@@ -1135,6 +1135,7 @@
 	set_task_cpu(p, this_cpu);
 	nr_running_inc(this_rq);
 	enqueue_task(p, this_rq->active);
+	p->timestamp = sched_clock() - (src_rq->timestamp_last_tick - p->timestamp);
 	/*
 	 * Note that idle threads have a prio of MAX_PRIO, for this test
 	 * to be always true for them.

@@ -1155,7 +1156,7 @@
 static inline int
 can_migrate_task(task_t *tsk, runqueue_t *rq, int this_cpu, int idle)
 {
-	unsigned long delta = sched_clock() - tsk->timestamp;
+	unsigned long delta = rq->timestamp_last_tick - tsk->timestamp;
 
 	if (!idle && (delta <= JIFFIES_TO_NS(cache_decay_ticks)))
 		return 0;

@@ -1361,6 +1362,8 @@
 	runqueue_t *rq = this_rq();
 	task_t *p = current;
 
+	rq->timestamp_last_tick = sched_clock();
+
 	if (rcu_pending(cpu))
 		rcu_check_callbacks(cpu, user_ticks);
 

@@ -2639,6 +2642,8 @@
 		if (p->prio < rq_dest->curr->prio)
 			resched_task(rq_dest->curr);
 	}
+	p->timestamp = rq_dest->timestamp_last_tick;
+
  out:
 	double_rq_unlock(this_rq(), rq_dest);
 	local_irq_restore(flags);

My personal preference is to keep sched_clock() semantics unchanged (i.e., to presume that all CPU values are synchronized), and to bury non-compliant platform complexity in arch-specific and platform-specific implementations, rather than add any unnecessary complications to sched.c.

As a reference point, the current i386 2.6.0-test11 algorithm is platform- specific and is, in my opinion, less clean than the arch/ia64 change I have
proposed: all i386 NUMA platforms are forced to use the low-resolution "jiffies" value as the only officially synchronized timebase. (However, with my sched.c patch, it is possible that i386 NUMA platforms could use the unsynchronized higher resolution TSC.)

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
		return (unsigned long long)jiffies * (1000000000 / HZ);

	/* Read the Time Stamp Counter */
	rdtscll(this_offset);

	/* return the value in ns */
	return cycles_2_ns(this_offset);
}

This same "#ifndef CONFIG_NUMA" fallback-to-jiffies approach would work for ia64, but I don't see it as either visually superior to my platform-specific vector or as functionally superior, because all NUMA platforms would revert back to using the low-resolution jiffies as the sched_clock() timebase. The 2.4 kernel used jiffies, and someone decided that in 2.6 the scheduler needs a higher-resolution timestamp to better calculate process priority.

An unworkable approach (before anyone suggests it) is to periodically resync ITC clocks: an sn platform can theoretically support CPUs that run at different clock speeds, and thus these ITCs can never be synchronized.

Comments?

John Hawkes

Here is the full ia64 patch that Mosberger rejected:

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 (offset * local_cpu_data->nsec_per_cyc) >> IA64_NSEC_PER_CY

C_SHIFT;
+}
+
+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;
 }

[snip]

I've tried switching sched_clock() to call monotonic_clock() on i386 (both functions do basically the same thing, only monotonic_clock redirects to the system's chosen time source). However,the consensus was that the access time to read the systems non-"drifty" time source can be too expensive to make it worth while.

I'll concede that I haven't done enough testing to measure it in any great detail, but the interest in my patch was very very low. So I'd be interested in any measurements you have to the contrary.

Personally, I'd keep your changes arch specific for 2.6. When 2.7 opens I'd be very interested in ideas and input for broader change in the time subsystem.

thanks
-john

Requiring that sched_clock() be synchronised is difficult for some platforms. Clearly, it is better if we can relax that.

Your patch to kernel/sched.c looks good: low overhead, simple, Ingo likes it.

Could you please finalise it, cook up the ia64 and numaq implementations and send it over?

this is a tough problem that wont go away.

Even platforms where the per-CPU clock is supposed to be synchronized, sometimes it isnt. (this is a recurring problem on x86 SMP - so x86 will benefit from it too.)

the relaxation means the effective granularity reduction of the migration decisions - but this is not a problem, migration latencies are always a high multiple of the timer irq frequency. The cycle accuracy of sched_clock() is otherwise very important for correct interactivity decisions - but this is only used locally and is thus preserved by the patch. The only area where this change can reduce the quality of interactivity estimatio is when a task oscillates very quickly between multiple CPUs and is also somehow relevant to interactivity.

So i believe the generic relaxing of sched_clock() synchronization is the right thing to do. I like your patch. It adds minimal overhead and solves a hard problem - nice work! Andrew, please apply it.

Ingo

Its a great looking patch if you must have high res sched_clock. So I guess I agree with it.

Can we have a scheduler day when Andrew is ready to take patches for it? I have a few small changes that I'd like to get merged soon too (not sched domains - that should probably go to the mm tree for a while)

Relevant patches are
sched-ctx-count-preempt.patch
sched-fork-cleanup.patch
sched-migrate-comment.patch
sched-style.patch
sched-migrate-affinity-race.patch

miaow ;)

Post 'em.

I'm just thinking that computers with unsynched clocks have less need for good interactivity, but thats probably too narrow and x86 a view anyway.

OK, I'll trim the cc list though...

it's also a matter of predictable behavior. The scheduler should not behave differently just because there's no synchronized clock. Behavioral forks like that tend to come back and cause trouble later.

Ingo

Andrew what are they feeding you these days? ;)

x86 and TSCs don't do that great a job either ;)