Optimization of function pull_rt_task()

The condition (src_rq->rt.rt_nr_running) is weak because it doesn't consider the cases when src_rq has only processes bound to it (when single cpu is allowed). It may be running kernel thread like migration/x etc.

So it's better to use more stronger condition which is able to exclude above conditions. The function has_pushable_tasks() complitely does this. A task may be pullable for another cpu rq only if he is pushable for his own queue.

Signed-off-by Kirill Tkhai <[email protected]>

---
 kernel/sched/rt.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

kernel/sched/rt.c +1 -1

index c5565c3..61e3086 100644
@@ -1729,7 +1729,7 @@ static int pull_rt_task(struct rq *this_rq)
 		/*
 		 * Are there still pullable RT tasks?
 		 */
-		if (src_rq->rt.rt_nr_running <= 1)
+		if (!has_pushable_tasks(src_rq))
 			goto skip;
 
 		p = pick_next_highest_task_rt(src_rq, this_cpu);

Quoted 9 lines · Kirill Tkhai

The condition (src_rq->rt.rt_nr_running) is weak because it doesn't consider the cases when src_rq has only processes bound to it (when single cpu is allowed). It may be running kernel thread like migration/x etc.

So it's better to use more stronger condition which is able to exclude above conditions. The function has_pushable_tasks() complitely does this. A task may be pullable for another cpu rq only if he is pushable for his own queue.

I considered this before, and for some reason I never did the change. I'll have to think about it. It seems like this would be the obvious case, but I think there was something not so obvious that caused issues. But I don't remember what it was.

I'll have to rethink this again.

Quoted 16 lines · Steven Rostedt

Quoted 9 lines · Kirill Tkhai

The condition (src_rq->rt.rt_nr_running) is weak because it doesn't consider the cases when src_rq has only processes bound to it (when single cpu is allowed). It may be running kernel thread like migration/x etc.

So it's better to use more stronger condition which is able to exclude above conditions. The function has_pushable_tasks() complitely does this. A task may be pullable for another cpu rq only if he is pushable for his own queue.

I considered this before, and for some reason I never did the change. I'll have to think about it. It seems like this would be the obvious case, but I think there was something not so obvious that caused issues. But I don't remember what it was.

Quoted 1 line

I'll have to rethink this again.

I can't find anything wrong with this change. Maybe things change, or I was thinking of another change.

I'll apply it and start running my tests against it.

Quoted 17 lines · Steven Rostedt

Quoted 16 lines · Steven Rostedt

Quoted 9 lines · Kirill Tkhai

The condition (src_rq->rt.rt_nr_running) is weak because it doesn't consider the cases when src_rq has only processes bound to it (when single cpu is allowed). It may be running kernel thread like migration/x etc.

So it's better to use more stronger condition which is able to exclude above conditions. The function has_pushable_tasks() complitely does this. A task may be pullable for another cpu rq only if he is pushable for his own queue.

I considered this before, and for some reason I never did the change. I'll have to think about it. It seems like this would be the obvious case, but I think there was something not so obvious that caused issues. But I don't remember what it was.

Quoted 6 lines

Quoted 1 line

I'll have to rethink this again.

I can't find anything wrong with this change. Maybe things change, or I was thinking of another change.

I'll apply it and start running my tests against it.

Not only does this seem to work fine, I took it one step further :-)

Peter, do you see anything wrong with this patch?

-- Steve

kernel/sched/rt.c +6 -31

