sched: uclamp sum aggregation

From: Hongyan Xia <[email protected]>

kernel/sched/fair.c +13 -0

+static void update_se_chain(struct task_struct *p)
+{
+#ifdef CONFIG_UCLAMP_TASK
+	struct sched_entity *se = &p->se;
+	struct rq *rq = task_rq(p);
+
+	for_each_sched_entity(se) {
+		struct cfs_rq *cfs_rq = cfs_rq_of(se);
+
+		___update_util_avg_uclamp(&cfs_rq->avg, se);
+	}
+#endif
+}
 /*
  * The enqueue_task method is called before nr_running is
  * increased. Here we update the fair scheduling stats and

@@ -6511,6 +6531,16 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 			goto enqueue_throttle;
 	}

Quoted 1 line · Hongyan Xia

From: Hongyan Xia <[email protected]>

[...]

Quoted 4 lines

(quoted diff) +0 -0

@@ -6445,6 +6450,21 @@ static int sched_idle_cpu(int cpu)
  }
  #endif
 

kernel/sched/fair.c static int sched_idle_cpu(int cpu) · line 6453

Quoted 1 line

kernel/sched/fair.c +1 -0

+void ___update_util_avg_uclamp(struct sched_avg *avg, struct sched_entity *se);

IMHO, struct sched_avg *avg can only be the one of a cfs_rq. So passing a cfs_rq would eliminate the question whether this can be from another se.

Quoted 19 lines

kernel/sched/fair.c +13 -0

+static void update_se_chain(struct task_struct *p)
+{
+#ifdef CONFIG_UCLAMP_TASK
+	struct sched_entity *se = &p->se;
+	struct rq *rq = task_rq(p);
+
+	for_each_sched_entity(se) {
+		struct cfs_rq *cfs_rq = cfs_rq_of(se);
+
+		___update_util_avg_uclamp(&cfs_rq->avg, se);
+	}
+#endif
+}
  /*
   * The enqueue_task method is called before nr_running is
   * increased. Here we update the fair scheduling stats and

@@ -6511,6 +6531,16 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
  			goto enqueue_throttle;
  	}

kernel/sched/fair.c enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) · line 6542

Quoted 10 lines

kernel/sched/fair.c +9 -0

 
+	/*
+	 * Re-evaluate the se hierarchy now that on_rq is true. This is
+	 * important to enforce uclamp the moment a task with uclamp is
+	 * enqueued, rather than waiting a timer tick for uclamp to kick in.
+	 *
+	 * XXX: This duplicates some of the work already done in the above for
+	 * loops.
+	 */
+	update_se_chain(p);

I try to figure out why this is necessary here:

enqueue_task_fair()
for_each_sched_entity()

     enqueue_entity()
       update_load_avg()
         __update_load_avg_se()
           ___update_util_avg_uclamp()        <-- if se->on_rq,
                                                  update p (se) if we
                                                  cross PELT period (1)
                                                  boundaries
           ___decay_util_avg_uclamp_towards() <-- decay p (se)      (2)

       enqueue_util_avg_uclamp()          <-- enqueue p into cfs_rq (3)

       se->on_rq = 1                          <-- set p (se) on_rq  (4)

for_each_sched_entity()
update_load_avg() <-- update all on_rq se's
in the hierarchy (5)

update_se_chain() <-- update p (se) and its
se hierarchy (6)

(1) Skip p since it is !se->on_rq.

(2) Decay p->se->avg.util_avg_uclamp to 0 since it was sleeping.

(3) Attach p to its cfs_rq

...

(6) Update all all se's and cfs_rq's involved in p's task_group hierarchy (including propagation from se (level=x+1) to cfs_rq (level=x))

Question for me is why can't you integrate the util_avg_uclamp signals for se's and cfs_rq's/rq's much closer into existing PELT functions?

Quoted 5 lines · Dietmar Eggemann

Quoted 1 line · Hongyan Xia

From: Hongyan Xia <[email protected]>

[...]

Quoted 9 lines

Quoted 5 lines

(quoted diff) +0 -0

@@ -6445,6 +6450,21 @@ static int sched_idle_cpu(int cpu)
   }
   #endif

  +void ___update_util_avg_uclamp(struct sched_avg *avg, struct sched_entity *se);

IMHO, struct sched_avg *avg can only be the one of a cfs_rq. So passing a cfs_rq would eliminate the question whether this can be from another se.

At the moment, yes, the avg can only come from cfs_rq. The reason why I kept sched_avg is that once we have sum aggregation for RT tasks, it's very likely we will end up calling this function on rt_rq->avg, so having just sched_avg here will work for RT in the future.

Quoted 2 lines

Question for me is why can't you integrate the util_avg_uclamp signals for se's and cfs_rq's/rq's much closer into existing PELT functions?

So the problem is that when we enqueue the task (say UCLAMP_MIN of 200), at that exact moment se->on_rq is false, so we only decay and not enforce UCLAMP_MIN. Further up in the hierarchy we do update_load_avg(), but the se of the task has already been processed so UCLAMP_MIN has not taken any effect. To make sure UCLAMP_MIN is immediately effective, I just re-evaluate the whole hierarchy from bottom to top.

I probably didn't quite catch what you said here. Could you elaborate a bit on what 'much closer' means?

From: Hongyan Xia <[email protected]>

Track a uclamped version of util_avg in sched_avg, which clamps util_avg within [uclamp[UCLAMP_MIN], uclamp[UCLAMP_MAX]] every time util_avg is updated. At the CFS rq level, cfs_rq->avg.util_avg_uclamp must always be the sum of all util_avg_uclamp of entities on this cfs_rq. So, each time the util_avg_uclamp of an entity gets updated, we also track the delta and update the cfs_rq.

We can't put the update of cfs_rq util_avg_uclamp separately in propagate_entity_load_avg(), because util_avg_uclamp of se and cfs_rq are not tracked separately, unlike util_avg. As a result, util_avg_uclamp of the se and the cfs_rq the se is on must be updated at the same time.

Signed-off-by Hongyan Xia <[email protected]>

---
 include/linux/sched.h |  9 ++++++++-
 kernel/sched/fair.c   | 39 +++++++++++++++++++++++++++++++++++++++
 kernel/sched/pelt.c   | 43 +++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h  | 37 +++++++++++++++++++++++++++++++++++++
 4 files changed, 127 insertions(+), 1 deletion(-)

include/linux/sched.h +8 -1

index 177b3f3676ef..825d7b86b006 100644
@@ -499,7 +499,14 @@ struct sched_avg {
        u32                             period_contrib;
        unsigned long                   load_avg;
        unsigned long                   runnable_avg;
-       unsigned long                   util_avg;
+       unsigned int                    util_avg;
+#ifdef CONFIG_UCLAMP_TASK
+       /*
+        * XXX: util_avg shrunk to accommodate util_avg_uclamp.
+        * What are the consequences?
+        */
+       unsigned int                    util_avg_uclamp;
+#endif
        struct util_est                 util_est;
 } ____cacheline_aligned;
 

kernel/sched/fair.c +39 -0

index 0b7445cd5af9..33e5a6e751c0 100644
@@ -1077,6 +1077,9 @@ void post_init_entity_util_avg(struct task_struct *p)
        }
 
        sa->runnable_avg = sa->util_avg;
+#ifdef CONFIG_UCLAMP_TASK
+       sa->util_avg_uclamp = sa->util_avg;
+#endif
 }
 
 #else /* !CONFIG_SMP */

@@ -5068,6 +5071,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
        update_stats_enqueue_fair(cfs_rq, se, flags);
        if (!curr)
                __enqueue_entity(cfs_rq, se);
+       enqueue_util_avg_uclamp(cfs_rq, se);
        se->on_rq = 1;
 
        if (cfs_rq->nr_running == 1) {

@@ -5138,6 +5142,7 @@ dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
        update_entity_lag(cfs_rq, se);
        if (se != cfs_rq->curr)
                __dequeue_entity(cfs_rq, se);
+       dequeue_util_avg_uclamp(cfs_rq, se);
        se->on_rq = 0;
        account_entity_dequeue(cfs_rq, se);
 

@@ -6445,6 +6450,21 @@ static int sched_idle_cpu(int cpu)
 }
 #endif
 
+void ___update_util_avg_uclamp(struct sched_avg *avg, struct sched_entity *se);
+
+static void update_se_chain(struct task_struct *p)
+{
+#ifdef CONFIG_UCLAMP_TASK
+       struct sched_entity *se = &p->se;
+       struct rq *rq = task_rq(p);
+
+       for_each_sched_entity(se) {
+               struct cfs_rq *cfs_rq = cfs_rq_of(se);
+
+               ___update_util_avg_uclamp(&cfs_rq->avg, se);
+       }
+#endif
+}
 /*
  * The enqueue_task method is called before nr_running is
  * increased. Here we update the fair scheduling stats and

@@ -6511,6 +6531,16 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
                        goto enqueue_throttle;
        }
 
+       /*
+        * Re-evaluate the se hierarchy now that on_rq is true. This is
+        * important to enforce uclamp the moment a task with uclamp is
+        * enqueued, rather than waiting a timer tick for uclamp to kick in.
+        *
+        * XXX: This duplicates some of the work already done in the above for
+        * loops.
+        */
+       update_se_chain(p);
+
        /* At this point se is NULL and we are at root level*/
        add_nr_running(rq, 1);
 

@@ -6612,6 +6642,15 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 dequeue_throttle:
        util_est_update(&rq->cfs, p, task_sleep);
        hrtick_update(rq);
+
+#ifdef CONFIG_UCLAMP_TASK
+       if (rq->cfs.h_nr_running == 0) {
+               WARN_ONCE(rq->cfs.avg.util_avg_uclamp,
+                       "0 tasks on CFS of CPU %d, but util_avg_uclamp is %u\n",
+                       rq->cpu, rq->cfs.avg.util_avg_uclamp);
+               WRITE_ONCE(rq->cfs.avg.util_avg_uclamp, 0);
+       }
+#endif
 }
 
 #ifdef CONFIG_SMP

kernel/sched/pelt.c +43 -0

index 0f310768260c..c656e4dcb1d1 100644
@@ -266,6 +266,48 @@ ___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. */
+void ___update_util_avg_uclamp(struct sched_avg *avg, struct sched_entity *se)
+{
+       unsigned int util;
+       int delta;
+
+       if (entity_is_task(se)) {
+               unsigned int uclamp_min, uclamp_max;
+
+               if (!se->on_rq)
+                       return;
+
+               util = READ_ONCE(se->avg.util_avg);
+               uclamp_min = uclamp_eff_value(task_of(se), UCLAMP_MIN);
+               uclamp_max = uclamp_eff_value(task_of(se), UCLAMP_MAX);
+               util = clamp(util, uclamp_min, uclamp_max);
+       } else {
+               util = READ_ONCE(group_cfs_rq(se)->avg.util_avg_uclamp);
+
+               if (!se->on_rq) {
+                       WRITE_ONCE(se->avg.util_avg_uclamp, util);
+                       return;
+               }
+       }
+
+       delta = util - READ_ONCE(se->avg.util_avg_uclamp);
+       if (delta == 0)
+               return;
+
+       WRITE_ONCE(se->avg.util_avg_uclamp, util);
+       util = READ_ONCE(avg->util_avg_uclamp);
+       util += delta;
+       WRITE_ONCE(avg->util_avg_uclamp, util);
+}
+#else /* !CONFIG_UCLAMP_TASK */
+static void
+___update_util_avg_uclamp(struct sched_avg *avg, struct sched_entity *se)
+{
+}
+#endif
+
 /*
  * sched_entity:
  *

@@ -309,6 +351,7 @@ int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se
                                cfs_rq->curr == se)) {
 
                ___update_load_avg(&se->avg, se_weight(se));
+               ___update_util_avg_uclamp(&cfs_rq->avg, se);
                cfs_se_util_change(&se->avg);
                trace_pelt_se_tp(se);
                return 1;

kernel/sched/sched.h +37 -1

index 3a01b7a2bf66..2eefcdb0c3b0 100644
@@ -3133,6 +3133,33 @@ static inline bool uclamp_is_used(void)
 {
        return static_branch_likely(&sched_uclamp_used);
 }
+
+static inline void enqueue_util_avg_uclamp(struct cfs_rq *cfs_rq,
+                                          struct sched_entity *se)
+{
+       unsigned int cfs_val = READ_ONCE(cfs_rq->avg.util_avg_uclamp);
+       unsigned int se_val = READ_ONCE(se->avg.util_avg_uclamp);
+
+       WRITE_ONCE(cfs_rq->avg.util_avg_uclamp, cfs_val + se_val);
+}
+
+static inline void dequeue_util_avg_uclamp(struct cfs_rq *cfs_rq,
+                                          struct sched_entity *se)
+{
+       unsigned int cfs_val = READ_ONCE(cfs_rq->avg.util_avg_uclamp);
+       unsigned int se_val = READ_ONCE(se->avg.util_avg_uclamp), new_val;
+
+       if (cfs_val > se_val)
+               new_val = cfs_val - se_val;
+       else {
+               WARN_ONCE(cfs_val < se_val,
+                       "CPU %d. cfs_rq %p, cfs_val %u is even less than se_val %u before subtraction\n",
+                       rq_of(cfs_rq)->cpu, cfs_rq, cfs_val, se_val);
+               new_val = 0;
+       }
+
+       WRITE_ONCE(cfs_rq->avg.util_avg_uclamp, new_val);
+}
 #else /* CONFIG_UCLAMP_TASK */
 static inline unsigned long uclamp_eff_value(struct task_struct *p,
                                             enum uclamp_id clamp_id)

