Skip to contentSkip to conversation

sched: Fix __load_balance_iterator() for cfq with only one task

PATCH In review Gautham R Shenoy 4 participants 9 messages Sep 5, 2008 – Sep 12, 2008

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched: Fix __load_balance_iterator() for cfq with only one task

sched: Fix __load_balance_iterator() for cfq with only one task.

From: Gautham R Shenoy <[email protected]>

The __load_balance_iterator() returns a NULL when there's only one sched_entity which is a task. It is caused by the following code-path.

	/* Skip over entities that are not tasks */
	do {
		se = list_entry(next, struct sched_entity, group_node);
		next = next->next;
	} while (next != &cfs_rq->tasks && !entity_is_task(se));

	if (next == &cfs_rq->tasks)
		return NULL;
	^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      This will return NULL even when se is a task.

As a side-effect, there was a regression in sched_mc behavior since 2.6.25, since iter_move_one_task() when it calls load_balance_start_fair(), would not get any tasks to move!

Fix this by checking if the last entity was a task or not.

Cc Peter Zijlstra <[email protected]>
Cc Vaidyanathan Srinivasan <[email protected]>
Cc Ingo Molnar <[email protected]>

---

 kernel/sched_fair.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
kernel/sched_fair.c +1 -1
index fb8994c..f1c96e3 100644
@@ -1451,7 +1451,7 @@ __load_balance_iterator(struct cfs_rq *cfs_rq, struct list_head *next)
 		next = next->next;
 	} while (next != &cfs_rq->tasks && !entity_is_task(se));
 
-	if (next == &cfs_rq->tasks)
+	if (next == &cfs_rq->tasks && !entity_is_task(se))
 		return NULL;
 
 	cfs_rq->balance_iterator = next;
Signature · 2 lines
Thanks and Regards
gautham
#1 lore raw
Quoted 19 lines · Gautham R Shenoy

sched: Fix __load_balance_iterator() for cfq with only one task.

From: Gautham R Shenoy <[email protected]>

The __load_balance_iterator() returns a NULL when there's only one sched_entity which is a task. It is caused by the following code-path.

	/* Skip over entities that are not tasks */
	do {
		se = list_entry(next, struct sched_entity, group_node);
		next = next->next;
	} while (next != &cfs_rq->tasks && !entity_is_task(se));

	if (next == &cfs_rq->tasks)
		return NULL;
	^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      This will return NULL even when se is a task.
Quoted 5 lines

As a side-effect, there was a regression in sched_mc behavior since 2.6.25, since iter_move_one_task() when it calls load_balance_start_fair(), would not get any tasks to move!

Fix this by checking if the last entity was a task or not.

Gregory did a similar fix a while ago, but that caused grief of some kind..

Greg, can you recollect why we pulled it? I can't seem to find it.

Aside from that this patch looks fine..

Quoted 23 lines
Cc Peter Zijlstra <[email protected]>
Cc Vaidyanathan Srinivasan <[email protected]>
Cc Ingo Molnar <[email protected]>

---

 kernel/sched_fair.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
kernel/sched_fair.c +1 -1
index fb8994c..f1c96e3 100644
@@ -1451,7 +1451,7 @@ __load_balance_iterator(struct cfs_rq *cfs_rq, struct list_head *next)
 		next = next->next;
 	} while (next != &cfs_rq->tasks && !entity_is_task(se));
 
-	if (next == &cfs_rq->tasks)
+	if (next == &cfs_rq->tasks && !entity_is_task(se))
 		return NULL;
 
 	cfs_rq->balance_iterator = next;
#2 lore raw
Quoted 24 lines · Peter Zijlstra
Quoted 23 lines · Gautham R Shenoy

sched: Fix __load_balance_iterator() for cfq with only one task.

From: Gautham R Shenoy <[email protected]>

The __load_balance_iterator() returns a NULL when there's only one sched_entity which is a task. It is caused by the following code-path.

	/* Skip over entities that are not tasks */
	do {
		se = list_entry(next, struct sched_entity, group_node);
		next = next->next;
	} while (next != &cfs_rq->tasks && !entity_is_task(se));

	if (next == &cfs_rq->tasks)
		return NULL;
	^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      This will return NULL even when se is a task.

As a side-effect, there was a regression in sched_mc behavior since 2.6.25, since iter_move_one_task() when it calls load_balance_start_fair(), would not get any tasks to move!

