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