blob: 1144bf55669d01c571d3d332df086efa39cc5d99 [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 Haskins637f5082008-01-25 21:08:18 +010015 cpu_set(rq->cpu, rq->rd->rto_mask);
Steven Rostedt4fd29172008-01-25 21:08:06 +010016 /*
17 * Make sure the mask is visible before we set
18 * the overload count. That is checked to determine
19 * if we should look at the mask. It would be a shame
20 * if we looked at the mask, but the mask was not
21 * updated yet.
22 */
23 wmb();
Gregory Haskins637f5082008-01-25 21:08:18 +010024 atomic_inc(&rq->rd->rto_count);
Steven Rostedt4fd29172008-01-25 21:08:06 +010025}
Ingo Molnar84de4272008-01-25 21:08:15 +010026
Steven Rostedt4fd29172008-01-25 21:08:06 +010027static inline void rt_clear_overload(struct rq *rq)
28{
29 /* the order here really doesn't matter */
Gregory Haskins637f5082008-01-25 21:08:18 +010030 atomic_dec(&rq->rd->rto_count);
31 cpu_clear(rq->cpu, rq->rd->rto_mask);
Steven Rostedt4fd29172008-01-25 21:08:06 +010032}
Gregory Haskins73fe6aa2008-01-25 21:08:07 +010033
34static void update_rt_migration(struct rq *rq)
35{
Gregory Haskins637f5082008-01-25 21:08:18 +010036 if (rq->rt.rt_nr_migratory && (rq->rt.rt_nr_running > 1)) {
Gregory Haskinscdc8eb92008-01-25 21:08:23 +010037 if (!rq->rt.overloaded) {
38 rt_set_overload(rq);
39 rq->rt.overloaded = 1;
40 }
41 } else if (rq->rt.overloaded) {
Gregory Haskins73fe6aa2008-01-25 21:08:07 +010042 rt_clear_overload(rq);
Gregory Haskins637f5082008-01-25 21:08:18 +010043 rq->rt.overloaded = 0;
44 }
Gregory Haskins73fe6aa2008-01-25 21:08:07 +010045}
Steven Rostedt4fd29172008-01-25 21:08:06 +010046#endif /* CONFIG_SMP */
47
Peter Zijlstra6f505b12008-01-25 21:08:30 +010048static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
Peter Zijlstrafa85ae22008-01-25 21:08:29 +010049{
Peter Zijlstra6f505b12008-01-25 21:08:30 +010050 return container_of(rt_se, struct task_struct, rt);
51}
52
53static inline int on_rt_rq(struct sched_rt_entity *rt_se)
54{
55 return !list_empty(&rt_se->run_list);
56}
57
58#ifdef CONFIG_FAIR_GROUP_SCHED
59
60static inline unsigned int sched_rt_ratio(struct rt_rq *rt_rq)
61{
62 if (!rt_rq->tg)
63 return SCHED_RT_FRAC;
64
65 return rt_rq->tg->rt_ratio;
66}
67
68#define for_each_leaf_rt_rq(rt_rq, rq) \
69 list_for_each_entry(rt_rq, &rq->leaf_rt_rq_list, leaf_rt_rq_list)
70
71static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
72{
73 return rt_rq->rq;
74}
75
76static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
77{
78 return rt_se->rt_rq;
79}
80
81#define for_each_sched_rt_entity(rt_se) \
82 for (; rt_se; rt_se = rt_se->parent)
83
84static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
85{
86 return rt_se->my_q;
87}
88
89static void enqueue_rt_entity(struct sched_rt_entity *rt_se);
90static void dequeue_rt_entity(struct sched_rt_entity *rt_se);
91
92static void sched_rt_ratio_enqueue(struct rt_rq *rt_rq)
93{
94 struct sched_rt_entity *rt_se = rt_rq->rt_se;
95
96 if (rt_se && !on_rt_rq(rt_se) && rt_rq->rt_nr_running) {
97 enqueue_rt_entity(rt_se);
98 resched_task(rq_of_rt_rq(rt_rq)->curr);
99 }
100}
101
102static void sched_rt_ratio_dequeue(struct rt_rq *rt_rq)
103{
104 struct sched_rt_entity *rt_se = rt_rq->rt_se;
105
106 if (rt_se && on_rt_rq(rt_se))
107 dequeue_rt_entity(rt_se);
108}
109
110#else
111
112static inline unsigned int sched_rt_ratio(struct rt_rq *rt_rq)
113{
114 return sysctl_sched_rt_ratio;
115}
116
117#define for_each_leaf_rt_rq(rt_rq, rq) \
118 for (rt_rq = &rq->rt; rt_rq; rt_rq = NULL)
119
120static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
121{
122 return container_of(rt_rq, struct rq, rt);
123}
124
125static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
126{
127 struct task_struct *p = rt_task_of(rt_se);
128 struct rq *rq = task_rq(p);
129
130 return &rq->rt;
131}
132
133#define for_each_sched_rt_entity(rt_se) \
134 for (; rt_se; rt_se = NULL)
135
136static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
137{
138 return NULL;
139}
140
141static inline void sched_rt_ratio_enqueue(struct rt_rq *rt_rq)
142{
143}
144
145static inline void sched_rt_ratio_dequeue(struct rt_rq *rt_rq)
146{
147}
148
149#endif
150
151static inline int rt_se_prio(struct sched_rt_entity *rt_se)
152{
153#ifdef CONFIG_FAIR_GROUP_SCHED
154 struct rt_rq *rt_rq = group_rt_rq(rt_se);
155
156 if (rt_rq)
157 return rt_rq->highest_prio;
158#endif
159
160 return rt_task_of(rt_se)->prio;
161}
162
163static int sched_rt_ratio_exceeded(struct rt_rq *rt_rq)
164{
165 unsigned int rt_ratio = sched_rt_ratio(rt_rq);
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100166 u64 period, ratio;
167
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100168 if (rt_ratio == SCHED_RT_FRAC)
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100169 return 0;
170
171 if (rt_rq->rt_throttled)
172 return 1;
173
174 period = (u64)sysctl_sched_rt_period * NSEC_PER_MSEC;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100175 ratio = (period * rt_ratio) >> SCHED_RT_FRAC_SHIFT;
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100176
177 if (rt_rq->rt_time > ratio) {
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100178 rt_rq->rt_throttled = 1;
179 sched_rt_ratio_dequeue(rt_rq);
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100180 return 1;
181 }
182
183 return 0;
184}
185
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100186static void __update_sched_rt_period(struct rt_rq *rt_rq, u64 period)
187{
188 unsigned long rt_ratio = sched_rt_ratio(rt_rq);
189 u64 ratio = (period * rt_ratio) >> SCHED_RT_FRAC_SHIFT;
190
191 rt_rq->rt_time -= min(rt_rq->rt_time, ratio);
192 if (rt_rq->rt_throttled) {
193 rt_rq->rt_throttled = 0;
194 sched_rt_ratio_enqueue(rt_rq);
195 }
196}
197
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100198static void update_sched_rt_period(struct rq *rq)
199{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100200 struct rt_rq *rt_rq;
201 u64 period;
202
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100203 while (rq->clock > rq->rt_period_expire) {
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100204 period = (u64)sysctl_sched_rt_period * NSEC_PER_MSEC;
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100205 rq->rt_period_expire += period;
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100206
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100207 for_each_leaf_rt_rq(rt_rq, rq)
208 __update_sched_rt_period(rt_rq, period);
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100209 }
210}
211
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200212/*
213 * Update the current task's runtime statistics. Skip current tasks that
214 * are not in our scheduling class.
215 */
Alexey Dobriyana9957442007-10-15 17:00:13 +0200216static void update_curr_rt(struct rq *rq)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200217{
218 struct task_struct *curr = rq->curr;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100219 struct sched_rt_entity *rt_se = &curr->rt;
220 struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200221 u64 delta_exec;
222
223 if (!task_has_rt_policy(curr))
224 return;
225
Ingo Molnard2819182007-08-09 11:16:47 +0200226 delta_exec = rq->clock - curr->se.exec_start;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200227 if (unlikely((s64)delta_exec < 0))
228 delta_exec = 0;
Ingo Molnar6cfb0d52007-08-02 17:41:40 +0200229
230 schedstat_set(curr->se.exec_max, max(curr->se.exec_max, delta_exec));
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200231
232 curr->se.sum_exec_runtime += delta_exec;
Ingo Molnard2819182007-08-09 11:16:47 +0200233 curr->se.exec_start = rq->clock;
Srivatsa Vaddagirid842de82007-12-02 20:04:49 +0100234 cpuacct_charge(curr, delta_exec);
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100235
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100236 rt_rq->rt_time += delta_exec;
237 /*
238 * might make it a tad more accurate:
239 *
240 * update_sched_rt_period(rq);
241 */
242 if (sched_rt_ratio_exceeded(rt_rq))
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100243 resched_task(curr);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200244}
245
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100246static inline
247void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
Steven Rostedt63489e42008-01-25 21:08:03 +0100248{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100249 WARN_ON(!rt_prio(rt_se_prio(rt_se)));
250 rt_rq->rt_nr_running++;
251#if defined CONFIG_SMP || defined CONFIG_FAIR_GROUP_SCHED
252 if (rt_se_prio(rt_se) < rt_rq->highest_prio)
253 rt_rq->highest_prio = rt_se_prio(rt_se);
254#endif
Steven Rostedt764a9d62008-01-25 21:08:04 +0100255#ifdef CONFIG_SMP
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100256 if (rt_se->nr_cpus_allowed > 1) {
257 struct rq *rq = rq_of_rt_rq(rt_rq);
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100258 rq->rt.rt_nr_migratory++;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100259 }
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100260
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100261 update_rt_migration(rq_of_rt_rq(rt_rq));
262#endif
Steven Rostedt63489e42008-01-25 21:08:03 +0100263}
264
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100265static inline
266void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
Steven Rostedt63489e42008-01-25 21:08:03 +0100267{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100268 WARN_ON(!rt_prio(rt_se_prio(rt_se)));
269 WARN_ON(!rt_rq->rt_nr_running);
270 rt_rq->rt_nr_running--;
271#if defined CONFIG_SMP || defined CONFIG_FAIR_GROUP_SCHED
272 if (rt_rq->rt_nr_running) {
Steven Rostedt764a9d62008-01-25 21:08:04 +0100273 struct rt_prio_array *array;
274
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100275 WARN_ON(rt_se_prio(rt_se) < rt_rq->highest_prio);
276 if (rt_se_prio(rt_se) == rt_rq->highest_prio) {
Steven Rostedt764a9d62008-01-25 21:08:04 +0100277 /* recalculate */
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100278 array = &rt_rq->active;
279 rt_rq->highest_prio =
Steven Rostedt764a9d62008-01-25 21:08:04 +0100280 sched_find_first_bit(array->bitmap);
281 } /* otherwise leave rq->highest prio alone */
282 } else
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100283 rt_rq->highest_prio = MAX_RT_PRIO;
284#endif
285#ifdef CONFIG_SMP
286 if (rt_se->nr_cpus_allowed > 1) {
287 struct rq *rq = rq_of_rt_rq(rt_rq);
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100288 rq->rt.rt_nr_migratory--;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100289 }
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100290
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100291 update_rt_migration(rq_of_rt_rq(rt_rq));
Steven Rostedt764a9d62008-01-25 21:08:04 +0100292#endif /* CONFIG_SMP */
Steven Rostedt63489e42008-01-25 21:08:03 +0100293}
294
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100295static void enqueue_rt_entity(struct sched_rt_entity *rt_se)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200296{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100297 struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
298 struct rt_prio_array *array = &rt_rq->active;
299 struct rt_rq *group_rq = group_rt_rq(rt_se);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200300
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100301 if (group_rq && group_rq->rt_throttled)
302 return;
Steven Rostedt63489e42008-01-25 21:08:03 +0100303
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100304 list_add_tail(&rt_se->run_list, array->queue + rt_se_prio(rt_se));
305 __set_bit(rt_se_prio(rt_se), array->bitmap);
Peter Zijlstra78f2c7d2008-01-25 21:08:27 +0100306
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100307 inc_rt_tasks(rt_se, rt_rq);
308}
309
310static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
311{
312 struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
313 struct rt_prio_array *array = &rt_rq->active;
314
315 list_del_init(&rt_se->run_list);
316 if (list_empty(array->queue + rt_se_prio(rt_se)))
317 __clear_bit(rt_se_prio(rt_se), array->bitmap);
318
319 dec_rt_tasks(rt_se, rt_rq);
320}
321
322/*
323 * Because the prio of an upper entry depends on the lower
324 * entries, we must remove entries top - down.
325 *
326 * XXX: O(1/2 h^2) because we can only walk up, not down the chain.
327 * doesn't matter much for now, as h=2 for GROUP_SCHED.
328 */
329static void dequeue_rt_stack(struct task_struct *p)
330{
331 struct sched_rt_entity *rt_se, *top_se;
332
333 /*
334 * dequeue all, top - down.
335 */
336 do {
337 rt_se = &p->rt;
338 top_se = NULL;
339 for_each_sched_rt_entity(rt_se) {
340 if (on_rt_rq(rt_se))
341 top_se = rt_se;
342 }
343 if (top_se)
344 dequeue_rt_entity(top_se);
345 } while (top_se);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200346}
347
348/*
349 * Adding/removing a task to/from a priority array:
350 */
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100351static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
352{
353 struct sched_rt_entity *rt_se = &p->rt;
354
355 if (wakeup)
356 rt_se->timeout = 0;
357
358 dequeue_rt_stack(p);
359
360 /*
361 * enqueue everybody, bottom - up.
362 */
363 for_each_sched_rt_entity(rt_se)
364 enqueue_rt_entity(rt_se);
365
366 inc_cpu_load(rq, p->se.load.weight);
367}
368
Ingo Molnarf02231e2007-08-09 11:16:48 +0200369static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200370{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100371 struct sched_rt_entity *rt_se = &p->rt;
372 struct rt_rq *rt_rq;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200373
Ingo Molnarf1e14ef2007-08-09 11:16:48 +0200374 update_curr_rt(rq);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200375
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100376 dequeue_rt_stack(p);
Steven Rostedt63489e42008-01-25 21:08:03 +0100377
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100378 /*
379 * re-enqueue all non-empty rt_rq entities.
380 */
381 for_each_sched_rt_entity(rt_se) {
382 rt_rq = group_rt_rq(rt_se);
383 if (rt_rq && rt_rq->rt_nr_running)
384 enqueue_rt_entity(rt_se);
385 }
386
387 dec_cpu_load(rq, p->se.load.weight);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200388}
389
390/*
391 * Put task to the end of the run list without the overhead of dequeue
392 * followed by enqueue.
393 */
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100394static
395void requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200396{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100397 struct rt_prio_array *array = &rt_rq->active;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200398
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100399 list_move_tail(&rt_se->run_list, array->queue + rt_se_prio(rt_se));
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200400}
401
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100402static void requeue_task_rt(struct rq *rq, struct task_struct *p)
403{
404 struct sched_rt_entity *rt_se = &p->rt;
405 struct rt_rq *rt_rq;
406
407 for_each_sched_rt_entity(rt_se) {
408 rt_rq = rt_rq_of_se(rt_se);
409 requeue_rt_entity(rt_rq, rt_se);
410 }
411}
412
413static void yield_task_rt(struct rq *rq)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200414{
Dmitry Adamushko4530d7a2007-10-15 17:00:08 +0200415 requeue_task_rt(rq, rq->curr);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200416}
417
Gregory Haskinse7693a32008-01-25 21:08:09 +0100418#ifdef CONFIG_SMP
Gregory Haskins318e0892008-01-25 21:08:10 +0100419static int find_lowest_rq(struct task_struct *task);
420
Gregory Haskinse7693a32008-01-25 21:08:09 +0100421static int select_task_rq_rt(struct task_struct *p, int sync)
422{
Gregory Haskins318e0892008-01-25 21:08:10 +0100423 struct rq *rq = task_rq(p);
424
425 /*
Steven Rostedte1f47d82008-01-25 21:08:12 +0100426 * If the current task is an RT task, then
427 * try to see if we can wake this RT task up on another
428 * runqueue. Otherwise simply start this RT task
429 * on its current runqueue.
430 *
431 * We want to avoid overloading runqueues. Even if
432 * the RT task is of higher priority than the current RT task.
433 * RT tasks behave differently than other tasks. If
434 * one gets preempted, we try to push it off to another queue.
435 * So trying to keep a preempting RT task on the same
436 * cache hot CPU will force the running RT task to
437 * a cold CPU. So we waste all the cache for the lower
438 * RT task in hopes of saving some of a RT task
439 * that is just being woken and probably will have
440 * cold cache anyway.
Gregory Haskins318e0892008-01-25 21:08:10 +0100441 */
Gregory Haskins17b32792008-01-25 21:08:13 +0100442 if (unlikely(rt_task(rq->curr)) &&
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100443 (p->rt.nr_cpus_allowed > 1)) {
Gregory Haskins318e0892008-01-25 21:08:10 +0100444 int cpu = find_lowest_rq(p);
445
446 return (cpu == -1) ? task_cpu(p) : cpu;
447 }
448
449 /*
450 * Otherwise, just let it ride on the affined RQ and the
451 * post-schedule router will push the preempted task away
452 */
Gregory Haskinse7693a32008-01-25 21:08:09 +0100453 return task_cpu(p);
454}
455#endif /* CONFIG_SMP */
456
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200457/*
458 * Preempt the current task with a newly woken task if needed:
459 */
460static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p)
461{
462 if (p->prio < rq->curr->prio)
463 resched_task(rq->curr);
464}
465
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100466static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
467 struct rt_rq *rt_rq)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200468{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100469 struct rt_prio_array *array = &rt_rq->active;
470 struct sched_rt_entity *next = NULL;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200471 struct list_head *queue;
472 int idx;
473
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100474 if (sched_rt_ratio_exceeded(rt_rq))
475 goto out;
Peter Zijlstrafa85ae22008-01-25 21:08:29 +0100476
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200477 idx = sched_find_first_bit(array->bitmap);
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100478 BUG_ON(idx >= MAX_RT_PRIO);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200479
480 queue = array->queue + idx;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100481 next = list_entry(queue->next, struct sched_rt_entity, run_list);
482 out:
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200483 return next;
484}
485
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100486static struct task_struct *pick_next_task_rt(struct rq *rq)
487{
488 struct sched_rt_entity *rt_se;
489 struct task_struct *p;
490 struct rt_rq *rt_rq;
491
492 retry:
493 rt_rq = &rq->rt;
494
495 if (unlikely(!rt_rq->rt_nr_running))
496 return NULL;
497
498 if (sched_rt_ratio_exceeded(rt_rq))
499 return NULL;
500
501 do {
502 rt_se = pick_next_rt_entity(rq, rt_rq);
503 if (unlikely(!rt_se))
504 goto retry;
505 rt_rq = group_rt_rq(rt_se);
506 } while (rt_rq);
507
508 p = rt_task_of(rt_se);
509 p->se.exec_start = rq->clock;
510 return p;
511}
512
Ingo Molnar31ee5292007-08-09 11:16:49 +0200513static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200514{
Ingo Molnarf1e14ef2007-08-09 11:16:48 +0200515 update_curr_rt(rq);
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200516 p->se.exec_start = 0;
517}
518
Peter Williams681f3e62007-10-24 18:23:51 +0200519#ifdef CONFIG_SMP
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100520
Steven Rostedte8fa1362008-01-25 21:08:05 +0100521/* Only try algorithms three times */
522#define RT_MAX_TRIES 3
523
524static int double_lock_balance(struct rq *this_rq, struct rq *busiest);
525static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep);
526
Steven Rostedtf65eda42008-01-25 21:08:07 +0100527static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
528{
529 if (!task_running(rq, p) &&
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100530 (cpu < 0 || cpu_isset(cpu, p->cpus_allowed)) &&
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100531 (p->rt.nr_cpus_allowed > 1))
Steven Rostedtf65eda42008-01-25 21:08:07 +0100532 return 1;
533 return 0;
534}
535
Steven Rostedte8fa1362008-01-25 21:08:05 +0100536/* Return the second highest RT task, NULL otherwise */
Ingo Molnar79064fb2008-01-25 21:08:14 +0100537static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu)
Steven Rostedte8fa1362008-01-25 21:08:05 +0100538{
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100539 struct task_struct *next = NULL;
540 struct sched_rt_entity *rt_se;
541 struct rt_prio_array *array;
542 struct rt_rq *rt_rq;
Steven Rostedte8fa1362008-01-25 21:08:05 +0100543 int idx;
544
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100545 for_each_leaf_rt_rq(rt_rq, rq) {
546 array = &rt_rq->active;
547 idx = sched_find_first_bit(array->bitmap);
548 next_idx:
549 if (idx >= MAX_RT_PRIO)
550 continue;
551 if (next && next->prio < idx)
552 continue;
553 list_for_each_entry(rt_se, array->queue + idx, run_list) {
554 struct task_struct *p = rt_task_of(rt_se);
555 if (pick_rt_task(rq, p, cpu)) {
556 next = p;
557 break;
558 }
559 }
560 if (!next) {
561 idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
562 goto next_idx;
563 }
Steven Rostedte8fa1362008-01-25 21:08:05 +0100564 }
565
Steven Rostedte8fa1362008-01-25 21:08:05 +0100566 return next;
567}
568
569static DEFINE_PER_CPU(cpumask_t, local_cpu_mask);
570
Gregory Haskins6e1254d2008-01-25 21:08:11 +0100571static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask)
Gregory Haskins07b40322008-01-25 21:08:10 +0100572{
Gregory Haskins6e1254d2008-01-25 21:08:11 +0100573 int lowest_prio = -1;
Steven Rostedt610bf052008-01-25 21:08:13 +0100574 int lowest_cpu = -1;
Gregory Haskins06f90db2008-01-25 21:08:13 +0100575 int count = 0;
Steven Rostedt610bf052008-01-25 21:08:13 +0100576 int cpu;
Gregory Haskins07b40322008-01-25 21:08:10 +0100577
Gregory Haskins637f5082008-01-25 21:08:18 +0100578 cpus_and(*lowest_mask, task_rq(task)->rd->online, task->cpus_allowed);
Gregory Haskins07b40322008-01-25 21:08:10 +0100579
580 /*
581 * Scan each rq for the lowest prio.
582 */
Steven Rostedt610bf052008-01-25 21:08:13 +0100583 for_each_cpu_mask(cpu, *lowest_mask) {
Gregory Haskins07b40322008-01-25 21:08:10 +0100584 struct rq *rq = cpu_rq(cpu);
585
Gregory Haskins07b40322008-01-25 21:08:10 +0100586 /* We look for lowest RT prio or non-rt CPU */
587 if (rq->rt.highest_prio >= MAX_RT_PRIO) {
Steven Rostedt610bf052008-01-25 21:08:13 +0100588 /*
589 * if we already found a low RT queue
590 * and now we found this non-rt queue
591 * clear the mask and set our bit.
592 * Otherwise just return the queue as is
593 * and the count==1 will cause the algorithm
594 * to use the first bit found.
595 */
596 if (lowest_cpu != -1) {
Gregory Haskins6e1254d2008-01-25 21:08:11 +0100597 cpus_clear(*lowest_mask);
Steven Rostedt610bf052008-01-25 21:08:13 +0100598 cpu_set(rq->cpu, *lowest_mask);
599 }
Gregory Haskins6e1254d2008-01-25 21:08:11 +0100600 return 1;
Gregory Haskins07b40322008-01-25 21:08:10 +0100601 }
602
603 /* no locking for now */
Gregory Haskins6e1254d2008-01-25 21:08:11 +0100604 if ((rq->rt.highest_prio > task->prio)
605 && (rq->rt.highest_prio >= lowest_prio)) {
606 if (rq->rt.highest_prio > lowest_prio) {
607 /* new low - clear old data */
608 lowest_prio = rq->rt.highest_prio;
Steven Rostedt610bf052008-01-25 21:08:13 +0100609 lowest_cpu = cpu;
610 count = 0;
Gregory Haskins6e1254d2008-01-25 21:08:11 +0100611 }
Gregory Haskins06f90db2008-01-25 21:08:13 +0100612 count++;
Steven Rostedt610bf052008-01-25 21:08:13 +0100613 } else
614 cpu_clear(cpu, *lowest_mask);
615 }
616
617 /*
618 * Clear out all the set bits that represent
619 * runqueues that were of higher prio than
620 * the lowest_prio.
621 */
622 if (lowest_cpu > 0) {
623 /*
624 * Perhaps we could add another cpumask op to
625 * zero out bits. Like cpu_zero_bits(cpumask, nrbits);
626 * Then that could be optimized to use memset and such.
627 */
628 for_each_cpu_mask(cpu, *lowest_mask) {
629 if (cpu >= lowest_cpu)
630 break;
631 cpu_clear(cpu, *lowest_mask);
Gregory Haskins07b40322008-01-25 21:08:10 +0100632 }
633 }
634
Gregory Haskins06f90db2008-01-25 21:08:13 +0100635 return count;
Gregory Haskins6e1254d2008-01-25 21:08:11 +0100636}
637
638static inline int pick_optimal_cpu(int this_cpu, cpumask_t *mask)
639{
640 int first;
641
642 /* "this_cpu" is cheaper to preempt than a remote processor */
643 if ((this_cpu != -1) && cpu_isset(this_cpu, *mask))
644 return this_cpu;
645
646 first = first_cpu(*mask);
647 if (first != NR_CPUS)
648 return first;
649
650 return -1;
651}
652
653static int find_lowest_rq(struct task_struct *task)
654{
655 struct sched_domain *sd;
656 cpumask_t *lowest_mask = &__get_cpu_var(local_cpu_mask);
657 int this_cpu = smp_processor_id();
658 int cpu = task_cpu(task);
Gregory Haskins06f90db2008-01-25 21:08:13 +0100659 int count = find_lowest_cpus(task, lowest_mask);
Gregory Haskins6e1254d2008-01-25 21:08:11 +0100660
Gregory Haskins06f90db2008-01-25 21:08:13 +0100661 if (!count)
662 return -1; /* No targets found */
663
664 /*
665 * There is no sense in performing an optimal search if only one
666 * target is found.
667 */
668 if (count == 1)
669 return first_cpu(*lowest_mask);
Gregory Haskins6e1254d2008-01-25 21:08:11 +0100670
671 /*
672 * At this point we have built a mask of cpus representing the
673 * lowest priority tasks in the system. Now we want to elect
674 * the best one based on our affinity and topology.
675 *
676 * We prioritize the last cpu that the task executed on since
677 * it is most likely cache-hot in that location.
678 */
679 if (cpu_isset(cpu, *lowest_mask))
680 return cpu;
681
682 /*
683 * Otherwise, we consult the sched_domains span maps to figure
684 * out which cpu is logically closest to our hot cache data.
685 */
686 if (this_cpu == cpu)
687 this_cpu = -1; /* Skip this_cpu opt if the same */
688
689 for_each_domain(cpu, sd) {
690 if (sd->flags & SD_WAKE_AFFINE) {
691 cpumask_t domain_mask;
692 int best_cpu;
693
694 cpus_and(domain_mask, sd->span, *lowest_mask);
695
696 best_cpu = pick_optimal_cpu(this_cpu,
697 &domain_mask);
698 if (best_cpu != -1)
699 return best_cpu;
700 }
701 }
702
703 /*
704 * And finally, if there were no matches within the domains
705 * just give the caller *something* to work with from the compatible
706 * locations.
707 */
708 return pick_optimal_cpu(this_cpu, lowest_mask);
Gregory Haskins07b40322008-01-25 21:08:10 +0100709}
710
Steven Rostedte8fa1362008-01-25 21:08:05 +0100711/* Will lock the rq it finds */
Ingo Molnar4df64c02008-01-25 21:08:15 +0100712static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
Steven Rostedte8fa1362008-01-25 21:08:05 +0100713{
714 struct rq *lowest_rq = NULL;
Steven Rostedte8fa1362008-01-25 21:08:05 +0100715 int tries;
Ingo Molnar4df64c02008-01-25 21:08:15 +0100716 int cpu;
Steven Rostedte8fa1362008-01-25 21:08:05 +0100717
718 for (tries = 0; tries < RT_MAX_TRIES; tries++) {
Gregory Haskins07b40322008-01-25 21:08:10 +0100719 cpu = find_lowest_rq(task);
Steven Rostedte8fa1362008-01-25 21:08:05 +0100720
Gregory Haskins2de0b462008-01-25 21:08:10 +0100721 if ((cpu == -1) || (cpu == rq->cpu))
Steven Rostedte8fa1362008-01-25 21:08:05 +0100722 break;
723
Gregory Haskins07b40322008-01-25 21:08:10 +0100724 lowest_rq = cpu_rq(cpu);
725
Steven Rostedte8fa1362008-01-25 21:08:05 +0100726 /* if the prio of this runqueue changed, try again */
Gregory Haskins07b40322008-01-25 21:08:10 +0100727 if (double_lock_balance(rq, lowest_rq)) {
Steven Rostedte8fa1362008-01-25 21:08:05 +0100728 /*
729 * We had to unlock the run queue. In
730 * the mean time, task could have
731 * migrated already or had its affinity changed.
732 * Also make sure that it wasn't scheduled on its rq.
733 */
Gregory Haskins07b40322008-01-25 21:08:10 +0100734 if (unlikely(task_rq(task) != rq ||
Ingo Molnar4df64c02008-01-25 21:08:15 +0100735 !cpu_isset(lowest_rq->cpu,
736 task->cpus_allowed) ||
Gregory Haskins07b40322008-01-25 21:08:10 +0100737 task_running(rq, task) ||
Steven Rostedte8fa1362008-01-25 21:08:05 +0100738 !task->se.on_rq)) {
Ingo Molnar4df64c02008-01-25 21:08:15 +0100739
Steven Rostedte8fa1362008-01-25 21:08:05 +0100740 spin_unlock(&lowest_rq->lock);
741 lowest_rq = NULL;
742 break;
743 }
744 }
745
746 /* If this rq is still suitable use it. */
747 if (lowest_rq->rt.highest_prio > task->prio)
748 break;
749
750 /* try again */
751 spin_unlock(&lowest_rq->lock);
752 lowest_rq = NULL;
753 }
754
755 return lowest_rq;
756}
757
758/*
759 * If the current CPU has more than one RT task, see if the non
760 * running task can migrate over to a CPU that is running a task
761 * of lesser priority.
762 */
Gregory Haskins697f0a42008-01-25 21:08:09 +0100763static int push_rt_task(struct rq *rq)
Steven Rostedte8fa1362008-01-25 21:08:05 +0100764{
765 struct task_struct *next_task;
766 struct rq *lowest_rq;
767 int ret = 0;
768 int paranoid = RT_MAX_TRIES;
769
Gregory Haskinsa22d7fc2008-01-25 21:08:12 +0100770 if (!rq->rt.overloaded)
771 return 0;
772
Gregory Haskins697f0a42008-01-25 21:08:09 +0100773 next_task = pick_next_highest_task_rt(rq, -1);
Steven Rostedte8fa1362008-01-25 21:08:05 +0100774 if (!next_task)
775 return 0;
776
777 retry:
Gregory Haskins697f0a42008-01-25 21:08:09 +0100778 if (unlikely(next_task == rq->curr)) {
Steven Rostedtf65eda42008-01-25 21:08:07 +0100779 WARN_ON(1);
Steven Rostedte8fa1362008-01-25 21:08:05 +0100780 return 0;
Steven Rostedtf65eda42008-01-25 21:08:07 +0100781 }
Steven Rostedte8fa1362008-01-25 21:08:05 +0100782
783 /*
784 * It's possible that the next_task slipped in of
785 * higher priority than current. If that's the case
786 * just reschedule current.
787 */
Gregory Haskins697f0a42008-01-25 21:08:09 +0100788 if (unlikely(next_task->prio < rq->curr->prio)) {
789 resched_task(rq->curr);
Steven Rostedte8fa1362008-01-25 21:08:05 +0100790 return 0;
791 }
792
Gregory Haskins697f0a42008-01-25 21:08:09 +0100793 /* We might release rq lock */
Steven Rostedte8fa1362008-01-25 21:08:05 +0100794 get_task_struct(next_task);
795
796 /* find_lock_lowest_rq locks the rq if found */
Gregory Haskins697f0a42008-01-25 21:08:09 +0100797 lowest_rq = find_lock_lowest_rq(next_task, rq);
Steven Rostedte8fa1362008-01-25 21:08:05 +0100798 if (!lowest_rq) {
799 struct task_struct *task;
800 /*
Gregory Haskins697f0a42008-01-25 21:08:09 +0100801 * find lock_lowest_rq releases rq->lock
Steven Rostedte8fa1362008-01-25 21:08:05 +0100802 * so it is possible that next_task has changed.
803 * If it has, then try again.
804 */
Gregory Haskins697f0a42008-01-25 21:08:09 +0100805 task = pick_next_highest_task_rt(rq, -1);
Steven Rostedte8fa1362008-01-25 21:08:05 +0100806 if (unlikely(task != next_task) && task && paranoid--) {
807 put_task_struct(next_task);
808 next_task = task;
809 goto retry;
810 }
811 goto out;
812 }
813
Gregory Haskins697f0a42008-01-25 21:08:09 +0100814 deactivate_task(rq, next_task, 0);
Steven Rostedte8fa1362008-01-25 21:08:05 +0100815 set_task_cpu(next_task, lowest_rq->cpu);
816 activate_task(lowest_rq, next_task, 0);
817
818 resched_task(lowest_rq->curr);
819
820 spin_unlock(&lowest_rq->lock);
821
822 ret = 1;
823out:
824 put_task_struct(next_task);
825
826 return ret;
827}
828
829/*
830 * TODO: Currently we just use the second highest prio task on
831 * the queue, and stop when it can't migrate (or there's
832 * no more RT tasks). There may be a case where a lower
833 * priority RT task has a different affinity than the
834 * higher RT task. In this case the lower RT task could
835 * possibly be able to migrate where as the higher priority
836 * RT task could not. We currently ignore this issue.
837 * Enhancements are welcome!
838 */
839static void push_rt_tasks(struct rq *rq)
840{
841 /* push_rt_task will return true if it moved an RT */
842 while (push_rt_task(rq))
843 ;
844}
845
Steven Rostedtf65eda42008-01-25 21:08:07 +0100846static int pull_rt_task(struct rq *this_rq)
847{
Ingo Molnar80bf3172008-01-25 21:08:17 +0100848 int this_cpu = this_rq->cpu, ret = 0, cpu;
849 struct task_struct *p, *next;
Steven Rostedtf65eda42008-01-25 21:08:07 +0100850 struct rq *src_rq;
Steven Rostedtf65eda42008-01-25 21:08:07 +0100851
Gregory Haskins637f5082008-01-25 21:08:18 +0100852 if (likely(!rt_overloaded(this_rq)))
Steven Rostedtf65eda42008-01-25 21:08:07 +0100853 return 0;
854
855 next = pick_next_task_rt(this_rq);
856
Gregory Haskins637f5082008-01-25 21:08:18 +0100857 for_each_cpu_mask(cpu, this_rq->rd->rto_mask) {
Steven Rostedtf65eda42008-01-25 21:08:07 +0100858 if (this_cpu == cpu)
859 continue;
860
861 src_rq = cpu_rq(cpu);
Steven Rostedtf65eda42008-01-25 21:08:07 +0100862 /*
863 * We can potentially drop this_rq's lock in
864 * double_lock_balance, and another CPU could
865 * steal our next task - hence we must cause
866 * the caller to recalculate the next task
867 * in that case:
868 */
869 if (double_lock_balance(this_rq, src_rq)) {
870 struct task_struct *old_next = next;
Ingo Molnar80bf3172008-01-25 21:08:17 +0100871
Steven Rostedtf65eda42008-01-25 21:08:07 +0100872 next = pick_next_task_rt(this_rq);
873 if (next != old_next)
874 ret = 1;
875 }
876
877 /*
878 * Are there still pullable RT tasks?
879 */
Mike Galbraith614ee1f2008-01-25 21:08:30 +0100880 if (src_rq->rt.rt_nr_running <= 1)
881 goto skip;
Steven Rostedtf65eda42008-01-25 21:08:07 +0100882
Steven Rostedtf65eda42008-01-25 21:08:07 +0100883 p = pick_next_highest_task_rt(src_rq, this_cpu);
884
885 /*
886 * Do we have an RT task that preempts
887 * the to-be-scheduled task?
888 */
889 if (p && (!next || (p->prio < next->prio))) {
890 WARN_ON(p == src_rq->curr);
891 WARN_ON(!p->se.on_rq);
892
893 /*
894 * There's a chance that p is higher in priority
895 * than what's currently running on its cpu.
896 * This is just that p is wakeing up and hasn't
897 * had a chance to schedule. We only pull
898 * p if it is lower in priority than the
899 * current task on the run queue or
900 * this_rq next task is lower in prio than
901 * the current task on that rq.
902 */
903 if (p->prio < src_rq->curr->prio ||
904 (next && next->prio < src_rq->curr->prio))
Mike Galbraith614ee1f2008-01-25 21:08:30 +0100905 goto skip;
Steven Rostedtf65eda42008-01-25 21:08:07 +0100906
907 ret = 1;
908
909 deactivate_task(src_rq, p, 0);
910 set_task_cpu(p, this_cpu);
911 activate_task(this_rq, p, 0);
912 /*
913 * We continue with the search, just in
914 * case there's an even higher prio task
915 * in another runqueue. (low likelyhood
916 * but possible)
Ingo Molnar80bf3172008-01-25 21:08:17 +0100917 *
Steven Rostedtf65eda42008-01-25 21:08:07 +0100918 * Update next so that we won't pick a task
919 * on another cpu with a priority lower (or equal)
920 * than the one we just picked.
921 */
922 next = p;
923
924 }
Mike Galbraith614ee1f2008-01-25 21:08:30 +0100925 skip:
Steven Rostedtf65eda42008-01-25 21:08:07 +0100926 spin_unlock(&src_rq->lock);
927 }
928
929 return ret;
930}
931
Steven Rostedt9a897c52008-01-25 21:08:22 +0100932static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
Steven Rostedtf65eda42008-01-25 21:08:07 +0100933{
934 /* Try to pull RT tasks here if we lower this rq's prio */
Ingo Molnar7f51f292008-01-25 21:08:17 +0100935 if (unlikely(rt_task(prev)) && rq->rt.highest_prio > prev->prio)
Steven Rostedtf65eda42008-01-25 21:08:07 +0100936 pull_rt_task(rq);
937}
938
Steven Rostedt9a897c52008-01-25 21:08:22 +0100939static void post_schedule_rt(struct rq *rq)
Steven Rostedte8fa1362008-01-25 21:08:05 +0100940{
941 /*
942 * If we have more than one rt_task queued, then
943 * see if we can push the other rt_tasks off to other CPUS.
944 * Note we may release the rq lock, and since
945 * the lock was owned by prev, we need to release it
946 * first via finish_lock_switch and then reaquire it here.
947 */
Gregory Haskinsa22d7fc2008-01-25 21:08:12 +0100948 if (unlikely(rq->rt.overloaded)) {
Steven Rostedte8fa1362008-01-25 21:08:05 +0100949 spin_lock_irq(&rq->lock);
950 push_rt_tasks(rq);
951 spin_unlock_irq(&rq->lock);
952 }
953}
954
Steven Rostedt4642daf2008-01-25 21:08:07 +0100955
Steven Rostedt9a897c52008-01-25 21:08:22 +0100956static void task_wake_up_rt(struct rq *rq, struct task_struct *p)
Steven Rostedt4642daf2008-01-25 21:08:07 +0100957{
Steven Rostedt9a897c52008-01-25 21:08:22 +0100958 if (!task_running(rq, p) &&
Gregory Haskinsa22d7fc2008-01-25 21:08:12 +0100959 (p->prio >= rq->rt.highest_prio) &&
960 rq->rt.overloaded)
Steven Rostedt4642daf2008-01-25 21:08:07 +0100961 push_rt_tasks(rq);
962}
963
Peter Williams43010652007-08-09 11:16:46 +0200964static unsigned long
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200965load_balance_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
Peter Williamse1d14842007-10-24 18:23:51 +0200966 unsigned long max_load_move,
967 struct sched_domain *sd, enum cpu_idle_type idle,
968 int *all_pinned, int *this_best_prio)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200969{
Steven Rostedtc7a1e462008-01-25 21:08:07 +0100970 /* don't touch RT tasks */
971 return 0;
Peter Williamse1d14842007-10-24 18:23:51 +0200972}
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200973
Peter Williamse1d14842007-10-24 18:23:51 +0200974static int
975move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
976 struct sched_domain *sd, enum cpu_idle_type idle)
977{
Steven Rostedtc7a1e462008-01-25 21:08:07 +0100978 /* don't touch RT tasks */
979 return 0;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +0200980}
Ingo Molnardeeeccd2008-01-25 21:08:15 +0100981
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100982static void set_cpus_allowed_rt(struct task_struct *p, cpumask_t *new_mask)
983{
984 int weight = cpus_weight(*new_mask);
985
986 BUG_ON(!rt_task(p));
987
988 /*
989 * Update the migration status of the RQ if we have an RT task
990 * which is running AND changing its weight value.
991 */
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100992 if (p->se.on_rq && (weight != p->rt.nr_cpus_allowed)) {
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100993 struct rq *rq = task_rq(p);
994
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100995 if ((p->rt.nr_cpus_allowed <= 1) && (weight > 1)) {
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100996 rq->rt.rt_nr_migratory++;
Peter Zijlstra6f505b12008-01-25 21:08:30 +0100997 } else if ((p->rt.nr_cpus_allowed > 1) && (weight <= 1)) {
Gregory Haskins73fe6aa2008-01-25 21:08:07 +0100998 BUG_ON(!rq->rt.rt_nr_migratory);
999 rq->rt.rt_nr_migratory--;
1000 }
1001
1002 update_rt_migration(rq);
1003 }
1004
1005 p->cpus_allowed = *new_mask;
Peter Zijlstra6f505b12008-01-25 21:08:30 +01001006 p->rt.nr_cpus_allowed = weight;
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001007}
Ingo Molnardeeeccd2008-01-25 21:08:15 +01001008
Ingo Molnarbdd7c812008-01-25 21:08:18 +01001009/* Assumes rq->lock is held */
1010static void join_domain_rt(struct rq *rq)
1011{
1012 if (rq->rt.overloaded)
1013 rt_set_overload(rq);
1014}
1015
1016/* Assumes rq->lock is held */
1017static void leave_domain_rt(struct rq *rq)
1018{
1019 if (rq->rt.overloaded)
1020 rt_clear_overload(rq);
1021}
Steven Rostedtcb469842008-01-25 21:08:22 +01001022
1023/*
1024 * When switch from the rt queue, we bring ourselves to a position
1025 * that we might want to pull RT tasks from other runqueues.
1026 */
1027static void switched_from_rt(struct rq *rq, struct task_struct *p,
1028 int running)
1029{
1030 /*
1031 * If there are other RT tasks then we will reschedule
1032 * and the scheduling of the other RT tasks will handle
1033 * the balancing. But if we are the last RT task
1034 * we may need to handle the pulling of RT tasks
1035 * now.
1036 */
1037 if (!rq->rt.rt_nr_running)
1038 pull_rt_task(rq);
1039}
Steven Rostedte8fa1362008-01-25 21:08:05 +01001040#endif /* CONFIG_SMP */
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001041
Steven Rostedtcb469842008-01-25 21:08:22 +01001042/*
1043 * When switching a task to RT, we may overload the runqueue
1044 * with RT tasks. In this case we try to push them off to
1045 * other runqueues.
1046 */
1047static void switched_to_rt(struct rq *rq, struct task_struct *p,
1048 int running)
1049{
1050 int check_resched = 1;
1051
1052 /*
1053 * If we are already running, then there's nothing
1054 * that needs to be done. But if we are not running
1055 * we may need to preempt the current running task.
1056 * If that current running task is also an RT task
1057 * then see if we can move to another run queue.
1058 */
1059 if (!running) {
1060#ifdef CONFIG_SMP
1061 if (rq->rt.overloaded && push_rt_task(rq) &&
1062 /* Don't resched if we changed runqueues */
1063 rq != task_rq(p))
1064 check_resched = 0;
1065#endif /* CONFIG_SMP */
1066 if (check_resched && p->prio < rq->curr->prio)
1067 resched_task(rq->curr);
1068 }
1069}
1070
1071/*
1072 * Priority of the task has changed. This may cause
1073 * us to initiate a push or pull.
1074 */
1075static void prio_changed_rt(struct rq *rq, struct task_struct *p,
1076 int oldprio, int running)
1077{
1078 if (running) {
1079#ifdef CONFIG_SMP
1080 /*
1081 * If our priority decreases while running, we
1082 * may need to pull tasks to this runqueue.
1083 */
1084 if (oldprio < p->prio)
1085 pull_rt_task(rq);
1086 /*
1087 * If there's a higher priority task waiting to run
1088 * then reschedule.
1089 */
1090 if (p->prio > rq->rt.highest_prio)
1091 resched_task(p);
1092#else
1093 /* For UP simply resched on drop of prio */
1094 if (oldprio < p->prio)
1095 resched_task(p);
1096#endif /* CONFIG_SMP */
1097 } else {
1098 /*
1099 * This task is not running, but if it is
1100 * greater than the current running task
1101 * then reschedule.
1102 */
1103 if (p->prio < rq->curr->prio)
1104 resched_task(rq->curr);
1105 }
1106}
1107
Peter Zijlstra78f2c7d2008-01-25 21:08:27 +01001108static void watchdog(struct rq *rq, struct task_struct *p)
1109{
1110 unsigned long soft, hard;
1111
1112 if (!p->signal)
1113 return;
1114
1115 soft = p->signal->rlim[RLIMIT_RTTIME].rlim_cur;
1116 hard = p->signal->rlim[RLIMIT_RTTIME].rlim_max;
1117
1118 if (soft != RLIM_INFINITY) {
1119 unsigned long next;
1120
1121 p->rt.timeout++;
1122 next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ);
1123 if (next > p->rt.timeout) {
1124 u64 next_time = p->se.sum_exec_runtime;
1125
1126 next_time += next * (NSEC_PER_SEC/HZ);
1127 if (p->it_sched_expires > next_time)
1128 p->it_sched_expires = next_time;
1129 } else
1130 p->it_sched_expires = p->se.sum_exec_runtime;
1131 }
1132}
Steven Rostedtcb469842008-01-25 21:08:22 +01001133
Peter Zijlstra8f4d37e2008-01-25 21:08:29 +01001134static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001135{
Peter Zijlstra67e2be02007-12-20 15:01:17 +01001136 update_curr_rt(rq);
1137
Peter Zijlstra78f2c7d2008-01-25 21:08:27 +01001138 watchdog(rq, p);
1139
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001140 /*
1141 * RR tasks need a special form of timeslice management.
1142 * FIFO tasks have no timeslices.
1143 */
1144 if (p->policy != SCHED_RR)
1145 return;
1146
Peter Zijlstrafa717062008-01-25 21:08:27 +01001147 if (--p->rt.time_slice)
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001148 return;
1149
Peter Zijlstrafa717062008-01-25 21:08:27 +01001150 p->rt.time_slice = DEF_TIMESLICE;
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001151
Dmitry Adamushko98fbc792007-08-24 20:39:10 +02001152 /*
1153 * Requeue to the end of queue if we are not the only element
1154 * on the queue:
1155 */
Peter Zijlstrafa717062008-01-25 21:08:27 +01001156 if (p->rt.run_list.prev != p->rt.run_list.next) {
Dmitry Adamushko98fbc792007-08-24 20:39:10 +02001157 requeue_task_rt(rq, p);
1158 set_tsk_need_resched(p);
1159 }
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001160}
1161
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001162static void set_curr_task_rt(struct rq *rq)
1163{
1164 struct task_struct *p = rq->curr;
1165
1166 p->se.exec_start = rq->clock;
1167}
1168
Ingo Molnar5522d5d2007-10-15 17:00:12 +02001169const struct sched_class rt_sched_class = {
1170 .next = &fair_sched_class,
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001171 .enqueue_task = enqueue_task_rt,
1172 .dequeue_task = dequeue_task_rt,
1173 .yield_task = yield_task_rt,
Gregory Haskinse7693a32008-01-25 21:08:09 +01001174#ifdef CONFIG_SMP
1175 .select_task_rq = select_task_rq_rt,
1176#endif /* CONFIG_SMP */
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001177
1178 .check_preempt_curr = check_preempt_curr_rt,
1179
1180 .pick_next_task = pick_next_task_rt,
1181 .put_prev_task = put_prev_task_rt,
1182
Peter Williams681f3e62007-10-24 18:23:51 +02001183#ifdef CONFIG_SMP
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001184 .load_balance = load_balance_rt,
Peter Williamse1d14842007-10-24 18:23:51 +02001185 .move_one_task = move_one_task_rt,
Gregory Haskins73fe6aa2008-01-25 21:08:07 +01001186 .set_cpus_allowed = set_cpus_allowed_rt,
Ingo Molnarbdd7c812008-01-25 21:08:18 +01001187 .join_domain = join_domain_rt,
1188 .leave_domain = leave_domain_rt,
Steven Rostedt9a897c52008-01-25 21:08:22 +01001189 .pre_schedule = pre_schedule_rt,
1190 .post_schedule = post_schedule_rt,
1191 .task_wake_up = task_wake_up_rt,
Steven Rostedtcb469842008-01-25 21:08:22 +01001192 .switched_from = switched_from_rt,
Peter Williams681f3e62007-10-24 18:23:51 +02001193#endif
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001194
Srivatsa Vaddagiri83b699e2007-10-15 17:00:08 +02001195 .set_curr_task = set_curr_task_rt,
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001196 .task_tick = task_tick_rt,
Steven Rostedtcb469842008-01-25 21:08:22 +01001197
1198 .prio_changed = prio_changed_rt,
1199 .switched_to = switched_to_rt,
Ingo Molnarbb44e5d2007-07-09 18:51:58 +02001200};