index 61e3086..b44fd1b 100644
@@ -1416,39 +1416,15 @@ static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
 /* Return the second highest RT task, NULL otherwise */
 static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu)
 {
-	struct task_struct *next = NULL;
-	struct sched_rt_entity *rt_se;
-	struct rt_prio_array *array;
-	struct rt_rq *rt_rq;
-	int idx;
+	struct plist_head *head = &rq->rt.pushable_tasks;
+	struct task_struct *next;
 
-	for_each_leaf_rt_rq(rt_rq, rq) {
-		array = &rt_rq->active;
-		idx = sched_find_first_bit(array->bitmap);
-next_idx:
-		if (idx >= MAX_RT_PRIO)
-			continue;
-		if (next && next->prio <= idx)
-			continue;
-		list_for_each_entry(rt_se, array->queue + idx, run_list) {
-			struct task_struct *p;
-
-			if (!rt_entity_is_task(rt_se))
-				continue;
-
-			p = rt_task_of(rt_se);
-			if (pick_rt_task(rq, p, cpu)) {
-				next = p;
-				break;
-			}
-		}
-		if (!next) {
-			idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
-			goto next_idx;
-		}
+	plist_for_each_entry(next, head, pushable_tasks) {
+		if (pick_rt_task(rq, next, cpu))
+			return next;
 	}
 
-	return next;
+	return NULL;
 }
 
 static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);
 
 
--

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/

Quoted 22 lines · Steven Rostedt

Quoted 20 lines · Steven Rostedt

Quoted 10 lines · Kirill Tkhai

Quoted 9 lines

 The condition (src_rq->rt.rt_nr_running) is weak because it doesn't consider the cases when src_rq has only processes bound to it (when single cpu is allowed). It may be running kernel thread like migration/x etc.

 So it's better to use more stronger condition which is able to exclude above conditions. The function has_pushable_tasks() complitely does this. A task may be pullable for another cpu rq only if he is pushable for his own queue.

Quoted 6 lines

 I considered this before, and for some reason I never did the change. I'll have to think about it. It seems like this would be the obvious case, but I think there was something not so obvious that caused issues. But I don't remember what it was.

 I'll have to rethink this again.

 I can't find anything wrong with this change. Maybe things change, or I was thinking of another change.

Quoted 2 lines

Quoted 1 line

 I'll apply it and start running my tests against it.

 Not only does this seem to work fine, I took it one step further :-)

Hmm... throttle doesn't handle the pushable list, so we may find a throttled task by pick_next_pushable_task().

Thanks,
Yong

Quoted 54 lines

 Peter, do you see anything wrong with this patch?

 -- Steve

 diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
 index 61e3086..b44fd1b 100644
 --- a/kernel/sched/rt.c
 +++ b/kernel/sched/rt.c
 @@ -1416,39 +1416,15 @@ static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu) /* Return the second highest RT task, NULL otherwise */
  static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu)
  {
 - struct task_struct *next = NULL;
 - struct sched_rt_entity *rt_se;
 - struct rt_prio_array *array;
 - struct rt_rq *rt_rq;
 - int idx;
 + struct plist_head *head = &rq->rt.pushable_tasks;
 + struct task_struct *next;

 - for_each_leaf_rt_rq(rt_rq, rq) {
 - array = &rt_rq->active;
 - idx = sched_find_first_bit(array->bitmap); -next_idx:
 - if (idx >= MAX_RT_PRIO)
 - continue;
 - if (next && next->prio <= idx)
 - continue;
 - list_for_each_entry(rt_se, array->queue + idx, run_list) {
 - struct task_struct *p;
 -
 - if (!rt_entity_is_task(rt_se))
 - continue;
 -
 - p = rt_task_of(rt_se);
 - if (pick_rt_task(rq, p, cpu)) {
 - next = p;
 - break;
 - }
 - }
 - if (!next) {
 - idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
 - goto next_idx;
 - }
 + plist_for_each_entry(next, head, pushable_tasks) {
 + if (pick_rt_task(rq, next, cpu))
 + return next;
          }

 - return next;
 + return NULL;
  }

Quoted 7 lines

  static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);

 --
 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/

--
Only stand for myself

19.04.2012, 12:54, "Yong Zhang" <[email protected]>:

Quoted 29 lines · Steven Rostedt

