sched: core-balancer v2
Subsystems (2)
cover sched: core-balancer v2
Here is an update to the core-balancer previously discussed here
http://lkml.org/lkml/2008/5/12/260
Changes since v1:
1) Fixed a memory allocation error pointed out by Suresh Siddha
2) Implemented a suggestion by Suresh to only assign core-balancers to SMP or NUMA domains (i.e. exclude HT/MC domains)
3) Fixed several small bugs and misc cleanups
Comments/feedback welcome!
Regards,
-Greg
RFC PATCH 1/3 sched: create sched_balancer container for sched_groups
We want to add multiple sched_group balancing domains per sched_domains (later in the series), so we split up the current logic to make it more fine grained. This patch does not alter the general logic at all. However, it does move the initialization of some of the fields to runtime instead of declared statically in topology.h
Signed-off-by Gregory Haskins <[email protected]>
---
include/asm-ia64/topology.h | 6 -- include/asm-mips/mach-ip27/topology.h | 3 - include/asm-powerpc/topology.h | 3 - include/asm-sh/topology.h | 3 - include/asm-sparc64/topology.h | 2 - include/asm-x86/topology.h | 2 - include/linux/sched.h | 15 +++- include/linux/topology.h | 8 -- kernel/sched.c | 125 +++++++++++++++++++++------------ 9 files changed, 89 insertions(+), 78 deletions(-)
include/asm-ia64/topology.h +0 -6
@@ -75,9 +75,6 @@ void build_cpu_to_node_map(void); | SD_BALANCE_NEWIDLE \ | SD_BALANCE_EXEC \ | SD_WAKE_AFFINE, \ - .last_balance = jiffies, \ - .balance_interval = 1, \ - .nr_balance_failed = 0, \ }/* sched_domains SD_NODE_INIT for IA64 NUMA machines */
@@ -101,9 +98,6 @@ void build_cpu_to_node_map(void); | SD_BALANCE_FORK \ | SD_SERIALIZE \ | SD_WAKE_BALANCE, \ - .last_balance = jiffies, \ - .balance_interval = 64, \ - .nr_balance_failed = 0, \ }#endif /* CONFIG_NUMA */
include/asm-mips/mach-ip27/topology.h +0 -3
@@ -49,9 +49,6 @@ extern unsigned char __node_distances[MAX_COMPACT_NODES][MAX_COMPACT_NODES]; .flags = SD_LOAD_BALANCE \ | SD_BALANCE_EXEC \ | SD_WAKE_BALANCE, \ - .last_balance = jiffies, \ - .balance_interval = 1, \ - .nr_balance_failed = 0, \ }#include <asm-generic/topology.h>
include/asm-powerpc/topology.h +0 -3
@@ -67,9 +67,6 @@ static inline int pcibus_to_node(struct pci_bus *bus) | SD_WAKE_IDLE \ | SD_SERIALIZE \ | SD_WAKE_BALANCE, \ - .last_balance = jiffies, \ - .balance_interval = 1, \ - .nr_balance_failed = 0, \ }extern void __init dump_numa_cpu_topology (void );
include/asm-sh/topology.h +0 -3
@@ -24,9 +24,6 @@ | SD_BALANCE_EXEC \ | SD_SERIALIZE \ | SD_WAKE_BALANCE, \ - .last_balance = jiffies, \ - .balance_interval = 1, \ - .nr_balance_failed = 0, \ }#endif
include/asm-sparc64/topology.h +0 -2
@@ -62,8 +62,6 @@ static inline int pcibus_to_node(struct pci_bus *pbus) | SD_BALANCE_EXEC \ | SD_SERIALIZE \ | SD_WAKE_BALANCE, \ - .last_balance = jiffies, \ - .balance_interval = 1, \ }#else /* CONFIG_NUMA */
include/asm-x86/topology.h +0 -2
@@ -166,8 +166,6 @@ extern unsigned long node_remap_size[]; | SD_BALANCE_FORK \ | SD_SERIALIZE \ | SD_WAKE_BALANCE, \ - .last_balance = jiffies, \ - .balance_interval = 1, \ }#ifdef CONFIG_X86_64_ACPI_NUMA
include/linux/sched.h +10 -5
@@ -762,11 +762,18 @@ struct sched_domain_attr { .relax_domain_level = -1, \ } +struct sched_balancer { +struct sched_group *groups; +unsigned long last_exec;/* init to jiffies. units in jiffies */ +unsigned long interval;/* initialise to 1. units in ms. */ +unsigned long *interval_reset;/* value to reset interval to */ +unsigned int nr_failed;/* initialise to 0 */ +}; +struct sched_domain {/* These fields must be setup */ struct sched_domain *parent;/* top domain must be null terminated */ struct sched_domain *child;/* bottom domain must be null terminated */ -struct sched_group *groups;/* the balancing groups of the domain */ cpumask_t span;/* span of all CPUs in this domain */ int first_cpu;/* cache of the first cpu in this domain */ unsigned long min_interval;/* Minimum balance interval ms */
@@ -782,10 +789,8 @@ struct sched_domain {int flags;/* See SD_* */ enum sched_domain_level level; -/* Runtime fields. */ -unsigned long last_balance;/* init to jiffies. units in jiffies */ -unsigned int balance_interval;/* initialise to 1. units in ms. */ -unsigned int nr_balance_failed;/* initialise to 0 */ +/* Balancer data */ +struct sched_balancer group_balancer;#ifdef CONFIG_SCHEDSTATS /* load_balance() stats */
include/linux/topology.h +0 -8
@@ -101,8 +101,6 @@ void arch_update_cpu_topology(void); | SD_WAKE_AFFINE \ | SD_WAKE_IDLE \ | SD_SHARE_CPUPOWER, \ - .last_balance = jiffies, \ - .balance_interval = 1, \ }#endif #endif /* CONFIG_SCHED_SMT */
@@ -126,8 +124,6 @@ void arch_update_cpu_topology(void); | SD_WAKE_AFFINE \ | SD_SHARE_PKG_RESOURCES\ | BALANCE_FOR_MC_POWER, \ - .last_balance = jiffies, \ - .balance_interval = 1, \ }#endif #endif /* CONFIG_SCHED_MC */
@@ -151,8 +147,6 @@ void arch_update_cpu_topology(void); | SD_BALANCE_EXEC \ | SD_WAKE_AFFINE \ | BALANCE_FOR_PKG_POWER,\ - .last_balance = jiffies, \ - .balance_interval = 1, \ }#endif
@@ -167,8 +161,6 @@ void arch_update_cpu_topology(void); .idle_idx = 3, \ .flags = SD_LOAD_BALANCE \ | SD_SERIALIZE, \ - .last_balance = jiffies, \ - .balance_interval = 64, \ }#ifdef CONFIG_NUMA
kernel/sched.c +79 -46
366 lines not on this page · raw message
RFC PATCH 2/3 sched: pass specific sched_balancer to functions
In reply to Gregory HaskinsInstead of assuming sd->group_balancer.groups is the intended group. We will use this later in the series to introduce alternate balancers.
Signed-off-by Gregory Haskins <[email protected]>
---
kernel/sched.c | 21 ++++++++++++--------- 1 files changed, 12 insertions(+), 9 deletions(-)
kernel/sched.c +12 -9
@@ -3288,11 +3288,12 @@ static int move_one_task(struct rq *this_rq, int this_cpu, struct rq *busiest,* should be moved to restore balance via the imbalance parameter. */ static struct sched_group * -find_busiest_group (struct sched_domain *sd,int this_cpu, +find_busiest_group (struct sched_domain *sd,struct sched_balancer *balancer, +int this_cpu,unsigned long *imbalance,enum cpu_idle_type idle,int *sd_idle,const cpumask_t *cpus,int *balance) { -struct sched_group *first_group = sd->group_balancer.groups; +struct sched_group *first_group = balancer->groups;struct sched_group *busiest =NULL , *this =NULL , *group = first_group;unsigned long max_load, avg_load, total_load, this_load, total_pwr;unsigned long max_pull;
@@ -3630,10 +3631,11 @@ find_busiest_queue(struct sched_group *group, enum cpu_idle_type idle,* tasks if there is an imbalance. */ static int load_balance (int this_cpu,struct rq *this_rq, -struct sched_domain *sd,enum cpu_idle_type idle, +struct sched_domain *sd, +struct sched_balancer *balancer, +enum cpu_idle_type idle,int *balance,cpumask_t *cpus) { -struct sched_balancer *balancer = &sd->group_balancer;int ld_moved, all_pinned =0 , active_balance =0 , sd_idle =0 ;struct sched_group *group;unsigned long imbalance;
@@ -3658,8 +3660,8 @@ static int load_balance(int this_cpu, struct rq *this_rq,schedstat_inc (sd, lb_count[idle]); redo: - group =find_busiest_group (sd, this_cpu, &imbalance, idle, &sd_idle, - cpus, balance); + group =find_busiest_group (sd, balancer, this_cpu, &imbalance, idle, + &sd_idle, cpus, balance);if (*balance ==0 ) goto out_balanced;
@@ -3819,8 +3821,8 @@ load_balance_newidle(int this_cpu, struct rq *this_rq, struct sched_domain *sd,schedstat_inc (sd, lb_count[CPU_NEWLY_IDLE ]); redo: - group =find_busiest_group (sd, this_cpu, &imbalance,CPU_NEWLY_IDLE , - &sd_idle, cpus,NULL ); + group =find_busiest_group (sd, balancer, this_cpu, &imbalance, +CPU_NEWLY_IDLE , &sd_idle, cpus,NULL );if (!group) {schedstat_inc (sd, lb_nobusyg[CPU_NEWLY_IDLE ]); goto out_balanced;
@@ -4082,7 +4084,8 @@ static void rebalance_domains(int cpu, enum cpu_idle_type idle) }if (time_after_eq (jiffies, balancer->last_exec + interval)) { -if (load_balance (cpu, rq, sd, idle, &balance, &tmp)) { +if (load_balance (cpu, rq, sd, balancer, + idle, &balance, &tmp)) {/* * We've pulled tasks over so either we're no * longer idle, or one of our SMT siblings is
RFC PATCH 3/3 sched: add a per-core balancer group
In reply to Gregory HaskinsThe current scheduler balances SCHED_OTHER tasks based on a hierarchy of sched_domains and sched_groups as dictated by the physical cache/node topology of the hardware. This policy leads to the overall optimal balancing solution, but leaves a hole under certain circumstances (see Documentation/scheduler/core_balancer.txt for more details).
This patch adds the concept of a new per-core grouping at each domain-level to address the shortcomings in the group_balancer.
Signed-off-by Gregory Haskins <[email protected]>
---
Documentation/scheduler/core_balancer.txt | 69 +++++++++++++ include/linux/sched.h | 2 kernel/sched.c | 149 +++++++++++++++++++++-------- 3 files changed, 180 insertions(+), 40 deletions(-)
Documentation/scheduler/core_balancer.txt new file +69 -0
@@ -0,0 +1,69 @@ +Core Balancing +---------------------- + +The standard group_balancer manages SCHED_OTHER tasks based on a hierarchy +of sched_domains and sched_groups as dictated by the physical cache/node +topology of the hardware. Each group may contain one or more cores which +have a specific relationship to other members of the group. Balancing +is always performed on an inter-group basis. + +For example, consider a quad-core, dual socket Intel Xeon system. It has +a total of 8 cores across one logical NUMA node, with a cache shared +between cores [0,2], [1,3], [4,6], [5,7]. From a sched_domain/group +perspective on core 0, this looks like the following: + +domain-0: (MC) + span: 0x5 + groups = 2 -> [0], [2] + domain-1: (SMP) + span: 0xff + groups = 4 -> [0,2], [1,3], [4,6], [5,7] + domain-2: (NUMA) + span: 0xff + groups = 1 -> [0-7] + +Recall that balancing is always inter-group, and will get more aggressive +in the lower domains than the higher ones. The balancing logic will +attempt to balance between [0],[2] first, [0,2], [1,3], [4,6], [5,7] +second, and [0-7] last. Note that since domain-2 only consists of 1 +group, it will never result in a balance decision since there must be +at least two groups to consider. + +This layout is quite logical. The idea is that [0], and [2] can +balance between each other aggresively in a very efficient manner +since they share a cache. Once the load is equalized between two +cache-peers, domain-1 can spread the load out between the other +peer-groups. This represents a pretty good way to structure the +balancing operations. + +However, there is one slight problem with the group_balancer: Since we +always balance inter-group, intra-group imbalances may result in +suboptimal behavior if we hit the condition where lower-level domains +(domain-0 in this example) are ineffective. This condition can arise +whenever a domain-level imbalance cannot be resolved such that the group +has a high aggregate load rating, yet some cores are relatively idle. + +For example, if a core has a large but affined load, or otherwise +untouchable tasks (e.g. RT tasks), SCHED_OTHER will not be able to +equalize the load. The net result is that one or more members of the +group may remain relatively unloaded, while the load rating for the +entire group is high. The higher layer domains will only consider the +group as a whole, and the lower level domains are left powerless to +equalize the vacuum. + +To address this concern, core_balancer adds the concept of a new grouping +of cores at each domain-level: a per-core grouping (each core in its own +unique group). This "core_balancer" group is configured to run much less +aggressively than its topologically relevant brother: "group_balancer". +Core_balancer will sweep through the cores every so often, correcting +intra-group vacuums left over from lower level domains. In most cases, +the group_balancer should have already established equilibrium, therefore +benefiting from the hardwares natural affinity hierarchy. In the cases +where it cannot achieve equilibrium, the core_balancer tries to take it +one step closer. + +By default, group_balancer runs at sd->min_interval, whereas +core_balancer starts at sd->max_interval (both of which will respond +to dynamic programming). Both will employ a multiplicative backoff +algorithm when faced with repeated migration failure. +
include/linux/sched.h +2 -0
@@ -715,6 +715,7 @@ enum cpu_idle_type {#define SD_SHARE_PKG_RESOURCES 512/* Domain members share cpu pkg resources */ #define SD_SERIALIZE 1024/* Only a single load balancing instance */ #define SD_WAKE_IDLE_FAR 2048/* Gain latency sacrificing cache hit */ +#define SD_CORE_BALANCE 4096/* Balance on a per-core basis */ #define BALANCE_FOR_MC_POWER \ (sched_smt_power_savings ? SD_POWERSAVINGS_BALANCE : 0)
@@ -791,6 +792,7 @@ struct sched_domain {/* Balancer data */ struct sched_balancer group_balancer; +struct sched_balancer core_balancer;#ifdef CONFIG_SCHEDSTATS /* load_balance() stats */
kernel/sched.c +109 -40
202 lines not on this page · raw message