@@ -3175,6 +3202,16 @@ static inline bool uclamp_rq_is_idle(struct rq *rq)
 {
        return false;
 }
+
+static inline void enqueue_util_avg_uclamp(struct cfs_rq *cfs_rq,
+                                          struct sched_entity *se)
+{
+}
+
+static inline void dequeue_util_avg_uclamp(struct cfs_rq *cfs_rq,
+                                          struct sched_entity *se)
+{
+}
 #endif /* CONFIG_UCLAMP_TASK */
 
 #ifdef CONFIG_HAVE_SCHED_AVG_IRQ
--

2.34.1

Quoted 9 lines · Hongyan Xia

From: Hongyan Xia <[email protected]>

Track a uclamped version of util_avg in sched_avg, which clamps util_avg within [uclamp[UCLAMP_MIN], uclamp[UCLAMP_MAX]] every time util_avg is updated. At the CFS rq level, cfs_rq->avg.util_avg_uclamp must always be the sum of all util_avg_uclamp of entities on this cfs_rq. So, each time the util_avg_uclamp of an entity gets updated, we also track the delta and update the cfs_rq.

No please don't do that. Don't start to mix several different signals in one. Typically uclamp_min doen't say you want to use at least this amount of cpu capacity.

With tasks with a util_avg of 10 but a uclamp min of 1024 what does it mean when you start to sum this value ?

Quoted 3 lines

[...]

Quoted 11 lines · Vincent Guittot

Quoted 9 lines · Hongyan Xia

From: Hongyan Xia <[email protected]>

Track a uclamped version of util_avg in sched_avg, which clamps util_avg within [uclamp[UCLAMP_MIN], uclamp[UCLAMP_MAX]] every time util_avg is updated. At the CFS rq level, cfs_rq->avg.util_avg_uclamp must always be the sum of all util_avg_uclamp of entities on this cfs_rq. So, each time the util_avg_uclamp of an entity gets updated, we also track the delta and update the cfs_rq.

Quoted 3 lines

No please don't do that. Don't start to mix several different signals in one. Typically uclamp_min doen't say you want to use at least this amount of cpu capacity.

But I'd say with uclamp, PELT is already broken and is a mixed signal

anyway. When uclamp is used, a util_avg value X doesn't mean X, it means X under some rq uclamp, and the worst part is that the rq uclamp may or may not have anything to do with this task's uclamp.

Pretending X is a true PELT value now (and not a mixed value) is why we have so many problems today. For example in the frequency spike problem, if a task A has no idle time under uclamp_max, its PELT does not reflect reality. The moment another task B comes in and uncap the rq uclamp_max,

the current scheduler code thinks the 1024 of A means a real 1024, which is wrong and is exactly why we see a spike when B joins. It's also why

we need to special case 0 spare capacity with recent patches, because rq util_avg has lost its original PELT meaning under uclamp.

Because X is not the true PELT, we always have to do something to bring it back into reality. What the current max aggregation code does is to introduce corner cases, like treating 0 spare capacity as potential opportunity to queue more tasks (which creates further problems in my tests), and maybe introducing uclamp load balancing special cases in the future, or introducing uclamp filtering to delay the effect of wrong PELT values.

What this series does is not much different. We keep the somewhat wrong value X, but we also remember under what uclamp values did we get that X to bring things back into reality, which means now we have [X, uclamp_min when X happens, uclamp_max when X happens]. To save space, this becomes [X, clamped X], which is what this series does. The original PELT value X is kept, but we use the clamped X in several places to improve our decisions.

Quoted 1 line

Quoted 2 lines

With tasks with a util_avg of 10 but a uclamp min of 1024 what does it mean when you start to sum this value ?

Like I replied in another comment, assuming a uclamp_min of 1024 is a hint to run the task on the big CPUs, I don't think it's right to

directly use uclamp as a CPU placement indicator. A uclamp value may come from ADFP from userspace. An ADPF uclamp_min value of little CPU capacity + 1 certainly doesn't mean a game on purpose wants to avoid the little core. It simply means it wants at least this much performance, and whether this results in placing the game thread on a big CPU is purely the job of EAS (or CAS, etc.). We want to use little CPU + 1 as uclamp_min because we know the SoC and the little CPU is bad, but uclamp should be generic and should not rely on knowing the SoC.

Basically, under sum aggregation one would not use a uclamp_min value of 1024 to place a small task on a big core. A uclamp_min of 1024 under sum aggregation has the meaning in ADPF, which is a hint to try to run me as fast as possible.

Quoted 3 lines

Quoted 3 lines

[...]

From: Hongyan Xia <[email protected]>

Because util_avg_uclamp is not directly managed by PELT, it lacks the nice property of slowly decaying to a lower value, resulting in performance degredation due to premature frequency drops.

Add functions to decay root cfs utilization and tasks that are not on the rq. This way, we get the benefits of PELT while still maintaining uclamp. The rules are simple:

1. When task is se->on_rq, enforce its util_avg_uclamp within uclamp range.
2. When task is !se->on_rq, PELT decay its util_avg_uclamp.
3. When the root CFS util drops, PELT decay to the target frequency instead of immediately dropping to a lower target frequency.

TODO: Can we somehow integrate this uclamp sum aggregation directly into util_avg, so that we don't need to introduce a new util_avg_uclamp signal and don't need to simulate PELT decay?

Signed-off-by Hongyan Xia <[email protected]>

---
 kernel/sched/fair.c  |  20 +++++++++
 kernel/sched/pelt.c  | 103 ++++++++++++++++++++++++++++++++++++++++---
 kernel/sched/sched.h |   2 +
 3 files changed, 119 insertions(+), 6 deletions(-)

kernel/sched/fair.c +0 -0

index 33e5a6e751c0..420af57d01ee 100644

