Skip to contentSkip to conversation

bug in sched.c:activate_task()

PATCH Chen, Kenneth W 6 participants 17 messages Oct 5, 2004 Scheduler

lore
Share & tools
lore
#0 lore raw

Update p->timestamp to "now" in activate_task() doesn't look right to me at all. p->timestamp records last time it was running on a cpu. activate_task shouldn't update that variable when it queues a task on the runqueue.

This bug (and combined with others) triggers improper load balancing.

Patch against linux-2.6.9-rc3. Didn't diff it against 2.6.9-rc3-mm2 because mm tree has so many change in sched.c.

kernel/sched.c renamed from kernel/sched.c.orig +0 -1
@@ -888,7 +888,6 @@ static void activate_task(task_t *p, run
 			p->activated = 1;
 		}
 	}
-	p->timestamp = now;
 
 	__activate_task(p, rq);
 }
#1 lore raw
Quoted 6 lines · Kenneth W

Update p->timestamp to "now" in activate_task() doesn't look right to me at all. p->timestamp records last time it was running on a cpu. activate_task shouldn't update that variable when it queues a task on the runqueue.

This bug (and combined with others) triggers improper load balancing.

The updated timestamp was placed there by Ingo to detect on-runqueue time. If it is being used for load balancing then it is being used in error.

Con

#2 lore raw
Quoted 7 lines · Con Kolivas
Quoted 5 lines · Kenneth W

Update p->timestamp to "now" in activate_task() doesn't look right to me at all. p->timestamp records last time it was running on a cpu. activate_task shouldn't update that variable when it queues a task on the runqueue.

Quoted 5 lines
Quoted 1 line

This bug (and combined with others) triggers improper load balancing.

The updated timestamp was placed there by Ingo to detect on-runqueue time. If it is being used for load balancing then it is being used in error.

Load balancing wants to know if a task is considered cache hot.

#3 lore raw
Quoted 9 lines · Nick Piggin
Quoted 7 lines · Con Kolivas
Quoted 5 lines · Kenneth W

Update p->timestamp to "now" in activate_task() doesn't look right to me at all. p->timestamp records last time it was running on a cpu. activate_task shouldn't update that variable when it queues a task on the runqueue.

Quoted 7 lines
Quoted 5 lines
Quoted 1 line

This bug (and combined with others) triggers improper load balancing.

The updated timestamp was placed there by Ingo to detect on-runqueue time. If it is being used for load balancing then it is being used in error.

Load balancing wants to know if a task is considered cache hot.

Yes I know. It used to be performed based on jiffies which was adequate resolution for cache warmth at the time. The timestamp was being used for on runqueue length measurement before the load balancing was modified to use that value.

Con

#4 lore raw
In reply to Con Kolivas
Quoted 11 lines · Con Kolivas
Quoted 6 lines · Kenneth W

Update p->timestamp to "now" in activate_task() doesn't look right to me at all. p->timestamp records last time it was running on a cpu. activate_task shouldn't update that variable when it queues a task on the runqueue.

This bug (and combined with others) triggers improper load balancing.

The updated timestamp was placed there by Ingo to detect on-runqueue time. If it is being used for load balancing then it is being used in error.

The ZAPHOD scheduler (being trialled in 2.6.9-rc3-mm2) uses its own time stamp so as not to interfere with the use of timestamp by load balancing code so it should be OK to delete this line form activate_task() in 2.6.9-rc3-mm2 without effecting ZAPHOD.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce
#5 lore raw
In reply to Chen, Kenneth W
Quoted 5 lines · Kenneth W

Update p->timestamp to "now" in activate_task() doesn't look right to me at all. p->timestamp records last time it was running on a cpu. activate_task shouldn't update that variable when it queues a task on the runqueue.

Quoted 7 lines

This bug (and combined with others) triggers improper load balancing.

Patch against linux-2.6.9-rc3. Didn't diff it against 2.6.9-rc3-mm2 because mm tree has so many change in sched.c.

