sched/rt: fix SCHED_RR across cgroups
[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 #include "sched.h"
7
8 #include <linux/slab.h>
9
10 static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun);
11
12 struct rt_bandwidth def_rt_bandwidth;
13
14 static enum hrtimer_restart sched_rt_period_timer(struct hrtimer *timer)
15 {
16         struct rt_bandwidth *rt_b =
17                 container_of(timer, struct rt_bandwidth, rt_period_timer);
18         ktime_t now;
19         int overrun;
20         int idle = 0;
21
22         for (;;) {
23                 now = hrtimer_cb_get_time(timer);
24                 overrun = hrtimer_forward(timer, now, rt_b->rt_period);
25
26                 if (!overrun)
27                         break;
28
29                 idle = do_sched_rt_period_timer(rt_b, overrun);
30         }
31
32         return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
33 }
34
35 void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime)
36 {
37         rt_b->rt_period = ns_to_ktime(period);
38         rt_b->rt_runtime = runtime;
39
40         raw_spin_lock_init(&rt_b->rt_runtime_lock);
41
42         hrtimer_init(&rt_b->rt_period_timer,
43                         CLOCK_MONOTONIC, HRTIMER_MODE_REL);
44         rt_b->rt_period_timer.function = sched_rt_period_timer;
45 }
46
47 static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
48 {
49         if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
50                 return;
51
52         if (hrtimer_active(&rt_b->rt_period_timer))
53                 return;
54
55         raw_spin_lock(&rt_b->rt_runtime_lock);
56         start_bandwidth_timer(&rt_b->rt_period_timer, rt_b->rt_period);
57         raw_spin_unlock(&rt_b->rt_runtime_lock);
58 }
59
60 void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
61 {
62         struct rt_prio_array *array;
63         int i;
64
65         array = &rt_rq->active;
66         for (i = 0; i < MAX_RT_PRIO; i++) {
67                 INIT_LIST_HEAD(array->queue + i);
68                 __clear_bit(i, array->bitmap);
69         }
70         /* delimiter for bitsearch: */
71         __set_bit(MAX_RT_PRIO, array->bitmap);
72
73 #if defined CONFIG_SMP
74         rt_rq->highest_prio.curr = MAX_RT_PRIO;
75         rt_rq->highest_prio.next = MAX_RT_PRIO;
76         rt_rq->rt_nr_migratory = 0;
77         rt_rq->overloaded = 0;
78         plist_head_init(&rt_rq->pushable_tasks);
79 #endif
80
81         rt_rq->rt_time = 0;
82         rt_rq->rt_throttled = 0;
83         rt_rq->rt_runtime = 0;
84         raw_spin_lock_init(&rt_rq->rt_runtime_lock);
85 }
86
87 #ifdef CONFIG_RT_GROUP_SCHED
88 static void destroy_rt_bandwidth(struct rt_bandwidth *rt_b)
89 {
90         hrtimer_cancel(&rt_b->rt_period_timer);
91 }
92
93 #define rt_entity_is_task(rt_se) (!(rt_se)->my_q)
94
95 static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
96 {
97 #ifdef CONFIG_SCHED_DEBUG
98         WARN_ON_ONCE(!rt_entity_is_task(rt_se));
99 #endif
100         return container_of(rt_se, struct task_struct, rt);
101 }
102
103 static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
104 {
105         return rt_rq->rq;
106 }
107
108 static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
109 {
110         return rt_se->rt_rq;
111 }
112
113 void free_rt_sched_group(struct task_group *tg)
114 {
115         int i;
116
117         if (tg->rt_se)
118                 destroy_rt_bandwidth(&tg->rt_bandwidth);
119
120         for_each_possible_cpu(i) {
121                 if (tg->rt_rq)
122                         kfree(tg->rt_rq[i]);
123                 if (tg->rt_se)
124                         kfree(tg->rt_se[i]);
125         }
126
127         kfree(tg->rt_rq);
128         kfree(tg->rt_se);
129 }
130
131 void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
132                 struct sched_rt_entity *rt_se, int cpu,
133                 struct sched_rt_entity *parent)
134 {
135         struct rq *rq = cpu_rq(cpu);
136
137         rt_rq->highest_prio.curr = MAX_RT_PRIO;
138         rt_rq->rt_nr_boosted = 0;
139         rt_rq->rq = rq;
140         rt_rq->tg = tg;
141
142         tg->rt_rq[cpu] = rt_rq;
143         tg->rt_se[cpu] = rt_se;
144
145         if (!rt_se)
146                 return;
147
148         if (!parent)
149                 rt_se->rt_rq = &rq->rt;
150         else
151                 rt_se->rt_rq = parent->my_q;
152
153         rt_se->my_q = rt_rq;
154         rt_se->parent = parent;
155         INIT_LIST_HEAD(&rt_se->run_list);
156 }
157
158 int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
159 {
160         struct rt_rq *rt_rq;
161         struct sched_rt_entity *rt_se;
162         int i;
163
164         tg->rt_rq = kzalloc(sizeof(rt_rq) * nr_cpu_ids, GFP_KERNEL);
165         if (!tg->rt_rq)
166                 goto err;
167         tg->rt_se = kzalloc(sizeof(rt_se) * nr_cpu_ids, GFP_KERNEL);
168         if (!tg->rt_se)
169                 goto err;
170
171         init_rt_bandwidth(&tg->rt_bandwidth,
172                         ktime_to_ns(def_rt_bandwidth.rt_period), 0);
173
174         for_each_possible_cpu(i) {
175                 rt_rq = kzalloc_node(sizeof(struct rt_rq),
176                                      GFP_KERNEL, cpu_to_node(i));
177                 if (!rt_rq)
178                         goto err;
179
180                 rt_se = kzalloc_node(sizeof(struct sched_rt_entity),
181                                      GFP_KERNEL, cpu_to_node(i));
182                 if (!rt_se)
183                         goto err_free_rq;
184
185                 init_rt_rq(rt_rq, cpu_rq(i));
186                 rt_rq->rt_runtime = tg->rt_bandwidth.rt_runtime;
187                 init_tg_rt_entry(tg, rt_rq, rt_se, i, parent->rt_se[i]);
188         }
189
190         return 1;
191
192 err_free_rq:
193         kfree(rt_rq);
194 err:
195         return 0;
196 }
197
198 #else /* CONFIG_RT_GROUP_SCHED */
199
200 #define rt_entity_is_task(rt_se) (1)
201
202 static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
203 {
204         return container_of(rt_se, struct task_struct, rt);
205 }
206
207 static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
208 {
209         return container_of(rt_rq, struct rq, rt);
210 }
211
212 static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
213 {
214         struct task_struct *p = rt_task_of(rt_se);
215         struct rq *rq = task_rq(p);
216
217         return &rq->rt;
218 }
219
220 void free_rt_sched_group(struct task_group *tg) { }
221
222 int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
223 {
224         return 1;
225 }
226 #endif /* CONFIG_RT_GROUP_SCHED */
227
228 #ifdef CONFIG_SMP
229
230 static inline int rt_overloaded(struct rq *rq)
231 {
232         return atomic_read(&rq->rd->rto_count);
233 }
234
235 static inline void rt_set_overload(struct rq *rq)
236 {
237         if (!rq->online)
238                 return;
239
240         cpumask_set_cpu(rq->cpu, rq->rd->rto_mask);
241         /*
242          * Make sure the mask is visible before we set
243          * the overload count. That is checked to determine
244          * if we should look at the mask. It would be a shame
245          * if we looked at the mask, but the mask was not
246          * updated yet.
247          */
248         wmb();
249         atomic_inc(&rq->rd->rto_count);
250 }
251
252 static inline void rt_clear_overload(struct rq *rq)
253 {
254         if (!rq->online)
255                 return;
256
257         /* the order here really doesn't matter */
258         atomic_dec(&rq->rd->rto_count);
259         cpumask_clear_cpu(rq->cpu, rq->rd->rto_mask);
260 }
261
262 static void update_rt_migration(struct rt_rq *rt_rq)
263 {
264         if (rt_rq->rt_nr_migratory && rt_rq->rt_nr_total > 1) {
265                 if (!rt_rq->overloaded) {
266                         rt_set_overload(rq_of_rt_rq(rt_rq));
267                         rt_rq->overloaded = 1;
268                 }
269         } else if (rt_rq->overloaded) {
270                 rt_clear_overload(rq_of_rt_rq(rt_rq));
271                 rt_rq->overloaded = 0;
272         }
273 }
274
275 static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
276 {
277         if (!rt_entity_is_task(rt_se))
278                 return;
279
280         rt_rq = &rq_of_rt_rq(rt_rq)->rt;
281
282         rt_rq->rt_nr_total++;
283         if (rt_se->nr_cpus_allowed > 1)
284                 rt_rq->rt_nr_migratory++;
285
286         update_rt_migration(rt_rq);
287 }
288
289 static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
290 {
291         if (!rt_entity_is_task(rt_se))
292                 return;
293
294         rt_rq = &rq_of_rt_rq(rt_rq)->rt;
295
296         rt_rq->rt_nr_total--;
297         if (rt_se->nr_cpus_allowed > 1)
298                 rt_rq->rt_nr_migratory--;
299
300         update_rt_migration(rt_rq);
301 }
302
303 static inline int has_pushable_tasks(struct rq *rq)
304 {
305         return !plist_head_empty(&rq->rt.pushable_tasks);
306 }
307
308 static void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
309 {
310         plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
311         plist_node_init(&p->pushable_tasks, p->prio);
312         plist_add(&p->pushable_tasks, &rq->rt.pushable_tasks);
313
314         /* Update the highest prio pushable task */
315         if (p->prio < rq->rt.highest_prio.next)
316                 rq->rt.highest_prio.next = p->prio;
317 }
318
319 static void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
320 {
321         plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
322
323         /* Update the new highest prio pushable task */
324         if (has_pushable_tasks(rq)) {
325                 p = plist_first_entry(&rq->rt.pushable_tasks,
326                                       struct task_struct, pushable_tasks);
327                 rq->rt.highest_prio.next = p->prio;
328         } else
329                 rq->rt.highest_prio.next = MAX_RT_PRIO;
330 }
331
332 #else
333
334 static inline void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
335 {
336 }
337
338 static inline void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
339 {
340 }
341
342 static inline
343 void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
344 {
345 }
346
347 static inline
348 void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
349 {
350 }
351
352 #endif /* CONFIG_SMP */
353
354 static inline int on_rt_rq(struct sched_rt_entity *rt_se)
355 {
356         return !list_empty(&rt_se->run_list);
357 }
358
359 #ifdef CONFIG_RT_GROUP_SCHED
360
361 static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
362 {
363         if (!rt_rq->tg)
364                 return RUNTIME_INF;
365
366         return rt_rq->rt_runtime;
367 }
368
369 static inline u64 sched_rt_period(struct rt_rq *rt_rq)
370 {
371         return ktime_to_ns(rt_rq->tg->rt_bandwidth.rt_period);
372 }
373
374 typedef struct task_group *rt_rq_iter_t;
375
376 static inline struct task_group *next_task_group(struct task_group *tg)
377 {
378         do {
379                 tg = list_entry_rcu(tg->list.next,
380                         typeof(struct task_group), list);
381         } while (&tg->list != &task_groups && task_group_is_autogroup(tg));
382
383         if (&tg->list == &task_groups)
384                 tg = NULL;
385
386         return tg;
387 }
388
389 #define for_each_rt_rq(rt_rq, iter, rq)                                 \
390         for (iter = container_of(&task_groups, typeof(*iter), list);    \
391                 (iter = next_task_group(iter)) &&                       \
392                 (rt_rq = iter->rt_rq[cpu_of(rq)]);)
393
394 static inline void list_add_leaf_rt_rq(struct rt_rq *rt_rq)
395 {
396         list_add_rcu(&rt_rq->leaf_rt_rq_list,
397                         &rq_of_rt_rq(rt_rq)->leaf_rt_rq_list);
398 }
399
400 static inline void list_del_leaf_rt_rq(struct rt_rq *rt_rq)
401 {
402         list_del_rcu(&rt_rq->leaf_rt_rq_list);
403 }
404
405 #define for_each_leaf_rt_rq(rt_rq, rq) \
406         list_for_each_entry_rcu(rt_rq, &rq->leaf_rt_rq_list, leaf_rt_rq_list)
407
408 #define for_each_sched_rt_entity(rt_se) \
409         for (; rt_se; rt_se = rt_se->parent)
410
411 static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
412 {
413         return rt_se->my_q;
414 }
415
416 static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head);
417 static void dequeue_rt_entity(struct sched_rt_entity *rt_se);
418
419 static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
420 {
421         struct task_struct *curr = rq_of_rt_rq(rt_rq)->curr;
422         struct sched_rt_entity *rt_se;
423
424         int cpu = cpu_of(rq_of_rt_rq(rt_rq));
425
426         rt_se = rt_rq->tg->rt_se[cpu];
427
428         if (rt_rq->rt_nr_running) {
429                 if (rt_se && !on_rt_rq(rt_se))
430                         enqueue_rt_entity(rt_se, false);
431                 if (rt_rq->highest_prio.curr < curr->prio)
432                         resched_task(curr);
433         }
434 }
435
436 static void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
437 {
438         struct sched_rt_entity *rt_se;
439         int cpu = cpu_of(rq_of_rt_rq(rt_rq));
440
441         rt_se = rt_rq->tg->rt_se[cpu];
442
443         if (rt_se && on_rt_rq(rt_se))
444                 dequeue_rt_entity(rt_se);
445 }
446
447 static inline int rt_rq_throttled(struct rt_rq *rt_rq)
448 {
449         return rt_rq->rt_throttled && !rt_rq->rt_nr_boosted;
450 }
451
452 static int rt_se_boosted(struct sched_rt_entity *rt_se)
453 {
454         struct rt_rq *rt_rq = group_rt_rq(rt_se);
455         struct task_struct *p;
456
457         if (rt_rq)
458                 return !!rt_rq->rt_nr_boosted;
459
460         p = rt_task_of(rt_se);
461         return p->prio != p->normal_prio;
462 }
463
464 #ifdef CONFIG_SMP
465 static inline const struct cpumask *sched_rt_period_mask(void)
466 {
467         return cpu_rq(smp_processor_id())->rd->span;
468 }
469 #else
470 static inline const struct cpumask *sched_rt_period_mask(void)
471 {
472         return cpu_online_mask;
473 }
474 #endif
475
476 static inline
477 struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
478 {
479         return container_of(rt_b, struct task_group, rt_bandwidth)->rt_rq[cpu];
480 }
481
482 static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
483 {
484         return &rt_rq->tg->rt_bandwidth;
485 }
486
487 #else /* !CONFIG_RT_GROUP_SCHED */
488
489 static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
490 {
491         return rt_rq->rt_runtime;
492 }
493
494 static inline u64 sched_rt_period(struct rt_rq *rt_rq)
495 {
496         return ktime_to_ns(def_rt_bandwidth.rt_period);
497 }
498
499 typedef struct rt_rq *rt_rq_iter_t;
500
501 #define for_each_rt_rq(rt_rq, iter, rq) \
502         for ((void) iter, rt_rq = &rq->rt; rt_rq; rt_rq = NULL)
503
504 static inline void list_add_leaf_rt_rq(struct rt_rq *rt_rq)
505 {
506 }
507
508 static inline void list_del_leaf_rt_rq(struct rt_rq *rt_rq)
509 {
510 }
511
512 #define for_each_leaf_rt_rq(rt_rq, rq) \
513         for (rt_rq = &rq->rt; rt_rq; rt_rq = NULL)
514
515 #define for_each_sched_rt_entity(rt_se) \
516         for (; rt_se; rt_se = NULL)
517
518 static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
519 {
520         return NULL;
521 }
522
523 static inline void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
524 {
525         if (rt_rq->rt_nr_running)
526                 resched_task(rq_of_rt_rq(rt_rq)->curr);
527 }
528
529 static inline void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
530 {
531 }
532
533 static inline int rt_rq_throttled(struct rt_rq *rt_rq)
534 {
535         return rt_rq->rt_throttled;
536 }
537
538 static inline const struct cpumask *sched_rt_period_mask(void)
539 {
540         return cpu_online_mask;
541 }
542
543 static inline
544 struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
545 {
546         return &cpu_rq(cpu)->rt;
547 }
548
549 static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
550 {
551         return &def_rt_bandwidth;
552 }
553
554 #endif /* CONFIG_RT_GROUP_SCHED */
555
556 #ifdef CONFIG_SMP
557 /*
558  * We ran out of runtime, see if we can borrow some from our neighbours.
559  */
560 static int do_balance_runtime(struct rt_rq *rt_rq)
561 {
562         struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
563         struct root_domain *rd = cpu_rq(smp_processor_id())->rd;
564         int i, weight, more = 0;
565         u64 rt_period;
566
567         weight = cpumask_weight(rd->span);
568
569         raw_spin_lock(&rt_b->rt_runtime_lock);
570         rt_period = ktime_to_ns(rt_b->rt_period);
571         for_each_cpu(i, rd->span) {
572                 struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
573                 s64 diff;
574
575                 if (iter == rt_rq)
576                         continue;
577
578                 raw_spin_lock(&iter->rt_runtime_lock);
579                 /*
580                  * Either all rqs have inf runtime and there's nothing to steal
581                  * or __disable_runtime() below sets a specific rq to inf to
582                  * indicate its been disabled and disalow stealing.
583                  */
584                 if (iter->rt_runtime == RUNTIME_INF)
585                         goto next;
586
587                 /*
588                  * From runqueues with spare time, take 1/n part of their
589                  * spare time, but no more than our period.
590                  */
591                 diff = iter->rt_runtime - iter->rt_time;
592                 if (diff > 0) {
593                         diff = div_u64((u64)diff, weight);
594                         if (rt_rq->rt_runtime + diff > rt_period)
595                                 diff = rt_period - rt_rq->rt_runtime;
596                         iter->rt_runtime -= diff;
597                         rt_rq->rt_runtime += diff;
598                         more = 1;
599                         if (rt_rq->rt_runtime == rt_period) {
600                                 raw_spin_unlock(&iter->rt_runtime_lock);
601                                 break;
602                         }
603                 }
604 next:
605                 raw_spin_unlock(&iter->rt_runtime_lock);
606         }
607         raw_spin_unlock(&rt_b->rt_runtime_lock);
608
609         return more;
610 }
611
612 /*
613  * Ensure this RQ takes back all the runtime it lend to its neighbours.
614  */
615 static void __disable_runtime(struct rq *rq)
616 {
617         struct root_domain *rd = rq->rd;
618         rt_rq_iter_t iter;
619         struct rt_rq *rt_rq;
620
621         if (unlikely(!scheduler_running))
622                 return;
623
624         for_each_rt_rq(rt_rq, iter, rq) {
625                 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
626                 s64 want;
627                 int i;
628
629                 raw_spin_lock(&rt_b->rt_runtime_lock);
630                 raw_spin_lock(&rt_rq->rt_runtime_lock);
631                 /*
632                  * Either we're all inf and nobody needs to borrow, or we're
633                  * already disabled and thus have nothing to do, or we have
634                  * exactly the right amount of runtime to take out.
635                  */
636                 if (rt_rq->rt_runtime == RUNTIME_INF ||
637                                 rt_rq->rt_runtime == rt_b->rt_runtime)
638                         goto balanced;
639                 raw_spin_unlock(&rt_rq->rt_runtime_lock);
640
641                 /*
642                  * Calculate the difference between what we started out with
643                  * and what we current have, that's the amount of runtime
644                  * we lend and now have to reclaim.
645                  */
646                 want = rt_b->rt_runtime - rt_rq->rt_runtime;
647
648                 /*
649                  * Greedy reclaim, take back as much as we can.
650                  */
651                 for_each_cpu(i, rd->span) {
652                         struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
653                         s64 diff;
654
655                         /*
656                          * Can't reclaim from ourselves or disabled runqueues.
657                          */
658                         if (iter == rt_rq || iter->rt_runtime == RUNTIME_INF)
659                                 continue;
660
661                         raw_spin_lock(&iter->rt_runtime_lock);
662                         if (want > 0) {
663                                 diff = min_t(s64, iter->rt_runtime, want);
664                                 iter->rt_runtime -= diff;
665                                 want -= diff;
666                         } else {
667                                 iter->rt_runtime -= want;
668                                 want -= want;
669                         }
670                         raw_spin_unlock(&iter->rt_runtime_lock);
671
672                         if (!want)
673                                 break;
674                 }
675
676                 raw_spin_lock(&rt_rq->rt_runtime_lock);
677                 /*
678                  * We cannot be left wanting - that would mean some runtime
679                  * leaked out of the system.
680                  */
681                 BUG_ON(want);
682 balanced:
683                 /*
684                  * Disable all the borrow logic by pretending we have inf
685                  * runtime - in which case borrowing doesn't make sense.
686                  */
687                 rt_rq->rt_runtime = RUNTIME_INF;
688                 rt_rq->rt_throttled = 0;
689                 raw_spin_unlock(&rt_rq->rt_runtime_lock);
690                 raw_spin_unlock(&rt_b->rt_runtime_lock);
691         }
692 }
693
694 static void disable_runtime(struct rq *rq)
695 {
696         unsigned long flags;
697
698         raw_spin_lock_irqsave(&rq->lock, flags);
699         __disable_runtime(rq);
700         raw_spin_unlock_irqrestore(&rq->lock, flags);
701 }
702
703 static void __enable_runtime(struct rq *rq)
704 {
705         rt_rq_iter_t iter;
706         struct rt_rq *rt_rq;
707
708         if (unlikely(!scheduler_running))
709                 return;
710
711         /*
712          * Reset each runqueue's bandwidth settings
713          */
714         for_each_rt_rq(rt_rq, iter, rq) {
715                 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
716
717                 raw_spin_lock(&rt_b->rt_runtime_lock);
718                 raw_spin_lock(&rt_rq->rt_runtime_lock);
719                 rt_rq->rt_runtime = rt_b->rt_runtime;
720                 rt_rq->rt_time = 0;
721                 rt_rq->rt_throttled = 0;
722                 raw_spin_unlock(&rt_rq->rt_runtime_lock);
723                 raw_spin_unlock(&rt_b->rt_runtime_lock);
724         }
725 }
726
727 static void enable_runtime(struct rq *rq)
728 {
729         unsigned long flags;
730
731         raw_spin_lock_irqsave(&rq->lock, flags);
732         __enable_runtime(rq);
733         raw_spin_unlock_irqrestore(&rq->lock, flags);
734 }
735
736 int update_runtime(struct notifier_block *nfb, unsigned long action, void *hcpu)
737 {
738         int cpu = (int)(long)hcpu;
739
740         switch (action) {
741         case CPU_DOWN_PREPARE:
742         case CPU_DOWN_PREPARE_FROZEN:
743                 disable_runtime(cpu_rq(cpu));
744                 return NOTIFY_OK;
745
746         case CPU_DOWN_FAILED:
747         case CPU_DOWN_FAILED_FROZEN:
748         case CPU_ONLINE:
749         case CPU_ONLINE_FROZEN:
750                 enable_runtime(cpu_rq(cpu));
751                 return NOTIFY_OK;
752
753         default:
754                 return NOTIFY_DONE;
755         }
756 }
757
758 static int balance_runtime(struct rt_rq *rt_rq)
759 {
760         int more = 0;
761
762         if (!sched_feat(RT_RUNTIME_SHARE))
763                 return more;
764
765         if (rt_rq->rt_time > rt_rq->rt_runtime) {
766                 raw_spin_unlock(&rt_rq->rt_runtime_lock);
767                 more = do_balance_runtime(rt_rq);
768                 raw_spin_lock(&rt_rq->rt_runtime_lock);
769         }
770
771         return more;
772 }
773 #else /* !CONFIG_SMP */
774 static inline int balance_runtime(struct rt_rq *rt_rq)
775 {
776         return 0;
777 }
778 #endif /* CONFIG_SMP */
779
780 static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)
781 {
782         int i, idle = 1, throttled = 0;
783         const struct cpumask *span;
784
785         span = sched_rt_period_mask();
786         for_each_cpu(i, span) {
787                 int enqueue = 0;
788                 struct rt_rq *rt_rq = sched_rt_period_rt_rq(rt_b, i);
789                 struct rq *rq = rq_of_rt_rq(rt_rq);
790
791                 raw_spin_lock(&rq->lock);
792                 if (rt_rq->rt_time) {
793                         u64 runtime;
794
795                         raw_spin_lock(&rt_rq->rt_runtime_lock);
796                         if (rt_rq->rt_throttled)
797                                 balance_runtime(rt_rq);
798                         runtime = rt_rq->rt_runtime;
799                         rt_rq->rt_time -= min(rt_rq->rt_time, overrun*runtime);
800                         if (rt_rq->rt_throttled && rt_rq->rt_time < runtime) {
801                                 rt_rq->rt_throttled = 0;
802                                 enqueue = 1;
803
804                                 /*
805                                  * Force a clock update if the CPU was idle,
806                                  * lest wakeup -> unthrottle time accumulate.
807                                  */
808                                 if (rt_rq->rt_nr_running && rq->curr == rq->idle)
809                                         rq->skip_clock_update = -1;
810                         }
811                         if (rt_rq->rt_time || rt_rq->rt_nr_running)
812                                 idle = 0;
813                         raw_spin_unlock(&rt_rq->rt_runtime_lock);
814                 } else if (rt_rq->rt_nr_running) {
815                         idle = 0;
816                         if (!rt_rq_throttled(rt_rq))
817                                 enqueue = 1;
818                 }
819                 if (rt_rq->rt_throttled)
820                         throttled = 1;
821
822                 if (enqueue)
823                         sched_rt_rq_enqueue(rt_rq);
824                 raw_spin_unlock(&rq->lock);
825         }
826
827         if (!throttled && (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF))
828                 return 1;
829
830         return idle;
831 }
832
833 static inline int rt_se_prio(struct sched_rt_entity *rt_se)
834 {
835 #ifdef CONFIG_RT_GROUP_SCHED
836         struct rt_rq *rt_rq = group_rt_rq(rt_se);
837
838         if (rt_rq)
839                 return rt_rq->highest_prio.curr;
840 #endif
841
842         return rt_task_of(rt_se)->prio;
843 }
844
845 static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
846 {
847         u64 runtime = sched_rt_runtime(rt_rq);
848
849         if (rt_rq->rt_throttled)
850                 return rt_rq_throttled(rt_rq);
851
852         if (runtime >= sched_rt_period(rt_rq))
853                 return 0;
854
855         balance_runtime(rt_rq);
856         runtime = sched_rt_runtime(rt_rq);
857         if (runtime == RUNTIME_INF)
858                 return 0;
859
860         if (rt_rq->rt_time > runtime) {
861                 struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
862
863                 /*
864                  * Don't actually throttle groups that have no runtime assigned
865                  * but accrue some time due to boosting.
866                  */
867                 if (likely(rt_b->rt_runtime)) {
868                         static bool once = false;
869
870                         rt_rq->rt_throttled = 1;
871
872                         if (!once) {
873                                 once = true;
874                                 printk_sched("sched: RT throttling activated\n");
875                         }
876                 } else {
877                         /*
878                          * In case we did anyway, make it go away,
879                          * replenishment is a joke, since it will replenish us
880                          * with exactly 0 ns.
881                          */
882                         rt_rq->rt_time = 0;
883                 }
884
885                 if (rt_rq_throttled(rt_rq)) {
886                         sched_rt_rq_dequeue(rt_rq);
887                         return 1;
888                 }
889         }
890
891         return 0;
892 }
893
894 /*
895  * Update the current task's runtime statistics. Skip current tasks that
896  * are not in our scheduling class.
897  */
898 static void update_curr_rt(struct rq *rq)
899 {
900         struct task_struct *curr = rq->curr;
901         struct sched_rt_entity *rt_se = &curr->rt;
902         struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
903         u64 delta_exec;
904
905         if (curr->sched_class != &rt_sched_class)
906                 return;
907
908         delta_exec = rq->clock_task - curr->se.exec_start;
909         if (unlikely((s64)delta_exec < 0))
910                 delta_exec = 0;
911
912         schedstat_set(curr->se.statistics.exec_max,
913                       max(curr->se.statistics.exec_max, delta_exec));
914
915         curr->se.sum_exec_runtime += delta_exec;
916         account_group_exec_runtime(curr, delta_exec);
917
918         curr->se.exec_start = rq->clock_task;
919         cpuacct_charge(curr, delta_exec);
920
921         sched_rt_avg_update(rq, delta_exec);
922
923         if (!rt_bandwidth_enabled())
924                 return;
925
926         for_each_sched_rt_entity(rt_se) {
927                 rt_rq = rt_rq_of_se(rt_se);
928
929                 if (sched_rt_runtime(rt_rq) != RUNTIME_INF) {
930                         raw_spin_lock(&rt_rq->rt_runtime_lock);
931                         rt_rq->rt_time += delta_exec;
932                         if (sched_rt_runtime_exceeded(rt_rq))
933                                 resched_task(curr);
934                         raw_spin_unlock(&rt_rq->rt_runtime_lock);
935                 }
936         }
937 }
938
939 #if defined CONFIG_SMP
940
941 static void
942 inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
943 {
944         struct rq *rq = rq_of_rt_rq(rt_rq);
945
946         if (rq->online && prio < prev_prio)
947                 cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
948 }
949
950 static void
951 dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
952 {
953         struct rq *rq = rq_of_rt_rq(rt_rq);
954
955         if (rq->online && rt_rq->highest_prio.curr != prev_prio)
956                 cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr);
957 }
958
959 #else /* CONFIG_SMP */
960
961 static inline
962 void inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}
963 static inline
964 void dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}
965
966 #endif /* CONFIG_SMP */
967
968 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
969 static void
970 inc_rt_prio(struct rt_rq *rt_rq, int prio)
971 {
972         int prev_prio = rt_rq->highest_prio.curr;
973
974         if (prio < prev_prio)
975                 rt_rq->highest_prio.curr = prio;
976
977         inc_rt_prio_smp(rt_rq, prio, prev_prio);
978 }
979
980 static void
981 dec_rt_prio(struct rt_rq *rt_rq, int prio)
982 {
983         int prev_prio = rt_rq->highest_prio.curr;
984
985         if (rt_rq->rt_nr_running) {
986
987                 WARN_ON(prio < prev_prio);
988
989                 /*
990                  * This may have been our highest task, and therefore
991                  * we may have some recomputation to do
992                  */
993                 if (prio == prev_prio) {
994                         struct rt_prio_array *array = &rt_rq->active;
995
996                         rt_rq->highest_prio.curr =
997                                 sched_find_first_bit(array->bitmap);
998                 }
999
1000         } else
1001                 rt_rq->highest_prio.curr = MAX_RT_PRIO;
1002
1003         dec_rt_prio_smp(rt_rq, prio, prev_prio);
1004 }
1005
1006 #else
1007
1008 static inline void inc_rt_prio(struct rt_rq *rt_rq, int prio) {}
1009 static inline void dec_rt_prio(struct rt_rq *rt_rq, int prio) {}
1010
1011 #endif /* CONFIG_SMP || CONFIG_RT_GROUP_SCHED */
1012
1013 #ifdef CONFIG_RT_GROUP_SCHED
1014
1015 static void
1016 inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
1017 {
1018         if (rt_se_boosted(rt_se))
1019                 rt_rq->rt_nr_boosted++;
1020
1021         if (rt_rq->tg)
1022                 start_rt_bandwidth(&rt_rq->tg->rt_bandwidth);
1023 }
1024
1025 static void
1026 dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
1027 {
1028         if (rt_se_boosted(rt_se))
1029                 rt_rq->rt_nr_boosted--;
1030
1031         WARN_ON(!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted);
1032 }
1033
1034 #else /* CONFIG_RT_GROUP_SCHED */
1035
1036 static void
1037 inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
1038 {
1039         start_rt_bandwidth(&def_rt_bandwidth);
1040 }
1041
1042 static inline
1043 void dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) {}
1044
1045 #endif /* CONFIG_RT_GROUP_SCHED */
1046
1047 static inline
1048 void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
1049 {
1050         int prio = rt_se_prio(rt_se);
1051
1052         WARN_ON(!rt_prio(prio));
1053         rt_rq->rt_nr_running++;
1054
1055         inc_rt_prio(rt_rq, prio);
1056         inc_rt_migration(rt_se, rt_rq);
1057         inc_rt_group(rt_se, rt_rq);
1058 }
1059
1060 static inline
1061 void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
1062 {
1063         WARN_ON(!rt_prio(rt_se_prio(rt_se)));
1064         WARN_ON(!rt_rq->rt_nr_running);
1065         rt_rq->rt_nr_running--;
1066
1067         dec_rt_prio(rt_rq, rt_se_prio(rt_se));
1068         dec_rt_migration(rt_se, rt_rq);
1069         dec_rt_group(rt_se, rt_rq);
1070 }
1071
1072 static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
1073 {
1074         struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
1075         struct rt_prio_array *array = &rt_rq->active;
1076         struct rt_rq *group_rq = group_rt_rq(rt_se);
1077         struct list_head *queue = array->queue + rt_se_prio(rt_se);
1078
1079         /*
1080          * Don't enqueue the group if its throttled, or when empty.
1081          * The latter is a consequence of the former when a child group
1082          * get throttled and the current group doesn't have any other
1083          * active members.
1084          */
1085         if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running))
1086                 return;
1087
1088         if (!rt_rq->rt_nr_running)
1089                 list_add_leaf_rt_rq(rt_rq);
1090
1091         if (head)
1092                 list_add(&rt_se->run_list, queue);
1093         else
1094                 list_add_tail(&rt_se->run_list, queue);
1095         __set_bit(rt_se_prio(rt_se), array->bitmap);
1096
1097         inc_rt_tasks(rt_se, rt_rq);
1098 }
1099
1100 static void __dequeue_rt_entity(struct sched_rt_entity *rt_se)
1101 {
1102         struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
1103         struct rt_prio_array *array = &rt_rq->active;
1104
1105         list_del_init(&rt_se->run_list);
1106         if (list_empty(array->queue + rt_se_prio(rt_se)))
1107                 __clear_bit(rt_se_prio(rt_se), array->bitmap);
1108
1109         dec_rt_tasks(rt_se, rt_rq);
1110         if (!rt_rq->rt_nr_running)
1111                 list_del_leaf_rt_rq(rt_rq);
1112 }
1113
1114 /*
1115  * Because the prio of an upper entry depends on the lower
1116  * entries, we must remove entries top - down.
1117  */
1118 static void dequeue_rt_stack(struct sched_rt_entity *rt_se)
1119 {
1120         struct sched_rt_entity *back = NULL;
1121
1122         for_each_sched_rt_entity(rt_se) {
1123                 rt_se->back = back;
1124                 back = rt_se;
1125         }
1126
1127         for (rt_se = back; rt_se; rt_se = rt_se->back) {
1128                 if (on_rt_rq(rt_se))
1129                         __dequeue_rt_entity(rt_se);
1130         }
1131 }
1132
1133 static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
1134 {
1135         dequeue_rt_stack(rt_se);
1136         for_each_sched_rt_entity(rt_se)
1137                 __enqueue_rt_entity(rt_se, head);
1138 }
1139
1140 static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
1141 {
1142         dequeue_rt_stack(rt_se);
1143
1144         for_each_sched_rt_entity(rt_se) {
1145                 struct rt_rq *rt_rq = group_rt_rq(rt_se);
1146
1147                 if (rt_rq && rt_rq->rt_nr_running)
1148                         __enqueue_rt_entity(rt_se, false);
1149         }
1150 }
1151
1152 /*
1153  * Adding/removing a task to/from a priority array:
1154  */
1155 static void
1156 enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)
1157 {
1158         struct sched_rt_entity *rt_se = &p->rt;
1159
1160         if (flags & ENQUEUE_WAKEUP)
1161                 rt_se->timeout = 0;
1162
1163         enqueue_rt_entity(rt_se, flags & ENQUEUE_HEAD);
1164
1165         if (!task_current(rq, p) && p->rt.nr_cpus_allowed > 1)
1166                 enqueue_pushable_task(rq, p);
1167
1168         inc_nr_running(rq);
1169 }
1170
1171 static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags)
1172 {
1173         struct sched_rt_entity *rt_se = &p->rt;
1174
1175         update_curr_rt(rq);
1176         dequeue_rt_entity(rt_se);
1177
1178         dequeue_pushable_task(rq, p);
1179
1180         dec_nr_running(rq);
1181 }
1182
1183 /*
1184  * Put task to the head or the end of the run list without the overhead of
1185  * dequeue followed by enqueue.
1186  */
1187 static void
1188 requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se, int head)
1189 {
1190         if (on_rt_rq(rt_se)) {
1191                 struct rt_prio_array *array = &rt_rq->active;
1192                 struct list_head *queue = array->queue + rt_se_prio(rt_se);
1193
1194                 if (head)
1195                         list_move(&rt_se->run_list, queue);
1196                 else
1197                         list_move_tail(&rt_se->run_list, queue);
1198         }
1199 }
1200
1201 static void requeue_task_rt(struct rq *rq, struct task_struct *p, int head)
1202 {
1203         struct sched_rt_entity *rt_se = &p->rt;
1204         struct rt_rq *rt_rq;
1205
1206         for_each_sched_rt_entity(rt_se) {
1207                 rt_rq = rt_rq_of_se(rt_se);
1208                 requeue_rt_entity(rt_rq, rt_se, head);
1209         }
1210 }
1211
1212 static void yield_task_rt(struct rq *rq)
1213 {
1214         requeue_task_rt(rq, rq->curr, 0);
1215 }
1216
1217 #ifdef CONFIG_SMP
1218 static int find_lowest_rq(struct task_struct *task);
1219
1220 static int
1221 select_task_rq_rt(struct task_struct *p, int sd_flag, int flags)
1222 {
1223         struct task_struct *curr;
1224         struct rq *rq;
1225         int cpu;
1226
1227         cpu = task_cpu(p);
1228
1229         if (p->rt.nr_cpus_allowed == 1)
1230                 goto out;
1231
1232         /* For anything but wake ups, just return the task_cpu */
1233         if (sd_flag != SD_BALANCE_WAKE && sd_flag != SD_BALANCE_FORK)
1234                 goto out;
1235
1236         rq = cpu_rq(cpu);
1237
1238         rcu_read_lock();
1239         curr = ACCESS_ONCE(rq->curr); /* unlocked access */
1240
1241         /*
1242          * If the current task on @p's runqueue is an RT task, then
1243          * try to see if we can wake this RT task up on another
1244          * runqueue. Otherwise simply start this RT task
1245          * on its current runqueue.
1246          *
1247          * We want to avoid overloading runqueues. If the woken
1248          * task is a higher priority, then it will stay on this CPU
1249          * and the lower prio task should be moved to another CPU.
1250          * Even though this will probably make the lower prio task
1251          * lose its cache, we do not want to bounce a higher task
1252          * around just because it gave up its CPU, perhaps for a
1253          * lock?
1254          *
1255          * For equal prio tasks, we just let the scheduler sort it out.
1256          *
1257          * Otherwise, just let it ride on the affined RQ and the
1258          * post-schedule router will push the preempted task away
1259          *
1260          * This test is optimistic, if we get it wrong the load-balancer
1261          * will have to sort it out.
1262          */
1263         if (curr && unlikely(rt_task(curr)) &&
1264             (curr->rt.nr_cpus_allowed < 2 ||
1265              curr->prio <= p->prio) &&
1266             (p->rt.nr_cpus_allowed > 1)) {
1267                 int target = find_lowest_rq(p);
1268
1269                 if (target != -1)
1270                         cpu = target;
1271         }
1272         rcu_read_unlock();
1273
1274 out:
1275         return cpu;
1276 }
1277
1278 static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
1279 {
1280         if (rq->curr->rt.nr_cpus_allowed == 1)
1281                 return;
1282
1283         if (p->rt.nr_cpus_allowed != 1
1284             && cpupri_find(&rq->rd->cpupri, p, NULL))
1285                 return;
1286
1287         if (!cpupri_find(&rq->rd->cpupri, rq->curr, NULL))
1288                 return;
1289
1290         /*
1291          * There appears to be other cpus that can accept
1292          * current and none to run 'p', so lets reschedule
1293          * to try and push current away:
1294          */
1295         requeue_task_rt(rq, p, 1);
1296         resched_task(rq->curr);
1297 }
1298
1299 #endif /* CONFIG_SMP */
1300
1301 /*
1302  * Preempt the current task with a newly woken task if needed:
1303  */
1304 static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags)
1305 {
1306         if (p->prio < rq->curr->prio) {
1307                 resched_task(rq->curr);
1308                 return;
1309         }
1310
1311 #ifdef CONFIG_SMP
1312         /*
1313          * If:
1314          *
1315          * - the newly woken task is of equal priority to the current task
1316          * - the newly woken task is non-migratable while current is migratable
1317          * - current will be preempted on the next reschedule
1318          *
1319          * we should check to see if current can readily move to a different
1320          * cpu.  If so, we will reschedule to allow the push logic to try
1321          * to move current somewhere else, making room for our non-migratable
1322          * task.
1323          */
1324         if (p->prio == rq->curr->prio && !test_tsk_need_resched(rq->curr))
1325                 check_preempt_equal_prio(rq, p);
1326 #endif
1327 }
1328
1329 static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
1330                                                    struct rt_rq *rt_rq)
1331 {
1332         struct rt_prio_array *array = &rt_rq->active;
1333         struct sched_rt_entity *next = NULL;
1334         struct list_head *queue;
1335         int idx;
1336
1337         idx = sched_find_first_bit(array->bitmap);
1338         BUG_ON(idx >= MAX_RT_PRIO);
1339
1340         queue = array->queue + idx;
1341         next = list_entry(queue->next, struct sched_rt_entity, run_list);
1342
1343         return next;
1344 }
1345
1346 static struct task_struct *_pick_next_task_rt(struct rq *rq)
1347 {
1348         struct sched_rt_entity *rt_se;
1349         struct task_struct *p;
1350         struct rt_rq *rt_rq;
1351
1352         rt_rq = &rq->rt;
1353
1354         if (!rt_rq->rt_nr_running)
1355                 return NULL;
1356
1357         if (rt_rq_throttled(rt_rq))
1358                 return NULL;
1359
1360         do {
1361                 rt_se = pick_next_rt_entity(rq, rt_rq);
1362                 BUG_ON(!rt_se);
1363                 rt_rq = group_rt_rq(rt_se);
1364         } while (rt_rq);
1365
1366         p = rt_task_of(rt_se);
1367         p->se.exec_start = rq->clock_task;
1368
1369         return p;
1370 }
1371
1372 static struct task_struct *pick_next_task_rt(struct rq *rq)
1373 {
1374         struct task_struct *p = _pick_next_task_rt(rq);
1375
1376         /* The running task is never eligible for pushing */
1377         if (p)
1378                 dequeue_pushable_task(rq, p);
1379
1380 #ifdef CONFIG_SMP
1381         /*
1382          * We detect this state here so that we can avoid taking the RQ
1383          * lock again later if there is no need to push
1384          */
1385         rq->post_schedule = has_pushable_tasks(rq);
1386 #endif
1387
1388         return p;
1389 }
1390
1391 static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
1392 {
1393         update_curr_rt(rq);
1394
1395         /*
1396          * The previous task needs to be made eligible for pushing
1397          * if it is still active
1398          */
1399         if (on_rt_rq(&p->rt) && p->rt.nr_cpus_allowed > 1)
1400                 enqueue_pushable_task(rq, p);
1401 }
1402
1403 #ifdef CONFIG_SMP
1404
1405 /* Only try algorithms three times */
1406 #define RT_MAX_TRIES 3
1407
1408 static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
1409 {
1410         if (!task_running(rq, p) &&
1411             (cpu < 0 || cpumask_test_cpu(cpu, tsk_cpus_allowed(p))) &&
1412             (p->rt.nr_cpus_allowed > 1))
1413                 return 1;
1414         return 0;
1415 }
1416
1417 /* Return the second highest RT task, NULL otherwise */
1418 static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu)
1419 {
1420         struct task_struct *next = NULL;
1421         struct sched_rt_entity *rt_se;
1422         struct rt_prio_array *array;
1423         struct rt_rq *rt_rq;
1424         int idx;
1425
1426         for_each_leaf_rt_rq(rt_rq, rq) {
1427                 array = &rt_rq->active;
1428                 idx = sched_find_first_bit(array->bitmap);
1429 next_idx:
1430                 if (idx >= MAX_RT_PRIO)
1431                         continue;
1432                 if (next && next->prio <= idx)
1433                         continue;
1434                 list_for_each_entry(rt_se, array->queue + idx, run_list) {
1435                         struct task_struct *p;
1436
1437                         if (!rt_entity_is_task(rt_se))
1438                                 continue;
1439
1440                         p = rt_task_of(rt_se);
1441                         if (pick_rt_task(rq, p, cpu)) {
1442                                 next = p;
1443                                 break;
1444                         }
1445                 }
1446                 if (!next) {
1447                         idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
1448                         goto next_idx;
1449                 }
1450         }
1451
1452         return next;
1453 }
1454
1455 static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);
1456
1457 static int find_lowest_rq(struct task_struct *task)
1458 {
1459         struct sched_domain *sd;
1460         struct cpumask *lowest_mask = __get_cpu_var(local_cpu_mask);
1461         int this_cpu = smp_processor_id();
1462         int cpu      = task_cpu(task);
1463
1464         /* Make sure the mask is initialized first */
1465         if (unlikely(!lowest_mask))
1466                 return -1;
1467
1468         if (task->rt.nr_cpus_allowed == 1)
1469                 return -1; /* No other targets possible */
1470
1471         if (!cpupri_find(&task_rq(task)->rd->cpupri, task, lowest_mask))
1472                 return -1; /* No targets found */
1473
1474         /*
1475          * At this point we have built a mask of cpus representing the
1476          * lowest priority tasks in the system.  Now we want to elect
1477          * the best one based on our affinity and topology.
1478          *
1479          * We prioritize the last cpu that the task executed on since
1480          * it is most likely cache-hot in that location.
1481          */
1482         if (cpumask_test_cpu(cpu, lowest_mask))
1483                 return cpu;
1484
1485         /*
1486          * Otherwise, we consult the sched_domains span maps to figure
1487          * out which cpu is logically closest to our hot cache data.
1488          */
1489         if (!cpumask_test_cpu(this_cpu, lowest_mask))
1490                 this_cpu = -1; /* Skip this_cpu opt if not among lowest */
1491
1492         rcu_read_lock();
1493         for_each_domain(cpu, sd) {
1494                 if (sd->flags & SD_WAKE_AFFINE) {
1495                         int best_cpu;
1496
1497                         /*
1498                          * "this_cpu" is cheaper to preempt than a
1499                          * remote processor.
1500                          */
1501                         if (this_cpu != -1 &&
1502                             cpumask_test_cpu(this_cpu, sched_domain_span(sd))) {
1503                                 rcu_read_unlock();
1504                                 return this_cpu;
1505                         }
1506
1507                         best_cpu = cpumask_first_and(lowest_mask,
1508                                                      sched_domain_span(sd));
1509                         if (best_cpu < nr_cpu_ids) {
1510                                 rcu_read_unlock();
1511                                 return best_cpu;
1512                         }
1513                 }
1514         }
1515         rcu_read_unlock();
1516
1517         /*
1518          * And finally, if there were no matches within the domains
1519          * just give the caller *something* to work with from the compatible
1520          * locations.
1521          */
1522         if (this_cpu != -1)
1523                 return this_cpu;
1524
1525         cpu = cpumask_any(lowest_mask);
1526         if (cpu < nr_cpu_ids)
1527                 return cpu;
1528         return -1;
1529 }
1530
1531 /* Will lock the rq it finds */
1532 static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
1533 {
1534         struct rq *lowest_rq = NULL;
1535         int tries;
1536         int cpu;
1537
1538         for (tries = 0; tries < RT_MAX_TRIES; tries++) {
1539                 cpu = find_lowest_rq(task);
1540
1541                 if ((cpu == -1) || (cpu == rq->cpu))
1542                         break;
1543
1544                 lowest_rq = cpu_rq(cpu);
1545
1546                 /* if the prio of this runqueue changed, try again */
1547                 if (double_lock_balance(rq, lowest_rq)) {
1548                         /*
1549                          * We had to unlock the run queue. In
1550                          * the mean time, task could have
1551                          * migrated already or had its affinity changed.
1552                          * Also make sure that it wasn't scheduled on its rq.
1553                          */
1554                         if (unlikely(task_rq(task) != rq ||
1555                                      !cpumask_test_cpu(lowest_rq->cpu,
1556                                                        tsk_cpus_allowed(task)) ||
1557                                      task_running(rq, task) ||
1558                                      !task->on_rq)) {
1559
1560                                 raw_spin_unlock(&lowest_rq->lock);
1561                                 lowest_rq = NULL;
1562                                 break;
1563                         }
1564                 }
1565
1566                 /* If this rq is still suitable use it. */
1567                 if (lowest_rq->rt.highest_prio.curr > task->prio)
1568                         break;
1569
1570                 /* try again */
1571                 double_unlock_balance(rq, lowest_rq);
1572                 lowest_rq = NULL;
1573         }
1574
1575         return lowest_rq;
1576 }
1577
1578 static struct task_struct *pick_next_pushable_task(struct rq *rq)
1579 {
1580         struct task_struct *p;
1581
1582         if (!has_pushable_tasks(rq))
1583                 return NULL;
1584
1585         p = plist_first_entry(&rq->rt.pushable_tasks,
1586                               struct task_struct, pushable_tasks);
1587
1588         BUG_ON(rq->cpu != task_cpu(p));
1589         BUG_ON(task_current(rq, p));
1590         BUG_ON(p->rt.nr_cpus_allowed <= 1);
1591
1592         BUG_ON(!p->on_rq);
1593         BUG_ON(!rt_task(p));
1594
1595         return p;
1596 }
1597
1598 /*
1599  * If the current CPU has more than one RT task, see if the non
1600  * running task can migrate over to a CPU that is running a task
1601  * of lesser priority.
1602  */
1603 static int push_rt_task(struct rq *rq)
1604 {
1605         struct task_struct *next_task;
1606         struct rq *lowest_rq;
1607         int ret = 0;
1608
1609         if (!rq->rt.overloaded)
1610                 return 0;
1611
1612         next_task = pick_next_pushable_task(rq);
1613         if (!next_task)
1614                 return 0;
1615
1616 #ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW
1617        if (unlikely(task_running(rq, next_task)))
1618                return 0;
1619 #endif
1620
1621 retry:
1622         if (unlikely(next_task == rq->curr)) {
1623                 WARN_ON(1);
1624                 return 0;
1625         }
1626
1627         /*
1628          * It's possible that the next_task slipped in of
1629          * higher priority than current. If that's the case
1630          * just reschedule current.
1631          */
1632         if (unlikely(next_task->prio < rq->curr->prio)) {
1633                 resched_task(rq->curr);
1634                 return 0;
1635         }
1636
1637         /* We might release rq lock */
1638         get_task_struct(next_task);
1639
1640         /* find_lock_lowest_rq locks the rq if found */
1641         lowest_rq = find_lock_lowest_rq(next_task, rq);
1642         if (!lowest_rq) {
1643                 struct task_struct *task;
1644                 /*
1645                  * find_lock_lowest_rq releases rq->lock
1646                  * so it is possible that next_task has migrated.
1647                  *
1648                  * We need to make sure that the task is still on the same
1649                  * run-queue and is also still the next task eligible for
1650                  * pushing.
1651                  */
1652                 task = pick_next_pushable_task(rq);
1653                 if (task_cpu(next_task) == rq->cpu && task == next_task) {
1654                         /*
1655                          * The task hasn't migrated, and is still the next
1656                          * eligible task, but we failed to find a run-queue
1657                          * to push it to.  Do not retry in this case, since
1658                          * other cpus will pull from us when ready.
1659                          */
1660                         goto out;
1661                 }
1662
1663                 if (!task)
1664                         /* No more tasks, just exit */
1665                         goto out;
1666
1667                 /*
1668                  * Something has shifted, try again.
1669                  */
1670                 put_task_struct(next_task);
1671                 next_task = task;
1672                 goto retry;
1673         }
1674
1675         deactivate_task(rq, next_task, 0);
1676         set_task_cpu(next_task, lowest_rq->cpu);
1677         activate_task(lowest_rq, next_task, 0);
1678         ret = 1;
1679
1680         resched_task(lowest_rq->curr);
1681
1682         double_unlock_balance(rq, lowest_rq);
1683
1684 out:
1685         put_task_struct(next_task);
1686
1687         return ret;
1688 }
1689
1690 static void push_rt_tasks(struct rq *rq)
1691 {
1692         /* push_rt_task will return true if it moved an RT */
1693         while (push_rt_task(rq))
1694                 ;
1695 }
1696
1697 static int pull_rt_task(struct rq *this_rq)
1698 {
1699         int this_cpu = this_rq->cpu, ret = 0, cpu;
1700         struct task_struct *p;
1701         struct rq *src_rq;
1702
1703         if (likely(!rt_overloaded(this_rq)))
1704                 return 0;
1705
1706         for_each_cpu(cpu, this_rq->rd->rto_mask) {
1707                 if (this_cpu == cpu)
1708                         continue;
1709
1710                 src_rq = cpu_rq(cpu);
1711
1712                 /*
1713                  * Don't bother taking the src_rq->lock if the next highest
1714                  * task is known to be lower-priority than our current task.
1715                  * This may look racy, but if this value is about to go
1716                  * logically higher, the src_rq will push this task away.
1717                  * And if its going logically lower, we do not care
1718                  */
1719                 if (src_rq->rt.highest_prio.next >=
1720                     this_rq->rt.highest_prio.curr)
1721                         continue;
1722
1723                 /*
1724                  * We can potentially drop this_rq's lock in
1725                  * double_lock_balance, and another CPU could
1726                  * alter this_rq
1727                  */
1728                 double_lock_balance(this_rq, src_rq);
1729
1730                 /*
1731                  * Are there still pullable RT tasks?
1732                  */
1733                 if (src_rq->rt.rt_nr_running <= 1)
1734                         goto skip;
1735
1736                 p = pick_next_highest_task_rt(src_rq, this_cpu);
1737
1738                 /*
1739                  * Do we have an RT task that preempts
1740                  * the to-be-scheduled task?
1741                  */
1742                 if (p && (p->prio < this_rq->rt.highest_prio.curr)) {
1743                         WARN_ON(p == src_rq->curr);
1744                         WARN_ON(!p->on_rq);
1745
1746                         /*
1747                          * There's a chance that p is higher in priority
1748                          * than what's currently running on its cpu.
1749                          * This is just that p is wakeing up and hasn't
1750                          * had a chance to schedule. We only pull
1751                          * p if it is lower in priority than the
1752                          * current task on the run queue
1753                          */
1754                         if (p->prio < src_rq->curr->prio)
1755                                 goto skip;
1756
1757                         ret = 1;
1758
1759                         deactivate_task(src_rq, p, 0);
1760                         set_task_cpu(p, this_cpu);
1761                         activate_task(this_rq, p, 0);
1762                         /*
1763                          * We continue with the search, just in
1764                          * case there's an even higher prio task
1765                          * in another runqueue. (low likelihood
1766                          * but possible)
1767                          */
1768                 }
1769 skip:
1770                 double_unlock_balance(this_rq, src_rq);
1771         }
1772
1773         return ret;
1774 }
1775
1776 static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
1777 {
1778         /* Try to pull RT tasks here if we lower this rq's prio */
1779         if (rq->rt.highest_prio.curr > prev->prio)
1780                 pull_rt_task(rq);
1781 }
1782
1783 static void post_schedule_rt(struct rq *rq)
1784 {
1785         push_rt_tasks(rq);
1786 }
1787
1788 /*
1789  * If we are not running and we are not going to reschedule soon, we should
1790  * try to push tasks away now
1791  */
1792 static void task_woken_rt(struct rq *rq, struct task_struct *p)
1793 {
1794         if (!task_running(rq, p) &&
1795             !test_tsk_need_resched(rq->curr) &&
1796             has_pushable_tasks(rq) &&
1797             p->rt.nr_cpus_allowed > 1 &&
1798             rt_task(rq->curr) &&
1799             (rq->curr->rt.nr_cpus_allowed < 2 ||
1800              rq->curr->prio <= p->prio))
1801                 push_rt_tasks(rq);
1802 }
1803
1804 static void set_cpus_allowed_rt(struct task_struct *p,
1805                                 const struct cpumask *new_mask)
1806 {
1807         int weight = cpumask_weight(new_mask);
1808
1809         BUG_ON(!rt_task(p));
1810
1811         /*
1812          * Update the migration status of the RQ if we have an RT task
1813          * which is running AND changing its weight value.
1814          */
1815         if (p->on_rq && (weight != p->rt.nr_cpus_allowed)) {
1816                 struct rq *rq = task_rq(p);
1817
1818                 if (!task_current(rq, p)) {
1819                         /*
1820                          * Make sure we dequeue this task from the pushable list
1821                          * before going further.  It will either remain off of
1822                          * the list because we are no longer pushable, or it
1823                          * will be requeued.
1824                          */
1825                         if (p->rt.nr_cpus_allowed > 1)
1826                                 dequeue_pushable_task(rq, p);
1827
1828                         /*
1829                          * Requeue if our weight is changing and still > 1
1830                          */
1831                         if (weight > 1)
1832                                 enqueue_pushable_task(rq, p);
1833
1834                 }
1835
1836                 if ((p->rt.nr_cpus_allowed <= 1) && (weight > 1)) {
1837                         rq->rt.rt_nr_migratory++;
1838                 } else if ((p->rt.nr_cpus_allowed > 1) && (weight <= 1)) {
1839                         BUG_ON(!rq->rt.rt_nr_migratory);
1840                         rq->rt.rt_nr_migratory--;
1841                 }
1842
1843                 update_rt_migration(&rq->rt);
1844         }
1845 }
1846
1847 /* Assumes rq->lock is held */
1848 static void rq_online_rt(struct rq *rq)
1849 {
1850         if (rq->rt.overloaded)
1851                 rt_set_overload(rq);
1852
1853         __enable_runtime(rq);
1854
1855         cpupri_set(&rq->rd->cpupri, rq->cpu, rq->rt.highest_prio.curr);
1856 }
1857
1858 /* Assumes rq->lock is held */
1859 static void rq_offline_rt(struct rq *rq)
1860 {
1861         if (rq->rt.overloaded)
1862                 rt_clear_overload(rq);
1863
1864         __disable_runtime(rq);
1865
1866         cpupri_set(&rq->rd->cpupri, rq->cpu, CPUPRI_INVALID);
1867 }
1868
1869 /*
1870  * When switch from the rt queue, we bring ourselves to a position
1871  * that we might want to pull RT tasks from other runqueues.
1872  */
1873 static void switched_from_rt(struct rq *rq, struct task_struct *p)
1874 {
1875         /*
1876          * If there are other RT tasks then we will reschedule
1877          * and the scheduling of the other RT tasks will handle
1878          * the balancing. But if we are the last RT task
1879          * we may need to handle the pulling of RT tasks
1880          * now.
1881          */
1882         if (p->on_rq && !rq->rt.rt_nr_running)
1883                 pull_rt_task(rq);
1884 }
1885
1886 void init_sched_rt_class(void)
1887 {
1888         unsigned int i;
1889
1890         for_each_possible_cpu(i) {
1891                 zalloc_cpumask_var_node(&per_cpu(local_cpu_mask, i),
1892                                         GFP_KERNEL, cpu_to_node(i));
1893         }
1894 }
1895 #endif /* CONFIG_SMP */
1896
1897 /*
1898  * When switching a task to RT, we may overload the runqueue
1899  * with RT tasks. In this case we try to push them off to
1900  * other runqueues.
1901  */
1902 static void switched_to_rt(struct rq *rq, struct task_struct *p)
1903 {
1904         int check_resched = 1;
1905
1906         /*
1907          * If we are already running, then there's nothing
1908          * that needs to be done. But if we are not running
1909          * we may need to preempt the current running task.
1910          * If that current running task is also an RT task
1911          * then see if we can move to another run queue.
1912          */
1913         if (p->on_rq && rq->curr != p) {
1914 #ifdef CONFIG_SMP
1915                 if (rq->rt.overloaded && push_rt_task(rq) &&
1916                     /* Don't resched if we changed runqueues */
1917                     rq != task_rq(p))
1918                         check_resched = 0;
1919 #endif /* CONFIG_SMP */
1920                 if (check_resched && p->prio < rq->curr->prio)
1921                         resched_task(rq->curr);
1922         }
1923 }
1924
1925 /*
1926  * Priority of the task has changed. This may cause
1927  * us to initiate a push or pull.
1928  */
1929 static void
1930 prio_changed_rt(struct rq *rq, struct task_struct *p, int oldprio)
1931 {
1932         if (!p->on_rq)
1933                 return;
1934
1935         if (rq->curr == p) {
1936 #ifdef CONFIG_SMP
1937                 /*
1938                  * If our priority decreases while running, we
1939                  * may need to pull tasks to this runqueue.
1940                  */
1941                 if (oldprio < p->prio)
1942                         pull_rt_task(rq);
1943                 /*
1944                  * If there's a higher priority task waiting to run
1945                  * then reschedule. Note, the above pull_rt_task
1946                  * can release the rq lock and p could migrate.
1947                  * Only reschedule if p is still on the same runqueue.
1948                  */
1949                 if (p->prio > rq->rt.highest_prio.curr && rq->curr == p)
1950                         resched_task(p);
1951 #else
1952                 /* For UP simply resched on drop of prio */
1953                 if (oldprio < p->prio)
1954                         resched_task(p);
1955 #endif /* CONFIG_SMP */
1956         } else {
1957                 /*
1958                  * This task is not running, but if it is
1959                  * greater than the current running task
1960                  * then reschedule.
1961                  */
1962                 if (p->prio < rq->curr->prio)
1963                         resched_task(rq->curr);
1964         }
1965 }
1966
1967 static void watchdog(struct rq *rq, struct task_struct *p)
1968 {
1969         unsigned long soft, hard;
1970
1971         /* max may change after cur was read, this will be fixed next tick */
1972         soft = task_rlimit(p, RLIMIT_RTTIME);
1973         hard = task_rlimit_max(p, RLIMIT_RTTIME);
1974
1975         if (soft != RLIM_INFINITY) {
1976                 unsigned long next;
1977
1978                 p->rt.timeout++;
1979                 next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ);
1980                 if (p->rt.timeout > next)
1981                         p->cputime_expires.sched_exp = p->se.sum_exec_runtime;
1982         }
1983 }
1984
1985 static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
1986 {
1987         struct sched_rt_entity *rt_se = &p->rt;
1988
1989         update_curr_rt(rq);
1990
1991         watchdog(rq, p);
1992
1993         /*
1994          * RR tasks need a special form of timeslice management.
1995          * FIFO tasks have no timeslices.
1996          */
1997         if (p->policy != SCHED_RR)
1998                 return;
1999
2000         if (--p->rt.time_slice)
2001                 return;
2002
2003         p->rt.time_slice = RR_TIMESLICE;
2004
2005         /*
2006          * Requeue to the end of queue if we (and all of our ancestors) are the
2007          * only element on the queue
2008          */
2009         for_each_sched_rt_entity(rt_se) {
2010                 if (rt_se->run_list.prev != rt_se->run_list.next) {
2011                         requeue_task_rt(rq, p, 0);
2012                         set_tsk_need_resched(p);
2013                         return;
2014                 }
2015         }
2016 }
2017
2018 static void set_curr_task_rt(struct rq *rq)
2019 {
2020         struct task_struct *p = rq->curr;
2021
2022         p->se.exec_start = rq->clock_task;
2023
2024         /* The running task is never eligible for pushing */
2025         dequeue_pushable_task(rq, p);
2026 }
2027
2028 static unsigned int get_rr_interval_rt(struct rq *rq, struct task_struct *task)
2029 {
2030         /*
2031          * Time slice is 0 for SCHED_FIFO tasks
2032          */
2033         if (task->policy == SCHED_RR)
2034                 return RR_TIMESLICE;
2035         else
2036                 return 0;
2037 }
2038
2039 const struct sched_class rt_sched_class = {
2040         .next                   = &fair_sched_class,
2041         .enqueue_task           = enqueue_task_rt,
2042         .dequeue_task           = dequeue_task_rt,
2043         .yield_task             = yield_task_rt,
2044
2045         .check_preempt_curr     = check_preempt_curr_rt,
2046
2047         .pick_next_task         = pick_next_task_rt,
2048         .put_prev_task          = put_prev_task_rt,
2049
2050 #ifdef CONFIG_SMP
2051         .select_task_rq         = select_task_rq_rt,
2052
2053         .set_cpus_allowed       = set_cpus_allowed_rt,
2054         .rq_online              = rq_online_rt,
2055         .rq_offline             = rq_offline_rt,
2056         .pre_schedule           = pre_schedule_rt,
2057         .post_schedule          = post_schedule_rt,
2058         .task_woken             = task_woken_rt,
2059         .switched_from          = switched_from_rt,
2060 #endif
2061
2062         .set_curr_task          = set_curr_task_rt,
2063         .task_tick              = task_tick_rt,
2064
2065         .get_rr_interval        = get_rr_interval_rt,
2066
2067         .prio_changed           = prio_changed_rt,
2068         .switched_to            = switched_to_rt,
2069 };
2070
2071 #ifdef CONFIG_SCHED_DEBUG
2072 extern void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq);
2073
2074 void print_rt_stats(struct seq_file *m, int cpu)
2075 {
2076         rt_rq_iter_t iter;
2077         struct rt_rq *rt_rq;
2078
2079         rcu_read_lock();
2080         for_each_rt_rq(rt_rq, iter, cpu_rq(cpu))
2081                 print_rt_rq(m, cpu, rt_rq);
2082         rcu_read_unlock();
2083 }
2084 #endif /* CONFIG_SCHED_DEBUG */