[PATCH] sched: remove the next highest_prio in RT scheduling

[PATCH] sched: remove the next highest_prio in RT scheduling

[Hillf Danton]

The next highest_prio element in rt_rq structure, is only used when pulling
RT task. As shown by the following snippet (in diff format for clearity),

-		if (src_rq->rt.highest_prio.next >=
+		if (src_rq->rt.highest_prio.curr >=
 		    this_rq->rt.highest_prio.curr)
 			continue;

the "next" could be replaced with "curr" in the above comparison, since
the next is no less than curr by definition.

Then operations for updating the element are deleted accordingly.

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

--- tip-git/kernel/sched.c	Sun May 22 18:21:46 2011
+++ sched.c	Sat May 28 20:53:24 2011
@@ -384,9 +384,6 @@ struct rt_rq {
 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
 	struct {
 		int curr; /* highest queued rt task prio */
-#ifdef CONFIG_SMP
-		int next; /* next highest */
-#endif
 	} highest_prio;
 #endif
 #ifdef CONFIG_SMP
@@ -7718,9 +7715,6 @@ static void init_rt_rq(struct rt_rq *rt_

 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
 	rt_rq->highest_prio.curr = MAX_RT_PRIO;
-#ifdef CONFIG_SMP
-	rt_rq->highest_prio.next = MAX_RT_PRIO;
-#endif
 #endif
 #ifdef CONFIG_SMP
 	rt_rq->rt_nr_migratory = 0;
--- tip-git/kernel/sched_rt.c	Sun May 22 20:12:01 2011
+++ sched_rt.c	Sat May 28 21:00:04 2011
@@ -664,67 +664,19 @@ static void update_curr_rt(struct rq *rq

 #if defined CONFIG_SMP

-static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu);
-
-static inline int next_prio(struct rq *rq)
-{
-	struct task_struct *next = pick_next_highest_task_rt(rq, rq->cpu);
-
-	if (next && rt_prio(next->prio))
-		return next->prio;
-	else
-		return MAX_RT_PRIO;
-}
-
-static void
-inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
-{
-	struct rq *rq = rq_of_rt_rq(rt_rq);
-
-	if (prio < prev_prio) {
-
-		/*
-		 * If the new task is higher in priority than anything on the
-		 * run-queue, we know that the previous high becomes our
-		 * next-highest.
-		 */
-		rt_rq->highest_prio.next = prev_prio;
-
-		if (rq->online)
-			cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
-
-	} else if (prio == rt_rq->highest_prio.curr)
-		/*
-		 * If the next task is equal in priority to the highest on
-		 * the run-queue, then we implicitly know that the next highest
-		 * task cannot be any lower than current
-		 */
-		rt_rq->highest_prio.next = prio;
-	else if (prio < rt_rq->highest_prio.next)
-		/*
-		 * Otherwise, we need to recompute next-highest
-		 */
-		rt_rq->highest_prio.next = next_prio(rq);
-}
-
 static void
-dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
+update_rt_prio_smp(struct rt_rq *rt_rq, int prev_prio)
 {
 	struct rq *rq = rq_of_rt_rq(rt_rq);

-	if (rt_rq->rt_nr_running && (prio <= rt_rq->highest_prio.next))
-		rt_rq->highest_prio.next = next_prio(rq);
-
 	if (rq->online && rt_rq->highest_prio.curr != prev_prio)
 		cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr);
 }

 #else /* CONFIG_SMP */

-static inline
-void inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}
-static inline
-void dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}
+static inline void
+update_rt_prio_smp(struct rt_rq *rt_rq, int prev_prio) {}

 #endif /* CONFIG_SMP */

@@ -737,7 +689,7 @@ inc_rt_prio(struct rt_rq *rt_rq, int pri
 	if (prio < prev_prio)
 		rt_rq->highest_prio.curr = prio;

-	inc_rt_prio_smp(rt_rq, prio, prev_prio);
+	update_rt_prio_smp(rt_rq, prev_prio);
 }

 static void
