On Fri, Apr 17, 2015 at 10:34:21PM +0100, Wu, Junjie wrote:

On 4/15/2015 22:29, Michael Turquette wrote:

...

From: Morten Rasmussen Morten.Rasmussen@arm.com

Architectures that don't have any other means for tracking cpu frequency changes need a callback from cpufreq to implement a scaling factor to enable scale-invariant per-entity load-tracking in the scheduler.

To compute the scale invariance correction factor the architecture would need to know both the max frequency and the current frequency. This patch defines weak functions for setting both from cpufreq.

Related architecture specific functions use weak function definitions. The same approach is followed here.

These callbacks can be used to implement frequency scaling of cpu capacity later.

Cc: Rafael J. Wysocki rjw@rjwysocki.net Cc: Viresh Kumar viresh.kumar@linaro.org Signed-off-by: Morten Rasmussen morten.rasmussen@arm.com

---

drivers/cpufreq/cpufreq.c | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/drivers/cpufreq/cpufreq.c b/drivers/cpufreq/cpufreq.c index 28e59a4..3c6398a 100644 --- a/drivers/cpufreq/cpufreq.c +++ b/drivers/cpufreq/cpufreq.c @@ -280,6 +280,10 @@ static void adjust_jiffies(unsigned long val, struct cpufreq_freqs *ci) #endif }

+void __weak arch_scale_set_curr_freq(int cpu, unsigned long freq) {}

+void __weak arch_scale_set_max_freq(int cpu, unsigned long freq) {}