kernel/sched/fair.c +4 -0

 	struct sched_avg *sa = &cfs_rq->avg;
 	int decayed = 0;
 
 	if (cfs_rq->removed.nr) {
 		unsigned long r;
+		struct rq *rq = rq_of(cfs_rq);
 		u32 divider = get_pelt_divider(&cfs_rq->avg);
 
 		raw_spin_lock(&cfs_rq->removed.lock);
 		swap(cfs_rq->removed.util_avg, removed_util);
 		swap(cfs_rq->removed.load_avg, removed_load);
 		swap(cfs_rq->removed.runnable_avg, removed_runnable);
+#ifdef CONFIG_UCLAMP_TASK
+		swap(rq->root_cfs_util_uclamp_removed, removed_root_util);
+#endif
 		cfs_rq->removed.nr = 0;
 		raw_spin_unlock(&cfs_rq->removed.lock);
 

#ifdef CONFIG_UCLAMP_TASK

kernel/sched/fair.c +3 -0

+static void ___decay_util_avg_uclamp_towards(u64 now,
+					     u64 last_update_time,
+					     u32 period_contrib,

kernel/sched/fair.c +26 -0

+	if (!last_update_time)
+		return;
+	delta = now - last_update_time;
+	if ((s64)delta < 0)
+		return;
+	delta >>= 10;
+	if (!delta)
+		return;
+
+	delta += period_contrib;
+	periods = delta / 1024;
+	if (periods) {
+		u64 diff = old_val - new_val;
+
+		/*
+		 * Let's assume 3 tasks, A, B and C. A is still on rq but B and
+		 * C have just been dequeued. The cfs.avg.util_avg_uclamp has
+		 * become A but root_cfs_util_uclamp just starts to decay and is
+		 * now still A + B + C.
+		 *
+		 * After p periods with y being the decay factor, the new
+		 * root_cfs_util_uclamp should become
+		 *
+		 * A + B * y^p + C * y^p == A + (A + B + C - A) * y^p
+		 *     == cfs.avg.util_avg_uclamp +
+		 *        (root_cfs_util_uclamp_at_the_start - cfs.avg.util_avg_uclamp) * y^p

Quoted 16 lines · Hongyan Xia

From: Hongyan Xia <[email protected]>

Because util_avg_uclamp is not directly managed by PELT, it lacks the nice property of slowly decaying to a lower value, resulting in performance degredation due to premature frequency drops.

Add functions to decay root cfs utilization and tasks that are not on the rq. This way, we get the benefits of PELT while still maintaining uclamp. The rules are simple:

1. When task is se->on_rq, enforce its util_avg_uclamp within uclamp range.
2. When task is !se->on_rq, PELT decay its util_avg_uclamp.
3. When the root CFS util drops, PELT decay to the target frequency instead of immediately dropping to a lower target frequency.

Quoted 3 lines

TODO: Can we somehow integrate this uclamp sum aggregation directly into util_avg, so that we don't need to introduce a new util_avg_uclamp signal and don't need to simulate PELT decay?

That's a good question. I'm wondering why you were not able to integrate the maintenance of the util_avg_uclamp values inside the existing PELT update functionality in fair.c ((__update_load_avg_xxx(), propagate_entity_load_avg() -> update_tg_cfs_util() etc.)

Why do you need extra functions like ___decay_util_avg_uclamp_towards() and ___update_util_avg_uclamp() for this?

Quoted 12 lines

Signed-off-by Hongyan Xia <[email protected]>

---
  kernel/sched/fair.c  |  20 +++++++++
  kernel/sched/pelt.c  | 103 ++++++++++++++++++++++++++++++++++++++++---
  kernel/sched/sched.h |   2 +
  3 files changed, 119 insertions(+), 6 deletions(-)

kernel/sched/fair.c +0 -0

index 33e5a6e751c0..420af57d01ee 100644

kernel/sched/fair.c static inline int · line 4314

Quoted 4 lines

kernel/sched/fair.c +1 -0

@@ -4311,17 +4311,22 @@ static inline int
  update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
  {
  	unsigned long removed_load = 0, removed_util = 0, removed_runnable = 0;
+	unsigned int removed_root_util = 0;

  unsigned long removed_load = 0, removed_util = 0, removed_runnable = 0;

(quoted diff) +1 -1

-unsigned int removed_root_util = 0;
+unsigned int __maybe_unused removed_root_util = 0;

Otherwise you get warning: unused variable ‘rq’ w/ !CONFIG_UCLAMP_TASK

[...]

Quoted 9 lines

  #ifdef CONFIG_UCLAMP_TASK

kernel/sched/fair.c +8 -0

+static void ___decay_util_avg_uclamp_towards(u64 now,
+					     u64 last_update_time,
+					     u32 period_contrib,
+					     unsigned int *old,
+					     unsigned int new_val)
+{
+	unsigned int old_val = READ_ONCE(*old);
+	u64 delta, periods;

kernel/sched/fair.c

Quoted 5 lines

kernel/sched/fair.c +5 -0

+
+	if (old_val <= new_val) {
+		WRITE_ONCE(*old, new_val);
+		return;
+	}

Why is the function called decay? In case new >= old you set old = new and bail out. So it's also more like an update function?

Quoted 26 lines

kernel/sched/fair.c +26 -0

+	if (!last_update_time)
+		return;
+	delta = now - last_update_time;
+	if ((s64)delta < 0)
+		return;
+	delta >>= 10;
+	if (!delta)
+		return;
+
+	delta += period_contrib;
+	periods = delta / 1024;
+	if (periods) {
+		u64 diff = old_val - new_val;
+
+		/*
+		 * Let's assume 3 tasks, A, B and C. A is still on rq but B and
+		 * C have just been dequeued. The cfs.avg.util_avg_uclamp has
+		 * become A but root_cfs_util_uclamp just starts to decay and is
+		 * now still A + B + C.
+		 *
+		 * After p periods with y being the decay factor, the new
+		 * root_cfs_util_uclamp should become
+		 *
+		 * A + B * y^p + C * y^p == A + (A + B + C - A) * y^p
+		 *     == cfs.avg.util_avg_uclamp +
+		 *        (root_cfs_util_uclamp_at_the_start - cfs.avg.util_avg_uclamp) * y^p

kernel/sched/fair.c

Quoted 10 lines

kernel/sched/fair.c +10 -0

+		 *     == cfs.avg.util_avg_uclamp + diff * y^p
+		 *
+		 * So, instead of summing up each individual decayed values, we
+		 * could just decay the diff and not bother with the summation
+		 * at all. This is why we decay the diff here.
+		 */
+		diff = decay_load(diff, periods);
+		WRITE_ONCE(*old, new_val + diff);
+	}
+}

Looks like ___decay_util_avg_uclamp_towards() is used for:

(1) tasks with !se->on_rq to decay before enqueue

(2) rq->root_cfs_util_uclamp to align with

     &rq_of(cfs_rq)->cfs->avg.util_avg_uclamp

All the cfs_rq's and the taskgroup se's seem to be updated only in ___update_util_avg_uclamp() (which also handles the propagation towards the root taskgroup).

[...]

From: Hongyan Xia <[email protected]>

Because util_avg_uclamp is not directly managed by PELT, it lacks the nice property of slowly decaying to a lower value, resulting in performance degredation due to premature frequency drops.

Add functions to decay root cfs utilization and tasks that are not on the rq. This way, we get the benefits of PELT while still maintaining uclamp. The rules are simple:

1. When task is se->on_rq, enforce its util_avg_uclamp within uclamp range.
2. When task is !se->on_rq, PELT decay its util_avg_uclamp.
3. When the root CFS util drops, PELT decay to the target frequency instead of immediately dropping to a lower target frequency.

TODO: Can we somehow integrate this uclamp sum aggregation directly into util_avg, so that we don't need to introduce a new util_avg_uclamp signal and don't need to simulate PELT decay?

Signed-off-by Hongyan Xia <[email protected]>

---
 kernel/sched/fair.c  |  20 +++++++++
 kernel/sched/pelt.c  | 103 ++++++++++++++++++++++++++++++++++++++++---
 kernel/sched/sched.h |   2 +
 3 files changed, 119 insertions(+), 6 deletions(-)

kernel/sched/fair.c +20 -0

index 33e5a6e751c0..420af57d01ee 100644
@@ -4311,17 +4311,22 @@ static inline int
 update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
 {
        unsigned long removed_load = 0, removed_util = 0, removed_runnable = 0;
+       unsigned int removed_root_util = 0;
        struct sched_avg *sa = &cfs_rq->avg;
        int decayed = 0;
 
        if (cfs_rq->removed.nr) {
                unsigned long r;
+               struct rq *rq = rq_of(cfs_rq);
                u32 divider = get_pelt_divider(&cfs_rq->avg);
 
                raw_spin_lock(&cfs_rq->removed.lock);
                swap(cfs_rq->removed.util_avg, removed_util);
                swap(cfs_rq->removed.load_avg, removed_load);
                swap(cfs_rq->removed.runnable_avg, removed_runnable);
+#ifdef CONFIG_UCLAMP_TASK
+               swap(rq->root_cfs_util_uclamp_removed, removed_root_util);
+#endif
                cfs_rq->removed.nr = 0;
                raw_spin_unlock(&cfs_rq->removed.lock);
 

@@ -4346,6 +4351,12 @@ update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
                 *    util_avg * minimum possible divider
                 */
                sa->util_sum = max_t(u32, sa->util_sum, sa->util_avg * PELT_MIN_DIVIDER);
+#ifdef CONFIG_UCLAMP_TASK
+               r = removed_root_util;
+               sub_positive(&rq->root_cfs_util_uclamp, r);
+               rq->root_cfs_util_uclamp =
+                       max(rq->root_cfs_util_uclamp, rq->cfs.avg.util_avg_uclamp);
+#endif
 
                r = removed_runnable;
                sub_positive(&sa->runnable_avg, r);

@@ -4527,6 +4538,7 @@ static void sync_entity_load_avg(struct sched_entity *se)
 static void remove_entity_load_avg(struct sched_entity *se)
 {
        struct cfs_rq *cfs_rq = cfs_rq_of(se);
+       struct rq *rq = rq_of(cfs_rq);
        unsigned long flags;
 
        /*

@@ -4542,6 +4554,9 @@ static void remove_entity_load_avg(struct sched_entity *se)
        cfs_rq->removed.util_avg        += se->avg.util_avg;
        cfs_rq->removed.load_avg        += se->avg.load_avg;
        cfs_rq->removed.runnable_avg    += se->avg.runnable_avg;
+#ifdef CONFIG_UCLAMP_TASK
+       rq->root_cfs_util_uclamp_removed += se->avg.util_avg_uclamp;
+#endif
        raw_spin_unlock_irqrestore(&cfs_rq->removed.lock, flags);
 }
 

@@ -6462,6 +6477,11 @@ static void update_se_chain(struct task_struct *p)
                struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
                ___update_util_avg_uclamp(&cfs_rq->avg, se);
+               if (&rq->cfs == cfs_rq) {
+                       rq->root_cfs_util_uclamp = max(rq->root_cfs_util_uclamp,
+                                                      cfs_rq->avg.util_avg_uclamp);
+                       cfs_rq_util_change(cfs_rq, 0);
+               }
        }
 #endif
 }

kernel/sched/pelt.c +97 -6

index c656e4dcb1d1..83d5ac7e7ddb 100644
@@ -267,6 +267,57 @@ ___update_load_avg(struct sched_avg *sa, unsigned long load)
 }
 
 #ifdef CONFIG_UCLAMP_TASK
+static void ___decay_util_avg_uclamp_towards(u64 now,
+                                            u64 last_update_time,
+                                            u32 period_contrib,
+                                            unsigned int *old,
+                                            unsigned int new_val)
+{
+       unsigned int old_val = READ_ONCE(*old);
+       u64 delta, periods;
+
+       if (old_val <= new_val) {
+               WRITE_ONCE(*old, new_val);
+               return;
+       }
+
+       if (!last_update_time)
+               return;
+       delta = now - last_update_time;
+       if ((s64)delta < 0)
+               return;
+       delta >>= 10;
+       if (!delta)
+               return;
+
+       delta += period_contrib;
+       periods = delta / 1024;
+       if (periods) {
+               u64 diff = old_val - new_val;
+
+               /*
+                * Let's assume 3 tasks, A, B and C. A is still on rq but B and
+                * C have just been dequeued. The cfs.avg.util_avg_uclamp has
+                * become A but root_cfs_util_uclamp just starts to decay and is
+                * now still A + B + C.
+                *
+                * After p periods with y being the decay factor, the new
+                * root_cfs_util_uclamp should become
+                *
+                * A + B * y^p + C * y^p == A + (A + B + C - A) * y^p
+                *     == cfs.avg.util_avg_uclamp +
+                *        (root_cfs_util_uclamp_at_the_start - cfs.avg.util_avg_uclamp) * y^p
+                *     == cfs.avg.util_avg_uclamp + diff * y^p
+                *
+                * So, instead of summing up each individual decayed values, we
+                * could just decay the diff and not bother with the summation
+                * at all. This is why we decay the diff here.
+                */
+               diff = decay_load(diff, periods);
+               WRITE_ONCE(*old, new_val + diff);
+       }
+}
+
 /* avg must belong to the queue this se is on. */
 void ___update_util_avg_uclamp(struct sched_avg *avg, struct sched_entity *se)
 {

@@ -336,17 +387,33 @@ ___update_util_avg_uclamp(struct sched_avg *avg, struct sched_entity *se)
 
 int __update_load_avg_blocked_se(u64 now, struct sched_entity *se)
 {
+       u64 last_update_time = se->avg.last_update_time;
+       u32 period_contrib = se->avg.period_contrib;
+       int ret = 0;
+
        if (___update_load_sum(now, &se->avg, 0, 0, 0)) {
                ___update_load_avg(&se->avg, se_weight(se));
                trace_pelt_se_tp(se);
-               return 1;
+               ret = 1;
        }
 
-       return 0;
+#ifdef CONFIG_UCLAMP_TASK
+       if (entity_is_task(se))
+               ___decay_util_avg_uclamp_towards(now,
+                                                last_update_time,
+                                                period_contrib,
+                                                &se->avg.util_avg_uclamp,
+                                                0);
+#endif
+       return ret;
 }
 
 int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
+       u64 last_update_time = se->avg.last_update_time;
+       u32 period_contrib = se->avg.period_contrib;
+       int ret = 0;
+
        if (___update_load_sum(now, &se->avg, !!se->on_rq, se_runnable(se),
                                cfs_rq->curr == se)) {
 

@@ -354,14 +421,26 @@ int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se
                ___update_util_avg_uclamp(&cfs_rq->avg, se);
                cfs_se_util_change(&se->avg);
                trace_pelt_se_tp(se);
-               return 1;
+               ret = 1;
        }
 
-       return 0;
+#ifdef CONFIG_UCLAMP_TASK
+       if (!se->on_rq && entity_is_task(se))
+               ___decay_util_avg_uclamp_towards(now,
+                                                last_update_time,
+                                                period_contrib,
+                                                &se->avg.util_avg_uclamp,
+                                                0);
+#endif
+       return ret;
 }
 
 int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq)
 {
+       u64 last_update_time = cfs_rq->avg.last_update_time;
+       u32 period_contrib = cfs_rq->avg.period_contrib;
+       int ret = 0;
+
        if (___update_load_sum(now, &cfs_rq->avg,
                                scale_load_down(cfs_rq->load.weight),
                                cfs_rq->h_nr_running,

@@ -369,10 +448,22 @@ int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq)
 
                ___update_load_avg(&cfs_rq->avg, 1);
                trace_pelt_cfs_tp(cfs_rq);
-               return 1;
+               ret = 1;
        }
 
-       return 0;
+#ifdef CONFIG_UCLAMP_TASK
+       if (&rq_of(cfs_rq)->cfs == cfs_rq) {
+               unsigned int target = READ_ONCE(cfs_rq->avg.util_avg_uclamp);
+
+               ___decay_util_avg_uclamp_towards(now,
+                               last_update_time,
+                               period_contrib,
+                               &rq_of(cfs_rq)->root_cfs_util_uclamp,
+                               target);
+       }
+#endif
+
+       return ret;
 }
 
 /*

kernel/sched/sched.h +2 -1

index 2eefcdb0c3b0..98fa5e79f4e9 100644
@@ -992,6 +992,8 @@ struct rq {
        /* Utilization clamp values based on CPU's RUNNABLE tasks */
        struct uclamp_rq        uclamp[UCLAMP_CNT] ____cacheline_aligned;
        unsigned int            uclamp_flags;
+       unsigned int            root_cfs_util_uclamp;
+       unsigned int            root_cfs_util_uclamp_removed;
 #define UCLAMP_FLAG_IDLE 0x01
 #endif
 
--

2.34.1

Quoted 6 lines · Hongyan Xia

From: Hongyan Xia <[email protected]>

Because util_avg_uclamp is not directly managed by PELT, it lacks the nice property of slowly decaying to a lower value, resulting in performance degredation due to premature frequency drops.

That a very good reason for not doing this

Quoted 4 lines

Add functions to decay root cfs utilization and tasks that are not on the rq. This way, we get the benefits of PELT while still maintaining uclamp. The rules are simple:

Nack. This just highlights that you are mixing different things and then trying to make it work.

Please keep PELT out of uclamp_min/max

From: Hongyan Xia <[email protected]>

Switch to the new util_avg_uclamp for task and runqueue utilization. Since util_est() calls task_util(), this means util_est is now also a clamped value.

Now that we have the 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 root_cfs_util_uclamp to know what frequency to choose. Because we simulate PELT decay in root_cfs_util_uclamp anyway, there's no need in cpufreq_schedutil.c to avoid premature frequency drops.

Consequently, there is no need for uclamp_rq_util_with(). This function takes the un-clamped util value and sends it through various clamping filters to get the final value. However, util_avg_uclamp is propagated with clamping in mind already, so it does not need to be clamped again.

TODO: There are two major caveats in this patch.
1. At the moment sum aggregation does not consider RT tasks. The avg_rt signal considers all RT tasks on this rq as a single entity, which means the utilization of individual RT tasks is not tracked separately. If we want to use sum aggregation, we might have to track utilization of RT tasks individually.

2. Busy time accounting in compute_energy() now takes the uclamp'ed value. Ideally, it should reflect reality and use the un-clamp'ed values. However, that would require maintaining both the normal and uclamp'ed values for util_est. This needs to be revisited if it causes real problems in practice.

kernel/sched/core.c +0 -0

index efe3848978a0..32511ee63f01 100644
@@ -7402,10 +7402,12 @@ int sched_core_idle_cpu(int cpu)
  * The DL bandwidth number otoh is not a measured metric but a value computed

kernel/sched/core.c +1 -2

@@ -7468,11 +7459,13 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
 static unsigned long
 cpu_util(int cpu, struct task_struct *p, int dst_cpu, int boost)
 {
-	struct cfs_rq *cfs_rq = &cpu_rq(cpu)->cfs;
-	unsigned long util = READ_ONCE(cfs_rq->avg.util_avg);
+	struct rq *rq = cpu_rq(cpu);

From: Hongyan Xia <[email protected]>

Currently, there's no way to distinguish the difference between 1) a CPU that is actually maxed out at its highest frequency, or 2) one that is throttled because of UCLAMP_MAX, since both present util_avg values of 1024. This is problematic because when we try to pick a CPU for a task to run, we would like to give 2) a chance, or at least prefer 2) to 1).

Current upstream gives neither a chance because the spare capacity is 0 for either case. There are patches to fix this problem by considering 0 capacities [1], but this might still be inefficient because this ends up treating 1) and 2) equally, and will always pick the same one because we don't change how we iterate through all CPUs. If we end up putting many tasks on 1), then this creates a seriously unbalanced load for the two CPUs.

