On Mon, Mar 19, 2018 at 12:24:09PM +0000, Patrick Bellasi wrote:

Hi Leo,

On 17-Mar 20:05, Leo Yan wrote:

...

Move out energy env cpumask setting from select_energy_cpu_idx() and prepare it ahead. This changes make code more clear, which can prepare energy environment variable before energy calculation.

Change-Id: I9061492177ad8d4830cf8bbdaffdf7860b27e319 Signed-off-by: Leo Yan leo.yan@linaro.org

---

kernel/sched/fair.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 315c386..37231b8 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5874,15 +5874,6 @@ static inline int select_energy_cpu_idx(struct energy_env *eenv) if (!sd) return EAS_CPU_PRV;

• cpumask_clear(&eenv->cpus_mask);
• for (cpu_idx = EAS_CPU_PRV; cpu_idx < EAS_CPU_CNT; ++cpu_idx) {

• int cpu = eenv->cpu[cpu_idx].cpu_id;
  

The intent to do it here and do it with a loop is because of that EAS_CPU_CNT definition, which should make it clear that potentially we can think about having more then 3 candidate we have not.

That's why also I don't agree that moving this block outside makes the code more clear...

I think we could connect this patch with patch 0006 'sched/fair: Use cpumask to track candidates for energy calculation'; so all cpumask should be initialized in function select_energy_cpu_brute().

We can take this patch as refactoring for 'preparing energy_env context' so we can have two distinguished steps: the first step is preparation eenv context (in func select_energy_cpu_brute()) and second step is energy calculation & comparison (in func select_energy_cpu_idx()).

Thanks, Leo Yan

...

• if (cpu < 0)
  

• 	continue;
  

• cpumask_set_cpu(cpu, &eenv->cpus_mask);
  

• }
• sg = sd->groups; do { /* Skip SGs which do not contains a candidate CPU */

@@ -7133,7 +7124,6 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync }, };

#ifdef CONFIG_SCHED_WALT if (!walt_disabled && sysctl_sched_use_walt_cpu_util && p->state == TASK_WAKING) @@ -7147,6 +7137,14 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync goto unlock; }

• cpumask_clear(&eenv.cpus_mask);
  

• if (prev_cpu >= 0)
  

• 	cpumask_set_cpu(prev_cpu, &eenv.cpus_mask);
  

• if (next_cpu >= 0)
  

• 	cpumask_set_cpu(next_cpu, &eenv.cpus_mask);
  

• if (backup_cpu >= 0)
  

• 	cpumask_set_cpu(backup_cpu, &eenv.cpus_mask);
  

• /* Check if EAS_CPU_NXT is a more energy efficient CPU */ if (select_energy_cpu_idx(&eenv) != EAS_CPU_PRV) { schedstat_inc(p->se.statistics.nr_wakeups_secb_nrg_sav);

-- 1.9.1

-- #include <best/regards.h>

Patrick Bellasi

On Mon, Mar 19, 2018 at 07:07:33AM +0100, Daniel Lezcano wrote:

On Sat, Mar 17, 2018 at 08:05:15PM +0800, Leo Yan wrote:

...

select_energy_cpu_idx() returns the target CPU index, and eenv->next_idx is used to define target CPU index as well; it's pointless to use two methods to return exactly same value.

This patch is to change the definition for return value of select_energy_cpu_idx(), errors return negative value and success returns 0. And later use eenv->next_idx for target CPU index.

Yes there is a duplication of the information. Actually, the change could be the contrary: make select_energy_cpu_idx return the cpu_idx and kill the next_idx field in the structure.

next_idx field is used only in the calling function, it could be stored in a local variable.

Yeah, good suggestion. Will fix in next version.

Thanks, Leo Yan

...

Change-Id: I57bc9c96566eaf6085c85ea9386d11422cafddbf Signed-off-by: Leo Yan leo.yan@linaro.org

---

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

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 37231b8..0f0b307 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5850,16 +5850,15 @@ static inline bool cpu_in_sg(struct sched_group *sg, int cpu)

• select_energy_cpu_idx(): estimate the energy impact of changing the
• utilization distribution.

• • The eenv parameter specifies the changes: utilisation amount and a pair of
• • possible CPU candidates (the previous CPU and a different target CPU).
• • This function returns the index of a CPU candidate specified by the

• • eenv::next_idx returns the index of a CPU candidate specified by the
  • energy_env which corresponds to the first CPU saving energy.
  • Thus, 0 (EAS_CPU_PRV) means that non of the CPU candidate is more energy

• • efficient than running on prev_cpu. This is also the value returned in case
• • of abort due to error conditions during the computations.
• • A value greater than zero means that the first energy-efficient CPU is the
• • one represented by eenv->cpu[eenv->next_idx].cpu_id.

• • efficient than running on prev_cpu. A value greater than zero means that
• • the first energy-efficient CPU is the one represented by
• • eenv->cpu[eenv->next_idx].cpu_id.
• • The function returns negative value in case of abort due to error
• • conditions during the computations, success returns 0.
  */

static inline int select_energy_cpu_idx(struct energy_env *eenv) { @@ -5871,8 +5870,10 @@ static inline int select_energy_cpu_idx(struct energy_env *eenv)

sd_cpu = eenv->cpu[EAS_CPU_PRV].cpu_id; sd = rcu_dereference(per_cpu(sd_ea, sd_cpu));

• if (!sd)

• return EAS_CPU_PRV;
  

• if (!sd) {

• eenv->next_idx = EAS_CPU_PRV;
  

• return -1;
  

• }

  sg = sd->groups; do {

@@ -5882,8 +5883,10 @@ static inline int select_energy_cpu_idx(struct energy_env *eenv)

eenv->sg_top = sg;
/* energy is unscaled to reduce rounding errors */

• if (compute_energy(eenv) == -EINVAL)
  

• 	return EAS_CPU_PRV;
  

• if (compute_energy(eenv) == -EINVAL) {
  

• 	eenv->next_idx = EAS_CPU_PRV;
  

• 	return -EINVAL;
  

• }
  
  

  } while (sg = sg->next, sg != sd->groups);

@@ -5929,7 +5932,7 @@ static inline int select_energy_cpu_idx(struct energy_env *eenv) } }

• return eenv->next_idx;

• return 0;

}

/* @@ -7145,17 +7148,18 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync if (backup_cpu >= 0) cpumask_set_cpu(backup_cpu, &eenv.cpus_mask);

• select_energy_cpu_idx(&eenv);
  

• /* Check if EAS_CPU_NXT is a more energy efficient CPU */

• if (select_energy_cpu_idx(&eenv) != EAS_CPU_PRV) {
  

• if (eenv.next_idx != EAS_CPU_PRV) {
  schedstat_inc(p->se.statistics.nr_wakeups_secb_nrg_sav);
  schedstat_inc(this_rq()->eas_stats.secb_nrg_sav);
  

• 	target_cpu = eenv.cpu[eenv.next_idx].cpu_id;
  

• 	goto unlock;
  

• } else {
  

• 	schedstat_inc(p->se.statistics.nr_wakeups_secb_no_nrg_sav);
  

• 	schedstat_inc(this_rq()->eas_stats.secb_no_nrg_sav);
  

  }

• schedstat_inc(p->se.statistics.nr_wakeups_secb_no_nrg_sav);
  

• schedstat_inc(this_rq()->eas_stats.secb_no_nrg_sav);
  

• target_cpu = prev_cpu;
  

• target_cpu = eenv.cpu[eenv.next_idx].cpu_id;
  

  goto unlock; }

-- 1.9.1

--

http://www.linaro.org/ Linaro.org │ Open source software for ARM SoCs

Follow Linaro: http://www.facebook.com/pages/Linaro Facebook | http://twitter.com/#!/linaroorg Twitter | http://www.linaro.org/linaro-blog/ Blog

On Mon, Mar 19, 2018 at 12:33:01PM +0000, Patrick Bellasi wrote:

On 19-Mar 07:07, Daniel Lezcano wrote:

...

On Sat, Mar 17, 2018 at 08:05:15PM +0800, Leo Yan wrote:

...

select_energy_cpu_idx() returns the target CPU index, and eenv->next_idx is used to define target CPU index as well; it's pointless to use two methods to return exactly same value.

This patch is to change the definition for return value of select_energy_cpu_idx(), errors return negative value and success returns 0. And later use eenv->next_idx for target CPU index.

Yes there is a duplication of the information. Actually, the change could be the contrary: make select_energy_cpu_idx return the cpu_idx and kill the next_idx field in the structure.

next_idx field is used only in the calling function, it could be stored in a local variable.

Unfortunately it's not merged (yet) in eas-dev, but there is an energy_diff tracepoint which gets eenv only data.

