uclamp sum aggregation
Subsystems (2)
cover uclamp sum aggregation
Current uclamp implementation, max aggregation, has several drawbacks. This series gives an alternative implementation that addresses the problems and shows other advantages, mostly:
1. Simplicity. Sum aggregation implements uclamp with less than half of code than max aggregation.
2. Effectiveness. Sum aggregation shows better uclamp effectiveness, either in benchmark scores or more importantly, in energy efficiency.
3. Works on its own. No changes in cpufreq or other sub-systems are needed.
4. Low-overhead. No bucket operations and no need to tweak the number of buckets to balance between overhead and uclamp granularity.
The key idea of sum aggregation is fairly simple. Each task has a util_avg_bias, which is obtained by:
util_avg_bias = clamp(util_avg, uclamp_min, uclamp_max) - util_avg;
If a CPU has N tasks, p1, p2, p3... pN, then we sum the biases up and obtain a rq total bias:
rq_bias = util_avg_bias1 + util_avg_bias2... + util_avg_biasN;
Then we use the biased rq utilization rq_util + rq_bias to select OPP and to schedule tasks.
PATCH BREAKDOWN:
Patch 1/7 reverts a patch that accommodate uclamp_max tasks under max aggregation. This patch is not needed and creates other problems for sum aggregation. It is discussed elsewhere that this patch will be improved and there may not be the need to revert it in the future.
Patch 2, 3 and 4 implement sum aggregation.
Patch 5 and 6 remove max aggregation.
Patch 7 applies PELT decay on negative util_avg_bias. This improves energy efficiency and task placement, but is not strictly necessary.
TESTING:
Two notebooks are shared at
https://nbviewer.org/github/honxia02/notebooks/blob/bb97afd74f49d4b8add8b28ad4378ea337c695a8/whitebox/max.ipynb
https://nbviewer.org/github/honxia02/notebooks/blob/bb97afd74f49d4b8add8b28ad4378ea337c695a8/whitebox/sum-offset.ipynb
The experiments done in notebooks are on Arm Juno r2 board. CPU0-3 are little cores with capacity of 383. CPU4-5 are big cores. The rt-app profiles used for these experiments are included in the notebooks.
Scenario 1: Scheduling 4 tasks with UCLAMP_MAX at 110.
The scheduling decisions are plotted in Out[11]. Both max and sum aggregation understand the UCLAMP_MAX hint and schedule all 4 tasks on the little cluster. Max aggregation sometimes schedule 2 tasks on 1 CPU, and this is the reason why sum aggregation reverts the 1st commit. However, the reverted patch may be improved and this revert may not be needed in the future.
Scenario 2: Scheduling 2 tasks with UCLAMP_MIN and UCLAMP_MAX at a value slightly above the capacity of the little CPU.
Results are in Out[17]. The purpose is to use UCLAMP_MIN to place tasks on the big core. Both max and sum aggregation handle this correctly.
Scenario 3: Task A is a task with a small utilization pinned to CPU4. Task B is an always-running task pinned to CPU5, but UCLAMP_MAX capped at 300. After a while, task A is then pinned to CPU5, joining B.
Results are in Out[23]. Max aggregation sees a frequency spike at 239.75s. When zoomed in, one can see square-wave-like utilization values because of A periodically going to sleep. When A wakes up, its default UCLAMP_MAX of 1024 will uncap B and reach the highest CPU frequency. When A sleeps, B's UCLAMP_MAX will be in effect and will reduce rq utilization. This happens repeatedly, hence the square wave. In contrast, sum aggregation sees a normal increase in utilization when A joins B, without any square-wave behavior.
Scenario 4: 4 always-running tasks with UCLAMP_MAX of 110 pinned to the little PD (CPU0-3). 4 same tasks pinned to the big PD (CPU4-5). After a while, remove the CPU pinning of the 4 tasks on the big PD.
Results are in Out[29]. After unpinning, max aggregation moves all 8 tasks to the little cluster, but schedules 5 tasks on CPU0 and 1 each on CPU1-3. In contrast, sum aggregation schedules 2 on each little CPU after unpinning, which is the desired balanced task placement.
Same as Scenario 1, the situation may not be as bad once the improvement of the reverted patch comes out in the future.
Scenario 5: Scheduling 8 tasks with UCLAMP_MAX of 110.
Results are in Out[35] and Out[36]. There's no doubt that sum aggregation yields substantially better scheduling decisions. This tests roughly the same thing as Scenario 4.
EVALUATION:
We backport patches to kernel v6.1 on Pixel 6 and run Android benchmarks.
Speedometer:
We run Speedometer 2.0 to test ADPF/uclamp effectiveness. Because sum aggregation does not circumvent the 20% OPP margin, we reduce uclamp values to 80% to be fair.
------------------------------------------------------
| score | score | % | CPU power (mW) | % | | max | 161.4 | | 2358.9 | | | sum_0.8 | 166.0 | +2.85 | 2485.0 | +5.35 | | sum_tuned | 162.6 | +0.74 | 2332.0 | -1.14 |
------------------------------------------------------
We see a consistant higher score and higher average power consumption. Note that a higher score also means a reduction in run-time, so total energy increase for sum_0.8 is only 1.88%.
We then reduce uclamp values so that the Speedometer score is roughly the same. If we do so, then sum aggregation actually gives a reduced average power and total energy consumption than max aggregation.
UIBench:
-----------------------------------------------------------------
| score | jank percentage | % | CPU power (mW) | % | | max | 0.375% | | 122.75 | | | sum_0.8 | 0.440% | +17.33 | 116.35 | -5.21 | | sum_tuned | 0.220% | -41.33 | 119.35 | -2.77 |
-----------------------------------------------------------------
UIBench on Pixel 6 by default already has a low enough jank percentage. Moving to sum aggregation gives higher jank percentage and lower power consumption. We then tune the hardcoded uclamp values in the Android image to take advantage of the power budget, and can achieve more than 41% jank reduction while still operating with less power consumption than max aggregation.
This result is not suggesting that sum aggregation greatly outperforms max aggregation, because the jank percentage is already very low, but instead suggests that hardcoded uclamp values in the system (like in init scripts) need to be changed to perform well under sum aggregation. If tuned well, sum aggregation generally shows better effectiveness, or the same effectiveness but with less power consumption.
---
Changed in v1 since RFCv3:
- Rebase and add comments as suggested.
- Move util_est changes into a separate patch.
- Fix build failures on !CONFIG_SMP detected by Intel kernel bot.
- Avoid duplicate calls to util() and util_uclamp() functions by using the static key.
Changed in RFCv3:
- Addresses the biggest concern from multiple people, that PELT and uclamp need to be separate. The new design is significantly simpler than the previous revision and separates util_avg_uclamp into the original util_avg (which this series doesn't touch at all) and the util_avg_bias component.
- Keep the tri-state return value of util_fits_cpu().
- Keep both the unclamped and clamped util_est, so that we use the right one depending on the caller in frequency or energy calculations.
Hongyan Xia (7):
Revert "sched/uclamp: Set max_spare_cap_cpu even if max_spare_cap is
0"
sched/uclamp: Track a new util_avg_bias signal sched/uclamp: Add util_est_uclamp
sched/fair: Use util biases for utilization and frequency sched/uclamp: Remove all uclamp bucket logic sched/uclamp: Simplify uclamp_eff_value() Propagate negative bias
include/linux/sched.h | 8 +- init/Kconfig | 32 --- kernel/sched/core.c | 294 ++-------------------- kernel/sched/cpufreq_schedutil.c | 12 +- kernel/sched/debug.c | 2 +- kernel/sched/fair.c | 419 ++++++++++++++++--------------- kernel/sched/pelt.c | 37 +++ kernel/sched/rt.c | 4 - kernel/sched/sched.h | 131 +++------- kernel/sched/syscalls.c | 16 +- 10 files changed, 312 insertions(+), 643 deletions(-)
Signature · 1 line
2.34.1
PATCH 1/7 Revert "sched/uclamp: Set max_spare_cap_cpu even if max_spare_cap is 0"
From: Hongyan Xia <[email protected]>
That commit creates further problems because 0 spare capacity can be either a real indication that the CPU is maxed out, or the CPU is UCLAMP_MAX throttled, but we end up giving all of them a chance which can results in bogus energy calculations. It also tends to schedule tasks on the same CPU and requires load balancing patches. Sum aggregation solves these problems and this patch is not needed.
This reverts commit 6b00a40147653c8ea748e8f4396510f252763364.
--- kernel/sched/fair.c | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-)
kernel/sched/fair.c +6 -5
@@ -8028,10 +8028,11 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)for (; pd; pd = pd->next) {unsigned long util_min = p_util_min, util_max = p_util_max;unsigned long cpu_cap, cpu_actual_cap, util; -long prev_spare_cap =-1 , max_spare_cap =-1 ; +unsigned long cur_delta, max_spare_cap =0 ;unsigned long rq_util_min, rq_util_max; -unsigned long cur_delta, base_energy; +unsigned long prev_spare_cap =0 ;int max_spare_cap_cpu =-1 ; +unsigned long base_energy;int fits, max_fits =-1 ;cpumask_and (cpus,perf_domain_span (pd), cpu_online_mask);
@@ -8093,7 +8094,7 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu) prev_spare_cap = cpu_cap; prev_fits = fits; }else if ((fits > max_fits) || - ((fits == max_fits) && ((long )cpu_cap > max_spare_cap))) { + ((fits == max_fits) && (cpu_cap > max_spare_cap))) {/* * Find the CPU with the maximum spare capacity * among the remaining CPUs in the performance
@@ -8105,7 +8106,7 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu) } } -if (max_spare_cap_cpu <0 && prev_spare_cap <0 ) +if (max_spare_cap_cpu <0 && prev_spare_cap ==0 )continue ;eenv_pd_busy_time (&eenv, cpus, p);
@@ -8113,7 +8114,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 (prev_spare_cap >-1 ) { +if (prev_spare_cap >0 ) { prev_delta =compute_energy (&eenv, pd, cpus, p, prev_cpu);/* CPU utilization has changed */
Signature · 1 line
2.34.1
PATCH 2/7 sched/uclamp: Track a new util_avg_bias signal
In reply to Hongyan XiaAdd a util_avg_bias signal in sched_avg, which is obtained by:
util_avg_bias = clamp(util_avg, uclamp_min, uclamp_max) - util_avg
The task utilization after considering uclamp is;
util_avg_uclamp = util_avg + util_avg_bias
We then sum up all biases on the same rq and use the total bias to bias the rq utilization. This is the core idea of uclamp sum aggregation. The rq utilization will be
rq_util_avg_uclamp = rq_util_avg + total_util_avg_bias
--- include/linux/sched.h | 3 ++- kernel/sched/debug.c | 2 +- kernel/sched/fair.c | 31 +++++++++++++++++++++++++++++++ kernel/sched/pelt.c | 37 +++++++++++++++++++++++++++++++++++++ kernel/sched/sched.h | 24 ++++++++++++++++++++++++ 5 files changed, 95 insertions(+), 2 deletions(-)
include/linux/sched.h +2 -1
@@ -476,7 +476,8 @@ struct sched_avg {u32 period_contrib;unsigned long load_avg;unsigned long runnable_avg; -unsigned long util_avg; +unsigned int util_avg; +int util_avg_bias;unsigned int util_est; }____cacheline_aligned ;
kernel/sched/debug.c +1 -1
@@ -683,7 +683,7 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq) cfs_rq->avg.load_avg);SEQ_printf (m," .%-30s: %lu\n" ,"runnable_avg" , cfs_rq->avg.runnable_avg); -SEQ_printf (m," .%-30s: %lu\n" ,"util_avg" , +SEQ_printf (m," .%-30s: %u\n" ,"util_avg" , cfs_rq->avg.util_avg);SEQ_printf (m," .%-30s: %u\n" ,"util_est" , cfs_rq->avg.util_est);
kernel/sched/fair.c +31 -0
@@ -1089,6 +1089,7 @@ void post_init_entity_util_avg(struct task_struct *p) } sa->runnable_avg = sa->util_avg; + sa->util_avg_bias =0 ; }#else /* !CONFIG_SMP */
@@ -4844,6 +4845,32 @@ static inline unsigned long task_util_est(struct task_struct *p)return max (task_util (p),_task_util_est (p)); } +#ifdef CONFIG_UCLAMP_TASK +static inline long task_util_bias (struct task_struct *p) +{ +return READ_ONCE (p->se.avg.util_avg_bias); +} + +static inline unsigned long task_util_uclamp (struct task_struct *p) +{ +long ret =task_util (p); + + ret +=task_util_bias (p); + +return max (ret,0L ); +} +#else +static inline long task_util_bias (struct task_struct *p) +{ +return 0 ; +} + +static inline unsigned long task_util_uclamp (struct task_struct *p) +{ +return task_util (p); +} +#endif +static inline void util_est_enqueue (struct cfs_rq *cfs_rq,struct task_struct *p) {
@@ -6807,6 +6834,9 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)/* At this point se is NULL and we are at root level*/ add_nr_running (rq,1 ); +util_bias_enqueue (rq, p); +/* XXX: We should skip the update above and only do it once here. */ +cpufreq_update_util (rq,0 );/* * Since new tasks are assigned an initial util_avg equal to
@@ -6898,6 +6928,7 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)/* At this point se is NULL and we are at root level*/ sub_nr_running (rq,1 ); +util_bias_dequeue (rq, p);/* balance early to pull high priority tasks */ if (unlikely (!was_sched_idle &&sched_idle_rq (rq)))
kernel/sched/pelt.c +37 -0
@@ -266,6 +266,39 @@ ___update_load_avg(struct sched_avg *sa, unsigned long load)WRITE_ONCE (sa->util_avg, sa->util_sum / divider); } +#ifdef CONFIG_UCLAMP_TASK +/* avg must belong to the queue this se is on. */ +static void util_bias_update (struct task_struct *p) +{ +unsigned int util, uclamp_min, uclamp_max; +struct rq *rq; +int old, new; + + util =READ_ONCE (p->se.avg.util_avg); + uclamp_min =uclamp_eff_value (p,UCLAMP_MIN ); + uclamp_max =uclamp_eff_value (p,UCLAMP_MAX ); +/* +* uclamp_max at the max value means there is no uclamp_max, and should +* not have any clamping effect at all here. +*/ +if (uclamp_max ==SCHED_CAPACITY_SCALE ) + uclamp_max =UINT_MAX ; + old =READ_ONCE (p->se.avg.util_avg_bias); + new = (int )clamp (util, uclamp_min, uclamp_max) - (int )util; + +WRITE_ONCE (p->se.avg.util_avg_bias, new); +if (!p->se.on_rq) +return ; + rq =task_rq (p); +WRITE_ONCE (rq->cfs.avg.util_avg_bias, +READ_ONCE (rq->cfs.avg.util_avg_bias) + new - old); +} +#else /* !CONFIG_UCLAMP_TASK */ +static void util_bias_update (struct task_struct *p) +{ +} +#endif +/* * sched_entity: *
@@ -296,6 +329,8 @@ int __update_load_avg_blocked_se(u64 now, struct sched_entity *se) {if (___update_load_sum (now, &se->avg,0 ,0 ,0 )) {___update_load_avg (&se->avg,se_weight (se)); +if (entity_is_task (se)) +util_bias_update (task_of (se));trace_pelt_se_tp (se);return 1 ; }
@@ -310,6 +345,8 @@ int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se___update_load_avg (&se->avg,se_weight (se));cfs_se_util_change (&se->avg); +if (entity_is_task (se)) +util_bias_update (task_of (se));trace_pelt_se_tp (se);return 1 ; }
kernel/sched/sched.h +24 -0
@@ -3178,6 +3178,22 @@ uclamp_se_set(struct uclamp_se *uc_se, unsigned int value, bool user_defined) uc_se->user_defined = user_defined; } +static inline void util_bias_enqueue (struct rq *rq,struct task_struct *p) +{ +int rq_val =READ_ONCE (rq->cfs.avg.util_avg_bias); +int p_val =READ_ONCE (p->se.avg.util_avg_bias); + +WRITE_ONCE (rq->cfs.avg.util_avg_bias, rq_val + p_val); +} + +static inline void util_bias_dequeue (struct rq *rq,struct task_struct *p) +{ +int rq_val =READ_ONCE (rq->cfs.avg.util_avg_bias); +int p_val =READ_ONCE (p->se.avg.util_avg_bias); + +WRITE_ONCE (rq->cfs.avg.util_avg_bias, rq_val - p_val); +} +#else /* !CONFIG_UCLAMP_TASK: */ static inline unsigned long
@@ -3215,6 +3231,14 @@ static inline bool uclamp_rq_is_idle(struct rq *rq) return false; } +static inline void util_bias_enqueue (struct rq *rq,struct task_struct *p) +{ +} + +static inline void util_bias_dequeue (struct rq *rq,struct task_struct *p) +{ +} +#endif /* !CONFIG_UCLAMP_TASK */ #ifdef CONFIG_HAVE_SCHED_AVG_IRQ
Signature · 1 line
2.34.1
PATCH 3/7 sched/uclamp: Add util_est_uclamp
In reply to Hongyan XiaThe new util_est_uclamp is essentially clamp(util_est, min, max) and follows how util_est operates.
--- include/linux/sched.h | 1 + kernel/sched/fair.c | 30 ++++++++++++++++++++++++++++++ 2 files changed, 31 insertions(+)
include/linux/sched.h +1 -0
@@ -479,6 +479,7 @@ struct sched_avg {unsigned int util_avg;int util_avg_bias;unsigned int util_est; +unsigned int util_est_uclamp; }____cacheline_aligned ;/*
kernel/sched/fair.c +30 -0
@@ -4859,6 +4859,16 @@ static inline unsigned long task_util_uclamp(struct task_struct *p) return max(ret, 0L); } + +static inline unsigned long _task_util_est_uclamp (struct task_struct *p) +{ +return READ_ONCE (p->se.avg.util_est_uclamp); +} + +static inline unsigned long task_util_est_uclamp (struct task_struct *p) +{ +return max (task_util_uclamp (p),_task_util_est_uclamp (p)); +}#else static inline long task_util_bias (struct task_struct *p) {
@@ -4869,6 +4879,16 @@ static inline unsigned long task_util_uclamp(struct task_struct *p) {return task_util (p); } + +static inline unsigned long _task_util_est_uclamp (struct task_struct *p) +{ +return _task_util_est (p); +} + +static inline unsigned long task_util_est_uclamp (struct task_struct *p) +{ +return task_util_est (p); +}#endif static inline void util_est_enqueue(struct cfs_rq *cfs_rq,
@@ -4883,6 +4903,9 @@ static inline void util_est_enqueue(struct cfs_rq *cfs_rq, enqueued = cfs_rq->avg.util_est; enqueued +=_task_util_est (p);WRITE_ONCE (cfs_rq->avg.util_est, enqueued); + enqueued = cfs_rq->avg.util_est_uclamp; + enqueued +=_task_util_est_uclamp (p); +WRITE_ONCE (cfs_rq->avg.util_est_uclamp, enqueued);trace_sched_util_est_cfs_tp (cfs_rq); }
@@ -4899,6 +4922,9 @@ static inline void util_est_dequeue(struct cfs_rq *cfs_rq, enqueued = cfs_rq->avg.util_est; enqueued -= min_t(unsigned int, enqueued, _task_util_est(p));WRITE_ONCE (cfs_rq->avg.util_est, enqueued); + enqueued = cfs_rq->avg.util_est_uclamp; + enqueued -= min_t(unsigned int, enqueued, _task_util_est_uclamp(p)); +WRITE_ONCE (cfs_rq->avg.util_est_uclamp, enqueued);trace_sched_util_est_cfs_tp (cfs_rq); }
@@ -4986,6 +5012,10 @@ static inline void util_est_update(struct cfs_rq *cfs_rq, ewma -= last_ewma_diff; ewma >>=UTIL_EST_WEIGHT_SHIFT ; done: +WRITE_ONCE (p->se.avg.util_est_uclamp, +clamp (ewma, + (unsigned int )uclamp_eff_value (p,UCLAMP_MIN ), + (unsigned int )uclamp_eff_value (p,UCLAMP_MAX ))); ewma |=UTIL_AVG_UNCHANGED ;WRITE_ONCE (p->se.avg.util_est, ewma);
Signature · 1 line
2.34.1
PATCH 4/7 sched/fair: Use util biases for utilization and frequency
In reply to Hongyan XiaUse the new util_avg_bias for task and runqueue utilization. We also maintain separate util_est and util_est_uclamp signals.
Now that we have the uclamp sum aggregated CFS util value, we do not need to consult uclamp buckets to know how the frequency should be clamped. We simply look at the aggregated top level rq->cfs.avg.util_avg
+ rq->cfs.avg.util_avg_bias and rq->cfs.avg.util_est_uclamp to know what frequency to choose and how to place tasks.
--- kernel/sched/cpufreq_schedutil.c | 12 +- kernel/sched/fair.c | 303 +++++++++++-------------------- kernel/sched/sched.h | 20 +- kernel/sched/syscalls.c | 14 +- 4 files changed, 117 insertions(+), 232 deletions(-)
kernel/sched/cpufreq_schedutil.c +3 -9
@@ -197,7 +197,7 @@ unsigned long sugov_effective_cpu_perf(int cpu, unsigned long actual,static void sugov_get_util (struct sugov_cpu *sg_cpu,unsigned long boost) { -unsigned long min, max, util =cpu_util_cfs_boost (sg_cpu->cpu); +unsigned long min, max, util =cpu_util_cfs_boost_uclamp (sg_cpu->cpu); util =effective_cpu_util (sg_cpu->cpu, util, &min, &max); util =max (util, boost);
@@ -385,11 +385,8 @@ static void sugov_update_single_freq(struct update_util_data *hook, u64 time,/* * Do not reduce the frequency if the CPU has not been idle * recently, as the reduction is likely to be premature then. -* -* Except when the rq is capped by uclamp_max. */ -if (!uclamp_rq_is_capped (cpu_rq (sg_cpu->cpu)) && -sugov_cpu_is_busy (sg_cpu) && next_f < sg_policy->next_freq && +if (sugov_cpu_is_busy (sg_cpu) && next_f < sg_policy->next_freq && !sg_policy->need_freq_update) { next_f = sg_policy->next_freq;
@@ -439,11 +436,8 @@ static void sugov_update_single_perf(struct update_util_data *hook, u64 time,/* * Do not reduce the target performance level if the CPU has not been * idle recently, as the reduction is likely to be premature then. -* -* Except when the rq is capped by uclamp_max. */ -if (!uclamp_rq_is_capped (cpu_rq (sg_cpu->cpu)) && -sugov_cpu_is_busy (sg_cpu) && sg_cpu->util < prev_util) +if (sugov_cpu_is_busy (sg_cpu) && sg_cpu->util < prev_util) sg_cpu->util = prev_util; cpufreq_driver_adjust_perf(sg_cpu->cpu, sg_cpu->bw_min,
kernel/sched/fair.c +111 -192
493 lines not on this page · raw message
kernel/sched/sched.h +1 -19
@@ -3089,9 +3089,8 @@ static inline unsigned long cpu_util_dl(struct rq *rq)return READ_ONCE (rq->avg_dl.util_avg); } -extern unsigned long cpu_util_cfs (int cpu); -extern unsigned long cpu_util_cfs_boost (int cpu); +extern unsigned long cpu_util_cfs_boost_uclamp (int cpu);static inline unsigned long cpu_util_rt (struct rq *rq) {
@@ -3121,21 +3120,6 @@ static inline bool uclamp_rq_is_idle(struct rq *rq)return rq->uclamp_flags &UCLAMP_FLAG_IDLE ; } -/* Is the rq being capped/throttled by uclamp_max? */ -static inline bool uclamp_rq_is_capped (struct rq *rq) -{ -unsigned long rq_util; -unsigned long max_util; - -if (!static_branch_likely (&sched_uclamp_used)) -return false; - - rq_util =cpu_util_cfs (cpu_of (rq)) +cpu_util_rt (rq); - max_util =READ_ONCE (rq->uclamp[UCLAMP_MAX ].value); - -return max_util !=SCHED_CAPACITY_SCALE && rq_util >= max_util; -} -/* * When uclamp is compiled in, the aggregation at rq level is 'turned off' * by default in the fast path and only gets turned on once userspace performs
@@ -3205,8 +3189,6 @@ uclamp_eff_value(struct task_struct *p, enum uclamp_id clamp_id)return SCHED_CAPACITY_SCALE ; } -static inline bool uclamp_rq_is_capped (struct rq *rq) {return false; } -static inline bool uclamp_is_used (void ) {return false;
kernel/sched/syscalls.c +2 -12
@@ -303,13 +303,7 @@ unsigned long effective_cpu_util(int cpu, unsigned long util_cfs, }if (min) { -/* -* The minimum utilization returns the highest level between: -* - the computed DL bandwidth needed with the IRQ pressure which -* steals time to the deadline task. -* - The minimum performance requirement for CFS and/or RT. -*/ - *min =max (irq +cpu_bw_dl (rq),uclamp_rq_get (rq,UCLAMP_MIN )); + *min = irq +cpu_bw_dl (rq);/* * When an RT task is runnable and uclamp is not used, we must
@@ -328,12 +322,8 @@ unsigned long effective_cpu_util(int cpu, unsigned long util_cfs, util = util_cfs +cpu_util_rt (rq); util +=cpu_util_dl (rq); -/* -* The maximum hint is a soft bandwidth requirement, which can be lower -* than the actual utilization because of uclamp_max requirements. -*/ if (max) - *max =min (scale,uclamp_rq_get (rq,UCLAMP_MAX )); + *max = scale;if (util >= scale)return scale;
Signature · 1 line
2.34.1
PATCH 5/7 sched/uclamp: Remove all uclamp bucket logic
In reply to Hongyan XiaAlso rewrite uclamp_update_active() so that the effective uclamp values are updated every time we change task group properties, change system defaults or a request is issued from userspace.
This also signnificantly reduces uclamp overhead because we no longer need to compute effective uclamp values and manipulate buckets every time a task is enqueued or dequeued (in uclamp_rq_{inc/dec}()).
TODO: Rewrite documentation to match the new logic.
--- include/linux/sched.h | 4 - init/Kconfig | 32 ----- kernel/sched/core.c | 287 +++------------------------------------- kernel/sched/fair.c | 4 - kernel/sched/rt.c | 4 - kernel/sched/sched.h | 95 +------------ kernel/sched/syscalls.c | 2 + 7 files changed, 20 insertions(+), 408 deletions(-)
include/linux/sched.h +0 -4
@@ -685,9 +685,6 @@ struct sched_dl_entity { };#ifdef CONFIG_UCLAMP_TASK -/* Number of utilization clamp buckets (shorter alias) */ -#define UCLAMP_BUCKETS CONFIG_UCLAMP_BUCKETS_COUNT -/* * Utilization clamp for a scheduling entity * @value: clamp value "assigned" to a se
@@ -713,7 +710,6 @@ struct sched_dl_entity {*/ struct uclamp_se {unsigned int value :bits_per (SCHED_CAPACITY_SCALE ); -unsigned int bucket_id :bits_per (UCLAMP_BUCKETS );unsigned int active :1 ;unsigned int user_defined :1 ; };
init/Kconfig +0 -32
@@ -817,38 +817,6 @@ config UCLAMP_TASK enforce or grant any specific bandwidth for tasks. If in doubt, say N. - -config UCLAMP_BUCKETS_COUNT - int "Number of supported utilization clamp buckets" - range 5 20 - default 5 - depends on UCLAMP_TASK - help - Defines the number of clamp buckets to use. The range of each bucket - will be SCHED_CAPACITY_SCALE/UCLAMP_BUCKETS_COUNT. The higher the - number of clamp buckets the finer their granularity and the higher - the precision of clamping aggregation and tracking at run-time. - - For example, with the minimum configuration value we will have 5 - clamp buckets tracking 20% utilization each. A 25% boosted tasks will - be refcounted in the [20..39]% bucket and will set the bucket clamp - effective value to 25%. - If a second 30% boosted task should be co-scheduled on the same CPU, - that task will be refcounted in the same bucket of the first task and - it will boost the bucket clamp effective value to 30%. - The clamp effective value of a bucket is reset to its nominal value - (20% in the example above) when there are no more tasks refcounted in - that bucket. - - An additional boost/capping margin can be added to some tasks. In the - example above the 25% task will be boosted to 30% until it exits the - CPU. If that should be considered not acceptable on certain systems, - it's always possible to reduce the margin by increasing the number of - clamp buckets to trade off used memory for run-time tracking - precision. - - If in doubt, use the default value. - endmenu #
kernel/sched/core.c +15 -272
370 lines not on this page · raw message
kernel/sched/fair.c +0 -4
@@ -13217,10 +13217,6 @@ DEFINE_SCHED_CLASS(fair) = {#ifdef CONFIG_SCHED_CORE .task_is_throttled = task_is_throttled_fair,#endif - -#ifdef CONFIG_UCLAMP_TASK - .uclamp_enabled = 1, -#endif };#ifdef CONFIG_SCHED_DEBUG
kernel/sched/rt.c +0 -4
@@ -2680,10 +2680,6 @@ DEFINE_SCHED_CLASS(rt) = {#ifdef CONFIG_SCHED_CORE .task_is_throttled = task_is_throttled_rt,#endif - -#ifdef CONFIG_UCLAMP_TASK - .uclamp_enabled = 1, -#endif };#ifdef CONFIG_RT_GROUP_SCHED
kernel/sched/sched.h +3 -92
138 lines not on this page · raw message
kernel/sched/syscalls.c +2 -0
@@ -520,6 +520,8 @@ static void __setscheduler_uclamp(struct task_struct *p,uclamp_se_set (&p->uclamp_req[UCLAMP_MAX ], attr->sched_util_max, true); } + +uclamp_update_active_nolock (p); }#else /* !CONFIG_UCLAMP_TASK: */
Signature · 1 line
2.34.1
PATCH 6/7 sched/uclamp: Simplify uclamp_eff_value()
In reply to Hongyan XiaThe commit
sched: Remove all uclamp bucket logic
removes uclamp_rq_{inc/dec}() functions, so now p->uclamp contains the correct values all the time after a uclamp_update_active() call, and there's no need to toggle the boolean active after an update. As a result, this function is fairly simple now and can live as a static inline function.
--- kernel/sched/core.c | 13 ++++--------- kernel/sched/sched.h | 10 +++++++++- 2 files changed, 13 insertions(+), 10 deletions(-)
kernel/sched/core.c +4 -9
@@ -1484,20 +1484,14 @@ uclamp_eff_get(struct task_struct *p, enum uclamp_id clamp_id)return uc_req; } -unsigned long uclamp_eff_value (struct task_struct *p,enum uclamp_id clamp_id) -{ -if (!uclamp_is_used () || !p->uclamp[clamp_id].active) -return uclamp_none (clamp_id); - -return p->uclamp[clamp_id].value; -} -void uclamp_update_active_nolock (struct task_struct *p) {enum uclamp_id clamp_id; -for_each_clamp_id (clamp_id) +for_each_clamp_id (clamp_id) { p->uclamp[clamp_id] =uclamp_eff_get (p, clamp_id); + p->uclamp[clamp_id].active =1 ; + } } static inline void
@@ -1652,6 +1646,7 @@ static void uclamp_fork(struct task_struct *p)for_each_clamp_id (clamp_id) {uclamp_se_set (&p->uclamp_req[clamp_id],uclamp_none (clamp_id), false); + p->uclamp[clamp_id].active =0 ; } }
kernel/sched/sched.h +9 -1
@@ -3052,7 +3052,6 @@ static inline unsigned long cpu_util_rt(struct rq *rq)#ifdef CONFIG_UCLAMP_TASK -unsigned long uclamp_eff_value (struct task_struct *p,enum uclamp_id clamp_id);void uclamp_update_active_nolock (struct task_struct *p);/*
@@ -3081,6 +3080,15 @@ static inline unsigned int uclamp_none(enum uclamp_id clamp_id)return SCHED_CAPACITY_SCALE ; } +static inline unsigned long +uclamp_eff_value (struct task_struct *p,enum uclamp_id clamp_id) +{ +if (uclamp_is_used () && p->uclamp[clamp_id].active) +return p->uclamp[clamp_id].value; + +return uclamp_none (clamp_id); +} +static inline void uclamp_se_set (struct uclamp_se *uc_se,unsigned int value,bool user_defined) {
Signature · 1 line
2.34.1
PATCH 7/7 Propagate negative bias
In reply to Hongyan XiaNegative bias is interesting, because dequeuing such a task will actually increase utilization.
Solve by applying PELT decay to negative biases as well. This in fact can be implemented easily with some math tricks.
--- kernel/sched/fair.c | 40 ++++++++++++++++++++++++++++++++++++++++ kernel/sched/sched.h | 4 ++++ 2 files changed, 44 insertions(+)
kernel/sched/fair.c +40 -0
@@ -4878,6 +4878,45 @@ static inline unsigned long root_cfs_util_uclamp(struct rq *rq) return max(ret, 0L); } + +/* +* Negative biases are tricky. If we remove them right away then dequeuing a +* uclamp_max task has the interesting effect that dequeuing results in a higher +* rq utilization. Solve this by applying PELT decay to the bias itself. +* +* Keeping track of a PELT-decayed negative bias is extra overhead. However, we +* observe this interesting math property, where y is the decay factor and p is +* the number of periods elapsed: +* +* util_new = util_old * y^p - neg_bias * y^p +* = (util_old - neg_bias) * y^p +* +* Therefore, we simply subtract the negative bias from util_avg the moment we +* dequeue, then the PELT signal itself is the total of util_avg and the decayed +* negative bias, and we no longer need to track the decayed bias separately. +*/ +static void propagate_negative_bias (struct task_struct *p) +{ +if (task_util_bias (p) <0 && !task_on_rq_migrating (p)) { +unsigned long neg_bias = -task_util_bias (p); +struct sched_entity *se = &p->se; +struct cfs_rq *cfs_rq; + + p->se.avg.util_avg_bias =0 ; + +for_each_sched_entity (se) { +u32 divider, neg_sum; + + cfs_rq =cfs_rq_of (se); + divider =get_pelt_divider (&cfs_rq->avg); + neg_sum = neg_bias * divider; +sub_positive (&se->avg.util_avg, neg_bias); +sub_positive (&se->avg.util_sum, neg_sum); +sub_positive (&cfs_rq->avg.util_avg, neg_bias); +sub_positive (&cfs_rq->avg.util_sum, neg_sum); + } + } +}#else static inline long task_util_bias (struct task_struct *p) {
@@ -6869,6 +6908,7 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)/* At this point se is NULL and we are at root level*/ sub_nr_running (rq,1 );util_bias_dequeue (rq, p); +propagate_negative_bias (p);/* balance early to pull high priority tasks */ if (unlikely (!was_sched_idle &&sched_idle_rq (rq)))
kernel/sched/sched.h +4 -0
@@ -3140,6 +3140,10 @@ static inline void util_bias_dequeue(struct rq *rq, struct task_struct *p) { } +static inline void propagate_negative_bias (struct task_struct *p) +{ +} +#endif /* !CONFIG_UCLAMP_TASK */ #ifdef CONFIG_HAVE_SCHED_AVG_IRQ
Signature · 1 line
2.34.1
K Prateek Nayak
reviewerRe: [PATCH 7/7] Propagate negative bias
Hello Hongyan,
Quoted 44 lines · Hongyan Xia
Negative bias is interesting, because dequeuing such a task will actually increase utilization.
Solve by applying PELT decay to negative biases as well. This in fact can be implemented easily with some math tricks.
Signed-off-by Hongyan Xia <[email protected]>--- kernel/sched/fair.c | 40 ++++++++++++++++++++++++++++++++++++++++ kernel/sched/sched.h | 4 ++++ 2 files changed, 44 insertions(+)kernel/sched/fair.c +24
-0@@ -4878,6 +4878,45 @@ static inline unsigned long root_cfs_util_uclamp(struct rq *rq)return max (ret,0L ); } + +/* +* Negative biases are tricky. If we remove them right away then dequeuing a +* uclamp_max task has the interesting effect that dequeuing results in a higher +* rq utilization. Solve this by applying PELT decay to the bias itself. +* +* Keeping track of a PELT-decayed negative bias is extra overhead. However, we +* observe this interesting math property, where y is the decay factor and p is +* the number of periods elapsed: +* +* util_new = util_old * y^p - neg_bias * y^p +* = (util_old - neg_bias) * y^p +* +* Therefore, we simply subtract the negative bias from util_avg the moment we +* dequeue, then the PELT signal itself is the total of util_avg and the decayed +* negative bias, and we no longer need to track the decayed bias separately. +*/ +static void propagate_negative_bias (struct task_struct *p) +{ +if (task_util_bias (p) <0 && !task_on_rq_migrating (p)) { +unsigned long neg_bias = -task_util_bias (p); +struct sched_entity *se = &p->se; +struct cfs_rq *cfs_rq; +
kernel/sched/fair.c static inline unsigned long root_cfs_util_uclamp(struct rq *rq) · line 4914
Quoted 10 lines
kernel/sched/fair.c +10
-0+ p->se.avg.util_avg_bias =0 ; + +for_each_sched_entity (se) { +u32 divider, neg_sum; + + cfs_rq =cfs_rq_of (se); + divider =get_pelt_divider (&cfs_rq->avg); + neg_sum = neg_bias * divider; +sub_positive (&se->avg.util_avg, neg_bias); +sub_positive (&se->avg.util_sum, neg_sum);
Most cases where I've seen "get_pelt_divider()" followed by "add_positive()" or "sub_positive()" on "util_avg" and "util_sum" I've seen a correction step that does:
util_sum = max_t(u32, util_sum, util_avg * PELT_MIN_DIVIDER)
There is a comment on its significance in "update_cfs_rq_load_avg()". Would it also apply in this case?
kernel/sched/fair.c static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags) · line 6911
Quoted 13 lines
kernel/sched/fair.c +6
-0+sub_positive (&cfs_rq->avg.util_avg, neg_bias); + sub_positive(&cfs_rq->avg.util_sum, neg_sum); + } + } +}#else static inline long task_util_bias (struct task_struct *p) {@@ -6869,6 +6908,7 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)/* At this point se is NULL and we are at root level*/ sub_nr_running (rq,1 );util_bias_dequeue (rq, p); +propagate_negative_bias (p);
Perhaps I'm pointing to a premature optimization but since the hierarchy is traversed above in "dequeue_task_fair()", could the "neg_bias" and "neg_sum" removal be done along the way above instead of "propagate_negative_bias()" traversing the hierarchy again? I don't see a dependency on "util_bias_dequeue()" (which modifies "rq->cfs.avg.util_avg_bias") for "propagate_negative_bias()" (which works purely with task_util_bias() or "p->se.avg.util_avg_bias") but if I'm missing something please do let me know.
Since you mentioned this patch isn't strictly necessary in the cover letter, I would wait for other folks to chime in before changing this :)
Quoted 4 lines
kernel/sched/fair.c +0
-0/* balance early to pull high priority tasks */ if (unlikely (!was_sched_idle &&sched_idle_rq (rq)))
Signature · 2 lines
Thanks and Regards, Prateek
Re: [PATCH 7/7] Propagate negative bias
Hi,
Thanks for taking a look!
Quoted 69 lines · K Prateek Nayak
Hello Hongyan,
Quoted 51 lines · Hongyan Xia
Negative bias is interesting, because dequeuing such a task will actually increase utilization.
Solve by applying PELT decay to negative biases as well. This in fact can be implemented easily with some math tricks.
Signed-off-by Hongyan Xia <[email protected]>---
kernel/sched/fair.c | 40 ++++++++++++++++++++++++++++++++++++++++kernel/sched/sched.h| 4 ++++2 files changed, 44 insertions(+)kernel/sched/fair.c +3
-0@@ -4878,6 +4878,45 @@ static inline unsigned long root_cfs_util_uclamp(struct rq *rq) return max(ret, 0L); } + +/* +* Negative biases are tricky. If we remove them right away then dequeuing a
+ *uclamp_maxtask has the interesting effect that dequeuing results in a higher
+ * rq utilization. Solve this by applying PELT decay to the bias itself.
+ *
+ * Keeping track of a PELT-decayed negative bias is extra overhead. However, we
+ * observe this interesting math property, where y is the decay factor and p is
+ * the number of periods elapsed:
+ *
+ *util_new=util_old* y^p -neg_bias* y^p
+ * = (util_old-neg_bias) * y^p
+ *
+ * Therefore, we simply subtract the negative bias fromutil_avgthe moment we
+ * dequeue, then the PELT signal itself is the total ofutil_avgand the decayed
+ * negative bias, and we no longer need to track the decayed bias separately.
+ */kernel/sched/fair.c +7
-0+static void propagate_negative_bias (struct task_struct *p) +{ + if (task_util_bias(p) < 0 && !task_on_rq_migrating(p)) { + unsigned long neg_bias = -task_util_bias(p); + struct sched_entity *se = &p->se; + struct cfs_rq *cfs_rq; +kernel/sched/fair.c static inline unsigned long root_cfs_util_uclamp(struct rq *rq) · line 4914
Quoted 10 lines
kernel/sched/fair.c +10
-0+ p->se.avg.util_avg_bias = 0; + + for_each_sched_entity(se) { + u32 divider, neg_sum; + + cfs_rq = cfs_rq_of(se); + divider = get_pelt_divider(&cfs_rq->avg); + neg_sum = neg_bias * divider; + sub_positive(&se->avg.util_avg, neg_bias); + sub_positive(&se->avg.util_sum, neg_sum);Most cases where I've seen "
get_pelt_divider()" followed by "add_positive()" or "sub_positive()" on "util_avg" and "util_sum" I've seen a correction step that does:
Quoted 5 lines
util_sum =
max_t(u32, util_sum, util_avg * PELT_MIN_DIVIDER)There is a comment on its significance in "
update_cfs_rq_load_avg()". Would it also apply in this case?
That's a good point. The problem in update_cfs_rq_load_avg() should also be possible here. I can add the guard logic in the next rev.
But if we change the code in a way suggested below, then this problem is solved anyway.
Quoted 24 lines
Quoted 9 lines
+
sub_positive(&cfs_rq->avg.util_avg, neg_bias); +sub_positive(&cfs_rq->avg.util_sum, neg_sum); + }
+ }
+}
#else
static inline longtask_util_bias(struct task_struct *p){kernel/sched/fair.c static void dequeue_task_fair(struct rq *rq, · line 6912
Quoted 5 lines
kernel/sched/fair.c +1
-0@@ -6869,6 +6908,7 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags) /* At this point se is NULL and we are at root level*/ sub_nr_running(rq, 1); util_bias_dequeue(rq, p); + propagate_negative_bias(p);Perhaps I'm pointing to a premature optimization but since the hierarchy is traversed above in "
dequeue_task_fair()", could the "neg_bias" and "neg_sum" removal be done along the way above instead of "propagate_negative_bias()" traversing the hierarchy again? I don't see a dependency on "util_bias_dequeue()" (which modifies "rq->cfs.avg.util_avg_bias") for "propagate_negative_bias()" (which works purely withtask_util_bias()or "p->se.avg.util_avg_bias") but if I'm missing something please do let me know.
Quoted 2 lines
Since you mentioned this patch isn't strictly necessary in the cover letter, I would wait for other folks to chime in before changing this :)
I've been thinking about similar things for both enqueue() and dequeue(). Currently this series makes util_avg_bias completely separate from util_avg to ease review, acting more like util_est, but like you said we do things twice in a couple of places.
enqueue_task_fair():
for_each_sched_entity()
enqueue_entity()
if root_cfs()
cpufreq_update_util()
util_bias_enqueue(p) cpufreq_update_util() // duplicate cpufreq update
dequeue_task_fair():
for_each_sched_entity()
dequeue_entity()
if root_cfs()
cpufreq_update_util()
util_bias_dequeue(p) propagate_negative_bias() // duplicate tree traversal cpufreq_update_util() // duplicate cpufreq update
But we can integrate the bias closer into the hierarchy, like this:
enqueue_task_fair():
for_each_sched_entity() enqueue_entity() if (entity_is_task()) util_bias_enqueue(p) if root_cfs() // No duplicate cpufreq updates cpufreq_update_util()
dequeue_task_fair():
for_each_sched_entity() dequeue_entity() if (entity_is_task()) util_bias_dequeue(p) // No need to traverse twice. propagate_negative_bias(p) if root_cfs() // No duplicate cpufreq updates cpufreq_update_util()
This new structure will address both of your concerns.
Quoted 4 lines
Quoted 3 lines
kernel/sched/fair.c +0
-0/* balance early to pull high priority tasks */ if (unlikely(!was_sched_idle && sched_idle_rq(rq)))