Skip to contentSkip to conversation

sched/core: add unlikely in group_has_capacity()

PATCH In review Qi Zheng 3 participants 5 messages Jul 30, 2020 – Aug 17, 2020 Scheduler

lore
Share & tools
lore

Qi Zheng

author
#0 lore raw

PATCH 1/1 sched/core: add unlikely in group_has_capacity()

1. The group_has_capacity() function is only called in group_classify().
2. Before calling the group_has_capacity() function, group_is_overloaded() will first judge the following formula, if it holds, the group_classify() will directly return the group_overloaded.

	(sgs->group_capacity * imbalance_pct) <
                        (sgs->group_runnable * 100)

Therefore, when the group_has_capacity() is called, the probability that the above formalu holds is very small. Hint compilers about that.

---
 kernel/sched/fair.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
kernel/sched/fair.c +2 -2
index 2ba8f230feb9..9074fd5e23b2 100644
@@ -8234,8 +8234,8 @@ group_has_capacity(unsigned int imbalance_pct, struct sg_lb_stats *sgs)
 	if (sgs->sum_nr_running < sgs->group_weight)
 		return true;
 
-	if ((sgs->group_capacity * imbalance_pct) <
-			(sgs->group_runnable * 100))
+	if (unlikely((sgs->group_capacity * imbalance_pct) <
+			(sgs->group_runnable * 100)))
 		return false;
 
 	if ((sgs->group_capacity * 100) >
Signature · 1 line
2.25.1
#1 lore raw
Quoted 24 lines · Qi Zheng

1. The group_has_capacity() function is only called in group_classify().
2. Before calling the group_has_capacity() function, group_is_overloaded() will first judge the following formula, if it holds, the group_classify() will directly return the group_overloaded.

	(sgs->group_capacity * imbalance_pct) <
                        (sgs->group_runnable * 100)

Therefore, when the group_has_capacity() is called, the probability that the above formalu holds is very small. Hint compilers about that.

---
 kernel/sched/fair.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
kernel/sched/fair.c +0 -0
index 2ba8f230feb9..9074fd5e23b2 100644

kernel/sched/fair.c group_has_capacity(unsigned int imbalance_pct, struct sg_lb_stats *sgs) · line 8239

Quoted 8 lines
kernel/sched/fair.c +2 -2
@@ -8234,8 +8234,8 @@ group_has_capacity(unsigned int imbalance_pct, struct sg_lb_stats *sgs)
 	if (sgs->sum_nr_running < sgs->group_weight)
 		return true;
 
-	if ((sgs->group_capacity * imbalance_pct) <
-			(sgs->group_runnable * 100))
+	if (unlikely((sgs->group_capacity * imbalance_pct) <
+			(sgs->group_runnable * 100)))
 		return false;

Isn't the probability that this second check will match around 0%?

I.e. wouldn't the right fix be to remove the duplicate check from group_has_capacity(), because it's already been checked in group_classify()? Maybe while leaving a comment in place?

Thanks,

Ingo

author
#2 lore raw

Yeah, because of the following two points, I also think the probability is 0%:
a) the sd is protected by rcu lock, and load_balance() func is between rcu_read_lock() and rcu_read_unlock().
b) the sgs is a local variable.

So in the group_classify(), the env->sd->imbalance_pct and the sgs will not be changed. May I remove the duplicate check from group_has_capacity() and resubmit a patch?

Yours,
Qi Zheng

Quoted 46 lines · Ingo Molnar
Quoted 24 lines · Qi Zheng

1. The group_has_capacity() function is only called in group_classify().
2. Before calling the group_has_capacity() function, group_is_overloaded() will first judge the following formula, if it holds, the group_classify() will directly return the group_overloaded.

(sgs->group_capacity * imbalance_pct) <
(sgs->group_runnable * 100)

Therefore, when the group_has_capacity() is called, the probability that the above formalu holds is very small. Hint compilers about that.

