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

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

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

~ [ 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