blob: 57e7f3672fd7c61f4b51ffcdb7a09bec525626e5 [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
23/*
Peter Zijlstra21805082007-08-25 18:41:53 +020024 * Targeted preemption latency for CPU-bound tasks:
25 * (default: 20ms, units: nanoseconds)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020026 *
Peter Zijlstra21805082007-08-25 18:41:53 +020027 * NOTE: this latency value is not the same as the concept of
28 * 'timeslice length' - timeslices in CFS are of variable length.
29 * (to see the precise effective timeslice length of your workload,
30 * run vmstat and monitor the context-switches field)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020031 *
32 * On SMP systems the value of this is multiplied by the log2 of the
33 * number of CPUs. (i.e. factor 2x on 2-way systems, 3x on 4-way
34 * systems, 4x on 8-way systems, 5x on 16-way systems, etc.)
Peter Zijlstra21805082007-08-25 18:41:53 +020035 * Targeted preemption latency for CPU-bound tasks:
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020036 */
Ingo Molnar2bd8e6d2007-10-15 17:00:02 +020037const_debug unsigned int sysctl_sched_latency = 20000000ULL;
38
39/*
40 * After fork, child runs first. (default) If set to 0 then
41 * parent will (try to) run first.
42 */
43const_debug unsigned int sysctl_sched_child_runs_first = 1;
Peter Zijlstra21805082007-08-25 18:41:53 +020044
45/*
46 * Minimal preemption granularity for CPU-bound tasks:
47 * (default: 2 msec, units: nanoseconds)
48 */
Peter Zijlstra5f6d858e2007-10-15 17:00:12 +020049const_debug unsigned int sysctl_sched_nr_latency = 20;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020050
51/*
Ingo Molnar1799e352007-09-19 23:34:46 +020052 * sys_sched_yield() compat mode
53 *
54 * This option switches the agressive yield implementation of the
55 * old scheduler back on.
56 */
57unsigned int __read_mostly sysctl_sched_compat_yield;
58
59/*
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020060 * SCHED_BATCH wake-up granularity.
Ingo Molnar71fd3712007-08-24 20:39:10 +020061 * (default: 25 msec, units: nanoseconds)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020062 *
63 * This option delays the preemption effects of decoupled workloads
64 * and reduces their over-scheduling. Synchronous workloads will still
65 * have immediate wakeup/sleep latencies.
66 */
Ingo Molnar2bd8e6d2007-10-15 17:00:02 +020067const_debug unsigned int sysctl_sched_batch_wakeup_granularity = 25000000UL;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020068
69/*
70 * SCHED_OTHER wake-up granularity.
71 * (default: 1 msec, units: nanoseconds)
72 *
73 * This option delays the preemption effects of decoupled workloads
74 * and reduces their over-scheduling. Synchronous workloads will still
75 * have immediate wakeup/sleep latencies.
76 */
Ingo Molnar2e09bf52007-10-15 17:00:05 +020077const_debug unsigned int sysctl_sched_wakeup_granularity = 2000000UL;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020078
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020079extern struct sched_class fair_sched_class;
80
81/**************************************************************
82 * CFS operations on generic schedulable entities:
83 */
84
85#ifdef CONFIG_FAIR_GROUP_SCHED
86
87/* cpu runqueue to which this cfs_rq is attached */
88static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
89{
90 return cfs_rq->rq;
91}
92
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020093/* An entity is a task if it doesn't "own" a runqueue */
94#define entity_is_task(se) (!se->my_q)
95
Ingo Molnarbf0f6f22007-07-09 18:51:58 +020096#else /* CONFIG_FAIR_GROUP_SCHED */
97
98static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
99{
100 return container_of(cfs_rq, struct rq, cfs);
101}
102
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200103#define entity_is_task(se) 1
104
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200105#endif /* CONFIG_FAIR_GROUP_SCHED */
106
107static inline struct task_struct *task_of(struct sched_entity *se)
108{
109 return container_of(se, struct task_struct, se);
110}
111
112
113/**************************************************************
114 * Scheduling class tree data structure manipulation methods:
115 */
116
Peter Zijlstra02e04312007-10-15 17:00:07 +0200117static inline u64
118max_vruntime(u64 min_vruntime, u64 vruntime)
119{
Peter Zijlstra368059a2007-10-15 17:00:11 +0200120 s64 delta = (s64)(vruntime - min_vruntime);
121 if (delta > 0)
Peter Zijlstra02e04312007-10-15 17:00:07 +0200122 min_vruntime = vruntime;
123
124 return min_vruntime;
125}
126
Peter Zijlstrab0ffd242007-10-15 17:00:12 +0200127static inline u64
128min_vruntime(u64 min_vruntime, u64 vruntime)
129{
130 s64 delta = (s64)(vruntime - min_vruntime);
131 if (delta < 0)
132 min_vruntime = vruntime;
133
134 return min_vruntime;
135}
136
Peter Zijlstra02e04312007-10-15 17:00:07 +0200137static inline s64
138entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
Peter Zijlstra9014623c2007-10-15 17:00:05 +0200139{
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200140 return se->vruntime - cfs_rq->min_vruntime;
Peter Zijlstra9014623c2007-10-15 17:00:05 +0200141}
142
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200143/*
144 * Enqueue an entity into the rb-tree:
145 */
Ingo Molnar19ccd972007-10-15 17:00:04 +0200146static void
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200147__enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
148{
149 struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
150 struct rb_node *parent = NULL;
151 struct sched_entity *entry;
Peter Zijlstra9014623c2007-10-15 17:00:05 +0200152 s64 key = entity_key(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200153 int leftmost = 1;
154
155 /*
156 * Find the right place in the rbtree:
157 */
158 while (*link) {
159 parent = *link;
160 entry = rb_entry(parent, struct sched_entity, run_node);
161 /*
162 * We dont care about collisions. Nodes with
163 * the same key stay together.
164 */
Peter Zijlstra9014623c2007-10-15 17:00:05 +0200165 if (key < entity_key(cfs_rq, entry)) {
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200166 link = &parent->rb_left;
167 } else {
168 link = &parent->rb_right;
169 leftmost = 0;
170 }
171 }
172
173 /*
174 * Maintain a cache of leftmost tree entries (it is frequently
175 * used):
176 */
177 if (leftmost)
Ingo Molnar57cb4992007-10-15 17:00:11 +0200178 cfs_rq->rb_leftmost = &se->run_node;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200179
180 rb_link_node(&se->run_node, parent, link);
181 rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200182}
183
Ingo Molnar19ccd972007-10-15 17:00:04 +0200184static void
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200185__dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
186{
187 if (cfs_rq->rb_leftmost == &se->run_node)
Ingo Molnar57cb4992007-10-15 17:00:11 +0200188 cfs_rq->rb_leftmost = rb_next(&se->run_node);
Ingo Molnare9acbff2007-10-15 17:00:04 +0200189
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200190 rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200191}
192
193static inline struct rb_node *first_fair(struct cfs_rq *cfs_rq)
194{
195 return cfs_rq->rb_leftmost;
196}
197
198static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
199{
200 return rb_entry(first_fair(cfs_rq), struct sched_entity, run_node);
201}
202
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200203static inline struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
204{
205 struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
206 struct sched_entity *se = NULL;
207 struct rb_node *parent;
208
209 while (*link) {
210 parent = *link;
211 se = rb_entry(parent, struct sched_entity, run_node);
212 link = &parent->rb_right;
213 }
214
215 return se;
216}
217
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200218/**************************************************************
219 * Scheduling class statistics methods:
220 */
221
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200222static u64 __sched_period(unsigned long nr_running)
223{
224 u64 period = sysctl_sched_latency;
Peter Zijlstra5f6d858e2007-10-15 17:00:12 +0200225 unsigned long nr_latency = sysctl_sched_nr_latency;
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200226
227 if (unlikely(nr_running > nr_latency)) {
228 period *= nr_running;
229 do_div(period, nr_latency);
230 }
231
232 return period;
233}
234
Peter Zijlstra6d0f0eb2007-10-15 17:00:05 +0200235static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
Peter Zijlstra21805082007-08-25 18:41:53 +0200236{
Peter Zijlstra6d0f0eb2007-10-15 17:00:05 +0200237 u64 period = __sched_period(cfs_rq->nr_running);
Peter Zijlstra21805082007-08-25 18:41:53 +0200238
Peter Zijlstra6d0f0eb2007-10-15 17:00:05 +0200239 period *= se->load.weight;
240 do_div(period, cfs_rq->load.weight);
Peter Zijlstra21805082007-08-25 18:41:53 +0200241
Peter Zijlstra6d0f0eb2007-10-15 17:00:05 +0200242 return period;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200243}
244
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200245static u64 __sched_vslice(unsigned long nr_running)
246{
Peter Zijlstra5f6d858e2007-10-15 17:00:12 +0200247 unsigned long period = sysctl_sched_latency;
248 unsigned long nr_latency = sysctl_sched_nr_latency;
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200249
Peter Zijlstra5f6d858e2007-10-15 17:00:12 +0200250 if (unlikely(nr_running > nr_latency))
251 nr_running = nr_latency;
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200252
Peter Zijlstra5f6d858e2007-10-15 17:00:12 +0200253 period /= nr_running;
254
255 return (u64)period;
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200256}
257
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200258/*
259 * Update the current task's runtime statistics. Skip current tasks that
260 * are not in our scheduling class.
261 */
262static inline void
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200263__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
264 unsigned long delta_exec)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200265{
Ingo Molnarbbdba7c2007-10-15 17:00:06 +0200266 unsigned long delta_exec_weighted;
Peter Zijlstrab0ffd242007-10-15 17:00:12 +0200267 u64 vruntime;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200268
Ingo Molnar8179ca232007-08-02 17:41:40 +0200269 schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200270
271 curr->sum_exec_runtime += delta_exec;
Ingo Molnar7a62eab2007-10-15 17:00:06 +0200272 schedstat_add(cfs_rq, exec_clock, delta_exec);
Ingo Molnare9acbff2007-10-15 17:00:04 +0200273 delta_exec_weighted = delta_exec;
274 if (unlikely(curr->load.weight != NICE_0_LOAD)) {
275 delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
276 &curr->load);
277 }
278 curr->vruntime += delta_exec_weighted;
Peter Zijlstra02e04312007-10-15 17:00:07 +0200279
280 /*
281 * maintain cfs_rq->min_vruntime to be a monotonic increasing
282 * value tracking the leftmost vruntime in the tree.
283 */
284 if (first_fair(cfs_rq)) {
Peter Zijlstrab0ffd242007-10-15 17:00:12 +0200285 vruntime = min_vruntime(curr->vruntime,
286 __pick_next_entity(cfs_rq)->vruntime);
Peter Zijlstra02e04312007-10-15 17:00:07 +0200287 } else
Peter Zijlstrab0ffd242007-10-15 17:00:12 +0200288 vruntime = curr->vruntime;
Peter Zijlstra02e04312007-10-15 17:00:07 +0200289
290 cfs_rq->min_vruntime =
Peter Zijlstrab0ffd242007-10-15 17:00:12 +0200291 max_vruntime(cfs_rq->min_vruntime, vruntime);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200292}
293
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200294static void update_curr(struct cfs_rq *cfs_rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200295{
Ingo Molnar429d43b2007-10-15 17:00:03 +0200296 struct sched_entity *curr = cfs_rq->curr;
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200297 u64 now = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200298 unsigned long delta_exec;
299
300 if (unlikely(!curr))
301 return;
302
303 /*
304 * Get the amount of time the current task was running
305 * since the last time we changed load (this cannot
306 * overflow on 32 bits):
307 */
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200308 delta_exec = (unsigned long)(now - curr->exec_start);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200309
Ingo Molnar8ebc91d2007-10-15 17:00:03 +0200310 __update_curr(cfs_rq, curr, delta_exec);
311 curr->exec_start = now;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200312}
313
314static inline void
Ingo Molnar5870db52007-08-09 11:16:47 +0200315update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200316{
Ingo Molnard2819182007-08-09 11:16:47 +0200317 schedstat_set(se->wait_start, rq_of(cfs_rq)->clock);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200318}
319
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200320static inline unsigned long
Ingo Molnar08e23882007-10-15 17:00:04 +0200321calc_weighted(unsigned long delta, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200322{
Ingo Molnar08e23882007-10-15 17:00:04 +0200323 unsigned long weight = se->load.weight;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200324
Ingo Molnar08e23882007-10-15 17:00:04 +0200325 if (unlikely(weight != NICE_0_LOAD))
326 return (u64)delta * se->load.weight >> NICE_0_SHIFT;
327 else
328 return delta;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200329}
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200330
331/*
332 * Task is being enqueued - update stats:
333 */
Ingo Molnard2417e52007-08-09 11:16:47 +0200334static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200335{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200336 /*
337 * Are we enqueueing a waiting task? (for current tasks
338 * a dequeue/enqueue event is a NOP)
339 */
Ingo Molnar429d43b2007-10-15 17:00:03 +0200340 if (se != cfs_rq->curr)
Ingo Molnar5870db52007-08-09 11:16:47 +0200341 update_stats_wait_start(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200342}
343
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200344static void
Ingo Molnar9ef0a962007-08-09 11:16:47 +0200345update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200346{
Ingo Molnarbbdba7c2007-10-15 17:00:06 +0200347 schedstat_set(se->wait_max, max(se->wait_max,
348 rq_of(cfs_rq)->clock - se->wait_start));
Ingo Molnar6cfb0d52007-08-02 17:41:40 +0200349 schedstat_set(se->wait_start, 0);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200350}
351
352static inline void
Ingo Molnar19b6a2e2007-08-09 11:16:48 +0200353update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200354{
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200355 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200356 /*
357 * Mark the end of the wait period if dequeueing a
358 * waiting task:
359 */
Ingo Molnar429d43b2007-10-15 17:00:03 +0200360 if (se != cfs_rq->curr)
Ingo Molnar9ef0a962007-08-09 11:16:47 +0200361 update_stats_wait_end(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200362}
363
364/*
365 * We are picking a new current task - update its stats:
366 */
367static inline void
Ingo Molnar79303e92007-08-09 11:16:47 +0200368update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200369{
370 /*
371 * We are starting a new run period:
372 */
Ingo Molnard2819182007-08-09 11:16:47 +0200373 se->exec_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200374}
375
376/*
377 * We are descheduling a task - update its stats:
378 */
379static inline void
Ingo Molnarc7e9b5b2007-08-09 11:16:48 +0200380update_stats_curr_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200381{
382 se->exec_start = 0;
383}
384
385/**************************************************
386 * Scheduling class queueing methods:
387 */
388
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200389static void
390account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
391{
392 update_load_add(&cfs_rq->load, se->load.weight);
393 cfs_rq->nr_running++;
394 se->on_rq = 1;
395}
396
397static void
398account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
399{
400 update_load_sub(&cfs_rq->load, se->load.weight);
401 cfs_rq->nr_running--;
402 se->on_rq = 0;
403}
404
Ingo Molnar2396af62007-08-09 11:16:48 +0200405static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200406{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200407#ifdef CONFIG_SCHEDSTATS
408 if (se->sleep_start) {
Ingo Molnard2819182007-08-09 11:16:47 +0200409 u64 delta = rq_of(cfs_rq)->clock - se->sleep_start;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200410
411 if ((s64)delta < 0)
412 delta = 0;
413
414 if (unlikely(delta > se->sleep_max))
415 se->sleep_max = delta;
416
417 se->sleep_start = 0;
418 se->sum_sleep_runtime += delta;
419 }
420 if (se->block_start) {
Ingo Molnard2819182007-08-09 11:16:47 +0200421 u64 delta = rq_of(cfs_rq)->clock - se->block_start;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200422
423 if ((s64)delta < 0)
424 delta = 0;
425
426 if (unlikely(delta > se->block_max))
427 se->block_max = delta;
428
429 se->block_start = 0;
430 se->sum_sleep_runtime += delta;
Ingo Molnar30084fb2007-10-02 14:13:08 +0200431
432 /*
433 * Blocking time is in units of nanosecs, so shift by 20 to
434 * get a milliseconds-range estimation of the amount of
435 * time that the task spent sleeping:
436 */
437 if (unlikely(prof_on == SLEEP_PROFILING)) {
Ingo Molnare22f5bb2007-10-15 17:00:06 +0200438 struct task_struct *tsk = task_of(se);
439
Ingo Molnar30084fb2007-10-02 14:13:08 +0200440 profile_hits(SLEEP_PROFILING, (void *)get_wchan(tsk),
441 delta >> 20);
442 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200443 }
444#endif
445}
446
Peter Zijlstraddc97292007-10-15 17:00:10 +0200447static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
448{
449#ifdef CONFIG_SCHED_DEBUG
450 s64 d = se->vruntime - cfs_rq->min_vruntime;
451
452 if (d < 0)
453 d = -d;
454
455 if (d > 3*sysctl_sched_latency)
456 schedstat_inc(cfs_rq, nr_spread_over);
457#endif
458}
459
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200460static void
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200461place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
462{
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200463 u64 vruntime;
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200464
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200465 vruntime = cfs_rq->min_vruntime;
Peter Zijlstra94dfb5e2007-10-15 17:00:05 +0200466
467 if (sched_feat(USE_TREE_AVG)) {
468 struct sched_entity *last = __pick_last_entity(cfs_rq);
469 if (last) {
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200470 vruntime += last->vruntime;
471 vruntime >>= 1;
Peter Zijlstra94dfb5e2007-10-15 17:00:05 +0200472 }
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200473 } else if (sched_feat(APPROX_AVG) && cfs_rq->nr_running)
474 vruntime += __sched_vslice(cfs_rq->nr_running)/2;
Peter Zijlstra94dfb5e2007-10-15 17:00:05 +0200475
476 if (initial && sched_feat(START_DEBIT))
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200477 vruntime += __sched_vslice(cfs_rq->nr_running + 1);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200478
Ingo Molnar8465e792007-10-15 17:00:11 +0200479 if (!initial) {
Ingo Molnar94359f02007-10-15 17:00:11 +0200480 if (sched_feat(NEW_FAIR_SLEEPERS))
481 vruntime -= sysctl_sched_latency;
482
Ingo Molnarb8487b922007-10-15 17:00:11 +0200483 vruntime = max_t(s64, vruntime, se->vruntime);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200484 }
485
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200486 se->vruntime = vruntime;
487
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200488}
489
490static void
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200491enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200492{
493 /*
494 * Update the fair clock.
495 */
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200496 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200497
Ingo Molnare9acbff2007-10-15 17:00:04 +0200498 if (wakeup) {
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200499 place_entity(cfs_rq, se, 0);
Ingo Molnar2396af62007-08-09 11:16:48 +0200500 enqueue_sleeper(cfs_rq, se);
Ingo Molnare9acbff2007-10-15 17:00:04 +0200501 }
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200502
Ingo Molnard2417e52007-08-09 11:16:47 +0200503 update_stats_enqueue(cfs_rq, se);
Peter Zijlstraddc97292007-10-15 17:00:10 +0200504 check_spread(cfs_rq, se);
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200505 if (se != cfs_rq->curr)
506 __enqueue_entity(cfs_rq, se);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200507 account_entity_enqueue(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200508}
509
510static void
Ingo Molnar525c2712007-08-09 11:16:48 +0200511dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200512{
Ingo Molnar19b6a2e2007-08-09 11:16:48 +0200513 update_stats_dequeue(cfs_rq, se);
Dmitry Adamushkodb36cc72007-10-15 17:00:06 +0200514 if (sleep) {
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200515#ifdef CONFIG_SCHEDSTATS
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200516 if (entity_is_task(se)) {
517 struct task_struct *tsk = task_of(se);
518
519 if (tsk->state & TASK_INTERRUPTIBLE)
Ingo Molnard2819182007-08-09 11:16:47 +0200520 se->sleep_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200521 if (tsk->state & TASK_UNINTERRUPTIBLE)
Ingo Molnard2819182007-08-09 11:16:47 +0200522 se->block_start = rq_of(cfs_rq)->clock;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200523 }
Dmitry Adamushkodb36cc72007-10-15 17:00:06 +0200524#endif
Peter Zijlstra67e9fb22007-10-15 17:00:10 +0200525 }
526
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200527 if (se != cfs_rq->curr)
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200528 __dequeue_entity(cfs_rq, se);
529 account_entity_dequeue(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200530}
531
532/*
533 * Preempt the current task with a newly woken task if needed:
534 */
Peter Zijlstra7c92e542007-09-05 14:32:49 +0200535static void
Ingo Molnar2e09bf52007-10-15 17:00:05 +0200536check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200537{
Peter Zijlstra11697832007-09-05 14:32:49 +0200538 unsigned long ideal_runtime, delta_exec;
539
Peter Zijlstra6d0f0eb2007-10-15 17:00:05 +0200540 ideal_runtime = sched_slice(cfs_rq, curr);
Peter Zijlstra11697832007-09-05 14:32:49 +0200541 delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
542 if (delta_exec > ideal_runtime)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200543 resched_task(rq_of(cfs_rq)->curr);
544}
545
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200546static void
Ingo Molnar8494f412007-08-09 11:16:48 +0200547set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200548{
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200549 /* 'current' is not kept within the tree. */
550 if (se->on_rq) {
551 /*
552 * Any task has to be enqueued before it get to execute on
553 * a CPU. So account for the time it spent waiting on the
554 * runqueue.
555 */
556 update_stats_wait_end(cfs_rq, se);
557 __dequeue_entity(cfs_rq, se);
558 }
559
Ingo Molnar79303e92007-08-09 11:16:47 +0200560 update_stats_curr_start(cfs_rq, se);
Ingo Molnar429d43b2007-10-15 17:00:03 +0200561 cfs_rq->curr = se;
Ingo Molnareba1ed42007-10-15 17:00:02 +0200562#ifdef CONFIG_SCHEDSTATS
563 /*
564 * Track our maximum slice length, if the CPU's load is at
565 * least twice that of our own weight (i.e. dont track it
566 * when there are only lesser-weight tasks around):
567 */
Dmitry Adamushko495eca42007-10-15 17:00:06 +0200568 if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
Ingo Molnareba1ed42007-10-15 17:00:02 +0200569 se->slice_max = max(se->slice_max,
570 se->sum_exec_runtime - se->prev_sum_exec_runtime);
571 }
572#endif
Peter Zijlstra4a55b452007-09-05 14:32:49 +0200573 se->prev_sum_exec_runtime = se->sum_exec_runtime;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200574}
575
Ingo Molnar9948f4b2007-08-09 11:16:48 +0200576static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200577{
578 struct sched_entity *se = __pick_next_entity(cfs_rq);
579
Ingo Molnar8494f412007-08-09 11:16:48 +0200580 set_next_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200581
582 return se;
583}
584
Ingo Molnarab6cde22007-08-09 11:16:48 +0200585static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200586{
587 /*
588 * If still on the runqueue then deactivate_task()
589 * was not called and update_curr() has to be done:
590 */
591 if (prev->on_rq)
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200592 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200593
Ingo Molnarc7e9b5b2007-08-09 11:16:48 +0200594 update_stats_curr_end(cfs_rq, prev);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200595
Peter Zijlstraddc97292007-10-15 17:00:10 +0200596 check_spread(cfs_rq, prev);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200597 if (prev->on_rq) {
Ingo Molnar5870db52007-08-09 11:16:47 +0200598 update_stats_wait_start(cfs_rq, prev);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200599 /* Put 'current' back into the tree. */
600 __enqueue_entity(cfs_rq, prev);
601 }
Ingo Molnar429d43b2007-10-15 17:00:03 +0200602 cfs_rq->curr = NULL;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200603}
604
605static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
606{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200607 /*
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200608 * Update run-time statistics of the 'current'.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200609 */
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200610 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200611
Ingo Molnar2e09bf52007-10-15 17:00:05 +0200612 if (cfs_rq->nr_running > 1)
613 check_preempt_tick(cfs_rq, curr);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200614}
615
616/**************************************************
617 * CFS operations on tasks:
618 */
619
620#ifdef CONFIG_FAIR_GROUP_SCHED
621
622/* Walk up scheduling entities hierarchy */
623#define for_each_sched_entity(se) \
624 for (; se; se = se->parent)
625
626static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
627{
628 return p->se.cfs_rq;
629}
630
631/* runqueue on which this entity is (to be) queued */
632static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
633{
634 return se->cfs_rq;
635}
636
637/* runqueue "owned" by this group */
638static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
639{
640 return grp->my_q;
641}
642
643/* Given a group's cfs_rq on one cpu, return its corresponding cfs_rq on
644 * another cpu ('this_cpu')
645 */
646static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
647{
Srivatsa Vaddagiri29f59db2007-10-15 17:00:07 +0200648 return cfs_rq->tg->cfs_rq[this_cpu];
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200649}
650
651/* Iterate thr' all leaf cfs_rq's on a runqueue */
652#define for_each_leaf_cfs_rq(rq, cfs_rq) \
653 list_for_each_entry(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
654
Srivatsa Vaddagirifad095a2007-10-15 17:00:12 +0200655/* Do the two (enqueued) entities belong to the same group ? */
656static inline int
657is_same_group(struct sched_entity *se, struct sched_entity *pse)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200658{
Srivatsa Vaddagirifad095a2007-10-15 17:00:12 +0200659 if (se->cfs_rq == pse->cfs_rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200660 return 1;
661
662 return 0;
663}
664
Srivatsa Vaddagirifad095a2007-10-15 17:00:12 +0200665static inline struct sched_entity *parent_entity(struct sched_entity *se)
666{
667 return se->parent;
668}
669
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200670#else /* CONFIG_FAIR_GROUP_SCHED */
671
672#define for_each_sched_entity(se) \
673 for (; se; se = NULL)
674
675static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
676{
677 return &task_rq(p)->cfs;
678}
679
680static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
681{
682 struct task_struct *p = task_of(se);
683 struct rq *rq = task_rq(p);
684
685 return &rq->cfs;
686}
687
688/* runqueue "owned" by this group */
689static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
690{
691 return NULL;
692}
693
694static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
695{
696 return &cpu_rq(this_cpu)->cfs;
697}
698
699#define for_each_leaf_cfs_rq(rq, cfs_rq) \
700 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
701
Srivatsa Vaddagirifad095a2007-10-15 17:00:12 +0200702static inline int
703is_same_group(struct sched_entity *se, struct sched_entity *pse)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200704{
705 return 1;
706}
707
Srivatsa Vaddagirifad095a2007-10-15 17:00:12 +0200708static inline struct sched_entity *parent_entity(struct sched_entity *se)
709{
710 return NULL;
711}
712
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200713#endif /* CONFIG_FAIR_GROUP_SCHED */
714
715/*
716 * The enqueue_task method is called before nr_running is
717 * increased. Here we update the fair scheduling stats and
718 * then put the task into the rbtree:
719 */
Ingo Molnarfd390f62007-08-09 11:16:48 +0200720static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200721{
722 struct cfs_rq *cfs_rq;
723 struct sched_entity *se = &p->se;
724
725 for_each_sched_entity(se) {
726 if (se->on_rq)
727 break;
728 cfs_rq = cfs_rq_of(se);
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +0200729 enqueue_entity(cfs_rq, se, wakeup);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200730 }
731}
732
733/*
734 * The dequeue_task method is called before nr_running is
735 * decreased. We remove the task from the rbtree and
736 * update the fair scheduling stats:
737 */
Ingo Molnarf02231e2007-08-09 11:16:48 +0200738static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200739{
740 struct cfs_rq *cfs_rq;
741 struct sched_entity *se = &p->se;
742
743 for_each_sched_entity(se) {
744 cfs_rq = cfs_rq_of(se);
Ingo Molnar525c2712007-08-09 11:16:48 +0200745 dequeue_entity(cfs_rq, se, sleep);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200746 /* Don't dequeue parent if it has other entities besides us */
747 if (cfs_rq->load.weight)
748 break;
749 }
750}
751
752/*
Ingo Molnar1799e352007-09-19 23:34:46 +0200753 * sched_yield() support is very simple - we dequeue and enqueue.
754 *
755 * If compat_yield is turned on then we requeue to the end of the tree.
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200756 */
Dmitry Adamushko4530d7a2007-10-15 17:00:08 +0200757static void yield_task_fair(struct rq *rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200758{
Srivatsa Vaddagiri72ea22f2007-10-15 17:00:08 +0200759 struct cfs_rq *cfs_rq = task_cfs_rq(rq->curr);
Dmitry Adamushko4530d7a2007-10-15 17:00:08 +0200760 struct sched_entity *rightmost, *se = &rq->curr->se;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200761
762 /*
Ingo Molnar1799e352007-09-19 23:34:46 +0200763 * Are we the only task in the tree?
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200764 */
Ingo Molnar1799e352007-09-19 23:34:46 +0200765 if (unlikely(cfs_rq->nr_running == 1))
766 return;
767
768 if (likely(!sysctl_sched_compat_yield)) {
769 __update_rq_clock(rq);
770 /*
771 * Dequeue and enqueue the task to update its
772 * position within the tree:
773 */
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +0200774 update_curr(cfs_rq);
Ingo Molnar1799e352007-09-19 23:34:46 +0200775
776 return;
777 }
778 /*
779 * Find the rightmost entry in the rbtree:
780 */
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +0200781 rightmost = __pick_last_entity(cfs_rq);
Ingo Molnar1799e352007-09-19 23:34:46 +0200782 /*
783 * Already in the rightmost position?
784 */
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +0200785 if (unlikely(rightmost->vruntime < se->vruntime))
Ingo Molnar1799e352007-09-19 23:34:46 +0200786 return;
787
788 /*
789 * Minimally necessary key value to be last in the tree:
Dmitry Adamushko2b1e3152007-10-15 17:00:12 +0200790 * Upon rescheduling, sched_class::put_prev_task() will place
791 * 'current' within the tree based on its new key value.
Ingo Molnar1799e352007-09-19 23:34:46 +0200792 */
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +0200793 se->vruntime = rightmost->vruntime + 1;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200794}
795
796/*
797 * Preempt the current task with a newly woken task if needed:
798 */
Ingo Molnar2e09bf52007-10-15 17:00:05 +0200799static void check_preempt_wakeup(struct rq *rq, struct task_struct *p)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200800{
801 struct task_struct *curr = rq->curr;
Srivatsa Vaddagirifad095a2007-10-15 17:00:12 +0200802 struct cfs_rq *cfs_rq = task_cfs_rq(curr);
Srivatsa Vaddagiri8651a862007-10-15 17:00:12 +0200803 struct sched_entity *se = &curr->se, *pse = &p->se;
Srivatsa Vaddagirifad095a2007-10-15 17:00:12 +0200804 s64 delta;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200805
806 if (unlikely(rt_prio(p->prio))) {
Ingo Molnara8e504d2007-08-09 11:16:47 +0200807 update_rq_clock(rq);
Ingo Molnarb7cc0892007-08-09 11:16:47 +0200808 update_curr(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200809 resched_task(curr);
810 return;
811 }
812
Srivatsa Vaddagirifad095a2007-10-15 17:00:12 +0200813 while (!is_same_group(se, pse)) {
814 se = parent_entity(se);
815 pse = parent_entity(pse);
Ingo Molnar2e09bf52007-10-15 17:00:05 +0200816 }
Srivatsa Vaddagirifad095a2007-10-15 17:00:12 +0200817
818 delta = se->vruntime - pse->vruntime;
819
820 if (delta > (s64)sysctl_sched_wakeup_granularity)
821 resched_task(curr);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200822}
823
Ingo Molnarfb8d4722007-08-09 11:16:48 +0200824static struct task_struct *pick_next_task_fair(struct rq *rq)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200825{
826 struct cfs_rq *cfs_rq = &rq->cfs;
827 struct sched_entity *se;
828
829 if (unlikely(!cfs_rq->nr_running))
830 return NULL;
831
832 do {
Ingo Molnar9948f4b2007-08-09 11:16:48 +0200833 se = pick_next_entity(cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200834 cfs_rq = group_cfs_rq(se);
835 } while (cfs_rq);
836
837 return task_of(se);
838}
839
840/*
841 * Account for a descheduled task:
842 */
Ingo Molnar31ee5292007-08-09 11:16:49 +0200843static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200844{
845 struct sched_entity *se = &prev->se;
846 struct cfs_rq *cfs_rq;
847
848 for_each_sched_entity(se) {
849 cfs_rq = cfs_rq_of(se);
Ingo Molnarab6cde22007-08-09 11:16:48 +0200850 put_prev_entity(cfs_rq, se);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200851 }
852}
853
854/**************************************************
855 * Fair scheduling class load-balancing methods:
856 */
857
858/*
859 * Load-balancing iterator. Note: while the runqueue stays locked
860 * during the whole iteration, the current task might be
861 * dequeued so the iterator has to be dequeue-safe. Here we
862 * achieve that by always pre-iterating before returning
863 * the current task:
864 */
865static inline struct task_struct *
866__load_balance_iterator(struct cfs_rq *cfs_rq, struct rb_node *curr)
867{
868 struct task_struct *p;
869
870 if (!curr)
871 return NULL;
872
873 p = rb_entry(curr, struct task_struct, se.run_node);
874 cfs_rq->rb_load_balance_curr = rb_next(curr);
875
876 return p;
877}
878
879static struct task_struct *load_balance_start_fair(void *arg)
880{
881 struct cfs_rq *cfs_rq = arg;
882
883 return __load_balance_iterator(cfs_rq, first_fair(cfs_rq));
884}
885
886static struct task_struct *load_balance_next_fair(void *arg)
887{
888 struct cfs_rq *cfs_rq = arg;
889
890 return __load_balance_iterator(cfs_rq, cfs_rq->rb_load_balance_curr);
891}
892
Peter Williamsa4ac01c2007-08-09 11:16:46 +0200893#ifdef CONFIG_FAIR_GROUP_SCHED
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200894static int cfs_rq_best_prio(struct cfs_rq *cfs_rq)
895{
896 struct sched_entity *curr;
897 struct task_struct *p;
898
899 if (!cfs_rq->nr_running)
900 return MAX_PRIO;
901
Srivatsa Vaddagiri9b5b7752007-10-15 17:00:09 +0200902 curr = cfs_rq->curr;
903 if (!curr)
904 curr = __pick_next_entity(cfs_rq);
905
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200906 p = task_of(curr);
907
908 return p->prio;
909}
Peter Williamsa4ac01c2007-08-09 11:16:46 +0200910#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200911
Peter Williams43010652007-08-09 11:16:46 +0200912static unsigned long
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200913load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
Peter Williamsa4ac01c2007-08-09 11:16:46 +0200914 unsigned long max_nr_move, unsigned long max_load_move,
915 struct sched_domain *sd, enum cpu_idle_type idle,
916 int *all_pinned, int *this_best_prio)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200917{
918 struct cfs_rq *busy_cfs_rq;
919 unsigned long load_moved, total_nr_moved = 0, nr_moved;
920 long rem_load_move = max_load_move;
921 struct rq_iterator cfs_rq_iterator;
922
923 cfs_rq_iterator.start = load_balance_start_fair;
924 cfs_rq_iterator.next = load_balance_next_fair;
925
926 for_each_leaf_cfs_rq(busiest, busy_cfs_rq) {
Peter Williamsa4ac01c2007-08-09 11:16:46 +0200927#ifdef CONFIG_FAIR_GROUP_SCHED
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200928 struct cfs_rq *this_cfs_rq;
Ingo Molnare56f31a2007-08-10 23:05:11 +0200929 long imbalance;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200930 unsigned long maxload;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200931
932 this_cfs_rq = cpu_cfs_rq(busy_cfs_rq, this_cpu);
933
Ingo Molnare56f31a2007-08-10 23:05:11 +0200934 imbalance = busy_cfs_rq->load.weight - this_cfs_rq->load.weight;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200935 /* Don't pull if this_cfs_rq has more load than busy_cfs_rq */
936 if (imbalance <= 0)
937 continue;
938
939 /* Don't pull more than imbalance/2 */
940 imbalance /= 2;
941 maxload = min(rem_load_move, imbalance);
942
Peter Williamsa4ac01c2007-08-09 11:16:46 +0200943 *this_best_prio = cfs_rq_best_prio(this_cfs_rq);
944#else
Ingo Molnare56f31a2007-08-10 23:05:11 +0200945# define maxload rem_load_move
Peter Williamsa4ac01c2007-08-09 11:16:46 +0200946#endif
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200947 /* pass busy_cfs_rq argument into
948 * load_balance_[start|next]_fair iterators
949 */
950 cfs_rq_iterator.arg = busy_cfs_rq;
951 nr_moved = balance_tasks(this_rq, this_cpu, busiest,
952 max_nr_move, maxload, sd, idle, all_pinned,
Peter Williamsa4ac01c2007-08-09 11:16:46 +0200953 &load_moved, this_best_prio, &cfs_rq_iterator);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200954
955 total_nr_moved += nr_moved;
956 max_nr_move -= nr_moved;
957 rem_load_move -= load_moved;
958
959 if (max_nr_move <= 0 || rem_load_move <= 0)
960 break;
961 }
962
Peter Williams43010652007-08-09 11:16:46 +0200963 return max_load_move - rem_load_move;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200964}
965
966/*
967 * scheduler tick hitting a task of our scheduling class:
968 */
969static void task_tick_fair(struct rq *rq, struct task_struct *curr)
970{
971 struct cfs_rq *cfs_rq;
972 struct sched_entity *se = &curr->se;
973
974 for_each_sched_entity(se) {
975 cfs_rq = cfs_rq_of(se);
976 entity_tick(cfs_rq, se);
977 }
978}
979
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200980#define swap(a,b) do { typeof(a) tmp = (a); (a) = (b); (b) = tmp; } while (0)
981
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200982/*
983 * Share the fairness runtime between parent and child, thus the
984 * total amount of pressure for CPU stays equal - new tasks
985 * get a chance to run but frequent forkers are not allowed to
986 * monopolize the CPU. Note: the parent runqueue is locked,
987 * the child is not running yet.
988 */
Ingo Molnaree0827d2007-08-09 11:16:49 +0200989static void task_new_fair(struct rq *rq, struct task_struct *p)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200990{
991 struct cfs_rq *cfs_rq = task_cfs_rq(p);
Ingo Molnar429d43b2007-10-15 17:00:03 +0200992 struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
Ingo Molnarbf0f6f22007-07-09 18:51:58 +0200993
994 sched_info_queued(p);
995
Ting Yang7109c4422007-08-28 12:53:24 +0200996 update_curr(cfs_rq);
Peter Zijlstraaeb73b02007-10-15 17:00:05 +0200997 place_entity(cfs_rq, se, 1);
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200998
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +0200999 if (sysctl_sched_child_runs_first &&
1000 curr->vruntime < se->vruntime) {
Dmitry Adamushko87fefa32007-10-15 17:00:08 +02001001 /*
Ingo Molnaredcb60a2007-10-15 17:00:08 +02001002 * Upon rescheduling, sched_class::put_prev_task() will place
1003 * 'current' within the tree based on its new key value.
1004 */
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02001005 swap(curr->vruntime, se->vruntime);
Peter Zijlstra4d78e7b2007-10-15 17:00:04 +02001006 }
1007
Ingo Molnare9acbff2007-10-15 17:00:04 +02001008 update_stats_enqueue(cfs_rq, se);
Peter Zijlstraddc97292007-10-15 17:00:10 +02001009 check_spread(cfs_rq, se);
1010 check_spread(cfs_rq, curr);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001011 __enqueue_entity(cfs_rq, se);
Dmitry Adamushko30cfdcf2007-10-15 17:00:07 +02001012 account_entity_enqueue(cfs_rq, se);
Ingo Molnarbb61c212007-10-15 17:00:02 +02001013 resched_task(rq->curr);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001014}
1015
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001016/* Account for a task changing its policy or group.
1017 *
1018 * This routine is mostly called to set cfs_rq->curr field when a task
1019 * migrates between groups/classes.
1020 */
1021static void set_curr_task_fair(struct rq *rq)
1022{
1023 struct sched_entity *se = &rq->curr->se;
1024
1025 for_each_sched_entity(se)
1026 set_next_entity(cfs_rq_of(se), se);
1027}
1028
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001029/*
1030 * All the scheduling class methods:
1031 */
1032struct sched_class fair_sched_class __read_mostly = {
1033 .enqueue_task = enqueue_task_fair,
1034 .dequeue_task = dequeue_task_fair,
1035 .yield_task = yield_task_fair,
1036
Ingo Molnar2e09bf52007-10-15 17:00:05 +02001037 .check_preempt_curr = check_preempt_wakeup,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001038
1039 .pick_next_task = pick_next_task_fair,
1040 .put_prev_task = put_prev_task_fair,
1041
1042 .load_balance = load_balance_fair,
1043
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001044 .set_curr_task = set_curr_task_fair,
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001045 .task_tick = task_tick_fair,
1046 .task_new = task_new_fair,
1047};
1048
1049#ifdef CONFIG_SCHED_DEBUG
Ingo Molnar5cef9ec2007-08-09 11:16:47 +02001050static void print_cfs_stats(struct seq_file *m, int cpu)
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001051{
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001052 struct cfs_rq *cfs_rq;
1053
Srivatsa Vaddagiri75c28ac2007-10-15 17:00:09 +02001054#ifdef CONFIG_FAIR_GROUP_SCHED
1055 print_cfs_rq(m, cpu, &cpu_rq(cpu)->cfs);
1056#endif
Ingo Molnarc3b64f12007-08-09 11:16:51 +02001057 for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
Ingo Molnar5cef9ec2007-08-09 11:16:47 +02001058 print_cfs_rq(m, cpu, cfs_rq);
Ingo Molnarbf0f6f22007-07-09 18:51:58 +02001059}
1060#endif