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