blob: 5bedf6e3ebf36e0ed7dc477dde9317fa3f5ec7e4 [file] [log] [blame]
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001/*
2 * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH)
3 *
4 * Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
5 *
6 * Interactivity improvements by Mike Galbraith
7 * (C) 2007 Mike Galbraith <efault@gmx.de>
8 *
9 * Various enhancements by Dmitry Adamushko.
10 * (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
11 *
12 * Group scheduling enhancements by Srivatsa Vaddagiri
13 * Copyright IBM Corporation, 2007
14 * Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
15 *
16 * Scaled math optimizations by Thomas Gleixner
17 * Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
Peter Zijlstra21805082007-08-25 18:41:53 +020018 *
19 * Adaptive scheduling granularity, math enhancements by Peter Zijlstra
20 * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020021 */
22
Arjan van de Ven97455122008-01-25 21:08:34 +010023#include <linux/latencytop.h>
Christian Ehrhardt1983a922009-11-30 12:16:47 +010024#include <linux/sched.h>
Arjan van de Ven97455122008-01-25 21:08:34 +010025
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020026/*
Peter Zijlstra21805082007-08-25 18:41:53 +020027 * Targeted preemption latency for CPU-bound tasks:
Mike Galbraith172e0822009-09-09 15:41:37 +020028 * (default: 5ms * (1 + ilog(ncpus)), units: nanoseconds)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020029 *
Peter Zijlstra21805082007-08-25 18:41:53 +020030 * NOTE: this latency value is not the same as the concept of
Ingo Molnard274a4c2007-10-15 17:00:14 +020031 * 'timeslice length' - timeslices in CFS are of variable length
32 * and have no persistent notion like in traditional, time-slice
33 * based scheduling concepts.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020034 *
Ingo Molnard274a4c2007-10-15 17:00:14 +020035 * (to see the precise effective timeslice length of your workload,
36 * run vmstat and monitor the context-switches (cs) field)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020037 */
Mike Galbraith172e0822009-09-09 15:41:37 +020038unsigned int sysctl_sched_latency = 5000000ULL;
Christian Ehrhardt0bcdcf22009-11-30 12:16:46 +010039unsigned int normalized_sysctl_sched_latency = 5000000ULL;
Ingo Molnar2bd8e6d2007-10-15 17:00:02 +020040
41/*
Christian Ehrhardt1983a922009-11-30 12:16:47 +010042 * The initial- and re-scaling of tunables is configurable
43 * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus))
44 *
45 * Options are:
46 * SCHED_TUNABLESCALING_NONE - unscaled, always *1
47 * SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus)
48 * SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus
49 */
50enum sched_tunable_scaling sysctl_sched_tunable_scaling
51 = SCHED_TUNABLESCALING_LOG;
52
53/*
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010054 * Minimal preemption granularity for CPU-bound tasks:
Mike Galbraith172e0822009-09-09 15:41:37 +020055 * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010056 */
Mike Galbraith172e0822009-09-09 15:41:37 +020057unsigned int sysctl_sched_min_granularity = 1000000ULL;
Christian Ehrhardt0bcdcf22009-11-30 12:16:46 +010058unsigned int normalized_sysctl_sched_min_granularity = 1000000ULL;
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010059
60/*
61 * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
62 */
Zou Nan hai722aab02007-11-26 21:21:49 +010063static unsigned int sched_nr_latency = 5;
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010064
65/*
Mike Galbraith2bba22c2009-09-09 15:41:37 +020066 * After fork, child runs first. If set to 0 (default) then
Ingo Molnar2bd8e6d2007-10-15 17:00:02 +020067 * parent will (try to) run first.
68 */
Mike Galbraith2bba22c2009-09-09 15:41:37 +020069unsigned int sysctl_sched_child_runs_first __read_mostly;
Peter Zijlstra21805082007-08-25 18:41:53 +020070
71/*
Ingo Molnar1799e352007-09-19 23:34:46 +020072 * sys_sched_yield() compat mode
73 *
74 * This option switches the agressive yield implementation of the
75 * old scheduler back on.
76 */
77unsigned int __read_mostly sysctl_sched_compat_yield;
78
79/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020080 * SCHED_OTHER wake-up granularity.
Mike Galbraith172e0822009-09-09 15:41:37 +020081 * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020082 *
83 * This option delays the preemption effects of decoupled workloads
84 * and reduces their over-scheduling. Synchronous workloads will still
85 * have immediate wakeup/sleep latencies.
86 */
Mike Galbraith172e0822009-09-09 15:41:37 +020087unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
Christian Ehrhardt0bcdcf22009-11-30 12:16:46 +010088unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020089
Ingo Molnarda84d962007-10-15 17:00:18 +020090const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
91
Peter Zijlstraa4c2f002008-10-17 19:27:03 +020092static const struct sched_class fair_sched_class;
93
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020094/**************************************************************
95 * CFS operations on generic schedulable entities:
96 */
97
98#ifdef CONFIG_FAIR_GROUP_SCHED
99
100/* cpu runqueue to which this cfs_rq is attached */
101static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
102{
103 return cfs_rq->rq;
104}
105
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200106/* An entity is a task if it doesn't "own" a runqueue */
107#define entity_is_task(se) (!se->my_q)
108
Peter Zijlstra8f488942009-07-24 12:25:30 +0200109static inline struct task_struct *task_of(struct sched_entity *se)
110{
111#ifdef CONFIG_SCHED_DEBUG
112 WARN_ON_ONCE(!entity_is_task(se));
113#endif
114 return container_of(se, struct task_struct, se);
115}
116
Peter Zijlstrab7581492008-04-19 19:45:00 +0200117/* Walk up scheduling entities hierarchy */
118#define for_each_sched_entity(se) \
119 for (; se; se = se->parent)
120
121static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
122{
123 return p->se.cfs_rq;
124}
125
126/* runqueue on which this entity is (to be) queued */
127static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
128{
129 return se->cfs_rq;
130}
131
132/* runqueue "owned" by this group */
133static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
134{
135 return grp->my_q;
136}
137
138/* Given a group's cfs_rq on one cpu, return its corresponding cfs_rq on
139 * another cpu ('this_cpu')
140 */
141static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
142{
143 return cfs_rq->tg->cfs_rq[this_cpu];
144}
145
146/* Iterate thr' all leaf cfs_rq's on a runqueue */
147#define for_each_leaf_cfs_rq(rq, cfs_rq) \
148 list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
149
150/* Do the two (enqueued) entities belong to the same group ? */
151static inline int
152is_same_group(struct sched_entity *se, struct sched_entity *pse)
153{
154 if (se->cfs_rq == pse->cfs_rq)
155 return 1;
156
157 return 0;
158}
159
160static inline struct sched_entity *parent_entity(struct sched_entity *se)
161{
162 return se->parent;
163}
164
Peter Zijlstra464b7522008-10-24 11:06:15 +0200165/* return depth at which a sched entity is present in the hierarchy */
166static inline int depth_se(struct sched_entity *se)
167{
168 int depth = 0;
169
170 for_each_sched_entity(se)
171 depth++;
172
173 return depth;
174}
175
176static void
177find_matching_se(struct sched_entity **se, struct sched_entity **pse)
178{
179 int se_depth, pse_depth;
180
181 /*
182 * preemption test can be made between sibling entities who are in the
183 * same cfs_rq i.e who have a common parent. Walk up the hierarchy of
184 * both tasks until we find their ancestors who are siblings of common
185 * parent.
186 */
187
188 /* First walk up until both entities are at same depth */
189 se_depth = depth_se(*se);
190 pse_depth = depth_se(*pse);
191
192 while (se_depth > pse_depth) {
193 se_depth--;
194 *se = parent_entity(*se);
195 }
196
197 while (pse_depth > se_depth) {
198 pse_depth--;
199 *pse = parent_entity(*pse);
200 }
201
202 while (!is_same_group(*se, *pse)) {
203 *se = parent_entity(*se);
204 *pse = parent_entity(*pse);
205 }
206}
207
Peter Zijlstra8f488942009-07-24 12:25:30 +0200208#else /* !CONFIG_FAIR_GROUP_SCHED */
209
210static inline struct task_struct *task_of(struct sched_entity *se)
211{
212 return container_of(se, struct task_struct, se);
213}
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200214
215static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
216{
217 return container_of(cfs_rq, struct rq, cfs);
218}
219
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200220#define entity_is_task(se) 1
221
Peter Zijlstrab7581492008-04-19 19:45:00 +0200222#define for_each_sched_entity(se) \
223 for (; se; se = NULL)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200224
Peter Zijlstrab7581492008-04-19 19:45:00 +0200225static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200226{
Peter Zijlstrab7581492008-04-19 19:45:00 +0200227 return &task_rq(p)->cfs;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200228}
229
Peter Zijlstrab7581492008-04-19 19:45:00 +0200230static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
231{
232 struct task_struct *p = task_of(se);
233 struct rq *rq = task_rq(p);
234
235 return &rq->cfs;
236}
237
238/* runqueue "owned" by this group */
239static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
240{
241 return NULL;
242}
243
244static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
245{
246 return &cpu_rq(this_cpu)->cfs;
247}
248
249#define for_each_leaf_cfs_rq(rq, cfs_rq) \
250 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
251
252static inline int
253is_same_group(struct sched_entity *se, struct sched_entity *pse)
254{
255 return 1;
256}
257
258static inline struct sched_entity *parent_entity(struct sched_entity *se)
259{
260 return NULL;
261}
262
Peter Zijlstra464b7522008-10-24 11:06:15 +0200263static inline void
264find_matching_se(struct sched_entity **se, struct sched_entity **pse)
265{
266}
267
Peter Zijlstrab7581492008-04-19 19:45:00 +0200268#endif /* CONFIG_FAIR_GROUP_SCHED */
269
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200270
271/**************************************************************
272 * Scheduling class tree data structure manipulation methods:
273 */
274
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200275static inline u64 max_vruntime(u64 min_vruntime, u64 vruntime)
Peter Zijlstra02e04312007-10-15 17:00:07 +0200276{
Peter Zijlstra368059a2007-10-15 17:00:11 +0200277 s64 delta = (s64)(vruntime - min_vruntime);
278 if (delta > 0)
Peter Zijlstra02e04312007-10-15 17:00:07 +0200279 min_vruntime = vruntime;
280
281 return min_vruntime;
282}
283
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200284static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
Peter Zijlstrab0ffd242007-10-15 17:00:12 +0200285{
286 s64 delta = (s64)(vruntime - min_vruntime);
287 if (delta < 0)
288 min_vruntime = vruntime;
289
290 return min_vruntime;
291}
292
Fabio Checconi54fdc582009-07-16 12:32:27 +0200293static inline int entity_before(struct sched_entity *a,
294 struct sched_entity *b)
295{
296 return (s64)(a->vruntime - b->vruntime) < 0;
297}
298
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200299static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
Peter Zijlstra90146232007-10-15 17:00:05 +0200300{
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200301 return se->vruntime - cfs_rq->min_vruntime;
Peter Zijlstra90146232007-10-15 17:00:05 +0200302}
303
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200304static void update_min_vruntime(struct cfs_rq *cfs_rq)
305{
306 u64 vruntime = cfs_rq->min_vruntime;
307
308 if (cfs_rq->curr)
309 vruntime = cfs_rq->curr->vruntime;
310
311 if (cfs_rq->rb_leftmost) {
312 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
313 struct sched_entity,
314 run_node);
315
Peter Zijlstrae17036d2009-01-15 14:53:39 +0100316 if (!cfs_rq->curr)
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200317 vruntime = se->vruntime;
318 else
319 vruntime = min_vruntime(vruntime, se->vruntime);
320 }
321
322 cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
323}
324
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200325/*
326 * Enqueue an entity into the rb-tree:
327 */
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200328static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200329{
330 struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
331 struct rb_node *parent = NULL;
332 struct sched_entity *entry;
Peter Zijlstra90146232007-10-15 17:00:05 +0200333 s64 key = entity_key(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200334 int leftmost = 1;
335
336 /*
337 * Find the right place in the rbtree:
338 */
339 while (*link) {
340 parent = *link;
341 entry = rb_entry(parent, struct sched_entity, run_node);
342 /*
343 * We dont care about collisions. Nodes with
344 * the same key stay together.
345 */
Peter Zijlstra90146232007-10-15 17:00:05 +0200346 if (key < entity_key(cfs_rq, entry)) {
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200347 link = &parent->rb_left;
348 } else {
349 link = &parent->rb_right;
350 leftmost = 0;
351 }
352 }
353
354 /*
355 * Maintain a cache of leftmost tree entries (it is frequently
356 * used):
357 */
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200358 if (leftmost)
Ingo Molnar57cb4992007-10-15 17:00:11 +0200359 cfs_rq->rb_leftmost = &se->run_node;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200360
361 rb_link_node(&se->run_node, parent, link);
362 rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200363}
364
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200365static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200366{
Peter Zijlstra3fe69742008-03-14 20:55:51 +0100367 if (cfs_rq->rb_leftmost == &se->run_node) {
368 struct rb_node *next_node;
Peter Zijlstra3fe69742008-03-14 20:55:51 +0100369
370 next_node = rb_next(&se->run_node);
371 cfs_rq->rb_leftmost = next_node;
Peter Zijlstra3fe69742008-03-14 20:55:51 +0100372 }
Ingo Molnare9acbff2007-10-15 17:00:04 +0200373
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200374 rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200375}
376
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200377static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
378{
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100379 struct rb_node *left = cfs_rq->rb_leftmost;
380
381 if (!left)
382 return NULL;
383
384 return rb_entry(left, struct sched_entity, run_node);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200385}
386
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100387static struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200388{
Ingo Molnar7eee3e62008-02-22 10:32:21 +0100389 struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200390
Balbir Singh70eee742008-02-22 13:25:53 +0530391 if (!last)
392 return NULL;
Ingo Molnar7eee3e62008-02-22 10:32:21 +0100393
394 return rb_entry(last, struct sched_entity, run_node);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200395}
396
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200397/**************************************************************
398 * Scheduling class statistics methods:
399 */
400
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100401#ifdef CONFIG_SCHED_DEBUG
Christian Ehrhardtacb4a842009-11-30 12:16:48 +0100402int sched_proc_update_handler(struct ctl_table *table, int write,
Alexey Dobriyan8d65af72009-09-23 15:57:19 -0700403 void __user *buffer, size_t *lenp,
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100404 loff_t *ppos)
405{
Alexey Dobriyan8d65af72009-09-23 15:57:19 -0700406 int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
Christian Ehrhardtacb4a842009-11-30 12:16:48 +0100407 int factor = get_update_sysctl_factor();
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100408
409 if (ret || !write)
410 return ret;
411
412 sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
413 sysctl_sched_min_granularity);
414
Christian Ehrhardtacb4a842009-11-30 12:16:48 +0100415#define WRT_SYSCTL(name) \
416 (normalized_sysctl_##name = sysctl_##name / (factor))
417 WRT_SYSCTL(sched_min_granularity);
418 WRT_SYSCTL(sched_latency);
419 WRT_SYSCTL(sched_wakeup_granularity);
420 WRT_SYSCTL(sched_shares_ratelimit);
421#undef WRT_SYSCTL
422
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100423 return 0;
424}
425#endif
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200426
427/*
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200428 * delta /= w
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200429 */
430static inline unsigned long
431calc_delta_fair(unsigned long delta, struct sched_entity *se)
432{
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200433 if (unlikely(se->load.weight != NICE_0_LOAD))
434 delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200435
436 return delta;
437}
438
439/*
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200440 * The idea is to set a period in which each task runs once.
441 *
442 * When there are too many tasks (sysctl_sched_nr_latency) we have to stretch
443 * this period because otherwise the slices get too small.
444 *
445 * p = (nr <= nl) ? l : l*nr/nl
446 */
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200447static u64 __sched_period(unsigned long nr_running)
448{
449 u64 period = sysctl_sched_latency;
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100450 unsigned long nr_latency = sched_nr_latency;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200451
452 if (unlikely(nr_running > nr_latency)) {
Peter Zijlstra4bf0b772008-01-25 21:08:21 +0100453 period = sysctl_sched_min_granularity;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200454 period *= nr_running;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200455 }
456
457 return period;
458}
459
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200460/*
461 * We calculate the wall-time slice from the period by taking a part
462 * proportional to the weight.
463 *
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200464 * s = p*P[w/rw]
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200465 */
Peter Zijlstra6d0f0eb2007-10-15 17:00:05 +0200466static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
Peter Zijlstra21805082007-08-25 18:41:53 +0200467{
Mike Galbraith0a582442009-01-02 12:16:42 +0100468 u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200469
Mike Galbraith0a582442009-01-02 12:16:42 +0100470 for_each_sched_entity(se) {
Lin Ming6272d682009-01-15 17:17:15 +0100471 struct load_weight *load;
Christian Engelmayer3104bf02009-06-16 10:35:12 +0200472 struct load_weight lw;
Lin Ming6272d682009-01-15 17:17:15 +0100473
474 cfs_rq = cfs_rq_of(se);
475 load = &cfs_rq->load;
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200476
Mike Galbraith0a582442009-01-02 12:16:42 +0100477 if (unlikely(!se->on_rq)) {
Christian Engelmayer3104bf02009-06-16 10:35:12 +0200478 lw = cfs_rq->load;
Mike Galbraith0a582442009-01-02 12:16:42 +0100479
480 update_load_add(&lw, se->load.weight);
481 load = &lw;
482 }
483 slice = calc_delta_mine(slice, se->load.weight, load);
484 }
485 return slice;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200486}
487
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200488/*
Peter Zijlstraac884de2008-04-19 19:45:00 +0200489 * We calculate the vruntime slice of a to be inserted task
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200490 *
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200491 * vs = s/w
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200492 */
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200493static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200494{
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200495 return calc_delta_fair(sched_slice(cfs_rq, se), se);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200496}
497
498/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200499 * Update the current task's runtime statistics. Skip current tasks that
500 * are not in our scheduling class.
501 */
502static inline void
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200503__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
504 unsigned long delta_exec)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200505{
Ingo Molnarbbdba7c2007-10-15 17:00:06 +0200506 unsigned long delta_exec_weighted;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200507
Ingo Molnar8179ca232007-08-02 17:41:40 +0200508 schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200509
510 curr->sum_exec_runtime += delta_exec;
Ingo Molnar7a62eab2007-10-15 17:00:06 +0200511 schedstat_add(cfs_rq, exec_clock, delta_exec);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200512 delta_exec_weighted = calc_delta_fair(delta_exec, curr);
Ingo Molnare9acbff2007-10-15 17:00:04 +0200513 curr->vruntime += delta_exec_weighted;
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200514 update_min_vruntime(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200515}
516
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200517static void update_curr(struct cfs_rq *cfs_rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200518{
Ingo Molnar429d43b2007-10-15 17:00:03 +0200519 struct sched_entity *curr = cfs_rq->curr;
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200520 u64 now = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200521 unsigned long delta_exec;
522
523 if (unlikely(!curr))
524 return;
525
526 /*
527 * Get the amount of time the current task was running
528 * since the last time we changed load (this cannot
529 * overflow on 32 bits):
530 */
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200531 delta_exec = (unsigned long)(now - curr->exec_start);
Peter Zijlstra34f28ec2008-12-16 08:45:31 +0100532 if (!delta_exec)
533 return;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200534
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200535 __update_curr(cfs_rq, curr, delta_exec);
536 curr->exec_start = now;
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100537
538 if (entity_is_task(curr)) {
539 struct task_struct *curtask = task_of(curr);
540
Ingo Molnarf977bb42009-09-13 18:15:54 +0200541 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100542 cpuacct_charge(curtask, delta_exec);
Frank Mayharf06febc2008-09-12 09:54:39 -0700543 account_group_exec_runtime(curtask, delta_exec);
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100544 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200545}
546
547static inline void
Ingo Molnar5870db52007-08-09 11:16:47 +0200548update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200549{
Ingo Molnard2819182007-08-09 11:16:47 +0200550 schedstat_set(se->wait_start, rq_of(cfs_rq)->clock);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200551}
552
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200553/*
554 * Task is being enqueued - update stats:
555 */
Ingo Molnard2417e52007-08-09 11:16:47 +0200556static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200557{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200558 /*
559 * Are we enqueueing a waiting task? (for current tasks
560 * a dequeue/enqueue event is a NOP)
561 */
Ingo Molnar429d43b2007-10-15 17:00:03 +0200562 if (se != cfs_rq->curr)
Ingo Molnar5870db52007-08-09 11:16:47 +0200563 update_stats_wait_start(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200564}
565
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200566static void
Ingo Molnar9ef0a962007-08-09 11:16:47 +0200567update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200568{
Ingo Molnarbbdba7c2007-10-15 17:00:06 +0200569 schedstat_set(se->wait_max, max(se->wait_max,
570 rq_of(cfs_rq)->clock - se->wait_start));
Arjan van de Ven6d082592008-01-25 21:08:35 +0100571 schedstat_set(se->wait_count, se->wait_count + 1);
572 schedstat_set(se->wait_sum, se->wait_sum +
573 rq_of(cfs_rq)->clock - se->wait_start);
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200574#ifdef CONFIG_SCHEDSTATS
575 if (entity_is_task(se)) {
576 trace_sched_stat_wait(task_of(se),
577 rq_of(cfs_rq)->clock - se->wait_start);
578 }
579#endif
Ingo Molnare1f84502009-09-10 20:52:09 +0200580 schedstat_set(se->wait_start, 0);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200581}
582
583static inline void
Ingo Molnar19b6a2e2007-08-09 11:16:48 +0200584update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200585{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200586 /*
587 * Mark the end of the wait period if dequeueing a
588 * waiting task:
589 */
Ingo Molnar429d43b2007-10-15 17:00:03 +0200590 if (se != cfs_rq->curr)
Ingo Molnar9ef0a962007-08-09 11:16:47 +0200591 update_stats_wait_end(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200592}
593
594/*
595 * We are picking a new current task - update its stats:
596 */
597static inline void
Ingo Molnar79303e92007-08-09 11:16:47 +0200598update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200599{
600 /*
601 * We are starting a new run period:
602 */
Ingo Molnard2819182007-08-09 11:16:47 +0200603 se->exec_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200604}
605
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200606/**************************************************
607 * Scheduling class queueing methods:
608 */
609
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200610#if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
611static void
612add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
613{
614 cfs_rq->task_weight += weight;
615}
616#else
617static inline void
618add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
619{
620}
621#endif
622
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200623static void
624account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
625{
626 update_load_add(&cfs_rq->load, se->load.weight);
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200627 if (!parent_entity(se))
628 inc_cpu_load(rq_of(cfs_rq), se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530629 if (entity_is_task(se)) {
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200630 add_cfs_task_weight(cfs_rq, se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530631 list_add(&se->group_node, &cfs_rq->tasks);
632 }
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200633 cfs_rq->nr_running++;
634 se->on_rq = 1;
635}
636
637static void
638account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
639{
640 update_load_sub(&cfs_rq->load, se->load.weight);
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200641 if (!parent_entity(se))
642 dec_cpu_load(rq_of(cfs_rq), se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530643 if (entity_is_task(se)) {
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200644 add_cfs_task_weight(cfs_rq, -se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530645 list_del_init(&se->group_node);
646 }
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200647 cfs_rq->nr_running--;
648 se->on_rq = 0;
649}
650
Ingo Molnar2396af62007-08-09 11:16:48 +0200651static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200652{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200653#ifdef CONFIG_SCHEDSTATS
Peter Zijlstrae4143142009-07-23 20:13:26 +0200654 struct task_struct *tsk = NULL;
655
656 if (entity_is_task(se))
657 tsk = task_of(se);
658
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200659 if (se->sleep_start) {
Ingo Molnard2819182007-08-09 11:16:47 +0200660 u64 delta = rq_of(cfs_rq)->clock - se->sleep_start;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200661
662 if ((s64)delta < 0)
663 delta = 0;
664
665 if (unlikely(delta > se->sleep_max))
666 se->sleep_max = delta;
667
668 se->sleep_start = 0;
669 se->sum_sleep_runtime += delta;
Arjan van de Ven97455122008-01-25 21:08:34 +0100670
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200671 if (tsk) {
Peter Zijlstrae4143142009-07-23 20:13:26 +0200672 account_scheduler_latency(tsk, delta >> 10, 1);
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200673 trace_sched_stat_sleep(tsk, delta);
674 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200675 }
676 if (se->block_start) {
Ingo Molnard2819182007-08-09 11:16:47 +0200677 u64 delta = rq_of(cfs_rq)->clock - se->block_start;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200678
679 if ((s64)delta < 0)
680 delta = 0;
681
682 if (unlikely(delta > se->block_max))
683 se->block_max = delta;
684
685 se->block_start = 0;
686 se->sum_sleep_runtime += delta;
Ingo Molnar30084fb2007-10-02 14:13:08 +0200687
Peter Zijlstrae4143142009-07-23 20:13:26 +0200688 if (tsk) {
Arjan van de Ven8f0dfc32009-07-20 11:26:58 -0700689 if (tsk->in_iowait) {
690 se->iowait_sum += delta;
691 se->iowait_count++;
Peter Zijlstra768d0c22009-07-23 20:13:26 +0200692 trace_sched_stat_iowait(tsk, delta);
Arjan van de Ven8f0dfc32009-07-20 11:26:58 -0700693 }
694
Peter Zijlstrae4143142009-07-23 20:13:26 +0200695 /*
696 * Blocking time is in units of nanosecs, so shift by
697 * 20 to get a milliseconds-range estimation of the
698 * amount of time that the task spent sleeping:
699 */
700 if (unlikely(prof_on == SLEEP_PROFILING)) {
701 profile_hits(SLEEP_PROFILING,
702 (void *)get_wchan(tsk),
703 delta >> 20);
704 }
705 account_scheduler_latency(tsk, delta >> 10, 0);
Ingo Molnar30084fb2007-10-02 14:13:08 +0200706 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200707 }
708#endif
709}
710
Peter Zijlstraddc97292007-10-15 17:00:10 +0200711static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
712{
713#ifdef CONFIG_SCHED_DEBUG
714 s64 d = se->vruntime - cfs_rq->min_vruntime;
715
716 if (d < 0)
717 d = -d;
718
719 if (d > 3*sysctl_sched_latency)
720 schedstat_inc(cfs_rq, nr_spread_over);
721#endif
722}
723
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200724static void
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200725place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
726{
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200727 u64 vruntime = cfs_rq->min_vruntime;
Peter Zijlstra94dfb5e2007-10-15 17:00:05 +0200728
Peter Zijlstra2cb86002007-11-09 22:39:37 +0100729 /*
730 * The 'current' period is already promised to the current tasks,
731 * however the extra weight of the new task will slow them down a
732 * little, place the new task so that it fits in the slot that
733 * stays open at the end.
734 */
Peter Zijlstra94dfb5e2007-10-15 17:00:05 +0200735 if (initial && sched_feat(START_DEBIT))
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200736 vruntime += sched_vslice(cfs_rq, se);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200737
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200738 /* sleeps up to a single latency don't count. */
739 if (!initial && sched_feat(FAIR_SLEEPERS)) {
740 unsigned long thresh = sysctl_sched_latency;
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200741
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200742 /*
743 * Convert the sleeper threshold into virtual time.
744 * SCHED_IDLE is a special sub-class. We care about
745 * fairness only relative to other SCHED_IDLE tasks,
746 * all of which have the same weight.
747 */
748 if (sched_feat(NORMALIZED_SLEEPER) && (!entity_is_task(se) ||
749 task_of(se)->policy != SCHED_IDLE))
750 thresh = calc_delta_fair(thresh, se);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200751
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200752 /*
753 * Halve their sleep time's effect, to allow
754 * for a gentler effect of sleepers:
755 */
756 if (sched_feat(GENTLE_FAIR_SLEEPERS))
757 thresh >>= 1;
Ingo Molnar51e03042009-09-16 08:54:45 +0200758
Mike Galbraitha2e7a7e2009-09-18 09:19:25 +0200759 vruntime -= thresh;
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200760 }
761
Mike Galbraithb5d9d732009-09-08 11:12:28 +0200762 /* ensure we never gain time by being placed backwards. */
763 vruntime = max_vruntime(se->vruntime, vruntime);
764
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200765 se->vruntime = vruntime;
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200766}
767
768static void
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200769enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200770{
771 /*
Dmitry Adamushkoa2a2d682007-10-15 17:00:13 +0200772 * Update run-time statistics of the 'current'.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200773 */
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200774 update_curr(cfs_rq);
Peter Zijlstraa9922412008-05-05 23:56:17 +0200775 account_entity_enqueue(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200776
Ingo Molnare9acbff2007-10-15 17:00:04 +0200777 if (wakeup) {
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200778 place_entity(cfs_rq, se, 0);
Ingo Molnar2396af62007-08-09 11:16:48 +0200779 enqueue_sleeper(cfs_rq, se);
Ingo Molnare9acbff2007-10-15 17:00:04 +0200780 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200781
Ingo Molnard2417e52007-08-09 11:16:47 +0200782 update_stats_enqueue(cfs_rq, se);
Peter Zijlstraddc97292007-10-15 17:00:10 +0200783 check_spread(cfs_rq, se);
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200784 if (se != cfs_rq->curr)
785 __enqueue_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200786}
787
Peter Zijlstraa571bbe2009-01-28 14:51:40 +0100788static void __clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
Peter Zijlstra2002c692008-11-11 11:52:33 +0100789{
Peter Zijlstrade69a802009-09-17 09:01:20 +0200790 if (!se || cfs_rq->last == se)
Peter Zijlstra2002c692008-11-11 11:52:33 +0100791 cfs_rq->last = NULL;
792
Peter Zijlstrade69a802009-09-17 09:01:20 +0200793 if (!se || cfs_rq->next == se)
Peter Zijlstra2002c692008-11-11 11:52:33 +0100794 cfs_rq->next = NULL;
795}
796
Peter Zijlstraa571bbe2009-01-28 14:51:40 +0100797static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
798{
799 for_each_sched_entity(se)
800 __clear_buddies(cfs_rq_of(se), se);
801}
802
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200803static void
Ingo Molnar525c2712007-08-09 11:16:48 +0200804dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200805{
Dmitry Adamushkoa2a2d682007-10-15 17:00:13 +0200806 /*
807 * Update run-time statistics of the 'current'.
808 */
809 update_curr(cfs_rq);
810
Ingo Molnar19b6a2e2007-08-09 11:16:48 +0200811 update_stats_dequeue(cfs_rq, se);
Dmitry Adamushkodb36cc72007-10-15 17:00:06 +0200812 if (sleep) {
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200813#ifdef CONFIG_SCHEDSTATS
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200814 if (entity_is_task(se)) {
815 struct task_struct *tsk = task_of(se);
816
817 if (tsk->state & TASK_INTERRUPTIBLE)
Ingo Molnard2819182007-08-09 11:16:47 +0200818 se->sleep_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200819 if (tsk->state & TASK_UNINTERRUPTIBLE)
Ingo Molnard2819182007-08-09 11:16:47 +0200820 se->block_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200821 }
Dmitry Adamushkodb36cc72007-10-15 17:00:06 +0200822#endif
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200823 }
824
Peter Zijlstra2002c692008-11-11 11:52:33 +0100825 clear_buddies(cfs_rq, se);
Peter Zijlstra47932412008-11-04 21:25:09 +0100826
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200827 if (se != cfs_rq->curr)
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200828 __dequeue_entity(cfs_rq, se);
829 account_entity_dequeue(cfs_rq, se);
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200830 update_min_vruntime(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200831}
832
833/*
834 * Preempt the current task with a newly woken task if needed:
835 */
Peter Zijlstra7c92e542007-09-05 14:32:49 +0200836static void
Ingo Molnar2e09bf52007-10-15 17:00:05 +0200837check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200838{
Peter Zijlstra11697832007-09-05 14:32:49 +0200839 unsigned long ideal_runtime, delta_exec;
840
Peter Zijlstra6d0f0eb2007-10-15 17:00:05 +0200841 ideal_runtime = sched_slice(cfs_rq, curr);
Peter Zijlstra11697832007-09-05 14:32:49 +0200842 delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
Mike Galbraitha9f3e2b2009-01-28 14:51:39 +0100843 if (delta_exec > ideal_runtime) {
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200844 resched_task(rq_of(cfs_rq)->curr);
Mike Galbraitha9f3e2b2009-01-28 14:51:39 +0100845 /*
846 * The current task ran long enough, ensure it doesn't get
847 * re-elected due to buddy favours.
848 */
849 clear_buddies(cfs_rq, curr);
Mike Galbraithf685cea2009-10-23 23:09:22 +0200850 return;
851 }
852
853 /*
854 * Ensure that a task that missed wakeup preemption by a
855 * narrow margin doesn't have to wait for a full slice.
856 * This also mitigates buddy induced latencies under load.
857 */
858 if (!sched_feat(WAKEUP_PREEMPT))
859 return;
860
861 if (delta_exec < sysctl_sched_min_granularity)
862 return;
863
864 if (cfs_rq->nr_running > 1) {
865 struct sched_entity *se = __pick_next_entity(cfs_rq);
866 s64 delta = curr->vruntime - se->vruntime;
867
868 if (delta > ideal_runtime)
869 resched_task(rq_of(cfs_rq)->curr);
Mike Galbraitha9f3e2b2009-01-28 14:51:39 +0100870 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200871}
872
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200873static void
Ingo Molnar8494f412007-08-09 11:16:48 +0200874set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200875{
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200876 /* 'current' is not kept within the tree. */
877 if (se->on_rq) {
878 /*
879 * Any task has to be enqueued before it get to execute on
880 * a CPU. So account for the time it spent waiting on the
881 * runqueue.
882 */
883 update_stats_wait_end(cfs_rq, se);
884 __dequeue_entity(cfs_rq, se);
885 }
886
Ingo Molnar79303e92007-08-09 11:16:47 +0200887 update_stats_curr_start(cfs_rq, se);
Ingo Molnar429d43b2007-10-15 17:00:03 +0200888 cfs_rq->curr = se;
Ingo Molnareba1ed42007-10-15 17:00:02 +0200889#ifdef CONFIG_SCHEDSTATS
890 /*
891 * Track our maximum slice length, if the CPU's load is at
892 * least twice that of our own weight (i.e. dont track it
893 * when there are only lesser-weight tasks around):
894 */
Dmitry Adamushko495eca42007-10-15 17:00:06 +0200895 if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
Ingo Molnareba1ed42007-10-15 17:00:02 +0200896 se->slice_max = max(se->slice_max,
897 se->sum_exec_runtime - se->prev_sum_exec_runtime);
898 }
899#endif
Peter Zijlstra4a55b452007-09-05 14:32:49 +0200900 se->prev_sum_exec_runtime = se->sum_exec_runtime;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200901}
902
Peter Zijlstra3f3a4902008-10-24 11:06:16 +0200903static int
904wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
905
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100906static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
Peter Zijlstraaa2ac252008-03-14 21:12:12 +0100907{
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100908 struct sched_entity *se = __pick_next_entity(cfs_rq);
Mike Galbraithf685cea2009-10-23 23:09:22 +0200909 struct sched_entity *left = se;
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100910
Mike Galbraithf685cea2009-10-23 23:09:22 +0200911 if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
912 se = cfs_rq->next;
Peter Zijlstraaa2ac252008-03-14 21:12:12 +0100913
Mike Galbraithf685cea2009-10-23 23:09:22 +0200914 /*
915 * Prefer last buddy, try to return the CPU to a preempted task.
916 */
917 if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
918 se = cfs_rq->last;
919
920 clear_buddies(cfs_rq, se);
Peter Zijlstra47932412008-11-04 21:25:09 +0100921
922 return se;
Peter Zijlstraaa2ac252008-03-14 21:12:12 +0100923}
924
Ingo Molnarab6cde22007-08-09 11:16:48 +0200925static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200926{
927 /*
928 * If still on the runqueue then deactivate_task()
929 * was not called and update_curr() has to be done:
930 */
931 if (prev->on_rq)
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200932 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200933
Peter Zijlstraddc97292007-10-15 17:00:10 +0200934 check_spread(cfs_rq, prev);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200935 if (prev->on_rq) {
Ingo Molnar5870db52007-08-09 11:16:47 +0200936 update_stats_wait_start(cfs_rq, prev);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200937 /* Put 'current' back into the tree. */
938 __enqueue_entity(cfs_rq, prev);
939 }
Ingo Molnar429d43b2007-10-15 17:00:03 +0200940 cfs_rq->curr = NULL;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200941}
942
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100943static void
944entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200945{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200946 /*
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200947 * Update run-time statistics of the 'current'.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200948 */
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200949 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200950
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100951#ifdef CONFIG_SCHED_HRTICK
952 /*
953 * queued ticks are scheduled to match the slice, so don't bother
954 * validating it and just reschedule.
955 */
Harvey Harrison983ed7a2008-04-24 18:17:55 -0700956 if (queued) {
957 resched_task(rq_of(cfs_rq)->curr);
958 return;
959 }
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100960 /*
961 * don't let the period tick interfere with the hrtick preemption
962 */
963 if (!sched_feat(DOUBLE_TICK) &&
964 hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
965 return;
966#endif
967
Peter Zijlstrace6c1312007-10-15 17:00:14 +0200968 if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
Ingo Molnar2e09bf52007-10-15 17:00:05 +0200969 check_preempt_tick(cfs_rq, curr);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200970}
971
972/**************************************************
973 * CFS operations on tasks:
974 */
975
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100976#ifdef CONFIG_SCHED_HRTICK
977static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
978{
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100979 struct sched_entity *se = &p->se;
980 struct cfs_rq *cfs_rq = cfs_rq_of(se);
981
982 WARN_ON(task_rq(p) != rq);
983
984 if (hrtick_enabled(rq) && cfs_rq->nr_running > 1) {
985 u64 slice = sched_slice(cfs_rq, se);
986 u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
987 s64 delta = slice - ran;
988
989 if (delta < 0) {
990 if (rq->curr == p)
991 resched_task(p);
992 return;
993 }
994
995 /*
996 * Don't schedule slices shorter than 10000ns, that just
997 * doesn't make sense. Rely on vruntime for fairness.
998 */
Peter Zijlstra31656512008-07-18 18:01:23 +0200999 if (rq->curr != p)
Peter Zijlstra157124c2008-07-28 11:53:11 +02001000 delta = max_t(s64, 10000LL, delta);
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001001
Peter Zijlstra31656512008-07-18 18:01:23 +02001002 hrtick_start(rq, delta);
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001003 }
1004}
Peter Zijlstraa4c2f002008-10-17 19:27:03 +02001005
1006/*
1007 * called from enqueue/dequeue and updates the hrtick when the
1008 * current task is from our class and nr_running is low enough
1009 * to matter.
1010 */
1011static void hrtick_update(struct rq *rq)
1012{
1013 struct task_struct *curr = rq->curr;
1014
1015 if (curr->sched_class != &fair_sched_class)
1016 return;
1017
1018 if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
1019 hrtick_start_fair(rq, curr);
1020}
Dhaval Giani55e12e52008-06-24 23:39:43 +05301021#else /* !CONFIG_SCHED_HRTICK */
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001022static inline void
1023hrtick_start_fair(struct rq *rq, struct task_struct *p)
1024{
1025}
Peter Zijlstraa4c2f002008-10-17 19:27:03 +02001026
1027static inline void hrtick_update(struct rq *rq)
1028{
1029}
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001030#endif
1031
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001032/*
1033 * The enqueue_task method is called before nr_running is
1034 * increased. Here we update the fair scheduling stats and
1035 * then put the task into the rbtree:
1036 */
Ingo Molnarfd390f62007-08-09 11:16:48 +02001037static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001038{
1039 struct cfs_rq *cfs_rq;
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001040 struct sched_entity *se = &p->se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001041
1042 for_each_sched_entity(se) {
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001043 if (se->on_rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001044 break;
1045 cfs_rq = cfs_rq_of(se);
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001046 enqueue_entity(cfs_rq, se, wakeup);
Srivatsa Vaddagirib9fa3df2007-10-15 17:00:12 +02001047 wakeup = 1;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001048 }
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001049
Peter Zijlstraa4c2f002008-10-17 19:27:03 +02001050 hrtick_update(rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001051}
1052
1053/*
1054 * The dequeue_task method is called before nr_running is
1055 * decreased. We remove the task from the rbtree and
1056 * update the fair scheduling stats:
1057 */
Ingo Molnarf02231e2007-08-09 11:16:48 +02001058static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001059{
1060 struct cfs_rq *cfs_rq;
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001061 struct sched_entity *se = &p->se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001062
1063 for_each_sched_entity(se) {
1064 cfs_rq = cfs_rq_of(se);
Ingo Molnar525c2712007-08-09 11:16:48 +02001065 dequeue_entity(cfs_rq, se, sleep);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001066 /* Don't dequeue parent if it has other entities besides us */
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001067 if (cfs_rq->load.weight)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001068 break;
Srivatsa Vaddagirib9fa3df2007-10-15 17:00:12 +02001069 sleep = 1;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001070 }
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001071
Peter Zijlstraa4c2f002008-10-17 19:27:03 +02001072 hrtick_update(rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001073}
1074
1075/*
Ingo Molnar1799e352007-09-19 23:34:46 +02001076 * sched_yield() support is very simple - we dequeue and enqueue.
1077 *
1078 * If compat_yield is turned on then we requeue to the end of the tree.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001079 */
Dmitry Adamushko4530d7a2007-10-15 17:00:08 +02001080static void yield_task_fair(struct rq *rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001081{
Ingo Molnardb292ca2007-12-04 17:04:39 +01001082 struct task_struct *curr = rq->curr;
1083 struct cfs_rq *cfs_rq = task_cfs_rq(curr);
1084 struct sched_entity *rightmost, *se = &curr->se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001085
1086 /*
Ingo Molnar1799e352007-09-19 23:34:46 +02001087 * Are we the only task in the tree?
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001088 */
Ingo Molnar1799e352007-09-19 23:34:46 +02001089 if (unlikely(cfs_rq->nr_running == 1))
1090 return;
1091
Peter Zijlstra2002c692008-11-11 11:52:33 +01001092 clear_buddies(cfs_rq, se);
1093
Ingo Molnardb292ca2007-12-04 17:04:39 +01001094 if (likely(!sysctl_sched_compat_yield) && curr->policy != SCHED_BATCH) {
Peter Zijlstra3e51f332008-05-03 18:29:28 +02001095 update_rq_clock(rq);
Ingo Molnar1799e352007-09-19 23:34:46 +02001096 /*
Dmitry Adamushkoa2a2d682007-10-15 17:00:13 +02001097 * Update run-time statistics of the 'current'.
Ingo Molnar1799e352007-09-19 23:34:46 +02001098 */
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +02001099 update_curr(cfs_rq);
Ingo Molnar1799e352007-09-19 23:34:46 +02001100
1101 return;
1102 }
1103 /*
1104 * Find the rightmost entry in the rbtree:
1105 */
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +02001106 rightmost = __pick_last_entity(cfs_rq);
Ingo Molnar1799e352007-09-19 23:34:46 +02001107 /*
1108 * Already in the rightmost position?
1109 */
Fabio Checconi54fdc582009-07-16 12:32:27 +02001110 if (unlikely(!rightmost || entity_before(rightmost, se)))
Ingo Molnar1799e352007-09-19 23:34:46 +02001111 return;
1112
1113 /*
1114 * Minimally necessary key value to be last in the tree:
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +02001115 * Upon rescheduling, sched_class::put_prev_task() will place
1116 * 'current' within the tree based on its new key value.
Ingo Molnar1799e352007-09-19 23:34:46 +02001117 */
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +02001118 se->vruntime = rightmost->vruntime + 1;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001119}
1120
Gregory Haskinse7693a32008-01-25 21:08:09 +01001121#ifdef CONFIG_SMP
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001122
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001123#ifdef CONFIG_FAIR_GROUP_SCHED
Peter Zijlstraf5bfb7d2008-06-27 13:41:39 +02001124/*
1125 * effective_load() calculates the load change as seen from the root_task_group
1126 *
1127 * Adding load to a group doesn't make a group heavier, but can cause movement
1128 * of group shares between cpus. Assuming the shares were perfectly aligned one
1129 * can calculate the shift in shares.
1130 *
1131 * The problem is that perfectly aligning the shares is rather expensive, hence
1132 * we try to avoid doing that too often - see update_shares(), which ratelimits
1133 * this change.
1134 *
1135 * We compensate this by not only taking the current delta into account, but
1136 * also considering the delta between when the shares were last adjusted and
1137 * now.
1138 *
1139 * We still saw a performance dip, some tracing learned us that between
1140 * cgroup:/ and cgroup:/foo balancing the number of affine wakeups increased
1141 * significantly. Therefore try to bias the error in direction of failing
1142 * the affine wakeup.
1143 *
1144 */
Peter Zijlstraf1d239f2008-06-27 13:41:38 +02001145static long effective_load(struct task_group *tg, int cpu,
1146 long wl, long wg)
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001147{
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001148 struct sched_entity *se = tg->se[cpu];
Peter Zijlstraf1d239f2008-06-27 13:41:38 +02001149
1150 if (!tg->parent)
1151 return wl;
1152
1153 /*
Peter Zijlstraf5bfb7d2008-06-27 13:41:39 +02001154 * By not taking the decrease of shares on the other cpu into
1155 * account our error leans towards reducing the affine wakeups.
1156 */
1157 if (!wl && sched_feat(ASYM_EFF_LOAD))
1158 return wl;
1159
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001160 for_each_sched_entity(se) {
Peter Zijlstracb5ef422008-06-27 13:41:32 +02001161 long S, rw, s, a, b;
Peter Zijlstra940959e2008-09-23 15:33:42 +02001162 long more_w;
1163
1164 /*
1165 * Instead of using this increment, also add the difference
1166 * between when the shares were last updated and now.
1167 */
1168 more_w = se->my_q->load.weight - se->my_q->rq_weight;
1169 wl += more_w;
1170 wg += more_w;
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001171
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001172 S = se->my_q->tg->shares;
1173 s = se->my_q->shares;
Peter Zijlstraf1d239f2008-06-27 13:41:38 +02001174 rw = se->my_q->rq_weight;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001175
Peter Zijlstracb5ef422008-06-27 13:41:32 +02001176 a = S*(rw + wl);
1177 b = S*rw + s*wg;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001178
Peter Zijlstra940959e2008-09-23 15:33:42 +02001179 wl = s*(a-b);
1180
1181 if (likely(b))
1182 wl /= b;
1183
Peter Zijlstra83378262008-06-27 13:41:37 +02001184 /*
1185 * Assume the group is already running and will
1186 * thus already be accounted for in the weight.
1187 *
1188 * That is, moving shares between CPUs, does not
1189 * alter the group weight.
1190 */
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001191 wg = 0;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001192 }
1193
1194 return wl;
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001195}
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001196
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001197#else
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001198
Peter Zijlstra83378262008-06-27 13:41:37 +02001199static inline unsigned long effective_load(struct task_group *tg, int cpu,
1200 unsigned long wl, unsigned long wg)
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001201{
Peter Zijlstra83378262008-06-27 13:41:37 +02001202 return wl;
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001203}
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001204
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001205#endif
1206
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001207static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001208{
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001209 struct task_struct *curr = current;
1210 unsigned long this_load, load;
1211 int idx, this_cpu, prev_cpu;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001212 unsigned long tl_per_task;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001213 unsigned int imbalance;
1214 struct task_group *tg;
Peter Zijlstra83378262008-06-27 13:41:37 +02001215 unsigned long weight;
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001216 int balanced;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001217
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001218 idx = sd->wake_idx;
1219 this_cpu = smp_processor_id();
1220 prev_cpu = task_cpu(p);
1221 load = source_load(prev_cpu, idx);
1222 this_load = target_load(this_cpu, idx);
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001223
Peter Zijlstrae69b0f12009-09-15 19:38:52 +02001224 if (sync) {
1225 if (sched_feat(SYNC_LESS) &&
1226 (curr->se.avg_overlap > sysctl_sched_migration_cost ||
1227 p->se.avg_overlap > sysctl_sched_migration_cost))
1228 sync = 0;
1229 } else {
1230 if (sched_feat(SYNC_MORE) &&
1231 (curr->se.avg_overlap < sysctl_sched_migration_cost &&
1232 p->se.avg_overlap < sysctl_sched_migration_cost))
1233 sync = 1;
1234 }
Peter Zijlstrafc631c82009-02-11 14:27:17 +01001235
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001236 /*
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001237 * If sync wakeup then subtract the (maximum possible)
1238 * effect of the currently running task from the load
1239 * of the current CPU:
1240 */
Peter Zijlstra83378262008-06-27 13:41:37 +02001241 if (sync) {
1242 tg = task_group(current);
1243 weight = current->se.load.weight;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001244
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001245 this_load += effective_load(tg, this_cpu, -weight, -weight);
Peter Zijlstra83378262008-06-27 13:41:37 +02001246 load += effective_load(tg, prev_cpu, 0, -weight);
1247 }
1248
1249 tg = task_group(p);
1250 weight = p->se.load.weight;
1251
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001252 imbalance = 100 + (sd->imbalance_pct - 100) / 2;
1253
Peter Zijlstra71a29aa2009-09-07 18:28:05 +02001254 /*
1255 * In low-load situations, where prev_cpu is idle and this_cpu is idle
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001256 * due to the sync cause above having dropped this_load to 0, we'll
1257 * always have an imbalance, but there's really nothing you can do
1258 * about that, so that's good too.
Peter Zijlstra71a29aa2009-09-07 18:28:05 +02001259 *
1260 * Otherwise check if either cpus are near enough in load to allow this
1261 * task to be woken on this_cpu.
1262 */
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001263 balanced = !this_load ||
1264 100*(this_load + effective_load(tg, this_cpu, weight, weight)) <=
Peter Zijlstra83378262008-06-27 13:41:37 +02001265 imbalance*(load + effective_load(tg, prev_cpu, 0, weight));
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001266
1267 /*
1268 * If the currently running task will sleep within
1269 * a reasonable amount of time then attract this newly
1270 * woken task:
1271 */
Peter Zijlstra2fb76352008-10-08 09:16:04 +02001272 if (sync && balanced)
1273 return 1;
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001274
1275 schedstat_inc(p, se.nr_wakeups_affine_attempts);
1276 tl_per_task = cpu_avg_load_per_task(this_cpu);
1277
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001278 if (balanced ||
1279 (this_load <= load &&
1280 this_load + target_load(prev_cpu, idx) <= tl_per_task)) {
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001281 /*
1282 * This domain has SD_WAKE_AFFINE and
1283 * p is cache cold in this domain, and
1284 * there is no bad imbalance.
1285 */
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001286 schedstat_inc(sd, ttwu_move_affine);
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001287 schedstat_inc(p, se.nr_wakeups_affine);
1288
1289 return 1;
1290 }
1291 return 0;
1292}
1293
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001294/*
1295 * find_idlest_group finds and returns the least busy CPU group within the
1296 * domain.
1297 */
1298static struct sched_group *
Peter Zijlstra78e7ed52009-09-03 13:16:51 +02001299find_idlest_group(struct sched_domain *sd, struct task_struct *p,
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001300 int this_cpu, int load_idx)
Gregory Haskinse7693a32008-01-25 21:08:09 +01001301{
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001302 struct sched_group *idlest = NULL, *this = NULL, *group = sd->groups;
1303 unsigned long min_load = ULONG_MAX, this_load = 0;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001304 int imbalance = 100 + (sd->imbalance_pct-100)/2;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001305
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001306 do {
1307 unsigned long load, avg_load;
1308 int local_group;
1309 int i;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001310
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001311 /* Skip over this group if it has no CPUs allowed */
1312 if (!cpumask_intersects(sched_group_cpus(group),
1313 &p->cpus_allowed))
1314 continue;
1315
1316 local_group = cpumask_test_cpu(this_cpu,
1317 sched_group_cpus(group));
1318
1319 /* Tally up the load of all CPUs in the group */
1320 avg_load = 0;
1321
1322 for_each_cpu(i, sched_group_cpus(group)) {
1323 /* Bias balancing toward cpus of our domain */
1324 if (local_group)
1325 load = source_load(i, load_idx);
1326 else
1327 load = target_load(i, load_idx);
1328
1329 avg_load += load;
1330 }
1331
1332 /* Adjust by relative CPU power of the group */
1333 avg_load = (avg_load * SCHED_LOAD_SCALE) / group->cpu_power;
1334
1335 if (local_group) {
1336 this_load = avg_load;
1337 this = group;
1338 } else if (avg_load < min_load) {
1339 min_load = avg_load;
1340 idlest = group;
1341 }
1342 } while (group = group->next, group != sd->groups);
1343
1344 if (!idlest || 100*this_load < imbalance*min_load)
1345 return NULL;
1346 return idlest;
1347}
1348
1349/*
1350 * find_idlest_cpu - find the idlest cpu among the cpus in group.
1351 */
1352static int
1353find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
1354{
1355 unsigned long load, min_load = ULONG_MAX;
1356 int idlest = -1;
1357 int i;
1358
1359 /* Traverse only the allowed CPUs */
1360 for_each_cpu_and(i, sched_group_cpus(group), &p->cpus_allowed) {
1361 load = weighted_cpuload(i);
1362
1363 if (load < min_load || (load == min_load && i == this_cpu)) {
1364 min_load = load;
1365 idlest = i;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001366 }
1367 }
1368
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001369 return idlest;
1370}
Gregory Haskinse7693a32008-01-25 21:08:09 +01001371
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001372/*
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001373 * Try and locate an idle CPU in the sched_domain.
1374 */
1375static int
1376select_idle_sibling(struct task_struct *p, struct sched_domain *sd, int target)
1377{
1378 int cpu = smp_processor_id();
1379 int prev_cpu = task_cpu(p);
1380 int i;
1381
1382 /*
1383 * If this domain spans both cpu and prev_cpu (see the SD_WAKE_AFFINE
1384 * test in select_task_rq_fair) and the prev_cpu is idle then that's
1385 * always a better target than the current cpu.
1386 */
Peter Zijlstrafe3bcfe2009-11-12 15:55:29 +01001387 if (target == cpu && !cpu_rq(prev_cpu)->cfs.nr_running)
1388 return prev_cpu;
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001389
1390 /*
1391 * Otherwise, iterate the domain and find an elegible idle cpu.
1392 */
Peter Zijlstrafe3bcfe2009-11-12 15:55:29 +01001393 for_each_cpu_and(i, sched_domain_span(sd), &p->cpus_allowed) {
1394 if (!cpu_rq(i)->cfs.nr_running) {
1395 target = i;
1396 break;
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001397 }
1398 }
1399
1400 return target;
1401}
1402
1403/*
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001404 * sched_balance_self: balance the current task (running on cpu) in domains
1405 * that have the 'flag' flag set. In practice, this is SD_BALANCE_FORK and
1406 * SD_BALANCE_EXEC.
1407 *
1408 * Balance, ie. select the least loaded group.
1409 *
1410 * Returns the target CPU number, or the same CPU if no balancing is needed.
1411 *
1412 * preempt must be disabled.
1413 */
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001414static int select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001415{
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001416 struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001417 int cpu = smp_processor_id();
1418 int prev_cpu = task_cpu(p);
1419 int new_cpu = cpu;
1420 int want_affine = 0;
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001421 int want_sd = 1;
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001422 int sync = wake_flags & WF_SYNC;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001423
Peter Zijlstra0763a662009-09-14 19:37:39 +02001424 if (sd_flag & SD_BALANCE_WAKE) {
Mike Galbraith3f04e8c2009-09-19 16:52:35 +02001425 if (sched_feat(AFFINE_WAKEUPS) &&
1426 cpumask_test_cpu(cpu, &p->cpus_allowed))
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001427 want_affine = 1;
1428 new_cpu = prev_cpu;
1429 }
Gregory Haskinse7693a32008-01-25 21:08:09 +01001430
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001431 for_each_domain(cpu, tmp) {
1432 /*
Peter Zijlstraae154be2009-09-10 14:40:57 +02001433 * If power savings logic is enabled for a domain, see if we
1434 * are not overloaded, if so, don't balance wider.
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001435 */
Peter Zijlstra59abf022009-09-16 08:28:30 +02001436 if (tmp->flags & (SD_POWERSAVINGS_BALANCE|SD_PREFER_LOCAL)) {
Peter Zijlstraae154be2009-09-10 14:40:57 +02001437 unsigned long power = 0;
1438 unsigned long nr_running = 0;
1439 unsigned long capacity;
1440 int i;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001441
Peter Zijlstraae154be2009-09-10 14:40:57 +02001442 for_each_cpu(i, sched_domain_span(tmp)) {
1443 power += power_of(i);
1444 nr_running += cpu_rq(i)->cfs.nr_running;
1445 }
Gregory Haskinse7693a32008-01-25 21:08:09 +01001446
Peter Zijlstraae154be2009-09-10 14:40:57 +02001447 capacity = DIV_ROUND_CLOSEST(power, SCHED_LOAD_SCALE);
Ingo Molnar4ae7d5c2008-03-19 01:42:00 +01001448
Peter Zijlstra59abf022009-09-16 08:28:30 +02001449 if (tmp->flags & SD_POWERSAVINGS_BALANCE)
1450 nr_running /= 2;
1451
1452 if (nr_running < capacity)
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001453 want_sd = 0;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001454 }
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001455
Peter Zijlstrafe3bcfe2009-11-12 15:55:29 +01001456 /*
1457 * While iterating the domains looking for a spanning
1458 * WAKE_AFFINE domain, adjust the affine target to any idle cpu
1459 * in cache sharing domains along the way.
1460 */
1461 if (want_affine) {
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001462 int target = -1;
Mike Galbraitha1f84a32009-10-27 15:35:38 +01001463
1464 /*
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001465 * If both cpu and prev_cpu are part of this domain,
1466 * cpu is a valid SD_WAKE_AFFINE target.
Mike Galbraitha1f84a32009-10-27 15:35:38 +01001467 */
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001468 if (cpumask_test_cpu(prev_cpu, sched_domain_span(tmp)))
1469 target = cpu;
Mike Galbraitha1f84a32009-10-27 15:35:38 +01001470
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001471 /*
1472 * If there's an idle sibling in this domain, make that
1473 * the wake_affine target instead of the current cpu.
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001474 */
1475 if (tmp->flags & SD_PREFER_SIBLING)
1476 target = select_idle_sibling(p, tmp, target);
Mike Galbraitha1f84a32009-10-27 15:35:38 +01001477
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001478 if (target >= 0) {
Peter Zijlstrafe3bcfe2009-11-12 15:55:29 +01001479 if (tmp->flags & SD_WAKE_AFFINE) {
1480 affine_sd = tmp;
1481 want_affine = 0;
1482 }
Peter Zijlstraa50bde52009-11-12 15:55:28 +01001483 cpu = target;
Mike Galbraitha1f84a32009-10-27 15:35:38 +01001484 }
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001485 }
1486
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001487 if (!want_sd && !want_affine)
1488 break;
1489
Peter Zijlstra0763a662009-09-14 19:37:39 +02001490 if (!(tmp->flags & sd_flag))
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001491 continue;
1492
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001493 if (want_sd)
1494 sd = tmp;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001495 }
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001496
Peter Zijlstra29cd8ba2009-09-17 09:01:14 +02001497 if (sched_feat(LB_SHARES_UPDATE)) {
1498 /*
1499 * Pick the largest domain to update shares over
1500 */
1501 tmp = sd;
1502 if (affine_sd && (!tmp ||
1503 cpumask_weight(sched_domain_span(affine_sd)) >
1504 cpumask_weight(sched_domain_span(sd))))
1505 tmp = affine_sd;
1506
1507 if (tmp)
1508 update_shares(tmp);
1509 }
1510
Peter Zijlstrafb58bac2009-12-01 12:21:47 +01001511 if (affine_sd && wake_affine(affine_sd, p, sync))
1512 return cpu;
Peter Zijlstra3b640892009-09-16 13:44:33 +02001513
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001514 while (sd) {
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001515 int load_idx = sd->forkexec_idx;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001516 struct sched_group *group;
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001517 int weight;
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001518
Peter Zijlstra0763a662009-09-14 19:37:39 +02001519 if (!(sd->flags & sd_flag)) {
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001520 sd = sd->child;
1521 continue;
1522 }
1523
Peter Zijlstra5158f4e2009-09-16 13:46:59 +02001524 if (sd_flag & SD_BALANCE_WAKE)
1525 load_idx = sd->wake_idx;
1526
1527 group = find_idlest_group(sd, p, cpu, load_idx);
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001528 if (!group) {
1529 sd = sd->child;
1530 continue;
1531 }
1532
Peter Zijlstrad7c33c42009-09-11 12:45:38 +02001533 new_cpu = find_idlest_cpu(group, p, cpu);
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001534 if (new_cpu == -1 || new_cpu == cpu) {
1535 /* Now try balancing at a lower domain level of cpu */
1536 sd = sd->child;
1537 continue;
1538 }
1539
1540 /* Now try balancing at a lower domain level of new_cpu */
1541 cpu = new_cpu;
1542 weight = cpumask_weight(sched_domain_span(sd));
1543 sd = NULL;
1544 for_each_domain(cpu, tmp) {
1545 if (weight <= cpumask_weight(sched_domain_span(tmp)))
1546 break;
Peter Zijlstra0763a662009-09-14 19:37:39 +02001547 if (tmp->flags & sd_flag)
Peter Zijlstraaaee1202009-09-10 13:36:25 +02001548 sd = tmp;
1549 }
1550 /* while loop will break here if sd == NULL */
Gregory Haskinse7693a32008-01-25 21:08:09 +01001551 }
1552
Peter Zijlstrac88d5912009-09-10 13:50:02 +02001553 return new_cpu;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001554}
1555#endif /* CONFIG_SMP */
1556
Peter Zijlstrae52fb7c2009-01-14 12:39:19 +01001557/*
1558 * Adaptive granularity
1559 *
1560 * se->avg_wakeup gives the average time a task runs until it does a wakeup,
1561 * with the limit of wakeup_gran -- when it never does a wakeup.
1562 *
1563 * So the smaller avg_wakeup is the faster we want this task to preempt,
1564 * but we don't want to treat the preemptee unfairly and therefore allow it
1565 * to run for at least the amount of time we'd like to run.
1566 *
1567 * NOTE: we use 2*avg_wakeup to increase the probability of actually doing one
1568 *
1569 * NOTE: we use *nr_running to scale with load, this nicely matches the
1570 * degrading latency on load.
1571 */
1572static unsigned long
1573adaptive_gran(struct sched_entity *curr, struct sched_entity *se)
1574{
1575 u64 this_run = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
1576 u64 expected_wakeup = 2*se->avg_wakeup * cfs_rq_of(se)->nr_running;
1577 u64 gran = 0;
1578
1579 if (this_run < expected_wakeup)
1580 gran = expected_wakeup - this_run;
1581
1582 return min_t(s64, gran, sysctl_sched_wakeup_granularity);
1583}
1584
1585static unsigned long
1586wakeup_gran(struct sched_entity *curr, struct sched_entity *se)
Peter Zijlstra0bbd3332008-04-19 19:44:57 +02001587{
1588 unsigned long gran = sysctl_sched_wakeup_granularity;
1589
Peter Zijlstrae52fb7c2009-01-14 12:39:19 +01001590 if (cfs_rq_of(curr)->curr && sched_feat(ADAPTIVE_GRAN))
1591 gran = adaptive_gran(curr, se);
1592
Peter Zijlstra0bbd3332008-04-19 19:44:57 +02001593 /*
Peter Zijlstrae52fb7c2009-01-14 12:39:19 +01001594 * Since its curr running now, convert the gran from real-time
1595 * to virtual-time in his units.
Peter Zijlstra0bbd3332008-04-19 19:44:57 +02001596 */
Peter Zijlstrae52fb7c2009-01-14 12:39:19 +01001597 if (sched_feat(ASYM_GRAN)) {
1598 /*
1599 * By using 'se' instead of 'curr' we penalize light tasks, so
1600 * they get preempted easier. That is, if 'se' < 'curr' then
1601 * the resulting gran will be larger, therefore penalizing the
1602 * lighter, if otoh 'se' > 'curr' then the resulting gran will
1603 * be smaller, again penalizing the lighter task.
1604 *
1605 * This is especially important for buddies when the leftmost
1606 * task is higher priority than the buddy.
1607 */
1608 if (unlikely(se->load.weight != NICE_0_LOAD))
1609 gran = calc_delta_fair(gran, se);
1610 } else {
1611 if (unlikely(curr->load.weight != NICE_0_LOAD))
1612 gran = calc_delta_fair(gran, curr);
1613 }
Peter Zijlstra0bbd3332008-04-19 19:44:57 +02001614
1615 return gran;
1616}
1617
1618/*
Peter Zijlstra464b7522008-10-24 11:06:15 +02001619 * Should 'se' preempt 'curr'.
1620 *
1621 * |s1
1622 * |s2
1623 * |s3
1624 * g
1625 * |<--->|c
1626 *
1627 * w(c, s1) = -1
1628 * w(c, s2) = 0
1629 * w(c, s3) = 1
1630 *
1631 */
1632static int
1633wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
1634{
1635 s64 gran, vdiff = curr->vruntime - se->vruntime;
1636
1637 if (vdiff <= 0)
1638 return -1;
1639
Peter Zijlstrae52fb7c2009-01-14 12:39:19 +01001640 gran = wakeup_gran(curr, se);
Peter Zijlstra464b7522008-10-24 11:06:15 +02001641 if (vdiff > gran)
1642 return 1;
1643
1644 return 0;
1645}
1646
Peter Zijlstra02479092008-11-04 21:25:10 +01001647static void set_last_buddy(struct sched_entity *se)
1648{
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001649 if (likely(task_of(se)->policy != SCHED_IDLE)) {
1650 for_each_sched_entity(se)
1651 cfs_rq_of(se)->last = se;
1652 }
Peter Zijlstra02479092008-11-04 21:25:10 +01001653}
1654
1655static void set_next_buddy(struct sched_entity *se)
1656{
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001657 if (likely(task_of(se)->policy != SCHED_IDLE)) {
1658 for_each_sched_entity(se)
1659 cfs_rq_of(se)->next = se;
1660 }
Peter Zijlstra02479092008-11-04 21:25:10 +01001661}
1662
Peter Zijlstra464b7522008-10-24 11:06:15 +02001663/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001664 * Preempt the current task with a newly woken task if needed:
1665 */
Peter Zijlstra5a9b86f2009-09-16 13:47:58 +02001666static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001667{
1668 struct task_struct *curr = rq->curr;
Srivatsa Vaddagiri8651a862007-10-15 17:00:12 +02001669 struct sched_entity *se = &curr->se, *pse = &p->se;
Mike Galbraith03e89e42008-12-16 08:45:30 +01001670 struct cfs_rq *cfs_rq = task_cfs_rq(curr);
Peter Zijlstra5a9b86f2009-09-16 13:47:58 +02001671 int sync = wake_flags & WF_SYNC;
Mike Galbraithf685cea2009-10-23 23:09:22 +02001672 int scale = cfs_rq->nr_running >= sched_nr_latency;
Mike Galbraith03e89e42008-12-16 08:45:30 +01001673
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01001674 if (unlikely(rt_prio(p->prio)))
1675 goto preempt;
Peter Zijlstraaa2ac252008-03-14 21:12:12 +01001676
Peter Zijlstrad95f98d2008-11-04 21:25:08 +01001677 if (unlikely(p->sched_class != &fair_sched_class))
1678 return;
1679
Ingo Molnar4ae7d5c2008-03-19 01:42:00 +01001680 if (unlikely(se == pse))
1681 return;
1682
Mike Galbraithf685cea2009-10-23 23:09:22 +02001683 if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK))
Mike Galbraith3cb63d52009-09-11 12:01:17 +02001684 set_next_buddy(pse);
Peter Zijlstra57fdc262008-09-23 15:33:45 +02001685
Bharata B Raoaec0a512008-08-28 14:42:49 +05301686 /*
1687 * We can come here with TIF_NEED_RESCHED already set from new task
1688 * wake up path.
1689 */
1690 if (test_tsk_need_resched(curr))
1691 return;
1692
Ingo Molnar91c234b2007-10-15 17:00:18 +02001693 /*
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001694 * Batch and idle tasks do not preempt (their preemption is driven by
Ingo Molnar91c234b2007-10-15 17:00:18 +02001695 * the tick):
1696 */
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001697 if (unlikely(p->policy != SCHED_NORMAL))
Ingo Molnar91c234b2007-10-15 17:00:18 +02001698 return;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001699
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001700 /* Idle tasks are by definition preempted by everybody. */
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01001701 if (unlikely(curr->policy == SCHED_IDLE))
1702 goto preempt;
Peter Zijlstra6bc912b2009-01-15 14:53:38 +01001703
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01001704 if (sched_feat(WAKEUP_SYNC) && sync)
1705 goto preempt;
Peter Zijlstra15afe092008-09-20 23:38:02 +02001706
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01001707 if (sched_feat(WAKEUP_OVERLAP) &&
1708 se->avg_overlap < sysctl_sched_migration_cost &&
1709 pse->avg_overlap < sysctl_sched_migration_cost)
1710 goto preempt;
1711
Peter Zijlstraad4b78b2009-09-16 12:31:31 +02001712 if (!sched_feat(WAKEUP_PREEMPT))
1713 return;
1714
Jupyung Leea65ac742009-11-17 18:51:40 +09001715 update_curr(cfs_rq);
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01001716 find_matching_se(&se, &pse);
1717 BUG_ON(!pse);
1718 if (wakeup_preempt_entity(se, pse) == 1)
1719 goto preempt;
Jupyung Leea65ac742009-11-17 18:51:40 +09001720
Peter Zijlstra3a7e73a2009-11-28 18:51:02 +01001721 return;
1722
1723preempt:
1724 resched_task(curr);
1725 /*
1726 * Only set the backward buddy when the current task is still
1727 * on the rq. This can happen when a wakeup gets interleaved
1728 * with schedule on the ->pre_schedule() or idle_balance()
1729 * point, either of which can * drop the rq lock.
1730 *
1731 * Also, during early boot the idle thread is in the fair class,
1732 * for obvious reasons its a bad idea to schedule back to it.
1733 */
1734 if (unlikely(!se->on_rq || curr == rq->idle))
1735 return;
1736
1737 if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))
1738 set_last_buddy(se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001739}
1740
Ingo Molnarfb8d4722007-08-09 11:16:48 +02001741static struct task_struct *pick_next_task_fair(struct rq *rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001742{
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001743 struct task_struct *p;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001744 struct cfs_rq *cfs_rq = &rq->cfs;
1745 struct sched_entity *se;
1746
Tim Blechmann36ace272009-11-24 11:55:45 +01001747 if (!cfs_rq->nr_running)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001748 return NULL;
1749
1750 do {
Ingo Molnar9948f4b2007-08-09 11:16:48 +02001751 se = pick_next_entity(cfs_rq);
Peter Zijlstraf4b67552008-11-04 21:25:07 +01001752 set_next_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001753 cfs_rq = group_cfs_rq(se);
1754 } while (cfs_rq);
1755
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001756 p = task_of(se);
1757 hrtick_start_fair(rq, p);
1758
1759 return p;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001760}
1761
1762/*
1763 * Account for a descheduled task:
1764 */
Ingo Molnar31ee5292007-08-09 11:16:49 +02001765static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001766{
1767 struct sched_entity *se = &prev->se;
1768 struct cfs_rq *cfs_rq;
1769
1770 for_each_sched_entity(se) {
1771 cfs_rq = cfs_rq_of(se);
Ingo Molnarab6cde22007-08-09 11:16:48 +02001772 put_prev_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001773 }
1774}
1775
Peter Williams681f3e62007-10-24 18:23:51 +02001776#ifdef CONFIG_SMP
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001777/**************************************************
1778 * Fair scheduling class load-balancing methods:
1779 */
1780
1781/*
1782 * Load-balancing iterator. Note: while the runqueue stays locked
1783 * during the whole iteration, the current task might be
1784 * dequeued so the iterator has to be dequeue-safe. Here we
1785 * achieve that by always pre-iterating before returning
1786 * the current task:
1787 */
Alexey Dobriyana9957442007-10-15 17:00:13 +02001788static struct task_struct *
Peter Zijlstra4a55bd52008-04-19 19:45:00 +02001789__load_balance_iterator(struct cfs_rq *cfs_rq, struct list_head *next)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001790{
Dhaval Giani354d60c2008-04-19 19:44:59 +02001791 struct task_struct *p = NULL;
1792 struct sched_entity *se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001793
Mike Galbraith77ae6512008-08-11 13:32:02 +02001794 if (next == &cfs_rq->tasks)
1795 return NULL;
1796
Bharata B Raob87f1722008-09-25 09:53:54 +05301797 se = list_entry(next, struct sched_entity, group_node);
1798 p = task_of(se);
1799 cfs_rq->balance_iterator = next->next;
Mike Galbraith77ae6512008-08-11 13:32:02 +02001800
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001801 return p;
1802}
1803
1804static struct task_struct *load_balance_start_fair(void *arg)
1805{
1806 struct cfs_rq *cfs_rq = arg;
1807
Peter Zijlstra4a55bd52008-04-19 19:45:00 +02001808 return __load_balance_iterator(cfs_rq, cfs_rq->tasks.next);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001809}
1810
1811static struct task_struct *load_balance_next_fair(void *arg)
1812{
1813 struct cfs_rq *cfs_rq = arg;
1814
Peter Zijlstra4a55bd52008-04-19 19:45:00 +02001815 return __load_balance_iterator(cfs_rq, cfs_rq->balance_iterator);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001816}
1817
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001818static unsigned long
1819__load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1820 unsigned long max_load_move, struct sched_domain *sd,
1821 enum cpu_idle_type idle, int *all_pinned, int *this_best_prio,
1822 struct cfs_rq *cfs_rq)
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001823{
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001824 struct rq_iterator cfs_rq_iterator;
Ingo Molnar6363ca52008-05-29 11:28:57 +02001825
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001826 cfs_rq_iterator.start = load_balance_start_fair;
1827 cfs_rq_iterator.next = load_balance_next_fair;
1828 cfs_rq_iterator.arg = cfs_rq;
Ingo Molnar6363ca52008-05-29 11:28:57 +02001829
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001830 return balance_tasks(this_rq, this_cpu, busiest,
1831 max_load_move, sd, idle, all_pinned,
1832 this_best_prio, &cfs_rq_iterator);
Ingo Molnar6363ca52008-05-29 11:28:57 +02001833}
Ingo Molnar6363ca52008-05-29 11:28:57 +02001834
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001835#ifdef CONFIG_FAIR_GROUP_SCHED
Ingo Molnar6363ca52008-05-29 11:28:57 +02001836static unsigned long
1837load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1838 unsigned long max_load_move,
1839 struct sched_domain *sd, enum cpu_idle_type idle,
1840 int *all_pinned, int *this_best_prio)
1841{
Ingo Molnar6363ca52008-05-29 11:28:57 +02001842 long rem_load_move = max_load_move;
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001843 int busiest_cpu = cpu_of(busiest);
1844 struct task_group *tg;
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001845
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001846 rcu_read_lock();
Peter Zijlstrac8cba852008-06-27 13:41:23 +02001847 update_h_load(busiest_cpu);
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001848
Chris Friesencaea8a02008-09-22 11:06:09 -06001849 list_for_each_entry_rcu(tg, &task_groups, list) {
Peter Zijlstrac8cba852008-06-27 13:41:23 +02001850 struct cfs_rq *busiest_cfs_rq = tg->cfs_rq[busiest_cpu];
Peter Zijlstra42a3ac72008-06-27 13:41:29 +02001851 unsigned long busiest_h_load = busiest_cfs_rq->h_load;
1852 unsigned long busiest_weight = busiest_cfs_rq->load.weight;
Srivatsa Vaddagiri243e0e72008-06-27 13:41:36 +02001853 u64 rem_load, moved_load;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001854
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001855 /*
1856 * empty group
1857 */
Peter Zijlstrac8cba852008-06-27 13:41:23 +02001858 if (!busiest_cfs_rq->task_weight)
Ingo Molnar6363ca52008-05-29 11:28:57 +02001859 continue;
1860
Srivatsa Vaddagiri243e0e72008-06-27 13:41:36 +02001861 rem_load = (u64)rem_load_move * busiest_weight;
1862 rem_load = div_u64(rem_load, busiest_h_load + 1);
Ingo Molnar6363ca52008-05-29 11:28:57 +02001863
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001864 moved_load = __load_balance_fair(this_rq, this_cpu, busiest,
Srivatsa Vaddagiri53fecd82008-06-27 13:41:20 +02001865 rem_load, sd, idle, all_pinned, this_best_prio,
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001866 tg->cfs_rq[busiest_cpu]);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001867
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001868 if (!moved_load)
1869 continue;
1870
Peter Zijlstra42a3ac72008-06-27 13:41:29 +02001871 moved_load *= busiest_h_load;
Srivatsa Vaddagiri243e0e72008-06-27 13:41:36 +02001872 moved_load = div_u64(moved_load, busiest_weight + 1);
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001873
1874 rem_load_move -= moved_load;
1875 if (rem_load_move < 0)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001876 break;
1877 }
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001878 rcu_read_unlock();
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001879
Peter Williams43010652007-08-09 11:16:46 +02001880 return max_load_move - rem_load_move;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001881}
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001882#else
1883static unsigned long
1884load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1885 unsigned long max_load_move,
1886 struct sched_domain *sd, enum cpu_idle_type idle,
1887 int *all_pinned, int *this_best_prio)
1888{
1889 return __load_balance_fair(this_rq, this_cpu, busiest,
1890 max_load_move, sd, idle, all_pinned,
1891 this_best_prio, &busiest->cfs);
1892}
1893#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001894
Peter Williamse1d14842007-10-24 18:23:51 +02001895static int
1896move_one_task_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1897 struct sched_domain *sd, enum cpu_idle_type idle)
1898{
1899 struct cfs_rq *busy_cfs_rq;
1900 struct rq_iterator cfs_rq_iterator;
1901
1902 cfs_rq_iterator.start = load_balance_start_fair;
1903 cfs_rq_iterator.next = load_balance_next_fair;
1904
1905 for_each_leaf_cfs_rq(busiest, busy_cfs_rq) {
1906 /*
1907 * pass busy_cfs_rq argument into
1908 * load_balance_[start|next]_fair iterators
1909 */
1910 cfs_rq_iterator.arg = busy_cfs_rq;
1911 if (iter_move_one_task(this_rq, this_cpu, busiest, sd, idle,
1912 &cfs_rq_iterator))
1913 return 1;
1914 }
1915
1916 return 0;
1917}
Christian Ehrhardt0bcdcf22009-11-30 12:16:46 +01001918
1919static void rq_online_fair(struct rq *rq)
1920{
1921 update_sysctl();
1922}
1923
1924static void rq_offline_fair(struct rq *rq)
1925{
1926 update_sysctl();
1927}
1928
Dhaval Giani55e12e52008-06-24 23:39:43 +05301929#endif /* CONFIG_SMP */
Peter Williamse1d14842007-10-24 18:23:51 +02001930
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001931/*
1932 * scheduler tick hitting a task of our scheduling class:
1933 */
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001934static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001935{
1936 struct cfs_rq *cfs_rq;
1937 struct sched_entity *se = &curr->se;
1938
1939 for_each_sched_entity(se) {
1940 cfs_rq = cfs_rq_of(se);
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001941 entity_tick(cfs_rq, se, queued);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001942 }
1943}
1944
1945/*
Peter Zijlstracd29fe62009-11-27 17:32:46 +01001946 * called on fork with the child task as argument from the parent's context
1947 * - child not yet on the tasklist
1948 * - preemption disabled
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001949 */
Peter Zijlstracd29fe62009-11-27 17:32:46 +01001950static void task_fork_fair(struct task_struct *p)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001951{
Peter Zijlstracd29fe62009-11-27 17:32:46 +01001952 struct cfs_rq *cfs_rq = task_cfs_rq(current);
Ingo Molnar429d43b2007-10-15 17:00:03 +02001953 struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
Ingo Molnar00bf7bf2007-10-15 17:00:14 +02001954 int this_cpu = smp_processor_id();
Peter Zijlstracd29fe62009-11-27 17:32:46 +01001955 struct rq *rq = this_rq();
1956 unsigned long flags;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001957
Thomas Gleixner05fa7852009-11-17 14:28:38 +01001958 raw_spin_lock_irqsave(&rq->lock, flags);
Peter Zijlstracd29fe62009-11-27 17:32:46 +01001959
1960 if (unlikely(task_cpu(p) != this_cpu))
1961 __set_task_cpu(p, this_cpu);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001962
Ting Yang7109c4422007-08-28 12:53:24 +02001963 update_curr(cfs_rq);
Peter Zijlstracd29fe62009-11-27 17:32:46 +01001964
Mike Galbraithb5d9d732009-09-08 11:12:28 +02001965 if (curr)
1966 se->vruntime = curr->vruntime;
Peter Zijlstraaeb73b02007-10-15 17:00:05 +02001967 place_entity(cfs_rq, se, 1);
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02001968
Peter Zijlstracd29fe62009-11-27 17:32:46 +01001969 if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
Dmitry Adamushko87fefa32007-10-15 17:00:08 +02001970 /*
Ingo Molnaredcb60a2007-10-15 17:00:08 +02001971 * Upon rescheduling, sched_class::put_prev_task() will place
1972 * 'current' within the tree based on its new key value.
1973 */
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02001974 swap(curr->vruntime, se->vruntime);
Bharata B Raoaec0a512008-08-28 14:42:49 +05301975 resched_task(rq->curr);
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02001976 }
1977
Thomas Gleixner05fa7852009-11-17 14:28:38 +01001978 raw_spin_unlock_irqrestore(&rq->lock, flags);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001979}
1980
Steven Rostedtcb469842008-01-25 21:08:22 +01001981/*
1982 * Priority of the task has changed. Check to see if we preempt
1983 * the current task.
1984 */
1985static void prio_changed_fair(struct rq *rq, struct task_struct *p,
1986 int oldprio, int running)
1987{
1988 /*
1989 * Reschedule if we are currently running on this runqueue and
1990 * our priority decreased, or if we are not currently running on
1991 * this runqueue and our priority is higher than the current's
1992 */
1993 if (running) {
1994 if (p->prio > oldprio)
1995 resched_task(rq->curr);
1996 } else
Peter Zijlstra15afe092008-09-20 23:38:02 +02001997 check_preempt_curr(rq, p, 0);
Steven Rostedtcb469842008-01-25 21:08:22 +01001998}
1999
2000/*
2001 * We switched to the sched_fair class.
2002 */
2003static void switched_to_fair(struct rq *rq, struct task_struct *p,
2004 int running)
2005{
2006 /*
2007 * We were most likely switched from sched_rt, so
2008 * kick off the schedule if running, otherwise just see
2009 * if we can still preempt the current task.
2010 */
2011 if (running)
2012 resched_task(rq->curr);
2013 else
Peter Zijlstra15afe092008-09-20 23:38:02 +02002014 check_preempt_curr(rq, p, 0);
Steven Rostedtcb469842008-01-25 21:08:22 +01002015}
2016
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02002017/* Account for a task changing its policy or group.
2018 *
2019 * This routine is mostly called to set cfs_rq->curr field when a task
2020 * migrates between groups/classes.
2021 */
2022static void set_curr_task_fair(struct rq *rq)
2023{
2024 struct sched_entity *se = &rq->curr->se;
2025
2026 for_each_sched_entity(se)
2027 set_next_entity(cfs_rq_of(se), se);
2028}
2029
Peter Zijlstra810b3812008-02-29 15:21:01 -05002030#ifdef CONFIG_FAIR_GROUP_SCHED
2031static void moved_group_fair(struct task_struct *p)
2032{
2033 struct cfs_rq *cfs_rq = task_cfs_rq(p);
2034
2035 update_curr(cfs_rq);
2036 place_entity(cfs_rq, &p->se, 1);
2037}
2038#endif
2039
Thomas Gleixnerdba091b2009-12-09 09:32:03 +01002040unsigned int get_rr_interval_fair(struct rq *rq, struct task_struct *task)
Peter Williams0d721ce2009-09-21 01:31:53 +00002041{
2042 struct sched_entity *se = &task->se;
Peter Williams0d721ce2009-09-21 01:31:53 +00002043 unsigned int rr_interval = 0;
2044
2045 /*
2046 * Time slice is 0 for SCHED_OTHER tasks that are on an otherwise
2047 * idle runqueue:
2048 */
Peter Williams0d721ce2009-09-21 01:31:53 +00002049 if (rq->cfs.load.weight)
2050 rr_interval = NS_TO_JIFFIES(sched_slice(&rq->cfs, se));
Peter Williams0d721ce2009-09-21 01:31:53 +00002051
2052 return rr_interval;
2053}
2054
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002055/*
2056 * All the scheduling class methods:
2057 */
Ingo Molnar5522d5d2007-10-15 17:00:12 +02002058static const struct sched_class fair_sched_class = {
2059 .next = &idle_sched_class,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002060 .enqueue_task = enqueue_task_fair,
2061 .dequeue_task = dequeue_task_fair,
2062 .yield_task = yield_task_fair,
2063
Ingo Molnar2e09bf52007-10-15 17:00:05 +02002064 .check_preempt_curr = check_preempt_wakeup,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002065
2066 .pick_next_task = pick_next_task_fair,
2067 .put_prev_task = put_prev_task_fair,
2068
Peter Williams681f3e62007-10-24 18:23:51 +02002069#ifdef CONFIG_SMP
Li Zefan4ce72a22008-10-22 15:25:26 +08002070 .select_task_rq = select_task_rq_fair,
2071
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002072 .load_balance = load_balance_fair,
Peter Williamse1d14842007-10-24 18:23:51 +02002073 .move_one_task = move_one_task_fair,
Christian Ehrhardt0bcdcf22009-11-30 12:16:46 +01002074 .rq_online = rq_online_fair,
2075 .rq_offline = rq_offline_fair,
Peter Williams681f3e62007-10-24 18:23:51 +02002076#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002077
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02002078 .set_curr_task = set_curr_task_fair,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002079 .task_tick = task_tick_fair,
Peter Zijlstracd29fe62009-11-27 17:32:46 +01002080 .task_fork = task_fork_fair,
Steven Rostedtcb469842008-01-25 21:08:22 +01002081
2082 .prio_changed = prio_changed_fair,
2083 .switched_to = switched_to_fair,
Peter Zijlstra810b3812008-02-29 15:21:01 -05002084
Peter Williams0d721ce2009-09-21 01:31:53 +00002085 .get_rr_interval = get_rr_interval_fair,
2086
Peter Zijlstra810b3812008-02-29 15:21:01 -05002087#ifdef CONFIG_FAIR_GROUP_SCHED
2088 .moved_group = moved_group_fair,
2089#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002090};
2091
2092#ifdef CONFIG_SCHED_DEBUG
Ingo Molnar5cef9ec2007-08-09 11:16:47 +02002093static void print_cfs_stats(struct seq_file *m, int cpu)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002094{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002095 struct cfs_rq *cfs_rq;
2096
Peter Zijlstra5973e5b2008-01-25 21:08:34 +01002097 rcu_read_lock();
Ingo Molnarc3b64f12007-08-09 11:16:51 +02002098 for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
Ingo Molnar5cef9ec2007-08-09 11:16:47 +02002099 print_cfs_rq(m, cpu, cfs_rq);
Peter Zijlstra5973e5b2008-01-25 21:08:34 +01002100 rcu_read_unlock();
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02002101}
2102#endif