• static void __cpufreq_notify_transition(struct cpufreq_policy *policy, struct cpufreq_freqs *freqs, unsigned int state) {

@@ -317,6 +321,7 @@ static void __cpufreq_notify_transition(struct cpufreq_policy *policy, pr_debug("FREQ: %lu - CPU: %lu\n", (unsigned long)freqs->new, (unsigned long)freqs->cpu); trace_cpu_frequency(freqs->new, freqs->cpu);

• arch_scale_set_curr_freq(freqs->cpu, freqs->new);
  

  srcu_notifier_call_chain(&cpufreq_transition_notifier_list, CPUFREQ_POSTCHANGE, freqs); if (likely(policy) && likely(policy->cpu == freqs->cpu))

@@ -2148,7 +2153,7 @@ static int cpufreq_set_policy(struct cpufreq_policy *policy, struct cpufreq_policy *new_policy) { struct cpufreq_governor *old_gov;

• int ret;

• int ret, cpu;

  pr_debug("setting new policy for CPU %u: %u - %u kHz\n", new_policy->cpu, new_policy->min, new_policy->max);

@@ -2186,6 +2191,12 @@ static int cpufreq_set_policy(struct cpufreq_policy *policy, policy->min = new_policy->min; policy->max = new_policy->max;

• for_each_cpu(cpu, policy->cpus) {

• arch_scale_set_max_freq(cpu, policy->max);
  

• /* Workaround for corner cases where notifiers don't fire */
  

• arch_scale_set_curr_freq(cpu, policy->cur);
  

• }
• pr_debug("new min and max freqs are %u - %u kHz\n", policy->min, policy->max);

Just curious why we need these new callbacks? I don't think they are providing any new information not already given by existing cpufreq policy and transition notifications.

Right. They are providing the same information I think. I went with the __weak function callbacks as this method is used for the existing scaling functions used by the scheduler (arch_scale_{cpu,freq}_capacity()). However, that is changing now so I should give it a try and see if we can use the notifiers instead. There might be some initialization problems though as the notifier has to be registrered before cpufreq initializes the first (default) policy for us to know what the max frequency is.

Morten

On 4/24/2015 7:50, Morten Rasmussen wrote:

On Mon, Apr 20, 2015 at 12:54:15PM +0100, Morten Rasmussen wrote:

...

On Fri, Apr 17, 2015 at 10:34:21PM +0100, Wu, Junjie wrote:

...

On 4/15/2015 22:29, Michael Turquette wrote:

...

From: Morten Rasmussen Morten.Rasmussen@arm.com

Architectures that don't have any other means for tracking cpu frequency changes need a callback from cpufreq to implement a scaling factor to enable scale-invariant per-entity load-tracking in the scheduler.

To compute the scale invariance correction factor the architecture would need to know both the max frequency and the current frequency. This patch defines weak functions for setting both from cpufreq.

Related architecture specific functions use weak function definitions. The same approach is followed here.

These callbacks can be used to implement frequency scaling of cpu capacity later.

Cc: Rafael J. Wysocki rjw@rjwysocki.net Cc: Viresh Kumar viresh.kumar@linaro.org Signed-off-by: Morten Rasmussen morten.rasmussen@arm.com

---

drivers/cpufreq/cpufreq.c | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/drivers/cpufreq/cpufreq.c b/drivers/cpufreq/cpufreq.c index 28e59a4..3c6398a 100644 --- a/drivers/cpufreq/cpufreq.c +++ b/drivers/cpufreq/cpufreq.c @@ -280,6 +280,10 @@ static void adjust_jiffies(unsigned long val, struct cpufreq_freqs *ci) #endif }

+void __weak arch_scale_set_curr_freq(int cpu, unsigned long freq) {}

+void __weak arch_scale_set_max_freq(int cpu, unsigned long freq) {}

• static void __cpufreq_notify_transition(struct cpufreq_policy *policy, struct cpufreq_freqs *freqs, unsigned int state) {

@@ -317,6 +321,7 @@ static void __cpufreq_notify_transition(struct cpufreq_policy *policy, pr_debug("FREQ: %lu - CPU: %lu\n", (unsigned long)freqs->new, (unsigned long)freqs->cpu); trace_cpu_frequency(freqs->new, freqs->cpu);

• arch_scale_set_curr_freq(freqs->cpu, freqs->new);
  srcu_notifier_call_chain(&cpufreq_transition_notifier_list,
  		CPUFREQ_POSTCHANGE, freqs);
  if (likely(policy) && likely(policy->cpu == freqs->cpu))
  

@@ -2148,7 +2153,7 @@ static int cpufreq_set_policy(struct cpufreq_policy *policy, struct cpufreq_policy *new_policy) { struct cpufreq_governor *old_gov;

• int ret;

• int ret, cpu;

  pr_debug("setting new policy for CPU %u: %u - %u kHz\n", new_policy->cpu, new_policy->min, new_policy->max);

@@ -2186,6 +2191,12 @@ static int cpufreq_set_policy(struct cpufreq_policy *policy, policy->min = new_policy->min; policy->max = new_policy->max;

• for_each_cpu(cpu, policy->cpus) {

• arch_scale_set_max_freq(cpu, policy->max);
  

• /* Workaround for corner cases where notifiers don't fire */
  

• arch_scale_set_curr_freq(cpu, policy->cur);
  

• }
• pr_debug("new min and max freqs are %u - %u kHz\n", policy->min, policy->max);

Just curious why we need these new callbacks? I don't think they are providing any new information not already given by existing cpufreq policy and transition notifications.

Right. They are providing the same information I think. I went with the __weak function callbacks as this method is used for the existing scaling functions used by the scheduler (arch_scale_{cpu,freq}_capacity()). However, that is changing now so I should give it a try and see if we can use the notifiers instead. There might be some initialization problems though as the notifier has to be registrered before cpufreq initializes the first (default) policy for us to know what the max frequency is.

I think the patch below gives us what we need using the cpufreq notifiers instead. It is just a single patch, no neeed to touch cpufreq, so the patch below replaces both patch 1 and 2.

I haven't found any initialization problems on TC2. I'm not 100% sure that policy->cur is set at initilization of all cpufreq drivers. Drivers are not required to have a get-function which seems required for policy->cur to be set.

Even if cpufreq driver's init doesn't fill in policy->cur, cpufreq_init_policy() would call cpufreq_set_policy() that sets frequency. You would receive both policy and transition notifications where the POSTCHANGE would have the right frequency information. I think your patch would be fine.

I haven't tested with hotplug yet.

Mike: I have pushed the patch to linux-arm.org as well.

Morten

From 0fe329c77782acde0290954779a2ee17920a3dad Mon Sep 17 00:00:00 2001 From: Morten Rasmussen Morten.Rasmussen@arm.com Date: Mon, 22 Sep 2014 17:24:03 +0100 Subject: [PATCH] arm: Frequency invariant scheduler load-tracking support

Implements arch-specific function to provide the scheduler with a frequency scaling correction factor for more accurate load-tracking. The factor is:

current_freq(cpu) << SCHED_CAPACITY_SHIFT / max_freq(cpu)

This implementation only provides frequency invariance. No micro-architecture invariance yet.

Cc: Russell King linux@arm.linux.org.uk

Signed-off-by: Morten Rasmussen morten.rasmussen@arm.com

arch/arm/include/asm/topology.h | 7 ++++++ arch/arm/kernel/smp.c | 53 +++++++++++++++++++++++++++++++++++++++-- arch/arm/kernel/topology.c | 17 +++++++++++++ 3 files changed, 75 insertions(+), 2 deletions(-)

diff --git a/arch/arm/include/asm/topology.h b/arch/arm/include/asm/topology.h index 2fe85ff..4b985dc 100644 --- a/arch/arm/include/asm/topology.h +++ b/arch/arm/include/asm/topology.h @@ -24,6 +24,13 @@ void init_cpu_topology(void); void store_cpu_topology(unsigned int cpuid); const struct cpumask *cpu_coregroup_mask(int cpu);

+#define arch_scale_freq_capacity arm_arch_scale_freq_capacity +struct sched_domain; +extern +unsigned long arm_arch_scale_freq_capacity(struct sched_domain *sd, int cpu);

+DECLARE_PER_CPU(atomic_long_t, cpu_freq_capacity);

• #else

  static inline void init_cpu_topology(void) { }

diff --git a/arch/arm/kernel/smp.c b/arch/arm/kernel/smp.c index 86ef244..297ce1b 100644 --- a/arch/arm/kernel/smp.c +++ b/arch/arm/kernel/smp.c @@ -672,12 +672,34 @@ static DEFINE_PER_CPU(unsigned long, l_p_j_ref); static DEFINE_PER_CPU(unsigned long, l_p_j_ref_freq); static unsigned long global_l_p_j_ref; static unsigned long global_l_p_j_ref_freq; +static DEFINE_PER_CPU(atomic_long_t, cpu_max_freq); +DEFINE_PER_CPU(atomic_long_t, cpu_freq_capacity);

+/*

• • Scheduler load-tracking scale-invariance
• • Provides the scheduler with a scale-invariance correction factor that
• • compensates for frequency scaling through arch_scale_freq_capacity()
• • (implemented in topology.c).
• */

+static inline +void scale_freq_capacity(int cpu, unsigned long curr, unsigned long max) +{

• unsigned long capacity;
• if (!max)

• return;
  

• capacity = (curr << SCHED_CAPACITY_SHIFT) / max;
• atomic_long_set(&per_cpu(cpu_freq_capacity, cpu), capacity);

+}

static int cpufreq_callback(struct notifier_block *nb, unsigned long val, void *data) { struct cpufreq_freqs *freq = data; int cpu = freq->cpu;

• unsigned long max = atomic_long_read(&per_cpu(cpu_max_freq, cpu));

  if (freq->flags & CPUFREQ_CONST_LOOPS) return NOTIFY_OK;

@@ -702,6 +724,9 @@ static int cpufreq_callback(struct notifier_block *nb, per_cpu(l_p_j_ref_freq, cpu), freq->new); }

• scale_freq_capacity(cpu, freq->new, max);
• return NOTIFY_OK; }

@@ -709,11 +734,35 @@ static struct notifier_block cpufreq_notifier = { .notifier_call = cpufreq_callback, };

+static int cpufreq_policy_callback(struct notifier_block *nb,

• 				unsigned long val, void *data)
  

+{

• struct cpufreq_policy *policy = data;
• int i;
• for_each_cpu(i, policy->cpus) {

• scale_freq_capacity(i, policy->cur, policy->max);
  

• atomic_long_set(&per_cpu(cpu_max_freq, i), policy->max);
  

• }
• return NOTIFY_OK;

+}

You need to skip all other events except CPUFREQ_NOTIFY. CPUFREQ_ADJUST and CPUFREQ_INCOMPATIBLE are meant for drivers to change policy->min/max, and it not uncommon to have policy->max adjusted by kernel thermal drivers. CPUFREQ_NOTIFY is the final result of new limits.

- Junjie

+static struct notifier_block cpufreq_policy_notifier = {

• .notifier_call = cpufreq_policy_callback,

+};

• static int __init register_cpufreq_notifier(void) {

• return cpufreq_register_notifier(&cpufreq_notifier,

• int ret;
• ret = cpufreq_register_notifier(&cpufreq_notifier, CPUFREQ_TRANSITION_NOTIFIER);
• if (ret)

• return ret;
  

• return cpufreq_register_notifier(&cpufreq_policy_notifier,

• 				CPUFREQ_POLICY_NOTIFIER);
  

  } core_initcall(register_cpufreq_notifier);

• #endif

diff --git a/arch/arm/kernel/topology.c b/arch/arm/kernel/topology.c index 08b7847..9c09e6e 100644 --- a/arch/arm/kernel/topology.c +++ b/arch/arm/kernel/topology.c @@ -169,6 +169,23 @@ static void update_cpu_capacity(unsigned int cpu) cpu, arch_scale_cpu_capacity(NULL, cpu)); }

+/*

• • Scheduler load-tracking scale-invariance
• • Provides the scheduler with a scale-invariance correction factor that
• • compensates for frequency scaling (arch_scale_freq_capacity()). The scaling
• • factor is updated in smp.c
• */

+unsigned long arm_arch_scale_freq_capacity(struct sched_domain *sd, int cpu) +{

• unsigned long curr = atomic_long_read(&per_cpu(cpu_freq_capacity, cpu));
• if (!curr)

• return SCHED_CAPACITY_SCALE;
  

• return curr;

+}

• #else static inline void parse_dt_topology(void) {} static inline void update_cpu_capacity(unsigned int cpuid) {}

Quoting Morten Rasmussen (2015-04-27 06:52:10)

On Fri, Apr 24, 2015 at 06:32:02PM +0100, Wu, Junjie wrote:

...

On 4/24/2015 7:50, Morten Rasmussen wrote:

...

On Mon, Apr 20, 2015 at 12:54:15PM +0100, Morten Rasmussen wrote:

...

On Fri, Apr 17, 2015 at 10:34:21PM +0100, Wu, Junjie wrote:

...

On 4/15/2015 22:29, Michael Turquette wrote:

...

From: Morten Rasmussen Morten.Rasmussen@arm.com

Architectures that don't have any other means for tracking cpu frequency changes need a callback from cpufreq to implement a scaling factor to enable scale-invariant per-entity load-tracking in the scheduler.

To compute the scale invariance correction factor the architecture would need to know both the max frequency and the current frequency. This patch defines weak functions for setting both from cpufreq.

Related architecture specific functions use weak function definitions. The same approach is followed here.

These callbacks can be used to implement frequency scaling of cpu capacity later.

Cc: Rafael J. Wysocki rjw@rjwysocki.net Cc: Viresh Kumar viresh.kumar@linaro.org Signed-off-by: Morten Rasmussen morten.rasmussen@arm.com

---

drivers/cpufreq/cpufreq.c | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/drivers/cpufreq/cpufreq.c b/drivers/cpufreq/cpufreq.c index 28e59a4..3c6398a 100644 --- a/drivers/cpufreq/cpufreq.c +++ b/drivers/cpufreq/cpufreq.c @@ -280,6 +280,10 @@ static void adjust_jiffies(unsigned long val, struct cpufreq_freqs *ci) #endif }

+void __weak arch_scale_set_curr_freq(int cpu, unsigned long freq) {}

+void __weak arch_scale_set_max_freq(int cpu, unsigned long freq) {}

• static void __cpufreq_notify_transition(struct cpufreq_policy *policy, struct cpufreq_freqs *freqs, unsigned int state) {

@@ -317,6 +321,7 @@ static void __cpufreq_notify_transition(struct cpufreq_policy *policy, pr_debug("FREQ: %lu - CPU: %lu\n", (unsigned long)freqs->new, (unsigned long)freqs->cpu); trace_cpu_frequency(freqs->new, freqs->cpu);

•            arch_scale_set_curr_freq(freqs->cpu, freqs->new);
             srcu_notifier_call_chain(&cpufreq_transition_notifier_list,
                             CPUFREQ_POSTCHANGE, freqs);
             if (likely(policy) && likely(policy->cpu == freqs->cpu))
  

@@ -2148,7 +2153,7 @@ static int cpufreq_set_policy(struct cpufreq_policy *policy, struct cpufreq_policy *new_policy) { struct cpufreq_governor *old_gov;

•    int ret;
  

•    int ret, cpu;
  
     pr_debug("setting new policy for CPU %u: %u - %u kHz\n",
              new_policy->cpu, new_policy->min, new_policy->max);
  

@@ -2186,6 +2191,12 @@ static int cpufreq_set_policy(struct cpufreq_policy *policy, policy->min = new_policy->min; policy->max = new_policy->max;

•    for_each_cpu(cpu, policy->cpus) {
  

•            arch_scale_set_max_freq(cpu, policy->max);
  

•            /* Workaround for corner cases where notifiers don't fire */
  

•            arch_scale_set_curr_freq(cpu, policy->cur);
  

•    }
  

•    pr_debug("new min and max freqs are %u - %u kHz\n",
              policy->min, policy->max);
  
  
  

Just curious why we need these new callbacks? I don't think they are providing any new information not already given by existing cpufreq policy and transition notifications.

Right. They are providing the same information I think. I went with the __weak function callbacks as this method is used for the existing scaling functions used by the scheduler (arch_scale_{cpu,freq}_capacity()). However, that is changing now so I should give it a try and see if we can use the notifiers instead. There might be some initialization problems though as the notifier has to be registrered before cpufreq initializes the first (default) policy for us to know what the max frequency is.

I think the patch below gives us what we need using the cpufreq notifiers instead. It is just a single patch, no neeed to touch cpufreq, so the patch below replaces both patch 1 and 2.

I haven't found any initialization problems on TC2. I'm not 100% sure that policy->cur is set at initilization of all cpufreq drivers. Drivers are not required to have a get-function which seems required for policy->cur to be set.

Even if cpufreq driver's init doesn't fill in policy->cur, cpufreq_init_policy() would call cpufreq_set_policy() that sets frequency. You would receive both policy and transition notifications where the POSTCHANGE would have the right frequency information. I think your patch would be fine.

AFAICT, you are not guaranteed a transition notification during init. I don't get one on TC2 if I use the userspace governor as default. But Viresh has confirmed that somebody will set policy->cur in all cases.

[...]

...

...

@@ -709,11 +734,35 @@ static struct notifier_block cpufreq_notifier = { .notifier_call = cpufreq_callback, };

+static int cpufreq_policy_callback(struct notifier_block *nb,

•                                       unsigned long val, void *data)
  

+{

• struct cpufreq_policy *policy = data;
• int i;
• for_each_cpu(i, policy->cpus) {

•       scale_freq_capacity(i, policy->cur, policy->max);
  

•       atomic_long_set(&per_cpu(cpu_max_freq, i), policy->max);
  

• }
• return NOTIFY_OK;

+}

You need to skip all other events except CPUFREQ_NOTIFY. CPUFREQ_ADJUST and CPUFREQ_INCOMPATIBLE are meant for drivers to change policy->min/max, and it not uncommon to have policy->max adjusted by kernel thermal drivers. CPUFREQ_NOTIFY is the final result of new limits.

Good point, thanks. No reason to let all the noise pass through to the scheduler. I have added:

•   if (val != CPUFREQ_NOTIFY)
  

•           return NOTIFY_OK;
  
  

before the loop above.

Mike: I have force-updated the branch to contain this fix.

Morten,

Thanks. I've gone ahead and pushed my RFC v2 to eas-dev yesterday. I'll rebase it to your patch after we complete this comments/review cycle.

Regards, Mike

Thanks, Morten

On 16 April 2015 at 07:29, Michael Turquette mturquette@linaro.org wrote:

From: Morten Rasmussen Morten.Rasmussen@arm.com

Implements arch-specific function to provide the scheduler with a frequency scaling correction factor for more accurate load-tracking. The factor is:

    current_freq(cpu) * SCHED_CAPACITY_SCALE / max_freq(cpu)

This implementation only provides frequency invariance. No micro-architecture invariance yet.

Cc: Russell King linux@arm.linux.org.uk Signed-off-by: Morten Rasmussen morten.rasmussen@arm.com

---

arch/arm/include/asm/topology.h | 4 ++++ arch/arm/kernel/topology.c | 41 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 45 insertions(+)

diff --git a/arch/arm/include/asm/topology.h b/arch/arm/include/asm/topology.h index 2fe85ff..86acd06 100644 --- a/arch/arm/include/asm/topology.h +++ b/arch/arm/include/asm/topology.h @@ -24,6 +24,10 @@ void init_cpu_topology(void); void store_cpu_topology(unsigned int cpuid); const struct cpumask *cpu_coregroup_mask(int cpu);

+#define arch_scale_freq_capacity arm_arch_scale_freq_capacity +struct sched_domain; +extern unsigned long arm_arch_scale_freq_capacity(struct sched_domain *sd, int cpu);

#else

static inline void init_cpu_topology(void) { } diff --git a/arch/arm/kernel/topology.c b/arch/arm/kernel/topology.c index 08b7847..eccc634 100644 --- a/arch/arm/kernel/topology.c +++ b/arch/arm/kernel/topology.c @@ -169,6 +169,47 @@ static void update_cpu_capacity(unsigned int cpu) cpu, arch_scale_cpu_capacity(NULL, cpu)); }

+/*

• • Scheduler load-tracking scale-invariance
• • Provides the scheduler with a scale-invariance correction factor that
• • compensates for frequency scaling.
• */

+static DEFINE_PER_CPU(atomic_long_t, cpu_freq_capacity); +static DEFINE_PER_CPU(atomic_long_t, cpu_max_freq);

+/* cpufreq callback function setting current cpu frequency */ +void arch_scale_set_curr_freq(int cpu, unsigned long freq) +{

•   unsigned long max = atomic_long_read(&per_cpu(cpu_max_freq, cpu));
  

•   unsigned long curr;
  

•   if (!max)
  

•           return;
  

•   curr = (freq * SCHED_CAPACITY_SCALE) / max;
  

•   atomic_long_set(&per_cpu(cpu_freq_capacity, cpu), curr);
  

+}

+/* cpufreq callback function setting max cpu frequency */ +void arch_scale_set_max_freq(int cpu, unsigned long freq) +{

•   atomic_long_set(&per_cpu(cpu_max_freq, cpu), freq);
  

You should update per_cpu(cpu_freq_capacity, cpu) too

+}

+/* arch_scale_freq_capacity() implementation called from scheduler */ +unsigned long arm_arch_scale_freq_capacity(struct sched_domain *sd, int cpu) +{

•   unsigned long curr = atomic_long_read(&per_cpu(cpu_freq_capacity, cpu));
  

•   if (!curr)
  

•           return SCHED_CAPACITY_SCALE;
  

•   return curr;
  

+}

#else static inline void parse_dt_topology(void) {} static inline void update_cpu_capacity(unsigned int cpuid) {} -- 1.9.1

On 23 April 2015 at 16:37, Morten Rasmussen morten.rasmussen@arm.com wrote:

On Wed, Apr 22, 2015 at 05:20:07PM +0100, Vincent Guittot wrote:

...

On 16 April 2015 at 07:29, Michael Turquette mturquette@linaro.org wrote:

...

From: Morten Rasmussen Morten.Rasmussen@arm.com

Implements arch-specific function to provide the scheduler with a frequency scaling correction factor for more accurate load-tracking. The factor is:

    current_freq(cpu) * SCHED_CAPACITY_SCALE / max_freq(cpu)

This implementation only provides frequency invariance. No micro-architecture invariance yet.

Cc: Russell King linux@arm.linux.org.uk Signed-off-by: Morten Rasmussen morten.rasmussen@arm.com

---

arch/arm/include/asm/topology.h | 4 ++++ arch/arm/kernel/topology.c | 41 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 45 insertions(+)

diff --git a/arch/arm/include/asm/topology.h b/arch/arm/include/asm/topology.h index 2fe85ff..86acd06 100644 --- a/arch/arm/include/asm/topology.h +++ b/arch/arm/include/asm/topology.h @@ -24,6 +24,10 @@ void init_cpu_topology(void); void store_cpu_topology(unsigned int cpuid); const struct cpumask *cpu_coregroup_mask(int cpu);

+#define arch_scale_freq_capacity arm_arch_scale_freq_capacity +struct sched_domain; +extern unsigned long arm_arch_scale_freq_capacity(struct sched_domain *sd, int cpu);

#else

static inline void init_cpu_topology(void) { } diff --git a/arch/arm/kernel/topology.c b/arch/arm/kernel/topology.c index 08b7847..eccc634 100644 --- a/arch/arm/kernel/topology.c +++ b/arch/arm/kernel/topology.c @@ -169,6 +169,47 @@ static void update_cpu_capacity(unsigned int cpu) cpu, arch_scale_cpu_capacity(NULL, cpu)); }

+/*

• • Scheduler load-tracking scale-invariance
• • Provides the scheduler with a scale-invariance correction factor that
• • compensates for frequency scaling.
• */

+static DEFINE_PER_CPU(atomic_long_t, cpu_freq_capacity); +static DEFINE_PER_CPU(atomic_long_t, cpu_max_freq);

+/* cpufreq callback function setting current cpu frequency */ +void arch_scale_set_curr_freq(int cpu, unsigned long freq) +{

•   unsigned long max = atomic_long_read(&per_cpu(cpu_max_freq, cpu));
  

•   unsigned long curr;
  

•   if (!max)
  

•           return;
  

•   curr = (freq * SCHED_CAPACITY_SCALE) / max;
  

•   atomic_long_set(&per_cpu(cpu_freq_capacity, cpu), curr);
  

+}

+/* cpufreq callback function setting max cpu frequency */ +void arch_scale_set_max_freq(int cpu, unsigned long freq) +{

•   atomic_long_set(&per_cpu(cpu_max_freq, cpu), freq);
  

You should update per_cpu(cpu_freq_capacity, cpu) too

Right. I made the assumption that we wouldn't change max very often. But I guess we could do something like:

    unsigned long curr, old_max;

    if (!freq)
            return;

    old_max = atomic_long_read(&per_cpu(cpu_max_freq, cpu));
    curr = atomic_long_read(&per_cpu(cpu_freq_capacity, cpu));
    curr = (curr * old_max)/freq;

    atomic_long_set(&per_cpu(cpu_max_freq, cpu), freq);
    atomic_long_set(&per_cpu(cpu_freq_capacity, cpu), curr);

We would get some rounding errors though if we change max. For example:

curr max capacity 200 1000 204 200 800 255 (as proposed for arch_scale_set_max_freq()) 200 800 256 (if computed by arch_scale_set_curr_freq())

This can only be avoided by having another per_cpu variable storing the curr freq too. It shouldn't be a big deal. I can fix that.

I don't have strong opinion about which proposal is the best but the use of another per cpu variable makes code much more simple and readable IMHO

Vincent

Thanks, Morten

Hi Mike,

On 16/04/15 06:29, Michael Turquette wrote:

This patch introduces the SCHED_ENERGY_FREQ sched feature, which is implemented using jump labels when SCHED_DEBUG is defined. It is statically set to false when SCHED_DEBUG is not defined and thus disabled by default.

Signed-off-by: Michael Turquette mturquette@linaro.org

kernel/sched/fair.c | 5 +++++ kernel/sched/features.h | 6 ++++++ 2 files changed, 11 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 46855d0..75aec8d 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -4207,6 +4207,11 @@ static inline void hrtick_update(struct rq *rq) } #endif +static inline bool sched_energy_freq(void) +{

• return sched_feat(SCHED_ENERGY_FREQ);

+}

/*

• The enqueue_task method is called before nr_running is
• increased. Here we update the fair scheduling stats and

diff --git a/kernel/sched/features.h b/kernel/sched/features.h index 91e33cd..77381cf 100644 --- a/kernel/sched/features.h +++ b/kernel/sched/features.h @@ -96,3 +96,9 @@ SCHED_FEAT(NUMA_FAVOUR_HIGHER, true) */ SCHED_FEAT(NUMA_RESIST_LOWER, false) #endif

+/*

• • Scheduler-driven CPU frequency selection aimed to save energy based on
• • load tracking
• */

+SCHED_FEAT(SCHED_ENERGY_FREQ, false)

Do we really need this? I understand that you don't want to add overhead in enqueue/dequeue/etc paths, but to me it looks a bit redundant as to enable the governor we have to both set it in scaling_governor and enable this sched feature.

Thanks,

- Juri

Hi,

On 16/04/15 19:41, Michael Turquette wrote:

Quoting Juri Lelli (2015-04-16 09:53:28)

...

Hi Mike,

On 16/04/15 06:29, Michael Turquette wrote:

...

This patch introduces the SCHED_ENERGY_FREQ sched feature, which is implemented using jump labels when SCHED_DEBUG is defined. It is statically set to false when SCHED_DEBUG is not defined and thus disabled by default.

Signed-off-by: Michael Turquette mturquette@linaro.org

kernel/sched/fair.c | 5 +++++ kernel/sched/features.h | 6 ++++++ 2 files changed, 11 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 46855d0..75aec8d 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -4207,6 +4207,11 @@ static inline void hrtick_update(struct rq *rq) } #endif +static inline bool sched_energy_freq(void) +{

• return sched_feat(SCHED_ENERGY_FREQ);
  

+}

/*

• The enqueue_task method is called before nr_running is
• increased. Here we update the fair scheduling stats and

diff --git a/kernel/sched/features.h b/kernel/sched/features.h index 91e33cd..77381cf 100644 --- a/kernel/sched/features.h +++ b/kernel/sched/features.h @@ -96,3 +96,9 @@ SCHED_FEAT(NUMA_FAVOUR_HIGHER, true) */ SCHED_FEAT(NUMA_RESIST_LOWER, false) #endif

+/*

• • Scheduler-driven CPU frequency selection aimed to save energy based on
• • load tracking
• */

+SCHED_FEAT(SCHED_ENERGY_FREQ, false)

Do we really need this? I understand that you don't want to add overhead in enqueue/dequeue/etc paths, but to me it looks a bit redundant as to enable the governor we have to both set it in scaling_governor and enable this sched feature.

I do not think it is redundant. If we remove this but the governor is not active then there is still overhead. cap_gov_update_cpu will call cpufreq_cpu_get(int cpu), fetch the policy pointer and only after that will we realize that there is no policy.gov_data, at which point we bail.

I'd prefer to avoid running through this code every time we enter {en,de}queue_task_fair and task_tick_fair.

Completely agree. That's exactly what I meant with "I understand that you don't want...", thanks for clarifying :).

An alternative might be to keep per-cpu pointers to gov_data. Then we only need to check for !per_cpu(cap_gov_data, cpu) and bail quickly.

Yeah, something like this might work better IMHO, so that we have a single switch for the whole thing.

Thanks,

- Juri

Regards, Mike

...

Thanks,

• Juri

On Thu, Apr 16, 2015 at 10:59 AM, Michael Turquette mturquette@linaro.org wrote:

Scheduler-driven cpu frequency selection is desirable as part of the on-going effort to make the scheduler better aware of energy consumption. No piece of the Linux kernel has a better view of the factors that affect a cpu frequency selection policy than the scheduler[0], and this patch is an attempt to get that discussion going again.

This patch implements a cpufreq governor, cap_gov, that directly accesses scheduler statistics, in particular the pelt data from cfs via the get_cpu_usage() function.

Put plainly, cap_gov selects the lowest cpu frequency that will prevent a runqueue from being over-utilized (until we hit the highest frequency of course).

cap_gov converts available cpu frequencies into capacity states. When the utilization of a cfs runqueue changes then the policy selects the capacity state which is the floor of the new usage.

Unlike the previous posting from 2014[1] this governor implements no policy of its own (e.g. with tunable thresholds for determining when to scale frequency), but instead implements a "follow the usage" method, where usage is defined as the cpu frequency-invariant product of utilization_load_avg and cpu_capacity_orig.

This governor is event-driven. There is no polling loop to check cpu idle time, or any other method which is unsynchronized with the scheduler. The entry points for this policy are in fair.c: enqueue_task_fair, dequeue_task_fair and task_tick_fair. run_rebalance_domains is used to kick the worker thread to prevent fatally re-entering into scheduler.

This policy is implemented using the cpufreq governor interface for two main reasons:

1. re-using the cpufreq machine drivers without using the governor

interface is hard.

2. using the cpufreq interface allows us to switch between the

scheduler-driven policy and legacy cpufreq governors such as ondemand at run-time. This is very useful for comparative testing and tuning.

Finally, it is worth mentioning that this approach neglects all scheduling classes except for cfs. It is possible to add support for deadline and other other classes here, but I also wonder if a multi-governor approach would be a more maintainable solution, where the cpufreq core aggregates the constraints set by multiple governors. Supporting such an approach in the cpufreq core would also allow for peripheral devices to place constraint on cpu frequency without having to hack such behavior in at the governor level.

Thanks to Juri Lelli juri.lelli@arm.com for doing a good bit of testing, bug fixing and contributing towards the design.

[0] http://article.gmane.org/gmane.linux.kernel/1499836 [1] https://lkml.org/lkml/2014/10/22/22

Signed-off-by: Michael Turquette mturquette@linaro.org

drivers/cpufreq/Kconfig | 22 +++ include/linux/cpufreq.h | 3 + kernel/sched/Makefile | 1 + kernel/sched/cap_gov.c | 361 ++++++++++++++++++++++++++++++++++++++++++++++++ kernel/sched/fair.c | 19 +++ kernel/sched/sched.h | 8 ++ 6 files changed, 414 insertions(+) create mode 100644 kernel/sched/cap_gov.c

diff --git a/drivers/cpufreq/Kconfig b/drivers/cpufreq/Kconfig index a171fef..654d70a 100644 --- a/drivers/cpufreq/Kconfig +++ b/drivers/cpufreq/Kconfig @@ -102,6 +102,15 @@ config CPU_FREQ_DEFAULT_GOV_CONSERVATIVE Be aware that not all cpufreq drivers support the conservative governor. If unsure have a look at the help section of the driver. Fallback governor will be the performance governor.

+config CPU_FREQ_DEFAULT_GOV_CAP_GOV

•   bool "cap_gov"
  

•   select CPU_FREQ_GOV_CAP_GOV
  

•   select CPU_FREQ_GOV_PERFORMANCE
  

•   help
  

•     Use the CPUfreq governor 'cap_gov' as default. This scales cpu
  

•     frequency from the scheduler as per-entity load tracking
  

•     statistics are updated.
  

endchoice

config CPU_FREQ_GOV_PERFORMANCE @@ -183,6 +192,19 @@ config CPU_FREQ_GOV_CONSERVATIVE

      If in doubt, say N.

+config CPU_FREQ_GOV_CAP_GOV

Two GOVs are redundant here and make it hard to read. A few name suggestions for your baby:

CPU_FREQ_GOV_SCHED_CAP CPU_FREQ_GOV_SCHED_STATS

•   tristate "'capacity governor' cpufreq governor"
  

•   depends on CPU_FREQ
  

•   select CPU_FREQ_GOV_COMMON
  

•   help
  

•     'cap_gov' - this governor scales cpu frequency from the
  

same as above

•     scheduler as a function of cpu capacity utilization. It does
  

•     not evaluate utilization on a periodic basis (unlike ondemand)
  

•     but instead is invoked from CFS when updating per-entity load
  

•     tracking statistics.
  

perhaps add something to the effect that it is more responsive than existing governors to really sell it? :)

•     If in doubt, say N.
  

comment "CPU frequency scaling drivers"

config CPUFREQ_DT diff --git a/include/linux/cpufreq.h b/include/linux/cpufreq.h index 7cdf63a..4fc066f 100644 --- a/include/linux/cpufreq.h +++ b/include/linux/cpufreq.h @@ -488,6 +488,9 @@ extern struct cpufreq_governor cpufreq_gov_ondemand; #elif defined(CONFIG_CPU_FREQ_DEFAULT_GOV_CONSERVATIVE) extern struct cpufreq_governor cpufreq_gov_conservative; #define CPUFREQ_DEFAULT_GOVERNOR (&cpufreq_gov_conservative) +#elif defined(CONFIG_CPU_FREQ_DEFAULT_GOV_CAP_GOV) +extern struct cpufreq_governor cpufreq_gov_cap_gov; +#define CPUFREQ_DEFAULT_GOVERNOR (&cpufreq_gov_cap_gov) #endif

/********************************************************************* diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile index 46be870..da601d5 100644 --- a/kernel/sched/Makefile +++ b/kernel/sched/Makefile @@ -19,3 +19,4 @@ obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o obj-$(CONFIG_SCHEDSTATS) += stats.o obj-$(CONFIG_SCHED_DEBUG) += debug.o obj-$(CONFIG_CGROUP_CPUACCT) += cpuacct.o +obj-$(CONFIG_CPU_FREQ_GOV_CAP_GOV) += cap_gov.o diff --git a/kernel/sched/cap_gov.c b/kernel/sched/cap_gov.c new file mode 100644 index 0000000..72873ab --- /dev/null +++ b/kernel/sched/cap_gov.c @@ -0,0 +1,361 @@ +/*

• • Copyright (C) 2014 Michael Turquette mturquette@linaro.org
• • This program is free software; you can redistribute it and/or modify
• • it under the terms of the GNU General Public License version 2 as
• • published by the Free Software Foundation.
• */

+#include <linux/cpufreq.h> +#include <linux/module.h> +#include <linux/kthread.h> +#include <linux/percpu.h>

+#include "sched.h"

+#define UP_THRESHOLD 95

A comment that this probably belong as a sysfs tunable

+#define THROTTLE_NSEC 50000000 /* 50ms default */

+/*

• • per-cpu pointer to atomic_t gov_data->cap_gov_wake_task

s/cap_gov_wake_task/need_wake_task/

• • used in scheduler hot paths {en,de}queueu, task_tick without having to
• • access struct cpufreq_policy and struct gov_data
• */

+static DEFINE_PER_CPU(atomic_t *, cap_gov_wake_task);

+/**

• • gov_data - per-policy data internal to the governor
• • @throttle: time until throttling period expires. Derived from THROTTLE_NSEC

@throttle_nsec ?

• • @task: worker task for dvfs transition that may block/sleep
• • @need_wake_task: flag the governor to wake this policy's worker thread
• • struct gov_data is the per-policy cap_gov-specific data structure. A
• • per-policy instance of it is created when the cap_gov governor receives
• • the CPUFREQ_GOV_START condition and a pointer to it exists in the gov_data
• • member of struct cpufreq_policy.
• • Readers of this data must call down_read(policy->rwsem). Writers must
• • call down_write(policy->rwsem).
• */

+struct gov_data {

•   ktime_t throttle;
  

•   unsigned int throttle_nsec;
  

•   struct task_struct *task;
  

•   atomic_t need_wake_task;
  

+};

+/**

• • cap_gov_select_freq - pick the next frequency for a cpu
• • @cpu: the cpu whose frequency may be changed
• • cap_gov_select_freq works in a way similar to the ondemand governor. First
• • we inspect the utilization of all of the cpus in this policy to find the
• • most utilized cpu. This is achieved by calling get_cpu_usage, which returns
• • frequency-invarant capacity utilization.
• • This max utilization is compared against the up_threshold (default 95%
• • utilization). If the max cpu utilization is greater than this threshold then
• • we scale the policy up to the max frequency. Othewise we find the lowest
• • frequency (smallest cpu capacity) that is still larger than the max capacity
• • utilization for this policy.
• • Returns frequency selected.
• */

+static unsigned long cap_gov_select_freq(struct cpufreq_policy *policy) +{

•   int cpu = 0;
  

•   struct gov_data *gd;
  

•   int index;
  

•   unsigned long freq = 0, max_usage = 0, cap = 0, usage = 0;
  

•   struct cpufreq_frequency_table *pos;
  

•   if (!policy->gov_data)
  

•           goto out;
  

•   gd = policy->gov_data;
  

•   /*
  

•    * get_cpu_usage is called without locking the runqueues. This is the
  

•    * same behavior used by find_busiest_cpu in load_balance. We are
  

•    * willing to accept occasionally stale data here in exchange for
  

•    * lockless behavior.
  

•    */
  

•   for_each_cpu(cpu, policy->cpus) {
  

•           usage = get_cpu_usage(cpu);
  

•           trace_printk("cpu = %d usage = %lu", cpu, usage);
  

•           if (usage > max_usage)
  

•                   max_usage = usage;
  

•   }
  

•   trace_printk("max_usage = %lu", max_usage);
  

•   /* find the utilization threshold at which we scale up frequency */
  

•   index = cpufreq_frequency_table_get_index(policy, policy->cur);
  

•   /*
  

•    * converge towards max_usage. We want the lowest frequency whose
  

•    * capacity is >= to max_usage. In other words:
  

•    *
  

•    *      find capacity == floor(usage)
  

•    *
  

•    * Sadly cpufreq freq tables are not guaranteed to be ordered by
  

•    * frequency...
  

•    */
  

•   freq = policy->max;
  

•   cpufreq_for_each_entry(pos, policy->freq_table) {
  

•           cap = pos->frequency * SCHED_CAPACITY_SCALE /
  

•                   policy->max;
  

•           if (max_usage < cap && pos->frequency < freq)
  

•                   freq = pos->frequency;
  

•           trace_printk("cpu = %u max_usage = %lu cap = %lu \
  

•                           table_freq = %u freq = %lu",
  

•                           cpumask_first(policy->cpus), max_usage, cap,
  

•                           pos->frequency, freq);
  

•   }
  

+out:

•   trace_printk("cpu %d final freq %lu", cpu, freq);
  

•   return freq;
  

+}

+/*

• • we pass in struct cpufreq_policy. This is safe because changing out the
• • policy requires a call to __cpufreq_governor(policy, CPUFREQ_GOV_STOP),
• • which tears down all of the data structures and __cpufreq_governor(policy,
• • CPUFREQ_GOV_START) will do a full rebuild, including this kthread with the
• • new policy pointer
• */

+static int cap_gov_thread(void *data) +{

•   struct sched_param param;
  

•   struct cpufreq_policy *policy;
  

•   struct gov_data *gd;
  

•   unsigned long freq;
  

•   int ret;
  

•   policy = (struct cpufreq_policy *) data;
  

•   if (!policy) {
  

•           pr_warn("%s: missing policy\n", __func__);
  

•           do_exit(-EINVAL);
  

•   }
  

•   gd = policy->gov_data;
  

•   if (!gd) {
  

•           pr_warn("%s: missing governor data\n", __func__);
  

•           do_exit(-EINVAL);
  

•   }
  

•   param.sched_priority = 0;
  

•   sched_setscheduler(current, SCHED_FIFO, &param);
  

•   set_cpus_allowed_ptr(current, policy->related_cpus);
  

•   /* main loop of the per-policy kthread */
  

•   do {
  

•           down_write(&policy->rwsem);
  

•           if (!atomic_read(&gd->need_wake_task))  {
  

•                   if (kthread_should_stop())
  

•                           break;
  

•                   trace_printk("NOT waking up kthread (%d)", gd->task->pid);
  

•                   up_write(&policy->rwsem);
  

•                   set_current_state(TASK_INTERRUPTIBLE);
  

•                   schedule();
  

•                   continue;
  

•           }
  

•           trace_printk("kthread %d requested freq switch", gd->task->pid);
  

•           freq = cap_gov_select_freq(policy);
  

•           ret = __cpufreq_driver_target(policy, freq,
  

•                           CPUFREQ_RELATION_H);
  

•           if (ret)
  

•                   pr_debug("%s: __cpufreq_driver_target returned %d\n",
  

•                                   __func__, ret);
  

•           trace_printk("kthread %d requested freq switch", gd->task->pid);
  

•           gd->throttle = ktime_add_ns(ktime_get(), gd->throttle_nsec);
  

•           atomic_set(&gd->need_wake_task, 0);
  

•           up_write(&policy->rwsem);
  

•   } while (!kthread_should_stop());
  

•   do_exit(0);
  

+}

+static void cap_gov_wake_up_process(struct task_struct *task) +{

•   /* this is null during early boot */
  

•   if (IS_ERR_OR_NULL(task)) {
  

•           return;
  

•   }
  

•   wake_up_process(task);
  

+}

+void cap_gov_kick_thread(int cpu) +{

•   struct cpufreq_policy *policy;
  

•   struct gov_data *gd = NULL;
  

•   policy = cpufreq_cpu_get(cpu);
  

•   if (IS_ERR_OR_NULL(policy))
  

•           return;
  

•   gd = policy->gov_data;
  

•   if (!gd)
  

•           goto out;
  

•   /* per-cpu access not needed here since we have gd */
  

•   if (atomic_read(&gd->need_wake_task)) {
  

•           trace_printk("waking up kthread (%d)", gd->task->pid);
  

•           cap_gov_wake_up_process(gd->task);
  

•   }
  

+out:

•   cpufreq_cpu_put(policy);
  

+}

+/**

• • cap_gov_update_cpu - interface to scheduler for changing capacity values
• • @cpu: cpu whose capacity utilization has recently changed
• • cap_gov_udpate_cpu is an interface exposed to the scheduler so that the
• • scheduler may inform the governor of updates to capacity utilization and
• • make changes to cpu frequency. Currently this interface is designed around
• • PELT values in CFS. It can be expanded to other scheduling classes in the
• • future if needed.
• • The semantics of this call vary based on the cpu frequency scaling
• • characteristics of the hardware.
• • If kicking off a dvfs transition is an operation that might block or sleep
• • in the cpufreq driver then we set the need_wake_task flag in this function

The comment here isn't obvious since first glance you don't touch need_wake_task. Perhaps clarify it as follows?

we set the need_wake_task (cap_gov_wake_task is a pointer to it)

• • and return. Selecting a frequency and programming it is done in a dedicated
• • kernel thread which will be woken up from rebalance_domains. See
• • cap_gov_kick_thread above.
• • If kicking off a dvfs transition is an operation that returns quickly in the
• • cpufreq driver and will never sleep then we select the frequency in this
• • function and program the hardware for it in the scheduler hot path. No
• • dedicated kthread is needed.
• */

+void cap_gov_update_cpu(int cpu) +{

•   struct cpufreq_policy *policy;
  

•   struct gov_data *gd;
  

•   /* XXX put policy pointer in per-cpu data? */
  

•   policy = cpufreq_cpu_get(cpu);
  

•   if (IS_ERR_OR_NULL(policy)) {
  

•           return;
  

•   }
  

•   if (!policy->gov_data) {
  

•           trace_printk("missing governor data");
  

•           goto out;
  

•   }
  

•   gd = policy->gov_data;
  

•   /* bail early if we are throttled */
  

•   if (ktime_before(ktime_get(), gd->throttle)) {
  

•           trace_printk("THROTTLED");
  

•           goto out;
  

•   }
  

•   atomic_set(per_cpu(cap_gov_wake_task, cpu), 1);
  

+out:

•   cpufreq_cpu_put(policy);
  

•   return;
  

+}

+static void cap_gov_start(struct cpufreq_policy *policy) +{

•   int cpu;
  

•   struct gov_data *gd;
  

•   /* prepare per-policy private data */
  

•   gd = kzalloc(sizeof(*gd), GFP_KERNEL);
  

•   if (!gd) {
  

•           pr_debug("%s: failed to allocate private data\n", __func__);
  

•           return;
  

•   }
  

•   /*
  

•    * Don't ask for freq changes at an higher rate than what
  

•    * the driver advertises as transition latency.
  

•    */
  

•   gd->throttle_nsec = policy->cpuinfo.transition_latency ?
  

•                       policy->cpuinfo.transition_latency :
  

•                       THROTTLE_NSEC;
  

•   pr_debug("%s: throttle threshold = %u [ns]\n",
  

•             __func__, gd->throttle_nsec);
  

•   /* save per-cpu pointer to per-policy need_wake_task */
  

•   for_each_cpu(cpu, policy->related_cpus)
  

•           per_cpu(cap_gov_wake_task, cpu) = &gd->need_wake_task;
  

•   /* init per-policy kthread */
  

•   gd->task = kthread_create(cap_gov_thread, policy, "kcap_gov_task");
  

•   if (IS_ERR_OR_NULL(gd->task))
  

•           pr_err("%s: failed to create kcap_gov_task thread\n", __func__);
  

•   policy->gov_data = gd;
  

+}

+static void cap_gov_stop(struct cpufreq_policy *policy) +{

•   struct gov_data *gd;
  

•   gd = policy->gov_data;
  

•   policy->gov_data = NULL;
  

•   kthread_stop(gd->task);
  

•   /* FIXME replace with devm counterparts? */
  

•   kfree(gd);
  

+}

+static int cap_gov_setup(struct cpufreq_policy *policy, unsigned int event) +{

•   switch (event) {
  

•           case CPUFREQ_GOV_START:
  

•                   /* Start managing the frequency */
  

•                   cap_gov_start(policy);
  

•                   return 0;
  

•           case CPUFREQ_GOV_STOP:
  

•                   cap_gov_stop(policy);
  

•                   return 0;
  

•           case CPUFREQ_GOV_LIMITS:        /* unused */
  

•           case CPUFREQ_GOV_POLICY_INIT:   /* unused */
  

•           case CPUFREQ_GOV_POLICY_EXIT:   /* unused */
  

•                   break;
  

•   }
  

•   return 0;
  

+}

+#ifndef CONFIG_CPU_FREQ_DEFAULT_GOV_CAP_GOV +static +#endif +struct cpufreq_governor cpufreq_gov_cap_gov = {

•   .name                   = "cap_gov",
  

•   .governor               = cap_gov_setup,
  

•   .owner                  = THIS_MODULE,
  

+};

+static int __init cap_gov_init(void) +{

•   return cpufreq_register_governor(&cpufreq_gov_cap_gov);
  

+}

+static void __exit cap_gov_exit(void) +{

•   cpufreq_unregister_governor(&cpufreq_gov_cap_gov);
  

+}

+/* Try to make this the default governor */ +fs_initcall(cap_gov_init);

module_exit(cap_gov_exit) to allow switching governors

+MODULE_LICENSE("GPL");

Fill in MODULE_AUTHOR, MODULE_DESCRIPTION

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index b066a61..2ec2dc7 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -4257,6 +4257,10 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) update_rq_runnable_avg(rq, rq->nr_running); add_nr_running(rq, 1); }