Fix by using util_avg_uclamp for util_fits_cpu(). This way, case 1) will still keep its utilization at 1024 whereas 2) shows spare capacities if the sum of util_avg_uclamp values is still under the CPU capacity. Note that this is roughly what the sum aggregation does in the Android kernel [2] (although we clamp UCLAMP_MIN as well in this patch, which may need some discussions), which shows superior energy savings because there's more chance that a task can get scheduled on 2) instead of finding a big CPU to run on.

Under sum aggregation, checking whether a task fits a CPU becomes much simpler. We simply do fits_capacity() and there does not need to be code checking all corner cases for uclamp. This means util_fits_cpu() returns to true and false instead of tri-state, simplifying a significant amount of code.

From: Hongyan Xia <[email protected]>

Also 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.

kernel/sched/core.c +0 -10

@@ -1542,196 +1485,24 @@ uclamp_eff_get(struct task_struct *p, enum uclamp_id clamp_id)
 
 unsigned long uclamp_eff_value(struct task_struct *p, enum uclamp_id clamp_id)
 {
-	struct uclamp_se uc_eff;
-
-	/* Task currently refcounted: use back-annotated (effective) value */
-	if (p->uclamp[clamp_id].active)
-		return (unsigned long)p->uclamp[clamp_id].value;
-
-	uc_eff = uclamp_eff_get(p, clamp_id);
-
-	return (unsigned long)uc_eff.value;
-}

Quoted 5 lines · Hongyan Xia

From: Hongyan Xia <[email protected]>

Also 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.

Tested it with

# cgcreate -g cpu:/A
# echo $$ > /sys/fs/cgroup/cpu/A/tasks

(1) per-task

# uclampset --pid $$  -m 256 -M 768

(2) per taskgroup

# echo 25.0 > /sys/fs/cgroup/cpu/A/cpu.uclamp.min
# echo 75.0 > /sys/fs/cgroup/cpu/A/cpu.uclamp.max

(3) system-wide

# echo 256 > /proc/sys/kernel/sched_util_clamp_min
# echo 768 > /proc/sys/kernel/sched_util_clamp_max

uclamp_update_active() -> uclamp_update_active_nolock() is called in all cases.

uclamp_eff_get()'s function header still mentions clamp bucket index.

Quoted 1 line

[...]

[...]

From: Hongyan Xia <[email protected]>

The commit

sched: Remove all uclamp bucket logic

removes uclamp_{inc/dec}() functions, so now p->uclamp contains the

correct values all the time after a update_uclamp_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.

Current implementation of uclamp leaves many things to be desired. There are several problems:

1. Max aggregation is fragile. A single task with a high UCLAMP_MAX (or with the default value, which is 1024) can ruin the previous settings the moment it is enqueued, as shown in the uclamp frequency spike problem in Section 5.2 of Documentation/scheduler/sched-util-clamp.rst. Constantly running at 1024 utilization implies that the CPU is driven at its max capacity. However, with UCLAMP_MAX, this assumption is no longer true. To mitigate this, one idea is to filter out uclamp values for short-running tasks. However, the effectiveness of this idea remains to be seen.

2. No way to differentiate between UCLAMP_MAX throttled CPU or a CPU running at its peak, as both show utilization of 1024. However, in certain cases it's important to tell the difference, as we still want to take the opportunity to enqueue tasks in the former case.

It's also debatable whether uclamp should be a frequency hint. An example is a system with a mid CPU of capacity 500, and a little CPU with capacity 100. If we have 10 tasks with UCLAMP_MIN of 101, then util_fits_cpu() will schedule them on the mid CPU because feec() thinks they don't fit on the little, even though we should use the little core at some point instead of making the mid even more crowded. Of course, this in reality doesn't happen because of other mechanisms like load balancing, but it's also not good when other mechanisms can

cancel the effect of uclamp in feec(). A CPU running at capacity 500 for 1ms or for 1000ms gives completely different performance levels, so trying to fit only the frequency does not give us any performance guarantees. If we then talk about not only running at some frequency but also for some amount of time, then what we really mean is a capacity hint, not a frequency hint.

It's even worse when the tasks scheduled on the mid CPU also have UCLAMP_MAX values. In the previous example, instead of running at 500, a single UCLAMP_MAX, assuming it's 110, can make the mid CPU run at a much lower frequency than 500, so it is then a really bad decision to honor the UCLAMP_MIN frequency hint and place it on the mid CPU, instead of running it on the little CPU which is less crowded, and has pretty much the same capacity (100 vs 110) anyway.

This series attempts to solve these problems by tracking a util_avg_uclamp signal in tasks and cfs_rq. At task level, p->se.avg.util_avg_uclamp is basically tracking the normal util_avg, but clamped within its uclamp min and max. At cfs_rq level, util_avg_uclamp must always be the sum of all util_avg_uclamp of all the entities on this cfs_rq. As a result, cfs_rq->avg.util_avg_uclamp is the sum aggregation of all the clamped values, which indicates the frequency this rq should run at and what the utilization is.

This idea solves Problem 1 by capping the utilization of an always-running task throttled by UCLAMP_MAX. Although the task (denoted by Task A) has no idle time, the util_avg_uclamp signal gives its UCLAMP_MAX value instead of 1024, so even if another task (Task B) with a UCLAMP_MAX value at 1024 joins the rq, the util_avg_uclamp is A's UCLAMP_MAX plus B's utilization, instead of 1024 plus B's utilization, which means we no longer have the frequency spike problem caused by B. This should mean that we might completely avoid the need for uclamp filtering.

It also solves Problem 2 by tracking the capped utilization of a rq. Using util_avg_uclamp, we are able to differentiate between a CPU throttled by UCLAMP_MAX and one that is actually running at its peak capacity. An always-running rq with a task having UCLAMP_MAX at 300 will report a cfs_rq util_avg_uclamp at 300, not 1024, which means task placement sees spare capacity on this CPU and will allocate some tasks to it, instead of treating it the same way as a CPU actually running at the peak. This brings us closer to the benefits of Android's sum aggregation (see code related to CONFIG_USE_GROUP_THROTTLE at
https://android.googlesource.com/kernel/gs/+/refs/heads/android-gs-raviole-5.10-android12-d1/drivers/soc/google/vh/kernel/sched/fair.c#510),

which shows energy benefits because we are able to schedule tasks on smaller cores which are UCLAMP_MAX capped, instead of finding a fresh big CPU. However, a major difference is that this series has an amortized cost of O(1), instead of O(n) in cpu_util_next() in Android kernels.

It avoids the shortcomings from uclamp-being-a-frequency-hint. Under sum aggregation, the scheduler sees the sum aggregated util_avg_uclamp and will avoid the problem of enqueueing too many tasks just to fit the frequency, and will place tasks on little CPUs in the previous example.

Patch 2/6 tries to simulate PELT decay in the new util_avg_uclamp signal, as this gives us gradual decay of utilization which avoids premature CPU frequency drops. This is a major caveat of this series. We should explore if there's a better way to integrate uclamp directly into the util_avg signal, instead of introducing a new util_avg_uclamp and then simulate PELT on it.

This new design significantly simplifies uclamp logic.
Patch 4/6 removes the tri-state return value of util_fits_cpu(). Patch 5/6 then completely removes uclamp buckets. Because the util_avg_uclamp is already a clamped value propagated from bottom to top, there's no need to clamp anything at the top level and we can just use this value for frequency selection and spare capacity search. Basically, the idea is that all uclamp logic happens inside util_avg_uclamp, and other code using this new signal can just use it like util_avg, without even knowing that uclamp exists. This drastically reduces the complexity of uclamp and makes the code considering all the uclamp corner cases unnecessary. At the end of the series, we remove 749 lines of code while adding a bit more than 300 (although once we update Documentation.rst, it will be a bit more than that).

Note that this series is still considered RFC status. TODO items are:

1. Implement sum aggregation for RT tasks.
2. Improve handling of cpu_util(boost).

TESTING:

Initial test and benchmark results suggest that sum aggregation not only is significantly simpler, but generally performs much better in achieving what uclamp is supposed to do. Two notebooks are shared at

https://nbviewer.org/github/honxia02/sum_aggre_notebooks/blob/main/upstream.ipynb
https://nbviewer.org/github/honxia02/sum_aggre_notebooks/blob/main/sum.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 always-running tasks with UCLAMP_MAX at 200.

The scheduling decisions are plotted in Out[11] and Out[14] respectively. Max aggregation fails to recognize the opportunity to run all of them on the efficient little Power Domain (PD), whereas sum aggregation runs all 4 on the little PD, leaving the big PD completely powered off, satisfying uclamp requests while saving power.

Scenario 2: Scheduling 4 tasks with UCLAMP_MIN and UCLAMP_MAX at a value slightly above the capacity of the little CPU.

Results are in Out[17] and Out[82]. The purpose is to use UCLAMP_MIN to place tasks on the big core. Max aggregation is pretty much in an overutilized state the entire time. Sum aggregation sees that the big CPU can hold two such tasks (satisfying both UCLAMP_MIN and UCLAMP_MAX requests for all 4 tasks) on each big CPU and quickly settles down, and is still under EAS without overutilization.

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 200. After a while, task A is then pinned to CPU5, joining B.

Results are in Out[23] and Out[95]. The blue util_avg signal is the original root CFS util_avg. The yellow line is the root CFS utilization after considering uclamp. Max aggregation sees a frequency spike at 579.1s. 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 to 200. This happens repeatedly, hence the square wave. In contrast, sum aggregation sees a normal increase in utilization when A joins B, at around 2507s, without any square-wave behavior.

Scenario 4: 4 always-running tasks with UCLAMP_MAX of 120 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] and Out[101]. Max aggregation fails to identify that all 8 tasks can be packed on the little PD, whereas sum aggregation immediately moves the 4 tasks pinned to big PD to the little PD the moment pinning is removed. Sum aggregation understands that even when the rq seems to have utilization of 1024, this is because of UCLAMP_MAX and there's still opportunity to pack 2 such tasks on each little CPU, leaving the big PD untouched, saving power.

BENCHMARKS:

One TODO item is to handle cpu_util(boost) better. The current handling of boost is far from ideal and is a known caveat. All below benchmarks numbers are done without any boosting in cpu_util(), in both max and sum aggregation.

Geekbench 6 (on Rock-5B board)

+-----+-------------+------------+
|     | Single-core | Multi-core |
+-----+-------------+------------+
| Max |      800.6  |     2977.0 |
| Sum |      801.2  |     2981.4 |
+-----+-------------+------------+

No regression is seen after switching to sum aggregation.

Jankbench (backporting sum aggregation to Android 5.18 mainline kernel)

+------+-----------------+-------+-----------+
|      |    variable     | value | perc_diff |
+------+-----------------+-------+-----------+
| main | jank_percentage |  1.1  |    0.00%  |
|  sum | jank_percentage |  0.5  |  -53.92%  |
+------+-----------------+-------+-----------+

+------------+--------+------+-------+-----------+
|            | metric |  tag | value | perc_diff |
+------------+--------+------+-------+-----------+
|    CPU     | gmean  | main | 166.1 |   0.00%   |
|  CPU-Big   | gmean  | main | 55.1  |   0.00%   |
| CPU-Little | gmean  | main | 91.7  |   0.00%   |
|  CPU-Mid   | gmean  | main | 19.2  |   0.00%   |
|    CPU     | gmean  |  sum | 161.3 |  -2.85%   |
|  CPU-Big   | gmean  |  sum | 52.9  |  -3.97%   |
| CPU-Little | gmean  |  sum | 86.7  |  -5.39%   |
|  CPU-Mid   | gmean  |  sum | 21.6  |  12.63%   |
+------------+--------+------+-------+-----------+

The TL;DR of Jankbench is that sum aggregation reduces jank by 54% while with 2.85% less CPU power. Note that this benchmark on Pixel 6 by default has some sort of uclamp feedback applied to it. When jank is detected, certain display and benchmark threads are applied with a UCLAMP_MIN value of 512 (any help in identifying where these UCLAMP_MIN values come from in the mainline Android kernel is appreciated). In contrast, we constantly apply a UCLAMP_MIN value of 60 to these threads without any feedback loop. If a similar feedback loop is involved to only apply UCLAMP_MIN when needed, power consumption can be expected to be even lower.

