projects/linux·blob v4.2 · refs

2358 lines · 53.3 KiB

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