•   if(sched_energy_freq())
  

•           cap_gov_update_cpu(cpu_of(rq));
  

•   hrtick_update(rq);
  

}

@@ -4318,6 +4322,10 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags) sub_nr_running(rq, 1); update_rq_runnable_avg(rq, 1); }

•   if(sched_energy_freq())
  

•           cap_gov_update_cpu(cpu_of(rq));
  

•   hrtick_update(rq);
  

}

@@ -7768,6 +7776,14 @@ static void run_rebalance_domains(struct softirq_action *h) */ nohz_idle_balance(this_rq, idle); rebalance_domains(this_rq, idle);

•   /*
  

•    * FIXME some hardware does not require this, but current CPUfreq
  

•    * locking prevents us from changing cpu frequency with rq locks held
  

•    * and interrupts disabled
  

•    */
  

•   if (sched_energy_freq())
  

•           cap_gov_kick_thread(cpu_of(this_rq));
  

}

/* @@ -7821,6 +7837,9 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) task_tick_numa(rq, curr);

    update_rq_runnable_avg(rq, 1);

•   if(sched_energy_freq())
  

•           cap_gov_update_cpu(cpu_of(rq));
  

}

/* diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index 0fe57ba..c45f1ee 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -1398,6 +1398,14 @@ unsigned long arch_scale_freq_capacity(struct sched_domain *sd, int cpu)

int get_cpu_usage(int cpu);

+#ifdef CONFIG_CPU_FREQ_GOV_CAP_GOV +void cap_gov_update_cpu(int cpu); +void cap_gov_kick_thread(int cpu); +#else +static inline void cap_gov_update_cpu(int cpu) {} +static inline void cap_gov_kick_thread(int cpu) {} +#endif

static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta) { rq->rt_avg += rt_delta * arch_scale_freq_capacity(NULL, cpu_of(rq)); -- 1.9.1

Quoting Amit Kucheria (2015-04-16 00:11:22)

On Thu, Apr 16, 2015 at 10:59 AM, Michael Turquette mturquette@linaro.org wrote:

...

+config CPU_FREQ_GOV_CAP_GOV

Two GOVs are redundant here and make it hard to read. A few name suggestions for your baby:

CPU_FREQ_GOV_SCHED_CAP CPU_FREQ_GOV_SCHED_STATS

I don't want the name to be too generic, since we're only dealing with cfs right now. Perhaps your SCHED_CAP variant or maybe CPU_FREQ_GOV_SCHED_CFS? That leaves room for SCHED_DL and others later on.

...

•   tristate "'capacity governor' cpufreq governor"
  

•   depends on CPU_FREQ
  

•   select CPU_FREQ_GOV_COMMON
  

•   help
  

•     'cap_gov' - this governor scales cpu frequency from the
  

same as above

...

•     scheduler as a function of cpu capacity utilization. It does
  

•     not evaluate utilization on a periodic basis (unlike ondemand)
  

•     but instead is invoked from CFS when updating per-entity load
  

•     tracking statistics.
  

perhaps add something to the effect that it is more responsive than existing governors to really sell it? :)

Good idea. I'll add,

"Response to changes in load is improved over polling governors due to its event-driven design"

...

•     If in doubt, say N.
  

comment "CPU frequency scaling drivers"

config CPUFREQ_DT diff --git a/include/linux/cpufreq.h b/include/linux/cpufreq.h index 7cdf63a..4fc066f 100644 --- a/include/linux/cpufreq.h +++ b/include/linux/cpufreq.h @@ -488,6 +488,9 @@ extern struct cpufreq_governor cpufreq_gov_ondemand; #elif defined(CONFIG_CPU_FREQ_DEFAULT_GOV_CONSERVATIVE) extern struct cpufreq_governor cpufreq_gov_conservative; #define CPUFREQ_DEFAULT_GOVERNOR (&cpufreq_gov_conservative) +#elif defined(CONFIG_CPU_FREQ_DEFAULT_GOV_CAP_GOV) +extern struct cpufreq_governor cpufreq_gov_cap_gov; +#define CPUFREQ_DEFAULT_GOVERNOR (&cpufreq_gov_cap_gov) #endif

/********************************************************************* diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile index 46be870..da601d5 100644 --- a/kernel/sched/Makefile +++ b/kernel/sched/Makefile @@ -19,3 +19,4 @@ obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o obj-$(CONFIG_SCHEDSTATS) += stats.o obj-$(CONFIG_SCHED_DEBUG) += debug.o obj-$(CONFIG_CGROUP_CPUACCT) += cpuacct.o +obj-$(CONFIG_CPU_FREQ_GOV_CAP_GOV) += cap_gov.o diff --git a/kernel/sched/cap_gov.c b/kernel/sched/cap_gov.c new file mode 100644 index 0000000..72873ab --- /dev/null +++ b/kernel/sched/cap_gov.c @@ -0,0 +1,361 @@ +/*

• • Copyright (C) 2014 Michael Turquette mturquette@linaro.org
• • This program is free software; you can redistribute it and/or modify
• • it under the terms of the GNU General Public License version 2 as
• • published by the Free Software Foundation.
• */