Actually, now that I have the code in front of me, I was wrong and this patch is right.

This timestamp is never used for anything, so the assignment is pointless.

maintainer
#6 lore raw
In reply to Chen, Kenneth W
Quoted 4 lines · Kenneth W

Update p->timestamp to "now" in activate_task() doesn't look right to me at all. p->timestamp records last time it was running on a cpu. activate_task shouldn't update that variable when it queues a task on the runqueue.

correct, we are overriding it in schedule():

        if (likely(prev != next)) {
                next->timestamp = now;
                rq->nr_switches++;

the line your patch removes is a remnant of an earlier logic when we timestamped tasks when they touched the runqueue. (vs. timestamping when they actually run on a CPU.) So the patch looks good to me. Andrew, please apply.

Ingo

Quoted 27 lines

This bug (and combined with others) triggers improper load balancing.

Patch against linux-2.6.9-rc3. Didn't diff it against 2.6.9-rc3-mm2 because mm tree has so many change in sched.c.

kernel/sched.c renamed from kernel/sched.c.orig +0 -2
@@ -888,7 +888,6 @@ static void activate_task(task_t *p, run
 			p->activated = 1;
 		}
 	}
-	p->timestamp = now;
 
 	__activate_task(p, rq);
 }
 
 
-

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

#7 lore raw
Quoted 9 lines · Ingo Molnar
Quoted 3 lines · Kenneth W

Update p->timestamp to "now" in activate_task() doesn't look right to me
at all. p->timestamp records last time it was running on a cpu. activate_task shouldn't update that variable when it queues a task on the runqueue.

correct, we are overriding it in schedule():

