~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/kernel/sched/rt.c

Version: ~ [ linux-5.12-rc1 ] ~ [ linux-5.11.2 ] ~ [ linux-5.10.19 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.101 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.177 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.222 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.258 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.258 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp