blob: 5ad4440f0fc44798b84417fa56463dd19ad81267 [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>
24
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020025/*
Peter Zijlstra21805082007-08-25 18:41:53 +020026 * Targeted preemption latency for CPU-bound tasks:
Zou Nan hai722aab02007-11-26 21:21:49 +010027 * (default: 20ms * (1 + ilog(ncpus)), units: nanoseconds)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020028 *
Peter Zijlstra21805082007-08-25 18:41:53 +020029 * NOTE: this latency value is not the same as the concept of
Ingo Molnard274a4c2007-10-15 17:00:14 +020030 * 'timeslice length' - timeslices in CFS are of variable length
31 * and have no persistent notion like in traditional, time-slice
32 * based scheduling concepts.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020033 *
Ingo Molnard274a4c2007-10-15 17:00:14 +020034 * (to see the precise effective timeslice length of your workload,
35 * run vmstat and monitor the context-switches (cs) field)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020036 */
Ingo Molnar19978ca2007-11-09 22:39:38 +010037unsigned int sysctl_sched_latency = 20000000ULL;
Ingo Molnar2bd8e6d2007-10-15 17:00:02 +020038
39/*
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010040 * Minimal preemption granularity for CPU-bound tasks:
Zou Nan hai722aab02007-11-26 21:21:49 +010041 * (default: 4 msec * (1 + ilog(ncpus)), units: nanoseconds)
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010042 */
Zou Nan hai722aab02007-11-26 21:21:49 +010043unsigned int sysctl_sched_min_granularity = 4000000ULL;
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010044
45/*
46 * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
47 */
Zou Nan hai722aab02007-11-26 21:21:49 +010048static unsigned int sched_nr_latency = 5;
Peter Zijlstrab2be5e92007-11-09 22:39:37 +010049
50/*
Ingo Molnar2bd8e6d2007-10-15 17:00:02 +020051 * After fork, child runs first. (default) If set to 0 then
52 * parent will (try to) run first.
53 */
54const_debug unsigned int sysctl_sched_child_runs_first = 1;
Peter Zijlstra21805082007-08-25 18:41:53 +020055
56/*
Ingo Molnar1799e352007-09-19 23:34:46 +020057 * sys_sched_yield() compat mode
58 *
59 * This option switches the agressive yield implementation of the
60 * old scheduler back on.
61 */
62unsigned int __read_mostly sysctl_sched_compat_yield;
63
64/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020065 * SCHED_OTHER wake-up granularity.
Peter Zijlstra103638d92008-06-27 13:41:16 +020066 * (default: 5 msec * (1 + ilog(ncpus)), units: nanoseconds)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020067 *
68 * This option delays the preemption effects of decoupled workloads
69 * and reduces their over-scheduling. Synchronous workloads will still
70 * have immediate wakeup/sleep latencies.
71 */
Peter Zijlstra103638d92008-06-27 13:41:16 +020072unsigned int sysctl_sched_wakeup_granularity = 5000000UL;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020073
Ingo Molnarda84d962007-10-15 17:00:18 +020074const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
75
Peter Zijlstraa4c2f002008-10-17 19:27:03 +020076static const struct sched_class fair_sched_class;
77
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020078/**************************************************************
79 * CFS operations on generic schedulable entities:
80 */
81
Peter Zijlstrab7581492008-04-19 19:45:00 +020082static inline struct task_struct *task_of(struct sched_entity *se)
83{
84 return container_of(se, struct task_struct, se);
85}
86
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020087#ifdef CONFIG_FAIR_GROUP_SCHED
88
89/* cpu runqueue to which this cfs_rq is attached */
90static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
91{
92 return cfs_rq->rq;
93}
94
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020095/* An entity is a task if it doesn't "own" a runqueue */
96#define entity_is_task(se) (!se->my_q)
97
Peter Zijlstrab7581492008-04-19 19:45:00 +020098/* Walk up scheduling entities hierarchy */
99#define for_each_sched_entity(se) \
100 for (; se; se = se->parent)
101
102static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
103{
104 return p->se.cfs_rq;
105}
106
107/* runqueue on which this entity is (to be) queued */
108static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
109{
110 return se->cfs_rq;
111}
112
113/* runqueue "owned" by this group */
114static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
115{
116 return grp->my_q;
117}
118
119/* Given a group's cfs_rq on one cpu, return its corresponding cfs_rq on
120 * another cpu ('this_cpu')
121 */
122static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
123{
124 return cfs_rq->tg->cfs_rq[this_cpu];
125}
126
127/* Iterate thr' all leaf cfs_rq's on a runqueue */
128#define for_each_leaf_cfs_rq(rq, cfs_rq) \
129 list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
130
131/* Do the two (enqueued) entities belong to the same group ? */
132static inline int
133is_same_group(struct sched_entity *se, struct sched_entity *pse)
134{
135 if (se->cfs_rq == pse->cfs_rq)
136 return 1;
137
138 return 0;
139}
140
141static inline struct sched_entity *parent_entity(struct sched_entity *se)
142{
143 return se->parent;
144}
145
Peter Zijlstra464b7522008-10-24 11:06:15 +0200146/* return depth at which a sched entity is present in the hierarchy */
147static inline int depth_se(struct sched_entity *se)
148{
149 int depth = 0;
150
151 for_each_sched_entity(se)
152 depth++;
153
154 return depth;
155}
156
157static void
158find_matching_se(struct sched_entity **se, struct sched_entity **pse)
159{
160 int se_depth, pse_depth;
161
162 /*
163 * preemption test can be made between sibling entities who are in the
164 * same cfs_rq i.e who have a common parent. Walk up the hierarchy of
165 * both tasks until we find their ancestors who are siblings of common
166 * parent.
167 */
168
169 /* First walk up until both entities are at same depth */
170 se_depth = depth_se(*se);
171 pse_depth = depth_se(*pse);
172
173 while (se_depth > pse_depth) {
174 se_depth--;
175 *se = parent_entity(*se);
176 }
177
178 while (pse_depth > se_depth) {
179 pse_depth--;
180 *pse = parent_entity(*pse);
181 }
182
183 while (!is_same_group(*se, *pse)) {
184 *se = parent_entity(*se);
185 *pse = parent_entity(*pse);
186 }
187}
188
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200189#else /* CONFIG_FAIR_GROUP_SCHED */
190
191static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
192{
193 return container_of(cfs_rq, struct rq, cfs);
194}
195
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200196#define entity_is_task(se) 1
197
Peter Zijlstrab7581492008-04-19 19:45:00 +0200198#define for_each_sched_entity(se) \
199 for (; se; se = NULL)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200200
Peter Zijlstrab7581492008-04-19 19:45:00 +0200201static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200202{
Peter Zijlstrab7581492008-04-19 19:45:00 +0200203 return &task_rq(p)->cfs;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200204}
205
Peter Zijlstrab7581492008-04-19 19:45:00 +0200206static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
207{
208 struct task_struct *p = task_of(se);
209 struct rq *rq = task_rq(p);
210
211 return &rq->cfs;
212}
213
214/* runqueue "owned" by this group */
215static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
216{
217 return NULL;
218}
219
220static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
221{
222 return &cpu_rq(this_cpu)->cfs;
223}
224
225#define for_each_leaf_cfs_rq(rq, cfs_rq) \
226 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
227
228static inline int
229is_same_group(struct sched_entity *se, struct sched_entity *pse)
230{
231 return 1;
232}
233
234static inline struct sched_entity *parent_entity(struct sched_entity *se)
235{
236 return NULL;
237}
238
Peter Zijlstra464b7522008-10-24 11:06:15 +0200239static inline void
240find_matching_se(struct sched_entity **se, struct sched_entity **pse)
241{
242}
243
Peter Zijlstrab7581492008-04-19 19:45:00 +0200244#endif /* CONFIG_FAIR_GROUP_SCHED */
245
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200246
247/**************************************************************
248 * Scheduling class tree data structure manipulation methods:
249 */
250
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200251static inline u64 max_vruntime(u64 min_vruntime, u64 vruntime)
Peter Zijlstra02e04312007-10-15 17:00:07 +0200252{
Peter Zijlstra368059a2007-10-15 17:00:11 +0200253 s64 delta = (s64)(vruntime - min_vruntime);
254 if (delta > 0)
Peter Zijlstra02e04312007-10-15 17:00:07 +0200255 min_vruntime = vruntime;
256
257 return min_vruntime;
258}
259
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200260static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
Peter Zijlstrab0ffd242007-10-15 17:00:12 +0200261{
262 s64 delta = (s64)(vruntime - min_vruntime);
263 if (delta < 0)
264 min_vruntime = vruntime;
265
266 return min_vruntime;
267}
268
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200269static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
Peter Zijlstra90146232007-10-15 17:00:05 +0200270{
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200271 return se->vruntime - cfs_rq->min_vruntime;
Peter Zijlstra90146232007-10-15 17:00:05 +0200272}
273
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200274static void update_min_vruntime(struct cfs_rq *cfs_rq)
275{
276 u64 vruntime = cfs_rq->min_vruntime;
277
278 if (cfs_rq->curr)
279 vruntime = cfs_rq->curr->vruntime;
280
281 if (cfs_rq->rb_leftmost) {
282 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
283 struct sched_entity,
284 run_node);
285
286 if (vruntime == cfs_rq->min_vruntime)
287 vruntime = se->vruntime;
288 else
289 vruntime = min_vruntime(vruntime, se->vruntime);
290 }
291
292 cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
293}
294
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200295/*
296 * Enqueue an entity into the rb-tree:
297 */
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200298static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200299{
300 struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
301 struct rb_node *parent = NULL;
302 struct sched_entity *entry;
Peter Zijlstra90146232007-10-15 17:00:05 +0200303 s64 key = entity_key(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200304 int leftmost = 1;
305
306 /*
307 * Find the right place in the rbtree:
308 */
309 while (*link) {
310 parent = *link;
311 entry = rb_entry(parent, struct sched_entity, run_node);
312 /*
313 * We dont care about collisions. Nodes with
314 * the same key stay together.
315 */
Peter Zijlstra90146232007-10-15 17:00:05 +0200316 if (key < entity_key(cfs_rq, entry)) {
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200317 link = &parent->rb_left;
318 } else {
319 link = &parent->rb_right;
320 leftmost = 0;
321 }
322 }
323
324 /*
325 * Maintain a cache of leftmost tree entries (it is frequently
326 * used):
327 */
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200328 if (leftmost)
Ingo Molnar57cb4992007-10-15 17:00:11 +0200329 cfs_rq->rb_leftmost = &se->run_node;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200330
331 rb_link_node(&se->run_node, parent, link);
332 rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200333}
334
Ingo Molnar0702e3e2007-10-15 17:00:14 +0200335static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200336{
Peter Zijlstra3fe69742008-03-14 20:55:51 +0100337 if (cfs_rq->rb_leftmost == &se->run_node) {
338 struct rb_node *next_node;
Peter Zijlstra3fe69742008-03-14 20:55:51 +0100339
340 next_node = rb_next(&se->run_node);
341 cfs_rq->rb_leftmost = next_node;
Peter Zijlstra3fe69742008-03-14 20:55:51 +0100342 }
Ingo Molnare9acbff2007-10-15 17:00:04 +0200343
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200344 rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200345}
346
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200347static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
348{
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100349 struct rb_node *left = cfs_rq->rb_leftmost;
350
351 if (!left)
352 return NULL;
353
354 return rb_entry(left, struct sched_entity, run_node);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200355}
356
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100357static struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200358{
Ingo Molnar7eee3e62008-02-22 10:32:21 +0100359 struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200360
Balbir Singh70eee742008-02-22 13:25:53 +0530361 if (!last)
362 return NULL;
Ingo Molnar7eee3e62008-02-22 10:32:21 +0100363
364 return rb_entry(last, struct sched_entity, run_node);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200365}
366
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200367/**************************************************************
368 * Scheduling class statistics methods:
369 */
370
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100371#ifdef CONFIG_SCHED_DEBUG
372int sched_nr_latency_handler(struct ctl_table *table, int write,
373 struct file *filp, void __user *buffer, size_t *lenp,
374 loff_t *ppos)
375{
376 int ret = proc_dointvec_minmax(table, write, filp, buffer, lenp, ppos);
377
378 if (ret || !write)
379 return ret;
380
381 sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
382 sysctl_sched_min_granularity);
383
384 return 0;
385}
386#endif
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200387
388/*
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200389 * delta *= P[w / rw]
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200390 */
391static inline unsigned long
392calc_delta_weight(unsigned long delta, struct sched_entity *se)
393{
394 for_each_sched_entity(se) {
395 delta = calc_delta_mine(delta,
396 se->load.weight, &cfs_rq_of(se)->load);
397 }
398
399 return delta;
400}
401
402/*
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200403 * delta /= w
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200404 */
405static inline unsigned long
406calc_delta_fair(unsigned long delta, struct sched_entity *se)
407{
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200408 if (unlikely(se->load.weight != NICE_0_LOAD))
409 delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200410
411 return delta;
412}
413
414/*
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200415 * The idea is to set a period in which each task runs once.
416 *
417 * When there are too many tasks (sysctl_sched_nr_latency) we have to stretch
418 * this period because otherwise the slices get too small.
419 *
420 * p = (nr <= nl) ? l : l*nr/nl
421 */
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200422static u64 __sched_period(unsigned long nr_running)
423{
424 u64 period = sysctl_sched_latency;
Peter Zijlstrab2be5e92007-11-09 22:39:37 +0100425 unsigned long nr_latency = sched_nr_latency;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200426
427 if (unlikely(nr_running > nr_latency)) {
Peter Zijlstra4bf0b772008-01-25 21:08:21 +0100428 period = sysctl_sched_min_granularity;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200429 period *= nr_running;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200430 }
431
432 return period;
433}
434
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200435/*
436 * We calculate the wall-time slice from the period by taking a part
437 * proportional to the weight.
438 *
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200439 * s = p*P[w/rw]
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200440 */
Peter Zijlstra6d0f0eb2007-10-15 17:00:05 +0200441static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
Peter Zijlstra21805082007-08-25 18:41:53 +0200442{
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200443 unsigned long nr_running = cfs_rq->nr_running;
444
445 if (unlikely(!se->on_rq))
446 nr_running++;
447
448 return calc_delta_weight(__sched_period(nr_running), se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200449}
450
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200451/*
Peter Zijlstraac884de2008-04-19 19:45:00 +0200452 * We calculate the vruntime slice of a to be inserted task
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200453 *
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200454 * vs = s/w
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200455 */
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200456static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnar647e7ca2007-10-15 17:00:13 +0200457{
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200458 return calc_delta_fair(sched_slice(cfs_rq, se), se);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200459}
460
461/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200462 * Update the current task's runtime statistics. Skip current tasks that
463 * are not in our scheduling class.
464 */
465static inline void
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200466__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
467 unsigned long delta_exec)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200468{
Ingo Molnarbbdba7c2007-10-15 17:00:06 +0200469 unsigned long delta_exec_weighted;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200470
Ingo Molnar8179ca232007-08-02 17:41:40 +0200471 schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200472
473 curr->sum_exec_runtime += delta_exec;
Ingo Molnar7a62eab2007-10-15 17:00:06 +0200474 schedstat_add(cfs_rq, exec_clock, delta_exec);
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200475 delta_exec_weighted = calc_delta_fair(delta_exec, curr);
Ingo Molnare9acbff2007-10-15 17:00:04 +0200476 curr->vruntime += delta_exec_weighted;
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200477 update_min_vruntime(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200478}
479
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200480static void update_curr(struct cfs_rq *cfs_rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200481{
Ingo Molnar429d43b2007-10-15 17:00:03 +0200482 struct sched_entity *curr = cfs_rq->curr;
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200483 u64 now = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200484 unsigned long delta_exec;
485
486 if (unlikely(!curr))
487 return;
488
489 /*
490 * Get the amount of time the current task was running
491 * since the last time we changed load (this cannot
492 * overflow on 32 bits):
493 */
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200494 delta_exec = (unsigned long)(now - curr->exec_start);
Peter Zijlstra34f28ec2008-12-16 08:45:31 +0100495 if (!delta_exec)
496 return;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200497
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200498 __update_curr(cfs_rq, curr, delta_exec);
499 curr->exec_start = now;
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100500
501 if (entity_is_task(curr)) {
502 struct task_struct *curtask = task_of(curr);
503
504 cpuacct_charge(curtask, delta_exec);
Frank Mayharf06febc2008-09-12 09:54:39 -0700505 account_group_exec_runtime(curtask, delta_exec);
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100506 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200507}
508
509static inline void
Ingo Molnar5870db52007-08-09 11:16:47 +0200510update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200511{
Ingo Molnard2819182007-08-09 11:16:47 +0200512 schedstat_set(se->wait_start, rq_of(cfs_rq)->clock);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200513}
514
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200515/*
516 * Task is being enqueued - update stats:
517 */
Ingo Molnard2417e52007-08-09 11:16:47 +0200518static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200519{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200520 /*
521 * Are we enqueueing a waiting task? (for current tasks
522 * a dequeue/enqueue event is a NOP)
523 */
Ingo Molnar429d43b2007-10-15 17:00:03 +0200524 if (se != cfs_rq->curr)
Ingo Molnar5870db52007-08-09 11:16:47 +0200525 update_stats_wait_start(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200526}
527
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200528static void
Ingo Molnar9ef0a962007-08-09 11:16:47 +0200529update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200530{
Ingo Molnarbbdba7c2007-10-15 17:00:06 +0200531 schedstat_set(se->wait_max, max(se->wait_max,
532 rq_of(cfs_rq)->clock - se->wait_start));
Arjan van de Ven6d082592008-01-25 21:08:35 +0100533 schedstat_set(se->wait_count, se->wait_count + 1);
534 schedstat_set(se->wait_sum, se->wait_sum +
535 rq_of(cfs_rq)->clock - se->wait_start);
Ingo Molnar6cfb0d52007-08-02 17:41:40 +0200536 schedstat_set(se->wait_start, 0);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200537}
538
539static inline void
Ingo Molnar19b6a2e2007-08-09 11:16:48 +0200540update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200541{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200542 /*
543 * Mark the end of the wait period if dequeueing a
544 * waiting task:
545 */
Ingo Molnar429d43b2007-10-15 17:00:03 +0200546 if (se != cfs_rq->curr)
Ingo Molnar9ef0a962007-08-09 11:16:47 +0200547 update_stats_wait_end(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200548}
549
550/*
551 * We are picking a new current task - update its stats:
552 */
553static inline void
Ingo Molnar79303e92007-08-09 11:16:47 +0200554update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200555{
556 /*
557 * We are starting a new run period:
558 */
Ingo Molnard2819182007-08-09 11:16:47 +0200559 se->exec_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200560}
561
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200562/**************************************************
563 * Scheduling class queueing methods:
564 */
565
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200566#if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
567static void
568add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
569{
570 cfs_rq->task_weight += weight;
571}
572#else
573static inline void
574add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
575{
576}
577#endif
578
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200579static void
580account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
581{
582 update_load_add(&cfs_rq->load, se->load.weight);
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200583 if (!parent_entity(se))
584 inc_cpu_load(rq_of(cfs_rq), se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530585 if (entity_is_task(se)) {
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200586 add_cfs_task_weight(cfs_rq, se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530587 list_add(&se->group_node, &cfs_rq->tasks);
588 }
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200589 cfs_rq->nr_running++;
590 se->on_rq = 1;
591}
592
593static void
594account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
595{
596 update_load_sub(&cfs_rq->load, se->load.weight);
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200597 if (!parent_entity(se))
598 dec_cpu_load(rq_of(cfs_rq), se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530599 if (entity_is_task(se)) {
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200600 add_cfs_task_weight(cfs_rq, -se->load.weight);
Bharata B Raob87f1722008-09-25 09:53:54 +0530601 list_del_init(&se->group_node);
602 }
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200603 cfs_rq->nr_running--;
604 se->on_rq = 0;
605}
606
Ingo Molnar2396af62007-08-09 11:16:48 +0200607static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200608{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200609#ifdef CONFIG_SCHEDSTATS
610 if (se->sleep_start) {
Ingo Molnard2819182007-08-09 11:16:47 +0200611 u64 delta = rq_of(cfs_rq)->clock - se->sleep_start;
Arjan van de Ven97455122008-01-25 21:08:34 +0100612 struct task_struct *tsk = task_of(se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200613
614 if ((s64)delta < 0)
615 delta = 0;
616
617 if (unlikely(delta > se->sleep_max))
618 se->sleep_max = delta;
619
620 se->sleep_start = 0;
621 se->sum_sleep_runtime += delta;
Arjan van de Ven97455122008-01-25 21:08:34 +0100622
623 account_scheduler_latency(tsk, delta >> 10, 1);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200624 }
625 if (se->block_start) {
Ingo Molnard2819182007-08-09 11:16:47 +0200626 u64 delta = rq_of(cfs_rq)->clock - se->block_start;
Arjan van de Ven97455122008-01-25 21:08:34 +0100627 struct task_struct *tsk = task_of(se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200628
629 if ((s64)delta < 0)
630 delta = 0;
631
632 if (unlikely(delta > se->block_max))
633 se->block_max = delta;
634
635 se->block_start = 0;
636 se->sum_sleep_runtime += delta;
Ingo Molnar30084fb2007-10-02 14:13:08 +0200637
638 /*
639 * Blocking time is in units of nanosecs, so shift by 20 to
640 * get a milliseconds-range estimation of the amount of
641 * time that the task spent sleeping:
642 */
643 if (unlikely(prof_on == SLEEP_PROFILING)) {
Ingo Molnare22f5bb2007-10-15 17:00:06 +0200644
Ingo Molnar30084fb2007-10-02 14:13:08 +0200645 profile_hits(SLEEP_PROFILING, (void *)get_wchan(tsk),
646 delta >> 20);
647 }
Arjan van de Ven97455122008-01-25 21:08:34 +0100648 account_scheduler_latency(tsk, delta >> 10, 0);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200649 }
650#endif
651}
652
Peter Zijlstraddc97292007-10-15 17:00:10 +0200653static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
654{
655#ifdef CONFIG_SCHED_DEBUG
656 s64 d = se->vruntime - cfs_rq->min_vruntime;
657
658 if (d < 0)
659 d = -d;
660
661 if (d > 3*sysctl_sched_latency)
662 schedstat_inc(cfs_rq, nr_spread_over);
663#endif
664}
665
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200666static void
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200667place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
668{
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200669 u64 vruntime = cfs_rq->min_vruntime;
Peter Zijlstra94dfb5e2007-10-15 17:00:05 +0200670
Peter Zijlstra2cb86002007-11-09 22:39:37 +0100671 /*
672 * The 'current' period is already promised to the current tasks,
673 * however the extra weight of the new task will slow them down a
674 * little, place the new task so that it fits in the slot that
675 * stays open at the end.
676 */
Peter Zijlstra94dfb5e2007-10-15 17:00:05 +0200677 if (initial && sched_feat(START_DEBIT))
Peter Zijlstraf9c0b092008-10-17 19:27:04 +0200678 vruntime += sched_vslice(cfs_rq, se);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200679
Ingo Molnar8465e792007-10-15 17:00:11 +0200680 if (!initial) {
Peter Zijlstra2cb86002007-11-09 22:39:37 +0100681 /* sleeps upto a single latency don't count. */
Peter Zijlstraa7be37a2008-06-27 13:41:11 +0200682 if (sched_feat(NEW_FAIR_SLEEPERS)) {
683 unsigned long thresh = sysctl_sched_latency;
684
685 /*
686 * convert the sleeper threshold into virtual time
687 */
688 if (sched_feat(NORMALIZED_SLEEPER))
689 thresh = calc_delta_fair(thresh, se);
690
691 vruntime -= thresh;
692 }
Ingo Molnar94359f02007-10-15 17:00:11 +0200693
Peter Zijlstra2cb86002007-11-09 22:39:37 +0100694 /* ensure we never gain time by being placed backwards. */
695 vruntime = max_vruntime(se->vruntime, vruntime);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200696 }
697
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200698 se->vruntime = vruntime;
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200699}
700
701static void
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200702enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200703{
704 /*
Dmitry Adamushkoa2a2d682007-10-15 17:00:13 +0200705 * Update run-time statistics of the 'current'.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200706 */
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200707 update_curr(cfs_rq);
Peter Zijlstraa9922412008-05-05 23:56:17 +0200708 account_entity_enqueue(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200709
Ingo Molnare9acbff2007-10-15 17:00:04 +0200710 if (wakeup) {
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200711 place_entity(cfs_rq, se, 0);
Ingo Molnar2396af62007-08-09 11:16:48 +0200712 enqueue_sleeper(cfs_rq, se);
Ingo Molnare9acbff2007-10-15 17:00:04 +0200713 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200714
Ingo Molnard2417e52007-08-09 11:16:47 +0200715 update_stats_enqueue(cfs_rq, se);
Peter Zijlstraddc97292007-10-15 17:00:10 +0200716 check_spread(cfs_rq, se);
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200717 if (se != cfs_rq->curr)
718 __enqueue_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200719}
720
Peter Zijlstra2002c692008-11-11 11:52:33 +0100721static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
722{
723 if (cfs_rq->last == se)
724 cfs_rq->last = NULL;
725
726 if (cfs_rq->next == se)
727 cfs_rq->next = NULL;
728}
729
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200730static void
Ingo Molnar525c2712007-08-09 11:16:48 +0200731dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200732{
Dmitry Adamushkoa2a2d682007-10-15 17:00:13 +0200733 /*
734 * Update run-time statistics of the 'current'.
735 */
736 update_curr(cfs_rq);
737
Ingo Molnar19b6a2e2007-08-09 11:16:48 +0200738 update_stats_dequeue(cfs_rq, se);
Dmitry Adamushkodb36cc72007-10-15 17:00:06 +0200739 if (sleep) {
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200740#ifdef CONFIG_SCHEDSTATS
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200741 if (entity_is_task(se)) {
742 struct task_struct *tsk = task_of(se);
743
744 if (tsk->state & TASK_INTERRUPTIBLE)
Ingo Molnard2819182007-08-09 11:16:47 +0200745 se->sleep_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200746 if (tsk->state & TASK_UNINTERRUPTIBLE)
Ingo Molnard2819182007-08-09 11:16:47 +0200747 se->block_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200748 }
Dmitry Adamushkodb36cc72007-10-15 17:00:06 +0200749#endif
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200750 }
751
Peter Zijlstra2002c692008-11-11 11:52:33 +0100752 clear_buddies(cfs_rq, se);
Peter Zijlstra47932412008-11-04 21:25:09 +0100753
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200754 if (se != cfs_rq->curr)
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200755 __dequeue_entity(cfs_rq, se);
756 account_entity_dequeue(cfs_rq, se);
Peter Zijlstra1af5f732008-10-24 11:06:13 +0200757 update_min_vruntime(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200758}
759
760/*
761 * Preempt the current task with a newly woken task if needed:
762 */
Peter Zijlstra7c92e542007-09-05 14:32:49 +0200763static void
Ingo Molnar2e09bf52007-10-15 17:00:05 +0200764check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200765{
Peter Zijlstra11697832007-09-05 14:32:49 +0200766 unsigned long ideal_runtime, delta_exec;
767
Peter Zijlstra6d0f0eb2007-10-15 17:00:05 +0200768 ideal_runtime = sched_slice(cfs_rq, curr);
Peter Zijlstra11697832007-09-05 14:32:49 +0200769 delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
Ingo Molnar3e3e13f2007-11-09 22:39:39 +0100770 if (delta_exec > ideal_runtime)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200771 resched_task(rq_of(cfs_rq)->curr);
772}
773
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200774static void
Ingo Molnar8494f412007-08-09 11:16:48 +0200775set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200776{
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200777 /* 'current' is not kept within the tree. */
778 if (se->on_rq) {
779 /*
780 * Any task has to be enqueued before it get to execute on
781 * a CPU. So account for the time it spent waiting on the
782 * runqueue.
783 */
784 update_stats_wait_end(cfs_rq, se);
785 __dequeue_entity(cfs_rq, se);
786 }
787
Ingo Molnar79303e92007-08-09 11:16:47 +0200788 update_stats_curr_start(cfs_rq, se);
Ingo Molnar429d43b2007-10-15 17:00:03 +0200789 cfs_rq->curr = se;
Ingo Molnareba1ed42007-10-15 17:00:02 +0200790#ifdef CONFIG_SCHEDSTATS
791 /*
792 * Track our maximum slice length, if the CPU's load is at
793 * least twice that of our own weight (i.e. dont track it
794 * when there are only lesser-weight tasks around):
795 */
Dmitry Adamushko495eca42007-10-15 17:00:06 +0200796 if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
Ingo Molnareba1ed42007-10-15 17:00:02 +0200797 se->slice_max = max(se->slice_max,
798 se->sum_exec_runtime - se->prev_sum_exec_runtime);
799 }
800#endif
Peter Zijlstra4a55b452007-09-05 14:32:49 +0200801 se->prev_sum_exec_runtime = se->sum_exec_runtime;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200802}
803
Peter Zijlstra3f3a4902008-10-24 11:06:16 +0200804static int
805wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
806
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100807static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
Peter Zijlstraaa2ac252008-03-14 21:12:12 +0100808{
Peter Zijlstraf4b67552008-11-04 21:25:07 +0100809 struct sched_entity *se = __pick_next_entity(cfs_rq);
810
Peter Zijlstra47932412008-11-04 21:25:09 +0100811 if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, se) < 1)
812 return cfs_rq->next;
Peter Zijlstraaa2ac252008-03-14 21:12:12 +0100813
Peter Zijlstra47932412008-11-04 21:25:09 +0100814 if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, se) < 1)
815 return cfs_rq->last;
816
817 return se;
Peter Zijlstraaa2ac252008-03-14 21:12:12 +0100818}
819
Ingo Molnarab6cde22007-08-09 11:16:48 +0200820static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200821{
822 /*
823 * If still on the runqueue then deactivate_task()
824 * was not called and update_curr() has to be done:
825 */
826 if (prev->on_rq)
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200827 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200828
Peter Zijlstraddc97292007-10-15 17:00:10 +0200829 check_spread(cfs_rq, prev);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200830 if (prev->on_rq) {
Ingo Molnar5870db52007-08-09 11:16:47 +0200831 update_stats_wait_start(cfs_rq, prev);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200832 /* Put 'current' back into the tree. */
833 __enqueue_entity(cfs_rq, prev);
834 }
Ingo Molnar429d43b2007-10-15 17:00:03 +0200835 cfs_rq->curr = NULL;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200836}
837
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100838static void
839entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200840{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200841 /*
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200842 * Update run-time statistics of the 'current'.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200843 */
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200844 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200845
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100846#ifdef CONFIG_SCHED_HRTICK
847 /*
848 * queued ticks are scheduled to match the slice, so don't bother
849 * validating it and just reschedule.
850 */
Harvey Harrison983ed7a2008-04-24 18:17:55 -0700851 if (queued) {
852 resched_task(rq_of(cfs_rq)->curr);
853 return;
854 }
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100855 /*
856 * don't let the period tick interfere with the hrtick preemption
857 */
858 if (!sched_feat(DOUBLE_TICK) &&
859 hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
860 return;
861#endif
862
Peter Zijlstrace6c1312007-10-15 17:00:14 +0200863 if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
Ingo Molnar2e09bf52007-10-15 17:00:05 +0200864 check_preempt_tick(cfs_rq, curr);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200865}
866
867/**************************************************
868 * CFS operations on tasks:
869 */
870
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100871#ifdef CONFIG_SCHED_HRTICK
872static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
873{
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100874 struct sched_entity *se = &p->se;
875 struct cfs_rq *cfs_rq = cfs_rq_of(se);
876
877 WARN_ON(task_rq(p) != rq);
878
879 if (hrtick_enabled(rq) && cfs_rq->nr_running > 1) {
880 u64 slice = sched_slice(cfs_rq, se);
881 u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
882 s64 delta = slice - ran;
883
884 if (delta < 0) {
885 if (rq->curr == p)
886 resched_task(p);
887 return;
888 }
889
890 /*
891 * Don't schedule slices shorter than 10000ns, that just
892 * doesn't make sense. Rely on vruntime for fairness.
893 */
Peter Zijlstra31656512008-07-18 18:01:23 +0200894 if (rq->curr != p)
Peter Zijlstra157124c2008-07-28 11:53:11 +0200895 delta = max_t(s64, 10000LL, delta);
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100896
Peter Zijlstra31656512008-07-18 18:01:23 +0200897 hrtick_start(rq, delta);
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100898 }
899}
Peter Zijlstraa4c2f002008-10-17 19:27:03 +0200900
901/*
902 * called from enqueue/dequeue and updates the hrtick when the
903 * current task is from our class and nr_running is low enough
904 * to matter.
905 */
906static void hrtick_update(struct rq *rq)
907{
908 struct task_struct *curr = rq->curr;
909
910 if (curr->sched_class != &fair_sched_class)
911 return;
912
913 if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
914 hrtick_start_fair(rq, curr);
915}
Dhaval Giani55e12e52008-06-24 23:39:43 +0530916#else /* !CONFIG_SCHED_HRTICK */
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100917static inline void
918hrtick_start_fair(struct rq *rq, struct task_struct *p)
919{
920}
Peter Zijlstraa4c2f002008-10-17 19:27:03 +0200921
922static inline void hrtick_update(struct rq *rq)
923{
924}
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100925#endif
926
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200927/*
928 * The enqueue_task method is called before nr_running is
929 * increased. Here we update the fair scheduling stats and
930 * then put the task into the rbtree:
931 */
Ingo Molnarfd390f62007-08-09 11:16:48 +0200932static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200933{
934 struct cfs_rq *cfs_rq;
Peter Zijlstra62fb1852008-02-25 17:34:02 +0100935 struct sched_entity *se = &p->se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200936
937 for_each_sched_entity(se) {
Peter Zijlstra62fb1852008-02-25 17:34:02 +0100938 if (se->on_rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200939 break;
940 cfs_rq = cfs_rq_of(se);
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200941 enqueue_entity(cfs_rq, se, wakeup);
Srivatsa Vaddagirib9fa3df2007-10-15 17:00:12 +0200942 wakeup = 1;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200943 }
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100944
Peter Zijlstraa4c2f002008-10-17 19:27:03 +0200945 hrtick_update(rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200946}
947
948/*
949 * The dequeue_task method is called before nr_running is
950 * decreased. We remove the task from the rbtree and
951 * update the fair scheduling stats:
952 */
Ingo Molnarf02231e2007-08-09 11:16:48 +0200953static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200954{
955 struct cfs_rq *cfs_rq;
Peter Zijlstra62fb1852008-02-25 17:34:02 +0100956 struct sched_entity *se = &p->se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200957
958 for_each_sched_entity(se) {
959 cfs_rq = cfs_rq_of(se);
Ingo Molnar525c2712007-08-09 11:16:48 +0200960 dequeue_entity(cfs_rq, se, sleep);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200961 /* Don't dequeue parent if it has other entities besides us */
Peter Zijlstra62fb1852008-02-25 17:34:02 +0100962 if (cfs_rq->load.weight)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200963 break;
Srivatsa Vaddagirib9fa3df2007-10-15 17:00:12 +0200964 sleep = 1;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200965 }
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +0100966
Peter Zijlstraa4c2f002008-10-17 19:27:03 +0200967 hrtick_update(rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200968}
969
970/*
Ingo Molnar1799e352007-09-19 23:34:46 +0200971 * sched_yield() support is very simple - we dequeue and enqueue.
972 *
973 * If compat_yield is turned on then we requeue to the end of the tree.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200974 */
Dmitry Adamushko4530d7a2007-10-15 17:00:08 +0200975static void yield_task_fair(struct rq *rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200976{
Ingo Molnardb292ca2007-12-04 17:04:39 +0100977 struct task_struct *curr = rq->curr;
978 struct cfs_rq *cfs_rq = task_cfs_rq(curr);
979 struct sched_entity *rightmost, *se = &curr->se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200980
981 /*
Ingo Molnar1799e352007-09-19 23:34:46 +0200982 * Are we the only task in the tree?
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200983 */
Ingo Molnar1799e352007-09-19 23:34:46 +0200984 if (unlikely(cfs_rq->nr_running == 1))
985 return;
986
Peter Zijlstra2002c692008-11-11 11:52:33 +0100987 clear_buddies(cfs_rq, se);
988
Ingo Molnardb292ca2007-12-04 17:04:39 +0100989 if (likely(!sysctl_sched_compat_yield) && curr->policy != SCHED_BATCH) {
Peter Zijlstra3e51f332008-05-03 18:29:28 +0200990 update_rq_clock(rq);
Ingo Molnar1799e352007-09-19 23:34:46 +0200991 /*
Dmitry Adamushkoa2a2d682007-10-15 17:00:13 +0200992 * Update run-time statistics of the 'current'.
Ingo Molnar1799e352007-09-19 23:34:46 +0200993 */
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +0200994 update_curr(cfs_rq);
Ingo Molnar1799e352007-09-19 23:34:46 +0200995
996 return;
997 }
998 /*
999 * Find the rightmost entry in the rbtree:
1000 */
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +02001001 rightmost = __pick_last_entity(cfs_rq);
Ingo Molnar1799e352007-09-19 23:34:46 +02001002 /*
1003 * Already in the rightmost position?
1004 */
Peter Zijlstra79b3fef2008-02-18 13:39:37 +01001005 if (unlikely(!rightmost || rightmost->vruntime < se->vruntime))
Ingo Molnar1799e352007-09-19 23:34:46 +02001006 return;
1007
1008 /*
1009 * Minimally necessary key value to be last in the tree:
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +02001010 * Upon rescheduling, sched_class::put_prev_task() will place
1011 * 'current' within the tree based on its new key value.
Ingo Molnar1799e352007-09-19 23:34:46 +02001012 */
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +02001013 se->vruntime = rightmost->vruntime + 1;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001014}
1015
1016/*
Gregory Haskinse7693a32008-01-25 21:08:09 +01001017 * wake_idle() will wake a task on an idle cpu if task->cpu is
1018 * not idle and an idle cpu is available. The span of cpus to
1019 * search starts with cpus closest then further out as needed,
1020 * so we always favor a closer, idle cpu.
Max Krasnyanskye761b772008-07-15 04:43:49 -07001021 * Domains may include CPUs that are not usable for migration,
1022 * hence we need to mask them out (cpu_active_map)
Gregory Haskinse7693a32008-01-25 21:08:09 +01001023 *
1024 * Returns the CPU we should wake onto.
1025 */
1026#if defined(ARCH_HAS_SCHED_WAKE_IDLE)
1027static int wake_idle(int cpu, struct task_struct *p)
1028{
1029 cpumask_t tmp;
1030 struct sched_domain *sd;
1031 int i;
1032
1033 /*
1034 * If it is idle, then it is the best cpu to run this task.
1035 *
1036 * This cpu is also the best, if it has more than one task already.
1037 * Siblings must be also busy(in most cases) as they didn't already
1038 * pickup the extra load from this cpu and hence we need not check
1039 * sibling runqueue info. This will avoid the checks and cache miss
1040 * penalities associated with that.
1041 */
Gregory Haskins104f6452008-04-28 12:40:01 -04001042 if (idle_cpu(cpu) || cpu_rq(cpu)->cfs.nr_running > 1)
Gregory Haskinse7693a32008-01-25 21:08:09 +01001043 return cpu;
1044
1045 for_each_domain(cpu, sd) {
Hidetoshi Seto1d3504f2008-04-15 14:04:23 +09001046 if ((sd->flags & SD_WAKE_IDLE)
1047 || ((sd->flags & SD_WAKE_IDLE_FAR)
1048 && !task_hot(p, task_rq(p)->clock, sd))) {
Gregory Haskinse7693a32008-01-25 21:08:09 +01001049 cpus_and(tmp, sd->span, p->cpus_allowed);
Max Krasnyanskye761b772008-07-15 04:43:49 -07001050 cpus_and(tmp, tmp, cpu_active_map);
Mike Travis363ab6f2008-05-12 21:21:13 +02001051 for_each_cpu_mask_nr(i, tmp) {
Gregory Haskinse7693a32008-01-25 21:08:09 +01001052 if (idle_cpu(i)) {
1053 if (i != task_cpu(p)) {
1054 schedstat_inc(p,
1055 se.nr_wakeups_idle);
1056 }
1057 return i;
1058 }
1059 }
1060 } else {
1061 break;
1062 }
1063 }
1064 return cpu;
1065}
Dhaval Giani55e12e52008-06-24 23:39:43 +05301066#else /* !ARCH_HAS_SCHED_WAKE_IDLE*/
Gregory Haskinse7693a32008-01-25 21:08:09 +01001067static inline int wake_idle(int cpu, struct task_struct *p)
1068{
1069 return cpu;
1070}
1071#endif
1072
1073#ifdef CONFIG_SMP
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001074
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001075#ifdef CONFIG_FAIR_GROUP_SCHED
Peter Zijlstraf5bfb7d2008-06-27 13:41:39 +02001076/*
1077 * effective_load() calculates the load change as seen from the root_task_group
1078 *
1079 * Adding load to a group doesn't make a group heavier, but can cause movement
1080 * of group shares between cpus. Assuming the shares were perfectly aligned one
1081 * can calculate the shift in shares.
1082 *
1083 * The problem is that perfectly aligning the shares is rather expensive, hence
1084 * we try to avoid doing that too often - see update_shares(), which ratelimits
1085 * this change.
1086 *
1087 * We compensate this by not only taking the current delta into account, but
1088 * also considering the delta between when the shares were last adjusted and
1089 * now.
1090 *
1091 * We still saw a performance dip, some tracing learned us that between
1092 * cgroup:/ and cgroup:/foo balancing the number of affine wakeups increased
1093 * significantly. Therefore try to bias the error in direction of failing
1094 * the affine wakeup.
1095 *
1096 */
Peter Zijlstraf1d239f2008-06-27 13:41:38 +02001097static long effective_load(struct task_group *tg, int cpu,
1098 long wl, long wg)
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001099{
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001100 struct sched_entity *se = tg->se[cpu];
Peter Zijlstraf1d239f2008-06-27 13:41:38 +02001101
1102 if (!tg->parent)
1103 return wl;
1104
1105 /*
Peter Zijlstraf5bfb7d2008-06-27 13:41:39 +02001106 * By not taking the decrease of shares on the other cpu into
1107 * account our error leans towards reducing the affine wakeups.
1108 */
1109 if (!wl && sched_feat(ASYM_EFF_LOAD))
1110 return wl;
1111
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001112 for_each_sched_entity(se) {
Peter Zijlstracb5ef422008-06-27 13:41:32 +02001113 long S, rw, s, a, b;
Peter Zijlstra940959e2008-09-23 15:33:42 +02001114 long more_w;
1115
1116 /*
1117 * Instead of using this increment, also add the difference
1118 * between when the shares were last updated and now.
1119 */
1120 more_w = se->my_q->load.weight - se->my_q->rq_weight;
1121 wl += more_w;
1122 wg += more_w;
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001123
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001124 S = se->my_q->tg->shares;
1125 s = se->my_q->shares;
Peter Zijlstraf1d239f2008-06-27 13:41:38 +02001126 rw = se->my_q->rq_weight;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001127
Peter Zijlstracb5ef422008-06-27 13:41:32 +02001128 a = S*(rw + wl);
1129 b = S*rw + s*wg;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001130
Peter Zijlstra940959e2008-09-23 15:33:42 +02001131 wl = s*(a-b);
1132
1133 if (likely(b))
1134 wl /= b;
1135
Peter Zijlstra83378262008-06-27 13:41:37 +02001136 /*
1137 * Assume the group is already running and will
1138 * thus already be accounted for in the weight.
1139 *
1140 * That is, moving shares between CPUs, does not
1141 * alter the group weight.
1142 */
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001143 wg = 0;
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001144 }
1145
1146 return wl;
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001147}
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001148
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001149#else
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001150
Peter Zijlstra83378262008-06-27 13:41:37 +02001151static inline unsigned long effective_load(struct task_group *tg, int cpu,
1152 unsigned long wl, unsigned long wg)
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001153{
Peter Zijlstra83378262008-06-27 13:41:37 +02001154 return wl;
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001155}
Peter Zijlstra4be9daa2008-06-27 13:41:30 +02001156
Peter Zijlstrabb3469a2008-06-27 13:41:27 +02001157#endif
1158
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001159static int
Amit K. Arora64b9e022008-09-30 17:15:39 +05301160wake_affine(struct sched_domain *this_sd, struct rq *this_rq,
Ingo Molnar4ae7d5c2008-03-19 01:42:00 +01001161 struct task_struct *p, int prev_cpu, int this_cpu, int sync,
1162 int idx, unsigned long load, unsigned long this_load,
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001163 unsigned int imbalance)
1164{
Ingo Molnar4ae7d5c2008-03-19 01:42:00 +01001165 struct task_struct *curr = this_rq->curr;
Peter Zijlstra83378262008-06-27 13:41:37 +02001166 struct task_group *tg;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001167 unsigned long tl = this_load;
1168 unsigned long tl_per_task;
Peter Zijlstra83378262008-06-27 13:41:37 +02001169 unsigned long weight;
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001170 int balanced;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001171
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001172 if (!(this_sd->flags & SD_WAKE_AFFINE) || !sched_feat(AFFINE_WAKEUPS))
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001173 return 0;
1174
Mike Galbraith0d130332008-10-24 11:06:14 +02001175 if (sync && (curr->se.avg_overlap > sysctl_sched_migration_cost ||
1176 p->se.avg_overlap > sysctl_sched_migration_cost))
1177 sync = 0;
Peter Zijlstra2fb76352008-10-08 09:16:04 +02001178
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001179 /*
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001180 * If sync wakeup then subtract the (maximum possible)
1181 * effect of the currently running task from the load
1182 * of the current CPU:
1183 */
Peter Zijlstra83378262008-06-27 13:41:37 +02001184 if (sync) {
1185 tg = task_group(current);
1186 weight = current->se.load.weight;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001187
Peter Zijlstra83378262008-06-27 13:41:37 +02001188 tl += effective_load(tg, this_cpu, -weight, -weight);
1189 load += effective_load(tg, prev_cpu, 0, -weight);
1190 }
1191
1192 tg = task_group(p);
1193 weight = p->se.load.weight;
1194
1195 balanced = 100*(tl + effective_load(tg, this_cpu, weight, weight)) <=
1196 imbalance*(load + effective_load(tg, prev_cpu, 0, weight));
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001197
1198 /*
1199 * If the currently running task will sleep within
1200 * a reasonable amount of time then attract this newly
1201 * woken task:
1202 */
Peter Zijlstra2fb76352008-10-08 09:16:04 +02001203 if (sync && balanced)
1204 return 1;
Mike Galbraithb3137bc2008-05-29 11:11:41 +02001205
1206 schedstat_inc(p, se.nr_wakeups_affine_attempts);
1207 tl_per_task = cpu_avg_load_per_task(this_cpu);
1208
Amit K. Arora64b9e022008-09-30 17:15:39 +05301209 if (balanced || (tl <= load && tl + target_load(prev_cpu, idx) <=
1210 tl_per_task)) {
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001211 /*
1212 * This domain has SD_WAKE_AFFINE and
1213 * p is cache cold in this domain, and
1214 * there is no bad imbalance.
1215 */
1216 schedstat_inc(this_sd, ttwu_move_affine);
1217 schedstat_inc(p, se.nr_wakeups_affine);
1218
1219 return 1;
1220 }
1221 return 0;
1222}
1223
Gregory Haskinse7693a32008-01-25 21:08:09 +01001224static int select_task_rq_fair(struct task_struct *p, int sync)
1225{
Gregory Haskinse7693a32008-01-25 21:08:09 +01001226 struct sched_domain *sd, *this_sd = NULL;
Ingo Molnarac192d32008-03-16 20:56:26 +01001227 int prev_cpu, this_cpu, new_cpu;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001228 unsigned long load, this_load;
Amit K. Arora64b9e022008-09-30 17:15:39 +05301229 struct rq *this_rq;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001230 unsigned int imbalance;
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001231 int idx;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001232
Ingo Molnarac192d32008-03-16 20:56:26 +01001233 prev_cpu = task_cpu(p);
Ingo Molnarac192d32008-03-16 20:56:26 +01001234 this_cpu = smp_processor_id();
Ingo Molnar4ae7d5c2008-03-19 01:42:00 +01001235 this_rq = cpu_rq(this_cpu);
Ingo Molnarac192d32008-03-16 20:56:26 +01001236 new_cpu = prev_cpu;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001237
Amit K. Arora64b9e022008-09-30 17:15:39 +05301238 if (prev_cpu == this_cpu)
1239 goto out;
Ingo Molnarac192d32008-03-16 20:56:26 +01001240 /*
1241 * 'this_sd' is the first domain that both
1242 * this_cpu and prev_cpu are present in:
1243 */
Gregory Haskinse7693a32008-01-25 21:08:09 +01001244 for_each_domain(this_cpu, sd) {
Ingo Molnarac192d32008-03-16 20:56:26 +01001245 if (cpu_isset(prev_cpu, sd->span)) {
Gregory Haskinse7693a32008-01-25 21:08:09 +01001246 this_sd = sd;
1247 break;
1248 }
1249 }
1250
1251 if (unlikely(!cpu_isset(this_cpu, p->cpus_allowed)))
Ingo Molnarf4827382008-03-16 21:21:47 +01001252 goto out;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001253
1254 /*
1255 * Check for affine wakeup and passive balancing possibilities.
1256 */
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001257 if (!this_sd)
Ingo Molnarf4827382008-03-16 21:21:47 +01001258 goto out;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001259
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001260 idx = this_sd->wake_idx;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001261
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001262 imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001263
Ingo Molnarac192d32008-03-16 20:56:26 +01001264 load = source_load(prev_cpu, idx);
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001265 this_load = target_load(this_cpu, idx);
Gregory Haskinse7693a32008-01-25 21:08:09 +01001266
Amit K. Arora64b9e022008-09-30 17:15:39 +05301267 if (wake_affine(this_sd, this_rq, p, prev_cpu, this_cpu, sync, idx,
Ingo Molnar4ae7d5c2008-03-19 01:42:00 +01001268 load, this_load, imbalance))
1269 return this_cpu;
1270
Ingo Molnar098fb9d2008-03-16 20:36:10 +01001271 /*
1272 * Start passive balancing when half the imbalance_pct
1273 * limit is reached.
1274 */
1275 if (this_sd->flags & SD_WAKE_BALANCE) {
1276 if (imbalance*this_load <= 100*load) {
1277 schedstat_inc(this_sd, ttwu_move_balance);
1278 schedstat_inc(p, se.nr_wakeups_passive);
Ingo Molnar4ae7d5c2008-03-19 01:42:00 +01001279 return this_cpu;
Gregory Haskinse7693a32008-01-25 21:08:09 +01001280 }
1281 }
1282
Ingo Molnarf4827382008-03-16 21:21:47 +01001283out:
Gregory Haskinse7693a32008-01-25 21:08:09 +01001284 return wake_idle(new_cpu, p);
1285}
1286#endif /* CONFIG_SMP */
1287
Peter Zijlstra0bbd33362008-04-19 19:44:57 +02001288static unsigned long wakeup_gran(struct sched_entity *se)
1289{
1290 unsigned long gran = sysctl_sched_wakeup_granularity;
1291
1292 /*
Peter Zijlstraa7be37a2008-06-27 13:41:11 +02001293 * More easily preempt - nice tasks, while not making it harder for
1294 * + nice tasks.
Peter Zijlstra0bbd33362008-04-19 19:44:57 +02001295 */
Peter Zijlstra464b7522008-10-24 11:06:15 +02001296 if (!sched_feat(ASYM_GRAN) || se->load.weight > NICE_0_LOAD)
1297 gran = calc_delta_fair(sysctl_sched_wakeup_granularity, se);
Peter Zijlstra0bbd33362008-04-19 19:44:57 +02001298
1299 return gran;
1300}
1301
1302/*
Peter Zijlstra464b7522008-10-24 11:06:15 +02001303 * Should 'se' preempt 'curr'.
1304 *
1305 * |s1
1306 * |s2
1307 * |s3
1308 * g
1309 * |<--->|c
1310 *
1311 * w(c, s1) = -1
1312 * w(c, s2) = 0
1313 * w(c, s3) = 1
1314 *
1315 */
1316static int
1317wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
1318{
1319 s64 gran, vdiff = curr->vruntime - se->vruntime;
1320
1321 if (vdiff <= 0)
1322 return -1;
1323
1324 gran = wakeup_gran(curr);
1325 if (vdiff > gran)
1326 return 1;
1327
1328 return 0;
1329}
1330
Peter Zijlstra02479092008-11-04 21:25:10 +01001331static void set_last_buddy(struct sched_entity *se)
1332{
1333 for_each_sched_entity(se)
1334 cfs_rq_of(se)->last = se;
1335}
1336
1337static void set_next_buddy(struct sched_entity *se)
1338{
1339 for_each_sched_entity(se)
1340 cfs_rq_of(se)->next = se;
1341}
1342
Peter Zijlstra464b7522008-10-24 11:06:15 +02001343/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001344 * Preempt the current task with a newly woken task if needed:
1345 */
Peter Zijlstra15afe092008-09-20 23:38:02 +02001346static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int sync)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001347{
1348 struct task_struct *curr = rq->curr;
Srivatsa Vaddagiri8651a862007-10-15 17:00:12 +02001349 struct sched_entity *se = &curr->se, *pse = &p->se;
Mike Galbraith03e89e42008-12-16 08:45:30 +01001350 struct cfs_rq *cfs_rq = task_cfs_rq(curr);
1351
1352 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001353
1354 if (unlikely(rt_prio(p->prio))) {
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001355 resched_task(curr);
1356 return;
1357 }
Peter Zijlstraaa2ac252008-03-14 21:12:12 +01001358
Peter Zijlstrad95f98d2008-11-04 21:25:08 +01001359 if (unlikely(p->sched_class != &fair_sched_class))
1360 return;
1361
Ingo Molnar4ae7d5c2008-03-19 01:42:00 +01001362 if (unlikely(se == pse))
1363 return;
1364
Peter Zijlstra47932412008-11-04 21:25:09 +01001365 /*
1366 * Only set the backward buddy when the current task is still on the
1367 * rq. This can happen when a wakeup gets interleaved with schedule on
1368 * the ->pre_schedule() or idle_balance() point, either of which can
1369 * drop the rq lock.
1370 *
1371 * Also, during early boot the idle thread is in the fair class, for
1372 * obvious reasons its a bad idea to schedule back to the idle thread.
1373 */
1374 if (sched_feat(LAST_BUDDY) && likely(se->on_rq && curr != rq->idle))
Peter Zijlstra02479092008-11-04 21:25:10 +01001375 set_last_buddy(se);
1376 set_next_buddy(pse);
Peter Zijlstra57fdc262008-09-23 15:33:45 +02001377
Bharata B Raoaec0a512008-08-28 14:42:49 +05301378 /*
1379 * We can come here with TIF_NEED_RESCHED already set from new task
1380 * wake up path.
1381 */
1382 if (test_tsk_need_resched(curr))
1383 return;
1384
Ingo Molnar91c234b2007-10-15 17:00:18 +02001385 /*
1386 * Batch tasks do not preempt (their preemption is driven by
1387 * the tick):
1388 */
1389 if (unlikely(p->policy == SCHED_BATCH))
1390 return;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001391
Ingo Molnar77d9cc42007-11-09 22:39:39 +01001392 if (!sched_feat(WAKEUP_PREEMPT))
1393 return;
Peter Zijlstrace6c1312007-10-15 17:00:14 +02001394
Peter Zijlstra2fb76352008-10-08 09:16:04 +02001395 if (sched_feat(WAKEUP_OVERLAP) && (sync ||
1396 (se->avg_overlap < sysctl_sched_migration_cost &&
1397 pse->avg_overlap < sysctl_sched_migration_cost))) {
Peter Zijlstra15afe092008-09-20 23:38:02 +02001398 resched_task(curr);
1399 return;
1400 }
1401
Peter Zijlstra464b7522008-10-24 11:06:15 +02001402 find_matching_se(&se, &pse);
1403
1404 while (se) {
1405 BUG_ON(!pse);
1406
1407 if (wakeup_preempt_entity(se, pse) == 1) {
1408 resched_task(curr);
1409 break;
1410 }
1411
1412 se = parent_entity(se);
1413 pse = parent_entity(pse);
1414 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001415}
1416
Ingo Molnarfb8d4722007-08-09 11:16:48 +02001417static struct task_struct *pick_next_task_fair(struct rq *rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001418{
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001419 struct task_struct *p;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001420 struct cfs_rq *cfs_rq = &rq->cfs;
1421 struct sched_entity *se;
1422
1423 if (unlikely(!cfs_rq->nr_running))
1424 return NULL;
1425
1426 do {
Ingo Molnar9948f4b2007-08-09 11:16:48 +02001427 se = pick_next_entity(cfs_rq);
Peter Zijlstraf4b67552008-11-04 21:25:07 +01001428 set_next_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001429 cfs_rq = group_cfs_rq(se);
1430 } while (cfs_rq);
1431
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001432 p = task_of(se);
1433 hrtick_start_fair(rq, p);
1434
1435 return p;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001436}
1437
1438/*
1439 * Account for a descheduled task:
1440 */
Ingo Molnar31ee5292007-08-09 11:16:49 +02001441static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001442{
1443 struct sched_entity *se = &prev->se;
1444 struct cfs_rq *cfs_rq;
1445
1446 for_each_sched_entity(se) {
1447 cfs_rq = cfs_rq_of(se);
Ingo Molnarab6cde22007-08-09 11:16:48 +02001448 put_prev_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001449 }
1450}
1451
Peter Williams681f3e62007-10-24 18:23:51 +02001452#ifdef CONFIG_SMP
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001453/**************************************************
1454 * Fair scheduling class load-balancing methods:
1455 */
1456
1457/*
1458 * Load-balancing iterator. Note: while the runqueue stays locked
1459 * during the whole iteration, the current task might be
1460 * dequeued so the iterator has to be dequeue-safe. Here we
1461 * achieve that by always pre-iterating before returning
1462 * the current task:
1463 */
Alexey Dobriyana9957442007-10-15 17:00:13 +02001464static struct task_struct *
Peter Zijlstra4a55bd52008-04-19 19:45:00 +02001465__load_balance_iterator(struct cfs_rq *cfs_rq, struct list_head *next)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001466{
Dhaval Giani354d60c2008-04-19 19:44:59 +02001467 struct task_struct *p = NULL;
1468 struct sched_entity *se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001469
Mike Galbraith77ae6512008-08-11 13:32:02 +02001470 if (next == &cfs_rq->tasks)
1471 return NULL;
1472
Bharata B Raob87f1722008-09-25 09:53:54 +05301473 se = list_entry(next, struct sched_entity, group_node);
1474 p = task_of(se);
1475 cfs_rq->balance_iterator = next->next;
Mike Galbraith77ae6512008-08-11 13:32:02 +02001476
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001477 return p;
1478}
1479
1480static struct task_struct *load_balance_start_fair(void *arg)
1481{
1482 struct cfs_rq *cfs_rq = arg;
1483
Peter Zijlstra4a55bd52008-04-19 19:45:00 +02001484 return __load_balance_iterator(cfs_rq, cfs_rq->tasks.next);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001485}
1486
1487static struct task_struct *load_balance_next_fair(void *arg)
1488{
1489 struct cfs_rq *cfs_rq = arg;
1490
Peter Zijlstra4a55bd52008-04-19 19:45:00 +02001491 return __load_balance_iterator(cfs_rq, cfs_rq->balance_iterator);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001492}
1493
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001494static unsigned long
1495__load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1496 unsigned long max_load_move, struct sched_domain *sd,
1497 enum cpu_idle_type idle, int *all_pinned, int *this_best_prio,
1498 struct cfs_rq *cfs_rq)
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001499{
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001500 struct rq_iterator cfs_rq_iterator;
Ingo Molnar6363ca52008-05-29 11:28:57 +02001501
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001502 cfs_rq_iterator.start = load_balance_start_fair;
1503 cfs_rq_iterator.next = load_balance_next_fair;
1504 cfs_rq_iterator.arg = cfs_rq;
Ingo Molnar6363ca52008-05-29 11:28:57 +02001505
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001506 return balance_tasks(this_rq, this_cpu, busiest,
1507 max_load_move, sd, idle, all_pinned,
1508 this_best_prio, &cfs_rq_iterator);
Ingo Molnar6363ca52008-05-29 11:28:57 +02001509}
Ingo Molnar6363ca52008-05-29 11:28:57 +02001510
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001511#ifdef CONFIG_FAIR_GROUP_SCHED
Ingo Molnar6363ca52008-05-29 11:28:57 +02001512static unsigned long
1513load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1514 unsigned long max_load_move,
1515 struct sched_domain *sd, enum cpu_idle_type idle,
1516 int *all_pinned, int *this_best_prio)
1517{
Ingo Molnar6363ca52008-05-29 11:28:57 +02001518 long rem_load_move = max_load_move;
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001519 int busiest_cpu = cpu_of(busiest);
1520 struct task_group *tg;
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001521
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001522 rcu_read_lock();
Peter Zijlstrac8cba852008-06-27 13:41:23 +02001523 update_h_load(busiest_cpu);
Peter Zijlstra62fb1852008-02-25 17:34:02 +01001524
Chris Friesencaea8a02008-09-22 11:06:09 -06001525 list_for_each_entry_rcu(tg, &task_groups, list) {
Peter Zijlstrac8cba852008-06-27 13:41:23 +02001526 struct cfs_rq *busiest_cfs_rq = tg->cfs_rq[busiest_cpu];
Peter Zijlstra42a3ac72008-06-27 13:41:29 +02001527 unsigned long busiest_h_load = busiest_cfs_rq->h_load;
1528 unsigned long busiest_weight = busiest_cfs_rq->load.weight;
Srivatsa Vaddagiri243e0e72008-06-27 13:41:36 +02001529 u64 rem_load, moved_load;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001530
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001531 /*
1532 * empty group
1533 */
Peter Zijlstrac8cba852008-06-27 13:41:23 +02001534 if (!busiest_cfs_rq->task_weight)
Ingo Molnar6363ca52008-05-29 11:28:57 +02001535 continue;
1536
Srivatsa Vaddagiri243e0e72008-06-27 13:41:36 +02001537 rem_load = (u64)rem_load_move * busiest_weight;
1538 rem_load = div_u64(rem_load, busiest_h_load + 1);
Ingo Molnar6363ca52008-05-29 11:28:57 +02001539
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001540 moved_load = __load_balance_fair(this_rq, this_cpu, busiest,
Srivatsa Vaddagiri53fecd82008-06-27 13:41:20 +02001541 rem_load, sd, idle, all_pinned, this_best_prio,
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001542 tg->cfs_rq[busiest_cpu]);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001543
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001544 if (!moved_load)
1545 continue;
1546
Peter Zijlstra42a3ac72008-06-27 13:41:29 +02001547 moved_load *= busiest_h_load;
Srivatsa Vaddagiri243e0e72008-06-27 13:41:36 +02001548 moved_load = div_u64(moved_load, busiest_weight + 1);
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001549
1550 rem_load_move -= moved_load;
1551 if (rem_load_move < 0)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001552 break;
1553 }
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001554 rcu_read_unlock();
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001555
Peter Williams43010652007-08-09 11:16:46 +02001556 return max_load_move - rem_load_move;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001557}
Peter Zijlstrac09595f2008-06-27 13:41:14 +02001558#else
1559static unsigned long
1560load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1561 unsigned long max_load_move,
1562 struct sched_domain *sd, enum cpu_idle_type idle,
1563 int *all_pinned, int *this_best_prio)
1564{
1565 return __load_balance_fair(this_rq, this_cpu, busiest,
1566 max_load_move, sd, idle, all_pinned,
1567 this_best_prio, &busiest->cfs);
1568}
1569#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001570
Peter Williamse1d14842007-10-24 18:23:51 +02001571static int
1572move_one_task_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1573 struct sched_domain *sd, enum cpu_idle_type idle)
1574{
1575 struct cfs_rq *busy_cfs_rq;
1576 struct rq_iterator cfs_rq_iterator;
1577
1578 cfs_rq_iterator.start = load_balance_start_fair;
1579 cfs_rq_iterator.next = load_balance_next_fair;
1580
1581 for_each_leaf_cfs_rq(busiest, busy_cfs_rq) {
1582 /*
1583 * pass busy_cfs_rq argument into
1584 * load_balance_[start|next]_fair iterators
1585 */
1586 cfs_rq_iterator.arg = busy_cfs_rq;
1587 if (iter_move_one_task(this_rq, this_cpu, busiest, sd, idle,
1588 &cfs_rq_iterator))
1589 return 1;
1590 }
1591
1592 return 0;
1593}
Dhaval Giani55e12e52008-06-24 23:39:43 +05301594#endif /* CONFIG_SMP */
Peter Williamse1d14842007-10-24 18:23:51 +02001595
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001596/*
1597 * scheduler tick hitting a task of our scheduling class:
1598 */
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001599static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001600{
1601 struct cfs_rq *cfs_rq;
1602 struct sched_entity *se = &curr->se;
1603
1604 for_each_sched_entity(se) {
1605 cfs_rq = cfs_rq_of(se);
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001606 entity_tick(cfs_rq, se, queued);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001607 }
1608}
1609
Ingo Molnar8eb172d2007-10-29 21:18:11 +01001610#define swap(a, b) do { typeof(a) tmp = (a); (a) = (b); (b) = tmp; } while (0)
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02001611
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001612/*
1613 * Share the fairness runtime between parent and child, thus the
1614 * total amount of pressure for CPU stays equal - new tasks
1615 * get a chance to run but frequent forkers are not allowed to
1616 * monopolize the CPU. Note: the parent runqueue is locked,
1617 * the child is not running yet.
1618 */
Ingo Molnaree0827d2007-08-09 11:16:49 +02001619static void task_new_fair(struct rq *rq, struct task_struct *p)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001620{
1621 struct cfs_rq *cfs_rq = task_cfs_rq(p);
Ingo Molnar429d43b2007-10-15 17:00:03 +02001622 struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
Ingo Molnar00bf7bf2007-10-15 17:00:14 +02001623 int this_cpu = smp_processor_id();
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001624
1625 sched_info_queued(p);
1626
Ting Yang7109c4422007-08-28 12:53:24 +02001627 update_curr(cfs_rq);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +02001628 place_entity(cfs_rq, se, 1);
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02001629
Srivatsa Vaddagiri3c90e6e2007-11-09 22:39:39 +01001630 /* 'curr' will be NULL if the child belongs to a different group */
Ingo Molnar00bf7bf2007-10-15 17:00:14 +02001631 if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
Srivatsa Vaddagiri3c90e6e2007-11-09 22:39:39 +01001632 curr && curr->vruntime < se->vruntime) {
Dmitry Adamushko87fefa32007-10-15 17:00:08 +02001633 /*
Ingo Molnaredcb60a2007-10-15 17:00:08 +02001634 * Upon rescheduling, sched_class::put_prev_task() will place
1635 * 'current' within the tree based on its new key value.
1636 */
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02001637 swap(curr->vruntime, se->vruntime);
Bharata B Raoaec0a512008-08-28 14:42:49 +05301638 resched_task(rq->curr);
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02001639 }
1640
Srivatsa Vaddagirib9dca1e2007-10-17 16:55:11 +02001641 enqueue_task_fair(rq, p, 0);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001642}
1643
Steven Rostedtcb469842008-01-25 21:08:22 +01001644/*
1645 * Priority of the task has changed. Check to see if we preempt
1646 * the current task.
1647 */
1648static void prio_changed_fair(struct rq *rq, struct task_struct *p,
1649 int oldprio, int running)
1650{
1651 /*
1652 * Reschedule if we are currently running on this runqueue and
1653 * our priority decreased, or if we are not currently running on
1654 * this runqueue and our priority is higher than the current's
1655 */
1656 if (running) {
1657 if (p->prio > oldprio)
1658 resched_task(rq->curr);
1659 } else
Peter Zijlstra15afe092008-09-20 23:38:02 +02001660 check_preempt_curr(rq, p, 0);
Steven Rostedtcb469842008-01-25 21:08:22 +01001661}
1662
1663/*
1664 * We switched to the sched_fair class.
1665 */
1666static void switched_to_fair(struct rq *rq, struct task_struct *p,
1667 int running)
1668{
1669 /*
1670 * We were most likely switched from sched_rt, so
1671 * kick off the schedule if running, otherwise just see
1672 * if we can still preempt the current task.
1673 */
1674 if (running)
1675 resched_task(rq->curr);
1676 else
Peter Zijlstra15afe092008-09-20 23:38:02 +02001677 check_preempt_curr(rq, p, 0);
Steven Rostedtcb469842008-01-25 21:08:22 +01001678}
1679
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001680/* Account for a task changing its policy or group.
1681 *
1682 * This routine is mostly called to set cfs_rq->curr field when a task
1683 * migrates between groups/classes.
1684 */
1685static void set_curr_task_fair(struct rq *rq)
1686{
1687 struct sched_entity *se = &rq->curr->se;
1688
1689 for_each_sched_entity(se)
1690 set_next_entity(cfs_rq_of(se), se);
1691}
1692
Peter Zijlstra810b3812008-02-29 15:21:01 -05001693#ifdef CONFIG_FAIR_GROUP_SCHED
1694static void moved_group_fair(struct task_struct *p)
1695{
1696 struct cfs_rq *cfs_rq = task_cfs_rq(p);
1697
1698 update_curr(cfs_rq);
1699 place_entity(cfs_rq, &p->se, 1);
1700}
1701#endif
1702
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001703/*
1704 * All the scheduling class methods:
1705 */
Ingo Molnar5522d5d2007-10-15 17:00:12 +02001706static const struct sched_class fair_sched_class = {
1707 .next = &idle_sched_class,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001708 .enqueue_task = enqueue_task_fair,
1709 .dequeue_task = dequeue_task_fair,
1710 .yield_task = yield_task_fair,
1711
Ingo Molnar2e09bf52007-10-15 17:00:05 +02001712 .check_preempt_curr = check_preempt_wakeup,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001713
1714 .pick_next_task = pick_next_task_fair,
1715 .put_prev_task = put_prev_task_fair,
1716
Peter Williams681f3e62007-10-24 18:23:51 +02001717#ifdef CONFIG_SMP
Li Zefan4ce72a22008-10-22 15:25:26 +08001718 .select_task_rq = select_task_rq_fair,
1719
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001720 .load_balance = load_balance_fair,
Peter Williamse1d14842007-10-24 18:23:51 +02001721 .move_one_task = move_one_task_fair,
Peter Williams681f3e62007-10-24 18:23:51 +02001722#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001723
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001724 .set_curr_task = set_curr_task_fair,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001725 .task_tick = task_tick_fair,
1726 .task_new = task_new_fair,
Steven Rostedtcb469842008-01-25 21:08:22 +01001727
1728 .prio_changed = prio_changed_fair,
1729 .switched_to = switched_to_fair,
Peter Zijlstra810b3812008-02-29 15:21:01 -05001730
1731#ifdef CONFIG_FAIR_GROUP_SCHED
1732 .moved_group = moved_group_fair,
1733#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001734};
1735
1736#ifdef CONFIG_SCHED_DEBUG
Ingo Molnar5cef9ec2007-08-09 11:16:47 +02001737static void print_cfs_stats(struct seq_file *m, int cpu)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001738{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001739 struct cfs_rq *cfs_rq;
1740
Peter Zijlstra5973e5b2008-01-25 21:08:34 +01001741 rcu_read_lock();
Ingo Molnarc3b64f12007-08-09 11:16:51 +02001742 for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
Ingo Molnar5cef9ec2007-08-09 11:16:47 +02001743 print_cfs_rq(m, cpu, cfs_rq);
Peter Zijlstra5973e5b2008-01-25 21:08:34 +01001744 rcu_read_unlock();
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001745}
1746#endif