Quoted 8 lines
        if (likely(prev != next)) {
                next->timestamp = now;
                rq->nr_switches++;

the line your patch removes is a remnant of an earlier logic when we timestamped tasks when they touched the runqueue. (vs. timestamping when they actually run on a CPU.) So the patch looks good to me. Andrew, please apply.

	unsigned long long delta = now - next->timestamp;

	if (next->activated == 1)
		delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;

is in schedule() before we update the timestamp, no?

Con

maintainer
#8 lore raw
Quoted 6 lines · Con Kolivas
	unsigned long long delta = now - next->timestamp;

	if (next->activated == 1)
		delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;

is in schedule() before we update the timestamp, no?

indeed ... so the patch is just random incorrect damage that happened to distrub the scheduler fixing some balancing problem. Kenneth, what precisely is the balancing problem you are seeing?

Ingo

#9 lore raw
Quoted 5 lines · Ingo Molnar
Quoted 2 lines · Con Kolivas
	unsigned long long delta = now - next->timestamp;
Quoted 8 lines
Quoted 4 lines
	if (next->activated == 1)
		delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;

is in schedule() before we update the timestamp, no?

indeed ... so the patch is just random incorrect damage that happened to distrub the scheduler fixing some balancing problem. Kenneth, what precisely is the balancing problem you are seeing?

We used to compare jiffy difference in can_migrate_task by comparing it to cache_decay_ticks. Somewhere in the merging of sched_domains it was changed to task_hot which uses timestamp.

Con

#10 lore raw
Quoted 13 lines · Con Kolivas
Quoted 11 lines · Ingo Molnar
Quoted 6 lines · Con Kolivas
    unsigned long long delta = now - next->timestamp;

    if (next->activated == 1)
        delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;

is in schedule() before we update the timestamp, no?

Quoted 8 lines
Quoted 3 lines

indeed ... so the patch is just random incorrect damage that happened to distrub the scheduler fixing some balancing problem. Kenneth, what precisely is the balancing problem you are seeing?

We used to compare jiffy difference in can_migrate_task by comparing it to cache_decay_ticks. Somewhere in the merging of sched_domains it was changed to task_hot which uses timestamp.

It always used ->timestamp though, even when that was in jiffies. sched domains didn't change anything there (and IIRC it used task_hot before sched domains).

maintainer
#11 lore raw
In reply to Con Kolivas
Quoted 3 lines · Con Kolivas

We used to compare jiffy difference in can_migrate_task by comparing it to cache_decay_ticks. Somewhere in the merging of sched_domains it was changed to task_hot which uses timestamp.

yep, that's fishy. Kenneth, could you try the simple patch below? It gets rid of task_hot() in essence. If this works out we could try it - it gets rid of some more code from sched.c too. Perhaps SD_WAKE_AFFINE is enough control.

Ingo

sched.c renamed from sched.c.orig +1 -1
@@ -180,7 +180,7 @@ static unsigned int task_timeslice(task_
 	else
 		return SCALE_PRIO(DEF_TIMESLICE, p->static_prio);
 }
-#define task_hot(p, now, sd) ((now) - (p)->timestamp < (sd)->cache_hot_time)
+#define task_hot(p, now, sd) 0
 
 enum idle_type
 {
#12 lore raw
Quoted 3 lines · Con Kolivas

We used to compare jiffy difference in can_migrate_task by comparing it to cache_decay_ticks. Somewhere in the merging of sched_domains it was changed to task_hot which uses timestamp.

Quoted 8 lines · Ingo Molnar

yep, that's fishy. Kenneth, could you try the simple patch below? It gets rid of task_hot() in essence. If this works out we could try it - it gets rid of some more code from sched.c too. Perhaps SD_WAKE_AFFINE is enough control.

sched.c static unsigned int task_timeslice(task_ · line 186

Quoted 8 lines
sched.c renamed from sched.c.orig +1 -1
@@ -180,7 +180,7 @@ static unsigned int task_timeslice(task_
 	else
 		return SCALE_PRIO(DEF_TIMESLICE, p->static_prio);
 }
-#define task_hot(p, now, sd) ((now) - (p)->timestamp < (sd)->cache_hot_time)
+#define task_hot(p, now, sd) 0
 
 enum idle_type
 {

We have experimented with similar thing, via bumping up sd->cache_hot_time to a very large number, like 1 sec. What we measured was a equally low throughput. But that was because of not enough load balancing, we are seeing is large amount of idle time.

- Ken

#13 lore raw
In reply to Ingo Molnar

Ingo Molnar wrote on Monday, October 04, 2004 11:55 PM

Quoted 12 lines · Con Kolivas
Quoted 7 lines
	unsigned long long delta = now - next->timestamp;

	if (next->activated == 1)
		delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;

is in schedule() before we update the timestamp, no?

indeed ... so the patch is just random incorrect damage that happened to distrub the scheduler fixing some balancing problem. Kenneth, what precisely is the balancing problem you are seeing?

We are seeing truck load of move_task() which was originated from newly idle load balance. The problem is load balancing going nuts moving tons of tasks around and what we are seeing is cache misses for the application shots up to the roof and suffering from cache threshing.

- Ken

#14 lore raw
In reply to Con Kolivas
Quoted 22 lines · Con Kolivas
Quoted 10 lines · Ingo Molnar
Quoted 3 lines · Kenneth W

Update p->timestamp to "now" in activate_task() doesn't look right to me
at all. p->timestamp records last time it was running on a cpu. activate_task shouldn't update that variable when it queues a task on the runqueue.

correct, we are overriding it in schedule():

Quoted 8 lines
        if (likely(prev != next)) {
                next->timestamp = now;
                rq->nr_switches++;

the line your patch removes is a remnant of an earlier logic when we timestamped tasks when they touched the runqueue. (vs. timestamping when they actually run on a CPU.) So the patch looks good to me. Andrew, please apply.

Quoted 7 lines
    unsigned long long delta = now - next->timestamp;

    if (next->activated == 1)
        delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;

is in schedule() before we update the timestamp, no?

Yeah right, unfortunately.

#15 lore raw
In reply to Chen, Kenneth W
Quoted 4 lines · Chen, Kenneth W

Update p->timestamp to "now" in activate_task() doesn't look right to me at all. p->timestamp records last time it was running on a cpu. activate_task shouldn't update that variable when it queues a task on the runqueue.

it is being used for multiple purposes: measuring on-CPU time, measuring on-runqueue time (for interactivity) and measuring off-runqueue time (for interactivity). It is also used to measure cache-hotness, by the balancing code.

now, this particular update of p->timestamp:

Review static void activate_task(task_t *p, run · line 889

Quoted 3 lines
(quoted diff) +0 -1
@@ -888,7 +888,6 @@ static void activate_task(task_t *p, run
 
-	p->timestamp = now;

is important for the interactivity code that runs in schedule() - it wants to know how much time we spent on the runqueue without having run.

but you are right that the task_hot() use of p->timestamp is incorrect for freshly woken up tasks - we want the balancer to be able to re-route tasks to another CPU, as long as the task has not hit the runqueue yet (which it hasnt where we consider it in the balancer).

the clean solution is to separate the multiple uses of p->timestamp:
with the patch below p->timestamp is purely used for the interactivity code, and p->last_ran is for the rebalancer. The patch is ontop of your task_hot() fix-patch. Does this work for your workload?

Ingo

kernel/sched.c renamed from kernel/sched.c.orig +3 -2
@@ -185,7 +185,8 @@ static unsigned int task_timeslice(task_
 	else
 		return SCALE_PRIO(DEF_TIMESLICE, p->static_prio);
 }
-#define task_hot(p, now, sd) ((now) - (p)->timestamp < (sd)->cache_hot_time)
+#define task_hot(p, now, sd) ((long long) ((now) - (p)->last_ran)	\
+				< (long long) (sd)->cache_hot_time)
 
 /*
  * These are the runqueue data structures:
@@ -2833,7 +2834,7 @@ switch_tasks:
 		if (!(HIGH_CREDIT(prev) || LOW_CREDIT(prev)))
 			prev->interactive_credit--;
 	}
-	prev->timestamp = now;
+	prev->timestamp = prev->last_ran = now;
 
 	sched_info_switch(prev, next);
 	if (likely(prev != next)) {
include/linux/sched.h renamed from include/linux/sched.h.orig +1 -1
@@ -527,7 +527,7 @@ struct task_struct {
 
 	unsigned long sleep_avg;
 	long interactive_credit;
-	unsigned long long timestamp;
+	unsigned long long timestamp, last_ran;
 	int activated;
 
 	unsigned long policy;
#16 lore raw
Quoted 4 lines · Chen, Kenneth W

Update p->timestamp to "now" in activate_task() doesn't look right to me at all. p->timestamp records last time it was running on a cpu. activate_task shouldn't update that variable when it queues a task on the runqueue.

Ingo Molnar wrote on Tuesday, October 05, 2004 1:19 AM

Quoted 19 lines

it is being used for multiple purposes: measuring on-CPU time, measuring on-runqueue time (for interactivity) and measuring off-runqueue time (for interactivity). It is also used to measure cache-hotness, by the balancing code.

now, this particular update of p->timestamp:

Review static void activate_task(task_t *p, run · line 889

Quoted 3 lines
(quoted diff) +0 -1
@@ -888,7 +888,6 @@ static void activate_task(task_t *p, run
 
-	p->timestamp = now;

is important for the interactivity code that runs in schedule() - it wants to know how much time we spent on the runqueue without having run.

but you are right that the task_hot() use of p->timestamp is incorrect for freshly woken up tasks - we want the balancer to be able to re-route tasks to another CPU, as long as the task has not hit the runqueue yet (which it hasnt where we consider it in the balancer).

Quoted 4 lines

the clean solution is to separate the multiple uses of p->timestamp:
with the patch below p->timestamp is purely used for the interactivity code, and p->last_ran is for the rebalancer. The patch is ontop of your task_hot() fix-patch. Does this work for your workload?

I will take this for a spin and report back the result.

- Ken