[PATCH 0/2] sched/fair: feec()/scale_rt_capacity() improvements

[PATCH 0/2] sched/fair: feec()/scale_rt_capacity() improvements

[Pierre Gondois]

This patch-set aims to improve:
 - find_energy_efficient_cpu() by removing max_spare_cap_cpu from
   the candidate CPUs if prev_cpu is already the CPU with the
   maximum spared capacity.
 - scale_rt_capacity() by using irq scaling on RT and DL rq signals
   and removing irq signal from the available remaining capacity.

Pierre Gondois (2):
  sched/fair: Check if prev_cpu has highest spare cap in feec()
  sched/fair: Use IRQ scaling for all sched classes

 kernel/sched/fair.c | 32 +++++++++++++++++++-------------
 1 file changed, 19 insertions(+), 13 deletions(-)

-- 
2.25.1

[PATCH 1/2] sched/fair: Check if prev_cpu has highest spare cap in feec()

[Pierre Gondois]

When evaluating the CPU candidates in the perf domain (pd) containing
the previously used CPU (prev_cpu), find_energy_efficient_cpu()
evaluates the energy of the pd:
- without the task (base_energy)
- with the task placed on prev_cpu (if the task fits)
- with the task placed on the CPU with the highest spare capacity,
  prev_cpu being excluded from this set

If prev_cpu is already the CPU with the highest spare capacity,
max_spare_cap_cpu will be the CPU with the second highest spare
capacity.

On an Arm64 Juno-r2, with a workload of 10 tasks at a 10% duty cycle,
when prev_cpu and max_spare_cap_cpu are both valid candidates,
prev_spare_cap > max_spare_cap at ~82%.
Thus the energy of the pd when placing the task on max_spare_cap_cpu
is computed with no possible positive outcome 82% most of the time.

Do not consider max_spare_cap_cpu as a valid candidate if
prev_spare_cap > max_spare_cap.

Signed-off-by: Pierre Gondois <pierre.gondois@arm.com>
---
 kernel/sched/fair.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 914096c5b1ae..bcae7bdd5582 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6900,7 +6900,7 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
 	for (; pd; pd = pd->next) {
 		unsigned long cpu_cap, cpu_thermal_cap, util;
 		unsigned long cur_delta, max_spare_cap = 0;
-		bool compute_prev_delta = false;
+		unsigned long prev_spare_cap = 0;
 		int max_spare_cap_cpu = -1;
 		unsigned long base_energy;
 
@@ -6944,18 +6944,19 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
 
 			if (cpu == prev_cpu) {
 				/* Always use prev_cpu as a candidate. */
-				compute_prev_delta = true;
+				prev_spare_cap = cpu_cap;
 			} else if (cpu_cap > max_spare_cap) {
 				/*
 				 * Find the CPU with the maximum spare capacity
-				 * in the performance domain.
+				 * among the remaining CPUs in the performance
+				 * domain.
 				 */
 				max_spare_cap = cpu_cap;
 				max_spare_cap_cpu = cpu;
 			}
 		}
 
-		if (max_spare_cap_cpu < 0 && !compute_prev_delta)
+		if (max_spare_cap_cpu < 0 && prev_spare_cap == 0)
 			continue;
 
 		eenv_pd_busy_time(&eenv, cpus, p);
@@ -6963,7 +6964,7 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
 		base_energy = compute_energy(&eenv, pd, cpus, p, -1);
 
 		/* Evaluate the energy impact of using prev_cpu. */
