blob: 9502aa899f735e3d205185a05919fcf7c5ca04b8 [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>
Sisir Koppaka3436ae12011-03-26 18:22:55 +053025#include <linux/cpumask.h>
Arjan van de Ven97455122008-01-25 21:08:34 +010026
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020027/*
Peter Zijlstra21805082007-08-25 18:41:53 +020028 * Targeted preemption latency for CPU-bound tasks:
Takuya Yoshikawa864616e2010-10-14 16:09:13 +090029 * (default: 6ms * (1 + ilog(ncpus)), units: nanoseconds)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020030 *
Peter Zijlstra21805082007-08-25 18:41:53 +020031 * NOTE: this latency value is not the same as the concept of
Ingo Molnard274a4c2007-10-15 17:00:14 +020032 * 'timeslice length' - timeslices in CFS are of variable length
33 * and have no persistent notion like in traditional, time-slice
34 * based scheduling concepts.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020035 *
Ingo Molnard274a4c2007-10-15 17:00:14 +020036 * (to see the precise effective timeslice length of your workload,
37 * run vmstat and monitor the context-switches (cs) field)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020038 */
Mike Galbraith21406922010-03-11 17:17:15 +010039unsigned int sysctl_sched_latency = 6000000ULL;
40unsigned int normalized_sysctl_sched_latency = 6000000ULL;
Ingo Molnar2bd8e6d2007-10-15 17:00:02 +020041
42/*
Christian Ehrhardt1983a922009-11-30 12:16:47 +010043 * The initial- and re-scaling of tunables is configurable
44 * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus))
45 *
46 * Options are:
47 * SCHED_TUNABLESCALING_NONE - unscaled, always *1
48 * SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus)
49 * SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus
50 */
51enum sched_tunable_scaling sysctl_sched_tunable_scaling
52 = SCHED_TUNABLESCALING_LOG;
53
54/*
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010055 * Minimal preemption granularity for CPU-bound tasks:
Takuya Yoshikawa864616e2010-10-14 16:09:13 +090056 * (default: 0.75 msec * (1 + ilog(ncpus)), units: nanoseconds)
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010057 */
Ingo Molnar0bf377b2010-09-12 08:14:52 +020058unsigned int sysctl_sched_min_granularity = 750000ULL;
59unsigned int normalized_sysctl_sched_min_granularity = 750000ULL;
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010060
61/*
62 * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
63 */
Ingo Molnar0bf377b2010-09-12 08:14:52 +020064static unsigned int sched_nr_latency = 8;
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010065
66/*
Mike Galbraith2bba22c2009-09-09 15:41:37 +020067 * After fork, child runs first. If set to 0 (default) then
Ingo Molnar2bd8e6d2007-10-15 17:00:02 +020068 * parent will (try to) run first.
69 */
Mike Galbraith2bba22c2009-09-09 15:41:37 +020070unsigned int sysctl_sched_child_runs_first __read_mostly;
Peter Zijlstra21805082007-08-25 18:41:53 +020071
72/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020073 * SCHED_OTHER wake-up granularity.
Mike Galbraith172e0822009-09-09 15:41:37 +020074 * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020075 *
76 * This option delays the preemption effects of decoupled workloads
77 * and reduces their over-scheduling. Synchronous workloads will still
78 * have immediate wakeup/sleep latencies.
79 */
Mike Galbraith172e0822009-09-09 15:41:37 +020080unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
Christian Ehrhardt0bcdcf22009-11-30 12:16:46 +010081unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020082
Ingo Molnarda84d962007-10-15 17:00:18 +020083const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
84
Paul Turnera7a4f8a2010-11-15 15:47:06 -080085/*
86 * The exponential sliding window over which load is averaged for shares
87 * distribution.
88 * (default: 10msec)
89 */
90unsigned int __read_mostly sysctl_sched_shares_window = 10000000UL;
91
Paul Turnerec12cb72011-07-21 09:43:30 -070092#ifdef CONFIG_CFS_BANDWIDTH
93/*
94 * Amount of runtime to allocate from global (tg) to local (per-cfs_rq) pool
95 * each time a cfs_rq requests quota.
96 *
97 * Note: in the case that the slice exceeds the runtime remaining (either due
98 * to consumption or the quota being specified to be smaller than the slice)
99 * we will always only issue the remaining available time.
100 *
101 * default: 5 msec, units: microseconds
102 */
103unsigned int sysctl_sched_cfs_bandwidth_slice = 5000UL;
104#endif
105
Peter Zijlstraa4c2f002008-10-17 19:27:03 +0200106static const struct sched_class fair_sched_class;
107
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200108/**************************************************************
109 * CFS operations on generic schedulable entities:
110 */
111
112#ifdef CONFIG_FAIR_GROUP_SCHED
113
114/* cpu runqueue to which this cfs_rq is attached */
115static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
116{
117 return cfs_rq->rq;
118}
119
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200120/* An entity is a task if it doesn't "own" a runqueue */
121#define entity_is_task(se) (!se->my_q)
122
Peter Zijlstra8f488942009-07-24 12:25:30 +0200123static inline struct task_struct *task_of(struct sched_entity *se)
124{
125#ifdef CONFIG_SCHED_DEBUG
126 WARN_ON_ONCE(!entity_is_task(se));
127#endif
128 return container_of(se, struct task_struct, se);
129}
130
Peter Zijlstrab7581492008-04-19 19:45:00 +0200131/* Walk up scheduling entities hierarchy */
132#define for_each_sched_entity(se) \
133 for (; se; se = se->parent)
134
135static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
136{
137 return p->se.cfs_rq;
138}
139
140/* runqueue on which this entity is (to be) queued */
141static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
142{
143 return se->cfs_rq;
144}
145
146/* runqueue "owned" by this group */
147static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
148{
149 return grp->my_q;
150}
151
Peter Zijlstra3d4b47b2010-11-15 15:47:01 -0800152static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
153{
154 if (!cfs_rq->on_list) {
Paul Turner67e86252010-11-15 15:47:05 -0800155 /*
156 * Ensure we either appear before our parent (if already
157 * enqueued) or force our parent to appear after us when it is
158 * enqueued. The fact that we always enqueue bottom-up
159 * reduces this to two cases.
160 */
161 if (cfs_rq->tg->parent &&
162 cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
163 list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
Peter Zijlstra3d4b47b2010-11-15 15:47:01 -0800164 &rq_of(cfs_rq)->leaf_cfs_rq_list);
Paul Turner67e86252010-11-15 15:47:05 -0800165 } else {
166 list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
167 &rq_of(cfs_rq)->leaf_cfs_rq_list);
168 }
Peter Zijlstra3d4b47b2010-11-15 15:47:01 -0800169
170 cfs_rq->on_list = 1;
171 }
172}
173
174static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
175{
176 if (cfs_rq->on_list) {
177 list_del_rcu(&cfs_rq->leaf_cfs_rq_list);
178 cfs_rq->on_list = 0;
179 }
180}
181
Peter Zijlstrab7581492008-04-19 19:45:00 +0200182/* Iterate thr' all leaf cfs_rq's on a runqueue */
183#define for_each_leaf_cfs_rq(rq, cfs_rq) \
184 list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
185
186/* Do the two (enqueued) entities belong to the same group ? */
187static inline int
188is_same_group(struct sched_entity *se, struct sched_entity *pse)
189{
190 if (se->cfs_rq == pse->cfs_rq)
191 return 1;
192
193 return 0;
194}
195
196static inline struct sched_entity *parent_entity(struct sched_entity *se)
197{
198 return se->parent;
199}
200
Peter Zijlstra464b7522008-10-24 11:06:15 +0200201/* return depth at which a sched entity is present in the hierarchy */
202static inline int depth_se(struct sched_entity *se)
203{
204 int depth = 0;
205
206 for_each_sched_entity(se)
207 depth++;
208
209 return depth;
210}
211
212static void
213find_matching_se(struct sched_entity **se, struct sched_entity **pse)
214{
215 int se_depth, pse_depth;
216
217 /*
218 * preemption test can be made between sibling entities who are in the
219 * same cfs_rq i.e who have a common parent. Walk up the hierarchy of
220 * both tasks until we find their ancestors who are siblings of common
221 * parent.
222 */
223
224 /* First walk up until both entities are at same depth */
225 se_depth = depth_se(*se);
226 pse_depth = depth_se(*pse);
227
228 while (se_depth > pse_depth) {
229 se_depth--;
230 *se = parent_entity(*se);
231 }
232
233 while (pse_depth > se_depth) {
234 pse_depth--;
235 *pse = parent_entity(*pse);
236 }
237
238 while (!is_same_group(*se, *pse)) {
239 *se = parent_entity(*se);
240 *pse = parent_entity(*pse);
241 }
242}
243
Peter Zijlstra8f488942009-07-24 12:25:30 +0200244#else /* !CONFIG_FAIR_GROUP_SCHED */
245
246static inline struct task_struct *task_of(struct sched_entity *se)
247{
248 return container_of(se, struct task_struct, se);
249}
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200250
251static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
252{
253 return container_of(cfs_rq, struct rq, cfs);
254}
255
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200256#define entity_is_task(se) 1
257
Peter Zijlstrab7581492008-04-19 19:45:00 +0200258#define for_each_sched_entity(se) \
259 for (; se; se = NULL)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200260
Peter Zijlstrab7581492008-04-19 19:45:00 +0200261static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200262{
Peter Zijlstrab7581492008-04-19 19:45:00 +0200263 return &task_rq(p)->cfs;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200264}
265
Peter Zijlstrab7581492008-04-19 19:45:00 +0200266static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
267{
268 struct task_struct *p = task_of(se);
269 struct rq *rq = task_rq(p);
270
271 return &rq->cfs;
272}
273
274/* runqueue "owned" by this group */
275static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
276{
277 return NULL;
278}
279
Peter Zijlstra3d4b47b2010-11-15 15:47:01 -0800280static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
281{
282}
283
284static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
285{
286}
287
Peter Zijlstrab7581492008-04-19 19:45:00 +0200288#define for_each_leaf_cfs_rq(rq, cfs_rq) \
289 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
290
291static inline int
292is_same_group(struct sched_entity *se, struct sched_entity *pse)
293{
294 return 1;
295}
296
297static inline struct sched_entity *parent_entity(struct sched_entity *se)
298{
299 return NULL;
300}
301
Peter Zijlstra464b7522008-10-24 11:06:15 +0200302static inline void
303find_matching_se(struct sched_entity **se, struct sched_entity **pse)
304{
305}
306
Peter Zijlstrab7581492008-04-19 19:45:00 +0200307#endif /* CONFIG_FAIR_GROUP_SCHED */
308
Paul Turnerec12cb72011-07-21 09:43:30 -0700309static void account_cfs_rq_runtime(struct cfs_rq *cfs_rq,
310 unsigned long delta_exec);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200311
312/**************************************************************
313 * Scheduling class tree data structure manipulation methods:
314 */
315
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200316static inline u64 max_vruntime(u64 min_vruntime, u64 vruntime)
Peter Zijlstra02e04312007-10-15 17:00:07 +0200317{
Peter Zijlstra368059a2007-10-15 17:00:11 +0200318 s64 delta = (s64)(vruntime - min_vruntime);
319 if (delta > 0)
Peter Zijlstra02e04312007-10-15 17:00:07 +0200320 min_vruntime = vruntime;
321
322 return min_vruntime;
323}
324
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200325static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
Peter Zijlstrab0ffd242007-10-15 17:00:12 +0200326{
327 s64 delta = (s64)(vruntime - min_vruntime);
328 if (delta < 0)
329 min_vruntime = vruntime;
330
331 return min_vruntime;
332}
333
Fabio Checconi54fdc582009-07-16 12:32:27 +0200334static inline int entity_before(struct sched_entity *a,
335 struct sched_entity *b)
336{
337 return (s64)(a->vruntime - b->vruntime) < 0;
338}
339
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200340static void update_min_vruntime(struct cfs_rq *cfs_rq)
341{
342 u64 vruntime = cfs_rq->min_vruntime;
343
344 if (cfs_rq->curr)
345 vruntime = cfs_rq->curr->vruntime;
346
347 if (cfs_rq->rb_leftmost) {
348 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
349 struct sched_entity,
350 run_node);
351
Peter Zijlstrae17036d2009-01-15 14:53:39 +0100352 if (!cfs_rq->curr)
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200353 vruntime = se->vruntime;
354 else
355 vruntime = min_vruntime(vruntime, se->vruntime);
356 }
357
358 cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
Peter Zijlstra3fe16982011-04-05 17:23:48 +0200359#ifndef CONFIG_64BIT
360 smp_wmb();
361 cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
362#endif
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200363}
364
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200365/*
366 * Enqueue an entity into the rb-tree:
367 */
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200368static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200369{
370 struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
371 struct rb_node *parent = NULL;
372 struct sched_entity *entry;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200373 int leftmost = 1;
374
375 /*
376 * Find the right place in the rbtree:
377 */
378 while (*link) {
379 parent = *link;
380 entry = rb_entry(parent, struct sched_entity, run_node);
381 /*
382 * We dont care about collisions. Nodes with
383 * the same key stay together.
384 */
Stephan Baerwolf2bd2d6f2011-07-20 14:46:59 +0200385 if (entity_before(se, entry)) {
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200386 link = &parent->rb_left;
387 } else {
388 link = &parent->rb_right;
389 leftmost = 0;
390 }
391 }
392
393 /*
394 * Maintain a cache of leftmost tree entries (it is frequently
395 * used):
396 */
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200397 if (leftmost)
Ingo Molnar57cb4992007-10-15 17:00:11 +0200398 cfs_rq->rb_leftmost = &se->run_node;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200399
400 rb_link_node(&se->run_node, parent, link);
401 rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200402}
403
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200404static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200405{
Peter Zijlstra3fe69742008-03-14 20:55:51 +0100406 if (cfs_rq->rb_leftmost == &se->run_node) {
407 struct rb_node *next_node;
Peter Zijlstra3fe69742008-03-14 20:55:51 +0100408
409 next_node = rb_next(&se->run_node);
410 cfs_rq->rb_leftmost = next_node;
Peter Zijlstra3fe69742008-03-14 20:55:51 +0100411 }
Ingo Molnare9acbff2007-10-15 17:00:04 +0200412
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200413 rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200414}
415
Rik van Rielac53db52011-02-01 09:51:03 -0500416static struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200417{
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100418 struct rb_node *left = cfs_rq->rb_leftmost;
419
420 if (!left)
421 return NULL;
422
423 return rb_entry(left, struct sched_entity, run_node);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200424}
425
Rik van Rielac53db52011-02-01 09:51:03 -0500426static struct sched_entity *__pick_next_entity(struct sched_entity *se)
427{
428 struct rb_node *next = rb_next(&se->run_node);
429
430 if (!next)
431 return NULL;
432
433 return rb_entry(next, struct sched_entity, run_node);
434}
435
436#ifdef CONFIG_SCHED_DEBUG
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100437static struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200438{
Ingo Molnar7eee3e62008-02-22 10:32:21 +0100439 struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200440
Balbir Singh70eee742008-02-22 13:25:53 +0530441 if (!last)
442 return NULL;
Ingo Molnar7eee3e62008-02-22 10:32:21 +0100443
444 return rb_entry(last, struct sched_entity, run_node);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200445}
446
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200447/**************************************************************
448 * Scheduling class statistics methods:
449 */
450
Christian Ehrhardtacb4a842009-11-30 12:16:48 +0100451int sched_proc_update_handler(struct ctl_table *table, int write,
Alexey Dobriyan8d65af72009-09-23 15:57:19 -0700452 void __user *buffer, size_t *lenp,
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100453 loff_t *ppos)
454{
Alexey Dobriyan8d65af72009-09-23 15:57:19 -0700455 int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
Christian Ehrhardtacb4a842009-11-30 12:16:48 +0100456 int factor = get_update_sysctl_factor();
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100457
458 if (ret || !write)
459 return ret;
460
461 sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
462 sysctl_sched_min_granularity);
463
Christian Ehrhardtacb4a842009-11-30 12:16:48 +0100464#define WRT_SYSCTL(name) \
465 (normalized_sysctl_##name = sysctl_##name / (factor))
466 WRT_SYSCTL(sched_min_granularity);
467 WRT_SYSCTL(sched_latency);
468 WRT_SYSCTL(sched_wakeup_granularity);
Christian Ehrhardtacb4a842009-11-30 12:16:48 +0100469#undef WRT_SYSCTL
470
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100471 return 0;
472}
473#endif
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200474
475/*
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200476 * delta /= w
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200477 */
478static inline unsigned long
479calc_delta_fair(unsigned long delta, struct sched_entity *se)
480{
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200481 if (unlikely(se->load.weight != NICE_0_LOAD))
482 delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200483
484 return delta;
485}
486
487/*
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200488 * The idea is to set a period in which each task runs once.
489 *
490 * When there are too many tasks (sysctl_sched_nr_latency) we have to stretch
491 * this period because otherwise the slices get too small.
492 *
493 * p = (nr <= nl) ? l : l*nr/nl
494 */
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200495static u64 __sched_period(unsigned long nr_running)
496{
497 u64 period = sysctl_sched_latency;
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100498 unsigned long nr_latency = sched_nr_latency;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200499
500 if (unlikely(nr_running > nr_latency)) {
Peter Zijlstra4bf0b772008-01-25 21:08:21 +0100501 period = sysctl_sched_min_granularity;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200502 period *= nr_running;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200503 }
504
505 return period;
506}
507
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200508/*
509 * We calculate the wall-time slice from the period by taking a part
510 * proportional to the weight.
511 *
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200512 * s = p*P[w/rw]
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200513 */
Peter Zijlstra6d0f0ebd2007-10-15 17:00:05 +0200514static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
Peter Zijlstra21805082007-08-25 18:41:53 +0200515{
Mike Galbraith0a582442009-01-02 12:16:42 +0100516 u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200517
Mike Galbraith0a582442009-01-02 12:16:42 +0100518 for_each_sched_entity(se) {
Lin Ming6272d682009-01-15 17:17:15 +0100519 struct load_weight *load;
Christian Engelmayer3104bf02009-06-16 10:35:12 +0200520 struct load_weight lw;
Lin Ming6272d682009-01-15 17:17:15 +0100521
522 cfs_rq = cfs_rq_of(se);
523 load = &cfs_rq->load;
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200524
Mike Galbraith0a582442009-01-02 12:16:42 +0100525 if (unlikely(!se->on_rq)) {
Christian Engelmayer3104bf02009-06-16 10:35:12 +0200526 lw = cfs_rq->load;
Mike Galbraith0a582442009-01-02 12:16:42 +0100527
528 update_load_add(&lw, se->load.weight);
529 load = &lw;
530 }
531 slice = calc_delta_mine(slice, se->load.weight, load);
532 }
533 return slice;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200534}
535
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200536/*
Peter Zijlstraac884de2008-04-19 19:45:00 +0200537 * We calculate the vruntime slice of a to be inserted task
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200538 *
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200539 * vs = s/w
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200540 */
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200541static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200542{
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200543 return calc_delta_fair(sched_slice(cfs_rq, se), se);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200544}
545
Paul Turnerd6b55912010-11-15 15:47:09 -0800546static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update);
Paul Turner6d5ab292011-01-21 20:45:01 -0800547static void update_cfs_shares(struct cfs_rq *cfs_rq);
Paul Turner3b3d1902010-11-15 15:47:08 -0800548
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200549/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200550 * Update the current task's runtime statistics. Skip current tasks that
551 * are not in our scheduling class.
552 */
553static inline void
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200554__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
555 unsigned long delta_exec)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200556{
Ingo Molnarbbdba7c2007-10-15 17:00:06 +0200557 unsigned long delta_exec_weighted;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200558
Lucas De Marchi41acab82010-03-10 23:37:45 -0300559 schedstat_set(curr->statistics.exec_max,
560 max((u64)delta_exec, curr->statistics.exec_max));
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200561
562 curr->sum_exec_runtime += delta_exec;
Ingo Molnar7a62eab2007-10-15 17:00:06 +0200563 schedstat_add(cfs_rq, exec_clock, delta_exec);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200564 delta_exec_weighted = calc_delta_fair(delta_exec, curr);
Peter Zijlstra88ec22d2009-12-16 18:04:41 +0100565
Ingo Molnare9acbff2007-10-15 17:00:04 +0200566 curr->vruntime += delta_exec_weighted;
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200567 update_min_vruntime(cfs_rq);
Paul Turner3b3d1902010-11-15 15:47:08 -0800568
Peter Zijlstra70caf8a2010-11-20 00:53:51 +0100569#if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
Paul Turner3b3d1902010-11-15 15:47:08 -0800570 cfs_rq->load_unacc_exec_time += delta_exec;
Paul Turner3b3d1902010-11-15 15:47:08 -0800571#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200572}
573
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200574static void update_curr(struct cfs_rq *cfs_rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200575{
Ingo Molnar429d43b2007-10-15 17:00:03 +0200576 struct sched_entity *curr = cfs_rq->curr;
Venkatesh Pallipadi305e6832010-10-04 17:03:21 -0700577 u64 now = rq_of(cfs_rq)->clock_task;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200578 unsigned long delta_exec;
579
580 if (unlikely(!curr))
581 return;
582
583 /*
584 * Get the amount of time the current task was running
585 * since the last time we changed load (this cannot
586 * overflow on 32 bits):
587 */
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200588 delta_exec = (unsigned long)(now - curr->exec_start);
Peter Zijlstra34f28ec2008-12-16 08:45:31 +0100589 if (!delta_exec)
590 return;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200591
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200592 __update_curr(cfs_rq, curr, delta_exec);
593 curr->exec_start = now;
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100594
595 if (entity_is_task(curr)) {
596 struct task_struct *curtask = task_of(curr);
597
Ingo Molnarf977bb42009-09-13 18:15:54 +0200598 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100599 cpuacct_charge(curtask, delta_exec);
Frank Mayharf06febc2008-09-12 09:54:39 -0700600 account_group_exec_runtime(curtask, delta_exec);
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100601 }
Paul Turnerec12cb72011-07-21 09:43:30 -0700602
603 account_cfs_rq_runtime(cfs_rq, delta_exec);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200604}
605
606static inline void
Ingo Molnar5870db52007-08-09 11:16:47 +0200607update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200608{
Lucas De Marchi41acab82010-03-10 23:37:45 -0300609 schedstat_set(se->statistics.wait_start, rq_of(cfs_rq)->clock);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200610}
611
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200612/*
613 * Task is being enqueued - update stats:
614 */
Ingo Molnard2417e52007-08-09 11:16:47 +0200615static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200616{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200617 /*
618 * Are we enqueueing a waiting task? (for current tasks
619 * a dequeue/enqueue event is a NOP)
620 */
Ingo Molnar429d43b2007-10-15 17:00:03 +0200621 if (se != cfs_rq->curr)
Ingo Molnar5870db52007-08-09 11:16:47 +0200622 update_stats_wait_start(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200623}
624
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200625static void
Ingo Molnar9ef0a962007-08-09 11:16:47 +0200626update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200627{
Lucas De Marchi41acab82010-03-10 23:37:45 -0300628 schedstat_set(se->statistics.wait_max, max(se->statistics.wait_max,
629 rq_of(cfs_rq)->clock - se->statistics.wait_start));
630 schedstat_set(se->statistics.wait_count, se->statistics.wait_count + 1);
631 schedstat_set(se->statistics.wait_sum, se->statistics.wait_sum +
632 rq_of(cfs_rq)->clock - se->statistics.wait_start);
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200633#ifdef CONFIG_SCHEDSTATS
634 if (entity_is_task(se)) {
635 trace_sched_stat_wait(task_of(se),
Lucas De Marchi41acab82010-03-10 23:37:45 -0300636 rq_of(cfs_rq)->clock - se->statistics.wait_start);
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200637 }
638#endif
Lucas De Marchi41acab82010-03-10 23:37:45 -0300639 schedstat_set(se->statistics.wait_start, 0);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200640}
641
642static inline void
Ingo Molnar19b6a2e2007-08-09 11:16:48 +0200643update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200644{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200645 /*
646 * Mark the end of the wait period if dequeueing a
647 * waiting task:
648 */
Ingo Molnar429d43b2007-10-15 17:00:03 +0200649 if (se != cfs_rq->curr)
Ingo Molnar9ef0a962007-08-09 11:16:47 +0200650 update_stats_wait_end(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200651}
652
653/*
654 * We are picking a new current task - update its stats:
655 */
656static inline void
Ingo Molnar79303e92007-08-09 11:16:47 +0200657update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200658{
659 /*
660 * We are starting a new run period:
661 */
Venkatesh Pallipadi305e6832010-10-04 17:03:21 -0700662 se->exec_start = rq_of(cfs_rq)->clock_task;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200663}
664
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200665/**************************************************
666 * Scheduling class queueing methods:
667 */
668
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200669#if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
670static void
671add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
672{
673 cfs_rq->task_weight += weight;
674}
675#else
676static inline void
677add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
678{
679}
680#endif
681
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200682static void
683account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
684{
685 update_load_add(&cfs_rq->load, se->load.weight);
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200686 if (!parent_entity(se))
687 inc_cpu_load(rq_of(cfs_rq), se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530688 if (entity_is_task(se)) {
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200689 add_cfs_task_weight(cfs_rq, se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530690 list_add(&se->group_node, &cfs_rq->tasks);
691 }
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200692 cfs_rq->nr_running++;
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200693}
694
695static void
696account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
697{
698 update_load_sub(&cfs_rq->load, se->load.weight);
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200699 if (!parent_entity(se))
700 dec_cpu_load(rq_of(cfs_rq), se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530701 if (entity_is_task(se)) {
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200702 add_cfs_task_weight(cfs_rq, -se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530703 list_del_init(&se->group_node);
704 }
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200705 cfs_rq->nr_running--;
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200706}
707
Yong Zhang3ff6dca2011-01-24 15:33:52 +0800708#ifdef CONFIG_FAIR_GROUP_SCHED
709# ifdef CONFIG_SMP
Paul Turnerd6b55912010-11-15 15:47:09 -0800710static void update_cfs_rq_load_contribution(struct cfs_rq *cfs_rq,
711 int global_update)
712{
713 struct task_group *tg = cfs_rq->tg;
714 long load_avg;
715
716 load_avg = div64_u64(cfs_rq->load_avg, cfs_rq->load_period+1);
717 load_avg -= cfs_rq->load_contribution;
718
719 if (global_update || abs(load_avg) > cfs_rq->load_contribution / 8) {
720 atomic_add(load_avg, &tg->load_weight);
721 cfs_rq->load_contribution += load_avg;
722 }
723}
724
725static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800726{
Paul Turnera7a4f8a2010-11-15 15:47:06 -0800727 u64 period = sysctl_sched_shares_window;
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800728 u64 now, delta;
Paul Turnere33078b2010-11-15 15:47:04 -0800729 unsigned long load = cfs_rq->load.weight;
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800730
Paul Turnerb815f192011-01-21 20:45:00 -0800731 if (cfs_rq->tg == &root_task_group)
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800732 return;
733
Paul Turner05ca62c2011-01-21 20:45:02 -0800734 now = rq_of(cfs_rq)->clock_task;
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800735 delta = now - cfs_rq->load_stamp;
736
Paul Turnere33078b2010-11-15 15:47:04 -0800737 /* truncate load history at 4 idle periods */
738 if (cfs_rq->load_stamp > cfs_rq->load_last &&
739 now - cfs_rq->load_last > 4 * period) {
740 cfs_rq->load_period = 0;
741 cfs_rq->load_avg = 0;
Paul Turnerf07333b2011-01-21 20:45:03 -0800742 delta = period - 1;
Paul Turnere33078b2010-11-15 15:47:04 -0800743 }
744
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800745 cfs_rq->load_stamp = now;
Paul Turner3b3d1902010-11-15 15:47:08 -0800746 cfs_rq->load_unacc_exec_time = 0;
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800747 cfs_rq->load_period += delta;
Paul Turnere33078b2010-11-15 15:47:04 -0800748 if (load) {
749 cfs_rq->load_last = now;
750 cfs_rq->load_avg += delta * load;
751 }
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800752
Paul Turnerd6b55912010-11-15 15:47:09 -0800753 /* consider updating load contribution on each fold or truncate */
754 if (global_update || cfs_rq->load_period > period
755 || !cfs_rq->load_period)
756 update_cfs_rq_load_contribution(cfs_rq, global_update);
757
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800758 while (cfs_rq->load_period > period) {
759 /*
760 * Inline assembly required to prevent the compiler
761 * optimising this loop into a divmod call.
762 * See __iter_div_u64_rem() for another example of this.
763 */
764 asm("" : "+rm" (cfs_rq->load_period));
765 cfs_rq->load_period /= 2;
766 cfs_rq->load_avg /= 2;
767 }
Peter Zijlstra3d4b47b2010-11-15 15:47:01 -0800768
Paul Turnere33078b2010-11-15 15:47:04 -0800769 if (!cfs_rq->curr && !cfs_rq->nr_running && !cfs_rq->load_avg)
770 list_del_leaf_cfs_rq(cfs_rq);
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800771}
772
Paul Turner6d5ab292011-01-21 20:45:01 -0800773static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
Yong Zhang3ff6dca2011-01-24 15:33:52 +0800774{
775 long load_weight, load, shares;
776
Paul Turner6d5ab292011-01-21 20:45:01 -0800777 load = cfs_rq->load.weight;
Yong Zhang3ff6dca2011-01-24 15:33:52 +0800778
779 load_weight = atomic_read(&tg->load_weight);
Yong Zhang3ff6dca2011-01-24 15:33:52 +0800780 load_weight += load;
Paul Turner6d5ab292011-01-21 20:45:01 -0800781 load_weight -= cfs_rq->load_contribution;
Yong Zhang3ff6dca2011-01-24 15:33:52 +0800782
783 shares = (tg->shares * load);
784 if (load_weight)
785 shares /= load_weight;
786
787 if (shares < MIN_SHARES)
788 shares = MIN_SHARES;
789 if (shares > tg->shares)
790 shares = tg->shares;
791
792 return shares;
793}
794
795static void update_entity_shares_tick(struct cfs_rq *cfs_rq)
796{
797 if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) {
798 update_cfs_load(cfs_rq, 0);
Paul Turner6d5ab292011-01-21 20:45:01 -0800799 update_cfs_shares(cfs_rq);
Yong Zhang3ff6dca2011-01-24 15:33:52 +0800800 }
801}
802# else /* CONFIG_SMP */
803static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
804{
805}
806
Paul Turner6d5ab292011-01-21 20:45:01 -0800807static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
Yong Zhang3ff6dca2011-01-24 15:33:52 +0800808{
809 return tg->shares;
810}
811
812static inline void update_entity_shares_tick(struct cfs_rq *cfs_rq)
813{
814}
815# endif /* CONFIG_SMP */
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800816static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
817 unsigned long weight)
818{
Paul Turner19e5eeb2010-12-15 19:10:18 -0800819 if (se->on_rq) {
820 /* commit outstanding execution time */
821 if (cfs_rq->curr == se)
822 update_curr(cfs_rq);
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800823 account_entity_dequeue(cfs_rq, se);
Paul Turner19e5eeb2010-12-15 19:10:18 -0800824 }
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800825
826 update_load_set(&se->load, weight);
827
828 if (se->on_rq)
829 account_entity_enqueue(cfs_rq, se);
830}
831
Paul Turner6d5ab292011-01-21 20:45:01 -0800832static void update_cfs_shares(struct cfs_rq *cfs_rq)
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800833{
834 struct task_group *tg;
835 struct sched_entity *se;
Yong Zhang3ff6dca2011-01-24 15:33:52 +0800836 long shares;
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800837
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800838 tg = cfs_rq->tg;
839 se = tg->se[cpu_of(rq_of(cfs_rq))];
840 if (!se)
841 return;
Yong Zhang3ff6dca2011-01-24 15:33:52 +0800842#ifndef CONFIG_SMP
843 if (likely(se->load.weight == tg->shares))
844 return;
845#endif
Paul Turner6d5ab292011-01-21 20:45:01 -0800846 shares = calc_cfs_shares(cfs_rq, tg);
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800847
848 reweight_entity(cfs_rq_of(se), se, shares);
849}
850#else /* CONFIG_FAIR_GROUP_SCHED */
Paul Turnerd6b55912010-11-15 15:47:09 -0800851static void update_cfs_load(struct cfs_rq *cfs_rq, int global_update)
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800852{
853}
854
Paul Turner6d5ab292011-01-21 20:45:01 -0800855static inline void update_cfs_shares(struct cfs_rq *cfs_rq)
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800856{
857}
Paul Turner43365bd2010-12-15 19:10:17 -0800858
859static inline void update_entity_shares_tick(struct cfs_rq *cfs_rq)
860{
861}
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800862#endif /* CONFIG_FAIR_GROUP_SCHED */
863
Ingo Molnar2396af62007-08-09 11:16:48 +0200864static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200865{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200866#ifdef CONFIG_SCHEDSTATS
Peter Zijlstrae4143142009-07-23 20:13:26 +0200867 struct task_struct *tsk = NULL;
868
869 if (entity_is_task(se))
870 tsk = task_of(se);
871
Lucas De Marchi41acab82010-03-10 23:37:45 -0300872 if (se->statistics.sleep_start) {
873 u64 delta = rq_of(cfs_rq)->clock - se->statistics.sleep_start;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200874
875 if ((s64)delta < 0)
876 delta = 0;
877
Lucas De Marchi41acab82010-03-10 23:37:45 -0300878 if (unlikely(delta > se->statistics.sleep_max))
879 se->statistics.sleep_max = delta;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200880
Lucas De Marchi41acab82010-03-10 23:37:45 -0300881 se->statistics.sleep_start = 0;
882 se->statistics.sum_sleep_runtime += delta;
Arjan van de Ven97455122008-01-25 21:08:34 +0100883
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200884 if (tsk) {
Peter Zijlstrae4143142009-07-23 20:13:26 +0200885 account_scheduler_latency(tsk, delta >> 10, 1);
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200886 trace_sched_stat_sleep(tsk, delta);
887 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200888 }
Lucas De Marchi41acab82010-03-10 23:37:45 -0300889 if (se->statistics.block_start) {
890 u64 delta = rq_of(cfs_rq)->clock - se->statistics.block_start;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200891
892 if ((s64)delta < 0)
893 delta = 0;
894
Lucas De Marchi41acab82010-03-10 23:37:45 -0300895 if (unlikely(delta > se->statistics.block_max))
896 se->statistics.block_max = delta;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200897
Lucas De Marchi41acab82010-03-10 23:37:45 -0300898 se->statistics.block_start = 0;
899 se->statistics.sum_sleep_runtime += delta;
Ingo Molnar30084fb2007-10-02 14:13:08 +0200900
Peter Zijlstrae4143142009-07-23 20:13:26 +0200901 if (tsk) {
Arjan van de Ven8f0dfc32009-07-20 11:26:58 -0700902 if (tsk->in_iowait) {
Lucas De Marchi41acab82010-03-10 23:37:45 -0300903 se->statistics.iowait_sum += delta;
904 se->statistics.iowait_count++;
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200905 trace_sched_stat_iowait(tsk, delta);
Arjan van de Ven8f0dfc32009-07-20 11:26:58 -0700906 }
907
Peter Zijlstrae4143142009-07-23 20:13:26 +0200908 /*
909 * Blocking time is in units of nanosecs, so shift by
910 * 20 to get a milliseconds-range estimation of the
911 * amount of time that the task spent sleeping:
912 */
913 if (unlikely(prof_on == SLEEP_PROFILING)) {
914 profile_hits(SLEEP_PROFILING,
915 (void *)get_wchan(tsk),
916 delta >> 20);
917 }
918 account_scheduler_latency(tsk, delta >> 10, 0);
Ingo Molnar30084fb2007-10-02 14:13:08 +0200919 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200920 }
921#endif
922}
923
Peter Zijlstraddc97292007-10-15 17:00:10 +0200924static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
925{
926#ifdef CONFIG_SCHED_DEBUG
927 s64 d = se->vruntime - cfs_rq->min_vruntime;
928
929 if (d < 0)
930 d = -d;
931
932 if (d > 3*sysctl_sched_latency)
933 schedstat_inc(cfs_rq, nr_spread_over);
934#endif
935}
936
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200937static void
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200938place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
939{
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200940 u64 vruntime = cfs_rq->min_vruntime;
Peter Zijlstra94dfb5e2007-10-15 17:00:05 +0200941
Peter Zijlstra2cb86002007-11-09 22:39:37 +0100942 /*
943 * The 'current' period is already promised to the current tasks,
944 * however the extra weight of the new task will slow them down a
945 * little, place the new task so that it fits in the slot that
946 * stays open at the end.
947 */
Peter Zijlstra94dfb5e2007-10-15 17:00:05 +0200948 if (initial && sched_feat(START_DEBIT))
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200949 vruntime += sched_vslice(cfs_rq, se);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200950
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200951 /* sleeps up to a single latency don't count. */
Mike Galbraith5ca98802010-03-11 17:17:17 +0100952 if (!initial) {
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200953 unsigned long thresh = sysctl_sched_latency;
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200954
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200955 /*
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200956 * Halve their sleep time's effect, to allow
957 * for a gentler effect of sleepers:
958 */
959 if (sched_feat(GENTLE_FAIR_SLEEPERS))
960 thresh >>= 1;
Ingo Molnar51e03042009-09-16 08:54:45 +0200961
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200962 vruntime -= thresh;
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200963 }
964
Mike Galbraithb5d9d732009-09-08 11:12:28 +0200965 /* ensure we never gain time by being placed backwards. */
966 vruntime = max_vruntime(se->vruntime, vruntime);
967
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200968 se->vruntime = vruntime;
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200969}
970
971static void
Peter Zijlstra88ec22d2009-12-16 18:04:41 +0100972enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200973{
974 /*
Peter Zijlstra88ec22d2009-12-16 18:04:41 +0100975 * Update the normalized vruntime before updating min_vruntime
976 * through callig update_curr().
977 */
Peter Zijlstra371fd7e2010-03-24 16:38:48 +0100978 if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
Peter Zijlstra88ec22d2009-12-16 18:04:41 +0100979 se->vruntime += cfs_rq->min_vruntime;
980
981 /*
Dmitry Adamushkoa2a2d682007-10-15 17:00:13 +0200982 * Update run-time statistics of the 'current'.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200983 */
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200984 update_curr(cfs_rq);
Paul Turnerd6b55912010-11-15 15:47:09 -0800985 update_cfs_load(cfs_rq, 0);
Peter Zijlstraa9922412008-05-05 23:56:17 +0200986 account_entity_enqueue(cfs_rq, se);
Paul Turner6d5ab292011-01-21 20:45:01 -0800987 update_cfs_shares(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200988
Peter Zijlstra88ec22d2009-12-16 18:04:41 +0100989 if (flags & ENQUEUE_WAKEUP) {
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200990 place_entity(cfs_rq, se, 0);
Ingo Molnar2396af62007-08-09 11:16:48 +0200991 enqueue_sleeper(cfs_rq, se);
Ingo Molnare9acbff2007-10-15 17:00:04 +0200992 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200993
Ingo Molnard2417e52007-08-09 11:16:47 +0200994 update_stats_enqueue(cfs_rq, se);
Peter Zijlstraddc97292007-10-15 17:00:10 +0200995 check_spread(cfs_rq, se);
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200996 if (se != cfs_rq->curr)
997 __enqueue_entity(cfs_rq, se);
Peter Zijlstra2069dd72010-11-15 15:47:00 -0800998 se->on_rq = 1;
Peter Zijlstra3d4b47b2010-11-15 15:47:01 -0800999
1000 if (cfs_rq->nr_running == 1)
1001 list_add_leaf_cfs_rq(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001002}
1003
Rik van Riel2c13c9192011-02-01 09:48:37 -05001004static void __clear_buddies_last(struct sched_entity *se)
Peter Zijlstra2002c692008-11-11 11:52:33 +01001005{
Rik van Riel2c13c9192011-02-01 09:48:37 -05001006 for_each_sched_entity(se) {
1007 struct cfs_rq *cfs_rq = cfs_rq_of(se);
1008 if (cfs_rq->last == se)
1009 cfs_rq->last = NULL;
1010 else
1011 break;
1012 }
1013}
Peter Zijlstra2002c692008-11-11 11:52:33 +01001014
Rik van Riel2c13c9192011-02-01 09:48:37 -05001015static void __clear_buddies_next(struct sched_entity *se)
1016{
1017 for_each_sched_entity(se) {
1018 struct cfs_rq *cfs_rq = cfs_rq_of(se);
1019 if (cfs_rq->next == se)
1020 cfs_rq->next = NULL;
1021 else
1022 break;
1023 }
Peter Zijlstra2002c692008-11-11 11:52:33 +01001024}
1025
Rik van Rielac53db52011-02-01 09:51:03 -05001026static void __clear_buddies_skip(struct sched_entity *se)
1027{
1028 for_each_sched_entity(se) {
1029 struct cfs_rq *cfs_rq = cfs_rq_of(se);
1030 if (cfs_rq->skip == se)
1031 cfs_rq->skip = NULL;
1032 else
1033 break;
1034 }
1035}
1036
Peter Zijlstraa571bbe2009-01-28 14:51:40 +01001037static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
1038{
Rik van Riel2c13c9192011-02-01 09:48:37 -05001039 if (cfs_rq->last == se)
1040 __clear_buddies_last(se);
1041
1042 if (cfs_rq->next == se)
1043 __clear_buddies_next(se);
Rik van Rielac53db52011-02-01 09:51:03 -05001044
1045 if (cfs_rq->skip == se)
1046 __clear_buddies_skip(se);
Peter Zijlstraa571bbe2009-01-28 14:51:40 +01001047}
1048
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001049static void
Peter Zijlstra371fd7e2010-03-24 16:38:48 +01001050dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001051{
Dmitry Adamushkoa2a2d682007-10-15 17:00:13 +02001052 /*
1053 * Update run-time statistics of the 'current'.
1054 */
1055 update_curr(cfs_rq);
1056
Ingo Molnar19b6a2e2007-08-09 11:16:48 +02001057 update_stats_dequeue(cfs_rq, se);
Peter Zijlstra371fd7e2010-03-24 16:38:48 +01001058 if (flags & DEQUEUE_SLEEP) {
Peter Zijlstra67e9fb22007-10-15 17:00:10 +02001059#ifdef CONFIG_SCHEDSTATS
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001060 if (entity_is_task(se)) {
1061 struct task_struct *tsk = task_of(se);
1062
1063 if (tsk->state & TASK_INTERRUPTIBLE)
Lucas De Marchi41acab82010-03-10 23:37:45 -03001064 se->statistics.sleep_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001065 if (tsk->state & TASK_UNINTERRUPTIBLE)
Lucas De Marchi41acab82010-03-10 23:37:45 -03001066 se->statistics.block_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001067 }
Dmitry Adamushkodb36cc72007-10-15 17:00:06 +02001068#endif
Peter Zijlstra67e9fb22007-10-15 17:00:10 +02001069 }
1070
Peter Zijlstra2002c692008-11-11 11:52:33 +01001071 clear_buddies(cfs_rq, se);
Peter Zijlstra47932412008-11-04 21:25:09 +01001072
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001073 if (se != cfs_rq->curr)
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +02001074 __dequeue_entity(cfs_rq, se);
Peter Zijlstra2069dd72010-11-15 15:47:00 -08001075 se->on_rq = 0;
Paul Turnerd6b55912010-11-15 15:47:09 -08001076 update_cfs_load(cfs_rq, 0);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +02001077 account_entity_dequeue(cfs_rq, se);
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01001078
1079 /*
1080 * Normalize the entity after updating the min_vruntime because the
1081 * update can refer to the ->curr item and we need to reflect this
1082 * movement in our normalized position.
1083 */
Peter Zijlstra371fd7e2010-03-24 16:38:48 +01001084 if (!(flags & DEQUEUE_SLEEP))
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01001085 se->vruntime -= cfs_rq->min_vruntime;
Peter Zijlstra1e876232011-05-17 16:21:10 -07001086
1087 update_min_vruntime(cfs_rq);
1088 update_cfs_shares(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001089}
1090
1091/*
1092 * Preempt the current task with a newly woken task if needed:
1093 */
Peter Zijlstra7c92e542007-09-05 14:32:49 +02001094static void
Ingo Molnar2e09bf52007-10-15 17:00:05 +02001095check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001096{
Peter Zijlstra11697832007-09-05 14:32:49 +02001097 unsigned long ideal_runtime, delta_exec;
1098
Peter Zijlstra6d0f0ebd2007-10-15 17:00:05 +02001099 ideal_runtime = sched_slice(cfs_rq, curr);
Peter Zijlstra11697832007-09-05 14:32:49 +02001100 delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
Mike Galbraitha9f3e2b2009-01-28 14:51:39 +01001101 if (delta_exec > ideal_runtime) {
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001102 resched_task(rq_of(cfs_rq)->curr);
Mike Galbraitha9f3e2b2009-01-28 14:51:39 +01001103 /*
1104 * The current task ran long enough, ensure it doesn't get
1105 * re-elected due to buddy favours.
1106 */
1107 clear_buddies(cfs_rq, curr);
Mike Galbraithf685cea2009-10-23 23:09:22 +02001108 return;
1109 }
1110
1111 /*
1112 * Ensure that a task that missed wakeup preemption by a
1113 * narrow margin doesn't have to wait for a full slice.
1114 * This also mitigates buddy induced latencies under load.
1115 */
Mike Galbraithf685cea2009-10-23 23:09:22 +02001116 if (delta_exec < sysctl_sched_min_granularity)
1117 return;
1118
1119 if (cfs_rq->nr_running > 1) {
Rik van Rielac53db52011-02-01 09:51:03 -05001120 struct sched_entity *se = __pick_first_entity(cfs_rq);
Mike Galbraithf685cea2009-10-23 23:09:22 +02001121 s64 delta = curr->vruntime - se->vruntime;
1122
Mike Galbraithd7d82942011-01-05 05:41:17 +01001123 if (delta < 0)
1124 return;
1125
Mike Galbraithf685cea2009-10-23 23:09:22 +02001126 if (delta > ideal_runtime)
1127 resched_task(rq_of(cfs_rq)->curr);
Mike Galbraitha9f3e2b2009-01-28 14:51:39 +01001128 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001129}
1130
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001131static void
Ingo Molnar8494f412007-08-09 11:16:48 +02001132set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001133{
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001134 /* 'current' is not kept within the tree. */
1135 if (se->on_rq) {
1136 /*
1137 * Any task has to be enqueued before it get to execute on
1138 * a CPU. So account for the time it spent waiting on the
1139 * runqueue.
1140 */
1141 update_stats_wait_end(cfs_rq, se);
1142 __dequeue_entity(cfs_rq, se);
1143 }
1144
Ingo Molnar79303e92007-08-09 11:16:47 +02001145 update_stats_curr_start(cfs_rq, se);
Ingo Molnar429d43b2007-10-15 17:00:03 +02001146 cfs_rq->curr = se;
Ingo Molnareba1ed42007-10-15 17:00:02 +02001147#ifdef CONFIG_SCHEDSTATS
1148 /*
1149 * Track our maximum slice length, if the CPU's load is at
1150 * least twice that of our own weight (i.e. dont track it
1151 * when there are only lesser-weight tasks around):
1152 */
Dmitry Adamushko495eca42007-10-15 17:00:06 +02001153 if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
Lucas De Marchi41acab82010-03-10 23:37:45 -03001154 se->statistics.slice_max = max(se->statistics.slice_max,
Ingo Molnareba1ed42007-10-15 17:00:02 +02001155 se->sum_exec_runtime - se->prev_sum_exec_runtime);
1156 }
1157#endif
Peter Zijlstra4a55b452007-09-05 14:32:49 +02001158 se->prev_sum_exec_runtime = se->sum_exec_runtime;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001159}
1160
Peter Zijlstra3f3a4902008-10-24 11:06:16 +02001161static int
1162wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
1163
Rik van Rielac53db52011-02-01 09:51:03 -05001164/*
1165 * Pick the next process, keeping these things in mind, in this order:
1166 * 1) keep things fair between processes/task groups
1167 * 2) pick the "next" process, since someone really wants that to run
1168 * 3) pick the "last" process, for cache locality
1169 * 4) do not run the "skip" process, if something else is available
1170 */
Peter Zijlstraf4b67552008-11-04 21:25:07 +01001171static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
Peter Zijlstraaa2ac252008-03-14 21:12:12 +01001172{
Rik van Rielac53db52011-02-01 09:51:03 -05001173 struct sched_entity *se = __pick_first_entity(cfs_rq);
Mike Galbraithf685cea2009-10-23 23:09:22 +02001174 struct sched_entity *left = se;
Peter Zijlstraf4b67552008-11-04 21:25:07 +01001175
Rik van Rielac53db52011-02-01 09:51:03 -05001176 /*
1177 * Avoid running the skip buddy, if running something else can
1178 * be done without getting too unfair.
1179 */
1180 if (cfs_rq->skip == se) {
1181 struct sched_entity *second = __pick_next_entity(se);
1182 if (second && wakeup_preempt_entity(second, left) < 1)
1183 se = second;
1184 }
Peter Zijlstraaa2ac252008-03-14 21:12:12 +01001185
Mike Galbraithf685cea2009-10-23 23:09:22 +02001186 /*
1187 * Prefer last buddy, try to return the CPU to a preempted task.
1188 */
1189 if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
1190 se = cfs_rq->last;
1191
Rik van Rielac53db52011-02-01 09:51:03 -05001192 /*
1193 * Someone really wants this to run. If it's not unfair, run it.
1194 */
1195 if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
1196 se = cfs_rq->next;
1197
Mike Galbraithf685cea2009-10-23 23:09:22 +02001198 clear_buddies(cfs_rq, se);
Peter Zijlstra47932412008-11-04 21:25:09 +01001199
1200 return se;
Peter Zijlstraaa2ac252008-03-14 21:12:12 +01001201}
1202
Ingo Molnarab6cde22007-08-09 11:16:48 +02001203static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001204{
1205 /*
1206 * If still on the runqueue then deactivate_task()
1207 * was not called and update_curr() has to be done:
1208 */
1209 if (prev->on_rq)
Ingo Molnarb7cc0892007-08-09 11:16:47 +02001210 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001211
Peter Zijlstraddc97292007-10-15 17:00:10 +02001212 check_spread(cfs_rq, prev);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +02001213 if (prev->on_rq) {
Ingo Molnar5870db52007-08-09 11:16:47 +02001214 update_stats_wait_start(cfs_rq, prev);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +02001215 /* Put 'current' back into the tree. */
1216 __enqueue_entity(cfs_rq, prev);
1217 }
Ingo Molnar429d43b2007-10-15 17:00:03 +02001218 cfs_rq->curr = NULL;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001219}
1220
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001221static void
1222entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001223{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001224 /*
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +02001225 * Update run-time statistics of the 'current'.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001226 */
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +02001227 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001228
Paul Turner43365bd2010-12-15 19:10:17 -08001229 /*
1230 * Update share accounting for long-running entities.
1231 */
1232 update_entity_shares_tick(cfs_rq);
1233
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001234#ifdef CONFIG_SCHED_HRTICK
1235 /*
1236 * queued ticks are scheduled to match the slice, so don't bother
1237 * validating it and just reschedule.
1238 */
Harvey Harrison983ed7a2008-04-24 18:17:55 -07001239 if (queued) {
1240 resched_task(rq_of(cfs_rq)->curr);
1241 return;
1242 }
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001243 /*
1244 * don't let the period tick interfere with the hrtick preemption
1245 */
1246 if (!sched_feat(DOUBLE_TICK) &&
1247 hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
1248 return;
1249#endif
1250
Yong Zhang2c2efae2011-07-29 16:20:33 +08001251 if (cfs_rq->nr_running > 1)
Ingo Molnar2e09bf52007-10-15 17:00:05 +02001252 check_preempt_tick(cfs_rq, curr);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001253}
1254
Paul Turnerab84d312011-07-21 09:43:28 -07001255
1256/**************************************************
1257 * CFS bandwidth control machinery
1258 */
1259
1260#ifdef CONFIG_CFS_BANDWIDTH
1261/*
1262 * default period for cfs group bandwidth.
1263 * default: 0.1s, units: nanoseconds
1264 */
1265static inline u64 default_cfs_period(void)
1266{
1267 return 100000000ULL;
1268}
Paul Turnerec12cb72011-07-21 09:43:30 -07001269
1270static inline u64 sched_cfs_bandwidth_slice(void)
1271{
1272 return (u64)sysctl_sched_cfs_bandwidth_slice * NSEC_PER_USEC;
1273}
1274
1275static void assign_cfs_rq_runtime(struct cfs_rq *cfs_rq)
1276{
1277 struct task_group *tg = cfs_rq->tg;
1278 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
1279 u64 amount = 0, min_amount;
1280
1281 /* note: this is a positive sum as runtime_remaining <= 0 */
1282 min_amount = sched_cfs_bandwidth_slice() - cfs_rq->runtime_remaining;
1283
1284 raw_spin_lock(&cfs_b->lock);
1285 if (cfs_b->quota == RUNTIME_INF)
1286 amount = min_amount;
1287 else if (cfs_b->runtime > 0) {
1288 amount = min(cfs_b->runtime, min_amount);
1289 cfs_b->runtime -= amount;
1290 }
1291 raw_spin_unlock(&cfs_b->lock);
1292
1293 cfs_rq->runtime_remaining += amount;
1294}
1295
1296static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq,
1297 unsigned long delta_exec)
1298{
1299 if (!cfs_rq->runtime_enabled)
1300 return;
1301
1302 cfs_rq->runtime_remaining -= delta_exec;
1303 if (cfs_rq->runtime_remaining > 0)
1304 return;
1305
1306 assign_cfs_rq_runtime(cfs_rq);
1307}
1308
1309static __always_inline void account_cfs_rq_runtime(struct cfs_rq *cfs_rq,
1310 unsigned long delta_exec)
1311{
1312 if (!cfs_rq->runtime_enabled)
1313 return;
1314
1315 __account_cfs_rq_runtime(cfs_rq, delta_exec);
1316}
1317
1318#else
1319static void account_cfs_rq_runtime(struct cfs_rq *cfs_rq,
1320 unsigned long delta_exec) {}
Paul Turnerab84d312011-07-21 09:43:28 -07001321#endif
1322
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001323/**************************************************
1324 * CFS operations on tasks:
1325 */
1326
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001327#ifdef CONFIG_SCHED_HRTICK
1328static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
1329{
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001330 struct sched_entity *se = &p->se;
1331 struct cfs_rq *cfs_rq = cfs_rq_of(se);
1332
1333 WARN_ON(task_rq(p) != rq);
1334
1335 if (hrtick_enabled(rq) && cfs_rq->nr_running > 1) {
1336 u64 slice = sched_slice(cfs_rq, se);
1337 u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
1338 s64 delta = slice - ran;
1339
1340 if (delta < 0) {
1341 if (rq->curr == p)
1342 resched_task(p);
1343 return;
1344 }
1345
1346 /*
1347 * Don't schedule slices shorter than 10000ns, that just
1348 * doesn't make sense. Rely on vruntime for fairness.
1349 */
Peter Zijlstra31656512008-07-18 18:01:23 +02001350 if (rq->curr != p)
Peter Zijlstra157124c2008-07-28 11:53:11 +02001351 delta = max_t(s64, 10000LL, delta);
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001352
Peter Zijlstra31656512008-07-18 18:01:23 +02001353 hrtick_start(rq, delta);
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001354 }
1355}
Peter Zijlstraa4c2f002008-10-17 19:27:03 +02001356
1357/*
1358 * called from enqueue/dequeue and updates the hrtick when the
1359 * current task is from our class and nr_running is low enough
1360 * to matter.
1361 */
1362static void hrtick_update(struct rq *rq)
1363{
1364 struct task_struct *curr = rq->curr;
1365
1366 if (curr->sched_class != &fair_sched_class)
1367 return;
1368
1369 if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
1370 hrtick_start_fair(rq, curr);
1371}
Dhaval Giani55e12e52008-06-24 23:39:43 +05301372#else /* !CONFIG_SCHED_HRTICK */
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001373static inline void
1374hrtick_start_fair(struct rq *rq, struct task_struct *p)
1375{
1376}
Peter Zijlstraa4c2f002008-10-17 19:27:03 +02001377
1378static inline void hrtick_update(struct rq *rq)
1379{
1380}
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001381#endif
1382
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001383/*
1384 * The enqueue_task method is called before nr_running is
1385 * increased. Here we update the fair scheduling stats and
1386 * then put the task into the rbtree:
1387 */
Thomas Gleixnerea87bb72010-01-20 20:58:57 +00001388static void
Peter Zijlstra371fd7e2010-03-24 16:38:48 +01001389enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001390{
1391 struct cfs_rq *cfs_rq;
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001392 struct sched_entity *se = &p->se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001393
1394 for_each_sched_entity(se) {
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001395 if (se->on_rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001396 break;
1397 cfs_rq = cfs_rq_of(se);
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01001398 enqueue_entity(cfs_rq, se, flags);
Paul Turner953bfcd2011-07-21 09:43:27 -07001399 cfs_rq->h_nr_running++;
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01001400 flags = ENQUEUE_WAKEUP;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001401 }
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001402
Peter Zijlstra2069dd72010-11-15 15:47:00 -08001403 for_each_sched_entity(se) {
Lin Ming0f317142011-07-22 09:14:31 +08001404 cfs_rq = cfs_rq_of(se);
Paul Turner953bfcd2011-07-21 09:43:27 -07001405 cfs_rq->h_nr_running++;
Peter Zijlstra2069dd72010-11-15 15:47:00 -08001406
Paul Turnerd6b55912010-11-15 15:47:09 -08001407 update_cfs_load(cfs_rq, 0);
Paul Turner6d5ab292011-01-21 20:45:01 -08001408 update_cfs_shares(cfs_rq);
Peter Zijlstra2069dd72010-11-15 15:47:00 -08001409 }
1410
Paul Turner953bfcd2011-07-21 09:43:27 -07001411 inc_nr_running(rq);
Peter Zijlstraa4c2f002008-10-17 19:27:03 +02001412 hrtick_update(rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001413}
1414
Venkatesh Pallipadi2f368252011-04-14 10:30:53 -07001415static void set_next_buddy(struct sched_entity *se);
1416
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001417/*
1418 * The dequeue_task method is called before nr_running is
1419 * decreased. We remove the task from the rbtree and
1420 * update the fair scheduling stats:
1421 */
Peter Zijlstra371fd7e2010-03-24 16:38:48 +01001422static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001423{
1424 struct cfs_rq *cfs_rq;
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001425 struct sched_entity *se = &p->se;
Venkatesh Pallipadi2f368252011-04-14 10:30:53 -07001426 int task_sleep = flags & DEQUEUE_SLEEP;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001427
1428 for_each_sched_entity(se) {
1429 cfs_rq = cfs_rq_of(se);
Peter Zijlstra371fd7e2010-03-24 16:38:48 +01001430 dequeue_entity(cfs_rq, se, flags);
Paul Turner953bfcd2011-07-21 09:43:27 -07001431 cfs_rq->h_nr_running--;
Peter Zijlstra2069dd72010-11-15 15:47:00 -08001432
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001433 /* Don't dequeue parent if it has other entities besides us */
Venkatesh Pallipadi2f368252011-04-14 10:30:53 -07001434 if (cfs_rq->load.weight) {
1435 /*
1436 * Bias pick_next to pick a task from this cfs_rq, as
1437 * p is sleeping when it is within its sched_slice.
1438 */
1439 if (task_sleep && parent_entity(se))
1440 set_next_buddy(parent_entity(se));
Paul Turner9598c822011-07-06 22:30:37 -07001441
1442 /* avoid re-evaluating load for this entity */
1443 se = parent_entity(se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001444 break;
Venkatesh Pallipadi2f368252011-04-14 10:30:53 -07001445 }
Peter Zijlstra371fd7e2010-03-24 16:38:48 +01001446 flags |= DEQUEUE_SLEEP;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001447 }
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001448
Peter Zijlstra2069dd72010-11-15 15:47:00 -08001449 for_each_sched_entity(se) {
Lin Ming0f317142011-07-22 09:14:31 +08001450 cfs_rq = cfs_rq_of(se);
Paul Turner953bfcd2011-07-21 09:43:27 -07001451 cfs_rq->h_nr_running--;
Peter Zijlstra2069dd72010-11-15 15:47:00 -08001452
Paul Turnerd6b55912010-11-15 15:47:09 -08001453 update_cfs_load(cfs_rq, 0);
Paul Turner6d5ab292011-01-21 20:45:01 -08001454 update_cfs_shares(cfs_rq);
Peter Zijlstra2069dd72010-11-15 15:47:00 -08001455 }
1456
Paul Turner953bfcd2011-07-21 09:43:27 -07001457 dec_nr_running(rq);
Peter Zijlstraa4c2f002008-10-17 19:27:03 +02001458 hrtick_update(rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001459}
1460
Gregory Haskinse7693a32008-01-25 21:08:09 +01001461#ifdef CONFIG_SMP
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001462
Peter Zijlstra74f8e4b2011-04-05 17:23:47 +02001463static void task_waking_fair(struct task_struct *p)
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01001464{
1465 struct sched_entity *se = &p->se;
1466 struct cfs_rq *cfs_rq = cfs_rq_of(se);
Peter Zijlstra3fe16982011-04-05 17:23:48 +02001467 u64 min_vruntime;
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01001468
Peter Zijlstra3fe16982011-04-05 17:23:48 +02001469#ifndef CONFIG_64BIT
1470 u64 min_vruntime_copy;
Peter Zijlstra74f8e4b2011-04-05 17:23:47 +02001471
Peter Zijlstra3fe16982011-04-05 17:23:48 +02001472 do {
1473 min_vruntime_copy = cfs_rq->min_vruntime_copy;
1474 smp_rmb();
1475 min_vruntime = cfs_rq->min_vruntime;
1476 } while (min_vruntime != min_vruntime_copy);
1477#else
1478 min_vruntime = cfs_rq->min_vruntime;
1479#endif
1480
1481 se->vruntime -= min_vruntime;
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01001482}
1483
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001484#ifdef CONFIG_FAIR_GROUP_SCHED
Peter Zijlstraf5bfb7d2008-06-27 13:41:39 +02001485/*
1486 * effective_load() calculates the load change as seen from the root_task_group
1487 *
1488 * Adding load to a group doesn't make a group heavier, but can cause movement
1489 * of group shares between cpus. Assuming the shares were perfectly aligned one
1490 * can calculate the shift in shares.
Peter Zijlstraf5bfb7d2008-06-27 13:41:39 +02001491 */
Peter Zijlstra2069dd72010-11-15 15:47:00 -08001492static long effective_load(struct task_group *tg, int cpu, long wl, long wg)
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001493{
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001494 struct sched_entity *se = tg->se[cpu];
Peter Zijlstraf1d239f2008-06-27 13:41:38 +02001495
1496 if (!tg->parent)
1497 return wl;
1498
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001499 for_each_sched_entity(se) {
Paul Turner977dda72011-01-14 17:57:50 -08001500 long lw, w;
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001501
Paul Turner977dda72011-01-14 17:57:50 -08001502 tg = se->my_q->tg;
1503 w = se->my_q->load.weight;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001504
Paul Turner977dda72011-01-14 17:57:50 -08001505 /* use this cpu's instantaneous contribution */
1506 lw = atomic_read(&tg->load_weight);
1507 lw -= se->my_q->load_contribution;
1508 lw += w + wg;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001509
Paul Turner977dda72011-01-14 17:57:50 -08001510 wl += w;
Peter Zijlstra940959e2008-09-23 15:33:42 +02001511
Paul Turner977dda72011-01-14 17:57:50 -08001512 if (lw > 0 && wl < lw)
1513 wl = (wl * tg->shares) / lw;
1514 else
1515 wl = tg->shares;
Peter Zijlstra940959e2008-09-23 15:33:42 +02001516
Paul Turner977dda72011-01-14 17:57:50 -08001517 /* zero point is MIN_SHARES */
1518 if (wl < MIN_SHARES)
1519 wl = MIN_SHARES;
1520 wl -= se->load.weight;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001521 wg = 0;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001522 }
1523
1524 return wl;
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001525}
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001526
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001527#else
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001528
Peter Zijlstra83378262008-06-27 13:41:37 +02001529static inline unsigned long effective_load(struct task_group *tg, int cpu,
1530 unsigned long wl, unsigned long wg)
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001531{
Peter Zijlstra83378262008-06-27 13:41:37 +02001532 return wl;
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001533}
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001534
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001535#endif
1536
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001537static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001538{
Paul Turnere37b6a72011-01-21 20:44:59 -08001539 s64 this_load, load;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001540 int idx, this_cpu, prev_cpu;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001541 unsigned long tl_per_task;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001542 struct task_group *tg;
Peter Zijlstra83378262008-06-27 13:41:37 +02001543 unsigned long weight;
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001544 int balanced;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001545
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001546 idx = sd->wake_idx;
1547 this_cpu = smp_processor_id();
1548 prev_cpu = task_cpu(p);
1549 load = source_load(prev_cpu, idx);
1550 this_load = target_load(this_cpu, idx);
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001551
1552 /*
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001553 * If sync wakeup then subtract the (maximum possible)
1554 * effect of the currently running task from the load
1555 * of the current CPU:
1556 */
Peter Zijlstra83378262008-06-27 13:41:37 +02001557 if (sync) {
1558 tg = task_group(current);
1559 weight = current->se.load.weight;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001560
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001561 this_load += effective_load(tg, this_cpu, -weight, -weight);
Peter Zijlstra83378262008-06-27 13:41:37 +02001562 load += effective_load(tg, prev_cpu, 0, -weight);
1563 }
1564
1565 tg = task_group(p);
1566 weight = p->se.load.weight;
1567
Peter Zijlstra71a29aa2009-09-07 18:28:05 +02001568 /*
1569 * In low-load situations, where prev_cpu is idle and this_cpu is idle
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001570 * due to the sync cause above having dropped this_load to 0, we'll
1571 * always have an imbalance, but there's really nothing you can do
1572 * about that, so that's good too.
Peter Zijlstra71a29aa2009-09-07 18:28:05 +02001573 *
1574 * Otherwise check if either cpus are near enough in load to allow this
1575 * task to be woken on this_cpu.
1576 */
Paul Turnere37b6a72011-01-21 20:44:59 -08001577 if (this_load > 0) {
1578 s64 this_eff_load, prev_eff_load;
Peter Zijlstrae51fd5e2010-05-31 12:37:30 +02001579
1580 this_eff_load = 100;
1581 this_eff_load *= power_of(prev_cpu);
1582 this_eff_load *= this_load +
1583 effective_load(tg, this_cpu, weight, weight);
1584
1585 prev_eff_load = 100 + (sd->imbalance_pct - 100) / 2;
1586 prev_eff_load *= power_of(this_cpu);
1587 prev_eff_load *= load + effective_load(tg, prev_cpu, 0, weight);
1588
1589 balanced = this_eff_load <= prev_eff_load;
1590 } else
1591 balanced = true;
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001592
1593 /*
1594 * If the currently running task will sleep within
1595 * a reasonable amount of time then attract this newly
1596 * woken task:
1597 */
Peter Zijlstra2fb76352008-10-08 09:16:04 +02001598 if (sync && balanced)
1599 return 1;
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001600
Lucas De Marchi41acab82010-03-10 23:37:45 -03001601 schedstat_inc(p, se.statistics.nr_wakeups_affine_attempts);
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001602 tl_per_task = cpu_avg_load_per_task(this_cpu);
1603
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001604 if (balanced ||
1605 (this_load <= load &&
1606 this_load + target_load(prev_cpu, idx) <= tl_per_task)) {
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001607 /*
1608 * This domain has SD_WAKE_AFFINE and
1609 * p is cache cold in this domain, and
1610 * there is no bad imbalance.
1611 */
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001612 schedstat_inc(sd, ttwu_move_affine);
Lucas De Marchi41acab82010-03-10 23:37:45 -03001613 schedstat_inc(p, se.statistics.nr_wakeups_affine);
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001614
1615 return 1;
1616 }
1617 return 0;
1618}
1619
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001620/*
1621 * find_idlest_group finds and returns the least busy CPU group within the
1622 * domain.
1623 */
1624static struct sched_group *
Peter Zijlstra78e7ed52009-09-03 13:16:51 +02001625find_idlest_group(struct sched_domain *sd, struct task_struct *p,
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001626 int this_cpu, int load_idx)
Gregory Haskinse7693a32008-01-25 21:08:09 +01001627{
Andi Kleenb3bd3de2010-08-10 14:17:51 -07001628 struct sched_group *idlest = NULL, *group = sd->groups;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001629 unsigned long min_load = ULONG_MAX, this_load = 0;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001630 int imbalance = 100 + (sd->imbalance_pct-100)/2;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001631
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001632 do {
1633 unsigned long load, avg_load;
1634 int local_group;
1635 int i;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001636
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001637 /* Skip over this group if it has no CPUs allowed */
1638 if (!cpumask_intersects(sched_group_cpus(group),
1639 &p->cpus_allowed))
1640 continue;
1641
1642 local_group = cpumask_test_cpu(this_cpu,
1643 sched_group_cpus(group));
1644
1645 /* Tally up the load of all CPUs in the group */
1646 avg_load = 0;
1647
1648 for_each_cpu(i, sched_group_cpus(group)) {
1649 /* Bias balancing toward cpus of our domain */
1650 if (local_group)
1651 load = source_load(i, load_idx);
1652 else
1653 load = target_load(i, load_idx);
1654
1655 avg_load += load;
1656 }
1657
1658 /* Adjust by relative CPU power of the group */
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02001659 avg_load = (avg_load * SCHED_POWER_SCALE) / group->sgp->power;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001660
1661 if (local_group) {
1662 this_load = avg_load;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001663 } else if (avg_load < min_load) {
1664 min_load = avg_load;
1665 idlest = group;
1666 }
1667 } while (group = group->next, group != sd->groups);
1668
1669 if (!idlest || 100*this_load < imbalance*min_load)
1670 return NULL;
1671 return idlest;
1672}
1673
1674/*
1675 * find_idlest_cpu - find the idlest cpu among the cpus in group.
1676 */
1677static int
1678find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
1679{
1680 unsigned long load, min_load = ULONG_MAX;
1681 int idlest = -1;
1682 int i;
1683
1684 /* Traverse only the allowed CPUs */
1685 for_each_cpu_and(i, sched_group_cpus(group), &p->cpus_allowed) {
1686 load = weighted_cpuload(i);
1687
1688 if (load < min_load || (load == min_load && i == this_cpu)) {
1689 min_load = load;
1690 idlest = i;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001691 }
1692 }
1693
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001694 return idlest;
1695}
Gregory Haskinse7693a32008-01-25 21:08:09 +01001696
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001697/*
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001698 * Try and locate an idle CPU in the sched_domain.
1699 */
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001700static int select_idle_sibling(struct task_struct *p, int target)
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001701{
1702 int cpu = smp_processor_id();
1703 int prev_cpu = task_cpu(p);
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001704 struct sched_domain *sd;
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001705 int i;
1706
1707 /*
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001708 * If the task is going to be woken-up on this cpu and if it is
1709 * already idle, then it is the right target.
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001710 */
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001711 if (target == cpu && idle_cpu(cpu))
1712 return cpu;
1713
1714 /*
1715 * If the task is going to be woken-up on the cpu where it previously
1716 * ran and if it is currently idle, then it the right target.
1717 */
1718 if (target == prev_cpu && idle_cpu(prev_cpu))
Peter Zijlstrafe3bcfe2009-11-12 15:55:29 +01001719 return prev_cpu;
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001720
1721 /*
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001722 * Otherwise, iterate the domains and find an elegible idle cpu.
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001723 */
Peter Zijlstradce840a2011-04-07 14:09:50 +02001724 rcu_read_lock();
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001725 for_each_domain(target, sd) {
1726 if (!(sd->flags & SD_SHARE_PKG_RESOURCES))
Peter Zijlstrafe3bcfe2009-11-12 15:55:29 +01001727 break;
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001728
1729 for_each_cpu_and(i, sched_domain_span(sd), &p->cpus_allowed) {
1730 if (idle_cpu(i)) {
1731 target = i;
1732 break;
1733 }
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001734 }
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001735
1736 /*
1737 * Lets stop looking for an idle sibling when we reached
1738 * the domain that spans the current cpu and prev_cpu.
1739 */
1740 if (cpumask_test_cpu(cpu, sched_domain_span(sd)) &&
1741 cpumask_test_cpu(prev_cpu, sched_domain_span(sd)))
1742 break;
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001743 }
Peter Zijlstradce840a2011-04-07 14:09:50 +02001744 rcu_read_unlock();
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001745
1746 return target;
1747}
1748
1749/*
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001750 * sched_balance_self: balance the current task (running on cpu) in domains
1751 * that have the 'flag' flag set. In practice, this is SD_BALANCE_FORK and
1752 * SD_BALANCE_EXEC.
1753 *
1754 * Balance, ie. select the least loaded group.
1755 *
1756 * Returns the target CPU number, or the same CPU if no balancing is needed.
1757 *
1758 * preempt must be disabled.
1759 */
Peter Zijlstra0017d732010-03-24 18:34:10 +01001760static int
Peter Zijlstra7608dec2011-04-05 17:23:46 +02001761select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001762{
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001763 struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001764 int cpu = smp_processor_id();
1765 int prev_cpu = task_cpu(p);
1766 int new_cpu = cpu;
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001767 int want_affine = 0;
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001768 int want_sd = 1;
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001769 int sync = wake_flags & WF_SYNC;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001770
Peter Zijlstra0763a662009-09-14 19:37:39 +02001771 if (sd_flag & SD_BALANCE_WAKE) {
Mike Galbraithbeac4c72010-03-11 17:17:20 +01001772 if (cpumask_test_cpu(cpu, &p->cpus_allowed))
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001773 want_affine = 1;
1774 new_cpu = prev_cpu;
1775 }
Gregory Haskinse7693a32008-01-25 21:08:09 +01001776
Peter Zijlstradce840a2011-04-07 14:09:50 +02001777 rcu_read_lock();
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001778 for_each_domain(cpu, tmp) {
Peter Zijlstrae4f428882009-12-16 18:04:34 +01001779 if (!(tmp->flags & SD_LOAD_BALANCE))
1780 continue;
1781
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001782 /*
Peter Zijlstraae154be2009-09-10 14:40:57 +02001783 * If power savings logic is enabled for a domain, see if we
1784 * are not overloaded, if so, don't balance wider.
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001785 */
Peter Zijlstra59abf022009-09-16 08:28:30 +02001786 if (tmp->flags & (SD_POWERSAVINGS_BALANCE|SD_PREFER_LOCAL)) {
Peter Zijlstraae154be2009-09-10 14:40:57 +02001787 unsigned long power = 0;
1788 unsigned long nr_running = 0;
1789 unsigned long capacity;
1790 int i;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001791
Peter Zijlstraae154be2009-09-10 14:40:57 +02001792 for_each_cpu(i, sched_domain_span(tmp)) {
1793 power += power_of(i);
1794 nr_running += cpu_rq(i)->cfs.nr_running;
1795 }
Gregory Haskinse7693a32008-01-25 21:08:09 +01001796
Nikhil Rao1399fa72011-05-18 10:09:39 -07001797 capacity = DIV_ROUND_CLOSEST(power, SCHED_POWER_SCALE);
Ingo Molnar4ae7d5c2008-03-19 01:42:00 +01001798
Peter Zijlstra59abf022009-09-16 08:28:30 +02001799 if (tmp->flags & SD_POWERSAVINGS_BALANCE)
1800 nr_running /= 2;
1801
1802 if (nr_running < capacity)
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001803 want_sd = 0;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001804 }
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001805
Peter Zijlstrafe3bcfe2009-11-12 15:55:29 +01001806 /*
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001807 * If both cpu and prev_cpu are part of this domain,
1808 * cpu is a valid SD_WAKE_AFFINE target.
Peter Zijlstrafe3bcfe2009-11-12 15:55:29 +01001809 */
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001810 if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
1811 cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) {
1812 affine_sd = tmp;
1813 want_affine = 0;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001814 }
1815
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001816 if (!want_sd && !want_affine)
1817 break;
1818
Peter Zijlstra0763a662009-09-14 19:37:39 +02001819 if (!(tmp->flags & sd_flag))
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001820 continue;
1821
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001822 if (want_sd)
1823 sd = tmp;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001824 }
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001825
Mike Galbraith8b911ac2010-03-11 17:17:16 +01001826 if (affine_sd) {
Suresh Siddha99bd5e22010-03-31 16:47:45 -07001827 if (cpu == prev_cpu || wake_affine(affine_sd, p, sync))
Peter Zijlstradce840a2011-04-07 14:09:50 +02001828 prev_cpu = cpu;
1829
1830 new_cpu = select_idle_sibling(p, prev_cpu);
1831 goto unlock;
Mike Galbraith8b911ac2010-03-11 17:17:16 +01001832 }
Peter Zijlstra3b640892009-09-16 13:44:33 +02001833
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001834 while (sd) {
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001835 int load_idx = sd->forkexec_idx;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001836 struct sched_group *group;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001837 int weight;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001838
Peter Zijlstra0763a662009-09-14 19:37:39 +02001839 if (!(sd->flags & sd_flag)) {
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001840 sd = sd->child;
1841 continue;
1842 }
1843
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001844 if (sd_flag & SD_BALANCE_WAKE)
1845 load_idx = sd->wake_idx;
1846
1847 group = find_idlest_group(sd, p, cpu, load_idx);
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001848 if (!group) {
1849 sd = sd->child;
1850 continue;
1851 }
1852
Peter Zijlstrad7c33c42009-09-11 12:45:38 +02001853 new_cpu = find_idlest_cpu(group, p, cpu);
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001854 if (new_cpu == -1 || new_cpu == cpu) {
1855 /* Now try balancing at a lower domain level of cpu */
1856 sd = sd->child;
1857 continue;
1858 }
1859
1860 /* Now try balancing at a lower domain level of new_cpu */
1861 cpu = new_cpu;
Peter Zijlstra669c55e2010-04-16 14:59:29 +02001862 weight = sd->span_weight;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001863 sd = NULL;
1864 for_each_domain(cpu, tmp) {
Peter Zijlstra669c55e2010-04-16 14:59:29 +02001865 if (weight <= tmp->span_weight)
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001866 break;
Peter Zijlstra0763a662009-09-14 19:37:39 +02001867 if (tmp->flags & sd_flag)
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001868 sd = tmp;
1869 }
1870 /* while loop will break here if sd == NULL */
Gregory Haskinse7693a32008-01-25 21:08:09 +01001871 }
Peter Zijlstradce840a2011-04-07 14:09:50 +02001872unlock:
1873 rcu_read_unlock();
Gregory Haskinse7693a32008-01-25 21:08:09 +01001874
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001875 return new_cpu;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001876}
1877#endif /* CONFIG_SMP */
1878
Peter Zijlstrae52fb7c2009-01-14 12:39:19 +01001879static unsigned long
1880wakeup_gran(struct sched_entity *curr, struct sched_entity *se)
Peter Zijlstra0bbd3332008-04-19 19:44:57 +02001881{
1882 unsigned long gran = sysctl_sched_wakeup_granularity;
1883
1884 /*
Peter Zijlstrae52fb7c2009-01-14 12:39:19 +01001885 * Since its curr running now, convert the gran from real-time
1886 * to virtual-time in his units.
Mike Galbraith13814d42010-03-11 17:17:04 +01001887 *
1888 * By using 'se' instead of 'curr' we penalize light tasks, so
1889 * they get preempted easier. That is, if 'se' < 'curr' then
1890 * the resulting gran will be larger, therefore penalizing the
1891 * lighter, if otoh 'se' > 'curr' then the resulting gran will
1892 * be smaller, again penalizing the lighter task.
1893 *
1894 * This is especially important for buddies when the leftmost
1895 * task is higher priority than the buddy.
Peter Zijlstra0bbd3332008-04-19 19:44:57 +02001896 */
Shaohua Lif4ad9bd2011-04-08 12:53:09 +08001897 return calc_delta_fair(gran, se);
Peter Zijlstra0bbd3332008-04-19 19:44:57 +02001898}
1899
1900/*
Peter Zijlstra464b7522008-10-24 11:06:15 +02001901 * Should 'se' preempt 'curr'.
1902 *
1903 * |s1
1904 * |s2
1905 * |s3
1906 * g
1907 * |<--->|c
1908 *
1909 * w(c, s1) = -1
1910 * w(c, s2) = 0
1911 * w(c, s3) = 1
1912 *
1913 */
1914static int
1915wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
1916{
1917 s64 gran, vdiff = curr->vruntime - se->vruntime;
1918
1919 if (vdiff <= 0)
1920 return -1;
1921
Peter Zijlstrae52fb7c2009-01-14 12:39:19 +01001922 gran = wakeup_gran(curr, se);
Peter Zijlstra464b7522008-10-24 11:06:15 +02001923 if (vdiff > gran)
1924 return 1;
1925
1926 return 0;
1927}
1928
Peter Zijlstra02479092008-11-04 21:25:10 +01001929static void set_last_buddy(struct sched_entity *se)
1930{
Venkatesh Pallipadi69c80f32011-04-13 18:21:09 -07001931 if (entity_is_task(se) && unlikely(task_of(se)->policy == SCHED_IDLE))
1932 return;
1933
1934 for_each_sched_entity(se)
1935 cfs_rq_of(se)->last = se;
Peter Zijlstra02479092008-11-04 21:25:10 +01001936}
1937
1938static void set_next_buddy(struct sched_entity *se)
1939{
Venkatesh Pallipadi69c80f32011-04-13 18:21:09 -07001940 if (entity_is_task(se) && unlikely(task_of(se)->policy == SCHED_IDLE))
1941 return;
1942
1943 for_each_sched_entity(se)
1944 cfs_rq_of(se)->next = se;
Peter Zijlstra02479092008-11-04 21:25:10 +01001945}
1946
Rik van Rielac53db52011-02-01 09:51:03 -05001947static void set_skip_buddy(struct sched_entity *se)
1948{
Venkatesh Pallipadi69c80f32011-04-13 18:21:09 -07001949 for_each_sched_entity(se)
1950 cfs_rq_of(se)->skip = se;
Rik van Rielac53db52011-02-01 09:51:03 -05001951}
1952
Peter Zijlstra464b7522008-10-24 11:06:15 +02001953/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001954 * Preempt the current task with a newly woken task if needed:
1955 */
Peter Zijlstra5a9b86f2009-09-16 13:47:58 +02001956static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001957{
1958 struct task_struct *curr = rq->curr;
Srivatsa Vaddagiri8651a862007-10-15 17:00:12 +02001959 struct sched_entity *se = &curr->se, *pse = &p->se;
Mike Galbraith03e89e42008-12-16 08:45:30 +01001960 struct cfs_rq *cfs_rq = task_cfs_rq(curr);
Mike Galbraithf685cea2009-10-23 23:09:22 +02001961 int scale = cfs_rq->nr_running >= sched_nr_latency;
Venkatesh Pallipadi2f368252011-04-14 10:30:53 -07001962 int next_buddy_marked = 0;
Mike Galbraith03e89e42008-12-16 08:45:30 +01001963
Ingo Molnar4ae7d5c2008-03-19 01:42:00 +01001964 if (unlikely(se == pse))
1965 return;
1966
Venkatesh Pallipadi2f368252011-04-14 10:30:53 -07001967 if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK)) {
Mike Galbraith3cb63d52009-09-11 12:01:17 +02001968 set_next_buddy(pse);
Venkatesh Pallipadi2f368252011-04-14 10:30:53 -07001969 next_buddy_marked = 1;
1970 }
Peter Zijlstra57fdc262008-09-23 15:33:45 +02001971
Bharata B Raoaec0a512008-08-28 14:42:49 +05301972 /*
1973 * We can come here with TIF_NEED_RESCHED already set from new task
1974 * wake up path.
1975 */
1976 if (test_tsk_need_resched(curr))
1977 return;
1978
Darren Harta2f5c9a2011-02-22 13:04:33 -08001979 /* Idle tasks are by definition preempted by non-idle tasks. */
1980 if (unlikely(curr->policy == SCHED_IDLE) &&
1981 likely(p->policy != SCHED_IDLE))
1982 goto preempt;
1983
Ingo Molnar91c234b2007-10-15 17:00:18 +02001984 /*
Darren Harta2f5c9a2011-02-22 13:04:33 -08001985 * Batch and idle tasks do not preempt non-idle tasks (their preemption
1986 * is driven by the tick):
Ingo Molnar91c234b2007-10-15 17:00:18 +02001987 */
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001988 if (unlikely(p->policy != SCHED_NORMAL))
Ingo Molnar91c234b2007-10-15 17:00:18 +02001989 return;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001990
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01001991 find_matching_se(&se, &pse);
Paul Turner9bbd7372011-07-05 19:07:21 -07001992 update_curr(cfs_rq_of(se));
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01001993 BUG_ON(!pse);
Venkatesh Pallipadi2f368252011-04-14 10:30:53 -07001994 if (wakeup_preempt_entity(se, pse) == 1) {
1995 /*
1996 * Bias pick_next to pick the sched entity that is
1997 * triggering this preemption.
1998 */
1999 if (!next_buddy_marked)
2000 set_next_buddy(pse);
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01002001 goto preempt;
Venkatesh Pallipadi2f368252011-04-14 10:30:53 -07002002 }
Jupyung Leea65ac742009-11-17 18:51:40 +09002003
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01002004 return;
2005
2006preempt:
2007 resched_task(curr);
2008 /*
2009 * Only set the backward buddy when the current task is still
2010 * on the rq. This can happen when a wakeup gets interleaved
2011 * with schedule on the ->pre_schedule() or idle_balance()
2012 * point, either of which can * drop the rq lock.
2013 *
2014 * Also, during early boot the idle thread is in the fair class,
2015 * for obvious reasons its a bad idea to schedule back to it.
2016 */
2017 if (unlikely(!se->on_rq || curr == rq->idle))
2018 return;
2019
2020 if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))
2021 set_last_buddy(se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002022}
2023
Ingo Molnarfb8d4722007-08-09 11:16:48 +02002024static struct task_struct *pick_next_task_fair(struct rq *rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002025{
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01002026 struct task_struct *p;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002027 struct cfs_rq *cfs_rq = &rq->cfs;
2028 struct sched_entity *se;
2029
Tim Blechmann36ace272009-11-24 11:55:45 +01002030 if (!cfs_rq->nr_running)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002031 return NULL;
2032
2033 do {
Ingo Molnar9948f4b2007-08-09 11:16:48 +02002034 se = pick_next_entity(cfs_rq);
Peter Zijlstraf4b67552008-11-04 21:25:07 +01002035 set_next_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002036 cfs_rq = group_cfs_rq(se);
2037 } while (cfs_rq);
2038
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01002039 p = task_of(se);
2040 hrtick_start_fair(rq, p);
2041
2042 return p;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002043}
2044
2045/*
2046 * Account for a descheduled task:
2047 */
Ingo Molnar31ee5292007-08-09 11:16:49 +02002048static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002049{
2050 struct sched_entity *se = &prev->se;
2051 struct cfs_rq *cfs_rq;
2052
2053 for_each_sched_entity(se) {
2054 cfs_rq = cfs_rq_of(se);
Ingo Molnarab6cde22007-08-09 11:16:48 +02002055 put_prev_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002056 }
2057}
2058
Rik van Rielac53db52011-02-01 09:51:03 -05002059/*
2060 * sched_yield() is very simple
2061 *
2062 * The magic of dealing with the ->skip buddy is in pick_next_entity.
2063 */
2064static void yield_task_fair(struct rq *rq)
2065{
2066 struct task_struct *curr = rq->curr;
2067 struct cfs_rq *cfs_rq = task_cfs_rq(curr);
2068 struct sched_entity *se = &curr->se;
2069
2070 /*
2071 * Are we the only task in the tree?
2072 */
2073 if (unlikely(rq->nr_running == 1))
2074 return;
2075
2076 clear_buddies(cfs_rq, se);
2077
2078 if (curr->policy != SCHED_BATCH) {
2079 update_rq_clock(rq);
2080 /*
2081 * Update run-time statistics of the 'current'.
2082 */
2083 update_curr(cfs_rq);
2084 }
2085
2086 set_skip_buddy(se);
2087}
2088
Mike Galbraithd95f4122011-02-01 09:50:51 -05002089static bool yield_to_task_fair(struct rq *rq, struct task_struct *p, bool preempt)
2090{
2091 struct sched_entity *se = &p->se;
2092
2093 if (!se->on_rq)
2094 return false;
2095
2096 /* Tell the scheduler that we'd really like pse to run next. */
2097 set_next_buddy(se);
2098
Mike Galbraithd95f4122011-02-01 09:50:51 -05002099 yield_task_fair(rq);
2100
2101 return true;
2102}
2103
Peter Williams681f3e62007-10-24 18:23:51 +02002104#ifdef CONFIG_SMP
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002105/**************************************************
2106 * Fair scheduling class load-balancing methods:
2107 */
2108
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002109/*
2110 * pull_task - move a task from a remote runqueue to the local runqueue.
2111 * Both runqueues must be locked.
2112 */
2113static void pull_task(struct rq *src_rq, struct task_struct *p,
2114 struct rq *this_rq, int this_cpu)
2115{
2116 deactivate_task(src_rq, p, 0);
2117 set_task_cpu(p, this_cpu);
2118 activate_task(this_rq, p, 0);
2119 check_preempt_curr(this_rq, p, 0);
2120}
2121
2122/*
2123 * can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
2124 */
2125static
2126int can_migrate_task(struct task_struct *p, struct rq *rq, int this_cpu,
2127 struct sched_domain *sd, enum cpu_idle_type idle,
2128 int *all_pinned)
2129{
2130 int tsk_cache_hot = 0;
2131 /*
2132 * We do not migrate tasks that are:
2133 * 1) running (obviously), or
2134 * 2) cannot be migrated to this CPU due to cpus_allowed, or
2135 * 3) are cache-hot on their current CPU.
2136 */
2137 if (!cpumask_test_cpu(this_cpu, &p->cpus_allowed)) {
Lucas De Marchi41acab82010-03-10 23:37:45 -03002138 schedstat_inc(p, se.statistics.nr_failed_migrations_affine);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002139 return 0;
2140 }
2141 *all_pinned = 0;
2142
2143 if (task_running(rq, p)) {
Lucas De Marchi41acab82010-03-10 23:37:45 -03002144 schedstat_inc(p, se.statistics.nr_failed_migrations_running);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002145 return 0;
2146 }
2147
2148 /*
2149 * Aggressive migration if:
2150 * 1) task is cache cold, or
2151 * 2) too many balance attempts have failed.
2152 */
2153
Venkatesh Pallipadi305e6832010-10-04 17:03:21 -07002154 tsk_cache_hot = task_hot(p, rq->clock_task, sd);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002155 if (!tsk_cache_hot ||
2156 sd->nr_balance_failed > sd->cache_nice_tries) {
2157#ifdef CONFIG_SCHEDSTATS
2158 if (tsk_cache_hot) {
2159 schedstat_inc(sd, lb_hot_gained[idle]);
Lucas De Marchi41acab82010-03-10 23:37:45 -03002160 schedstat_inc(p, se.statistics.nr_forced_migrations);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002161 }
2162#endif
2163 return 1;
2164 }
2165
2166 if (tsk_cache_hot) {
Lucas De Marchi41acab82010-03-10 23:37:45 -03002167 schedstat_inc(p, se.statistics.nr_failed_migrations_hot);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002168 return 0;
2169 }
2170 return 1;
2171}
2172
Peter Zijlstra897c3952009-12-17 17:45:42 +01002173/*
2174 * move_one_task tries to move exactly one task from busiest to this_rq, as
2175 * part of active balancing operations within "domain".
2176 * Returns 1 if successful and 0 otherwise.
2177 *
2178 * Called with both runqueues locked.
2179 */
2180static int
2181move_one_task(struct rq *this_rq, int this_cpu, struct rq *busiest,
2182 struct sched_domain *sd, enum cpu_idle_type idle)
2183{
2184 struct task_struct *p, *n;
2185 struct cfs_rq *cfs_rq;
2186 int pinned = 0;
2187
2188 for_each_leaf_cfs_rq(busiest, cfs_rq) {
2189 list_for_each_entry_safe(p, n, &cfs_rq->tasks, se.group_node) {
2190
2191 if (!can_migrate_task(p, busiest, this_cpu,
2192 sd, idle, &pinned))
2193 continue;
2194
2195 pull_task(busiest, p, this_rq, this_cpu);
2196 /*
2197 * Right now, this is only the second place pull_task()
2198 * is called, so we can safely collect pull_task()
2199 * stats here rather than inside pull_task().
2200 */
2201 schedstat_inc(sd, lb_gained[idle]);
2202 return 1;
2203 }
2204 }
2205
2206 return 0;
2207}
2208
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002209static unsigned long
2210balance_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
2211 unsigned long max_load_move, struct sched_domain *sd,
2212 enum cpu_idle_type idle, int *all_pinned,
Vladimir Davydov931aeed2011-05-03 22:31:07 +04002213 struct cfs_rq *busiest_cfs_rq)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002214{
Ken Chenb30aef12011-04-08 12:20:16 -07002215 int loops = 0, pulled = 0;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002216 long rem_load_move = max_load_move;
Peter Zijlstraee00e662009-12-17 17:25:20 +01002217 struct task_struct *p, *n;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002218
2219 if (max_load_move == 0)
2220 goto out;
2221
Peter Zijlstraee00e662009-12-17 17:25:20 +01002222 list_for_each_entry_safe(p, n, &busiest_cfs_rq->tasks, se.group_node) {
2223 if (loops++ > sysctl_sched_nr_migrate)
2224 break;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002225
Peter Zijlstraee00e662009-12-17 17:25:20 +01002226 if ((p->se.load.weight >> 1) > rem_load_move ||
Ken Chenb30aef12011-04-08 12:20:16 -07002227 !can_migrate_task(p, busiest, this_cpu, sd, idle,
2228 all_pinned))
Peter Zijlstraee00e662009-12-17 17:25:20 +01002229 continue;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002230
Peter Zijlstraee00e662009-12-17 17:25:20 +01002231 pull_task(busiest, p, this_rq, this_cpu);
2232 pulled++;
2233 rem_load_move -= p->se.load.weight;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002234
2235#ifdef CONFIG_PREEMPT
Peter Zijlstraee00e662009-12-17 17:25:20 +01002236 /*
2237 * NEWIDLE balancing is a source of latency, so preemptible
2238 * kernels will stop after the first task is pulled to minimize
2239 * the critical section.
2240 */
2241 if (idle == CPU_NEWLY_IDLE)
2242 break;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002243#endif
2244
Peter Zijlstraee00e662009-12-17 17:25:20 +01002245 /*
2246 * We only want to steal up to the prescribed amount of
2247 * weighted load.
2248 */
2249 if (rem_load_move <= 0)
2250 break;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002251 }
2252out:
2253 /*
2254 * Right now, this is one of only two places pull_task() is called,
2255 * so we can safely collect pull_task() stats here rather than
2256 * inside pull_task().
2257 */
2258 schedstat_add(sd, lb_gained[idle], pulled);
2259
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002260 return max_load_move - rem_load_move;
2261}
2262
Peter Zijlstra230059de2009-12-17 17:47:12 +01002263#ifdef CONFIG_FAIR_GROUP_SCHED
Peter Zijlstra9e3081c2010-11-15 15:47:02 -08002264/*
2265 * update tg->load_weight by folding this cpu's load_avg
2266 */
Paul Turner67e86252010-11-15 15:47:05 -08002267static int update_shares_cpu(struct task_group *tg, int cpu)
Peter Zijlstra9e3081c2010-11-15 15:47:02 -08002268{
2269 struct cfs_rq *cfs_rq;
2270 unsigned long flags;
2271 struct rq *rq;
Peter Zijlstra9e3081c2010-11-15 15:47:02 -08002272
2273 if (!tg->se[cpu])
2274 return 0;
2275
2276 rq = cpu_rq(cpu);
2277 cfs_rq = tg->cfs_rq[cpu];
2278
2279 raw_spin_lock_irqsave(&rq->lock, flags);
2280
2281 update_rq_clock(rq);
Paul Turnerd6b55912010-11-15 15:47:09 -08002282 update_cfs_load(cfs_rq, 1);
Peter Zijlstra9e3081c2010-11-15 15:47:02 -08002283
2284 /*
2285 * We need to update shares after updating tg->load_weight in
2286 * order to adjust the weight of groups with long running tasks.
2287 */
Paul Turner6d5ab292011-01-21 20:45:01 -08002288 update_cfs_shares(cfs_rq);
Peter Zijlstra9e3081c2010-11-15 15:47:02 -08002289
2290 raw_spin_unlock_irqrestore(&rq->lock, flags);
2291
2292 return 0;
2293}
2294
2295static void update_shares(int cpu)
2296{
2297 struct cfs_rq *cfs_rq;
2298 struct rq *rq = cpu_rq(cpu);
2299
2300 rcu_read_lock();
Peter Zijlstra9763b672011-07-13 13:09:25 +02002301 /*
2302 * Iterates the task_group tree in a bottom up fashion, see
2303 * list_add_leaf_cfs_rq() for details.
2304 */
Paul Turner67e86252010-11-15 15:47:05 -08002305 for_each_leaf_cfs_rq(rq, cfs_rq)
2306 update_shares_cpu(cfs_rq->tg, cpu);
Peter Zijlstra9e3081c2010-11-15 15:47:02 -08002307 rcu_read_unlock();
2308}
2309
Peter Zijlstra9763b672011-07-13 13:09:25 +02002310/*
2311 * Compute the cpu's hierarchical load factor for each task group.
2312 * This needs to be done in a top-down fashion because the load of a child
2313 * group is a fraction of its parents load.
2314 */
2315static int tg_load_down(struct task_group *tg, void *data)
2316{
2317 unsigned long load;
2318 long cpu = (long)data;
2319
2320 if (!tg->parent) {
2321 load = cpu_rq(cpu)->load.weight;
2322 } else {
2323 load = tg->parent->cfs_rq[cpu]->h_load;
2324 load *= tg->se[cpu]->load.weight;
2325 load /= tg->parent->cfs_rq[cpu]->load.weight + 1;
2326 }
2327
2328 tg->cfs_rq[cpu]->h_load = load;
2329
2330 return 0;
2331}
2332
2333static void update_h_load(long cpu)
2334{
2335 walk_tg_tree(tg_load_down, tg_nop, (void *)cpu);
2336}
2337
Peter Zijlstra230059de2009-12-17 17:47:12 +01002338static unsigned long
2339load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
2340 unsigned long max_load_move,
2341 struct sched_domain *sd, enum cpu_idle_type idle,
Vladimir Davydov931aeed2011-05-03 22:31:07 +04002342 int *all_pinned)
Peter Zijlstra230059de2009-12-17 17:47:12 +01002343{
2344 long rem_load_move = max_load_move;
Peter Zijlstra9763b672011-07-13 13:09:25 +02002345 struct cfs_rq *busiest_cfs_rq;
Peter Zijlstra230059de2009-12-17 17:47:12 +01002346
2347 rcu_read_lock();
Peter Zijlstra9763b672011-07-13 13:09:25 +02002348 update_h_load(cpu_of(busiest));
Peter Zijlstra230059de2009-12-17 17:47:12 +01002349
Peter Zijlstra9763b672011-07-13 13:09:25 +02002350 for_each_leaf_cfs_rq(busiest, busiest_cfs_rq) {
Peter Zijlstra230059de2009-12-17 17:47:12 +01002351 unsigned long busiest_h_load = busiest_cfs_rq->h_load;
2352 unsigned long busiest_weight = busiest_cfs_rq->load.weight;
2353 u64 rem_load, moved_load;
2354
2355 /*
2356 * empty group
2357 */
2358 if (!busiest_cfs_rq->task_weight)
2359 continue;
2360
2361 rem_load = (u64)rem_load_move * busiest_weight;
2362 rem_load = div_u64(rem_load, busiest_h_load + 1);
2363
2364 moved_load = balance_tasks(this_rq, this_cpu, busiest,
Vladimir Davydov931aeed2011-05-03 22:31:07 +04002365 rem_load, sd, idle, all_pinned,
Peter Zijlstra230059de2009-12-17 17:47:12 +01002366 busiest_cfs_rq);
2367
2368 if (!moved_load)
2369 continue;
2370
2371 moved_load *= busiest_h_load;
2372 moved_load = div_u64(moved_load, busiest_weight + 1);
2373
2374 rem_load_move -= moved_load;
2375 if (rem_load_move < 0)
2376 break;
2377 }
2378 rcu_read_unlock();
2379
2380 return max_load_move - rem_load_move;
2381}
2382#else
Peter Zijlstra9e3081c2010-11-15 15:47:02 -08002383static inline void update_shares(int cpu)
2384{
2385}
2386
Peter Zijlstra230059de2009-12-17 17:47:12 +01002387static unsigned long
2388load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
2389 unsigned long max_load_move,
2390 struct sched_domain *sd, enum cpu_idle_type idle,
Vladimir Davydov931aeed2011-05-03 22:31:07 +04002391 int *all_pinned)
Peter Zijlstra230059de2009-12-17 17:47:12 +01002392{
2393 return balance_tasks(this_rq, this_cpu, busiest,
2394 max_load_move, sd, idle, all_pinned,
Vladimir Davydov931aeed2011-05-03 22:31:07 +04002395 &busiest->cfs);
Peter Zijlstra230059de2009-12-17 17:47:12 +01002396}
2397#endif
2398
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002399/*
2400 * move_tasks tries to move up to max_load_move weighted load from busiest to
2401 * this_rq, as part of a balancing operation within domain "sd".
2402 * Returns 1 if successful and 0 otherwise.
2403 *
2404 * Called with both runqueues locked.
2405 */
2406static int move_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
2407 unsigned long max_load_move,
2408 struct sched_domain *sd, enum cpu_idle_type idle,
2409 int *all_pinned)
2410{
Peter Zijlstra3d45fd82009-12-17 17:12:46 +01002411 unsigned long total_load_moved = 0, load_moved;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002412
2413 do {
Peter Zijlstra3d45fd82009-12-17 17:12:46 +01002414 load_moved = load_balance_fair(this_rq, this_cpu, busiest,
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002415 max_load_move - total_load_moved,
Vladimir Davydov931aeed2011-05-03 22:31:07 +04002416 sd, idle, all_pinned);
Peter Zijlstra3d45fd82009-12-17 17:12:46 +01002417
2418 total_load_moved += load_moved;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002419
2420#ifdef CONFIG_PREEMPT
2421 /*
2422 * NEWIDLE balancing is a source of latency, so preemptible
2423 * kernels will stop after the first task is pulled to minimize
2424 * the critical section.
2425 */
2426 if (idle == CPU_NEWLY_IDLE && this_rq->nr_running)
2427 break;
Peter Zijlstrabaa8c112009-12-17 18:10:09 +01002428
2429 if (raw_spin_is_contended(&this_rq->lock) ||
2430 raw_spin_is_contended(&busiest->lock))
2431 break;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002432#endif
Peter Zijlstra3d45fd82009-12-17 17:12:46 +01002433 } while (load_moved && max_load_move > total_load_moved);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002434
2435 return total_load_moved > 0;
2436}
2437
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002438/********** Helpers for find_busiest_group ************************/
2439/*
2440 * sd_lb_stats - Structure to store the statistics of a sched_domain
2441 * during load balancing.
2442 */
2443struct sd_lb_stats {
2444 struct sched_group *busiest; /* Busiest group in this sd */
2445 struct sched_group *this; /* Local group in this sd */
2446 unsigned long total_load; /* Total load of all groups in sd */
2447 unsigned long total_pwr; /* Total power of all groups in sd */
2448 unsigned long avg_load; /* Average load across all groups in sd */
2449
2450 /** Statistics of this group */
2451 unsigned long this_load;
2452 unsigned long this_load_per_task;
2453 unsigned long this_nr_running;
Nikhil Raofab47622010-10-15 13:12:29 -07002454 unsigned long this_has_capacity;
Suresh Siddhaaae6d3d2010-09-17 15:02:32 -07002455 unsigned int this_idle_cpus;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002456
2457 /* Statistics of the busiest group */
Suresh Siddhaaae6d3d2010-09-17 15:02:32 -07002458 unsigned int busiest_idle_cpus;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002459 unsigned long max_load;
2460 unsigned long busiest_load_per_task;
2461 unsigned long busiest_nr_running;
Suresh Siddhadd5feea2010-02-23 16:13:52 -08002462 unsigned long busiest_group_capacity;
Nikhil Raofab47622010-10-15 13:12:29 -07002463 unsigned long busiest_has_capacity;
Suresh Siddhaaae6d3d2010-09-17 15:02:32 -07002464 unsigned int busiest_group_weight;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002465
2466 int group_imb; /* Is there imbalance in this sd */
2467#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
2468 int power_savings_balance; /* Is powersave balance needed for this sd */
2469 struct sched_group *group_min; /* Least loaded group in sd */
2470 struct sched_group *group_leader; /* Group which relieves group_min */
2471 unsigned long min_load_per_task; /* load_per_task in group_min */
2472 unsigned long leader_nr_running; /* Nr running of group_leader */
2473 unsigned long min_nr_running; /* Nr running of group_min */
2474#endif
2475};
2476
2477/*
2478 * sg_lb_stats - stats of a sched_group required for load_balancing
2479 */
2480struct sg_lb_stats {
2481 unsigned long avg_load; /*Avg load across the CPUs of the group */
2482 unsigned long group_load; /* Total load over the CPUs of the group */
2483 unsigned long sum_nr_running; /* Nr tasks running in the group */
2484 unsigned long sum_weighted_load; /* Weighted load of group's tasks */
2485 unsigned long group_capacity;
Suresh Siddhaaae6d3d2010-09-17 15:02:32 -07002486 unsigned long idle_cpus;
2487 unsigned long group_weight;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002488 int group_imb; /* Is there an imbalance in the group ? */
Nikhil Raofab47622010-10-15 13:12:29 -07002489 int group_has_capacity; /* Is there extra capacity in the group? */
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002490};
2491
2492/**
2493 * group_first_cpu - Returns the first cpu in the cpumask of a sched_group.
2494 * @group: The group whose first cpu is to be returned.
2495 */
2496static inline unsigned int group_first_cpu(struct sched_group *group)
2497{
2498 return cpumask_first(sched_group_cpus(group));
2499}
2500
2501/**
2502 * get_sd_load_idx - Obtain the load index for a given sched domain.
2503 * @sd: The sched_domain whose load_idx is to be obtained.
2504 * @idle: The Idle status of the CPU for whose sd load_icx is obtained.
2505 */
2506static inline int get_sd_load_idx(struct sched_domain *sd,
2507 enum cpu_idle_type idle)
2508{
2509 int load_idx;
2510
2511 switch (idle) {
2512 case CPU_NOT_IDLE:
2513 load_idx = sd->busy_idx;
2514 break;
2515
2516 case CPU_NEWLY_IDLE:
2517 load_idx = sd->newidle_idx;
2518 break;
2519 default:
2520 load_idx = sd->idle_idx;
2521 break;
2522 }
2523
2524 return load_idx;
2525}
2526
2527
2528#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
2529/**
2530 * init_sd_power_savings_stats - Initialize power savings statistics for
2531 * the given sched_domain, during load balancing.
2532 *
2533 * @sd: Sched domain whose power-savings statistics are to be initialized.
2534 * @sds: Variable containing the statistics for sd.
2535 * @idle: Idle status of the CPU at which we're performing load-balancing.
2536 */
2537static inline void init_sd_power_savings_stats(struct sched_domain *sd,
2538 struct sd_lb_stats *sds, enum cpu_idle_type idle)
2539{
2540 /*
2541 * Busy processors will not participate in power savings
2542 * balance.
2543 */
2544 if (idle == CPU_NOT_IDLE || !(sd->flags & SD_POWERSAVINGS_BALANCE))
2545 sds->power_savings_balance = 0;
2546 else {
2547 sds->power_savings_balance = 1;
2548 sds->min_nr_running = ULONG_MAX;
2549 sds->leader_nr_running = 0;
2550 }
2551}
2552
2553/**
2554 * update_sd_power_savings_stats - Update the power saving stats for a
2555 * sched_domain while performing load balancing.
2556 *
2557 * @group: sched_group belonging to the sched_domain under consideration.
2558 * @sds: Variable containing the statistics of the sched_domain
2559 * @local_group: Does group contain the CPU for which we're performing
2560 * load balancing ?
2561 * @sgs: Variable containing the statistics of the group.
2562 */
2563static inline void update_sd_power_savings_stats(struct sched_group *group,
2564 struct sd_lb_stats *sds, int local_group, struct sg_lb_stats *sgs)
2565{
2566
2567 if (!sds->power_savings_balance)
2568 return;
2569
2570 /*
2571 * If the local group is idle or completely loaded
2572 * no need to do power savings balance at this domain
2573 */
2574 if (local_group && (sds->this_nr_running >= sgs->group_capacity ||
2575 !sds->this_nr_running))
2576 sds->power_savings_balance = 0;
2577
2578 /*
2579 * If a group is already running at full capacity or idle,
2580 * don't include that group in power savings calculations
2581 */
2582 if (!sds->power_savings_balance ||
2583 sgs->sum_nr_running >= sgs->group_capacity ||
2584 !sgs->sum_nr_running)
2585 return;
2586
2587 /*
2588 * Calculate the group which has the least non-idle load.
2589 * This is the group from where we need to pick up the load
2590 * for saving power
2591 */
2592 if ((sgs->sum_nr_running < sds->min_nr_running) ||
2593 (sgs->sum_nr_running == sds->min_nr_running &&
2594 group_first_cpu(group) > group_first_cpu(sds->group_min))) {
2595 sds->group_min = group;
2596 sds->min_nr_running = sgs->sum_nr_running;
2597 sds->min_load_per_task = sgs->sum_weighted_load /
2598 sgs->sum_nr_running;
2599 }
2600
2601 /*
2602 * Calculate the group which is almost near its
2603 * capacity but still has some space to pick up some load
2604 * from other group and save more power
2605 */
2606 if (sgs->sum_nr_running + 1 > sgs->group_capacity)
2607 return;
2608
2609 if (sgs->sum_nr_running > sds->leader_nr_running ||
2610 (sgs->sum_nr_running == sds->leader_nr_running &&
2611 group_first_cpu(group) < group_first_cpu(sds->group_leader))) {
2612 sds->group_leader = group;
2613 sds->leader_nr_running = sgs->sum_nr_running;
2614 }
2615}
2616
2617/**
2618 * check_power_save_busiest_group - see if there is potential for some power-savings balance
2619 * @sds: Variable containing the statistics of the sched_domain
2620 * under consideration.
2621 * @this_cpu: Cpu at which we're currently performing load-balancing.
2622 * @imbalance: Variable to store the imbalance.
2623 *
2624 * Description:
2625 * Check if we have potential to perform some power-savings balance.
2626 * If yes, set the busiest group to be the least loaded group in the
2627 * sched_domain, so that it's CPUs can be put to idle.
2628 *
2629 * Returns 1 if there is potential to perform power-savings balance.
2630 * Else returns 0.
2631 */
2632static inline int check_power_save_busiest_group(struct sd_lb_stats *sds,
2633 int this_cpu, unsigned long *imbalance)
2634{
2635 if (!sds->power_savings_balance)
2636 return 0;
2637
2638 if (sds->this != sds->group_leader ||
2639 sds->group_leader == sds->group_min)
2640 return 0;
2641
2642 *imbalance = sds->min_load_per_task;
2643 sds->busiest = sds->group_min;
2644
2645 return 1;
2646
2647}
2648#else /* CONFIG_SCHED_MC || CONFIG_SCHED_SMT */
2649static inline void init_sd_power_savings_stats(struct sched_domain *sd,
2650 struct sd_lb_stats *sds, enum cpu_idle_type idle)
2651{
2652 return;
2653}
2654
2655static inline void update_sd_power_savings_stats(struct sched_group *group,
2656 struct sd_lb_stats *sds, int local_group, struct sg_lb_stats *sgs)
2657{
2658 return;
2659}
2660
2661static inline int check_power_save_busiest_group(struct sd_lb_stats *sds,
2662 int this_cpu, unsigned long *imbalance)
2663{
2664 return 0;
2665}
2666#endif /* CONFIG_SCHED_MC || CONFIG_SCHED_SMT */
2667
2668
2669unsigned long default_scale_freq_power(struct sched_domain *sd, int cpu)
2670{
Nikhil Rao1399fa72011-05-18 10:09:39 -07002671 return SCHED_POWER_SCALE;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002672}
2673
2674unsigned long __weak arch_scale_freq_power(struct sched_domain *sd, int cpu)
2675{
2676 return default_scale_freq_power(sd, cpu);
2677}
2678
2679unsigned long default_scale_smt_power(struct sched_domain *sd, int cpu)
2680{
Peter Zijlstra669c55e2010-04-16 14:59:29 +02002681 unsigned long weight = sd->span_weight;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002682 unsigned long smt_gain = sd->smt_gain;
2683
2684 smt_gain /= weight;
2685
2686 return smt_gain;
2687}
2688
2689unsigned long __weak arch_scale_smt_power(struct sched_domain *sd, int cpu)
2690{
2691 return default_scale_smt_power(sd, cpu);
2692}
2693
2694unsigned long scale_rt_power(int cpu)
2695{
2696 struct rq *rq = cpu_rq(cpu);
2697 u64 total, available;
2698
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002699 total = sched_avg_period() + (rq->clock - rq->age_stamp);
Venkatesh Pallipadiaa483802010-10-04 17:03:22 -07002700
2701 if (unlikely(total < rq->rt_avg)) {
2702 /* Ensures that power won't end up being negative */
2703 available = 0;
2704 } else {
2705 available = total - rq->rt_avg;
2706 }
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002707
Nikhil Rao1399fa72011-05-18 10:09:39 -07002708 if (unlikely((s64)total < SCHED_POWER_SCALE))
2709 total = SCHED_POWER_SCALE;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002710
Nikhil Rao1399fa72011-05-18 10:09:39 -07002711 total >>= SCHED_POWER_SHIFT;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002712
2713 return div_u64(available, total);
2714}
2715
2716static void update_cpu_power(struct sched_domain *sd, int cpu)
2717{
Peter Zijlstra669c55e2010-04-16 14:59:29 +02002718 unsigned long weight = sd->span_weight;
Nikhil Rao1399fa72011-05-18 10:09:39 -07002719 unsigned long power = SCHED_POWER_SCALE;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002720 struct sched_group *sdg = sd->groups;
2721
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002722 if ((sd->flags & SD_SHARE_CPUPOWER) && weight > 1) {
2723 if (sched_feat(ARCH_POWER))
2724 power *= arch_scale_smt_power(sd, cpu);
2725 else
2726 power *= default_scale_smt_power(sd, cpu);
2727
Nikhil Rao1399fa72011-05-18 10:09:39 -07002728 power >>= SCHED_POWER_SHIFT;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002729 }
2730
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02002731 sdg->sgp->power_orig = power;
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002732
2733 if (sched_feat(ARCH_POWER))
2734 power *= arch_scale_freq_power(sd, cpu);
2735 else
2736 power *= default_scale_freq_power(sd, cpu);
2737
Nikhil Rao1399fa72011-05-18 10:09:39 -07002738 power >>= SCHED_POWER_SHIFT;
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002739
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002740 power *= scale_rt_power(cpu);
Nikhil Rao1399fa72011-05-18 10:09:39 -07002741 power >>= SCHED_POWER_SHIFT;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002742
2743 if (!power)
2744 power = 1;
2745
Peter Zijlstrae51fd5e2010-05-31 12:37:30 +02002746 cpu_rq(cpu)->cpu_power = power;
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02002747 sdg->sgp->power = power;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002748}
2749
2750static void update_group_power(struct sched_domain *sd, int cpu)
2751{
2752 struct sched_domain *child = sd->child;
2753 struct sched_group *group, *sdg = sd->groups;
2754 unsigned long power;
2755
2756 if (!child) {
2757 update_cpu_power(sd, cpu);
2758 return;
2759 }
2760
2761 power = 0;
2762
2763 group = child->groups;
2764 do {
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02002765 power += group->sgp->power;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002766 group = group->next;
2767 } while (group != child->groups);
2768
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02002769 sdg->sgp->power = power;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002770}
2771
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002772/*
2773 * Try and fix up capacity for tiny siblings, this is needed when
2774 * things like SD_ASYM_PACKING need f_b_g to select another sibling
2775 * which on its own isn't powerful enough.
2776 *
2777 * See update_sd_pick_busiest() and check_asym_packing().
2778 */
2779static inline int
2780fix_small_capacity(struct sched_domain *sd, struct sched_group *group)
2781{
2782 /*
Nikhil Rao1399fa72011-05-18 10:09:39 -07002783 * Only siblings can have significantly less than SCHED_POWER_SCALE
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002784 */
Peter Zijlstraa6c75f22011-04-07 14:09:52 +02002785 if (!(sd->flags & SD_SHARE_CPUPOWER))
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002786 return 0;
2787
2788 /*
2789 * If ~90% of the cpu_power is still there, we're good.
2790 */
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02002791 if (group->sgp->power * 32 > group->sgp->power_orig * 29)
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002792 return 1;
2793
2794 return 0;
2795}
2796
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002797/**
2798 * update_sg_lb_stats - Update sched_group's statistics for load balancing.
2799 * @sd: The sched_domain whose statistics are to be updated.
2800 * @group: sched_group whose statistics are to be updated.
2801 * @this_cpu: Cpu for which load balance is currently performed.
2802 * @idle: Idle status of this_cpu
2803 * @load_idx: Load index of sched_domain of this_cpu for load calc.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002804 * @local_group: Does group contain this_cpu.
2805 * @cpus: Set of cpus considered for load balancing.
2806 * @balance: Should we balance.
2807 * @sgs: variable to hold the statistics for this group.
2808 */
2809static inline void update_sg_lb_stats(struct sched_domain *sd,
2810 struct sched_group *group, int this_cpu,
Venkatesh Pallipadi46e49b32011-02-14 14:38:50 -08002811 enum cpu_idle_type idle, int load_idx,
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002812 int local_group, const struct cpumask *cpus,
2813 int *balance, struct sg_lb_stats *sgs)
2814{
Nikhil Rao2582f0e2010-10-13 12:09:36 -07002815 unsigned long load, max_cpu_load, min_cpu_load, max_nr_running;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002816 int i;
2817 unsigned int balance_cpu = -1, first_idle_cpu = 0;
Suresh Siddhadd5feea2010-02-23 16:13:52 -08002818 unsigned long avg_load_per_task = 0;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002819
Gautham R Shenoy871e35b2010-01-20 14:02:44 -06002820 if (local_group)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002821 balance_cpu = group_first_cpu(group);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002822
2823 /* Tally up the load of all CPUs in the group */
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002824 max_cpu_load = 0;
2825 min_cpu_load = ~0UL;
Nikhil Rao2582f0e2010-10-13 12:09:36 -07002826 max_nr_running = 0;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002827
2828 for_each_cpu_and(i, sched_group_cpus(group), cpus) {
2829 struct rq *rq = cpu_rq(i);
2830
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002831 /* Bias balancing toward cpus of our domain */
2832 if (local_group) {
2833 if (idle_cpu(i) && !first_idle_cpu) {
2834 first_idle_cpu = 1;
2835 balance_cpu = i;
2836 }
2837
2838 load = target_load(i, load_idx);
2839 } else {
2840 load = source_load(i, load_idx);
Nikhil Rao2582f0e2010-10-13 12:09:36 -07002841 if (load > max_cpu_load) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002842 max_cpu_load = load;
Nikhil Rao2582f0e2010-10-13 12:09:36 -07002843 max_nr_running = rq->nr_running;
2844 }
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002845 if (min_cpu_load > load)
2846 min_cpu_load = load;
2847 }
2848
2849 sgs->group_load += load;
2850 sgs->sum_nr_running += rq->nr_running;
2851 sgs->sum_weighted_load += weighted_cpuload(i);
Suresh Siddhaaae6d3d2010-09-17 15:02:32 -07002852 if (idle_cpu(i))
2853 sgs->idle_cpus++;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002854 }
2855
2856 /*
2857 * First idle cpu or the first cpu(busiest) in this sched group
2858 * is eligible for doing load balancing at this and above
2859 * domains. In the newly idle case, we will allow all the cpu's
2860 * to do the newly idle load balance.
2861 */
Peter Zijlstrabbc8cb52010-07-09 15:15:43 +02002862 if (idle != CPU_NEWLY_IDLE && local_group) {
2863 if (balance_cpu != this_cpu) {
2864 *balance = 0;
2865 return;
2866 }
2867 update_group_power(sd, this_cpu);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002868 }
2869
2870 /* Adjust by relative CPU power of the group */
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02002871 sgs->avg_load = (sgs->group_load*SCHED_POWER_SCALE) / group->sgp->power;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002872
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002873 /*
2874 * Consider the group unbalanced when the imbalance is larger
Peter Zijlstra866ab432011-02-21 18:56:47 +01002875 * than the average weight of a task.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002876 *
2877 * APZ: with cgroup the avg task weight can vary wildly and
2878 * might not be a suitable number - should we keep a
2879 * normalized nr_running number somewhere that negates
2880 * the hierarchy?
2881 */
Suresh Siddhadd5feea2010-02-23 16:13:52 -08002882 if (sgs->sum_nr_running)
2883 avg_load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002884
Peter Zijlstra866ab432011-02-21 18:56:47 +01002885 if ((max_cpu_load - min_cpu_load) >= avg_load_per_task && max_nr_running > 1)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002886 sgs->group_imb = 1;
2887
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02002888 sgs->group_capacity = DIV_ROUND_CLOSEST(group->sgp->power,
Nikhil Rao1399fa72011-05-18 10:09:39 -07002889 SCHED_POWER_SCALE);
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10002890 if (!sgs->group_capacity)
2891 sgs->group_capacity = fix_small_capacity(sd, group);
Suresh Siddhaaae6d3d2010-09-17 15:02:32 -07002892 sgs->group_weight = group->group_weight;
Nikhil Raofab47622010-10-15 13:12:29 -07002893
2894 if (sgs->group_capacity > sgs->sum_nr_running)
2895 sgs->group_has_capacity = 1;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002896}
2897
2898/**
Michael Neuling532cb4c2010-06-08 14:57:02 +10002899 * update_sd_pick_busiest - return 1 on busiest group
2900 * @sd: sched_domain whose statistics are to be checked
2901 * @sds: sched_domain statistics
2902 * @sg: sched_group candidate to be checked for being the busiest
Michael Neulingb6b12292010-06-10 12:06:21 +10002903 * @sgs: sched_group statistics
2904 * @this_cpu: the current cpu
Michael Neuling532cb4c2010-06-08 14:57:02 +10002905 *
2906 * Determine if @sg is a busier group than the previously selected
2907 * busiest group.
2908 */
2909static bool update_sd_pick_busiest(struct sched_domain *sd,
2910 struct sd_lb_stats *sds,
2911 struct sched_group *sg,
2912 struct sg_lb_stats *sgs,
2913 int this_cpu)
2914{
2915 if (sgs->avg_load <= sds->max_load)
2916 return false;
2917
2918 if (sgs->sum_nr_running > sgs->group_capacity)
2919 return true;
2920
2921 if (sgs->group_imb)
2922 return true;
2923
2924 /*
2925 * ASYM_PACKING needs to move all the work to the lowest
2926 * numbered CPUs in the group, therefore mark all groups
2927 * higher than ourself as busy.
2928 */
2929 if ((sd->flags & SD_ASYM_PACKING) && sgs->sum_nr_running &&
2930 this_cpu < group_first_cpu(sg)) {
2931 if (!sds->busiest)
2932 return true;
2933
2934 if (group_first_cpu(sds->busiest) > group_first_cpu(sg))
2935 return true;
2936 }
2937
2938 return false;
2939}
2940
2941/**
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002942 * update_sd_lb_stats - Update sched_group's statistics for load balancing.
2943 * @sd: sched_domain whose statistics are to be updated.
2944 * @this_cpu: Cpu for which load balance is currently performed.
2945 * @idle: Idle status of this_cpu
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002946 * @cpus: Set of cpus considered for load balancing.
2947 * @balance: Should we balance.
2948 * @sds: variable to hold the statistics for this sched_domain.
2949 */
2950static inline void update_sd_lb_stats(struct sched_domain *sd, int this_cpu,
Venkatesh Pallipadi46e49b32011-02-14 14:38:50 -08002951 enum cpu_idle_type idle, const struct cpumask *cpus,
2952 int *balance, struct sd_lb_stats *sds)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002953{
2954 struct sched_domain *child = sd->child;
Michael Neuling532cb4c2010-06-08 14:57:02 +10002955 struct sched_group *sg = sd->groups;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002956 struct sg_lb_stats sgs;
2957 int load_idx, prefer_sibling = 0;
2958
2959 if (child && child->flags & SD_PREFER_SIBLING)
2960 prefer_sibling = 1;
2961
2962 init_sd_power_savings_stats(sd, sds, idle);
2963 load_idx = get_sd_load_idx(sd, idle);
2964
2965 do {
2966 int local_group;
2967
Michael Neuling532cb4c2010-06-08 14:57:02 +10002968 local_group = cpumask_test_cpu(this_cpu, sched_group_cpus(sg));
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002969 memset(&sgs, 0, sizeof(sgs));
Venkatesh Pallipadi46e49b32011-02-14 14:38:50 -08002970 update_sg_lb_stats(sd, sg, this_cpu, idle, load_idx,
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002971 local_group, cpus, balance, &sgs);
2972
Peter Zijlstra8f190fb2009-12-24 14:18:21 +01002973 if (local_group && !(*balance))
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002974 return;
2975
2976 sds->total_load += sgs.group_load;
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02002977 sds->total_pwr += sg->sgp->power;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002978
2979 /*
2980 * In case the child domain prefers tasks go to siblings
Michael Neuling532cb4c2010-06-08 14:57:02 +10002981 * first, lower the sg capacity to one so that we'll try
Nikhil Rao75dd3212010-10-15 13:12:30 -07002982 * and move all the excess tasks away. We lower the capacity
2983 * of a group only if the local group has the capacity to fit
2984 * these excess tasks, i.e. nr_running < group_capacity. The
2985 * extra check prevents the case where you always pull from the
2986 * heaviest group when it is already under-utilized (possible
2987 * with a large weight task outweighs the tasks on the system).
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002988 */
Nikhil Rao75dd3212010-10-15 13:12:30 -07002989 if (prefer_sibling && !local_group && sds->this_has_capacity)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002990 sgs.group_capacity = min(sgs.group_capacity, 1UL);
2991
2992 if (local_group) {
2993 sds->this_load = sgs.avg_load;
Michael Neuling532cb4c2010-06-08 14:57:02 +10002994 sds->this = sg;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01002995 sds->this_nr_running = sgs.sum_nr_running;
2996 sds->this_load_per_task = sgs.sum_weighted_load;
Nikhil Raofab47622010-10-15 13:12:29 -07002997 sds->this_has_capacity = sgs.group_has_capacity;
Suresh Siddhaaae6d3d2010-09-17 15:02:32 -07002998 sds->this_idle_cpus = sgs.idle_cpus;
Michael Neuling532cb4c2010-06-08 14:57:02 +10002999 } else if (update_sd_pick_busiest(sd, sds, sg, &sgs, this_cpu)) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003000 sds->max_load = sgs.avg_load;
Michael Neuling532cb4c2010-06-08 14:57:02 +10003001 sds->busiest = sg;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003002 sds->busiest_nr_running = sgs.sum_nr_running;
Suresh Siddhaaae6d3d2010-09-17 15:02:32 -07003003 sds->busiest_idle_cpus = sgs.idle_cpus;
Suresh Siddhadd5feea2010-02-23 16:13:52 -08003004 sds->busiest_group_capacity = sgs.group_capacity;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003005 sds->busiest_load_per_task = sgs.sum_weighted_load;
Nikhil Raofab47622010-10-15 13:12:29 -07003006 sds->busiest_has_capacity = sgs.group_has_capacity;
Suresh Siddhaaae6d3d2010-09-17 15:02:32 -07003007 sds->busiest_group_weight = sgs.group_weight;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003008 sds->group_imb = sgs.group_imb;
3009 }
3010
Michael Neuling532cb4c2010-06-08 14:57:02 +10003011 update_sd_power_savings_stats(sg, sds, local_group, &sgs);
3012 sg = sg->next;
3013 } while (sg != sd->groups);
3014}
3015
Michael Neuling2ec57d42010-06-29 12:02:01 +10003016int __weak arch_sd_sibling_asym_packing(void)
Michael Neuling532cb4c2010-06-08 14:57:02 +10003017{
3018 return 0*SD_ASYM_PACKING;
3019}
3020
3021/**
3022 * check_asym_packing - Check to see if the group is packed into the
3023 * sched doman.
3024 *
3025 * This is primarily intended to used at the sibling level. Some
3026 * cores like POWER7 prefer to use lower numbered SMT threads. In the
3027 * case of POWER7, it can move to lower SMT modes only when higher
3028 * threads are idle. When in lower SMT modes, the threads will
3029 * perform better since they share less core resources. Hence when we
3030 * have idle threads, we want them to be the higher ones.
3031 *
3032 * This packing function is run on idle threads. It checks to see if
3033 * the busiest CPU in this domain (core in the P7 case) has a higher
3034 * CPU number than the packing function is being run on. Here we are
3035 * assuming lower CPU number will be equivalent to lower a SMT thread
3036 * number.
3037 *
Michael Neulingb6b12292010-06-10 12:06:21 +10003038 * Returns 1 when packing is required and a task should be moved to
3039 * this CPU. The amount of the imbalance is returned in *imbalance.
3040 *
Michael Neuling532cb4c2010-06-08 14:57:02 +10003041 * @sd: The sched_domain whose packing is to be checked.
3042 * @sds: Statistics of the sched_domain which is to be packed
3043 * @this_cpu: The cpu at whose sched_domain we're performing load-balance.
3044 * @imbalance: returns amount of imbalanced due to packing.
Michael Neuling532cb4c2010-06-08 14:57:02 +10003045 */
3046static int check_asym_packing(struct sched_domain *sd,
3047 struct sd_lb_stats *sds,
3048 int this_cpu, unsigned long *imbalance)
3049{
3050 int busiest_cpu;
3051
3052 if (!(sd->flags & SD_ASYM_PACKING))
3053 return 0;
3054
3055 if (!sds->busiest)
3056 return 0;
3057
3058 busiest_cpu = group_first_cpu(sds->busiest);
3059 if (this_cpu > busiest_cpu)
3060 return 0;
3061
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02003062 *imbalance = DIV_ROUND_CLOSEST(sds->max_load * sds->busiest->sgp->power,
Nikhil Rao1399fa72011-05-18 10:09:39 -07003063 SCHED_POWER_SCALE);
Michael Neuling532cb4c2010-06-08 14:57:02 +10003064 return 1;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003065}
3066
3067/**
3068 * fix_small_imbalance - Calculate the minor imbalance that exists
3069 * amongst the groups of a sched_domain, during
3070 * load balancing.
3071 * @sds: Statistics of the sched_domain whose imbalance is to be calculated.
3072 * @this_cpu: The cpu at whose sched_domain we're performing load-balance.
3073 * @imbalance: Variable to store the imbalance.
3074 */
3075static inline void fix_small_imbalance(struct sd_lb_stats *sds,
3076 int this_cpu, unsigned long *imbalance)
3077{
3078 unsigned long tmp, pwr_now = 0, pwr_move = 0;
3079 unsigned int imbn = 2;
Suresh Siddhadd5feea2010-02-23 16:13:52 -08003080 unsigned long scaled_busy_load_per_task;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003081
3082 if (sds->this_nr_running) {
3083 sds->this_load_per_task /= sds->this_nr_running;
3084 if (sds->busiest_load_per_task >
3085 sds->this_load_per_task)
3086 imbn = 1;
3087 } else
3088 sds->this_load_per_task =
3089 cpu_avg_load_per_task(this_cpu);
3090
Suresh Siddhadd5feea2010-02-23 16:13:52 -08003091 scaled_busy_load_per_task = sds->busiest_load_per_task
Nikhil Rao1399fa72011-05-18 10:09:39 -07003092 * SCHED_POWER_SCALE;
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02003093 scaled_busy_load_per_task /= sds->busiest->sgp->power;
Suresh Siddhadd5feea2010-02-23 16:13:52 -08003094
3095 if (sds->max_load - sds->this_load + scaled_busy_load_per_task >=
3096 (scaled_busy_load_per_task * imbn)) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003097 *imbalance = sds->busiest_load_per_task;
3098 return;
3099 }
3100
3101 /*
3102 * OK, we don't have enough imbalance to justify moving tasks,
3103 * however we may be able to increase total CPU power used by
3104 * moving them.
3105 */
3106
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02003107 pwr_now += sds->busiest->sgp->power *
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003108 min(sds->busiest_load_per_task, sds->max_load);
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02003109 pwr_now += sds->this->sgp->power *
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003110 min(sds->this_load_per_task, sds->this_load);
Nikhil Rao1399fa72011-05-18 10:09:39 -07003111 pwr_now /= SCHED_POWER_SCALE;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003112
3113 /* Amount of load we'd subtract */
Nikhil Rao1399fa72011-05-18 10:09:39 -07003114 tmp = (sds->busiest_load_per_task * SCHED_POWER_SCALE) /
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02003115 sds->busiest->sgp->power;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003116 if (sds->max_load > tmp)
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02003117 pwr_move += sds->busiest->sgp->power *
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003118 min(sds->busiest_load_per_task, sds->max_load - tmp);
3119
3120 /* Amount of load we'd add */
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02003121 if (sds->max_load * sds->busiest->sgp->power <
Nikhil Rao1399fa72011-05-18 10:09:39 -07003122 sds->busiest_load_per_task * SCHED_POWER_SCALE)
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02003123 tmp = (sds->max_load * sds->busiest->sgp->power) /
3124 sds->this->sgp->power;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003125 else
Nikhil Rao1399fa72011-05-18 10:09:39 -07003126 tmp = (sds->busiest_load_per_task * SCHED_POWER_SCALE) /
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02003127 sds->this->sgp->power;
3128 pwr_move += sds->this->sgp->power *
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003129 min(sds->this_load_per_task, sds->this_load + tmp);
Nikhil Rao1399fa72011-05-18 10:09:39 -07003130 pwr_move /= SCHED_POWER_SCALE;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003131
3132 /* Move if we gain throughput */
3133 if (pwr_move > pwr_now)
3134 *imbalance = sds->busiest_load_per_task;
3135}
3136
3137/**
3138 * calculate_imbalance - Calculate the amount of imbalance present within the
3139 * groups of a given sched_domain during load balance.
3140 * @sds: statistics of the sched_domain whose imbalance is to be calculated.
3141 * @this_cpu: Cpu for which currently load balance is being performed.
3142 * @imbalance: The variable to store the imbalance.
3143 */
3144static inline void calculate_imbalance(struct sd_lb_stats *sds, int this_cpu,
3145 unsigned long *imbalance)
3146{
Suresh Siddhadd5feea2010-02-23 16:13:52 -08003147 unsigned long max_pull, load_above_capacity = ~0UL;
3148
3149 sds->busiest_load_per_task /= sds->busiest_nr_running;
3150 if (sds->group_imb) {
3151 sds->busiest_load_per_task =
3152 min(sds->busiest_load_per_task, sds->avg_load);
3153 }
3154
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003155 /*
3156 * In the presence of smp nice balancing, certain scenarios can have
3157 * max load less than avg load(as we skip the groups at or below
3158 * its cpu_power, while calculating max_load..)
3159 */
3160 if (sds->max_load < sds->avg_load) {
3161 *imbalance = 0;
3162 return fix_small_imbalance(sds, this_cpu, imbalance);
3163 }
3164
Suresh Siddhadd5feea2010-02-23 16:13:52 -08003165 if (!sds->group_imb) {
3166 /*
3167 * Don't want to pull so many tasks that a group would go idle.
3168 */
3169 load_above_capacity = (sds->busiest_nr_running -
3170 sds->busiest_group_capacity);
3171
Nikhil Rao1399fa72011-05-18 10:09:39 -07003172 load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_POWER_SCALE);
Suresh Siddhadd5feea2010-02-23 16:13:52 -08003173
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02003174 load_above_capacity /= sds->busiest->sgp->power;
Suresh Siddhadd5feea2010-02-23 16:13:52 -08003175 }
3176
3177 /*
3178 * We're trying to get all the cpus to the average_load, so we don't
3179 * want to push ourselves above the average load, nor do we wish to
3180 * reduce the max loaded cpu below the average load. At the same time,
3181 * we also don't want to reduce the group load below the group capacity
3182 * (so that we can implement power-savings policies etc). Thus we look
3183 * for the minimum possible imbalance.
3184 * Be careful of negative numbers as they'll appear as very large values
3185 * with unsigned longs.
3186 */
3187 max_pull = min(sds->max_load - sds->avg_load, load_above_capacity);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003188
3189 /* How much load to actually move to equalise the imbalance */
Peter Zijlstra9c3f75c2011-07-14 13:00:06 +02003190 *imbalance = min(max_pull * sds->busiest->sgp->power,
3191 (sds->avg_load - sds->this_load) * sds->this->sgp->power)
Nikhil Rao1399fa72011-05-18 10:09:39 -07003192 / SCHED_POWER_SCALE;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003193
3194 /*
3195 * if *imbalance is less than the average load per runnable task
Lucas De Marchi25985ed2011-03-30 22:57:33 -03003196 * there is no guarantee that any tasks will be moved so we'll have
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003197 * a think about bumping its value to force at least one task to be
3198 * moved
3199 */
3200 if (*imbalance < sds->busiest_load_per_task)
3201 return fix_small_imbalance(sds, this_cpu, imbalance);
3202
3203}
Nikhil Raofab47622010-10-15 13:12:29 -07003204
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003205/******* find_busiest_group() helpers end here *********************/
3206
3207/**
3208 * find_busiest_group - Returns the busiest group within the sched_domain
3209 * if there is an imbalance. If there isn't an imbalance, and
3210 * the user has opted for power-savings, it returns a group whose
3211 * CPUs can be put to idle by rebalancing those tasks elsewhere, if
3212 * such a group exists.
3213 *
3214 * Also calculates the amount of weighted load which should be moved
3215 * to restore balance.
3216 *
3217 * @sd: The sched_domain whose busiest group is to be returned.
3218 * @this_cpu: The cpu for which load balancing is currently being performed.
3219 * @imbalance: Variable which stores amount of weighted load which should
3220 * be moved to restore balance/put a group to idle.
3221 * @idle: The idle status of this_cpu.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003222 * @cpus: The set of CPUs under consideration for load-balancing.
3223 * @balance: Pointer to a variable indicating if this_cpu
3224 * is the appropriate cpu to perform load balancing at this_level.
3225 *
3226 * Returns: - the busiest group if imbalance exists.
3227 * - If no imbalance and user has opted for power-savings balance,
3228 * return the least loaded group whose CPUs can be
3229 * put to idle by rebalancing its tasks onto our group.
3230 */
3231static struct sched_group *
3232find_busiest_group(struct sched_domain *sd, int this_cpu,
3233 unsigned long *imbalance, enum cpu_idle_type idle,
Venkatesh Pallipadi46e49b32011-02-14 14:38:50 -08003234 const struct cpumask *cpus, int *balance)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003235{
3236 struct sd_lb_stats sds;
3237
3238 memset(&sds, 0, sizeof(sds));
3239
3240 /*
3241 * Compute the various statistics relavent for load balancing at
3242 * this level.
3243 */
Venkatesh Pallipadi46e49b32011-02-14 14:38:50 -08003244 update_sd_lb_stats(sd, this_cpu, idle, cpus, balance, &sds);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003245
Peter Zijlstracc57aa82011-02-21 18:55:32 +01003246 /*
3247 * this_cpu is not the appropriate cpu to perform load balancing at
3248 * this level.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003249 */
Peter Zijlstra8f190fb2009-12-24 14:18:21 +01003250 if (!(*balance))
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003251 goto ret;
3252
Michael Neuling532cb4c2010-06-08 14:57:02 +10003253 if ((idle == CPU_IDLE || idle == CPU_NEWLY_IDLE) &&
3254 check_asym_packing(sd, &sds, this_cpu, imbalance))
3255 return sds.busiest;
3256
Peter Zijlstracc57aa82011-02-21 18:55:32 +01003257 /* There is no busy sibling group to pull tasks from */
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003258 if (!sds.busiest || sds.busiest_nr_running == 0)
3259 goto out_balanced;
3260
Nikhil Rao1399fa72011-05-18 10:09:39 -07003261 sds.avg_load = (SCHED_POWER_SCALE * sds.total_load) / sds.total_pwr;
Ken Chenb0432d82011-04-07 17:23:22 -07003262
Peter Zijlstra866ab432011-02-21 18:56:47 +01003263 /*
3264 * If the busiest group is imbalanced the below checks don't
3265 * work because they assumes all things are equal, which typically
3266 * isn't true due to cpus_allowed constraints and the like.
3267 */
3268 if (sds.group_imb)
3269 goto force_balance;
3270
Peter Zijlstracc57aa82011-02-21 18:55:32 +01003271 /* SD_BALANCE_NEWIDLE trumps SMP nice when underutilized */
Nikhil Raofab47622010-10-15 13:12:29 -07003272 if (idle == CPU_NEWLY_IDLE && sds.this_has_capacity &&
3273 !sds.busiest_has_capacity)
3274 goto force_balance;
3275
Peter Zijlstracc57aa82011-02-21 18:55:32 +01003276 /*
3277 * If the local group is more busy than the selected busiest group
3278 * don't try and pull any tasks.
3279 */
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003280 if (sds.this_load >= sds.max_load)
3281 goto out_balanced;
3282
Peter Zijlstracc57aa82011-02-21 18:55:32 +01003283 /*
3284 * Don't pull any tasks if this group is already above the domain
3285 * average load.
3286 */
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003287 if (sds.this_load >= sds.avg_load)
3288 goto out_balanced;
3289
Peter Zijlstrac186faf2011-02-21 18:52:53 +01003290 if (idle == CPU_IDLE) {
Suresh Siddhaaae6d3d2010-09-17 15:02:32 -07003291 /*
3292 * This cpu is idle. If the busiest group load doesn't
3293 * have more tasks than the number of available cpu's and
3294 * there is no imbalance between this and busiest group
3295 * wrt to idle cpu's, it is balanced.
3296 */
Peter Zijlstrac186faf2011-02-21 18:52:53 +01003297 if ((sds.this_idle_cpus <= sds.busiest_idle_cpus + 1) &&
Suresh Siddhaaae6d3d2010-09-17 15:02:32 -07003298 sds.busiest_nr_running <= sds.busiest_group_weight)
3299 goto out_balanced;
Peter Zijlstrac186faf2011-02-21 18:52:53 +01003300 } else {
3301 /*
3302 * In the CPU_NEWLY_IDLE, CPU_NOT_IDLE cases, use
3303 * imbalance_pct to be conservative.
3304 */
3305 if (100 * sds.max_load <= sd->imbalance_pct * sds.this_load)
3306 goto out_balanced;
Suresh Siddhaaae6d3d2010-09-17 15:02:32 -07003307 }
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003308
Nikhil Raofab47622010-10-15 13:12:29 -07003309force_balance:
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003310 /* Looks like there is an imbalance. Compute it */
3311 calculate_imbalance(&sds, this_cpu, imbalance);
3312 return sds.busiest;
3313
3314out_balanced:
3315 /*
3316 * There is no obvious imbalance. But check if we can do some balancing
3317 * to save power.
3318 */
3319 if (check_power_save_busiest_group(&sds, this_cpu, imbalance))
3320 return sds.busiest;
3321ret:
3322 *imbalance = 0;
3323 return NULL;
3324}
3325
3326/*
3327 * find_busiest_queue - find the busiest runqueue among the cpus in group.
3328 */
3329static struct rq *
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10003330find_busiest_queue(struct sched_domain *sd, struct sched_group *group,
3331 enum cpu_idle_type idle, unsigned long imbalance,
3332 const struct cpumask *cpus)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003333{
3334 struct rq *busiest = NULL, *rq;
3335 unsigned long max_load = 0;
3336 int i;
3337
3338 for_each_cpu(i, sched_group_cpus(group)) {
3339 unsigned long power = power_of(i);
Nikhil Rao1399fa72011-05-18 10:09:39 -07003340 unsigned long capacity = DIV_ROUND_CLOSEST(power,
3341 SCHED_POWER_SCALE);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003342 unsigned long wl;
3343
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10003344 if (!capacity)
3345 capacity = fix_small_capacity(sd, group);
3346
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003347 if (!cpumask_test_cpu(i, cpus))
3348 continue;
3349
3350 rq = cpu_rq(i);
Thomas Gleixner6e40f5b2010-02-16 16:48:56 +01003351 wl = weighted_cpuload(i);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003352
Thomas Gleixner6e40f5b2010-02-16 16:48:56 +01003353 /*
3354 * When comparing with imbalance, use weighted_cpuload()
3355 * which is not scaled with the cpu power.
3356 */
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003357 if (capacity && rq->nr_running == 1 && wl > imbalance)
3358 continue;
3359
Thomas Gleixner6e40f5b2010-02-16 16:48:56 +01003360 /*
3361 * For the load comparisons with the other cpu's, consider
3362 * the weighted_cpuload() scaled with the cpu power, so that
3363 * the load can be moved away from the cpu that is potentially
3364 * running at a lower capacity.
3365 */
Nikhil Rao1399fa72011-05-18 10:09:39 -07003366 wl = (wl * SCHED_POWER_SCALE) / power;
Thomas Gleixner6e40f5b2010-02-16 16:48:56 +01003367
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003368 if (wl > max_load) {
3369 max_load = wl;
3370 busiest = rq;
3371 }
3372 }
3373
3374 return busiest;
3375}
3376
3377/*
3378 * Max backoff if we encounter pinned tasks. Pretty arbitrary value, but
3379 * so long as it is large enough.
3380 */
3381#define MAX_PINNED_INTERVAL 512
3382
3383/* Working cpumask for load_balance and load_balance_newidle. */
3384static DEFINE_PER_CPU(cpumask_var_t, load_balance_tmpmask);
3385
Venkatesh Pallipadi46e49b32011-02-14 14:38:50 -08003386static int need_active_balance(struct sched_domain *sd, int idle,
Michael Neuling532cb4c2010-06-08 14:57:02 +10003387 int busiest_cpu, int this_cpu)
Peter Zijlstra1af3ed32009-12-23 15:10:31 +01003388{
3389 if (idle == CPU_NEWLY_IDLE) {
Michael Neuling532cb4c2010-06-08 14:57:02 +10003390
3391 /*
3392 * ASYM_PACKING needs to force migrate tasks from busy but
3393 * higher numbered CPUs in order to pack all tasks in the
3394 * lowest numbered CPUs.
3395 */
3396 if ((sd->flags & SD_ASYM_PACKING) && busiest_cpu > this_cpu)
3397 return 1;
3398
Peter Zijlstra1af3ed32009-12-23 15:10:31 +01003399 /*
3400 * The only task running in a non-idle cpu can be moved to this
3401 * cpu in an attempt to completely freeup the other CPU
3402 * package.
3403 *
3404 * The package power saving logic comes from
3405 * find_busiest_group(). If there are no imbalance, then
3406 * f_b_g() will return NULL. However when sched_mc={1,2} then
3407 * f_b_g() will select a group from which a running task may be
3408 * pulled to this cpu in order to make the other package idle.
3409 * If there is no opportunity to make a package idle and if
3410 * there are no imbalance, then f_b_g() will return NULL and no
3411 * action will be taken in load_balance_newidle().
3412 *
3413 * Under normal task pull operation due to imbalance, there
3414 * will be more than one task in the source run queue and
3415 * move_tasks() will succeed. ld_moved will be true and this
3416 * active balance code will not be triggered.
3417 */
Peter Zijlstra1af3ed32009-12-23 15:10:31 +01003418 if (sched_mc_power_savings < POWERSAVINGS_BALANCE_WAKEUP)
3419 return 0;
3420 }
3421
3422 return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
3423}
3424
Tejun Heo969c7922010-05-06 18:49:21 +02003425static int active_load_balance_cpu_stop(void *data);
3426
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003427/*
3428 * Check this_cpu to ensure it is balanced within domain. Attempt to move
3429 * tasks if there is an imbalance.
3430 */
3431static int load_balance(int this_cpu, struct rq *this_rq,
3432 struct sched_domain *sd, enum cpu_idle_type idle,
3433 int *balance)
3434{
Venkatesh Pallipadi46e49b32011-02-14 14:38:50 -08003435 int ld_moved, all_pinned = 0, active_balance = 0;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003436 struct sched_group *group;
3437 unsigned long imbalance;
3438 struct rq *busiest;
3439 unsigned long flags;
3440 struct cpumask *cpus = __get_cpu_var(load_balance_tmpmask);
3441
3442 cpumask_copy(cpus, cpu_active_mask);
3443
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003444 schedstat_inc(sd, lb_count[idle]);
3445
3446redo:
Venkatesh Pallipadi46e49b32011-02-14 14:38:50 -08003447 group = find_busiest_group(sd, this_cpu, &imbalance, idle,
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003448 cpus, balance);
3449
3450 if (*balance == 0)
3451 goto out_balanced;
3452
3453 if (!group) {
3454 schedstat_inc(sd, lb_nobusyg[idle]);
3455 goto out_balanced;
3456 }
3457
Srivatsa Vaddagiri9d5efe02010-06-08 14:57:02 +10003458 busiest = find_busiest_queue(sd, group, idle, imbalance, cpus);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003459 if (!busiest) {
3460 schedstat_inc(sd, lb_nobusyq[idle]);
3461 goto out_balanced;
3462 }
3463
3464 BUG_ON(busiest == this_rq);
3465
3466 schedstat_add(sd, lb_imbalance[idle], imbalance);
3467
3468 ld_moved = 0;
3469 if (busiest->nr_running > 1) {
3470 /*
3471 * Attempt to move tasks. If find_busiest_group has found
3472 * an imbalance but busiest->nr_running <= 1, the group is
3473 * still unbalanced. ld_moved simply stays zero, so it is
3474 * correctly treated as an imbalance.
3475 */
Ken Chenb30aef12011-04-08 12:20:16 -07003476 all_pinned = 1;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003477 local_irq_save(flags);
3478 double_rq_lock(this_rq, busiest);
3479 ld_moved = move_tasks(this_rq, this_cpu, busiest,
3480 imbalance, sd, idle, &all_pinned);
3481 double_rq_unlock(this_rq, busiest);
3482 local_irq_restore(flags);
3483
3484 /*
3485 * some other cpu did the load balance for us.
3486 */
3487 if (ld_moved && this_cpu != smp_processor_id())
3488 resched_cpu(this_cpu);
3489
3490 /* All tasks on this runqueue were pinned by CPU affinity */
3491 if (unlikely(all_pinned)) {
3492 cpumask_clear_cpu(cpu_of(busiest), cpus);
3493 if (!cpumask_empty(cpus))
3494 goto redo;
3495 goto out_balanced;
3496 }
3497 }
3498
3499 if (!ld_moved) {
3500 schedstat_inc(sd, lb_failed[idle]);
Venkatesh Pallipadi58b26c42010-09-10 18:19:17 -07003501 /*
3502 * Increment the failure counter only on periodic balance.
3503 * We do not want newidle balance, which can be very
3504 * frequent, pollute the failure counter causing
3505 * excessive cache_hot migrations and active balances.
3506 */
3507 if (idle != CPU_NEWLY_IDLE)
3508 sd->nr_balance_failed++;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003509
Venkatesh Pallipadi46e49b32011-02-14 14:38:50 -08003510 if (need_active_balance(sd, idle, cpu_of(busiest), this_cpu)) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003511 raw_spin_lock_irqsave(&busiest->lock, flags);
3512
Tejun Heo969c7922010-05-06 18:49:21 +02003513 /* don't kick the active_load_balance_cpu_stop,
3514 * if the curr task on busiest cpu can't be
3515 * moved to this_cpu
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003516 */
3517 if (!cpumask_test_cpu(this_cpu,
3518 &busiest->curr->cpus_allowed)) {
3519 raw_spin_unlock_irqrestore(&busiest->lock,
3520 flags);
3521 all_pinned = 1;
3522 goto out_one_pinned;
3523 }
3524
Tejun Heo969c7922010-05-06 18:49:21 +02003525 /*
3526 * ->active_balance synchronizes accesses to
3527 * ->active_balance_work. Once set, it's cleared
3528 * only after active load balance is finished.
3529 */
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003530 if (!busiest->active_balance) {
3531 busiest->active_balance = 1;
3532 busiest->push_cpu = this_cpu;
3533 active_balance = 1;
3534 }
3535 raw_spin_unlock_irqrestore(&busiest->lock, flags);
Tejun Heo969c7922010-05-06 18:49:21 +02003536
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003537 if (active_balance)
Tejun Heo969c7922010-05-06 18:49:21 +02003538 stop_one_cpu_nowait(cpu_of(busiest),
3539 active_load_balance_cpu_stop, busiest,
3540 &busiest->active_balance_work);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003541
3542 /*
3543 * We've kicked active balancing, reset the failure
3544 * counter.
3545 */
3546 sd->nr_balance_failed = sd->cache_nice_tries+1;
3547 }
3548 } else
3549 sd->nr_balance_failed = 0;
3550
3551 if (likely(!active_balance)) {
3552 /* We were unbalanced, so reset the balancing interval */
3553 sd->balance_interval = sd->min_interval;
3554 } else {
3555 /*
3556 * If we've begun active balancing, start to back off. This
3557 * case may not be covered by the all_pinned logic if there
3558 * is only 1 task on the busy runqueue (because we don't call
3559 * move_tasks).
3560 */
3561 if (sd->balance_interval < sd->max_interval)
3562 sd->balance_interval *= 2;
3563 }
3564
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003565 goto out;
3566
3567out_balanced:
3568 schedstat_inc(sd, lb_balanced[idle]);
3569
3570 sd->nr_balance_failed = 0;
3571
3572out_one_pinned:
3573 /* tune up the balancing interval */
3574 if ((all_pinned && sd->balance_interval < MAX_PINNED_INTERVAL) ||
3575 (sd->balance_interval < sd->max_interval))
3576 sd->balance_interval *= 2;
3577
Venkatesh Pallipadi46e49b32011-02-14 14:38:50 -08003578 ld_moved = 0;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003579out:
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003580 return ld_moved;
3581}
3582
3583/*
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003584 * idle_balance is called by schedule() if this_cpu is about to become
3585 * idle. Attempts to pull tasks from other CPUs.
3586 */
3587static void idle_balance(int this_cpu, struct rq *this_rq)
3588{
3589 struct sched_domain *sd;
3590 int pulled_task = 0;
3591 unsigned long next_balance = jiffies + HZ;
3592
3593 this_rq->idle_stamp = this_rq->clock;
3594
3595 if (this_rq->avg_idle < sysctl_sched_migration_cost)
3596 return;
3597
Peter Zijlstraf492e122009-12-23 15:29:42 +01003598 /*
3599 * Drop the rq->lock, but keep IRQ/preempt disabled.
3600 */
3601 raw_spin_unlock(&this_rq->lock);
3602
Paul Turnerc66eaf62010-11-15 15:47:07 -08003603 update_shares(this_cpu);
Peter Zijlstradce840a2011-04-07 14:09:50 +02003604 rcu_read_lock();
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003605 for_each_domain(this_cpu, sd) {
3606 unsigned long interval;
Peter Zijlstraf492e122009-12-23 15:29:42 +01003607 int balance = 1;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003608
3609 if (!(sd->flags & SD_LOAD_BALANCE))
3610 continue;
3611
Peter Zijlstraf492e122009-12-23 15:29:42 +01003612 if (sd->flags & SD_BALANCE_NEWIDLE) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003613 /* If we've pulled tasks over stop searching: */
Peter Zijlstraf492e122009-12-23 15:29:42 +01003614 pulled_task = load_balance(this_cpu, this_rq,
3615 sd, CPU_NEWLY_IDLE, &balance);
3616 }
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003617
3618 interval = msecs_to_jiffies(sd->balance_interval);
3619 if (time_after(next_balance, sd->last_balance + interval))
3620 next_balance = sd->last_balance + interval;
Nikhil Raod5ad1402010-11-17 11:42:04 -08003621 if (pulled_task) {
3622 this_rq->idle_stamp = 0;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003623 break;
Nikhil Raod5ad1402010-11-17 11:42:04 -08003624 }
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003625 }
Peter Zijlstradce840a2011-04-07 14:09:50 +02003626 rcu_read_unlock();
Peter Zijlstraf492e122009-12-23 15:29:42 +01003627
3628 raw_spin_lock(&this_rq->lock);
3629
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003630 if (pulled_task || time_after(jiffies, this_rq->next_balance)) {
3631 /*
3632 * We are going idle. next_balance may be set based on
3633 * a busy processor. So reset next_balance.
3634 */
3635 this_rq->next_balance = next_balance;
3636 }
3637}
3638
3639/*
Tejun Heo969c7922010-05-06 18:49:21 +02003640 * active_load_balance_cpu_stop is run by cpu stopper. It pushes
3641 * running tasks off the busiest CPU onto idle CPUs. It requires at
3642 * least 1 task to be running on each physical CPU where possible, and
3643 * avoids physical / logical imbalances.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003644 */
Tejun Heo969c7922010-05-06 18:49:21 +02003645static int active_load_balance_cpu_stop(void *data)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003646{
Tejun Heo969c7922010-05-06 18:49:21 +02003647 struct rq *busiest_rq = data;
3648 int busiest_cpu = cpu_of(busiest_rq);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003649 int target_cpu = busiest_rq->push_cpu;
Tejun Heo969c7922010-05-06 18:49:21 +02003650 struct rq *target_rq = cpu_rq(target_cpu);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003651 struct sched_domain *sd;
Tejun Heo969c7922010-05-06 18:49:21 +02003652
3653 raw_spin_lock_irq(&busiest_rq->lock);
3654
3655 /* make sure the requested cpu hasn't gone down in the meantime */
3656 if (unlikely(busiest_cpu != smp_processor_id() ||
3657 !busiest_rq->active_balance))
3658 goto out_unlock;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003659
3660 /* Is there any task to move? */
3661 if (busiest_rq->nr_running <= 1)
Tejun Heo969c7922010-05-06 18:49:21 +02003662 goto out_unlock;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003663
3664 /*
3665 * This condition is "impossible", if it occurs
3666 * we need to fix it. Originally reported by
3667 * Bjorn Helgaas on a 128-cpu setup.
3668 */
3669 BUG_ON(busiest_rq == target_rq);
3670
3671 /* move a task from busiest_rq to target_rq */
3672 double_lock_balance(busiest_rq, target_rq);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003673
3674 /* Search for an sd spanning us and the target CPU. */
Peter Zijlstradce840a2011-04-07 14:09:50 +02003675 rcu_read_lock();
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003676 for_each_domain(target_cpu, sd) {
3677 if ((sd->flags & SD_LOAD_BALANCE) &&
3678 cpumask_test_cpu(busiest_cpu, sched_domain_span(sd)))
3679 break;
3680 }
3681
3682 if (likely(sd)) {
3683 schedstat_inc(sd, alb_count);
3684
3685 if (move_one_task(target_rq, target_cpu, busiest_rq,
3686 sd, CPU_IDLE))
3687 schedstat_inc(sd, alb_pushed);
3688 else
3689 schedstat_inc(sd, alb_failed);
3690 }
Peter Zijlstradce840a2011-04-07 14:09:50 +02003691 rcu_read_unlock();
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003692 double_unlock_balance(busiest_rq, target_rq);
Tejun Heo969c7922010-05-06 18:49:21 +02003693out_unlock:
3694 busiest_rq->active_balance = 0;
3695 raw_spin_unlock_irq(&busiest_rq->lock);
3696 return 0;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003697}
3698
3699#ifdef CONFIG_NO_HZ
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003700
3701static DEFINE_PER_CPU(struct call_single_data, remote_sched_softirq_cb);
3702
3703static void trigger_sched_softirq(void *data)
3704{
3705 raise_softirq_irqoff(SCHED_SOFTIRQ);
3706}
3707
3708static inline void init_sched_softirq_csd(struct call_single_data *csd)
3709{
3710 csd->func = trigger_sched_softirq;
3711 csd->info = NULL;
3712 csd->flags = 0;
3713 csd->priv = 0;
3714}
3715
3716/*
3717 * idle load balancing details
3718 * - One of the idle CPUs nominates itself as idle load_balancer, while
3719 * entering idle.
3720 * - This idle load balancer CPU will also go into tickless mode when
3721 * it is idle, just like all other idle CPUs
3722 * - When one of the busy CPUs notice that there may be an idle rebalancing
3723 * needed, they will kick the idle load balancer, which then does idle
3724 * load balancing for all the idle CPUs.
3725 */
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003726static struct {
3727 atomic_t load_balancer;
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003728 atomic_t first_pick_cpu;
3729 atomic_t second_pick_cpu;
3730 cpumask_var_t idle_cpus_mask;
3731 cpumask_var_t grp_idle_mask;
3732 unsigned long next_balance; /* in jiffy units */
3733} nohz ____cacheline_aligned;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003734
3735int get_nohz_load_balancer(void)
3736{
3737 return atomic_read(&nohz.load_balancer);
3738}
3739
3740#if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
3741/**
3742 * lowest_flag_domain - Return lowest sched_domain containing flag.
3743 * @cpu: The cpu whose lowest level of sched domain is to
3744 * be returned.
3745 * @flag: The flag to check for the lowest sched_domain
3746 * for the given cpu.
3747 *
3748 * Returns the lowest sched_domain of a cpu which contains the given flag.
3749 */
3750static inline struct sched_domain *lowest_flag_domain(int cpu, int flag)
3751{
3752 struct sched_domain *sd;
3753
3754 for_each_domain(cpu, sd)
Hillf Danton08354712011-06-16 21:55:19 -04003755 if (sd->flags & flag)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003756 break;
3757
3758 return sd;
3759}
3760
3761/**
3762 * for_each_flag_domain - Iterates over sched_domains containing the flag.
3763 * @cpu: The cpu whose domains we're iterating over.
3764 * @sd: variable holding the value of the power_savings_sd
3765 * for cpu.
3766 * @flag: The flag to filter the sched_domains to be iterated.
3767 *
3768 * Iterates over all the scheduler domains for a given cpu that has the 'flag'
3769 * set, starting from the lowest sched_domain to the highest.
3770 */
3771#define for_each_flag_domain(cpu, sd, flag) \
3772 for (sd = lowest_flag_domain(cpu, flag); \
3773 (sd && (sd->flags & flag)); sd = sd->parent)
3774
3775/**
3776 * is_semi_idle_group - Checks if the given sched_group is semi-idle.
3777 * @ilb_group: group to be checked for semi-idleness
3778 *
3779 * Returns: 1 if the group is semi-idle. 0 otherwise.
3780 *
3781 * We define a sched_group to be semi idle if it has atleast one idle-CPU
3782 * and atleast one non-idle CPU. This helper function checks if the given
3783 * sched_group is semi-idle or not.
3784 */
3785static inline int is_semi_idle_group(struct sched_group *ilb_group)
3786{
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003787 cpumask_and(nohz.grp_idle_mask, nohz.idle_cpus_mask,
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003788 sched_group_cpus(ilb_group));
3789
3790 /*
3791 * A sched_group is semi-idle when it has atleast one busy cpu
3792 * and atleast one idle cpu.
3793 */
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003794 if (cpumask_empty(nohz.grp_idle_mask))
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003795 return 0;
3796
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003797 if (cpumask_equal(nohz.grp_idle_mask, sched_group_cpus(ilb_group)))
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003798 return 0;
3799
3800 return 1;
3801}
3802/**
3803 * find_new_ilb - Finds the optimum idle load balancer for nomination.
3804 * @cpu: The cpu which is nominating a new idle_load_balancer.
3805 *
3806 * Returns: Returns the id of the idle load balancer if it exists,
3807 * Else, returns >= nr_cpu_ids.
3808 *
3809 * This algorithm picks the idle load balancer such that it belongs to a
3810 * semi-idle powersavings sched_domain. The idea is to try and avoid
3811 * completely idle packages/cores just for the purpose of idle load balancing
3812 * when there are other idle cpu's which are better suited for that job.
3813 */
3814static int find_new_ilb(int cpu)
3815{
3816 struct sched_domain *sd;
3817 struct sched_group *ilb_group;
Peter Zijlstradce840a2011-04-07 14:09:50 +02003818 int ilb = nr_cpu_ids;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003819
3820 /*
3821 * Have idle load balancer selection from semi-idle packages only
3822 * when power-aware load balancing is enabled
3823 */
3824 if (!(sched_smt_power_savings || sched_mc_power_savings))
3825 goto out_done;
3826
3827 /*
3828 * Optimize for the case when we have no idle CPUs or only one
3829 * idle CPU. Don't walk the sched_domain hierarchy in such cases
3830 */
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003831 if (cpumask_weight(nohz.idle_cpus_mask) < 2)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003832 goto out_done;
3833
Peter Zijlstradce840a2011-04-07 14:09:50 +02003834 rcu_read_lock();
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003835 for_each_flag_domain(cpu, sd, SD_POWERSAVINGS_BALANCE) {
3836 ilb_group = sd->groups;
3837
3838 do {
Peter Zijlstradce840a2011-04-07 14:09:50 +02003839 if (is_semi_idle_group(ilb_group)) {
3840 ilb = cpumask_first(nohz.grp_idle_mask);
3841 goto unlock;
3842 }
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003843
3844 ilb_group = ilb_group->next;
3845
3846 } while (ilb_group != sd->groups);
3847 }
Peter Zijlstradce840a2011-04-07 14:09:50 +02003848unlock:
3849 rcu_read_unlock();
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003850
3851out_done:
Peter Zijlstradce840a2011-04-07 14:09:50 +02003852 return ilb;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003853}
3854#else /* (CONFIG_SCHED_MC || CONFIG_SCHED_SMT) */
3855static inline int find_new_ilb(int call_cpu)
3856{
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003857 return nr_cpu_ids;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003858}
3859#endif
3860
3861/*
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003862 * Kick a CPU to do the nohz balancing, if it is time for it. We pick the
3863 * nohz_load_balancer CPU (if there is one) otherwise fallback to any idle
3864 * CPU (if there is one).
3865 */
3866static void nohz_balancer_kick(int cpu)
3867{
3868 int ilb_cpu;
3869
3870 nohz.next_balance++;
3871
3872 ilb_cpu = get_nohz_load_balancer();
3873
3874 if (ilb_cpu >= nr_cpu_ids) {
3875 ilb_cpu = cpumask_first(nohz.idle_cpus_mask);
3876 if (ilb_cpu >= nr_cpu_ids)
3877 return;
3878 }
3879
3880 if (!cpu_rq(ilb_cpu)->nohz_balance_kick) {
3881 struct call_single_data *cp;
3882
3883 cpu_rq(ilb_cpu)->nohz_balance_kick = 1;
3884 cp = &per_cpu(remote_sched_softirq_cb, cpu);
3885 __smp_call_function_single(ilb_cpu, cp, 0);
3886 }
3887 return;
3888}
3889
3890/*
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003891 * This routine will try to nominate the ilb (idle load balancing)
3892 * owner among the cpus whose ticks are stopped. ilb owner will do the idle
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003893 * load balancing on behalf of all those cpus.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003894 *
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003895 * When the ilb owner becomes busy, we will not have new ilb owner until some
3896 * idle CPU wakes up and goes back to idle or some busy CPU tries to kick
3897 * idle load balancing by kicking one of the idle CPUs.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003898 *
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003899 * Ticks are stopped for the ilb owner as well, with busy CPU kicking this
3900 * ilb owner CPU in future (when there is a need for idle load balancing on
3901 * behalf of all idle CPUs).
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003902 */
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003903void select_nohz_load_balancer(int stop_tick)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003904{
3905 int cpu = smp_processor_id();
3906
3907 if (stop_tick) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003908 if (!cpu_active(cpu)) {
3909 if (atomic_read(&nohz.load_balancer) != cpu)
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003910 return;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003911
3912 /*
3913 * If we are going offline and still the leader,
3914 * give up!
3915 */
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003916 if (atomic_cmpxchg(&nohz.load_balancer, cpu,
3917 nr_cpu_ids) != cpu)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003918 BUG();
3919
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003920 return;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003921 }
3922
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003923 cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003924
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003925 if (atomic_read(&nohz.first_pick_cpu) == cpu)
3926 atomic_cmpxchg(&nohz.first_pick_cpu, cpu, nr_cpu_ids);
3927 if (atomic_read(&nohz.second_pick_cpu) == cpu)
3928 atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003929
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003930 if (atomic_read(&nohz.load_balancer) >= nr_cpu_ids) {
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003931 int new_ilb;
3932
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003933 /* make me the ilb owner */
3934 if (atomic_cmpxchg(&nohz.load_balancer, nr_cpu_ids,
3935 cpu) != nr_cpu_ids)
3936 return;
3937
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003938 /*
3939 * Check to see if there is a more power-efficient
3940 * ilb.
3941 */
3942 new_ilb = find_new_ilb(cpu);
3943 if (new_ilb < nr_cpu_ids && new_ilb != cpu) {
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003944 atomic_set(&nohz.load_balancer, nr_cpu_ids);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003945 resched_cpu(new_ilb);
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003946 return;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003947 }
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003948 return;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003949 }
3950 } else {
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003951 if (!cpumask_test_cpu(cpu, nohz.idle_cpus_mask))
3952 return;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003953
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003954 cpumask_clear_cpu(cpu, nohz.idle_cpus_mask);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003955
3956 if (atomic_read(&nohz.load_balancer) == cpu)
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003957 if (atomic_cmpxchg(&nohz.load_balancer, cpu,
3958 nr_cpu_ids) != cpu)
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003959 BUG();
3960 }
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07003961 return;
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003962}
3963#endif
3964
3965static DEFINE_SPINLOCK(balancing);
3966
Peter Zijlstra49c022e2011-04-05 10:14:25 +02003967static unsigned long __read_mostly max_load_balance_interval = HZ/10;
3968
3969/*
3970 * Scale the max load_balance interval with the number of CPUs in the system.
3971 * This trades load-balance latency on larger machines for less cross talk.
3972 */
3973static void update_max_interval(void)
3974{
3975 max_load_balance_interval = HZ*num_online_cpus()/10;
3976}
3977
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003978/*
3979 * It checks each scheduling domain to see if it is due to be balanced,
3980 * and initiates a balancing operation if so.
3981 *
3982 * Balancing parameters are set up in arch_init_sched_domains.
3983 */
3984static void rebalance_domains(int cpu, enum cpu_idle_type idle)
3985{
3986 int balance = 1;
3987 struct rq *rq = cpu_rq(cpu);
3988 unsigned long interval;
3989 struct sched_domain *sd;
3990 /* Earliest time when we have to do rebalance again */
3991 unsigned long next_balance = jiffies + 60*HZ;
3992 int update_next_balance = 0;
3993 int need_serialize;
3994
Peter Zijlstra2069dd72010-11-15 15:47:00 -08003995 update_shares(cpu);
3996
Peter Zijlstradce840a2011-04-07 14:09:50 +02003997 rcu_read_lock();
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01003998 for_each_domain(cpu, sd) {
3999 if (!(sd->flags & SD_LOAD_BALANCE))
4000 continue;
4001
4002 interval = sd->balance_interval;
4003 if (idle != CPU_IDLE)
4004 interval *= sd->busy_factor;
4005
4006 /* scale ms to jiffies */
4007 interval = msecs_to_jiffies(interval);
Peter Zijlstra49c022e2011-04-05 10:14:25 +02004008 interval = clamp(interval, 1UL, max_load_balance_interval);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004009
4010 need_serialize = sd->flags & SD_SERIALIZE;
4011
4012 if (need_serialize) {
4013 if (!spin_trylock(&balancing))
4014 goto out;
4015 }
4016
4017 if (time_after_eq(jiffies, sd->last_balance + interval)) {
4018 if (load_balance(cpu, rq, sd, idle, &balance)) {
4019 /*
4020 * We've pulled tasks over so either we're no
Peter Zijlstrac186faf2011-02-21 18:52:53 +01004021 * longer idle.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004022 */
4023 idle = CPU_NOT_IDLE;
4024 }
4025 sd->last_balance = jiffies;
4026 }
4027 if (need_serialize)
4028 spin_unlock(&balancing);
4029out:
4030 if (time_after(next_balance, sd->last_balance + interval)) {
4031 next_balance = sd->last_balance + interval;
4032 update_next_balance = 1;
4033 }
4034
4035 /*
4036 * Stop the load balance at this level. There is another
4037 * CPU in our sched group which is doing load balancing more
4038 * actively.
4039 */
4040 if (!balance)
4041 break;
4042 }
Peter Zijlstradce840a2011-04-07 14:09:50 +02004043 rcu_read_unlock();
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004044
4045 /*
4046 * next_balance will be updated only when there is a need.
4047 * When the cpu is attached to null domain for ex, it will not be
4048 * updated.
4049 */
4050 if (likely(update_next_balance))
4051 rq->next_balance = next_balance;
4052}
4053
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07004054#ifdef CONFIG_NO_HZ
4055/*
4056 * In CONFIG_NO_HZ case, the idle balance kickee will do the
4057 * rebalancing for all the cpus for whom scheduler ticks are stopped.
4058 */
4059static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle)
4060{
4061 struct rq *this_rq = cpu_rq(this_cpu);
4062 struct rq *rq;
4063 int balance_cpu;
4064
4065 if (idle != CPU_IDLE || !this_rq->nohz_balance_kick)
4066 return;
4067
4068 for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
4069 if (balance_cpu == this_cpu)
4070 continue;
4071
4072 /*
4073 * If this cpu gets work to do, stop the load balancing
4074 * work being done for other cpus. Next load
4075 * balancing owner will pick it up.
4076 */
4077 if (need_resched()) {
4078 this_rq->nohz_balance_kick = 0;
4079 break;
4080 }
4081
4082 raw_spin_lock_irq(&this_rq->lock);
Suresh Siddha5343bdb2010-07-09 15:19:54 +02004083 update_rq_clock(this_rq);
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07004084 update_cpu_load(this_rq);
4085 raw_spin_unlock_irq(&this_rq->lock);
4086
4087 rebalance_domains(balance_cpu, CPU_IDLE);
4088
4089 rq = cpu_rq(balance_cpu);
4090 if (time_after(this_rq->next_balance, rq->next_balance))
4091 this_rq->next_balance = rq->next_balance;
4092 }
4093 nohz.next_balance = this_rq->next_balance;
4094 this_rq->nohz_balance_kick = 0;
4095}
4096
4097/*
4098 * Current heuristic for kicking the idle load balancer
4099 * - first_pick_cpu is the one of the busy CPUs. It will kick
4100 * idle load balancer when it has more than one process active. This
4101 * eliminates the need for idle load balancing altogether when we have
4102 * only one running process in the system (common case).
4103 * - If there are more than one busy CPU, idle load balancer may have
4104 * to run for active_load_balance to happen (i.e., two busy CPUs are
4105 * SMT or core siblings and can run better if they move to different
4106 * physical CPUs). So, second_pick_cpu is the second of the busy CPUs
4107 * which will kick idle load balancer as soon as it has any load.
4108 */
4109static inline int nohz_kick_needed(struct rq *rq, int cpu)
4110{
4111 unsigned long now = jiffies;
4112 int ret;
4113 int first_pick_cpu, second_pick_cpu;
4114
4115 if (time_before(now, nohz.next_balance))
4116 return 0;
4117
Suresh Siddhaf6c3f162010-09-13 11:02:21 -07004118 if (rq->idle_at_tick)
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07004119 return 0;
4120
4121 first_pick_cpu = atomic_read(&nohz.first_pick_cpu);
4122 second_pick_cpu = atomic_read(&nohz.second_pick_cpu);
4123
4124 if (first_pick_cpu < nr_cpu_ids && first_pick_cpu != cpu &&
4125 second_pick_cpu < nr_cpu_ids && second_pick_cpu != cpu)
4126 return 0;
4127
4128 ret = atomic_cmpxchg(&nohz.first_pick_cpu, nr_cpu_ids, cpu);
4129 if (ret == nr_cpu_ids || ret == cpu) {
4130 atomic_cmpxchg(&nohz.second_pick_cpu, cpu, nr_cpu_ids);
4131 if (rq->nr_running > 1)
4132 return 1;
4133 } else {
4134 ret = atomic_cmpxchg(&nohz.second_pick_cpu, nr_cpu_ids, cpu);
4135 if (ret == nr_cpu_ids || ret == cpu) {
4136 if (rq->nr_running)
4137 return 1;
4138 }
4139 }
4140 return 0;
4141}
4142#else
4143static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle) { }
4144#endif
4145
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004146/*
4147 * run_rebalance_domains is triggered when needed from the scheduler tick.
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07004148 * Also triggered for nohz idle balancing (with nohz_balancing_kick set).
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004149 */
4150static void run_rebalance_domains(struct softirq_action *h)
4151{
4152 int this_cpu = smp_processor_id();
4153 struct rq *this_rq = cpu_rq(this_cpu);
4154 enum cpu_idle_type idle = this_rq->idle_at_tick ?
4155 CPU_IDLE : CPU_NOT_IDLE;
4156
4157 rebalance_domains(this_cpu, idle);
4158
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004159 /*
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07004160 * If this cpu has a pending nohz_balance_kick, then do the
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004161 * balancing on behalf of the other idle cpus whose ticks are
4162 * stopped.
4163 */
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07004164 nohz_idle_balance(this_cpu, idle);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004165}
4166
4167static inline int on_null_domain(int cpu)
4168{
Paul E. McKenney90a65012010-02-28 08:32:18 -08004169 return !rcu_dereference_sched(cpu_rq(cpu)->sd);
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004170}
4171
4172/*
4173 * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing.
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004174 */
4175static inline void trigger_load_balance(struct rq *rq, int cpu)
4176{
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004177 /* Don't need to rebalance while attached to NULL domain */
4178 if (time_after_eq(jiffies, rq->next_balance) &&
4179 likely(!on_null_domain(cpu)))
4180 raise_softirq(SCHED_SOFTIRQ);
Venkatesh Pallipadi83cd4fe2010-05-21 17:09:41 -07004181#ifdef CONFIG_NO_HZ
4182 else if (nohz_kick_needed(rq, cpu) && likely(!on_null_domain(cpu)))
4183 nohz_balancer_kick(cpu);
4184#endif
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004185}
4186
Christian Ehrhardt0bcdcf22009-11-30 12:16:46 +01004187static void rq_online_fair(struct rq *rq)
4188{
4189 update_sysctl();
4190}
4191
4192static void rq_offline_fair(struct rq *rq)
4193{
4194 update_sysctl();
4195}
4196
Peter Zijlstra1e3c88b2009-12-17 17:00:43 +01004197#else /* CONFIG_SMP */
4198
4199/*
4200 * on UP we do not need to balance between CPUs:
4201 */
4202static inline void idle_balance(int cpu, struct rq *rq)
4203{
4204}
4205
Dhaval Giani55e12e52008-06-24 23:39:43 +05304206#endif /* CONFIG_SMP */
Peter Williamse1d14842007-10-24 18:23:51 +02004207
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004208/*
4209 * scheduler tick hitting a task of our scheduling class:
4210 */
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01004211static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004212{
4213 struct cfs_rq *cfs_rq;
4214 struct sched_entity *se = &curr->se;
4215
4216 for_each_sched_entity(se) {
4217 cfs_rq = cfs_rq_of(se);
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01004218 entity_tick(cfs_rq, se, queued);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004219 }
4220}
4221
4222/*
Peter Zijlstracd29fe62009-11-27 17:32:46 +01004223 * called on fork with the child task as argument from the parent's context
4224 * - child not yet on the tasklist
4225 * - preemption disabled
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004226 */
Peter Zijlstracd29fe62009-11-27 17:32:46 +01004227static void task_fork_fair(struct task_struct *p)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004228{
Peter Zijlstracd29fe62009-11-27 17:32:46 +01004229 struct cfs_rq *cfs_rq = task_cfs_rq(current);
Ingo Molnar429d43b2007-10-15 17:00:03 +02004230 struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
Ingo Molnar00bf7bf2007-10-15 17:00:14 +02004231 int this_cpu = smp_processor_id();
Peter Zijlstracd29fe62009-11-27 17:32:46 +01004232 struct rq *rq = this_rq();
4233 unsigned long flags;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004234
Thomas Gleixner05fa7852009-11-17 14:28:38 +01004235 raw_spin_lock_irqsave(&rq->lock, flags);
Peter Zijlstracd29fe62009-11-27 17:32:46 +01004236
Peter Zijlstra861d0342010-08-19 13:31:43 +02004237 update_rq_clock(rq);
4238
Paul E. McKenneyb0a0f662010-10-06 17:32:51 -07004239 if (unlikely(task_cpu(p) != this_cpu)) {
4240 rcu_read_lock();
Peter Zijlstracd29fe62009-11-27 17:32:46 +01004241 __set_task_cpu(p, this_cpu);
Paul E. McKenneyb0a0f662010-10-06 17:32:51 -07004242 rcu_read_unlock();
4243 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004244
Ting Yang7109c442007-08-28 12:53:24 +02004245 update_curr(cfs_rq);
Peter Zijlstracd29fe62009-11-27 17:32:46 +01004246
Mike Galbraithb5d9d732009-09-08 11:12:28 +02004247 if (curr)
4248 se->vruntime = curr->vruntime;
Peter Zijlstraaeb73b02007-10-15 17:00:05 +02004249 place_entity(cfs_rq, se, 1);
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02004250
Peter Zijlstracd29fe62009-11-27 17:32:46 +01004251 if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
Dmitry Adamushko87fefa32007-10-15 17:00:08 +02004252 /*
Ingo Molnaredcb60a2007-10-15 17:00:08 +02004253 * Upon rescheduling, sched_class::put_prev_task() will place
4254 * 'current' within the tree based on its new key value.
4255 */
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02004256 swap(curr->vruntime, se->vruntime);
Bharata B Raoaec0a512008-08-28 14:42:49 +05304257 resched_task(rq->curr);
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02004258 }
4259
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01004260 se->vruntime -= cfs_rq->min_vruntime;
4261
Thomas Gleixner05fa7852009-11-17 14:28:38 +01004262 raw_spin_unlock_irqrestore(&rq->lock, flags);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004263}
4264
Steven Rostedtcb469842008-01-25 21:08:22 +01004265/*
4266 * Priority of the task has changed. Check to see if we preempt
4267 * the current task.
4268 */
Peter Zijlstrada7a7352011-01-17 17:03:27 +01004269static void
4270prio_changed_fair(struct rq *rq, struct task_struct *p, int oldprio)
Steven Rostedtcb469842008-01-25 21:08:22 +01004271{
Peter Zijlstrada7a7352011-01-17 17:03:27 +01004272 if (!p->se.on_rq)
4273 return;
4274
Steven Rostedtcb469842008-01-25 21:08:22 +01004275 /*
4276 * Reschedule if we are currently running on this runqueue and
4277 * our priority decreased, or if we are not currently running on
4278 * this runqueue and our priority is higher than the current's
4279 */
Peter Zijlstrada7a7352011-01-17 17:03:27 +01004280 if (rq->curr == p) {
Steven Rostedtcb469842008-01-25 21:08:22 +01004281 if (p->prio > oldprio)
4282 resched_task(rq->curr);
4283 } else
Peter Zijlstra15afe092008-09-20 23:38:02 +02004284 check_preempt_curr(rq, p, 0);
Steven Rostedtcb469842008-01-25 21:08:22 +01004285}
4286
Peter Zijlstrada7a7352011-01-17 17:03:27 +01004287static void switched_from_fair(struct rq *rq, struct task_struct *p)
4288{
4289 struct sched_entity *se = &p->se;
4290 struct cfs_rq *cfs_rq = cfs_rq_of(se);
4291
4292 /*
4293 * Ensure the task's vruntime is normalized, so that when its
4294 * switched back to the fair class the enqueue_entity(.flags=0) will
4295 * do the right thing.
4296 *
4297 * If it was on_rq, then the dequeue_entity(.flags=0) will already
4298 * have normalized the vruntime, if it was !on_rq, then only when
4299 * the task is sleeping will it still have non-normalized vruntime.
4300 */
4301 if (!se->on_rq && p->state != TASK_RUNNING) {
4302 /*
4303 * Fix up our vruntime so that the current sleep doesn't
4304 * cause 'unlimited' sleep bonus.
4305 */
4306 place_entity(cfs_rq, se, 0);
4307 se->vruntime -= cfs_rq->min_vruntime;
4308 }
4309}
4310
Steven Rostedtcb469842008-01-25 21:08:22 +01004311/*
4312 * We switched to the sched_fair class.
4313 */
Peter Zijlstrada7a7352011-01-17 17:03:27 +01004314static void switched_to_fair(struct rq *rq, struct task_struct *p)
Steven Rostedtcb469842008-01-25 21:08:22 +01004315{
Peter Zijlstrada7a7352011-01-17 17:03:27 +01004316 if (!p->se.on_rq)
4317 return;
4318
Steven Rostedtcb469842008-01-25 21:08:22 +01004319 /*
4320 * We were most likely switched from sched_rt, so
4321 * kick off the schedule if running, otherwise just see
4322 * if we can still preempt the current task.
4323 */
Peter Zijlstrada7a7352011-01-17 17:03:27 +01004324 if (rq->curr == p)
Steven Rostedtcb469842008-01-25 21:08:22 +01004325 resched_task(rq->curr);
4326 else
Peter Zijlstra15afe092008-09-20 23:38:02 +02004327 check_preempt_curr(rq, p, 0);
Steven Rostedtcb469842008-01-25 21:08:22 +01004328}
4329
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02004330/* Account for a task changing its policy or group.
4331 *
4332 * This routine is mostly called to set cfs_rq->curr field when a task
4333 * migrates between groups/classes.
4334 */
4335static void set_curr_task_fair(struct rq *rq)
4336{
4337 struct sched_entity *se = &rq->curr->se;
4338
Paul Turnerec12cb72011-07-21 09:43:30 -07004339 for_each_sched_entity(se) {
4340 struct cfs_rq *cfs_rq = cfs_rq_of(se);
4341
4342 set_next_entity(cfs_rq, se);
4343 /* ensure bandwidth has been allocated on our new cfs_rq */
4344 account_cfs_rq_runtime(cfs_rq, 0);
4345 }
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02004346}
4347
Peter Zijlstra810b3812008-02-29 15:21:01 -05004348#ifdef CONFIG_FAIR_GROUP_SCHED
Peter Zijlstrab2b5ce02010-10-15 15:24:15 +02004349static void task_move_group_fair(struct task_struct *p, int on_rq)
Peter Zijlstra810b3812008-02-29 15:21:01 -05004350{
Peter Zijlstrab2b5ce02010-10-15 15:24:15 +02004351 /*
4352 * If the task was not on the rq at the time of this cgroup movement
4353 * it must have been asleep, sleeping tasks keep their ->vruntime
4354 * absolute on their old rq until wakeup (needed for the fair sleeper
4355 * bonus in place_entity()).
4356 *
4357 * If it was on the rq, we've just 'preempted' it, which does convert
4358 * ->vruntime to a relative base.
4359 *
4360 * Make sure both cases convert their relative position when migrating
4361 * to another cgroup's rq. This does somewhat interfere with the
4362 * fair sleeper stuff for the first placement, but who cares.
4363 */
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01004364 if (!on_rq)
Peter Zijlstrab2b5ce02010-10-15 15:24:15 +02004365 p->se.vruntime -= cfs_rq_of(&p->se)->min_vruntime;
4366 set_task_rq(p, task_cpu(p));
4367 if (!on_rq)
4368 p->se.vruntime += cfs_rq_of(&p->se)->min_vruntime;
Peter Zijlstra810b3812008-02-29 15:21:01 -05004369}
4370#endif
4371
H Hartley Sweeten6d686f42010-01-13 20:21:52 -07004372static unsigned int get_rr_interval_fair(struct rq *rq, struct task_struct *task)
Peter Williams0d721ce2009-09-21 01:31:53 +00004373{
4374 struct sched_entity *se = &task->se;
Peter Williams0d721ce2009-09-21 01:31:53 +00004375 unsigned int rr_interval = 0;
4376
4377 /*
4378 * Time slice is 0 for SCHED_OTHER tasks that are on an otherwise
4379 * idle runqueue:
4380 */
Peter Williams0d721ce2009-09-21 01:31:53 +00004381 if (rq->cfs.load.weight)
4382 rr_interval = NS_TO_JIFFIES(sched_slice(&rq->cfs, se));
Peter Williams0d721ce2009-09-21 01:31:53 +00004383
4384 return rr_interval;
4385}
4386
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004387/*
4388 * All the scheduling class methods:
4389 */
Ingo Molnar5522d5d2007-10-15 17:00:12 +02004390static const struct sched_class fair_sched_class = {
4391 .next = &idle_sched_class,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004392 .enqueue_task = enqueue_task_fair,
4393 .dequeue_task = dequeue_task_fair,
4394 .yield_task = yield_task_fair,
Mike Galbraithd95f4122011-02-01 09:50:51 -05004395 .yield_to_task = yield_to_task_fair,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004396
Ingo Molnar2e09bf52007-10-15 17:00:05 +02004397 .check_preempt_curr = check_preempt_wakeup,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004398
4399 .pick_next_task = pick_next_task_fair,
4400 .put_prev_task = put_prev_task_fair,
4401
Peter Williams681f3e62007-10-24 18:23:51 +02004402#ifdef CONFIG_SMP
Li Zefan4ce72a22008-10-22 15:25:26 +08004403 .select_task_rq = select_task_rq_fair,
4404
Christian Ehrhardt0bcdcf22009-11-30 12:16:46 +01004405 .rq_online = rq_online_fair,
4406 .rq_offline = rq_offline_fair,
Peter Zijlstra88ec22d2009-12-16 18:04:41 +01004407
4408 .task_waking = task_waking_fair,
Peter Williams681f3e62007-10-24 18:23:51 +02004409#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004410
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02004411 .set_curr_task = set_curr_task_fair,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004412 .task_tick = task_tick_fair,
Peter Zijlstracd29fe62009-11-27 17:32:46 +01004413 .task_fork = task_fork_fair,
Steven Rostedtcb469842008-01-25 21:08:22 +01004414
4415 .prio_changed = prio_changed_fair,
Peter Zijlstrada7a7352011-01-17 17:03:27 +01004416 .switched_from = switched_from_fair,
Steven Rostedtcb469842008-01-25 21:08:22 +01004417 .switched_to = switched_to_fair,
Peter Zijlstra810b3812008-02-29 15:21:01 -05004418
Peter Williams0d721ce2009-09-21 01:31:53 +00004419 .get_rr_interval = get_rr_interval_fair,
4420
Peter Zijlstra810b3812008-02-29 15:21:01 -05004421#ifdef CONFIG_FAIR_GROUP_SCHED
Peter Zijlstrab2b5ce02010-10-15 15:24:15 +02004422 .task_move_group = task_move_group_fair,
Peter Zijlstra810b3812008-02-29 15:21:01 -05004423#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004424};
4425
4426#ifdef CONFIG_SCHED_DEBUG
Ingo Molnar5cef9ec2007-08-09 11:16:47 +02004427static void print_cfs_stats(struct seq_file *m, int cpu)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004428{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004429 struct cfs_rq *cfs_rq;
4430
Peter Zijlstra5973e5b2008-01-25 21:08:34 +01004431 rcu_read_lock();
Ingo Molnarc3b64f12007-08-09 11:16:51 +02004432 for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
Ingo Molnar5cef9ec2007-08-09 11:16:47 +02004433 print_cfs_rq(m, cpu, cfs_rq);
Peter Zijlstra5973e5b2008-01-25 21:08:34 +01004434 rcu_read_unlock();
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02004435}
4436#endif