[RFC PATCH] sched: rt: fix selecting runqueue for task to be pushed

[RFC PATCH] sched: rt: fix selecting runqueue for task to be pushed

[Hillf Danton]

When we are trying to push task out, no point to select the last cpu that
the given task executed on, which is fixed by selecting target cpu with
cache affinity concerned, and with SD_WAKE_AFFINE ignored as we are not
handling sleeper.

[based on upstream]

Signed-off-by: Hillf Danton <dhillf@gmail.com>
---

--- a/kernel/sched/rt.c	Mon Dec 10 19:52:20 2012
+++ b/kernel/sched/rt.c	Mon Dec 10 20:00:16 2012
@@ -1234,7 +1234,7 @@ static void yield_task_rt(struct rq *rq)
 }

 #ifdef CONFIG_SMP
-static int find_lowest_rq(struct task_struct *task);
+static int find_lowest_rq(struct task_struct *task, int pushing);

 static int
 select_task_rq_rt(struct task_struct *p, int sd_flag, int flags)
@@ -1283,7 +1283,7 @@ select_task_rq_rt(struct task_struct *p,
 	    (curr->nr_cpus_allowed < 2 ||
 	     curr->prio <= p->prio) &&
 	    (p->nr_cpus_allowed > 1)) {
-		int target = find_lowest_rq(p);
+		int target = find_lowest_rq(p, 0);

 		if (target != -1)
 			cpu = target;
@@ -1473,7 +1473,7 @@ next_idx:

 static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);