Quoted 13 lines · Hongyan Xia

Current implementation of uclamp leaves many things to be desired. There are several problems:

1. Max aggregation is fragile. A single task with a high UCLAMP_MAX (or with the default value, which is 1024) can ruin the previous settings the moment it is enqueued, as shown in the uclamp frequency spike problem in Section 5.2 of Documentation/scheduler/sched-util-clamp.rst. Constantly running at 1024 utilization implies that the CPU is driven at its max capacity. However, with UCLAMP_MAX, this assumption is no longer true. To mitigate this, one idea is to filter out uclamp values for short-running tasks. However, the effectiveness of this idea remains to be seen.

The difference is that we don't have to lift the uclamp_max cap of runnable p1's uclamp_max (< 1024) when a short running p2 with uclamp_max = 1024 becomes runnable? Since now, when this happens, we would just add p2's util_avg_uclamp to cfs_rq's util_avg_uclamp which is tiny compared to its uclamp_max = 1024.

Quoted 4 lines

2. No way to differentiate between UCLAMP_MAX throttled CPU or a CPU running at its peak, as both show utilization of 1024. However, in certain cases it's important to tell the difference, as we still want to take the opportunity to enqueue tasks in the former case.

Is this related to the best_fits/max_fits logic in find_energy_efficient_cpu() (feec()) and select_idle_capacity() (sic()) (commit e5ed0550c04c "sched/fair: unlink misfit task from cpu overutilized")?
With your approach, having cfs_rq's util_avg_uclamp next to its util_avg would allow to see those difference by comparing the two signals?

Quoted 8 lines

It's also debatable whether uclamp should be a frequency hint. An example is a system with a mid CPU of capacity 500, and a little CPU with capacity 100. If we have 10 tasks with UCLAMP_MIN of 101, then util_fits_cpu() will schedule them on the mid CPU because feec() thinks they don't fit on the little, even though we should use the little core at some point instead of making the mid even more crowded. Of course, this in reality doesn't happen because of other mechanisms like load balancing, but it's also not good when other mechanisms can

CPU overutilization detection enables CFS load-balance & sis()->sic() and disables feec().

Quoted 6 lines

cancel the effect of uclamp in feec(). A CPU running at capacity 500 for 1ms or for 1000ms gives completely different performance levels, so trying to fit only the frequency does not give us any performance guarantees. If we then talk about not only running at some frequency but also for some amount of time, then what we really mean is a capacity hint, not a frequency hint.

Isn't CPU frequency and capacity going in the same direction?

IPC * CPU frequency = Instruction per Second == Performance (Capacity).

And in the scheduler, utilization is the portion of the Capacity currently used.

What sum aggregation does differently is that you can sum-up individually clamped utilization contributions and compare them against capacity rather then being forced to use the maximum value of a clamp value of one (runnable) task to guide frequency. This avoids those discontinuity-moments when a task with a high uclamp value switches between runnable and sleeping state.

Quoted 17 lines

It's even worse when the tasks scheduled on the mid CPU also have UCLAMP_MAX values. In the previous example, instead of running at 500, a single UCLAMP_MAX, assuming it's 110, can make the mid CPU run at a much lower frequency than 500, so it is then a really bad decision to honor the UCLAMP_MIN frequency hint and place it on the mid CPU, instead of running it on the little CPU which is less crowded, and has pretty much the same capacity (100 vs 110) anyway.

This series attempts to solve these problems by tracking a util_avg_uclamp signal in tasks and cfs_rq. At task level, p->se.avg.util_avg_uclamp is basically tracking the normal util_avg, but clamped within its uclamp min and max. At cfs_rq level, util_avg_uclamp must always be the sum of all util_avg_uclamp of all the entities on this cfs_rq. As a result, cfs_rq->avg.util_avg_uclamp is the sum aggregation of all the clamped values, which indicates the frequency this rq should run at and what the utilization is.

Quoted 9 lines

This idea solves Problem 1 by capping the utilization of an always-running task throttled by UCLAMP_MAX. Although the task (denoted by Task A) has no idle time, the util_avg_uclamp signal gives its UCLAMP_MAX value instead of 1024, so even if another task (Task B) with a UCLAMP_MAX value at 1024 joins the rq, the util_avg_uclamp is A's UCLAMP_MAX plus B's utilization, instead of 1024 plus B's utilization, which means we no longer have the frequency spike problem caused by B. This should mean that we might completely avoid the need for uclamp filtering.

That would be very nice since I remember that this filtering approach hat to figure out the actual runtime of the task and the implemention couldn't be just in the sched class code but had to be done in core code as well.

Quoted 11 lines

It also solves Problem 2 by tracking the capped utilization of a rq. Using util_avg_uclamp, we are able to differentiate between a CPU throttled by UCLAMP_MAX and one that is actually running at its peak capacity. An always-running rq with a task having UCLAMP_MAX at 300 will report a cfs_rq util_avg_uclamp at 300, not 1024, which means task placement sees spare capacity on this CPU and will allocate some tasks to it, instead of treating it the same way as a CPU actually running at the peak. This brings us closer to the benefits of Android's sum aggregation (see code related to CONFIG_USE_GROUP_THROTTLE at
https://android.googlesource.com/kernel/gs/+/refs/heads/android-gs-raviole-5.10-android12-d1/drivers/soc/google/vh/kernel/sched/fair.c#510),

That's true although the latest Pixel phone does not seem to rely on CONFIG_USE_GROUP_THROTTLE anymore but on customized PELT tracking for so called Vendor CFS Util Groups and its sum aggregation on CPU (root cfs_rq) level(CONFIG_USE_VENDOR_GROUP_UTIL).

CONFIG_USE_GROUP_THROTTLE was using the fact that Android only uses 1. level taskgroups to map its different task types (e.g. foreground, background etc.) into:

for_each_leaf_cfs_rq_safe()
calc subgroup_util_sum and throttled_subgroup_util_sum and skip root

cpu_util = root_util - subgroup_util_sum + throttled_subgroup_util_sum

So summing up the (throttled (capped)) contritions of the 1. level taskgroups plus the root taskgroup util.

With CONFIG_USE_VENDOR_GROUP_UTIL each tasks has a vendor pointer into an CFS util array indexed by an Android task type ID to which the task contributes its util. CPU util is then sum aggregated over this array.

We should recall that this is all done because the current uclamp-max max aggression isn't working for Androids use-cases.

So to overcome this issue in mainline is key here.

Quoted 32 lines

which shows energy benefits because we are able to schedule tasks on smaller cores which are UCLAMP_MAX capped, instead of finding a fresh big CPU. However, a major difference is that this series has an amortized cost of O(1), instead of O(n) in cpu_util_next() in Android kernels.

It avoids the shortcomings from uclamp-being-a-frequency-hint. Under sum aggregation, the scheduler sees the sum aggregated util_avg_uclamp and will avoid the problem of enqueueing too many tasks just to fit the frequency, and will place tasks on little CPUs in the previous example.

Patch 2/6 tries to simulate PELT decay in the new util_avg_uclamp signal, as this gives us gradual decay of utilization which avoids premature CPU frequency drops. This is a major caveat of this series. We should explore if there's a better way to integrate uclamp directly into the util_avg signal, instead of introducing a new util_avg_uclamp and then simulate PELT on it.

This new design significantly simplifies uclamp logic.
Patch 4/6 removes the tri-state return value of util_fits_cpu(). Patch 5/6 then completely removes uclamp buckets. Because the util_avg_uclamp is already a clamped value propagated from bottom to top, there's no need to clamp anything at the top level and we can just use this value for frequency selection and spare capacity search. Basically, the idea is that all uclamp logic happens inside util_avg_uclamp, and other code using this new signal can just use it like util_avg, without even knowing that uclamp exists. This drastically reduces the complexity of uclamp and makes the code considering all the uclamp corner cases unnecessary. At the end of the series, we remove 749 lines of code while adding a bit more than 300 (although once we update Documentation.rst, it will be a bit more than that).

Quoted 4 lines

Note that this series is still considered RFC status. TODO items are:

1. Implement sum aggregation for RT tasks.
2. Improve handling of cpu_util(boost).

What about the integration with util_est here?

In cpu_util(), &rq->cfs->avg.util_avg is replaced by rq->root_cfs_util_uclamp

and in

task_util_est() (should be actually named task_util() to be in sync with cpu_util(), i.e. returning max(util, util_est)), task_util(p) returns p->se.avg.util_avg_uclamp.

Are there use cases for the original avg.util_avg still in place?

Quoted 13 lines

TESTING:

Initial test and benchmark results suggest that sum aggregation not only is significantly simpler, but generally performs much better in achieving what uclamp is supposed to do. Two notebooks are shared at

https://nbviewer.org/github/honxia02/sum_aggre_notebooks/blob/main/upstream.ipynb
https://nbviewer.org/github/honxia02/sum_aggre_notebooks/blob/main/sum.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.

Quoted 7 lines

Scenario 1: Scheduling 4 always-running tasks with UCLAMP_MAX at 200.

The scheduling decisions are plotted in Out[11] and Out[14] respectively. Max aggregation fails to recognize the opportunity to run all of them on the efficient little Power Domain (PD), whereas sum aggregation runs all 4 on the little PD, leaving the big PD completely powered off, satisfying uclamp requests while saving power.

Does upstream already contain the v6.7 fixes Fix uclamp code corner cases ?

https://lkml.kernel.org/r/[email protected]

Quoted 9 lines

Scenario 2: Scheduling 4 tasks with UCLAMP_MIN and UCLAMP_MAX at a value slightly above the capacity of the little CPU.

Results are in Out[17] and Out[82]. The purpose is to use UCLAMP_MIN to place tasks on the big core. Max aggregation is pretty much in an overutilized state the entire time. Sum aggregation sees that the big CPU can hold two such tasks (satisfying both UCLAMP_MIN and UCLAMP_MAX requests for all 4 tasks) on each big CPU and quickly settles down, and is still under EAS without overutilization.

thread0-[0-3] uclamp_max = 309. So p->se.avg.util_avg_uclamp is constrained by this value for all 4 tasks, letting 2 tasks fit on each of the big CPUs. You have to zoom in into Out[82] to actually see this.

And I guess for max aggregation cpu_overutilized() can't hold the clamp continuously because of all the other short running uclamp_max = 1024 (default) tasks on the rq's.

Quoted 4 lines

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 200. After a while, task A is then pinned to CPU5, joining B.

Quoted 11 lines

Results are in Out[23] and Out[95]. The blue util_avg signal is the original root CFS util_avg. The yellow line is the root CFS utilization after considering uclamp. Max aggregation sees a frequency spike at 579.1s. 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 to 200. This happens repeatedly, hence the square wave. In contrast, sum aggregation sees a normal increase in utilization when A joins B, at around 2507s, without any square-wave behavior.

Makes sense. But there shouldn't be a root_cfs_util_uclamp in main? Which signal does the yellow line represent in Out[23]?

Quoted 11 lines

Scenario 4: 4 always-running tasks with UCLAMP_MAX of 120 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] and Out[101]. Max aggregation fails to identify that all 8 tasks can be packed on the little PD, whereas sum aggregation immediately moves the 4 tasks pinned to big PD to the little PD the moment pinning is removed. Sum aggregation understands that even when the rq seems to have utilization of 1024, this is because of UCLAMP_MAX and there's still opportunity to pack 2 such tasks on each little CPU, leaving the big PD untouched, saving power.

Looks good to me.

Quoted 7 lines

BENCHMARKS:

One TODO item is to handle cpu_util(boost) better. The current handling of boost is far from ideal and is a known caveat. All below benchmarks numbers are done without any boosting in cpu_util(), in both max and sum aggregation.

Maybe to early for black-box tests at this stage but good to see that nothing seems to go sideways with uclamp sum aggregation.

Quoted 43 lines

Geekbench 6 (on Rock-5B board)

+-----+-------------+------------+
|     | Single-core | Multi-core |
+-----+-------------+------------+
| Max |      800.6  |     2977.0 |
| Sum |      801.2  |     2981.4 |
+-----+-------------+------------+

No regression is seen after switching to sum aggregation.

Jankbench (backporting sum aggregation to Android 5.18 mainline kernel)

+------+-----------------+-------+-----------+
|      |    variable     | value | perc_diff |
+------+-----------------+-------+-----------+
| main | jank_percentage |  1.1  |    0.00%  |
|  sum | jank_percentage |  0.5  |  -53.92%  |
+------+-----------------+-------+-----------+

