blob: d9ba9d5f99d6af74b7c1db5ff5814c15900b68b0 [file] [log] [blame]
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001/*
2 * Real-Time Scheduling Class (mapped to the SCHED_FIFO and SCHED_RR
3 * policies)
4 */
5
Steven Rostedt4fd29172008-01-25 21:08:06 +01006#ifdef CONFIG_SMP
Ingo Molnar84de4272008-01-25 21:08:15 +01007
Gregory Haskins637f5082008-01-25 21:08:18 +01008static inline int rt_overloaded(struct rq *rq)
Steven Rostedt4fd29172008-01-25 21:08:06 +01009{
Gregory Haskins637f5082008-01-25 21:08:18 +010010 return atomic_read(&rq->rd->rto_count);
Steven Rostedt4fd29172008-01-25 21:08:06 +010011}
Ingo Molnar84de4272008-01-25 21:08:15 +010012
Steven Rostedt4fd29172008-01-25 21:08:06 +010013static inline void rt_set_overload(struct rq *rq)
14{
Gregory Haskins1f11eb62008-06-04 15:04:05 -040015 if (!rq->online)
16 return;
17
Gregory Haskins637f5082008-01-25 21:08:18 +010018 cpu_set(rq->cpu, rq->rd->rto_mask);
Steven Rostedt4fd29172008-01-25 21:08:06 +010019 /*
20 * Make sure the mask is visible before we set
21 * the overload count. That is checked to determine
22 * if we should look at the mask. It would be a shame
23 * if we looked at the mask, but the mask was not
24 * updated yet.
25 */
26 wmb();
Gregory Haskins637f5082008-01-25 21:08:18 +010027 atomic_inc(&rq->rd->rto_count);
Steven Rostedt4fd29172008-01-25 21:08:06 +010028}
Ingo Molnar84de4272008-01-25 21:08:15 +010029
Steven Rostedt4fd29172008-01-25 21:08:06 +010030static inline void rt_clear_overload(struct rq *rq)
31{
Gregory Haskins1f11eb62008-06-04 15:04:05 -040032 if (!rq->online)
33 return;
34
Steven Rostedt4fd29172008-01-25 21:08:06 +010035 /* the order here really doesn't matter */
Gregory Haskins637f5082008-01-25 21:08:18 +010036 atomic_dec(&rq->rd->rto_count);
37 cpu_clear(rq->cpu, rq->rd->rto_mask);
Steven Rostedt4fd29172008-01-25 21:08:06 +010038}
Gregory Haskins73fe6aa2008-01-25 21:08:07 +010039
40static void update_rt_migration(struct rq *rq)
41{
Gregory Haskins637f5082008-01-25 21:08:18 +010042 if (rq->rt.rt_nr_migratory && (rq->rt.rt_nr_running > 1)) {
Gregory Haskinscdc8eb92008-01-25 21:08:23 +010043 if (!rq->rt.overloaded) {
44 rt_set_overload(rq);
45 rq->rt.overloaded = 1;
46 }
47 } else if (rq->rt.overloaded) {
Gregory Haskins73fe6aa2008-01-25 21:08:07 +010048 rt_clear_overload(rq);
Gregory Haskins637f5082008-01-25 21:08:18 +010049 rq->rt.overloaded = 0;
50 }
Gregory Haskins73fe6aa2008-01-25 21:08:07 +010051}
Steven Rostedt4fd29172008-01-25 21:08:06 +010052#endif /* CONFIG_SMP */
53
Peter Zijlstra6f505b12008-01-25 21:08:30 +010054static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
Peter Zijlstrafa85ae22008-01-25 21:08:29 +010055{
Peter Zijlstra6f505b12008-01-25 21:08:30 +010056 return container_of(rt_se, struct task_struct, rt);
57}
58
59static inline int on_rt_rq(struct sched_rt_entity *rt_se)
60{
61 return !list_empty(&rt_se->run_list);
62}
63
Peter Zijlstra052f1dc2008-02-13 15:45:40 +010064#ifdef CONFIG_RT_GROUP_SCHED
Peter Zijlstra6f505b12008-01-25 21:08:30 +010065
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010066static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +010067{
68 if (!rt_rq->tg)
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +010069 return RUNTIME_INF;
Peter Zijlstra6f505b12008-01-25 21:08:30 +010070
Peter Zijlstraac086bc2008-04-19 19:44:58 +020071 return rt_rq->rt_runtime;
72}
73
74static inline u64 sched_rt_period(struct rt_rq *rt_rq)
75{
76 return ktime_to_ns(rt_rq->tg->rt_bandwidth.rt_period);
Peter Zijlstra6f505b12008-01-25 21:08:30 +010077}
78
79#define for_each_leaf_rt_rq(rt_rq, rq) \
80 list_for_each_entry(rt_rq, &rq->leaf_rt_rq_list, leaf_rt_rq_list)
81
82static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
83{
84 return rt_rq->rq;
85}
86
87static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
88{
89 return rt_se->rt_rq;
90}
91
92#define for_each_sched_rt_entity(rt_se) \
93 for (; rt_se; rt_se = rt_se->parent)
94
95static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
96{
97 return rt_se->my_q;
98}
99
100static void enqueue_rt_entity(struct sched_rt_entity *rt_se);
101static void dequeue_rt_entity(struct sched_rt_entity *rt_se);
102
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100103static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100104{
Dario Faggiolif6121f42008-10-03 17:40:46 +0200105 struct task_struct *curr = rq_of_rt_rq(rt_rq)->curr;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100106 struct sched_rt_entity *rt_se = rt_rq->rt_se;
107
Dario Faggiolif6121f42008-10-03 17:40:46 +0200108 if (rt_rq->rt_nr_running) {
109 if (rt_se && !on_rt_rq(rt_se))
110 enqueue_rt_entity(rt_se);
Peter Zijlstra10203872008-01-25 21:08:32 +0100111 if (rt_rq->highest_prio < curr->prio)
112 resched_task(curr);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100113 }
114}
115
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100116static void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100117{
118 struct sched_rt_entity *rt_se = rt_rq->rt_se;
119
120 if (rt_se && on_rt_rq(rt_se))
121 dequeue_rt_entity(rt_se);
122}
123
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100124static inline int rt_rq_throttled(struct rt_rq *rt_rq)
125{
126 return rt_rq->rt_throttled && !rt_rq->rt_nr_boosted;
127}
128
129static int rt_se_boosted(struct sched_rt_entity *rt_se)
130{
131 struct rt_rq *rt_rq = group_rt_rq(rt_se);
132 struct task_struct *p;
133
134 if (rt_rq)
135 return !!rt_rq->rt_nr_boosted;
136
137 p = rt_task_of(rt_se);
138 return p->prio != p->normal_prio;
139}
140
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200141#ifdef CONFIG_SMP
142static inline cpumask_t sched_rt_period_mask(void)
143{
144 return cpu_rq(smp_processor_id())->rd->span;
145}
146#else
147static inline cpumask_t sched_rt_period_mask(void)
148{
149 return cpu_online_map;
150}
151#endif
152
153static inline
154struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
155{
156 return container_of(rt_b, struct task_group, rt_bandwidth)->rt_rq[cpu];
157}
158
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200159static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
160{
161 return &rt_rq->tg->rt_bandwidth;
162}
163
Dhaval Giani55e12e52008-06-24 23:39:43 +0530164#else /* !CONFIG_RT_GROUP_SCHED */
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100165
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100166static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100167{
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200168 return rt_rq->rt_runtime;
169}
170
171static inline u64 sched_rt_period(struct rt_rq *rt_rq)
172{
173 return ktime_to_ns(def_rt_bandwidth.rt_period);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100174}
175
176#define for_each_leaf_rt_rq(rt_rq, rq) \
177 for (rt_rq = &rq->rt; rt_rq; rt_rq = NULL)
178
179static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
180{
181 return container_of(rt_rq, struct rq, rt);
182}
183
184static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
185{
186 struct task_struct *p = rt_task_of(rt_se);
187 struct rq *rq = task_rq(p);
188
189 return &rq->rt;
190}
191
192#define for_each_sched_rt_entity(rt_se) \
193 for (; rt_se; rt_se = NULL)
194
195static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
196{
197 return NULL;
198}
199
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100200static inline void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100201{
John Blackwoodf3ade832008-08-26 15:09:43 -0400202 if (rt_rq->rt_nr_running)
203 resched_task(rq_of_rt_rq(rt_rq)->curr);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100204}
205
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100206static inline void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100207{
208}
209
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100210static inline int rt_rq_throttled(struct rt_rq *rt_rq)
211{
212 return rt_rq->rt_throttled;
213}
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200214
215static inline cpumask_t sched_rt_period_mask(void)
216{
217 return cpu_online_map;
218}
219
220static inline
221struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
222{
223 return &cpu_rq(cpu)->rt;
224}
225
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200226static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
227{
228 return &def_rt_bandwidth;
229}
230
Dhaval Giani55e12e52008-06-24 23:39:43 +0530231#endif /* CONFIG_RT_GROUP_SCHED */
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100232
Peter Zijlstrab79f3832008-06-19 14:22:25 +0200233#ifdef CONFIG_SMP
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200234/*
235 * We ran out of runtime, see if we can borrow some from our neighbours.
236 */
Peter Zijlstrab79f3832008-06-19 14:22:25 +0200237static int do_balance_runtime(struct rt_rq *rt_rq)
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200238{
239 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
240 struct root_domain *rd = cpu_rq(smp_processor_id())->rd;
241 int i, weight, more = 0;
242 u64 rt_period;
243
244 weight = cpus_weight(rd->span);
245
246 spin_lock(&rt_b->rt_runtime_lock);
247 rt_period = ktime_to_ns(rt_b->rt_period);
Ingo Molnar82638842008-07-16 00:29:07 +0200248 for_each_cpu_mask_nr(i, rd->span) {
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200249 struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
250 s64 diff;
251
252 if (iter == rt_rq)
253 continue;
254
255 spin_lock(&iter->rt_runtime_lock);
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200256 /*
257 * Either all rqs have inf runtime and there's nothing to steal
258 * or __disable_runtime() below sets a specific rq to inf to
259 * indicate its been disabled and disalow stealing.
260 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200261 if (iter->rt_runtime == RUNTIME_INF)
262 goto next;
263
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200264 /*
265 * From runqueues with spare time, take 1/n part of their
266 * spare time, but no more than our period.
267 */
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200268 diff = iter->rt_runtime - iter->rt_time;
269 if (diff > 0) {
Peter Zijlstra58838cf2008-07-24 12:43:13 +0200270 diff = div_u64((u64)diff, weight);
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200271 if (rt_rq->rt_runtime + diff > rt_period)
272 diff = rt_period - rt_rq->rt_runtime;
273 iter->rt_runtime -= diff;
274 rt_rq->rt_runtime += diff;
275 more = 1;
276 if (rt_rq->rt_runtime == rt_period) {
277 spin_unlock(&iter->rt_runtime_lock);
278 break;
279 }
280 }
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200281next:
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200282 spin_unlock(&iter->rt_runtime_lock);
283 }
284 spin_unlock(&rt_b->rt_runtime_lock);
285
286 return more;
287}
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200288
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200289/*
290 * Ensure this RQ takes back all the runtime it lend to its neighbours.
291 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200292static void __disable_runtime(struct rq *rq)
293{
294 struct root_domain *rd = rq->rd;
295 struct rt_rq *rt_rq;
296
297 if (unlikely(!scheduler_running))
298 return;
299
300 for_each_leaf_rt_rq(rt_rq, rq) {
301 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
302 s64 want;
303 int i;
304
305 spin_lock(&rt_b->rt_runtime_lock);
306 spin_lock(&rt_rq->rt_runtime_lock);
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200307 /*
308 * Either we're all inf and nobody needs to borrow, or we're
309 * already disabled and thus have nothing to do, or we have
310 * exactly the right amount of runtime to take out.
311 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200312 if (rt_rq->rt_runtime == RUNTIME_INF ||
313 rt_rq->rt_runtime == rt_b->rt_runtime)
314 goto balanced;
315 spin_unlock(&rt_rq->rt_runtime_lock);
316
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200317 /*
318 * Calculate the difference between what we started out with
319 * and what we current have, that's the amount of runtime
320 * we lend and now have to reclaim.
321 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200322 want = rt_b->rt_runtime - rt_rq->rt_runtime;
323
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200324 /*
325 * Greedy reclaim, take back as much as we can.
326 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200327 for_each_cpu_mask(i, rd->span) {
328 struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
329 s64 diff;
330
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200331 /*
332 * Can't reclaim from ourselves or disabled runqueues.
333 */
Peter Zijlstraf1679d02008-08-14 15:49:00 +0200334 if (iter == rt_rq || iter->rt_runtime == RUNTIME_INF)
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200335 continue;
336
337 spin_lock(&iter->rt_runtime_lock);
338 if (want > 0) {
339 diff = min_t(s64, iter->rt_runtime, want);
340 iter->rt_runtime -= diff;
341 want -= diff;
342 } else {
343 iter->rt_runtime -= want;
344 want -= want;
345 }
346 spin_unlock(&iter->rt_runtime_lock);
347
348 if (!want)
349 break;
350 }
351
352 spin_lock(&rt_rq->rt_runtime_lock);
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200353 /*
354 * We cannot be left wanting - that would mean some runtime
355 * leaked out of the system.
356 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200357 BUG_ON(want);
358balanced:
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200359 /*
360 * Disable all the borrow logic by pretending we have inf
361 * runtime - in which case borrowing doesn't make sense.
362 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200363 rt_rq->rt_runtime = RUNTIME_INF;
364 spin_unlock(&rt_rq->rt_runtime_lock);
365 spin_unlock(&rt_b->rt_runtime_lock);
366 }
367}
368
369static void disable_runtime(struct rq *rq)
370{
371 unsigned long flags;
372
373 spin_lock_irqsave(&rq->lock, flags);
374 __disable_runtime(rq);
375 spin_unlock_irqrestore(&rq->lock, flags);
376}
377
378static void __enable_runtime(struct rq *rq)
379{
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200380 struct rt_rq *rt_rq;
381
382 if (unlikely(!scheduler_running))
383 return;
384
Peter Zijlstra78333cd2008-09-23 15:33:43 +0200385 /*
386 * Reset each runqueue's bandwidth settings
387 */
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200388 for_each_leaf_rt_rq(rt_rq, rq) {
389 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
390
391 spin_lock(&rt_b->rt_runtime_lock);
392 spin_lock(&rt_rq->rt_runtime_lock);
393 rt_rq->rt_runtime = rt_b->rt_runtime;
394 rt_rq->rt_time = 0;
Zhang, Yanminbaf25732008-09-09 11:26:33 +0800395 rt_rq->rt_throttled = 0;
Peter Zijlstra7def2be2008-06-05 14:49:58 +0200396 spin_unlock(&rt_rq->rt_runtime_lock);
397 spin_unlock(&rt_b->rt_runtime_lock);
398 }
399}
400
401static void enable_runtime(struct rq *rq)
402{
403 unsigned long flags;
404
405 spin_lock_irqsave(&rq->lock, flags);
406 __enable_runtime(rq);
407 spin_unlock_irqrestore(&rq->lock, flags);
408}
409
Peter Zijlstraeff65492008-06-19 14:22:26 +0200410static int balance_runtime(struct rt_rq *rt_rq)
411{
412 int more = 0;
413
414 if (rt_rq->rt_time > rt_rq->rt_runtime) {
415 spin_unlock(&rt_rq->rt_runtime_lock);
416 more = do_balance_runtime(rt_rq);
417 spin_lock(&rt_rq->rt_runtime_lock);
418 }
419
420 return more;
421}
Dhaval Giani55e12e52008-06-24 23:39:43 +0530422#else /* !CONFIG_SMP */
Peter Zijlstraeff65492008-06-19 14:22:26 +0200423static inline int balance_runtime(struct rt_rq *rt_rq)
424{
425 return 0;
426}
Dhaval Giani55e12e52008-06-24 23:39:43 +0530427#endif /* CONFIG_SMP */
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100428
429static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)
430{
431 int i, idle = 1;
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200432 cpumask_t span;
433
Peter Zijlstra0b148fa2008-08-19 12:33:04 +0200434 if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200435 return 1;
436
437 span = sched_rt_period_mask();
Peter Zijlstraeff65492008-06-19 14:22:26 +0200438 for_each_cpu_mask(i, span) {
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200439 int enqueue = 0;
440 struct rt_rq *rt_rq = sched_rt_period_rt_rq(rt_b, i);
441 struct rq *rq = rq_of_rt_rq(rt_rq);
442
443 spin_lock(&rq->lock);
444 if (rt_rq->rt_time) {
445 u64 runtime;
446
447 spin_lock(&rt_rq->rt_runtime_lock);
Peter Zijlstraeff65492008-06-19 14:22:26 +0200448 if (rt_rq->rt_throttled)
449 balance_runtime(rt_rq);
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200450 runtime = rt_rq->rt_runtime;
451 rt_rq->rt_time -= min(rt_rq->rt_time, overrun*runtime);
452 if (rt_rq->rt_throttled && rt_rq->rt_time < runtime) {
453 rt_rq->rt_throttled = 0;
454 enqueue = 1;
455 }
456 if (rt_rq->rt_time || rt_rq->rt_nr_running)
457 idle = 0;
458 spin_unlock(&rt_rq->rt_runtime_lock);
Peter Zijlstra8a8cde12008-06-19 14:22:28 +0200459 } else if (rt_rq->rt_nr_running)
460 idle = 0;
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200461
462 if (enqueue)
463 sched_rt_rq_enqueue(rt_rq);
464 spin_unlock(&rq->lock);
465 }
466
467 return idle;
468}
469
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100470static inline int rt_se_prio(struct sched_rt_entity *rt_se)
471{
Peter Zijlstra052f1dc2008-02-13 15:45:40 +0100472#ifdef CONFIG_RT_GROUP_SCHED
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100473 struct rt_rq *rt_rq = group_rt_rq(rt_se);
474
475 if (rt_rq)
476 return rt_rq->highest_prio;
477#endif
478
479 return rt_task_of(rt_se)->prio;
480}
481
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100482static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100483{
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100484 u64 runtime = sched_rt_runtime(rt_rq);
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100485
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100486 if (rt_rq->rt_throttled)
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100487 return rt_rq_throttled(rt_rq);
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100488
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200489 if (sched_rt_runtime(rt_rq) >= sched_rt_period(rt_rq))
490 return 0;
491
Peter Zijlstrab79f3832008-06-19 14:22:25 +0200492 balance_runtime(rt_rq);
493 runtime = sched_rt_runtime(rt_rq);
494 if (runtime == RUNTIME_INF)
495 return 0;
Peter Zijlstraac086bc2008-04-19 19:44:58 +0200496
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100497 if (rt_rq->rt_time > runtime) {
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100498 rt_rq->rt_throttled = 1;
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100499 if (rt_rq_throttled(rt_rq)) {
Peter Zijlstra9f0c1e52008-02-13 15:45:39 +0100500 sched_rt_rq_dequeue(rt_rq);
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100501 return 1;
502 }
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100503 }
504
505 return 0;
506}
507
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200508/*
509 * Update the current task's runtime statistics. Skip current tasks that
510 * are not in our scheduling class.
511 */
Alexey Dobriyana9957442007-10-15 17:00:13 +0200512static void update_curr_rt(struct rq *rq)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200513{
514 struct task_struct *curr = rq->curr;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100515 struct sched_rt_entity *rt_se = &curr->rt;
516 struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200517 u64 delta_exec;
518
519 if (!task_has_rt_policy(curr))
520 return;
521
Ingo Molnard2819182007-08-09 11:16:47 +0200522 delta_exec = rq->clock - curr->se.exec_start;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200523 if (unlikely((s64)delta_exec < 0))
524 delta_exec = 0;
Ingo Molnar6cfb0d52007-08-02 17:41:40 +0200525
526 schedstat_set(curr->se.exec_max, max(curr->se.exec_max, delta_exec));
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200527
528 curr->se.sum_exec_runtime += delta_exec;
Frank Mayharf06febc2008-09-12 09:54:39 -0700529 account_group_exec_runtime(curr, delta_exec);
530
Ingo Molnard2819182007-08-09 11:16:47 +0200531 curr->se.exec_start = rq->clock;
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100532 cpuacct_charge(curr, delta_exec);
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100533
Peter Zijlstra0b148fa2008-08-19 12:33:04 +0200534 if (!rt_bandwidth_enabled())
535 return;
536
Dhaval Giani354d60c2008-04-19 19:44:59 +0200537 for_each_sched_rt_entity(rt_se) {
538 rt_rq = rt_rq_of_se(rt_se);
539
540 spin_lock(&rt_rq->rt_runtime_lock);
Peter Zijlstracc2991c2008-08-19 12:33:03 +0200541 if (sched_rt_runtime(rt_rq) != RUNTIME_INF) {
542 rt_rq->rt_time += delta_exec;
543 if (sched_rt_runtime_exceeded(rt_rq))
544 resched_task(curr);
545 }
Dhaval Giani354d60c2008-04-19 19:44:59 +0200546 spin_unlock(&rt_rq->rt_runtime_lock);
547 }
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200548}
549
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100550static inline
551void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
Steven Rostedt63489e42008-01-25 21:08:03 +0100552{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100553 WARN_ON(!rt_prio(rt_se_prio(rt_se)));
554 rt_rq->rt_nr_running++;
Peter Zijlstra052f1dc2008-02-13 15:45:40 +0100555#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
Gregory Haskins6e0534f2008-05-12 21:21:01 +0200556 if (rt_se_prio(rt_se) < rt_rq->highest_prio) {
David Howells577b4a52008-07-11 13:34:54 +0100557#ifdef CONFIG_SMP
Gregory Haskins6e0534f2008-05-12 21:21:01 +0200558 struct rq *rq = rq_of_rt_rq(rt_rq);
David Howells577b4a52008-07-11 13:34:54 +0100559#endif
Gregory Haskins1f11eb62008-06-04 15:04:05 -0400560
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100561 rt_rq->highest_prio = rt_se_prio(rt_se);
Ingo Molnar1100ac92008-06-05 12:25:37 +0200562#ifdef CONFIG_SMP
Gregory Haskins1f11eb62008-06-04 15:04:05 -0400563 if (rq->online)
564 cpupri_set(&rq->rd->cpupri, rq->cpu,
565 rt_se_prio(rt_se));
Ingo Molnar1100ac92008-06-05 12:25:37 +0200566#endif
Gregory Haskins6e0534f2008-05-12 21:21:01 +0200567 }
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100568#endif
Steven Rostedt764a9d62008-01-25 21:08:04 +0100569#ifdef CONFIG_SMP
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100570 if (rt_se->nr_cpus_allowed > 1) {
571 struct rq *rq = rq_of_rt_rq(rt_rq);
Ingo Molnar1100ac92008-06-05 12:25:37 +0200572
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100573 rq->rt.rt_nr_migratory++;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100574 }
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100575
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100576 update_rt_migration(rq_of_rt_rq(rt_rq));
577#endif
Peter Zijlstra052f1dc2008-02-13 15:45:40 +0100578#ifdef CONFIG_RT_GROUP_SCHED
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100579 if (rt_se_boosted(rt_se))
580 rt_rq->rt_nr_boosted++;
Peter Zijlstrad0b27fa2008-04-19 19:44:57 +0200581
582 if (rt_rq->tg)
583 start_rt_bandwidth(&rt_rq->tg->rt_bandwidth);
584#else
585 start_rt_bandwidth(&def_rt_bandwidth);
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100586#endif
Steven Rostedt63489e42008-01-25 21:08:03 +0100587}
588
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100589static inline
590void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
Steven Rostedt63489e42008-01-25 21:08:03 +0100591{
Gregory Haskins6e0534f2008-05-12 21:21:01 +0200592#ifdef CONFIG_SMP
593 int highest_prio = rt_rq->highest_prio;
594#endif
595
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100596 WARN_ON(!rt_prio(rt_se_prio(rt_se)));
597 WARN_ON(!rt_rq->rt_nr_running);
598 rt_rq->rt_nr_running--;
Peter Zijlstra052f1dc2008-02-13 15:45:40 +0100599#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100600 if (rt_rq->rt_nr_running) {
Steven Rostedt764a9d62008-01-25 21:08:04 +0100601 struct rt_prio_array *array;
602
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100603 WARN_ON(rt_se_prio(rt_se) < rt_rq->highest_prio);
604 if (rt_se_prio(rt_se) == rt_rq->highest_prio) {
Steven Rostedt764a9d62008-01-25 21:08:04 +0100605 /* recalculate */
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100606 array = &rt_rq->active;
607 rt_rq->highest_prio =
Steven Rostedt764a9d62008-01-25 21:08:04 +0100608 sched_find_first_bit(array->bitmap);
609 } /* otherwise leave rq->highest prio alone */
610 } else
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100611 rt_rq->highest_prio = MAX_RT_PRIO;
612#endif
613#ifdef CONFIG_SMP
614 if (rt_se->nr_cpus_allowed > 1) {
615 struct rq *rq = rq_of_rt_rq(rt_rq);
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100616 rq->rt.rt_nr_migratory--;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100617 }
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100618
Gregory Haskins6e0534f2008-05-12 21:21:01 +0200619 if (rt_rq->highest_prio != highest_prio) {
620 struct rq *rq = rq_of_rt_rq(rt_rq);
Gregory Haskins1f11eb62008-06-04 15:04:05 -0400621
622 if (rq->online)
623 cpupri_set(&rq->rd->cpupri, rq->cpu,
624 rt_rq->highest_prio);
Gregory Haskins6e0534f2008-05-12 21:21:01 +0200625 }
626
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100627 update_rt_migration(rq_of_rt_rq(rt_rq));
Steven Rostedt764a9d62008-01-25 21:08:04 +0100628#endif /* CONFIG_SMP */
Peter Zijlstra052f1dc2008-02-13 15:45:40 +0100629#ifdef CONFIG_RT_GROUP_SCHED
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100630 if (rt_se_boosted(rt_se))
631 rt_rq->rt_nr_boosted--;
632
633 WARN_ON(!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted);
634#endif
Steven Rostedt63489e42008-01-25 21:08:03 +0100635}
636
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200637static void __enqueue_rt_entity(struct sched_rt_entity *rt_se)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200638{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100639 struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
640 struct rt_prio_array *array = &rt_rq->active;
641 struct rt_rq *group_rq = group_rt_rq(rt_se);
Dmitry Adamushko20b63312008-06-11 00:58:30 +0200642 struct list_head *queue = array->queue + rt_se_prio(rt_se);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200643
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200644 /*
645 * Don't enqueue the group if its throttled, or when empty.
646 * The latter is a consequence of the former when a child group
647 * get throttled and the current group doesn't have any other
648 * active members.
649 */
650 if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running))
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100651 return;
Steven Rostedt63489e42008-01-25 21:08:03 +0100652
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200653 list_add_tail(&rt_se->run_list, queue);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100654 __set_bit(rt_se_prio(rt_se), array->bitmap);
Peter Zijlstra78f2c7d2008-01-25 21:08:27 +0100655
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100656 inc_rt_tasks(rt_se, rt_rq);
657}
658
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200659static void __dequeue_rt_entity(struct sched_rt_entity *rt_se)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100660{
661 struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
662 struct rt_prio_array *array = &rt_rq->active;
663
664 list_del_init(&rt_se->run_list);
665 if (list_empty(array->queue + rt_se_prio(rt_se)))
666 __clear_bit(rt_se_prio(rt_se), array->bitmap);
667
668 dec_rt_tasks(rt_se, rt_rq);
669}
670
671/*
672 * Because the prio of an upper entry depends on the lower
673 * entries, we must remove entries top - down.
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100674 */
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200675static void dequeue_rt_stack(struct sched_rt_entity *rt_se)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100676{
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200677 struct sched_rt_entity *back = NULL;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100678
Peter Zijlstra58d6c2d2008-04-19 19:45:00 +0200679 for_each_sched_rt_entity(rt_se) {
680 rt_se->back = back;
681 back = rt_se;
682 }
683
684 for (rt_se = back; rt_se; rt_se = rt_se->back) {
685 if (on_rt_rq(rt_se))
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200686 __dequeue_rt_entity(rt_se);
687 }
688}
689
690static void enqueue_rt_entity(struct sched_rt_entity *rt_se)
691{
692 dequeue_rt_stack(rt_se);
693 for_each_sched_rt_entity(rt_se)
694 __enqueue_rt_entity(rt_se);
695}
696
697static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
698{
699 dequeue_rt_stack(rt_se);
700
701 for_each_sched_rt_entity(rt_se) {
702 struct rt_rq *rt_rq = group_rt_rq(rt_se);
703
704 if (rt_rq && rt_rq->rt_nr_running)
705 __enqueue_rt_entity(rt_se);
Peter Zijlstra58d6c2d2008-04-19 19:45:00 +0200706 }
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200707}
708
709/*
710 * Adding/removing a task to/from a priority array:
711 */
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100712static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
713{
714 struct sched_rt_entity *rt_se = &p->rt;
715
716 if (wakeup)
717 rt_se->timeout = 0;
718
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200719 enqueue_rt_entity(rt_se);
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200720
721 inc_cpu_load(rq, p->se.load.weight);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100722}
723
Ingo Molnarf02231e2007-08-09 11:16:48 +0200724static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200725{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100726 struct sched_rt_entity *rt_se = &p->rt;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200727
Ingo Molnarf1e14ef2007-08-09 11:16:48 +0200728 update_curr_rt(rq);
Peter Zijlstraad2a3f12008-06-19 09:06:57 +0200729 dequeue_rt_entity(rt_se);
Peter Zijlstrac09595f2008-06-27 13:41:14 +0200730
731 dec_cpu_load(rq, p->se.load.weight);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200732}
733
734/*
735 * Put task to the end of the run list without the overhead of dequeue
736 * followed by enqueue.
737 */
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200738static void
739requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se, int head)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200740{
Ingo Molnar1cdad712008-06-19 09:09:15 +0200741 if (on_rt_rq(rt_se)) {
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200742 struct rt_prio_array *array = &rt_rq->active;
743 struct list_head *queue = array->queue + rt_se_prio(rt_se);
744
745 if (head)
746 list_move(&rt_se->run_list, queue);
747 else
748 list_move_tail(&rt_se->run_list, queue);
Ingo Molnar1cdad712008-06-19 09:09:15 +0200749 }
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200750}
751
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200752static void requeue_task_rt(struct rq *rq, struct task_struct *p, int head)
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100753{
754 struct sched_rt_entity *rt_se = &p->rt;
755 struct rt_rq *rt_rq;
756
757 for_each_sched_rt_entity(rt_se) {
758 rt_rq = rt_rq_of_se(rt_se);
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200759 requeue_rt_entity(rt_rq, rt_se, head);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100760 }
761}
762
763static void yield_task_rt(struct rq *rq)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200764{
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200765 requeue_task_rt(rq, rq->curr, 0);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200766}
767
Gregory Haskinse7693a32008-01-25 21:08:09 +0100768#ifdef CONFIG_SMP
Gregory Haskins318e0892008-01-25 21:08:10 +0100769static int find_lowest_rq(struct task_struct *task);
770
Gregory Haskinse7693a32008-01-25 21:08:09 +0100771static int select_task_rq_rt(struct task_struct *p, int sync)
772{
Gregory Haskins318e0892008-01-25 21:08:10 +0100773 struct rq *rq = task_rq(p);
774
775 /*
Steven Rostedte1f47d82008-01-25 21:08:12 +0100776 * If the current task is an RT task, then
777 * try to see if we can wake this RT task up on another
778 * runqueue. Otherwise simply start this RT task
779 * on its current runqueue.
780 *
781 * We want to avoid overloading runqueues. Even if
782 * the RT task is of higher priority than the current RT task.
783 * RT tasks behave differently than other tasks. If
784 * one gets preempted, we try to push it off to another queue.
785 * So trying to keep a preempting RT task on the same
786 * cache hot CPU will force the running RT task to
787 * a cold CPU. So we waste all the cache for the lower
788 * RT task in hopes of saving some of a RT task
789 * that is just being woken and probably will have
790 * cold cache anyway.
Gregory Haskins318e0892008-01-25 21:08:10 +0100791 */
Gregory Haskins17b32792008-01-25 21:08:13 +0100792 if (unlikely(rt_task(rq->curr)) &&
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100793 (p->rt.nr_cpus_allowed > 1)) {
Gregory Haskins318e0892008-01-25 21:08:10 +0100794 int cpu = find_lowest_rq(p);
795
796 return (cpu == -1) ? task_cpu(p) : cpu;
797 }
798
799 /*
800 * Otherwise, just let it ride on the affined RQ and the
801 * post-schedule router will push the preempted task away
802 */
Gregory Haskinse7693a32008-01-25 21:08:09 +0100803 return task_cpu(p);
804}
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200805
806static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
807{
808 cpumask_t mask;
809
810 if (rq->curr->rt.nr_cpus_allowed == 1)
811 return;
812
813 if (p->rt.nr_cpus_allowed != 1
814 && cpupri_find(&rq->rd->cpupri, p, &mask))
815 return;
816
817 if (!cpupri_find(&rq->rd->cpupri, rq->curr, &mask))
818 return;
819
820 /*
821 * There appears to be other cpus that can accept
822 * current and none to run 'p', so lets reschedule
823 * to try and push current away:
824 */
825 requeue_task_rt(rq, p, 1);
826 resched_task(rq->curr);
827}
828
Gregory Haskinse7693a32008-01-25 21:08:09 +0100829#endif /* CONFIG_SMP */
830
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200831/*
832 * Preempt the current task with a newly woken task if needed:
833 */
Peter Zijlstra15afe092008-09-20 23:38:02 +0200834static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int sync)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200835{
Gregory Haskins45c01e82008-05-12 21:20:41 +0200836 if (p->prio < rq->curr->prio) {
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200837 resched_task(rq->curr);
Gregory Haskins45c01e82008-05-12 21:20:41 +0200838 return;
839 }
840
841#ifdef CONFIG_SMP
842 /*
843 * If:
844 *
845 * - the newly woken task is of equal priority to the current task
846 * - the newly woken task is non-migratable while current is migratable
847 * - current will be preempted on the next reschedule
848 *
849 * we should check to see if current can readily move to a different
850 * cpu. If so, we will reschedule to allow the push logic to try
851 * to move current somewhere else, making room for our non-migratable
852 * task.
853 */
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +0200854 if (p->prio == rq->curr->prio && !need_resched())
855 check_preempt_equal_prio(rq, p);
Gregory Haskins45c01e82008-05-12 21:20:41 +0200856#endif
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200857}
858
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100859static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
860 struct rt_rq *rt_rq)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200861{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100862 struct rt_prio_array *array = &rt_rq->active;
863 struct sched_rt_entity *next = NULL;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200864 struct list_head *queue;
865 int idx;
866
867 idx = sched_find_first_bit(array->bitmap);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100868 BUG_ON(idx >= MAX_RT_PRIO);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200869
870 queue = array->queue + idx;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100871 next = list_entry(queue->next, struct sched_rt_entity, run_list);
Dmitry Adamushko326587b2008-01-25 21:08:34 +0100872
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200873 return next;
874}
875
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100876static struct task_struct *pick_next_task_rt(struct rq *rq)
877{
878 struct sched_rt_entity *rt_se;
879 struct task_struct *p;
880 struct rt_rq *rt_rq;
881
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100882 rt_rq = &rq->rt;
883
884 if (unlikely(!rt_rq->rt_nr_running))
885 return NULL;
886
Peter Zijlstra23b0fdf2008-02-13 15:45:39 +0100887 if (rt_rq_throttled(rt_rq))
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100888 return NULL;
889
890 do {
891 rt_se = pick_next_rt_entity(rq, rt_rq);
Dmitry Adamushko326587b2008-01-25 21:08:34 +0100892 BUG_ON(!rt_se);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100893 rt_rq = group_rt_rq(rt_se);
894 } while (rt_rq);
895
896 p = rt_task_of(rt_se);
897 p->se.exec_start = rq->clock;
898 return p;
899}
900
Ingo Molnar31ee5292007-08-09 11:16:49 +0200901static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200902{
Ingo Molnarf1e14ef2007-08-09 11:16:48 +0200903 update_curr_rt(rq);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200904 p->se.exec_start = 0;
905}
906
Peter Williams681f3e62007-10-24 18:23:51 +0200907#ifdef CONFIG_SMP
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100908
Steven Rostedte8fa1362008-01-25 21:08:05 +0100909/* Only try algorithms three times */
910#define RT_MAX_TRIES 3
911
912static int double_lock_balance(struct rq *this_rq, struct rq *busiest);
Peter Zijlstra1b12bbc2008-08-11 09:30:22 +0200913static void double_unlock_balance(struct rq *this_rq, struct rq *busiest);
914
Steven Rostedte8fa1362008-01-25 21:08:05 +0100915static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep);
916
Steven Rostedtf65eda42008-01-25 21:08:07 +0100917static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
918{
919 if (!task_running(rq, p) &&
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100920 (cpu < 0 || cpu_isset(cpu, p->cpus_allowed)) &&
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100921 (p->rt.nr_cpus_allowed > 1))
Steven Rostedtf65eda42008-01-25 21:08:07 +0100922 return 1;
923 return 0;
924}
925
Steven Rostedte8fa1362008-01-25 21:08:05 +0100926/* Return the second highest RT task, NULL otherwise */
Ingo Molnar79064fb2008-01-25 21:08:14 +0100927static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu)
Steven Rostedte8fa1362008-01-25 21:08:05 +0100928{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100929 struct task_struct *next = NULL;
930 struct sched_rt_entity *rt_se;
931 struct rt_prio_array *array;
932 struct rt_rq *rt_rq;
Steven Rostedte8fa1362008-01-25 21:08:05 +0100933 int idx;
934
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100935 for_each_leaf_rt_rq(rt_rq, rq) {
936 array = &rt_rq->active;
937 idx = sched_find_first_bit(array->bitmap);
938 next_idx:
939 if (idx >= MAX_RT_PRIO)
940 continue;
941 if (next && next->prio < idx)
942 continue;
943 list_for_each_entry(rt_se, array->queue + idx, run_list) {
944 struct task_struct *p = rt_task_of(rt_se);
945 if (pick_rt_task(rq, p, cpu)) {
946 next = p;
947 break;
948 }
949 }
950 if (!next) {
951 idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
952 goto next_idx;
953 }
Steven Rostedte8fa1362008-01-25 21:08:05 +0100954 }
955
Steven Rostedte8fa1362008-01-25 21:08:05 +0100956 return next;
957}
958
959static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);
960
Gregory Haskins6e1254d2008-01-25 21:08:11 +0100961static inline int pick_optimal_cpu(int this_cpu, cpumask_t *mask)
962{
963 int first;
964
965 /* "this_cpu" is cheaper to preempt than a remote processor */
966 if ((this_cpu != -1) && cpu_isset(this_cpu, *mask))
967 return this_cpu;
968
969 first = first_cpu(*mask);
970 if (first != NR_CPUS)
971 return first;
972
973 return -1;
974}
975
976static int find_lowest_rq(struct task_struct *task)
977{
978 struct sched_domain *sd;
979 cpumask_t *lowest_mask = &__get_cpu_var(local_cpu_mask);
980 int this_cpu = smp_processor_id();
981 int cpu = task_cpu(task);
982
Gregory Haskins6e0534f2008-05-12 21:21:01 +0200983 if (task->rt.nr_cpus_allowed == 1)
984 return -1; /* No other targets possible */
985
986 if (!cpupri_find(&task_rq(task)->rd->cpupri, task, lowest_mask))
Gregory Haskins06f90db2008-01-25 21:08:13 +0100987 return -1; /* No targets found */
988
989 /*
Max Krasnyanskye761b772008-07-15 04:43:49 -0700990 * Only consider CPUs that are usable for migration.
991 * I guess we might want to change cpupri_find() to ignore those
992 * in the first place.
993 */
994 cpus_and(*lowest_mask, *lowest_mask, cpu_active_map);
995
996 /*
Gregory Haskins6e1254d2008-01-25 21:08:11 +0100997 * At this point we have built a mask of cpus representing the
998 * lowest priority tasks in the system. Now we want to elect
999 * the best one based on our affinity and topology.
1000 *
1001 * We prioritize the last cpu that the task executed on since
1002 * it is most likely cache-hot in that location.
1003 */
1004 if (cpu_isset(cpu, *lowest_mask))
1005 return cpu;
1006
1007 /*
1008 * Otherwise, we consult the sched_domains span maps to figure
1009 * out which cpu is logically closest to our hot cache data.
1010 */
1011 if (this_cpu == cpu)
1012 this_cpu = -1; /* Skip this_cpu opt if the same */
1013
1014 for_each_domain(cpu, sd) {
1015 if (sd->flags & SD_WAKE_AFFINE) {
1016 cpumask_t domain_mask;
1017 int best_cpu;
1018
1019 cpus_and(domain_mask, sd->span, *lowest_mask);
1020
1021 best_cpu = pick_optimal_cpu(this_cpu,
1022 &domain_mask);
1023 if (best_cpu != -1)
1024 return best_cpu;
1025 }
1026 }
1027
1028 /*
1029 * And finally, if there were no matches within the domains
1030 * just give the caller *something* to work with from the compatible
1031 * locations.
1032 */
1033 return pick_optimal_cpu(this_cpu, lowest_mask);
Gregory Haskins07b40322008-01-25 21:08:10 +01001034}
1035
Steven Rostedte8fa1362008-01-25 21:08:05 +01001036/* Will lock the rq it finds */
Ingo Molnar4df64c02008-01-25 21:08:15 +01001037static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
Steven Rostedte8fa1362008-01-25 21:08:05 +01001038{
1039 struct rq *lowest_rq = NULL;
Steven Rostedte8fa1362008-01-25 21:08:05 +01001040 int tries;
Ingo Molnar4df64c02008-01-25 21:08:15 +01001041 int cpu;
Steven Rostedte8fa1362008-01-25 21:08:05 +01001042
1043 for (tries = 0; tries < RT_MAX_TRIES; tries++) {
Gregory Haskins07b40322008-01-25 21:08:10 +01001044 cpu = find_lowest_rq(task);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001045
Gregory Haskins2de0b462008-01-25 21:08:10 +01001046 if ((cpu == -1) || (cpu == rq->cpu))
Steven Rostedte8fa1362008-01-25 21:08:05 +01001047 break;
1048
Gregory Haskins07b40322008-01-25 21:08:10 +01001049 lowest_rq = cpu_rq(cpu);
1050
Steven Rostedte8fa1362008-01-25 21:08:05 +01001051 /* if the prio of this runqueue changed, try again */
Gregory Haskins07b40322008-01-25 21:08:10 +01001052 if (double_lock_balance(rq, lowest_rq)) {
Steven Rostedte8fa1362008-01-25 21:08:05 +01001053 /*
1054 * We had to unlock the run queue. In
1055 * the mean time, task could have
1056 * migrated already or had its affinity changed.
1057 * Also make sure that it wasn't scheduled on its rq.
1058 */
Gregory Haskins07b40322008-01-25 21:08:10 +01001059 if (unlikely(task_rq(task) != rq ||
Ingo Molnar4df64c02008-01-25 21:08:15 +01001060 !cpu_isset(lowest_rq->cpu,
1061 task->cpus_allowed) ||
Gregory Haskins07b40322008-01-25 21:08:10 +01001062 task_running(rq, task) ||
Steven Rostedte8fa1362008-01-25 21:08:05 +01001063 !task->se.on_rq)) {
Ingo Molnar4df64c02008-01-25 21:08:15 +01001064
Steven Rostedte8fa1362008-01-25 21:08:05 +01001065 spin_unlock(&lowest_rq->lock);
1066 lowest_rq = NULL;
1067 break;
1068 }
1069 }
1070
1071 /* If this rq is still suitable use it. */
1072 if (lowest_rq->rt.highest_prio > task->prio)
1073 break;
1074
1075 /* try again */
Peter Zijlstra1b12bbc2008-08-11 09:30:22 +02001076 double_unlock_balance(rq, lowest_rq);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001077 lowest_rq = NULL;
1078 }
1079
1080 return lowest_rq;
1081}
1082
1083/*
1084 * If the current CPU has more than one RT task, see if the non
1085 * running task can migrate over to a CPU that is running a task
1086 * of lesser priority.
1087 */
Gregory Haskins697f0a42008-01-25 21:08:09 +01001088static int push_rt_task(struct rq *rq)
Steven Rostedte8fa1362008-01-25 21:08:05 +01001089{
1090 struct task_struct *next_task;
1091 struct rq *lowest_rq;
1092 int ret = 0;
1093 int paranoid = RT_MAX_TRIES;
1094
Gregory Haskinsa22d7fc2008-01-25 21:08:12 +01001095 if (!rq->rt.overloaded)
1096 return 0;
1097
Gregory Haskins697f0a42008-01-25 21:08:09 +01001098 next_task = pick_next_highest_task_rt(rq, -1);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001099 if (!next_task)
1100 return 0;
1101
1102 retry:
Gregory Haskins697f0a42008-01-25 21:08:09 +01001103 if (unlikely(next_task == rq->curr)) {
Steven Rostedtf65eda42008-01-25 21:08:07 +01001104 WARN_ON(1);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001105 return 0;
Steven Rostedtf65eda42008-01-25 21:08:07 +01001106 }
Steven Rostedte8fa1362008-01-25 21:08:05 +01001107
1108 /*
1109 * It's possible that the next_task slipped in of
1110 * higher priority than current. If that's the case
1111 * just reschedule current.
1112 */
Gregory Haskins697f0a42008-01-25 21:08:09 +01001113 if (unlikely(next_task->prio < rq->curr->prio)) {
1114 resched_task(rq->curr);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001115 return 0;
1116 }
1117
Gregory Haskins697f0a42008-01-25 21:08:09 +01001118 /* We might release rq lock */
Steven Rostedte8fa1362008-01-25 21:08:05 +01001119 get_task_struct(next_task);
1120
1121 /* find_lock_lowest_rq locks the rq if found */
Gregory Haskins697f0a42008-01-25 21:08:09 +01001122 lowest_rq = find_lock_lowest_rq(next_task, rq);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001123 if (!lowest_rq) {
1124 struct task_struct *task;
1125 /*
Gregory Haskins697f0a42008-01-25 21:08:09 +01001126 * find lock_lowest_rq releases rq->lock
Steven Rostedte8fa1362008-01-25 21:08:05 +01001127 * so it is possible that next_task has changed.
1128 * If it has, then try again.
1129 */
Gregory Haskins697f0a42008-01-25 21:08:09 +01001130 task = pick_next_highest_task_rt(rq, -1);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001131 if (unlikely(task != next_task) && task && paranoid--) {
1132 put_task_struct(next_task);
1133 next_task = task;
1134 goto retry;
1135 }
1136 goto out;
1137 }
1138
Gregory Haskins697f0a42008-01-25 21:08:09 +01001139 deactivate_task(rq, next_task, 0);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001140 set_task_cpu(next_task, lowest_rq->cpu);
1141 activate_task(lowest_rq, next_task, 0);
1142
1143 resched_task(lowest_rq->curr);
1144
Peter Zijlstra1b12bbc2008-08-11 09:30:22 +02001145 double_unlock_balance(rq, lowest_rq);
Steven Rostedte8fa1362008-01-25 21:08:05 +01001146
1147 ret = 1;
1148out:
1149 put_task_struct(next_task);
1150
1151 return ret;
1152}
1153
1154/*
1155 * TODO: Currently we just use the second highest prio task on
1156 * the queue, and stop when it can't migrate (or there's
1157 * no more RT tasks). There may be a case where a lower
1158 * priority RT task has a different affinity than the
1159 * higher RT task. In this case the lower RT task could
1160 * possibly be able to migrate where as the higher priority
1161 * RT task could not. We currently ignore this issue.
1162 * Enhancements are welcome!
1163 */
1164static void push_rt_tasks(struct rq *rq)
1165{
1166 /* push_rt_task will return true if it moved an RT */
1167 while (push_rt_task(rq))
1168 ;
1169}
1170
Steven Rostedtf65eda42008-01-25 21:08:07 +01001171static int pull_rt_task(struct rq *this_rq)
1172{
Ingo Molnar80bf3172008-01-25 21:08:17 +01001173 int this_cpu = this_rq->cpu, ret = 0, cpu;
1174 struct task_struct *p, *next;
Steven Rostedtf65eda42008-01-25 21:08:07 +01001175 struct rq *src_rq;
Steven Rostedtf65eda42008-01-25 21:08:07 +01001176
Gregory Haskins637f5082008-01-25 21:08:18 +01001177 if (likely(!rt_overloaded(this_rq)))
Steven Rostedtf65eda42008-01-25 21:08:07 +01001178 return 0;
1179
1180 next = pick_next_task_rt(this_rq);
1181
Mike Travis363ab6f2008-05-12 21:21:13 +02001182 for_each_cpu_mask_nr(cpu, this_rq->rd->rto_mask) {
Steven Rostedtf65eda42008-01-25 21:08:07 +01001183 if (this_cpu == cpu)
1184 continue;
1185
1186 src_rq = cpu_rq(cpu);
Steven Rostedtf65eda42008-01-25 21:08:07 +01001187 /*
1188 * We can potentially drop this_rq's lock in
1189 * double_lock_balance, and another CPU could
1190 * steal our next task - hence we must cause
1191 * the caller to recalculate the next task
1192 * in that case:
1193 */
1194 if (double_lock_balance(this_rq, src_rq)) {
1195 struct task_struct *old_next = next;
Ingo Molnar80bf3172008-01-25 21:08:17 +01001196
Steven Rostedtf65eda42008-01-25 21:08:07 +01001197 next = pick_next_task_rt(this_rq);
1198 if (next != old_next)
1199 ret = 1;
1200 }
1201
1202 /*
1203 * Are there still pullable RT tasks?
1204 */
Mike Galbraith614ee1f2008-01-25 21:08:30 +01001205 if (src_rq->rt.rt_nr_running <= 1)
1206 goto skip;
Steven Rostedtf65eda42008-01-25 21:08:07 +01001207
Steven Rostedtf65eda42008-01-25 21:08:07 +01001208 p = pick_next_highest_task_rt(src_rq, this_cpu);
1209
1210 /*
1211 * Do we have an RT task that preempts
1212 * the to-be-scheduled task?
1213 */
1214 if (p && (!next || (p->prio < next->prio))) {
1215 WARN_ON(p == src_rq->curr);
1216 WARN_ON(!p->se.on_rq);
1217
1218 /*
1219 * There's a chance that p is higher in priority
1220 * than what's currently running on its cpu.
1221 * This is just that p is wakeing up and hasn't
1222 * had a chance to schedule. We only pull
1223 * p if it is lower in priority than the
1224 * current task on the run queue or
1225 * this_rq next task is lower in prio than
1226 * the current task on that rq.
1227 */
1228 if (p->prio < src_rq->curr->prio ||
1229 (next && next->prio < src_rq->curr->prio))
Mike Galbraith614ee1f2008-01-25 21:08:30 +01001230 goto skip;
Steven Rostedtf65eda42008-01-25 21:08:07 +01001231
1232 ret = 1;
1233
1234 deactivate_task(src_rq, p, 0);
1235 set_task_cpu(p, this_cpu);
1236 activate_task(this_rq, p, 0);
1237 /*
1238 * We continue with the search, just in
1239 * case there's an even higher prio task
1240 * in another runqueue. (low likelyhood
1241 * but possible)
Ingo Molnar80bf3172008-01-25 21:08:17 +01001242 *
Steven Rostedtf65eda42008-01-25 21:08:07 +01001243 * Update next so that we won't pick a task
1244 * on another cpu with a priority lower (or equal)
1245 * than the one we just picked.
1246 */
1247 next = p;
1248
1249 }
Mike Galbraith614ee1f2008-01-25 21:08:30 +01001250 skip:
Peter Zijlstra1b12bbc2008-08-11 09:30:22 +02001251 double_unlock_balance(this_rq, src_rq);
Steven Rostedtf65eda42008-01-25 21:08:07 +01001252 }
1253
1254 return ret;
1255}
1256
Steven Rostedt9a897c52008-01-25 21:08:22 +01001257static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
Steven Rostedtf65eda42008-01-25 21:08:07 +01001258{
1259 /* Try to pull RT tasks here if we lower this rq's prio */
Ingo Molnar7f51f292008-01-25 21:08:17 +01001260 if (unlikely(rt_task(prev)) && rq->rt.highest_prio > prev->prio)
Steven Rostedtf65eda42008-01-25 21:08:07 +01001261 pull_rt_task(rq);
1262}
1263
Steven Rostedt9a897c52008-01-25 21:08:22 +01001264static void post_schedule_rt(struct rq *rq)
Steven Rostedte8fa1362008-01-25 21:08:05 +01001265{
1266 /*
1267 * If we have more than one rt_task queued, then
1268 * see if we can push the other rt_tasks off to other CPUS.
1269 * Note we may release the rq lock, and since
1270 * the lock was owned by prev, we need to release it
1271 * first via finish_lock_switch and then reaquire it here.
1272 */
Gregory Haskinsa22d7fc2008-01-25 21:08:12 +01001273 if (unlikely(rq->rt.overloaded)) {
Steven Rostedte8fa1362008-01-25 21:08:05 +01001274 spin_lock_irq(&rq->lock);
1275 push_rt_tasks(rq);
1276 spin_unlock_irq(&rq->lock);
1277 }
1278}
1279
Gregory Haskins8ae121a2008-04-23 07:13:29 -04001280/*
1281 * If we are not running and we are not going to reschedule soon, we should
1282 * try to push tasks away now
1283 */
Steven Rostedt9a897c52008-01-25 21:08:22 +01001284static void task_wake_up_rt(struct rq *rq, struct task_struct *p)
Steven Rostedt4642daf2008-01-25 21:08:07 +01001285{
Steven Rostedt9a897c52008-01-25 21:08:22 +01001286 if (!task_running(rq, p) &&
Gregory Haskins8ae121a2008-04-23 07:13:29 -04001287 !test_tsk_need_resched(rq->curr) &&
Gregory Haskinsa22d7fc2008-01-25 21:08:12 +01001288 rq->rt.overloaded)
Steven Rostedt4642daf2008-01-25 21:08:07 +01001289 push_rt_tasks(rq);
1290}
1291
Peter Williams43010652007-08-09 11:16:46 +02001292static unsigned long
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001293load_balance_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
Peter Williamse1d14842007-10-24 18:23:51 +02001294 unsigned long max_load_move,
1295 struct sched_domain *sd, enum cpu_idle_type idle,
1296 int *all_pinned, int *this_best_prio)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001297{
Steven Rostedtc7a1e462008-01-25 21:08:07 +01001298 /* don't touch RT tasks */
1299 return 0;
Peter Williamse1d14842007-10-24 18:23:51 +02001300}
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001301
Peter Williamse1d14842007-10-24 18:23:51 +02001302static int
1303move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
1304 struct sched_domain *sd, enum cpu_idle_type idle)
1305{
Steven Rostedtc7a1e462008-01-25 21:08:07 +01001306 /* don't touch RT tasks */
1307 return 0;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001308}
Ingo Molnardeeeccd2008-01-25 21:08:15 +01001309
Mike Traviscd8ba7c2008-03-26 14:23:49 -07001310static void set_cpus_allowed_rt(struct task_struct *p,
1311 const cpumask_t *new_mask)
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001312{
1313 int weight = cpus_weight(*new_mask);
1314
1315 BUG_ON(!rt_task(p));
1316
1317 /*
1318 * Update the migration status of the RQ if we have an RT task
1319 * which is running AND changing its weight value.
1320 */
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001321 if (p->se.on_rq && (weight != p->rt.nr_cpus_allowed)) {
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001322 struct rq *rq = task_rq(p);
1323
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001324 if ((p->rt.nr_cpus_allowed <= 1) && (weight > 1)) {
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001325 rq->rt.rt_nr_migratory++;
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001326 } else if ((p->rt.nr_cpus_allowed > 1) && (weight <= 1)) {
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001327 BUG_ON(!rq->rt.rt_nr_migratory);
1328 rq->rt.rt_nr_migratory--;
1329 }
1330
1331 update_rt_migration(rq);
1332 }
1333
1334 p->cpus_allowed = *new_mask;
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001335 p->rt.nr_cpus_allowed = weight;
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001336}
Ingo Molnardeeeccd2008-01-25 21:08:15 +01001337
Ingo Molnarbdd7c812008-01-25 21:08:18 +01001338/* Assumes rq->lock is held */
Gregory Haskins1f11eb62008-06-04 15:04:05 -04001339static void rq_online_rt(struct rq *rq)
Ingo Molnarbdd7c812008-01-25 21:08:18 +01001340{
1341 if (rq->rt.overloaded)
1342 rt_set_overload(rq);
Gregory Haskins6e0534f2008-05-12 21:21:01 +02001343
Peter Zijlstra7def2be2008-06-05 14:49:58 +02001344 __enable_runtime(rq);
1345
Gregory Haskins6e0534f2008-05-12 21:21:01 +02001346 cpupri_set(&rq->rd->cpupri, rq->cpu, rq->rt.highest_prio);
Ingo Molnarbdd7c812008-01-25 21:08:18 +01001347}
1348
1349/* Assumes rq->lock is held */
Gregory Haskins1f11eb62008-06-04 15:04:05 -04001350static void rq_offline_rt(struct rq *rq)
Ingo Molnarbdd7c812008-01-25 21:08:18 +01001351{
1352 if (rq->rt.overloaded)
1353 rt_clear_overload(rq);
Gregory Haskins6e0534f2008-05-12 21:21:01 +02001354
Peter Zijlstra7def2be2008-06-05 14:49:58 +02001355 __disable_runtime(rq);
1356
Gregory Haskins6e0534f2008-05-12 21:21:01 +02001357 cpupri_set(&rq->rd->cpupri, rq->cpu, CPUPRI_INVALID);
Ingo Molnarbdd7c812008-01-25 21:08:18 +01001358}
Steven Rostedtcb469842008-01-25 21:08:22 +01001359
1360/*
1361 * When switch from the rt queue, we bring ourselves to a position
1362 * that we might want to pull RT tasks from other runqueues.
1363 */
1364static void switched_from_rt(struct rq *rq, struct task_struct *p,
1365 int running)
1366{
1367 /*
1368 * If there are other RT tasks then we will reschedule
1369 * and the scheduling of the other RT tasks will handle
1370 * the balancing. But if we are the last RT task
1371 * we may need to handle the pulling of RT tasks
1372 * now.
1373 */
1374 if (!rq->rt.rt_nr_running)
1375 pull_rt_task(rq);
1376}
Steven Rostedte8fa1362008-01-25 21:08:05 +01001377#endif /* CONFIG_SMP */
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001378
Steven Rostedtcb469842008-01-25 21:08:22 +01001379/*
1380 * When switching a task to RT, we may overload the runqueue
1381 * with RT tasks. In this case we try to push them off to
1382 * other runqueues.
1383 */
1384static void switched_to_rt(struct rq *rq, struct task_struct *p,
1385 int running)
1386{
1387 int check_resched = 1;
1388
1389 /*
1390 * If we are already running, then there's nothing
1391 * that needs to be done. But if we are not running
1392 * we may need to preempt the current running task.
1393 * If that current running task is also an RT task
1394 * then see if we can move to another run queue.
1395 */
1396 if (!running) {
1397#ifdef CONFIG_SMP
1398 if (rq->rt.overloaded && push_rt_task(rq) &&
1399 /* Don't resched if we changed runqueues */
1400 rq != task_rq(p))
1401 check_resched = 0;
1402#endif /* CONFIG_SMP */
1403 if (check_resched && p->prio < rq->curr->prio)
1404 resched_task(rq->curr);
1405 }
1406}
1407
1408/*
1409 * Priority of the task has changed. This may cause
1410 * us to initiate a push or pull.
1411 */
1412static void prio_changed_rt(struct rq *rq, struct task_struct *p,
1413 int oldprio, int running)
1414{
1415 if (running) {
1416#ifdef CONFIG_SMP
1417 /*
1418 * If our priority decreases while running, we
1419 * may need to pull tasks to this runqueue.
1420 */
1421 if (oldprio < p->prio)
1422 pull_rt_task(rq);
1423 /*
1424 * If there's a higher priority task waiting to run
Steven Rostedt6fa46fa2008-03-05 10:00:12 -05001425 * then reschedule. Note, the above pull_rt_task
1426 * can release the rq lock and p could migrate.
1427 * Only reschedule if p is still on the same runqueue.
Steven Rostedtcb469842008-01-25 21:08:22 +01001428 */
Steven Rostedt6fa46fa2008-03-05 10:00:12 -05001429 if (p->prio > rq->rt.highest_prio && rq->curr == p)
Steven Rostedtcb469842008-01-25 21:08:22 +01001430 resched_task(p);
1431#else
1432 /* For UP simply resched on drop of prio */
1433 if (oldprio < p->prio)
1434 resched_task(p);
1435#endif /* CONFIG_SMP */
1436 } else {
1437 /*
1438 * This task is not running, but if it is
1439 * greater than the current running task
1440 * then reschedule.
1441 */
1442 if (p->prio < rq->curr->prio)
1443 resched_task(rq->curr);
1444 }
1445}
1446
Peter Zijlstra78f2c7d2008-01-25 21:08:27 +01001447static void watchdog(struct rq *rq, struct task_struct *p)
1448{
1449 unsigned long soft, hard;
1450
1451 if (!p->signal)
1452 return;
1453
1454 soft = p->signal->rlim[RLIMIT_RTTIME].rlim_cur;
1455 hard = p->signal->rlim[RLIMIT_RTTIME].rlim_max;
1456
1457 if (soft != RLIM_INFINITY) {
1458 unsigned long next;
1459
1460 p->rt.timeout++;
1461 next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ);
Peter Zijlstra5a52dd52008-01-25 21:08:32 +01001462 if (p->rt.timeout > next)
Frank Mayharf06febc2008-09-12 09:54:39 -07001463 p->cputime_expires.sched_exp = p->se.sum_exec_runtime;
Peter Zijlstra78f2c7d2008-01-25 21:08:27 +01001464 }
1465}
Steven Rostedtcb469842008-01-25 21:08:22 +01001466
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001467static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001468{
Peter Zijlstra67e2be02007-12-20 15:01:17 +01001469 update_curr_rt(rq);
1470
Peter Zijlstra78f2c7d2008-01-25 21:08:27 +01001471 watchdog(rq, p);
1472
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001473 /*
1474 * RR tasks need a special form of timeslice management.
1475 * FIFO tasks have no timeslices.
1476 */
1477 if (p->policy != SCHED_RR)
1478 return;
1479
Peter Zijlstrafa717062008-01-25 21:08:27 +01001480 if (--p->rt.time_slice)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001481 return;
1482
Peter Zijlstrafa717062008-01-25 21:08:27 +01001483 p->rt.time_slice = DEF_TIMESLICE;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001484
Dmitry Adamushko98fbc792007-08-24 20:39:10 +02001485 /*
1486 * Requeue to the end of queue if we are not the only element
1487 * on the queue:
1488 */
Peter Zijlstrafa717062008-01-25 21:08:27 +01001489 if (p->rt.run_list.prev != p->rt.run_list.next) {
Dmitry Adamushko7ebefa82008-07-01 23:32:15 +02001490 requeue_task_rt(rq, p, 0);
Dmitry Adamushko98fbc792007-08-24 20:39:10 +02001491 set_tsk_need_resched(p);
1492 }
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001493}
1494
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001495static void set_curr_task_rt(struct rq *rq)
1496{
1497 struct task_struct *p = rq->curr;
1498
1499 p->se.exec_start = rq->clock;
1500}
1501
Harvey Harrison2abdad02008-04-25 10:53:13 -07001502static const struct sched_class rt_sched_class = {
Ingo Molnar5522d5d2007-10-15 17:00:12 +02001503 .next = &fair_sched_class,
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001504 .enqueue_task = enqueue_task_rt,
1505 .dequeue_task = dequeue_task_rt,
1506 .yield_task = yield_task_rt,
1507
1508 .check_preempt_curr = check_preempt_curr_rt,
1509
1510 .pick_next_task = pick_next_task_rt,
1511 .put_prev_task = put_prev_task_rt,
1512
Peter Williams681f3e62007-10-24 18:23:51 +02001513#ifdef CONFIG_SMP
Li Zefan4ce72a22008-10-22 15:25:26 +08001514 .select_task_rq = select_task_rq_rt,
1515
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001516 .load_balance = load_balance_rt,
Peter Williamse1d14842007-10-24 18:23:51 +02001517 .move_one_task = move_one_task_rt,
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001518 .set_cpus_allowed = set_cpus_allowed_rt,
Gregory Haskins1f11eb62008-06-04 15:04:05 -04001519 .rq_online = rq_online_rt,
1520 .rq_offline = rq_offline_rt,
Steven Rostedt9a897c52008-01-25 21:08:22 +01001521 .pre_schedule = pre_schedule_rt,
1522 .post_schedule = post_schedule_rt,
1523 .task_wake_up = task_wake_up_rt,
Steven Rostedtcb469842008-01-25 21:08:22 +01001524 .switched_from = switched_from_rt,
Peter Williams681f3e62007-10-24 18:23:51 +02001525#endif
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001526
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001527 .set_curr_task = set_curr_task_rt,
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001528 .task_tick = task_tick_rt,
Steven Rostedtcb469842008-01-25 21:08:22 +01001529
1530 .prio_changed = prio_changed_rt,
1531 .switched_to = switched_to_rt,
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001532};
Peter Zijlstraada18de2008-06-19 14:22:24 +02001533
1534#ifdef CONFIG_SCHED_DEBUG
1535extern void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq);
1536
1537static void print_rt_stats(struct seq_file *m, int cpu)
1538{
1539 struct rt_rq *rt_rq;
1540
1541 rcu_read_lock();
1542 for_each_leaf_rt_rq(rt_rq, cpu_rq(cpu))
1543 print_rt_rq(m, cpu, rt_rq);
1544 rcu_read_unlock();
1545}
Dhaval Giani55e12e52008-06-24 23:39:43 +05301546#endif /* CONFIG_SCHED_DEBUG */