uclamp sum aggregation

From: Hongyan Xia <[email protected]>

That commit creates further problems because 0 spare capacity can be either a real indication that the CPU is maxed out, or the CPU is UCLAMP_MAX throttled, but we end up giving all of them a chance which can results in bogus energy calculations. It also tends to schedule tasks on the same CPU and requires load balancing patches. Sum aggregation solves these problems and this patch is not needed.

This reverts commit 6b00a40147653c8ea748e8f4396510f252763364.

Quoted 9 lines · Hongyan Xia

From: Hongyan Xia <[email protected]>

That commit creates further problems because 0 spare capacity can be either a real indication that the CPU is maxed out, or the CPU is UCLAMP_MAX throttled, but we end up giving all of them a chance which can results in bogus energy calculations. It also tends to schedule tasks on the same CPU and requires load balancing patches. Sum aggregation solves these problems and this patch is not needed.

Quoted 1 line

This reverts commit 6b00a40147653c8ea748e8f4396510f252763364.

I assume you did this revert especially for the 'Scenario 5: 8 tasks with UCLAMP_MAX of 120' testcase?

IMHO, the issue is especially visible in compute_energy()'s busy_time computation with a valid destination CPU (dst_cpu >= 0). I.e. when we have to add performance domain (pd) and task busy time.

find_energy_efficient_cpu() (feec())

for each pd
for each cpu in pd

set {prev_,max}_spare_cap

bail if prev_ and max_spare_cap < 0 (was == 0 before )

{base_,prev_,cur_}energy = compute_energy

So with the patch we potentially compute energy for a saturated PD according:

compute_energy()

   if (dst_cpu >= 0)
    busy_time = min(eenv->pd_cap, eenv->busy_time + eenv->task_busy_time)
                    <----(a)--->  <--------------(b)------------------->

   energy = em_cpu_energy(pd->em_pd, max_util, busy_time, eenv->cpu_cap)

If (b) > (a) then we're saturated and 'energy' is bogus.

The way to fix this is up for discussion:

(1) feec() returning prev_cpu
(2) feec() returning -1 (forcing wakeup into sis() -> sic())
(3) using uclamped values for task and rq utilization

None of those have immediately given the desired task placement on mainline (2 tasks on each of the 4 little CPUs and no task on the 2 big CPUs on my [l B B l l l] w/ CPU capacities = [446 1024 1024 446 446 446] machine) you can achieve with uclamp sum aggregation.

[...]

On 01/02/2024 14:11, Hongyan Xia wrote:

[...]

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

Quoted 7 lines

/*
* The code below (indirectly) updates schedutil which looks at

kernel/sched/fair.c +1 -0

@@ -6769,6 +6770,10 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
  #ifdef CONFIG_UCLAMP_TASK
  	util_uclamp_enqueue(&rq->cfs.avg, p);
  	update_util_uclamp(0, 0, 0, &rq->cfs.avg, p);
+	if (migrated)

IMHO, you don't need 'bool __maybe_unused migrated'. You can use:

if (flags & ENQUEUE_MIGRATED)

kernel/sched/fair.c static void migrate_task_rq_fair(struct task_struct *p, int new_cpu) · line 8260

Quoted 11 lines

kernel/sched/fair.c +4 -0

+		rq->root_cfs_util_uclamp += p->se.avg.util_avg_uclamp;
+	rq->root_cfs_util_uclamp = max(rq->root_cfs_util_uclamp,
+				       rq->cfs.avg.util_avg_uclamp);
  	/* TODO: Better skip the frequency update in the for loop above. */
  	cpufreq_update_util(rq, 0);
  #endif

@@ -8252,6 +8257,7 @@ static void migrate_task_rq_fair(struct task_struct *p, int new_cpu)
  		migrate_se_pelt_lag(se);
  	}
 
+	remove_root_cfs_util_uclamp(p);

You can't always do this here. In the '!task_on_rq_migrating()' case we don't hold the 'old' rq->lock.

Have a look into remove_entity_load_avg() for what we do for PELT in this case.

And:

144d8487bc6e ("sched/fair: Implement synchonous PELT detach on load-balance migrate") e1f078f50478 ("sched/fair: Combine detach into dequeue when migrating task")

[...]

kernel/sched/pelt.c ___update_load_avg(struct sched_avg *sa, unsigned long load) · line 330

Quoted 8 lines

/* avg must belong to the queue this se is on. */

kernel/sched/pelt.c +5 -1