+------------+--------+------+-------+-----------+
|            | metric |  tag | value | perc_diff |
+------------+--------+------+-------+-----------+
|    CPU     | gmean  | main | 166.1 |   0.00%   |
|  CPU-Big   | gmean  | main | 55.1  |   0.00%   |
| CPU-Little | gmean  | main | 91.7  |   0.00%   |
|  CPU-Mid   | gmean  | main | 19.2  |   0.00%   |
|    CPU     | gmean  |  sum | 161.3 |  -2.85%   |
|  CPU-Big   | gmean  |  sum | 52.9  |  -3.97%   |
| CPU-Little | gmean  |  sum | 86.7  |  -5.39%   |
|  CPU-Mid   | gmean  |  sum | 21.6  |  12.63%   |
+------------+--------+------+-------+-----------+

The TL;DR of Jankbench is that sum aggregation reduces jank by 54% while with 2.85% less CPU power. Note that this benchmark on Pixel 6 by default has some sort of uclamp feedback applied to it. When jank is detected, certain display and benchmark threads are applied with a UCLAMP_MIN value of 512 (any help in identifying where these UCLAMP_MIN values come from in the mainline Android kernel is appreciated). In contrast, we constantly apply a UCLAMP_MIN value of 60 to these threads without any feedback loop. If a similar feedback loop is involved to only apply UCLAMP_MIN when needed, power consumption can be expected to be even lower.

[...]

Quoted 15 lines · Dietmar Eggemann

Quoted 13 lines · Hongyan Xia

Current implementation of uclamp leaves many things to be desired. There are several problems:

1. Max aggregation is fragile. A single task with a high UCLAMP_MAX (or with the default value, which is 1024) can ruin the previous settings the moment it is enqueued, as shown in the uclamp frequency spike problem in Section 5.2 of Documentation/scheduler/sched-util-clamp.rst. Constantly running at 1024 utilization implies that the CPU is driven at its max capacity. However, with UCLAMP_MAX, this assumption is no longer true. To mitigate this, one idea is to filter out uclamp values for short-running tasks. However, the effectiveness of this idea remains to be seen.

Quoted 5 lines

The difference is that we don't have to lift the uclamp_max cap of runnable p1's uclamp_max (< 1024) when a short running p2 with uclamp_max = 1024 becomes runnable? Since now, when this happens, we would just add p2's util_avg_uclamp to cfs_rq's util_avg_uclamp which is tiny compared to its uclamp_max = 1024.

Yes. That's a correct interpretation. I can add this version to the cover letter to make things clearer.

Quoted 6 lines

Quoted 5 lines

2. No way to differentiate between UCLAMP_MAX throttled CPU or a CPU running at its peak, as both show utilization of 1024. However, in certain cases it's important to tell the difference, as we still want
    to take the opportunity to enqueue tasks in the former case.

Quoted 7 lines

Is this related to the best_fits/max_fits logic in find_energy_efficient_cpu() (feec()) and select_idle_capacity() (sic()) (commit e5ed0550c04c "sched/fair: unlink misfit task from cpu overutilized")?
With your approach, having cfs_rq's util_avg_uclamp next to its util_avg would allow to see those difference by comparing the two signals?

Somewhat related. The usefulness is mostly around cpu_util(). Max aggregation will see cpu_util() of 1024 (spare capacity of 0) even when this is caused by UCLAMP_MAX, not by actually running the CPU at max capacity, whereas this series will have a util < 1024 if capped by UCLAMP_MAX.

This means the patch to consider 0 spare capacities (because under max aggregation 0 capacity doesn't mean the CPU is at max) is unnecessary:

6b00a40147653c8ea748e8f4396510f252763364 sched/uclamp: Set max_spare_cap_cpu even if max_spare_cap is 0

Quoted 14 lines

Quoted 6 lines

cancel the effect of uclamp in feec(). A CPU running at capacity 500 for 1ms or for 1000ms gives completely different performance levels, so trying to fit only the frequency does not give us any performance guarantees. If we then talk about not only running at some frequency but also for some amount of time, then what we really mean is a capacity hint, not a frequency hint.

Isn't CPU frequency and capacity going in the same direction?

  IPC * CPU frequency = Instruction per Second == Performance (Capacity).

And in the scheduler, utilization is the portion of the Capacity currently used.

Quoted 6 lines

What sum aggregation does differently is that you can sum-up individually clamped utilization contributions and compare them against capacity rather then being forced to use the maximum value of a clamp value of one (runnable) task to guide frequency. This avoids those discontinuity-moments when a task with a high uclamp value switches between runnable and sleeping state.

I guess what I was describing was a new metric:

    Work = Capacity * Time

Max aggregation aims to fit capacity, but if a task can be run at a high capacity but for only a very short period of time, then this scheduling is not particularly useful. Like in the above example, moving a task with UCLAMP_MIN of 101 to the mid CPU isn't helpful when there are already 10 tasks on the mid CPU, because Time is reduced.

Quoted 10 lines

Quoted 9 lines

This idea solves Problem 1 by capping the utilization of an always-running task throttled by UCLAMP_MAX. Although the task (denoted by Task A) has no idle time, the util_avg_uclamp signal gives its UCLAMP_MAX value instead of 1024, so even if another task (Task B) with a UCLAMP_MAX value at 1024 joins the rq, the util_avg_uclamp is A's UCLAMP_MAX plus B's utilization, instead of 1024 plus B's utilization, which means we no longer have the frequency spike problem caused by B. This should mean that we might completely avoid the need for uclamp filtering.

Quoted 4 lines

That would be very nice since I remember that this filtering approach hat to figure out the actual runtime of the task and the implemention couldn't be just in the sched class code but had to be done in core code as well.

Yes. So far I don't see any need for filtering and runtime accounting in uclamp sum aggregation.

Quoted 4 lines

We should recall that this is all done because the current uclamp-max max aggression isn't working for Androids use-cases.

So to overcome this issue in mainline is key here.

Thanks for pointing me to the latest Pixel code.

The basic ideas of that and this series look very similar. Both sum up CFS utilization instead of directly tracking the root CFS utilization. This series so far has only implemented uclamp on tasks, but the same code can also be implemented on group sched_entities. Once I implement that, then it essentially does the same thing as GROUP_THROTTLE. I think if the current Pixel code works, then it's likely this series works too.

The big difference is that this series relies on CONFIG_FAIR_GROUP_SCHED. There seems to be complaints about it and I may need to know why it's not desirable for Android.

Quoted 16 lines

Quoted 4 lines

Note that this series is still considered RFC status. TODO items are:

1. Implement sum aggregation for RT tasks.
2. Improve handling of cpu_util(boost).

What about the integration with util_est here?

In cpu_util(), &rq->cfs->avg.util_avg is replaced by rq->root_cfs_util_uclamp

and in

task_util_est() (should be actually named task_util() to be in sync with cpu_util(), i.e. returning max(util, util_est)), task_util(p) returns p->se.avg.util_avg_uclamp.

Quoted 1 line

Are there use cases for the original avg.util_avg still in place?

We still need the original avg.util_avg for tasks because util_avg_uclamp is clamped from it, but other than that, at the moment there's no reason to use the normal util_avg.

Quoted 1 line

Quoted 1 line

Scenario 1: Scheduling 4 always-running tasks with UCLAMP_MAX at 200.

Quoted 4 lines

Does upstream already contain the v6.7 fixes Fix uclamp code corner cases ?

https://lkml.kernel.org/r/[email protected]

Unfortunately, no. These experiments were done before that patch. I quickly did a test and that patch did fix this issue. Now the four little tasks are scheduled on the small PD.

But I remember that you have another test indicating that the patch may expose some new issues?

Quoted 1 line

Quoted 1 line

Scenario 2: Scheduling 4 tasks with UCLAMP_MIN and UCLAMP_MAX at a value

Quoted 7 lines

thread0-[0-3] uclamp_max = 309. So p->se.avg.util_avg_uclamp is constrained by this value for all 4 tasks, letting 2 tasks fit on each of the big CPUs. You have to zoom in into Out[82] to actually see this.

And I guess for max aggregation cpu_overutilized() can't hold the clamp continuously because of all the other short running uclamp_max = 1024 (default) tasks on the rq's.

Actually I'm not 100% sure about the reason why max aggregation under this experiment never stabilizes. I can investigate further.

Quoted 1 line

Quoted 1 line

Scenario 3: Task A is a task with a small utilization pinned to CPU4.

Quoted 2 lines

Makes sense. But there shouldn't be a root_cfs_util_uclamp in main? Which signal does the yellow line represent in Out[23]?

Ah, that can be confusing. For current upstream root_cfs_util_uclamp comes from uclamp_rq_util_with(rq, cfs_rq->avg.util_avg).

Current implementation of uclamp leaves many things to be desired. There are several problems:

1. Max aggregation is fragile. A single task with a high UCLAMP_MAX (or with the default value, which is 1024) can ruin the previous settings the moment it is enqueued, as shown in the uclamp frequency spike problem in Section 5.2 of Documentation/scheduler/sched-util-clamp.rst. Constantly running at 1024 utilization implies that the CPU is driven at its max capacity. However, with UCLAMP_MAX, this assumption is no longer true. To mitigate this, one idea is to filter out uclamp values for short-running tasks. However, the effectiveness of this idea remains to be seen.

2. No way to differentiate between UCLAMP_MAX throttled CPU or a CPU running at its peak, as both show utilization of 1024. However, in certain cases it's important to tell the difference, as we still want to take the opportunity to enqueue tasks in the former case.

It's also debatable whether uclamp should be a frequency hint. An

example is a system with a mid CPU of capacity 500, and a little CPU with capacity 100. If we have 10 tasks with UCLAMP_MIN of 101, then util_fits_cpu() will schedule them on the mid CPU because feec() thinks they don't fit on the little, even though we should use the little core at some point instead of making the mid even more crowded.

Of course, this in reality doesn't happen because of other mechanisms like load balancing, but it's also not good when other mechanisms can cancel the effect of uclamp in feec(). A CPU running at capacity 500 for 1ms or for 1000ms gives completely different performance levels, so trying to fit only the frequency does not give us any performance guarantees. If we then talk about not only running at some frequency but also for some amount of time, then what we really mean is a capacity hint, not a frequency hint.

It's even worse when the tasks scheduled on the mid CPU also have UCLAMP_MAX values. In the previous example, instead of running at 500, a single UCLAMP_MAX, assuming it's 110, can make the mid CPU run at a much lower frequency than 500, so it is then a really bad decision to honor the UCLAMP_MIN frequency hint and place it on the mid CPU, instead of running it on the little CPU which is less crowded, and has pretty much the same capacity (100 vs 110) anyway.

This series attempts to solve these problems by tracking a util_avg_uclamp signal in tasks and cfs_rq. At task level,

p->se.avg.util_avg_uclamp is basically tracking the normal util_avg, but clamped within its uclamp min and max. At cfs_rq level, util_avg_uclamp must always be the sum of all util_avg_uclamp of all the entities on this cfs_rq. As a result, cfs_rq->avg.util_avg_uclamp is the sum aggregation of all the clamped values, which indicates the frequency this rq should run at and what the utilization is.

This idea solves Problem 1 by capping the utilization of an always-running task throttled by UCLAMP_MAX. Although the task (denoted by Task A) has no idle time, the util_avg_uclamp signal gives its UCLAMP_MAX value instead of 1024, so even if another task (Task B) with a UCLAMP_MAX value at 1024 joins the rq, the util_avg_uclamp is A's UCLAMP_MAX plus B's utilization, instead of 1024 plus B's utilization, which means we no longer have the frequency spike problem caused by B. This should mean that we might completely avoid the need for uclamp filtering.

It also solves Problem 2 by tracking the capped utilization of a rq. Using util_avg_uclamp, we are able to differentiate between a CPU throttled by UCLAMP_MAX and one that is actually running at its peak capacity. An always-running rq with a task having UCLAMP_MAX at 300 will report a cfs_rq util_avg_uclamp at 300, not 1024, which means task placement sees spare capacity on this CPU and will allocate some tasks to it, instead of treating it the same way as a CPU actually running at

the peak. This brings us closer to the benefits of Android's sum aggregation (see code related to CONFIG_USE_GROUP_THROTTLE at
https://android.googlesource.com/kernel/gs/+/refs/heads/android-gs-raviole-5.10-android12-d1/drivers/soc/google/vh/kernel/sched/fair.c#510),
which shows energy benefits because we are able to schedule tasks on smaller cores which are UCLAMP_MAX capped, instead of finding a fresh

big CPU. However, a major difference is that this series has an amortized cost of O(1), instead of O(n) in cpu_util_next() in Android kernels.

It avoids the shortcomings from uclamp-being-a-frequency-hint. Under sum

aggregation, the scheduler sees the sum aggregated util_avg_uclamp and will avoid the problem of enqueueing too many tasks just to fit the frequency, and will place tasks on little CPUs in the previous example.

Hi Hongyan

Quoted 13 lines · Hongyan Xia

Current implementation of uclamp leaves many things to be desired. There are several problems:

1. Max aggregation is fragile. A single task with a high UCLAMP_MAX (or with the default value, which is 1024) can ruin the previous settings the moment it is enqueued, as shown in the uclamp frequency spike problem in Section 5.2 of Documentation/scheduler/sched-util-clamp.rst. Constantly running at 1024 utilization implies that the CPU is driven at its max capacity. However, with UCLAMP_MAX, this assumption is no longer true. To mitigate this, one idea is to filter out uclamp values for short-running tasks. However, the effectiveness of this idea remains to be seen.

This was proved when I was at arm and it is used in products now too. It is effective.

Quoted 6 lines

2. No way to differentiate between UCLAMP_MAX throttled CPU or a CPU running at its peak, as both show utilization of 1024. However, in certain cases it's important to tell the difference, as we still want to take the opportunity to enqueue tasks in the former case.

Quoted 1 line

It's also debatable whether uclamp should be a frequency hint. An

It is not debatable. Uclamp is a performance hint which translates into task placement (for HMP) and frequency selection. On SMP the latter is the only meaning for uclamp. For the time being at least until we get a new technology that can impact performance ;-)