-		if (compute_prev_delta) {
+		if (prev_spare_cap > 0) {
 			prev_delta = compute_energy(&eenv, pd, cpus, p,
 						    prev_cpu);
 			/* CPU utilization has changed */
@@ -6974,7 +6975,7 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
 		}
 
 		/* Evaluate the energy impact of using max_spare_cap_cpu. */
-		if (max_spare_cap_cpu >= 0) {
+		if (max_spare_cap_cpu >= 0 && max_spare_cap > prev_spare_cap) {
 			cur_delta = compute_energy(&eenv, pd, cpus, p,
 						   max_spare_cap_cpu);
 			/* CPU utilization has changed */
-- 
2.25.1

[PATCH 2/2] sched/fair: Use IRQ scaling for all sched classes

[Pierre Gondois]

The time spent executing IRQ handlers is not reflected in the
utilization of CPU. IRQ scaling reduces rq CFS, RT and DL
util by reflecting the CPU capacity reduction due to IRQs.

commit 9033ea11889f ("cpufreq/schedutil: Take time spent in interrupts
into account")
introduced the notion of IRQ scaling for the now called
effective_cpu_util() function with the following expression (for the
CPU util):
  IRQ util_avg + (max_cap - IRQ util_avg / max_cap ) * /Sum rq util_avg

commit 523e979d3164 ("sched/core: Use PELT for scale_rt_capacity()")
introduced IRQ scaling for scale_rt_capacity(), but without scaling
RT and DL rq util.

scale_rt_capacity() excludes RT and DL rq signals from IRQ scaling.
Only the available capacity is scaled. However RT and DL rq util
should also be scaled.

Applying IRQ scaling allows to extract the IRQ util avg. So IRQ util
avg should also be subtracted from the available capacity.
Thermal pressure is not execution time but reduces the maximum
possible capacity of a CPU. So IRQ scaling should not be applied.

Thus, in this order:
 - subtract thermal pressure
 - apply IRQ scaling on the remaining capacity (RT + DL + CFS + free)
 - subtract IRQ util

Also, sort variables in reverse tree order.

Signed-off-by: Pierre Gondois <pierre.gondois@arm.com>
---
 kernel/sched/fair.c | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index bcae7bdd5582..546e490d6753 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8468,16 +8468,23 @@ static inline void init_sd_lb_stats(struct sd_lb_stats *sds)
 
 static unsigned long scale_rt_capacity(int cpu)
 {
-	struct rq *rq = cpu_rq(cpu);
 	unsigned long max = arch_scale_cpu_capacity(cpu);
+	struct rq *rq = cpu_rq(cpu);
+	unsigned long irq, thermal;
 	unsigned long used, free;
-	unsigned long irq;
 
 	irq = cpu_util_irq(rq);
 
 	if (unlikely(irq >= max))
 		return 1;
 
+	thermal = thermal_load_avg(rq);
+	if (unlikely(thermal >= max))
+		return 1;
+
+	free = max - thermal;
+	free = scale_irq_capacity(free, irq, max);
+
 	/*
 	 * avg_rt.util_avg and avg_dl.util_avg track binary signals
 	 * (running and not running) with weights 0 and 1024 respectively.
@@ -8486,14 +8493,12 @@ static unsigned long scale_rt_capacity(int cpu)
 	 */
 	used = READ_ONCE(rq->avg_rt.util_avg);
 	used += READ_ONCE(rq->avg_dl.util_avg);
-	used += thermal_load_avg(rq);
+	used += irq;
 
-	if (unlikely(used >= max))
+	if (unlikely(used >= free))
 		return 1;
 
-	free = max - used;
-
-	return scale_irq_capacity(free, irq, max);
+	return free - used;
 }
 
 static void update_cpu_capacity(struct sched_domain *sd, int cpu)
-- 
2.25.1

Re: [PATCH 2/2] sched/fair: Use IRQ scaling for all sched classes

[Vincent Guittot]

On Fri, 19 Aug 2022 at 17:33, Pierre Gondois <pierre.gondois@arm.com> wrote:
>
> The time spent executing IRQ handlers is not reflected in the
> utilization of CPU. IRQ scaling reduces rq CFS, RT and DL
> util by reflecting the CPU capacity reduction due to IRQs.
>
> commit 9033ea11889f ("cpufreq/schedutil: Take time spent in interrupts
> into account")
> introduced the notion of IRQ scaling for the now called
> effective_cpu_util() function with the following expression (for the
> CPU util):
>   IRQ util_avg + (max_cap - IRQ util_avg / max_cap ) * /Sum rq util_avg
>
> commit 523e979d3164 ("sched/core: Use PELT for scale_rt_capacity()")
> introduced IRQ scaling for scale_rt_capacity(), but without scaling
> RT and DL rq util.
>
> scale_rt_capacity() excludes RT and DL rq signals from IRQ scaling.
> Only the available capacity is scaled. However RT and DL rq util
> should also be scaled.

RT and DL are not excluded, they are removed before scaling the
available time. We compute the available cpu capacity in the clock
task domain before scaling it in the full clock domain

Let imagine that we have the following timeshare:

|       100%      |
|-IRQ-|-RT--|-----|
| 33% | 33% | 33% |
      |   100%    |
      | 50% | 50% |

irq uses a third of the time

RT uses a third of the time but 50% of the clock task as the time in
interrupt context is not accounted for. This means that the RT
utilization is 50%

In order to know what is available for others we do:

100% - 50% RT = 50% available in the clock task context

Then, we scale the 50% of available time to take the time stolen by IRQ

(100% - 33% IRQ) * 50% / 100% = 33%

So the available capacity for others is 33% of the original capacity
which is correct

What you're proposing:

free = (100% - 33% IRQ) * 100% / 100% = 67%

used = 50% RT + 33% IRQ == 83% whereas it should be 33% RT + 33% IRQ == 66%

Then free < used which means that there is no capacity available for
others which is not true

>
> Applying IRQ scaling allows to extract the IRQ util avg. So IRQ util
> avg should also be subtracted from the available capacity.
> Thermal pressure is not execution time but reduces the maximum
> possible capacity of a CPU. So IRQ scaling should not be applied.

thermal pressure uses clock_task so it has the same constraint as RT,
DL and CFS signal i.e. irq time is not accounted

>
> Thus, in this order:
>  - subtract thermal pressure
>  - apply IRQ scaling on the remaining capacity (RT + DL + CFS + free)
>  - subtract IRQ util
>
> Also, sort variables in reverse tree order.
>
> Signed-off-by: Pierre Gondois <pierre.gondois@arm.com>
> ---
>  kernel/sched/fair.c | 19 ++++++++++++-------
>  1 file changed, 12 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index bcae7bdd5582..546e490d6753 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8468,16 +8468,23 @@ static inline void init_sd_lb_stats(struct sd_lb_stats *sds)
>
>  static unsigned long scale_rt_capacity(int cpu)
>  {
> -       struct rq *rq = cpu_rq(cpu);
>         unsigned long max = arch_scale_cpu_capacity(cpu);
> +       struct rq *rq = cpu_rq(cpu);
> +       unsigned long irq, thermal;
>         unsigned long used, free;
> -       unsigned long irq;
>
>         irq = cpu_util_irq(rq);
>
>         if (unlikely(irq >= max))
>                 return 1;
>
> +       thermal = thermal_load_avg(rq);
> +       if (unlikely(thermal >= max))
> +               return 1;
> +
> +       free = max - thermal;
> +       free = scale_irq_capacity(free, irq, max);
> +
>         /*
>          * avg_rt.util_avg and avg_dl.util_avg track binary signals
>          * (running and not running) with weights 0 and 1024 respectively.
> @@ -8486,14 +8493,12 @@ static unsigned long scale_rt_capacity(int cpu)
>          */
>         used = READ_ONCE(rq->avg_rt.util_avg);
>         used += READ_ONCE(rq->avg_dl.util_avg);
> -       used += thermal_load_avg(rq);
> +       used += irq;

rq->avg_rt.util_avg and irq==cpu_util_irq(rq)) are not in the same
time scale so you can't add them


>
> -       if (unlikely(used >= max))
> +       if (unlikely(used >= free))
>                 return 1;
>
> -       free = max - used;
> -
> -       return scale_irq_capacity(free, irq, max);
> +       return free - used;
>  }
>
>  static void update_cpu_capacity(struct sched_domain *sd, int cpu)
> --
> 2.25.1
>

Re: [PATCH 2/2] sched/fair: Use IRQ scaling for all sched classes

[Pierre Gondois]

On 8/23/22 18:26, Vincent Guittot wrote:
> On Fri, 19 Aug 2022 at 17:33, Pierre Gondois <pierre.gondois@arm.com> wrote:
>>
>> The time spent executing IRQ handlers is not reflected in the
>> utilization of CPU. IRQ scaling reduces rq CFS, RT and DL
>> util by reflecting the CPU capacity reduction due to IRQs.
>>
>> commit 9033ea11889f ("cpufreq/schedutil: Take time spent in interrupts
>> into account")
>> introduced the notion of IRQ scaling for the now called
>> effective_cpu_util() function with the following expression (for the
>> CPU util):
>>    IRQ util_avg + (max_cap - IRQ util_avg / max_cap ) * /Sum rq util_avg
>>
>> commit 523e979d3164 ("sched/core: Use PELT for scale_rt_capacity()")
>> introduced IRQ scaling for scale_rt_capacity(), but without scaling
>> RT and DL rq util.
>>
>> scale_rt_capacity() excludes RT and DL rq signals from IRQ scaling.
>> Only the available capacity is scaled. However RT and DL rq util
>> should also be scaled.
> 
> RT and DL are not excluded, they are removed before scaling the
> available time. We compute the available cpu capacity in the clock
> task domain before scaling it in the full clock domain
> 
> Let imagine that we have the following timeshare:
> 
> |       100%      |
> |-IRQ-|-RT--|-----|
> | 33% | 33% | 33% |
>        |   100%    |
>        | 50% | 50% |
> 
> irq uses a third of the time
> 
> RT uses a third of the time but 50% of the clock task as the time in
> interrupt context is not accounted for. This means that the RT
> utilization is 50%
> 
> In order to know what is available for others we do:
> 
> 100% - 50% RT = 50% available in the clock task context
> 
> Then, we scale the 50% of available time to take the time stolen by IRQ
> 
> (100% - 33% IRQ) * 50% / 100% = 33%
> 
> So the available capacity for others is 33% of the original capacity
> which is correct
> 
> What you're proposing:
> 
> free = (100% - 33% IRQ) * 100% / 100% = 67%
> 
> used = 50% RT + 33% IRQ == 83% whereas it should be 33% RT + 33% IRQ == 66%
> 
> Then free < used which means that there is no capacity available for
> others which is not true

Ok yes indeed, the scaling is correct as it is.

Thanks for the detailed explanation,
Pierre

> 
>>
>> Applying IRQ scaling allows to extract the IRQ util avg. So IRQ util
>> avg should also be subtracted from the available capacity.
>> Thermal pressure is not execution time but reduces the maximum
>> possible capacity of a CPU. So IRQ scaling should not be applied.
> 
> thermal pressure uses clock_task so it has the same constraint as RT,
> DL and CFS signal i.e. irq time is not accounted
> 
>>
>> Thus, in this order:
>>   - subtract thermal pressure
>>   - apply IRQ scaling on the remaining capacity (RT + DL + CFS + free)
>>   - subtract IRQ util
>>
>> Also, sort variables in reverse tree order.
>>
>> Signed-off-by: Pierre Gondois <pierre.gondois@arm.com>
>> ---
>>   kernel/sched/fair.c | 19 ++++++++++++-------
>>   1 file changed, 12 insertions(+), 7 deletions(-)
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index bcae7bdd5582..546e490d6753 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -8468,16 +8468,23 @@ static inline void init_sd_lb_stats(struct sd_lb_stats *sds)
>>
>>   static unsigned long scale_rt_capacity(int cpu)
>>   {
>> -       struct rq *rq = cpu_rq(cpu);
>>          unsigned long max = arch_scale_cpu_capacity(cpu);
>> +       struct rq *rq = cpu_rq(cpu);
>> +       unsigned long irq, thermal;
>>          unsigned long used, free;
>> -       unsigned long irq;
>>
>>          irq = cpu_util_irq(rq);
>>
>>          if (unlikely(irq >= max))
>>                  return 1;
>>
>> +       thermal = thermal_load_avg(rq);
>> +       if (unlikely(thermal >= max))
>> +               return 1;
>> +
>> +       free = max - thermal;
>> +       free = scale_irq_capacity(free, irq, max);
>> +
>>          /*
>>           * avg_rt.util_avg and avg_dl.util_avg track binary signals
>>           * (running and not running) with weights 0 and 1024 respectively.
>> @@ -8486,14 +8493,12 @@ static unsigned long scale_rt_capacity(int cpu)
>>           */
>>          used = READ_ONCE(rq->avg_rt.util_avg);
>>          used += READ_ONCE(rq->avg_dl.util_avg);
>> -       used += thermal_load_avg(rq);
>> +       used += irq;
> 
> rq->avg_rt.util_avg and irq==cpu_util_irq(rq)) are not in the same
> time scale so you can't add them
> 
> 
>>
>> -       if (unlikely(used >= max))
>> +       if (unlikely(used >= free))
>>                  return 1;
>>
>> -       free = max - used;
>> -
>> -       return scale_irq_capacity(free, irq, max);
>> +       return free - used;
>>   }
>>
>>   static void update_cpu_capacity(struct sched_domain *sd, int cpu)
>> --
>> 2.25.1
>>

Re: [PATCH 1/2] sched/fair: Check if prev_cpu has highest spare cap in feec()

[Dietmar Eggemann]

On 19/08/2022 17:33, Pierre Gondois wrote:
> When evaluating the CPU candidates in the perf domain (pd) containing
> the previously used CPU (prev_cpu), find_energy_efficient_cpu()
> evaluates the energy of the pd:
> - without the task (base_energy)
> - with the task placed on prev_cpu (if the task fits)
> - with the task placed on the CPU with the highest spare capacity,
>   prev_cpu being excluded from this set
> 
> If prev_cpu is already the CPU with the highest spare capacity,
> max_spare_cap_cpu will be the CPU with the second highest spare
> capacity.
> 
> On an Arm64 Juno-r2, with a workload of 10 tasks at a 10% duty cycle,
> when prev_cpu and max_spare_cap_cpu are both valid candidates,
> prev_spare_cap > max_spare_cap at ~82%.
> Thus the energy of the pd when placing the task on max_spare_cap_cpu
> is computed with no possible positive outcome 82% most of the time.
> 
> Do not consider max_spare_cap_cpu as a valid candidate if
> prev_spare_cap > max_spare_cap.
> 
> Signed-off-by: Pierre Gondois <pierre.gondois@arm.com>

LGTM. When I ran the workload I see this happening in 50%-90% of the EAS
wakeups. This should prevent one needless compute_energy() call out of 7
on a typical 3-gear system like 2x2x4 in these cases.

Reviewed-by: Dietmar Eggemann <dietmar.eggemann@arm.com>

[...]

Re: [PATCH 1/2] sched/fair: Check if prev_cpu has highest spare cap in feec()

[Pierre Gondois]

Hello Peter,

The second patch:
  -[PATCH 2/2] sched/fair: Use IRQ scaling for all sched classes
must be dropped, cf. Vincent Guittot's review, but I believe this patch
should be ok to take if there is no other comment,

Regards,
Pierre

On 8/29/22 07:13, Dietmar Eggemann wrote:
> On 19/08/2022 17:33, Pierre Gondois wrote:
>> When evaluating the CPU candidates in the perf domain (pd) containing
>> the previously used CPU (prev_cpu), find_energy_efficient_cpu()
>> evaluates the energy of the pd:
>> - without the task (base_energy)
>> - with the task placed on prev_cpu (if the task fits)
>> - with the task placed on the CPU with the highest spare capacity,
>>    prev_cpu being excluded from this set
>>
>> If prev_cpu is already the CPU with the highest spare capacity,
>> max_spare_cap_cpu will be the CPU with the second highest spare
>> capacity.
>>
>> On an Arm64 Juno-r2, with a workload of 10 tasks at a 10% duty cycle,
>> when prev_cpu and max_spare_cap_cpu are both valid candidates,
>> prev_spare_cap > max_spare_cap at ~82%.
>> Thus the energy of the pd when placing the task on max_spare_cap_cpu
>> is computed with no possible positive outcome 82% most of the time.
>>
>> Do not consider max_spare_cap_cpu as a valid candidate if
>> prev_spare_cap > max_spare_cap.
>>
>> Signed-off-by: Pierre Gondois <pierre.gondois@arm.com>
> 
> LGTM. When I ran the workload I see this happening in 50%-90% of the EAS
> wakeups. This should prevent one needless compute_energy() call out of 7
> on a typical 3-gear system like 2x2x4 in these cases.
> 
> Reviewed-by: Dietmar Eggemann <dietmar.eggemann@arm.com>
> 
> [...]