+#include <linux/cpufreq.h> +#include <linux/module.h> +#include <linux/kthread.h> +#include <linux/percpu.h>

+#include "sched.h"

+#define UP_THRESHOLD 95

A comment that this probably belong as a sysfs tunable

Doh, this shouldn't be here at all. I don't use any up or down thresholds in this version.

...

+#define THROTTLE_NSEC 50000000 /* 50ms default */

+/*

• • per-cpu pointer to atomic_t gov_data->cap_gov_wake_task

s/cap_gov_wake_task/need_wake_task/

Ack. I might also be able to gid rid of this entirely with the irq_work stuff.

...

• • used in scheduler hot paths {en,de}queueu, task_tick without having to
• • access struct cpufreq_policy and struct gov_data
• */

+static DEFINE_PER_CPU(atomic_t *, cap_gov_wake_task);

+/**

• • gov_data - per-policy data internal to the governor
• • @throttle: time until throttling period expires. Derived from THROTTLE_NSEC

@throttle_nsec ?

Ack.

...

• • @task: worker task for dvfs transition that may block/sleep
• • @need_wake_task: flag the governor to wake this policy's worker thread
• • struct gov_data is the per-policy cap_gov-specific data structure. A
• • per-policy instance of it is created when the cap_gov governor receives
• • the CPUFREQ_GOV_START condition and a pointer to it exists in the gov_data
• • member of struct cpufreq_policy.
• • Readers of this data must call down_read(policy->rwsem). Writers must
• • call down_write(policy->rwsem).
• */