Quoted 5 lines

example is a system with a mid CPU of capacity 500, and a little CPU with capacity 100. If we have 10 tasks with UCLAMP_MIN of 101, then util_fits_cpu() will schedule them on the mid CPU because feec() thinks they don't fit on the little, even though we should use the little core at some point instead of making the mid even more crowded.

This is not a problem. One of the major design points for uclamp is to allow small tasks to request to run faster. So if you have 100 tasks that run for 100us and to meet that they need to run at mid CPU that is fine. That doesn't necessarily mean they'll overutilized the cluster.

If the cluster gets overutilized, then EAS will be disabled and find_idle_capacity() will spread into highest spare capacity idle CPU, which includes little CPUs. And this behavior is no different to have tasks with util greater than 100 wanting to run on mid cores. The only difference is that we can pack more on mid core before overutilized can be triggered. Which is the desired effect.

So this is a no issue and we should spread once the cluster is busy.

Quoted 8 lines

Of course, this in reality doesn't happen because of other mechanisms like load balancing, but it's also not good when other mechanisms can cancel the effect of uclamp in feec(). A CPU running at capacity 500 for 1ms or for 1000ms gives completely different performance levels, so trying to fit only the frequency does not give us any performance guarantees. If we then talk about not only running at some frequency but also for some amount of time, then what we really mean is a capacity hint, not a frequency hint.

I'm not sure I parsed that. But again, it's a performance hint which implies both.

Quoted 8 lines

It's even worse when the tasks scheduled on the mid CPU also have UCLAMP_MAX values. In the previous example, instead of running at 500, a single UCLAMP_MAX, assuming it's 110, can make the mid CPU run at a much lower frequency than 500, so it is then a really bad decision to honor the UCLAMP_MIN frequency hint and place it on the mid CPU, instead of running it on the little CPU which is less crowded, and has pretty much the same capacity (100 vs 110) anyway.

I can't follow this reasoning.

It seems you're assuming the user has picked 110 by mistake and it is okay to ignore it.

FYI, one of the use cases is to set uclamp_min to capacity_of(little_core)+1 because they're so crappy to handle their workload. It is still better than using affinity as when the system gets busy we can still use the little core. But only when the system is busy and crowded already.

I don't know what's the reference to the mid core having a task with uclamp_max, but seems a bug in feec() if not predicting the frequency correctly.

Quoted 3 lines

This series attempts to solve these problems by tracking a util_avg_uclamp signal in tasks and cfs_rq. At task level,

This was discussed offline and brought several times on the list already. uclamp is a performance not a bandwidth hint. I remember Dietmar was suggesting this concept in the past and I objected that this converts uclamp into a bandwidth hint. This overlaps with CFS bandwidth controller. We can use that if somebody wants to limit the bandwidth the task can consume. uclamp is about limiting the performance level it can reach. ie: it is not about cycles consumed, but Performance Point reached.

Quoted 6 lines

p->se.avg.util_avg_uclamp is basically tracking the normal util_avg, but clamped within its uclamp min and max. At cfs_rq level, util_avg_uclamp must always be the sum of all util_avg_uclamp of all the entities on this cfs_rq. As a result, cfs_rq->avg.util_avg_uclamp is the sum aggregation of all the clamped values, which indicates the frequency this rq should run at and what the utilization is.

This is a no go for me. A task performance requirements can not be added to resemble the 'size' of the tasks. Tasks with util_avg 100 but a uclamp_min of 1024 should allow us to pack them in the big core. Which is an important use case to use. A bunch of small tasks that need to run faster are okay to pack on a bigger core if they need to run faster as long as this doesn't cause overutilized to trigger.

Quoted 11 lines

This idea solves Problem 1 by capping the utilization of an always-running task throttled by UCLAMP_MAX. Although the task (denoted by Task A) has no idle time, the util_avg_uclamp signal gives its UCLAMP_MAX value instead of 1024, so even if another task (Task B) with a UCLAMP_MAX value at 1024 joins the rq, the util_avg_uclamp is A's UCLAMP_MAX plus B's utilization, instead of 1024 plus B's utilization, which means we no longer have the frequency spike problem caused by B. This should mean that we might completely avoid the need for uclamp filtering.

Quoted 7 lines

It also solves Problem 2 by tracking the capped utilization of a rq. Using util_avg_uclamp, we are able to differentiate between a CPU throttled by UCLAMP_MAX and one that is actually running at its peak capacity. An always-running rq with a task having UCLAMP_MAX at 300 will report a cfs_rq util_avg_uclamp at 300, not 1024, which means task placement sees spare capacity on this CPU and will allocate some tasks to it, instead of treating it the same way as a CPU actually running at

We don't need to know the actual spare capacity, though that would be nice to have.

But generally in my view this CPU should be available for non capped task to run on. I view this a load balancer problem where wake up path can consider this CPU as a candidate and rely on load balancer to move this task away to another (smaller) CPU ASAP. If this capped task is already on the smaller CPU and there's nowhere else to place the uncapped task in the system then we must be quite busy already.

If userspace ends up capping too many tasks too hard that we end up with no idle time in the system (where otherwise we should) I consider this a bad usage in the userspace and will ask them not to cap that hard. This is a case of one shooting themselves in the foot. Maybe we need to care in the future, but so far this doesn't seem a valid problem to address. I'd like to see why userspace has failed to do proper management first before jumping to fix this.

What I'd expect more use cases of tasks that are truly 1024 but being capped. In this case there's truly no idle time on the CPU and your proposal won't address this. I don't think we have a way to distinguish between the two cases at the moment.

Quoted 5 lines

the peak. This brings us closer to the benefits of Android's sum aggregation (see code related to CONFIG_USE_GROUP_THROTTLE at
https://android.googlesource.com/kernel/gs/+/refs/heads/android-gs-raviole-5.10-android12-d1/drivers/soc/google/vh/kernel/sched/fair.c#510),
which shows energy benefits because we are able to schedule tasks on smaller cores which are UCLAMP_MAX capped, instead of finding a fresh

You're jumping to the wrong conclusion about why this is being used. This was to overcome issues when using cpu.shares. This has nothing to do with UCLAMP_MAX. uclamp_max filter is what is being used. Based on the proposal I posted long ago

	https://android-review.googlesource.com/c/kernel/common/+/1914696

Quoted 5 lines

big CPU. However, a major difference is that this series has an amortized cost of O(1), instead of O(n) in cpu_util_next() in Android kernels.

It avoids the shortcomings from uclamp-being-a-frequency-hint. Under sum

This is not a short coming. Performance implies frequency. We should not confused how schedutil works to estimate perf requirement based on historical run time (util_avg) and the fact that a task with short historical runtime needs to run faster. Running faster means increasing frequency.

Quoted 3 lines

aggregation, the scheduler sees the sum aggregated util_avg_uclamp and will avoid the problem of enqueueing too many tasks just to fit the frequency, and will place tasks on little CPUs in the previous example.

I think the issue of uclamp being a performance but not a bandwidth hint was raised several times. Did I miss something that makes this not converting it to a bandwidth hint?

Hi Qais,

Quoted 26 lines · Qais Yousef

Hi Hongyan

Quoted 13 lines · Hongyan Xia

Current implementation of uclamp leaves many things to be desired. There are several problems:

1. Max aggregation is fragile. A single task with a high UCLAMP_MAX (or with the default value, which is 1024) can ruin the previous settings the moment it is enqueued, as shown in the uclamp frequency spike problem in Section 5.2 of Documentation/scheduler/sched-util-clamp.rst. Constantly running at 1024 utilization implies that the CPU is driven at its max capacity. However, with UCLAMP_MAX, this assumption is no longer true. To mitigate this, one idea is to filter out uclamp values for short-running tasks. However, the effectiveness of this idea remains to be seen.

This was proved when I was at arm and it is used in products now too. It is effective.

Quoted 6 lines

2. No way to differentiate between UCLAMP_MAX throttled CPU or a CPU running at its peak, as both show utilization of 1024. However, in certain cases it's important to tell the difference, as we still want to take the opportunity to enqueue tasks in the former case.

Quoted 6 lines

Quoted 1 line

It's also debatable whether uclamp should be a frequency hint. An

It is not debatable. Uclamp is a performance hint which translates into task placement (for HMP) and frequency selection. On SMP the latter is the only meaning for uclamp. For the time being at least until we get a new technology that can impact performance ;-)

I agree. In this new series, uclamp is still a performance hint which affects task placement and frequency, so we don't have a disagreement here.

Quoted 10 lines

Quoted 5 lines

example is a system with a mid CPU of capacity 500, and a little CPU with capacity 100. If we have 10 tasks with UCLAMP_MIN of 101, then util_fits_cpu() will schedule them on the mid CPU because feec() thinks they don't fit on the little, even though we should use the little core at some point instead of making the mid even more crowded.

This is not a problem. One of the major design points for uclamp is to allow small tasks to request to run faster. So if you have 100 tasks that run for 100us and to meet that they need to run at mid CPU that is fine. That doesn't necessarily mean they'll overutilized the cluster.

I understand. This design point is what sum aggregation does as well. This alone is not a problem, but moving a CPU to another CPU to fit uclamp_min requirement can be a problem, when the destination CPU is crowded and mixed with uclamp_max. I will elaborate on this below.

Quoted 35 lines

If the cluster gets overutilized, then EAS will be disabled and find_idle_capacity() will spread into highest spare capacity idle CPU, which includes little CPUs. And this behavior is no different to have tasks with util greater than 100 wanting to run on mid cores. The only difference is that we can pack more on mid core before overutilized can be triggered. Which is the desired effect.

So this is a no issue and we should spread once the cluster is busy.

Quoted 8 lines

Of course, this in reality doesn't happen because of other mechanisms like load balancing, but it's also not good when other mechanisms can cancel the effect of uclamp in feec(). A CPU running at capacity 500 for 1ms or for 1000ms gives completely different performance levels, so trying to fit only the frequency does not give us any performance guarantees. If we then talk about not only running at some frequency but also for some amount of time, then what we really mean is a capacity hint, not a frequency hint.

I'm not sure I parsed that. But again, it's a performance hint which implies both.

Quoted 8 lines

It's even worse when the tasks scheduled on the mid CPU also have UCLAMP_MAX values. In the previous example, instead of running at 500, a single UCLAMP_MAX, assuming it's 110, can make the mid CPU run at a much lower frequency than 500, so it is then a really bad decision to honor the UCLAMP_MIN frequency hint and place it on the mid CPU, instead of running it on the little CPU which is less crowded, and has pretty much the same capacity (100 vs 110) anyway.

I can't follow this reasoning.

It seems you're assuming the user has picked 110 by mistake and it is okay to ignore it.

Quoted 8 lines

FYI, one of the use cases is to set uclamp_min to capacity_of(little_core)+1 because they're so crappy to handle their workload. It is still better than using affinity as when the system gets busy we can still use the little core. But only when the system is busy and crowded already.

I don't know what's the reference to the mid core having a task with uclamp_max, but seems a bug in feec() if not predicting the frequency correctly.

The example in the cover letter might be complex. I can simplify as a "N tasks" problem.

Say 2 CPUs, one with capacity 1024 and the other 512. Assume there's a task with uclamp_min 513 and uclamp_max of 800, then the big CPU can, in theory, fit an infinite number of such tasks on the big CPU, without triggering overutilization. What does uclamp_min even mean when this happens? uclamp_min should be a hint of a minimum performance it should get, but it breaks down when there are N tasks, so the hint from uclamp_min is divided by N. Under max aggregation, uclamp_min doesn't give you the "performance" of this task. It gives performance of the CPU, and this is not the performance of this task when N > 1. In fact, N can be infinity. This is the same problem shared by multiple uclamp users from LPC, where max aggregation hints the performance of the CPU, but not the task itself.

