Re: bug in sched.c:task_hot()
From: Peter Williams
Date: Tue Oct 05 2004 - 03:10:01 EST
Nick Piggin wrote:
Peter Williams wrote:
Chen, Kenneth W wrote:
Current implementation of task_hot() has a performance bug in it
that it will cause integer underflow.
Variable "now" (typically passed in as rq->timestamp_last_tick)
and p->timestamp are all defined as unsigned long long. However,
If former is smaller than the latter, integer under flow occurs
which make the result of subtraction a huge positive number. Then
it is compared to sd->cache_hot_time and it will wrongly identify
a cache hot task as cache cold.
This bug causes large amount of incorrect process migration across
cpus (at stunning 10,000 per second) and we lost cache affinity very
quickly and almost took double digit performance regression on a db
transaction processing workload. Patch to fix the bug. Diff'ed against
Signed-off-by: Ken Chen <kenneth.w.chen@xxxxxxxxx>
--- linux-2.6.9-rc3/kernel/sched.c.orig 2004-10-04
+++ linux-2.6.9-rc3/kernel/sched.c 2004-10-04 19:19:27.000000000
@@ -180,7 +180,8 @@ static unsigned int task_timeslice(task_
return SCALE_PRIO(DEF_TIMESLICE, p->static_prio);
-#define task_hot(p, now, sd) ((now) - (p)->timestamp <
+#define task_hot(p, now, sd) ((long long) ((now) - (p)->timestamp) \
+ < (long long) (sd)->cache_hot_time)
The interesting question is: How does now get to be less than
timestamp? This probably means that timestamp_last_tick is not a good
way of getting a value for "now".
It is the best we can do.
You could use sched_clock() which will do better. The setting of
timestamp in schedule() gives you a pretty good chance that it's value
will be greater than timestamp_last_tick.
By the way, neither is sched_clock() when measuring small time
differences as it is not monotonic (something that I had to allow for
in my scheduling code).
I'm pretty sure it is monotonic, actually. I know some CPUs can execute
rdtsc speculatively, but I don't think it would ever be sane to execute
two rdtsc's in the wrong order.
I have experienced it going backwards and I assumed that it was due to
the timing code applying corrections. (You've got two choices if your
clock is running fast: one is to mark time until the real world catches
up with you and the other is to set your clock back to the correct time
when you notice a discrepancy. I assumed that the second strategy had
been followed by the time code and didn't bother checking further
because it was an easy problem to sidestep.) Admittedly, this behaviour
was only observed when measuring very short times such as the time spent
on the runqueue waiting for CPU access when the system was idle BUT it
was definitely occurring. And it only occurred on a system where the
lower bits of the values returned by sched_clock() were not zero i.e. a
reasonably modern one. It was observed on a single CPU machine as well
and was not, therefore, a result of drift between CPUs.
I applied no such safeguards to the timing used by the load balancing
code as I assumed that it already worked.
It should (modulo this bug).
I'm reasonably confident that ZAPHOD doesn't change the values of
timestamp or timestamp_last_tick to something that they would not have
been without ZAPHOD and there are other scheduler changes (than
ZAPHOD's) in -mm2 which may bear examination.
ZAPHOD also did not introduce the declaration of these values as
unsigned long long as that is present in rc3. BTW a quick to the
problem is to change their declarations to just long long as we don't
need the 64th bit for a few hundred years.
Peter Williams pwil3058@xxxxxxxxxxxxxx
"Learning, n. The kind of ignorance distinguishing the studious."
-- Ambrose Bierce
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/