-void update_util_uclamp(struct sched_avg *avg, struct task_struct *p)
+void update_util_uclamp(u64 now,
+			u64 last_update_time,
+			u32 period_contrib,
+			struct sched_avg *avg,
+			struct task_struct *p)
  {

I was wondering why you use such a long parameter list for this function.

IMHO

update_util_uclamp(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se)

would work as well. You could check whether se represents a task inside update_util_uclamp() as well as get last_update_time and period_contrib.

The only reason I see is that you want to use this function for the RT class as well later, where you have to deal with 'struct rt_rq' and 'struct sched_rt_entity'.

IMHO, it's always better to keep the implementation to the minimum and only introduce changes which are related to the functionality you present. This would make reviewing so much easier.

Quoted 4 lines

unsigned int util, uclamp_min, uclamp_max; int delta;

kernel/sched/pelt.c ___update_load_avg(struct sched_avg *sa, unsigned long load) · line 341

Quoted 9 lines

kernel/sched/pelt.c +7 -1

-	if (!p->se.on_rq)
+	if (!p->se.on_rq) {
+		___update_util_uclamp_towards(now,
+					      last_update_time,
+					      period_contrib,
+					      &p->se.avg.util_avg_uclamp,
+					      0);
  		return;
+	}

You decay 'p->se.avg.util_avg_uclamp' which is not really related to root_cfs_util_uclamp (patch header). IMHO, this would belong to 2/7.

This is the util_avg_uclamp handling for a se (task):

enqueue_task_fair()

   util_uclamp_enqueue()

   update_util_uclamp()                 (1)

     if (!p->se.on_rq)                  (x)
       ___update_util_uclamp_towards()  (2)

dequeue_task_fair()

util_uclamp_dequeue()

__update_load_avg_blocked_se()

   update_util_uclamp()

     (x)

__update_load_avg_se()

   update_util_uclamp()

     (x)

Why is it so unbalanced? Why do you need (1) and (2)?

Isn't this just an indication that the se util_avg_uclamp is done at the wrong places?

Is there an other way to provide a task/rq signal as the base for uclamp sum aggregation?

[...]

Quoted 15 lines · Dietmar Eggemann

On 01/02/2024 14:11, Hongyan Xia wrote:

[...]

kernel/sched/fair.c enqueue_task_fair(struct rq *rq, struct · line 6774

Quoted 8 lines

      /*
       * The code below (indirectly) updates schedutil which looks at

kernel/sched/fair.c +1 -0

@@ -6769,6 +6770,10 @@ enqueue_task_fair(struct rq *rq, struct
 task_struct *p, int flags)
   #ifdef CONFIG_UCLAMP_TASK
       util_uclamp_enqueue(&rq->cfs.avg, p);
       update_util_uclamp(0, 0, 0, &rq->cfs.avg, p);
+    if (migrated)

IMHO, you don't need 'bool __maybe_unused migrated'. You can use:

Quoted 1 line

   if (flags & ENQUEUE_MIGRATED)

I'm not sure if they are entirely equivalent. Both task_on_rq_migrating() and !task_on_rq_migrating() can have last_update_time == 0 but ENQUEUE_MIGRATED flag is only for the former. Maybe I'm missing something?

Quoted 20 lines

Quoted 8 lines

  /* avg must belong to the queue this se is on. */

kernel/sched/pelt.c +5 -1

-void update_util_uclamp(struct sched_avg *avg, struct task_struct *p)
+void update_util_uclamp(u64 now,
+            u64 last_update_time,
+            u32 period_contrib,
+            struct sched_avg *avg,
+            struct task_struct *p)

  {

I was wondering why you use such a long parameter list for this function.

IMHO

   update_util_uclamp(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se)

would work as well. You could check whether se represents a task inside update_util_uclamp() as well as get last_update_time and period_contrib.

Quoted 7 lines

The only reason I see is that you want to use this function for the RT class as well later, where you have to deal with 'struct rt_rq' and 'struct sched_rt_entity'.

IMHO, it's always better to keep the implementation to the minimum and only introduce changes which are related to the functionality you present. This would make reviewing so much easier.

Those parameters are necessary because of

if (___update_load_sum()) {
    ___update_load_avg();
    update_util_uclamp();
}

We have to cache last_update_time and period_contrib, because after ___update_load_sum() is done, both parameters in sched_avg have already been updated and overwritten and we lose the timestamp when the sched_avg was previously updated. update_util_uclamp() needs to know when sched_avg was previously updated.

Quoted 13 lines

Quoted 12 lines

      unsigned int util, uclamp_min, uclamp_max; int delta;
  -    if (!p->se.on_rq)
+    if (!p->se.on_rq) {
+        ___update_util_uclamp_towards(now,
+                          last_update_time, +                          period_contrib,
+                          &p->se.avg.util_avg_uclamp, +                          0);
          return;
+    }

Quoted 2 lines

You decay 'p->se.avg.util_avg_uclamp' which is not really related to root_cfs_util_uclamp (patch header). IMHO, this would belong to 2/7.

I would say this still belongs to 3/7, because 2/7 only implements utilization for on_rq tasks. This patch implements utilization for both on_rq and !on_rq. For rq, we have rq->cfs.avg.util_avg_uclamp (for on_rq) and rq->root_cfs_util_uclamp (for on_rq plus !on_rq).

For tasks, we also have two utilization numbers, one is on_rq and the other is on_rq plus !on_rq. However, we know they do not have to be stored in separate variables and util_avg_uclamp can capture both.

Moving this to 2/7 might be fine, although then this would be the only !on_rq utilization in 2/7. I can add comments to clarify the situation.

Quoted 29 lines

This is the util_avg_uclamp handling for a se (task):

enqueue_task_fair()

   util_uclamp_enqueue()

   update_util_uclamp()                 (1)

     if (!p->se.on_rq)                  (x)
       ___update_util_uclamp_towards()  (2)

dequeue_task_fair()

   util_uclamp_dequeue()

__update_load_avg_blocked_se()

   update_util_uclamp()

     (x)

__update_load_avg_se()

   update_util_uclamp()

     (x)

Why is it so unbalanced? Why do you need (1) and (2)?

Quoted 5 lines

Isn't this just an indication that the se util_avg_uclamp is done at the wrong places?

Is there an other way to provide a task/rq signal as the base for uclamp sum aggregation?

(2) won't happen, because at that point p->se.on_rq must be 1.

The sequence during enqueue_task_fair() is:

enqueue_task_fair(p)
    enqueue_entity(se)
        update_load_avg(se)
            update_util_uclamp(p) (decay path)
        p->se.on_rq = 1;
    util_uclamp_enqueue(p)
    update_util_uclamp(p) (update path)

The only reason why we want to issue update_util_uclamp() after seeing on_rq == 1 is that now it goes down the normal uclamp path and not the decay path. Otherwise, uclamp won't immediately engage during enqueue and has to wait a timer tick.

Ideally, we should:

enqueue_task_fair(p)
    enqueue_entity(se)
        update_load_avg(se) util_uclamp_enqueue(p) update_util_uclamp(p) (force update path) p->se.on_rq = 1;

This requires us to invent a new flag to update_util_uclamp() to force the update path even when p->se.on_rq is 0.

At the moment I'm treating util_avg_uclamp in the same way as util_est after the comments in v1, which is independent and has its own code path. We can go back to the old style, where util_avg_uclamp is closer to how we treat se rather than a separate thing like util_est.

Quoted 16 lines · Hongyan Xia

Quoted 15 lines · Dietmar Eggemann

On 01/02/2024 14:11, Hongyan Xia wrote:

[...]

kernel/sched/fair.c enqueue_task_fair(struct rq *rq, struct · line 6774

Quoted 8 lines

      /*
       * The code below (indirectly) updates schedutil which looks at

kernel/sched/fair.c +1 -0

@@ -6769,6 +6770,10 @@ enqueue_task_fair(struct rq *rq, struct
 task_struct *p, int flags)
   #ifdef CONFIG_UCLAMP_TASK
       util_uclamp_enqueue(&rq->cfs.avg, p);
       update_util_uclamp(0, 0, 0, &rq->cfs.avg, p);
+    if (migrated)

IMHO, you don't need 'bool __maybe_unused migrated'. You can use:

Quoted 6 lines

Quoted 1 line

   if (flags & ENQUEUE_MIGRATED)

I'm not sure if they are entirely equivalent. Both task_on_rq_migrating() and !task_on_rq_migrating() can have last_update_time == 0 but ENQUEUE_MIGRATED flag is only for the former. Maybe I'm missing something?

That's true. There are 2:

   (!task_on_rq_migrating() && !p->se.avg.last_update_time)

cases:

(1) wakeup migration: ENQUEUE_MIGRATED (0x40) set in ttwu_do_wakeup()

(2) new task: wake_up_new_task() -> activate_task(), ENQUEUE_MIGRATED is not set.

I assume you want to add the task's util_avg_uclamp to rq->root_cfs_util_uclamp in (2) too? So:

     if (flags & ENQUEUE_MIGRATED || task_new)

[...]

Quoted 28 lines

Quoted 20 lines

kernel/sched/pelt.c ___update_load_avg(struct sched_avg *sa, unsigned long load) · line 330

Quoted 8 lines

  /* avg must belong to the queue this se is on. */

kernel/sched/pelt.c +5 -1

-void update_util_uclamp(struct sched_avg *avg, struct task_struct *p)
+void update_util_uclamp(u64 now,
+            u64 last_update_time,
+            u32 period_contrib,
+            struct sched_avg *avg,
+            struct task_struct *p)
   {

I was wondering why you use such a long parameter list for this function.

IMHO

   update_util_uclamp(u64 now, struct cfs_rq *cfs_rq, struct
sched_entity *se)

would work as well. You could check whether se represents a task inside update_util_uclamp() as well as get last_update_time and period_contrib.

Quoted 7 lines

The only reason I see is that you want to use this function for the RT class as well later, where you have to deal with 'struct rt_rq' and 'struct sched_rt_entity'.

IMHO, it's always better to keep the implementation to the minimum and only introduce changes which are related to the functionality you present. This would make reviewing so much easier.

Quoted 6 lines

Those parameters are necessary because of

if (___update_load_sum()) {
    ___update_load_avg();
    update_util_uclamp();
}

So you need ___update_load_avg() happening for the normal uclamp path and last_uptade_time and period_contrib for the decay path (1) of update_util_uclamp()?

This is pretty hard to grasp. Isn't there a cleaner solution for this?

Why do you need the:

   if (!avg)
     return;

thing in update_util_uclamp()? __update_load_avg_blocked_se() calls update_util_uclamp(..., avg = NULL, ...) but this should follow (1)?

Quoted 19 lines

We have to cache last_update_time and period_contrib, because after ___update_load_sum() is done, both parameters in sched_avg have already been updated and overwritten and we lose the timestamp when the sched_avg was previously updated. update_util_uclamp() needs to know when sched_avg was previously updated.

Quoted 13 lines

Quoted 12 lines

      unsigned int util, uclamp_min, uclamp_max; int delta;
  -    if (!p->se.on_rq)
+    if (!p->se.on_rq) {
+        ___update_util_uclamp_towards(now,
+                          last_update_time, +                          period_contrib,
+                          &p->se.avg.util_avg_uclamp, +                          0);
          return;
+    }

Quoted 7 lines

Quoted 2 lines

You decay 'p->se.avg.util_avg_uclamp' which is not really related to root_cfs_util_uclamp (patch header). IMHO, this would belong to 2/7.

I would say this still belongs to 3/7, because 2/7 only implements utilization for on_rq tasks. This patch implements utilization for both on_rq and !on_rq. For rq, we have rq->cfs.avg.util_avg_uclamp (for on_rq) and rq->root_cfs_util_uclamp (for on_rq plus !on_rq).

Looks like you maintain rq->cfs.avg.util_avg_uclamp (2) (consider all runnable tasks) to be able to:

(a) set rq->root_cfs_util_uclamp (3) to max((3), (2))

(b) check that if 'rq->cfs.h_nr_running == 0' that (2) = 0 too.

uclamp is based on runnable tasks (so enqueue/dequeue) but you uclamp around util_avg which has contributions from blocked tasks. And that's why you have to maintain (3). And (3) only decays within __update_load_avg_cfs_rq().
Can this be the reason why th implementation is so convoluted? It's definitely more complicated than util_est with its easy layout:

enqueue_task_fair()
util_est_enqueue()

dequeue_task_fair()
util_est_dequeue()
util_est_update()

Quoted 3 lines

For tasks, we also have two utilization numbers, one is on_rq and the other is on_rq plus !on_rq. However, we know they do not have to be stored in separate variables and util_avg_uclamp can capture both.

Here you lost me. Which value does 'p->se.avg.util_avg_uclamp' store? 'runnable' or 'runnable + blocking'? I would say it's the latter one but like in PELT we don't update the task signal when it's sleeping.

Quoted 32 lines

Moving this to 2/7 might be fine, although then this would be the only !on_rq utilization in 2/7. I can add comments to clarify the situation.

Quoted 29 lines

This is the util_avg_uclamp handling for a se (task):

enqueue_task_fair()

   util_uclamp_enqueue()

   update_util_uclamp()                 (1)

     if (!p->se.on_rq)                  (x)
       ___update_util_uclamp_towards()  (2)

dequeue_task_fair()

   util_uclamp_dequeue()

__update_load_avg_blocked_se()

   update_util_uclamp()

     (x)

__update_load_avg_se()

   update_util_uclamp()

     (x)

Why is it so unbalanced? Why do you need (1) and (2)?

Quoted 7 lines

Quoted 5 lines

Isn't this just an indication that the se util_avg_uclamp is done at the wrong places?

Is there an other way to provide a task/rq signal as the base for uclamp sum aggregation?

(2) won't happen, because at that point p->se.on_rq must be 1.

I see.

Quoted 10 lines

The sequence during enqueue_task_fair() is:

enqueue_task_fair(p)
    enqueue_entity(se)
        update_load_avg(se)
            update_util_uclamp(p) (decay path)
        p->se.on_rq = 1;
    util_uclamp_enqueue(p)
    update_util_uclamp(p) (update path)

Quoted 4 lines

The only reason why we want to issue update_util_uclamp() after seeing on_rq == 1 is that now it goes down the normal uclamp path and not the decay path. Otherwise, uclamp won't immediately engage during enqueue and has to wait a timer tick.

OK, I see, the task contribution should be visible immediately after the enqueue.

Quoted 9 lines

Ideally, we should:

enqueue_task_fair(p)
    enqueue_entity(se)
        update_load_avg(se) util_uclamp_enqueue(p) update_util_uclamp(p) (force update path) p->se.on_rq = 1;

Quoted 2 lines

This requires us to invent a new flag to update_util_uclamp() to force the update path even when p->se.on_rq is 0.

I guess you have to go this way to achieve a cleaner/easier integration of 'util_avg_uclamp'.

Quoted 4 lines

At the moment I'm treating util_avg_uclamp in the same way as util_est after the comments in v1, which is independent and has its own code path. We can go back to the old style, where util_avg_uclamp is closer to how we treat se rather than a separate thing like util_est.

Except that 'util_est' integration is much easier to understand. And this is because of 'util_est' is clear runnable based only and is not linked to any blocked part.

[...]

On 01/02/2024 14:12, Hongyan Xia wrote:

[...]

Review static int select_idle_sibling(struct task_struct *p, int prev, int target) · line 7703

Quoted 10 lines

(quoted diff) +4 -2

@@ -7685,11 +7697,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);
+	struct cfs_rq *cfs_rq = &rq->cfs;
+	unsigned long util = root_cfs_util(rq);
+	bool capped = uclamp_rq_is_capped(rq);

I try to rerun your tests in your 2 ipynbs (cover letter) but this let's the sum aggr stack go sideways ...

if 'sched_uclamp_used' then uclamp_rq_is_capped() will call cpu_util_cfs()->cpu_util() which then calls uclamp_rq_is_capped() recursively resulting in a stack overflow.

Do you have a fix for that you can share? For the time I remove the call to uclamp_rq_is_capped() in cpu_util().

[...]

[1]: https://lore.kernel.org/all/[email protected]/

[2]: https://android.googlesource.com/kernel/gs/+/refs/heads/android-gs-raviole-5.10-android12-d1/drivers/soc/google/vh/kernel/sched/fair.c#510

Quoted 1 line · Hongyan Xia

[1]: https://lore.kernel.org/all/[email protected]/

Their solution is not acceptable for the same reason yours isn't. Saravana and David know this and we discussed at LPC. uclamp hints are limits and should not be summed.

Quoted 1 line

[2]: https://android.googlesource.com/kernel/gs/+/refs/heads/android-gs-raviole-5.10-android12-d1/drivers/soc/google/vh/kernel/sched/fair.c#510

I think I clarified several times so far that this is not related to uclamp. Could you please refrain from referring to it again in the future? This is misleading and neither helps your cause nor its cause. The fact that you're relating to it makes me very worried as both links demonstrate lack of understanding/confusion of what uclamp is supposed to be.

Again, this solution is not acceptable and you're moving things in the wrong direction. We don't want to redesign what uclamp means, but fix some corner cases. And you're doing the former not the latter.

Quoted 7 lines · Qais Yousef

Quoted 1 line · Hongyan Xia

[1]: https://lore.kernel.org/all/[email protected]/

Their solution is not acceptable for the same reason yours isn't. Saravana and David know this and we discussed at LPC. uclamp hints are limits and should not be summed.

Uclamp is a performance hint and nothing in its definition says it can't be

summed. Clearly whether a uclamp approach should be taken should be determined by how well it works as a hint, not by how we calculate it. I would not say I want to reject max aggregation simply because it throws away all other uclamp values except the max. It's because I have real evaluation results showing sum aggregation works as a much better hint.

Quoted 8 lines

Quoted 2 lines

[2]: https://android.googlesource.com/kernel/gs/+/refs/heads/android-gs-raviole-5.10-android12-d1/drivers/soc/google/vh/kernel/sched/fair.c#510

I think I clarified several times so far that this is not related to uclamp. Could you please refrain from referring to it again in the future? This is misleading and neither helps your cause nor its cause. The fact that you're relating to it makes me very worried as both links demonstrate lack of understanding/confusion of what uclamp is supposed to be.

The intention of the code is irrelevant. What I'm talking about is what

effect the code actually has. The fact that you keep thinking I don't understand what the code does even after me explaining "I know what the intention of the code is, I'm just talking about the actual effect of the code" is an even more worrying sign.

Quoted 3 lines

Again, this solution is not acceptable and you're moving things in the wrong direction. We don't want to redesign what uclamp means, but fix some corner cases. And you're doing the former not the latter.

I'm saying max aggregation is not effective and proposing a more effective implementation. In fact, you have sent a series that removes max aggregation. Clearly that does not count as fixing corner cases but is actually a redesign, and I don't understand why you are allowed to do such things and I am not. Also, when something becomes harder and harder to fix, a redesign that solves all the problems is clearly justified.

What I can summarize from sum aggregation is:

Pros:
1. A more effective implementation, proven by evaluation numbers
2. Consuming the same or even less power in benchmarks
3. 350 lines of code in total, less than half of max aggregation
4. This series shows the entirety and effectiveness of sum aggregation, at this very moment, today. Max aggregation needs further filtering and load balancing patches which we have not seen yet.
5. Resolves the drawbacks from max aggregation (which you might say is the same as 4)
6. Significantly reduces uclamp overhead, no bucket operations

Cons:
1. should not be summed (although the scheduler used to sum up utilization and util_est sums up a processed PELT signal today)
2. Under-utilization case (which is a problem GROUP_THROTTLE also has, and can be worked around. Please, I know the intention of GROUP_THROTTLE, I'm just talking about its actual effects).

I don't see why the things I listed above is in the wrong direction.

Quoted 9 lines · Hongyan Xia

Quoted 7 lines · Qais Yousef

Quoted 1 line · Hongyan Xia

[1]: https://lore.kernel.org/all/[email protected]/

Their solution is not acceptable for the same reason yours isn't. Saravana and David know this and we discussed at LPC. uclamp hints are limits and should not be summed.

Quoted 1 line

Uclamp is a performance hint and nothing in its definition says it can't be

That's the major problem here. The definition says it can't be summed because they're limits. So if two tasks boosted to 1024, then their combined performance limit is 2048? Or if 4 tasks are capped to 512, then the combined limits is 2048? You're changing the behavior. If not, please help me understand how not. You're treating them as 'bandwidth' hints.

Quoted 5 lines

summed. Clearly whether a uclamp approach should be taken should be determined by how well it works as a hint, not by how we calculate it. I would not say I want to reject max aggregation simply because it throws away all other uclamp values except the max. It's because I have real evaluation results showing sum aggregation works as a much better hint.

It is easy to get numbers that shows improvements. That doesn't necessarily mean it is correct.

Quoted 10 lines

Quoted 8 lines

Quoted 2 lines

[2]: https://android.googlesource.com/kernel/gs/+/refs/heads/android-gs-raviole-5.10-android12-d1/drivers/soc/google/vh/kernel/sched/fair.c#510

I think I clarified several times so far that this is not related to uclamp. Could you please refrain from referring to it again in the future? This is misleading and neither helps your cause nor its cause. The fact that you're relating to it makes me very worried as both links demonstrate lack of understanding/confusion of what uclamp is supposed to be.

The intention of the code is irrelevant. What I'm talking about is what

It is relevant.

1. You failed to get consent on using this an example.
2. You failed to demonstrate the purpose of the code and why it was actually added. I don't think you know the full details anyway.
3. You're using a hack that is problematic and needs to be deleted as a proof of something good that _we do not want_.
4. How do you know it works as you think it is? You're making wrong assumptions that are misleading and quite frankly annoying.

Generally we don't want to discuss this in this venue. So for the last time please stop bringing it up altogether and let's focus on the problems you are seeing and trying to fix and leave other people's code out of the discussion.

Quoted 9 lines

effect the code actually has. The fact that you keep thinking I don't understand what the code does even after me explaining "I know what the intention of the code is, I'm just talking about the actual effect of the code" is an even more worrying sign.

Quoted 3 lines

Again, this solution is not acceptable and you're moving things in the wrong direction. We don't want to redesign what uclamp means, but fix some corner cases. And you're doing the former not the latter.

Quoted 6 lines

I'm saying max aggregation is not effective and proposing a more effective implementation. In fact, you have sent a series that removes max aggregation. Clearly that does not count as fixing corner cases but is actually a redesign, and I don't understand why you are allowed to do such things and I am not. Also, when something becomes harder and harder to fix, a redesign that solves all the problems is clearly justified.

I don't have issues with max aggregation removal. I actually would love to see it gone. But summing uclamp values changes the meaning of uclamp hints. Which is my number 1 concern.

And you're lumping too many problems to max aggregations. It was brought up several times that overutilized definition being tied to misfit is not fit for purpose anymore. This needs to be fixed. feec() fails to distribute fairly when capacities are equal. This is a known old problem. This needs fixing. energy computation needs to evolve to deal with a number of new realities. This needs fixing. Load balancer can't correct bad decision at wake up in aligned way with feec(), this needs fixing. Adding a new signal is not the right way to fix these problems. And the only issue with max-aggregation in practice is the fact it is not effective in restricting power use for uclamp_max. It has also the minor problem of boosting unnecessarily for the duration of enqueue of the task. The correct behavior we want and other vendors has expressed to me in the

past is to apply the boost/cap only when required; ie the task is running. The hardware can cope with this. And this is tied to how cpufreq governor works and if there are hardware limitations that makes this hard to achieve, then it is up to the governor to decide this, not the scheduler. We already have util_avg and util_est. I really don't think we need another addition. We just need to fix issues else where and improve the interface with the cpufreq governor to honour the performance limits the tasks have so that we can get rid off max-aggregation.

Quoted 22 lines

What I can summarize from sum aggregation is:

Pros:
1. A more effective implementation, proven by evaluation numbers
2. Consuming the same or even less power in benchmarks
3. 350 lines of code in total, less than half of max aggregation
4. This series shows the entirety and effectiveness of sum aggregation, at this very moment, today. Max aggregation needs further filtering and load balancing patches which we have not seen yet.
5. Resolves the drawbacks from max aggregation (which you might say is the same as 4)
6. Significantly reduces uclamp overhead, no bucket operations

Cons:
1. should not be summed (although the scheduler used to sum up utilization and util_est sums up a processed PELT signal today)
2. Under-utilization case (which is a problem GROUP_THROTTLE also has, and can be worked around. Please, I know the intention of GROUP_THROTTLE, I'm just talking about its actual effects).

I don't see why the things I listed above is in the wrong direction.

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

1. Max aggregation only takes into account the max uclamp value. All other uclamp values are not in effect.
2. Uclamp max aggregation gives UCLAMP_MIN and UCLAMP_MAX at the rq level, and whether that translates to the desired performance of a specific task is unknown, because it depends on other tasks on rq.
3. Complexity. Uclamp max aggregation now sits at more than 750 lines of code and there is ongoing work to rework several interfaces to prepare for further uclamp changes. Uclamp max aggregation itself also needs future improvements in uclamp filtering and load balancing

The first 2 points can manifest into the following symptoms,

1. High-rate OPP changes ("frequency spike" problem). An always-running task with a UCLAMP_MAX of 200 will drive the CPU at 200 even though its utilization is 1024. However, when a util_avg task of 300 but with default UCLAMP_MAX of 1024 joins the rq, the rq UCLAMP_MAX will be uncapped, and the UCLAMP_MAX of the first task is no longer in effect therefore driving the CPU at 1024, the highest OPP. When the second task sleeps, the OPP will be reduced to 200. This fast and sudden OPP switch every time the 2nd task wakes up or sleeps is unnecessary.
2. Using UCLAMP_MIN to boost performance under max aggregation has been shown to have weaker effectiveness than "sum aggregated" approaches, including the util_guest proposal [1] and uclamp sum aggregation in this series. The performance level of UCLAMP_MIN for a task under max aggregation is unpredictable when there are more than 1 task runnable on the rq.

This series solves these problems by tracking a util_avg_uclamp signal in tasks and root 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, rq->cfs.avg.util_avg_uclamp is the sum aggregation of all the clamped values, which hints the frequency this rq should run at and what the utilization is. This proposal has some similarities to the util_guest series for VM workloads, in that it brings the desired performance to the task that requested it, not to the rq, in which the share of the task is unpredictable.

Note: This new signal does not change the existing PELT signal. The new signal is only an extra hint to the scheduler to improve scheduling decisions.

TL;DR OF THIS SERIES:

- Our evaluation shows significantly better effectiveness than max aggregation. UI benchmarks and VM workloads have improved latency and higher scores at the same or even reduced power consumption.
- For other benchmarks that do not involve uclamp, we have not observed any noticeable regressions.
- This series is the entirety of sum aggregation. No groundwork or refactoring in the scheduler is needed. The complexity of several existing uclamp-related functions is massively reduced and sum aggregation code is less than half of that in max aggregation (304+, 701-). The complexity gap will be even greater with all the ongoing patches for max aggregation.

DECOMPOSITION OF SUM AGGREGATION:

- Patch 1 reverts some max aggregation code. Sum aggregation shows no

such problems so mitigation patches are not necessary, and that patch has other undesirable side effects.
- Patch 2 and 3 introduce new sum aggregated signals to be a more effective hint to the scheduler. Patch 3 employs a math trick to make it significantly simpler to track on-rq and off-rq task utilization contributions.
- Patch 4, 5 and 6 start using the new signal while significantly simplifying existing uclamp code, including the total removal of uclamp buckets and max aggregation.
- Patch 7 and part of 6 remove the overhead of uclamp on task enqueue and dequeue, because uclamp values and buckets no longer need to be re-computed every time a uclamp'ed task joins or leaves the rq.

TESTING:

Sum aggregation generally performs better in tests. Two notebooks, max vs. sum aggregation, are shared at

https://nbviewer.org/github/honxia02/notebooks/blob/618de22a8da96205015fefabee203536683bd4e2/whitebox/max.ipynb
https://nbviewer.org/github/honxia02/notebooks/blob/618de22a8da96205015fefabee203536683bd4e2/whitebox/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]. Both max and sum aggregation recognizes the UCLAMP_MAX hints and run all the threads on the little Performance Domain (PD). However, max aggregation in the test shows some randomness in task placement, and we see the 4 threads are often not evenly distributed across the 4 little CPUs. This uneven task placement is also the reason why we revert the patch:

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

When the spare capacity is 0, the reverted patch tends to gather many tasks on the same CPU because its EM calculation is bogus and it thinks this placement is more energy efficient.

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]. The purpose is to use UCLAMP_MIN to place tasks on the big core but not to run at the highest OPP. Both max and sum aggregation accomplish this task successfully, running the two threads at the big cluster while not driving the frequency at the max.

Scenario 3: Task A is a task with a small utilization pinned to CPU4. Task B is an always-running task pinned to CPU5, but UCLAMP_MAX capped at 300. After a while, task A is then pinned to CPU5, joining B.

Results are in Out[23]. The util_avg curve is the original root CFS util_avg. The root_cfs_util_uclamp is the root CFS utilization after considering uclamp. Max aggregation sees a frequency spike at 751.7s. When zoomed in, one can see square-wave-like utilization and CPU

frequency values because of task 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 300. This happens repeatedly, hence the square wave. In contrast, sum aggregation sees a normal increase in

utilization when A joins B, at around 430.64s, without any square-wave behavior. The CPU frequency also stays stable while the two tasks are on the same rq.

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]. Both max and sum aggregation understand that we can move the 4 tasks from the big PD to the little PD to reduce power because of the UCLAMP_MAX hints. However, max aggregation shows severely unbalanced task placement, scheduling 5 tasks on CPU0 while 1 each on CPU1-3. Sum aggregation schedules 2 tasks on each little CPU, honoring UCLAMP_MAX while maintaining balanced task placement.

Again, this unbalanced task placement is the reason why we reverted:

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

Scenario 5: 8 tasks with UCLAMP_MAX of 120.

This test is similar to Scenario 4, shown in Out[35]. Both max and sum aggregation understand the UCLAMP_MAX hints and schedule all tasks on the 4 little CPUs. Max aggregation again shows unstable and unbalanced task placement while sum aggregation schedules 2 tasks on each little CPU, and the task placement remains stable. The total task residency is shown in Out[36], showing how unbalanced max aggregation is.

BENCHMARKS:

Geekbench 6, no uclamp (on Rock-5B board)

+-----+-------------+------------+
|     | Single-core | Multi-core |
+-----+-------------+------------+
| Max |      801.3  |     2976.8 |
| Sum |      802.8  |     2989.2 |
+-----+-------------+------------+

No regression is seen after switching to sum aggregation.

Jankbench (backporting sum aggregation to Pixel 6 Android 5.18 mainline kernel):

Jank percentage:

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

Average power:

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

UIBench (backporting sum aggregation to Pixel 6 Android 6.6 mainline kernel):

Jank percentage:

+-------------+-------+-----------+
|      tag    | value | perc_diff |
+-------------+-------+-----------+
|   max_aggr  |  0.3  |    0.0    |
|   sum_aggr  |  0.26 |   -12.5   |
+-------------+-------+-----------+

Average input latency:

+-------------+--------+-----------+
|      tag    | value  | perc_diff |
+-------------+--------+-----------+
|   max_aggr  | 107.39 |    0.0    |
|   sum_aggr  | 81.135 |   -24.5   |
+-------------+--------+-----------+

Average power:

+------------+--------------+--------+-----------+
|  channel   |     tag      | value  | perc_diff |
+------------+--------------+--------+-----------+
|    CPU     |   max_aggr   | 209.85 |   0.0%    |
|  CPU-Big   |   max_aggr   |  89.8  |   0.0%    |
| CPU-Little |   max_aggr   |  94.45 |   0.0%    |
|  CPU-Mid   |   max_aggr   |  25.45 |   0.0%    |
|    GPU     |   max_aggr   |  22.9  |   0.0%    |
|   Total    |   max_aggr   | 232.75 |   0.0%    |
|    CPU     |   sum_aggr   | 206.05 |  -1.81%   |
|  CPU-Big   |   sum_aggr   |  84.7  |  -5.68%   |
| CPU-Little |   sum_aggr   |  94.9  |   0.48%   |
|  CPU-Mid   |   sum_aggr   |  26.3  |   3.34%   |
|    GPU     |   sum_aggr   |  22.45 |  -1.97%   |
|   Total    |   sum_aggr   | 228.5  |  -1.83%   |
+------------+--------------+--------+-----------+

It should be noted that sum aggregation reduces jank and reduces input latency while consuming less power.

VM cpufreq hypercall driver [1], on Rock-5B board. Baseline indicates a setup without the VM cpufreq driver:

Geekbench 6 uncontended. No other host threads running.

+------+-------------+-----------+------------+-----------+
|      | Single-core | perc_diff | Multi-core | perc_diff |
+------+-------------+-----------+------------+-----------+
| base |      796.4  |         0 |     2947.0 |         0 |
|  max |      795.6  |     -0.10 |     2929.6 |     -0.59 |
|  sum |      794.6  |     -0.23 |     2935.6 |     -0.39 |
+------+-------------+-----------+------------+-----------+

Geekbench 6 contended. Host CPUs each has a 50% duty-cycle task running.

+------+-------------+-----------+------------+-----------+
|      | Single-core | perc_diff | Multi-core | perc_diff |
+------+-------------+-----------+------------+-----------+
| base |      604.6  |         0 |     2330.2 |         0 |
|  max |      599.4  |     -0.86 |     2327.2 |     -0.13 |
|  sum |      645.8  |      6.81 |     2336.6 |      0.27 |
+------+-------------+-----------+------------+-----------+

VM CPUfreq driver using sum aggregation outperforms max aggregation when the host is contended. When the host has no contention (only the VM vCPUs are running and each host CPU accommodates one guest vCPU), the two aggregation methods are roughly the same, and a bit surprisingly, offers no speed-up versus the baseline. This is probably because of the overhead of hypercalls, and the fact that Geekbench is CPU intensive and is not the best workload to show the effectiveness of VM cpufreq driver. We will try to benchmark on more VM workloads.

LIMITATIONS:

1. RT sum aggregation is not shown in the series.

A proof-of-concept RT sum aggregation implementation is done and going through testing, with < 50 lines of code, using the same ideas as in CFS. They will be sent out separately if we can agree on CFS sum aggregation and once the testing is done.

2. A heavily UCLAMP_MAX-throttled task may prevent the CFS rq from triggering over-utilization.

For example, two always-running task each having utilization of 512. If one of the task is severely UCLAMP_MAX restricted, say, with a UCLAMP_MAX of 1, then the total CFS sum aggregation will be 512 + 1 = 513, which won't trigger over-utilization even though the other task has no UCLAMP_MAX and wants more performance.

I'm working on a fix for this problem. This at the moment can be solved by either not giving long-running tasks ridiculously low UCLAMP_MAX values, or adjusting the priority of UCLAMP_MAX tasks to make sure it does not get a share of CPU run-time that vastly exceeds its UCLAMP_MAX. However, my personal view is that maybe UCLAMP_MIN and UCLAMP_MAX just don't belong together, and the proper way is to have a per-task

bandwidth throttling mechanism and what we want as UCLAMP_MAX maybe actually belongs to that mechanism.

However, since the Android GROUP_THROTTLE feature [2] has the exact same problem and has been used in actual products, we don't think this is a big limitation in practice.

[1]: https://lore.kernel.org/all/[email protected]/
[2]: https://android.googlesource.com/kernel/gs/+/refs/heads/android-gs-raviole-5.10-android12-d1/drivers/soc/google/vh/kernel/sched/fair.c#510

---
Changed in v2:
- Rework util_avg_uclamp to be closer to the style of util_est.
- Rewrite patch notes to reflect the new style.
- Add the discussion of the under-utilizated example in limitations, found by Vincent G.
- Remove task group uclamp to focus on tasks first.
- Fix several bugs in task migration.
- Add benchmark numbers from UIBench and VM cpufreq.
- Update python notebooks to reflect the latest max vs. sum aggregation.

Hongyan Xia (7):
Revert "sched/uclamp: Set max_spare_cap_cpu even if max_spare_cap is

    0"

sched/uclamp: Track uclamped util_avg in sched_avg sched/uclamp: Introduce root_cfs_util_uclamp for rq sched/fair: Use CFS util_avg_uclamp for utilization and frequency sched/fair: Massively simplify util_fits_cpu() sched/uclamp: Remove all uclamp bucket logic sched/uclamp: Simplify uclamp_eff_value()

 include/linux/sched.h            |   7 +-
 init/Kconfig                     |  32 ---
 kernel/sched/core.c              | 324 +++---------------------------
 kernel/sched/cpufreq_schedutil.c |  10 +-
 kernel/sched/fair.c              | 333 +++++++------------------------
 kernel/sched/pelt.c              | 144 ++++++++++++-
 kernel/sched/pelt.h              |   6 +-
 kernel/sched/rt.c                |   4 -
 kernel/sched/sched.h             | 145 ++++++--------
 9 files changed, 304 insertions(+), 701 deletions(-)

--
2.34.1

Quoted 32 lines · Hongyan Xia

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

1. Max aggregation only takes into account the max uclamp value. All other uclamp values are not in effect.
2. Uclamp max aggregation gives UCLAMP_MIN and UCLAMP_MAX at the rq level, and whether that translates to the desired performance of a specific task is unknown, because it depends on other tasks on rq.
3. Complexity. Uclamp max aggregation now sits at more than 750 lines of code and there is ongoing work to rework several interfaces to prepare for further uclamp changes. Uclamp max aggregation itself also needs future improvements in uclamp filtering and load balancing

The first 2 points can manifest into the following symptoms,

1. High-rate OPP changes ("frequency spike" problem). An always-running task with a UCLAMP_MAX of 200 will drive the CPU at 200 even though its utilization is 1024. However, when a util_avg task of 300 but with default UCLAMP_MAX of 1024 joins the rq, the rq UCLAMP_MAX will be uncapped, and the UCLAMP_MAX of the first task is no longer in effect therefore driving the CPU at 1024, the highest OPP. When the second task sleeps, the OPP will be reduced to 200. This fast and sudden OPP switch every time the 2nd task wakes up or sleeps is unnecessary.
2. Using UCLAMP_MIN to boost performance under max aggregation has been shown to have weaker effectiveness than "sum aggregated" approaches, including the util_guest proposal [1] and uclamp sum aggregation in this series. The performance level of UCLAMP_MIN for a task under max aggregation is unpredictable when there are more than 1 task runnable on the rq.

Quoted 11 lines

This series solves these problems by tracking a util_avg_uclamp signal in tasks and root 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, rq->cfs.avg.util_avg_uclamp is the sum aggregation of all the clamped values, which hints the frequency this rq should run at and what the utilization is. This proposal has some similarities to the util_guest series for VM workloads, in that it brings the desired performance to the task that requested it, not to the rq, in which the share of the task is unpredictable.

As I mentioned in your previous version, I don't want such mixed signals which are hard to maintain (as you then try to compensate for all side effects and compensate for some decaying as an example) and don't mean anything at the end. You must find another way if you want to go in that direction of sum aggregated.

Quoted 19 lines

Note: This new signal does not change the existing PELT signal. The new signal is only an extra hint to the scheduler to improve scheduling decisions.

TL;DR OF THIS SERIES:

- Our evaluation shows significantly better effectiveness than max aggregation. UI benchmarks and VM workloads have improved latency and higher scores at the same or even reduced power consumption.
- For other benchmarks that do not involve uclamp, we have not observed any noticeable regressions.
- This series is the entirety of sum aggregation. No groundwork or refactoring in the scheduler is needed. The complexity of several existing uclamp-related functions is massively reduced and sum aggregation code is less than half of that in max aggregation (304+, 701-). The complexity gap will be even greater with all the ongoing patches for max aggregation.

Quoted 3 lines

DECOMPOSITION OF SUM AGGREGATION:

- Patch 1 reverts some max aggregation code. Sum aggregation shows no

Sorry I don't get what you mean here by reverting some max aggregation code ? This is not really linked to max aggregation but how EAS and feec() try to compute energy

The code that is reverted here mainly highlights where your problem is and more generally speaking one of the problems of the current algorithm of EAS and feec() when it tries to estimate the energy cost. We don't take into account that an utilization becoming larger the cpu capacity means more running time. Such problem has been highlighted previously and is one root cause of the problems that you are trying to solve there

Quoted 34 lines

such problems so mitigation patches are not necessary, and that patch has other undesirable side effects.
- Patch 2 and 3 introduce new sum aggregated signals to be a more effective hint to the scheduler. Patch 3 employs a math trick to make it significantly simpler to track on-rq and off-rq task utilization contributions.
- Patch 4, 5 and 6 start using the new signal while significantly simplifying existing uclamp code, including the total removal of uclamp buckets and max aggregation.
- Patch 7 and part of 6 remove the overhead of uclamp on task enqueue and dequeue, because uclamp values and buckets no longer need to be re-computed every time a uclamp'ed task joins or leaves the rq.

TESTING:

Sum aggregation generally performs better in tests. Two notebooks, max vs. sum aggregation, are shared at

https://nbviewer.org/github/honxia02/notebooks/blob/618de22a8da96205015fefabee203536683bd4e2/whitebox/max.ipynb
https://nbviewer.org/github/honxia02/notebooks/blob/618de22a8da96205015fefabee203536683bd4e2/whitebox/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]. Both max and sum aggregation recognizes the UCLAMP_MAX hints and run all the threads on the little Performance Domain (PD). However, max aggregation in the test shows some randomness in task placement, and we see the 4 threads are often not evenly distributed across the 4 little CPUs. This uneven task placement is also the reason why we revert the patch:

Quoted 5 lines

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

When the spare capacity is 0, the reverted patch tends to gather many tasks on the same CPU because its EM calculation is bogus and it thinks this placement is more energy efficient.

So the problem is not max vs sum aggregation but fix feec()

Quoted 8 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]. The purpose is to use UCLAMP_MIN to place tasks on the big core but not to run at the highest OPP. Both max and sum aggregation accomplish this task successfully, running the two threads at the big cluster while not driving the frequency at the max.

No problem here

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

Quoted 4 lines

Results are in Out[23]. The util_avg curve is the original root CFS util_avg. The root_cfs_util_uclamp is the root CFS utilization after considering uclamp. Max aggregation sees a frequency spike at 751.7s. When zoomed in, one can see square-wave-like utilization and CPU

sidenote: there is no graph showed in your links so nothing to see or zoom

Quoted 5 lines

frequency values because of task 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 300. This happens repeatedly, hence the square wave. In contrast, sum aggregation sees a normal increase in

What do you mean by normal increase ?

Quoted 3 lines

utilization when A joins B, at around 430.64s, without any square-wave behavior. The CPU frequency also stays stable while the two tasks are on the same rq.

Difficult to make any comment as there is no graph to see in your link.

What should be the right frequency in such a case ?

Quoted 12 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]. Both max and sum aggregation understand that we can move the 4 tasks from the big PD to the little PD to reduce power because of the UCLAMP_MAX hints. However, max aggregation shows severely unbalanced task placement, scheduling 5 tasks on CPU0 while 1 each on CPU1-3. Sum aggregation schedules 2 tasks on each little CPU, honoring UCLAMP_MAX while maintaining balanced task placement.

Quoted 3 lines

Again, this unbalanced task placement is the reason why we reverted:

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

So then it's not a matter a sum vs max aggregation but to fix the EAS policy to place tasks correctly

Quoted 9 lines

Scenario 5: 8 tasks with UCLAMP_MAX of 120.

This test is similar to Scenario 4, shown in Out[35]. Both max and sum aggregation understand the UCLAMP_MAX hints and schedule all tasks on the 4 little CPUs. Max aggregation again shows unstable and unbalanced task placement while sum aggregation schedules 2 tasks on each little CPU, and the task placement remains stable. The total task residency is shown in Out[36], showing how unbalanced max aggregation is.

same comment as previous test

Quoted 115 lines

BENCHMARKS:

Geekbench 6, no uclamp (on Rock-5B board)

+-----+-------------+------------+
|     | Single-core | Multi-core |
+-----+-------------+------------+
| Max |      801.3  |     2976.8 |
| Sum |      802.8  |     2989.2 |
+-----+-------------+------------+

No regression is seen after switching to sum aggregation.

Jankbench (backporting sum aggregation to Pixel 6 Android 5.18 mainline kernel):

Jank percentage:

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

Average power:

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

UIBench (backporting sum aggregation to Pixel 6 Android 6.6 mainline kernel):

Jank percentage:

+-------------+-------+-----------+
|      tag    | value | perc_diff |
+-------------+-------+-----------+
|   max_aggr  |  0.3  |    0.0    |
|   sum_aggr  |  0.26 |   -12.5   |
+-------------+-------+-----------+

Average input latency:

+-------------+--------+-----------+
|      tag    | value  | perc_diff |
+-------------+--------+-----------+
|   max_aggr  | 107.39 |    0.0    |
|   sum_aggr  | 81.135 |   -24.5   |
+-------------+--------+-----------+

Average power:

+------------+--------------+--------+-----------+
|  channel   |     tag      | value  | perc_diff |
+------------+--------------+--------+-----------+
|    CPU     |   max_aggr   | 209.85 |   0.0%    |
|  CPU-Big   |   max_aggr   |  89.8  |   0.0%    |
| CPU-Little |   max_aggr   |  94.45 |   0.0%    |
|  CPU-Mid   |   max_aggr   |  25.45 |   0.0%    |
|    GPU     |   max_aggr   |  22.9  |   0.0%    |
|   Total    |   max_aggr   | 232.75 |   0.0%    |
|    CPU     |   sum_aggr   | 206.05 |  -1.81%   |
|  CPU-Big   |   sum_aggr   |  84.7  |  -5.68%   |
| CPU-Little |   sum_aggr   |  94.9  |   0.48%   |
|  CPU-Mid   |   sum_aggr   |  26.3  |   3.34%   |
|    GPU     |   sum_aggr   |  22.45 |  -1.97%   |
|   Total    |   sum_aggr   | 228.5  |  -1.83%   |
+------------+--------------+--------+-----------+

It should be noted that sum aggregation reduces jank and reduces input latency while consuming less power.

VM cpufreq hypercall driver [1], on Rock-5B board. Baseline indicates a setup without the VM cpufreq driver:

Geekbench 6 uncontended. No other host threads running.

+------+-------------+-----------+------------+-----------+
|      | Single-core | perc_diff | Multi-core | perc_diff |
+------+-------------+-----------+------------+-----------+
| base |      796.4  |         0 |     2947.0 |         0 |
|  max |      795.6  |     -0.10 |     2929.6 |     -0.59 |
|  sum |      794.6  |     -0.23 |     2935.6 |     -0.39 |
+------+-------------+-----------+------------+-----------+

Geekbench 6 contended. Host CPUs each has a 50% duty-cycle task running.

+------+-------------+-----------+------------+-----------+
|      | Single-core | perc_diff | Multi-core | perc_diff |
+------+-------------+-----------+------------+-----------+
| base |      604.6  |         0 |     2330.2 |         0 |
|  max |      599.4  |     -0.86 |     2327.2 |     -0.13 |
|  sum |      645.8  |      6.81 |     2336.6 |      0.27 |
+------+-------------+-----------+------------+-----------+

VM CPUfreq driver using sum aggregation outperforms max aggregation when the host is contended. When the host has no contention (only the VM vCPUs are running and each host CPU accommodates one guest vCPU), the two aggregation methods are roughly the same, and a bit surprisingly, offers no speed-up versus the baseline. This is probably because of the overhead of hypercalls, and the fact that Geekbench is CPU intensive and is not the best workload to show the effectiveness of VM cpufreq driver. We will try to benchmark on more VM workloads.

LIMITATIONS:

1. RT sum aggregation is not shown in the series.

A proof-of-concept RT sum aggregation implementation is done and going through testing, with < 50 lines of code, using the same ideas as in CFS. They will be sent out separately if we can agree on CFS sum aggregation and once the testing is done.

Quoted 8 lines

2. A heavily UCLAMP_MAX-throttled task may prevent the CFS rq from triggering over-utilization.

For example, two always-running task each having utilization of 512. If one of the task is severely UCLAMP_MAX restricted, say, with a UCLAMP_MAX of 1, then the total CFS sum aggregation will be 512 + 1 = 513, which won't trigger over-utilization even though the other task has no UCLAMP_MAX and wants more performance.

But what if they are pinned to the same CPU or other cpus are already fully busy ? This is a blocking point because the uclamp of one task then impacts the cpu bandwidth of another not clamped task

Quoted 7 lines

I'm working on a fix for this problem. This at the moment can be solved by either not giving long-running tasks ridiculously low UCLAMP_MAX values, or adjusting the priority of UCLAMP_MAX tasks to make sure it does not get a share of CPU run-time that vastly exceeds its UCLAMP_MAX. However, my personal view is that maybe UCLAMP_MIN and UCLAMP_MAX just don't belong together, and the proper way is to have a per-task

No this is a blocking point. We don't want to add dependency between nice priority and uclamp.

Quoted 6 lines

bandwidth throttling mechanism and what we want as UCLAMP_MAX maybe actually belongs to that mechanism.

However, since the Android GROUP_THROTTLE feature [2] has the exact same problem and has been used in actual products, we don't think this is a big limitation in practice.

This is not because an out of tree patchset is ok to go with a wrong behavior that it makes this patchset acceptable

Quoted 39 lines

[1]: https://lore.kernel.org/all/[email protected]/
[2]: https://android.googlesource.com/kernel/gs/+/refs/heads/android-gs-raviole-5.10-android12-d1/drivers/soc/google/vh/kernel/sched/fair.c#510

---
Changed in v2:
- Rework util_avg_uclamp to be closer to the style of util_est.
- Rewrite patch notes to reflect the new style.
- Add the discussion of the under-utilizated example in limitations, found by Vincent G.
- Remove task group uclamp to focus on tasks first.
- Fix several bugs in task migration.
- Add benchmark numbers from UIBench and VM cpufreq.
- Update python notebooks to reflect the latest max vs. sum aggregation.

Hongyan Xia (7):
Revert "sched/uclamp: Set max_spare_cap_cpu even if max_spare_cap is

     0"

sched/uclamp: Track uclamped util_avg in sched_avg sched/uclamp: Introduce root_cfs_util_uclamp for rq sched/fair: Use CFS util_avg_uclamp for utilization and frequency sched/fair: Massively simplify util_fits_cpu() sched/uclamp: Remove all uclamp bucket logic sched/uclamp: Simplify uclamp_eff_value()

  include/linux/sched.h            |   7 +-
  init/Kconfig                     |  32 ---
  kernel/sched/core.c              | 324 +++---------------------------
  kernel/sched/cpufreq_schedutil.c |  10 +-
  kernel/sched/fair.c              | 333 +++++++------------------------
  kernel/sched/pelt.c              | 144 ++++++++++++-
  kernel/sched/pelt.h              |   6 +-
  kernel/sched/rt.c                |   4 -
  kernel/sched/sched.h             | 145 ++++++--------
  9 files changed, 304 insertions(+), 701 deletions(-)

--
2.34.1