Quoted 6 lines
Quoted 1 line

Fix this by checking if the last entity was a task or not.

Gregory did a similar fix a while ago, but that caused grief of some kind..

Greg, can you recollect why we pulled it? I can't seem to find it.

Gregory pointed me to this thread:

http://lkml.org/lkml/2008/8/11/81

ego, can you run sysbench to confirm?

Quoted 31 lines

Aside from that this patch looks fine..

Quoted 15 lines
Cc Peter Zijlstra <[email protected]>
Cc Vaidyanathan Srinivasan <[email protected]>
Cc Ingo Molnar <[email protected]>

---

 kernel/sched_fair.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
kernel/sched_fair.c +0 -0
index fb8994c..f1c96e3 100644

kernel/sched_fair.c __load_balance_iterator(struct cfs_rq *cfs_rq, struct list_head *next) · line 1457

Quoted 8 lines
kernel/sched_fair.c +1 -1
@@ -1451,7 +1451,7 @@ __load_balance_iterator(struct cfs_rq *cfs_rq, struct list_head *next)
 		next = next->next;
 	} while (next != &cfs_rq->tasks && !entity_is_task(se));
 
-	if (next == &cfs_rq->tasks)
+	if (next == &cfs_rq->tasks && !entity_is_task(se))
 		return NULL;
 
 	cfs_rq->balance_iterator = next;

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

#3 lore raw
Quoted 30 lines · Peter Zijlstra
Quoted 29 lines · Peter Zijlstra
Quoted 19 lines · Gautham R Shenoy

sched: Fix __load_balance_iterator() for cfq with only one task.

From: Gautham R Shenoy <[email protected]>

The __load_balance_iterator() returns a NULL when there's only one sched_entity which is a task. It is caused by the following code-path.

	/* Skip over entities that are not tasks */
	do {
		se = list_entry(next, struct sched_entity, group_node);
		next = next->next;
	} while (next != &cfs_rq->tasks && !entity_is_task(se));

	if (next == &cfs_rq->tasks)
		return NULL;
	^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      This will return NULL even when se is a task.
Quoted 5 lines

As a side-effect, there was a regression in sched_mc behavior since 2.6.25, since iter_move_one_task() when it calls load_balance_start_fair(), would not get any tasks to move!

Fix this by checking if the last entity was a task or not.

Gregory did a similar fix a while ago, but that caused grief of some kind..

Quoted 7 lines
Quoted 1 line

Greg, can you recollect why we pulled it? I can't seem to find it.

Gregory pointed me to this thread:

http://lkml.org/lkml/2008/8/11/81

ego, can you run sysbench to confirm?

Am planning to run it today.

Mike, with what --oltp-* mode did you run the sysbench test?

That aside, if Mike's analysis is correct regarding the client/server pairs not running on the same CPU as buddies, shouldn't this be fixed in a higher level routine rather than have this anomaly in __load_balancer_iterator(), which is supposed to return the runnable tasks in the cfs_rq ?

It's current behavior is that __load_balancer_iterator() will return NULL even if the last entity in the list is a runnable task.

This behavior clearly hinders sched_mc powersavings from migrating a sole remaining task from a powersavings-sched_domain in-order to evacuate that domain and put all the CPUs of the domain into a low-power state.

Quoted 33 lines
Quoted 32 lines

Aside from that this patch looks fine..

Quoted 15 lines
Cc Peter Zijlstra <[email protected]>
Cc Vaidyanathan Srinivasan <[email protected]>
Cc Ingo Molnar <[email protected]>

---

 kernel/sched_fair.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
kernel/sched_fair.c +0 -0
index fb8994c..f1c96e3 100644

kernel/sched_fair.c __load_balance_iterator(struct cfs_rq *cfs_rq, struct list_head *next) · line 1457

Quoted 8 lines
kernel/sched_fair.c +1 -1
@@ -1451,7 +1451,7 @@ __load_balance_iterator(struct cfs_rq *cfs_rq, struct list_head *next)
 		next = next->next;
 	} while (next != &cfs_rq->tasks && !entity_is_task(se));
 
-	if (next == &cfs_rq->tasks)
+	if (next == &cfs_rq->tasks && !entity_is_task(se))
 		return NULL;
 
 	cfs_rq->balance_iterator = next;

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