That's the reason why we store next_idx in the eenv, moreover it makes the code more self-contained from a functional standpoint since everywhere you know that the eenv contains all the information which defined a certain energy aware wakeup decision.

Using next_idx as a return value is also another design decision, since it makes the core more streamline to read.

Thus, overall I don't see a big point on this patch if you consider the above two "design decisions".

I personlly prefer to remove redundant variable from data structure as we can, this finally can help us to keep code as simple as possible. So I am bias to Daniel suggestion.

And after quick thinking, after removing 'next_idx' field it should not impact ftrace event recording, right?

Thanks, Leo Yan

...

...

Change-Id: I57bc9c96566eaf6085c85ea9386d11422cafddbf Signed-off-by: Leo Yan leo.yan@linaro.org

---

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

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 37231b8..0f0b307 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5850,16 +5850,15 @@ static inline bool cpu_in_sg(struct sched_group *sg, int cpu)

• select_energy_cpu_idx(): estimate the energy impact of changing the
• utilization distribution.

• • The eenv parameter specifies the changes: utilisation amount and a pair of
• • possible CPU candidates (the previous CPU and a different target CPU).
• • This function returns the index of a CPU candidate specified by the

• • eenv::next_idx returns the index of a CPU candidate specified by the
  • energy_env which corresponds to the first CPU saving energy.
  • Thus, 0 (EAS_CPU_PRV) means that non of the CPU candidate is more energy

• • efficient than running on prev_cpu. This is also the value returned in case
• • of abort due to error conditions during the computations.
• • A value greater than zero means that the first energy-efficient CPU is the
• • one represented by eenv->cpu[eenv->next_idx].cpu_id.

• • efficient than running on prev_cpu. A value greater than zero means that
• • the first energy-efficient CPU is the one represented by
• • eenv->cpu[eenv->next_idx].cpu_id.
• • The function returns negative value in case of abort due to error
• • conditions during the computations, success returns 0.
  */

static inline int select_energy_cpu_idx(struct energy_env *eenv) { @@ -5871,8 +5870,10 @@ static inline int select_energy_cpu_idx(struct energy_env *eenv)

sd_cpu = eenv->cpu[EAS_CPU_PRV].cpu_id; sd = rcu_dereference(per_cpu(sd_ea, sd_cpu));

• if (!sd)

• return EAS_CPU_PRV;
  

• if (!sd) {

• eenv->next_idx = EAS_CPU_PRV;
  

• return -1;
  

• }

  sg = sd->groups; do {

@@ -5882,8 +5883,10 @@ static inline int select_energy_cpu_idx(struct energy_env *eenv)

eenv->sg_top = sg;
/* energy is unscaled to reduce rounding errors */

• if (compute_energy(eenv) == -EINVAL)
  

• 	return EAS_CPU_PRV;
  

• if (compute_energy(eenv) == -EINVAL) {
  

• 	eenv->next_idx = EAS_CPU_PRV;
  

• 	return -EINVAL;
  

• }
  
  

  } while (sg = sg->next, sg != sd->groups);

@@ -5929,7 +5932,7 @@ static inline int select_energy_cpu_idx(struct energy_env *eenv) } }

• return eenv->next_idx;

• return 0;

}

/* @@ -7145,17 +7148,18 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync if (backup_cpu >= 0) cpumask_set_cpu(backup_cpu, &eenv.cpus_mask);

• select_energy_cpu_idx(&eenv);
  

• /* Check if EAS_CPU_NXT is a more energy efficient CPU */

• if (select_energy_cpu_idx(&eenv) != EAS_CPU_PRV) {
  

• if (eenv.next_idx != EAS_CPU_PRV) {
  schedstat_inc(p->se.statistics.nr_wakeups_secb_nrg_sav);
  schedstat_inc(this_rq()->eas_stats.secb_nrg_sav);
  

• 	target_cpu = eenv.cpu[eenv.next_idx].cpu_id;
  

• 	goto unlock;
  

• } else {
  

• 	schedstat_inc(p->se.statistics.nr_wakeups_secb_no_nrg_sav);
  

• 	schedstat_inc(this_rq()->eas_stats.secb_no_nrg_sav);
  

  }

• schedstat_inc(p->se.statistics.nr_wakeups_secb_no_nrg_sav);
  

• schedstat_inc(this_rq()->eas_stats.secb_no_nrg_sav);
  

• target_cpu = prev_cpu;
  

• target_cpu = eenv.cpu[eenv.next_idx].cpu_id;
  

  goto unlock; }

-- 1.9.1

--

http://www.linaro.org/ Linaro.org │ Open source software for ARM SoCs

Follow Linaro: http://www.facebook.com/pages/Linaro Facebook | http://twitter.com/#!/linaroorg Twitter | http://www.linaro.org/linaro-blog/ Blog

-- #include <best/regards.h>

Patrick Bellasi

On 17-Mar 20:05, Leo Yan wrote:

Function select_energy_cpu_brute() can firstly handle for case 'next_cpu == prev_cpu', so can avoid big amount code indentation under the case 'next_cpu != prev_cpu'.

The existing code is still withing the 80 cols margin and also not so bad to read.

Thus I'm not in general a big fan of this kind of function-0-change patches... and I would really like to avoid them at least when they are not part of a functional refactoring.

Moreover...

Change-Id: Iac08b5f1e6072805c0bee22680bd0ecab411cdba Signed-off-by: Leo Yan leo.yan@linaro.org

---

kernel/sched/fair.c | 91 +++++++++++++++++++++++++---------------------------- 1 file changed, 42 insertions(+), 49 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 0f0b307..b67999a 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -7060,6 +7060,8 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync int target_cpu; int backup_cpu; int next_cpu;

• int delta = 0;

• struct energy_env eenv;

  schedstat_inc(p->se.statistics.nr_wakeups_secb_attempts); schedstat_inc(this_rq()->eas_stats.secb_attempts);

@@ -7108,63 +7110,54 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync }

target_cpu = prev_cpu;

