[RFC PATCH 1/3] ARM: (Experimental) Provide Estimated CPU Capacity measure

[RFC PATCH 1/3] ARM: (Experimental) Provide Estimated CPU Capacity measure

[Chris Redpath]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=UTF-8, Size: 14879 bytes --]

Bsed upon the CPU Power of a core, computes a capacity measure
between 0 and 1024 scaling in line with the frequency using a
simple linear scale derived from the maximum frequency reported
by CPUFreq.

Scaling CPU Power with frequency and estimated capacity gives an
estimate of the amount of potential compute capacity available to
a specific core relative to any other in the system.

Change-Id: I8048a23fe5999536b6325a5ec64549dd69f5a865
---
 arch/arm/Kconfig                  |   16 +++
 arch/arm/include/asm/topology.h   |    7 ++
 arch/arm/kernel/topology.c        |  216 ++++++++++++++++++++++++++++++++++++-
 drivers/base/topology.c           |   18 ++++
 linaro/configs/big-LITTLE-MP.conf |    3 +-
 5 files changed, 258 insertions(+), 2 deletions(-)

diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig
index 71d5b22..86ea8e8 100644
--- a/arch/arm/Kconfig
+++ b/arch/arm/Kconfig
@@ -1624,6 +1624,22 @@ config SCHED_SMT
          MultiThreading at a cost of slightly increased overhead in some
          places. If unsure say N here.

+config ARCH_SCALE_INVARIANT_CPU_CAPACITY
+       bool "Scale-Invariant CPU Compute Capacity Recording (EXPERIMENTAL)"
+       depends on EXPERIMENTAL
+       depends on CPU_FREQ
+       help
+         Provides a new measure of maximum and instantaneous CPU compute
+         capacity, derived from a table of relative compute performance
+         for each core type present in the system. The table is an
+         estimate and specific core performance may be different for
+         any particular workload. The measure includes the relative
+         performance and a linear scale of current to maximum frequency
+         such that at maximum frequency (as expressed in the DTB) the
+         reported compute capacity will be equal to the estimated
+         performance from the table. Values range between 0 and 1023 where
+         1023 is the highest capacity available in the system.
+
 config HAVE_ARM_SCU
        bool
        help
diff --git a/arch/arm/include/asm/topology.h b/arch/arm/include/asm/topology.h
index 417cf43..3e3c1cd 100644
--- a/arch/arm/include/asm/topology.h
+++ b/arch/arm/include/asm/topology.h
@@ -19,6 +19,13 @@ extern struct cputopo_arm cpu_topology[NR_CPUS];
 #define topology_core_id(cpu)          (cpu_topology[cpu].core_id)
 #define topology_core_cpumask(cpu)     (&cpu_topology[cpu].core_sibling)
 #define topology_thread_cpumask(cpu)   (&cpu_topology[cpu].thread_sibling)
+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+extern unsigned long arch_get_max_cpu_capacity(int);
+extern unsigned long arch_get_cpu_capacity(int);
+
+#define topology_max_cpu_capacity(cpu) (arch_get_max_cpu_capacity(cpu))
+#define topology_cpu_capacity(cpu)     (arch_get_cpu_capacity(cpu))
+#endif

 #define mc_capable()   (cpu_topology[0].socket_id != -1)
 #define smt_capable()  (cpu_topology[0].thread_id != -1)
diff --git a/arch/arm/kernel/topology.c b/arch/arm/kernel/topology.c
index 354e279..8c4650a 100644
--- a/arch/arm/kernel/topology.c
+++ b/arch/arm/kernel/topology.c
@@ -40,12 +40,65 @@
  * rebalance_domains for all idle cores and the cpu_power can be updated
  * during this sequence.
  */