Quoted 18 lines

Quoted 16 lines · Steven Rostedt

Quoted 15 lines · Steven Rostedt

Quoted 9 lines · Kirill Tkhai

?The condition (src_rq->rt.rt_nr_running) is weak because it doesn't ?consider the cases when src_rq has only processes bound to it (when ?single cpu is allowed). It may be running kernel thread like ?migration/x etc.

?So it's better to use more stronger condition which is able to exclude ?above conditions. The function has_pushable_tasks() complitely does ?this. A task may be pullable for another cpu rq only if he is pushable ?for his own queue.

?I considered this before, and for some reason I never did the change. ?I'll have to think about it. It seems like this would be the obvious ?case, but I think there was something not so obvious that caused issues. ?But I don't remember what it was.

Quoted 6 lines

Quoted 5 lines

Quoted 1 line

?I'll have to rethink this again.

?I can't find anything wrong with this change. Maybe things change, or I ?was thinking of another change.

?I'll apply it and start running my tests against it.

?Not only does this seem to work fine, I took it one step further :-)

Hmm... throttle doesn't handle the pushable list, so we may find a throttled task by pick_next_pushable_task().

Quoted 2 lines

Thanks,
Yong

I don't complitelly understand throttle logic.

Is the source patch not-appliable the same reason?

Kirill

Quoted 56 lines

Quoted 56 lines

?Peter, do you see anything wrong with this patch?

?-- Steve

?diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
?index 61e3086..b44fd1b 100644
?--- a/kernel/sched/rt.c
?+++ b/kernel/sched/rt.c
?@@ -1416,39 +1416,15 @@ static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu) ??/* Return the second highest RT task, NULL otherwise */
??static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu) ??{
?- struct task_struct *next = NULL;
?- struct sched_rt_entity *rt_se;
?- struct rt_prio_array *array;
?- struct rt_rq *rt_rq;
?- int idx;
?+ struct plist_head *head = &rq->rt.pushable_tasks;
?+ struct task_struct *next;

?- for_each_leaf_rt_rq(rt_rq, rq) {
?- array = &rt_rq->active;
?- idx = sched_find_first_bit(array->bitmap); ?-next_idx:
?- if (idx >= MAX_RT_PRIO)
?- continue;
?- if (next && next->prio <= idx)
?- continue;
?- list_for_each_entry(rt_se, array->queue + idx, run_list) { ?- struct task_struct *p;
?-
?- if (!rt_entity_is_task(rt_se))
?- continue;
?-
?- p = rt_task_of(rt_se);
?- if (pick_rt_task(rq, p, cpu)) {
?- next = p;
?- break;
?- }
?- }
?- if (!next) {
?- idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1); ?- goto next_idx;
?- }
?+ plist_for_each_entry(next, head, pushable_tasks) { ?+ if (pick_rt_task(rq, next, cpu))
?+ return next;
??????????}

?- return next;
?+ return NULL;
??}

??static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);

Quoted 7 lines

Quoted 5 lines

?--
?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/

--
Only stand for myself

--
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/

Quoted 35 lines · Kirill Tkhai

19.04.2012, 12:54, "Yong Zhang" <[email protected]>:

Quoted 31 lines · Steven Rostedt

Quoted 18 lines

Quoted 16 lines · Steven Rostedt

Quoted 15 lines · Steven Rostedt

Quoted 9 lines · Kirill Tkhai

?The condition (src_rq->rt.rt_nr_running) is weak because it doesn't ?consider the cases when src_rq has only processes bound to it (when ?single cpu is allowed). It may be running kernel thread like ?migration/x etc.

?So it's better to use more stronger condition which is able to exclude ?above conditions. The function has_pushable_tasks() complitely does ?this. A task may be pullable for another cpu rq only if he is pushable ?for his own queue.

?I considered this before, and for some reason I never did the change. ?I'll have to think about it. It seems like this would be the obvious ?case, but I think there was something not so obvious that caused issues. ?But I don't remember what it was.