---
  kernel/sched/fair.c | 4 ++--
  1 file changed, 2 insertions(+), 2 deletions(-)
kernel/sched/fair.c +0 -0
index 2ba8f230feb9..9074fd5e23b2 100644

kernel/sched/fair.c group_has_capacity(unsigned int imbalance_pct, struct sg_lb_stats *sgs) · line 8239

Quoted 8 lines
kernel/sched/fair.c +2 -2
@@ -8234,8 +8234,8 @@ group_has_capacity(unsigned int imbalance_pct, struct sg_lb_stats *sgs)
  	if (sgs->sum_nr_running < sgs->group_weight)
  		return true;
 
-	if ((sgs->group_capacity * imbalance_pct) <
-			(sgs->group_runnable * 100))
+	if (unlikely((sgs->group_capacity * imbalance_pct) <
+			(sgs->group_runnable * 100)))
  		return false;

Isn't the probability that this second check will match around 0%?

I.e. wouldn't the right fix be to remove the duplicate check from group_has_capacity(), because it's already been checked in group_classify()? Maybe while leaving a comment in place?

Thanks,

Ingo

author
#3 lore raw
Quoted 6 lines · Qi Zheng

Yeah, because of the following two points, I also think the probability is 0%:
a) the sd is protected by rcu lock, and load_balance() func is between rcu_read_lock() and rcu_read_unlock().
b) the sgs is a local variable.

Quoted 54 lines

So in the group_classify(), the env->sd->imbalance_pct and the sgs will not be changed. May I remove the duplicate check from group_has_capacity() and resubmit a patch?

Yours,
Qi Zheng

Quoted 46 lines · Ingo Molnar
Quoted 24 lines · Qi Zheng

1. The group_has_capacity() function is only called in group_classify().
2. Before calling the group_has_capacity() function, group_is_overloaded() will first judge the following formula, if it holds, the group_classify() will directly return the group_overloaded.

    (sgs->group_capacity * imbalance_pct) < (sgs->group_runnable * 100)

Therefore, when the group_has_capacity() is called, the probability that the above formalu holds is very small. Hint compilers about that.

---
  kernel/sched/fair.c | 4 ++--

  1 file changed, 2 insertions(+), 2 deletions(-)
kernel/sched/fair.c +0 -0
index 2ba8f230feb9..9074fd5e23b2 100644

kernel/sched/fair.c group_has_capacity(unsigned int imbalance_pct, · line 8239

Quoted 8 lines
kernel/sched/fair.c +2 -2
@@ -8234,8 +8234,8 @@ group_has_capacity(unsigned int imbalance_pct, 
 struct sg_lb_stats *sgs)
       if (sgs->sum_nr_running < sgs->group_weight)
           return true;
-    if ((sgs->group_capacity * imbalance_pct) <
-            (sgs->group_runnable * 100))
+    if (unlikely((sgs->group_capacity * imbalance_pct) <
+            (sgs->group_runnable * 100)))
           return false;

Isn't the probability that this second check will match around 0%?

I.e. wouldn't the right fix be to remove the duplicate check from group_has_capacity(), because it's already been checked in group_classify()? Maybe while leaving a comment in place?

Thanks,

    Ingo

Hi,

As Valentin and I discussed in the patch below, simply removing the check may not be completely harmless.

	[PATCH]sched/fair: Remove the duplicate check from
					group_has_capacity() :
	-	if ((sgs->group_capacity * imbalance_pct) <
	-			(sgs->group_runnable * 100))
	-		return false;

If sum_nr_running < group_weight, we won't evaluate it. If sum_nr_running > group_weight, we either won't call into
group_has_capacity() or we'll have checked it already in group_overloaded().
But in the case of sum_nr_running == group_weight, we can run to this check.

Although I also think it is unlikely to cause the significant capacity pressure at the == case, but I'm not sure whether there are some special scenarios. such as some cpus in sg->cpumask are no longer active, or other scenarios?

So adding the unlikely() in group_has_capacity() may be the safest way.

Add Valentin Schneider <[email protected]>.

Yours,
Qi Zheng

maintainer
#4 lore raw
Quoted 75 lines · Qi Zheng
Quoted 6 lines · Qi Zheng

Yeah, because of the following two points, I also think the probability is 0%:
a) the sd is protected by rcu lock, and load_balance() func is between rcu_read_lock() and rcu_read_unlock().
b) the sgs is a local variable.

