diff options
Diffstat (limited to 'kernel/sched_fair.c')
-rw-r--r-- | kernel/sched_fair.c | 1699 |
1 files changed, 1644 insertions, 55 deletions
diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c index 8fe7ee81c552..3e1fd96c6cf9 100644 --- a/kernel/sched_fair.c +++ b/kernel/sched_fair.c | |||
@@ -1053,7 +1053,8 @@ static inline void hrtick_update(struct rq *rq) | |||
1053 | * increased. Here we update the fair scheduling stats and | 1053 | * increased. Here we update the fair scheduling stats and |
1054 | * then put the task into the rbtree: | 1054 | * then put the task into the rbtree: |
1055 | */ | 1055 | */ |
1056 | static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup) | 1056 | static void |
1057 | enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup, bool head) | ||
1057 | { | 1058 | { |
1058 | struct cfs_rq *cfs_rq; | 1059 | struct cfs_rq *cfs_rq; |
1059 | struct sched_entity *se = &p->se; | 1060 | struct sched_entity *se = &p->se; |
@@ -1815,57 +1816,164 @@ static void put_prev_task_fair(struct rq *rq, struct task_struct *prev) | |||
1815 | */ | 1816 | */ |
1816 | 1817 | ||
1817 | /* | 1818 | /* |
1818 | * Load-balancing iterator. Note: while the runqueue stays locked | 1819 | * pull_task - move a task from a remote runqueue to the local runqueue. |
1819 | * during the whole iteration, the current task might be | 1820 | * Both runqueues must be locked. |
1820 | * dequeued so the iterator has to be dequeue-safe. Here we | ||
1821 | * achieve that by always pre-iterating before returning | ||
1822 | * the current task: | ||
1823 | */ | 1821 | */ |
1824 | static struct task_struct * | 1822 | static void pull_task(struct rq *src_rq, struct task_struct *p, |
1825 | __load_balance_iterator(struct cfs_rq *cfs_rq, struct list_head *next) | 1823 | struct rq *this_rq, int this_cpu) |
1826 | { | 1824 | { |
1827 | struct task_struct *p = NULL; | 1825 | deactivate_task(src_rq, p, 0); |
1828 | struct sched_entity *se; | 1826 | set_task_cpu(p, this_cpu); |
1827 | activate_task(this_rq, p, 0); | ||
1828 | check_preempt_curr(this_rq, p, 0); | ||
1829 | } | ||
1829 | 1830 | ||
1830 | if (next == &cfs_rq->tasks) | 1831 | /* |
1831 | return NULL; | 1832 | * can_migrate_task - may task p from runqueue rq be migrated to this_cpu? |
1833 | */ | ||
1834 | static | ||
1835 | int can_migrate_task(struct task_struct *p, struct rq *rq, int this_cpu, | ||
1836 | struct sched_domain *sd, enum cpu_idle_type idle, | ||
1837 | int *all_pinned) | ||
1838 | { | ||
1839 | int tsk_cache_hot = 0; | ||
1840 | /* | ||
1841 | * We do not migrate tasks that are: | ||
1842 | * 1) running (obviously), or | ||
1843 | * 2) cannot be migrated to this CPU due to cpus_allowed, or | ||
1844 | * 3) are cache-hot on their current CPU. | ||
1845 | */ | ||
1846 | if (!cpumask_test_cpu(this_cpu, &p->cpus_allowed)) { | ||
1847 | schedstat_inc(p, se.nr_failed_migrations_affine); | ||
1848 | return 0; | ||
1849 | } | ||
1850 | *all_pinned = 0; | ||
1832 | 1851 | ||
1833 | se = list_entry(next, struct sched_entity, group_node); | 1852 | if (task_running(rq, p)) { |
1834 | p = task_of(se); | 1853 | schedstat_inc(p, se.nr_failed_migrations_running); |
1835 | cfs_rq->balance_iterator = next->next; | 1854 | return 0; |
1855 | } | ||
1836 | 1856 | ||
1837 | return p; | 1857 | /* |
1838 | } | 1858 | * Aggressive migration if: |
1859 | * 1) task is cache cold, or | ||
1860 | * 2) too many balance attempts have failed. | ||
1861 | */ | ||
1839 | 1862 | ||
1840 | static struct task_struct *load_balance_start_fair(void *arg) | 1863 | tsk_cache_hot = task_hot(p, rq->clock, sd); |
1841 | { | 1864 | if (!tsk_cache_hot || |
1842 | struct cfs_rq *cfs_rq = arg; | 1865 | sd->nr_balance_failed > sd->cache_nice_tries) { |
1866 | #ifdef CONFIG_SCHEDSTATS | ||
1867 | if (tsk_cache_hot) { | ||
1868 | schedstat_inc(sd, lb_hot_gained[idle]); | ||
1869 | schedstat_inc(p, se.nr_forced_migrations); | ||
1870 | } | ||
1871 | #endif | ||
1872 | return 1; | ||
1873 | } | ||
1843 | 1874 | ||
1844 | return __load_balance_iterator(cfs_rq, cfs_rq->tasks.next); | 1875 | if (tsk_cache_hot) { |
1876 | schedstat_inc(p, se.nr_failed_migrations_hot); | ||
1877 | return 0; | ||
1878 | } | ||
1879 | return 1; | ||
1845 | } | 1880 | } |
1846 | 1881 | ||
1847 | static struct task_struct *load_balance_next_fair(void *arg) | 1882 | /* |
1883 | * move_one_task tries to move exactly one task from busiest to this_rq, as | ||
1884 | * part of active balancing operations within "domain". | ||
1885 | * Returns 1 if successful and 0 otherwise. | ||
1886 | * | ||
1887 | * Called with both runqueues locked. | ||
1888 | */ | ||
1889 | static int | ||
1890 | move_one_task(struct rq *this_rq, int this_cpu, struct rq *busiest, | ||
1891 | struct sched_domain *sd, enum cpu_idle_type idle) | ||
1848 | { | 1892 | { |
1849 | struct cfs_rq *cfs_rq = arg; | 1893 | struct task_struct *p, *n; |
1894 | struct cfs_rq *cfs_rq; | ||
1895 | int pinned = 0; | ||
1896 | |||
1897 | for_each_leaf_cfs_rq(busiest, cfs_rq) { | ||
1898 | list_for_each_entry_safe(p, n, &cfs_rq->tasks, se.group_node) { | ||
1899 | |||
1900 | if (!can_migrate_task(p, busiest, this_cpu, | ||
1901 | sd, idle, &pinned)) | ||
1902 | continue; | ||
1850 | 1903 | ||
1851 | return __load_balance_iterator(cfs_rq, cfs_rq->balance_iterator); | 1904 | pull_task(busiest, p, this_rq, this_cpu); |
1905 | /* | ||
1906 | * Right now, this is only the second place pull_task() | ||
1907 | * is called, so we can safely collect pull_task() | ||
1908 | * stats here rather than inside pull_task(). | ||
1909 | */ | ||
1910 | schedstat_inc(sd, lb_gained[idle]); | ||
1911 | return 1; | ||
1912 | } | ||
1913 | } | ||
1914 | |||
1915 | return 0; | ||
1852 | } | 1916 | } |
1853 | 1917 | ||
1854 | static unsigned long | 1918 | static unsigned long |
1855 | __load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest, | 1919 | balance_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest, |
1856 | unsigned long max_load_move, struct sched_domain *sd, | 1920 | unsigned long max_load_move, struct sched_domain *sd, |
1857 | enum cpu_idle_type idle, int *all_pinned, int *this_best_prio, | 1921 | enum cpu_idle_type idle, int *all_pinned, |
1858 | struct cfs_rq *cfs_rq) | 1922 | int *this_best_prio, struct cfs_rq *busiest_cfs_rq) |
1859 | { | 1923 | { |
1860 | struct rq_iterator cfs_rq_iterator; | 1924 | int loops = 0, pulled = 0, pinned = 0; |
1925 | long rem_load_move = max_load_move; | ||
1926 | struct task_struct *p, *n; | ||
1861 | 1927 | ||
1862 | cfs_rq_iterator.start = load_balance_start_fair; | 1928 | if (max_load_move == 0) |
1863 | cfs_rq_iterator.next = load_balance_next_fair; | 1929 | goto out; |
1864 | cfs_rq_iterator.arg = cfs_rq; | ||
1865 | 1930 | ||
1866 | return balance_tasks(this_rq, this_cpu, busiest, | 1931 | pinned = 1; |
1867 | max_load_move, sd, idle, all_pinned, | 1932 | |
1868 | this_best_prio, &cfs_rq_iterator); | 1933 | list_for_each_entry_safe(p, n, &busiest_cfs_rq->tasks, se.group_node) { |
1934 | if (loops++ > sysctl_sched_nr_migrate) | ||
1935 | break; | ||
1936 | |||
1937 | if ((p->se.load.weight >> 1) > rem_load_move || | ||
1938 | !can_migrate_task(p, busiest, this_cpu, sd, idle, &pinned)) | ||
1939 | continue; | ||
1940 | |||
1941 | pull_task(busiest, p, this_rq, this_cpu); | ||
1942 | pulled++; | ||
1943 | rem_load_move -= p->se.load.weight; | ||
1944 | |||
1945 | #ifdef CONFIG_PREEMPT | ||
1946 | /* | ||
1947 | * NEWIDLE balancing is a source of latency, so preemptible | ||
1948 | * kernels will stop after the first task is pulled to minimize | ||
1949 | * the critical section. | ||
1950 | */ | ||
1951 | if (idle == CPU_NEWLY_IDLE) | ||
1952 | break; | ||
1953 | #endif | ||
1954 | |||
1955 | /* | ||
1956 | * We only want to steal up to the prescribed amount of | ||
1957 | * weighted load. | ||
1958 | */ | ||
1959 | if (rem_load_move <= 0) | ||
1960 | break; | ||
1961 | |||
1962 | if (p->prio < *this_best_prio) | ||
1963 | *this_best_prio = p->prio; | ||
1964 | } | ||
1965 | out: | ||
1966 | /* | ||
1967 | * Right now, this is one of only two places pull_task() is called, | ||
1968 | * so we can safely collect pull_task() stats here rather than | ||
1969 | * inside pull_task(). | ||
1970 | */ | ||
1971 | schedstat_add(sd, lb_gained[idle], pulled); | ||
1972 | |||
1973 | if (all_pinned) | ||
1974 | *all_pinned = pinned; | ||
1975 | |||
1976 | return max_load_move - rem_load_move; | ||
1869 | } | 1977 | } |
1870 | 1978 | ||
1871 | #ifdef CONFIG_FAIR_GROUP_SCHED | 1979 | #ifdef CONFIG_FAIR_GROUP_SCHED |
@@ -1897,9 +2005,9 @@ load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest, | |||
1897 | rem_load = (u64)rem_load_move * busiest_weight; | 2005 | rem_load = (u64)rem_load_move * busiest_weight; |
1898 | rem_load = div_u64(rem_load, busiest_h_load + 1); | 2006 | rem_load = div_u64(rem_load, busiest_h_load + 1); |
1899 | 2007 | ||
1900 | moved_load = __load_balance_fair(this_rq, this_cpu, busiest, | 2008 | moved_load = balance_tasks(this_rq, this_cpu, busiest, |
1901 | rem_load, sd, idle, all_pinned, this_best_prio, | 2009 | rem_load, sd, idle, all_pinned, this_best_prio, |
1902 | tg->cfs_rq[busiest_cpu]); | 2010 | busiest_cfs_rq); |
1903 | 2011 | ||
1904 | if (!moved_load) | 2012 | if (!moved_load) |
1905 | continue; | 2013 | continue; |
@@ -1922,35 +2030,1509 @@ load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest, | |||
1922 | struct sched_domain *sd, enum cpu_idle_type idle, | 2030 | struct sched_domain *sd, enum cpu_idle_type idle, |
1923 | int *all_pinned, int *this_best_prio) | 2031 | int *all_pinned, int *this_best_prio) |
1924 | { | 2032 | { |
1925 | return __load_balance_fair(this_rq, this_cpu, busiest, | 2033 | return balance_tasks(this_rq, this_cpu, busiest, |
1926 | max_load_move, sd, idle, all_pinned, | 2034 | max_load_move, sd, idle, all_pinned, |
1927 | this_best_prio, &busiest->cfs); | 2035 | this_best_prio, &busiest->cfs); |
1928 | } | 2036 | } |
1929 | #endif | 2037 | #endif |
1930 | 2038 | ||
1931 | static int | 2039 | /* |
1932 | move_one_task_fair(struct rq *this_rq, int this_cpu, struct rq *busiest, | 2040 | * move_tasks tries to move up to max_load_move weighted load from busiest to |
1933 | struct sched_domain *sd, enum cpu_idle_type idle) | 2041 | * this_rq, as part of a balancing operation within domain "sd". |
2042 | * Returns 1 if successful and 0 otherwise. | ||
2043 | * | ||
2044 | * Called with both runqueues locked. | ||
2045 | */ | ||
2046 | static int move_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest, | ||
2047 | unsigned long max_load_move, | ||
2048 | struct sched_domain *sd, enum cpu_idle_type idle, | ||
2049 | int *all_pinned) | ||
1934 | { | 2050 | { |
1935 | struct cfs_rq *busy_cfs_rq; | 2051 | unsigned long total_load_moved = 0, load_moved; |
1936 | struct rq_iterator cfs_rq_iterator; | 2052 | int this_best_prio = this_rq->curr->prio; |
1937 | 2053 | ||
1938 | cfs_rq_iterator.start = load_balance_start_fair; | 2054 | do { |
1939 | cfs_rq_iterator.next = load_balance_next_fair; | 2055 | load_moved = load_balance_fair(this_rq, this_cpu, busiest, |
2056 | max_load_move - total_load_moved, | ||
2057 | sd, idle, all_pinned, &this_best_prio); | ||
1940 | 2058 | ||
1941 | for_each_leaf_cfs_rq(busiest, busy_cfs_rq) { | 2059 | total_load_moved += load_moved; |
2060 | |||
2061 | #ifdef CONFIG_PREEMPT | ||
1942 | /* | 2062 | /* |
1943 | * pass busy_cfs_rq argument into | 2063 | * NEWIDLE balancing is a source of latency, so preemptible |
1944 | * load_balance_[start|next]_fair iterators | 2064 | * kernels will stop after the first task is pulled to minimize |
2065 | * the critical section. | ||
1945 | */ | 2066 | */ |
1946 | cfs_rq_iterator.arg = busy_cfs_rq; | 2067 | if (idle == CPU_NEWLY_IDLE && this_rq->nr_running) |
1947 | if (iter_move_one_task(this_rq, this_cpu, busiest, sd, idle, | 2068 | break; |
1948 | &cfs_rq_iterator)) | 2069 | |
1949 | return 1; | 2070 | if (raw_spin_is_contended(&this_rq->lock) || |
2071 | raw_spin_is_contended(&busiest->lock)) | ||
2072 | break; | ||
2073 | #endif | ||
2074 | } while (load_moved && max_load_move > total_load_moved); | ||
2075 | |||
2076 | return total_load_moved > 0; | ||
2077 | } | ||
2078 | |||
2079 | /********** Helpers for find_busiest_group ************************/ | ||
2080 | /* | ||
2081 | * sd_lb_stats - Structure to store the statistics of a sched_domain | ||
2082 | * during load balancing. | ||
2083 | */ | ||
2084 | struct sd_lb_stats { | ||
2085 | struct sched_group *busiest; /* Busiest group in this sd */ | ||
2086 | struct sched_group *this; /* Local group in this sd */ | ||
2087 | unsigned long total_load; /* Total load of all groups in sd */ | ||
2088 | unsigned long total_pwr; /* Total power of all groups in sd */ | ||
2089 | unsigned long avg_load; /* Average load across all groups in sd */ | ||
2090 | |||
2091 | /** Statistics of this group */ | ||
2092 | unsigned long this_load; | ||
2093 | unsigned long this_load_per_task; | ||
2094 | unsigned long this_nr_running; | ||
2095 | |||
2096 | /* Statistics of the busiest group */ | ||
2097 | unsigned long max_load; | ||
2098 | unsigned long busiest_load_per_task; | ||
2099 | unsigned long busiest_nr_running; | ||
2100 | unsigned long busiest_group_capacity; | ||
2101 | |||
2102 | int group_imb; /* Is there imbalance in this sd */ | ||
2103 | #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT) | ||
2104 | int power_savings_balance; /* Is powersave balance needed for this sd */ | ||
2105 | struct sched_group *group_min; /* Least loaded group in sd */ | ||
2106 | struct sched_group *group_leader; /* Group which relieves group_min */ | ||
2107 | unsigned long min_load_per_task; /* load_per_task in group_min */ | ||
2108 | unsigned long leader_nr_running; /* Nr running of group_leader */ | ||
2109 | unsigned long min_nr_running; /* Nr running of group_min */ | ||
2110 | #endif | ||
2111 | }; | ||
2112 | |||
2113 | /* | ||
2114 | * sg_lb_stats - stats of a sched_group required for load_balancing | ||
2115 | */ | ||
2116 | struct sg_lb_stats { | ||
2117 | unsigned long avg_load; /*Avg load across the CPUs of the group */ | ||
2118 | unsigned long group_load; /* Total load over the CPUs of the group */ | ||
2119 | unsigned long sum_nr_running; /* Nr tasks running in the group */ | ||
2120 | unsigned long sum_weighted_load; /* Weighted load of group's tasks */ | ||
2121 | unsigned long group_capacity; | ||
2122 | int group_imb; /* Is there an imbalance in the group ? */ | ||
2123 | }; | ||
2124 | |||
2125 | /** | ||
2126 | * group_first_cpu - Returns the first cpu in the cpumask of a sched_group. | ||
2127 | * @group: The group whose first cpu is to be returned. | ||
2128 | */ | ||
2129 | static inline unsigned int group_first_cpu(struct sched_group *group) | ||
2130 | { | ||
2131 | return cpumask_first(sched_group_cpus(group)); | ||
2132 | } | ||
2133 | |||
2134 | /** | ||
2135 | * get_sd_load_idx - Obtain the load index for a given sched domain. | ||
2136 | * @sd: The sched_domain whose load_idx is to be obtained. | ||
2137 | * @idle: The Idle status of the CPU for whose sd load_icx is obtained. | ||
2138 | */ | ||
2139 | static inline int get_sd_load_idx(struct sched_domain *sd, | ||
2140 | enum cpu_idle_type idle) | ||
2141 | { | ||
2142 | int load_idx; | ||
2143 | |||
2144 | switch (idle) { | ||
2145 | case CPU_NOT_IDLE: | ||
2146 | load_idx = sd->busy_idx; | ||
2147 | break; | ||
2148 | |||
2149 | case CPU_NEWLY_IDLE: | ||
2150 | load_idx = sd->newidle_idx; | ||
2151 | break; | ||
2152 | default: | ||
2153 | load_idx = sd->idle_idx; | ||
2154 | break; | ||
1950 | } | 2155 | } |
1951 | 2156 | ||
2157 | return load_idx; | ||
2158 | } | ||
2159 | |||
2160 | |||
2161 | #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT) | ||
2162 | /** | ||
2163 | * init_sd_power_savings_stats - Initialize power savings statistics for | ||
2164 | * the given sched_domain, during load balancing. | ||
2165 | * | ||
2166 | * @sd: Sched domain whose power-savings statistics are to be initialized. | ||
2167 | * @sds: Variable containing the statistics for sd. | ||
2168 | * @idle: Idle status of the CPU at which we're performing load-balancing. | ||
2169 | */ | ||
2170 | static inline void init_sd_power_savings_stats(struct sched_domain *sd, | ||
2171 | struct sd_lb_stats *sds, enum cpu_idle_type idle) | ||
2172 | { | ||
2173 | /* | ||
2174 | * Busy processors will not participate in power savings | ||
2175 | * balance. | ||
2176 | */ | ||
2177 | if (idle == CPU_NOT_IDLE || !(sd->flags & SD_POWERSAVINGS_BALANCE)) | ||
2178 | sds->power_savings_balance = 0; | ||
2179 | else { | ||
2180 | sds->power_savings_balance = 1; | ||
2181 | sds->min_nr_running = ULONG_MAX; | ||
2182 | sds->leader_nr_running = 0; | ||
2183 | } | ||
2184 | } | ||
2185 | |||
2186 | /** | ||
2187 | * update_sd_power_savings_stats - Update the power saving stats for a | ||
2188 | * sched_domain while performing load balancing. | ||
2189 | * | ||
2190 | * @group: sched_group belonging to the sched_domain under consideration. | ||
2191 | * @sds: Variable containing the statistics of the sched_domain | ||
2192 | * @local_group: Does group contain the CPU for which we're performing | ||
2193 | * load balancing ? | ||
2194 | * @sgs: Variable containing the statistics of the group. | ||
2195 | */ | ||
2196 | static inline void update_sd_power_savings_stats(struct sched_group *group, | ||
2197 | struct sd_lb_stats *sds, int local_group, struct sg_lb_stats *sgs) | ||
2198 | { | ||
2199 | |||
2200 | if (!sds->power_savings_balance) | ||
2201 | return; | ||
2202 | |||
2203 | /* | ||
2204 | * If the local group is idle or completely loaded | ||
2205 | * no need to do power savings balance at this domain | ||
2206 | */ | ||
2207 | if (local_group && (sds->this_nr_running >= sgs->group_capacity || | ||
2208 | !sds->this_nr_running)) | ||
2209 | sds->power_savings_balance = 0; | ||
2210 | |||
2211 | /* | ||
2212 | * If a group is already running at full capacity or idle, | ||
2213 | * don't include that group in power savings calculations | ||
2214 | */ | ||
2215 | if (!sds->power_savings_balance || | ||
2216 | sgs->sum_nr_running >= sgs->group_capacity || | ||
2217 | !sgs->sum_nr_running) | ||
2218 | return; | ||
2219 | |||
2220 | /* | ||
2221 | * Calculate the group which has the least non-idle load. | ||
2222 | * This is the group from where we need to pick up the load | ||
2223 | * for saving power | ||
2224 | */ | ||
2225 | if ((sgs->sum_nr_running < sds->min_nr_running) || | ||
2226 | (sgs->sum_nr_running == sds->min_nr_running && | ||
2227 | group_first_cpu(group) > group_first_cpu(sds->group_min))) { | ||
2228 | sds->group_min = group; | ||
2229 | sds->min_nr_running = sgs->sum_nr_running; | ||
2230 | sds->min_load_per_task = sgs->sum_weighted_load / | ||
2231 | sgs->sum_nr_running; | ||
2232 | } | ||
2233 | |||
2234 | /* | ||
2235 | * Calculate the group which is almost near its | ||
2236 | * capacity but still has some space to pick up some load | ||
2237 | * from other group and save more power | ||
2238 | */ | ||
2239 | if (sgs->sum_nr_running + 1 > sgs->group_capacity) | ||
2240 | return; | ||
2241 | |||
2242 | if (sgs->sum_nr_running > sds->leader_nr_running || | ||
2243 | (sgs->sum_nr_running == sds->leader_nr_running && | ||
2244 | group_first_cpu(group) < group_first_cpu(sds->group_leader))) { | ||
2245 | sds->group_leader = group; | ||
2246 | sds->leader_nr_running = sgs->sum_nr_running; | ||
2247 | } | ||
2248 | } | ||
2249 | |||
2250 | /** | ||
2251 | * check_power_save_busiest_group - see if there is potential for some power-savings balance | ||
2252 | * @sds: Variable containing the statistics of the sched_domain | ||
2253 | * under consideration. | ||
2254 | * @this_cpu: Cpu at which we're currently performing load-balancing. | ||
2255 | * @imbalance: Variable to store the imbalance. | ||
2256 | * | ||
2257 | * Description: | ||
2258 | * Check if we have potential to perform some power-savings balance. | ||
2259 | * If yes, set the busiest group to be the least loaded group in the | ||
2260 | * sched_domain, so that it's CPUs can be put to idle. | ||
2261 | * | ||
2262 | * Returns 1 if there is potential to perform power-savings balance. | ||
2263 | * Else returns 0. | ||
2264 | */ | ||
2265 | static inline int check_power_save_busiest_group(struct sd_lb_stats *sds, | ||
2266 | int this_cpu, unsigned long *imbalance) | ||
2267 | { | ||
2268 | if (!sds->power_savings_balance) | ||
2269 | return 0; | ||
2270 | |||
2271 | if (sds->this != sds->group_leader || | ||
2272 | sds->group_leader == sds->group_min) | ||
2273 | return 0; | ||
2274 | |||
2275 | *imbalance = sds->min_load_per_task; | ||
2276 | sds->busiest = sds->group_min; | ||
2277 | |||
2278 | return 1; | ||
2279 | |||
2280 | } | ||
2281 | #else /* CONFIG_SCHED_MC || CONFIG_SCHED_SMT */ | ||
2282 | static inline void init_sd_power_savings_stats(struct sched_domain *sd, | ||
2283 | struct sd_lb_stats *sds, enum cpu_idle_type idle) | ||
2284 | { | ||
2285 | return; | ||
2286 | } | ||
2287 | |||
2288 | static inline void update_sd_power_savings_stats(struct sched_group *group, | ||
2289 | struct sd_lb_stats *sds, int local_group, struct sg_lb_stats *sgs) | ||
2290 | { | ||
2291 | return; | ||
2292 | } | ||
2293 | |||
2294 | static inline int check_power_save_busiest_group(struct sd_lb_stats *sds, | ||
2295 | int this_cpu, unsigned long *imbalance) | ||
2296 | { | ||
1952 | return 0; | 2297 | return 0; |
1953 | } | 2298 | } |
2299 | #endif /* CONFIG_SCHED_MC || CONFIG_SCHED_SMT */ | ||
2300 | |||
2301 | |||
2302 | unsigned long default_scale_freq_power(struct sched_domain *sd, int cpu) | ||
2303 | { | ||
2304 | return SCHED_LOAD_SCALE; | ||
2305 | } | ||
2306 | |||
2307 | unsigned long __weak arch_scale_freq_power(struct sched_domain *sd, int cpu) | ||
2308 | { | ||
2309 | return default_scale_freq_power(sd, cpu); | ||
2310 | } | ||
2311 | |||
2312 | unsigned long default_scale_smt_power(struct sched_domain *sd, int cpu) | ||
2313 | { | ||
2314 | unsigned long weight = cpumask_weight(sched_domain_span(sd)); | ||
2315 | unsigned long smt_gain = sd->smt_gain; | ||
2316 | |||
2317 | smt_gain /= weight; | ||
2318 | |||
2319 | return smt_gain; | ||
2320 | } | ||
2321 | |||
2322 | unsigned long __weak arch_scale_smt_power(struct sched_domain *sd, int cpu) | ||
2323 | { | ||
2324 | return default_scale_smt_power(sd, cpu); | ||
2325 | } | ||
2326 | |||
2327 | unsigned long scale_rt_power(int cpu) | ||
2328 | { | ||
2329 | struct rq *rq = cpu_rq(cpu); | ||
2330 | u64 total, available; | ||
2331 | |||
2332 | sched_avg_update(rq); | ||
2333 | |||
2334 | total = sched_avg_period() + (rq->clock - rq->age_stamp); | ||
2335 | available = total - rq->rt_avg; | ||
2336 | |||
2337 | if (unlikely((s64)total < SCHED_LOAD_SCALE)) | ||
2338 | total = SCHED_LOAD_SCALE; | ||
2339 | |||
2340 | total >>= SCHED_LOAD_SHIFT; | ||
2341 | |||
2342 | return div_u64(available, total); | ||
2343 | } | ||
2344 | |||
2345 | static void update_cpu_power(struct sched_domain *sd, int cpu) | ||
2346 | { | ||
2347 | unsigned long weight = cpumask_weight(sched_domain_span(sd)); | ||
2348 | unsigned long power = SCHED_LOAD_SCALE; | ||
2349 | struct sched_group *sdg = sd->groups; | ||
2350 | |||
2351 | if (sched_feat(ARCH_POWER)) | ||
2352 | power *= arch_scale_freq_power(sd, cpu); | ||
2353 | else | ||
2354 | power *= default_scale_freq_power(sd, cpu); | ||
2355 | |||
2356 | power >>= SCHED_LOAD_SHIFT; | ||
2357 | |||
2358 | if ((sd->flags & SD_SHARE_CPUPOWER) && weight > 1) { | ||
2359 | if (sched_feat(ARCH_POWER)) | ||
2360 | power *= arch_scale_smt_power(sd, cpu); | ||
2361 | else | ||
2362 | power *= default_scale_smt_power(sd, cpu); | ||
2363 | |||
2364 | power >>= SCHED_LOAD_SHIFT; | ||
2365 | } | ||
2366 | |||
2367 | power *= scale_rt_power(cpu); | ||
2368 | power >>= SCHED_LOAD_SHIFT; | ||
2369 | |||
2370 | if (!power) | ||
2371 | power = 1; | ||
2372 | |||
2373 | sdg->cpu_power = power; | ||
2374 | } | ||
2375 | |||
2376 | static void update_group_power(struct sched_domain *sd, int cpu) | ||
2377 | { | ||
2378 | struct sched_domain *child = sd->child; | ||
2379 | struct sched_group *group, *sdg = sd->groups; | ||
2380 | unsigned long power; | ||
2381 | |||
2382 | if (!child) { | ||
2383 | update_cpu_power(sd, cpu); | ||
2384 | return; | ||
2385 | } | ||
2386 | |||
2387 | power = 0; | ||
2388 | |||
2389 | group = child->groups; | ||
2390 | do { | ||
2391 | power += group->cpu_power; | ||
2392 | group = group->next; | ||
2393 | } while (group != child->groups); | ||
2394 | |||
2395 | sdg->cpu_power = power; | ||
2396 | } | ||
2397 | |||
2398 | /** | ||
2399 | * update_sg_lb_stats - Update sched_group's statistics for load balancing. | ||
2400 | * @sd: The sched_domain whose statistics are to be updated. | ||
2401 | * @group: sched_group whose statistics are to be updated. | ||
2402 | * @this_cpu: Cpu for which load balance is currently performed. | ||
2403 | * @idle: Idle status of this_cpu | ||
2404 | * @load_idx: Load index of sched_domain of this_cpu for load calc. | ||
2405 | * @sd_idle: Idle status of the sched_domain containing group. | ||
2406 | * @local_group: Does group contain this_cpu. | ||
2407 | * @cpus: Set of cpus considered for load balancing. | ||
2408 | * @balance: Should we balance. | ||
2409 | * @sgs: variable to hold the statistics for this group. | ||
2410 | */ | ||
2411 | static inline void update_sg_lb_stats(struct sched_domain *sd, | ||
2412 | struct sched_group *group, int this_cpu, | ||
2413 | enum cpu_idle_type idle, int load_idx, int *sd_idle, | ||
2414 | int local_group, const struct cpumask *cpus, | ||
2415 | int *balance, struct sg_lb_stats *sgs) | ||
2416 | { | ||
2417 | unsigned long load, max_cpu_load, min_cpu_load; | ||
2418 | int i; | ||
2419 | unsigned int balance_cpu = -1, first_idle_cpu = 0; | ||
2420 | unsigned long avg_load_per_task = 0; | ||
2421 | |||
2422 | if (local_group) | ||
2423 | balance_cpu = group_first_cpu(group); | ||
2424 | |||
2425 | /* Tally up the load of all CPUs in the group */ | ||
2426 | max_cpu_load = 0; | ||
2427 | min_cpu_load = ~0UL; | ||
2428 | |||
2429 | for_each_cpu_and(i, sched_group_cpus(group), cpus) { | ||
2430 | struct rq *rq = cpu_rq(i); | ||
2431 | |||
2432 | if (*sd_idle && rq->nr_running) | ||
2433 | *sd_idle = 0; | ||
2434 | |||
2435 | /* Bias balancing toward cpus of our domain */ | ||
2436 | if (local_group) { | ||
2437 | if (idle_cpu(i) && !first_idle_cpu) { | ||
2438 | first_idle_cpu = 1; | ||
2439 | balance_cpu = i; | ||
2440 | } | ||
2441 | |||
2442 | load = target_load(i, load_idx); | ||
2443 | } else { | ||
2444 | load = source_load(i, load_idx); | ||
2445 | if (load > max_cpu_load) | ||
2446 | max_cpu_load = load; | ||
2447 | if (min_cpu_load > load) | ||
2448 | min_cpu_load = load; | ||
2449 | } | ||
2450 | |||
2451 | sgs->group_load += load; | ||
2452 | sgs->sum_nr_running += rq->nr_running; | ||
2453 | sgs->sum_weighted_load += weighted_cpuload(i); | ||
2454 | |||
2455 | } | ||
2456 | |||
2457 | /* | ||
2458 | * First idle cpu or the first cpu(busiest) in this sched group | ||
2459 | * is eligible for doing load balancing at this and above | ||
2460 | * domains. In the newly idle case, we will allow all the cpu's | ||
2461 | * to do the newly idle load balance. | ||
2462 | */ | ||
2463 | if (idle != CPU_NEWLY_IDLE && local_group && | ||
2464 | balance_cpu != this_cpu) { | ||
2465 | *balance = 0; | ||
2466 | return; | ||
2467 | } | ||
2468 | |||
2469 | update_group_power(sd, this_cpu); | ||
2470 | |||
2471 | /* Adjust by relative CPU power of the group */ | ||
2472 | sgs->avg_load = (sgs->group_load * SCHED_LOAD_SCALE) / group->cpu_power; | ||
2473 | |||
2474 | /* | ||
2475 | * Consider the group unbalanced when the imbalance is larger | ||
2476 | * than the average weight of two tasks. | ||
2477 | * | ||
2478 | * APZ: with cgroup the avg task weight can vary wildly and | ||
2479 | * might not be a suitable number - should we keep a | ||
2480 | * normalized nr_running number somewhere that negates | ||
2481 | * the hierarchy? | ||
2482 | */ | ||
2483 | if (sgs->sum_nr_running) | ||
2484 | avg_load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running; | ||
2485 | |||
2486 | if ((max_cpu_load - min_cpu_load) > 2*avg_load_per_task) | ||
2487 | sgs->group_imb = 1; | ||
2488 | |||
2489 | sgs->group_capacity = | ||
2490 | DIV_ROUND_CLOSEST(group->cpu_power, SCHED_LOAD_SCALE); | ||
2491 | } | ||
2492 | |||
2493 | /** | ||
2494 | * update_sd_lb_stats - Update sched_group's statistics for load balancing. | ||
2495 | * @sd: sched_domain whose statistics are to be updated. | ||
2496 | * @this_cpu: Cpu for which load balance is currently performed. | ||
2497 | * @idle: Idle status of this_cpu | ||
2498 | * @sd_idle: Idle status of the sched_domain containing group. | ||
2499 | * @cpus: Set of cpus considered for load balancing. | ||
2500 | * @balance: Should we balance. | ||
2501 | * @sds: variable to hold the statistics for this sched_domain. | ||
2502 | */ | ||
2503 | static inline void update_sd_lb_stats(struct sched_domain *sd, int this_cpu, | ||
2504 | enum cpu_idle_type idle, int *sd_idle, | ||
2505 | const struct cpumask *cpus, int *balance, | ||
2506 | struct sd_lb_stats *sds) | ||
2507 | { | ||
2508 | struct sched_domain *child = sd->child; | ||
2509 | struct sched_group *group = sd->groups; | ||
2510 | struct sg_lb_stats sgs; | ||
2511 | int load_idx, prefer_sibling = 0; | ||
2512 | |||
2513 | if (child && child->flags & SD_PREFER_SIBLING) | ||
2514 | prefer_sibling = 1; | ||
2515 | |||
2516 | init_sd_power_savings_stats(sd, sds, idle); | ||
2517 | load_idx = get_sd_load_idx(sd, idle); | ||
2518 | |||
2519 | do { | ||
2520 | int local_group; | ||
2521 | |||
2522 | local_group = cpumask_test_cpu(this_cpu, | ||
2523 | sched_group_cpus(group)); | ||
2524 | memset(&sgs, 0, sizeof(sgs)); | ||
2525 | update_sg_lb_stats(sd, group, this_cpu, idle, load_idx, sd_idle, | ||
2526 | local_group, cpus, balance, &sgs); | ||
2527 | |||
2528 | if (local_group && !(*balance)) | ||
2529 | return; | ||
2530 | |||
2531 | sds->total_load += sgs.group_load; | ||
2532 | sds->total_pwr += group->cpu_power; | ||
2533 | |||
2534 | /* | ||
2535 | * In case the child domain prefers tasks go to siblings | ||
2536 | * first, lower the group capacity to one so that we'll try | ||
2537 | * and move all the excess tasks away. | ||
2538 | */ | ||
2539 | if (prefer_sibling) | ||
2540 | sgs.group_capacity = min(sgs.group_capacity, 1UL); | ||
2541 | |||
2542 | if (local_group) { | ||
2543 | sds->this_load = sgs.avg_load; | ||
2544 | sds->this = group; | ||
2545 | sds->this_nr_running = sgs.sum_nr_running; | ||
2546 | sds->this_load_per_task = sgs.sum_weighted_load; | ||
2547 | } else if (sgs.avg_load > sds->max_load && | ||
2548 | (sgs.sum_nr_running > sgs.group_capacity || | ||
2549 | sgs.group_imb)) { | ||
2550 | sds->max_load = sgs.avg_load; | ||
2551 | sds->busiest = group; | ||
2552 | sds->busiest_nr_running = sgs.sum_nr_running; | ||
2553 | sds->busiest_group_capacity = sgs.group_capacity; | ||
2554 | sds->busiest_load_per_task = sgs.sum_weighted_load; | ||
2555 | sds->group_imb = sgs.group_imb; | ||
2556 | } | ||
2557 | |||
2558 | update_sd_power_savings_stats(group, sds, local_group, &sgs); | ||
2559 | group = group->next; | ||
2560 | } while (group != sd->groups); | ||
2561 | } | ||
2562 | |||
2563 | /** | ||
2564 | * fix_small_imbalance - Calculate the minor imbalance that exists | ||
2565 | * amongst the groups of a sched_domain, during | ||
2566 | * load balancing. | ||
2567 | * @sds: Statistics of the sched_domain whose imbalance is to be calculated. | ||
2568 | * @this_cpu: The cpu at whose sched_domain we're performing load-balance. | ||
2569 | * @imbalance: Variable to store the imbalance. | ||
2570 | */ | ||
2571 | static inline void fix_small_imbalance(struct sd_lb_stats *sds, | ||
2572 | int this_cpu, unsigned long *imbalance) | ||
2573 | { | ||
2574 | unsigned long tmp, pwr_now = 0, pwr_move = 0; | ||
2575 | unsigned int imbn = 2; | ||
2576 | unsigned long scaled_busy_load_per_task; | ||
2577 | |||
2578 | if (sds->this_nr_running) { | ||
2579 | sds->this_load_per_task /= sds->this_nr_running; | ||
2580 | if (sds->busiest_load_per_task > | ||
2581 | sds->this_load_per_task) | ||
2582 | imbn = 1; | ||
2583 | } else | ||
2584 | sds->this_load_per_task = | ||
2585 | cpu_avg_load_per_task(this_cpu); | ||
2586 | |||
2587 | scaled_busy_load_per_task = sds->busiest_load_per_task | ||
2588 | * SCHED_LOAD_SCALE; | ||
2589 | scaled_busy_load_per_task /= sds->busiest->cpu_power; | ||
2590 | |||
2591 | if (sds->max_load - sds->this_load + scaled_busy_load_per_task >= | ||
2592 | (scaled_busy_load_per_task * imbn)) { | ||
2593 | *imbalance = sds->busiest_load_per_task; | ||
2594 | return; | ||
2595 | } | ||
2596 | |||
2597 | /* | ||
2598 | * OK, we don't have enough imbalance to justify moving tasks, | ||
2599 | * however we may be able to increase total CPU power used by | ||
2600 | * moving them. | ||
2601 | */ | ||
2602 | |||
2603 | pwr_now += sds->busiest->cpu_power * | ||
2604 | min(sds->busiest_load_per_task, sds->max_load); | ||
2605 | pwr_now += sds->this->cpu_power * | ||
2606 | min(sds->this_load_per_task, sds->this_load); | ||
2607 | pwr_now /= SCHED_LOAD_SCALE; | ||
2608 | |||
2609 | /* Amount of load we'd subtract */ | ||
2610 | tmp = (sds->busiest_load_per_task * SCHED_LOAD_SCALE) / | ||
2611 | sds->busiest->cpu_power; | ||
2612 | if (sds->max_load > tmp) | ||
2613 | pwr_move += sds->busiest->cpu_power * | ||
2614 | min(sds->busiest_load_per_task, sds->max_load - tmp); | ||
2615 | |||
2616 | /* Amount of load we'd add */ | ||
2617 | if (sds->max_load * sds->busiest->cpu_power < | ||
2618 | sds->busiest_load_per_task * SCHED_LOAD_SCALE) | ||
2619 | tmp = (sds->max_load * sds->busiest->cpu_power) / | ||
2620 | sds->this->cpu_power; | ||
2621 | else | ||
2622 | tmp = (sds->busiest_load_per_task * SCHED_LOAD_SCALE) / | ||
2623 | sds->this->cpu_power; | ||
2624 | pwr_move += sds->this->cpu_power * | ||
2625 | min(sds->this_load_per_task, sds->this_load + tmp); | ||
2626 | pwr_move /= SCHED_LOAD_SCALE; | ||
2627 | |||
2628 | /* Move if we gain throughput */ | ||
2629 | if (pwr_move > pwr_now) | ||
2630 | *imbalance = sds->busiest_load_per_task; | ||
2631 | } | ||
2632 | |||
2633 | /** | ||
2634 | * calculate_imbalance - Calculate the amount of imbalance present within the | ||
2635 | * groups of a given sched_domain during load balance. | ||
2636 | * @sds: statistics of the sched_domain whose imbalance is to be calculated. | ||
2637 | * @this_cpu: Cpu for which currently load balance is being performed. | ||
2638 | * @imbalance: The variable to store the imbalance. | ||
2639 | */ | ||
2640 | static inline void calculate_imbalance(struct sd_lb_stats *sds, int this_cpu, | ||
2641 | unsigned long *imbalance) | ||
2642 | { | ||
2643 | unsigned long max_pull, load_above_capacity = ~0UL; | ||
2644 | |||
2645 | sds->busiest_load_per_task /= sds->busiest_nr_running; | ||
2646 | if (sds->group_imb) { | ||
2647 | sds->busiest_load_per_task = | ||
2648 | min(sds->busiest_load_per_task, sds->avg_load); | ||
2649 | } | ||
2650 | |||
2651 | /* | ||
2652 | * In the presence of smp nice balancing, certain scenarios can have | ||
2653 | * max load less than avg load(as we skip the groups at or below | ||
2654 | * its cpu_power, while calculating max_load..) | ||
2655 | */ | ||
2656 | if (sds->max_load < sds->avg_load) { | ||
2657 | *imbalance = 0; | ||
2658 | return fix_small_imbalance(sds, this_cpu, imbalance); | ||
2659 | } | ||
2660 | |||
2661 | if (!sds->group_imb) { | ||
2662 | /* | ||
2663 | * Don't want to pull so many tasks that a group would go idle. | ||
2664 | */ | ||
2665 | load_above_capacity = (sds->busiest_nr_running - | ||
2666 | sds->busiest_group_capacity); | ||
2667 | |||
2668 | load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_LOAD_SCALE); | ||
2669 | |||
2670 | load_above_capacity /= sds->busiest->cpu_power; | ||
2671 | } | ||
2672 | |||
2673 | /* | ||
2674 | * We're trying to get all the cpus to the average_load, so we don't | ||
2675 | * want to push ourselves above the average load, nor do we wish to | ||
2676 | * reduce the max loaded cpu below the average load. At the same time, | ||
2677 | * we also don't want to reduce the group load below the group capacity | ||
2678 | * (so that we can implement power-savings policies etc). Thus we look | ||
2679 | * for the minimum possible imbalance. | ||
2680 | * Be careful of negative numbers as they'll appear as very large values | ||
2681 | * with unsigned longs. | ||
2682 | */ | ||
2683 | max_pull = min(sds->max_load - sds->avg_load, load_above_capacity); | ||
2684 | |||
2685 | /* How much load to actually move to equalise the imbalance */ | ||
2686 | *imbalance = min(max_pull * sds->busiest->cpu_power, | ||
2687 | (sds->avg_load - sds->this_load) * sds->this->cpu_power) | ||
2688 | / SCHED_LOAD_SCALE; | ||
2689 | |||
2690 | /* | ||
2691 | * if *imbalance is less than the average load per runnable task | ||
2692 | * there is no gaurantee that any tasks will be moved so we'll have | ||
2693 | * a think about bumping its value to force at least one task to be | ||
2694 | * moved | ||
2695 | */ | ||
2696 | if (*imbalance < sds->busiest_load_per_task) | ||
2697 | return fix_small_imbalance(sds, this_cpu, imbalance); | ||
2698 | |||
2699 | } | ||
2700 | /******* find_busiest_group() helpers end here *********************/ | ||
2701 | |||
2702 | /** | ||
2703 | * find_busiest_group - Returns the busiest group within the sched_domain | ||
2704 | * if there is an imbalance. If there isn't an imbalance, and | ||
2705 | * the user has opted for power-savings, it returns a group whose | ||
2706 | * CPUs can be put to idle by rebalancing those tasks elsewhere, if | ||
2707 | * such a group exists. | ||
2708 | * | ||
2709 | * Also calculates the amount of weighted load which should be moved | ||
2710 | * to restore balance. | ||
2711 | * | ||
2712 | * @sd: The sched_domain whose busiest group is to be returned. | ||
2713 | * @this_cpu: The cpu for which load balancing is currently being performed. | ||
2714 | * @imbalance: Variable which stores amount of weighted load which should | ||
2715 | * be moved to restore balance/put a group to idle. | ||
2716 | * @idle: The idle status of this_cpu. | ||
2717 | * @sd_idle: The idleness of sd | ||
2718 | * @cpus: The set of CPUs under consideration for load-balancing. | ||
2719 | * @balance: Pointer to a variable indicating if this_cpu | ||
2720 | * is the appropriate cpu to perform load balancing at this_level. | ||
2721 | * | ||
2722 | * Returns: - the busiest group if imbalance exists. | ||
2723 | * - If no imbalance and user has opted for power-savings balance, | ||
2724 | * return the least loaded group whose CPUs can be | ||
2725 | * put to idle by rebalancing its tasks onto our group. | ||
2726 | */ | ||
2727 | static struct sched_group * | ||
2728 | find_busiest_group(struct sched_domain *sd, int this_cpu, | ||
2729 | unsigned long *imbalance, enum cpu_idle_type idle, | ||
2730 | int *sd_idle, const struct cpumask *cpus, int *balance) | ||
2731 | { | ||
2732 | struct sd_lb_stats sds; | ||
2733 | |||
2734 | memset(&sds, 0, sizeof(sds)); | ||
2735 | |||
2736 | /* | ||
2737 | * Compute the various statistics relavent for load balancing at | ||
2738 | * this level. | ||
2739 | */ | ||
2740 | update_sd_lb_stats(sd, this_cpu, idle, sd_idle, cpus, | ||
2741 | balance, &sds); | ||
2742 | |||
2743 | /* Cases where imbalance does not exist from POV of this_cpu */ | ||
2744 | /* 1) this_cpu is not the appropriate cpu to perform load balancing | ||
2745 | * at this level. | ||
2746 | * 2) There is no busy sibling group to pull from. | ||
2747 | * 3) This group is the busiest group. | ||
2748 | * 4) This group is more busy than the avg busieness at this | ||
2749 | * sched_domain. | ||
2750 | * 5) The imbalance is within the specified limit. | ||
2751 | */ | ||
2752 | if (!(*balance)) | ||
2753 | goto ret; | ||
2754 | |||
2755 | if (!sds.busiest || sds.busiest_nr_running == 0) | ||
2756 | goto out_balanced; | ||
2757 | |||
2758 | if (sds.this_load >= sds.max_load) | ||
2759 | goto out_balanced; | ||
2760 | |||
2761 | sds.avg_load = (SCHED_LOAD_SCALE * sds.total_load) / sds.total_pwr; | ||
2762 | |||
2763 | if (sds.this_load >= sds.avg_load) | ||
2764 | goto out_balanced; | ||
2765 | |||
2766 | if (100 * sds.max_load <= sd->imbalance_pct * sds.this_load) | ||
2767 | goto out_balanced; | ||
2768 | |||
2769 | /* Looks like there is an imbalance. Compute it */ | ||
2770 | calculate_imbalance(&sds, this_cpu, imbalance); | ||
2771 | return sds.busiest; | ||
2772 | |||
2773 | out_balanced: | ||
2774 | /* | ||
2775 | * There is no obvious imbalance. But check if we can do some balancing | ||
2776 | * to save power. | ||
2777 | */ | ||
2778 | if (check_power_save_busiest_group(&sds, this_cpu, imbalance)) | ||
2779 | return sds.busiest; | ||
2780 | ret: | ||
2781 | *imbalance = 0; | ||
2782 | return NULL; | ||
2783 | } | ||
2784 | |||
2785 | /* | ||
2786 | * find_busiest_queue - find the busiest runqueue among the cpus in group. | ||
2787 | */ | ||
2788 | static struct rq * | ||
2789 | find_busiest_queue(struct sched_group *group, enum cpu_idle_type idle, | ||
2790 | unsigned long imbalance, const struct cpumask *cpus) | ||
2791 | { | ||
2792 | struct rq *busiest = NULL, *rq; | ||
2793 | unsigned long max_load = 0; | ||
2794 | int i; | ||
2795 | |||
2796 | for_each_cpu(i, sched_group_cpus(group)) { | ||
2797 | unsigned long power = power_of(i); | ||
2798 | unsigned long capacity = DIV_ROUND_CLOSEST(power, SCHED_LOAD_SCALE); | ||
2799 | unsigned long wl; | ||
2800 | |||
2801 | if (!cpumask_test_cpu(i, cpus)) | ||
2802 | continue; | ||
2803 | |||
2804 | rq = cpu_rq(i); | ||
2805 | wl = weighted_cpuload(i); | ||
2806 | |||
2807 | /* | ||
2808 | * When comparing with imbalance, use weighted_cpuload() | ||
2809 | * which is not scaled with the cpu power. | ||
2810 | */ | ||
2811 | if (capacity && rq->nr_running == 1 && wl > imbalance) | ||
2812 | continue; | ||
2813 | |||
2814 | /* | ||
2815 | * For the load comparisons with the other cpu's, consider | ||
2816 | * the weighted_cpuload() scaled with the cpu power, so that | ||
2817 | * the load can be moved away from the cpu that is potentially | ||
2818 | * running at a lower capacity. | ||
2819 | */ | ||
2820 | wl = (wl * SCHED_LOAD_SCALE) / power; | ||
2821 | |||
2822 | if (wl > max_load) { | ||
2823 | max_load = wl; | ||
2824 | busiest = rq; | ||
2825 | } | ||
2826 | } | ||
2827 | |||
2828 | return busiest; | ||
2829 | } | ||
2830 | |||
2831 | /* | ||
2832 | * Max backoff if we encounter pinned tasks. Pretty arbitrary value, but | ||
2833 | * so long as it is large enough. | ||
2834 | */ | ||
2835 | #define MAX_PINNED_INTERVAL 512 | ||
2836 | |||
2837 | /* Working cpumask for load_balance and load_balance_newidle. */ | ||
2838 | static DEFINE_PER_CPU(cpumask_var_t, load_balance_tmpmask); | ||
2839 | |||
2840 | static int need_active_balance(struct sched_domain *sd, int sd_idle, int idle) | ||
2841 | { | ||
2842 | if (idle == CPU_NEWLY_IDLE) { | ||
2843 | /* | ||
2844 | * The only task running in a non-idle cpu can be moved to this | ||
2845 | * cpu in an attempt to completely freeup the other CPU | ||
2846 | * package. | ||
2847 | * | ||
2848 | * The package power saving logic comes from | ||
2849 | * find_busiest_group(). If there are no imbalance, then | ||
2850 | * f_b_g() will return NULL. However when sched_mc={1,2} then | ||
2851 | * f_b_g() will select a group from which a running task may be | ||
2852 | * pulled to this cpu in order to make the other package idle. | ||
2853 | * If there is no opportunity to make a package idle and if | ||
2854 | * there are no imbalance, then f_b_g() will return NULL and no | ||
2855 | * action will be taken in load_balance_newidle(). | ||
2856 | * | ||
2857 | * Under normal task pull operation due to imbalance, there | ||
2858 | * will be more than one task in the source run queue and | ||
2859 | * move_tasks() will succeed. ld_moved will be true and this | ||
2860 | * active balance code will not be triggered. | ||
2861 | */ | ||
2862 | if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER && | ||
2863 | !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE)) | ||
2864 | return 0; | ||
2865 | |||
2866 | if (sched_mc_power_savings < POWERSAVINGS_BALANCE_WAKEUP) | ||
2867 | return 0; | ||
2868 | } | ||
2869 | |||
2870 | return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2); | ||
2871 | } | ||
2872 | |||
2873 | /* | ||
2874 | * Check this_cpu to ensure it is balanced within domain. Attempt to move | ||
2875 | * tasks if there is an imbalance. | ||
2876 | */ | ||
2877 | static int load_balance(int this_cpu, struct rq *this_rq, | ||
2878 | struct sched_domain *sd, enum cpu_idle_type idle, | ||
2879 | int *balance) | ||
2880 | { | ||
2881 | int ld_moved, all_pinned = 0, active_balance = 0, sd_idle = 0; | ||
2882 | struct sched_group *group; | ||
2883 | unsigned long imbalance; | ||
2884 | struct rq *busiest; | ||
2885 | unsigned long flags; | ||
2886 | struct cpumask *cpus = __get_cpu_var(load_balance_tmpmask); | ||
2887 | |||
2888 | cpumask_copy(cpus, cpu_active_mask); | ||
2889 | |||
2890 | /* | ||
2891 | * When power savings policy is enabled for the parent domain, idle | ||
2892 | * sibling can pick up load irrespective of busy siblings. In this case, | ||
2893 | * let the state of idle sibling percolate up as CPU_IDLE, instead of | ||
2894 | * portraying it as CPU_NOT_IDLE. | ||
2895 | */ | ||
2896 | if (idle != CPU_NOT_IDLE && sd->flags & SD_SHARE_CPUPOWER && | ||
2897 | !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE)) | ||
2898 | sd_idle = 1; | ||
2899 | |||
2900 | schedstat_inc(sd, lb_count[idle]); | ||
2901 | |||
2902 | redo: | ||
2903 | update_shares(sd); | ||
2904 | group = find_busiest_group(sd, this_cpu, &imbalance, idle, &sd_idle, | ||
2905 | cpus, balance); | ||
2906 | |||
2907 | if (*balance == 0) | ||
2908 | goto out_balanced; | ||
2909 | |||
2910 | if (!group) { | ||
2911 | schedstat_inc(sd, lb_nobusyg[idle]); | ||
2912 | goto out_balanced; | ||
2913 | } | ||
2914 | |||
2915 | busiest = find_busiest_queue(group, idle, imbalance, cpus); | ||
2916 | if (!busiest) { | ||
2917 | schedstat_inc(sd, lb_nobusyq[idle]); | ||
2918 | goto out_balanced; | ||
2919 | } | ||
2920 | |||
2921 | BUG_ON(busiest == this_rq); | ||
2922 | |||
2923 | schedstat_add(sd, lb_imbalance[idle], imbalance); | ||
2924 | |||
2925 | ld_moved = 0; | ||
2926 | if (busiest->nr_running > 1) { | ||
2927 | /* | ||
2928 | * Attempt to move tasks. If find_busiest_group has found | ||
2929 | * an imbalance but busiest->nr_running <= 1, the group is | ||
2930 | * still unbalanced. ld_moved simply stays zero, so it is | ||
2931 | * correctly treated as an imbalance. | ||
2932 | */ | ||
2933 | local_irq_save(flags); | ||
2934 | double_rq_lock(this_rq, busiest); | ||
2935 | ld_moved = move_tasks(this_rq, this_cpu, busiest, | ||
2936 | imbalance, sd, idle, &all_pinned); | ||
2937 | double_rq_unlock(this_rq, busiest); | ||
2938 | local_irq_restore(flags); | ||
2939 | |||
2940 | /* | ||
2941 | * some other cpu did the load balance for us. | ||
2942 | */ | ||
2943 | if (ld_moved && this_cpu != smp_processor_id()) | ||
2944 | resched_cpu(this_cpu); | ||
2945 | |||
2946 | /* All tasks on this runqueue were pinned by CPU affinity */ | ||
2947 | if (unlikely(all_pinned)) { | ||
2948 | cpumask_clear_cpu(cpu_of(busiest), cpus); | ||
2949 | if (!cpumask_empty(cpus)) | ||
2950 | goto redo; | ||
2951 | goto out_balanced; | ||
2952 | } | ||
2953 | } | ||
2954 | |||
2955 | if (!ld_moved) { | ||
2956 | schedstat_inc(sd, lb_failed[idle]); | ||
2957 | sd->nr_balance_failed++; | ||
2958 | |||
2959 | if (need_active_balance(sd, sd_idle, idle)) { | ||
2960 | raw_spin_lock_irqsave(&busiest->lock, flags); | ||
2961 | |||
2962 | /* don't kick the migration_thread, if the curr | ||
2963 | * task on busiest cpu can't be moved to this_cpu | ||
2964 | */ | ||
2965 | if (!cpumask_test_cpu(this_cpu, | ||
2966 | &busiest->curr->cpus_allowed)) { | ||
2967 | raw_spin_unlock_irqrestore(&busiest->lock, | ||
2968 | flags); | ||
2969 | all_pinned = 1; | ||
2970 | goto out_one_pinned; | ||
2971 | } | ||
2972 | |||
2973 | if (!busiest->active_balance) { | ||
2974 | busiest->active_balance = 1; | ||
2975 | busiest->push_cpu = this_cpu; | ||
2976 | active_balance = 1; | ||
2977 | } | ||
2978 | raw_spin_unlock_irqrestore(&busiest->lock, flags); | ||
2979 | if (active_balance) | ||
2980 | wake_up_process(busiest->migration_thread); | ||
2981 | |||
2982 | /* | ||
2983 | * We've kicked active balancing, reset the failure | ||
2984 | * counter. | ||
2985 | */ | ||
2986 | sd->nr_balance_failed = sd->cache_nice_tries+1; | ||
2987 | } | ||
2988 | } else | ||
2989 | sd->nr_balance_failed = 0; | ||
2990 | |||
2991 | if (likely(!active_balance)) { | ||
2992 | /* We were unbalanced, so reset the balancing interval */ | ||
2993 | sd->balance_interval = sd->min_interval; | ||
2994 | } else { | ||
2995 | /* | ||
2996 | * If we've begun active balancing, start to back off. This | ||
2997 | * case may not be covered by the all_pinned logic if there | ||
2998 | * is only 1 task on the busy runqueue (because we don't call | ||
2999 | * move_tasks). | ||
3000 | */ | ||
3001 | if (sd->balance_interval < sd->max_interval) | ||
3002 | sd->balance_interval *= 2; | ||
3003 | } | ||
3004 | |||
3005 | if (!ld_moved && !sd_idle && sd->flags & SD_SHARE_CPUPOWER && | ||
3006 | !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE)) | ||
3007 | ld_moved = -1; | ||
3008 | |||
3009 | goto out; | ||
3010 | |||
3011 | out_balanced: | ||
3012 | schedstat_inc(sd, lb_balanced[idle]); | ||
3013 | |||
3014 | sd->nr_balance_failed = 0; | ||
3015 | |||
3016 | out_one_pinned: | ||
3017 | /* tune up the balancing interval */ | ||
3018 | if ((all_pinned && sd->balance_interval < MAX_PINNED_INTERVAL) || | ||
3019 | (sd->balance_interval < sd->max_interval)) | ||
3020 | sd->balance_interval *= 2; | ||
3021 | |||
3022 | if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER && | ||
3023 | !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE)) | ||
3024 | ld_moved = -1; | ||
3025 | else | ||
3026 | ld_moved = 0; | ||
3027 | out: | ||
3028 | if (ld_moved) | ||
3029 | update_shares(sd); | ||
3030 | return ld_moved; | ||
3031 | } | ||
3032 | |||
3033 | /* | ||
3034 | * idle_balance is called by schedule() if this_cpu is about to become | ||
3035 | * idle. Attempts to pull tasks from other CPUs. | ||
3036 | */ | ||
3037 | static void idle_balance(int this_cpu, struct rq *this_rq) | ||
3038 | { | ||
3039 | struct sched_domain *sd; | ||
3040 | int pulled_task = 0; | ||
3041 | unsigned long next_balance = jiffies + HZ; | ||
3042 | |||
3043 | this_rq->idle_stamp = this_rq->clock; | ||
3044 | |||
3045 | if (this_rq->avg_idle < sysctl_sched_migration_cost) | ||
3046 | return; | ||
3047 | |||
3048 | /* | ||
3049 | * Drop the rq->lock, but keep IRQ/preempt disabled. | ||
3050 | */ | ||
3051 | raw_spin_unlock(&this_rq->lock); | ||
3052 | |||
3053 | for_each_domain(this_cpu, sd) { | ||
3054 | unsigned long interval; | ||
3055 | int balance = 1; | ||
3056 | |||
3057 | if (!(sd->flags & SD_LOAD_BALANCE)) | ||
3058 | continue; | ||
3059 | |||
3060 | if (sd->flags & SD_BALANCE_NEWIDLE) { | ||
3061 | /* If we've pulled tasks over stop searching: */ | ||
3062 | pulled_task = load_balance(this_cpu, this_rq, | ||
3063 | sd, CPU_NEWLY_IDLE, &balance); | ||
3064 | } | ||
3065 | |||
3066 | interval = msecs_to_jiffies(sd->balance_interval); | ||
3067 | if (time_after(next_balance, sd->last_balance + interval)) | ||
3068 | next_balance = sd->last_balance + interval; | ||
3069 | if (pulled_task) { | ||
3070 | this_rq->idle_stamp = 0; | ||
3071 | break; | ||
3072 | } | ||
3073 | } | ||
3074 | |||
3075 | raw_spin_lock(&this_rq->lock); | ||
3076 | |||
3077 | if (pulled_task || time_after(jiffies, this_rq->next_balance)) { | ||
3078 | /* | ||
3079 | * We are going idle. next_balance may be set based on | ||
3080 | * a busy processor. So reset next_balance. | ||
3081 | */ | ||
3082 | this_rq->next_balance = next_balance; | ||
3083 | } | ||
3084 | } | ||
3085 | |||
3086 | /* | ||
3087 | * active_load_balance is run by migration threads. It pushes running tasks | ||
3088 | * off the busiest CPU onto idle CPUs. It requires at least 1 task to be | ||
3089 | * running on each physical CPU where possible, and avoids physical / | ||
3090 | * logical imbalances. | ||
3091 | * | ||
3092 | * Called with busiest_rq locked. | ||
3093 | */ | ||
3094 | static void active_load_balance(struct rq *busiest_rq, int busiest_cpu) | ||
3095 | { | ||
3096 | int target_cpu = busiest_rq->push_cpu; | ||
3097 | struct sched_domain *sd; | ||
3098 | struct rq *target_rq; | ||
3099 | |||
3100 | /* Is there any task to move? */ | ||
3101 | if (busiest_rq->nr_running <= 1) | ||
3102 | return; | ||
3103 | |||
3104 | target_rq = cpu_rq(target_cpu); | ||
3105 | |||
3106 | /* | ||
3107 | * This condition is "impossible", if it occurs | ||
3108 | * we need to fix it. Originally reported by | ||
3109 | * Bjorn Helgaas on a 128-cpu setup. | ||
3110 | */ | ||
3111 | BUG_ON(busiest_rq == target_rq); | ||
3112 | |||
3113 | /* move a task from busiest_rq to target_rq */ | ||
3114 | double_lock_balance(busiest_rq, target_rq); | ||
3115 | update_rq_clock(busiest_rq); | ||
3116 | update_rq_clock(target_rq); | ||
3117 | |||
3118 | /* Search for an sd spanning us and the target CPU. */ | ||
3119 | for_each_domain(target_cpu, sd) { | ||
3120 | if ((sd->flags & SD_LOAD_BALANCE) && | ||
3121 | cpumask_test_cpu(busiest_cpu, sched_domain_span(sd))) | ||
3122 | break; | ||
3123 | } | ||
3124 | |||
3125 | if (likely(sd)) { | ||
3126 | schedstat_inc(sd, alb_count); | ||
3127 | |||
3128 | if (move_one_task(target_rq, target_cpu, busiest_rq, | ||
3129 | sd, CPU_IDLE)) | ||
3130 | schedstat_inc(sd, alb_pushed); | ||
3131 | else | ||
3132 | schedstat_inc(sd, alb_failed); | ||
3133 | } | ||
3134 | double_unlock_balance(busiest_rq, target_rq); | ||
3135 | } | ||
3136 | |||
3137 | #ifdef CONFIG_NO_HZ | ||
3138 | static struct { | ||
3139 | atomic_t load_balancer; | ||
3140 | cpumask_var_t cpu_mask; | ||
3141 | cpumask_var_t ilb_grp_nohz_mask; | ||
3142 | } nohz ____cacheline_aligned = { | ||
3143 | .load_balancer = ATOMIC_INIT(-1), | ||
3144 | }; | ||
3145 | |||
3146 | int get_nohz_load_balancer(void) | ||
3147 | { | ||
3148 | return atomic_read(&nohz.load_balancer); | ||
3149 | } | ||
3150 | |||
3151 | #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT) | ||
3152 | /** | ||
3153 | * lowest_flag_domain - Return lowest sched_domain containing flag. | ||
3154 | * @cpu: The cpu whose lowest level of sched domain is to | ||
3155 | * be returned. | ||
3156 | * @flag: The flag to check for the lowest sched_domain | ||
3157 | * for the given cpu. | ||
3158 | * | ||
3159 | * Returns the lowest sched_domain of a cpu which contains the given flag. | ||
3160 | */ | ||
3161 | static inline struct sched_domain *lowest_flag_domain(int cpu, int flag) | ||
3162 | { | ||
3163 | struct sched_domain *sd; | ||
3164 | |||
3165 | for_each_domain(cpu, sd) | ||
3166 | if (sd && (sd->flags & flag)) | ||
3167 | break; | ||
3168 | |||
3169 | return sd; | ||
3170 | } | ||
3171 | |||
3172 | /** | ||
3173 | * for_each_flag_domain - Iterates over sched_domains containing the flag. | ||
3174 | * @cpu: The cpu whose domains we're iterating over. | ||
3175 | * @sd: variable holding the value of the power_savings_sd | ||
3176 | * for cpu. | ||
3177 | * @flag: The flag to filter the sched_domains to be iterated. | ||
3178 | * | ||
3179 | * Iterates over all the scheduler domains for a given cpu that has the 'flag' | ||
3180 | * set, starting from the lowest sched_domain to the highest. | ||
3181 | */ | ||
3182 | #define for_each_flag_domain(cpu, sd, flag) \ | ||
3183 | for (sd = lowest_flag_domain(cpu, flag); \ | ||
3184 | (sd && (sd->flags & flag)); sd = sd->parent) | ||
3185 | |||
3186 | /** | ||
3187 | * is_semi_idle_group - Checks if the given sched_group is semi-idle. | ||
3188 | * @ilb_group: group to be checked for semi-idleness | ||
3189 | * | ||
3190 | * Returns: 1 if the group is semi-idle. 0 otherwise. | ||
3191 | * | ||
3192 | * We define a sched_group to be semi idle if it has atleast one idle-CPU | ||
3193 | * and atleast one non-idle CPU. This helper function checks if the given | ||
3194 | * sched_group is semi-idle or not. | ||
3195 | */ | ||
3196 | static inline int is_semi_idle_group(struct sched_group *ilb_group) | ||
3197 | { | ||
3198 | cpumask_and(nohz.ilb_grp_nohz_mask, nohz.cpu_mask, | ||
3199 | sched_group_cpus(ilb_group)); | ||
3200 | |||
3201 | /* | ||
3202 | * A sched_group is semi-idle when it has atleast one busy cpu | ||
3203 | * and atleast one idle cpu. | ||
3204 | */ | ||
3205 | if (cpumask_empty(nohz.ilb_grp_nohz_mask)) | ||
3206 | return 0; | ||
3207 | |||
3208 | if (cpumask_equal(nohz.ilb_grp_nohz_mask, sched_group_cpus(ilb_group))) | ||
3209 | return 0; | ||
3210 | |||
3211 | return 1; | ||
3212 | } | ||
3213 | /** | ||
3214 | * find_new_ilb - Finds the optimum idle load balancer for nomination. | ||
3215 | * @cpu: The cpu which is nominating a new idle_load_balancer. | ||
3216 | * | ||
3217 | * Returns: Returns the id of the idle load balancer if it exists, | ||
3218 | * Else, returns >= nr_cpu_ids. | ||
3219 | * | ||
3220 | * This algorithm picks the idle load balancer such that it belongs to a | ||
3221 | * semi-idle powersavings sched_domain. The idea is to try and avoid | ||
3222 | * completely idle packages/cores just for the purpose of idle load balancing | ||
3223 | * when there are other idle cpu's which are better suited for that job. | ||
3224 | */ | ||
3225 | static int find_new_ilb(int cpu) | ||
3226 | { | ||
3227 | struct sched_domain *sd; | ||
3228 | struct sched_group *ilb_group; | ||
3229 | |||
3230 | /* | ||
3231 | * Have idle load balancer selection from semi-idle packages only | ||
3232 | * when power-aware load balancing is enabled | ||
3233 | */ | ||
3234 | if (!(sched_smt_power_savings || sched_mc_power_savings)) | ||
3235 | goto out_done; | ||
3236 | |||
3237 | /* | ||
3238 | * Optimize for the case when we have no idle CPUs or only one | ||
3239 | * idle CPU. Don't walk the sched_domain hierarchy in such cases | ||
3240 | */ | ||
3241 | if (cpumask_weight(nohz.cpu_mask) < 2) | ||
3242 | goto out_done; | ||
3243 | |||
3244 | for_each_flag_domain(cpu, sd, SD_POWERSAVINGS_BALANCE) { | ||
3245 | ilb_group = sd->groups; | ||
3246 | |||
3247 | do { | ||
3248 | if (is_semi_idle_group(ilb_group)) | ||
3249 | return cpumask_first(nohz.ilb_grp_nohz_mask); | ||
3250 | |||
3251 | ilb_group = ilb_group->next; | ||
3252 | |||
3253 | } while (ilb_group != sd->groups); | ||
3254 | } | ||
3255 | |||
3256 | out_done: | ||
3257 | return cpumask_first(nohz.cpu_mask); | ||
3258 | } | ||
3259 | #else /* (CONFIG_SCHED_MC || CONFIG_SCHED_SMT) */ | ||
3260 | static inline int find_new_ilb(int call_cpu) | ||
3261 | { | ||
3262 | return cpumask_first(nohz.cpu_mask); | ||
3263 | } | ||
3264 | #endif | ||
3265 | |||
3266 | /* | ||
3267 | * This routine will try to nominate the ilb (idle load balancing) | ||
3268 | * owner among the cpus whose ticks are stopped. ilb owner will do the idle | ||
3269 | * load balancing on behalf of all those cpus. If all the cpus in the system | ||
3270 | * go into this tickless mode, then there will be no ilb owner (as there is | ||
3271 | * no need for one) and all the cpus will sleep till the next wakeup event | ||
3272 | * arrives... | ||
3273 | * | ||
3274 | * For the ilb owner, tick is not stopped. And this tick will be used | ||
3275 | * for idle load balancing. ilb owner will still be part of | ||
3276 | * nohz.cpu_mask.. | ||
3277 | * | ||
3278 | * While stopping the tick, this cpu will become the ilb owner if there | ||
3279 | * is no other owner. And will be the owner till that cpu becomes busy | ||
3280 | * or if all cpus in the system stop their ticks at which point | ||
3281 | * there is no need for ilb owner. | ||
3282 | * | ||
3283 | * When the ilb owner becomes busy, it nominates another owner, during the | ||
3284 | * next busy scheduler_tick() | ||
3285 | */ | ||
3286 | int select_nohz_load_balancer(int stop_tick) | ||
3287 | { | ||
3288 | int cpu = smp_processor_id(); | ||
3289 | |||
3290 | if (stop_tick) { | ||
3291 | cpu_rq(cpu)->in_nohz_recently = 1; | ||
3292 | |||
3293 | if (!cpu_active(cpu)) { | ||
3294 | if (atomic_read(&nohz.load_balancer) != cpu) | ||
3295 | return 0; | ||
3296 | |||
3297 | /* | ||
3298 | * If we are going offline and still the leader, | ||
3299 | * give up! | ||
3300 | */ | ||
3301 | if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu) | ||
3302 | BUG(); | ||
3303 | |||
3304 | return 0; | ||
3305 | } | ||
3306 | |||
3307 | cpumask_set_cpu(cpu, nohz.cpu_mask); | ||
3308 | |||
3309 | /* time for ilb owner also to sleep */ | ||
3310 | if (cpumask_weight(nohz.cpu_mask) == num_active_cpus()) { | ||
3311 | if (atomic_read(&nohz.load_balancer) == cpu) | ||
3312 | atomic_set(&nohz.load_balancer, -1); | ||
3313 | return 0; | ||
3314 | } | ||
3315 | |||
3316 | if (atomic_read(&nohz.load_balancer) == -1) { | ||
3317 | /* make me the ilb owner */ | ||
3318 | if (atomic_cmpxchg(&nohz.load_balancer, -1, cpu) == -1) | ||
3319 | return 1; | ||
3320 | } else if (atomic_read(&nohz.load_balancer) == cpu) { | ||
3321 | int new_ilb; | ||
3322 | |||
3323 | if (!(sched_smt_power_savings || | ||
3324 | sched_mc_power_savings)) | ||
3325 | return 1; | ||
3326 | /* | ||
3327 | * Check to see if there is a more power-efficient | ||
3328 | * ilb. | ||
3329 | */ | ||
3330 | new_ilb = find_new_ilb(cpu); | ||
3331 | if (new_ilb < nr_cpu_ids && new_ilb != cpu) { | ||
3332 | atomic_set(&nohz.load_balancer, -1); | ||
3333 | resched_cpu(new_ilb); | ||
3334 | return 0; | ||
3335 | } | ||
3336 | return 1; | ||
3337 | } | ||
3338 | } else { | ||
3339 | if (!cpumask_test_cpu(cpu, nohz.cpu_mask)) | ||
3340 | return 0; | ||
3341 | |||
3342 | cpumask_clear_cpu(cpu, nohz.cpu_mask); | ||
3343 | |||
3344 | if (atomic_read(&nohz.load_balancer) == cpu) | ||
3345 | if (atomic_cmpxchg(&nohz.load_balancer, cpu, -1) != cpu) | ||
3346 | BUG(); | ||
3347 | } | ||
3348 | return 0; | ||
3349 | } | ||
3350 | #endif | ||
3351 | |||
3352 | static DEFINE_SPINLOCK(balancing); | ||
3353 | |||
3354 | /* | ||
3355 | * It checks each scheduling domain to see if it is due to be balanced, | ||
3356 | * and initiates a balancing operation if so. | ||
3357 | * | ||
3358 | * Balancing parameters are set up in arch_init_sched_domains. | ||
3359 | */ | ||
3360 | static void rebalance_domains(int cpu, enum cpu_idle_type idle) | ||
3361 | { | ||
3362 | int balance = 1; | ||
3363 | struct rq *rq = cpu_rq(cpu); | ||
3364 | unsigned long interval; | ||
3365 | struct sched_domain *sd; | ||
3366 | /* Earliest time when we have to do rebalance again */ | ||
3367 | unsigned long next_balance = jiffies + 60*HZ; | ||
3368 | int update_next_balance = 0; | ||
3369 | int need_serialize; | ||
3370 | |||
3371 | for_each_domain(cpu, sd) { | ||
3372 | if (!(sd->flags & SD_LOAD_BALANCE)) | ||
3373 | continue; | ||
3374 | |||
3375 | interval = sd->balance_interval; | ||
3376 | if (idle != CPU_IDLE) | ||
3377 | interval *= sd->busy_factor; | ||
3378 | |||
3379 | /* scale ms to jiffies */ | ||
3380 | interval = msecs_to_jiffies(interval); | ||
3381 | if (unlikely(!interval)) | ||
3382 | interval = 1; | ||
3383 | if (interval > HZ*NR_CPUS/10) | ||
3384 | interval = HZ*NR_CPUS/10; | ||
3385 | |||
3386 | need_serialize = sd->flags & SD_SERIALIZE; | ||
3387 | |||
3388 | if (need_serialize) { | ||
3389 | if (!spin_trylock(&balancing)) | ||
3390 | goto out; | ||
3391 | } | ||
3392 | |||
3393 | if (time_after_eq(jiffies, sd->last_balance + interval)) { | ||
3394 | if (load_balance(cpu, rq, sd, idle, &balance)) { | ||
3395 | /* | ||
3396 | * We've pulled tasks over so either we're no | ||
3397 | * longer idle, or one of our SMT siblings is | ||
3398 | * not idle. | ||
3399 | */ | ||
3400 | idle = CPU_NOT_IDLE; | ||
3401 | } | ||
3402 | sd->last_balance = jiffies; | ||
3403 | } | ||
3404 | if (need_serialize) | ||
3405 | spin_unlock(&balancing); | ||
3406 | out: | ||
3407 | if (time_after(next_balance, sd->last_balance + interval)) { | ||
3408 | next_balance = sd->last_balance + interval; | ||
3409 | update_next_balance = 1; | ||
3410 | } | ||
3411 | |||
3412 | /* | ||
3413 | * Stop the load balance at this level. There is another | ||
3414 | * CPU in our sched group which is doing load balancing more | ||
3415 | * actively. | ||
3416 | */ | ||
3417 | if (!balance) | ||
3418 | break; | ||
3419 | } | ||
3420 | |||
3421 | /* | ||
3422 | * next_balance will be updated only when there is a need. | ||
3423 | * When the cpu is attached to null domain for ex, it will not be | ||
3424 | * updated. | ||
3425 | */ | ||
3426 | if (likely(update_next_balance)) | ||
3427 | rq->next_balance = next_balance; | ||
3428 | } | ||
3429 | |||
3430 | /* | ||
3431 | * run_rebalance_domains is triggered when needed from the scheduler tick. | ||
3432 | * In CONFIG_NO_HZ case, the idle load balance owner will do the | ||
3433 | * rebalancing for all the cpus for whom scheduler ticks are stopped. | ||
3434 | */ | ||
3435 | static void run_rebalance_domains(struct softirq_action *h) | ||
3436 | { | ||
3437 | int this_cpu = smp_processor_id(); | ||
3438 | struct rq *this_rq = cpu_rq(this_cpu); | ||
3439 | enum cpu_idle_type idle = this_rq->idle_at_tick ? | ||
3440 | CPU_IDLE : CPU_NOT_IDLE; | ||
3441 | |||
3442 | rebalance_domains(this_cpu, idle); | ||
3443 | |||
3444 | #ifdef CONFIG_NO_HZ | ||
3445 | /* | ||
3446 | * If this cpu is the owner for idle load balancing, then do the | ||
3447 | * balancing on behalf of the other idle cpus whose ticks are | ||
3448 | * stopped. | ||
3449 | */ | ||
3450 | if (this_rq->idle_at_tick && | ||
3451 | atomic_read(&nohz.load_balancer) == this_cpu) { | ||
3452 | struct rq *rq; | ||
3453 | int balance_cpu; | ||
3454 | |||
3455 | for_each_cpu(balance_cpu, nohz.cpu_mask) { | ||
3456 | if (balance_cpu == this_cpu) | ||
3457 | continue; | ||
3458 | |||
3459 | /* | ||
3460 | * If this cpu gets work to do, stop the load balancing | ||
3461 | * work being done for other cpus. Next load | ||
3462 | * balancing owner will pick it up. | ||
3463 | */ | ||
3464 | if (need_resched()) | ||
3465 | break; | ||
3466 | |||
3467 | rebalance_domains(balance_cpu, CPU_IDLE); | ||
3468 | |||
3469 | rq = cpu_rq(balance_cpu); | ||
3470 | if (time_after(this_rq->next_balance, rq->next_balance)) | ||
3471 | this_rq->next_balance = rq->next_balance; | ||
3472 | } | ||
3473 | } | ||
3474 | #endif | ||
3475 | } | ||
3476 | |||
3477 | static inline int on_null_domain(int cpu) | ||
3478 | { | ||
3479 | return !rcu_dereference(cpu_rq(cpu)->sd); | ||
3480 | } | ||
3481 | |||
3482 | /* | ||
3483 | * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing. | ||
3484 | * | ||
3485 | * In case of CONFIG_NO_HZ, this is the place where we nominate a new | ||
3486 | * idle load balancing owner or decide to stop the periodic load balancing, | ||
3487 | * if the whole system is idle. | ||
3488 | */ | ||
3489 | static inline void trigger_load_balance(struct rq *rq, int cpu) | ||
3490 | { | ||
3491 | #ifdef CONFIG_NO_HZ | ||
3492 | /* | ||
3493 | * If we were in the nohz mode recently and busy at the current | ||
3494 | * scheduler tick, then check if we need to nominate new idle | ||
3495 | * load balancer. | ||
3496 | */ | ||
3497 | if (rq->in_nohz_recently && !rq->idle_at_tick) { | ||
3498 | rq->in_nohz_recently = 0; | ||
3499 | |||
3500 | if (atomic_read(&nohz.load_balancer) == cpu) { | ||
3501 | cpumask_clear_cpu(cpu, nohz.cpu_mask); | ||
3502 | atomic_set(&nohz.load_balancer, -1); | ||
3503 | } | ||
3504 | |||
3505 | if (atomic_read(&nohz.load_balancer) == -1) { | ||
3506 | int ilb = find_new_ilb(cpu); | ||
3507 | |||
3508 | if (ilb < nr_cpu_ids) | ||
3509 | resched_cpu(ilb); | ||
3510 | } | ||
3511 | } | ||
3512 | |||
3513 | /* | ||
3514 | * If this cpu is idle and doing idle load balancing for all the | ||
3515 | * cpus with ticks stopped, is it time for that to stop? | ||
3516 | */ | ||
3517 | if (rq->idle_at_tick && atomic_read(&nohz.load_balancer) == cpu && | ||
3518 | cpumask_weight(nohz.cpu_mask) == num_online_cpus()) { | ||
3519 | resched_cpu(cpu); | ||
3520 | return; | ||
3521 | } | ||
3522 | |||
3523 | /* | ||
3524 | * If this cpu is idle and the idle load balancing is done by | ||
3525 | * someone else, then no need raise the SCHED_SOFTIRQ | ||
3526 | */ | ||
3527 | if (rq->idle_at_tick && atomic_read(&nohz.load_balancer) != cpu && | ||
3528 | cpumask_test_cpu(cpu, nohz.cpu_mask)) | ||
3529 | return; | ||
3530 | #endif | ||
3531 | /* Don't need to rebalance while attached to NULL domain */ | ||
3532 | if (time_after_eq(jiffies, rq->next_balance) && | ||
3533 | likely(!on_null_domain(cpu))) | ||
3534 | raise_softirq(SCHED_SOFTIRQ); | ||
3535 | } | ||
1954 | 3536 | ||
1955 | static void rq_online_fair(struct rq *rq) | 3537 | static void rq_online_fair(struct rq *rq) |
1956 | { | 3538 | { |
@@ -1962,6 +3544,15 @@ static void rq_offline_fair(struct rq *rq) | |||
1962 | update_sysctl(); | 3544 | update_sysctl(); |
1963 | } | 3545 | } |
1964 | 3546 | ||
3547 | #else /* CONFIG_SMP */ | ||
3548 | |||
3549 | /* | ||
3550 | * on UP we do not need to balance between CPUs: | ||
3551 | */ | ||
3552 | static inline void idle_balance(int cpu, struct rq *rq) | ||
3553 | { | ||
3554 | } | ||
3555 | |||
1965 | #endif /* CONFIG_SMP */ | 3556 | #endif /* CONFIG_SMP */ |
1966 | 3557 | ||
1967 | /* | 3558 | /* |
@@ -2076,7 +3667,7 @@ static void moved_group_fair(struct task_struct *p, int on_rq) | |||
2076 | } | 3667 | } |
2077 | #endif | 3668 | #endif |
2078 | 3669 | ||
2079 | unsigned int get_rr_interval_fair(struct rq *rq, struct task_struct *task) | 3670 | static unsigned int get_rr_interval_fair(struct rq *rq, struct task_struct *task) |
2080 | { | 3671 | { |
2081 | struct sched_entity *se = &task->se; | 3672 | struct sched_entity *se = &task->se; |
2082 | unsigned int rr_interval = 0; | 3673 | unsigned int rr_interval = 0; |
@@ -2108,8 +3699,6 @@ static const struct sched_class fair_sched_class = { | |||
2108 | #ifdef CONFIG_SMP | 3699 | #ifdef CONFIG_SMP |
2109 | .select_task_rq = select_task_rq_fair, | 3700 | .select_task_rq = select_task_rq_fair, |
2110 | 3701 | ||
2111 | .load_balance = load_balance_fair, | ||
2112 | .move_one_task = move_one_task_fair, | ||
2113 | .rq_online = rq_online_fair, | 3702 | .rq_online = rq_online_fair, |
2114 | .rq_offline = rq_offline_fair, | 3703 | .rq_offline = rq_offline_fair, |
2115 | 3704 | ||