Signature · 2 lines
Thanks and Regards
gautham
#4 lore raw
Quoted 49 lines · Gautham R Shenoy
Quoted 30 lines · Peter Zijlstra
Quoted 29 lines · Peter Zijlstra
Quoted 19 lines · Gautham R Shenoy

sched: Fix __load_balance_iterator() for cfq with only one task.

From: Gautham R Shenoy <[email protected]>

The __load_balance_iterator() returns a NULL when there's only one sched_entity which is a task. It is caused by the following code-path.

	/* Skip over entities that are not tasks */
	do {
		se = list_entry(next, struct sched_entity, group_node);
		next = next->next;
	} while (next != &cfs_rq->tasks && !entity_is_task(se));

	if (next == &cfs_rq->tasks)
		return NULL;
	^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      This will return NULL even when se is a task.
Quoted 5 lines

As a side-effect, there was a regression in sched_mc behavior since 2.6.25, since iter_move_one_task() when it calls load_balance_start_fair(), would not get any tasks to move!

Fix this by checking if the last entity was a task or not.

Gregory did a similar fix a while ago, but that caused grief of some kind..

Quoted 7 lines
Quoted 1 line

Greg, can you recollect why we pulled it? I can't seem to find it.

Gregory pointed me to this thread:

http://lkml.org/lkml/2008/8/11/81

ego, can you run sysbench to confirm?

Am planning to run it today.

Mike, with what --oltp-* mode did you run the sysbench test?

That aside, if Mike's analysis is correct regarding the client/server pairs not running on the same CPU as buddies, shouldn't this be fixed in a higher level routine rather than have this anomaly in __load_balancer_iterator(), which is supposed to return the runnable tasks in the cfs_rq ?

Quoted 7 lines

It's current behavior is that __load_balancer_iterator() will return NULL even if the last entity in the list is a runnable task.

This behavior clearly hinders sched_mc powersavings from migrating a sole remaining task from a powersavings-sched_domain in-order to evacuate that domain and put all the CPUs of the domain into a low-power state.

Sure - there is buddy_hot in task_hot() to avoid moving buddies, and I think we should do something like this:

@@ -590,7 +602,7 @@ account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)

                add_cfs_task_weight(cfs_rq, se->load.weight);
        cfs_rq->nr_running++;
        se->on_rq = 1;

- list_add(&se->group_node, &cfs_rq->tasks);
+ list_add_tail(&se->group_node, &cfs_rq->tasks);
}

static void

(most likely whitespace damaged)

#6 lore raw
In reply to Gautham R Shenoy
Quoted 5 lines · Gautham R Shenoy
Quoted 1 line · Peter Zijlstra

ego, can you run sysbench to confirm?

Am planning to run it today.

I just tested rc6 with 6d299f1b53b84e2665f402d9bcc494800aba6386 applied, and it does not exhibit the problem which triggered the revert, so I'd suggest reverting it. (Perhaps more clock manifestations)

-Mike

#7 lore raw
Quoted 10 lines · Mike Galbraith
Quoted 5 lines · Gautham R Shenoy
Quoted 1 line · Peter Zijlstra

ego, can you run sysbench to confirm?

Am planning to run it today.

I just tested rc6 with 6d299f1b53b84e2665f402d9bcc494800aba6386 applied, and it does not exhibit the problem which triggered the revert, so I'd suggest reverting it. (Perhaps more clock manifestations)

That's good news!

Thanks for doing this

Quoted 3 lines

-Mike

Signature · 2 lines
Thanks and Regards
gautham
#8 lore raw
In reply to Gautham R Shenoy
Quoted 8 lines · Gautham R Shenoy

sched: Fix __load_balance_iterator() for cfq with only one task.

From: Gautham R Shenoy <[email protected]>

The __load_balance_iterator() returns a NULL when there's only one sched_entity which is a task. It is caused by the following code-path.

Quoted 10 lines
	/* Skip over entities that are not tasks */
	do {
		se = list_entry(next, struct sched_entity, group_node);
		next = next->next;
	} while (next != &cfs_rq->tasks && !entity_is_task(se));

	if (next == &cfs_rq->tasks)
		return NULL;
	^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      This will return NULL even when se is a task.

Thank you! I'd been looking suspiciously at this routine as well due to strange load-balancing behaviour that I saw while testing the fair group code, but I hadn't yet tracked down the exact problem.

Peter/Ingo, this appears to explain the issues described in the mail I sent on the 4th. After applying this change the imbalance between tasks in the same group is substantially reduced.

Chris