+
+/* when CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY is in use, a new measure of
+ * compute capacity is available. This is limited to a maximum of 1024 and
+ * scaled between 0 and 1023 according to frequency.
+ * Cores with different base CPU powers are scaled in line with this.
+ * CPU capacity for each core represents a comparable ratio to maximum
+ * achievable core compute capacity for a core in this system.
+ *
+ * e.g.1 If all cores in the system have a base CPU power of 1024 according to
+ * efficiency calculations and are DVFS scalable between 500MHz and 1GHz, the
+ * cores currently at 1GHz will have CPU power of 1024 whilst the cores
+ * currently at 500MHz will have CPU power of 512.
+ *
+ * e.g.2
+ * If core 0 has a base CPU power of 2048 and runs at 500MHz & 1GHz whilst
+ * core 1 has a base CPU power of 1024 and runs at 100MHz and 200MHz, then
+ * the following possibilities are available:
+ *
+ * cpu power\| 1GHz:100Mhz | 1GHz : 200MHz | 500MHz:100MHz | 500MHz:200MHz |
+ * ----------|-------------|---------------|---------------|---------------|
+ *    core 0 |    1024     |     1024      |     512       |     512       |
+ *    core 1 |     256     |      512      |     256       |     512       |
+ *
+ * This information may be useful to the scheduler when load balancing,
+ * so that the compute capacity of the core a task ran on can be baked into
+ * task load histories.
+ */
 static DEFINE_PER_CPU(unsigned long, cpu_scale);
+static DEFINE_PER_CPU(unsigned long, base_cpu_capacity);
+static DEFINE_PER_CPU(unsigned long, invariant_cpu_capacity);
+static DEFINE_PER_CPU(unsigned long, prescaled_cpu_capacity);
+
+static int frequency_invariant_power_enabled = 1;
+
+/* >0=1, <=0=0 */
+void set_invariant_power_enabled(int val)
+{
+       if(val>0)
+               frequency_invariant_power_enabled = 1;
+       else
+               frequency_invariant_power_enabled = 0;
+}

 unsigned long arch_scale_freq_power(struct sched_domain *sd, int cpu)
 {
        return per_cpu(cpu_scale, cpu);
 }