+struct gov_data {

•   ktime_t throttle;
  

•   unsigned int throttle_nsec;
  

•   struct task_struct *task;
  

•   atomic_t need_wake_task;
  

+};

+/**

• • cap_gov_select_freq - pick the next frequency for a cpu
• • @cpu: the cpu whose frequency may be changed
• • cap_gov_select_freq works in a way similar to the ondemand governor. First
• • we inspect the utilization of all of the cpus in this policy to find the
• • most utilized cpu. This is achieved by calling get_cpu_usage, which returns
• • frequency-invarant capacity utilization.
• • This max utilization is compared against the up_threshold (default 95%
• • utilization). If the max cpu utilization is greater than this threshold then
• • we scale the policy up to the max frequency. Othewise we find the lowest
• • frequency (smallest cpu capacity) that is still larger than the max capacity
• • utilization for this policy.
• • Returns frequency selected.
• */

+static unsigned long cap_gov_select_freq(struct cpufreq_policy *policy) +{

•   int cpu = 0;
  

•   struct gov_data *gd;
  

•   int index;
  

•   unsigned long freq = 0, max_usage = 0, cap = 0, usage = 0;
  

•   struct cpufreq_frequency_table *pos;
  

•   if (!policy->gov_data)
  

•           goto out;
  

•   gd = policy->gov_data;
  

•   /*
  

•    * get_cpu_usage is called without locking the runqueues. This is the
  

•    * same behavior used by find_busiest_cpu in load_balance. We are
  

•    * willing to accept occasionally stale data here in exchange for
  

•    * lockless behavior.
  

•    */
  

•   for_each_cpu(cpu, policy->cpus) {
  

•           usage = get_cpu_usage(cpu);
  

•           trace_printk("cpu = %d usage = %lu", cpu, usage);
  

•           if (usage > max_usage)
  

•                   max_usage = usage;
  

•   }
  

•   trace_printk("max_usage = %lu", max_usage);
  

•   /* find the utilization threshold at which we scale up frequency */
  

•   index = cpufreq_frequency_table_get_index(policy, policy->cur);
  

•   /*
  

•    * converge towards max_usage. We want the lowest frequency whose
  

•    * capacity is >= to max_usage. In other words:
  

•    *
  

•    *      find capacity == floor(usage)
  

•    *
  

•    * Sadly cpufreq freq tables are not guaranteed to be ordered by
  

•    * frequency...
  

•    */
  

•   freq = policy->max;
  

•   cpufreq_for_each_entry(pos, policy->freq_table) {
  

•           cap = pos->frequency * SCHED_CAPACITY_SCALE /
  

•                   policy->max;
  

•           if (max_usage < cap && pos->frequency < freq)
  

•                   freq = pos->frequency;
  

•           trace_printk("cpu = %u max_usage = %lu cap = %lu \
  

•                           table_freq = %u freq = %lu",
  

•                           cpumask_first(policy->cpus), max_usage, cap,
  

•                           pos->frequency, freq);
  

•   }
  

+out:

•   trace_printk("cpu %d final freq %lu", cpu, freq);
  

•   return freq;
  

+}

+/*

• • we pass in struct cpufreq_policy. This is safe because changing out the
• • policy requires a call to __cpufreq_governor(policy, CPUFREQ_GOV_STOP),
• • which tears down all of the data structures and __cpufreq_governor(policy,
• • CPUFREQ_GOV_START) will do a full rebuild, including this kthread with the
• • new policy pointer
• */

+static int cap_gov_thread(void *data) +{

•   struct sched_param param;
  

•   struct cpufreq_policy *policy;
  

•   struct gov_data *gd;
  

•   unsigned long freq;
  

•   int ret;
  

•   policy = (struct cpufreq_policy *) data;
  

•   if (!policy) {
  

•           pr_warn("%s: missing policy\n", __func__);
  

•           do_exit(-EINVAL);
  

•   }
  

•   gd = policy->gov_data;
  

•   if (!gd) {
  

•           pr_warn("%s: missing governor data\n", __func__);
  

•           do_exit(-EINVAL);
  

•   }
  

•   param.sched_priority = 0;
  

•   sched_setscheduler(current, SCHED_FIFO, &param);
  

•   set_cpus_allowed_ptr(current, policy->related_cpus);
  

•   /* main loop of the per-policy kthread */
  

•   do {
  

•           down_write(&policy->rwsem);
  

•           if (!atomic_read(&gd->need_wake_task))  {
  

•                   if (kthread_should_stop())
  

•                           break;
  

•                   trace_printk("NOT waking up kthread (%d)", gd->task->pid);
  

•                   up_write(&policy->rwsem);
  

•                   set_current_state(TASK_INTERRUPTIBLE);
  

•                   schedule();
  

•                   continue;
  

•           }
  

•           trace_printk("kthread %d requested freq switch", gd->task->pid);
  

•           freq = cap_gov_select_freq(policy);
  

•           ret = __cpufreq_driver_target(policy, freq,
  

•                           CPUFREQ_RELATION_H);
  

•           if (ret)
  

•                   pr_debug("%s: __cpufreq_driver_target returned %d\n",
  

•                                   __func__, ret);
  

•           trace_printk("kthread %d requested freq switch", gd->task->pid);
  

•           gd->throttle = ktime_add_ns(ktime_get(), gd->throttle_nsec);
  

•           atomic_set(&gd->need_wake_task, 0);
  

•           up_write(&policy->rwsem);
  

•   } while (!kthread_should_stop());
  

•   do_exit(0);
  

+}

+static void cap_gov_wake_up_process(struct task_struct *task) +{

•   /* this is null during early boot */
  

•   if (IS_ERR_OR_NULL(task)) {
  

•           return;
  

•   }
  

•   wake_up_process(task);
  

+}

+void cap_gov_kick_thread(int cpu) +{

•   struct cpufreq_policy *policy;
  

•   struct gov_data *gd = NULL;
  

•   policy = cpufreq_cpu_get(cpu);
  

•   if (IS_ERR_OR_NULL(policy))
  

•           return;
  

•   gd = policy->gov_data;
  

•   if (!gd)
  

•           goto out;
  

•   /* per-cpu access not needed here since we have gd */
  

•   if (atomic_read(&gd->need_wake_task)) {
  

•           trace_printk("waking up kthread (%d)", gd->task->pid);
  

•           cap_gov_wake_up_process(gd->task);
  

•   }
  

+out:

•   cpufreq_cpu_put(policy);
  

+}

+/**

• • cap_gov_update_cpu - interface to scheduler for changing capacity values
• • @cpu: cpu whose capacity utilization has recently changed
• • cap_gov_udpate_cpu is an interface exposed to the scheduler so that the
• • scheduler may inform the governor of updates to capacity utilization and
• • make changes to cpu frequency. Currently this interface is designed around
• • PELT values in CFS. It can be expanded to other scheduling classes in the
• • future if needed.
• • The semantics of this call vary based on the cpu frequency scaling
• • characteristics of the hardware.
• • If kicking off a dvfs transition is an operation that might block or sleep
• • in the cpufreq driver then we set the need_wake_task flag in this function

The comment here isn't obvious since first glance you don't touch need_wake_task. Perhaps clarify it as follows?

we set the need_wake_task (cap_gov_wake_task is a pointer to it)

I can do that. Additionally the kerneldoc description should remove all of the text about hardware that has async/non-blocking dvfs transition. This version of the patch ALWAYS kicks the kthread and the previous "driver_might_sleep" bool has been removed.

Trying to keep the submission as simple and not-over-engineered as possible.

Regards, Mike

Quoting Juri Lelli (2015-04-16 09:46:47)

Hi Mike,

On 16/04/15 06:29, Michael Turquette wrote:

...

Scheduler-driven cpu frequency selection is desirable as part of the on-going effort to make the scheduler better aware of energy consumption. No piece of the Linux kernel has a better view of the factors that affect a cpu frequency selection policy than the scheduler[0], and this patch is an attempt to get that discussion going again.

This patch implements a cpufreq governor, cap_gov, that directly accesses scheduler statistics, in particular the pelt data from cfs via the get_cpu_usage() function.

Put plainly, cap_gov selects the lowest cpu frequency that will prevent a runqueue from being over-utilized (until we hit the highest frequency of course).

cap_gov converts available cpu frequencies into capacity states. When the utilization of a cfs runqueue changes then the policy selects the capacity state which is the floor of the new usage.

Unlike the previous posting from 2014[1] this governor implements no policy of its own (e.g. with tunable thresholds for determining when to scale frequency), but instead implements a "follow the usage" method, where usage is defined as the cpu frequency-invariant product of utilization_load_avg and cpu_capacity_orig.

This governor is event-driven. There is no polling loop to check cpu idle time, or any other method which is unsynchronized with the scheduler. The entry points for this policy are in fair.c: enqueue_task_fair, dequeue_task_fair and task_tick_fair. run_rebalance_domains is used to kick the worker thread to prevent fatally re-entering into scheduler.

This policy is implemented using the cpufreq governor interface for two main reasons:

1. re-using the cpufreq machine drivers without using the governor

interface is hard.

2. using the cpufreq interface allows us to switch between the

scheduler-driven policy and legacy cpufreq governors such as ondemand at run-time. This is very useful for comparative testing and tuning.

Finally, it is worth mentioning that this approach neglects all scheduling classes except for cfs. It is possible to add support for deadline and other other classes here, but I also wonder if a multi-governor approach would be a more maintainable solution, where the cpufreq core aggregates the constraints set by multiple governors. Supporting such an approach in the cpufreq core would also allow for peripheral devices to place constraint on cpu frequency without having to hack such behavior in at the governor level.

Thanks to Juri Lelli juri.lelli@arm.com for doing a good bit of testing, bug fixing and contributing towards the design.

[0] http://article.gmane.org/gmane.linux.kernel/1499836 [1] https://lkml.org/lkml/2014/10/22/22

Signed-off-by: Michael Turquette mturquette@linaro.org

drivers/cpufreq/Kconfig | 22 +++ include/linux/cpufreq.h | 3 + kernel/sched/Makefile | 1 + kernel/sched/cap_gov.c | 361 ++++++++++++++++++++++++++++++++++++++++++++++++ kernel/sched/fair.c | 19 +++ kernel/sched/sched.h | 8 ++ 6 files changed, 414 insertions(+) create mode 100644 kernel/sched/cap_gov.c

diff --git a/drivers/cpufreq/Kconfig b/drivers/cpufreq/Kconfig index a171fef..654d70a 100644 --- a/drivers/cpufreq/Kconfig +++ b/drivers/cpufreq/Kconfig @@ -102,6 +102,15 @@ config CPU_FREQ_DEFAULT_GOV_CONSERVATIVE Be aware that not all cpufreq drivers support the conservative governor. If unsure have a look at the help section of the driver. Fallback governor will be the performance governor.

+config CPU_FREQ_DEFAULT_GOV_CAP_GOV

•   bool "cap_gov"
  

•   select CPU_FREQ_GOV_CAP_GOV
  

•   select CPU_FREQ_GOV_PERFORMANCE
  

•   help
  

•     Use the CPUfreq governor 'cap_gov' as default. This scales cpu
  

•     frequency from the scheduler as per-entity load tracking
  

•     statistics are updated.
  

endchoice

config CPU_FREQ_GOV_PERFORMANCE @@ -183,6 +192,19 @@ config CPU_FREQ_GOV_CONSERVATIVE

      If in doubt, say N.

+config CPU_FREQ_GOV_CAP_GOV

•   tristate "'capacity governor' cpufreq governor"
  

•   depends on CPU_FREQ
  

•   select CPU_FREQ_GOV_COMMON
  

•   help
  

•     'cap_gov' - this governor scales cpu frequency from the
  

•     scheduler as a function of cpu capacity utilization. It does
  

•     not evaluate utilization on a periodic basis (unlike ondemand)
  

•     but instead is invoked from CFS when updating per-entity load
  

•     tracking statistics.
  

•     If in doubt, say N.
  

comment "CPU frequency scaling drivers"

config CPUFREQ_DT diff --git a/include/linux/cpufreq.h b/include/linux/cpufreq.h index 7cdf63a..4fc066f 100644 --- a/include/linux/cpufreq.h +++ b/include/linux/cpufreq.h @@ -488,6 +488,9 @@ extern struct cpufreq_governor cpufreq_gov_ondemand; #elif defined(CONFIG_CPU_FREQ_DEFAULT_GOV_CONSERVATIVE) extern struct cpufreq_governor cpufreq_gov_conservative; #define CPUFREQ_DEFAULT_GOVERNOR (&cpufreq_gov_conservative) +#elif defined(CONFIG_CPU_FREQ_DEFAULT_GOV_CAP_GOV) +extern struct cpufreq_governor cpufreq_gov_cap_gov; +#define CPUFREQ_DEFAULT_GOVERNOR (&cpufreq_gov_cap_gov) #endif

/********************************************************************* diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile index 46be870..da601d5 100644 --- a/kernel/sched/Makefile +++ b/kernel/sched/Makefile @@ -19,3 +19,4 @@ obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o obj-$(CONFIG_SCHEDSTATS) += stats.o obj-$(CONFIG_SCHED_DEBUG) += debug.o obj-$(CONFIG_CGROUP_CPUACCT) += cpuacct.o +obj-$(CONFIG_CPU_FREQ_GOV_CAP_GOV) += cap_gov.o diff --git a/kernel/sched/cap_gov.c b/kernel/sched/cap_gov.c new file mode 100644 index 0000000..72873ab --- /dev/null +++ b/kernel/sched/cap_gov.c @@ -0,0 +1,361 @@ +/*

• • Copyright (C) 2014 Michael Turquette mturquette@linaro.org
• • This program is free software; you can redistribute it and/or modify
• • it under the terms of the GNU General Public License version 2 as
• • published by the Free Software Foundation.
• */