@@ -763,7 +715,7 @@ dec_rt_prio(struct rt_rq *rt_rq, int pri
 	} else
 		rt_rq->highest_prio.curr = MAX_RT_PRIO;

-	dec_rt_prio_smp(rt_rq, prio, prev_prio);
+	update_rt_prio_smp(rt_rq, prev_prio);
 }

 #else
@@ -1456,7 +1408,7 @@ static int pull_rt_task(struct rq *this_
 		 * logically higher, the src_rq will push this task away.
 		 * And if its going logically lower, we do not care
 		 */
-		if (src_rq->rt.highest_prio.next >=
+		if (src_rq->rt.highest_prio.curr >=
 		    this_rq->rt.highest_prio.curr)
 			continue;

Re: [PATCH] sched: remove the next highest_prio in RT scheduling

[Steven Rostedt]

On Sat, 2011-05-28 at 22:25 +0800, Hillf Danton wrote:
> The next highest_prio element in rt_rq structure, is only used when pulling
> RT task. As shown by the following snippet (in diff format for clearity),
> 
> -		if (src_rq->rt.highest_prio.next >=
> +		if (src_rq->rt.highest_prio.curr >=
>  		    this_rq->rt.highest_prio.curr)
>  			continue;
> 
> the "next" could be replaced with "curr" in the above comparison, since
> the next is no less than curr by definition.

But it completely misses the point of what we are doing. We will never
pull a running task, but we can pull a waiting task. That's the point of
the "next" field. We want to know if a high priority task is waiting to
run, and if so, then we will pull it over to this CPU because this CPU
is about to switch to a task with a lower priority. If a waiting task of
higher priority than this CPU is on another CPU, we want to pull it
over.

This patch totally breaks this. We don't care about "curr" we care about
"next".

-- Steve

> 
> Then operations for updating the element are deleted accordingly.
> 
> Signed-off-by: Hillf Danton <dhillf@gmail.com>
> ---
> 
> --- tip-git/kernel/sched.c	Sun May 22 18:21:46 2011
> +++ sched.c	Sat May 28 20:53:24 2011
> @@ -384,9 +384,6 @@ struct rt_rq {
>  #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
>  	struct {
>  		int curr; /* highest queued rt task prio */
> -#ifdef CONFIG_SMP
> -		int next; /* next highest */
> -#endif
>  	} highest_prio;
>  #endif
>  #ifdef CONFIG_SMP
> @@ -7718,9 +7715,6 @@ static void init_rt_rq(struct rt_rq *rt_
> 
>  #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
>  	rt_rq->highest_prio.curr = MAX_RT_PRIO;
> -#ifdef CONFIG_SMP
> -	rt_rq->highest_prio.next = MAX_RT_PRIO;
> -#endif
>  #endif
>  #ifdef CONFIG_SMP
>  	rt_rq->rt_nr_migratory = 0;
> --- tip-git/kernel/sched_rt.c	Sun May 22 20:12:01 2011
> +++ sched_rt.c	Sat May 28 21:00:04 2011
> @@ -664,67 +664,19 @@ static void update_curr_rt(struct rq *rq
> 
>  #if defined CONFIG_SMP
> 
> -static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu);
> -
> -static inline int next_prio(struct rq *rq)
> -{
> -	struct task_struct *next = pick_next_highest_task_rt(rq, rq->cpu);
> -
> -	if (next && rt_prio(next->prio))
> -		return next->prio;
> -	else
> -		return MAX_RT_PRIO;
> -}
> -
> -static void
> -inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
> -{
> -	struct rq *rq = rq_of_rt_rq(rt_rq);
> -
> -	if (prio < prev_prio) {
> -
> -		/*
> -		 * If the new task is higher in priority than anything on the
> -		 * run-queue, we know that the previous high becomes our
> -		 * next-highest.
> -		 */
> -		rt_rq->highest_prio.next = prev_prio;
> -
> -		if (rq->online)
> -			cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
> -
> -	} else if (prio == rt_rq->highest_prio.curr)
> -		/*
> -		 * If the next task is equal in priority to the highest on
> -		 * the run-queue, then we implicitly know that the next highest
> -		 * task cannot be any lower than current
> -		 */
> -		rt_rq->highest_prio.next = prio;
> -	else if (prio < rt_rq->highest_prio.next)
> -		/*
> -		 * Otherwise, we need to recompute next-highest
> -		 */
> -		rt_rq->highest_prio.next = next_prio(rq);
> -}
> -
>  static void
> -dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
> +update_rt_prio_smp(struct rt_rq *rt_rq, int prev_prio)
>  {
>  	struct rq *rq = rq_of_rt_rq(rt_rq);
> 
> -	if (rt_rq->rt_nr_running && (prio <= rt_rq->highest_prio.next))
> -		rt_rq->highest_prio.next = next_prio(rq);
> -
>  	if (rq->online && rt_rq->highest_prio.curr != prev_prio)
>  		cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr);
>  }
> 
>  #else /* CONFIG_SMP */
> 
> -static inline
> -void inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}
> -static inline
> -void dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}
> +static inline void
> +update_rt_prio_smp(struct rt_rq *rt_rq, int prev_prio) {}
> 
>  #endif /* CONFIG_SMP */
> 
> @@ -737,7 +689,7 @@ inc_rt_prio(struct rt_rq *rt_rq, int pri
>  	if (prio < prev_prio)
>  		rt_rq->highest_prio.curr = prio;
> 
> -	inc_rt_prio_smp(rt_rq, prio, prev_prio);
> +	update_rt_prio_smp(rt_rq, prev_prio);
>  }
> 
>  static void
> @@ -763,7 +715,7 @@ dec_rt_prio(struct rt_rq *rt_rq, int pri
>  	} else
>  		rt_rq->highest_prio.curr = MAX_RT_PRIO;
> 
> -	dec_rt_prio_smp(rt_rq, prio, prev_prio);
> +	update_rt_prio_smp(rt_rq, prev_prio);
>  }
> 
>  #else
> @@ -1456,7 +1408,7 @@ static int pull_rt_task(struct rq *this_
>  		 * logically higher, the src_rq will push this task away.
>  		 * And if its going logically lower, we do not care
>  		 */
> -		if (src_rq->rt.highest_prio.next >=
> +		if (src_rq->rt.highest_prio.curr >=
>  		    this_rq->rt.highest_prio.curr)
>  			continue;

Re: [PATCH] sched: remove the next highest_prio in RT scheduling

[Hillf Danton]

On Tue, May 31, 2011 at 10:40 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> On Sat, 2011-05-28 at 22:25 +0800, Hillf Danton wrote:
>> The next highest_prio element in rt_rq structure, is only used when pulling
>> RT task. As shown by the following snippet (in diff format for clearity),
>>
>> -             if (src_rq->rt.highest_prio.next >=
>> +             if (src_rq->rt.highest_prio.curr >=
>>                   this_rq->rt.highest_prio.curr)
>>                       continue;
>>
>> the "next" could be replaced with "curr" in the above comparison, since
>> the next is no less than curr by definition.
>
> But it completely misses the point of what we are doing. We will never
> pull a running task, but we can pull a waiting task. That's the point of
> the "next" field. We want to know if a high priority task is waiting to
> run, and if so, then we will pull it over to this CPU because this CPU
> is about to switch to a task with a lower priority. If a waiting task of
> higher priority than this CPU is on another CPU, we want to pull it
> over.
>
> This patch totally breaks this. We don't care about "curr" we care about
> "next".
>
Hi Steven

Both the next and curr reach same result, or incorrect result, before locking
RQ, as the comment says, it is racy. After locking RQ, priority is checked again
to pull the correct tasks with no running task included. The difference between
the next and curr before locking RQ is the core of the patch that incorrect
result could be achieved with no updating the next field.

thanks
           Hillf

Re: [PATCH] sched: remove the next highest_prio in RT scheduling

[Steven Rostedt]

On Sat, 2011-06-04 at 12:44 +0800, Hillf Danton wrote:

> Both the next and curr reach same result, or incorrect result, before locking

Not quite. curr could be of higher priority than this rq, but next be of
lower priority. In that case, we still want to skip the rq.

But this patch does simplify things, and I give you credit for that.
I'll have to run some tests to see how much in practice this occurs, and
see if it is worth removing and using your method instead.

-- Steve

> RQ, as the comment says, it is racy. After locking RQ, priority is checked again
> to pull the correct tasks with no running task included. The difference between
> the next and curr before locking RQ is the core of the patch that incorrect
> result could be achieved with no updating the next field.
> 
> thanks
>            Hillf

Re: [PATCH] sched: remove the next highest_prio in RT scheduling

[Hillf Danton]

On Sat, Jun 4, 2011 at 1:06 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> On Sat, 2011-06-04 at 12:44 +0800, Hillf Danton wrote:
>
>> Both the next and curr reach same result, or incorrect result, before locking
>
> Not quite. curr could be of higher priority than this rq, but next be of
> lower priority. In that case, we still want to skip the rq.
>
> But this patch does simplify things, and I give you credit for that.
> I'll have to run some tests to see how much in practice this occurs, and
> see if it is worth removing and using your method instead.
>
Hi Steve

Big surprise, you work on Saturday!

good weekend

Hillf
>
>> RQ, as the comment says, it is racy. After locking RQ, priority is checked again
>> to pull the correct tasks with no running task included. The difference between
>> the next and curr before locking RQ is the core of the patch that incorrect
>> result could be achieved with no updating the next field.
>>
>> thanks
>>            Hillf
>
>
>

Re: [PATCH] sched: remove the next highest_prio in RT scheduling

[Steven Rostedt]

On Sat, 2011-06-04 at 13:11 +0800, Hillf Danton wrote:
> On Sat, Jun 4, 2011 at 1:06 PM, Steven Rostedt <rostedt@goodmis.org> wrote:
> >
> Hi Steve
> 
> Big surprise, you work on Saturday!

Technically Saturday, but I was working late Friday night.

> 
> good weekend

You too.

-- Steve

[tip:sched/core] sched: Use pushable_tasks to determine next highest prio

[tip-bot for Steven Rostedt]

Commit-ID:  5181f4a46afd99e5e85c639b189e43e0a42b53df
Gitweb:     http://git.kernel.org/tip/5181f4a46afd99e5e85c639b189e43e0a42b53df
Author:     Steven Rostedt <srostedt@redhat.com>
AuthorDate: Thu, 16 Jun 2011 21:55:23 -0400
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Sun, 14 Aug 2011 12:00:55 +0200

sched: Use pushable_tasks to determine next highest prio

Hillf Danton proposed a patch (see link) that cleaned up the
sched_rt code that calculates the priority of the next highest priority
task to be used in finding run queues to pull from.

His patch removed the calculating of the next prio to just use the current
prio when deteriming if we should examine a run queue to pull from. The problem
with his patch was that it caused more false checks. Because we check a run
queue for pushable tasks if the current priority of that run queue is higher
in priority than the task about to run on our run queue. But after grabbing
the locks and doing the real check, we find that there may not be a task
that has a higher prio task to pull. Thus the locks were taken with nothing to
do.

I added some trace_printks() to record when and how many times the run queue
locks were taken to check for pullable tasks, compared to how many times we
pulled a task.

With the current method, it was:

  3806 locks taken vs 2812 pulled tasks

With Hillf's patch:

  6728 locks taken vs 2804 pulled tasks

The number of times locks were taken to pull a task went up almost double with
no more success rate.

But his patch did get me thinking. When we look at the priority of the highest
task to consider taking the locks to do a pull, a failure to pull can be one
of the following: (in order of most likely)

 o RT task was pushed off already between the check and taking the lock
 o Waiting RT task can not be migrated
 o RT task's CPU affinity does not include the target run queue's CPU
 o RT task's priority changed between the check and taking the lock

And with Hillf's patch, the thing that caused most of the failures, is
the RT task to pull was not at the right priority to pull (not greater than
the current RT task priority on the target run queue).

Most of the above cases we can't help. But the current method does not check
if the next highest prio RT task can be migrated or not, and if it can not,
we still grab the locks to do the test (we don't find out about this fact until
after we have the locks). I thought about this case, and realized that the
pushable task plist that is maintained only holds RT tasks that can migrate.
If we move the calculating of the next highest prio task from the inc/dec_rt_task()
functions into the queuing of the pushable tasks, then we only measure the
priorities of those tasks that we push, and we get this basically for free.

Not only does this patch make the code a little more efficient, it cleans it
up and makes it a little simpler.

Thanks to Hillf Danton for inspiring me on this patch.

Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Hillf Danton <dhillf@gmail.com>
Cc: Gregory Haskins <ghaskins@novell.com>
Link: http://lkml.kernel.org/r/BANLkTimQ67180HxCx5vgMqumqw1EkFh3qg@mail.gmail.com
Signed-off-by: Ingo Molnar <mingo@elte.hu>
---
 kernel/sched_rt.c |   61 +++++++++++++++-------------------------------------
 1 files changed, 18 insertions(+), 43 deletions(-)

diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c
index 2153a87..a8c207f 100644
--- a/kernel/sched_rt.c
+++ b/kernel/sched_rt.c
@@ -124,21 +124,33 @@ static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
 	update_rt_migration(rt_rq);
 }
 
+static inline int has_pushable_tasks(struct rq *rq)
+{
+	return !plist_head_empty(&rq->rt.pushable_tasks);
+}
+
 static void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
 {
 	plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
 	plist_node_init(&p->pushable_tasks, p->prio);
 	plist_add(&p->pushable_tasks, &rq->rt.pushable_tasks);
+
+	/* Update the highest prio pushable task */
+	if (p->prio < rq->rt.highest_prio.next)
+		rq->rt.highest_prio.next = p->prio;
 }
 
 static void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
 {
 	plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
-}
 
-static inline int has_pushable_tasks(struct rq *rq)
-{
-	return !plist_head_empty(&rq->rt.pushable_tasks);
+	/* Update the new highest prio pushable task */
+	if (has_pushable_tasks(rq)) {
+		p = plist_first_entry(&rq->rt.pushable_tasks,
+				      struct task_struct, pushable_tasks);
+		rq->rt.highest_prio.next = p->prio;
+	} else
+		rq->rt.highest_prio.next = MAX_RT_PRIO;
 }
 
 #else
@@ -698,47 +710,13 @@ static void update_curr_rt(struct rq *rq)
 
 #if defined CONFIG_SMP
 
-static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu);
-
-static inline int next_prio(struct rq *rq)
-{
-	struct task_struct *next = pick_next_highest_task_rt(rq, rq->cpu);
-
-	if (next)
-		return next->prio;
-	else
-		return MAX_RT_PRIO;
-}
-
 static void
 inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
 {
 	struct rq *rq = rq_of_rt_rq(rt_rq);
 
-	if (prio < prev_prio) {
-
-		/*
-		 * If the new task is higher in priority than anything on the
-		 * run-queue, we know that the previous high becomes our
-		 * next-highest.
-		 */
-		rt_rq->highest_prio.next = prev_prio;
-
-		if (rq->online)
-			cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
-
-	} else if (prio == rt_rq->highest_prio.curr)
-		/*
-		 * If the next task is equal in priority to the highest on
-		 * the run-queue, then we implicitly know that the next highest
-		 * task cannot be any lower than current
-		 */
-		rt_rq->highest_prio.next = prio;
-	else if (prio < rt_rq->highest_prio.next)
-		/*
-		 * Otherwise, we need to recompute next-highest
-		 */
-		rt_rq->highest_prio.next = next_prio(rq);
+	if (rq->online && prio < prev_prio)
+		cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
 }
 
 static void
@@ -746,9 +724,6 @@ dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
 {
 	struct rq *rq = rq_of_rt_rq(rt_rq);
 
-	if (rt_rq->rt_nr_running && (prio <= rt_rq->highest_prio.next))
-		rt_rq->highest_prio.next = next_prio(rq);
-
 	if (rq->online && rt_rq->highest_prio.curr != prev_prio)
 		cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr);
 }