• if (next_cpu != prev_cpu) {

• int delta = 0;
  

• struct energy_env eenv = {
  

• 	.p              = p,
  

• 	.util_delta     = task_util(p),
  

• 	/* Task's previous CPU candidate */
  

• 	.cpu[EAS_CPU_PRV] = {
  

• 		.cpu_id = prev_cpu,
  

• 	},
  

• 	/* Main alternative CPU candidate */
  

• 	.cpu[EAS_CPU_NXT] = {
  

• 		.cpu_id = next_cpu,
  

• 	},
  

• 	/* Backup alternative CPU candidate */
  

• 	.cpu[EAS_CPU_BKP] = {
  

• 		.cpu_id = backup_cpu,
  

• 	},
  

• };
  

The block above exploits the designated initializers to ensure a zero initialization to all omitted members... for example eenv.energy which is used by the following code to sum track the estimated energy of a candidate to ensure a zero initialization to all omitted members... for example eenv.energy which is used by the following code to sum track the estimated energy of a candidate.

• if (next_cpu == prev_cpu) {

• schedstat_inc(p->se.statistics.nr_wakeups_secb_count);
  

• schedstat_inc(this_rq()->eas_stats.secb_count);
  

• goto unlock;
  

• }
• eenv.p = p;
• eenv.util_delta = task_util(p);
• /* Task's previous CPU candidate */
• eenv.cpu[EAS_CPU_PRV].cpu_id = prev_cpu;
• /* Main alternative CPU candidate */
• eenv.cpu[EAS_CPU_NXT].cpu_id = next_cpu;
• /* Backup alternative CPU candidate */
• eenv.cpu[EAS_CPU_BKP].cpu_id = backup_cpu;

... AFAIKS here we don't sure eenv.cpu[XXX].energy = 0

Thus don't we get whatever is on stack as initial energy value?

#ifdef CONFIG_SCHED_WALT

• if (!walt_disabled && sysctl_sched_use_walt_cpu_util &&
  

• 	p->state == TASK_WAKING)
  

• 	delta = task_util(p);
  

• if (!walt_disabled && sysctl_sched_use_walt_cpu_util &&

• p->state == TASK_WAKING)
  

• delta = task_util(p);
  

#endif

• /* Not enough spare capacity on previous cpu */
  

• if (__cpu_overutilized(prev_cpu, delta)) {
  

• 	schedstat_inc(p->se.statistics.nr_wakeups_secb_insuff_cap);
  

• 	schedstat_inc(this_rq()->eas_stats.secb_insuff_cap);
  

• 	target_cpu = next_cpu;
  

• 	goto unlock;
  

• }
  

• cpumask_clear(&eenv.cpus_mask);
  

• if (prev_cpu >= 0)
  

• 	cpumask_set_cpu(prev_cpu, &eenv.cpus_mask);
  

• if (next_cpu >= 0)
  

• 	cpumask_set_cpu(next_cpu, &eenv.cpus_mask);
  

• if (backup_cpu >= 0)
  

• 	cpumask_set_cpu(backup_cpu, &eenv.cpus_mask);
  

• /* Not enough spare capacity on previous cpu */
• if (__cpu_overutilized(prev_cpu, delta)) {

• schedstat_inc(p->se.statistics.nr_wakeups_secb_insuff_cap);
  

• schedstat_inc(this_rq()->eas_stats.secb_insuff_cap);
  

• target_cpu = next_cpu;
  

• goto unlock;
  

• }

• select_energy_cpu_idx(&eenv);
  

• cpumask_clear(&eenv.cpus_mask);
• if (prev_cpu >= 0)

• cpumask_set_cpu(prev_cpu, &eenv.cpus_mask);
  

• if (next_cpu >= 0)

• cpumask_set_cpu(next_cpu, &eenv.cpus_mask);
  

• if (backup_cpu >= 0)

• cpumask_set_cpu(backup_cpu, &eenv.cpus_mask);
  
  

• /* Check if EAS_CPU_NXT is a more energy efficient CPU */
  

• if (eenv.next_idx != EAS_CPU_PRV) {
  

• 	schedstat_inc(p->se.statistics.nr_wakeups_secb_nrg_sav);
  

• 	schedstat_inc(this_rq()->eas_stats.secb_nrg_sav);
  

• } else {
  

• 	schedstat_inc(p->se.statistics.nr_wakeups_secb_no_nrg_sav);
  

• 	schedstat_inc(this_rq()->eas_stats.secb_no_nrg_sav);
  

• }
  

• select_energy_cpu_idx(&eenv);

• target_cpu = eenv.cpu[eenv.next_idx].cpu_id;
  

• goto unlock;
  

• /* Check if EAS_CPU_NXT is a more energy efficient CPU */
• if (eenv.next_idx != EAS_CPU_PRV) {

• schedstat_inc(p->se.statistics.nr_wakeups_secb_nrg_sav);
  

• schedstat_inc(this_rq()->eas_stats.secb_nrg_sav);
  

• } else {

• schedstat_inc(p->se.statistics.nr_wakeups_secb_no_nrg_sav);
  

• schedstat_inc(this_rq()->eas_stats.secb_no_nrg_sav);
  

  }

• schedstat_inc(p->se.statistics.nr_wakeups_secb_count);
• schedstat_inc(this_rq()->eas_stats.secb_count);

• target_cpu = eenv.cpu[eenv.next_idx].cpu_id;

unlock: rcu_read_unlock(); -- 1.9.1

-- #include <best/regards.h>

Patrick Bellasi

On 17-Mar 20:05, Leo Yan wrote:

This commit changes to use per cpu data to maintain energy environment structure, so can move it out from kernel stack and avoid the stack overflow issue if we want to add more items into energy environment structure for later optimization.

This relocation makes sense to us, to the point that:

- Chris already used this approach in the EAS re-expression for v4.14 kernels: https://android.googlesource.com/kernel/common/+/android-4.14/ which has been available since some mothns now.

- Quentin/Dietmar are using a similar approach for the "mainline" posting (soon to be posted on LKML)

Thus, this seems to be yet another implementation.

IMHO we should focus on reviewing/refactoring the v4.14 version, maybe by improving what's in that kernel to add some of the interesting features you are proposing in this series.

At the end it would be nice to reduce the amount of code variations we have around... thus, before merging such a big change in v4.9, I would like to see that we all agree we can use the same solution both in v4.14 and v4.9.

Another thing to consider is that the mainline solution is more likely to be aligned with what Dietmar is going to push on LKML (perhaps by today)... thus keep an eye on that too.

Change-Id: Ifdcb1bbae36cb8e074b31ec35f00c79f6a14b973 Signed-off-by: Leo Yan leo.yan@linaro.org

---

kernel/sched/fair.c | 62 +++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 46 insertions(+), 16 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 6c0b918..9997a6a 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6690,7 +6690,36 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)

return target; }

+static struct kmem_cache *energy_env_cache __read_mostly; +static DEFINE_PER_CPU(struct energy_env *, energy_env);

+static void init_energy_env(void) +{

• struct energy_env *eenv;
• int i;
• energy_env_cache = KMEM_CACHE(energy_env, 0);
• for_each_possible_cpu(i) {

• eenv = kmem_cache_alloc(energy_env_cache, GFP_KERNEL | __GFP_ZERO);
  

• if (!eenv)
  

• 	goto err;
  

• rcu_assign_pointer(per_cpu(energy_env, i), eenv);
  

• }
• return;

+err:

• for_each_possible_cpu(i) {

• eenv = rcu_dereference(per_cpu(energy_env, i));
  

• if (!eenv)
  

• 	continue;
  

• kmem_cache_free(energy_env_cache, eenv);
  

• }

+}

/*

• cpu_util_wake: Compute cpu utilization with any contributions from
• the waking task p removed. check_for_migration() looks for a better CPU of

@@ -7061,14 +7090,13 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync int backup_cpu; int next_cpu; int delta = 0;

• struct energy_env eenv;

• int cpu = smp_processor_id();

• struct energy_env *eenv;

  schedstat_inc(p->se.statistics.nr_wakeups_secb_attempts); schedstat_inc(this_rq()->eas_stats.secb_attempts);

  if (sysctl_sched_sync_hint_enable && sync) {

• int cpu = smp_processor_id();
  

• if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p))) { schedstat_inc(p->se.statistics.nr_wakeups_secb_sync); schedstat_inc(this_rq()->eas_stats.secb_sync);

@@ -7116,14 +7144,15 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync goto unlock; }

• eenv.p = p;
• eenv.util_delta = task_util(p);

• eenv = rcu_dereference(per_cpu(energy_env, cpu));
• eenv->p = p;
• eenv->util_delta = task_util(p); /* Task's previous CPU candidate */

• eenv.cpu[EAS_CPU_PRV].cpu_id = prev_cpu;

• eenv->cpu[EAS_CPU_PRV].cpu_id = prev_cpu; /* Main alternative CPU candidate */

• eenv.cpu[EAS_CPU_NXT].cpu_id = next_cpu;

• eenv->cpu[EAS_CPU_NXT].cpu_id = next_cpu; /* Backup alternative CPU candidate */

• eenv.cpu[EAS_CPU_BKP].cpu_id = backup_cpu;

• eenv->cpu[EAS_CPU_BKP].cpu_id = backup_cpu;

#ifdef CONFIG_SCHED_WALT if (!walt_disabled && sysctl_sched_use_walt_cpu_util && @@ -7138,18 +7167,18 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync goto unlock; }

• cpumask_clear(&eenv.cpus_mask);

• cpumask_clear(&eenv->cpus_mask); if (prev_cpu >= 0)

• cpumask_set_cpu(prev_cpu, &eenv.cpus_mask);
  

• cpumask_set_cpu(prev_cpu, &eenv->cpus_mask);
  

  if (next_cpu >= 0)

• cpumask_set_cpu(next_cpu, &eenv.cpus_mask);
  

• cpumask_set_cpu(next_cpu, &eenv->cpus_mask);
  

  if (backup_cpu >= 0)

• cpumask_set_cpu(backup_cpu, &eenv.cpus_mask);
  

• cpumask_set_cpu(backup_cpu, &eenv->cpus_mask);
  
  

• select_energy_cpu_idx(&eenv);

• select_energy_cpu_idx(eenv);

  /* Check if EAS_CPU_NXT is a more energy efficient CPU */

• if (eenv.next_idx != EAS_CPU_PRV) {

• if (eenv->next_idx != EAS_CPU_PRV) { schedstat_inc(p->se.statistics.nr_wakeups_secb_nrg_sav); schedstat_inc(this_rq()->eas_stats.secb_nrg_sav); } else {

@@ -7157,7 +7186,7 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync schedstat_inc(this_rq()->eas_stats.secb_no_nrg_sav); }

• target_cpu = eenv.cpu[eenv.next_idx].cpu_id;

• target_cpu = eenv->cpu[eenv->next_idx].cpu_id;

unlock: rcu_read_unlock(); @@ -10975,6 +11004,7 @@ __init void init_sched_fair_class(void) nohz.next_balance = jiffies; zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT); #endif

• init_energy_env();

#endif /* SMP */

}

1.9.1

-- #include <best/regards.h>

Patrick Bellasi

On Mon, Mar 19, 2018 at 06:28:08PM +0100, Daniel Lezcano wrote:

On Sat, Mar 17, 2018 at 08:05:18PM +0800, Leo Yan wrote:

...

This commit changes to use per cpu data to maintain energy environment structure, so can move it out from kernel stack and avoid the stack overflow issue if we want to add more items into energy environment structure for later optimization.

Change-Id: Ifdcb1bbae36cb8e074b31ec35f00c79f6a14b973 Signed-off-by: Leo Yan leo.yan@linaro.org

---

kernel/sched/fair.c | 62 +++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 46 insertions(+), 16 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 6c0b918..9997a6a 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6690,7 +6690,36 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)

return target; }

+static struct kmem_cache *energy_env_cache __read_mostly; +static DEFINE_PER_CPU(struct energy_env *, energy_env);

+static void init_energy_env(void) +{

• struct energy_env *eenv;
• int i;
• energy_env_cache = KMEM_CACHE(energy_env, 0);
• for_each_possible_cpu(i) {

• eenv = kmem_cache_alloc(energy_env_cache, GFP_KERNEL | __GFP_ZERO);
  

• if (!eenv)
  

• 	goto err;
  

• rcu_assign_pointer(per_cpu(energy_env, i), eenv);
  

• }
• return;

+err:

• for_each_possible_cpu(i) {

• eenv = rcu_dereference(per_cpu(energy_env, i));
  

• if (!eenv)
  

• 	continue;
  

• kmem_cache_free(energy_env_cache, eenv);
  

• }

+}

This portion of code is not right.

First you create a pool of objects with kmem_cache_create() and then you use this poll of objects to allocate cached objects.

It should be like:

At init time: struct pool *mypool = kmem_cache_create("my_poll", sizeof(struct poll), 0, SLAB_PANIC, NULL);

During runtime: replace kzalloc by:

myobject = kmem_cache_zalloc(mypoll, GFP_KERNEL);

and kfree by:

kmem_cache_free(myobject);

And at exit time: kmem_cache_destroy(mypool);

Usually the pool of objects stays there for the entire life-cycle of the subsystem.

The poll of objects is visible at /proc/slabinfo.

However, this is only usefull when you are allocating and freeing objects at each services (eg. a new process at fork time, a new timer, etc ...)

For this change, a statically per cpu define (not a pointer) is ok and then access with per_cpu_ptr.

static DEFINE_PER_CPU(struct energy_env, energy_env);

[ ... ]

struct energy_env *eenv = per_cpu_ptr(&energy_env, cpu);

Will fix for this.

At beginning I tried avoid too big size for kernel Image linkage. After your reminding, the static data should be placed into .bss section, so it's good to use static definition.

Thanks, Leo Yan

...

/*

• cpu_util_wake: Compute cpu utilization with any contributions from
• the waking task p removed. check_for_migration() looks for a better CPU of

@@ -7061,14 +7090,13 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync int backup_cpu; int next_cpu; int delta = 0;

• struct energy_env eenv;

• int cpu = smp_processor_id();

• struct energy_env *eenv;

  schedstat_inc(p->se.statistics.nr_wakeups_secb_attempts); schedstat_inc(this_rq()->eas_stats.secb_attempts);

  if (sysctl_sched_sync_hint_enable && sync) {

• int cpu = smp_processor_id();
  

• if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p))) { schedstat_inc(p->se.statistics.nr_wakeups_secb_sync); schedstat_inc(this_rq()->eas_stats.secb_sync);

@@ -7116,14 +7144,15 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync goto unlock; }

• eenv.p = p;
• eenv.util_delta = task_util(p);

• eenv = rcu_dereference(per_cpu(energy_env, cpu));
• eenv->p = p;
• eenv->util_delta = task_util(p); /* Task's previous CPU candidate */

• eenv.cpu[EAS_CPU_PRV].cpu_id = prev_cpu;

• eenv->cpu[EAS_CPU_PRV].cpu_id = prev_cpu; /* Main alternative CPU candidate */

• eenv.cpu[EAS_CPU_NXT].cpu_id = next_cpu;

• eenv->cpu[EAS_CPU_NXT].cpu_id = next_cpu; /* Backup alternative CPU candidate */

• eenv.cpu[EAS_CPU_BKP].cpu_id = backup_cpu;

• eenv->cpu[EAS_CPU_BKP].cpu_id = backup_cpu;

#ifdef CONFIG_SCHED_WALT if (!walt_disabled && sysctl_sched_use_walt_cpu_util && @@ -7138,18 +7167,18 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync goto unlock; }

• cpumask_clear(&eenv.cpus_mask);

• cpumask_clear(&eenv->cpus_mask); if (prev_cpu >= 0)

• cpumask_set_cpu(prev_cpu, &eenv.cpus_mask);
  

• cpumask_set_cpu(prev_cpu, &eenv->cpus_mask);
  

  if (next_cpu >= 0)

• cpumask_set_cpu(next_cpu, &eenv.cpus_mask);
  

• cpumask_set_cpu(next_cpu, &eenv->cpus_mask);
  

  if (backup_cpu >= 0)

• cpumask_set_cpu(backup_cpu, &eenv.cpus_mask);
  

• cpumask_set_cpu(backup_cpu, &eenv->cpus_mask);
  
  

• select_energy_cpu_idx(&eenv);

• select_energy_cpu_idx(eenv);

  /* Check if EAS_CPU_NXT is a more energy efficient CPU */

• if (eenv.next_idx != EAS_CPU_PRV) {

• if (eenv->next_idx != EAS_CPU_PRV) { schedstat_inc(p->se.statistics.nr_wakeups_secb_nrg_sav); schedstat_inc(this_rq()->eas_stats.secb_nrg_sav); } else {

@@ -7157,7 +7186,7 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync schedstat_inc(this_rq()->eas_stats.secb_no_nrg_sav); }

• target_cpu = eenv.cpu[eenv.next_idx].cpu_id;

• target_cpu = eenv->cpu[eenv->next_idx].cpu_id;

unlock: rcu_read_unlock(); @@ -10975,6 +11004,7 @@ __init void init_sched_fair_class(void) nohz.next_balance = jiffies; zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT); #endif

• init_energy_env();

#endif /* SMP */

}

1.9.1

--

http://www.linaro.org/ Linaro.org │ Open source software for ARM SoCs

Follow Linaro: http://www.facebook.com/pages/Linaro Facebook | http://twitter.com/#!/linaroorg Twitter | http://www.linaro.org/linaro-blog/ Blog

On 17-Mar 20:05, Leo Yan wrote:

The energy calculation has two steps, the first step is to select CPU candidates, the second step is to compare energy for these candidates. Now in first step we use three candidates (EAS_CPU_PRV, EAS_CPU_NXT and EAS_CPU_BKP), and energy calculation also uses these three CPU index for computation iteration.

If we bind code to these three candidates, it's hard for us to extend for more CPU candidates; on the other hand cpumask structure is more suitable to track candidates and for extension for more candidates.

This patch is to use cpumask structure to track the candidates, and remove the three predefined candidates EAS_CPU_PRV, EAS_CPU_NXT and EAS_CPU_BKP.

Again, I'm in favour to this approach, but still think it should be aligned with the mainline proposal... which, as I told, Dietmar is going to post soon on LKML...

Change-Id: I0fb1a904b6024ebfb3c26daa1a00dc8132eebb3a Signed-off-by: Leo Yan leo.yan@linaro.org

---

kernel/sched/fair.c | 151 ++++++++++++++++++++-------------------------------- 1 file changed, 57 insertions(+), 94 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 9997a6a..f4206c1 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5444,20 +5444,6 @@ static inline bool energy_aware(void) }

/*

• • CPU candidates.
• • These are labels to reference CPU candidates for an energy_diff.
• • Currently we support only two possible candidates: the task's previous CPU
• • and another candiate CPU.
• • More advanced/aggressive EAS selection policies can consider more
• • candidates.
• */

-#define EAS_CPU_PRV 0 -#define EAS_CPU_NXT 1 -#define EAS_CPU_BKP 2 -#define EAS_CPU_CNT 3

-/*

• energy_diff - supports the computation of the estimated energy impact in
• moving a "task"'s "util_delta" between different CPU candidates.

*/ @@ -5471,10 +5457,6 @@ struct energy_env {

/* CPU candidates to evaluate */ struct {

• /* CPU ID, must be in cpus_mask */
  

• int	cpu_id;
  

• /*
  • Index (into sched_group_energy::cap_states) of the OPP the
  • CPU needs to run at if the task is placed on it.

@@ -5488,16 +5470,16 @@ struct energy_env { /* Estimated system energy */ unsigned int energy;

• /* Estimated energy variation wrt EAS_CPU_PRV */
  

• /* Estimated energy variation wrt previous CPU */
  

  int nrg_delta;

• } cpu[EAS_CPU_CNT];

• } cpu[NR_CPUS];