+#include <linux/cpufreq.h> +#include <linux/module.h> +#include <linux/kthread.h> +#include <linux/percpu.h>

+#include "sched.h"

+#define UP_THRESHOLD 95

Is this a leftover? In the changelog you say that you moved away from thresholds. Anyway, since we scale utilization by freq, I'm not sure we can live without some sort of up_threshold. The problem is that if you are running a task flat out on a CPU at a certain freq, let's say the lower one, you'll always get a usage for that CPU that corresponds to the current capacity of that CPU at that freq. As you use the usage signal to decide when to ramp up, you will never ramp up in this situation because the signal won't cross the capacity at the lower frequency.

We could solve this problem by putting the up threshold back. As soon as you cross it you go to max, and then adapt, choosing the right capacity for the actual, non capped, utilization of the task.

...

+#define THROTTLE_NSEC 50000000 /* 50ms default */

+/*

• • per-cpu pointer to atomic_t gov_data->cap_gov_wake_task
• • used in scheduler hot paths {en,de}queueu, task_tick without having to
• • access struct cpufreq_policy and struct gov_data
• */

+static DEFINE_PER_CPU(atomic_t *, cap_gov_wake_task);

+/**

• • gov_data - per-policy data internal to the governor
• • @throttle: time until throttling period expires. Derived from THROTTLE_NSEC
• • @task: worker task for dvfs transition that may block/sleep
• • @need_wake_task: flag the governor to wake this policy's worker thread
• • struct gov_data is the per-policy cap_gov-specific data structure. A
• • per-policy instance of it is created when the cap_gov governor receives
• • the CPUFREQ_GOV_START condition and a pointer to it exists in the gov_data
• • member of struct cpufreq_policy.
• • Readers of this data must call down_read(policy->rwsem). Writers must
• • call down_write(policy->rwsem).
• */

+struct gov_data {

•   ktime_t throttle;
  

•   unsigned int throttle_nsec;
  

•   struct task_struct *task;
  

•   atomic_t need_wake_task;
  

+};

+/**

• • cap_gov_select_freq - pick the next frequency for a cpu
• • @cpu: the cpu whose frequency may be changed
• • cap_gov_select_freq works in a way similar to the ondemand governor. First
• • we inspect the utilization of all of the cpus in this policy to find the
• • most utilized cpu. This is achieved by calling get_cpu_usage, which returns
• • frequency-invarant capacity utilization.
• • This max utilization is compared against the up_threshold (default 95%
• • utilization). If the max cpu utilization is greater than this threshold then
• • we scale the policy up to the max frequency. Othewise we find the lowest
• • frequency (smallest cpu capacity) that is still larger than the max capacity
• • utilization for this policy.
• • Returns frequency selected.
• */

+static unsigned long cap_gov_select_freq(struct cpufreq_policy *policy) +{

•   int cpu = 0;
  

•   struct gov_data *gd;
  

•   int index;
  

•   unsigned long freq = 0, max_usage = 0, cap = 0, usage = 0;
  

•   struct cpufreq_frequency_table *pos;
  

•   if (!policy->gov_data)
  

•           goto out;
  

•   gd = policy->gov_data;
  

•   /*
  

•    * get_cpu_usage is called without locking the runqueues. This is the
  

•    * same behavior used by find_busiest_cpu in load_balance. We are
  

•    * willing to accept occasionally stale data here in exchange for
  

•    * lockless behavior.
  

•    */
  

•   for_each_cpu(cpu, policy->cpus) {
  

•           usage = get_cpu_usage(cpu);
  

•           trace_printk("cpu = %d usage = %lu", cpu, usage);
  

Here and below, do you want to post the patches with trace_printks?

Good catch. Will remove.

Proper tracepoint support can show up in a later patch.

...

•           if (usage > max_usage)
  

•                   max_usage = usage;
  

•   }
  

•   trace_printk("max_usage = %lu", max_usage);
  

•   /* find the utilization threshold at which we scale up frequency */
  

•   index = cpufreq_frequency_table_get_index(policy, policy->cur);
  

•   /*
  

•    * converge towards max_usage. We want the lowest frequency whose
  

•    * capacity is >= to max_usage. In other words:
  

•    *
  

•    *      find capacity == floor(usage)
  

•    *
  

•    * Sadly cpufreq freq tables are not guaranteed to be ordered by
  

•    * frequency...
  

•    */
  

•   freq = policy->max;
  

•   cpufreq_for_each_entry(pos, policy->freq_table) {
  

•           cap = pos->frequency * SCHED_CAPACITY_SCALE /
  

•                   policy->max;
  

•           if (max_usage < cap && pos->frequency < freq)
  

•                   freq = pos->frequency;
  

•           trace_printk("cpu = %u max_usage = %lu cap = %lu \
  

•                           table_freq = %u freq = %lu",
  

•                           cpumask_first(policy->cpus), max_usage, cap,
  

•                           pos->frequency, freq);
  

•   }
  

+out:

•   trace_printk("cpu %d final freq %lu", cpu, freq);
  

•   return freq;
  

+}

+/*

• • we pass in struct cpufreq_policy. This is safe because changing out the
• • policy requires a call to __cpufreq_governor(policy, CPUFREQ_GOV_STOP),
• • which tears down all of the data structures and __cpufreq_governor(policy,
• • CPUFREQ_GOV_START) will do a full rebuild, including this kthread with the
• • new policy pointer
• */

+static int cap_gov_thread(void *data) +{

•   struct sched_param param;
  

•   struct cpufreq_policy *policy;
  

•   struct gov_data *gd;
  

•   unsigned long freq;
  

•   int ret;
  

•   policy = (struct cpufreq_policy *) data;
  

•   if (!policy) {
  

•           pr_warn("%s: missing policy\n", __func__);
  

•           do_exit(-EINVAL);
  

•   }
  

•   gd = policy->gov_data;
  

•   if (!gd) {
  

•           pr_warn("%s: missing governor data\n", __func__);
  

•           do_exit(-EINVAL);
  

•   }
  

•   param.sched_priority = 0;
  

•   sched_setscheduler(current, SCHED_FIFO, &param);
  

•   set_cpus_allowed_ptr(current, policy->related_cpus);
  

We should check return values of these functions, use the in-kernel version of setscheduler and set a true RT prio for kthreads, something like:

•   param.sched_priority = 0;
  

•   sched_setscheduler(current, SCHED_FIFO, &param);
  

•   set_cpus_allowed_ptr(current, policy->related_cpus);
  

•   param.sched_priority = 50;
  

•   ret = sched_setscheduler_nocheck(gd->task, SCHED_FIFO, &param);
  

•   if (ret) {
  

•           pr_warn("%s: failed to set SCHED_FIFO\n", __func__);
  

•           do_exit(-EINVAL);
  

•   } else {
  

•           pr_debug("%s: kthread (%d) set to SCHED_FIFO\n",
  

•                    __func__, gd->task->pid);
  

•   }
  

•   ret = set_cpus_allowed_ptr(gd->task, policy->related_cpus);
  

•   if (ret) {
  

•           pr_warn("%s: failed to set allowed ptr\n", __func__);
  

•           do_exit(-EINVAL);
  

•   }
  

Yes, I had rolled in your code to do this in a previous version. I'll bring it back in.

...

•   /* main loop of the per-policy kthread */
  

•   do {
  

•           down_write(&policy->rwsem);
  

•           if (!atomic_read(&gd->need_wake_task))  {
  

•                   if (kthread_should_stop())
  

•                           break;
  

•                   trace_printk("NOT waking up kthread (%d)", gd->task->pid);
  

•                   up_write(&policy->rwsem);
  

•                   set_current_state(TASK_INTERRUPTIBLE);
  

•                   schedule();
  

•                   continue;
  

•           }
  

•           trace_printk("kthread %d requested freq switch", gd->task->pid);
  

•           freq = cap_gov_select_freq(policy);
  

•           ret = __cpufreq_driver_target(policy, freq,
  

•                           CPUFREQ_RELATION_H);
  

•           if (ret)
  

•                   pr_debug("%s: __cpufreq_driver_target returned %d\n",
  

•                                   __func__, ret);
  

•           trace_printk("kthread %d requested freq switch", gd->task->pid);
  

•           gd->throttle = ktime_add_ns(ktime_get(), gd->throttle_nsec);
  

•           atomic_set(&gd->need_wake_task, 0);
  

•           up_write(&policy->rwsem);
  

•   } while (!kthread_should_stop());
  

•   do_exit(0);
  

+}

+static void cap_gov_wake_up_process(struct task_struct *task) +{

•   /* this is null during early boot */
  

•   if (IS_ERR_OR_NULL(task)) {
  

•           return;
  

•   }
  

•   wake_up_process(task);
  

+}

+void cap_gov_kick_thread(int cpu) +{

•   struct cpufreq_policy *policy;
  

•   struct gov_data *gd = NULL;
  

•   policy = cpufreq_cpu_get(cpu);
  

•   if (IS_ERR_OR_NULL(policy))
  

•           return;
  

•   gd = policy->gov_data;
  

•   if (!gd)
  

•           goto out;
  

•   /* per-cpu access not needed here since we have gd */
  

•   if (atomic_read(&gd->need_wake_task)) {
  

•           trace_printk("waking up kthread (%d)", gd->task->pid);
  

•           cap_gov_wake_up_process(gd->task);
  

•   }
  

+out:

•   cpufreq_cpu_put(policy);
  

+}

