Skip to contentSkip to conversation

sched/fair: Make balance_fair() test sched_fair_runnable() instead of rq->nr_running

PATCH Superseded Tejun Heo 4 participants 7 messages Aug 3, 2024 – Aug 7, 2024 Scheduler

lore
Share & tools
lore

Tejun Heo

author
#0 lore raw

PATCH 1/1 sched/fair: Make balance_fair() test sched_fair_runnable() instead of rq->nr_running

balance_fair() skips newidle balancing if rq->nr_running - there are already tasks on the rq, so no need to try to pull tasks. However, this doesn't seem correct when bandwidth throttling is in use. When an entity gets throttled, rq->nr_running is not decremented, so a CPU could end up in a situation where rq->nr_running is not zero but there are no runnable tasks. Theoretically, skipping newidle balance in this condition can lead to increased latencies although I couldn't come up with a scenario where this could be demonstrated reliably.

Update balance_fair() to use sched_fair_runnable() which tests rq->cfs.nr_running which is updated by bandwidth throttling. Note that pick_next_task_fair() already uses sched_fair_runnable() in its optimized path for the same purpose.

This also makes put_prev_task_balance() avoid incorrectly skipping lower priority classes' (such as sched_ext) balance(). When a CPU has only lower priority class tasks, rq->nr_running would still be positive and balance_fair() would return 1 even when fair doesn't have any tasks to run. This makes put_prev_task_balance() skip lower priority classes' balance() incorrectly which may lead to stalls.

---
 kernel/sched/fair.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/fair.c +1 -1