• /*

• * Index (into energy_env::cpu) of the morst energy efficient CPU for
  

• * the specified energy_env::p
  

• */
  

• int next_idx;

• /* The morst energy efficient CPU for the specified energy_env::p */

• int next_cpu;

• /* Previous CPU */

• int prev_cpu;

  /* Support data */ struct sched_group *sg_top;

@@ -5530,7 +5512,7 @@ static unsigned long __cpu_norm_util(unsigned long util, unsigned long capacity) return (util << SCHED_CAPACITY_SHIFT)/capacity; }

-static unsigned long group_max_util(struct energy_env *eenv, int cpu_idx) +static unsigned long group_max_util(struct energy_env *eenv, int cpu_id) { unsigned long max_util = 0; unsigned long util; @@ -5545,7 +5527,7 @@ static unsigned long group_max_util(struct energy_env *eenv, int cpu_idx) * then we should add the (estimated) utilization of the task * assuming we will wake it up on that CPU. */

• if (unlikely(cpu == eenv->cpu[cpu_idx].cpu_id))
  

• if (unlikely(cpu == cpu_id))
  util += eenv->util_delta;
  
  

  max_util = max(max_util, util);

@@ -5575,9 +5557,9 @@ static unsigned long group_max_util(struct energy_env *eenv, int cpu_idx)

• estimate (more busy).

*/ static unsigned -long group_norm_util(struct energy_env *eenv, int cpu_idx) +long group_norm_util(struct energy_env *eenv, int cpu_id) {

• unsigned long capacity = eenv->cpu[cpu_idx].cap;

• unsigned long capacity = eenv->cpu[cpu_id].cap; unsigned long util, util_sum = 0; int cpu;

@@ -5590,7 +5572,7 @@ long group_norm_util(struct energy_env *eenv, int cpu_idx) * then we should add the (estimated) utilization of the task * assuming we will wake it up on that CPU. */

• if (unlikely(cpu == eenv->cpu[cpu_idx].cpu_id))
  

• if (unlikely(cpu == cpu_id))
  util += eenv->util_delta;
  
  

  util_sum += __cpu_norm_util(util, capacity);

@@ -5599,29 +5581,29 @@ long group_norm_util(struct energy_env *eenv, int cpu_idx) return min_t(unsigned long, util_sum, SCHED_CAPACITY_SCALE); }

-static int find_new_capacity(struct energy_env *eenv, int cpu_idx) +static int find_new_capacity(struct energy_env *eenv, int cpu_id) { const struct sched_group_energy *sge = eenv->sg->sge; int idx, max_idx = sge->nr_cap_states - 1;

• unsigned long util = group_max_util(eenv, cpu_idx);

• unsigned long util = group_max_util(eenv, cpu_id);

  /* default is max_cap if we don't find a match */

• eenv->cpu[cpu_idx].cap_idx = max_idx;
• eenv->cpu[cpu_idx].cap = sge->cap_states[max_idx].cap;

• eenv->cpu[cpu_id].cap_idx = max_idx;

• eenv->cpu[cpu_id].cap = sge->cap_states[max_idx].cap;

  for (idx = 0; idx < sge->nr_cap_states; idx++) { if (sge->cap_states[idx].cap >= util) { /* Keep track of SG's capacity */

• 	eenv->cpu[cpu_idx].cap_idx = idx;
  

• 	eenv->cpu[cpu_idx].cap = sge->cap_states[idx].cap;
  

• 	eenv->cpu[cpu_id].cap_idx = idx;
  

• 	eenv->cpu[cpu_id].cap = sge->cap_states[idx].cap;
  break;
  

  } }

• return eenv->cpu[cpu_idx].cap_idx;

• return eenv->cpu[cpu_id].cap_idx;

}

-static int group_idle_state(struct energy_env *eenv, int cpu_idx) +static int group_idle_state(struct energy_env *eenv, int cpu_id) { struct sched_group *sg = eenv->sg; int i, state = INT_MAX; @@ -5635,10 +5617,8 @@ static int group_idle_state(struct energy_env *eenv, int cpu_idx) /* Take non-cpuidle idling into account (active idle/arch_cpu_idle()) */ state++;

• src_in_grp = cpumask_test_cpu(eenv->cpu[EAS_CPU_PRV].cpu_id,

• 		      sched_group_cpus(sg));
  

• dst_in_grp = cpumask_test_cpu(eenv->cpu[cpu_idx].cpu_id,

• 		      sched_group_cpus(sg));
  

• src_in_grp = cpumask_test_cpu(eenv->prev_cpu, sched_group_cpus(sg));
• dst_in_grp = cpumask_test_cpu(cpu_id, sched_group_cpus(sg)); if (src_in_grp == dst_in_grp) { /* both CPUs under consideration are in the same group or not in
  • either group, migration should leave idle state the same.

@@ -5652,7 +5632,7 @@ static int group_idle_state(struct energy_env *eenv, int cpu_idx) */ for_each_cpu(i, sched_group_cpus(sg)) { grp_util += cpu_util_wake(i, eenv->p);

• if (unlikely(i == eenv->cpu[cpu_idx].cpu_id))
  

• if (unlikely(i == cpu_id))
  grp_util += eenv->util_delta;
  

  }

@@ -5707,39 +5687,36 @@ static void calc_sg_energy(struct energy_env *eenv) unsigned long sg_util; int cap_idx, idle_idx; int total_energy = 0;

• int cpu_idx;
• for (cpu_idx = EAS_CPU_PRV; cpu_idx < EAS_CPU_CNT; ++cpu_idx) {

• int cpu;

• for_each_cpu(cpu, &eenv->cpus_mask) {

• if (eenv->cpu[cpu_idx].cpu_id == -1)
  

• 	continue;
  

  /* Compute ACTIVE energy */

• cap_idx = find_new_capacity(eenv, cpu_idx);
  

• cap_idx = find_new_capacity(eenv, cpu);
  

  busy_power = sg->sge->cap_states[cap_idx].power; /*
  • in order to calculate cpu_norm_util, we need to know which
  • capacity level the group will be at, so calculate that first
  */

• sg_util = group_norm_util(eenv, cpu_idx);
  

• sg_util = group_norm_util(eenv, cpu);
  
  

  busy_energy = sg_util * busy_power;

  /* Compute IDLE energy */

• idle_idx = group_idle_state(eenv, cpu_idx);
  

• idle_idx = group_idle_state(eenv, cpu);
  

  idle_power = sg->sge->idle_states[idle_idx].power;

  idle_energy = SCHED_CAPACITY_SCALE - sg_util; idle_energy *= idle_power;

  total_energy = busy_energy + idle_energy;

• eenv->cpu[cpu_idx].energy += total_energy;
  

• eenv->cpu[cpu].energy += total_energy;
  

  }

}

/*

• compute_energy() computes the absolute variation in energy consumption by

• • moving eenv.util_delta from EAS_CPU_PRV to EAS_CPU_NXT.

• • moving eenv::util_delta from eenv::prev_cpu to eenv::next_cpu.
  • NOTE: compute_energy() may fail when racing with sched_domain updates, in

  •   which case we abort by returning -EINVAL.
    

@@ -5850,12 +5827,8 @@ static inline bool cpu_in_sg(struct sched_group *sg, int cpu)

• select_energy_cpu_idx(): estimate the energy impact of changing the
• utilization distribution.

• • eenv::next_idx returns the index of a CPU candidate specified by the
• • energy_env which corresponds to the first CPU saving energy.
• • Thus, 0 (EAS_CPU_PRV) means that non of the CPU candidate is more energy
• • efficient than running on prev_cpu. A value greater than zero means that
• • the first energy-efficient CPU is the one represented by
• • eenv->cpu[eenv->next_idx].cpu_id.

• • eenv::next_cpu returns a CPU candidate specified by the energy_env which
• • corresponds to the first energy-efficient CPU.
  • The function returns negative value in case of abort due to error
  • conditions during the computations, success returns 0.

@@ -5864,14 +5837,13 @@ static inline int select_energy_cpu_idx(struct energy_env *eenv) { struct sched_domain *sd; struct sched_group *sg;

• int sd_cpu = -1;
• int cpu_idx;

• int cpu; int margin;

• sd_cpu = eenv->cpu[EAS_CPU_PRV].cpu_id;
• sd = rcu_dereference(per_cpu(sd_ea, sd_cpu));

• cpu = cpumask_first(&eenv->cpus_mask);
• sd = rcu_dereference(per_cpu(sd_ea, cpu)); if (!sd) {

• eenv->next_idx = EAS_CPU_PRV;
  

• eenv->next_cpu = eenv->prev_cpu;
  

  return -1; }

@@ -5884,49 +5856,46 @@ static inline int select_energy_cpu_idx(struct energy_env *eenv) eenv->sg_top = sg; /* energy is unscaled to reduce rounding errors */ if (compute_energy(eenv) == -EINVAL) {

• 	eenv->next_idx = EAS_CPU_PRV;
  

• 	eenv->next_cpu = eenv->prev_cpu;
  return -EINVAL;
  

  }

  } while (sg = sg->next, sg != sd->groups);

  /* Scale energy before comparisons */

• for (cpu_idx = EAS_CPU_PRV; cpu_idx < EAS_CPU_CNT; ++cpu_idx)

• eenv->cpu[cpu_idx].energy >>= SCHED_CAPACITY_SHIFT;
  

• for_each_cpu(cpu, &eenv->cpus_mask)

• eenv->cpu[cpu].energy >>= SCHED_CAPACITY_SHIFT;
  
  

  /*

  • Compute the dead-zone margin used to prevent too many task
  • migrations with negligible energy savings.
  • An energy saving is considered meaningful if it reduces the energy

• * consumption of EAS_CPU_PRV CPU candidate by at least ~1.56%
  

• * consumption of previous CPU candidate by at least ~1.56%
  

  */

• margin = eenv->cpu[EAS_CPU_PRV].energy >> 6;

• margin = eenv->cpu[eenv->prev_cpu].energy >> 6;

  /*

• * By default the EAS_CPU_PRV CPU is considered the most energy
  

• * By default the previous CPU is considered the most energy
  

  • efficient, with a 0 energy variation.
  */

• eenv->next_idx = EAS_CPU_PRV;

• eenv->next_cpu = eenv->prev_cpu;

  /*

  • Compare the other CPU candidates to find a CPU which can be

• * more energy efficient then EAS_CPU_PRV
  

• * more energy efficient than previous CPU
  

  */

• for (cpu_idx = EAS_CPU_NXT; cpu_idx < EAS_CPU_CNT; ++cpu_idx) {

• /* Skip not valid scheduled candidates */
  

• if (eenv->cpu[cpu_idx].cpu_id < 0)
  

• 	continue;
  

• /* Compute energy delta wrt EAS_CPU_PRV */
  

• eenv->cpu[cpu_idx].nrg_delta =
  

• 	eenv->cpu[cpu_idx].energy -
  

• 	eenv->cpu[EAS_CPU_PRV].energy;
  

• for_each_cpu(cpu, &eenv->cpus_mask) {

• /* Compute energy delta wrt previous CPU */
  

• eenv->cpu[cpu].nrg_delta =
  

• 	eenv->cpu[cpu].energy - eenv->cpu[eenv->prev_cpu].energy;
  

  /* filter energy variations within the dead-zone margin */

• if (abs(eenv->cpu[cpu_idx].nrg_delta) < margin)
  

• 	eenv->cpu[cpu_idx].nrg_delta = 0;
  

• if (abs(eenv->cpu[cpu].nrg_delta) < margin)
  

• 	eenv->cpu[cpu].nrg_delta = 0;
  

  /* update the schedule candidate with min(nrg_delta) */

• if (eenv->cpu[cpu_idx].nrg_delta <
  

•     eenv->cpu[eenv->next_idx].nrg_delta) {
  

• 	eenv->next_idx = cpu_idx;
  

• if (eenv->cpu[cpu].nrg_delta <
  

•     eenv->cpu[eenv->next_cpu].nrg_delta) {
  

• 	eenv->next_cpu = cpu;
  if (sched_feat(FBT_STRICT_ORDER))
  	break;
  

  }

@@ -7147,12 +7116,6 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync eenv = rcu_dereference(per_cpu(energy_env, cpu)); eenv->p = p; eenv->util_delta = task_util(p);

• /* Task's previous CPU candidate */
• eenv->cpu[EAS_CPU_PRV].cpu_id = prev_cpu;
• /* Main alternative CPU candidate */
• eenv->cpu[EAS_CPU_NXT].cpu_id = next_cpu;
• /* Backup alternative CPU candidate */
• eenv->cpu[EAS_CPU_BKP].cpu_id = backup_cpu;

#ifdef CONFIG_SCHED_WALT if (!walt_disabled && sysctl_sched_use_walt_cpu_util && @@ -7177,8 +7140,8 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync

select_energy_cpu_idx(eenv);

• /* Check if EAS_CPU_NXT is a more energy efficient CPU */
• if (eenv->next_idx != EAS_CPU_PRV) {

• /* Check if eenv::next_cpu is a more energy efficient CPU */
• if (eenv->next_cpu != eenv->prev_cpu) { schedstat_inc(p->se.statistics.nr_wakeups_secb_nrg_sav); schedstat_inc(this_rq()->eas_stats.secb_nrg_sav); } else {

@@ -7186,7 +7149,7 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync schedstat_inc(this_rq()->eas_stats.secb_no_nrg_sav); }

• target_cpu = eenv->cpu[eenv->next_idx].cpu_id;

• target_cpu = eenv->next_cpu;

unlock: rcu_read_unlock(); -- 1.9.1

-- #include <best/regards.h>

Patrick Bellasi

On Mon, Mar 19, 2018 at 03:52:48PM +0000, Patrick Bellasi wrote:

On 17-Mar 20:05, Leo Yan wrote:

...

Let's firstly see one example for a small utilization task is waken up and need calculate energy for two candidate CPUs. From hardware design perspective, each candidate CPU cannot decide OPP by itself due it binds with other CPUs in the same clock domain, e.g. it binds clock domain in the cluster with other CPUs, at the end we need to compute energy for all CPUs in the cluster.

Let's use below CPU topology as the example:

Cluster_0               Cluster_1
CPU_0                   CPU_4
CPU_1                   CPU_5
CPU_2                   CPU_6
CPU_3                   CPU_7

Current code always calculate the energy for all CPUs in bound clock domain, if the candidates are CPU_0 and CPU_4, the formula for energy computation is as below:

E(CPU_x) stands the CPU_x energy, notation E(CPU_x)` means the CPU_x energy after take placed on it, TE(CPU_x) means the total energy for all computation for all CPUs when task is placed on CPU_x, E_DIFF(CPU_x - CPU_y) means the energy difference between CPU_x and CPU_y, it equals to TE(CPU_x) - TE(CPU_y).

TE(CPU_0) = E(CPU_0)` + E(CPU_1) + E(CPU_2) + E(CPU_3) + E(CLS_0)` + E(CPU_4) + E(CPU_5) + E(CPU_6) + E(CPU_7) + E(CLS_1)

TE(CPU_4) = E(CPU_0) + E(CPU_1) + E(CPU_2) + E(CPU_3) + E(CLS_0) + E(CPU_4)` + E(CPU_5) + E(CPU_6) + E(CPU_7) + E(CLS_1)`

E_DIFF(CPU_0 - CPU_4) = TE(CPU_0) - TE(CPU_4)

From upper formula we easily get to know CPU_1/2/3/5/6/7 energy computations are redundant,

This means that, for example, the contribution E(CPU_2) is the same in TE(CPU_0) and TE(CPU_4), right?

Yes.

If that's what you mean, I'm not entirely convinced. This is true _IFF_ the OPP for Cluster_0 does not change while having the task in CPU_0 or having the task in the other cluster.

If the OPP for Cluster_0 should change, then E(CPU_2) can have to very different values in TE(CPU_0) and TE(CPU_4).

You are totally right. If cluster_0 OPP is to be changed, we must compute E(CPU_2) for this case. I should clarify this prerequisite in the commit log.

...

on the other hand if we only consider the energy consumption by waken task, the energy difference is between the target CPU energy data before and after task placed on it.

Sorry, I don't completely get this last... ... and it seems it's they key to understand to next paragraph :/

Let me rephrase it: Let's assume the task is placed onto on candidate CPU, if this candidate CPU has same OPP with without this waken task on it, then we can simply calculate the energy introduced by the task:

E_DIFF = E(CPU_target)` - E(CPU_target)

...

This method have one benefit is it can avoid to compute all CPUs energy in the same cluster, and only can focus the energy change introduced by waken task on the target CPU,

Do you mean that we whould ignore the blocked utilization?

No, if the candidate CPU has no OPP change for waken task placement, we can skip to compuate all other irrelevant CPUs energy in the same cluster.

...

which this method is called 'task oriented computation' in this patch, the energy computation can be optimized as:

TE(CPU_0) = E(CPU_0)` + E(CLS_0)` - E(CPU_0) - E(CLS_0) TE(CPU_4) = E(CPU_4)` + E(CLS_1)` - E(CPU_4) - E(CLS_1)

Again, IMHO in the above formula, if the OPP could change we cannot disregard energy variations from other cpus in Cluster_1.

Yes. I will refine the commit log.

...

E_DIFF(CPU_0 - CPU_4) = TE(CPU_0) - TE(CPU_4)

As the result, the computation iteration can be reduced from 20 times to 8 times; so this can significantly reduce calculation overload.

After using task oriented computation, it has one case the computation might take longer time than previous method. For instance, when candidates are CPU_0 and CPU1, and after place task on either CPU the OPP will be increased,

... but this can happen also in the previous case.

Let say that CPU_4 has a utilization which is ~80% less then the capacity of its current OPP and that the task's PREV_CPU is CPU_0.

Let's also assume that the utilization of the task is big enought to require a capacity increase on CPU_4. Then, the energy for all the other CPUs in Cluster_1 are different in the before and after case.

Agree. I will list all possible cases in commit log in next version.

...

in this case, the old method uses below computation:

TE(CPU_0) = E(CPU_0)` + E(CPU_1) + E(CPU_2) + E(CPU_3) + E(CLS_0) TE(CPU_1) = E(CPU_0) + E(CPU_1)` + E(CPU_2) + E(CPU_3) + E(CLS_0)

E_DIFF(CPU_0 - CPU_1) = TE(CPU_0) - TE(CPU_1)

Using task oriented computation, because the OPP increasing impacts other CPUs in the same cluster, so it needs to calculate all related CPUs energy:

TE(CPU_0) = E(CPU_0)` + E(CPU_1)' + E(CPU_2)' + E(CPU_3)' + E(CLS_0)` - E(CPU_0) - E(CPU_1) - E(CPU_2) - E(CPU_3) - E(CLS_0)

TE(CPU_1) = E(CPU_0)` + E(CPU_1)' + E(CPU_2)' + E(CPU_3)' + E(CLS_0)` - E(CPU_0) - E(CPU_1) - E(CPU_2) - E(CPU_3) - E(CLS_0)

E_DIFF(CPU_0 - CPU_1) = TE(CPU_0) - TE(CPU_1)

We can use more complex method for optimization, e.g. we can extend eenv structure to cache CPU energy data so can reuse them for two candidates. This can be used for later optimization.

As side effect, this patch also resolves energy calculation consistent issue, e.g. for some cases the energy calculation is for one cluster, some cases the energy calculation is for multiple clusters; so the energy data semantics are not consistent for different scenarios.

That's becasue we care about relative differences in energy consumptions...

...

Computation inconsistent issue might introduce trouble for PE filter.

... we should look into those issues. We know about some of them and already have patches, which was part of the 3.18 kernel used by Pixel devices but not yet merged in 4.4, since we notice that these cases, although being broken, are also not happening in Android because of the schedtune configurations used by Pixel devices.

To more clearly describe the issue I observed, please see below code related with dead-zone margin [1]:

/* * Compute the dead-zone margin used to prevent too many task * migrations with negligible energy savings. * An energy saving is considered meaningful if it reduces the energy * consumption of EAS_CPU_PRV CPU candidate by at least ~1.56% */ margin = eenv->cpu[EAS_CPU_PRV].energy >> 6;

So the dead-zone margin is: eenv->cpu[EAS_CPU_PRV].energy / 64; the value of eenv->cpu[EAS_CPU_PRV].energy is not consistent, it might be one cluster energy (for all candidates in same cluster) or two clusters energy (for candidates are in two clusters).

[1] https://android.googlesource.com/kernel/common/+/android-4.9-eas-dev/kernel/...

...

This patch fixes issue by always calculating task based energy.

To achieve the optimization, this patch utilizes 'eenv->sg_cap' and 'eenv->sg_top' parameters; the parameter 'eenv->sg_cap' is only about the CPU capacity shared attribution, so eventually it's to describe the clock domain shared within CPUs, from this parameter we can get to know the final OPP selection; we need utilize parameter 'eenv->sg_top' to define which CPU we take care about, if the frequency is not changed after placing waken task then it will set the first level scheduling group to it (means one the single CPU) so the energy computation is limited to this single CPU, otherwise it rolls back to compute all CPUs

Ok, so that maens that we always check for OPP changes... then it should work...

...

in the same clock domain.

Change-Id: Ifb64ad77c6173388abf13e255e2ed8e8586a38bc Signed-off-by: Leo Yan leo.yan@linaro.org

---

kernel/sched/fair.c | 76 ++++++++++++++++++++++++++++++----------------------- 1 file changed, 43 insertions(+), 33 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 49eee75..4811fce 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5473,7 +5473,7 @@ struct energy_env { /* Estimated energy variation wrt previous CPU */ int nrg_delta;

• } cpu[NR_CPUS];

• } cpu[NR_CPUS*2];

         ^^^^^^^^^^^

Why can't we have a before/after set of variables directly in the definition of eenv?

Given the usage below it should also turns out to be slightly more cache friendly. i.e.

struct energy_env {

#define PREV_CAP 0 #define NEXT_CAP 1 struct { // ... } cpu[2][NR_CPUS]; }

Yeah, thanks for good suggestions. Will refine patch with it.

...

/* The morst energy efficient CPU for the specified energy_env::p */ int next_cpu; @@ -5791,45 +5791,55 @@ static int compute_energy(struct energy_env *eenv, int candidate) */ static int compute_task_energy(struct energy_env *eenv, int cpu) {

• struct sched_domain *sd, *sd_cap;
• struct sched_group *sg;
• int first_cpu;

• struct sched_domain *sd;
• unsigned int prev_cap_idx, next_cap_idx;
• int cmp_idx, ret;

• sd = rcu_dereference(per_cpu(sd_ea, cpu));

• sd = rcu_dereference(per_cpu(sd_scs, cpu)); if (!sd) return -1; /* Error */

• sg = sd->groups;
• do {

• /* Skip SGs which do not contains a candidate CPU */
  

• if (!cpumask_intersects(&eenv->cpus_mask, sched_group_cpus(sg)))
  

• 	continue;
  

• eenv->sg_top = sg;
  

• first_cpu = cpumask_first(sched_group_cpus(sg));
  

• /*
  

•  * The CPU capacity sharing attribution is decided by hardhware
  

•  * design so we can decide the sg_cp value at the beginning
  

•  * for specific CPU.
  

•  */
  

• sd_cap = rcu_dereference(per_cpu(sd_scs, first_cpu));
  

• if (sd_cap && sd_cap->parent)
  

• 	eenv->sg_cap = sd_cap->parent->groups;
  

• else
  

• 	eenv->sg_cap = sd_cap->groups;
  

• find_new_capacity(eenv, cpu);
  

• /*

• * The CPU capacity sharing attribution is decided by hardhware
  

• * design so we can decide the sg_cp value at the beginning
  

• * for specific CPU.
  

• */
  

• if (sd && sd->parent)

• eenv->sg_cap = sd->parent->groups;
  

• else

• eenv->sg_cap = sd->groups;
  

• /* Estimate capacity index before task placement */
• cmp_idx = NR_CPUS + cpu;
• prev_cap_idx = find_new_capacity(eenv, cmp_idx);
• next_cap_idx = find_new_capacity(eenv, cpu);

                                           ^^^^

Based on the above suggestion, this parameter would be {PREV,NEXT}_CAP.

...

• /*

• * Computation is iteration sched_group from bottom to up level for
  

• * energy accumulation, 'sg_top' is top most sched_group:
  

• * - If the CPU frequency has no change before and after task placed
  

• *   onto the target CPU, set 'sg_top' to sched_group for the target
  

• *   CPU; this means only to calculate the energy for this single CPU
  

• *   and ignore other CPUs in the same clock domain.
  

+1

...

• * - If found the OPP frequency is changed after task placement then
  

• *   need to calculate all CPUs who bound in the same clock domain,
  

• *   so set 'sg_top' to shared capacity scheduling group.
  

• */
  

• if (prev_cap_idx != next_cap_idx)

• eenv->sg_top = eenv->sg_cap;
  

• else

• eenv->sg_top = sd->groups;
  
  

• /* energy is unscaled to reduce rounding errors */
  

• if (compute_energy(eenv, cpu) == -EINVAL) {
  

• 	eenv->next_cpu = eenv->prev_cpu;
  

• 	return -EINVAL;
  

• }
  

• /* energy is unscaled to reduce rounding errors */
• ret = compute_energy(eenv, cmp_idx);

                               ^^^^^^^

Same here... that would be a {PREV,NEXT}_CAP.

...

• if (ret < 0)

• return ret;
  
  

• } while (sg = sg->next, sg != sd->groups);

• ret = compute_energy(eenv, cpu);

• if (ret < 0)

• return ret;
  
  

• eenv->cpu[cpu].energy -= eenv->cpu[cmp_idx].energy;

    eenv->cpu[NEXT_CAP][cpu].energy -= eenv->cpu[PREV_CPU][cpu].energy;

...

return 0; }

-- 1.9.1

-- #include <best/regards.h>

Patrick Bellasi

On 17-Mar 20:05, Leo Yan wrote:

This patch is typical optimization by using more memory space to get better performance. eenv::cpu is extended as below usage:

+----------------+ ---> eenv::cpu[0] | new nrg | +----------------+ ---> eenv::cpu[NR_CPUS] | nrg(CPU) | +----------------+ ---> eenv::cpu[NR_CPUS*2] | nrg(Cluster) | +----------------+

If task placement is to trigger CPU frequency change, then we save the calculated energy value for without task placement into cpu[NR_CPUS*2..NR_CPUS*3-1], later if there has another CPU also need this same value for calculation, then it can directly fetch this value. So can avoid duplicate calculation for CPUs in the same cluster.

Change-Id: Ic1fbdc3513a8f90148e3dfabe385f40fdbe609bd Signed-off-by: Leo Yan leo.yan@linaro.org

---

kernel/sched/fair.c | 33 ++++++++++++++++++++++++++++----- 1 file changed, 28 insertions(+), 5 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 4811fce..b834fb3 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5473,7 +5473,9 @@ struct energy_env { /* Estimated energy variation wrt previous CPU */ int nrg_delta;

• } cpu[NR_CPUS*2];

• /* Flag for if has calculated already */
  

• int	used;
  

• } cpu[NR_CPUS*3];

  /* The morst energy efficient CPU for the specified energy_env::p */ int next_cpu;

@@ -5725,6 +5727,9 @@ static int compute_energy(struct energy_env *eenv, int candidate)

WARN_ON(!eenv->sg_top->sge);

• if (eenv->cpu[candidate].used)

• return 0;
  

• /* If a cpu is hotplugged in while we are in this function,
  • it does not appear in the existing eenv::sg_top mask
  • which came from the sched_group pointer of the

@@ -5782,6 +5787,7 @@ static int compute_energy(struct energy_env *eenv, int candidate) if (cpu_count) return -EINVAL;

• eenv->cpu[candidate].used = 1;

That's interesting... Chris should have something similar in v4.14... although not exactly the same.

Can't we recycle on of the already existing variable (e.g. nrg_delta) has a sentinel to flag when the slot is already in use?

Another alternative could be to recycle the MSBs of cpu_id to encode some flags like this one.

return 0; }

@@ -5810,8 +5816,7 @@ static int compute_task_energy(struct energy_env *eenv, int cpu) eenv->sg_cap = sd->groups;

/* Estimate capacity index before task placement */

• cmp_idx = NR_CPUS + cpu;
• prev_cap_idx = find_new_capacity(eenv, cmp_idx);

• prev_cap_idx = find_new_capacity(eenv, cpu + NR_CPUS); next_cap_idx = find_new_capacity(eenv, cpu);

  /*

@@ -5825,10 +5830,25 @@ static int compute_task_energy(struct energy_env *eenv, int cpu) * need to calculate all CPUs who bound in the same clock domain, * so set 'sg_top' to shared capacity scheduling group. */

• if (prev_cap_idx != next_cap_idx)

• if (prev_cap_idx != next_cap_idx) { eenv->sg_top = eenv->sg_cap;

• else

• /*
  

•  * eenv::cpus[(NR_CPUS*2)..(NR_CPUS*3-1)] is used to calculate
  

•  * whole cluster level energy calculation; so this value also
  

•  * can be used by other CPUs in the same cluster to calculate
  

•  * difference.
  

•  */
  

• cmp_idx  = cpumask_first(sched_group_cpus(eenv->sg_top));
  

• cmp_idx += NR_CPUS * 2;
  

• find_new_capacity(eenv, cmp_idx);
  

• } else { eenv->sg_top = sd->groups;

• /*
  

•  * eenv::cpus[(NR_CPUS)..(NR_CPUS*2-1)] is used to calculate
  

•  * single CPU energy calculation.
  

•  */
  

• cmp_idx = cpu + NR_CPUS;
  

• }

I like memorization techniques... but we should really try to get it working by defining a proper struct layout/nesting instead of playing math on indexes like here above... it's so error prone :/

/* energy is unscaled to reduce rounding errors */ ret = compute_energy(eenv, cmp_idx); @@ -7146,6 +7166,9 @@ static int select_energy_cpu_brute(struct task_struct *p, int prev_cpu, int sync if (backup_cpu >= 0) cpumask_set_cpu(backup_cpu, &eenv->cpus_mask);

• /* Clear energy calculation data */

• memset(eenv->cpu, 0, sizeof(eenv->cpu));

• select_energy_cpu_idx(eenv);

  /* Check if eenv::next_cpu is a more energy efficient CPU */

-- 1.9.1

-- #include <best/regards.h>

Patrick Bellasi

On 17-Mar 20:05, Leo Yan wrote:

When calculation energy difference before and after task placement on specific CPU, the idle state selection sometimes is based on the idle state index and sometimes based on the utilization to estimation. So the different idle state selections even happens on same one CPU, and the idle state estimation code is totally different with current CPU idle governor.

Moreover, the estimated IDLE stat is always a bit "random" and it seems to not give big advantages in terms of energy aware decisions...

Avoid to introduce big deviation for energy calculation, let's remove the idle state estimation.

.. that's why the simplifies energy model Dietmar is going to post on LKML is not considering idle (and cluster) energy.

If you reached the same conclusions, we should really review/test/push for that simplifies mode because it will make our life so much easier... especially considering all the complexity we have here, also after applying all these patches you propose :)

Change-Id: I4de0df9ce8f4e425206bd14de7c8069b488c4483 Signed-off-by: Leo Yan leo.yan@linaro.org

---

kernel/sched/fair.c | 49 ------------------------------------------------- 1 file changed, 49 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index b834fb3..4e43c9a 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5609,8 +5609,6 @@ static int group_idle_state(struct energy_env *eenv, int cpu_id) { struct sched_group *sg = eenv->sg; int i, state = INT_MAX;

• int src_in_grp, dst_in_grp;

• long grp_util = 0;

  /* Find the shallowest idle state in the sched group. */ for_each_cpu(i, sched_group_cpus(sg))

@@ -5619,53 +5617,6 @@ static int group_idle_state(struct energy_env *eenv, int cpu_id) /* Take non-cpuidle idling into account (active idle/arch_cpu_idle()) */ state++;

• src_in_grp = cpumask_test_cpu(eenv->prev_cpu, sched_group_cpus(sg));
• dst_in_grp = cpumask_test_cpu(cpu_id, sched_group_cpus(sg));
• if (src_in_grp == dst_in_grp) {

• /* both CPUs under consideration are in the same group or not in
  

•  * either group, migration should leave idle state the same.
  

•  */
  

• goto end;
  

• }
• /*

• * Try to estimate if a deeper idle state is
  

• * achievable when we move the task.
  

• */
  

• for_each_cpu(i, sched_group_cpus(sg)) {

• grp_util += cpu_util_wake(i, eenv->p);
  

• if (unlikely(i == cpu_id))
  

• 	grp_util += eenv->util_delta;
  

• }
• if (grp_util <=

• ((long)sg->sgc->max_capacity * (int)sg->group_weight)) {
  

• /* after moving, this group is at most partly
  

•  * occupied, so it should have some idle time.
  

•  */
  

• int max_idle_state_idx = sg->sge->nr_idle_states - 2;
  

• int new_state = grp_util * max_idle_state_idx;
  

• if (grp_util <= 0)
  

• 	/* group will have no util, use lowest state */
  

• 	new_state = max_idle_state_idx + 1;
  

• else {
  

• 	/* for partially idle, linearly map util to idle
  

• 	 * states, excluding the lowest one. This does not
  

• 	 * correspond to the state we expect to enter in
  

• 	 * reality, but an indication of what might happen.
  

• 	 */
  

• 	new_state = min(max_idle_state_idx, (int)
  

• 			(new_state / sg->sgc->max_capacity));
  

• 	new_state = max_idle_state_idx - new_state;
  

• }
  

• state = new_state;
  

• } else {

• /* After moving, the group will be fully occupied
  

•  * so assume it will not be idle at all.
  

•  */
  

• state = 0;
  

• }

-end: return state; }

-- 1.9.1

-- #include <best/regards.h>

Patrick Bellasi