+/**

• • cap_gov_update_cpu - interface to scheduler for changing capacity values
• • @cpu: cpu whose capacity utilization has recently changed
• • cap_gov_udpate_cpu is an interface exposed to the scheduler so that the
• • scheduler may inform the governor of updates to capacity utilization and
• • make changes to cpu frequency. Currently this interface is designed around
• • PELT values in CFS. It can be expanded to other scheduling classes in the
• • future if needed.
• • The semantics of this call vary based on the cpu frequency scaling
• • characteristics of the hardware.
• • If kicking off a dvfs transition is an operation that might block or sleep
• • in the cpufreq driver then we set the need_wake_task flag in this function
• • and return. Selecting a frequency and programming it is done in a dedicated
• • kernel thread which will be woken up from rebalance_domains. See
• • cap_gov_kick_thread above.
• • If kicking off a dvfs transition is an operation that returns quickly in the
• • cpufreq driver and will never sleep then we select the frequency in this
• • function and program the hardware for it in the scheduler hot path. No
• • dedicated kthread is needed.

This is not something that we already have, right? This is of course fine, but IMHO we have to highlight this "problem" a bit more. Also, clearly state that code for that case is not part of this patchset.

As I stated in reply to Amit, I'm thinking of removing some of the above text since I removed support for "driver_might_sleep".

I want to keep the patch set as simple as possible, and regardless of whether or not we have async dvfs hardware it is still not possible to call __cpufreq_driver_target from within the schedule() context, so for not it is a moot point.

Regards, Mike

Thanks,

• Juri

...

• */

+void cap_gov_update_cpu(int cpu) +{

•   struct cpufreq_policy *policy;
  

•   struct gov_data *gd;
  

•   /* XXX put policy pointer in per-cpu data? */
  

•   policy = cpufreq_cpu_get(cpu);
  

•   if (IS_ERR_OR_NULL(policy)) {
  

•           return;
  

•   }
  

•   if (!policy->gov_data) {
  

•           trace_printk("missing governor data");
  

•           goto out;
  

•   }
  

•   gd = policy->gov_data;
  

•   /* bail early if we are throttled */
  

•   if (ktime_before(ktime_get(), gd->throttle)) {
  

•           trace_printk("THROTTLED");
  

•           goto out;
  

•   }
  

•   atomic_set(per_cpu(cap_gov_wake_task, cpu), 1);
  

+out:

•   cpufreq_cpu_put(policy);
  

•   return;
  

+}

+static void cap_gov_start(struct cpufreq_policy *policy) +{

•   int cpu;
  

•   struct gov_data *gd;
  

•   /* prepare per-policy private data */
  

•   gd = kzalloc(sizeof(*gd), GFP_KERNEL);
  

•   if (!gd) {
  

•           pr_debug("%s: failed to allocate private data\n", __func__);
  

•           return;
  

•   }
  

•   /*
  

•    * Don't ask for freq changes at an higher rate than what
  

•    * the driver advertises as transition latency.
  

•    */
  

•   gd->throttle_nsec = policy->cpuinfo.transition_latency ?
  

•                       policy->cpuinfo.transition_latency :
  

•                       THROTTLE_NSEC;
  

•   pr_debug("%s: throttle threshold = %u [ns]\n",
  

•             __func__, gd->throttle_nsec);
  

•   /* save per-cpu pointer to per-policy need_wake_task */
  

•   for_each_cpu(cpu, policy->related_cpus)
  

•           per_cpu(cap_gov_wake_task, cpu) = &gd->need_wake_task;
  

•   /* init per-policy kthread */
  

•   gd->task = kthread_create(cap_gov_thread, policy, "kcap_gov_task");
  

•   if (IS_ERR_OR_NULL(gd->task))
  

•           pr_err("%s: failed to create kcap_gov_task thread\n", __func__);
  

•   policy->gov_data = gd;
  

+}

+static void cap_gov_stop(struct cpufreq_policy *policy) +{

•   struct gov_data *gd;
  

•   gd = policy->gov_data;
  

•   policy->gov_data = NULL;
  

•   kthread_stop(gd->task);
  

•   /* FIXME replace with devm counterparts? */
  

•   kfree(gd);
  

+}

+static int cap_gov_setup(struct cpufreq_policy *policy, unsigned int event) +{

•   switch (event) {
  

•           case CPUFREQ_GOV_START:
  

•                   /* Start managing the frequency */
  

•                   cap_gov_start(policy);
  

•                   return 0;
  

•           case CPUFREQ_GOV_STOP:
  

•                   cap_gov_stop(policy);
  

•                   return 0;
  

•           case CPUFREQ_GOV_LIMITS:        /* unused */
  

•           case CPUFREQ_GOV_POLICY_INIT:   /* unused */
  

•           case CPUFREQ_GOV_POLICY_EXIT:   /* unused */
  

•                   break;
  

•   }
  

•   return 0;
  

+}

+#ifndef CONFIG_CPU_FREQ_DEFAULT_GOV_CAP_GOV +static +#endif +struct cpufreq_governor cpufreq_gov_cap_gov = {

•   .name                   = "cap_gov",
  

•   .governor               = cap_gov_setup,
  

•   .owner                  = THIS_MODULE,
  

+};

+static int __init cap_gov_init(void) +{

•   return cpufreq_register_governor(&cpufreq_gov_cap_gov);
  

+}

+static void __exit cap_gov_exit(void) +{

•   cpufreq_unregister_governor(&cpufreq_gov_cap_gov);
  

+}

+/* Try to make this the default governor */ +fs_initcall(cap_gov_init);

+MODULE_LICENSE("GPL"); diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index b066a61..2ec2dc7 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -4257,6 +4257,10 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) update_rq_runnable_avg(rq, rq->nr_running); add_nr_running(rq, 1); }

•   if(sched_energy_freq())
  

•           cap_gov_update_cpu(cpu_of(rq));
  

•   hrtick_update(rq);
  

}

@@ -4318,6 +4322,10 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags) sub_nr_running(rq, 1); update_rq_runnable_avg(rq, 1); }

•   if(sched_energy_freq())
  

•           cap_gov_update_cpu(cpu_of(rq));
  

•   hrtick_update(rq);
  

}

@@ -7768,6 +7776,14 @@ static void run_rebalance_domains(struct softirq_action *h) */ nohz_idle_balance(this_rq, idle); rebalance_domains(this_rq, idle);

•   /*
  

•    * FIXME some hardware does not require this, but current CPUfreq
  

•    * locking prevents us from changing cpu frequency with rq locks held
  

•    * and interrupts disabled
  

•    */
  

•   if (sched_energy_freq())
  

•           cap_gov_kick_thread(cpu_of(this_rq));
  

}

/* @@ -7821,6 +7837,9 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) task_tick_numa(rq, curr);

    update_rq_runnable_avg(rq, 1);

•   if(sched_energy_freq())
  

•           cap_gov_update_cpu(cpu_of(rq));
  

}

/* diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index 0fe57ba..c45f1ee 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -1398,6 +1398,14 @@ unsigned long arch_scale_freq_capacity(struct sched_domain *sd, int cpu)

int get_cpu_usage(int cpu);

+#ifdef CONFIG_CPU_FREQ_GOV_CAP_GOV +void cap_gov_update_cpu(int cpu); +void cap_gov_kick_thread(int cpu); +#else +static inline void cap_gov_update_cpu(int cpu) {} +static inline void cap_gov_kick_thread(int cpu) {} +#endif

static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta) { rq->rt_avg += rt_delta * arch_scale_freq_capacity(NULL, cpu_of(rq)); -- 1.9.1

On 16 April 2015 at 07:29, Michael Turquette mturquette@linaro.org wrote:

Scheduler-driven cpu frequency selection is desirable as part of the on-going effort to make the scheduler better aware of energy consumption. No piece of the Linux kernel has a better view of the factors that affect a cpu frequency selection policy than the scheduler[0], and this patch is an attempt to get that discussion going again.

This patch implements a cpufreq governor, cap_gov, that directly accesses scheduler statistics, in particular the pelt data from cfs via the get_cpu_usage() function.

Put plainly, cap_gov selects the lowest cpu frequency that will prevent a runqueue from being over-utilized (until we hit the highest frequency of course).

cap_gov converts available cpu frequencies into capacity states. When the utilization of a cfs runqueue changes then the policy selects the capacity state which is the floor of the new usage.

Unlike the previous posting from 2014[1] this governor implements no policy of its own (e.g. with tunable thresholds for determining when to scale frequency), but instead implements a "follow the usage" method, where usage is defined as the cpu frequency-invariant product of utilization_load_avg and cpu_capacity_orig.

This governor is event-driven. There is no polling loop to check cpu idle time, or any other method which is unsynchronized with the scheduler. The entry points for this policy are in fair.c: enqueue_task_fair, dequeue_task_fair and task_tick_fair. run_rebalance_domains is used to kick the worker thread to prevent fatally re-entering into scheduler.

This policy is implemented using the cpufreq governor interface for two main reasons:

1. re-using the cpufreq machine drivers without using the governor

interface is hard.

2. using the cpufreq interface allows us to switch between the

scheduler-driven policy and legacy cpufreq governors such as ondemand at run-time. This is very useful for comparative testing and tuning.

Finally, it is worth mentioning that this approach neglects all scheduling classes except for cfs. It is possible to add support for deadline and other other classes here, but I also wonder if a multi-governor approach would be a more maintainable solution, where the cpufreq core aggregates the constraints set by multiple governors. Supporting such an approach in the cpufreq core would also allow for peripheral devices to place constraint on cpu frequency without having to hack such behavior in at the governor level.

Thanks to Juri Lelli juri.lelli@arm.com for doing a good bit of testing, bug fixing and contributing towards the design.

[0] http://article.gmane.org/gmane.linux.kernel/1499836 [1] https://lkml.org/lkml/2014/10/22/22

Signed-off-by: Michael Turquette mturquette@linaro.org

drivers/cpufreq/Kconfig | 22 +++ include/linux/cpufreq.h | 3 + kernel/sched/Makefile | 1 + kernel/sched/cap_gov.c | 361 ++++++++++++++++++++++++++++++++++++++++++++++++ kernel/sched/fair.c | 19 +++ kernel/sched/sched.h | 8 ++ 6 files changed, 414 insertions(+) create mode 100644 kernel/sched/cap_gov.c

diff --git a/drivers/cpufreq/Kconfig b/drivers/cpufreq/Kconfig index a171fef..654d70a 100644 --- a/drivers/cpufreq/Kconfig +++ b/drivers/cpufreq/Kconfig @@ -102,6 +102,15 @@ config CPU_FREQ_DEFAULT_GOV_CONSERVATIVE Be aware that not all cpufreq drivers support the conservative governor. If unsure have a look at the help section of the driver. Fallback governor will be the performance governor.

+config CPU_FREQ_DEFAULT_GOV_CAP_GOV

•   bool "cap_gov"
  

•   select CPU_FREQ_GOV_CAP_GOV
  

•   select CPU_FREQ_GOV_PERFORMANCE
  

•   help
  

•     Use the CPUfreq governor 'cap_gov' as default. This scales cpu
  

•     frequency from the scheduler as per-entity load tracking
  

•     statistics are updated.
  

endchoice

config CPU_FREQ_GOV_PERFORMANCE @@ -183,6 +192,19 @@ config CPU_FREQ_GOV_CONSERVATIVE

      If in doubt, say N.

+config CPU_FREQ_GOV_CAP_GOV

•   tristate "'capacity governor' cpufreq governor"
  

•   depends on CPU_FREQ
  

•   select CPU_FREQ_GOV_COMMON
  

•   help
  

•     'cap_gov' - this governor scales cpu frequency from the
  

•     scheduler as a function of cpu capacity utilization. It does
  

•     not evaluate utilization on a periodic basis (unlike ondemand)
  

•     but instead is invoked from CFS when updating per-entity load
  

•     tracking statistics.
  

•     If in doubt, say N.
  

comment "CPU frequency scaling drivers"

config CPUFREQ_DT diff --git a/include/linux/cpufreq.h b/include/linux/cpufreq.h index 7cdf63a..4fc066f 100644 --- a/include/linux/cpufreq.h +++ b/include/linux/cpufreq.h @@ -488,6 +488,9 @@ extern struct cpufreq_governor cpufreq_gov_ondemand; #elif defined(CONFIG_CPU_FREQ_DEFAULT_GOV_CONSERVATIVE) extern struct cpufreq_governor cpufreq_gov_conservative; #define CPUFREQ_DEFAULT_GOVERNOR (&cpufreq_gov_conservative) +#elif defined(CONFIG_CPU_FREQ_DEFAULT_GOV_CAP_GOV) +extern struct cpufreq_governor cpufreq_gov_cap_gov; +#define CPUFREQ_DEFAULT_GOVERNOR (&cpufreq_gov_cap_gov) #endif

/********************************************************************* diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile index 46be870..da601d5 100644 --- a/kernel/sched/Makefile +++ b/kernel/sched/Makefile @@ -19,3 +19,4 @@ obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o obj-$(CONFIG_SCHEDSTATS) += stats.o obj-$(CONFIG_SCHED_DEBUG) += debug.o obj-$(CONFIG_CGROUP_CPUACCT) += cpuacct.o +obj-$(CONFIG_CPU_FREQ_GOV_CAP_GOV) += cap_gov.o diff --git a/kernel/sched/cap_gov.c b/kernel/sched/cap_gov.c new file mode 100644 index 0000000..72873ab --- /dev/null +++ b/kernel/sched/cap_gov.c @@ -0,0 +1,361 @@ +/*

• • Copyright (C) 2014 Michael Turquette mturquette@linaro.org
• • This program is free software; you can redistribute it and/or modify
• • it under the terms of the GNU General Public License version 2 as
• • published by the Free Software Foundation.
• */

+#include <linux/cpufreq.h> +#include <linux/module.h> +#include <linux/kthread.h> +#include <linux/percpu.h>

+#include "sched.h"

+#define UP_THRESHOLD 95 +#define THROTTLE_NSEC 50000000 /* 50ms default */