Quoted 54 lines

So in the group_classify(), the env->sd->imbalance_pct and the sgs will not be changed. May I remove the duplicate check from group_has_capacity() and resubmit a patch?

Yours,
Qi Zheng

Quoted 46 lines · Ingo Molnar
Quoted 24 lines · Qi Zheng

1. The group_has_capacity() function is only called in group_classify().
2. Before calling the group_has_capacity() function, group_is_overloaded() will first judge the following formula, if it holds, the group_classify() will directly return the group_overloaded.

(sgs->group_capacity * imbalance_pct) <
(sgs->group_runnable * 100)

Therefore, when the group_has_capacity() is called, the probability that the above formalu holds is very small. Hint compilers about that.

---
  kernel/sched/fair.c | 4 ++--
  1 file changed, 2 insertions(+), 2 deletions(-)
kernel/sched/fair.c +0 -0
index 2ba8f230feb9..9074fd5e23b2 100644

kernel/sched/fair.c group_has_capacity(unsigned int imbalance_pct, · line 8239

Quoted 8 lines
kernel/sched/fair.c +2 -2
@@ -8234,8 +8234,8 @@ group_has_capacity(unsigned int imbalance_pct,
 struct sg_lb_stats *sgs)
      if (sgs->sum_nr_running < sgs->group_weight)
          return true;
-    if ((sgs->group_capacity * imbalance_pct) <
-            (sgs->group_runnable * 100))
+    if (unlikely((sgs->group_capacity * imbalance_pct) <
+            (sgs->group_runnable * 100)))
          return false;

Isn't the probability that this second check will match around 0%?

I.e. wouldn't the right fix be to remove the duplicate check from group_has_capacity(), because it's already been checked in group_classify()? Maybe while leaving a comment in place?

Thanks,

Ingo

Hi,

As Valentin and I discussed in the patch below, simply removing the check may not be completely harmless.

[PATCH]sched/fair: Remove the duplicate check from
group_has_capacity() :
- if ((sgs->group_capacity * imbalance_pct) <
- (sgs->group_runnable * 100))
- return false;

Quoted 6 lines

If sum_nr_running < group_weight, we won't evaluate it. If sum_nr_running > group_weight, we either won't call into
group_has_capacity() or we'll have checked it already in group_overloaded().
But in the case of sum_nr_running == group_weight, we can run to this check.

The case "sum_nr_running == group_weight" should not be considered as a corner case because that's the final state that we are trying to reach with load balance: 1 task per CPU
And because of task migrations involved to reach this state, we easily have a temporarly low group_utilization (because of the migration) but a high group_runnable. This state highlights the fact that some tasks were competing for CPU cycles before the migration done by the load balance and the task that remains on the CPU, should fill the spare capacity. So the test prevents the load balance to immediately put back another task on the CPU

Removing the condition should not be considered

Quoted 8 lines

Although I also think it is unlikely to cause the significant capacity pressure at the == case, but I'm not sure whether there are some special scenarios. such as some cpus in sg->cpumask are no longer active, or other scenarios?

So adding the unlikely() in group_has_capacity() may be the safest way.

Adding unlikely() is safe and I'm fine to add it but I'd like some figures that show improvements

Regards,
Vincent

Quoted 5 lines

Add Valentin Schneider <[email protected]>.

Yours,
Qi Zheng