blob: 806d1b227a21060aac100994a8992266c00b59b5 [file] [log] [blame]
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001/*
2 * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH)
3 *
4 * Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
5 *
6 * Interactivity improvements by Mike Galbraith
7 * (C) 2007 Mike Galbraith <efault@gmx.de>
8 *
9 * Various enhancements by Dmitry Adamushko.
10 * (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
11 *
12 * Group scheduling enhancements by Srivatsa Vaddagiri
13 * Copyright IBM Corporation, 2007
14 * Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
15 *
16 * Scaled math optimizations by Thomas Gleixner
17 * Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
Peter Zijlstra21805082007-08-25 18:41:53 +020018 *
19 * Adaptive scheduling granularity, math enhancements by Peter Zijlstra
20 * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020021 */
22
Arjan van de Ven97455122008-01-25 21:08:34 +010023#include <linux/latencytop.h>
Christian Ehrhardt1983a922009-11-30 12:16:47 +010024#include <linux/sched.h>
Arjan van de Ven97455122008-01-25 21:08:34 +010025
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020026/*
Peter Zijlstra21805082007-08-25 18:41:53 +020027 * Targeted preemption latency for CPU-bound tasks:
Mike Galbraith172e0822009-09-09 15:41:37 +020028 * (default: 5ms * (1 + ilog(ncpus)), units: nanoseconds)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020029 *
Peter Zijlstra21805082007-08-25 18:41:53 +020030 * NOTE: this latency value is not the same as the concept of
Ingo Molnard274a4c2007-10-15 17:00:14 +020031 * 'timeslice length' - timeslices in CFS are of variable length
32 * and have no persistent notion like in traditional, time-slice
33 * based scheduling concepts.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020034 *
Ingo Molnard274a4c2007-10-15 17:00:14 +020035 * (to see the precise effective timeslice length of your workload,
36 * run vmstat and monitor the context-switches (cs) field)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020037 */
Mike Galbraith21406922010-03-11 17:17:15 +010038unsigned int sysctl_sched_latency = 6000000ULL;
39unsigned int normalized_sysctl_sched_latency = 6000000ULL;
Ingo Molnar2bd8e6d2007-10-15 17:00:02 +020040
41/*
Christian Ehrhardt1983a922009-11-30 12:16:47 +010042 * The initial- and re-scaling of tunables is configurable
43 * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus))
44 *
45 * Options are:
46 * SCHED_TUNABLESCALING_NONE - unscaled, always *1
47 * SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus)
48 * SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus
49 */
50enum sched_tunable_scaling sysctl_sched_tunable_scaling
51 = SCHED_TUNABLESCALING_LOG;
52
53/*
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010054 * Minimal preemption granularity for CPU-bound tasks:
Mike Galbraith21406922010-03-11 17:17:15 +010055 * (default: 2 msec * (1 + ilog(ncpus)), units: nanoseconds)
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010056 */
Mike Galbraith21406922010-03-11 17:17:15 +010057unsigned int sysctl_sched_min_granularity = 2000000ULL;
58unsigned int normalized_sysctl_sched_min_granularity = 2000000ULL;
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010059
60/*
61 * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
62 */
Mike Galbraith21406922010-03-11 17:17:15 +010063static unsigned int sched_nr_latency = 3;
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010064
65/*
Mike Galbraith2bba22c2009-09-09 15:41:37 +020066 * After fork, child runs first. If set to 0 (default) then
Ingo Molnar2bd8e6d2007-10-15 17:00:02 +020067 * parent will (try to) run first.
68 */
Mike Galbraith2bba22c2009-09-09 15:41:37 +020069unsigned int sysctl_sched_child_runs_first __read_mostly;
Peter Zijlstra21805082007-08-25 18:41:53 +020070
71/*
Ingo Molnar1799e352007-09-19 23:34:46 +020072 * sys_sched_yield() compat mode
73 *
74 * This option switches the agressive yield implementation of the
75 * old scheduler back on.
76 */
77unsigned int __read_mostly sysctl_sched_compat_yield;
78
79/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020080 * SCHED_OTHER wake-up granularity.
Mike Galbraith172e0822009-09-09 15:41:37 +020081 * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020082 *
83 * This option delays the preemption effects of decoupled workloads
84 * and reduces their over-scheduling. Synchronous workloads will still
85 * have immediate wakeup/sleep latencies.
86 */
Mike Galbraith172e0822009-09-09 15:41:37 +020087unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
Christian Ehrhardt0bcdcf22009-11-30 12:16:46 +010088unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020089
Ingo Molnarda84d962007-10-15 17:00:18 +020090const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
91
Peter Zijlstraa4c2f002008-10-17 19:27:03 +020092static const struct sched_class fair_sched_class;
93
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020094/**************************************************************
95 * CFS operations on generic schedulable entities:
96 */
97
98#ifdef CONFIG_FAIR_GROUP_SCHED
99
100/* cpu runqueue to which this cfs_rq is attached */
101static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
102{
103 return cfs_rq->rq;
104}
105
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200106/* An entity is a task if it doesn't "own" a runqueue */
107#define entity_is_task(se) (!se->my_q)
108
Peter Zijlstra8f488942009-07-24 12:25:30 +0200109static inline struct task_struct *task_of(struct sched_entity *se)
110{
111#ifdef CONFIG_SCHED_DEBUG
112 WARN_ON_ONCE(!entity_is_task(se));
113#endif
114 return container_of(se, struct task_struct, se);
115}
116
Peter Zijlstrab7581492008-04-19 19:45:00 +0200117/* Walk up scheduling entities hierarchy */
118#define for_each_sched_entity(se) \
119 for (; se; se = se->parent)
120
121static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
122{
123 return p->se.cfs_rq;
124}
125
126/* runqueue on which this entity is (to be) queued */
127static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
128{
129 return se->cfs_rq;
130}
131
132/* runqueue "owned" by this group */
133static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
134{
135 return grp->my_q;
136}
137
138/* Given a group's cfs_rq on one cpu, return its corresponding cfs_rq on
139 * another cpu ('this_cpu')
140 */
141static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
142{
143 return cfs_rq->tg->cfs_rq[this_cpu];
144}
145
146/* Iterate thr' all leaf cfs_rq's on a runqueue */
147#define for_each_leaf_cfs_rq(rq, cfs_rq) \
148 list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
149
150/* Do the two (enqueued) entities belong to the same group ? */
151static inline int
152is_same_group(struct sched_entity *se, struct sched_entity *pse)
153{
154 if (se->cfs_rq == pse->cfs_rq)
155 return 1;
156
157 return 0;
158}
159
160static inline struct sched_entity *parent_entity(struct sched_entity *se)
161{
162 return se->parent;
163}
164
Peter Zijlstra464b7522008-10-24 11:06:15 +0200165/* return depth at which a sched entity is present in the hierarchy */
166static inline int depth_se(struct sched_entity *se)
167{
168 int depth = 0;
169
170 for_each_sched_entity(se)
171 depth++;
172
173 return depth;
174}
175
176static void
177find_matching_se(struct sched_entity **se, struct sched_entity **pse)
178{
179 int se_depth, pse_depth;
180
181 /*
182 * preemption test can be made between sibling entities who are in the
183 * same cfs_rq i.e who have a common parent. Walk up the hierarchy of
184 * both tasks until we find their ancestors who are siblings of common
185 * parent.
186 */
187
188 /* First walk up until both entities are at same depth */
189 se_depth = depth_se(*se);
190 pse_depth = depth_se(*pse);
191
192 while (se_depth > pse_depth) {
193 se_depth--;
194 *se = parent_entity(*se);
195 }
196
197 while (pse_depth > se_depth) {
198 pse_depth--;
199 *pse = parent_entity(*pse);
200 }
201
202 while (!is_same_group(*se, *pse)) {
203 *se = parent_entity(*se);
204 *pse = parent_entity(*pse);
205 }
206}
207
Peter Zijlstra8f488942009-07-24 12:25:30 +0200208#else /* !CONFIG_FAIR_GROUP_SCHED */
209
210static inline struct task_struct *task_of(struct sched_entity *se)
211{
212 return container_of(se, struct task_struct, se);
213}
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200214
215static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
216{
217 return container_of(cfs_rq, struct rq, cfs);
218}
219
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200220#define entity_is_task(se) 1
221
Peter Zijlstrab7581492008-04-19 19:45:00 +0200222#define for_each_sched_entity(se) \
223 for (; se; se = NULL)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200224
Peter Zijlstrab7581492008-04-19 19:45:00 +0200225static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200226{
Peter Zijlstrab7581492008-04-19 19:45:00 +0200227 return &task_rq(p)->cfs;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200228}
229
Peter Zijlstrab7581492008-04-19 19:45:00 +0200230static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
231{
232 struct task_struct *p = task_of(se);
233 struct rq *rq = task_rq(p);
234
235 return &rq->cfs;
236}
237
238/* runqueue "owned" by this group */
239static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
240{
241 return NULL;
242}
243
244static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
245{
246 return &cpu_rq(this_cpu)->cfs;
247}
248
249#define for_each_leaf_cfs_rq(rq, cfs_rq) \
250 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
251
252static inline int
253is_same_group(struct sched_entity *se, struct sched_entity *pse)
254{
255 return 1;
256}
257
258static inline struct sched_entity *parent_entity(struct sched_entity *se)
259{
260 return NULL;
261}
262
Peter Zijlstra464b7522008-10-24 11:06:15 +0200263static inline void
264find_matching_se(struct sched_entity **se, struct sched_entity **pse)
265{
266}
267
Peter Zijlstrab7581492008-04-19 19:45:00 +0200268#endif /* CONFIG_FAIR_GROUP_SCHED */
269
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200270
271/**************************************************************
272 * Scheduling class tree data structure manipulation methods:
273 */
274
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200275static inline u64 max_vruntime(u64 min_vruntime, u64 vruntime)
Peter Zijlstra02e04312007-10-15 17:00:07 +0200276{
Peter Zijlstra368059a2007-10-15 17:00:11 +0200277 s64 delta = (s64)(vruntime - min_vruntime);
278 if (delta > 0)
Peter Zijlstra02e04312007-10-15 17:00:07 +0200279 min_vruntime = vruntime;
280
281 return min_vruntime;
282}
283
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200284static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
Peter Zijlstrab0ffd242007-10-15 17:00:12 +0200285{
286 s64 delta = (s64)(vruntime - min_vruntime);
287 if (delta < 0)
288 min_vruntime = vruntime;
289
290 return min_vruntime;
291}
292
Fabio Checconi54fdc582009-07-16 12:32:27 +0200293static inline int entity_before(struct sched_entity *a,
294 struct sched_entity *b)
295{
296 return (s64)(a->vruntime - b->vruntime) < 0;
297}
298
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200299static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
Peter Zijlstra90146232007-10-15 17:00:05 +0200300{
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200301 return se->vruntime - cfs_rq->min_vruntime;
Peter Zijlstra90146232007-10-15 17:00:05 +0200302}
303
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200304static void update_min_vruntime(struct cfs_rq *cfs_rq)
305{
306 u64 vruntime = cfs_rq->min_vruntime;
307
308 if (cfs_rq->curr)
309 vruntime = cfs_rq->curr->vruntime;
310
311 if (cfs_rq->rb_leftmost) {
312 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
313 struct sched_entity,
314 run_node);
315
Peter Zijlstrae17036d2009-01-15 14:53:39 +0100316 if (!cfs_rq->curr)
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200317 vruntime = se->vruntime;
318 else
319 vruntime = min_vruntime(vruntime, se->vruntime);
320 }
321
322 cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
323}
324
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200325/*
326 * Enqueue an entity into the rb-tree:
327 */
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200328static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200329{
330 struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
331 struct rb_node *parent = NULL;
332 struct sched_entity *entry;
Peter Zijlstra90146232007-10-15 17:00:05 +0200333 s64 key = entity_key(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200334 int leftmost = 1;
335
336 /*
337 * Find the right place in the rbtree:
338 */
339 while (*link) {
340 parent = *link;
341 entry = rb_entry(parent, struct sched_entity, run_node);
342 /*
343 * We dont care about collisions. Nodes with
344 * the same key stay together.
345 */
Peter Zijlstra90146232007-10-15 17:00:05 +0200346 if (key < entity_key(cfs_rq, entry)) {
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200347 link = &parent->rb_left;
348 } else {
349 link = &parent->rb_right;
350 leftmost = 0;
351 }
352 }
353
354 /*
355 * Maintain a cache of leftmost tree entries (it is frequently
356 * used):
357 */
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200358 if (leftmost)
Ingo Molnar57cb4992007-10-15 17:00:11 +0200359 cfs_rq->rb_leftmost = &se->run_node;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200360
361 rb_link_node(&se->run_node, parent, link);
362 rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200363}
364
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200365static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200366{
Peter Zijlstra3fe69742008-03-14 20:55:51 +0100367 if (cfs_rq->rb_leftmost == &se->run_node) {
368 struct rb_node *next_node;
Peter Zijlstra3fe69742008-03-14 20:55:51 +0100369
370 next_node = rb_next(&se->run_node);
371 cfs_rq->rb_leftmost = next_node;
Peter Zijlstra3fe69742008-03-14 20:55:51 +0100372 }
Ingo Molnare9acbff2007-10-15 17:00:04 +0200373
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200374 rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200375}
376
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200377static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
378{
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100379 struct rb_node *left = cfs_rq->rb_leftmost;
380
381 if (!left)
382 return NULL;
383
384 return rb_entry(left, struct sched_entity, run_node);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200385}
386
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100387static struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200388{
Ingo Molnar7eee3e62008-02-22 10:32:21 +0100389 struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200390
Balbir Singh70eee742008-02-22 13:25:53 +0530391 if (!last)
392 return NULL;
Ingo Molnar7eee3e62008-02-22 10:32:21 +0100393
394 return rb_entry(last, struct sched_entity, run_node);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200395}
396
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200397/**************************************************************
398 * Scheduling class statistics methods:
399 */
400
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100401#ifdef CONFIG_SCHED_DEBUG
Christian Ehrhardtacb4a842009-11-30 12:16:48 +0100402int sched_proc_update_handler(struct ctl_table *table, int write,
Alexey Dobriyan8d65af72009-09-23 15:57:19 -0700403 void __user *buffer, size_t *lenp,
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100404 loff_t *ppos)
405{
Alexey Dobriyan8d65af72009-09-23 15:57:19 -0700406 int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
Christian Ehrhardtacb4a842009-11-30 12:16:48 +0100407 int factor = get_update_sysctl_factor();
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100408
409 if (ret || !write)
410 return ret;
411
412 sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
413 sysctl_sched_min_granularity);
414
Christian Ehrhardtacb4a842009-11-30 12:16:48 +0100415#define WRT_SYSCTL(name) \
416 (normalized_sysctl_##name = sysctl_##name / (factor))
417 WRT_SYSCTL(sched_min_granularity);
418 WRT_SYSCTL(sched_latency);
419 WRT_SYSCTL(sched_wakeup_granularity);
420 WRT_SYSCTL(sched_shares_ratelimit);
421#undef WRT_SYSCTL
422
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100423 return 0;
424}
425#endif
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200426
427/*
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200428 * delta /= w
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200429 */
430static inline unsigned long
431calc_delta_fair(unsigned long delta, struct sched_entity *se)
432{
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200433 if (unlikely(se->load.weight != NICE_0_LOAD))
434 delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200435
436 return delta;
437}
438
439/*
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200440 * The idea is to set a period in which each task runs once.
441 *
442 * When there are too many tasks (sysctl_sched_nr_latency) we have to stretch
443 * this period because otherwise the slices get too small.
444 *
445 * p = (nr <= nl) ? l : l*nr/nl
446 */
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200447static u64 __sched_period(unsigned long nr_running)
448{
449 u64 period = sysctl_sched_latency;
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100450 unsigned long nr_latency = sched_nr_latency;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200451
452 if (unlikely(nr_running > nr_latency)) {
Peter Zijlstra4bf0b772008-01-25 21:08:21 +0100453 period = sysctl_sched_min_granularity;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200454 period *= nr_running;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200455 }
456
457 return period;
458}
459
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200460/*
461 * We calculate the wall-time slice from the period by taking a part
462 * proportional to the weight.
463 *
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200464 * s = p*P[w/rw]
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200465 */
Peter Zijlstra6d0f0eb2007-10-15 17:00:05 +0200466static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
Peter Zijlstra21805082007-08-25 18:41:53 +0200467{
Mike Galbraith0a582442009-01-02 12:16:42 +0100468 u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200469
Mike Galbraith0a582442009-01-02 12:16:42 +0100470 for_each_sched_entity(se) {
Lin Ming6272d682009-01-15 17:17:15 +0100471 struct load_weight *load;
Christian Engelmayer3104bf02009-06-16 10:35:12 +0200472 struct load_weight lw;
Lin Ming6272d682009-01-15 17:17:15 +0100473
474 cfs_rq = cfs_rq_of(se);
475 load = &cfs_rq->load;
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200476
Mike Galbraith0a582442009-01-02 12:16:42 +0100477 if (unlikely(!se->on_rq)) {
Christian Engelmayer3104bf02009-06-16 10:35:12 +0200478 lw = cfs_rq->load;
Mike Galbraith0a582442009-01-02 12:16:42 +0100479
480 update_load_add(&lw, se->load.weight);
481 load = &lw;
482 }
483 slice = calc_delta_mine(slice, se->load.weight, load);
484 }
485 return slice;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200486}
487
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200488/*
Peter Zijlstraac884de2008-04-19 19:45:00 +0200489 * We calculate the vruntime slice of a to be inserted task
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200490 *
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200491 * vs = s/w
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200492 */
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200493static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200494{
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200495 return calc_delta_fair(sched_slice(cfs_rq, se), se);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200496}
497
498/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200499 * Update the current task's runtime statistics. Skip current tasks that
500 * are not in our scheduling class.
501 */
502static inline void
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200503__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
504 unsigned long delta_exec)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200505{
Ingo Molnarbbdba7c2007-10-15 17:00:06 +0200506 unsigned long delta_exec_weighted;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200507
Lucas De Marchi41acab82010-03-10 23:37:45 -0300508 schedstat_set(curr->statistics.exec_max,
509 max((u64)delta_exec, curr->statistics.exec_max));
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200510
511 curr->sum_exec_runtime += delta_exec;
Ingo Molnar7a62eab2007-10-15 17:00:06 +0200512 schedstat_add(cfs_rq, exec_clock, delta_exec);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200513 delta_exec_weighted = calc_delta_fair(delta_exec, curr);
Peter Zijlstra88ec22d2009-12-16 18:04:41 +0100514
Ingo Molnare9acbff2007-10-15 17:00:04 +0200515 curr->vruntime += delta_exec_weighted;
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200516 update_min_vruntime(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200517}
518
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200519static void update_curr(struct cfs_rq *cfs_rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200520{
Ingo Molnar429d43b2007-10-15 17:00:03 +0200521 struct sched_entity *curr = cfs_rq->curr;
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200522 u64 now = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200523 unsigned long delta_exec;
524
525 if (unlikely(!curr))
526 return;
527
528 /*
529 * Get the amount of time the current task was running
530 * since the last time we changed load (this cannot
531 * overflow on 32 bits):
532 */
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200533 delta_exec = (unsigned long)(now - curr->exec_start);
Peter Zijlstra34f28ec2008-12-16 08:45:31 +0100534 if (!delta_exec)
535 return;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200536
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200537 __update_curr(cfs_rq, curr, delta_exec);
538 curr->exec_start = now;
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100539
540 if (entity_is_task(curr)) {
541 struct task_struct *curtask = task_of(curr);
542
Ingo Molnarf977bb42009-09-13 18:15:54 +0200543 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100544 cpuacct_charge(curtask, delta_exec);
Frank Mayharf06febc2008-09-12 09:54:39 -0700545 account_group_exec_runtime(curtask, delta_exec);
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100546 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200547}
548
549static inline void
Ingo Molnar5870db52007-08-09 11:16:47 +0200550update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200551{
Lucas De Marchi41acab82010-03-10 23:37:45 -0300552 schedstat_set(se->statistics.wait_start, rq_of(cfs_rq)->clock);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200553}
554
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200555/*
556 * Task is being enqueued - update stats:
557 */
Ingo Molnard2417e52007-08-09 11:16:47 +0200558static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200559{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200560 /*
561 * Are we enqueueing a waiting task? (for current tasks
562 * a dequeue/enqueue event is a NOP)
563 */
Ingo Molnar429d43b2007-10-15 17:00:03 +0200564 if (se != cfs_rq->curr)
Ingo Molnar5870db52007-08-09 11:16:47 +0200565 update_stats_wait_start(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200566}
567
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200568static void
Ingo Molnar9ef0a962007-08-09 11:16:47 +0200569update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200570{
Lucas De Marchi41acab82010-03-10 23:37:45 -0300571 schedstat_set(se->statistics.wait_max, max(se->statistics.wait_max,
572 rq_of(cfs_rq)->clock - se->statistics.wait_start));
573 schedstat_set(se->statistics.wait_count, se->statistics.wait_count + 1);
574 schedstat_set(se->statistics.wait_sum, se->statistics.wait_sum +
575 rq_of(cfs_rq)->clock - se->statistics.wait_start);
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200576#ifdef CONFIG_SCHEDSTATS
577 if (entity_is_task(se)) {
578 trace_sched_stat_wait(task_of(se),
Lucas De Marchi41acab82010-03-10 23:37:45 -0300579 rq_of(cfs_rq)->clock - se->statistics.wait_start);
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200580 }
581#endif
Lucas De Marchi41acab82010-03-10 23:37:45 -0300582 schedstat_set(se->statistics.wait_start, 0);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200583}
584
585static inline void
Ingo Molnar19b6a2e2007-08-09 11:16:48 +0200586update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200587{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200588 /*
589 * Mark the end of the wait period if dequeueing a
590 * waiting task:
591 */
Ingo Molnar429d43b2007-10-15 17:00:03 +0200592 if (se != cfs_rq->curr)
Ingo Molnar9ef0a962007-08-09 11:16:47 +0200593 update_stats_wait_end(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200594}
595
596/*
597 * We are picking a new current task - update its stats:
598 */
599static inline void
Ingo Molnar79303e92007-08-09 11:16:47 +0200600update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200601{
602 /*
603 * We are starting a new run period:
604 */
Ingo Molnard2819182007-08-09 11:16:47 +0200605 se->exec_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200606}
607
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200608/**************************************************
609 * Scheduling class queueing methods:
610 */
611
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200612#if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
613static void
614add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
615{
616 cfs_rq->task_weight += weight;
617}
618#else
619static inline void
620add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
621{
622}
623#endif
624
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200625static void
626account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
627{
628 update_load_add(&cfs_rq->load, se->load.weight);
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200629 if (!parent_entity(se))
630 inc_cpu_load(rq_of(cfs_rq), se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530631 if (entity_is_task(se)) {
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200632 add_cfs_task_weight(cfs_rq, se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530633 list_add(&se->group_node, &cfs_rq->tasks);
634 }
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200635 cfs_rq->nr_running++;
636 se->on_rq = 1;
637}
638
639static void
640account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
641{
642 update_load_sub(&cfs_rq->load, se->load.weight);
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200643 if (!parent_entity(se))
644 dec_cpu_load(rq_of(cfs_rq), se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530645 if (entity_is_task(se)) {
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200646 add_cfs_task_weight(cfs_rq, -se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530647 list_del_init(&se->group_node);
648 }
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200649 cfs_rq->nr_running--;
650 se->on_rq = 0;
651}
652
Ingo Molnar2396af62007-08-09 11:16:48 +0200653static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200654{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200655#ifdef CONFIG_SCHEDSTATS
Peter Zijlstrae4143142009-07-23 20:13:26 +0200656 struct task_struct *tsk = NULL;
657
658 if (entity_is_task(se))
659 tsk = task_of(se);
660
Lucas De Marchi41acab82010-03-10 23:37:45 -0300661 if (se->statistics.sleep_start) {
662 u64 delta = rq_of(cfs_rq)->clock - se->statistics.sleep_start;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200663
664 if ((s64)delta < 0)
665 delta = 0;
666
Lucas De Marchi41acab82010-03-10 23:37:45 -0300667 if (unlikely(delta > se->statistics.sleep_max))
668 se->statistics.sleep_max = delta;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200669
Lucas De Marchi41acab82010-03-10 23:37:45 -0300670 se->statistics.sleep_start = 0;
671 se->statistics.sum_sleep_runtime += delta;
Arjan van de Ven97455122008-01-25 21:08:34 +0100672
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200673 if (tsk) {
Peter Zijlstrae4143142009-07-23 20:13:26 +0200674 account_scheduler_latency(tsk, delta >> 10, 1);
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200675 trace_sched_stat_sleep(tsk, delta);
676 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200677 }
Lucas De Marchi41acab82010-03-10 23:37:45 -0300678 if (se->statistics.block_start) {
679 u64 delta = rq_of(cfs_rq)->clock - se->statistics.block_start;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200680
681 if ((s64)delta < 0)
682 delta = 0;
683
Lucas De Marchi41acab82010-03-10 23:37:45 -0300684 if (unlikely(delta > se->statistics.block_max))
685 se->statistics.block_max = delta;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200686
Lucas De Marchi41acab82010-03-10 23:37:45 -0300687 se->statistics.block_start = 0;
688 se->statistics.sum_sleep_runtime += delta;
Ingo Molnar30084fb2007-10-02 14:13:08 +0200689
Peter Zijlstrae4143142009-07-23 20:13:26 +0200690 if (tsk) {
Arjan van de Ven8f0dfc32009-07-20 11:26:58 -0700691 if (tsk->in_iowait) {
Lucas De Marchi41acab82010-03-10 23:37:45 -0300692 se->statistics.iowait_sum += delta;
693 se->statistics.iowait_count++;
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200694 trace_sched_stat_iowait(tsk, delta);
Arjan van de Ven8f0dfc32009-07-20 11:26:58 -0700695 }
696
Peter Zijlstrae4143142009-07-23 20:13:26 +0200697 /*
698 * Blocking time is in units of nanosecs, so shift by
699 * 20 to get a milliseconds-range estimation of the
700 * amount of time that the task spent sleeping:
701 */
702 if (unlikely(prof_on == SLEEP_PROFILING)) {
703 profile_hits(SLEEP_PROFILING,
704 (void *)get_wchan(tsk),
705 delta >> 20);
706 }
707 account_scheduler_latency(tsk, delta >> 10, 0);
Ingo Molnar30084fb2007-10-02 14:13:08 +0200708 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200709 }
710#endif
711}
712
Peter Zijlstraddc97292007-10-15 17:00:10 +0200713static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
714{
715#ifdef CONFIG_SCHED_DEBUG
716 s64 d = se->vruntime - cfs_rq->min_vruntime;
717
718 if (d < 0)
719 d = -d;
720
721 if (d > 3*sysctl_sched_latency)
722 schedstat_inc(cfs_rq, nr_spread_over);
723#endif
724}
725
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200726static void
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200727place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
728{
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200729 u64 vruntime = cfs_rq->min_vruntime;
Peter Zijlstra94dfb5e2007-10-15 17:00:05 +0200730
Peter Zijlstra2cb86002007-11-09 22:39:37 +0100731 /*
732 * The 'current' period is already promised to the current tasks,
733 * however the extra weight of the new task will slow them down a
734 * little, place the new task so that it fits in the slot that
735 * stays open at the end.
736 */
Peter Zijlstra94dfb5e2007-10-15 17:00:05 +0200737 if (initial && sched_feat(START_DEBIT))
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200738 vruntime += sched_vslice(cfs_rq, se);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200739
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200740 /* sleeps up to a single latency don't count. */
Mike Galbraith5ca98802010-03-11 17:17:17 +0100741 if (!initial) {
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200742 unsigned long thresh = sysctl_sched_latency;
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200743
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200744 /*
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200745 * Halve their sleep time's effect, to allow
746 * for a gentler effect of sleepers:
747 */
748 if (sched_feat(GENTLE_FAIR_SLEEPERS))
749 thresh >>= 1;
Ingo Molnar51e03042009-09-16 08:54:45 +0200750
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200751 vruntime -= thresh;
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200752 }
753
Mike Galbraithb5d9d732009-09-08 11:12:28 +0200754 /* ensure we never gain time by being placed backwards. */
755 vruntime = max_vruntime(se->vruntime, vruntime);
756
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200757 se->vruntime = vruntime;
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200758}
759
760static void
Peter Zijlstra88ec22d2009-12-16 18:04:41 +0100761enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200762{
763 /*
Peter Zijlstra88ec22d2009-12-16 18:04:41 +0100764 * Update the normalized vruntime before updating min_vruntime
765 * through callig update_curr().
766 */
Peter Zijlstra371fd7e2010-03-24 16:38:48 +0100767 if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
Peter Zijlstra88ec22d2009-12-16 18:04:41 +0100768 se->vruntime += cfs_rq->min_vruntime;
769
770 /*
Dmitry Adamushkoa2a2d682007-10-15 17:00:13 +0200771 * Update run-time statistics of the 'current'.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200772 */
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200773 update_curr(cfs_rq);
Peter Zijlstraa9922412008-05-05 23:56:17 +0200774 account_entity_enqueue(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200775
Peter Zijlstra88ec22d2009-12-16 18:04:41 +0100776 if (flags & ENQUEUE_WAKEUP) {
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200777 place_entity(cfs_rq, se, 0);
Ingo Molnar2396af62007-08-09 11:16:48 +0200778 enqueue_sleeper(cfs_rq, se);
Ingo Molnare9acbff2007-10-15 17:00:04 +0200779 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200780
Ingo Molnard2417e52007-08-09 11:16:47 +0200781 update_stats_enqueue(cfs_rq, se);
Peter Zijlstraddc97292007-10-15 17:00:10 +0200782 check_spread(cfs_rq, se);
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200783 if (se != cfs_rq->curr)
784 __enqueue_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200785}
786
Peter Zijlstraa571bbe2009-01-28 14:51:40 +0100787static void __clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
Peter Zijlstra2002c692008-11-11 11:52:33 +0100788{
Peter Zijlstrade69a802009-09-17 09:01:20 +0200789 if (!se || cfs_rq->last == se)
Peter Zijlstra2002c692008-11-11 11:52:33 +0100790 cfs_rq->last = NULL;
791
Peter Zijlstrade69a802009-09-17 09:01:20 +0200792 if (!se || cfs_rq->next == se)
Peter Zijlstra2002c692008-11-11 11:52:33 +0100793 cfs_rq->next = NULL;
794}
795
Peter Zijlstraa571bbe2009-01-28 14:51:40 +0100796static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
797{
798 for_each_sched_entity(se)
799 __clear_buddies(cfs_rq_of(se), se);
800}
801
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200802static void
Peter Zijlstra371fd7e2010-03-24 16:38:48 +0100803dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200804{
Dmitry Adamushkoa2a2d682007-10-15 17:00:13 +0200805 /*
806 * Update run-time statistics of the 'current'.
807 */
808 update_curr(cfs_rq);
809
Ingo Molnar19b6a2e2007-08-09 11:16:48 +0200810 update_stats_dequeue(cfs_rq, se);
Peter Zijlstra371fd7e2010-03-24 16:38:48 +0100811 if (flags & DEQUEUE_SLEEP) {
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200812#ifdef CONFIG_SCHEDSTATS
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200813 if (entity_is_task(se)) {
814 struct task_struct *tsk = task_of(se);
815
816 if (tsk->state & TASK_INTERRUPTIBLE)
Lucas De Marchi41acab82010-03-10 23:37:45 -0300817 se->statistics.sleep_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200818 if (tsk->state & TASK_UNINTERRUPTIBLE)
Lucas De Marchi41acab82010-03-10 23:37:45 -0300819 se->statistics.block_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200820 }
Dmitry Adamushkodb36cc72007-10-15 17:00:06 +0200821#endif
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200822 }
823
Peter Zijlstra2002c692008-11-11 11:52:33 +0100824 clear_buddies(cfs_rq, se);
Peter Zijlstra47932412008-11-04 21:25:09 +0100825
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200826 if (se != cfs_rq->curr)
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200827 __dequeue_entity(cfs_rq, se);
828 account_entity_dequeue(cfs_rq, se);
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200829 update_min_vruntime(cfs_rq);
Peter Zijlstra88ec22d2009-12-16 18:04:41 +0100830
831 /*
832 * Normalize the entity after updating the min_vruntime because the
833 * update can refer to the ->curr item and we need to reflect this
834 * movement in our normalized position.
835 */
Peter Zijlstra371fd7e2010-03-24 16:38:48 +0100836 if (!(flags & DEQUEUE_SLEEP))
Peter Zijlstra88ec22d2009-12-16 18:04:41 +0100837 se->vruntime -= cfs_rq->min_vruntime;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200838}
839
840/*
841 * Preempt the current task with a newly woken task if needed:
842 */
Peter Zijlstra7c92e542007-09-05 14:32:49 +0200843static void
Ingo Molnar2e09bf52007-10-15 17:00:05 +0200844check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200845{
Peter Zijlstra11697832007-09-05 14:32:49 +0200846 unsigned long ideal_runtime, delta_exec;
847
Peter Zijlstra6d0f0eb2007-10-15 17:00:05 +0200848 ideal_runtime = sched_slice(cfs_rq, curr);
Peter Zijlstra11697832007-09-05 14:32:49 +0200849 delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
Mike Galbraitha9f3e2b2009-01-28 14:51:39 +0100850 if (delta_exec > ideal_runtime) {
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200851 resched_task(rq_of(cfs_rq)->curr);
Mike Galbraitha9f3e2b2009-01-28 14:51:39 +0100852 /*
853 * The current task ran long enough, ensure it doesn't get
854 * re-elected due to buddy favours.
855 */
856 clear_buddies(cfs_rq, curr);
Mike Galbraithf685cea2009-10-23 23:09:22 +0200857 return;
858 }
859
860 /*
861 * Ensure that a task that missed wakeup preemption by a
862 * narrow margin doesn't have to wait for a full slice.
863 * This also mitigates buddy induced latencies under load.
864 */
865 if (!sched_feat(WAKEUP_PREEMPT))
866 return;
867
868 if (delta_exec < sysctl_sched_min_granularity)
869 return;
870
871 if (cfs_rq->nr_running > 1) {
872 struct sched_entity *se = __pick_next_entity(cfs_rq);
873 s64 delta = curr->vruntime - se->vruntime;
874
875 if (delta > ideal_runtime)
876 resched_task(rq_of(cfs_rq)->curr);
Mike Galbraitha9f3e2b2009-01-28 14:51:39 +0100877 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200878}
879
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200880static void
Ingo Molnar8494f412007-08-09 11:16:48 +0200881set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200882{
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200883 /* 'current' is not kept within the tree. */
884 if (se->on_rq) {
885 /*
886 * Any task has to be enqueued before it get to execute on
887 * a CPU. So account for the time it spent waiting on the
888 * runqueue.
889 */
890 update_stats_wait_end(cfs_rq, se);
891 __dequeue_entity(cfs_rq, se);
892 }
893
Ingo Molnar79303e92007-08-09 11:16:47 +0200894 update_stats_curr_start(cfs_rq, se);
Ingo Molnar429d43b2007-10-15 17:00:03 +0200895 cfs_rq->curr = se;
Ingo Molnareba1ed42007-10-15 17:00:02 +0200896#ifdef CONFIG_SCHEDSTATS
897 /*
898 * Track our maximum slice length, if the CPU's load is at
899 * least twice that of our own weight (i.e. dont track it
900 * when there are only lesser-weight tasks around):
901 */
Dmitry Adamushko495eca42007-10-15 17:00:06 +0200902 if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
Lucas De Marchi41acab82010-03-10 23:37:45 -0300903 se->statistics.slice_max = max(se->statistics.slice_max,
Ingo Molnareba1ed42007-10-15 17:00:02 +0200904 se->sum_exec_runtime - se->prev_sum_exec_runtime);
905 }
906#endif
Peter Zijlstra4a55b452007-09-05 14:32:49 +0200907 se->prev_sum_exec_runtime = se->sum_exec_runtime;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200908}
909
Peter Zijlstra3f3a4902008-10-24 11:06:16 +0200910static int
911wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
912
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100913static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
Peter Zijlstraaa2ac252008-03-14 21:12:12 +0100914{
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100915 struct sched_entity *se = __pick_next_entity(cfs_rq);
Mike Galbraithf685cea2009-10-23 23:09:22 +0200916 struct sched_entity *left = se;
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100917
Mike Galbraithf685cea2009-10-23 23:09:22 +0200918 if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
919 se = cfs_rq->next;
Peter Zijlstraaa2ac252008-03-14 21:12:12 +0100920
Mike Galbraithf685cea2009-10-23 23:09:22 +0200921 /*
922 * Prefer last buddy, try to return the CPU to a preempted task.
923 */
924 if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
925 se = cfs_rq->last;
926
927 clear_buddies(cfs_rq, se);
Peter Zijlstra47932412008-11-04 21:25:09 +0100928
929 return se;
Peter Zijlstraaa2ac252008-03-14 21:12:12 +0100930}
931
Ingo Molnarab6cde22007-08-09 11:16:48 +0200932static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200933{
934 /*
935 * If still on the runqueue then deactivate_task()
936 * was not called and update_curr() has to be done:
937 */
938 if (prev->on_rq)
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200939 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200940
Peter Zijlstraddc97292007-10-15 17:00:10 +0200941 check_spread(cfs_rq, prev);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200942 if (prev->on_rq) {
Ingo Molnar5870db52007-08-09 11:16:47 +0200943 update_stats_wait_start(cfs_rq, prev);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200944 /* Put 'current' back into the tree. */
945 __enqueue_entity(cfs_rq, prev);
946 }
Ingo Molnar429d43b2007-10-15 17:00:03 +0200947 cfs_rq->curr = NULL;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200948}
949
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100950static void
951entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200952{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200953 /*
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200954 * Update run-time statistics of the 'current'.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200955 */
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200956 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200957
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100958#ifdef CONFIG_SCHED_HRTICK
959 /*
960 * queued ticks are scheduled to match the slice, so don't bother
961 * validating it and just reschedule.
962 */
Harvey Harrison983ed7a2008-04-24 18:17:55 -0700963 if (queued) {
964 resched_task(rq_of(cfs_rq)->curr);
965 return;
966 }
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100967 /*
968 * don't let the period tick interfere with the hrtick preemption
969 */
970 if (!sched_feat(DOUBLE_TICK) &&
971 hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
972 return;
973#endif
974
Peter Zijlstrace6c1312007-10-15 17:00:14 +0200975 if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
Ingo Molnar2e09bf52007-10-15 17:00:05 +0200976 check_preempt_tick(cfs_rq, curr);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200977}
978
979/**************************************************
980 * CFS operations on tasks:
981 */
982
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100983#ifdef CONFIG_SCHED_HRTICK
984static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
985{
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100986 struct sched_entity *se = &p->se;
987 struct cfs_rq *cfs_rq = cfs_rq_of(se);
988
989 WARN_ON(task_rq(p) != rq);
990
991 if (hrtick_enabled(rq) && cfs_rq->nr_running > 1) {
992 u64 slice = sched_slice(cfs_rq, se);
993 u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
994 s64 delta = slice - ran;
995
996 if (delta < 0) {
997 if (rq->curr == p)
998 resched_task(p);
999 return;
1000 }
1001
1002 /*
1003 * Don't schedule slices shorter than 10000ns, that just
1004 * doesn't make sense. Rely on vruntime for fairness.
1005 */
Peter Zijlstra31656512008-07-18 18:01:23 +02001006 if (rq->curr != p)
Peter Zijlstra157124c2008-07-28 11:53:11 +02001007 delta = max_t(s64, 10000LL, delta);
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001008
Peter Zijlstra31656512008-07-18 18:01:23 +02001009 hrtick_start(rq, delta);
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001010 }
1011}
Peter Zijlstraa4c2f002008-10-17 19:27:03 +02001012
1013/*
1014 * called from enqueue/dequeue and updates the hrtick when the
1015 * current task is from our class and nr_running is low enough
1016 * to matter.
1017 */
1018static void hrtick_update(struct rq *rq)
1019{
1020 struct task_struct *curr = rq->curr;
1021
1022 if (curr->sched_class != &fair_sched_class)
1023 return;
1024
1025 if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
1026 hrtick_start_fair(rq, curr);
1027}
Dhaval Giani55e12e52008-06-24 23:39:43 +05301028#else /* !CONFIG_SCHED_HRTICK */
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001029static inline void
1030hrtick_start_fair(struct rq *rq, struct task_struct *p)
1031{
1032}
Peter Zijlstraa4c2f002008-10-17 19:27:03 +02001033
1034static inline void hrtick_update(struct rq *rq)
1035{
1036}
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001037#endif
1038
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001039/*
1040 * The enqueue_task method is called before nr_running is
1041 * increased. Here we update the fair scheduling stats and
1042 * then put the task into the rbtree:
1043 */
Thomas Gleixnerea87bb72010-01-20 20:58:57 +00001044static void
Peter Zijlstra371fd7e2010-03-24 16:38:48 +01001045enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001046{
1047 struct cfs_rq *cfs_rq;
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001048 struct sched_entity *se = &p->se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001049
1050 for_each_sched_entity(se) {
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001051 if (se->on_rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001052 break;
1053 cfs_rq = cfs_rq_of(se);
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01001054 enqueue_entity(cfs_rq, se, flags);
1055 flags = ENQUEUE_WAKEUP;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001056 }
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001057
Peter Zijlstraa4c2f002008-10-17 19:27:03 +02001058 hrtick_update(rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001059}
1060
1061/*
1062 * The dequeue_task method is called before nr_running is
1063 * decreased. We remove the task from the rbtree and
1064 * update the fair scheduling stats:
1065 */
Peter Zijlstra371fd7e2010-03-24 16:38:48 +01001066static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001067{
1068 struct cfs_rq *cfs_rq;
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001069 struct sched_entity *se = &p->se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001070
1071 for_each_sched_entity(se) {
1072 cfs_rq = cfs_rq_of(se);
Peter Zijlstra371fd7e2010-03-24 16:38:48 +01001073 dequeue_entity(cfs_rq, se, flags);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001074 /* Don't dequeue parent if it has other entities besides us */
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001075 if (cfs_rq->load.weight)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001076 break;
Peter Zijlstra371fd7e2010-03-24 16:38:48 +01001077 flags |= DEQUEUE_SLEEP;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001078 }
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001079
Peter Zijlstraa4c2f002008-10-17 19:27:03 +02001080 hrtick_update(rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001081}
1082
1083/*
Ingo Molnar1799e352007-09-19 23:34:46 +02001084 * sched_yield() support is very simple - we dequeue and enqueue.
1085 *
1086 * If compat_yield is turned on then we requeue to the end of the tree.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001087 */
Dmitry Adamushko4530d7a2007-10-15 17:00:08 +02001088static void yield_task_fair(struct rq *rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001089{
Ingo Molnardb292ca2007-12-04 17:04:39 +01001090 struct task_struct *curr = rq->curr;
1091 struct cfs_rq *cfs_rq = task_cfs_rq(curr);
1092 struct sched_entity *rightmost, *se = &curr->se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001093
1094 /*
Ingo Molnar1799e352007-09-19 23:34:46 +02001095 * Are we the only task in the tree?
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001096 */
Ingo Molnar1799e352007-09-19 23:34:46 +02001097 if (unlikely(cfs_rq->nr_running == 1))
1098 return;
1099
Peter Zijlstra2002c692008-11-11 11:52:33 +01001100 clear_buddies(cfs_rq, se);
1101
Ingo Molnardb292ca2007-12-04 17:04:39 +01001102 if (likely(!sysctl_sched_compat_yield) && curr->policy != SCHED_BATCH) {
Peter Zijlstra3e51f332008-05-03 18:29:28 +02001103 update_rq_clock(rq);
Ingo Molnar1799e352007-09-19 23:34:46 +02001104 /*
Dmitry Adamushkoa2a2d682007-10-15 17:00:13 +02001105 * Update run-time statistics of the 'current'.
Ingo Molnar1799e352007-09-19 23:34:46 +02001106 */
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +02001107 update_curr(cfs_rq);
Ingo Molnar1799e352007-09-19 23:34:46 +02001108
1109 return;
1110 }
1111 /*
1112 * Find the rightmost entry in the rbtree:
1113 */
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +02001114 rightmost = __pick_last_entity(cfs_rq);
Ingo Molnar1799e352007-09-19 23:34:46 +02001115 /*
1116 * Already in the rightmost position?
1117 */
Fabio Checconi54fdc582009-07-16 12:32:27 +02001118 if (unlikely(!rightmost || entity_before(rightmost, se)))
Ingo Molnar1799e352007-09-19 23:34:46 +02001119 return;
1120
1121 /*
1122 * Minimally necessary key value to be last in the tree:
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +02001123 * Upon rescheduling, sched_class::put_prev_task() will place
1124 * 'current' within the tree based on its new key value.
Ingo Molnar1799e352007-09-19 23:34:46 +02001125 */
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +02001126 se->vruntime = rightmost->vruntime + 1;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001127}
1128
Gregory Haskinse7693a32008-01-25 21:08:09 +01001129#ifdef CONFIG_SMP
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001130
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01001131static void task_waking_fair(struct rq *rq, struct task_struct *p)
1132{
1133 struct sched_entity *se = &p->se;
1134 struct cfs_rq *cfs_rq = cfs_rq_of(se);
1135
1136 se->vruntime -= cfs_rq->min_vruntime;
1137}
1138
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001139#ifdef CONFIG_FAIR_GROUP_SCHED
Peter Zijlstraf5bfb7d2008-06-27 13:41:39 +02001140/*
1141 * effective_load() calculates the load change as seen from the root_task_group
1142 *
1143 * Adding load to a group doesn't make a group heavier, but can cause movement
1144 * of group shares between cpus. Assuming the shares were perfectly aligned one
1145 * can calculate the shift in shares.
1146 *
1147 * The problem is that perfectly aligning the shares is rather expensive, hence
1148 * we try to avoid doing that too often - see update_shares(), which ratelimits
1149 * this change.
1150 *
1151 * We compensate this by not only taking the current delta into account, but
1152 * also considering the delta between when the shares were last adjusted and
1153 * now.
1154 *
1155 * We still saw a performance dip, some tracing learned us that between
1156 * cgroup:/ and cgroup:/foo balancing the number of affine wakeups increased
1157 * significantly. Therefore try to bias the error in direction of failing
1158 * the affine wakeup.
1159 *
1160 */
Peter Zijlstraf1d239f2008-06-27 13:41:38 +02001161static long effective_load(struct task_group *tg, int cpu,
1162 long wl, long wg)
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001163{
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001164 struct sched_entity *se = tg->se[cpu];
Peter Zijlstraf1d239f2008-06-27 13:41:38 +02001165
1166 if (!tg->parent)
1167 return wl;
1168
1169 /*
Peter Zijlstraf5bfb7d2008-06-27 13:41:39 +02001170 * By not taking the decrease of shares on the other cpu into
1171 * account our error leans towards reducing the affine wakeups.
1172 */
1173 if (!wl && sched_feat(ASYM_EFF_LOAD))
1174 return wl;
1175
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001176 for_each_sched_entity(se) {
Peter Zijlstracb5ef422008-06-27 13:41:32 +02001177 long S, rw, s, a, b;
Peter Zijlstra940959e2008-09-23 15:33:42 +02001178 long more_w;
1179
1180 /*
1181 * Instead of using this increment, also add the difference
1182 * between when the shares were last updated and now.
1183 */
1184 more_w = se->my_q->load.weight - se->my_q->rq_weight;
1185 wl += more_w;
1186 wg += more_w;
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001187
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001188 S = se->my_q->tg->shares;
1189 s = se->my_q->shares;
Peter Zijlstraf1d239f2008-06-27 13:41:38 +02001190 rw = se->my_q->rq_weight;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001191
Peter Zijlstracb5ef422008-06-27 13:41:32 +02001192 a = S*(rw + wl);
1193 b = S*rw + s*wg;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001194
Peter Zijlstra940959e2008-09-23 15:33:42 +02001195 wl = s*(a-b);
1196
1197 if (likely(b))
1198 wl /= b;
1199
Peter Zijlstra83378262008-06-27 13:41:37 +02001200 /*
1201 * Assume the group is already running and will
1202 * thus already be accounted for in the weight.
1203 *
1204 * That is, moving shares between CPUs, does not
1205 * alter the group weight.
1206 */
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001207 wg = 0;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001208 }
1209
1210 return wl;
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001211}
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001212
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001213#else
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001214
Peter Zijlstra83378262008-06-27 13:41:37 +02001215static inline unsigned long effective_load(struct task_group *tg, int cpu,
1216 unsigned long wl, unsigned long wg)
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001217{
Peter Zijlstra83378262008-06-27 13:41:37 +02001218 return wl;
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001219}
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001220
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001221#endif
1222
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001223static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001224{
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001225 unsigned long this_load, load;
1226 int idx, this_cpu, prev_cpu;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001227 unsigned long tl_per_task;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001228 struct task_group *tg;
Peter Zijlstra83378262008-06-27 13:41:37 +02001229 unsigned long weight;
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001230 int balanced;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001231
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001232 idx = sd->wake_idx;
1233 this_cpu = smp_processor_id();
1234 prev_cpu = task_cpu(p);
1235 load = source_load(prev_cpu, idx);
1236 this_load = target_load(this_cpu, idx);
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001237
1238 /*
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001239 * If sync wakeup then subtract the (maximum possible)
1240 * effect of the currently running task from the load
1241 * of the current CPU:
1242 */
Daniel J Bluemanf3b577d2010-06-01 14:06:13 +01001243 rcu_read_lock();
Peter Zijlstra83378262008-06-27 13:41:37 +02001244 if (sync) {
1245 tg = task_group(current);
1246 weight = current->se.load.weight;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001247
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001248 this_load += effective_load(tg, this_cpu, -weight, -weight);
Peter Zijlstra83378262008-06-27 13:41:37 +02001249 load += effective_load(tg, prev_cpu, 0, -weight);
1250 }
1251
1252 tg = task_group(p);
1253 weight = p->se.load.weight;
1254
Peter Zijlstra71a29aa2009-09-07 18:28:05 +02001255 /*
1256 * In low-load situations, where prev_cpu is idle and this_cpu is idle
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001257 * due to the sync cause above having dropped this_load to 0, we'll
1258 * always have an imbalance, but there's really nothing you can do
1259 * about that, so that's good too.
Peter Zijlstra71a29aa2009-09-07 18:28:05 +02001260 *
1261 * Otherwise check if either cpus are near enough in load to allow this
1262 * task to be woken on this_cpu.
1263 */
Peter Zijlstrae51fd5e2010-05-31 12:37:30 +02001264 if (this_load) {
1265 unsigned long this_eff_load, prev_eff_load;
1266
1267 this_eff_load = 100;
1268 this_eff_load *= power_of(prev_cpu);
1269 this_eff_load *= this_load +
1270 effective_load(tg, this_cpu, weight, weight);
1271
1272 prev_eff_load = 100 + (sd->imbalance_pct - 100) / 2;
1273 prev_eff_load *= power_of(this_cpu);
1274 prev_eff_load *= load + effective_load(tg, prev_cpu, 0, weight);
1275
1276 balanced = this_eff_load <= prev_eff_load;
1277 } else
1278 balanced = true;
Daniel J Bluemanf3b577d2010-06-01 14:06:13 +01001279 rcu_read_unlock();
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001280
1281 /*
1282 * If the currently running task will sleep within
1283 * a reasonable amount of time then attract this newly
1284 * woken task:
1285 */
Peter Zijlstra2fb76352008-10-08 09:16:04 +02001286 if (sync && balanced)
1287 return 1;
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001288
Lucas De Marchi41acab82010-03-10 23:37:45 -03001289 schedstat_inc(p, se.statistics.nr_wakeups_affine_attempts);
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001290 tl_per_task = cpu_avg_load_per_task(this_cpu);
1291
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001292 if (balanced ||
1293 (this_load <= load &&
1294 this_load + target_load(prev_cpu, idx) <= tl_per_task)) {
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001295 /*
1296 * This domain has SD_WAKE_AFFINE and
1297 * p is cache cold in this domain, and
1298 * there is no bad imbalance.
1299 */
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001300 schedstat_inc(sd, ttwu_move_affine);
Lucas De Marchi41acab82010-03-10 23:37:45 -03001301 schedstat_inc(p, se.statistics.nr_wakeups_affine);
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001302
1303 return 1;
1304 }
1305 return 0;
1306}
1307
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001308/*
1309 * find_idlest_group finds and returns the least busy CPU group within the
1310 * domain.
1311 */
1312static struct sched_group *
Peter Zijlstra78e7ed52009-09-03 13:16:51 +02001313find_idlest_group(struct sched_domain *sd, struct task_struct *p,
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001314 int this_cpu, int load_idx)
Gregory Haskinse7693a32008-01-25 21:08:09 +01001315{
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001316 struct sched_group *idlest = NULL, *this = NULL, *group = sd->groups;
1317 unsigned long min_load = ULONG_MAX, this_load = 0;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001318 int imbalance = 100 + (sd->imbalance_pct-100)/2;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001319
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001320 do {
1321 unsigned long load, avg_load;
1322 int local_group;
1323 int i;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001324
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001325 /* Skip over this group if it has no CPUs allowed */
1326 if (!cpumask_intersects(sched_group_cpus(group),
1327 &p->cpus_allowed))
1328 continue;
1329
1330 local_group = cpumask_test_cpu(this_cpu,
1331 sched_group_cpus(group));
1332
1333 /* Tally up the load of all CPUs in the group */
1334 avg_load = 0;
1335
1336 for_each_cpu(i, sched_group_cpus(group)) {
1337 /* Bias balancing toward cpus of our domain */
1338 if (local_group)
1339 load = source_load(i, load_idx);
1340 else
1341 load = target_load(i, load_idx);
1342
1343 avg_load += load;
1344 }
1345
1346 /* Adjust by relative CPU power of the group */
1347 avg_load = (avg_load * SCHED_LOAD_SCALE) / group->cpu_power;
1348
1349 if (local_group) {
1350 this_load = avg_load;
1351 this = group;
1352 } else if (avg_load < min_load) {
1353 min_load = avg_load;
1354 idlest = group;
1355 }
1356 } while (group = group->next, group != sd->groups);
1357
1358 if (!idlest || 100*this_load < imbalance*min_load)
1359 return NULL;
1360 return idlest;
1361}
1362
1363/*
1364 * find_idlest_cpu - find the idlest cpu among the cpus in group.
1365 */
1366static int
1367find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
1368{
1369 unsigned long load, min_load = ULONG_MAX;
1370 int idlest = -1;
1371 int i;
1372
1373 /* Traverse only the allowed CPUs */
1374 for_each_cpu_and(i, sched_group_cpus(group), &p->cpus_allowed) {
1375 load = weighted_cpuload(i);
1376
1377 if (load < min_load || (load == min_load && i == this_cpu)) {
1378 min_load = load;
1379 idlest = i;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001380 }
1381 }
1382
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001383 return idlest;
1384}
Gregory Haskinse7693a32008-01-25 21:08:09 +01001385
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001386/*
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001387 * Try and locate an idle CPU in the sched_domain.
1388 */
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001389static int select_idle_sibling(struct task_struct *p, int target)
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001390{
1391 int cpu = smp_processor_id();
1392 int prev_cpu = task_cpu(p);
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001393 struct sched_domain *sd;
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001394 int i;
1395
1396 /*
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001397 * If the task is going to be woken-up on this cpu and if it is
1398 * already idle, then it is the right target.
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001399 */
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001400 if (target == cpu && idle_cpu(cpu))
1401 return cpu;
1402
1403 /*
1404 * If the task is going to be woken-up on the cpu where it previously
1405 * ran and if it is currently idle, then it the right target.
1406 */
1407 if (target == prev_cpu && idle_cpu(prev_cpu))
Peter Zijlstrafe3bcfe2009-11-12 15:55:29 +01001408 return prev_cpu;
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001409
1410 /*
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001411 * Otherwise, iterate the domains and find an elegible idle cpu.
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001412 */
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001413 for_each_domain(target, sd) {
1414 if (!(sd->flags & SD_SHARE_PKG_RESOURCES))
Peter Zijlstrafe3bcfe2009-11-12 15:55:29 +01001415 break;
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001416
1417 for_each_cpu_and(i, sched_domain_span(sd), &p->cpus_allowed) {
1418 if (idle_cpu(i)) {
1419 target = i;
1420 break;
1421 }
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001422 }
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001423
1424 /*
1425 * Lets stop looking for an idle sibling when we reached
1426 * the domain that spans the current cpu and prev_cpu.
1427 */
1428 if (cpumask_test_cpu(cpu, sched_domain_span(sd)) &&
1429 cpumask_test_cpu(prev_cpu, sched_domain_span(sd)))
1430 break;
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001431 }
1432
1433 return target;
1434}
1435
1436/*
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001437 * sched_balance_self: balance the current task (running on cpu) in domains
1438 * that have the 'flag' flag set. In practice, this is SD_BALANCE_FORK and
1439 * SD_BALANCE_EXEC.
1440 *
1441 * Balance, ie. select the least loaded group.
1442 *
1443 * Returns the target CPU number, or the same CPU if no balancing is needed.
1444 *
1445 * preempt must be disabled.
1446 */
Peter Zijlstra0017d732010-03-24 18:34:10 +01001447static int
1448select_task_rq_fair(struct rq *rq, struct task_struct *p, int sd_flag, int wake_flags)
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001449{
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001450 struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001451 int cpu = smp_processor_id();
1452 int prev_cpu = task_cpu(p);
1453 int new_cpu = cpu;
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001454 int want_affine = 0;
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001455 int want_sd = 1;
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001456 int sync = wake_flags & WF_SYNC;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001457
Peter Zijlstra0763a662009-09-14 19:37:39 +02001458 if (sd_flag & SD_BALANCE_WAKE) {
Mike Galbraithbeac4c72010-03-11 17:17:20 +01001459 if (cpumask_test_cpu(cpu, &p->cpus_allowed))
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001460 want_affine = 1;
1461 new_cpu = prev_cpu;
1462 }
Gregory Haskinse7693a32008-01-25 21:08:09 +01001463
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001464 for_each_domain(cpu, tmp) {
Peter Zijlstrae4f42882009-12-16 18:04:34 +01001465 if (!(tmp->flags & SD_LOAD_BALANCE))
1466 continue;
1467
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001468 /*
Peter Zijlstraae154be2009-09-10 14:40:57 +02001469 * If power savings logic is enabled for a domain, see if we
1470 * are not overloaded, if so, don't balance wider.
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001471 */
Peter Zijlstra59abf022009-09-16 08:28:30 +02001472 if (tmp->flags & (SD_POWERSAVINGS_BALANCE|SD_PREFER_LOCAL)) {
Peter Zijlstraae154be2009-09-10 14:40:57 +02001473 unsigned long power = 0;
1474 unsigned long nr_running = 0;
1475 unsigned long capacity;
1476 int i;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001477
Peter Zijlstraae154be2009-09-10 14:40:57 +02001478 for_each_cpu(i, sched_domain_span(tmp)) {
1479 power += power_of(i);
1480 nr_running += cpu_rq(i)->cfs.nr_running;
1481 }
Gregory Haskinse7693a32008-01-25 21:08:09 +01001482
Peter Zijlstraae154be2009-09-10 14:40:57 +02001483 capacity = DIV_ROUND_CLOSEST(power, SCHED_LOAD_SCALE);
Ingo Molnar4ae7d5c2008-03-19 01:42:00 +01001484
Peter Zijlstra59abf022009-09-16 08:28:30 +02001485 if (tmp->flags & SD_POWERSAVINGS_BALANCE)
1486 nr_running /= 2;
1487
1488 if (nr_running < capacity)
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001489 want_sd = 0;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001490 }
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001491
Peter Zijlstrafe3bcfe2009-11-12 15:55:29 +01001492 /*
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001493 * If both cpu and prev_cpu are part of this domain,
1494 * cpu is a valid SD_WAKE_AFFINE target.
Peter Zijlstrafe3bcfe2009-11-12 15:55:29 +01001495 */
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001496 if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
1497 cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) {
1498 affine_sd = tmp;
1499 want_affine = 0;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001500 }
1501
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001502 if (!want_sd && !want_affine)
1503 break;
1504
Peter Zijlstra0763a662009-09-14 19:37:39 +02001505 if (!(tmp->flags & sd_flag))
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001506 continue;
1507
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001508 if (want_sd)
1509 sd = tmp;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001510 }
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001511
Mike Galbraith8b911ac2010-03-11 17:17:16 +01001512#ifdef CONFIG_FAIR_GROUP_SCHED
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001513 if (sched_feat(LB_SHARES_UPDATE)) {
1514 /*
1515 * Pick the largest domain to update shares over
1516 */
1517 tmp = sd;
Peter Zijlstra669c55e2010-04-16 14:59:29 +02001518 if (affine_sd && (!tmp || affine_sd->span_weight > sd->span_weight))
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001519 tmp = affine_sd;
1520
Peter Zijlstra0017d732010-03-24 18:34:10 +01001521 if (tmp) {
1522 raw_spin_unlock(&rq->lock);
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001523 update_shares(tmp);
Peter Zijlstra0017d732010-03-24 18:34:10 +01001524 raw_spin_lock(&rq->lock);
1525 }
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001526 }
Mike Galbraith8b911ac2010-03-11 17:17:16 +01001527#endif
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001528
Mike Galbraith8b911ac2010-03-11 17:17:16 +01001529 if (affine_sd) {
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001530 if (cpu == prev_cpu || wake_affine(affine_sd, p, sync))
1531 return select_idle_sibling(p, cpu);
1532 else
1533 return select_idle_sibling(p, prev_cpu);
Mike Galbraith8b911ac2010-03-11 17:17:16 +01001534 }
Peter Zijlstra3b640892009-09-16 13:44:33 +02001535
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001536 while (sd) {
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001537 int load_idx = sd->forkexec_idx;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001538 struct sched_group *group;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001539 int weight;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001540
Peter Zijlstra0763a662009-09-14 19:37:39 +02001541 if (!(sd->flags & sd_flag)) {
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001542 sd = sd->child;
1543 continue;
1544 }
1545
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001546 if (sd_flag & SD_BALANCE_WAKE)
1547 load_idx = sd->wake_idx;
1548
1549 group = find_idlest_group(sd, p, cpu, load_idx);
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001550 if (!group) {
1551 sd = sd->child;
1552 continue;
1553 }
1554
Peter Zijlstrad7c33c42009-09-11 12:45:38 +02001555 new_cpu = find_idlest_cpu(group, p, cpu);
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001556 if (new_cpu == -1 || new_cpu == cpu) {
1557 /* Now try balancing at a lower domain level of cpu */
1558 sd = sd->child;
1559 continue;
1560 }
1561
1562 /* Now try balancing at a lower domain level of new_cpu */
1563 cpu = new_cpu;
Peter Zijlstra669c55e2010-04-16 14:59:29 +02001564 weight = sd->span_weight;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001565 sd = NULL;
1566 for_each_domain(cpu, tmp) {
Peter Zijlstra669c55e2010-04-16 14:59:29 +02001567 if (weight <= tmp->span_weight)
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001568 break;
Peter Zijlstra0763a662009-09-14 19:37:39 +02001569 if (tmp->flags & sd_flag)
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001570 sd = tmp;
1571 }
1572 /* while loop will break here if sd == NULL */
Gregory Haskinse7693a32008-01-25 21:08:09 +01001573 }
1574
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001575 return new_cpu;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001576}
1577#endif /* CONFIG_SMP */
1578
Peter Zijlstrae52fb7c2009-01-14 12:39:19 +01001579static unsigned long
1580wakeup_gran(struct sched_entity *curr, struct sched_entity *se)
Peter Zijlstra0bbd3332008-04-19 19:44:57 +02001581{
1582 unsigned long gran = sysctl_sched_wakeup_granularity;
1583
1584 /*
Peter Zijlstrae52fb7c2009-01-14 12:39:19 +01001585 * Since its curr running now, convert the gran from real-time
1586 * to virtual-time in his units.
Mike Galbraith13814d42010-03-11 17:17:04 +01001587 *
1588 * By using 'se' instead of 'curr' we penalize light tasks, so
1589 * they get preempted easier. That is, if 'se' < 'curr' then
1590 * the resulting gran will be larger, therefore penalizing the
1591 * lighter, if otoh 'se' > 'curr' then the resulting gran will
1592 * be smaller, again penalizing the lighter task.
1593 *
1594 * This is especially important for buddies when the leftmost
1595 * task is higher priority than the buddy.
Peter Zijlstra0bbd3332008-04-19 19:44:57 +02001596 */
Mike Galbraith13814d42010-03-11 17:17:04 +01001597 if (unlikely(se->load.weight != NICE_0_LOAD))
1598 gran = calc_delta_fair(gran, se);
Peter Zijlstra0bbd3332008-04-19 19:44:57 +02001599
1600 return gran;
1601}
1602
1603/*
Peter Zijlstra464b7522008-10-24 11:06:15 +02001604 * Should 'se' preempt 'curr'.
1605 *
1606 * |s1
1607 * |s2
1608 * |s3
1609 * g
1610 * |<--->|c
1611 *
1612 * w(c, s1) = -1
1613 * w(c, s2) = 0
1614 * w(c, s3) = 1
1615 *
1616 */
1617static int
1618wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
1619{
1620 s64 gran, vdiff = curr->vruntime - se->vruntime;
1621
1622 if (vdiff <= 0)
1623 return -1;
1624
Peter Zijlstrae52fb7c2009-01-14 12:39:19 +01001625 gran = wakeup_gran(curr, se);
Peter Zijlstra464b7522008-10-24 11:06:15 +02001626 if (vdiff > gran)
1627 return 1;
1628
1629 return 0;
1630}
1631
Peter Zijlstra02479092008-11-04 21:25:10 +01001632static void set_last_buddy(struct sched_entity *se)
1633{
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001634 if (likely(task_of(se)->policy != SCHED_IDLE)) {
1635 for_each_sched_entity(se)
1636 cfs_rq_of(se)->last = se;
1637 }
Peter Zijlstra02479092008-11-04 21:25:10 +01001638}
1639
1640static void set_next_buddy(struct sched_entity *se)
1641{
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001642 if (likely(task_of(se)->policy != SCHED_IDLE)) {
1643 for_each_sched_entity(se)
1644 cfs_rq_of(se)->next = se;
1645 }
Peter Zijlstra02479092008-11-04 21:25:10 +01001646}
1647
Peter Zijlstra464b7522008-10-24 11:06:15 +02001648/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001649 * Preempt the current task with a newly woken task if needed:
1650 */
Peter Zijlstra5a9b86f2009-09-16 13:47:58 +02001651static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001652{
1653 struct task_struct *curr = rq->curr;
Srivatsa Vaddagiri8651a862007-10-15 17:00:12 +02001654 struct sched_entity *se = &curr->se, *pse = &p->se;
Mike Galbraith03e89e42008-12-16 08:45:30 +01001655 struct cfs_rq *cfs_rq = task_cfs_rq(curr);
Mike Galbraithf685cea2009-10-23 23:09:22 +02001656 int scale = cfs_rq->nr_running >= sched_nr_latency;
Mike Galbraith03e89e42008-12-16 08:45:30 +01001657
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01001658 if (unlikely(rt_prio(p->prio)))
1659 goto preempt;
Peter Zijlstraaa2ac252008-03-14 21:12:12 +01001660
Peter Zijlstrad95f98d2008-11-04 21:25:08 +01001661 if (unlikely(p->sched_class != &fair_sched_class))
1662 return;
1663
Ingo Molnar4ae7d5c2008-03-19 01:42:00 +01001664 if (unlikely(se == pse))
1665 return;
1666
Mike Galbraithf685cea2009-10-23 23:09:22 +02001667 if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK))
Mike Galbraith3cb63d52009-09-11 12:01:17 +02001668 set_next_buddy(pse);
Peter Zijlstra57fdc262008-09-23 15:33:45 +02001669
Bharata B Raoaec0a512008-08-28 14:42:49 +05301670 /*
1671 * We can come here with TIF_NEED_RESCHED already set from new task
1672 * wake up path.
1673 */
1674 if (test_tsk_need_resched(curr))
1675 return;
1676
Ingo Molnar91c234b2007-10-15 17:00:18 +02001677 /*
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001678 * Batch and idle tasks do not preempt (their preemption is driven by
Ingo Molnar91c234b2007-10-15 17:00:18 +02001679 * the tick):
1680 */
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001681 if (unlikely(p->policy != SCHED_NORMAL))
Ingo Molnar91c234b2007-10-15 17:00:18 +02001682 return;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001683
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001684 /* Idle tasks are by definition preempted by everybody. */
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01001685 if (unlikely(curr->policy == SCHED_IDLE))
1686 goto preempt;
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001687
Peter Zijlstraad4b78b2009-09-16 12:31:31 +02001688 if (!sched_feat(WAKEUP_PREEMPT))
1689 return;
1690
Jupyung Leea65ac742009-11-17 18:51:40 +09001691 update_curr(cfs_rq);
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01001692 find_matching_se(&se, &pse);
1693 BUG_ON(!pse);
1694 if (wakeup_preempt_entity(se, pse) == 1)
1695 goto preempt;
Jupyung Leea65ac742009-11-17 18:51:40 +09001696
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01001697 return;
1698
1699preempt:
1700 resched_task(curr);
1701 /*
1702 * Only set the backward buddy when the current task is still
1703 * on the rq. This can happen when a wakeup gets interleaved
1704 * with schedule on the ->pre_schedule() or idle_balance()
1705 * point, either of which can * drop the rq lock.
1706 *
1707 * Also, during early boot the idle thread is in the fair class,
1708 * for obvious reasons its a bad idea to schedule back to it.
1709 */
1710 if (unlikely(!se->on_rq || curr == rq->idle))
1711 return;
1712
1713 if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))
1714 set_last_buddy(se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001715}
1716
Ingo Molnarfb8d4722007-08-09 11:16:48 +02001717static struct task_struct *pick_next_task_fair(struct rq *rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001718{
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001719 struct task_struct *p;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001720 struct cfs_rq *cfs_rq = &rq->cfs;
1721 struct sched_entity *se;
1722
Tim Blechmann36ace272009-11-24 11:55:45 +01001723 if (!cfs_rq->nr_running)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001724 return NULL;
1725
1726 do {
Ingo Molnar9948f4b2007-08-09 11:16:48 +02001727 se = pick_next_entity(cfs_rq);
Peter Zijlstraf4b67552008-11-04 21:25:07 +01001728 set_next_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001729 cfs_rq = group_cfs_rq(se);
1730 } while (cfs_rq);
1731
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001732 p = task_of(se);
1733 hrtick_start_fair(rq, p);
1734
1735 return p;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001736}
1737
1738/*
1739 * Account for a descheduled task:
1740 */
Ingo Molnar31ee5292007-08-09 11:16:49 +02001741static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001742{
1743 struct sched_entity *se = &prev->se;
1744 struct cfs_rq *cfs_rq;
1745
1746 for_each_sched_entity(se) {
1747 cfs_rq = cfs_rq_of(se);
Ingo Molnarab6cde22007-08-09 11:16:48 +02001748 put_prev_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001749 }
1750}
1751
Peter Williams681f3e62007-10-24 18:23:51 +02001752#ifdef CONFIG_SMP
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001753/**************************************************
1754 * Fair scheduling class load-balancing methods:
1755 */
1756
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001757/*
1758 * pull_task - move a task from a remote runqueue to the local runqueue.
1759 * Both runqueues must be locked.
1760 */
1761static void pull_task(struct rq *src_rq, struct task_struct *p,
1762 struct rq *this_rq, int this_cpu)
1763{
1764 deactivate_task(src_rq, p, 0);
1765 set_task_cpu(p, this_cpu);
1766 activate_task(this_rq, p, 0);
1767 check_preempt_curr(this_rq, p, 0);
1768}
1769
1770/*
1771 * can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
1772 */
1773static
1774int can_migrate_task(struct task_struct *p, struct rq *rq, int this_cpu,
1775 struct sched_domain *sd, enum cpu_idle_type idle,
1776 int *all_pinned)
1777{
1778 int tsk_cache_hot = 0;
1779 /*
1780 * We do not migrate tasks that are:
1781 * 1) running (obviously), or
1782 * 2) cannot be migrated to this CPU due to cpus_allowed, or
1783 * 3) are cache-hot on their current CPU.
1784 */
1785 if (!cpumask_test_cpu(this_cpu, &p->cpus_allowed)) {
Lucas De Marchi41acab82010-03-10 23:37:45 -03001786 schedstat_inc(p, se.statistics.nr_failed_migrations_affine);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001787 return 0;
1788 }
1789 *all_pinned = 0;
1790
1791 if (task_running(rq, p)) {
Lucas De Marchi41acab82010-03-10 23:37:45 -03001792 schedstat_inc(p, se.statistics.nr_failed_migrations_running);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001793 return 0;
1794 }
1795
1796 /*
1797 * Aggressive migration if:
1798 * 1) task is cache cold, or
1799 * 2) too many balance attempts have failed.
1800 */
1801
1802 tsk_cache_hot = task_hot(p, rq->clock, sd);
1803 if (!tsk_cache_hot ||
1804 sd->nr_balance_failed > sd->cache_nice_tries) {
1805#ifdef CONFIG_SCHEDSTATS
1806 if (tsk_cache_hot) {
1807 schedstat_inc(sd, lb_hot_gained[idle]);
Lucas De Marchi41acab82010-03-10 23:37:45 -03001808 schedstat_inc(p, se.statistics.nr_forced_migrations);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001809 }
1810#endif
1811 return 1;
1812 }
1813
1814 if (tsk_cache_hot) {
Lucas De Marchi41acab82010-03-10 23:37:45 -03001815 schedstat_inc(p, se.statistics.nr_failed_migrations_hot);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001816 return 0;
1817 }
1818 return 1;
1819}
1820
Peter Zijlstra897c3952009-12-17 17:45:42 +01001821/*
1822 * move_one_task tries to move exactly one task from busiest to this_rq, as
1823 * part of active balancing operations within "domain".
1824 * Returns 1 if successful and 0 otherwise.
1825 *
1826 * Called with both runqueues locked.
1827 */
1828static int
1829move_one_task(struct rq *this_rq, int this_cpu, struct rq *busiest,
1830 struct sched_domain *sd, enum cpu_idle_type idle)
1831{
1832 struct task_struct *p, *n;
1833 struct cfs_rq *cfs_rq;
1834 int pinned = 0;
1835
1836 for_each_leaf_cfs_rq(busiest, cfs_rq) {
1837 list_for_each_entry_safe(p, n, &cfs_rq->tasks, se.group_node) {
1838
1839 if (!can_migrate_task(p, busiest, this_cpu,
1840 sd, idle, &pinned))
1841 continue;
1842
1843 pull_task(busiest, p, this_rq, this_cpu);
1844 /*
1845 * Right now, this is only the second place pull_task()
1846 * is called, so we can safely collect pull_task()
1847 * stats here rather than inside pull_task().
1848 */
1849 schedstat_inc(sd, lb_gained[idle]);
1850 return 1;
1851 }
1852 }
1853
1854 return 0;
1855}
1856
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001857static unsigned long
1858balance_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
1859 unsigned long max_load_move, struct sched_domain *sd,
1860 enum cpu_idle_type idle, int *all_pinned,
Peter Zijlstraee00e662009-12-17 17:25:20 +01001861 int *this_best_prio, struct cfs_rq *busiest_cfs_rq)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001862{
1863 int loops = 0, pulled = 0, pinned = 0;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001864 long rem_load_move = max_load_move;
Peter Zijlstraee00e662009-12-17 17:25:20 +01001865 struct task_struct *p, *n;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001866
1867 if (max_load_move == 0)
1868 goto out;
1869
1870 pinned = 1;
1871
Peter Zijlstraee00e662009-12-17 17:25:20 +01001872 list_for_each_entry_safe(p, n, &busiest_cfs_rq->tasks, se.group_node) {
1873 if (loops++ > sysctl_sched_nr_migrate)
1874 break;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001875
Peter Zijlstraee00e662009-12-17 17:25:20 +01001876 if ((p->se.load.weight >> 1) > rem_load_move ||
1877 !can_migrate_task(p, busiest, this_cpu, sd, idle, &pinned))
1878 continue;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001879
Peter Zijlstraee00e662009-12-17 17:25:20 +01001880 pull_task(busiest, p, this_rq, this_cpu);
1881 pulled++;
1882 rem_load_move -= p->se.load.weight;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001883
1884#ifdef CONFIG_PREEMPT
Peter Zijlstraee00e662009-12-17 17:25:20 +01001885 /*
1886 * NEWIDLE balancing is a source of latency, so preemptible
1887 * kernels will stop after the first task is pulled to minimize
1888 * the critical section.
1889 */
1890 if (idle == CPU_NEWLY_IDLE)
1891 break;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001892#endif
1893
Peter Zijlstraee00e662009-12-17 17:25:20 +01001894 /*
1895 * We only want to steal up to the prescribed amount of
1896 * weighted load.
1897 */
1898 if (rem_load_move <= 0)
1899 break;
1900
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001901 if (p->prio < *this_best_prio)
1902 *this_best_prio = p->prio;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001903 }
1904out:
1905 /*
1906 * Right now, this is one of only two places pull_task() is called,
1907 * so we can safely collect pull_task() stats here rather than
1908 * inside pull_task().
1909 */
1910 schedstat_add(sd, lb_gained[idle], pulled);
1911
1912 if (all_pinned)
1913 *all_pinned = pinned;
1914
1915 return max_load_move - rem_load_move;
1916}
1917
Peter Zijlstra230059de2009-12-17 17:47:12 +01001918#ifdef CONFIG_FAIR_GROUP_SCHED
1919static unsigned long
1920load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1921 unsigned long max_load_move,
1922 struct sched_domain *sd, enum cpu_idle_type idle,
1923 int *all_pinned, int *this_best_prio)
1924{
1925 long rem_load_move = max_load_move;
1926 int busiest_cpu = cpu_of(busiest);
1927 struct task_group *tg;
1928
1929 rcu_read_lock();
1930 update_h_load(busiest_cpu);
1931
1932 list_for_each_entry_rcu(tg, &task_groups, list) {
1933 struct cfs_rq *busiest_cfs_rq = tg->cfs_rq[busiest_cpu];
1934 unsigned long busiest_h_load = busiest_cfs_rq->h_load;
1935 unsigned long busiest_weight = busiest_cfs_rq->load.weight;
1936 u64 rem_load, moved_load;
1937
1938 /*
1939 * empty group
1940 */
1941 if (!busiest_cfs_rq->task_weight)
1942 continue;
1943
1944 rem_load = (u64)rem_load_move * busiest_weight;
1945 rem_load = div_u64(rem_load, busiest_h_load + 1);
1946
1947 moved_load = balance_tasks(this_rq, this_cpu, busiest,
1948 rem_load, sd, idle, all_pinned, this_best_prio,
1949 busiest_cfs_rq);
1950
1951 if (!moved_load)
1952 continue;
1953
1954 moved_load *= busiest_h_load;
1955 moved_load = div_u64(moved_load, busiest_weight + 1);
1956
1957 rem_load_move -= moved_load;
1958 if (rem_load_move < 0)
1959 break;
1960 }
1961 rcu_read_unlock();
1962
1963 return max_load_move - rem_load_move;
1964}
1965#else
1966static unsigned long
1967load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1968 unsigned long max_load_move,
1969 struct sched_domain *sd, enum cpu_idle_type idle,
1970 int *all_pinned, int *this_best_prio)
1971{
1972 return balance_tasks(this_rq, this_cpu, busiest,
1973 max_load_move, sd, idle, all_pinned,
1974 this_best_prio, &busiest->cfs);
1975}
1976#endif
1977
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001978/*
1979 * move_tasks tries to move up to max_load_move weighted load from busiest to
1980 * this_rq, as part of a balancing operation within domain "sd".
1981 * Returns 1 if successful and 0 otherwise.
1982 *
1983 * Called with both runqueues locked.
1984 */
1985static int move_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
1986 unsigned long max_load_move,
1987 struct sched_domain *sd, enum cpu_idle_type idle,
1988 int *all_pinned)
1989{
Peter Zijlstra3d45fd82009-12-17 17:12:46 +01001990 unsigned long total_load_moved = 0, load_moved;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001991 int this_best_prio = this_rq->curr->prio;
1992
1993 do {
Peter Zijlstra3d45fd82009-12-17 17:12:46 +01001994 load_moved = load_balance_fair(this_rq, this_cpu, busiest,
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001995 max_load_move - total_load_moved,
1996 sd, idle, all_pinned, &this_best_prio);
Peter Zijlstra3d45fd82009-12-17 17:12:46 +01001997
1998 total_load_moved += load_moved;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01001999
2000#ifdef CONFIG_PREEMPT
2001 /*
2002 * NEWIDLE balancing is a source of latency, so preemptible
2003 * kernels will stop after the first task is pulled to minimize
2004 * the critical section.
2005 */
2006 if (idle == CPU_NEWLY_IDLE && this_rq->nr_running)
2007 break;
Peter Zijlstrabaa8c112009-12-17 18:10:09 +01002008
2009 if (raw_spin_is_contended(&this_rq->lock) ||
2010 raw_spin_is_contended(&busiest->lock))
2011 break;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002012#endif
Peter Zijlstra3d45fd82009-12-17 17:12:46 +01002013 } while (load_moved && max_load_move > total_load_moved);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002014
2015 return total_load_moved > 0;
2016}
2017
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002018/********** Helpers for find_busiest_group ************************/
2019/*
2020 * sd_lb_stats - Structure to store the statistics of a sched_domain
2021 * during load balancing.
2022 */
2023struct sd_lb_stats {
2024 struct sched_group *busiest; /* Busiest group in this sd */
2025 struct sched_group *this; /* Local group in this sd */
2026 unsigned long total_load; /* Total load of all groups in sd */
2027 unsigned long total_pwr; /* Total power of all groups in sd */
2028 unsigned long avg_load; /* Average load across all groups in sd */
2029
2030 /** Statistics of this group */
2031 unsigned long this_load;
2032 unsigned long this_load_per_task;
2033 unsigned long this_nr_running;
2034
2035 /* Statistics of the busiest group */
2036 unsigned long max_load;
2037 unsigned long busiest_load_per_task;
2038 unsigned long busiest_nr_running;
Suresh Siddhadd5feea2010-02-23 16:13:52 -08002039 unsigned long busiest_group_capacity;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002040
2041 int group_imb; /* Is there imbalance in this sd */
2042#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
2043 int power_savings_balance; /* Is powersave balance needed for this sd */
2044 struct sched_group *group_min; /* Least loaded group in sd */
2045 struct sched_group *group_leader; /* Group which relieves group_min */
2046 unsigned long min_load_per_task; /* load_per_task in group_min */
2047 unsigned long leader_nr_running; /* Nr running of group_leader */
2048 unsigned long min_nr_running; /* Nr running of group_min */
2049#endif
2050};
2051
2052/*
2053 * sg_lb_stats - stats of a sched_group required for load_balancing
2054 */
2055struct sg_lb_stats {
2056 unsigned long avg_load; /*Avg load across the CPUs of the group */
2057 unsigned long group_load; /* Total load over the CPUs of the group */
2058 unsigned long sum_nr_running; /* Nr tasks running in the group */
2059 unsigned long sum_weighted_load; /* Weighted load of group's tasks */
2060 unsigned long group_capacity;
2061 int group_imb; /* Is there an imbalance in the group ? */
2062};
2063
2064/**
2065 * group_first_cpu - Returns the first cpu in the cpumask of a sched_group.
2066 * @group: The group whose first cpu is to be returned.
2067 */
2068static inline unsigned int group_first_cpu(struct sched_group *group)
2069{
2070 return cpumask_first(sched_group_cpus(group));
2071}
2072
2073/**
2074 * get_sd_load_idx - Obtain the load index for a given sched domain.
2075 * @sd: The sched_domain whose load_idx is to be obtained.
2076 * @idle: The Idle status of the CPU for whose sd load_icx is obtained.
2077 */
2078static inline int get_sd_load_idx(struct sched_domain *sd,
2079 enum cpu_idle_type idle)
2080{
2081 int load_idx;
2082
2083 switch (idle) {
2084 case CPU_NOT_IDLE:
2085 load_idx = sd->busy_idx;
2086 break;
2087
2088 case CPU_NEWLY_IDLE:
2089 load_idx = sd->newidle_idx;
2090 break;
2091 default:
2092 load_idx = sd->idle_idx;
2093 break;
2094 }
2095
2096 return load_idx;
2097}
2098
2099
2100#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
2101/**
2102 * init_sd_power_savings_stats - Initialize power savings statistics for
2103 * the given sched_domain, during load balancing.
2104 *
2105 * @sd: Sched domain whose power-savings statistics are to be initialized.
2106 * @sds: Variable containing the statistics for sd.
2107 * @idle: Idle status of the CPU at which we're performing load-balancing.
2108 */
2109static inline void init_sd_power_savings_stats(struct sched_domain *sd,
2110 struct sd_lb_stats *sds, enum cpu_idle_type idle)
2111{
2112 /*
2113 * Busy processors will not participate in power savings
2114 * balance.
2115 */
2116 if (idle == CPU_NOT_IDLE || !(sd->flags & SD_POWERSAVINGS_BALANCE))
2117 sds->power_savings_balance = 0;
2118 else {
2119 sds->power_savings_balance = 1;
2120 sds->min_nr_running = ULONG_MAX;
2121 sds->leader_nr_running = 0;
2122 }
2123}
2124
2125/**
2126 * update_sd_power_savings_stats - Update the power saving stats for a
2127 * sched_domain while performing load balancing.
2128 *
2129 * @group: sched_group belonging to the sched_domain under consideration.
2130 * @sds: Variable containing the statistics of the sched_domain
2131 * @local_group: Does group contain the CPU for which we're performing
2132 * load balancing ?
2133 * @sgs: Variable containing the statistics of the group.
2134 */
2135static inline void update_sd_power_savings_stats(struct sched_group *group,
2136 struct sd_lb_stats *sds, int local_group, struct sg_lb_stats *sgs)
2137{
2138
2139 if (!sds->power_savings_balance)
2140 return;
2141
2142 /*
2143 * If the local group is idle or completely loaded
2144 * no need to do power savings balance at this domain
2145 */
2146 if (local_group && (sds->this_nr_running >= sgs->group_capacity ||
2147 !sds->this_nr_running))
2148 sds->power_savings_balance = 0;
2149
2150 /*
2151 * If a group is already running at full capacity or idle,
2152 * don't include that group in power savings calculations
2153 */
2154 if (!sds->power_savings_balance ||
2155 sgs->sum_nr_running >= sgs->group_capacity ||
2156 !sgs->sum_nr_running)
2157 return;
2158
2159 /*
2160 * Calculate the group which has the least non-idle load.
2161 * This is the group from where we need to pick up the load
2162 * for saving power
2163 */
2164 if ((sgs->sum_nr_running < sds->min_nr_running) ||
2165 (sgs->sum_nr_running == sds->min_nr_running &&
2166 group_first_cpu(group) > group_first_cpu(sds->group_min))) {
2167 sds->group_min = group;
2168 sds->min_nr_running = sgs->sum_nr_running;
2169 sds->min_load_per_task = sgs->sum_weighted_load /
2170 sgs->sum_nr_running;
2171 }
2172
2173 /*
2174 * Calculate the group which is almost near its
2175 * capacity but still has some space to pick up some load
2176 * from other group and save more power
2177 */
2178 if (sgs->sum_nr_running + 1 > sgs->group_capacity)
2179 return;
2180
2181 if (sgs->sum_nr_running > sds->leader_nr_running ||
2182 (sgs->sum_nr_running == sds->leader_nr_running &&
2183 group_first_cpu(group) < group_first_cpu(sds->group_leader))) {
2184 sds->group_leader = group;
2185 sds->leader_nr_running = sgs->sum_nr_running;
2186 }
2187}
2188
2189/**
2190 * check_power_save_busiest_group - see if there is potential for some power-savings balance
2191 * @sds: Variable containing the statistics of the sched_domain
2192 * under consideration.
2193 * @this_cpu: Cpu at which we're currently performing load-balancing.
2194 * @imbalance: Variable to store the imbalance.
2195 *
2196 * Description:
2197 * Check if we have potential to perform some power-savings balance.
2198 * If yes, set the busiest group to be the least loaded group in the
2199 * sched_domain, so that it's CPUs can be put to idle.
2200 *
2201 * Returns 1 if there is potential to perform power-savings balance.
2202 * Else returns 0.
2203 */
2204static inline int check_power_save_busiest_group(struct sd_lb_stats *sds,
2205 int this_cpu, unsigned long *imbalance)
2206{
2207 if (!sds->power_savings_balance)
2208 return 0;
2209
2210 if (sds->this != sds->group_leader ||
2211 sds->group_leader == sds->group_min)
2212 return 0;
2213
2214 *imbalance = sds->min_load_per_task;
2215 sds->busiest = sds->group_min;
2216
2217 return 1;
2218
2219}
2220#else /* CONFIG_SCHED_MC || CONFIG_SCHED_SMT */
2221static inline void init_sd_power_savings_stats(struct sched_domain *sd,
2222 struct sd_lb_stats *sds, enum cpu_idle_type idle)
2223{
2224 return;
2225}
2226
2227static inline void update_sd_power_savings_stats(struct sched_group *group,
2228 struct sd_lb_stats *sds, int local_group, struct sg_lb_stats *sgs)
2229{
2230 return;
2231}
2232
2233static inline int check_power_save_busiest_group(struct sd_lb_stats *sds,
2234 int this_cpu, unsigned long *imbalance)
2235{
2236 return 0;
2237}
2238#endif /* CONFIG_SCHED_MC || CONFIG_SCHED_SMT */
2239
2240
2241unsigned long default_scale_freq_power(struct sched_domain *sd, int cpu)
2242{
2243 return SCHED_LOAD_SCALE;
2244}
2245
2246unsigned long __weak arch_scale_freq_power(struct sched_domain *sd, int cpu)
2247{
2248 return default_scale_freq_power(sd, cpu);
2249}
2250
2251unsigned long default_scale_smt_power(struct sched_domain *sd, int cpu)
2252{
Peter Zijlstra669c55e2010-04-16 14:59:29 +02002253 unsigned long weight = sd->span_weight;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002254 unsigned long smt_gain = sd->smt_gain;
2255
2256 smt_gain /= weight;
2257
2258 return smt_gain;
2259}
2260
2261unsigned long __weak arch_scale_smt_power(struct sched_domain *sd, int cpu)
2262{
2263 return default_scale_smt_power(sd, cpu);
2264}
2265
2266unsigned long scale_rt_power(int cpu)
2267{
2268 struct rq *rq = cpu_rq(cpu);
2269 u64 total, available;
2270
2271 sched_avg_update(rq);
2272
2273 total = sched_avg_period() + (rq->clock - rq->age_stamp);
2274 available = total - rq->rt_avg;
2275
2276 if (unlikely((s64)total < SCHED_LOAD_SCALE))
2277 total = SCHED_LOAD_SCALE;
2278
2279 total >>= SCHED_LOAD_SHIFT;
2280
2281 return div_u64(available, total);
2282}
2283
2284static void update_cpu_power(struct sched_domain *sd, int cpu)
2285{
Peter Zijlstra669c55e2010-04-16 14:59:29 +02002286 unsigned long weight = sd->span_weight;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002287 unsigned long power = SCHED_LOAD_SCALE;
2288 struct sched_group *sdg = sd->groups;
2289
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002290 if ((sd->flags & SD_SHARE_CPUPOWER) && weight > 1) {
2291 if (sched_feat(ARCH_POWER))
2292 power *= arch_scale_smt_power(sd, cpu);
2293 else
2294 power *= default_scale_smt_power(sd, cpu);
2295
2296 power >>= SCHED_LOAD_SHIFT;
2297 }
2298
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002299 sdg->cpu_power_orig = power;
2300
2301 if (sched_feat(ARCH_POWER))
2302 power *= arch_scale_freq_power(sd, cpu);
2303 else
2304 power *= default_scale_freq_power(sd, cpu);
2305
2306 power >>= SCHED_LOAD_SHIFT;
2307
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002308 power *= scale_rt_power(cpu);
2309 power >>= SCHED_LOAD_SHIFT;
2310
2311 if (!power)
2312 power = 1;
2313
Peter Zijlstrae51fd5e2010-05-31 12:37:30 +02002314 cpu_rq(cpu)->cpu_power = power;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002315 sdg->cpu_power = power;
2316}
2317
2318static void update_group_power(struct sched_domain *sd, int cpu)
2319{
2320 struct sched_domain *child = sd->child;
2321 struct sched_group *group, *sdg = sd->groups;
2322 unsigned long power;
2323
2324 if (!child) {
2325 update_cpu_power(sd, cpu);
2326 return;
2327 }
2328
2329 power = 0;
2330
2331 group = child->groups;
2332 do {
2333 power += group->cpu_power;
2334 group = group->next;
2335 } while (group != child->groups);
2336
2337 sdg->cpu_power = power;
2338}
2339
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002340/*
2341 * Try and fix up capacity for tiny siblings, this is needed when
2342 * things like SD_ASYM_PACKING need f_b_g to select another sibling
2343 * which on its own isn't powerful enough.
2344 *
2345 * See update_sd_pick_busiest() and check_asym_packing().
2346 */
2347static inline int
2348fix_small_capacity(struct sched_domain *sd, struct sched_group *group)
2349{
2350 /*
2351 * Only siblings can have significantly less than SCHED_LOAD_SCALE
2352 */
2353 if (sd->level != SD_LV_SIBLING)
2354 return 0;
2355
2356 /*
2357 * If ~90% of the cpu_power is still there, we're good.
2358 */
Michael Neuling694f5a12010-06-10 09:03:37 +10002359 if (group->cpu_power * 32 > group->cpu_power_orig * 29)
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002360 return 1;
2361
2362 return 0;
2363}
2364
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002365/**
2366 * update_sg_lb_stats - Update sched_group's statistics for load balancing.
2367 * @sd: The sched_domain whose statistics are to be updated.
2368 * @group: sched_group whose statistics are to be updated.
2369 * @this_cpu: Cpu for which load balance is currently performed.
2370 * @idle: Idle status of this_cpu
2371 * @load_idx: Load index of sched_domain of this_cpu for load calc.
2372 * @sd_idle: Idle status of the sched_domain containing group.
2373 * @local_group: Does group contain this_cpu.
2374 * @cpus: Set of cpus considered for load balancing.
2375 * @balance: Should we balance.
2376 * @sgs: variable to hold the statistics for this group.
2377 */
2378static inline void update_sg_lb_stats(struct sched_domain *sd,
2379 struct sched_group *group, int this_cpu,
2380 enum cpu_idle_type idle, int load_idx, int *sd_idle,
2381 int local_group, const struct cpumask *cpus,
2382 int *balance, struct sg_lb_stats *sgs)
2383{
2384 unsigned long load, max_cpu_load, min_cpu_load;
2385 int i;
2386 unsigned int balance_cpu = -1, first_idle_cpu = 0;
Suresh Siddhadd5feea2010-02-23 16:13:52 -08002387 unsigned long avg_load_per_task = 0;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002388
Gautham R Shenoy871e35b2010-01-20 14:02:44 -06002389 if (local_group)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002390 balance_cpu = group_first_cpu(group);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002391
2392 /* Tally up the load of all CPUs in the group */
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002393 max_cpu_load = 0;
2394 min_cpu_load = ~0UL;
2395
2396 for_each_cpu_and(i, sched_group_cpus(group), cpus) {
2397 struct rq *rq = cpu_rq(i);
2398
2399 if (*sd_idle && rq->nr_running)
2400 *sd_idle = 0;
2401
2402 /* Bias balancing toward cpus of our domain */
2403 if (local_group) {
2404 if (idle_cpu(i) && !first_idle_cpu) {
2405 first_idle_cpu = 1;
2406 balance_cpu = i;
2407 }
2408
2409 load = target_load(i, load_idx);
2410 } else {
2411 load = source_load(i, load_idx);
2412 if (load > max_cpu_load)
2413 max_cpu_load = load;
2414 if (min_cpu_load > load)
2415 min_cpu_load = load;
2416 }
2417
2418 sgs->group_load += load;
2419 sgs->sum_nr_running += rq->nr_running;
2420 sgs->sum_weighted_load += weighted_cpuload(i);
2421
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002422 }
2423
2424 /*
2425 * First idle cpu or the first cpu(busiest) in this sched group
2426 * is eligible for doing load balancing at this and above
2427 * domains. In the newly idle case, we will allow all the cpu's
2428 * to do the newly idle load balance.
2429 */
Peter Zijlstrabbc8cb52010-07-09 15:15:43 +02002430 if (idle != CPU_NEWLY_IDLE && local_group) {
2431 if (balance_cpu != this_cpu) {
2432 *balance = 0;
2433 return;
2434 }
2435 update_group_power(sd, this_cpu);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002436 }
2437
2438 /* Adjust by relative CPU power of the group */
2439 sgs->avg_load = (sgs->group_load * SCHED_LOAD_SCALE) / group->cpu_power;
2440
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002441 /*
2442 * Consider the group unbalanced when the imbalance is larger
2443 * than the average weight of two tasks.
2444 *
2445 * APZ: with cgroup the avg task weight can vary wildly and
2446 * might not be a suitable number - should we keep a
2447 * normalized nr_running number somewhere that negates
2448 * the hierarchy?
2449 */
Suresh Siddhadd5feea2010-02-23 16:13:52 -08002450 if (sgs->sum_nr_running)
2451 avg_load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002452
2453 if ((max_cpu_load - min_cpu_load) > 2*avg_load_per_task)
2454 sgs->group_imb = 1;
2455
2456 sgs->group_capacity =
2457 DIV_ROUND_CLOSEST(group->cpu_power, SCHED_LOAD_SCALE);
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002458 if (!sgs->group_capacity)
2459 sgs->group_capacity = fix_small_capacity(sd, group);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002460}
2461
2462/**
Michael Neuling532cb4c2010-06-08 14:57:02 +10002463 * update_sd_pick_busiest - return 1 on busiest group
2464 * @sd: sched_domain whose statistics are to be checked
2465 * @sds: sched_domain statistics
2466 * @sg: sched_group candidate to be checked for being the busiest
Michael Neulingb6b12292010-06-10 12:06:21 +10002467 * @sgs: sched_group statistics
2468 * @this_cpu: the current cpu
Michael Neuling532cb4c2010-06-08 14:57:02 +10002469 *
2470 * Determine if @sg is a busier group than the previously selected
2471 * busiest group.
2472 */
2473static bool update_sd_pick_busiest(struct sched_domain *sd,
2474 struct sd_lb_stats *sds,
2475 struct sched_group *sg,
2476 struct sg_lb_stats *sgs,
2477 int this_cpu)
2478{
2479 if (sgs->avg_load <= sds->max_load)
2480 return false;
2481
2482 if (sgs->sum_nr_running > sgs->group_capacity)
2483 return true;
2484
2485 if (sgs->group_imb)
2486 return true;
2487
2488 /*
2489 * ASYM_PACKING needs to move all the work to the lowest
2490 * numbered CPUs in the group, therefore mark all groups
2491 * higher than ourself as busy.
2492 */
2493 if ((sd->flags & SD_ASYM_PACKING) && sgs->sum_nr_running &&
2494 this_cpu < group_first_cpu(sg)) {
2495 if (!sds->busiest)
2496 return true;
2497
2498 if (group_first_cpu(sds->busiest) > group_first_cpu(sg))
2499 return true;
2500 }
2501
2502 return false;
2503}
2504
2505/**
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002506 * update_sd_lb_stats - Update sched_group's statistics for load balancing.
2507 * @sd: sched_domain whose statistics are to be updated.
2508 * @this_cpu: Cpu for which load balance is currently performed.
2509 * @idle: Idle status of this_cpu
Michael Neuling532cb4c2010-06-08 14:57:02 +10002510 * @sd_idle: Idle status of the sched_domain containing sg.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002511 * @cpus: Set of cpus considered for load balancing.
2512 * @balance: Should we balance.
2513 * @sds: variable to hold the statistics for this sched_domain.
2514 */
2515static inline void update_sd_lb_stats(struct sched_domain *sd, int this_cpu,
2516 enum cpu_idle_type idle, int *sd_idle,
2517 const struct cpumask *cpus, int *balance,
2518 struct sd_lb_stats *sds)
2519{
2520 struct sched_domain *child = sd->child;
Michael Neuling532cb4c2010-06-08 14:57:02 +10002521 struct sched_group *sg = sd->groups;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002522 struct sg_lb_stats sgs;
2523 int load_idx, prefer_sibling = 0;
2524
2525 if (child && child->flags & SD_PREFER_SIBLING)
2526 prefer_sibling = 1;
2527
2528 init_sd_power_savings_stats(sd, sds, idle);
2529 load_idx = get_sd_load_idx(sd, idle);
2530
2531 do {
2532 int local_group;
2533
Michael Neuling532cb4c2010-06-08 14:57:02 +10002534 local_group = cpumask_test_cpu(this_cpu, sched_group_cpus(sg));
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002535 memset(&sgs, 0, sizeof(sgs));
Michael Neuling532cb4c2010-06-08 14:57:02 +10002536 update_sg_lb_stats(sd, sg, this_cpu, idle, load_idx, sd_idle,
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002537 local_group, cpus, balance, &sgs);
2538
Peter Zijlstra8f190fb2009-12-24 14:18:21 +01002539 if (local_group && !(*balance))
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002540 return;
2541
2542 sds->total_load += sgs.group_load;
Michael Neuling532cb4c2010-06-08 14:57:02 +10002543 sds->total_pwr += sg->cpu_power;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002544
2545 /*
2546 * In case the child domain prefers tasks go to siblings
Michael Neuling532cb4c2010-06-08 14:57:02 +10002547 * first, lower the sg capacity to one so that we'll try
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002548 * and move all the excess tasks away.
2549 */
2550 if (prefer_sibling)
2551 sgs.group_capacity = min(sgs.group_capacity, 1UL);
2552
2553 if (local_group) {
2554 sds->this_load = sgs.avg_load;
Michael Neuling532cb4c2010-06-08 14:57:02 +10002555 sds->this = sg;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002556 sds->this_nr_running = sgs.sum_nr_running;
2557 sds->this_load_per_task = sgs.sum_weighted_load;
Michael Neuling532cb4c2010-06-08 14:57:02 +10002558 } else if (update_sd_pick_busiest(sd, sds, sg, &sgs, this_cpu)) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002559 sds->max_load = sgs.avg_load;
Michael Neuling532cb4c2010-06-08 14:57:02 +10002560 sds->busiest = sg;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002561 sds->busiest_nr_running = sgs.sum_nr_running;
Suresh Siddhadd5feea2010-02-23 16:13:52 -08002562 sds->busiest_group_capacity = sgs.group_capacity;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002563 sds->busiest_load_per_task = sgs.sum_weighted_load;
2564 sds->group_imb = sgs.group_imb;
2565 }
2566
Michael Neuling532cb4c2010-06-08 14:57:02 +10002567 update_sd_power_savings_stats(sg, sds, local_group, &sgs);
2568 sg = sg->next;
2569 } while (sg != sd->groups);
2570}
2571
Michael Neuling2ec57d42010-06-29 12:02:01 +10002572int __weak arch_sd_sibling_asym_packing(void)
Michael Neuling532cb4c2010-06-08 14:57:02 +10002573{
2574 return 0*SD_ASYM_PACKING;
2575}
2576
2577/**
2578 * check_asym_packing - Check to see if the group is packed into the
2579 * sched doman.
2580 *
2581 * This is primarily intended to used at the sibling level. Some
2582 * cores like POWER7 prefer to use lower numbered SMT threads. In the
2583 * case of POWER7, it can move to lower SMT modes only when higher
2584 * threads are idle. When in lower SMT modes, the threads will
2585 * perform better since they share less core resources. Hence when we
2586 * have idle threads, we want them to be the higher ones.
2587 *
2588 * This packing function is run on idle threads. It checks to see if
2589 * the busiest CPU in this domain (core in the P7 case) has a higher
2590 * CPU number than the packing function is being run on. Here we are
2591 * assuming lower CPU number will be equivalent to lower a SMT thread
2592 * number.
2593 *
Michael Neulingb6b12292010-06-10 12:06:21 +10002594 * Returns 1 when packing is required and a task should be moved to
2595 * this CPU. The amount of the imbalance is returned in *imbalance.
2596 *
Michael Neuling532cb4c2010-06-08 14:57:02 +10002597 * @sd: The sched_domain whose packing is to be checked.
2598 * @sds: Statistics of the sched_domain which is to be packed
2599 * @this_cpu: The cpu at whose sched_domain we're performing load-balance.
2600 * @imbalance: returns amount of imbalanced due to packing.
Michael Neuling532cb4c2010-06-08 14:57:02 +10002601 */
2602static int check_asym_packing(struct sched_domain *sd,
2603 struct sd_lb_stats *sds,
2604 int this_cpu, unsigned long *imbalance)
2605{
2606 int busiest_cpu;
2607
2608 if (!(sd->flags & SD_ASYM_PACKING))
2609 return 0;
2610
2611 if (!sds->busiest)
2612 return 0;
2613
2614 busiest_cpu = group_first_cpu(sds->busiest);
2615 if (this_cpu > busiest_cpu)
2616 return 0;
2617
2618 *imbalance = DIV_ROUND_CLOSEST(sds->max_load * sds->busiest->cpu_power,
2619 SCHED_LOAD_SCALE);
2620 return 1;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002621}
2622
2623/**
2624 * fix_small_imbalance - Calculate the minor imbalance that exists
2625 * amongst the groups of a sched_domain, during
2626 * load balancing.
2627 * @sds: Statistics of the sched_domain whose imbalance is to be calculated.
2628 * @this_cpu: The cpu at whose sched_domain we're performing load-balance.
2629 * @imbalance: Variable to store the imbalance.
2630 */
2631static inline void fix_small_imbalance(struct sd_lb_stats *sds,
2632 int this_cpu, unsigned long *imbalance)
2633{
2634 unsigned long tmp, pwr_now = 0, pwr_move = 0;
2635 unsigned int imbn = 2;
Suresh Siddhadd5feea2010-02-23 16:13:52 -08002636 unsigned long scaled_busy_load_per_task;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002637
2638 if (sds->this_nr_running) {
2639 sds->this_load_per_task /= sds->this_nr_running;
2640 if (sds->busiest_load_per_task >
2641 sds->this_load_per_task)
2642 imbn = 1;
2643 } else
2644 sds->this_load_per_task =
2645 cpu_avg_load_per_task(this_cpu);
2646
Suresh Siddhadd5feea2010-02-23 16:13:52 -08002647 scaled_busy_load_per_task = sds->busiest_load_per_task
2648 * SCHED_LOAD_SCALE;
2649 scaled_busy_load_per_task /= sds->busiest->cpu_power;
2650
2651 if (sds->max_load - sds->this_load + scaled_busy_load_per_task >=
2652 (scaled_busy_load_per_task * imbn)) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002653 *imbalance = sds->busiest_load_per_task;
2654 return;
2655 }
2656
2657 /*
2658 * OK, we don't have enough imbalance to justify moving tasks,
2659 * however we may be able to increase total CPU power used by
2660 * moving them.
2661 */
2662
2663 pwr_now += sds->busiest->cpu_power *
2664 min(sds->busiest_load_per_task, sds->max_load);
2665 pwr_now += sds->this->cpu_power *
2666 min(sds->this_load_per_task, sds->this_load);
2667 pwr_now /= SCHED_LOAD_SCALE;
2668
2669 /* Amount of load we'd subtract */
2670 tmp = (sds->busiest_load_per_task * SCHED_LOAD_SCALE) /
2671 sds->busiest->cpu_power;
2672 if (sds->max_load > tmp)
2673 pwr_move += sds->busiest->cpu_power *
2674 min(sds->busiest_load_per_task, sds->max_load - tmp);
2675
2676 /* Amount of load we'd add */
2677 if (sds->max_load * sds->busiest->cpu_power <
2678 sds->busiest_load_per_task * SCHED_LOAD_SCALE)
2679 tmp = (sds->max_load * sds->busiest->cpu_power) /
2680 sds->this->cpu_power;
2681 else
2682 tmp = (sds->busiest_load_per_task * SCHED_LOAD_SCALE) /
2683 sds->this->cpu_power;
2684 pwr_move += sds->this->cpu_power *
2685 min(sds->this_load_per_task, sds->this_load + tmp);
2686 pwr_move /= SCHED_LOAD_SCALE;
2687
2688 /* Move if we gain throughput */
2689 if (pwr_move > pwr_now)
2690 *imbalance = sds->busiest_load_per_task;
2691}
2692
2693/**
2694 * calculate_imbalance - Calculate the amount of imbalance present within the
2695 * groups of a given sched_domain during load balance.
2696 * @sds: statistics of the sched_domain whose imbalance is to be calculated.
2697 * @this_cpu: Cpu for which currently load balance is being performed.
2698 * @imbalance: The variable to store the imbalance.
2699 */
2700static inline void calculate_imbalance(struct sd_lb_stats *sds, int this_cpu,
2701 unsigned long *imbalance)
2702{
Suresh Siddhadd5feea2010-02-23 16:13:52 -08002703 unsigned long max_pull, load_above_capacity = ~0UL;
2704
2705 sds->busiest_load_per_task /= sds->busiest_nr_running;
2706 if (sds->group_imb) {
2707 sds->busiest_load_per_task =
2708 min(sds->busiest_load_per_task, sds->avg_load);
2709 }
2710
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002711 /*
2712 * In the presence of smp nice balancing, certain scenarios can have
2713 * max load less than avg load(as we skip the groups at or below
2714 * its cpu_power, while calculating max_load..)
2715 */
2716 if (sds->max_load < sds->avg_load) {
2717 *imbalance = 0;
2718 return fix_small_imbalance(sds, this_cpu, imbalance);
2719 }
2720
Suresh Siddhadd5feea2010-02-23 16:13:52 -08002721 if (!sds->group_imb) {
2722 /*
2723 * Don't want to pull so many tasks that a group would go idle.
2724 */
2725 load_above_capacity = (sds->busiest_nr_running -
2726 sds->busiest_group_capacity);
2727
2728 load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_LOAD_SCALE);
2729
2730 load_above_capacity /= sds->busiest->cpu_power;
2731 }
2732
2733 /*
2734 * We're trying to get all the cpus to the average_load, so we don't
2735 * want to push ourselves above the average load, nor do we wish to
2736 * reduce the max loaded cpu below the average load. At the same time,
2737 * we also don't want to reduce the group load below the group capacity
2738 * (so that we can implement power-savings policies etc). Thus we look
2739 * for the minimum possible imbalance.
2740 * Be careful of negative numbers as they'll appear as very large values
2741 * with unsigned longs.
2742 */
2743 max_pull = min(sds->max_load - sds->avg_load, load_above_capacity);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002744
2745 /* How much load to actually move to equalise the imbalance */
2746 *imbalance = min(max_pull * sds->busiest->cpu_power,
2747 (sds->avg_load - sds->this_load) * sds->this->cpu_power)
2748 / SCHED_LOAD_SCALE;
2749
2750 /*
2751 * if *imbalance is less than the average load per runnable task
2752 * there is no gaurantee that any tasks will be moved so we'll have
2753 * a think about bumping its value to force at least one task to be
2754 * moved
2755 */
2756 if (*imbalance < sds->busiest_load_per_task)
2757 return fix_small_imbalance(sds, this_cpu, imbalance);
2758
2759}
2760/******* find_busiest_group() helpers end here *********************/
2761
2762/**
2763 * find_busiest_group - Returns the busiest group within the sched_domain
2764 * if there is an imbalance. If there isn't an imbalance, and
2765 * the user has opted for power-savings, it returns a group whose
2766 * CPUs can be put to idle by rebalancing those tasks elsewhere, if
2767 * such a group exists.
2768 *
2769 * Also calculates the amount of weighted load which should be moved
2770 * to restore balance.
2771 *
2772 * @sd: The sched_domain whose busiest group is to be returned.
2773 * @this_cpu: The cpu for which load balancing is currently being performed.
2774 * @imbalance: Variable which stores amount of weighted load which should
2775 * be moved to restore balance/put a group to idle.
2776 * @idle: The idle status of this_cpu.
2777 * @sd_idle: The idleness of sd
2778 * @cpus: The set of CPUs under consideration for load-balancing.
2779 * @balance: Pointer to a variable indicating if this_cpu
2780 * is the appropriate cpu to perform load balancing at this_level.
2781 *
2782 * Returns: - the busiest group if imbalance exists.
2783 * - If no imbalance and user has opted for power-savings balance,
2784 * return the least loaded group whose CPUs can be
2785 * put to idle by rebalancing its tasks onto our group.
2786 */
2787static struct sched_group *
2788find_busiest_group(struct sched_domain *sd, int this_cpu,
2789 unsigned long *imbalance, enum cpu_idle_type idle,
2790 int *sd_idle, const struct cpumask *cpus, int *balance)
2791{
2792 struct sd_lb_stats sds;
2793
2794 memset(&sds, 0, sizeof(sds));
2795
2796 /*
2797 * Compute the various statistics relavent for load balancing at
2798 * this level.
2799 */
2800 update_sd_lb_stats(sd, this_cpu, idle, sd_idle, cpus,
2801 balance, &sds);
2802
2803 /* Cases where imbalance does not exist from POV of this_cpu */
2804 /* 1) this_cpu is not the appropriate cpu to perform load balancing
2805 * at this level.
2806 * 2) There is no busy sibling group to pull from.
2807 * 3) This group is the busiest group.
2808 * 4) This group is more busy than the avg busieness at this
2809 * sched_domain.
2810 * 5) The imbalance is within the specified limit.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002811 */
Peter Zijlstra8f190fb2009-12-24 14:18:21 +01002812 if (!(*balance))
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002813 goto ret;
2814
Michael Neuling532cb4c2010-06-08 14:57:02 +10002815 if ((idle == CPU_IDLE || idle == CPU_NEWLY_IDLE) &&
2816 check_asym_packing(sd, &sds, this_cpu, imbalance))
2817 return sds.busiest;
2818
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002819 if (!sds.busiest || sds.busiest_nr_running == 0)
2820 goto out_balanced;
2821
2822 if (sds.this_load >= sds.max_load)
2823 goto out_balanced;
2824
2825 sds.avg_load = (SCHED_LOAD_SCALE * sds.total_load) / sds.total_pwr;
2826
2827 if (sds.this_load >= sds.avg_load)
2828 goto out_balanced;
2829
2830 if (100 * sds.max_load <= sd->imbalance_pct * sds.this_load)
2831 goto out_balanced;
2832
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002833 /* Looks like there is an imbalance. Compute it */
2834 calculate_imbalance(&sds, this_cpu, imbalance);
2835 return sds.busiest;
2836
2837out_balanced:
2838 /*
2839 * There is no obvious imbalance. But check if we can do some balancing
2840 * to save power.
2841 */
2842 if (check_power_save_busiest_group(&sds, this_cpu, imbalance))
2843 return sds.busiest;
2844ret:
2845 *imbalance = 0;
2846 return NULL;
2847}
2848
2849/*
2850 * find_busiest_queue - find the busiest runqueue among the cpus in group.
2851 */
2852static struct rq *
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002853find_busiest_queue(struct sched_domain *sd, struct sched_group *group,
2854 enum cpu_idle_type idle, unsigned long imbalance,
2855 const struct cpumask *cpus)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002856{
2857 struct rq *busiest = NULL, *rq;
2858 unsigned long max_load = 0;
2859 int i;
2860
2861 for_each_cpu(i, sched_group_cpus(group)) {
2862 unsigned long power = power_of(i);
2863 unsigned long capacity = DIV_ROUND_CLOSEST(power, SCHED_LOAD_SCALE);
2864 unsigned long wl;
2865
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002866 if (!capacity)
2867 capacity = fix_small_capacity(sd, group);
2868
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002869 if (!cpumask_test_cpu(i, cpus))
2870 continue;
2871
2872 rq = cpu_rq(i);
Thomas Gleixner6e40f5b2010-02-16 16:48:56 +01002873 wl = weighted_cpuload(i);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002874
Thomas Gleixner6e40f5b2010-02-16 16:48:56 +01002875 /*
2876 * When comparing with imbalance, use weighted_cpuload()
2877 * which is not scaled with the cpu power.
2878 */
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002879 if (capacity && rq->nr_running == 1 && wl > imbalance)
2880 continue;
2881
Thomas Gleixner6e40f5b2010-02-16 16:48:56 +01002882 /*
2883 * For the load comparisons with the other cpu's, consider
2884 * the weighted_cpuload() scaled with the cpu power, so that
2885 * the load can be moved away from the cpu that is potentially
2886 * running at a lower capacity.
2887 */
2888 wl = (wl * SCHED_LOAD_SCALE) / power;
2889
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002890 if (wl > max_load) {
2891 max_load = wl;
2892 busiest = rq;
2893 }
2894 }
2895
2896 return busiest;
2897}
2898
2899/*
2900 * Max backoff if we encounter pinned tasks. Pretty arbitrary value, but
2901 * so long as it is large enough.
2902 */
2903#define MAX_PINNED_INTERVAL 512
2904
2905/* Working cpumask for load_balance and load_balance_newidle. */
2906static DEFINE_PER_CPU(cpumask_var_t, load_balance_tmpmask);
2907
Michael Neuling532cb4c2010-06-08 14:57:02 +10002908static int need_active_balance(struct sched_domain *sd, int sd_idle, int idle,
2909 int busiest_cpu, int this_cpu)
Peter Zijlstra1af3ed32009-12-23 15:10:31 +01002910{
2911 if (idle == CPU_NEWLY_IDLE) {
Michael Neuling532cb4c2010-06-08 14:57:02 +10002912
2913 /*
2914 * ASYM_PACKING needs to force migrate tasks from busy but
2915 * higher numbered CPUs in order to pack all tasks in the
2916 * lowest numbered CPUs.
2917 */
2918 if ((sd->flags & SD_ASYM_PACKING) && busiest_cpu > this_cpu)
2919 return 1;
2920
Peter Zijlstra1af3ed32009-12-23 15:10:31 +01002921 /*
2922 * The only task running in a non-idle cpu can be moved to this
2923 * cpu in an attempt to completely freeup the other CPU
2924 * package.
2925 *
2926 * The package power saving logic comes from
2927 * find_busiest_group(). If there are no imbalance, then
2928 * f_b_g() will return NULL. However when sched_mc={1,2} then
2929 * f_b_g() will select a group from which a running task may be
2930 * pulled to this cpu in order to make the other package idle.
2931 * If there is no opportunity to make a package idle and if
2932 * there are no imbalance, then f_b_g() will return NULL and no
2933 * action will be taken in load_balance_newidle().
2934 *
2935 * Under normal task pull operation due to imbalance, there
2936 * will be more than one task in the source run queue and
2937 * move_tasks() will succeed. ld_moved will be true and this
2938 * active balance code will not be triggered.
2939 */
2940 if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
2941 !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
2942 return 0;
2943
2944 if (sched_mc_power_savings < POWERSAVINGS_BALANCE_WAKEUP)
2945 return 0;
2946 }
2947
2948 return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
2949}
2950
Tejun Heo969c7922010-05-06 18:49:21 +02002951static int active_load_balance_cpu_stop(void *data);
2952
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002953/*
2954 * Check this_cpu to ensure it is balanced within domain. Attempt to move
2955 * tasks if there is an imbalance.
2956 */
2957static int load_balance(int this_cpu, struct rq *this_rq,
2958 struct sched_domain *sd, enum cpu_idle_type idle,
2959 int *balance)
2960{
2961 int ld_moved, all_pinned = 0, active_balance = 0, sd_idle = 0;
2962 struct sched_group *group;
2963 unsigned long imbalance;
2964 struct rq *busiest;
2965 unsigned long flags;
2966 struct cpumask *cpus = __get_cpu_var(load_balance_tmpmask);
2967
2968 cpumask_copy(cpus, cpu_active_mask);
2969
2970 /*
2971 * When power savings policy is enabled for the parent domain, idle
2972 * sibling can pick up load irrespective of busy siblings. In this case,
2973 * let the state of idle sibling percolate up as CPU_IDLE, instead of
2974 * portraying it as CPU_NOT_IDLE.
2975 */
2976 if (idle != CPU_NOT_IDLE && sd->flags & SD_SHARE_CPUPOWER &&
2977 !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
2978 sd_idle = 1;
2979
2980 schedstat_inc(sd, lb_count[idle]);
2981
2982redo:
2983 update_shares(sd);
2984 group = find_busiest_group(sd, this_cpu, &imbalance, idle, &sd_idle,
2985 cpus, balance);
2986
2987 if (*balance == 0)
2988 goto out_balanced;
2989
2990 if (!group) {
2991 schedstat_inc(sd, lb_nobusyg[idle]);
2992 goto out_balanced;
2993 }
2994
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002995 busiest = find_busiest_queue(sd, group, idle, imbalance, cpus);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002996 if (!busiest) {
2997 schedstat_inc(sd, lb_nobusyq[idle]);
2998 goto out_balanced;
2999 }
3000
3001 BUG_ON(busiest == this_rq);
3002
3003 schedstat_add(sd, lb_imbalance[idle], imbalance);
3004
3005 ld_moved = 0;
3006 if (busiest->nr_running > 1) {
3007 /*
3008 * Attempt to move tasks. If find_busiest_group has found
3009 * an imbalance but busiest->nr_running <= 1, the group is
3010 * still unbalanced. ld_moved simply stays zero, so it is
3011 * correctly treated as an imbalance.
3012 */
3013 local_irq_save(flags);
3014 double_rq_lock(this_rq, busiest);
3015 ld_moved = move_tasks(this_rq, this_cpu, busiest,
3016 imbalance, sd, idle, &all_pinned);
3017 double_rq_unlock(this_rq, busiest);
3018 local_irq_restore(flags);
3019
3020 /*
3021 * some other cpu did the load balance for us.
3022 */
3023 if (ld_moved && this_cpu != smp_processor_id())
3024 resched_cpu(this_cpu);
3025
3026 /* All tasks on this runqueue were pinned by CPU affinity */
3027 if (unlikely(all_pinned)) {
3028 cpumask_clear_cpu(cpu_of(busiest), cpus);
3029 if (!cpumask_empty(cpus))
3030 goto redo;
3031 goto out_balanced;
3032 }
3033 }
3034
3035 if (!ld_moved) {
3036 schedstat_inc(sd, lb_failed[idle]);
3037 sd->nr_balance_failed++;
3038
Michael Neuling532cb4c2010-06-08 14:57:02 +10003039 if (need_active_balance(sd, sd_idle, idle, cpu_of(busiest),
3040 this_cpu)) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003041 raw_spin_lock_irqsave(&busiest->lock, flags);
3042
Tejun Heo969c7922010-05-06 18:49:21 +02003043 /* don't kick the active_load_balance_cpu_stop,
3044 * if the curr task on busiest cpu can't be
3045 * moved to this_cpu
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003046 */
3047 if (!cpumask_test_cpu(this_cpu,
3048 &busiest->curr->cpus_allowed)) {
3049 raw_spin_unlock_irqrestore(&busiest->lock,
3050 flags);
3051 all_pinned = 1;
3052 goto out_one_pinned;
3053 }
3054
Tejun Heo969c7922010-05-06 18:49:21 +02003055 /*
3056 * ->active_balance synchronizes accesses to
3057 * ->active_balance_work. Once set, it's cleared
3058 * only after active load balance is finished.
3059 */
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003060 if (!busiest->active_balance) {
3061 busiest->active_balance = 1;
3062 busiest->push_cpu = this_cpu;
3063 active_balance = 1;
3064 }
3065 raw_spin_unlock_irqrestore(&busiest->lock, flags);
Tejun Heo969c7922010-05-06 18:49:21 +02003066
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003067 if (active_balance)
Tejun Heo969c7922010-05-06 18:49:21 +02003068 stop_one_cpu_nowait(cpu_of(busiest),
3069 active_load_balance_cpu_stop, busiest,
3070 &busiest->active_balance_work);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003071
3072 /*
3073 * We've kicked active balancing, reset the failure
3074 * counter.
3075 */
3076 sd->nr_balance_failed = sd->cache_nice_tries+1;
3077 }
3078 } else
3079 sd->nr_balance_failed = 0;
3080
3081 if (likely(!active_balance)) {
3082 /* We were unbalanced, so reset the balancing interval */
3083 sd->balance_interval = sd->min_interval;
3084 } else {
3085 /*
3086 * If we've begun active balancing, start to back off. This
3087 * case may not be covered by the all_pinned logic if there
3088 * is only 1 task on the busy runqueue (because we don't call
3089 * move_tasks).
3090 */
3091 if (sd->balance_interval < sd->max_interval)
3092 sd->balance_interval *= 2;
3093 }
3094
3095 if (!ld_moved && !sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
3096 !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
3097 ld_moved = -1;
3098
3099 goto out;
3100
3101out_balanced:
3102 schedstat_inc(sd, lb_balanced[idle]);
3103
3104 sd->nr_balance_failed = 0;
3105
3106out_one_pinned:
3107 /* tune up the balancing interval */
3108 if ((all_pinned && sd->balance_interval < MAX_PINNED_INTERVAL) ||
3109 (sd->balance_interval < sd->max_interval))
3110 sd->balance_interval *= 2;
3111
3112 if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
3113 !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
3114 ld_moved = -1;
3115 else
3116 ld_moved = 0;
3117out:
3118 if (ld_moved)
3119 update_shares(sd);
3120 return ld_moved;
3121}
3122
3123/*
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003124 * idle_balance is called by schedule() if this_cpu is about to become
3125 * idle. Attempts to pull tasks from other CPUs.
3126 */
3127static void idle_balance(int this_cpu, struct rq *this_rq)
3128{
3129 struct sched_domain *sd;
3130 int pulled_task = 0;
3131 unsigned long next_balance = jiffies + HZ;
3132
3133 this_rq->idle_stamp = this_rq->clock;
3134
3135 if (this_rq->avg_idle < sysctl_sched_migration_cost)
3136 return;
3137
Peter Zijlstraf492e122009-12-23 15:29:42 +01003138 /*
3139 * Drop the rq->lock, but keep IRQ/preempt disabled.
3140 */
3141 raw_spin_unlock(&this_rq->lock);
3142
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003143 for_each_domain(this_cpu, sd) {
3144 unsigned long interval;
Peter Zijlstraf492e122009-12-23 15:29:42 +01003145 int balance = 1;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003146
3147 if (!(sd->flags & SD_LOAD_BALANCE))
3148 continue;
3149
Peter Zijlstraf492e122009-12-23 15:29:42 +01003150 if (sd->flags & SD_BALANCE_NEWIDLE) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003151 /* If we've pulled tasks over stop searching: */
Peter Zijlstraf492e122009-12-23 15:29:42 +01003152 pulled_task = load_balance(this_cpu, this_rq,
3153 sd, CPU_NEWLY_IDLE, &balance);
3154 }
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003155
3156 interval = msecs_to_jiffies(sd->balance_interval);
3157 if (time_after(next_balance, sd->last_balance + interval))
3158 next_balance = sd->last_balance + interval;
3159 if (pulled_task) {
3160 this_rq->idle_stamp = 0;
3161 break;
3162 }
3163 }
Peter Zijlstraf492e122009-12-23 15:29:42 +01003164
3165 raw_spin_lock(&this_rq->lock);
3166
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003167 if (pulled_task || time_after(jiffies, this_rq->next_balance)) {
3168 /*
3169 * We are going idle. next_balance may be set based on
3170 * a busy processor. So reset next_balance.
3171 */
3172 this_rq->next_balance = next_balance;
3173 }
3174}
3175
3176/*
Tejun Heo969c7922010-05-06 18:49:21 +02003177 * active_load_balance_cpu_stop is run by cpu stopper. It pushes
3178 * running tasks off the busiest CPU onto idle CPUs. It requires at
3179 * least 1 task to be running on each physical CPU where possible, and
3180 * avoids physical / logical imbalances.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003181 */
Tejun Heo969c7922010-05-06 18:49:21 +02003182static int active_load_balance_cpu_stop(void *data)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003183{
Tejun Heo969c7922010-05-06 18:49:21 +02003184 struct rq *busiest_rq = data;
3185 int busiest_cpu = cpu_of(busiest_rq);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003186 int target_cpu = busiest_rq->push_cpu;
Tejun Heo969c7922010-05-06 18:49:21 +02003187 struct rq *target_rq = cpu_rq(target_cpu);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003188 struct sched_domain *sd;
Tejun Heo969c7922010-05-06 18:49:21 +02003189
3190 raw_spin_lock_irq(&busiest_rq->lock);
3191
3192 /* make sure the requested cpu hasn't gone down in the meantime */
3193 if (unlikely(busiest_cpu != smp_processor_id() ||
3194 !busiest_rq->active_balance))
3195 goto out_unlock;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003196
3197 /* Is there any task to move? */
3198 if (busiest_rq->nr_running <= 1)
Tejun Heo969c7922010-05-06 18:49:21 +02003199 goto out_unlock;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003200
3201 /*
3202 * This condition is "impossible", if it occurs
3203 * we need to fix it. Originally reported by
3204 * Bjorn Helgaas on a 128-cpu setup.
3205 */
3206 BUG_ON(busiest_rq == target_rq);
3207
3208 /* move a task from busiest_rq to target_rq */
3209 double_lock_balance(busiest_rq, target_rq);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003210
3211 /* Search for an sd spanning us and the target CPU. */
3212 for_each_domain(target_cpu, sd) {
3213 if ((sd->flags & SD_LOAD_BALANCE) &&
3214 cpumask_test_cpu(busiest_cpu, sched_domain_span(sd)))
3215 break;
3216 }
3217
3218 if (likely(sd)) {
3219 schedstat_inc(sd, alb_count);
3220
3221 if (move_one_task(target_rq, target_cpu, busiest_rq,
3222 sd, CPU_IDLE))
3223 schedstat_inc(sd, alb_pushed);
3224 else
3225 schedstat_inc(sd, alb_failed);
3226 }
3227 double_unlock_balance(busiest_rq, target_rq);
Tejun Heo969c7922010-05-06 18:49:21 +02003228out_unlock:
3229 busiest_rq->active_balance = 0;
3230 raw_spin_unlock_irq(&busiest_rq->lock);
3231 return 0;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003232}
3233
3234#ifdef CONFIG_NO_HZ
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003235
3236static DEFINE_PER_CPU(struct call_single_data, remote_sched_softirq_cb);
3237
3238static void trigger_sched_softirq(void *data)
3239{
3240 raise_softirq_irqoff(SCHED_SOFTIRQ);
3241}
3242
3243static inline void init_sched_softirq_csd(struct call_single_data *csd)
3244{
3245 csd->func = trigger_sched_softirq;
3246 csd->info = NULL;
3247 csd->flags = 0;
3248 csd->priv = 0;
3249}
3250
3251/*
3252 * idle load balancing details
3253 * - One of the idle CPUs nominates itself as idle load_balancer, while
3254 * entering idle.
3255 * - This idle load balancer CPU will also go into tickless mode when
3256 * it is idle, just like all other idle CPUs
3257 * - When one of the busy CPUs notice that there may be an idle rebalancing
3258 * needed, they will kick the idle load balancer, which then does idle
3259 * load balancing for all the idle CPUs.
3260 */
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003261static struct {
3262 atomic_t load_balancer;
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003263 atomic_t first_pick_cpu;
3264 atomic_t second_pick_cpu;
3265 cpumask_var_t idle_cpus_mask;
3266 cpumask_var_t grp_idle_mask;
3267 unsigned long next_balance; /* in jiffy units */
3268} nohz ____cacheline_aligned;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003269
3270int get_nohz_load_balancer(void)
3271{
3272 return atomic_read(&nohz.load_balancer);
3273}
3274
3275#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
3276/**
3277 * lowest_flag_domain - Return lowest sched_domain containing flag.
3278 * @cpu: The cpu whose lowest level of sched domain is to
3279 * be returned.
3280 * @flag: The flag to check for the lowest sched_domain
3281 * for the given cpu.
3282 *
3283 * Returns the lowest sched_domain of a cpu which contains the given flag.
3284 */
3285static inline struct sched_domain *lowest_flag_domain(int cpu, int flag)
3286{
3287 struct sched_domain *sd;
3288
3289 for_each_domain(cpu, sd)
3290 if (sd && (sd->flags & flag))
3291 break;
3292
3293 return sd;
3294}
3295
3296/**
3297 * for_each_flag_domain - Iterates over sched_domains containing the flag.
3298 * @cpu: The cpu whose domains we're iterating over.
3299 * @sd: variable holding the value of the power_savings_sd
3300 * for cpu.
3301 * @flag: The flag to filter the sched_domains to be iterated.
3302 *
3303 * Iterates over all the scheduler domains for a given cpu that has the 'flag'
3304 * set, starting from the lowest sched_domain to the highest.
3305 */
3306#define for_each_flag_domain(cpu, sd, flag) \
3307 for (sd = lowest_flag_domain(cpu, flag); \
3308 (sd && (sd->flags & flag)); sd = sd->parent)
3309
3310/**
3311 * is_semi_idle_group - Checks if the given sched_group is semi-idle.
3312 * @ilb_group: group to be checked for semi-idleness
3313 *
3314 * Returns: 1 if the group is semi-idle. 0 otherwise.
3315 *
3316 * We define a sched_group to be semi idle if it has atleast one idle-CPU
3317 * and atleast one non-idle CPU. This helper function checks if the given
3318 * sched_group is semi-idle or not.
3319 */
3320static inline int is_semi_idle_group(struct sched_group *ilb_group)
3321{
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003322 cpumask_and(nohz.grp_idle_mask, nohz.idle_cpus_mask,
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003323 sched_group_cpus(ilb_group));
3324
3325 /*
3326 * A sched_group is semi-idle when it has atleast one busy cpu
3327 * and atleast one idle cpu.
3328 */
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003329 if (cpumask_empty(nohz.grp_idle_mask))
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003330 return 0;
3331
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003332 if (cpumask_equal(nohz.grp_idle_mask, sched_group_cpus(ilb_group)))
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003333 return 0;
3334
3335 return 1;
3336}
3337/**
3338 * find_new_ilb - Finds the optimum idle load balancer for nomination.
3339 * @cpu: The cpu which is nominating a new idle_load_balancer.
3340 *
3341 * Returns: Returns the id of the idle load balancer if it exists,
3342 * Else, returns >= nr_cpu_ids.
3343 *
3344 * This algorithm picks the idle load balancer such that it belongs to a
3345 * semi-idle powersavings sched_domain. The idea is to try and avoid
3346 * completely idle packages/cores just for the purpose of idle load balancing
3347 * when there are other idle cpu's which are better suited for that job.
3348 */
3349static int find_new_ilb(int cpu)
3350{
3351 struct sched_domain *sd;
3352 struct sched_group *ilb_group;
3353
3354 /*
3355 * Have idle load balancer selection from semi-idle packages only
3356 * when power-aware load balancing is enabled
3357 */
3358 if (!(sched_smt_power_savings || sched_mc_power_savings))
3359 goto out_done;
3360
3361 /*
3362 * Optimize for the case when we have no idle CPUs or only one
3363 * idle CPU. Don't walk the sched_domain hierarchy in such cases
3364 */
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003365 if (cpumask_weight(nohz.idle_cpus_mask) < 2)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003366 goto out_done;
3367
3368 for_each_flag_domain(cpu, sd, SD_POWERSAVINGS_BALANCE) {
3369 ilb_group = sd->groups;
3370
3371 do {
3372 if (is_semi_idle_group(ilb_group))
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003373 return cpumask_first(nohz.grp_idle_mask);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003374
3375 ilb_group = ilb_group->next;
3376
3377 } while (ilb_group != sd->groups);
3378 }
3379
3380out_done:
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003381 return nr_cpu_ids;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003382}
3383#else /* (CONFIG_SCHED_MC || CONFIG_SCHED_SMT) */
3384static inline int find_new_ilb(int call_cpu)
3385{
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003386 return nr_cpu_ids;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003387}
3388#endif
3389
3390/*
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003391 * Kick a CPU to do the nohz balancing, if it is time for it. We pick the
3392 * nohz_load_balancer CPU (if there is one) otherwise fallback to any idle
3393 * CPU (if there is one).
3394 */
3395static void nohz_balancer_kick(int cpu)
3396{
3397 int ilb_cpu;
3398
3399 nohz.next_balance++;
3400
3401 ilb_cpu = get_nohz_load_balancer();
3402
3403 if (ilb_cpu >= nr_cpu_ids) {
3404 ilb_cpu = cpumask_first(nohz.idle_cpus_mask);
3405 if (ilb_cpu >= nr_cpu_ids)
3406 return;
3407 }
3408
3409 if (!cpu_rq(ilb_cpu)->nohz_balance_kick) {
3410 struct call_single_data *cp;
3411
3412 cpu_rq(ilb_cpu)->nohz_balance_kick = 1;
3413 cp = &per_cpu(remote_sched_softirq_cb, cpu);
3414 __smp_call_function_single(ilb_cpu, cp, 0);
3415 }
3416 return;
3417}
3418
3419/*
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003420 * This routine will try to nominate the ilb (idle load balancing)
3421 * owner among the cpus whose ticks are stopped. ilb owner will do the idle
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003422 * load balancing on behalf of all those cpus.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003423 *
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003424 * When the ilb owner becomes busy, we will not have new ilb owner until some
3425 * idle CPU wakes up and goes back to idle or some busy CPU tries to kick
3426 * idle load balancing by kicking one of the idle CPUs.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003427 *
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003428 * Ticks are stopped for the ilb owner as well, with busy CPU kicking this
3429 * ilb owner CPU in future (when there is a need for idle load balancing on
3430 * behalf of all idle CPUs).
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003431 */
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003432void select_nohz_load_balancer(int stop_tick)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003433{
3434 int cpu = smp_processor_id();
3435
3436 if (stop_tick) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003437 if (!cpu_active(cpu)) {
3438 if (atomic_read(&nohz.load_balancer) != cpu)
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003439 return;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003440
3441 /*
3442 * If we are going offline and still the leader,
3443 * give up!
3444 */
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003445 if (atomic_cmpxchg(&nohz.load_balancer, cpu,
3446 nr_cpu_ids) != cpu)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003447 BUG();
3448
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003449 return;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003450 }
3451
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003452 cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003453
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003454 if (atomic_read(&nohz.first_pick_cpu) == cpu)
3455 atomic_cmpxchg(&nohz.first_pick_cpu, cpu, nr_cpu_ids);
3456 if (atomic_read(&nohz.second_pick_cpu) == cpu)
3457 atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003458
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003459 if (atomic_read(&nohz.load_balancer) >= nr_cpu_ids) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003460 int new_ilb;
3461
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003462 /* make me the ilb owner */
3463 if (atomic_cmpxchg(&nohz.load_balancer, nr_cpu_ids,
3464 cpu) != nr_cpu_ids)
3465 return;
3466
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003467 /*
3468 * Check to see if there is a more power-efficient
3469 * ilb.
3470 */
3471 new_ilb = find_new_ilb(cpu);
3472 if (new_ilb < nr_cpu_ids && new_ilb != cpu) {
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003473 atomic_set(&nohz.load_balancer, nr_cpu_ids);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003474 resched_cpu(new_ilb);
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003475 return;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003476 }
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003477 return;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003478 }
3479 } else {
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003480 if (!cpumask_test_cpu(cpu, nohz.idle_cpus_mask))
3481 return;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003482
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003483 cpumask_clear_cpu(cpu, nohz.idle_cpus_mask);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003484
3485 if (atomic_read(&nohz.load_balancer) == cpu)
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003486 if (atomic_cmpxchg(&nohz.load_balancer, cpu,
3487 nr_cpu_ids) != cpu)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003488 BUG();
3489 }
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003490 return;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003491}
3492#endif
3493
3494static DEFINE_SPINLOCK(balancing);
3495
3496/*
3497 * It checks each scheduling domain to see if it is due to be balanced,
3498 * and initiates a balancing operation if so.
3499 *
3500 * Balancing parameters are set up in arch_init_sched_domains.
3501 */
3502static void rebalance_domains(int cpu, enum cpu_idle_type idle)
3503{
3504 int balance = 1;
3505 struct rq *rq = cpu_rq(cpu);
3506 unsigned long interval;
3507 struct sched_domain *sd;
3508 /* Earliest time when we have to do rebalance again */
3509 unsigned long next_balance = jiffies + 60*HZ;
3510 int update_next_balance = 0;
3511 int need_serialize;
3512
3513 for_each_domain(cpu, sd) {
3514 if (!(sd->flags & SD_LOAD_BALANCE))
3515 continue;
3516
3517 interval = sd->balance_interval;
3518 if (idle != CPU_IDLE)
3519 interval *= sd->busy_factor;
3520
3521 /* scale ms to jiffies */
3522 interval = msecs_to_jiffies(interval);
3523 if (unlikely(!interval))
3524 interval = 1;
3525 if (interval > HZ*NR_CPUS/10)
3526 interval = HZ*NR_CPUS/10;
3527
3528 need_serialize = sd->flags & SD_SERIALIZE;
3529
3530 if (need_serialize) {
3531 if (!spin_trylock(&balancing))
3532 goto out;
3533 }
3534
3535 if (time_after_eq(jiffies, sd->last_balance + interval)) {
3536 if (load_balance(cpu, rq, sd, idle, &balance)) {
3537 /*
3538 * We've pulled tasks over so either we're no
3539 * longer idle, or one of our SMT siblings is
3540 * not idle.
3541 */
3542 idle = CPU_NOT_IDLE;
3543 }
3544 sd->last_balance = jiffies;
3545 }
3546 if (need_serialize)
3547 spin_unlock(&balancing);
3548out:
3549 if (time_after(next_balance, sd->last_balance + interval)) {
3550 next_balance = sd->last_balance + interval;
3551 update_next_balance = 1;
3552 }
3553
3554 /*
3555 * Stop the load balance at this level. There is another
3556 * CPU in our sched group which is doing load balancing more
3557 * actively.
3558 */
3559 if (!balance)
3560 break;
3561 }
3562
3563 /*
3564 * next_balance will be updated only when there is a need.
3565 * When the cpu is attached to null domain for ex, it will not be
3566 * updated.
3567 */
3568 if (likely(update_next_balance))
3569 rq->next_balance = next_balance;
3570}
3571
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003572#ifdef CONFIG_NO_HZ
3573/*
3574 * In CONFIG_NO_HZ case, the idle balance kickee will do the
3575 * rebalancing for all the cpus for whom scheduler ticks are stopped.
3576 */
3577static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle)
3578{
3579 struct rq *this_rq = cpu_rq(this_cpu);
3580 struct rq *rq;
3581 int balance_cpu;
3582
3583 if (idle != CPU_IDLE || !this_rq->nohz_balance_kick)
3584 return;
3585
3586 for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
3587 if (balance_cpu == this_cpu)
3588 continue;
3589
3590 /*
3591 * If this cpu gets work to do, stop the load balancing
3592 * work being done for other cpus. Next load
3593 * balancing owner will pick it up.
3594 */
3595 if (need_resched()) {
3596 this_rq->nohz_balance_kick = 0;
3597 break;
3598 }
3599
3600 raw_spin_lock_irq(&this_rq->lock);
Suresh Siddha5343bdb2010-07-09 15:19:54 +02003601 update_rq_clock(this_rq);
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003602 update_cpu_load(this_rq);
3603 raw_spin_unlock_irq(&this_rq->lock);
3604
3605 rebalance_domains(balance_cpu, CPU_IDLE);
3606
3607 rq = cpu_rq(balance_cpu);
3608 if (time_after(this_rq->next_balance, rq->next_balance))
3609 this_rq->next_balance = rq->next_balance;
3610 }
3611 nohz.next_balance = this_rq->next_balance;
3612 this_rq->nohz_balance_kick = 0;
3613}
3614
3615/*
3616 * Current heuristic for kicking the idle load balancer
3617 * - first_pick_cpu is the one of the busy CPUs. It will kick
3618 * idle load balancer when it has more than one process active. This
3619 * eliminates the need for idle load balancing altogether when we have
3620 * only one running process in the system (common case).
3621 * - If there are more than one busy CPU, idle load balancer may have
3622 * to run for active_load_balance to happen (i.e., two busy CPUs are
3623 * SMT or core siblings and can run better if they move to different
3624 * physical CPUs). So, second_pick_cpu is the second of the busy CPUs
3625 * which will kick idle load balancer as soon as it has any load.
3626 */
3627static inline int nohz_kick_needed(struct rq *rq, int cpu)
3628{
3629 unsigned long now = jiffies;
3630 int ret;
3631 int first_pick_cpu, second_pick_cpu;
3632
3633 if (time_before(now, nohz.next_balance))
3634 return 0;
3635
3636 if (!rq->nr_running)
3637 return 0;
3638
3639 first_pick_cpu = atomic_read(&nohz.first_pick_cpu);
3640 second_pick_cpu = atomic_read(&nohz.second_pick_cpu);
3641
3642 if (first_pick_cpu < nr_cpu_ids && first_pick_cpu != cpu &&
3643 second_pick_cpu < nr_cpu_ids && second_pick_cpu != cpu)
3644 return 0;
3645
3646 ret = atomic_cmpxchg(&nohz.first_pick_cpu, nr_cpu_ids, cpu);
3647 if (ret == nr_cpu_ids || ret == cpu) {
3648 atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);
3649 if (rq->nr_running > 1)
3650 return 1;
3651 } else {
3652 ret = atomic_cmpxchg(&nohz.second_pick_cpu, nr_cpu_ids, cpu);
3653 if (ret == nr_cpu_ids || ret == cpu) {
3654 if (rq->nr_running)
3655 return 1;
3656 }
3657 }
3658 return 0;
3659}
3660#else
3661static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle) { }
3662#endif
3663
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003664/*
3665 * run_rebalance_domains is triggered when needed from the scheduler tick.
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003666 * Also triggered for nohz idle balancing (with nohz_balancing_kick set).
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003667 */
3668static void run_rebalance_domains(struct softirq_action *h)
3669{
3670 int this_cpu = smp_processor_id();
3671 struct rq *this_rq = cpu_rq(this_cpu);
3672 enum cpu_idle_type idle = this_rq->idle_at_tick ?
3673 CPU_IDLE : CPU_NOT_IDLE;
3674
3675 rebalance_domains(this_cpu, idle);
3676
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003677 /*
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003678 * If this cpu has a pending nohz_balance_kick, then do the
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003679 * balancing on behalf of the other idle cpus whose ticks are
3680 * stopped.
3681 */
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003682 nohz_idle_balance(this_cpu, idle);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003683}
3684
3685static inline int on_null_domain(int cpu)
3686{
Paul E. McKenney90a65012010-02-28 08:32:18 -08003687 return !rcu_dereference_sched(cpu_rq(cpu)->sd);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003688}
3689
3690/*
3691 * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003692 */
3693static inline void trigger_load_balance(struct rq *rq, int cpu)
3694{
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003695 /* Don't need to rebalance while attached to NULL domain */
3696 if (time_after_eq(jiffies, rq->next_balance) &&
3697 likely(!on_null_domain(cpu)))
3698 raise_softirq(SCHED_SOFTIRQ);
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003699#ifdef CONFIG_NO_HZ
3700 else if (nohz_kick_needed(rq, cpu) && likely(!on_null_domain(cpu)))
3701 nohz_balancer_kick(cpu);
3702#endif
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003703}
3704
Christian Ehrhardt0bcdcf22009-11-30 12:16:46 +01003705static void rq_online_fair(struct rq *rq)
3706{
3707 update_sysctl();
3708}
3709
3710static void rq_offline_fair(struct rq *rq)
3711{
3712 update_sysctl();
3713}
3714
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003715#else /* CONFIG_SMP */
3716
3717/*
3718 * on UP we do not need to balance between CPUs:
3719 */
3720static inline void idle_balance(int cpu, struct rq *rq)
3721{
3722}
3723
Dhaval Giani55e12e52008-06-24 23:39:43 +05303724#endif /* CONFIG_SMP */
Peter Williamse1d14842007-10-24 18:23:51 +02003725
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003726/*
3727 * scheduler tick hitting a task of our scheduling class:
3728 */
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01003729static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003730{
3731 struct cfs_rq *cfs_rq;
3732 struct sched_entity *se = &curr->se;
3733
3734 for_each_sched_entity(se) {
3735 cfs_rq = cfs_rq_of(se);
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01003736 entity_tick(cfs_rq, se, queued);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003737 }
3738}
3739
3740/*
Peter Zijlstracd29fe62009-11-27 17:32:46 +01003741 * called on fork with the child task as argument from the parent's context
3742 * - child not yet on the tasklist
3743 * - preemption disabled
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003744 */
Peter Zijlstracd29fe62009-11-27 17:32:46 +01003745static void task_fork_fair(struct task_struct *p)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003746{
Peter Zijlstracd29fe62009-11-27 17:32:46 +01003747 struct cfs_rq *cfs_rq = task_cfs_rq(current);
Ingo Molnar429d43b2007-10-15 17:00:03 +02003748 struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
Ingo Molnar00bf7bf2007-10-15 17:00:14 +02003749 int this_cpu = smp_processor_id();
Peter Zijlstracd29fe62009-11-27 17:32:46 +01003750 struct rq *rq = this_rq();
3751 unsigned long flags;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003752
Thomas Gleixner05fa7852009-11-17 14:28:38 +01003753 raw_spin_lock_irqsave(&rq->lock, flags);
Peter Zijlstracd29fe62009-11-27 17:32:46 +01003754
3755 if (unlikely(task_cpu(p) != this_cpu))
3756 __set_task_cpu(p, this_cpu);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003757
Ting Yang7109c4422007-08-28 12:53:24 +02003758 update_curr(cfs_rq);
Peter Zijlstracd29fe62009-11-27 17:32:46 +01003759
Mike Galbraithb5d9d732009-09-08 11:12:28 +02003760 if (curr)
3761 se->vruntime = curr->vruntime;
Peter Zijlstraaeb73b02007-10-15 17:00:05 +02003762 place_entity(cfs_rq, se, 1);
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02003763
Peter Zijlstracd29fe62009-11-27 17:32:46 +01003764 if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
Dmitry Adamushko87fefa32007-10-15 17:00:08 +02003765 /*
Ingo Molnaredcb60a2007-10-15 17:00:08 +02003766 * Upon rescheduling, sched_class::put_prev_task() will place
3767 * 'current' within the tree based on its new key value.
3768 */
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02003769 swap(curr->vruntime, se->vruntime);
Bharata B Raoaec0a512008-08-28 14:42:49 +05303770 resched_task(rq->curr);
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02003771 }
3772
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01003773 se->vruntime -= cfs_rq->min_vruntime;
3774
Thomas Gleixner05fa7852009-11-17 14:28:38 +01003775 raw_spin_unlock_irqrestore(&rq->lock, flags);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003776}
3777
Steven Rostedtcb469842008-01-25 21:08:22 +01003778/*
3779 * Priority of the task has changed. Check to see if we preempt
3780 * the current task.
3781 */
3782static void prio_changed_fair(struct rq *rq, struct task_struct *p,
3783 int oldprio, int running)
3784{
3785 /*
3786 * Reschedule if we are currently running on this runqueue and
3787 * our priority decreased, or if we are not currently running on
3788 * this runqueue and our priority is higher than the current's
3789 */
3790 if (running) {
3791 if (p->prio > oldprio)
3792 resched_task(rq->curr);
3793 } else
Peter Zijlstra15afe092008-09-20 23:38:02 +02003794 check_preempt_curr(rq, p, 0);
Steven Rostedtcb469842008-01-25 21:08:22 +01003795}
3796
3797/*
3798 * We switched to the sched_fair class.
3799 */
3800static void switched_to_fair(struct rq *rq, struct task_struct *p,
3801 int running)
3802{
3803 /*
3804 * We were most likely switched from sched_rt, so
3805 * kick off the schedule if running, otherwise just see
3806 * if we can still preempt the current task.
3807 */
3808 if (running)
3809 resched_task(rq->curr);
3810 else
Peter Zijlstra15afe092008-09-20 23:38:02 +02003811 check_preempt_curr(rq, p, 0);
Steven Rostedtcb469842008-01-25 21:08:22 +01003812}
3813
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02003814/* Account for a task changing its policy or group.
3815 *
3816 * This routine is mostly called to set cfs_rq->curr field when a task
3817 * migrates between groups/classes.
3818 */
3819static void set_curr_task_fair(struct rq *rq)
3820{
3821 struct sched_entity *se = &rq->curr->se;
3822
3823 for_each_sched_entity(se)
3824 set_next_entity(cfs_rq_of(se), se);
3825}
3826
Peter Zijlstra810b3812008-02-29 15:21:01 -05003827#ifdef CONFIG_FAIR_GROUP_SCHED
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01003828static void moved_group_fair(struct task_struct *p, int on_rq)
Peter Zijlstra810b3812008-02-29 15:21:01 -05003829{
3830 struct cfs_rq *cfs_rq = task_cfs_rq(p);
3831
3832 update_curr(cfs_rq);
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01003833 if (!on_rq)
3834 place_entity(cfs_rq, &p->se, 1);
Peter Zijlstra810b3812008-02-29 15:21:01 -05003835}
3836#endif
3837
H Hartley Sweeten6d686f42010-01-13 20:21:52 -07003838static unsigned int get_rr_interval_fair(struct rq *rq, struct task_struct *task)
Peter Williams0d721ce2009-09-21 01:31:53 +00003839{
3840 struct sched_entity *se = &task->se;
Peter Williams0d721ce2009-09-21 01:31:53 +00003841 unsigned int rr_interval = 0;
3842
3843 /*
3844 * Time slice is 0 for SCHED_OTHER tasks that are on an otherwise
3845 * idle runqueue:
3846 */
Peter Williams0d721ce2009-09-21 01:31:53 +00003847 if (rq->cfs.load.weight)
3848 rr_interval = NS_TO_JIFFIES(sched_slice(&rq->cfs, se));
Peter Williams0d721ce2009-09-21 01:31:53 +00003849
3850 return rr_interval;
3851}
3852
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003853/*
3854 * All the scheduling class methods:
3855 */
Ingo Molnar5522d5d2007-10-15 17:00:12 +02003856static const struct sched_class fair_sched_class = {
3857 .next = &idle_sched_class,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003858 .enqueue_task = enqueue_task_fair,
3859 .dequeue_task = dequeue_task_fair,
3860 .yield_task = yield_task_fair,
3861
Ingo Molnar2e09bf52007-10-15 17:00:05 +02003862 .check_preempt_curr = check_preempt_wakeup,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003863
3864 .pick_next_task = pick_next_task_fair,
3865 .put_prev_task = put_prev_task_fair,
3866
Peter Williams681f3e62007-10-24 18:23:51 +02003867#ifdef CONFIG_SMP
Li Zefan4ce72a22008-10-22 15:25:26 +08003868 .select_task_rq = select_task_rq_fair,
3869
Christian Ehrhardt0bcdcf22009-11-30 12:16:46 +01003870 .rq_online = rq_online_fair,
3871 .rq_offline = rq_offline_fair,
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01003872
3873 .task_waking = task_waking_fair,
Peter Williams681f3e62007-10-24 18:23:51 +02003874#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003875
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02003876 .set_curr_task = set_curr_task_fair,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003877 .task_tick = task_tick_fair,
Peter Zijlstracd29fe62009-11-27 17:32:46 +01003878 .task_fork = task_fork_fair,
Steven Rostedtcb469842008-01-25 21:08:22 +01003879
3880 .prio_changed = prio_changed_fair,
3881 .switched_to = switched_to_fair,
Peter Zijlstra810b3812008-02-29 15:21:01 -05003882
Peter Williams0d721ce2009-09-21 01:31:53 +00003883 .get_rr_interval = get_rr_interval_fair,
3884
Peter Zijlstra810b3812008-02-29 15:21:01 -05003885#ifdef CONFIG_FAIR_GROUP_SCHED
3886 .moved_group = moved_group_fair,
3887#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003888};
3889
3890#ifdef CONFIG_SCHED_DEBUG
Ingo Molnar5cef9ec2007-08-09 11:16:47 +02003891static void print_cfs_stats(struct seq_file *m, int cpu)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003892{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003893 struct cfs_rq *cfs_rq;
3894
Peter Zijlstra5973e5b2008-01-25 21:08:34 +01003895 rcu_read_lock();
Ingo Molnarc3b64f12007-08-09 11:16:51 +02003896 for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
Ingo Molnar5cef9ec2007-08-09 11:16:47 +02003897 print_cfs_rq(m, cpu, cfs_rq);
Peter Zijlstra5973e5b2008-01-25 21:08:34 +01003898 rcu_read_unlock();
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02003899}
3900#endif