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