| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <CAKfTPtAOHmhNv_1q0k7qxmR8tTdw3+7+UBRuKMyXNJsxoTgsbg@mail.gmail.com>
Date: Tue, 3 Feb 2026 18:16:27 +0100
From: Vincent Guittot <vincent.guittot@...aro.org>
To: Qiliang Yuan <realwujing@...il.com>
Cc: Ingo Molnar <mingo@...hat.com>, Peter Zijlstra <peterz@...radead.org>,
Juri Lelli <juri.lelli@...hat.com>, Qiliang Yuan <yuanql9@...natelecom.cn>,
Dietmar Eggemann <dietmar.eggemann@....com>, Steven Rostedt <rostedt@...dmis.org>,
Ben Segall <bsegall@...gle.com>, Mel Gorman <mgorman@...e.de>,
Valentin Schneider <vschneid@...hat.com>, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2 RSEND] sched/fair: Optimize EAS energy calculation
complexity from O(N) to O(1) inside inner loop
On Mon, 2 Feb 2026 at 04:05, Qiliang Yuan <realwujing@...il.com> wrote:
>
> Pre-calculate the base maximum utilization of each performance domain during the
> main loop of find_energy_efficient_cpu() and cache it in the local
> 'energy_env' structure.
>
> By caching this base value, the maximum utilization for candidate CPU
> placements (such as prev_cpu and max_spare_cap_cpu) can be determined in
> O(1) time, eliminating redundant scans of the performance domain. This
> optimizes the energy estimation path by reducing the number of scans per
> performance domain from three to one.
Ok, but the whole feec() remains O(n)
>
> This change significantly reduces wake-up latency on systems with high core
> counts or complex performance domain topologies by minimizing the overall
> complexity of the Energy-Aware Scheduling (EAS) calculation.
Could you add some figures to highlight the statement above ?
>
> Signed-off-by: Qiliang Yuan <yuanql9@...natelecom.cn>
> Signed-off-by: Qiliang Yuan <realwujing@...il.com>
> ---
> v2:
> - Ensure RCU safety by using local 'energy_env' for caching instead of
> modifying the shared 'perf_domain' structure.
> - Consolidate pre-calculation into the main loop to avoid an extra pass
> over the performance domains.
> v1:
> - Optimize energy calculation by pre-calculating performance domain max utilization.
> - Add max_util and max_spare_cap_cpu to struct perf_domain.
> - Reduce inner loop complexity from O(N) to O(1) for energy estimation.
>
> kernel/sched/fair.c | 36 ++++++++++++++++++------------------
> 1 file changed, 18 insertions(+), 18 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index e71302282671..5c114c49c202 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8148,6 +8148,7 @@ struct energy_env {
> unsigned long pd_busy_time;
> unsigned long cpu_cap;
> unsigned long pd_cap;
> + unsigned long pd_max_util;
> };
>
> /*
> @@ -8215,41 +8216,32 @@ static inline void eenv_pd_busy_time(struct energy_env *eenv,
> * exceed @eenv->cpu_cap.
> */
> static inline unsigned long
> -eenv_pd_max_util(struct energy_env *eenv, struct cpumask *pd_cpus,
> +eenv_pd_max_util(struct energy_env *eenv, struct perf_domain *pd,
> struct task_struct *p, int dst_cpu)
> {
> - unsigned long max_util = 0;
> - int cpu;
> + unsigned long max_util = eenv->pd_max_util;
>
> - for_each_cpu(cpu, pd_cpus) {
> - struct task_struct *tsk = (cpu == dst_cpu) ? p : NULL;
> - unsigned long util = cpu_util(cpu, p, dst_cpu, 1);
> + if (dst_cpu >= 0 && cpumask_test_cpu(dst_cpu, perf_domain_span(pd))) {
> + unsigned long util = cpu_util(dst_cpu, p, dst_cpu, 1);
> unsigned long eff_util, min, max;
>
> - /*
> - * Performance domain frequency: utilization clamping
> - * must be considered since it affects the selection
> - * of the performance domain frequency.
> - * NOTE: in case RT tasks are running, by default the min
> - * utilization can be max OPP.
> - */
> - eff_util = effective_cpu_util(cpu, util, &min, &max);
> + eff_util = effective_cpu_util(dst_cpu, util, &min, &max);
>
> /* Task's uclamp can modify min and max value */
> - if (tsk && uclamp_is_used()) {
> + if (uclamp_is_used()) {
> min = max(min, uclamp_eff_value(p, UCLAMP_MIN));
>
> /*
> * If there is no active max uclamp constraint,
> * directly use task's one, otherwise keep max.
> */
> - if (uclamp_rq_is_idle(cpu_rq(cpu)))
> + if (uclamp_rq_is_idle(cpu_rq(dst_cpu)))
> max = uclamp_eff_value(p, UCLAMP_MAX);
> else
> max = max(max, uclamp_eff_value(p, UCLAMP_MAX));
> }
>
> - eff_util = sugov_effective_cpu_perf(cpu, eff_util, min, max);
> + eff_util = sugov_effective_cpu_perf(dst_cpu, eff_util, min, max);
> max_util = max(max_util, eff_util);
> }
>
> @@ -8265,7 +8257,7 @@ static inline unsigned long
> compute_energy(struct energy_env *eenv, struct perf_domain *pd,
> struct cpumask *pd_cpus, struct task_struct *p, int dst_cpu)
> {
> - unsigned long max_util = eenv_pd_max_util(eenv, pd_cpus, p, dst_cpu);
> + unsigned long max_util = eenv_pd_max_util(eenv, pd, p, dst_cpu);
> unsigned long busy_time = eenv->pd_busy_time;
> unsigned long energy;
>
> @@ -8376,12 +8368,20 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
>
> eenv.cpu_cap = cpu_actual_cap;
> eenv.pd_cap = 0;
> + eenv.pd_max_util = 0;
>
> for_each_cpu(cpu, cpus) {
> struct rq *rq = cpu_rq(cpu);
> + unsigned long util_b, eff_util_b, min_b, max_b;
>
> eenv.pd_cap += cpu_actual_cap;
>
> + /* Pre-calculate base max utilization for the performance domain */
> + util_b = cpu_util(cpu, p, -1, 1);
> + eff_util_b = effective_cpu_util(cpu, util_b, &min_b, &max_b);
> + eff_util_b = sugov_effective_cpu_perf(cpu, eff_util_b, min_b, max_b);
> + eenv.pd_max_util = max(eenv.pd_max_util, eff_util_b);
You pre calculate the above for all CPUs (each CPU of each PD)
in order to not do the above 2-3 times for PDs with a CPU that could fit.
So this will be a win if all PDs have a CPU that fits and we have to
compute_energy for them but not if only few/one PDs have a CPU that
fits
> +
> if (!cpumask_test_cpu(cpu, sched_domain_span(sd)))
> continue;
>
> --
> 2.51.0
>
Powered by blists - more mailing lists