Quoted 6 lines

Quoted 5 lines

Quoted 1 line

?I'll have to rethink this again.

?I can't find anything wrong with this change. Maybe things change, or I ?was thinking of another change.

?I'll apply it and start running my tests against it.

?Not only does this seem to work fine, I took it one step further :-)

Hmm... throttle doesn't handle the pushable list, so we may find a throttled task by pick_next_pushable_task().

Thanks,
Yong

Quoted 3 lines

I don't complitelly understand throttle logic.

Is the source patch not-appliable the same reason?

I guess so.

Your patch will change the semantic of pick_next_pushable_task().

Thanks,
Yong

Quoted 71 lines

Kirill

Quoted 56 lines

Quoted 56 lines

?Peter, do you see anything wrong with this patch?

?-- Steve

?diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
?index 61e3086..b44fd1b 100644
?--- a/kernel/sched/rt.c
?+++ b/kernel/sched/rt.c
?@@ -1416,39 +1416,15 @@ static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu) ??/* Return the second highest RT task, NULL otherwise */
??static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu) ??{
?- struct task_struct *next = NULL;
?- struct sched_rt_entity *rt_se;
?- struct rt_prio_array *array;
?- struct rt_rq *rt_rq;
?- int idx;
?+ struct plist_head *head = &rq->rt.pushable_tasks;
?+ struct task_struct *next;

?- for_each_leaf_rt_rq(rt_rq, rq) {
?- array = &rt_rq->active;
?- idx = sched_find_first_bit(array->bitmap); ?-next_idx:
?- if (idx >= MAX_RT_PRIO)
?- continue;
?- if (next && next->prio <= idx)
?- continue;
?- list_for_each_entry(rt_se, array->queue + idx, run_list) { ?- struct task_struct *p;
?-
?- if (!rt_entity_is_task(rt_se))
?- continue;
?-
?- p = rt_task_of(rt_se);
?- if (pick_rt_task(rq, p, cpu)) {
?- next = p;
?- break;
?- }
?- }
?- if (!next) {
?- idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1); ?- goto next_idx;
?- }
?+ plist_for_each_entry(next, head, pushable_tasks) { ?+ if (pick_rt_task(rq, next, cpu))
?+ return next;
??????????}

?- return next;
?+ return NULL;
??}

??static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);

Quoted 7 lines

Quoted 5 lines

?--
?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/

--
Only stand for myself

--
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/

Doing my INBOX maintenance (clean up), I've stumbled on this thread again. I'm not sure the changes here are hopeless.

Quoted 29 lines · Yong Zhang

Quoted 28 lines · Kirill Tkhai

 19.04.2012, 12:54, "Yong Zhang" <[email protected]>:

Quoted 27 lines · Steven Rostedt

Quoted 17 lines

Quoted 16 lines · Steven Rostedt

Quoted 15 lines · Steven Rostedt

Quoted 9 lines · Kirill Tkhai

 ?The condition (src_rq->rt.rt_nr_running) is weak because it doesn't ?consider the cases when src_rq has only processes bound to it (when ?single cpu is allowed). It may be running kernel thread like ?migration/x etc.

 ?So it's better to use more stronger condition which is able to exclude ?above conditions. The function has_pushable_tasks() complitely does ?this. A task may be pullable for another cpu rq only if he is pushable ?for his own queue.

 ?I considered this before, and for some reason I never did the change. ?I'll have to think about it. It seems like this would be the obvious ?case, but I think there was something not so obvious that caused issues. ?But I don't remember what it was.

Quoted 6 lines

Quoted 5 lines

Quoted 1 line

 ?I'll have to rethink this again.

 ?I can't find anything wrong with this change. Maybe things change, or I ?was thinking of another change.

 ?I'll apply it and start running my tests against it.

 ?Not only does this seem to work fine, I took it one step further :-)

 Hmm... throttle doesn't handle the pushable list, so we may find a throttled task by pick_next_pushable_task().

