From 00d520269ed1cf7266b595312614e06569da0394 Mon Sep 17 00:00:00 2001 From: Morten Rasmussen Date: Fri, 14 Sep 2012 14:38:09 +0100 Subject: sched: Task placement for heterogeneous systems based on task load-tracking This patch introduces the basic SCHED_HMP infrastructure. Each class of cpus is represented by a hmp_domain and tasks will only be moved between these domains when their load profiles suggest it is beneficial. SCHED_HMP relies heavily on the task load-tracking introduced in Paul Turners fair group scheduling patch set: SCHED_HMP requires that the platform implements arch_get_hmp_domains() which should set up the platform specific list of hmp_domains. It is also assumed that the platform disables SD_LOAD_BALANCE for the appropriate sched_domains. Tasks placement takes place every time a task is to be inserted into a runqueue based on its load history. The task placement decision is based on load thresholds. There are no restrictions on the number of hmp_domains, however, multiple (>2) has not been tested and the up/down migration policy is rather simple. Signed-off-by: Morten Rasmussen --- arch/arm/Kconfig | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) (limited to 'arch') diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig index 5b714695b01..7abe7094def 100644 --- a/arch/arm/Kconfig +++ b/arch/arm/Kconfig @@ -1582,6 +1582,23 @@ config SCHED_SMT MultiThreading at a cost of slightly increased overhead in some places. If unsure say N here. +config DISABLE_CPU_SCHED_DOMAIN_BALANCE + bool "(EXPERIMENTAL) Disable CPU level scheduler load-balancing" + help + Disables scheduler load-balancing at CPU sched domain level. + +config SCHED_HMP + bool "(EXPERIMENTAL) Heterogenous multiprocessor scheduling" + depends on DISABLE_CPU_SCHED_DOMAIN_BALANCE && SCHED_MC && FAIR_GROUP_SCHED && !SCHED_AUTOGROUP + help + Experimental scheduler optimizations for heterogeneous platforms. + Attempts to introspectively select task affinity to optimize power + and performance. Basic support for multiple (>2) cpu types is in place, + but it has only been tested with two types of cpus. + There is currently no support for migration of task groups, hence + !SCHED_AUTOGROUP. Furthermore, normal load-balancing must be disabled + between cpus of different type (DISABLE_CPU_SCHED_DOMAIN_BALANCE). + config HAVE_ARM_SCU bool help -- cgit v1.2.3 From b46f8c8b364e03ea97e0807fe4e09d32c9dce69a Mon Sep 17 00:00:00 2001 From: Morten Rasmussen Date: Fri, 14 Sep 2012 14:38:11 +0100 Subject: sched: Introduce priority-based task migration filter Introduces a priority threshold which prevents low priority task from migrating to faster hmp_domains (cpus). This is useful for user-space software which assigns lower task priority to background task. Signed-off-by: Morten Rasmussen --- arch/arm/Kconfig | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'arch') diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig index 7abe7094def..d24768c04be 100644 --- a/arch/arm/Kconfig +++ b/arch/arm/Kconfig @@ -1599,6 +1599,19 @@ config SCHED_HMP !SCHED_AUTOGROUP. Furthermore, normal load-balancing must be disabled between cpus of different type (DISABLE_CPU_SCHED_DOMAIN_BALANCE). +config SCHED_HMP_PRIO_FILTER + bool "(EXPERIMENTAL) Filter HMP migrations by task priority" + depends on SCHED_HMP + help + Enables task priority based HMP migration filter. Any task with + a NICE value above the threshold will always be on low-power cpus + with less compute capacity. + +config SCHED_HMP_PRIO_FILTER_VAL + int "NICE priority threshold" + default 5 + depends on SCHED_HMP_PRIO_FILTER + config HAVE_ARM_SCU bool help -- cgit v1.2.3 From bb7c9814e9cdeaccd05ad9c08764ed9249020273 Mon Sep 17 00:00:00 2001 From: Morten Rasmussen Date: Fri, 14 Sep 2012 14:38:12 +0100 Subject: ARM: Add HMP scheduling support for ARM architecture Adds Kconfig entries to enable HMP scheduling on ARM platforms. Currently, it disables CPU level sched_domain load-balacing in order to simplify things. This needs fixing in a later revision. HMP scheduling will do the load-balancing at this level instead. Signed-off-by: Morten Rasmussen --- arch/arm/Kconfig | 14 ++++++++++++++ arch/arm/include/asm/topology.h | 31 +++++++++++++++++++++++++++++++ 2 files changed, 45 insertions(+) (limited to 'arch') diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig index d24768c04be..b6d20ffd0ec 100644 --- a/arch/arm/Kconfig +++ b/arch/arm/Kconfig @@ -1612,6 +1612,20 @@ config SCHED_HMP_PRIO_FILTER_VAL default 5 depends on SCHED_HMP_PRIO_FILTER +config HMP_FAST_CPU_MASK + string "HMP scheduler fast CPU mask" + depends on SCHED_HMP + help + Specify the cpuids of the fast CPUs in the system as a list string, + e.g. cpuid 0+1 should be specified as 0-1. + +config HMP_SLOW_CPU_MASK + string "HMP scheduler slow CPU mask" + depends on SCHED_HMP + help + Specify the cpuids of the slow CPUs in the system as a list string, + e.g. cpuid 0+1 should be specified as 0-1. + config HAVE_ARM_SCU bool help diff --git a/arch/arm/include/asm/topology.h b/arch/arm/include/asm/topology.h index 58b8b84adcd..5692ba11322 100644 --- a/arch/arm/include/asm/topology.h +++ b/arch/arm/include/asm/topology.h @@ -27,6 +27,37 @@ void init_cpu_topology(void); void store_cpu_topology(unsigned int cpuid); const struct cpumask *cpu_coregroup_mask(int cpu); +#ifdef CONFIG_DISABLE_CPU_SCHED_DOMAIN_BALANCE +/* Common values for CPUs */ +#ifndef SD_CPU_INIT +#define SD_CPU_INIT (struct sched_domain) { \ + .min_interval = 1, \ + .max_interval = 4, \ + .busy_factor = 64, \ + .imbalance_pct = 125, \ + .cache_nice_tries = 1, \ + .busy_idx = 2, \ + .idle_idx = 1, \ + .newidle_idx = 0, \ + .wake_idx = 0, \ + .forkexec_idx = 0, \ + \ + .flags = 0*SD_LOAD_BALANCE \ + | 1*SD_BALANCE_NEWIDLE \ + | 1*SD_BALANCE_EXEC \ + | 1*SD_BALANCE_FORK \ + | 0*SD_BALANCE_WAKE \ + | 1*SD_WAKE_AFFINE \ + | 0*SD_SHARE_CPUPOWER \ + | 0*SD_SHARE_PKG_RESOURCES \ + | 0*SD_SERIALIZE \ + , \ + .last_balance = jiffies, \ + .balance_interval = 1, \ +} +#endif +#endif /* CONFIG_DISABLE_CPU_SCHED_DOMAIN_BALANCE */ + #else static inline void init_cpu_topology(void) { } -- cgit v1.2.3 From 9731b49a4c5dc602164ca78f8bc75298c8a93ccc Mon Sep 17 00:00:00 2001 From: Morten Rasmussen Date: Fri, 14 Sep 2012 14:38:13 +0100 Subject: ARM: sched: Use device-tree to provide fast/slow CPU list for HMP We can't rely on Kconfig options to set the fast and slow CPU lists for HMP scheduling if we want a single kernel binary to support multiple devices with different CPU topology. E.g. TC2 (ARM's Test-Chip-2 big.LITTLE system), Fast Models, or even non big.LITTLE devices. This patch adds the function arch_get_fast_and_slow_cpus() to generate the lists at run-time by parsing the CPU nodes in device-tree; it assumes slow cores are A7s and everything else is fast. The function still supports the old Kconfig options as this is useful for testing the HMP scheduler on devices without big.LITTLE. This patch is reuse of a patch by Jon Medhurst with a few bits left out. Signed-off-by: Morten Rasmussen --- arch/arm/Kconfig | 4 ++- arch/arm/kernel/topology.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 72 insertions(+), 1 deletion(-) (limited to 'arch') diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig index b6d20ffd0ec..fa304b88e7c 100644 --- a/arch/arm/Kconfig +++ b/arch/arm/Kconfig @@ -1616,13 +1616,15 @@ config HMP_FAST_CPU_MASK string "HMP scheduler fast CPU mask" depends on SCHED_HMP help - Specify the cpuids of the fast CPUs in the system as a list string, + Leave empty to use device tree information. + Specify the cpuids of the fast CPUs in the system as a list string, e.g. cpuid 0+1 should be specified as 0-1. config HMP_SLOW_CPU_MASK string "HMP scheduler slow CPU mask" depends on SCHED_HMP help + Leave empty to use device tree information. Specify the cpuids of the slow CPUs in the system as a list string, e.g. cpuid 0+1 should be specified as 0-1. diff --git a/arch/arm/kernel/topology.c b/arch/arm/kernel/topology.c index 79282ebcd93..eac7424d372 100644 --- a/arch/arm/kernel/topology.c +++ b/arch/arm/kernel/topology.c @@ -287,6 +287,75 @@ void store_cpu_topology(unsigned int cpuid) cpu_topology[cpuid].socket_id, mpidr); } + +#ifdef CONFIG_SCHED_HMP + +static const char * const little_cores[] = { + "arm,cortex-a7", + NULL, +}; + +static bool is_little_cpu(struct device_node *cn) +{ + const char * const *lc; + for (lc = little_cores; *lc; lc++) + if (of_device_is_compatible(cn, *lc)) + return true; + return false; +} + +void __init arch_get_fast_and_slow_cpus(struct cpumask *fast, + struct cpumask *slow) +{ + struct device_node *cn = NULL; + int cpu = 0; + + cpumask_clear(fast); + cpumask_clear(slow); + + /* + * Use the config options if they are given. This helps testing + * HMP scheduling on systems without a big.LITTLE architecture. + */ + if (strlen(CONFIG_HMP_FAST_CPU_MASK) && strlen(CONFIG_HMP_SLOW_CPU_MASK)) { + if (cpulist_parse(CONFIG_HMP_FAST_CPU_MASK, fast)) + WARN(1, "Failed to parse HMP fast cpu mask!\n"); + if (cpulist_parse(CONFIG_HMP_SLOW_CPU_MASK, slow)) + WARN(1, "Failed to parse HMP slow cpu mask!\n"); + return; + } + + /* + * Else, parse device tree for little cores. + */ + while ((cn = of_find_node_by_type(cn, "cpu"))) { + + if (cpu >= num_possible_cpus()) + break; + + if (is_little_cpu(cn)) + cpumask_set_cpu(cpu, slow); + else + cpumask_set_cpu(cpu, fast); + + cpu++; + } + + if (!cpumask_empty(fast) && !cpumask_empty(slow)) + return; + + /* + * We didn't find both big and little cores so let's call all cores + * fast as this will keep the system running, with all cores being + * treated equal. + */ + cpumask_setall(fast); + cpumask_clear(slow); +} + +#endif /* CONFIG_SCHED_HMP */ + + /* * init_cpu_topology is called at boot when only one cpu is running * which prevent simultaneous write access to cpu_topology array -- cgit v1.2.3 From 053663e6bc778b946ee7f70505ccf86f371c0180 Mon Sep 17 00:00:00 2001 From: Morten Rasmussen Date: Fri, 14 Sep 2012 14:38:14 +0100 Subject: ARM: sched: Setup SCHED_HMP domains SCHED_HMP requires the different cpu types to be represented by an ordered list of hmp_domains. Each hmp_domain represents all cpus of a particular type using a cpumask. The list is platform specific and therefore must be generated by platform code by implementing arch_get_hmp_domains(). Signed-off-by: Morten Rasmussen --- arch/arm/kernel/topology.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) (limited to 'arch') diff --git a/arch/arm/kernel/topology.c b/arch/arm/kernel/topology.c index eac7424d372..04271db020c 100644 --- a/arch/arm/kernel/topology.c +++ b/arch/arm/kernel/topology.c @@ -353,6 +353,28 @@ void __init arch_get_fast_and_slow_cpus(struct cpumask *fast, cpumask_clear(slow); } +void __init arch_get_hmp_domains(struct list_head *hmp_domains_list) +{ + struct cpumask hmp_fast_cpu_mask; + struct cpumask hmp_slow_cpu_mask; + struct hmp_domain *domain; + + arch_get_fast_and_slow_cpus(&hmp_fast_cpu_mask, &hmp_slow_cpu_mask); + + /* + * Initialize hmp_domains + * Must be ordered with respect to compute capacity. + * Fastest domain at head of list. + */ + domain = (struct hmp_domain *) + kmalloc(sizeof(struct hmp_domain), GFP_KERNEL); + cpumask_copy(&domain->cpus, &hmp_slow_cpu_mask); + list_add(&domain->hmp_domains, hmp_domains_list); + domain = (struct hmp_domain *) + kmalloc(sizeof(struct hmp_domain), GFP_KERNEL); + cpumask_copy(&domain->cpus, &hmp_fast_cpu_mask); + list_add(&domain->hmp_domains, hmp_domains_list); +} #endif /* CONFIG_SCHED_HMP */ -- cgit v1.2.3 From b193b65dd36c95059cbd04d391c58ff4582db146 Mon Sep 17 00:00:00 2001 From: Morten Rasmussen Date: Wed, 10 Oct 2012 14:51:25 +0100 Subject: sched: Enable HMP priority filter by default This updates the ARM Kconfig to enable the HMP priority filter by default. Signed-off-by: Morten Rasmussen --- arch/arm/Kconfig | 1 + 1 file changed, 1 insertion(+) (limited to 'arch') diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig index fa304b88e7c..8ae87dc3806 100644 --- a/arch/arm/Kconfig +++ b/arch/arm/Kconfig @@ -1602,6 +1602,7 @@ config SCHED_HMP config SCHED_HMP_PRIO_FILTER bool "(EXPERIMENTAL) Filter HMP migrations by task priority" depends on SCHED_HMP + default y help Enables task priority based HMP migration filter. Any task with a NICE value above the threshold will always be on low-power cpus -- cgit v1.2.3 From 1a574871bfd002f4d7c7bcf004fd9835de9cea63 Mon Sep 17 00:00:00 2001 From: Jon Medhurst Date: Fri, 12 Oct 2012 13:45:35 +0100 Subject: ARM: sched: Avoid empty 'slow' HMP domain On homogeneous (non-heterogeneous) systems all CPUs will be declared 'fast' and the slow cpu list will be empty. In this situation we need to avoid adding an empty slow HMP domain otherwise the scheduler code will blow up when it attempts to move a task to the slow domain. Signed-off-by: Jon Medhurst --- arch/arm/kernel/topology.c | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) (limited to 'arch') diff --git a/arch/arm/kernel/topology.c b/arch/arm/kernel/topology.c index 04271db020c..f487129ab7f 100644 --- a/arch/arm/kernel/topology.c +++ b/arch/arm/kernel/topology.c @@ -366,10 +366,12 @@ void __init arch_get_hmp_domains(struct list_head *hmp_domains_list) * Must be ordered with respect to compute capacity. * Fastest domain at head of list. */ - domain = (struct hmp_domain *) - kmalloc(sizeof(struct hmp_domain), GFP_KERNEL); - cpumask_copy(&domain->cpus, &hmp_slow_cpu_mask); - list_add(&domain->hmp_domains, hmp_domains_list); + if(!cpumask_empty(&hmp_slow_cpu_mask)) { + domain = (struct hmp_domain *) + kmalloc(sizeof(struct hmp_domain), GFP_KERNEL); + cpumask_copy(&domain->cpus, &hmp_slow_cpu_mask); + list_add(&domain->hmp_domains, hmp_domains_list); + } domain = (struct hmp_domain *) kmalloc(sizeof(struct hmp_domain), GFP_KERNEL); cpumask_copy(&domain->cpus, &hmp_fast_cpu_mask); -- cgit v1.2.3 From 161bebe64ce4264105c09e022deeab0b94b06ead Mon Sep 17 00:00:00 2001 From: Sudeep KarkadaNagesha Date: Mon, 24 Sep 2012 14:07:20 +0100 Subject: sched: fix arch_get_fast_and_slow_cpus to get logical cpumask correctly The patch "sched: Use device-tree to provide fast/slow CPU list for HMP" depends on the ordering of CPU's in the device tree. It breaks to determine the logical mask correctly if the logical mask of the CPUs differ from physical ordering in the device tree. This patch fix the logic by depending on the mpidr in the device tree and mapping that mpidr to the logical cpu. Signed-off-by: Sudeep KarkadaNagesha Signed-off-by: Liviu Dudau --- arch/arm/kernel/topology.c | 20 ++++++++++++++++---- 1 file changed, 16 insertions(+), 4 deletions(-) (limited to 'arch') diff --git a/arch/arm/kernel/topology.c b/arch/arm/kernel/topology.c index f487129ab7f..677325f4355 100644 --- a/arch/arm/kernel/topology.c +++ b/arch/arm/kernel/topology.c @@ -22,6 +22,7 @@ #include #include +#include #include /* @@ -308,7 +309,7 @@ void __init arch_get_fast_and_slow_cpus(struct cpumask *fast, struct cpumask *slow) { struct device_node *cn = NULL; - int cpu = 0; + int cpu; cpumask_clear(fast); cpumask_clear(slow); @@ -330,15 +331,26 @@ void __init arch_get_fast_and_slow_cpus(struct cpumask *fast, */ while ((cn = of_find_node_by_type(cn, "cpu"))) { - if (cpu >= num_possible_cpus()) + const u32 *mpidr; + int len; + + mpidr = of_get_property(cn, "reg", &len); + if (!mpidr || len != 4) { + pr_err("* %s missing reg property\n", cn->full_name); + continue; + } + + cpu = get_logical_index(be32_to_cpup(mpidr)); + if (cpu == -EINVAL) { + pr_err("couldn't get logical index for mpidr %x\n", + be32_to_cpup(mpidr)); break; + } if (is_little_cpu(cn)) cpumask_set_cpu(cpu, slow); else cpumask_set_cpu(cpu, fast); - - cpu++; } if (!cpumask_empty(fast) && !cpumask_empty(slow)) -- cgit v1.2.3 From 37380d0b7621d487b1d2885ad93227e880074ee5 Mon Sep 17 00:00:00 2001 From: Olivier Cozette Date: Wed, 17 Oct 2012 14:30:30 +0100 Subject: ARM: Change load tracking scale using sysfs These functions allow to change the load average period used in the task load average computation through /sys/kernel/hmp/load_avg_period_ms. This period is the time in ms to go from 0 to 0.5 load average while running or the time from 1 to 0.5 while sleeping. The default one used is 32 and gives the same load_avg_ratio computation than without this patch. These functions also allow to change the up and down threshold of HMP using /sys/kernel/hmp/{up,down}_threshold. Both must be between 0 and 1024. The thresholds are divided by 1024 before being compared to the load_avg_ratio. If /sys/kernel/hmp/load_avg_period_ms is 128 and /sys/kernel/hmp/up_threshold is 512, a task will be migrated to a bigger cluster after running for 128ms. Because after load_avg_period_ms the load average is 0.5 and real up_threshold us 512 / 1024 = 0.5. Signed-off-by: Olivier Cozette Signed-off-by: Chris Redpath --- arch/arm/Kconfig | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) (limited to 'arch') diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig index 8ae87dc3806..42ea637002d 100644 --- a/arch/arm/Kconfig +++ b/arch/arm/Kconfig @@ -1629,6 +1629,29 @@ config HMP_SLOW_CPU_MASK Specify the cpuids of the slow CPUs in the system as a list string, e.g. cpuid 0+1 should be specified as 0-1. +config HMP_VARIABLE_SCALE + bool "Allows changing the load tracking scale through sysfs" + depends on SCHED_HMP + help + When turned on, this option exports the thresholds and load average + period value for the load tracking patches through sysfs. + The values can be modified to change the rate of load accumulation + and the thresholds used for HMP migration. + The load_avg_period_ms is the time in ms to reach a load average of + 0.5 for an idle task of 0 load average ratio that start a busy loop. + The up_threshold and down_threshold is the value to go to a faster + CPU or to go back to a slower cpu. + The {up,down}_threshold are devided by 1024 before being compared + to the load average. + For examples, with load_avg_period_ms = 128 and up_threshold = 512, + a running task with a load of 0 will be migrated to a bigger CPU after + 128ms, because after 128ms its load_avg_ratio is 0.5 and the real + up_threshold is 0.5. + This patch has the same behavior as changing the Y of the load + average computation to + (1002/1024)^(LOAD_AVG_PERIOD/load_avg_period_ms) + but it remove intermadiate overflows in computation. + config HAVE_ARM_SCU bool help -- cgit v1.2.3 From ee74021b31619243c350396d721732ca38dbd8a4 Mon Sep 17 00:00:00 2001 From: Chris Redpath Date: Fri, 16 Nov 2012 10:03:00 +0000 Subject: ARM: Experimental Frequency-Invariant Load Scaling Patch Evaluation Patch to investigate using load as a representation of the amount of POTENTIAL cpu compute capacity used rather than a representation of the CURRENT cpu compute capacity. If CPUFreq is enabled, scales load in accordance with frequency. Powersave/performance CPUFreq governors are detected and scaling is disabled while these governors are in use. This is because when a single-frequency governor is in use, potential CPU capacity is static. So long as the governors and CPUFreq subsystem correctly report the frequencies available, the scaling should self tune. Adds an additional file to sysfs to allow this feature to be disabled for experimentation. /sys/kernel/hmp/frequency_invariant_load_scale write 0 to disable, 1 to enable. Signed-off-by: Chris Redpath --- arch/arm/Kconfig | 15 +++++++++++++++ 1 file changed, 15 insertions(+) (limited to 'arch') diff --git a/arch/arm/Kconfig b/arch/arm/Kconfig index 42ea637002d..7b5392d14dc 100644 --- a/arch/arm/Kconfig +++ b/arch/arm/Kconfig @@ -1652,6 +1652,21 @@ config HMP_VARIABLE_SCALE (1002/1024)^(LOAD_AVG_PERIOD/load_avg_period_ms) but it remove intermadiate overflows in computation. +config HMP_FREQUENCY_INVARIANT_SCALE + bool "(EXPERIMENTAL) Frequency-Invariant Tracked Load for HMP" + depends on HMP_VARIABLE_SCALE && CPU_FREQ + help + Scales the current load contribution in line with the frequency + of the CPU that the task was executed on. + In this version, we use a simple linear scale derived from the + maximum frequency reported by CPUFreq. + Restricting tracked load to be scaled by the CPU's frequency + represents the consumption of possible compute capacity + (rather than consumption of actual instantaneous capacity as + normal) and allows the HMP migration's simple threshold + migration strategy to interact more predictably with CPUFreq's + asynchronous compute capacity changes. + config HAVE_ARM_SCU bool help -- cgit v1.2.3