-static int find_lowest_rq(struct task_struct *task)
+static int find_lowest_rq(struct task_struct *task, int pushing)
 {
 	struct sched_domain *sd;
 	struct cpumask *lowest_mask = __get_cpu_var(local_cpu_mask);
@@ -1495,6 +1495,12 @@ static int find_lowest_rq(struct task_st
 	 * lowest priority tasks in the system.  Now we want to elect
 	 * the best one based on our affinity and topology.
 	 *
+	 * If we are pushing task out, ignore the last cpu that the
+	 * task executed on.
+	 */
+	if (pushing)
+		goto consult_sd;
+	/*
 	 * We prioritize the last cpu that the task executed on since
 	 * it is most likely cache-hot in that location.
 	 */
@@ -1508,8 +1514,21 @@ static int find_lowest_rq(struct task_st
 	if (!cpumask_test_cpu(this_cpu, lowest_mask))
 		this_cpu = -1; /* Skip this_cpu opt if not among lowest */

+consult_sd:
 	rcu_read_lock();
 	for_each_domain(cpu, sd) {
+		if (pushing) {
+			int sel;
+			for_each_cpu_and(sel, lowest_mask,
+					sched_domain_span(sd)) {
+				/* We prefer LLC cpu */
+				if (sel != cpu) {
+					rcu_read_unlock();
+					return sel;
+				}
+			}
+			continue;
+		}
 		if (sd->flags & SD_WAKE_AFFINE) {
 			int best_cpu;

@@ -1533,6 +1552,8 @@ static int find_lowest_rq(struct task_st
 	}
 	rcu_read_unlock();

+	if (pushing)
+		return -1;
 	/*
 	 * And finally, if there were no matches within the domains
 	 * just give the caller *something* to work with from the compatible
@@ -1555,7 +1576,7 @@ static struct rq *find_lock_lowest_rq(st
 	int cpu;

 	for (tries = 0; tries < RT_MAX_TRIES; tries++) {
-		cpu = find_lowest_rq(task);
+		cpu = find_lowest_rq(task, 1);

 		if ((cpu == -1) || (cpu == rq->cpu))
 			break;
--

Re: [RFC PATCH] sched: rt: fix selecting runqueue for task to be pushed

[Steven Rostedt]

On Mon, 2012-12-10 at 20:19 +0800, Hillf Danton wrote:
> When we are trying to push task out, no point to select the last cpu that
> the given task executed on, which is fixed by selecting target cpu with
> cache affinity concerned, and with SD_WAKE_AFFINE ignored as we are not
> handling sleeper.

I have to ask. Why?

The check you are skipping is if the task is running on a CPU that is
already the lowest CPU priority (lowest_mask returns the CPUs running
tasks of the lowest priority in the system). Which means that either the
task that we are pushing is the same priority or lesser priority than
what is running on the other CPUs. Either case, this task wont push out
a task on the other CPUs because it's not higher priority than those
tasks.

You just added more work for the same result (no push).

-- Steve

Re: [RFC PATCH] sched: rt: fix selecting runqueue for task to be pushed

[Hillf Danton]

On Mon, Dec 10, 2012 at 10:21 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> On Mon, 2012-12-10 at 20:19 +0800, Hillf Danton wrote:
>> When we are trying to push task out, no point to select the last cpu that
>> the given task executed on, which is fixed by selecting target cpu with
>> cache affinity concerned, and with SD_WAKE_AFFINE ignored as we are not
>> handling sleeper.
>
> I have to ask. Why?
>
> The check you are skipping is if the task is running on a CPU that is
> already the lowest CPU priority (lowest_mask returns the CPUs running
> tasks of the lowest priority in the system).

Hm ... how do you get the lowest mask for a pushable task iff
that check makes sense?

> Which means that either the
> task that we are pushing is the same priority or lesser priority than
> what is running on the other CPUs. Either case, this task wont push out
> a task on the other CPUs because it's not higher priority than those
> tasks.
>
> You just added more work for the same result (no push).
>
> -- Steve
>
>

Re: [RFC PATCH] sched: rt: fix selecting runqueue for task to be pushed

[Steven Rostedt]

On Tue, 2012-12-11 at 20:10 +0800, Hillf Danton wrote:
> On Mon, Dec 10, 2012 at 10:21 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> > On Mon, 2012-12-10 at 20:19 +0800, Hillf Danton wrote:
> >> When we are trying to push task out, no point to select the last cpu that
> >> the given task executed on, which is fixed by selecting target cpu with
> >> cache affinity concerned, and with SD_WAKE_AFFINE ignored as we are not
> >> handling sleeper.
> >
> > I have to ask. Why?
> >
> > The check you are skipping is if the task is running on a CPU that is
> > already the lowest CPU priority (lowest_mask returns the CPUs running
> > tasks of the lowest priority in the system).
> 
> Hm ... how do you get the lowest mask for a pushable task iff
> that check makes sense?

I'm actually thinking that that test should always fail. The
cpupri_find() does a scan of all priorities up to but not including the
current task's priority. If cpupri_find() finds a mask, it means that it
found CPUs that are running only tasks of lower priority than the task
we are checking. Which means, it should never include the task's CPU, as
that CPU should have a higher priority than what is being returned by
lowest_mask. If it can't find a set of CPUs of lower priority, it should
return false, and the find_lowest_rq() should exit.

I'll add a WARN_ON_ONCE() there, and see if I can trigger it. :-/


-- Steve

Re: [RFC PATCH] sched: rt: fix selecting runqueue for task to be pushed

[Steven Rostedt]

On Tue, 2012-12-11 at 20:54 -0500, Steven Rostedt wrote:

> I'm actually thinking that that test should always fail. The
> cpupri_find() does a scan of all priorities up to but not including the
> current task's priority. If cpupri_find() finds a mask, it means that it
> found CPUs that are running only tasks of lower priority than the task
> we are checking. Which means, it should never include the task's CPU, as
> that CPU should have a higher priority than what is being returned by
> lowest_mask. If it can't find a set of CPUs of lower priority, it should
> return false, and the find_lowest_rq() should exit.
> 
> I'll add a WARN_ON_ONCE() there, and see if I can trigger it. :-/

Ah, for select_task_rq_rt() it can get that CPU, because it's called in
the wakeup path before the task is added into the CPUs priority. And we
definitely want the current CPU in that case.

For pushing, the local CPU should never be returned. I'll check to make
sure that's the case too.

-- Steve

Re: [RFC PATCH] sched: rt: fix selecting runqueue for task to be pushed

[Hillf Danton]

On Wed, Dec 12, 2012 at 10:46 AM, Steven Rostedt <rostedt@goodmis.org> wrote:
> On Tue, 2012-12-11 at 20:54 -0500, Steven Rostedt wrote:
>
>> I'm actually thinking that that test should always fail. The
>> cpupri_find() does a scan of all priorities up to but not including the
>> current task's priority. If cpupri_find() finds a mask, it means that it
>> found CPUs that are running only tasks of lower priority than the task
>> we are checking. Which means, it should never include the task's CPU, as
>> that CPU should have a higher priority than what is being returned by
>> lowest_mask. If it can't find a set of CPUs of lower priority, it should
>> return false, and the find_lowest_rq() should exit.
>>
>> I'll add a WARN_ON_ONCE() there, and see if I can trigger it. :-/
>
> Ah, for select_task_rq_rt() it can get that CPU, because it's called in
> the wakeup path before the task is added into the CPUs priority. And we
> definitely want the current CPU in that case.
>
Hm ... the latency of the woken task increases iff we overload its
runqueue, no?

Hillf

Re: [RFC PATCH] sched: rt: fix selecting runqueue for task to be pushed

[Steven Rostedt]

On Wed, 2012-12-12 at 19:44 +0800, Hillf Danton wrote:
> On Wed, Dec 12, 2012 at 10:46 AM, Steven Rostedt <rostedt@goodmis.org> wrote:
> > On Tue, 2012-12-11 at 20:54 -0500, Steven Rostedt wrote:
> >
> >> I'm actually thinking that that test should always fail. The
> >> cpupri_find() does a scan of all priorities up to but not including the
> >> current task's priority. If cpupri_find() finds a mask, it means that it
> >> found CPUs that are running only tasks of lower priority than the task
> >> we are checking. Which means, it should never include the task's CPU, as
> >> that CPU should have a higher priority than what is being returned by
> >> lowest_mask. If it can't find a set of CPUs of lower priority, it should
> >> return false, and the find_lowest_rq() should exit.
> >>
> >> I'll add a WARN_ON_ONCE() there, and see if I can trigger it. :-/
> >
> > Ah, for select_task_rq_rt() it can get that CPU, because it's called in
> > the wakeup path before the task is added into the CPUs priority. And we
> > definitely want the current CPU in that case.
> >
> Hm ... the latency of the woken task increases iff we overload its
> runqueue, no?
> 

No, it doesn't.

-- Steve