As to "FYI, one of the use cases is to set uclamp_min to capacity_of(little_core)+1 because they're so crappy to handle their workload", I'm afraid I disagree with this. I think uclamp is a simple hinting mechanism to the scheduler to say: please try to give me [uclamp_min, uclamp_max] performance. It's then the job of EAS to pick

the most efficient CPU. We know the little CPU is crappy because we have deep knowledge of the device, but uclamp values could just come from game developers (using ADPF) who have no knowledge of the SoC, and in the game developer's view, asking uclamp of little CPU + 1 is simply because he/she wants that performance, not because the developer thinks the little CPU should be avoided. I don't think a soft-affinity-like property belongs here. We should improve EM and let EAS do its job instead of teaching it to interpret uclamp as affinity hints.

Quoted 11 lines

Quoted 3 lines

This series attempts to solve these problems by tracking a util_avg_uclamp signal in tasks and cfs_rq. At task level,

This was discussed offline and brought several times on the list already. uclamp is a performance not a bandwidth hint. I remember Dietmar was suggesting this concept in the past and I objected that this converts uclamp into a bandwidth hint. This overlaps with CFS bandwidth controller. We can use that if somebody wants to limit the bandwidth the task can consume. uclamp is about limiting the performance level it can reach. ie: it is not about cycles consumed, but Performance Point reached.

I'd argue the current max aggregation implementation is further away from a performance hint. The moment there are more tasks interacting with each other on the same rq, the performance hinting ability of max aggregation tends to do worse, like uclamp_min being divided by N, frequency spikes, uneven task distribution (both shown in the evaluation section of my cover letter) etc, whereas sum aggregation still performs well.

Other shortcomings are not that critical, but the fact that uclamp_min's effectiveness is divided by N under max aggregation I think is not acceptable.

Quoted 8 lines

Quoted 7 lines

p->se.avg.util_avg_uclamp is basically tracking the normal util_avg, but clamped within its uclamp min and max. At cfs_rq level, util_avg_uclamp must always be the sum of all util_avg_uclamp of all the entities on this cfs_rq. As a result, cfs_rq->avg.util_avg_uclamp is the sum aggregation of all the clamped values, which indicates the frequency this rq should run at and what the utilization is.

Quoted 6 lines

This is a no go for me. A task performance requirements can not be added to resemble the 'size' of the tasks. Tasks with util_avg 100 but a uclamp_min of 1024 should allow us to pack them in the big core. Which is an important use case to use. A bunch of small tasks that need to run faster are okay to pack on a bigger core if they need to run faster as long as this doesn't cause overutilized to trigger.

I see. I now understand where we start to diverge. It seems we want completely different things from uclamp.

Max aggregation: please try to place me on a CPU that can give CPU capacity [uclamp_min, uclamp_max] and run that CPU within that range. Sum aggregation: please try to treat me like a task with utilization within [uclamp_min, uclamp_max].

Like I mentioned in the previous comment, I'm afraid I disagree with using uclamp as a CPU affinity hint, even if it's just a soft affinity. Its job should just be a performance hint and EM should tell EAS which CPU to pick under that hint. If the little CPU is crappy, then the crappiness should be reflected in the EM, and maybe dynamic EM can help.

Quoted 22 lines

Quoted 11 lines

This idea solves Problem 1 by capping the utilization of an always-running task throttled by UCLAMP_MAX. Although the task (denoted by Task A) has no idle time, the util_avg_uclamp signal gives its UCLAMP_MAX value instead of 1024, so even if another task (Task B) with a UCLAMP_MAX value at 1024 joins the rq, the util_avg_uclamp is A's UCLAMP_MAX plus B's utilization, instead of 1024 plus B's utilization, which means we no longer have the frequency spike problem caused by B. This should mean that we might completely avoid the need for uclamp filtering.

Quoted 7 lines

It also solves Problem 2 by tracking the capped utilization of a rq. Using util_avg_uclamp, we are able to differentiate between a CPU throttled by UCLAMP_MAX and one that is actually running at its peak capacity. An always-running rq with a task having UCLAMP_MAX at 300 will report a cfs_rq util_avg_uclamp at 300, not 1024, which means task placement sees spare capacity on this CPU and will allocate some tasks to it, instead of treating it the same way as a CPU actually running at

We don't need to know the actual spare capacity, though that would be nice to have.

Quoted 6 lines

But generally in my view this CPU should be available for non capped task to run on. I view this a load balancer problem where wake up path can consider this CPU as a candidate and rely on load balancer to move this task away to another (smaller) CPU ASAP. If this capped task is already on the smaller CPU and there's nowhere else to place the uncapped task in the system then we must be quite busy already.

I'm not quite sure relying on the load balancer is a good idea, because then it means we need uclamp code in the load balancer and the

complexity keeps growing. An example is that after applying the patch

'sched/uclamp: Set max_spare_cap_cpu even if max_spare_cap is 0'

even though the scheduler now knows that CPUs with 0 spare capacity are now candidates, it creates a very unbalanced task placement and CPU0 tends to receive a lot of tasks in my tests. This certainly needs some uclamp-aware code in the load balancer, whereas sum aggregation has no such problem and balance is achieved during task placement in the first place.

Quoted 11 lines

If userspace ends up capping too many tasks too hard that we end up with no idle time in the system (where otherwise we should) I consider this a bad usage in the userspace and will ask them not to cap that hard. This is a case of one shooting themselves in the foot. Maybe we need to care in the future, but so far this doesn't seem a valid problem to address. I'd like to see why userspace has failed to do proper management first before jumping to fix this.

What I'd expect more use cases of tasks that are truly 1024 but being capped. In this case there's truly no idle time on the CPU and your proposal won't address this. I don't think we have a way to distinguish between the two cases at the moment.

I don't quite get what you mean. In the examples in my cover letter the capped tasks are truly 1024. Two CPUs, one with an uncapped 1024 task and the other a 1024 task but with uclamp_max of 300. The scheduler sees cfs_rq->avg.util_avg_uclamp of 1024 in the first CPU and 300 in the 2nd, so my proposal indeed sees the difference, and will have the opportunity to place more tasks on the 2nd CPU without any corner case code.

Quoted 6 lines

Quoted 5 lines

the peak. This brings us closer to the benefits of Android's sum aggregation (see code related to CONFIG_USE_GROUP_THROTTLE at
https://android.googlesource.com/kernel/gs/+/refs/heads/android-gs-raviole-5.10-android12-d1/drivers/soc/google/vh/kernel/sched/fair.c#510),
which shows energy benefits because we are able to schedule tasks on smaller cores which are UCLAMP_MAX capped, instead of finding a fresh

Quoted 7 lines

You're jumping to the wrong conclusion about why this is being used. This was to overcome issues when using cpu.shares. This has nothing to do with UCLAMP_MAX. uclamp_max filter is what is being used. Based on the proposal I posted long ago

      https://android-review.googlesource.com/c/kernel/common/+/1914696

Maybe I need to rephrase. I said that GROUP_THROTTLE can give us some energy benefits. I didn't draw any conclusion that this was why it was invented. I was also trying to suggest that, under sum aggregation, the same code can work for both uclamp and GROUP_THROTTLE. However, I probably need to better understand the issues around cpu.shares before saying this concretely.

Also, uclamp filtering might be another example why I think max aggregation is over-complicated. Sum aggregation has only around 300 lines of code so far without the need for filtering at all.

Quoted 11 lines

Quoted 5 lines

big CPU. However, a major difference is that this series has an amortized cost of O(1), instead of O(n) in cpu_util_next() in Android kernels.

It avoids the shortcomings from uclamp-being-a-frequency-hint. Under sum

This is not a short coming. Performance implies frequency. We should not confused how schedutil works to estimate perf requirement based on historical run time (util_avg) and the fact that a task with short historical runtime needs to run faster. Running faster means increasing frequency.

Quoted 8 lines

Quoted 3 lines

aggregation, the scheduler sees the sum aggregated util_avg_uclamp and will avoid the problem of enqueueing too many tasks just to fit the frequency, and will place tasks on little CPUs in the previous example.

I think the issue of uclamp being a performance but not a bandwidth hint was raised several times. Did I miss something that makes this not converting it to a bandwidth hint?

I wonder what does performance hint even mean if it doesn't at least correlate to bandwidth in some way? Yes, specifying uclamp_min under max aggregation can run the CPU at least at that frequency, but if you have N tasks on the same rq, then each task can only get a share of uclamp_min/N. I highly doubt that when a mobile phone developer increases the uclamp_min of an application, he or she is okay with doubling the CPU frequency when it runs and running it only for 1/10 of the time because it gets moved to a crowded big CPU, which essentially gives 0.2x the "performance" in my opinion, so I'm not sure fully disconnecting bandwidth from performance is meaningful. Of course, a (not yet) uclamp-aware load balancer could come in and migrate those tasks, but why not avoid this problem in the first place via sum aggregation without involving the load balancer, especially when today we don't have any indication of how well a uclamp-aware load balancer can perform anyway?

In the end I may still not be able to fully grasp what the issues of sum aggregations are. I think so far I get that it's closer to "bandwidth" and not "performance" (which I think "performance" doesn't mean much if it doesn't correlate to bandwidth) and it doesn't work as a CPU affinity hint (it actually does to some degree, but the uclamp values need to be different). But I think focusing on these ignores the whole picture, which are the benefits of sum aggregation (already presented in the evaluation section of the cover letter of this series):

1. It's fewer than 350 lines of code (max aggregation is 750+ and still growing).
2. It doesn't suffer from frequency spikes or load balancing issues.
3. It needs no code to consider uclamp as a corner case in the scheduler. No need to carry around uclamp_min and uclamp_max in so many functions. util_fits_cpu() is just one line of code.
4. It's effective. When you say a uclamp_min of X, the scheduler really tries to give you X for your task, not for the CPU you are on, as seen in 54% reduction of jank in jankbench, without increasing energy consumption.
5. It looks like something multiple developers want from LPC 2023. The use cases of "additive uclamp", and hinting the host from the VM via util_guest can be achieved exactly by uclamp sum aggregation.

Given these benefits, I think it's probably a good idea to give sum aggregation a serious look. On my Pixel 6, sum aggregation either gives better benchmark scores at the same energy as max aggregation, or consumes less power at the same benchmark scores. I'll keep benchmarking it but so far so good.

Hongyan

Quoted 6 lines · Hongyan Xia

[...]

Other shortcomings are not that critical, but the fact that uclamp_min's effectiveness is divided by N under max aggregation I think is not acceptable.

Change EAS task placement policy in this case to take into account actual utilization and uclamp_min/max

Quoted 1 line

[...]

Quoted 8 lines · Vincent Guittot

Quoted 6 lines · Hongyan Xia

[...]

Other shortcomings are not that critical, but the fact that uclamp_min's effectiveness is divided by N under max aggregation I think is not acceptable.

Quoted 2 lines

Change EAS task placement policy in this case to take into account actual utilization and uclamp_min/max

Thank you. I agree. I want to emphasize this specifically because this is exactly what I'm trying to do. The whole series can be rephrased in a different way:

- The PELT signal is distorted when uclamp is active.

- Let's consider the [PELT, uclamp_min, uclamp_max] tuple.

- Always carrying all three variables is too much, but [PELT, clamped(PELT)] is an approximation that works really well.

Of course, I'll explore if there's a way to make things less messy. I just realized why I didn't do things util_est way but instead directly clamping on PELT, it's because util_est boosts util_avg and can't work for uclamp_max. I'll keep exploring options.

Quoted 1 line

Quoted 1 line

[...]

Quoted 17 lines · Hongyan Xia

Quoted 10 lines · Vincent Guittot

Quoted 6 lines · Hongyan Xia

[...]

Other shortcomings are not that critical, but the fact that uclamp_min's effectiveness is divided by N under max aggregation I think is not acceptable.

Change EAS task placement policy in this case to take into account actual utilization and uclamp_min/max

Thank you. I agree. I want to emphasize this specifically because this is exactly what I'm trying to do. The whole series can be rephrased in a different way:

Quoted 1 line

- The PELT signal is distorted when uclamp is active.

Sorry but no it's not >> - Let's consider the [PELT, uclamp_min, uclamp_max] tuple.

That's what we are already doing with effective_cpu_util. We might want to improve how we use them in EAS but that's another story than your proposal

Quoted 2 lines

- Always carrying all three variables is too much, but [PELT, clamped(PELT)] is an approximation that works really well.

As said before. It's a no go for this mix

Quoted 7 lines

Of course, I'll explore if there's a way to make things less messy. I just realized why I didn't do things util_est way but instead directly clamping on PELT, it's because util_est boosts util_avg and can't work for uclamp_max. I'll keep exploring options.

Quoted 1 line

Quoted 1 line

[...]