+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+unsigned long arch_get_cpu_capacity(int cpu)
+{
+       return per_cpu(invariant_cpu_capacity, cpu);
+}
+unsigned long arch_get_max_cpu_capacity(int cpu)
+{
+       return per_cpu(base_cpu_capacity, cpu);
+}
+#endif
+
+

 static void set_power_scale(unsigned int cpu, unsigned long power)
 {
@@ -82,7 +135,6 @@ struct cpu_capacity {
 struct cpu_capacity *cpu_capacity;

 unsigned long middle_capacity = 1;
-
 /*
  * Iterate all CPUs' descriptor in DT and compute the efficiency
  * (as per table_efficiency). Also calculate a middle efficiency
@@ -349,3 +401,165 @@ void __init init_cpu_topology(void)

        parse_dt_topology();
 }
+
+
+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+#include <linux/cpufreq.h>
+
+#define CPUPOWER_FREQSCALE_SHIFT 10
+#define CPUPOWER_FREQSCALE_DEFAULT (1L << CPUPOWER_FREQSCALE_SHIFT)
+struct cpufreq_extents {
+       u32 max;
+       u32 flags;
+};
+/* Flag set when the governor in use only allows one frequency.
+ * Disables scaling.
+ */
+#define CPUPOWER_FREQINVAR_SINGLEFREQ 0x01
+static struct cpufreq_extents freq_scale[CONFIG_NR_CPUS];
+
+static unsigned long get_max_cpu_power()
+{
+       unsigned long max_cpu_power = 0;
+       int cpu;
+       for_each_online_cpu(cpu){
+               if( per_cpu(cpu_scale, cpu) > max_cpu_power)
+                       max_cpu_power = per_cpu(cpu_scale, cpu);
+       }
+       return max_cpu_power;
+}
+
+
+/* Called when the CPU Frequency is changed.
+ * Once for each CPU.
+ */
+static int cpufreq_callback(struct notifier_block *nb,
+                                       unsigned long val, void *data)
+{
+       struct cpufreq_freqs *freq = data;
+       int cpu = freq->cpu;
+       struct cpufreq_extents *extents;
+       unsigned int curr_freq;
+
+       if (freq->flags & CPUFREQ_CONST_LOOPS)
+               return NOTIFY_OK;
+
+       if (val != CPUFREQ_POSTCHANGE)
+               return NOTIFY_OK;
+
+       /* if dynamic load scale is disabled, set the load scale to 1.0 */
+       if (!frequency_invariant_power_enabled) {
+               per_cpu(invariant_cpu_capacity, cpu) = per_cpu(base_cpu_capacity, cpu);
+               return NOTIFY_OK;
+       }
+
+       extents = &freq_scale[cpu];
+       /* If our governor was recognised as a single-freq governor,
+        * use curr = max to be sure multiplier is 1.0
+        */
+       if (extents->flags & CPUPOWER_FREQINVAR_SINGLEFREQ)
+               curr_freq = extents->max;
+       else
+               curr_freq = freq->new >> CPUPOWER_FREQSCALE_SHIFT;
+
+       per_cpu(invariant_cpu_capacity, cpu) = (curr_freq *
+               per_cpu(prescaled_cpu_capacity, cpu)) >> CPUPOWER_FREQSCALE_SHIFT;
+       return NOTIFY_OK;
+}
+
+/* Called when the CPUFreq governor is changed.
+ * Only called for the CPUs which are actually changed by the
+ * userspace.
+ */
+static int cpufreq_policy_callback(struct notifier_block *nb,
+                                      unsigned long event, void *data)
+{
+       struct cpufreq_policy *policy = data;
+       struct cpufreq_extents *extents;
+       int cpu, singleFreq = 0, cpu_capacity;
+       static const char performance_governor[] = "performance";
+       static const char powersave_governor[] = "powersave";
+       unsigned long max_cpu_power;
+
+       if (event == CPUFREQ_START)
+               return 0;
+
+       if (event != CPUFREQ_INCOMPATIBLE)
+               return 0;
+
+       /* CPUFreq governors do not accurately report the range of
+        * CPU Frequencies they will choose from.
+        * We recognise performance and powersave governors as
+        * single-frequency only.
+        */
+       if (!strncmp(policy->governor->name, performance_governor,
+                       strlen(performance_governor)) ||
+               !strncmp(policy->governor->name, powersave_governor,
+                               strlen(powersave_governor)))
+               singleFreq = 1;
+
+       max_cpu_power = get_max_cpu_power();
+       /* Make sure that all CPUs impacted by this policy are
+        * updated since we will only get a notification when the
+        * user explicitly changes the policy on a CPU.
+        */
+       for_each_cpu(cpu, policy->cpus) {
+               /* scale cpu_power to max(1024) */
+               cpu_capacity = (per_cpu(cpu_scale, cpu) << CPUPOWER_FREQSCALE_SHIFT)
+                               / max_cpu_power;
+               extents = &freq_scale[cpu];
+               extents->max = policy->max >> CPUPOWER_FREQSCALE_SHIFT;
+               if (!frequency_invariant_power_enabled) {
+                       /* when disabled, invariant_cpu_scale = cpu_scale */
+                       per_cpu(base_cpu_capacity, cpu) = CPUPOWER_FREQSCALE_DEFAULT;
+                       per_cpu(invariant_cpu_capacity, cpu) = CPUPOWER_FREQSCALE_DEFAULT;
+                       /* unused when disabled */
+                       per_cpu(prescaled_cpu_capacity, cpu) = CPUPOWER_FREQSCALE_DEFAULT;
+               } else {
+                       if (singleFreq)
+                               extents->flags |= CPUPOWER_FREQINVAR_SINGLEFREQ;
+                       else
+                               extents->flags &= ~CPUPOWER_FREQINVAR_SINGLEFREQ;
+                       per_cpu(base_cpu_capacity, cpu) = cpu_capacity;
+                       per_cpu(prescaled_cpu_capacity, cpu) = (cpu_capacity << CPUPOWER_FREQSCALE_SHIFT) / extents->max;
+                       per_cpu(invariant_cpu_capacity, cpu) =
+                                       ((policy->cur >> CPUPOWER_FREQSCALE_SHIFT) *
+                                       per_cpu(prescaled_cpu_capacity, cpu)) >> CPUPOWER_FREQSCALE_SHIFT;
+               }
+       }
+       return 0;
+}
+
+static struct notifier_block cpufreq_notifier = {
+       .notifier_call  = cpufreq_callback,
+};
+static struct notifier_block cpufreq_policy_notifier = {
+       .notifier_call  = cpufreq_policy_callback,
+};
+
+static int __init register_topology_cpufreq_notifier(void)
+{
+       int ret;
+
+       /* init safe defaults since there are no policies at registration */
+       for (ret = 0; ret < CONFIG_NR_CPUS; ret++) {
+               /* safe defaults */
+               freq_scale[ret].max = CPUPOWER_FREQSCALE_DEFAULT;
+               per_cpu(base_cpu_capacity, ret) = CPUPOWER_FREQSCALE_DEFAULT;
+               per_cpu(invariant_cpu_capacity, ret) = CPUPOWER_FREQSCALE_DEFAULT;
+               per_cpu(prescaled_cpu_capacity, ret) = CPUPOWER_FREQSCALE_DEFAULT;
+       }
+
+       pr_info("topology: registering cpufreq notifiers for scale-invariant CPU Power\n");
+       ret = cpufreq_register_notifier(&cpufreq_policy_notifier,
+                       CPUFREQ_POLICY_NOTIFIER);
+
+       if (ret != -EINVAL)
+               ret = cpufreq_register_notifier(&cpufreq_notifier,
+                       CPUFREQ_TRANSITION_NOTIFIER);
+
+       return ret;
+}
+
+core_initcall(register_topology_cpufreq_notifier);
+#endif /* CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY */
diff --git a/drivers/base/topology.c b/drivers/base/topology.c
index ae989c5..23159ad 100644
--- a/drivers/base/topology.c
+++ b/drivers/base/topology.c
@@ -43,6 +43,13 @@ static ssize_t show_##name(struct device *dev,                       \
        unsigned int cpu = dev->id;                             \
        return sprintf(buf, "%d\n", topology_##name(cpu));      \
 }
+#define define_id_lu_show_func(name)                   \
+static ssize_t show_##name(struct device *dev,                 \
+               struct device_attribute *attr, char *buf)       \
+{                                                              \
+       unsigned int cpu = dev->id;                             \
+       return sprintf(buf, "%lu\n", topology_##name(cpu));     \
+}

 #if defined(topology_thread_cpumask) || defined(topology_core_cpumask) || \
     defined(topology_book_cpumask)
@@ -122,6 +129,13 @@ define_one_ro_named(book_siblings, show_book_cpumask);
 define_one_ro_named(book_siblings_list, show_book_cpumask_list);
 #endif

+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+define_id_lu_show_func(max_cpu_capacity);
+define_one_ro(max_cpu_capacity);
+define_id_lu_show_func(cpu_capacity);
+define_one_ro(cpu_capacity);
+#endif
+
 static struct attribute *default_attrs[] = {
        &dev_attr_physical_package_id.attr,
        &dev_attr_core_id.attr,
@@ -134,6 +148,10 @@ static struct attribute *default_attrs[] = {
        &dev_attr_book_siblings.attr,
        &dev_attr_book_siblings_list.attr,
 #endif
+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+       &dev_attr_max_cpu_capacity.attr,
+       &dev_attr_cpu_capacity.attr,
+#endif
        NULL
 };

diff --git a/linaro/configs/big-LITTLE-MP.conf b/linaro/configs/big-LITTLE-MP.conf
index 8cc2be0..34122aa 100644
--- a/linaro/configs/big-LITTLE-MP.conf
+++ b/linaro/configs/big-LITTLE-MP.conf
@@ -8,6 +8,7 @@ CONFIG_SCHED_HMP=y
 CONFIG_HMP_FAST_CPU_MASK=""
 CONFIG_HMP_SLOW_CPU_MASK=""
 CONFIG_HMP_VARIABLE_SCALE=y
-CONFIG_HMP_FREQUENCY_INVARIANT_SCALE=y
 CONFIG_SCHED_HMP_PRIO_FILTER=y
 CONFIG_SCHED_HMP_PRIO_FILTER_VAL=5
+CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY=y
+
--
1.7.9.5


-- IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium.  Thank you.
ÿôèº{.nÇ+‰·Ÿ®‰­†+%ŠËÿ±éݶ\x17¥Šwÿº{.nÇ+‰·¥Š{±þG«éÿŠ{ayº\x1dʇڙë,j\a­¢f£¢·hšïêÿ‘êçz_è®\x03(­éšŽŠÝ¢j"ú\x1a¶^[m§ÿÿ¾\a«þG«éÿ¢¸?™¨è­Ú&£ø§~á¶iO•æ¬z·švØ^\x14\x04\x1a¶^[m§ÿÿÃ\fÿ¶ìÿ¢¸?–I¥

[RFC PATCH 2/3] sched: introduce compute capacity for CPUs, groups and domains

[Chris Redpath]

Using the per-cpu compute capacity exported from topology
when CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY is active, place this
information alongside cpu_power in the scheduler and combine for the
various aggregating entities.

Change-Id: I4984c335bcdc128680e7459b3f86bb05e04593cc
---
 include/linux/sched.h        |    7 +++++
 include/trace/events/sched.h |   24 +++++++++++++++
 kernel/sched/core.c          |    2 ++
 kernel/sched/debug.c         |    3 ++
 kernel/sched/fair.c          |   69 ++++++++++++++++++++++++++++++++++++++----
 kernel/sched/sched.h         |    4 +++
 6 files changed, 103 insertions(+), 6 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 7c64f30..f2ee59a 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -863,6 +863,13 @@ struct sched_group_power {
 	unsigned int power, power_orig;
 	unsigned long next_update;
 	/*
+	 * Compute capacity of this group, where each CPU has a compute
+	 * capacity expressed as a value [0..SCHED_POWER_SCALE] against
+	 * the most powerful CPU in the system of capacity SCHED_POWER_SCALE.
+	 */
+	unsigned int compute_capacity;
+	unsigned int max_compute_capacity;
+	/*
 	 * Number of busy cpus in this group.
 	 */
 	atomic_t nr_busy_cpus;
diff --git a/include/trace/events/sched.h b/include/trace/events/sched.h
index 8932919..45e27bc 100644
--- a/include/trace/events/sched.h
+++ b/include/trace/events/sched.h
@@ -985,6 +985,30 @@ TRACE_EVENT(sched_fsi,
 );
 
 /*
+ * Extra debug trace points
+ */
+TRACE_EVENT(sched_upd_cap,
+
+	TP_PROTO(int dst_cpu, unsigned long curr, unsigned long max ),
+
+	TP_ARGS(dst_cpu, curr, max ),
+
+	TP_STRUCT__entry(
+		__field(int,  dst_cpu)
+		__field(unsigned long,  curr)
+		__field(unsigned long,  max)
+	),
+
+	TP_fast_assign(
+		__entry->dst_cpu = dst_cpu;
+		__entry->curr = curr;
+		__entry->max = max;
+	),
+
+	TP_printk("cpu=%d curr=%lu max=%lu",
+			__entry->dst_cpu, __entry->curr, __entry->max)
+);
+/*
  * Tracepoint for showing priority inheritance modifying a tasks
  * priority.
  */
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index ec7406d..e535222 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -6940,6 +6940,8 @@ void __init sched_init(void)
 		rq->sd = NULL;
 		rq->rd = NULL;
 		rq->cpu_power = SCHED_POWER_SCALE;
+		rq->curr_compute_capacity = SCHED_POWER_SCALE;
+		rq->max_compute_capacity = SCHED_POWER_SCALE;
 		rq->post_schedule = 0;
 		rq->active_balance = 0;
 		rq->next_balance = jiffies;
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index b9d54d0..9102bb4 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -290,6 +290,9 @@ do {									\
 #define PN(x) \
 	SEQ_printf(m, "  .%-30s: %Ld.%06ld\n", #x, SPLIT_NS(rq->x))
 
+	P(cpu_power);
+	P(curr_compute_capacity);
+	P(max_compute_capacity);
 	P(nr_running);
 	SEQ_printf(m, "  .%-30s: %lu\n", "load",
 		   rq->load.weight);
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index d9af9c1..f6bbe1e 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1267,6 +1267,27 @@ static u32 __compute_runnable_contrib(u64 n)
 	return contrib + runnable_avg_yN_sum[n];
 }
 
+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+#define SCHED_ARCH_SCALE_POWER_SHIFT 10
+#endif
+static inline unsigned long compute_capacity_of(int cpu)
+{
+	return cpu_rq(cpu)->curr_compute_capacity;
+}
+
+static inline unsigned long max_compute_capacity_of(int cpu)
+{
+	return cpu_rq(cpu)->max_compute_capacity;
+}
+
+static inline void update_cpu_capacity(int cpu)
+{
+	int tmp_capacity = arch_get_cpu_capacity(cpu);
+	int tmp_max_capacity = arch_get_max_cpu_capacity(cpu);
+	trace_sched_upd_cap(cpu, tmp_capacity, tmp_max_capacity);
+	cpu_rq(cpu)->max_compute_capacity = tmp_max_capacity;
+	cpu_rq(cpu)->curr_compute_capacity = tmp_capacity;
+}
 /*
  * We can represent the historical contribution to runnable average as the
  * coefficients of a geometric series.  To do this we sub-divide our runnable
@@ -4360,6 +4381,8 @@ struct sd_lb_stats {
 	unsigned long total_load;  /* Total load of all groups in sd */
 	unsigned long total_pwr;   /*	Total power of all groups in sd */
 	unsigned long avg_load;	   /* Average load across all groups in sd */
+	unsigned long total_cap;   /* Total current compute capacity of all groups in sd */
+	unsigned long total_maxcap; /* Total max compute capacity of all groups in sd */
 
 	/** Statistics of this group */
 	unsigned long this_load;
@@ -4388,7 +4411,9 @@ struct sg_lb_stats {
 	unsigned long group_load; /* Total load over the CPUs of the group */
 	unsigned long sum_nr_running; /* Nr tasks running in the group */
 	unsigned long sum_weighted_load; /* Weighted load of group's tasks */
-	unsigned long group_capacity;
+	unsigned long group_compute_capacity; /* current compute capacity of the group */
+	unsigned long group_max_compute_capacity; /* maximum compute capacity of the group */
+	unsigned long group_capacity; /* Nr tasks this group can handle before considered overloaded */
 	unsigned long idle_cpus;
 	unsigned long group_weight;
 	int group_imb; /* Is there an imbalance in the group ? */
@@ -4430,6 +4455,23 @@ unsigned long __weak arch_scale_freq_power(struct sched_domain *sd, int cpu)
 {
 	return default_scale_freq_power(sd, cpu);
 }
+unsigned long __weak arch_cpu_capacity(int cpu)
+{
+	return SCHED_POWER_SCALE;
+}
+unsigned long __weak arch_max_cpu_capacity(int cpu)
+{
+	return SCHED_POWER_SCALE;
+}
+
+unsigned long __weak arch_get_cpu_capacity(int cpu)
+{
+	return SCHED_POWER_SCALE;
+}
+unsigned long __weak arch_get_max_cpu_capacity(int cpu)
+{
+	return SCHED_POWER_SCALE;
+}
 
 unsigned long default_scale_smt_power(struct sched_domain *sd, int cpu)
 {
@@ -4506,6 +4548,7 @@ static void update_cpu_power(struct sched_domain *sd, int cpu)
 		power = 1;
 
 	cpu_rq(cpu)->cpu_power = power;
+	update_cpu_capacity(cpu);
 	sdg->sgp->power = power;
 }
 
@@ -4514,6 +4557,7 @@ void update_group_power(struct sched_domain *sd, int cpu)
 	struct sched_domain *child = sd->child;
 	struct sched_group *group, *sdg = sd->groups;
 	unsigned long power;
+	unsigned long compute_capacity, max_compute_capacity;
 	unsigned long interval;
 
 	interval = msecs_to_jiffies(sd->balance_interval);
@@ -4526,6 +4570,8 @@ void update_group_power(struct sched_domain *sd, int cpu)
 	}
 
 	power = 0;
+	compute_capacity = 0;
+	max_compute_capacity = 0;
 
 	if (child->flags & SD_OVERLAP) {
 		/*
@@ -4533,8 +4579,11 @@ void update_group_power(struct sched_domain *sd, int cpu)
 		 * span the current group.
 		 */
 
-		for_each_cpu(cpu, sched_group_cpus(sdg))
+		for_each_cpu(cpu, sched_group_cpus(sdg)) {
 			power += power_of(cpu);
+			compute_capacity += compute_capacity_of(cpu);
+			max_compute_capacity += max_compute_capacity_of(cpu);
+		}
 	} else  {
 		/*
 		 * !SD_OVERLAP domains can assume that child groups
@@ -4544,11 +4593,15 @@ void update_group_power(struct sched_domain *sd, int cpu)
 		group = child->groups;
 		do {
 			power += group->sgp->power;
+			compute_capacity += group->sgp->compute_capacity;
+			max_compute_capacity += group->sgp->max_compute_capacity;
 			group = group->next;
 		} while (group != child->groups);
 	}
 
 	sdg->sgp->power_orig = sdg->sgp->power = power;
+	sdg->sgp->compute_capacity = compute_capacity;
+	sdg->sgp->max_compute_capacity = max_compute_capacity;
 }
 
 /*
@@ -4639,6 +4692,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 		sgs->group_load += load;
 		sgs->sum_nr_running += nr_running;
 		sgs->sum_weighted_load += weighted_cpuload(i);
+		sgs->group_compute_capacity += compute_capacity_of(i);
+		sgs->group_max_compute_capacity += max_compute_capacity_of(i);
 		if (idle_cpu(i))
 			sgs->idle_cpus++;
 	}
@@ -4774,6 +4829,8 @@ static inline void update_sd_lb_stats(struct lb_env *env,
 
 		sds->total_load += sgs.group_load;
 		sds->total_pwr += sg->sgp->power;
+		sds->total_cap += sg->sgp->compute_capacity;
+		sds->total_maxcap += sg->sgp->compute_capacity;
 
 		/*
 		 * In case the child domain prefers tasks go to siblings
@@ -5122,12 +5179,12 @@ static struct rq *find_busiest_queue(struct lb_env *env,
 
 	for_each_cpu(i, sched_group_cpus(group)) {
 		unsigned long power = power_of(i);
-		unsigned long capacity = DIV_ROUND_CLOSEST(power,
+		unsigned long task_capacity = DIV_ROUND_CLOSEST(power,
 							   SCHED_POWER_SCALE);
 		unsigned long wl;
 
-		if (!capacity)
-			capacity = fix_small_capacity(env->sd, group);
+		if (!task_capacity)
+			task_capacity = fix_small_capacity(env->sd, group);
 
 		if (!cpumask_test_cpu(i, env->cpus))
 			continue;
@@ -5151,7 +5208,7 @@ static struct rq *find_busiest_queue(struct lb_env *env,
 		 * When comparing with imbalance, use weighted_cpuload()
 		 * which is not scaled with the cpu power.
 		 */
-		if (capacity && rq->nr_running == 1 && wl > env->imbalance)
+		if (task_capacity && rq->nr_running == 1 && wl > env->imbalance)
 			continue;
 
 		/*
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 6f8976b..0946f40 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -412,6 +412,10 @@ struct rq {
 
 	unsigned long cpu_power;
 
+	/* CPU compute capacity estimation */
+	unsigned long max_compute_capacity;
+	unsigned long curr_compute_capacity;
+
 	unsigned char idle_balance;
 	/* For active balancing */
 	int post_schedule;
-- 
1.7.9.5

[RFC PATCH 3/3] sched: Scale load contribution by CPU Capacity

[Chris Redpath]

Modulate the tracked load of a task using the measure of current
and maximum compute capacity for the core it is executing on.

Change-Id: If6aea806e631f2313fd925c8902260a522663dbd

Conflicts:

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

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index f6bbe1e..3f3ee08 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1319,11 +1319,15 @@ static inline void update_cpu_capacity(int cpu)
 static __always_inline int __update_entity_runnable_avg(u64 now,
 							struct sched_avg *sa,
 							int runnable,
-							int running)
+							int running,
+							int cpu)
 {
 	u64 delta, periods;
 	u32 runnable_contrib;
 	int delta_w, decayed = 0;
+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+	u32 curr_scale = 1<<SCHED_ARCH_SCALE_POWER_SHIFT;
+#endif /* CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY */
 
 	delta = now - sa->last_runnable_update;
 	/*
@@ -1344,6 +1348,12 @@ static __always_inline int __update_entity_runnable_avg(u64 now,
 		return 0;
 	sa->last_runnable_update = now;
 
+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+	update_cpu_capacity(cpu);
+	curr_scale = (compute_capacity_of(cpu) << SCHED_ARCH_SCALE_POWER_SHIFT)
+			/ (max_compute_capacity_of(cpu)+1);
+#endif
+
 	/* delta_w is the amount already accumulated against our next period */
 	delta_w = sa->runnable_avg_period % 1024;
 	if (delta + delta_w >= 1024) {
@@ -1356,13 +1366,17 @@ static __always_inline int __update_entity_runnable_avg(u64 now,
 		 * period and accrue it.
 		 */
 		delta_w = 1024 - delta_w;
+		sa->runnable_avg_period += delta_w;
+		delta -= delta_w;
+		/* scale runnable time if necessary */
+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+		delta_w = (delta_w * curr_scale)
+				>> SCHED_ARCH_SCALE_POWER_SHIFT;
+#endif
 		if (runnable)
 			sa->runnable_avg_sum += delta_w;
 		if (running)
 			sa->usage_avg_sum += delta_w;
-		sa->runnable_avg_period += delta_w;
-
-		delta -= delta_w;
 
 		/* Figure out how many additional periods this update spans */
 		periods = delta / 1024;
@@ -1376,19 +1390,31 @@ static __always_inline int __update_entity_runnable_avg(u64 now,
 
 		/* Efficiently calculate \sum (1..n_period) 1024*y^i */
 		runnable_contrib = __compute_runnable_contrib(periods);
+		sa->runnable_avg_period += runnable_contrib;
+		/* Apply load scaling if necessary.
+		 * Note that multiplying the whole series is same as
+		 * multiplying all terms
+		 */
+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+		runnable_contrib = (runnable_contrib * curr_scale)
+				>> SCHED_ARCH_SCALE_POWER_SHIFT;
+#endif 
 		if (runnable)
 			sa->runnable_avg_sum += runnable_contrib;
 		if (running)
 			sa->usage_avg_sum += runnable_contrib;
-		sa->runnable_avg_period += runnable_contrib;
 	}
 
 	/* Remainder of delta accrued against u_0` */
+	sa->runnable_avg_period += delta;
+	/* scale if necessary */
+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+	delta = ((delta * curr_scale) >> SCHED_ARCH_SCALE_POWER_SHIFT);
+#endif
 	if (runnable)
 		sa->runnable_avg_sum += delta;
 	if (running)
 		sa->usage_avg_sum += delta;
-	sa->runnable_avg_period += delta;
 
 	return decayed;
 }
@@ -1551,7 +1577,11 @@ static inline void update_entity_load_avg(struct sched_entity *se,
 	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 	long contrib_delta;
 	u64 now;
+	int cpu = -1;   /* not used in normal case */
 
+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+	cpu = cfs_rq->rq->cpu;
+#endif
 	/*
 	 * For a group entity we need to use their owned cfs_rq_clock_task() in
 	 * case they are the parent of a throttled hierarchy.
@@ -1562,7 +1592,7 @@ static inline void update_entity_load_avg(struct sched_entity *se,
 		now = cfs_rq_clock_task(group_cfs_rq(se));
 
 	if (!__update_entity_runnable_avg(now, &se->avg, se->on_rq,
-					  cfs_rq->curr == se))
+			cfs_rq->curr == se, cpu))
 		return;
 
 	contrib_delta = __update_entity_load_avg_contrib(se);
@@ -1607,8 +1637,13 @@ static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq, int force_update)
 static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
 {
 	u32 contrib;
+	int cpu = -1;	/* not used in normal case */
+
+#ifdef CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY
+	cpu = rq->cpu;
+#endif
 	__update_entity_runnable_avg(rq->clock_task, &rq->avg, runnable,
-				     runnable);
+			runnable, cpu);
 	__update_tg_runnable_avg(&rq->avg, &rq->cfs);
 	contrib = rq->avg.runnable_avg_sum * scale_load_down(1024);
 	contrib /= (rq->avg.runnable_avg_period + 1);
-- 
1.7.9.5