Quoted 8 lines

Quoted 5 lines

Quoted 2 lines

 Thanks,
 Yong

 I don't complitelly understand throttle logic.

 Is the source patch not-appliable the same reason?

 I guess so.

 Your patch will change the semantic of pick_next_pushable_task().

Looking at the original patch, I don't see how it changes the semantics (although mine may have). The original patch was:

kernel/sched/rt.c +1 -1

@@ -1729,7 +1729,7 @@ static int pull_rt_task(struct rq *this_rq)
                 /*
                  * Are there still pullable RT tasks?
                  */
-               if (src_rq->rt.rt_nr_running <= 1)
+               if (!has_pushable_tasks(src_rq))
                         goto skip;
 
                 p = pick_next_highest_task_rt(src_rq, this_cpu);

And I still don't see a problem with this. If a rq has no pushable tasks, then we shouldn't bother trying to pull from it (no task can migrate).

Thus, the original patch, I believe should be applied without question.

Now, about my patch, the one that made pick_next_highest_task_rt into just:

static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu) {
       struct plist_head *head = &rq->rt.pushable_tasks;
       struct task_struct *next;

       plist_for_each_entry(next, head, pushable_tasks) { if (pick_rt_task(rq, next, cpu)) return next;
       }

       return NULL;
}

You said could pick a task from a throttled rq. I'm not sure that is different than what we have now. As the current pick_next_highest_task_rt() just does a loop over the leaf_rt_rqs which includes throttled rqs. That's because a throttled rq will not dequeue the rt_rq from the leaf_rt_rq list if the rt_rq has rt_nr_running != 0.

I'm still thinking about adding both patches.

-- Steve

Quoted 70 lines

 Thanks,
 Yong

Quoted 68 lines

 Kirill

Quoted 55 lines

Quoted 55 lines

 ?Peter, do you see anything wrong with this patch?

 ?-- Steve

 ?diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
 ?index 61e3086..b44fd1b 100644
 ?--- a/kernel/sched/rt.c
 ?+++ b/kernel/sched/rt.c
 ?@@ -1416,39 +1416,15 @@ static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu) ??/* Return the second highest RT task, NULL otherwise */
 ??static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu) ??{
 ?- struct task_struct *next = NULL;
 ?- struct sched_rt_entity *rt_se;
 ?- struct rt_prio_array *array;
 ?- struct rt_rq *rt_rq;
 ?- int idx;
 ?+ struct plist_head *head = &rq->rt.pushable_tasks;
 ?+ struct task_struct *next;

 ?- for_each_leaf_rt_rq(rt_rq, rq) {
 ?- array = &rt_rq->active;
 ?- idx = sched_find_first_bit(array->bitmap); ?-next_idx:
 ?- if (idx >= MAX_RT_PRIO)
 ?- continue;
 ?- if (next && next->prio <= idx)
 ?- continue;
 ?- list_for_each_entry(rt_se, array->queue + idx, run_list) { ?- struct task_struct *p;
 ?-
 ?- if (!rt_entity_is_task(rt_se))
 ?- continue;
 ?-
 ?- p = rt_task_of(rt_se);
 ?- if (pick_rt_task(rq, p, cpu)) {
 ?- next = p;
 ?- break;
 ?- }
 ?- }
 ?- if (!next) {
 ?- idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1); ?- goto next_idx;
 ?- }
 ?+ plist_for_each_entry(next, head, pushable_tasks) { ?+ if (pick_rt_task(rq, next, cpu))
 ?+ return next;
 ??????????}

 ?- return next;
 ?+ return NULL;
 ??}

 ??static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);

Quoted 7 lines

Quoted 5 lines

 ?--
 ?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/

 --
 Only stand for myself

 --
 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/