@@ -8323,7 +8323,7 @@ static void set_cpus_allowed_fair(struct
 static int
 balance_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-	if (rq->nr_running)
+	if (sched_fair_runnable(rq))
 		return 1;
 
 	return sched_balance_newidle(rq, rf) != 0;
#1 lore raw

Hello Tejun,

Quoted 5 lines · Tejun Heo

balance_fair() skips newidle balancing if rq->nr_running - there are already tasks on the rq, so no need to try to pull tasks. However, this doesn't seem correct when bandwidth throttling is in use. When an entity gets throttled, rq->nr_running is not decremented, so a CPU could end up in a situation where rq->nr_running is not zero but there are no runnable tasks.

When does this happen exactly? throttle_cfs_rq() calls sub_nr_running() negating the "h_nr_running" of the throttled entity from the rq->nr_running. Even deadline entities on being throttled dequeue the entity (or don't enqueue them at all in enqueue_dl_entity()) and would have the correct "rq->nr_running". Could you please highlight the path that might hit this scenario?

Signature · 2 lines
Thanks and Regards,
Prateek
Quoted 34 lines

Theoretically, skipping newidle balance in this condition can lead to increased latencies although I couldn't come up with a scenario where this could be demonstrated reliably.

Update balance_fair() to use sched_fair_runnable() which tests rq->cfs.nr_running which is updated by bandwidth throttling. Note that pick_next_task_fair() already uses sched_fair_runnable() in its optimized path for the same purpose.

This also makes put_prev_task_balance() avoid incorrectly skipping lower priority classes' (such as sched_ext) balance(). When a CPU has only lower priority class tasks, rq->nr_running would still be positive and balance_fair() would return 1 even when fair doesn't have any tasks to run. This makes put_prev_task_balance() skip lower priority classes' balance() incorrectly which may lead to stalls.

---
  kernel/sched/fair.c |    2 +-
  1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/fair.c +1 -1
@@ -8323,7 +8323,7 @@ static void set_cpus_allowed_fair(struct
  static int
  balance_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
  {
-	if (rq->nr_running)
+	if (sched_fair_runnable(rq))
  		return 1;
 
  	return sched_balance_newidle(rq, rf) != 0;
author
#2 lore raw

Hello,

On Mon, Aug 05, 2024 at 08:51:05AM +0530, K Prateek Nayak wrote:
...

Quoted 6 lines

When does this happen exactly? throttle_cfs_rq() calls sub_nr_running() negating the "h_nr_running" of the throttled entity from the rq->nr_running. Even deadline entities on being throttled dequeue the entity (or don't enqueue them at all in enqueue_dl_entity()) and would have the correct "rq->nr_running". Could you please highlight the path that might hit this scenario?

I just missed the sub_nr_running() call. No wonder I couldn't see behavior difference. I'll redo the patch description.

Thanks.

Signature · 1 line
tejun
author
#3 lore raw

PATCH v2 1/1 sched/fair: Make balance_fair() test sched_fair_runnable() instead of rq->nr_running

In reply to Tejun Heo

balance_fair() skips newidle balancing if rq->nr_running - there are already tasks on the rq, so no need to try to pull tasks. This tests the total number of queued tasks on the CPU instead of only the fair class, but is still correct as the rq can currently only have fair class tasks while balance_fair() is running.

However, with the addition of sched_ext below the fair class, this will not hold anymore and make put_prev_task_balance() skip sched_ext's balance() incorrectly as, when a CPU has only lower priority class tasks, rq->nr_running would still be positive and balance_fair() would return 1 even when fair doesn't have any tasks to run.

Update balance_fair() to use sched_fair_runnable() which tests rq->cfs.nr_running which is updated by bandwidth throttling. Note that pick_next_task_fair() already uses sched_fair_runnable() in its optimized path for the same purpose.

v2: K Prateek Nayak pointed out that the bw control issue described in v1
was incorrect. Patch description updated. As this makes the patch only relevant for sched_ext, I'll carry this through the sched_ext tree unless there are objections.

---
 kernel/sched/fair.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/fair.c +1 -1
@@ -8323,7 +8323,7 @@ static void set_cpus_allowed_fair(struct
 static int
 balance_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-	if (rq->nr_running)
+	if (sched_fair_runnable(rq))
 		return 1;
 
 	return sched_balance_newidle(rq, rf) != 0;
Reviewed-by on v2 1/1
#4 lore raw
Quoted 17 lines · Tejun Heo

balance_fair() skips newidle balancing if rq->nr_running - there are already tasks on the rq, so no need to try to pull tasks. This tests the total number of queued tasks on the CPU instead of only the fair class, but is still correct as the rq can currently only have fair class tasks while balance_fair() is running.

However, with the addition of sched_ext below the fair class, this will not hold anymore and make put_prev_task_balance() skip sched_ext's balance() incorrectly as, when a CPU has only lower priority class tasks, rq->nr_running would still be positive and balance_fair() would return 1 even when fair doesn't have any tasks to run.

Update balance_fair() to use sched_fair_runnable() which tests rq->cfs.nr_running which is updated by bandwidth throttling. Note that pick_next_task_fair() already uses sched_fair_runnable() in its optimized path for the same purpose.

Quoted 8 lines

v2: K Prateek Nayak pointed out that the bw control issue described in v1
was incorrect. Patch description updated. As this makes the patch only relevant for sched_ext, I'll carry this through the sched_ext tree unless there are objections.

Looks good to me.

Thanks.

Quoted 15 lines
---
  kernel/sched/fair.c |    2 +-
  1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/fair.c +1 -1
@@ -8323,7 +8323,7 @@ static void set_cpus_allowed_fair(struct
  static int
  balance_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
  {
-	if (rq->nr_running)
+	if (sched_fair_runnable(rq))
  		return 1;
 
  	return sched_balance_newidle(rq, rf) != 0;
reviewer Reviewed-by on v2 1/1
#5 lore raw
In reply to Tejun Heo

Hello Tejun,

Thank you for updating the commit message.

Quoted 17 lines · Tejun Heo

balance_fair() skips newidle balancing if rq->nr_running - there are already tasks on the rq, so no need to try to pull tasks. This tests the total number of queued tasks on the CPU instead of only the fair class, but is still correct as the rq can currently only have fair class tasks while balance_fair() is running.

However, with the addition of sched_ext below the fair class, this will not hold anymore and make put_prev_task_balance() skip sched_ext's balance() incorrectly as, when a CPU has only lower priority class tasks, rq->nr_running would still be positive and balance_fair() would return 1 even when fair doesn't have any tasks to run.

Update balance_fair() to use sched_fair_runnable() which tests rq->cfs.nr_running which is updated by bandwidth throttling. Note that pick_next_task_fair() already uses sched_fair_runnable() in its optimized path for the same purpose.

Quoted 8 lines

v2: K Prateek Nayak pointed out that the bw control issue described in v1
was incorrect. Patch description updated. As this makes the patch only relevant for sched_ext, I'll carry this through the sched_ext tree unless there are objections.

Looks good to me!

Signature · 2 lines
Thanks and Regards,
Prateek
Quoted 15 lines
---
  kernel/sched/fair.c |    2 +-
  1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/fair.c +1 -1
@@ -8323,7 +8323,7 @@ static void set_cpus_allowed_fair(struct
  static int
  balance_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
  {
-	if (rq->nr_running)
+	if (sched_fair_runnable(rq))
  		return 1;
 
  	return sched_balance_newidle(rq, rf) != 0;
merge bot Applied
#6 lore raw
In reply to Tejun Heo
The following commit has been merged into the sched/core branch of tip:

The following commit has been merged into the sched/core branch of tip:

Commit-ID:     924e2904da9b5edec61611918b98ab1f7fccc461
Gitweb:        https://git.kernel.org/tip/924e2904da9b5edec61611918b98ab1f7fccc461
Author:        Tejun Heo <[email protected]>
AuthorDate:    Mon, 05 Aug 2024 12:39:10 -10:00
Committer:     Peter Zijlstra <[email protected]>
CommitterDate: Wed, 07 Aug 2024 12:44:16 +02:00

sched/fair: Make balance_fair() test sched_fair_runnable() instead of rq->nr_running

balance_fair() skips newidle balancing if rq->nr_running - there are already tasks on the rq, so no need to try to pull tasks. This tests the total number of queued tasks on the CPU instead of only the fair class, but is still correct as the rq can currently only have fair class tasks while balance_fair() is running.

However, with the addition of sched_ext below the fair class, this will not hold anymore and make put_prev_task_balance() skip sched_ext's balance() incorrectly as, when a CPU has only lower priority class tasks, rq->nr_running would still be positive and balance_fair() would return 1 even when fair doesn't have any tasks to run.

Update balance_fair() to use sched_fair_runnable() which tests rq->cfs.nr_running which is updated by bandwidth throttling. Note that pick_next_task_fair() already uses sched_fair_runnable() in its optimized path for the same purpose.

---
 kernel/sched/fair.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/fair.c +1 -1
index 795ceef..6d39a82 100644
@@ -8355,7 +8355,7 @@ static void set_cpus_allowed_fair(struct task_struct *p, struct affinity_context
 static int
 balance_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
-	if (rq->nr_running)
+	if (sched_fair_runnable(rq))
 		return 1;
 
 	return sched_balance_newidle(rq, rf) != 0;