+/*

• • per-cpu pointer to atomic_t gov_data->cap_gov_wake_task
• • used in scheduler hot paths {en,de}queueu, task_tick without having to
• • access struct cpufreq_policy and struct gov_data
• */

+static DEFINE_PER_CPU(atomic_t *, cap_gov_wake_task);

+/**

• • gov_data - per-policy data internal to the governor
• • @throttle: time until throttling period expires. Derived from THROTTLE_NSEC
• • @task: worker task for dvfs transition that may block/sleep
• • @need_wake_task: flag the governor to wake this policy's worker thread
• • struct gov_data is the per-policy cap_gov-specific data structure. A
• • per-policy instance of it is created when the cap_gov governor receives
• • the CPUFREQ_GOV_START condition and a pointer to it exists in the gov_data
• • member of struct cpufreq_policy.
• • Readers of this data must call down_read(policy->rwsem). Writers must
• • call down_write(policy->rwsem).
• */

+struct gov_data {

•   ktime_t throttle;
  

•   unsigned int throttle_nsec;
  

•   struct task_struct *task;
  

•   atomic_t need_wake_task;
  

+};

+/**

• • cap_gov_select_freq - pick the next frequency for a cpu
• • @cpu: the cpu whose frequency may be changed
• • cap_gov_select_freq works in a way similar to the ondemand governor. First
• • we inspect the utilization of all of the cpus in this policy to find the
• • most utilized cpu. This is achieved by calling get_cpu_usage, which returns
• • frequency-invarant capacity utilization.
• • This max utilization is compared against the up_threshold (default 95%
• • utilization). If the max cpu utilization is greater than this threshold then
• • we scale the policy up to the max frequency. Othewise we find the lowest
• • frequency (smallest cpu capacity) that is still larger than the max capacity
• • utilization for this policy.
• • Returns frequency selected.
• */

+static unsigned long cap_gov_select_freq(struct cpufreq_policy *policy) +{

•   int cpu = 0;
  

•   struct gov_data *gd;
  

•   int index;
  

•   unsigned long freq = 0, max_usage = 0, cap = 0, usage = 0;
  

•   struct cpufreq_frequency_table *pos;
  

•   if (!policy->gov_data)
  

•           goto out;
  

•   gd = policy->gov_data;
  

•   /*
  

•    * get_cpu_usage is called without locking the runqueues. This is the
  

•    * same behavior used by find_busiest_cpu in load_balance. We are
  

•    * willing to accept occasionally stale data here in exchange for
  

•    * lockless behavior.
  

•    */
  

•   for_each_cpu(cpu, policy->cpus) {
  

•           usage = get_cpu_usage(cpu);
  

•           trace_printk("cpu = %d usage = %lu", cpu, usage);
  

•           if (usage > max_usage)
  

•                   max_usage = usage;
  

•   }
  

•   trace_printk("max_usage = %lu", max_usage);
  

•   /* find the utilization threshold at which we scale up frequency */
  

•   index = cpufreq_frequency_table_get_index(policy, policy->cur);
  

•   /*
  

•    * converge towards max_usage. We want the lowest frequency whose
  

•    * capacity is >= to max_usage. In other words:
  

•    *
  

•    *      find capacity == floor(usage)
  

•    *
  

•    * Sadly cpufreq freq tables are not guaranteed to be ordered by
  

•    * frequency...
  

•    */
  

•   freq = policy->max;
  

•   cpufreq_for_each_entry(pos, policy->freq_table) {
  

•           cap = pos->frequency * SCHED_CAPACITY_SCALE /
  

•                   policy->max;
  

•           if (max_usage < cap && pos->frequency < freq)
  

•                   freq = pos->frequency;
  

•           trace_printk("cpu = %u max_usage = %lu cap = %lu \
  

•                           table_freq = %u freq = %lu",
  

•                           cpumask_first(policy->cpus), max_usage, cap,
  

•                           pos->frequency, freq);
  

•   }
  

+out:

•   trace_printk("cpu %d final freq %lu", cpu, freq);
  

•   return freq;
  

+}

+/*

• • we pass in struct cpufreq_policy. This is safe because changing out the
• • policy requires a call to __cpufreq_governor(policy, CPUFREQ_GOV_STOP),
• • which tears down all of the data structures and __cpufreq_governor(policy,
• • CPUFREQ_GOV_START) will do a full rebuild, including this kthread with the
• • new policy pointer
• */

+static int cap_gov_thread(void *data) +{

•   struct sched_param param;
  

•   struct cpufreq_policy *policy;
  

•   struct gov_data *gd;
  

•   unsigned long freq;
  

•   int ret;
  

•   policy = (struct cpufreq_policy *) data;
  

•   if (!policy) {
  

•           pr_warn("%s: missing policy\n", __func__);
  

•           do_exit(-EINVAL);
  

•   }
  

•   gd = policy->gov_data;
  

•   if (!gd) {
  

•           pr_warn("%s: missing governor data\n", __func__);
  

•           do_exit(-EINVAL);
  

•   }
  

•   param.sched_priority = 0;
  

•   sched_setscheduler(current, SCHED_FIFO, &param);
  

•   set_cpus_allowed_ptr(current, policy->related_cpus);
  

•   /* main loop of the per-policy kthread */
  

•   do {
  

•           down_write(&policy->rwsem);
  

•           if (!atomic_read(&gd->need_wake_task))  {
  

•                   if (kthread_should_stop())
  

•                           break;
  

•                   trace_printk("NOT waking up kthread (%d)", gd->task->pid);
  

•                   up_write(&policy->rwsem);
  

•                   set_current_state(TASK_INTERRUPTIBLE);
  

•                   schedule();
  

•                   continue;
  

•           }
  

•           trace_printk("kthread %d requested freq switch", gd->task->pid);
  

•           freq = cap_gov_select_freq(policy);
  

•           ret = __cpufreq_driver_target(policy, freq,
  

•                           CPUFREQ_RELATION_H);
  

•           if (ret)
  

•                   pr_debug("%s: __cpufreq_driver_target returned %d\n",
  

•                                   __func__, ret);
  

•           trace_printk("kthread %d requested freq switch", gd->task->pid);
  

•           gd->throttle = ktime_add_ns(ktime_get(), gd->throttle_nsec);
  

•           atomic_set(&gd->need_wake_task, 0);
  

•           up_write(&policy->rwsem);
  

•   } while (!kthread_should_stop());
  

•   do_exit(0);
  

+}

+static void cap_gov_wake_up_process(struct task_struct *task) +{

•   /* this is null during early boot */
  

•   if (IS_ERR_OR_NULL(task)) {
  

•           return;
  

•   }
  

•   wake_up_process(task);
  

+}

+void cap_gov_kick_thread(int cpu) +{

•   struct cpufreq_policy *policy;
  

•   struct gov_data *gd = NULL;
  

•   policy = cpufreq_cpu_get(cpu);
  

•   if (IS_ERR_OR_NULL(policy))
  

•           return;
  

•   gd = policy->gov_data;
  

•   if (!gd)
  

•           goto out;
  

•   /* per-cpu access not needed here since we have gd */
  

•   if (atomic_read(&gd->need_wake_task)) {
  

•           trace_printk("waking up kthread (%d)", gd->task->pid);
  

•           cap_gov_wake_up_process(gd->task);
  

•   }
  

+out:

•   cpufreq_cpu_put(policy);
  

+}

+/**

• • cap_gov_update_cpu - interface to scheduler for changing capacity values
• • @cpu: cpu whose capacity utilization has recently changed
• • cap_gov_udpate_cpu is an interface exposed to the scheduler so that the
• • scheduler may inform the governor of updates to capacity utilization and
• • make changes to cpu frequency. Currently this interface is designed around
• • PELT values in CFS. It can be expanded to other scheduling classes in the
• • future if needed.
• • The semantics of this call vary based on the cpu frequency scaling
• • characteristics of the hardware.
• • If kicking off a dvfs transition is an operation that might block or sleep
• • in the cpufreq driver then we set the need_wake_task flag in this function
• • and return. Selecting a frequency and programming it is done in a dedicated
• • kernel thread which will be woken up from rebalance_domains. See
• • cap_gov_kick_thread above.
• • If kicking off a dvfs transition is an operation that returns quickly in the
• • cpufreq driver and will never sleep then we select the frequency in this
• • function and program the hardware for it in the scheduler hot path. No
• • dedicated kthread is needed.
• */

+void cap_gov_update_cpu(int cpu) +{

•   struct cpufreq_policy *policy;
  

•   struct gov_data *gd;
  

•   /* XXX put policy pointer in per-cpu data? */
  

•   policy = cpufreq_cpu_get(cpu);
  

•   if (IS_ERR_OR_NULL(policy)) {
  

•           return;
  

•   }
  

•   if (!policy->gov_data) {
  

•           trace_printk("missing governor data");
  

•           goto out;
  

•   }
  

•   gd = policy->gov_data;
  

•   /* bail early if we are throttled */
  

•   if (ktime_before(ktime_get(), gd->throttle)) {
  

•           trace_printk("THROTTLED");
  

•           goto out;
  

•   }
  

•   atomic_set(per_cpu(cap_gov_wake_task, cpu), 1);
  

+out:

•   cpufreq_cpu_put(policy);
  

•   return;
  

+}

+static void cap_gov_start(struct cpufreq_policy *policy) +{

•   int cpu;
  

•   struct gov_data *gd;
  

•   /* prepare per-policy private data */
  

•   gd = kzalloc(sizeof(*gd), GFP_KERNEL);
  

•   if (!gd) {
  

•           pr_debug("%s: failed to allocate private data\n", __func__);
  

•           return;
  

•   }
  

•   /*
  

•    * Don't ask for freq changes at an higher rate than what
  

•    * the driver advertises as transition latency.
  

•    */
  

•   gd->throttle_nsec = policy->cpuinfo.transition_latency ?
  

•                       policy->cpuinfo.transition_latency :
  

•                       THROTTLE_NSEC;
  

•   pr_debug("%s: throttle threshold = %u [ns]\n",
  

•             __func__, gd->throttle_nsec);
  

•   /* save per-cpu pointer to per-policy need_wake_task */
  

•   for_each_cpu(cpu, policy->related_cpus)
  

•           per_cpu(cap_gov_wake_task, cpu) = &gd->need_wake_task;
  

•   /* init per-policy kthread */
  

•   gd->task = kthread_create(cap_gov_thread, policy, "kcap_gov_task");
  

•   if (IS_ERR_OR_NULL(gd->task))
  

•           pr_err("%s: failed to create kcap_gov_task thread\n", __func__);
  

•   policy->gov_data = gd;
  

+}

+static void cap_gov_stop(struct cpufreq_policy *policy) +{

•   struct gov_data *gd;
  

•   gd = policy->gov_data;
  

•   policy->gov_data = NULL;
  

•   kthread_stop(gd->task);
  

•   /* FIXME replace with devm counterparts? */
  

•   kfree(gd);
  

+}

+static int cap_gov_setup(struct cpufreq_policy *policy, unsigned int event) +{

•   switch (event) {
  

•           case CPUFREQ_GOV_START:
  

•                   /* Start managing the frequency */
  

•                   cap_gov_start(policy);
  

•                   return 0;
  

•           case CPUFREQ_GOV_STOP:
  

•                   cap_gov_stop(policy);
  

•                   return 0;
  

•           case CPUFREQ_GOV_LIMITS:        /* unused */
  

•           case CPUFREQ_GOV_POLICY_INIT:   /* unused */
  

•           case CPUFREQ_GOV_POLICY_EXIT:   /* unused */
  

•                   break;
  

•   }
  

•   return 0;
  

+}

+#ifndef CONFIG_CPU_FREQ_DEFAULT_GOV_CAP_GOV +static +#endif +struct cpufreq_governor cpufreq_gov_cap_gov = {

•   .name                   = "cap_gov",
  

•   .governor               = cap_gov_setup,
  

•   .owner                  = THIS_MODULE,
  

+};

+static int __init cap_gov_init(void) +{

•   return cpufreq_register_governor(&cpufreq_gov_cap_gov);
  

+}

+static void __exit cap_gov_exit(void) +{

•   cpufreq_unregister_governor(&cpufreq_gov_cap_gov);
  

+}

+/* Try to make this the default governor */ +fs_initcall(cap_gov_init);

+MODULE_LICENSE("GPL"); diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index b066a61..2ec2dc7 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -4257,6 +4257,10 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) update_rq_runnable_avg(rq, rq->nr_running); add_nr_running(rq, 1); }

•   if(sched_energy_freq())
  

•           cap_gov_update_cpu(cpu_of(rq));
  

•   hrtick_update(rq);
  

}

@@ -4318,6 +4322,10 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags) sub_nr_running(rq, 1); update_rq_runnable_avg(rq, 1); }

•   if(sched_energy_freq())
  

•           cap_gov_update_cpu(cpu_of(rq));
  

•   hrtick_update(rq);
  

}

@@ -7768,6 +7776,14 @@ static void run_rebalance_domains(struct softirq_action *h) */ nohz_idle_balance(this_rq, idle); rebalance_domains(this_rq, idle);

•   /*
  

•    * FIXME some hardware does not require this, but current CPUfreq
  

•    * locking prevents us from changing cpu frequency with rq locks held
  

•    * and interrupts disabled
  

•    */
  

•   if (sched_energy_freq())
  

•           cap_gov_kick_thread(cpu_of(this_rq));
  

}

/* @@ -7821,6 +7837,9 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) task_tick_numa(rq, curr);

    update_rq_runnable_avg(rq, 1);

•   if(sched_energy_freq())
  

•           cap_gov_update_cpu(cpu_of(rq));
  

}