RT: fix push_rt_task() to handle dequeue_pushable properly
[linux-2.6.git] / kernel / sched_rt.c
1 /*
2  * Real-Time Scheduling Class (mapped to the SCHED_FIFO and SCHED_RR
3  * policies)
4  */
5
6 #ifdef CONFIG_SMP
7
8 static inline int rt_overloaded(struct rq *rq)
9 {
10         return atomic_read(&rq->rd->rto_count);
11 }
12
13 static inline void rt_set_overload(struct rq *rq)
14 {
15         if (!rq->online)
16                 return;
17
18         cpumask_set_cpu(rq->cpu, rq->rd->rto_mask);
19         /*
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();
27         atomic_inc(&rq->rd->rto_count);
28 }
29
30 static inline void rt_clear_overload(struct rq *rq)
31 {
32         if (!rq->online)
33                 return;
34
35         /* the order here really doesn't matter */
36         atomic_dec(&rq->rd->rto_count);
37         cpumask_clear_cpu(rq->cpu, rq->rd->rto_mask);
38 }
39
40 static void update_rt_migration(struct rq *rq)
41 {
42         if (rq->rt.rt_nr_migratory && (rq->rt.rt_nr_running > 1)) {
43                 if (!rq->rt.overloaded) {
44                         rt_set_overload(rq);
45                         rq->rt.overloaded = 1;
46                 }
47         } else if (rq->rt.overloaded) {
48                 rt_clear_overload(rq);
49                 rq->rt.overloaded = 0;
50         }
51 }
52
53 static void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
54 {
55         plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
56         plist_node_init(&p->pushable_tasks, p->prio);
57         plist_add(&p->pushable_tasks, &rq->rt.pushable_tasks);
58 }
59
60 static void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
61 {
62         plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
63 }
64
65 #else
66
67 #define enqueue_pushable_task(rq, p) do { } while (0)
68 #define dequeue_pushable_task(rq, p) do { } while (0)
69
70 #endif /* CONFIG_SMP */
71
72 static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
73 {
74         return container_of(rt_se, struct task_struct, rt);
75 }
76
77 static inline int on_rt_rq(struct sched_rt_entity *rt_se)
78 {
79         return !list_empty(&rt_se->run_list);
80 }
81
82 #ifdef CONFIG_RT_GROUP_SCHED
83
84 static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
85 {
86         if (!rt_rq->tg)
87                 return RUNTIME_INF;
88
89         return rt_rq->rt_runtime;
90 }
91
92 static inline u64 sched_rt_period(struct rt_rq *rt_rq)
93 {
94         return ktime_to_ns(rt_rq->tg->rt_bandwidth.rt_period);
95 }
96
97 #define for_each_leaf_rt_rq(rt_rq, rq) \
98         list_for_each_entry(rt_rq, &rq->leaf_rt_rq_list, leaf_rt_rq_list)
99
100 static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
101 {
102         return rt_rq->rq;
103 }
104
105 static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
106 {
107         return rt_se->rt_rq;
108 }
109
110 #define for_each_sched_rt_entity(rt_se) \
111         for (; rt_se; rt_se = rt_se->parent)
112
113 static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
114 {
115         return rt_se->my_q;
116 }
117
118 static void enqueue_rt_entity(struct sched_rt_entity *rt_se);
119 static void dequeue_rt_entity(struct sched_rt_entity *rt_se);
120
121 static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
122 {
123         struct task_struct *curr = rq_of_rt_rq(rt_rq)->curr;
124         struct sched_rt_entity *rt_se = rt_rq->rt_se;
125
126         if (rt_rq->rt_nr_running) {
127                 if (rt_se && !on_rt_rq(rt_se))
128                         enqueue_rt_entity(rt_se);
129                 if (rt_rq->highest_prio.curr < curr->prio)
130                         resched_task(curr);
131         }
132 }
133
134 static void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
135 {
136         struct sched_rt_entity *rt_se = rt_rq->rt_se;
137
138         if (rt_se && on_rt_rq(rt_se))
139                 dequeue_rt_entity(rt_se);
140 }
141
142 static inline int rt_rq_throttled(struct rt_rq *rt_rq)
143 {
144         return rt_rq->rt_throttled && !rt_rq->rt_nr_boosted;
145 }
146
147 static int rt_se_boosted(struct sched_rt_entity *rt_se)
148 {
149         struct rt_rq *rt_rq = group_rt_rq(rt_se);
150         struct task_struct *p;
151
152         if (rt_rq)
153                 return !!rt_rq->rt_nr_boosted;
154
155         p = rt_task_of(rt_se);
156         return p->prio != p->normal_prio;
157 }
158
159 #ifdef CONFIG_SMP
160 static inline const struct cpumask *sched_rt_period_mask(void)
161 {
162         return cpu_rq(smp_processor_id())->rd->span;
163 }
164 #else
165 static inline const struct cpumask *sched_rt_period_mask(void)
166 {
167         return cpu_online_mask;
168 }
169 #endif
170
171 static inline
172 struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
173 {
174         return container_of(rt_b, struct task_group, rt_bandwidth)->rt_rq[cpu];
175 }
176
177 static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
178 {
179         return &rt_rq->tg->rt_bandwidth;
180 }
181
182 #else /* !CONFIG_RT_GROUP_SCHED */
183
184 static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
185 {
186         return rt_rq->rt_runtime;
187 }
188
189 static inline u64 sched_rt_period(struct rt_rq *rt_rq)
190 {
191         return ktime_to_ns(def_rt_bandwidth.rt_period);
192 }
193
194 #define for_each_leaf_rt_rq(rt_rq, rq) \
195         for (rt_rq = &rq->rt; rt_rq; rt_rq = NULL)
196
197 static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
198 {
199         return container_of(rt_rq, struct rq, rt);
200 }
201
202 static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
203 {
204         struct task_struct *p = rt_task_of(rt_se);
205         struct rq *rq = task_rq(p);
206
207         return &rq->rt;
208 }
209
210 #define for_each_sched_rt_entity(rt_se) \
211         for (; rt_se; rt_se = NULL)
212
213 static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
214 {
215         return NULL;
216 }
217
218 static inline void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
219 {
220         if (rt_rq->rt_nr_running)
221                 resched_task(rq_of_rt_rq(rt_rq)->curr);
222 }
223
224 static inline void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
225 {
226 }
227
228 static inline int rt_rq_throttled(struct rt_rq *rt_rq)
229 {
230         return rt_rq->rt_throttled;
231 }
232
233 static inline const struct cpumask *sched_rt_period_mask(void)
234 {
235         return cpu_online_mask;
236 }
237
238 static inline
239 struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
240 {
241         return &cpu_rq(cpu)->rt;
242 }
243
244 static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
245 {
246         return &def_rt_bandwidth;
247 }
248
249 #endif /* CONFIG_RT_GROUP_SCHED */
250
251 #ifdef CONFIG_SMP
252 /*
253  * We ran out of runtime, see if we can borrow some from our neighbours.
254  */
255 static int do_balance_runtime(struct rt_rq *rt_rq)
256 {
257         struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
258         struct root_domain *rd = cpu_rq(smp_processor_id())->rd;
259         int i, weight, more = 0;
260         u64 rt_period;
261
262         weight = cpumask_weight(rd->span);
263
264         spin_lock(&rt_b->rt_runtime_lock);
265         rt_period = ktime_to_ns(rt_b->rt_period);
266         for_each_cpu(i, rd->span) {
267                 struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
268                 s64 diff;
269
270                 if (iter == rt_rq)
271                         continue;
272
273                 spin_lock(&iter->rt_runtime_lock);
274                 /*
275                  * Either all rqs have inf runtime and there's nothing to steal
276                  * or __disable_runtime() below sets a specific rq to inf to
277                  * indicate its been disabled and disalow stealing.
278                  */
279                 if (iter->rt_runtime == RUNTIME_INF)
280                         goto next;
281
282                 /*
283                  * From runqueues with spare time, take 1/n part of their
284                  * spare time, but no more than our period.
285                  */
286                 diff = iter->rt_runtime - iter->rt_time;
287                 if (diff > 0) {
288                         diff = div_u64((u64)diff, weight);
289                         if (rt_rq->rt_runtime + diff > rt_period)
290                                 diff = rt_period - rt_rq->rt_runtime;
291                         iter->rt_runtime -= diff;
292                         rt_rq->rt_runtime += diff;
293                         more = 1;
294                         if (rt_rq->rt_runtime == rt_period) {
295                                 spin_unlock(&iter->rt_runtime_lock);
296                                 break;
297                         }
298                 }
299 next:
300                 spin_unlock(&iter->rt_runtime_lock);
301         }
302         spin_unlock(&rt_b->rt_runtime_lock);
303
304         return more;
305 }
306
307 /*
308  * Ensure this RQ takes back all the runtime it lend to its neighbours.
309  */
310 static void __disable_runtime(struct rq *rq)
311 {
312         struct root_domain *rd = rq->rd;
313         struct rt_rq *rt_rq;
314
315         if (unlikely(!scheduler_running))
316                 return;
317
318         for_each_leaf_rt_rq(rt_rq, rq) {
319                 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
320                 s64 want;
321                 int i;
322
323                 spin_lock(&rt_b->rt_runtime_lock);
324                 spin_lock(&rt_rq->rt_runtime_lock);
325                 /*
326                  * Either we're all inf and nobody needs to borrow, or we're
327                  * already disabled and thus have nothing to do, or we have
328                  * exactly the right amount of runtime to take out.
329                  */
330                 if (rt_rq->rt_runtime == RUNTIME_INF ||
331                                 rt_rq->rt_runtime == rt_b->rt_runtime)
332                         goto balanced;
333                 spin_unlock(&rt_rq->rt_runtime_lock);
334
335                 /*
336                  * Calculate the difference between what we started out with
337                  * and what we current have, that's the amount of runtime
338                  * we lend and now have to reclaim.
339                  */
340                 want = rt_b->rt_runtime - rt_rq->rt_runtime;
341
342                 /*
343                  * Greedy reclaim, take back as much as we can.
344                  */
345                 for_each_cpu(i, rd->span) {
346                         struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
347                         s64 diff;
348
349                         /*
350                          * Can't reclaim from ourselves or disabled runqueues.
351                          */
352                         if (iter == rt_rq || iter->rt_runtime == RUNTIME_INF)
353                                 continue;
354
355                         spin_lock(&iter->rt_runtime_lock);
356                         if (want > 0) {
357                                 diff = min_t(s64, iter->rt_runtime, want);
358                                 iter->rt_runtime -= diff;
359                                 want -= diff;
360                         } else {
361                                 iter->rt_runtime -= want;
362                                 want -= want;
363                         }
364                         spin_unlock(&iter->rt_runtime_lock);
365
366                         if (!want)
367                                 break;
368                 }
369
370                 spin_lock(&rt_rq->rt_runtime_lock);
371                 /*
372                  * We cannot be left wanting - that would mean some runtime
373                  * leaked out of the system.
374                  */
375                 BUG_ON(want);
376 balanced:
377                 /*
378                  * Disable all the borrow logic by pretending we have inf
379                  * runtime - in which case borrowing doesn't make sense.
380                  */
381                 rt_rq->rt_runtime = RUNTIME_INF;
382                 spin_unlock(&rt_rq->rt_runtime_lock);
383                 spin_unlock(&rt_b->rt_runtime_lock);
384         }
385 }
386
387 static void disable_runtime(struct rq *rq)
388 {
389         unsigned long flags;
390
391         spin_lock_irqsave(&rq->lock, flags);
392         __disable_runtime(rq);
393         spin_unlock_irqrestore(&rq->lock, flags);
394 }
395
396 static void __enable_runtime(struct rq *rq)
397 {
398         struct rt_rq *rt_rq;
399
400         if (unlikely(!scheduler_running))
401                 return;
402
403         /*
404          * Reset each runqueue's bandwidth settings
405          */
406         for_each_leaf_rt_rq(rt_rq, rq) {
407                 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
408
409                 spin_lock(&rt_b->rt_runtime_lock);
410                 spin_lock(&rt_rq->rt_runtime_lock);
411                 rt_rq->rt_runtime = rt_b->rt_runtime;
412                 rt_rq->rt_time = 0;
413                 rt_rq->rt_throttled = 0;
414                 spin_unlock(&rt_rq->rt_runtime_lock);
415                 spin_unlock(&rt_b->rt_runtime_lock);
416         }
417 }
418
419 static void enable_runtime(struct rq *rq)
420 {
421         unsigned long flags;
422
423         spin_lock_irqsave(&rq->lock, flags);
424         __enable_runtime(rq);
425         spin_unlock_irqrestore(&rq->lock, flags);
426 }
427
428 static int balance_runtime(struct rt_rq *rt_rq)
429 {
430         int more = 0;
431
432         if (rt_rq->rt_time > rt_rq->rt_runtime) {
433                 spin_unlock(&rt_rq->rt_runtime_lock);
434                 more = do_balance_runtime(rt_rq);
435                 spin_lock(&rt_rq->rt_runtime_lock);
436         }
437
438         return more;
439 }
440 #else /* !CONFIG_SMP */
441 static inline int balance_runtime(struct rt_rq *rt_rq)
442 {
443         return 0;
444 }
445 #endif /* CONFIG_SMP */
446
447 static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)
448 {
449         int i, idle = 1;
450         const struct cpumask *span;
451
452         if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
453                 return 1;
454
455         span = sched_rt_period_mask();
456         for_each_cpu(i, span) {
457                 int enqueue = 0;
458                 struct rt_rq *rt_rq = sched_rt_period_rt_rq(rt_b, i);
459                 struct rq *rq = rq_of_rt_rq(rt_rq);
460
461                 spin_lock(&rq->lock);
462                 if (rt_rq->rt_time) {
463                         u64 runtime;
464
465                         spin_lock(&rt_rq->rt_runtime_lock);
466                         if (rt_rq->rt_throttled)
467                                 balance_runtime(rt_rq);
468                         runtime = rt_rq->rt_runtime;
469                         rt_rq->rt_time -= min(rt_rq->rt_time, overrun*runtime);
470                         if (rt_rq->rt_throttled && rt_rq->rt_time < runtime) {
471                                 rt_rq->rt_throttled = 0;
472                                 enqueue = 1;
473                         }
474                         if (rt_rq->rt_time || rt_rq->rt_nr_running)
475                                 idle = 0;
476                         spin_unlock(&rt_rq->rt_runtime_lock);
477                 } else if (rt_rq->rt_nr_running)
478                         idle = 0;
479
480                 if (enqueue)
481                         sched_rt_rq_enqueue(rt_rq);
482                 spin_unlock(&rq->lock);
483         }
484
485         return idle;
486 }
487
488 static inline int rt_se_prio(struct sched_rt_entity *rt_se)
489 {
490 #ifdef CONFIG_RT_GROUP_SCHED
491         struct rt_rq *rt_rq = group_rt_rq(rt_se);
492
493         if (rt_rq)
494                 return rt_rq->highest_prio.curr;
495 #endif
496
497         return rt_task_of(rt_se)->prio;
498 }
499
500 static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
501 {
502         u64 runtime = sched_rt_runtime(rt_rq);
503
504         if (rt_rq->rt_throttled)
505                 return rt_rq_throttled(rt_rq);
506
507         if (sched_rt_runtime(rt_rq) >= sched_rt_period(rt_rq))
508                 return 0;
509
510         balance_runtime(rt_rq);
511         runtime = sched_rt_runtime(rt_rq);
512         if (runtime == RUNTIME_INF)
513                 return 0;
514
515         if (rt_rq->rt_time > runtime) {
516                 rt_rq->rt_throttled = 1;
517                 if (rt_rq_throttled(rt_rq)) {
518                         sched_rt_rq_dequeue(rt_rq);
519                         return 1;
520                 }
521         }
522
523         return 0;
524 }
525
526 /*
527  * Update the current task's runtime statistics. Skip current tasks that
528  * are not in our scheduling class.
529  */
530 static void update_curr_rt(struct rq *rq)
531 {
532         struct task_struct *curr = rq->curr;
533         struct sched_rt_entity *rt_se = &curr->rt;
534         struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
535         u64 delta_exec;
536
537         if (!task_has_rt_policy(curr))
538                 return;
539
540         delta_exec = rq->clock - curr->se.exec_start;
541         if (unlikely((s64)delta_exec < 0))
542                 delta_exec = 0;
543
544         schedstat_set(curr->se.exec_max, max(curr->se.exec_max, delta_exec));
545
546         curr->se.sum_exec_runtime += delta_exec;
547         account_group_exec_runtime(curr, delta_exec);
548
549         curr->se.exec_start = rq->clock;
550         cpuacct_charge(curr, delta_exec);
551
552         if (!rt_bandwidth_enabled())
553                 return;
554
555         for_each_sched_rt_entity(rt_se) {
556                 rt_rq = rt_rq_of_se(rt_se);
557
558                 if (sched_rt_runtime(rt_rq) != RUNTIME_INF) {
559                         spin_lock(&rt_rq->rt_runtime_lock);
560                         rt_rq->rt_time += delta_exec;
561                         if (sched_rt_runtime_exceeded(rt_rq))
562                                 resched_task(curr);
563                         spin_unlock(&rt_rq->rt_runtime_lock);
564                 }
565         }
566 }
567
568 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
569
570 static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu);
571
572 static inline int next_prio(struct rq *rq)
573 {
574         struct task_struct *next = pick_next_highest_task_rt(rq, rq->cpu);
575
576         if (next && rt_prio(next->prio))
577                 return next->prio;
578         else
579                 return MAX_RT_PRIO;
580 }
581 #endif
582
583 static inline
584 void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
585 {
586         int prio = rt_se_prio(rt_se);
587 #ifdef CONFIG_SMP
588         struct rq *rq = rq_of_rt_rq(rt_rq);
589 #endif
590
591         WARN_ON(!rt_prio(prio));
592         rt_rq->rt_nr_running++;
593 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
594         if (prio < rt_rq->highest_prio.curr) {
595
596                 /*
597                  * If the new task is higher in priority than anything on the
598                  * run-queue, we have a new high that must be published to
599                  * the world.  We also know that the previous high becomes
600                  * our next-highest.
601                  */
602                 rt_rq->highest_prio.next = rt_rq->highest_prio.curr;
603                 rt_rq->highest_prio.curr = prio;
604 #ifdef CONFIG_SMP
605                 if (rq->online)
606                         cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
607 #endif
608         } else if (prio == rt_rq->highest_prio.curr)
609                 /*
610                  * If the next task is equal in priority to the highest on
611                  * the run-queue, then we implicitly know that the next highest
612                  * task cannot be any lower than current
613                  */
614                 rt_rq->highest_prio.next = prio;
615         else if (prio < rt_rq->highest_prio.next)
616                 /*
617                  * Otherwise, we need to recompute next-highest
618                  */
619                 rt_rq->highest_prio.next = next_prio(rq);
620 #endif
621 #ifdef CONFIG_SMP
622         if (rt_se->nr_cpus_allowed > 1)
623                 rq->rt.rt_nr_migratory++;
624
625         update_rt_migration(rq);
626 #endif
627 #ifdef CONFIG_RT_GROUP_SCHED
628         if (rt_se_boosted(rt_se))
629                 rt_rq->rt_nr_boosted++;
630
631         if (rt_rq->tg)
632                 start_rt_bandwidth(&rt_rq->tg->rt_bandwidth);
633 #else
634         start_rt_bandwidth(&def_rt_bandwidth);
635 #endif
636 }
637
638 static inline
639 void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
640 {
641 #ifdef CONFIG_SMP
642         struct rq *rq = rq_of_rt_rq(rt_rq);
643         int highest_prio = rt_rq->highest_prio.curr;
644 #endif
645
646         WARN_ON(!rt_prio(rt_se_prio(rt_se)));
647         WARN_ON(!rt_rq->rt_nr_running);
648         rt_rq->rt_nr_running--;
649 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
650         if (rt_rq->rt_nr_running) {
651                 int prio = rt_se_prio(rt_se);
652
653                 WARN_ON(prio < rt_rq->highest_prio.curr);
654
655                 /*
656                  * This may have been our highest or next-highest priority
657                  * task and therefore we may have some recomputation to do
658                  */
659                 if (prio == rt_rq->highest_prio.curr) {
660                         struct rt_prio_array *array = &rt_rq->active;
661
662                         rt_rq->highest_prio.curr =
663                                 sched_find_first_bit(array->bitmap);
664                 }
665
666                 if (prio <= rt_rq->highest_prio.next)
667                         rt_rq->highest_prio.next = next_prio(rq);
668         } else
669                 rt_rq->highest_prio.curr = MAX_RT_PRIO;
670 #endif
671 #ifdef CONFIG_SMP
672         if (rt_se->nr_cpus_allowed > 1)
673                 rq->rt.rt_nr_migratory--;
674
675         if (rq->online && rt_rq->highest_prio.curr != highest_prio)
676                 cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr);
677
678         update_rt_migration(rq);
679 #endif /* CONFIG_SMP */
680 #ifdef CONFIG_RT_GROUP_SCHED
681         if (rt_se_boosted(rt_se))
682                 rt_rq->rt_nr_boosted--;
683
684         WARN_ON(!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted);
685 #endif
686 }
687
688 static void __enqueue_rt_entity(struct sched_rt_entity *rt_se)
689 {
690         struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
691         struct rt_prio_array *array = &rt_rq->active;
692         struct rt_rq *group_rq = group_rt_rq(rt_se);
693         struct list_head *queue = array->queue + rt_se_prio(rt_se);
694
695         /*
696          * Don't enqueue the group if its throttled, or when empty.
697          * The latter is a consequence of the former when a child group
698          * get throttled and the current group doesn't have any other
699          * active members.
700          */
701         if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running))
702                 return;
703
704         list_add_tail(&rt_se->run_list, queue);
705         __set_bit(rt_se_prio(rt_se), array->bitmap);
706
707         inc_rt_tasks(rt_se, rt_rq);
708 }
709
710 static void __dequeue_rt_entity(struct sched_rt_entity *rt_se)
711 {
712         struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
713         struct rt_prio_array *array = &rt_rq->active;
714
715         list_del_init(&rt_se->run_list);
716         if (list_empty(array->queue + rt_se_prio(rt_se)))
717                 __clear_bit(rt_se_prio(rt_se), array->bitmap);
718
719         dec_rt_tasks(rt_se, rt_rq);
720 }
721
722 /*
723  * Because the prio of an upper entry depends on the lower
724  * entries, we must remove entries top - down.
725  */
726 static void dequeue_rt_stack(struct sched_rt_entity *rt_se)
727 {
728         struct sched_rt_entity *back = NULL;
729
730         for_each_sched_rt_entity(rt_se) {
731                 rt_se->back = back;
732                 back = rt_se;
733         }
734
735         for (rt_se = back; rt_se; rt_se = rt_se->back) {
736                 if (on_rt_rq(rt_se))
737                         __dequeue_rt_entity(rt_se);
738         }
739 }
740
741 static void enqueue_rt_entity(struct sched_rt_entity *rt_se)
742 {
743         dequeue_rt_stack(rt_se);
744         for_each_sched_rt_entity(rt_se)
745                 __enqueue_rt_entity(rt_se);
746 }
747
748 static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
749 {
750         dequeue_rt_stack(rt_se);
751
752         for_each_sched_rt_entity(rt_se) {
753                 struct rt_rq *rt_rq = group_rt_rq(rt_se);
754
755                 if (rt_rq && rt_rq->rt_nr_running)
756                         __enqueue_rt_entity(rt_se);
757         }
758 }
759
760 /*
761  * Adding/removing a task to/from a priority array:
762  */
763 static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup)
764 {
765         struct sched_rt_entity *rt_se = &p->rt;
766
767         if (wakeup)
768                 rt_se->timeout = 0;
769
770         enqueue_rt_entity(rt_se);
771
772         if (!task_current(rq, p) && p->rt.nr_cpus_allowed > 1)
773                 enqueue_pushable_task(rq, p);
774
775         inc_cpu_load(rq, p->se.load.weight);
776 }
777
778 static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep)
779 {
780         struct sched_rt_entity *rt_se = &p->rt;
781
782         update_curr_rt(rq);
783         dequeue_rt_entity(rt_se);
784
785         dequeue_pushable_task(rq, p);
786
787         dec_cpu_load(rq, p->se.load.weight);
788 }
789
790 /*
791  * Put task to the end of the run list without the overhead of dequeue
792  * followed by enqueue.
793  */
794 static void
795 requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se, int head)
796 {
797         if (on_rt_rq(rt_se)) {
798                 struct rt_prio_array *array = &rt_rq->active;
799                 struct list_head *queue = array->queue + rt_se_prio(rt_se);
800
801                 if (head)
802                         list_move(&rt_se->run_list, queue);
803                 else
804                         list_move_tail(&rt_se->run_list, queue);
805         }
806 }
807
808 static void requeue_task_rt(struct rq *rq, struct task_struct *p, int head)
809 {
810         struct sched_rt_entity *rt_se = &p->rt;
811         struct rt_rq *rt_rq;
812
813         for_each_sched_rt_entity(rt_se) {
814                 rt_rq = rt_rq_of_se(rt_se);
815                 requeue_rt_entity(rt_rq, rt_se, head);
816         }
817 }
818
819 static void yield_task_rt(struct rq *rq)
820 {
821         requeue_task_rt(rq, rq->curr, 0);
822 }
823
824 #ifdef CONFIG_SMP
825 static int find_lowest_rq(struct task_struct *task);
826
827 static int select_task_rq_rt(struct task_struct *p, int sync)
828 {
829         struct rq *rq = task_rq(p);
830
831         /*
832          * If the current task is an RT task, then
833          * try to see if we can wake this RT task up on another
834          * runqueue. Otherwise simply start this RT task
835          * on its current runqueue.
836          *
837          * We want to avoid overloading runqueues. Even if
838          * the RT task is of higher priority than the current RT task.
839          * RT tasks behave differently than other tasks. If
840          * one gets preempted, we try to push it off to another queue.
841          * So trying to keep a preempting RT task on the same
842          * cache hot CPU will force the running RT task to
843          * a cold CPU. So we waste all the cache for the lower
844          * RT task in hopes of saving some of a RT task
845          * that is just being woken and probably will have
846          * cold cache anyway.
847          */
848         if (unlikely(rt_task(rq->curr)) &&
849             (p->rt.nr_cpus_allowed > 1)) {
850                 int cpu = find_lowest_rq(p);
851
852                 return (cpu == -1) ? task_cpu(p) : cpu;
853         }
854
855         /*
856          * Otherwise, just let it ride on the affined RQ and the
857          * post-schedule router will push the preempted task away
858          */
859         return task_cpu(p);
860 }
861
862 static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
863 {
864         cpumask_var_t mask;
865
866         if (rq->curr->rt.nr_cpus_allowed == 1)
867                 return;
868
869         if (!alloc_cpumask_var(&mask, GFP_ATOMIC))
870                 return;
871
872         if (p->rt.nr_cpus_allowed != 1
873             && cpupri_find(&rq->rd->cpupri, p, mask))
874                 goto free;
875
876         if (!cpupri_find(&rq->rd->cpupri, rq->curr, mask))
877                 goto free;
878
879         /*
880          * There appears to be other cpus that can accept
881          * current and none to run 'p', so lets reschedule
882          * to try and push current away:
883          */
884         requeue_task_rt(rq, p, 1);
885         resched_task(rq->curr);
886 free:
887         free_cpumask_var(mask);
888 }
889
890 #endif /* CONFIG_SMP */
891
892 /*
893  * Preempt the current task with a newly woken task if needed:
894  */
895 static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int sync)
896 {
897         if (p->prio < rq->curr->prio) {
898                 resched_task(rq->curr);
899                 return;
900         }
901
902 #ifdef CONFIG_SMP
903         /*
904          * If:
905          *
906          * - the newly woken task is of equal priority to the current task
907          * - the newly woken task is non-migratable while current is migratable
908          * - current will be preempted on the next reschedule
909          *
910          * we should check to see if current can readily move to a different
911          * cpu.  If so, we will reschedule to allow the push logic to try
912          * to move current somewhere else, making room for our non-migratable
913          * task.
914          */
915         if (p->prio == rq->curr->prio && !need_resched())
916                 check_preempt_equal_prio(rq, p);
917 #endif
918 }
919
920 static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
921                                                    struct rt_rq *rt_rq)
922 {
923         struct rt_prio_array *array = &rt_rq->active;
924         struct sched_rt_entity *next = NULL;
925         struct list_head *queue;
926         int idx;
927
928         idx = sched_find_first_bit(array->bitmap);
929         BUG_ON(idx >= MAX_RT_PRIO);
930
931         queue = array->queue + idx;
932         next = list_entry(queue->next, struct sched_rt_entity, run_list);
933
934         return next;
935 }
936
937 static struct task_struct *_pick_next_task_rt(struct rq *rq)
938 {
939         struct sched_rt_entity *rt_se;
940         struct task_struct *p;
941         struct rt_rq *rt_rq;
942
943         rt_rq = &rq->rt;
944
945         if (unlikely(!rt_rq->rt_nr_running))
946                 return NULL;
947
948         if (rt_rq_throttled(rt_rq))
949                 return NULL;
950
951         do {
952                 rt_se = pick_next_rt_entity(rq, rt_rq);
953                 BUG_ON(!rt_se);
954                 rt_rq = group_rt_rq(rt_se);
955         } while (rt_rq);
956
957         p = rt_task_of(rt_se);
958         p->se.exec_start = rq->clock;
959
960         return p;
961 }
962
963 static struct task_struct *pick_next_task_rt(struct rq *rq)
964 {
965         struct task_struct *p = _pick_next_task_rt(rq);
966
967         /* The running task is never eligible for pushing */
968         if (p)
969                 dequeue_pushable_task(rq, p);
970
971         return p;
972 }
973
974 static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
975 {
976         update_curr_rt(rq);
977         p->se.exec_start = 0;
978
979         /*
980          * The previous task needs to be made eligible for pushing
981          * if it is still active
982          */
983         if (p->se.on_rq && p->rt.nr_cpus_allowed > 1)
984                 enqueue_pushable_task(rq, p);
985 }
986
987 #ifdef CONFIG_SMP
988
989 /* Only try algorithms three times */
990 #define RT_MAX_TRIES 3
991
992 static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep);
993
994 static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
995 {
996         if (!task_running(rq, p) &&
997             (cpu < 0 || cpumask_test_cpu(cpu, &p->cpus_allowed)) &&
998             (p->rt.nr_cpus_allowed > 1))
999                 return 1;
1000         return 0;
1001 }
1002
1003 /* Return the second highest RT task, NULL otherwise */
1004 static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu)
1005 {
1006         struct task_struct *next = NULL;
1007         struct sched_rt_entity *rt_se;
1008         struct rt_prio_array *array;
1009         struct rt_rq *rt_rq;
1010         int idx;
1011
1012         for_each_leaf_rt_rq(rt_rq, rq) {
1013                 array = &rt_rq->active;
1014                 idx = sched_find_first_bit(array->bitmap);
1015  next_idx:
1016                 if (idx >= MAX_RT_PRIO)
1017                         continue;
1018                 if (next && next->prio < idx)
1019                         continue;
1020                 list_for_each_entry(rt_se, array->queue + idx, run_list) {
1021                         struct task_struct *p = rt_task_of(rt_se);
1022                         if (pick_rt_task(rq, p, cpu)) {
1023                                 next = p;
1024                                 break;
1025                         }
1026                 }
1027                 if (!next) {
1028                         idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
1029                         goto next_idx;
1030                 }
1031         }
1032
1033         return next;
1034 }
1035
1036 static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);
1037
1038 static inline int pick_optimal_cpu(int this_cpu, cpumask_t *mask)
1039 {
1040         int first;
1041
1042         /* "this_cpu" is cheaper to preempt than a remote processor */
1043         if ((this_cpu != -1) && cpu_isset(this_cpu, *mask))
1044                 return this_cpu;
1045
1046         first = first_cpu(*mask);
1047         if (first != NR_CPUS)
1048                 return first;
1049
1050         return -1;
1051 }
1052
1053 static int find_lowest_rq(struct task_struct *task)
1054 {
1055         struct sched_domain *sd;
1056         struct cpumask *lowest_mask = __get_cpu_var(local_cpu_mask);
1057         int this_cpu = smp_processor_id();
1058         int cpu      = task_cpu(task);
1059
1060         if (task->rt.nr_cpus_allowed == 1)
1061                 return -1; /* No other targets possible */
1062
1063         if (!cpupri_find(&task_rq(task)->rd->cpupri, task, lowest_mask))
1064                 return -1; /* No targets found */
1065
1066         /*
1067          * Only consider CPUs that are usable for migration.
1068          * I guess we might want to change cpupri_find() to ignore those
1069          * in the first place.
1070          */
1071         cpumask_and(lowest_mask, lowest_mask, cpu_active_mask);
1072
1073         /*
1074          * At this point we have built a mask of cpus representing the
1075          * lowest priority tasks in the system.  Now we want to elect
1076          * the best one based on our affinity and topology.
1077          *
1078          * We prioritize the last cpu that the task executed on since
1079          * it is most likely cache-hot in that location.
1080          */
1081         if (cpumask_test_cpu(cpu, lowest_mask))
1082                 return cpu;
1083
1084         /*
1085          * Otherwise, we consult the sched_domains span maps to figure
1086          * out which cpu is logically closest to our hot cache data.
1087          */
1088         if (this_cpu == cpu)
1089                 this_cpu = -1; /* Skip this_cpu opt if the same */
1090
1091         for_each_domain(cpu, sd) {
1092                 if (sd->flags & SD_WAKE_AFFINE) {
1093                         cpumask_t domain_mask;
1094                         int       best_cpu;
1095
1096                         cpumask_and(&domain_mask, sched_domain_span(sd),
1097                                     lowest_mask);
1098
1099                         best_cpu = pick_optimal_cpu(this_cpu,
1100                                                     &domain_mask);
1101                         if (best_cpu != -1)
1102                                 return best_cpu;
1103                 }
1104         }
1105
1106         /*
1107          * And finally, if there were no matches within the domains
1108          * just give the caller *something* to work with from the compatible
1109          * locations.
1110          */
1111         return pick_optimal_cpu(this_cpu, lowest_mask);
1112 }
1113
1114 /* Will lock the rq it finds */
1115 static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
1116 {
1117         struct rq *lowest_rq = NULL;
1118         int tries;
1119         int cpu;
1120
1121         for (tries = 0; tries < RT_MAX_TRIES; tries++) {
1122                 cpu = find_lowest_rq(task);
1123
1124                 if ((cpu == -1) || (cpu == rq->cpu))
1125                         break;
1126
1127                 lowest_rq = cpu_rq(cpu);
1128
1129                 /* if the prio of this runqueue changed, try again */
1130                 if (double_lock_balance(rq, lowest_rq)) {
1131                         /*
1132                          * We had to unlock the run queue. In
1133                          * the mean time, task could have
1134                          * migrated already or had its affinity changed.
1135                          * Also make sure that it wasn't scheduled on its rq.
1136                          */
1137                         if (unlikely(task_rq(task) != rq ||
1138                                      !cpumask_test_cpu(lowest_rq->cpu,
1139                                                        &task->cpus_allowed) ||
1140                                      task_running(rq, task) ||
1141                                      !task->se.on_rq)) {
1142
1143                                 spin_unlock(&lowest_rq->lock);
1144                                 lowest_rq = NULL;
1145                                 break;
1146                         }
1147                 }
1148
1149                 /* If this rq is still suitable use it. */
1150                 if (lowest_rq->rt.highest_prio.curr > task->prio)
1151                         break;
1152
1153                 /* try again */
1154                 double_unlock_balance(rq, lowest_rq);
1155                 lowest_rq = NULL;
1156         }
1157
1158         return lowest_rq;
1159 }
1160
1161 static inline int has_pushable_tasks(struct rq *rq)
1162 {
1163         return !plist_head_empty(&rq->rt.pushable_tasks);
1164 }
1165
1166 static struct task_struct *pick_next_pushable_task(struct rq *rq)
1167 {
1168         struct task_struct *p;
1169
1170         if (!has_pushable_tasks(rq))
1171                 return NULL;
1172
1173         p = plist_first_entry(&rq->rt.pushable_tasks,
1174                               struct task_struct, pushable_tasks);
1175
1176         BUG_ON(rq->cpu != task_cpu(p));
1177         BUG_ON(task_current(rq, p));
1178         BUG_ON(p->rt.nr_cpus_allowed <= 1);
1179
1180         BUG_ON(!p->se.on_rq);
1181         BUG_ON(!rt_task(p));
1182
1183         return p;
1184 }
1185
1186 /*
1187  * If the current CPU has more than one RT task, see if the non
1188  * running task can migrate over to a CPU that is running a task
1189  * of lesser priority.
1190  */
1191 static int push_rt_task(struct rq *rq)
1192 {
1193         struct task_struct *next_task;
1194         struct rq *lowest_rq;
1195
1196         if (!rq->rt.overloaded)
1197                 return 0;
1198
1199         next_task = pick_next_pushable_task(rq);
1200         if (!next_task)
1201                 return 0;
1202
1203  retry:
1204         if (unlikely(next_task == rq->curr)) {
1205                 WARN_ON(1);
1206                 return 0;
1207         }
1208
1209         /*
1210          * It's possible that the next_task slipped in of
1211          * higher priority than current. If that's the case
1212          * just reschedule current.
1213          */
1214         if (unlikely(next_task->prio < rq->curr->prio)) {
1215                 resched_task(rq->curr);
1216                 return 0;
1217         }
1218
1219         /* We might release rq lock */
1220         get_task_struct(next_task);
1221
1222         /* find_lock_lowest_rq locks the rq if found */
1223         lowest_rq = find_lock_lowest_rq(next_task, rq);
1224         if (!lowest_rq) {
1225                 struct task_struct *task;
1226                 /*
1227                  * find lock_lowest_rq releases rq->lock
1228                  * so it is possible that next_task has migrated.
1229                  *
1230                  * We need to make sure that the task is still on the same
1231                  * run-queue and is also still the next task eligible for
1232                  * pushing.
1233                  */
1234                 task = pick_next_pushable_task(rq);
1235                 if (task_cpu(next_task) == rq->cpu && task == next_task) {
1236                         /*
1237                          * If we get here, the task hasnt moved at all, but
1238                          * it has failed to push.  We will not try again,
1239                          * since the other cpus will pull from us when they
1240                          * are ready.
1241                          */
1242                         dequeue_pushable_task(rq, next_task);
1243                         goto out;
1244                 }
1245
1246                 if (!task)
1247                         /* No more tasks, just exit */
1248                         goto out;
1249
1250                 /*
1251                  * Something has shifted, try again.
1252                  */
1253                 put_task_struct(next_task);
1254                 next_task = task;
1255                 goto retry;
1256         }
1257
1258         deactivate_task(rq, next_task, 0);
1259         set_task_cpu(next_task, lowest_rq->cpu);
1260         activate_task(lowest_rq, next_task, 0);
1261
1262         resched_task(lowest_rq->curr);
1263
1264         double_unlock_balance(rq, lowest_rq);
1265
1266 out:
1267         put_task_struct(next_task);
1268
1269         return 1;
1270 }
1271
1272 static void push_rt_tasks(struct rq *rq)
1273 {
1274         /* push_rt_task will return true if it moved an RT */
1275         while (push_rt_task(rq))
1276                 ;
1277 }
1278
1279 static int pull_rt_task(struct rq *this_rq)
1280 {
1281         int this_cpu = this_rq->cpu, ret = 0, cpu;
1282         struct task_struct *p;
1283         struct rq *src_rq;
1284
1285         if (likely(!rt_overloaded(this_rq)))
1286                 return 0;
1287
1288         for_each_cpu(cpu, this_rq->rd->rto_mask) {
1289                 if (this_cpu == cpu)
1290                         continue;
1291
1292                 src_rq = cpu_rq(cpu);
1293
1294                 /*
1295                  * Don't bother taking the src_rq->lock if the next highest
1296                  * task is known to be lower-priority than our current task.
1297                  * This may look racy, but if this value is about to go
1298                  * logically higher, the src_rq will push this task away.
1299                  * And if its going logically lower, we do not care
1300                  */
1301                 if (src_rq->rt.highest_prio.next >=
1302                     this_rq->rt.highest_prio.curr)
1303                         continue;
1304
1305                 /*
1306                  * We can potentially drop this_rq's lock in
1307                  * double_lock_balance, and another CPU could
1308                  * alter this_rq
1309                  */
1310                 double_lock_balance(this_rq, src_rq);
1311
1312                 /*
1313                  * Are there still pullable RT tasks?
1314                  */
1315                 if (src_rq->rt.rt_nr_running <= 1)
1316                         goto skip;
1317
1318                 p = pick_next_highest_task_rt(src_rq, this_cpu);
1319
1320                 /*
1321                  * Do we have an RT task that preempts
1322                  * the to-be-scheduled task?
1323                  */
1324                 if (p && (p->prio < this_rq->rt.highest_prio.curr)) {
1325                         WARN_ON(p == src_rq->curr);
1326                         WARN_ON(!p->se.on_rq);
1327
1328                         /*
1329                          * There's a chance that p is higher in priority
1330                          * than what's currently running on its cpu.
1331                          * This is just that p is wakeing up and hasn't
1332                          * had a chance to schedule. We only pull
1333                          * p if it is lower in priority than the
1334                          * current task on the run queue
1335                          */
1336                         if (p->prio < src_rq->curr->prio)
1337                                 goto skip;
1338
1339                         ret = 1;
1340
1341                         deactivate_task(src_rq, p, 0);
1342                         set_task_cpu(p, this_cpu);
1343                         activate_task(this_rq, p, 0);
1344                         /*
1345                          * We continue with the search, just in
1346                          * case there's an even higher prio task
1347                          * in another runqueue. (low likelyhood
1348                          * but possible)
1349                          */
1350                 }
1351  skip:
1352                 double_unlock_balance(this_rq, src_rq);
1353         }
1354
1355         return ret;
1356 }
1357
1358 static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
1359 {
1360         /* Try to pull RT tasks here if we lower this rq's prio */
1361         if (unlikely(rt_task(prev)) && rq->rt.highest_prio.curr > prev->prio)
1362                 pull_rt_task(rq);
1363 }
1364
1365 /*
1366  * assumes rq->lock is held
1367  */
1368 static int needs_post_schedule_rt(struct rq *rq)
1369 {
1370         return has_pushable_tasks(rq);
1371 }
1372
1373 static void post_schedule_rt(struct rq *rq)
1374 {
1375         /*
1376          * This is only called if needs_post_schedule_rt() indicates that
1377          * we need to push tasks away
1378          */
1379         spin_lock_irq(&rq->lock);
1380         push_rt_tasks(rq);
1381         spin_unlock_irq(&rq->lock);
1382 }
1383
1384 /*
1385  * If we are not running and we are not going to reschedule soon, we should
1386  * try to push tasks away now
1387  */
1388 static void task_wake_up_rt(struct rq *rq, struct task_struct *p)
1389 {
1390         if (!task_running(rq, p) &&
1391             !test_tsk_need_resched(rq->curr) &&
1392             has_pushable_tasks(rq) &&
1393             p->rt.nr_cpus_allowed > 1)
1394                 push_rt_tasks(rq);
1395 }
1396
1397 static unsigned long
1398 load_balance_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
1399                 unsigned long max_load_move,
1400                 struct sched_domain *sd, enum cpu_idle_type idle,
1401                 int *all_pinned, int *this_best_prio)
1402 {
1403         /* don't touch RT tasks */
1404         return 0;
1405 }
1406
1407 static int
1408 move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest,
1409                  struct sched_domain *sd, enum cpu_idle_type idle)
1410 {
1411         /* don't touch RT tasks */
1412         return 0;
1413 }
1414
1415 static void set_cpus_allowed_rt(struct task_struct *p,
1416                                 const struct cpumask *new_mask)
1417 {
1418         int weight = cpumask_weight(new_mask);
1419
1420         BUG_ON(!rt_task(p));
1421
1422         /*
1423          * Update the migration status of the RQ if we have an RT task
1424          * which is running AND changing its weight value.
1425          */
1426         if (p->se.on_rq && (weight != p->rt.nr_cpus_allowed)) {
1427                 struct rq *rq = task_rq(p);
1428
1429                 if (!task_current(rq, p)) {
1430                         /*
1431                          * Make sure we dequeue this task from the pushable list
1432                          * before going further.  It will either remain off of
1433                          * the list because we are no longer pushable, or it
1434                          * will be requeued.
1435                          */
1436                         if (p->rt.nr_cpus_allowed > 1)
1437                                 dequeue_pushable_task(rq, p);
1438
1439                         /*
1440                          * Requeue if our weight is changing and still > 1
1441                          */
1442                         if (weight > 1)
1443                                 enqueue_pushable_task(rq, p);
1444
1445                 }
1446
1447                 if ((p->rt.nr_cpus_allowed <= 1) && (weight > 1)) {
1448                         rq->rt.rt_nr_migratory++;
1449                 } else if ((p->rt.nr_cpus_allowed > 1) && (weight <= 1)) {
1450                         BUG_ON(!rq->rt.rt_nr_migratory);
1451                         rq->rt.rt_nr_migratory--;
1452                 }
1453
1454                 update_rt_migration(rq);
1455         }
1456
1457         cpumask_copy(&p->cpus_allowed, new_mask);
1458         p->rt.nr_cpus_allowed = weight;
1459 }
1460
1461 /* Assumes rq->lock is held */
1462 static void rq_online_rt(struct rq *rq)
1463 {
1464         if (rq->rt.overloaded)
1465                 rt_set_overload(rq);
1466
1467         __enable_runtime(rq);
1468
1469         cpupri_set(&rq->rd->cpupri, rq->cpu, rq->rt.highest_prio.curr);
1470 }
1471
1472 /* Assumes rq->lock is held */
1473 static void rq_offline_rt(struct rq *rq)
1474 {
1475         if (rq->rt.overloaded)
1476                 rt_clear_overload(rq);
1477
1478         __disable_runtime(rq);
1479
1480         cpupri_set(&rq->rd->cpupri, rq->cpu, CPUPRI_INVALID);
1481 }
1482
1483 /*
1484  * When switch from the rt queue, we bring ourselves to a position
1485  * that we might want to pull RT tasks from other runqueues.
1486  */
1487 static void switched_from_rt(struct rq *rq, struct task_struct *p,
1488                            int running)
1489 {
1490         /*
1491          * If there are other RT tasks then we will reschedule
1492          * and the scheduling of the other RT tasks will handle
1493          * the balancing. But if we are the last RT task
1494          * we may need to handle the pulling of RT tasks
1495          * now.
1496          */
1497         if (!rq->rt.rt_nr_running)
1498                 pull_rt_task(rq);
1499 }
1500
1501 static inline void init_sched_rt_class(void)
1502 {
1503         unsigned int i;
1504
1505         for_each_possible_cpu(i)
1506                 alloc_cpumask_var(&per_cpu(local_cpu_mask, i), GFP_KERNEL);
1507 }
1508 #endif /* CONFIG_SMP */
1509
1510 /*
1511  * When switching a task to RT, we may overload the runqueue
1512  * with RT tasks. In this case we try to push them off to
1513  * other runqueues.
1514  */
1515 static void switched_to_rt(struct rq *rq, struct task_struct *p,
1516                            int running)
1517 {
1518         int check_resched = 1;
1519
1520         /*
1521          * If we are already running, then there's nothing
1522          * that needs to be done. But if we are not running
1523          * we may need to preempt the current running task.
1524          * If that current running task is also an RT task
1525          * then see if we can move to another run queue.
1526          */
1527         if (!running) {
1528 #ifdef CONFIG_SMP
1529                 if (rq->rt.overloaded && push_rt_task(rq) &&
1530                     /* Don't resched if we changed runqueues */
1531                     rq != task_rq(p))
1532                         check_resched = 0;
1533 #endif /* CONFIG_SMP */
1534                 if (check_resched && p->prio < rq->curr->prio)
1535                         resched_task(rq->curr);
1536         }
1537 }
1538
1539 /*
1540  * Priority of the task has changed. This may cause
1541  * us to initiate a push or pull.
1542  */
1543 static void prio_changed_rt(struct rq *rq, struct task_struct *p,
1544                             int oldprio, int running)
1545 {
1546         if (running) {
1547 #ifdef CONFIG_SMP
1548                 /*
1549                  * If our priority decreases while running, we
1550                  * may need to pull tasks to this runqueue.
1551                  */
1552                 if (oldprio < p->prio)
1553                         pull_rt_task(rq);
1554                 /*
1555                  * If there's a higher priority task waiting to run
1556                  * then reschedule. Note, the above pull_rt_task
1557                  * can release the rq lock and p could migrate.
1558                  * Only reschedule if p is still on the same runqueue.
1559                  */
1560                 if (p->prio > rq->rt.highest_prio.curr && rq->curr == p)
1561                         resched_task(p);
1562 #else
1563                 /* For UP simply resched on drop of prio */
1564                 if (oldprio < p->prio)
1565                         resched_task(p);
1566 #endif /* CONFIG_SMP */
1567         } else {
1568                 /*
1569                  * This task is not running, but if it is
1570                  * greater than the current running task
1571                  * then reschedule.
1572                  */
1573                 if (p->prio < rq->curr->prio)
1574                         resched_task(rq->curr);
1575         }
1576 }
1577
1578 static void watchdog(struct rq *rq, struct task_struct *p)
1579 {
1580         unsigned long soft, hard;
1581
1582         if (!p->signal)
1583                 return;
1584
1585         soft = p->signal->rlim[RLIMIT_RTTIME].rlim_cur;
1586         hard = p->signal->rlim[RLIMIT_RTTIME].rlim_max;
1587
1588         if (soft != RLIM_INFINITY) {
1589                 unsigned long next;
1590
1591                 p->rt.timeout++;
1592                 next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ);
1593                 if (p->rt.timeout > next)
1594                         p->cputime_expires.sched_exp = p->se.sum_exec_runtime;
1595         }
1596 }
1597
1598 static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
1599 {
1600         update_curr_rt(rq);
1601
1602         watchdog(rq, p);
1603
1604         /*
1605          * RR tasks need a special form of timeslice management.
1606          * FIFO tasks have no timeslices.
1607          */
1608         if (p->policy != SCHED_RR)
1609                 return;
1610
1611         if (--p->rt.time_slice)
1612                 return;
1613
1614         p->rt.time_slice = DEF_TIMESLICE;
1615
1616         /*
1617          * Requeue to the end of queue if we are not the only element
1618          * on the queue:
1619          */
1620         if (p->rt.run_list.prev != p->rt.run_list.next) {
1621                 requeue_task_rt(rq, p, 0);
1622                 set_tsk_need_resched(p);
1623         }
1624 }
1625
1626 static void set_curr_task_rt(struct rq *rq)
1627 {
1628         struct task_struct *p = rq->curr;
1629
1630         p->se.exec_start = rq->clock;
1631
1632         /* The running task is never eligible for pushing */
1633         dequeue_pushable_task(rq, p);
1634 }
1635
1636 static const struct sched_class rt_sched_class = {
1637         .next                   = &fair_sched_class,
1638         .enqueue_task           = enqueue_task_rt,
1639         .dequeue_task           = dequeue_task_rt,
1640         .yield_task             = yield_task_rt,
1641
1642         .check_preempt_curr     = check_preempt_curr_rt,
1643
1644         .pick_next_task         = pick_next_task_rt,
1645         .put_prev_task          = put_prev_task_rt,
1646
1647 #ifdef CONFIG_SMP
1648         .select_task_rq         = select_task_rq_rt,
1649
1650         .load_balance           = load_balance_rt,
1651         .move_one_task          = move_one_task_rt,
1652         .set_cpus_allowed       = set_cpus_allowed_rt,
1653         .rq_online              = rq_online_rt,
1654         .rq_offline             = rq_offline_rt,
1655         .pre_schedule           = pre_schedule_rt,
1656         .needs_post_schedule    = needs_post_schedule_rt,
1657         .post_schedule          = post_schedule_rt,
1658         .task_wake_up           = task_wake_up_rt,
1659         .switched_from          = switched_from_rt,
1660 #endif
1661
1662         .set_curr_task          = set_curr_task_rt,
1663         .task_tick              = task_tick_rt,
1664
1665         .prio_changed           = prio_changed_rt,
1666         .switched_to            = switched_to_rt,
1667 };
1668
1669 #ifdef CONFIG_SCHED_DEBUG
1670 extern void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq);
1671
1672 static void print_rt_stats(struct seq_file *m, int cpu)
1673 {
1674         struct rt_rq *rt_rq;
1675
1676         rcu_read_lock();
1677         for_each_leaf_rt_rq(rt_rq, cpu_rq(cpu))
1678                 print_rt_rq(m, cpu, rt_rq);
1679         rcu_read_unlock();
1680 }
1681 #endif /* CONFIG_SCHED_DEBUG */
1682